dsi_bitstream/codes/
golomb.rs

1/*
2 * SPDX-FileCopyrightText: 2023 Sebastiano Vigna
3 *
4 * SPDX-License-Identifier: Apache-2.0 OR MIT
5 */
6
7//! Golomb codes.
8//!
9//! Given a modulus *b* ≥ 1, the Golomb code of a natural number *x* is given by
10//! ⌊*x* / *b*⌋ in [unary code] followed by the [minimal binary code] of *x* mod
11//! *b*.
12//!
13//! Let *r* be the root of order *b* of 2: then, the implied distribution of the
14//! Golomb code with modulus *b* is ≈ 1/*rˣ*.
15//!
16//! Note that the Golomb code for *b* = 1 is exactly the unary code.
17//!
18//! For natural numbers distributed with a geometric distribution with base *p*,
19//! the optimal code is a Golomb code with [*b* = ⌈−log(2 − *p*) / log(1 −
20//! *p*)⌉].
21//!
22//! For a faster, less precise alternative, see [Rice codes].
23//!
24//! The supported range is [0 . . 2⁶⁴) for *b* in [1 . . 2⁶⁴), but writing
25//! 2⁶⁴ – 1 when *b* = 1 requires writing the unary code for 2⁶⁴ – 1, which
26//! might not be possible depending on the [`BitWrite`]
27//! implementation (and would require writing 2⁶⁴ bits anyway).
28//!
29//! # References
30//!
31//! Solomon W. Golomb, “[Run-length encodings (Corresp.)]”. IEEE Transactions on
32//! Information Theory, 12(3):399–401, July 1966.
33//!
34//! Robert G. Gallager and David C. Van Voorhis, “[Optimal source codes for
35//! geometrically distributed integer alphabets (Corresp.)]”. IEEE Transactions
36//! on Information Theory, 21(2):228–230, March 1975.
37//!
38//! [unary code]: BitRead::read_unary
39//! [minimal binary code]: super::minimal_binary
40//! [*b* = ⌈−log(2 − *p*) / log(1 − *p*)⌉]: b
41//! [Rice codes]: super::rice
42//! [Run-length encodings (Corresp.)]: https://doi.org/10.1109/TIT.1966.1053907
43//! [Optimal source codes for geometrically distributed integer alphabets (Corresp.)]: https://doi.org/10.1109/TIT.1975.1055357
44
45use super::minimal_binary::{MinimalBinaryRead, MinimalBinaryWrite, len_minimal_binary};
46use crate::traits::*;
47
48/// Returns the length of the Golomb code for `n` with modulus `b`.
49#[must_use]
50#[inline(always)]
51pub const fn len_golomb(n: u64, b: u64) -> usize {
52    (n / b) as usize + 1 + len_minimal_binary(n % b, b)
53}
54
55/// Returns the optimal value of *b* for a geometric distribution of base *p*,
56/// that is, ⌈−log(2 − *p*) / log(1 − *p*)⌉.
57#[must_use]
58#[cfg(feature = "std")]
59pub fn b(p: f64) -> u64 {
60    (-(2.0 - p).ln() / (1.0 - p).ln()).ceil() as u64
61}
62
63/// Trait for reading Golomb codes.
64pub trait GolombRead<E: Endianness>: BitRead<E> + MinimalBinaryRead<E> {
65    #[inline(always)]
66    fn read_golomb(&mut self, b: u64) -> Result<u64, Self::Error> {
67        Ok(self.read_unary()? * b + self.read_minimal_binary(b)?)
68    }
69}
70
71/// Trait for writing Golomb codes.
72pub trait GolombWrite<E: Endianness>: BitWrite<E> + MinimalBinaryWrite<E> {
73    #[inline(always)]
74    fn write_golomb(&mut self, n: u64, b: u64) -> Result<usize, Self::Error> {
75        Ok(self.write_unary(n / b)? + self.write_minimal_binary(n % b, b)?)
76    }
77}
78
79impl<E: Endianness, B: BitRead<E>> GolombRead<E> for B {}
80impl<E: Endianness, B: BitWrite<E>> GolombWrite<E> for B {}
dsi_bitstream/codes/golomb.rs

dsi_bitstream/codes/
golomb.rs
