2 * common functions for Indeo Video Interactive codecs (Indeo4 and Indeo5)
4 * Copyright (c) 2009 Maxim Poliakovski
6 * This file is part of Libav.
8 * Libav is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU Lesser General Public
10 * License as published by the Free Software Foundation; either
11 * version 2.1 of the License, or (at your option) any later version.
13 * Libav is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * Lesser General Public License for more details.
18 * You should have received a copy of the GNU Lesser General Public
19 * License along with Libav; if not, write to the Free Software
20 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
25 * This file contains functions and data shared by both Indeo4 and
29 #define BITSTREAM_READER_LE
30 #include "libavutil/attributes.h"
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)) {
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 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) {
271 for (b = 0; b < planes[p].num_bands; b++) {
272 band = &planes[p].bands[b];
273 x_tiles = IVI_NUM_TILES(band->width, t_width);
274 y_tiles = IVI_NUM_TILES(band->height, t_height);
275 band->num_tiles = x_tiles * y_tiles;
277 av_freep(&band->tiles);
278 band->tiles = av_mallocz(band->num_tiles * sizeof(IVITile));
280 return AVERROR(ENOMEM);
284 /* use the first luma band as reference for motion vectors
286 ref_tile = planes[0].bands[0].tiles;
288 for (y = 0; y < band->height; y += t_height) {
289 for (x = 0; x < band->width; x += t_width) {
292 tile->mb_size = band->mb_size;
293 tile->width = FFMIN(band->width - x, t_width);
294 tile->height = FFMIN(band->height - y, t_height);
295 tile->is_empty = tile->data_size = 0;
296 /* calculate number of macroblocks */
297 tile->num_MBs = IVI_MBs_PER_TILE(tile->width, tile->height,
300 av_freep(&tile->mbs);
301 tile->mbs = av_malloc(tile->num_MBs * sizeof(IVIMbInfo));
303 return AVERROR(ENOMEM);
307 tile->ref_mbs = ref_tile->mbs;
321 int ff_ivi_dec_tile_data_size(GetBitContext *gb)
327 len = get_bits(gb, 8);
329 len = get_bits_long(gb, 24);
332 /* align the bitstream reader on the byte boundary */
338 int ff_ivi_decode_blocks(GetBitContext *gb, IVIBandDesc *band, IVITile *tile)
340 int mbn, blk, num_blocks, num_coeffs, blk_size, scan_pos, run, val,
341 pos, is_intra, mc_type = 0, mv_x, mv_y, col_mask;
342 uint8_t col_flags[8];
343 int32_t prev_dc, trvec[64];
344 uint32_t cbp, sym, lo, hi, quant, buf_offs, q;
346 RVMapDesc *rvmap = band->rv_map;
347 void (*mc_with_delta_func)(int16_t *buf, const int16_t *ref_buf, uint32_t pitch, int mc_type);
348 void (*mc_no_delta_func) (int16_t *buf, const int16_t *ref_buf, uint32_t pitch, int mc_type);
349 const uint16_t *base_tab;
350 const uint8_t *scale_tab;
352 prev_dc = 0; /* init intra prediction for the DC coefficient */
354 blk_size = band->blk_size;
355 col_mask = blk_size - 1; /* column mask for tracking non-zero coeffs */
356 num_blocks = (band->mb_size != blk_size) ? 4 : 1; /* number of blocks per mb */
357 num_coeffs = blk_size * blk_size;
359 mc_with_delta_func = ff_ivi_mc_8x8_delta;
360 mc_no_delta_func = ff_ivi_mc_8x8_no_delta;
362 mc_with_delta_func = ff_ivi_mc_4x4_delta;
363 mc_no_delta_func = ff_ivi_mc_4x4_no_delta;
366 for (mbn = 0, mb = tile->mbs; mbn < tile->num_MBs; mb++, mbn++) {
367 is_intra = !mb->type;
369 buf_offs = mb->buf_offs;
371 quant = av_clip(band->glob_quant + mb->q_delta, 0, 23);
373 base_tab = is_intra ? band->intra_base : band->inter_base;
374 scale_tab = is_intra ? band->intra_scale : band->inter_scale;
376 quant = scale_tab[quant];
381 if (band->is_halfpel) {
382 mc_type = ((mv_y & 1) << 1) | (mv_x & 1);
384 mv_y >>= 1; /* convert halfpel vectors into fullpel ones */
387 int dmv_x, dmv_y, cx, cy;
389 dmv_x = mb->mv_x >> band->is_halfpel;
390 dmv_y = mb->mv_y >> band->is_halfpel;
391 cx = mb->mv_x & band->is_halfpel;
392 cy = mb->mv_y & band->is_halfpel;
394 if ( mb->xpos + dmv_x < 0
395 || mb->xpos + dmv_x + band->mb_size + cx > band->pitch
396 || mb->ypos + dmv_y < 0
397 || mb->ypos + dmv_y + band->mb_size + cy > band->aheight) {
398 return AVERROR_INVALIDDATA;
403 for (blk = 0; blk < num_blocks; blk++) {
404 /* adjust block position in the buffer according to its number */
406 buf_offs += blk_size;
407 } else if (blk == 2) {
408 buf_offs -= blk_size;
409 buf_offs += blk_size * band->pitch;
412 if (cbp & 1) { /* block coded ? */
414 memset(trvec, 0, num_coeffs*sizeof(trvec[0])); /* zero transform vector */
415 memset(col_flags, 0, sizeof(col_flags)); /* zero column flags */
417 while (scan_pos <= num_coeffs) {
418 sym = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
419 if (sym == rvmap->eob_sym)
420 break; /* End of block */
422 if (sym == rvmap->esc_sym) { /* Escape - run/val explicitly coded using 3 vlc codes */
423 run = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1) + 1;
424 lo = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
425 hi = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
426 val = IVI_TOSIGNED((hi << 6) | lo); /* merge them and convert into signed val */
429 av_log(NULL, AV_LOG_ERROR, "Invalid sym encountered: %d.\n", sym);
432 run = rvmap->runtab[sym];
433 val = rvmap->valtab[sym];
436 /* de-zigzag and dequantize */
438 if (scan_pos >= num_coeffs)
440 pos = band->scan[scan_pos];
443 av_dlog(NULL, "Val = 0 encountered!\n");
445 q = (base_tab[pos] * quant) >> 9;
447 val = val * q + FFSIGN(val) * (((q ^ 1) - 1) >> 1);
449 col_flags[pos & col_mask] |= !!val; /* track columns containing non-zero coeffs */
452 if (scan_pos >= num_coeffs && sym != rvmap->eob_sym)
453 return -1; /* corrupt block data */
455 /* undoing DC coeff prediction for intra-blocks */
456 if (is_intra && band->is_2d_trans) {
459 col_flags[0] |= !!prev_dc;
462 /* apply inverse transform */
463 band->inv_transform(trvec, band->buf + buf_offs,
464 band->pitch, col_flags);
466 /* apply motion compensation */
468 mc_with_delta_func(band->buf + buf_offs,
469 band->ref_buf + buf_offs + mv_y * band->pitch + mv_x,
470 band->pitch, mc_type);
472 /* block not coded */
473 /* for intra blocks apply the dc slant transform */
474 /* for inter - perform the motion compensation without delta */
475 if (is_intra && band->dc_transform) {
476 band->dc_transform(&prev_dc, band->buf + buf_offs,
477 band->pitch, blk_size);
479 mc_no_delta_func(band->buf + buf_offs,
480 band->ref_buf + buf_offs + mv_y * band->pitch + mv_x,
481 band->pitch, mc_type);
494 * Handle empty tiles by performing data copying and motion
495 * compensation respectively.
497 * @param[in] avctx ptr to the AVCodecContext
498 * @param[in] band pointer to the band descriptor
499 * @param[in] tile pointer to the tile descriptor
500 * @param[in] mv_scale scaling factor for motion vectors
502 static int ivi_process_empty_tile(AVCodecContext *avctx, IVIBandDesc *band,
503 IVITile *tile, int32_t mv_scale)
505 int x, y, need_mc, mbn, blk, num_blocks, mv_x, mv_y, mc_type;
506 int offs, mb_offset, row_offset;
507 IVIMbInfo *mb, *ref_mb;
510 void (*mc_no_delta_func)(int16_t *buf, const int16_t *ref_buf, uint32_t pitch,
513 if (tile->num_MBs != IVI_MBs_PER_TILE(tile->width, tile->height, band->mb_size)) {
514 av_log(avctx, AV_LOG_ERROR, "Allocated tile size %d mismatches "
515 "parameters %d in ivi_process_empty_tile()\n",
516 tile->num_MBs, IVI_MBs_PER_TILE(tile->width, tile->height, band->mb_size));
517 return AVERROR_INVALIDDATA;
520 offs = tile->ypos * band->pitch + tile->xpos;
522 ref_mb = tile->ref_mbs;
523 row_offset = band->mb_size * band->pitch;
524 need_mc = 0; /* reset the mc tracking flag */
526 for (y = tile->ypos; y < (tile->ypos + tile->height); y += band->mb_size) {
529 for (x = tile->xpos; x < (tile->xpos + tile->width); x += band->mb_size) {
532 mb->buf_offs = mb_offset;
534 mb->type = 1; /* set the macroblocks type = INTER */
535 mb->cbp = 0; /* all blocks are empty */
537 if (!band->qdelta_present && !band->plane && !band->band_num) {
538 mb->q_delta = band->glob_quant;
543 if (band->inherit_qdelta && ref_mb)
544 mb->q_delta = ref_mb->q_delta;
546 if (band->inherit_mv) {
547 /* motion vector inheritance */
549 mb->mv_x = ivi_scale_mv(ref_mb->mv_x, mv_scale);
550 mb->mv_y = ivi_scale_mv(ref_mb->mv_y, mv_scale);
552 mb->mv_x = ref_mb->mv_x;
553 mb->mv_y = ref_mb->mv_y;
555 need_mc |= mb->mv_x || mb->mv_y; /* tracking non-zero motion vectors */
561 mb_offset += band->mb_size;
566 if (band->inherit_mv && need_mc) { /* apply motion compensation if there is at least one non-zero motion vector */
567 num_blocks = (band->mb_size != band->blk_size) ? 4 : 1; /* number of blocks per mb */
568 mc_no_delta_func = (band->blk_size == 8) ? ff_ivi_mc_8x8_no_delta
569 : ff_ivi_mc_4x4_no_delta;
571 for (mbn = 0, mb = tile->mbs; mbn < tile->num_MBs; mb++, mbn++) {
574 if (!band->is_halfpel) {
575 mc_type = 0; /* we have only fullpel vectors */
577 mc_type = ((mv_y & 1) << 1) | (mv_x & 1);
579 mv_y >>= 1; /* convert halfpel vectors into fullpel ones */
582 for (blk = 0; blk < num_blocks; blk++) {
583 /* adjust block position in the buffer according with its number */
584 offs = mb->buf_offs + band->blk_size * ((blk & 1) + !!(blk & 2) * band->pitch);
585 mc_no_delta_func(band->buf + offs,
586 band->ref_buf + offs + mv_y * band->pitch + mv_x,
587 band->pitch, mc_type);
591 /* copy data from the reference tile into the current one */
592 src = band->ref_buf + tile->ypos * band->pitch + tile->xpos;
593 dst = band->buf + tile->ypos * band->pitch + tile->xpos;
594 for (y = 0; y < tile->height; y++) {
595 memcpy(dst, src, tile->width*sizeof(band->buf[0]));
606 static uint16_t ivi_calc_band_checksum(IVIBandDesc *band)
609 int16_t *src, checksum;
614 for (y = 0; y < band->height; src += band->pitch, y++)
615 for (x = 0; x < band->width; x++)
622 void ff_ivi_output_plane(IVIPlaneDesc *plane, uint8_t *dst, int dst_pitch)
625 const int16_t *src = plane->bands[0].buf;
626 uint32_t pitch = plane->bands[0].pitch;
631 for (y = 0; y < plane->height; y++) {
632 for (x = 0; x < plane->width; x++)
633 dst[x] = av_clip_uint8(src[x] + 128);
640 * Decode an Indeo 4 or 5 band.
642 * @param[in,out] ctx ptr to the decoder context
643 * @param[in,out] band ptr to the band descriptor
644 * @param[in] avctx ptr to the AVCodecContext
645 * @return result code: 0 = OK, -1 = error
647 static int decode_band(IVI45DecContext *ctx,
648 IVIBandDesc *band, AVCodecContext *avctx)
650 int result, i, t, idx1, idx2, pos;
653 band->buf = band->bufs[ctx->dst_buf];
655 av_log(avctx, AV_LOG_ERROR, "Band buffer points to no data!\n");
656 return AVERROR_INVALIDDATA;
658 band->ref_buf = band->bufs[ctx->ref_buf];
659 band->data_ptr = ctx->frame_data + (get_bits_count(&ctx->gb) >> 3);
661 result = ctx->decode_band_hdr(ctx, band, avctx);
663 av_log(avctx, AV_LOG_ERROR, "Error while decoding band header: %d\n",
668 if (band->is_empty) {
669 av_log(avctx, AV_LOG_ERROR, "Empty band encountered!\n");
670 return AVERROR_INVALIDDATA;
673 band->rv_map = &ctx->rvmap_tabs[band->rvmap_sel];
675 /* apply corrections to the selected rvmap table if present */
676 for (i = 0; i < band->num_corr; i++) {
677 idx1 = band->corr[i * 2];
678 idx2 = band->corr[i * 2 + 1];
679 FFSWAP(uint8_t, band->rv_map->runtab[idx1], band->rv_map->runtab[idx2]);
680 FFSWAP(int16_t, band->rv_map->valtab[idx1], band->rv_map->valtab[idx2]);
683 pos = get_bits_count(&ctx->gb);
685 for (t = 0; t < band->num_tiles; t++) {
686 tile = &band->tiles[t];
688 if (tile->mb_size != band->mb_size) {
689 av_log(avctx, AV_LOG_ERROR, "MB sizes mismatch: %d vs. %d\n",
690 band->mb_size, tile->mb_size);
691 return AVERROR_INVALIDDATA;
693 tile->is_empty = get_bits1(&ctx->gb);
694 if (tile->is_empty) {
695 result = ivi_process_empty_tile(avctx, band, tile,
696 (ctx->planes[0].bands[0].mb_size >> 3) - (band->mb_size >> 3));
699 av_dlog(avctx, "Empty tile encountered!\n");
701 tile->data_size = ff_ivi_dec_tile_data_size(&ctx->gb);
702 if (!tile->data_size) {
703 av_log(avctx, AV_LOG_ERROR, "Tile data size is zero!\n");
704 return AVERROR_INVALIDDATA;
707 result = ctx->decode_mb_info(ctx, band, tile, avctx);
711 result = ff_ivi_decode_blocks(&ctx->gb, band, tile);
712 if (result < 0 || ((get_bits_count(&ctx->gb) - pos) >> 3) != tile->data_size) {
713 av_log(avctx, AV_LOG_ERROR, "Corrupted tile data encountered!\n");
717 pos += tile->data_size << 3; // skip to next tile
721 /* restore the selected rvmap table by applying its corrections in reverse order */
722 for (i = band->num_corr-1; i >= 0; i--) {
723 idx1 = band->corr[i*2];
724 idx2 = band->corr[i*2+1];
725 FFSWAP(uint8_t, band->rv_map->runtab[idx1], band->rv_map->runtab[idx2]);
726 FFSWAP(int16_t, band->rv_map->valtab[idx1], band->rv_map->valtab[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);
759 av_log(avctx, AV_LOG_ERROR,
760 "Error while decoding picture header: %d\n", result);
763 if (ctx->gop_invalid)
764 return AVERROR_INVALIDDATA;
766 if (ctx->gop_flags & IVI5_IS_PROTECTED) {
767 av_log(avctx, AV_LOG_ERROR, "Password-protected clip!\n");
771 ctx->switch_buffers(ctx);
775 if (ctx->is_nonnull_frame(ctx)) {
776 for (p = 0; p < 3; p++) {
777 for (b = 0; b < ctx->planes[p].num_bands; b++) {
778 result = decode_band(ctx, &ctx->planes[p].bands[b], avctx);
780 av_log(avctx, AV_LOG_ERROR,
781 "Error while decoding band: %d, plane: %d\n", b, p);
788 //STOP_TIMER("decode_planes"); }
790 /* If the bidirectional mode is enabled, next I and the following P frame will */
791 /* be sent together. Unfortunately the approach below seems to be the only way */
792 /* to handle the B-frames mode. That's exactly the same Intel decoders do. */
793 if (avctx->codec_id == AV_CODEC_ID_INDEO4 && ctx->frame_type == 0/*FRAMETYPE_INTRA*/) {
794 while (get_bits(&ctx->gb, 8)); // skip version string
795 skip_bits_long(&ctx->gb, 64); // skip padding, TODO: implement correct 8-bytes alignment
796 if (get_bits_left(&ctx->gb) > 18 && show_bits(&ctx->gb, 18) == 0x3FFF8)
797 av_log(avctx, AV_LOG_ERROR, "Buffer contains IP frames!\n");
800 if (ctx->frame.data[0])
801 avctx->release_buffer(avctx, &ctx->frame);
803 ctx->frame.reference = 0;
804 avcodec_set_dimensions(avctx, ctx->planes[0].width, ctx->planes[0].height);
805 if ((result = avctx->get_buffer(avctx, &ctx->frame)) < 0) {
806 av_log(avctx, AV_LOG_ERROR, "get_buffer() failed\n");
810 if (ctx->is_scalable) {
811 if (avctx->codec_id == AV_CODEC_ID_INDEO4)
812 ff_ivi_recompose_haar(&ctx->planes[0], ctx->frame.data[0], ctx->frame.linesize[0]);
814 ff_ivi_recompose53 (&ctx->planes[0], ctx->frame.data[0], ctx->frame.linesize[0]);
816 ff_ivi_output_plane(&ctx->planes[0], ctx->frame.data[0], ctx->frame.linesize[0]);
819 ff_ivi_output_plane(&ctx->planes[2], ctx->frame.data[1], ctx->frame.linesize[1]);
820 ff_ivi_output_plane(&ctx->planes[1], ctx->frame.data[2], ctx->frame.linesize[2]);
822 *data_size = sizeof(AVFrame);
823 *(AVFrame*)data = ctx->frame;
829 * Close Indeo5 decoder and clean up its context.
831 av_cold int ff_ivi_decode_close(AVCodecContext *avctx)
833 IVI45DecContext *ctx = avctx->priv_data;
835 ff_ivi_free_buffers(&ctx->planes[0]);
837 if (ctx->mb_vlc.cust_tab.table)
838 ff_free_vlc(&ctx->mb_vlc.cust_tab);
840 if (ctx->frame.data[0])
841 avctx->release_buffer(avctx, &ctx->frame);
843 #if IVI4_STREAM_ANALYSER
844 if (avctx->codec_id == AV_CODEC_ID_INDEO4) {
845 if (ctx->is_scalable)
846 av_log(avctx, AV_LOG_ERROR, "This video uses scalability mode!\n");
847 if (ctx->uses_tiling)
848 av_log(avctx, AV_LOG_ERROR, "This video uses local decoding!\n");
849 if (ctx->has_b_frames)
850 av_log(avctx, AV_LOG_ERROR, "This video contains B-frames!\n");
852 av_log(avctx, AV_LOG_ERROR, "Transparency mode is enabled!\n");
854 av_log(avctx, AV_LOG_ERROR, "This video uses Haar transform!\n");
855 if (ctx->uses_fullpel)
856 av_log(avctx, AV_LOG_ERROR, "This video uses fullpel motion vectors!\n");
865 * These are 2x8 predefined Huffman codebooks for coding macroblock/block
866 * signals. They are specified using "huffman descriptors" in order to
867 * avoid huge static tables. The decoding tables will be generated at
868 * startup from these descriptors.
870 const IVIHuffDesc ff_ivi_mb_huff_desc[8] = {
871 {8, {0, 4, 5, 4, 4, 4, 6, 6}},
872 {12, {0, 2, 2, 3, 3, 3, 3, 5, 3, 2, 2, 2}},
873 {12, {0, 2, 3, 4, 3, 3, 3, 3, 4, 3, 2, 2}},
874 {12, {0, 3, 4, 4, 3, 3, 3, 3, 3, 2, 2, 2}},
875 {13, {0, 4, 4, 3, 3, 3, 3, 2, 3, 3, 2, 1, 1}},
876 {9, {0, 4, 4, 4, 4, 3, 3, 3, 2}},
877 {10, {0, 4, 4, 4, 4, 3, 3, 2, 2, 2}},
878 {12, {0, 4, 4, 4, 3, 3, 2, 3, 2, 2, 2, 2}}
881 const IVIHuffDesc ff_ivi_blk_huff_desc[8] = {
882 {10, {1, 2, 3, 4, 4, 7, 5, 5, 4, 1}},
883 {11, {2, 3, 4, 4, 4, 7, 5, 4, 3, 3, 2}},
884 {12, {2, 4, 5, 5, 5, 5, 6, 4, 4, 3, 1, 1}},
885 {13, {3, 3, 4, 4, 5, 6, 6, 4, 4, 3, 2, 1, 1}},
886 {11, {3, 4, 4, 5, 5, 5, 6, 5, 4, 2, 2}},
887 {13, {3, 4, 5, 5, 5, 5, 6, 4, 3, 3, 2, 1, 1}},
888 {13, {3, 4, 5, 5, 5, 6, 5, 4, 3, 3, 2, 1, 1}},
889 {9, {3, 4, 4, 5, 5, 5, 6, 5, 5}}
894 * Scan patterns shared between indeo4 and indeo5
896 const uint8_t ff_ivi_vertical_scan_8x8[64] = {
897 0, 8, 16, 24, 32, 40, 48, 56,
898 1, 9, 17, 25, 33, 41, 49, 57,
899 2, 10, 18, 26, 34, 42, 50, 58,
900 3, 11, 19, 27, 35, 43, 51, 59,
901 4, 12, 20, 28, 36, 44, 52, 60,
902 5, 13, 21, 29, 37, 45, 53, 61,
903 6, 14, 22, 30, 38, 46, 54, 62,
904 7, 15, 23, 31, 39, 47, 55, 63
907 const uint8_t ff_ivi_horizontal_scan_8x8[64] = {
908 0, 1, 2, 3, 4, 5, 6, 7,
909 8, 9, 10, 11, 12, 13, 14, 15,
910 16, 17, 18, 19, 20, 21, 22, 23,
911 24, 25, 26, 27, 28, 29, 30, 31,
912 32, 33, 34, 35, 36, 37, 38, 39,
913 40, 41, 42, 43, 44, 45, 46, 47,
914 48, 49, 50, 51, 52, 53, 54, 55,
915 56, 57, 58, 59, 60, 61, 62, 63
918 const uint8_t ff_ivi_direct_scan_4x4[16] = {
919 0, 1, 4, 8, 5, 2, 3, 6, 9, 12, 13, 10, 7, 11, 14, 15
924 * Run-value (RLE) tables.
926 const RVMapDesc ff_ivi_rvmap_tabs[9] = {
931 {1, 1, 0, 1, 1, 0, 1, 1, 2, 2, 1, 1, 1, 1, 3, 3,
932 1, 1, 2, 2, 1, 1, 4, 4, 1, 1, 1, 1, 2, 2, 5, 5,
933 1, 1, 3, 3, 1, 1, 6, 6, 1, 2, 1, 2, 7, 7, 1, 1,
934 8, 8, 1, 1, 4, 2, 1, 4, 2, 1, 3, 3, 1, 1, 1, 9,
935 9, 1, 2, 1, 2, 1, 5, 5, 1, 1, 10, 10, 1, 1, 3, 3,
936 2, 2, 1, 1, 11, 11, 6, 4, 4, 1, 6, 1, 2, 1, 2, 12,
937 8, 1, 12, 7, 8, 7, 1, 16, 1, 16, 1, 3, 3, 13, 1, 13,
938 2, 2, 1, 15, 1, 5, 14, 15, 1, 5, 14, 1, 17, 8, 17, 8,
939 1, 4, 4, 2, 2, 1, 25, 25, 24, 24, 1, 3, 1, 3, 1, 8,
940 6, 7, 6, 1, 18, 8, 18, 1, 7, 23, 2, 2, 23, 1, 1, 21,
941 22, 9, 9, 22, 19, 1, 21, 5, 19, 5, 1, 33, 20, 33, 20, 8,
942 4, 4, 1, 32, 2, 2, 8, 3, 32, 26, 3, 1, 7, 7, 26, 6,
943 1, 6, 1, 1, 16, 1, 10, 1, 10, 2, 16, 29, 28, 2, 29, 28,
944 1, 27, 5, 8, 5, 27, 1, 8, 3, 7, 3, 31, 41, 31, 1, 41,
945 6, 1, 6, 7, 4, 4, 1, 1, 2, 1, 2, 11, 34, 30, 11, 1,
946 30, 15, 15, 34, 36, 40, 36, 40, 35, 35, 37, 37, 39, 39, 38, 38},
949 { 1, -1, 0, 2, -2, 0, 3, -3, 1, -1, 4, -4, 5, -5, 1, -1,
950 6, -6, 2, -2, 7, -7, 1, -1, 8, -8, 9, -9, 3, -3, 1, -1,
951 10, -10, 2, -2, 11, -11, 1, -1, 12, 4, -12, -4, 1, -1, 13, -13,
952 1, -1, 14, -14, 2, 5, 15, -2, -5, -15, -3, 3, 16, -16, 17, 1,
953 -1, -17, 6, 18, -6, -18, 2, -2, 19, -19, 1, -1, 20, -20, 4, -4,
954 7, -7, 21, -21, 1, -1, 2, 3, -3, 22, -2, -22, 8, 23, -8, 1,
955 2, -23, -1, 2, -2, -2, 24, 1, -24, -1, 25, 5, -5, 1, -25, -1,
956 9, -9, 26, 1, -26, 3, 1, -1, 27, -3, -1, -27, 1, 3, -1, -3,
957 28, -4, 4, 10, -10, -28, 1, -1, 1, -1, 29, 6, -29, -6, 30, -4,
958 3, 3, -3, -30, 1, 4, -1, 31, -3, 1, 11, -11, -1, -31, 32, -1,
959 -1, 2, -2, 1, 1, -32, 1, 4, -1, -4, 33, -1, 1, 1, -1, 5,
960 5, -5, -33, -1, -12, 12, -5, -7, 1, 1, 7, 34, 4, -4, -1, 4,
961 -34, -4, 35, 36, -2, -35, -2, -36, 2, 13, 2, -1, 1, -13, 1, -1,
962 37, 1, -5, 6, 5, -1, 38, -6, -8, 5, 8, -1, 1, 1, -37, -1,
963 5, 39, -5, -5, 6, -6, -38, -39, -14, 40, 14, 2, 1, 1, -2, -40,
964 -1, -2, 2, -1, -1, -1, 1, 1, 1, -1, 1, -1, 1, -1, 1, -1}
970 {0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 8, 6, 8, 7,
971 7, 9, 9, 10, 10, 11, 11, 1, 12, 1, 12, 13, 13, 16, 14, 16,
972 14, 15, 15, 17, 17, 18, 0, 18, 19, 20, 21, 19, 22, 21, 20, 22,
973 25, 24, 2, 25, 24, 23, 23, 2, 26, 28, 26, 28, 29, 27, 29, 27,
974 33, 33, 1, 32, 1, 3, 32, 30, 36, 3, 36, 30, 31, 31, 35, 34,
975 37, 41, 34, 35, 37, 4, 41, 4, 49, 8, 8, 49, 40, 38, 5, 38,
976 40, 39, 5, 39, 42, 43, 42, 7, 57, 6, 43, 44, 6, 50, 7, 44,
977 57, 48, 50, 48, 45, 45, 46, 47, 51, 46, 47, 58, 1, 51, 58, 1,
978 52, 59, 53, 9, 52, 55, 55, 59, 53, 56, 54, 56, 54, 9, 64, 64,
979 60, 63, 60, 63, 61, 62, 61, 62, 2, 10, 2, 10, 11, 1, 11, 13,
980 12, 1, 12, 13, 16, 16, 8, 8, 14, 3, 3, 15, 14, 15, 4, 4,
981 1, 17, 17, 5, 1, 7, 7, 5, 6, 1, 2, 2, 6, 22, 1, 25,
982 21, 22, 8, 24, 1, 21, 25, 24, 8, 18, 18, 23, 9, 20, 23, 33,
983 29, 33, 20, 1, 19, 1, 29, 36, 9, 36, 19, 41, 28, 57, 32, 3,
984 28, 3, 1, 27, 49, 49, 1, 32, 26, 26, 2, 4, 4, 7, 57, 41,
985 2, 7, 10, 5, 37, 16, 10, 27, 8, 8, 13, 16, 37, 13, 1, 5},
988 {0, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, 1, -1, -1, 1,
989 -1, 1, -1, 1, -1, 1, -1, 2, 1, -2, -1, 1, -1, 1, 1, -1,
990 -1, 1, -1, 1, -1, 1, 0, -1, 1, 1, 1, -1, 1, -1, -1, -1,
991 1, 1, 2, -1, -1, 1, -1, -2, 1, 1, -1, -1, 1, 1, -1, -1,
992 1, -1, 3, 1, -3, 2, -1, 1, 1, -2, -1, -1, -1, 1, 1, 1,
993 1, 1, -1, -1, -1, 2, -1, -2, 1, 2, -2, -1, 1, 1, 2, -1,
994 -1, 1, -2, -1, 1, 1, -1, 2, 1, 2, -1, 1, -2, -1, -2, -1,
995 -1, 1, 1, -1, 1, -1, 1, 1, 1, -1, -1, 1, 4, -1, -1, -4,
996 1, 1, 1, 2, -1, -1, 1, -1, -1, 1, -1, -1, 1, -2, 1, -1,
997 1, 1, -1, -1, 1, 1, -1, -1, 3, 2, -3, -2, 2, 5, -2, 2,
998 2, -5, -2, -2, -2, 2, -3, 3, 2, 3, -3, 2, -2, -2, 3, -3,
999 6, 2, -2, 3, -6, 3, -3, -3, 3, 7, -4, 4, -3, 2, -7, 2,
1000 2, -2, -4, 2, 8, -2, -2, -2, 4, 2, -2, 2, 3, 2, -2, -2,
1001 2, 2, -2, -8, -2, 9, -2, 2, -3, -2, 2, -2, 2, 2, 2, 4,
1002 -2, -4, 10, 2, 2, -2, -9, -2, 2, -2, 5, 4, -4, 4, -2, 2,
1003 -5, -4, -3, 4, 2, -3, 3, -2, -5, 5, 3, 3, -2, -3, -10, -4}
1009 {1, 1, 0, 2, 2, 1, 1, 3, 3, 4, 4, 0, 1, 1, 5, 5,
1010 2, 2, 6, 6, 7, 7, 1, 8, 1, 8, 3, 3, 9, 9, 1, 2,
1011 2, 1, 4, 10, 4, 10, 11, 11, 1, 5, 12, 12, 1, 5, 13, 13,
1012 3, 3, 6, 6, 2, 2, 14, 14, 16, 16, 15, 7, 15, 8, 8, 7,
1013 1, 1, 17, 17, 4, 4, 1, 1, 18, 18, 2, 2, 5, 5, 25, 3,
1014 9, 3, 25, 9, 19, 24, 19, 24, 1, 21, 20, 1, 21, 22, 20, 22,
1015 23, 23, 8, 6, 33, 6, 8, 33, 7, 7, 26, 26, 1, 32, 1, 32,
1016 28, 4, 28, 10, 29, 27, 27, 10, 41, 4, 29, 2, 2, 41, 36, 31,
1017 49, 31, 34, 30, 34, 36, 30, 35, 1, 49, 11, 5, 35, 11, 1, 3,
1018 3, 5, 37, 37, 8, 40, 8, 40, 12, 12, 42, 42, 1, 38, 16, 57,
1019 1, 6, 16, 39, 38, 6, 7, 7, 13, 13, 39, 43, 2, 43, 57, 2,
1020 50, 9, 44, 9, 50, 4, 15, 48, 44, 4, 1, 15, 48, 14, 14, 1,
1021 45, 45, 8, 3, 5, 8, 51, 47, 3, 46, 46, 47, 5, 51, 1, 17,
1022 17, 58, 1, 58, 2, 52, 52, 2, 53, 7, 59, 6, 6, 56, 53, 55,
1023 7, 55, 1, 54, 59, 56, 54, 10, 1, 10, 4, 60, 1, 60, 8, 4,
1024 8, 64, 64, 61, 1, 63, 3, 63, 62, 61, 5, 11, 5, 3, 11, 62},
1027 { 1, -1, 0, 1, -1, 2, -2, 1, -1, 1, -1, 0, 3, -3, 1, -1,
1028 2, -2, 1, -1, 1, -1, 4, 1, -4, -1, 2, -2, 1, -1, 5, 3,
1029 -3, -5, 2, 1, -2, -1, 1, -1, 6, 2, 1, -1, -6, -2, 1, -1,
1030 3, -3, 2, -2, 4, -4, 1, -1, 1, -1, 1, 2, -1, 2, -2, -2,
1031 7, -7, 1, -1, 3, -3, 8, -8, 1, -1, 5, -5, 3, -3, 1, 4,
1032 2, -4, -1, -2, 1, 1, -1, -1, 9, 1, 1, -9, -1, 1, -1, -1,
1033 1, -1, 3, -3, 1, 3, -3, -1, 3, -3, 1, -1, 10, 1, -10, -1,
1034 1, 4, -1, 2, 1, -1, 1, -2, 1, -4, -1, 6, -6, -1, 1, 1,
1035 1, -1, 1, 1, -1, -1, -1, 1, 11, -1, -2, 4, -1, 2, -11, 5,
1036 -5, -4, -1, 1, 4, 1, -4, -1, -2, 2, 1, -1, 12, 1, -2, 1,
1037 -12, 4, 2, 1, -1, -4, 4, -4, 2, -2, -1, 1, 7, -1, -1, -7,
1038 -1, -3, 1, 3, 1, 5, 2, 1, -1, -5, 13, -2, -1, 2, -2, -13,
1039 1, -1, 5, 6, 5, -5, 1, 1, -6, 1, -1, -1, -5, -1, 14, 2,
1040 -2, 1, -14, -1, 8, 1, -1, -8, 1, 5, 1, 5, -5, 1, -1, 1,
1041 -5, -1, 15, 1, -1, -1, -1, 3, -15, -3, 6, 1, 16, -1, 6, -6,
1042 -6, 1, -1, 1, -16, 1, 7, -1, 1, -1, -6, -3, 6, -7, 3, -1}
1048 {0, 1, 1, 2, 2, 3, 3, 4, 4, 1, 1, 5, 5, 6, 6, 7,
1049 7, 8, 8, 9, 9, 2, 2, 10, 10, 1, 1, 11, 11, 12, 12, 3,
1050 3, 13, 13, 0, 14, 14, 16, 15, 16, 15, 4, 4, 17, 1, 17, 1,
1051 5, 5, 18, 18, 2, 2, 6, 6, 8, 19, 7, 8, 7, 19, 20, 20,
1052 21, 21, 22, 24, 22, 24, 23, 23, 1, 1, 25, 25, 3, 3, 26, 26,
1053 9, 9, 27, 27, 28, 28, 33, 29, 4, 33, 29, 1, 4, 1, 32, 32,
1054 2, 2, 31, 10, 30, 10, 30, 31, 34, 34, 5, 5, 36, 36, 35, 41,
1055 35, 11, 41, 11, 37, 1, 8, 8, 37, 6, 1, 6, 40, 7, 7, 40,
1056 12, 38, 12, 39, 39, 38, 49, 13, 49, 13, 3, 42, 3, 42, 16, 16,
1057 43, 43, 14, 14, 1, 1, 44, 15, 44, 15, 2, 2, 57, 48, 50, 48,
1058 57, 50, 4, 45, 45, 4, 46, 47, 47, 46, 1, 51, 1, 17, 17, 51,
1059 8, 9, 9, 5, 58, 8, 58, 5, 52, 52, 55, 56, 53, 56, 55, 59,
1060 59, 53, 54, 1, 6, 54, 7, 7, 6, 1, 2, 3, 2, 3, 64, 60,
1061 60, 10, 10, 64, 61, 62, 61, 63, 1, 63, 62, 1, 18, 24, 18, 4,
1062 25, 4, 8, 21, 21, 1, 24, 22, 25, 22, 8, 11, 19, 11, 23, 1,
1063 20, 23, 19, 20, 5, 12, 5, 1, 16, 2, 12, 13, 2, 13, 1, 16},
1066 { 0, 1, -1, 1, -1, 1, -1, 1, -1, 2, -2, 1, -1, 1, -1, 1,
1067 -1, 1, -1, 1, -1, 2, -2, 1, -1, 3, -3, 1, -1, 1, -1, 2,
1068 -2, 1, -1, 0, 1, -1, 1, 1, -1, -1, 2, -2, 1, 4, -1, -4,
1069 2, -2, 1, -1, -3, 3, 2, -2, 2, 1, 2, -2, -2, -1, 1, -1,
1070 1, -1, 1, 1, -1, -1, 1, -1, 5, -5, 1, -1, 3, -3, 1, -1,
1071 2, -2, 1, -1, 1, -1, 1, 1, 3, -1, -1, 6, -3, -6, -1, 1,
1072 4, -4, 1, 2, 1, -2, -1, -1, 1, -1, 3, -3, 1, -1, 1, 1,
1073 -1, 2, -1, -2, 1, 7, -3, 3, -1, 3, -7, -3, 1, -3, 3, -1,
1074 2, 1, -2, 1, -1, -1, 1, 2, -1, -2, -4, -1, 4, 1, 2, -2,
1075 1, -1, -2, 2, 8, -8, -1, 2, 1, -2, -5, 5, 1, -1, -1, 1,
1076 -1, 1, 4, -1, 1, -4, -1, -1, 1, 1, 9, 1, -9, 2, -2, -1,
1077 -4, 3, -3, -4, -1, 4, 1, 4, 1, -1, 1, -1, 1, 1, -1, 1,
1078 -1, -1, -1, 10, 4, 1, 4, -4, -4, -10, 6, 5, -6, -5, 1, -1,
1079 1, 3, -3, -1, 1, -1, -1, -1, 11, 1, 1, -11, -2, -2, 2, 5,
1080 -2, -5, -5, 2, -2, 12, 2, -2, 2, 2, 5, -3, -2, 3, -2, -12,
1081 -2, 2, 2, 2, -5, 3, 5, 13, -3, 7, -3, -3, -7, 3, -13, 3}
1087 {0, 1, 1, 1, 2, 2, 1, 3, 3, 1, 1, 1, 4, 4, 1, 5,
1088 2, 1, 5, 2, 1, 1, 6, 6, 1, 1, 1, 1, 1, 7, 3, 1,
1089 2, 3, 0, 1, 2, 7, 1, 1, 1, 8, 1, 1, 8, 1, 1, 1,
1090 9, 1, 9, 1, 2, 1, 1, 2, 1, 1, 10, 4, 1, 10, 1, 4,
1091 1, 1, 1, 1, 1, 3, 1, 1, 1, 3, 2, 1, 5, 1, 1, 1,
1092 2, 5, 1, 11, 1, 11, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1093 2, 1, 6, 1, 6, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 12,
1094 3, 1, 12, 1, 1, 1, 2, 1, 1, 3, 1, 1, 1, 1, 1, 1,
1095 4, 1, 1, 1, 2, 1, 1, 4, 1, 1, 1, 1, 1, 1, 2, 1,
1096 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 2, 1, 1, 5,
1097 1, 1, 1, 1, 1, 7, 1, 7, 1, 1, 2, 3, 1, 1, 1, 1,
1098 5, 1, 1, 1, 1, 1, 1, 2, 13, 1, 1, 1, 1, 1, 1, 1,
1099 1, 1, 1, 1, 1, 1, 1, 1, 13, 2, 1, 1, 4, 1, 1, 1,
1100 3, 1, 6, 1, 1, 1, 14, 1, 1, 1, 1, 1, 14, 6, 1, 1,
1101 1, 1, 15, 2, 4, 1, 2, 3, 15, 1, 1, 1, 8, 1, 1, 8,
1102 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1},
1105 { 0, 1, -1, 2, 1, -1, -2, 1, -1, 3, -3, 4, 1, -1, -4, 1,
1106 2, 5, -1, -2, -5, 6, 1, -1, -6, 7, -7, 8, -8, 1, 2, 9,
1107 3, -2, 0, -9, -3, -1, 10, -10, 11, 1, -11, 12, -1, -12, 13, -13,
1108 1, 14, -1, -14, 4, 15, -15, -4, 16, -16, 1, 2, 17, -1, -17, -2,
1109 18, -18, 19, -19, 20, 3, -20, 21, -21, -3, 5, 22, 2, -22, -23, 23,
1110 -5, -2, 24, 1, -24, -1, 25, -25, 26, -26, -27, 27, 28, 29, -28, -29,
1111 6, 30, 2, -31, -2, -30, 31, -6, -32, 32, 33, -33, 34, -35, -34, 1,
1112 4, -36, -1, 35, 37, 36, 7, -37, 38, -4, -38, 39, 41, 40, -40, -39,
1113 3, 42, -43, -41, -7, -42, 43, -3, 44, -44, 45, -45, 46, 47, 8, -47,
1114 -48, -46, 50, -50, 48, 49, 51, -49, 52, -52, 5, -51, -8, -53, 53, 3,
1115 -56, 56, 55, 54, -54, 2, 60, -2, -55, 58, 9, -5, 59, 57, -57, -63,
1116 -3, -58, -60, -61, 61, -59, -62, -9, 1, 64, 62, 69, -64, 63, 65, -67,
1117 -68, 66, -65, 68, -66, -69, 67, -70, -1, 10, 71, -71, 4, 73, 72, 70,
1118 6, -76, -3, 74, -78, -74, 1, 78, 80, -72, -75, 76, -1, 3, -73, 79,
1119 75, 77, 1, 11, -4, -79, -10, -6, -1, -77, -83, -80, 2, 81, -84, -2,
1120 83, -81, 82, -82, 84, -87, -86, 85, -11, -85, 86, -89, 87, -88, 88, 89}
1126 {1, 1, 0, 2, 1, 2, 1, 3, 3, 1, 1, 4, 4, 2, 2, 1,
1127 1, 5, 5, 6, 1, 6, 1, 7, 7, 3, 3, 2, 8, 2, 8, 1,
1128 1, 0, 9, 9, 1, 1, 10, 4, 10, 4, 11, 11, 2, 1, 2, 1,
1129 12, 12, 3, 3, 1, 1, 13, 5, 5, 13, 14, 1, 1, 14, 2, 2,
1130 6, 6, 15, 1, 1, 15, 16, 4, 7, 16, 4, 7, 1, 1, 3, 3,
1131 8, 8, 2, 2, 1, 1, 17, 17, 1, 1, 18, 18, 5, 5, 2, 2,
1132 1, 1, 9, 19, 9, 19, 20, 3, 3, 20, 1, 10, 21, 1, 10, 4,
1133 4, 21, 22, 6, 6, 22, 1, 1, 23, 24, 2, 2, 23, 24, 11, 1,
1134 1, 11, 7, 25, 7, 1, 1, 25, 8, 8, 3, 26, 3, 1, 12, 2,
1135 2, 26, 1, 12, 5, 5, 27, 4, 1, 4, 1, 27, 28, 1, 28, 13,
1136 1, 13, 2, 29, 2, 1, 32, 6, 1, 30, 14, 29, 14, 6, 3, 31,
1137 3, 1, 30, 1, 32, 31, 33, 9, 33, 1, 1, 7, 9, 7, 2, 2,
1138 1, 1, 4, 36, 34, 4, 5, 10, 10, 5, 34, 1, 1, 35, 8, 8,
1139 36, 3, 35, 1, 15, 3, 2, 1, 16, 15, 16, 2, 37, 1, 37, 1,
1140 1, 1, 6, 6, 38, 1, 38, 11, 1, 39, 39, 40, 11, 2, 41, 4,
1141 40, 1, 2, 4, 1, 1, 1, 41, 3, 1, 3, 1, 5, 7, 5, 7},
1144 { 1, -1, 0, 1, 2, -1, -2, 1, -1, 3, -3, 1, -1, 2, -2, 4,
1145 -4, 1, -1, 1, 5, -1, -5, 1, -1, 2, -2, 3, 1, -3, -1, 6,
1146 -6, 0, 1, -1, 7, -7, 1, 2, -1, -2, 1, -1, 4, 8, -4, -8,
1147 1, -1, 3, -3, 9, -9, 1, 2, -2, -1, 1, 10, -10, -1, 5, -5,
1148 2, -2, 1, 11, -11, -1, 1, 3, 2, -1, -3, -2, 12, -12, 4, -4,
1149 2, -2, -6, 6, 13, -13, 1, -1, 14, -14, 1, -1, 3, -3, 7, -7,
1150 15, -15, 2, 1, -2, -1, 1, 5, -5, -1, -16, 2, 1, 16, -2, 4,
1151 -4, -1, 1, 3, -3, -1, 17, -17, 1, 1, -8, 8, -1, -1, 2, 18,
1152 -18, -2, 3, 1, -3, 19, -19, -1, 3, -3, 6, 1, -6, 20, 2, 9,
1153 -9, -1, -20, -2, 4, -4, 1, -5, 21, 5, -21, -1, 1, -22, -1, 2,
1154 22, -2, 10, 1, -10, 23, 1, 4, -23, 1, 2, -1, -2, -4, -7, 1,
1155 7, -24, -1, 24, -1, -1, 1, 3, -1, -25, 25, 4, -3, -4, 11, -11,
1156 26, -26, 6, 1, 1, -6, -5, -3, 3, 5, -1, -27, 27, 1, 4, -4,
1157 -1, -8, -1, 28, 2, 8, -12, -28, -2, -2, 2, 12, -1, 29, 1, -29,
1158 30, -30, 5, -5, 1, -31, -1, 3, 31, -1, 1, 1, -3, -13, 1, -7,
1159 -1, -32, 13, 7, 32, 33, -33, -1, -9, -34, 9, 34, -6, 5, 6, -5}
1165 {1, 1, 0, 1, 1, 2, 2, 1, 1, 3, 3, 1, 1, 0, 2, 2,
1166 4, 1, 4, 1, 1, 1, 5, 5, 1, 1, 6, 6, 2, 2, 1, 1,
1167 3, 3, 7, 7, 1, 1, 8, 8, 1, 1, 2, 2, 1, 9, 1, 9,
1168 4, 4, 10, 1, 1, 10, 1, 1, 11, 11, 3, 3, 1, 2, 1, 2,
1169 1, 1, 12, 12, 5, 5, 1, 1, 13, 1, 1, 13, 2, 2, 1, 1,
1170 6, 6, 1, 1, 4, 14, 4, 14, 3, 1, 3, 1, 1, 1, 15, 7,
1171 15, 2, 2, 7, 1, 1, 1, 8, 1, 8, 16, 16, 1, 1, 1, 1,
1172 2, 1, 1, 2, 1, 1, 3, 5, 5, 3, 4, 1, 1, 4, 1, 1,
1173 17, 17, 9, 1, 1, 9, 2, 2, 1, 1, 10, 10, 1, 6, 1, 1,
1174 6, 18, 1, 1, 18, 1, 1, 1, 2, 2, 3, 1, 3, 1, 1, 1,
1175 4, 1, 19, 1, 19, 7, 1, 1, 20, 1, 4, 20, 1, 7, 11, 2,
1176 1, 11, 21, 2, 8, 5, 1, 8, 1, 5, 21, 1, 1, 1, 22, 1,
1177 1, 22, 1, 1, 3, 3, 1, 23, 2, 12, 24, 1, 1, 2, 1, 1,
1178 12, 23, 1, 1, 24, 1, 1, 1, 4, 1, 1, 1, 2, 1, 6, 6,
1179 4, 2, 1, 1, 1, 1, 1, 1, 1, 14, 13, 3, 1, 25, 9, 25,
1180 14, 1, 9, 3, 13, 1, 1, 1, 1, 1, 10, 1, 1, 2, 10, 2},
1183 {-20, -1, 0, 2, -2, 1, -1, 3, -3, 1, -1, 4, -4, 0, 2, -2,
1184 1, 5, -1, -5, 6, -6, 1, -1, 7, -7, 1, -1, 3, -3, 8, -8,
1185 2, -2, 1, -1, 9, -9, 1, -1, 10, -10, 4, -4, 11, 1, -11, -1,
1186 2, -2, 1, 12, -12, -1, 13, -13, 1, -1, 3, -3, 14, 5, -14, -5,
1187 -15, 15, -1, 1, 2, -2, 16, -16, 1, 17, -17, -1, 6, -6, 18, -18,
1188 2, -2, -19, 19, -3, 1, 3, -1, 4, 20, -4, 1, -21, 21, 1, 2,
1189 -1, -7, 7, -2, 22, -22, 23, 2, -23, -2, 1, -1, -24, 24, -25, 25,
1190 -8, -26, 26, 8, -27, 27, 5, 3, -3, -5, -4, 28, -28, 4, 29, -29,
1191 1, -1, -2, -30, 30, 2, 9, -9, -31, 31, 2, -2, -32, 3, 32, -33,
1192 -3, 1, 33, -34, -1, 34, -35, 35, -10, 10, -6, 36, 6, -36, 37, -37,
1193 -5, 38, 1, -38, -1, 3, 39, -39, -1, 40, 5, 1, -40, -3, 2, -11,
1194 -41, -2, 1, 11, -3, -4, 41, 3, 42, 4, -1, -43, -42, 43, 1, -44,
1195 45, -1, 44, -45, -7, 7, -46, 1, -12, 2, 1, -47, 46, 12, 47, 48,
1196 -2, -1, -48, 49, -1, -50, -49, 50, -6, -51, 51, 52, -13, 53, -4, 4,
1197 6, 13, -53, -52, -54, 55, 54, -55, -56, -2, 2, -8, 56, 1, -3, -1,
1198 2, 58, 3, 8, -2, 57, -58, -60, -59, -57, -3, 60, 59, -14, 3, 14}
1204 {1, 1, 0, 2, 2, 1, 1, 3, 3, 4, 4, 5, 5, 1, 1, 6,
1205 6, 2, 2, 7, 7, 8, 8, 1, 1, 3, 3, 9, 9, 10, 10, 1,
1206 1, 2, 2, 4, 4, 11, 0, 11, 12, 12, 13, 13, 1, 1, 5, 5,
1207 14, 14, 15, 16, 15, 16, 3, 3, 1, 6, 1, 6, 2, 2, 7, 7,
1208 8, 8, 17, 17, 1, 1, 4, 4, 18, 18, 2, 2, 1, 19, 1, 20,
1209 19, 20, 21, 21, 3, 3, 22, 22, 5, 5, 24, 1, 1, 23, 9, 23,
1210 24, 9, 2, 2, 10, 1, 1, 10, 6, 6, 25, 4, 4, 25, 7, 7,
1211 26, 8, 1, 8, 3, 1, 26, 3, 11, 11, 27, 27, 2, 28, 1, 2,
1212 28, 1, 12, 12, 5, 5, 29, 13, 13, 29, 32, 1, 1, 33, 31, 30,
1213 32, 4, 30, 33, 4, 31, 3, 14, 1, 1, 3, 34, 34, 2, 2, 14,
1214 6, 6, 35, 36, 35, 36, 1, 15, 1, 16, 16, 15, 7, 9, 7, 9,
1215 37, 8, 8, 37, 1, 1, 39, 2, 38, 39, 2, 40, 5, 38, 40, 5,
1216 3, 3, 4, 4, 10, 10, 1, 1, 1, 1, 41, 2, 41, 2, 6, 6,
1217 1, 1, 11, 42, 11, 43, 3, 42, 3, 17, 4, 43, 1, 17, 7, 1,
1218 8, 44, 4, 7, 44, 5, 8, 2, 5, 1, 2, 48, 45, 1, 12, 45,
1219 12, 48, 13, 13, 1, 9, 9, 46, 1, 46, 47, 47, 49, 18, 18, 49},
1222 { 1, -1, 0, 1, -1, 2, -2, 1, -1, 1, -1, 1, -1, 3, -3, 1,
1223 -1, -2, 2, 1, -1, 1, -1, 4, -4, -2, 2, 1, -1, 1, -1, 5,
1224 -5, -3, 3, 2, -2, 1, 0, -1, 1, -1, 1, -1, 6, -6, 2, -2,
1225 1, -1, 1, 1, -1, -1, -3, 3, 7, 2, -7, -2, -4, 4, 2, -2,
1226 2, -2, 1, -1, 8, -8, 3, -3, 1, -1, -5, 5, 9, 1, -9, 1,
1227 -1, -1, 1, -1, -4, 4, 1, -1, 3, -3, 1, -10, 10, 1, 2, -1,
1228 -1, -2, 6, -6, 2, 11, -11, -2, 3, -3, 1, -4, 4, -1, 3, -3,
1229 1, 3, 12, -3, -5, -12, -1, 5, 2, -2, 1, -1, -7, 1, 13, 7,
1230 -1, -13, 2, -2, 4, -4, 1, 2, -2, -1, 1, 14, -14, 1, 1, 1,
1231 -1, -5, -1, -1, 5, -1, -6, 2, -15, 15, 6, 1, -1, -8, 8, -2,
1232 -4, 4, 1, 1, -1, -1, 16, 2, -16, -2, 2, -2, 4, 3, -4, -3,
1233 -1, -4, 4, 1, -17, 17, -1, -9, 1, 1, 9, 1, -5, -1, -1, 5,
1234 -7, 7, 6, -6, 3, -3, 18, -18, 19, -19, 1, -10, -1, 10, -5, 5,
1235 20, -20, -3, 1, 3, 1, 8, -1, -8, 2, 7, -1, -21, -2, 5, 21,
1236 5, -1, -7, -5, 1, -6, -5, -11, 6, 22, 11, 1, 1, -22, -3, -1,
1237 3, -1, 3, -3, -23, 4, -4, 1, 23, -1, 1, -1, 1, -2, 2, -1}
1243 {1, 1, 1, 1, 0, 2, 2, 1, 1, 3, 3, 0, 1, 1, 2, 2,
1244 4, 4, 1, 1, 5, 5, 1, 1, 2, 2, 3, 3, 6, 6, 1, 1,
1245 7, 7, 8, 1, 8, 2, 2, 1, 4, 4, 1, 3, 1, 3, 9, 9,
1246 2, 2, 1, 5, 1, 5, 10, 10, 1, 1, 11, 11, 3, 6, 3, 4,
1247 4, 6, 2, 2, 1, 12, 1, 12, 7, 13, 7, 13, 1, 1, 8, 8,
1248 2, 2, 14, 14, 16, 15, 16, 5, 5, 1, 3, 15, 1, 3, 4, 4,
1249 1, 1, 17, 17, 2, 2, 6, 6, 1, 18, 1, 18, 22, 21, 22, 21,
1250 25, 24, 25, 19, 9, 20, 9, 23, 19, 24, 20, 3, 23, 7, 3, 1,
1251 1, 7, 28, 26, 29, 5, 28, 26, 5, 8, 29, 4, 8, 27, 2, 2,
1252 4, 27, 1, 1, 10, 36, 10, 33, 33, 36, 30, 1, 32, 32, 1, 30,
1253 6, 31, 31, 35, 3, 6, 11, 11, 3, 2, 35, 2, 34, 1, 34, 1,
1254 37, 37, 12, 7, 12, 5, 41, 5, 4, 7, 1, 8, 13, 4, 1, 41,
1255 13, 38, 8, 38, 9, 1, 40, 40, 9, 1, 39, 2, 2, 49, 39, 42,
1256 3, 3, 14, 16, 49, 14, 16, 42, 43, 43, 6, 6, 15, 1, 1, 15,
1257 44, 44, 1, 1, 50, 48, 4, 5, 4, 7, 5, 2, 10, 10, 48, 7,
1258 50, 45, 2, 1, 45, 8, 8, 1, 46, 46, 3, 47, 47, 3, 1, 1},
1261 { 1, -1, 2, -2, 0, 1, -1, 3, -3, 1, -1, 0, 4, -4, 2, -2,
1262 1, -1, 5, -5, 1, -1, 6, -6, 3, -3, 2, -2, 1, -1, 7, -7,
1263 1, -1, 1, 8, -1, 4, -4, -8, 2, -2, 9, 3, -9, -3, 1, -1,
1264 5, -5, 10, 2, -10, -2, 1, -1, 11, -11, 1, -1, -4, 2, 4, 3,
1265 -3, -2, 6, -6, 12, 1, -12, -1, 2, 1, -2, -1, 13, -13, 2, -2,
1266 7, -7, 1, -1, 1, 1, -1, 3, -3, 14, 5, -1, -14, -5, 4, -4,
1267 15, -15, 1, -1, 8, -8, -3, 3, 16, 1, -16, -1, 1, 1, -1, -1,
1268 1, 1, -1, 1, 2, 1, -2, 1, -1, -1, -1, 6, -1, 3, -6, 17,
1269 -17, -3, 1, 1, 1, 4, -1, -1, -4, 3, -1, 5, -3, -1, -9, 9,
1270 -5, 1, 18, -18, 2, 1, -2, 1, -1, -1, 1, 19, -1, 1, -19, -1,
1271 4, 1, -1, 1, 7, -4, -2, 2, -7, 10, -1, -10, 1, 20, -1, -20,
1272 1, -1, 2, 4, -2, 5, 1, -5, 6, -4, 21, 4, 2, -6, -21, -1,
1273 -2, 1, -4, -1, -3, 22, -1, 1, 3, -22, -1, 11, -11, 1, 1, 1,
1274 8, -8, 2, 2, -1, -2, -2, -1, 1, -1, -5, 5, 2, 23, -23, -2,
1275 1, -1, 24, -24, -1, -1, 7, 6, -7, 5, -6, 12, -3, 3, 1, -5,
1276 1, 1, -12, 25, -1, -5, 5, -25, -1, 1, 9, 1, -1, -9, 26, -26}