Bitcoin Core  22.99.0
P2P Digital Currency
golomb_rice.cpp
Go to the documentation of this file.
1 // Copyright (c) 2020 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 uint64_t MapIntoRange(const uint64_t x, const uint64_t n)
23 {
24  const uint64_t x_hi = x >> 32;
25  const uint64_t x_lo = x & 0xFFFFFFFF;
26  const uint64_t n_hi = n >> 32;
27  const uint64_t n_lo = n & 0xFFFFFFFF;
28  const uint64_t ac = x_hi * n_hi;
29  const uint64_t ad = x_hi * n_lo;
30  const uint64_t bc = x_lo * n_hi;
31  const uint64_t bd = x_lo * n_lo;
32  const uint64_t mid34 = (bd >> 32) + (bc & 0xFFFFFFFF) + (ad & 0xFFFFFFFF);
33  const uint64_t upper64 = ac + (bc >> 32) + (ad >> 32) + (mid34 >> 32);
34  return upper64;
35 }
36 
37 uint64_t HashToRange(const std::vector<uint8_t>& element, const uint64_t f)
38 {
39  const uint64_t hash = CSipHasher(0x0706050403020100ULL, 0x0F0E0D0C0B0A0908ULL)
40  .Write(element.data(), element.size())
41  .Finalize();
42  return MapIntoRange(hash, f);
43 }
44 
45 std::vector<uint64_t> BuildHashedSet(const std::unordered_set<std::vector<uint8_t>, ByteVectorHash>& elements, const uint64_t f)
46 {
47  std::vector<uint64_t> hashed_elements;
48  hashed_elements.reserve(elements.size());
49  for (const std::vector<uint8_t>& element : elements) {
50  hashed_elements.push_back(HashToRange(element, f));
51  }
52  std::sort(hashed_elements.begin(), hashed_elements.end());
53  return hashed_elements;
54 }
55 } // namespace
56 
57 FUZZ_TARGET(golomb_rice)
58 {
59  FuzzedDataProvider fuzzed_data_provider(buffer.data(), buffer.size());
60  std::vector<uint8_t> golomb_rice_data;
61  std::vector<uint64_t> encoded_deltas;
62  {
63  std::unordered_set<std::vector<uint8_t>, ByteVectorHash> elements;
64  const int n = fuzzed_data_provider.ConsumeIntegralInRange<int>(0, 512);
65  for (int i = 0; i < n; ++i) {
66  elements.insert(ConsumeRandomLengthByteVector(fuzzed_data_provider, 16));
67  }
68  CVectorWriter stream(SER_NETWORK, 0, golomb_rice_data, 0);
69  WriteCompactSize(stream, static_cast<uint32_t>(elements.size()));
70  BitStreamWriter<CVectorWriter> bitwriter(stream);
71  if (!elements.empty()) {
72  uint64_t last_value = 0;
73  for (const uint64_t value : BuildHashedSet(elements, static_cast<uint64_t>(elements.size()) * static_cast<uint64_t>(BASIC_FILTER_M))) {
74  const uint64_t delta = value - last_value;
75  encoded_deltas.push_back(delta);
76  GolombRiceEncode(bitwriter, BASIC_FILTER_P, delta);
77  last_value = value;
78  }
79  }
80  bitwriter.Flush();
81  }
82 
83  std::vector<uint64_t> decoded_deltas;
84  {
85  VectorReader stream{SER_NETWORK, 0, golomb_rice_data, 0};
86  BitStreamReader<VectorReader> bitreader(stream);
87  const uint32_t n = static_cast<uint32_t>(ReadCompactSize(stream));
88  for (uint32_t i = 0; i < n; ++i) {
89  decoded_deltas.push_back(GolombRiceDecode(bitreader, BASIC_FILTER_P));
90  }
91  }
92 
93  assert(encoded_deltas == decoded_deltas);
94 
95  {
96  const std::vector<uint8_t> random_bytes = ConsumeRandomLengthByteVector(fuzzed_data_provider, 1024);
97  VectorReader stream{SER_NETWORK, 0, random_bytes, 0};
98  uint32_t n;
99  try {
100  n = static_cast<uint32_t>(ReadCompactSize(stream));
101  } catch (const std::ios_base::failure&) {
102  return;
103  }
104  BitStreamReader<VectorReader> bitreader(stream);
105  for (uint32_t i = 0; i < std::min<uint32_t>(n, 1024); ++i) {
106  try {
107  (void)GolombRiceDecode(bitreader, BASIC_FILTER_P);
108  } catch (const std::ios_base::failure&) {
109  }
110  }
111  }
112 }
BitStreamReader
Definition: streams.h:457
assert
assert(!tx.IsCoinBase())
GolombRiceDecode
uint64_t GolombRiceDecode(BitStreamReader< IStream > &bitreader, uint8_t P)
Definition: golombrice.h:30
ByteVectorHash
Implementation of Hash named requirement for types that internally store a byte array.
Definition: bytevectorhash.h:16
BitStreamWriter::Flush
void Flush()
Flush any unwritten bits to the output stream, padding with 0's to the next byte boundary.
Definition: streams.h:545
BASIC_FILTER_M
constexpr uint32_t BASIC_FILTER_M
Definition: blockfilter.h:86
CVectorWriter
Definition: streams.h:72
streams.h
MapIntoRange
static uint64_t MapIntoRange(uint64_t x, uint64_t n)
Definition: blockfilter.cpp:32
util.h
golombrice.h
ReadCompactSize
uint64_t ReadCompactSize(Stream &is, bool range_check=true)
Decode a CompactSize-encoded variable-length integer.
Definition: serialize.h:282
VectorReader
Minimal stream for reading from an existing vector by reference.
Definition: streams.h:133
BitStreamWriter
Definition: streams.h:500
CSipHasher
SipHash-2-4.
Definition: siphash.h:13
CSipHasher::Finalize
uint64_t Finalize() const
Compute the 64-bit SipHash-2-4 of the data written so far.
Definition: siphash.cpp:76
WriteCompactSize
void WriteCompactSize(CSizeComputer &os, uint64_t nSize)
Definition: serialize.h:1074
FuzzedDataProvider.h
ConsumeRandomLengthByteVector
std::vector< uint8_t > ConsumeRandomLengthByteVector(FuzzedDataProvider &fuzzed_data_provider, const std::optional< size_t > &max_length=std::nullopt) noexcept
Definition: util.h:61
GolombRiceEncode
void GolombRiceEncode(BitStreamWriter< OStream > &bitwriter, uint8_t P, uint64_t x)
Definition: golombrice.h:13
FUZZ_TARGET
FUZZ_TARGET(golomb_rice)
Definition: golomb_rice.cpp:57
bytevectorhash.h
fuzz.h
FuzzedDataProvider
Definition: FuzzedDataProvider.h:31
BASIC_FILTER_P
constexpr uint8_t BASIC_FILTER_P
Definition: blockfilter.h:85
serialize.h
SER_NETWORK
@ SER_NETWORK
Definition: serialize.h:138
FuzzedDataProvider::ConsumeIntegralInRange
T ConsumeIntegralInRange(T min, T max)
Definition: FuzzedDataProvider.h:204
CSipHasher::Write
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