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