]> git.nihav.org Git - nihav.git/blob - nihav-core/src/io/intcode.rs
h264: add SIMD optimisations for x86_64 (not enabled by default)
[nihav.git] / nihav-core / src / io / intcode.rs
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 }