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

dsi_bitstream/codes/
gamma.rs
