dsi_bitstream/codes/
golomb.rs

1/*
2 * SPDX-FileCopyrightText: 2023 Sebastiano Vigna
3 *
4 * SPDX-License-Identifier: Apache-2.0 OR LGPL-2.1-or-later
5 */
6
7//! Golomb codes.
8//!
9//! Given a modulo *b* ≥ 1, the Golomb code of a natural number *x* is given by ⌊*x*
10//! / *b*⌋ in [unary code](BitRead::read_unary) followed by the [minimal binary
11//! code](super::minimal_binary) of *x* mod *b*.
12//!
13//! Let *r* be the root of order *b* of 2: then, the implied distribution of the
14//! Golomb code of modulo *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*)⌉](b).
21//!
22//! For a faster, less precise alternative, see [Rice codes](super::rice).
23//!
24//! # References
25//!
26//! Solomon W. Golomb, “[Run-length encodings
27//! (Corresp.)](https://doi.org/10.1109/TIT.1966.1053907)”. IEEE Transactions on
28//! Information Theory, 12(3):399−401, July 1966.
29//!
30//! Robert G. Gallager and David C. Van Voorhis, “[Optimal source codes for
31//! geometrically distributed integer alphabets
32//! (Corresp.)](https://doi.org/10.1109/TIT.1975.1055357)”. IEEE Transactions on
33//! Information Theory, 21(2):228−230, March 1975.
34
35use super::minimal_binary::{len_minimal_binary, MinimalBinaryRead, MinimalBinaryWrite};
36use crate::traits::*;
37
38/// Returns the length of the Golomb code for `n` with modulo `b`.
39#[must_use]
40#[inline(always)]
41pub fn len_golomb(n: u64, b: u64) -> usize {
42    (n / b) as usize + 1 + len_minimal_binary(n % b, b)
43}
44
45/// Returns the optimal value of *b* for a geometric distribution of base *p*,
46/// that is, ⌈−log(2 − *p*) / log(1 − *p*)⌉.
47pub fn b(p: f64) -> u64 {
48    (-(2.0 - p).ln() / (1.0 - p).ln()).ceil() as u64
49}
50
51/// Trait for reading Golomb codes.
52pub trait GolombRead<E: Endianness>: BitRead<E> + MinimalBinaryRead<E> {
53    #[inline(always)]
54    fn read_golomb(&mut self, b: u64) -> Result<u64, Self::Error> {
55        Ok(self.read_unary()? * b + self.read_minimal_binary(b)?)
56    }
57}
58
59/// Trait for writing Golomb codes.
60pub trait GolombWrite<E: Endianness>: BitWrite<E> + MinimalBinaryWrite<E> {
61    #[inline(always)]
62    fn write_golomb(&mut self, n: u64, b: u64) -> Result<usize, Self::Error> {
63        Ok(self.write_unary(n / b)? + self.write_minimal_binary(n % b, b)?)
64    }
65}
66
67impl<E: Endianness, B: BitRead<E>> GolombRead<E> for B {}
68impl<E: Endianness, B: BitWrite<E>> GolombWrite<E> for B {}
dsi_bitstream/codes/golomb.rs

dsi_bitstream/codes/
golomb.rs
