1use crate::bits::{BitCodec, BitWriter};
3use crate::{ParseError, WireInt};
4
5#[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 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 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 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 const UE: [&str; 10] =
140 ["1", "010", "011", "00100", "00101", "00110", "00111", "0001000", "0001001", "0001010"];
141
142 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 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}