1 | /* |
2 | * Copyright 2012-present 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 | TEST(Bits, SignedMultiBit8) { |
178 | runSignedMultiBitTest8<int8_t>(); |
179 | } |
180 | |
181 | template <class T, class R = T> |
182 | void runMultiBitTest64() { |
183 | auto load = detail::BitsTraits<T>::load; |
184 | T buf[] = {0x123456789abcdef0, 0x13579bdf2468ace0}; |
185 | |
186 | EXPECT_EQ(0x123456789abcdef0, load(Bits<T>::get(buf, 0, 64))); |
187 | EXPECT_EQ(0xf0, load(Bits<T>::get(buf, 0, 8))); |
188 | EXPECT_EQ(0x89abcdef, load(Bits<T>::get(buf, 4, 32))); |
189 | EXPECT_EQ(0x189abcdef, load(Bits<T>::get(buf, 4, 33))); |
190 | |
191 | Bits<T>::set(buf, 4, 31, 0x55555555); |
192 | EXPECT_EQ(0xd5555555, load(Bits<T>::get(buf, 4, 32))); |
193 | EXPECT_EQ(0x1d5555555, load(Bits<T>::get(buf, 4, 33))); |
194 | EXPECT_EQ(0xd55555550, load(Bits<T>::get(buf, 0, 36))); |
195 | |
196 | Bits<T>::set(buf, 0, 64, 0x23456789abcdef01); |
197 | EXPECT_EQ(0x23456789abcdef01, load(Bits<T>::get(buf, 0, 64))); |
198 | } |
199 | |
200 | TEST(Bits, MultiBit64) { |
201 | runMultiBitTest64<uint64_t>(); |
202 | } |
203 | |
204 | TEST(Bits, MultiBitSigned64) { |
205 | // runMultiBitTest64<int64_t>(); |
206 | } |
207 | |
208 | TEST(Bits, MultiBitUnaligned64) { |
209 | runMultiBitTest64<Unaligned<uint64_t>, uint64_t>(); |
210 | } |
211 | |
212 | namespace { |
213 | template <bool aligned, class T> |
214 | typename std::enable_if<!aligned>::type |
215 | testSet(uint8_t* buf, size_t start, size_t bits, 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 |
222 | testSet(uint8_t* buf, size_t start, size_t bits, T value) { |
223 | Bits<T>::set(reinterpret_cast<T*>(buf), start, bits, value); |
224 | } |
225 | |
226 | template <bool aligned, class T> |
227 | typename std::enable_if<!aligned, T>::type |
228 | testGet(uint8_t* buf, size_t start, size_t bits) { |
229 | return Bits<Unaligned<T>>::get( |
230 | reinterpret_cast<Unaligned<T>*>(buf), start, bits); |
231 | } |
232 | |
233 | template <bool aligned, class T> |
234 | typename std::enable_if<aligned, T>::type |
235 | testGet(uint8_t* buf, size_t start, size_t bits) { |
236 | return Bits<T>::get(reinterpret_cast<T*>(buf), start, bits); |
237 | } |
238 | |
239 | template <class T, bool negate = false> |
240 | T testValue(int bits) { |
241 | if (std::is_signed<T>::value) { |
242 | --bits; |
243 | } |
244 | auto value = std::pow(2, bits) * (negate ? -2.0 : 2.0) / 3.0; |
245 | CHECK_GE(value, std::numeric_limits<T>::min()); |
246 | CHECK_LE(value, std::numeric_limits<T>::max()); |
247 | return static_cast<T>(value); |
248 | } |
249 | } // namespace |
250 | |
251 | TEST(Bits, Boundaries) { |
252 | uint8_t buf[20]; |
253 | for (size_t offset = 0; offset <= 64; ++offset) { |
254 | for (size_t size = 0; size <= 32; ++size) { |
255 | int32_t value = testValue<int32_t>(size); |
256 | testSet<true>(buf, offset, size, value); |
257 | EXPECT_EQ(value, (testGet<true, int32_t>(buf, offset, size))); |
258 | } |
259 | } |
260 | } |
261 | |
262 | template <size_t N> |
263 | void accSize(size_t& w) { |
264 | for (size_t s = 0; s <= N; ++s) { |
265 | w += s; |
266 | } |
267 | } |
268 | |
269 | template <size_t N, typename T, bool NEG, bool aligned> |
270 | void testSetLoop(size_t& w, size_t bufSize, uint8_t* buf) { |
271 | for (size_t s = 0; s <= N; ++s) { |
272 | CHECK_LE(s + w, 8 * bufSize) << s << ' ' << w << ' ' << bufSize; |
273 | testSet<aligned>(buf, w, s, testValue<T, NEG>(s)); |
274 | EXPECT_EQ((testValue<T, NEG>(s)), (testGet<aligned, T>(buf, w, s))) << s; |
275 | w += s; |
276 | } |
277 | } |
278 | |
279 | template <size_t N, typename T, bool NEG, bool aligned> |
280 | void testGetLoop(size_t& r, size_t bufSize, uint8_t* buf) { |
281 | for (size_t s = 0; s <= N; ++s) { |
282 | CHECK_LE(s + r, 8 * bufSize); |
283 | EXPECT_EQ((testValue<T, NEG>(s)), (testGet<aligned, T>(buf, r, s))) << s; |
284 | r += s; |
285 | } |
286 | } |
287 | |
288 | template <bool aligned> |
289 | void testConcatenation() { |
290 | // concatenate fields of length 1, 2, 3, ... 64, all unsigned, storing 2/3s |
291 | // the maximum value in each. |
292 | |
293 | // calculate how much buffer size we need |
294 | size_t bufSize = 0; |
295 | { |
296 | size_t w = 0; |
297 | // Unsigned |
298 | accSize<8>(w); |
299 | accSize<16>(w); |
300 | accSize<32>(w); |
301 | accSize<64>(w); |
302 | |
303 | // Signed NEG=false |
304 | accSize<7>(w); |
305 | accSize<15>(w); |
306 | accSize<31>(w); |
307 | accSize<63>(w); |
308 | |
309 | // Signed NEG=true |
310 | accSize<7>(w); |
311 | accSize<15>(w); |
312 | accSize<31>(w); |
313 | accSize<63>(w); |
314 | |
315 | bufSize = w; |
316 | } |
317 | // bits->bytes, rounding up |
318 | bufSize = (bufSize + 7) / 8; |
319 | // round up to next multiple of 8 |
320 | bufSize = (bufSize + 7) / 8 * 8; |
321 | std::vector<uint8_t> buffer(bufSize); |
322 | uint8_t* buf = buffer.data(); |
323 | { |
324 | size_t w = 0; |
325 | // Unsigned |
326 | testSetLoop<8, uint8_t, false, aligned>(w, bufSize, buf); |
327 | testSetLoop<16, uint16_t, false, aligned>(w, bufSize, buf); |
328 | testSetLoop<32, uint32_t, false, aligned>(w, bufSize, buf); |
329 | testSetLoop<64, uint64_t, false, aligned>(w, bufSize, buf); |
330 | |
331 | // Signed NEG=false |
332 | testSetLoop<7, int8_t, false, aligned>(w, bufSize, buf); |
333 | testSetLoop<15, int16_t, false, aligned>(w, bufSize, buf); |
334 | testSetLoop<31, int32_t, false, aligned>(w, bufSize, buf); |
335 | testSetLoop<63, int64_t, false, aligned>(w, bufSize, buf); |
336 | |
337 | // Signed NEG=true |
338 | testSetLoop<7, int8_t, true, aligned>(w, bufSize, buf); |
339 | testSetLoop<15, int16_t, true, aligned>(w, bufSize, buf); |
340 | testSetLoop<31, int32_t, true, aligned>(w, bufSize, buf); |
341 | testSetLoop<63, int64_t, true, aligned>(w, bufSize, buf); |
342 | } |
343 | |
344 | { |
345 | size_t r = 0; |
346 | // Unsigned |
347 | testGetLoop<8, uint8_t, false, aligned>(r, bufSize, buf); |
348 | testGetLoop<16, uint16_t, false, aligned>(r, bufSize, buf); |
349 | testGetLoop<32, uint32_t, false, aligned>(r, bufSize, buf); |
350 | testGetLoop<64, uint64_t, false, aligned>(r, bufSize, buf); |
351 | |
352 | // Signed NEG=false |
353 | testGetLoop<7, int8_t, false, aligned>(r, bufSize, buf); |
354 | testGetLoop<15, int16_t, false, aligned>(r, bufSize, buf); |
355 | testGetLoop<31, int32_t, false, aligned>(r, bufSize, buf); |
356 | testGetLoop<63, int64_t, false, aligned>(r, bufSize, buf); |
357 | |
358 | // Signed NEG=true |
359 | testGetLoop<7, int8_t, true, aligned>(r, bufSize, buf); |
360 | testGetLoop<15, int16_t, true, aligned>(r, bufSize, buf); |
361 | testGetLoop<31, int32_t, true, aligned>(r, bufSize, buf); |
362 | testGetLoop<63, int64_t, true, aligned>(r, bufSize, buf); |
363 | } |
364 | } |
365 | |
366 | TEST(Bits, ConcatenationUnalignedUnsigned) { |
367 | testConcatenation<false>(); |
368 | } |
369 | |
370 | TEST(Bits, ConcatenationAligned) { |
371 | testConcatenation<true>(); |
372 | } |
373 | |
374 | int main(int argc, char* argv[]) { |
375 | testing::InitGoogleTest(&argc, argv); |
376 | gflags::ParseCommandLineFlags(&argc, &argv, true); |
377 | return RUN_ALL_TESTS(); |
378 | } |
379 | |