folly/test/GroupVarintTest.cpp

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