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 */
530 if (is_intra && band->dc_transform) {
531 band->dc_transform(&prev_dc, band->buf + buf_offs,
532 band->pitch, blk_size);
534 mc_no_delta_func(band->buf + buf_offs,
535 band->ref_buf + buf_offs + mv_y * band->pitch + mv_x,
536 band->pitch, mc_type);
549 * Handle empty tiles by performing data copying and motion
550 * compensation respectively.
552 * @param[in] avctx ptr to the AVCodecContext
553 * @param[in] band pointer to the band descriptor
554 * @param[in] tile pointer to the tile descriptor
555 * @param[in] mv_scale scaling factor for motion vectors
557 static int ivi_process_empty_tile(AVCodecContext *avctx, IVIBandDesc *band,
558 IVITile *tile, int32_t mv_scale)
560 int x, y, need_mc, mbn, blk, num_blocks, mv_x, mv_y, mc_type;
561 int offs, mb_offset, row_offset;
562 IVIMbInfo *mb, *ref_mb;
565 void (*mc_no_delta_func)(int16_t *buf, const int16_t *ref_buf, uint32_t pitch,
568 if (tile->num_MBs != IVI_MBs_PER_TILE(tile->width, tile->height, band->mb_size)) {
569 av_log(avctx, AV_LOG_ERROR, "Allocated tile size %d mismatches "
570 "parameters %d in ivi_process_empty_tile()\n",
571 tile->num_MBs, IVI_MBs_PER_TILE(tile->width, tile->height, band->mb_size));
572 return AVERROR_INVALIDDATA;
575 offs = tile->ypos * band->pitch + tile->xpos;
577 ref_mb = tile->ref_mbs;
578 row_offset = band->mb_size * band->pitch;
579 need_mc = 0; /* reset the mc tracking flag */
581 for (y = tile->ypos; y < (tile->ypos + tile->height); y += band->mb_size) {
584 for (x = tile->xpos; x < (tile->xpos + tile->width); x += band->mb_size) {
587 mb->buf_offs = mb_offset;
589 mb->type = 1; /* set the macroblocks type = INTER */
590 mb->cbp = 0; /* all blocks are empty */
592 if (!band->qdelta_present && !band->plane && !band->band_num) {
593 mb->q_delta = band->glob_quant;
598 if (band->inherit_qdelta && ref_mb)
599 mb->q_delta = ref_mb->q_delta;
601 if (band->inherit_mv) {
602 /* motion vector inheritance */
604 mb->mv_x = ivi_scale_mv(ref_mb->mv_x, mv_scale);
605 mb->mv_y = ivi_scale_mv(ref_mb->mv_y, mv_scale);
607 mb->mv_x = ref_mb->mv_x;
608 mb->mv_y = ref_mb->mv_y;
610 need_mc |= mb->mv_x || mb->mv_y; /* tracking non-zero motion vectors */
616 mb_offset += band->mb_size;
621 if (band->inherit_mv && need_mc) { /* apply motion compensation if there is at least one non-zero motion vector */
622 num_blocks = (band->mb_size != band->blk_size) ? 4 : 1; /* number of blocks per mb */
623 mc_no_delta_func = (band->blk_size == 8) ? ff_ivi_mc_8x8_no_delta
624 : ff_ivi_mc_4x4_no_delta;
626 for (mbn = 0, mb = tile->mbs; mbn < tile->num_MBs; mb++, mbn++) {
629 if (!band->is_halfpel) {
630 mc_type = 0; /* we have only fullpel vectors */
632 mc_type = ((mv_y & 1) << 1) | (mv_x & 1);
634 mv_y >>= 1; /* convert halfpel vectors into fullpel ones */
637 for (blk = 0; blk < num_blocks; blk++) {
638 /* adjust block position in the buffer according with its number */
639 offs = mb->buf_offs + band->blk_size * ((blk & 1) + !!(blk & 2) * band->pitch);
640 mc_no_delta_func(band->buf + offs,
641 band->ref_buf + offs + mv_y * band->pitch + mv_x,
642 band->pitch, mc_type);
646 /* copy data from the reference tile into the current one */
647 src = band->ref_buf + tile->ypos * band->pitch + tile->xpos;
648 dst = band->buf + tile->ypos * band->pitch + tile->xpos;
649 for (y = 0; y < tile->height; y++) {
650 memcpy(dst, src, tile->width*sizeof(band->buf[0]));
661 static uint16_t ivi_calc_band_checksum(IVIBandDesc *band)
664 int16_t *src, checksum;
669 for (y = 0; y < band->height; src += band->pitch, y++)
670 for (x = 0; x < band->width; x++)
678 * Convert and output the current plane.
679 * This conversion is done by adding back the bias value of 128
680 * (subtracted in the encoder) and clipping the result.
682 * @param[in] plane pointer to the descriptor of the plane being processed
683 * @param[out] dst pointer to the buffer receiving converted pixels
684 * @param[in] dst_pitch pitch for moving to the next y line
686 static void ivi_output_plane(IVIPlaneDesc *plane, uint8_t *dst, int dst_pitch)
689 const int16_t *src = plane->bands[0].buf;
690 uint32_t pitch = plane->bands[0].pitch;
695 for (y = 0; y < plane->height; y++) {
696 for (x = 0; x < plane->width; x++)
697 dst[x] = av_clip_uint8(src[x] + 128);
704 * Decode an Indeo 4 or 5 band.
706 * @param[in,out] ctx ptr to the decoder context
707 * @param[in,out] band ptr to the band descriptor
708 * @param[in] avctx ptr to the AVCodecContext
709 * @return result code: 0 = OK, -1 = error
711 static int decode_band(IVI45DecContext *ctx,
712 IVIBandDesc *band, AVCodecContext *avctx)
714 int result, i, t, idx1, idx2, pos;
717 band->buf = band->bufs[ctx->dst_buf];
719 av_log(avctx, AV_LOG_ERROR, "Band buffer points to no data!\n");
720 return AVERROR_INVALIDDATA;
722 band->ref_buf = band->bufs[ctx->ref_buf];
723 band->data_ptr = ctx->frame_data + (get_bits_count(&ctx->gb) >> 3);
725 result = ctx->decode_band_hdr(ctx, band, avctx);
727 av_log(avctx, AV_LOG_ERROR, "Error while decoding band header: %d\n",
732 if (band->is_empty) {
733 av_log(avctx, AV_LOG_ERROR, "Empty band encountered!\n");
734 return AVERROR_INVALIDDATA;
737 band->rv_map = &ctx->rvmap_tabs[band->rvmap_sel];
739 /* apply corrections to the selected rvmap table if present */
740 for (i = 0; i < band->num_corr; i++) {
741 idx1 = band->corr[i * 2];
742 idx2 = band->corr[i * 2 + 1];
743 FFSWAP(uint8_t, band->rv_map->runtab[idx1], band->rv_map->runtab[idx2]);
744 FFSWAP(int16_t, band->rv_map->valtab[idx1], band->rv_map->valtab[idx2]);
747 pos = get_bits_count(&ctx->gb);
749 for (t = 0; t < band->num_tiles; t++) {
750 tile = &band->tiles[t];
752 if (tile->mb_size != band->mb_size) {
753 av_log(avctx, AV_LOG_ERROR, "MB sizes mismatch: %d vs. %d\n",
754 band->mb_size, tile->mb_size);
755 return AVERROR_INVALIDDATA;
757 tile->is_empty = get_bits1(&ctx->gb);
758 if (tile->is_empty) {
759 result = ivi_process_empty_tile(avctx, band, tile,
760 (ctx->planes[0].bands[0].mb_size >> 3) - (band->mb_size >> 3));
763 av_dlog(avctx, "Empty tile encountered!\n");
765 tile->data_size = ivi_dec_tile_data_size(&ctx->gb);
766 if (!tile->data_size) {
767 av_log(avctx, AV_LOG_ERROR, "Tile data size is zero!\n");
768 return AVERROR_INVALIDDATA;
771 result = ctx->decode_mb_info(ctx, band, tile, avctx);
775 result = ivi_decode_blocks(&ctx->gb, band, tile, avctx);
776 if (result < 0 || ((get_bits_count(&ctx->gb) - pos) >> 3) != tile->data_size) {
777 av_log(avctx, AV_LOG_ERROR, "Corrupted tile data encountered!\n");
781 pos += tile->data_size << 3; // skip to next tile
785 /* restore the selected rvmap table by applying its corrections in reverse order */
786 for (i = band->num_corr-1; i >= 0; i--) {
787 idx1 = band->corr[i*2];
788 idx2 = band->corr[i*2+1];
789 FFSWAP(uint8_t, band->rv_map->runtab[idx1], band->rv_map->runtab[idx2]);
790 FFSWAP(int16_t, band->rv_map->valtab[idx1], band->rv_map->valtab[idx2]);
794 if (band->checksum_present) {
795 uint16_t chksum = ivi_calc_band_checksum(band);
796 if (chksum != band->checksum) {
797 av_log(avctx, AV_LOG_ERROR,
798 "Band checksum mismatch! Plane %d, band %d, received: %x, calculated: %x\n",
799 band->plane, band->band_num, band->checksum, chksum);
804 align_get_bits(&ctx->gb);
809 int ff_ivi_decode_frame(AVCodecContext *avctx, void *data, int *got_frame,
812 IVI45DecContext *ctx = avctx->priv_data;
813 const uint8_t *buf = avpkt->data;
814 int buf_size = avpkt->size;
817 init_get_bits(&ctx->gb, buf, buf_size * 8);
818 ctx->frame_data = buf;
819 ctx->frame_size = buf_size;
821 result = ctx->decode_pic_hdr(ctx, avctx);
823 av_log(avctx, AV_LOG_ERROR,
824 "Error while decoding picture header: %d\n", result);
827 if (ctx->gop_invalid)
828 return AVERROR_INVALIDDATA;
830 if (ctx->gop_flags & IVI5_IS_PROTECTED) {
831 av_log(avctx, AV_LOG_ERROR, "Password-protected clip!\n");
835 ctx->switch_buffers(ctx);
839 if (ctx->is_nonnull_frame(ctx)) {
840 for (p = 0; p < 3; p++) {
841 for (b = 0; b < ctx->planes[p].num_bands; b++) {
842 result = decode_band(ctx, &ctx->planes[p].bands[b], avctx);
844 av_log(avctx, AV_LOG_ERROR,
845 "Error while decoding band: %d, plane: %d\n", b, p);
852 //STOP_TIMER("decode_planes"); }
854 /* If the bidirectional mode is enabled, next I and the following P frame will */
855 /* be sent together. Unfortunately the approach below seems to be the only way */
856 /* to handle the B-frames mode. That's exactly the same Intel decoders do. */
857 if (avctx->codec_id == AV_CODEC_ID_INDEO4 && ctx->frame_type == 0/*FRAMETYPE_INTRA*/) {
858 while (get_bits(&ctx->gb, 8)); // skip version string
859 skip_bits_long(&ctx->gb, 64); // skip padding, TODO: implement correct 8-bytes alignment
860 if (get_bits_left(&ctx->gb) > 18 && show_bits(&ctx->gb, 18) == 0x3FFF8)
861 av_log(avctx, AV_LOG_ERROR, "Buffer contains IP frames!\n");
864 if (ctx->frame.data[0])
865 avctx->release_buffer(avctx, &ctx->frame);
867 ctx->frame.reference = 0;
868 avcodec_set_dimensions(avctx, ctx->planes[0].width, ctx->planes[0].height);
869 if ((result = ff_get_buffer(avctx, &ctx->frame)) < 0) {
870 av_log(avctx, AV_LOG_ERROR, "get_buffer() failed\n");
874 if (ctx->is_scalable) {
875 if (avctx->codec_id == AV_CODEC_ID_INDEO4)
876 ff_ivi_recompose_haar(&ctx->planes[0], ctx->frame.data[0], ctx->frame.linesize[0]);
878 ff_ivi_recompose53 (&ctx->planes[0], ctx->frame.data[0], ctx->frame.linesize[0]);
880 ivi_output_plane(&ctx->planes[0], ctx->frame.data[0], ctx->frame.linesize[0]);
883 ivi_output_plane(&ctx->planes[2], ctx->frame.data[1], ctx->frame.linesize[1]);
884 ivi_output_plane(&ctx->planes[1], ctx->frame.data[2], ctx->frame.linesize[2]);
887 *(AVFrame*)data = ctx->frame;
893 * Close Indeo5 decoder and clean up its context.
895 av_cold int ff_ivi_decode_close(AVCodecContext *avctx)
897 IVI45DecContext *ctx = avctx->priv_data;
899 ivi_free_buffers(&ctx->planes[0]);
901 if (ctx->mb_vlc.cust_tab.table)
902 ff_free_vlc(&ctx->mb_vlc.cust_tab);
904 if (ctx->frame.data[0])
905 avctx->release_buffer(avctx, &ctx->frame);
907 #if IVI4_STREAM_ANALYSER
908 if (avctx->codec_id == AV_CODEC_ID_INDEO4) {
909 if (ctx->is_scalable)
910 av_log(avctx, AV_LOG_ERROR, "This video uses scalability mode!\n");
911 if (ctx->uses_tiling)
912 av_log(avctx, AV_LOG_ERROR, "This video uses local decoding!\n");
913 if (ctx->has_b_frames)
914 av_log(avctx, AV_LOG_ERROR, "This video contains B-frames!\n");
916 av_log(avctx, AV_LOG_ERROR, "Transparency mode is enabled!\n");
918 av_log(avctx, AV_LOG_ERROR, "This video uses Haar transform!\n");
919 if (ctx->uses_fullpel)
920 av_log(avctx, AV_LOG_ERROR, "This video uses fullpel motion vectors!\n");
929 * These are 2x8 predefined Huffman codebooks for coding macroblock/block
930 * signals. They are specified using "huffman descriptors" in order to
931 * avoid huge static tables. The decoding tables will be generated at
932 * startup from these descriptors.
934 const IVIHuffDesc ff_ivi_mb_huff_desc[8] = {
935 {8, {0, 4, 5, 4, 4, 4, 6, 6}},
936 {12, {0, 2, 2, 3, 3, 3, 3, 5, 3, 2, 2, 2}},
937 {12, {0, 2, 3, 4, 3, 3, 3, 3, 4, 3, 2, 2}},
938 {12, {0, 3, 4, 4, 3, 3, 3, 3, 3, 2, 2, 2}},
939 {13, {0, 4, 4, 3, 3, 3, 3, 2, 3, 3, 2, 1, 1}},
940 {9, {0, 4, 4, 4, 4, 3, 3, 3, 2}},
941 {10, {0, 4, 4, 4, 4, 3, 3, 2, 2, 2}},
942 {12, {0, 4, 4, 4, 3, 3, 2, 3, 2, 2, 2, 2}}
945 const IVIHuffDesc ff_ivi_blk_huff_desc[8] = {
946 {10, {1, 2, 3, 4, 4, 7, 5, 5, 4, 1}},
947 {11, {2, 3, 4, 4, 4, 7, 5, 4, 3, 3, 2}},
948 {12, {2, 4, 5, 5, 5, 5, 6, 4, 4, 3, 1, 1}},
949 {13, {3, 3, 4, 4, 5, 6, 6, 4, 4, 3, 2, 1, 1}},
950 {11, {3, 4, 4, 5, 5, 5, 6, 5, 4, 2, 2}},
951 {13, {3, 4, 5, 5, 5, 5, 6, 4, 3, 3, 2, 1, 1}},
952 {13, {3, 4, 5, 5, 5, 6, 5, 4, 3, 3, 2, 1, 1}},
953 {9, {3, 4, 4, 5, 5, 5, 6, 5, 5}}
958 * Scan patterns shared between indeo4 and indeo5
960 const uint8_t ff_ivi_vertical_scan_8x8[64] = {
961 0, 8, 16, 24, 32, 40, 48, 56,
962 1, 9, 17, 25, 33, 41, 49, 57,
963 2, 10, 18, 26, 34, 42, 50, 58,
964 3, 11, 19, 27, 35, 43, 51, 59,
965 4, 12, 20, 28, 36, 44, 52, 60,
966 5, 13, 21, 29, 37, 45, 53, 61,
967 6, 14, 22, 30, 38, 46, 54, 62,
968 7, 15, 23, 31, 39, 47, 55, 63
971 const uint8_t ff_ivi_horizontal_scan_8x8[64] = {
972 0, 1, 2, 3, 4, 5, 6, 7,
973 8, 9, 10, 11, 12, 13, 14, 15,
974 16, 17, 18, 19, 20, 21, 22, 23,
975 24, 25, 26, 27, 28, 29, 30, 31,
976 32, 33, 34, 35, 36, 37, 38, 39,
977 40, 41, 42, 43, 44, 45, 46, 47,
978 48, 49, 50, 51, 52, 53, 54, 55,
979 56, 57, 58, 59, 60, 61, 62, 63
982 const uint8_t ff_ivi_direct_scan_4x4[16] = {
983 0, 1, 4, 8, 5, 2, 3, 6, 9, 12, 13, 10, 7, 11, 14, 15
988 * Run-value (RLE) tables.
990 const RVMapDesc ff_ivi_rvmap_tabs[9] = {
995 {1, 1, 0, 1, 1, 0, 1, 1, 2, 2, 1, 1, 1, 1, 3, 3,
996 1, 1, 2, 2, 1, 1, 4, 4, 1, 1, 1, 1, 2, 2, 5, 5,
997 1, 1, 3, 3, 1, 1, 6, 6, 1, 2, 1, 2, 7, 7, 1, 1,
998 8, 8, 1, 1, 4, 2, 1, 4, 2, 1, 3, 3, 1, 1, 1, 9,
999 9, 1, 2, 1, 2, 1, 5, 5, 1, 1, 10, 10, 1, 1, 3, 3,
1000 2, 2, 1, 1, 11, 11, 6, 4, 4, 1, 6, 1, 2, 1, 2, 12,
1001 8, 1, 12, 7, 8, 7, 1, 16, 1, 16, 1, 3, 3, 13, 1, 13,
1002 2, 2, 1, 15, 1, 5, 14, 15, 1, 5, 14, 1, 17, 8, 17, 8,
1003 1, 4, 4, 2, 2, 1, 25, 25, 24, 24, 1, 3, 1, 3, 1, 8,
1004 6, 7, 6, 1, 18, 8, 18, 1, 7, 23, 2, 2, 23, 1, 1, 21,
1005 22, 9, 9, 22, 19, 1, 21, 5, 19, 5, 1, 33, 20, 33, 20, 8,
1006 4, 4, 1, 32, 2, 2, 8, 3, 32, 26, 3, 1, 7, 7, 26, 6,
1007 1, 6, 1, 1, 16, 1, 10, 1, 10, 2, 16, 29, 28, 2, 29, 28,
1008 1, 27, 5, 8, 5, 27, 1, 8, 3, 7, 3, 31, 41, 31, 1, 41,
1009 6, 1, 6, 7, 4, 4, 1, 1, 2, 1, 2, 11, 34, 30, 11, 1,
1010 30, 15, 15, 34, 36, 40, 36, 40, 35, 35, 37, 37, 39, 39, 38, 38},
1013 { 1, -1, 0, 2, -2, 0, 3, -3, 1, -1, 4, -4, 5, -5, 1, -1,
1014 6, -6, 2, -2, 7, -7, 1, -1, 8, -8, 9, -9, 3, -3, 1, -1,
1015 10, -10, 2, -2, 11, -11, 1, -1, 12, 4, -12, -4, 1, -1, 13, -13,
1016 1, -1, 14, -14, 2, 5, 15, -2, -5, -15, -3, 3, 16, -16, 17, 1,
1017 -1, -17, 6, 18, -6, -18, 2, -2, 19, -19, 1, -1, 20, -20, 4, -4,
1018 7, -7, 21, -21, 1, -1, 2, 3, -3, 22, -2, -22, 8, 23, -8, 1,
1019 2, -23, -1, 2, -2, -2, 24, 1, -24, -1, 25, 5, -5, 1, -25, -1,
1020 9, -9, 26, 1, -26, 3, 1, -1, 27, -3, -1, -27, 1, 3, -1, -3,
1021 28, -4, 4, 10, -10, -28, 1, -1, 1, -1, 29, 6, -29, -6, 30, -4,
1022 3, 3, -3, -30, 1, 4, -1, 31, -3, 1, 11, -11, -1, -31, 32, -1,
1023 -1, 2, -2, 1, 1, -32, 1, 4, -1, -4, 33, -1, 1, 1, -1, 5,
1024 5, -5, -33, -1, -12, 12, -5, -7, 1, 1, 7, 34, 4, -4, -1, 4,
1025 -34, -4, 35, 36, -2, -35, -2, -36, 2, 13, 2, -1, 1, -13, 1, -1,
1026 37, 1, -5, 6, 5, -1, 38, -6, -8, 5, 8, -1, 1, 1, -37, -1,
1027 5, 39, -5, -5, 6, -6, -38, -39, -14, 40, 14, 2, 1, 1, -2, -40,
1028 -1, -2, 2, -1, -1, -1, 1, 1, 1, -1, 1, -1, 1, -1, 1, -1}
1034 {0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 8, 6, 8, 7,
1035 7, 9, 9, 10, 10, 11, 11, 1, 12, 1, 12, 13, 13, 16, 14, 16,
1036 14, 15, 15, 17, 17, 18, 0, 18, 19, 20, 21, 19, 22, 21, 20, 22,
1037 25, 24, 2, 25, 24, 23, 23, 2, 26, 28, 26, 28, 29, 27, 29, 27,
1038 33, 33, 1, 32, 1, 3, 32, 30, 36, 3, 36, 30, 31, 31, 35, 34,
1039 37, 41, 34, 35, 37, 4, 41, 4, 49, 8, 8, 49, 40, 38, 5, 38,
1040 40, 39, 5, 39, 42, 43, 42, 7, 57, 6, 43, 44, 6, 50, 7, 44,
1041 57, 48, 50, 48, 45, 45, 46, 47, 51, 46, 47, 58, 1, 51, 58, 1,
1042 52, 59, 53, 9, 52, 55, 55, 59, 53, 56, 54, 56, 54, 9, 64, 64,
1043 60, 63, 60, 63, 61, 62, 61, 62, 2, 10, 2, 10, 11, 1, 11, 13,
1044 12, 1, 12, 13, 16, 16, 8, 8, 14, 3, 3, 15, 14, 15, 4, 4,
1045 1, 17, 17, 5, 1, 7, 7, 5, 6, 1, 2, 2, 6, 22, 1, 25,
1046 21, 22, 8, 24, 1, 21, 25, 24, 8, 18, 18, 23, 9, 20, 23, 33,
1047 29, 33, 20, 1, 19, 1, 29, 36, 9, 36, 19, 41, 28, 57, 32, 3,
1048 28, 3, 1, 27, 49, 49, 1, 32, 26, 26, 2, 4, 4, 7, 57, 41,
1049 2, 7, 10, 5, 37, 16, 10, 27, 8, 8, 13, 16, 37, 13, 1, 5},
1052 {0, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, 1, -1, -1, 1,
1053 -1, 1, -1, 1, -1, 1, -1, 2, 1, -2, -1, 1, -1, 1, 1, -1,
1054 -1, 1, -1, 1, -1, 1, 0, -1, 1, 1, 1, -1, 1, -1, -1, -1,
1055 1, 1, 2, -1, -1, 1, -1, -2, 1, 1, -1, -1, 1, 1, -1, -1,
1056 1, -1, 3, 1, -3, 2, -1, 1, 1, -2, -1, -1, -1, 1, 1, 1,
1057 1, 1, -1, -1, -1, 2, -1, -2, 1, 2, -2, -1, 1, 1, 2, -1,
1058 -1, 1, -2, -1, 1, 1, -1, 2, 1, 2, -1, 1, -2, -1, -2, -1,
1059 -1, 1, 1, -1, 1, -1, 1, 1, 1, -1, -1, 1, 4, -1, -1, -4,
1060 1, 1, 1, 2, -1, -1, 1, -1, -1, 1, -1, -1, 1, -2, 1, -1,
1061 1, 1, -1, -1, 1, 1, -1, -1, 3, 2, -3, -2, 2, 5, -2, 2,
1062 2, -5, -2, -2, -2, 2, -3, 3, 2, 3, -3, 2, -2, -2, 3, -3,
1063 6, 2, -2, 3, -6, 3, -3, -3, 3, 7, -4, 4, -3, 2, -7, 2,
1064 2, -2, -4, 2, 8, -2, -2, -2, 4, 2, -2, 2, 3, 2, -2, -2,
1065 2, 2, -2, -8, -2, 9, -2, 2, -3, -2, 2, -2, 2, 2, 2, 4,
1066 -2, -4, 10, 2, 2, -2, -9, -2, 2, -2, 5, 4, -4, 4, -2, 2,
1067 -5, -4, -3, 4, 2, -3, 3, -2, -5, 5, 3, 3, -2, -3, -10, -4}
1073 {1, 1, 0, 2, 2, 1, 1, 3, 3, 4, 4, 0, 1, 1, 5, 5,
1074 2, 2, 6, 6, 7, 7, 1, 8, 1, 8, 3, 3, 9, 9, 1, 2,
1075 2, 1, 4, 10, 4, 10, 11, 11, 1, 5, 12, 12, 1, 5, 13, 13,
1076 3, 3, 6, 6, 2, 2, 14, 14, 16, 16, 15, 7, 15, 8, 8, 7,
1077 1, 1, 17, 17, 4, 4, 1, 1, 18, 18, 2, 2, 5, 5, 25, 3,
1078 9, 3, 25, 9, 19, 24, 19, 24, 1, 21, 20, 1, 21, 22, 20, 22,
1079 23, 23, 8, 6, 33, 6, 8, 33, 7, 7, 26, 26, 1, 32, 1, 32,
1080 28, 4, 28, 10, 29, 27, 27, 10, 41, 4, 29, 2, 2, 41, 36, 31,
1081 49, 31, 34, 30, 34, 36, 30, 35, 1, 49, 11, 5, 35, 11, 1, 3,
1082 3, 5, 37, 37, 8, 40, 8, 40, 12, 12, 42, 42, 1, 38, 16, 57,
1083 1, 6, 16, 39, 38, 6, 7, 7, 13, 13, 39, 43, 2, 43, 57, 2,
1084 50, 9, 44, 9, 50, 4, 15, 48, 44, 4, 1, 15, 48, 14, 14, 1,
1085 45, 45, 8, 3, 5, 8, 51, 47, 3, 46, 46, 47, 5, 51, 1, 17,
1086 17, 58, 1, 58, 2, 52, 52, 2, 53, 7, 59, 6, 6, 56, 53, 55,
1087 7, 55, 1, 54, 59, 56, 54, 10, 1, 10, 4, 60, 1, 60, 8, 4,
1088 8, 64, 64, 61, 1, 63, 3, 63, 62, 61, 5, 11, 5, 3, 11, 62},
1091 { 1, -1, 0, 1, -1, 2, -2, 1, -1, 1, -1, 0, 3, -3, 1, -1,
1092 2, -2, 1, -1, 1, -1, 4, 1, -4, -1, 2, -2, 1, -1, 5, 3,
1093 -3, -5, 2, 1, -2, -1, 1, -1, 6, 2, 1, -1, -6, -2, 1, -1,
1094 3, -3, 2, -2, 4, -4, 1, -1, 1, -1, 1, 2, -1, 2, -2, -2,
1095 7, -7, 1, -1, 3, -3, 8, -8, 1, -1, 5, -5, 3, -3, 1, 4,
1096 2, -4, -1, -2, 1, 1, -1, -1, 9, 1, 1, -9, -1, 1, -1, -1,
1097 1, -1, 3, -3, 1, 3, -3, -1, 3, -3, 1, -1, 10, 1, -10, -1,
1098 1, 4, -1, 2, 1, -1, 1, -2, 1, -4, -1, 6, -6, -1, 1, 1,
1099 1, -1, 1, 1, -1, -1, -1, 1, 11, -1, -2, 4, -1, 2, -11, 5,
1100 -5, -4, -1, 1, 4, 1, -4, -1, -2, 2, 1, -1, 12, 1, -2, 1,
1101 -12, 4, 2, 1, -1, -4, 4, -4, 2, -2, -1, 1, 7, -1, -1, -7,
1102 -1, -3, 1, 3, 1, 5, 2, 1, -1, -5, 13, -2, -1, 2, -2, -13,
1103 1, -1, 5, 6, 5, -5, 1, 1, -6, 1, -1, -1, -5, -1, 14, 2,
1104 -2, 1, -14, -1, 8, 1, -1, -8, 1, 5, 1, 5, -5, 1, -1, 1,
1105 -5, -1, 15, 1, -1, -1, -1, 3, -15, -3, 6, 1, 16, -1, 6, -6,
1106 -6, 1, -1, 1, -16, 1, 7, -1, 1, -1, -6, -3, 6, -7, 3, -1}
1112 {0, 1, 1, 2, 2, 3, 3, 4, 4, 1, 1, 5, 5, 6, 6, 7,
1113 7, 8, 8, 9, 9, 2, 2, 10, 10, 1, 1, 11, 11, 12, 12, 3,
1114 3, 13, 13, 0, 14, 14, 16, 15, 16, 15, 4, 4, 17, 1, 17, 1,
1115 5, 5, 18, 18, 2, 2, 6, 6, 8, 19, 7, 8, 7, 19, 20, 20,
1116 21, 21, 22, 24, 22, 24, 23, 23, 1, 1, 25, 25, 3, 3, 26, 26,
1117 9, 9, 27, 27, 28, 28, 33, 29, 4, 33, 29, 1, 4, 1, 32, 32,
1118 2, 2, 31, 10, 30, 10, 30, 31, 34, 34, 5, 5, 36, 36, 35, 41,
1119 35, 11, 41, 11, 37, 1, 8, 8, 37, 6, 1, 6, 40, 7, 7, 40,
1120 12, 38, 12, 39, 39, 38, 49, 13, 49, 13, 3, 42, 3, 42, 16, 16,
1121 43, 43, 14, 14, 1, 1, 44, 15, 44, 15, 2, 2, 57, 48, 50, 48,
1122 57, 50, 4, 45, 45, 4, 46, 47, 47, 46, 1, 51, 1, 17, 17, 51,
1123 8, 9, 9, 5, 58, 8, 58, 5, 52, 52, 55, 56, 53, 56, 55, 59,
1124 59, 53, 54, 1, 6, 54, 7, 7, 6, 1, 2, 3, 2, 3, 64, 60,
1125 60, 10, 10, 64, 61, 62, 61, 63, 1, 63, 62, 1, 18, 24, 18, 4,
1126 25, 4, 8, 21, 21, 1, 24, 22, 25, 22, 8, 11, 19, 11, 23, 1,
1127 20, 23, 19, 20, 5, 12, 5, 1, 16, 2, 12, 13, 2, 13, 1, 16},
1130 { 0, 1, -1, 1, -1, 1, -1, 1, -1, 2, -2, 1, -1, 1, -1, 1,
1131 -1, 1, -1, 1, -1, 2, -2, 1, -1, 3, -3, 1, -1, 1, -1, 2,
1132 -2, 1, -1, 0, 1, -1, 1, 1, -1, -1, 2, -2, 1, 4, -1, -4,
1133 2, -2, 1, -1, -3, 3, 2, -2, 2, 1, 2, -2, -2, -1, 1, -1,
1134 1, -1, 1, 1, -1, -1, 1, -1, 5, -5, 1, -1, 3, -3, 1, -1,
1135 2, -2, 1, -1, 1, -1, 1, 1, 3, -1, -1, 6, -3, -6, -1, 1,
1136 4, -4, 1, 2, 1, -2, -1, -1, 1, -1, 3, -3, 1, -1, 1, 1,
1137 -1, 2, -1, -2, 1, 7, -3, 3, -1, 3, -7, -3, 1, -3, 3, -1,
1138 2, 1, -2, 1, -1, -1, 1, 2, -1, -2, -4, -1, 4, 1, 2, -2,
1139 1, -1, -2, 2, 8, -8, -1, 2, 1, -2, -5, 5, 1, -1, -1, 1,
1140 -1, 1, 4, -1, 1, -4, -1, -1, 1, 1, 9, 1, -9, 2, -2, -1,
1141 -4, 3, -3, -4, -1, 4, 1, 4, 1, -1, 1, -1, 1, 1, -1, 1,
1142 -1, -1, -1, 10, 4, 1, 4, -4, -4, -10, 6, 5, -6, -5, 1, -1,
1143 1, 3, -3, -1, 1, -1, -1, -1, 11, 1, 1, -11, -2, -2, 2, 5,
1144 -2, -5, -5, 2, -2, 12, 2, -2, 2, 2, 5, -3, -2, 3, -2, -12,
1145 -2, 2, 2, 2, -5, 3, 5, 13, -3, 7, -3, -3, -7, 3, -13, 3}
1151 {0, 1, 1, 1, 2, 2, 1, 3, 3, 1, 1, 1, 4, 4, 1, 5,
1152 2, 1, 5, 2, 1, 1, 6, 6, 1, 1, 1, 1, 1, 7, 3, 1,
1153 2, 3, 0, 1, 2, 7, 1, 1, 1, 8, 1, 1, 8, 1, 1, 1,
1154 9, 1, 9, 1, 2, 1, 1, 2, 1, 1, 10, 4, 1, 10, 1, 4,
1155 1, 1, 1, 1, 1, 3, 1, 1, 1, 3, 2, 1, 5, 1, 1, 1,
1156 2, 5, 1, 11, 1, 11, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1157 2, 1, 6, 1, 6, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 12,
1158 3, 1, 12, 1, 1, 1, 2, 1, 1, 3, 1, 1, 1, 1, 1, 1,
1159 4, 1, 1, 1, 2, 1, 1, 4, 1, 1, 1, 1, 1, 1, 2, 1,
1160 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 2, 1, 1, 5,
1161 1, 1, 1, 1, 1, 7, 1, 7, 1, 1, 2, 3, 1, 1, 1, 1,
1162 5, 1, 1, 1, 1, 1, 1, 2, 13, 1, 1, 1, 1, 1, 1, 1,
1163 1, 1, 1, 1, 1, 1, 1, 1, 13, 2, 1, 1, 4, 1, 1, 1,
1164 3, 1, 6, 1, 1, 1, 14, 1, 1, 1, 1, 1, 14, 6, 1, 1,
1165 1, 1, 15, 2, 4, 1, 2, 3, 15, 1, 1, 1, 8, 1, 1, 8,
1166 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1},
1169 { 0, 1, -1, 2, 1, -1, -2, 1, -1, 3, -3, 4, 1, -1, -4, 1,
1170 2, 5, -1, -2, -5, 6, 1, -1, -6, 7, -7, 8, -8, 1, 2, 9,
1171 3, -2, 0, -9, -3, -1, 10, -10, 11, 1, -11, 12, -1, -12, 13, -13,
1172 1, 14, -1, -14, 4, 15, -15, -4, 16, -16, 1, 2, 17, -1, -17, -2,
1173 18, -18, 19, -19, 20, 3, -20, 21, -21, -3, 5, 22, 2, -22, -23, 23,
1174 -5, -2, 24, 1, -24, -1, 25, -25, 26, -26, -27, 27, 28, 29, -28, -29,
1175 6, 30, 2, -31, -2, -30, 31, -6, -32, 32, 33, -33, 34, -35, -34, 1,
1176 4, -36, -1, 35, 37, 36, 7, -37, 38, -4, -38, 39, 41, 40, -40, -39,
1177 3, 42, -43, -41, -7, -42, 43, -3, 44, -44, 45, -45, 46, 47, 8, -47,
1178 -48, -46, 50, -50, 48, 49, 51, -49, 52, -52, 5, -51, -8, -53, 53, 3,
1179 -56, 56, 55, 54, -54, 2, 60, -2, -55, 58, 9, -5, 59, 57, -57, -63,
1180 -3, -58, -60, -61, 61, -59, -62, -9, 1, 64, 62, 69, -64, 63, 65, -67,
1181 -68, 66, -65, 68, -66, -69, 67, -70, -1, 10, 71, -71, 4, 73, 72, 70,
1182 6, -76, -3, 74, -78, -74, 1, 78, 80, -72, -75, 76, -1, 3, -73, 79,
1183 75, 77, 1, 11, -4, -79, -10, -6, -1, -77, -83, -80, 2, 81, -84, -2,
1184 83, -81, 82, -82, 84, -87, -86, 85, -11, -85, 86, -89, 87, -88, 88, 89}
1190 {1, 1, 0, 2, 1, 2, 1, 3, 3, 1, 1, 4, 4, 2, 2, 1,
1191 1, 5, 5, 6, 1, 6, 1, 7, 7, 3, 3, 2, 8, 2, 8, 1,
1192 1, 0, 9, 9, 1, 1, 10, 4, 10, 4, 11, 11, 2, 1, 2, 1,
1193 12, 12, 3, 3, 1, 1, 13, 5, 5, 13, 14, 1, 1, 14, 2, 2,
1194 6, 6, 15, 1, 1, 15, 16, 4, 7, 16, 4, 7, 1, 1, 3, 3,
1195 8, 8, 2, 2, 1, 1, 17, 17, 1, 1, 18, 18, 5, 5, 2, 2,
1196 1, 1, 9, 19, 9, 19, 20, 3, 3, 20, 1, 10, 21, 1, 10, 4,
1197 4, 21, 22, 6, 6, 22, 1, 1, 23, 24, 2, 2, 23, 24, 11, 1,
1198 1, 11, 7, 25, 7, 1, 1, 25, 8, 8, 3, 26, 3, 1, 12, 2,
1199 2, 26, 1, 12, 5, 5, 27, 4, 1, 4, 1, 27, 28, 1, 28, 13,
1200 1, 13, 2, 29, 2, 1, 32, 6, 1, 30, 14, 29, 14, 6, 3, 31,
1201 3, 1, 30, 1, 32, 31, 33, 9, 33, 1, 1, 7, 9, 7, 2, 2,
1202 1, 1, 4, 36, 34, 4, 5, 10, 10, 5, 34, 1, 1, 35, 8, 8,
1203 36, 3, 35, 1, 15, 3, 2, 1, 16, 15, 16, 2, 37, 1, 37, 1,
1204 1, 1, 6, 6, 38, 1, 38, 11, 1, 39, 39, 40, 11, 2, 41, 4,
1205 40, 1, 2, 4, 1, 1, 1, 41, 3, 1, 3, 1, 5, 7, 5, 7},
1208 { 1, -1, 0, 1, 2, -1, -2, 1, -1, 3, -3, 1, -1, 2, -2, 4,
1209 -4, 1, -1, 1, 5, -1, -5, 1, -1, 2, -2, 3, 1, -3, -1, 6,
1210 -6, 0, 1, -1, 7, -7, 1, 2, -1, -2, 1, -1, 4, 8, -4, -8,
1211 1, -1, 3, -3, 9, -9, 1, 2, -2, -1, 1, 10, -10, -1, 5, -5,
1212 2, -2, 1, 11, -11, -1, 1, 3, 2, -1, -3, -2, 12, -12, 4, -4,
1213 2, -2, -6, 6, 13, -13, 1, -1, 14, -14, 1, -1, 3, -3, 7, -7,
1214 15, -15, 2, 1, -2, -1, 1, 5, -5, -1, -16, 2, 1, 16, -2, 4,
1215 -4, -1, 1, 3, -3, -1, 17, -17, 1, 1, -8, 8, -1, -1, 2, 18,
1216 -18, -2, 3, 1, -3, 19, -19, -1, 3, -3, 6, 1, -6, 20, 2, 9,
1217 -9, -1, -20, -2, 4, -4, 1, -5, 21, 5, -21, -1, 1, -22, -1, 2,
1218 22, -2, 10, 1, -10, 23, 1, 4, -23, 1, 2, -1, -2, -4, -7, 1,
1219 7, -24, -1, 24, -1, -1, 1, 3, -1, -25, 25, 4, -3, -4, 11, -11,
1220 26, -26, 6, 1, 1, -6, -5, -3, 3, 5, -1, -27, 27, 1, 4, -4,
1221 -1, -8, -1, 28, 2, 8, -12, -28, -2, -2, 2, 12, -1, 29, 1, -29,
1222 30, -30, 5, -5, 1, -31, -1, 3, 31, -1, 1, 1, -3, -13, 1, -7,
1223 -1, -32, 13, 7, 32, 33, -33, -1, -9, -34, 9, 34, -6, 5, 6, -5}
1229 {1, 1, 0, 1, 1, 2, 2, 1, 1, 3, 3, 1, 1, 0, 2, 2,
1230 4, 1, 4, 1, 1, 1, 5, 5, 1, 1, 6, 6, 2, 2, 1, 1,
1231 3, 3, 7, 7, 1, 1, 8, 8, 1, 1, 2, 2, 1, 9, 1, 9,
1232 4, 4, 10, 1, 1, 10, 1, 1, 11, 11, 3, 3, 1, 2, 1, 2,
1233 1, 1, 12, 12, 5, 5, 1, 1, 13, 1, 1, 13, 2, 2, 1, 1,
1234 6, 6, 1, 1, 4, 14, 4, 14, 3, 1, 3, 1, 1, 1, 15, 7,
1235 15, 2, 2, 7, 1, 1, 1, 8, 1, 8, 16, 16, 1, 1, 1, 1,
1236 2, 1, 1, 2, 1, 1, 3, 5, 5, 3, 4, 1, 1, 4, 1, 1,
1237 17, 17, 9, 1, 1, 9, 2, 2, 1, 1, 10, 10, 1, 6, 1, 1,
1238 6, 18, 1, 1, 18, 1, 1, 1, 2, 2, 3, 1, 3, 1, 1, 1,
1239 4, 1, 19, 1, 19, 7, 1, 1, 20, 1, 4, 20, 1, 7, 11, 2,
1240 1, 11, 21, 2, 8, 5, 1, 8, 1, 5, 21, 1, 1, 1, 22, 1,
1241 1, 22, 1, 1, 3, 3, 1, 23, 2, 12, 24, 1, 1, 2, 1, 1,
1242 12, 23, 1, 1, 24, 1, 1, 1, 4, 1, 1, 1, 2, 1, 6, 6,
1243 4, 2, 1, 1, 1, 1, 1, 1, 1, 14, 13, 3, 1, 25, 9, 25,
1244 14, 1, 9, 3, 13, 1, 1, 1, 1, 1, 10, 1, 1, 2, 10, 2},
1247 {-20, -1, 0, 2, -2, 1, -1, 3, -3, 1, -1, 4, -4, 0, 2, -2,
1248 1, 5, -1, -5, 6, -6, 1, -1, 7, -7, 1, -1, 3, -3, 8, -8,
1249 2, -2, 1, -1, 9, -9, 1, -1, 10, -10, 4, -4, 11, 1, -11, -1,
1250 2, -2, 1, 12, -12, -1, 13, -13, 1, -1, 3, -3, 14, 5, -14, -5,
1251 -15, 15, -1, 1, 2, -2, 16, -16, 1, 17, -17, -1, 6, -6, 18, -18,
1252 2, -2, -19, 19, -3, 1, 3, -1, 4, 20, -4, 1, -21, 21, 1, 2,
1253 -1, -7, 7, -2, 22, -22, 23, 2, -23, -2, 1, -1, -24, 24, -25, 25,
1254 -8, -26, 26, 8, -27, 27, 5, 3, -3, -5, -4, 28, -28, 4, 29, -29,
1255 1, -1, -2, -30, 30, 2, 9, -9, -31, 31, 2, -2, -32, 3, 32, -33,
1256 -3, 1, 33, -34, -1, 34, -35, 35, -10, 10, -6, 36, 6, -36, 37, -37,
1257 -5, 38, 1, -38, -1, 3, 39, -39, -1, 40, 5, 1, -40, -3, 2, -11,
1258 -41, -2, 1, 11, -3, -4, 41, 3, 42, 4, -1, -43, -42, 43, 1, -44,
1259 45, -1, 44, -45, -7, 7, -46, 1, -12, 2, 1, -47, 46, 12, 47, 48,
1260 -2, -1, -48, 49, -1, -50, -49, 50, -6, -51, 51, 52, -13, 53, -4, 4,
1261 6, 13, -53, -52, -54, 55, 54, -55, -56, -2, 2, -8, 56, 1, -3, -1,
1262 2, 58, 3, 8, -2, 57, -58, -60, -59, -57, -3, 60, 59, -14, 3, 14}
1268 {1, 1, 0, 2, 2, 1, 1, 3, 3, 4, 4, 5, 5, 1, 1, 6,
1269 6, 2, 2, 7, 7, 8, 8, 1, 1, 3, 3, 9, 9, 10, 10, 1,
1270 1, 2, 2, 4, 4, 11, 0, 11, 12, 12, 13, 13, 1, 1, 5, 5,
1271 14, 14, 15, 16, 15, 16, 3, 3, 1, 6, 1, 6, 2, 2, 7, 7,
1272 8, 8, 17, 17, 1, 1, 4, 4, 18, 18, 2, 2, 1, 19, 1, 20,
1273 19, 20, 21, 21, 3, 3, 22, 22, 5, 5, 24, 1, 1, 23, 9, 23,
1274 24, 9, 2, 2, 10, 1, 1, 10, 6, 6, 25, 4, 4, 25, 7, 7,
1275 26, 8, 1, 8, 3, 1, 26, 3, 11, 11, 27, 27, 2, 28, 1, 2,
1276 28, 1, 12, 12, 5, 5, 29, 13, 13, 29, 32, 1, 1, 33, 31, 30,
1277 32, 4, 30, 33, 4, 31, 3, 14, 1, 1, 3, 34, 34, 2, 2, 14,
1278 6, 6, 35, 36, 35, 36, 1, 15, 1, 16, 16, 15, 7, 9, 7, 9,
1279 37, 8, 8, 37, 1, 1, 39, 2, 38, 39, 2, 40, 5, 38, 40, 5,
1280 3, 3, 4, 4, 10, 10, 1, 1, 1, 1, 41, 2, 41, 2, 6, 6,
1281 1, 1, 11, 42, 11, 43, 3, 42, 3, 17, 4, 43, 1, 17, 7, 1,
1282 8, 44, 4, 7, 44, 5, 8, 2, 5, 1, 2, 48, 45, 1, 12, 45,
1283 12, 48, 13, 13, 1, 9, 9, 46, 1, 46, 47, 47, 49, 18, 18, 49},
1286 { 1, -1, 0, 1, -1, 2, -2, 1, -1, 1, -1, 1, -1, 3, -3, 1,
1287 -1, -2, 2, 1, -1, 1, -1, 4, -4, -2, 2, 1, -1, 1, -1, 5,
1288 -5, -3, 3, 2, -2, 1, 0, -1, 1, -1, 1, -1, 6, -6, 2, -2,
1289 1, -1, 1, 1, -1, -1, -3, 3, 7, 2, -7, -2, -4, 4, 2, -2,
1290 2, -2, 1, -1, 8, -8, 3, -3, 1, -1, -5, 5, 9, 1, -9, 1,
1291 -1, -1, 1, -1, -4, 4, 1, -1, 3, -3, 1, -10, 10, 1, 2, -1,
1292 -1, -2, 6, -6, 2, 11, -11, -2, 3, -3, 1, -4, 4, -1, 3, -3,
1293 1, 3, 12, -3, -5, -12, -1, 5, 2, -2, 1, -1, -7, 1, 13, 7,
1294 -1, -13, 2, -2, 4, -4, 1, 2, -2, -1, 1, 14, -14, 1, 1, 1,
1295 -1, -5, -1, -1, 5, -1, -6, 2, -15, 15, 6, 1, -1, -8, 8, -2,
1296 -4, 4, 1, 1, -1, -1, 16, 2, -16, -2, 2, -2, 4, 3, -4, -3,
1297 -1, -4, 4, 1, -17, 17, -1, -9, 1, 1, 9, 1, -5, -1, -1, 5,
1298 -7, 7, 6, -6, 3, -3, 18, -18, 19, -19, 1, -10, -1, 10, -5, 5,
1299 20, -20, -3, 1, 3, 1, 8, -1, -8, 2, 7, -1, -21, -2, 5, 21,
1300 5, -1, -7, -5, 1, -6, -5, -11, 6, 22, 11, 1, 1, -22, -3, -1,
1301 3, -1, 3, -3, -23, 4, -4, 1, 23, -1, 1, -1, 1, -2, 2, -1}
1307 {1, 1, 1, 1, 0, 2, 2, 1, 1, 3, 3, 0, 1, 1, 2, 2,
1308 4, 4, 1, 1, 5, 5, 1, 1, 2, 2, 3, 3, 6, 6, 1, 1,
1309 7, 7, 8, 1, 8, 2, 2, 1, 4, 4, 1, 3, 1, 3, 9, 9,
1310 2, 2, 1, 5, 1, 5, 10, 10, 1, 1, 11, 11, 3, 6, 3, 4,
1311 4, 6, 2, 2, 1, 12, 1, 12, 7, 13, 7, 13, 1, 1, 8, 8,
1312 2, 2, 14, 14, 16, 15, 16, 5, 5, 1, 3, 15, 1, 3, 4, 4,
1313 1, 1, 17, 17, 2, 2, 6, 6, 1, 18, 1, 18, 22, 21, 22, 21,
1314 25, 24, 25, 19, 9, 20, 9, 23, 19, 24, 20, 3, 23, 7, 3, 1,
1315 1, 7, 28, 26, 29, 5, 28, 26, 5, 8, 29, 4, 8, 27, 2, 2,
1316 4, 27, 1, 1, 10, 36, 10, 33, 33, 36, 30, 1, 32, 32, 1, 30,
1317 6, 31, 31, 35, 3, 6, 11, 11, 3, 2, 35, 2, 34, 1, 34, 1,
1318 37, 37, 12, 7, 12, 5, 41, 5, 4, 7, 1, 8, 13, 4, 1, 41,
1319 13, 38, 8, 38, 9, 1, 40, 40, 9, 1, 39, 2, 2, 49, 39, 42,
1320 3, 3, 14, 16, 49, 14, 16, 42, 43, 43, 6, 6, 15, 1, 1, 15,
1321 44, 44, 1, 1, 50, 48, 4, 5, 4, 7, 5, 2, 10, 10, 48, 7,
1322 50, 45, 2, 1, 45, 8, 8, 1, 46, 46, 3, 47, 47, 3, 1, 1},
1325 { 1, -1, 2, -2, 0, 1, -1, 3, -3, 1, -1, 0, 4, -4, 2, -2,
1326 1, -1, 5, -5, 1, -1, 6, -6, 3, -3, 2, -2, 1, -1, 7, -7,
1327 1, -1, 1, 8, -1, 4, -4, -8, 2, -2, 9, 3, -9, -3, 1, -1,
1328 5, -5, 10, 2, -10, -2, 1, -1, 11, -11, 1, -1, -4, 2, 4, 3,
1329 -3, -2, 6, -6, 12, 1, -12, -1, 2, 1, -2, -1, 13, -13, 2, -2,
1330 7, -7, 1, -1, 1, 1, -1, 3, -3, 14, 5, -1, -14, -5, 4, -4,
1331 15, -15, 1, -1, 8, -8, -3, 3, 16, 1, -16, -1, 1, 1, -1, -1,
1332 1, 1, -1, 1, 2, 1, -2, 1, -1, -1, -1, 6, -1, 3, -6, 17,
1333 -17, -3, 1, 1, 1, 4, -1, -1, -4, 3, -1, 5, -3, -1, -9, 9,
1334 -5, 1, 18, -18, 2, 1, -2, 1, -1, -1, 1, 19, -1, 1, -19, -1,
1335 4, 1, -1, 1, 7, -4, -2, 2, -7, 10, -1, -10, 1, 20, -1, -20,
1336 1, -1, 2, 4, -2, 5, 1, -5, 6, -4, 21, 4, 2, -6, -21, -1,
1337 -2, 1, -4, -1, -3, 22, -1, 1, 3, -22, -1, 11, -11, 1, 1, 1,
1338 8, -8, 2, 2, -1, -2, -2, -1, 1, -1, -5, 5, 2, 23, -23, -2,
1339 1, -1, 24, -24, -1, -1, 7, 6, -7, 5, -6, 12, -3, 3, 1, -5,
1340 1, 1, -12, 25, -1, -5, 5, -25, -1, 1, 9, 1, -1, -9, 26, -26}