Inside Bitcoin

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
13namespace {
14
15/** Pop the first byte from a byte-span, and return it. */
16uint8_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. */
25template<typename S>
26void 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];