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

dsi_bitstream/codes/
delta.rs
