scuffle_expgolomb/
lib.rs

1//! A set of helper functions to encode and decode exponential-golomb values.
2//!
3//! This crate extends upon the [`BitReader`] and [`BitWriter`] from the
4//! [`scuffle-bytes-util`][scuffle_bytes_util] crate to provide functionality
5//! for reading and writing Exp-Golomb encoded numbers.
6#![cfg_attr(feature = "docs", doc = "\n\nSee the [changelog][changelog] for a full release history.")]
7#![cfg_attr(feature = "docs", doc = "## Feature flags")]
8#![cfg_attr(feature = "docs", doc = document_features::document_features!())]
9//! ## Usage
10//!
11//! ```rust
12//! # fn test() -> std::io::Result<()> {
13//! use scuffle_expgolomb::{BitReaderExpGolombExt, BitWriterExpGolombExt};
14//! use scuffle_bytes_util::{BitReader, BitWriter};
15//!
16//! let mut bit_writer = BitWriter::default();
17//! bit_writer.write_exp_golomb(0)?;
18//! bit_writer.write_exp_golomb(1)?;
19//! bit_writer.write_exp_golomb(2)?;
20//!
21//! let data: Vec<u8> = bit_writer.finish()?;
22//!
23//! let mut bit_reader = BitReader::new(std::io::Cursor::new(data));
24//!
25//! let result = bit_reader.read_exp_golomb()?;
26//! assert_eq!(result, 0);
27//!
28//! let result = bit_reader.read_exp_golomb()?;
29//! assert_eq!(result, 1);
30//!
31//! let result = bit_reader.read_exp_golomb()?;
32//! assert_eq!(result, 2);
33//! # Ok(())
34//! # }
35//! # test().expect("failed to run test");
36//! ```
37//!
38//! ## License
39//!
40//! This project is licensed under the MIT or Apache-2.0 license.
41//! You can choose between one of them if you use this work.
42//!
43//! `SPDX-License-Identifier: MIT OR Apache-2.0`
44#![cfg_attr(all(coverage_nightly, test), feature(coverage_attribute))]
45#![cfg_attr(docsrs, feature(doc_auto_cfg))]
46#![deny(missing_docs)]
47#![deny(unsafe_code)]
48#![deny(unreachable_pub)]
49
50use std::io;
51
52use scuffle_bytes_util::{BitReader, BitWriter};
53
54/// Extension trait for reading Exp-Golomb encoded numbers from a bit reader
55///
56/// See: <https://en.wikipedia.org/wiki/Exponential-Golomb_coding>
57///
58/// - [`BitReader`]
59pub trait BitReaderExpGolombExt {
60    /// Reads an Exp-Golomb encoded number
61    fn read_exp_golomb(&mut self) -> io::Result<u64>;
62
63    /// Reads a signed Exp-Golomb encoded number
64    fn read_signed_exp_golomb(&mut self) -> io::Result<i64> {
65        let exp_glob = self.read_exp_golomb()?;
66
67        if exp_glob % 2 == 0 {
68            Ok(-((exp_glob / 2) as i64))
69        } else {
70            Ok((exp_glob / 2) as i64 + 1)
71        }
72    }
73}
74
75impl<R: io::Read> BitReaderExpGolombExt for BitReader<R> {
76    fn read_exp_golomb(&mut self) -> io::Result<u64> {
77        let mut leading_zeros = 0;
78        while !self.read_bit()? {
79            leading_zeros += 1;
80        }
81
82        let mut result = 1;
83        for _ in 0..leading_zeros {
84            result <<= 1;
85            result |= self.read_bit()? as u64;
86        }
87
88        Ok(result - 1)
89    }
90}
91
92/// Extension trait for writing Exp-Golomb encoded numbers to a bit writer
93///
94/// See: <https://en.wikipedia.org/wiki/Exponential-Golomb_coding>
95///
96/// - [`BitWriter`]
97pub trait BitWriterExpGolombExt {
98    /// Writes an Exp-Golomb encoded number
99    fn write_exp_golomb(&mut self, input: u64) -> io::Result<()>;
100
101    /// Writes a signed Exp-Golomb encoded number
102    fn write_signed_exp_golomb(&mut self, number: i64) -> io::Result<()> {
103        let number = if number <= 0 {
104            -number as u64 * 2
105        } else {
106            number as u64 * 2 - 1
107        };
108
109        self.write_exp_golomb(number)
110    }
111}
112
113impl<W: io::Write> BitWriterExpGolombExt for BitWriter<W> {
114    fn write_exp_golomb(&mut self, input: u64) -> io::Result<()> {
115        let mut number = input + 1;
116        let mut leading_zeros = 0;
117        while number > 1 {
118            number >>= 1;
119            leading_zeros += 1;
120        }
121
122        for _ in 0..leading_zeros {
123            self.write_bit(false)?;
124        }
125
126        self.write_bits(input + 1, leading_zeros + 1)?;
127
128        Ok(())
129    }
130}
131
132/// Returns the number of bits that a signed Exp-Golomb encoded number would take up.
133///
134/// See: <https://en.wikipedia.org/wiki/Exponential-Golomb_coding>
135pub fn size_of_signed_exp_golomb(number: i64) -> u64 {
136    let number = if number <= 0 {
137        -number as u64 * 2
138    } else {
139        number as u64 * 2 - 1
140    };
141
142    size_of_exp_golomb(number)
143}
144
145/// Returns the number of bits that an Exp-Golomb encoded number would take up.
146///
147/// See: <https://en.wikipedia.org/wiki/Exponential-Golomb_coding>
148pub fn size_of_exp_golomb(number: u64) -> u64 {
149    let mut number = number + 1;
150    let mut leading_zeros = 0;
151    while number > 1 {
152        number >>= 1;
153        leading_zeros += 1;
154    }
155
156    leading_zeros * 2 + 1
157}
158
159#[cfg(test)]
160#[cfg_attr(all(test, coverage_nightly), coverage(off))]
161mod tests {
162    use bytes::Buf;
163    use scuffle_bytes_util::{BitReader, BitWriter};
164
165    use crate::{BitReaderExpGolombExt, BitWriterExpGolombExt, size_of_exp_golomb, size_of_signed_exp_golomb};
166
167    pub(crate) fn get_remaining_bits(reader: &BitReader<std::io::Cursor<Vec<u8>>>) -> usize {
168        let remaining = reader.get_ref().remaining();
169
170        if reader.is_aligned() {
171            remaining * 8
172        } else {
173            remaining * 8 + (8 - reader.bit_pos() as usize)
174        }
175    }
176
177    #[test]
178    fn test_exp_glob_decode() {
179        let mut bit_writer = BitWriter::<Vec<u8>>::default();
180
181        bit_writer.write_bits(0b1, 1).unwrap(); // 0
182        bit_writer.write_bits(0b010, 3).unwrap(); // 1
183        bit_writer.write_bits(0b011, 3).unwrap(); // 2
184        bit_writer.write_bits(0b00100, 5).unwrap(); // 3
185        bit_writer.write_bits(0b00101, 5).unwrap(); // 4
186        bit_writer.write_bits(0b00110, 5).unwrap(); // 5
187        bit_writer.write_bits(0b00111, 5).unwrap(); // 6
188
189        let data = bit_writer.finish().unwrap();
190
191        let mut bit_reader = BitReader::new(std::io::Cursor::new(data));
192
193        let remaining_bits = get_remaining_bits(&bit_reader);
194
195        let result = bit_reader.read_exp_golomb().unwrap();
196        assert_eq!(result, 0);
197        assert_eq!(get_remaining_bits(&bit_reader), remaining_bits - 1);
198
199        let result = bit_reader.read_exp_golomb().unwrap();
200        assert_eq!(result, 1);
201        assert_eq!(get_remaining_bits(&bit_reader), remaining_bits - 4);
202
203        let result = bit_reader.read_exp_golomb().unwrap();
204        assert_eq!(result, 2);
205        assert_eq!(get_remaining_bits(&bit_reader), remaining_bits - 7);
206
207        let result = bit_reader.read_exp_golomb().unwrap();
208        assert_eq!(result, 3);
209        assert_eq!(get_remaining_bits(&bit_reader), remaining_bits - 12);
210
211        let result = bit_reader.read_exp_golomb().unwrap();
212        assert_eq!(result, 4);
213        assert_eq!(get_remaining_bits(&bit_reader), remaining_bits - 17);
214
215        let result = bit_reader.read_exp_golomb().unwrap();
216        assert_eq!(result, 5);
217        assert_eq!(get_remaining_bits(&bit_reader), remaining_bits - 22);
218
219        let result = bit_reader.read_exp_golomb().unwrap();
220        assert_eq!(result, 6);
221        assert_eq!(get_remaining_bits(&bit_reader), remaining_bits - 27);
222    }
223
224    #[test]
225    fn test_signed_exp_glob_decode() {
226        let mut bit_writer = BitWriter::<Vec<u8>>::default();
227
228        bit_writer.write_bits(0b1, 1).unwrap(); // 0
229        bit_writer.write_bits(0b010, 3).unwrap(); // 1
230        bit_writer.write_bits(0b011, 3).unwrap(); // -1
231        bit_writer.write_bits(0b00100, 5).unwrap(); // 2
232        bit_writer.write_bits(0b00101, 5).unwrap(); // -2
233        bit_writer.write_bits(0b00110, 5).unwrap(); // 3
234        bit_writer.write_bits(0b00111, 5).unwrap(); // -3
235
236        let data = bit_writer.finish().unwrap();
237
238        let mut bit_reader = BitReader::new(std::io::Cursor::new(data));
239
240        let remaining_bits = get_remaining_bits(&bit_reader);
241
242        let result = bit_reader.read_signed_exp_golomb().unwrap();
243        assert_eq!(result, 0);
244        assert_eq!(get_remaining_bits(&bit_reader), remaining_bits - 1);
245
246        let result = bit_reader.read_signed_exp_golomb().unwrap();
247        assert_eq!(result, 1);
248        assert_eq!(get_remaining_bits(&bit_reader), remaining_bits - 4);
249
250        let result = bit_reader.read_signed_exp_golomb().unwrap();
251        assert_eq!(result, -1);
252        assert_eq!(get_remaining_bits(&bit_reader), remaining_bits - 7);
253
254        let result = bit_reader.read_signed_exp_golomb().unwrap();
255        assert_eq!(result, 2);
256        assert_eq!(get_remaining_bits(&bit_reader), remaining_bits - 12);
257
258        let result = bit_reader.read_signed_exp_golomb().unwrap();
259        assert_eq!(result, -2);
260        assert_eq!(get_remaining_bits(&bit_reader), remaining_bits - 17);
261
262        let result = bit_reader.read_signed_exp_golomb().unwrap();
263        assert_eq!(result, 3);
264        assert_eq!(get_remaining_bits(&bit_reader), remaining_bits - 22);
265
266        let result = bit_reader.read_signed_exp_golomb().unwrap();
267        assert_eq!(result, -3);
268        assert_eq!(get_remaining_bits(&bit_reader), remaining_bits - 27);
269    }
270
271    #[test]
272    fn test_exp_glob_encode() {
273        let mut bit_writer = BitWriter::<Vec<u8>>::default();
274
275        bit_writer.write_exp_golomb(0).unwrap();
276        bit_writer.write_exp_golomb(1).unwrap();
277        bit_writer.write_exp_golomb(2).unwrap();
278        bit_writer.write_exp_golomb(3).unwrap();
279        bit_writer.write_exp_golomb(4).unwrap();
280        bit_writer.write_exp_golomb(5).unwrap();
281        bit_writer.write_exp_golomb(6).unwrap();
282        bit_writer.write_exp_golomb(u64::MAX - 1).unwrap();
283
284        let data = bit_writer.finish().unwrap();
285
286        let mut bit_reader = BitReader::new(std::io::Cursor::new(data));
287
288        let remaining_bits = get_remaining_bits(&bit_reader);
289
290        let result = bit_reader.read_exp_golomb().unwrap();
291        assert_eq!(result, 0);
292        assert_eq!(get_remaining_bits(&bit_reader), remaining_bits - 1);
293
294        let result = bit_reader.read_exp_golomb().unwrap();
295        assert_eq!(result, 1);
296        assert_eq!(get_remaining_bits(&bit_reader), remaining_bits - 4);
297
298        let result = bit_reader.read_exp_golomb().unwrap();
299        assert_eq!(result, 2);
300        assert_eq!(get_remaining_bits(&bit_reader), remaining_bits - 7);
301
302        let result = bit_reader.read_exp_golomb().unwrap();
303        assert_eq!(result, 3);
304        assert_eq!(get_remaining_bits(&bit_reader), remaining_bits - 12);
305
306        let result = bit_reader.read_exp_golomb().unwrap();
307        assert_eq!(result, 4);
308        assert_eq!(get_remaining_bits(&bit_reader), remaining_bits - 17);
309
310        let result = bit_reader.read_exp_golomb().unwrap();
311        assert_eq!(result, 5);
312        assert_eq!(get_remaining_bits(&bit_reader), remaining_bits - 22);
313
314        let result = bit_reader.read_exp_golomb().unwrap();
315        assert_eq!(result, 6);
316        assert_eq!(get_remaining_bits(&bit_reader), remaining_bits - 27);
317
318        let result = bit_reader.read_exp_golomb().unwrap();
319        assert_eq!(result, u64::MAX - 1);
320        assert_eq!(get_remaining_bits(&bit_reader), remaining_bits - 154);
321    }
322
323    #[test]
324    fn test_signed_exp_glob_encode() {
325        let mut bit_writer = BitWriter::<Vec<u8>>::default();
326
327        bit_writer.write_signed_exp_golomb(0).unwrap();
328        bit_writer.write_signed_exp_golomb(1).unwrap();
329        bit_writer.write_signed_exp_golomb(-1).unwrap();
330        bit_writer.write_signed_exp_golomb(2).unwrap();
331        bit_writer.write_signed_exp_golomb(-2).unwrap();
332        bit_writer.write_signed_exp_golomb(3).unwrap();
333        bit_writer.write_signed_exp_golomb(-3).unwrap();
334        bit_writer.write_signed_exp_golomb(i64::MAX).unwrap();
335
336        let data = bit_writer.finish().unwrap();
337
338        let mut bit_reader = BitReader::new(std::io::Cursor::new(data));
339
340        let remaining_bits = get_remaining_bits(&bit_reader);
341
342        let result = bit_reader.read_signed_exp_golomb().unwrap();
343        assert_eq!(result, 0);
344        assert_eq!(get_remaining_bits(&bit_reader), remaining_bits - 1);
345
346        let result = bit_reader.read_signed_exp_golomb().unwrap();
347        assert_eq!(result, 1);
348        assert_eq!(get_remaining_bits(&bit_reader), remaining_bits - 4);
349
350        let result = bit_reader.read_signed_exp_golomb().unwrap();
351        assert_eq!(result, -1);
352        assert_eq!(get_remaining_bits(&bit_reader), remaining_bits - 7);
353
354        let result = bit_reader.read_signed_exp_golomb().unwrap();
355        assert_eq!(result, 2);
356        assert_eq!(get_remaining_bits(&bit_reader), remaining_bits - 12);
357
358        let result = bit_reader.read_signed_exp_golomb().unwrap();
359        assert_eq!(result, -2);
360        assert_eq!(get_remaining_bits(&bit_reader), remaining_bits - 17);
361
362        let result = bit_reader.read_signed_exp_golomb().unwrap();
363        assert_eq!(result, 3);
364        assert_eq!(get_remaining_bits(&bit_reader), remaining_bits - 22);
365
366        let result = bit_reader.read_signed_exp_golomb().unwrap();
367        assert_eq!(result, -3);
368        assert_eq!(get_remaining_bits(&bit_reader), remaining_bits - 27);
369
370        let result = bit_reader.read_signed_exp_golomb().unwrap();
371        assert_eq!(result, i64::MAX);
372        assert_eq!(get_remaining_bits(&bit_reader), remaining_bits - 154);
373    }
374
375    #[test]
376    fn test_expg_sizes() {
377        assert_eq!(1, size_of_exp_golomb(0)); // 0b1
378        assert_eq!(3, size_of_exp_golomb(1)); // 0b010
379        assert_eq!(3, size_of_exp_golomb(2)); // 0b011
380        assert_eq!(5, size_of_exp_golomb(3)); // 0b00100
381        assert_eq!(5, size_of_exp_golomb(4)); // 0b00101
382        assert_eq!(5, size_of_exp_golomb(5)); // 0b00110
383        assert_eq!(5, size_of_exp_golomb(6)); // 0b00111
384
385        assert_eq!(1, size_of_signed_exp_golomb(0)); // 0b1
386        assert_eq!(3, size_of_signed_exp_golomb(1)); // 0b010
387        assert_eq!(3, size_of_signed_exp_golomb(-1)); // 0b011
388        assert_eq!(5, size_of_signed_exp_golomb(2)); // 0b00100
389        assert_eq!(5, size_of_signed_exp_golomb(-2)); // 0b00101
390        assert_eq!(5, size_of_signed_exp_golomb(3)); // 0b00110
391        assert_eq!(5, size_of_signed_exp_golomb(-3)); // 0b00111
392    }
393}
394
395/// Changelogs generated by [scuffle_changelog]
396#[cfg(feature = "docs")]
397#[scuffle_changelog::changelog]
398pub mod changelog {}
scuffle_expgolomb/lib.rs

scuffle_expgolomb/
lib.rs
