Bitcoin Core  22.99.0
P2P Digital Currency
golombrice.h
Go to the documentation of this file.
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 {
17  // Write quotient as unary-encoded: q 1's followed by one 0.
18  uint64_t q = x >> P;
19  while (q > 0) {
20  int nbits = q <= 64 ? static_cast<int>(q) : 64;
21  bitwriter.Write(~0ULL, nbits);
22  q -= nbits;
23  }
24  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  bitwriter.Write(x, P);
29 }
30 
31 template <typename IStream>
32 uint64_t GolombRiceDecode(BitStreamReader<IStream>& bitreader, uint8_t P)
33 {
34  // Read unary-encoded quotient: q 1's followed by one 0.
35  uint64_t q = 0;
36  while (bitreader.Read(1) == 1) {
37  ++q;
38  }
39 
40  uint64_t r = bitreader.Read(P);
41 
42  return (q << P) + r;
43 }
44 
45 #endif // BITCOIN_UTIL_GOLOMBRICE_H
BitStreamReader
Definition: streams.h:371
GolombRiceDecode
uint64_t GolombRiceDecode(BitStreamReader< IStream > &bitreader, uint8_t P)
Definition: golombrice.h:32
streams.h
BitStreamWriter
Definition: streams.h:414
BitStreamReader::Read
uint64_t Read(int nbits)
Read the specified number of bits from the stream.
Definition: streams.h:391
BitStreamWriter::Write
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:439
GolombRiceEncode
void GolombRiceEncode(BitStreamWriter< OStream > &bitwriter, uint8_t P, uint64_t x)
Definition: golombrice.h:15
fastrange.h