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
30 #include "libavutil/attributes.h"
34 #include "ivi_common.h"
37 extern const IVIHuffDesc ff_ivi_mb_huff_desc[8]; ///< static macroblock huffman tables
38 extern const IVIHuffDesc ff_ivi_blk_huff_desc[8]; ///< static block huffman tables
40 VLC ff_ivi_mb_vlc_tabs [8];
41 VLC ff_ivi_blk_vlc_tabs[8];
44 * Reverse "nbits" bits of the value "val" and return the result
45 * in the least significant bits.
47 static uint16_t inv_bits(uint16_t val, int nbits)
52 res = ff_reverse[val] >> (8-nbits);
54 res = ((ff_reverse[val & 0xFF] << 8) + (ff_reverse[val >> 8])) >> (16-nbits);
59 int ff_ivi_create_huff_from_desc(const IVIHuffDesc *cb, VLC *vlc, int flag)
61 int pos, i, j, codes_per_row, prefix, not_last_row;
62 uint16_t codewords[256]; /* FIXME: move this temporal storage out? */
65 pos = 0; /* current position = 0 */
67 for (i = 0; i < cb->num_rows; i++) {
68 codes_per_row = 1 << cb->xbits[i];
69 not_last_row = (i != cb->num_rows - 1);
70 prefix = ((1 << i) - 1) << (cb->xbits[i] + not_last_row);
72 for (j = 0; j < codes_per_row; j++) {
73 if (pos >= 256) /* Some Indeo5 codebooks can have more than 256 */
74 break; /* elements, but only 256 codes are allowed! */
76 bits[pos] = i + cb->xbits[i] + not_last_row;
77 if (bits[pos] > IVI_VLC_BITS)
78 return -1; /* invalid descriptor */
80 codewords[pos] = inv_bits((prefix | j), bits[pos]);
88 /* number of codewords = pos */
89 return init_vlc(vlc, IVI_VLC_BITS, pos, bits, 1, 1, codewords, 2, 2,
90 (flag ? INIT_VLC_USE_NEW_STATIC : 0) | INIT_VLC_LE);
93 void ff_ivi_init_static_vlc(void)
96 static VLC_TYPE table_data[8192 * 16][2];
97 static int initialized_vlcs = 0;
101 for (i = 0; i < 8; i++) {
102 ff_ivi_mb_vlc_tabs[i].table = table_data + i * 2 * 8192;
103 ff_ivi_mb_vlc_tabs[i].table_allocated = 8192;
104 ff_ivi_create_huff_from_desc(&ff_ivi_mb_huff_desc[i], &ff_ivi_mb_vlc_tabs[i], 1);
105 ff_ivi_blk_vlc_tabs[i].table = table_data + (i * 2 + 1) * 8192;
106 ff_ivi_blk_vlc_tabs[i].table_allocated = 8192;
107 ff_ivi_create_huff_from_desc(&ff_ivi_blk_huff_desc[i], &ff_ivi_blk_vlc_tabs[i], 1);
109 initialized_vlcs = 1;
112 int ff_ivi_dec_huff_desc(GetBitContext *gb, int desc_coded, int which_tab,
113 IVIHuffTab *huff_tab, AVCodecContext *avctx)
116 IVIHuffDesc new_huff;
119 /* select default table */
120 huff_tab->tab = (which_tab) ? &ff_ivi_blk_vlc_tabs[7]
121 : &ff_ivi_mb_vlc_tabs [7];
123 huff_tab->tab_sel = get_bits(gb, 3);
124 if (huff_tab->tab_sel == 7) {
125 /* custom huffman table (explicitly encoded) */
126 new_huff.num_rows = get_bits(gb, 4);
127 if (!new_huff.num_rows) {
128 av_log(avctx, AV_LOG_ERROR, "Empty custom Huffman table!\n");
129 return AVERROR_INVALIDDATA;
132 for (i = 0; i < new_huff.num_rows; i++)
133 new_huff.xbits[i] = get_bits(gb, 4);
135 /* Have we got the same custom table? Rebuild if not. */
136 if (ff_ivi_huff_desc_cmp(&new_huff, &huff_tab->cust_desc) || !huff_tab->cust_tab.table) {
137 ff_ivi_huff_desc_copy(&huff_tab->cust_desc, &new_huff);
139 if (huff_tab->cust_tab.table)
140 ff_free_vlc(&huff_tab->cust_tab);
141 result = ff_ivi_create_huff_from_desc(&huff_tab->cust_desc,
142 &huff_tab->cust_tab, 0);
144 huff_tab->cust_desc.num_rows = 0; // reset faulty description
145 av_log(avctx, AV_LOG_ERROR,
146 "Error while initializing custom vlc table!\n");
150 huff_tab->tab = &huff_tab->cust_tab;
152 /* select one of predefined tables */
153 huff_tab->tab = (which_tab) ? &ff_ivi_blk_vlc_tabs[huff_tab->tab_sel]
154 : &ff_ivi_mb_vlc_tabs [huff_tab->tab_sel];
161 int ff_ivi_huff_desc_cmp(const IVIHuffDesc *desc1, const IVIHuffDesc *desc2)
163 return desc1->num_rows != desc2->num_rows
164 || memcmp(desc1->xbits, desc2->xbits, desc1->num_rows);
167 void ff_ivi_huff_desc_copy(IVIHuffDesc *dst, const IVIHuffDesc *src)
169 dst->num_rows = src->num_rows;
170 memcpy(dst->xbits, src->xbits, src->num_rows);
173 av_cold int ff_ivi_init_planes(IVIPlaneDesc *planes, const IVIPicConfig *cfg)
176 uint32_t b_width, b_height, align_fac, width_aligned, height_aligned, buf_size;
179 ff_ivi_free_buffers(planes);
181 /* fill in the descriptor of the luminance plane */
182 planes[0].width = cfg->pic_width;
183 planes[0].height = cfg->pic_height;
184 planes[0].num_bands = cfg->luma_bands;
186 /* fill in the descriptors of the chrominance planes */
187 planes[1].width = planes[2].width = (cfg->pic_width + 3) >> 2;
188 planes[1].height = planes[2].height = (cfg->pic_height + 3) >> 2;
189 planes[1].num_bands = planes[2].num_bands = cfg->chroma_bands;
191 for (p = 0; p < 3; p++) {
192 planes[p].bands = av_mallocz(planes[p].num_bands * sizeof(IVIBandDesc));
193 if (!planes[p].bands)
194 return AVERROR(ENOMEM);
196 /* select band dimensions: if there is only one band then it
197 * has the full size, if there are several bands each of them
198 * has only half size */
199 b_width = planes[p].num_bands == 1 ? planes[p].width : (planes[p].width + 1) >> 1;
200 b_height = planes[p].num_bands == 1 ? planes[p].height : (planes[p].height + 1) >> 1;
202 /* luma band buffers will be aligned on 16x16 (max macroblock size) */
203 /* chroma band buffers will be aligned on 8x8 (max macroblock size) */
204 align_fac = p ? 8 : 16;
205 width_aligned = FFALIGN(b_width , align_fac);
206 height_aligned = FFALIGN(b_height, align_fac);
207 buf_size = width_aligned * height_aligned * sizeof(int16_t);
209 for (b = 0; b < planes[p].num_bands; b++) {
210 band = &planes[p].bands[b]; /* select appropriate plane/band */
213 band->width = b_width;
214 band->height = b_height;
215 band->pitch = width_aligned;
216 band->aheight = height_aligned;
217 band->bufs[0] = av_mallocz(buf_size);
218 band->bufs[1] = av_mallocz(buf_size);
219 band->bufsize = buf_size/2;
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) {
271 if(t_width<=0 || t_height<=0)
272 return AVERROR(EINVAL);
274 for (b = 0; b < planes[p].num_bands; b++) {
275 band = &planes[p].bands[b];
276 x_tiles = IVI_NUM_TILES(band->width, t_width);
277 y_tiles = IVI_NUM_TILES(band->height, t_height);
278 band->num_tiles = x_tiles * y_tiles;
280 av_freep(&band->tiles);
281 band->tiles = av_mallocz(band->num_tiles * sizeof(IVITile));
283 return AVERROR(ENOMEM);
287 /* use the first luma band as reference for motion vectors
289 ref_tile = planes[0].bands[0].tiles;
291 for (y = 0; y < band->height; y += t_height) {
292 for (x = 0; x < band->width; x += t_width) {
295 tile->mb_size = band->mb_size;
296 tile->width = FFMIN(band->width - x, t_width);
297 tile->height = FFMIN(band->height - y, t_height);
298 tile->is_empty = tile->data_size = 0;
299 /* calculate number of macroblocks */
300 tile->num_MBs = IVI_MBs_PER_TILE(tile->width, tile->height,
303 av_freep(&tile->mbs);
304 tile->mbs = av_malloc(tile->num_MBs * sizeof(IVIMbInfo));
306 return AVERROR(ENOMEM);
310 tile->ref_mbs = ref_tile->mbs;
324 int ff_ivi_dec_tile_data_size(GetBitContext *gb)
330 len = get_bits(gb, 8);
332 len = get_bits_long(gb, 24);
335 /* align the bitstream reader on the byte boundary */
341 int ff_ivi_decode_blocks(GetBitContext *gb, IVIBandDesc *band, IVITile *tile)
343 int mbn, blk, num_blocks, num_coeffs, blk_size, scan_pos, run, val,
344 pos, is_intra, mc_type = 0, mv_x, mv_y, col_mask;
345 uint8_t col_flags[8];
346 int32_t prev_dc, trvec[64];
347 uint32_t cbp, sym, lo, hi, quant, buf_offs, q;
349 RVMapDesc *rvmap = band->rv_map;
350 void (*mc_with_delta_func)(int16_t *buf, const int16_t *ref_buf, uint32_t pitch, int mc_type);
351 void (*mc_no_delta_func) (int16_t *buf, const int16_t *ref_buf, uint32_t pitch, int mc_type);
352 const uint16_t *base_tab;
353 const uint8_t *scale_tab;
355 prev_dc = 0; /* init intra prediction for the DC coefficient */
357 blk_size = band->blk_size;
358 col_mask = blk_size - 1; /* column mask for tracking non-zero coeffs */
359 num_blocks = (band->mb_size != blk_size) ? 4 : 1; /* number of blocks per mb */
360 num_coeffs = blk_size * blk_size;
362 mc_with_delta_func = ff_ivi_mc_8x8_delta;
363 mc_no_delta_func = ff_ivi_mc_8x8_no_delta;
365 mc_with_delta_func = ff_ivi_mc_4x4_delta;
366 mc_no_delta_func = ff_ivi_mc_4x4_no_delta;
369 for (mbn = 0, mb = tile->mbs; mbn < tile->num_MBs; mb++, mbn++) {
370 is_intra = !mb->type;
372 buf_offs = mb->buf_offs;
374 quant = av_clip(band->glob_quant + mb->q_delta, 0, 23);
376 base_tab = is_intra ? band->intra_base : band->inter_base;
377 scale_tab = is_intra ? band->intra_scale : band->inter_scale;
379 quant = scale_tab[quant];
384 if (band->is_halfpel) {
385 mc_type = ((mv_y & 1) << 1) | (mv_x & 1);
387 mv_y >>= 1; /* convert halfpel vectors into fullpel ones */
390 int dmv_x, dmv_y, cx, cy;
392 dmv_x = mb->mv_x >> band->is_halfpel;
393 dmv_y = mb->mv_y >> band->is_halfpel;
394 cx = mb->mv_x & band->is_halfpel;
395 cy = mb->mv_y & band->is_halfpel;
397 if ( mb->xpos + dmv_x < 0
398 || mb->xpos + dmv_x + band->mb_size + cx > band->pitch
399 || mb->ypos + dmv_y < 0
400 || mb->ypos + dmv_y + band->mb_size + cy > band->aheight) {
401 return AVERROR_INVALIDDATA;
406 for (blk = 0; blk < num_blocks; blk++) {
407 /* adjust block position in the buffer according to its number */
409 buf_offs += blk_size;
410 } else if (blk == 2) {
411 buf_offs -= blk_size;
412 buf_offs += blk_size * band->pitch;
415 if (cbp & 1) { /* block coded ? */
417 memset(trvec, 0, num_coeffs*sizeof(trvec[0])); /* zero transform vector */
418 memset(col_flags, 0, sizeof(col_flags)); /* zero column flags */
420 while (scan_pos <= num_coeffs) {
421 sym = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
422 if (sym == rvmap->eob_sym)
423 break; /* End of block */
425 if (sym == rvmap->esc_sym) { /* Escape - run/val explicitly coded using 3 vlc codes */
426 run = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1) + 1;
427 lo = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
428 hi = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
429 val = IVI_TOSIGNED((hi << 6) | lo); /* merge them and convert into signed val */
432 av_log(NULL, AV_LOG_ERROR, "Invalid sym encountered: %d.\n", sym);
435 run = rvmap->runtab[sym];
436 val = rvmap->valtab[sym];
439 /* de-zigzag and dequantize */
441 if (scan_pos >= (unsigned)num_coeffs)
443 pos = band->scan[scan_pos];
446 av_dlog(NULL, "Val = 0 encountered!\n");
448 q = (base_tab[pos] * quant) >> 9;
450 val = val * q + FFSIGN(val) * (((q ^ 1) - 1) >> 1);
452 col_flags[pos & col_mask] |= !!val; /* track columns containing non-zero coeffs */
455 if (scan_pos >= num_coeffs && sym != rvmap->eob_sym)
456 return -1; /* corrupt block data */
458 /* undoing DC coeff prediction for intra-blocks */
459 if (is_intra && band->is_2d_trans) {
462 col_flags[0] |= !!prev_dc;
464 if(band->transform_size > band->blk_size){
465 av_log(0, AV_LOG_ERROR, "Too large transform\n");
466 return AVERROR_INVALIDDATA;
468 /* apply inverse transform */
469 band->inv_transform(trvec, band->buf + buf_offs,
470 band->pitch, col_flags);
472 /* apply motion compensation */
474 mc_with_delta_func(band->buf + buf_offs,
475 band->ref_buf + buf_offs + mv_y * band->pitch + mv_x,
476 band->pitch, mc_type);
478 /* block not coded */
479 /* for intra blocks apply the dc slant transform */
480 /* for inter - perform the motion compensation without delta */
481 if (is_intra && band->dc_transform) {
482 band->dc_transform(&prev_dc, band->buf + buf_offs,
483 band->pitch, blk_size);
485 mc_no_delta_func(band->buf + buf_offs,
486 band->ref_buf + buf_offs + mv_y * band->pitch + mv_x,
487 band->pitch, mc_type);
500 * Handle empty tiles by performing data copying and motion
501 * compensation respectively.
503 * @param[in] avctx ptr to the AVCodecContext
504 * @param[in] band pointer to the band descriptor
505 * @param[in] tile pointer to the tile descriptor
506 * @param[in] mv_scale scaling factor for motion vectors
508 static int ivi_process_empty_tile(AVCodecContext *avctx, IVIBandDesc *band,
509 IVITile *tile, int32_t mv_scale)
511 int x, y, need_mc, mbn, blk, num_blocks, mv_x, mv_y, mc_type;
512 int offs, mb_offset, row_offset;
513 IVIMbInfo *mb, *ref_mb;
516 void (*mc_no_delta_func)(int16_t *buf, const int16_t *ref_buf, uint32_t pitch,
519 if (tile->num_MBs != IVI_MBs_PER_TILE(tile->width, tile->height, band->mb_size)) {
520 av_log(avctx, AV_LOG_ERROR, "Allocated tile size %d mismatches "
521 "parameters %d in ivi_process_empty_tile()\n",
522 tile->num_MBs, IVI_MBs_PER_TILE(tile->width, tile->height, band->mb_size));
523 return AVERROR_INVALIDDATA;
526 offs = tile->ypos * band->pitch + tile->xpos;
528 ref_mb = tile->ref_mbs;
529 row_offset = band->mb_size * band->pitch;
530 need_mc = 0; /* reset the mc tracking flag */
532 for (y = tile->ypos; y < (tile->ypos + tile->height); y += band->mb_size) {
535 for (x = tile->xpos; x < (tile->xpos + tile->width); x += band->mb_size) {
538 mb->buf_offs = mb_offset;
540 mb->type = 1; /* set the macroblocks type = INTER */
541 mb->cbp = 0; /* all blocks are empty */
543 if (!band->qdelta_present && !band->plane && !band->band_num) {
544 mb->q_delta = band->glob_quant;
549 if (band->inherit_qdelta && ref_mb)
550 mb->q_delta = ref_mb->q_delta;
552 if (band->inherit_mv && ref_mb) {
553 /* motion vector inheritance */
555 mb->mv_x = ivi_scale_mv(ref_mb->mv_x, mv_scale);
556 mb->mv_y = ivi_scale_mv(ref_mb->mv_y, mv_scale);
558 mb->mv_x = ref_mb->mv_x;
559 mb->mv_y = ref_mb->mv_y;
561 need_mc |= mb->mv_x || mb->mv_y; /* tracking non-zero motion vectors */
567 mb_offset += band->mb_size;
572 if (band->inherit_mv && need_mc) { /* apply motion compensation if there is at least one non-zero motion vector */
573 num_blocks = (band->mb_size != band->blk_size) ? 4 : 1; /* number of blocks per mb */
574 mc_no_delta_func = (band->blk_size == 8) ? ff_ivi_mc_8x8_no_delta
575 : ff_ivi_mc_4x4_no_delta;
577 for (mbn = 0, mb = tile->mbs; mbn < tile->num_MBs; mb++, mbn++) {
580 if (!band->is_halfpel) {
581 mc_type = 0; /* we have only fullpel vectors */
583 mc_type = ((mv_y & 1) << 1) | (mv_x & 1);
585 mv_y >>= 1; /* convert halfpel vectors into fullpel ones */
588 for (blk = 0; blk < num_blocks; blk++) {
589 /* adjust block position in the buffer according with its number */
590 offs = mb->buf_offs + band->blk_size * ((blk & 1) + !!(blk & 2) * band->pitch);
591 mc_no_delta_func(band->buf + offs,
592 band->ref_buf + offs + mv_y * band->pitch + mv_x,
593 band->pitch, mc_type);
597 /* copy data from the reference tile into the current one */
598 src = band->ref_buf + tile->ypos * band->pitch + tile->xpos;
599 dst = band->buf + tile->ypos * band->pitch + tile->xpos;
600 for (y = 0; y < tile->height; y++) {
601 memcpy(dst, src, tile->width*sizeof(band->buf[0]));
612 static uint16_t ivi_calc_band_checksum(IVIBandDesc *band)
615 int16_t *src, checksum;
620 for (y = 0; y < band->height; src += band->pitch, y++)
621 for (x = 0; x < band->width; x++)
628 void ff_ivi_output_plane(IVIPlaneDesc *plane, uint8_t *dst, int dst_pitch)
631 const int16_t *src = plane->bands[0].buf;
632 uint32_t pitch = plane->bands[0].pitch;
637 for (y = 0; y < plane->height; y++) {
638 for (x = 0; x < plane->width; x++)
639 dst[x] = av_clip_uint8(src[x] + 128);
646 * Decode an Indeo 4 or 5 band.
648 * @param[in,out] ctx ptr to the decoder context
649 * @param[in,out] band ptr to the band descriptor
650 * @param[in] avctx ptr to the AVCodecContext
651 * @return result code: 0 = OK, -1 = error
653 static int decode_band(IVI45DecContext *ctx,
654 IVIBandDesc *band, AVCodecContext *avctx)
656 int result, i, t, idx1, idx2, pos;
659 band->buf = band->bufs[ctx->dst_buf];
661 av_log(avctx, AV_LOG_ERROR, "Band buffer points to no data!\n");
662 return AVERROR_INVALIDDATA;
664 band->ref_buf = band->bufs[ctx->ref_buf];
665 band->data_ptr = ctx->frame_data + (get_bits_count(&ctx->gb) >> 3);
667 result = ctx->decode_band_hdr(ctx, band, avctx);
669 av_log(avctx, AV_LOG_ERROR, "Error while decoding band header: %d\n",
674 if (band->is_empty) {
675 av_log(avctx, AV_LOG_ERROR, "Empty band encountered!\n");
676 return AVERROR_INVALIDDATA;
679 band->rv_map = &ctx->rvmap_tabs[band->rvmap_sel];
681 /* apply corrections to the selected rvmap table if present */
682 for (i = 0; i < band->num_corr; i++) {
683 idx1 = band->corr[i * 2];
684 idx2 = band->corr[i * 2 + 1];
685 FFSWAP(uint8_t, band->rv_map->runtab[idx1], band->rv_map->runtab[idx2]);
686 FFSWAP(int16_t, band->rv_map->valtab[idx1], band->rv_map->valtab[idx2]);
687 if (idx1 == band->rv_map->eob_sym || idx2 == band->rv_map->eob_sym)
688 band->rv_map->eob_sym ^= idx1 ^ idx2;
689 if (idx1 == band->rv_map->esc_sym || idx2 == band->rv_map->esc_sym)
690 band->rv_map->esc_sym ^= idx1 ^ idx2;
693 pos = get_bits_count(&ctx->gb);
695 for (t = 0; t < band->num_tiles; t++) {
696 tile = &band->tiles[t];
698 if (tile->mb_size != band->mb_size) {
699 av_log(avctx, AV_LOG_ERROR, "MB sizes mismatch: %d vs. %d\n",
700 band->mb_size, tile->mb_size);
701 return AVERROR_INVALIDDATA;
703 tile->is_empty = get_bits1(&ctx->gb);
704 if (tile->is_empty) {
705 result = ivi_process_empty_tile(avctx, band, tile,
706 (ctx->planes[0].bands[0].mb_size >> 3) - (band->mb_size >> 3));
709 av_dlog(avctx, "Empty tile encountered!\n");
711 tile->data_size = ff_ivi_dec_tile_data_size(&ctx->gb);
712 if (!tile->data_size) {
713 av_log(avctx, AV_LOG_ERROR, "Tile data size is zero!\n");
714 result = AVERROR_INVALIDDATA;
718 result = ctx->decode_mb_info(ctx, band, tile, avctx);
722 result = ff_ivi_decode_blocks(&ctx->gb, band, tile);
723 if (result < 0 || ((get_bits_count(&ctx->gb) - pos) >> 3) != tile->data_size) {
724 av_log(avctx, AV_LOG_ERROR, "Corrupted tile data encountered!\n");
728 pos += tile->data_size << 3; // skip to next tile
732 /* restore the selected rvmap table by applying its corrections in reverse order */
733 for (i = band->num_corr-1; i >= 0; i--) {
734 idx1 = band->corr[i*2];
735 idx2 = band->corr[i*2+1];
736 FFSWAP(uint8_t, band->rv_map->runtab[idx1], band->rv_map->runtab[idx2]);
737 FFSWAP(int16_t, band->rv_map->valtab[idx1], band->rv_map->valtab[idx2]);
738 if (idx1 == band->rv_map->eob_sym || idx2 == band->rv_map->eob_sym)
739 band->rv_map->eob_sym ^= idx1 ^ idx2;
740 if (idx1 == band->rv_map->esc_sym || idx2 == band->rv_map->esc_sym)
741 band->rv_map->esc_sym ^= idx1 ^ idx2;
745 if (band->checksum_present) {
746 uint16_t chksum = ivi_calc_band_checksum(band);
747 if (chksum != band->checksum) {
748 av_log(avctx, AV_LOG_ERROR,
749 "Band checksum mismatch! Plane %d, band %d, received: %x, calculated: %x\n",
750 band->plane, band->band_num, band->checksum, chksum);
755 align_get_bits(&ctx->gb);
760 int ff_ivi_decode_frame(AVCodecContext *avctx, void *data, int *data_size,
763 IVI45DecContext *ctx = avctx->priv_data;
764 const uint8_t *buf = avpkt->data;
765 int buf_size = avpkt->size;
768 init_get_bits(&ctx->gb, buf, buf_size * 8);
769 ctx->frame_data = buf;
770 ctx->frame_size = buf_size;
772 result = ctx->decode_pic_hdr(ctx, avctx);
774 av_log(avctx, AV_LOG_ERROR,
775 "Error while decoding picture header: %d\n", result);
778 if (ctx->gop_invalid)
779 return AVERROR_INVALIDDATA;
781 if (ctx->gop_flags & IVI5_IS_PROTECTED) {
782 av_log(avctx, AV_LOG_ERROR, "Password-protected clip!\n");
786 ctx->switch_buffers(ctx);
790 if (ctx->is_nonnull_frame(ctx)) {
791 ctx->buf_invalid[ctx->dst_buf] = 1;
792 for (p = 0; p < 3; p++) {
793 for (b = 0; b < ctx->planes[p].num_bands; b++) {
794 result = decode_band(ctx, &ctx->planes[p].bands[b], avctx);
796 av_log(avctx, AV_LOG_ERROR,
797 "Error while decoding band: %d, plane: %d\n", b, p);
802 ctx->buf_invalid[ctx->dst_buf] = 0;
804 if (ctx->buf_invalid[ctx->dst_buf])
807 //STOP_TIMER("decode_planes"); }
809 /* If the bidirectional mode is enabled, next I and the following P frame will */
810 /* be sent together. Unfortunately the approach below seems to be the only way */
811 /* to handle the B-frames mode. That's exactly the same Intel decoders do. */
812 if (avctx->codec_id == AV_CODEC_ID_INDEO4 && ctx->frame_type == 0/*FRAMETYPE_INTRA*/) {
813 while (get_bits(&ctx->gb, 8)); // skip version string
814 skip_bits_long(&ctx->gb, 64); // skip padding, TODO: implement correct 8-bytes alignment
815 if (get_bits_left(&ctx->gb) > 18 && show_bits(&ctx->gb, 18) == 0x3FFF8)
816 av_log(avctx, AV_LOG_ERROR, "Buffer contains IP frames!\n");
819 if (!ctx->is_nonnull_frame(ctx))
822 if (ctx->frame.data[0])
823 avctx->release_buffer(avctx, &ctx->frame);
825 ctx->frame.reference = 0;
826 avcodec_set_dimensions(avctx, ctx->planes[0].width, ctx->planes[0].height);
827 if ((result = avctx->get_buffer(avctx, &ctx->frame)) < 0) {
828 av_log(avctx, AV_LOG_ERROR, "get_buffer() failed\n");
832 if (ctx->is_scalable) {
833 if (avctx->codec_id == AV_CODEC_ID_INDEO4)
834 ff_ivi_recompose_haar(&ctx->planes[0], ctx->frame.data[0], ctx->frame.linesize[0]);
836 ff_ivi_recompose53 (&ctx->planes[0], ctx->frame.data[0], ctx->frame.linesize[0]);
838 ff_ivi_output_plane(&ctx->planes[0], ctx->frame.data[0], ctx->frame.linesize[0]);
841 ff_ivi_output_plane(&ctx->planes[2], ctx->frame.data[1], ctx->frame.linesize[1]);
842 ff_ivi_output_plane(&ctx->planes[1], ctx->frame.data[2], ctx->frame.linesize[2]);
844 *data_size = sizeof(AVFrame);
845 *(AVFrame*)data = ctx->frame;
851 * Close Indeo5 decoder and clean up its context.
853 av_cold int ff_ivi_decode_close(AVCodecContext *avctx)
855 IVI45DecContext *ctx = avctx->priv_data;
857 ff_ivi_free_buffers(&ctx->planes[0]);
859 if (ctx->mb_vlc.cust_tab.table)
860 ff_free_vlc(&ctx->mb_vlc.cust_tab);
862 if (ctx->frame.data[0])
863 avctx->release_buffer(avctx, &ctx->frame);
865 #if IVI4_STREAM_ANALYSER
866 if (avctx->codec_id == AV_CODEC_ID_INDEO4) {
867 if (ctx->is_scalable)
868 av_log(avctx, AV_LOG_ERROR, "This video uses scalability mode!\n");
869 if (ctx->uses_tiling)
870 av_log(avctx, AV_LOG_ERROR, "This video uses local decoding!\n");
871 if (ctx->has_b_frames)
872 av_log(avctx, AV_LOG_ERROR, "This video contains B-frames!\n");
874 av_log(avctx, AV_LOG_ERROR, "Transparency mode is enabled!\n");
876 av_log(avctx, AV_LOG_ERROR, "This video uses Haar transform!\n");
877 if (ctx->uses_fullpel)
878 av_log(avctx, AV_LOG_ERROR, "This video uses fullpel motion vectors!\n");
887 * These are 2x8 predefined Huffman codebooks for coding macroblock/block
888 * signals. They are specified using "huffman descriptors" in order to
889 * avoid huge static tables. The decoding tables will be generated at
890 * startup from these descriptors.
892 const IVIHuffDesc ff_ivi_mb_huff_desc[8] = {
893 {8, {0, 4, 5, 4, 4, 4, 6, 6}},
894 {12, {0, 2, 2, 3, 3, 3, 3, 5, 3, 2, 2, 2}},
895 {12, {0, 2, 3, 4, 3, 3, 3, 3, 4, 3, 2, 2}},
896 {12, {0, 3, 4, 4, 3, 3, 3, 3, 3, 2, 2, 2}},
897 {13, {0, 4, 4, 3, 3, 3, 3, 2, 3, 3, 2, 1, 1}},
898 {9, {0, 4, 4, 4, 4, 3, 3, 3, 2}},
899 {10, {0, 4, 4, 4, 4, 3, 3, 2, 2, 2}},
900 {12, {0, 4, 4, 4, 3, 3, 2, 3, 2, 2, 2, 2}}
903 const IVIHuffDesc ff_ivi_blk_huff_desc[8] = {
904 {10, {1, 2, 3, 4, 4, 7, 5, 5, 4, 1}},
905 {11, {2, 3, 4, 4, 4, 7, 5, 4, 3, 3, 2}},
906 {12, {2, 4, 5, 5, 5, 5, 6, 4, 4, 3, 1, 1}},
907 {13, {3, 3, 4, 4, 5, 6, 6, 4, 4, 3, 2, 1, 1}},
908 {11, {3, 4, 4, 5, 5, 5, 6, 5, 4, 2, 2}},
909 {13, {3, 4, 5, 5, 5, 5, 6, 4, 3, 3, 2, 1, 1}},
910 {13, {3, 4, 5, 5, 5, 6, 5, 4, 3, 3, 2, 1, 1}},
911 {9, {3, 4, 4, 5, 5, 5, 6, 5, 5}}
916 * Scan patterns shared between indeo4 and indeo5
918 const uint8_t ff_ivi_vertical_scan_8x8[64] = {
919 0, 8, 16, 24, 32, 40, 48, 56,
920 1, 9, 17, 25, 33, 41, 49, 57,
921 2, 10, 18, 26, 34, 42, 50, 58,
922 3, 11, 19, 27, 35, 43, 51, 59,
923 4, 12, 20, 28, 36, 44, 52, 60,
924 5, 13, 21, 29, 37, 45, 53, 61,
925 6, 14, 22, 30, 38, 46, 54, 62,
926 7, 15, 23, 31, 39, 47, 55, 63
929 const uint8_t ff_ivi_horizontal_scan_8x8[64] = {
930 0, 1, 2, 3, 4, 5, 6, 7,
931 8, 9, 10, 11, 12, 13, 14, 15,
932 16, 17, 18, 19, 20, 21, 22, 23,
933 24, 25, 26, 27, 28, 29, 30, 31,
934 32, 33, 34, 35, 36, 37, 38, 39,
935 40, 41, 42, 43, 44, 45, 46, 47,
936 48, 49, 50, 51, 52, 53, 54, 55,
937 56, 57, 58, 59, 60, 61, 62, 63
940 const uint8_t ff_ivi_direct_scan_4x4[16] = {
941 0, 1, 4, 8, 5, 2, 3, 6, 9, 12, 13, 10, 7, 11, 14, 15
946 * Run-value (RLE) tables.
948 const RVMapDesc ff_ivi_rvmap_tabs[9] = {
953 {1, 1, 0, 1, 1, 0, 1, 1, 2, 2, 1, 1, 1, 1, 3, 3,
954 1, 1, 2, 2, 1, 1, 4, 4, 1, 1, 1, 1, 2, 2, 5, 5,
955 1, 1, 3, 3, 1, 1, 6, 6, 1, 2, 1, 2, 7, 7, 1, 1,
956 8, 8, 1, 1, 4, 2, 1, 4, 2, 1, 3, 3, 1, 1, 1, 9,
957 9, 1, 2, 1, 2, 1, 5, 5, 1, 1, 10, 10, 1, 1, 3, 3,
958 2, 2, 1, 1, 11, 11, 6, 4, 4, 1, 6, 1, 2, 1, 2, 12,
959 8, 1, 12, 7, 8, 7, 1, 16, 1, 16, 1, 3, 3, 13, 1, 13,
960 2, 2, 1, 15, 1, 5, 14, 15, 1, 5, 14, 1, 17, 8, 17, 8,
961 1, 4, 4, 2, 2, 1, 25, 25, 24, 24, 1, 3, 1, 3, 1, 8,
962 6, 7, 6, 1, 18, 8, 18, 1, 7, 23, 2, 2, 23, 1, 1, 21,
963 22, 9, 9, 22, 19, 1, 21, 5, 19, 5, 1, 33, 20, 33, 20, 8,
964 4, 4, 1, 32, 2, 2, 8, 3, 32, 26, 3, 1, 7, 7, 26, 6,
965 1, 6, 1, 1, 16, 1, 10, 1, 10, 2, 16, 29, 28, 2, 29, 28,
966 1, 27, 5, 8, 5, 27, 1, 8, 3, 7, 3, 31, 41, 31, 1, 41,
967 6, 1, 6, 7, 4, 4, 1, 1, 2, 1, 2, 11, 34, 30, 11, 1,
968 30, 15, 15, 34, 36, 40, 36, 40, 35, 35, 37, 37, 39, 39, 38, 38},
971 { 1, -1, 0, 2, -2, 0, 3, -3, 1, -1, 4, -4, 5, -5, 1, -1,
972 6, -6, 2, -2, 7, -7, 1, -1, 8, -8, 9, -9, 3, -3, 1, -1,
973 10, -10, 2, -2, 11, -11, 1, -1, 12, 4, -12, -4, 1, -1, 13, -13,
974 1, -1, 14, -14, 2, 5, 15, -2, -5, -15, -3, 3, 16, -16, 17, 1,
975 -1, -17, 6, 18, -6, -18, 2, -2, 19, -19, 1, -1, 20, -20, 4, -4,
976 7, -7, 21, -21, 1, -1, 2, 3, -3, 22, -2, -22, 8, 23, -8, 1,
977 2, -23, -1, 2, -2, -2, 24, 1, -24, -1, 25, 5, -5, 1, -25, -1,
978 9, -9, 26, 1, -26, 3, 1, -1, 27, -3, -1, -27, 1, 3, -1, -3,
979 28, -4, 4, 10, -10, -28, 1, -1, 1, -1, 29, 6, -29, -6, 30, -4,
980 3, 3, -3, -30, 1, 4, -1, 31, -3, 1, 11, -11, -1, -31, 32, -1,
981 -1, 2, -2, 1, 1, -32, 1, 4, -1, -4, 33, -1, 1, 1, -1, 5,
982 5, -5, -33, -1, -12, 12, -5, -7, 1, 1, 7, 34, 4, -4, -1, 4,
983 -34, -4, 35, 36, -2, -35, -2, -36, 2, 13, 2, -1, 1, -13, 1, -1,
984 37, 1, -5, 6, 5, -1, 38, -6, -8, 5, 8, -1, 1, 1, -37, -1,
985 5, 39, -5, -5, 6, -6, -38, -39, -14, 40, 14, 2, 1, 1, -2, -40,
986 -1, -2, 2, -1, -1, -1, 1, 1, 1, -1, 1, -1, 1, -1, 1, -1}
992 {0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 8, 6, 8, 7,
993 7, 9, 9, 10, 10, 11, 11, 1, 12, 1, 12, 13, 13, 16, 14, 16,
994 14, 15, 15, 17, 17, 18, 0, 18, 19, 20, 21, 19, 22, 21, 20, 22,
995 25, 24, 2, 25, 24, 23, 23, 2, 26, 28, 26, 28, 29, 27, 29, 27,
996 33, 33, 1, 32, 1, 3, 32, 30, 36, 3, 36, 30, 31, 31, 35, 34,
997 37, 41, 34, 35, 37, 4, 41, 4, 49, 8, 8, 49, 40, 38, 5, 38,
998 40, 39, 5, 39, 42, 43, 42, 7, 57, 6, 43, 44, 6, 50, 7, 44,
999 57, 48, 50, 48, 45, 45, 46, 47, 51, 46, 47, 58, 1, 51, 58, 1,
1000 52, 59, 53, 9, 52, 55, 55, 59, 53, 56, 54, 56, 54, 9, 64, 64,
1001 60, 63, 60, 63, 61, 62, 61, 62, 2, 10, 2, 10, 11, 1, 11, 13,
1002 12, 1, 12, 13, 16, 16, 8, 8, 14, 3, 3, 15, 14, 15, 4, 4,
1003 1, 17, 17, 5, 1, 7, 7, 5, 6, 1, 2, 2, 6, 22, 1, 25,
1004 21, 22, 8, 24, 1, 21, 25, 24, 8, 18, 18, 23, 9, 20, 23, 33,
1005 29, 33, 20, 1, 19, 1, 29, 36, 9, 36, 19, 41, 28, 57, 32, 3,
1006 28, 3, 1, 27, 49, 49, 1, 32, 26, 26, 2, 4, 4, 7, 57, 41,
1007 2, 7, 10, 5, 37, 16, 10, 27, 8, 8, 13, 16, 37, 13, 1, 5},
1010 {0, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, 1, -1, -1, 1,
1011 -1, 1, -1, 1, -1, 1, -1, 2, 1, -2, -1, 1, -1, 1, 1, -1,
1012 -1, 1, -1, 1, -1, 1, 0, -1, 1, 1, 1, -1, 1, -1, -1, -1,
1013 1, 1, 2, -1, -1, 1, -1, -2, 1, 1, -1, -1, 1, 1, -1, -1,
1014 1, -1, 3, 1, -3, 2, -1, 1, 1, -2, -1, -1, -1, 1, 1, 1,
1015 1, 1, -1, -1, -1, 2, -1, -2, 1, 2, -2, -1, 1, 1, 2, -1,
1016 -1, 1, -2, -1, 1, 1, -1, 2, 1, 2, -1, 1, -2, -1, -2, -1,
1017 -1, 1, 1, -1, 1, -1, 1, 1, 1, -1, -1, 1, 4, -1, -1, -4,
1018 1, 1, 1, 2, -1, -1, 1, -1, -1, 1, -1, -1, 1, -2, 1, -1,
1019 1, 1, -1, -1, 1, 1, -1, -1, 3, 2, -3, -2, 2, 5, -2, 2,
1020 2, -5, -2, -2, -2, 2, -3, 3, 2, 3, -3, 2, -2, -2, 3, -3,
1021 6, 2, -2, 3, -6, 3, -3, -3, 3, 7, -4, 4, -3, 2, -7, 2,
1022 2, -2, -4, 2, 8, -2, -2, -2, 4, 2, -2, 2, 3, 2, -2, -2,
1023 2, 2, -2, -8, -2, 9, -2, 2, -3, -2, 2, -2, 2, 2, 2, 4,
1024 -2, -4, 10, 2, 2, -2, -9, -2, 2, -2, 5, 4, -4, 4, -2, 2,
1025 -5, -4, -3, 4, 2, -3, 3, -2, -5, 5, 3, 3, -2, -3, -10, -4}
1031 {1, 1, 0, 2, 2, 1, 1, 3, 3, 4, 4, 0, 1, 1, 5, 5,
1032 2, 2, 6, 6, 7, 7, 1, 8, 1, 8, 3, 3, 9, 9, 1, 2,
1033 2, 1, 4, 10, 4, 10, 11, 11, 1, 5, 12, 12, 1, 5, 13, 13,
1034 3, 3, 6, 6, 2, 2, 14, 14, 16, 16, 15, 7, 15, 8, 8, 7,
1035 1, 1, 17, 17, 4, 4, 1, 1, 18, 18, 2, 2, 5, 5, 25, 3,
1036 9, 3, 25, 9, 19, 24, 19, 24, 1, 21, 20, 1, 21, 22, 20, 22,
1037 23, 23, 8, 6, 33, 6, 8, 33, 7, 7, 26, 26, 1, 32, 1, 32,
1038 28, 4, 28, 10, 29, 27, 27, 10, 41, 4, 29, 2, 2, 41, 36, 31,
1039 49, 31, 34, 30, 34, 36, 30, 35, 1, 49, 11, 5, 35, 11, 1, 3,
1040 3, 5, 37, 37, 8, 40, 8, 40, 12, 12, 42, 42, 1, 38, 16, 57,
1041 1, 6, 16, 39, 38, 6, 7, 7, 13, 13, 39, 43, 2, 43, 57, 2,
1042 50, 9, 44, 9, 50, 4, 15, 48, 44, 4, 1, 15, 48, 14, 14, 1,
1043 45, 45, 8, 3, 5, 8, 51, 47, 3, 46, 46, 47, 5, 51, 1, 17,
1044 17, 58, 1, 58, 2, 52, 52, 2, 53, 7, 59, 6, 6, 56, 53, 55,
1045 7, 55, 1, 54, 59, 56, 54, 10, 1, 10, 4, 60, 1, 60, 8, 4,
1046 8, 64, 64, 61, 1, 63, 3, 63, 62, 61, 5, 11, 5, 3, 11, 62},
1049 { 1, -1, 0, 1, -1, 2, -2, 1, -1, 1, -1, 0, 3, -3, 1, -1,
1050 2, -2, 1, -1, 1, -1, 4, 1, -4, -1, 2, -2, 1, -1, 5, 3,
1051 -3, -5, 2, 1, -2, -1, 1, -1, 6, 2, 1, -1, -6, -2, 1, -1,
1052 3, -3, 2, -2, 4, -4, 1, -1, 1, -1, 1, 2, -1, 2, -2, -2,
1053 7, -7, 1, -1, 3, -3, 8, -8, 1, -1, 5, -5, 3, -3, 1, 4,
1054 2, -4, -1, -2, 1, 1, -1, -1, 9, 1, 1, -9, -1, 1, -1, -1,
1055 1, -1, 3, -3, 1, 3, -3, -1, 3, -3, 1, -1, 10, 1, -10, -1,
1056 1, 4, -1, 2, 1, -1, 1, -2, 1, -4, -1, 6, -6, -1, 1, 1,
1057 1, -1, 1, 1, -1, -1, -1, 1, 11, -1, -2, 4, -1, 2, -11, 5,
1058 -5, -4, -1, 1, 4, 1, -4, -1, -2, 2, 1, -1, 12, 1, -2, 1,
1059 -12, 4, 2, 1, -1, -4, 4, -4, 2, -2, -1, 1, 7, -1, -1, -7,
1060 -1, -3, 1, 3, 1, 5, 2, 1, -1, -5, 13, -2, -1, 2, -2, -13,
1061 1, -1, 5, 6, 5, -5, 1, 1, -6, 1, -1, -1, -5, -1, 14, 2,
1062 -2, 1, -14, -1, 8, 1, -1, -8, 1, 5, 1, 5, -5, 1, -1, 1,
1063 -5, -1, 15, 1, -1, -1, -1, 3, -15, -3, 6, 1, 16, -1, 6, -6,
1064 -6, 1, -1, 1, -16, 1, 7, -1, 1, -1, -6, -3, 6, -7, 3, -1}
1070 {0, 1, 1, 2, 2, 3, 3, 4, 4, 1, 1, 5, 5, 6, 6, 7,
1071 7, 8, 8, 9, 9, 2, 2, 10, 10, 1, 1, 11, 11, 12, 12, 3,
1072 3, 13, 13, 0, 14, 14, 16, 15, 16, 15, 4, 4, 17, 1, 17, 1,
1073 5, 5, 18, 18, 2, 2, 6, 6, 8, 19, 7, 8, 7, 19, 20, 20,
1074 21, 21, 22, 24, 22, 24, 23, 23, 1, 1, 25, 25, 3, 3, 26, 26,
1075 9, 9, 27, 27, 28, 28, 33, 29, 4, 33, 29, 1, 4, 1, 32, 32,
1076 2, 2, 31, 10, 30, 10, 30, 31, 34, 34, 5, 5, 36, 36, 35, 41,
1077 35, 11, 41, 11, 37, 1, 8, 8, 37, 6, 1, 6, 40, 7, 7, 40,
1078 12, 38, 12, 39, 39, 38, 49, 13, 49, 13, 3, 42, 3, 42, 16, 16,
1079 43, 43, 14, 14, 1, 1, 44, 15, 44, 15, 2, 2, 57, 48, 50, 48,
1080 57, 50, 4, 45, 45, 4, 46, 47, 47, 46, 1, 51, 1, 17, 17, 51,
1081 8, 9, 9, 5, 58, 8, 58, 5, 52, 52, 55, 56, 53, 56, 55, 59,
1082 59, 53, 54, 1, 6, 54, 7, 7, 6, 1, 2, 3, 2, 3, 64, 60,
1083 60, 10, 10, 64, 61, 62, 61, 63, 1, 63, 62, 1, 18, 24, 18, 4,
1084 25, 4, 8, 21, 21, 1, 24, 22, 25, 22, 8, 11, 19, 11, 23, 1,
1085 20, 23, 19, 20, 5, 12, 5, 1, 16, 2, 12, 13, 2, 13, 1, 16},
1088 { 0, 1, -1, 1, -1, 1, -1, 1, -1, 2, -2, 1, -1, 1, -1, 1,
1089 -1, 1, -1, 1, -1, 2, -2, 1, -1, 3, -3, 1, -1, 1, -1, 2,
1090 -2, 1, -1, 0, 1, -1, 1, 1, -1, -1, 2, -2, 1, 4, -1, -4,
1091 2, -2, 1, -1, -3, 3, 2, -2, 2, 1, 2, -2, -2, -1, 1, -1,
1092 1, -1, 1, 1, -1, -1, 1, -1, 5, -5, 1, -1, 3, -3, 1, -1,
1093 2, -2, 1, -1, 1, -1, 1, 1, 3, -1, -1, 6, -3, -6, -1, 1,
1094 4, -4, 1, 2, 1, -2, -1, -1, 1, -1, 3, -3, 1, -1, 1, 1,
1095 -1, 2, -1, -2, 1, 7, -3, 3, -1, 3, -7, -3, 1, -3, 3, -1,
1096 2, 1, -2, 1, -1, -1, 1, 2, -1, -2, -4, -1, 4, 1, 2, -2,
1097 1, -1, -2, 2, 8, -8, -1, 2, 1, -2, -5, 5, 1, -1, -1, 1,
1098 -1, 1, 4, -1, 1, -4, -1, -1, 1, 1, 9, 1, -9, 2, -2, -1,
1099 -4, 3, -3, -4, -1, 4, 1, 4, 1, -1, 1, -1, 1, 1, -1, 1,
1100 -1, -1, -1, 10, 4, 1, 4, -4, -4, -10, 6, 5, -6, -5, 1, -1,
1101 1, 3, -3, -1, 1, -1, -1, -1, 11, 1, 1, -11, -2, -2, 2, 5,
1102 -2, -5, -5, 2, -2, 12, 2, -2, 2, 2, 5, -3, -2, 3, -2, -12,
1103 -2, 2, 2, 2, -5, 3, 5, 13, -3, 7, -3, -3, -7, 3, -13, 3}
1109 {0, 1, 1, 1, 2, 2, 1, 3, 3, 1, 1, 1, 4, 4, 1, 5,
1110 2, 1, 5, 2, 1, 1, 6, 6, 1, 1, 1, 1, 1, 7, 3, 1,
1111 2, 3, 0, 1, 2, 7, 1, 1, 1, 8, 1, 1, 8, 1, 1, 1,
1112 9, 1, 9, 1, 2, 1, 1, 2, 1, 1, 10, 4, 1, 10, 1, 4,
1113 1, 1, 1, 1, 1, 3, 1, 1, 1, 3, 2, 1, 5, 1, 1, 1,
1114 2, 5, 1, 11, 1, 11, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1115 2, 1, 6, 1, 6, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 12,
1116 3, 1, 12, 1, 1, 1, 2, 1, 1, 3, 1, 1, 1, 1, 1, 1,
1117 4, 1, 1, 1, 2, 1, 1, 4, 1, 1, 1, 1, 1, 1, 2, 1,
1118 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 2, 1, 1, 5,
1119 1, 1, 1, 1, 1, 7, 1, 7, 1, 1, 2, 3, 1, 1, 1, 1,
1120 5, 1, 1, 1, 1, 1, 1, 2, 13, 1, 1, 1, 1, 1, 1, 1,
1121 1, 1, 1, 1, 1, 1, 1, 1, 13, 2, 1, 1, 4, 1, 1, 1,
1122 3, 1, 6, 1, 1, 1, 14, 1, 1, 1, 1, 1, 14, 6, 1, 1,
1123 1, 1, 15, 2, 4, 1, 2, 3, 15, 1, 1, 1, 8, 1, 1, 8,
1124 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1},
1127 { 0, 1, -1, 2, 1, -1, -2, 1, -1, 3, -3, 4, 1, -1, -4, 1,
1128 2, 5, -1, -2, -5, 6, 1, -1, -6, 7, -7, 8, -8, 1, 2, 9,
1129 3, -2, 0, -9, -3, -1, 10, -10, 11, 1, -11, 12, -1, -12, 13, -13,
1130 1, 14, -1, -14, 4, 15, -15, -4, 16, -16, 1, 2, 17, -1, -17, -2,
1131 18, -18, 19, -19, 20, 3, -20, 21, -21, -3, 5, 22, 2, -22, -23, 23,
1132 -5, -2, 24, 1, -24, -1, 25, -25, 26, -26, -27, 27, 28, 29, -28, -29,
1133 6, 30, 2, -31, -2, -30, 31, -6, -32, 32, 33, -33, 34, -35, -34, 1,
1134 4, -36, -1, 35, 37, 36, 7, -37, 38, -4, -38, 39, 41, 40, -40, -39,
1135 3, 42, -43, -41, -7, -42, 43, -3, 44, -44, 45, -45, 46, 47, 8, -47,
1136 -48, -46, 50, -50, 48, 49, 51, -49, 52, -52, 5, -51, -8, -53, 53, 3,
1137 -56, 56, 55, 54, -54, 2, 60, -2, -55, 58, 9, -5, 59, 57, -57, -63,
1138 -3, -58, -60, -61, 61, -59, -62, -9, 1, 64, 62, 69, -64, 63, 65, -67,
1139 -68, 66, -65, 68, -66, -69, 67, -70, -1, 10, 71, -71, 4, 73, 72, 70,
1140 6, -76, -3, 74, -78, -74, 1, 78, 80, -72, -75, 76, -1, 3, -73, 79,
1141 75, 77, 1, 11, -4, -79, -10, -6, -1, -77, -83, -80, 2, 81, -84, -2,
1142 83, -81, 82, -82, 84, -87, -86, 85, -11, -85, 86, -89, 87, -88, 88, 89}
1148 {1, 1, 0, 2, 1, 2, 1, 3, 3, 1, 1, 4, 4, 2, 2, 1,
1149 1, 5, 5, 6, 1, 6, 1, 7, 7, 3, 3, 2, 8, 2, 8, 1,
1150 1, 0, 9, 9, 1, 1, 10, 4, 10, 4, 11, 11, 2, 1, 2, 1,
1151 12, 12, 3, 3, 1, 1, 13, 5, 5, 13, 14, 1, 1, 14, 2, 2,
1152 6, 6, 15, 1, 1, 15, 16, 4, 7, 16, 4, 7, 1, 1, 3, 3,
1153 8, 8, 2, 2, 1, 1, 17, 17, 1, 1, 18, 18, 5, 5, 2, 2,
1154 1, 1, 9, 19, 9, 19, 20, 3, 3, 20, 1, 10, 21, 1, 10, 4,
1155 4, 21, 22, 6, 6, 22, 1, 1, 23, 24, 2, 2, 23, 24, 11, 1,
1156 1, 11, 7, 25, 7, 1, 1, 25, 8, 8, 3, 26, 3, 1, 12, 2,
1157 2, 26, 1, 12, 5, 5, 27, 4, 1, 4, 1, 27, 28, 1, 28, 13,
1158 1, 13, 2, 29, 2, 1, 32, 6, 1, 30, 14, 29, 14, 6, 3, 31,
1159 3, 1, 30, 1, 32, 31, 33, 9, 33, 1, 1, 7, 9, 7, 2, 2,
1160 1, 1, 4, 36, 34, 4, 5, 10, 10, 5, 34, 1, 1, 35, 8, 8,
1161 36, 3, 35, 1, 15, 3, 2, 1, 16, 15, 16, 2, 37, 1, 37, 1,
1162 1, 1, 6, 6, 38, 1, 38, 11, 1, 39, 39, 40, 11, 2, 41, 4,
1163 40, 1, 2, 4, 1, 1, 1, 41, 3, 1, 3, 1, 5, 7, 5, 7},
1166 { 1, -1, 0, 1, 2, -1, -2, 1, -1, 3, -3, 1, -1, 2, -2, 4,
1167 -4, 1, -1, 1, 5, -1, -5, 1, -1, 2, -2, 3, 1, -3, -1, 6,
1168 -6, 0, 1, -1, 7, -7, 1, 2, -1, -2, 1, -1, 4, 8, -4, -8,
1169 1, -1, 3, -3, 9, -9, 1, 2, -2, -1, 1, 10, -10, -1, 5, -5,
1170 2, -2, 1, 11, -11, -1, 1, 3, 2, -1, -3, -2, 12, -12, 4, -4,
1171 2, -2, -6, 6, 13, -13, 1, -1, 14, -14, 1, -1, 3, -3, 7, -7,
1172 15, -15, 2, 1, -2, -1, 1, 5, -5, -1, -16, 2, 1, 16, -2, 4,
1173 -4, -1, 1, 3, -3, -1, 17, -17, 1, 1, -8, 8, -1, -1, 2, 18,
1174 -18, -2, 3, 1, -3, 19, -19, -1, 3, -3, 6, 1, -6, 20, 2, 9,
1175 -9, -1, -20, -2, 4, -4, 1, -5, 21, 5, -21, -1, 1, -22, -1, 2,
1176 22, -2, 10, 1, -10, 23, 1, 4, -23, 1, 2, -1, -2, -4, -7, 1,
1177 7, -24, -1, 24, -1, -1, 1, 3, -1, -25, 25, 4, -3, -4, 11, -11,
1178 26, -26, 6, 1, 1, -6, -5, -3, 3, 5, -1, -27, 27, 1, 4, -4,
1179 -1, -8, -1, 28, 2, 8, -12, -28, -2, -2, 2, 12, -1, 29, 1, -29,
1180 30, -30, 5, -5, 1, -31, -1, 3, 31, -1, 1, 1, -3, -13, 1, -7,
1181 -1, -32, 13, 7, 32, 33, -33, -1, -9, -34, 9, 34, -6, 5, 6, -5}
1187 {1, 1, 0, 1, 1, 2, 2, 1, 1, 3, 3, 1, 1, 0, 2, 2,
1188 4, 1, 4, 1, 1, 1, 5, 5, 1, 1, 6, 6, 2, 2, 1, 1,
1189 3, 3, 7, 7, 1, 1, 8, 8, 1, 1, 2, 2, 1, 9, 1, 9,
1190 4, 4, 10, 1, 1, 10, 1, 1, 11, 11, 3, 3, 1, 2, 1, 2,
1191 1, 1, 12, 12, 5, 5, 1, 1, 13, 1, 1, 13, 2, 2, 1, 1,
1192 6, 6, 1, 1, 4, 14, 4, 14, 3, 1, 3, 1, 1, 1, 15, 7,
1193 15, 2, 2, 7, 1, 1, 1, 8, 1, 8, 16, 16, 1, 1, 1, 1,
1194 2, 1, 1, 2, 1, 1, 3, 5, 5, 3, 4, 1, 1, 4, 1, 1,
1195 17, 17, 9, 1, 1, 9, 2, 2, 1, 1, 10, 10, 1, 6, 1, 1,
1196 6, 18, 1, 1, 18, 1, 1, 1, 2, 2, 3, 1, 3, 1, 1, 1,
1197 4, 1, 19, 1, 19, 7, 1, 1, 20, 1, 4, 20, 1, 7, 11, 2,
1198 1, 11, 21, 2, 8, 5, 1, 8, 1, 5, 21, 1, 1, 1, 22, 1,
1199 1, 22, 1, 1, 3, 3, 1, 23, 2, 12, 24, 1, 1, 2, 1, 1,
1200 12, 23, 1, 1, 24, 1, 1, 1, 4, 1, 1, 1, 2, 1, 6, 6,
1201 4, 2, 1, 1, 1, 1, 1, 1, 1, 14, 13, 3, 1, 25, 9, 25,
1202 14, 1, 9, 3, 13, 1, 1, 1, 1, 1, 10, 1, 1, 2, 10, 2},
1205 {-20, -1, 0, 2, -2, 1, -1, 3, -3, 1, -1, 4, -4, 0, 2, -2,
1206 1, 5, -1, -5, 6, -6, 1, -1, 7, -7, 1, -1, 3, -3, 8, -8,
1207 2, -2, 1, -1, 9, -9, 1, -1, 10, -10, 4, -4, 11, 1, -11, -1,
1208 2, -2, 1, 12, -12, -1, 13, -13, 1, -1, 3, -3, 14, 5, -14, -5,
1209 -15, 15, -1, 1, 2, -2, 16, -16, 1, 17, -17, -1, 6, -6, 18, -18,
1210 2, -2, -19, 19, -3, 1, 3, -1, 4, 20, -4, 1, -21, 21, 1, 2,
1211 -1, -7, 7, -2, 22, -22, 23, 2, -23, -2, 1, -1, -24, 24, -25, 25,
1212 -8, -26, 26, 8, -27, 27, 5, 3, -3, -5, -4, 28, -28, 4, 29, -29,
1213 1, -1, -2, -30, 30, 2, 9, -9, -31, 31, 2, -2, -32, 3, 32, -33,
1214 -3, 1, 33, -34, -1, 34, -35, 35, -10, 10, -6, 36, 6, -36, 37, -37,
1215 -5, 38, 1, -38, -1, 3, 39, -39, -1, 40, 5, 1, -40, -3, 2, -11,
1216 -41, -2, 1, 11, -3, -4, 41, 3, 42, 4, -1, -43, -42, 43, 1, -44,
1217 45, -1, 44, -45, -7, 7, -46, 1, -12, 2, 1, -47, 46, 12, 47, 48,
1218 -2, -1, -48, 49, -1, -50, -49, 50, -6, -51, 51, 52, -13, 53, -4, 4,
1219 6, 13, -53, -52, -54, 55, 54, -55, -56, -2, 2, -8, 56, 1, -3, -1,
1220 2, 58, 3, 8, -2, 57, -58, -60, -59, -57, -3, 60, 59, -14, 3, 14}
1226 {1, 1, 0, 2, 2, 1, 1, 3, 3, 4, 4, 5, 5, 1, 1, 6,
1227 6, 2, 2, 7, 7, 8, 8, 1, 1, 3, 3, 9, 9, 10, 10, 1,
1228 1, 2, 2, 4, 4, 11, 0, 11, 12, 12, 13, 13, 1, 1, 5, 5,
1229 14, 14, 15, 16, 15, 16, 3, 3, 1, 6, 1, 6, 2, 2, 7, 7,
1230 8, 8, 17, 17, 1, 1, 4, 4, 18, 18, 2, 2, 1, 19, 1, 20,
1231 19, 20, 21, 21, 3, 3, 22, 22, 5, 5, 24, 1, 1, 23, 9, 23,
1232 24, 9, 2, 2, 10, 1, 1, 10, 6, 6, 25, 4, 4, 25, 7, 7,
1233 26, 8, 1, 8, 3, 1, 26, 3, 11, 11, 27, 27, 2, 28, 1, 2,
1234 28, 1, 12, 12, 5, 5, 29, 13, 13, 29, 32, 1, 1, 33, 31, 30,
1235 32, 4, 30, 33, 4, 31, 3, 14, 1, 1, 3, 34, 34, 2, 2, 14,
1236 6, 6, 35, 36, 35, 36, 1, 15, 1, 16, 16, 15, 7, 9, 7, 9,
1237 37, 8, 8, 37, 1, 1, 39, 2, 38, 39, 2, 40, 5, 38, 40, 5,
1238 3, 3, 4, 4, 10, 10, 1, 1, 1, 1, 41, 2, 41, 2, 6, 6,
1239 1, 1, 11, 42, 11, 43, 3, 42, 3, 17, 4, 43, 1, 17, 7, 1,
1240 8, 44, 4, 7, 44, 5, 8, 2, 5, 1, 2, 48, 45, 1, 12, 45,
1241 12, 48, 13, 13, 1, 9, 9, 46, 1, 46, 47, 47, 49, 18, 18, 49},
1244 { 1, -1, 0, 1, -1, 2, -2, 1, -1, 1, -1, 1, -1, 3, -3, 1,
1245 -1, -2, 2, 1, -1, 1, -1, 4, -4, -2, 2, 1, -1, 1, -1, 5,
1246 -5, -3, 3, 2, -2, 1, 0, -1, 1, -1, 1, -1, 6, -6, 2, -2,
1247 1, -1, 1, 1, -1, -1, -3, 3, 7, 2, -7, -2, -4, 4, 2, -2,
1248 2, -2, 1, -1, 8, -8, 3, -3, 1, -1, -5, 5, 9, 1, -9, 1,
1249 -1, -1, 1, -1, -4, 4, 1, -1, 3, -3, 1, -10, 10, 1, 2, -1,
1250 -1, -2, 6, -6, 2, 11, -11, -2, 3, -3, 1, -4, 4, -1, 3, -3,
1251 1, 3, 12, -3, -5, -12, -1, 5, 2, -2, 1, -1, -7, 1, 13, 7,
1252 -1, -13, 2, -2, 4, -4, 1, 2, -2, -1, 1, 14, -14, 1, 1, 1,
1253 -1, -5, -1, -1, 5, -1, -6, 2, -15, 15, 6, 1, -1, -8, 8, -2,
1254 -4, 4, 1, 1, -1, -1, 16, 2, -16, -2, 2, -2, 4, 3, -4, -3,
1255 -1, -4, 4, 1, -17, 17, -1, -9, 1, 1, 9, 1, -5, -1, -1, 5,
1256 -7, 7, 6, -6, 3, -3, 18, -18, 19, -19, 1, -10, -1, 10, -5, 5,
1257 20, -20, -3, 1, 3, 1, 8, -1, -8, 2, 7, -1, -21, -2, 5, 21,
1258 5, -1, -7, -5, 1, -6, -5, -11, 6, 22, 11, 1, 1, -22, -3, -1,
1259 3, -1, 3, -3, -23, 4, -4, 1, 23, -1, 1, -1, 1, -2, 2, -1}
1265 {1, 1, 1, 1, 0, 2, 2, 1, 1, 3, 3, 0, 1, 1, 2, 2,
1266 4, 4, 1, 1, 5, 5, 1, 1, 2, 2, 3, 3, 6, 6, 1, 1,
1267 7, 7, 8, 1, 8, 2, 2, 1, 4, 4, 1, 3, 1, 3, 9, 9,
1268 2, 2, 1, 5, 1, 5, 10, 10, 1, 1, 11, 11, 3, 6, 3, 4,
1269 4, 6, 2, 2, 1, 12, 1, 12, 7, 13, 7, 13, 1, 1, 8, 8,
1270 2, 2, 14, 14, 16, 15, 16, 5, 5, 1, 3, 15, 1, 3, 4, 4,
1271 1, 1, 17, 17, 2, 2, 6, 6, 1, 18, 1, 18, 22, 21, 22, 21,
1272 25, 24, 25, 19, 9, 20, 9, 23, 19, 24, 20, 3, 23, 7, 3, 1,
1273 1, 7, 28, 26, 29, 5, 28, 26, 5, 8, 29, 4, 8, 27, 2, 2,
1274 4, 27, 1, 1, 10, 36, 10, 33, 33, 36, 30, 1, 32, 32, 1, 30,
1275 6, 31, 31, 35, 3, 6, 11, 11, 3, 2, 35, 2, 34, 1, 34, 1,
1276 37, 37, 12, 7, 12, 5, 41, 5, 4, 7, 1, 8, 13, 4, 1, 41,
1277 13, 38, 8, 38, 9, 1, 40, 40, 9, 1, 39, 2, 2, 49, 39, 42,
1278 3, 3, 14, 16, 49, 14, 16, 42, 43, 43, 6, 6, 15, 1, 1, 15,
1279 44, 44, 1, 1, 50, 48, 4, 5, 4, 7, 5, 2, 10, 10, 48, 7,
1280 50, 45, 2, 1, 45, 8, 8, 1, 46, 46, 3, 47, 47, 3, 1, 1},
1283 { 1, -1, 2, -2, 0, 1, -1, 3, -3, 1, -1, 0, 4, -4, 2, -2,
1284 1, -1, 5, -5, 1, -1, 6, -6, 3, -3, 2, -2, 1, -1, 7, -7,
1285 1, -1, 1, 8, -1, 4, -4, -8, 2, -2, 9, 3, -9, -3, 1, -1,
1286 5, -5, 10, 2, -10, -2, 1, -1, 11, -11, 1, -1, -4, 2, 4, 3,
1287 -3, -2, 6, -6, 12, 1, -12, -1, 2, 1, -2, -1, 13, -13, 2, -2,
1288 7, -7, 1, -1, 1, 1, -1, 3, -3, 14, 5, -1, -14, -5, 4, -4,
1289 15, -15, 1, -1, 8, -8, -3, 3, 16, 1, -16, -1, 1, 1, -1, -1,
1290 1, 1, -1, 1, 2, 1, -2, 1, -1, -1, -1, 6, -1, 3, -6, 17,
1291 -17, -3, 1, 1, 1, 4, -1, -1, -4, 3, -1, 5, -3, -1, -9, 9,
1292 -5, 1, 18, -18, 2, 1, -2, 1, -1, -1, 1, 19, -1, 1, -19, -1,
1293 4, 1, -1, 1, 7, -4, -2, 2, -7, 10, -1, -10, 1, 20, -1, -20,
1294 1, -1, 2, 4, -2, 5, 1, -5, 6, -4, 21, 4, 2, -6, -21, -1,
1295 -2, 1, -4, -1, -3, 22, -1, 1, 3, -22, -1, 11, -11, 1, 1, 1,
1296 8, -8, 2, 2, -1, -2, -2, -1, 1, -1, -5, 5, 2, 23, -23, -2,
1297 1, -1, 24, -24, -1, -1, 7, 6, -7, 5, -6, 12, -3, 3, 1, -5,
1298 1, 1, -12, 25, -1, -5, 5, -25, -1, 1, 9, 1, -1, -9, 26, -26}