bitset.cpp raw
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 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
24 /** Perform a simulation fuzz test on BitSet type S. */
25 template<typename S>
26 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 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 }
317