]> git.nihav.org Git - nihav.git/blob - nihav-duck/src/codecs/vp56.rs
add MPEG-4 ASP decoder
[nihav.git] / nihav-duck / src / codecs / vp56.rs
1 use nihav_core::codecs::*;
2 use nihav_core::io::bitreader::*;
3 use nihav_codec_support::codecs::{MV, ZERO_MV};
4 use super::vpcommon::*;
5
6 pub const TOKEN_LARGE: u8 = 5;
7 pub const TOKEN_EOB: u8 = 42;
8
9 #[derive(Clone,Copy,Debug,Default)]
10 #[allow(dead_code)]
11 pub struct VP56Header {
12 pub is_intra: bool,
13 pub is_golden: bool,
14 pub quant: u8,
15 pub multistream: bool,
16 pub use_huffman: bool,
17 pub version: u8,
18 pub profile: u8,
19 pub interlaced: bool,
20 pub offset: u16,
21 pub mb_w: u8,
22 pub mb_h: u8,
23 pub disp_w: u8,
24 pub disp_h: u8,
25 pub scale: u8,
26 }
27
28 #[derive(Clone,Copy,Default)]
29 pub struct VP56MVModel {
30 pub nz_prob: u8,
31 pub sign_prob: u8,
32 pub raw_probs: [u8; 8],
33 pub tree_probs: [u8; 7],
34 }
35
36 #[derive(Clone,Copy,Default)]
37 pub struct VP56MBTypeModel {
38 pub probs: [u8; 10],
39 }
40
41 #[derive(Clone,Copy,Default)]
42 pub struct VP56CoeffModel {
43 pub dc_token_probs: [[[u8; 5]; 6]; 6],
44 pub dc_value_probs: [u8; 11],
45 pub ac_ctype_probs: [[[[u8; 5]; 5]; 6]; 3],
46 pub ac_type_probs: [[[[u8; 5]; 6]; 3]; 3],
47 pub ac_val_probs: [[[u8; 11]; 6]; 3],
48 }
49
50 pub struct VP6Models {
51 pub scan_order: [usize; 64],
52 pub scan: [usize; 64],
53 pub zigzag: [usize; 64],
54 pub zero_run_probs: [[u8; 14]; 2],
55 }
56
57 const MAX_HUFF_ELEMS: usize = 12;
58 #[derive(Clone,Copy,Default)]
59 pub struct VP6Huff {
60 pub codes: [u16; MAX_HUFF_ELEMS],
61 pub bits: [u8; MAX_HUFF_ELEMS],
62 }
63
64 #[derive(Clone,Copy,Default)]
65 struct Node {
66 weight: u16,
67 sym: i8,
68 ch0: usize,
69 ch1: usize,
70 }
71
72 fn prob2weight(a: u8, b: u8) -> u8 {
73 let w = ((u16::from(a) * u16::from(b)) >> 8) as u8;
74 if w == 0 {
75 1
76 } else {
77 w
78 }
79 }
80
81 impl VP6Huff {
82 fn build_codes(&mut self, probs: &[u8; 11]) {
83 let mut weights = [0u8; 12];
84
85 weights[11] = prob2weight( probs[0], probs[ 1]);
86 weights[ 0] = prob2weight( probs[0], !probs[ 1]);
87 weights[ 1] = prob2weight(!probs[0], probs[ 2]);
88 let lvroot = prob2weight(!probs[0], !probs[ 2]);
89 let tworoot = prob2weight( lvroot, probs[ 3]);
90 let hlroot = prob2weight( lvroot, !probs[ 3]);
91 weights[ 2] = prob2weight( tworoot, probs[ 4]);
92 let root34 = prob2weight( tworoot, !probs[ 4]);
93 weights[ 3] = prob2weight( root34, probs[ 5]);
94 weights[ 4] = prob2weight( root34, !probs[ 5]);
95 let c1root = prob2weight( hlroot, probs[ 6]);
96 let c34root = prob2weight( hlroot, !probs[ 6]);
97 weights[ 5] = prob2weight( c1root, probs[ 7]);
98 weights[ 6] = prob2weight( c1root, !probs[ 7]);
99 let c3root = prob2weight( c34root, probs[ 8]);
100 let c4root = prob2weight( c34root, !probs[ 8]);
101 weights[ 7] = prob2weight( c3root, probs[ 9]);
102 weights[ 8] = prob2weight( c3root, !probs[ 9]);
103 weights[ 9] = prob2weight( c4root, probs[10]);
104 weights[10] = prob2weight( c4root, !probs[10]);
105
106 self.build(&weights);
107 }
108 fn build_codes_zero_run(&mut self, probs: &[u8; 14]) {
109 let mut weights = [0u8; 9];
110
111 let root = prob2weight( probs[0], probs[1]);
112 weights[0] = prob2weight( root, probs[2]);
113 weights[1] = prob2weight( root, !probs[2]);
114
115 let root = prob2weight( probs[0], !probs[1]);
116 weights[2] = prob2weight( root, probs[3]);
117 weights[3] = prob2weight( root, !probs[3]);
118
119 let root = prob2weight(!probs[0], probs[4]);
120 weights[8] = prob2weight(!probs[0], !probs[4]);
121 let root1 = prob2weight( root, probs[5]);
122 let root2 = prob2weight( root, !probs[5]);
123 weights[4] = prob2weight( root1, probs[6]);
124 weights[5] = prob2weight( root1, !probs[6]);
125 weights[6] = prob2weight( root2, probs[7]);
126 weights[7] = prob2weight( root2, !probs[7]);
127
128 self.build(&weights);
129 }
130 fn build(&mut self, weights: &[u8]) {
131 let mut nodes = [Node::default(); MAX_HUFF_ELEMS * 2];
132 let mut nlen = 0;
133
134 for w in weights.iter().rev() {
135 let weight = u16::from(*w);
136 let mut pos = nlen;
137 for i in 0..nlen {
138 if nodes[i].weight > weight {
139 pos = i;
140 break;
141 }
142 }
143 for j in (pos..nlen).rev() {
144 nodes[j + 1] = nodes[j];
145 }
146 nodes[pos].weight = weight;
147 nodes[pos].sym = (weights.len() - nlen - 1) as i8;
148 nlen += 1;
149 }
150
151 let mut low = 0;
152 for _ in 0..nlen-1 {
153 let nnode = Node {
154 weight: nodes[low + 0].weight + nodes[low + 1].weight,
155 sym: -1,
156 ch0: low + 0,
157 ch1: low + 1,
158 };
159 low += 2;
160 let mut pos = low;
161 while (pos < nlen) && (nodes[pos].weight < nnode.weight) {
162 pos += 1;
163 }
164 for j in (pos..nlen).rev() {
165 nodes[j + 1] = nodes[j];
166 }
167 nodes[pos] = nnode;
168 nlen += 1;
169 }
170 self.get_codes(&nodes, nlen - 1, 0, 0);
171 for i in nlen..self.codes.len() {
172 self.codes[i] = self.codes[0];
173 self.bits[i] = self.bits[0];
174 }
175 }
176 fn get_codes(&mut self, nodes: &[Node], pos: usize, code: u16, len: u8) {
177 if nodes[pos].sym >= 0 {
178 self.codes[nodes[pos].sym as usize] = code;
179 self.bits [nodes[pos].sym as usize] = len;
180 } else {
181 self.get_codes(nodes, nodes[pos].ch0, (code << 1) | 0, len + 1);
182 self.get_codes(nodes, nodes[pos].ch1, (code << 1) | 1, len + 1);
183 }
184 }
185 }
186
187 pub trait ReadHuff {
188 fn read_huff(&mut self, huff: &VP6Huff) -> DecoderResult<u8>;
189 }
190
191 impl<'a> ReadHuff for BitReader<'a> {
192 fn read_huff(&mut self, huff: &VP6Huff) -> DecoderResult<u8> {
193 let peekval = self.peek(16);
194 for (i, (code, bit)) in huff.codes.iter().zip(huff.bits.iter()).enumerate() {
195 if (peekval >> (16 - *bit)) == u32::from(*code) {
196 self.skip(u32::from(*bit))?;
197 return Ok(i as u8);
198 }
199 }
200 Err(DecoderError::InvalidData)
201 }
202 }
203
204 #[derive(Clone,Copy,Default)]
205 pub struct VP6HuffModels {
206 pub dc_token_tree: [VP6Huff; 2],
207 pub ac_token_tree: [[[VP6Huff; 6]; 3]; 2],
208 pub zero_run_tree: [VP6Huff; 2],
209 }
210
211 impl VP6Models {
212 fn new() -> Self {
213 Self {
214 scan_order: [0; 64],
215 scan: [0; 64],
216 zigzag: [0; 64],
217 zero_run_probs: [[0; 14]; 2],
218 }
219 }
220 }
221
222 pub struct VP56Models {
223 pub mv_models: [VP56MVModel; 2],
224 pub mbtype_models: [[VP56MBTypeModel; 10]; 3],
225 pub coeff_models: [VP56CoeffModel; 2],
226 pub prob_xmitted: [[u8; 20]; 3],
227 pub vp6models: VP6Models,
228 pub vp6huff: VP6HuffModels,
229 }
230
231 impl VP56Models {
232 fn new() -> Self {
233 Self {
234 mv_models: [VP56MVModel::default(); 2],
235 mbtype_models: [[VP56MBTypeModel::default(); 10]; 3],
236 coeff_models: [VP56CoeffModel::default(); 2],
237 prob_xmitted: [[0; 20]; 3],
238 vp6models: VP6Models::new(),
239 vp6huff: VP6HuffModels::default(),
240 }
241 }
242 }
243
244 pub trait VP56Parser {
245 fn parse_header(&mut self, bc: &mut BoolCoder) -> DecoderResult<VP56Header>;
246 fn reset_models(&self, models: &mut VP56Models);
247 fn decode_mv(&self, bc: &mut BoolCoder, model: &VP56MVModel) -> i16;
248 fn decode_mv_models(&self, bc: &mut BoolCoder, models: &mut [VP56MVModel; 2]) -> DecoderResult<()>;
249 fn decode_coeff_models(&self, bc: &mut BoolCoder, models: &mut VP56Models, is_intra: bool) -> DecoderResult<()>;
250 fn decode_block(&self, bc: &mut BoolCoder, coeffs: &mut [i16; 64], model: &VP56CoeffModel, vp6model: &VP6Models, fstate: &mut FrameState) -> DecoderResult<()>;
251 fn decode_block_huff(&self, br: &mut BitReader, coeffs: &mut [i16; 64], vp6model: &VP6Models, model: &VP6HuffModels, fstate: &mut FrameState) -> DecoderResult<()>;
252 fn mc_block(&self, dst: &mut NASimpleVideoFrame<u8>, mc_buf: NAVideoBufferRef<u8>, src: NAVideoBufferRef<u8>, plane: usize, x: usize, y: usize, mv: MV, loop_thr: i16);
253 }
254
255 enum CoeffReader<'a> {
256 None,
257 Bool(BoolCoder<'a>),
258 Huff(BitReader<'a>),
259 }
260
261 #[derive(Clone,Copy,Default)]
262 struct MBInfo {
263 mb_type: VPMBType,
264 mv: MV,
265 }
266
267 pub struct FrameState {
268 pub mb_x: usize,
269 pub mb_y: usize,
270 pub plane: usize,
271 pub coeff_cat: [[u8; 64]; 4],
272 pub last_idx: [usize; 4],
273 pub top_ctx: u8,
274 pub ctx_idx: usize,
275 pub dc_quant: i16,
276 pub ac_quant: i16,
277 pub dc_zero_run: [usize; 2],
278 pub ac_zero_run: [usize; 2],
279 }
280
281 impl FrameState {
282 fn new() -> Self {
283 Self {
284 mb_x: 0,
285 mb_y: 0,
286 plane: 0,
287 coeff_cat: [[0; 64]; 4],
288 last_idx: [0; 4],
289 top_ctx: 0,
290 ctx_idx: 0,
291 dc_quant: 0,
292 ac_quant: 0,
293 dc_zero_run: [0; 2],
294 ac_zero_run: [0; 2],
295 }
296 }
297 }
298
299 #[derive(Default)]
300 pub struct VP56DCPred {
301 dc_y: Vec<i16>,
302 dc_u: Vec<i16>,
303 dc_v: Vec<i16>,
304 ldc_y: [i16; 2],
305 ldc_u: i16,
306 ldc_v: i16,
307 ref_y: Vec<u8>,
308 ref_c: Vec<u8>,
309 ref_left: u8,
310 y_idx: usize,
311 c_idx: usize,
312 }
313
314 const INVALID_REF: u8 = 42;
315
316 impl VP56DCPred {
317 fn new() -> Self { Self::default() }
318 fn resize(&mut self, mb_w: usize) {
319 self.dc_y.resize(mb_w * 2 + 2, 0);
320 self.dc_u.resize(mb_w + 2, 0);
321 self.dc_v.resize(mb_w + 2, 0);
322 self.ref_y.resize(mb_w * 2 + 2, INVALID_REF);
323 self.ref_c.resize(mb_w + 2, INVALID_REF);
324 self.ref_c[0] = 0;
325 }
326 fn reset(&mut self) {
327 self.update_row();
328 for el in self.ref_y.iter_mut().skip(1) { *el = INVALID_REF; }
329 for el in self.ref_c.iter_mut().skip(1) { *el = INVALID_REF; }
330 }
331 fn update_row(&mut self) {
332 self.y_idx = 1;
333 self.c_idx = 1;
334 self.ldc_y = [0; 2];
335 self.ldc_u = 0;
336 self.ldc_v = 0;
337 self.ref_left = INVALID_REF;
338 }
339 fn next_mb(&mut self) {
340 self.y_idx += 2;
341 self.c_idx += 1;
342 }
343 }
344
345 pub struct VP56Decoder {
346 version: u8,
347 has_alpha: bool,
348 flip: bool,
349 shuf: VPShuffler,
350 width: usize,
351 height: usize,
352 mb_w: usize,
353 mb_h: usize,
354 models: VP56Models,
355 amodels: VP56Models,
356 coeffs: [[i16; 64]; 6],
357 last_mbt: VPMBType,
358
359 loop_thr: i16,
360 ilace_prob: u8,
361 ilace_mb: bool,
362
363 mb_info: Vec<MBInfo>,
364 fstate: FrameState,
365 dc_pred: VP56DCPred,
366 last_dc: [[i16; 4]; 3],
367 top_ctx: [Vec<u8>; 4],
368
369 mc_buf: NAVideoBufferRef<u8>,
370 }
371
372 fn rescale_mb_mode_prob(prob: u32, total: u32) -> u8 {
373 (255 * prob / (1 + total)) as u8
374 }
375
376 fn map_mb_type(mbtype: VPMBType) -> usize {
377 match mbtype {
378 VPMBType::InterNoMV => 0,
379 VPMBType::Intra => 1,
380 VPMBType::InterMV => 2,
381 VPMBType::InterNearest => 3,
382 VPMBType::InterNear => 4,
383 VPMBType::GoldenNoMV => 5,
384 VPMBType::GoldenMV => 6,
385 VPMBType::InterFourMV => 7,
386 VPMBType::GoldenNearest => 8,
387 VPMBType::GoldenNear => 9,
388 }
389 }
390
391 pub fn expand_token_bc(bc: &mut BoolCoder, val_probs: &[u8; 11], token: u8, version: u8) -> i16 {
392 let mut sign = false;
393 let level;
394 if token < TOKEN_LARGE {
395 if token != 0 {
396 sign = bc.read_bool();
397 }
398 level = i16::from(token);
399 } else {
400 let cat: usize = vp_tree!(bc, val_probs[6],
401 vp_tree!(bc, val_probs[7], 0, 1),
402 vp_tree!(bc, val_probs[8],
403 vp_tree!(bc, val_probs[9], 2, 3),
404 vp_tree!(bc, val_probs[10], 4, 5)));
405 if version == 5 {
406 sign = bc.read_bool();
407 }
408 let mut add = 0i16;
409 let add_probs = &VP56_COEF_ADD_PROBS[cat];
410 for prob in add_probs.iter() {
411 if *prob == 128 { break; }
412 add = (add << 1) | (bc.read_prob(*prob) as i16);
413 }
414 if version != 5 {
415 sign = bc.read_bool();
416 }
417 level = VP56_COEF_BASE[cat] + add;
418 }
419 if !sign {
420 level
421 } else {
422 -level
423 }
424 }
425
426 impl VP56Decoder {
427 pub fn new(version: u8, has_alpha: bool, flip: bool) -> Self {
428 let vt = alloc_video_buffer(NAVideoInfo::new(24, 24, false, VP_YUVA420_FORMAT), 4).unwrap();
429 let mc_buf = vt.get_vbuf().unwrap();
430 Self {
431 version, has_alpha, flip,
432 shuf: VPShuffler::new(),
433 width: 0,
434 height: 0,
435 mb_w: 0,
436 mb_h: 0,
437 models: VP56Models::new(),
438 amodels: VP56Models::new(),
439 coeffs: [[0; 64]; 6],
440 last_mbt: VPMBType::InterNoMV,
441
442 loop_thr: 0,
443 ilace_prob: 0,
444 ilace_mb: false,
445
446 mb_info: Vec::new(),
447 fstate: FrameState::new(),
448 dc_pred: VP56DCPred::new(),
449 last_dc: [[0; 4]; 3],
450 top_ctx: [Vec::new(), Vec::new(), Vec::new(), Vec::new()],
451
452 mc_buf,
453 }
454 }
455 fn set_dimensions(&mut self, width: usize, height: usize) {
456 self.width = width;
457 self.height = height;
458 self.mb_w = (self.width + 15) >> 4;
459 self.mb_h = (self.height + 15) >> 4;
460 self.mb_info.resize(self.mb_w * self.mb_h, MBInfo::default());
461 self.top_ctx = [vec![0; self.mb_w * 2], vec![0; self.mb_w], vec![0; self.mb_w], vec![0; self.mb_w * 2]];
462 }
463 pub fn init(&mut self, supp: &mut NADecoderSupport, vinfo: NAVideoInfo) -> DecoderResult<()> {
464 supp.pool_u8.set_dec_bufs(3 + if vinfo.get_format().has_alpha() { 1 } else { 0 });
465 supp.pool_u8.prealloc_video(NAVideoInfo::new(vinfo.get_width(), vinfo.get_height(), false, vinfo.get_format()), 4)?;
466 self.set_dimensions(vinfo.get_width(), vinfo.get_height());
467 self.dc_pred.resize(self.mb_w);
468 Ok(())
469 }
470 pub fn flush(&mut self) {
471 self.shuf.clear();
472 }
473 pub fn decode_frame(&mut self, supp: &mut NADecoderSupport, src: &[u8], br: &mut dyn VP56Parser) -> DecoderResult<(NABufferType, FrameType)> {
474 let aoffset;
475 let mut bc;
476 if self.has_alpha {
477 validate!(src.len() >= 7);
478 aoffset = ((src[0] as usize) << 16) | ((src[1] as usize) << 8) | (src[2] as usize);
479 validate!((aoffset > 0) && (aoffset < src.len() - 3));
480 bc = BoolCoder::new(&src[3..])?;
481 } else {
482 validate!(src.len() >= 4);
483 aoffset = src.len();
484 bc = BoolCoder::new(src)?;
485 }
486 let hdr = br.parse_header(&mut bc)?;
487 validate!((hdr.offset as usize) < aoffset); //XXX: take alpha 3 byte offset into account?
488
489 if hdr.mb_w != 0 && (usize::from(hdr.mb_w) != self.mb_w || usize::from(hdr.mb_h) != self.mb_h) {
490 self.set_dimensions((hdr.mb_w as usize) * 16, (hdr.mb_h as usize) * 16);
491 }
492 let fmt = if !self.has_alpha {
493 YUV420_FORMAT
494 } else {
495 VP_YUVA420_FORMAT
496 };
497 let vinfo = NAVideoInfo::new(self.width, self.height, self.flip, fmt);
498 let ret = supp.pool_u8.get_free();
499 if ret.is_none() {
500 return Err(DecoderError::AllocError);
501 }
502 let mut buf = ret.unwrap();
503 if buf.get_info() != vinfo {
504 self.shuf.clear();
505 supp.pool_u8.reset();
506 supp.pool_u8.prealloc_video(vinfo, 4)?;
507 let ret = supp.pool_u8.get_free();
508 if ret.is_none() {
509 return Err(DecoderError::AllocError);
510 }
511 buf = ret.unwrap();
512 }
513 let mut dframe = NASimpleVideoFrame::from_video_buf(&mut buf).unwrap();
514
515 if hdr.is_intra {
516 self.shuf.clear();
517 } else {
518 if !self.shuf.has_refs() {
519 return Err(DecoderError::MissingReference);
520 }
521 }
522
523 let psrc = &src[if self.has_alpha { 3 } else { 0 }..aoffset];
524 self.decode_planes(br, &mut dframe, &mut bc, &hdr, psrc, false)?;
525
526 if self.has_alpha {
527 let asrc = &src[aoffset + 3..];
528 let mut bc = BoolCoder::new(asrc)?;
529 let ahdr = br.parse_header(&mut bc)?;
530 validate!(ahdr.mb_w == hdr.mb_w && ahdr.mb_h == hdr.mb_h);
531 std::mem::swap(&mut self.models, &mut self.amodels);
532 let ret = self.decode_planes(br, &mut dframe, &mut bc, &ahdr, asrc, true);
533 std::mem::swap(&mut self.models, &mut self.amodels);
534 if let Err(err) = ret {
535 return Err(err);
536 }
537 match (hdr.is_golden, ahdr.is_golden) {
538 (true, true) => { self.shuf.add_golden_frame(buf.clone()); },
539 (true, false) => {
540 let cur_golden = self.shuf.get_golden().unwrap();
541 let off = cur_golden.get_offset(3);
542 let stride = cur_golden.get_stride(3);
543 let mut new_golden = supp.pool_u8.get_copy(&buf).unwrap();
544 let dst = new_golden.get_data_mut().unwrap();
545 let src = cur_golden.get_data();
546 dst[off..][..stride * self.mb_h * 16].copy_from_slice(&src[off..][..stride * self.mb_h * 16]);
547 self.shuf.add_golden_frame(new_golden);
548 },
549 (false, true) => {
550 let cur_golden = self.shuf.get_golden().unwrap();
551 let off = cur_golden.get_offset(3);
552 let stride = cur_golden.get_stride(3);
553 let mut new_golden = supp.pool_u8.get_copy(&cur_golden).unwrap();
554 let dst = new_golden.get_data_mut().unwrap();
555 let src = buf.get_data();
556 dst[off..][..stride * self.mb_h * 16].copy_from_slice(&src[off..][..stride * self.mb_h * 16]);
557 self.shuf.add_golden_frame(new_golden);
558 },
559 _ => {},
560 };
561 }
562
563 if hdr.is_golden && !self.has_alpha {
564 self.shuf.add_golden_frame(buf.clone());
565 }
566 self.shuf.add_frame(buf.clone());
567
568 Ok((NABufferType::Video(buf), if hdr.is_intra { FrameType::I } else { FrameType::P }))
569 }
570 fn decode_planes(&mut self, br: &mut dyn VP56Parser, dframe: &mut NASimpleVideoFrame<u8>, bc: &mut BoolCoder, hdr: &VP56Header, src: &[u8], alpha: bool) -> DecoderResult<()> {
571 let mut cr;
572 if hdr.multistream {
573 let off = hdr.offset as usize;
574 if !hdr.use_huffman {
575 let bc2 = BoolCoder::new(&src[off..])?;
576 cr = CoeffReader::Bool(bc2);
577 } else {
578 let br = BitReader::new(&src[off..], BitReaderMode::BE);
579 cr = CoeffReader::Huff(br);
580 }
581 } else {
582 cr = CoeffReader::None;
583 }
584
585 if hdr.is_intra {
586 br.reset_models(&mut self.models);
587 self.reset_mbtype_models();
588 } else {
589 self.decode_mode_prob_models(bc)?;
590 br.decode_mv_models(bc, &mut self.models.mv_models)?;
591 }
592 br.decode_coeff_models(bc, &mut self.models, hdr.is_intra)?;
593 if hdr.use_huffman {
594 for i in 0..2 {
595 self.models.vp6huff.dc_token_tree[i].build_codes(&self.models.coeff_models[i].dc_value_probs);
596 }
597 for i in 0..2 {
598 for mode in 0..3 {
599 for band in 0..6 {
600 self.models.vp6huff.ac_token_tree[i][mode][band].build_codes(&self.models.coeff_models[i].ac_val_probs[mode][band]);
601 }
602 }
603 }
604 for i in 0..2 {
605 self.models.vp6huff.zero_run_tree[i].build_codes_zero_run(&self.models.vp6models.zero_run_probs[i]);
606 }
607 }
608
609 if hdr.interlaced {
610 self.ilace_prob = bc.read_bits(8) as u8;
611 }
612
613 self.fstate = FrameState::new();
614 self.fstate.dc_quant = VP56_DC_QUANTS[hdr.quant as usize] * 4;
615 self.fstate.ac_quant = VP56_AC_QUANTS[hdr.quant as usize] * 4;
616 self.loop_thr = i16::from(VP56_FILTER_LIMITS[hdr.quant as usize]);
617
618 self.last_mbt = VPMBType::InterNoMV;
619 for vec in self.top_ctx.iter_mut() {
620 for el in vec.iter_mut() {
621 *el = 0;
622 }
623 }
624 self.last_dc = [[0; 4]; 3];
625 self.last_dc[0][1] = 0x80;
626 self.last_dc[0][2] = 0x80;
627 self.dc_pred.reset();
628
629 self.ilace_mb = false;
630 for mb_y in 0..self.mb_h {
631 self.fstate.mb_y = mb_y;
632 self.fstate.coeff_cat = [[0; 64]; 4];
633 self.fstate.last_idx = [24; 4];
634 for mb_x in 0..self.mb_w {
635 self.fstate.mb_x = mb_x;
636 self.decode_mb(dframe, bc, &mut cr, br, hdr, alpha)?;
637 self.dc_pred.next_mb();
638 }
639 self.dc_pred.update_row();
640 }
641 Ok(())
642 }
643 fn reset_mbtype_models(&mut self) {
644 const DEFAULT_XMITTED_PROBS: [[u8; 20]; 3] = [
645 [ 42, 69, 2, 1, 7, 1, 42, 44, 22, 6, 3, 1, 2, 0, 5, 1, 1, 0, 0, 0 ],
646 [ 8, 229, 1, 1, 8, 0, 0, 0, 0, 0, 2, 1, 1, 0, 0, 0, 1, 1, 0, 0 ],
647 [ 35, 122, 1, 1, 6, 1, 34, 46, 0, 0, 2, 1, 1, 0, 1, 0, 1, 1, 0, 0 ]
648 ];
649 self.models.prob_xmitted.copy_from_slice(&DEFAULT_XMITTED_PROBS);
650 }
651 fn decode_mode_prob_models(&mut self, bc: &mut BoolCoder) -> DecoderResult<()> {
652 for ctx in 0..3 {
653 if bc.read_prob(174) {
654 let idx = bc.read_bits(4) as usize;
655 for i in 0..20 {
656 self.models.prob_xmitted[ctx][i ^ 1] = VP56_MODE_VQ[ctx][idx][i];
657 }
658 }
659 if bc.read_prob(254) {
660 for set in 0..20 {
661 if bc.read_prob(205) {
662 let sign = bc.read_bool();
663 let diff = vp_tree!(bc, 171,
664 vp_tree!(bc, 83, 2, 1),
665 vp_tree!(bc, 199,
666 vp_tree!(bc, 140,
667 vp_tree!(bc, 125,
668 vp_tree!(bc, 104, 6, 5),
669 4
670 ),
671 3
672 ),
673 bc.read_bits(7)
674 )) * 4;
675 validate!(diff < 256);
676 let diff = diff as u8;
677 if !sign {
678 validate!(self.models.prob_xmitted[ctx][set ^ 1] <= 255 - diff);
679 self.models.prob_xmitted[ctx][set ^ 1] += diff;
680 } else {
681 validate!(self.models.prob_xmitted[ctx][set ^ 1] >= diff);
682 self.models.prob_xmitted[ctx][set ^ 1] -= diff;
683 }
684 }
685 }
686 }
687 }
688 for ctx in 0..3 {
689 let prob_xmitted = &self.models.prob_xmitted[ctx];
690 for mode in 0..10 {
691 let mdl = &mut self.models.mbtype_models[ctx][mode];
692 let mut cnt = [0u32; 10];
693 let mut total = 0;
694 for i in 0..10 {
695 if i == mode { continue; }
696 cnt[i] = 100 * u32::from(prob_xmitted[i * 2]);
697 total += cnt[i];
698 }
699 let sum = u32::from(prob_xmitted[mode * 2]) + u32::from(prob_xmitted[mode * 2 + 1]);
700 mdl.probs[9] = 255 - rescale_mb_mode_prob(u32::from(prob_xmitted[mode * 2 + 1]), sum);
701
702 let inter_mv0_weight = (cnt[0] as u32) + (cnt[2] as u32);
703 let inter_mv1_weight = (cnt[3] as u32) + (cnt[4] as u32);
704 let gold_mv0_weight = (cnt[5] as u32) + (cnt[6] as u32);
705 let gold_mv1_weight = (cnt[8] as u32) + (cnt[9] as u32);
706 let mix_weight = (cnt[1] as u32) + (cnt[7] as u32);
707 mdl.probs[0] = 1 + rescale_mb_mode_prob(inter_mv0_weight + inter_mv1_weight, total);
708 mdl.probs[1] = 1 + rescale_mb_mode_prob(inter_mv0_weight, inter_mv0_weight + inter_mv1_weight);
709 mdl.probs[2] = 1 + rescale_mb_mode_prob(mix_weight, mix_weight + gold_mv0_weight + gold_mv1_weight);
710 mdl.probs[3] = 1 + rescale_mb_mode_prob(cnt[0] as u32, inter_mv0_weight);
711 mdl.probs[4] = 1 + rescale_mb_mode_prob(cnt[3] as u32, inter_mv1_weight);
712 mdl.probs[5] = 1 + rescale_mb_mode_prob(cnt[1], mix_weight);
713 mdl.probs[6] = 1 + rescale_mb_mode_prob(gold_mv0_weight, gold_mv0_weight + gold_mv1_weight);
714 mdl.probs[7] = 1 + rescale_mb_mode_prob(cnt[5], gold_mv0_weight);
715 mdl.probs[8] = 1 + rescale_mb_mode_prob(cnt[8], gold_mv1_weight);
716 }
717 }
718 Ok(())
719 }
720 fn find_mv_pred(&self, ref_id: u8) -> (usize, MV, MV, MV) {
721 const CAND_POS: [(i8, i8); 12] = [
722 (-1, 0), ( 0, -1),
723 (-1, -1), (-1, 1),
724 (-2, 0), ( 0, -2),
725 (-1, -2), (-2, -1),
726 (-2, 1), (-1, 2),
727 (-2, -2), (-2, 2)
728 ];
729
730 let mut nearest_mv = ZERO_MV;
731 let mut near_mv = ZERO_MV;
732 let mut pred_mv = ZERO_MV;
733 let mut num_mv: usize = 0;
734
735 for (i, (yoff, xoff)) in CAND_POS.iter().enumerate() {
736 let cx = (self.fstate.mb_x as isize) + (*xoff as isize);
737 let cy = (self.fstate.mb_y as isize) + (*yoff as isize);
738 if (cx < 0) || (cy < 0) {
739 continue;
740 }
741 let cx = cx as usize;
742 let cy = cy as usize;
743 if (cx >= self.mb_w) || (cy >= self.mb_h) {
744 continue;
745 }
746 let mb_pos = cx + cy * self.mb_w;
747 let mv = self.mb_info[mb_pos].mv;
748 if (self.mb_info[mb_pos].mb_type.get_ref_id() != ref_id) || (mv == ZERO_MV) {
749 continue;
750 }
751 if num_mv == 0 {
752 nearest_mv = mv;
753 num_mv += 1;
754 if (self.version > 5) && (i < 2) {
755 pred_mv = mv;
756 }
757 } else if mv != nearest_mv {
758 near_mv = mv;
759 num_mv += 1;
760 break;
761 }
762 }
763
764 (num_mv, nearest_mv, near_mv, pred_mv)
765 }
766 fn decode_mv(&self, bc: &mut BoolCoder, br: &mut dyn VP56Parser) -> MV {
767 let x = br.decode_mv(bc, &self.models.mv_models[0]);
768 let y = br.decode_mv(bc, &self.models.mv_models[1]);
769 MV{ x, y }
770 }
771 fn decode_mb_type(&mut self, bc: &mut BoolCoder, ctx: usize) -> DecoderResult<VPMBType> {
772 let probs = &self.models.mbtype_models[ctx][map_mb_type(self.last_mbt)].probs;
773 if !bc.read_prob(probs[9]) {
774 self.last_mbt = vp_tree!(
775 bc, probs[0],
776 vp_tree!(bc, probs[1],
777 vp_tree!(bc, probs[3], VPMBType::InterNoMV, VPMBType::InterMV),
778 vp_tree!(bc, probs[4], VPMBType::InterNearest, VPMBType::InterNear)
779 ),
780 vp_tree!(bc, probs[2],
781 vp_tree!(bc, probs[5], VPMBType::Intra, VPMBType::InterFourMV),
782 vp_tree!(bc, probs[6],
783 vp_tree!(bc, probs[7], VPMBType::GoldenNoMV, VPMBType::GoldenMV),
784 vp_tree!(bc, probs[8], VPMBType::GoldenNearest, VPMBType::GoldenNear)
785 )
786 )
787 );
788 }
789 Ok(self.last_mbt)
790 }
791 #[allow(clippy::cognitive_complexity)]
792 fn decode_mb(&mut self, frm: &mut NASimpleVideoFrame<u8>, bc: &mut BoolCoder, cr: &mut CoeffReader, br: &mut dyn VP56Parser, hdr: &VP56Header, alpha: bool) -> DecoderResult<()> {
793 const FOURMV_SUB_TYPE: [VPMBType; 4] = [ VPMBType::InterNoMV, VPMBType::InterMV, VPMBType::InterNearest, VPMBType::InterNear ];
794
795 let mb_x = self.fstate.mb_x;
796 let mb_y = self.fstate.mb_y;
797 self.coeffs = [[0; 64]; 6];
798 let mb_pos = mb_x + mb_y * self.mb_w;
799 let mut four_mv = [ZERO_MV; 4];
800 let mut four_mbt = [VPMBType::Intra; 4];
801
802 if hdr.interlaced {
803 let iprob = self.ilace_prob;
804 let prob = if mb_x == 0 {
805 iprob
806 } else if !self.ilace_mb {
807 iprob + (((256 - u16::from(iprob)) >> 1) as u8)
808 } else {
809 iprob - (iprob >> 1)
810 };
811 self.ilace_mb = bc.read_prob(prob);
812 }
813
814 let (num_mv, nearest_mv, near_mv, pred_mv) = if hdr.is_intra {
815 (0, ZERO_MV, ZERO_MV, ZERO_MV)
816 } else { self.find_mv_pred(VP_REF_INTER) };
817 let mb_type = if hdr.is_intra {
818 VPMBType::Intra
819 } else {
820 self.decode_mb_type(bc, (num_mv + 1) % 3)?
821 };
822 self.mb_info[mb_pos].mb_type = mb_type;
823 if mb_type.get_ref_id() != VP_REF_GOLDEN {
824 match mb_type {
825 VPMBType::Intra |
826 VPMBType::InterNoMV => {
827 self.mb_info[mb_pos].mv = ZERO_MV;
828 },
829 VPMBType::InterMV => {
830 let diff_mv = self.decode_mv(bc, br);
831 self.mb_info[mb_pos].mv = pred_mv + diff_mv;
832 },
833 VPMBType::InterNearest => {
834 self.mb_info[mb_pos].mv = nearest_mv;
835 },
836 VPMBType::InterNear => {
837 self.mb_info[mb_pos].mv = near_mv;
838 },
839 VPMBType::InterFourMV => {
840 for i in 0..4 {
841 four_mbt[i] = FOURMV_SUB_TYPE[bc.read_bits(2) as usize];
842 }
843 for i in 0..4 {
844 match four_mbt[i] {
845 VPMBType::InterNoMV => {},
846 VPMBType::InterMV => {
847 let diff_mv = self.decode_mv(bc, br);
848 four_mv[i] = pred_mv + diff_mv;
849 },
850 VPMBType::InterNearest => {
851 four_mv[i] = nearest_mv;
852 },
853 VPMBType::InterNear => {
854 four_mv[i] = near_mv;
855 },
856 _ => unreachable!(),
857 };
858 }
859 self.mb_info[mb_pos].mv = four_mv[3];
860 },
861 _ => unreachable!(),
862 };
863 } else {
864 let (_num_mv, nearest_mv, near_mv, pred_mv) = self.find_mv_pred(VP_REF_GOLDEN);
865 match mb_type {
866 VPMBType::GoldenNoMV => {
867 self.mb_info[mb_pos].mv = ZERO_MV;
868 },
869 VPMBType::GoldenMV => {
870 let diff_mv = self.decode_mv(bc, br);
871 self.mb_info[mb_pos].mv = pred_mv + diff_mv;
872 },
873 VPMBType::GoldenNearest => {
874 self.mb_info[mb_pos].mv = nearest_mv;
875 },
876 VPMBType::GoldenNear => {
877 self.mb_info[mb_pos].mv = near_mv;
878 },
879 _ => unreachable!(),
880 };
881 }
882 if !mb_type.is_intra() && (mb_type != VPMBType::InterFourMV) {
883 self.do_mc(br, frm, mb_type, self.mb_info[mb_pos].mv, alpha);
884 } else if mb_type == VPMBType::InterFourMV {
885 self.do_fourmv(br, frm, &four_mv, alpha);
886 }
887
888 for blk_no in 0..4 {
889 self.fstate.plane = if !alpha { 0 } else { 3 };
890 self.fstate.ctx_idx = blk_no >> 1;
891 self.fstate.top_ctx = self.top_ctx[self.fstate.plane][mb_x * 2 + (blk_no & 1)];
892 match cr {
893 CoeffReader::None => {
894 br.decode_block(bc, &mut self.coeffs[blk_no], &self.models.coeff_models[0], &self.models.vp6models, &mut self.fstate)?;
895 },
896 CoeffReader::Bool(ref mut bcc) => {
897 br.decode_block(bcc, &mut self.coeffs[blk_no], &self.models.coeff_models[0], &self.models.vp6models, &mut self.fstate)?;
898 },
899 CoeffReader::Huff(ref mut brc) => {
900 br.decode_block_huff(brc, &mut self.coeffs[blk_no], &self.models.vp6models, &self.models.vp6huff, &mut self.fstate)?;
901 },
902 };
903 self.top_ctx[self.fstate.plane][mb_x * 2 + (blk_no & 1)] = self.fstate.top_ctx;
904 self.predict_dc(mb_type, mb_pos, blk_no, alpha);
905
906 let bx = mb_x * 2 + (blk_no & 1);
907 let by = mb_y * 2 + (blk_no >> 1);
908 let has_ac = self.fstate.last_idx[self.fstate.ctx_idx] > 0;
909 if mb_type.is_intra() {
910 if !self.ilace_mb {
911 if has_ac {
912 vp_put_block(&mut self.coeffs[blk_no], bx, by, self.fstate.plane, frm);
913 } else {
914 vp_put_block_dc(&mut self.coeffs[blk_no], bx, by, self.fstate.plane, frm);
915 }
916 } else {
917 vp_put_block_ilace(&mut self.coeffs[blk_no], bx, by, self.fstate.plane, frm);
918 }
919 } else {
920 if !self.ilace_mb {
921 if has_ac {
922 vp_add_block(&mut self.coeffs[blk_no], bx, by, self.fstate.plane, frm);
923 } else {
924 vp_add_block_dc(&mut self.coeffs[blk_no], bx, by, self.fstate.plane, frm);
925 }
926 } else {
927 vp_add_block_ilace(&mut self.coeffs[blk_no], bx, by, self.fstate.plane, frm);
928 }
929 }
930 }
931 for blk_no in 4..6 {
932 self.fstate.plane = blk_no - 3;
933 self.fstate.ctx_idx = blk_no - 2;
934 self.fstate.top_ctx = self.top_ctx[self.fstate.plane][mb_x];
935 match cr {
936 CoeffReader::None => {
937 br.decode_block(bc, &mut self.coeffs[blk_no], &self.models.coeff_models[1], &self.models.vp6models, &mut self.fstate)?;
938 },
939 CoeffReader::Bool(ref mut bcc) => {
940 br.decode_block(bcc, &mut self.coeffs[blk_no], &self.models.coeff_models[1], &self.models.vp6models, &mut self.fstate)?;
941 },
942 CoeffReader::Huff(ref mut brc) => {
943 br.decode_block_huff(brc, &mut self.coeffs[blk_no], &self.models.vp6models, &self.models.vp6huff, &mut self.fstate)?;
944 },
945 };
946 self.top_ctx[self.fstate.plane][mb_x] = self.fstate.top_ctx;
947 self.predict_dc(mb_type, mb_pos, blk_no, alpha);
948 if !alpha {
949 let has_ac = self.fstate.last_idx[self.fstate.ctx_idx] > 0;
950 if mb_type.is_intra() {
951 if has_ac {
952 vp_put_block(&mut self.coeffs[blk_no], mb_x, mb_y, self.fstate.plane, frm);
953 } else {
954 vp_put_block_dc(&mut self.coeffs[blk_no], mb_x, mb_y, self.fstate.plane, frm);
955 }
956 } else {
957 if has_ac {
958 vp_add_block(&mut self.coeffs[blk_no], mb_x, mb_y, self.fstate.plane, frm);
959 } else {
960 vp_add_block_dc(&mut self.coeffs[blk_no], mb_x, mb_y, self.fstate.plane, frm);
961 }
962 }
963 }
964 }
965 Ok(())
966 }
967 fn do_mc(&mut self, br: &dyn VP56Parser, frm: &mut NASimpleVideoFrame<u8>, mb_type: VPMBType, mv: MV, alpha: bool) {
968 let x = self.fstate.mb_x * 16;
969 let y = self.fstate.mb_y * 16;
970 let plane = if !alpha { 0 } else { 3 };
971 let src = if mb_type.get_ref_id() == VP_REF_INTER {
972 self.shuf.get_last().unwrap()
973 } else {
974 self.shuf.get_golden().unwrap()
975 };
976
977 br.mc_block(frm, self.mc_buf.clone(), src.clone(), plane, x + 0, y + 0, mv, self.loop_thr);
978 br.mc_block(frm, self.mc_buf.clone(), src.clone(), plane, x + 8, y + 0, mv, self.loop_thr);
979 br.mc_block(frm, self.mc_buf.clone(), src.clone(), plane, x + 0, y + 8, mv, self.loop_thr);
980 br.mc_block(frm, self.mc_buf.clone(), src.clone(), plane, x + 8, y + 8, mv, self.loop_thr);
981 if !alpha {
982 let x = self.fstate.mb_x * 8;
983 let y = self.fstate.mb_y * 8;
984 br.mc_block(frm, self.mc_buf.clone(), src.clone(), 1, x, y, mv, self.loop_thr);
985 br.mc_block(frm, self.mc_buf.clone(), src, 2, x, y, mv, self.loop_thr);
986 }
987 }
988 fn do_fourmv(&mut self, br: &dyn VP56Parser, frm: &mut NASimpleVideoFrame<u8>, mvs: &[MV; 4], alpha: bool) {
989 let x = self.fstate.mb_x * 16;
990 let y = self.fstate.mb_y * 16;
991 let plane = if !alpha { 0 } else { 3 };
992 let src = self.shuf.get_last().unwrap();
993 for blk_no in 0..4 {
994 br.mc_block(frm, self.mc_buf.clone(), src.clone(),
995 plane, x + (blk_no & 1) * 8, y + (blk_no & 2) * 4,
996 mvs[blk_no], self.loop_thr);
997 }
998 if !alpha {
999 let x = self.fstate.mb_x * 8;
1000 let y = self.fstate.mb_y * 8;
1001 let sum = mvs[0] + mvs[1] + mvs[2] + mvs[3];
1002 let mv = MV { x: sum.x / 4, y: sum.y / 4 };
1003 br.mc_block(frm, self.mc_buf.clone(), src.clone(), 1, x, y, mv, self.loop_thr);
1004 br.mc_block(frm, self.mc_buf.clone(), src, 2, x, y, mv, self.loop_thr);
1005 }
1006 }
1007 fn predict_dc(&mut self, mb_type: VPMBType, _mb_pos: usize, blk_no: usize, _alpha: bool) {
1008 let is_luma = blk_no < 4;
1009 let (plane, dcs) = match blk_no {
1010 4 => (1, &mut self.dc_pred.dc_u),
1011 5 => (2, &mut self.dc_pred.dc_v),
1012 _ => (0, &mut self.dc_pred.dc_y),
1013 };
1014 let (dc_ref, dc_idx) = if is_luma {
1015 (&mut self.dc_pred.ref_y, self.dc_pred.y_idx + (blk_no & 1))
1016 } else {
1017 (&mut self.dc_pred.ref_c, self.dc_pred.c_idx)
1018 };
1019 let ref_id = mb_type.get_ref_id();
1020 let mut dc_pred = 0;
1021 let mut count = 0;
1022 let has_left_blk = is_luma && ((blk_no & 1) == 1);
1023 if has_left_blk || self.dc_pred.ref_left == ref_id {
1024 dc_pred += match blk_no {
1025 0 | 1 => self.dc_pred.ldc_y[0],
1026 2 | 3 => self.dc_pred.ldc_y[1],
1027 4 => self.dc_pred.ldc_u,
1028 _ => self.dc_pred.ldc_v,
1029 };
1030 count += 1;
1031 }
1032 if dc_ref[dc_idx] == ref_id {
1033 dc_pred += dcs[dc_idx];
1034 count += 1;
1035 }
1036 if self.version == 5 {
1037 if (count < 2) && (dc_ref[dc_idx - 1] == ref_id) {
1038 dc_pred += dcs[dc_idx - 1];
1039 count += 1;
1040 }
1041 if (count < 2) && (dc_ref[dc_idx + 1] == ref_id) {
1042 dc_pred += dcs[dc_idx + 1];
1043 count += 1;
1044 }
1045 }
1046 if count == 0 {
1047 dc_pred = self.last_dc[ref_id as usize][plane];
1048 } else if count == 2 {
1049 dc_pred /= 2;
1050 }
1051 self.coeffs[blk_no][0] += dc_pred;
1052
1053 let dc = self.coeffs[blk_no][0];
1054 if blk_no != 4 { // update top block reference only for the second chroma component
1055 dc_ref[dc_idx] = ref_id;
1056 }
1057 match blk_no {
1058 0 | 1 => {
1059 self.dc_pred.ldc_y[0] = dc;
1060 },
1061 2 | 3 => {
1062 self.dc_pred.ldc_y[1] = dc;
1063 },
1064 4 => {
1065 self.dc_pred.ldc_u = dc;
1066 },
1067 _ => {
1068 self.dc_pred.ldc_v = dc;
1069 self.dc_pred.ref_left = ref_id;
1070 },
1071 };
1072 dcs[dc_idx] = dc;
1073
1074 self.last_dc[ref_id as usize][plane] = dc;
1075 self.coeffs[blk_no][0] = self.coeffs[blk_no][0].wrapping_mul(self.fstate.dc_quant);
1076 }
1077 }
1078
1079 const VP56_DC_QUANTS: [i16; 64] = [
1080 47, 47, 47, 47, 45, 43, 43, 43,
1081 43, 43, 42, 41, 41, 40, 40, 40,
1082 40, 35, 35, 35, 35, 33, 33, 33,
1083 33, 32, 32, 32, 27, 27, 26, 26,
1084 25, 25, 24, 24, 23, 23, 19, 19,
1085 19, 19, 18, 18, 17, 16, 16, 16,
1086 16, 16, 15, 11, 11, 11, 10, 10,
1087 9, 8, 7, 5, 3, 3, 2, 2
1088 ];
1089 const VP56_AC_QUANTS: [i16; 64] = [
1090 94, 92, 90, 88, 86, 82, 78, 74,
1091 70, 66, 62, 58, 54, 53, 52, 51,
1092 50, 49, 48, 47, 46, 45, 44, 43,
1093 42, 40, 39, 37, 36, 35, 34, 33,
1094 32, 31, 30, 29, 28, 27, 26, 25,
1095 24, 23, 22, 21, 20, 19, 18, 17,
1096 16, 15, 14, 13, 12, 11, 10, 9,
1097 8, 7, 6, 5, 4, 3, 2, 1
1098 ];
1099
1100 const VP56_FILTER_LIMITS: [u8; 64] = [
1101 14, 14, 13, 13, 12, 12, 10, 10,
1102 10, 10, 8, 8, 8, 8, 8, 8,
1103 8, 8, 8, 8, 8, 8, 8, 8,
1104 8, 8, 8, 8, 8, 8, 8, 8,
1105 8, 8, 8, 8, 7, 7, 7, 7,
1106 7, 7, 6, 6, 6, 6, 6, 6,
1107 5, 5, 5, 5, 4, 4, 4, 4,
1108 4, 4, 4, 3, 3, 3, 3, 2
1109 ];
1110
1111 const VP56_MODE_VQ: [[[u8; 20]; 16]; 3] = [
1112 [
1113 [ 9, 15, 32, 25, 7, 19, 9, 21, 1, 12, 14, 12, 3, 18, 14, 23, 3, 10, 0, 4 ],
1114 [ 48, 39, 1, 2, 11, 27, 29, 44, 7, 27, 1, 4, 0, 3, 1, 6, 1, 2, 0, 0 ],
1115 [ 21, 32, 1, 2, 4, 10, 32, 43, 6, 23, 2, 3, 1, 19, 1, 6, 12, 21, 0, 7 ],
1116 [ 69, 83, 0, 0, 0, 2, 10, 29, 3, 12, 0, 1, 0, 3, 0, 3, 2, 2, 0, 0 ],
1117 [ 11, 20, 1, 4, 18, 36, 43, 48, 13, 35, 0, 2, 0, 5, 3, 12, 1, 2, 0, 0 ],
1118 [ 70, 44, 0, 1, 2, 10, 37, 46, 8, 26, 0, 2, 0, 2, 0, 2, 0, 1, 0, 0 ],
1119 [ 8, 15, 0, 1, 8, 21, 74, 53, 22, 42, 0, 1, 0, 2, 0, 3, 1, 2, 0, 0 ],
1120 [ 141, 42, 0, 0, 1, 4, 11, 24, 1, 11, 0, 1, 0, 1, 0, 2, 0, 0, 0, 0 ],
1121 [ 8, 19, 4, 10, 24, 45, 21, 37, 9, 29, 0, 3, 1, 7, 11, 25, 0, 2, 0, 1 ],
1122 [ 46, 42, 0, 1, 2, 10, 54, 51, 10, 30, 0, 2, 0, 2, 0, 1, 0, 1, 0, 0 ],
1123 [ 28, 32, 0, 0, 3, 10, 75, 51, 14, 33, 0, 1, 0, 2, 0, 1, 1, 2, 0, 0 ],
1124 [ 100, 46, 0, 1, 3, 9, 21, 37, 5, 20, 0, 1, 0, 2, 1, 2, 0, 1, 0, 0 ],
1125 [ 27, 29, 0, 1, 9, 25, 53, 51, 12, 34, 0, 1, 0, 3, 1, 5, 0, 2, 0, 0 ],
1126 [ 80, 38, 0, 0, 1, 4, 69, 33, 5, 16, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0 ],
1127 [ 16, 20, 0, 0, 2, 8, 104, 49, 15, 33, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0 ],
1128 [ 194, 16, 0, 0, 1, 1, 1, 9, 1, 3, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0 ],
1129 ], [
1130 [ 41, 22, 1, 0, 1, 31, 0, 0, 0, 0, 0, 1, 1, 7, 0, 1, 98, 25, 4, 10 ],
1131 [ 123, 37, 6, 4, 1, 27, 0, 0, 0, 0, 5, 8, 1, 7, 0, 1, 12, 10, 0, 2 ],
1132 [ 26, 14, 14, 12, 0, 24, 0, 0, 0, 0, 55, 17, 1, 9, 0, 36, 5, 7, 1, 3 ],
1133 [ 209, 5, 0, 0, 0, 27, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0 ],
1134 [ 2, 5, 4, 5, 0, 121, 0, 0, 0, 0, 0, 3, 2, 4, 1, 4, 2, 2, 0, 1 ],
1135 [ 175, 5, 0, 1, 0, 48, 0, 0, 0, 0, 0, 2, 0, 1, 0, 2, 0, 1, 0, 0 ],
1136 [ 83, 5, 2, 3, 0, 102, 0, 0, 0, 0, 1, 3, 0, 2, 0, 1, 0, 0, 0, 0 ],
1137 [ 233, 6, 0, 0, 0, 8, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0 ],
1138 [ 34, 16, 112, 21, 1, 28, 0, 0, 0, 0, 6, 8, 1, 7, 0, 3, 2, 5, 0, 2 ],
1139 [ 159, 35, 2, 2, 0, 25, 0, 0, 0, 0, 3, 6, 0, 5, 0, 1, 4, 4, 0, 1 ],
1140 [ 75, 39, 5, 7, 2, 48, 0, 0, 0, 0, 3, 11, 2, 16, 1, 4, 7, 10, 0, 2 ],
1141 [ 212, 21, 0, 1, 0, 9, 0, 0, 0, 0, 1, 2, 0, 2, 0, 0, 2, 2, 0, 0 ],
1142 [ 4, 2, 0, 0, 0, 172, 0, 0, 0, 0, 0, 1, 0, 2, 0, 0, 2, 0, 0, 0 ],
1143 [ 187, 22, 1, 1, 0, 17, 0, 0, 0, 0, 3, 6, 0, 4, 0, 1, 4, 4, 0, 1 ],
1144 [ 133, 6, 1, 2, 1, 70, 0, 0, 0, 0, 0, 2, 0, 4, 0, 3, 1, 1, 0, 0 ],
1145 [ 251, 1, 0, 0, 0, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 ],
1146 ], [
1147 [ 2, 3, 2, 3, 0, 2, 0, 2, 0, 0, 11, 4, 1, 4, 0, 2, 3, 2, 0, 4 ],
1148 [ 49, 46, 3, 4, 7, 31, 42, 41, 0, 0, 2, 6, 1, 7, 1, 4, 2, 4, 0, 1 ],
1149 [ 26, 25, 1, 1, 2, 10, 67, 39, 0, 0, 1, 1, 0, 14, 0, 2, 31, 26, 1, 6 ],
1150 [ 103, 46, 1, 2, 2, 10, 33, 42, 0, 0, 1, 4, 0, 3, 0, 1, 1, 3, 0, 0 ],
1151 [ 14, 31, 9, 13, 14, 54, 22, 29, 0, 0, 2, 6, 4, 18, 6, 13, 1, 5, 0, 1 ],
1152 [ 85, 39, 0, 0, 1, 9, 69, 40, 0, 0, 0, 1, 0, 3, 0, 1, 2, 3, 0, 0 ],
1153 [ 31, 28, 0, 0, 3, 14, 130, 34, 0, 0, 0, 1, 0, 3, 0, 1, 3, 3, 0, 1 ],
1154 [ 171, 25, 0, 0, 1, 5, 25, 21, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0 ],
1155 [ 17, 21, 68, 29, 6, 15, 13, 22, 0, 0, 6, 12, 3, 14, 4, 10, 1, 7, 0, 3 ],
1156 [ 51, 39, 0, 1, 2, 12, 91, 44, 0, 0, 0, 2, 0, 3, 0, 1, 2, 3, 0, 1 ],
1157 [ 81, 25, 0, 0, 2, 9, 106, 26, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0 ],
1158 [ 140, 37, 0, 1, 1, 8, 24, 33, 0, 0, 1, 2, 0, 2, 0, 1, 1, 2, 0, 0 ],
1159 [ 14, 23, 1, 3, 11, 53, 90, 31, 0, 0, 0, 3, 1, 5, 2, 6, 1, 2, 0, 0 ],
1160 [ 123, 29, 0, 0, 1, 7, 57, 30, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0 ],
1161 [ 13, 14, 0, 0, 4, 20, 175, 20, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0 ],
1162 [ 202, 23, 0, 0, 1, 3, 2, 9, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0 ],
1163 ]
1164 ];
1165