Debian Codegraph @

src/SPERR/test_scripts/bitstream_unit_test.cpp

raw
1 #include "gtest/gtest.h"
2
3 #include "Bitmask.h"
4 #include "Bitstream.h"
5
6 #include <random>
7 #include <vector>
8
9 namespace {
10
11 using Stream = sperr::Bitstream;
12 using Mask = sperr::Bitmask;
13
14 TEST(Bitstream, constructor)
15 {
16 auto s1 = Stream();
17 EXPECT_EQ(s1.capacity(), 0);
18
19 auto s2 = Stream(1024 + 1);
20 EXPECT_EQ(s2.capacity(), 1024 + 64);
21
22 auto s3 = Stream(1024 + 63);
23 EXPECT_EQ(s3.capacity(), 1024 + 64);
24
25 auto s4 = Stream(1024 + 64);
26 EXPECT_EQ(s4.capacity(), 1024 + 64);
27
28 auto s5 = Stream(1024 + 65);
29 EXPECT_EQ(s5.capacity(), 1024 + 64 * 2);
30
31 auto s6 = Stream(1024 - 1);
32 EXPECT_EQ(s6.capacity(), 1024);
33
34 auto s7 = Stream(1024 - 63);
35 EXPECT_EQ(s7.capacity(), 1024);
36
37 auto s8 = Stream(1024 - 64);
38 EXPECT_EQ(s8.capacity(), 1024 - 64);
39
40 auto s9 = Stream(1024 - 65);
41 EXPECT_EQ(s9.capacity(), 1024 - 64);
42 }
43
44 TEST(Bitstream, MemoryAllocation1)
45 {
46 auto s1 = Stream(64);
47 auto vec = std::vector<bool>();
48
49 std::random_device rd;
50 std::mt19937 gen(rd());
51 std::uniform_int_distribution<unsigned int> distrib(0, 1);
52
53 s1.rewind();
54 for (size_t i = 0; i < 64; i++) {
55 auto val = distrib(gen);
56 s1.wbit(val);
57 vec.push_back(val);
58 }
59 EXPECT_EQ(s1.capacity(), 64);
60
61 // Write another bit and flush; the capacity is expected to grow to 128.
62 s1.wbit(1);
63 vec.push_back(1);
64 EXPECT_EQ(s1.wtell(), 65);
65 EXPECT_EQ(s1.capacity(), 64);
66 s1.flush();
67 EXPECT_EQ(s1.capacity(), 128);
68
69 // All saved bits should be correct too.
70 s1.rewind();
71 for (size_t i = 0; i < vec.size(); i++)
72 EXPECT_EQ(s1.rbit(), vec[i]) << "at idx = " << i;
73
74 // Let's try to trigger another memory re-allocation
75 s1.wseek(65);
76 for (size_t i = 0; i < 64; i++) {
77 auto val = distrib(gen);
78 s1.wbit(val);
79 vec.push_back(val);
80 }
81 EXPECT_EQ(s1.wtell(), 129);
82 EXPECT_EQ(s1.capacity(), 128);
83 s1.flush();
84 EXPECT_EQ(s1.capacity(), 192);
85 s1.rewind();
86 for (size_t i = 0; i < vec.size(); i++)
87 EXPECT_EQ(s1.rbit(), vec[i]) << "at idx = " << i;
88 }
89
90 TEST(Bitstream, StreamWriteRead)
91 {
92 const size_t N = 150;
93 auto s1 = Stream();
94 auto vec = std::vector<bool>(N);
95
96 // Make N writes
97 std::random_device rd;
98 std::mt19937 gen(rd());
99 std::uniform_int_distribution<unsigned int> distrib1(0, 1);
100 for (size_t i = 0; i < N; i++) {
101 const bool bit = distrib1(gen);
102 vec[i] = bit;
103 s1.wbit(bit);
104 }
105 EXPECT_EQ(s1.wtell(), 150);
106 s1.flush();
107 EXPECT_EQ(s1.wtell(), 192);
108
109 s1.rewind();
110 for (size_t i = 0; i < N; i++)
111 EXPECT_EQ(s1.rbit(), vec[i]) << " at idx = " << i;
112 }
113
114 TEST(Bitstream, RandomWriteRead)
115 {
116 const size_t N = 256;
117 auto s1 = Stream(59);
118 auto vec = std::vector<bool>(N);
119
120 // Make N stream writes
121 std::random_device rd;
122 std::mt19937 gen(rd());
123 std::uniform_int_distribution<unsigned int> distrib1(0, 1);
124 for (size_t i = 0; i < N; i++) {
125 const bool bit = distrib1(gen);
126 vec[i] = bit;
127 s1.wbit(bit);
128 }
129 EXPECT_EQ(s1.wtell(), 256);
130 s1.flush();
131 EXPECT_EQ(s1.wtell(), 256);
132
133 // Make random writes on word boundaries
134 s1.wseek(63);
135 s1.wbit(true);
136 vec[63] = true;
137 s1.wseek(127);
138 s1.wbit(false);
139 vec[127] = false;
140 s1.wseek(191);
141 s1.wbit(true);
142 vec[191] = true;
143 s1.wseek(255);
144 s1.wbit(false);
145 vec[255] = false;
146 s1.rewind();
147 for (size_t i = 0; i < N; i++)
148 EXPECT_EQ(s1.rbit(), vec[i]) << " at idx = " << i;
149
150 // Make random reads
151 std::uniform_int_distribution<unsigned int> distrib2(0, N - 1);
152 for (size_t i = 0; i < 100; i++) {
153 const auto pos = distrib2(gen);
154 s1.rseek(pos);
155 EXPECT_EQ(s1.rbit(), vec[pos]) << " at idx = " << i;
156 }
157 }
158
159 TEST(Bitstream, CompactStream)
160 {
161 // Test full 64-bit multiples
162 size_t N = 128;
163 std::random_device rd;
164 std::mt19937 gen(rd());
165 std::uniform_int_distribution<unsigned int> distrib1(0, 1);
166 auto s1 = Stream();
167
168 for (size_t i = 0; i < N; i++)
169 s1.wbit(distrib1(gen));
170 s1.flush();
171
172 auto buf = s1.get_bitstream(N);
173 EXPECT_EQ(buf.size(), 16);
174 s1.rewind();
175 auto s2 = Stream();
176 s2.parse_bitstream(buf.data(), 128);
177 for (size_t i = 0; i < N; i++)
178 EXPECT_EQ(s1.rbit(), s2.rbit());
179
180 // Test full 64-bit multiples and 8-bit multiples
181 buf = s1.get_bitstream(80);
182 EXPECT_EQ(buf.size(), 10);
183 s1.rewind();
184 s2.parse_bitstream(buf.data(), 80);
185 for (size_t i = 0; i < 80; i++)
186 EXPECT_EQ(s1.rbit(), s2.rbit());
187
188 // Test full 64-bit multiples, 8-bit multiples, and remaining bits
189 buf = s1.get_bitstream(85);
190 EXPECT_EQ(buf.size(), 11);
191 s1.rewind();
192 s2.parse_bitstream(buf.data(), 85);
193 for (size_t i = 0; i < 85; i++)
194 EXPECT_EQ(s1.rbit(), s2.rbit());
195
196 // Test less than 64 bits
197 buf = s1.get_bitstream(45);
198 EXPECT_EQ(buf.size(), 6);
199 s1.rewind();
200 s2.parse_bitstream(buf.data(), 45);
201 for (size_t i = 0; i < 45; i++)
202 EXPECT_EQ(s1.rbit(), s2.rbit());
203
204 // Test less than 8 bits
205 buf = s1.get_bitstream(5);
206 EXPECT_EQ(buf.size(), 1);
207 s1.rewind();
208 s2.parse_bitstream(buf.data(), 5);
209 for (size_t i = 0; i < 5; i++)
210 EXPECT_EQ(s1.rbit(), s2.rbit());
211 }
212
213 TEST(Bitstream, Reserve)
214 {
215 std::random_device rd;
216 std::mt19937 gen(rd());
217 std::uniform_int_distribution<unsigned int> distrib1(0, 1);
218
219 // Reserve on an empty stream.
220 auto s1 = Stream();
221 s1.reserve(30);
222 for (size_t i = 0; i < s1.capacity(); i++)
223 EXPECT_EQ(s1.rbit(), false);
224
225 // Reserve on a stream that's been written.
226 auto s2 = Stream();
227 s1.rewind();
228 for (size_t i = 0; i < 30; i++) {
229 auto bit = distrib1(gen);
230 s1.wbit(bit);
231 s2.wbit(bit);
232 }
233 s1.flush();
234 s2.flush();
235 s1.reserve(100);
236 s1.rewind();
237 s2.rewind();
238 for (size_t i = 0; i < 30; i++)
239 EXPECT_EQ(s1.rbit(), s2.rbit());
240 for (size_t i = 30; i < s1.capacity(); i++)
241 EXPECT_EQ(s1.rbit(), false);
242
243 // Reserve on a stream that's from parsing another bitstream.
244 s1.wseek(30);
245 for (size_t i = 0; i < 41; i++)
246 s1.wbit(distrib1(gen));
247 s1.flush();
248 auto buf = s1.get_bitstream(71);
249 s2.parse_bitstream(buf.data(), 71);
250 s1.rewind();
251 s2.rewind();
252 for (size_t i = 0; i < 71; i++)
253 EXPECT_EQ(s1.rbit(), s2.rbit());
254 s2.reserve(150);
255 for (size_t i = 71; i < s2.capacity(); i++)
256 EXPECT_EQ(s2.rbit(), false);
257 }
258
259 TEST(Bitmask, CountTrue)
260 {
261 auto m1 = Mask(64);
262 for (size_t i = 0; i < 5; i++)
263 m1.wtrue(i * 4);
264 EXPECT_EQ(m1.count_true(), 5);
265
266 m1.reset();
267 m1.resize(110);
268 for (size_t i = 0; i < 20; i++)
269 m1.wtrue(i * 5);
270 EXPECT_EQ(m1.count_true(), 20);
271
272 m1.resize(60);
273 EXPECT_EQ(m1.count_true(), 12); // 0, 5, ..., 50, 55
274
275 m1.resize(192);
276 EXPECT_EQ(m1.count_true(), 13); // 0, 5, ..., 55, 60
277
278 for (size_t i = 0; i < 23; i++)
279 m1.wtrue(i * 7);
280 EXPECT_EQ(m1.count_true(), 34); // 13 + 23 minus positions 0, 35.
281 }
282
283 TEST(Bitmask, RandomReadWrite)
284 {
285 const size_t N = 192;
286 auto m1 = Mask(N);
287 EXPECT_EQ(m1.size(), N);
288 m1.wlong(0, 928798ul);
289 m1.wlong(64, 9845932ul);
290 m1.wlong(128, 77719821ul);
291 EXPECT_EQ(m1.rlong(1), 928798ul);
292 EXPECT_EQ(m1.rlong(65), 9845932ul);
293 EXPECT_EQ(m1.rlong(129), 77719821ul);
294
295 auto vec = std::vector<bool>();
296 for (size_t i = 0; i < N; i++)
297 vec.push_back(m1.rbit(i));
298
299 std::random_device rd;
300 std::mt19937 gen(rd());
301 std::uniform_int_distribution<unsigned int> distrib(0, 1);
302 for (size_t i = 30; i < N - 20; i++) {
303 bool ran = distrib(gen);
304 m1.wbit(i, ran);
305 vec[i] = ran;
306 }
307 for (size_t i = 1; i < N; i += 35) {
308 if (i % 2 == 0) {
309 m1.wtrue(i);
310 vec[i] = true;
311 }
312 else {
313 m1.wfalse(i);
314 vec[i] = false;
315 }
316 }
317 for (size_t i = 0; i < N; i++)
318 EXPECT_EQ(m1.rbit(i), vec[i]) << "at idx = " << i;
319 }
320
321 TEST(Bitmask, BufferTransfer)
322 {
323 auto src = Mask(60);
324 src.wlong(0, 78344ul);
325 auto buf = src.view_buffer();
326
327 auto dst = Mask(60);
328 dst.use_bitstream(buf.data());
329 EXPECT_EQ(src.size(), dst.size());
330 for (size_t i = 0; i < src.size(); i++)
331 EXPECT_EQ(src.rbit(i), dst.rbit(i));
332
333 src.resize(120);
334 src.wlong(100, 19837ul);
335 buf = src.view_buffer();
336
337 dst.resize(120);
338 dst.use_bitstream(buf.data());
339 EXPECT_EQ(src.size(), dst.size());
340 for (size_t i = 0; i < src.size(); i++)
341 EXPECT_EQ(src.rbit(i), dst.rbit(i));
342
343 src.resize(128);
344 buf = src.view_buffer();
345
346 dst.resize(128);
347 dst.use_bitstream(buf.data());
348 EXPECT_EQ(src.size(), dst.size());
349 for (size_t i = 0; i < src.size(); i++)
350 EXPECT_EQ(src.rbit(i), dst.rbit(i));
351
352 src.resize(150);
353 src.wlong(130, 19837ul);
354 buf = src.view_buffer();
355
356 dst.resize(150);
357 dst.use_bitstream(buf.data());
358 EXPECT_EQ(src.size(), dst.size());
359 for (size_t i = 0; i < src.size(); i++)
360 EXPECT_EQ(src.rbit(i), dst.rbit(i));
361 }
362
363 TEST(Bitmask, has_true)
364 {
365 const size_t mask_size = 210;
366
367 // Loop over all positions
368 for (size_t idx = 0; idx < mask_size; idx++) {
369 auto mask = Mask(mask_size);
370 mask.wtrue(idx);
371
372 // Loop over all starting positions
373 for (size_t start = 0; start < mask_size; start++) {
374
375 // Loop over all range length
376 for (size_t len = 0; len < mask_size - start; len++) {
377 auto ans1 = mask.has_true<false>(start, len);
378 auto ans2 = -1l;
379 for (size_t i = start; i < start + len; i++)
380 if (mask.rbit(i)) {
381 ans2 = 1;
382 break;
383 }
384 EXPECT_EQ(ans1, ans2);
385 }
386
387 }
388 }
389 }
390
391 TEST(Bitmask, has_true_position)
392 {
393 const size_t mask_size = 210;
394
395 // Loop over all positions
396 for (size_t idx = 0; idx < mask_size; idx++) {
397 auto mask = Mask(mask_size);
398 mask.wtrue(idx);
399
400 // Loop over all starting positions
401 for (size_t start = 0; start < mask_size; start++) {
402
403 // Loop over all range length
404 for (size_t len = 0; len < mask_size - start; len++) {
405 auto ans1 = mask.has_true<true>(start, len);
406 auto ans2 = -1l;
407 for (size_t i = start; i < start + len; i++)
408 if (mask.rbit(i)) {
409 ans2 = i - start;
410 break;
411 }
412 EXPECT_EQ(ans1, ans2) << "idx = " << idx << ", start = " << start << ", len = " << len << std::endl;
413 if (ans1 != ans2)
414 goto END_LABEL;
415 }
416
417 }
418 }
419
420 END_LABEL:
421 {}
422 }
423
424 #if __cplusplus >= 201907L && defined __cpp_lib_three_way_comparison
425 TEST(Bitmask, spaceship)
426 {
427 auto src = Mask(60);
428 auto dst = Mask(90);
429 EXPECT_NE(src, dst);
430 src.resize(90);
431 EXPECT_EQ(src, dst);
432
433 dst.wlong(64, std::numeric_limits<uint64_t>::max());
434 EXPECT_NE(src, dst);
435
436 for (size_t i = 64; i < 90; i++) {
437 src.wbit(i, i % 3 == 0);
438 dst.wbit(i, i % 3 == 0);
439 }
440 EXPECT_EQ(src.rlong(63), dst.rlong(63));
441 EXPECT_NE(src.rlong(64), dst.rlong(64));
442 EXPECT_EQ(src, dst);
443 }
444 #endif
445
446 } // namespace