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
44 typedef void (*ivi_mc_func) (int16_t *buf, const int16_t *ref_buf,
45 uint32_t pitch, int mc_type);
47 static int ivi_mc(IVIBandDesc *band, ivi_mc_func mc,
48 int offs, int mv_x, int mv_y, int mc_type)
50 int ref_offs = offs + mv_y * band->pitch + mv_x;
51 int buf_size = band->pitch * band->aheight;
52 int min_size = band->pitch * (band->blk_size - 1) + band->blk_size;
53 int ref_size = (mc_type > 1) * band->pitch + (mc_type & 1);
55 if (offs < 0 || ref_offs < 0 || !band->ref_buf)
56 return AVERROR_INVALIDDATA;
57 if (buf_size - min_size < offs)
58 return AVERROR_INVALIDDATA;
59 if (buf_size - min_size - ref_size < ref_offs)
60 return AVERROR_INVALIDDATA;
62 mc(band->buf + offs, band->ref_buf + ref_offs, band->pitch, mc_type);
68 * Reverse "nbits" bits of the value "val" and return the result
69 * in the least significant bits.
71 static uint16_t inv_bits(uint16_t val, int nbits)
76 res = ff_reverse[val] >> (8 - nbits);
78 res = ((ff_reverse[val & 0xFF] << 8) +
79 (ff_reverse[val >> 8])) >> (16 - nbits);
85 * Generate a huffman codebook from the given descriptor
86 * and convert it into the Libav VLC table.
88 * @param[in] cb pointer to codebook descriptor
89 * @param[out] vlc where to place the generated VLC table
90 * @param[in] flag flag: 1 - for static or 0 for dynamic tables
91 * @return result code: 0 - OK, -1 = error (invalid codebook descriptor)
93 static int ivi_create_huff_from_desc(const IVIHuffDesc *cb, VLC *vlc, int flag)
95 int pos, i, j, codes_per_row, prefix, not_last_row;
96 uint16_t codewords[256]; /* FIXME: move this temporal storage out? */
99 pos = 0; /* current position = 0 */
101 for (i = 0; i < cb->num_rows; i++) {
102 codes_per_row = 1 << cb->xbits[i];
103 not_last_row = (i != cb->num_rows - 1);
104 prefix = ((1 << i) - 1) << (cb->xbits[i] + not_last_row);
106 for (j = 0; j < codes_per_row; j++) {
107 if (pos >= 256) /* Some Indeo5 codebooks can have more than 256 */
108 break; /* elements, but only 256 codes are allowed! */
110 bits[pos] = i + cb->xbits[i] + not_last_row;
111 if (bits[pos] > IVI_VLC_BITS)
112 return AVERROR_INVALIDDATA; /* invalid descriptor */
114 codewords[pos] = inv_bits((prefix | j), bits[pos]);
122 /* number of codewords = pos */
123 return init_vlc(vlc, IVI_VLC_BITS, pos, bits, 1, 1, codewords, 2, 2,
124 (flag ? INIT_VLC_USE_NEW_STATIC : 0) | INIT_VLC_LE);
127 av_cold void ff_ivi_init_static_vlc(void)
130 static VLC_TYPE table_data[8192 * 16][2];
131 static int initialized_vlcs = 0;
133 if (initialized_vlcs)
135 for (i = 0; i < 8; i++) {
136 ivi_mb_vlc_tabs[i].table = table_data + i * 2 * 8192;
137 ivi_mb_vlc_tabs[i].table_allocated = 8192;
138 ivi_create_huff_from_desc(&ff_ivi_mb_huff_desc[i],
139 &ivi_mb_vlc_tabs[i], 1);
140 ivi_blk_vlc_tabs[i].table = table_data + (i * 2 + 1) * 8192;
141 ivi_blk_vlc_tabs[i].table_allocated = 8192;
142 ivi_create_huff_from_desc(&ff_ivi_blk_huff_desc[i],
143 &ivi_blk_vlc_tabs[i], 1);
145 initialized_vlcs = 1;
149 * Copy huffman codebook descriptors.
151 * @param[out] dst ptr to the destination descriptor
152 * @param[in] src ptr to the source descriptor
154 static void ivi_huff_desc_copy(IVIHuffDesc *dst, const IVIHuffDesc *src)
156 dst->num_rows = src->num_rows;
157 memcpy(dst->xbits, src->xbits, src->num_rows);
161 * Compare two huffman codebook descriptors.
163 * @param[in] desc1 ptr to the 1st descriptor to compare
164 * @param[in] desc2 ptr to the 2nd descriptor to compare
165 * @return comparison result: 0 - equal, 1 - not equal
167 static int ivi_huff_desc_cmp(const IVIHuffDesc *desc1,
168 const IVIHuffDesc *desc2)
170 return desc1->num_rows != desc2->num_rows ||
171 memcmp(desc1->xbits, desc2->xbits, desc1->num_rows);
174 int ff_ivi_dec_huff_desc(GetBitContext *gb, int desc_coded, int which_tab,
175 IVIHuffTab *huff_tab, AVCodecContext *avctx)
178 IVIHuffDesc new_huff;
181 /* select default table */
182 huff_tab->tab = (which_tab) ? &ivi_blk_vlc_tabs[7]
183 : &ivi_mb_vlc_tabs [7];
187 huff_tab->tab_sel = get_bits(gb, 3);
188 if (huff_tab->tab_sel == 7) {
189 /* custom huffman table (explicitly encoded) */
190 new_huff.num_rows = get_bits(gb, 4);
191 if (!new_huff.num_rows) {
192 av_log(avctx, AV_LOG_ERROR, "Empty custom Huffman table!\n");
193 return AVERROR_INVALIDDATA;
196 for (i = 0; i < new_huff.num_rows; i++)
197 new_huff.xbits[i] = get_bits(gb, 4);
199 /* Have we got the same custom table? Rebuild if not. */
200 if (ivi_huff_desc_cmp(&new_huff, &huff_tab->cust_desc)) {
201 ivi_huff_desc_copy(&huff_tab->cust_desc, &new_huff);
203 if (huff_tab->cust_tab.table)
204 ff_free_vlc(&huff_tab->cust_tab);
205 result = ivi_create_huff_from_desc(&huff_tab->cust_desc,
206 &huff_tab->cust_tab, 0);
208 // reset faulty description
209 huff_tab->cust_desc.num_rows = 0;
210 av_log(avctx, AV_LOG_ERROR,
211 "Error while initializing custom vlc table!\n");
215 huff_tab->tab = &huff_tab->cust_tab;
217 /* select one of predefined tables */
218 huff_tab->tab = (which_tab) ? &ivi_blk_vlc_tabs[huff_tab->tab_sel]
219 : &ivi_mb_vlc_tabs [huff_tab->tab_sel];
226 * Free planes, bands and macroblocks buffers.
228 * @param[in] planes pointer to the array of the plane descriptors
230 static av_cold void ivi_free_buffers(IVIPlaneDesc *planes)
234 for (p = 0; p < 3; p++) {
235 for (b = 0; b < planes[p].num_bands; b++) {
236 av_freep(&planes[p].bands[b].bufs[0]);
237 av_freep(&planes[p].bands[b].bufs[1]);
238 av_freep(&planes[p].bands[b].bufs[2]);
240 if (planes[p].bands[b].blk_vlc.cust_tab.table)
241 ff_free_vlc(&planes[p].bands[b].blk_vlc.cust_tab);
242 for (t = 0; t < planes[p].bands[b].num_tiles; t++)
243 av_freep(&planes[p].bands[b].tiles[t].mbs);
244 av_freep(&planes[p].bands[b].tiles);
246 av_freep(&planes[p].bands);
247 planes[p].num_bands = 0;
251 av_cold int ff_ivi_init_planes(IVIPlaneDesc *planes, const IVIPicConfig *cfg)
254 uint32_t b_width, b_height, align_fac, width_aligned,
255 height_aligned, buf_size;
258 ivi_free_buffers(planes);
260 if (cfg->pic_width < 1 || cfg->pic_height < 1 ||
261 cfg->luma_bands < 1 || cfg->chroma_bands < 1)
262 return AVERROR_INVALIDDATA;
264 /* fill in the descriptor of the luminance plane */
265 planes[0].width = cfg->pic_width;
266 planes[0].height = cfg->pic_height;
267 planes[0].num_bands = cfg->luma_bands;
269 /* fill in the descriptors of the chrominance planes */
270 planes[1].width = planes[2].width = (cfg->pic_width + 3) >> 2;
271 planes[1].height = planes[2].height = (cfg->pic_height + 3) >> 2;
272 planes[1].num_bands = planes[2].num_bands = cfg->chroma_bands;
274 for (p = 0; p < 3; p++) {
275 planes[p].bands = av_mallocz(planes[p].num_bands * sizeof(IVIBandDesc));
276 if (!planes[p].bands)
277 return AVERROR(ENOMEM);
279 /* select band dimensions: if there is only one band then it
280 * has the full size, if there are several bands each of them
281 * has only half size */
282 b_width = planes[p].num_bands == 1 ? planes[p].width
283 : (planes[p].width + 1) >> 1;
284 b_height = planes[p].num_bands == 1 ? planes[p].height
285 : (planes[p].height + 1) >> 1;
287 /* luma band buffers will be aligned on 16x16 (max macroblock size) */
288 /* chroma band buffers will be aligned on 8x8 (max macroblock size) */
289 align_fac = p ? 8 : 16;
290 width_aligned = FFALIGN(b_width , align_fac);
291 height_aligned = FFALIGN(b_height, align_fac);
292 buf_size = width_aligned * height_aligned * sizeof(int16_t);
294 for (b = 0; b < planes[p].num_bands; b++) {
295 band = &planes[p].bands[b]; /* select appropriate plane/band */
298 band->width = b_width;
299 band->height = b_height;
300 band->pitch = width_aligned;
301 band->aheight = height_aligned;
302 band->bufs[0] = av_mallocz(buf_size);
303 band->bufs[1] = av_mallocz(buf_size);
304 if (!band->bufs[0] || !band->bufs[1])
305 return AVERROR(ENOMEM);
307 /* allocate the 3rd band buffer for scalability mode */
308 if (cfg->luma_bands > 1) {
309 band->bufs[2] = av_mallocz(buf_size);
311 return AVERROR(ENOMEM);
313 /* reset custom vlc */
314 planes[p].bands[0].blk_vlc.cust_desc.num_rows = 0;
321 static int ivi_init_tiles(IVIBandDesc *band, IVITile *ref_tile,
322 int p, int b, int t_height, int t_width)
325 IVITile *tile = band->tiles;
327 for (y = 0; y < band->height; y += t_height) {
328 for (x = 0; x < band->width; x += t_width) {
331 tile->mb_size = band->mb_size;
332 tile->width = FFMIN(band->width - x, t_width);
333 tile->height = FFMIN(band->height - y, t_height);
334 tile->is_empty = tile->data_size = 0;
335 /* calculate number of macroblocks */
336 tile->num_MBs = IVI_MBs_PER_TILE(tile->width, tile->height,
339 av_freep(&tile->mbs);
340 tile->mbs = av_malloc(tile->num_MBs * sizeof(IVIMbInfo));
342 return AVERROR(ENOMEM);
346 if (tile->num_MBs != ref_tile->num_MBs)
347 return AVERROR_INVALIDDATA;
348 tile->ref_mbs = ref_tile->mbs;
358 av_cold int ff_ivi_init_tiles(IVIPlaneDesc *planes,
359 int tile_width, int tile_height)
361 int p, b, x_tiles, y_tiles, t_width, t_height, ret;
364 for (p = 0; p < 3; p++) {
365 t_width = !p ? tile_width : (tile_width + 3) >> 2;
366 t_height = !p ? tile_height : (tile_height + 3) >> 2;
368 if (!p && planes[0].num_bands == 4) {
373 for (b = 0; b < planes[p].num_bands; b++) {
374 band = &planes[p].bands[b];
375 x_tiles = IVI_NUM_TILES(band->width, t_width);
376 y_tiles = IVI_NUM_TILES(band->height, t_height);
377 band->num_tiles = x_tiles * y_tiles;
379 av_freep(&band->tiles);
380 band->tiles = av_mallocz(band->num_tiles * sizeof(IVITile));
382 return AVERROR(ENOMEM);
384 /* use the first luma band as reference for motion vectors
386 ret = ivi_init_tiles(band, planes[0].bands[0].tiles,
387 p, b, t_height, t_width);
397 * Decode size of the tile data.
398 * The size is stored as a variable-length field having the following format:
399 * if (tile_data_size < 255) than this field is only one byte long
400 * if (tile_data_size >= 255) than this field four is byte long: 0xFF X1 X2 X3
401 * where X1-X3 is size of the tile data
403 * @param[in,out] gb the GetBit context
404 * @return size of the tile data in bytes
406 static int ivi_dec_tile_data_size(GetBitContext *gb)
412 len = get_bits(gb, 8);
414 len = get_bits_long(gb, 24);
417 /* align the bitstream reader on the byte boundary */
423 static int ivi_dc_transform(IVIBandDesc *band, int *prev_dc, int buf_offs,
426 int buf_size = band->pitch * band->aheight - buf_offs;
427 int min_size = (blk_size - 1) * band->pitch + blk_size;
429 if (!band->dc_transform)
433 if (min_size > buf_size)
434 return AVERROR_INVALIDDATA;
436 band->dc_transform(prev_dc, band->buf + buf_offs,
437 band->pitch, blk_size);
442 static int ivi_decode_coded_blocks(GetBitContext *gb, IVIBandDesc *band,
443 ivi_mc_func mc, int mv_x, int mv_y,
444 int *prev_dc, int is_intra, int mc_type,
445 uint32_t quant, int offs,
446 AVCodecContext *avctx)
448 const uint16_t *base_tab = is_intra ? band->intra_base : band->inter_base;
449 RVMapDesc *rvmap = band->rv_map;
450 uint8_t col_flags[8];
452 uint32_t sym = 0, lo, hi, q;
454 int blk_size = band->blk_size;
455 int num_coeffs = blk_size * blk_size;
456 int col_mask = blk_size - 1;
458 int min_size = band->pitch * (band->transform_size - 1) +
459 band->transform_size;
460 int buf_size = band->pitch * band->aheight - offs;
462 if (min_size > buf_size)
463 return AVERROR_INVALIDDATA;
466 av_log(avctx, AV_LOG_ERROR, "Scan pattern is not set.\n");
467 return AVERROR_INVALIDDATA;
470 /* zero transform vector */
471 memset(trvec, 0, num_coeffs * sizeof(trvec[0]));
472 /* zero column flags */
473 memset(col_flags, 0, sizeof(col_flags));
474 while (scan_pos <= num_coeffs) {
475 sym = get_vlc2(gb, band->blk_vlc.tab->table,
477 if (sym == rvmap->eob_sym)
478 break; /* End of block */
480 /* Escape - run/val explicitly coded using 3 vlc codes */
481 if (sym == rvmap->esc_sym) {
482 run = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1) + 1;
483 lo = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
484 hi = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
485 /* merge them and convert into signed val */
486 val = IVI_TOSIGNED((hi << 6) | lo);
489 av_log(avctx, AV_LOG_ERROR, "Invalid sym encountered: %d.\n", sym);
490 return AVERROR_INVALIDDATA;
492 run = rvmap->runtab[sym];
493 val = rvmap->valtab[sym];
496 /* de-zigzag and dequantize */
498 if (scan_pos >= num_coeffs || scan_pos < 0)
500 pos = band->scan[scan_pos];
503 av_dlog(avctx, "Val = 0 encountered!\n");
505 q = (base_tab[pos] * quant) >> 9;
507 val = val * q + FFSIGN(val) * (((q ^ 1) - 1) >> 1);
509 /* track columns containing non-zero coeffs */
510 col_flags[pos & col_mask] |= !!val;
513 if (scan_pos < 0 || scan_pos >= num_coeffs && sym != rvmap->eob_sym)
514 return AVERROR_INVALIDDATA; /* corrupt block data */
516 /* undoing DC coeff prediction for intra-blocks */
517 if (is_intra && band->is_2d_trans) {
518 *prev_dc += trvec[0];
520 col_flags[0] |= !!*prev_dc;
523 /* apply inverse transform */
524 band->inv_transform(trvec, band->buf + offs,
525 band->pitch, col_flags);
527 /* apply motion compensation */
529 return ivi_mc(band, mc, offs, mv_x, mv_y, mc_type);
535 * extract huffman-coded transform coefficients from the bitstream,
536 * dequantize them, apply inverse transform and motion compensation
537 * in order to reconstruct the picture.
539 * @param[in,out] gb the GetBit context
540 * @param[in] band pointer to the band descriptor
541 * @param[in] tile pointer to the tile descriptor
542 * @return result code: 0 - OK, -1 = error (corrupted blocks data)
544 static int ivi_decode_blocks(GetBitContext *gb, IVIBandDesc *band,
545 IVITile *tile, AVCodecContext *avctx)
547 int mbn, blk, num_blocks, blk_size, ret, is_intra, mc_type = 0;
548 int mv_x = 0, mv_y = 0;
550 uint32_t cbp, quant, buf_offs;
552 ivi_mc_func mc_with_delta_func, mc_no_delta_func;
553 const uint8_t *scale_tab;
555 /* init intra prediction for the DC coefficient */
557 blk_size = band->blk_size;
558 /* number of blocks per mb */
559 num_blocks = (band->mb_size != blk_size) ? 4 : 1;
561 mc_with_delta_func = ff_ivi_mc_8x8_delta;
562 mc_no_delta_func = ff_ivi_mc_8x8_no_delta;
564 mc_with_delta_func = ff_ivi_mc_4x4_delta;
565 mc_no_delta_func = ff_ivi_mc_4x4_no_delta;
568 for (mbn = 0, mb = tile->mbs; mbn < tile->num_MBs; mb++, mbn++) {
569 is_intra = !mb->type;
571 buf_offs = mb->buf_offs;
573 quant = band->glob_quant + mb->q_delta;
574 if (avctx->codec_id == AV_CODEC_ID_INDEO4)
575 quant = av_clip(quant, 0, 31);
577 quant = av_clip(quant, 0, 23);
579 scale_tab = is_intra ? band->intra_scale : band->inter_scale;
581 quant = scale_tab[quant];
586 if (band->is_halfpel) {
587 mc_type = ((mv_y & 1) << 1) | (mv_x & 1);
589 mv_y >>= 1; /* convert halfpel vectors into fullpel ones */
592 int dmv_x, dmv_y, cx, cy;
594 dmv_x = mb->mv_x >> band->is_halfpel;
595 dmv_y = mb->mv_y >> band->is_halfpel;
596 cx = mb->mv_x & band->is_halfpel;
597 cy = mb->mv_y & band->is_halfpel;
599 if (mb->xpos + dmv_x < 0 ||
600 mb->xpos + dmv_x + band->mb_size + cx > band->pitch ||
601 mb->ypos + dmv_y < 0 ||
602 mb->ypos + dmv_y + band->mb_size + cy > band->aheight) {
603 return AVERROR_INVALIDDATA;
608 for (blk = 0; blk < num_blocks; blk++) {
609 /* adjust block position in the buffer according to its number */
611 buf_offs += blk_size;
612 } else if (blk == 2) {
613 buf_offs -= blk_size;
614 buf_offs += blk_size * band->pitch;
617 if (cbp & 1) { /* block coded ? */
618 ret = ivi_decode_coded_blocks(gb, band, mc_with_delta_func,
619 mv_x, mv_y, &prev_dc, is_intra,
620 mc_type, quant, buf_offs, avctx);
624 /* block not coded */
625 /* for intra blocks apply the dc slant transform */
626 /* for inter - perform the motion compensation without delta */
628 ret = ivi_dc_transform(band, &prev_dc, buf_offs, blk_size);
632 ret = ivi_mc(band, mc_no_delta_func, buf_offs,
633 mv_x, mv_y, mc_type);
649 * Handle empty tiles by performing data copying and motion
650 * compensation respectively.
652 * @param[in] avctx ptr to the AVCodecContext
653 * @param[in] band pointer to the band descriptor
654 * @param[in] tile pointer to the tile descriptor
655 * @param[in] mv_scale scaling factor for motion vectors
657 static int ivi_process_empty_tile(AVCodecContext *avctx, IVIBandDesc *band,
658 IVITile *tile, int32_t mv_scale)
660 int x, y, need_mc, mbn, blk, num_blocks, mv_x, mv_y, mc_type;
661 int offs, mb_offset, row_offset, ret;
662 IVIMbInfo *mb, *ref_mb;
665 ivi_mc_func mc_no_delta_func;
667 if (tile->num_MBs != IVI_MBs_PER_TILE(tile->width, tile->height, band->mb_size)) {
668 av_log(avctx, AV_LOG_ERROR, "Allocated tile size %d mismatches "
669 "parameters %d in ivi_process_empty_tile()\n",
670 tile->num_MBs, IVI_MBs_PER_TILE(tile->width, tile->height, band->mb_size));
671 return AVERROR_INVALIDDATA;
674 offs = tile->ypos * band->pitch + tile->xpos;
676 ref_mb = tile->ref_mbs;
677 row_offset = band->mb_size * band->pitch;
678 need_mc = 0; /* reset the mc tracking flag */
680 for (y = tile->ypos; y < (tile->ypos + tile->height); y += band->mb_size) {
683 for (x = tile->xpos; x < (tile->xpos + tile->width); x += band->mb_size) {
686 mb->buf_offs = mb_offset;
688 mb->type = 1; /* set the macroblocks type = INTER */
689 mb->cbp = 0; /* all blocks are empty */
691 if (!band->qdelta_present && !band->plane && !band->band_num) {
692 mb->q_delta = band->glob_quant;
697 if (band->inherit_qdelta && ref_mb)
698 mb->q_delta = ref_mb->q_delta;
700 if (band->inherit_mv && ref_mb) {
701 /* motion vector inheritance */
703 mb->mv_x = ivi_scale_mv(ref_mb->mv_x, mv_scale);
704 mb->mv_y = ivi_scale_mv(ref_mb->mv_y, mv_scale);
706 mb->mv_x = ref_mb->mv_x;
707 mb->mv_y = ref_mb->mv_y;
709 need_mc |= mb->mv_x || mb->mv_y; /* tracking non-zero motion vectors */
715 mb_offset += band->mb_size;
720 if (band->inherit_mv && need_mc) { /* apply motion compensation if there is at least one non-zero motion vector */
721 num_blocks = (band->mb_size != band->blk_size) ? 4 : 1; /* number of blocks per mb */
722 mc_no_delta_func = (band->blk_size == 8) ? ff_ivi_mc_8x8_no_delta
723 : ff_ivi_mc_4x4_no_delta;
725 for (mbn = 0, mb = tile->mbs; mbn < tile->num_MBs; mb++, mbn++) {
728 if (!band->is_halfpel) {
729 mc_type = 0; /* we have only fullpel vectors */
731 mc_type = ((mv_y & 1) << 1) | (mv_x & 1);
733 mv_y >>= 1; /* convert halfpel vectors into fullpel ones */
736 for (blk = 0; blk < num_blocks; blk++) {
737 /* adjust block position in the buffer according with its number */
738 offs = mb->buf_offs + band->blk_size * ((blk & 1) + !!(blk & 2) * band->pitch);
739 ret = ivi_mc(band, mc_no_delta_func, offs,
740 mv_x, mv_y, mc_type);
746 /* copy data from the reference tile into the current one */
747 src = band->ref_buf + tile->ypos * band->pitch + tile->xpos;
748 dst = band->buf + tile->ypos * band->pitch + tile->xpos;
749 for (y = 0; y < tile->height; y++) {
750 memcpy(dst, src, tile->width*sizeof(band->buf[0]));
761 static uint16_t ivi_calc_band_checksum(IVIBandDesc *band)
764 int16_t *src, checksum;
769 for (y = 0; y < band->height; src += band->pitch, y++)
770 for (x = 0; x < band->width; x++)
778 * Convert and output the current plane.
779 * This conversion is done by adding back the bias value of 128
780 * (subtracted in the encoder) and clipping the result.
782 * @param[in] plane pointer to the descriptor of the plane being processed
783 * @param[out] dst pointer to the buffer receiving converted pixels
784 * @param[in] dst_pitch pitch for moving to the next y line
786 static void ivi_output_plane(IVIPlaneDesc *plane, uint8_t *dst, int dst_pitch)
789 const int16_t *src = plane->bands[0].buf;
790 uint32_t pitch = plane->bands[0].pitch;
795 for (y = 0; y < plane->height; y++) {
796 for (x = 0; x < plane->width; x++)
797 dst[x] = av_clip_uint8(src[x] + 128);
804 * Decode an Indeo 4 or 5 band.
806 * @param[in,out] ctx ptr to the decoder context
807 * @param[in,out] band ptr to the band descriptor
808 * @param[in] avctx ptr to the AVCodecContext
809 * @return result code: 0 = OK, -1 = error
811 static int decode_band(IVI45DecContext *ctx,
812 IVIBandDesc *band, AVCodecContext *avctx)
814 int result, i, t, idx1, idx2, pos;
817 band->buf = band->bufs[ctx->dst_buf];
819 av_log(avctx, AV_LOG_ERROR, "Band buffer points to no data!\n");
820 return AVERROR_INVALIDDATA;
822 band->ref_buf = band->bufs[ctx->ref_buf];
823 band->data_ptr = ctx->frame_data + (get_bits_count(&ctx->gb) >> 3);
825 result = ctx->decode_band_hdr(ctx, band, avctx);
827 av_log(avctx, AV_LOG_ERROR, "Error while decoding band header: %d\n",
832 if (band->is_empty) {
833 av_log(avctx, AV_LOG_ERROR, "Empty band encountered!\n");
834 return AVERROR_INVALIDDATA;
837 band->rv_map = &ctx->rvmap_tabs[band->rvmap_sel];
839 /* apply corrections to the selected rvmap table if present */
840 for (i = 0; i < band->num_corr; i++) {
841 idx1 = band->corr[i * 2];
842 idx2 = band->corr[i * 2 + 1];
843 FFSWAP(uint8_t, band->rv_map->runtab[idx1], band->rv_map->runtab[idx2]);
844 FFSWAP(int16_t, band->rv_map->valtab[idx1], band->rv_map->valtab[idx2]);
847 pos = get_bits_count(&ctx->gb);
849 for (t = 0; t < band->num_tiles; t++) {
850 tile = &band->tiles[t];
852 if (tile->mb_size != band->mb_size) {
853 av_log(avctx, AV_LOG_ERROR, "MB sizes mismatch: %d vs. %d\n",
854 band->mb_size, tile->mb_size);
855 return AVERROR_INVALIDDATA;
857 tile->is_empty = get_bits1(&ctx->gb);
858 if (tile->is_empty) {
859 result = ivi_process_empty_tile(avctx, band, tile,
860 (ctx->planes[0].bands[0].mb_size >> 3) - (band->mb_size >> 3));
863 av_dlog(avctx, "Empty tile encountered!\n");
865 tile->data_size = ivi_dec_tile_data_size(&ctx->gb);
866 if (!tile->data_size) {
867 av_log(avctx, AV_LOG_ERROR, "Tile data size is zero!\n");
868 return AVERROR_INVALIDDATA;
871 result = ctx->decode_mb_info(ctx, band, tile, avctx);
875 result = ivi_decode_blocks(&ctx->gb, band, tile, avctx);
877 av_log(avctx, AV_LOG_ERROR,
878 "Corrupted tile data encountered!\n");
882 if (((get_bits_count(&ctx->gb) - pos) >> 3) != tile->data_size) {
883 av_log(avctx, AV_LOG_ERROR,
884 "Tile data_size mismatch!\n");
885 result = AVERROR_INVALIDDATA;
889 pos += tile->data_size << 3; // skip to next tile
893 /* restore the selected rvmap table by applying its corrections in
895 for (i = band->num_corr-1; i >= 0; i--) {
896 idx1 = band->corr[i*2];
897 idx2 = band->corr[i*2+1];
898 FFSWAP(uint8_t, band->rv_map->runtab[idx1], band->rv_map->runtab[idx2]);
899 FFSWAP(int16_t, band->rv_map->valtab[idx1], band->rv_map->valtab[idx2]);
903 if (band->checksum_present) {
904 uint16_t chksum = ivi_calc_band_checksum(band);
905 if (chksum != band->checksum) {
906 av_log(avctx, AV_LOG_ERROR,
907 "Band checksum mismatch! Plane %d, band %d, "
908 "received: %x, calculated: %x\n",
909 band->plane, band->band_num, band->checksum, chksum);
914 align_get_bits(&ctx->gb);
919 int ff_ivi_decode_frame(AVCodecContext *avctx, void *data, int *got_frame,
922 IVI45DecContext *ctx = avctx->priv_data;
923 const uint8_t *buf = avpkt->data;
924 AVFrame *frame = data;
925 int buf_size = avpkt->size;
928 init_get_bits(&ctx->gb, buf, buf_size * 8);
929 ctx->frame_data = buf;
930 ctx->frame_size = buf_size;
932 result = ctx->decode_pic_hdr(ctx, avctx);
934 av_log(avctx, AV_LOG_ERROR,
935 "Error while decoding picture header: %d\n", result);
938 if (ctx->gop_invalid)
939 return AVERROR_INVALIDDATA;
941 if (ctx->gop_flags & IVI5_IS_PROTECTED) {
942 avpriv_report_missing_feature(avctx, "Password-protected clip!\n");
943 return AVERROR_PATCHWELCOME;
946 ctx->switch_buffers(ctx);
950 if (ctx->is_nonnull_frame(ctx)) {
951 for (p = 0; p < 3; p++) {
952 for (b = 0; b < ctx->planes[p].num_bands; b++) {
953 result = decode_band(ctx, &ctx->planes[p].bands[b], avctx);
955 av_log(avctx, AV_LOG_ERROR,
956 "Error while decoding band: %d, plane: %d\n", b, p);
962 if (ctx->is_scalable)
963 return AVERROR_INVALIDDATA;
965 for (p = 0; p < 3; p++) {
966 if (!ctx->planes[p].bands[0].buf)
967 return AVERROR_INVALIDDATA;
971 //STOP_TIMER("decode_planes"); }
973 /* If the bidirectional mode is enabled, next I and the following P
974 * frame will be sent together. Unfortunately the approach below seems
975 * to be the only way to handle the B-frames mode.
976 * That's exactly the same Intel decoders do.
978 if (avctx->codec_id == AV_CODEC_ID_INDEO4 &&
979 ctx->frame_type == 0/*FRAMETYPE_INTRA*/) {
980 while (get_bits(&ctx->gb, 8)); // skip version string
981 skip_bits_long(&ctx->gb, 64); // skip padding, TODO: implement correct 8-bytes alignment
982 if (get_bits_left(&ctx->gb) > 18 && show_bits(&ctx->gb, 18) == 0x3FFF8)
983 av_log(avctx, AV_LOG_ERROR, "Buffer contains IP frames!\n");
986 avcodec_set_dimensions(avctx, ctx->planes[0].width, ctx->planes[0].height);
987 if ((result = ff_get_buffer(avctx, frame, 0)) < 0) {
988 av_log(avctx, AV_LOG_ERROR, "get_buffer() failed\n");
992 if (ctx->is_scalable) {
993 if (avctx->codec_id == AV_CODEC_ID_INDEO4)
994 ff_ivi_recompose_haar(&ctx->planes[0], frame->data[0], frame->linesize[0]);
996 ff_ivi_recompose53 (&ctx->planes[0], frame->data[0], frame->linesize[0]);
998 ivi_output_plane(&ctx->planes[0], frame->data[0], frame->linesize[0]);
1001 ivi_output_plane(&ctx->planes[2], frame->data[1], frame->linesize[1]);
1002 ivi_output_plane(&ctx->planes[1], frame->data[2], frame->linesize[2]);
1010 * Close Indeo5 decoder and clean up its context.
1012 av_cold int ff_ivi_decode_close(AVCodecContext *avctx)
1014 IVI45DecContext *ctx = avctx->priv_data;
1016 ivi_free_buffers(&ctx->planes[0]);
1018 if (ctx->mb_vlc.cust_tab.table)
1019 ff_free_vlc(&ctx->mb_vlc.cust_tab);
1021 #if IVI4_STREAM_ANALYSER
1022 if (avctx->codec_id == AV_CODEC_ID_INDEO4) {
1023 if (ctx->is_scalable)
1024 av_log(avctx, AV_LOG_ERROR, "This video uses scalability mode!\n");
1025 if (ctx->uses_tiling)
1026 av_log(avctx, AV_LOG_ERROR, "This video uses local decoding!\n");
1027 if (ctx->has_b_frames)
1028 av_log(avctx, AV_LOG_ERROR, "This video contains B-frames!\n");
1029 if (ctx->has_transp)
1030 av_log(avctx, AV_LOG_ERROR, "Transparency mode is enabled!\n");
1032 av_log(avctx, AV_LOG_ERROR, "This video uses Haar transform!\n");
1033 if (ctx->uses_fullpel)
1034 av_log(avctx, AV_LOG_ERROR, "This video uses fullpel motion vectors!\n");
1043 * These are 2x8 predefined Huffman codebooks for coding macroblock/block
1044 * signals. They are specified using "huffman descriptors" in order to
1045 * avoid huge static tables. The decoding tables will be generated at
1046 * startup from these descriptors.
1048 const IVIHuffDesc ff_ivi_mb_huff_desc[8] = {
1049 {8, {0, 4, 5, 4, 4, 4, 6, 6}},
1050 {12, {0, 2, 2, 3, 3, 3, 3, 5, 3, 2, 2, 2}},
1051 {12, {0, 2, 3, 4, 3, 3, 3, 3, 4, 3, 2, 2}},
1052 {12, {0, 3, 4, 4, 3, 3, 3, 3, 3, 2, 2, 2}},
1053 {13, {0, 4, 4, 3, 3, 3, 3, 2, 3, 3, 2, 1, 1}},
1054 {9, {0, 4, 4, 4, 4, 3, 3, 3, 2}},
1055 {10, {0, 4, 4, 4, 4, 3, 3, 2, 2, 2}},
1056 {12, {0, 4, 4, 4, 3, 3, 2, 3, 2, 2, 2, 2}}
1059 const IVIHuffDesc ff_ivi_blk_huff_desc[8] = {
1060 {10, {1, 2, 3, 4, 4, 7, 5, 5, 4, 1}},
1061 {11, {2, 3, 4, 4, 4, 7, 5, 4, 3, 3, 2}},
1062 {12, {2, 4, 5, 5, 5, 5, 6, 4, 4, 3, 1, 1}},
1063 {13, {3, 3, 4, 4, 5, 6, 6, 4, 4, 3, 2, 1, 1}},
1064 {11, {3, 4, 4, 5, 5, 5, 6, 5, 4, 2, 2}},
1065 {13, {3, 4, 5, 5, 5, 5, 6, 4, 3, 3, 2, 1, 1}},
1066 {13, {3, 4, 5, 5, 5, 6, 5, 4, 3, 3, 2, 1, 1}},
1067 {9, {3, 4, 4, 5, 5, 5, 6, 5, 5}}
1072 * Scan patterns shared between indeo4 and indeo5
1074 const uint8_t ff_ivi_vertical_scan_8x8[64] = {
1075 0, 8, 16, 24, 32, 40, 48, 56,
1076 1, 9, 17, 25, 33, 41, 49, 57,
1077 2, 10, 18, 26, 34, 42, 50, 58,
1078 3, 11, 19, 27, 35, 43, 51, 59,
1079 4, 12, 20, 28, 36, 44, 52, 60,
1080 5, 13, 21, 29, 37, 45, 53, 61,
1081 6, 14, 22, 30, 38, 46, 54, 62,
1082 7, 15, 23, 31, 39, 47, 55, 63
1085 const uint8_t ff_ivi_horizontal_scan_8x8[64] = {
1086 0, 1, 2, 3, 4, 5, 6, 7,
1087 8, 9, 10, 11, 12, 13, 14, 15,
1088 16, 17, 18, 19, 20, 21, 22, 23,
1089 24, 25, 26, 27, 28, 29, 30, 31,
1090 32, 33, 34, 35, 36, 37, 38, 39,
1091 40, 41, 42, 43, 44, 45, 46, 47,
1092 48, 49, 50, 51, 52, 53, 54, 55,
1093 56, 57, 58, 59, 60, 61, 62, 63
1096 const uint8_t ff_ivi_direct_scan_4x4[16] = {
1097 0, 1, 4, 8, 5, 2, 3, 6, 9, 12, 13, 10, 7, 11, 14, 15
1102 * Run-value (RLE) tables.
1104 const RVMapDesc ff_ivi_rvmap_tabs[9] = {
1109 {1, 1, 0, 1, 1, 0, 1, 1, 2, 2, 1, 1, 1, 1, 3, 3,
1110 1, 1, 2, 2, 1, 1, 4, 4, 1, 1, 1, 1, 2, 2, 5, 5,
1111 1, 1, 3, 3, 1, 1, 6, 6, 1, 2, 1, 2, 7, 7, 1, 1,
1112 8, 8, 1, 1, 4, 2, 1, 4, 2, 1, 3, 3, 1, 1, 1, 9,
1113 9, 1, 2, 1, 2, 1, 5, 5, 1, 1, 10, 10, 1, 1, 3, 3,
1114 2, 2, 1, 1, 11, 11, 6, 4, 4, 1, 6, 1, 2, 1, 2, 12,
1115 8, 1, 12, 7, 8, 7, 1, 16, 1, 16, 1, 3, 3, 13, 1, 13,
1116 2, 2, 1, 15, 1, 5, 14, 15, 1, 5, 14, 1, 17, 8, 17, 8,
1117 1, 4, 4, 2, 2, 1, 25, 25, 24, 24, 1, 3, 1, 3, 1, 8,
1118 6, 7, 6, 1, 18, 8, 18, 1, 7, 23, 2, 2, 23, 1, 1, 21,
1119 22, 9, 9, 22, 19, 1, 21, 5, 19, 5, 1, 33, 20, 33, 20, 8,
1120 4, 4, 1, 32, 2, 2, 8, 3, 32, 26, 3, 1, 7, 7, 26, 6,
1121 1, 6, 1, 1, 16, 1, 10, 1, 10, 2, 16, 29, 28, 2, 29, 28,
1122 1, 27, 5, 8, 5, 27, 1, 8, 3, 7, 3, 31, 41, 31, 1, 41,
1123 6, 1, 6, 7, 4, 4, 1, 1, 2, 1, 2, 11, 34, 30, 11, 1,
1124 30, 15, 15, 34, 36, 40, 36, 40, 35, 35, 37, 37, 39, 39, 38, 38},
1127 { 1, -1, 0, 2, -2, 0, 3, -3, 1, -1, 4, -4, 5, -5, 1, -1,
1128 6, -6, 2, -2, 7, -7, 1, -1, 8, -8, 9, -9, 3, -3, 1, -1,
1129 10, -10, 2, -2, 11, -11, 1, -1, 12, 4, -12, -4, 1, -1, 13, -13,
1130 1, -1, 14, -14, 2, 5, 15, -2, -5, -15, -3, 3, 16, -16, 17, 1,
1131 -1, -17, 6, 18, -6, -18, 2, -2, 19, -19, 1, -1, 20, -20, 4, -4,
1132 7, -7, 21, -21, 1, -1, 2, 3, -3, 22, -2, -22, 8, 23, -8, 1,
1133 2, -23, -1, 2, -2, -2, 24, 1, -24, -1, 25, 5, -5, 1, -25, -1,
1134 9, -9, 26, 1, -26, 3, 1, -1, 27, -3, -1, -27, 1, 3, -1, -3,
1135 28, -4, 4, 10, -10, -28, 1, -1, 1, -1, 29, 6, -29, -6, 30, -4,
1136 3, 3, -3, -30, 1, 4, -1, 31, -3, 1, 11, -11, -1, -31, 32, -1,
1137 -1, 2, -2, 1, 1, -32, 1, 4, -1, -4, 33, -1, 1, 1, -1, 5,
1138 5, -5, -33, -1, -12, 12, -5, -7, 1, 1, 7, 34, 4, -4, -1, 4,
1139 -34, -4, 35, 36, -2, -35, -2, -36, 2, 13, 2, -1, 1, -13, 1, -1,
1140 37, 1, -5, 6, 5, -1, 38, -6, -8, 5, 8, -1, 1, 1, -37, -1,
1141 5, 39, -5, -5, 6, -6, -38, -39, -14, 40, 14, 2, 1, 1, -2, -40,
1142 -1, -2, 2, -1, -1, -1, 1, 1, 1, -1, 1, -1, 1, -1, 1, -1}
1148 {0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 8, 6, 8, 7,
1149 7, 9, 9, 10, 10, 11, 11, 1, 12, 1, 12, 13, 13, 16, 14, 16,
1150 14, 15, 15, 17, 17, 18, 0, 18, 19, 20, 21, 19, 22, 21, 20, 22,
1151 25, 24, 2, 25, 24, 23, 23, 2, 26, 28, 26, 28, 29, 27, 29, 27,
1152 33, 33, 1, 32, 1, 3, 32, 30, 36, 3, 36, 30, 31, 31, 35, 34,
1153 37, 41, 34, 35, 37, 4, 41, 4, 49, 8, 8, 49, 40, 38, 5, 38,
1154 40, 39, 5, 39, 42, 43, 42, 7, 57, 6, 43, 44, 6, 50, 7, 44,
1155 57, 48, 50, 48, 45, 45, 46, 47, 51, 46, 47, 58, 1, 51, 58, 1,
1156 52, 59, 53, 9, 52, 55, 55, 59, 53, 56, 54, 56, 54, 9, 64, 64,
1157 60, 63, 60, 63, 61, 62, 61, 62, 2, 10, 2, 10, 11, 1, 11, 13,
1158 12, 1, 12, 13, 16, 16, 8, 8, 14, 3, 3, 15, 14, 15, 4, 4,
1159 1, 17, 17, 5, 1, 7, 7, 5, 6, 1, 2, 2, 6, 22, 1, 25,
1160 21, 22, 8, 24, 1, 21, 25, 24, 8, 18, 18, 23, 9, 20, 23, 33,
1161 29, 33, 20, 1, 19, 1, 29, 36, 9, 36, 19, 41, 28, 57, 32, 3,
1162 28, 3, 1, 27, 49, 49, 1, 32, 26, 26, 2, 4, 4, 7, 57, 41,
1163 2, 7, 10, 5, 37, 16, 10, 27, 8, 8, 13, 16, 37, 13, 1, 5},
1166 {0, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, 1, -1, -1, 1,
1167 -1, 1, -1, 1, -1, 1, -1, 2, 1, -2, -1, 1, -1, 1, 1, -1,
1168 -1, 1, -1, 1, -1, 1, 0, -1, 1, 1, 1, -1, 1, -1, -1, -1,
1169 1, 1, 2, -1, -1, 1, -1, -2, 1, 1, -1, -1, 1, 1, -1, -1,
1170 1, -1, 3, 1, -3, 2, -1, 1, 1, -2, -1, -1, -1, 1, 1, 1,
1171 1, 1, -1, -1, -1, 2, -1, -2, 1, 2, -2, -1, 1, 1, 2, -1,
1172 -1, 1, -2, -1, 1, 1, -1, 2, 1, 2, -1, 1, -2, -1, -2, -1,
1173 -1, 1, 1, -1, 1, -1, 1, 1, 1, -1, -1, 1, 4, -1, -1, -4,
1174 1, 1, 1, 2, -1, -1, 1, -1, -1, 1, -1, -1, 1, -2, 1, -1,
1175 1, 1, -1, -1, 1, 1, -1, -1, 3, 2, -3, -2, 2, 5, -2, 2,
1176 2, -5, -2, -2, -2, 2, -3, 3, 2, 3, -3, 2, -2, -2, 3, -3,
1177 6, 2, -2, 3, -6, 3, -3, -3, 3, 7, -4, 4, -3, 2, -7, 2,
1178 2, -2, -4, 2, 8, -2, -2, -2, 4, 2, -2, 2, 3, 2, -2, -2,
1179 2, 2, -2, -8, -2, 9, -2, 2, -3, -2, 2, -2, 2, 2, 2, 4,
1180 -2, -4, 10, 2, 2, -2, -9, -2, 2, -2, 5, 4, -4, 4, -2, 2,
1181 -5, -4, -3, 4, 2, -3, 3, -2, -5, 5, 3, 3, -2, -3, -10, -4}
1187 {1, 1, 0, 2, 2, 1, 1, 3, 3, 4, 4, 0, 1, 1, 5, 5,
1188 2, 2, 6, 6, 7, 7, 1, 8, 1, 8, 3, 3, 9, 9, 1, 2,
1189 2, 1, 4, 10, 4, 10, 11, 11, 1, 5, 12, 12, 1, 5, 13, 13,
1190 3, 3, 6, 6, 2, 2, 14, 14, 16, 16, 15, 7, 15, 8, 8, 7,
1191 1, 1, 17, 17, 4, 4, 1, 1, 18, 18, 2, 2, 5, 5, 25, 3,
1192 9, 3, 25, 9, 19, 24, 19, 24, 1, 21, 20, 1, 21, 22, 20, 22,
1193 23, 23, 8, 6, 33, 6, 8, 33, 7, 7, 26, 26, 1, 32, 1, 32,
1194 28, 4, 28, 10, 29, 27, 27, 10, 41, 4, 29, 2, 2, 41, 36, 31,
1195 49, 31, 34, 30, 34, 36, 30, 35, 1, 49, 11, 5, 35, 11, 1, 3,
1196 3, 5, 37, 37, 8, 40, 8, 40, 12, 12, 42, 42, 1, 38, 16, 57,
1197 1, 6, 16, 39, 38, 6, 7, 7, 13, 13, 39, 43, 2, 43, 57, 2,
1198 50, 9, 44, 9, 50, 4, 15, 48, 44, 4, 1, 15, 48, 14, 14, 1,
1199 45, 45, 8, 3, 5, 8, 51, 47, 3, 46, 46, 47, 5, 51, 1, 17,
1200 17, 58, 1, 58, 2, 52, 52, 2, 53, 7, 59, 6, 6, 56, 53, 55,
1201 7, 55, 1, 54, 59, 56, 54, 10, 1, 10, 4, 60, 1, 60, 8, 4,
1202 8, 64, 64, 61, 1, 63, 3, 63, 62, 61, 5, 11, 5, 3, 11, 62},
1205 { 1, -1, 0, 1, -1, 2, -2, 1, -1, 1, -1, 0, 3, -3, 1, -1,
1206 2, -2, 1, -1, 1, -1, 4, 1, -4, -1, 2, -2, 1, -1, 5, 3,
1207 -3, -5, 2, 1, -2, -1, 1, -1, 6, 2, 1, -1, -6, -2, 1, -1,
1208 3, -3, 2, -2, 4, -4, 1, -1, 1, -1, 1, 2, -1, 2, -2, -2,
1209 7, -7, 1, -1, 3, -3, 8, -8, 1, -1, 5, -5, 3, -3, 1, 4,
1210 2, -4, -1, -2, 1, 1, -1, -1, 9, 1, 1, -9, -1, 1, -1, -1,
1211 1, -1, 3, -3, 1, 3, -3, -1, 3, -3, 1, -1, 10, 1, -10, -1,
1212 1, 4, -1, 2, 1, -1, 1, -2, 1, -4, -1, 6, -6, -1, 1, 1,
1213 1, -1, 1, 1, -1, -1, -1, 1, 11, -1, -2, 4, -1, 2, -11, 5,
1214 -5, -4, -1, 1, 4, 1, -4, -1, -2, 2, 1, -1, 12, 1, -2, 1,
1215 -12, 4, 2, 1, -1, -4, 4, -4, 2, -2, -1, 1, 7, -1, -1, -7,
1216 -1, -3, 1, 3, 1, 5, 2, 1, -1, -5, 13, -2, -1, 2, -2, -13,
1217 1, -1, 5, 6, 5, -5, 1, 1, -6, 1, -1, -1, -5, -1, 14, 2,
1218 -2, 1, -14, -1, 8, 1, -1, -8, 1, 5, 1, 5, -5, 1, -1, 1,
1219 -5, -1, 15, 1, -1, -1, -1, 3, -15, -3, 6, 1, 16, -1, 6, -6,
1220 -6, 1, -1, 1, -16, 1, 7, -1, 1, -1, -6, -3, 6, -7, 3, -1}
1226 {0, 1, 1, 2, 2, 3, 3, 4, 4, 1, 1, 5, 5, 6, 6, 7,
1227 7, 8, 8, 9, 9, 2, 2, 10, 10, 1, 1, 11, 11, 12, 12, 3,
1228 3, 13, 13, 0, 14, 14, 16, 15, 16, 15, 4, 4, 17, 1, 17, 1,
1229 5, 5, 18, 18, 2, 2, 6, 6, 8, 19, 7, 8, 7, 19, 20, 20,
1230 21, 21, 22, 24, 22, 24, 23, 23, 1, 1, 25, 25, 3, 3, 26, 26,
1231 9, 9, 27, 27, 28, 28, 33, 29, 4, 33, 29, 1, 4, 1, 32, 32,
1232 2, 2, 31, 10, 30, 10, 30, 31, 34, 34, 5, 5, 36, 36, 35, 41,
1233 35, 11, 41, 11, 37, 1, 8, 8, 37, 6, 1, 6, 40, 7, 7, 40,
1234 12, 38, 12, 39, 39, 38, 49, 13, 49, 13, 3, 42, 3, 42, 16, 16,
1235 43, 43, 14, 14, 1, 1, 44, 15, 44, 15, 2, 2, 57, 48, 50, 48,
1236 57, 50, 4, 45, 45, 4, 46, 47, 47, 46, 1, 51, 1, 17, 17, 51,
1237 8, 9, 9, 5, 58, 8, 58, 5, 52, 52, 55, 56, 53, 56, 55, 59,
1238 59, 53, 54, 1, 6, 54, 7, 7, 6, 1, 2, 3, 2, 3, 64, 60,
1239 60, 10, 10, 64, 61, 62, 61, 63, 1, 63, 62, 1, 18, 24, 18, 4,
1240 25, 4, 8, 21, 21, 1, 24, 22, 25, 22, 8, 11, 19, 11, 23, 1,
1241 20, 23, 19, 20, 5, 12, 5, 1, 16, 2, 12, 13, 2, 13, 1, 16},
1244 { 0, 1, -1, 1, -1, 1, -1, 1, -1, 2, -2, 1, -1, 1, -1, 1,
1245 -1, 1, -1, 1, -1, 2, -2, 1, -1, 3, -3, 1, -1, 1, -1, 2,
1246 -2, 1, -1, 0, 1, -1, 1, 1, -1, -1, 2, -2, 1, 4, -1, -4,
1247 2, -2, 1, -1, -3, 3, 2, -2, 2, 1, 2, -2, -2, -1, 1, -1,
1248 1, -1, 1, 1, -1, -1, 1, -1, 5, -5, 1, -1, 3, -3, 1, -1,
1249 2, -2, 1, -1, 1, -1, 1, 1, 3, -1, -1, 6, -3, -6, -1, 1,
1250 4, -4, 1, 2, 1, -2, -1, -1, 1, -1, 3, -3, 1, -1, 1, 1,
1251 -1, 2, -1, -2, 1, 7, -3, 3, -1, 3, -7, -3, 1, -3, 3, -1,
1252 2, 1, -2, 1, -1, -1, 1, 2, -1, -2, -4, -1, 4, 1, 2, -2,
1253 1, -1, -2, 2, 8, -8, -1, 2, 1, -2, -5, 5, 1, -1, -1, 1,
1254 -1, 1, 4, -1, 1, -4, -1, -1, 1, 1, 9, 1, -9, 2, -2, -1,
1255 -4, 3, -3, -4, -1, 4, 1, 4, 1, -1, 1, -1, 1, 1, -1, 1,
1256 -1, -1, -1, 10, 4, 1, 4, -4, -4, -10, 6, 5, -6, -5, 1, -1,
1257 1, 3, -3, -1, 1, -1, -1, -1, 11, 1, 1, -11, -2, -2, 2, 5,
1258 -2, -5, -5, 2, -2, 12, 2, -2, 2, 2, 5, -3, -2, 3, -2, -12,
1259 -2, 2, 2, 2, -5, 3, 5, 13, -3, 7, -3, -3, -7, 3, -13, 3}
1265 {0, 1, 1, 1, 2, 2, 1, 3, 3, 1, 1, 1, 4, 4, 1, 5,
1266 2, 1, 5, 2, 1, 1, 6, 6, 1, 1, 1, 1, 1, 7, 3, 1,
1267 2, 3, 0, 1, 2, 7, 1, 1, 1, 8, 1, 1, 8, 1, 1, 1,
1268 9, 1, 9, 1, 2, 1, 1, 2, 1, 1, 10, 4, 1, 10, 1, 4,
1269 1, 1, 1, 1, 1, 3, 1, 1, 1, 3, 2, 1, 5, 1, 1, 1,
1270 2, 5, 1, 11, 1, 11, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1271 2, 1, 6, 1, 6, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 12,
1272 3, 1, 12, 1, 1, 1, 2, 1, 1, 3, 1, 1, 1, 1, 1, 1,
1273 4, 1, 1, 1, 2, 1, 1, 4, 1, 1, 1, 1, 1, 1, 2, 1,
1274 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 2, 1, 1, 5,
1275 1, 1, 1, 1, 1, 7, 1, 7, 1, 1, 2, 3, 1, 1, 1, 1,
1276 5, 1, 1, 1, 1, 1, 1, 2, 13, 1, 1, 1, 1, 1, 1, 1,
1277 1, 1, 1, 1, 1, 1, 1, 1, 13, 2, 1, 1, 4, 1, 1, 1,
1278 3, 1, 6, 1, 1, 1, 14, 1, 1, 1, 1, 1, 14, 6, 1, 1,
1279 1, 1, 15, 2, 4, 1, 2, 3, 15, 1, 1, 1, 8, 1, 1, 8,
1280 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1},
1283 { 0, 1, -1, 2, 1, -1, -2, 1, -1, 3, -3, 4, 1, -1, -4, 1,
1284 2, 5, -1, -2, -5, 6, 1, -1, -6, 7, -7, 8, -8, 1, 2, 9,
1285 3, -2, 0, -9, -3, -1, 10, -10, 11, 1, -11, 12, -1, -12, 13, -13,
1286 1, 14, -1, -14, 4, 15, -15, -4, 16, -16, 1, 2, 17, -1, -17, -2,
1287 18, -18, 19, -19, 20, 3, -20, 21, -21, -3, 5, 22, 2, -22, -23, 23,
1288 -5, -2, 24, 1, -24, -1, 25, -25, 26, -26, -27, 27, 28, 29, -28, -29,
1289 6, 30, 2, -31, -2, -30, 31, -6, -32, 32, 33, -33, 34, -35, -34, 1,
1290 4, -36, -1, 35, 37, 36, 7, -37, 38, -4, -38, 39, 41, 40, -40, -39,
1291 3, 42, -43, -41, -7, -42, 43, -3, 44, -44, 45, -45, 46, 47, 8, -47,
1292 -48, -46, 50, -50, 48, 49, 51, -49, 52, -52, 5, -51, -8, -53, 53, 3,
1293 -56, 56, 55, 54, -54, 2, 60, -2, -55, 58, 9, -5, 59, 57, -57, -63,
1294 -3, -58, -60, -61, 61, -59, -62, -9, 1, 64, 62, 69, -64, 63, 65, -67,
1295 -68, 66, -65, 68, -66, -69, 67, -70, -1, 10, 71, -71, 4, 73, 72, 70,
1296 6, -76, -3, 74, -78, -74, 1, 78, 80, -72, -75, 76, -1, 3, -73, 79,
1297 75, 77, 1, 11, -4, -79, -10, -6, -1, -77, -83, -80, 2, 81, -84, -2,
1298 83, -81, 82, -82, 84, -87, -86, 85, -11, -85, 86, -89, 87, -88, 88, 89}
1304 {1, 1, 0, 2, 1, 2, 1, 3, 3, 1, 1, 4, 4, 2, 2, 1,
1305 1, 5, 5, 6, 1, 6, 1, 7, 7, 3, 3, 2, 8, 2, 8, 1,
1306 1, 0, 9, 9, 1, 1, 10, 4, 10, 4, 11, 11, 2, 1, 2, 1,
1307 12, 12, 3, 3, 1, 1, 13, 5, 5, 13, 14, 1, 1, 14, 2, 2,
1308 6, 6, 15, 1, 1, 15, 16, 4, 7, 16, 4, 7, 1, 1, 3, 3,
1309 8, 8, 2, 2, 1, 1, 17, 17, 1, 1, 18, 18, 5, 5, 2, 2,
1310 1, 1, 9, 19, 9, 19, 20, 3, 3, 20, 1, 10, 21, 1, 10, 4,
1311 4, 21, 22, 6, 6, 22, 1, 1, 23, 24, 2, 2, 23, 24, 11, 1,
1312 1, 11, 7, 25, 7, 1, 1, 25, 8, 8, 3, 26, 3, 1, 12, 2,
1313 2, 26, 1, 12, 5, 5, 27, 4, 1, 4, 1, 27, 28, 1, 28, 13,
1314 1, 13, 2, 29, 2, 1, 32, 6, 1, 30, 14, 29, 14, 6, 3, 31,
1315 3, 1, 30, 1, 32, 31, 33, 9, 33, 1, 1, 7, 9, 7, 2, 2,
1316 1, 1, 4, 36, 34, 4, 5, 10, 10, 5, 34, 1, 1, 35, 8, 8,
1317 36, 3, 35, 1, 15, 3, 2, 1, 16, 15, 16, 2, 37, 1, 37, 1,
1318 1, 1, 6, 6, 38, 1, 38, 11, 1, 39, 39, 40, 11, 2, 41, 4,
1319 40, 1, 2, 4, 1, 1, 1, 41, 3, 1, 3, 1, 5, 7, 5, 7},
1322 { 1, -1, 0, 1, 2, -1, -2, 1, -1, 3, -3, 1, -1, 2, -2, 4,
1323 -4, 1, -1, 1, 5, -1, -5, 1, -1, 2, -2, 3, 1, -3, -1, 6,
1324 -6, 0, 1, -1, 7, -7, 1, 2, -1, -2, 1, -1, 4, 8, -4, -8,
1325 1, -1, 3, -3, 9, -9, 1, 2, -2, -1, 1, 10, -10, -1, 5, -5,
1326 2, -2, 1, 11, -11, -1, 1, 3, 2, -1, -3, -2, 12, -12, 4, -4,
1327 2, -2, -6, 6, 13, -13, 1, -1, 14, -14, 1, -1, 3, -3, 7, -7,
1328 15, -15, 2, 1, -2, -1, 1, 5, -5, -1, -16, 2, 1, 16, -2, 4,
1329 -4, -1, 1, 3, -3, -1, 17, -17, 1, 1, -8, 8, -1, -1, 2, 18,
1330 -18, -2, 3, 1, -3, 19, -19, -1, 3, -3, 6, 1, -6, 20, 2, 9,
1331 -9, -1, -20, -2, 4, -4, 1, -5, 21, 5, -21, -1, 1, -22, -1, 2,
1332 22, -2, 10, 1, -10, 23, 1, 4, -23, 1, 2, -1, -2, -4, -7, 1,
1333 7, -24, -1, 24, -1, -1, 1, 3, -1, -25, 25, 4, -3, -4, 11, -11,
1334 26, -26, 6, 1, 1, -6, -5, -3, 3, 5, -1, -27, 27, 1, 4, -4,
1335 -1, -8, -1, 28, 2, 8, -12, -28, -2, -2, 2, 12, -1, 29, 1, -29,
1336 30, -30, 5, -5, 1, -31, -1, 3, 31, -1, 1, 1, -3, -13, 1, -7,
1337 -1, -32, 13, 7, 32, 33, -33, -1, -9, -34, 9, 34, -6, 5, 6, -5}
1343 {1, 1, 0, 1, 1, 2, 2, 1, 1, 3, 3, 1, 1, 0, 2, 2,
1344 4, 1, 4, 1, 1, 1, 5, 5, 1, 1, 6, 6, 2, 2, 1, 1,
1345 3, 3, 7, 7, 1, 1, 8, 8, 1, 1, 2, 2, 1, 9, 1, 9,
1346 4, 4, 10, 1, 1, 10, 1, 1, 11, 11, 3, 3, 1, 2, 1, 2,
1347 1, 1, 12, 12, 5, 5, 1, 1, 13, 1, 1, 13, 2, 2, 1, 1,
1348 6, 6, 1, 1, 4, 14, 4, 14, 3, 1, 3, 1, 1, 1, 15, 7,
1349 15, 2, 2, 7, 1, 1, 1, 8, 1, 8, 16, 16, 1, 1, 1, 1,
1350 2, 1, 1, 2, 1, 1, 3, 5, 5, 3, 4, 1, 1, 4, 1, 1,
1351 17, 17, 9, 1, 1, 9, 2, 2, 1, 1, 10, 10, 1, 6, 1, 1,
1352 6, 18, 1, 1, 18, 1, 1, 1, 2, 2, 3, 1, 3, 1, 1, 1,
1353 4, 1, 19, 1, 19, 7, 1, 1, 20, 1, 4, 20, 1, 7, 11, 2,
1354 1, 11, 21, 2, 8, 5, 1, 8, 1, 5, 21, 1, 1, 1, 22, 1,
1355 1, 22, 1, 1, 3, 3, 1, 23, 2, 12, 24, 1, 1, 2, 1, 1,
1356 12, 23, 1, 1, 24, 1, 1, 1, 4, 1, 1, 1, 2, 1, 6, 6,
1357 4, 2, 1, 1, 1, 1, 1, 1, 1, 14, 13, 3, 1, 25, 9, 25,
1358 14, 1, 9, 3, 13, 1, 1, 1, 1, 1, 10, 1, 1, 2, 10, 2},
1361 {-20, -1, 0, 2, -2, 1, -1, 3, -3, 1, -1, 4, -4, 0, 2, -2,
1362 1, 5, -1, -5, 6, -6, 1, -1, 7, -7, 1, -1, 3, -3, 8, -8,
1363 2, -2, 1, -1, 9, -9, 1, -1, 10, -10, 4, -4, 11, 1, -11, -1,
1364 2, -2, 1, 12, -12, -1, 13, -13, 1, -1, 3, -3, 14, 5, -14, -5,
1365 -15, 15, -1, 1, 2, -2, 16, -16, 1, 17, -17, -1, 6, -6, 18, -18,
1366 2, -2, -19, 19, -3, 1, 3, -1, 4, 20, -4, 1, -21, 21, 1, 2,
1367 -1, -7, 7, -2, 22, -22, 23, 2, -23, -2, 1, -1, -24, 24, -25, 25,
1368 -8, -26, 26, 8, -27, 27, 5, 3, -3, -5, -4, 28, -28, 4, 29, -29,
1369 1, -1, -2, -30, 30, 2, 9, -9, -31, 31, 2, -2, -32, 3, 32, -33,
1370 -3, 1, 33, -34, -1, 34, -35, 35, -10, 10, -6, 36, 6, -36, 37, -37,
1371 -5, 38, 1, -38, -1, 3, 39, -39, -1, 40, 5, 1, -40, -3, 2, -11,
1372 -41, -2, 1, 11, -3, -4, 41, 3, 42, 4, -1, -43, -42, 43, 1, -44,
1373 45, -1, 44, -45, -7, 7, -46, 1, -12, 2, 1, -47, 46, 12, 47, 48,
1374 -2, -1, -48, 49, -1, -50, -49, 50, -6, -51, 51, 52, -13, 53, -4, 4,
1375 6, 13, -53, -52, -54, 55, 54, -55, -56, -2, 2, -8, 56, 1, -3, -1,
1376 2, 58, 3, 8, -2, 57, -58, -60, -59, -57, -3, 60, 59, -14, 3, 14}
1382 {1, 1, 0, 2, 2, 1, 1, 3, 3, 4, 4, 5, 5, 1, 1, 6,
1383 6, 2, 2, 7, 7, 8, 8, 1, 1, 3, 3, 9, 9, 10, 10, 1,
1384 1, 2, 2, 4, 4, 11, 0, 11, 12, 12, 13, 13, 1, 1, 5, 5,
1385 14, 14, 15, 16, 15, 16, 3, 3, 1, 6, 1, 6, 2, 2, 7, 7,
1386 8, 8, 17, 17, 1, 1, 4, 4, 18, 18, 2, 2, 1, 19, 1, 20,
1387 19, 20, 21, 21, 3, 3, 22, 22, 5, 5, 24, 1, 1, 23, 9, 23,
1388 24, 9, 2, 2, 10, 1, 1, 10, 6, 6, 25, 4, 4, 25, 7, 7,
1389 26, 8, 1, 8, 3, 1, 26, 3, 11, 11, 27, 27, 2, 28, 1, 2,
1390 28, 1, 12, 12, 5, 5, 29, 13, 13, 29, 32, 1, 1, 33, 31, 30,
1391 32, 4, 30, 33, 4, 31, 3, 14, 1, 1, 3, 34, 34, 2, 2, 14,
1392 6, 6, 35, 36, 35, 36, 1, 15, 1, 16, 16, 15, 7, 9, 7, 9,
1393 37, 8, 8, 37, 1, 1, 39, 2, 38, 39, 2, 40, 5, 38, 40, 5,
1394 3, 3, 4, 4, 10, 10, 1, 1, 1, 1, 41, 2, 41, 2, 6, 6,
1395 1, 1, 11, 42, 11, 43, 3, 42, 3, 17, 4, 43, 1, 17, 7, 1,
1396 8, 44, 4, 7, 44, 5, 8, 2, 5, 1, 2, 48, 45, 1, 12, 45,
1397 12, 48, 13, 13, 1, 9, 9, 46, 1, 46, 47, 47, 49, 18, 18, 49},
1400 { 1, -1, 0, 1, -1, 2, -2, 1, -1, 1, -1, 1, -1, 3, -3, 1,
1401 -1, -2, 2, 1, -1, 1, -1, 4, -4, -2, 2, 1, -1, 1, -1, 5,
1402 -5, -3, 3, 2, -2, 1, 0, -1, 1, -1, 1, -1, 6, -6, 2, -2,
1403 1, -1, 1, 1, -1, -1, -3, 3, 7, 2, -7, -2, -4, 4, 2, -2,
1404 2, -2, 1, -1, 8, -8, 3, -3, 1, -1, -5, 5, 9, 1, -9, 1,
1405 -1, -1, 1, -1, -4, 4, 1, -1, 3, -3, 1, -10, 10, 1, 2, -1,
1406 -1, -2, 6, -6, 2, 11, -11, -2, 3, -3, 1, -4, 4, -1, 3, -3,
1407 1, 3, 12, -3, -5, -12, -1, 5, 2, -2, 1, -1, -7, 1, 13, 7,
1408 -1, -13, 2, -2, 4, -4, 1, 2, -2, -1, 1, 14, -14, 1, 1, 1,
1409 -1, -5, -1, -1, 5, -1, -6, 2, -15, 15, 6, 1, -1, -8, 8, -2,
1410 -4, 4, 1, 1, -1, -1, 16, 2, -16, -2, 2, -2, 4, 3, -4, -3,
1411 -1, -4, 4, 1, -17, 17, -1, -9, 1, 1, 9, 1, -5, -1, -1, 5,
1412 -7, 7, 6, -6, 3, -3, 18, -18, 19, -19, 1, -10, -1, 10, -5, 5,
1413 20, -20, -3, 1, 3, 1, 8, -1, -8, 2, 7, -1, -21, -2, 5, 21,
1414 5, -1, -7, -5, 1, -6, -5, -11, 6, 22, 11, 1, 1, -22, -3, -1,
1415 3, -1, 3, -3, -23, 4, -4, 1, 23, -1, 1, -1, 1, -2, 2, -1}
1421 {1, 1, 1, 1, 0, 2, 2, 1, 1, 3, 3, 0, 1, 1, 2, 2,
1422 4, 4, 1, 1, 5, 5, 1, 1, 2, 2, 3, 3, 6, 6, 1, 1,
1423 7, 7, 8, 1, 8, 2, 2, 1, 4, 4, 1, 3, 1, 3, 9, 9,
1424 2, 2, 1, 5, 1, 5, 10, 10, 1, 1, 11, 11, 3, 6, 3, 4,
1425 4, 6, 2, 2, 1, 12, 1, 12, 7, 13, 7, 13, 1, 1, 8, 8,
1426 2, 2, 14, 14, 16, 15, 16, 5, 5, 1, 3, 15, 1, 3, 4, 4,
1427 1, 1, 17, 17, 2, 2, 6, 6, 1, 18, 1, 18, 22, 21, 22, 21,
1428 25, 24, 25, 19, 9, 20, 9, 23, 19, 24, 20, 3, 23, 7, 3, 1,
1429 1, 7, 28, 26, 29, 5, 28, 26, 5, 8, 29, 4, 8, 27, 2, 2,
1430 4, 27, 1, 1, 10, 36, 10, 33, 33, 36, 30, 1, 32, 32, 1, 30,
1431 6, 31, 31, 35, 3, 6, 11, 11, 3, 2, 35, 2, 34, 1, 34, 1,
1432 37, 37, 12, 7, 12, 5, 41, 5, 4, 7, 1, 8, 13, 4, 1, 41,
1433 13, 38, 8, 38, 9, 1, 40, 40, 9, 1, 39, 2, 2, 49, 39, 42,
1434 3, 3, 14, 16, 49, 14, 16, 42, 43, 43, 6, 6, 15, 1, 1, 15,
1435 44, 44, 1, 1, 50, 48, 4, 5, 4, 7, 5, 2, 10, 10, 48, 7,
1436 50, 45, 2, 1, 45, 8, 8, 1, 46, 46, 3, 47, 47, 3, 1, 1},
1439 { 1, -1, 2, -2, 0, 1, -1, 3, -3, 1, -1, 0, 4, -4, 2, -2,
1440 1, -1, 5, -5, 1, -1, 6, -6, 3, -3, 2, -2, 1, -1, 7, -7,
1441 1, -1, 1, 8, -1, 4, -4, -8, 2, -2, 9, 3, -9, -3, 1, -1,
1442 5, -5, 10, 2, -10, -2, 1, -1, 11, -11, 1, -1, -4, 2, 4, 3,
1443 -3, -2, 6, -6, 12, 1, -12, -1, 2, 1, -2, -1, 13, -13, 2, -2,
1444 7, -7, 1, -1, 1, 1, -1, 3, -3, 14, 5, -1, -14, -5, 4, -4,
1445 15, -15, 1, -1, 8, -8, -3, 3, 16, 1, -16, -1, 1, 1, -1, -1,
1446 1, 1, -1, 1, 2, 1, -2, 1, -1, -1, -1, 6, -1, 3, -6, 17,
1447 -17, -3, 1, 1, 1, 4, -1, -1, -4, 3, -1, 5, -3, -1, -9, 9,
1448 -5, 1, 18, -18, 2, 1, -2, 1, -1, -1, 1, 19, -1, 1, -19, -1,
1449 4, 1, -1, 1, 7, -4, -2, 2, -7, 10, -1, -10, 1, 20, -1, -20,
1450 1, -1, 2, 4, -2, 5, 1, -5, 6, -4, 21, 4, 2, -6, -21, -1,
1451 -2, 1, -4, -1, -3, 22, -1, 1, 3, -22, -1, 11, -11, 1, 1, 1,
1452 8, -8, 2, 2, -1, -2, -2, -1, 1, -1, -5, 5, 2, 23, -23, -2,
1453 1, -1, 24, -24, -1, -1, 7, 6, -7, 5, -6, 12, -3, 3, 1, -5,
1454 1, 1, -12, 25, -1, -5, 5, -25, -1, 1, 9, 1, -1, -9, 26, -26}