2 * common functions for Indeo Video Interactive codecs (Indeo4 and Indeo5)
4 * Copyright (c) 2009 Maxim Poliakovski
6 * This file is part of FFmpeg.
8 * FFmpeg is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU Lesser General Public
10 * License as published by the Free Software Foundation; either
11 * version 2.1 of the License, or (at your option) any later version.
13 * FFmpeg is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * Lesser General Public License for more details.
18 * You should have received a copy of the GNU Lesser General Public
19 * License along with FFmpeg; if not, write to the Free Software
20 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
25 * This file contains functions and data shared by both Indeo4 and
29 #define BITSTREAM_READER_LE
30 #include "libavutil/attributes.h"
35 #include "ivi_common.h"
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 av_assert0(offs >= 0 && ref_offs >= 0 && band->ref_buf);
83 av_assert0(buf_size - min_size >= offs);
84 av_assert0(buf_size - min_size - ref_size >= ref_offs);
86 mc(band->buf + offs, band->ref_buf + ref_offs, band->pitch, mc_type);
92 * Reverse "nbits" bits of the value "val" and return the result
93 * in the least significant bits.
95 static uint16_t inv_bits(uint16_t val, int nbits)
100 res = ff_reverse[val] >> (8 - nbits);
102 res = ((ff_reverse[val & 0xFF] << 8) +
103 (ff_reverse[val >> 8])) >> (16 - nbits);
109 * Generate a huffman codebook from the given descriptor
110 * and convert it into the FFmpeg VLC table.
112 * @param[in] cb pointer to codebook descriptor
113 * @param[out] vlc where to place the generated VLC table
114 * @param[in] flag flag: 1 - for static or 0 for dynamic tables
115 * @return result code: 0 - OK, -1 = error (invalid codebook descriptor)
117 static int ivi_create_huff_from_desc(const IVIHuffDesc *cb, VLC *vlc, int flag)
119 int pos, i, j, codes_per_row, prefix, not_last_row;
120 uint16_t codewords[256]; /* FIXME: move this temporal storage out? */
123 pos = 0; /* current position = 0 */
125 for (i = 0; i < cb->num_rows; i++) {
126 codes_per_row = 1 << cb->xbits[i];
127 not_last_row = (i != cb->num_rows - 1);
128 prefix = ((1 << i) - 1) << (cb->xbits[i] + not_last_row);
130 for (j = 0; j < codes_per_row; j++) {
131 if (pos >= 256) /* Some Indeo5 codebooks can have more than 256 */
132 break; /* elements, but only 256 codes are allowed! */
134 bits[pos] = i + cb->xbits[i] + not_last_row;
135 if (bits[pos] > IVI_VLC_BITS)
136 return AVERROR_INVALIDDATA; /* invalid descriptor */
138 codewords[pos] = inv_bits((prefix | j), bits[pos]);
146 /* number of codewords = pos */
147 return init_vlc(vlc, IVI_VLC_BITS, pos, bits, 1, 1, codewords, 2, 2,
148 (flag ? INIT_VLC_USE_NEW_STATIC : 0) | INIT_VLC_LE);
151 av_cold void ff_ivi_init_static_vlc(void)
154 static VLC_TYPE table_data[8192 * 16][2];
155 static int initialized_vlcs = 0;
157 if (initialized_vlcs)
159 for (i = 0; i < 8; i++) {
160 ivi_mb_vlc_tabs[i].table = table_data + i * 2 * 8192;
161 ivi_mb_vlc_tabs[i].table_allocated = 8192;
162 ivi_create_huff_from_desc(&ivi_mb_huff_desc[i],
163 &ivi_mb_vlc_tabs[i], 1);
164 ivi_blk_vlc_tabs[i].table = table_data + (i * 2 + 1) * 8192;
165 ivi_blk_vlc_tabs[i].table_allocated = 8192;
166 ivi_create_huff_from_desc(&ivi_blk_huff_desc[i],
167 &ivi_blk_vlc_tabs[i], 1);
169 initialized_vlcs = 1;
173 * Copy huffman codebook descriptors.
175 * @param[out] dst ptr to the destination descriptor
176 * @param[in] src ptr to the source descriptor
178 static void ivi_huff_desc_copy(IVIHuffDesc *dst, const IVIHuffDesc *src)
180 dst->num_rows = src->num_rows;
181 memcpy(dst->xbits, src->xbits, src->num_rows);
185 * Compare two huffman codebook descriptors.
187 * @param[in] desc1 ptr to the 1st descriptor to compare
188 * @param[in] desc2 ptr to the 2nd descriptor to compare
189 * @return comparison result: 0 - equal, 1 - not equal
191 static int ivi_huff_desc_cmp(const IVIHuffDesc *desc1,
192 const IVIHuffDesc *desc2)
194 return desc1->num_rows != desc2->num_rows ||
195 memcmp(desc1->xbits, desc2->xbits, desc1->num_rows);
198 int ff_ivi_dec_huff_desc(GetBitContext *gb, int desc_coded, int which_tab,
199 IVIHuffTab *huff_tab, AVCodecContext *avctx)
202 IVIHuffDesc new_huff;
205 /* select default table */
206 huff_tab->tab = (which_tab) ? &ivi_blk_vlc_tabs[7]
207 : &ivi_mb_vlc_tabs [7];
211 huff_tab->tab_sel = get_bits(gb, 3);
212 if (huff_tab->tab_sel == 7) {
213 /* custom huffman table (explicitly encoded) */
214 new_huff.num_rows = get_bits(gb, 4);
215 if (!new_huff.num_rows) {
216 av_log(avctx, AV_LOG_ERROR, "Empty custom Huffman table!\n");
217 return AVERROR_INVALIDDATA;
220 for (i = 0; i < new_huff.num_rows; i++)
221 new_huff.xbits[i] = get_bits(gb, 4);
223 /* Have we got the same custom table? Rebuild if not. */
224 if (ivi_huff_desc_cmp(&new_huff, &huff_tab->cust_desc) || !huff_tab->cust_tab.table) {
225 ivi_huff_desc_copy(&huff_tab->cust_desc, &new_huff);
227 if (huff_tab->cust_tab.table)
228 ff_free_vlc(&huff_tab->cust_tab);
229 result = ivi_create_huff_from_desc(&huff_tab->cust_desc,
230 &huff_tab->cust_tab, 0);
232 // reset faulty description
233 huff_tab->cust_desc.num_rows = 0;
234 av_log(avctx, AV_LOG_ERROR,
235 "Error while initializing custom vlc table!\n");
239 huff_tab->tab = &huff_tab->cust_tab;
241 /* select one of predefined tables */
242 huff_tab->tab = (which_tab) ? &ivi_blk_vlc_tabs[huff_tab->tab_sel]
243 : &ivi_mb_vlc_tabs [huff_tab->tab_sel];
250 * Free planes, bands and macroblocks buffers.
252 * @param[in] planes pointer to the array of the plane descriptors
254 static av_cold void ivi_free_buffers(IVIPlaneDesc *planes)
258 for (p = 0; p < 3; p++) {
260 for (b = 0; b < planes[p].num_bands; b++) {
261 av_freep(&planes[p].bands[b].bufs[0]);
262 av_freep(&planes[p].bands[b].bufs[1]);
263 av_freep(&planes[p].bands[b].bufs[2]);
265 if (planes[p].bands[b].blk_vlc.cust_tab.table)
266 ff_free_vlc(&planes[p].bands[b].blk_vlc.cust_tab);
267 for (t = 0; t < planes[p].bands[b].num_tiles; t++)
268 av_freep(&planes[p].bands[b].tiles[t].mbs);
269 av_freep(&planes[p].bands[b].tiles);
271 av_freep(&planes[p].bands);
272 planes[p].num_bands = 0;
276 av_cold int ff_ivi_init_planes(IVIPlaneDesc *planes, const IVIPicConfig *cfg)
279 uint32_t b_width, b_height, align_fac, width_aligned,
280 height_aligned, buf_size;
283 ivi_free_buffers(planes);
285 if (cfg->pic_width < 1 || cfg->pic_height < 1 ||
286 cfg->luma_bands < 1 || cfg->chroma_bands < 1)
287 return AVERROR_INVALIDDATA;
289 /* fill in the descriptor of the luminance plane */
290 planes[0].width = cfg->pic_width;
291 planes[0].height = cfg->pic_height;
292 planes[0].num_bands = cfg->luma_bands;
294 /* fill in the descriptors of the chrominance planes */
295 planes[1].width = planes[2].width = (cfg->pic_width + 3) >> 2;
296 planes[1].height = planes[2].height = (cfg->pic_height + 3) >> 2;
297 planes[1].num_bands = planes[2].num_bands = cfg->chroma_bands;
299 for (p = 0; p < 3; p++) {
300 planes[p].bands = av_mallocz(planes[p].num_bands * sizeof(IVIBandDesc));
301 if (!planes[p].bands)
302 return AVERROR(ENOMEM);
304 /* select band dimensions: if there is only one band then it
305 * has the full size, if there are several bands each of them
306 * has only half size */
307 b_width = planes[p].num_bands == 1 ? planes[p].width
308 : (planes[p].width + 1) >> 1;
309 b_height = planes[p].num_bands == 1 ? planes[p].height
310 : (planes[p].height + 1) >> 1;
312 /* luma band buffers will be aligned on 16x16 (max macroblock size) */
313 /* chroma band buffers will be aligned on 8x8 (max macroblock size) */
314 align_fac = p ? 8 : 16;
315 width_aligned = FFALIGN(b_width , align_fac);
316 height_aligned = FFALIGN(b_height, align_fac);
317 buf_size = width_aligned * height_aligned * sizeof(int16_t);
319 for (b = 0; b < planes[p].num_bands; b++) {
320 band = &planes[p].bands[b]; /* select appropriate plane/band */
323 band->width = b_width;
324 band->height = b_height;
325 band->pitch = width_aligned;
326 band->aheight = height_aligned;
327 band->bufs[0] = av_mallocz(buf_size);
328 band->bufs[1] = av_mallocz(buf_size);
329 band->bufsize = buf_size/2;
330 if (!band->bufs[0] || !band->bufs[1])
331 return AVERROR(ENOMEM);
333 /* allocate the 3rd band buffer for scalability mode */
334 if (cfg->luma_bands > 1) {
335 band->bufs[2] = av_mallocz(buf_size);
337 return AVERROR(ENOMEM);
339 /* reset custom vlc */
340 planes[p].bands[0].blk_vlc.cust_desc.num_rows = 0;
347 static int ivi_init_tiles(IVIBandDesc *band, IVITile *ref_tile,
348 int p, int b, int t_height, int t_width)
351 IVITile *tile = band->tiles;
353 for (y = 0; y < band->height; y += t_height) {
354 for (x = 0; x < band->width; x += t_width) {
357 tile->mb_size = band->mb_size;
358 tile->width = FFMIN(band->width - x, t_width);
359 tile->height = FFMIN(band->height - y, t_height);
360 tile->is_empty = tile->data_size = 0;
361 /* calculate number of macroblocks */
362 tile->num_MBs = IVI_MBs_PER_TILE(tile->width, tile->height,
365 av_freep(&tile->mbs);
366 tile->mbs = av_malloc(tile->num_MBs * sizeof(IVIMbInfo));
368 return AVERROR(ENOMEM);
372 if (tile->num_MBs != ref_tile->num_MBs) {
373 av_log(NULL, AV_LOG_DEBUG, "ref_tile mismatch\n");
374 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) {
400 if(t_width<=0 || t_height<=0)
401 return AVERROR(EINVAL);
403 for (b = 0; b < planes[p].num_bands; b++) {
404 band = &planes[p].bands[b];
405 x_tiles = IVI_NUM_TILES(band->width, t_width);
406 y_tiles = IVI_NUM_TILES(band->height, t_height);
407 band->num_tiles = x_tiles * y_tiles;
409 av_freep(&band->tiles);
410 band->tiles = av_mallocz(band->num_tiles * sizeof(IVITile));
412 return AVERROR(ENOMEM);
414 /* use the first luma band as reference for motion vectors
416 ret = ivi_init_tiles(band, planes[0].bands[0].tiles,
417 p, b, t_height, t_width);
427 * Decode size of the tile data.
428 * The size is stored as a variable-length field having the following format:
429 * if (tile_data_size < 255) than this field is only one byte long
430 * if (tile_data_size >= 255) than this field four is byte long: 0xFF X1 X2 X3
431 * where X1-X3 is size of the tile data
433 * @param[in,out] gb the GetBit context
434 * @return size of the tile data in bytes
436 static int ivi_dec_tile_data_size(GetBitContext *gb)
442 len = get_bits(gb, 8);
444 len = get_bits_long(gb, 24);
447 /* align the bitstream reader on the byte boundary */
453 static int ivi_dc_transform(IVIBandDesc *band, int *prev_dc, int buf_offs,
456 int buf_size = band->pitch * band->aheight - buf_offs;
457 int min_size = (blk_size - 1) * band->pitch + blk_size;
459 if (min_size > buf_size)
460 return AVERROR_INVALIDDATA;
462 band->dc_transform(prev_dc, band->buf + buf_offs,
463 band->pitch, blk_size);
468 static int ivi_decode_coded_blocks(GetBitContext *gb, IVIBandDesc *band,
469 ivi_mc_func mc, int mv_x, int mv_y,
470 int *prev_dc, int is_intra, int mc_type,
471 uint32_t quant, int offs,
472 AVCodecContext *avctx)
474 const uint16_t *base_tab = is_intra ? band->intra_base : band->inter_base;
475 RVMapDesc *rvmap = band->rv_map;
476 uint8_t col_flags[8];
478 uint32_t sym = 0, lo, hi, q;
480 int blk_size = band->blk_size;
481 int num_coeffs = blk_size * blk_size;
482 int col_mask = blk_size - 1;
484 int min_size = band->pitch * (band->transform_size - 1) +
485 band->transform_size;
486 int buf_size = band->pitch * band->aheight - offs;
488 if (min_size > buf_size)
489 return AVERROR_INVALIDDATA;
492 av_log(avctx, AV_LOG_ERROR, "Scan pattern is not set.\n");
493 return AVERROR_INVALIDDATA;
496 /* zero transform vector */
497 memset(trvec, 0, num_coeffs * sizeof(trvec[0]));
498 /* zero column flags */
499 memset(col_flags, 0, sizeof(col_flags));
500 while (scan_pos <= num_coeffs) {
501 sym = get_vlc2(gb, band->blk_vlc.tab->table,
503 if (sym == rvmap->eob_sym)
504 break; /* End of block */
506 /* Escape - run/val explicitly coded using 3 vlc codes */
507 if (sym == rvmap->esc_sym) {
508 run = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1) + 1;
509 lo = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
510 hi = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
511 /* merge them and convert into signed val */
512 val = IVI_TOSIGNED((hi << 6) | lo);
515 av_log(avctx, AV_LOG_ERROR, "Invalid sym encountered: %d.\n", sym);
516 return AVERROR_INVALIDDATA;
518 run = rvmap->runtab[sym];
519 val = rvmap->valtab[sym];
522 /* de-zigzag and dequantize */
524 if (scan_pos >= num_coeffs || scan_pos < 0)
526 pos = band->scan[scan_pos];
529 av_dlog(avctx, "Val = 0 encountered!\n");
531 q = (base_tab[pos] * quant) >> 9;
533 val = val * q + FFSIGN(val) * (((q ^ 1) - 1) >> 1);
535 /* track columns containing non-zero coeffs */
536 col_flags[pos & col_mask] |= !!val;
539 if (scan_pos < 0 || scan_pos >= num_coeffs && sym != rvmap->eob_sym)
540 return AVERROR_INVALIDDATA; /* corrupt block data */
542 /* undoing DC coeff prediction for intra-blocks */
543 if (is_intra && band->is_2d_trans) {
544 *prev_dc += trvec[0];
546 col_flags[0] |= !!*prev_dc;
549 if(band->transform_size > band->blk_size){
550 av_log(NULL, AV_LOG_ERROR, "Too large transform\n");
551 return AVERROR_INVALIDDATA;
554 /* apply inverse transform */
555 band->inv_transform(trvec, band->buf + offs,
556 band->pitch, col_flags);
558 /* apply motion compensation */
560 return ivi_mc(band, mc, offs, mv_x, mv_y, mc_type);
566 * extract huffman-coded transform coefficients from the bitstream,
567 * dequantize them, apply inverse transform and motion compensation
568 * in order to reconstruct the picture.
570 * @param[in,out] gb the GetBit context
571 * @param[in] band pointer to the band descriptor
572 * @param[in] tile pointer to the tile descriptor
573 * @return result code: 0 - OK, -1 = error (corrupted blocks data)
575 static int ivi_decode_blocks(GetBitContext *gb, IVIBandDesc *band,
576 IVITile *tile, AVCodecContext *avctx)
578 int mbn, blk, num_blocks, blk_size, ret, is_intra, mc_type = 0;
579 int mv_x = 0, mv_y = 0;
581 uint32_t cbp, quant, buf_offs;
583 ivi_mc_func mc_with_delta_func, mc_no_delta_func;
584 const uint8_t *scale_tab;
586 /* init intra prediction for the DC coefficient */
588 blk_size = band->blk_size;
589 /* number of blocks per mb */
590 num_blocks = (band->mb_size != blk_size) ? 4 : 1;
592 mc_with_delta_func = ff_ivi_mc_8x8_delta;
593 mc_no_delta_func = ff_ivi_mc_8x8_no_delta;
595 mc_with_delta_func = ff_ivi_mc_4x4_delta;
596 mc_no_delta_func = ff_ivi_mc_4x4_no_delta;
599 for (mbn = 0, mb = tile->mbs; mbn < tile->num_MBs; mb++, mbn++) {
600 is_intra = !mb->type;
602 buf_offs = mb->buf_offs;
604 quant = band->glob_quant + mb->q_delta;
605 if (avctx->codec_id == AV_CODEC_ID_INDEO4)
606 quant = av_clip(quant, 0, 31);
608 quant = av_clip(quant, 0, 23);
610 scale_tab = is_intra ? band->intra_scale : band->inter_scale;
612 quant = scale_tab[quant];
617 if (band->is_halfpel) {
618 mc_type = ((mv_y & 1) << 1) | (mv_x & 1);
620 mv_y >>= 1; /* convert halfpel vectors into fullpel ones */
623 int dmv_x, dmv_y, cx, cy;
625 dmv_x = mb->mv_x >> band->is_halfpel;
626 dmv_y = mb->mv_y >> band->is_halfpel;
627 cx = mb->mv_x & band->is_halfpel;
628 cy = mb->mv_y & band->is_halfpel;
630 if (mb->xpos + dmv_x < 0 ||
631 mb->xpos + dmv_x + band->mb_size + cx > band->pitch ||
632 mb->ypos + dmv_y < 0 ||
633 mb->ypos + dmv_y + band->mb_size + cy > band->aheight) {
634 return AVERROR_INVALIDDATA;
639 for (blk = 0; blk < num_blocks; blk++) {
640 /* adjust block position in the buffer according to its number */
642 buf_offs += blk_size;
643 } else if (blk == 2) {
644 buf_offs -= blk_size;
645 buf_offs += blk_size * band->pitch;
648 if (cbp & 1) { /* block coded ? */
649 ret = ivi_decode_coded_blocks(gb, band, mc_with_delta_func,
650 mv_x, mv_y, &prev_dc, is_intra,
651 mc_type, quant, buf_offs, avctx);
655 /* block not coded */
656 /* for intra blocks apply the dc slant transform */
657 /* for inter - perform the motion compensation without delta */
659 ret = ivi_dc_transform(band, &prev_dc, buf_offs, blk_size);
663 ret = ivi_mc(band, mc_no_delta_func, buf_offs,
664 mv_x, mv_y, mc_type);
680 * Handle empty tiles by performing data copying and motion
681 * compensation respectively.
683 * @param[in] avctx ptr to the AVCodecContext
684 * @param[in] band pointer to the band descriptor
685 * @param[in] tile pointer to the tile descriptor
686 * @param[in] mv_scale scaling factor for motion vectors
688 static int ivi_process_empty_tile(AVCodecContext *avctx, IVIBandDesc *band,
689 IVITile *tile, int32_t mv_scale)
691 int x, y, need_mc, mbn, blk, num_blocks, mv_x, mv_y, mc_type;
692 int offs, mb_offset, row_offset, ret;
693 IVIMbInfo *mb, *ref_mb;
696 ivi_mc_func mc_no_delta_func;
698 if (tile->num_MBs != IVI_MBs_PER_TILE(tile->width, tile->height, band->mb_size)) {
699 av_log(avctx, AV_LOG_ERROR, "Allocated tile size %d mismatches "
700 "parameters %d in ivi_process_empty_tile()\n",
701 tile->num_MBs, IVI_MBs_PER_TILE(tile->width, tile->height, band->mb_size));
702 return AVERROR_INVALIDDATA;
705 offs = tile->ypos * band->pitch + tile->xpos;
707 ref_mb = tile->ref_mbs;
708 row_offset = band->mb_size * band->pitch;
709 need_mc = 0; /* reset the mc tracking flag */
711 for (y = tile->ypos; y < (tile->ypos + tile->height); y += band->mb_size) {
714 for (x = tile->xpos; x < (tile->xpos + tile->width); x += band->mb_size) {
717 mb->buf_offs = mb_offset;
719 mb->type = 1; /* set the macroblocks type = INTER */
720 mb->cbp = 0; /* all blocks are empty */
722 if (!band->qdelta_present && !band->plane && !band->band_num) {
723 mb->q_delta = band->glob_quant;
728 if (band->inherit_qdelta && ref_mb)
729 mb->q_delta = ref_mb->q_delta;
731 if (band->inherit_mv && ref_mb) {
732 /* motion vector inheritance */
734 mb->mv_x = ivi_scale_mv(ref_mb->mv_x, mv_scale);
735 mb->mv_y = ivi_scale_mv(ref_mb->mv_y, mv_scale);
737 mb->mv_x = ref_mb->mv_x;
738 mb->mv_y = ref_mb->mv_y;
740 need_mc |= mb->mv_x || mb->mv_y; /* tracking non-zero motion vectors */
742 int dmv_x, dmv_y, cx, cy;
744 dmv_x = mb->mv_x >> band->is_halfpel;
745 dmv_y = mb->mv_y >> band->is_halfpel;
746 cx = mb->mv_x & band->is_halfpel;
747 cy = mb->mv_y & band->is_halfpel;
749 if ( mb->xpos + dmv_x < 0
750 || mb->xpos + dmv_x + band->mb_size + cx > band->pitch
751 || mb->ypos + dmv_y < 0
752 || mb->ypos + dmv_y + band->mb_size + cy > band->aheight) {
753 av_log(avctx, AV_LOG_ERROR, "MV out of bounds\n");
754 return AVERROR_INVALIDDATA;
762 mb_offset += band->mb_size;
767 if (band->inherit_mv && need_mc) { /* apply motion compensation if there is at least one non-zero motion vector */
768 num_blocks = (band->mb_size != band->blk_size) ? 4 : 1; /* number of blocks per mb */
769 mc_no_delta_func = (band->blk_size == 8) ? ff_ivi_mc_8x8_no_delta
770 : ff_ivi_mc_4x4_no_delta;
772 for (mbn = 0, mb = tile->mbs; mbn < tile->num_MBs; mb++, mbn++) {
775 if (!band->is_halfpel) {
776 mc_type = 0; /* we have only fullpel vectors */
778 mc_type = ((mv_y & 1) << 1) | (mv_x & 1);
780 mv_y >>= 1; /* convert halfpel vectors into fullpel ones */
783 for (blk = 0; blk < num_blocks; blk++) {
784 /* adjust block position in the buffer according with its number */
785 offs = mb->buf_offs + band->blk_size * ((blk & 1) + !!(blk & 2) * band->pitch);
786 ret = ivi_mc(band, mc_no_delta_func, offs,
787 mv_x, mv_y, mc_type);
793 /* copy data from the reference tile into the current one */
794 src = band->ref_buf + tile->ypos * band->pitch + tile->xpos;
795 dst = band->buf + tile->ypos * band->pitch + tile->xpos;
796 for (y = 0; y < tile->height; y++) {
797 memcpy(dst, src, tile->width*sizeof(band->buf[0]));
808 static uint16_t ivi_calc_band_checksum(IVIBandDesc *band)
811 int16_t *src, checksum;
816 for (y = 0; y < band->height; src += band->pitch, y++)
817 for (x = 0; x < band->width; x++)
825 * Convert and output the current plane.
826 * This conversion is done by adding back the bias value of 128
827 * (subtracted in the encoder) and clipping the result.
829 * @param[in] plane pointer to the descriptor of the plane being processed
830 * @param[out] dst pointer to the buffer receiving converted pixels
831 * @param[in] dst_pitch pitch for moving to the next y line
833 static void ivi_output_plane(IVIPlaneDesc *plane, uint8_t *dst, int dst_pitch)
836 const int16_t *src = plane->bands[0].buf;
837 uint32_t pitch = plane->bands[0].pitch;
842 for (y = 0; y < plane->height; y++) {
843 for (x = 0; x < plane->width; x++)
844 dst[x] = av_clip_uint8(src[x] + 128);
851 * Decode an Indeo 4 or 5 band.
853 * @param[in,out] ctx ptr to the decoder context
854 * @param[in,out] band ptr to the band descriptor
855 * @param[in] avctx ptr to the AVCodecContext
856 * @return result code: 0 = OK, -1 = error
858 static int decode_band(IVI45DecContext *ctx,
859 IVIBandDesc *band, AVCodecContext *avctx)
861 int result, i, t, idx1, idx2, pos;
864 band->buf = band->bufs[ctx->dst_buf];
866 av_log(avctx, AV_LOG_ERROR, "Band buffer points to no data!\n");
867 return AVERROR_INVALIDDATA;
869 band->ref_buf = band->bufs[ctx->ref_buf];
870 band->data_ptr = ctx->frame_data + (get_bits_count(&ctx->gb) >> 3);
872 result = ctx->decode_band_hdr(ctx, band, avctx);
874 av_log(avctx, AV_LOG_ERROR, "Error while decoding band header: %d\n",
879 if (band->is_empty) {
880 av_log(avctx, AV_LOG_ERROR, "Empty band encountered!\n");
881 return AVERROR_INVALIDDATA;
884 band->rv_map = &ctx->rvmap_tabs[band->rvmap_sel];
886 /* apply corrections to the selected rvmap table if present */
887 for (i = 0; i < band->num_corr; i++) {
888 idx1 = band->corr[i * 2];
889 idx2 = band->corr[i * 2 + 1];
890 FFSWAP(uint8_t, band->rv_map->runtab[idx1], band->rv_map->runtab[idx2]);
891 FFSWAP(int16_t, band->rv_map->valtab[idx1], band->rv_map->valtab[idx2]);
892 if (idx1 == band->rv_map->eob_sym || idx2 == band->rv_map->eob_sym)
893 band->rv_map->eob_sym ^= idx1 ^ idx2;
894 if (idx1 == band->rv_map->esc_sym || idx2 == band->rv_map->esc_sym)
895 band->rv_map->esc_sym ^= idx1 ^ idx2;
898 pos = get_bits_count(&ctx->gb);
900 for (t = 0; t < band->num_tiles; t++) {
901 tile = &band->tiles[t];
903 if (tile->mb_size != band->mb_size) {
904 av_log(avctx, AV_LOG_ERROR, "MB sizes mismatch: %d vs. %d\n",
905 band->mb_size, tile->mb_size);
906 return AVERROR_INVALIDDATA;
908 tile->is_empty = get_bits1(&ctx->gb);
909 if (tile->is_empty) {
910 result = ivi_process_empty_tile(avctx, band, tile,
911 (ctx->planes[0].bands[0].mb_size >> 3) - (band->mb_size >> 3));
914 av_dlog(avctx, "Empty tile encountered!\n");
916 tile->data_size = ivi_dec_tile_data_size(&ctx->gb);
917 if (!tile->data_size) {
918 av_log(avctx, AV_LOG_ERROR, "Tile data size is zero!\n");
919 result = AVERROR_INVALIDDATA;
923 result = ctx->decode_mb_info(ctx, band, tile, avctx);
927 result = ivi_decode_blocks(&ctx->gb, band, tile, avctx);
929 av_log(avctx, AV_LOG_ERROR,
930 "Corrupted tile data encountered!\n");
934 if (((get_bits_count(&ctx->gb) - pos) >> 3) != tile->data_size) {
935 av_log(avctx, AV_LOG_ERROR,
936 "Tile data_size mismatch!\n");
937 result = AVERROR_INVALIDDATA;
941 pos += tile->data_size << 3; // skip to next tile
945 /* restore the selected rvmap table by applying its corrections in
947 for (i = band->num_corr-1; i >= 0; i--) {
948 idx1 = band->corr[i*2];
949 idx2 = band->corr[i*2+1];
950 FFSWAP(uint8_t, band->rv_map->runtab[idx1], band->rv_map->runtab[idx2]);
951 FFSWAP(int16_t, band->rv_map->valtab[idx1], band->rv_map->valtab[idx2]);
952 if (idx1 == band->rv_map->eob_sym || idx2 == band->rv_map->eob_sym)
953 band->rv_map->eob_sym ^= idx1 ^ idx2;
954 if (idx1 == band->rv_map->esc_sym || idx2 == band->rv_map->esc_sym)
955 band->rv_map->esc_sym ^= idx1 ^ idx2;
959 if (band->checksum_present) {
960 uint16_t chksum = ivi_calc_band_checksum(band);
961 if (chksum != band->checksum) {
962 av_log(avctx, AV_LOG_ERROR,
963 "Band checksum mismatch! Plane %d, band %d, "
964 "received: %x, calculated: %x\n",
965 band->plane, band->band_num, band->checksum, chksum);
970 align_get_bits(&ctx->gb);
975 int ff_ivi_decode_frame(AVCodecContext *avctx, void *data, int *got_frame,
978 IVI45DecContext *ctx = avctx->priv_data;
979 const uint8_t *buf = avpkt->data;
980 AVFrame *frame = data;
981 int buf_size = avpkt->size;
984 init_get_bits(&ctx->gb, buf, buf_size * 8);
985 ctx->frame_data = buf;
986 ctx->frame_size = buf_size;
988 result = ctx->decode_pic_hdr(ctx, avctx);
990 av_log(avctx, AV_LOG_ERROR,
991 "Error while decoding picture header: %d\n", result);
994 if (ctx->gop_invalid)
995 return AVERROR_INVALIDDATA;
997 if (ctx->gop_flags & IVI5_IS_PROTECTED) {
998 avpriv_report_missing_feature(avctx, "Password-protected clip!\n");
999 return AVERROR_PATCHWELCOME;
1002 ctx->switch_buffers(ctx);
1006 if (ctx->is_nonnull_frame(ctx)) {
1007 ctx->buf_invalid[ctx->dst_buf] = 1;
1008 for (p = 0; p < 3; p++) {
1009 for (b = 0; b < ctx->planes[p].num_bands; b++) {
1010 result = decode_band(ctx, &ctx->planes[p].bands[b], avctx);
1012 av_log(avctx, AV_LOG_ERROR,
1013 "Error while decoding band: %d, plane: %d\n", b, p);
1018 ctx->buf_invalid[ctx->dst_buf] = 0;
1020 if (ctx->is_scalable)
1021 return AVERROR_INVALIDDATA;
1023 for (p = 0; p < 3; p++) {
1024 if (!ctx->planes[p].bands[0].buf)
1025 return AVERROR_INVALIDDATA;
1028 if (ctx->buf_invalid[ctx->dst_buf])
1031 //STOP_TIMER("decode_planes"); }
1033 /* If the bidirectional mode is enabled, next I and the following P
1034 * frame will be sent together. Unfortunately the approach below seems
1035 * to be the only way to handle the B-frames mode.
1036 * That's exactly the same Intel decoders do.
1038 if (avctx->codec_id == AV_CODEC_ID_INDEO4 &&
1039 ctx->frame_type == 0/*FRAMETYPE_INTRA*/) {
1040 while (get_bits(&ctx->gb, 8)); // skip version string
1041 skip_bits_long(&ctx->gb, 64); // skip padding, TODO: implement correct 8-bytes alignment
1042 if (get_bits_left(&ctx->gb) > 18 && show_bits(&ctx->gb, 18) == 0x3FFF8)
1043 av_log(avctx, AV_LOG_ERROR, "Buffer contains IP frames!\n");
1046 if (!ctx->is_nonnull_frame(ctx))
1049 avcodec_set_dimensions(avctx, ctx->planes[0].width, ctx->planes[0].height);
1050 if ((result = ff_get_buffer(avctx, frame, 0)) < 0)
1053 if (ctx->is_scalable) {
1054 if (avctx->codec_id == AV_CODEC_ID_INDEO4)
1055 ff_ivi_recompose_haar(&ctx->planes[0], frame->data[0], frame->linesize[0]);
1057 ff_ivi_recompose53 (&ctx->planes[0], frame->data[0], frame->linesize[0]);
1059 ivi_output_plane(&ctx->planes[0], frame->data[0], frame->linesize[0]);
1062 ivi_output_plane(&ctx->planes[2], frame->data[1], frame->linesize[1]);
1063 ivi_output_plane(&ctx->planes[1], frame->data[2], frame->linesize[2]);
1071 * Close Indeo5 decoder and clean up its context.
1073 av_cold int ff_ivi_decode_close(AVCodecContext *avctx)
1075 IVI45DecContext *ctx = avctx->priv_data;
1077 ivi_free_buffers(&ctx->planes[0]);
1079 if (ctx->mb_vlc.cust_tab.table)
1080 ff_free_vlc(&ctx->mb_vlc.cust_tab);
1082 #if IVI4_STREAM_ANALYSER
1083 if (avctx->codec_id == AV_CODEC_ID_INDEO4) {
1084 if (ctx->is_scalable)
1085 av_log(avctx, AV_LOG_ERROR, "This video uses scalability mode!\n");
1086 if (ctx->uses_tiling)
1087 av_log(avctx, AV_LOG_ERROR, "This video uses local decoding!\n");
1088 if (ctx->has_b_frames)
1089 av_log(avctx, AV_LOG_ERROR, "This video contains B-frames!\n");
1090 if (ctx->has_transp)
1091 av_log(avctx, AV_LOG_ERROR, "Transparency mode is enabled!\n");
1093 av_log(avctx, AV_LOG_ERROR, "This video uses Haar transform!\n");
1094 if (ctx->uses_fullpel)
1095 av_log(avctx, AV_LOG_ERROR, "This video uses fullpel motion vectors!\n");
1104 * Scan patterns shared between indeo4 and indeo5
1106 const uint8_t ff_ivi_vertical_scan_8x8[64] = {
1107 0, 8, 16, 24, 32, 40, 48, 56,
1108 1, 9, 17, 25, 33, 41, 49, 57,
1109 2, 10, 18, 26, 34, 42, 50, 58,
1110 3, 11, 19, 27, 35, 43, 51, 59,
1111 4, 12, 20, 28, 36, 44, 52, 60,
1112 5, 13, 21, 29, 37, 45, 53, 61,
1113 6, 14, 22, 30, 38, 46, 54, 62,
1114 7, 15, 23, 31, 39, 47, 55, 63
1117 const uint8_t ff_ivi_horizontal_scan_8x8[64] = {
1118 0, 1, 2, 3, 4, 5, 6, 7,
1119 8, 9, 10, 11, 12, 13, 14, 15,
1120 16, 17, 18, 19, 20, 21, 22, 23,
1121 24, 25, 26, 27, 28, 29, 30, 31,
1122 32, 33, 34, 35, 36, 37, 38, 39,
1123 40, 41, 42, 43, 44, 45, 46, 47,
1124 48, 49, 50, 51, 52, 53, 54, 55,
1125 56, 57, 58, 59, 60, 61, 62, 63
1128 const uint8_t ff_ivi_direct_scan_4x4[16] = {
1129 0, 1, 4, 8, 5, 2, 3, 6, 9, 12, 13, 10, 7, 11, 14, 15
1134 * Run-value (RLE) tables.
1136 const RVMapDesc ff_ivi_rvmap_tabs[9] = {
1141 {1, 1, 0, 1, 1, 0, 1, 1, 2, 2, 1, 1, 1, 1, 3, 3,
1142 1, 1, 2, 2, 1, 1, 4, 4, 1, 1, 1, 1, 2, 2, 5, 5,
1143 1, 1, 3, 3, 1, 1, 6, 6, 1, 2, 1, 2, 7, 7, 1, 1,
1144 8, 8, 1, 1, 4, 2, 1, 4, 2, 1, 3, 3, 1, 1, 1, 9,
1145 9, 1, 2, 1, 2, 1, 5, 5, 1, 1, 10, 10, 1, 1, 3, 3,
1146 2, 2, 1, 1, 11, 11, 6, 4, 4, 1, 6, 1, 2, 1, 2, 12,
1147 8, 1, 12, 7, 8, 7, 1, 16, 1, 16, 1, 3, 3, 13, 1, 13,
1148 2, 2, 1, 15, 1, 5, 14, 15, 1, 5, 14, 1, 17, 8, 17, 8,
1149 1, 4, 4, 2, 2, 1, 25, 25, 24, 24, 1, 3, 1, 3, 1, 8,
1150 6, 7, 6, 1, 18, 8, 18, 1, 7, 23, 2, 2, 23, 1, 1, 21,
1151 22, 9, 9, 22, 19, 1, 21, 5, 19, 5, 1, 33, 20, 33, 20, 8,
1152 4, 4, 1, 32, 2, 2, 8, 3, 32, 26, 3, 1, 7, 7, 26, 6,
1153 1, 6, 1, 1, 16, 1, 10, 1, 10, 2, 16, 29, 28, 2, 29, 28,
1154 1, 27, 5, 8, 5, 27, 1, 8, 3, 7, 3, 31, 41, 31, 1, 41,
1155 6, 1, 6, 7, 4, 4, 1, 1, 2, 1, 2, 11, 34, 30, 11, 1,
1156 30, 15, 15, 34, 36, 40, 36, 40, 35, 35, 37, 37, 39, 39, 38, 38},
1159 { 1, -1, 0, 2, -2, 0, 3, -3, 1, -1, 4, -4, 5, -5, 1, -1,
1160 6, -6, 2, -2, 7, -7, 1, -1, 8, -8, 9, -9, 3, -3, 1, -1,
1161 10, -10, 2, -2, 11, -11, 1, -1, 12, 4, -12, -4, 1, -1, 13, -13,
1162 1, -1, 14, -14, 2, 5, 15, -2, -5, -15, -3, 3, 16, -16, 17, 1,
1163 -1, -17, 6, 18, -6, -18, 2, -2, 19, -19, 1, -1, 20, -20, 4, -4,
1164 7, -7, 21, -21, 1, -1, 2, 3, -3, 22, -2, -22, 8, 23, -8, 1,
1165 2, -23, -1, 2, -2, -2, 24, 1, -24, -1, 25, 5, -5, 1, -25, -1,
1166 9, -9, 26, 1, -26, 3, 1, -1, 27, -3, -1, -27, 1, 3, -1, -3,
1167 28, -4, 4, 10, -10, -28, 1, -1, 1, -1, 29, 6, -29, -6, 30, -4,
1168 3, 3, -3, -30, 1, 4, -1, 31, -3, 1, 11, -11, -1, -31, 32, -1,
1169 -1, 2, -2, 1, 1, -32, 1, 4, -1, -4, 33, -1, 1, 1, -1, 5,
1170 5, -5, -33, -1, -12, 12, -5, -7, 1, 1, 7, 34, 4, -4, -1, 4,
1171 -34, -4, 35, 36, -2, -35, -2, -36, 2, 13, 2, -1, 1, -13, 1, -1,
1172 37, 1, -5, 6, 5, -1, 38, -6, -8, 5, 8, -1, 1, 1, -37, -1,
1173 5, 39, -5, -5, 6, -6, -38, -39, -14, 40, 14, 2, 1, 1, -2, -40,
1174 -1, -2, 2, -1, -1, -1, 1, 1, 1, -1, 1, -1, 1, -1, 1, -1}
1180 {0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 8, 6, 8, 7,
1181 7, 9, 9, 10, 10, 11, 11, 1, 12, 1, 12, 13, 13, 16, 14, 16,
1182 14, 15, 15, 17, 17, 18, 0, 18, 19, 20, 21, 19, 22, 21, 20, 22,
1183 25, 24, 2, 25, 24, 23, 23, 2, 26, 28, 26, 28, 29, 27, 29, 27,
1184 33, 33, 1, 32, 1, 3, 32, 30, 36, 3, 36, 30, 31, 31, 35, 34,
1185 37, 41, 34, 35, 37, 4, 41, 4, 49, 8, 8, 49, 40, 38, 5, 38,
1186 40, 39, 5, 39, 42, 43, 42, 7, 57, 6, 43, 44, 6, 50, 7, 44,
1187 57, 48, 50, 48, 45, 45, 46, 47, 51, 46, 47, 58, 1, 51, 58, 1,
1188 52, 59, 53, 9, 52, 55, 55, 59, 53, 56, 54, 56, 54, 9, 64, 64,
1189 60, 63, 60, 63, 61, 62, 61, 62, 2, 10, 2, 10, 11, 1, 11, 13,
1190 12, 1, 12, 13, 16, 16, 8, 8, 14, 3, 3, 15, 14, 15, 4, 4,
1191 1, 17, 17, 5, 1, 7, 7, 5, 6, 1, 2, 2, 6, 22, 1, 25,
1192 21, 22, 8, 24, 1, 21, 25, 24, 8, 18, 18, 23, 9, 20, 23, 33,
1193 29, 33, 20, 1, 19, 1, 29, 36, 9, 36, 19, 41, 28, 57, 32, 3,
1194 28, 3, 1, 27, 49, 49, 1, 32, 26, 26, 2, 4, 4, 7, 57, 41,
1195 2, 7, 10, 5, 37, 16, 10, 27, 8, 8, 13, 16, 37, 13, 1, 5},
1198 {0, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, 1, -1, -1, 1,
1199 -1, 1, -1, 1, -1, 1, -1, 2, 1, -2, -1, 1, -1, 1, 1, -1,
1200 -1, 1, -1, 1, -1, 1, 0, -1, 1, 1, 1, -1, 1, -1, -1, -1,
1201 1, 1, 2, -1, -1, 1, -1, -2, 1, 1, -1, -1, 1, 1, -1, -1,
1202 1, -1, 3, 1, -3, 2, -1, 1, 1, -2, -1, -1, -1, 1, 1, 1,
1203 1, 1, -1, -1, -1, 2, -1, -2, 1, 2, -2, -1, 1, 1, 2, -1,
1204 -1, 1, -2, -1, 1, 1, -1, 2, 1, 2, -1, 1, -2, -1, -2, -1,
1205 -1, 1, 1, -1, 1, -1, 1, 1, 1, -1, -1, 1, 4, -1, -1, -4,
1206 1, 1, 1, 2, -1, -1, 1, -1, -1, 1, -1, -1, 1, -2, 1, -1,
1207 1, 1, -1, -1, 1, 1, -1, -1, 3, 2, -3, -2, 2, 5, -2, 2,
1208 2, -5, -2, -2, -2, 2, -3, 3, 2, 3, -3, 2, -2, -2, 3, -3,
1209 6, 2, -2, 3, -6, 3, -3, -3, 3, 7, -4, 4, -3, 2, -7, 2,
1210 2, -2, -4, 2, 8, -2, -2, -2, 4, 2, -2, 2, 3, 2, -2, -2,
1211 2, 2, -2, -8, -2, 9, -2, 2, -3, -2, 2, -2, 2, 2, 2, 4,
1212 -2, -4, 10, 2, 2, -2, -9, -2, 2, -2, 5, 4, -4, 4, -2, 2,
1213 -5, -4, -3, 4, 2, -3, 3, -2, -5, 5, 3, 3, -2, -3, -10, -4}
1219 {1, 1, 0, 2, 2, 1, 1, 3, 3, 4, 4, 0, 1, 1, 5, 5,
1220 2, 2, 6, 6, 7, 7, 1, 8, 1, 8, 3, 3, 9, 9, 1, 2,
1221 2, 1, 4, 10, 4, 10, 11, 11, 1, 5, 12, 12, 1, 5, 13, 13,
1222 3, 3, 6, 6, 2, 2, 14, 14, 16, 16, 15, 7, 15, 8, 8, 7,
1223 1, 1, 17, 17, 4, 4, 1, 1, 18, 18, 2, 2, 5, 5, 25, 3,
1224 9, 3, 25, 9, 19, 24, 19, 24, 1, 21, 20, 1, 21, 22, 20, 22,
1225 23, 23, 8, 6, 33, 6, 8, 33, 7, 7, 26, 26, 1, 32, 1, 32,
1226 28, 4, 28, 10, 29, 27, 27, 10, 41, 4, 29, 2, 2, 41, 36, 31,
1227 49, 31, 34, 30, 34, 36, 30, 35, 1, 49, 11, 5, 35, 11, 1, 3,
1228 3, 5, 37, 37, 8, 40, 8, 40, 12, 12, 42, 42, 1, 38, 16, 57,
1229 1, 6, 16, 39, 38, 6, 7, 7, 13, 13, 39, 43, 2, 43, 57, 2,
1230 50, 9, 44, 9, 50, 4, 15, 48, 44, 4, 1, 15, 48, 14, 14, 1,
1231 45, 45, 8, 3, 5, 8, 51, 47, 3, 46, 46, 47, 5, 51, 1, 17,
1232 17, 58, 1, 58, 2, 52, 52, 2, 53, 7, 59, 6, 6, 56, 53, 55,
1233 7, 55, 1, 54, 59, 56, 54, 10, 1, 10, 4, 60, 1, 60, 8, 4,
1234 8, 64, 64, 61, 1, 63, 3, 63, 62, 61, 5, 11, 5, 3, 11, 62},
1237 { 1, -1, 0, 1, -1, 2, -2, 1, -1, 1, -1, 0, 3, -3, 1, -1,
1238 2, -2, 1, -1, 1, -1, 4, 1, -4, -1, 2, -2, 1, -1, 5, 3,
1239 -3, -5, 2, 1, -2, -1, 1, -1, 6, 2, 1, -1, -6, -2, 1, -1,
1240 3, -3, 2, -2, 4, -4, 1, -1, 1, -1, 1, 2, -1, 2, -2, -2,
1241 7, -7, 1, -1, 3, -3, 8, -8, 1, -1, 5, -5, 3, -3, 1, 4,
1242 2, -4, -1, -2, 1, 1, -1, -1, 9, 1, 1, -9, -1, 1, -1, -1,
1243 1, -1, 3, -3, 1, 3, -3, -1, 3, -3, 1, -1, 10, 1, -10, -1,
1244 1, 4, -1, 2, 1, -1, 1, -2, 1, -4, -1, 6, -6, -1, 1, 1,
1245 1, -1, 1, 1, -1, -1, -1, 1, 11, -1, -2, 4, -1, 2, -11, 5,
1246 -5, -4, -1, 1, 4, 1, -4, -1, -2, 2, 1, -1, 12, 1, -2, 1,
1247 -12, 4, 2, 1, -1, -4, 4, -4, 2, -2, -1, 1, 7, -1, -1, -7,
1248 -1, -3, 1, 3, 1, 5, 2, 1, -1, -5, 13, -2, -1, 2, -2, -13,
1249 1, -1, 5, 6, 5, -5, 1, 1, -6, 1, -1, -1, -5, -1, 14, 2,
1250 -2, 1, -14, -1, 8, 1, -1, -8, 1, 5, 1, 5, -5, 1, -1, 1,
1251 -5, -1, 15, 1, -1, -1, -1, 3, -15, -3, 6, 1, 16, -1, 6, -6,
1252 -6, 1, -1, 1, -16, 1, 7, -1, 1, -1, -6, -3, 6, -7, 3, -1}
1258 {0, 1, 1, 2, 2, 3, 3, 4, 4, 1, 1, 5, 5, 6, 6, 7,
1259 7, 8, 8, 9, 9, 2, 2, 10, 10, 1, 1, 11, 11, 12, 12, 3,
1260 3, 13, 13, 0, 14, 14, 16, 15, 16, 15, 4, 4, 17, 1, 17, 1,
1261 5, 5, 18, 18, 2, 2, 6, 6, 8, 19, 7, 8, 7, 19, 20, 20,
1262 21, 21, 22, 24, 22, 24, 23, 23, 1, 1, 25, 25, 3, 3, 26, 26,
1263 9, 9, 27, 27, 28, 28, 33, 29, 4, 33, 29, 1, 4, 1, 32, 32,
1264 2, 2, 31, 10, 30, 10, 30, 31, 34, 34, 5, 5, 36, 36, 35, 41,
1265 35, 11, 41, 11, 37, 1, 8, 8, 37, 6, 1, 6, 40, 7, 7, 40,
1266 12, 38, 12, 39, 39, 38, 49, 13, 49, 13, 3, 42, 3, 42, 16, 16,
1267 43, 43, 14, 14, 1, 1, 44, 15, 44, 15, 2, 2, 57, 48, 50, 48,
1268 57, 50, 4, 45, 45, 4, 46, 47, 47, 46, 1, 51, 1, 17, 17, 51,
1269 8, 9, 9, 5, 58, 8, 58, 5, 52, 52, 55, 56, 53, 56, 55, 59,
1270 59, 53, 54, 1, 6, 54, 7, 7, 6, 1, 2, 3, 2, 3, 64, 60,
1271 60, 10, 10, 64, 61, 62, 61, 63, 1, 63, 62, 1, 18, 24, 18, 4,
1272 25, 4, 8, 21, 21, 1, 24, 22, 25, 22, 8, 11, 19, 11, 23, 1,
1273 20, 23, 19, 20, 5, 12, 5, 1, 16, 2, 12, 13, 2, 13, 1, 16},
1276 { 0, 1, -1, 1, -1, 1, -1, 1, -1, 2, -2, 1, -1, 1, -1, 1,
1277 -1, 1, -1, 1, -1, 2, -2, 1, -1, 3, -3, 1, -1, 1, -1, 2,
1278 -2, 1, -1, 0, 1, -1, 1, 1, -1, -1, 2, -2, 1, 4, -1, -4,
1279 2, -2, 1, -1, -3, 3, 2, -2, 2, 1, 2, -2, -2, -1, 1, -1,
1280 1, -1, 1, 1, -1, -1, 1, -1, 5, -5, 1, -1, 3, -3, 1, -1,
1281 2, -2, 1, -1, 1, -1, 1, 1, 3, -1, -1, 6, -3, -6, -1, 1,
1282 4, -4, 1, 2, 1, -2, -1, -1, 1, -1, 3, -3, 1, -1, 1, 1,
1283 -1, 2, -1, -2, 1, 7, -3, 3, -1, 3, -7, -3, 1, -3, 3, -1,
1284 2, 1, -2, 1, -1, -1, 1, 2, -1, -2, -4, -1, 4, 1, 2, -2,
1285 1, -1, -2, 2, 8, -8, -1, 2, 1, -2, -5, 5, 1, -1, -1, 1,
1286 -1, 1, 4, -1, 1, -4, -1, -1, 1, 1, 9, 1, -9, 2, -2, -1,
1287 -4, 3, -3, -4, -1, 4, 1, 4, 1, -1, 1, -1, 1, 1, -1, 1,
1288 -1, -1, -1, 10, 4, 1, 4, -4, -4, -10, 6, 5, -6, -5, 1, -1,
1289 1, 3, -3, -1, 1, -1, -1, -1, 11, 1, 1, -11, -2, -2, 2, 5,
1290 -2, -5, -5, 2, -2, 12, 2, -2, 2, 2, 5, -3, -2, 3, -2, -12,
1291 -2, 2, 2, 2, -5, 3, 5, 13, -3, 7, -3, -3, -7, 3, -13, 3}
1297 {0, 1, 1, 1, 2, 2, 1, 3, 3, 1, 1, 1, 4, 4, 1, 5,
1298 2, 1, 5, 2, 1, 1, 6, 6, 1, 1, 1, 1, 1, 7, 3, 1,
1299 2, 3, 0, 1, 2, 7, 1, 1, 1, 8, 1, 1, 8, 1, 1, 1,
1300 9, 1, 9, 1, 2, 1, 1, 2, 1, 1, 10, 4, 1, 10, 1, 4,
1301 1, 1, 1, 1, 1, 3, 1, 1, 1, 3, 2, 1, 5, 1, 1, 1,
1302 2, 5, 1, 11, 1, 11, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1303 2, 1, 6, 1, 6, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 12,
1304 3, 1, 12, 1, 1, 1, 2, 1, 1, 3, 1, 1, 1, 1, 1, 1,
1305 4, 1, 1, 1, 2, 1, 1, 4, 1, 1, 1, 1, 1, 1, 2, 1,
1306 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 2, 1, 1, 5,
1307 1, 1, 1, 1, 1, 7, 1, 7, 1, 1, 2, 3, 1, 1, 1, 1,
1308 5, 1, 1, 1, 1, 1, 1, 2, 13, 1, 1, 1, 1, 1, 1, 1,
1309 1, 1, 1, 1, 1, 1, 1, 1, 13, 2, 1, 1, 4, 1, 1, 1,
1310 3, 1, 6, 1, 1, 1, 14, 1, 1, 1, 1, 1, 14, 6, 1, 1,
1311 1, 1, 15, 2, 4, 1, 2, 3, 15, 1, 1, 1, 8, 1, 1, 8,
1312 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1},
1315 { 0, 1, -1, 2, 1, -1, -2, 1, -1, 3, -3, 4, 1, -1, -4, 1,
1316 2, 5, -1, -2, -5, 6, 1, -1, -6, 7, -7, 8, -8, 1, 2, 9,
1317 3, -2, 0, -9, -3, -1, 10, -10, 11, 1, -11, 12, -1, -12, 13, -13,
1318 1, 14, -1, -14, 4, 15, -15, -4, 16, -16, 1, 2, 17, -1, -17, -2,
1319 18, -18, 19, -19, 20, 3, -20, 21, -21, -3, 5, 22, 2, -22, -23, 23,
1320 -5, -2, 24, 1, -24, -1, 25, -25, 26, -26, -27, 27, 28, 29, -28, -29,
1321 6, 30, 2, -31, -2, -30, 31, -6, -32, 32, 33, -33, 34, -35, -34, 1,
1322 4, -36, -1, 35, 37, 36, 7, -37, 38, -4, -38, 39, 41, 40, -40, -39,
1323 3, 42, -43, -41, -7, -42, 43, -3, 44, -44, 45, -45, 46, 47, 8, -47,
1324 -48, -46, 50, -50, 48, 49, 51, -49, 52, -52, 5, -51, -8, -53, 53, 3,
1325 -56, 56, 55, 54, -54, 2, 60, -2, -55, 58, 9, -5, 59, 57, -57, -63,
1326 -3, -58, -60, -61, 61, -59, -62, -9, 1, 64, 62, 69, -64, 63, 65, -67,
1327 -68, 66, -65, 68, -66, -69, 67, -70, -1, 10, 71, -71, 4, 73, 72, 70,
1328 6, -76, -3, 74, -78, -74, 1, 78, 80, -72, -75, 76, -1, 3, -73, 79,
1329 75, 77, 1, 11, -4, -79, -10, -6, -1, -77, -83, -80, 2, 81, -84, -2,
1330 83, -81, 82, -82, 84, -87, -86, 85, -11, -85, 86, -89, 87, -88, 88, 89}
1336 {1, 1, 0, 2, 1, 2, 1, 3, 3, 1, 1, 4, 4, 2, 2, 1,
1337 1, 5, 5, 6, 1, 6, 1, 7, 7, 3, 3, 2, 8, 2, 8, 1,
1338 1, 0, 9, 9, 1, 1, 10, 4, 10, 4, 11, 11, 2, 1, 2, 1,
1339 12, 12, 3, 3, 1, 1, 13, 5, 5, 13, 14, 1, 1, 14, 2, 2,
1340 6, 6, 15, 1, 1, 15, 16, 4, 7, 16, 4, 7, 1, 1, 3, 3,
1341 8, 8, 2, 2, 1, 1, 17, 17, 1, 1, 18, 18, 5, 5, 2, 2,
1342 1, 1, 9, 19, 9, 19, 20, 3, 3, 20, 1, 10, 21, 1, 10, 4,
1343 4, 21, 22, 6, 6, 22, 1, 1, 23, 24, 2, 2, 23, 24, 11, 1,
1344 1, 11, 7, 25, 7, 1, 1, 25, 8, 8, 3, 26, 3, 1, 12, 2,
1345 2, 26, 1, 12, 5, 5, 27, 4, 1, 4, 1, 27, 28, 1, 28, 13,
1346 1, 13, 2, 29, 2, 1, 32, 6, 1, 30, 14, 29, 14, 6, 3, 31,
1347 3, 1, 30, 1, 32, 31, 33, 9, 33, 1, 1, 7, 9, 7, 2, 2,
1348 1, 1, 4, 36, 34, 4, 5, 10, 10, 5, 34, 1, 1, 35, 8, 8,
1349 36, 3, 35, 1, 15, 3, 2, 1, 16, 15, 16, 2, 37, 1, 37, 1,
1350 1, 1, 6, 6, 38, 1, 38, 11, 1, 39, 39, 40, 11, 2, 41, 4,
1351 40, 1, 2, 4, 1, 1, 1, 41, 3, 1, 3, 1, 5, 7, 5, 7},
1354 { 1, -1, 0, 1, 2, -1, -2, 1, -1, 3, -3, 1, -1, 2, -2, 4,
1355 -4, 1, -1, 1, 5, -1, -5, 1, -1, 2, -2, 3, 1, -3, -1, 6,
1356 -6, 0, 1, -1, 7, -7, 1, 2, -1, -2, 1, -1, 4, 8, -4, -8,
1357 1, -1, 3, -3, 9, -9, 1, 2, -2, -1, 1, 10, -10, -1, 5, -5,
1358 2, -2, 1, 11, -11, -1, 1, 3, 2, -1, -3, -2, 12, -12, 4, -4,
1359 2, -2, -6, 6, 13, -13, 1, -1, 14, -14, 1, -1, 3, -3, 7, -7,
1360 15, -15, 2, 1, -2, -1, 1, 5, -5, -1, -16, 2, 1, 16, -2, 4,
1361 -4, -1, 1, 3, -3, -1, 17, -17, 1, 1, -8, 8, -1, -1, 2, 18,
1362 -18, -2, 3, 1, -3, 19, -19, -1, 3, -3, 6, 1, -6, 20, 2, 9,
1363 -9, -1, -20, -2, 4, -4, 1, -5, 21, 5, -21, -1, 1, -22, -1, 2,
1364 22, -2, 10, 1, -10, 23, 1, 4, -23, 1, 2, -1, -2, -4, -7, 1,
1365 7, -24, -1, 24, -1, -1, 1, 3, -1, -25, 25, 4, -3, -4, 11, -11,
1366 26, -26, 6, 1, 1, -6, -5, -3, 3, 5, -1, -27, 27, 1, 4, -4,
1367 -1, -8, -1, 28, 2, 8, -12, -28, -2, -2, 2, 12, -1, 29, 1, -29,
1368 30, -30, 5, -5, 1, -31, -1, 3, 31, -1, 1, 1, -3, -13, 1, -7,
1369 -1, -32, 13, 7, 32, 33, -33, -1, -9, -34, 9, 34, -6, 5, 6, -5}
1375 {1, 1, 0, 1, 1, 2, 2, 1, 1, 3, 3, 1, 1, 0, 2, 2,
1376 4, 1, 4, 1, 1, 1, 5, 5, 1, 1, 6, 6, 2, 2, 1, 1,
1377 3, 3, 7, 7, 1, 1, 8, 8, 1, 1, 2, 2, 1, 9, 1, 9,
1378 4, 4, 10, 1, 1, 10, 1, 1, 11, 11, 3, 3, 1, 2, 1, 2,
1379 1, 1, 12, 12, 5, 5, 1, 1, 13, 1, 1, 13, 2, 2, 1, 1,
1380 6, 6, 1, 1, 4, 14, 4, 14, 3, 1, 3, 1, 1, 1, 15, 7,
1381 15, 2, 2, 7, 1, 1, 1, 8, 1, 8, 16, 16, 1, 1, 1, 1,
1382 2, 1, 1, 2, 1, 1, 3, 5, 5, 3, 4, 1, 1, 4, 1, 1,
1383 17, 17, 9, 1, 1, 9, 2, 2, 1, 1, 10, 10, 1, 6, 1, 1,
1384 6, 18, 1, 1, 18, 1, 1, 1, 2, 2, 3, 1, 3, 1, 1, 1,
1385 4, 1, 19, 1, 19, 7, 1, 1, 20, 1, 4, 20, 1, 7, 11, 2,
1386 1, 11, 21, 2, 8, 5, 1, 8, 1, 5, 21, 1, 1, 1, 22, 1,
1387 1, 22, 1, 1, 3, 3, 1, 23, 2, 12, 24, 1, 1, 2, 1, 1,
1388 12, 23, 1, 1, 24, 1, 1, 1, 4, 1, 1, 1, 2, 1, 6, 6,
1389 4, 2, 1, 1, 1, 1, 1, 1, 1, 14, 13, 3, 1, 25, 9, 25,
1390 14, 1, 9, 3, 13, 1, 1, 1, 1, 1, 10, 1, 1, 2, 10, 2},
1393 {-20, -1, 0, 2, -2, 1, -1, 3, -3, 1, -1, 4, -4, 0, 2, -2,
1394 1, 5, -1, -5, 6, -6, 1, -1, 7, -7, 1, -1, 3, -3, 8, -8,
1395 2, -2, 1, -1, 9, -9, 1, -1, 10, -10, 4, -4, 11, 1, -11, -1,
1396 2, -2, 1, 12, -12, -1, 13, -13, 1, -1, 3, -3, 14, 5, -14, -5,
1397 -15, 15, -1, 1, 2, -2, 16, -16, 1, 17, -17, -1, 6, -6, 18, -18,
1398 2, -2, -19, 19, -3, 1, 3, -1, 4, 20, -4, 1, -21, 21, 1, 2,
1399 -1, -7, 7, -2, 22, -22, 23, 2, -23, -2, 1, -1, -24, 24, -25, 25,
1400 -8, -26, 26, 8, -27, 27, 5, 3, -3, -5, -4, 28, -28, 4, 29, -29,
1401 1, -1, -2, -30, 30, 2, 9, -9, -31, 31, 2, -2, -32, 3, 32, -33,
1402 -3, 1, 33, -34, -1, 34, -35, 35, -10, 10, -6, 36, 6, -36, 37, -37,
1403 -5, 38, 1, -38, -1, 3, 39, -39, -1, 40, 5, 1, -40, -3, 2, -11,
1404 -41, -2, 1, 11, -3, -4, 41, 3, 42, 4, -1, -43, -42, 43, 1, -44,
1405 45, -1, 44, -45, -7, 7, -46, 1, -12, 2, 1, -47, 46, 12, 47, 48,
1406 -2, -1, -48, 49, -1, -50, -49, 50, -6, -51, 51, 52, -13, 53, -4, 4,
1407 6, 13, -53, -52, -54, 55, 54, -55, -56, -2, 2, -8, 56, 1, -3, -1,
1408 2, 58, 3, 8, -2, 57, -58, -60, -59, -57, -3, 60, 59, -14, 3, 14}
1414 {1, 1, 0, 2, 2, 1, 1, 3, 3, 4, 4, 5, 5, 1, 1, 6,
1415 6, 2, 2, 7, 7, 8, 8, 1, 1, 3, 3, 9, 9, 10, 10, 1,
1416 1, 2, 2, 4, 4, 11, 0, 11, 12, 12, 13, 13, 1, 1, 5, 5,
1417 14, 14, 15, 16, 15, 16, 3, 3, 1, 6, 1, 6, 2, 2, 7, 7,
1418 8, 8, 17, 17, 1, 1, 4, 4, 18, 18, 2, 2, 1, 19, 1, 20,
1419 19, 20, 21, 21, 3, 3, 22, 22, 5, 5, 24, 1, 1, 23, 9, 23,
1420 24, 9, 2, 2, 10, 1, 1, 10, 6, 6, 25, 4, 4, 25, 7, 7,
1421 26, 8, 1, 8, 3, 1, 26, 3, 11, 11, 27, 27, 2, 28, 1, 2,
1422 28, 1, 12, 12, 5, 5, 29, 13, 13, 29, 32, 1, 1, 33, 31, 30,
1423 32, 4, 30, 33, 4, 31, 3, 14, 1, 1, 3, 34, 34, 2, 2, 14,
1424 6, 6, 35, 36, 35, 36, 1, 15, 1, 16, 16, 15, 7, 9, 7, 9,
1425 37, 8, 8, 37, 1, 1, 39, 2, 38, 39, 2, 40, 5, 38, 40, 5,
1426 3, 3, 4, 4, 10, 10, 1, 1, 1, 1, 41, 2, 41, 2, 6, 6,
1427 1, 1, 11, 42, 11, 43, 3, 42, 3, 17, 4, 43, 1, 17, 7, 1,
1428 8, 44, 4, 7, 44, 5, 8, 2, 5, 1, 2, 48, 45, 1, 12, 45,
1429 12, 48, 13, 13, 1, 9, 9, 46, 1, 46, 47, 47, 49, 18, 18, 49},
1432 { 1, -1, 0, 1, -1, 2, -2, 1, -1, 1, -1, 1, -1, 3, -3, 1,
1433 -1, -2, 2, 1, -1, 1, -1, 4, -4, -2, 2, 1, -1, 1, -1, 5,
1434 -5, -3, 3, 2, -2, 1, 0, -1, 1, -1, 1, -1, 6, -6, 2, -2,
1435 1, -1, 1, 1, -1, -1, -3, 3, 7, 2, -7, -2, -4, 4, 2, -2,
1436 2, -2, 1, -1, 8, -8, 3, -3, 1, -1, -5, 5, 9, 1, -9, 1,
1437 -1, -1, 1, -1, -4, 4, 1, -1, 3, -3, 1, -10, 10, 1, 2, -1,
1438 -1, -2, 6, -6, 2, 11, -11, -2, 3, -3, 1, -4, 4, -1, 3, -3,
1439 1, 3, 12, -3, -5, -12, -1, 5, 2, -2, 1, -1, -7, 1, 13, 7,
1440 -1, -13, 2, -2, 4, -4, 1, 2, -2, -1, 1, 14, -14, 1, 1, 1,
1441 -1, -5, -1, -1, 5, -1, -6, 2, -15, 15, 6, 1, -1, -8, 8, -2,
1442 -4, 4, 1, 1, -1, -1, 16, 2, -16, -2, 2, -2, 4, 3, -4, -3,
1443 -1, -4, 4, 1, -17, 17, -1, -9, 1, 1, 9, 1, -5, -1, -1, 5,
1444 -7, 7, 6, -6, 3, -3, 18, -18, 19, -19, 1, -10, -1, 10, -5, 5,
1445 20, -20, -3, 1, 3, 1, 8, -1, -8, 2, 7, -1, -21, -2, 5, 21,
1446 5, -1, -7, -5, 1, -6, -5, -11, 6, 22, 11, 1, 1, -22, -3, -1,
1447 3, -1, 3, -3, -23, 4, -4, 1, 23, -1, 1, -1, 1, -2, 2, -1}
1453 {1, 1, 1, 1, 0, 2, 2, 1, 1, 3, 3, 0, 1, 1, 2, 2,
1454 4, 4, 1, 1, 5, 5, 1, 1, 2, 2, 3, 3, 6, 6, 1, 1,
1455 7, 7, 8, 1, 8, 2, 2, 1, 4, 4, 1, 3, 1, 3, 9, 9,
1456 2, 2, 1, 5, 1, 5, 10, 10, 1, 1, 11, 11, 3, 6, 3, 4,
1457 4, 6, 2, 2, 1, 12, 1, 12, 7, 13, 7, 13, 1, 1, 8, 8,
1458 2, 2, 14, 14, 16, 15, 16, 5, 5, 1, 3, 15, 1, 3, 4, 4,
1459 1, 1, 17, 17, 2, 2, 6, 6, 1, 18, 1, 18, 22, 21, 22, 21,
1460 25, 24, 25, 19, 9, 20, 9, 23, 19, 24, 20, 3, 23, 7, 3, 1,
1461 1, 7, 28, 26, 29, 5, 28, 26, 5, 8, 29, 4, 8, 27, 2, 2,
1462 4, 27, 1, 1, 10, 36, 10, 33, 33, 36, 30, 1, 32, 32, 1, 30,
1463 6, 31, 31, 35, 3, 6, 11, 11, 3, 2, 35, 2, 34, 1, 34, 1,
1464 37, 37, 12, 7, 12, 5, 41, 5, 4, 7, 1, 8, 13, 4, 1, 41,
1465 13, 38, 8, 38, 9, 1, 40, 40, 9, 1, 39, 2, 2, 49, 39, 42,
1466 3, 3, 14, 16, 49, 14, 16, 42, 43, 43, 6, 6, 15, 1, 1, 15,
1467 44, 44, 1, 1, 50, 48, 4, 5, 4, 7, 5, 2, 10, 10, 48, 7,
1468 50, 45, 2, 1, 45, 8, 8, 1, 46, 46, 3, 47, 47, 3, 1, 1},
1471 { 1, -1, 2, -2, 0, 1, -1, 3, -3, 1, -1, 0, 4, -4, 2, -2,
1472 1, -1, 5, -5, 1, -1, 6, -6, 3, -3, 2, -2, 1, -1, 7, -7,
1473 1, -1, 1, 8, -1, 4, -4, -8, 2, -2, 9, 3, -9, -3, 1, -1,
1474 5, -5, 10, 2, -10, -2, 1, -1, 11, -11, 1, -1, -4, 2, 4, 3,
1475 -3, -2, 6, -6, 12, 1, -12, -1, 2, 1, -2, -1, 13, -13, 2, -2,
1476 7, -7, 1, -1, 1, 1, -1, 3, -3, 14, 5, -1, -14, -5, 4, -4,
1477 15, -15, 1, -1, 8, -8, -3, 3, 16, 1, -16, -1, 1, 1, -1, -1,
1478 1, 1, -1, 1, 2, 1, -2, 1, -1, -1, -1, 6, -1, 3, -6, 17,
1479 -17, -3, 1, 1, 1, 4, -1, -1, -4, 3, -1, 5, -3, -1, -9, 9,
1480 -5, 1, 18, -18, 2, 1, -2, 1, -1, -1, 1, 19, -1, 1, -19, -1,
1481 4, 1, -1, 1, 7, -4, -2, 2, -7, 10, -1, -10, 1, 20, -1, -20,
1482 1, -1, 2, 4, -2, 5, 1, -5, 6, -4, 21, 4, 2, -6, -21, -1,
1483 -2, 1, -4, -1, -3, 22, -1, 1, 3, -22, -1, 11, -11, 1, 1, 1,
1484 8, -8, 2, 2, -1, -2, -2, -1, 1, -1, -5, 5, 2, 23, -23, -2,
1485 1, -1, 24, -24, -1, -1, 7, 6, -7, 5, -6, 12, -3, 3, 1, -5,
1486 1, 1, -12, 25, -1, -5, 5, -25, -1, 1, 9, 1, -1, -9, 26, -26}