src/leveldb/util/coding_test.cc

   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
  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 != NULL);
  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 (int 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 (int 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
 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
 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 (int 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
 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
 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 (int 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
 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
 194 int main(int argc, char** argv) {
 195   return leveldb::test::RunAllTests();
 196 }