Line data    Source code

       1             : // Copyright (c) 2018-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             : #ifndef BITCOIN_UTIL_GOLOMBRICE_H
       6             : #define BITCOIN_UTIL_GOLOMBRICE_H
       7             : 
       8             : #include <util/fastrange.h>
       9             : 
      10             : #include <streams.h>
      11             : 
      12             : #include <cstdint>
      13             : 
      14             : template <typename OStream>
      15         381 : void GolombRiceEncode(BitStreamWriter<OStream>& bitwriter, uint8_t P, uint64_t x)
      16             : {
      17             :     // Write quotient as unary-encoded: q 1's followed by one 0.
      18         381 :     uint64_t q = x >> P;
      19         507 :     while (q > 0) {
      20         126 :         int nbits = q <= 64 ? static_cast<int>(q) : 64;
      21         126 :         bitwriter.Write(~0ULL, nbits);
      22         126 :         q -= nbits;
      23             :     }
      24         381 :     bitwriter.Write(0, 1);
      25             : 
      26             :     // Write the remainder in P bits. Since the remainder is just the bottom
      27             :     // P bits of x, there is no need to mask first.
      28         381 :     bitwriter.Write(x, P);
      29         381 : }
      30             : 
      31             : template <typename IStream>
      32        9169 : uint64_t GolombRiceDecode(BitStreamReader<IStream>& bitreader, uint8_t P)
      33             : {
      34             :     // Read unary-encoded quotient: q 1's followed by one 0.
      35        9169 :     uint64_t q = 0;
      36       13689 :     while (bitreader.Read(1) == 1) {
      37        4520 :         ++q;
      38             :     }
      39             : 
      40        9169 :     uint64_t r = bitreader.Read(P);
      41             : 
      42        9169 :     return (q << P) + r;
      43             : }
      44             : 
      45             : #endif // BITCOIN_UTIL_GOLOMBRICE_H