2 * common functions for Indeo Video Interactive codecs (Indeo4 and Indeo5)
4 * Copyright (c) 2009 Maxim Poliakovski
6 * This file is part of FFmpeg.
8 * FFmpeg is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU Lesser General Public
10 * License as published by the Free Software Foundation; either
11 * version 2.1 of the License, or (at your option) any later version.
13 * FFmpeg is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * Lesser General Public License for more details.
18 * You should have received a copy of the GNU Lesser General Public
19 * License along with FFmpeg; if not, write to the Free Software
20 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
25 * This file contains functions and data shared by both Indeo4 and
29 #define BITSTREAM_READER_LE
30 #include "libavutil/attributes.h"
35 #include "ivi_common.h"
38 extern const IVIHuffDesc ff_ivi_mb_huff_desc[8]; ///< static macroblock huffman tables
39 extern const IVIHuffDesc ff_ivi_blk_huff_desc[8]; ///< static block huffman tables
41 VLC ff_ivi_mb_vlc_tabs [8];
42 VLC ff_ivi_blk_vlc_tabs[8];
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);
60 int ff_ivi_create_huff_from_desc(const IVIHuffDesc *cb, VLC *vlc, int flag)
62 int pos, i, j, codes_per_row, prefix, not_last_row;
63 uint16_t codewords[256]; /* FIXME: move this temporal storage out? */
66 pos = 0; /* current position = 0 */
68 for (i = 0; i < cb->num_rows; i++) {
69 codes_per_row = 1 << cb->xbits[i];
70 not_last_row = (i != cb->num_rows - 1);
71 prefix = ((1 << i) - 1) << (cb->xbits[i] + not_last_row);
73 for (j = 0; j < codes_per_row; j++) {
74 if (pos >= 256) /* Some Indeo5 codebooks can have more than 256 */
75 break; /* elements, but only 256 codes are allowed! */
77 bits[pos] = i + cb->xbits[i] + not_last_row;
78 if (bits[pos] > IVI_VLC_BITS)
79 return -1; /* invalid descriptor */
81 codewords[pos] = inv_bits((prefix | j), bits[pos]);
89 /* number of codewords = pos */
90 return init_vlc(vlc, IVI_VLC_BITS, pos, bits, 1, 1, codewords, 2, 2,
91 (flag ? INIT_VLC_USE_NEW_STATIC : 0) | INIT_VLC_LE);
94 void ff_ivi_init_static_vlc(void)
97 static VLC_TYPE table_data[8192 * 16][2];
98 static int initialized_vlcs = 0;
100 if (initialized_vlcs)
102 for (i = 0; i < 8; i++) {
103 ff_ivi_mb_vlc_tabs[i].table = table_data + i * 2 * 8192;
104 ff_ivi_mb_vlc_tabs[i].table_allocated = 8192;
105 ff_ivi_create_huff_from_desc(&ff_ivi_mb_huff_desc[i], &ff_ivi_mb_vlc_tabs[i], 1);
106 ff_ivi_blk_vlc_tabs[i].table = table_data + (i * 2 + 1) * 8192;
107 ff_ivi_blk_vlc_tabs[i].table_allocated = 8192;
108 ff_ivi_create_huff_from_desc(&ff_ivi_blk_huff_desc[i], &ff_ivi_blk_vlc_tabs[i], 1);
110 initialized_vlcs = 1;
113 int ff_ivi_dec_huff_desc(GetBitContext *gb, int desc_coded, int which_tab,
114 IVIHuffTab *huff_tab, AVCodecContext *avctx)
117 IVIHuffDesc new_huff;
120 /* select default table */
121 huff_tab->tab = (which_tab) ? &ff_ivi_blk_vlc_tabs[7]
122 : &ff_ivi_mb_vlc_tabs [7];
124 huff_tab->tab_sel = get_bits(gb, 3);
125 if (huff_tab->tab_sel == 7) {
126 /* custom huffman table (explicitly encoded) */
127 new_huff.num_rows = get_bits(gb, 4);
128 if (!new_huff.num_rows) {
129 av_log(avctx, AV_LOG_ERROR, "Empty custom Huffman table!\n");
130 return AVERROR_INVALIDDATA;
133 for (i = 0; i < new_huff.num_rows; i++)
134 new_huff.xbits[i] = get_bits(gb, 4);
136 /* Have we got the same custom table? Rebuild if not. */
137 if (ff_ivi_huff_desc_cmp(&new_huff, &huff_tab->cust_desc) || !huff_tab->cust_tab.table) {
138 ff_ivi_huff_desc_copy(&huff_tab->cust_desc, &new_huff);
140 if (huff_tab->cust_tab.table)
141 ff_free_vlc(&huff_tab->cust_tab);
142 result = ff_ivi_create_huff_from_desc(&huff_tab->cust_desc,
143 &huff_tab->cust_tab, 0);
145 huff_tab->cust_desc.num_rows = 0; // reset faulty description
146 av_log(avctx, AV_LOG_ERROR,
147 "Error while initializing custom vlc table!\n");
151 huff_tab->tab = &huff_tab->cust_tab;
153 /* select one of predefined tables */
154 huff_tab->tab = (which_tab) ? &ff_ivi_blk_vlc_tabs[huff_tab->tab_sel]
155 : &ff_ivi_mb_vlc_tabs [huff_tab->tab_sel];
162 int ff_ivi_huff_desc_cmp(const IVIHuffDesc *desc1, const IVIHuffDesc *desc2)
164 return desc1->num_rows != desc2->num_rows
165 || memcmp(desc1->xbits, desc2->xbits, desc1->num_rows);
168 void ff_ivi_huff_desc_copy(IVIHuffDesc *dst, const IVIHuffDesc *src)
170 dst->num_rows = src->num_rows;
171 memcpy(dst->xbits, src->xbits, src->num_rows);
174 av_cold int ff_ivi_init_planes(IVIPlaneDesc *planes, const IVIPicConfig *cfg)
177 uint32_t b_width, b_height, align_fac, width_aligned, height_aligned, buf_size;
180 ff_ivi_free_buffers(planes);
182 /* fill in the descriptor of the luminance plane */
183 planes[0].width = cfg->pic_width;
184 planes[0].height = cfg->pic_height;
185 planes[0].num_bands = cfg->luma_bands;
187 /* fill in the descriptors of the chrominance planes */
188 planes[1].width = planes[2].width = (cfg->pic_width + 3) >> 2;
189 planes[1].height = planes[2].height = (cfg->pic_height + 3) >> 2;
190 planes[1].num_bands = planes[2].num_bands = cfg->chroma_bands;
192 for (p = 0; p < 3; p++) {
193 planes[p].bands = av_mallocz(planes[p].num_bands * sizeof(IVIBandDesc));
194 if (!planes[p].bands)
195 return AVERROR(ENOMEM);
197 /* select band dimensions: if there is only one band then it
198 * has the full size, if there are several bands each of them
199 * has only half size */
200 b_width = planes[p].num_bands == 1 ? planes[p].width : (planes[p].width + 1) >> 1;
201 b_height = planes[p].num_bands == 1 ? planes[p].height : (planes[p].height + 1) >> 1;
203 /* luma band buffers will be aligned on 16x16 (max macroblock size) */
204 /* chroma band buffers will be aligned on 8x8 (max macroblock size) */
205 align_fac = p ? 8 : 16;
206 width_aligned = FFALIGN(b_width , align_fac);
207 height_aligned = FFALIGN(b_height, align_fac);
208 buf_size = width_aligned * height_aligned * sizeof(int16_t);
210 for (b = 0; b < planes[p].num_bands; b++) {
211 band = &planes[p].bands[b]; /* select appropriate plane/band */
214 band->width = b_width;
215 band->height = b_height;
216 band->pitch = width_aligned;
217 band->aheight = height_aligned;
218 band->bufs[0] = av_mallocz(buf_size);
219 band->bufs[1] = av_mallocz(buf_size);
220 band->bufsize = buf_size/2;
221 if (!band->bufs[0] || !band->bufs[1])
222 return AVERROR(ENOMEM);
224 /* allocate the 3rd band buffer for scalability mode */
225 if (cfg->luma_bands > 1) {
226 band->bufs[2] = av_mallocz(buf_size);
228 return AVERROR(ENOMEM);
231 planes[p].bands[0].blk_vlc.cust_desc.num_rows = 0; /* reset custom vlc */
238 av_cold void ff_ivi_free_buffers(IVIPlaneDesc *planes)
242 for (p = 0; p < 3; p++) {
244 for (b = 0; b < planes[p].num_bands; b++) {
245 av_freep(&planes[p].bands[b].bufs[0]);
246 av_freep(&planes[p].bands[b].bufs[1]);
247 av_freep(&planes[p].bands[b].bufs[2]);
249 if (planes[p].bands[b].blk_vlc.cust_tab.table)
250 ff_free_vlc(&planes[p].bands[b].blk_vlc.cust_tab);
251 for (t = 0; t < planes[p].bands[b].num_tiles; t++)
252 av_freep(&planes[p].bands[b].tiles[t].mbs);
253 av_freep(&planes[p].bands[b].tiles);
255 av_freep(&planes[p].bands);
259 av_cold int ff_ivi_init_tiles(IVIPlaneDesc *planes, int tile_width, int tile_height)
261 int p, b, x, y, x_tiles, y_tiles, t_width, t_height;
263 IVITile *tile, *ref_tile;
265 for (p = 0; p < 3; p++) {
266 t_width = !p ? tile_width : (tile_width + 3) >> 2;
267 t_height = !p ? tile_height : (tile_height + 3) >> 2;
269 if (!p && planes[0].num_bands == 4) {
273 if(t_width<=0 || t_height<=0)
274 return AVERROR(EINVAL);
276 for (b = 0; b < planes[p].num_bands; b++) {
277 band = &planes[p].bands[b];
278 x_tiles = IVI_NUM_TILES(band->width, t_width);
279 y_tiles = IVI_NUM_TILES(band->height, t_height);
280 band->num_tiles = x_tiles * y_tiles;
282 av_freep(&band->tiles);
283 band->tiles = av_mallocz(band->num_tiles * sizeof(IVITile));
285 return AVERROR(ENOMEM);
289 /* use the first luma band as reference for motion vectors
291 ref_tile = planes[0].bands[0].tiles;
293 for (y = 0; y < band->height; y += t_height) {
294 for (x = 0; x < band->width; x += t_width) {
297 tile->mb_size = band->mb_size;
298 tile->width = FFMIN(band->width - x, t_width);
299 tile->height = FFMIN(band->height - y, t_height);
300 tile->is_empty = tile->data_size = 0;
301 /* calculate number of macroblocks */
302 tile->num_MBs = IVI_MBs_PER_TILE(tile->width, tile->height,
305 av_freep(&tile->mbs);
306 tile->mbs = av_malloc(tile->num_MBs * sizeof(IVIMbInfo));
308 return AVERROR(ENOMEM);
312 if (tile->num_MBs <= ref_tile->num_MBs) {
313 tile->ref_mbs = ref_tile->mbs;
315 av_log(NULL, AV_LOG_DEBUG, "Cannot use ref_tile, too few mbs\n");
329 int ff_ivi_dec_tile_data_size(GetBitContext *gb)
335 len = get_bits(gb, 8);
337 len = get_bits_long(gb, 24);
340 /* align the bitstream reader on the byte boundary */
346 int ff_ivi_decode_blocks(GetBitContext *gb, IVIBandDesc *band, IVITile *tile)
348 int mbn, blk, num_blocks, num_coeffs, blk_size, scan_pos, run, val,
349 pos, is_intra, mc_type = 0, mv_x, mv_y, col_mask;
350 uint8_t col_flags[8];
351 int32_t prev_dc, trvec[64];
352 uint32_t cbp, sym, lo, hi, quant, buf_offs, q;
354 RVMapDesc *rvmap = band->rv_map;
355 void (*mc_with_delta_func)(int16_t *buf, const int16_t *ref_buf, uint32_t pitch, int mc_type);
356 void (*mc_no_delta_func) (int16_t *buf, const int16_t *ref_buf, uint32_t pitch, int mc_type);
357 const uint16_t *base_tab;
358 const uint8_t *scale_tab;
360 prev_dc = 0; /* init intra prediction for the DC coefficient */
362 blk_size = band->blk_size;
363 col_mask = blk_size - 1; /* column mask for tracking non-zero coeffs */
364 num_blocks = (band->mb_size != blk_size) ? 4 : 1; /* number of blocks per mb */
365 num_coeffs = blk_size * blk_size;
367 mc_with_delta_func = ff_ivi_mc_8x8_delta;
368 mc_no_delta_func = ff_ivi_mc_8x8_no_delta;
370 mc_with_delta_func = ff_ivi_mc_4x4_delta;
371 mc_no_delta_func = ff_ivi_mc_4x4_no_delta;
374 for (mbn = 0, mb = tile->mbs; mbn < tile->num_MBs; mb++, mbn++) {
375 is_intra = !mb->type;
377 buf_offs = mb->buf_offs;
379 quant = av_clip(band->glob_quant + mb->q_delta, 0, 23);
381 base_tab = is_intra ? band->intra_base : band->inter_base;
382 scale_tab = is_intra ? band->intra_scale : band->inter_scale;
384 quant = scale_tab[quant];
389 if (band->is_halfpel) {
390 mc_type = ((mv_y & 1) << 1) | (mv_x & 1);
392 mv_y >>= 1; /* convert halfpel vectors into fullpel ones */
395 int dmv_x, dmv_y, cx, cy;
397 dmv_x = mb->mv_x >> band->is_halfpel;
398 dmv_y = mb->mv_y >> band->is_halfpel;
399 cx = mb->mv_x & band->is_halfpel;
400 cy = mb->mv_y & band->is_halfpel;
402 if ( mb->xpos + dmv_x < 0
403 || mb->xpos + dmv_x + band->mb_size + cx > band->pitch
404 || mb->ypos + dmv_y < 0
405 || mb->ypos + dmv_y + band->mb_size + cy > band->aheight) {
406 return AVERROR_INVALIDDATA;
411 for (blk = 0; blk < num_blocks; blk++) {
412 /* adjust block position in the buffer according to its number */
414 buf_offs += blk_size;
415 } else if (blk == 2) {
416 buf_offs -= blk_size;
417 buf_offs += blk_size * band->pitch;
420 if (cbp & 1) { /* block coded ? */
422 memset(trvec, 0, num_coeffs*sizeof(trvec[0])); /* zero transform vector */
423 memset(col_flags, 0, sizeof(col_flags)); /* zero column flags */
425 while (scan_pos <= num_coeffs) {
426 sym = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
427 if (sym == rvmap->eob_sym)
428 break; /* End of block */
430 if (sym == rvmap->esc_sym) { /* Escape - run/val explicitly coded using 3 vlc codes */
431 run = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1) + 1;
432 lo = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
433 hi = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
434 val = IVI_TOSIGNED((hi << 6) | lo); /* merge them and convert into signed val */
437 av_log(NULL, AV_LOG_ERROR, "Invalid sym encountered: %d.\n", sym);
440 run = rvmap->runtab[sym];
441 val = rvmap->valtab[sym];
444 /* de-zigzag and dequantize */
446 if (scan_pos >= (unsigned)num_coeffs)
448 pos = band->scan[scan_pos];
451 av_dlog(NULL, "Val = 0 encountered!\n");
453 q = (base_tab[pos] * quant) >> 9;
455 val = val * q + FFSIGN(val) * (((q ^ 1) - 1) >> 1);
457 col_flags[pos & col_mask] |= !!val; /* track columns containing non-zero coeffs */
460 if (scan_pos >= num_coeffs && sym != rvmap->eob_sym)
461 return -1; /* corrupt block data */
463 /* undoing DC coeff prediction for intra-blocks */
464 if (is_intra && band->is_2d_trans) {
467 col_flags[0] |= !!prev_dc;
469 if(band->transform_size > band->blk_size){
470 av_log(NULL, AV_LOG_ERROR, "Too large transform\n");
471 return AVERROR_INVALIDDATA;
473 /* apply inverse transform */
474 band->inv_transform(trvec, band->buf + buf_offs,
475 band->pitch, col_flags);
477 /* apply motion compensation */
479 mc_with_delta_func(band->buf + buf_offs,
480 band->ref_buf + buf_offs + mv_y * band->pitch + mv_x,
481 band->pitch, mc_type);
483 /* block not coded */
484 /* for intra blocks apply the dc slant transform */
485 /* for inter - perform the motion compensation without delta */
487 band->dc_transform(&prev_dc, band->buf + buf_offs,
488 band->pitch, blk_size);
490 mc_no_delta_func(band->buf + buf_offs,
491 band->ref_buf + buf_offs + mv_y * band->pitch + mv_x,
492 band->pitch, mc_type);
505 * Handle empty tiles by performing data copying and motion
506 * compensation respectively.
508 * @param[in] avctx ptr to the AVCodecContext
509 * @param[in] band pointer to the band descriptor
510 * @param[in] tile pointer to the tile descriptor
511 * @param[in] mv_scale scaling factor for motion vectors
513 static int ivi_process_empty_tile(AVCodecContext *avctx, IVIBandDesc *band,
514 IVITile *tile, int32_t mv_scale)
516 int x, y, need_mc, mbn, blk, num_blocks, mv_x, mv_y, mc_type;
517 int offs, mb_offset, row_offset;
518 IVIMbInfo *mb, *ref_mb;
521 void (*mc_no_delta_func)(int16_t *buf, const int16_t *ref_buf, uint32_t pitch,
524 if (tile->num_MBs != IVI_MBs_PER_TILE(tile->width, tile->height, band->mb_size)) {
525 av_log(avctx, AV_LOG_ERROR, "Allocated tile size %d mismatches "
526 "parameters %d in ivi_process_empty_tile()\n",
527 tile->num_MBs, IVI_MBs_PER_TILE(tile->width, tile->height, band->mb_size));
528 return AVERROR_INVALIDDATA;
531 offs = tile->ypos * band->pitch + tile->xpos;
533 ref_mb = tile->ref_mbs;
534 row_offset = band->mb_size * band->pitch;
535 need_mc = 0; /* reset the mc tracking flag */
537 for (y = tile->ypos; y < (tile->ypos + tile->height); y += band->mb_size) {
540 for (x = tile->xpos; x < (tile->xpos + tile->width); x += band->mb_size) {
543 mb->buf_offs = mb_offset;
545 mb->type = 1; /* set the macroblocks type = INTER */
546 mb->cbp = 0; /* all blocks are empty */
548 if (!band->qdelta_present && !band->plane && !band->band_num) {
549 mb->q_delta = band->glob_quant;
554 if (band->inherit_qdelta && ref_mb)
555 mb->q_delta = ref_mb->q_delta;
557 if (band->inherit_mv && ref_mb) {
558 /* motion vector inheritance */
560 mb->mv_x = ivi_scale_mv(ref_mb->mv_x, mv_scale);
561 mb->mv_y = ivi_scale_mv(ref_mb->mv_y, mv_scale);
563 mb->mv_x = ref_mb->mv_x;
564 mb->mv_y = ref_mb->mv_y;
566 need_mc |= mb->mv_x || mb->mv_y; /* tracking non-zero motion vectors */
568 int dmv_x, dmv_y, cx, cy;
570 dmv_x = mb->mv_x >> band->is_halfpel;
571 dmv_y = mb->mv_y >> band->is_halfpel;
572 cx = mb->mv_x & band->is_halfpel;
573 cy = mb->mv_y & band->is_halfpel;
575 if ( mb->xpos + dmv_x < 0
576 || mb->xpos + dmv_x + band->mb_size + cx > band->pitch
577 || mb->ypos + dmv_y < 0
578 || mb->ypos + dmv_y + band->mb_size + cy > band->aheight) {
579 av_log(avctx, AV_LOG_ERROR, "MV out of bounds\n");
580 return AVERROR_INVALIDDATA;
588 mb_offset += band->mb_size;
593 if (band->inherit_mv && need_mc) { /* apply motion compensation if there is at least one non-zero motion vector */
594 num_blocks = (band->mb_size != band->blk_size) ? 4 : 1; /* number of blocks per mb */
595 mc_no_delta_func = (band->blk_size == 8) ? ff_ivi_mc_8x8_no_delta
596 : ff_ivi_mc_4x4_no_delta;
598 for (mbn = 0, mb = tile->mbs; mbn < tile->num_MBs; mb++, mbn++) {
601 if (!band->is_halfpel) {
602 mc_type = 0; /* we have only fullpel vectors */
604 mc_type = ((mv_y & 1) << 1) | (mv_x & 1);
606 mv_y >>= 1; /* convert halfpel vectors into fullpel ones */
609 for (blk = 0; blk < num_blocks; blk++) {
610 /* adjust block position in the buffer according with its number */
611 offs = mb->buf_offs + band->blk_size * ((blk & 1) + !!(blk & 2) * band->pitch);
612 mc_no_delta_func(band->buf + offs,
613 band->ref_buf + offs + mv_y * band->pitch + mv_x,
614 band->pitch, mc_type);
618 /* copy data from the reference tile into the current one */
619 src = band->ref_buf + tile->ypos * band->pitch + tile->xpos;
620 dst = band->buf + tile->ypos * band->pitch + tile->xpos;
621 for (y = 0; y < tile->height; y++) {
622 memcpy(dst, src, tile->width*sizeof(band->buf[0]));
633 static uint16_t ivi_calc_band_checksum(IVIBandDesc *band)
636 int16_t *src, checksum;
641 for (y = 0; y < band->height; src += band->pitch, y++)
642 for (x = 0; x < band->width; x++)
649 void ff_ivi_output_plane(IVIPlaneDesc *plane, uint8_t *dst, int dst_pitch)
652 const int16_t *src = plane->bands[0].buf;
653 uint32_t pitch = plane->bands[0].pitch;
658 for (y = 0; y < plane->height; y++) {
659 for (x = 0; x < plane->width; x++)
660 dst[x] = av_clip_uint8(src[x] + 128);
667 * Decode an Indeo 4 or 5 band.
669 * @param[in,out] ctx ptr to the decoder context
670 * @param[in,out] band ptr to the band descriptor
671 * @param[in] avctx ptr to the AVCodecContext
672 * @return result code: 0 = OK, -1 = error
674 static int decode_band(IVI45DecContext *ctx,
675 IVIBandDesc *band, AVCodecContext *avctx)
677 int result, i, t, idx1, idx2, pos;
680 band->buf = band->bufs[ctx->dst_buf];
682 av_log(avctx, AV_LOG_ERROR, "Band buffer points to no data!\n");
683 return AVERROR_INVALIDDATA;
685 band->ref_buf = band->bufs[ctx->ref_buf];
686 band->data_ptr = ctx->frame_data + (get_bits_count(&ctx->gb) >> 3);
688 result = ctx->decode_band_hdr(ctx, band, avctx);
690 av_log(avctx, AV_LOG_ERROR, "Error while decoding band header: %d\n",
695 if (band->is_empty) {
696 av_log(avctx, AV_LOG_ERROR, "Empty band encountered!\n");
697 return AVERROR_INVALIDDATA;
700 band->rv_map = &ctx->rvmap_tabs[band->rvmap_sel];
702 /* apply corrections to the selected rvmap table if present */
703 for (i = 0; i < band->num_corr; i++) {
704 idx1 = band->corr[i * 2];
705 idx2 = band->corr[i * 2 + 1];
706 FFSWAP(uint8_t, band->rv_map->runtab[idx1], band->rv_map->runtab[idx2]);
707 FFSWAP(int16_t, band->rv_map->valtab[idx1], band->rv_map->valtab[idx2]);
708 if (idx1 == band->rv_map->eob_sym || idx2 == band->rv_map->eob_sym)
709 band->rv_map->eob_sym ^= idx1 ^ idx2;
710 if (idx1 == band->rv_map->esc_sym || idx2 == band->rv_map->esc_sym)
711 band->rv_map->esc_sym ^= idx1 ^ idx2;
714 pos = get_bits_count(&ctx->gb);
716 for (t = 0; t < band->num_tiles; t++) {
717 tile = &band->tiles[t];
719 if (tile->mb_size != band->mb_size) {
720 av_log(avctx, AV_LOG_ERROR, "MB sizes mismatch: %d vs. %d\n",
721 band->mb_size, tile->mb_size);
722 return AVERROR_INVALIDDATA;
724 tile->is_empty = get_bits1(&ctx->gb);
725 if (tile->is_empty) {
726 result = ivi_process_empty_tile(avctx, band, tile,
727 (ctx->planes[0].bands[0].mb_size >> 3) - (band->mb_size >> 3));
730 av_dlog(avctx, "Empty tile encountered!\n");
732 tile->data_size = ff_ivi_dec_tile_data_size(&ctx->gb);
733 if (!tile->data_size) {
734 av_log(avctx, AV_LOG_ERROR, "Tile data size is zero!\n");
735 result = AVERROR_INVALIDDATA;
739 result = ctx->decode_mb_info(ctx, band, tile, avctx);
743 result = ff_ivi_decode_blocks(&ctx->gb, band, tile);
744 if (result < 0 || ((get_bits_count(&ctx->gb) - pos) >> 3) != tile->data_size) {
745 av_log(avctx, AV_LOG_ERROR, "Corrupted tile data encountered!\n");
749 pos += tile->data_size << 3; // skip to next tile
753 /* restore the selected rvmap table by applying its corrections in reverse order */
754 for (i = band->num_corr-1; i >= 0; i--) {
755 idx1 = band->corr[i*2];
756 idx2 = band->corr[i*2+1];
757 FFSWAP(uint8_t, band->rv_map->runtab[idx1], band->rv_map->runtab[idx2]);
758 FFSWAP(int16_t, band->rv_map->valtab[idx1], band->rv_map->valtab[idx2]);
759 if (idx1 == band->rv_map->eob_sym || idx2 == band->rv_map->eob_sym)
760 band->rv_map->eob_sym ^= idx1 ^ idx2;
761 if (idx1 == band->rv_map->esc_sym || idx2 == band->rv_map->esc_sym)
762 band->rv_map->esc_sym ^= idx1 ^ idx2;
766 if (band->checksum_present) {
767 uint16_t chksum = ivi_calc_band_checksum(band);
768 if (chksum != band->checksum) {
769 av_log(avctx, AV_LOG_ERROR,
770 "Band checksum mismatch! Plane %d, band %d, received: %x, calculated: %x\n",
771 band->plane, band->band_num, band->checksum, chksum);
776 align_get_bits(&ctx->gb);
781 int ff_ivi_decode_frame(AVCodecContext *avctx, void *data, int *got_frame,
784 IVI45DecContext *ctx = avctx->priv_data;
785 const uint8_t *buf = avpkt->data;
786 int buf_size = avpkt->size;
789 init_get_bits(&ctx->gb, buf, buf_size * 8);
790 ctx->frame_data = buf;
791 ctx->frame_size = buf_size;
793 result = ctx->decode_pic_hdr(ctx, avctx);
795 av_log(avctx, AV_LOG_ERROR,
796 "Error while decoding picture header: %d\n", result);
799 if (ctx->gop_invalid)
800 return AVERROR_INVALIDDATA;
802 if (ctx->gop_flags & IVI5_IS_PROTECTED) {
803 av_log(avctx, AV_LOG_ERROR, "Password-protected clip!\n");
807 ctx->switch_buffers(ctx);
811 if (ctx->is_nonnull_frame(ctx)) {
812 ctx->buf_invalid[ctx->dst_buf] = 1;
813 for (p = 0; p < 3; p++) {
814 for (b = 0; b < ctx->planes[p].num_bands; b++) {
815 result = decode_band(ctx, &ctx->planes[p].bands[b], avctx);
817 av_log(avctx, AV_LOG_ERROR,
818 "Error while decoding band: %d, plane: %d\n", b, p);
823 ctx->buf_invalid[ctx->dst_buf] = 0;
825 if (ctx->buf_invalid[ctx->dst_buf])
828 //STOP_TIMER("decode_planes"); }
830 /* If the bidirectional mode is enabled, next I and the following P frame will */
831 /* be sent together. Unfortunately the approach below seems to be the only way */
832 /* to handle the B-frames mode. That's exactly the same Intel decoders do. */
833 if (avctx->codec_id == AV_CODEC_ID_INDEO4 && ctx->frame_type == 0/*FRAMETYPE_INTRA*/) {
834 while (get_bits(&ctx->gb, 8)); // skip version string
835 skip_bits_long(&ctx->gb, 64); // skip padding, TODO: implement correct 8-bytes alignment
836 if (get_bits_left(&ctx->gb) > 18 && show_bits(&ctx->gb, 18) == 0x3FFF8)
837 av_log(avctx, AV_LOG_ERROR, "Buffer contains IP frames!\n");
840 if (!ctx->is_nonnull_frame(ctx))
843 if (ctx->frame.data[0])
844 avctx->release_buffer(avctx, &ctx->frame);
846 ctx->frame.reference = 0;
847 avcodec_set_dimensions(avctx, ctx->planes[0].width, ctx->planes[0].height);
848 if ((result = ff_get_buffer(avctx, &ctx->frame)) < 0) {
849 av_log(avctx, AV_LOG_ERROR, "get_buffer() failed\n");
853 if (ctx->is_scalable) {
854 if (avctx->codec_id == AV_CODEC_ID_INDEO4)
855 ff_ivi_recompose_haar(&ctx->planes[0], ctx->frame.data[0], ctx->frame.linesize[0]);
857 ff_ivi_recompose53 (&ctx->planes[0], ctx->frame.data[0], ctx->frame.linesize[0]);
859 ff_ivi_output_plane(&ctx->planes[0], ctx->frame.data[0], ctx->frame.linesize[0]);
862 ff_ivi_output_plane(&ctx->planes[2], ctx->frame.data[1], ctx->frame.linesize[1]);
863 ff_ivi_output_plane(&ctx->planes[1], ctx->frame.data[2], ctx->frame.linesize[2]);
866 *(AVFrame*)data = ctx->frame;
872 * Close Indeo5 decoder and clean up its context.
874 av_cold int ff_ivi_decode_close(AVCodecContext *avctx)
876 IVI45DecContext *ctx = avctx->priv_data;
878 ff_ivi_free_buffers(&ctx->planes[0]);
880 if (ctx->mb_vlc.cust_tab.table)
881 ff_free_vlc(&ctx->mb_vlc.cust_tab);
883 if (ctx->frame.data[0])
884 avctx->release_buffer(avctx, &ctx->frame);
886 #if IVI4_STREAM_ANALYSER
887 if (avctx->codec_id == AV_CODEC_ID_INDEO4) {
888 if (ctx->is_scalable)
889 av_log(avctx, AV_LOG_ERROR, "This video uses scalability mode!\n");
890 if (ctx->uses_tiling)
891 av_log(avctx, AV_LOG_ERROR, "This video uses local decoding!\n");
892 if (ctx->has_b_frames)
893 av_log(avctx, AV_LOG_ERROR, "This video contains B-frames!\n");
895 av_log(avctx, AV_LOG_ERROR, "Transparency mode is enabled!\n");
897 av_log(avctx, AV_LOG_ERROR, "This video uses Haar transform!\n");
898 if (ctx->uses_fullpel)
899 av_log(avctx, AV_LOG_ERROR, "This video uses fullpel motion vectors!\n");
908 * These are 2x8 predefined Huffman codebooks for coding macroblock/block
909 * signals. They are specified using "huffman descriptors" in order to
910 * avoid huge static tables. The decoding tables will be generated at
911 * startup from these descriptors.
913 const IVIHuffDesc ff_ivi_mb_huff_desc[8] = {
914 {8, {0, 4, 5, 4, 4, 4, 6, 6}},
915 {12, {0, 2, 2, 3, 3, 3, 3, 5, 3, 2, 2, 2}},
916 {12, {0, 2, 3, 4, 3, 3, 3, 3, 4, 3, 2, 2}},
917 {12, {0, 3, 4, 4, 3, 3, 3, 3, 3, 2, 2, 2}},
918 {13, {0, 4, 4, 3, 3, 3, 3, 2, 3, 3, 2, 1, 1}},
919 {9, {0, 4, 4, 4, 4, 3, 3, 3, 2}},
920 {10, {0, 4, 4, 4, 4, 3, 3, 2, 2, 2}},
921 {12, {0, 4, 4, 4, 3, 3, 2, 3, 2, 2, 2, 2}}
924 const IVIHuffDesc ff_ivi_blk_huff_desc[8] = {
925 {10, {1, 2, 3, 4, 4, 7, 5, 5, 4, 1}},
926 {11, {2, 3, 4, 4, 4, 7, 5, 4, 3, 3, 2}},
927 {12, {2, 4, 5, 5, 5, 5, 6, 4, 4, 3, 1, 1}},
928 {13, {3, 3, 4, 4, 5, 6, 6, 4, 4, 3, 2, 1, 1}},
929 {11, {3, 4, 4, 5, 5, 5, 6, 5, 4, 2, 2}},
930 {13, {3, 4, 5, 5, 5, 5, 6, 4, 3, 3, 2, 1, 1}},
931 {13, {3, 4, 5, 5, 5, 6, 5, 4, 3, 3, 2, 1, 1}},
932 {9, {3, 4, 4, 5, 5, 5, 6, 5, 5}}
937 * Scan patterns shared between indeo4 and indeo5
939 const uint8_t ff_ivi_vertical_scan_8x8[64] = {
940 0, 8, 16, 24, 32, 40, 48, 56,
941 1, 9, 17, 25, 33, 41, 49, 57,
942 2, 10, 18, 26, 34, 42, 50, 58,
943 3, 11, 19, 27, 35, 43, 51, 59,
944 4, 12, 20, 28, 36, 44, 52, 60,
945 5, 13, 21, 29, 37, 45, 53, 61,
946 6, 14, 22, 30, 38, 46, 54, 62,
947 7, 15, 23, 31, 39, 47, 55, 63
950 const uint8_t ff_ivi_horizontal_scan_8x8[64] = {
951 0, 1, 2, 3, 4, 5, 6, 7,
952 8, 9, 10, 11, 12, 13, 14, 15,
953 16, 17, 18, 19, 20, 21, 22, 23,
954 24, 25, 26, 27, 28, 29, 30, 31,
955 32, 33, 34, 35, 36, 37, 38, 39,
956 40, 41, 42, 43, 44, 45, 46, 47,
957 48, 49, 50, 51, 52, 53, 54, 55,
958 56, 57, 58, 59, 60, 61, 62, 63
961 const uint8_t ff_ivi_direct_scan_4x4[16] = {
962 0, 1, 4, 8, 5, 2, 3, 6, 9, 12, 13, 10, 7, 11, 14, 15
967 * Run-value (RLE) tables.
969 const RVMapDesc ff_ivi_rvmap_tabs[9] = {
974 {1, 1, 0, 1, 1, 0, 1, 1, 2, 2, 1, 1, 1, 1, 3, 3,
975 1, 1, 2, 2, 1, 1, 4, 4, 1, 1, 1, 1, 2, 2, 5, 5,
976 1, 1, 3, 3, 1, 1, 6, 6, 1, 2, 1, 2, 7, 7, 1, 1,
977 8, 8, 1, 1, 4, 2, 1, 4, 2, 1, 3, 3, 1, 1, 1, 9,
978 9, 1, 2, 1, 2, 1, 5, 5, 1, 1, 10, 10, 1, 1, 3, 3,
979 2, 2, 1, 1, 11, 11, 6, 4, 4, 1, 6, 1, 2, 1, 2, 12,
980 8, 1, 12, 7, 8, 7, 1, 16, 1, 16, 1, 3, 3, 13, 1, 13,
981 2, 2, 1, 15, 1, 5, 14, 15, 1, 5, 14, 1, 17, 8, 17, 8,
982 1, 4, 4, 2, 2, 1, 25, 25, 24, 24, 1, 3, 1, 3, 1, 8,
983 6, 7, 6, 1, 18, 8, 18, 1, 7, 23, 2, 2, 23, 1, 1, 21,
984 22, 9, 9, 22, 19, 1, 21, 5, 19, 5, 1, 33, 20, 33, 20, 8,
985 4, 4, 1, 32, 2, 2, 8, 3, 32, 26, 3, 1, 7, 7, 26, 6,
986 1, 6, 1, 1, 16, 1, 10, 1, 10, 2, 16, 29, 28, 2, 29, 28,
987 1, 27, 5, 8, 5, 27, 1, 8, 3, 7, 3, 31, 41, 31, 1, 41,
988 6, 1, 6, 7, 4, 4, 1, 1, 2, 1, 2, 11, 34, 30, 11, 1,
989 30, 15, 15, 34, 36, 40, 36, 40, 35, 35, 37, 37, 39, 39, 38, 38},
992 { 1, -1, 0, 2, -2, 0, 3, -3, 1, -1, 4, -4, 5, -5, 1, -1,
993 6, -6, 2, -2, 7, -7, 1, -1, 8, -8, 9, -9, 3, -3, 1, -1,
994 10, -10, 2, -2, 11, -11, 1, -1, 12, 4, -12, -4, 1, -1, 13, -13,
995 1, -1, 14, -14, 2, 5, 15, -2, -5, -15, -3, 3, 16, -16, 17, 1,
996 -1, -17, 6, 18, -6, -18, 2, -2, 19, -19, 1, -1, 20, -20, 4, -4,
997 7, -7, 21, -21, 1, -1, 2, 3, -3, 22, -2, -22, 8, 23, -8, 1,
998 2, -23, -1, 2, -2, -2, 24, 1, -24, -1, 25, 5, -5, 1, -25, -1,
999 9, -9, 26, 1, -26, 3, 1, -1, 27, -3, -1, -27, 1, 3, -1, -3,
1000 28, -4, 4, 10, -10, -28, 1, -1, 1, -1, 29, 6, -29, -6, 30, -4,
1001 3, 3, -3, -30, 1, 4, -1, 31, -3, 1, 11, -11, -1, -31, 32, -1,
1002 -1, 2, -2, 1, 1, -32, 1, 4, -1, -4, 33, -1, 1, 1, -1, 5,
1003 5, -5, -33, -1, -12, 12, -5, -7, 1, 1, 7, 34, 4, -4, -1, 4,
1004 -34, -4, 35, 36, -2, -35, -2, -36, 2, 13, 2, -1, 1, -13, 1, -1,
1005 37, 1, -5, 6, 5, -1, 38, -6, -8, 5, 8, -1, 1, 1, -37, -1,
1006 5, 39, -5, -5, 6, -6, -38, -39, -14, 40, 14, 2, 1, 1, -2, -40,
1007 -1, -2, 2, -1, -1, -1, 1, 1, 1, -1, 1, -1, 1, -1, 1, -1}
1013 {0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 8, 6, 8, 7,
1014 7, 9, 9, 10, 10, 11, 11, 1, 12, 1, 12, 13, 13, 16, 14, 16,
1015 14, 15, 15, 17, 17, 18, 0, 18, 19, 20, 21, 19, 22, 21, 20, 22,
1016 25, 24, 2, 25, 24, 23, 23, 2, 26, 28, 26, 28, 29, 27, 29, 27,
1017 33, 33, 1, 32, 1, 3, 32, 30, 36, 3, 36, 30, 31, 31, 35, 34,
1018 37, 41, 34, 35, 37, 4, 41, 4, 49, 8, 8, 49, 40, 38, 5, 38,
1019 40, 39, 5, 39, 42, 43, 42, 7, 57, 6, 43, 44, 6, 50, 7, 44,
1020 57, 48, 50, 48, 45, 45, 46, 47, 51, 46, 47, 58, 1, 51, 58, 1,
1021 52, 59, 53, 9, 52, 55, 55, 59, 53, 56, 54, 56, 54, 9, 64, 64,
1022 60, 63, 60, 63, 61, 62, 61, 62, 2, 10, 2, 10, 11, 1, 11, 13,
1023 12, 1, 12, 13, 16, 16, 8, 8, 14, 3, 3, 15, 14, 15, 4, 4,
1024 1, 17, 17, 5, 1, 7, 7, 5, 6, 1, 2, 2, 6, 22, 1, 25,
1025 21, 22, 8, 24, 1, 21, 25, 24, 8, 18, 18, 23, 9, 20, 23, 33,
1026 29, 33, 20, 1, 19, 1, 29, 36, 9, 36, 19, 41, 28, 57, 32, 3,
1027 28, 3, 1, 27, 49, 49, 1, 32, 26, 26, 2, 4, 4, 7, 57, 41,
1028 2, 7, 10, 5, 37, 16, 10, 27, 8, 8, 13, 16, 37, 13, 1, 5},
1031 {0, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, 1, -1, -1, 1,
1032 -1, 1, -1, 1, -1, 1, -1, 2, 1, -2, -1, 1, -1, 1, 1, -1,
1033 -1, 1, -1, 1, -1, 1, 0, -1, 1, 1, 1, -1, 1, -1, -1, -1,
1034 1, 1, 2, -1, -1, 1, -1, -2, 1, 1, -1, -1, 1, 1, -1, -1,
1035 1, -1, 3, 1, -3, 2, -1, 1, 1, -2, -1, -1, -1, 1, 1, 1,
1036 1, 1, -1, -1, -1, 2, -1, -2, 1, 2, -2, -1, 1, 1, 2, -1,
1037 -1, 1, -2, -1, 1, 1, -1, 2, 1, 2, -1, 1, -2, -1, -2, -1,
1038 -1, 1, 1, -1, 1, -1, 1, 1, 1, -1, -1, 1, 4, -1, -1, -4,
1039 1, 1, 1, 2, -1, -1, 1, -1, -1, 1, -1, -1, 1, -2, 1, -1,
1040 1, 1, -1, -1, 1, 1, -1, -1, 3, 2, -3, -2, 2, 5, -2, 2,
1041 2, -5, -2, -2, -2, 2, -3, 3, 2, 3, -3, 2, -2, -2, 3, -3,
1042 6, 2, -2, 3, -6, 3, -3, -3, 3, 7, -4, 4, -3, 2, -7, 2,
1043 2, -2, -4, 2, 8, -2, -2, -2, 4, 2, -2, 2, 3, 2, -2, -2,
1044 2, 2, -2, -8, -2, 9, -2, 2, -3, -2, 2, -2, 2, 2, 2, 4,
1045 -2, -4, 10, 2, 2, -2, -9, -2, 2, -2, 5, 4, -4, 4, -2, 2,
1046 -5, -4, -3, 4, 2, -3, 3, -2, -5, 5, 3, 3, -2, -3, -10, -4}
1052 {1, 1, 0, 2, 2, 1, 1, 3, 3, 4, 4, 0, 1, 1, 5, 5,
1053 2, 2, 6, 6, 7, 7, 1, 8, 1, 8, 3, 3, 9, 9, 1, 2,
1054 2, 1, 4, 10, 4, 10, 11, 11, 1, 5, 12, 12, 1, 5, 13, 13,
1055 3, 3, 6, 6, 2, 2, 14, 14, 16, 16, 15, 7, 15, 8, 8, 7,
1056 1, 1, 17, 17, 4, 4, 1, 1, 18, 18, 2, 2, 5, 5, 25, 3,
1057 9, 3, 25, 9, 19, 24, 19, 24, 1, 21, 20, 1, 21, 22, 20, 22,
1058 23, 23, 8, 6, 33, 6, 8, 33, 7, 7, 26, 26, 1, 32, 1, 32,
1059 28, 4, 28, 10, 29, 27, 27, 10, 41, 4, 29, 2, 2, 41, 36, 31,
1060 49, 31, 34, 30, 34, 36, 30, 35, 1, 49, 11, 5, 35, 11, 1, 3,
1061 3, 5, 37, 37, 8, 40, 8, 40, 12, 12, 42, 42, 1, 38, 16, 57,
1062 1, 6, 16, 39, 38, 6, 7, 7, 13, 13, 39, 43, 2, 43, 57, 2,
1063 50, 9, 44, 9, 50, 4, 15, 48, 44, 4, 1, 15, 48, 14, 14, 1,
1064 45, 45, 8, 3, 5, 8, 51, 47, 3, 46, 46, 47, 5, 51, 1, 17,
1065 17, 58, 1, 58, 2, 52, 52, 2, 53, 7, 59, 6, 6, 56, 53, 55,
1066 7, 55, 1, 54, 59, 56, 54, 10, 1, 10, 4, 60, 1, 60, 8, 4,
1067 8, 64, 64, 61, 1, 63, 3, 63, 62, 61, 5, 11, 5, 3, 11, 62},
1070 { 1, -1, 0, 1, -1, 2, -2, 1, -1, 1, -1, 0, 3, -3, 1, -1,
1071 2, -2, 1, -1, 1, -1, 4, 1, -4, -1, 2, -2, 1, -1, 5, 3,
1072 -3, -5, 2, 1, -2, -1, 1, -1, 6, 2, 1, -1, -6, -2, 1, -1,
1073 3, -3, 2, -2, 4, -4, 1, -1, 1, -1, 1, 2, -1, 2, -2, -2,
1074 7, -7, 1, -1, 3, -3, 8, -8, 1, -1, 5, -5, 3, -3, 1, 4,
1075 2, -4, -1, -2, 1, 1, -1, -1, 9, 1, 1, -9, -1, 1, -1, -1,
1076 1, -1, 3, -3, 1, 3, -3, -1, 3, -3, 1, -1, 10, 1, -10, -1,
1077 1, 4, -1, 2, 1, -1, 1, -2, 1, -4, -1, 6, -6, -1, 1, 1,
1078 1, -1, 1, 1, -1, -1, -1, 1, 11, -1, -2, 4, -1, 2, -11, 5,
1079 -5, -4, -1, 1, 4, 1, -4, -1, -2, 2, 1, -1, 12, 1, -2, 1,
1080 -12, 4, 2, 1, -1, -4, 4, -4, 2, -2, -1, 1, 7, -1, -1, -7,
1081 -1, -3, 1, 3, 1, 5, 2, 1, -1, -5, 13, -2, -1, 2, -2, -13,
1082 1, -1, 5, 6, 5, -5, 1, 1, -6, 1, -1, -1, -5, -1, 14, 2,
1083 -2, 1, -14, -1, 8, 1, -1, -8, 1, 5, 1, 5, -5, 1, -1, 1,
1084 -5, -1, 15, 1, -1, -1, -1, 3, -15, -3, 6, 1, 16, -1, 6, -6,
1085 -6, 1, -1, 1, -16, 1, 7, -1, 1, -1, -6, -3, 6, -7, 3, -1}
1091 {0, 1, 1, 2, 2, 3, 3, 4, 4, 1, 1, 5, 5, 6, 6, 7,
1092 7, 8, 8, 9, 9, 2, 2, 10, 10, 1, 1, 11, 11, 12, 12, 3,
1093 3, 13, 13, 0, 14, 14, 16, 15, 16, 15, 4, 4, 17, 1, 17, 1,
1094 5, 5, 18, 18, 2, 2, 6, 6, 8, 19, 7, 8, 7, 19, 20, 20,
1095 21, 21, 22, 24, 22, 24, 23, 23, 1, 1, 25, 25, 3, 3, 26, 26,
1096 9, 9, 27, 27, 28, 28, 33, 29, 4, 33, 29, 1, 4, 1, 32, 32,
1097 2, 2, 31, 10, 30, 10, 30, 31, 34, 34, 5, 5, 36, 36, 35, 41,
1098 35, 11, 41, 11, 37, 1, 8, 8, 37, 6, 1, 6, 40, 7, 7, 40,
1099 12, 38, 12, 39, 39, 38, 49, 13, 49, 13, 3, 42, 3, 42, 16, 16,
1100 43, 43, 14, 14, 1, 1, 44, 15, 44, 15, 2, 2, 57, 48, 50, 48,
1101 57, 50, 4, 45, 45, 4, 46, 47, 47, 46, 1, 51, 1, 17, 17, 51,
1102 8, 9, 9, 5, 58, 8, 58, 5, 52, 52, 55, 56, 53, 56, 55, 59,
1103 59, 53, 54, 1, 6, 54, 7, 7, 6, 1, 2, 3, 2, 3, 64, 60,
1104 60, 10, 10, 64, 61, 62, 61, 63, 1, 63, 62, 1, 18, 24, 18, 4,
1105 25, 4, 8, 21, 21, 1, 24, 22, 25, 22, 8, 11, 19, 11, 23, 1,
1106 20, 23, 19, 20, 5, 12, 5, 1, 16, 2, 12, 13, 2, 13, 1, 16},
1109 { 0, 1, -1, 1, -1, 1, -1, 1, -1, 2, -2, 1, -1, 1, -1, 1,
1110 -1, 1, -1, 1, -1, 2, -2, 1, -1, 3, -3, 1, -1, 1, -1, 2,
1111 -2, 1, -1, 0, 1, -1, 1, 1, -1, -1, 2, -2, 1, 4, -1, -4,
1112 2, -2, 1, -1, -3, 3, 2, -2, 2, 1, 2, -2, -2, -1, 1, -1,
1113 1, -1, 1, 1, -1, -1, 1, -1, 5, -5, 1, -1, 3, -3, 1, -1,
1114 2, -2, 1, -1, 1, -1, 1, 1, 3, -1, -1, 6, -3, -6, -1, 1,
1115 4, -4, 1, 2, 1, -2, -1, -1, 1, -1, 3, -3, 1, -1, 1, 1,
1116 -1, 2, -1, -2, 1, 7, -3, 3, -1, 3, -7, -3, 1, -3, 3, -1,
1117 2, 1, -2, 1, -1, -1, 1, 2, -1, -2, -4, -1, 4, 1, 2, -2,
1118 1, -1, -2, 2, 8, -8, -1, 2, 1, -2, -5, 5, 1, -1, -1, 1,
1119 -1, 1, 4, -1, 1, -4, -1, -1, 1, 1, 9, 1, -9, 2, -2, -1,
1120 -4, 3, -3, -4, -1, 4, 1, 4, 1, -1, 1, -1, 1, 1, -1, 1,
1121 -1, -1, -1, 10, 4, 1, 4, -4, -4, -10, 6, 5, -6, -5, 1, -1,
1122 1, 3, -3, -1, 1, -1, -1, -1, 11, 1, 1, -11, -2, -2, 2, 5,
1123 -2, -5, -5, 2, -2, 12, 2, -2, 2, 2, 5, -3, -2, 3, -2, -12,
1124 -2, 2, 2, 2, -5, 3, 5, 13, -3, 7, -3, -3, -7, 3, -13, 3}
1130 {0, 1, 1, 1, 2, 2, 1, 3, 3, 1, 1, 1, 4, 4, 1, 5,
1131 2, 1, 5, 2, 1, 1, 6, 6, 1, 1, 1, 1, 1, 7, 3, 1,
1132 2, 3, 0, 1, 2, 7, 1, 1, 1, 8, 1, 1, 8, 1, 1, 1,
1133 9, 1, 9, 1, 2, 1, 1, 2, 1, 1, 10, 4, 1, 10, 1, 4,
1134 1, 1, 1, 1, 1, 3, 1, 1, 1, 3, 2, 1, 5, 1, 1, 1,
1135 2, 5, 1, 11, 1, 11, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1136 2, 1, 6, 1, 6, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 12,
1137 3, 1, 12, 1, 1, 1, 2, 1, 1, 3, 1, 1, 1, 1, 1, 1,
1138 4, 1, 1, 1, 2, 1, 1, 4, 1, 1, 1, 1, 1, 1, 2, 1,
1139 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 2, 1, 1, 5,
1140 1, 1, 1, 1, 1, 7, 1, 7, 1, 1, 2, 3, 1, 1, 1, 1,
1141 5, 1, 1, 1, 1, 1, 1, 2, 13, 1, 1, 1, 1, 1, 1, 1,
1142 1, 1, 1, 1, 1, 1, 1, 1, 13, 2, 1, 1, 4, 1, 1, 1,
1143 3, 1, 6, 1, 1, 1, 14, 1, 1, 1, 1, 1, 14, 6, 1, 1,
1144 1, 1, 15, 2, 4, 1, 2, 3, 15, 1, 1, 1, 8, 1, 1, 8,
1145 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1},
1148 { 0, 1, -1, 2, 1, -1, -2, 1, -1, 3, -3, 4, 1, -1, -4, 1,
1149 2, 5, -1, -2, -5, 6, 1, -1, -6, 7, -7, 8, -8, 1, 2, 9,
1150 3, -2, 0, -9, -3, -1, 10, -10, 11, 1, -11, 12, -1, -12, 13, -13,
1151 1, 14, -1, -14, 4, 15, -15, -4, 16, -16, 1, 2, 17, -1, -17, -2,
1152 18, -18, 19, -19, 20, 3, -20, 21, -21, -3, 5, 22, 2, -22, -23, 23,
1153 -5, -2, 24, 1, -24, -1, 25, -25, 26, -26, -27, 27, 28, 29, -28, -29,
1154 6, 30, 2, -31, -2, -30, 31, -6, -32, 32, 33, -33, 34, -35, -34, 1,
1155 4, -36, -1, 35, 37, 36, 7, -37, 38, -4, -38, 39, 41, 40, -40, -39,
1156 3, 42, -43, -41, -7, -42, 43, -3, 44, -44, 45, -45, 46, 47, 8, -47,
1157 -48, -46, 50, -50, 48, 49, 51, -49, 52, -52, 5, -51, -8, -53, 53, 3,
1158 -56, 56, 55, 54, -54, 2, 60, -2, -55, 58, 9, -5, 59, 57, -57, -63,
1159 -3, -58, -60, -61, 61, -59, -62, -9, 1, 64, 62, 69, -64, 63, 65, -67,
1160 -68, 66, -65, 68, -66, -69, 67, -70, -1, 10, 71, -71, 4, 73, 72, 70,
1161 6, -76, -3, 74, -78, -74, 1, 78, 80, -72, -75, 76, -1, 3, -73, 79,
1162 75, 77, 1, 11, -4, -79, -10, -6, -1, -77, -83, -80, 2, 81, -84, -2,
1163 83, -81, 82, -82, 84, -87, -86, 85, -11, -85, 86, -89, 87, -88, 88, 89}
1169 {1, 1, 0, 2, 1, 2, 1, 3, 3, 1, 1, 4, 4, 2, 2, 1,
1170 1, 5, 5, 6, 1, 6, 1, 7, 7, 3, 3, 2, 8, 2, 8, 1,
1171 1, 0, 9, 9, 1, 1, 10, 4, 10, 4, 11, 11, 2, 1, 2, 1,
1172 12, 12, 3, 3, 1, 1, 13, 5, 5, 13, 14, 1, 1, 14, 2, 2,
1173 6, 6, 15, 1, 1, 15, 16, 4, 7, 16, 4, 7, 1, 1, 3, 3,
1174 8, 8, 2, 2, 1, 1, 17, 17, 1, 1, 18, 18, 5, 5, 2, 2,
1175 1, 1, 9, 19, 9, 19, 20, 3, 3, 20, 1, 10, 21, 1, 10, 4,
1176 4, 21, 22, 6, 6, 22, 1, 1, 23, 24, 2, 2, 23, 24, 11, 1,
1177 1, 11, 7, 25, 7, 1, 1, 25, 8, 8, 3, 26, 3, 1, 12, 2,
1178 2, 26, 1, 12, 5, 5, 27, 4, 1, 4, 1, 27, 28, 1, 28, 13,
1179 1, 13, 2, 29, 2, 1, 32, 6, 1, 30, 14, 29, 14, 6, 3, 31,
1180 3, 1, 30, 1, 32, 31, 33, 9, 33, 1, 1, 7, 9, 7, 2, 2,
1181 1, 1, 4, 36, 34, 4, 5, 10, 10, 5, 34, 1, 1, 35, 8, 8,
1182 36, 3, 35, 1, 15, 3, 2, 1, 16, 15, 16, 2, 37, 1, 37, 1,
1183 1, 1, 6, 6, 38, 1, 38, 11, 1, 39, 39, 40, 11, 2, 41, 4,
1184 40, 1, 2, 4, 1, 1, 1, 41, 3, 1, 3, 1, 5, 7, 5, 7},
1187 { 1, -1, 0, 1, 2, -1, -2, 1, -1, 3, -3, 1, -1, 2, -2, 4,
1188 -4, 1, -1, 1, 5, -1, -5, 1, -1, 2, -2, 3, 1, -3, -1, 6,
1189 -6, 0, 1, -1, 7, -7, 1, 2, -1, -2, 1, -1, 4, 8, -4, -8,
1190 1, -1, 3, -3, 9, -9, 1, 2, -2, -1, 1, 10, -10, -1, 5, -5,
1191 2, -2, 1, 11, -11, -1, 1, 3, 2, -1, -3, -2, 12, -12, 4, -4,
1192 2, -2, -6, 6, 13, -13, 1, -1, 14, -14, 1, -1, 3, -3, 7, -7,
1193 15, -15, 2, 1, -2, -1, 1, 5, -5, -1, -16, 2, 1, 16, -2, 4,
1194 -4, -1, 1, 3, -3, -1, 17, -17, 1, 1, -8, 8, -1, -1, 2, 18,
1195 -18, -2, 3, 1, -3, 19, -19, -1, 3, -3, 6, 1, -6, 20, 2, 9,
1196 -9, -1, -20, -2, 4, -4, 1, -5, 21, 5, -21, -1, 1, -22, -1, 2,
1197 22, -2, 10, 1, -10, 23, 1, 4, -23, 1, 2, -1, -2, -4, -7, 1,
1198 7, -24, -1, 24, -1, -1, 1, 3, -1, -25, 25, 4, -3, -4, 11, -11,
1199 26, -26, 6, 1, 1, -6, -5, -3, 3, 5, -1, -27, 27, 1, 4, -4,
1200 -1, -8, -1, 28, 2, 8, -12, -28, -2, -2, 2, 12, -1, 29, 1, -29,
1201 30, -30, 5, -5, 1, -31, -1, 3, 31, -1, 1, 1, -3, -13, 1, -7,
1202 -1, -32, 13, 7, 32, 33, -33, -1, -9, -34, 9, 34, -6, 5, 6, -5}
1208 {1, 1, 0, 1, 1, 2, 2, 1, 1, 3, 3, 1, 1, 0, 2, 2,
1209 4, 1, 4, 1, 1, 1, 5, 5, 1, 1, 6, 6, 2, 2, 1, 1,
1210 3, 3, 7, 7, 1, 1, 8, 8, 1, 1, 2, 2, 1, 9, 1, 9,
1211 4, 4, 10, 1, 1, 10, 1, 1, 11, 11, 3, 3, 1, 2, 1, 2,
1212 1, 1, 12, 12, 5, 5, 1, 1, 13, 1, 1, 13, 2, 2, 1, 1,
1213 6, 6, 1, 1, 4, 14, 4, 14, 3, 1, 3, 1, 1, 1, 15, 7,
1214 15, 2, 2, 7, 1, 1, 1, 8, 1, 8, 16, 16, 1, 1, 1, 1,
1215 2, 1, 1, 2, 1, 1, 3, 5, 5, 3, 4, 1, 1, 4, 1, 1,
1216 17, 17, 9, 1, 1, 9, 2, 2, 1, 1, 10, 10, 1, 6, 1, 1,
1217 6, 18, 1, 1, 18, 1, 1, 1, 2, 2, 3, 1, 3, 1, 1, 1,
1218 4, 1, 19, 1, 19, 7, 1, 1, 20, 1, 4, 20, 1, 7, 11, 2,
1219 1, 11, 21, 2, 8, 5, 1, 8, 1, 5, 21, 1, 1, 1, 22, 1,
1220 1, 22, 1, 1, 3, 3, 1, 23, 2, 12, 24, 1, 1, 2, 1, 1,
1221 12, 23, 1, 1, 24, 1, 1, 1, 4, 1, 1, 1, 2, 1, 6, 6,
1222 4, 2, 1, 1, 1, 1, 1, 1, 1, 14, 13, 3, 1, 25, 9, 25,
1223 14, 1, 9, 3, 13, 1, 1, 1, 1, 1, 10, 1, 1, 2, 10, 2},
1226 {-20, -1, 0, 2, -2, 1, -1, 3, -3, 1, -1, 4, -4, 0, 2, -2,
1227 1, 5, -1, -5, 6, -6, 1, -1, 7, -7, 1, -1, 3, -3, 8, -8,
1228 2, -2, 1, -1, 9, -9, 1, -1, 10, -10, 4, -4, 11, 1, -11, -1,
1229 2, -2, 1, 12, -12, -1, 13, -13, 1, -1, 3, -3, 14, 5, -14, -5,
1230 -15, 15, -1, 1, 2, -2, 16, -16, 1, 17, -17, -1, 6, -6, 18, -18,
1231 2, -2, -19, 19, -3, 1, 3, -1, 4, 20, -4, 1, -21, 21, 1, 2,
1232 -1, -7, 7, -2, 22, -22, 23, 2, -23, -2, 1, -1, -24, 24, -25, 25,
1233 -8, -26, 26, 8, -27, 27, 5, 3, -3, -5, -4, 28, -28, 4, 29, -29,
1234 1, -1, -2, -30, 30, 2, 9, -9, -31, 31, 2, -2, -32, 3, 32, -33,
1235 -3, 1, 33, -34, -1, 34, -35, 35, -10, 10, -6, 36, 6, -36, 37, -37,
1236 -5, 38, 1, -38, -1, 3, 39, -39, -1, 40, 5, 1, -40, -3, 2, -11,
1237 -41, -2, 1, 11, -3, -4, 41, 3, 42, 4, -1, -43, -42, 43, 1, -44,
1238 45, -1, 44, -45, -7, 7, -46, 1, -12, 2, 1, -47, 46, 12, 47, 48,
1239 -2, -1, -48, 49, -1, -50, -49, 50, -6, -51, 51, 52, -13, 53, -4, 4,
1240 6, 13, -53, -52, -54, 55, 54, -55, -56, -2, 2, -8, 56, 1, -3, -1,
1241 2, 58, 3, 8, -2, 57, -58, -60, -59, -57, -3, 60, 59, -14, 3, 14}
1247 {1, 1, 0, 2, 2, 1, 1, 3, 3, 4, 4, 5, 5, 1, 1, 6,
1248 6, 2, 2, 7, 7, 8, 8, 1, 1, 3, 3, 9, 9, 10, 10, 1,
1249 1, 2, 2, 4, 4, 11, 0, 11, 12, 12, 13, 13, 1, 1, 5, 5,
1250 14, 14, 15, 16, 15, 16, 3, 3, 1, 6, 1, 6, 2, 2, 7, 7,
1251 8, 8, 17, 17, 1, 1, 4, 4, 18, 18, 2, 2, 1, 19, 1, 20,
1252 19, 20, 21, 21, 3, 3, 22, 22, 5, 5, 24, 1, 1, 23, 9, 23,
1253 24, 9, 2, 2, 10, 1, 1, 10, 6, 6, 25, 4, 4, 25, 7, 7,
1254 26, 8, 1, 8, 3, 1, 26, 3, 11, 11, 27, 27, 2, 28, 1, 2,
1255 28, 1, 12, 12, 5, 5, 29, 13, 13, 29, 32, 1, 1, 33, 31, 30,
1256 32, 4, 30, 33, 4, 31, 3, 14, 1, 1, 3, 34, 34, 2, 2, 14,
1257 6, 6, 35, 36, 35, 36, 1, 15, 1, 16, 16, 15, 7, 9, 7, 9,
1258 37, 8, 8, 37, 1, 1, 39, 2, 38, 39, 2, 40, 5, 38, 40, 5,
1259 3, 3, 4, 4, 10, 10, 1, 1, 1, 1, 41, 2, 41, 2, 6, 6,
1260 1, 1, 11, 42, 11, 43, 3, 42, 3, 17, 4, 43, 1, 17, 7, 1,
1261 8, 44, 4, 7, 44, 5, 8, 2, 5, 1, 2, 48, 45, 1, 12, 45,
1262 12, 48, 13, 13, 1, 9, 9, 46, 1, 46, 47, 47, 49, 18, 18, 49},
1265 { 1, -1, 0, 1, -1, 2, -2, 1, -1, 1, -1, 1, -1, 3, -3, 1,
1266 -1, -2, 2, 1, -1, 1, -1, 4, -4, -2, 2, 1, -1, 1, -1, 5,
1267 -5, -3, 3, 2, -2, 1, 0, -1, 1, -1, 1, -1, 6, -6, 2, -2,
1268 1, -1, 1, 1, -1, -1, -3, 3, 7, 2, -7, -2, -4, 4, 2, -2,
1269 2, -2, 1, -1, 8, -8, 3, -3, 1, -1, -5, 5, 9, 1, -9, 1,
1270 -1, -1, 1, -1, -4, 4, 1, -1, 3, -3, 1, -10, 10, 1, 2, -1,
1271 -1, -2, 6, -6, 2, 11, -11, -2, 3, -3, 1, -4, 4, -1, 3, -3,
1272 1, 3, 12, -3, -5, -12, -1, 5, 2, -2, 1, -1, -7, 1, 13, 7,
1273 -1, -13, 2, -2, 4, -4, 1, 2, -2, -1, 1, 14, -14, 1, 1, 1,
1274 -1, -5, -1, -1, 5, -1, -6, 2, -15, 15, 6, 1, -1, -8, 8, -2,
1275 -4, 4, 1, 1, -1, -1, 16, 2, -16, -2, 2, -2, 4, 3, -4, -3,
1276 -1, -4, 4, 1, -17, 17, -1, -9, 1, 1, 9, 1, -5, -1, -1, 5,
1277 -7, 7, 6, -6, 3, -3, 18, -18, 19, -19, 1, -10, -1, 10, -5, 5,
1278 20, -20, -3, 1, 3, 1, 8, -1, -8, 2, 7, -1, -21, -2, 5, 21,
1279 5, -1, -7, -5, 1, -6, -5, -11, 6, 22, 11, 1, 1, -22, -3, -1,
1280 3, -1, 3, -3, -23, 4, -4, 1, 23, -1, 1, -1, 1, -2, 2, -1}
1286 {1, 1, 1, 1, 0, 2, 2, 1, 1, 3, 3, 0, 1, 1, 2, 2,
1287 4, 4, 1, 1, 5, 5, 1, 1, 2, 2, 3, 3, 6, 6, 1, 1,
1288 7, 7, 8, 1, 8, 2, 2, 1, 4, 4, 1, 3, 1, 3, 9, 9,
1289 2, 2, 1, 5, 1, 5, 10, 10, 1, 1, 11, 11, 3, 6, 3, 4,
1290 4, 6, 2, 2, 1, 12, 1, 12, 7, 13, 7, 13, 1, 1, 8, 8,
1291 2, 2, 14, 14, 16, 15, 16, 5, 5, 1, 3, 15, 1, 3, 4, 4,
1292 1, 1, 17, 17, 2, 2, 6, 6, 1, 18, 1, 18, 22, 21, 22, 21,
1293 25, 24, 25, 19, 9, 20, 9, 23, 19, 24, 20, 3, 23, 7, 3, 1,
1294 1, 7, 28, 26, 29, 5, 28, 26, 5, 8, 29, 4, 8, 27, 2, 2,
1295 4, 27, 1, 1, 10, 36, 10, 33, 33, 36, 30, 1, 32, 32, 1, 30,
1296 6, 31, 31, 35, 3, 6, 11, 11, 3, 2, 35, 2, 34, 1, 34, 1,
1297 37, 37, 12, 7, 12, 5, 41, 5, 4, 7, 1, 8, 13, 4, 1, 41,
1298 13, 38, 8, 38, 9, 1, 40, 40, 9, 1, 39, 2, 2, 49, 39, 42,
1299 3, 3, 14, 16, 49, 14, 16, 42, 43, 43, 6, 6, 15, 1, 1, 15,
1300 44, 44, 1, 1, 50, 48, 4, 5, 4, 7, 5, 2, 10, 10, 48, 7,
1301 50, 45, 2, 1, 45, 8, 8, 1, 46, 46, 3, 47, 47, 3, 1, 1},
1304 { 1, -1, 2, -2, 0, 1, -1, 3, -3, 1, -1, 0, 4, -4, 2, -2,
1305 1, -1, 5, -5, 1, -1, 6, -6, 3, -3, 2, -2, 1, -1, 7, -7,
1306 1, -1, 1, 8, -1, 4, -4, -8, 2, -2, 9, 3, -9, -3, 1, -1,
1307 5, -5, 10, 2, -10, -2, 1, -1, 11, -11, 1, -1, -4, 2, 4, 3,
1308 -3, -2, 6, -6, 12, 1, -12, -1, 2, 1, -2, -1, 13, -13, 2, -2,
1309 7, -7, 1, -1, 1, 1, -1, 3, -3, 14, 5, -1, -14, -5, 4, -4,
1310 15, -15, 1, -1, 8, -8, -3, 3, 16, 1, -16, -1, 1, 1, -1, -1,
1311 1, 1, -1, 1, 2, 1, -2, 1, -1, -1, -1, 6, -1, 3, -6, 17,
1312 -17, -3, 1, 1, 1, 4, -1, -1, -4, 3, -1, 5, -3, -1, -9, 9,
1313 -5, 1, 18, -18, 2, 1, -2, 1, -1, -1, 1, 19, -1, 1, -19, -1,
1314 4, 1, -1, 1, 7, -4, -2, 2, -7, 10, -1, -10, 1, 20, -1, -20,
1315 1, -1, 2, 4, -2, 5, 1, -5, 6, -4, 21, 4, 2, -6, -21, -1,
1316 -2, 1, -4, -1, -3, 22, -1, 1, 3, -22, -1, 11, -11, 1, 1, 1,
1317 8, -8, 2, 2, -1, -2, -2, -1, 1, -1, -5, 5, 2, 23, -23, -2,
1318 1, -1, 24, -24, -1, -1, 7, 6, -7, 5, -6, 12, -3, 3, 1, -5,
1319 1, 1, -12, 25, -1, -5, 5, -25, -1, 1, 9, 1, -1, -9, 26, -26}