2 * common functions for Indeo Video Interactive codecs (Indeo4 and Indeo5)
4 * Copyright (c) 2009 Maxim Poliakovski
6 * This file is part of Libav.
8 * Libav is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU Lesser General Public
10 * License as published by the Free Software Foundation; either
11 * version 2.1 of the License, or (at your option) any later version.
13 * Libav is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * Lesser General Public License for more details.
18 * You should have received a copy of the GNU Lesser General Public
19 * License along with Libav; if not, write to the Free Software
20 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
25 * This file contains functions and data shared by both Indeo4 and
29 #define BITSTREAM_READER_LE
30 #include "libavutil/attributes.h"
35 #include "ivi_common.h"
38 extern const IVIHuffDesc ff_ivi_mb_huff_desc[8]; ///< static macroblock huffman tables
39 extern const IVIHuffDesc ff_ivi_blk_huff_desc[8]; ///< static block huffman tables
41 VLC ff_ivi_mb_vlc_tabs [8];
42 VLC ff_ivi_blk_vlc_tabs[8];
45 * Reverse "nbits" bits of the value "val" and return the result
46 * in the least significant bits.
48 static uint16_t inv_bits(uint16_t val, int nbits)
53 res = ff_reverse[val] >> (8-nbits);
55 res = ((ff_reverse[val & 0xFF] << 8) + (ff_reverse[val >> 8])) >> (16-nbits);
60 int ff_ivi_create_huff_from_desc(const IVIHuffDesc *cb, VLC *vlc, int flag)
62 int pos, i, j, codes_per_row, prefix, not_last_row;
63 uint16_t codewords[256]; /* FIXME: move this temporal storage out? */
66 pos = 0; /* current position = 0 */
68 for (i = 0; i < cb->num_rows; i++) {
69 codes_per_row = 1 << cb->xbits[i];
70 not_last_row = (i != cb->num_rows - 1);
71 prefix = ((1 << i) - 1) << (cb->xbits[i] + not_last_row);
73 for (j = 0; j < codes_per_row; j++) {
74 if (pos >= 256) /* Some Indeo5 codebooks can have more than 256 */
75 break; /* elements, but only 256 codes are allowed! */
77 bits[pos] = i + cb->xbits[i] + not_last_row;
78 if (bits[pos] > IVI_VLC_BITS)
79 return -1; /* invalid descriptor */
81 codewords[pos] = inv_bits((prefix | j), bits[pos]);
89 /* number of codewords = pos */
90 return init_vlc(vlc, IVI_VLC_BITS, pos, bits, 1, 1, codewords, 2, 2,
91 (flag ? INIT_VLC_USE_NEW_STATIC : 0) | INIT_VLC_LE);
94 void ff_ivi_init_static_vlc(void)
97 static VLC_TYPE table_data[8192 * 16][2];
98 static int initialized_vlcs = 0;
100 if (initialized_vlcs)
102 for (i = 0; i < 8; i++) {
103 ff_ivi_mb_vlc_tabs[i].table = table_data + i * 2 * 8192;
104 ff_ivi_mb_vlc_tabs[i].table_allocated = 8192;
105 ff_ivi_create_huff_from_desc(&ff_ivi_mb_huff_desc[i], &ff_ivi_mb_vlc_tabs[i], 1);
106 ff_ivi_blk_vlc_tabs[i].table = table_data + (i * 2 + 1) * 8192;
107 ff_ivi_blk_vlc_tabs[i].table_allocated = 8192;
108 ff_ivi_create_huff_from_desc(&ff_ivi_blk_huff_desc[i], &ff_ivi_blk_vlc_tabs[i], 1);
110 initialized_vlcs = 1;
113 int ff_ivi_dec_huff_desc(GetBitContext *gb, int desc_coded, int which_tab,
114 IVIHuffTab *huff_tab, AVCodecContext *avctx)
117 IVIHuffDesc new_huff;
120 /* select default table */
121 huff_tab->tab = (which_tab) ? &ff_ivi_blk_vlc_tabs[7]
122 : &ff_ivi_mb_vlc_tabs [7];
124 huff_tab->tab_sel = get_bits(gb, 3);
125 if (huff_tab->tab_sel == 7) {
126 /* custom huffman table (explicitly encoded) */
127 new_huff.num_rows = get_bits(gb, 4);
128 if (!new_huff.num_rows) {
129 av_log(avctx, AV_LOG_ERROR, "Empty custom Huffman table!\n");
130 return AVERROR_INVALIDDATA;
133 for (i = 0; i < new_huff.num_rows; i++)
134 new_huff.xbits[i] = get_bits(gb, 4);
136 /* Have we got the same custom table? Rebuild if not. */
137 if (ff_ivi_huff_desc_cmp(&new_huff, &huff_tab->cust_desc)) {
138 ff_ivi_huff_desc_copy(&huff_tab->cust_desc, &new_huff);
140 if (huff_tab->cust_tab.table)
141 ff_free_vlc(&huff_tab->cust_tab);
142 result = ff_ivi_create_huff_from_desc(&huff_tab->cust_desc,
143 &huff_tab->cust_tab, 0);
145 huff_tab->cust_desc.num_rows = 0; // reset faulty description
146 av_log(avctx, AV_LOG_ERROR,
147 "Error while initializing custom vlc table!\n");
151 huff_tab->tab = &huff_tab->cust_tab;
153 /* select one of predefined tables */
154 huff_tab->tab = (which_tab) ? &ff_ivi_blk_vlc_tabs[huff_tab->tab_sel]
155 : &ff_ivi_mb_vlc_tabs [huff_tab->tab_sel];
162 int ff_ivi_huff_desc_cmp(const IVIHuffDesc *desc1, const IVIHuffDesc *desc2)
164 return desc1->num_rows != desc2->num_rows
165 || memcmp(desc1->xbits, desc2->xbits, desc1->num_rows);
168 void ff_ivi_huff_desc_copy(IVIHuffDesc *dst, const IVIHuffDesc *src)
170 dst->num_rows = src->num_rows;
171 memcpy(dst->xbits, src->xbits, src->num_rows);
174 av_cold int ff_ivi_init_planes(IVIPlaneDesc *planes, const IVIPicConfig *cfg)
177 uint32_t b_width, b_height, align_fac, width_aligned, height_aligned, buf_size;
180 ff_ivi_free_buffers(planes);
182 /* fill in the descriptor of the luminance plane */
183 planes[0].width = cfg->pic_width;
184 planes[0].height = cfg->pic_height;
185 planes[0].num_bands = cfg->luma_bands;
187 /* fill in the descriptors of the chrominance planes */
188 planes[1].width = planes[2].width = (cfg->pic_width + 3) >> 2;
189 planes[1].height = planes[2].height = (cfg->pic_height + 3) >> 2;
190 planes[1].num_bands = planes[2].num_bands = cfg->chroma_bands;
192 for (p = 0; p < 3; p++) {
193 planes[p].bands = av_mallocz(planes[p].num_bands * sizeof(IVIBandDesc));
194 if (!planes[p].bands)
195 return AVERROR(ENOMEM);
197 /* select band dimensions: if there is only one band then it
198 * has the full size, if there are several bands each of them
199 * has only half size */
200 b_width = planes[p].num_bands == 1 ? planes[p].width : (planes[p].width + 1) >> 1;
201 b_height = planes[p].num_bands == 1 ? planes[p].height : (planes[p].height + 1) >> 1;
203 /* luma band buffers will be aligned on 16x16 (max macroblock size) */
204 /* chroma band buffers will be aligned on 8x8 (max macroblock size) */
205 align_fac = p ? 8 : 16;
206 width_aligned = FFALIGN(b_width , align_fac);
207 height_aligned = FFALIGN(b_height, align_fac);
208 buf_size = width_aligned * height_aligned * sizeof(int16_t);
210 for (b = 0; b < planes[p].num_bands; b++) {
211 band = &planes[p].bands[b]; /* select appropriate plane/band */
214 band->width = b_width;
215 band->height = b_height;
216 band->pitch = width_aligned;
217 band->aheight = height_aligned;
218 band->bufs[0] = av_mallocz(buf_size);
219 band->bufs[1] = av_mallocz(buf_size);
220 if (!band->bufs[0] || !band->bufs[1])
221 return AVERROR(ENOMEM);
223 /* allocate the 3rd band buffer for scalability mode */
224 if (cfg->luma_bands > 1) {
225 band->bufs[2] = av_mallocz(buf_size);
227 return AVERROR(ENOMEM);
230 planes[p].bands[0].blk_vlc.cust_desc.num_rows = 0; /* reset custom vlc */
237 av_cold void ff_ivi_free_buffers(IVIPlaneDesc *planes)
241 for (p = 0; p < 3; p++) {
242 for (b = 0; b < planes[p].num_bands; b++) {
243 av_freep(&planes[p].bands[b].bufs[0]);
244 av_freep(&planes[p].bands[b].bufs[1]);
245 av_freep(&planes[p].bands[b].bufs[2]);
247 if (planes[p].bands[b].blk_vlc.cust_tab.table)
248 ff_free_vlc(&planes[p].bands[b].blk_vlc.cust_tab);
249 for (t = 0; t < planes[p].bands[b].num_tiles; t++)
250 av_freep(&planes[p].bands[b].tiles[t].mbs);
251 av_freep(&planes[p].bands[b].tiles);
253 av_freep(&planes[p].bands);
257 av_cold int ff_ivi_init_tiles(IVIPlaneDesc *planes, int tile_width, int tile_height)
259 int p, b, x, y, x_tiles, y_tiles, t_width, t_height;
261 IVITile *tile, *ref_tile;
263 for (p = 0; p < 3; p++) {
264 t_width = !p ? tile_width : (tile_width + 3) >> 2;
265 t_height = !p ? tile_height : (tile_height + 3) >> 2;
267 if (!p && planes[0].num_bands == 4) {
272 for (b = 0; b < planes[p].num_bands; b++) {
273 band = &planes[p].bands[b];
274 x_tiles = IVI_NUM_TILES(band->width, t_width);
275 y_tiles = IVI_NUM_TILES(band->height, t_height);
276 band->num_tiles = x_tiles * y_tiles;
278 av_freep(&band->tiles);
279 band->tiles = av_mallocz(band->num_tiles * sizeof(IVITile));
281 return AVERROR(ENOMEM);
285 /* use the first luma band as reference for motion vectors
287 ref_tile = planes[0].bands[0].tiles;
289 for (y = 0; y < band->height; y += t_height) {
290 for (x = 0; x < band->width; x += t_width) {
293 tile->mb_size = band->mb_size;
294 tile->width = FFMIN(band->width - x, t_width);
295 tile->height = FFMIN(band->height - y, t_height);
296 tile->is_empty = tile->data_size = 0;
297 /* calculate number of macroblocks */
298 tile->num_MBs = IVI_MBs_PER_TILE(tile->width, tile->height,
301 av_freep(&tile->mbs);
302 tile->mbs = av_malloc(tile->num_MBs * sizeof(IVIMbInfo));
304 return AVERROR(ENOMEM);
308 tile->ref_mbs = ref_tile->mbs;
322 int ff_ivi_dec_tile_data_size(GetBitContext *gb)
328 len = get_bits(gb, 8);
330 len = get_bits_long(gb, 24);
333 /* align the bitstream reader on the byte boundary */
339 int ff_ivi_decode_blocks(GetBitContext *gb, IVIBandDesc *band, IVITile *tile)
341 int mbn, blk, num_blocks, num_coeffs, blk_size, scan_pos, run, val,
342 pos, is_intra, mc_type = 0, mv_x, mv_y, col_mask;
343 uint8_t col_flags[8];
344 int32_t prev_dc, trvec[64];
345 uint32_t cbp, sym, lo, hi, quant, buf_offs, q;
347 RVMapDesc *rvmap = band->rv_map;
348 void (*mc_with_delta_func)(int16_t *buf, const int16_t *ref_buf, uint32_t pitch, int mc_type);
349 void (*mc_no_delta_func) (int16_t *buf, const int16_t *ref_buf, uint32_t pitch, int mc_type);
350 const uint16_t *base_tab;
351 const uint8_t *scale_tab;
353 prev_dc = 0; /* init intra prediction for the DC coefficient */
355 blk_size = band->blk_size;
356 col_mask = blk_size - 1; /* column mask for tracking non-zero coeffs */
357 num_blocks = (band->mb_size != blk_size) ? 4 : 1; /* number of blocks per mb */
358 num_coeffs = blk_size * blk_size;
360 mc_with_delta_func = ff_ivi_mc_8x8_delta;
361 mc_no_delta_func = ff_ivi_mc_8x8_no_delta;
363 mc_with_delta_func = ff_ivi_mc_4x4_delta;
364 mc_no_delta_func = ff_ivi_mc_4x4_no_delta;
367 for (mbn = 0, mb = tile->mbs; mbn < tile->num_MBs; mb++, mbn++) {
368 is_intra = !mb->type;
370 buf_offs = mb->buf_offs;
372 quant = av_clip(band->glob_quant + mb->q_delta, 0, 23);
374 base_tab = is_intra ? band->intra_base : band->inter_base;
375 scale_tab = is_intra ? band->intra_scale : band->inter_scale;
377 quant = scale_tab[quant];
382 if (band->is_halfpel) {
383 mc_type = ((mv_y & 1) << 1) | (mv_x & 1);
385 mv_y >>= 1; /* convert halfpel vectors into fullpel ones */
388 int dmv_x, dmv_y, cx, cy;
390 dmv_x = mb->mv_x >> band->is_halfpel;
391 dmv_y = mb->mv_y >> band->is_halfpel;
392 cx = mb->mv_x & band->is_halfpel;
393 cy = mb->mv_y & band->is_halfpel;
395 if ( mb->xpos + dmv_x < 0
396 || mb->xpos + dmv_x + band->mb_size + cx > band->pitch
397 || mb->ypos + dmv_y < 0
398 || mb->ypos + dmv_y + band->mb_size + cy > band->aheight) {
399 return AVERROR_INVALIDDATA;
404 for (blk = 0; blk < num_blocks; blk++) {
405 /* adjust block position in the buffer according to its number */
407 buf_offs += blk_size;
408 } else if (blk == 2) {
409 buf_offs -= blk_size;
410 buf_offs += blk_size * band->pitch;
413 if (cbp & 1) { /* block coded ? */
415 memset(trvec, 0, num_coeffs*sizeof(trvec[0])); /* zero transform vector */
416 memset(col_flags, 0, sizeof(col_flags)); /* zero column flags */
418 while (scan_pos <= num_coeffs) {
419 sym = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
420 if (sym == rvmap->eob_sym)
421 break; /* End of block */
423 if (sym == rvmap->esc_sym) { /* Escape - run/val explicitly coded using 3 vlc codes */
424 run = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1) + 1;
425 lo = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
426 hi = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
427 val = IVI_TOSIGNED((hi << 6) | lo); /* merge them and convert into signed val */
430 av_log(NULL, AV_LOG_ERROR, "Invalid sym encountered: %d.\n", sym);
433 run = rvmap->runtab[sym];
434 val = rvmap->valtab[sym];
437 /* de-zigzag and dequantize */
439 if (scan_pos >= num_coeffs)
441 pos = band->scan[scan_pos];
444 av_dlog(NULL, "Val = 0 encountered!\n");
446 q = (base_tab[pos] * quant) >> 9;
448 val = val * q + FFSIGN(val) * (((q ^ 1) - 1) >> 1);
450 col_flags[pos & col_mask] |= !!val; /* track columns containing non-zero coeffs */
453 if (scan_pos >= num_coeffs && sym != rvmap->eob_sym)
454 return -1; /* corrupt block data */
456 /* undoing DC coeff prediction for intra-blocks */
457 if (is_intra && band->is_2d_trans) {
460 col_flags[0] |= !!prev_dc;
463 /* apply inverse transform */
464 band->inv_transform(trvec, band->buf + buf_offs,
465 band->pitch, col_flags);
467 /* apply motion compensation */
469 mc_with_delta_func(band->buf + buf_offs,
470 band->ref_buf + buf_offs + mv_y * band->pitch + mv_x,
471 band->pitch, mc_type);
473 /* block not coded */
474 /* for intra blocks apply the dc slant transform */
475 /* for inter - perform the motion compensation without delta */
476 if (is_intra && band->dc_transform) {
477 band->dc_transform(&prev_dc, band->buf + buf_offs,
478 band->pitch, blk_size);
480 mc_no_delta_func(band->buf + buf_offs,
481 band->ref_buf + buf_offs + mv_y * band->pitch + mv_x,
482 band->pitch, mc_type);
495 * Handle empty tiles by performing data copying and motion
496 * compensation respectively.
498 * @param[in] avctx ptr to the AVCodecContext
499 * @param[in] band pointer to the band descriptor
500 * @param[in] tile pointer to the tile descriptor
501 * @param[in] mv_scale scaling factor for motion vectors
503 static int ivi_process_empty_tile(AVCodecContext *avctx, IVIBandDesc *band,
504 IVITile *tile, int32_t mv_scale)
506 int x, y, need_mc, mbn, blk, num_blocks, mv_x, mv_y, mc_type;
507 int offs, mb_offset, row_offset;
508 IVIMbInfo *mb, *ref_mb;
511 void (*mc_no_delta_func)(int16_t *buf, const int16_t *ref_buf, uint32_t pitch,
514 if (tile->num_MBs != IVI_MBs_PER_TILE(tile->width, tile->height, band->mb_size)) {
515 av_log(avctx, AV_LOG_ERROR, "Allocated tile size %d mismatches "
516 "parameters %d in ivi_process_empty_tile()\n",
517 tile->num_MBs, IVI_MBs_PER_TILE(tile->width, tile->height, band->mb_size));
518 return AVERROR_INVALIDDATA;
521 offs = tile->ypos * band->pitch + tile->xpos;
523 ref_mb = tile->ref_mbs;
524 row_offset = band->mb_size * band->pitch;
525 need_mc = 0; /* reset the mc tracking flag */
527 for (y = tile->ypos; y < (tile->ypos + tile->height); y += band->mb_size) {
530 for (x = tile->xpos; x < (tile->xpos + tile->width); x += band->mb_size) {
533 mb->buf_offs = mb_offset;
535 mb->type = 1; /* set the macroblocks type = INTER */
536 mb->cbp = 0; /* all blocks are empty */
538 if (!band->qdelta_present && !band->plane && !band->band_num) {
539 mb->q_delta = band->glob_quant;
544 if (band->inherit_qdelta && ref_mb)
545 mb->q_delta = ref_mb->q_delta;
547 if (band->inherit_mv) {
548 /* motion vector inheritance */
550 mb->mv_x = ivi_scale_mv(ref_mb->mv_x, mv_scale);
551 mb->mv_y = ivi_scale_mv(ref_mb->mv_y, mv_scale);
553 mb->mv_x = ref_mb->mv_x;
554 mb->mv_y = ref_mb->mv_y;
556 need_mc |= mb->mv_x || mb->mv_y; /* tracking non-zero motion vectors */
562 mb_offset += band->mb_size;
567 if (band->inherit_mv && need_mc) { /* apply motion compensation if there is at least one non-zero motion vector */
568 num_blocks = (band->mb_size != band->blk_size) ? 4 : 1; /* number of blocks per mb */
569 mc_no_delta_func = (band->blk_size == 8) ? ff_ivi_mc_8x8_no_delta
570 : ff_ivi_mc_4x4_no_delta;
572 for (mbn = 0, mb = tile->mbs; mbn < tile->num_MBs; mb++, mbn++) {
575 if (!band->is_halfpel) {
576 mc_type = 0; /* we have only fullpel vectors */
578 mc_type = ((mv_y & 1) << 1) | (mv_x & 1);
580 mv_y >>= 1; /* convert halfpel vectors into fullpel ones */
583 for (blk = 0; blk < num_blocks; blk++) {
584 /* adjust block position in the buffer according with its number */
585 offs = mb->buf_offs + band->blk_size * ((blk & 1) + !!(blk & 2) * band->pitch);
586 mc_no_delta_func(band->buf + offs,
587 band->ref_buf + offs + mv_y * band->pitch + mv_x,
588 band->pitch, mc_type);
592 /* copy data from the reference tile into the current one */
593 src = band->ref_buf + tile->ypos * band->pitch + tile->xpos;
594 dst = band->buf + tile->ypos * band->pitch + tile->xpos;
595 for (y = 0; y < tile->height; y++) {
596 memcpy(dst, src, tile->width*sizeof(band->buf[0]));
607 static uint16_t ivi_calc_band_checksum(IVIBandDesc *band)
610 int16_t *src, checksum;
615 for (y = 0; y < band->height; src += band->pitch, y++)
616 for (x = 0; x < band->width; x++)
623 void ff_ivi_output_plane(IVIPlaneDesc *plane, uint8_t *dst, int dst_pitch)
626 const int16_t *src = plane->bands[0].buf;
627 uint32_t pitch = plane->bands[0].pitch;
632 for (y = 0; y < plane->height; y++) {
633 for (x = 0; x < plane->width; x++)
634 dst[x] = av_clip_uint8(src[x] + 128);
641 * Decode an Indeo 4 or 5 band.
643 * @param[in,out] ctx ptr to the decoder context
644 * @param[in,out] band ptr to the band descriptor
645 * @param[in] avctx ptr to the AVCodecContext
646 * @return result code: 0 = OK, -1 = error
648 static int decode_band(IVI45DecContext *ctx,
649 IVIBandDesc *band, AVCodecContext *avctx)
651 int result, i, t, idx1, idx2, pos;
654 band->buf = band->bufs[ctx->dst_buf];
656 av_log(avctx, AV_LOG_ERROR, "Band buffer points to no data!\n");
657 return AVERROR_INVALIDDATA;
659 band->ref_buf = band->bufs[ctx->ref_buf];
660 band->data_ptr = ctx->frame_data + (get_bits_count(&ctx->gb) >> 3);
662 result = ctx->decode_band_hdr(ctx, band, avctx);
664 av_log(avctx, AV_LOG_ERROR, "Error while decoding band header: %d\n",
669 if (band->is_empty) {
670 av_log(avctx, AV_LOG_ERROR, "Empty band encountered!\n");
671 return AVERROR_INVALIDDATA;
674 band->rv_map = &ctx->rvmap_tabs[band->rvmap_sel];
676 /* apply corrections to the selected rvmap table if present */
677 for (i = 0; i < band->num_corr; i++) {
678 idx1 = band->corr[i * 2];
679 idx2 = band->corr[i * 2 + 1];
680 FFSWAP(uint8_t, band->rv_map->runtab[idx1], band->rv_map->runtab[idx2]);
681 FFSWAP(int16_t, band->rv_map->valtab[idx1], band->rv_map->valtab[idx2]);
684 pos = get_bits_count(&ctx->gb);
686 for (t = 0; t < band->num_tiles; t++) {
687 tile = &band->tiles[t];
689 if (tile->mb_size != band->mb_size) {
690 av_log(avctx, AV_LOG_ERROR, "MB sizes mismatch: %d vs. %d\n",
691 band->mb_size, tile->mb_size);
692 return AVERROR_INVALIDDATA;
694 tile->is_empty = get_bits1(&ctx->gb);
695 if (tile->is_empty) {
696 result = ivi_process_empty_tile(avctx, band, tile,
697 (ctx->planes[0].bands[0].mb_size >> 3) - (band->mb_size >> 3));
700 av_dlog(avctx, "Empty tile encountered!\n");
702 tile->data_size = ff_ivi_dec_tile_data_size(&ctx->gb);
703 if (!tile->data_size) {
704 av_log(avctx, AV_LOG_ERROR, "Tile data size is zero!\n");
705 return AVERROR_INVALIDDATA;
708 result = ctx->decode_mb_info(ctx, band, tile, avctx);
712 result = ff_ivi_decode_blocks(&ctx->gb, band, tile);
713 if (result < 0 || ((get_bits_count(&ctx->gb) - pos) >> 3) != tile->data_size) {
714 av_log(avctx, AV_LOG_ERROR, "Corrupted tile data encountered!\n");
718 pos += tile->data_size << 3; // skip to next tile
722 /* restore the selected rvmap table by applying its corrections in reverse order */
723 for (i = band->num_corr-1; i >= 0; i--) {
724 idx1 = band->corr[i*2];
725 idx2 = band->corr[i*2+1];
726 FFSWAP(uint8_t, band->rv_map->runtab[idx1], band->rv_map->runtab[idx2]);
727 FFSWAP(int16_t, band->rv_map->valtab[idx1], band->rv_map->valtab[idx2]);
731 if (band->checksum_present) {
732 uint16_t chksum = ivi_calc_band_checksum(band);
733 if (chksum != band->checksum) {
734 av_log(avctx, AV_LOG_ERROR,
735 "Band checksum mismatch! Plane %d, band %d, received: %x, calculated: %x\n",
736 band->plane, band->band_num, band->checksum, chksum);
741 align_get_bits(&ctx->gb);
746 int ff_ivi_decode_frame(AVCodecContext *avctx, void *data, int *got_frame,
749 IVI45DecContext *ctx = avctx->priv_data;
750 const uint8_t *buf = avpkt->data;
751 int buf_size = avpkt->size;
754 init_get_bits(&ctx->gb, buf, buf_size * 8);
755 ctx->frame_data = buf;
756 ctx->frame_size = buf_size;
758 result = ctx->decode_pic_hdr(ctx, avctx);
760 av_log(avctx, AV_LOG_ERROR,
761 "Error while decoding picture header: %d\n", result);
764 if (ctx->gop_invalid)
765 return AVERROR_INVALIDDATA;
767 if (ctx->gop_flags & IVI5_IS_PROTECTED) {
768 av_log(avctx, AV_LOG_ERROR, "Password-protected clip!\n");
772 ctx->switch_buffers(ctx);
776 if (ctx->is_nonnull_frame(ctx)) {
777 for (p = 0; p < 3; p++) {
778 for (b = 0; b < ctx->planes[p].num_bands; b++) {
779 result = decode_band(ctx, &ctx->planes[p].bands[b], avctx);
781 av_log(avctx, AV_LOG_ERROR,
782 "Error while decoding band: %d, plane: %d\n", b, p);
789 //STOP_TIMER("decode_planes"); }
791 /* If the bidirectional mode is enabled, next I and the following P frame will */
792 /* be sent together. Unfortunately the approach below seems to be the only way */
793 /* to handle the B-frames mode. That's exactly the same Intel decoders do. */
794 if (avctx->codec_id == AV_CODEC_ID_INDEO4 && ctx->frame_type == 0/*FRAMETYPE_INTRA*/) {
795 while (get_bits(&ctx->gb, 8)); // skip version string
796 skip_bits_long(&ctx->gb, 64); // skip padding, TODO: implement correct 8-bytes alignment
797 if (get_bits_left(&ctx->gb) > 18 && show_bits(&ctx->gb, 18) == 0x3FFF8)
798 av_log(avctx, AV_LOG_ERROR, "Buffer contains IP frames!\n");
801 if (ctx->frame.data[0])
802 avctx->release_buffer(avctx, &ctx->frame);
804 ctx->frame.reference = 0;
805 avcodec_set_dimensions(avctx, ctx->planes[0].width, ctx->planes[0].height);
806 if ((result = ff_get_buffer(avctx, &ctx->frame)) < 0) {
807 av_log(avctx, AV_LOG_ERROR, "get_buffer() failed\n");
811 if (ctx->is_scalable) {
812 if (avctx->codec_id == AV_CODEC_ID_INDEO4)
813 ff_ivi_recompose_haar(&ctx->planes[0], ctx->frame.data[0], ctx->frame.linesize[0]);
815 ff_ivi_recompose53 (&ctx->planes[0], ctx->frame.data[0], ctx->frame.linesize[0]);
817 ff_ivi_output_plane(&ctx->planes[0], ctx->frame.data[0], ctx->frame.linesize[0]);
820 ff_ivi_output_plane(&ctx->planes[2], ctx->frame.data[1], ctx->frame.linesize[1]);
821 ff_ivi_output_plane(&ctx->planes[1], ctx->frame.data[2], ctx->frame.linesize[2]);
824 *(AVFrame*)data = ctx->frame;
830 * Close Indeo5 decoder and clean up its context.
832 av_cold int ff_ivi_decode_close(AVCodecContext *avctx)
834 IVI45DecContext *ctx = avctx->priv_data;
836 ff_ivi_free_buffers(&ctx->planes[0]);
838 if (ctx->mb_vlc.cust_tab.table)
839 ff_free_vlc(&ctx->mb_vlc.cust_tab);
841 if (ctx->frame.data[0])
842 avctx->release_buffer(avctx, &ctx->frame);
844 #if IVI4_STREAM_ANALYSER
845 if (avctx->codec_id == AV_CODEC_ID_INDEO4) {
846 if (ctx->is_scalable)
847 av_log(avctx, AV_LOG_ERROR, "This video uses scalability mode!\n");
848 if (ctx->uses_tiling)
849 av_log(avctx, AV_LOG_ERROR, "This video uses local decoding!\n");
850 if (ctx->has_b_frames)
851 av_log(avctx, AV_LOG_ERROR, "This video contains B-frames!\n");
853 av_log(avctx, AV_LOG_ERROR, "Transparency mode is enabled!\n");
855 av_log(avctx, AV_LOG_ERROR, "This video uses Haar transform!\n");
856 if (ctx->uses_fullpel)
857 av_log(avctx, AV_LOG_ERROR, "This video uses fullpel motion vectors!\n");
866 * These are 2x8 predefined Huffman codebooks for coding macroblock/block
867 * signals. They are specified using "huffman descriptors" in order to
868 * avoid huge static tables. The decoding tables will be generated at
869 * startup from these descriptors.
871 const IVIHuffDesc ff_ivi_mb_huff_desc[8] = {
872 {8, {0, 4, 5, 4, 4, 4, 6, 6}},
873 {12, {0, 2, 2, 3, 3, 3, 3, 5, 3, 2, 2, 2}},
874 {12, {0, 2, 3, 4, 3, 3, 3, 3, 4, 3, 2, 2}},
875 {12, {0, 3, 4, 4, 3, 3, 3, 3, 3, 2, 2, 2}},
876 {13, {0, 4, 4, 3, 3, 3, 3, 2, 3, 3, 2, 1, 1}},
877 {9, {0, 4, 4, 4, 4, 3, 3, 3, 2}},
878 {10, {0, 4, 4, 4, 4, 3, 3, 2, 2, 2}},
879 {12, {0, 4, 4, 4, 3, 3, 2, 3, 2, 2, 2, 2}}
882 const IVIHuffDesc ff_ivi_blk_huff_desc[8] = {
883 {10, {1, 2, 3, 4, 4, 7, 5, 5, 4, 1}},
884 {11, {2, 3, 4, 4, 4, 7, 5, 4, 3, 3, 2}},
885 {12, {2, 4, 5, 5, 5, 5, 6, 4, 4, 3, 1, 1}},
886 {13, {3, 3, 4, 4, 5, 6, 6, 4, 4, 3, 2, 1, 1}},
887 {11, {3, 4, 4, 5, 5, 5, 6, 5, 4, 2, 2}},
888 {13, {3, 4, 5, 5, 5, 5, 6, 4, 3, 3, 2, 1, 1}},
889 {13, {3, 4, 5, 5, 5, 6, 5, 4, 3, 3, 2, 1, 1}},
890 {9, {3, 4, 4, 5, 5, 5, 6, 5, 5}}
895 * Scan patterns shared between indeo4 and indeo5
897 const uint8_t ff_ivi_vertical_scan_8x8[64] = {
898 0, 8, 16, 24, 32, 40, 48, 56,
899 1, 9, 17, 25, 33, 41, 49, 57,
900 2, 10, 18, 26, 34, 42, 50, 58,
901 3, 11, 19, 27, 35, 43, 51, 59,
902 4, 12, 20, 28, 36, 44, 52, 60,
903 5, 13, 21, 29, 37, 45, 53, 61,
904 6, 14, 22, 30, 38, 46, 54, 62,
905 7, 15, 23, 31, 39, 47, 55, 63
908 const uint8_t ff_ivi_horizontal_scan_8x8[64] = {
909 0, 1, 2, 3, 4, 5, 6, 7,
910 8, 9, 10, 11, 12, 13, 14, 15,
911 16, 17, 18, 19, 20, 21, 22, 23,
912 24, 25, 26, 27, 28, 29, 30, 31,
913 32, 33, 34, 35, 36, 37, 38, 39,
914 40, 41, 42, 43, 44, 45, 46, 47,
915 48, 49, 50, 51, 52, 53, 54, 55,
916 56, 57, 58, 59, 60, 61, 62, 63
919 const uint8_t ff_ivi_direct_scan_4x4[16] = {
920 0, 1, 4, 8, 5, 2, 3, 6, 9, 12, 13, 10, 7, 11, 14, 15
925 * Run-value (RLE) tables.
927 const RVMapDesc ff_ivi_rvmap_tabs[9] = {
932 {1, 1, 0, 1, 1, 0, 1, 1, 2, 2, 1, 1, 1, 1, 3, 3,
933 1, 1, 2, 2, 1, 1, 4, 4, 1, 1, 1, 1, 2, 2, 5, 5,
934 1, 1, 3, 3, 1, 1, 6, 6, 1, 2, 1, 2, 7, 7, 1, 1,
935 8, 8, 1, 1, 4, 2, 1, 4, 2, 1, 3, 3, 1, 1, 1, 9,
936 9, 1, 2, 1, 2, 1, 5, 5, 1, 1, 10, 10, 1, 1, 3, 3,
937 2, 2, 1, 1, 11, 11, 6, 4, 4, 1, 6, 1, 2, 1, 2, 12,
938 8, 1, 12, 7, 8, 7, 1, 16, 1, 16, 1, 3, 3, 13, 1, 13,
939 2, 2, 1, 15, 1, 5, 14, 15, 1, 5, 14, 1, 17, 8, 17, 8,
940 1, 4, 4, 2, 2, 1, 25, 25, 24, 24, 1, 3, 1, 3, 1, 8,
941 6, 7, 6, 1, 18, 8, 18, 1, 7, 23, 2, 2, 23, 1, 1, 21,
942 22, 9, 9, 22, 19, 1, 21, 5, 19, 5, 1, 33, 20, 33, 20, 8,
943 4, 4, 1, 32, 2, 2, 8, 3, 32, 26, 3, 1, 7, 7, 26, 6,
944 1, 6, 1, 1, 16, 1, 10, 1, 10, 2, 16, 29, 28, 2, 29, 28,
945 1, 27, 5, 8, 5, 27, 1, 8, 3, 7, 3, 31, 41, 31, 1, 41,
946 6, 1, 6, 7, 4, 4, 1, 1, 2, 1, 2, 11, 34, 30, 11, 1,
947 30, 15, 15, 34, 36, 40, 36, 40, 35, 35, 37, 37, 39, 39, 38, 38},
950 { 1, -1, 0, 2, -2, 0, 3, -3, 1, -1, 4, -4, 5, -5, 1, -1,
951 6, -6, 2, -2, 7, -7, 1, -1, 8, -8, 9, -9, 3, -3, 1, -1,
952 10, -10, 2, -2, 11, -11, 1, -1, 12, 4, -12, -4, 1, -1, 13, -13,
953 1, -1, 14, -14, 2, 5, 15, -2, -5, -15, -3, 3, 16, -16, 17, 1,
954 -1, -17, 6, 18, -6, -18, 2, -2, 19, -19, 1, -1, 20, -20, 4, -4,
955 7, -7, 21, -21, 1, -1, 2, 3, -3, 22, -2, -22, 8, 23, -8, 1,
956 2, -23, -1, 2, -2, -2, 24, 1, -24, -1, 25, 5, -5, 1, -25, -1,
957 9, -9, 26, 1, -26, 3, 1, -1, 27, -3, -1, -27, 1, 3, -1, -3,
958 28, -4, 4, 10, -10, -28, 1, -1, 1, -1, 29, 6, -29, -6, 30, -4,
959 3, 3, -3, -30, 1, 4, -1, 31, -3, 1, 11, -11, -1, -31, 32, -1,
960 -1, 2, -2, 1, 1, -32, 1, 4, -1, -4, 33, -1, 1, 1, -1, 5,
961 5, -5, -33, -1, -12, 12, -5, -7, 1, 1, 7, 34, 4, -4, -1, 4,
962 -34, -4, 35, 36, -2, -35, -2, -36, 2, 13, 2, -1, 1, -13, 1, -1,
963 37, 1, -5, 6, 5, -1, 38, -6, -8, 5, 8, -1, 1, 1, -37, -1,
964 5, 39, -5, -5, 6, -6, -38, -39, -14, 40, 14, 2, 1, 1, -2, -40,
965 -1, -2, 2, -1, -1, -1, 1, 1, 1, -1, 1, -1, 1, -1, 1, -1}
971 {0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 8, 6, 8, 7,
972 7, 9, 9, 10, 10, 11, 11, 1, 12, 1, 12, 13, 13, 16, 14, 16,
973 14, 15, 15, 17, 17, 18, 0, 18, 19, 20, 21, 19, 22, 21, 20, 22,
974 25, 24, 2, 25, 24, 23, 23, 2, 26, 28, 26, 28, 29, 27, 29, 27,
975 33, 33, 1, 32, 1, 3, 32, 30, 36, 3, 36, 30, 31, 31, 35, 34,
976 37, 41, 34, 35, 37, 4, 41, 4, 49, 8, 8, 49, 40, 38, 5, 38,
977 40, 39, 5, 39, 42, 43, 42, 7, 57, 6, 43, 44, 6, 50, 7, 44,
978 57, 48, 50, 48, 45, 45, 46, 47, 51, 46, 47, 58, 1, 51, 58, 1,
979 52, 59, 53, 9, 52, 55, 55, 59, 53, 56, 54, 56, 54, 9, 64, 64,
980 60, 63, 60, 63, 61, 62, 61, 62, 2, 10, 2, 10, 11, 1, 11, 13,
981 12, 1, 12, 13, 16, 16, 8, 8, 14, 3, 3, 15, 14, 15, 4, 4,
982 1, 17, 17, 5, 1, 7, 7, 5, 6, 1, 2, 2, 6, 22, 1, 25,
983 21, 22, 8, 24, 1, 21, 25, 24, 8, 18, 18, 23, 9, 20, 23, 33,
984 29, 33, 20, 1, 19, 1, 29, 36, 9, 36, 19, 41, 28, 57, 32, 3,
985 28, 3, 1, 27, 49, 49, 1, 32, 26, 26, 2, 4, 4, 7, 57, 41,
986 2, 7, 10, 5, 37, 16, 10, 27, 8, 8, 13, 16, 37, 13, 1, 5},
989 {0, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, 1, -1, -1, 1,
990 -1, 1, -1, 1, -1, 1, -1, 2, 1, -2, -1, 1, -1, 1, 1, -1,
991 -1, 1, -1, 1, -1, 1, 0, -1, 1, 1, 1, -1, 1, -1, -1, -1,
992 1, 1, 2, -1, -1, 1, -1, -2, 1, 1, -1, -1, 1, 1, -1, -1,
993 1, -1, 3, 1, -3, 2, -1, 1, 1, -2, -1, -1, -1, 1, 1, 1,
994 1, 1, -1, -1, -1, 2, -1, -2, 1, 2, -2, -1, 1, 1, 2, -1,
995 -1, 1, -2, -1, 1, 1, -1, 2, 1, 2, -1, 1, -2, -1, -2, -1,
996 -1, 1, 1, -1, 1, -1, 1, 1, 1, -1, -1, 1, 4, -1, -1, -4,
997 1, 1, 1, 2, -1, -1, 1, -1, -1, 1, -1, -1, 1, -2, 1, -1,
998 1, 1, -1, -1, 1, 1, -1, -1, 3, 2, -3, -2, 2, 5, -2, 2,
999 2, -5, -2, -2, -2, 2, -3, 3, 2, 3, -3, 2, -2, -2, 3, -3,
1000 6, 2, -2, 3, -6, 3, -3, -3, 3, 7, -4, 4, -3, 2, -7, 2,
1001 2, -2, -4, 2, 8, -2, -2, -2, 4, 2, -2, 2, 3, 2, -2, -2,
1002 2, 2, -2, -8, -2, 9, -2, 2, -3, -2, 2, -2, 2, 2, 2, 4,
1003 -2, -4, 10, 2, 2, -2, -9, -2, 2, -2, 5, 4, -4, 4, -2, 2,
1004 -5, -4, -3, 4, 2, -3, 3, -2, -5, 5, 3, 3, -2, -3, -10, -4}
1010 {1, 1, 0, 2, 2, 1, 1, 3, 3, 4, 4, 0, 1, 1, 5, 5,
1011 2, 2, 6, 6, 7, 7, 1, 8, 1, 8, 3, 3, 9, 9, 1, 2,
1012 2, 1, 4, 10, 4, 10, 11, 11, 1, 5, 12, 12, 1, 5, 13, 13,
1013 3, 3, 6, 6, 2, 2, 14, 14, 16, 16, 15, 7, 15, 8, 8, 7,
1014 1, 1, 17, 17, 4, 4, 1, 1, 18, 18, 2, 2, 5, 5, 25, 3,
1015 9, 3, 25, 9, 19, 24, 19, 24, 1, 21, 20, 1, 21, 22, 20, 22,
1016 23, 23, 8, 6, 33, 6, 8, 33, 7, 7, 26, 26, 1, 32, 1, 32,
1017 28, 4, 28, 10, 29, 27, 27, 10, 41, 4, 29, 2, 2, 41, 36, 31,
1018 49, 31, 34, 30, 34, 36, 30, 35, 1, 49, 11, 5, 35, 11, 1, 3,
1019 3, 5, 37, 37, 8, 40, 8, 40, 12, 12, 42, 42, 1, 38, 16, 57,
1020 1, 6, 16, 39, 38, 6, 7, 7, 13, 13, 39, 43, 2, 43, 57, 2,
1021 50, 9, 44, 9, 50, 4, 15, 48, 44, 4, 1, 15, 48, 14, 14, 1,
1022 45, 45, 8, 3, 5, 8, 51, 47, 3, 46, 46, 47, 5, 51, 1, 17,
1023 17, 58, 1, 58, 2, 52, 52, 2, 53, 7, 59, 6, 6, 56, 53, 55,
1024 7, 55, 1, 54, 59, 56, 54, 10, 1, 10, 4, 60, 1, 60, 8, 4,
1025 8, 64, 64, 61, 1, 63, 3, 63, 62, 61, 5, 11, 5, 3, 11, 62},
1028 { 1, -1, 0, 1, -1, 2, -2, 1, -1, 1, -1, 0, 3, -3, 1, -1,
1029 2, -2, 1, -1, 1, -1, 4, 1, -4, -1, 2, -2, 1, -1, 5, 3,
1030 -3, -5, 2, 1, -2, -1, 1, -1, 6, 2, 1, -1, -6, -2, 1, -1,
1031 3, -3, 2, -2, 4, -4, 1, -1, 1, -1, 1, 2, -1, 2, -2, -2,
1032 7, -7, 1, -1, 3, -3, 8, -8, 1, -1, 5, -5, 3, -3, 1, 4,
1033 2, -4, -1, -2, 1, 1, -1, -1, 9, 1, 1, -9, -1, 1, -1, -1,
1034 1, -1, 3, -3, 1, 3, -3, -1, 3, -3, 1, -1, 10, 1, -10, -1,
1035 1, 4, -1, 2, 1, -1, 1, -2, 1, -4, -1, 6, -6, -1, 1, 1,
1036 1, -1, 1, 1, -1, -1, -1, 1, 11, -1, -2, 4, -1, 2, -11, 5,
1037 -5, -4, -1, 1, 4, 1, -4, -1, -2, 2, 1, -1, 12, 1, -2, 1,
1038 -12, 4, 2, 1, -1, -4, 4, -4, 2, -2, -1, 1, 7, -1, -1, -7,
1039 -1, -3, 1, 3, 1, 5, 2, 1, -1, -5, 13, -2, -1, 2, -2, -13,
1040 1, -1, 5, 6, 5, -5, 1, 1, -6, 1, -1, -1, -5, -1, 14, 2,
1041 -2, 1, -14, -1, 8, 1, -1, -8, 1, 5, 1, 5, -5, 1, -1, 1,
1042 -5, -1, 15, 1, -1, -1, -1, 3, -15, -3, 6, 1, 16, -1, 6, -6,
1043 -6, 1, -1, 1, -16, 1, 7, -1, 1, -1, -6, -3, 6, -7, 3, -1}
1049 {0, 1, 1, 2, 2, 3, 3, 4, 4, 1, 1, 5, 5, 6, 6, 7,
1050 7, 8, 8, 9, 9, 2, 2, 10, 10, 1, 1, 11, 11, 12, 12, 3,
1051 3, 13, 13, 0, 14, 14, 16, 15, 16, 15, 4, 4, 17, 1, 17, 1,
1052 5, 5, 18, 18, 2, 2, 6, 6, 8, 19, 7, 8, 7, 19, 20, 20,
1053 21, 21, 22, 24, 22, 24, 23, 23, 1, 1, 25, 25, 3, 3, 26, 26,
1054 9, 9, 27, 27, 28, 28, 33, 29, 4, 33, 29, 1, 4, 1, 32, 32,
1055 2, 2, 31, 10, 30, 10, 30, 31, 34, 34, 5, 5, 36, 36, 35, 41,
1056 35, 11, 41, 11, 37, 1, 8, 8, 37, 6, 1, 6, 40, 7, 7, 40,
1057 12, 38, 12, 39, 39, 38, 49, 13, 49, 13, 3, 42, 3, 42, 16, 16,
1058 43, 43, 14, 14, 1, 1, 44, 15, 44, 15, 2, 2, 57, 48, 50, 48,
1059 57, 50, 4, 45, 45, 4, 46, 47, 47, 46, 1, 51, 1, 17, 17, 51,
1060 8, 9, 9, 5, 58, 8, 58, 5, 52, 52, 55, 56, 53, 56, 55, 59,
1061 59, 53, 54, 1, 6, 54, 7, 7, 6, 1, 2, 3, 2, 3, 64, 60,
1062 60, 10, 10, 64, 61, 62, 61, 63, 1, 63, 62, 1, 18, 24, 18, 4,
1063 25, 4, 8, 21, 21, 1, 24, 22, 25, 22, 8, 11, 19, 11, 23, 1,
1064 20, 23, 19, 20, 5, 12, 5, 1, 16, 2, 12, 13, 2, 13, 1, 16},
1067 { 0, 1, -1, 1, -1, 1, -1, 1, -1, 2, -2, 1, -1, 1, -1, 1,
1068 -1, 1, -1, 1, -1, 2, -2, 1, -1, 3, -3, 1, -1, 1, -1, 2,
1069 -2, 1, -1, 0, 1, -1, 1, 1, -1, -1, 2, -2, 1, 4, -1, -4,
1070 2, -2, 1, -1, -3, 3, 2, -2, 2, 1, 2, -2, -2, -1, 1, -1,
1071 1, -1, 1, 1, -1, -1, 1, -1, 5, -5, 1, -1, 3, -3, 1, -1,
1072 2, -2, 1, -1, 1, -1, 1, 1, 3, -1, -1, 6, -3, -6, -1, 1,
1073 4, -4, 1, 2, 1, -2, -1, -1, 1, -1, 3, -3, 1, -1, 1, 1,
1074 -1, 2, -1, -2, 1, 7, -3, 3, -1, 3, -7, -3, 1, -3, 3, -1,
1075 2, 1, -2, 1, -1, -1, 1, 2, -1, -2, -4, -1, 4, 1, 2, -2,
1076 1, -1, -2, 2, 8, -8, -1, 2, 1, -2, -5, 5, 1, -1, -1, 1,
1077 -1, 1, 4, -1, 1, -4, -1, -1, 1, 1, 9, 1, -9, 2, -2, -1,
1078 -4, 3, -3, -4, -1, 4, 1, 4, 1, -1, 1, -1, 1, 1, -1, 1,
1079 -1, -1, -1, 10, 4, 1, 4, -4, -4, -10, 6, 5, -6, -5, 1, -1,
1080 1, 3, -3, -1, 1, -1, -1, -1, 11, 1, 1, -11, -2, -2, 2, 5,
1081 -2, -5, -5, 2, -2, 12, 2, -2, 2, 2, 5, -3, -2, 3, -2, -12,
1082 -2, 2, 2, 2, -5, 3, 5, 13, -3, 7, -3, -3, -7, 3, -13, 3}
1088 {0, 1, 1, 1, 2, 2, 1, 3, 3, 1, 1, 1, 4, 4, 1, 5,
1089 2, 1, 5, 2, 1, 1, 6, 6, 1, 1, 1, 1, 1, 7, 3, 1,
1090 2, 3, 0, 1, 2, 7, 1, 1, 1, 8, 1, 1, 8, 1, 1, 1,
1091 9, 1, 9, 1, 2, 1, 1, 2, 1, 1, 10, 4, 1, 10, 1, 4,
1092 1, 1, 1, 1, 1, 3, 1, 1, 1, 3, 2, 1, 5, 1, 1, 1,
1093 2, 5, 1, 11, 1, 11, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1094 2, 1, 6, 1, 6, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 12,
1095 3, 1, 12, 1, 1, 1, 2, 1, 1, 3, 1, 1, 1, 1, 1, 1,
1096 4, 1, 1, 1, 2, 1, 1, 4, 1, 1, 1, 1, 1, 1, 2, 1,
1097 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 2, 1, 1, 5,
1098 1, 1, 1, 1, 1, 7, 1, 7, 1, 1, 2, 3, 1, 1, 1, 1,
1099 5, 1, 1, 1, 1, 1, 1, 2, 13, 1, 1, 1, 1, 1, 1, 1,
1100 1, 1, 1, 1, 1, 1, 1, 1, 13, 2, 1, 1, 4, 1, 1, 1,
1101 3, 1, 6, 1, 1, 1, 14, 1, 1, 1, 1, 1, 14, 6, 1, 1,
1102 1, 1, 15, 2, 4, 1, 2, 3, 15, 1, 1, 1, 8, 1, 1, 8,
1103 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1},
1106 { 0, 1, -1, 2, 1, -1, -2, 1, -1, 3, -3, 4, 1, -1, -4, 1,
1107 2, 5, -1, -2, -5, 6, 1, -1, -6, 7, -7, 8, -8, 1, 2, 9,
1108 3, -2, 0, -9, -3, -1, 10, -10, 11, 1, -11, 12, -1, -12, 13, -13,
1109 1, 14, -1, -14, 4, 15, -15, -4, 16, -16, 1, 2, 17, -1, -17, -2,
1110 18, -18, 19, -19, 20, 3, -20, 21, -21, -3, 5, 22, 2, -22, -23, 23,
1111 -5, -2, 24, 1, -24, -1, 25, -25, 26, -26, -27, 27, 28, 29, -28, -29,
1112 6, 30, 2, -31, -2, -30, 31, -6, -32, 32, 33, -33, 34, -35, -34, 1,
1113 4, -36, -1, 35, 37, 36, 7, -37, 38, -4, -38, 39, 41, 40, -40, -39,
1114 3, 42, -43, -41, -7, -42, 43, -3, 44, -44, 45, -45, 46, 47, 8, -47,
1115 -48, -46, 50, -50, 48, 49, 51, -49, 52, -52, 5, -51, -8, -53, 53, 3,
1116 -56, 56, 55, 54, -54, 2, 60, -2, -55, 58, 9, -5, 59, 57, -57, -63,
1117 -3, -58, -60, -61, 61, -59, -62, -9, 1, 64, 62, 69, -64, 63, 65, -67,
1118 -68, 66, -65, 68, -66, -69, 67, -70, -1, 10, 71, -71, 4, 73, 72, 70,
1119 6, -76, -3, 74, -78, -74, 1, 78, 80, -72, -75, 76, -1, 3, -73, 79,
1120 75, 77, 1, 11, -4, -79, -10, -6, -1, -77, -83, -80, 2, 81, -84, -2,
1121 83, -81, 82, -82, 84, -87, -86, 85, -11, -85, 86, -89, 87, -88, 88, 89}
1127 {1, 1, 0, 2, 1, 2, 1, 3, 3, 1, 1, 4, 4, 2, 2, 1,
1128 1, 5, 5, 6, 1, 6, 1, 7, 7, 3, 3, 2, 8, 2, 8, 1,
1129 1, 0, 9, 9, 1, 1, 10, 4, 10, 4, 11, 11, 2, 1, 2, 1,
1130 12, 12, 3, 3, 1, 1, 13, 5, 5, 13, 14, 1, 1, 14, 2, 2,
1131 6, 6, 15, 1, 1, 15, 16, 4, 7, 16, 4, 7, 1, 1, 3, 3,
1132 8, 8, 2, 2, 1, 1, 17, 17, 1, 1, 18, 18, 5, 5, 2, 2,
1133 1, 1, 9, 19, 9, 19, 20, 3, 3, 20, 1, 10, 21, 1, 10, 4,
1134 4, 21, 22, 6, 6, 22, 1, 1, 23, 24, 2, 2, 23, 24, 11, 1,
1135 1, 11, 7, 25, 7, 1, 1, 25, 8, 8, 3, 26, 3, 1, 12, 2,
1136 2, 26, 1, 12, 5, 5, 27, 4, 1, 4, 1, 27, 28, 1, 28, 13,
1137 1, 13, 2, 29, 2, 1, 32, 6, 1, 30, 14, 29, 14, 6, 3, 31,
1138 3, 1, 30, 1, 32, 31, 33, 9, 33, 1, 1, 7, 9, 7, 2, 2,
1139 1, 1, 4, 36, 34, 4, 5, 10, 10, 5, 34, 1, 1, 35, 8, 8,
1140 36, 3, 35, 1, 15, 3, 2, 1, 16, 15, 16, 2, 37, 1, 37, 1,
1141 1, 1, 6, 6, 38, 1, 38, 11, 1, 39, 39, 40, 11, 2, 41, 4,
1142 40, 1, 2, 4, 1, 1, 1, 41, 3, 1, 3, 1, 5, 7, 5, 7},
1145 { 1, -1, 0, 1, 2, -1, -2, 1, -1, 3, -3, 1, -1, 2, -2, 4,
1146 -4, 1, -1, 1, 5, -1, -5, 1, -1, 2, -2, 3, 1, -3, -1, 6,
1147 -6, 0, 1, -1, 7, -7, 1, 2, -1, -2, 1, -1, 4, 8, -4, -8,
1148 1, -1, 3, -3, 9, -9, 1, 2, -2, -1, 1, 10, -10, -1, 5, -5,
1149 2, -2, 1, 11, -11, -1, 1, 3, 2, -1, -3, -2, 12, -12, 4, -4,
1150 2, -2, -6, 6, 13, -13, 1, -1, 14, -14, 1, -1, 3, -3, 7, -7,
1151 15, -15, 2, 1, -2, -1, 1, 5, -5, -1, -16, 2, 1, 16, -2, 4,
1152 -4, -1, 1, 3, -3, -1, 17, -17, 1, 1, -8, 8, -1, -1, 2, 18,
1153 -18, -2, 3, 1, -3, 19, -19, -1, 3, -3, 6, 1, -6, 20, 2, 9,
1154 -9, -1, -20, -2, 4, -4, 1, -5, 21, 5, -21, -1, 1, -22, -1, 2,
1155 22, -2, 10, 1, -10, 23, 1, 4, -23, 1, 2, -1, -2, -4, -7, 1,
1156 7, -24, -1, 24, -1, -1, 1, 3, -1, -25, 25, 4, -3, -4, 11, -11,
1157 26, -26, 6, 1, 1, -6, -5, -3, 3, 5, -1, -27, 27, 1, 4, -4,
1158 -1, -8, -1, 28, 2, 8, -12, -28, -2, -2, 2, 12, -1, 29, 1, -29,
1159 30, -30, 5, -5, 1, -31, -1, 3, 31, -1, 1, 1, -3, -13, 1, -7,
1160 -1, -32, 13, 7, 32, 33, -33, -1, -9, -34, 9, 34, -6, 5, 6, -5}
1166 {1, 1, 0, 1, 1, 2, 2, 1, 1, 3, 3, 1, 1, 0, 2, 2,
1167 4, 1, 4, 1, 1, 1, 5, 5, 1, 1, 6, 6, 2, 2, 1, 1,
1168 3, 3, 7, 7, 1, 1, 8, 8, 1, 1, 2, 2, 1, 9, 1, 9,
1169 4, 4, 10, 1, 1, 10, 1, 1, 11, 11, 3, 3, 1, 2, 1, 2,
1170 1, 1, 12, 12, 5, 5, 1, 1, 13, 1, 1, 13, 2, 2, 1, 1,
1171 6, 6, 1, 1, 4, 14, 4, 14, 3, 1, 3, 1, 1, 1, 15, 7,
1172 15, 2, 2, 7, 1, 1, 1, 8, 1, 8, 16, 16, 1, 1, 1, 1,
1173 2, 1, 1, 2, 1, 1, 3, 5, 5, 3, 4, 1, 1, 4, 1, 1,
1174 17, 17, 9, 1, 1, 9, 2, 2, 1, 1, 10, 10, 1, 6, 1, 1,
1175 6, 18, 1, 1, 18, 1, 1, 1, 2, 2, 3, 1, 3, 1, 1, 1,
1176 4, 1, 19, 1, 19, 7, 1, 1, 20, 1, 4, 20, 1, 7, 11, 2,
1177 1, 11, 21, 2, 8, 5, 1, 8, 1, 5, 21, 1, 1, 1, 22, 1,
1178 1, 22, 1, 1, 3, 3, 1, 23, 2, 12, 24, 1, 1, 2, 1, 1,
1179 12, 23, 1, 1, 24, 1, 1, 1, 4, 1, 1, 1, 2, 1, 6, 6,
1180 4, 2, 1, 1, 1, 1, 1, 1, 1, 14, 13, 3, 1, 25, 9, 25,
1181 14, 1, 9, 3, 13, 1, 1, 1, 1, 1, 10, 1, 1, 2, 10, 2},
1184 {-20, -1, 0, 2, -2, 1, -1, 3, -3, 1, -1, 4, -4, 0, 2, -2,
1185 1, 5, -1, -5, 6, -6, 1, -1, 7, -7, 1, -1, 3, -3, 8, -8,
1186 2, -2, 1, -1, 9, -9, 1, -1, 10, -10, 4, -4, 11, 1, -11, -1,
1187 2, -2, 1, 12, -12, -1, 13, -13, 1, -1, 3, -3, 14, 5, -14, -5,
1188 -15, 15, -1, 1, 2, -2, 16, -16, 1, 17, -17, -1, 6, -6, 18, -18,
1189 2, -2, -19, 19, -3, 1, 3, -1, 4, 20, -4, 1, -21, 21, 1, 2,
1190 -1, -7, 7, -2, 22, -22, 23, 2, -23, -2, 1, -1, -24, 24, -25, 25,
1191 -8, -26, 26, 8, -27, 27, 5, 3, -3, -5, -4, 28, -28, 4, 29, -29,
1192 1, -1, -2, -30, 30, 2, 9, -9, -31, 31, 2, -2, -32, 3, 32, -33,
1193 -3, 1, 33, -34, -1, 34, -35, 35, -10, 10, -6, 36, 6, -36, 37, -37,
1194 -5, 38, 1, -38, -1, 3, 39, -39, -1, 40, 5, 1, -40, -3, 2, -11,
1195 -41, -2, 1, 11, -3, -4, 41, 3, 42, 4, -1, -43, -42, 43, 1, -44,
1196 45, -1, 44, -45, -7, 7, -46, 1, -12, 2, 1, -47, 46, 12, 47, 48,
1197 -2, -1, -48, 49, -1, -50, -49, 50, -6, -51, 51, 52, -13, 53, -4, 4,
1198 6, 13, -53, -52, -54, 55, 54, -55, -56, -2, 2, -8, 56, 1, -3, -1,
1199 2, 58, 3, 8, -2, 57, -58, -60, -59, -57, -3, 60, 59, -14, 3, 14}
1205 {1, 1, 0, 2, 2, 1, 1, 3, 3, 4, 4, 5, 5, 1, 1, 6,
1206 6, 2, 2, 7, 7, 8, 8, 1, 1, 3, 3, 9, 9, 10, 10, 1,
1207 1, 2, 2, 4, 4, 11, 0, 11, 12, 12, 13, 13, 1, 1, 5, 5,
1208 14, 14, 15, 16, 15, 16, 3, 3, 1, 6, 1, 6, 2, 2, 7, 7,
1209 8, 8, 17, 17, 1, 1, 4, 4, 18, 18, 2, 2, 1, 19, 1, 20,
1210 19, 20, 21, 21, 3, 3, 22, 22, 5, 5, 24, 1, 1, 23, 9, 23,
1211 24, 9, 2, 2, 10, 1, 1, 10, 6, 6, 25, 4, 4, 25, 7, 7,
1212 26, 8, 1, 8, 3, 1, 26, 3, 11, 11, 27, 27, 2, 28, 1, 2,
1213 28, 1, 12, 12, 5, 5, 29, 13, 13, 29, 32, 1, 1, 33, 31, 30,
1214 32, 4, 30, 33, 4, 31, 3, 14, 1, 1, 3, 34, 34, 2, 2, 14,
1215 6, 6, 35, 36, 35, 36, 1, 15, 1, 16, 16, 15, 7, 9, 7, 9,
1216 37, 8, 8, 37, 1, 1, 39, 2, 38, 39, 2, 40, 5, 38, 40, 5,
1217 3, 3, 4, 4, 10, 10, 1, 1, 1, 1, 41, 2, 41, 2, 6, 6,
1218 1, 1, 11, 42, 11, 43, 3, 42, 3, 17, 4, 43, 1, 17, 7, 1,
1219 8, 44, 4, 7, 44, 5, 8, 2, 5, 1, 2, 48, 45, 1, 12, 45,
1220 12, 48, 13, 13, 1, 9, 9, 46, 1, 46, 47, 47, 49, 18, 18, 49},
1223 { 1, -1, 0, 1, -1, 2, -2, 1, -1, 1, -1, 1, -1, 3, -3, 1,
1224 -1, -2, 2, 1, -1, 1, -1, 4, -4, -2, 2, 1, -1, 1, -1, 5,
1225 -5, -3, 3, 2, -2, 1, 0, -1, 1, -1, 1, -1, 6, -6, 2, -2,
1226 1, -1, 1, 1, -1, -1, -3, 3, 7, 2, -7, -2, -4, 4, 2, -2,
1227 2, -2, 1, -1, 8, -8, 3, -3, 1, -1, -5, 5, 9, 1, -9, 1,
1228 -1, -1, 1, -1, -4, 4, 1, -1, 3, -3, 1, -10, 10, 1, 2, -1,
1229 -1, -2, 6, -6, 2, 11, -11, -2, 3, -3, 1, -4, 4, -1, 3, -3,
1230 1, 3, 12, -3, -5, -12, -1, 5, 2, -2, 1, -1, -7, 1, 13, 7,
1231 -1, -13, 2, -2, 4, -4, 1, 2, -2, -1, 1, 14, -14, 1, 1, 1,
1232 -1, -5, -1, -1, 5, -1, -6, 2, -15, 15, 6, 1, -1, -8, 8, -2,
1233 -4, 4, 1, 1, -1, -1, 16, 2, -16, -2, 2, -2, 4, 3, -4, -3,
1234 -1, -4, 4, 1, -17, 17, -1, -9, 1, 1, 9, 1, -5, -1, -1, 5,
1235 -7, 7, 6, -6, 3, -3, 18, -18, 19, -19, 1, -10, -1, 10, -5, 5,
1236 20, -20, -3, 1, 3, 1, 8, -1, -8, 2, 7, -1, -21, -2, 5, 21,
1237 5, -1, -7, -5, 1, -6, -5, -11, 6, 22, 11, 1, 1, -22, -3, -1,
1238 3, -1, 3, -3, -23, 4, -4, 1, 23, -1, 1, -1, 1, -2, 2, -1}
1244 {1, 1, 1, 1, 0, 2, 2, 1, 1, 3, 3, 0, 1, 1, 2, 2,
1245 4, 4, 1, 1, 5, 5, 1, 1, 2, 2, 3, 3, 6, 6, 1, 1,
1246 7, 7, 8, 1, 8, 2, 2, 1, 4, 4, 1, 3, 1, 3, 9, 9,
1247 2, 2, 1, 5, 1, 5, 10, 10, 1, 1, 11, 11, 3, 6, 3, 4,
1248 4, 6, 2, 2, 1, 12, 1, 12, 7, 13, 7, 13, 1, 1, 8, 8,
1249 2, 2, 14, 14, 16, 15, 16, 5, 5, 1, 3, 15, 1, 3, 4, 4,
1250 1, 1, 17, 17, 2, 2, 6, 6, 1, 18, 1, 18, 22, 21, 22, 21,
1251 25, 24, 25, 19, 9, 20, 9, 23, 19, 24, 20, 3, 23, 7, 3, 1,
1252 1, 7, 28, 26, 29, 5, 28, 26, 5, 8, 29, 4, 8, 27, 2, 2,
1253 4, 27, 1, 1, 10, 36, 10, 33, 33, 36, 30, 1, 32, 32, 1, 30,
1254 6, 31, 31, 35, 3, 6, 11, 11, 3, 2, 35, 2, 34, 1, 34, 1,
1255 37, 37, 12, 7, 12, 5, 41, 5, 4, 7, 1, 8, 13, 4, 1, 41,
1256 13, 38, 8, 38, 9, 1, 40, 40, 9, 1, 39, 2, 2, 49, 39, 42,
1257 3, 3, 14, 16, 49, 14, 16, 42, 43, 43, 6, 6, 15, 1, 1, 15,
1258 44, 44, 1, 1, 50, 48, 4, 5, 4, 7, 5, 2, 10, 10, 48, 7,
1259 50, 45, 2, 1, 45, 8, 8, 1, 46, 46, 3, 47, 47, 3, 1, 1},
1262 { 1, -1, 2, -2, 0, 1, -1, 3, -3, 1, -1, 0, 4, -4, 2, -2,
1263 1, -1, 5, -5, 1, -1, 6, -6, 3, -3, 2, -2, 1, -1, 7, -7,
1264 1, -1, 1, 8, -1, 4, -4, -8, 2, -2, 9, 3, -9, -3, 1, -1,
1265 5, -5, 10, 2, -10, -2, 1, -1, 11, -11, 1, -1, -4, 2, 4, 3,
1266 -3, -2, 6, -6, 12, 1, -12, -1, 2, 1, -2, -1, 13, -13, 2, -2,
1267 7, -7, 1, -1, 1, 1, -1, 3, -3, 14, 5, -1, -14, -5, 4, -4,
1268 15, -15, 1, -1, 8, -8, -3, 3, 16, 1, -16, -1, 1, 1, -1, -1,
1269 1, 1, -1, 1, 2, 1, -2, 1, -1, -1, -1, 6, -1, 3, -6, 17,
1270 -17, -3, 1, 1, 1, 4, -1, -1, -4, 3, -1, 5, -3, -1, -9, 9,
1271 -5, 1, 18, -18, 2, 1, -2, 1, -1, -1, 1, 19, -1, 1, -19, -1,
1272 4, 1, -1, 1, 7, -4, -2, 2, -7, 10, -1, -10, 1, 20, -1, -20,
1273 1, -1, 2, 4, -2, 5, 1, -5, 6, -4, 21, 4, 2, -6, -21, -1,
1274 -2, 1, -4, -1, -3, 22, -1, 1, 3, -22, -1, 11, -11, 1, 1, 1,
1275 8, -8, 2, 2, -1, -2, -2, -1, 1, -1, -5, 5, 2, 23, -23, -2,
1276 1, -1, 24, -24, -1, -1, 7, 6, -7, 5, -6, 12, -3, 3, 1, -5,
1277 1, 1, -12, 25, -1, -5, 5, -25, -1, 1, 9, 1, -1, -9, 26, -26}