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 {
17  FuzzedDataProvider fuzzed_data_provider{buffer.data(), buffer.size()};
18  const auto capacity{fuzzed_data_provider.ConsumeIntegralInRange<size_t>(1, 200)};
19  Minisketch sketch_a{Assert(MakeMinisketch32(capacity))};
20  Minisketch sketch_b{Assert(MakeMinisketch32(capacity))};
21 
22  // Fill two sets and keep the difference in a map
23  std::map<uint32_t, bool> diff;
24  LIMITED_WHILE(fuzzed_data_provider.ConsumeBool(), 10000)
25  {
26  const auto entry{fuzzed_data_provider.ConsumeIntegralInRange<uint32_t>(1, std::numeric_limits<uint32_t>::max() - 1)};
27  const auto KeepDiff{[&] {
28  bool& mut{diff[entry]};
29  mut = !mut;
30  }};
31  CallOneOf(
32  fuzzed_data_provider,
33  [&] {
34  sketch_a.Add(entry);
35  KeepDiff();
36  },
37  [&] {
38  sketch_b.Add(entry);
39  KeepDiff();
40  },
41  [&] {
42  sketch_a.Add(entry);
43  sketch_b.Add(entry);
44  });
45  }
46  const auto num_diff{std::accumulate(diff.begin(), diff.end(), size_t{0}, [](auto n, const auto& e) { return n + e.second; })};
47 
48  Minisketch sketch_ar{MakeMinisketch32(capacity)};
49  Minisketch sketch_br{MakeMinisketch32(capacity)};
50  sketch_ar.Deserialize(sketch_a.Serialize());
51  sketch_br.Deserialize(sketch_b.Serialize());
52 
53  Minisketch sketch_diff{std::move(fuzzed_data_provider.ConsumeBool() ? sketch_a : sketch_ar)};
54  sketch_diff.Merge(fuzzed_data_provider.ConsumeBool() ? sketch_b : sketch_br);
55 
56  if (capacity >= num_diff) {
57  const auto max_elements{fuzzed_data_provider.ConsumeIntegralInRange<size_t>(num_diff, capacity)};
58  const auto dec{*Assert(sketch_diff.Decode(max_elements))};
59  Assert(dec.size() == num_diff);
60  for (auto d : dec) {
61  Assert(diff.at(d));
62  }
63  }
64 }
minisketchwrapper.h
check.h
util.h
minisketch.h
Assert
#define Assert(val)
Identity function.
Definition: check.h:57
CallOneOf
size_t CallOneOf(FuzzedDataProvider &fuzzed_data_provider, Callables... callables)
Definition: util.h:40
FUZZ_TARGET
FUZZ_TARGET(minisketch)
Definition: minisketch.cpp:15
FuzzedDataProvider.h
minisketch
struct minisketch minisketch
Opaque type for decoded sketches.
Definition: minisketch.h:40
MakeMinisketch32
Minisketch MakeMinisketch32(size_t capacity)
Wrapper around Minisketch::Minisketch(32, implementation, capacity).
Definition: minisketchwrapper.cpp:69
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