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>
GolombRiceEncode(BitStreamWriter<OStream> & bitwriter,uint8_t P,uint64_t x)13 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 uint64_t q = x >> P;
17 while (q > 0) {
18 int nbits = q <= 64 ? static_cast<int>(q) : 64;
19 bitwriter.Write(~0ULL, nbits);
20 q -= nbits;
21 }
22 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 bitwriter.Write(x, P);
27 }
28
29 template <typename IStream>
GolombRiceDecode(BitStreamReader<IStream> & bitreader,uint8_t P)30 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 while (bitreader.Read(1) == 1) {
35 ++q;
36 }
37
38 uint64_t r = bitreader.Read(P);
39
40 return (q << P) + r;
41 }
42
43 #endif // BITCOIN_UTIL_GOLOMBRICE_H
44