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