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 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//! # Table-Based Optimization
25//!
26//! Like [ω](super::omega) codes, δ codes use a special optimization for partial
27//! decoding. Due to the structure of δ codes (a γ code followed by fixed bits),
28//! when a complete codeword cannot be read from the table, the table may still
29//! provide partial information about the γ prefix that was successfully decoded.
30//! This partial state is used to directly read the remaining fixed bits,
31//! avoiding re-reading the γ prefix.
32//!
33//! # References
34//!
35//! Peter Elias, “[Universal codeword sets and representations of the
36//! integers](https://doi.org/10.1109/TIT.1975.1055349)”. IEEE Transactions on
37//! Information Theory, 21(2):194–203, March 1975.
38
39use super::delta_tables;
40use super::gamma::{GammaReadParam, GammaWriteParam, len_gamma_param};
41use crate::traits::*;
42
43/// Returns the length of the δ code for `n`.
44#[must_use]
45#[inline(always)]
46pub fn len_delta_param<const USE_DELTA_TABLE: bool, const USE_GAMMA_TABLE: bool>(n: u64) -> usize {
47    debug_assert!(n < u64::MAX);
48    if USE_DELTA_TABLE {
49        // We cannot use .get() here because n is a u64
50        if n < delta_tables::LEN.len() as u64 {
51            return delta_tables::LEN[n as usize] as usize;
52        }
53    }
54    let λ = (n + 1).ilog2();
55    λ as usize + len_gamma_param::<USE_GAMMA_TABLE>(λ as _)
56}
57
58/// Returns the length of the δ code for `n` using
59/// a default value for `USE_DELTA_TABLE` and `USE_GAMMA_TABLE`.
60#[must_use]
61#[inline(always)]
62pub fn len_delta(n: u64) -> usize {
63    #[cfg(target_arch = "arm")]
64    return len_delta_param::<false, false>(n);
65    #[cfg(not(target_arch = "arm"))]
66    return len_delta_param::<false, true>(n);
67}
68
69/// Trait for reading δ codes.
70///
71/// This is the trait you should usually pull into scope to read δ codes.
72pub trait DeltaRead<E: Endianness>: BitRead<E> {
73    fn read_delta(&mut self) -> Result<u64, Self::Error>;
74}
75
76/// Parametric trait for reading δ codes.
77///
78/// This trait is more general than [`DeltaRead`], as it makes it possible
79/// to specify how to use tables using const parameters.
80///
81/// We provide an implementation of this trait for [`BitRead`]. An implementation
82/// of [`DeltaRead`] using default values is usually provided exploiting the
83/// [`crate::codes::params::ReadParams`] mechanism.
84pub trait DeltaReadParam<E: Endianness>: GammaReadParam<E> {
85    fn read_delta_param<const USE_DELTA_TABLE: bool, const USE_GAMMA_TABLE: bool>(
86        &mut self,
87    ) -> Result<u64, Self::Error>;
88}
89
90/// Default, internal non-table based implementation that works
91/// for any endianness.
92#[inline(always)]
93fn default_read_delta<E: Endianness, B: GammaReadParam<E>, const USE_GAMMA_TABLE: bool>(
94    backend: &mut B,
95) -> Result<u64, B::Error> {
96    let len = backend.read_gamma_param::<USE_GAMMA_TABLE>()?;
97    debug_assert!(len < 64);
98    Ok(backend.read_bits(len as usize)? + (1 << len) - 1)
99}
100
101impl<B: GammaReadParam<BE>> DeltaReadParam<BE> for B {
102    #[inline(always)]
103    fn read_delta_param<const USE_DELTA_TABLE: bool, const USE_GAMMA_TABLE: bool>(
104        &mut self,
105    ) -> Result<u64, B::Error> {
106        const {
107            if USE_DELTA_TABLE {
108                delta_tables::check_read_table(B::PEEK_BITS)
109            }
110        }
111        if USE_DELTA_TABLE {
112            let (len_with_flag, value_or_gamma) = delta_tables::read_table_be(self);
113            if len_with_flag > 0 {
114                // Complete code - bits already skipped in read_table
115                return Ok(value_or_gamma);
116            } else if len_with_flag < 0 {
117                // Partial code: gamma decoded, need to read fixed part
118                // Bits already skipped in read_table
119                let gamma_len = value_or_gamma;
120                debug_assert!(gamma_len < 64);
121                return Ok(self.read_bits(gamma_len as usize)? + (1 << gamma_len) - 1);
122            }
123            // len_with_flag == 0: no valid decoding, fall through
124        }
125        default_read_delta::<BE, _, USE_GAMMA_TABLE>(self)
126    }
127}
128
129impl<B: GammaReadParam<LE>> DeltaReadParam<LE> for B {
130    #[inline(always)]
131    fn read_delta_param<const USE_DELTA_TABLE: bool, const USE_GAMMA_TABLE: bool>(
132        &mut self,
133    ) -> Result<u64, B::Error> {
134        const {
135            if USE_DELTA_TABLE {
136                delta_tables::check_read_table(B::PEEK_BITS)
137            }
138        }
139        if USE_DELTA_TABLE {
140            let (len_with_flag, value_or_gamma) = delta_tables::read_table_le(self);
141            if len_with_flag > 0 {
142                // Complete code - bits already skipped in read_table
143                return Ok(value_or_gamma);
144            } else if len_with_flag < 0 {
145                // Partial code: gamma decoded, need to read fixed part
146                // Bits already skipped in read_table
147                let gamma_len = value_or_gamma;
148                debug_assert!(gamma_len < 64);
149                return Ok(self.read_bits(gamma_len as usize)? + (1 << gamma_len) - 1);
150            }
151            // len_with_flag == 0: no valid decoding, fall through
152        }
153        default_read_delta::<LE, _, USE_GAMMA_TABLE>(self)
154    }
155}
156
157/// Trait for writing δ codes.
158///
159/// This is the trait you should usually pull into scope to write δ codes.
160pub trait DeltaWrite<E: Endianness>: BitWrite<E> {
161    fn write_delta(&mut self, n: u64) -> Result<usize, Self::Error>;
162}
163
164/// Parametric trait for writing δ codes.
165///
166/// This trait is more general than [`DeltaWrite`], as it makes it possible
167/// to specify how to use tables using const parameters.
168///
169/// We provide an implementation of this trait for [`BitWrite`]. An implementation
170/// of [`DeltaWrite`] using default values is usually provided exploiting the
171/// [`crate::codes::params::WriteParams`] mechanism.
172pub trait DeltaWriteParam<E: Endianness>: GammaWriteParam<E> {
173    fn write_delta_param<const USE_DELTA_TABLE: bool, const USE_GAMMA_TABLE: bool>(
174        &mut self,
175        n: u64,
176    ) -> Result<usize, Self::Error>;
177}
178
179impl<B: GammaWriteParam<BE>> DeltaWriteParam<BE> for B {
180    #[inline(always)]
181    #[allow(clippy::collapsible_if)]
182    fn write_delta_param<const USE_DELTA_TABLE: bool, const USE_GAMMA_TABLE: bool>(
183        &mut self,
184        n: u64,
185    ) -> Result<usize, Self::Error> {
186        if USE_DELTA_TABLE {
187            if let Some(len) = delta_tables::write_table_be(self, n)? {
188                return Ok(len);
189            }
190        }
191        default_write_delta::<BE, _, USE_GAMMA_TABLE>(self, n)
192    }
193}
194
195impl<B: GammaWriteParam<LE>> DeltaWriteParam<LE> for B {
196    #[inline(always)]
197    #[allow(clippy::collapsible_if)]
198    fn write_delta_param<const USE_DELTA_TABLE: bool, const USE_GAMMA_TABLE: bool>(
199        &mut self,
200        n: u64,
201    ) -> Result<usize, Self::Error> {
202        if USE_DELTA_TABLE {
203            if let Some(len) = delta_tables::write_table_le(self, n)? {
204                return Ok(len);
205            }
206        }
207        default_write_delta::<LE, _, USE_GAMMA_TABLE>(self, n)
208    }
209}
210
211/// Default, internal non-table based implementation that works
212/// for any endianness.
213#[inline(always)]
214fn default_write_delta<E: Endianness, B: GammaWriteParam<E>, const USE_GAMMA_TABLE: bool>(
215    backend: &mut B,
216    mut n: u64,
217) -> Result<usize, B::Error> {
218    debug_assert!(n < u64::MAX);
219    n += 1;
220    let λ = n.ilog2();
221
222    #[cfg(feature = "checks")]
223    {
224        // Clean up n in case checks are enabled
225        n ^= 1 << λ;
226    }
227
228    Ok(backend.write_gamma_param::<USE_GAMMA_TABLE>(λ as _)? + backend.write_bits(n, λ as _)?)
229}
dsi_bitstream/codes/delta.rs

dsi_bitstream/codes/
delta.rs
