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 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)) {
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 = band->glob_quant + mb->q_delta;
422 if (avctx->codec_id == AV_CODEC_ID_INDEO4)
423 quant = av_clip(quant, 0, 31);
425 quant = av_clip(quant, 0, 23);
427 base_tab = is_intra ? band->intra_base : band->inter_base;
428 scale_tab = is_intra ? band->intra_scale : band->inter_scale;
430 quant = scale_tab[quant];
435 if (band->is_halfpel) {
436 mc_type = ((mv_y & 1) << 1) | (mv_x & 1);
438 mv_y >>= 1; /* convert halfpel vectors into fullpel ones */
441 int dmv_x, dmv_y, cx, cy;
443 dmv_x = mb->mv_x >> band->is_halfpel;
444 dmv_y = mb->mv_y >> band->is_halfpel;
445 cx = mb->mv_x & band->is_halfpel;
446 cy = mb->mv_y & band->is_halfpel;
448 if ( mb->xpos + dmv_x < 0
449 || mb->xpos + dmv_x + band->mb_size + cx > band->pitch
450 || mb->ypos + dmv_y < 0
451 || mb->ypos + dmv_y + band->mb_size + cy > band->aheight) {
452 return AVERROR_INVALIDDATA;
457 for (blk = 0; blk < num_blocks; blk++) {
458 /* adjust block position in the buffer according to its number */
460 buf_offs += blk_size;
461 } else if (blk == 2) {
462 buf_offs -= blk_size;
463 buf_offs += blk_size * band->pitch;
466 if (cbp & 1) { /* block coded ? */
468 av_log(avctx, AV_LOG_ERROR, "Scan pattern is not set.\n");
469 return AVERROR_INVALIDDATA;
473 memset(trvec, 0, num_coeffs*sizeof(trvec[0])); /* zero transform vector */
474 memset(col_flags, 0, sizeof(col_flags)); /* zero column flags */
476 while (scan_pos <= num_coeffs) {
477 sym = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
478 if (sym == rvmap->eob_sym)
479 break; /* End of block */
481 if (sym == rvmap->esc_sym) { /* Escape - run/val explicitly coded using 3 vlc codes */
482 run = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1) + 1;
483 lo = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
484 hi = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
485 val = IVI_TOSIGNED((hi << 6) | lo); /* merge them and convert into signed val */
488 av_log(avctx, AV_LOG_ERROR, "Invalid sym encountered: %d.\n", sym);
491 run = rvmap->runtab[sym];
492 val = rvmap->valtab[sym];
495 /* de-zigzag and dequantize */
497 if (scan_pos >= num_coeffs)
499 pos = band->scan[scan_pos];
502 av_dlog(avctx, "Val = 0 encountered!\n");
504 q = (base_tab[pos] * quant) >> 9;
506 val = val * q + FFSIGN(val) * (((q ^ 1) - 1) >> 1);
508 col_flags[pos & col_mask] |= !!val; /* track columns containing non-zero coeffs */
511 if (scan_pos >= num_coeffs && sym != rvmap->eob_sym)
512 return -1; /* corrupt block data */
514 /* undoing DC coeff prediction for intra-blocks */
515 if (is_intra && band->is_2d_trans) {
518 col_flags[0] |= !!prev_dc;
521 /* apply inverse transform */
522 band->inv_transform(trvec, band->buf + buf_offs,
523 band->pitch, col_flags);
525 /* apply motion compensation */
527 mc_with_delta_func(band->buf + buf_offs,
528 band->ref_buf + buf_offs + mv_y * band->pitch + mv_x,
529 band->pitch, mc_type);
531 /* block not coded */
532 /* for intra blocks apply the dc slant transform */
533 /* for inter - perform the motion compensation without delta */
535 if (band->dc_transform)
536 band->dc_transform(&prev_dc, band->buf + buf_offs,
537 band->pitch, blk_size);
539 mc_no_delta_func(band->buf + buf_offs,
540 band->ref_buf + buf_offs + mv_y * band->pitch + mv_x,
541 band->pitch, mc_type);
554 * Handle empty tiles by performing data copying and motion
555 * compensation respectively.
557 * @param[in] avctx ptr to the AVCodecContext
558 * @param[in] band pointer to the band descriptor
559 * @param[in] tile pointer to the tile descriptor
560 * @param[in] mv_scale scaling factor for motion vectors
562 static int ivi_process_empty_tile(AVCodecContext *avctx, IVIBandDesc *band,
563 IVITile *tile, int32_t mv_scale)
565 int x, y, need_mc, mbn, blk, num_blocks, mv_x, mv_y, mc_type;
566 int offs, mb_offset, row_offset;
567 IVIMbInfo *mb, *ref_mb;
570 void (*mc_no_delta_func)(int16_t *buf, const int16_t *ref_buf, uint32_t pitch,
573 if (tile->num_MBs != IVI_MBs_PER_TILE(tile->width, tile->height, band->mb_size)) {
574 av_log(avctx, AV_LOG_ERROR, "Allocated tile size %d mismatches "
575 "parameters %d in ivi_process_empty_tile()\n",
576 tile->num_MBs, IVI_MBs_PER_TILE(tile->width, tile->height, band->mb_size));
577 return AVERROR_INVALIDDATA;
580 offs = tile->ypos * band->pitch + tile->xpos;
582 ref_mb = tile->ref_mbs;
583 row_offset = band->mb_size * band->pitch;
584 need_mc = 0; /* reset the mc tracking flag */
586 for (y = tile->ypos; y < (tile->ypos + tile->height); y += band->mb_size) {
589 for (x = tile->xpos; x < (tile->xpos + tile->width); x += band->mb_size) {
592 mb->buf_offs = mb_offset;
594 mb->type = 1; /* set the macroblocks type = INTER */
595 mb->cbp = 0; /* all blocks are empty */
597 if (!band->qdelta_present && !band->plane && !band->band_num) {
598 mb->q_delta = band->glob_quant;
603 if (band->inherit_qdelta && ref_mb)
604 mb->q_delta = ref_mb->q_delta;
606 if (band->inherit_mv) {
607 /* motion vector inheritance */
609 mb->mv_x = ivi_scale_mv(ref_mb->mv_x, mv_scale);
610 mb->mv_y = ivi_scale_mv(ref_mb->mv_y, mv_scale);
612 mb->mv_x = ref_mb->mv_x;
613 mb->mv_y = ref_mb->mv_y;
615 need_mc |= mb->mv_x || mb->mv_y; /* tracking non-zero motion vectors */
621 mb_offset += band->mb_size;
626 if (band->inherit_mv && need_mc) { /* apply motion compensation if there is at least one non-zero motion vector */
627 num_blocks = (band->mb_size != band->blk_size) ? 4 : 1; /* number of blocks per mb */
628 mc_no_delta_func = (band->blk_size == 8) ? ff_ivi_mc_8x8_no_delta
629 : ff_ivi_mc_4x4_no_delta;
631 for (mbn = 0, mb = tile->mbs; mbn < tile->num_MBs; mb++, mbn++) {
634 if (!band->is_halfpel) {
635 mc_type = 0; /* we have only fullpel vectors */
637 mc_type = ((mv_y & 1) << 1) | (mv_x & 1);
639 mv_y >>= 1; /* convert halfpel vectors into fullpel ones */
642 for (blk = 0; blk < num_blocks; blk++) {
643 /* adjust block position in the buffer according with its number */
644 offs = mb->buf_offs + band->blk_size * ((blk & 1) + !!(blk & 2) * band->pitch);
645 mc_no_delta_func(band->buf + offs,
646 band->ref_buf + offs + mv_y * band->pitch + mv_x,
647 band->pitch, mc_type);
651 /* copy data from the reference tile into the current one */
652 src = band->ref_buf + tile->ypos * band->pitch + tile->xpos;
653 dst = band->buf + tile->ypos * band->pitch + tile->xpos;
654 for (y = 0; y < tile->height; y++) {
655 memcpy(dst, src, tile->width*sizeof(band->buf[0]));
666 static uint16_t ivi_calc_band_checksum(IVIBandDesc *band)
669 int16_t *src, checksum;
674 for (y = 0; y < band->height; src += band->pitch, y++)
675 for (x = 0; x < band->width; x++)
683 * Convert and output the current plane.
684 * This conversion is done by adding back the bias value of 128
685 * (subtracted in the encoder) and clipping the result.
687 * @param[in] plane pointer to the descriptor of the plane being processed
688 * @param[out] dst pointer to the buffer receiving converted pixels
689 * @param[in] dst_pitch pitch for moving to the next y line
691 static void ivi_output_plane(IVIPlaneDesc *plane, uint8_t *dst, int dst_pitch)
694 const int16_t *src = plane->bands[0].buf;
695 uint32_t pitch = plane->bands[0].pitch;
700 for (y = 0; y < plane->height; y++) {
701 for (x = 0; x < plane->width; x++)
702 dst[x] = av_clip_uint8(src[x] + 128);
709 * Decode an Indeo 4 or 5 band.
711 * @param[in,out] ctx ptr to the decoder context
712 * @param[in,out] band ptr to the band descriptor
713 * @param[in] avctx ptr to the AVCodecContext
714 * @return result code: 0 = OK, -1 = error
716 static int decode_band(IVI45DecContext *ctx,
717 IVIBandDesc *band, AVCodecContext *avctx)
719 int result, i, t, idx1, idx2, pos;
722 band->buf = band->bufs[ctx->dst_buf];
724 av_log(avctx, AV_LOG_ERROR, "Band buffer points to no data!\n");
725 return AVERROR_INVALIDDATA;
727 band->ref_buf = band->bufs[ctx->ref_buf];
728 band->data_ptr = ctx->frame_data + (get_bits_count(&ctx->gb) >> 3);
730 result = ctx->decode_band_hdr(ctx, band, avctx);
732 av_log(avctx, AV_LOG_ERROR, "Error while decoding band header: %d\n",
737 if (band->is_empty) {
738 av_log(avctx, AV_LOG_ERROR, "Empty band encountered!\n");
739 return AVERROR_INVALIDDATA;
742 band->rv_map = &ctx->rvmap_tabs[band->rvmap_sel];
744 /* apply corrections to the selected rvmap table if present */
745 for (i = 0; i < band->num_corr; i++) {
746 idx1 = band->corr[i * 2];
747 idx2 = band->corr[i * 2 + 1];
748 FFSWAP(uint8_t, band->rv_map->runtab[idx1], band->rv_map->runtab[idx2]);
749 FFSWAP(int16_t, band->rv_map->valtab[idx1], band->rv_map->valtab[idx2]);
752 pos = get_bits_count(&ctx->gb);
754 for (t = 0; t < band->num_tiles; t++) {
755 tile = &band->tiles[t];
757 if (tile->mb_size != band->mb_size) {
758 av_log(avctx, AV_LOG_ERROR, "MB sizes mismatch: %d vs. %d\n",
759 band->mb_size, tile->mb_size);
760 return AVERROR_INVALIDDATA;
762 tile->is_empty = get_bits1(&ctx->gb);
763 if (tile->is_empty) {
764 result = ivi_process_empty_tile(avctx, band, tile,
765 (ctx->planes[0].bands[0].mb_size >> 3) - (band->mb_size >> 3));
768 av_dlog(avctx, "Empty tile encountered!\n");
770 tile->data_size = ivi_dec_tile_data_size(&ctx->gb);
771 if (!tile->data_size) {
772 av_log(avctx, AV_LOG_ERROR, "Tile data size is zero!\n");
773 return AVERROR_INVALIDDATA;
776 result = ctx->decode_mb_info(ctx, band, tile, avctx);
780 result = ivi_decode_blocks(&ctx->gb, band, tile, avctx);
781 if (result < 0 || ((get_bits_count(&ctx->gb) - pos) >> 3) != tile->data_size) {
782 av_log(avctx, AV_LOG_ERROR, "Corrupted tile data encountered!\n");
786 pos += tile->data_size << 3; // skip to next tile
790 /* restore the selected rvmap table by applying its corrections in reverse order */
791 for (i = band->num_corr-1; i >= 0; i--) {
792 idx1 = band->corr[i*2];
793 idx2 = band->corr[i*2+1];
794 FFSWAP(uint8_t, band->rv_map->runtab[idx1], band->rv_map->runtab[idx2]);
795 FFSWAP(int16_t, band->rv_map->valtab[idx1], band->rv_map->valtab[idx2]);
799 if (band->checksum_present) {
800 uint16_t chksum = ivi_calc_band_checksum(band);
801 if (chksum != band->checksum) {
802 av_log(avctx, AV_LOG_ERROR,
803 "Band checksum mismatch! Plane %d, band %d, received: %x, calculated: %x\n",
804 band->plane, band->band_num, band->checksum, chksum);
809 align_get_bits(&ctx->gb);
814 int ff_ivi_decode_frame(AVCodecContext *avctx, void *data, int *got_frame,
817 IVI45DecContext *ctx = avctx->priv_data;
818 const uint8_t *buf = avpkt->data;
819 AVFrame *frame = data;
820 int buf_size = avpkt->size;
823 init_get_bits(&ctx->gb, buf, buf_size * 8);
824 ctx->frame_data = buf;
825 ctx->frame_size = buf_size;
827 result = ctx->decode_pic_hdr(ctx, avctx);
829 av_log(avctx, AV_LOG_ERROR,
830 "Error while decoding picture header: %d\n", result);
833 if (ctx->gop_invalid)
834 return AVERROR_INVALIDDATA;
836 if (ctx->gop_flags & IVI5_IS_PROTECTED) {
837 av_log(avctx, AV_LOG_ERROR, "Password-protected clip!\n");
841 ctx->switch_buffers(ctx);
845 if (ctx->is_nonnull_frame(ctx)) {
846 for (p = 0; p < 3; p++) {
847 for (b = 0; b < ctx->planes[p].num_bands; b++) {
848 result = decode_band(ctx, &ctx->planes[p].bands[b], avctx);
850 av_log(avctx, AV_LOG_ERROR,
851 "Error while decoding band: %d, plane: %d\n", b, p);
858 //STOP_TIMER("decode_planes"); }
860 /* If the bidirectional mode is enabled, next I and the following P frame will */
861 /* be sent together. Unfortunately the approach below seems to be the only way */
862 /* to handle the B-frames mode. That's exactly the same Intel decoders do. */
863 if (avctx->codec_id == AV_CODEC_ID_INDEO4 && ctx->frame_type == 0/*FRAMETYPE_INTRA*/) {
864 while (get_bits(&ctx->gb, 8)); // skip version string
865 skip_bits_long(&ctx->gb, 64); // skip padding, TODO: implement correct 8-bytes alignment
866 if (get_bits_left(&ctx->gb) > 18 && show_bits(&ctx->gb, 18) == 0x3FFF8)
867 av_log(avctx, AV_LOG_ERROR, "Buffer contains IP frames!\n");
870 avcodec_set_dimensions(avctx, ctx->planes[0].width, ctx->planes[0].height);
871 if ((result = ff_get_buffer(avctx, frame, 0)) < 0) {
872 av_log(avctx, AV_LOG_ERROR, "get_buffer() failed\n");
876 if (ctx->is_scalable) {
877 if (avctx->codec_id == AV_CODEC_ID_INDEO4)
878 ff_ivi_recompose_haar(&ctx->planes[0], frame->data[0], frame->linesize[0]);
880 ff_ivi_recompose53 (&ctx->planes[0], frame->data[0], frame->linesize[0]);
882 ivi_output_plane(&ctx->planes[0], frame->data[0], frame->linesize[0]);
885 ivi_output_plane(&ctx->planes[2], frame->data[1], frame->linesize[1]);
886 ivi_output_plane(&ctx->planes[1], frame->data[2], frame->linesize[2]);
894 * Close Indeo5 decoder and clean up its context.
896 av_cold int ff_ivi_decode_close(AVCodecContext *avctx)
898 IVI45DecContext *ctx = avctx->priv_data;
900 ivi_free_buffers(&ctx->planes[0]);
902 if (ctx->mb_vlc.cust_tab.table)
903 ff_free_vlc(&ctx->mb_vlc.cust_tab);
905 #if IVI4_STREAM_ANALYSER
906 if (avctx->codec_id == AV_CODEC_ID_INDEO4) {
907 if (ctx->is_scalable)
908 av_log(avctx, AV_LOG_ERROR, "This video uses scalability mode!\n");
909 if (ctx->uses_tiling)
910 av_log(avctx, AV_LOG_ERROR, "This video uses local decoding!\n");
911 if (ctx->has_b_frames)
912 av_log(avctx, AV_LOG_ERROR, "This video contains B-frames!\n");
914 av_log(avctx, AV_LOG_ERROR, "Transparency mode is enabled!\n");
916 av_log(avctx, AV_LOG_ERROR, "This video uses Haar transform!\n");
917 if (ctx->uses_fullpel)
918 av_log(avctx, AV_LOG_ERROR, "This video uses fullpel motion vectors!\n");
927 * These are 2x8 predefined Huffman codebooks for coding macroblock/block
928 * signals. They are specified using "huffman descriptors" in order to
929 * avoid huge static tables. The decoding tables will be generated at
930 * startup from these descriptors.
932 const IVIHuffDesc ff_ivi_mb_huff_desc[8] = {
933 {8, {0, 4, 5, 4, 4, 4, 6, 6}},
934 {12, {0, 2, 2, 3, 3, 3, 3, 5, 3, 2, 2, 2}},
935 {12, {0, 2, 3, 4, 3, 3, 3, 3, 4, 3, 2, 2}},
936 {12, {0, 3, 4, 4, 3, 3, 3, 3, 3, 2, 2, 2}},
937 {13, {0, 4, 4, 3, 3, 3, 3, 2, 3, 3, 2, 1, 1}},
938 {9, {0, 4, 4, 4, 4, 3, 3, 3, 2}},
939 {10, {0, 4, 4, 4, 4, 3, 3, 2, 2, 2}},
940 {12, {0, 4, 4, 4, 3, 3, 2, 3, 2, 2, 2, 2}}
943 const IVIHuffDesc ff_ivi_blk_huff_desc[8] = {
944 {10, {1, 2, 3, 4, 4, 7, 5, 5, 4, 1}},
945 {11, {2, 3, 4, 4, 4, 7, 5, 4, 3, 3, 2}},
946 {12, {2, 4, 5, 5, 5, 5, 6, 4, 4, 3, 1, 1}},
947 {13, {3, 3, 4, 4, 5, 6, 6, 4, 4, 3, 2, 1, 1}},
948 {11, {3, 4, 4, 5, 5, 5, 6, 5, 4, 2, 2}},
949 {13, {3, 4, 5, 5, 5, 5, 6, 4, 3, 3, 2, 1, 1}},
950 {13, {3, 4, 5, 5, 5, 6, 5, 4, 3, 3, 2, 1, 1}},
951 {9, {3, 4, 4, 5, 5, 5, 6, 5, 5}}
956 * Scan patterns shared between indeo4 and indeo5
958 const uint8_t ff_ivi_vertical_scan_8x8[64] = {
959 0, 8, 16, 24, 32, 40, 48, 56,
960 1, 9, 17, 25, 33, 41, 49, 57,
961 2, 10, 18, 26, 34, 42, 50, 58,
962 3, 11, 19, 27, 35, 43, 51, 59,
963 4, 12, 20, 28, 36, 44, 52, 60,
964 5, 13, 21, 29, 37, 45, 53, 61,
965 6, 14, 22, 30, 38, 46, 54, 62,
966 7, 15, 23, 31, 39, 47, 55, 63
969 const uint8_t ff_ivi_horizontal_scan_8x8[64] = {
970 0, 1, 2, 3, 4, 5, 6, 7,
971 8, 9, 10, 11, 12, 13, 14, 15,
972 16, 17, 18, 19, 20, 21, 22, 23,
973 24, 25, 26, 27, 28, 29, 30, 31,
974 32, 33, 34, 35, 36, 37, 38, 39,
975 40, 41, 42, 43, 44, 45, 46, 47,
976 48, 49, 50, 51, 52, 53, 54, 55,
977 56, 57, 58, 59, 60, 61, 62, 63
980 const uint8_t ff_ivi_direct_scan_4x4[16] = {
981 0, 1, 4, 8, 5, 2, 3, 6, 9, 12, 13, 10, 7, 11, 14, 15
986 * Run-value (RLE) tables.
988 const RVMapDesc ff_ivi_rvmap_tabs[9] = {
993 {1, 1, 0, 1, 1, 0, 1, 1, 2, 2, 1, 1, 1, 1, 3, 3,
994 1, 1, 2, 2, 1, 1, 4, 4, 1, 1, 1, 1, 2, 2, 5, 5,
995 1, 1, 3, 3, 1, 1, 6, 6, 1, 2, 1, 2, 7, 7, 1, 1,
996 8, 8, 1, 1, 4, 2, 1, 4, 2, 1, 3, 3, 1, 1, 1, 9,
997 9, 1, 2, 1, 2, 1, 5, 5, 1, 1, 10, 10, 1, 1, 3, 3,
998 2, 2, 1, 1, 11, 11, 6, 4, 4, 1, 6, 1, 2, 1, 2, 12,
999 8, 1, 12, 7, 8, 7, 1, 16, 1, 16, 1, 3, 3, 13, 1, 13,
1000 2, 2, 1, 15, 1, 5, 14, 15, 1, 5, 14, 1, 17, 8, 17, 8,
1001 1, 4, 4, 2, 2, 1, 25, 25, 24, 24, 1, 3, 1, 3, 1, 8,
1002 6, 7, 6, 1, 18, 8, 18, 1, 7, 23, 2, 2, 23, 1, 1, 21,
1003 22, 9, 9, 22, 19, 1, 21, 5, 19, 5, 1, 33, 20, 33, 20, 8,
1004 4, 4, 1, 32, 2, 2, 8, 3, 32, 26, 3, 1, 7, 7, 26, 6,
1005 1, 6, 1, 1, 16, 1, 10, 1, 10, 2, 16, 29, 28, 2, 29, 28,
1006 1, 27, 5, 8, 5, 27, 1, 8, 3, 7, 3, 31, 41, 31, 1, 41,
1007 6, 1, 6, 7, 4, 4, 1, 1, 2, 1, 2, 11, 34, 30, 11, 1,
1008 30, 15, 15, 34, 36, 40, 36, 40, 35, 35, 37, 37, 39, 39, 38, 38},
1011 { 1, -1, 0, 2, -2, 0, 3, -3, 1, -1, 4, -4, 5, -5, 1, -1,
1012 6, -6, 2, -2, 7, -7, 1, -1, 8, -8, 9, -9, 3, -3, 1, -1,
1013 10, -10, 2, -2, 11, -11, 1, -1, 12, 4, -12, -4, 1, -1, 13, -13,
1014 1, -1, 14, -14, 2, 5, 15, -2, -5, -15, -3, 3, 16, -16, 17, 1,
1015 -1, -17, 6, 18, -6, -18, 2, -2, 19, -19, 1, -1, 20, -20, 4, -4,
1016 7, -7, 21, -21, 1, -1, 2, 3, -3, 22, -2, -22, 8, 23, -8, 1,
1017 2, -23, -1, 2, -2, -2, 24, 1, -24, -1, 25, 5, -5, 1, -25, -1,
1018 9, -9, 26, 1, -26, 3, 1, -1, 27, -3, -1, -27, 1, 3, -1, -3,
1019 28, -4, 4, 10, -10, -28, 1, -1, 1, -1, 29, 6, -29, -6, 30, -4,
1020 3, 3, -3, -30, 1, 4, -1, 31, -3, 1, 11, -11, -1, -31, 32, -1,
1021 -1, 2, -2, 1, 1, -32, 1, 4, -1, -4, 33, -1, 1, 1, -1, 5,
1022 5, -5, -33, -1, -12, 12, -5, -7, 1, 1, 7, 34, 4, -4, -1, 4,
1023 -34, -4, 35, 36, -2, -35, -2, -36, 2, 13, 2, -1, 1, -13, 1, -1,
1024 37, 1, -5, 6, 5, -1, 38, -6, -8, 5, 8, -1, 1, 1, -37, -1,
1025 5, 39, -5, -5, 6, -6, -38, -39, -14, 40, 14, 2, 1, 1, -2, -40,
1026 -1, -2, 2, -1, -1, -1, 1, 1, 1, -1, 1, -1, 1, -1, 1, -1}
1032 {0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 8, 6, 8, 7,
1033 7, 9, 9, 10, 10, 11, 11, 1, 12, 1, 12, 13, 13, 16, 14, 16,
1034 14, 15, 15, 17, 17, 18, 0, 18, 19, 20, 21, 19, 22, 21, 20, 22,
1035 25, 24, 2, 25, 24, 23, 23, 2, 26, 28, 26, 28, 29, 27, 29, 27,
1036 33, 33, 1, 32, 1, 3, 32, 30, 36, 3, 36, 30, 31, 31, 35, 34,
1037 37, 41, 34, 35, 37, 4, 41, 4, 49, 8, 8, 49, 40, 38, 5, 38,
1038 40, 39, 5, 39, 42, 43, 42, 7, 57, 6, 43, 44, 6, 50, 7, 44,
1039 57, 48, 50, 48, 45, 45, 46, 47, 51, 46, 47, 58, 1, 51, 58, 1,
1040 52, 59, 53, 9, 52, 55, 55, 59, 53, 56, 54, 56, 54, 9, 64, 64,
1041 60, 63, 60, 63, 61, 62, 61, 62, 2, 10, 2, 10, 11, 1, 11, 13,
1042 12, 1, 12, 13, 16, 16, 8, 8, 14, 3, 3, 15, 14, 15, 4, 4,
1043 1, 17, 17, 5, 1, 7, 7, 5, 6, 1, 2, 2, 6, 22, 1, 25,
1044 21, 22, 8, 24, 1, 21, 25, 24, 8, 18, 18, 23, 9, 20, 23, 33,
1045 29, 33, 20, 1, 19, 1, 29, 36, 9, 36, 19, 41, 28, 57, 32, 3,
1046 28, 3, 1, 27, 49, 49, 1, 32, 26, 26, 2, 4, 4, 7, 57, 41,
1047 2, 7, 10, 5, 37, 16, 10, 27, 8, 8, 13, 16, 37, 13, 1, 5},
1050 {0, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, 1, -1, -1, 1,
1051 -1, 1, -1, 1, -1, 1, -1, 2, 1, -2, -1, 1, -1, 1, 1, -1,
1052 -1, 1, -1, 1, -1, 1, 0, -1, 1, 1, 1, -1, 1, -1, -1, -1,
1053 1, 1, 2, -1, -1, 1, -1, -2, 1, 1, -1, -1, 1, 1, -1, -1,
1054 1, -1, 3, 1, -3, 2, -1, 1, 1, -2, -1, -1, -1, 1, 1, 1,
1055 1, 1, -1, -1, -1, 2, -1, -2, 1, 2, -2, -1, 1, 1, 2, -1,
1056 -1, 1, -2, -1, 1, 1, -1, 2, 1, 2, -1, 1, -2, -1, -2, -1,
1057 -1, 1, 1, -1, 1, -1, 1, 1, 1, -1, -1, 1, 4, -1, -1, -4,
1058 1, 1, 1, 2, -1, -1, 1, -1, -1, 1, -1, -1, 1, -2, 1, -1,
1059 1, 1, -1, -1, 1, 1, -1, -1, 3, 2, -3, -2, 2, 5, -2, 2,
1060 2, -5, -2, -2, -2, 2, -3, 3, 2, 3, -3, 2, -2, -2, 3, -3,
1061 6, 2, -2, 3, -6, 3, -3, -3, 3, 7, -4, 4, -3, 2, -7, 2,
1062 2, -2, -4, 2, 8, -2, -2, -2, 4, 2, -2, 2, 3, 2, -2, -2,
1063 2, 2, -2, -8, -2, 9, -2, 2, -3, -2, 2, -2, 2, 2, 2, 4,
1064 -2, -4, 10, 2, 2, -2, -9, -2, 2, -2, 5, 4, -4, 4, -2, 2,
1065 -5, -4, -3, 4, 2, -3, 3, -2, -5, 5, 3, 3, -2, -3, -10, -4}
1071 {1, 1, 0, 2, 2, 1, 1, 3, 3, 4, 4, 0, 1, 1, 5, 5,
1072 2, 2, 6, 6, 7, 7, 1, 8, 1, 8, 3, 3, 9, 9, 1, 2,
1073 2, 1, 4, 10, 4, 10, 11, 11, 1, 5, 12, 12, 1, 5, 13, 13,
1074 3, 3, 6, 6, 2, 2, 14, 14, 16, 16, 15, 7, 15, 8, 8, 7,
1075 1, 1, 17, 17, 4, 4, 1, 1, 18, 18, 2, 2, 5, 5, 25, 3,
1076 9, 3, 25, 9, 19, 24, 19, 24, 1, 21, 20, 1, 21, 22, 20, 22,
1077 23, 23, 8, 6, 33, 6, 8, 33, 7, 7, 26, 26, 1, 32, 1, 32,
1078 28, 4, 28, 10, 29, 27, 27, 10, 41, 4, 29, 2, 2, 41, 36, 31,
1079 49, 31, 34, 30, 34, 36, 30, 35, 1, 49, 11, 5, 35, 11, 1, 3,
1080 3, 5, 37, 37, 8, 40, 8, 40, 12, 12, 42, 42, 1, 38, 16, 57,
1081 1, 6, 16, 39, 38, 6, 7, 7, 13, 13, 39, 43, 2, 43, 57, 2,
1082 50, 9, 44, 9, 50, 4, 15, 48, 44, 4, 1, 15, 48, 14, 14, 1,
1083 45, 45, 8, 3, 5, 8, 51, 47, 3, 46, 46, 47, 5, 51, 1, 17,
1084 17, 58, 1, 58, 2, 52, 52, 2, 53, 7, 59, 6, 6, 56, 53, 55,
1085 7, 55, 1, 54, 59, 56, 54, 10, 1, 10, 4, 60, 1, 60, 8, 4,
1086 8, 64, 64, 61, 1, 63, 3, 63, 62, 61, 5, 11, 5, 3, 11, 62},
1089 { 1, -1, 0, 1, -1, 2, -2, 1, -1, 1, -1, 0, 3, -3, 1, -1,
1090 2, -2, 1, -1, 1, -1, 4, 1, -4, -1, 2, -2, 1, -1, 5, 3,
1091 -3, -5, 2, 1, -2, -1, 1, -1, 6, 2, 1, -1, -6, -2, 1, -1,
1092 3, -3, 2, -2, 4, -4, 1, -1, 1, -1, 1, 2, -1, 2, -2, -2,
1093 7, -7, 1, -1, 3, -3, 8, -8, 1, -1, 5, -5, 3, -3, 1, 4,
1094 2, -4, -1, -2, 1, 1, -1, -1, 9, 1, 1, -9, -1, 1, -1, -1,
1095 1, -1, 3, -3, 1, 3, -3, -1, 3, -3, 1, -1, 10, 1, -10, -1,
1096 1, 4, -1, 2, 1, -1, 1, -2, 1, -4, -1, 6, -6, -1, 1, 1,
1097 1, -1, 1, 1, -1, -1, -1, 1, 11, -1, -2, 4, -1, 2, -11, 5,
1098 -5, -4, -1, 1, 4, 1, -4, -1, -2, 2, 1, -1, 12, 1, -2, 1,
1099 -12, 4, 2, 1, -1, -4, 4, -4, 2, -2, -1, 1, 7, -1, -1, -7,
1100 -1, -3, 1, 3, 1, 5, 2, 1, -1, -5, 13, -2, -1, 2, -2, -13,
1101 1, -1, 5, 6, 5, -5, 1, 1, -6, 1, -1, -1, -5, -1, 14, 2,
1102 -2, 1, -14, -1, 8, 1, -1, -8, 1, 5, 1, 5, -5, 1, -1, 1,
1103 -5, -1, 15, 1, -1, -1, -1, 3, -15, -3, 6, 1, 16, -1, 6, -6,
1104 -6, 1, -1, 1, -16, 1, 7, -1, 1, -1, -6, -3, 6, -7, 3, -1}
1110 {0, 1, 1, 2, 2, 3, 3, 4, 4, 1, 1, 5, 5, 6, 6, 7,
1111 7, 8, 8, 9, 9, 2, 2, 10, 10, 1, 1, 11, 11, 12, 12, 3,
1112 3, 13, 13, 0, 14, 14, 16, 15, 16, 15, 4, 4, 17, 1, 17, 1,
1113 5, 5, 18, 18, 2, 2, 6, 6, 8, 19, 7, 8, 7, 19, 20, 20,
1114 21, 21, 22, 24, 22, 24, 23, 23, 1, 1, 25, 25, 3, 3, 26, 26,
1115 9, 9, 27, 27, 28, 28, 33, 29, 4, 33, 29, 1, 4, 1, 32, 32,
1116 2, 2, 31, 10, 30, 10, 30, 31, 34, 34, 5, 5, 36, 36, 35, 41,
1117 35, 11, 41, 11, 37, 1, 8, 8, 37, 6, 1, 6, 40, 7, 7, 40,
1118 12, 38, 12, 39, 39, 38, 49, 13, 49, 13, 3, 42, 3, 42, 16, 16,
1119 43, 43, 14, 14, 1, 1, 44, 15, 44, 15, 2, 2, 57, 48, 50, 48,
1120 57, 50, 4, 45, 45, 4, 46, 47, 47, 46, 1, 51, 1, 17, 17, 51,
1121 8, 9, 9, 5, 58, 8, 58, 5, 52, 52, 55, 56, 53, 56, 55, 59,
1122 59, 53, 54, 1, 6, 54, 7, 7, 6, 1, 2, 3, 2, 3, 64, 60,
1123 60, 10, 10, 64, 61, 62, 61, 63, 1, 63, 62, 1, 18, 24, 18, 4,
1124 25, 4, 8, 21, 21, 1, 24, 22, 25, 22, 8, 11, 19, 11, 23, 1,
1125 20, 23, 19, 20, 5, 12, 5, 1, 16, 2, 12, 13, 2, 13, 1, 16},
1128 { 0, 1, -1, 1, -1, 1, -1, 1, -1, 2, -2, 1, -1, 1, -1, 1,
1129 -1, 1, -1, 1, -1, 2, -2, 1, -1, 3, -3, 1, -1, 1, -1, 2,
1130 -2, 1, -1, 0, 1, -1, 1, 1, -1, -1, 2, -2, 1, 4, -1, -4,
1131 2, -2, 1, -1, -3, 3, 2, -2, 2, 1, 2, -2, -2, -1, 1, -1,
1132 1, -1, 1, 1, -1, -1, 1, -1, 5, -5, 1, -1, 3, -3, 1, -1,
1133 2, -2, 1, -1, 1, -1, 1, 1, 3, -1, -1, 6, -3, -6, -1, 1,
1134 4, -4, 1, 2, 1, -2, -1, -1, 1, -1, 3, -3, 1, -1, 1, 1,
1135 -1, 2, -1, -2, 1, 7, -3, 3, -1, 3, -7, -3, 1, -3, 3, -1,
1136 2, 1, -2, 1, -1, -1, 1, 2, -1, -2, -4, -1, 4, 1, 2, -2,
1137 1, -1, -2, 2, 8, -8, -1, 2, 1, -2, -5, 5, 1, -1, -1, 1,
1138 -1, 1, 4, -1, 1, -4, -1, -1, 1, 1, 9, 1, -9, 2, -2, -1,
1139 -4, 3, -3, -4, -1, 4, 1, 4, 1, -1, 1, -1, 1, 1, -1, 1,
1140 -1, -1, -1, 10, 4, 1, 4, -4, -4, -10, 6, 5, -6, -5, 1, -1,
1141 1, 3, -3, -1, 1, -1, -1, -1, 11, 1, 1, -11, -2, -2, 2, 5,
1142 -2, -5, -5, 2, -2, 12, 2, -2, 2, 2, 5, -3, -2, 3, -2, -12,
1143 -2, 2, 2, 2, -5, 3, 5, 13, -3, 7, -3, -3, -7, 3, -13, 3}
1149 {0, 1, 1, 1, 2, 2, 1, 3, 3, 1, 1, 1, 4, 4, 1, 5,
1150 2, 1, 5, 2, 1, 1, 6, 6, 1, 1, 1, 1, 1, 7, 3, 1,
1151 2, 3, 0, 1, 2, 7, 1, 1, 1, 8, 1, 1, 8, 1, 1, 1,
1152 9, 1, 9, 1, 2, 1, 1, 2, 1, 1, 10, 4, 1, 10, 1, 4,
1153 1, 1, 1, 1, 1, 3, 1, 1, 1, 3, 2, 1, 5, 1, 1, 1,
1154 2, 5, 1, 11, 1, 11, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1155 2, 1, 6, 1, 6, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 12,
1156 3, 1, 12, 1, 1, 1, 2, 1, 1, 3, 1, 1, 1, 1, 1, 1,
1157 4, 1, 1, 1, 2, 1, 1, 4, 1, 1, 1, 1, 1, 1, 2, 1,
1158 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 2, 1, 1, 5,
1159 1, 1, 1, 1, 1, 7, 1, 7, 1, 1, 2, 3, 1, 1, 1, 1,
1160 5, 1, 1, 1, 1, 1, 1, 2, 13, 1, 1, 1, 1, 1, 1, 1,
1161 1, 1, 1, 1, 1, 1, 1, 1, 13, 2, 1, 1, 4, 1, 1, 1,
1162 3, 1, 6, 1, 1, 1, 14, 1, 1, 1, 1, 1, 14, 6, 1, 1,
1163 1, 1, 15, 2, 4, 1, 2, 3, 15, 1, 1, 1, 8, 1, 1, 8,
1164 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1},
1167 { 0, 1, -1, 2, 1, -1, -2, 1, -1, 3, -3, 4, 1, -1, -4, 1,
1168 2, 5, -1, -2, -5, 6, 1, -1, -6, 7, -7, 8, -8, 1, 2, 9,
1169 3, -2, 0, -9, -3, -1, 10, -10, 11, 1, -11, 12, -1, -12, 13, -13,
1170 1, 14, -1, -14, 4, 15, -15, -4, 16, -16, 1, 2, 17, -1, -17, -2,
1171 18, -18, 19, -19, 20, 3, -20, 21, -21, -3, 5, 22, 2, -22, -23, 23,
1172 -5, -2, 24, 1, -24, -1, 25, -25, 26, -26, -27, 27, 28, 29, -28, -29,
1173 6, 30, 2, -31, -2, -30, 31, -6, -32, 32, 33, -33, 34, -35, -34, 1,
1174 4, -36, -1, 35, 37, 36, 7, -37, 38, -4, -38, 39, 41, 40, -40, -39,
1175 3, 42, -43, -41, -7, -42, 43, -3, 44, -44, 45, -45, 46, 47, 8, -47,
1176 -48, -46, 50, -50, 48, 49, 51, -49, 52, -52, 5, -51, -8, -53, 53, 3,
1177 -56, 56, 55, 54, -54, 2, 60, -2, -55, 58, 9, -5, 59, 57, -57, -63,
1178 -3, -58, -60, -61, 61, -59, -62, -9, 1, 64, 62, 69, -64, 63, 65, -67,
1179 -68, 66, -65, 68, -66, -69, 67, -70, -1, 10, 71, -71, 4, 73, 72, 70,
1180 6, -76, -3, 74, -78, -74, 1, 78, 80, -72, -75, 76, -1, 3, -73, 79,
1181 75, 77, 1, 11, -4, -79, -10, -6, -1, -77, -83, -80, 2, 81, -84, -2,
1182 83, -81, 82, -82, 84, -87, -86, 85, -11, -85, 86, -89, 87, -88, 88, 89}
1188 {1, 1, 0, 2, 1, 2, 1, 3, 3, 1, 1, 4, 4, 2, 2, 1,
1189 1, 5, 5, 6, 1, 6, 1, 7, 7, 3, 3, 2, 8, 2, 8, 1,
1190 1, 0, 9, 9, 1, 1, 10, 4, 10, 4, 11, 11, 2, 1, 2, 1,
1191 12, 12, 3, 3, 1, 1, 13, 5, 5, 13, 14, 1, 1, 14, 2, 2,
1192 6, 6, 15, 1, 1, 15, 16, 4, 7, 16, 4, 7, 1, 1, 3, 3,
1193 8, 8, 2, 2, 1, 1, 17, 17, 1, 1, 18, 18, 5, 5, 2, 2,
1194 1, 1, 9, 19, 9, 19, 20, 3, 3, 20, 1, 10, 21, 1, 10, 4,
1195 4, 21, 22, 6, 6, 22, 1, 1, 23, 24, 2, 2, 23, 24, 11, 1,
1196 1, 11, 7, 25, 7, 1, 1, 25, 8, 8, 3, 26, 3, 1, 12, 2,
1197 2, 26, 1, 12, 5, 5, 27, 4, 1, 4, 1, 27, 28, 1, 28, 13,
1198 1, 13, 2, 29, 2, 1, 32, 6, 1, 30, 14, 29, 14, 6, 3, 31,
1199 3, 1, 30, 1, 32, 31, 33, 9, 33, 1, 1, 7, 9, 7, 2, 2,
1200 1, 1, 4, 36, 34, 4, 5, 10, 10, 5, 34, 1, 1, 35, 8, 8,
1201 36, 3, 35, 1, 15, 3, 2, 1, 16, 15, 16, 2, 37, 1, 37, 1,
1202 1, 1, 6, 6, 38, 1, 38, 11, 1, 39, 39, 40, 11, 2, 41, 4,
1203 40, 1, 2, 4, 1, 1, 1, 41, 3, 1, 3, 1, 5, 7, 5, 7},
1206 { 1, -1, 0, 1, 2, -1, -2, 1, -1, 3, -3, 1, -1, 2, -2, 4,
1207 -4, 1, -1, 1, 5, -1, -5, 1, -1, 2, -2, 3, 1, -3, -1, 6,
1208 -6, 0, 1, -1, 7, -7, 1, 2, -1, -2, 1, -1, 4, 8, -4, -8,
1209 1, -1, 3, -3, 9, -9, 1, 2, -2, -1, 1, 10, -10, -1, 5, -5,
1210 2, -2, 1, 11, -11, -1, 1, 3, 2, -1, -3, -2, 12, -12, 4, -4,
1211 2, -2, -6, 6, 13, -13, 1, -1, 14, -14, 1, -1, 3, -3, 7, -7,
1212 15, -15, 2, 1, -2, -1, 1, 5, -5, -1, -16, 2, 1, 16, -2, 4,
1213 -4, -1, 1, 3, -3, -1, 17, -17, 1, 1, -8, 8, -1, -1, 2, 18,
1214 -18, -2, 3, 1, -3, 19, -19, -1, 3, -3, 6, 1, -6, 20, 2, 9,
1215 -9, -1, -20, -2, 4, -4, 1, -5, 21, 5, -21, -1, 1, -22, -1, 2,
1216 22, -2, 10, 1, -10, 23, 1, 4, -23, 1, 2, -1, -2, -4, -7, 1,
1217 7, -24, -1, 24, -1, -1, 1, 3, -1, -25, 25, 4, -3, -4, 11, -11,
1218 26, -26, 6, 1, 1, -6, -5, -3, 3, 5, -1, -27, 27, 1, 4, -4,
1219 -1, -8, -1, 28, 2, 8, -12, -28, -2, -2, 2, 12, -1, 29, 1, -29,
1220 30, -30, 5, -5, 1, -31, -1, 3, 31, -1, 1, 1, -3, -13, 1, -7,
1221 -1, -32, 13, 7, 32, 33, -33, -1, -9, -34, 9, 34, -6, 5, 6, -5}
1227 {1, 1, 0, 1, 1, 2, 2, 1, 1, 3, 3, 1, 1, 0, 2, 2,
1228 4, 1, 4, 1, 1, 1, 5, 5, 1, 1, 6, 6, 2, 2, 1, 1,
1229 3, 3, 7, 7, 1, 1, 8, 8, 1, 1, 2, 2, 1, 9, 1, 9,
1230 4, 4, 10, 1, 1, 10, 1, 1, 11, 11, 3, 3, 1, 2, 1, 2,
1231 1, 1, 12, 12, 5, 5, 1, 1, 13, 1, 1, 13, 2, 2, 1, 1,
1232 6, 6, 1, 1, 4, 14, 4, 14, 3, 1, 3, 1, 1, 1, 15, 7,
1233 15, 2, 2, 7, 1, 1, 1, 8, 1, 8, 16, 16, 1, 1, 1, 1,
1234 2, 1, 1, 2, 1, 1, 3, 5, 5, 3, 4, 1, 1, 4, 1, 1,
1235 17, 17, 9, 1, 1, 9, 2, 2, 1, 1, 10, 10, 1, 6, 1, 1,
1236 6, 18, 1, 1, 18, 1, 1, 1, 2, 2, 3, 1, 3, 1, 1, 1,
1237 4, 1, 19, 1, 19, 7, 1, 1, 20, 1, 4, 20, 1, 7, 11, 2,
1238 1, 11, 21, 2, 8, 5, 1, 8, 1, 5, 21, 1, 1, 1, 22, 1,
1239 1, 22, 1, 1, 3, 3, 1, 23, 2, 12, 24, 1, 1, 2, 1, 1,
1240 12, 23, 1, 1, 24, 1, 1, 1, 4, 1, 1, 1, 2, 1, 6, 6,
1241 4, 2, 1, 1, 1, 1, 1, 1, 1, 14, 13, 3, 1, 25, 9, 25,
1242 14, 1, 9, 3, 13, 1, 1, 1, 1, 1, 10, 1, 1, 2, 10, 2},
1245 {-20, -1, 0, 2, -2, 1, -1, 3, -3, 1, -1, 4, -4, 0, 2, -2,
1246 1, 5, -1, -5, 6, -6, 1, -1, 7, -7, 1, -1, 3, -3, 8, -8,
1247 2, -2, 1, -1, 9, -9, 1, -1, 10, -10, 4, -4, 11, 1, -11, -1,
1248 2, -2, 1, 12, -12, -1, 13, -13, 1, -1, 3, -3, 14, 5, -14, -5,
1249 -15, 15, -1, 1, 2, -2, 16, -16, 1, 17, -17, -1, 6, -6, 18, -18,
1250 2, -2, -19, 19, -3, 1, 3, -1, 4, 20, -4, 1, -21, 21, 1, 2,
1251 -1, -7, 7, -2, 22, -22, 23, 2, -23, -2, 1, -1, -24, 24, -25, 25,
1252 -8, -26, 26, 8, -27, 27, 5, 3, -3, -5, -4, 28, -28, 4, 29, -29,
1253 1, -1, -2, -30, 30, 2, 9, -9, -31, 31, 2, -2, -32, 3, 32, -33,
1254 -3, 1, 33, -34, -1, 34, -35, 35, -10, 10, -6, 36, 6, -36, 37, -37,
1255 -5, 38, 1, -38, -1, 3, 39, -39, -1, 40, 5, 1, -40, -3, 2, -11,
1256 -41, -2, 1, 11, -3, -4, 41, 3, 42, 4, -1, -43, -42, 43, 1, -44,
1257 45, -1, 44, -45, -7, 7, -46, 1, -12, 2, 1, -47, 46, 12, 47, 48,
1258 -2, -1, -48, 49, -1, -50, -49, 50, -6, -51, 51, 52, -13, 53, -4, 4,
1259 6, 13, -53, -52, -54, 55, 54, -55, -56, -2, 2, -8, 56, 1, -3, -1,
1260 2, 58, 3, 8, -2, 57, -58, -60, -59, -57, -3, 60, 59, -14, 3, 14}
1266 {1, 1, 0, 2, 2, 1, 1, 3, 3, 4, 4, 5, 5, 1, 1, 6,
1267 6, 2, 2, 7, 7, 8, 8, 1, 1, 3, 3, 9, 9, 10, 10, 1,
1268 1, 2, 2, 4, 4, 11, 0, 11, 12, 12, 13, 13, 1, 1, 5, 5,
1269 14, 14, 15, 16, 15, 16, 3, 3, 1, 6, 1, 6, 2, 2, 7, 7,
1270 8, 8, 17, 17, 1, 1, 4, 4, 18, 18, 2, 2, 1, 19, 1, 20,
1271 19, 20, 21, 21, 3, 3, 22, 22, 5, 5, 24, 1, 1, 23, 9, 23,
1272 24, 9, 2, 2, 10, 1, 1, 10, 6, 6, 25, 4, 4, 25, 7, 7,
1273 26, 8, 1, 8, 3, 1, 26, 3, 11, 11, 27, 27, 2, 28, 1, 2,
1274 28, 1, 12, 12, 5, 5, 29, 13, 13, 29, 32, 1, 1, 33, 31, 30,
1275 32, 4, 30, 33, 4, 31, 3, 14, 1, 1, 3, 34, 34, 2, 2, 14,
1276 6, 6, 35, 36, 35, 36, 1, 15, 1, 16, 16, 15, 7, 9, 7, 9,
1277 37, 8, 8, 37, 1, 1, 39, 2, 38, 39, 2, 40, 5, 38, 40, 5,
1278 3, 3, 4, 4, 10, 10, 1, 1, 1, 1, 41, 2, 41, 2, 6, 6,
1279 1, 1, 11, 42, 11, 43, 3, 42, 3, 17, 4, 43, 1, 17, 7, 1,
1280 8, 44, 4, 7, 44, 5, 8, 2, 5, 1, 2, 48, 45, 1, 12, 45,
1281 12, 48, 13, 13, 1, 9, 9, 46, 1, 46, 47, 47, 49, 18, 18, 49},
1284 { 1, -1, 0, 1, -1, 2, -2, 1, -1, 1, -1, 1, -1, 3, -3, 1,
1285 -1, -2, 2, 1, -1, 1, -1, 4, -4, -2, 2, 1, -1, 1, -1, 5,
1286 -5, -3, 3, 2, -2, 1, 0, -1, 1, -1, 1, -1, 6, -6, 2, -2,
1287 1, -1, 1, 1, -1, -1, -3, 3, 7, 2, -7, -2, -4, 4, 2, -2,
1288 2, -2, 1, -1, 8, -8, 3, -3, 1, -1, -5, 5, 9, 1, -9, 1,
1289 -1, -1, 1, -1, -4, 4, 1, -1, 3, -3, 1, -10, 10, 1, 2, -1,
1290 -1, -2, 6, -6, 2, 11, -11, -2, 3, -3, 1, -4, 4, -1, 3, -3,
1291 1, 3, 12, -3, -5, -12, -1, 5, 2, -2, 1, -1, -7, 1, 13, 7,
1292 -1, -13, 2, -2, 4, -4, 1, 2, -2, -1, 1, 14, -14, 1, 1, 1,
1293 -1, -5, -1, -1, 5, -1, -6, 2, -15, 15, 6, 1, -1, -8, 8, -2,
1294 -4, 4, 1, 1, -1, -1, 16, 2, -16, -2, 2, -2, 4, 3, -4, -3,
1295 -1, -4, 4, 1, -17, 17, -1, -9, 1, 1, 9, 1, -5, -1, -1, 5,
1296 -7, 7, 6, -6, 3, -3, 18, -18, 19, -19, 1, -10, -1, 10, -5, 5,
1297 20, -20, -3, 1, 3, 1, 8, -1, -8, 2, 7, -1, -21, -2, 5, 21,
1298 5, -1, -7, -5, 1, -6, -5, -11, 6, 22, 11, 1, 1, -22, -3, -1,
1299 3, -1, 3, -3, -23, 4, -4, 1, 23, -1, 1, -1, 1, -2, 2, -1}
1305 {1, 1, 1, 1, 0, 2, 2, 1, 1, 3, 3, 0, 1, 1, 2, 2,
1306 4, 4, 1, 1, 5, 5, 1, 1, 2, 2, 3, 3, 6, 6, 1, 1,
1307 7, 7, 8, 1, 8, 2, 2, 1, 4, 4, 1, 3, 1, 3, 9, 9,
1308 2, 2, 1, 5, 1, 5, 10, 10, 1, 1, 11, 11, 3, 6, 3, 4,
1309 4, 6, 2, 2, 1, 12, 1, 12, 7, 13, 7, 13, 1, 1, 8, 8,
1310 2, 2, 14, 14, 16, 15, 16, 5, 5, 1, 3, 15, 1, 3, 4, 4,
1311 1, 1, 17, 17, 2, 2, 6, 6, 1, 18, 1, 18, 22, 21, 22, 21,
1312 25, 24, 25, 19, 9, 20, 9, 23, 19, 24, 20, 3, 23, 7, 3, 1,
1313 1, 7, 28, 26, 29, 5, 28, 26, 5, 8, 29, 4, 8, 27, 2, 2,
1314 4, 27, 1, 1, 10, 36, 10, 33, 33, 36, 30, 1, 32, 32, 1, 30,
1315 6, 31, 31, 35, 3, 6, 11, 11, 3, 2, 35, 2, 34, 1, 34, 1,
1316 37, 37, 12, 7, 12, 5, 41, 5, 4, 7, 1, 8, 13, 4, 1, 41,
1317 13, 38, 8, 38, 9, 1, 40, 40, 9, 1, 39, 2, 2, 49, 39, 42,
1318 3, 3, 14, 16, 49, 14, 16, 42, 43, 43, 6, 6, 15, 1, 1, 15,
1319 44, 44, 1, 1, 50, 48, 4, 5, 4, 7, 5, 2, 10, 10, 48, 7,
1320 50, 45, 2, 1, 45, 8, 8, 1, 46, 46, 3, 47, 47, 3, 1, 1},
1323 { 1, -1, 2, -2, 0, 1, -1, 3, -3, 1, -1, 0, 4, -4, 2, -2,
1324 1, -1, 5, -5, 1, -1, 6, -6, 3, -3, 2, -2, 1, -1, 7, -7,
1325 1, -1, 1, 8, -1, 4, -4, -8, 2, -2, 9, 3, -9, -3, 1, -1,
1326 5, -5, 10, 2, -10, -2, 1, -1, 11, -11, 1, -1, -4, 2, 4, 3,
1327 -3, -2, 6, -6, 12, 1, -12, -1, 2, 1, -2, -1, 13, -13, 2, -2,
1328 7, -7, 1, -1, 1, 1, -1, 3, -3, 14, 5, -1, -14, -5, 4, -4,
1329 15, -15, 1, -1, 8, -8, -3, 3, 16, 1, -16, -1, 1, 1, -1, -1,
1330 1, 1, -1, 1, 2, 1, -2, 1, -1, -1, -1, 6, -1, 3, -6, 17,
1331 -17, -3, 1, 1, 1, 4, -1, -1, -4, 3, -1, 5, -3, -1, -9, 9,
1332 -5, 1, 18, -18, 2, 1, -2, 1, -1, -1, 1, 19, -1, 1, -19, -1,
1333 4, 1, -1, 1, 7, -4, -2, 2, -7, 10, -1, -10, 1, 20, -1, -20,
1334 1, -1, 2, 4, -2, 5, 1, -5, 6, -4, 21, 4, 2, -6, -21, -1,
1335 -2, 1, -4, -1, -3, 22, -1, 1, 3, -22, -1, 11, -11, 1, 1, 1,
1336 8, -8, 2, 2, -1, -2, -2, -1, 1, -1, -5, 5, 2, 23, -23, -2,
1337 1, -1, 24, -24, -1, -1, 7, 6, -7, 5, -6, 12, -3, 3, 1, -5,
1338 1, 1, -12, 25, -1, -5, 5, -25, -1, 1, 9, 1, -1, -9, 26, -26}