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 "util/testharness.h"
8
9 namespace leveldb {
10
11 class Coding { };
12
TEST(Coding,Fixed32)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
TEST(Coding,Fixed64)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
TEST(Coding,EncodingOutput)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
TEST(Coding,Varint32)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 != NULL);
92 ASSERT_EQ(expected, actual);
93 ASSERT_EQ(VarintLength(actual), p - start);
94 }
95 ASSERT_EQ(p, s.data() + s.size());
96 }
97
TEST(Coding,Varint64)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 != NULL);
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 TEST(Coding, Varint32Overflow) {
135 uint32_t result;
136 std::string input("\x81\x82\x83\x84\x85\x11");
137 ASSERT_TRUE(GetVarint32Ptr(input.data(), input.data() + input.size(), &result)
138 == NULL);
139 }
140
TEST(Coding,Varint32Truncation)141 TEST(Coding, Varint32Truncation) {
142 uint32_t large_value = (1u << 31) + 100;
143 std::string s;
144 PutVarint32(&s, large_value);
145 uint32_t result;
146 for (size_t len = 0; len < s.size() - 1; len++) {
147 ASSERT_TRUE(GetVarint32Ptr(s.data(), s.data() + len, &result) == NULL);
148 }
149 ASSERT_TRUE(GetVarint32Ptr(s.data(), s.data() + s.size(), &result) != NULL);
150 ASSERT_EQ(large_value, result);
151 }
152
TEST(Coding,Varint64Overflow)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(), &result)
157 == NULL);
158 }
159
TEST(Coding,Varint64Truncation)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) == NULL);
167 }
168 ASSERT_TRUE(GetVarint64Ptr(s.data(), s.data() + s.size(), &result) != NULL);
169 ASSERT_EQ(large_value, result);
170 }
171
TEST(Coding,Strings)172 TEST(Coding, Strings) {
173 std::string s;
174 PutLengthPrefixedSlice(&s, Slice(""));
175 PutLengthPrefixedSlice(&s, Slice("foo"));
176 PutLengthPrefixedSlice(&s, Slice("bar"));
177 PutLengthPrefixedSlice(&s, Slice(std::string(200, 'x')));
178
179 Slice input(s);
180 Slice v;
181 ASSERT_TRUE(GetLengthPrefixedSlice(&input, &v));
182 ASSERT_EQ("", v.ToString());
183 ASSERT_TRUE(GetLengthPrefixedSlice(&input, &v));
184 ASSERT_EQ("foo", v.ToString());
185 ASSERT_TRUE(GetLengthPrefixedSlice(&input, &v));
186 ASSERT_EQ("bar", v.ToString());
187 ASSERT_TRUE(GetLengthPrefixedSlice(&input, &v));
188 ASSERT_EQ(std::string(200, 'x'), v.ToString());
189 ASSERT_EQ("", input.ToString());
190 }
191
192 } // namespace leveldb
193
main(int argc,char ** argv)194 int main(int argc, char** argv) {
195 return leveldb::test::RunAllTests();
196 }
197