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//! The supported range is [0 . . 2⁶⁴) for *b* in [0 . . 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`](crate::traits::BitWrite)
27//! implementation (and would require writing 2⁶⁴ bits anyway).
28//!
29//! # References
30//!
31//! Solomon W. Golomb, “[Run-length encodings
32//! (Corresp.)](https://doi.org/10.1109/TIT.1966.1053907)”. IEEE Transactions on
33//! Information Theory, 12(3):399−401, July 1966.
34//!
35//! Robert G. Gallager and David C. Van Voorhis, “[Optimal source codes for
36//! geometrically distributed integer alphabets
37//! (Corresp.)](https://doi.org/10.1109/TIT.1975.1055357)”. IEEE Transactions on
38//! Information Theory, 21(2):228−230, March 1975.
39
40use super::minimal_binary::{MinimalBinaryRead, MinimalBinaryWrite, len_minimal_binary};
41use crate::traits::*;
42
43/// Returns the length of the Golomb code for `n` with modulo `b`.
44#[must_use]
45#[inline(always)]
46pub fn len_golomb(n: u64, b: u64) -> usize {
47    (n / b) as usize + 1 + len_minimal_binary(n % b, b)
48}
49
50/// Returns the optimal value of *b* for a geometric distribution of base *p*,
51/// that is, ⌈−log(2 − *p*) / log(1 − *p*)⌉.
52pub fn b(p: f64) -> u64 {
53    (-(2.0 - p).ln() / (1.0 - p).ln()).ceil() as u64
54}
55
56/// Trait for reading Golomb codes.
57pub trait GolombRead<E: Endianness>: BitRead<E> + MinimalBinaryRead<E> {
58    #[inline(always)]
59    fn read_golomb(&mut self, b: u64) -> Result<u64, Self::Error> {
60        Ok(self.read_unary()? * b + self.read_minimal_binary(b)?)
61    }
62}
63
64/// Trait for writing Golomb codes.
65pub trait GolombWrite<E: Endianness>: BitWrite<E> + MinimalBinaryWrite<E> {
66    #[inline(always)]
67    fn write_golomb(&mut self, n: u64, b: u64) -> Result<usize, Self::Error> {
68        Ok(self.write_unary(n / b)? + self.write_minimal_binary(n % b, b)?)
69    }
70}
71
72impl<E: Endianness, B: BitRead<E>> GolombRead<E> for B {}
73impl<E: Endianness, B: BitWrite<E>> GolombWrite<E> for B {}
dsi_bitstream/codes/golomb.rs

dsi_bitstream/codes/
golomb.rs
