Blender V5.3
BLI_bit_span_test.cc
Go to the documentation of this file.
1/* SPDX-FileCopyrightText: 2023 Blender Authors
2 *
3 * SPDX-License-Identifier: Apache-2.0 */
4
5#include <array>
6
7#include "BLI_bit_span.hh"
8#include "BLI_bit_span_ops.hh"
10#include "BLI_bit_vector.hh"
11#include "BLI_timeit.hh"
12#include "BLI_vector.hh"
13
14#include "testing/testing.h"
15
16namespace blender::bits::tests {
17
18TEST(bit_span, DefaultConstructor)
19{
20 {
21 char buffer[sizeof(BitSpan)];
22 memset(buffer, 0xff, sizeof(BitSpan));
23 BitSpan &span = *new (buffer) BitSpan();
24 EXPECT_TRUE(span.is_empty());
25 EXPECT_EQ(span.size(), 0);
26 }
27 {
28 char buffer[sizeof(MutableBitSpan)];
29 memset(buffer, 0xff, sizeof(MutableBitSpan));
30 MutableBitSpan &span = *new (buffer) MutableBitSpan();
31 EXPECT_TRUE(span.is_empty());
32 EXPECT_EQ(span.size(), 0);
33 }
34}
35
36TEST(bit_span, Iteration)
37{
38 uint64_t data = (1 << 2) | (1 << 3);
39 const BitSpan span(&data, 30);
40 EXPECT_EQ(span.size(), 30);
41 int index = 0;
42 for (const BitRef bit : span) {
43 EXPECT_EQ(bit.test(), ELEM(index, 2, 3));
44 index++;
45 }
46
47 {
48 const Vector<int> expect{2, 3};
50 for (const int bit_index : iter_1_indices(data)) {
51 result.append(bit_index);
52 }
53 EXPECT_EQ_SPAN(expect.as_span(), result.as_span());
54 }
55 {
56 uint64_t data2 = 0xFBu;
57 const Vector<int> expect{0, 1, 3, 4, 5, 6, 7};
59 for (const int bit_index : iter_1_indices(data2)) {
60 result.append(bit_index);
61 }
62 EXPECT_EQ_SPAN(expect.as_span(), result.as_span());
63 }
64 {
65 uint64_t data2 = ~uint64_t(0);
66 int i = 0;
67 for (const int bit_index : iter_1_indices(data2)) {
68 EXPECT_EQ(i, bit_index);
69 i++;
70 }
71 EXPECT_EQ(i, 64);
72 }
73 {
74 uint64_t data2 = 0;
75 int i = 0;
76 for ([[maybe_unused]] const int bit_index : iter_1_indices(data2)) {
77 i++;
78 }
79 EXPECT_EQ(i, 0);
80 }
81}
82
83TEST(bit_span, MutableIteration)
84{
85 uint64_t data = 0;
86 MutableBitSpan span(&data, 40);
87 EXPECT_EQ(span.size(), 40);
88 int index = 0;
89 for (MutableBitRef bit : span) {
90 bit.set(index % 4 == 0);
91 index++;
92 }
94 0b0000'0000'0000'0000'0000'0000'0001'0001'0001'0001'0001'0001'0001'0001'0001'0001);
95}
96
97TEST(bit_span, SubscriptOperator)
98{
99 uint64_t data[2] = {0, 0};
100 MutableBitSpan mutable_span(data, 128);
101 BitSpan span = mutable_span;
102
103 EXPECT_EQ(mutable_span.data(), data);
104 EXPECT_EQ(mutable_span.bit_range(), IndexRange(128));
105 EXPECT_EQ(span.data(), data);
106 EXPECT_EQ(span.bit_range(), IndexRange(128));
107
108 EXPECT_FALSE(mutable_span[5].test());
109 EXPECT_FALSE(span[5].test());
110 mutable_span[5].set(true);
111 EXPECT_TRUE(mutable_span[5].test());
112 EXPECT_TRUE(span[5].test());
113
114 EXPECT_FALSE(mutable_span[120].test());
115 EXPECT_FALSE(span[120].test());
116 mutable_span[120].set(true);
117 EXPECT_TRUE(mutable_span[120].test());
118 EXPECT_TRUE(span[120].test());
119
120 EXPECT_EQ(data[0],
121 0b0000'0000'0000'0000'0000'0000'0000'0000'0000'0000'0000'0000'0000'0000'0010'0000);
122 EXPECT_EQ(data[1],
123 0b0000'0001'0000'0000'0000'0000'0000'0000'0000'0000'0000'0000'0000'0000'0000'0000);
124}
125
126TEST(bit_span, RangeConstructor)
127{
128 uint64_t data = 0;
129 MutableBitSpan mutable_span(&data, IndexRange(4, 3));
130 BitSpan span = mutable_span;
131
132 EXPECT_FALSE(mutable_span[1].test());
133 EXPECT_FALSE(span[1].test());
134 mutable_span[0].set(true);
135 mutable_span[1].set(true);
136 mutable_span[2].set(true);
137 mutable_span[0].set(false);
138 mutable_span[2].set(false);
139 EXPECT_TRUE(mutable_span[1].test());
140 EXPECT_TRUE(span[1].test());
141
143 0b0000'0000'0000'0000'0000'0000'0000'0000'0000'0000'0000'0000'0000'0000'0010'0000);
144}
145
146TEST(bit_span, Set)
147{
148 uint64_t data = 0;
149 MutableBitSpan(&data, 64).set_all(true);
150 EXPECT_EQ(data, uint64_t(-1));
151 MutableBitSpan(&data, 64).set_all(false);
153
154 MutableBitSpan(&data, IndexRange(4, 8)).set_all(true);
156 0b0000'0000'0000'0000'0000'0000'0000'0000'0000'0000'0000'0000'0000'1111'1111'0000);
157 MutableBitSpan(&data, IndexRange(8, 30)).set_all(false);
158
160 0b0000'0000'0000'0000'0000'0000'0000'0000'0000'0000'0000'0000'0000'0000'1111'0000);
161}
162
163TEST(bit_span, SetEmpty)
164{
165 MutableBitSpan().set_all(true);
166 MutableBitSpan().set_all(false);
167}
168
169TEST(bit_span, SetSliced)
170{
171 std::array<uint64_t, 10> data;
172 memset(data.data(), 0, sizeof(data));
173 MutableBitSpan span{data.data(), 640};
174 span.slice(IndexRange(5, 500)).set_all(true);
175
176 for (const int64_t i : IndexRange(640)) {
177 EXPECT_EQ(span[i], i >= 5 && i < 505);
178 }
179
180 span.slice(IndexRange(10, 190)).set_all(false);
181
182 for (const int64_t i : IndexRange(640)) {
183 EXPECT_EQ(span[i], (i >= 5 && i < 10) || (i >= 200 && i < 505));
184 }
185}
186
187TEST(bit_span, IsBounded)
188{
189 std::array<uint64_t, 10> data;
190
199
205
212}
213
214TEST(bit_span, CopyFrom)
215{
216 std::array<uint64_t, 30> src_data;
217 uint64_t i = 0;
218 for (uint64_t &value : src_data) {
219 value = i;
220 i += 234589766883;
221 }
222 const BitSpan src(src_data.data(), src_data.size() * BitsPerInt);
223
224 std::array<uint64_t, 4> dst_data;
225 dst_data.fill(-1);
226 MutableBitSpan dst(dst_data.data(), 100);
227 dst.copy_from(src.slice({401, 100}));
228
229 for (const int i : dst.index_range()) {
230 EXPECT_TRUE(dst[i].test() == src[401 + i].test());
231 }
232}
233
234TEST(bit_span, InPlaceOr)
235{
236 std::array<uint64_t, 100> data_1;
237 MutableBitSpan span_1(data_1.data(), data_1.size() * BitsPerInt);
238 for (const int i : span_1.index_range()) {
239 span_1[i].set(i % 2 == 0);
240 }
241
242 std::array<uint64_t, 100> data_2;
243 MutableBitSpan span_2(data_2.data(), data_2.size() * BitsPerInt);
244 for (const int i : span_2.index_range()) {
245 span_2[i].set(i % 2 != 0);
246 }
247
248 span_1 |= span_2;
249 for (const int i : span_1.index_range()) {
250 EXPECT_TRUE(span_1[i].test());
251 }
252}
253
254TEST(bit_span, InPlaceAnd)
255{
256 std::array<uint64_t, 100> data_1{};
257 MutableBitSpan span_1(data_1.data(), data_1.size() * BitsPerInt);
258 for (const int i : span_1.index_range()) {
259 span_1[i].set(i % 2 == 0);
260 }
261
262 std::array<uint64_t, 100> data_2{};
263 MutableBitSpan span_2(data_2.data(), data_2.size() * BitsPerInt);
264 for (const int i : span_2.index_range()) {
265 span_2[i].set(i % 2 != 0);
266 }
267
268 span_1 &= span_2;
269 for (const int i : span_1.index_range()) {
270 EXPECT_FALSE(span_1[i].test());
271 }
272}
273
274TEST(bit_span, ForEach1)
275{
276 std::array<uint64_t, 2> data{};
277 MutableBitSpan span(data.data(), data.size() * BitsPerInt);
278 for (const int i : {1, 28, 37, 86}) {
279 span[i].set();
280 }
281
282 Vector<int> indices_test;
283 foreach_1_index(span.slice({4, span.size() - 4}), [&](const int i) { indices_test.append(i); });
284
285 EXPECT_EQ(indices_test.as_span(), Span({24, 33, 82}));
286}
287
288TEST(bit_span, ForEach1Cancel)
289{
290 BitVector<> vec(100, false);
291 vec[4].set();
292 vec[10].set();
293 vec[20].set();
294 {
295 Vector<int> indices;
296 foreach_1_index(vec, [&](const int i) {
297 indices.append(i);
298 return i < 5;
299 });
300 EXPECT_EQ(indices.as_span(), Span({4, 10}));
301 }
302 {
303 Vector<int> indices;
304 foreach_1_index(vec, [&](const int i) {
305 indices.append(i);
306 return i < 15;
307 });
308 EXPECT_EQ(indices.as_span(), Span({4, 10, 20}));
309 }
310 {
311 Vector<int> indices;
312 foreach_1_index(vec, [&](const int i) {
313 indices.append(i);
314 return false;
315 });
316 EXPECT_EQ(indices.as_span(), Span({4}));
317 }
318 {
319 Vector<int> indices;
320 foreach_1_index(vec, [&](const int i) {
321 indices.append(i);
322 return true;
323 });
324 EXPECT_EQ(indices.as_span(), Span({4, 10, 20}));
325 }
326}
327
328TEST(bit_span, FindFirst1Index)
329{
330 {
331 BitVector<> vec(0);
332 EXPECT_EQ(find_first_1_index(vec), std::nullopt);
333 }
334 {
335 BitVector<> vec(10'000, false);
336 EXPECT_EQ(find_first_1_index(vec), std::nullopt);
337 }
338 {
339 BitVector<> vec(10'000, true);
341 }
342 {
343 BitVector<> vec(10, false);
344 vec[6].set();
346 }
347 {
348 BitVector<> vec(10'000, false);
349 vec[2'500].set();
350 EXPECT_EQ(find_first_1_index(vec), 2'500);
351 EXPECT_EQ(find_first_1_index(BitSpan(vec).drop_front(100)), 2'400);
352 }
353 {
354 BitVector<> vec_a(10'000, false);
355 BitVector<> vec_b(10'000, false);
356 vec_a[2'000].set();
357 vec_a[2'400].set();
358 vec_a[2'500].set();
359 vec_b[2'000].set();
360 vec_b[2'400].set();
361 vec_b[2'600].set();
362 /* This finds the first index where the two vectors are different. */
364 [](const BitInt a, const BitInt b) { return a ^ b; }, vec_a, vec_b),
365 2'500);
366 }
367}
368
369TEST(bit_span, FindFirst0Index)
370{
371 {
372 BitVector<> vec(0);
373 EXPECT_EQ(find_first_0_index(vec), std::nullopt);
374 }
375 {
376 BitVector<> vec(10'000, true);
377 EXPECT_EQ(find_first_0_index(vec), std::nullopt);
378 }
379 {
380 BitVector<> vec(10'000, false);
382 }
383 {
384 BitVector<> vec(10'000, true);
385 vec[2'500].reset();
386 EXPECT_EQ(find_first_0_index(vec), 2'500);
387 EXPECT_EQ(find_first_0_index(BitSpan(vec).drop_front(100)), 2'400);
388 }
389}
390
392{
393 {
394 Vector<bool> bools(5, false);
395 bools[2] = true;
396 BitVector<> bits(bools.size());
397 bits[0].set();
399 EXPECT_TRUE(bits[0]);
400 EXPECT_FALSE(bits[1]);
401 EXPECT_TRUE(bits[2]);
402 EXPECT_FALSE(bits[3]);
403 EXPECT_FALSE(bits[4]);
404 }
405 {
406 Vector<bool> bools(100, true);
407 BitVector<> bits(1000, false);
410 EXPECT_FALSE(bits[99]);
411 EXPECT_TRUE(bits[100]);
412 EXPECT_TRUE(bits[101]);
413 EXPECT_TRUE(bits[199]);
414 EXPECT_FALSE(bits[200]);
415 }
416}
417
418TEST(bit_span, to_index_ranges_small)
419{
420 BitVector<> bits(10, false);
421 bits[2].set();
422 bits[3].set();
423 bits[4].set();
424 bits[6].set();
425 bits[7].set();
426
428 IndexRangesBuilder<int> builder(builder_buffer);
429 bits_to_index_ranges(bits, builder);
430
431 EXPECT_EQ(builder.size(), 2);
434}
435
436TEST(bit_span, to_index_ranges_all_ones)
437{
438 BitVector<> bits(10000, true);
439
441 IndexRangesBuilder<int> builder(builder_buffer);
442 bits_to_index_ranges(BitSpan(bits).take_back(8765), builder);
443
444 EXPECT_EQ(builder.size(), 1);
445 EXPECT_EQ(builder[0], IndexRange(8765));
446}
447
448} // namespace blender::bits::tests
#define ELEM(...)
constexpr IndexRange()=default
static constexpr IndexRange from_begin_size(const int64_t begin, const int64_t size)
static constexpr IndexRange from_begin_end_inclusive(const int64_t begin, const int64_t last)
int64_t size() const
void append(const T &value)
Span< T > as_span() const
const BitInt * data() const
BitSpan slice(const IndexRange range) const
const IndexRange & bit_range() const
MutableBitSpan slice(const IndexRange range) const
const IndexRange & bit_range() const
IndexRange index_range() const
void copy_from(const BitSpan other)
Definition bit_span.cc:66
#define EXPECT_FALSE(result)
#define EXPECT_TRUE(result)
TEST(bit_group_vector, DefaultConstruct)
uint64_t BitInt
bool or_bools_into_bits(Span< bool > bools, MutableBitSpan r_bits, int64_t allowed_overshoot=0)
std::optional< int64_t > find_first_1_index_expr(ExprFn &&Expr, const FirstBitSpanT &first_arg, const BitSpanT &...args)
OneBitIteratorRange iter_1_indices(BitInt value)
void bits_to_index_ranges(const BitSpan bits, IndexRangesBuilder< IntT > &builder)
bool is_bounded_span(const BitSpan span)
std::optional< int64_t > find_first_0_index(const BitSpanT &data)
void foreach_1_index(const BitSpanT &data, Fn &&fn)
std::optional< int64_t > find_first_1_index(const BitSpanT &data)
unsigned __int64 uint64_t
Definition BKE_text.h:91
__int64 int64_t
Definition BKE_text.h:90
BMesh const char void * data
EXPECT_EQ(BLI_expr_pylike_eval(expr, nullptr, 0, &result), EXPR_PYLIKE_INVALID)