Skip to main content

layline_core/num/
expgolomb.rs

1//! Exp-Golomb coding.
2use crate::bits::{BitCodec, BitWriter};
3use crate::{ParseError, WireInt};
4
5/// Unsigned Exp-Golomb, H.264 ยง9.1 `ue(v)`.
6///
7/// A code word is `n` zero bits, a one bit, then `n` value bits. The value is `2^n - 1` plus
8/// those bits. It reads the top of each byte first, so it implements only `BitCodec<true>`.
9///
10/// ```
11/// use layline_core::BitCodec;
12/// use layline_core::num::ExpGolomb;
13///
14/// // H.264 Table 9-1: codeNum 0 is `1`, 1 is `010`, 2 is `011`, 3 is `00100`.
15/// assert_eq!(ExpGolomb::decode(&[0b1000_0000], 0), Ok((ExpGolomb(0), 1)));
16/// assert_eq!(ExpGolomb::decode(&[0b0100_0000], 0), Ok((ExpGolomb(1), 3)));
17/// assert_eq!(ExpGolomb::decode(&[0b0010_0000], 0), Ok((ExpGolomb(3), 5)));
18/// ```
19///
20/// H.264 `se(v)` is `-unzigzag(codeNum)`, using [`zigzag`](super::zigzag) with the sign flipped:
21///
22/// ```
23/// use layline_core::num::{ExpGolomb, unzigzag, zigzag};
24/// use layline_core::{BitCodec, BitWriter, Buffer, Overflow, ParseError};
25///
26/// #[derive(Debug, PartialEq)]
27/// struct Se(i64);
28///
29/// impl BitCodec<true> for Se {
30///     fn decode(bytes: &[u8], at_bit: usize) -> Result<(Self, usize), ParseError> {
31///         let (code, used) = ExpGolomb::decode(bytes, at_bit)?;
32///         Ok((Se(-unzigzag(code.0)), used))
33///     }
34///
35///     fn encode<B: Buffer>(&self, out: &mut BitWriter<'_, B, true>) -> Result<(), Overflow> {
36///         ExpGolomb(zigzag(-self.0)).encode(out)
37///     }
38/// }
39///
40/// // H.264 Table 9-3: code numbers 0, 1, 2 are the values 0, 1, -1.
41/// assert_eq!(Se::decode(&[0b1000_0000], 0), Ok((Se(0), 1)));
42/// assert_eq!(Se::decode(&[0b0100_0000], 0), Ok((Se(1), 3)));
43/// assert_eq!(Se::decode(&[0b0110_0000], 0), Ok((Se(-1), 3)));
44/// ```
45#[derive(Debug, Clone, Copy, Default, PartialEq, Eq, PartialOrd, Ord, Hash)]
46pub struct ExpGolomb(pub u64);
47
48impl From<u64> for ExpGolomb {
49    fn from(v: u64) -> Self {
50        Self(v)
51    }
52}
53
54impl From<ExpGolomb> for u64 {
55    fn from(v: ExpGolomb) -> Self {
56        v.0
57    }
58}
59
60impl ExpGolomb {
61    /// The number of leading zero bits, and the bits after the one bit.
62    const fn split(self) -> (u32, u64) {
63        if self.0 == u64::MAX {
64            return (64, 0);
65        }
66        let zeros = (self.0 + 1).ilog2();
67        (zeros, self.0 + 1 - (1u64 << zeros))
68    }
69}
70
71impl BitCodec<true> for ExpGolomb {
72    fn decode(bytes: &[u8], at_bit: usize) -> Result<(Self, usize), ParseError> {
73        let mut r = crate::BitReader::<true>::at(bytes, at_bit);
74        let mut zeros = 0u32;
75        while !r.bit()? {
76            zeros += 1;
77            if zeros > 64 {
78                return Err(ParseError::Malformed { field: "ExpGolomb", at: at_bit / 8 });
79            }
80        }
81        let suffix = if zeros == 0 { 0 } else { r.read(zeros)? };
82        let base = crate::mask::mask64(zeros);
83        let value = base
84            .checked_add(suffix)
85            .ok_or(ParseError::Malformed { field: "ExpGolomb", at: at_bit / 8 })?;
86        Ok((Self(value), r.position() - at_bit))
87    }
88
89    fn encode<B: crate::Buffer>(
90        &self,
91        out: &mut BitWriter<'_, B, true>,
92    ) -> Result<(), crate::Overflow> {
93        let (zeros, suffix) = self.split();
94        out.write(0, zeros)?;
95        out.bit(true)?;
96        out.write(suffix, zeros)
97    }
98}
99
100impl WireInt for ExpGolomb {
101    fn to_i64(&self) -> i64 {
102        self.0.to_i64()
103    }
104
105    fn from_i64(n: i64) -> Self {
106        Self(n as u64)
107    }
108}
109
110#[cfg(all(test, feature = "alloc"))]
111mod tests {
112    use super::*;
113    use alloc::vec::Vec;
114
115    /// The code word for `value`, as a string of bits.
116    fn word<T: BitCodec<true>>(value: &T) -> alloc::string::String {
117        let mut bytes = Vec::new();
118        let mut w = BitWriter::<_, true>::new(&mut bytes);
119        value.encode(&mut w).expect("a vector has room");
120        let bits = w.position();
121        (0..bits).map(|i| if bytes[i / 8] >> (7 - i % 8) & 1 == 1 { '1' } else { '0' }).collect()
122    }
123
124    /// Decode `word`, with ones after it to catch a decode that reads too far.
125    fn read<T: BitCodec<true> + core::fmt::Debug>(word: &str) -> (T, usize) {
126        let mut bytes = alloc::vec![0xFFu8; word.len().div_ceil(8) + 8];
127        for (i, c) in word.chars().enumerate() {
128            let bit = 0x80u8 >> (i % 8);
129            if c == '0' {
130                bytes[i / 8] &= !bit;
131            } else {
132                bytes[i / 8] |= bit;
133            }
134        }
135        T::decode(&bytes, 0).expect("the table's code word decodes")
136    }
137
138    /// ITU-T H.264 Table 9-1: the first ten `ue(v)` code words.
139    const UE: [&str; 10] =
140        ["1", "010", "011", "00100", "00101", "00110", "00111", "0001000", "0001001", "0001010"];
141
142    /// ITU-T H.264 Table 9-3: the value each of the first seven code numbers has as `se(v)`.
143    const SE: [i64; 7] = [0, 1, -1, 2, -2, 3, -3];
144
145    #[test]
146    fn the_published_unsigned_table_is_the_code_word_both_ways() {
147        for (n, bits) in UE.iter().enumerate() {
148            let value = ExpGolomb(n as u64);
149            assert_eq!(&word(&value), bits, "code number {n}");
150            assert_eq!(read::<ExpGolomb>(bits), (value, bits.len()));
151        }
152    }
153
154    #[test]
155    fn the_published_signed_table_is_the_unsigned_code_word_for_its_code_number() {
156        for (n, value) in SE.iter().enumerate() {
157            assert_eq!(crate::num::zigzag(-*value), n as u64, "value {value}");
158            assert_eq!(-crate::num::unzigzag(n as u64), *value, "code number {n}");
159            assert_eq!(&word(&ExpGolomb(n as u64)), UE[n], "value {value}");
160        }
161    }
162
163    #[test]
164    fn every_value_to_a_thousand_round_trips_in_both_directions() {
165        for n in 0..=1000u64 {
166            let value = ExpGolomb(n);
167            let bits = word(&value);
168            assert_eq!(bits.len(), 2 * (64 - (n + 1).leading_zeros() as usize) - 1);
169            assert_eq!(read::<ExpGolomb>(&bits), (value, bits.len()));
170        }
171        for v in -1000..=1000i64 {
172            let code = crate::num::zigzag(-v);
173            let bits = word(&ExpGolomb(code));
174            assert_eq!(read::<ExpGolomb>(&bits), (ExpGolomb(code), bits.len()));
175            assert_eq!(-crate::num::unzigzag(code), v, "the bijection closes");
176        }
177    }
178
179    #[test]
180    fn the_widest_code_number_is_sixty_four_zero_bits_and_the_bits_after_it() {
181        let bits = word(&ExpGolomb(u64::MAX));
182        assert_eq!(bits.len(), 129);
183        assert!(bits[..64].chars().all(|c| c == '0') && &bits[64..65] == "1");
184        assert_eq!(read::<ExpGolomb>(&bits), (ExpGolomb(u64::MAX), 129));
185
186        let one_less = word(&ExpGolomb(u64::MAX - 1));
187        assert_eq!(one_less.len(), 127);
188        assert_eq!(read::<ExpGolomb>(&one_less), (ExpGolomb(u64::MAX - 1), 127));
189    }
190
191    #[test]
192    fn a_code_word_of_more_than_sixty_five_zero_bits_is_malformed() {
193        let bytes = [0u8; 16];
194        assert_eq!(
195            ExpGolomb::decode(&bytes, 0),
196            Err(ParseError::Malformed { field: "ExpGolomb", at: 0 })
197        );
198    }
199
200    #[test]
201    fn a_code_word_the_bytes_end_inside_is_short() {
202        // Eight zero bits, and the ninth is past the end.
203        assert_eq!(
204            ExpGolomb::decode(&[0u8], 0),
205            Err(ParseError::Short { need_bytes: 2, got_bytes: 1, at: 1 })
206        );
207        assert_eq!(
208            ExpGolomb::decode(&[], 0),
209            Err(ParseError::Short { need_bytes: 1, got_bytes: 0, at: 0 })
210        );
211    }
212
213    #[test]
214    fn a_value_at_every_start_offset_reads_back_what_it_wrote() {
215        let values: Vec<u64> = alloc::vec![0, 1, 2, 7, 8, 255, 1023, 65_535, u32::MAX as u64];
216        for offset in 0..=7u32 {
217            for v in &values {
218                let mut bytes = Vec::new();
219                let (at, width) = {
220                    let mut w = BitWriter::<_, true>::new(&mut bytes);
221                    w.write(0, offset).unwrap();
222                    let at = w.position();
223                    ExpGolomb(*v).encode(&mut w).unwrap();
224                    let width = w.position() - at;
225                    w.write(0, 7).unwrap();
226                    (at, width)
227                };
228                assert_eq!(
229                    ExpGolomb::decode(&bytes, at),
230                    Ok((ExpGolomb(*v), width)),
231                    "offset={offset} value={v}"
232                );
233            }
234        }
235    }
236}