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

dsi_bitstream/codes/
delta.rs
