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"
31 #include "libavutil/timer.h"
36 #include "ivi_common.h"
40 * These are 2x8 predefined Huffman codebooks for coding macroblock/block
41 * signals. They are specified using "huffman descriptors" in order to
42 * avoid huge static tables. The decoding tables will be generated at
43 * startup from these descriptors.
45 /** static macroblock huffman tables */
46 static const IVIHuffDesc ivi_mb_huff_desc[8] = {
47 {8, {0, 4, 5, 4, 4, 4, 6, 6}},
48 {12, {0, 2, 2, 3, 3, 3, 3, 5, 3, 2, 2, 2}},
49 {12, {0, 2, 3, 4, 3, 3, 3, 3, 4, 3, 2, 2}},
50 {12, {0, 3, 4, 4, 3, 3, 3, 3, 3, 2, 2, 2}},
51 {13, {0, 4, 4, 3, 3, 3, 3, 2, 3, 3, 2, 1, 1}},
52 {9, {0, 4, 4, 4, 4, 3, 3, 3, 2}},
53 {10, {0, 4, 4, 4, 4, 3, 3, 2, 2, 2}},
54 {12, {0, 4, 4, 4, 3, 3, 2, 3, 2, 2, 2, 2}}
57 /** static block huffman tables */
58 static const IVIHuffDesc ivi_blk_huff_desc[8] = {
59 {10, {1, 2, 3, 4, 4, 7, 5, 5, 4, 1}},
60 {11, {2, 3, 4, 4, 4, 7, 5, 4, 3, 3, 2}},
61 {12, {2, 4, 5, 5, 5, 5, 6, 4, 4, 3, 1, 1}},
62 {13, {3, 3, 4, 4, 5, 6, 6, 4, 4, 3, 2, 1, 1}},
63 {11, {3, 4, 4, 5, 5, 5, 6, 5, 4, 2, 2}},
64 {13, {3, 4, 5, 5, 5, 5, 6, 4, 3, 3, 2, 1, 1}},
65 {13, {3, 4, 5, 5, 5, 6, 5, 4, 3, 3, 2, 1, 1}},
66 {9, {3, 4, 4, 5, 5, 5, 6, 5, 5}}
69 static VLC ivi_mb_vlc_tabs [8]; ///< static macroblock Huffman tables
70 static VLC ivi_blk_vlc_tabs[8]; ///< static block Huffman tables
72 typedef void (*ivi_mc_func) (int16_t *buf, const int16_t *ref_buf,
73 uint32_t pitch, int mc_type);
75 static int ivi_mc(IVIBandDesc *band, ivi_mc_func mc,
76 int offs, int mv_x, int mv_y, int mc_type)
78 int ref_offs = offs + mv_y * band->pitch + mv_x;
79 int buf_size = band->pitch * band->aheight;
80 int min_size = band->pitch * (band->blk_size - 1) + band->blk_size;
81 int ref_size = (mc_type > 1) * band->pitch + (mc_type & 1);
83 if (offs < 0 || ref_offs < 0 || !band->ref_buf)
84 return AVERROR_INVALIDDATA;
85 if (buf_size - min_size < offs)
86 return AVERROR_INVALIDDATA;
87 if (buf_size - min_size - ref_size < ref_offs)
88 return AVERROR_INVALIDDATA;
90 mc(band->buf + offs, band->ref_buf + ref_offs, band->pitch, mc_type);
96 * Reverse "nbits" bits of the value "val" and return the result
97 * in the least significant bits.
99 static uint16_t inv_bits(uint16_t val, int nbits)
104 res = ff_reverse[val] >> (8 - nbits);
106 res = ((ff_reverse[val & 0xFF] << 8) +
107 (ff_reverse[val >> 8])) >> (16 - nbits);
113 * Generate a huffman codebook from the given descriptor
114 * and convert it into the Libav VLC table.
116 * @param[in] cb pointer to codebook descriptor
117 * @param[out] vlc where to place the generated VLC table
118 * @param[in] flag flag: 1 - for static or 0 for dynamic tables
119 * @return result code: 0 - OK, -1 = error (invalid codebook descriptor)
121 static int ivi_create_huff_from_desc(const IVIHuffDesc *cb, VLC *vlc, int flag)
123 int pos, i, j, codes_per_row, prefix, not_last_row;
124 uint16_t codewords[256]; /* FIXME: move this temporal storage out? */
127 pos = 0; /* current position = 0 */
129 for (i = 0; i < cb->num_rows; i++) {
130 codes_per_row = 1 << cb->xbits[i];
131 not_last_row = (i != cb->num_rows - 1);
132 prefix = ((1 << i) - 1) << (cb->xbits[i] + not_last_row);
134 for (j = 0; j < codes_per_row; j++) {
135 if (pos >= 256) /* Some Indeo5 codebooks can have more than 256 */
136 break; /* elements, but only 256 codes are allowed! */
138 bits[pos] = i + cb->xbits[i] + not_last_row;
139 if (bits[pos] > IVI_VLC_BITS)
140 return AVERROR_INVALIDDATA; /* invalid descriptor */
142 codewords[pos] = inv_bits((prefix | j), bits[pos]);
150 /* number of codewords = pos */
151 return init_vlc(vlc, IVI_VLC_BITS, pos, bits, 1, 1, codewords, 2, 2,
152 (flag ? INIT_VLC_USE_NEW_STATIC : 0) | INIT_VLC_LE);
155 av_cold void ff_ivi_init_static_vlc(void)
158 static VLC_TYPE table_data[8192 * 16][2];
159 static int initialized_vlcs = 0;
161 if (initialized_vlcs)
163 for (i = 0; i < 8; i++) {
164 ivi_mb_vlc_tabs[i].table = table_data + i * 2 * 8192;
165 ivi_mb_vlc_tabs[i].table_allocated = 8192;
166 ivi_create_huff_from_desc(&ivi_mb_huff_desc[i],
167 &ivi_mb_vlc_tabs[i], 1);
168 ivi_blk_vlc_tabs[i].table = table_data + (i * 2 + 1) * 8192;
169 ivi_blk_vlc_tabs[i].table_allocated = 8192;
170 ivi_create_huff_from_desc(&ivi_blk_huff_desc[i],
171 &ivi_blk_vlc_tabs[i], 1);
173 initialized_vlcs = 1;
177 * Copy huffman codebook descriptors.
179 * @param[out] dst ptr to the destination descriptor
180 * @param[in] src ptr to the source descriptor
182 static void ivi_huff_desc_copy(IVIHuffDesc *dst, const IVIHuffDesc *src)
184 dst->num_rows = src->num_rows;
185 memcpy(dst->xbits, src->xbits, src->num_rows);
189 * Compare two huffman codebook descriptors.
191 * @param[in] desc1 ptr to the 1st descriptor to compare
192 * @param[in] desc2 ptr to the 2nd descriptor to compare
193 * @return comparison result: 0 - equal, 1 - not equal
195 static int ivi_huff_desc_cmp(const IVIHuffDesc *desc1,
196 const IVIHuffDesc *desc2)
198 return desc1->num_rows != desc2->num_rows ||
199 memcmp(desc1->xbits, desc2->xbits, desc1->num_rows);
202 int ff_ivi_dec_huff_desc(GetBitContext *gb, int desc_coded, int which_tab,
203 IVIHuffTab *huff_tab, AVCodecContext *avctx)
206 IVIHuffDesc new_huff;
209 /* select default table */
210 huff_tab->tab = (which_tab) ? &ivi_blk_vlc_tabs[7]
211 : &ivi_mb_vlc_tabs [7];
215 huff_tab->tab_sel = get_bits(gb, 3);
216 if (huff_tab->tab_sel == 7) {
217 /* custom huffman table (explicitly encoded) */
218 new_huff.num_rows = get_bits(gb, 4);
219 if (!new_huff.num_rows) {
220 av_log(avctx, AV_LOG_ERROR, "Empty custom Huffman table!\n");
221 return AVERROR_INVALIDDATA;
224 for (i = 0; i < new_huff.num_rows; i++)
225 new_huff.xbits[i] = get_bits(gb, 4);
227 /* Have we got the same custom table? Rebuild if not. */
228 if (ivi_huff_desc_cmp(&new_huff, &huff_tab->cust_desc)) {
229 ivi_huff_desc_copy(&huff_tab->cust_desc, &new_huff);
231 if (huff_tab->cust_tab.table)
232 ff_free_vlc(&huff_tab->cust_tab);
233 result = ivi_create_huff_from_desc(&huff_tab->cust_desc,
234 &huff_tab->cust_tab, 0);
236 // reset faulty description
237 huff_tab->cust_desc.num_rows = 0;
238 av_log(avctx, AV_LOG_ERROR,
239 "Error while initializing custom vlc table!\n");
243 huff_tab->tab = &huff_tab->cust_tab;
245 /* select one of predefined tables */
246 huff_tab->tab = (which_tab) ? &ivi_blk_vlc_tabs[huff_tab->tab_sel]
247 : &ivi_mb_vlc_tabs [huff_tab->tab_sel];
254 * Free planes, bands and macroblocks buffers.
256 * @param[in] planes pointer to the array of the plane descriptors
258 static av_cold void ivi_free_buffers(IVIPlaneDesc *planes)
262 for (p = 0; p < 3; p++) {
263 for (b = 0; b < planes[p].num_bands; b++) {
264 av_freep(&planes[p].bands[b].bufs[0]);
265 av_freep(&planes[p].bands[b].bufs[1]);
266 av_freep(&planes[p].bands[b].bufs[2]);
268 if (planes[p].bands[b].blk_vlc.cust_tab.table)
269 ff_free_vlc(&planes[p].bands[b].blk_vlc.cust_tab);
270 for (t = 0; t < planes[p].bands[b].num_tiles; t++)
271 av_freep(&planes[p].bands[b].tiles[t].mbs);
272 av_freep(&planes[p].bands[b].tiles);
274 av_freep(&planes[p].bands);
275 planes[p].num_bands = 0;
279 av_cold int ff_ivi_init_planes(IVIPlaneDesc *planes, const IVIPicConfig *cfg)
282 uint32_t b_width, b_height, align_fac, width_aligned,
283 height_aligned, buf_size;
286 ivi_free_buffers(planes);
288 if (cfg->pic_width < 1 || cfg->pic_height < 1 ||
289 cfg->luma_bands < 1 || cfg->chroma_bands < 1)
290 return AVERROR_INVALIDDATA;
292 /* fill in the descriptor of the luminance plane */
293 planes[0].width = cfg->pic_width;
294 planes[0].height = cfg->pic_height;
295 planes[0].num_bands = cfg->luma_bands;
297 /* fill in the descriptors of the chrominance planes */
298 planes[1].width = planes[2].width = (cfg->pic_width + 3) >> 2;
299 planes[1].height = planes[2].height = (cfg->pic_height + 3) >> 2;
300 planes[1].num_bands = planes[2].num_bands = cfg->chroma_bands;
302 for (p = 0; p < 3; p++) {
303 planes[p].bands = av_mallocz(planes[p].num_bands * sizeof(IVIBandDesc));
304 if (!planes[p].bands)
305 return AVERROR(ENOMEM);
307 /* select band dimensions: if there is only one band then it
308 * has the full size, if there are several bands each of them
309 * has only half size */
310 b_width = planes[p].num_bands == 1 ? planes[p].width
311 : (planes[p].width + 1) >> 1;
312 b_height = planes[p].num_bands == 1 ? planes[p].height
313 : (planes[p].height + 1) >> 1;
315 /* luma band buffers will be aligned on 16x16 (max macroblock size) */
316 /* chroma band buffers will be aligned on 8x8 (max macroblock size) */
317 align_fac = p ? 8 : 16;
318 width_aligned = FFALIGN(b_width , align_fac);
319 height_aligned = FFALIGN(b_height, align_fac);
320 buf_size = width_aligned * height_aligned * sizeof(int16_t);
322 for (b = 0; b < planes[p].num_bands; b++) {
323 band = &planes[p].bands[b]; /* select appropriate plane/band */
326 band->width = b_width;
327 band->height = b_height;
328 band->pitch = width_aligned;
329 band->aheight = height_aligned;
330 band->bufs[0] = av_mallocz(buf_size);
331 band->bufs[1] = av_mallocz(buf_size);
332 if (!band->bufs[0] || !band->bufs[1])
333 return AVERROR(ENOMEM);
335 /* allocate the 3rd band buffer for scalability mode */
336 if (cfg->luma_bands > 1) {
337 band->bufs[2] = av_mallocz(buf_size);
339 return AVERROR(ENOMEM);
341 /* reset custom vlc */
342 planes[p].bands[0].blk_vlc.cust_desc.num_rows = 0;
349 static int ivi_init_tiles(IVIBandDesc *band, IVITile *ref_tile,
350 int p, int b, int t_height, int t_width)
353 IVITile *tile = band->tiles;
355 for (y = 0; y < band->height; y += t_height) {
356 for (x = 0; x < band->width; x += t_width) {
359 tile->mb_size = band->mb_size;
360 tile->width = FFMIN(band->width - x, t_width);
361 tile->height = FFMIN(band->height - y, t_height);
362 tile->is_empty = tile->data_size = 0;
363 /* calculate number of macroblocks */
364 tile->num_MBs = IVI_MBs_PER_TILE(tile->width, tile->height,
367 av_freep(&tile->mbs);
368 tile->mbs = av_malloc(tile->num_MBs * sizeof(IVIMbInfo));
370 return AVERROR(ENOMEM);
374 if (tile->num_MBs != ref_tile->num_MBs)
375 return AVERROR_INVALIDDATA;
376 tile->ref_mbs = ref_tile->mbs;
386 av_cold int ff_ivi_init_tiles(IVIPlaneDesc *planes,
387 int tile_width, int tile_height)
389 int p, b, x_tiles, y_tiles, t_width, t_height, ret;
392 for (p = 0; p < 3; p++) {
393 t_width = !p ? tile_width : (tile_width + 3) >> 2;
394 t_height = !p ? tile_height : (tile_height + 3) >> 2;
396 if (!p && planes[0].num_bands == 4) {
401 for (b = 0; b < planes[p].num_bands; b++) {
402 band = &planes[p].bands[b];
403 x_tiles = IVI_NUM_TILES(band->width, t_width);
404 y_tiles = IVI_NUM_TILES(band->height, t_height);
405 band->num_tiles = x_tiles * y_tiles;
407 av_freep(&band->tiles);
408 band->tiles = av_mallocz(band->num_tiles * sizeof(IVITile));
410 return AVERROR(ENOMEM);
412 /* use the first luma band as reference for motion vectors
414 ret = ivi_init_tiles(band, planes[0].bands[0].tiles,
415 p, b, t_height, t_width);
425 * Decode size of the tile data.
426 * The size is stored as a variable-length field having the following format:
427 * if (tile_data_size < 255) than this field is only one byte long
428 * if (tile_data_size >= 255) than this field four is byte long: 0xFF X1 X2 X3
429 * where X1-X3 is size of the tile data
431 * @param[in,out] gb the GetBit context
432 * @return size of the tile data in bytes
434 static int ivi_dec_tile_data_size(GetBitContext *gb)
440 len = get_bits(gb, 8);
442 len = get_bits_long(gb, 24);
445 /* align the bitstream reader on the byte boundary */
451 static int ivi_dc_transform(IVIBandDesc *band, int *prev_dc, int buf_offs,
454 int buf_size = band->pitch * band->aheight - buf_offs;
455 int min_size = (blk_size - 1) * band->pitch + blk_size;
457 if (!band->dc_transform)
461 if (min_size > buf_size)
462 return AVERROR_INVALIDDATA;
464 band->dc_transform(prev_dc, band->buf + buf_offs,
465 band->pitch, blk_size);
470 static int ivi_decode_coded_blocks(GetBitContext *gb, IVIBandDesc *band,
471 ivi_mc_func mc, int mv_x, int mv_y,
472 int *prev_dc, int is_intra, int mc_type,
473 uint32_t quant, int offs,
474 AVCodecContext *avctx)
476 const uint16_t *base_tab = is_intra ? band->intra_base : band->inter_base;
477 RVMapDesc *rvmap = band->rv_map;
478 uint8_t col_flags[8];
480 uint32_t sym = 0, lo, hi, q;
482 int blk_size = band->blk_size;
483 int num_coeffs = blk_size * blk_size;
484 int col_mask = blk_size - 1;
486 int min_size = band->pitch * (band->transform_size - 1) +
487 band->transform_size;
488 int buf_size = band->pitch * band->aheight - offs;
490 if (min_size > buf_size)
491 return AVERROR_INVALIDDATA;
494 av_log(avctx, AV_LOG_ERROR, "Scan pattern is not set.\n");
495 return AVERROR_INVALIDDATA;
498 /* zero transform vector */
499 memset(trvec, 0, num_coeffs * sizeof(trvec[0]));
500 /* zero column flags */
501 memset(col_flags, 0, sizeof(col_flags));
502 while (scan_pos <= num_coeffs) {
503 sym = get_vlc2(gb, band->blk_vlc.tab->table,
505 if (sym == rvmap->eob_sym)
506 break; /* End of block */
508 /* Escape - run/val explicitly coded using 3 vlc codes */
509 if (sym == rvmap->esc_sym) {
510 run = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1) + 1;
511 lo = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
512 hi = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
513 /* merge them and convert into signed val */
514 val = IVI_TOSIGNED((hi << 6) | lo);
517 av_log(avctx, AV_LOG_ERROR, "Invalid sym encountered: %d.\n", sym);
518 return AVERROR_INVALIDDATA;
520 run = rvmap->runtab[sym];
521 val = rvmap->valtab[sym];
524 /* de-zigzag and dequantize */
526 if (scan_pos >= num_coeffs || scan_pos < 0)
528 pos = band->scan[scan_pos];
531 av_dlog(avctx, "Val = 0 encountered!\n");
533 q = (base_tab[pos] * quant) >> 9;
535 val = val * q + FFSIGN(val) * (((q ^ 1) - 1) >> 1);
537 /* track columns containing non-zero coeffs */
538 col_flags[pos & col_mask] |= !!val;
541 if (scan_pos < 0 || scan_pos >= num_coeffs && sym != rvmap->eob_sym)
542 return AVERROR_INVALIDDATA; /* corrupt block data */
544 /* undoing DC coeff prediction for intra-blocks */
545 if (is_intra && band->is_2d_trans) {
546 *prev_dc += trvec[0];
548 col_flags[0] |= !!*prev_dc;
551 /* apply inverse transform */
552 band->inv_transform(trvec, band->buf + offs,
553 band->pitch, col_flags);
555 /* apply motion compensation */
557 return ivi_mc(band, mc, offs, mv_x, mv_y, mc_type);
563 * extract huffman-coded transform coefficients from the bitstream,
564 * dequantize them, apply inverse transform and motion compensation
565 * in order to reconstruct the picture.
567 * @param[in,out] gb the GetBit context
568 * @param[in] band pointer to the band descriptor
569 * @param[in] tile pointer to the tile descriptor
570 * @return result code: 0 - OK, -1 = error (corrupted blocks data)
572 static int ivi_decode_blocks(GetBitContext *gb, IVIBandDesc *band,
573 IVITile *tile, AVCodecContext *avctx)
575 int mbn, blk, num_blocks, blk_size, ret, is_intra, mc_type = 0;
576 int mv_x = 0, mv_y = 0;
578 uint32_t cbp, quant, buf_offs;
580 ivi_mc_func mc_with_delta_func, mc_no_delta_func;
581 const uint8_t *scale_tab;
583 /* init intra prediction for the DC coefficient */
585 blk_size = band->blk_size;
586 /* number of blocks per mb */
587 num_blocks = (band->mb_size != blk_size) ? 4 : 1;
589 mc_with_delta_func = ff_ivi_mc_8x8_delta;
590 mc_no_delta_func = ff_ivi_mc_8x8_no_delta;
592 mc_with_delta_func = ff_ivi_mc_4x4_delta;
593 mc_no_delta_func = ff_ivi_mc_4x4_no_delta;
596 for (mbn = 0, mb = tile->mbs; mbn < tile->num_MBs; mb++, mbn++) {
597 is_intra = !mb->type;
599 buf_offs = mb->buf_offs;
601 quant = band->glob_quant + mb->q_delta;
602 if (avctx->codec_id == AV_CODEC_ID_INDEO4)
603 quant = av_clip(quant, 0, 31);
605 quant = av_clip(quant, 0, 23);
607 scale_tab = is_intra ? band->intra_scale : band->inter_scale;
609 quant = scale_tab[quant];
614 if (band->is_halfpel) {
615 mc_type = ((mv_y & 1) << 1) | (mv_x & 1);
617 mv_y >>= 1; /* convert halfpel vectors into fullpel ones */
620 int dmv_x, dmv_y, cx, cy;
622 dmv_x = mb->mv_x >> band->is_halfpel;
623 dmv_y = mb->mv_y >> band->is_halfpel;
624 cx = mb->mv_x & band->is_halfpel;
625 cy = mb->mv_y & band->is_halfpel;
627 if (mb->xpos + dmv_x < 0 ||
628 mb->xpos + dmv_x + band->mb_size + cx > band->pitch ||
629 mb->ypos + dmv_y < 0 ||
630 mb->ypos + dmv_y + band->mb_size + cy > band->aheight) {
631 return AVERROR_INVALIDDATA;
636 for (blk = 0; blk < num_blocks; blk++) {
637 /* adjust block position in the buffer according to its number */
639 buf_offs += blk_size;
640 } else if (blk == 2) {
641 buf_offs -= blk_size;
642 buf_offs += blk_size * band->pitch;
645 if (cbp & 1) { /* block coded ? */
646 ret = ivi_decode_coded_blocks(gb, band, mc_with_delta_func,
647 mv_x, mv_y, &prev_dc, is_intra,
648 mc_type, quant, buf_offs, avctx);
652 /* block not coded */
653 /* for intra blocks apply the dc slant transform */
654 /* for inter - perform the motion compensation without delta */
656 ret = ivi_dc_transform(band, &prev_dc, buf_offs, blk_size);
660 ret = ivi_mc(band, mc_no_delta_func, buf_offs,
661 mv_x, mv_y, mc_type);
677 * Handle empty tiles by performing data copying and motion
678 * compensation respectively.
680 * @param[in] avctx ptr to the AVCodecContext
681 * @param[in] band pointer to the band descriptor
682 * @param[in] tile pointer to the tile descriptor
683 * @param[in] mv_scale scaling factor for motion vectors
685 static int ivi_process_empty_tile(AVCodecContext *avctx, IVIBandDesc *band,
686 IVITile *tile, int32_t mv_scale)
688 int x, y, need_mc, mbn, blk, num_blocks, mv_x, mv_y, mc_type;
689 int offs, mb_offset, row_offset, ret;
690 IVIMbInfo *mb, *ref_mb;
693 ivi_mc_func mc_no_delta_func;
695 if (tile->num_MBs != IVI_MBs_PER_TILE(tile->width, tile->height, band->mb_size)) {
696 av_log(avctx, AV_LOG_ERROR, "Allocated tile size %d mismatches "
697 "parameters %d in ivi_process_empty_tile()\n",
698 tile->num_MBs, IVI_MBs_PER_TILE(tile->width, tile->height, band->mb_size));
699 return AVERROR_INVALIDDATA;
702 offs = tile->ypos * band->pitch + tile->xpos;
704 ref_mb = tile->ref_mbs;
705 row_offset = band->mb_size * band->pitch;
706 need_mc = 0; /* reset the mc tracking flag */
708 for (y = tile->ypos; y < (tile->ypos + tile->height); y += band->mb_size) {
711 for (x = tile->xpos; x < (tile->xpos + tile->width); x += band->mb_size) {
714 mb->buf_offs = mb_offset;
716 mb->type = 1; /* set the macroblocks type = INTER */
717 mb->cbp = 0; /* all blocks are empty */
719 if (!band->qdelta_present && !band->plane && !band->band_num) {
720 mb->q_delta = band->glob_quant;
725 if (band->inherit_qdelta && ref_mb)
726 mb->q_delta = ref_mb->q_delta;
728 if (band->inherit_mv && ref_mb) {
729 /* motion vector inheritance */
731 mb->mv_x = ivi_scale_mv(ref_mb->mv_x, mv_scale);
732 mb->mv_y = ivi_scale_mv(ref_mb->mv_y, mv_scale);
734 mb->mv_x = ref_mb->mv_x;
735 mb->mv_y = ref_mb->mv_y;
737 need_mc |= mb->mv_x || mb->mv_y; /* tracking non-zero motion vectors */
743 mb_offset += band->mb_size;
748 if (band->inherit_mv && need_mc) { /* apply motion compensation if there is at least one non-zero motion vector */
749 num_blocks = (band->mb_size != band->blk_size) ? 4 : 1; /* number of blocks per mb */
750 mc_no_delta_func = (band->blk_size == 8) ? ff_ivi_mc_8x8_no_delta
751 : ff_ivi_mc_4x4_no_delta;
753 for (mbn = 0, mb = tile->mbs; mbn < tile->num_MBs; mb++, mbn++) {
756 if (!band->is_halfpel) {
757 mc_type = 0; /* we have only fullpel vectors */
759 mc_type = ((mv_y & 1) << 1) | (mv_x & 1);
761 mv_y >>= 1; /* convert halfpel vectors into fullpel ones */
764 for (blk = 0; blk < num_blocks; blk++) {
765 /* adjust block position in the buffer according with its number */
766 offs = mb->buf_offs + band->blk_size * ((blk & 1) + !!(blk & 2) * band->pitch);
767 ret = ivi_mc(band, mc_no_delta_func, offs,
768 mv_x, mv_y, mc_type);
774 /* copy data from the reference tile into the current one */
775 src = band->ref_buf + tile->ypos * band->pitch + tile->xpos;
776 dst = band->buf + tile->ypos * band->pitch + tile->xpos;
777 for (y = 0; y < tile->height; y++) {
778 memcpy(dst, src, tile->width*sizeof(band->buf[0]));
789 static uint16_t ivi_calc_band_checksum(IVIBandDesc *band)
792 int16_t *src, checksum;
797 for (y = 0; y < band->height; src += band->pitch, y++)
798 for (x = 0; x < band->width; x++)
806 * Convert and output the current plane.
807 * This conversion is done by adding back the bias value of 128
808 * (subtracted in the encoder) and clipping the result.
810 * @param[in] plane pointer to the descriptor of the plane being processed
811 * @param[out] dst pointer to the buffer receiving converted pixels
812 * @param[in] dst_pitch pitch for moving to the next y line
814 static void ivi_output_plane(IVIPlaneDesc *plane, uint8_t *dst, int dst_pitch)
817 const int16_t *src = plane->bands[0].buf;
818 uint32_t pitch = plane->bands[0].pitch;
823 for (y = 0; y < plane->height; y++) {
824 for (x = 0; x < plane->width; x++)
825 dst[x] = av_clip_uint8(src[x] + 128);
832 * Decode an Indeo 4 or 5 band.
834 * @param[in,out] ctx ptr to the decoder context
835 * @param[in,out] band ptr to the band descriptor
836 * @param[in] avctx ptr to the AVCodecContext
837 * @return result code: 0 = OK, -1 = error
839 static int decode_band(IVI45DecContext *ctx,
840 IVIBandDesc *band, AVCodecContext *avctx)
842 int result, i, t, idx1, idx2, pos;
845 band->buf = band->bufs[ctx->dst_buf];
847 av_log(avctx, AV_LOG_ERROR, "Band buffer points to no data!\n");
848 return AVERROR_INVALIDDATA;
850 band->ref_buf = band->bufs[ctx->ref_buf];
851 band->data_ptr = ctx->frame_data + (get_bits_count(&ctx->gb) >> 3);
853 result = ctx->decode_band_hdr(ctx, band, avctx);
855 av_log(avctx, AV_LOG_ERROR, "Error while decoding band header: %d\n",
860 if (band->is_empty) {
861 av_log(avctx, AV_LOG_ERROR, "Empty band encountered!\n");
862 return AVERROR_INVALIDDATA;
865 band->rv_map = &ctx->rvmap_tabs[band->rvmap_sel];
867 /* apply corrections to the selected rvmap table if present */
868 for (i = 0; i < band->num_corr; i++) {
869 idx1 = band->corr[i * 2];
870 idx2 = band->corr[i * 2 + 1];
871 FFSWAP(uint8_t, band->rv_map->runtab[idx1], band->rv_map->runtab[idx2]);
872 FFSWAP(int16_t, band->rv_map->valtab[idx1], band->rv_map->valtab[idx2]);
875 pos = get_bits_count(&ctx->gb);
877 for (t = 0; t < band->num_tiles; t++) {
878 tile = &band->tiles[t];
880 if (tile->mb_size != band->mb_size) {
881 av_log(avctx, AV_LOG_ERROR, "MB sizes mismatch: %d vs. %d\n",
882 band->mb_size, tile->mb_size);
883 return AVERROR_INVALIDDATA;
885 tile->is_empty = get_bits1(&ctx->gb);
886 if (tile->is_empty) {
887 result = ivi_process_empty_tile(avctx, band, tile,
888 (ctx->planes[0].bands[0].mb_size >> 3) - (band->mb_size >> 3));
891 av_dlog(avctx, "Empty tile encountered!\n");
893 tile->data_size = ivi_dec_tile_data_size(&ctx->gb);
894 if (!tile->data_size) {
895 av_log(avctx, AV_LOG_ERROR, "Tile data size is zero!\n");
896 return AVERROR_INVALIDDATA;
899 result = ctx->decode_mb_info(ctx, band, tile, avctx);
903 result = ivi_decode_blocks(&ctx->gb, band, tile, avctx);
905 av_log(avctx, AV_LOG_ERROR,
906 "Corrupted tile data encountered!\n");
910 if (((get_bits_count(&ctx->gb) - pos) >> 3) != tile->data_size) {
911 av_log(avctx, AV_LOG_ERROR,
912 "Tile data_size mismatch!\n");
913 result = AVERROR_INVALIDDATA;
917 pos += tile->data_size << 3; // skip to next tile
921 /* restore the selected rvmap table by applying its corrections in
923 for (i = band->num_corr-1; i >= 0; i--) {
924 idx1 = band->corr[i*2];
925 idx2 = band->corr[i*2+1];
926 FFSWAP(uint8_t, band->rv_map->runtab[idx1], band->rv_map->runtab[idx2]);
927 FFSWAP(int16_t, band->rv_map->valtab[idx1], band->rv_map->valtab[idx2]);
931 if (band->checksum_present) {
932 uint16_t chksum = ivi_calc_band_checksum(band);
933 if (chksum != band->checksum) {
934 av_log(avctx, AV_LOG_ERROR,
935 "Band checksum mismatch! Plane %d, band %d, "
936 "received: %x, calculated: %x\n",
937 band->plane, band->band_num, band->checksum, chksum);
942 align_get_bits(&ctx->gb);
947 int ff_ivi_decode_frame(AVCodecContext *avctx, void *data, int *got_frame,
950 IVI45DecContext *ctx = avctx->priv_data;
951 const uint8_t *buf = avpkt->data;
952 AVFrame *frame = data;
953 int buf_size = avpkt->size;
956 init_get_bits(&ctx->gb, buf, buf_size * 8);
957 ctx->frame_data = buf;
958 ctx->frame_size = buf_size;
960 result = ctx->decode_pic_hdr(ctx, avctx);
962 av_log(avctx, AV_LOG_ERROR,
963 "Error while decoding picture header: %d\n", result);
966 if (ctx->gop_invalid)
967 return AVERROR_INVALIDDATA;
969 if (ctx->gop_flags & IVI5_IS_PROTECTED) {
970 avpriv_report_missing_feature(avctx, "Password-protected clip!\n");
971 return AVERROR_PATCHWELCOME;
974 if (!ctx->planes[0].bands) {
975 av_log(avctx, AV_LOG_ERROR, "Color planes not initialized yet\n");
976 return AVERROR_INVALIDDATA;
979 ctx->switch_buffers(ctx);
983 if (ctx->is_nonnull_frame(ctx)) {
984 for (p = 0; p < 3; p++) {
985 for (b = 0; b < ctx->planes[p].num_bands; b++) {
986 result = decode_band(ctx, &ctx->planes[p].bands[b], avctx);
988 av_log(avctx, AV_LOG_ERROR,
989 "Error while decoding band: %d, plane: %d\n", b, p);
995 if (ctx->is_scalable)
996 return AVERROR_INVALIDDATA;
998 for (p = 0; p < 3; p++) {
999 if (!ctx->planes[p].bands[0].buf)
1000 return AVERROR_INVALIDDATA;
1004 //STOP_TIMER("decode_planes"); }
1006 /* If the bidirectional mode is enabled, next I and the following P
1007 * frame will be sent together. Unfortunately the approach below seems
1008 * to be the only way to handle the B-frames mode.
1009 * That's exactly the same Intel decoders do.
1011 if (avctx->codec_id == AV_CODEC_ID_INDEO4 &&
1012 ctx->frame_type == 0/*FRAMETYPE_INTRA*/) {
1013 while (get_bits(&ctx->gb, 8)); // skip version string
1014 skip_bits_long(&ctx->gb, 64); // skip padding, TODO: implement correct 8-bytes alignment
1015 if (get_bits_left(&ctx->gb) > 18 && show_bits(&ctx->gb, 18) == 0x3FFF8)
1016 av_log(avctx, AV_LOG_ERROR, "Buffer contains IP frames!\n");
1019 result = ff_set_dimensions(avctx, ctx->planes[0].width, ctx->planes[0].height);
1023 if ((result = ff_get_buffer(avctx, frame, 0)) < 0) {
1024 av_log(avctx, AV_LOG_ERROR, "get_buffer() failed\n");
1028 if (ctx->is_scalable) {
1029 if (avctx->codec_id == AV_CODEC_ID_INDEO4)
1030 ff_ivi_recompose_haar(&ctx->planes[0], frame->data[0], frame->linesize[0]);
1032 ff_ivi_recompose53 (&ctx->planes[0], frame->data[0], frame->linesize[0]);
1034 ivi_output_plane(&ctx->planes[0], frame->data[0], frame->linesize[0]);
1037 ivi_output_plane(&ctx->planes[2], frame->data[1], frame->linesize[1]);
1038 ivi_output_plane(&ctx->planes[1], frame->data[2], frame->linesize[2]);
1046 * Close Indeo5 decoder and clean up its context.
1048 av_cold int ff_ivi_decode_close(AVCodecContext *avctx)
1050 IVI45DecContext *ctx = avctx->priv_data;
1052 ivi_free_buffers(&ctx->planes[0]);
1054 if (ctx->mb_vlc.cust_tab.table)
1055 ff_free_vlc(&ctx->mb_vlc.cust_tab);
1057 #if IVI4_STREAM_ANALYSER
1058 if (avctx->codec_id == AV_CODEC_ID_INDEO4) {
1059 if (ctx->is_scalable)
1060 av_log(avctx, AV_LOG_ERROR, "This video uses scalability mode!\n");
1061 if (ctx->uses_tiling)
1062 av_log(avctx, AV_LOG_ERROR, "This video uses local decoding!\n");
1063 if (ctx->has_b_frames)
1064 av_log(avctx, AV_LOG_ERROR, "This video contains B-frames!\n");
1065 if (ctx->has_transp)
1066 av_log(avctx, AV_LOG_ERROR, "Transparency mode is enabled!\n");
1068 av_log(avctx, AV_LOG_ERROR, "This video uses Haar transform!\n");
1069 if (ctx->uses_fullpel)
1070 av_log(avctx, AV_LOG_ERROR, "This video uses fullpel motion vectors!\n");
1079 * Scan patterns shared between indeo4 and indeo5
1081 const uint8_t ff_ivi_vertical_scan_8x8[64] = {
1082 0, 8, 16, 24, 32, 40, 48, 56,
1083 1, 9, 17, 25, 33, 41, 49, 57,
1084 2, 10, 18, 26, 34, 42, 50, 58,
1085 3, 11, 19, 27, 35, 43, 51, 59,
1086 4, 12, 20, 28, 36, 44, 52, 60,
1087 5, 13, 21, 29, 37, 45, 53, 61,
1088 6, 14, 22, 30, 38, 46, 54, 62,
1089 7, 15, 23, 31, 39, 47, 55, 63
1092 const uint8_t ff_ivi_horizontal_scan_8x8[64] = {
1093 0, 1, 2, 3, 4, 5, 6, 7,
1094 8, 9, 10, 11, 12, 13, 14, 15,
1095 16, 17, 18, 19, 20, 21, 22, 23,
1096 24, 25, 26, 27, 28, 29, 30, 31,
1097 32, 33, 34, 35, 36, 37, 38, 39,
1098 40, 41, 42, 43, 44, 45, 46, 47,
1099 48, 49, 50, 51, 52, 53, 54, 55,
1100 56, 57, 58, 59, 60, 61, 62, 63
1103 const uint8_t ff_ivi_direct_scan_4x4[16] = {
1104 0, 1, 4, 8, 5, 2, 3, 6, 9, 12, 13, 10, 7, 11, 14, 15
1109 * Run-value (RLE) tables.
1111 const RVMapDesc ff_ivi_rvmap_tabs[9] = {
1116 {1, 1, 0, 1, 1, 0, 1, 1, 2, 2, 1, 1, 1, 1, 3, 3,
1117 1, 1, 2, 2, 1, 1, 4, 4, 1, 1, 1, 1, 2, 2, 5, 5,
1118 1, 1, 3, 3, 1, 1, 6, 6, 1, 2, 1, 2, 7, 7, 1, 1,
1119 8, 8, 1, 1, 4, 2, 1, 4, 2, 1, 3, 3, 1, 1, 1, 9,
1120 9, 1, 2, 1, 2, 1, 5, 5, 1, 1, 10, 10, 1, 1, 3, 3,
1121 2, 2, 1, 1, 11, 11, 6, 4, 4, 1, 6, 1, 2, 1, 2, 12,
1122 8, 1, 12, 7, 8, 7, 1, 16, 1, 16, 1, 3, 3, 13, 1, 13,
1123 2, 2, 1, 15, 1, 5, 14, 15, 1, 5, 14, 1, 17, 8, 17, 8,
1124 1, 4, 4, 2, 2, 1, 25, 25, 24, 24, 1, 3, 1, 3, 1, 8,
1125 6, 7, 6, 1, 18, 8, 18, 1, 7, 23, 2, 2, 23, 1, 1, 21,
1126 22, 9, 9, 22, 19, 1, 21, 5, 19, 5, 1, 33, 20, 33, 20, 8,
1127 4, 4, 1, 32, 2, 2, 8, 3, 32, 26, 3, 1, 7, 7, 26, 6,
1128 1, 6, 1, 1, 16, 1, 10, 1, 10, 2, 16, 29, 28, 2, 29, 28,
1129 1, 27, 5, 8, 5, 27, 1, 8, 3, 7, 3, 31, 41, 31, 1, 41,
1130 6, 1, 6, 7, 4, 4, 1, 1, 2, 1, 2, 11, 34, 30, 11, 1,
1131 30, 15, 15, 34, 36, 40, 36, 40, 35, 35, 37, 37, 39, 39, 38, 38},
1134 { 1, -1, 0, 2, -2, 0, 3, -3, 1, -1, 4, -4, 5, -5, 1, -1,
1135 6, -6, 2, -2, 7, -7, 1, -1, 8, -8, 9, -9, 3, -3, 1, -1,
1136 10, -10, 2, -2, 11, -11, 1, -1, 12, 4, -12, -4, 1, -1, 13, -13,
1137 1, -1, 14, -14, 2, 5, 15, -2, -5, -15, -3, 3, 16, -16, 17, 1,
1138 -1, -17, 6, 18, -6, -18, 2, -2, 19, -19, 1, -1, 20, -20, 4, -4,
1139 7, -7, 21, -21, 1, -1, 2, 3, -3, 22, -2, -22, 8, 23, -8, 1,
1140 2, -23, -1, 2, -2, -2, 24, 1, -24, -1, 25, 5, -5, 1, -25, -1,
1141 9, -9, 26, 1, -26, 3, 1, -1, 27, -3, -1, -27, 1, 3, -1, -3,
1142 28, -4, 4, 10, -10, -28, 1, -1, 1, -1, 29, 6, -29, -6, 30, -4,
1143 3, 3, -3, -30, 1, 4, -1, 31, -3, 1, 11, -11, -1, -31, 32, -1,
1144 -1, 2, -2, 1, 1, -32, 1, 4, -1, -4, 33, -1, 1, 1, -1, 5,
1145 5, -5, -33, -1, -12, 12, -5, -7, 1, 1, 7, 34, 4, -4, -1, 4,
1146 -34, -4, 35, 36, -2, -35, -2, -36, 2, 13, 2, -1, 1, -13, 1, -1,
1147 37, 1, -5, 6, 5, -1, 38, -6, -8, 5, 8, -1, 1, 1, -37, -1,
1148 5, 39, -5, -5, 6, -6, -38, -39, -14, 40, 14, 2, 1, 1, -2, -40,
1149 -1, -2, 2, -1, -1, -1, 1, 1, 1, -1, 1, -1, 1, -1, 1, -1}
1155 {0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 8, 6, 8, 7,
1156 7, 9, 9, 10, 10, 11, 11, 1, 12, 1, 12, 13, 13, 16, 14, 16,
1157 14, 15, 15, 17, 17, 18, 0, 18, 19, 20, 21, 19, 22, 21, 20, 22,
1158 25, 24, 2, 25, 24, 23, 23, 2, 26, 28, 26, 28, 29, 27, 29, 27,
1159 33, 33, 1, 32, 1, 3, 32, 30, 36, 3, 36, 30, 31, 31, 35, 34,
1160 37, 41, 34, 35, 37, 4, 41, 4, 49, 8, 8, 49, 40, 38, 5, 38,
1161 40, 39, 5, 39, 42, 43, 42, 7, 57, 6, 43, 44, 6, 50, 7, 44,
1162 57, 48, 50, 48, 45, 45, 46, 47, 51, 46, 47, 58, 1, 51, 58, 1,
1163 52, 59, 53, 9, 52, 55, 55, 59, 53, 56, 54, 56, 54, 9, 64, 64,
1164 60, 63, 60, 63, 61, 62, 61, 62, 2, 10, 2, 10, 11, 1, 11, 13,
1165 12, 1, 12, 13, 16, 16, 8, 8, 14, 3, 3, 15, 14, 15, 4, 4,
1166 1, 17, 17, 5, 1, 7, 7, 5, 6, 1, 2, 2, 6, 22, 1, 25,
1167 21, 22, 8, 24, 1, 21, 25, 24, 8, 18, 18, 23, 9, 20, 23, 33,
1168 29, 33, 20, 1, 19, 1, 29, 36, 9, 36, 19, 41, 28, 57, 32, 3,
1169 28, 3, 1, 27, 49, 49, 1, 32, 26, 26, 2, 4, 4, 7, 57, 41,
1170 2, 7, 10, 5, 37, 16, 10, 27, 8, 8, 13, 16, 37, 13, 1, 5},
1173 {0, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, 1, -1, -1, 1,
1174 -1, 1, -1, 1, -1, 1, -1, 2, 1, -2, -1, 1, -1, 1, 1, -1,
1175 -1, 1, -1, 1, -1, 1, 0, -1, 1, 1, 1, -1, 1, -1, -1, -1,
1176 1, 1, 2, -1, -1, 1, -1, -2, 1, 1, -1, -1, 1, 1, -1, -1,
1177 1, -1, 3, 1, -3, 2, -1, 1, 1, -2, -1, -1, -1, 1, 1, 1,
1178 1, 1, -1, -1, -1, 2, -1, -2, 1, 2, -2, -1, 1, 1, 2, -1,
1179 -1, 1, -2, -1, 1, 1, -1, 2, 1, 2, -1, 1, -2, -1, -2, -1,
1180 -1, 1, 1, -1, 1, -1, 1, 1, 1, -1, -1, 1, 4, -1, -1, -4,
1181 1, 1, 1, 2, -1, -1, 1, -1, -1, 1, -1, -1, 1, -2, 1, -1,
1182 1, 1, -1, -1, 1, 1, -1, -1, 3, 2, -3, -2, 2, 5, -2, 2,
1183 2, -5, -2, -2, -2, 2, -3, 3, 2, 3, -3, 2, -2, -2, 3, -3,
1184 6, 2, -2, 3, -6, 3, -3, -3, 3, 7, -4, 4, -3, 2, -7, 2,
1185 2, -2, -4, 2, 8, -2, -2, -2, 4, 2, -2, 2, 3, 2, -2, -2,
1186 2, 2, -2, -8, -2, 9, -2, 2, -3, -2, 2, -2, 2, 2, 2, 4,
1187 -2, -4, 10, 2, 2, -2, -9, -2, 2, -2, 5, 4, -4, 4, -2, 2,
1188 -5, -4, -3, 4, 2, -3, 3, -2, -5, 5, 3, 3, -2, -3, -10, -4}
1194 {1, 1, 0, 2, 2, 1, 1, 3, 3, 4, 4, 0, 1, 1, 5, 5,
1195 2, 2, 6, 6, 7, 7, 1, 8, 1, 8, 3, 3, 9, 9, 1, 2,
1196 2, 1, 4, 10, 4, 10, 11, 11, 1, 5, 12, 12, 1, 5, 13, 13,
1197 3, 3, 6, 6, 2, 2, 14, 14, 16, 16, 15, 7, 15, 8, 8, 7,
1198 1, 1, 17, 17, 4, 4, 1, 1, 18, 18, 2, 2, 5, 5, 25, 3,
1199 9, 3, 25, 9, 19, 24, 19, 24, 1, 21, 20, 1, 21, 22, 20, 22,
1200 23, 23, 8, 6, 33, 6, 8, 33, 7, 7, 26, 26, 1, 32, 1, 32,
1201 28, 4, 28, 10, 29, 27, 27, 10, 41, 4, 29, 2, 2, 41, 36, 31,
1202 49, 31, 34, 30, 34, 36, 30, 35, 1, 49, 11, 5, 35, 11, 1, 3,
1203 3, 5, 37, 37, 8, 40, 8, 40, 12, 12, 42, 42, 1, 38, 16, 57,
1204 1, 6, 16, 39, 38, 6, 7, 7, 13, 13, 39, 43, 2, 43, 57, 2,
1205 50, 9, 44, 9, 50, 4, 15, 48, 44, 4, 1, 15, 48, 14, 14, 1,
1206 45, 45, 8, 3, 5, 8, 51, 47, 3, 46, 46, 47, 5, 51, 1, 17,
1207 17, 58, 1, 58, 2, 52, 52, 2, 53, 7, 59, 6, 6, 56, 53, 55,
1208 7, 55, 1, 54, 59, 56, 54, 10, 1, 10, 4, 60, 1, 60, 8, 4,
1209 8, 64, 64, 61, 1, 63, 3, 63, 62, 61, 5, 11, 5, 3, 11, 62},
1212 { 1, -1, 0, 1, -1, 2, -2, 1, -1, 1, -1, 0, 3, -3, 1, -1,
1213 2, -2, 1, -1, 1, -1, 4, 1, -4, -1, 2, -2, 1, -1, 5, 3,
1214 -3, -5, 2, 1, -2, -1, 1, -1, 6, 2, 1, -1, -6, -2, 1, -1,
1215 3, -3, 2, -2, 4, -4, 1, -1, 1, -1, 1, 2, -1, 2, -2, -2,
1216 7, -7, 1, -1, 3, -3, 8, -8, 1, -1, 5, -5, 3, -3, 1, 4,
1217 2, -4, -1, -2, 1, 1, -1, -1, 9, 1, 1, -9, -1, 1, -1, -1,
1218 1, -1, 3, -3, 1, 3, -3, -1, 3, -3, 1, -1, 10, 1, -10, -1,
1219 1, 4, -1, 2, 1, -1, 1, -2, 1, -4, -1, 6, -6, -1, 1, 1,
1220 1, -1, 1, 1, -1, -1, -1, 1, 11, -1, -2, 4, -1, 2, -11, 5,
1221 -5, -4, -1, 1, 4, 1, -4, -1, -2, 2, 1, -1, 12, 1, -2, 1,
1222 -12, 4, 2, 1, -1, -4, 4, -4, 2, -2, -1, 1, 7, -1, -1, -7,
1223 -1, -3, 1, 3, 1, 5, 2, 1, -1, -5, 13, -2, -1, 2, -2, -13,
1224 1, -1, 5, 6, 5, -5, 1, 1, -6, 1, -1, -1, -5, -1, 14, 2,
1225 -2, 1, -14, -1, 8, 1, -1, -8, 1, 5, 1, 5, -5, 1, -1, 1,
1226 -5, -1, 15, 1, -1, -1, -1, 3, -15, -3, 6, 1, 16, -1, 6, -6,
1227 -6, 1, -1, 1, -16, 1, 7, -1, 1, -1, -6, -3, 6, -7, 3, -1}
1233 {0, 1, 1, 2, 2, 3, 3, 4, 4, 1, 1, 5, 5, 6, 6, 7,
1234 7, 8, 8, 9, 9, 2, 2, 10, 10, 1, 1, 11, 11, 12, 12, 3,
1235 3, 13, 13, 0, 14, 14, 16, 15, 16, 15, 4, 4, 17, 1, 17, 1,
1236 5, 5, 18, 18, 2, 2, 6, 6, 8, 19, 7, 8, 7, 19, 20, 20,
1237 21, 21, 22, 24, 22, 24, 23, 23, 1, 1, 25, 25, 3, 3, 26, 26,
1238 9, 9, 27, 27, 28, 28, 33, 29, 4, 33, 29, 1, 4, 1, 32, 32,
1239 2, 2, 31, 10, 30, 10, 30, 31, 34, 34, 5, 5, 36, 36, 35, 41,
1240 35, 11, 41, 11, 37, 1, 8, 8, 37, 6, 1, 6, 40, 7, 7, 40,
1241 12, 38, 12, 39, 39, 38, 49, 13, 49, 13, 3, 42, 3, 42, 16, 16,
1242 43, 43, 14, 14, 1, 1, 44, 15, 44, 15, 2, 2, 57, 48, 50, 48,
1243 57, 50, 4, 45, 45, 4, 46, 47, 47, 46, 1, 51, 1, 17, 17, 51,
1244 8, 9, 9, 5, 58, 8, 58, 5, 52, 52, 55, 56, 53, 56, 55, 59,
1245 59, 53, 54, 1, 6, 54, 7, 7, 6, 1, 2, 3, 2, 3, 64, 60,
1246 60, 10, 10, 64, 61, 62, 61, 63, 1, 63, 62, 1, 18, 24, 18, 4,
1247 25, 4, 8, 21, 21, 1, 24, 22, 25, 22, 8, 11, 19, 11, 23, 1,
1248 20, 23, 19, 20, 5, 12, 5, 1, 16, 2, 12, 13, 2, 13, 1, 16},
1251 { 0, 1, -1, 1, -1, 1, -1, 1, -1, 2, -2, 1, -1, 1, -1, 1,
1252 -1, 1, -1, 1, -1, 2, -2, 1, -1, 3, -3, 1, -1, 1, -1, 2,
1253 -2, 1, -1, 0, 1, -1, 1, 1, -1, -1, 2, -2, 1, 4, -1, -4,
1254 2, -2, 1, -1, -3, 3, 2, -2, 2, 1, 2, -2, -2, -1, 1, -1,
1255 1, -1, 1, 1, -1, -1, 1, -1, 5, -5, 1, -1, 3, -3, 1, -1,
1256 2, -2, 1, -1, 1, -1, 1, 1, 3, -1, -1, 6, -3, -6, -1, 1,
1257 4, -4, 1, 2, 1, -2, -1, -1, 1, -1, 3, -3, 1, -1, 1, 1,
1258 -1, 2, -1, -2, 1, 7, -3, 3, -1, 3, -7, -3, 1, -3, 3, -1,
1259 2, 1, -2, 1, -1, -1, 1, 2, -1, -2, -4, -1, 4, 1, 2, -2,
1260 1, -1, -2, 2, 8, -8, -1, 2, 1, -2, -5, 5, 1, -1, -1, 1,
1261 -1, 1, 4, -1, 1, -4, -1, -1, 1, 1, 9, 1, -9, 2, -2, -1,
1262 -4, 3, -3, -4, -1, 4, 1, 4, 1, -1, 1, -1, 1, 1, -1, 1,
1263 -1, -1, -1, 10, 4, 1, 4, -4, -4, -10, 6, 5, -6, -5, 1, -1,
1264 1, 3, -3, -1, 1, -1, -1, -1, 11, 1, 1, -11, -2, -2, 2, 5,
1265 -2, -5, -5, 2, -2, 12, 2, -2, 2, 2, 5, -3, -2, 3, -2, -12,
1266 -2, 2, 2, 2, -5, 3, 5, 13, -3, 7, -3, -3, -7, 3, -13, 3}
1272 {0, 1, 1, 1, 2, 2, 1, 3, 3, 1, 1, 1, 4, 4, 1, 5,
1273 2, 1, 5, 2, 1, 1, 6, 6, 1, 1, 1, 1, 1, 7, 3, 1,
1274 2, 3, 0, 1, 2, 7, 1, 1, 1, 8, 1, 1, 8, 1, 1, 1,
1275 9, 1, 9, 1, 2, 1, 1, 2, 1, 1, 10, 4, 1, 10, 1, 4,
1276 1, 1, 1, 1, 1, 3, 1, 1, 1, 3, 2, 1, 5, 1, 1, 1,
1277 2, 5, 1, 11, 1, 11, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1278 2, 1, 6, 1, 6, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 12,
1279 3, 1, 12, 1, 1, 1, 2, 1, 1, 3, 1, 1, 1, 1, 1, 1,
1280 4, 1, 1, 1, 2, 1, 1, 4, 1, 1, 1, 1, 1, 1, 2, 1,
1281 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 2, 1, 1, 5,
1282 1, 1, 1, 1, 1, 7, 1, 7, 1, 1, 2, 3, 1, 1, 1, 1,
1283 5, 1, 1, 1, 1, 1, 1, 2, 13, 1, 1, 1, 1, 1, 1, 1,
1284 1, 1, 1, 1, 1, 1, 1, 1, 13, 2, 1, 1, 4, 1, 1, 1,
1285 3, 1, 6, 1, 1, 1, 14, 1, 1, 1, 1, 1, 14, 6, 1, 1,
1286 1, 1, 15, 2, 4, 1, 2, 3, 15, 1, 1, 1, 8, 1, 1, 8,
1287 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1},
1290 { 0, 1, -1, 2, 1, -1, -2, 1, -1, 3, -3, 4, 1, -1, -4, 1,
1291 2, 5, -1, -2, -5, 6, 1, -1, -6, 7, -7, 8, -8, 1, 2, 9,
1292 3, -2, 0, -9, -3, -1, 10, -10, 11, 1, -11, 12, -1, -12, 13, -13,
1293 1, 14, -1, -14, 4, 15, -15, -4, 16, -16, 1, 2, 17, -1, -17, -2,
1294 18, -18, 19, -19, 20, 3, -20, 21, -21, -3, 5, 22, 2, -22, -23, 23,
1295 -5, -2, 24, 1, -24, -1, 25, -25, 26, -26, -27, 27, 28, 29, -28, -29,
1296 6, 30, 2, -31, -2, -30, 31, -6, -32, 32, 33, -33, 34, -35, -34, 1,
1297 4, -36, -1, 35, 37, 36, 7, -37, 38, -4, -38, 39, 41, 40, -40, -39,
1298 3, 42, -43, -41, -7, -42, 43, -3, 44, -44, 45, -45, 46, 47, 8, -47,
1299 -48, -46, 50, -50, 48, 49, 51, -49, 52, -52, 5, -51, -8, -53, 53, 3,
1300 -56, 56, 55, 54, -54, 2, 60, -2, -55, 58, 9, -5, 59, 57, -57, -63,
1301 -3, -58, -60, -61, 61, -59, -62, -9, 1, 64, 62, 69, -64, 63, 65, -67,
1302 -68, 66, -65, 68, -66, -69, 67, -70, -1, 10, 71, -71, 4, 73, 72, 70,
1303 6, -76, -3, 74, -78, -74, 1, 78, 80, -72, -75, 76, -1, 3, -73, 79,
1304 75, 77, 1, 11, -4, -79, -10, -6, -1, -77, -83, -80, 2, 81, -84, -2,
1305 83, -81, 82, -82, 84, -87, -86, 85, -11, -85, 86, -89, 87, -88, 88, 89}
1311 {1, 1, 0, 2, 1, 2, 1, 3, 3, 1, 1, 4, 4, 2, 2, 1,
1312 1, 5, 5, 6, 1, 6, 1, 7, 7, 3, 3, 2, 8, 2, 8, 1,
1313 1, 0, 9, 9, 1, 1, 10, 4, 10, 4, 11, 11, 2, 1, 2, 1,
1314 12, 12, 3, 3, 1, 1, 13, 5, 5, 13, 14, 1, 1, 14, 2, 2,
1315 6, 6, 15, 1, 1, 15, 16, 4, 7, 16, 4, 7, 1, 1, 3, 3,
1316 8, 8, 2, 2, 1, 1, 17, 17, 1, 1, 18, 18, 5, 5, 2, 2,
1317 1, 1, 9, 19, 9, 19, 20, 3, 3, 20, 1, 10, 21, 1, 10, 4,
1318 4, 21, 22, 6, 6, 22, 1, 1, 23, 24, 2, 2, 23, 24, 11, 1,
1319 1, 11, 7, 25, 7, 1, 1, 25, 8, 8, 3, 26, 3, 1, 12, 2,
1320 2, 26, 1, 12, 5, 5, 27, 4, 1, 4, 1, 27, 28, 1, 28, 13,
1321 1, 13, 2, 29, 2, 1, 32, 6, 1, 30, 14, 29, 14, 6, 3, 31,
1322 3, 1, 30, 1, 32, 31, 33, 9, 33, 1, 1, 7, 9, 7, 2, 2,
1323 1, 1, 4, 36, 34, 4, 5, 10, 10, 5, 34, 1, 1, 35, 8, 8,
1324 36, 3, 35, 1, 15, 3, 2, 1, 16, 15, 16, 2, 37, 1, 37, 1,
1325 1, 1, 6, 6, 38, 1, 38, 11, 1, 39, 39, 40, 11, 2, 41, 4,
1326 40, 1, 2, 4, 1, 1, 1, 41, 3, 1, 3, 1, 5, 7, 5, 7},
1329 { 1, -1, 0, 1, 2, -1, -2, 1, -1, 3, -3, 1, -1, 2, -2, 4,
1330 -4, 1, -1, 1, 5, -1, -5, 1, -1, 2, -2, 3, 1, -3, -1, 6,
1331 -6, 0, 1, -1, 7, -7, 1, 2, -1, -2, 1, -1, 4, 8, -4, -8,
1332 1, -1, 3, -3, 9, -9, 1, 2, -2, -1, 1, 10, -10, -1, 5, -5,
1333 2, -2, 1, 11, -11, -1, 1, 3, 2, -1, -3, -2, 12, -12, 4, -4,
1334 2, -2, -6, 6, 13, -13, 1, -1, 14, -14, 1, -1, 3, -3, 7, -7,
1335 15, -15, 2, 1, -2, -1, 1, 5, -5, -1, -16, 2, 1, 16, -2, 4,
1336 -4, -1, 1, 3, -3, -1, 17, -17, 1, 1, -8, 8, -1, -1, 2, 18,
1337 -18, -2, 3, 1, -3, 19, -19, -1, 3, -3, 6, 1, -6, 20, 2, 9,
1338 -9, -1, -20, -2, 4, -4, 1, -5, 21, 5, -21, -1, 1, -22, -1, 2,
1339 22, -2, 10, 1, -10, 23, 1, 4, -23, 1, 2, -1, -2, -4, -7, 1,
1340 7, -24, -1, 24, -1, -1, 1, 3, -1, -25, 25, 4, -3, -4, 11, -11,
1341 26, -26, 6, 1, 1, -6, -5, -3, 3, 5, -1, -27, 27, 1, 4, -4,
1342 -1, -8, -1, 28, 2, 8, -12, -28, -2, -2, 2, 12, -1, 29, 1, -29,
1343 30, -30, 5, -5, 1, -31, -1, 3, 31, -1, 1, 1, -3, -13, 1, -7,
1344 -1, -32, 13, 7, 32, 33, -33, -1, -9, -34, 9, 34, -6, 5, 6, -5}
1350 {1, 1, 0, 1, 1, 2, 2, 1, 1, 3, 3, 1, 1, 0, 2, 2,
1351 4, 1, 4, 1, 1, 1, 5, 5, 1, 1, 6, 6, 2, 2, 1, 1,
1352 3, 3, 7, 7, 1, 1, 8, 8, 1, 1, 2, 2, 1, 9, 1, 9,
1353 4, 4, 10, 1, 1, 10, 1, 1, 11, 11, 3, 3, 1, 2, 1, 2,
1354 1, 1, 12, 12, 5, 5, 1, 1, 13, 1, 1, 13, 2, 2, 1, 1,
1355 6, 6, 1, 1, 4, 14, 4, 14, 3, 1, 3, 1, 1, 1, 15, 7,
1356 15, 2, 2, 7, 1, 1, 1, 8, 1, 8, 16, 16, 1, 1, 1, 1,
1357 2, 1, 1, 2, 1, 1, 3, 5, 5, 3, 4, 1, 1, 4, 1, 1,
1358 17, 17, 9, 1, 1, 9, 2, 2, 1, 1, 10, 10, 1, 6, 1, 1,
1359 6, 18, 1, 1, 18, 1, 1, 1, 2, 2, 3, 1, 3, 1, 1, 1,
1360 4, 1, 19, 1, 19, 7, 1, 1, 20, 1, 4, 20, 1, 7, 11, 2,
1361 1, 11, 21, 2, 8, 5, 1, 8, 1, 5, 21, 1, 1, 1, 22, 1,
1362 1, 22, 1, 1, 3, 3, 1, 23, 2, 12, 24, 1, 1, 2, 1, 1,
1363 12, 23, 1, 1, 24, 1, 1, 1, 4, 1, 1, 1, 2, 1, 6, 6,
1364 4, 2, 1, 1, 1, 1, 1, 1, 1, 14, 13, 3, 1, 25, 9, 25,
1365 14, 1, 9, 3, 13, 1, 1, 1, 1, 1, 10, 1, 1, 2, 10, 2},
1368 {-20, -1, 0, 2, -2, 1, -1, 3, -3, 1, -1, 4, -4, 0, 2, -2,
1369 1, 5, -1, -5, 6, -6, 1, -1, 7, -7, 1, -1, 3, -3, 8, -8,
1370 2, -2, 1, -1, 9, -9, 1, -1, 10, -10, 4, -4, 11, 1, -11, -1,
1371 2, -2, 1, 12, -12, -1, 13, -13, 1, -1, 3, -3, 14, 5, -14, -5,
1372 -15, 15, -1, 1, 2, -2, 16, -16, 1, 17, -17, -1, 6, -6, 18, -18,
1373 2, -2, -19, 19, -3, 1, 3, -1, 4, 20, -4, 1, -21, 21, 1, 2,
1374 -1, -7, 7, -2, 22, -22, 23, 2, -23, -2, 1, -1, -24, 24, -25, 25,
1375 -8, -26, 26, 8, -27, 27, 5, 3, -3, -5, -4, 28, -28, 4, 29, -29,
1376 1, -1, -2, -30, 30, 2, 9, -9, -31, 31, 2, -2, -32, 3, 32, -33,
1377 -3, 1, 33, -34, -1, 34, -35, 35, -10, 10, -6, 36, 6, -36, 37, -37,
1378 -5, 38, 1, -38, -1, 3, 39, -39, -1, 40, 5, 1, -40, -3, 2, -11,
1379 -41, -2, 1, 11, -3, -4, 41, 3, 42, 4, -1, -43, -42, 43, 1, -44,
1380 45, -1, 44, -45, -7, 7, -46, 1, -12, 2, 1, -47, 46, 12, 47, 48,
1381 -2, -1, -48, 49, -1, -50, -49, 50, -6, -51, 51, 52, -13, 53, -4, 4,
1382 6, 13, -53, -52, -54, 55, 54, -55, -56, -2, 2, -8, 56, 1, -3, -1,
1383 2, 58, 3, 8, -2, 57, -58, -60, -59, -57, -3, 60, 59, -14, 3, 14}
1389 {1, 1, 0, 2, 2, 1, 1, 3, 3, 4, 4, 5, 5, 1, 1, 6,
1390 6, 2, 2, 7, 7, 8, 8, 1, 1, 3, 3, 9, 9, 10, 10, 1,
1391 1, 2, 2, 4, 4, 11, 0, 11, 12, 12, 13, 13, 1, 1, 5, 5,
1392 14, 14, 15, 16, 15, 16, 3, 3, 1, 6, 1, 6, 2, 2, 7, 7,
1393 8, 8, 17, 17, 1, 1, 4, 4, 18, 18, 2, 2, 1, 19, 1, 20,
1394 19, 20, 21, 21, 3, 3, 22, 22, 5, 5, 24, 1, 1, 23, 9, 23,
1395 24, 9, 2, 2, 10, 1, 1, 10, 6, 6, 25, 4, 4, 25, 7, 7,
1396 26, 8, 1, 8, 3, 1, 26, 3, 11, 11, 27, 27, 2, 28, 1, 2,
1397 28, 1, 12, 12, 5, 5, 29, 13, 13, 29, 32, 1, 1, 33, 31, 30,
1398 32, 4, 30, 33, 4, 31, 3, 14, 1, 1, 3, 34, 34, 2, 2, 14,
1399 6, 6, 35, 36, 35, 36, 1, 15, 1, 16, 16, 15, 7, 9, 7, 9,
1400 37, 8, 8, 37, 1, 1, 39, 2, 38, 39, 2, 40, 5, 38, 40, 5,
1401 3, 3, 4, 4, 10, 10, 1, 1, 1, 1, 41, 2, 41, 2, 6, 6,
1402 1, 1, 11, 42, 11, 43, 3, 42, 3, 17, 4, 43, 1, 17, 7, 1,
1403 8, 44, 4, 7, 44, 5, 8, 2, 5, 1, 2, 48, 45, 1, 12, 45,
1404 12, 48, 13, 13, 1, 9, 9, 46, 1, 46, 47, 47, 49, 18, 18, 49},
1407 { 1, -1, 0, 1, -1, 2, -2, 1, -1, 1, -1, 1, -1, 3, -3, 1,
1408 -1, -2, 2, 1, -1, 1, -1, 4, -4, -2, 2, 1, -1, 1, -1, 5,
1409 -5, -3, 3, 2, -2, 1, 0, -1, 1, -1, 1, -1, 6, -6, 2, -2,
1410 1, -1, 1, 1, -1, -1, -3, 3, 7, 2, -7, -2, -4, 4, 2, -2,
1411 2, -2, 1, -1, 8, -8, 3, -3, 1, -1, -5, 5, 9, 1, -9, 1,
1412 -1, -1, 1, -1, -4, 4, 1, -1, 3, -3, 1, -10, 10, 1, 2, -1,
1413 -1, -2, 6, -6, 2, 11, -11, -2, 3, -3, 1, -4, 4, -1, 3, -3,
1414 1, 3, 12, -3, -5, -12, -1, 5, 2, -2, 1, -1, -7, 1, 13, 7,
1415 -1, -13, 2, -2, 4, -4, 1, 2, -2, -1, 1, 14, -14, 1, 1, 1,
1416 -1, -5, -1, -1, 5, -1, -6, 2, -15, 15, 6, 1, -1, -8, 8, -2,
1417 -4, 4, 1, 1, -1, -1, 16, 2, -16, -2, 2, -2, 4, 3, -4, -3,
1418 -1, -4, 4, 1, -17, 17, -1, -9, 1, 1, 9, 1, -5, -1, -1, 5,
1419 -7, 7, 6, -6, 3, -3, 18, -18, 19, -19, 1, -10, -1, 10, -5, 5,
1420 20, -20, -3, 1, 3, 1, 8, -1, -8, 2, 7, -1, -21, -2, 5, 21,
1421 5, -1, -7, -5, 1, -6, -5, -11, 6, 22, 11, 1, 1, -22, -3, -1,
1422 3, -1, 3, -3, -23, 4, -4, 1, 23, -1, 1, -1, 1, -2, 2, -1}
1428 {1, 1, 1, 1, 0, 2, 2, 1, 1, 3, 3, 0, 1, 1, 2, 2,
1429 4, 4, 1, 1, 5, 5, 1, 1, 2, 2, 3, 3, 6, 6, 1, 1,
1430 7, 7, 8, 1, 8, 2, 2, 1, 4, 4, 1, 3, 1, 3, 9, 9,
1431 2, 2, 1, 5, 1, 5, 10, 10, 1, 1, 11, 11, 3, 6, 3, 4,
1432 4, 6, 2, 2, 1, 12, 1, 12, 7, 13, 7, 13, 1, 1, 8, 8,
1433 2, 2, 14, 14, 16, 15, 16, 5, 5, 1, 3, 15, 1, 3, 4, 4,
1434 1, 1, 17, 17, 2, 2, 6, 6, 1, 18, 1, 18, 22, 21, 22, 21,
1435 25, 24, 25, 19, 9, 20, 9, 23, 19, 24, 20, 3, 23, 7, 3, 1,
1436 1, 7, 28, 26, 29, 5, 28, 26, 5, 8, 29, 4, 8, 27, 2, 2,
1437 4, 27, 1, 1, 10, 36, 10, 33, 33, 36, 30, 1, 32, 32, 1, 30,
1438 6, 31, 31, 35, 3, 6, 11, 11, 3, 2, 35, 2, 34, 1, 34, 1,
1439 37, 37, 12, 7, 12, 5, 41, 5, 4, 7, 1, 8, 13, 4, 1, 41,
1440 13, 38, 8, 38, 9, 1, 40, 40, 9, 1, 39, 2, 2, 49, 39, 42,
1441 3, 3, 14, 16, 49, 14, 16, 42, 43, 43, 6, 6, 15, 1, 1, 15,
1442 44, 44, 1, 1, 50, 48, 4, 5, 4, 7, 5, 2, 10, 10, 48, 7,
1443 50, 45, 2, 1, 45, 8, 8, 1, 46, 46, 3, 47, 47, 3, 1, 1},
1446 { 1, -1, 2, -2, 0, 1, -1, 3, -3, 1, -1, 0, 4, -4, 2, -2,
1447 1, -1, 5, -5, 1, -1, 6, -6, 3, -3, 2, -2, 1, -1, 7, -7,
1448 1, -1, 1, 8, -1, 4, -4, -8, 2, -2, 9, 3, -9, -3, 1, -1,
1449 5, -5, 10, 2, -10, -2, 1, -1, 11, -11, 1, -1, -4, 2, 4, 3,
1450 -3, -2, 6, -6, 12, 1, -12, -1, 2, 1, -2, -1, 13, -13, 2, -2,
1451 7, -7, 1, -1, 1, 1, -1, 3, -3, 14, 5, -1, -14, -5, 4, -4,
1452 15, -15, 1, -1, 8, -8, -3, 3, 16, 1, -16, -1, 1, 1, -1, -1,
1453 1, 1, -1, 1, 2, 1, -2, 1, -1, -1, -1, 6, -1, 3, -6, 17,
1454 -17, -3, 1, 1, 1, 4, -1, -1, -4, 3, -1, 5, -3, -1, -9, 9,
1455 -5, 1, 18, -18, 2, 1, -2, 1, -1, -1, 1, 19, -1, 1, -19, -1,
1456 4, 1, -1, 1, 7, -4, -2, 2, -7, 10, -1, -10, 1, 20, -1, -20,
1457 1, -1, 2, 4, -2, 5, 1, -5, 6, -4, 21, 4, 2, -6, -21, -1,
1458 -2, 1, -4, -1, -3, 22, -1, 1, 3, -22, -1, 11, -11, 1, 1, 1,
1459 8, -8, 2, 2, -1, -2, -2, -1, 1, -1, -5, 5, 2, 23, -23, -2,
1460 1, -1, 24, -24, -1, -1, 7, 6, -7, 5, -6, 12, -3, 3, 1, -5,
1461 1, 1, -12, 25, -1, -5, 5, -25, -1, 1, 9, 1, -1, -9, 26, -26}