Branch data     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                 :            : void GolombRiceEncode(BitStreamWriter<OStream>& bitwriter, uint8_t P, uint64_t x)
#      16                 :       6868 : {
#      17                 :            :     // Write quotient as unary-encoded: q 1's followed by one 0.
#      18                 :       6868 :     uint64_t q = x >> P;
#      19         [ +  + ]:       9200 :     while (q > 0) {
#      20         [ +  - ]:       2332 :         int nbits = q <= 64 ? static_cast<int>(q) : 64;
#      21                 :       2332 :         bitwriter.Write(~0ULL, nbits);
#      22                 :       2332 :         q -= nbits;
#      23                 :       2332 :     }
#      24                 :       6868 :     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                 :       6868 :     bitwriter.Write(x, P);
#      29                 :       6868 : }
#      30                 :            : 
#      31                 :            : template <typename IStream>
#      32                 :            : uint64_t GolombRiceDecode(BitStreamReader<IStream>& bitreader, uint8_t P)
#      33                 :      18909 : {
#      34                 :            :     // Read unary-encoded quotient: q 1's followed by one 0.
#      35                 :      18909 :     uint64_t q = 0;
#      36         [ +  + ]:      28119 :     while (bitreader.Read(1) == 1) {
#      37                 :       9210 :         ++q;
#      38                 :       9210 :     }
#      39                 :            : 
#      40                 :      18909 :     uint64_t r = bitreader.Read(P);
#      41                 :            : 
#      42                 :      18909 :     return (q << P) + r;
#      43                 :      18909 : }
#      44                 :            : 
#      45                 :            : #endif // BITCOIN_UTIL_GOLOMBRICE_H