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