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 <streams.h>
#       9                 :            : 
#      10                 :            : #include <cstdint>
#      11                 :            : 
#      12                 :            : template <typename OStream>
#      13                 :            : void GolombRiceEncode(BitStreamWriter<OStream>& bitwriter, uint8_t P, uint64_t x)
#      14                 :       5652 : {
#      15                 :            :     // Write quotient as unary-encoded: q 1's followed by one 0.
#      16                 :       5652 :     uint64_t q = x >> P;
#      17         [ +  + ]:       7532 :     while (q > 0) {
#      18         [ +  - ]:       1880 :         int nbits = q <= 64 ? static_cast<int>(q) : 64;
#      19                 :       1880 :         bitwriter.Write(~0ULL, nbits);
#      20                 :       1880 :         q -= nbits;
#      21                 :       1880 :     }
#      22                 :       5652 :     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                 :       5652 :     bitwriter.Write(x, P);
#      27                 :       5652 : }
#      28                 :            : 
#      29                 :            : template <typename IStream>
#      30                 :            : uint64_t GolombRiceDecode(BitStreamReader<IStream>& bitreader, uint8_t P)
#      31                 :      18849 : {
#      32                 :            :     // Read unary-encoded quotient: q 1's followed by one 0.
#      33                 :      18849 :     uint64_t q = 0;
#      34         [ +  + ]:      27998 :     while (bitreader.Read(1) == 1) {
#      35                 :       9149 :         ++q;
#      36                 :       9149 :     }
#      37                 :            : 
#      38                 :      18849 :     uint64_t r = bitreader.Read(P);
#      39                 :            : 
#      40                 :      18849 :     return (q << P) + r;
#      41                 :      18849 : }
#      42                 :            : 
#      43                 :            : #endif // BITCOIN_UTIL_GOLOMBRICE_H