Line data    Source code

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