Bitcoin Core 31.99.0
P2P Digital Currency
bitdeque.cpp
Go to the documentation of this file.
1// Copyright (c) 2022-present The Bitcoin Core developers
2// Distributed under the MIT software license, see the accompanying
3// file COPYING or http://www.opensource.org/licenses/mit-license.php.
4
5#include <random.h>
6#include <test/fuzz/FuzzedDataProvider.h>
7#include <test/fuzz/util.h>
8#include <util/bitdeque.h>
9
10#include <deque>
11#include <vector>
12
13namespace {
14
15constexpr int LEN_BITS = 16;
16constexpr int RANDDATA_BITS = 20;
17
18using bitdeque_type = bitdeque<128>;
19
21std::vector<bool> RANDDATA;
22
23void InitRandData()
24{
25 FastRandomContext ctx(true);
26 RANDDATA.clear();
27 for (size_t i = 0; i < (1U << RANDDATA_BITS) + (1U << LEN_BITS); ++i) {
28 RANDDATA.push_back(ctx.randbool());
29 }
30}
31
32} // namespace
33
34FUZZ_TARGET(bitdeque, .init = InitRandData)
35{
36 FuzzedDataProvider provider(buffer.data(), buffer.size());
37 FastRandomContext ctx(true);
38
39 size_t maxlen = (1U << provider.ConsumeIntegralInRange<size_t>(0, LEN_BITS)) - 1;
40 size_t limitlen = 4 * maxlen;
41
42 std::deque<bool> deq;
43 bitdeque_type bitdeq;
44
45 const auto& cdeq = deq;
46 const auto& cbitdeq = bitdeq;
47
48 size_t initlen = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
49 while (initlen) {
50 bool val = ctx.randbool();
51 deq.push_back(val);
52 bitdeq.push_back(val);
53 --initlen;
54 }
55
56 const auto iter_limit{maxlen > 6000 ? 90U : 900U};
57 LIMITED_WHILE (provider.remaining_bytes() > 0, iter_limit) {
58 CallOneOf(
59 provider,
60 [&] {
61 // constructor()
62 deq = std::deque<bool>{};
63 bitdeq = bitdeque_type{};
64 },
65 [&] {
66 // clear()
67 deq.clear();
68 bitdeq.clear();
69 },
70 [&] {
71 // resize()
72 auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
73 deq.resize(count);
74 bitdeq.resize(count);
75 },
76 [&] {
77 // assign(count, val)
78 auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
79 bool val = ctx.randbool();
80 deq.assign(count, val);
81 bitdeq.assign(count, val);
82 },
83 [&] {
84 // constructor(count, val)
85 auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
86 bool val = ctx.randbool();
87 deq = std::deque<bool>(count, val);
88 bitdeq = bitdeque_type(count, val);
89 },
90 [&] {
91 // constructor(count)
92 auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
93 deq = std::deque<bool>(count);
94 bitdeq = bitdeque_type(count);
95 },
96 [&] {
97 // construct(begin, end)
98 auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
99 auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS);
100 auto rand_end = rand_begin + count;
101 deq = std::deque<bool>(rand_begin, rand_end);
102 bitdeq = bitdeque_type(rand_begin, rand_end);
103 },
104 [&] {
105 // assign(begin, end)
106 auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
107 auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS);
108 auto rand_end = rand_begin + count;
109 deq.assign(rand_begin, rand_end);
110 bitdeq.assign(rand_begin, rand_end);
111 },
112 [&] {
113 // construct(initializer_list)
114 std::initializer_list<bool> ilist{ctx.randbool(), ctx.randbool(), ctx.randbool(), ctx.randbool(), ctx.randbool()};
115 deq = std::deque<bool>(ilist);
116 bitdeq = bitdeque_type(ilist);
117 },
118 [&] {
119 // assign(initializer_list)
120 std::initializer_list<bool> ilist{ctx.randbool(), ctx.randbool(), ctx.randbool()};
121 deq.assign(ilist);
122 bitdeq.assign(ilist);
123 },
124 [&] {
125 // operator=(const&)
126 auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
127 bool val = ctx.randbool();
128 const std::deque<bool> deq2(count, val);
129 deq = deq2;
130 const bitdeque_type bitdeq2(count, val);
131 bitdeq = bitdeq2;
132 },
133 [&] {
134 // operator=(&&)
135 auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
136 bool val = ctx.randbool();
137 std::deque<bool> deq2(count, val);
138 deq = std::move(deq2);
139 bitdeque_type bitdeq2(count, val);
140 bitdeq = std::move(bitdeq2);
141 },
142 [&] {
143 // deque swap
144 auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
145 auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS);
146 auto rand_end = rand_begin + count;
147 std::deque<bool> deq2(rand_begin, rand_end);
148 bitdeque_type bitdeq2(rand_begin, rand_end);
149 using std::swap;
150 assert(deq.size() == bitdeq.size());
151 assert(deq2.size() == bitdeq2.size());
152 swap(deq, deq2);
153 swap(bitdeq, bitdeq2);
154 assert(deq.size() == bitdeq.size());
155 assert(deq2.size() == bitdeq2.size());
156 },
157 [&] {
158 // deque.swap
159 auto count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
160 auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS);
161 auto rand_end = rand_begin + count;
162 std::deque<bool> deq2(rand_begin, rand_end);
163 bitdeque_type bitdeq2(rand_begin, rand_end);
164 assert(deq.size() == bitdeq.size());
165 assert(deq2.size() == bitdeq2.size());
166 deq.swap(deq2);
167 bitdeq.swap(bitdeq2);
168 assert(deq.size() == bitdeq.size());
169 assert(deq2.size() == bitdeq2.size());
170 },
171 [&] {
172 // operator=(initializer_list)
173 std::initializer_list<bool> ilist{ctx.randbool(), ctx.randbool(), ctx.randbool()};
174 deq = ilist;
175 bitdeq = ilist;
176 },
177 [&] {
178 // iterator arithmetic
179 auto pos1 = provider.ConsumeIntegralInRange<long>(0, cdeq.size());
180 auto pos2 = provider.ConsumeIntegralInRange<long>(0, cdeq.size());
181 auto it = deq.begin() + pos1;
182 auto bitit = bitdeq.begin() + pos1;
183 if ((size_t)pos1 != cdeq.size()) assert(*it == *bitit);
184 assert(it - deq.begin() == pos1);
185 assert(bitit - bitdeq.begin() == pos1);
186 if (provider.ConsumeBool()) {
187 it += pos2 - pos1;
188 bitit += pos2 - pos1;
189 } else {
190 it -= pos1 - pos2;
191 bitit -= pos1 - pos2;
192 }
193 if ((size_t)pos2 != cdeq.size()) assert(*it == *bitit);
194 assert(deq.end() - it == bitdeq.end() - bitit);
195 if (provider.ConsumeBool()) {
196 if ((size_t)pos2 != cdeq.size()) {
197 ++it;
198 ++bitit;
199 }
200 } else {
201 if (pos2 != 0) {
202 --it;
203 --bitit;
204 }
205 }
206 assert(deq.end() - it == bitdeq.end() - bitit);
207 },
208 [&] {
209 // begin() and end()
210 assert(deq.end() - deq.begin() == bitdeq.end() - bitdeq.begin());
211 },
212 [&] {
213 // begin() and end() (const)
214 assert(cdeq.end() - cdeq.begin() == cbitdeq.end() - cbitdeq.begin());
215 },
216 [&] {
217 // rbegin() and rend()
218 assert(deq.rend() - deq.rbegin() == bitdeq.rend() - bitdeq.rbegin());
219 },
220 [&] {
221 // rbegin() and rend() (const)
222 assert(cdeq.rend() - cdeq.rbegin() == cbitdeq.rend() - cbitdeq.rbegin());
223 },
224 [&] {
225 // cbegin() and cend()
226 assert(cdeq.cend() - cdeq.cbegin() == cbitdeq.cend() - cbitdeq.cbegin());
227 },
228 [&] {
229 // crbegin() and crend()
230 assert(cdeq.crend() - cdeq.crbegin() == cbitdeq.crend() - cbitdeq.crbegin());
231 },
232 [&] {
233 // size() and maxsize()
234 assert(cdeq.size() == cbitdeq.size());
235 assert(cbitdeq.size() <= cbitdeq.max_size());
236 },
237 [&] {
238 // empty
239 assert(cdeq.empty() == cbitdeq.empty());
240 },
241 [&] {
242 // at (in range) and flip
243 if (!cdeq.empty()) {
244 size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 1);
245 auto& ref = deq.at(pos);
246 auto bitref = bitdeq.at(pos);
247 assert(ref == bitref);
248 if (ctx.randbool()) {
249 ref = !ref;
250 bitref.flip();
251 }
252 }
253 },
254 [&] {
255 // at (maybe out of range) and bit assign
256 size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() + maxlen);
257 bool newval = ctx.randbool();
258 bool throw_deq{false}, throw_bitdeq{false};
259 bool val_deq{false}, val_bitdeq{false};
260 try {
261 auto& ref = deq.at(pos);
262 val_deq = ref;
263 ref = newval;
264 } catch (const std::out_of_range&) {
265 throw_deq = true;
266 }
267 try {
268 auto ref = bitdeq.at(pos);
269 val_bitdeq = ref;
270 ref = newval;
271 } catch (const std::out_of_range&) {
272 throw_bitdeq = true;
273 }
274 assert(throw_deq == throw_bitdeq);
275 assert(throw_bitdeq == (pos >= cdeq.size()));
276 if (!throw_deq) assert(val_deq == val_bitdeq);
277 },
278 [&] {
279 // at (maybe out of range) (const)
280 size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() + maxlen);
281 bool throw_deq{false}, throw_bitdeq{false};
282 bool val_deq{false}, val_bitdeq{false};
283 try {
284 auto& ref = cdeq.at(pos);
285 val_deq = ref;
286 } catch (const std::out_of_range&) {
287 throw_deq = true;
288 }
289 try {
290 auto ref = cbitdeq.at(pos);
291 val_bitdeq = ref;
292 } catch (const std::out_of_range&) {
293 throw_bitdeq = true;
294 }
295 assert(throw_deq == throw_bitdeq);
296 assert(throw_bitdeq == (pos >= cdeq.size()));
297 if (!throw_deq) assert(val_deq == val_bitdeq);
298 },
299 [&] {
300 // operator[]
301 if (!cdeq.empty()) {
302 size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 1);
303 assert(deq[pos] == bitdeq[pos]);
304 if (ctx.randbool()) {
305 deq[pos] = !deq[pos];
306 bitdeq[pos].flip();
307 }
308 }
309 },
310 [&] {
311 // operator[] const
312 if (!cdeq.empty()) {
313 size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 1);
314 assert(deq[pos] == bitdeq[pos]);
315 }
316 },
317 [&] {
318 // front()
319 if (!cdeq.empty()) {
320 auto& ref = deq.front();
321 auto bitref = bitdeq.front();
322 assert(ref == bitref);
323 if (ctx.randbool()) {
324 ref = !ref;
325 bitref = !bitref;
326 }
327 }
328 },
329 [&] {
330 // front() const
331 if (!cdeq.empty()) {
332 auto& ref = cdeq.front();
333 auto bitref = cbitdeq.front();
334 assert(ref == bitref);
335 }
336 },
337 [&] {
338 // back() and swap(bool, ref)
339 if (!cdeq.empty()) {
340 auto& ref = deq.back();
341 auto bitref = bitdeq.back();
342 assert(ref == bitref);
343 if (ctx.randbool()) {
344 ref = !ref;
345 bitref.flip();
346 }
347 }
348 },
349 [&] {
350 // back() const
351 if (!cdeq.empty()) {
352 const auto& cdeq = deq;
353 const auto& cbitdeq = bitdeq;
354 auto& ref = cdeq.back();
355 auto bitref = cbitdeq.back();
356 assert(ref == bitref);
357 }
358 },
359 [&] {
360 // push_back()
361 if (cdeq.size() < limitlen) {
362 bool val = ctx.randbool();
363 if (cdeq.empty()) {
364 deq.push_back(val);
365 bitdeq.push_back(val);
366 } else {
367 size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 1);
368 auto& ref = deq[pos];
369 auto bitref = bitdeq[pos];
370 assert(ref == bitref);
371 deq.push_back(val);
372 bitdeq.push_back(val);
373 assert(ref == bitref); // references are not invalidated
374 }
375 }
376 },
377 [&] {
378 // push_front()
379 if (cdeq.size() < limitlen) {
380 bool val = ctx.randbool();
381 if (cdeq.empty()) {
382 deq.push_front(val);
383 bitdeq.push_front(val);
384 } else {
385 size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 1);
386 auto& ref = deq[pos];
387 auto bitref = bitdeq[pos];
388 assert(ref == bitref);
389 deq.push_front(val);
390 bitdeq.push_front(val);
391 assert(ref == bitref); // references are not invalidated
392 }
393 }
394 },
395 [&] {
396 // pop_back()
397 if (!cdeq.empty()) {
398 if (cdeq.size() == 1) {
399 deq.pop_back();
400 bitdeq.pop_back();
401 } else {
402 size_t pos = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 2);
403 auto& ref = deq[pos];
404 auto bitref = bitdeq[pos];
405 assert(ref == bitref);
406 deq.pop_back();
407 bitdeq.pop_back();
408 assert(ref == bitref); // references to other elements are not invalidated
409 }
410 }
411 },
412 [&] {
413 // pop_front()
414 if (!cdeq.empty()) {
415 if (cdeq.size() == 1) {
416 deq.pop_front();
417 bitdeq.pop_front();
418 } else {
419 size_t pos = provider.ConsumeIntegralInRange<size_t>(1, cdeq.size() - 1);
420 auto& ref = deq[pos];
421 auto bitref = bitdeq[pos];
422 assert(ref == bitref);
423 deq.pop_front();
424 bitdeq.pop_front();
425 assert(ref == bitref); // references to other elements are not invalidated
426 }
427 }
428 },
429 [&] {
430 // erase (in middle, single)
431 if (!cdeq.empty()) {
432 size_t before = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - 1);
433 size_t after = cdeq.size() - 1 - before;
434 auto it = deq.erase(cdeq.begin() + before);
435 auto bitit = bitdeq.erase(cbitdeq.begin() + before);
436 assert(it == cdeq.begin() + before && it == cdeq.end() - after);
437 assert(bitit == cbitdeq.begin() + before && bitit == cbitdeq.end() - after);
438 }
439 },
440 [&] {
441 // erase (at front, range)
442 size_t count = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size());
443 auto it = deq.erase(cdeq.begin(), cdeq.begin() + count);
444 auto bitit = bitdeq.erase(cbitdeq.begin(), cbitdeq.begin() + count);
445 assert(it == deq.begin());
446 assert(bitit == bitdeq.begin());
447 },
448 [&] {
449 // erase (at back, range)
450 size_t count = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size());
451 auto it = deq.erase(cdeq.end() - count, cdeq.end());
452 auto bitit = bitdeq.erase(cbitdeq.end() - count, cbitdeq.end());
453 assert(it == deq.end());
454 assert(bitit == bitdeq.end());
455 },
456 [&] {
457 // erase (in middle, range)
458 size_t count = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size());
459 size_t before = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size() - count);
460 size_t after = cdeq.size() - count - before;
461 auto it = deq.erase(cdeq.begin() + before, cdeq.end() - after);
462 auto bitit = bitdeq.erase(cbitdeq.begin() + before, cbitdeq.end() - after);
463 assert(it == cdeq.begin() + before && it == cdeq.end() - after);
464 assert(bitit == cbitdeq.begin() + before && bitit == cbitdeq.end() - after);
465 },
466 [&] {
467 // insert/emplace (in middle, single)
468 if (cdeq.size() < limitlen) {
469 size_t before = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size());
470 bool val = ctx.randbool();
471 bool do_emplace = provider.ConsumeBool();
472 auto it = deq.insert(cdeq.begin() + before, val);
473 auto bitit = do_emplace ? bitdeq.emplace(cbitdeq.begin() + before, val)
474 : bitdeq.insert(cbitdeq.begin() + before, val);
475 assert(it == deq.begin() + before);
476 assert(bitit == bitdeq.begin() + before);
477 }
478 },
479 [&] {
480 // insert (at front, begin/end)
481 if (cdeq.size() < limitlen) {
482 size_t count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
483 auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS);
484 auto rand_end = rand_begin + count;
485 auto it = deq.insert(cdeq.begin(), rand_begin, rand_end);
486 auto bitit = bitdeq.insert(cbitdeq.begin(), rand_begin, rand_end);
487 assert(it == cdeq.begin());
488 assert(bitit == cbitdeq.begin());
489 }
490 },
491 [&] {
492 // insert (at back, begin/end)
493 if (cdeq.size() < limitlen) {
494 size_t count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
495 auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS);
496 auto rand_end = rand_begin + count;
497 auto it = deq.insert(cdeq.end(), rand_begin, rand_end);
498 auto bitit = bitdeq.insert(cbitdeq.end(), rand_begin, rand_end);
499 assert(it == cdeq.end() - count);
500 assert(bitit == cbitdeq.end() - count);
501 }
502 },
503 [&] {
504 // insert (in middle, range)
505 if (cdeq.size() < limitlen) {
506 size_t count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
507 size_t before = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size());
508 bool val = ctx.randbool();
509 auto it = deq.insert(cdeq.begin() + before, count, val);
510 auto bitit = bitdeq.insert(cbitdeq.begin() + before, count, val);
511 assert(it == deq.begin() + before);
512 assert(bitit == bitdeq.begin() + before);
513 }
514 },
515 [&] {
516 // insert (in middle, begin/end)
517 if (cdeq.size() < limitlen) {
518 size_t count = provider.ConsumeIntegralInRange<size_t>(0, maxlen);
519 size_t before = provider.ConsumeIntegralInRange<size_t>(0, cdeq.size());
520 auto rand_begin = RANDDATA.begin() + ctx.randbits(RANDDATA_BITS);
521 auto rand_end = rand_begin + count;
522 auto it = deq.insert(cdeq.begin() + before, rand_begin, rand_end);
523 auto bitit = bitdeq.insert(cbitdeq.begin() + before, rand_begin, rand_end);
524 assert(it == deq.begin() + before);
525 assert(bitit == bitdeq.begin() + before);
526 }
527 });
528 }
529 {
530 assert(deq.size() == bitdeq.size());
531 auto it = deq.begin();
532 auto bitit = bitdeq.begin();
533 auto itend = deq.end();
534 while (it != itend) {
535 assert(*it == *bitit);
536 ++it;
537 ++bitit;
538 }
539 }
540}
FUZZ_TARGET
FUZZ_TARGET(bitdeque,.init=InitRandData)
Definition: bitdeque.cpp:34
FastRandomContext
Fast randomness source.
Definition: random.h:386
FuzzedDataProvider::ConsumeIntegralInRange
T ConsumeIntegralInRange(T min, T max)
Definition: FuzzedDataProvider.h:205
RandomMixin::randbool
bool randbool() noexcept
Generate a random boolean.
Definition: random.h:325
RandomMixin::randbits
uint64_t randbits(int bits) noexcept
Generate a random (bits)-bit integer.
Definition: random.h:204
bitdeque
Class that mimics std::deque<bool>, but with std::vector<bool>'s bit packing.
Definition: bitdeque.h:24
LIMITED_WHILE
LIMITED_WHILE(provider.remaining_bytes(), 10000)
Definition: coinscache_sim.cpp:271
init
Definition: basic.cpp:8
provider
FuzzedDataProvider provider
Definition: dbwrapper.cpp:366
CallOneOf
size_t CallOneOf(FuzzedDataProvider &fuzzed_data_provider, Callables... callables)
Definition: util.h:37
count
static int count
Definition: tests_exhaustive.c:39
assert
assert(!tx.IsCoinBase())
Generated on Sun Jul 19 2026 20:00:34 for Bitcoin Core by doxygen 1.9.4