folly/experimental/test/BitsTest.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 <cmath>
  18
  19 #include <folly/experimental/Bits.h>
  20
  21 #include <glog/logging.h>
  22
  23 #include <folly/portability/GTest.h>
  24
  25 using namespace folly;
  26
  27 template <class T>
  28 void runSimpleTest8() {
  29   auto load = detail::BitsTraits<T>::load;
  30
  31   EXPECT_EQ(0, Bits<T>::blockCount(0));
  32   EXPECT_EQ(1, Bits<T>::blockCount(1));
  33   EXPECT_EQ(1, Bits<T>::blockCount(8));
  34   EXPECT_EQ(2, Bits<T>::blockCount(9));
  35   EXPECT_EQ(256, Bits<T>::blockCount(2048));
  36   EXPECT_EQ(257, Bits<T>::blockCount(2049));
  37
  38   EXPECT_EQ(4, Bits<T>::blockIndex(39));
  39   EXPECT_EQ(7, Bits<T>::bitOffset(39));
  40   EXPECT_EQ(5, Bits<T>::blockIndex(40));
  41   EXPECT_EQ(0, Bits<T>::bitOffset(40));
  42
  43   T buf[256];
  44   std::fill(buf, buf + 256, T(0));
  45
  46   Bits<T>::set(buf, 36);
  47   Bits<T>::set(buf, 39);
  48   EXPECT_EQ((1 << 7) | (1 << 4), load(buf[4]));
  49   EXPECT_EQ(0, load(buf[5]));
  50   Bits<T>::clear(buf, 39);
  51   EXPECT_EQ(1 << 4, load(buf[4]));
  52   EXPECT_EQ(0, load(buf[5]));
  53   Bits<T>::set(buf, 40);
  54   EXPECT_EQ(1 << 4, load(buf[4]));
  55   EXPECT_EQ(1, load(buf[5]));
  56
  57   EXPECT_EQ(2, Bits<T>::count(buf, buf + 256));
  58 }
  59
  60 TEST(Bits, Simple8) {
  61   runSimpleTest8<uint8_t>();
  62 }
  63
  64 TEST(Bits, SimpleUnaligned8) {
  65   runSimpleTest8<Unaligned<uint8_t>>();
  66 }
  67
  68 template <class T>
  69 void runSimpleTest64() {
  70   auto load = detail::BitsTraits<T>::load;
  71
  72   EXPECT_EQ(0, Bits<T>::blockCount(0));
  73   EXPECT_EQ(1, Bits<T>::blockCount(1));
  74   EXPECT_EQ(1, Bits<T>::blockCount(8));
  75   EXPECT_EQ(1, Bits<T>::blockCount(9));
  76   EXPECT_EQ(1, Bits<T>::blockCount(64));
  77   EXPECT_EQ(2, Bits<T>::blockCount(65));
  78   EXPECT_EQ(32, Bits<T>::blockCount(2048));
  79   EXPECT_EQ(33, Bits<T>::blockCount(2049));
  80
  81   EXPECT_EQ(0, Bits<T>::blockIndex(39));
  82   EXPECT_EQ(39, Bits<T>::bitOffset(39));
  83   EXPECT_EQ(4, Bits<T>::blockIndex(319));
  84   EXPECT_EQ(63, Bits<T>::bitOffset(319));
  85   EXPECT_EQ(5, Bits<T>::blockIndex(320));
  86   EXPECT_EQ(0, Bits<T>::bitOffset(320));
  87
  88   T buf[256];
  89   std::fill(buf, buf + 256, T(0));
  90
  91   Bits<T>::set(buf, 300);
  92   Bits<T>::set(buf, 319);
  93   EXPECT_EQ((uint64_t(1) << 44) | (uint64_t(1) << 63), load(buf[4]));
  94   EXPECT_EQ(0, load(buf[5]));
  95   Bits<T>::clear(buf, 319);
  96   EXPECT_EQ(uint64_t(1) << 44, load(buf[4]));
  97   EXPECT_EQ(0, load(buf[5]));
  98   Bits<T>::set(buf, 320);
  99   EXPECT_EQ(uint64_t(1) << 44, load(buf[4]));
 100   EXPECT_EQ(1, load(buf[5]));
 101
 102   EXPECT_EQ(2, Bits<T>::count(buf, buf + 256));
 103 }
 104
 105 TEST(Bits, Simple64) {
 106   runSimpleTest64<uint64_t>();
 107 }
 108
 109 TEST(Bits, SimpleUnaligned64) {
 110   runSimpleTest64<Unaligned<uint64_t>>();
 111 }
 112
 113 template <class T>
 114 void runMultiBitTest8() {
 115   auto load = detail::BitsTraits<T>::load;
 116   T buf[] = {0x12, 0x34, 0x56, 0x78};
 117
 118   EXPECT_EQ(0x02, load(Bits<T>::get(buf, 0, 4)));
 119   EXPECT_EQ(0x1a, load(Bits<T>::get(buf, 9, 5)));
 120   EXPECT_EQ(0xb1, load(Bits<T>::get(buf, 13, 8)));
 121
 122   Bits<T>::set(buf, 0, 4, 0x0b);
 123   EXPECT_EQ(0x1b, load(buf[0]));
 124   EXPECT_EQ(0x34, load(buf[1]));
 125   EXPECT_EQ(0x56, load(buf[2]));
 126   EXPECT_EQ(0x78, load(buf[3]));
 127
 128   Bits<T>::set(buf, 9, 5, 0x0e);
 129   EXPECT_EQ(0x1b, load(buf[0]));
 130   EXPECT_EQ(0x1c, load(buf[1]));
 131   EXPECT_EQ(0x56, load(buf[2]));
 132   EXPECT_EQ(0x78, load(buf[3]));
 133
 134   Bits<T>::set(buf, 13, 8, 0xaa);
 135   EXPECT_EQ(0x1b, load(buf[0]));
 136   EXPECT_EQ(0x5c, load(buf[1]));
 137   EXPECT_EQ(0x55, load(buf[2]));
 138   EXPECT_EQ(0x78, load(buf[3]));
 139 }
 140
 141 TEST(Bits, MultiBit8) {
 142   runMultiBitTest8<uint8_t>();
 143 }
 144
 145 TEST(Bits, MultiBitUnaligned8) {
 146   runMultiBitTest8<Unaligned<uint8_t>>();
 147 }
 148
 149 template <class T>
 150 void runSignedMultiBitTest8() {
 151   auto load = detail::BitsTraits<T>::load;
 152   T buf[] = {0x12, 0x34, 0x56, 0x78};
 153
 154   EXPECT_EQ(0x02, load(Bits<T>::get(buf, 0, 4)));
 155   EXPECT_EQ(0x1a-32, load(Bits<T>::get(buf, 9, 5)));
 156   EXPECT_EQ(0xb1-256, load(Bits<T>::get(buf, 13, 8)));
 157
 158   Bits<T>::set(buf, 0, 4, 0x0b - 0x10);
 159   EXPECT_EQ(0x1b, load(buf[0]));
 160   EXPECT_EQ(0x34, load(buf[1]));
 161   EXPECT_EQ(0x56, load(buf[2]));
 162   EXPECT_EQ(0x78, load(buf[3]));
 163
 164   Bits<T>::set(buf, 9, 5, 0x0e);
 165   EXPECT_EQ(0x1b, load(buf[0]));
 166   EXPECT_EQ(0x1c, load(buf[1]));
 167   EXPECT_EQ(0x56, load(buf[2]));
 168   EXPECT_EQ(0x78, load(buf[3]));
 169
 170   Bits<T>::set(buf, 13, 8, 0xaa - 0x100);
 171   EXPECT_EQ(0x1b, load(buf[0]));
 172   EXPECT_EQ(0x5c, load(buf[1]));
 173   EXPECT_EQ(0x55, load(buf[2]));
 174   EXPECT_EQ(0x78, load(buf[3]));
 175 }
 176
 177
 178 TEST(Bits, SignedMultiBit8) {
 179   runSignedMultiBitTest8<int8_t>();
 180 }
 181
 182 template <class T, class R = T>
 183 void runMultiBitTest64() {
 184   auto load = detail::BitsTraits<T>::load;
 185   T buf[] = {0x123456789abcdef0, 0x13579bdf2468ace0};
 186
 187   EXPECT_EQ(0x123456789abcdef0, load(Bits<T>::get(buf, 0, 64)));
 188   EXPECT_EQ(0xf0, load(Bits<T>::get(buf, 0, 8)));
 189   EXPECT_EQ(0x89abcdef, load(Bits<T>::get(buf, 4, 32)));
 190   EXPECT_EQ(0x189abcdef, load(Bits<T>::get(buf, 4, 33)));
 191
 192   Bits<T>::set(buf, 4, 31, 0x55555555);
 193   EXPECT_EQ(0xd5555555, load(Bits<T>::get(buf, 4, 32)));
 194   EXPECT_EQ(0x1d5555555, load(Bits<T>::get(buf, 4, 33)));
 195   EXPECT_EQ(0xd55555550, load(Bits<T>::get(buf, 0, 36)));
 196
 197   Bits<T>::set(buf, 0, 64, 0x23456789abcdef01);
 198   EXPECT_EQ(0x23456789abcdef01, load(Bits<T>::get(buf, 0, 64)));
 199 }
 200
 201 TEST(Bits, MultiBit64) {
 202   runMultiBitTest64<uint64_t>();
 203 }
 204
 205 TEST(Bits, MultiBitSigned64) {
 206   //runMultiBitTest64<int64_t>();
 207 }
 208
 209 TEST(Bits, MultiBitUnaligned64) {
 210   runMultiBitTest64<Unaligned<uint64_t>, uint64_t>();
 211 }
 212
 213 namespace {
 214 template <bool aligned, class T>
 215 typename std::enable_if<!aligned>::type testSet(uint8_t *buf,
 216                                                 size_t start,
 217                                                 size_t bits,
 218                                                 T value) {
 219   Bits<Unaligned<T>>::set(
 220       reinterpret_cast<Unaligned<T> *>(buf), start, bits, value);
 221 }
 222
 223 template <bool aligned, class T>
 224 typename std::enable_if<aligned>::type testSet(uint8_t *buf,
 225                                                size_t start,
 226                                                size_t bits,
 227                                                T value) {
 228   Bits<T>::set(reinterpret_cast<T *>(buf), start, bits, value);
 229 }
 230
 231 template <bool aligned, class T>
 232 typename std::enable_if<!aligned, T>::type testGet(uint8_t *buf,
 233                                                    size_t start,
 234                                                    size_t bits) {
 235   return Bits<Unaligned<T>>::get(
 236       reinterpret_cast<Unaligned<T> *>(buf), start, bits);
 237 }
 238
 239 template <bool aligned, class T>
 240 typename std::enable_if<aligned, T>::type testGet(uint8_t *buf,
 241                                                   size_t start,
 242                                                   size_t bits) {
 243   return Bits<T>::get(reinterpret_cast<T *>(buf), start, bits);
 244 }
 245
 246 template <class T, bool negate = false>
 247 T testValue(int bits) {
 248   if (std::is_signed<T>::value) {
 249     --bits;
 250   }
 251   auto value = std::pow(2, bits) * (negate ? -2.0 : 2.0) / 3.0;
 252   CHECK_GE(value, std::numeric_limits<T>::min());
 253   CHECK_LE(value, std::numeric_limits<T>::max());
 254   return static_cast<T>(value);
 255 }
 256 } // anonymous namespace
 257
 258 TEST(Bits, Boundaries) {
 259   uint8_t buf[20];
 260   for (size_t offset = 0; offset <= 64; ++offset) {
 261     for (size_t size = 0; size <= 32; ++size) {
 262       int32_t value = testValue<int32_t>(size);
 263       testSet<true>(buf, offset, size, value);
 264       EXPECT_EQ(value, (testGet<true, int32_t>(buf, offset, size)));
 265     }
 266   }
 267 }
 268
 269 template <size_t N>
 270 void accSize(size_t& w) {
 271   for (size_t s = 0; s <= N; ++s) {
 272     w += s;
 273   }
 274 }
 275
 276 template <size_t N, typename T, bool NEG, bool aligned>
 277 void testSetLoop(size_t& w, size_t bufSize, uint8_t* buf) {
 278   for (size_t s = 0; s <= N; ++s) {
 279     CHECK_LE(s + w, 8 * bufSize) << s << ' ' << w << ' ' << bufSize;
 280     testSet<aligned>(buf, w, s, testValue<T, NEG>(s));
 281     EXPECT_EQ((testValue<T, NEG>(s)), (testGet<aligned, T>(buf, w, s))) << s;
 282     w += s;
 283   }
 284 }
 285
 286 template <size_t N, typename T, bool NEG, bool aligned>
 287 void testGetLoop(size_t& r, size_t bufSize, uint8_t* buf) {
 288   for (size_t s = 0; s <= N; ++s) {
 289     CHECK_LE(s + r, 8 * bufSize);
 290     EXPECT_EQ((testValue<T, NEG>(s)), (testGet<aligned, T>(buf, r, s))) << s;
 291     r += s;
 292   }
 293 }
 294
 295 template <bool aligned>
 296 void testConcatenation() {
 297   // concatenate fields of length 1, 2, 3, ... 64, all unsigned, storing 2/3s
 298   // the maximum value in each.
 299
 300   // calculate how much buffer size we need
 301   size_t bufSize = 0;
 302   {
 303     size_t w = 0;
 304     // Unsigned
 305     accSize<8>(w);
 306     accSize<16>(w);
 307     accSize<32>(w);
 308     accSize<64>(w);
 309
 310     // Signed NEG=false
 311     accSize<7>(w);
 312     accSize<15>(w);
 313     accSize<31>(w);
 314     accSize<63>(w);
 315
 316     // Signed NEG=true
 317     accSize<7>(w);
 318     accSize<15>(w);
 319     accSize<31>(w);
 320     accSize<63>(w);
 321
 322     bufSize = w;
 323   }
 324   // bits->bytes, rounding up
 325   bufSize = (bufSize + 7) / 8;
 326   // round up to next multiple of 8
 327   bufSize = (bufSize + 7) / 8 * 8;
 328   std::vector<uint8_t> buffer(bufSize);
 329   uint8_t *buf = buffer.data();
 330   {
 331     size_t w = 0;
 332     // Unsigned
 333     testSetLoop<8, uint8_t, false, aligned>(w, bufSize, buf);
 334     testSetLoop<16, uint16_t, false, aligned>(w, bufSize, buf);
 335     testSetLoop<32, uint32_t, false, aligned>(w, bufSize, buf);
 336     testSetLoop<64, uint64_t, false, aligned>(w, bufSize, buf);
 337
 338     // Signed NEG=false
 339     testSetLoop<7, int8_t, false, aligned>(w, bufSize, buf);
 340     testSetLoop<15, int16_t, false, aligned>(w, bufSize, buf);
 341     testSetLoop<31, int32_t, false, aligned>(w, bufSize, buf);
 342     testSetLoop<63, int64_t, false, aligned>(w, bufSize, buf);
 343
 344     // Signed NEG=true
 345     testSetLoop<7, int8_t, true, aligned>(w, bufSize, buf);
 346     testSetLoop<15, int16_t, true, aligned>(w, bufSize, buf);
 347     testSetLoop<31, int32_t, true, aligned>(w, bufSize, buf);
 348     testSetLoop<63, int64_t, true, aligned>(w, bufSize, buf);
 349   }
 350
 351   {
 352     size_t r = 0;
 353     // Unsigned
 354     testGetLoop<8, uint8_t, false, aligned>(r, bufSize, buf);
 355     testGetLoop<16, uint16_t, false, aligned>(r, bufSize, buf);
 356     testGetLoop<32, uint32_t, false, aligned>(r, bufSize, buf);
 357     testGetLoop<64, uint64_t, false, aligned>(r, bufSize, buf);
 358
 359     // Signed NEG=false
 360     testGetLoop<7, int8_t, false, aligned>(r, bufSize, buf);
 361     testGetLoop<15, int16_t, false, aligned>(r, bufSize, buf);
 362     testGetLoop<31, int32_t, false, aligned>(r, bufSize, buf);
 363     testGetLoop<63, int64_t, false, aligned>(r, bufSize, buf);
 364
 365     // Signed NEG=true
 366     testGetLoop<7, int8_t, true, aligned>(r, bufSize, buf);
 367     testGetLoop<15, int16_t, true, aligned>(r, bufSize, buf);
 368     testGetLoop<31, int32_t, true, aligned>(r, bufSize, buf);
 369     testGetLoop<63, int64_t, true, aligned>(r, bufSize, buf);
 370   }
 371 }
 372
 373 TEST(Bits, ConcatenationUnalignedUnsigned) { testConcatenation<false>(); }
 374
 375 TEST(Bits, ConcatenationAligned) { testConcatenation<true>(); }
 376
 377 int main(int argc, char *argv[]) {
 378   testing::InitGoogleTest(&argc, argv);
 379   gflags::ParseCommandLineFlags(&argc, &argv, true);
 380   return RUN_ALL_TESTS();
 381 }