/bitcoin/src/util/golombrice.h
Line | Count | Source |
1 | | // Copyright (c) 2018-2022 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 | 2.23M | { |
17 | | // Write quotient as unary-encoded: q 1's followed by one 0. |
18 | 2.23M | uint64_t q = x >> P; |
19 | 2.89M | while (q > 0) { Branch (19:12): [True: 656k, False: 2.23M]
|
20 | 656k | int nbits = q <= 64 ? static_cast<int>(q) : 64; Branch (20:21): [True: 656k, False: 0]
|
21 | 656k | bitwriter.Write(~0ULL, nbits); |
22 | 656k | q -= nbits; |
23 | 656k | } |
24 | 2.23M | 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 | 2.23M | bitwriter.Write(x, P); |
29 | 2.23M | } |
30 | | |
31 | | template <typename IStream> |
32 | | uint64_t GolombRiceDecode(BitStreamReader<IStream>& bitreader, uint8_t P) |
33 | 0 | { |
34 | | // Read unary-encoded quotient: q 1's followed by one 0. |
35 | 0 | uint64_t q = 0; |
36 | 0 | while (bitreader.Read(1) == 1) { Branch (36:12): [True: 0, False: 0]
|
37 | 0 | ++q; |
38 | 0 | } |
39 | |
|
40 | 0 | uint64_t r = bitreader.Read(P); |
41 | |
|
42 | 0 | return (q << P) + r; |
43 | 0 | } |
44 | | |
45 | | #endif // BITCOIN_UTIL_GOLOMBRICE_H |