bitset.cpp
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 }