2 * common functions for Indeo Video Interactive codecs (Indeo4 and Indeo5)
4 * Copyright (c) 2009 Maxim Poliakovski
6 * This file is part of FFmpeg.
8 * FFmpeg 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 * FFmpeg 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 FFmpeg; 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
32 #include "ivi_common.h"
33 #include "libavutil/common.h"
36 extern const IVIHuffDesc ff_ivi_mb_huff_desc[8]; ///< static macroblock huffman tables
37 extern const IVIHuffDesc ff_ivi_blk_huff_desc[8]; ///< static block huffman tables
39 VLC ff_ivi_mb_vlc_tabs [8];
40 VLC ff_ivi_blk_vlc_tabs[8];
43 * Reverse "nbits" bits of the value "val" and return the result
44 * in the least significant bits.
46 static uint16_t inv_bits(uint16_t val, int nbits)
51 res = av_reverse[val] >> (8-nbits);
53 res = ((av_reverse[val & 0xFF] << 8) + (av_reverse[val >> 8])) >> (16-nbits);
58 int ff_ivi_create_huff_from_desc(const IVIHuffDesc *cb, VLC *vlc, int flag)
60 int pos, i, j, codes_per_row, prefix, not_last_row;
61 uint16_t codewords[256]; /* FIXME: move this temporal storage out? */
64 pos = 0; /* current position = 0 */
66 for (i = 0; i < cb->num_rows; i++) {
67 codes_per_row = 1 << cb->xbits[i];
68 not_last_row = (i != cb->num_rows - 1);
69 prefix = ((1 << i) - 1) << (cb->xbits[i] + not_last_row);
71 for (j = 0; j < codes_per_row; j++) {
72 if (pos >= 256) /* Some Indeo5 codebooks can have more than 256 */
73 break; /* elements, but only 256 codes are allowed! */
75 bits[pos] = i + cb->xbits[i] + not_last_row;
76 if (bits[pos] > IVI_VLC_BITS)
77 return -1; /* invalid descriptor */
79 codewords[pos] = inv_bits((prefix | j), bits[pos]);
87 /* number of codewords = pos */
88 return init_vlc(vlc, IVI_VLC_BITS, pos, bits, 1, 1, codewords, 2, 2,
89 (flag ? INIT_VLC_USE_NEW_STATIC : 0) | INIT_VLC_LE);
92 void ff_ivi_init_static_vlc(void)
95 static VLC_TYPE table_data[8192 * 16][2];
96 static int initialized_vlcs = 0;
100 for (i = 0; i < 8; i++) {
101 ff_ivi_mb_vlc_tabs[i].table = table_data + i * 2 * 8192;
102 ff_ivi_mb_vlc_tabs[i].table_allocated = 8192;
103 ff_ivi_create_huff_from_desc(&ff_ivi_mb_huff_desc[i], &ff_ivi_mb_vlc_tabs[i], 1);
104 ff_ivi_blk_vlc_tabs[i].table = table_data + (i * 2 + 1) * 8192;
105 ff_ivi_blk_vlc_tabs[i].table_allocated = 8192;
106 ff_ivi_create_huff_from_desc(&ff_ivi_blk_huff_desc[i], &ff_ivi_blk_vlc_tabs[i], 1);
108 initialized_vlcs = 1;
111 int ff_ivi_dec_huff_desc(GetBitContext *gb, int desc_coded, int which_tab,
112 IVIHuffTab *huff_tab, AVCodecContext *avctx)
115 IVIHuffDesc new_huff;
118 /* select default table */
119 huff_tab->tab = (which_tab) ? &ff_ivi_blk_vlc_tabs[7]
120 : &ff_ivi_mb_vlc_tabs [7];
122 huff_tab->tab_sel = get_bits(gb, 3);
123 if (huff_tab->tab_sel == 7) {
124 /* custom huffman table (explicitly encoded) */
125 new_huff.num_rows = get_bits(gb, 4);
126 if (!new_huff.num_rows) {
127 av_log(avctx, AV_LOG_ERROR, "Empty custom Huffman table!\n");
128 return AVERROR_INVALIDDATA;
131 for (i = 0; i < new_huff.num_rows; i++)
132 new_huff.xbits[i] = get_bits(gb, 4);
134 /* Have we got the same custom table? Rebuild if not. */
135 if (ff_ivi_huff_desc_cmp(&new_huff, &huff_tab->cust_desc) || !huff_tab->cust_tab.table) {
136 ff_ivi_huff_desc_copy(&huff_tab->cust_desc, &new_huff);
138 if (huff_tab->cust_tab.table)
139 ff_free_vlc(&huff_tab->cust_tab);
140 result = ff_ivi_create_huff_from_desc(&huff_tab->cust_desc,
141 &huff_tab->cust_tab, 0);
143 huff_tab->cust_desc.num_rows = 0; // reset faulty description
144 av_log(avctx, AV_LOG_ERROR,
145 "Error while initializing custom vlc table!\n");
149 huff_tab->tab = &huff_tab->cust_tab;
151 /* select one of predefined tables */
152 huff_tab->tab = (which_tab) ? &ff_ivi_blk_vlc_tabs[huff_tab->tab_sel]
153 : &ff_ivi_mb_vlc_tabs [huff_tab->tab_sel];
160 int ff_ivi_huff_desc_cmp(const IVIHuffDesc *desc1, const IVIHuffDesc *desc2)
162 return desc1->num_rows != desc2->num_rows
163 || memcmp(desc1->xbits, desc2->xbits, desc1->num_rows);
166 void ff_ivi_huff_desc_copy(IVIHuffDesc *dst, const IVIHuffDesc *src)
168 dst->num_rows = src->num_rows;
169 memcpy(dst->xbits, src->xbits, src->num_rows);
172 av_cold int ff_ivi_init_planes(IVIPlaneDesc *planes, const IVIPicConfig *cfg)
175 uint32_t b_width, b_height, align_fac, width_aligned, height_aligned, buf_size;
178 ff_ivi_free_buffers(planes);
180 /* fill in the descriptor of the luminance plane */
181 planes[0].width = cfg->pic_width;
182 planes[0].height = cfg->pic_height;
183 planes[0].num_bands = cfg->luma_bands;
185 /* fill in the descriptors of the chrominance planes */
186 planes[1].width = planes[2].width = (cfg->pic_width + 3) >> 2;
187 planes[1].height = planes[2].height = (cfg->pic_height + 3) >> 2;
188 planes[1].num_bands = planes[2].num_bands = cfg->chroma_bands;
190 for (p = 0; p < 3; p++) {
191 planes[p].bands = av_mallocz(planes[p].num_bands * sizeof(IVIBandDesc));
192 if (!planes[p].bands)
193 return AVERROR(ENOMEM);
195 /* select band dimensions: if there is only one band then it
196 * has the full size, if there are several bands each of them
197 * has only half size */
198 b_width = planes[p].num_bands == 1 ? planes[p].width : (planes[p].width + 1) >> 1;
199 b_height = planes[p].num_bands == 1 ? planes[p].height : (planes[p].height + 1) >> 1;
201 /* luma band buffers will be aligned on 16x16 (max macroblock size) */
202 /* chroma band buffers will be aligned on 8x8 (max macroblock size) */
203 align_fac = p ? 8 : 16;
204 width_aligned = FFALIGN(b_width , align_fac);
205 height_aligned = FFALIGN(b_height, align_fac);
206 buf_size = width_aligned * height_aligned * sizeof(int16_t);
208 for (b = 0; b < planes[p].num_bands; b++) {
209 band = &planes[p].bands[b]; /* select appropriate plane/band */
212 band->width = b_width;
213 band->height = b_height;
214 band->pitch = width_aligned;
215 band->aheight = height_aligned;
216 band->bufs[0] = av_mallocz(buf_size);
217 band->bufs[1] = av_mallocz(buf_size);
218 band->bufsize = buf_size/2;
219 if (!band->bufs[0] || !band->bufs[1])
220 return AVERROR(ENOMEM);
222 /* allocate the 3rd band buffer for scalability mode */
223 if (cfg->luma_bands > 1) {
224 band->bufs[2] = av_mallocz(buf_size);
226 return AVERROR(ENOMEM);
229 planes[p].bands[0].blk_vlc.cust_desc.num_rows = 0; /* reset custom vlc */
236 av_cold void ff_ivi_free_buffers(IVIPlaneDesc *planes)
240 for (p = 0; p < 3; p++) {
241 for (b = 0; b < planes[p].num_bands; b++) {
242 av_freep(&planes[p].bands[b].bufs[0]);
243 av_freep(&planes[p].bands[b].bufs[1]);
244 av_freep(&planes[p].bands[b].bufs[2]);
246 if (planes[p].bands[b].blk_vlc.cust_tab.table)
247 ff_free_vlc(&planes[p].bands[b].blk_vlc.cust_tab);
248 for (t = 0; t < planes[p].bands[b].num_tiles; t++)
249 av_freep(&planes[p].bands[b].tiles[t].mbs);
250 av_freep(&planes[p].bands[b].tiles);
252 av_freep(&planes[p].bands);
256 av_cold int ff_ivi_init_tiles(IVIPlaneDesc *planes, int tile_width, int tile_height)
258 int p, b, x, y, x_tiles, y_tiles, t_width, t_height;
260 IVITile *tile, *ref_tile;
262 for (p = 0; p < 3; p++) {
263 t_width = !p ? tile_width : (tile_width + 3) >> 2;
264 t_height = !p ? tile_height : (tile_height + 3) >> 2;
266 if (!p && planes[0].num_bands == 4) {
270 if(t_width<=0 || t_height<=0)
271 return AVERROR(EINVAL);
273 for (b = 0; b < planes[p].num_bands; b++) {
274 band = &planes[p].bands[b];
275 x_tiles = IVI_NUM_TILES(band->width, t_width);
276 y_tiles = IVI_NUM_TILES(band->height, t_height);
277 band->num_tiles = x_tiles * y_tiles;
279 av_freep(&band->tiles);
280 band->tiles = av_mallocz(band->num_tiles * sizeof(IVITile));
282 return AVERROR(ENOMEM);
286 /* use the first luma band as reference for motion vectors
288 ref_tile = planes[0].bands[0].tiles;
290 for (y = 0; y < band->height; y += t_height) {
291 for (x = 0; x < band->width; x += t_width) {
294 tile->mb_size = band->mb_size;
295 tile->width = FFMIN(band->width - x, t_width);
296 tile->height = FFMIN(band->height - y, t_height);
297 tile->is_empty = tile->data_size = 0;
298 /* calculate number of macroblocks */
299 tile->num_MBs = IVI_MBs_PER_TILE(tile->width, tile->height,
302 av_freep(&tile->mbs);
303 tile->mbs = av_malloc(tile->num_MBs * sizeof(IVIMbInfo));
305 return AVERROR(ENOMEM);
309 tile->ref_mbs = ref_tile->mbs;
323 int ff_ivi_dec_tile_data_size(GetBitContext *gb)
329 len = get_bits(gb, 8);
331 len = get_bits_long(gb, 24);
334 /* align the bitstream reader on the byte boundary */
340 int ff_ivi_decode_blocks(GetBitContext *gb, IVIBandDesc *band, IVITile *tile)
342 int mbn, blk, num_blocks, num_coeffs, blk_size, scan_pos, run, val,
343 pos, is_intra, mc_type = 0, mv_x, mv_y, col_mask;
344 uint8_t col_flags[8];
345 int32_t prev_dc, trvec[64];
346 uint32_t cbp, sym, lo, hi, quant, buf_offs, q;
348 RVMapDesc *rvmap = band->rv_map;
349 void (*mc_with_delta_func)(int16_t *buf, const int16_t *ref_buf, uint32_t pitch, int mc_type);
350 void (*mc_no_delta_func) (int16_t *buf, const int16_t *ref_buf, uint32_t pitch, int mc_type);
351 const uint16_t *base_tab;
352 const uint8_t *scale_tab;
354 prev_dc = 0; /* init intra prediction for the DC coefficient */
356 blk_size = band->blk_size;
357 col_mask = blk_size - 1; /* column mask for tracking non-zero coeffs */
358 num_blocks = (band->mb_size != blk_size) ? 4 : 1; /* number of blocks per mb */
359 num_coeffs = blk_size * blk_size;
361 mc_with_delta_func = ff_ivi_mc_8x8_delta;
362 mc_no_delta_func = ff_ivi_mc_8x8_no_delta;
364 mc_with_delta_func = ff_ivi_mc_4x4_delta;
365 mc_no_delta_func = ff_ivi_mc_4x4_no_delta;
368 for (mbn = 0, mb = tile->mbs; mbn < tile->num_MBs; mb++, mbn++) {
369 is_intra = !mb->type;
371 buf_offs = mb->buf_offs;
373 quant = av_clip(band->glob_quant + mb->q_delta, 0, 23);
375 base_tab = is_intra ? band->intra_base : band->inter_base;
376 scale_tab = is_intra ? band->intra_scale : band->inter_scale;
378 quant = scale_tab[quant];
383 if (band->is_halfpel) {
384 mc_type = ((mv_y & 1) << 1) | (mv_x & 1);
386 mv_y >>= 1; /* convert halfpel vectors into fullpel ones */
389 int dmv_x, dmv_y, cx, cy;
391 dmv_x = mb->mv_x >> band->is_halfpel;
392 dmv_y = mb->mv_y >> band->is_halfpel;
393 cx = mb->mv_x & band->is_halfpel;
394 cy = mb->mv_y & band->is_halfpel;
396 if ( mb->xpos + dmv_x < 0
397 || mb->xpos + dmv_x + band->mb_size + cx > band->pitch
398 || mb->ypos + dmv_y < 0
399 || mb->ypos + dmv_y + band->mb_size + cy > band->aheight) {
400 return AVERROR_INVALIDDATA;
405 for (blk = 0; blk < num_blocks; blk++) {
406 /* adjust block position in the buffer according to its number */
408 buf_offs += blk_size;
409 } else if (blk == 2) {
410 buf_offs -= blk_size;
411 buf_offs += blk_size * band->pitch;
414 if (cbp & 1) { /* block coded ? */
416 memset(trvec, 0, num_coeffs*sizeof(trvec[0])); /* zero transform vector */
417 memset(col_flags, 0, sizeof(col_flags)); /* zero column flags */
419 while (scan_pos <= num_coeffs) {
420 sym = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
421 if (sym == rvmap->eob_sym)
422 break; /* End of block */
424 if (sym == rvmap->esc_sym) { /* Escape - run/val explicitly coded using 3 vlc codes */
425 run = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1) + 1;
426 lo = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
427 hi = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
428 val = IVI_TOSIGNED((hi << 6) | lo); /* merge them and convert into signed val */
431 av_log(NULL, AV_LOG_ERROR, "Invalid sym encountered: %d.\n", sym);
434 run = rvmap->runtab[sym];
435 val = rvmap->valtab[sym];
438 /* de-zigzag and dequantize */
440 if (scan_pos >= (unsigned)num_coeffs)
442 pos = band->scan[scan_pos];
445 av_dlog(NULL, "Val = 0 encountered!\n");
447 q = (base_tab[pos] * quant) >> 9;
449 val = val * q + FFSIGN(val) * (((q ^ 1) - 1) >> 1);
451 col_flags[pos & col_mask] |= !!val; /* track columns containing non-zero coeffs */
454 if (scan_pos >= num_coeffs && sym != rvmap->eob_sym)
455 return -1; /* corrupt block data */
457 /* undoing DC coeff prediction for intra-blocks */
458 if (is_intra && band->is_2d_trans) {
461 col_flags[0] |= !!prev_dc;
463 if(band->transform_size > band->blk_size){
464 av_log(0, AV_LOG_ERROR, "Too large transform\n");
465 return AVERROR_INVALIDDATA;
467 /* apply inverse transform */
468 band->inv_transform(trvec, band->buf + buf_offs,
469 band->pitch, col_flags);
471 /* apply motion compensation */
473 mc_with_delta_func(band->buf + buf_offs,
474 band->ref_buf + buf_offs + mv_y * band->pitch + mv_x,
475 band->pitch, mc_type);
477 /* block not coded */
478 /* for intra blocks apply the dc slant transform */
479 /* for inter - perform the motion compensation without delta */
480 if (is_intra && band->dc_transform) {
481 band->dc_transform(&prev_dc, band->buf + buf_offs,
482 band->pitch, blk_size);
484 mc_no_delta_func(band->buf + buf_offs,
485 band->ref_buf + buf_offs + mv_y * band->pitch + mv_x,
486 band->pitch, mc_type);
498 void ff_ivi_process_empty_tile(AVCodecContext *avctx, IVIBandDesc *band,
499 IVITile *tile, int32_t mv_scale)
501 int x, y, need_mc, mbn, blk, num_blocks, mv_x, mv_y, mc_type;
502 int offs, mb_offset, row_offset;
503 IVIMbInfo *mb, *ref_mb;
506 void (*mc_no_delta_func)(int16_t *buf, const int16_t *ref_buf, uint32_t pitch,
509 if( tile->num_MBs != IVI_MBs_PER_TILE(tile->width, tile->height, band->mb_size) ){
510 av_log(avctx, AV_LOG_ERROR, "allocated tile size %d mismatches parameters %d in ff_ivi_process_empty_tile()\n",
511 tile->num_MBs, IVI_MBs_PER_TILE(tile->width, tile->height, band->mb_size));
515 offs = tile->ypos * band->pitch + tile->xpos;
517 ref_mb = tile->ref_mbs;
518 row_offset = band->mb_size * band->pitch;
519 need_mc = 0; /* reset the mc tracking flag */
521 for (y = tile->ypos; y < (tile->ypos + tile->height); y += band->mb_size) {
524 for (x = tile->xpos; x < (tile->xpos + tile->width); x += band->mb_size) {
527 mb->buf_offs = mb_offset;
529 mb->type = 1; /* set the macroblocks type = INTER */
530 mb->cbp = 0; /* all blocks are empty */
532 if (!band->qdelta_present && !band->plane && !band->band_num) {
533 mb->q_delta = band->glob_quant;
538 if (band->inherit_qdelta && ref_mb)
539 mb->q_delta = ref_mb->q_delta;
541 if (band->inherit_mv && ref_mb) {
542 /* motion vector inheritance */
544 mb->mv_x = ivi_scale_mv(ref_mb->mv_x, mv_scale);
545 mb->mv_y = ivi_scale_mv(ref_mb->mv_y, mv_scale);
547 mb->mv_x = ref_mb->mv_x;
548 mb->mv_y = ref_mb->mv_y;
550 need_mc |= mb->mv_x || mb->mv_y; /* tracking non-zero motion vectors */
556 mb_offset += band->mb_size;
561 if (band->inherit_mv && need_mc) { /* apply motion compensation if there is at least one non-zero motion vector */
562 num_blocks = (band->mb_size != band->blk_size) ? 4 : 1; /* number of blocks per mb */
563 mc_no_delta_func = (band->blk_size == 8) ? ff_ivi_mc_8x8_no_delta
564 : ff_ivi_mc_4x4_no_delta;
566 for (mbn = 0, mb = tile->mbs; mbn < tile->num_MBs; mb++, mbn++) {
569 if (!band->is_halfpel) {
570 mc_type = 0; /* we have only fullpel vectors */
572 mc_type = ((mv_y & 1) << 1) | (mv_x & 1);
574 mv_y >>= 1; /* convert halfpel vectors into fullpel ones */
577 for (blk = 0; blk < num_blocks; blk++) {
578 /* adjust block position in the buffer according with its number */
579 offs = mb->buf_offs + band->blk_size * ((blk & 1) + !!(blk & 2) * band->pitch);
580 mc_no_delta_func(band->buf + offs,
581 band->ref_buf + offs + mv_y * band->pitch + mv_x,
582 band->pitch, mc_type);
586 /* copy data from the reference tile into the current one */
587 src = band->ref_buf + tile->ypos * band->pitch + tile->xpos;
588 dst = band->buf + tile->ypos * band->pitch + tile->xpos;
589 for (y = 0; y < tile->height; y++) {
590 memcpy(dst, src, tile->width*sizeof(band->buf[0]));
599 static uint16_t ivi_calc_band_checksum(IVIBandDesc *band)
602 int16_t *src, checksum;
607 for (y = 0; y < band->height; src += band->pitch, y++)
608 for (x = 0; x < band->width; x++)
615 void ff_ivi_output_plane(IVIPlaneDesc *plane, uint8_t *dst, int dst_pitch)
618 const int16_t *src = plane->bands[0].buf;
619 uint32_t pitch = plane->bands[0].pitch;
624 for (y = 0; y < plane->height; y++) {
625 for (x = 0; x < plane->width; x++)
626 dst[x] = av_clip_uint8(src[x] + 128);
633 * Decode an Indeo 4 or 5 band.
635 * @param[in,out] ctx ptr to the decoder context
636 * @param[in,out] band ptr to the band descriptor
637 * @param[in] avctx ptr to the AVCodecContext
638 * @return result code: 0 = OK, -1 = error
640 static int decode_band(IVI45DecContext *ctx, int plane_num,
641 IVIBandDesc *band, AVCodecContext *avctx)
643 int result, i, t, idx1, idx2, pos;
646 band->buf = band->bufs[ctx->dst_buf];
648 av_log(avctx, AV_LOG_ERROR, "Band buffer points to no data!\n");
649 return AVERROR_INVALIDDATA;
651 band->ref_buf = band->bufs[ctx->ref_buf];
652 band->data_ptr = ctx->frame_data + (get_bits_count(&ctx->gb) >> 3);
654 result = ctx->decode_band_hdr(ctx, band, avctx);
656 av_log(avctx, AV_LOG_ERROR, "Error while decoding band header: %d\n",
661 if (band->is_empty) {
662 av_log(avctx, AV_LOG_ERROR, "Empty band encountered!\n");
663 return AVERROR_INVALIDDATA;
666 band->rv_map = &ctx->rvmap_tabs[band->rvmap_sel];
668 /* apply corrections to the selected rvmap table if present */
669 for (i = 0; i < band->num_corr; i++) {
670 idx1 = band->corr[i * 2];
671 idx2 = band->corr[i * 2 + 1];
672 FFSWAP(uint8_t, band->rv_map->runtab[idx1], band->rv_map->runtab[idx2]);
673 FFSWAP(int16_t, band->rv_map->valtab[idx1], band->rv_map->valtab[idx2]);
674 if (idx1 == band->rv_map->eob_sym || idx2 == band->rv_map->eob_sym)
675 band->rv_map->eob_sym ^= idx1 ^ idx2;
676 if (idx1 == band->rv_map->esc_sym || idx2 == band->rv_map->esc_sym)
677 band->rv_map->esc_sym ^= idx1 ^ idx2;
680 pos = get_bits_count(&ctx->gb);
682 for (t = 0; t < band->num_tiles; t++) {
683 tile = &band->tiles[t];
685 if (tile->mb_size != band->mb_size) {
686 av_log(avctx, AV_LOG_ERROR, "MB sizes mismatch: %d vs. %d\n",
687 band->mb_size, tile->mb_size);
688 return AVERROR_INVALIDDATA;
690 tile->is_empty = get_bits1(&ctx->gb);
691 if (tile->is_empty) {
692 ff_ivi_process_empty_tile(avctx, band, tile,
693 (ctx->planes[0].bands[0].mb_size >> 3) - (band->mb_size >> 3));
694 av_dlog(avctx, "Empty tile encountered!\n");
696 tile->data_size = ff_ivi_dec_tile_data_size(&ctx->gb);
697 if (!tile->data_size) {
698 av_log(avctx, AV_LOG_ERROR, "Tile data size is zero!\n");
699 result = AVERROR_INVALIDDATA;
703 result = ctx->decode_mb_info(ctx, band, tile, avctx);
707 result = ff_ivi_decode_blocks(&ctx->gb, band, tile);
708 if (result < 0 || ((get_bits_count(&ctx->gb) - pos) >> 3) != tile->data_size) {
709 av_log(avctx, AV_LOG_ERROR, "Corrupted tile data encountered!\n");
713 pos += tile->data_size << 3; // skip to next tile
717 /* restore the selected rvmap table by applying its corrections in reverse order */
718 for (i = band->num_corr-1; i >= 0; i--) {
719 idx1 = band->corr[i*2];
720 idx2 = band->corr[i*2+1];
721 FFSWAP(uint8_t, band->rv_map->runtab[idx1], band->rv_map->runtab[idx2]);
722 FFSWAP(int16_t, band->rv_map->valtab[idx1], band->rv_map->valtab[idx2]);
723 if (idx1 == band->rv_map->eob_sym || idx2 == band->rv_map->eob_sym)
724 band->rv_map->eob_sym ^= idx1 ^ idx2;
725 if (idx1 == band->rv_map->esc_sym || idx2 == band->rv_map->esc_sym)
726 band->rv_map->esc_sym ^= idx1 ^ idx2;
730 if (band->checksum_present) {
731 uint16_t chksum = ivi_calc_band_checksum(band);
732 if (chksum != band->checksum) {
733 av_log(avctx, AV_LOG_ERROR,
734 "Band checksum mismatch! Plane %d, band %d, received: %x, calculated: %x\n",
735 band->plane, band->band_num, band->checksum, chksum);
740 align_get_bits(&ctx->gb);
745 int ff_ivi_decode_frame(AVCodecContext *avctx, void *data, int *data_size,
748 IVI45DecContext *ctx = avctx->priv_data;
749 const uint8_t *buf = avpkt->data;
750 int buf_size = avpkt->size;
753 init_get_bits(&ctx->gb, buf, buf_size * 8);
754 ctx->frame_data = buf;
755 ctx->frame_size = buf_size;
757 result = ctx->decode_pic_hdr(ctx, avctx);
758 if (result || ctx->gop_invalid) {
759 av_log(avctx, AV_LOG_ERROR,
760 "Error while decoding picture header: %d\n", result);
764 if (ctx->gop_flags & IVI5_IS_PROTECTED) {
765 av_log(avctx, AV_LOG_ERROR, "Password-protected clip!\n");
769 ctx->switch_buffers(ctx);
773 if (ctx->is_nonnull_frame(ctx)) {
774 ctx->buf_invalid[ctx->dst_buf] = 1;
775 for (p = 0; p < 3; p++) {
776 for (b = 0; b < ctx->planes[p].num_bands; b++) {
777 result = decode_band(ctx, p, &ctx->planes[p].bands[b], avctx);
779 av_log(avctx, AV_LOG_ERROR,
780 "Error while decoding band: %d, plane: %d\n", b, p);
785 ctx->buf_invalid[ctx->dst_buf] = 0;
787 if (ctx->buf_invalid[ctx->dst_buf])
790 //STOP_TIMER("decode_planes"); }
792 /* If the bidirectional mode is enabled, next I and the following P frame will */
793 /* be sent together. Unfortunately the approach below seems to be the only way */
794 /* to handle the B-frames mode. That's exactly the same Intel decoders do. */
795 if (avctx->codec_id == CODEC_ID_INDEO4 && ctx->frame_type == 0/*FRAMETYPE_INTRA*/) {
796 while (get_bits(&ctx->gb, 8)); // skip version string
797 skip_bits_long(&ctx->gb, 64); // skip padding, TODO: implement correct 8-bytes alignment
798 if (get_bits_left(&ctx->gb) > 18 && show_bits(&ctx->gb, 18) == 0x3FFF8)
799 av_log(avctx, AV_LOG_ERROR, "Buffer contains IP frames!\n");
802 if (avctx->codec_id == CODEC_ID_INDEO4 && !ctx->is_nonnull_frame(ctx))
805 if (ctx->frame.data[0])
806 avctx->release_buffer(avctx, &ctx->frame);
808 avcodec_set_dimensions(avctx, ctx->planes[0].width, ctx->planes[0].height);
809 ctx->frame.reference = 0;
810 if ((result = avctx->get_buffer(avctx, &ctx->frame)) < 0) {
811 av_log(avctx, AV_LOG_ERROR, "get_buffer() failed\n");
815 if (ctx->is_scalable) {
816 if (avctx->codec_id == CODEC_ID_INDEO4)
817 ff_ivi_recompose_haar(&ctx->planes[0], ctx->frame.data[0], ctx->frame.linesize[0], 4);
819 ff_ivi_recompose53 (&ctx->planes[0], ctx->frame.data[0], ctx->frame.linesize[0], 4);
821 ff_ivi_output_plane(&ctx->planes[0], ctx->frame.data[0], ctx->frame.linesize[0]);
824 ff_ivi_output_plane(&ctx->planes[2], ctx->frame.data[1], ctx->frame.linesize[1]);
825 ff_ivi_output_plane(&ctx->planes[1], ctx->frame.data[2], ctx->frame.linesize[2]);
827 *data_size = sizeof(AVFrame);
828 *(AVFrame*)data = ctx->frame;
834 * Close Indeo5 decoder and clean up its context.
836 av_cold int ff_ivi_decode_close(AVCodecContext *avctx)
838 IVI45DecContext *ctx = avctx->priv_data;
840 ff_ivi_free_buffers(&ctx->planes[0]);
842 if (ctx->mb_vlc.cust_tab.table)
843 ff_free_vlc(&ctx->mb_vlc.cust_tab);
845 if (ctx->frame.data[0])
846 avctx->release_buffer(avctx, &ctx->frame);
848 #if IVI4_STREAM_ANALYSER
849 if (avctx->codec_id == CODEC_ID_INDEO4) {
850 if (ctx->is_scalable)
851 av_log(avctx, AV_LOG_ERROR, "This video uses scalability mode!\n");
852 if (ctx->uses_tiling)
853 av_log(avctx, AV_LOG_ERROR, "This video uses local decoding!\n");
854 if (ctx->has_b_frames)
855 av_log(avctx, AV_LOG_ERROR, "This video contains B-frames!\n");
857 av_log(avctx, AV_LOG_ERROR, "Transparency mode is enabled!\n");
859 av_log(avctx, AV_LOG_ERROR, "This video uses Haar transform!\n");
860 if (ctx->uses_fullpel)
861 av_log(avctx, AV_LOG_ERROR, "This video uses fullpel motion vectors!\n");
870 * These are 2x8 predefined Huffman codebooks for coding macroblock/block
871 * signals. They are specified using "huffman descriptors" in order to
872 * avoid huge static tables. The decoding tables will be generated at
873 * startup from these descriptors.
875 const IVIHuffDesc ff_ivi_mb_huff_desc[8] = {
876 {8, {0, 4, 5, 4, 4, 4, 6, 6}},
877 {12, {0, 2, 2, 3, 3, 3, 3, 5, 3, 2, 2, 2}},
878 {12, {0, 2, 3, 4, 3, 3, 3, 3, 4, 3, 2, 2}},
879 {12, {0, 3, 4, 4, 3, 3, 3, 3, 3, 2, 2, 2}},
880 {13, {0, 4, 4, 3, 3, 3, 3, 2, 3, 3, 2, 1, 1}},
881 {9, {0, 4, 4, 4, 4, 3, 3, 3, 2}},
882 {10, {0, 4, 4, 4, 4, 3, 3, 2, 2, 2}},
883 {12, {0, 4, 4, 4, 3, 3, 2, 3, 2, 2, 2, 2}}
886 const IVIHuffDesc ff_ivi_blk_huff_desc[8] = {
887 {10, {1, 2, 3, 4, 4, 7, 5, 5, 4, 1}},
888 {11, {2, 3, 4, 4, 4, 7, 5, 4, 3, 3, 2}},
889 {12, {2, 4, 5, 5, 5, 5, 6, 4, 4, 3, 1, 1}},
890 {13, {3, 3, 4, 4, 5, 6, 6, 4, 4, 3, 2, 1, 1}},
891 {11, {3, 4, 4, 5, 5, 5, 6, 5, 4, 2, 2}},
892 {13, {3, 4, 5, 5, 5, 5, 6, 4, 3, 3, 2, 1, 1}},
893 {13, {3, 4, 5, 5, 5, 6, 5, 4, 3, 3, 2, 1, 1}},
894 {9, {3, 4, 4, 5, 5, 5, 6, 5, 5}}
899 * Scan patterns shared between indeo4 and indeo5
901 const uint8_t ff_ivi_vertical_scan_8x8[64] = {
902 0, 8, 16, 24, 32, 40, 48, 56,
903 1, 9, 17, 25, 33, 41, 49, 57,
904 2, 10, 18, 26, 34, 42, 50, 58,
905 3, 11, 19, 27, 35, 43, 51, 59,
906 4, 12, 20, 28, 36, 44, 52, 60,
907 5, 13, 21, 29, 37, 45, 53, 61,
908 6, 14, 22, 30, 38, 46, 54, 62,
909 7, 15, 23, 31, 39, 47, 55, 63
912 const uint8_t ff_ivi_horizontal_scan_8x8[64] = {
913 0, 1, 2, 3, 4, 5, 6, 7,
914 8, 9, 10, 11, 12, 13, 14, 15,
915 16, 17, 18, 19, 20, 21, 22, 23,
916 24, 25, 26, 27, 28, 29, 30, 31,
917 32, 33, 34, 35, 36, 37, 38, 39,
918 40, 41, 42, 43, 44, 45, 46, 47,
919 48, 49, 50, 51, 52, 53, 54, 55,
920 56, 57, 58, 59, 60, 61, 62, 63
923 const uint8_t ff_ivi_direct_scan_4x4[16] = {
924 0, 1, 4, 8, 5, 2, 3, 6, 9, 12, 13, 10, 7, 11, 14, 15
929 * Run-value (RLE) tables.
931 const RVMapDesc ff_ivi_rvmap_tabs[9] = {
936 {1, 1, 0, 1, 1, 0, 1, 1, 2, 2, 1, 1, 1, 1, 3, 3,
937 1, 1, 2, 2, 1, 1, 4, 4, 1, 1, 1, 1, 2, 2, 5, 5,
938 1, 1, 3, 3, 1, 1, 6, 6, 1, 2, 1, 2, 7, 7, 1, 1,
939 8, 8, 1, 1, 4, 2, 1, 4, 2, 1, 3, 3, 1, 1, 1, 9,
940 9, 1, 2, 1, 2, 1, 5, 5, 1, 1, 10, 10, 1, 1, 3, 3,
941 2, 2, 1, 1, 11, 11, 6, 4, 4, 1, 6, 1, 2, 1, 2, 12,
942 8, 1, 12, 7, 8, 7, 1, 16, 1, 16, 1, 3, 3, 13, 1, 13,
943 2, 2, 1, 15, 1, 5, 14, 15, 1, 5, 14, 1, 17, 8, 17, 8,
944 1, 4, 4, 2, 2, 1, 25, 25, 24, 24, 1, 3, 1, 3, 1, 8,
945 6, 7, 6, 1, 18, 8, 18, 1, 7, 23, 2, 2, 23, 1, 1, 21,
946 22, 9, 9, 22, 19, 1, 21, 5, 19, 5, 1, 33, 20, 33, 20, 8,
947 4, 4, 1, 32, 2, 2, 8, 3, 32, 26, 3, 1, 7, 7, 26, 6,
948 1, 6, 1, 1, 16, 1, 10, 1, 10, 2, 16, 29, 28, 2, 29, 28,
949 1, 27, 5, 8, 5, 27, 1, 8, 3, 7, 3, 31, 41, 31, 1, 41,
950 6, 1, 6, 7, 4, 4, 1, 1, 2, 1, 2, 11, 34, 30, 11, 1,
951 30, 15, 15, 34, 36, 40, 36, 40, 35, 35, 37, 37, 39, 39, 38, 38},
954 { 1, -1, 0, 2, -2, 0, 3, -3, 1, -1, 4, -4, 5, -5, 1, -1,
955 6, -6, 2, -2, 7, -7, 1, -1, 8, -8, 9, -9, 3, -3, 1, -1,
956 10, -10, 2, -2, 11, -11, 1, -1, 12, 4, -12, -4, 1, -1, 13, -13,
957 1, -1, 14, -14, 2, 5, 15, -2, -5, -15, -3, 3, 16, -16, 17, 1,
958 -1, -17, 6, 18, -6, -18, 2, -2, 19, -19, 1, -1, 20, -20, 4, -4,
959 7, -7, 21, -21, 1, -1, 2, 3, -3, 22, -2, -22, 8, 23, -8, 1,
960 2, -23, -1, 2, -2, -2, 24, 1, -24, -1, 25, 5, -5, 1, -25, -1,
961 9, -9, 26, 1, -26, 3, 1, -1, 27, -3, -1, -27, 1, 3, -1, -3,
962 28, -4, 4, 10, -10, -28, 1, -1, 1, -1, 29, 6, -29, -6, 30, -4,
963 3, 3, -3, -30, 1, 4, -1, 31, -3, 1, 11, -11, -1, -31, 32, -1,
964 -1, 2, -2, 1, 1, -32, 1, 4, -1, -4, 33, -1, 1, 1, -1, 5,
965 5, -5, -33, -1, -12, 12, -5, -7, 1, 1, 7, 34, 4, -4, -1, 4,
966 -34, -4, 35, 36, -2, -35, -2, -36, 2, 13, 2, -1, 1, -13, 1, -1,
967 37, 1, -5, 6, 5, -1, 38, -6, -8, 5, 8, -1, 1, 1, -37, -1,
968 5, 39, -5, -5, 6, -6, -38, -39, -14, 40, 14, 2, 1, 1, -2, -40,
969 -1, -2, 2, -1, -1, -1, 1, 1, 1, -1, 1, -1, 1, -1, 1, -1}
975 {0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 8, 6, 8, 7,
976 7, 9, 9, 10, 10, 11, 11, 1, 12, 1, 12, 13, 13, 16, 14, 16,
977 14, 15, 15, 17, 17, 18, 0, 18, 19, 20, 21, 19, 22, 21, 20, 22,
978 25, 24, 2, 25, 24, 23, 23, 2, 26, 28, 26, 28, 29, 27, 29, 27,
979 33, 33, 1, 32, 1, 3, 32, 30, 36, 3, 36, 30, 31, 31, 35, 34,
980 37, 41, 34, 35, 37, 4, 41, 4, 49, 8, 8, 49, 40, 38, 5, 38,
981 40, 39, 5, 39, 42, 43, 42, 7, 57, 6, 43, 44, 6, 50, 7, 44,
982 57, 48, 50, 48, 45, 45, 46, 47, 51, 46, 47, 58, 1, 51, 58, 1,
983 52, 59, 53, 9, 52, 55, 55, 59, 53, 56, 54, 56, 54, 9, 64, 64,
984 60, 63, 60, 63, 61, 62, 61, 62, 2, 10, 2, 10, 11, 1, 11, 13,
985 12, 1, 12, 13, 16, 16, 8, 8, 14, 3, 3, 15, 14, 15, 4, 4,
986 1, 17, 17, 5, 1, 7, 7, 5, 6, 1, 2, 2, 6, 22, 1, 25,
987 21, 22, 8, 24, 1, 21, 25, 24, 8, 18, 18, 23, 9, 20, 23, 33,
988 29, 33, 20, 1, 19, 1, 29, 36, 9, 36, 19, 41, 28, 57, 32, 3,
989 28, 3, 1, 27, 49, 49, 1, 32, 26, 26, 2, 4, 4, 7, 57, 41,
990 2, 7, 10, 5, 37, 16, 10, 27, 8, 8, 13, 16, 37, 13, 1, 5},
993 {0, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, 1, -1, -1, 1,
994 -1, 1, -1, 1, -1, 1, -1, 2, 1, -2, -1, 1, -1, 1, 1, -1,
995 -1, 1, -1, 1, -1, 1, 0, -1, 1, 1, 1, -1, 1, -1, -1, -1,
996 1, 1, 2, -1, -1, 1, -1, -2, 1, 1, -1, -1, 1, 1, -1, -1,
997 1, -1, 3, 1, -3, 2, -1, 1, 1, -2, -1, -1, -1, 1, 1, 1,
998 1, 1, -1, -1, -1, 2, -1, -2, 1, 2, -2, -1, 1, 1, 2, -1,
999 -1, 1, -2, -1, 1, 1, -1, 2, 1, 2, -1, 1, -2, -1, -2, -1,
1000 -1, 1, 1, -1, 1, -1, 1, 1, 1, -1, -1, 1, 4, -1, -1, -4,
1001 1, 1, 1, 2, -1, -1, 1, -1, -1, 1, -1, -1, 1, -2, 1, -1,
1002 1, 1, -1, -1, 1, 1, -1, -1, 3, 2, -3, -2, 2, 5, -2, 2,
1003 2, -5, -2, -2, -2, 2, -3, 3, 2, 3, -3, 2, -2, -2, 3, -3,
1004 6, 2, -2, 3, -6, 3, -3, -3, 3, 7, -4, 4, -3, 2, -7, 2,
1005 2, -2, -4, 2, 8, -2, -2, -2, 4, 2, -2, 2, 3, 2, -2, -2,
1006 2, 2, -2, -8, -2, 9, -2, 2, -3, -2, 2, -2, 2, 2, 2, 4,
1007 -2, -4, 10, 2, 2, -2, -9, -2, 2, -2, 5, 4, -4, 4, -2, 2,
1008 -5, -4, -3, 4, 2, -3, 3, -2, -5, 5, 3, 3, -2, -3, -10, -4}
1014 {1, 1, 0, 2, 2, 1, 1, 3, 3, 4, 4, 0, 1, 1, 5, 5,
1015 2, 2, 6, 6, 7, 7, 1, 8, 1, 8, 3, 3, 9, 9, 1, 2,
1016 2, 1, 4, 10, 4, 10, 11, 11, 1, 5, 12, 12, 1, 5, 13, 13,
1017 3, 3, 6, 6, 2, 2, 14, 14, 16, 16, 15, 7, 15, 8, 8, 7,
1018 1, 1, 17, 17, 4, 4, 1, 1, 18, 18, 2, 2, 5, 5, 25, 3,
1019 9, 3, 25, 9, 19, 24, 19, 24, 1, 21, 20, 1, 21, 22, 20, 22,
1020 23, 23, 8, 6, 33, 6, 8, 33, 7, 7, 26, 26, 1, 32, 1, 32,
1021 28, 4, 28, 10, 29, 27, 27, 10, 41, 4, 29, 2, 2, 41, 36, 31,
1022 49, 31, 34, 30, 34, 36, 30, 35, 1, 49, 11, 5, 35, 11, 1, 3,
1023 3, 5, 37, 37, 8, 40, 8, 40, 12, 12, 42, 42, 1, 38, 16, 57,
1024 1, 6, 16, 39, 38, 6, 7, 7, 13, 13, 39, 43, 2, 43, 57, 2,
1025 50, 9, 44, 9, 50, 4, 15, 48, 44, 4, 1, 15, 48, 14, 14, 1,
1026 45, 45, 8, 3, 5, 8, 51, 47, 3, 46, 46, 47, 5, 51, 1, 17,
1027 17, 58, 1, 58, 2, 52, 52, 2, 53, 7, 59, 6, 6, 56, 53, 55,
1028 7, 55, 1, 54, 59, 56, 54, 10, 1, 10, 4, 60, 1, 60, 8, 4,
1029 8, 64, 64, 61, 1, 63, 3, 63, 62, 61, 5, 11, 5, 3, 11, 62},
1032 { 1, -1, 0, 1, -1, 2, -2, 1, -1, 1, -1, 0, 3, -3, 1, -1,
1033 2, -2, 1, -1, 1, -1, 4, 1, -4, -1, 2, -2, 1, -1, 5, 3,
1034 -3, -5, 2, 1, -2, -1, 1, -1, 6, 2, 1, -1, -6, -2, 1, -1,
1035 3, -3, 2, -2, 4, -4, 1, -1, 1, -1, 1, 2, -1, 2, -2, -2,
1036 7, -7, 1, -1, 3, -3, 8, -8, 1, -1, 5, -5, 3, -3, 1, 4,
1037 2, -4, -1, -2, 1, 1, -1, -1, 9, 1, 1, -9, -1, 1, -1, -1,
1038 1, -1, 3, -3, 1, 3, -3, -1, 3, -3, 1, -1, 10, 1, -10, -1,
1039 1, 4, -1, 2, 1, -1, 1, -2, 1, -4, -1, 6, -6, -1, 1, 1,
1040 1, -1, 1, 1, -1, -1, -1, 1, 11, -1, -2, 4, -1, 2, -11, 5,
1041 -5, -4, -1, 1, 4, 1, -4, -1, -2, 2, 1, -1, 12, 1, -2, 1,
1042 -12, 4, 2, 1, -1, -4, 4, -4, 2, -2, -1, 1, 7, -1, -1, -7,
1043 -1, -3, 1, 3, 1, 5, 2, 1, -1, -5, 13, -2, -1, 2, -2, -13,
1044 1, -1, 5, 6, 5, -5, 1, 1, -6, 1, -1, -1, -5, -1, 14, 2,
1045 -2, 1, -14, -1, 8, 1, -1, -8, 1, 5, 1, 5, -5, 1, -1, 1,
1046 -5, -1, 15, 1, -1, -1, -1, 3, -15, -3, 6, 1, 16, -1, 6, -6,
1047 -6, 1, -1, 1, -16, 1, 7, -1, 1, -1, -6, -3, 6, -7, 3, -1}
1053 {0, 1, 1, 2, 2, 3, 3, 4, 4, 1, 1, 5, 5, 6, 6, 7,
1054 7, 8, 8, 9, 9, 2, 2, 10, 10, 1, 1, 11, 11, 12, 12, 3,
1055 3, 13, 13, 0, 14, 14, 16, 15, 16, 15, 4, 4, 17, 1, 17, 1,
1056 5, 5, 18, 18, 2, 2, 6, 6, 8, 19, 7, 8, 7, 19, 20, 20,
1057 21, 21, 22, 24, 22, 24, 23, 23, 1, 1, 25, 25, 3, 3, 26, 26,
1058 9, 9, 27, 27, 28, 28, 33, 29, 4, 33, 29, 1, 4, 1, 32, 32,
1059 2, 2, 31, 10, 30, 10, 30, 31, 34, 34, 5, 5, 36, 36, 35, 41,
1060 35, 11, 41, 11, 37, 1, 8, 8, 37, 6, 1, 6, 40, 7, 7, 40,
1061 12, 38, 12, 39, 39, 38, 49, 13, 49, 13, 3, 42, 3, 42, 16, 16,
1062 43, 43, 14, 14, 1, 1, 44, 15, 44, 15, 2, 2, 57, 48, 50, 48,
1063 57, 50, 4, 45, 45, 4, 46, 47, 47, 46, 1, 51, 1, 17, 17, 51,
1064 8, 9, 9, 5, 58, 8, 58, 5, 52, 52, 55, 56, 53, 56, 55, 59,
1065 59, 53, 54, 1, 6, 54, 7, 7, 6, 1, 2, 3, 2, 3, 64, 60,
1066 60, 10, 10, 64, 61, 62, 61, 63, 1, 63, 62, 1, 18, 24, 18, 4,
1067 25, 4, 8, 21, 21, 1, 24, 22, 25, 22, 8, 11, 19, 11, 23, 1,
1068 20, 23, 19, 20, 5, 12, 5, 1, 16, 2, 12, 13, 2, 13, 1, 16},
1071 { 0, 1, -1, 1, -1, 1, -1, 1, -1, 2, -2, 1, -1, 1, -1, 1,
1072 -1, 1, -1, 1, -1, 2, -2, 1, -1, 3, -3, 1, -1, 1, -1, 2,
1073 -2, 1, -1, 0, 1, -1, 1, 1, -1, -1, 2, -2, 1, 4, -1, -4,
1074 2, -2, 1, -1, -3, 3, 2, -2, 2, 1, 2, -2, -2, -1, 1, -1,
1075 1, -1, 1, 1, -1, -1, 1, -1, 5, -5, 1, -1, 3, -3, 1, -1,
1076 2, -2, 1, -1, 1, -1, 1, 1, 3, -1, -1, 6, -3, -6, -1, 1,
1077 4, -4, 1, 2, 1, -2, -1, -1, 1, -1, 3, -3, 1, -1, 1, 1,
1078 -1, 2, -1, -2, 1, 7, -3, 3, -1, 3, -7, -3, 1, -3, 3, -1,
1079 2, 1, -2, 1, -1, -1, 1, 2, -1, -2, -4, -1, 4, 1, 2, -2,
1080 1, -1, -2, 2, 8, -8, -1, 2, 1, -2, -5, 5, 1, -1, -1, 1,
1081 -1, 1, 4, -1, 1, -4, -1, -1, 1, 1, 9, 1, -9, 2, -2, -1,
1082 -4, 3, -3, -4, -1, 4, 1, 4, 1, -1, 1, -1, 1, 1, -1, 1,
1083 -1, -1, -1, 10, 4, 1, 4, -4, -4, -10, 6, 5, -6, -5, 1, -1,
1084 1, 3, -3, -1, 1, -1, -1, -1, 11, 1, 1, -11, -2, -2, 2, 5,
1085 -2, -5, -5, 2, -2, 12, 2, -2, 2, 2, 5, -3, -2, 3, -2, -12,
1086 -2, 2, 2, 2, -5, 3, 5, 13, -3, 7, -3, -3, -7, 3, -13, 3}
1092 {0, 1, 1, 1, 2, 2, 1, 3, 3, 1, 1, 1, 4, 4, 1, 5,
1093 2, 1, 5, 2, 1, 1, 6, 6, 1, 1, 1, 1, 1, 7, 3, 1,
1094 2, 3, 0, 1, 2, 7, 1, 1, 1, 8, 1, 1, 8, 1, 1, 1,
1095 9, 1, 9, 1, 2, 1, 1, 2, 1, 1, 10, 4, 1, 10, 1, 4,
1096 1, 1, 1, 1, 1, 3, 1, 1, 1, 3, 2, 1, 5, 1, 1, 1,
1097 2, 5, 1, 11, 1, 11, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1098 2, 1, 6, 1, 6, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 12,
1099 3, 1, 12, 1, 1, 1, 2, 1, 1, 3, 1, 1, 1, 1, 1, 1,
1100 4, 1, 1, 1, 2, 1, 1, 4, 1, 1, 1, 1, 1, 1, 2, 1,
1101 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 2, 1, 1, 5,
1102 1, 1, 1, 1, 1, 7, 1, 7, 1, 1, 2, 3, 1, 1, 1, 1,
1103 5, 1, 1, 1, 1, 1, 1, 2, 13, 1, 1, 1, 1, 1, 1, 1,
1104 1, 1, 1, 1, 1, 1, 1, 1, 13, 2, 1, 1, 4, 1, 1, 1,
1105 3, 1, 6, 1, 1, 1, 14, 1, 1, 1, 1, 1, 14, 6, 1, 1,
1106 1, 1, 15, 2, 4, 1, 2, 3, 15, 1, 1, 1, 8, 1, 1, 8,
1107 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1},
1110 { 0, 1, -1, 2, 1, -1, -2, 1, -1, 3, -3, 4, 1, -1, -4, 1,
1111 2, 5, -1, -2, -5, 6, 1, -1, -6, 7, -7, 8, -8, 1, 2, 9,
1112 3, -2, 0, -9, -3, -1, 10, -10, 11, 1, -11, 12, -1, -12, 13, -13,
1113 1, 14, -1, -14, 4, 15, -15, -4, 16, -16, 1, 2, 17, -1, -17, -2,
1114 18, -18, 19, -19, 20, 3, -20, 21, -21, -3, 5, 22, 2, -22, -23, 23,
1115 -5, -2, 24, 1, -24, -1, 25, -25, 26, -26, -27, 27, 28, 29, -28, -29,
1116 6, 30, 2, -31, -2, -30, 31, -6, -32, 32, 33, -33, 34, -35, -34, 1,
1117 4, -36, -1, 35, 37, 36, 7, -37, 38, -4, -38, 39, 41, 40, -40, -39,
1118 3, 42, -43, -41, -7, -42, 43, -3, 44, -44, 45, -45, 46, 47, 8, -47,
1119 -48, -46, 50, -50, 48, 49, 51, -49, 52, -52, 5, -51, -8, -53, 53, 3,
1120 -56, 56, 55, 54, -54, 2, 60, -2, -55, 58, 9, -5, 59, 57, -57, -63,
1121 -3, -58, -60, -61, 61, -59, -62, -9, 1, 64, 62, 69, -64, 63, 65, -67,
1122 -68, 66, -65, 68, -66, -69, 67, -70, -1, 10, 71, -71, 4, 73, 72, 70,
1123 6, -76, -3, 74, -78, -74, 1, 78, 80, -72, -75, 76, -1, 3, -73, 79,
1124 75, 77, 1, 11, -4, -79, -10, -6, -1, -77, -83, -80, 2, 81, -84, -2,
1125 83, -81, 82, -82, 84, -87, -86, 85, -11, -85, 86, -89, 87, -88, 88, 89}
1131 {1, 1, 0, 2, 1, 2, 1, 3, 3, 1, 1, 4, 4, 2, 2, 1,
1132 1, 5, 5, 6, 1, 6, 1, 7, 7, 3, 3, 2, 8, 2, 8, 1,
1133 1, 0, 9, 9, 1, 1, 10, 4, 10, 4, 11, 11, 2, 1, 2, 1,
1134 12, 12, 3, 3, 1, 1, 13, 5, 5, 13, 14, 1, 1, 14, 2, 2,
1135 6, 6, 15, 1, 1, 15, 16, 4, 7, 16, 4, 7, 1, 1, 3, 3,
1136 8, 8, 2, 2, 1, 1, 17, 17, 1, 1, 18, 18, 5, 5, 2, 2,
1137 1, 1, 9, 19, 9, 19, 20, 3, 3, 20, 1, 10, 21, 1, 10, 4,
1138 4, 21, 22, 6, 6, 22, 1, 1, 23, 24, 2, 2, 23, 24, 11, 1,
1139 1, 11, 7, 25, 7, 1, 1, 25, 8, 8, 3, 26, 3, 1, 12, 2,
1140 2, 26, 1, 12, 5, 5, 27, 4, 1, 4, 1, 27, 28, 1, 28, 13,
1141 1, 13, 2, 29, 2, 1, 32, 6, 1, 30, 14, 29, 14, 6, 3, 31,
1142 3, 1, 30, 1, 32, 31, 33, 9, 33, 1, 1, 7, 9, 7, 2, 2,
1143 1, 1, 4, 36, 34, 4, 5, 10, 10, 5, 34, 1, 1, 35, 8, 8,
1144 36, 3, 35, 1, 15, 3, 2, 1, 16, 15, 16, 2, 37, 1, 37, 1,
1145 1, 1, 6, 6, 38, 1, 38, 11, 1, 39, 39, 40, 11, 2, 41, 4,
1146 40, 1, 2, 4, 1, 1, 1, 41, 3, 1, 3, 1, 5, 7, 5, 7},
1149 { 1, -1, 0, 1, 2, -1, -2, 1, -1, 3, -3, 1, -1, 2, -2, 4,
1150 -4, 1, -1, 1, 5, -1, -5, 1, -1, 2, -2, 3, 1, -3, -1, 6,
1151 -6, 0, 1, -1, 7, -7, 1, 2, -1, -2, 1, -1, 4, 8, -4, -8,
1152 1, -1, 3, -3, 9, -9, 1, 2, -2, -1, 1, 10, -10, -1, 5, -5,
1153 2, -2, 1, 11, -11, -1, 1, 3, 2, -1, -3, -2, 12, -12, 4, -4,
1154 2, -2, -6, 6, 13, -13, 1, -1, 14, -14, 1, -1, 3, -3, 7, -7,
1155 15, -15, 2, 1, -2, -1, 1, 5, -5, -1, -16, 2, 1, 16, -2, 4,
1156 -4, -1, 1, 3, -3, -1, 17, -17, 1, 1, -8, 8, -1, -1, 2, 18,
1157 -18, -2, 3, 1, -3, 19, -19, -1, 3, -3, 6, 1, -6, 20, 2, 9,
1158 -9, -1, -20, -2, 4, -4, 1, -5, 21, 5, -21, -1, 1, -22, -1, 2,
1159 22, -2, 10, 1, -10, 23, 1, 4, -23, 1, 2, -1, -2, -4, -7, 1,
1160 7, -24, -1, 24, -1, -1, 1, 3, -1, -25, 25, 4, -3, -4, 11, -11,
1161 26, -26, 6, 1, 1, -6, -5, -3, 3, 5, -1, -27, 27, 1, 4, -4,
1162 -1, -8, -1, 28, 2, 8, -12, -28, -2, -2, 2, 12, -1, 29, 1, -29,
1163 30, -30, 5, -5, 1, -31, -1, 3, 31, -1, 1, 1, -3, -13, 1, -7,
1164 -1, -32, 13, 7, 32, 33, -33, -1, -9, -34, 9, 34, -6, 5, 6, -5}
1170 {1, 1, 0, 1, 1, 2, 2, 1, 1, 3, 3, 1, 1, 0, 2, 2,
1171 4, 1, 4, 1, 1, 1, 5, 5, 1, 1, 6, 6, 2, 2, 1, 1,
1172 3, 3, 7, 7, 1, 1, 8, 8, 1, 1, 2, 2, 1, 9, 1, 9,
1173 4, 4, 10, 1, 1, 10, 1, 1, 11, 11, 3, 3, 1, 2, 1, 2,
1174 1, 1, 12, 12, 5, 5, 1, 1, 13, 1, 1, 13, 2, 2, 1, 1,
1175 6, 6, 1, 1, 4, 14, 4, 14, 3, 1, 3, 1, 1, 1, 15, 7,
1176 15, 2, 2, 7, 1, 1, 1, 8, 1, 8, 16, 16, 1, 1, 1, 1,
1177 2, 1, 1, 2, 1, 1, 3, 5, 5, 3, 4, 1, 1, 4, 1, 1,
1178 17, 17, 9, 1, 1, 9, 2, 2, 1, 1, 10, 10, 1, 6, 1, 1,
1179 6, 18, 1, 1, 18, 1, 1, 1, 2, 2, 3, 1, 3, 1, 1, 1,
1180 4, 1, 19, 1, 19, 7, 1, 1, 20, 1, 4, 20, 1, 7, 11, 2,
1181 1, 11, 21, 2, 8, 5, 1, 8, 1, 5, 21, 1, 1, 1, 22, 1,
1182 1, 22, 1, 1, 3, 3, 1, 23, 2, 12, 24, 1, 1, 2, 1, 1,
1183 12, 23, 1, 1, 24, 1, 1, 1, 4, 1, 1, 1, 2, 1, 6, 6,
1184 4, 2, 1, 1, 1, 1, 1, 1, 1, 14, 13, 3, 1, 25, 9, 25,
1185 14, 1, 9, 3, 13, 1, 1, 1, 1, 1, 10, 1, 1, 2, 10, 2},
1188 {-20, -1, 0, 2, -2, 1, -1, 3, -3, 1, -1, 4, -4, 0, 2, -2,
1189 1, 5, -1, -5, 6, -6, 1, -1, 7, -7, 1, -1, 3, -3, 8, -8,
1190 2, -2, 1, -1, 9, -9, 1, -1, 10, -10, 4, -4, 11, 1, -11, -1,
1191 2, -2, 1, 12, -12, -1, 13, -13, 1, -1, 3, -3, 14, 5, -14, -5,
1192 -15, 15, -1, 1, 2, -2, 16, -16, 1, 17, -17, -1, 6, -6, 18, -18,
1193 2, -2, -19, 19, -3, 1, 3, -1, 4, 20, -4, 1, -21, 21, 1, 2,
1194 -1, -7, 7, -2, 22, -22, 23, 2, -23, -2, 1, -1, -24, 24, -25, 25,
1195 -8, -26, 26, 8, -27, 27, 5, 3, -3, -5, -4, 28, -28, 4, 29, -29,
1196 1, -1, -2, -30, 30, 2, 9, -9, -31, 31, 2, -2, -32, 3, 32, -33,
1197 -3, 1, 33, -34, -1, 34, -35, 35, -10, 10, -6, 36, 6, -36, 37, -37,
1198 -5, 38, 1, -38, -1, 3, 39, -39, -1, 40, 5, 1, -40, -3, 2, -11,
1199 -41, -2, 1, 11, -3, -4, 41, 3, 42, 4, -1, -43, -42, 43, 1, -44,
1200 45, -1, 44, -45, -7, 7, -46, 1, -12, 2, 1, -47, 46, 12, 47, 48,
1201 -2, -1, -48, 49, -1, -50, -49, 50, -6, -51, 51, 52, -13, 53, -4, 4,
1202 6, 13, -53, -52, -54, 55, 54, -55, -56, -2, 2, -8, 56, 1, -3, -1,
1203 2, 58, 3, 8, -2, 57, -58, -60, -59, -57, -3, 60, 59, -14, 3, 14}
1209 {1, 1, 0, 2, 2, 1, 1, 3, 3, 4, 4, 5, 5, 1, 1, 6,
1210 6, 2, 2, 7, 7, 8, 8, 1, 1, 3, 3, 9, 9, 10, 10, 1,
1211 1, 2, 2, 4, 4, 11, 0, 11, 12, 12, 13, 13, 1, 1, 5, 5,
1212 14, 14, 15, 16, 15, 16, 3, 3, 1, 6, 1, 6, 2, 2, 7, 7,
1213 8, 8, 17, 17, 1, 1, 4, 4, 18, 18, 2, 2, 1, 19, 1, 20,
1214 19, 20, 21, 21, 3, 3, 22, 22, 5, 5, 24, 1, 1, 23, 9, 23,
1215 24, 9, 2, 2, 10, 1, 1, 10, 6, 6, 25, 4, 4, 25, 7, 7,
1216 26, 8, 1, 8, 3, 1, 26, 3, 11, 11, 27, 27, 2, 28, 1, 2,
1217 28, 1, 12, 12, 5, 5, 29, 13, 13, 29, 32, 1, 1, 33, 31, 30,
1218 32, 4, 30, 33, 4, 31, 3, 14, 1, 1, 3, 34, 34, 2, 2, 14,
1219 6, 6, 35, 36, 35, 36, 1, 15, 1, 16, 16, 15, 7, 9, 7, 9,
1220 37, 8, 8, 37, 1, 1, 39, 2, 38, 39, 2, 40, 5, 38, 40, 5,
1221 3, 3, 4, 4, 10, 10, 1, 1, 1, 1, 41, 2, 41, 2, 6, 6,
1222 1, 1, 11, 42, 11, 43, 3, 42, 3, 17, 4, 43, 1, 17, 7, 1,
1223 8, 44, 4, 7, 44, 5, 8, 2, 5, 1, 2, 48, 45, 1, 12, 45,
1224 12, 48, 13, 13, 1, 9, 9, 46, 1, 46, 47, 47, 49, 18, 18, 49},
1227 { 1, -1, 0, 1, -1, 2, -2, 1, -1, 1, -1, 1, -1, 3, -3, 1,
1228 -1, -2, 2, 1, -1, 1, -1, 4, -4, -2, 2, 1, -1, 1, -1, 5,
1229 -5, -3, 3, 2, -2, 1, 0, -1, 1, -1, 1, -1, 6, -6, 2, -2,
1230 1, -1, 1, 1, -1, -1, -3, 3, 7, 2, -7, -2, -4, 4, 2, -2,
1231 2, -2, 1, -1, 8, -8, 3, -3, 1, -1, -5, 5, 9, 1, -9, 1,
1232 -1, -1, 1, -1, -4, 4, 1, -1, 3, -3, 1, -10, 10, 1, 2, -1,
1233 -1, -2, 6, -6, 2, 11, -11, -2, 3, -3, 1, -4, 4, -1, 3, -3,
1234 1, 3, 12, -3, -5, -12, -1, 5, 2, -2, 1, -1, -7, 1, 13, 7,
1235 -1, -13, 2, -2, 4, -4, 1, 2, -2, -1, 1, 14, -14, 1, 1, 1,
1236 -1, -5, -1, -1, 5, -1, -6, 2, -15, 15, 6, 1, -1, -8, 8, -2,
1237 -4, 4, 1, 1, -1, -1, 16, 2, -16, -2, 2, -2, 4, 3, -4, -3,
1238 -1, -4, 4, 1, -17, 17, -1, -9, 1, 1, 9, 1, -5, -1, -1, 5,
1239 -7, 7, 6, -6, 3, -3, 18, -18, 19, -19, 1, -10, -1, 10, -5, 5,
1240 20, -20, -3, 1, 3, 1, 8, -1, -8, 2, 7, -1, -21, -2, 5, 21,
1241 5, -1, -7, -5, 1, -6, -5, -11, 6, 22, 11, 1, 1, -22, -3, -1,
1242 3, -1, 3, -3, -23, 4, -4, 1, 23, -1, 1, -1, 1, -2, 2, -1}
1248 {1, 1, 1, 1, 0, 2, 2, 1, 1, 3, 3, 0, 1, 1, 2, 2,
1249 4, 4, 1, 1, 5, 5, 1, 1, 2, 2, 3, 3, 6, 6, 1, 1,
1250 7, 7, 8, 1, 8, 2, 2, 1, 4, 4, 1, 3, 1, 3, 9, 9,
1251 2, 2, 1, 5, 1, 5, 10, 10, 1, 1, 11, 11, 3, 6, 3, 4,
1252 4, 6, 2, 2, 1, 12, 1, 12, 7, 13, 7, 13, 1, 1, 8, 8,
1253 2, 2, 14, 14, 16, 15, 16, 5, 5, 1, 3, 15, 1, 3, 4, 4,
1254 1, 1, 17, 17, 2, 2, 6, 6, 1, 18, 1, 18, 22, 21, 22, 21,
1255 25, 24, 25, 19, 9, 20, 9, 23, 19, 24, 20, 3, 23, 7, 3, 1,
1256 1, 7, 28, 26, 29, 5, 28, 26, 5, 8, 29, 4, 8, 27, 2, 2,
1257 4, 27, 1, 1, 10, 36, 10, 33, 33, 36, 30, 1, 32, 32, 1, 30,
1258 6, 31, 31, 35, 3, 6, 11, 11, 3, 2, 35, 2, 34, 1, 34, 1,
1259 37, 37, 12, 7, 12, 5, 41, 5, 4, 7, 1, 8, 13, 4, 1, 41,
1260 13, 38, 8, 38, 9, 1, 40, 40, 9, 1, 39, 2, 2, 49, 39, 42,
1261 3, 3, 14, 16, 49, 14, 16, 42, 43, 43, 6, 6, 15, 1, 1, 15,
1262 44, 44, 1, 1, 50, 48, 4, 5, 4, 7, 5, 2, 10, 10, 48, 7,
1263 50, 45, 2, 1, 45, 8, 8, 1, 46, 46, 3, 47, 47, 3, 1, 1},
1266 { 1, -1, 2, -2, 0, 1, -1, 3, -3, 1, -1, 0, 4, -4, 2, -2,
1267 1, -1, 5, -5, 1, -1, 6, -6, 3, -3, 2, -2, 1, -1, 7, -7,
1268 1, -1, 1, 8, -1, 4, -4, -8, 2, -2, 9, 3, -9, -3, 1, -1,
1269 5, -5, 10, 2, -10, -2, 1, -1, 11, -11, 1, -1, -4, 2, 4, 3,
1270 -3, -2, 6, -6, 12, 1, -12, -1, 2, 1, -2, -1, 13, -13, 2, -2,
1271 7, -7, 1, -1, 1, 1, -1, 3, -3, 14, 5, -1, -14, -5, 4, -4,
1272 15, -15, 1, -1, 8, -8, -3, 3, 16, 1, -16, -1, 1, 1, -1, -1,
1273 1, 1, -1, 1, 2, 1, -2, 1, -1, -1, -1, 6, -1, 3, -6, 17,
1274 -17, -3, 1, 1, 1, 4, -1, -1, -4, 3, -1, 5, -3, -1, -9, 9,
1275 -5, 1, 18, -18, 2, 1, -2, 1, -1, -1, 1, 19, -1, 1, -19, -1,
1276 4, 1, -1, 1, 7, -4, -2, 2, -7, 10, -1, -10, 1, 20, -1, -20,
1277 1, -1, 2, 4, -2, 5, 1, -5, 6, -4, 21, 4, 2, -6, -21, -1,
1278 -2, 1, -4, -1, -3, 22, -1, 1, 3, -22, -1, 11, -11, 1, 1, 1,
1279 8, -8, 2, 2, -1, -2, -2, -1, 1, -1, -5, 5, 2, 23, -23, -2,
1280 1, -1, 24, -24, -1, -1, 7, 6, -7, 5, -6, 12, -3, 3, 1, -5,
1281 1, 1, -12, 25, -1, -5, 5, -25, -1, 1, 9, 1, -1, -9, 26, -26}