compressed_intvec/
codecs.rs

1//! # Codecs Module
2//!
3//! This module provides implementations of various variable-length codes, such as minimal binary, gamma,
4//! delta, Exp‑Golomb, Zeta, Rice, and their parameterized variants. These codecs facilitate encoding and
5//! decoding unsigned 64-bit integers at the bit level, parameterized by an endianness marker and custom bit
6//! read/write implementations.
7//!
8//! ## Codecs Overview
9//!
10//! Refer to the [`codes`](https://docs.rs/dsi-bitstream/latest/dsi_bitstream/codes/index.html) module of [dsi-bitstream](https://docs.rs/dsi-bitstream) for more information on their implementation.
11
12use std::error::Error;
13
14use dsi_bitstream::prelude::*;
15/// Trait for encoding and decoding values using a variable-length code.
16///
17/// The trait is generic over an endianness type `E` and abstracts over writing/reading
18/// bit-level representations.
19///
20/// # Type Parameters
21///
22/// - `E`: Endianness marker (e.g. big-endian `BE` or little-endian `LE`).
23/// - `W`: A writer capable of writing bits/words in the specified codec.
24///
25/// # Associated Types
26///
27/// - `Params`: The type of extra parameters needed for the codec. For many codecs this is
28///   `()`, but some require additional runtime parameters.
29pub trait Codec<E: Endianness, W: BitWrite<E>> {
30    type Params;
31
32    fn encode(writer: &mut W, value: u64, params: Self::Params) -> Result<usize, Box<dyn Error>>;
33
34    fn decode<R2>(reader: &mut R2, params: Self::Params) -> Result<u64, Box<dyn Error>>
35    where
36        R2: for<'a> GammaRead<E>
37            + DeltaRead<E>
38            + ExpGolombRead<E>
39            + ZetaRead<E>
40            + RiceRead<E>
41            + ZetaReadParam<E>
42            + DeltaReadParam<E>
43            + GammaReadParam<E>
44            + MinimalBinaryRead<E>;
45}
46
47/// MinimalBinaryCodec: uses an upper bound as a runtime parameter.
48///
49/// For more information refer to the [`MinimalBinaryCodec`](https://docs.rs/dsi-bitstream/latest/dsi_bitstream/codes/minimal_binary/index.html) module.
50pub struct MinimalBinaryCodec;
51
52impl<E: Endianness, W: MinimalBinaryWrite<E>> Codec<E, W> for MinimalBinaryCodec {
53    type Params = u64; // The upper bound u > 0
54
55    #[inline(always)]
56    fn encode(writer: &mut W, value: u64, upper_bound: u64) -> Result<usize, Box<dyn Error>> {
57        Ok(writer.write_minimal_binary(value, upper_bound)?)
58    }
59
60    #[inline(always)]
61    fn decode<R: MinimalBinaryRead<E>>(
62        reader: &mut R,
63        upper_bound: u64,
64    ) -> Result<u64, Box<dyn Error>> {
65        Ok(reader.read_minimal_binary(upper_bound)?)
66    }
67}
68
69impl MinimalBinaryCodec {
70    /// Encodes a value using the minimal binary codec with the specified upper bound.
71    #[inline(always)]
72    pub fn encode<E: Endianness, W: MinimalBinaryWrite<E>>(
73        writer: &mut W,
74        value: u64,
75        upper_bound: u64,
76    ) -> Result<usize, Box<dyn Error>> {
77        Ok(writer.write_minimal_binary(value, upper_bound)?)
78    }
79
80    /// Decodes a value using the minimal binary codec with the specified upper bound.
81    #[inline(always)]
82    pub fn decode<E: Endianness, R>(reader: &mut R, upper_bound: u64) -> Result<u64, Box<dyn Error>>
83    where
84        R: MinimalBinaryRead<E>,
85    {
86        Ok(reader.read_minimal_binary(upper_bound)?)
87    }
88}
89
90/// GammaCodec: no extra runtime parameter.
91///
92/// Uses the gamma code for encoding and decoding. For more information refer to the [`Gamma`](https://docs.rs/dsi-bitstream/latest/dsi_bitstream/codes/gamma/index.html) module.
93pub struct GammaCodec;
94
95impl<E: Endianness, W: GammaWrite<E>> Codec<E, W> for GammaCodec {
96    type Params = ();
97
98    #[inline(always)]
99    fn encode(writer: &mut W, value: u64, _params: ()) -> Result<usize, Box<dyn Error>> {
100        Ok(writer.write_gamma(value)?)
101    }
102
103    #[inline(always)]
104    fn decode<R: GammaRead<E>>(reader: &mut R, _params: ()) -> Result<u64, Box<dyn Error>> {
105        Ok(reader.read_gamma()?)
106    }
107}
108
109impl GammaCodec {
110    /// Encodes a value using gamma coding.
111    #[inline(always)]
112    pub fn encode<W: GammaWrite<E>, E: Endianness>(
113        writer: &mut W,
114        value: u64,
115    ) -> Result<usize, Box<dyn Error>> {
116        <Self as Codec<E, W>>::encode(writer, value, ())
117    }
118    /// Decodes a value using gamma coding.
119    #[inline(always)]
120    pub fn decode<E: Endianness, R>(reader: &mut R) -> Result<u64, Box<dyn Error>>
121    where
122        R: GammaRead<E>,
123    {
124        Ok(reader.read_gamma()?)
125    }
126}
127
128/// DeltaCodec: no extra runtime parameter.
129///
130/// Uses the delta code for encoding and decoding. For more information refer to the [`Delta`](https://docs.rs/dsi-bitstream/latest/dsi_bitstream/codes/delta/index.html) module.
131pub struct DeltaCodec;
132
133impl<E: Endianness, W: DeltaWrite<E>> Codec<E, W> for DeltaCodec {
134    type Params = ();
135
136    #[inline(always)]
137    fn encode(writer: &mut W, value: u64, _params: ()) -> Result<usize, Box<dyn Error>> {
138        Ok(writer.write_delta(value)?)
139    }
140
141    #[inline(always)]
142    fn decode<R: DeltaRead<E>>(reader: &mut R, _params: ()) -> Result<u64, Box<dyn Error>> {
143        Ok(reader.read_delta()?)
144    }
145}
146
147impl DeltaCodec {
148    /// Encodes a value using delta coding.
149    #[inline(always)]
150    pub fn encode<E: Endianness, W: DeltaWrite<E>>(
151        writer: &mut W,
152        value: u64,
153    ) -> Result<usize, Box<dyn Error>> {
154        Ok(writer.write_delta(value)?)
155    }
156    /// Decodes a value using delta coding.
157    #[inline(always)]
158    pub fn decode<E: Endianness, R>(reader: &mut R) -> Result<u64, Box<dyn Error>>
159    where
160        R: DeltaRead<E>,
161    {
162        Ok(reader.read_delta()?)
163    }
164}
165
166/// Exp‑Golomb Codec: requires a runtime parameter (e.g. k).
167///
168/// This codec supports the Exp‑Golomb coding scheme which is parameterized by `k`. For more information refer to the [`ExpGolomb`](https://docs.rs/dsi-bitstream/latest/dsi_bitstream/codes/exp_golomb/index.html) module.
169///
170/// Note: When k=1, the Exp‑Golomb code is equivalent to the Gamma code.
171pub struct ExpGolombCodec;
172
173impl<E: Endianness, W: ExpGolombWrite<E>> Codec<E, W> for ExpGolombCodec {
174    type Params = usize;
175
176    #[inline(always)]
177    fn encode(writer: &mut W, value: u64, k: usize) -> Result<usize, Box<dyn Error>> {
178        Ok(writer.write_exp_golomb(value, k)?)
179    }
180
181    #[inline(always)]
182    fn decode<R: ExpGolombRead<E>>(reader: &mut R, k: usize) -> Result<u64, Box<dyn Error>> {
183        Ok(reader.read_exp_golomb(k)?)
184    }
185}
186
187impl ExpGolombCodec {
188    /// Encodes a value using Exp‑Golomb coding with the specified parameter `k`.
189    #[inline(always)]
190    pub fn encode<E: Endianness, W: ExpGolombWrite<E>>(
191        writer: &mut W,
192        value: u64,
193        k: usize,
194    ) -> Result<usize, Box<dyn Error>> {
195        Ok(writer.write_exp_golomb(value, k)?)
196    }
197
198    /// Decodes a value using Exp‑Golomb coding with the specified parameter `k`.
199    #[inline(always)]
200    pub fn decode<E: Endianness, R>(reader: &mut R, k: usize) -> Result<u64, Box<dyn Error>>
201    where
202        R: ExpGolombRead<E>,
203    {
204        Ok(reader.read_exp_golomb(k)?)
205    }
206}
207
208/// ZetaCodec: uses runtime parameter (k) with non‑parametric ζ functions.
209///
210/// The parameter is given as a `u64`. For more information refer to the [`Zeta`](https://docs.rs/dsi-bitstream/latest/dsi_bitstream/codes/zeta/index.html) module.
211pub struct ZetaCodec;
212
213impl<E: Endianness, W: ZetaWrite<E>> Codec<E, W> for ZetaCodec {
214    type Params = u64;
215
216    #[inline(always)]
217    fn encode(writer: &mut W, value: u64, k: u64) -> Result<usize, Box<dyn Error>> {
218        Ok(writer.write_zeta(value, k)?)
219    }
220
221    #[inline(always)]
222    fn decode<R: ZetaRead<E>>(reader: &mut R, k: u64) -> Result<u64, Box<dyn Error>> {
223        Ok(reader.read_zeta(k)?)
224    }
225}
226
227impl ZetaCodec {
228    /// Encodes a value using Zeta coding with parameter `k`.
229    #[inline(always)]
230    pub fn encode<E: Endianness, W: ZetaWrite<E>>(
231        writer: &mut W,
232        value: u64,
233        k: u64,
234    ) -> Result<usize, Box<dyn Error>> {
235        <Self as Codec<E, W>>::encode(writer, value, k)
236    }
237
238    /// Decodes a value using Zeta coding with parameter `k`.
239    #[inline(always)]
240    pub fn decode<E: Endianness, R>(reader: &mut R, k: u64) -> Result<u64, Box<dyn Error>>
241    where
242        R: ZetaRead<E>,
243    {
244        Ok(reader.read_zeta(k)?)
245    }
246}
247
248/// RiceCodec: uses the Rice functions with a runtime parameter (log2_b).
249///
250/// The parameter represents the logarithm base‑2 of the encoding base. For more information refer to the [`Rice`](https://docs.rs/dsi-bitstream/latest/dsi_bitstream/codes/rice/index.html) module.
251pub struct RiceCodec;
252
253impl<E: Endianness, W: RiceWrite<E>> Codec<E, W> for RiceCodec {
254    type Params = usize;
255
256    #[inline(always)]
257    fn encode(writer: &mut W, value: u64, log2_b: usize) -> Result<usize, Box<dyn Error>> {
258        Ok(writer.write_rice(value, log2_b)?)
259    }
260
261    #[inline(always)]
262    fn decode<R: RiceRead<E>>(reader: &mut R, log2_b: usize) -> Result<u64, Box<dyn Error>> {
263        Ok(reader.read_rice(log2_b)?)
264    }
265}
266
267impl RiceCodec {
268    /// Encodes a value using Rice coding with the specified `log2_b` parameter.
269    #[inline(always)]
270    pub fn encode<E: Endianness, W: RiceWrite<E>>(
271        writer: &mut W,
272        value: u64,
273        log2_b: usize,
274    ) -> Result<usize, Box<dyn Error>> {
275        Ok(writer.write_rice(value, log2_b)?)
276    }
277
278    /// Decodes a value using Rice coding with the specified `log2_b` parameter.
279    #[inline(always)]
280    pub fn decode<E: Endianness, R>(reader: &mut R, log2_b: usize) -> Result<u64, Box<dyn Error>>
281    where
282        R: RiceRead<E>,
283    {
284        Ok(reader.read_rice(log2_b)?)
285    }
286}
287
288/// ParamZetaCodec: uses a compile‑time flag for ζ functions.
289///
290/// The compile‑time flag `USE_TABLE` determines whether a lookup table is used. For more information refer to the [`Zeta`](https://docs.rs/dsi-bitstream/latest/dsi_bitstream/codes/zeta/index.html) module.
291pub struct ParamZetaCodec<const USE_TABLE: bool>;
292
293impl<E: Endianness, W: ZetaWriteParam<E>, const USE_TABLE: bool> Codec<E, W>
294    for ParamZetaCodec<USE_TABLE>
295{
296    type Params = ();
297
298    #[inline(always)]
299    fn encode(writer: &mut W, value: u64, _params: ()) -> Result<usize, Box<dyn Error>> {
300        Ok(writer.write_zeta3_param::<USE_TABLE>(value)?)
301    }
302
303    #[inline(always)]
304    fn decode<R: ZetaReadParam<E>>(reader: &mut R, _params: ()) -> Result<u64, Box<dyn Error>> {
305        Ok(reader.read_zeta3_param::<USE_TABLE>()?)
306    }
307}
308
309impl<const USE_TABLE: bool> ParamZetaCodec<USE_TABLE> {
310    /// Encodes a value using the parameterized Zeta codec.
311    #[inline(always)]
312    pub fn encode<E: Endianness, W: ZetaWriteParam<E>>(
313        writer: &mut W,
314        value: u64,
315    ) -> Result<usize, Box<dyn Error>> {
316        Ok(writer.write_zeta3_param::<USE_TABLE>(value)?)
317    }
318    /// Decodes a value using the parameterized Zeta codec.
319    #[inline(always)]
320    pub fn decode<E: Endianness, R>(reader: &mut R) -> Result<u64, Box<dyn Error>>
321    where
322        R: ZetaReadParam<E>,
323    {
324        Ok(reader.read_zeta3_param::<USE_TABLE>()?)
325    }
326}
327
328/// ParamDeltaCodec: uses compile‑time booleans for table usage.
329///
330/// The parameters `USE_DELTA_TABLE` and `USE_GAMMA_TABLE` are compile‑time flags. For more information refer to the [`Delta`](https://docs.rs/dsi-bitstream/latest/dsi_bitstream/codes/delta/index.html) module.
331pub struct ParamDeltaCodec<const USE_DELTA_TABLE: bool, const USE_GAMMA_TABLE: bool>;
332
333impl<
334        E: Endianness,
335        const USE_DELTA_TABLE: bool,
336        const USE_GAMMA_TABLE: bool,
337        W: DeltaWriteParam<E>,
338    > Codec<E, W> for ParamDeltaCodec<USE_DELTA_TABLE, USE_GAMMA_TABLE>
339{
340    type Params = ();
341
342    #[inline(always)]
343    fn encode(writer: &mut W, value: u64, _params: ()) -> Result<usize, Box<dyn Error>> {
344        Ok(writer.write_delta_param::<USE_DELTA_TABLE, USE_GAMMA_TABLE>(value)?)
345    }
346
347    #[inline(always)]
348    fn decode<R: DeltaReadParam<E>>(reader: &mut R, _params: ()) -> Result<u64, Box<dyn Error>> {
349        Ok(reader.read_delta_param::<USE_DELTA_TABLE, USE_GAMMA_TABLE>()?)
350    }
351}
352
353impl<const USE_DELTA_TABLE: bool, const USE_GAMMA_TABLE: bool>
354    ParamDeltaCodec<USE_DELTA_TABLE, USE_GAMMA_TABLE>
355{
356    /// Encodes a value using the parameterized Delta codec.
357    #[inline(always)]
358    pub fn encode<E: Endianness, W: DeltaWriteParam<E>>(
359        writer: &mut W,
360        value: u64,
361    ) -> Result<usize, Box<dyn Error>> {
362        Ok(writer.write_delta_param::<USE_DELTA_TABLE, USE_GAMMA_TABLE>(value)?)
363    }
364    /// Decodes a value using the parameterized Delta codec.
365    #[inline(always)]
366    pub fn decode<E: Endianness, R>(reader: &mut R) -> Result<u64, Box<dyn Error>>
367    where
368        R: DeltaReadParam<E>,
369    {
370        Ok(reader.read_delta_param::<USE_DELTA_TABLE, USE_GAMMA_TABLE>()?)
371    }
372}
373
374/// ParamGammaCodec: uses a compile‑time flag for table usage in gamma coding. For more information refer to the [`Gamma`](https://docs.rs/dsi-bitstream/latest/dsi_bitstream/codes/gamma/index.html) module.
375pub struct ParamGammaCodec<const USE_TABLE: bool>;
376
377impl<E: Endianness, W: GammaWriteParam<E>, const USE_TABLE: bool> Codec<E, W>
378    for ParamGammaCodec<USE_TABLE>
379{
380    type Params = ();
381
382    #[inline(always)]
383    fn encode(writer: &mut W, value: u64, _params: ()) -> Result<usize, Box<dyn Error>> {
384        Ok(writer.write_gamma_param::<USE_TABLE>(value)?)
385    }
386
387    #[inline(always)]
388    fn decode<R: GammaReadParam<E>>(reader: &mut R, _params: ()) -> Result<u64, Box<dyn Error>> {
389        Ok(reader.read_gamma_param::<USE_TABLE>()?)
390    }
391}
392
393impl<const USE_TABLE: bool> ParamGammaCodec<USE_TABLE> {
394    /// Encodes a value using the parameterized Gamma codec.
395    #[inline(always)]
396    pub fn encode<E: Endianness, W: GammaWriteParam<E>>(
397        writer: &mut W,
398        value: u64,
399    ) -> Result<usize, Box<dyn Error>> {
400        Ok(writer.write_gamma_param::<USE_TABLE>(value)?)
401    }
402    /// Decodes a value using the parameterized Gamma codec.
403    #[inline(always)]
404    pub fn decode<E: Endianness, R>(reader: &mut R) -> Result<u64, Box<dyn Error>>
405    where
406        R: GammaReadParam<E>,
407    {
408        Ok(reader.read_gamma_param::<USE_TABLE>()?)
409    }
410}
compressed_intvec/codecs.rs

compressed_intvec/
codecs.rs
