Bitcoin Core  22.99.0
P2P Digital Currency
minisketch.cpp
Go to the documentation of this file.
1 // Copyright (c) 2021 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 <minisketch.h>
8 #include <test/fuzz/fuzz.h>
9 #include <test/fuzz/util.h>
10 #include <util/check.h>
11 
12 #include <map>
13 #include <numeric>
14 
16 
18 {
19  FuzzedDataProvider fuzzed_data_provider{buffer.data(), buffer.size()};
20  const auto capacity{fuzzed_data_provider.ConsumeIntegralInRange<size_t>(1, 200)};
21  Minisketch sketch_a{Assert(MakeMinisketch32(capacity))};
22  Minisketch sketch_b{Assert(MakeMinisketch32(capacity))};
23 
24  // Fill two sets and keep the difference in a map
25  std::map<uint32_t, bool> diff;
26  LIMITED_WHILE(fuzzed_data_provider.ConsumeBool(), 10000)
27  {
28  const auto entry{fuzzed_data_provider.ConsumeIntegralInRange<uint32_t>(1, std::numeric_limits<uint32_t>::max() - 1)};
29  const auto KeepDiff{[&] {
30  bool& mut{diff[entry]};
31  mut = !mut;
32  }};
33  CallOneOf(
34  fuzzed_data_provider,
35  [&] {
36  sketch_a.Add(entry);
37  KeepDiff();
38  },
39  [&] {
40  sketch_b.Add(entry);
41  KeepDiff();
42  },
43  [&] {
44  sketch_a.Add(entry);
45  sketch_b.Add(entry);
46  });
47  }
48  const auto num_diff{std::accumulate(diff.begin(), diff.end(), size_t{0}, [](auto n, const auto& e) { return n + e.second; })};
49 
50  Minisketch sketch_ar{MakeMinisketch32(capacity)};
51  Minisketch sketch_br{MakeMinisketch32(capacity)};
52  sketch_ar.Deserialize(sketch_a.Serialize());
53  sketch_br.Deserialize(sketch_b.Serialize());
54 
55  Minisketch sketch_diff{std::move(fuzzed_data_provider.ConsumeBool() ? sketch_a : sketch_ar)};
56  sketch_diff.Merge(fuzzed_data_provider.ConsumeBool() ? sketch_b : sketch_br);
57 
58  if (capacity >= num_diff) {
59  const auto max_elements{fuzzed_data_provider.ConsumeIntegralInRange<size_t>(num_diff, capacity)};
60  const auto dec{*Assert(sketch_diff.Decode(max_elements))};
61  Assert(dec.size() == num_diff);
62  for (auto d : dec) {
63  Assert(diff.at(d));
64  }
65  }
66 }
minisketchwrapper.h
check.h
util.h
minisketch.h
Assert
#define Assert(val)
Identity function.
Definition: check.h:57
node::MakeMinisketch32
Minisketch MakeMinisketch32(size_t capacity)
Wrapper around Minisketch::Minisketch(32, implementation, capacity).
Definition: minisketchwrapper.cpp:70
CallOneOf
size_t CallOneOf(FuzzedDataProvider &fuzzed_data_provider, Callables... callables)
Definition: util.h:42
FUZZ_TARGET
FUZZ_TARGET(minisketch)
Definition: minisketch.cpp:17
FuzzedDataProvider.h
minisketch
struct minisketch minisketch
Opaque type for decoded sketches.
Definition: minisketch.h:40
LIMITED_WHILE
#define LIMITED_WHILE(condition, limit)
Can be used to limit a theoretically unbounded loop.
Definition: fuzz.h:18
fuzz.h
FuzzedDataProvider
Definition: FuzzedDataProvider.h:31
FuzzedDataProvider::ConsumeIntegralInRange
T ConsumeIntegralInRange(T min, T max)
Definition: FuzzedDataProvider.h:204