diff options
author | MarcoFalke <falke.marco@gmail.com> | 2020-04-20 15:31:07 -0400 |
---|---|---|
committer | MarcoFalke <falke.marco@gmail.com> | 2020-04-20 15:32:41 -0400 |
commit | c4c3f110eb93243fc8f740070240f50b0008f206 (patch) | |
tree | 31bb431b888dd063d39a2f0a56e8658ae3317234 /src/util | |
parent | 56d2ff8a8fc52676a22163f804a9f1a5415b4b71 (diff) | |
parent | 69749fbe6a95f45eb7a695a5f89be87e55c91fb8 (diff) | |
download | bitcoin-c4c3f110eb93243fc8f740070240f50b0008f206.tar.xz |
Merge #18190: tests: Add fuzzing harness for Golomb-Rice coding (GolombRiceEncode/GolombRiceDecode)
69749fbe6a95f45eb7a695a5f89be87e55c91fb8 tests: Add fuzzing harness for Golomb-Rice coding (GolombRiceEncode/GolombRiceDecode) (practicalswift)
Pull request description:
Add fuzzing harness for Golomb-Rice coding (`GolombRiceEncode`/`GolombRiceDecode`).
Test this PR using:
```
$ make distclean
$ ./autogen.sh
$ CC=clang CXX=clang++ ./configure --enable-fuzz \
--with-sanitizers=address,fuzzer,undefined
$ make
$ src/test/fuzz/golomb_rice
…
```
Top commit has no ACKs.
Tree-SHA512: 1b26512301b8c22ab3b804d9b9e4baf933f26f8c05e462d583863badcec7e694548a34849a0d7c4ff7d58b19f6338b51819976ecf642bc4659b04ef71182d748
Diffstat (limited to 'src/util')
-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 |