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