diff options
Diffstat (limited to 'src/util/golombrice.h')
-rw-r--r-- | src/util/golombrice.h | 43 |
1 files changed, 43 insertions, 0 deletions
diff --git a/src/util/golombrice.h b/src/util/golombrice.h new file mode 100644 index 0000000000..425e7f6681 --- /dev/null +++ b/src/util/golombrice.h @@ -0,0 +1,43 @@ +// Copyright (c) 2018-2019 The Bitcoin Core developers +// Distributed under the MIT software license, see the accompanying +// file COPYING or http://www.opensource.org/licenses/mit-license.php. + +#ifndef BITCOIN_UTIL_GOLOMBRICE_H +#define BITCOIN_UTIL_GOLOMBRICE_H + +#include <streams.h> + +#include <cstdint> + +template <typename OStream> +void GolombRiceEncode(BitStreamWriter<OStream>& bitwriter, uint8_t P, uint64_t x) +{ + // Write quotient as unary-encoded: q 1's followed by one 0. + uint64_t q = x >> P; + while (q > 0) { + int nbits = q <= 64 ? static_cast<int>(q) : 64; + bitwriter.Write(~0ULL, nbits); + q -= nbits; + } + bitwriter.Write(0, 1); + + // Write the remainder in P bits. Since the remainder is just the bottom + // P bits of x, there is no need to mask first. + bitwriter.Write(x, P); +} + +template <typename IStream> +uint64_t GolombRiceDecode(BitStreamReader<IStream>& bitreader, uint8_t P) +{ + // Read unary-encoded quotient: q 1's followed by one 0. + uint64_t q = 0; + while (bitreader.Read(1) == 1) { + ++q; + } + + uint64_t r = bitreader.Read(P); + + return (q << P) + r; +} + +#endif // BITCOIN_UTIL_GOLOMBRICE_H |