1 | // Copyright (c) 2011 The LevelDB Authors. All rights reserved. |
2 | // Use of this source code is governed by a BSD-style license that can be |
3 | // found in the LICENSE file. See the AUTHORS file for names of contributors. |
4 | |
5 | #include "util/coding.h" |
6 | |
7 | #include <vector> |
8 | |
9 | #include "gtest/gtest.h" |
10 | |
11 | namespace leveldb { |
12 | |
13 | TEST(Coding, Fixed32) { |
14 | std::string s; |
15 | for (uint32_t v = 0; v < 100000; v++) { |
16 | PutFixed32(&s, v); |
17 | } |
18 | |
19 | const char* p = s.data(); |
20 | for (uint32_t v = 0; v < 100000; v++) { |
21 | uint32_t actual = DecodeFixed32(p); |
22 | ASSERT_EQ(v, actual); |
23 | p += sizeof(uint32_t); |
24 | } |
25 | } |
26 | |
27 | TEST(Coding, Fixed64) { |
28 | std::string s; |
29 | for (int power = 0; power <= 63; power++) { |
30 | uint64_t v = static_cast<uint64_t>(1) << power; |
31 | PutFixed64(&s, v - 1); |
32 | PutFixed64(&s, v + 0); |
33 | PutFixed64(&s, v + 1); |
34 | } |
35 | |
36 | const char* p = s.data(); |
37 | for (int power = 0; power <= 63; power++) { |
38 | uint64_t v = static_cast<uint64_t>(1) << power; |
39 | uint64_t actual; |
40 | actual = DecodeFixed64(p); |
41 | ASSERT_EQ(v - 1, actual); |
42 | p += sizeof(uint64_t); |
43 | |
44 | actual = DecodeFixed64(p); |
45 | ASSERT_EQ(v + 0, actual); |
46 | p += sizeof(uint64_t); |
47 | |
48 | actual = DecodeFixed64(p); |
49 | ASSERT_EQ(v + 1, actual); |
50 | p += sizeof(uint64_t); |
51 | } |
52 | } |
53 | |
54 | // Test that encoding routines generate little-endian encodings |
55 | TEST(Coding, EncodingOutput) { |
56 | std::string dst; |
57 | PutFixed32(&dst, 0x04030201); |
58 | ASSERT_EQ(4, dst.size()); |
59 | ASSERT_EQ(0x01, static_cast<int>(dst[0])); |
60 | ASSERT_EQ(0x02, static_cast<int>(dst[1])); |
61 | ASSERT_EQ(0x03, static_cast<int>(dst[2])); |
62 | ASSERT_EQ(0x04, static_cast<int>(dst[3])); |
63 | |
64 | dst.clear(); |
65 | PutFixed64(&dst, 0x0807060504030201ull); |
66 | ASSERT_EQ(8, dst.size()); |
67 | ASSERT_EQ(0x01, static_cast<int>(dst[0])); |
68 | ASSERT_EQ(0x02, static_cast<int>(dst[1])); |
69 | ASSERT_EQ(0x03, static_cast<int>(dst[2])); |
70 | ASSERT_EQ(0x04, static_cast<int>(dst[3])); |
71 | ASSERT_EQ(0x05, static_cast<int>(dst[4])); |
72 | ASSERT_EQ(0x06, static_cast<int>(dst[5])); |
73 | ASSERT_EQ(0x07, static_cast<int>(dst[6])); |
74 | ASSERT_EQ(0x08, static_cast<int>(dst[7])); |
75 | } |
76 | |
77 | TEST(Coding, Varint32) { |
78 | std::string s; |
79 | for (uint32_t i = 0; i < (32 * 32); i++) { |
80 | uint32_t v = (i / 32) << (i % 32); |
81 | PutVarint32(&s, v); |
82 | } |
83 | |
84 | const char* p = s.data(); |
85 | const char* limit = p + s.size(); |
86 | for (uint32_t i = 0; i < (32 * 32); i++) { |
87 | uint32_t expected = (i / 32) << (i % 32); |
88 | uint32_t actual; |
89 | const char* start = p; |
90 | p = GetVarint32Ptr(p, limit, &actual); |
91 | ASSERT_TRUE(p != nullptr); |
92 | ASSERT_EQ(expected, actual); |
93 | ASSERT_EQ(VarintLength(actual), p - start); |
94 | } |
95 | ASSERT_EQ(p, s.data() + s.size()); |
96 | } |
97 | |
98 | TEST(Coding, Varint64) { |
99 | // Construct the list of values to check |
100 | std::vector<uint64_t> values; |
101 | // Some special values |
102 | values.push_back(0); |
103 | values.push_back(100); |
104 | values.push_back(~static_cast<uint64_t>(0)); |
105 | values.push_back(~static_cast<uint64_t>(0) - 1); |
106 | for (uint32_t k = 0; k < 64; k++) { |
107 | // Test values near powers of two |
108 | const uint64_t power = 1ull << k; |
109 | values.push_back(power); |
110 | values.push_back(power - 1); |
111 | values.push_back(power + 1); |
112 | } |
113 | |
114 | std::string s; |
115 | for (size_t i = 0; i < values.size(); i++) { |
116 | PutVarint64(&s, values[i]); |
117 | } |
118 | |
119 | const char* p = s.data(); |
120 | const char* limit = p + s.size(); |
121 | for (size_t i = 0; i < values.size(); i++) { |
122 | ASSERT_TRUE(p < limit); |
123 | uint64_t actual; |
124 | const char* start = p; |
125 | p = GetVarint64Ptr(p, limit, &actual); |
126 | ASSERT_TRUE(p != nullptr); |
127 | ASSERT_EQ(values[i], actual); |
128 | ASSERT_EQ(VarintLength(actual), p - start); |
129 | } |
130 | ASSERT_EQ(p, limit); |
131 | } |
132 | |
133 | TEST(Coding, Varint32Overflow) { |
134 | uint32_t result; |
135 | std::string input("\x81\x82\x83\x84\x85\x11" ); |
136 | ASSERT_TRUE(GetVarint32Ptr(input.data(), input.data() + input.size(), |
137 | &result) == nullptr); |
138 | } |
139 | |
140 | TEST(Coding, Varint32Truncation) { |
141 | uint32_t large_value = (1u << 31) + 100; |
142 | std::string s; |
143 | PutVarint32(&s, large_value); |
144 | uint32_t result; |
145 | for (size_t len = 0; len < s.size() - 1; len++) { |
146 | ASSERT_TRUE(GetVarint32Ptr(s.data(), s.data() + len, &result) == nullptr); |
147 | } |
148 | ASSERT_TRUE(GetVarint32Ptr(s.data(), s.data() + s.size(), &result) != |
149 | nullptr); |
150 | ASSERT_EQ(large_value, result); |
151 | } |
152 | |
153 | TEST(Coding, Varint64Overflow) { |
154 | uint64_t result; |
155 | std::string input("\x81\x82\x83\x84\x85\x81\x82\x83\x84\x85\x11" ); |
156 | ASSERT_TRUE(GetVarint64Ptr(input.data(), input.data() + input.size(), |
157 | &result) == nullptr); |
158 | } |
159 | |
160 | TEST(Coding, Varint64Truncation) { |
161 | uint64_t large_value = (1ull << 63) + 100ull; |
162 | std::string s; |
163 | PutVarint64(&s, large_value); |
164 | uint64_t result; |
165 | for (size_t len = 0; len < s.size() - 1; len++) { |
166 | ASSERT_TRUE(GetVarint64Ptr(s.data(), s.data() + len, &result) == nullptr); |
167 | } |
168 | ASSERT_TRUE(GetVarint64Ptr(s.data(), s.data() + s.size(), &result) != |
169 | nullptr); |
170 | ASSERT_EQ(large_value, result); |
171 | } |
172 | |
173 | TEST(Coding, Strings) { |
174 | std::string s; |
175 | PutLengthPrefixedSlice(&s, Slice("" )); |
176 | PutLengthPrefixedSlice(&s, Slice("foo" )); |
177 | PutLengthPrefixedSlice(&s, Slice("bar" )); |
178 | PutLengthPrefixedSlice(&s, Slice(std::string(200, 'x'))); |
179 | |
180 | Slice input(s); |
181 | Slice v; |
182 | ASSERT_TRUE(GetLengthPrefixedSlice(&input, &v)); |
183 | ASSERT_EQ("" , v.ToString()); |
184 | ASSERT_TRUE(GetLengthPrefixedSlice(&input, &v)); |
185 | ASSERT_EQ("foo" , v.ToString()); |
186 | ASSERT_TRUE(GetLengthPrefixedSlice(&input, &v)); |
187 | ASSERT_EQ("bar" , v.ToString()); |
188 | ASSERT_TRUE(GetLengthPrefixedSlice(&input, &v)); |
189 | ASSERT_EQ(std::string(200, 'x'), v.ToString()); |
190 | ASSERT_EQ("" , input.ToString()); |
191 | } |
192 | |
193 | } // namespace leveldb |
194 | |