Inside Bitcoin

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