folly/experimental/test/BitsTest.cpp

   1 /*
   2  * Copyright 2014 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 }
 254
 255 static_assert((-4) >> 1 == -2, "OH");
 256 template <bool aligned>
 257 void testConcatenation() {
 258   // concatenate fields of length 1, 2, 3, ... 64, all unsigned, storing 2/3s
 259   // the maximum value in each.
 260   const size_t bitLimit = 64;
 261   const size_t bitsPerPass = (1 + bitLimit) * bitLimit / 2;
 262   const size_t totalBits = bitsPerPass * 3;
 263   uint8_t buf[(totalBits + 7) / 8];
 264 #define EACH_UNSIGNED_SIZE(MACRO, ARG) \
 265   MACRO(8, uint8_t, ARG);              \
 266   MACRO(16, uint16_t, ARG);            \
 267   MACRO(32, uint32_t, ARG);            \
 268   MACRO(64, uint64_t, ARG);
 269 #define EACH_SIGNED_SIZE(MACRO, ARG) \
 270   MACRO(7, int8_t, ARG);             \
 271   MACRO(15, int16_t, ARG);           \
 272   MACRO(31, int32_t, ARG);           \
 273   MACRO(63, int64_t, ARG);
 274   {
 275     size_t w = 0, s;
 276 #define WRITE_TEST(N, T, NEG)                                                 \
 277   for (; s <= N; ++s, w += s) {                                               \
 278     testSet<aligned>(buf, w, s, testValue<T, NEG>(s));                        \
 279     EXPECT_EQ((testValue<T, NEG>(s)), (testGet<aligned, T>(buf, w, s))) << s; \
 280   }
 281     s = 0;
 282     EACH_UNSIGNED_SIZE(WRITE_TEST, false)
 283     s = 0;
 284     EACH_SIGNED_SIZE(WRITE_TEST, false)
 285     s = 0;
 286     EACH_SIGNED_SIZE(WRITE_TEST, true)
 287 #undef WRITE_TEST
 288   }
 289   {
 290     size_t r = 0, s;
 291 #define READ_TEST(N, T, NEG)  \
 292   for (; s <= N; ++s, r += s) \
 293     EXPECT_EQ((testValue<T, NEG>(s)), (testGet<aligned, T>(buf, r, s))) << s;
 294     s = 0;
 295     EACH_UNSIGNED_SIZE(READ_TEST, false)
 296     s = 0;
 297     EACH_SIGNED_SIZE(READ_TEST, false)
 298     s = 0;
 299     EACH_SIGNED_SIZE(READ_TEST, true)
 300 #undef READ_TEST
 301   }
 302 #undef EACH_UNSIGNED_SIZE
 303 }
 304
 305 TEST(Bits, ConcatenationUnalignedUnsigned) { testConcatenation<false>(); }
 306
 307 TEST(Bits, ConcatenationAligned) {
 308   testConcatenation<true>();
 309 }
 310
 311 int main(int argc, char *argv[]) {
 312   testing::InitGoogleTest(&argc, argv);
 313   gflags::ParseCommandLineFlags(&argc, &argv, true);
 314   return RUN_ALL_TESTS();
 315 }
 316