2 * common functions for Indeo Video Interactive codecs (Indeo4 and Indeo5)
4 * Copyright (c) 2009 Maxim Poliakovski
6 * This file is part of FFmpeg.
8 * FFmpeg is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU Lesser General Public
10 * License as published by the Free Software Foundation; either
11 * version 2.1 of the License, or (at your option) any later version.
13 * FFmpeg is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * Lesser General Public License for more details.
18 * You should have received a copy of the GNU Lesser General Public
19 * License along with FFmpeg; if not, write to the Free Software
20 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
25 * This file contains functions and data shared by both Indeo4 and
29 #define BITSTREAM_READER_LE
30 #include "libavutil/attributes.h"
35 #include "ivi_common.h"
38 extern const IVIHuffDesc ff_ivi_mb_huff_desc[8]; ///< static macroblock huffman tables
39 extern const IVIHuffDesc ff_ivi_blk_huff_desc[8]; ///< static block huffman tables
41 static VLC ivi_mb_vlc_tabs [8]; ///< static macroblock Huffman tables
42 static VLC ivi_blk_vlc_tabs[8]; ///< static block Huffman tables
45 * Reverse "nbits" bits of the value "val" and return the result
46 * in the least significant bits.
48 static uint16_t inv_bits(uint16_t val, int nbits)
53 res = ff_reverse[val] >> (8-nbits);
55 res = ((ff_reverse[val & 0xFF] << 8) + (ff_reverse[val >> 8])) >> (16-nbits);
61 * Generate a huffman codebook from the given descriptor
62 * and convert it into the FFmpeg VLC table.
64 * @param[in] cb pointer to codebook descriptor
65 * @param[out] vlc where to place the generated VLC table
66 * @param[in] flag flag: 1 - for static or 0 for dynamic tables
67 * @return result code: 0 - OK, -1 = error (invalid codebook descriptor)
69 static int ivi_create_huff_from_desc(const IVIHuffDesc *cb, VLC *vlc, int flag)
71 int pos, i, j, codes_per_row, prefix, not_last_row;
72 uint16_t codewords[256]; /* FIXME: move this temporal storage out? */
75 pos = 0; /* current position = 0 */
77 for (i = 0; i < cb->num_rows; i++) {
78 codes_per_row = 1 << cb->xbits[i];
79 not_last_row = (i != cb->num_rows - 1);
80 prefix = ((1 << i) - 1) << (cb->xbits[i] + not_last_row);
82 for (j = 0; j < codes_per_row; j++) {
83 if (pos >= 256) /* Some Indeo5 codebooks can have more than 256 */
84 break; /* elements, but only 256 codes are allowed! */
86 bits[pos] = i + cb->xbits[i] + not_last_row;
87 if (bits[pos] > IVI_VLC_BITS)
88 return AVERROR_INVALIDDATA; /* invalid descriptor */
90 codewords[pos] = inv_bits((prefix | j), bits[pos]);
98 /* number of codewords = pos */
99 return init_vlc(vlc, IVI_VLC_BITS, pos, bits, 1, 1, codewords, 2, 2,
100 (flag ? INIT_VLC_USE_NEW_STATIC : 0) | INIT_VLC_LE);
103 av_cold void ff_ivi_init_static_vlc(void)
106 static VLC_TYPE table_data[8192 * 16][2];
107 static int initialized_vlcs = 0;
109 if (initialized_vlcs)
111 for (i = 0; i < 8; i++) {
112 ivi_mb_vlc_tabs[i].table = table_data + i * 2 * 8192;
113 ivi_mb_vlc_tabs[i].table_allocated = 8192;
114 ivi_create_huff_from_desc(&ff_ivi_mb_huff_desc[i], &ivi_mb_vlc_tabs[i], 1);
115 ivi_blk_vlc_tabs[i].table = table_data + (i * 2 + 1) * 8192;
116 ivi_blk_vlc_tabs[i].table_allocated = 8192;
117 ivi_create_huff_from_desc(&ff_ivi_blk_huff_desc[i], &ivi_blk_vlc_tabs[i], 1);
119 initialized_vlcs = 1;
123 * Copy huffman codebook descriptors.
125 * @param[out] dst ptr to the destination descriptor
126 * @param[in] src ptr to the source descriptor
128 static void ivi_huff_desc_copy(IVIHuffDesc *dst, const IVIHuffDesc *src)
130 dst->num_rows = src->num_rows;
131 memcpy(dst->xbits, src->xbits, src->num_rows);
135 * Compare two huffman codebook descriptors.
137 * @param[in] desc1 ptr to the 1st descriptor to compare
138 * @param[in] desc2 ptr to the 2nd descriptor to compare
139 * @return comparison result: 0 - equal, 1 - not equal
141 static int ivi_huff_desc_cmp(const IVIHuffDesc *desc1, const IVIHuffDesc *desc2)
143 return desc1->num_rows != desc2->num_rows
144 || memcmp(desc1->xbits, desc2->xbits, desc1->num_rows);
147 int ff_ivi_dec_huff_desc(GetBitContext *gb, int desc_coded, int which_tab,
148 IVIHuffTab *huff_tab, AVCodecContext *avctx)
151 IVIHuffDesc new_huff;
154 /* select default table */
155 huff_tab->tab = (which_tab) ? &ivi_blk_vlc_tabs[7]
156 : &ivi_mb_vlc_tabs [7];
158 huff_tab->tab_sel = get_bits(gb, 3);
159 if (huff_tab->tab_sel == 7) {
160 /* custom huffman table (explicitly encoded) */
161 new_huff.num_rows = get_bits(gb, 4);
162 if (!new_huff.num_rows) {
163 av_log(avctx, AV_LOG_ERROR, "Empty custom Huffman table!\n");
164 return AVERROR_INVALIDDATA;
167 for (i = 0; i < new_huff.num_rows; i++)
168 new_huff.xbits[i] = get_bits(gb, 4);
170 /* Have we got the same custom table? Rebuild if not. */
171 if (ivi_huff_desc_cmp(&new_huff, &huff_tab->cust_desc) || !huff_tab->cust_tab.table) {
172 ivi_huff_desc_copy(&huff_tab->cust_desc, &new_huff);
174 if (huff_tab->cust_tab.table)
175 ff_free_vlc(&huff_tab->cust_tab);
176 result = ivi_create_huff_from_desc(&huff_tab->cust_desc,
177 &huff_tab->cust_tab, 0);
179 huff_tab->cust_desc.num_rows = 0; // reset faulty description
180 av_log(avctx, AV_LOG_ERROR,
181 "Error while initializing custom vlc table!\n");
185 huff_tab->tab = &huff_tab->cust_tab;
187 /* select one of predefined tables */
188 huff_tab->tab = (which_tab) ? &ivi_blk_vlc_tabs[huff_tab->tab_sel]
189 : &ivi_mb_vlc_tabs [huff_tab->tab_sel];
197 * Free planes, bands and macroblocks buffers.
199 * @param[in] planes pointer to the array of the plane descriptors
201 static av_cold void ivi_free_buffers(IVIPlaneDesc *planes)
205 for (p = 0; p < 3; p++) {
207 for (b = 0; b < planes[p].num_bands; b++) {
208 av_freep(&planes[p].bands[b].bufs[0]);
209 av_freep(&planes[p].bands[b].bufs[1]);
210 av_freep(&planes[p].bands[b].bufs[2]);
212 if (planes[p].bands[b].blk_vlc.cust_tab.table)
213 ff_free_vlc(&planes[p].bands[b].blk_vlc.cust_tab);
214 for (t = 0; t < planes[p].bands[b].num_tiles; t++)
215 av_freep(&planes[p].bands[b].tiles[t].mbs);
216 av_freep(&planes[p].bands[b].tiles);
218 av_freep(&planes[p].bands);
222 av_cold int ff_ivi_init_planes(IVIPlaneDesc *planes, const IVIPicConfig *cfg)
225 uint32_t b_width, b_height, align_fac, width_aligned, height_aligned, buf_size;
228 ivi_free_buffers(planes);
230 /* fill in the descriptor of the luminance plane */
231 planes[0].width = cfg->pic_width;
232 planes[0].height = cfg->pic_height;
233 planes[0].num_bands = cfg->luma_bands;
235 /* fill in the descriptors of the chrominance planes */
236 planes[1].width = planes[2].width = (cfg->pic_width + 3) >> 2;
237 planes[1].height = planes[2].height = (cfg->pic_height + 3) >> 2;
238 planes[1].num_bands = planes[2].num_bands = cfg->chroma_bands;
240 for (p = 0; p < 3; p++) {
241 planes[p].bands = av_mallocz(planes[p].num_bands * sizeof(IVIBandDesc));
242 if (!planes[p].bands)
243 return AVERROR(ENOMEM);
245 /* select band dimensions: if there is only one band then it
246 * has the full size, if there are several bands each of them
247 * has only half size */
248 b_width = planes[p].num_bands == 1 ? planes[p].width : (planes[p].width + 1) >> 1;
249 b_height = planes[p].num_bands == 1 ? planes[p].height : (planes[p].height + 1) >> 1;
251 /* luma band buffers will be aligned on 16x16 (max macroblock size) */
252 /* chroma band buffers will be aligned on 8x8 (max macroblock size) */
253 align_fac = p ? 8 : 16;
254 width_aligned = FFALIGN(b_width , align_fac);
255 height_aligned = FFALIGN(b_height, align_fac);
256 buf_size = width_aligned * height_aligned * sizeof(int16_t);
258 for (b = 0; b < planes[p].num_bands; b++) {
259 band = &planes[p].bands[b]; /* select appropriate plane/band */
262 band->width = b_width;
263 band->height = b_height;
264 band->pitch = width_aligned;
265 band->aheight = height_aligned;
266 band->bufs[0] = av_mallocz(buf_size);
267 band->bufs[1] = av_mallocz(buf_size);
268 band->bufsize = buf_size/2;
269 if (!band->bufs[0] || !band->bufs[1])
270 return AVERROR(ENOMEM);
272 /* allocate the 3rd band buffer for scalability mode */
273 if (cfg->luma_bands > 1) {
274 band->bufs[2] = av_mallocz(buf_size);
276 return AVERROR(ENOMEM);
279 planes[p].bands[0].blk_vlc.cust_desc.num_rows = 0; /* reset custom vlc */
286 av_cold int ff_ivi_init_tiles(IVIPlaneDesc *planes, int tile_width, int tile_height)
288 int p, b, x, y, x_tiles, y_tiles, t_width, t_height;
290 IVITile *tile, *ref_tile;
292 for (p = 0; p < 3; p++) {
293 t_width = !p ? tile_width : (tile_width + 3) >> 2;
294 t_height = !p ? tile_height : (tile_height + 3) >> 2;
296 if (!p && planes[0].num_bands == 4) {
300 if(t_width<=0 || t_height<=0)
301 return AVERROR(EINVAL);
303 for (b = 0; b < planes[p].num_bands; b++) {
304 band = &planes[p].bands[b];
305 x_tiles = IVI_NUM_TILES(band->width, t_width);
306 y_tiles = IVI_NUM_TILES(band->height, t_height);
307 band->num_tiles = x_tiles * y_tiles;
309 av_freep(&band->tiles);
310 band->tiles = av_mallocz(band->num_tiles * sizeof(IVITile));
312 return AVERROR(ENOMEM);
316 /* use the first luma band as reference for motion vectors
318 ref_tile = planes[0].bands[0].tiles;
320 for (y = 0; y < band->height; y += t_height) {
321 for (x = 0; x < band->width; x += t_width) {
324 tile->mb_size = band->mb_size;
325 tile->width = FFMIN(band->width - x, t_width);
326 tile->height = FFMIN(band->height - y, t_height);
327 tile->is_empty = tile->data_size = 0;
328 /* calculate number of macroblocks */
329 tile->num_MBs = IVI_MBs_PER_TILE(tile->width, tile->height,
332 av_freep(&tile->mbs);
333 tile->mbs = av_malloc(tile->num_MBs * sizeof(IVIMbInfo));
335 return AVERROR(ENOMEM);
339 if (tile->num_MBs <= ref_tile->num_MBs) {
340 tile->ref_mbs = ref_tile->mbs;
342 av_log(NULL, AV_LOG_DEBUG, "Cannot use ref_tile, too few mbs\n");
357 * Decode size of the tile data.
358 * The size is stored as a variable-length field having the following format:
359 * if (tile_data_size < 255) than this field is only one byte long
360 * if (tile_data_size >= 255) than this field four is byte long: 0xFF X1 X2 X3
361 * where X1-X3 is size of the tile data
363 * @param[in,out] gb the GetBit context
364 * @return size of the tile data in bytes
366 static int ivi_dec_tile_data_size(GetBitContext *gb)
372 len = get_bits(gb, 8);
374 len = get_bits_long(gb, 24);
377 /* align the bitstream reader on the byte boundary */
385 * extract huffman-coded transform coefficients from the bitstream,
386 * dequantize them, apply inverse transform and motion compensation
387 * in order to reconstruct the picture.
389 * @param[in,out] gb the GetBit context
390 * @param[in] band pointer to the band descriptor
391 * @param[in] tile pointer to the tile descriptor
392 * @return result code: 0 - OK, -1 = error (corrupted blocks data)
394 static int ivi_decode_blocks(GetBitContext *gb, IVIBandDesc *band, IVITile *tile,
395 AVCodecContext *avctx)
397 int mbn, blk, num_blocks, num_coeffs, blk_size, scan_pos, run, val,
398 pos, is_intra, mc_type = 0, av_uninit(mv_x), av_uninit(mv_y), col_mask;
399 uint8_t col_flags[8];
400 int32_t prev_dc, trvec[64];
401 uint32_t cbp, av_uninit(sym), lo, hi, quant, buf_offs, q;
403 RVMapDesc *rvmap = band->rv_map;
404 void (*mc_with_delta_func)(int16_t *buf, const int16_t *ref_buf, uint32_t pitch, int mc_type);
405 void (*mc_no_delta_func) (int16_t *buf, const int16_t *ref_buf, uint32_t pitch, int mc_type);
406 const uint16_t *base_tab;
407 const uint8_t *scale_tab;
409 prev_dc = 0; /* init intra prediction for the DC coefficient */
411 blk_size = band->blk_size;
412 col_mask = blk_size - 1; /* column mask for tracking non-zero coeffs */
413 num_blocks = (band->mb_size != blk_size) ? 4 : 1; /* number of blocks per mb */
414 num_coeffs = blk_size * blk_size;
416 mc_with_delta_func = ff_ivi_mc_8x8_delta;
417 mc_no_delta_func = ff_ivi_mc_8x8_no_delta;
419 mc_with_delta_func = ff_ivi_mc_4x4_delta;
420 mc_no_delta_func = ff_ivi_mc_4x4_no_delta;
423 for (mbn = 0, mb = tile->mbs; mbn < tile->num_MBs; mb++, mbn++) {
424 is_intra = !mb->type;
426 buf_offs = mb->buf_offs;
428 quant = band->glob_quant + mb->q_delta;
429 if (avctx->codec_id == AV_CODEC_ID_INDEO4)
430 quant = av_clip(quant, 0, 31);
432 quant = av_clip(quant, 0, 23);
434 base_tab = is_intra ? band->intra_base : band->inter_base;
435 scale_tab = is_intra ? band->intra_scale : band->inter_scale;
437 quant = scale_tab[quant];
442 if (band->is_halfpel) {
443 mc_type = ((mv_y & 1) << 1) | (mv_x & 1);
445 mv_y >>= 1; /* convert halfpel vectors into fullpel ones */
448 int dmv_x, dmv_y, cx, cy;
450 dmv_x = mb->mv_x >> band->is_halfpel;
451 dmv_y = mb->mv_y >> band->is_halfpel;
452 cx = mb->mv_x & band->is_halfpel;
453 cy = mb->mv_y & band->is_halfpel;
455 if ( mb->xpos + dmv_x < 0
456 || mb->xpos + dmv_x + band->mb_size + cx > band->pitch
457 || mb->ypos + dmv_y < 0
458 || mb->ypos + dmv_y + band->mb_size + cy > band->aheight) {
459 return AVERROR_INVALIDDATA;
464 for (blk = 0; blk < num_blocks; blk++) {
465 /* adjust block position in the buffer according to its number */
467 buf_offs += blk_size;
468 } else if (blk == 2) {
469 buf_offs -= blk_size;
470 buf_offs += blk_size * band->pitch;
473 if (cbp & 1) { /* block coded ? */
475 av_log(avctx, AV_LOG_ERROR, "Scan pattern is not set.\n");
476 return AVERROR_INVALIDDATA;
480 memset(trvec, 0, num_coeffs*sizeof(trvec[0])); /* zero transform vector */
481 memset(col_flags, 0, sizeof(col_flags)); /* zero column flags */
483 while (scan_pos <= num_coeffs) {
484 sym = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
485 if (sym == rvmap->eob_sym)
486 break; /* End of block */
488 if (sym == rvmap->esc_sym) { /* Escape - run/val explicitly coded using 3 vlc codes */
489 run = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1) + 1;
490 lo = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
491 hi = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
492 val = IVI_TOSIGNED((hi << 6) | lo); /* merge them and convert into signed val */
495 av_log(avctx, AV_LOG_ERROR, "Invalid sym encountered: %d.\n", sym);
496 return AVERROR_INVALIDDATA;
498 run = rvmap->runtab[sym];
499 val = rvmap->valtab[sym];
502 /* de-zigzag and dequantize */
504 if (scan_pos >= (unsigned)num_coeffs)
506 pos = band->scan[scan_pos];
509 av_dlog(avctx, "Val = 0 encountered!\n");
511 q = (base_tab[pos] * quant) >> 9;
513 val = val * q + FFSIGN(val) * (((q ^ 1) - 1) >> 1);
515 col_flags[pos & col_mask] |= !!val; /* track columns containing non-zero coeffs */
518 if (scan_pos >= num_coeffs && sym != rvmap->eob_sym)
519 return AVERROR_INVALIDDATA; /* corrupt block data */
521 /* undoing DC coeff prediction for intra-blocks */
522 if (is_intra && band->is_2d_trans) {
525 col_flags[0] |= !!prev_dc;
527 if(band->transform_size > band->blk_size){
528 av_log(NULL, AV_LOG_ERROR, "Too large transform\n");
529 return AVERROR_INVALIDDATA;
531 /* apply inverse transform */
532 band->inv_transform(trvec, band->buf + buf_offs,
533 band->pitch, col_flags);
535 /* apply motion compensation */
537 mc_with_delta_func(band->buf + buf_offs,
538 band->ref_buf + buf_offs + mv_y * band->pitch + mv_x,
539 band->pitch, mc_type);
541 /* block not coded */
542 /* for intra blocks apply the dc slant transform */
543 /* for inter - perform the motion compensation without delta */
545 band->dc_transform(&prev_dc, band->buf + buf_offs,
546 band->pitch, blk_size);
548 mc_no_delta_func(band->buf + buf_offs,
549 band->ref_buf + buf_offs + mv_y * band->pitch + mv_x,
550 band->pitch, mc_type);
563 * Handle empty tiles by performing data copying and motion
564 * compensation respectively.
566 * @param[in] avctx ptr to the AVCodecContext
567 * @param[in] band pointer to the band descriptor
568 * @param[in] tile pointer to the tile descriptor
569 * @param[in] mv_scale scaling factor for motion vectors
571 static int ivi_process_empty_tile(AVCodecContext *avctx, IVIBandDesc *band,
572 IVITile *tile, int32_t mv_scale)
574 int x, y, need_mc, mbn, blk, num_blocks, mv_x, mv_y, mc_type;
575 int offs, mb_offset, row_offset;
576 IVIMbInfo *mb, *ref_mb;
579 void (*mc_no_delta_func)(int16_t *buf, const int16_t *ref_buf, uint32_t pitch,
582 if (tile->num_MBs != IVI_MBs_PER_TILE(tile->width, tile->height, band->mb_size)) {
583 av_log(avctx, AV_LOG_ERROR, "Allocated tile size %d mismatches "
584 "parameters %d in ivi_process_empty_tile()\n",
585 tile->num_MBs, IVI_MBs_PER_TILE(tile->width, tile->height, band->mb_size));
586 return AVERROR_INVALIDDATA;
589 offs = tile->ypos * band->pitch + tile->xpos;
591 ref_mb = tile->ref_mbs;
592 row_offset = band->mb_size * band->pitch;
593 need_mc = 0; /* reset the mc tracking flag */
595 for (y = tile->ypos; y < (tile->ypos + tile->height); y += band->mb_size) {
598 for (x = tile->xpos; x < (tile->xpos + tile->width); x += band->mb_size) {
601 mb->buf_offs = mb_offset;
603 mb->type = 1; /* set the macroblocks type = INTER */
604 mb->cbp = 0; /* all blocks are empty */
606 if (!band->qdelta_present && !band->plane && !band->band_num) {
607 mb->q_delta = band->glob_quant;
612 if (band->inherit_qdelta && ref_mb)
613 mb->q_delta = ref_mb->q_delta;
615 if (band->inherit_mv && ref_mb) {
616 /* motion vector inheritance */
618 mb->mv_x = ivi_scale_mv(ref_mb->mv_x, mv_scale);
619 mb->mv_y = ivi_scale_mv(ref_mb->mv_y, mv_scale);
621 mb->mv_x = ref_mb->mv_x;
622 mb->mv_y = ref_mb->mv_y;
624 need_mc |= mb->mv_x || mb->mv_y; /* tracking non-zero motion vectors */
626 int dmv_x, dmv_y, cx, cy;
628 dmv_x = mb->mv_x >> band->is_halfpel;
629 dmv_y = mb->mv_y >> band->is_halfpel;
630 cx = mb->mv_x & band->is_halfpel;
631 cy = mb->mv_y & band->is_halfpel;
633 if ( mb->xpos + dmv_x < 0
634 || mb->xpos + dmv_x + band->mb_size + cx > band->pitch
635 || mb->ypos + dmv_y < 0
636 || mb->ypos + dmv_y + band->mb_size + cy > band->aheight) {
637 av_log(avctx, AV_LOG_ERROR, "MV out of bounds\n");
638 return AVERROR_INVALIDDATA;
646 mb_offset += band->mb_size;
651 if (band->inherit_mv && need_mc) { /* apply motion compensation if there is at least one non-zero motion vector */
652 num_blocks = (band->mb_size != band->blk_size) ? 4 : 1; /* number of blocks per mb */
653 mc_no_delta_func = (band->blk_size == 8) ? ff_ivi_mc_8x8_no_delta
654 : ff_ivi_mc_4x4_no_delta;
656 for (mbn = 0, mb = tile->mbs; mbn < tile->num_MBs; mb++, mbn++) {
659 if (!band->is_halfpel) {
660 mc_type = 0; /* we have only fullpel vectors */
662 mc_type = ((mv_y & 1) << 1) | (mv_x & 1);
664 mv_y >>= 1; /* convert halfpel vectors into fullpel ones */
667 for (blk = 0; blk < num_blocks; blk++) {
668 /* adjust block position in the buffer according with its number */
669 offs = mb->buf_offs + band->blk_size * ((blk & 1) + !!(blk & 2) * band->pitch);
670 mc_no_delta_func(band->buf + offs,
671 band->ref_buf + offs + mv_y * band->pitch + mv_x,
672 band->pitch, mc_type);
676 /* copy data from the reference tile into the current one */
677 src = band->ref_buf + tile->ypos * band->pitch + tile->xpos;
678 dst = band->buf + tile->ypos * band->pitch + tile->xpos;
679 for (y = 0; y < tile->height; y++) {
680 memcpy(dst, src, tile->width*sizeof(band->buf[0]));
691 static uint16_t ivi_calc_band_checksum(IVIBandDesc *band)
694 int16_t *src, checksum;
699 for (y = 0; y < band->height; src += band->pitch, y++)
700 for (x = 0; x < band->width; x++)
708 * Convert and output the current plane.
709 * This conversion is done by adding back the bias value of 128
710 * (subtracted in the encoder) and clipping the result.
712 * @param[in] plane pointer to the descriptor of the plane being processed
713 * @param[out] dst pointer to the buffer receiving converted pixels
714 * @param[in] dst_pitch pitch for moving to the next y line
716 static void ivi_output_plane(IVIPlaneDesc *plane, uint8_t *dst, int dst_pitch)
719 const int16_t *src = plane->bands[0].buf;
720 uint32_t pitch = plane->bands[0].pitch;
725 for (y = 0; y < plane->height; y++) {
726 for (x = 0; x < plane->width; x++)
727 dst[x] = av_clip_uint8(src[x] + 128);
734 * Decode an Indeo 4 or 5 band.
736 * @param[in,out] ctx ptr to the decoder context
737 * @param[in,out] band ptr to the band descriptor
738 * @param[in] avctx ptr to the AVCodecContext
739 * @return result code: 0 = OK, -1 = error
741 static int decode_band(IVI45DecContext *ctx,
742 IVIBandDesc *band, AVCodecContext *avctx)
744 int result, i, t, idx1, idx2, pos;
747 band->buf = band->bufs[ctx->dst_buf];
749 av_log(avctx, AV_LOG_ERROR, "Band buffer points to no data!\n");
750 return AVERROR_INVALIDDATA;
752 band->ref_buf = band->bufs[ctx->ref_buf];
753 band->data_ptr = ctx->frame_data + (get_bits_count(&ctx->gb) >> 3);
755 result = ctx->decode_band_hdr(ctx, band, avctx);
757 av_log(avctx, AV_LOG_ERROR, "Error while decoding band header: %d\n",
762 if (band->is_empty) {
763 av_log(avctx, AV_LOG_ERROR, "Empty band encountered!\n");
764 return AVERROR_INVALIDDATA;
767 band->rv_map = &ctx->rvmap_tabs[band->rvmap_sel];
769 /* apply corrections to the selected rvmap table if present */
770 for (i = 0; i < band->num_corr; i++) {
771 idx1 = band->corr[i * 2];
772 idx2 = band->corr[i * 2 + 1];
773 FFSWAP(uint8_t, band->rv_map->runtab[idx1], band->rv_map->runtab[idx2]);
774 FFSWAP(int16_t, band->rv_map->valtab[idx1], band->rv_map->valtab[idx2]);
775 if (idx1 == band->rv_map->eob_sym || idx2 == band->rv_map->eob_sym)
776 band->rv_map->eob_sym ^= idx1 ^ idx2;
777 if (idx1 == band->rv_map->esc_sym || idx2 == band->rv_map->esc_sym)
778 band->rv_map->esc_sym ^= idx1 ^ idx2;
781 pos = get_bits_count(&ctx->gb);
783 for (t = 0; t < band->num_tiles; t++) {
784 tile = &band->tiles[t];
786 if (tile->mb_size != band->mb_size) {
787 av_log(avctx, AV_LOG_ERROR, "MB sizes mismatch: %d vs. %d\n",
788 band->mb_size, tile->mb_size);
789 return AVERROR_INVALIDDATA;
791 tile->is_empty = get_bits1(&ctx->gb);
792 if (tile->is_empty) {
793 result = ivi_process_empty_tile(avctx, band, tile,
794 (ctx->planes[0].bands[0].mb_size >> 3) - (band->mb_size >> 3));
797 av_dlog(avctx, "Empty tile encountered!\n");
799 tile->data_size = ivi_dec_tile_data_size(&ctx->gb);
800 if (!tile->data_size) {
801 av_log(avctx, AV_LOG_ERROR, "Tile data size is zero!\n");
802 result = AVERROR_INVALIDDATA;
806 result = ctx->decode_mb_info(ctx, band, tile, avctx);
810 result = ivi_decode_blocks(&ctx->gb, band, tile, avctx);
812 av_log(avctx, AV_LOG_ERROR,
813 "Corrupted tile data encountered!\n");
817 if (((get_bits_count(&ctx->gb) - pos) >> 3) != tile->data_size) {
818 av_log(avctx, AV_LOG_ERROR,
819 "Tile data_size mismatch!\n");
820 result = AVERROR_INVALIDDATA;
824 pos += tile->data_size << 3; // skip to next tile
828 /* restore the selected rvmap table by applying its corrections in reverse order */
829 for (i = band->num_corr-1; i >= 0; i--) {
830 idx1 = band->corr[i*2];
831 idx2 = band->corr[i*2+1];
832 FFSWAP(uint8_t, band->rv_map->runtab[idx1], band->rv_map->runtab[idx2]);
833 FFSWAP(int16_t, band->rv_map->valtab[idx1], band->rv_map->valtab[idx2]);
834 if (idx1 == band->rv_map->eob_sym || idx2 == band->rv_map->eob_sym)
835 band->rv_map->eob_sym ^= idx1 ^ idx2;
836 if (idx1 == band->rv_map->esc_sym || idx2 == band->rv_map->esc_sym)
837 band->rv_map->esc_sym ^= idx1 ^ idx2;
841 if (band->checksum_present) {
842 uint16_t chksum = ivi_calc_band_checksum(band);
843 if (chksum != band->checksum) {
844 av_log(avctx, AV_LOG_ERROR,
845 "Band checksum mismatch! Plane %d, band %d, received: %x, calculated: %x\n",
846 band->plane, band->band_num, band->checksum, chksum);
851 align_get_bits(&ctx->gb);
856 int ff_ivi_decode_frame(AVCodecContext *avctx, void *data, int *got_frame,
859 IVI45DecContext *ctx = avctx->priv_data;
860 const uint8_t *buf = avpkt->data;
861 AVFrame *frame = data;
862 int buf_size = avpkt->size;
865 init_get_bits(&ctx->gb, buf, buf_size * 8);
866 ctx->frame_data = buf;
867 ctx->frame_size = buf_size;
869 result = ctx->decode_pic_hdr(ctx, avctx);
871 av_log(avctx, AV_LOG_ERROR,
872 "Error while decoding picture header: %d\n", result);
875 if (ctx->gop_invalid)
876 return AVERROR_INVALIDDATA;
878 if (ctx->gop_flags & IVI5_IS_PROTECTED) {
879 avpriv_report_missing_feature(avctx, "Password-protected clip!\n");
880 return AVERROR_PATCHWELCOME;
883 ctx->switch_buffers(ctx);
887 if (ctx->is_nonnull_frame(ctx)) {
888 ctx->buf_invalid[ctx->dst_buf] = 1;
889 for (p = 0; p < 3; p++) {
890 for (b = 0; b < ctx->planes[p].num_bands; b++) {
891 result = decode_band(ctx, &ctx->planes[p].bands[b], avctx);
893 av_log(avctx, AV_LOG_ERROR,
894 "Error while decoding band: %d, plane: %d\n", b, p);
899 ctx->buf_invalid[ctx->dst_buf] = 0;
901 if (ctx->buf_invalid[ctx->dst_buf])
904 //STOP_TIMER("decode_planes"); }
906 /* If the bidirectional mode is enabled, next I and the following P frame will */
907 /* be sent together. Unfortunately the approach below seems to be the only way */
908 /* to handle the B-frames mode. That's exactly the same Intel decoders do. */
909 if (avctx->codec_id == AV_CODEC_ID_INDEO4 && ctx->frame_type == 0/*FRAMETYPE_INTRA*/) {
910 while (get_bits(&ctx->gb, 8)); // skip version string
911 skip_bits_long(&ctx->gb, 64); // skip padding, TODO: implement correct 8-bytes alignment
912 if (get_bits_left(&ctx->gb) > 18 && show_bits(&ctx->gb, 18) == 0x3FFF8)
913 av_log(avctx, AV_LOG_ERROR, "Buffer contains IP frames!\n");
916 if (!ctx->is_nonnull_frame(ctx))
919 avcodec_set_dimensions(avctx, ctx->planes[0].width, ctx->planes[0].height);
920 if ((result = ff_get_buffer(avctx, frame, 0)) < 0)
923 if (ctx->is_scalable) {
924 if (avctx->codec_id == AV_CODEC_ID_INDEO4)
925 ff_ivi_recompose_haar(&ctx->planes[0], frame->data[0], frame->linesize[0]);
927 ff_ivi_recompose53 (&ctx->planes[0], frame->data[0], frame->linesize[0]);
929 ivi_output_plane(&ctx->planes[0], frame->data[0], frame->linesize[0]);
932 ivi_output_plane(&ctx->planes[2], frame->data[1], frame->linesize[1]);
933 ivi_output_plane(&ctx->planes[1], frame->data[2], frame->linesize[2]);
941 * Close Indeo5 decoder and clean up its context.
943 av_cold int ff_ivi_decode_close(AVCodecContext *avctx)
945 IVI45DecContext *ctx = avctx->priv_data;
947 ivi_free_buffers(&ctx->planes[0]);
949 if (ctx->mb_vlc.cust_tab.table)
950 ff_free_vlc(&ctx->mb_vlc.cust_tab);
952 #if IVI4_STREAM_ANALYSER
953 if (avctx->codec_id == AV_CODEC_ID_INDEO4) {
954 if (ctx->is_scalable)
955 av_log(avctx, AV_LOG_ERROR, "This video uses scalability mode!\n");
956 if (ctx->uses_tiling)
957 av_log(avctx, AV_LOG_ERROR, "This video uses local decoding!\n");
958 if (ctx->has_b_frames)
959 av_log(avctx, AV_LOG_ERROR, "This video contains B-frames!\n");
961 av_log(avctx, AV_LOG_ERROR, "Transparency mode is enabled!\n");
963 av_log(avctx, AV_LOG_ERROR, "This video uses Haar transform!\n");
964 if (ctx->uses_fullpel)
965 av_log(avctx, AV_LOG_ERROR, "This video uses fullpel motion vectors!\n");
974 * These are 2x8 predefined Huffman codebooks for coding macroblock/block
975 * signals. They are specified using "huffman descriptors" in order to
976 * avoid huge static tables. The decoding tables will be generated at
977 * startup from these descriptors.
979 const IVIHuffDesc ff_ivi_mb_huff_desc[8] = {
980 {8, {0, 4, 5, 4, 4, 4, 6, 6}},
981 {12, {0, 2, 2, 3, 3, 3, 3, 5, 3, 2, 2, 2}},
982 {12, {0, 2, 3, 4, 3, 3, 3, 3, 4, 3, 2, 2}},
983 {12, {0, 3, 4, 4, 3, 3, 3, 3, 3, 2, 2, 2}},
984 {13, {0, 4, 4, 3, 3, 3, 3, 2, 3, 3, 2, 1, 1}},
985 {9, {0, 4, 4, 4, 4, 3, 3, 3, 2}},
986 {10, {0, 4, 4, 4, 4, 3, 3, 2, 2, 2}},
987 {12, {0, 4, 4, 4, 3, 3, 2, 3, 2, 2, 2, 2}}
990 const IVIHuffDesc ff_ivi_blk_huff_desc[8] = {
991 {10, {1, 2, 3, 4, 4, 7, 5, 5, 4, 1}},
992 {11, {2, 3, 4, 4, 4, 7, 5, 4, 3, 3, 2}},
993 {12, {2, 4, 5, 5, 5, 5, 6, 4, 4, 3, 1, 1}},
994 {13, {3, 3, 4, 4, 5, 6, 6, 4, 4, 3, 2, 1, 1}},
995 {11, {3, 4, 4, 5, 5, 5, 6, 5, 4, 2, 2}},
996 {13, {3, 4, 5, 5, 5, 5, 6, 4, 3, 3, 2, 1, 1}},
997 {13, {3, 4, 5, 5, 5, 6, 5, 4, 3, 3, 2, 1, 1}},
998 {9, {3, 4, 4, 5, 5, 5, 6, 5, 5}}
1003 * Scan patterns shared between indeo4 and indeo5
1005 const uint8_t ff_ivi_vertical_scan_8x8[64] = {
1006 0, 8, 16, 24, 32, 40, 48, 56,
1007 1, 9, 17, 25, 33, 41, 49, 57,
1008 2, 10, 18, 26, 34, 42, 50, 58,
1009 3, 11, 19, 27, 35, 43, 51, 59,
1010 4, 12, 20, 28, 36, 44, 52, 60,
1011 5, 13, 21, 29, 37, 45, 53, 61,
1012 6, 14, 22, 30, 38, 46, 54, 62,
1013 7, 15, 23, 31, 39, 47, 55, 63
1016 const uint8_t ff_ivi_horizontal_scan_8x8[64] = {
1017 0, 1, 2, 3, 4, 5, 6, 7,
1018 8, 9, 10, 11, 12, 13, 14, 15,
1019 16, 17, 18, 19, 20, 21, 22, 23,
1020 24, 25, 26, 27, 28, 29, 30, 31,
1021 32, 33, 34, 35, 36, 37, 38, 39,
1022 40, 41, 42, 43, 44, 45, 46, 47,
1023 48, 49, 50, 51, 52, 53, 54, 55,
1024 56, 57, 58, 59, 60, 61, 62, 63
1027 const uint8_t ff_ivi_direct_scan_4x4[16] = {
1028 0, 1, 4, 8, 5, 2, 3, 6, 9, 12, 13, 10, 7, 11, 14, 15
1033 * Run-value (RLE) tables.
1035 const RVMapDesc ff_ivi_rvmap_tabs[9] = {
1040 {1, 1, 0, 1, 1, 0, 1, 1, 2, 2, 1, 1, 1, 1, 3, 3,
1041 1, 1, 2, 2, 1, 1, 4, 4, 1, 1, 1, 1, 2, 2, 5, 5,
1042 1, 1, 3, 3, 1, 1, 6, 6, 1, 2, 1, 2, 7, 7, 1, 1,
1043 8, 8, 1, 1, 4, 2, 1, 4, 2, 1, 3, 3, 1, 1, 1, 9,
1044 9, 1, 2, 1, 2, 1, 5, 5, 1, 1, 10, 10, 1, 1, 3, 3,
1045 2, 2, 1, 1, 11, 11, 6, 4, 4, 1, 6, 1, 2, 1, 2, 12,
1046 8, 1, 12, 7, 8, 7, 1, 16, 1, 16, 1, 3, 3, 13, 1, 13,
1047 2, 2, 1, 15, 1, 5, 14, 15, 1, 5, 14, 1, 17, 8, 17, 8,
1048 1, 4, 4, 2, 2, 1, 25, 25, 24, 24, 1, 3, 1, 3, 1, 8,
1049 6, 7, 6, 1, 18, 8, 18, 1, 7, 23, 2, 2, 23, 1, 1, 21,
1050 22, 9, 9, 22, 19, 1, 21, 5, 19, 5, 1, 33, 20, 33, 20, 8,
1051 4, 4, 1, 32, 2, 2, 8, 3, 32, 26, 3, 1, 7, 7, 26, 6,
1052 1, 6, 1, 1, 16, 1, 10, 1, 10, 2, 16, 29, 28, 2, 29, 28,
1053 1, 27, 5, 8, 5, 27, 1, 8, 3, 7, 3, 31, 41, 31, 1, 41,
1054 6, 1, 6, 7, 4, 4, 1, 1, 2, 1, 2, 11, 34, 30, 11, 1,
1055 30, 15, 15, 34, 36, 40, 36, 40, 35, 35, 37, 37, 39, 39, 38, 38},
1058 { 1, -1, 0, 2, -2, 0, 3, -3, 1, -1, 4, -4, 5, -5, 1, -1,
1059 6, -6, 2, -2, 7, -7, 1, -1, 8, -8, 9, -9, 3, -3, 1, -1,
1060 10, -10, 2, -2, 11, -11, 1, -1, 12, 4, -12, -4, 1, -1, 13, -13,
1061 1, -1, 14, -14, 2, 5, 15, -2, -5, -15, -3, 3, 16, -16, 17, 1,
1062 -1, -17, 6, 18, -6, -18, 2, -2, 19, -19, 1, -1, 20, -20, 4, -4,
1063 7, -7, 21, -21, 1, -1, 2, 3, -3, 22, -2, -22, 8, 23, -8, 1,
1064 2, -23, -1, 2, -2, -2, 24, 1, -24, -1, 25, 5, -5, 1, -25, -1,
1065 9, -9, 26, 1, -26, 3, 1, -1, 27, -3, -1, -27, 1, 3, -1, -3,
1066 28, -4, 4, 10, -10, -28, 1, -1, 1, -1, 29, 6, -29, -6, 30, -4,
1067 3, 3, -3, -30, 1, 4, -1, 31, -3, 1, 11, -11, -1, -31, 32, -1,
1068 -1, 2, -2, 1, 1, -32, 1, 4, -1, -4, 33, -1, 1, 1, -1, 5,
1069 5, -5, -33, -1, -12, 12, -5, -7, 1, 1, 7, 34, 4, -4, -1, 4,
1070 -34, -4, 35, 36, -2, -35, -2, -36, 2, 13, 2, -1, 1, -13, 1, -1,
1071 37, 1, -5, 6, 5, -1, 38, -6, -8, 5, 8, -1, 1, 1, -37, -1,
1072 5, 39, -5, -5, 6, -6, -38, -39, -14, 40, 14, 2, 1, 1, -2, -40,
1073 -1, -2, 2, -1, -1, -1, 1, 1, 1, -1, 1, -1, 1, -1, 1, -1}
1079 {0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 8, 6, 8, 7,
1080 7, 9, 9, 10, 10, 11, 11, 1, 12, 1, 12, 13, 13, 16, 14, 16,
1081 14, 15, 15, 17, 17, 18, 0, 18, 19, 20, 21, 19, 22, 21, 20, 22,
1082 25, 24, 2, 25, 24, 23, 23, 2, 26, 28, 26, 28, 29, 27, 29, 27,
1083 33, 33, 1, 32, 1, 3, 32, 30, 36, 3, 36, 30, 31, 31, 35, 34,
1084 37, 41, 34, 35, 37, 4, 41, 4, 49, 8, 8, 49, 40, 38, 5, 38,
1085 40, 39, 5, 39, 42, 43, 42, 7, 57, 6, 43, 44, 6, 50, 7, 44,
1086 57, 48, 50, 48, 45, 45, 46, 47, 51, 46, 47, 58, 1, 51, 58, 1,
1087 52, 59, 53, 9, 52, 55, 55, 59, 53, 56, 54, 56, 54, 9, 64, 64,
1088 60, 63, 60, 63, 61, 62, 61, 62, 2, 10, 2, 10, 11, 1, 11, 13,
1089 12, 1, 12, 13, 16, 16, 8, 8, 14, 3, 3, 15, 14, 15, 4, 4,
1090 1, 17, 17, 5, 1, 7, 7, 5, 6, 1, 2, 2, 6, 22, 1, 25,
1091 21, 22, 8, 24, 1, 21, 25, 24, 8, 18, 18, 23, 9, 20, 23, 33,
1092 29, 33, 20, 1, 19, 1, 29, 36, 9, 36, 19, 41, 28, 57, 32, 3,
1093 28, 3, 1, 27, 49, 49, 1, 32, 26, 26, 2, 4, 4, 7, 57, 41,
1094 2, 7, 10, 5, 37, 16, 10, 27, 8, 8, 13, 16, 37, 13, 1, 5},
1097 {0, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, 1, -1, -1, 1,
1098 -1, 1, -1, 1, -1, 1, -1, 2, 1, -2, -1, 1, -1, 1, 1, -1,
1099 -1, 1, -1, 1, -1, 1, 0, -1, 1, 1, 1, -1, 1, -1, -1, -1,
1100 1, 1, 2, -1, -1, 1, -1, -2, 1, 1, -1, -1, 1, 1, -1, -1,
1101 1, -1, 3, 1, -3, 2, -1, 1, 1, -2, -1, -1, -1, 1, 1, 1,
1102 1, 1, -1, -1, -1, 2, -1, -2, 1, 2, -2, -1, 1, 1, 2, -1,
1103 -1, 1, -2, -1, 1, 1, -1, 2, 1, 2, -1, 1, -2, -1, -2, -1,
1104 -1, 1, 1, -1, 1, -1, 1, 1, 1, -1, -1, 1, 4, -1, -1, -4,
1105 1, 1, 1, 2, -1, -1, 1, -1, -1, 1, -1, -1, 1, -2, 1, -1,
1106 1, 1, -1, -1, 1, 1, -1, -1, 3, 2, -3, -2, 2, 5, -2, 2,
1107 2, -5, -2, -2, -2, 2, -3, 3, 2, 3, -3, 2, -2, -2, 3, -3,
1108 6, 2, -2, 3, -6, 3, -3, -3, 3, 7, -4, 4, -3, 2, -7, 2,
1109 2, -2, -4, 2, 8, -2, -2, -2, 4, 2, -2, 2, 3, 2, -2, -2,
1110 2, 2, -2, -8, -2, 9, -2, 2, -3, -2, 2, -2, 2, 2, 2, 4,
1111 -2, -4, 10, 2, 2, -2, -9, -2, 2, -2, 5, 4, -4, 4, -2, 2,
1112 -5, -4, -3, 4, 2, -3, 3, -2, -5, 5, 3, 3, -2, -3, -10, -4}
1118 {1, 1, 0, 2, 2, 1, 1, 3, 3, 4, 4, 0, 1, 1, 5, 5,
1119 2, 2, 6, 6, 7, 7, 1, 8, 1, 8, 3, 3, 9, 9, 1, 2,
1120 2, 1, 4, 10, 4, 10, 11, 11, 1, 5, 12, 12, 1, 5, 13, 13,
1121 3, 3, 6, 6, 2, 2, 14, 14, 16, 16, 15, 7, 15, 8, 8, 7,
1122 1, 1, 17, 17, 4, 4, 1, 1, 18, 18, 2, 2, 5, 5, 25, 3,
1123 9, 3, 25, 9, 19, 24, 19, 24, 1, 21, 20, 1, 21, 22, 20, 22,
1124 23, 23, 8, 6, 33, 6, 8, 33, 7, 7, 26, 26, 1, 32, 1, 32,
1125 28, 4, 28, 10, 29, 27, 27, 10, 41, 4, 29, 2, 2, 41, 36, 31,
1126 49, 31, 34, 30, 34, 36, 30, 35, 1, 49, 11, 5, 35, 11, 1, 3,
1127 3, 5, 37, 37, 8, 40, 8, 40, 12, 12, 42, 42, 1, 38, 16, 57,
1128 1, 6, 16, 39, 38, 6, 7, 7, 13, 13, 39, 43, 2, 43, 57, 2,
1129 50, 9, 44, 9, 50, 4, 15, 48, 44, 4, 1, 15, 48, 14, 14, 1,
1130 45, 45, 8, 3, 5, 8, 51, 47, 3, 46, 46, 47, 5, 51, 1, 17,
1131 17, 58, 1, 58, 2, 52, 52, 2, 53, 7, 59, 6, 6, 56, 53, 55,
1132 7, 55, 1, 54, 59, 56, 54, 10, 1, 10, 4, 60, 1, 60, 8, 4,
1133 8, 64, 64, 61, 1, 63, 3, 63, 62, 61, 5, 11, 5, 3, 11, 62},
1136 { 1, -1, 0, 1, -1, 2, -2, 1, -1, 1, -1, 0, 3, -3, 1, -1,
1137 2, -2, 1, -1, 1, -1, 4, 1, -4, -1, 2, -2, 1, -1, 5, 3,
1138 -3, -5, 2, 1, -2, -1, 1, -1, 6, 2, 1, -1, -6, -2, 1, -1,
1139 3, -3, 2, -2, 4, -4, 1, -1, 1, -1, 1, 2, -1, 2, -2, -2,
1140 7, -7, 1, -1, 3, -3, 8, -8, 1, -1, 5, -5, 3, -3, 1, 4,
1141 2, -4, -1, -2, 1, 1, -1, -1, 9, 1, 1, -9, -1, 1, -1, -1,
1142 1, -1, 3, -3, 1, 3, -3, -1, 3, -3, 1, -1, 10, 1, -10, -1,
1143 1, 4, -1, 2, 1, -1, 1, -2, 1, -4, -1, 6, -6, -1, 1, 1,
1144 1, -1, 1, 1, -1, -1, -1, 1, 11, -1, -2, 4, -1, 2, -11, 5,
1145 -5, -4, -1, 1, 4, 1, -4, -1, -2, 2, 1, -1, 12, 1, -2, 1,
1146 -12, 4, 2, 1, -1, -4, 4, -4, 2, -2, -1, 1, 7, -1, -1, -7,
1147 -1, -3, 1, 3, 1, 5, 2, 1, -1, -5, 13, -2, -1, 2, -2, -13,
1148 1, -1, 5, 6, 5, -5, 1, 1, -6, 1, -1, -1, -5, -1, 14, 2,
1149 -2, 1, -14, -1, 8, 1, -1, -8, 1, 5, 1, 5, -5, 1, -1, 1,
1150 -5, -1, 15, 1, -1, -1, -1, 3, -15, -3, 6, 1, 16, -1, 6, -6,
1151 -6, 1, -1, 1, -16, 1, 7, -1, 1, -1, -6, -3, 6, -7, 3, -1}
1157 {0, 1, 1, 2, 2, 3, 3, 4, 4, 1, 1, 5, 5, 6, 6, 7,
1158 7, 8, 8, 9, 9, 2, 2, 10, 10, 1, 1, 11, 11, 12, 12, 3,
1159 3, 13, 13, 0, 14, 14, 16, 15, 16, 15, 4, 4, 17, 1, 17, 1,
1160 5, 5, 18, 18, 2, 2, 6, 6, 8, 19, 7, 8, 7, 19, 20, 20,
1161 21, 21, 22, 24, 22, 24, 23, 23, 1, 1, 25, 25, 3, 3, 26, 26,
1162 9, 9, 27, 27, 28, 28, 33, 29, 4, 33, 29, 1, 4, 1, 32, 32,
1163 2, 2, 31, 10, 30, 10, 30, 31, 34, 34, 5, 5, 36, 36, 35, 41,
1164 35, 11, 41, 11, 37, 1, 8, 8, 37, 6, 1, 6, 40, 7, 7, 40,
1165 12, 38, 12, 39, 39, 38, 49, 13, 49, 13, 3, 42, 3, 42, 16, 16,
1166 43, 43, 14, 14, 1, 1, 44, 15, 44, 15, 2, 2, 57, 48, 50, 48,
1167 57, 50, 4, 45, 45, 4, 46, 47, 47, 46, 1, 51, 1, 17, 17, 51,
1168 8, 9, 9, 5, 58, 8, 58, 5, 52, 52, 55, 56, 53, 56, 55, 59,
1169 59, 53, 54, 1, 6, 54, 7, 7, 6, 1, 2, 3, 2, 3, 64, 60,
1170 60, 10, 10, 64, 61, 62, 61, 63, 1, 63, 62, 1, 18, 24, 18, 4,
1171 25, 4, 8, 21, 21, 1, 24, 22, 25, 22, 8, 11, 19, 11, 23, 1,
1172 20, 23, 19, 20, 5, 12, 5, 1, 16, 2, 12, 13, 2, 13, 1, 16},
1175 { 0, 1, -1, 1, -1, 1, -1, 1, -1, 2, -2, 1, -1, 1, -1, 1,
1176 -1, 1, -1, 1, -1, 2, -2, 1, -1, 3, -3, 1, -1, 1, -1, 2,
1177 -2, 1, -1, 0, 1, -1, 1, 1, -1, -1, 2, -2, 1, 4, -1, -4,
1178 2, -2, 1, -1, -3, 3, 2, -2, 2, 1, 2, -2, -2, -1, 1, -1,
1179 1, -1, 1, 1, -1, -1, 1, -1, 5, -5, 1, -1, 3, -3, 1, -1,
1180 2, -2, 1, -1, 1, -1, 1, 1, 3, -1, -1, 6, -3, -6, -1, 1,
1181 4, -4, 1, 2, 1, -2, -1, -1, 1, -1, 3, -3, 1, -1, 1, 1,
1182 -1, 2, -1, -2, 1, 7, -3, 3, -1, 3, -7, -3, 1, -3, 3, -1,
1183 2, 1, -2, 1, -1, -1, 1, 2, -1, -2, -4, -1, 4, 1, 2, -2,
1184 1, -1, -2, 2, 8, -8, -1, 2, 1, -2, -5, 5, 1, -1, -1, 1,
1185 -1, 1, 4, -1, 1, -4, -1, -1, 1, 1, 9, 1, -9, 2, -2, -1,
1186 -4, 3, -3, -4, -1, 4, 1, 4, 1, -1, 1, -1, 1, 1, -1, 1,
1187 -1, -1, -1, 10, 4, 1, 4, -4, -4, -10, 6, 5, -6, -5, 1, -1,
1188 1, 3, -3, -1, 1, -1, -1, -1, 11, 1, 1, -11, -2, -2, 2, 5,
1189 -2, -5, -5, 2, -2, 12, 2, -2, 2, 2, 5, -3, -2, 3, -2, -12,
1190 -2, 2, 2, 2, -5, 3, 5, 13, -3, 7, -3, -3, -7, 3, -13, 3}
1196 {0, 1, 1, 1, 2, 2, 1, 3, 3, 1, 1, 1, 4, 4, 1, 5,
1197 2, 1, 5, 2, 1, 1, 6, 6, 1, 1, 1, 1, 1, 7, 3, 1,
1198 2, 3, 0, 1, 2, 7, 1, 1, 1, 8, 1, 1, 8, 1, 1, 1,
1199 9, 1, 9, 1, 2, 1, 1, 2, 1, 1, 10, 4, 1, 10, 1, 4,
1200 1, 1, 1, 1, 1, 3, 1, 1, 1, 3, 2, 1, 5, 1, 1, 1,
1201 2, 5, 1, 11, 1, 11, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1202 2, 1, 6, 1, 6, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 12,
1203 3, 1, 12, 1, 1, 1, 2, 1, 1, 3, 1, 1, 1, 1, 1, 1,
1204 4, 1, 1, 1, 2, 1, 1, 4, 1, 1, 1, 1, 1, 1, 2, 1,
1205 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 2, 1, 1, 5,
1206 1, 1, 1, 1, 1, 7, 1, 7, 1, 1, 2, 3, 1, 1, 1, 1,
1207 5, 1, 1, 1, 1, 1, 1, 2, 13, 1, 1, 1, 1, 1, 1, 1,
1208 1, 1, 1, 1, 1, 1, 1, 1, 13, 2, 1, 1, 4, 1, 1, 1,
1209 3, 1, 6, 1, 1, 1, 14, 1, 1, 1, 1, 1, 14, 6, 1, 1,
1210 1, 1, 15, 2, 4, 1, 2, 3, 15, 1, 1, 1, 8, 1, 1, 8,
1211 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1},
1214 { 0, 1, -1, 2, 1, -1, -2, 1, -1, 3, -3, 4, 1, -1, -4, 1,
1215 2, 5, -1, -2, -5, 6, 1, -1, -6, 7, -7, 8, -8, 1, 2, 9,
1216 3, -2, 0, -9, -3, -1, 10, -10, 11, 1, -11, 12, -1, -12, 13, -13,
1217 1, 14, -1, -14, 4, 15, -15, -4, 16, -16, 1, 2, 17, -1, -17, -2,
1218 18, -18, 19, -19, 20, 3, -20, 21, -21, -3, 5, 22, 2, -22, -23, 23,
1219 -5, -2, 24, 1, -24, -1, 25, -25, 26, -26, -27, 27, 28, 29, -28, -29,
1220 6, 30, 2, -31, -2, -30, 31, -6, -32, 32, 33, -33, 34, -35, -34, 1,
1221 4, -36, -1, 35, 37, 36, 7, -37, 38, -4, -38, 39, 41, 40, -40, -39,
1222 3, 42, -43, -41, -7, -42, 43, -3, 44, -44, 45, -45, 46, 47, 8, -47,
1223 -48, -46, 50, -50, 48, 49, 51, -49, 52, -52, 5, -51, -8, -53, 53, 3,
1224 -56, 56, 55, 54, -54, 2, 60, -2, -55, 58, 9, -5, 59, 57, -57, -63,
1225 -3, -58, -60, -61, 61, -59, -62, -9, 1, 64, 62, 69, -64, 63, 65, -67,
1226 -68, 66, -65, 68, -66, -69, 67, -70, -1, 10, 71, -71, 4, 73, 72, 70,
1227 6, -76, -3, 74, -78, -74, 1, 78, 80, -72, -75, 76, -1, 3, -73, 79,
1228 75, 77, 1, 11, -4, -79, -10, -6, -1, -77, -83, -80, 2, 81, -84, -2,
1229 83, -81, 82, -82, 84, -87, -86, 85, -11, -85, 86, -89, 87, -88, 88, 89}
1235 {1, 1, 0, 2, 1, 2, 1, 3, 3, 1, 1, 4, 4, 2, 2, 1,
1236 1, 5, 5, 6, 1, 6, 1, 7, 7, 3, 3, 2, 8, 2, 8, 1,
1237 1, 0, 9, 9, 1, 1, 10, 4, 10, 4, 11, 11, 2, 1, 2, 1,
1238 12, 12, 3, 3, 1, 1, 13, 5, 5, 13, 14, 1, 1, 14, 2, 2,
1239 6, 6, 15, 1, 1, 15, 16, 4, 7, 16, 4, 7, 1, 1, 3, 3,
1240 8, 8, 2, 2, 1, 1, 17, 17, 1, 1, 18, 18, 5, 5, 2, 2,
1241 1, 1, 9, 19, 9, 19, 20, 3, 3, 20, 1, 10, 21, 1, 10, 4,
1242 4, 21, 22, 6, 6, 22, 1, 1, 23, 24, 2, 2, 23, 24, 11, 1,
1243 1, 11, 7, 25, 7, 1, 1, 25, 8, 8, 3, 26, 3, 1, 12, 2,
1244 2, 26, 1, 12, 5, 5, 27, 4, 1, 4, 1, 27, 28, 1, 28, 13,
1245 1, 13, 2, 29, 2, 1, 32, 6, 1, 30, 14, 29, 14, 6, 3, 31,
1246 3, 1, 30, 1, 32, 31, 33, 9, 33, 1, 1, 7, 9, 7, 2, 2,
1247 1, 1, 4, 36, 34, 4, 5, 10, 10, 5, 34, 1, 1, 35, 8, 8,
1248 36, 3, 35, 1, 15, 3, 2, 1, 16, 15, 16, 2, 37, 1, 37, 1,
1249 1, 1, 6, 6, 38, 1, 38, 11, 1, 39, 39, 40, 11, 2, 41, 4,
1250 40, 1, 2, 4, 1, 1, 1, 41, 3, 1, 3, 1, 5, 7, 5, 7},
1253 { 1, -1, 0, 1, 2, -1, -2, 1, -1, 3, -3, 1, -1, 2, -2, 4,
1254 -4, 1, -1, 1, 5, -1, -5, 1, -1, 2, -2, 3, 1, -3, -1, 6,
1255 -6, 0, 1, -1, 7, -7, 1, 2, -1, -2, 1, -1, 4, 8, -4, -8,
1256 1, -1, 3, -3, 9, -9, 1, 2, -2, -1, 1, 10, -10, -1, 5, -5,
1257 2, -2, 1, 11, -11, -1, 1, 3, 2, -1, -3, -2, 12, -12, 4, -4,
1258 2, -2, -6, 6, 13, -13, 1, -1, 14, -14, 1, -1, 3, -3, 7, -7,
1259 15, -15, 2, 1, -2, -1, 1, 5, -5, -1, -16, 2, 1, 16, -2, 4,
1260 -4, -1, 1, 3, -3, -1, 17, -17, 1, 1, -8, 8, -1, -1, 2, 18,
1261 -18, -2, 3, 1, -3, 19, -19, -1, 3, -3, 6, 1, -6, 20, 2, 9,
1262 -9, -1, -20, -2, 4, -4, 1, -5, 21, 5, -21, -1, 1, -22, -1, 2,
1263 22, -2, 10, 1, -10, 23, 1, 4, -23, 1, 2, -1, -2, -4, -7, 1,
1264 7, -24, -1, 24, -1, -1, 1, 3, -1, -25, 25, 4, -3, -4, 11, -11,
1265 26, -26, 6, 1, 1, -6, -5, -3, 3, 5, -1, -27, 27, 1, 4, -4,
1266 -1, -8, -1, 28, 2, 8, -12, -28, -2, -2, 2, 12, -1, 29, 1, -29,
1267 30, -30, 5, -5, 1, -31, -1, 3, 31, -1, 1, 1, -3, -13, 1, -7,
1268 -1, -32, 13, 7, 32, 33, -33, -1, -9, -34, 9, 34, -6, 5, 6, -5}
1274 {1, 1, 0, 1, 1, 2, 2, 1, 1, 3, 3, 1, 1, 0, 2, 2,
1275 4, 1, 4, 1, 1, 1, 5, 5, 1, 1, 6, 6, 2, 2, 1, 1,
1276 3, 3, 7, 7, 1, 1, 8, 8, 1, 1, 2, 2, 1, 9, 1, 9,
1277 4, 4, 10, 1, 1, 10, 1, 1, 11, 11, 3, 3, 1, 2, 1, 2,
1278 1, 1, 12, 12, 5, 5, 1, 1, 13, 1, 1, 13, 2, 2, 1, 1,
1279 6, 6, 1, 1, 4, 14, 4, 14, 3, 1, 3, 1, 1, 1, 15, 7,
1280 15, 2, 2, 7, 1, 1, 1, 8, 1, 8, 16, 16, 1, 1, 1, 1,
1281 2, 1, 1, 2, 1, 1, 3, 5, 5, 3, 4, 1, 1, 4, 1, 1,
1282 17, 17, 9, 1, 1, 9, 2, 2, 1, 1, 10, 10, 1, 6, 1, 1,
1283 6, 18, 1, 1, 18, 1, 1, 1, 2, 2, 3, 1, 3, 1, 1, 1,
1284 4, 1, 19, 1, 19, 7, 1, 1, 20, 1, 4, 20, 1, 7, 11, 2,
1285 1, 11, 21, 2, 8, 5, 1, 8, 1, 5, 21, 1, 1, 1, 22, 1,
1286 1, 22, 1, 1, 3, 3, 1, 23, 2, 12, 24, 1, 1, 2, 1, 1,
1287 12, 23, 1, 1, 24, 1, 1, 1, 4, 1, 1, 1, 2, 1, 6, 6,
1288 4, 2, 1, 1, 1, 1, 1, 1, 1, 14, 13, 3, 1, 25, 9, 25,
1289 14, 1, 9, 3, 13, 1, 1, 1, 1, 1, 10, 1, 1, 2, 10, 2},
1292 {-20, -1, 0, 2, -2, 1, -1, 3, -3, 1, -1, 4, -4, 0, 2, -2,
1293 1, 5, -1, -5, 6, -6, 1, -1, 7, -7, 1, -1, 3, -3, 8, -8,
1294 2, -2, 1, -1, 9, -9, 1, -1, 10, -10, 4, -4, 11, 1, -11, -1,
1295 2, -2, 1, 12, -12, -1, 13, -13, 1, -1, 3, -3, 14, 5, -14, -5,
1296 -15, 15, -1, 1, 2, -2, 16, -16, 1, 17, -17, -1, 6, -6, 18, -18,
1297 2, -2, -19, 19, -3, 1, 3, -1, 4, 20, -4, 1, -21, 21, 1, 2,
1298 -1, -7, 7, -2, 22, -22, 23, 2, -23, -2, 1, -1, -24, 24, -25, 25,
1299 -8, -26, 26, 8, -27, 27, 5, 3, -3, -5, -4, 28, -28, 4, 29, -29,
1300 1, -1, -2, -30, 30, 2, 9, -9, -31, 31, 2, -2, -32, 3, 32, -33,
1301 -3, 1, 33, -34, -1, 34, -35, 35, -10, 10, -6, 36, 6, -36, 37, -37,
1302 -5, 38, 1, -38, -1, 3, 39, -39, -1, 40, 5, 1, -40, -3, 2, -11,
1303 -41, -2, 1, 11, -3, -4, 41, 3, 42, 4, -1, -43, -42, 43, 1, -44,
1304 45, -1, 44, -45, -7, 7, -46, 1, -12, 2, 1, -47, 46, 12, 47, 48,
1305 -2, -1, -48, 49, -1, -50, -49, 50, -6, -51, 51, 52, -13, 53, -4, 4,
1306 6, 13, -53, -52, -54, 55, 54, -55, -56, -2, 2, -8, 56, 1, -3, -1,
1307 2, 58, 3, 8, -2, 57, -58, -60, -59, -57, -3, 60, 59, -14, 3, 14}
1313 {1, 1, 0, 2, 2, 1, 1, 3, 3, 4, 4, 5, 5, 1, 1, 6,
1314 6, 2, 2, 7, 7, 8, 8, 1, 1, 3, 3, 9, 9, 10, 10, 1,
1315 1, 2, 2, 4, 4, 11, 0, 11, 12, 12, 13, 13, 1, 1, 5, 5,
1316 14, 14, 15, 16, 15, 16, 3, 3, 1, 6, 1, 6, 2, 2, 7, 7,
1317 8, 8, 17, 17, 1, 1, 4, 4, 18, 18, 2, 2, 1, 19, 1, 20,
1318 19, 20, 21, 21, 3, 3, 22, 22, 5, 5, 24, 1, 1, 23, 9, 23,
1319 24, 9, 2, 2, 10, 1, 1, 10, 6, 6, 25, 4, 4, 25, 7, 7,
1320 26, 8, 1, 8, 3, 1, 26, 3, 11, 11, 27, 27, 2, 28, 1, 2,
1321 28, 1, 12, 12, 5, 5, 29, 13, 13, 29, 32, 1, 1, 33, 31, 30,
1322 32, 4, 30, 33, 4, 31, 3, 14, 1, 1, 3, 34, 34, 2, 2, 14,
1323 6, 6, 35, 36, 35, 36, 1, 15, 1, 16, 16, 15, 7, 9, 7, 9,
1324 37, 8, 8, 37, 1, 1, 39, 2, 38, 39, 2, 40, 5, 38, 40, 5,
1325 3, 3, 4, 4, 10, 10, 1, 1, 1, 1, 41, 2, 41, 2, 6, 6,
1326 1, 1, 11, 42, 11, 43, 3, 42, 3, 17, 4, 43, 1, 17, 7, 1,
1327 8, 44, 4, 7, 44, 5, 8, 2, 5, 1, 2, 48, 45, 1, 12, 45,
1328 12, 48, 13, 13, 1, 9, 9, 46, 1, 46, 47, 47, 49, 18, 18, 49},
1331 { 1, -1, 0, 1, -1, 2, -2, 1, -1, 1, -1, 1, -1, 3, -3, 1,
1332 -1, -2, 2, 1, -1, 1, -1, 4, -4, -2, 2, 1, -1, 1, -1, 5,
1333 -5, -3, 3, 2, -2, 1, 0, -1, 1, -1, 1, -1, 6, -6, 2, -2,
1334 1, -1, 1, 1, -1, -1, -3, 3, 7, 2, -7, -2, -4, 4, 2, -2,
1335 2, -2, 1, -1, 8, -8, 3, -3, 1, -1, -5, 5, 9, 1, -9, 1,
1336 -1, -1, 1, -1, -4, 4, 1, -1, 3, -3, 1, -10, 10, 1, 2, -1,
1337 -1, -2, 6, -6, 2, 11, -11, -2, 3, -3, 1, -4, 4, -1, 3, -3,
1338 1, 3, 12, -3, -5, -12, -1, 5, 2, -2, 1, -1, -7, 1, 13, 7,
1339 -1, -13, 2, -2, 4, -4, 1, 2, -2, -1, 1, 14, -14, 1, 1, 1,
1340 -1, -5, -1, -1, 5, -1, -6, 2, -15, 15, 6, 1, -1, -8, 8, -2,
1341 -4, 4, 1, 1, -1, -1, 16, 2, -16, -2, 2, -2, 4, 3, -4, -3,
1342 -1, -4, 4, 1, -17, 17, -1, -9, 1, 1, 9, 1, -5, -1, -1, 5,
1343 -7, 7, 6, -6, 3, -3, 18, -18, 19, -19, 1, -10, -1, 10, -5, 5,
1344 20, -20, -3, 1, 3, 1, 8, -1, -8, 2, 7, -1, -21, -2, 5, 21,
1345 5, -1, -7, -5, 1, -6, -5, -11, 6, 22, 11, 1, 1, -22, -3, -1,
1346 3, -1, 3, -3, -23, 4, -4, 1, 23, -1, 1, -1, 1, -2, 2, -1}
1352 {1, 1, 1, 1, 0, 2, 2, 1, 1, 3, 3, 0, 1, 1, 2, 2,
1353 4, 4, 1, 1, 5, 5, 1, 1, 2, 2, 3, 3, 6, 6, 1, 1,
1354 7, 7, 8, 1, 8, 2, 2, 1, 4, 4, 1, 3, 1, 3, 9, 9,
1355 2, 2, 1, 5, 1, 5, 10, 10, 1, 1, 11, 11, 3, 6, 3, 4,
1356 4, 6, 2, 2, 1, 12, 1, 12, 7, 13, 7, 13, 1, 1, 8, 8,
1357 2, 2, 14, 14, 16, 15, 16, 5, 5, 1, 3, 15, 1, 3, 4, 4,
1358 1, 1, 17, 17, 2, 2, 6, 6, 1, 18, 1, 18, 22, 21, 22, 21,
1359 25, 24, 25, 19, 9, 20, 9, 23, 19, 24, 20, 3, 23, 7, 3, 1,
1360 1, 7, 28, 26, 29, 5, 28, 26, 5, 8, 29, 4, 8, 27, 2, 2,
1361 4, 27, 1, 1, 10, 36, 10, 33, 33, 36, 30, 1, 32, 32, 1, 30,
1362 6, 31, 31, 35, 3, 6, 11, 11, 3, 2, 35, 2, 34, 1, 34, 1,
1363 37, 37, 12, 7, 12, 5, 41, 5, 4, 7, 1, 8, 13, 4, 1, 41,
1364 13, 38, 8, 38, 9, 1, 40, 40, 9, 1, 39, 2, 2, 49, 39, 42,
1365 3, 3, 14, 16, 49, 14, 16, 42, 43, 43, 6, 6, 15, 1, 1, 15,
1366 44, 44, 1, 1, 50, 48, 4, 5, 4, 7, 5, 2, 10, 10, 48, 7,
1367 50, 45, 2, 1, 45, 8, 8, 1, 46, 46, 3, 47, 47, 3, 1, 1},
1370 { 1, -1, 2, -2, 0, 1, -1, 3, -3, 1, -1, 0, 4, -4, 2, -2,
1371 1, -1, 5, -5, 1, -1, 6, -6, 3, -3, 2, -2, 1, -1, 7, -7,
1372 1, -1, 1, 8, -1, 4, -4, -8, 2, -2, 9, 3, -9, -3, 1, -1,
1373 5, -5, 10, 2, -10, -2, 1, -1, 11, -11, 1, -1, -4, 2, 4, 3,
1374 -3, -2, 6, -6, 12, 1, -12, -1, 2, 1, -2, -1, 13, -13, 2, -2,
1375 7, -7, 1, -1, 1, 1, -1, 3, -3, 14, 5, -1, -14, -5, 4, -4,
1376 15, -15, 1, -1, 8, -8, -3, 3, 16, 1, -16, -1, 1, 1, -1, -1,
1377 1, 1, -1, 1, 2, 1, -2, 1, -1, -1, -1, 6, -1, 3, -6, 17,
1378 -17, -3, 1, 1, 1, 4, -1, -1, -4, 3, -1, 5, -3, -1, -9, 9,
1379 -5, 1, 18, -18, 2, 1, -2, 1, -1, -1, 1, 19, -1, 1, -19, -1,
1380 4, 1, -1, 1, 7, -4, -2, 2, -7, 10, -1, -10, 1, 20, -1, -20,
1381 1, -1, 2, 4, -2, 5, 1, -5, 6, -4, 21, 4, 2, -6, -21, -1,
1382 -2, 1, -4, -1, -3, 22, -1, 1, 3, -22, -1, 11, -11, 1, 1, 1,
1383 8, -8, 2, 2, -1, -2, -2, -1, 1, -1, -5, 5, 2, 23, -23, -2,
1384 1, -1, 24, -24, -1, -1, 7, 6, -7, 5, -6, 12, -3, 3, 1, -5,
1385 1, 1, -12, 25, -1, -5, 5, -25, -1, 1, 9, 1, -1, -9, 26, -26}