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