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"
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 Libav 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 -1; /* 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 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)) {
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++) {
206 for (b = 0; b < planes[p].num_bands; b++) {
207 av_freep(&planes[p].bands[b].bufs[0]);
208 av_freep(&planes[p].bands[b].bufs[1]);
209 av_freep(&planes[p].bands[b].bufs[2]);
211 if (planes[p].bands[b].blk_vlc.cust_tab.table)
212 ff_free_vlc(&planes[p].bands[b].blk_vlc.cust_tab);
213 for (t = 0; t < planes[p].bands[b].num_tiles; t++)
214 av_freep(&planes[p].bands[b].tiles[t].mbs);
215 av_freep(&planes[p].bands[b].tiles);
217 av_freep(&planes[p].bands);
221 av_cold int ff_ivi_init_planes(IVIPlaneDesc *planes, const IVIPicConfig *cfg)
224 uint32_t b_width, b_height, align_fac, width_aligned, height_aligned, buf_size;
227 ivi_free_buffers(planes);
229 /* fill in the descriptor of the luminance plane */
230 planes[0].width = cfg->pic_width;
231 planes[0].height = cfg->pic_height;
232 planes[0].num_bands = cfg->luma_bands;
234 /* fill in the descriptors of the chrominance planes */
235 planes[1].width = planes[2].width = (cfg->pic_width + 3) >> 2;
236 planes[1].height = planes[2].height = (cfg->pic_height + 3) >> 2;
237 planes[1].num_bands = planes[2].num_bands = cfg->chroma_bands;
239 for (p = 0; p < 3; p++) {
240 planes[p].bands = av_mallocz(planes[p].num_bands * sizeof(IVIBandDesc));
241 if (!planes[p].bands)
242 return AVERROR(ENOMEM);
244 /* select band dimensions: if there is only one band then it
245 * has the full size, if there are several bands each of them
246 * has only half size */
247 b_width = planes[p].num_bands == 1 ? planes[p].width : (planes[p].width + 1) >> 1;
248 b_height = planes[p].num_bands == 1 ? planes[p].height : (planes[p].height + 1) >> 1;
250 /* luma band buffers will be aligned on 16x16 (max macroblock size) */
251 /* chroma band buffers will be aligned on 8x8 (max macroblock size) */
252 align_fac = p ? 8 : 16;
253 width_aligned = FFALIGN(b_width , align_fac);
254 height_aligned = FFALIGN(b_height, align_fac);
255 buf_size = width_aligned * height_aligned * sizeof(int16_t);
257 for (b = 0; b < planes[p].num_bands; b++) {
258 band = &planes[p].bands[b]; /* select appropriate plane/band */
261 band->width = b_width;
262 band->height = b_height;
263 band->pitch = width_aligned;
264 band->aheight = height_aligned;
265 band->bufs[0] = av_mallocz(buf_size);
266 band->bufs[1] = av_mallocz(buf_size);
267 if (!band->bufs[0] || !band->bufs[1])
268 return AVERROR(ENOMEM);
270 /* allocate the 3rd band buffer for scalability mode */
271 if (cfg->luma_bands > 1) {
272 band->bufs[2] = av_mallocz(buf_size);
274 return AVERROR(ENOMEM);
277 planes[p].bands[0].blk_vlc.cust_desc.num_rows = 0; /* reset custom vlc */
284 av_cold int ff_ivi_init_tiles(IVIPlaneDesc *planes, int tile_width, int tile_height)
286 int p, b, x, y, x_tiles, y_tiles, t_width, t_height;
288 IVITile *tile, *ref_tile;
290 for (p = 0; p < 3; p++) {
291 t_width = !p ? tile_width : (tile_width + 3) >> 2;
292 t_height = !p ? tile_height : (tile_height + 3) >> 2;
294 if (!p && planes[0].num_bands == 4) {
299 for (b = 0; b < planes[p].num_bands; b++) {
300 band = &planes[p].bands[b];
301 x_tiles = IVI_NUM_TILES(band->width, t_width);
302 y_tiles = IVI_NUM_TILES(band->height, t_height);
303 band->num_tiles = x_tiles * y_tiles;
305 av_freep(&band->tiles);
306 band->tiles = av_mallocz(band->num_tiles * sizeof(IVITile));
308 return AVERROR(ENOMEM);
312 /* use the first luma band as reference for motion vectors
314 ref_tile = planes[0].bands[0].tiles;
316 for (y = 0; y < band->height; y += t_height) {
317 for (x = 0; x < band->width; x += t_width) {
320 tile->mb_size = band->mb_size;
321 tile->width = FFMIN(band->width - x, t_width);
322 tile->height = FFMIN(band->height - y, t_height);
323 tile->is_empty = tile->data_size = 0;
324 /* calculate number of macroblocks */
325 tile->num_MBs = IVI_MBs_PER_TILE(tile->width, tile->height,
328 av_freep(&tile->mbs);
329 tile->mbs = av_malloc(tile->num_MBs * sizeof(IVIMbInfo));
331 return AVERROR(ENOMEM);
335 tile->ref_mbs = ref_tile->mbs;
350 * Decode size of the tile data.
351 * The size is stored as a variable-length field having the following format:
352 * if (tile_data_size < 255) than this field is only one byte long
353 * if (tile_data_size >= 255) than this field four is byte long: 0xFF X1 X2 X3
354 * where X1-X3 is size of the tile data
356 * @param[in,out] gb the GetBit context
357 * @return size of the tile data in bytes
359 static int ivi_dec_tile_data_size(GetBitContext *gb)
365 len = get_bits(gb, 8);
367 len = get_bits_long(gb, 24);
370 /* align the bitstream reader on the byte boundary */
378 * extract huffman-coded transform coefficients from the bitstream,
379 * dequantize them, apply inverse transform and motion compensation
380 * in order to reconstruct the picture.
382 * @param[in,out] gb the GetBit context
383 * @param[in] band pointer to the band descriptor
384 * @param[in] tile pointer to the tile descriptor
385 * @return result code: 0 - OK, -1 = error (corrupted blocks data)
387 static int ivi_decode_blocks(GetBitContext *gb, IVIBandDesc *band, IVITile *tile,
388 AVCodecContext *avctx)
390 int mbn, blk, num_blocks, num_coeffs, blk_size, scan_pos, run, val,
391 pos, is_intra, mc_type = 0, mv_x, mv_y, col_mask;
392 uint8_t col_flags[8];
393 int32_t prev_dc, trvec[64];
394 uint32_t cbp, sym, lo, hi, quant, buf_offs, q;
396 RVMapDesc *rvmap = band->rv_map;
397 void (*mc_with_delta_func)(int16_t *buf, const int16_t *ref_buf, uint32_t pitch, int mc_type);
398 void (*mc_no_delta_func) (int16_t *buf, const int16_t *ref_buf, uint32_t pitch, int mc_type);
399 const uint16_t *base_tab;
400 const uint8_t *scale_tab;
402 prev_dc = 0; /* init intra prediction for the DC coefficient */
404 blk_size = band->blk_size;
405 col_mask = blk_size - 1; /* column mask for tracking non-zero coeffs */
406 num_blocks = (band->mb_size != blk_size) ? 4 : 1; /* number of blocks per mb */
407 num_coeffs = blk_size * blk_size;
409 mc_with_delta_func = ff_ivi_mc_8x8_delta;
410 mc_no_delta_func = ff_ivi_mc_8x8_no_delta;
412 mc_with_delta_func = ff_ivi_mc_4x4_delta;
413 mc_no_delta_func = ff_ivi_mc_4x4_no_delta;
416 for (mbn = 0, mb = tile->mbs; mbn < tile->num_MBs; mb++, mbn++) {
417 is_intra = !mb->type;
419 buf_offs = mb->buf_offs;
421 quant = av_clip(band->glob_quant + mb->q_delta, 0, 23);
423 base_tab = is_intra ? band->intra_base : band->inter_base;
424 scale_tab = is_intra ? band->intra_scale : band->inter_scale;
426 quant = scale_tab[quant];
431 if (band->is_halfpel) {
432 mc_type = ((mv_y & 1) << 1) | (mv_x & 1);
434 mv_y >>= 1; /* convert halfpel vectors into fullpel ones */
437 int dmv_x, dmv_y, cx, cy;
439 dmv_x = mb->mv_x >> band->is_halfpel;
440 dmv_y = mb->mv_y >> band->is_halfpel;
441 cx = mb->mv_x & band->is_halfpel;
442 cy = mb->mv_y & band->is_halfpel;
444 if ( mb->xpos + dmv_x < 0
445 || mb->xpos + dmv_x + band->mb_size + cx > band->pitch
446 || mb->ypos + dmv_y < 0
447 || mb->ypos + dmv_y + band->mb_size + cy > band->aheight) {
448 return AVERROR_INVALIDDATA;
453 for (blk = 0; blk < num_blocks; blk++) {
454 /* adjust block position in the buffer according to its number */
456 buf_offs += blk_size;
457 } else if (blk == 2) {
458 buf_offs -= blk_size;
459 buf_offs += blk_size * band->pitch;
462 if (cbp & 1) { /* block coded ? */
464 av_log(avctx, AV_LOG_ERROR, "Scan pattern is not set.\n");
465 return AVERROR_INVALIDDATA;
469 memset(trvec, 0, num_coeffs*sizeof(trvec[0])); /* zero transform vector */
470 memset(col_flags, 0, sizeof(col_flags)); /* zero column flags */
472 while (scan_pos <= num_coeffs) {
473 sym = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
474 if (sym == rvmap->eob_sym)
475 break; /* End of block */
477 if (sym == rvmap->esc_sym) { /* Escape - run/val explicitly coded using 3 vlc codes */
478 run = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1) + 1;
479 lo = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
480 hi = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
481 val = IVI_TOSIGNED((hi << 6) | lo); /* merge them and convert into signed val */
484 av_log(avctx, AV_LOG_ERROR, "Invalid sym encountered: %d.\n", sym);
487 run = rvmap->runtab[sym];
488 val = rvmap->valtab[sym];
491 /* de-zigzag and dequantize */
493 if (scan_pos >= num_coeffs)
495 pos = band->scan[scan_pos];
498 av_dlog(avctx, "Val = 0 encountered!\n");
500 q = (base_tab[pos] * quant) >> 9;
502 val = val * q + FFSIGN(val) * (((q ^ 1) - 1) >> 1);
504 col_flags[pos & col_mask] |= !!val; /* track columns containing non-zero coeffs */
507 if (scan_pos >= num_coeffs && sym != rvmap->eob_sym)
508 return -1; /* corrupt block data */
510 /* undoing DC coeff prediction for intra-blocks */
511 if (is_intra && band->is_2d_trans) {
514 col_flags[0] |= !!prev_dc;
517 /* apply inverse transform */
518 band->inv_transform(trvec, band->buf + buf_offs,
519 band->pitch, col_flags);
521 /* apply motion compensation */
523 mc_with_delta_func(band->buf + buf_offs,
524 band->ref_buf + buf_offs + mv_y * band->pitch + mv_x,
525 band->pitch, mc_type);
527 /* block not coded */
528 /* for intra blocks apply the dc slant transform */
529 /* for inter - perform the motion compensation without delta */
531 if (band->dc_transform)
532 band->dc_transform(&prev_dc, band->buf + buf_offs,
533 band->pitch, blk_size);
535 mc_no_delta_func(band->buf + buf_offs,
536 band->ref_buf + buf_offs + mv_y * band->pitch + mv_x,
537 band->pitch, mc_type);
550 * Handle empty tiles by performing data copying and motion
551 * compensation respectively.
553 * @param[in] avctx ptr to the AVCodecContext
554 * @param[in] band pointer to the band descriptor
555 * @param[in] tile pointer to the tile descriptor
556 * @param[in] mv_scale scaling factor for motion vectors
558 static int ivi_process_empty_tile(AVCodecContext *avctx, IVIBandDesc *band,
559 IVITile *tile, int32_t mv_scale)
561 int x, y, need_mc, mbn, blk, num_blocks, mv_x, mv_y, mc_type;
562 int offs, mb_offset, row_offset;
563 IVIMbInfo *mb, *ref_mb;
566 void (*mc_no_delta_func)(int16_t *buf, const int16_t *ref_buf, uint32_t pitch,
569 if (tile->num_MBs != IVI_MBs_PER_TILE(tile->width, tile->height, band->mb_size)) {
570 av_log(avctx, AV_LOG_ERROR, "Allocated tile size %d mismatches "
571 "parameters %d in ivi_process_empty_tile()\n",
572 tile->num_MBs, IVI_MBs_PER_TILE(tile->width, tile->height, band->mb_size));
573 return AVERROR_INVALIDDATA;
576 offs = tile->ypos * band->pitch + tile->xpos;
578 ref_mb = tile->ref_mbs;
579 row_offset = band->mb_size * band->pitch;
580 need_mc = 0; /* reset the mc tracking flag */
582 for (y = tile->ypos; y < (tile->ypos + tile->height); y += band->mb_size) {
585 for (x = tile->xpos; x < (tile->xpos + tile->width); x += band->mb_size) {
588 mb->buf_offs = mb_offset;
590 mb->type = 1; /* set the macroblocks type = INTER */
591 mb->cbp = 0; /* all blocks are empty */
593 if (!band->qdelta_present && !band->plane && !band->band_num) {
594 mb->q_delta = band->glob_quant;
599 if (band->inherit_qdelta && ref_mb)
600 mb->q_delta = ref_mb->q_delta;
602 if (band->inherit_mv) {
603 /* motion vector inheritance */
605 mb->mv_x = ivi_scale_mv(ref_mb->mv_x, mv_scale);
606 mb->mv_y = ivi_scale_mv(ref_mb->mv_y, mv_scale);
608 mb->mv_x = ref_mb->mv_x;
609 mb->mv_y = ref_mb->mv_y;
611 need_mc |= mb->mv_x || mb->mv_y; /* tracking non-zero motion vectors */
617 mb_offset += band->mb_size;
622 if (band->inherit_mv && need_mc) { /* apply motion compensation if there is at least one non-zero motion vector */
623 num_blocks = (band->mb_size != band->blk_size) ? 4 : 1; /* number of blocks per mb */
624 mc_no_delta_func = (band->blk_size == 8) ? ff_ivi_mc_8x8_no_delta
625 : ff_ivi_mc_4x4_no_delta;
627 for (mbn = 0, mb = tile->mbs; mbn < tile->num_MBs; mb++, mbn++) {
630 if (!band->is_halfpel) {
631 mc_type = 0; /* we have only fullpel vectors */
633 mc_type = ((mv_y & 1) << 1) | (mv_x & 1);
635 mv_y >>= 1; /* convert halfpel vectors into fullpel ones */
638 for (blk = 0; blk < num_blocks; blk++) {
639 /* adjust block position in the buffer according with its number */
640 offs = mb->buf_offs + band->blk_size * ((blk & 1) + !!(blk & 2) * band->pitch);
641 mc_no_delta_func(band->buf + offs,
642 band->ref_buf + offs + mv_y * band->pitch + mv_x,
643 band->pitch, mc_type);
647 /* copy data from the reference tile into the current one */
648 src = band->ref_buf + tile->ypos * band->pitch + tile->xpos;
649 dst = band->buf + tile->ypos * band->pitch + tile->xpos;
650 for (y = 0; y < tile->height; y++) {
651 memcpy(dst, src, tile->width*sizeof(band->buf[0]));
662 static uint16_t ivi_calc_band_checksum(IVIBandDesc *band)
665 int16_t *src, checksum;
670 for (y = 0; y < band->height; src += band->pitch, y++)
671 for (x = 0; x < band->width; x++)
679 * Convert and output the current plane.
680 * This conversion is done by adding back the bias value of 128
681 * (subtracted in the encoder) and clipping the result.
683 * @param[in] plane pointer to the descriptor of the plane being processed
684 * @param[out] dst pointer to the buffer receiving converted pixels
685 * @param[in] dst_pitch pitch for moving to the next y line
687 static void ivi_output_plane(IVIPlaneDesc *plane, uint8_t *dst, int dst_pitch)
690 const int16_t *src = plane->bands[0].buf;
691 uint32_t pitch = plane->bands[0].pitch;
696 for (y = 0; y < plane->height; y++) {
697 for (x = 0; x < plane->width; x++)
698 dst[x] = av_clip_uint8(src[x] + 128);
705 * Decode an Indeo 4 or 5 band.
707 * @param[in,out] ctx ptr to the decoder context
708 * @param[in,out] band ptr to the band descriptor
709 * @param[in] avctx ptr to the AVCodecContext
710 * @return result code: 0 = OK, -1 = error
712 static int decode_band(IVI45DecContext *ctx,
713 IVIBandDesc *band, AVCodecContext *avctx)
715 int result, i, t, idx1, idx2, pos;
718 band->buf = band->bufs[ctx->dst_buf];
720 av_log(avctx, AV_LOG_ERROR, "Band buffer points to no data!\n");
721 return AVERROR_INVALIDDATA;
723 band->ref_buf = band->bufs[ctx->ref_buf];
724 band->data_ptr = ctx->frame_data + (get_bits_count(&ctx->gb) >> 3);
726 result = ctx->decode_band_hdr(ctx, band, avctx);
728 av_log(avctx, AV_LOG_ERROR, "Error while decoding band header: %d\n",
733 if (band->is_empty) {
734 av_log(avctx, AV_LOG_ERROR, "Empty band encountered!\n");
735 return AVERROR_INVALIDDATA;
738 band->rv_map = &ctx->rvmap_tabs[band->rvmap_sel];
740 /* apply corrections to the selected rvmap table if present */
741 for (i = 0; i < band->num_corr; i++) {
742 idx1 = band->corr[i * 2];
743 idx2 = band->corr[i * 2 + 1];
744 FFSWAP(uint8_t, band->rv_map->runtab[idx1], band->rv_map->runtab[idx2]);
745 FFSWAP(int16_t, band->rv_map->valtab[idx1], band->rv_map->valtab[idx2]);
748 pos = get_bits_count(&ctx->gb);
750 for (t = 0; t < band->num_tiles; t++) {
751 tile = &band->tiles[t];
753 if (tile->mb_size != band->mb_size) {
754 av_log(avctx, AV_LOG_ERROR, "MB sizes mismatch: %d vs. %d\n",
755 band->mb_size, tile->mb_size);
756 return AVERROR_INVALIDDATA;
758 tile->is_empty = get_bits1(&ctx->gb);
759 if (tile->is_empty) {
760 result = ivi_process_empty_tile(avctx, band, tile,
761 (ctx->planes[0].bands[0].mb_size >> 3) - (band->mb_size >> 3));
764 av_dlog(avctx, "Empty tile encountered!\n");
766 tile->data_size = ivi_dec_tile_data_size(&ctx->gb);
767 if (!tile->data_size) {
768 av_log(avctx, AV_LOG_ERROR, "Tile data size is zero!\n");
769 return AVERROR_INVALIDDATA;
772 result = ctx->decode_mb_info(ctx, band, tile, avctx);
776 result = ivi_decode_blocks(&ctx->gb, band, tile, avctx);
777 if (result < 0 || ((get_bits_count(&ctx->gb) - pos) >> 3) != tile->data_size) {
778 av_log(avctx, AV_LOG_ERROR, "Corrupted tile data encountered!\n");
782 pos += tile->data_size << 3; // skip to next tile
786 /* restore the selected rvmap table by applying its corrections in reverse order */
787 for (i = band->num_corr-1; i >= 0; i--) {
788 idx1 = band->corr[i*2];
789 idx2 = band->corr[i*2+1];
790 FFSWAP(uint8_t, band->rv_map->runtab[idx1], band->rv_map->runtab[idx2]);
791 FFSWAP(int16_t, band->rv_map->valtab[idx1], band->rv_map->valtab[idx2]);
795 if (band->checksum_present) {
796 uint16_t chksum = ivi_calc_band_checksum(band);
797 if (chksum != band->checksum) {
798 av_log(avctx, AV_LOG_ERROR,
799 "Band checksum mismatch! Plane %d, band %d, received: %x, calculated: %x\n",
800 band->plane, band->band_num, band->checksum, chksum);
805 align_get_bits(&ctx->gb);
810 int ff_ivi_decode_frame(AVCodecContext *avctx, void *data, int *got_frame,
813 IVI45DecContext *ctx = avctx->priv_data;
814 const uint8_t *buf = avpkt->data;
815 AVFrame *frame = data;
816 int buf_size = avpkt->size;
819 init_get_bits(&ctx->gb, buf, buf_size * 8);
820 ctx->frame_data = buf;
821 ctx->frame_size = buf_size;
823 result = ctx->decode_pic_hdr(ctx, avctx);
825 av_log(avctx, AV_LOG_ERROR,
826 "Error while decoding picture header: %d\n", result);
829 if (ctx->gop_invalid)
830 return AVERROR_INVALIDDATA;
832 if (ctx->gop_flags & IVI5_IS_PROTECTED) {
833 av_log(avctx, AV_LOG_ERROR, "Password-protected clip!\n");
837 ctx->switch_buffers(ctx);
841 if (ctx->is_nonnull_frame(ctx)) {
842 for (p = 0; p < 3; p++) {
843 for (b = 0; b < ctx->planes[p].num_bands; b++) {
844 result = decode_band(ctx, &ctx->planes[p].bands[b], avctx);
846 av_log(avctx, AV_LOG_ERROR,
847 "Error while decoding band: %d, plane: %d\n", b, p);
854 //STOP_TIMER("decode_planes"); }
856 /* If the bidirectional mode is enabled, next I and the following P frame will */
857 /* be sent together. Unfortunately the approach below seems to be the only way */
858 /* to handle the B-frames mode. That's exactly the same Intel decoders do. */
859 if (avctx->codec_id == AV_CODEC_ID_INDEO4 && ctx->frame_type == 0/*FRAMETYPE_INTRA*/) {
860 while (get_bits(&ctx->gb, 8)); // skip version string
861 skip_bits_long(&ctx->gb, 64); // skip padding, TODO: implement correct 8-bytes alignment
862 if (get_bits_left(&ctx->gb) > 18 && show_bits(&ctx->gb, 18) == 0x3FFF8)
863 av_log(avctx, AV_LOG_ERROR, "Buffer contains IP frames!\n");
866 avcodec_set_dimensions(avctx, ctx->planes[0].width, ctx->planes[0].height);
867 if ((result = ff_get_buffer(avctx, frame, 0)) < 0) {
868 av_log(avctx, AV_LOG_ERROR, "get_buffer() failed\n");
872 if (ctx->is_scalable) {
873 if (avctx->codec_id == AV_CODEC_ID_INDEO4)
874 ff_ivi_recompose_haar(&ctx->planes[0], frame->data[0], frame->linesize[0]);
876 ff_ivi_recompose53 (&ctx->planes[0], frame->data[0], frame->linesize[0]);
878 ivi_output_plane(&ctx->planes[0], frame->data[0], frame->linesize[0]);
881 ivi_output_plane(&ctx->planes[2], frame->data[1], frame->linesize[1]);
882 ivi_output_plane(&ctx->planes[1], frame->data[2], frame->linesize[2]);
890 * Close Indeo5 decoder and clean up its context.
892 av_cold int ff_ivi_decode_close(AVCodecContext *avctx)
894 IVI45DecContext *ctx = avctx->priv_data;
896 ivi_free_buffers(&ctx->planes[0]);
898 if (ctx->mb_vlc.cust_tab.table)
899 ff_free_vlc(&ctx->mb_vlc.cust_tab);
901 #if IVI4_STREAM_ANALYSER
902 if (avctx->codec_id == AV_CODEC_ID_INDEO4) {
903 if (ctx->is_scalable)
904 av_log(avctx, AV_LOG_ERROR, "This video uses scalability mode!\n");
905 if (ctx->uses_tiling)
906 av_log(avctx, AV_LOG_ERROR, "This video uses local decoding!\n");
907 if (ctx->has_b_frames)
908 av_log(avctx, AV_LOG_ERROR, "This video contains B-frames!\n");
910 av_log(avctx, AV_LOG_ERROR, "Transparency mode is enabled!\n");
912 av_log(avctx, AV_LOG_ERROR, "This video uses Haar transform!\n");
913 if (ctx->uses_fullpel)
914 av_log(avctx, AV_LOG_ERROR, "This video uses fullpel motion vectors!\n");
923 * These are 2x8 predefined Huffman codebooks for coding macroblock/block
924 * signals. They are specified using "huffman descriptors" in order to
925 * avoid huge static tables. The decoding tables will be generated at
926 * startup from these descriptors.
928 const IVIHuffDesc ff_ivi_mb_huff_desc[8] = {
929 {8, {0, 4, 5, 4, 4, 4, 6, 6}},
930 {12, {0, 2, 2, 3, 3, 3, 3, 5, 3, 2, 2, 2}},
931 {12, {0, 2, 3, 4, 3, 3, 3, 3, 4, 3, 2, 2}},
932 {12, {0, 3, 4, 4, 3, 3, 3, 3, 3, 2, 2, 2}},
933 {13, {0, 4, 4, 3, 3, 3, 3, 2, 3, 3, 2, 1, 1}},
934 {9, {0, 4, 4, 4, 4, 3, 3, 3, 2}},
935 {10, {0, 4, 4, 4, 4, 3, 3, 2, 2, 2}},
936 {12, {0, 4, 4, 4, 3, 3, 2, 3, 2, 2, 2, 2}}
939 const IVIHuffDesc ff_ivi_blk_huff_desc[8] = {
940 {10, {1, 2, 3, 4, 4, 7, 5, 5, 4, 1}},
941 {11, {2, 3, 4, 4, 4, 7, 5, 4, 3, 3, 2}},
942 {12, {2, 4, 5, 5, 5, 5, 6, 4, 4, 3, 1, 1}},
943 {13, {3, 3, 4, 4, 5, 6, 6, 4, 4, 3, 2, 1, 1}},
944 {11, {3, 4, 4, 5, 5, 5, 6, 5, 4, 2, 2}},
945 {13, {3, 4, 5, 5, 5, 5, 6, 4, 3, 3, 2, 1, 1}},
946 {13, {3, 4, 5, 5, 5, 6, 5, 4, 3, 3, 2, 1, 1}},
947 {9, {3, 4, 4, 5, 5, 5, 6, 5, 5}}
952 * Scan patterns shared between indeo4 and indeo5
954 const uint8_t ff_ivi_vertical_scan_8x8[64] = {
955 0, 8, 16, 24, 32, 40, 48, 56,
956 1, 9, 17, 25, 33, 41, 49, 57,
957 2, 10, 18, 26, 34, 42, 50, 58,
958 3, 11, 19, 27, 35, 43, 51, 59,
959 4, 12, 20, 28, 36, 44, 52, 60,
960 5, 13, 21, 29, 37, 45, 53, 61,
961 6, 14, 22, 30, 38, 46, 54, 62,
962 7, 15, 23, 31, 39, 47, 55, 63
965 const uint8_t ff_ivi_horizontal_scan_8x8[64] = {
966 0, 1, 2, 3, 4, 5, 6, 7,
967 8, 9, 10, 11, 12, 13, 14, 15,
968 16, 17, 18, 19, 20, 21, 22, 23,
969 24, 25, 26, 27, 28, 29, 30, 31,
970 32, 33, 34, 35, 36, 37, 38, 39,
971 40, 41, 42, 43, 44, 45, 46, 47,
972 48, 49, 50, 51, 52, 53, 54, 55,
973 56, 57, 58, 59, 60, 61, 62, 63
976 const uint8_t ff_ivi_direct_scan_4x4[16] = {
977 0, 1, 4, 8, 5, 2, 3, 6, 9, 12, 13, 10, 7, 11, 14, 15
982 * Run-value (RLE) tables.
984 const RVMapDesc ff_ivi_rvmap_tabs[9] = {
989 {1, 1, 0, 1, 1, 0, 1, 1, 2, 2, 1, 1, 1, 1, 3, 3,
990 1, 1, 2, 2, 1, 1, 4, 4, 1, 1, 1, 1, 2, 2, 5, 5,
991 1, 1, 3, 3, 1, 1, 6, 6, 1, 2, 1, 2, 7, 7, 1, 1,
992 8, 8, 1, 1, 4, 2, 1, 4, 2, 1, 3, 3, 1, 1, 1, 9,
993 9, 1, 2, 1, 2, 1, 5, 5, 1, 1, 10, 10, 1, 1, 3, 3,
994 2, 2, 1, 1, 11, 11, 6, 4, 4, 1, 6, 1, 2, 1, 2, 12,
995 8, 1, 12, 7, 8, 7, 1, 16, 1, 16, 1, 3, 3, 13, 1, 13,
996 2, 2, 1, 15, 1, 5, 14, 15, 1, 5, 14, 1, 17, 8, 17, 8,
997 1, 4, 4, 2, 2, 1, 25, 25, 24, 24, 1, 3, 1, 3, 1, 8,
998 6, 7, 6, 1, 18, 8, 18, 1, 7, 23, 2, 2, 23, 1, 1, 21,
999 22, 9, 9, 22, 19, 1, 21, 5, 19, 5, 1, 33, 20, 33, 20, 8,
1000 4, 4, 1, 32, 2, 2, 8, 3, 32, 26, 3, 1, 7, 7, 26, 6,
1001 1, 6, 1, 1, 16, 1, 10, 1, 10, 2, 16, 29, 28, 2, 29, 28,
1002 1, 27, 5, 8, 5, 27, 1, 8, 3, 7, 3, 31, 41, 31, 1, 41,
1003 6, 1, 6, 7, 4, 4, 1, 1, 2, 1, 2, 11, 34, 30, 11, 1,
1004 30, 15, 15, 34, 36, 40, 36, 40, 35, 35, 37, 37, 39, 39, 38, 38},
1007 { 1, -1, 0, 2, -2, 0, 3, -3, 1, -1, 4, -4, 5, -5, 1, -1,
1008 6, -6, 2, -2, 7, -7, 1, -1, 8, -8, 9, -9, 3, -3, 1, -1,
1009 10, -10, 2, -2, 11, -11, 1, -1, 12, 4, -12, -4, 1, -1, 13, -13,
1010 1, -1, 14, -14, 2, 5, 15, -2, -5, -15, -3, 3, 16, -16, 17, 1,
1011 -1, -17, 6, 18, -6, -18, 2, -2, 19, -19, 1, -1, 20, -20, 4, -4,
1012 7, -7, 21, -21, 1, -1, 2, 3, -3, 22, -2, -22, 8, 23, -8, 1,
1013 2, -23, -1, 2, -2, -2, 24, 1, -24, -1, 25, 5, -5, 1, -25, -1,
1014 9, -9, 26, 1, -26, 3, 1, -1, 27, -3, -1, -27, 1, 3, -1, -3,
1015 28, -4, 4, 10, -10, -28, 1, -1, 1, -1, 29, 6, -29, -6, 30, -4,
1016 3, 3, -3, -30, 1, 4, -1, 31, -3, 1, 11, -11, -1, -31, 32, -1,
1017 -1, 2, -2, 1, 1, -32, 1, 4, -1, -4, 33, -1, 1, 1, -1, 5,
1018 5, -5, -33, -1, -12, 12, -5, -7, 1, 1, 7, 34, 4, -4, -1, 4,
1019 -34, -4, 35, 36, -2, -35, -2, -36, 2, 13, 2, -1, 1, -13, 1, -1,
1020 37, 1, -5, 6, 5, -1, 38, -6, -8, 5, 8, -1, 1, 1, -37, -1,
1021 5, 39, -5, -5, 6, -6, -38, -39, -14, 40, 14, 2, 1, 1, -2, -40,
1022 -1, -2, 2, -1, -1, -1, 1, 1, 1, -1, 1, -1, 1, -1, 1, -1}
1028 {0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 8, 6, 8, 7,
1029 7, 9, 9, 10, 10, 11, 11, 1, 12, 1, 12, 13, 13, 16, 14, 16,
1030 14, 15, 15, 17, 17, 18, 0, 18, 19, 20, 21, 19, 22, 21, 20, 22,
1031 25, 24, 2, 25, 24, 23, 23, 2, 26, 28, 26, 28, 29, 27, 29, 27,
1032 33, 33, 1, 32, 1, 3, 32, 30, 36, 3, 36, 30, 31, 31, 35, 34,
1033 37, 41, 34, 35, 37, 4, 41, 4, 49, 8, 8, 49, 40, 38, 5, 38,
1034 40, 39, 5, 39, 42, 43, 42, 7, 57, 6, 43, 44, 6, 50, 7, 44,
1035 57, 48, 50, 48, 45, 45, 46, 47, 51, 46, 47, 58, 1, 51, 58, 1,
1036 52, 59, 53, 9, 52, 55, 55, 59, 53, 56, 54, 56, 54, 9, 64, 64,
1037 60, 63, 60, 63, 61, 62, 61, 62, 2, 10, 2, 10, 11, 1, 11, 13,
1038 12, 1, 12, 13, 16, 16, 8, 8, 14, 3, 3, 15, 14, 15, 4, 4,
1039 1, 17, 17, 5, 1, 7, 7, 5, 6, 1, 2, 2, 6, 22, 1, 25,
1040 21, 22, 8, 24, 1, 21, 25, 24, 8, 18, 18, 23, 9, 20, 23, 33,
1041 29, 33, 20, 1, 19, 1, 29, 36, 9, 36, 19, 41, 28, 57, 32, 3,
1042 28, 3, 1, 27, 49, 49, 1, 32, 26, 26, 2, 4, 4, 7, 57, 41,
1043 2, 7, 10, 5, 37, 16, 10, 27, 8, 8, 13, 16, 37, 13, 1, 5},
1046 {0, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, 1, -1, -1, 1,
1047 -1, 1, -1, 1, -1, 1, -1, 2, 1, -2, -1, 1, -1, 1, 1, -1,
1048 -1, 1, -1, 1, -1, 1, 0, -1, 1, 1, 1, -1, 1, -1, -1, -1,
1049 1, 1, 2, -1, -1, 1, -1, -2, 1, 1, -1, -1, 1, 1, -1, -1,
1050 1, -1, 3, 1, -3, 2, -1, 1, 1, -2, -1, -1, -1, 1, 1, 1,
1051 1, 1, -1, -1, -1, 2, -1, -2, 1, 2, -2, -1, 1, 1, 2, -1,
1052 -1, 1, -2, -1, 1, 1, -1, 2, 1, 2, -1, 1, -2, -1, -2, -1,
1053 -1, 1, 1, -1, 1, -1, 1, 1, 1, -1, -1, 1, 4, -1, -1, -4,
1054 1, 1, 1, 2, -1, -1, 1, -1, -1, 1, -1, -1, 1, -2, 1, -1,
1055 1, 1, -1, -1, 1, 1, -1, -1, 3, 2, -3, -2, 2, 5, -2, 2,
1056 2, -5, -2, -2, -2, 2, -3, 3, 2, 3, -3, 2, -2, -2, 3, -3,
1057 6, 2, -2, 3, -6, 3, -3, -3, 3, 7, -4, 4, -3, 2, -7, 2,
1058 2, -2, -4, 2, 8, -2, -2, -2, 4, 2, -2, 2, 3, 2, -2, -2,
1059 2, 2, -2, -8, -2, 9, -2, 2, -3, -2, 2, -2, 2, 2, 2, 4,
1060 -2, -4, 10, 2, 2, -2, -9, -2, 2, -2, 5, 4, -4, 4, -2, 2,
1061 -5, -4, -3, 4, 2, -3, 3, -2, -5, 5, 3, 3, -2, -3, -10, -4}
1067 {1, 1, 0, 2, 2, 1, 1, 3, 3, 4, 4, 0, 1, 1, 5, 5,
1068 2, 2, 6, 6, 7, 7, 1, 8, 1, 8, 3, 3, 9, 9, 1, 2,
1069 2, 1, 4, 10, 4, 10, 11, 11, 1, 5, 12, 12, 1, 5, 13, 13,
1070 3, 3, 6, 6, 2, 2, 14, 14, 16, 16, 15, 7, 15, 8, 8, 7,
1071 1, 1, 17, 17, 4, 4, 1, 1, 18, 18, 2, 2, 5, 5, 25, 3,
1072 9, 3, 25, 9, 19, 24, 19, 24, 1, 21, 20, 1, 21, 22, 20, 22,
1073 23, 23, 8, 6, 33, 6, 8, 33, 7, 7, 26, 26, 1, 32, 1, 32,
1074 28, 4, 28, 10, 29, 27, 27, 10, 41, 4, 29, 2, 2, 41, 36, 31,
1075 49, 31, 34, 30, 34, 36, 30, 35, 1, 49, 11, 5, 35, 11, 1, 3,
1076 3, 5, 37, 37, 8, 40, 8, 40, 12, 12, 42, 42, 1, 38, 16, 57,
1077 1, 6, 16, 39, 38, 6, 7, 7, 13, 13, 39, 43, 2, 43, 57, 2,
1078 50, 9, 44, 9, 50, 4, 15, 48, 44, 4, 1, 15, 48, 14, 14, 1,
1079 45, 45, 8, 3, 5, 8, 51, 47, 3, 46, 46, 47, 5, 51, 1, 17,
1080 17, 58, 1, 58, 2, 52, 52, 2, 53, 7, 59, 6, 6, 56, 53, 55,
1081 7, 55, 1, 54, 59, 56, 54, 10, 1, 10, 4, 60, 1, 60, 8, 4,
1082 8, 64, 64, 61, 1, 63, 3, 63, 62, 61, 5, 11, 5, 3, 11, 62},
1085 { 1, -1, 0, 1, -1, 2, -2, 1, -1, 1, -1, 0, 3, -3, 1, -1,
1086 2, -2, 1, -1, 1, -1, 4, 1, -4, -1, 2, -2, 1, -1, 5, 3,
1087 -3, -5, 2, 1, -2, -1, 1, -1, 6, 2, 1, -1, -6, -2, 1, -1,
1088 3, -3, 2, -2, 4, -4, 1, -1, 1, -1, 1, 2, -1, 2, -2, -2,
1089 7, -7, 1, -1, 3, -3, 8, -8, 1, -1, 5, -5, 3, -3, 1, 4,
1090 2, -4, -1, -2, 1, 1, -1, -1, 9, 1, 1, -9, -1, 1, -1, -1,
1091 1, -1, 3, -3, 1, 3, -3, -1, 3, -3, 1, -1, 10, 1, -10, -1,
1092 1, 4, -1, 2, 1, -1, 1, -2, 1, -4, -1, 6, -6, -1, 1, 1,
1093 1, -1, 1, 1, -1, -1, -1, 1, 11, -1, -2, 4, -1, 2, -11, 5,
1094 -5, -4, -1, 1, 4, 1, -4, -1, -2, 2, 1, -1, 12, 1, -2, 1,
1095 -12, 4, 2, 1, -1, -4, 4, -4, 2, -2, -1, 1, 7, -1, -1, -7,
1096 -1, -3, 1, 3, 1, 5, 2, 1, -1, -5, 13, -2, -1, 2, -2, -13,
1097 1, -1, 5, 6, 5, -5, 1, 1, -6, 1, -1, -1, -5, -1, 14, 2,
1098 -2, 1, -14, -1, 8, 1, -1, -8, 1, 5, 1, 5, -5, 1, -1, 1,
1099 -5, -1, 15, 1, -1, -1, -1, 3, -15, -3, 6, 1, 16, -1, 6, -6,
1100 -6, 1, -1, 1, -16, 1, 7, -1, 1, -1, -6, -3, 6, -7, 3, -1}
1106 {0, 1, 1, 2, 2, 3, 3, 4, 4, 1, 1, 5, 5, 6, 6, 7,
1107 7, 8, 8, 9, 9, 2, 2, 10, 10, 1, 1, 11, 11, 12, 12, 3,
1108 3, 13, 13, 0, 14, 14, 16, 15, 16, 15, 4, 4, 17, 1, 17, 1,
1109 5, 5, 18, 18, 2, 2, 6, 6, 8, 19, 7, 8, 7, 19, 20, 20,
1110 21, 21, 22, 24, 22, 24, 23, 23, 1, 1, 25, 25, 3, 3, 26, 26,
1111 9, 9, 27, 27, 28, 28, 33, 29, 4, 33, 29, 1, 4, 1, 32, 32,
1112 2, 2, 31, 10, 30, 10, 30, 31, 34, 34, 5, 5, 36, 36, 35, 41,
1113 35, 11, 41, 11, 37, 1, 8, 8, 37, 6, 1, 6, 40, 7, 7, 40,
1114 12, 38, 12, 39, 39, 38, 49, 13, 49, 13, 3, 42, 3, 42, 16, 16,
1115 43, 43, 14, 14, 1, 1, 44, 15, 44, 15, 2, 2, 57, 48, 50, 48,
1116 57, 50, 4, 45, 45, 4, 46, 47, 47, 46, 1, 51, 1, 17, 17, 51,
1117 8, 9, 9, 5, 58, 8, 58, 5, 52, 52, 55, 56, 53, 56, 55, 59,
1118 59, 53, 54, 1, 6, 54, 7, 7, 6, 1, 2, 3, 2, 3, 64, 60,
1119 60, 10, 10, 64, 61, 62, 61, 63, 1, 63, 62, 1, 18, 24, 18, 4,
1120 25, 4, 8, 21, 21, 1, 24, 22, 25, 22, 8, 11, 19, 11, 23, 1,
1121 20, 23, 19, 20, 5, 12, 5, 1, 16, 2, 12, 13, 2, 13, 1, 16},
1124 { 0, 1, -1, 1, -1, 1, -1, 1, -1, 2, -2, 1, -1, 1, -1, 1,
1125 -1, 1, -1, 1, -1, 2, -2, 1, -1, 3, -3, 1, -1, 1, -1, 2,
1126 -2, 1, -1, 0, 1, -1, 1, 1, -1, -1, 2, -2, 1, 4, -1, -4,
1127 2, -2, 1, -1, -3, 3, 2, -2, 2, 1, 2, -2, -2, -1, 1, -1,
1128 1, -1, 1, 1, -1, -1, 1, -1, 5, -5, 1, -1, 3, -3, 1, -1,
1129 2, -2, 1, -1, 1, -1, 1, 1, 3, -1, -1, 6, -3, -6, -1, 1,
1130 4, -4, 1, 2, 1, -2, -1, -1, 1, -1, 3, -3, 1, -1, 1, 1,
1131 -1, 2, -1, -2, 1, 7, -3, 3, -1, 3, -7, -3, 1, -3, 3, -1,
1132 2, 1, -2, 1, -1, -1, 1, 2, -1, -2, -4, -1, 4, 1, 2, -2,
1133 1, -1, -2, 2, 8, -8, -1, 2, 1, -2, -5, 5, 1, -1, -1, 1,
1134 -1, 1, 4, -1, 1, -4, -1, -1, 1, 1, 9, 1, -9, 2, -2, -1,
1135 -4, 3, -3, -4, -1, 4, 1, 4, 1, -1, 1, -1, 1, 1, -1, 1,
1136 -1, -1, -1, 10, 4, 1, 4, -4, -4, -10, 6, 5, -6, -5, 1, -1,
1137 1, 3, -3, -1, 1, -1, -1, -1, 11, 1, 1, -11, -2, -2, 2, 5,
1138 -2, -5, -5, 2, -2, 12, 2, -2, 2, 2, 5, -3, -2, 3, -2, -12,
1139 -2, 2, 2, 2, -5, 3, 5, 13, -3, 7, -3, -3, -7, 3, -13, 3}
1145 {0, 1, 1, 1, 2, 2, 1, 3, 3, 1, 1, 1, 4, 4, 1, 5,
1146 2, 1, 5, 2, 1, 1, 6, 6, 1, 1, 1, 1, 1, 7, 3, 1,
1147 2, 3, 0, 1, 2, 7, 1, 1, 1, 8, 1, 1, 8, 1, 1, 1,
1148 9, 1, 9, 1, 2, 1, 1, 2, 1, 1, 10, 4, 1, 10, 1, 4,
1149 1, 1, 1, 1, 1, 3, 1, 1, 1, 3, 2, 1, 5, 1, 1, 1,
1150 2, 5, 1, 11, 1, 11, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1151 2, 1, 6, 1, 6, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 12,
1152 3, 1, 12, 1, 1, 1, 2, 1, 1, 3, 1, 1, 1, 1, 1, 1,
1153 4, 1, 1, 1, 2, 1, 1, 4, 1, 1, 1, 1, 1, 1, 2, 1,
1154 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 2, 1, 1, 5,
1155 1, 1, 1, 1, 1, 7, 1, 7, 1, 1, 2, 3, 1, 1, 1, 1,
1156 5, 1, 1, 1, 1, 1, 1, 2, 13, 1, 1, 1, 1, 1, 1, 1,
1157 1, 1, 1, 1, 1, 1, 1, 1, 13, 2, 1, 1, 4, 1, 1, 1,
1158 3, 1, 6, 1, 1, 1, 14, 1, 1, 1, 1, 1, 14, 6, 1, 1,
1159 1, 1, 15, 2, 4, 1, 2, 3, 15, 1, 1, 1, 8, 1, 1, 8,
1160 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1},
1163 { 0, 1, -1, 2, 1, -1, -2, 1, -1, 3, -3, 4, 1, -1, -4, 1,
1164 2, 5, -1, -2, -5, 6, 1, -1, -6, 7, -7, 8, -8, 1, 2, 9,
1165 3, -2, 0, -9, -3, -1, 10, -10, 11, 1, -11, 12, -1, -12, 13, -13,
1166 1, 14, -1, -14, 4, 15, -15, -4, 16, -16, 1, 2, 17, -1, -17, -2,
1167 18, -18, 19, -19, 20, 3, -20, 21, -21, -3, 5, 22, 2, -22, -23, 23,
1168 -5, -2, 24, 1, -24, -1, 25, -25, 26, -26, -27, 27, 28, 29, -28, -29,
1169 6, 30, 2, -31, -2, -30, 31, -6, -32, 32, 33, -33, 34, -35, -34, 1,
1170 4, -36, -1, 35, 37, 36, 7, -37, 38, -4, -38, 39, 41, 40, -40, -39,
1171 3, 42, -43, -41, -7, -42, 43, -3, 44, -44, 45, -45, 46, 47, 8, -47,
1172 -48, -46, 50, -50, 48, 49, 51, -49, 52, -52, 5, -51, -8, -53, 53, 3,
1173 -56, 56, 55, 54, -54, 2, 60, -2, -55, 58, 9, -5, 59, 57, -57, -63,
1174 -3, -58, -60, -61, 61, -59, -62, -9, 1, 64, 62, 69, -64, 63, 65, -67,
1175 -68, 66, -65, 68, -66, -69, 67, -70, -1, 10, 71, -71, 4, 73, 72, 70,
1176 6, -76, -3, 74, -78, -74, 1, 78, 80, -72, -75, 76, -1, 3, -73, 79,
1177 75, 77, 1, 11, -4, -79, -10, -6, -1, -77, -83, -80, 2, 81, -84, -2,
1178 83, -81, 82, -82, 84, -87, -86, 85, -11, -85, 86, -89, 87, -88, 88, 89}
1184 {1, 1, 0, 2, 1, 2, 1, 3, 3, 1, 1, 4, 4, 2, 2, 1,
1185 1, 5, 5, 6, 1, 6, 1, 7, 7, 3, 3, 2, 8, 2, 8, 1,
1186 1, 0, 9, 9, 1, 1, 10, 4, 10, 4, 11, 11, 2, 1, 2, 1,
1187 12, 12, 3, 3, 1, 1, 13, 5, 5, 13, 14, 1, 1, 14, 2, 2,
1188 6, 6, 15, 1, 1, 15, 16, 4, 7, 16, 4, 7, 1, 1, 3, 3,
1189 8, 8, 2, 2, 1, 1, 17, 17, 1, 1, 18, 18, 5, 5, 2, 2,
1190 1, 1, 9, 19, 9, 19, 20, 3, 3, 20, 1, 10, 21, 1, 10, 4,
1191 4, 21, 22, 6, 6, 22, 1, 1, 23, 24, 2, 2, 23, 24, 11, 1,
1192 1, 11, 7, 25, 7, 1, 1, 25, 8, 8, 3, 26, 3, 1, 12, 2,
1193 2, 26, 1, 12, 5, 5, 27, 4, 1, 4, 1, 27, 28, 1, 28, 13,
1194 1, 13, 2, 29, 2, 1, 32, 6, 1, 30, 14, 29, 14, 6, 3, 31,
1195 3, 1, 30, 1, 32, 31, 33, 9, 33, 1, 1, 7, 9, 7, 2, 2,
1196 1, 1, 4, 36, 34, 4, 5, 10, 10, 5, 34, 1, 1, 35, 8, 8,
1197 36, 3, 35, 1, 15, 3, 2, 1, 16, 15, 16, 2, 37, 1, 37, 1,
1198 1, 1, 6, 6, 38, 1, 38, 11, 1, 39, 39, 40, 11, 2, 41, 4,
1199 40, 1, 2, 4, 1, 1, 1, 41, 3, 1, 3, 1, 5, 7, 5, 7},
1202 { 1, -1, 0, 1, 2, -1, -2, 1, -1, 3, -3, 1, -1, 2, -2, 4,
1203 -4, 1, -1, 1, 5, -1, -5, 1, -1, 2, -2, 3, 1, -3, -1, 6,
1204 -6, 0, 1, -1, 7, -7, 1, 2, -1, -2, 1, -1, 4, 8, -4, -8,
1205 1, -1, 3, -3, 9, -9, 1, 2, -2, -1, 1, 10, -10, -1, 5, -5,
1206 2, -2, 1, 11, -11, -1, 1, 3, 2, -1, -3, -2, 12, -12, 4, -4,
1207 2, -2, -6, 6, 13, -13, 1, -1, 14, -14, 1, -1, 3, -3, 7, -7,
1208 15, -15, 2, 1, -2, -1, 1, 5, -5, -1, -16, 2, 1, 16, -2, 4,
1209 -4, -1, 1, 3, -3, -1, 17, -17, 1, 1, -8, 8, -1, -1, 2, 18,
1210 -18, -2, 3, 1, -3, 19, -19, -1, 3, -3, 6, 1, -6, 20, 2, 9,
1211 -9, -1, -20, -2, 4, -4, 1, -5, 21, 5, -21, -1, 1, -22, -1, 2,
1212 22, -2, 10, 1, -10, 23, 1, 4, -23, 1, 2, -1, -2, -4, -7, 1,
1213 7, -24, -1, 24, -1, -1, 1, 3, -1, -25, 25, 4, -3, -4, 11, -11,
1214 26, -26, 6, 1, 1, -6, -5, -3, 3, 5, -1, -27, 27, 1, 4, -4,
1215 -1, -8, -1, 28, 2, 8, -12, -28, -2, -2, 2, 12, -1, 29, 1, -29,
1216 30, -30, 5, -5, 1, -31, -1, 3, 31, -1, 1, 1, -3, -13, 1, -7,
1217 -1, -32, 13, 7, 32, 33, -33, -1, -9, -34, 9, 34, -6, 5, 6, -5}
1223 {1, 1, 0, 1, 1, 2, 2, 1, 1, 3, 3, 1, 1, 0, 2, 2,
1224 4, 1, 4, 1, 1, 1, 5, 5, 1, 1, 6, 6, 2, 2, 1, 1,
1225 3, 3, 7, 7, 1, 1, 8, 8, 1, 1, 2, 2, 1, 9, 1, 9,
1226 4, 4, 10, 1, 1, 10, 1, 1, 11, 11, 3, 3, 1, 2, 1, 2,
1227 1, 1, 12, 12, 5, 5, 1, 1, 13, 1, 1, 13, 2, 2, 1, 1,
1228 6, 6, 1, 1, 4, 14, 4, 14, 3, 1, 3, 1, 1, 1, 15, 7,
1229 15, 2, 2, 7, 1, 1, 1, 8, 1, 8, 16, 16, 1, 1, 1, 1,
1230 2, 1, 1, 2, 1, 1, 3, 5, 5, 3, 4, 1, 1, 4, 1, 1,
1231 17, 17, 9, 1, 1, 9, 2, 2, 1, 1, 10, 10, 1, 6, 1, 1,
1232 6, 18, 1, 1, 18, 1, 1, 1, 2, 2, 3, 1, 3, 1, 1, 1,
1233 4, 1, 19, 1, 19, 7, 1, 1, 20, 1, 4, 20, 1, 7, 11, 2,
1234 1, 11, 21, 2, 8, 5, 1, 8, 1, 5, 21, 1, 1, 1, 22, 1,
1235 1, 22, 1, 1, 3, 3, 1, 23, 2, 12, 24, 1, 1, 2, 1, 1,
1236 12, 23, 1, 1, 24, 1, 1, 1, 4, 1, 1, 1, 2, 1, 6, 6,
1237 4, 2, 1, 1, 1, 1, 1, 1, 1, 14, 13, 3, 1, 25, 9, 25,
1238 14, 1, 9, 3, 13, 1, 1, 1, 1, 1, 10, 1, 1, 2, 10, 2},
1241 {-20, -1, 0, 2, -2, 1, -1, 3, -3, 1, -1, 4, -4, 0, 2, -2,
1242 1, 5, -1, -5, 6, -6, 1, -1, 7, -7, 1, -1, 3, -3, 8, -8,
1243 2, -2, 1, -1, 9, -9, 1, -1, 10, -10, 4, -4, 11, 1, -11, -1,
1244 2, -2, 1, 12, -12, -1, 13, -13, 1, -1, 3, -3, 14, 5, -14, -5,
1245 -15, 15, -1, 1, 2, -2, 16, -16, 1, 17, -17, -1, 6, -6, 18, -18,
1246 2, -2, -19, 19, -3, 1, 3, -1, 4, 20, -4, 1, -21, 21, 1, 2,
1247 -1, -7, 7, -2, 22, -22, 23, 2, -23, -2, 1, -1, -24, 24, -25, 25,
1248 -8, -26, 26, 8, -27, 27, 5, 3, -3, -5, -4, 28, -28, 4, 29, -29,
1249 1, -1, -2, -30, 30, 2, 9, -9, -31, 31, 2, -2, -32, 3, 32, -33,
1250 -3, 1, 33, -34, -1, 34, -35, 35, -10, 10, -6, 36, 6, -36, 37, -37,
1251 -5, 38, 1, -38, -1, 3, 39, -39, -1, 40, 5, 1, -40, -3, 2, -11,
1252 -41, -2, 1, 11, -3, -4, 41, 3, 42, 4, -1, -43, -42, 43, 1, -44,
1253 45, -1, 44, -45, -7, 7, -46, 1, -12, 2, 1, -47, 46, 12, 47, 48,
1254 -2, -1, -48, 49, -1, -50, -49, 50, -6, -51, 51, 52, -13, 53, -4, 4,
1255 6, 13, -53, -52, -54, 55, 54, -55, -56, -2, 2, -8, 56, 1, -3, -1,
1256 2, 58, 3, 8, -2, 57, -58, -60, -59, -57, -3, 60, 59, -14, 3, 14}
1262 {1, 1, 0, 2, 2, 1, 1, 3, 3, 4, 4, 5, 5, 1, 1, 6,
1263 6, 2, 2, 7, 7, 8, 8, 1, 1, 3, 3, 9, 9, 10, 10, 1,
1264 1, 2, 2, 4, 4, 11, 0, 11, 12, 12, 13, 13, 1, 1, 5, 5,
1265 14, 14, 15, 16, 15, 16, 3, 3, 1, 6, 1, 6, 2, 2, 7, 7,
1266 8, 8, 17, 17, 1, 1, 4, 4, 18, 18, 2, 2, 1, 19, 1, 20,
1267 19, 20, 21, 21, 3, 3, 22, 22, 5, 5, 24, 1, 1, 23, 9, 23,
1268 24, 9, 2, 2, 10, 1, 1, 10, 6, 6, 25, 4, 4, 25, 7, 7,
1269 26, 8, 1, 8, 3, 1, 26, 3, 11, 11, 27, 27, 2, 28, 1, 2,
1270 28, 1, 12, 12, 5, 5, 29, 13, 13, 29, 32, 1, 1, 33, 31, 30,
1271 32, 4, 30, 33, 4, 31, 3, 14, 1, 1, 3, 34, 34, 2, 2, 14,
1272 6, 6, 35, 36, 35, 36, 1, 15, 1, 16, 16, 15, 7, 9, 7, 9,
1273 37, 8, 8, 37, 1, 1, 39, 2, 38, 39, 2, 40, 5, 38, 40, 5,
1274 3, 3, 4, 4, 10, 10, 1, 1, 1, 1, 41, 2, 41, 2, 6, 6,
1275 1, 1, 11, 42, 11, 43, 3, 42, 3, 17, 4, 43, 1, 17, 7, 1,
1276 8, 44, 4, 7, 44, 5, 8, 2, 5, 1, 2, 48, 45, 1, 12, 45,
1277 12, 48, 13, 13, 1, 9, 9, 46, 1, 46, 47, 47, 49, 18, 18, 49},
1280 { 1, -1, 0, 1, -1, 2, -2, 1, -1, 1, -1, 1, -1, 3, -3, 1,
1281 -1, -2, 2, 1, -1, 1, -1, 4, -4, -2, 2, 1, -1, 1, -1, 5,
1282 -5, -3, 3, 2, -2, 1, 0, -1, 1, -1, 1, -1, 6, -6, 2, -2,
1283 1, -1, 1, 1, -1, -1, -3, 3, 7, 2, -7, -2, -4, 4, 2, -2,
1284 2, -2, 1, -1, 8, -8, 3, -3, 1, -1, -5, 5, 9, 1, -9, 1,
1285 -1, -1, 1, -1, -4, 4, 1, -1, 3, -3, 1, -10, 10, 1, 2, -1,
1286 -1, -2, 6, -6, 2, 11, -11, -2, 3, -3, 1, -4, 4, -1, 3, -3,
1287 1, 3, 12, -3, -5, -12, -1, 5, 2, -2, 1, -1, -7, 1, 13, 7,
1288 -1, -13, 2, -2, 4, -4, 1, 2, -2, -1, 1, 14, -14, 1, 1, 1,
1289 -1, -5, -1, -1, 5, -1, -6, 2, -15, 15, 6, 1, -1, -8, 8, -2,
1290 -4, 4, 1, 1, -1, -1, 16, 2, -16, -2, 2, -2, 4, 3, -4, -3,
1291 -1, -4, 4, 1, -17, 17, -1, -9, 1, 1, 9, 1, -5, -1, -1, 5,
1292 -7, 7, 6, -6, 3, -3, 18, -18, 19, -19, 1, -10, -1, 10, -5, 5,
1293 20, -20, -3, 1, 3, 1, 8, -1, -8, 2, 7, -1, -21, -2, 5, 21,
1294 5, -1, -7, -5, 1, -6, -5, -11, 6, 22, 11, 1, 1, -22, -3, -1,
1295 3, -1, 3, -3, -23, 4, -4, 1, 23, -1, 1, -1, 1, -2, 2, -1}
1301 {1, 1, 1, 1, 0, 2, 2, 1, 1, 3, 3, 0, 1, 1, 2, 2,
1302 4, 4, 1, 1, 5, 5, 1, 1, 2, 2, 3, 3, 6, 6, 1, 1,
1303 7, 7, 8, 1, 8, 2, 2, 1, 4, 4, 1, 3, 1, 3, 9, 9,
1304 2, 2, 1, 5, 1, 5, 10, 10, 1, 1, 11, 11, 3, 6, 3, 4,
1305 4, 6, 2, 2, 1, 12, 1, 12, 7, 13, 7, 13, 1, 1, 8, 8,
1306 2, 2, 14, 14, 16, 15, 16, 5, 5, 1, 3, 15, 1, 3, 4, 4,
1307 1, 1, 17, 17, 2, 2, 6, 6, 1, 18, 1, 18, 22, 21, 22, 21,
1308 25, 24, 25, 19, 9, 20, 9, 23, 19, 24, 20, 3, 23, 7, 3, 1,
1309 1, 7, 28, 26, 29, 5, 28, 26, 5, 8, 29, 4, 8, 27, 2, 2,
1310 4, 27, 1, 1, 10, 36, 10, 33, 33, 36, 30, 1, 32, 32, 1, 30,
1311 6, 31, 31, 35, 3, 6, 11, 11, 3, 2, 35, 2, 34, 1, 34, 1,
1312 37, 37, 12, 7, 12, 5, 41, 5, 4, 7, 1, 8, 13, 4, 1, 41,
1313 13, 38, 8, 38, 9, 1, 40, 40, 9, 1, 39, 2, 2, 49, 39, 42,
1314 3, 3, 14, 16, 49, 14, 16, 42, 43, 43, 6, 6, 15, 1, 1, 15,
1315 44, 44, 1, 1, 50, 48, 4, 5, 4, 7, 5, 2, 10, 10, 48, 7,
1316 50, 45, 2, 1, 45, 8, 8, 1, 46, 46, 3, 47, 47, 3, 1, 1},
1319 { 1, -1, 2, -2, 0, 1, -1, 3, -3, 1, -1, 0, 4, -4, 2, -2,
1320 1, -1, 5, -5, 1, -1, 6, -6, 3, -3, 2, -2, 1, -1, 7, -7,
1321 1, -1, 1, 8, -1, 4, -4, -8, 2, -2, 9, 3, -9, -3, 1, -1,
1322 5, -5, 10, 2, -10, -2, 1, -1, 11, -11, 1, -1, -4, 2, 4, 3,
1323 -3, -2, 6, -6, 12, 1, -12, -1, 2, 1, -2, -1, 13, -13, 2, -2,
1324 7, -7, 1, -1, 1, 1, -1, 3, -3, 14, 5, -1, -14, -5, 4, -4,
1325 15, -15, 1, -1, 8, -8, -3, 3, 16, 1, -16, -1, 1, 1, -1, -1,
1326 1, 1, -1, 1, 2, 1, -2, 1, -1, -1, -1, 6, -1, 3, -6, 17,
1327 -17, -3, 1, 1, 1, 4, -1, -1, -4, 3, -1, 5, -3, -1, -9, 9,
1328 -5, 1, 18, -18, 2, 1, -2, 1, -1, -1, 1, 19, -1, 1, -19, -1,
1329 4, 1, -1, 1, 7, -4, -2, 2, -7, 10, -1, -10, 1, 20, -1, -20,
1330 1, -1, 2, 4, -2, 5, 1, -5, 6, -4, 21, 4, 2, -6, -21, -1,
1331 -2, 1, -4, -1, -3, 22, -1, 1, 3, -22, -1, 11, -11, 1, 1, 1,
1332 8, -8, 2, 2, -1, -2, -2, -1, 1, -1, -5, 5, 2, 23, -23, -2,
1333 1, -1, 24, -24, -1, -1, 7, 6, -7, 5, -6, 12, -3, 3, 1, -5,
1334 1, 1, -12, 25, -1, -5, 5, -25, -1, 1, 9, 1, -1, -9, 26, -26}