golomb_rice.cpp raw

   1  // Copyright (c) 2020-present 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>
   8  #include <test/fuzz/FuzzedDataProvider.h>
   9  #include <test/fuzz/fuzz.h>
  10  #include <test/fuzz/util.h>
  11  #include <test/util/random.h>
  12  #include <util/bytevectorhash.h>
  13  #include <util/golombrice.h>
  14  
  15  #include <algorithm>
  16  #include <cassert>
  17  #include <cstdint>
  18  #include <iosfwd>
  19  #include <unordered_set>
  20  #include <vector>
  21  
  22  namespace {
  23  
  24  uint64_t HashToRange(const std::vector<uint8_t>& element, const uint64_t f)
  25  {
  26      const uint64_t hash = CSipHasher(0x0706050403020100ULL, 0x0F0E0D0C0B0A0908ULL)
  27                                .Write(element)
  28                                .Finalize();
  29      return FastRange64(hash, f);
  30  }
  31  
  32  std::vector<uint64_t> BuildHashedSet(const std::unordered_set<std::vector<uint8_t>, ByteVectorHash>& elements, const uint64_t f)
  33  {
  34      std::vector<uint64_t> hashed_elements;
  35      hashed_elements.reserve(elements.size());
  36      for (const std::vector<uint8_t>& element : elements) {
  37          hashed_elements.push_back(HashToRange(element, f));
  38      }
  39      std::sort(hashed_elements.begin(), hashed_elements.end());
  40      return hashed_elements;
  41  }
  42  } // namespace
  43  
  44  FUZZ_TARGET(golomb_rice)
  45  {
  46      SeedRandomStateForTest(SeedRand::ZEROS);
  47      FuzzedDataProvider fuzzed_data_provider(buffer.data(), buffer.size());
  48      std::vector<uint8_t> golomb_rice_data;
  49      std::vector<uint64_t> encoded_deltas;
  50      {
  51          std::unordered_set<std::vector<uint8_t>, ByteVectorHash> elements;
  52          const int n = fuzzed_data_provider.ConsumeIntegralInRange<int>(0, 512);
  53          for (int i = 0; i < n; ++i) {
  54              elements.insert(ConsumeRandomLengthByteVector(fuzzed_data_provider, 16));
  55          }
  56          VectorWriter stream{golomb_rice_data, 0};
  57          WriteCompactSize(stream, static_cast<uint32_t>(elements.size()));
  58          BitStreamWriter bitwriter{stream};
  59          if (!elements.empty()) {
  60              uint64_t last_value = 0;
  61              for (const uint64_t value : BuildHashedSet(elements, static_cast<uint64_t>(elements.size()) * static_cast<uint64_t>(BASIC_FILTER_M))) {
  62                  const uint64_t delta = value - last_value;
  63                  encoded_deltas.push_back(delta);
  64                  GolombRiceEncode(bitwriter, BASIC_FILTER_P, delta);
  65                  last_value = value;
  66              }
  67          }
  68          bitwriter.Flush();
  69      }
  70  
  71      std::vector<uint64_t> decoded_deltas;
  72      {
  73          SpanReader stream{golomb_rice_data};
  74          BitStreamReader bitreader{stream};
  75          const uint32_t n = static_cast<uint32_t>(ReadCompactSize(stream));
  76          for (uint32_t i = 0; i < n; ++i) {
  77              decoded_deltas.push_back(GolombRiceDecode(bitreader, BASIC_FILTER_P));
  78          }
  79      }
  80  
  81      assert(encoded_deltas == decoded_deltas);
  82  
  83      {
  84          const std::vector<uint8_t> random_bytes = ConsumeRandomLengthByteVector(fuzzed_data_provider, 1024);
  85          SpanReader stream{random_bytes};
  86          uint32_t n;
  87          try {
  88              n = static_cast<uint32_t>(ReadCompactSize(stream));
  89          } catch (const std::ios_base::failure&) {
  90              return;
  91          }
  92          BitStreamReader bitreader{stream};
  93          for (uint32_t i = 0; i < std::min<uint32_t>(n, 1024); ++i) {
  94              try {
  95                  (void)GolombRiceDecode(bitreader, BASIC_FILTER_P);
  96              } catch (const std::ios_base::failure&) {
  97              }
  98          }
  99      }
 100  }
 101