folly/test/GroupVarintTest.cpp

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