folly/experimental/test/BitsTest.cpp

   1 /*
   2  * Copyright 2013 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 runMultiBitTest64() {
 148   auto load = detail::BitsTraits<T>::load;
 149   T buf[] = {0x123456789abcdef0, 0x13579bdf2468ace0};
 150
 151   EXPECT_EQ(0x123456789abcdef0, load(Bits<T>::get(buf, 0, 64)));
 152   EXPECT_EQ(0xf0, load(Bits<T>::get(buf, 0, 8)));
 153   EXPECT_EQ(0x89abcdef, load(Bits<T>::get(buf, 4, 32)));
 154   EXPECT_EQ(0x189abcdef, load(Bits<T>::get(buf, 4, 33)));
 155
 156   Bits<T>::set(buf, 4, 31, 0x55555555);
 157   EXPECT_EQ(0xd5555555, load(Bits<T>::get(buf, 4, 32)));
 158   EXPECT_EQ(0x1d5555555, load(Bits<T>::get(buf, 4, 33)));
 159   EXPECT_EQ(0xd55555550, load(Bits<T>::get(buf, 0, 36)));
 160
 161   Bits<T>::set(buf, 0, 64, 0x23456789abcdef01);
 162   EXPECT_EQ(0x23456789abcdef01, load(Bits<T>::get(buf, 0, 64)));
 163 }
 164
 165 TEST(Bits, MultiBit64) {
 166   runMultiBitTest64<uint64_t>();
 167 }
 168
 169 TEST(Bits, MultiBitUnaligned64) {
 170   runMultiBitTest64<Unaligned<uint64_t>>();
 171 }
 172
 173 int main(int argc, char *argv[]) {
 174   testing::InitGoogleTest(&argc, argv);
 175   google::ParseCommandLineFlags(&argc, &argv, true);
 176   return RUN_ALL_TESTS();
 177 }
 178