Bitcoin Core  29.1.0
P2P Digital Currency
bitset.cpp
Go to the documentation of this file.
1 // Copyright (c) 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 <span.h>
7 #include <test/fuzz/util.h>
8 #include <util/bitset.h>
9 
10 #include <bitset>
11 #include <vector>
12 
13 namespace {
14 
16 uint8_t ReadByte(FuzzBufferType& buffer)
17 {
18  if (buffer.empty()) return 0;
19  uint8_t ret = buffer.front();
20  buffer = buffer.subspan(1);
21  return ret;
22 }
23 
25 template<typename S>
26 void TestType(FuzzBufferType buffer)
27 {
32  InsecureRandomContext rng(buffer.size() + 0x10000 * S::Size());
33 
34  using Sim = std::bitset<S::Size()>;
35  // Up to 4 real BitSets (initially 2).
36  std::vector<S> real(2);
37  // Up to 4 std::bitsets with the same corresponding contents.
38  std::vector<Sim> sim(2);
39 
40  /* Compare sim[idx] with real[idx], using all inspector operations. */
41  auto compare_fn = [&](unsigned idx) {
42  /* iterators and operator[] */
43  auto it = real[idx].begin();
44  unsigned first = S::Size();
45  unsigned last = S::Size();
46  for (unsigned i = 0; i < S::Size(); ++i) {
47  bool match = (it != real[idx].end()) && *it == i;
48  assert(sim[idx][i] == real[idx][i]);
49  assert(match == real[idx][i]);
50  assert((it == real[idx].end()) != (it != real[idx].end()));
51  if (match) {
52  ++it;
53  if (first == S::Size()) first = i;
54  last = i;
55  }
56  }
57  assert(it == real[idx].end());
58  assert(!(it != real[idx].end()));
59  /* Any / None */
60  assert(sim[idx].any() == real[idx].Any());
61  assert(sim[idx].none() == real[idx].None());
62  /* First / Last */
63  if (sim[idx].any()) {
64  assert(first == real[idx].First());
65  assert(last == real[idx].Last());
66  }
67  /* Count */
68  assert(sim[idx].count() == real[idx].Count());
69  };
70 
71  LIMITED_WHILE(buffer.size() > 0, 1000) {
72  // Read one byte to determine which operation to execute on the BitSets.
73  int command = ReadByte(buffer) % 64;
74  // Read another byte that determines which bitsets will be involved.
75  unsigned args = ReadByte(buffer);
76  unsigned dest = ((args & 7) * sim.size()) >> 3;
77  unsigned src = (((args >> 3) & 7) * sim.size()) >> 3;
78  unsigned aux = (((args >> 6) & 3) * sim.size()) >> 2;
79  // Args are in range for non-empty sim, or sim is completely empty and will be grown
80  assert((sim.empty() && dest == 0 && src == 0 && aux == 0) ||
81  (!sim.empty() && dest < sim.size() && src < sim.size() && aux < sim.size()));
82 
83  // Pick one operation based on value of command. Not all operations are always applicable.
84  // Loop through the applicable ones until command reaches 0 (which avoids the need to
85  // compute the number of applicable commands ahead of time).
86  while (true) {
87  if (dest < sim.size() && command-- == 0) {
88  /* Set() (true) */
89  unsigned val = ReadByte(buffer) % S::Size();
90  assert(sim[dest][val] == real[dest][val]);
91  sim[dest].set(val);
92  real[dest].Set(val);
93  break;
94  } else if (dest < sim.size() && command-- == 0) {
95  /* Reset() */
96  unsigned val = ReadByte(buffer) % S::Size();
97  assert(sim[dest][val] == real[dest][val]);
98  sim[dest].reset(val);
99  real[dest].Reset(val);
100  break;
101  } else if (dest < sim.size() && command-- == 0) {
102  /* Set() (conditional) */
103  unsigned val = ReadByte(buffer) % S::Size();
104  assert(sim[dest][val] == real[dest][val]);
105  sim[dest].set(val, args >> 7);
106  real[dest].Set(val, args >> 7);
107  break;
108  } else if (sim.size() < 4 && command-- == 0) {
109  /* Construct empty. */
110  sim.resize(sim.size() + 1);
111  real.resize(real.size() + 1);
112  break;
113  } else if (sim.size() < 4 && command-- == 0) {
114  /* Construct singleton. */
115  unsigned val = ReadByte(buffer) % S::Size();
116  std::bitset<S::Size()> newset;
117  newset[val] = true;
118  sim.push_back(newset);
119  real.push_back(S::Singleton(val));
120  break;
121  } else if (dest < sim.size() && command-- == 0) {
122  /* Make random. */
123  compare_fn(dest);
124  sim[dest].reset();
125  real[dest] = S{};
126  for (unsigned i = 0; i < S::Size(); ++i) {
127  if (rng.randbool()) {
128  sim[dest][i] = true;
129  real[dest].Set(i);
130  }
131  }
132  break;
133  } else if (dest < sim.size() && command-- == 0) {
134  /* Assign initializer list. */
135  unsigned r1 = rng.randrange(S::Size());
136  unsigned r2 = rng.randrange(S::Size());
137  unsigned r3 = rng.randrange(S::Size());
138  compare_fn(dest);
139  sim[dest].reset();
140  real[dest] = {r1, r2, r3};
141  sim[dest].set(r1);
142  sim[dest].set(r2);
143  sim[dest].set(r3);
144  break;
145  } else if (!sim.empty() && command-- == 0) {
146  /* Destruct. */
147  compare_fn(sim.size() - 1);
148  sim.pop_back();
149  real.pop_back();
150  break;
151  } else if (sim.size() < 4 && src < sim.size() && command-- == 0) {
152  /* Copy construct. */
153  sim.emplace_back(sim[src]);
154  real.emplace_back(real[src]);
155  break;
156  } else if (src < sim.size() && dest < sim.size() && command-- == 0) {
157  /* Copy assign. */
158  compare_fn(dest);
159  sim[dest] = sim[src];
160  real[dest] = real[src];
161  break;
162  } else if (src < sim.size() && dest < sim.size() && command-- == 0) {
163  /* swap() function. */
164  swap(sim[dest], sim[src]);
165  swap(real[dest], real[src]);
166  break;
167  } else if (sim.size() < 4 && command-- == 0) {
168  /* Construct with initializer list. */
169  unsigned r1 = rng.randrange(S::Size());
170  unsigned r2 = rng.randrange(S::Size());
171  sim.emplace_back();
172  sim.back().set(r1);
173  sim.back().set(r2);
174  real.push_back(S{r1, r2});
175  break;
176  } else if (dest < sim.size() && command-- == 0) {
177  /* Fill() + copy assign. */
178  unsigned len = ReadByte(buffer) % S::Size();
179  compare_fn(dest);
180  sim[dest].reset();
181  for (unsigned i = 0; i < len; ++i) sim[dest][i] = true;
182  real[dest] = S::Fill(len);
183  break;
184  } else if (src < sim.size() && command-- == 0) {
185  /* Iterator copy based compare. */
186  unsigned val = ReadByte(buffer) % S::Size();
187  /* In a first loop, compare begin..end, and copy to it_copy at some point. */
188  auto it = real[src].begin(), it_copy = it;
189  for (unsigned i = 0; i < S::Size(); ++i) {
190  if (i == val) it_copy = it;
191  bool match = (it != real[src].end()) && *it == i;
192  assert(match == sim[src][i]);
193  if (match) ++it;
194  }
195  assert(it == real[src].end());
196  /* Then compare from the copied point again to end. */
197  for (unsigned i = val; i < S::Size(); ++i) {
198  bool match = (it_copy != real[src].end()) && *it_copy == i;
199  assert(match == sim[src][i]);
200  if (match) ++it_copy;
201  }
202  assert(it_copy == real[src].end());
203  break;
204  } else if (src < sim.size() && dest < sim.size() && command-- == 0) {
205  /* operator|= */
206  compare_fn(dest);
207  sim[dest] |= sim[src];
208  real[dest] |= real[src];
209  break;
210  } else if (src < sim.size() && dest < sim.size() && command-- == 0) {
211  /* operator&= */
212  compare_fn(dest);
213  sim[dest] &= sim[src];
214  real[dest] &= real[src];
215  break;
216  } else if (src < sim.size() && dest < sim.size() && command-- == 0) {
217  /* operator-= */
218  compare_fn(dest);
219  sim[dest] &= ~sim[src];
220  real[dest] -= real[src];
221  break;
222  } else if (src < sim.size() && dest < sim.size() && command-- == 0) {
223  /* operator^= */
224  compare_fn(dest);
225  sim[dest] ^= sim[src];
226  real[dest] ^= real[src];
227  break;
228  } else if (src < sim.size() && dest < sim.size() && aux < sim.size() && command-- == 0) {
229  /* operator| */
230  compare_fn(dest);
231  sim[dest] = sim[src] | sim[aux];
232  real[dest] = real[src] | real[aux];
233  break;
234  } else if (src < sim.size() && dest < sim.size() && aux < sim.size() && command-- == 0) {
235  /* operator& */
236  compare_fn(dest);
237  sim[dest] = sim[src] & sim[aux];
238  real[dest] = real[src] & real[aux];
239  break;
240  } else if (src < sim.size() && dest < sim.size() && aux < sim.size() && command-- == 0) {
241  /* operator- */
242  compare_fn(dest);
243  sim[dest] = sim[src] & ~sim[aux];
244  real[dest] = real[src] - real[aux];
245  break;
246  } else if (src < sim.size() && dest < sim.size() && aux < sim.size() && command-- == 0) {
247  /* operator^ */
248  compare_fn(dest);
249  sim[dest] = sim[src] ^ sim[aux];
250  real[dest] = real[src] ^ real[aux];
251  break;
252  } else if (src < sim.size() && aux < sim.size() && command-- == 0) {
253  /* IsSupersetOf() and IsSubsetOf() */
254  bool is_superset = (sim[aux] & ~sim[src]).none();
255  bool is_subset = (sim[src] & ~sim[aux]).none();
256  assert(real[src].IsSupersetOf(real[aux]) == is_superset);
257  assert(real[src].IsSubsetOf(real[aux]) == is_subset);
258  assert(real[aux].IsSupersetOf(real[src]) == is_subset);
259  assert(real[aux].IsSubsetOf(real[src]) == is_superset);
260  break;
261  } else if (src < sim.size() && aux < sim.size() && command-- == 0) {
262  /* operator== and operator!= */
263  assert((sim[src] == sim[aux]) == (real[src] == real[aux]));
264  assert((sim[src] != sim[aux]) == (real[src] != real[aux]));
265  break;
266  } else if (src < sim.size() && aux < sim.size() && command-- == 0) {
267  /* Overlaps() */
268  assert((sim[src] & sim[aux]).any() == real[src].Overlaps(real[aux]));
269  assert((sim[src] & sim[aux]).any() == real[aux].Overlaps(real[src]));
270  break;
271  }
272  }
273  }
274  /* Fully compare the final state. */
275  for (unsigned i = 0; i < sim.size(); ++i) {
276  compare_fn(i);
277  }
278 }
279 
280 } // namespace
281 
282 FUZZ_TARGET(bitset)
283 {
284  unsigned typdat = ReadByte(buffer) % 8;
285  if (typdat == 0) {
286  /* 16 bits */
287  TestType<bitset_detail::IntBitSet<uint16_t>>(buffer);
288  TestType<bitset_detail::MultiIntBitSet<uint16_t, 1>>(buffer);
289  } else if (typdat == 1) {
290  /* 32 bits */
291  TestType<bitset_detail::MultiIntBitSet<uint16_t, 2>>(buffer);
292  TestType<bitset_detail::IntBitSet<uint32_t>>(buffer);
293  } else if (typdat == 2) {
294  /* 48 bits */
295  TestType<bitset_detail::MultiIntBitSet<uint16_t, 3>>(buffer);
296  } else if (typdat == 3) {
297  /* 64 bits */
298  TestType<bitset_detail::IntBitSet<uint64_t>>(buffer);
299  TestType<bitset_detail::MultiIntBitSet<uint64_t, 1>>(buffer);
300  TestType<bitset_detail::MultiIntBitSet<uint32_t, 2>>(buffer);
301  TestType<bitset_detail::MultiIntBitSet<uint16_t, 4>>(buffer);
302  } else if (typdat == 4) {
303  /* 96 bits */
304  TestType<bitset_detail::MultiIntBitSet<uint32_t, 3>>(buffer);
305  } else if (typdat == 5) {
306  /* 128 bits */
307  TestType<bitset_detail::MultiIntBitSet<uint64_t, 2>>(buffer);
308  TestType<bitset_detail::MultiIntBitSet<uint32_t, 4>>(buffer);
309  } else if (typdat == 6) {
310  /* 192 bits */
311  TestType<bitset_detail::MultiIntBitSet<uint64_t, 3>>(buffer);
312  } else if (typdat == 7) {
313  /* 256 bits */
314  TestType<bitset_detail::MultiIntBitSet<uint64_t, 4>>(buffer);
315  }
316 }
NetPermissionFlags::None
ret
int ret
Definition: bitcoin-cli.cpp:1358
assert
assert(!tx.IsCoinBase())
FUZZ_TARGET
FUZZ_TARGET(bitset)
Definition: bitset.cpp:282
LIMITED_WHILE
#define LIMITED_WHILE(condition, limit)
Can be used to limit a theoretically unbounded loop.
Definition: fuzz.h:22
S
#define S(a, b, c, d, e, f, g, h, i, j, k, l, m, n, o, p)
Definition: precomputed_ecmult.c:8
FuzzBufferType
std::span< const uint8_t > FuzzBufferType
Definition: fuzz.h:25
args
ArgsManager & args
Definition: bitcoind.cpp:277
InsecureRandomContext
xoroshiro128++ PRNG.
Definition: random.h:415
command
const auto command
Definition: bitcoin-wallet.cpp:125
count
static int count
Definition: tests_exhaustive.c:34
Generated on Wed Sep 3 2025 12:00:00 for Bitcoin Core by   doxygen 1.8.14