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 <util/bitset.h>
6 : :
7 : : #include <random.h>
8 : : #include <span.h>
9 : : #include <test/fuzz/util.h>
10 : : #include <util/check.h>
11 : :
12 : : #include <bitset>
13 : : #include <vector>
14 : :
15 : : namespace {
16 : :
17 : : /** Pop the first byte from a byte-span, and return it. */
18 : 2000586 : uint8_t ReadByte(FuzzBufferType& buffer)
19 : : {
20 [ + + ]: 2000586 : if (buffer.empty()) return 0;
21 : 1998250 : uint8_t ret = buffer.front();
22 : 1998250 : buffer = buffer.subspan(1);
23 : 1998250 : return ret;
24 : : }
25 : :
26 : : /** Perform a simulation fuzz test on BitSet type S. */
27 : : template<typename S>
28 : 2928 : void TestType(FuzzBufferType buffer)
29 : : {
30 : : /** This fuzz test's design is based on the assumption that the actual bits stored in the
31 : : * bitsets and their simulations do not matter for the purpose of detecting edge cases, thus
32 : : * these are taken from a deterministically-seeded RNG instead. To provide some level of
33 : : * variation however, pick the seed based on the buffer size and size of the chosen bitset. */
34 : 2928 : InsecureRandomContext rng(buffer.size() + 0x10000 * S::Size());
35 : :
36 : : using Sim = std::bitset<S::Size()>;
37 : : // Up to 4 real BitSets (initially 2).
38 : 2928 : std::vector<S> real(2);
39 : : // Up to 4 std::bitsets with the same corresponding contents.
40 [ + - ][ + - ]: 2928 : std::vector<Sim> sim(2);
[ + - ][ + - ]
[ + - ]
41 : :
42 : : /* Compare sim[idx] with real[idx], using all inspector operations. */
43 : 835596 : auto compare_fn = [&](unsigned idx) {
44 : : /* iterators and operator[] */
45 [ + + + + : 416334 : auto it = real[idx].begin();
+ + ]
46 : 416334 : unsigned first = S::Size();
47 : 416334 : unsigned last = S::Size();
48 : 36695742 : for (unsigned i = 0; i < S::Size(); ++i) {
[ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + ]
49 : 36279408 : bool match = (it != real[idx].end()) && *it == i;
[ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + ]
50 : 36279408 : assert(sim[idx][i] == real[idx][i]);
[ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + ]
51 : 36279408 : assert(match == real[idx][i]);
[ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + ]
52 : 36279408 : assert((it == real[idx].end()) != (it != real[idx].end()));
[ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + ]
53 : 36279408 : if (match) {
[ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + ]
54 : 7259876 : ++it;
55 : 7259876 : if (first == S::Size()) first = i;
[ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + ]
56 : : last = i;
57 : : }
58 : : }
59 : 416334 : assert(it == real[idx].end());
[ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + ]
60 [ - + - + : 416334 : assert(!(it != real[idx].end()));
- + ]
61 : : /* Any / None */
62 : 897904 : assert(sim[idx].any() == real[idx].Any());
[ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + ]
63 : 744263 : assert(sim[idx].none() == real[idx].None());
[ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + ]
64 : : /* First / Last */
65 : 416334 : if (sim[idx].any()) {
[ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + +
+ + + + ]
66 : 336904 : assert(first == real[idx].First());
[ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + ]
67 : 336904 : assert(last == real[idx].Last());
[ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + ]
68 : : }
69 : : /* Count */
70 : 569975 : assert(sim[idx].count() == real[idx].Count());
[ - + - +
- + - + -
+ - + - +
- + - + -
+ - + - +
- + - + ]
71 : : };
72 : :
73 [ + + + + ]: 850658 : LIMITED_WHILE (buffer.size() > 0, 1000) {
[ + + + + ]
[ + + + + ]
[ + + + + ]
[ + + + + ]
74 : : // Read one byte to determine which operation to execute on the BitSets.
75 : 847730 : int command = ReadByte(buffer) % 64;
76 : : // Read another byte that determines which bitsets will be involved.
77 : 847730 : unsigned args = ReadByte(buffer);
78 [ - + ]: 847730 : unsigned dest = ((args & 7) * sim.size()) >> 3;
79 : 847730 : unsigned src = (((args >> 3) & 7) * sim.size()) >> 3;
80 : 847730 : unsigned aux = (((args >> 6) & 3) * sim.size()) >> 2;
81 : : // Args are in range for non-empty sim, or sim is completely empty and will be grown
82 : 847730 : assert((sim.empty() && dest == 0 && src == 0 && aux == 0) ||
[ + + - +
+ - + - +
- - + ]
83 : : (!sim.empty() && dest < sim.size() && src < sim.size() && aux < sim.size()));
84 : :
85 : : // Pick one operation based on value of command. Not all operations are always applicable.
86 : : // Loop through the applicable ones until command reaches 0 (which avoids the need to
87 : : // compute the number of applicable commands ahead of time).
88 : : while (true) {
89 [ + + + + ]: 2018766 : if (dest < sim.size() && command-- == 0) {
90 : : /* Set() (true) */
91 : 82487 : unsigned val = ReadByte(buffer) % S::Size();
92 [ - + ]: 82487 : assert(sim[dest][val] == real[dest][val]);
93 [ + - ][ + - ]: 82487 : sim[dest].set(val);
[ + - ][ + - ]
[ + - ]
94 : 82487 : real[dest].Set(val);
95 : 82487 : break;
96 [ + + + + ]: 1936279 : } else if (dest < sim.size() && command-- == 0) {
97 : : /* Reset() */
98 : 26957 : unsigned val = ReadByte(buffer) % S::Size();
99 [ - + ]: 26957 : assert(sim[dest][val] == real[dest][val]);
100 [ + - ][ + - ]: 26957 : sim[dest].reset(val);
[ + - ][ + - ]
[ + - ]
101 : 26957 : real[dest].Reset(val);
102 : 26957 : break;
103 [ + + + + ]: 1909322 : } else if (dest < sim.size() && command-- == 0) {
104 : : /* Set() (conditional) */
105 : 24159 : unsigned val = ReadByte(buffer) % S::Size();
106 [ - + ]: 24159 : assert(sim[dest][val] == real[dest][val]);
107 [ + - ][ + - ]: 24159 : sim[dest].set(val, args >> 7);
[ + - ][ + - ]
[ + - ]
108 : 24159 : real[dest].Set(val, args >> 7);
109 : 24159 : break;
110 [ + + + + ]: 1885163 : } else if (sim.size() < 4 && command-- == 0) {
111 : : /* Construct empty. */
112 [ + - ][ + - ]: 11032 : sim.resize(sim.size() + 1);
[ + - ][ + - ]
[ + - ]
113 [ + - ][ + - ]: 11032 : real.resize(real.size() + 1);
[ + - ][ + - ]
[ + - ]
114 : : break;
115 [ + + + + ]: 1874131 : } else if (sim.size() < 4 && command-- == 0) {
116 : : /* Construct singleton. */
117 : 11361 : unsigned val = ReadByte(buffer) % S::Size();
118 [ + + ]: 13862 : std::bitset<S::Size()> newset;
119 [ + - ][ + - ]: 11361 : newset[val] = true;
[ + - ][ + - ]
[ + - ]
120 [ + - ][ + - ]: 11361 : sim.push_back(newset);
[ + - ][ + - ]
[ + - ]
121 [ + - ][ + - ]: 11361 : real.push_back(S::Singleton(val));
[ + - ][ + - ]
[ + - ]
122 : : break;
123 [ + + + + ]: 1862770 : } else if (dest < sim.size() && command-- == 0) {
[ + + + + ]
124 : : /* Make random. */
125 : 49291 : compare_fn(dest);
126 : 49291 : sim[dest].reset();
127 : 49291 : real[dest] = S{};
128 [ + + ][ + + ]: 4222171 : for (unsigned i = 0; i < S::Size(); ++i) {
[ + + ][ + + ]
[ + + ]
129 [ + + ][ + + ]: 4172880 : if (rng.randbool()) {
130 : 2086884 : sim[dest][i] = true;
131 : 2086884 : real[dest].Set(i);
132 : : }
133 : : }
134 : : break;
135 [ + + + + ]: 1813479 : } else if (dest < sim.size() && command-- == 0) {
[ + + + + ]
136 : : /* Assign initializer list. */
137 : 62152 : unsigned r1 = rng.randrange(S::Size());
138 : 62152 : unsigned r2 = rng.randrange(S::Size());
139 : 62152 : unsigned r3 = rng.randrange(S::Size());
140 : 62152 : compare_fn(dest);
141 : 62152 : sim[dest].reset();
142 : 62152 : real[dest] = {r1, r2, r3};
143 [ + - ][ + - ]: 62152 : sim[dest].set(r1);
[ + - ][ + - ]
[ + - ]
144 [ + - ][ + - ]: 62152 : sim[dest].set(r2);
[ + - ][ + - ]
[ + - ]
145 [ + - ][ + - ]: 62152 : sim[dest].set(r3);
[ + - ][ + - ]
[ + - ]
146 : : break;
147 [ + + + + ]: 1751327 : } else if (!sim.empty() && command-- == 0) {
[ + + + + ]
148 : : /* Destruct. */
149 : 58843 : compare_fn(sim.size() - 1);
150 : 58843 : sim.pop_back();
151 : 58843 : real.pop_back();
152 : : break;
153 [ + + + + : 1692484 : } else if (sim.size() < 4 && src < sim.size() && command-- == 0) {
+ + ][ + +
+ + + + ]
154 : : /* Copy construct. */
155 [ + - ][ + - ]: 10331 : sim.emplace_back(sim[src]);
[ + - ][ + - ]
[ + - ]
156 [ + - ][ + - ]: 10331 : real.emplace_back(real[src]);
[ + - ][ + - ]
[ + - ]
157 : : break;
158 [ + + + - : 1682153 : } else if (src < sim.size() && dest < sim.size() && command-- == 0) {
+ + ][ + +
+ - + + ]
159 : : /* Copy assign. */
160 : 22983 : compare_fn(dest);
161 : 22983 : sim[dest] = sim[src];
162 : 22983 : real[dest] = real[src];
163 : 22983 : break;
164 [ + + + - : 1659170 : } else if (src < sim.size() && dest < sim.size() && command-- == 0) {
+ + ][ + +
+ - + + ]
165 : : /* swap() function. */
166 : 16775 : swap(sim[dest], sim[src]);
167 : 696938 : swap(real[dest], real[src]);
168 : : break;
169 [ + + + + ]: 1642395 : } else if (sim.size() < 4 && command-- == 0) {
[ + + + + ]
[ + + + + ]
170 : : /* Construct with initializer list. */
171 : 28587 : unsigned r1 = rng.randrange(S::Size());
172 : 28587 : unsigned r2 = rng.randrange(S::Size());
173 [ + - ][ + - ]: 28587 : sim.emplace_back();
[ + - ][ + - ]
[ + - ]
174 [ + - ][ + - ]: 28587 : sim.back().set(r1);
[ + - ][ + - ]
[ + - ]
175 [ + - ][ + - ]: 28587 : sim.back().set(r2);
[ + - ][ + - ]
[ + - ]
176 [ + - ][ + - ]: 189700 : real.push_back(S{r1, r2});
[ + - ][ + - ]
[ + - ]
177 : : break;
178 [ + + + + ]: 1613808 : } else if (dest < sim.size() && command-- == 0) {
[ + + + + ]
[ + + + + ]
179 : : /* Fill() + copy assign. */
180 : 57848 : unsigned len = ReadByte(buffer) % S::Size();
181 : 57848 : compare_fn(dest);
182 : 57848 : sim[dest].reset();
183 [ + + ][ + + ]: 1898881 : for (unsigned i = 0; i < len; ++i) sim[dest][i] = true;
[ + + ]
184 : 57848 : real[dest] = S::Fill(len);
185 : 57848 : break;
186 [ + + + + ]: 1555960 : } else if (src < sim.size() && command-- == 0) {
[ + + + + ]
[ + + + + ]
187 : : /* Iterator copy based compare. */
188 : 100660 : unsigned val = ReadByte(buffer) % S::Size();
189 : : /* In a first loop, compare begin..end, and copy to it_copy at some point. */
190 [ + + ]: 100660 : auto it = real[src].begin(), it_copy = it;
191 [ + + ][ + + ]: 9537284 : for (unsigned i = 0; i < S::Size(); ++i) {
[ + + ]
192 [ + + ][ + + ]: 9436624 : if (i == val) it_copy = it;
[ + + ]
193 [ + + + + ]: 9436624 : bool match = (it != real[src].end()) && *it == i;
[ + + + + ]
[ + + + + ]
194 [ - + ][ - + ]: 9436624 : assert(match == sim[src][i]);
[ - + ]
195 [ + + ][ + + ]: 9436624 : if (match) ++it;
[ + + ]
196 : : }
197 [ - + ][ - + ]: 100660 : assert(it == real[src].end());
[ - + ]
198 : : /* Then compare from the copied point again to end. */
199 [ + + ][ + + ]: 4737505 : for (unsigned i = val; i < S::Size(); ++i) {
[ + + ]
200 [ + + + + ]: 4636845 : bool match = (it_copy != real[src].end()) && *it_copy == i;
[ + + + + ]
[ + + + + ]
201 [ - + ][ - + ]: 4636845 : assert(match == sim[src][i]);
[ - + ]
202 [ + + ][ + + ]: 4636845 : if (match) ++it_copy;
[ + + ]
203 : : }
204 [ - + ][ - + ]: 100660 : assert(it_copy == real[src].end());
[ - + ][ - + ]
[ - + ]
205 : : break;
206 [ + + + - : 1455300 : } else if (src < sim.size() && dest < sim.size() && command-- == 0) {
+ + ][ + +
+ - + + ]
[ + + + -
+ + ]
207 : : /* operator|= */
208 : 23198 : compare_fn(dest);
209 : 23198 : sim[dest] |= sim[src];
210 : 23198 : real[dest] |= real[src];
211 : : break;
212 [ + + + - : 1432102 : } else if (src < sim.size() && dest < sim.size() && command-- == 0) {
+ + ][ + +
+ - + + ]
[ + + + -
+ + ][ + +
+ - + + ]
213 : : /* operator&= */
214 : 22598 : compare_fn(dest);
215 : 22598 : sim[dest] &= sim[src];
216 : 22598 : real[dest] &= real[src];
217 : : break;
218 [ + + + - : 1409504 : } else if (src < sim.size() && dest < sim.size() && command-- == 0) {
+ + ][ + +
+ - + + ]
[ + + + -
+ + ][ + +
+ - + + ]
219 : : /* operator-= */
220 : 21056 : compare_fn(dest);
221 : 21056 : sim[dest] &= ~sim[src];
222 : 21056 : real[dest] -= real[src];
223 : 16728 : break;
224 [ + + + - : 1388448 : } else if (src < sim.size() && dest < sim.size() && command-- == 0) {
+ + ][ + +
+ - + + ]
[ + + + -
+ + ][ + +
+ - + + ]
225 : : /* operator^= */
226 : 15271 : compare_fn(dest);
227 : 15271 : sim[dest] ^= sim[src];
228 : 695434 : real[dest] ^= real[src];
229 : : break;
230 [ + + + - : 1373177 : } else if (src < sim.size() && dest < sim.size() && aux < sim.size() && command-- == 0) {
+ - + + ]
[ + + + -
+ - + + ]
[ + + + -
+ - + + ]
[ + + + -
+ - + + ]
231 : : /* operator| */
232 : 19186 : compare_fn(dest);
233 : 22703 : sim[dest] = sim[src] | sim[aux];
234 : 22703 : real[dest] = real[src] | real[aux];
235 : 19186 : break;
236 [ + + + - : 1353991 : } else if (src < sim.size() && dest < sim.size() && aux < sim.size() && command-- == 0) {
+ - + + ]
[ + + + -
+ - + + ]
[ + + + -
+ - + + ]
[ + + + -
+ - + + ]
[ + + + -
+ - + + ]
237 : : /* operator& */
238 : 20845 : compare_fn(dest);
239 : 24833 : sim[dest] = sim[src] & sim[aux];
240 : 24833 : real[dest] = real[src] & real[aux];
241 : 20845 : break;
242 [ + + + - : 1333146 : } else if (src < sim.size() && dest < sim.size() && aux < sim.size() && command-- == 0) {
+ - + + ]
[ + + + -
+ - + + ]
[ + + + -
+ - + + ]
[ + + + -
+ - + + ]
[ + + + -
+ - + + ]
243 : : /* operator- */
244 : 18814 : compare_fn(dest);
245 : 21764 : sim[dest] = sim[src] & ~sim[aux];
246 : 18814 : real[dest] = real[src] - real[aux];
247 : 18814 : break;
248 [ + + + - : 1314332 : } else if (src < sim.size() && dest < sim.size() && aux < sim.size() && command-- == 0) {
+ - + + ]
[ + + + -
+ - + + ]
[ + + + -
+ - + + ]
[ + + + -
+ - + + ]
[ + + + -
+ - + + ]
249 : : /* operator^ */
250 : 15925 : compare_fn(dest);
251 : 18268 : sim[dest] = sim[src] ^ sim[aux];
252 : 18268 : real[dest] = real[src] ^ real[aux];
253 : 15925 : break;
254 [ + + + - : 1298407 : } else if (src < sim.size() && aux < sim.size() && command-- == 0) {
+ + ][ + +
+ - + + ]
[ + + + -
+ + ][ + +
+ - + + ]
[ + + + -
+ + ]
255 : : /* IsSupersetOf() and IsSubsetOf() */
256 [ + + ][ - + ]: 89157 : bool is_superset = (sim[aux] & ~sim[src]).none();
257 [ + + ]: 90561 : bool is_subset = (sim[src] & ~sim[aux]).none();
258 [ - + ][ - + ]: 116071 : assert(real[src].IsSupersetOf(real[aux]) == is_superset);
[ - + ][ - + ]
[ - + ]
259 [ - + ][ - + ]: 63267 : assert(real[src].IsSubsetOf(real[aux]) == is_subset);
[ - + ][ - + ]
[ - + ]
260 [ - + ][ - + ]: 52804 : assert(real[aux].IsSupersetOf(real[src]) == is_subset);
[ - + ][ - + ]
261 [ - + ][ - + ]: 52804 : assert(real[aux].IsSubsetOf(real[src]) == is_superset);
[ - + ][ - + ]
262 : : break;
263 [ + + + - : 1235140 : } else if (src < sim.size() && aux < sim.size() && command-- == 0) {
+ + ][ + +
+ - + + ]
[ + + + -
+ + ][ + +
+ - + + ]
[ + + + -
+ + ]
264 : : /* operator== and operator!= */
265 [ - + ][ - + ]: 25829 : assert((sim[src] == sim[aux]) == (real[src] == real[aux]));
[ - + ][ - + ]
[ + + - + ]
266 [ - + ][ - + ]: 24229 : assert((sim[src] != sim[aux]) == (real[src] != real[aux]));
[ - + ][ - + ]
[ - + ]
267 : : break;
268 [ + + + - : 2034952 : } else if (src < sim.size() && aux < sim.size() && command-- == 0) {
+ + + + ]
[ + + + -
+ + + + ]
[ + + + -
+ + + + ]
[ + + + -
+ + + + ]
[ + + + -
+ + + + ]
269 : : /* Overlaps() */
270 [ - + ][ - + ]: 110300 : assert((sim[src] & sim[aux]).any() == real[src].Overlaps(real[aux]));
[ - + ][ - + ]
[ + + - + ]
271 [ - + ][ - + ]: 110300 : assert((sim[src] & sim[aux]).any() == real[aux].Overlaps(real[src]));
[ - + ][ - + ]
[ + + - + ]
272 : : break;
273 : : }
274 : : }
275 : : }
276 : : /* Fully compare the final state. */
277 [ - + + + ]: 11252 : for (unsigned i = 0; i < sim.size(); ++i) {
[ - + + + ]
[ - + + + ]
[ - + + + ]
[ - + + + ]
278 : 8324 : compare_fn(i);
279 : : }
280 : 2928 : }
281 : :
282 : : } // namespace
283 : :
284 [ + - ]: 2130 : FUZZ_TARGET(bitset)
285 : : {
286 : 1654 : unsigned typdat = ReadByte(buffer) % 8;
287 [ + + ]: 1654 : if (typdat == 0) {
288 : : /* 16 bits */
289 : 182 : TestType<bitset_detail::IntBitSet<uint16_t>>(buffer);
290 : 182 : TestType<bitset_detail::MultiIntBitSet<uint16_t, 1>>(buffer);
291 [ + + ]: 1472 : } else if (typdat == 1) {
292 : : /* 32 bits */
293 : 191 : TestType<bitset_detail::MultiIntBitSet<uint16_t, 2>>(buffer);
294 : 191 : TestType<bitset_detail::IntBitSet<uint32_t>>(buffer);
295 [ + + ]: 1281 : } else if (typdat == 2) {
296 : : /* 48 bits */
297 : 198 : TestType<bitset_detail::MultiIntBitSet<uint16_t, 3>>(buffer);
298 [ + + ]: 1083 : } else if (typdat == 3) {
299 : : /* 64 bits */
300 : 226 : TestType<bitset_detail::IntBitSet<uint64_t>>(buffer);
301 : 226 : TestType<bitset_detail::MultiIntBitSet<uint64_t, 1>>(buffer);
302 : 226 : TestType<bitset_detail::MultiIntBitSet<uint32_t, 2>>(buffer);
303 : 226 : TestType<bitset_detail::MultiIntBitSet<uint16_t, 4>>(buffer);
304 [ + + ]: 857 : } else if (typdat == 4) {
305 : : /* 96 bits */
306 : 196 : TestType<bitset_detail::MultiIntBitSet<uint32_t, 3>>(buffer);
307 [ + + ]: 661 : } else if (typdat == 5) {
308 : : /* 128 bits */
309 : 223 : TestType<bitset_detail::MultiIntBitSet<uint64_t, 2>>(buffer);
310 : 223 : TestType<bitset_detail::MultiIntBitSet<uint32_t, 4>>(buffer);
311 [ + + ]: 438 : } else if (typdat == 6) {
312 : : /* 192 bits */
313 : 213 : TestType<bitset_detail::MultiIntBitSet<uint64_t, 3>>(buffer);
314 [ + - ]: 225 : } else if (typdat == 7) {
315 : : /* 256 bits */
316 : 225 : TestType<bitset_detail::MultiIntBitSet<uint64_t, 4>>(buffer);
317 : : }
318 : 1654 : }
|