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