Bitcoin Core  24.99.0
P2P Digital Currency
golomb_rice.cpp
Go to the documentation of this file.
1 // Copyright (c) 2020-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 <blockfilter.h>
6 #include <serialize.h>
7 #include <streams.h>
9 #include <test/fuzz/fuzz.h>
10 #include <test/fuzz/util.h>
11 #include <util/bytevectorhash.h>
12 #include <util/golombrice.h>
13 
14 #include <algorithm>
15 #include <cassert>
16 #include <cstdint>
17 #include <iosfwd>
18 #include <unordered_set>
19 #include <vector>
20 
21 namespace {
22 
23 uint64_t HashToRange(const std::vector<uint8_t>& element, const uint64_t f)
24 {
25  const uint64_t hash = CSipHasher(0x0706050403020100ULL, 0x0F0E0D0C0B0A0908ULL)
26  .Write(element.data(), element.size())
27  .Finalize();
28  return FastRange64(hash, f);
29 }
30 
31 std::vector<uint64_t> BuildHashedSet(const std::unordered_set<std::vector<uint8_t>, ByteVectorHash>& elements, const uint64_t f)
32 {
33  std::vector<uint64_t> hashed_elements;
34  hashed_elements.reserve(elements.size());
35  for (const std::vector<uint8_t>& element : elements) {
36  hashed_elements.push_back(HashToRange(element, f));
37  }
38  std::sort(hashed_elements.begin(), hashed_elements.end());
39  return hashed_elements;
40 }
41 } // namespace
42 
43 FUZZ_TARGET(golomb_rice)
44 {
45  FuzzedDataProvider fuzzed_data_provider(buffer.data(), buffer.size());
46  std::vector<uint8_t> golomb_rice_data;
47  std::vector<uint64_t> encoded_deltas;
48  {
49  std::unordered_set<std::vector<uint8_t>, ByteVectorHash> elements;
50  const int n = fuzzed_data_provider.ConsumeIntegralInRange<int>(0, 512);
51  for (int i = 0; i < n; ++i) {
52  elements.insert(ConsumeRandomLengthByteVector(fuzzed_data_provider, 16));
53  }
54  CVectorWriter stream(SER_NETWORK, 0, golomb_rice_data, 0);
55  WriteCompactSize(stream, static_cast<uint32_t>(elements.size()));
56  BitStreamWriter<CVectorWriter> bitwriter(stream);
57  if (!elements.empty()) {
58  uint64_t last_value = 0;
59  for (const uint64_t value : BuildHashedSet(elements, static_cast<uint64_t>(elements.size()) * static_cast<uint64_t>(BASIC_FILTER_M))) {
60  const uint64_t delta = value - last_value;
61  encoded_deltas.push_back(delta);
62  GolombRiceEncode(bitwriter, BASIC_FILTER_P, delta);
63  last_value = value;
64  }
65  }
66  bitwriter.Flush();
67  }
68 
69  std::vector<uint64_t> decoded_deltas;
70  {
71  SpanReader stream{SER_NETWORK, 0, golomb_rice_data};
72  BitStreamReader<SpanReader> bitreader{stream};
73  const uint32_t n = static_cast<uint32_t>(ReadCompactSize(stream));
74  for (uint32_t i = 0; i < n; ++i) {
75  decoded_deltas.push_back(GolombRiceDecode(bitreader, BASIC_FILTER_P));
76  }
77  }
78 
79  assert(encoded_deltas == decoded_deltas);
80 
81  {
82  const std::vector<uint8_t> random_bytes = ConsumeRandomLengthByteVector(fuzzed_data_provider, 1024);
83  SpanReader stream{SER_NETWORK, 0, random_bytes};
84  uint32_t n;
85  try {
86  n = static_cast<uint32_t>(ReadCompactSize(stream));
87  } catch (const std::ios_base::failure&) {
88  return;
89  }
90  BitStreamReader<SpanReader> bitreader{stream};
91  for (uint32_t i = 0; i < std::min<uint32_t>(n, 1024); ++i) {
92  try {
93  (void)GolombRiceDecode(bitreader, BASIC_FILTER_P);
94  } catch (const std::ios_base::failure&) {
95  }
96  }
97  }
98 }
constexpr uint8_t BASIC_FILTER_P
Definition: blockfilter.h:86
constexpr uint32_t BASIC_FILTER_M
Definition: blockfilter.h:87
void Flush()
Flush any unwritten bits to the output stream, padding with 0's to the next byte boundary.
Definition: streams.h:456
Implementation of Hash named requirement for types that internally store a byte array.
SipHash-2-4.
Definition: siphash.h:14
uint64_t Finalize() const
Compute the 64-bit SipHash-2-4 of the data written so far.
Definition: siphash.cpp:76
CSipHasher & Write(uint64_t data)
Hash a 64-bit integer worth of data It is treated as if this was the little-endian interpretation of ...
Definition: siphash.cpp:28
T ConsumeIntegralInRange(T min, T max)
Minimal stream for reading from an existing byte array by Span.
Definition: streams.h:135
static uint64_t FastRange64(uint64_t x, uint64_t n)
Fast range reduction with 64-bit input and 64-bit range.
Definition: fastrange.h:25
FUZZ_TARGET(golomb_rice)
Definition: golomb_rice.cpp:43
uint64_t GolombRiceDecode(BitStreamReader< IStream > &bitreader, uint8_t P)
Definition: golombrice.h:32
void GolombRiceEncode(BitStreamWriter< OStream > &bitwriter, uint8_t P, uint64_t x)
Definition: golombrice.h:15
@ SER_NETWORK
Definition: serialize.h:131
uint64_t ReadCompactSize(Stream &is, bool range_check=true)
Decode a CompactSize-encoded variable-length integer.
Definition: serialize.h:275
void WriteCompactSize(CSizeComputer &os, uint64_t nSize)
Definition: serialize.h:1103
std::vector< uint8_t > ConsumeRandomLengthByteVector(FuzzedDataProvider &fuzzed_data_provider, const std::optional< size_t > &max_length=std::nullopt) noexcept
Definition: util.h:110
assert(!tx.IsCoinBase())