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
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)) {
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 if (!band->bufs[0] || !band->bufs[1])
219 return AVERROR(ENOMEM);
221 /* allocate the 3rd band buffer for scalability mode */
222 if (cfg->luma_bands > 1) {
223 band->bufs[2] = av_mallocz(buf_size);
225 return AVERROR(ENOMEM);
228 planes[p].bands[0].blk_vlc.cust_desc.num_rows = 0; /* reset custom vlc */
235 av_cold void ff_ivi_free_buffers(IVIPlaneDesc *planes)
239 for (p = 0; p < 3; p++) {
240 for (b = 0; b < planes[p].num_bands; b++) {
241 av_freep(&planes[p].bands[b].bufs[0]);
242 av_freep(&planes[p].bands[b].bufs[1]);
243 av_freep(&planes[p].bands[b].bufs[2]);
245 if (planes[p].bands[b].blk_vlc.cust_tab.table)
246 ff_free_vlc(&planes[p].bands[b].blk_vlc.cust_tab);
247 for (t = 0; t < planes[p].bands[b].num_tiles; t++)
248 av_freep(&planes[p].bands[b].tiles[t].mbs);
249 av_freep(&planes[p].bands[b].tiles);
251 av_freep(&planes[p].bands);
255 av_cold int ff_ivi_init_tiles(IVIPlaneDesc *planes, int tile_width, int tile_height)
257 int p, b, x, y, x_tiles, y_tiles, t_width, t_height;
259 IVITile *tile, *ref_tile;
261 for (p = 0; p < 3; p++) {
262 t_width = !p ? tile_width : (tile_width + 3) >> 2;
263 t_height = !p ? tile_height : (tile_height + 3) >> 2;
265 if (!p && planes[0].num_bands == 4) {
270 for (b = 0; b < planes[p].num_bands; b++) {
271 band = &planes[p].bands[b];
272 x_tiles = IVI_NUM_TILES(band->width, t_width);
273 y_tiles = IVI_NUM_TILES(band->height, t_height);
274 band->num_tiles = x_tiles * y_tiles;
276 av_freep(&band->tiles);
277 band->tiles = av_mallocz(band->num_tiles * sizeof(IVITile));
279 return AVERROR(ENOMEM);
283 /* use the first luma band as reference for motion vectors
285 ref_tile = planes[0].bands[0].tiles;
287 for (y = 0; y < band->height; y += t_height) {
288 for (x = 0; x < band->width; x += t_width) {
291 tile->mb_size = band->mb_size;
292 tile->width = FFMIN(band->width - x, t_width);
293 tile->height = FFMIN(band->height - y, t_height);
294 tile->is_empty = tile->data_size = 0;
295 /* calculate number of macroblocks */
296 tile->num_MBs = IVI_MBs_PER_TILE(tile->width, tile->height,
299 av_freep(&tile->mbs);
300 tile->mbs = av_malloc(tile->num_MBs * sizeof(IVIMbInfo));
302 return AVERROR(ENOMEM);
306 tile->ref_mbs = ref_tile->mbs;
320 int ff_ivi_dec_tile_data_size(GetBitContext *gb)
326 len = get_bits(gb, 8);
328 len = get_bits_long(gb, 24);
331 /* align the bitstream reader on the byte boundary */
337 int ff_ivi_decode_blocks(GetBitContext *gb, IVIBandDesc *band, IVITile *tile)
339 int mbn, blk, num_blocks, num_coeffs, blk_size, scan_pos, run, val,
340 pos, is_intra, mc_type = 0, mv_x, mv_y, col_mask;
341 uint8_t col_flags[8];
342 int32_t prev_dc, trvec[64];
343 uint32_t cbp, sym, lo, hi, quant, buf_offs, q;
345 RVMapDesc *rvmap = band->rv_map;
346 void (*mc_with_delta_func)(int16_t *buf, const int16_t *ref_buf, uint32_t pitch, int mc_type);
347 void (*mc_no_delta_func) (int16_t *buf, const int16_t *ref_buf, uint32_t pitch, int mc_type);
348 const uint16_t *base_tab;
349 const uint8_t *scale_tab;
351 prev_dc = 0; /* init intra prediction for the DC coefficient */
353 blk_size = band->blk_size;
354 col_mask = blk_size - 1; /* column mask for tracking non-zero coeffs */
355 num_blocks = (band->mb_size != blk_size) ? 4 : 1; /* number of blocks per mb */
356 num_coeffs = blk_size * blk_size;
358 mc_with_delta_func = ff_ivi_mc_8x8_delta;
359 mc_no_delta_func = ff_ivi_mc_8x8_no_delta;
361 mc_with_delta_func = ff_ivi_mc_4x4_delta;
362 mc_no_delta_func = ff_ivi_mc_4x4_no_delta;
365 for (mbn = 0, mb = tile->mbs; mbn < tile->num_MBs; mb++, mbn++) {
366 is_intra = !mb->type;
368 buf_offs = mb->buf_offs;
370 quant = av_clip(band->glob_quant + mb->q_delta, 0, 23);
372 base_tab = is_intra ? band->intra_base : band->inter_base;
373 scale_tab = is_intra ? band->intra_scale : band->inter_scale;
375 quant = scale_tab[quant];
380 if (band->is_halfpel) {
381 mc_type = ((mv_y & 1) << 1) | (mv_x & 1);
383 mv_y >>= 1; /* convert halfpel vectors into fullpel ones */
386 int dmv_x, dmv_y, cx, cy;
388 dmv_x = mb->mv_x >> band->is_halfpel;
389 dmv_y = mb->mv_y >> band->is_halfpel;
390 cx = mb->mv_x & band->is_halfpel;
391 cy = mb->mv_y & band->is_halfpel;
393 if ( mb->xpos + dmv_x < 0
394 || mb->xpos + dmv_x + band->mb_size + cx > band->pitch
395 || mb->ypos + dmv_y < 0
396 || mb->ypos + dmv_y + band->mb_size + cy > band->aheight) {
397 return AVERROR_INVALIDDATA;
402 for (blk = 0; blk < num_blocks; blk++) {
403 /* adjust block position in the buffer according to its number */
405 buf_offs += blk_size;
406 } else if (blk == 2) {
407 buf_offs -= blk_size;
408 buf_offs += blk_size * band->pitch;
411 if (cbp & 1) { /* block coded ? */
413 memset(trvec, 0, num_coeffs*sizeof(trvec[0])); /* zero transform vector */
414 memset(col_flags, 0, sizeof(col_flags)); /* zero column flags */
416 while (scan_pos <= num_coeffs) {
417 sym = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
418 if (sym == rvmap->eob_sym)
419 break; /* End of block */
421 if (sym == rvmap->esc_sym) { /* Escape - run/val explicitly coded using 3 vlc codes */
422 run = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1) + 1;
423 lo = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
424 hi = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
425 val = IVI_TOSIGNED((hi << 6) | lo); /* merge them and convert into signed val */
428 av_log(NULL, AV_LOG_ERROR, "Invalid sym encountered: %d.\n", sym);
431 run = rvmap->runtab[sym];
432 val = rvmap->valtab[sym];
435 /* de-zigzag and dequantize */
437 if (scan_pos >= num_coeffs)
439 pos = band->scan[scan_pos];
442 av_dlog(NULL, "Val = 0 encountered!\n");
444 q = (base_tab[pos] * quant) >> 9;
446 val = val * q + FFSIGN(val) * (((q ^ 1) - 1) >> 1);
448 col_flags[pos & col_mask] |= !!val; /* track columns containing non-zero coeffs */
451 if (scan_pos >= num_coeffs && sym != rvmap->eob_sym)
452 return -1; /* corrupt block data */
454 /* undoing DC coeff prediction for intra-blocks */
455 if (is_intra && band->is_2d_trans) {
458 col_flags[0] |= !!prev_dc;
461 /* apply inverse transform */
462 band->inv_transform(trvec, band->buf + buf_offs,
463 band->pitch, col_flags);
465 /* apply motion compensation */
467 mc_with_delta_func(band->buf + buf_offs,
468 band->ref_buf + buf_offs + mv_y * band->pitch + mv_x,
469 band->pitch, mc_type);
471 /* block not coded */
472 /* for intra blocks apply the dc slant transform */
473 /* for inter - perform the motion compensation without delta */
474 if (is_intra && band->dc_transform) {
475 band->dc_transform(&prev_dc, band->buf + buf_offs,
476 band->pitch, blk_size);
478 mc_no_delta_func(band->buf + buf_offs,
479 band->ref_buf + buf_offs + mv_y * band->pitch + mv_x,
480 band->pitch, mc_type);
492 void ff_ivi_process_empty_tile(AVCodecContext *avctx, IVIBandDesc *band,
493 IVITile *tile, int32_t mv_scale)
495 int x, y, need_mc, mbn, blk, num_blocks, mv_x, mv_y, mc_type;
496 int offs, mb_offset, row_offset;
497 IVIMbInfo *mb, *ref_mb;
500 void (*mc_no_delta_func)(int16_t *buf, const int16_t *ref_buf, uint32_t pitch,
503 offs = tile->ypos * band->pitch + tile->xpos;
505 ref_mb = tile->ref_mbs;
506 row_offset = band->mb_size * band->pitch;
507 need_mc = 0; /* reset the mc tracking flag */
509 for (y = tile->ypos; y < (tile->ypos + tile->height); y += band->mb_size) {
512 for (x = tile->xpos; x < (tile->xpos + tile->width); x += band->mb_size) {
515 mb->buf_offs = mb_offset;
517 mb->type = 1; /* set the macroblocks type = INTER */
518 mb->cbp = 0; /* all blocks are empty */
520 if (!band->qdelta_present && !band->plane && !band->band_num) {
521 mb->q_delta = band->glob_quant;
526 if (band->inherit_qdelta && ref_mb)
527 mb->q_delta = ref_mb->q_delta;
529 if (band->inherit_mv) {
530 /* motion vector inheritance */
532 mb->mv_x = ivi_scale_mv(ref_mb->mv_x, mv_scale);
533 mb->mv_y = ivi_scale_mv(ref_mb->mv_y, mv_scale);
535 mb->mv_x = ref_mb->mv_x;
536 mb->mv_y = ref_mb->mv_y;
538 need_mc |= mb->mv_x || mb->mv_y; /* tracking non-zero motion vectors */
544 mb_offset += band->mb_size;
549 if (band->inherit_mv && need_mc) { /* apply motion compensation if there is at least one non-zero motion vector */
550 num_blocks = (band->mb_size != band->blk_size) ? 4 : 1; /* number of blocks per mb */
551 mc_no_delta_func = (band->blk_size == 8) ? ff_ivi_mc_8x8_no_delta
552 : ff_ivi_mc_4x4_no_delta;
554 for (mbn = 0, mb = tile->mbs; mbn < tile->num_MBs; mb++, mbn++) {
557 if (!band->is_halfpel) {
558 mc_type = 0; /* we have only fullpel vectors */
560 mc_type = ((mv_y & 1) << 1) | (mv_x & 1);
562 mv_y >>= 1; /* convert halfpel vectors into fullpel ones */
565 for (blk = 0; blk < num_blocks; blk++) {
566 /* adjust block position in the buffer according with its number */
567 offs = mb->buf_offs + band->blk_size * ((blk & 1) + !!(blk & 2) * band->pitch);
568 mc_no_delta_func(band->buf + offs,
569 band->ref_buf + offs + mv_y * band->pitch + mv_x,
570 band->pitch, mc_type);
574 /* copy data from the reference tile into the current one */
575 src = band->ref_buf + tile->ypos * band->pitch + tile->xpos;
576 dst = band->buf + tile->ypos * band->pitch + tile->xpos;
577 for (y = 0; y < tile->height; y++) {
578 memcpy(dst, src, tile->width*sizeof(band->buf[0]));
587 static uint16_t ivi_calc_band_checksum(IVIBandDesc *band)
590 int16_t *src, checksum;
595 for (y = 0; y < band->height; src += band->pitch, y++)
596 for (x = 0; x < band->width; x++)
603 void ff_ivi_output_plane(IVIPlaneDesc *plane, uint8_t *dst, int dst_pitch)
606 const int16_t *src = plane->bands[0].buf;
607 uint32_t pitch = plane->bands[0].pitch;
612 for (y = 0; y < plane->height; y++) {
613 for (x = 0; x < plane->width; x++)
614 dst[x] = av_clip_uint8(src[x] + 128);
621 * Decode an Indeo 4 or 5 band.
623 * @param[in,out] ctx ptr to the decoder context
624 * @param[in,out] band ptr to the band descriptor
625 * @param[in] avctx ptr to the AVCodecContext
626 * @return result code: 0 = OK, -1 = error
628 static int decode_band(IVI45DecContext *ctx, int plane_num,
629 IVIBandDesc *band, AVCodecContext *avctx)
631 int result, i, t, idx1, idx2, pos;
634 band->buf = band->bufs[ctx->dst_buf];
636 av_log(avctx, AV_LOG_ERROR, "Band buffer points to no data!\n");
637 return AVERROR_INVALIDDATA;
639 band->ref_buf = band->bufs[ctx->ref_buf];
640 band->data_ptr = ctx->frame_data + (get_bits_count(&ctx->gb) >> 3);
642 result = ctx->decode_band_hdr(ctx, band, avctx);
644 av_log(avctx, AV_LOG_ERROR, "Error while decoding band header: %d\n",
649 if (band->is_empty) {
650 av_log(avctx, AV_LOG_ERROR, "Empty band encountered!\n");
651 return AVERROR_INVALIDDATA;
654 band->rv_map = &ctx->rvmap_tabs[band->rvmap_sel];
656 /* apply corrections to the selected rvmap table if present */
657 for (i = 0; i < band->num_corr; i++) {
658 idx1 = band->corr[i * 2];
659 idx2 = band->corr[i * 2 + 1];
660 FFSWAP(uint8_t, band->rv_map->runtab[idx1], band->rv_map->runtab[idx2]);
661 FFSWAP(int16_t, band->rv_map->valtab[idx1], band->rv_map->valtab[idx2]);
664 pos = get_bits_count(&ctx->gb);
666 for (t = 0; t < band->num_tiles; t++) {
667 tile = &band->tiles[t];
669 if (tile->mb_size != band->mb_size) {
670 av_log(avctx, AV_LOG_ERROR, "MB sizes mismatch: %d vs. %d\n",
671 band->mb_size, tile->mb_size);
672 return AVERROR_INVALIDDATA;
674 tile->is_empty = get_bits1(&ctx->gb);
675 if (tile->is_empty) {
676 ff_ivi_process_empty_tile(avctx, band, tile,
677 (ctx->planes[0].bands[0].mb_size >> 3) - (band->mb_size >> 3));
678 av_dlog(avctx, "Empty tile encountered!\n");
680 tile->data_size = ff_ivi_dec_tile_data_size(&ctx->gb);
681 if (!tile->data_size) {
682 av_log(avctx, AV_LOG_ERROR, "Tile data size is zero!\n");
683 return AVERROR_INVALIDDATA;
686 result = ctx->decode_mb_info(ctx, band, tile, avctx);
690 result = ff_ivi_decode_blocks(&ctx->gb, band, tile);
691 if (result < 0 || ((get_bits_count(&ctx->gb) - pos) >> 3) != tile->data_size) {
692 av_log(avctx, AV_LOG_ERROR, "Corrupted tile data encountered!\n");
696 pos += tile->data_size << 3; // skip to next tile
700 /* restore the selected rvmap table by applying its corrections in reverse order */
701 for (i = band->num_corr-1; i >= 0; i--) {
702 idx1 = band->corr[i*2];
703 idx2 = band->corr[i*2+1];
704 FFSWAP(uint8_t, band->rv_map->runtab[idx1], band->rv_map->runtab[idx2]);
705 FFSWAP(int16_t, band->rv_map->valtab[idx1], band->rv_map->valtab[idx2]);
709 if (band->checksum_present) {
710 uint16_t chksum = ivi_calc_band_checksum(band);
711 if (chksum != band->checksum) {
712 av_log(avctx, AV_LOG_ERROR,
713 "Band checksum mismatch! Plane %d, band %d, received: %x, calculated: %x\n",
714 band->plane, band->band_num, band->checksum, chksum);
719 align_get_bits(&ctx->gb);
724 int ff_ivi_decode_frame(AVCodecContext *avctx, void *data, int *data_size,
727 IVI45DecContext *ctx = avctx->priv_data;
728 const uint8_t *buf = avpkt->data;
729 int buf_size = avpkt->size;
732 init_get_bits(&ctx->gb, buf, buf_size * 8);
733 ctx->frame_data = buf;
734 ctx->frame_size = buf_size;
736 result = ctx->decode_pic_hdr(ctx, avctx);
738 av_log(avctx, AV_LOG_ERROR,
739 "Error while decoding picture header: %d\n", result);
743 if (ctx->gop_flags & IVI5_IS_PROTECTED) {
744 av_log(avctx, AV_LOG_ERROR, "Password-protected clip!\n");
748 ctx->switch_buffers(ctx);
752 if (ctx->is_nonnull_frame(ctx)) {
753 for (p = 0; p < 3; p++) {
754 for (b = 0; b < ctx->planes[p].num_bands; b++) {
755 result = decode_band(ctx, p, &ctx->planes[p].bands[b], avctx);
757 av_log(avctx, AV_LOG_ERROR,
758 "Error while decoding band: %d, plane: %d\n", b, p);
765 //STOP_TIMER("decode_planes"); }
767 /* If the bidirectional mode is enabled, next I and the following P frame will */
768 /* be sent together. Unfortunately the approach below seems to be the only way */
769 /* to handle the B-frames mode. That's exactly the same Intel decoders do. */
770 if (avctx->codec_id == CODEC_ID_INDEO4 && ctx->frame_type == 0/*FRAMETYPE_INTRA*/) {
771 while (get_bits(&ctx->gb, 8)); // skip version string
772 skip_bits_long(&ctx->gb, 64); // skip padding, TODO: implement correct 8-bytes alignment
773 if (get_bits_left(&ctx->gb) > 18 && show_bits(&ctx->gb, 18) == 0x3FFF8)
774 av_log(avctx, AV_LOG_ERROR, "Buffer contains IP frames!\n");
777 if (ctx->frame.data[0])
778 avctx->release_buffer(avctx, &ctx->frame);
780 ctx->frame.reference = 0;
781 if ((result = avctx->get_buffer(avctx, &ctx->frame)) < 0) {
782 av_log(avctx, AV_LOG_ERROR, "get_buffer() failed\n");
786 if (ctx->is_scalable) {
787 if (avctx->codec_id == CODEC_ID_INDEO4)
788 ff_ivi_recompose_haar(&ctx->planes[0], ctx->frame.data[0], ctx->frame.linesize[0], 4);
790 ff_ivi_recompose53 (&ctx->planes[0], ctx->frame.data[0], ctx->frame.linesize[0], 4);
792 ff_ivi_output_plane(&ctx->planes[0], ctx->frame.data[0], ctx->frame.linesize[0]);
795 ff_ivi_output_plane(&ctx->planes[2], ctx->frame.data[1], ctx->frame.linesize[1]);
796 ff_ivi_output_plane(&ctx->planes[1], ctx->frame.data[2], ctx->frame.linesize[2]);
798 *data_size = sizeof(AVFrame);
799 *(AVFrame*)data = ctx->frame;
805 * Close Indeo5 decoder and clean up its context.
807 av_cold int ff_ivi_decode_close(AVCodecContext *avctx)
809 IVI45DecContext *ctx = avctx->priv_data;
811 ff_ivi_free_buffers(&ctx->planes[0]);
813 if (ctx->mb_vlc.cust_tab.table)
814 ff_free_vlc(&ctx->mb_vlc.cust_tab);
816 if (ctx->frame.data[0])
817 avctx->release_buffer(avctx, &ctx->frame);
819 #if IVI4_STREAM_ANALYSER
820 if (avctx->codec_id == CODEC_ID_INDEO4) {
821 if (ctx->is_scalable)
822 av_log(avctx, AV_LOG_ERROR, "This video uses scalability mode!\n");
823 if (ctx->uses_tiling)
824 av_log(avctx, AV_LOG_ERROR, "This video uses local decoding!\n");
825 if (ctx->has_b_frames)
826 av_log(avctx, AV_LOG_ERROR, "This video contains B-frames!\n");
828 av_log(avctx, AV_LOG_ERROR, "Transparency mode is enabled!\n");
830 av_log(avctx, AV_LOG_ERROR, "This video uses Haar transform!\n");
831 if (ctx->uses_fullpel)
832 av_log(avctx, AV_LOG_ERROR, "This video uses fullpel motion vectors!\n");
841 * These are 2x8 predefined Huffman codebooks for coding macroblock/block
842 * signals. They are specified using "huffman descriptors" in order to
843 * avoid huge static tables. The decoding tables will be generated at
844 * startup from these descriptors.
846 const IVIHuffDesc ff_ivi_mb_huff_desc[8] = {
847 {8, {0, 4, 5, 4, 4, 4, 6, 6}},
848 {12, {0, 2, 2, 3, 3, 3, 3, 5, 3, 2, 2, 2}},
849 {12, {0, 2, 3, 4, 3, 3, 3, 3, 4, 3, 2, 2}},
850 {12, {0, 3, 4, 4, 3, 3, 3, 3, 3, 2, 2, 2}},
851 {13, {0, 4, 4, 3, 3, 3, 3, 2, 3, 3, 2, 1, 1}},
852 {9, {0, 4, 4, 4, 4, 3, 3, 3, 2}},
853 {10, {0, 4, 4, 4, 4, 3, 3, 2, 2, 2}},
854 {12, {0, 4, 4, 4, 3, 3, 2, 3, 2, 2, 2, 2}}
857 const IVIHuffDesc ff_ivi_blk_huff_desc[8] = {
858 {10, {1, 2, 3, 4, 4, 7, 5, 5, 4, 1}},
859 {11, {2, 3, 4, 4, 4, 7, 5, 4, 3, 3, 2}},
860 {12, {2, 4, 5, 5, 5, 5, 6, 4, 4, 3, 1, 1}},
861 {13, {3, 3, 4, 4, 5, 6, 6, 4, 4, 3, 2, 1, 1}},
862 {11, {3, 4, 4, 5, 5, 5, 6, 5, 4, 2, 2}},
863 {13, {3, 4, 5, 5, 5, 5, 6, 4, 3, 3, 2, 1, 1}},
864 {13, {3, 4, 5, 5, 5, 6, 5, 4, 3, 3, 2, 1, 1}},
865 {9, {3, 4, 4, 5, 5, 5, 6, 5, 5}}
870 * Scan patterns shared between indeo4 and indeo5
872 const uint8_t ff_ivi_vertical_scan_8x8[64] = {
873 0, 8, 16, 24, 32, 40, 48, 56,
874 1, 9, 17, 25, 33, 41, 49, 57,
875 2, 10, 18, 26, 34, 42, 50, 58,
876 3, 11, 19, 27, 35, 43, 51, 59,
877 4, 12, 20, 28, 36, 44, 52, 60,
878 5, 13, 21, 29, 37, 45, 53, 61,
879 6, 14, 22, 30, 38, 46, 54, 62,
880 7, 15, 23, 31, 39, 47, 55, 63
883 const uint8_t ff_ivi_horizontal_scan_8x8[64] = {
884 0, 1, 2, 3, 4, 5, 6, 7,
885 8, 9, 10, 11, 12, 13, 14, 15,
886 16, 17, 18, 19, 20, 21, 22, 23,
887 24, 25, 26, 27, 28, 29, 30, 31,
888 32, 33, 34, 35, 36, 37, 38, 39,
889 40, 41, 42, 43, 44, 45, 46, 47,
890 48, 49, 50, 51, 52, 53, 54, 55,
891 56, 57, 58, 59, 60, 61, 62, 63
894 const uint8_t ff_ivi_direct_scan_4x4[16] = {
895 0, 1, 4, 8, 5, 2, 3, 6, 9, 12, 13, 10, 7, 11, 14, 15
900 * Run-value (RLE) tables.
902 const RVMapDesc ff_ivi_rvmap_tabs[9] = {
907 {1, 1, 0, 1, 1, 0, 1, 1, 2, 2, 1, 1, 1, 1, 3, 3,
908 1, 1, 2, 2, 1, 1, 4, 4, 1, 1, 1, 1, 2, 2, 5, 5,
909 1, 1, 3, 3, 1, 1, 6, 6, 1, 2, 1, 2, 7, 7, 1, 1,
910 8, 8, 1, 1, 4, 2, 1, 4, 2, 1, 3, 3, 1, 1, 1, 9,
911 9, 1, 2, 1, 2, 1, 5, 5, 1, 1, 10, 10, 1, 1, 3, 3,
912 2, 2, 1, 1, 11, 11, 6, 4, 4, 1, 6, 1, 2, 1, 2, 12,
913 8, 1, 12, 7, 8, 7, 1, 16, 1, 16, 1, 3, 3, 13, 1, 13,
914 2, 2, 1, 15, 1, 5, 14, 15, 1, 5, 14, 1, 17, 8, 17, 8,
915 1, 4, 4, 2, 2, 1, 25, 25, 24, 24, 1, 3, 1, 3, 1, 8,
916 6, 7, 6, 1, 18, 8, 18, 1, 7, 23, 2, 2, 23, 1, 1, 21,
917 22, 9, 9, 22, 19, 1, 21, 5, 19, 5, 1, 33, 20, 33, 20, 8,
918 4, 4, 1, 32, 2, 2, 8, 3, 32, 26, 3, 1, 7, 7, 26, 6,
919 1, 6, 1, 1, 16, 1, 10, 1, 10, 2, 16, 29, 28, 2, 29, 28,
920 1, 27, 5, 8, 5, 27, 1, 8, 3, 7, 3, 31, 41, 31, 1, 41,
921 6, 1, 6, 7, 4, 4, 1, 1, 2, 1, 2, 11, 34, 30, 11, 1,
922 30, 15, 15, 34, 36, 40, 36, 40, 35, 35, 37, 37, 39, 39, 38, 38},
925 { 1, -1, 0, 2, -2, 0, 3, -3, 1, -1, 4, -4, 5, -5, 1, -1,
926 6, -6, 2, -2, 7, -7, 1, -1, 8, -8, 9, -9, 3, -3, 1, -1,
927 10, -10, 2, -2, 11, -11, 1, -1, 12, 4, -12, -4, 1, -1, 13, -13,
928 1, -1, 14, -14, 2, 5, 15, -2, -5, -15, -3, 3, 16, -16, 17, 1,
929 -1, -17, 6, 18, -6, -18, 2, -2, 19, -19, 1, -1, 20, -20, 4, -4,
930 7, -7, 21, -21, 1, -1, 2, 3, -3, 22, -2, -22, 8, 23, -8, 1,
931 2, -23, -1, 2, -2, -2, 24, 1, -24, -1, 25, 5, -5, 1, -25, -1,
932 9, -9, 26, 1, -26, 3, 1, -1, 27, -3, -1, -27, 1, 3, -1, -3,
933 28, -4, 4, 10, -10, -28, 1, -1, 1, -1, 29, 6, -29, -6, 30, -4,
934 3, 3, -3, -30, 1, 4, -1, 31, -3, 1, 11, -11, -1, -31, 32, -1,
935 -1, 2, -2, 1, 1, -32, 1, 4, -1, -4, 33, -1, 1, 1, -1, 5,
936 5, -5, -33, -1, -12, 12, -5, -7, 1, 1, 7, 34, 4, -4, -1, 4,
937 -34, -4, 35, 36, -2, -35, -2, -36, 2, 13, 2, -1, 1, -13, 1, -1,
938 37, 1, -5, 6, 5, -1, 38, -6, -8, 5, 8, -1, 1, 1, -37, -1,
939 5, 39, -5, -5, 6, -6, -38, -39, -14, 40, 14, 2, 1, 1, -2, -40,
940 -1, -2, 2, -1, -1, -1, 1, 1, 1, -1, 1, -1, 1, -1, 1, -1}
946 {0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 8, 6, 8, 7,
947 7, 9, 9, 10, 10, 11, 11, 1, 12, 1, 12, 13, 13, 16, 14, 16,
948 14, 15, 15, 17, 17, 18, 0, 18, 19, 20, 21, 19, 22, 21, 20, 22,
949 25, 24, 2, 25, 24, 23, 23, 2, 26, 28, 26, 28, 29, 27, 29, 27,
950 33, 33, 1, 32, 1, 3, 32, 30, 36, 3, 36, 30, 31, 31, 35, 34,
951 37, 41, 34, 35, 37, 4, 41, 4, 49, 8, 8, 49, 40, 38, 5, 38,
952 40, 39, 5, 39, 42, 43, 42, 7, 57, 6, 43, 44, 6, 50, 7, 44,
953 57, 48, 50, 48, 45, 45, 46, 47, 51, 46, 47, 58, 1, 51, 58, 1,
954 52, 59, 53, 9, 52, 55, 55, 59, 53, 56, 54, 56, 54, 9, 64, 64,
955 60, 63, 60, 63, 61, 62, 61, 62, 2, 10, 2, 10, 11, 1, 11, 13,
956 12, 1, 12, 13, 16, 16, 8, 8, 14, 3, 3, 15, 14, 15, 4, 4,
957 1, 17, 17, 5, 1, 7, 7, 5, 6, 1, 2, 2, 6, 22, 1, 25,
958 21, 22, 8, 24, 1, 21, 25, 24, 8, 18, 18, 23, 9, 20, 23, 33,
959 29, 33, 20, 1, 19, 1, 29, 36, 9, 36, 19, 41, 28, 57, 32, 3,
960 28, 3, 1, 27, 49, 49, 1, 32, 26, 26, 2, 4, 4, 7, 57, 41,
961 2, 7, 10, 5, 37, 16, 10, 27, 8, 8, 13, 16, 37, 13, 1, 5},
964 {0, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, 1, -1, -1, 1,
965 -1, 1, -1, 1, -1, 1, -1, 2, 1, -2, -1, 1, -1, 1, 1, -1,
966 -1, 1, -1, 1, -1, 1, 0, -1, 1, 1, 1, -1, 1, -1, -1, -1,
967 1, 1, 2, -1, -1, 1, -1, -2, 1, 1, -1, -1, 1, 1, -1, -1,
968 1, -1, 3, 1, -3, 2, -1, 1, 1, -2, -1, -1, -1, 1, 1, 1,
969 1, 1, -1, -1, -1, 2, -1, -2, 1, 2, -2, -1, 1, 1, 2, -1,
970 -1, 1, -2, -1, 1, 1, -1, 2, 1, 2, -1, 1, -2, -1, -2, -1,
971 -1, 1, 1, -1, 1, -1, 1, 1, 1, -1, -1, 1, 4, -1, -1, -4,
972 1, 1, 1, 2, -1, -1, 1, -1, -1, 1, -1, -1, 1, -2, 1, -1,
973 1, 1, -1, -1, 1, 1, -1, -1, 3, 2, -3, -2, 2, 5, -2, 2,
974 2, -5, -2, -2, -2, 2, -3, 3, 2, 3, -3, 2, -2, -2, 3, -3,
975 6, 2, -2, 3, -6, 3, -3, -3, 3, 7, -4, 4, -3, 2, -7, 2,
976 2, -2, -4, 2, 8, -2, -2, -2, 4, 2, -2, 2, 3, 2, -2, -2,
977 2, 2, -2, -8, -2, 9, -2, 2, -3, -2, 2, -2, 2, 2, 2, 4,
978 -2, -4, 10, 2, 2, -2, -9, -2, 2, -2, 5, 4, -4, 4, -2, 2,
979 -5, -4, -3, 4, 2, -3, 3, -2, -5, 5, 3, 3, -2, -3, -10, -4}
985 {1, 1, 0, 2, 2, 1, 1, 3, 3, 4, 4, 0, 1, 1, 5, 5,
986 2, 2, 6, 6, 7, 7, 1, 8, 1, 8, 3, 3, 9, 9, 1, 2,
987 2, 1, 4, 10, 4, 10, 11, 11, 1, 5, 12, 12, 1, 5, 13, 13,
988 3, 3, 6, 6, 2, 2, 14, 14, 16, 16, 15, 7, 15, 8, 8, 7,
989 1, 1, 17, 17, 4, 4, 1, 1, 18, 18, 2, 2, 5, 5, 25, 3,
990 9, 3, 25, 9, 19, 24, 19, 24, 1, 21, 20, 1, 21, 22, 20, 22,
991 23, 23, 8, 6, 33, 6, 8, 33, 7, 7, 26, 26, 1, 32, 1, 32,
992 28, 4, 28, 10, 29, 27, 27, 10, 41, 4, 29, 2, 2, 41, 36, 31,
993 49, 31, 34, 30, 34, 36, 30, 35, 1, 49, 11, 5, 35, 11, 1, 3,
994 3, 5, 37, 37, 8, 40, 8, 40, 12, 12, 42, 42, 1, 38, 16, 57,
995 1, 6, 16, 39, 38, 6, 7, 7, 13, 13, 39, 43, 2, 43, 57, 2,
996 50, 9, 44, 9, 50, 4, 15, 48, 44, 4, 1, 15, 48, 14, 14, 1,
997 45, 45, 8, 3, 5, 8, 51, 47, 3, 46, 46, 47, 5, 51, 1, 17,
998 17, 58, 1, 58, 2, 52, 52, 2, 53, 7, 59, 6, 6, 56, 53, 55,
999 7, 55, 1, 54, 59, 56, 54, 10, 1, 10, 4, 60, 1, 60, 8, 4,
1000 8, 64, 64, 61, 1, 63, 3, 63, 62, 61, 5, 11, 5, 3, 11, 62},
1003 { 1, -1, 0, 1, -1, 2, -2, 1, -1, 1, -1, 0, 3, -3, 1, -1,
1004 2, -2, 1, -1, 1, -1, 4, 1, -4, -1, 2, -2, 1, -1, 5, 3,
1005 -3, -5, 2, 1, -2, -1, 1, -1, 6, 2, 1, -1, -6, -2, 1, -1,
1006 3, -3, 2, -2, 4, -4, 1, -1, 1, -1, 1, 2, -1, 2, -2, -2,
1007 7, -7, 1, -1, 3, -3, 8, -8, 1, -1, 5, -5, 3, -3, 1, 4,
1008 2, -4, -1, -2, 1, 1, -1, -1, 9, 1, 1, -9, -1, 1, -1, -1,
1009 1, -1, 3, -3, 1, 3, -3, -1, 3, -3, 1, -1, 10, 1, -10, -1,
1010 1, 4, -1, 2, 1, -1, 1, -2, 1, -4, -1, 6, -6, -1, 1, 1,
1011 1, -1, 1, 1, -1, -1, -1, 1, 11, -1, -2, 4, -1, 2, -11, 5,
1012 -5, -4, -1, 1, 4, 1, -4, -1, -2, 2, 1, -1, 12, 1, -2, 1,
1013 -12, 4, 2, 1, -1, -4, 4, -4, 2, -2, -1, 1, 7, -1, -1, -7,
1014 -1, -3, 1, 3, 1, 5, 2, 1, -1, -5, 13, -2, -1, 2, -2, -13,
1015 1, -1, 5, 6, 5, -5, 1, 1, -6, 1, -1, -1, -5, -1, 14, 2,
1016 -2, 1, -14, -1, 8, 1, -1, -8, 1, 5, 1, 5, -5, 1, -1, 1,
1017 -5, -1, 15, 1, -1, -1, -1, 3, -15, -3, 6, 1, 16, -1, 6, -6,
1018 -6, 1, -1, 1, -16, 1, 7, -1, 1, -1, -6, -3, 6, -7, 3, -1}
1024 {0, 1, 1, 2, 2, 3, 3, 4, 4, 1, 1, 5, 5, 6, 6, 7,
1025 7, 8, 8, 9, 9, 2, 2, 10, 10, 1, 1, 11, 11, 12, 12, 3,
1026 3, 13, 13, 0, 14, 14, 16, 15, 16, 15, 4, 4, 17, 1, 17, 1,
1027 5, 5, 18, 18, 2, 2, 6, 6, 8, 19, 7, 8, 7, 19, 20, 20,
1028 21, 21, 22, 24, 22, 24, 23, 23, 1, 1, 25, 25, 3, 3, 26, 26,
1029 9, 9, 27, 27, 28, 28, 33, 29, 4, 33, 29, 1, 4, 1, 32, 32,
1030 2, 2, 31, 10, 30, 10, 30, 31, 34, 34, 5, 5, 36, 36, 35, 41,
1031 35, 11, 41, 11, 37, 1, 8, 8, 37, 6, 1, 6, 40, 7, 7, 40,
1032 12, 38, 12, 39, 39, 38, 49, 13, 49, 13, 3, 42, 3, 42, 16, 16,
1033 43, 43, 14, 14, 1, 1, 44, 15, 44, 15, 2, 2, 57, 48, 50, 48,
1034 57, 50, 4, 45, 45, 4, 46, 47, 47, 46, 1, 51, 1, 17, 17, 51,
1035 8, 9, 9, 5, 58, 8, 58, 5, 52, 52, 55, 56, 53, 56, 55, 59,
1036 59, 53, 54, 1, 6, 54, 7, 7, 6, 1, 2, 3, 2, 3, 64, 60,
1037 60, 10, 10, 64, 61, 62, 61, 63, 1, 63, 62, 1, 18, 24, 18, 4,
1038 25, 4, 8, 21, 21, 1, 24, 22, 25, 22, 8, 11, 19, 11, 23, 1,
1039 20, 23, 19, 20, 5, 12, 5, 1, 16, 2, 12, 13, 2, 13, 1, 16},
1042 { 0, 1, -1, 1, -1, 1, -1, 1, -1, 2, -2, 1, -1, 1, -1, 1,
1043 -1, 1, -1, 1, -1, 2, -2, 1, -1, 3, -3, 1, -1, 1, -1, 2,
1044 -2, 1, -1, 0, 1, -1, 1, 1, -1, -1, 2, -2, 1, 4, -1, -4,
1045 2, -2, 1, -1, -3, 3, 2, -2, 2, 1, 2, -2, -2, -1, 1, -1,
1046 1, -1, 1, 1, -1, -1, 1, -1, 5, -5, 1, -1, 3, -3, 1, -1,
1047 2, -2, 1, -1, 1, -1, 1, 1, 3, -1, -1, 6, -3, -6, -1, 1,
1048 4, -4, 1, 2, 1, -2, -1, -1, 1, -1, 3, -3, 1, -1, 1, 1,
1049 -1, 2, -1, -2, 1, 7, -3, 3, -1, 3, -7, -3, 1, -3, 3, -1,
1050 2, 1, -2, 1, -1, -1, 1, 2, -1, -2, -4, -1, 4, 1, 2, -2,
1051 1, -1, -2, 2, 8, -8, -1, 2, 1, -2, -5, 5, 1, -1, -1, 1,
1052 -1, 1, 4, -1, 1, -4, -1, -1, 1, 1, 9, 1, -9, 2, -2, -1,
1053 -4, 3, -3, -4, -1, 4, 1, 4, 1, -1, 1, -1, 1, 1, -1, 1,
1054 -1, -1, -1, 10, 4, 1, 4, -4, -4, -10, 6, 5, -6, -5, 1, -1,
1055 1, 3, -3, -1, 1, -1, -1, -1, 11, 1, 1, -11, -2, -2, 2, 5,
1056 -2, -5, -5, 2, -2, 12, 2, -2, 2, 2, 5, -3, -2, 3, -2, -12,
1057 -2, 2, 2, 2, -5, 3, 5, 13, -3, 7, -3, -3, -7, 3, -13, 3}
1063 {0, 1, 1, 1, 2, 2, 1, 3, 3, 1, 1, 1, 4, 4, 1, 5,
1064 2, 1, 5, 2, 1, 1, 6, 6, 1, 1, 1, 1, 1, 7, 3, 1,
1065 2, 3, 0, 1, 2, 7, 1, 1, 1, 8, 1, 1, 8, 1, 1, 1,
1066 9, 1, 9, 1, 2, 1, 1, 2, 1, 1, 10, 4, 1, 10, 1, 4,
1067 1, 1, 1, 1, 1, 3, 1, 1, 1, 3, 2, 1, 5, 1, 1, 1,
1068 2, 5, 1, 11, 1, 11, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1069 2, 1, 6, 1, 6, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 12,
1070 3, 1, 12, 1, 1, 1, 2, 1, 1, 3, 1, 1, 1, 1, 1, 1,
1071 4, 1, 1, 1, 2, 1, 1, 4, 1, 1, 1, 1, 1, 1, 2, 1,
1072 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 2, 1, 1, 5,
1073 1, 1, 1, 1, 1, 7, 1, 7, 1, 1, 2, 3, 1, 1, 1, 1,
1074 5, 1, 1, 1, 1, 1, 1, 2, 13, 1, 1, 1, 1, 1, 1, 1,
1075 1, 1, 1, 1, 1, 1, 1, 1, 13, 2, 1, 1, 4, 1, 1, 1,
1076 3, 1, 6, 1, 1, 1, 14, 1, 1, 1, 1, 1, 14, 6, 1, 1,
1077 1, 1, 15, 2, 4, 1, 2, 3, 15, 1, 1, 1, 8, 1, 1, 8,
1078 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1},
1081 { 0, 1, -1, 2, 1, -1, -2, 1, -1, 3, -3, 4, 1, -1, -4, 1,
1082 2, 5, -1, -2, -5, 6, 1, -1, -6, 7, -7, 8, -8, 1, 2, 9,
1083 3, -2, 0, -9, -3, -1, 10, -10, 11, 1, -11, 12, -1, -12, 13, -13,
1084 1, 14, -1, -14, 4, 15, -15, -4, 16, -16, 1, 2, 17, -1, -17, -2,
1085 18, -18, 19, -19, 20, 3, -20, 21, -21, -3, 5, 22, 2, -22, -23, 23,
1086 -5, -2, 24, 1, -24, -1, 25, -25, 26, -26, -27, 27, 28, 29, -28, -29,
1087 6, 30, 2, -31, -2, -30, 31, -6, -32, 32, 33, -33, 34, -35, -34, 1,
1088 4, -36, -1, 35, 37, 36, 7, -37, 38, -4, -38, 39, 41, 40, -40, -39,
1089 3, 42, -43, -41, -7, -42, 43, -3, 44, -44, 45, -45, 46, 47, 8, -47,
1090 -48, -46, 50, -50, 48, 49, 51, -49, 52, -52, 5, -51, -8, -53, 53, 3,
1091 -56, 56, 55, 54, -54, 2, 60, -2, -55, 58, 9, -5, 59, 57, -57, -63,
1092 -3, -58, -60, -61, 61, -59, -62, -9, 1, 64, 62, 69, -64, 63, 65, -67,
1093 -68, 66, -65, 68, -66, -69, 67, -70, -1, 10, 71, -71, 4, 73, 72, 70,
1094 6, -76, -3, 74, -78, -74, 1, 78, 80, -72, -75, 76, -1, 3, -73, 79,
1095 75, 77, 1, 11, -4, -79, -10, -6, -1, -77, -83, -80, 2, 81, -84, -2,
1096 83, -81, 82, -82, 84, -87, -86, 85, -11, -85, 86, -89, 87, -88, 88, 89}
1102 {1, 1, 0, 2, 1, 2, 1, 3, 3, 1, 1, 4, 4, 2, 2, 1,
1103 1, 5, 5, 6, 1, 6, 1, 7, 7, 3, 3, 2, 8, 2, 8, 1,
1104 1, 0, 9, 9, 1, 1, 10, 4, 10, 4, 11, 11, 2, 1, 2, 1,
1105 12, 12, 3, 3, 1, 1, 13, 5, 5, 13, 14, 1, 1, 14, 2, 2,
1106 6, 6, 15, 1, 1, 15, 16, 4, 7, 16, 4, 7, 1, 1, 3, 3,
1107 8, 8, 2, 2, 1, 1, 17, 17, 1, 1, 18, 18, 5, 5, 2, 2,
1108 1, 1, 9, 19, 9, 19, 20, 3, 3, 20, 1, 10, 21, 1, 10, 4,
1109 4, 21, 22, 6, 6, 22, 1, 1, 23, 24, 2, 2, 23, 24, 11, 1,
1110 1, 11, 7, 25, 7, 1, 1, 25, 8, 8, 3, 26, 3, 1, 12, 2,
1111 2, 26, 1, 12, 5, 5, 27, 4, 1, 4, 1, 27, 28, 1, 28, 13,
1112 1, 13, 2, 29, 2, 1, 32, 6, 1, 30, 14, 29, 14, 6, 3, 31,
1113 3, 1, 30, 1, 32, 31, 33, 9, 33, 1, 1, 7, 9, 7, 2, 2,
1114 1, 1, 4, 36, 34, 4, 5, 10, 10, 5, 34, 1, 1, 35, 8, 8,
1115 36, 3, 35, 1, 15, 3, 2, 1, 16, 15, 16, 2, 37, 1, 37, 1,
1116 1, 1, 6, 6, 38, 1, 38, 11, 1, 39, 39, 40, 11, 2, 41, 4,
1117 40, 1, 2, 4, 1, 1, 1, 41, 3, 1, 3, 1, 5, 7, 5, 7},
1120 { 1, -1, 0, 1, 2, -1, -2, 1, -1, 3, -3, 1, -1, 2, -2, 4,
1121 -4, 1, -1, 1, 5, -1, -5, 1, -1, 2, -2, 3, 1, -3, -1, 6,
1122 -6, 0, 1, -1, 7, -7, 1, 2, -1, -2, 1, -1, 4, 8, -4, -8,
1123 1, -1, 3, -3, 9, -9, 1, 2, -2, -1, 1, 10, -10, -1, 5, -5,
1124 2, -2, 1, 11, -11, -1, 1, 3, 2, -1, -3, -2, 12, -12, 4, -4,
1125 2, -2, -6, 6, 13, -13, 1, -1, 14, -14, 1, -1, 3, -3, 7, -7,
1126 15, -15, 2, 1, -2, -1, 1, 5, -5, -1, -16, 2, 1, 16, -2, 4,
1127 -4, -1, 1, 3, -3, -1, 17, -17, 1, 1, -8, 8, -1, -1, 2, 18,
1128 -18, -2, 3, 1, -3, 19, -19, -1, 3, -3, 6, 1, -6, 20, 2, 9,
1129 -9, -1, -20, -2, 4, -4, 1, -5, 21, 5, -21, -1, 1, -22, -1, 2,
1130 22, -2, 10, 1, -10, 23, 1, 4, -23, 1, 2, -1, -2, -4, -7, 1,
1131 7, -24, -1, 24, -1, -1, 1, 3, -1, -25, 25, 4, -3, -4, 11, -11,
1132 26, -26, 6, 1, 1, -6, -5, -3, 3, 5, -1, -27, 27, 1, 4, -4,
1133 -1, -8, -1, 28, 2, 8, -12, -28, -2, -2, 2, 12, -1, 29, 1, -29,
1134 30, -30, 5, -5, 1, -31, -1, 3, 31, -1, 1, 1, -3, -13, 1, -7,
1135 -1, -32, 13, 7, 32, 33, -33, -1, -9, -34, 9, 34, -6, 5, 6, -5}
1141 {1, 1, 0, 1, 1, 2, 2, 1, 1, 3, 3, 1, 1, 0, 2, 2,
1142 4, 1, 4, 1, 1, 1, 5, 5, 1, 1, 6, 6, 2, 2, 1, 1,
1143 3, 3, 7, 7, 1, 1, 8, 8, 1, 1, 2, 2, 1, 9, 1, 9,
1144 4, 4, 10, 1, 1, 10, 1, 1, 11, 11, 3, 3, 1, 2, 1, 2,
1145 1, 1, 12, 12, 5, 5, 1, 1, 13, 1, 1, 13, 2, 2, 1, 1,
1146 6, 6, 1, 1, 4, 14, 4, 14, 3, 1, 3, 1, 1, 1, 15, 7,
1147 15, 2, 2, 7, 1, 1, 1, 8, 1, 8, 16, 16, 1, 1, 1, 1,
1148 2, 1, 1, 2, 1, 1, 3, 5, 5, 3, 4, 1, 1, 4, 1, 1,
1149 17, 17, 9, 1, 1, 9, 2, 2, 1, 1, 10, 10, 1, 6, 1, 1,
1150 6, 18, 1, 1, 18, 1, 1, 1, 2, 2, 3, 1, 3, 1, 1, 1,
1151 4, 1, 19, 1, 19, 7, 1, 1, 20, 1, 4, 20, 1, 7, 11, 2,
1152 1, 11, 21, 2, 8, 5, 1, 8, 1, 5, 21, 1, 1, 1, 22, 1,
1153 1, 22, 1, 1, 3, 3, 1, 23, 2, 12, 24, 1, 1, 2, 1, 1,
1154 12, 23, 1, 1, 24, 1, 1, 1, 4, 1, 1, 1, 2, 1, 6, 6,
1155 4, 2, 1, 1, 1, 1, 1, 1, 1, 14, 13, 3, 1, 25, 9, 25,
1156 14, 1, 9, 3, 13, 1, 1, 1, 1, 1, 10, 1, 1, 2, 10, 2},
1159 {-20, -1, 0, 2, -2, 1, -1, 3, -3, 1, -1, 4, -4, 0, 2, -2,
1160 1, 5, -1, -5, 6, -6, 1, -1, 7, -7, 1, -1, 3, -3, 8, -8,
1161 2, -2, 1, -1, 9, -9, 1, -1, 10, -10, 4, -4, 11, 1, -11, -1,
1162 2, -2, 1, 12, -12, -1, 13, -13, 1, -1, 3, -3, 14, 5, -14, -5,
1163 -15, 15, -1, 1, 2, -2, 16, -16, 1, 17, -17, -1, 6, -6, 18, -18,
1164 2, -2, -19, 19, -3, 1, 3, -1, 4, 20, -4, 1, -21, 21, 1, 2,
1165 -1, -7, 7, -2, 22, -22, 23, 2, -23, -2, 1, -1, -24, 24, -25, 25,
1166 -8, -26, 26, 8, -27, 27, 5, 3, -3, -5, -4, 28, -28, 4, 29, -29,
1167 1, -1, -2, -30, 30, 2, 9, -9, -31, 31, 2, -2, -32, 3, 32, -33,
1168 -3, 1, 33, -34, -1, 34, -35, 35, -10, 10, -6, 36, 6, -36, 37, -37,
1169 -5, 38, 1, -38, -1, 3, 39, -39, -1, 40, 5, 1, -40, -3, 2, -11,
1170 -41, -2, 1, 11, -3, -4, 41, 3, 42, 4, -1, -43, -42, 43, 1, -44,
1171 45, -1, 44, -45, -7, 7, -46, 1, -12, 2, 1, -47, 46, 12, 47, 48,
1172 -2, -1, -48, 49, -1, -50, -49, 50, -6, -51, 51, 52, -13, 53, -4, 4,
1173 6, 13, -53, -52, -54, 55, 54, -55, -56, -2, 2, -8, 56, 1, -3, -1,
1174 2, 58, 3, 8, -2, 57, -58, -60, -59, -57, -3, 60, 59, -14, 3, 14}
1180 {1, 1, 0, 2, 2, 1, 1, 3, 3, 4, 4, 5, 5, 1, 1, 6,
1181 6, 2, 2, 7, 7, 8, 8, 1, 1, 3, 3, 9, 9, 10, 10, 1,
1182 1, 2, 2, 4, 4, 11, 0, 11, 12, 12, 13, 13, 1, 1, 5, 5,
1183 14, 14, 15, 16, 15, 16, 3, 3, 1, 6, 1, 6, 2, 2, 7, 7,
1184 8, 8, 17, 17, 1, 1, 4, 4, 18, 18, 2, 2, 1, 19, 1, 20,
1185 19, 20, 21, 21, 3, 3, 22, 22, 5, 5, 24, 1, 1, 23, 9, 23,
1186 24, 9, 2, 2, 10, 1, 1, 10, 6, 6, 25, 4, 4, 25, 7, 7,
1187 26, 8, 1, 8, 3, 1, 26, 3, 11, 11, 27, 27, 2, 28, 1, 2,
1188 28, 1, 12, 12, 5, 5, 29, 13, 13, 29, 32, 1, 1, 33, 31, 30,
1189 32, 4, 30, 33, 4, 31, 3, 14, 1, 1, 3, 34, 34, 2, 2, 14,
1190 6, 6, 35, 36, 35, 36, 1, 15, 1, 16, 16, 15, 7, 9, 7, 9,
1191 37, 8, 8, 37, 1, 1, 39, 2, 38, 39, 2, 40, 5, 38, 40, 5,
1192 3, 3, 4, 4, 10, 10, 1, 1, 1, 1, 41, 2, 41, 2, 6, 6,
1193 1, 1, 11, 42, 11, 43, 3, 42, 3, 17, 4, 43, 1, 17, 7, 1,
1194 8, 44, 4, 7, 44, 5, 8, 2, 5, 1, 2, 48, 45, 1, 12, 45,
1195 12, 48, 13, 13, 1, 9, 9, 46, 1, 46, 47, 47, 49, 18, 18, 49},
1198 { 1, -1, 0, 1, -1, 2, -2, 1, -1, 1, -1, 1, -1, 3, -3, 1,
1199 -1, -2, 2, 1, -1, 1, -1, 4, -4, -2, 2, 1, -1, 1, -1, 5,
1200 -5, -3, 3, 2, -2, 1, 0, -1, 1, -1, 1, -1, 6, -6, 2, -2,
1201 1, -1, 1, 1, -1, -1, -3, 3, 7, 2, -7, -2, -4, 4, 2, -2,
1202 2, -2, 1, -1, 8, -8, 3, -3, 1, -1, -5, 5, 9, 1, -9, 1,
1203 -1, -1, 1, -1, -4, 4, 1, -1, 3, -3, 1, -10, 10, 1, 2, -1,
1204 -1, -2, 6, -6, 2, 11, -11, -2, 3, -3, 1, -4, 4, -1, 3, -3,
1205 1, 3, 12, -3, -5, -12, -1, 5, 2, -2, 1, -1, -7, 1, 13, 7,
1206 -1, -13, 2, -2, 4, -4, 1, 2, -2, -1, 1, 14, -14, 1, 1, 1,
1207 -1, -5, -1, -1, 5, -1, -6, 2, -15, 15, 6, 1, -1, -8, 8, -2,
1208 -4, 4, 1, 1, -1, -1, 16, 2, -16, -2, 2, -2, 4, 3, -4, -3,
1209 -1, -4, 4, 1, -17, 17, -1, -9, 1, 1, 9, 1, -5, -1, -1, 5,
1210 -7, 7, 6, -6, 3, -3, 18, -18, 19, -19, 1, -10, -1, 10, -5, 5,
1211 20, -20, -3, 1, 3, 1, 8, -1, -8, 2, 7, -1, -21, -2, 5, 21,
1212 5, -1, -7, -5, 1, -6, -5, -11, 6, 22, 11, 1, 1, -22, -3, -1,
1213 3, -1, 3, -3, -23, 4, -4, 1, 23, -1, 1, -1, 1, -2, 2, -1}
1219 {1, 1, 1, 1, 0, 2, 2, 1, 1, 3, 3, 0, 1, 1, 2, 2,
1220 4, 4, 1, 1, 5, 5, 1, 1, 2, 2, 3, 3, 6, 6, 1, 1,
1221 7, 7, 8, 1, 8, 2, 2, 1, 4, 4, 1, 3, 1, 3, 9, 9,
1222 2, 2, 1, 5, 1, 5, 10, 10, 1, 1, 11, 11, 3, 6, 3, 4,
1223 4, 6, 2, 2, 1, 12, 1, 12, 7, 13, 7, 13, 1, 1, 8, 8,
1224 2, 2, 14, 14, 16, 15, 16, 5, 5, 1, 3, 15, 1, 3, 4, 4,
1225 1, 1, 17, 17, 2, 2, 6, 6, 1, 18, 1, 18, 22, 21, 22, 21,
1226 25, 24, 25, 19, 9, 20, 9, 23, 19, 24, 20, 3, 23, 7, 3, 1,
1227 1, 7, 28, 26, 29, 5, 28, 26, 5, 8, 29, 4, 8, 27, 2, 2,
1228 4, 27, 1, 1, 10, 36, 10, 33, 33, 36, 30, 1, 32, 32, 1, 30,
1229 6, 31, 31, 35, 3, 6, 11, 11, 3, 2, 35, 2, 34, 1, 34, 1,
1230 37, 37, 12, 7, 12, 5, 41, 5, 4, 7, 1, 8, 13, 4, 1, 41,
1231 13, 38, 8, 38, 9, 1, 40, 40, 9, 1, 39, 2, 2, 49, 39, 42,
1232 3, 3, 14, 16, 49, 14, 16, 42, 43, 43, 6, 6, 15, 1, 1, 15,
1233 44, 44, 1, 1, 50, 48, 4, 5, 4, 7, 5, 2, 10, 10, 48, 7,
1234 50, 45, 2, 1, 45, 8, 8, 1, 46, 46, 3, 47, 47, 3, 1, 1},
1237 { 1, -1, 2, -2, 0, 1, -1, 3, -3, 1, -1, 0, 4, -4, 2, -2,
1238 1, -1, 5, -5, 1, -1, 6, -6, 3, -3, 2, -2, 1, -1, 7, -7,
1239 1, -1, 1, 8, -1, 4, -4, -8, 2, -2, 9, 3, -9, -3, 1, -1,
1240 5, -5, 10, 2, -10, -2, 1, -1, 11, -11, 1, -1, -4, 2, 4, 3,
1241 -3, -2, 6, -6, 12, 1, -12, -1, 2, 1, -2, -1, 13, -13, 2, -2,
1242 7, -7, 1, -1, 1, 1, -1, 3, -3, 14, 5, -1, -14, -5, 4, -4,
1243 15, -15, 1, -1, 8, -8, -3, 3, 16, 1, -16, -1, 1, 1, -1, -1,
1244 1, 1, -1, 1, 2, 1, -2, 1, -1, -1, -1, 6, -1, 3, -6, 17,
1245 -17, -3, 1, 1, 1, 4, -1, -1, -4, 3, -1, 5, -3, -1, -9, 9,
1246 -5, 1, 18, -18, 2, 1, -2, 1, -1, -1, 1, 19, -1, 1, -19, -1,
1247 4, 1, -1, 1, 7, -4, -2, 2, -7, 10, -1, -10, 1, 20, -1, -20,
1248 1, -1, 2, 4, -2, 5, 1, -5, 6, -4, 21, 4, 2, -6, -21, -1,
1249 -2, 1, -4, -1, -3, 22, -1, 1, 3, -22, -1, 11, -11, 1, 1, 1,
1250 8, -8, 2, 2, -1, -2, -2, -1, 1, -1, -5, 5, 2, 23, -23, -2,
1251 1, -1, 24, -24, -1, -1, 7, 6, -7, 5, -6, 12, -3, 3, 1, -5,
1252 1, 1, -12, 25, -1, -5, 5, -25, -1, 1, 9, 1, -1, -9, 26, -26}