folly/test/GroupVarintTest.cpp

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