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