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);
499 * Handle empty tiles by performing data copying and motion
500 * compensation respectively.
502 * @param[in] avctx ptr to the AVCodecContext
503 * @param[in] band pointer to the band descriptor
504 * @param[in] tile pointer to the tile descriptor
505 * @param[in] mv_scale scaling factor for motion vectors
507 static int ivi_process_empty_tile(AVCodecContext *avctx, IVIBandDesc *band,
508 IVITile *tile, int32_t mv_scale)
510 int x, y, need_mc, mbn, blk, num_blocks, mv_x, mv_y, mc_type;
511 int offs, mb_offset, row_offset;
512 IVIMbInfo *mb, *ref_mb;
515 void (*mc_no_delta_func)(int16_t *buf, const int16_t *ref_buf, uint32_t pitch,
518 if (tile->num_MBs != IVI_MBs_PER_TILE(tile->width, tile->height, band->mb_size)) {
519 av_log(avctx, AV_LOG_ERROR, "Allocated tile size %d mismatches "
520 "parameters %d in ivi_process_empty_tile()\n",
521 tile->num_MBs, IVI_MBs_PER_TILE(tile->width, tile->height, band->mb_size));
522 return AVERROR_INVALIDDATA;
525 offs = tile->ypos * band->pitch + tile->xpos;
527 ref_mb = tile->ref_mbs;
528 row_offset = band->mb_size * band->pitch;
529 need_mc = 0; /* reset the mc tracking flag */
531 for (y = tile->ypos; y < (tile->ypos + tile->height); y += band->mb_size) {
534 for (x = tile->xpos; x < (tile->xpos + tile->width); x += band->mb_size) {
537 mb->buf_offs = mb_offset;
539 mb->type = 1; /* set the macroblocks type = INTER */
540 mb->cbp = 0; /* all blocks are empty */
542 if (!band->qdelta_present && !band->plane && !band->band_num) {
543 mb->q_delta = band->glob_quant;
548 if (band->inherit_qdelta && ref_mb)
549 mb->q_delta = ref_mb->q_delta;
551 if (band->inherit_mv && ref_mb) {
552 /* motion vector inheritance */
554 mb->mv_x = ivi_scale_mv(ref_mb->mv_x, mv_scale);
555 mb->mv_y = ivi_scale_mv(ref_mb->mv_y, mv_scale);
557 mb->mv_x = ref_mb->mv_x;
558 mb->mv_y = ref_mb->mv_y;
560 need_mc |= mb->mv_x || mb->mv_y; /* tracking non-zero motion vectors */
566 mb_offset += band->mb_size;
571 if (band->inherit_mv && need_mc) { /* apply motion compensation if there is at least one non-zero motion vector */
572 num_blocks = (band->mb_size != band->blk_size) ? 4 : 1; /* number of blocks per mb */
573 mc_no_delta_func = (band->blk_size == 8) ? ff_ivi_mc_8x8_no_delta
574 : ff_ivi_mc_4x4_no_delta;
576 for (mbn = 0, mb = tile->mbs; mbn < tile->num_MBs; mb++, mbn++) {
579 if (!band->is_halfpel) {
580 mc_type = 0; /* we have only fullpel vectors */
582 mc_type = ((mv_y & 1) << 1) | (mv_x & 1);
584 mv_y >>= 1; /* convert halfpel vectors into fullpel ones */
587 for (blk = 0; blk < num_blocks; blk++) {
588 /* adjust block position in the buffer according with its number */
589 offs = mb->buf_offs + band->blk_size * ((blk & 1) + !!(blk & 2) * band->pitch);
590 mc_no_delta_func(band->buf + offs,
591 band->ref_buf + offs + mv_y * band->pitch + mv_x,
592 band->pitch, mc_type);
596 /* copy data from the reference tile into the current one */
597 src = band->ref_buf + tile->ypos * band->pitch + tile->xpos;
598 dst = band->buf + tile->ypos * band->pitch + tile->xpos;
599 for (y = 0; y < tile->height; y++) {
600 memcpy(dst, src, tile->width*sizeof(band->buf[0]));
611 static uint16_t ivi_calc_band_checksum(IVIBandDesc *band)
614 int16_t *src, checksum;
619 for (y = 0; y < band->height; src += band->pitch, y++)
620 for (x = 0; x < band->width; x++)
627 void ff_ivi_output_plane(IVIPlaneDesc *plane, uint8_t *dst, int dst_pitch)
630 const int16_t *src = plane->bands[0].buf;
631 uint32_t pitch = plane->bands[0].pitch;
636 for (y = 0; y < plane->height; y++) {
637 for (x = 0; x < plane->width; x++)
638 dst[x] = av_clip_uint8(src[x] + 128);
645 * Decode an Indeo 4 or 5 band.
647 * @param[in,out] ctx ptr to the decoder context
648 * @param[in,out] band ptr to the band descriptor
649 * @param[in] avctx ptr to the AVCodecContext
650 * @return result code: 0 = OK, -1 = error
652 static int decode_band(IVI45DecContext *ctx, int plane_num,
653 IVIBandDesc *band, AVCodecContext *avctx)
655 int result, i, t, idx1, idx2, pos;
658 band->buf = band->bufs[ctx->dst_buf];
660 av_log(avctx, AV_LOG_ERROR, "Band buffer points to no data!\n");
661 return AVERROR_INVALIDDATA;
663 band->ref_buf = band->bufs[ctx->ref_buf];
664 band->data_ptr = ctx->frame_data + (get_bits_count(&ctx->gb) >> 3);
666 result = ctx->decode_band_hdr(ctx, band, avctx);
668 av_log(avctx, AV_LOG_ERROR, "Error while decoding band header: %d\n",
673 if (band->is_empty) {
674 av_log(avctx, AV_LOG_ERROR, "Empty band encountered!\n");
675 return AVERROR_INVALIDDATA;
678 band->rv_map = &ctx->rvmap_tabs[band->rvmap_sel];
680 /* apply corrections to the selected rvmap table if present */
681 for (i = 0; i < band->num_corr; i++) {
682 idx1 = band->corr[i * 2];
683 idx2 = band->corr[i * 2 + 1];
684 FFSWAP(uint8_t, band->rv_map->runtab[idx1], band->rv_map->runtab[idx2]);
685 FFSWAP(int16_t, band->rv_map->valtab[idx1], band->rv_map->valtab[idx2]);
686 if (idx1 == band->rv_map->eob_sym || idx2 == band->rv_map->eob_sym)
687 band->rv_map->eob_sym ^= idx1 ^ idx2;
688 if (idx1 == band->rv_map->esc_sym || idx2 == band->rv_map->esc_sym)
689 band->rv_map->esc_sym ^= idx1 ^ idx2;
692 pos = get_bits_count(&ctx->gb);
694 for (t = 0; t < band->num_tiles; t++) {
695 tile = &band->tiles[t];
697 if (tile->mb_size != band->mb_size) {
698 av_log(avctx, AV_LOG_ERROR, "MB sizes mismatch: %d vs. %d\n",
699 band->mb_size, tile->mb_size);
700 return AVERROR_INVALIDDATA;
702 tile->is_empty = get_bits1(&ctx->gb);
703 if (tile->is_empty) {
704 result = ivi_process_empty_tile(avctx, band, tile,
705 (ctx->planes[0].bands[0].mb_size >> 3) - (band->mb_size >> 3));
708 av_dlog(avctx, "Empty tile encountered!\n");
710 tile->data_size = ff_ivi_dec_tile_data_size(&ctx->gb);
711 if (!tile->data_size) {
712 av_log(avctx, AV_LOG_ERROR, "Tile data size is zero!\n");
713 result = AVERROR_INVALIDDATA;
717 result = ctx->decode_mb_info(ctx, band, tile, avctx);
721 result = ff_ivi_decode_blocks(&ctx->gb, band, tile);
722 if (result < 0 || ((get_bits_count(&ctx->gb) - pos) >> 3) != tile->data_size) {
723 av_log(avctx, AV_LOG_ERROR, "Corrupted tile data encountered!\n");
727 pos += tile->data_size << 3; // skip to next tile
731 /* restore the selected rvmap table by applying its corrections in reverse order */
732 for (i = band->num_corr-1; i >= 0; i--) {
733 idx1 = band->corr[i*2];
734 idx2 = band->corr[i*2+1];
735 FFSWAP(uint8_t, band->rv_map->runtab[idx1], band->rv_map->runtab[idx2]);
736 FFSWAP(int16_t, band->rv_map->valtab[idx1], band->rv_map->valtab[idx2]);
737 if (idx1 == band->rv_map->eob_sym || idx2 == band->rv_map->eob_sym)
738 band->rv_map->eob_sym ^= idx1 ^ idx2;
739 if (idx1 == band->rv_map->esc_sym || idx2 == band->rv_map->esc_sym)
740 band->rv_map->esc_sym ^= idx1 ^ idx2;
744 if (band->checksum_present) {
745 uint16_t chksum = ivi_calc_band_checksum(band);
746 if (chksum != band->checksum) {
747 av_log(avctx, AV_LOG_ERROR,
748 "Band checksum mismatch! Plane %d, band %d, received: %x, calculated: %x\n",
749 band->plane, band->band_num, band->checksum, chksum);
754 align_get_bits(&ctx->gb);
759 int ff_ivi_decode_frame(AVCodecContext *avctx, void *data, int *data_size,
762 IVI45DecContext *ctx = avctx->priv_data;
763 const uint8_t *buf = avpkt->data;
764 int buf_size = avpkt->size;
767 init_get_bits(&ctx->gb, buf, buf_size * 8);
768 ctx->frame_data = buf;
769 ctx->frame_size = buf_size;
771 result = ctx->decode_pic_hdr(ctx, avctx);
773 av_log(avctx, AV_LOG_ERROR,
774 "Error while decoding picture header: %d\n", result);
777 if (ctx->gop_invalid)
778 return AVERROR_INVALIDDATA;
780 if (ctx->gop_flags & IVI5_IS_PROTECTED) {
781 av_log(avctx, AV_LOG_ERROR, "Password-protected clip!\n");
785 ctx->switch_buffers(ctx);
789 if (ctx->is_nonnull_frame(ctx)) {
790 ctx->buf_invalid[ctx->dst_buf] = 1;
791 for (p = 0; p < 3; p++) {
792 for (b = 0; b < ctx->planes[p].num_bands; b++) {
793 result = decode_band(ctx, p, &ctx->planes[p].bands[b], avctx);
795 av_log(avctx, AV_LOG_ERROR,
796 "Error while decoding band: %d, plane: %d\n", b, p);
801 ctx->buf_invalid[ctx->dst_buf] = 0;
803 if (ctx->buf_invalid[ctx->dst_buf])
806 //STOP_TIMER("decode_planes"); }
808 /* If the bidirectional mode is enabled, next I and the following P frame will */
809 /* be sent together. Unfortunately the approach below seems to be the only way */
810 /* to handle the B-frames mode. That's exactly the same Intel decoders do. */
811 if (avctx->codec_id == AV_CODEC_ID_INDEO4 && ctx->frame_type == 0/*FRAMETYPE_INTRA*/) {
812 while (get_bits(&ctx->gb, 8)); // skip version string
813 skip_bits_long(&ctx->gb, 64); // skip padding, TODO: implement correct 8-bytes alignment
814 if (get_bits_left(&ctx->gb) > 18 && show_bits(&ctx->gb, 18) == 0x3FFF8)
815 av_log(avctx, AV_LOG_ERROR, "Buffer contains IP frames!\n");
818 if (!ctx->is_nonnull_frame(ctx))
821 if (ctx->frame.data[0])
822 avctx->release_buffer(avctx, &ctx->frame);
824 ctx->frame.reference = 0;
825 avcodec_set_dimensions(avctx, ctx->planes[0].width, ctx->planes[0].height);
826 if ((result = avctx->get_buffer(avctx, &ctx->frame)) < 0) {
827 av_log(avctx, AV_LOG_ERROR, "get_buffer() failed\n");
831 if (ctx->is_scalable) {
832 if (avctx->codec_id == AV_CODEC_ID_INDEO4)
833 ff_ivi_recompose_haar(&ctx->planes[0], ctx->frame.data[0], ctx->frame.linesize[0]);
835 ff_ivi_recompose53 (&ctx->planes[0], ctx->frame.data[0], ctx->frame.linesize[0]);
837 ff_ivi_output_plane(&ctx->planes[0], ctx->frame.data[0], ctx->frame.linesize[0]);
840 ff_ivi_output_plane(&ctx->planes[2], ctx->frame.data[1], ctx->frame.linesize[1]);
841 ff_ivi_output_plane(&ctx->planes[1], ctx->frame.data[2], ctx->frame.linesize[2]);
843 *data_size = sizeof(AVFrame);
844 *(AVFrame*)data = ctx->frame;
850 * Close Indeo5 decoder and clean up its context.
852 av_cold int ff_ivi_decode_close(AVCodecContext *avctx)
854 IVI45DecContext *ctx = avctx->priv_data;
856 ff_ivi_free_buffers(&ctx->planes[0]);
858 if (ctx->mb_vlc.cust_tab.table)
859 ff_free_vlc(&ctx->mb_vlc.cust_tab);
861 if (ctx->frame.data[0])
862 avctx->release_buffer(avctx, &ctx->frame);
864 #if IVI4_STREAM_ANALYSER
865 if (avctx->codec_id == AV_CODEC_ID_INDEO4) {
866 if (ctx->is_scalable)
867 av_log(avctx, AV_LOG_ERROR, "This video uses scalability mode!\n");
868 if (ctx->uses_tiling)
869 av_log(avctx, AV_LOG_ERROR, "This video uses local decoding!\n");
870 if (ctx->has_b_frames)
871 av_log(avctx, AV_LOG_ERROR, "This video contains B-frames!\n");
873 av_log(avctx, AV_LOG_ERROR, "Transparency mode is enabled!\n");
875 av_log(avctx, AV_LOG_ERROR, "This video uses Haar transform!\n");
876 if (ctx->uses_fullpel)
877 av_log(avctx, AV_LOG_ERROR, "This video uses fullpel motion vectors!\n");
886 * These are 2x8 predefined Huffman codebooks for coding macroblock/block
887 * signals. They are specified using "huffman descriptors" in order to
888 * avoid huge static tables. The decoding tables will be generated at
889 * startup from these descriptors.
891 const IVIHuffDesc ff_ivi_mb_huff_desc[8] = {
892 {8, {0, 4, 5, 4, 4, 4, 6, 6}},
893 {12, {0, 2, 2, 3, 3, 3, 3, 5, 3, 2, 2, 2}},
894 {12, {0, 2, 3, 4, 3, 3, 3, 3, 4, 3, 2, 2}},
895 {12, {0, 3, 4, 4, 3, 3, 3, 3, 3, 2, 2, 2}},
896 {13, {0, 4, 4, 3, 3, 3, 3, 2, 3, 3, 2, 1, 1}},
897 {9, {0, 4, 4, 4, 4, 3, 3, 3, 2}},
898 {10, {0, 4, 4, 4, 4, 3, 3, 2, 2, 2}},
899 {12, {0, 4, 4, 4, 3, 3, 2, 3, 2, 2, 2, 2}}
902 const IVIHuffDesc ff_ivi_blk_huff_desc[8] = {
903 {10, {1, 2, 3, 4, 4, 7, 5, 5, 4, 1}},
904 {11, {2, 3, 4, 4, 4, 7, 5, 4, 3, 3, 2}},
905 {12, {2, 4, 5, 5, 5, 5, 6, 4, 4, 3, 1, 1}},
906 {13, {3, 3, 4, 4, 5, 6, 6, 4, 4, 3, 2, 1, 1}},
907 {11, {3, 4, 4, 5, 5, 5, 6, 5, 4, 2, 2}},
908 {13, {3, 4, 5, 5, 5, 5, 6, 4, 3, 3, 2, 1, 1}},
909 {13, {3, 4, 5, 5, 5, 6, 5, 4, 3, 3, 2, 1, 1}},
910 {9, {3, 4, 4, 5, 5, 5, 6, 5, 5}}
915 * Scan patterns shared between indeo4 and indeo5
917 const uint8_t ff_ivi_vertical_scan_8x8[64] = {
918 0, 8, 16, 24, 32, 40, 48, 56,
919 1, 9, 17, 25, 33, 41, 49, 57,
920 2, 10, 18, 26, 34, 42, 50, 58,
921 3, 11, 19, 27, 35, 43, 51, 59,
922 4, 12, 20, 28, 36, 44, 52, 60,
923 5, 13, 21, 29, 37, 45, 53, 61,
924 6, 14, 22, 30, 38, 46, 54, 62,
925 7, 15, 23, 31, 39, 47, 55, 63
928 const uint8_t ff_ivi_horizontal_scan_8x8[64] = {
929 0, 1, 2, 3, 4, 5, 6, 7,
930 8, 9, 10, 11, 12, 13, 14, 15,
931 16, 17, 18, 19, 20, 21, 22, 23,
932 24, 25, 26, 27, 28, 29, 30, 31,
933 32, 33, 34, 35, 36, 37, 38, 39,
934 40, 41, 42, 43, 44, 45, 46, 47,
935 48, 49, 50, 51, 52, 53, 54, 55,
936 56, 57, 58, 59, 60, 61, 62, 63
939 const uint8_t ff_ivi_direct_scan_4x4[16] = {
940 0, 1, 4, 8, 5, 2, 3, 6, 9, 12, 13, 10, 7, 11, 14, 15
945 * Run-value (RLE) tables.
947 const RVMapDesc ff_ivi_rvmap_tabs[9] = {
952 {1, 1, 0, 1, 1, 0, 1, 1, 2, 2, 1, 1, 1, 1, 3, 3,
953 1, 1, 2, 2, 1, 1, 4, 4, 1, 1, 1, 1, 2, 2, 5, 5,
954 1, 1, 3, 3, 1, 1, 6, 6, 1, 2, 1, 2, 7, 7, 1, 1,
955 8, 8, 1, 1, 4, 2, 1, 4, 2, 1, 3, 3, 1, 1, 1, 9,
956 9, 1, 2, 1, 2, 1, 5, 5, 1, 1, 10, 10, 1, 1, 3, 3,
957 2, 2, 1, 1, 11, 11, 6, 4, 4, 1, 6, 1, 2, 1, 2, 12,
958 8, 1, 12, 7, 8, 7, 1, 16, 1, 16, 1, 3, 3, 13, 1, 13,
959 2, 2, 1, 15, 1, 5, 14, 15, 1, 5, 14, 1, 17, 8, 17, 8,
960 1, 4, 4, 2, 2, 1, 25, 25, 24, 24, 1, 3, 1, 3, 1, 8,
961 6, 7, 6, 1, 18, 8, 18, 1, 7, 23, 2, 2, 23, 1, 1, 21,
962 22, 9, 9, 22, 19, 1, 21, 5, 19, 5, 1, 33, 20, 33, 20, 8,
963 4, 4, 1, 32, 2, 2, 8, 3, 32, 26, 3, 1, 7, 7, 26, 6,
964 1, 6, 1, 1, 16, 1, 10, 1, 10, 2, 16, 29, 28, 2, 29, 28,
965 1, 27, 5, 8, 5, 27, 1, 8, 3, 7, 3, 31, 41, 31, 1, 41,
966 6, 1, 6, 7, 4, 4, 1, 1, 2, 1, 2, 11, 34, 30, 11, 1,
967 30, 15, 15, 34, 36, 40, 36, 40, 35, 35, 37, 37, 39, 39, 38, 38},
970 { 1, -1, 0, 2, -2, 0, 3, -3, 1, -1, 4, -4, 5, -5, 1, -1,
971 6, -6, 2, -2, 7, -7, 1, -1, 8, -8, 9, -9, 3, -3, 1, -1,
972 10, -10, 2, -2, 11, -11, 1, -1, 12, 4, -12, -4, 1, -1, 13, -13,
973 1, -1, 14, -14, 2, 5, 15, -2, -5, -15, -3, 3, 16, -16, 17, 1,
974 -1, -17, 6, 18, -6, -18, 2, -2, 19, -19, 1, -1, 20, -20, 4, -4,
975 7, -7, 21, -21, 1, -1, 2, 3, -3, 22, -2, -22, 8, 23, -8, 1,
976 2, -23, -1, 2, -2, -2, 24, 1, -24, -1, 25, 5, -5, 1, -25, -1,
977 9, -9, 26, 1, -26, 3, 1, -1, 27, -3, -1, -27, 1, 3, -1, -3,
978 28, -4, 4, 10, -10, -28, 1, -1, 1, -1, 29, 6, -29, -6, 30, -4,
979 3, 3, -3, -30, 1, 4, -1, 31, -3, 1, 11, -11, -1, -31, 32, -1,
980 -1, 2, -2, 1, 1, -32, 1, 4, -1, -4, 33, -1, 1, 1, -1, 5,
981 5, -5, -33, -1, -12, 12, -5, -7, 1, 1, 7, 34, 4, -4, -1, 4,
982 -34, -4, 35, 36, -2, -35, -2, -36, 2, 13, 2, -1, 1, -13, 1, -1,
983 37, 1, -5, 6, 5, -1, 38, -6, -8, 5, 8, -1, 1, 1, -37, -1,
984 5, 39, -5, -5, 6, -6, -38, -39, -14, 40, 14, 2, 1, 1, -2, -40,
985 -1, -2, 2, -1, -1, -1, 1, 1, 1, -1, 1, -1, 1, -1, 1, -1}
991 {0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 8, 6, 8, 7,
992 7, 9, 9, 10, 10, 11, 11, 1, 12, 1, 12, 13, 13, 16, 14, 16,
993 14, 15, 15, 17, 17, 18, 0, 18, 19, 20, 21, 19, 22, 21, 20, 22,
994 25, 24, 2, 25, 24, 23, 23, 2, 26, 28, 26, 28, 29, 27, 29, 27,
995 33, 33, 1, 32, 1, 3, 32, 30, 36, 3, 36, 30, 31, 31, 35, 34,
996 37, 41, 34, 35, 37, 4, 41, 4, 49, 8, 8, 49, 40, 38, 5, 38,
997 40, 39, 5, 39, 42, 43, 42, 7, 57, 6, 43, 44, 6, 50, 7, 44,
998 57, 48, 50, 48, 45, 45, 46, 47, 51, 46, 47, 58, 1, 51, 58, 1,
999 52, 59, 53, 9, 52, 55, 55, 59, 53, 56, 54, 56, 54, 9, 64, 64,
1000 60, 63, 60, 63, 61, 62, 61, 62, 2, 10, 2, 10, 11, 1, 11, 13,
1001 12, 1, 12, 13, 16, 16, 8, 8, 14, 3, 3, 15, 14, 15, 4, 4,
1002 1, 17, 17, 5, 1, 7, 7, 5, 6, 1, 2, 2, 6, 22, 1, 25,
1003 21, 22, 8, 24, 1, 21, 25, 24, 8, 18, 18, 23, 9, 20, 23, 33,
1004 29, 33, 20, 1, 19, 1, 29, 36, 9, 36, 19, 41, 28, 57, 32, 3,
1005 28, 3, 1, 27, 49, 49, 1, 32, 26, 26, 2, 4, 4, 7, 57, 41,
1006 2, 7, 10, 5, 37, 16, 10, 27, 8, 8, 13, 16, 37, 13, 1, 5},
1009 {0, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, 1, -1, -1, 1,
1010 -1, 1, -1, 1, -1, 1, -1, 2, 1, -2, -1, 1, -1, 1, 1, -1,
1011 -1, 1, -1, 1, -1, 1, 0, -1, 1, 1, 1, -1, 1, -1, -1, -1,
1012 1, 1, 2, -1, -1, 1, -1, -2, 1, 1, -1, -1, 1, 1, -1, -1,
1013 1, -1, 3, 1, -3, 2, -1, 1, 1, -2, -1, -1, -1, 1, 1, 1,
1014 1, 1, -1, -1, -1, 2, -1, -2, 1, 2, -2, -1, 1, 1, 2, -1,
1015 -1, 1, -2, -1, 1, 1, -1, 2, 1, 2, -1, 1, -2, -1, -2, -1,
1016 -1, 1, 1, -1, 1, -1, 1, 1, 1, -1, -1, 1, 4, -1, -1, -4,
1017 1, 1, 1, 2, -1, -1, 1, -1, -1, 1, -1, -1, 1, -2, 1, -1,
1018 1, 1, -1, -1, 1, 1, -1, -1, 3, 2, -3, -2, 2, 5, -2, 2,
1019 2, -5, -2, -2, -2, 2, -3, 3, 2, 3, -3, 2, -2, -2, 3, -3,
1020 6, 2, -2, 3, -6, 3, -3, -3, 3, 7, -4, 4, -3, 2, -7, 2,
1021 2, -2, -4, 2, 8, -2, -2, -2, 4, 2, -2, 2, 3, 2, -2, -2,
1022 2, 2, -2, -8, -2, 9, -2, 2, -3, -2, 2, -2, 2, 2, 2, 4,
1023 -2, -4, 10, 2, 2, -2, -9, -2, 2, -2, 5, 4, -4, 4, -2, 2,
1024 -5, -4, -3, 4, 2, -3, 3, -2, -5, 5, 3, 3, -2, -3, -10, -4}
1030 {1, 1, 0, 2, 2, 1, 1, 3, 3, 4, 4, 0, 1, 1, 5, 5,
1031 2, 2, 6, 6, 7, 7, 1, 8, 1, 8, 3, 3, 9, 9, 1, 2,
1032 2, 1, 4, 10, 4, 10, 11, 11, 1, 5, 12, 12, 1, 5, 13, 13,
1033 3, 3, 6, 6, 2, 2, 14, 14, 16, 16, 15, 7, 15, 8, 8, 7,
1034 1, 1, 17, 17, 4, 4, 1, 1, 18, 18, 2, 2, 5, 5, 25, 3,
1035 9, 3, 25, 9, 19, 24, 19, 24, 1, 21, 20, 1, 21, 22, 20, 22,
1036 23, 23, 8, 6, 33, 6, 8, 33, 7, 7, 26, 26, 1, 32, 1, 32,
1037 28, 4, 28, 10, 29, 27, 27, 10, 41, 4, 29, 2, 2, 41, 36, 31,
1038 49, 31, 34, 30, 34, 36, 30, 35, 1, 49, 11, 5, 35, 11, 1, 3,
1039 3, 5, 37, 37, 8, 40, 8, 40, 12, 12, 42, 42, 1, 38, 16, 57,
1040 1, 6, 16, 39, 38, 6, 7, 7, 13, 13, 39, 43, 2, 43, 57, 2,
1041 50, 9, 44, 9, 50, 4, 15, 48, 44, 4, 1, 15, 48, 14, 14, 1,
1042 45, 45, 8, 3, 5, 8, 51, 47, 3, 46, 46, 47, 5, 51, 1, 17,
1043 17, 58, 1, 58, 2, 52, 52, 2, 53, 7, 59, 6, 6, 56, 53, 55,
1044 7, 55, 1, 54, 59, 56, 54, 10, 1, 10, 4, 60, 1, 60, 8, 4,
1045 8, 64, 64, 61, 1, 63, 3, 63, 62, 61, 5, 11, 5, 3, 11, 62},
1048 { 1, -1, 0, 1, -1, 2, -2, 1, -1, 1, -1, 0, 3, -3, 1, -1,
1049 2, -2, 1, -1, 1, -1, 4, 1, -4, -1, 2, -2, 1, -1, 5, 3,
1050 -3, -5, 2, 1, -2, -1, 1, -1, 6, 2, 1, -1, -6, -2, 1, -1,
1051 3, -3, 2, -2, 4, -4, 1, -1, 1, -1, 1, 2, -1, 2, -2, -2,
1052 7, -7, 1, -1, 3, -3, 8, -8, 1, -1, 5, -5, 3, -3, 1, 4,
1053 2, -4, -1, -2, 1, 1, -1, -1, 9, 1, 1, -9, -1, 1, -1, -1,
1054 1, -1, 3, -3, 1, 3, -3, -1, 3, -3, 1, -1, 10, 1, -10, -1,
1055 1, 4, -1, 2, 1, -1, 1, -2, 1, -4, -1, 6, -6, -1, 1, 1,
1056 1, -1, 1, 1, -1, -1, -1, 1, 11, -1, -2, 4, -1, 2, -11, 5,
1057 -5, -4, -1, 1, 4, 1, -4, -1, -2, 2, 1, -1, 12, 1, -2, 1,
1058 -12, 4, 2, 1, -1, -4, 4, -4, 2, -2, -1, 1, 7, -1, -1, -7,
1059 -1, -3, 1, 3, 1, 5, 2, 1, -1, -5, 13, -2, -1, 2, -2, -13,
1060 1, -1, 5, 6, 5, -5, 1, 1, -6, 1, -1, -1, -5, -1, 14, 2,
1061 -2, 1, -14, -1, 8, 1, -1, -8, 1, 5, 1, 5, -5, 1, -1, 1,
1062 -5, -1, 15, 1, -1, -1, -1, 3, -15, -3, 6, 1, 16, -1, 6, -6,
1063 -6, 1, -1, 1, -16, 1, 7, -1, 1, -1, -6, -3, 6, -7, 3, -1}
1069 {0, 1, 1, 2, 2, 3, 3, 4, 4, 1, 1, 5, 5, 6, 6, 7,
1070 7, 8, 8, 9, 9, 2, 2, 10, 10, 1, 1, 11, 11, 12, 12, 3,
1071 3, 13, 13, 0, 14, 14, 16, 15, 16, 15, 4, 4, 17, 1, 17, 1,
1072 5, 5, 18, 18, 2, 2, 6, 6, 8, 19, 7, 8, 7, 19, 20, 20,
1073 21, 21, 22, 24, 22, 24, 23, 23, 1, 1, 25, 25, 3, 3, 26, 26,
1074 9, 9, 27, 27, 28, 28, 33, 29, 4, 33, 29, 1, 4, 1, 32, 32,
1075 2, 2, 31, 10, 30, 10, 30, 31, 34, 34, 5, 5, 36, 36, 35, 41,
1076 35, 11, 41, 11, 37, 1, 8, 8, 37, 6, 1, 6, 40, 7, 7, 40,
1077 12, 38, 12, 39, 39, 38, 49, 13, 49, 13, 3, 42, 3, 42, 16, 16,
1078 43, 43, 14, 14, 1, 1, 44, 15, 44, 15, 2, 2, 57, 48, 50, 48,
1079 57, 50, 4, 45, 45, 4, 46, 47, 47, 46, 1, 51, 1, 17, 17, 51,
1080 8, 9, 9, 5, 58, 8, 58, 5, 52, 52, 55, 56, 53, 56, 55, 59,
1081 59, 53, 54, 1, 6, 54, 7, 7, 6, 1, 2, 3, 2, 3, 64, 60,
1082 60, 10, 10, 64, 61, 62, 61, 63, 1, 63, 62, 1, 18, 24, 18, 4,
1083 25, 4, 8, 21, 21, 1, 24, 22, 25, 22, 8, 11, 19, 11, 23, 1,
1084 20, 23, 19, 20, 5, 12, 5, 1, 16, 2, 12, 13, 2, 13, 1, 16},
1087 { 0, 1, -1, 1, -1, 1, -1, 1, -1, 2, -2, 1, -1, 1, -1, 1,
1088 -1, 1, -1, 1, -1, 2, -2, 1, -1, 3, -3, 1, -1, 1, -1, 2,
1089 -2, 1, -1, 0, 1, -1, 1, 1, -1, -1, 2, -2, 1, 4, -1, -4,
1090 2, -2, 1, -1, -3, 3, 2, -2, 2, 1, 2, -2, -2, -1, 1, -1,
1091 1, -1, 1, 1, -1, -1, 1, -1, 5, -5, 1, -1, 3, -3, 1, -1,
1092 2, -2, 1, -1, 1, -1, 1, 1, 3, -1, -1, 6, -3, -6, -1, 1,
1093 4, -4, 1, 2, 1, -2, -1, -1, 1, -1, 3, -3, 1, -1, 1, 1,
1094 -1, 2, -1, -2, 1, 7, -3, 3, -1, 3, -7, -3, 1, -3, 3, -1,
1095 2, 1, -2, 1, -1, -1, 1, 2, -1, -2, -4, -1, 4, 1, 2, -2,
1096 1, -1, -2, 2, 8, -8, -1, 2, 1, -2, -5, 5, 1, -1, -1, 1,
1097 -1, 1, 4, -1, 1, -4, -1, -1, 1, 1, 9, 1, -9, 2, -2, -1,
1098 -4, 3, -3, -4, -1, 4, 1, 4, 1, -1, 1, -1, 1, 1, -1, 1,
1099 -1, -1, -1, 10, 4, 1, 4, -4, -4, -10, 6, 5, -6, -5, 1, -1,
1100 1, 3, -3, -1, 1, -1, -1, -1, 11, 1, 1, -11, -2, -2, 2, 5,
1101 -2, -5, -5, 2, -2, 12, 2, -2, 2, 2, 5, -3, -2, 3, -2, -12,
1102 -2, 2, 2, 2, -5, 3, 5, 13, -3, 7, -3, -3, -7, 3, -13, 3}
1108 {0, 1, 1, 1, 2, 2, 1, 3, 3, 1, 1, 1, 4, 4, 1, 5,
1109 2, 1, 5, 2, 1, 1, 6, 6, 1, 1, 1, 1, 1, 7, 3, 1,
1110 2, 3, 0, 1, 2, 7, 1, 1, 1, 8, 1, 1, 8, 1, 1, 1,
1111 9, 1, 9, 1, 2, 1, 1, 2, 1, 1, 10, 4, 1, 10, 1, 4,
1112 1, 1, 1, 1, 1, 3, 1, 1, 1, 3, 2, 1, 5, 1, 1, 1,
1113 2, 5, 1, 11, 1, 11, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1114 2, 1, 6, 1, 6, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 12,
1115 3, 1, 12, 1, 1, 1, 2, 1, 1, 3, 1, 1, 1, 1, 1, 1,
1116 4, 1, 1, 1, 2, 1, 1, 4, 1, 1, 1, 1, 1, 1, 2, 1,
1117 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 2, 1, 1, 5,
1118 1, 1, 1, 1, 1, 7, 1, 7, 1, 1, 2, 3, 1, 1, 1, 1,
1119 5, 1, 1, 1, 1, 1, 1, 2, 13, 1, 1, 1, 1, 1, 1, 1,
1120 1, 1, 1, 1, 1, 1, 1, 1, 13, 2, 1, 1, 4, 1, 1, 1,
1121 3, 1, 6, 1, 1, 1, 14, 1, 1, 1, 1, 1, 14, 6, 1, 1,
1122 1, 1, 15, 2, 4, 1, 2, 3, 15, 1, 1, 1, 8, 1, 1, 8,
1123 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1},
1126 { 0, 1, -1, 2, 1, -1, -2, 1, -1, 3, -3, 4, 1, -1, -4, 1,
1127 2, 5, -1, -2, -5, 6, 1, -1, -6, 7, -7, 8, -8, 1, 2, 9,
1128 3, -2, 0, -9, -3, -1, 10, -10, 11, 1, -11, 12, -1, -12, 13, -13,
1129 1, 14, -1, -14, 4, 15, -15, -4, 16, -16, 1, 2, 17, -1, -17, -2,
1130 18, -18, 19, -19, 20, 3, -20, 21, -21, -3, 5, 22, 2, -22, -23, 23,
1131 -5, -2, 24, 1, -24, -1, 25, -25, 26, -26, -27, 27, 28, 29, -28, -29,
1132 6, 30, 2, -31, -2, -30, 31, -6, -32, 32, 33, -33, 34, -35, -34, 1,
1133 4, -36, -1, 35, 37, 36, 7, -37, 38, -4, -38, 39, 41, 40, -40, -39,
1134 3, 42, -43, -41, -7, -42, 43, -3, 44, -44, 45, -45, 46, 47, 8, -47,
1135 -48, -46, 50, -50, 48, 49, 51, -49, 52, -52, 5, -51, -8, -53, 53, 3,
1136 -56, 56, 55, 54, -54, 2, 60, -2, -55, 58, 9, -5, 59, 57, -57, -63,
1137 -3, -58, -60, -61, 61, -59, -62, -9, 1, 64, 62, 69, -64, 63, 65, -67,
1138 -68, 66, -65, 68, -66, -69, 67, -70, -1, 10, 71, -71, 4, 73, 72, 70,
1139 6, -76, -3, 74, -78, -74, 1, 78, 80, -72, -75, 76, -1, 3, -73, 79,
1140 75, 77, 1, 11, -4, -79, -10, -6, -1, -77, -83, -80, 2, 81, -84, -2,
1141 83, -81, 82, -82, 84, -87, -86, 85, -11, -85, 86, -89, 87, -88, 88, 89}
1147 {1, 1, 0, 2, 1, 2, 1, 3, 3, 1, 1, 4, 4, 2, 2, 1,
1148 1, 5, 5, 6, 1, 6, 1, 7, 7, 3, 3, 2, 8, 2, 8, 1,
1149 1, 0, 9, 9, 1, 1, 10, 4, 10, 4, 11, 11, 2, 1, 2, 1,
1150 12, 12, 3, 3, 1, 1, 13, 5, 5, 13, 14, 1, 1, 14, 2, 2,
1151 6, 6, 15, 1, 1, 15, 16, 4, 7, 16, 4, 7, 1, 1, 3, 3,
1152 8, 8, 2, 2, 1, 1, 17, 17, 1, 1, 18, 18, 5, 5, 2, 2,
1153 1, 1, 9, 19, 9, 19, 20, 3, 3, 20, 1, 10, 21, 1, 10, 4,
1154 4, 21, 22, 6, 6, 22, 1, 1, 23, 24, 2, 2, 23, 24, 11, 1,
1155 1, 11, 7, 25, 7, 1, 1, 25, 8, 8, 3, 26, 3, 1, 12, 2,
1156 2, 26, 1, 12, 5, 5, 27, 4, 1, 4, 1, 27, 28, 1, 28, 13,
1157 1, 13, 2, 29, 2, 1, 32, 6, 1, 30, 14, 29, 14, 6, 3, 31,
1158 3, 1, 30, 1, 32, 31, 33, 9, 33, 1, 1, 7, 9, 7, 2, 2,
1159 1, 1, 4, 36, 34, 4, 5, 10, 10, 5, 34, 1, 1, 35, 8, 8,
1160 36, 3, 35, 1, 15, 3, 2, 1, 16, 15, 16, 2, 37, 1, 37, 1,
1161 1, 1, 6, 6, 38, 1, 38, 11, 1, 39, 39, 40, 11, 2, 41, 4,
1162 40, 1, 2, 4, 1, 1, 1, 41, 3, 1, 3, 1, 5, 7, 5, 7},
1165 { 1, -1, 0, 1, 2, -1, -2, 1, -1, 3, -3, 1, -1, 2, -2, 4,
1166 -4, 1, -1, 1, 5, -1, -5, 1, -1, 2, -2, 3, 1, -3, -1, 6,
1167 -6, 0, 1, -1, 7, -7, 1, 2, -1, -2, 1, -1, 4, 8, -4, -8,
1168 1, -1, 3, -3, 9, -9, 1, 2, -2, -1, 1, 10, -10, -1, 5, -5,
1169 2, -2, 1, 11, -11, -1, 1, 3, 2, -1, -3, -2, 12, -12, 4, -4,
1170 2, -2, -6, 6, 13, -13, 1, -1, 14, -14, 1, -1, 3, -3, 7, -7,
1171 15, -15, 2, 1, -2, -1, 1, 5, -5, -1, -16, 2, 1, 16, -2, 4,
1172 -4, -1, 1, 3, -3, -1, 17, -17, 1, 1, -8, 8, -1, -1, 2, 18,
1173 -18, -2, 3, 1, -3, 19, -19, -1, 3, -3, 6, 1, -6, 20, 2, 9,
1174 -9, -1, -20, -2, 4, -4, 1, -5, 21, 5, -21, -1, 1, -22, -1, 2,
1175 22, -2, 10, 1, -10, 23, 1, 4, -23, 1, 2, -1, -2, -4, -7, 1,
1176 7, -24, -1, 24, -1, -1, 1, 3, -1, -25, 25, 4, -3, -4, 11, -11,
1177 26, -26, 6, 1, 1, -6, -5, -3, 3, 5, -1, -27, 27, 1, 4, -4,
1178 -1, -8, -1, 28, 2, 8, -12, -28, -2, -2, 2, 12, -1, 29, 1, -29,
1179 30, -30, 5, -5, 1, -31, -1, 3, 31, -1, 1, 1, -3, -13, 1, -7,
1180 -1, -32, 13, 7, 32, 33, -33, -1, -9, -34, 9, 34, -6, 5, 6, -5}
1186 {1, 1, 0, 1, 1, 2, 2, 1, 1, 3, 3, 1, 1, 0, 2, 2,
1187 4, 1, 4, 1, 1, 1, 5, 5, 1, 1, 6, 6, 2, 2, 1, 1,
1188 3, 3, 7, 7, 1, 1, 8, 8, 1, 1, 2, 2, 1, 9, 1, 9,
1189 4, 4, 10, 1, 1, 10, 1, 1, 11, 11, 3, 3, 1, 2, 1, 2,
1190 1, 1, 12, 12, 5, 5, 1, 1, 13, 1, 1, 13, 2, 2, 1, 1,
1191 6, 6, 1, 1, 4, 14, 4, 14, 3, 1, 3, 1, 1, 1, 15, 7,
1192 15, 2, 2, 7, 1, 1, 1, 8, 1, 8, 16, 16, 1, 1, 1, 1,
1193 2, 1, 1, 2, 1, 1, 3, 5, 5, 3, 4, 1, 1, 4, 1, 1,
1194 17, 17, 9, 1, 1, 9, 2, 2, 1, 1, 10, 10, 1, 6, 1, 1,
1195 6, 18, 1, 1, 18, 1, 1, 1, 2, 2, 3, 1, 3, 1, 1, 1,
1196 4, 1, 19, 1, 19, 7, 1, 1, 20, 1, 4, 20, 1, 7, 11, 2,
1197 1, 11, 21, 2, 8, 5, 1, 8, 1, 5, 21, 1, 1, 1, 22, 1,
1198 1, 22, 1, 1, 3, 3, 1, 23, 2, 12, 24, 1, 1, 2, 1, 1,
1199 12, 23, 1, 1, 24, 1, 1, 1, 4, 1, 1, 1, 2, 1, 6, 6,
1200 4, 2, 1, 1, 1, 1, 1, 1, 1, 14, 13, 3, 1, 25, 9, 25,
1201 14, 1, 9, 3, 13, 1, 1, 1, 1, 1, 10, 1, 1, 2, 10, 2},
1204 {-20, -1, 0, 2, -2, 1, -1, 3, -3, 1, -1, 4, -4, 0, 2, -2,
1205 1, 5, -1, -5, 6, -6, 1, -1, 7, -7, 1, -1, 3, -3, 8, -8,
1206 2, -2, 1, -1, 9, -9, 1, -1, 10, -10, 4, -4, 11, 1, -11, -1,
1207 2, -2, 1, 12, -12, -1, 13, -13, 1, -1, 3, -3, 14, 5, -14, -5,
1208 -15, 15, -1, 1, 2, -2, 16, -16, 1, 17, -17, -1, 6, -6, 18, -18,
1209 2, -2, -19, 19, -3, 1, 3, -1, 4, 20, -4, 1, -21, 21, 1, 2,
1210 -1, -7, 7, -2, 22, -22, 23, 2, -23, -2, 1, -1, -24, 24, -25, 25,
1211 -8, -26, 26, 8, -27, 27, 5, 3, -3, -5, -4, 28, -28, 4, 29, -29,
1212 1, -1, -2, -30, 30, 2, 9, -9, -31, 31, 2, -2, -32, 3, 32, -33,
1213 -3, 1, 33, -34, -1, 34, -35, 35, -10, 10, -6, 36, 6, -36, 37, -37,
1214 -5, 38, 1, -38, -1, 3, 39, -39, -1, 40, 5, 1, -40, -3, 2, -11,
1215 -41, -2, 1, 11, -3, -4, 41, 3, 42, 4, -1, -43, -42, 43, 1, -44,
1216 45, -1, 44, -45, -7, 7, -46, 1, -12, 2, 1, -47, 46, 12, 47, 48,
1217 -2, -1, -48, 49, -1, -50, -49, 50, -6, -51, 51, 52, -13, 53, -4, 4,
1218 6, 13, -53, -52, -54, 55, 54, -55, -56, -2, 2, -8, 56, 1, -3, -1,
1219 2, 58, 3, 8, -2, 57, -58, -60, -59, -57, -3, 60, 59, -14, 3, 14}
1225 {1, 1, 0, 2, 2, 1, 1, 3, 3, 4, 4, 5, 5, 1, 1, 6,
1226 6, 2, 2, 7, 7, 8, 8, 1, 1, 3, 3, 9, 9, 10, 10, 1,
1227 1, 2, 2, 4, 4, 11, 0, 11, 12, 12, 13, 13, 1, 1, 5, 5,
1228 14, 14, 15, 16, 15, 16, 3, 3, 1, 6, 1, 6, 2, 2, 7, 7,
1229 8, 8, 17, 17, 1, 1, 4, 4, 18, 18, 2, 2, 1, 19, 1, 20,
1230 19, 20, 21, 21, 3, 3, 22, 22, 5, 5, 24, 1, 1, 23, 9, 23,
1231 24, 9, 2, 2, 10, 1, 1, 10, 6, 6, 25, 4, 4, 25, 7, 7,
1232 26, 8, 1, 8, 3, 1, 26, 3, 11, 11, 27, 27, 2, 28, 1, 2,
1233 28, 1, 12, 12, 5, 5, 29, 13, 13, 29, 32, 1, 1, 33, 31, 30,
1234 32, 4, 30, 33, 4, 31, 3, 14, 1, 1, 3, 34, 34, 2, 2, 14,
1235 6, 6, 35, 36, 35, 36, 1, 15, 1, 16, 16, 15, 7, 9, 7, 9,
1236 37, 8, 8, 37, 1, 1, 39, 2, 38, 39, 2, 40, 5, 38, 40, 5,
1237 3, 3, 4, 4, 10, 10, 1, 1, 1, 1, 41, 2, 41, 2, 6, 6,
1238 1, 1, 11, 42, 11, 43, 3, 42, 3, 17, 4, 43, 1, 17, 7, 1,
1239 8, 44, 4, 7, 44, 5, 8, 2, 5, 1, 2, 48, 45, 1, 12, 45,
1240 12, 48, 13, 13, 1, 9, 9, 46, 1, 46, 47, 47, 49, 18, 18, 49},
1243 { 1, -1, 0, 1, -1, 2, -2, 1, -1, 1, -1, 1, -1, 3, -3, 1,
1244 -1, -2, 2, 1, -1, 1, -1, 4, -4, -2, 2, 1, -1, 1, -1, 5,
1245 -5, -3, 3, 2, -2, 1, 0, -1, 1, -1, 1, -1, 6, -6, 2, -2,
1246 1, -1, 1, 1, -1, -1, -3, 3, 7, 2, -7, -2, -4, 4, 2, -2,
1247 2, -2, 1, -1, 8, -8, 3, -3, 1, -1, -5, 5, 9, 1, -9, 1,
1248 -1, -1, 1, -1, -4, 4, 1, -1, 3, -3, 1, -10, 10, 1, 2, -1,
1249 -1, -2, 6, -6, 2, 11, -11, -2, 3, -3, 1, -4, 4, -1, 3, -3,
1250 1, 3, 12, -3, -5, -12, -1, 5, 2, -2, 1, -1, -7, 1, 13, 7,
1251 -1, -13, 2, -2, 4, -4, 1, 2, -2, -1, 1, 14, -14, 1, 1, 1,
1252 -1, -5, -1, -1, 5, -1, -6, 2, -15, 15, 6, 1, -1, -8, 8, -2,
1253 -4, 4, 1, 1, -1, -1, 16, 2, -16, -2, 2, -2, 4, 3, -4, -3,
1254 -1, -4, 4, 1, -17, 17, -1, -9, 1, 1, 9, 1, -5, -1, -1, 5,
1255 -7, 7, 6, -6, 3, -3, 18, -18, 19, -19, 1, -10, -1, 10, -5, 5,
1256 20, -20, -3, 1, 3, 1, 8, -1, -8, 2, 7, -1, -21, -2, 5, 21,
1257 5, -1, -7, -5, 1, -6, -5, -11, 6, 22, 11, 1, 1, -22, -3, -1,
1258 3, -1, 3, -3, -23, 4, -4, 1, 23, -1, 1, -1, 1, -2, 2, -1}
1264 {1, 1, 1, 1, 0, 2, 2, 1, 1, 3, 3, 0, 1, 1, 2, 2,
1265 4, 4, 1, 1, 5, 5, 1, 1, 2, 2, 3, 3, 6, 6, 1, 1,
1266 7, 7, 8, 1, 8, 2, 2, 1, 4, 4, 1, 3, 1, 3, 9, 9,
1267 2, 2, 1, 5, 1, 5, 10, 10, 1, 1, 11, 11, 3, 6, 3, 4,
1268 4, 6, 2, 2, 1, 12, 1, 12, 7, 13, 7, 13, 1, 1, 8, 8,
1269 2, 2, 14, 14, 16, 15, 16, 5, 5, 1, 3, 15, 1, 3, 4, 4,
1270 1, 1, 17, 17, 2, 2, 6, 6, 1, 18, 1, 18, 22, 21, 22, 21,
1271 25, 24, 25, 19, 9, 20, 9, 23, 19, 24, 20, 3, 23, 7, 3, 1,
1272 1, 7, 28, 26, 29, 5, 28, 26, 5, 8, 29, 4, 8, 27, 2, 2,
1273 4, 27, 1, 1, 10, 36, 10, 33, 33, 36, 30, 1, 32, 32, 1, 30,
1274 6, 31, 31, 35, 3, 6, 11, 11, 3, 2, 35, 2, 34, 1, 34, 1,
1275 37, 37, 12, 7, 12, 5, 41, 5, 4, 7, 1, 8, 13, 4, 1, 41,
1276 13, 38, 8, 38, 9, 1, 40, 40, 9, 1, 39, 2, 2, 49, 39, 42,
1277 3, 3, 14, 16, 49, 14, 16, 42, 43, 43, 6, 6, 15, 1, 1, 15,
1278 44, 44, 1, 1, 50, 48, 4, 5, 4, 7, 5, 2, 10, 10, 48, 7,
1279 50, 45, 2, 1, 45, 8, 8, 1, 46, 46, 3, 47, 47, 3, 1, 1},
1282 { 1, -1, 2, -2, 0, 1, -1, 3, -3, 1, -1, 0, 4, -4, 2, -2,
1283 1, -1, 5, -5, 1, -1, 6, -6, 3, -3, 2, -2, 1, -1, 7, -7,
1284 1, -1, 1, 8, -1, 4, -4, -8, 2, -2, 9, 3, -9, -3, 1, -1,
1285 5, -5, 10, 2, -10, -2, 1, -1, 11, -11, 1, -1, -4, 2, 4, 3,
1286 -3, -2, 6, -6, 12, 1, -12, -1, 2, 1, -2, -1, 13, -13, 2, -2,
1287 7, -7, 1, -1, 1, 1, -1, 3, -3, 14, 5, -1, -14, -5, 4, -4,
1288 15, -15, 1, -1, 8, -8, -3, 3, 16, 1, -16, -1, 1, 1, -1, -1,
1289 1, 1, -1, 1, 2, 1, -2, 1, -1, -1, -1, 6, -1, 3, -6, 17,
1290 -17, -3, 1, 1, 1, 4, -1, -1, -4, 3, -1, 5, -3, -1, -9, 9,
1291 -5, 1, 18, -18, 2, 1, -2, 1, -1, -1, 1, 19, -1, 1, -19, -1,
1292 4, 1, -1, 1, 7, -4, -2, 2, -7, 10, -1, -10, 1, 20, -1, -20,
1293 1, -1, 2, 4, -2, 5, 1, -5, 6, -4, 21, 4, 2, -6, -21, -1,
1294 -2, 1, -4, -1, -3, 22, -1, 1, 3, -22, -1, 11, -11, 1, 1, 1,
1295 8, -8, 2, 2, -1, -2, -2, -1, 1, -1, -5, 5, 2, 23, -23, -2,
1296 1, -1, 24, -24, -1, -1, 7, 6, -7, 5, -6, 12, -3, 3, 1, -5,
1297 1, 1, -12, 25, -1, -5, 5, -25, -1, 1, 9, 1, -1, -9, 26, -26}