dsi_bitstream/codes/
rice.rs

1/*
2 * SPDX-FileCopyrightText: 2023 Sebastiano Vigna
3 *
4 * SPDX-License-Identifier: Apache-2.0 OR MIT
5 */
6
7//! Rice codes.
8//!
9//! Rice codes (AKA Golomb–Rice codes) are a form of approximated [Golomb codes]
10//! in which the parameter *b* is a power of two. This restriction makes the
11//! code less precise in modeling data with a geometric distribution, but
12//! encoding and decoding can be performed without any integer arithmetic, and
13//! 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].
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*))⌉].
21//!
22//! The supported range is [0 . . 2⁶⁴) for log₂(*b*) in [0 . . 64), but writing
23//! 2⁶⁴ – 1 when *b* = 1 requires writing the unary code for 2⁶⁴ – 1, which
24//! might not be possible depending on the [`BitWrite`]
25//! implementation (and would require writing 2⁶⁴ bits anyway).
26//!
27//! # References
28//!
29//! Robert F. Rice, “[Some practical universal noiseless coding techniques]”.
30//! Jet Propulsion Laboratory, Pasadena, CA, Tech. Rep. JPL-79-22, JPL-83-17,
31//! and JPL-91-3, March 1979.
32//!
33//! Aaron Kiely. “[Selecting the Golomb parameter in Rice coding]”.
34//! Interplanetary Network Progress report 42-159, Jet Propulsion Laboratory,
35//! 2004.
36//!
37//! [Golomb codes]: crate::codes::golomb
38//! [the same as that of a Golomb code with the same parameter]: crate::codes::golomb
39//! [⌈log₂(ln((√5 + 1)/2) / ln(1 - *p*))⌉]: log2_b
40//! [Some practical universal noiseless coding techniques]: https://ntrs.nasa.gov/api/citations/19790014634/downloads/19790014634.pdf
41//! [Selecting the Golomb parameter in Rice coding]: https://tda.jpl.nasa.gov/progress_report/42-159/159E.pdf
42
43use crate::traits::*;
44
45/// Returns the length of the Rice code for `n` with parameter `log2_b`.
46#[must_use]
47#[inline(always)]
48pub const fn len_rice(n: u64, log2_b: usize) -> usize {
49    debug_assert!(log2_b < 64);
50    (n >> log2_b) as usize + 1 + log2_b
51}
52
53/// Returns the optimal value of log₂*b* for a geometric distribution of base
54/// *p*, that is, ⌈log₂(ln((√5 + 1)/2) / ln(1 - *p*))⌉
55#[must_use]
56#[cfg(feature = "std")]
57pub fn log2_b(p: f64) -> usize {
58    ((-((5f64.sqrt() + 1.0) / 2.0).ln() / (-p).ln_1p()).log2()).ceil() as usize
59}
60
61/// Trait for reading Rice codes.
62pub trait RiceRead<E: Endianness>: BitRead<E> {
63    #[inline(always)]
64    fn read_rice(&mut self, log2_b: usize) -> Result<u64, Self::Error> {
65        debug_assert!(log2_b < 64);
66        Ok((self.read_unary()? << log2_b) + self.read_bits(log2_b)?)
67    }
68}
69
70/// Trait for writing Rice codes.
71pub trait RiceWrite<E: Endianness>: BitWrite<E> {
72    #[inline(always)]
73    fn write_rice(&mut self, n: u64, log2_b: usize) -> Result<usize, Self::Error> {
74        debug_assert!(log2_b < 64);
75
76        let mut written_bits = self.write_unary(n >> log2_b)?;
77        #[cfg(feature = "checks")]
78        {
79            // Clean up n in case checks are enabled
80            let n = n & (1_u128 << log2_b).wrapping_sub(1) as u64;
81            written_bits += self.write_bits(n, log2_b)?;
82        }
83        #[cfg(not(feature = "checks"))]
84        {
85            written_bits += self.write_bits(n, log2_b)?;
86        }
87        Ok(written_bits)
88    }
89}
90
91impl<E: Endianness, B: BitRead<E>> RiceRead<E> for B {}
92impl<E: Endianness, B: BitWrite<E>> RiceWrite<E> for B {}
93
94#[cfg(test)]
95#[cfg(feature = "std")]
96mod tests {
97    use super::*;
98
99    #[test]
100    fn test_log2_b() {
101        use crate::prelude::golomb::b;
102
103        let mut p = 1.0;
104        for _ in 0..100 {
105            p *= 0.9;
106            let golomb = b(p);
107            if golomb & -(golomb as i64) as u64 == golomb {
108                assert_eq!(golomb, 1 << log2_b(p));
109            }
110        }
111    }
112}
dsi_bitstream/codes/rice.rs

dsi_bitstream/codes/
rice.rs
