Bitcoin Core  0.20.99
P2P Digital Currency
golombrice.h
Go to the documentation of this file.
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>
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>
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
void Write(uint64_t data, int nbits)
Write the nbits least significant bits of a 64-bit int to the output stream.
Definition: streams.h:562
uint64_t GolombRiceDecode(BitStreamReader< IStream > &bitreader, uint8_t P)
Definition: golombrice.h:30
uint64_t Read(int nbits)
Read the specified number of bits from the stream.
Definition: streams.h:514
void GolombRiceEncode(BitStreamWriter< OStream > &bitwriter, uint8_t P, uint64_t x)
Definition: golombrice.h:13