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"
39 * These are 2x8 predefined Huffman codebooks for coding macroblock/block
40 * signals. They are specified using "huffman descriptors" in order to
41 * avoid huge static tables. The decoding tables will be generated at
42 * startup from these descriptors.
44 /** static macroblock huffman tables */
45 static const IVIHuffDesc ivi_mb_huff_desc[8] = {
46 {8, {0, 4, 5, 4, 4, 4, 6, 6}},
47 {12, {0, 2, 2, 3, 3, 3, 3, 5, 3, 2, 2, 2}},
48 {12, {0, 2, 3, 4, 3, 3, 3, 3, 4, 3, 2, 2}},
49 {12, {0, 3, 4, 4, 3, 3, 3, 3, 3, 2, 2, 2}},
50 {13, {0, 4, 4, 3, 3, 3, 3, 2, 3, 3, 2, 1, 1}},
51 {9, {0, 4, 4, 4, 4, 3, 3, 3, 2}},
52 {10, {0, 4, 4, 4, 4, 3, 3, 2, 2, 2}},
53 {12, {0, 4, 4, 4, 3, 3, 2, 3, 2, 2, 2, 2}}
56 /** static block huffman tables */
57 static const IVIHuffDesc ivi_blk_huff_desc[8] = {
58 {10, {1, 2, 3, 4, 4, 7, 5, 5, 4, 1}},
59 {11, {2, 3, 4, 4, 4, 7, 5, 4, 3, 3, 2}},
60 {12, {2, 4, 5, 5, 5, 5, 6, 4, 4, 3, 1, 1}},
61 {13, {3, 3, 4, 4, 5, 6, 6, 4, 4, 3, 2, 1, 1}},
62 {11, {3, 4, 4, 5, 5, 5, 6, 5, 4, 2, 2}},
63 {13, {3, 4, 5, 5, 5, 5, 6, 4, 3, 3, 2, 1, 1}},
64 {13, {3, 4, 5, 5, 5, 6, 5, 4, 3, 3, 2, 1, 1}},
65 {9, {3, 4, 4, 5, 5, 5, 6, 5, 5}}
68 static VLC ivi_mb_vlc_tabs [8]; ///< static macroblock Huffman tables
69 static VLC ivi_blk_vlc_tabs[8]; ///< static block Huffman tables
71 typedef void (*ivi_mc_func) (int16_t *buf, const int16_t *ref_buf,
72 uint32_t pitch, int mc_type);
74 static int ivi_mc(IVIBandDesc *band, ivi_mc_func mc,
75 int offs, int mv_x, int mv_y, int mc_type)
77 int ref_offs = offs + mv_y * band->pitch + mv_x;
78 int buf_size = band->pitch * band->aheight;
79 int min_size = band->pitch * (band->blk_size - 1) + band->blk_size;
80 int ref_size = (mc_type > 1) * band->pitch + (mc_type & 1);
82 if (offs < 0 || ref_offs < 0 || !band->ref_buf)
83 return AVERROR_INVALIDDATA;
84 if (buf_size - min_size < offs)
85 return AVERROR_INVALIDDATA;
86 if (buf_size - min_size - ref_size < ref_offs)
87 return AVERROR_INVALIDDATA;
89 mc(band->buf + offs, band->ref_buf + ref_offs, band->pitch, mc_type);
95 * Reverse "nbits" bits of the value "val" and return the result
96 * in the least significant bits.
98 static uint16_t inv_bits(uint16_t val, int nbits)
103 res = ff_reverse[val] >> (8 - nbits);
105 res = ((ff_reverse[val & 0xFF] << 8) +
106 (ff_reverse[val >> 8])) >> (16 - nbits);
112 * Generate a huffman codebook from the given descriptor
113 * and convert it into the Libav VLC table.
115 * @param[in] cb pointer to codebook descriptor
116 * @param[out] vlc where to place the generated VLC table
117 * @param[in] flag flag: 1 - for static or 0 for dynamic tables
118 * @return result code: 0 - OK, -1 = error (invalid codebook descriptor)
120 static int ivi_create_huff_from_desc(const IVIHuffDesc *cb, VLC *vlc, int flag)
122 int pos, i, j, codes_per_row, prefix, not_last_row;
123 uint16_t codewords[256]; /* FIXME: move this temporal storage out? */
126 pos = 0; /* current position = 0 */
128 for (i = 0; i < cb->num_rows; i++) {
129 codes_per_row = 1 << cb->xbits[i];
130 not_last_row = (i != cb->num_rows - 1);
131 prefix = ((1 << i) - 1) << (cb->xbits[i] + not_last_row);
133 for (j = 0; j < codes_per_row; j++) {
134 if (pos >= 256) /* Some Indeo5 codebooks can have more than 256 */
135 break; /* elements, but only 256 codes are allowed! */
137 bits[pos] = i + cb->xbits[i] + not_last_row;
138 if (bits[pos] > IVI_VLC_BITS)
139 return AVERROR_INVALIDDATA; /* invalid descriptor */
141 codewords[pos] = inv_bits((prefix | j), bits[pos]);
149 /* number of codewords = pos */
150 return init_vlc(vlc, IVI_VLC_BITS, pos, bits, 1, 1, codewords, 2, 2,
151 (flag ? INIT_VLC_USE_NEW_STATIC : 0) | INIT_VLC_LE);
154 av_cold void ff_ivi_init_static_vlc(void)
157 static VLC_TYPE table_data[8192 * 16][2];
158 static int initialized_vlcs = 0;
160 if (initialized_vlcs)
162 for (i = 0; i < 8; i++) {
163 ivi_mb_vlc_tabs[i].table = table_data + i * 2 * 8192;
164 ivi_mb_vlc_tabs[i].table_allocated = 8192;
165 ivi_create_huff_from_desc(&ivi_mb_huff_desc[i],
166 &ivi_mb_vlc_tabs[i], 1);
167 ivi_blk_vlc_tabs[i].table = table_data + (i * 2 + 1) * 8192;
168 ivi_blk_vlc_tabs[i].table_allocated = 8192;
169 ivi_create_huff_from_desc(&ivi_blk_huff_desc[i],
170 &ivi_blk_vlc_tabs[i], 1);
172 initialized_vlcs = 1;
176 * Copy huffman codebook descriptors.
178 * @param[out] dst ptr to the destination descriptor
179 * @param[in] src ptr to the source descriptor
181 static void ivi_huff_desc_copy(IVIHuffDesc *dst, const IVIHuffDesc *src)
183 dst->num_rows = src->num_rows;
184 memcpy(dst->xbits, src->xbits, src->num_rows);
188 * Compare two huffman codebook descriptors.
190 * @param[in] desc1 ptr to the 1st descriptor to compare
191 * @param[in] desc2 ptr to the 2nd descriptor to compare
192 * @return comparison result: 0 - equal, 1 - not equal
194 static int ivi_huff_desc_cmp(const IVIHuffDesc *desc1,
195 const IVIHuffDesc *desc2)
197 return desc1->num_rows != desc2->num_rows ||
198 memcmp(desc1->xbits, desc2->xbits, desc1->num_rows);
201 int ff_ivi_dec_huff_desc(GetBitContext *gb, int desc_coded, int which_tab,
202 IVIHuffTab *huff_tab, AVCodecContext *avctx)
205 IVIHuffDesc new_huff;
208 /* select default table */
209 huff_tab->tab = (which_tab) ? &ivi_blk_vlc_tabs[7]
210 : &ivi_mb_vlc_tabs [7];
214 huff_tab->tab_sel = get_bits(gb, 3);
215 if (huff_tab->tab_sel == 7) {
216 /* custom huffman table (explicitly encoded) */
217 new_huff.num_rows = get_bits(gb, 4);
218 if (!new_huff.num_rows) {
219 av_log(avctx, AV_LOG_ERROR, "Empty custom Huffman table!\n");
220 return AVERROR_INVALIDDATA;
223 for (i = 0; i < new_huff.num_rows; i++)
224 new_huff.xbits[i] = get_bits(gb, 4);
226 /* Have we got the same custom table? Rebuild if not. */
227 if (ivi_huff_desc_cmp(&new_huff, &huff_tab->cust_desc)) {
228 ivi_huff_desc_copy(&huff_tab->cust_desc, &new_huff);
230 if (huff_tab->cust_tab.table)
231 ff_free_vlc(&huff_tab->cust_tab);
232 result = ivi_create_huff_from_desc(&huff_tab->cust_desc,
233 &huff_tab->cust_tab, 0);
235 // reset faulty description
236 huff_tab->cust_desc.num_rows = 0;
237 av_log(avctx, AV_LOG_ERROR,
238 "Error while initializing custom vlc table!\n");
242 huff_tab->tab = &huff_tab->cust_tab;
244 /* select one of predefined tables */
245 huff_tab->tab = (which_tab) ? &ivi_blk_vlc_tabs[huff_tab->tab_sel]
246 : &ivi_mb_vlc_tabs [huff_tab->tab_sel];
253 * Free planes, bands and macroblocks buffers.
255 * @param[in] planes pointer to the array of the plane descriptors
257 static av_cold void ivi_free_buffers(IVIPlaneDesc *planes)
261 for (p = 0; p < 3; p++) {
262 for (b = 0; b < planes[p].num_bands; b++) {
263 av_freep(&planes[p].bands[b].bufs[0]);
264 av_freep(&planes[p].bands[b].bufs[1]);
265 av_freep(&planes[p].bands[b].bufs[2]);
267 if (planes[p].bands[b].blk_vlc.cust_tab.table)
268 ff_free_vlc(&planes[p].bands[b].blk_vlc.cust_tab);
269 for (t = 0; t < planes[p].bands[b].num_tiles; t++)
270 av_freep(&planes[p].bands[b].tiles[t].mbs);
271 av_freep(&planes[p].bands[b].tiles);
273 av_freep(&planes[p].bands);
274 planes[p].num_bands = 0;
278 av_cold int ff_ivi_init_planes(IVIPlaneDesc *planes, const IVIPicConfig *cfg)
281 uint32_t b_width, b_height, align_fac, width_aligned,
282 height_aligned, buf_size;
285 ivi_free_buffers(planes);
287 if (cfg->pic_width < 1 || cfg->pic_height < 1 ||
288 cfg->luma_bands < 1 || cfg->chroma_bands < 1)
289 return AVERROR_INVALIDDATA;
291 /* fill in the descriptor of the luminance plane */
292 planes[0].width = cfg->pic_width;
293 planes[0].height = cfg->pic_height;
294 planes[0].num_bands = cfg->luma_bands;
296 /* fill in the descriptors of the chrominance planes */
297 planes[1].width = planes[2].width = (cfg->pic_width + 3) >> 2;
298 planes[1].height = planes[2].height = (cfg->pic_height + 3) >> 2;
299 planes[1].num_bands = planes[2].num_bands = cfg->chroma_bands;
301 for (p = 0; p < 3; p++) {
302 planes[p].bands = av_mallocz(planes[p].num_bands * sizeof(IVIBandDesc));
303 if (!planes[p].bands)
304 return AVERROR(ENOMEM);
306 /* select band dimensions: if there is only one band then it
307 * has the full size, if there are several bands each of them
308 * has only half size */
309 b_width = planes[p].num_bands == 1 ? planes[p].width
310 : (planes[p].width + 1) >> 1;
311 b_height = planes[p].num_bands == 1 ? planes[p].height
312 : (planes[p].height + 1) >> 1;
314 /* luma band buffers will be aligned on 16x16 (max macroblock size) */
315 /* chroma band buffers will be aligned on 8x8 (max macroblock size) */
316 align_fac = p ? 8 : 16;
317 width_aligned = FFALIGN(b_width , align_fac);
318 height_aligned = FFALIGN(b_height, align_fac);
319 buf_size = width_aligned * height_aligned * sizeof(int16_t);
321 for (b = 0; b < planes[p].num_bands; b++) {
322 band = &planes[p].bands[b]; /* select appropriate plane/band */
325 band->width = b_width;
326 band->height = b_height;
327 band->pitch = width_aligned;
328 band->aheight = height_aligned;
329 band->bufs[0] = av_mallocz(buf_size);
330 band->bufs[1] = av_mallocz(buf_size);
331 if (!band->bufs[0] || !band->bufs[1])
332 return AVERROR(ENOMEM);
334 /* allocate the 3rd band buffer for scalability mode */
335 if (cfg->luma_bands > 1) {
336 band->bufs[2] = av_mallocz(buf_size);
338 return AVERROR(ENOMEM);
340 /* reset custom vlc */
341 planes[p].bands[0].blk_vlc.cust_desc.num_rows = 0;
348 static int ivi_init_tiles(IVIBandDesc *band, IVITile *ref_tile,
349 int p, int b, int t_height, int t_width)
352 IVITile *tile = band->tiles;
354 for (y = 0; y < band->height; y += t_height) {
355 for (x = 0; x < band->width; x += t_width) {
358 tile->mb_size = band->mb_size;
359 tile->width = FFMIN(band->width - x, t_width);
360 tile->height = FFMIN(band->height - y, t_height);
361 tile->is_empty = tile->data_size = 0;
362 /* calculate number of macroblocks */
363 tile->num_MBs = IVI_MBs_PER_TILE(tile->width, tile->height,
366 av_freep(&tile->mbs);
367 tile->mbs = av_malloc(tile->num_MBs * sizeof(IVIMbInfo));
369 return AVERROR(ENOMEM);
373 if (tile->num_MBs != ref_tile->num_MBs)
374 return AVERROR_INVALIDDATA;
375 tile->ref_mbs = ref_tile->mbs;
385 av_cold int ff_ivi_init_tiles(IVIPlaneDesc *planes,
386 int tile_width, int tile_height)
388 int p, b, x_tiles, y_tiles, t_width, t_height, ret;
391 for (p = 0; p < 3; p++) {
392 t_width = !p ? tile_width : (tile_width + 3) >> 2;
393 t_height = !p ? tile_height : (tile_height + 3) >> 2;
395 if (!p && planes[0].num_bands == 4) {
400 for (b = 0; b < planes[p].num_bands; b++) {
401 band = &planes[p].bands[b];
402 x_tiles = IVI_NUM_TILES(band->width, t_width);
403 y_tiles = IVI_NUM_TILES(band->height, t_height);
404 band->num_tiles = x_tiles * y_tiles;
406 av_freep(&band->tiles);
407 band->tiles = av_mallocz(band->num_tiles * sizeof(IVITile));
409 return AVERROR(ENOMEM);
411 /* use the first luma band as reference for motion vectors
413 ret = ivi_init_tiles(band, planes[0].bands[0].tiles,
414 p, b, t_height, t_width);
424 * Decode size of the tile data.
425 * The size is stored as a variable-length field having the following format:
426 * if (tile_data_size < 255) than this field is only one byte long
427 * if (tile_data_size >= 255) than this field four is byte long: 0xFF X1 X2 X3
428 * where X1-X3 is size of the tile data
430 * @param[in,out] gb the GetBit context
431 * @return size of the tile data in bytes
433 static int ivi_dec_tile_data_size(GetBitContext *gb)
439 len = get_bits(gb, 8);
441 len = get_bits_long(gb, 24);
444 /* align the bitstream reader on the byte boundary */
450 static int ivi_dc_transform(IVIBandDesc *band, int *prev_dc, int buf_offs,
453 int buf_size = band->pitch * band->aheight - buf_offs;
454 int min_size = (blk_size - 1) * band->pitch + blk_size;
456 if (!band->dc_transform)
460 if (min_size > buf_size)
461 return AVERROR_INVALIDDATA;
463 band->dc_transform(prev_dc, band->buf + buf_offs,
464 band->pitch, blk_size);
469 static int ivi_decode_coded_blocks(GetBitContext *gb, IVIBandDesc *band,
470 ivi_mc_func mc, int mv_x, int mv_y,
471 int *prev_dc, int is_intra, int mc_type,
472 uint32_t quant, int offs,
473 AVCodecContext *avctx)
475 const uint16_t *base_tab = is_intra ? band->intra_base : band->inter_base;
476 RVMapDesc *rvmap = band->rv_map;
477 uint8_t col_flags[8];
479 uint32_t sym = 0, lo, hi, q;
481 int blk_size = band->blk_size;
482 int num_coeffs = blk_size * blk_size;
483 int col_mask = blk_size - 1;
485 int min_size = band->pitch * (band->transform_size - 1) +
486 band->transform_size;
487 int buf_size = band->pitch * band->aheight - offs;
489 if (min_size > buf_size)
490 return AVERROR_INVALIDDATA;
493 av_log(avctx, AV_LOG_ERROR, "Scan pattern is not set.\n");
494 return AVERROR_INVALIDDATA;
497 /* zero transform vector */
498 memset(trvec, 0, num_coeffs * sizeof(trvec[0]));
499 /* zero column flags */
500 memset(col_flags, 0, sizeof(col_flags));
501 while (scan_pos <= num_coeffs) {
502 sym = get_vlc2(gb, band->blk_vlc.tab->table,
504 if (sym == rvmap->eob_sym)
505 break; /* End of block */
507 /* Escape - run/val explicitly coded using 3 vlc codes */
508 if (sym == rvmap->esc_sym) {
509 run = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1) + 1;
510 lo = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
511 hi = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
512 /* merge them and convert into signed val */
513 val = IVI_TOSIGNED((hi << 6) | lo);
516 av_log(avctx, AV_LOG_ERROR, "Invalid sym encountered: %d.\n", sym);
517 return AVERROR_INVALIDDATA;
519 run = rvmap->runtab[sym];
520 val = rvmap->valtab[sym];
523 /* de-zigzag and dequantize */
525 if (scan_pos >= num_coeffs || scan_pos < 0)
527 pos = band->scan[scan_pos];
530 av_dlog(avctx, "Val = 0 encountered!\n");
532 q = (base_tab[pos] * quant) >> 9;
534 val = val * q + FFSIGN(val) * (((q ^ 1) - 1) >> 1);
536 /* track columns containing non-zero coeffs */
537 col_flags[pos & col_mask] |= !!val;
540 if (scan_pos < 0 || scan_pos >= num_coeffs && sym != rvmap->eob_sym)
541 return AVERROR_INVALIDDATA; /* corrupt block data */
543 /* undoing DC coeff prediction for intra-blocks */
544 if (is_intra && band->is_2d_trans) {
545 *prev_dc += trvec[0];
547 col_flags[0] |= !!*prev_dc;
550 /* apply inverse transform */
551 band->inv_transform(trvec, band->buf + offs,
552 band->pitch, col_flags);
554 /* apply motion compensation */
556 return ivi_mc(band, mc, offs, mv_x, mv_y, mc_type);
562 * extract huffman-coded transform coefficients from the bitstream,
563 * dequantize them, apply inverse transform and motion compensation
564 * in order to reconstruct the picture.
566 * @param[in,out] gb the GetBit context
567 * @param[in] band pointer to the band descriptor
568 * @param[in] tile pointer to the tile descriptor
569 * @return result code: 0 - OK, -1 = error (corrupted blocks data)
571 static int ivi_decode_blocks(GetBitContext *gb, IVIBandDesc *band,
572 IVITile *tile, AVCodecContext *avctx)
574 int mbn, blk, num_blocks, blk_size, ret, is_intra, mc_type = 0;
575 int mv_x = 0, mv_y = 0;
577 uint32_t cbp, quant, buf_offs;
579 ivi_mc_func mc_with_delta_func, mc_no_delta_func;
580 const uint8_t *scale_tab;
582 /* init intra prediction for the DC coefficient */
584 blk_size = band->blk_size;
585 /* number of blocks per mb */
586 num_blocks = (band->mb_size != blk_size) ? 4 : 1;
588 mc_with_delta_func = ff_ivi_mc_8x8_delta;
589 mc_no_delta_func = ff_ivi_mc_8x8_no_delta;
591 mc_with_delta_func = ff_ivi_mc_4x4_delta;
592 mc_no_delta_func = ff_ivi_mc_4x4_no_delta;
595 for (mbn = 0, mb = tile->mbs; mbn < tile->num_MBs; mb++, mbn++) {
596 is_intra = !mb->type;
598 buf_offs = mb->buf_offs;
600 quant = band->glob_quant + mb->q_delta;
601 if (avctx->codec_id == AV_CODEC_ID_INDEO4)
602 quant = av_clip(quant, 0, 31);
604 quant = av_clip(quant, 0, 23);
606 scale_tab = is_intra ? band->intra_scale : band->inter_scale;
608 quant = scale_tab[quant];
613 if (band->is_halfpel) {
614 mc_type = ((mv_y & 1) << 1) | (mv_x & 1);
616 mv_y >>= 1; /* convert halfpel vectors into fullpel ones */
619 int dmv_x, dmv_y, cx, cy;
621 dmv_x = mb->mv_x >> band->is_halfpel;
622 dmv_y = mb->mv_y >> band->is_halfpel;
623 cx = mb->mv_x & band->is_halfpel;
624 cy = mb->mv_y & band->is_halfpel;
626 if (mb->xpos + dmv_x < 0 ||
627 mb->xpos + dmv_x + band->mb_size + cx > band->pitch ||
628 mb->ypos + dmv_y < 0 ||
629 mb->ypos + dmv_y + band->mb_size + cy > band->aheight) {
630 return AVERROR_INVALIDDATA;
635 for (blk = 0; blk < num_blocks; blk++) {
636 /* adjust block position in the buffer according to its number */
638 buf_offs += blk_size;
639 } else if (blk == 2) {
640 buf_offs -= blk_size;
641 buf_offs += blk_size * band->pitch;
644 if (cbp & 1) { /* block coded ? */
645 ret = ivi_decode_coded_blocks(gb, band, mc_with_delta_func,
646 mv_x, mv_y, &prev_dc, is_intra,
647 mc_type, quant, buf_offs, avctx);
651 /* block not coded */
652 /* for intra blocks apply the dc slant transform */
653 /* for inter - perform the motion compensation without delta */
655 ret = ivi_dc_transform(band, &prev_dc, buf_offs, blk_size);
659 ret = ivi_mc(band, mc_no_delta_func, buf_offs,
660 mv_x, mv_y, mc_type);
676 * Handle empty tiles by performing data copying and motion
677 * compensation respectively.
679 * @param[in] avctx ptr to the AVCodecContext
680 * @param[in] band pointer to the band descriptor
681 * @param[in] tile pointer to the tile descriptor
682 * @param[in] mv_scale scaling factor for motion vectors
684 static int ivi_process_empty_tile(AVCodecContext *avctx, IVIBandDesc *band,
685 IVITile *tile, int32_t mv_scale)
687 int x, y, need_mc, mbn, blk, num_blocks, mv_x, mv_y, mc_type;
688 int offs, mb_offset, row_offset, ret;
689 IVIMbInfo *mb, *ref_mb;
692 ivi_mc_func mc_no_delta_func;
694 if (tile->num_MBs != IVI_MBs_PER_TILE(tile->width, tile->height, band->mb_size)) {
695 av_log(avctx, AV_LOG_ERROR, "Allocated tile size %d mismatches "
696 "parameters %d in ivi_process_empty_tile()\n",
697 tile->num_MBs, IVI_MBs_PER_TILE(tile->width, tile->height, band->mb_size));
698 return AVERROR_INVALIDDATA;
701 offs = tile->ypos * band->pitch + tile->xpos;
703 ref_mb = tile->ref_mbs;
704 row_offset = band->mb_size * band->pitch;
705 need_mc = 0; /* reset the mc tracking flag */
707 for (y = tile->ypos; y < (tile->ypos + tile->height); y += band->mb_size) {
710 for (x = tile->xpos; x < (tile->xpos + tile->width); x += band->mb_size) {
713 mb->buf_offs = mb_offset;
715 mb->type = 1; /* set the macroblocks type = INTER */
716 mb->cbp = 0; /* all blocks are empty */
718 if (!band->qdelta_present && !band->plane && !band->band_num) {
719 mb->q_delta = band->glob_quant;
724 if (band->inherit_qdelta && ref_mb)
725 mb->q_delta = ref_mb->q_delta;
727 if (band->inherit_mv && ref_mb) {
728 /* motion vector inheritance */
730 mb->mv_x = ivi_scale_mv(ref_mb->mv_x, mv_scale);
731 mb->mv_y = ivi_scale_mv(ref_mb->mv_y, mv_scale);
733 mb->mv_x = ref_mb->mv_x;
734 mb->mv_y = ref_mb->mv_y;
736 need_mc |= mb->mv_x || mb->mv_y; /* tracking non-zero motion vectors */
742 mb_offset += band->mb_size;
747 if (band->inherit_mv && need_mc) { /* apply motion compensation if there is at least one non-zero motion vector */
748 num_blocks = (band->mb_size != band->blk_size) ? 4 : 1; /* number of blocks per mb */
749 mc_no_delta_func = (band->blk_size == 8) ? ff_ivi_mc_8x8_no_delta
750 : ff_ivi_mc_4x4_no_delta;
752 for (mbn = 0, mb = tile->mbs; mbn < tile->num_MBs; mb++, mbn++) {
755 if (!band->is_halfpel) {
756 mc_type = 0; /* we have only fullpel vectors */
758 mc_type = ((mv_y & 1) << 1) | (mv_x & 1);
760 mv_y >>= 1; /* convert halfpel vectors into fullpel ones */
763 for (blk = 0; blk < num_blocks; blk++) {
764 /* adjust block position in the buffer according with its number */
765 offs = mb->buf_offs + band->blk_size * ((blk & 1) + !!(blk & 2) * band->pitch);
766 ret = ivi_mc(band, mc_no_delta_func, offs,
767 mv_x, mv_y, mc_type);
773 /* copy data from the reference tile into the current one */
774 src = band->ref_buf + tile->ypos * band->pitch + tile->xpos;
775 dst = band->buf + tile->ypos * band->pitch + tile->xpos;
776 for (y = 0; y < tile->height; y++) {
777 memcpy(dst, src, tile->width*sizeof(band->buf[0]));
788 static uint16_t ivi_calc_band_checksum(IVIBandDesc *band)
791 int16_t *src, checksum;
796 for (y = 0; y < band->height; src += band->pitch, y++)
797 for (x = 0; x < band->width; x++)
805 * Convert and output the current plane.
806 * This conversion is done by adding back the bias value of 128
807 * (subtracted in the encoder) and clipping the result.
809 * @param[in] plane pointer to the descriptor of the plane being processed
810 * @param[out] dst pointer to the buffer receiving converted pixels
811 * @param[in] dst_pitch pitch for moving to the next y line
813 static void ivi_output_plane(IVIPlaneDesc *plane, uint8_t *dst, int dst_pitch)
816 const int16_t *src = plane->bands[0].buf;
817 uint32_t pitch = plane->bands[0].pitch;
822 for (y = 0; y < plane->height; y++) {
823 for (x = 0; x < plane->width; x++)
824 dst[x] = av_clip_uint8(src[x] + 128);
831 * Decode an Indeo 4 or 5 band.
833 * @param[in,out] ctx ptr to the decoder context
834 * @param[in,out] band ptr to the band descriptor
835 * @param[in] avctx ptr to the AVCodecContext
836 * @return result code: 0 = OK, -1 = error
838 static int decode_band(IVI45DecContext *ctx,
839 IVIBandDesc *band, AVCodecContext *avctx)
841 int result, i, t, idx1, idx2, pos;
844 band->buf = band->bufs[ctx->dst_buf];
846 av_log(avctx, AV_LOG_ERROR, "Band buffer points to no data!\n");
847 return AVERROR_INVALIDDATA;
849 band->ref_buf = band->bufs[ctx->ref_buf];
850 band->data_ptr = ctx->frame_data + (get_bits_count(&ctx->gb) >> 3);
852 result = ctx->decode_band_hdr(ctx, band, avctx);
854 av_log(avctx, AV_LOG_ERROR, "Error while decoding band header: %d\n",
859 if (band->is_empty) {
860 av_log(avctx, AV_LOG_ERROR, "Empty band encountered!\n");
861 return AVERROR_INVALIDDATA;
864 band->rv_map = &ctx->rvmap_tabs[band->rvmap_sel];
866 /* apply corrections to the selected rvmap table if present */
867 for (i = 0; i < band->num_corr; i++) {
868 idx1 = band->corr[i * 2];
869 idx2 = band->corr[i * 2 + 1];
870 FFSWAP(uint8_t, band->rv_map->runtab[idx1], band->rv_map->runtab[idx2]);
871 FFSWAP(int16_t, band->rv_map->valtab[idx1], band->rv_map->valtab[idx2]);
874 pos = get_bits_count(&ctx->gb);
876 for (t = 0; t < band->num_tiles; t++) {
877 tile = &band->tiles[t];
879 if (tile->mb_size != band->mb_size) {
880 av_log(avctx, AV_LOG_ERROR, "MB sizes mismatch: %d vs. %d\n",
881 band->mb_size, tile->mb_size);
882 return AVERROR_INVALIDDATA;
884 tile->is_empty = get_bits1(&ctx->gb);
885 if (tile->is_empty) {
886 result = ivi_process_empty_tile(avctx, band, tile,
887 (ctx->planes[0].bands[0].mb_size >> 3) - (band->mb_size >> 3));
890 av_dlog(avctx, "Empty tile encountered!\n");
892 tile->data_size = ivi_dec_tile_data_size(&ctx->gb);
893 if (!tile->data_size) {
894 av_log(avctx, AV_LOG_ERROR, "Tile data size is zero!\n");
895 return AVERROR_INVALIDDATA;
898 result = ctx->decode_mb_info(ctx, band, tile, avctx);
902 result = ivi_decode_blocks(&ctx->gb, band, tile, avctx);
904 av_log(avctx, AV_LOG_ERROR,
905 "Corrupted tile data encountered!\n");
909 if (((get_bits_count(&ctx->gb) - pos) >> 3) != tile->data_size) {
910 av_log(avctx, AV_LOG_ERROR,
911 "Tile data_size mismatch!\n");
912 result = AVERROR_INVALIDDATA;
916 pos += tile->data_size << 3; // skip to next tile
920 /* restore the selected rvmap table by applying its corrections in
922 for (i = band->num_corr-1; i >= 0; i--) {
923 idx1 = band->corr[i*2];
924 idx2 = band->corr[i*2+1];
925 FFSWAP(uint8_t, band->rv_map->runtab[idx1], band->rv_map->runtab[idx2]);
926 FFSWAP(int16_t, band->rv_map->valtab[idx1], band->rv_map->valtab[idx2]);
930 if (band->checksum_present) {
931 uint16_t chksum = ivi_calc_band_checksum(band);
932 if (chksum != band->checksum) {
933 av_log(avctx, AV_LOG_ERROR,
934 "Band checksum mismatch! Plane %d, band %d, "
935 "received: %x, calculated: %x\n",
936 band->plane, band->band_num, band->checksum, chksum);
941 align_get_bits(&ctx->gb);
946 int ff_ivi_decode_frame(AVCodecContext *avctx, void *data, int *got_frame,
949 IVI45DecContext *ctx = avctx->priv_data;
950 const uint8_t *buf = avpkt->data;
951 AVFrame *frame = data;
952 int buf_size = avpkt->size;
955 init_get_bits(&ctx->gb, buf, buf_size * 8);
956 ctx->frame_data = buf;
957 ctx->frame_size = buf_size;
959 result = ctx->decode_pic_hdr(ctx, avctx);
961 av_log(avctx, AV_LOG_ERROR,
962 "Error while decoding picture header: %d\n", result);
965 if (ctx->gop_invalid)
966 return AVERROR_INVALIDDATA;
968 if (ctx->gop_flags & IVI5_IS_PROTECTED) {
969 avpriv_report_missing_feature(avctx, "Password-protected clip!\n");
970 return AVERROR_PATCHWELCOME;
973 if (!ctx->planes[0].bands) {
974 av_log(avctx, AV_LOG_ERROR, "Color planes not initialized yet\n");
975 return AVERROR_INVALIDDATA;
978 ctx->switch_buffers(ctx);
982 if (ctx->is_nonnull_frame(ctx)) {
983 for (p = 0; p < 3; p++) {
984 for (b = 0; b < ctx->planes[p].num_bands; b++) {
985 result = decode_band(ctx, &ctx->planes[p].bands[b], avctx);
987 av_log(avctx, AV_LOG_ERROR,
988 "Error while decoding band: %d, plane: %d\n", b, p);
994 if (ctx->is_scalable)
995 return AVERROR_INVALIDDATA;
997 for (p = 0; p < 3; p++) {
998 if (!ctx->planes[p].bands[0].buf)
999 return AVERROR_INVALIDDATA;
1003 //STOP_TIMER("decode_planes"); }
1005 /* If the bidirectional mode is enabled, next I and the following P
1006 * frame will be sent together. Unfortunately the approach below seems
1007 * to be the only way to handle the B-frames mode.
1008 * That's exactly the same Intel decoders do.
1010 if (avctx->codec_id == AV_CODEC_ID_INDEO4 &&
1011 ctx->frame_type == 0/*FRAMETYPE_INTRA*/) {
1012 while (get_bits(&ctx->gb, 8)); // skip version string
1013 skip_bits_long(&ctx->gb, 64); // skip padding, TODO: implement correct 8-bytes alignment
1014 if (get_bits_left(&ctx->gb) > 18 && show_bits(&ctx->gb, 18) == 0x3FFF8)
1015 av_log(avctx, AV_LOG_ERROR, "Buffer contains IP frames!\n");
1018 result = ff_set_dimensions(avctx, ctx->planes[0].width, ctx->planes[0].height);
1022 if ((result = ff_get_buffer(avctx, frame, 0)) < 0) {
1023 av_log(avctx, AV_LOG_ERROR, "get_buffer() failed\n");
1027 if (ctx->is_scalable) {
1028 if (avctx->codec_id == AV_CODEC_ID_INDEO4)
1029 ff_ivi_recompose_haar(&ctx->planes[0], frame->data[0], frame->linesize[0]);
1031 ff_ivi_recompose53 (&ctx->planes[0], frame->data[0], frame->linesize[0]);
1033 ivi_output_plane(&ctx->planes[0], frame->data[0], frame->linesize[0]);
1036 ivi_output_plane(&ctx->planes[2], frame->data[1], frame->linesize[1]);
1037 ivi_output_plane(&ctx->planes[1], frame->data[2], frame->linesize[2]);
1045 * Close Indeo5 decoder and clean up its context.
1047 av_cold int ff_ivi_decode_close(AVCodecContext *avctx)
1049 IVI45DecContext *ctx = avctx->priv_data;
1051 ivi_free_buffers(&ctx->planes[0]);
1053 if (ctx->mb_vlc.cust_tab.table)
1054 ff_free_vlc(&ctx->mb_vlc.cust_tab);
1056 #if IVI4_STREAM_ANALYSER
1057 if (avctx->codec_id == AV_CODEC_ID_INDEO4) {
1058 if (ctx->is_scalable)
1059 av_log(avctx, AV_LOG_ERROR, "This video uses scalability mode!\n");
1060 if (ctx->uses_tiling)
1061 av_log(avctx, AV_LOG_ERROR, "This video uses local decoding!\n");
1062 if (ctx->has_b_frames)
1063 av_log(avctx, AV_LOG_ERROR, "This video contains B-frames!\n");
1064 if (ctx->has_transp)
1065 av_log(avctx, AV_LOG_ERROR, "Transparency mode is enabled!\n");
1067 av_log(avctx, AV_LOG_ERROR, "This video uses Haar transform!\n");
1068 if (ctx->uses_fullpel)
1069 av_log(avctx, AV_LOG_ERROR, "This video uses fullpel motion vectors!\n");
1078 * Scan patterns shared between indeo4 and indeo5
1080 const uint8_t ff_ivi_vertical_scan_8x8[64] = {
1081 0, 8, 16, 24, 32, 40, 48, 56,
1082 1, 9, 17, 25, 33, 41, 49, 57,
1083 2, 10, 18, 26, 34, 42, 50, 58,
1084 3, 11, 19, 27, 35, 43, 51, 59,
1085 4, 12, 20, 28, 36, 44, 52, 60,
1086 5, 13, 21, 29, 37, 45, 53, 61,
1087 6, 14, 22, 30, 38, 46, 54, 62,
1088 7, 15, 23, 31, 39, 47, 55, 63
1091 const uint8_t ff_ivi_horizontal_scan_8x8[64] = {
1092 0, 1, 2, 3, 4, 5, 6, 7,
1093 8, 9, 10, 11, 12, 13, 14, 15,
1094 16, 17, 18, 19, 20, 21, 22, 23,
1095 24, 25, 26, 27, 28, 29, 30, 31,
1096 32, 33, 34, 35, 36, 37, 38, 39,
1097 40, 41, 42, 43, 44, 45, 46, 47,
1098 48, 49, 50, 51, 52, 53, 54, 55,
1099 56, 57, 58, 59, 60, 61, 62, 63
1102 const uint8_t ff_ivi_direct_scan_4x4[16] = {
1103 0, 1, 4, 8, 5, 2, 3, 6, 9, 12, 13, 10, 7, 11, 14, 15
1108 * Run-value (RLE) tables.
1110 const RVMapDesc ff_ivi_rvmap_tabs[9] = {
1115 {1, 1, 0, 1, 1, 0, 1, 1, 2, 2, 1, 1, 1, 1, 3, 3,
1116 1, 1, 2, 2, 1, 1, 4, 4, 1, 1, 1, 1, 2, 2, 5, 5,
1117 1, 1, 3, 3, 1, 1, 6, 6, 1, 2, 1, 2, 7, 7, 1, 1,
1118 8, 8, 1, 1, 4, 2, 1, 4, 2, 1, 3, 3, 1, 1, 1, 9,
1119 9, 1, 2, 1, 2, 1, 5, 5, 1, 1, 10, 10, 1, 1, 3, 3,
1120 2, 2, 1, 1, 11, 11, 6, 4, 4, 1, 6, 1, 2, 1, 2, 12,
1121 8, 1, 12, 7, 8, 7, 1, 16, 1, 16, 1, 3, 3, 13, 1, 13,
1122 2, 2, 1, 15, 1, 5, 14, 15, 1, 5, 14, 1, 17, 8, 17, 8,
1123 1, 4, 4, 2, 2, 1, 25, 25, 24, 24, 1, 3, 1, 3, 1, 8,
1124 6, 7, 6, 1, 18, 8, 18, 1, 7, 23, 2, 2, 23, 1, 1, 21,
1125 22, 9, 9, 22, 19, 1, 21, 5, 19, 5, 1, 33, 20, 33, 20, 8,
1126 4, 4, 1, 32, 2, 2, 8, 3, 32, 26, 3, 1, 7, 7, 26, 6,
1127 1, 6, 1, 1, 16, 1, 10, 1, 10, 2, 16, 29, 28, 2, 29, 28,
1128 1, 27, 5, 8, 5, 27, 1, 8, 3, 7, 3, 31, 41, 31, 1, 41,
1129 6, 1, 6, 7, 4, 4, 1, 1, 2, 1, 2, 11, 34, 30, 11, 1,
1130 30, 15, 15, 34, 36, 40, 36, 40, 35, 35, 37, 37, 39, 39, 38, 38},
1133 { 1, -1, 0, 2, -2, 0, 3, -3, 1, -1, 4, -4, 5, -5, 1, -1,
1134 6, -6, 2, -2, 7, -7, 1, -1, 8, -8, 9, -9, 3, -3, 1, -1,
1135 10, -10, 2, -2, 11, -11, 1, -1, 12, 4, -12, -4, 1, -1, 13, -13,
1136 1, -1, 14, -14, 2, 5, 15, -2, -5, -15, -3, 3, 16, -16, 17, 1,
1137 -1, -17, 6, 18, -6, -18, 2, -2, 19, -19, 1, -1, 20, -20, 4, -4,
1138 7, -7, 21, -21, 1, -1, 2, 3, -3, 22, -2, -22, 8, 23, -8, 1,
1139 2, -23, -1, 2, -2, -2, 24, 1, -24, -1, 25, 5, -5, 1, -25, -1,
1140 9, -9, 26, 1, -26, 3, 1, -1, 27, -3, -1, -27, 1, 3, -1, -3,
1141 28, -4, 4, 10, -10, -28, 1, -1, 1, -1, 29, 6, -29, -6, 30, -4,
1142 3, 3, -3, -30, 1, 4, -1, 31, -3, 1, 11, -11, -1, -31, 32, -1,
1143 -1, 2, -2, 1, 1, -32, 1, 4, -1, -4, 33, -1, 1, 1, -1, 5,
1144 5, -5, -33, -1, -12, 12, -5, -7, 1, 1, 7, 34, 4, -4, -1, 4,
1145 -34, -4, 35, 36, -2, -35, -2, -36, 2, 13, 2, -1, 1, -13, 1, -1,
1146 37, 1, -5, 6, 5, -1, 38, -6, -8, 5, 8, -1, 1, 1, -37, -1,
1147 5, 39, -5, -5, 6, -6, -38, -39, -14, 40, 14, 2, 1, 1, -2, -40,
1148 -1, -2, 2, -1, -1, -1, 1, 1, 1, -1, 1, -1, 1, -1, 1, -1}
1154 {0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 8, 6, 8, 7,
1155 7, 9, 9, 10, 10, 11, 11, 1, 12, 1, 12, 13, 13, 16, 14, 16,
1156 14, 15, 15, 17, 17, 18, 0, 18, 19, 20, 21, 19, 22, 21, 20, 22,
1157 25, 24, 2, 25, 24, 23, 23, 2, 26, 28, 26, 28, 29, 27, 29, 27,
1158 33, 33, 1, 32, 1, 3, 32, 30, 36, 3, 36, 30, 31, 31, 35, 34,
1159 37, 41, 34, 35, 37, 4, 41, 4, 49, 8, 8, 49, 40, 38, 5, 38,
1160 40, 39, 5, 39, 42, 43, 42, 7, 57, 6, 43, 44, 6, 50, 7, 44,
1161 57, 48, 50, 48, 45, 45, 46, 47, 51, 46, 47, 58, 1, 51, 58, 1,
1162 52, 59, 53, 9, 52, 55, 55, 59, 53, 56, 54, 56, 54, 9, 64, 64,
1163 60, 63, 60, 63, 61, 62, 61, 62, 2, 10, 2, 10, 11, 1, 11, 13,
1164 12, 1, 12, 13, 16, 16, 8, 8, 14, 3, 3, 15, 14, 15, 4, 4,
1165 1, 17, 17, 5, 1, 7, 7, 5, 6, 1, 2, 2, 6, 22, 1, 25,
1166 21, 22, 8, 24, 1, 21, 25, 24, 8, 18, 18, 23, 9, 20, 23, 33,
1167 29, 33, 20, 1, 19, 1, 29, 36, 9, 36, 19, 41, 28, 57, 32, 3,
1168 28, 3, 1, 27, 49, 49, 1, 32, 26, 26, 2, 4, 4, 7, 57, 41,
1169 2, 7, 10, 5, 37, 16, 10, 27, 8, 8, 13, 16, 37, 13, 1, 5},
1172 {0, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, 1, -1, -1, 1,
1173 -1, 1, -1, 1, -1, 1, -1, 2, 1, -2, -1, 1, -1, 1, 1, -1,
1174 -1, 1, -1, 1, -1, 1, 0, -1, 1, 1, 1, -1, 1, -1, -1, -1,
1175 1, 1, 2, -1, -1, 1, -1, -2, 1, 1, -1, -1, 1, 1, -1, -1,
1176 1, -1, 3, 1, -3, 2, -1, 1, 1, -2, -1, -1, -1, 1, 1, 1,
1177 1, 1, -1, -1, -1, 2, -1, -2, 1, 2, -2, -1, 1, 1, 2, -1,
1178 -1, 1, -2, -1, 1, 1, -1, 2, 1, 2, -1, 1, -2, -1, -2, -1,
1179 -1, 1, 1, -1, 1, -1, 1, 1, 1, -1, -1, 1, 4, -1, -1, -4,
1180 1, 1, 1, 2, -1, -1, 1, -1, -1, 1, -1, -1, 1, -2, 1, -1,
1181 1, 1, -1, -1, 1, 1, -1, -1, 3, 2, -3, -2, 2, 5, -2, 2,
1182 2, -5, -2, -2, -2, 2, -3, 3, 2, 3, -3, 2, -2, -2, 3, -3,
1183 6, 2, -2, 3, -6, 3, -3, -3, 3, 7, -4, 4, -3, 2, -7, 2,
1184 2, -2, -4, 2, 8, -2, -2, -2, 4, 2, -2, 2, 3, 2, -2, -2,
1185 2, 2, -2, -8, -2, 9, -2, 2, -3, -2, 2, -2, 2, 2, 2, 4,
1186 -2, -4, 10, 2, 2, -2, -9, -2, 2, -2, 5, 4, -4, 4, -2, 2,
1187 -5, -4, -3, 4, 2, -3, 3, -2, -5, 5, 3, 3, -2, -3, -10, -4}
1193 {1, 1, 0, 2, 2, 1, 1, 3, 3, 4, 4, 0, 1, 1, 5, 5,
1194 2, 2, 6, 6, 7, 7, 1, 8, 1, 8, 3, 3, 9, 9, 1, 2,
1195 2, 1, 4, 10, 4, 10, 11, 11, 1, 5, 12, 12, 1, 5, 13, 13,
1196 3, 3, 6, 6, 2, 2, 14, 14, 16, 16, 15, 7, 15, 8, 8, 7,
1197 1, 1, 17, 17, 4, 4, 1, 1, 18, 18, 2, 2, 5, 5, 25, 3,
1198 9, 3, 25, 9, 19, 24, 19, 24, 1, 21, 20, 1, 21, 22, 20, 22,
1199 23, 23, 8, 6, 33, 6, 8, 33, 7, 7, 26, 26, 1, 32, 1, 32,
1200 28, 4, 28, 10, 29, 27, 27, 10, 41, 4, 29, 2, 2, 41, 36, 31,
1201 49, 31, 34, 30, 34, 36, 30, 35, 1, 49, 11, 5, 35, 11, 1, 3,
1202 3, 5, 37, 37, 8, 40, 8, 40, 12, 12, 42, 42, 1, 38, 16, 57,
1203 1, 6, 16, 39, 38, 6, 7, 7, 13, 13, 39, 43, 2, 43, 57, 2,
1204 50, 9, 44, 9, 50, 4, 15, 48, 44, 4, 1, 15, 48, 14, 14, 1,
1205 45, 45, 8, 3, 5, 8, 51, 47, 3, 46, 46, 47, 5, 51, 1, 17,
1206 17, 58, 1, 58, 2, 52, 52, 2, 53, 7, 59, 6, 6, 56, 53, 55,
1207 7, 55, 1, 54, 59, 56, 54, 10, 1, 10, 4, 60, 1, 60, 8, 4,
1208 8, 64, 64, 61, 1, 63, 3, 63, 62, 61, 5, 11, 5, 3, 11, 62},
1211 { 1, -1, 0, 1, -1, 2, -2, 1, -1, 1, -1, 0, 3, -3, 1, -1,
1212 2, -2, 1, -1, 1, -1, 4, 1, -4, -1, 2, -2, 1, -1, 5, 3,
1213 -3, -5, 2, 1, -2, -1, 1, -1, 6, 2, 1, -1, -6, -2, 1, -1,
1214 3, -3, 2, -2, 4, -4, 1, -1, 1, -1, 1, 2, -1, 2, -2, -2,
1215 7, -7, 1, -1, 3, -3, 8, -8, 1, -1, 5, -5, 3, -3, 1, 4,
1216 2, -4, -1, -2, 1, 1, -1, -1, 9, 1, 1, -9, -1, 1, -1, -1,
1217 1, -1, 3, -3, 1, 3, -3, -1, 3, -3, 1, -1, 10, 1, -10, -1,
1218 1, 4, -1, 2, 1, -1, 1, -2, 1, -4, -1, 6, -6, -1, 1, 1,
1219 1, -1, 1, 1, -1, -1, -1, 1, 11, -1, -2, 4, -1, 2, -11, 5,
1220 -5, -4, -1, 1, 4, 1, -4, -1, -2, 2, 1, -1, 12, 1, -2, 1,
1221 -12, 4, 2, 1, -1, -4, 4, -4, 2, -2, -1, 1, 7, -1, -1, -7,
1222 -1, -3, 1, 3, 1, 5, 2, 1, -1, -5, 13, -2, -1, 2, -2, -13,
1223 1, -1, 5, 6, 5, -5, 1, 1, -6, 1, -1, -1, -5, -1, 14, 2,
1224 -2, 1, -14, -1, 8, 1, -1, -8, 1, 5, 1, 5, -5, 1, -1, 1,
1225 -5, -1, 15, 1, -1, -1, -1, 3, -15, -3, 6, 1, 16, -1, 6, -6,
1226 -6, 1, -1, 1, -16, 1, 7, -1, 1, -1, -6, -3, 6, -7, 3, -1}
1232 {0, 1, 1, 2, 2, 3, 3, 4, 4, 1, 1, 5, 5, 6, 6, 7,
1233 7, 8, 8, 9, 9, 2, 2, 10, 10, 1, 1, 11, 11, 12, 12, 3,
1234 3, 13, 13, 0, 14, 14, 16, 15, 16, 15, 4, 4, 17, 1, 17, 1,
1235 5, 5, 18, 18, 2, 2, 6, 6, 8, 19, 7, 8, 7, 19, 20, 20,
1236 21, 21, 22, 24, 22, 24, 23, 23, 1, 1, 25, 25, 3, 3, 26, 26,
1237 9, 9, 27, 27, 28, 28, 33, 29, 4, 33, 29, 1, 4, 1, 32, 32,
1238 2, 2, 31, 10, 30, 10, 30, 31, 34, 34, 5, 5, 36, 36, 35, 41,
1239 35, 11, 41, 11, 37, 1, 8, 8, 37, 6, 1, 6, 40, 7, 7, 40,
1240 12, 38, 12, 39, 39, 38, 49, 13, 49, 13, 3, 42, 3, 42, 16, 16,
1241 43, 43, 14, 14, 1, 1, 44, 15, 44, 15, 2, 2, 57, 48, 50, 48,
1242 57, 50, 4, 45, 45, 4, 46, 47, 47, 46, 1, 51, 1, 17, 17, 51,
1243 8, 9, 9, 5, 58, 8, 58, 5, 52, 52, 55, 56, 53, 56, 55, 59,
1244 59, 53, 54, 1, 6, 54, 7, 7, 6, 1, 2, 3, 2, 3, 64, 60,
1245 60, 10, 10, 64, 61, 62, 61, 63, 1, 63, 62, 1, 18, 24, 18, 4,
1246 25, 4, 8, 21, 21, 1, 24, 22, 25, 22, 8, 11, 19, 11, 23, 1,
1247 20, 23, 19, 20, 5, 12, 5, 1, 16, 2, 12, 13, 2, 13, 1, 16},
1250 { 0, 1, -1, 1, -1, 1, -1, 1, -1, 2, -2, 1, -1, 1, -1, 1,
1251 -1, 1, -1, 1, -1, 2, -2, 1, -1, 3, -3, 1, -1, 1, -1, 2,
1252 -2, 1, -1, 0, 1, -1, 1, 1, -1, -1, 2, -2, 1, 4, -1, -4,
1253 2, -2, 1, -1, -3, 3, 2, -2, 2, 1, 2, -2, -2, -1, 1, -1,
1254 1, -1, 1, 1, -1, -1, 1, -1, 5, -5, 1, -1, 3, -3, 1, -1,
1255 2, -2, 1, -1, 1, -1, 1, 1, 3, -1, -1, 6, -3, -6, -1, 1,
1256 4, -4, 1, 2, 1, -2, -1, -1, 1, -1, 3, -3, 1, -1, 1, 1,
1257 -1, 2, -1, -2, 1, 7, -3, 3, -1, 3, -7, -3, 1, -3, 3, -1,
1258 2, 1, -2, 1, -1, -1, 1, 2, -1, -2, -4, -1, 4, 1, 2, -2,
1259 1, -1, -2, 2, 8, -8, -1, 2, 1, -2, -5, 5, 1, -1, -1, 1,
1260 -1, 1, 4, -1, 1, -4, -1, -1, 1, 1, 9, 1, -9, 2, -2, -1,
1261 -4, 3, -3, -4, -1, 4, 1, 4, 1, -1, 1, -1, 1, 1, -1, 1,
1262 -1, -1, -1, 10, 4, 1, 4, -4, -4, -10, 6, 5, -6, -5, 1, -1,
1263 1, 3, -3, -1, 1, -1, -1, -1, 11, 1, 1, -11, -2, -2, 2, 5,
1264 -2, -5, -5, 2, -2, 12, 2, -2, 2, 2, 5, -3, -2, 3, -2, -12,
1265 -2, 2, 2, 2, -5, 3, 5, 13, -3, 7, -3, -3, -7, 3, -13, 3}
1271 {0, 1, 1, 1, 2, 2, 1, 3, 3, 1, 1, 1, 4, 4, 1, 5,
1272 2, 1, 5, 2, 1, 1, 6, 6, 1, 1, 1, 1, 1, 7, 3, 1,
1273 2, 3, 0, 1, 2, 7, 1, 1, 1, 8, 1, 1, 8, 1, 1, 1,
1274 9, 1, 9, 1, 2, 1, 1, 2, 1, 1, 10, 4, 1, 10, 1, 4,
1275 1, 1, 1, 1, 1, 3, 1, 1, 1, 3, 2, 1, 5, 1, 1, 1,
1276 2, 5, 1, 11, 1, 11, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1277 2, 1, 6, 1, 6, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 12,
1278 3, 1, 12, 1, 1, 1, 2, 1, 1, 3, 1, 1, 1, 1, 1, 1,
1279 4, 1, 1, 1, 2, 1, 1, 4, 1, 1, 1, 1, 1, 1, 2, 1,
1280 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 2, 1, 1, 5,
1281 1, 1, 1, 1, 1, 7, 1, 7, 1, 1, 2, 3, 1, 1, 1, 1,
1282 5, 1, 1, 1, 1, 1, 1, 2, 13, 1, 1, 1, 1, 1, 1, 1,
1283 1, 1, 1, 1, 1, 1, 1, 1, 13, 2, 1, 1, 4, 1, 1, 1,
1284 3, 1, 6, 1, 1, 1, 14, 1, 1, 1, 1, 1, 14, 6, 1, 1,
1285 1, 1, 15, 2, 4, 1, 2, 3, 15, 1, 1, 1, 8, 1, 1, 8,
1286 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1},
1289 { 0, 1, -1, 2, 1, -1, -2, 1, -1, 3, -3, 4, 1, -1, -4, 1,
1290 2, 5, -1, -2, -5, 6, 1, -1, -6, 7, -7, 8, -8, 1, 2, 9,
1291 3, -2, 0, -9, -3, -1, 10, -10, 11, 1, -11, 12, -1, -12, 13, -13,
1292 1, 14, -1, -14, 4, 15, -15, -4, 16, -16, 1, 2, 17, -1, -17, -2,
1293 18, -18, 19, -19, 20, 3, -20, 21, -21, -3, 5, 22, 2, -22, -23, 23,
1294 -5, -2, 24, 1, -24, -1, 25, -25, 26, -26, -27, 27, 28, 29, -28, -29,
1295 6, 30, 2, -31, -2, -30, 31, -6, -32, 32, 33, -33, 34, -35, -34, 1,
1296 4, -36, -1, 35, 37, 36, 7, -37, 38, -4, -38, 39, 41, 40, -40, -39,
1297 3, 42, -43, -41, -7, -42, 43, -3, 44, -44, 45, -45, 46, 47, 8, -47,
1298 -48, -46, 50, -50, 48, 49, 51, -49, 52, -52, 5, -51, -8, -53, 53, 3,
1299 -56, 56, 55, 54, -54, 2, 60, -2, -55, 58, 9, -5, 59, 57, -57, -63,
1300 -3, -58, -60, -61, 61, -59, -62, -9, 1, 64, 62, 69, -64, 63, 65, -67,
1301 -68, 66, -65, 68, -66, -69, 67, -70, -1, 10, 71, -71, 4, 73, 72, 70,
1302 6, -76, -3, 74, -78, -74, 1, 78, 80, -72, -75, 76, -1, 3, -73, 79,
1303 75, 77, 1, 11, -4, -79, -10, -6, -1, -77, -83, -80, 2, 81, -84, -2,
1304 83, -81, 82, -82, 84, -87, -86, 85, -11, -85, 86, -89, 87, -88, 88, 89}
1310 {1, 1, 0, 2, 1, 2, 1, 3, 3, 1, 1, 4, 4, 2, 2, 1,
1311 1, 5, 5, 6, 1, 6, 1, 7, 7, 3, 3, 2, 8, 2, 8, 1,
1312 1, 0, 9, 9, 1, 1, 10, 4, 10, 4, 11, 11, 2, 1, 2, 1,
1313 12, 12, 3, 3, 1, 1, 13, 5, 5, 13, 14, 1, 1, 14, 2, 2,
1314 6, 6, 15, 1, 1, 15, 16, 4, 7, 16, 4, 7, 1, 1, 3, 3,
1315 8, 8, 2, 2, 1, 1, 17, 17, 1, 1, 18, 18, 5, 5, 2, 2,
1316 1, 1, 9, 19, 9, 19, 20, 3, 3, 20, 1, 10, 21, 1, 10, 4,
1317 4, 21, 22, 6, 6, 22, 1, 1, 23, 24, 2, 2, 23, 24, 11, 1,
1318 1, 11, 7, 25, 7, 1, 1, 25, 8, 8, 3, 26, 3, 1, 12, 2,
1319 2, 26, 1, 12, 5, 5, 27, 4, 1, 4, 1, 27, 28, 1, 28, 13,
1320 1, 13, 2, 29, 2, 1, 32, 6, 1, 30, 14, 29, 14, 6, 3, 31,
1321 3, 1, 30, 1, 32, 31, 33, 9, 33, 1, 1, 7, 9, 7, 2, 2,
1322 1, 1, 4, 36, 34, 4, 5, 10, 10, 5, 34, 1, 1, 35, 8, 8,
1323 36, 3, 35, 1, 15, 3, 2, 1, 16, 15, 16, 2, 37, 1, 37, 1,
1324 1, 1, 6, 6, 38, 1, 38, 11, 1, 39, 39, 40, 11, 2, 41, 4,
1325 40, 1, 2, 4, 1, 1, 1, 41, 3, 1, 3, 1, 5, 7, 5, 7},
1328 { 1, -1, 0, 1, 2, -1, -2, 1, -1, 3, -3, 1, -1, 2, -2, 4,
1329 -4, 1, -1, 1, 5, -1, -5, 1, -1, 2, -2, 3, 1, -3, -1, 6,
1330 -6, 0, 1, -1, 7, -7, 1, 2, -1, -2, 1, -1, 4, 8, -4, -8,
1331 1, -1, 3, -3, 9, -9, 1, 2, -2, -1, 1, 10, -10, -1, 5, -5,
1332 2, -2, 1, 11, -11, -1, 1, 3, 2, -1, -3, -2, 12, -12, 4, -4,
1333 2, -2, -6, 6, 13, -13, 1, -1, 14, -14, 1, -1, 3, -3, 7, -7,
1334 15, -15, 2, 1, -2, -1, 1, 5, -5, -1, -16, 2, 1, 16, -2, 4,
1335 -4, -1, 1, 3, -3, -1, 17, -17, 1, 1, -8, 8, -1, -1, 2, 18,
1336 -18, -2, 3, 1, -3, 19, -19, -1, 3, -3, 6, 1, -6, 20, 2, 9,
1337 -9, -1, -20, -2, 4, -4, 1, -5, 21, 5, -21, -1, 1, -22, -1, 2,
1338 22, -2, 10, 1, -10, 23, 1, 4, -23, 1, 2, -1, -2, -4, -7, 1,
1339 7, -24, -1, 24, -1, -1, 1, 3, -1, -25, 25, 4, -3, -4, 11, -11,
1340 26, -26, 6, 1, 1, -6, -5, -3, 3, 5, -1, -27, 27, 1, 4, -4,
1341 -1, -8, -1, 28, 2, 8, -12, -28, -2, -2, 2, 12, -1, 29, 1, -29,
1342 30, -30, 5, -5, 1, -31, -1, 3, 31, -1, 1, 1, -3, -13, 1, -7,
1343 -1, -32, 13, 7, 32, 33, -33, -1, -9, -34, 9, 34, -6, 5, 6, -5}
1349 {1, 1, 0, 1, 1, 2, 2, 1, 1, 3, 3, 1, 1, 0, 2, 2,
1350 4, 1, 4, 1, 1, 1, 5, 5, 1, 1, 6, 6, 2, 2, 1, 1,
1351 3, 3, 7, 7, 1, 1, 8, 8, 1, 1, 2, 2, 1, 9, 1, 9,
1352 4, 4, 10, 1, 1, 10, 1, 1, 11, 11, 3, 3, 1, 2, 1, 2,
1353 1, 1, 12, 12, 5, 5, 1, 1, 13, 1, 1, 13, 2, 2, 1, 1,
1354 6, 6, 1, 1, 4, 14, 4, 14, 3, 1, 3, 1, 1, 1, 15, 7,
1355 15, 2, 2, 7, 1, 1, 1, 8, 1, 8, 16, 16, 1, 1, 1, 1,
1356 2, 1, 1, 2, 1, 1, 3, 5, 5, 3, 4, 1, 1, 4, 1, 1,
1357 17, 17, 9, 1, 1, 9, 2, 2, 1, 1, 10, 10, 1, 6, 1, 1,
1358 6, 18, 1, 1, 18, 1, 1, 1, 2, 2, 3, 1, 3, 1, 1, 1,
1359 4, 1, 19, 1, 19, 7, 1, 1, 20, 1, 4, 20, 1, 7, 11, 2,
1360 1, 11, 21, 2, 8, 5, 1, 8, 1, 5, 21, 1, 1, 1, 22, 1,
1361 1, 22, 1, 1, 3, 3, 1, 23, 2, 12, 24, 1, 1, 2, 1, 1,
1362 12, 23, 1, 1, 24, 1, 1, 1, 4, 1, 1, 1, 2, 1, 6, 6,
1363 4, 2, 1, 1, 1, 1, 1, 1, 1, 14, 13, 3, 1, 25, 9, 25,
1364 14, 1, 9, 3, 13, 1, 1, 1, 1, 1, 10, 1, 1, 2, 10, 2},
1367 {-20, -1, 0, 2, -2, 1, -1, 3, -3, 1, -1, 4, -4, 0, 2, -2,
1368 1, 5, -1, -5, 6, -6, 1, -1, 7, -7, 1, -1, 3, -3, 8, -8,
1369 2, -2, 1, -1, 9, -9, 1, -1, 10, -10, 4, -4, 11, 1, -11, -1,
1370 2, -2, 1, 12, -12, -1, 13, -13, 1, -1, 3, -3, 14, 5, -14, -5,
1371 -15, 15, -1, 1, 2, -2, 16, -16, 1, 17, -17, -1, 6, -6, 18, -18,
1372 2, -2, -19, 19, -3, 1, 3, -1, 4, 20, -4, 1, -21, 21, 1, 2,
1373 -1, -7, 7, -2, 22, -22, 23, 2, -23, -2, 1, -1, -24, 24, -25, 25,
1374 -8, -26, 26, 8, -27, 27, 5, 3, -3, -5, -4, 28, -28, 4, 29, -29,
1375 1, -1, -2, -30, 30, 2, 9, -9, -31, 31, 2, -2, -32, 3, 32, -33,
1376 -3, 1, 33, -34, -1, 34, -35, 35, -10, 10, -6, 36, 6, -36, 37, -37,
1377 -5, 38, 1, -38, -1, 3, 39, -39, -1, 40, 5, 1, -40, -3, 2, -11,
1378 -41, -2, 1, 11, -3, -4, 41, 3, 42, 4, -1, -43, -42, 43, 1, -44,
1379 45, -1, 44, -45, -7, 7, -46, 1, -12, 2, 1, -47, 46, 12, 47, 48,
1380 -2, -1, -48, 49, -1, -50, -49, 50, -6, -51, 51, 52, -13, 53, -4, 4,
1381 6, 13, -53, -52, -54, 55, 54, -55, -56, -2, 2, -8, 56, 1, -3, -1,
1382 2, 58, 3, 8, -2, 57, -58, -60, -59, -57, -3, 60, 59, -14, 3, 14}
1388 {1, 1, 0, 2, 2, 1, 1, 3, 3, 4, 4, 5, 5, 1, 1, 6,
1389 6, 2, 2, 7, 7, 8, 8, 1, 1, 3, 3, 9, 9, 10, 10, 1,
1390 1, 2, 2, 4, 4, 11, 0, 11, 12, 12, 13, 13, 1, 1, 5, 5,
1391 14, 14, 15, 16, 15, 16, 3, 3, 1, 6, 1, 6, 2, 2, 7, 7,
1392 8, 8, 17, 17, 1, 1, 4, 4, 18, 18, 2, 2, 1, 19, 1, 20,
1393 19, 20, 21, 21, 3, 3, 22, 22, 5, 5, 24, 1, 1, 23, 9, 23,
1394 24, 9, 2, 2, 10, 1, 1, 10, 6, 6, 25, 4, 4, 25, 7, 7,
1395 26, 8, 1, 8, 3, 1, 26, 3, 11, 11, 27, 27, 2, 28, 1, 2,
1396 28, 1, 12, 12, 5, 5, 29, 13, 13, 29, 32, 1, 1, 33, 31, 30,
1397 32, 4, 30, 33, 4, 31, 3, 14, 1, 1, 3, 34, 34, 2, 2, 14,
1398 6, 6, 35, 36, 35, 36, 1, 15, 1, 16, 16, 15, 7, 9, 7, 9,
1399 37, 8, 8, 37, 1, 1, 39, 2, 38, 39, 2, 40, 5, 38, 40, 5,
1400 3, 3, 4, 4, 10, 10, 1, 1, 1, 1, 41, 2, 41, 2, 6, 6,
1401 1, 1, 11, 42, 11, 43, 3, 42, 3, 17, 4, 43, 1, 17, 7, 1,
1402 8, 44, 4, 7, 44, 5, 8, 2, 5, 1, 2, 48, 45, 1, 12, 45,
1403 12, 48, 13, 13, 1, 9, 9, 46, 1, 46, 47, 47, 49, 18, 18, 49},
1406 { 1, -1, 0, 1, -1, 2, -2, 1, -1, 1, -1, 1, -1, 3, -3, 1,
1407 -1, -2, 2, 1, -1, 1, -1, 4, -4, -2, 2, 1, -1, 1, -1, 5,
1408 -5, -3, 3, 2, -2, 1, 0, -1, 1, -1, 1, -1, 6, -6, 2, -2,
1409 1, -1, 1, 1, -1, -1, -3, 3, 7, 2, -7, -2, -4, 4, 2, -2,
1410 2, -2, 1, -1, 8, -8, 3, -3, 1, -1, -5, 5, 9, 1, -9, 1,
1411 -1, -1, 1, -1, -4, 4, 1, -1, 3, -3, 1, -10, 10, 1, 2, -1,
1412 -1, -2, 6, -6, 2, 11, -11, -2, 3, -3, 1, -4, 4, -1, 3, -3,
1413 1, 3, 12, -3, -5, -12, -1, 5, 2, -2, 1, -1, -7, 1, 13, 7,
1414 -1, -13, 2, -2, 4, -4, 1, 2, -2, -1, 1, 14, -14, 1, 1, 1,
1415 -1, -5, -1, -1, 5, -1, -6, 2, -15, 15, 6, 1, -1, -8, 8, -2,
1416 -4, 4, 1, 1, -1, -1, 16, 2, -16, -2, 2, -2, 4, 3, -4, -3,
1417 -1, -4, 4, 1, -17, 17, -1, -9, 1, 1, 9, 1, -5, -1, -1, 5,
1418 -7, 7, 6, -6, 3, -3, 18, -18, 19, -19, 1, -10, -1, 10, -5, 5,
1419 20, -20, -3, 1, 3, 1, 8, -1, -8, 2, 7, -1, -21, -2, 5, 21,
1420 5, -1, -7, -5, 1, -6, -5, -11, 6, 22, 11, 1, 1, -22, -3, -1,
1421 3, -1, 3, -3, -23, 4, -4, 1, 23, -1, 1, -1, 1, -2, 2, -1}
1427 {1, 1, 1, 1, 0, 2, 2, 1, 1, 3, 3, 0, 1, 1, 2, 2,
1428 4, 4, 1, 1, 5, 5, 1, 1, 2, 2, 3, 3, 6, 6, 1, 1,
1429 7, 7, 8, 1, 8, 2, 2, 1, 4, 4, 1, 3, 1, 3, 9, 9,
1430 2, 2, 1, 5, 1, 5, 10, 10, 1, 1, 11, 11, 3, 6, 3, 4,
1431 4, 6, 2, 2, 1, 12, 1, 12, 7, 13, 7, 13, 1, 1, 8, 8,
1432 2, 2, 14, 14, 16, 15, 16, 5, 5, 1, 3, 15, 1, 3, 4, 4,
1433 1, 1, 17, 17, 2, 2, 6, 6, 1, 18, 1, 18, 22, 21, 22, 21,
1434 25, 24, 25, 19, 9, 20, 9, 23, 19, 24, 20, 3, 23, 7, 3, 1,
1435 1, 7, 28, 26, 29, 5, 28, 26, 5, 8, 29, 4, 8, 27, 2, 2,
1436 4, 27, 1, 1, 10, 36, 10, 33, 33, 36, 30, 1, 32, 32, 1, 30,
1437 6, 31, 31, 35, 3, 6, 11, 11, 3, 2, 35, 2, 34, 1, 34, 1,
1438 37, 37, 12, 7, 12, 5, 41, 5, 4, 7, 1, 8, 13, 4, 1, 41,
1439 13, 38, 8, 38, 9, 1, 40, 40, 9, 1, 39, 2, 2, 49, 39, 42,
1440 3, 3, 14, 16, 49, 14, 16, 42, 43, 43, 6, 6, 15, 1, 1, 15,
1441 44, 44, 1, 1, 50, 48, 4, 5, 4, 7, 5, 2, 10, 10, 48, 7,
1442 50, 45, 2, 1, 45, 8, 8, 1, 46, 46, 3, 47, 47, 3, 1, 1},
1445 { 1, -1, 2, -2, 0, 1, -1, 3, -3, 1, -1, 0, 4, -4, 2, -2,
1446 1, -1, 5, -5, 1, -1, 6, -6, 3, -3, 2, -2, 1, -1, 7, -7,
1447 1, -1, 1, 8, -1, 4, -4, -8, 2, -2, 9, 3, -9, -3, 1, -1,
1448 5, -5, 10, 2, -10, -2, 1, -1, 11, -11, 1, -1, -4, 2, 4, 3,
1449 -3, -2, 6, -6, 12, 1, -12, -1, 2, 1, -2, -1, 13, -13, 2, -2,
1450 7, -7, 1, -1, 1, 1, -1, 3, -3, 14, 5, -1, -14, -5, 4, -4,
1451 15, -15, 1, -1, 8, -8, -3, 3, 16, 1, -16, -1, 1, 1, -1, -1,
1452 1, 1, -1, 1, 2, 1, -2, 1, -1, -1, -1, 6, -1, 3, -6, 17,
1453 -17, -3, 1, 1, 1, 4, -1, -1, -4, 3, -1, 5, -3, -1, -9, 9,
1454 -5, 1, 18, -18, 2, 1, -2, 1, -1, -1, 1, 19, -1, 1, -19, -1,
1455 4, 1, -1, 1, 7, -4, -2, 2, -7, 10, -1, -10, 1, 20, -1, -20,
1456 1, -1, 2, 4, -2, 5, 1, -5, 6, -4, 21, 4, 2, -6, -21, -1,
1457 -2, 1, -4, -1, -3, 22, -1, 1, 3, -22, -1, 11, -11, 1, 1, 1,
1458 8, -8, 2, 2, -1, -2, -2, -1, 1, -1, -5, 5, 2, 23, -23, -2,
1459 1, -1, 24, -24, -1, -1, 7, 6, -7, 5, -6, 12, -3, 3, 1, -5,
1460 1, 1, -12, 25, -1, -5, 5, -25, -1, 1, 9, 1, -1, -9, 26, -26}