dsi_bitstream/codes/
gamma.rs

1/*
2 * SPDX-FileCopyrightText: 2023 Tommaso Fontana
3 * SPDX-FileCopyrightText: 2023 Inria
4 * SPDX-FileCopyrightText: 2023 Sebastiano Vigna
5 *
6 * SPDX-License-Identifier: Apache-2.0 OR LGPL-2.1-or-later
7 */
8
9//! Elias γ code.
10//!
11//! The γ code of a natural number *n* is the concatenation of the unary code of
12//! ⌊log₂(*n* + 1)⌋ and of the binary representation of *n* + 1 with the most
13//! significant bit removed.
14//!
15//! The implied distribution of the γ code is ≈ 1/2*x*².
16//!
17//! The `USE_TABLE` parameter enables or disables the use of pre-computed tables
18//! for decoding.
19//!
20//! The supported range is [0 . . 2⁶⁴ – 1).
21//!
22//! # References
23//!
24//! Peter Elias, “[Universal codeword sets and representations of the
25//! integers](https://doi.org/10.1109/TIT.1975.1055349)”. IEEE Transactions on
26//! Information Theory, 21(2):194−203, March 1975.
27
28use super::gamma_tables;
29use crate::traits::*;
30
31/// Returns the length of the γ code for `n`.
32#[must_use]
33#[inline(always)]
34pub fn len_gamma_param<const USE_TABLE: bool>(mut n: u64) -> usize {
35    debug_assert!(n < u64::MAX);
36    if USE_TABLE {
37        if let Some(idx) = gamma_tables::LEN.get(n as usize) {
38            return *idx as usize;
39        }
40    }
41    n += 1;
42    let λ = n.ilog2();
43    2 * λ as usize + 1
44}
45
46/// Returns the length of the γ code for `n` using
47/// a default value for `USE_TABLE`.
48#[inline(always)]
49pub fn len_gamma(n: u64) -> usize {
50    #[cfg(target_arch = "arm")]
51    return len_gamma_param::<false>(n);
52    #[cfg(not(target_arch = "arm"))]
53    return len_gamma_param::<true>(n);
54}
55
56/// Trait for reading γ codes.
57///
58/// This is the trait you should usually pull in scope to read γ codes.
59pub trait GammaRead<E: Endianness>: BitRead<E> {
60    fn read_gamma(&mut self) -> Result<u64, Self::Error>;
61}
62
63/// Parametric trait for reading γ codes.
64///
65/// This trait is is more general than [`GammaRead`], as it makes it possible
66/// to specify how to use tables using const parameters.
67///
68/// We provide an implementation of this trait for [`BitRead`]. An implementation
69/// of [`GammaRead`] using default values is usually provided exploiting the
70/// [`crate::codes::params::ReadParams`] mechanism.
71pub trait GammaReadParam<E: Endianness>: BitRead<E> {
72    fn read_gamma_param<const USE_TABLE: bool>(&mut self) -> Result<u64, Self::Error>;
73}
74
75/// Default, internal non-table based implementation that works
76/// for any endianness.
77#[inline(always)]
78fn default_read_gamma<E: Endianness, B: BitRead<E>>(backend: &mut B) -> Result<u64, B::Error> {
79    let len = backend.read_unary()?;
80    debug_assert!(len < 64);
81    Ok(backend.read_bits(len as usize)? + (1 << len) - 1)
82}
83
84impl<B: BitRead<BE>> GammaReadParam<BE> for B {
85    #[inline(always)]
86    fn read_gamma_param<const USE_TABLE: bool>(&mut self) -> Result<u64, Self::Error> {
87        if USE_TABLE {
88            if let Some((res, _)) = gamma_tables::read_table_be(self) {
89                return Ok(res);
90            }
91        }
92        default_read_gamma(self)
93    }
94}
95
96impl<B: BitRead<LE>> GammaReadParam<LE> for B {
97    #[inline(always)]
98    fn read_gamma_param<const USE_TABLE: bool>(&mut self) -> Result<u64, Self::Error> {
99        if USE_TABLE {
100            if let Some((res, _)) = gamma_tables::read_table_le(self) {
101                return Ok(res);
102            }
103        }
104        default_read_gamma(self)
105    }
106}
107
108/// Trait for writing γ codes.
109///
110/// This is the trait you should usually pull in scope to write γ codes.
111pub trait GammaWrite<E: Endianness>: BitWrite<E> {
112    fn write_gamma(&mut self, n: u64) -> Result<usize, Self::Error>;
113}
114
115/// Parametric trait for writing γ codes.
116///
117/// This trait is is more general than [`GammaWrite`], as it makes it possible
118/// to specify how to use tables using const parameters.
119///
120/// We provide an implementation of this trait for [`BitWrite`]. An implementation
121/// of [`GammaWrite`] using default values is usually provided exploiting the
122/// [`crate::codes::params::WriteParams`] mechanism.
123pub trait GammaWriteParam<E: Endianness>: BitWrite<E> {
124    fn write_gamma_param<const USE_TABLE: bool>(&mut self, n: u64) -> Result<usize, Self::Error>;
125}
126
127impl<B: BitWrite<BE>> GammaWriteParam<BE> for B {
128    #[inline(always)]
129    #[allow(clippy::collapsible_if)]
130    fn write_gamma_param<const USE_TABLE: bool>(&mut self, n: u64) -> Result<usize, Self::Error> {
131        if USE_TABLE {
132            if let Some(len) = gamma_tables::write_table_be(self, n)? {
133                return Ok(len);
134            }
135        }
136        default_write_gamma(self, n)
137    }
138}
139
140impl<B: BitWrite<LE>> GammaWriteParam<LE> for B {
141    #[inline(always)]
142    #[allow(clippy::collapsible_if)]
143    fn write_gamma_param<const USE_TABLE: bool>(&mut self, n: u64) -> Result<usize, Self::Error> {
144        if USE_TABLE {
145            if let Some(len) = gamma_tables::write_table_le(self, n)? {
146                return Ok(len);
147            }
148        }
149        default_write_gamma(self, n)
150    }
151}
152
153/// Default, internal non-table based implementation that works
154/// for any endianness.
155#[inline(always)]
156fn default_write_gamma<E: Endianness, B: BitWrite<E>>(
157    backend: &mut B,
158    mut n: u64,
159) -> Result<usize, B::Error> {
160    debug_assert!(n < u64::MAX);
161    n += 1;
162    let λ = n.ilog2();
163
164    #[cfg(feature = "checks")]
165    {
166        // Clean up n in case checks are enabled
167        n ^= 1 << λ;
168    }
169
170    Ok(backend.write_unary(λ as _)? + backend.write_bits(n, λ as _)?)
171}
dsi_bitstream/codes/gamma.rs

dsi_bitstream/codes/
gamma.rs
