Branch data Line data Source code
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 : :
15 : : /** Pop the first byte from a byte-span, and return it. */
16 : 2872969 : uint8_t ReadByte(FuzzBufferType& buffer)
17 : : {
18 [ + + ]: 2872969 : if (buffer.empty()) return 0;
19 : 2869930 : uint8_t ret = buffer.front();
20 : 2869930 : buffer = buffer.subspan(1);
21 : 2869930 : return ret;
22 : : }
23 : :
24 : : /** Perform a simulation fuzz test on BitSet type S. */
25 : : template<typename S>
26 : 4005 : void TestType(FuzzBufferType buffer)
27 : : {
28 : : /** This fuzz test's design is based on the assumption that the actual bits stored in the
29 : : * bitsets and their simulations do not matter for the purpose of detecting edge cases, thus
30 : : * these are taken from a deterministically-seeded RNG instead. To provide some level of
31 : : * variation however, pick the seed based on the buffer size and size of the chosen bitset. */
32 : 4005 : InsecureRandomContext rng(buffer.size() + 0x10000 * S::Size());
33 : :
34 : : using Sim = std::bitset<S::Size()>;
35 : : // Up to 4 real BitSets (initially 2).
36 : 4005 : std::vector<S> real(2);
37 : : // Up to 4 std::bitsets with the same corresponding contents.
38 [ + - ][ + - ]: 4005 : std::vector<Sim> sim(2);
[ + - ][ + - ]
[ + - ]
39 : :
40 : : /* Compare sim[idx] with real[idx], using all inspector operations. */
41 : 1266081 : auto compare_fn = [&](unsigned idx) {
42 : : /* iterators and operator[] */
43 [ + + + + : 631038 : auto it = real[idx].begin();
+ + ]
44 : 631038 : unsigned first = S::Size();
45 : 631038 : unsigned last = S::Size();
46 : 56387070 : for (unsigned i = 0; i < S::Size(); ++i) {
[ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + ]
47 : 55756032 : bool match = (it != real[idx].end()) && *it == i;
[ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + ]
48 : 55756032 : assert(sim[idx][i] == real[idx][i]);
[ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + ]
49 : 55756032 : assert(match == real[idx][i]);
[ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + ]
50 : 55756032 : assert((it == real[idx].end()) != (it != real[idx].end()));
[ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + ]
51 : 55756032 : if (match) {
[ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + ]
52 : 11081983 : ++it;
53 : 11081983 : if (first == S::Size()) first = i;
[ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + ]
54 : : last = i;
55 : : }
56 : : }
57 : 631038 : assert(it == real[idx].end());
[ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + ]
58 [ - + - + : 631038 : assert(!(it != real[idx].end()));
- + ]
59 : : /* Any / None */
60 : 1369399 : assert(sim[idx].any() == real[idx].Any());
[ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + ]
61 : 1128303 : assert(sim[idx].none() == real[idx].None());
[ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + ]
62 : : /* First / Last */
63 : 631038 : if (sim[idx].any()) {
[ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + ]
64 : 512760 : assert(first == real[idx].First());
[ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + ]
65 : 512760 : assert(last == real[idx].Last());
[ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + ]
66 : : }
67 : : /* Count */
68 : 872134 : assert(sim[idx].count() == real[idx].Count());
[ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + ]
69 : : };
70 : :
71 [ + + + + ]: 1237227 : LIMITED_WHILE (buffer.size() > 0, 1000) {
[ + + + + ]
[ + + + + ]
[ + + + + ]
[ + + + + ]
72 : : // Read one byte to determine which operation to execute on the BitSets.
73 : 1233222 : int command = ReadByte(buffer) % 64;
74 : : // Read another byte that determines which bitsets will be involved.
75 : 1233222 : unsigned args = ReadByte(buffer);
76 [ - + ]: 1233222 : unsigned dest = ((args & 7) * sim.size()) >> 3;
77 : 1233222 : unsigned src = (((args >> 3) & 7) * sim.size()) >> 3;
78 : 1233222 : 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 : 1233222 : 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 [ + + + + ]: 2996776 : if (dest < sim.size() && command-- == 0) {
88 : : /* Set() (true) */
89 : 118996 : unsigned val = ReadByte(buffer) % S::Size();
90 [ - + ]: 118996 : assert(sim[dest][val] == real[dest][val]);
91 [ + - ][ + - ]: 118996 : sim[dest].set(val);
[ + - ][ + - ]
[ + - ]
92 : 118996 : real[dest].Set(val);
93 : 118996 : break;
94 [ + + + + ]: 2877780 : } else if (dest < sim.size() && command-- == 0) {
95 : : /* Reset() */
96 : 40175 : unsigned val = ReadByte(buffer) % S::Size();
97 [ - + ]: 40175 : assert(sim[dest][val] == real[dest][val]);
98 [ + - ][ + - ]: 40175 : sim[dest].reset(val);
[ + - ][ + - ]
[ + - ]
99 : 40175 : real[dest].Reset(val);
100 : 40175 : break;
101 [ + + + + ]: 2837605 : } else if (dest < sim.size() && command-- == 0) {
102 : : /* Set() (conditional) */
103 : 35157 : unsigned val = ReadByte(buffer) % S::Size();
104 [ - + ]: 35157 : assert(sim[dest][val] == real[dest][val]);
105 [ + - ][ + - ]: 35157 : sim[dest].set(val, args >> 7);
[ + - ][ + - ]
[ + - ]
106 : 35157 : real[dest].Set(val, args >> 7);
107 : 35157 : break;
108 [ + + + + ]: 2802448 : } else if (sim.size() < 4 && command-- == 0) {
109 : : /* Construct empty. */
110 [ + - ][ + - ]: 17017 : sim.resize(sim.size() + 1);
[ + - ][ + - ]
[ + - ]
111 [ + - ][ + - ]: 17017 : real.resize(real.size() + 1);
[ + - ][ + - ]
[ + - ]
112 : : break;
113 [ + + + + ]: 2785431 : } else if (sim.size() < 4 && command-- == 0) {
114 : : /* Construct singleton. */
115 : 17163 : unsigned val = ReadByte(buffer) % S::Size();
116 [ + + ]: 21172 : std::bitset<S::Size()> newset;
117 [ + - ][ + - ]: 17163 : newset[val] = true;
[ + - ][ + - ]
[ + - ]
118 [ + - ][ + - ]: 17163 : sim.push_back(newset);
[ + - ][ + - ]
[ + - ]
119 [ + - ][ + - ]: 17163 : real.push_back(S::Singleton(val));
[ + - ][ + - ]
[ + - ]
120 : : break;
121 [ + + + + ]: 2768268 : } else if (dest < sim.size() && command-- == 0) {
[ + + + + ]
122 : : /* Make random. */
123 : 73921 : compare_fn(dest);
124 : 73921 : sim[dest].reset();
125 : 73921 : real[dest] = S{};
126 [ + + ][ + + ]: 6473889 : for (unsigned i = 0; i < S::Size(); ++i) {
[ + + ][ + + ]
[ + + ]
127 [ + + ][ + + ]: 6399968 : if (rng.randbool()) {
128 : 3198683 : sim[dest][i] = true;
129 : 3198683 : real[dest].Set(i);
130 : : }
131 : : }
132 : : break;
133 [ + + + + ]: 2694347 : } else if (dest < sim.size() && command-- == 0) {
[ + + + + ]
134 : : /* Assign initializer list. */
135 : 106705 : unsigned r1 = rng.randrange(S::Size());
136 : 106705 : unsigned r2 = rng.randrange(S::Size());
137 : 106705 : unsigned r3 = rng.randrange(S::Size());
138 : 106705 : compare_fn(dest);
139 : 106705 : sim[dest].reset();
140 : 106705 : real[dest] = {r1, r2, r3};
141 [ + - ][ + - ]: 106705 : sim[dest].set(r1);
[ + - ][ + - ]
[ + - ]
142 [ + - ][ + - ]: 106705 : sim[dest].set(r2);
[ + - ][ + - ]
[ + - ]
143 [ + - ][ + - ]: 106705 : sim[dest].set(r3);
[ + - ][ + - ]
[ + - ]
144 : : break;
145 [ + + + + ]: 2587642 : } else if (!sim.empty() && command-- == 0) {
[ + + + + ]
146 : : /* Destruct. */
147 : 90429 : compare_fn(sim.size() - 1);
148 : 90429 : sim.pop_back();
149 : 90429 : real.pop_back();
150 : : break;
151 [ + + + + : 2497213 : } else if (sim.size() < 4 && src < sim.size() && command-- == 0) {
+ + ][ + +
+ + + + ]
152 : : /* Copy construct. */
153 [ + - ][ + - ]: 15284 : sim.emplace_back(sim[src]);
[ + - ][ + - ]
[ + - ]
154 [ + - ][ + - ]: 15284 : real.emplace_back(real[src]);
[ + - ][ + - ]
[ + - ]
155 : : break;
156 [ + + + - : 2481929 : } else if (src < sim.size() && dest < sim.size() && command-- == 0) {
+ + ][ + +
+ - + + ]
157 : : /* Copy assign. */
158 : 34092 : compare_fn(dest);
159 : 34092 : sim[dest] = sim[src];
160 : 34092 : real[dest] = real[src];
161 : 34092 : break;
162 [ + + + - : 2447837 : } else if (src < sim.size() && dest < sim.size() && command-- == 0) {
+ + ][ + +
+ - + + ]
163 : : /* swap() function. */
164 : 25351 : swap(sim[dest], sim[src]);
165 : 1008387 : swap(real[dest], real[src]);
166 : : break;
167 [ + + + + ]: 2422486 : } else if (sim.size() < 4 && command-- == 0) {
[ + + + + ]
[ + + + + ]
168 : : /* Construct with initializer list. */
169 : 44351 : unsigned r1 = rng.randrange(S::Size());
170 : 44351 : unsigned r2 = rng.randrange(S::Size());
171 [ + - ][ + - ]: 44351 : sim.emplace_back();
[ + - ][ + - ]
[ + - ]
172 [ + - ][ + - ]: 44351 : sim.back().set(r1);
[ + - ][ + - ]
[ + - ]
173 [ + - ][ + - ]: 44351 : sim.back().set(r2);
[ + - ][ + - ]
[ + - ]
174 [ + - ][ + - ]: 284716 : real.push_back(S{r1, r2});
[ + - ][ + - ]
[ + - ]
175 : : break;
176 [ + + + + ]: 2378135 : } else if (dest < sim.size() && command-- == 0) {
[ + + + + ]
[ + + + + ]
177 : : /* Fill() + copy assign. */
178 : 85216 : unsigned len = ReadByte(buffer) % S::Size();
179 : 85216 : compare_fn(dest);
180 : 85216 : sim[dest].reset();
181 [ + + ][ + + ]: 2635116 : for (unsigned i = 0; i < len; ++i) sim[dest][i] = true;
[ + + ]
182 : 85216 : real[dest] = S::Fill(len);
183 : 85216 : break;
184 [ + + + + ]: 2292919 : } else if (src < sim.size() && command-- == 0) {
[ + + + + ]
[ + + + + ]
185 : : /* Iterator copy based compare. */
186 : 107552 : unsigned val = ReadByte(buffer) % S::Size();
187 : : /* In a first loop, compare begin..end, and copy to it_copy at some point. */
188 [ + + ]: 107552 : auto it = real[src].begin(), it_copy = it;
189 [ + + ][ + + ]: 9385072 : for (unsigned i = 0; i < S::Size(); ++i) {
[ + + ]
190 [ + + ][ + + ]: 9277520 : if (i == val) it_copy = it;
[ + + ]
191 [ + + + + ]: 9277520 : bool match = (it != real[src].end()) && *it == i;
[ + + + + ]
[ + + + + ]
192 [ - + ][ - + ]: 9277520 : assert(match == sim[src][i]);
[ - + ]
193 [ + + ][ + + ]: 9277520 : if (match) ++it;
[ + + ]
194 : : }
195 [ - + ][ - + ]: 107552 : assert(it == real[src].end());
[ - + ]
196 : : /* Then compare from the copied point again to end. */
197 [ + + ][ + + ]: 4087571 : for (unsigned i = val; i < S::Size(); ++i) {
[ + + ]
198 [ + + + + ]: 3980019 : bool match = (it_copy != real[src].end()) && *it_copy == i;
[ + + + + ]
[ + + + + ]
199 [ - + ][ - + ]: 3980019 : assert(match == sim[src][i]);
[ - + ]
200 [ + + ][ + + ]: 3980019 : if (match) ++it_copy;
[ + + ]
201 : : }
202 [ - + ][ - + ]: 107552 : assert(it_copy == real[src].end());
[ - + ][ - + ]
[ - + ]
203 : : break;
204 [ + + + - : 2185367 : } else if (src < sim.size() && dest < sim.size() && command-- == 0) {
+ + ][ + +
+ - + + ]
[ + + + -
+ + ]
205 : : /* operator|= */
206 : 37208 : compare_fn(dest);
207 : 37208 : sim[dest] |= sim[src];
208 : 37208 : real[dest] |= real[src];
209 : : break;
210 [ + + + - : 2148159 : } else if (src < sim.size() && dest < sim.size() && command-- == 0) {
+ + ][ + +
+ - + + ]
[ + + + -
+ + ][ + +
+ - + + ]
211 : : /* operator&= */
212 : 31876 : compare_fn(dest);
213 : 31876 : sim[dest] &= sim[src];
214 : 31876 : real[dest] &= real[src];
215 : : break;
216 [ + + + - : 2116283 : } else if (src < sim.size() && dest < sim.size() && command-- == 0) {
+ + ][ + +
+ - + + ]
[ + + + -
+ + ][ + +
+ - + + ]
217 : : /* operator-= */
218 : 30012 : compare_fn(dest);
219 : 30012 : sim[dest] &= ~sim[src];
220 : 30012 : real[dest] -= real[src];
221 : 24237 : break;
222 [ + + + - : 2086271 : } else if (src < sim.size() && dest < sim.size() && command-- == 0) {
+ + ][ + +
+ - + + ]
[ + + + -
+ + ][ + +
+ - + + ]
223 : : /* operator^= */
224 : 23816 : compare_fn(dest);
225 : 23816 : sim[dest] ^= sim[src];
226 : 1006852 : real[dest] ^= real[src];
227 : : break;
228 [ + + + - : 2062455 : } else if (src < sim.size() && dest < sim.size() && aux < sim.size() && command-- == 0) {
+ - + + ]
[ + + + -
+ - + + ]
[ + + + -
+ - + + ]
[ + + + -
+ - + + ]
229 : : /* operator| */
230 : 25707 : compare_fn(dest);
231 : 29489 : sim[dest] = sim[src] | sim[aux];
232 : 29489 : real[dest] = real[src] | real[aux];
233 : 25707 : break;
234 [ + + + - : 2036748 : } else if (src < sim.size() && dest < sim.size() && aux < sim.size() && command-- == 0) {
+ - + + ]
[ + + + -
+ - + + ]
[ + + + -
+ - + + ]
[ + + + -
+ - + + ]
[ + + + -
+ - + + ]
235 : : /* operator& */
236 : 28606 : compare_fn(dest);
237 : 33620 : sim[dest] = sim[src] & sim[aux];
238 : 33620 : real[dest] = real[src] & real[aux];
239 : 28606 : break;
240 [ + + + - : 2008142 : } else if (src < sim.size() && dest < sim.size() && aux < sim.size() && command-- == 0) {
+ - + + ]
[ + + + -
+ - + + ]
[ + + + -
+ - + + ]
[ + + + -
+ - + + ]
[ + + + -
+ - + + ]
241 : : /* operator- */
242 : 28309 : compare_fn(dest);
243 : 33233 : sim[dest] = sim[src] & ~sim[aux];
244 : 28309 : real[dest] = real[src] - real[aux];
245 : 28309 : break;
246 [ + + + - : 1979833 : } else if (src < sim.size() && dest < sim.size() && aux < sim.size() && command-- == 0) {
+ - + + ]
[ + + + -
+ - + + ]
[ + + + -
+ - + + ]
[ + + + -
+ - + + ]
[ + + + -
+ - + + ]
247 : : /* operator^ */
248 : 23745 : compare_fn(dest);
249 : 27507 : sim[dest] = sim[src] ^ sim[aux];
250 : 27507 : real[dest] = real[src] ^ real[aux];
251 : 23745 : break;
252 [ + + + - : 1956088 : } else if (src < sim.size() && aux < sim.size() && command-- == 0) {
+ + ][ + +
+ - + + ]
[ + + + -
+ + ][ + +
+ - + + ]
[ + + + -
+ + ]
253 : : /* IsSupersetOf() and IsSubsetOf() */
254 [ + + ][ - + ]: 136647 : bool is_superset = (sim[aux] & ~sim[src]).none();
255 [ + + ]: 136214 : bool is_subset = (sim[src] & ~sim[aux]).none();
256 [ - + ][ - + ]: 177597 : assert(real[src].IsSupersetOf(real[aux]) == is_superset);
[ - + ][ - + ]
[ - + ]
257 [ - + ][ - + ]: 97390 : assert(real[src].IsSubsetOf(real[aux]) == is_subset);
[ - + ][ - + ]
[ - + ]
258 [ - + ][ - + ]: 80207 : assert(real[aux].IsSupersetOf(real[src]) == is_subset);
[ - + ][ - + ]
259 [ - + ][ - + ]: 80207 : assert(real[aux].IsSubsetOf(real[src]) == is_superset);
[ - + ][ - + ]
260 : : break;
261 [ + + + - : 1858698 : } else if (src < sim.size() && aux < sim.size() && command-- == 0) {
+ + ][ + +
+ - + + ]
[ + + + -
+ + ][ + +
+ - + + ]
[ + + + -
+ + ]
262 : : /* operator== and operator!= */
263 [ - + ][ - + ]: 36802 : assert((sim[src] == sim[aux]) == (real[src] == real[aux]));
[ - + ][ - + ]
[ + + - + ]
264 [ - + ][ - + ]: 34138 : assert((sim[src] != sim[aux]) == (real[src] != real[aux]));
[ - + ][ - + ]
[ - + ]
265 : : break;
266 [ + + + - : 3037960 : } else if (src < sim.size() && aux < sim.size() && command-- == 0) {
+ + + + ]
[ + + + -
+ + + + ]
[ + + + -
+ + + + ]
[ + + + -
+ + + + ]
[ + + + -
+ + + + ]
267 : : /* Overlaps() */
268 [ - + ][ - + ]: 171604 : assert((sim[src] & sim[aux]).any() == real[src].Overlaps(real[aux]));
[ - + ][ - + ]
[ + + - + ]
269 [ - + ][ - + ]: 171604 : assert((sim[src] & sim[aux]).any() == real[aux].Overlaps(real[src]));
[ - + ][ - + ]
[ + + - + ]
270 : : break;
271 : : }
272 : : }
273 : : }
274 : : /* Fully compare the final state. */
275 [ - + + + ]: 15401 : for (unsigned i = 0; i < sim.size(); ++i) {
[ - + + + ]
[ - + + + ]
[ - + + + ]
[ - + + + ]
276 : 11396 : compare_fn(i);
277 : : }
278 : 4005 : }
279 : :
280 : : } // namespace
281 : :
282 [ + - ]: 2740 : FUZZ_TARGET(bitset)
283 : : {
284 : 2266 : unsigned typdat = ReadByte(buffer) % 8;
285 [ + + ]: 2266 : if (typdat == 0) {
286 : : /* 16 bits */
287 : 240 : TestType<bitset_detail::IntBitSet<uint16_t>>(buffer);
288 : 240 : TestType<bitset_detail::MultiIntBitSet<uint16_t, 1>>(buffer);
289 [ + + ]: 2026 : } else if (typdat == 1) {
290 : : /* 32 bits */
291 : 274 : TestType<bitset_detail::MultiIntBitSet<uint16_t, 2>>(buffer);
292 : 274 : TestType<bitset_detail::IntBitSet<uint32_t>>(buffer);
293 [ + + ]: 1752 : } else if (typdat == 2) {
294 : : /* 48 bits */
295 : 281 : TestType<bitset_detail::MultiIntBitSet<uint16_t, 3>>(buffer);
296 [ + + ]: 1471 : } else if (typdat == 3) {
297 : : /* 64 bits */
298 : 305 : TestType<bitset_detail::IntBitSet<uint64_t>>(buffer);
299 : 305 : TestType<bitset_detail::MultiIntBitSet<uint64_t, 1>>(buffer);
300 : 305 : TestType<bitset_detail::MultiIntBitSet<uint32_t, 2>>(buffer);
301 : 305 : TestType<bitset_detail::MultiIntBitSet<uint16_t, 4>>(buffer);
302 [ + + ]: 1166 : } else if (typdat == 4) {
303 : : /* 96 bits */
304 : 265 : TestType<bitset_detail::MultiIntBitSet<uint32_t, 3>>(buffer);
305 [ + + ]: 901 : } else if (typdat == 5) {
306 : : /* 128 bits */
307 : 310 : TestType<bitset_detail::MultiIntBitSet<uint64_t, 2>>(buffer);
308 : 310 : TestType<bitset_detail::MultiIntBitSet<uint32_t, 4>>(buffer);
309 [ + + ]: 591 : } else if (typdat == 6) {
310 : : /* 192 bits */
311 : 295 : TestType<bitset_detail::MultiIntBitSet<uint64_t, 3>>(buffer);
312 [ + - ]: 296 : } else if (typdat == 7) {
313 : : /* 256 bits */
314 : 296 : TestType<bitset_detail::MultiIntBitSet<uint64_t, 4>>(buffer);
315 : : }
316 : 2266 : }
|
