dsi_bitstream/codes/
rice.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//! Rice codes.
8//!
9//! Rice codes (AKA Golomb−Rice codes) are a form of approximated [Golomb
10//! codes](crate::codes::golomb) in which the parameter *b* is a power of
11//! two. This restriction makes the code less precise in modeling data with a
12//! geometric distribution, but encoding and decoding can be performed without
13//! any integer arithmetic, and thus much more quickly.
14//!
15//! The implied distribution of a Rice code is [the same as that of a Golomb
16//! code with the same parameter](crate::codes::golomb).
17//!
18//! For natural numbers distributed with a geometric distribution with base *p*,
19//! the base-2 logarithm of the optimal *b* is [⌈log₂(ln((√5 + 1)/2) / ln(1 -
20//! *p*))⌉](log2_b).
21//!
22//! # References
23//!
24//! Robert F. Rice, “[Some practical universal noiseless coding
25//! techniques](https://ntrs.nasa.gov/api/citations/19790014634/downloads/19790014634.pdf)”.
26//! Jet Propulsion Laboratory, Pasadena, CA, Tech. Rep. JPL-79-22, JPL-83-17,
27//! and JPL-91-3, March 1979.
28//!
29//! Aaron Kiely. “[Selecting the Golomb parameter in Rice
30//! coding](https://tda.jpl.nasa.gov/progress_report/42-159/159E.pdf)”.
31//! Interplanetary Network Progress report 42-159, Jet Propulsion Laboratory,
32//! 2004.
33
34use crate::traits::*;
35
36/// Returns the length of the Rice code for `n` with parameter `log2_b`.
37#[must_use]
38#[inline(always)]
39pub fn len_rice(n: u64, log2_b: usize) -> usize {
40    (n >> log2_b) as usize + 1 + log2_b
41}
42
43/// Returns the optimal value of log₂*b* for a geometric distribution of base
44/// *p*, that is, ⌈log₂(ln((√5 + 1)/2) / ln(1 - *p*))⌉
45pub fn log2_b(p: f64) -> usize {
46    ((-((5f64.sqrt() + 1.0) / 2.0).ln() / (-p).ln_1p()).log2()).ceil() as usize
47}
48
49/// Trait for reading Rice codes.
50pub trait RiceRead<E: Endianness>: BitRead<E> {
51    #[inline(always)]
52    fn read_rice(&mut self, log2_b: usize) -> Result<u64, Self::Error> {
53        Ok((self.read_unary()? << log2_b) + self.read_bits(log2_b)?)
54    }
55}
56
57/// Trait for writing Rice codes.
58pub trait RiceWrite<E: Endianness>: BitWrite<E> {
59    #[inline(always)]
60    fn write_rice(&mut self, n: u64, log2_b: usize) -> Result<usize, Self::Error> {
61        let mut written_bits = self.write_unary(n >> log2_b)?;
62        #[cfg(feature = "checks")]
63        {
64            // Clean up n in case checks are enabled
65            let n = n & (1_u128 << log2_b).wrapping_sub(1) as u64;
66            written_bits += self.write_bits(n, log2_b)?;
67        }
68        #[cfg(not(feature = "checks"))]
69        {
70            written_bits += self.write_bits(n, log2_b)?;
71        }
72        Ok(written_bits)
73    }
74}
75
76impl<E: Endianness, B: BitRead<E>> RiceRead<E> for B {}
77impl<E: Endianness, B: BitWrite<E>> RiceWrite<E> for B {}
78
79#[cfg(test)]
80#[test]
81fn test_log2_b() {
82    use crate::prelude::golomb::b;
83
84    let mut p = 1.0;
85    for _ in 0..100 {
86        p *= 0.9;
87        let golomb = b(p);
88        if golomb & -(golomb as i64) as u64 == golomb {
89            assert_eq!(golomb, 1 << log2_b(p));
90        }
91    }
92}
dsi_bitstream/codes/rice.rs

dsi_bitstream/codes/
rice.rs
