]>
Commit | Line | Data |
---|---|---|
1 | //! Some universal integer codes support for bitstream reader. | |
2 | use crate::io::bitreader::{BitReader, BitReaderError, BitReaderResult}; | |
3 | use crate::io::bitwriter::BitWriter; | |
4 | ||
5 | /// Unsigned integer code types. | |
6 | #[derive(Debug)] | |
7 | pub enum UintCodeType { | |
8 | /// Code where number is represented as run of ones with terminating zero. | |
9 | UnaryOnes, | |
10 | /// Code where number is represented as run of zeroes with terminating one. | |
11 | UnaryZeroes, | |
12 | /// Code for 0, 1 and 2 coded as `0`, `10` and `11` | |
13 | Unary012, | |
14 | /// Code for 0, 1 and 2 coded as `11`, `10` and `0` | |
15 | Unary210, | |
16 | /// General limited unary code with defined run and terminating bit. | |
17 | LimitedUnary(u32, u32), | |
18 | /// Limited run of zeroes with terminating one (unless the code has maximum length). | |
19 | /// | |
20 | /// [`Unary012`] is essentially an alias for `LimitedZeroes(2)`. | |
21 | /// | |
22 | /// [`Unary012`]: #variant.Unary012 | |
23 | LimitedZeroes(u32), | |
24 | /// Limited run of one with terminating zero (unless the code has maximum length). | |
25 | LimitedOnes(u32), | |
26 | /// Golomb code. | |
27 | Golomb(u8), | |
28 | /// Rice code. | |
29 | Rice(u8), | |
30 | /// Elias Gamma code (interleaved). | |
31 | Gamma, | |
32 | /// Elias Gamma' code (sometimes incorrectly called exp-Golomb). | |
33 | GammaP, | |
34 | } | |
35 | ||
36 | /// Signed integer code types. | |
37 | pub enum IntCodeType { | |
38 | /// Golomb code. Last bit represents the sign. | |
39 | Golomb(u8), | |
40 | /// Golomb code. Last bit represents the sign. | |
41 | Rice(u8), | |
42 | /// Elias Gamma code. Unsigned values are remapped as 0, 1, -1, 2, -2, ... | |
43 | Gamma, | |
44 | /// Elias Gamma' code. Unsigned values are remapped as 0, 1, -1, 2, -2, ... | |
45 | GammaP, | |
46 | } | |
47 | ||
48 | /// Universal integer code reader trait for bitstream reader. | |
49 | /// | |
50 | /// # Examples | |
51 | /// | |
52 | /// Read an unsigned Golomb code: | |
53 | /// ```` | |
54 | /// use nihav_core::io::bitreader::*; | |
55 | /// use nihav_core::io::intcode::{IntCodeReader,UintCodeType}; | |
56 | /// | |
57 | /// # fn foo() -> BitReaderResult<()> { | |
58 | /// let mem: [u8; 4] = [ 0, 1, 2, 3]; | |
59 | /// let mut br = BitReader::new(&mem, BitReaderMode::BE); | |
60 | /// let val = br.read_code(UintCodeType::Golomb(3))?; | |
61 | /// # Ok(()) | |
62 | /// # } | |
63 | /// ```` | |
64 | /// | |
65 | /// Read signed Elias code: | |
66 | /// ```` | |
67 | /// use nihav_core::io::bitreader::*; | |
68 | /// use nihav_core::io::intcode::{IntCodeReader,IntCodeType}; | |
69 | /// | |
70 | /// # fn foo() -> BitReaderResult<()> { | |
71 | /// let mem: [u8; 4] = [ 0, 1, 2, 3]; | |
72 | /// let mut br = BitReader::new(&mem, BitReaderMode::BE); | |
73 | /// let val = br.read_code_signed(IntCodeType::Gamma)?; | |
74 | /// # Ok(()) | |
75 | /// # } | |
76 | /// ```` | |
77 | pub trait IntCodeReader { | |
78 | /// Reads an unsigned integer code of requested type. | |
79 | fn read_code(&mut self, t: UintCodeType) -> BitReaderResult<u32>; | |
80 | /// Reads signed integer code of requested type. | |
81 | fn read_code_signed(&mut self, t: IntCodeType) -> BitReaderResult<i32>; | |
82 | } | |
83 | ||
84 | fn read_unary(br: &mut BitReader, terminator: u32) -> BitReaderResult<u32> { | |
85 | let mut res: u32 = 0; | |
86 | loop { | |
87 | if br.read(1)? == terminator { return Ok(res); } | |
88 | res += 1; | |
89 | } | |
90 | } | |
91 | ||
92 | fn read_unary_lim(br: &mut BitReader, len: u32, terminator: u32) -> BitReaderResult<u32> { | |
93 | let mut res: u32 = 0; | |
94 | loop { | |
95 | if br.read(1)? == terminator { return Ok(res); } | |
96 | res += 1; | |
97 | if res == len { return Ok(res); } | |
98 | } | |
99 | } | |
100 | ||
101 | fn read_unary210(br: &mut BitReader) -> BitReaderResult<u32> { | |
102 | let val = read_unary_lim(br, 2, 0)?; | |
103 | Ok(2 - val) | |
104 | } | |
105 | ||
106 | fn read_golomb(br: &mut BitReader, m: u8) -> BitReaderResult<u32> { | |
107 | if m == 0 { return Err(BitReaderError::InvalidValue); } | |
108 | let nbits = (8 - m.leading_zeros()) as u8; | |
109 | if (m & (m - 1)) == 0 { return read_rice(br, nbits); } | |
110 | let cutoff = u32::from((1 << nbits) - m); | |
111 | let pfx = read_unary(br, 0)?; | |
112 | let tail = br.read(nbits - 1)?; | |
113 | if tail < cutoff { | |
114 | let res = pfx * u32::from(m) + tail; | |
115 | Ok (res) | |
116 | } else { | |
117 | let add = br.read(1)?; | |
118 | let res = pfx * u32::from(m) + (tail - cutoff) * 2 + add + cutoff; | |
119 | Ok (res) | |
120 | } | |
121 | } | |
122 | ||
123 | fn read_rice(br: &mut BitReader, k: u8) -> BitReaderResult<u32> { | |
124 | let pfx = read_unary(br, 1)?; | |
125 | let ret = (pfx << k) + br.read(k)?; | |
126 | Ok(ret) | |
127 | } | |
128 | ||
129 | fn read_gamma(br: &mut BitReader) -> BitReaderResult<u32> { | |
130 | let mut ret = 1; | |
131 | while br.read(1)? != 1 { | |
132 | ret = (ret << 1) | br.read(1)?; | |
133 | } | |
134 | Ok(ret - 1) | |
135 | } | |
136 | ||
137 | fn read_gammap(br: &mut BitReader) -> BitReaderResult<u32> { | |
138 | let pfx = read_unary(br, 1)?; | |
139 | if pfx > 32 { return Err(BitReaderError::InvalidValue); } | |
140 | let ret = (1 << pfx) + br.read(pfx as u8)?; | |
141 | Ok(ret) | |
142 | } | |
143 | ||
144 | fn uval_to_sval0mp(uval: u32) -> i32 { | |
145 | if (uval & 1) != 0 { -(((uval + 1) >> 1) as i32) } | |
146 | else { (uval >> 1) as i32 } | |
147 | } | |
148 | ||
149 | fn uval_to_sval0pm(uval: u32) -> i32 { | |
150 | if (uval & 1) != 0 { ((uval + 1) >> 1) as i32 } | |
151 | else { -((uval >> 1) as i32) } | |
152 | } | |
153 | ||
154 | impl<'a> IntCodeReader for BitReader<'a> { | |
155 | #[inline(always)] | |
156 | fn read_code(&mut self, t: UintCodeType) -> BitReaderResult<u32> { | |
157 | match t { | |
158 | UintCodeType::UnaryOnes => read_unary(self, 0), | |
159 | UintCodeType::UnaryZeroes => read_unary(self, 1), | |
160 | UintCodeType::LimitedZeroes(len) => read_unary_lim(self, len, 1), | |
161 | UintCodeType::LimitedOnes(len) => read_unary_lim(self, len, 0), | |
162 | UintCodeType::LimitedUnary(len, term) => read_unary_lim(self, len, term), | |
163 | UintCodeType::Unary012 => read_unary_lim(self, 2, 0), | |
164 | UintCodeType::Unary210 => read_unary210(self), | |
165 | UintCodeType::Golomb(m) => read_golomb(self, m), | |
166 | UintCodeType::Rice(k) => read_rice(self, k), | |
167 | UintCodeType::Gamma => read_gamma(self), | |
168 | UintCodeType::GammaP => read_gammap(self), | |
169 | } | |
170 | } | |
171 | #[allow(unused_variables)] | |
172 | fn read_code_signed(&mut self, t: IntCodeType) -> BitReaderResult<i32> { | |
173 | let uval = | |
174 | match t { | |
175 | IntCodeType::Golomb(m) => read_golomb(self, m)?, | |
176 | IntCodeType::Rice(k) => read_rice(self, k)?, | |
177 | IntCodeType::Gamma => read_gamma(self)?, | |
178 | IntCodeType::GammaP => read_gammap(self)?, | |
179 | }; | |
180 | match t { | |
181 | IntCodeType::Golomb(m) => Ok(uval_to_sval0mp(uval)), | |
182 | IntCodeType::Rice(k) => Ok(uval_to_sval0mp(uval)), | |
183 | IntCodeType::Gamma => Ok(uval_to_sval0pm(uval)), | |
184 | IntCodeType::GammaP => Ok(uval_to_sval0pm(uval)), | |
185 | } | |
186 | } | |
187 | } | |
188 | ||
189 | /// Universal integer code writer trait for bitstream writer. | |
190 | /// | |
191 | /// # Examples | |
192 | /// | |
193 | /// Write an unsigned Golomb code: | |
194 | /// ```` | |
195 | /// use nihav_core::io::bitwriter::*; | |
196 | /// use nihav_core::io::intcode::{IntCodeWriter,UintCodeType}; | |
197 | /// | |
198 | /// let mut bw = BitWriter::new(Vec::new(), BitWriterMode::BE); | |
199 | /// bw.write_code(UintCodeType::Golomb(3), 42); | |
200 | /// ```` | |
201 | /// | |
202 | /// Write signed Elias code: | |
203 | /// ```` | |
204 | /// use nihav_core::io::bitwriter::*; | |
205 | /// use nihav_core::io::intcode::{IntCodeWriter,IntCodeType}; | |
206 | /// | |
207 | /// let mut bw = BitWriter::new(Vec::new(), BitWriterMode::BE); | |
208 | /// bw.write_code_signed(IntCodeType::Gamma, 42); | |
209 | /// ```` | |
210 | pub trait IntCodeWriter { | |
211 | /// Writes an unsigned integer code of requested type. | |
212 | fn write_code(&mut self, t: UintCodeType, val: u32); | |
213 | /// Writes signed integer code of requested type. | |
214 | fn write_code_signed(&mut self, t: IntCodeType, val: i32); | |
215 | } | |
216 | ||
217 | impl IntCodeWriter for BitWriter { | |
218 | #[inline(always)] | |
219 | fn write_code(&mut self, t: UintCodeType, val: u32) { | |
220 | match t { | |
221 | UintCodeType::UnaryOnes => write_unary(self, val, 0), | |
222 | UintCodeType::UnaryZeroes => write_unary(self, val, 1), | |
223 | UintCodeType::LimitedZeroes(len) => write_unary_lim(self, val, len, 1), | |
224 | UintCodeType::LimitedOnes(len) => write_unary_lim(self, val, len, 0), | |
225 | UintCodeType::LimitedUnary(len, term) => write_unary_lim(self, val, len, term), | |
226 | UintCodeType::Unary012 => write_unary_lim(self, val, 2, 0), | |
227 | UintCodeType::Unary210 => write_unary210(self, val), | |
228 | UintCodeType::Golomb(m) => write_golomb(self, val, m), | |
229 | UintCodeType::Rice(k) => write_rice(self, val, k), | |
230 | UintCodeType::Gamma => write_gamma(self, val), | |
231 | UintCodeType::GammaP => write_gammap(self, val), | |
232 | }; | |
233 | } | |
234 | fn write_code_signed(&mut self, t: IntCodeType, val: i32) { | |
235 | match t { | |
236 | IntCodeType::Golomb(m) => write_golomb(self, sval0mp_to_uval(val), m), | |
237 | IntCodeType::Rice(k) => write_rice(self, sval0mp_to_uval(val), k), | |
238 | IntCodeType::Gamma => write_gamma(self, sval0pm_to_uval(val)), | |
239 | IntCodeType::GammaP => write_gammap(self, sval0pm_to_uval(val)), | |
240 | }; | |
241 | } | |
242 | } | |
243 | ||
244 | fn sval0mp_to_uval(val: i32) -> u32 { | |
245 | if val < 0 { (-val as u32) * 2 - 1 } | |
246 | else { (val as u32) * 2 } | |
247 | } | |
248 | ||
249 | fn sval0pm_to_uval(val: i32) -> u32 { | |
250 | if val >= 0 { (val as u32) * 2 + 1 } | |
251 | else { (-val as u32) * 2 } | |
252 | } | |
253 | ||
254 | fn write_unary210(bw: &mut BitWriter, val: u32) { | |
255 | bw.write_bit(val == 0); | |
256 | if val != 0 { | |
257 | bw.write_bit(val == 1); | |
258 | } | |
259 | } | |
260 | ||
261 | fn write_unary(bw: &mut BitWriter, val: u32, term: u32) { | |
262 | let term = term != 0; | |
263 | for _ in 0..val { | |
264 | bw.write_bit(!term); | |
265 | } | |
266 | bw.write_bit(term); | |
267 | } | |
268 | ||
269 | fn write_unary_lim(bw: &mut BitWriter, val: u32, maxval: u32, term: u32) { | |
270 | let term = term != 0; | |
271 | for _ in 0..val { | |
272 | bw.write_bit(!term); | |
273 | } | |
274 | if val < maxval { | |
275 | bw.write_bit(term); | |
276 | } | |
277 | } | |
278 | ||
279 | fn write_rice(bw: &mut BitWriter, val: u32, k: u8) { | |
280 | let mut exp = val >> k; | |
281 | while exp >= 16 { | |
282 | bw.write(0, 16); | |
283 | exp -= 16 | |
284 | } | |
285 | if exp > 0 { | |
286 | bw.write(0, exp as u8); | |
287 | } | |
288 | bw.write1(); | |
289 | if k > 0 { | |
290 | let mant = val & ((1 << k) - 1); | |
291 | bw.write(mant, k); | |
292 | } | |
293 | } | |
294 | ||
295 | fn write_golomb(bw: &mut BitWriter, val: u32, m: u8) { | |
296 | if m == 0 { return; } | |
297 | let nbits = (8 - m.leading_zeros()) as u8; | |
298 | if (m & (m - 1)) == 0 { return write_rice(bw, val, nbits); } | |
299 | let q = val / u32::from(m); | |
300 | let r = val % u32::from(m); | |
301 | let cutoff = u32::from((1 << nbits) - m); | |
302 | ||
303 | write_unary(bw, q, 0); | |
304 | if r < cutoff { | |
305 | bw.write(r, nbits - 1); | |
306 | } else { | |
307 | bw.write(r + cutoff, nbits); | |
308 | } | |
309 | } | |
310 | ||
311 | fn write_gamma(bw: &mut BitWriter, val: u32) { | |
312 | let val = val + 1; | |
313 | let bits = (32 - val.leading_zeros()) as u8; | |
314 | let mut mask = 1 << bits >> 2; | |
315 | while mask != 0 { | |
316 | bw.write0(); | |
317 | bw.write_bit((val & mask) != 0); | |
318 | mask >>= 1; | |
319 | } | |
320 | bw.write1(); | |
321 | } | |
322 | ||
323 | fn write_gammap(bw: &mut BitWriter, val: u32) { | |
324 | let bits = 31 - val.leading_zeros(); | |
325 | write_unary(bw, bits, 1); | |
326 | bw.write(val - (1 << bits), bits as u8); | |
327 | } | |
328 | ||
329 | #[cfg(test)] | |
330 | mod test { | |
331 | use super::*; | |
332 | use crate::io::bitreader::*; | |
333 | use crate::io::bitwriter::*; | |
334 | ||
335 | #[test] | |
336 | fn int_codes() { | |
337 | const GDATA: [u8; 6] = [0b000_001_01, 0b0_0110_011, 0b1_1000_100, 0b1_1010_101, 0b10_10111_1, 0b1000_0000]; | |
338 | let src = &GDATA; | |
339 | let mut br = BitReader::new(src, BitReaderMode::BE); | |
340 | for i in 0..11 { | |
341 | assert_eq!(br.read_code(UintCodeType::Golomb(5)).unwrap(), i); | |
342 | } | |
343 | } | |
344 | #[test] | |
345 | fn rw_codes() { | |
346 | let mut bw = BitWriter::new(Vec::new(), BitWriterMode::BE); | |
347 | bw.write_code(UintCodeType::Golomb(5), 42); | |
348 | bw.write_code(UintCodeType::Gamma, 42); | |
349 | bw.write_code(UintCodeType::GammaP, 42); | |
350 | let data = bw.end(); | |
351 | let mut br = BitReader::new(&data, BitReaderMode::BE); | |
352 | ||
353 | let mut br = BitReader::new(&data, BitReaderMode::BE); | |
354 | assert_eq!(br.read_code(UintCodeType::Golomb(5)).unwrap(), 42); | |
355 | assert_eq!(br.read_code(UintCodeType::Gamma).unwrap(), 42); | |
356 | assert_eq!(br.read_code(UintCodeType::GammaP).unwrap(), 42); | |
357 | } | |
358 | } |