Branch data     Line data    Source code

       1                 :            : // Copyright (c) 2018-2022 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                 :      17448 : 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                 :      17448 :     uint64_t q = x >> P;
      19         [ +  + ]:      26218 :     while (q > 0) {
      20         [ +  + ]:       8770 :         int nbits = q <= 64 ? static_cast<int>(q) : 64;
      21                 :       8770 :         bitwriter.Write(~0ULL, nbits);
      22                 :       8770 :         q -= nbits;
      23                 :            :     }
      24                 :      17448 :     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                 :      17448 :     bitwriter.Write(x, P);
      29                 :      17448 : }
      30                 :            : 
      31                 :            : template <typename IStream>
      32                 :      37601 : uint64_t GolombRiceDecode(BitStreamReader<IStream>& bitreader, uint8_t P)
      33                 :            : {
      34                 :            :     // Read unary-encoded quotient: q 1's followed by one 0.
      35                 :      37601 :     uint64_t q = 0;
      36         [ +  + ]:     100838 :     while (bitreader.Read(1) == 1) {
      37                 :      63237 :         ++q;
      38                 :            :     }
      39                 :            : 
      40                 :      37601 :     uint64_t r = bitreader.Read(P);
      41                 :            : 
      42                 :      37601 :     return (q << P) + r;
      43                 :            : }
      44                 :            : 
      45                 :            : #endif // BITCOIN_UTIL_GOLOMBRICE_H