2 * common functions for Indeo Video Interactive codecs (Indeo4 and Indeo5)
4 * Copyright (c) 2009 Maxim Poliakovski
6 * This file is part of FFmpeg.
8 * FFmpeg is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU Lesser General Public
10 * License as published by the Free Software Foundation; either
11 * version 2.1 of the License, or (at your option) any later version.
13 * FFmpeg is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * Lesser General Public License for more details.
18 * You should have received a copy of the GNU Lesser General Public
19 * License along with FFmpeg; if not, write to the Free Software
20 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
25 * This file contains functions and data shared by both Indeo4 and
29 #define BITSTREAM_READER_LE
30 #include "libavutil/attributes.h"
34 #include "ivi_common.h"
37 extern const IVIHuffDesc ff_ivi_mb_huff_desc[8]; ///< static macroblock huffman tables
38 extern const IVIHuffDesc ff_ivi_blk_huff_desc[8]; ///< static block huffman tables
40 VLC ff_ivi_mb_vlc_tabs [8];
41 VLC ff_ivi_blk_vlc_tabs[8];
44 * Reverse "nbits" bits of the value "val" and return the result
45 * in the least significant bits.
47 static uint16_t inv_bits(uint16_t val, int nbits)
52 res = ff_reverse[val] >> (8-nbits);
54 res = ((ff_reverse[val & 0xFF] << 8) + (ff_reverse[val >> 8])) >> (16-nbits);
59 int ff_ivi_create_huff_from_desc(const IVIHuffDesc *cb, VLC *vlc, int flag)
61 int pos, i, j, codes_per_row, prefix, not_last_row;
62 uint16_t codewords[256]; /* FIXME: move this temporal storage out? */
65 pos = 0; /* current position = 0 */
67 for (i = 0; i < cb->num_rows; i++) {
68 codes_per_row = 1 << cb->xbits[i];
69 not_last_row = (i != cb->num_rows - 1);
70 prefix = ((1 << i) - 1) << (cb->xbits[i] + not_last_row);
72 for (j = 0; j < codes_per_row; j++) {
73 if (pos >= 256) /* Some Indeo5 codebooks can have more than 256 */
74 break; /* elements, but only 256 codes are allowed! */
76 bits[pos] = i + cb->xbits[i] + not_last_row;
77 if (bits[pos] > IVI_VLC_BITS)
78 return -1; /* invalid descriptor */
80 codewords[pos] = inv_bits((prefix | j), bits[pos]);
88 /* number of codewords = pos */
89 return init_vlc(vlc, IVI_VLC_BITS, pos, bits, 1, 1, codewords, 2, 2,
90 (flag ? INIT_VLC_USE_NEW_STATIC : 0) | INIT_VLC_LE);
93 void ff_ivi_init_static_vlc(void)
96 static VLC_TYPE table_data[8192 * 16][2];
97 static int initialized_vlcs = 0;
101 for (i = 0; i < 8; i++) {
102 ff_ivi_mb_vlc_tabs[i].table = table_data + i * 2 * 8192;
103 ff_ivi_mb_vlc_tabs[i].table_allocated = 8192;
104 ff_ivi_create_huff_from_desc(&ff_ivi_mb_huff_desc[i], &ff_ivi_mb_vlc_tabs[i], 1);
105 ff_ivi_blk_vlc_tabs[i].table = table_data + (i * 2 + 1) * 8192;
106 ff_ivi_blk_vlc_tabs[i].table_allocated = 8192;
107 ff_ivi_create_huff_from_desc(&ff_ivi_blk_huff_desc[i], &ff_ivi_blk_vlc_tabs[i], 1);
109 initialized_vlcs = 1;
112 int ff_ivi_dec_huff_desc(GetBitContext *gb, int desc_coded, int which_tab,
113 IVIHuffTab *huff_tab, AVCodecContext *avctx)
116 IVIHuffDesc new_huff;
119 /* select default table */
120 huff_tab->tab = (which_tab) ? &ff_ivi_blk_vlc_tabs[7]
121 : &ff_ivi_mb_vlc_tabs [7];
123 huff_tab->tab_sel = get_bits(gb, 3);
124 if (huff_tab->tab_sel == 7) {
125 /* custom huffman table (explicitly encoded) */
126 new_huff.num_rows = get_bits(gb, 4);
127 if (!new_huff.num_rows) {
128 av_log(avctx, AV_LOG_ERROR, "Empty custom Huffman table!\n");
129 return AVERROR_INVALIDDATA;
132 for (i = 0; i < new_huff.num_rows; i++)
133 new_huff.xbits[i] = get_bits(gb, 4);
135 /* Have we got the same custom table? Rebuild if not. */
136 if (ff_ivi_huff_desc_cmp(&new_huff, &huff_tab->cust_desc) || !huff_tab->cust_tab.table) {
137 ff_ivi_huff_desc_copy(&huff_tab->cust_desc, &new_huff);
139 if (huff_tab->cust_tab.table)
140 ff_free_vlc(&huff_tab->cust_tab);
141 result = ff_ivi_create_huff_from_desc(&huff_tab->cust_desc,
142 &huff_tab->cust_tab, 0);
144 huff_tab->cust_desc.num_rows = 0; // reset faulty description
145 av_log(avctx, AV_LOG_ERROR,
146 "Error while initializing custom vlc table!\n");
150 huff_tab->tab = &huff_tab->cust_tab;
152 /* select one of predefined tables */
153 huff_tab->tab = (which_tab) ? &ff_ivi_blk_vlc_tabs[huff_tab->tab_sel]
154 : &ff_ivi_mb_vlc_tabs [huff_tab->tab_sel];
161 int ff_ivi_huff_desc_cmp(const IVIHuffDesc *desc1, const IVIHuffDesc *desc2)
163 return desc1->num_rows != desc2->num_rows
164 || memcmp(desc1->xbits, desc2->xbits, desc1->num_rows);
167 void ff_ivi_huff_desc_copy(IVIHuffDesc *dst, const IVIHuffDesc *src)
169 dst->num_rows = src->num_rows;
170 memcpy(dst->xbits, src->xbits, src->num_rows);
173 av_cold int ff_ivi_init_planes(IVIPlaneDesc *planes, const IVIPicConfig *cfg)
176 uint32_t b_width, b_height, align_fac, width_aligned, height_aligned, buf_size;
179 ff_ivi_free_buffers(planes);
181 /* fill in the descriptor of the luminance plane */
182 planes[0].width = cfg->pic_width;
183 planes[0].height = cfg->pic_height;
184 planes[0].num_bands = cfg->luma_bands;
186 /* fill in the descriptors of the chrominance planes */
187 planes[1].width = planes[2].width = (cfg->pic_width + 3) >> 2;
188 planes[1].height = planes[2].height = (cfg->pic_height + 3) >> 2;
189 planes[1].num_bands = planes[2].num_bands = cfg->chroma_bands;
191 for (p = 0; p < 3; p++) {
192 planes[p].bands = av_mallocz(planes[p].num_bands * sizeof(IVIBandDesc));
193 if (!planes[p].bands)
194 return AVERROR(ENOMEM);
196 /* select band dimensions: if there is only one band then it
197 * has the full size, if there are several bands each of them
198 * has only half size */
199 b_width = planes[p].num_bands == 1 ? planes[p].width : (planes[p].width + 1) >> 1;
200 b_height = planes[p].num_bands == 1 ? planes[p].height : (planes[p].height + 1) >> 1;
202 /* luma band buffers will be aligned on 16x16 (max macroblock size) */
203 /* chroma band buffers will be aligned on 8x8 (max macroblock size) */
204 align_fac = p ? 8 : 16;
205 width_aligned = FFALIGN(b_width , align_fac);
206 height_aligned = FFALIGN(b_height, align_fac);
207 buf_size = width_aligned * height_aligned * sizeof(int16_t);
209 for (b = 0; b < planes[p].num_bands; b++) {
210 band = &planes[p].bands[b]; /* select appropriate plane/band */
213 band->width = b_width;
214 band->height = b_height;
215 band->pitch = width_aligned;
216 band->aheight = height_aligned;
217 band->bufs[0] = av_mallocz(buf_size);
218 band->bufs[1] = av_mallocz(buf_size);
219 band->bufsize = buf_size/2;
220 if (!band->bufs[0] || !band->bufs[1])
221 return AVERROR(ENOMEM);
223 /* allocate the 3rd band buffer for scalability mode */
224 if (cfg->luma_bands > 1) {
225 band->bufs[2] = av_mallocz(buf_size);
227 return AVERROR(ENOMEM);
230 planes[p].bands[0].blk_vlc.cust_desc.num_rows = 0; /* reset custom vlc */
237 av_cold void ff_ivi_free_buffers(IVIPlaneDesc *planes)
241 for (p = 0; p < 3; p++) {
243 for (b = 0; b < planes[p].num_bands; b++) {
244 av_freep(&planes[p].bands[b].bufs[0]);
245 av_freep(&planes[p].bands[b].bufs[1]);
246 av_freep(&planes[p].bands[b].bufs[2]);
248 if (planes[p].bands[b].blk_vlc.cust_tab.table)
249 ff_free_vlc(&planes[p].bands[b].blk_vlc.cust_tab);
250 for (t = 0; t < planes[p].bands[b].num_tiles; t++)
251 av_freep(&planes[p].bands[b].tiles[t].mbs);
252 av_freep(&planes[p].bands[b].tiles);
254 av_freep(&planes[p].bands);
258 av_cold int ff_ivi_init_tiles(IVIPlaneDesc *planes, int tile_width, int tile_height)
260 int p, b, x, y, x_tiles, y_tiles, t_width, t_height;
262 IVITile *tile, *ref_tile;
264 for (p = 0; p < 3; p++) {
265 t_width = !p ? tile_width : (tile_width + 3) >> 2;
266 t_height = !p ? tile_height : (tile_height + 3) >> 2;
268 if (!p && planes[0].num_bands == 4) {
272 if(t_width<=0 || t_height<=0)
273 return AVERROR(EINVAL);
275 for (b = 0; b < planes[p].num_bands; b++) {
276 band = &planes[p].bands[b];
277 x_tiles = IVI_NUM_TILES(band->width, t_width);
278 y_tiles = IVI_NUM_TILES(band->height, t_height);
279 band->num_tiles = x_tiles * y_tiles;
281 av_freep(&band->tiles);
282 band->tiles = av_mallocz(band->num_tiles * sizeof(IVITile));
284 return AVERROR(ENOMEM);
288 /* use the first luma band as reference for motion vectors
290 ref_tile = planes[0].bands[0].tiles;
292 for (y = 0; y < band->height; y += t_height) {
293 for (x = 0; x < band->width; x += t_width) {
296 tile->mb_size = band->mb_size;
297 tile->width = FFMIN(band->width - x, t_width);
298 tile->height = FFMIN(band->height - y, t_height);
299 tile->is_empty = tile->data_size = 0;
300 /* calculate number of macroblocks */
301 tile->num_MBs = IVI_MBs_PER_TILE(tile->width, tile->height,
304 av_freep(&tile->mbs);
305 tile->mbs = av_malloc(tile->num_MBs * sizeof(IVIMbInfo));
307 return AVERROR(ENOMEM);
311 if (tile->num_MBs <= ref_tile->num_MBs) {
312 tile->ref_mbs = ref_tile->mbs;
314 av_log(NULL, AV_LOG_DEBUG, "Cannot use ref_tile, too few mbs\n");
328 int ff_ivi_dec_tile_data_size(GetBitContext *gb)
334 len = get_bits(gb, 8);
336 len = get_bits_long(gb, 24);
339 /* align the bitstream reader on the byte boundary */
345 int ff_ivi_decode_blocks(GetBitContext *gb, IVIBandDesc *band, IVITile *tile)
347 int mbn, blk, num_blocks, num_coeffs, blk_size, scan_pos, run, val,
348 pos, is_intra, mc_type = 0, mv_x, mv_y, col_mask;
349 uint8_t col_flags[8];
350 int32_t prev_dc, trvec[64];
351 uint32_t cbp, sym, lo, hi, quant, buf_offs, q;
353 RVMapDesc *rvmap = band->rv_map;
354 void (*mc_with_delta_func)(int16_t *buf, const int16_t *ref_buf, uint32_t pitch, int mc_type);
355 void (*mc_no_delta_func) (int16_t *buf, const int16_t *ref_buf, uint32_t pitch, int mc_type);
356 const uint16_t *base_tab;
357 const uint8_t *scale_tab;
359 prev_dc = 0; /* init intra prediction for the DC coefficient */
361 blk_size = band->blk_size;
362 col_mask = blk_size - 1; /* column mask for tracking non-zero coeffs */
363 num_blocks = (band->mb_size != blk_size) ? 4 : 1; /* number of blocks per mb */
364 num_coeffs = blk_size * blk_size;
366 mc_with_delta_func = ff_ivi_mc_8x8_delta;
367 mc_no_delta_func = ff_ivi_mc_8x8_no_delta;
369 mc_with_delta_func = ff_ivi_mc_4x4_delta;
370 mc_no_delta_func = ff_ivi_mc_4x4_no_delta;
373 for (mbn = 0, mb = tile->mbs; mbn < tile->num_MBs; mb++, mbn++) {
374 is_intra = !mb->type;
376 buf_offs = mb->buf_offs;
378 quant = av_clip(band->glob_quant + mb->q_delta, 0, 23);
380 base_tab = is_intra ? band->intra_base : band->inter_base;
381 scale_tab = is_intra ? band->intra_scale : band->inter_scale;
383 quant = scale_tab[quant];
388 if (band->is_halfpel) {
389 mc_type = ((mv_y & 1) << 1) | (mv_x & 1);
391 mv_y >>= 1; /* convert halfpel vectors into fullpel ones */
394 int dmv_x, dmv_y, cx, cy;
396 dmv_x = mb->mv_x >> band->is_halfpel;
397 dmv_y = mb->mv_y >> band->is_halfpel;
398 cx = mb->mv_x & band->is_halfpel;
399 cy = mb->mv_y & band->is_halfpel;
401 if ( mb->xpos + dmv_x < 0
402 || mb->xpos + dmv_x + band->mb_size + cx > band->pitch
403 || mb->ypos + dmv_y < 0
404 || mb->ypos + dmv_y + band->mb_size + cy > band->aheight) {
405 return AVERROR_INVALIDDATA;
410 for (blk = 0; blk < num_blocks; blk++) {
411 /* adjust block position in the buffer according to its number */
413 buf_offs += blk_size;
414 } else if (blk == 2) {
415 buf_offs -= blk_size;
416 buf_offs += blk_size * band->pitch;
419 if (cbp & 1) { /* block coded ? */
421 memset(trvec, 0, num_coeffs*sizeof(trvec[0])); /* zero transform vector */
422 memset(col_flags, 0, sizeof(col_flags)); /* zero column flags */
424 while (scan_pos <= num_coeffs) {
425 sym = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
426 if (sym == rvmap->eob_sym)
427 break; /* End of block */
429 if (sym == rvmap->esc_sym) { /* Escape - run/val explicitly coded using 3 vlc codes */
430 run = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1) + 1;
431 lo = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
432 hi = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
433 val = IVI_TOSIGNED((hi << 6) | lo); /* merge them and convert into signed val */
436 av_log(NULL, AV_LOG_ERROR, "Invalid sym encountered: %d.\n", sym);
439 run = rvmap->runtab[sym];
440 val = rvmap->valtab[sym];
443 /* de-zigzag and dequantize */
445 if (scan_pos >= (unsigned)num_coeffs)
447 pos = band->scan[scan_pos];
450 av_dlog(NULL, "Val = 0 encountered!\n");
452 q = (base_tab[pos] * quant) >> 9;
454 val = val * q + FFSIGN(val) * (((q ^ 1) - 1) >> 1);
456 col_flags[pos & col_mask] |= !!val; /* track columns containing non-zero coeffs */
459 if (scan_pos >= num_coeffs && sym != rvmap->eob_sym)
460 return -1; /* corrupt block data */
462 /* undoing DC coeff prediction for intra-blocks */
463 if (is_intra && band->is_2d_trans) {
466 col_flags[0] |= !!prev_dc;
468 if(band->transform_size > band->blk_size){
469 av_log(NULL, AV_LOG_ERROR, "Too large transform\n");
470 return AVERROR_INVALIDDATA;
472 /* apply inverse transform */
473 band->inv_transform(trvec, band->buf + buf_offs,
474 band->pitch, col_flags);
476 /* apply motion compensation */
478 mc_with_delta_func(band->buf + buf_offs,
479 band->ref_buf + buf_offs + mv_y * band->pitch + mv_x,
480 band->pitch, mc_type);
482 /* block not coded */
483 /* for intra blocks apply the dc slant transform */
484 /* for inter - perform the motion compensation without delta */
486 band->dc_transform(&prev_dc, band->buf + buf_offs,
487 band->pitch, blk_size);
489 mc_no_delta_func(band->buf + buf_offs,
490 band->ref_buf + buf_offs + mv_y * band->pitch + mv_x,
491 band->pitch, mc_type);
504 * Handle empty tiles by performing data copying and motion
505 * compensation respectively.
507 * @param[in] avctx ptr to the AVCodecContext
508 * @param[in] band pointer to the band descriptor
509 * @param[in] tile pointer to the tile descriptor
510 * @param[in] mv_scale scaling factor for motion vectors
512 static int ivi_process_empty_tile(AVCodecContext *avctx, IVIBandDesc *band,
513 IVITile *tile, int32_t mv_scale)
515 int x, y, need_mc, mbn, blk, num_blocks, mv_x, mv_y, mc_type;
516 int offs, mb_offset, row_offset;
517 IVIMbInfo *mb, *ref_mb;
520 void (*mc_no_delta_func)(int16_t *buf, const int16_t *ref_buf, uint32_t pitch,
523 if (tile->num_MBs != IVI_MBs_PER_TILE(tile->width, tile->height, band->mb_size)) {
524 av_log(avctx, AV_LOG_ERROR, "Allocated tile size %d mismatches "
525 "parameters %d in ivi_process_empty_tile()\n",
526 tile->num_MBs, IVI_MBs_PER_TILE(tile->width, tile->height, band->mb_size));
527 return AVERROR_INVALIDDATA;
530 offs = tile->ypos * band->pitch + tile->xpos;
532 ref_mb = tile->ref_mbs;
533 row_offset = band->mb_size * band->pitch;
534 need_mc = 0; /* reset the mc tracking flag */
536 for (y = tile->ypos; y < (tile->ypos + tile->height); y += band->mb_size) {
539 for (x = tile->xpos; x < (tile->xpos + tile->width); x += band->mb_size) {
542 mb->buf_offs = mb_offset;
544 mb->type = 1; /* set the macroblocks type = INTER */
545 mb->cbp = 0; /* all blocks are empty */
547 if (!band->qdelta_present && !band->plane && !band->band_num) {
548 mb->q_delta = band->glob_quant;
553 if (band->inherit_qdelta && ref_mb)
554 mb->q_delta = ref_mb->q_delta;
556 if (band->inherit_mv && ref_mb) {
557 /* motion vector inheritance */
559 mb->mv_x = ivi_scale_mv(ref_mb->mv_x, mv_scale);
560 mb->mv_y = ivi_scale_mv(ref_mb->mv_y, mv_scale);
562 mb->mv_x = ref_mb->mv_x;
563 mb->mv_y = ref_mb->mv_y;
565 need_mc |= mb->mv_x || mb->mv_y; /* tracking non-zero motion vectors */
567 int dmv_x, dmv_y, cx, cy;
569 dmv_x = mb->mv_x >> band->is_halfpel;
570 dmv_y = mb->mv_y >> band->is_halfpel;
571 cx = mb->mv_x & band->is_halfpel;
572 cy = mb->mv_y & band->is_halfpel;
574 if ( mb->xpos + dmv_x < 0
575 || mb->xpos + dmv_x + band->mb_size + cx > band->pitch
576 || mb->ypos + dmv_y < 0
577 || mb->ypos + dmv_y + band->mb_size + cy > band->aheight) {
578 av_log(avctx, AV_LOG_ERROR, "MV out of bounds\n");
579 return AVERROR_INVALIDDATA;
587 mb_offset += band->mb_size;
592 if (band->inherit_mv && need_mc) { /* apply motion compensation if there is at least one non-zero motion vector */
593 num_blocks = (band->mb_size != band->blk_size) ? 4 : 1; /* number of blocks per mb */
594 mc_no_delta_func = (band->blk_size == 8) ? ff_ivi_mc_8x8_no_delta
595 : ff_ivi_mc_4x4_no_delta;
597 for (mbn = 0, mb = tile->mbs; mbn < tile->num_MBs; mb++, mbn++) {
600 if (!band->is_halfpel) {
601 mc_type = 0; /* we have only fullpel vectors */
603 mc_type = ((mv_y & 1) << 1) | (mv_x & 1);
605 mv_y >>= 1; /* convert halfpel vectors into fullpel ones */
608 for (blk = 0; blk < num_blocks; blk++) {
609 /* adjust block position in the buffer according with its number */
610 offs = mb->buf_offs + band->blk_size * ((blk & 1) + !!(blk & 2) * band->pitch);
611 mc_no_delta_func(band->buf + offs,
612 band->ref_buf + offs + mv_y * band->pitch + mv_x,
613 band->pitch, mc_type);
617 /* copy data from the reference tile into the current one */
618 src = band->ref_buf + tile->ypos * band->pitch + tile->xpos;
619 dst = band->buf + tile->ypos * band->pitch + tile->xpos;
620 for (y = 0; y < tile->height; y++) {
621 memcpy(dst, src, tile->width*sizeof(band->buf[0]));
632 static uint16_t ivi_calc_band_checksum(IVIBandDesc *band)
635 int16_t *src, checksum;
640 for (y = 0; y < band->height; src += band->pitch, y++)
641 for (x = 0; x < band->width; x++)
648 void ff_ivi_output_plane(IVIPlaneDesc *plane, uint8_t *dst, int dst_pitch)
651 const int16_t *src = plane->bands[0].buf;
652 uint32_t pitch = plane->bands[0].pitch;
657 for (y = 0; y < plane->height; y++) {
658 for (x = 0; x < plane->width; x++)
659 dst[x] = av_clip_uint8(src[x] + 128);
666 * Decode an Indeo 4 or 5 band.
668 * @param[in,out] ctx ptr to the decoder context
669 * @param[in,out] band ptr to the band descriptor
670 * @param[in] avctx ptr to the AVCodecContext
671 * @return result code: 0 = OK, -1 = error
673 static int decode_band(IVI45DecContext *ctx,
674 IVIBandDesc *band, AVCodecContext *avctx)
676 int result, i, t, idx1, idx2, pos;
679 band->buf = band->bufs[ctx->dst_buf];
681 av_log(avctx, AV_LOG_ERROR, "Band buffer points to no data!\n");
682 return AVERROR_INVALIDDATA;
684 band->ref_buf = band->bufs[ctx->ref_buf];
685 band->data_ptr = ctx->frame_data + (get_bits_count(&ctx->gb) >> 3);
687 result = ctx->decode_band_hdr(ctx, band, avctx);
689 av_log(avctx, AV_LOG_ERROR, "Error while decoding band header: %d\n",
694 if (band->is_empty) {
695 av_log(avctx, AV_LOG_ERROR, "Empty band encountered!\n");
696 return AVERROR_INVALIDDATA;
699 band->rv_map = &ctx->rvmap_tabs[band->rvmap_sel];
701 /* apply corrections to the selected rvmap table if present */
702 for (i = 0; i < band->num_corr; i++) {
703 idx1 = band->corr[i * 2];
704 idx2 = band->corr[i * 2 + 1];
705 FFSWAP(uint8_t, band->rv_map->runtab[idx1], band->rv_map->runtab[idx2]);
706 FFSWAP(int16_t, band->rv_map->valtab[idx1], band->rv_map->valtab[idx2]);
707 if (idx1 == band->rv_map->eob_sym || idx2 == band->rv_map->eob_sym)
708 band->rv_map->eob_sym ^= idx1 ^ idx2;
709 if (idx1 == band->rv_map->esc_sym || idx2 == band->rv_map->esc_sym)
710 band->rv_map->esc_sym ^= idx1 ^ idx2;
713 pos = get_bits_count(&ctx->gb);
715 for (t = 0; t < band->num_tiles; t++) {
716 tile = &band->tiles[t];
718 if (tile->mb_size != band->mb_size) {
719 av_log(avctx, AV_LOG_ERROR, "MB sizes mismatch: %d vs. %d\n",
720 band->mb_size, tile->mb_size);
721 return AVERROR_INVALIDDATA;
723 tile->is_empty = get_bits1(&ctx->gb);
724 if (tile->is_empty) {
725 result = ivi_process_empty_tile(avctx, band, tile,
726 (ctx->planes[0].bands[0].mb_size >> 3) - (band->mb_size >> 3));
729 av_dlog(avctx, "Empty tile encountered!\n");
731 tile->data_size = ff_ivi_dec_tile_data_size(&ctx->gb);
732 if (!tile->data_size) {
733 av_log(avctx, AV_LOG_ERROR, "Tile data size is zero!\n");
734 result = AVERROR_INVALIDDATA;
738 result = ctx->decode_mb_info(ctx, band, tile, avctx);
742 result = ff_ivi_decode_blocks(&ctx->gb, band, tile);
743 if (result < 0 || ((get_bits_count(&ctx->gb) - pos) >> 3) != tile->data_size) {
744 av_log(avctx, AV_LOG_ERROR, "Corrupted tile data encountered!\n");
748 pos += tile->data_size << 3; // skip to next tile
752 /* restore the selected rvmap table by applying its corrections in reverse order */
753 for (i = band->num_corr-1; i >= 0; i--) {
754 idx1 = band->corr[i*2];
755 idx2 = band->corr[i*2+1];
756 FFSWAP(uint8_t, band->rv_map->runtab[idx1], band->rv_map->runtab[idx2]);
757 FFSWAP(int16_t, band->rv_map->valtab[idx1], band->rv_map->valtab[idx2]);
758 if (idx1 == band->rv_map->eob_sym || idx2 == band->rv_map->eob_sym)
759 band->rv_map->eob_sym ^= idx1 ^ idx2;
760 if (idx1 == band->rv_map->esc_sym || idx2 == band->rv_map->esc_sym)
761 band->rv_map->esc_sym ^= idx1 ^ idx2;
765 if (band->checksum_present) {
766 uint16_t chksum = ivi_calc_band_checksum(band);
767 if (chksum != band->checksum) {
768 av_log(avctx, AV_LOG_ERROR,
769 "Band checksum mismatch! Plane %d, band %d, received: %x, calculated: %x\n",
770 band->plane, band->band_num, band->checksum, chksum);
775 align_get_bits(&ctx->gb);
780 int ff_ivi_decode_frame(AVCodecContext *avctx, void *data, int *data_size,
783 IVI45DecContext *ctx = avctx->priv_data;
784 const uint8_t *buf = avpkt->data;
785 int buf_size = avpkt->size;
788 init_get_bits(&ctx->gb, buf, buf_size * 8);
789 ctx->frame_data = buf;
790 ctx->frame_size = buf_size;
792 result = ctx->decode_pic_hdr(ctx, avctx);
794 av_log(avctx, AV_LOG_ERROR,
795 "Error while decoding picture header: %d\n", result);
798 if (ctx->gop_invalid)
799 return AVERROR_INVALIDDATA;
801 if (ctx->gop_flags & IVI5_IS_PROTECTED) {
802 av_log(avctx, AV_LOG_ERROR, "Password-protected clip!\n");
806 ctx->switch_buffers(ctx);
810 if (ctx->is_nonnull_frame(ctx)) {
811 ctx->buf_invalid[ctx->dst_buf] = 1;
812 for (p = 0; p < 3; p++) {
813 for (b = 0; b < ctx->planes[p].num_bands; b++) {
814 result = decode_band(ctx, &ctx->planes[p].bands[b], avctx);
816 av_log(avctx, AV_LOG_ERROR,
817 "Error while decoding band: %d, plane: %d\n", b, p);
822 ctx->buf_invalid[ctx->dst_buf] = 0;
824 if (ctx->buf_invalid[ctx->dst_buf])
827 //STOP_TIMER("decode_planes"); }
829 /* If the bidirectional mode is enabled, next I and the following P frame will */
830 /* be sent together. Unfortunately the approach below seems to be the only way */
831 /* to handle the B-frames mode. That's exactly the same Intel decoders do. */
832 if (avctx->codec_id == AV_CODEC_ID_INDEO4 && ctx->frame_type == 0/*FRAMETYPE_INTRA*/) {
833 while (get_bits(&ctx->gb, 8)); // skip version string
834 skip_bits_long(&ctx->gb, 64); // skip padding, TODO: implement correct 8-bytes alignment
835 if (get_bits_left(&ctx->gb) > 18 && show_bits(&ctx->gb, 18) == 0x3FFF8)
836 av_log(avctx, AV_LOG_ERROR, "Buffer contains IP frames!\n");
839 if (!ctx->is_nonnull_frame(ctx))
842 if (ctx->frame.data[0])
843 avctx->release_buffer(avctx, &ctx->frame);
845 ctx->frame.reference = 0;
846 avcodec_set_dimensions(avctx, ctx->planes[0].width, ctx->planes[0].height);
847 if ((result = avctx->get_buffer(avctx, &ctx->frame)) < 0) {
848 av_log(avctx, AV_LOG_ERROR, "get_buffer() failed\n");
852 if (ctx->is_scalable) {
853 if (avctx->codec_id == AV_CODEC_ID_INDEO4)
854 ff_ivi_recompose_haar(&ctx->planes[0], ctx->frame.data[0], ctx->frame.linesize[0]);
856 ff_ivi_recompose53 (&ctx->planes[0], ctx->frame.data[0], ctx->frame.linesize[0]);
858 ff_ivi_output_plane(&ctx->planes[0], ctx->frame.data[0], ctx->frame.linesize[0]);
861 ff_ivi_output_plane(&ctx->planes[2], ctx->frame.data[1], ctx->frame.linesize[1]);
862 ff_ivi_output_plane(&ctx->planes[1], ctx->frame.data[2], ctx->frame.linesize[2]);
864 *data_size = sizeof(AVFrame);
865 *(AVFrame*)data = ctx->frame;
871 * Close Indeo5 decoder and clean up its context.
873 av_cold int ff_ivi_decode_close(AVCodecContext *avctx)
875 IVI45DecContext *ctx = avctx->priv_data;
877 ff_ivi_free_buffers(&ctx->planes[0]);
879 if (ctx->mb_vlc.cust_tab.table)
880 ff_free_vlc(&ctx->mb_vlc.cust_tab);
882 if (ctx->frame.data[0])
883 avctx->release_buffer(avctx, &ctx->frame);
885 #if IVI4_STREAM_ANALYSER
886 if (avctx->codec_id == AV_CODEC_ID_INDEO4) {
887 if (ctx->is_scalable)
888 av_log(avctx, AV_LOG_ERROR, "This video uses scalability mode!\n");
889 if (ctx->uses_tiling)
890 av_log(avctx, AV_LOG_ERROR, "This video uses local decoding!\n");
891 if (ctx->has_b_frames)
892 av_log(avctx, AV_LOG_ERROR, "This video contains B-frames!\n");
894 av_log(avctx, AV_LOG_ERROR, "Transparency mode is enabled!\n");
896 av_log(avctx, AV_LOG_ERROR, "This video uses Haar transform!\n");
897 if (ctx->uses_fullpel)
898 av_log(avctx, AV_LOG_ERROR, "This video uses fullpel motion vectors!\n");
907 * These are 2x8 predefined Huffman codebooks for coding macroblock/block
908 * signals. They are specified using "huffman descriptors" in order to
909 * avoid huge static tables. The decoding tables will be generated at
910 * startup from these descriptors.
912 const IVIHuffDesc ff_ivi_mb_huff_desc[8] = {
913 {8, {0, 4, 5, 4, 4, 4, 6, 6}},
914 {12, {0, 2, 2, 3, 3, 3, 3, 5, 3, 2, 2, 2}},
915 {12, {0, 2, 3, 4, 3, 3, 3, 3, 4, 3, 2, 2}},
916 {12, {0, 3, 4, 4, 3, 3, 3, 3, 3, 2, 2, 2}},
917 {13, {0, 4, 4, 3, 3, 3, 3, 2, 3, 3, 2, 1, 1}},
918 {9, {0, 4, 4, 4, 4, 3, 3, 3, 2}},
919 {10, {0, 4, 4, 4, 4, 3, 3, 2, 2, 2}},
920 {12, {0, 4, 4, 4, 3, 3, 2, 3, 2, 2, 2, 2}}
923 const IVIHuffDesc ff_ivi_blk_huff_desc[8] = {
924 {10, {1, 2, 3, 4, 4, 7, 5, 5, 4, 1}},
925 {11, {2, 3, 4, 4, 4, 7, 5, 4, 3, 3, 2}},
926 {12, {2, 4, 5, 5, 5, 5, 6, 4, 4, 3, 1, 1}},
927 {13, {3, 3, 4, 4, 5, 6, 6, 4, 4, 3, 2, 1, 1}},
928 {11, {3, 4, 4, 5, 5, 5, 6, 5, 4, 2, 2}},
929 {13, {3, 4, 5, 5, 5, 5, 6, 4, 3, 3, 2, 1, 1}},
930 {13, {3, 4, 5, 5, 5, 6, 5, 4, 3, 3, 2, 1, 1}},
931 {9, {3, 4, 4, 5, 5, 5, 6, 5, 5}}
936 * Scan patterns shared between indeo4 and indeo5
938 const uint8_t ff_ivi_vertical_scan_8x8[64] = {
939 0, 8, 16, 24, 32, 40, 48, 56,
940 1, 9, 17, 25, 33, 41, 49, 57,
941 2, 10, 18, 26, 34, 42, 50, 58,
942 3, 11, 19, 27, 35, 43, 51, 59,
943 4, 12, 20, 28, 36, 44, 52, 60,
944 5, 13, 21, 29, 37, 45, 53, 61,
945 6, 14, 22, 30, 38, 46, 54, 62,
946 7, 15, 23, 31, 39, 47, 55, 63
949 const uint8_t ff_ivi_horizontal_scan_8x8[64] = {
950 0, 1, 2, 3, 4, 5, 6, 7,
951 8, 9, 10, 11, 12, 13, 14, 15,
952 16, 17, 18, 19, 20, 21, 22, 23,
953 24, 25, 26, 27, 28, 29, 30, 31,
954 32, 33, 34, 35, 36, 37, 38, 39,
955 40, 41, 42, 43, 44, 45, 46, 47,
956 48, 49, 50, 51, 52, 53, 54, 55,
957 56, 57, 58, 59, 60, 61, 62, 63
960 const uint8_t ff_ivi_direct_scan_4x4[16] = {
961 0, 1, 4, 8, 5, 2, 3, 6, 9, 12, 13, 10, 7, 11, 14, 15
966 * Run-value (RLE) tables.
968 const RVMapDesc ff_ivi_rvmap_tabs[9] = {
973 {1, 1, 0, 1, 1, 0, 1, 1, 2, 2, 1, 1, 1, 1, 3, 3,
974 1, 1, 2, 2, 1, 1, 4, 4, 1, 1, 1, 1, 2, 2, 5, 5,
975 1, 1, 3, 3, 1, 1, 6, 6, 1, 2, 1, 2, 7, 7, 1, 1,
976 8, 8, 1, 1, 4, 2, 1, 4, 2, 1, 3, 3, 1, 1, 1, 9,
977 9, 1, 2, 1, 2, 1, 5, 5, 1, 1, 10, 10, 1, 1, 3, 3,
978 2, 2, 1, 1, 11, 11, 6, 4, 4, 1, 6, 1, 2, 1, 2, 12,
979 8, 1, 12, 7, 8, 7, 1, 16, 1, 16, 1, 3, 3, 13, 1, 13,
980 2, 2, 1, 15, 1, 5, 14, 15, 1, 5, 14, 1, 17, 8, 17, 8,
981 1, 4, 4, 2, 2, 1, 25, 25, 24, 24, 1, 3, 1, 3, 1, 8,
982 6, 7, 6, 1, 18, 8, 18, 1, 7, 23, 2, 2, 23, 1, 1, 21,
983 22, 9, 9, 22, 19, 1, 21, 5, 19, 5, 1, 33, 20, 33, 20, 8,
984 4, 4, 1, 32, 2, 2, 8, 3, 32, 26, 3, 1, 7, 7, 26, 6,
985 1, 6, 1, 1, 16, 1, 10, 1, 10, 2, 16, 29, 28, 2, 29, 28,
986 1, 27, 5, 8, 5, 27, 1, 8, 3, 7, 3, 31, 41, 31, 1, 41,
987 6, 1, 6, 7, 4, 4, 1, 1, 2, 1, 2, 11, 34, 30, 11, 1,
988 30, 15, 15, 34, 36, 40, 36, 40, 35, 35, 37, 37, 39, 39, 38, 38},
991 { 1, -1, 0, 2, -2, 0, 3, -3, 1, -1, 4, -4, 5, -5, 1, -1,
992 6, -6, 2, -2, 7, -7, 1, -1, 8, -8, 9, -9, 3, -3, 1, -1,
993 10, -10, 2, -2, 11, -11, 1, -1, 12, 4, -12, -4, 1, -1, 13, -13,
994 1, -1, 14, -14, 2, 5, 15, -2, -5, -15, -3, 3, 16, -16, 17, 1,
995 -1, -17, 6, 18, -6, -18, 2, -2, 19, -19, 1, -1, 20, -20, 4, -4,
996 7, -7, 21, -21, 1, -1, 2, 3, -3, 22, -2, -22, 8, 23, -8, 1,
997 2, -23, -1, 2, -2, -2, 24, 1, -24, -1, 25, 5, -5, 1, -25, -1,
998 9, -9, 26, 1, -26, 3, 1, -1, 27, -3, -1, -27, 1, 3, -1, -3,
999 28, -4, 4, 10, -10, -28, 1, -1, 1, -1, 29, 6, -29, -6, 30, -4,
1000 3, 3, -3, -30, 1, 4, -1, 31, -3, 1, 11, -11, -1, -31, 32, -1,
1001 -1, 2, -2, 1, 1, -32, 1, 4, -1, -4, 33, -1, 1, 1, -1, 5,
1002 5, -5, -33, -1, -12, 12, -5, -7, 1, 1, 7, 34, 4, -4, -1, 4,
1003 -34, -4, 35, 36, -2, -35, -2, -36, 2, 13, 2, -1, 1, -13, 1, -1,
1004 37, 1, -5, 6, 5, -1, 38, -6, -8, 5, 8, -1, 1, 1, -37, -1,
1005 5, 39, -5, -5, 6, -6, -38, -39, -14, 40, 14, 2, 1, 1, -2, -40,
1006 -1, -2, 2, -1, -1, -1, 1, 1, 1, -1, 1, -1, 1, -1, 1, -1}
1012 {0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 8, 6, 8, 7,
1013 7, 9, 9, 10, 10, 11, 11, 1, 12, 1, 12, 13, 13, 16, 14, 16,
1014 14, 15, 15, 17, 17, 18, 0, 18, 19, 20, 21, 19, 22, 21, 20, 22,
1015 25, 24, 2, 25, 24, 23, 23, 2, 26, 28, 26, 28, 29, 27, 29, 27,
1016 33, 33, 1, 32, 1, 3, 32, 30, 36, 3, 36, 30, 31, 31, 35, 34,
1017 37, 41, 34, 35, 37, 4, 41, 4, 49, 8, 8, 49, 40, 38, 5, 38,
1018 40, 39, 5, 39, 42, 43, 42, 7, 57, 6, 43, 44, 6, 50, 7, 44,
1019 57, 48, 50, 48, 45, 45, 46, 47, 51, 46, 47, 58, 1, 51, 58, 1,
1020 52, 59, 53, 9, 52, 55, 55, 59, 53, 56, 54, 56, 54, 9, 64, 64,
1021 60, 63, 60, 63, 61, 62, 61, 62, 2, 10, 2, 10, 11, 1, 11, 13,
1022 12, 1, 12, 13, 16, 16, 8, 8, 14, 3, 3, 15, 14, 15, 4, 4,
1023 1, 17, 17, 5, 1, 7, 7, 5, 6, 1, 2, 2, 6, 22, 1, 25,
1024 21, 22, 8, 24, 1, 21, 25, 24, 8, 18, 18, 23, 9, 20, 23, 33,
1025 29, 33, 20, 1, 19, 1, 29, 36, 9, 36, 19, 41, 28, 57, 32, 3,
1026 28, 3, 1, 27, 49, 49, 1, 32, 26, 26, 2, 4, 4, 7, 57, 41,
1027 2, 7, 10, 5, 37, 16, 10, 27, 8, 8, 13, 16, 37, 13, 1, 5},
1030 {0, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, 1, -1, -1, 1,
1031 -1, 1, -1, 1, -1, 1, -1, 2, 1, -2, -1, 1, -1, 1, 1, -1,
1032 -1, 1, -1, 1, -1, 1, 0, -1, 1, 1, 1, -1, 1, -1, -1, -1,
1033 1, 1, 2, -1, -1, 1, -1, -2, 1, 1, -1, -1, 1, 1, -1, -1,
1034 1, -1, 3, 1, -3, 2, -1, 1, 1, -2, -1, -1, -1, 1, 1, 1,
1035 1, 1, -1, -1, -1, 2, -1, -2, 1, 2, -2, -1, 1, 1, 2, -1,
1036 -1, 1, -2, -1, 1, 1, -1, 2, 1, 2, -1, 1, -2, -1, -2, -1,
1037 -1, 1, 1, -1, 1, -1, 1, 1, 1, -1, -1, 1, 4, -1, -1, -4,
1038 1, 1, 1, 2, -1, -1, 1, -1, -1, 1, -1, -1, 1, -2, 1, -1,
1039 1, 1, -1, -1, 1, 1, -1, -1, 3, 2, -3, -2, 2, 5, -2, 2,
1040 2, -5, -2, -2, -2, 2, -3, 3, 2, 3, -3, 2, -2, -2, 3, -3,
1041 6, 2, -2, 3, -6, 3, -3, -3, 3, 7, -4, 4, -3, 2, -7, 2,
1042 2, -2, -4, 2, 8, -2, -2, -2, 4, 2, -2, 2, 3, 2, -2, -2,
1043 2, 2, -2, -8, -2, 9, -2, 2, -3, -2, 2, -2, 2, 2, 2, 4,
1044 -2, -4, 10, 2, 2, -2, -9, -2, 2, -2, 5, 4, -4, 4, -2, 2,
1045 -5, -4, -3, 4, 2, -3, 3, -2, -5, 5, 3, 3, -2, -3, -10, -4}
1051 {1, 1, 0, 2, 2, 1, 1, 3, 3, 4, 4, 0, 1, 1, 5, 5,
1052 2, 2, 6, 6, 7, 7, 1, 8, 1, 8, 3, 3, 9, 9, 1, 2,
1053 2, 1, 4, 10, 4, 10, 11, 11, 1, 5, 12, 12, 1, 5, 13, 13,
1054 3, 3, 6, 6, 2, 2, 14, 14, 16, 16, 15, 7, 15, 8, 8, 7,
1055 1, 1, 17, 17, 4, 4, 1, 1, 18, 18, 2, 2, 5, 5, 25, 3,
1056 9, 3, 25, 9, 19, 24, 19, 24, 1, 21, 20, 1, 21, 22, 20, 22,
1057 23, 23, 8, 6, 33, 6, 8, 33, 7, 7, 26, 26, 1, 32, 1, 32,
1058 28, 4, 28, 10, 29, 27, 27, 10, 41, 4, 29, 2, 2, 41, 36, 31,
1059 49, 31, 34, 30, 34, 36, 30, 35, 1, 49, 11, 5, 35, 11, 1, 3,
1060 3, 5, 37, 37, 8, 40, 8, 40, 12, 12, 42, 42, 1, 38, 16, 57,
1061 1, 6, 16, 39, 38, 6, 7, 7, 13, 13, 39, 43, 2, 43, 57, 2,
1062 50, 9, 44, 9, 50, 4, 15, 48, 44, 4, 1, 15, 48, 14, 14, 1,
1063 45, 45, 8, 3, 5, 8, 51, 47, 3, 46, 46, 47, 5, 51, 1, 17,
1064 17, 58, 1, 58, 2, 52, 52, 2, 53, 7, 59, 6, 6, 56, 53, 55,
1065 7, 55, 1, 54, 59, 56, 54, 10, 1, 10, 4, 60, 1, 60, 8, 4,
1066 8, 64, 64, 61, 1, 63, 3, 63, 62, 61, 5, 11, 5, 3, 11, 62},
1069 { 1, -1, 0, 1, -1, 2, -2, 1, -1, 1, -1, 0, 3, -3, 1, -1,
1070 2, -2, 1, -1, 1, -1, 4, 1, -4, -1, 2, -2, 1, -1, 5, 3,
1071 -3, -5, 2, 1, -2, -1, 1, -1, 6, 2, 1, -1, -6, -2, 1, -1,
1072 3, -3, 2, -2, 4, -4, 1, -1, 1, -1, 1, 2, -1, 2, -2, -2,
1073 7, -7, 1, -1, 3, -3, 8, -8, 1, -1, 5, -5, 3, -3, 1, 4,
1074 2, -4, -1, -2, 1, 1, -1, -1, 9, 1, 1, -9, -1, 1, -1, -1,
1075 1, -1, 3, -3, 1, 3, -3, -1, 3, -3, 1, -1, 10, 1, -10, -1,
1076 1, 4, -1, 2, 1, -1, 1, -2, 1, -4, -1, 6, -6, -1, 1, 1,
1077 1, -1, 1, 1, -1, -1, -1, 1, 11, -1, -2, 4, -1, 2, -11, 5,
1078 -5, -4, -1, 1, 4, 1, -4, -1, -2, 2, 1, -1, 12, 1, -2, 1,
1079 -12, 4, 2, 1, -1, -4, 4, -4, 2, -2, -1, 1, 7, -1, -1, -7,
1080 -1, -3, 1, 3, 1, 5, 2, 1, -1, -5, 13, -2, -1, 2, -2, -13,
1081 1, -1, 5, 6, 5, -5, 1, 1, -6, 1, -1, -1, -5, -1, 14, 2,
1082 -2, 1, -14, -1, 8, 1, -1, -8, 1, 5, 1, 5, -5, 1, -1, 1,
1083 -5, -1, 15, 1, -1, -1, -1, 3, -15, -3, 6, 1, 16, -1, 6, -6,
1084 -6, 1, -1, 1, -16, 1, 7, -1, 1, -1, -6, -3, 6, -7, 3, -1}
1090 {0, 1, 1, 2, 2, 3, 3, 4, 4, 1, 1, 5, 5, 6, 6, 7,
1091 7, 8, 8, 9, 9, 2, 2, 10, 10, 1, 1, 11, 11, 12, 12, 3,
1092 3, 13, 13, 0, 14, 14, 16, 15, 16, 15, 4, 4, 17, 1, 17, 1,
1093 5, 5, 18, 18, 2, 2, 6, 6, 8, 19, 7, 8, 7, 19, 20, 20,
1094 21, 21, 22, 24, 22, 24, 23, 23, 1, 1, 25, 25, 3, 3, 26, 26,
1095 9, 9, 27, 27, 28, 28, 33, 29, 4, 33, 29, 1, 4, 1, 32, 32,
1096 2, 2, 31, 10, 30, 10, 30, 31, 34, 34, 5, 5, 36, 36, 35, 41,
1097 35, 11, 41, 11, 37, 1, 8, 8, 37, 6, 1, 6, 40, 7, 7, 40,
1098 12, 38, 12, 39, 39, 38, 49, 13, 49, 13, 3, 42, 3, 42, 16, 16,
1099 43, 43, 14, 14, 1, 1, 44, 15, 44, 15, 2, 2, 57, 48, 50, 48,
1100 57, 50, 4, 45, 45, 4, 46, 47, 47, 46, 1, 51, 1, 17, 17, 51,
1101 8, 9, 9, 5, 58, 8, 58, 5, 52, 52, 55, 56, 53, 56, 55, 59,
1102 59, 53, 54, 1, 6, 54, 7, 7, 6, 1, 2, 3, 2, 3, 64, 60,
1103 60, 10, 10, 64, 61, 62, 61, 63, 1, 63, 62, 1, 18, 24, 18, 4,
1104 25, 4, 8, 21, 21, 1, 24, 22, 25, 22, 8, 11, 19, 11, 23, 1,
1105 20, 23, 19, 20, 5, 12, 5, 1, 16, 2, 12, 13, 2, 13, 1, 16},
1108 { 0, 1, -1, 1, -1, 1, -1, 1, -1, 2, -2, 1, -1, 1, -1, 1,
1109 -1, 1, -1, 1, -1, 2, -2, 1, -1, 3, -3, 1, -1, 1, -1, 2,
1110 -2, 1, -1, 0, 1, -1, 1, 1, -1, -1, 2, -2, 1, 4, -1, -4,
1111 2, -2, 1, -1, -3, 3, 2, -2, 2, 1, 2, -2, -2, -1, 1, -1,
1112 1, -1, 1, 1, -1, -1, 1, -1, 5, -5, 1, -1, 3, -3, 1, -1,
1113 2, -2, 1, -1, 1, -1, 1, 1, 3, -1, -1, 6, -3, -6, -1, 1,
1114 4, -4, 1, 2, 1, -2, -1, -1, 1, -1, 3, -3, 1, -1, 1, 1,
1115 -1, 2, -1, -2, 1, 7, -3, 3, -1, 3, -7, -3, 1, -3, 3, -1,
1116 2, 1, -2, 1, -1, -1, 1, 2, -1, -2, -4, -1, 4, 1, 2, -2,
1117 1, -1, -2, 2, 8, -8, -1, 2, 1, -2, -5, 5, 1, -1, -1, 1,
1118 -1, 1, 4, -1, 1, -4, -1, -1, 1, 1, 9, 1, -9, 2, -2, -1,
1119 -4, 3, -3, -4, -1, 4, 1, 4, 1, -1, 1, -1, 1, 1, -1, 1,
1120 -1, -1, -1, 10, 4, 1, 4, -4, -4, -10, 6, 5, -6, -5, 1, -1,
1121 1, 3, -3, -1, 1, -1, -1, -1, 11, 1, 1, -11, -2, -2, 2, 5,
1122 -2, -5, -5, 2, -2, 12, 2, -2, 2, 2, 5, -3, -2, 3, -2, -12,
1123 -2, 2, 2, 2, -5, 3, 5, 13, -3, 7, -3, -3, -7, 3, -13, 3}
1129 {0, 1, 1, 1, 2, 2, 1, 3, 3, 1, 1, 1, 4, 4, 1, 5,
1130 2, 1, 5, 2, 1, 1, 6, 6, 1, 1, 1, 1, 1, 7, 3, 1,
1131 2, 3, 0, 1, 2, 7, 1, 1, 1, 8, 1, 1, 8, 1, 1, 1,
1132 9, 1, 9, 1, 2, 1, 1, 2, 1, 1, 10, 4, 1, 10, 1, 4,
1133 1, 1, 1, 1, 1, 3, 1, 1, 1, 3, 2, 1, 5, 1, 1, 1,
1134 2, 5, 1, 11, 1, 11, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1135 2, 1, 6, 1, 6, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 12,
1136 3, 1, 12, 1, 1, 1, 2, 1, 1, 3, 1, 1, 1, 1, 1, 1,
1137 4, 1, 1, 1, 2, 1, 1, 4, 1, 1, 1, 1, 1, 1, 2, 1,
1138 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 2, 1, 1, 5,
1139 1, 1, 1, 1, 1, 7, 1, 7, 1, 1, 2, 3, 1, 1, 1, 1,
1140 5, 1, 1, 1, 1, 1, 1, 2, 13, 1, 1, 1, 1, 1, 1, 1,
1141 1, 1, 1, 1, 1, 1, 1, 1, 13, 2, 1, 1, 4, 1, 1, 1,
1142 3, 1, 6, 1, 1, 1, 14, 1, 1, 1, 1, 1, 14, 6, 1, 1,
1143 1, 1, 15, 2, 4, 1, 2, 3, 15, 1, 1, 1, 8, 1, 1, 8,
1144 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1},
1147 { 0, 1, -1, 2, 1, -1, -2, 1, -1, 3, -3, 4, 1, -1, -4, 1,
1148 2, 5, -1, -2, -5, 6, 1, -1, -6, 7, -7, 8, -8, 1, 2, 9,
1149 3, -2, 0, -9, -3, -1, 10, -10, 11, 1, -11, 12, -1, -12, 13, -13,
1150 1, 14, -1, -14, 4, 15, -15, -4, 16, -16, 1, 2, 17, -1, -17, -2,
1151 18, -18, 19, -19, 20, 3, -20, 21, -21, -3, 5, 22, 2, -22, -23, 23,
1152 -5, -2, 24, 1, -24, -1, 25, -25, 26, -26, -27, 27, 28, 29, -28, -29,
1153 6, 30, 2, -31, -2, -30, 31, -6, -32, 32, 33, -33, 34, -35, -34, 1,
1154 4, -36, -1, 35, 37, 36, 7, -37, 38, -4, -38, 39, 41, 40, -40, -39,
1155 3, 42, -43, -41, -7, -42, 43, -3, 44, -44, 45, -45, 46, 47, 8, -47,
1156 -48, -46, 50, -50, 48, 49, 51, -49, 52, -52, 5, -51, -8, -53, 53, 3,
1157 -56, 56, 55, 54, -54, 2, 60, -2, -55, 58, 9, -5, 59, 57, -57, -63,
1158 -3, -58, -60, -61, 61, -59, -62, -9, 1, 64, 62, 69, -64, 63, 65, -67,
1159 -68, 66, -65, 68, -66, -69, 67, -70, -1, 10, 71, -71, 4, 73, 72, 70,
1160 6, -76, -3, 74, -78, -74, 1, 78, 80, -72, -75, 76, -1, 3, -73, 79,
1161 75, 77, 1, 11, -4, -79, -10, -6, -1, -77, -83, -80, 2, 81, -84, -2,
1162 83, -81, 82, -82, 84, -87, -86, 85, -11, -85, 86, -89, 87, -88, 88, 89}
1168 {1, 1, 0, 2, 1, 2, 1, 3, 3, 1, 1, 4, 4, 2, 2, 1,
1169 1, 5, 5, 6, 1, 6, 1, 7, 7, 3, 3, 2, 8, 2, 8, 1,
1170 1, 0, 9, 9, 1, 1, 10, 4, 10, 4, 11, 11, 2, 1, 2, 1,
1171 12, 12, 3, 3, 1, 1, 13, 5, 5, 13, 14, 1, 1, 14, 2, 2,
1172 6, 6, 15, 1, 1, 15, 16, 4, 7, 16, 4, 7, 1, 1, 3, 3,
1173 8, 8, 2, 2, 1, 1, 17, 17, 1, 1, 18, 18, 5, 5, 2, 2,
1174 1, 1, 9, 19, 9, 19, 20, 3, 3, 20, 1, 10, 21, 1, 10, 4,
1175 4, 21, 22, 6, 6, 22, 1, 1, 23, 24, 2, 2, 23, 24, 11, 1,
1176 1, 11, 7, 25, 7, 1, 1, 25, 8, 8, 3, 26, 3, 1, 12, 2,
1177 2, 26, 1, 12, 5, 5, 27, 4, 1, 4, 1, 27, 28, 1, 28, 13,
1178 1, 13, 2, 29, 2, 1, 32, 6, 1, 30, 14, 29, 14, 6, 3, 31,
1179 3, 1, 30, 1, 32, 31, 33, 9, 33, 1, 1, 7, 9, 7, 2, 2,
1180 1, 1, 4, 36, 34, 4, 5, 10, 10, 5, 34, 1, 1, 35, 8, 8,
1181 36, 3, 35, 1, 15, 3, 2, 1, 16, 15, 16, 2, 37, 1, 37, 1,
1182 1, 1, 6, 6, 38, 1, 38, 11, 1, 39, 39, 40, 11, 2, 41, 4,
1183 40, 1, 2, 4, 1, 1, 1, 41, 3, 1, 3, 1, 5, 7, 5, 7},
1186 { 1, -1, 0, 1, 2, -1, -2, 1, -1, 3, -3, 1, -1, 2, -2, 4,
1187 -4, 1, -1, 1, 5, -1, -5, 1, -1, 2, -2, 3, 1, -3, -1, 6,
1188 -6, 0, 1, -1, 7, -7, 1, 2, -1, -2, 1, -1, 4, 8, -4, -8,
1189 1, -1, 3, -3, 9, -9, 1, 2, -2, -1, 1, 10, -10, -1, 5, -5,
1190 2, -2, 1, 11, -11, -1, 1, 3, 2, -1, -3, -2, 12, -12, 4, -4,
1191 2, -2, -6, 6, 13, -13, 1, -1, 14, -14, 1, -1, 3, -3, 7, -7,
1192 15, -15, 2, 1, -2, -1, 1, 5, -5, -1, -16, 2, 1, 16, -2, 4,
1193 -4, -1, 1, 3, -3, -1, 17, -17, 1, 1, -8, 8, -1, -1, 2, 18,
1194 -18, -2, 3, 1, -3, 19, -19, -1, 3, -3, 6, 1, -6, 20, 2, 9,
1195 -9, -1, -20, -2, 4, -4, 1, -5, 21, 5, -21, -1, 1, -22, -1, 2,
1196 22, -2, 10, 1, -10, 23, 1, 4, -23, 1, 2, -1, -2, -4, -7, 1,
1197 7, -24, -1, 24, -1, -1, 1, 3, -1, -25, 25, 4, -3, -4, 11, -11,
1198 26, -26, 6, 1, 1, -6, -5, -3, 3, 5, -1, -27, 27, 1, 4, -4,
1199 -1, -8, -1, 28, 2, 8, -12, -28, -2, -2, 2, 12, -1, 29, 1, -29,
1200 30, -30, 5, -5, 1, -31, -1, 3, 31, -1, 1, 1, -3, -13, 1, -7,
1201 -1, -32, 13, 7, 32, 33, -33, -1, -9, -34, 9, 34, -6, 5, 6, -5}
1207 {1, 1, 0, 1, 1, 2, 2, 1, 1, 3, 3, 1, 1, 0, 2, 2,
1208 4, 1, 4, 1, 1, 1, 5, 5, 1, 1, 6, 6, 2, 2, 1, 1,
1209 3, 3, 7, 7, 1, 1, 8, 8, 1, 1, 2, 2, 1, 9, 1, 9,
1210 4, 4, 10, 1, 1, 10, 1, 1, 11, 11, 3, 3, 1, 2, 1, 2,
1211 1, 1, 12, 12, 5, 5, 1, 1, 13, 1, 1, 13, 2, 2, 1, 1,
1212 6, 6, 1, 1, 4, 14, 4, 14, 3, 1, 3, 1, 1, 1, 15, 7,
1213 15, 2, 2, 7, 1, 1, 1, 8, 1, 8, 16, 16, 1, 1, 1, 1,
1214 2, 1, 1, 2, 1, 1, 3, 5, 5, 3, 4, 1, 1, 4, 1, 1,
1215 17, 17, 9, 1, 1, 9, 2, 2, 1, 1, 10, 10, 1, 6, 1, 1,
1216 6, 18, 1, 1, 18, 1, 1, 1, 2, 2, 3, 1, 3, 1, 1, 1,
1217 4, 1, 19, 1, 19, 7, 1, 1, 20, 1, 4, 20, 1, 7, 11, 2,
1218 1, 11, 21, 2, 8, 5, 1, 8, 1, 5, 21, 1, 1, 1, 22, 1,
1219 1, 22, 1, 1, 3, 3, 1, 23, 2, 12, 24, 1, 1, 2, 1, 1,
1220 12, 23, 1, 1, 24, 1, 1, 1, 4, 1, 1, 1, 2, 1, 6, 6,
1221 4, 2, 1, 1, 1, 1, 1, 1, 1, 14, 13, 3, 1, 25, 9, 25,
1222 14, 1, 9, 3, 13, 1, 1, 1, 1, 1, 10, 1, 1, 2, 10, 2},
1225 {-20, -1, 0, 2, -2, 1, -1, 3, -3, 1, -1, 4, -4, 0, 2, -2,
1226 1, 5, -1, -5, 6, -6, 1, -1, 7, -7, 1, -1, 3, -3, 8, -8,
1227 2, -2, 1, -1, 9, -9, 1, -1, 10, -10, 4, -4, 11, 1, -11, -1,
1228 2, -2, 1, 12, -12, -1, 13, -13, 1, -1, 3, -3, 14, 5, -14, -5,
1229 -15, 15, -1, 1, 2, -2, 16, -16, 1, 17, -17, -1, 6, -6, 18, -18,
1230 2, -2, -19, 19, -3, 1, 3, -1, 4, 20, -4, 1, -21, 21, 1, 2,
1231 -1, -7, 7, -2, 22, -22, 23, 2, -23, -2, 1, -1, -24, 24, -25, 25,
1232 -8, -26, 26, 8, -27, 27, 5, 3, -3, -5, -4, 28, -28, 4, 29, -29,
1233 1, -1, -2, -30, 30, 2, 9, -9, -31, 31, 2, -2, -32, 3, 32, -33,
1234 -3, 1, 33, -34, -1, 34, -35, 35, -10, 10, -6, 36, 6, -36, 37, -37,
1235 -5, 38, 1, -38, -1, 3, 39, -39, -1, 40, 5, 1, -40, -3, 2, -11,
1236 -41, -2, 1, 11, -3, -4, 41, 3, 42, 4, -1, -43, -42, 43, 1, -44,
1237 45, -1, 44, -45, -7, 7, -46, 1, -12, 2, 1, -47, 46, 12, 47, 48,
1238 -2, -1, -48, 49, -1, -50, -49, 50, -6, -51, 51, 52, -13, 53, -4, 4,
1239 6, 13, -53, -52, -54, 55, 54, -55, -56, -2, 2, -8, 56, 1, -3, -1,
1240 2, 58, 3, 8, -2, 57, -58, -60, -59, -57, -3, 60, 59, -14, 3, 14}
1246 {1, 1, 0, 2, 2, 1, 1, 3, 3, 4, 4, 5, 5, 1, 1, 6,
1247 6, 2, 2, 7, 7, 8, 8, 1, 1, 3, 3, 9, 9, 10, 10, 1,
1248 1, 2, 2, 4, 4, 11, 0, 11, 12, 12, 13, 13, 1, 1, 5, 5,
1249 14, 14, 15, 16, 15, 16, 3, 3, 1, 6, 1, 6, 2, 2, 7, 7,
1250 8, 8, 17, 17, 1, 1, 4, 4, 18, 18, 2, 2, 1, 19, 1, 20,
1251 19, 20, 21, 21, 3, 3, 22, 22, 5, 5, 24, 1, 1, 23, 9, 23,
1252 24, 9, 2, 2, 10, 1, 1, 10, 6, 6, 25, 4, 4, 25, 7, 7,
1253 26, 8, 1, 8, 3, 1, 26, 3, 11, 11, 27, 27, 2, 28, 1, 2,
1254 28, 1, 12, 12, 5, 5, 29, 13, 13, 29, 32, 1, 1, 33, 31, 30,
1255 32, 4, 30, 33, 4, 31, 3, 14, 1, 1, 3, 34, 34, 2, 2, 14,
1256 6, 6, 35, 36, 35, 36, 1, 15, 1, 16, 16, 15, 7, 9, 7, 9,
1257 37, 8, 8, 37, 1, 1, 39, 2, 38, 39, 2, 40, 5, 38, 40, 5,
1258 3, 3, 4, 4, 10, 10, 1, 1, 1, 1, 41, 2, 41, 2, 6, 6,
1259 1, 1, 11, 42, 11, 43, 3, 42, 3, 17, 4, 43, 1, 17, 7, 1,
1260 8, 44, 4, 7, 44, 5, 8, 2, 5, 1, 2, 48, 45, 1, 12, 45,
1261 12, 48, 13, 13, 1, 9, 9, 46, 1, 46, 47, 47, 49, 18, 18, 49},
1264 { 1, -1, 0, 1, -1, 2, -2, 1, -1, 1, -1, 1, -1, 3, -3, 1,
1265 -1, -2, 2, 1, -1, 1, -1, 4, -4, -2, 2, 1, -1, 1, -1, 5,
1266 -5, -3, 3, 2, -2, 1, 0, -1, 1, -1, 1, -1, 6, -6, 2, -2,
1267 1, -1, 1, 1, -1, -1, -3, 3, 7, 2, -7, -2, -4, 4, 2, -2,
1268 2, -2, 1, -1, 8, -8, 3, -3, 1, -1, -5, 5, 9, 1, -9, 1,
1269 -1, -1, 1, -1, -4, 4, 1, -1, 3, -3, 1, -10, 10, 1, 2, -1,
1270 -1, -2, 6, -6, 2, 11, -11, -2, 3, -3, 1, -4, 4, -1, 3, -3,
1271 1, 3, 12, -3, -5, -12, -1, 5, 2, -2, 1, -1, -7, 1, 13, 7,
1272 -1, -13, 2, -2, 4, -4, 1, 2, -2, -1, 1, 14, -14, 1, 1, 1,
1273 -1, -5, -1, -1, 5, -1, -6, 2, -15, 15, 6, 1, -1, -8, 8, -2,
1274 -4, 4, 1, 1, -1, -1, 16, 2, -16, -2, 2, -2, 4, 3, -4, -3,
1275 -1, -4, 4, 1, -17, 17, -1, -9, 1, 1, 9, 1, -5, -1, -1, 5,
1276 -7, 7, 6, -6, 3, -3, 18, -18, 19, -19, 1, -10, -1, 10, -5, 5,
1277 20, -20, -3, 1, 3, 1, 8, -1, -8, 2, 7, -1, -21, -2, 5, 21,
1278 5, -1, -7, -5, 1, -6, -5, -11, 6, 22, 11, 1, 1, -22, -3, -1,
1279 3, -1, 3, -3, -23, 4, -4, 1, 23, -1, 1, -1, 1, -2, 2, -1}
1285 {1, 1, 1, 1, 0, 2, 2, 1, 1, 3, 3, 0, 1, 1, 2, 2,
1286 4, 4, 1, 1, 5, 5, 1, 1, 2, 2, 3, 3, 6, 6, 1, 1,
1287 7, 7, 8, 1, 8, 2, 2, 1, 4, 4, 1, 3, 1, 3, 9, 9,
1288 2, 2, 1, 5, 1, 5, 10, 10, 1, 1, 11, 11, 3, 6, 3, 4,
1289 4, 6, 2, 2, 1, 12, 1, 12, 7, 13, 7, 13, 1, 1, 8, 8,
1290 2, 2, 14, 14, 16, 15, 16, 5, 5, 1, 3, 15, 1, 3, 4, 4,
1291 1, 1, 17, 17, 2, 2, 6, 6, 1, 18, 1, 18, 22, 21, 22, 21,
1292 25, 24, 25, 19, 9, 20, 9, 23, 19, 24, 20, 3, 23, 7, 3, 1,
1293 1, 7, 28, 26, 29, 5, 28, 26, 5, 8, 29, 4, 8, 27, 2, 2,
1294 4, 27, 1, 1, 10, 36, 10, 33, 33, 36, 30, 1, 32, 32, 1, 30,
1295 6, 31, 31, 35, 3, 6, 11, 11, 3, 2, 35, 2, 34, 1, 34, 1,
1296 37, 37, 12, 7, 12, 5, 41, 5, 4, 7, 1, 8, 13, 4, 1, 41,
1297 13, 38, 8, 38, 9, 1, 40, 40, 9, 1, 39, 2, 2, 49, 39, 42,
1298 3, 3, 14, 16, 49, 14, 16, 42, 43, 43, 6, 6, 15, 1, 1, 15,
1299 44, 44, 1, 1, 50, 48, 4, 5, 4, 7, 5, 2, 10, 10, 48, 7,
1300 50, 45, 2, 1, 45, 8, 8, 1, 46, 46, 3, 47, 47, 3, 1, 1},
1303 { 1, -1, 2, -2, 0, 1, -1, 3, -3, 1, -1, 0, 4, -4, 2, -2,
1304 1, -1, 5, -5, 1, -1, 6, -6, 3, -3, 2, -2, 1, -1, 7, -7,
1305 1, -1, 1, 8, -1, 4, -4, -8, 2, -2, 9, 3, -9, -3, 1, -1,
1306 5, -5, 10, 2, -10, -2, 1, -1, 11, -11, 1, -1, -4, 2, 4, 3,
1307 -3, -2, 6, -6, 12, 1, -12, -1, 2, 1, -2, -1, 13, -13, 2, -2,
1308 7, -7, 1, -1, 1, 1, -1, 3, -3, 14, 5, -1, -14, -5, 4, -4,
1309 15, -15, 1, -1, 8, -8, -3, 3, 16, 1, -16, -1, 1, 1, -1, -1,
1310 1, 1, -1, 1, 2, 1, -2, 1, -1, -1, -1, 6, -1, 3, -6, 17,
1311 -17, -3, 1, 1, 1, 4, -1, -1, -4, 3, -1, 5, -3, -1, -9, 9,
1312 -5, 1, 18, -18, 2, 1, -2, 1, -1, -1, 1, 19, -1, 1, -19, -1,
1313 4, 1, -1, 1, 7, -4, -2, 2, -7, 10, -1, -10, 1, 20, -1, -20,
1314 1, -1, 2, 4, -2, 5, 1, -5, 6, -4, 21, 4, 2, -6, -21, -1,
1315 -2, 1, -4, -1, -3, 22, -1, 1, 3, -22, -1, 11, -11, 1, 1, 1,
1316 8, -8, 2, 2, -1, -2, -2, -1, 1, -1, -5, 5, 2, 23, -23, -2,
1317 1, -1, 24, -24, -1, -1, 7, 6, -7, 5, -6, 12, -3, 3, 1, -5,
1318 1, 1, -12, 25, -1, -5, 5, -25, -1, 1, 9, 1, -1, -9, 26, -26}