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

dsi_bitstream/codes/
delta.rs
