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

dsi_bitstream/codes/
delta.rs
