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

scuffle_expgolomb/
lib.rs
