folly/test/GroupVarintTest.cpp

   1 /*
   2  * Copyright 2012 Facebook, Inc.
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *   http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 #include <stdarg.h>
  18 #include "folly/GroupVarint.h"
  19
  20 #include <gtest/gtest.h>
  21
  22 using namespace folly;
  23
  24 namespace {
  25
  26 class StringAppender {
  27  public:
  28   /* implicit */ StringAppender(std::string& s) : s_(s) { }
  29   void operator()(StringPiece sp) {
  30     s_.append(sp.data(), sp.size());
  31   }
  32  private:
  33   std::string& s_;
  34 };
  35
  36 typedef GroupVarintEncoder<uint32_t, StringAppender> GroupVarint32Encoder;
  37 typedef GroupVarintEncoder<uint64_t, StringAppender> GroupVarint64Encoder;
  38 typedef GroupVarintDecoder<uint32_t> GroupVarint32Decoder;
  39 typedef GroupVarintDecoder<uint32_t> GroupVarint64Decoder;
  40
  41 // Expected bytes follow, terminate with -1
  42 void testGroupVarint32(uint32_t a, uint32_t b, uint32_t c, uint32_t d, ...) {
  43   va_list ap;
  44   va_start(ap, d);
  45   std::vector<char> expectedBytes;
  46   int byte;
  47   while ((byte = va_arg(ap, int)) != -1) {
  48     expectedBytes.push_back(byte);
  49   }
  50   va_end(ap);
  51
  52   size_t size = GroupVarint32::size(a, b, c, d);
  53   EXPECT_EQ(expectedBytes.size(), size);
  54
  55   std::vector<char> foundBytes;
  56   foundBytes.resize(size + 4);
  57   char* start = &(foundBytes.front());
  58   char* p = GroupVarint32::encode(start, a, b, c, d);
  59   EXPECT_EQ((void*)(start + size), (void*)p);
  60
  61   for (size_t i = 0; i < size; i++) {
  62     EXPECT_EQ(0xff & expectedBytes[i], 0xff & foundBytes[i]);
  63   }
  64
  65   // Test decoding
  66   EXPECT_EQ(size, GroupVarint32::encodedSize(start));
  67
  68   uint32_t fa, fb, fc, fd;
  69   const char* r = GroupVarint32::decode(start, &fa, &fb, &fc, &fd);
  70   EXPECT_EQ((void*)(start + size), (void*)r);
  71
  72   EXPECT_EQ(a, fa);
  73   EXPECT_EQ(b, fb);
  74   EXPECT_EQ(c, fc);
  75   EXPECT_EQ(d, fd);
  76 }
  77
  78 void testGroupVarint64(uint64_t a, uint64_t b, uint64_t c, uint64_t d,
  79                        uint64_t e, ...) {
  80   va_list ap;
  81   va_start(ap, e);
  82   std::vector<char> expectedBytes;
  83   int byte;
  84   while ((byte = va_arg(ap, int)) != -1) {
  85     expectedBytes.push_back(byte);
  86   }
  87   va_end(ap);
  88
  89   size_t size = GroupVarint64::size(a, b, c, d, e);
  90   EXPECT_EQ(expectedBytes.size(), size);
  91
  92   std::vector<char> foundBytes;
  93   foundBytes.resize(size + 8);
  94   char* start = &(foundBytes.front());
  95   char* p = GroupVarint64::encode(start, a, b, c, d, e);
  96   EXPECT_EQ((void*)(start + size), (void*)p);
  97
  98   for (size_t i = 0; i < size; i++) {
  99     EXPECT_EQ(0xff & expectedBytes[i], 0xff & foundBytes[i]);
 100   }
 101
 102   // Test decoding
 103   EXPECT_EQ(size, GroupVarint64::encodedSize(start));
 104
 105   uint64_t fa, fb, fc, fd, fe;
 106   const char* r = GroupVarint64::decode(start, &fa, &fb, &fc, &fd, &fe);
 107   EXPECT_EQ((void*)(start + size), (void*)r);
 108
 109   EXPECT_EQ(a, fa);
 110   EXPECT_EQ(b, fb);
 111   EXPECT_EQ(c, fc);
 112   EXPECT_EQ(d, fd);
 113   EXPECT_EQ(e, fe);
 114 }
 115
 116 }  // namespace
 117
 118 TEST(GroupVarint, GroupVarint32) {
 119   EXPECT_EQ(0, GroupVarint32::maxSize(0));
 120   EXPECT_EQ(5, GroupVarint32::maxSize(1));
 121   EXPECT_EQ(9, GroupVarint32::maxSize(2));
 122   EXPECT_EQ(13, GroupVarint32::maxSize(3));
 123   EXPECT_EQ(17, GroupVarint32::maxSize(4));
 124   EXPECT_EQ(22, GroupVarint32::maxSize(5));
 125   EXPECT_EQ(26, GroupVarint32::maxSize(6));
 126   testGroupVarint32(0, 0, 0, 0,
 127                     0, 0, 0, 0, 0, -1);
 128   testGroupVarint32(1, 2, 3, 4,
 129                     0, 1, 2, 3, 4, -1);
 130   testGroupVarint32(1 << 8, (2 << 16) + 3, (4 << 24) + (5 << 8) + 6, 7,
 131                     0x39, 0, 1, 3, 0, 2, 6, 5, 0, 4, 7, -1);
 132 }
 133
 134 TEST(GroupVarint, GroupVarint64) {
 135   EXPECT_EQ(0, GroupVarint64::maxSize(0));
 136   EXPECT_EQ(10, GroupVarint64::maxSize(1));
 137   EXPECT_EQ(18, GroupVarint64::maxSize(2));
 138   EXPECT_EQ(26, GroupVarint64::maxSize(3));
 139   EXPECT_EQ(34, GroupVarint64::maxSize(4));
 140   EXPECT_EQ(42, GroupVarint64::maxSize(5));
 141   EXPECT_EQ(52, GroupVarint64::maxSize(6));
 142   testGroupVarint64(0, 0, 0, 0, 0,
 143                     0, 0, 0, 0, 0, 0, 0, -1);
 144   testGroupVarint64(1, 2, 3, 4, 5,
 145                     0, 0, 1, 2, 3, 4, 5, -1);
 146   testGroupVarint64(1 << 8, (2 << 16) + 3, (4 << 24) + (5 << 8) + 6,
 147                     (7ULL << 32) + (8 << 16),
 148                     (9ULL << 56) + (10ULL << 40) + 11,
 149                     0xd1, 0x78,
 150                     0, 1,
 151                     3, 0, 2,
 152                     6, 5, 0, 4,
 153                     0, 0, 8, 0, 7,
 154                     11, 0, 0, 0, 0, 10, 0, 9,
 155                     -1);
 156 }
 157
 158 TEST(GroupVarint, GroupVarintEncoder) {
 159   std::string s;
 160   {
 161     GroupVarint32Encoder gv(s);
 162     gv.add(0);
 163     gv.finish();
 164   }
 165   EXPECT_EQ(2, s.size());
 166   EXPECT_EQ(std::string("\x00\x00", 2), s);
 167   s.clear();
 168   {
 169     GroupVarint32Encoder gv(s);
 170     gv.add(1);
 171     gv.add(2);
 172     gv.add(3);
 173     gv.add(4);
 174     gv.finish();
 175   }
 176   EXPECT_EQ(5, s.size());
 177   EXPECT_EQ(std::string("\x00\x01\x02\x03\x04", 5), s);
 178 }
 179
 180
 181 TEST(GroupVarint, GroupVarintDecoder) {
 182   // Make sure we don't read out of bounds
 183   std::string padding(17, 'X');
 184
 185   {
 186     std::string s("\x00\x00", 2);
 187     s += padding;
 188     StringPiece p(s.data(), 2);
 189
 190     GroupVarint32Decoder gv(p);
 191     uint32_t v;
 192     EXPECT_TRUE(gv.next(&v));
 193     EXPECT_EQ(0, v);
 194     EXPECT_FALSE(gv.next(&v));
 195     EXPECT_TRUE(gv.rest().empty());
 196   }
 197
 198   {
 199     std::string s("\x00\x01\x02\x03\x04\x01\x02\x03\x04", 9);
 200     s += padding;
 201     StringPiece p(s.data(), 9);
 202
 203     GroupVarint32Decoder gv(p);
 204     uint32_t v;
 205     EXPECT_TRUE(gv.next(&v));
 206     EXPECT_EQ(1, v);
 207     EXPECT_TRUE(gv.next(&v));
 208     EXPECT_EQ(2, v);
 209     EXPECT_TRUE(gv.next(&v));
 210     EXPECT_EQ(3, v);
 211     EXPECT_TRUE(gv.next(&v));
 212     EXPECT_EQ(4, v);
 213     EXPECT_TRUE(gv.next(&v));
 214     EXPECT_EQ(0x0302, v);
 215     EXPECT_TRUE(gv.next(&v));
 216     EXPECT_EQ(4, v);
 217     EXPECT_FALSE(gv.next(&v));
 218     EXPECT_TRUE(gv.rest().empty());
 219   }
 220
 221   {
 222     // Limit max count when reading a full block
 223     std::string s("\x00\x01\x02\x03\x04\x01\x02\x03\x04", 9);
 224     s += padding;
 225     StringPiece p(s.data(), 9);
 226
 227     GroupVarint32Decoder gv(p, 3);
 228     uint32_t v;
 229     EXPECT_TRUE(gv.next(&v));
 230     EXPECT_EQ(1, v);
 231     EXPECT_TRUE(gv.next(&v));
 232     EXPECT_EQ(2, v);
 233     EXPECT_TRUE(gv.next(&v));
 234     EXPECT_EQ(3, v);
 235     EXPECT_FALSE(gv.next(&v));
 236     EXPECT_EQ(std::string("\x04\x01\x02\x03\x04", 5), gv.rest().toString());
 237   }
 238
 239   {
 240     // Limit max count when reading a partial block
 241     std::string s("\x00\x01\x02\x03\x04\x01\x02\x03\x04", 9);
 242     s += padding;
 243     StringPiece p(s.data(), 9);
 244
 245     GroupVarint32Decoder gv(p, 5);
 246     uint32_t v;
 247     EXPECT_TRUE(gv.next(&v));
 248     EXPECT_EQ(1, v);
 249     EXPECT_TRUE(gv.next(&v));
 250     EXPECT_EQ(2, v);
 251     EXPECT_TRUE(gv.next(&v));
 252     EXPECT_EQ(3, v);
 253     EXPECT_TRUE(gv.next(&v));
 254     EXPECT_EQ(4, v);
 255     EXPECT_TRUE(gv.next(&v));
 256     EXPECT_EQ(0x0302, v);
 257     EXPECT_FALSE(gv.next(&v));
 258     EXPECT_EQ(std::string("\x04", 1), gv.rest().toString());
 259   }
 260 }
 261