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"
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 av_assert0(offs >= 0 && ref_offs >= 0 && band->ref_buf);
84 av_assert0(buf_size - min_size >= offs);
85 av_assert0(buf_size - min_size - ref_size >= ref_offs);
87 mc(band->buf + offs, band->ref_buf + ref_offs, band->pitch, mc_type);
93 * Reverse "nbits" bits of the value "val" and return the result
94 * in the least significant bits.
96 static uint16_t inv_bits(uint16_t val, int nbits)
101 res = ff_reverse[val] >> (8 - nbits);
103 res = ((ff_reverse[val & 0xFF] << 8) +
104 (ff_reverse[val >> 8])) >> (16 - nbits);
110 * Generate a huffman codebook from the given descriptor
111 * and convert it into the FFmpeg VLC table.
113 * @param[in] cb pointer to codebook descriptor
114 * @param[out] vlc where to place the generated VLC table
115 * @param[in] flag flag: 1 - for static or 0 for dynamic tables
116 * @return result code: 0 - OK, -1 = error (invalid codebook descriptor)
118 static int ivi_create_huff_from_desc(const IVIHuffDesc *cb, VLC *vlc, int flag)
120 int pos, i, j, codes_per_row, prefix, not_last_row;
121 uint16_t codewords[256]; /* FIXME: move this temporal storage out? */
124 pos = 0; /* current position = 0 */
126 for (i = 0; i < cb->num_rows; i++) {
127 codes_per_row = 1 << cb->xbits[i];
128 not_last_row = (i != cb->num_rows - 1);
129 prefix = ((1 << i) - 1) << (cb->xbits[i] + not_last_row);
131 for (j = 0; j < codes_per_row; j++) {
132 if (pos >= 256) /* Some Indeo5 codebooks can have more than 256 */
133 break; /* elements, but only 256 codes are allowed! */
135 bits[pos] = i + cb->xbits[i] + not_last_row;
136 if (bits[pos] > IVI_VLC_BITS)
137 return AVERROR_INVALIDDATA; /* invalid descriptor */
139 codewords[pos] = inv_bits((prefix | j), bits[pos]);
147 /* number of codewords = pos */
148 return init_vlc(vlc, IVI_VLC_BITS, pos, bits, 1, 1, codewords, 2, 2,
149 (flag ? INIT_VLC_USE_NEW_STATIC : 0) | INIT_VLC_LE);
152 av_cold void ff_ivi_init_static_vlc(void)
155 static VLC_TYPE table_data[8192 * 16][2];
156 static int initialized_vlcs = 0;
158 if (initialized_vlcs)
160 for (i = 0; i < 8; i++) {
161 ivi_mb_vlc_tabs[i].table = table_data + i * 2 * 8192;
162 ivi_mb_vlc_tabs[i].table_allocated = 8192;
163 ivi_create_huff_from_desc(&ivi_mb_huff_desc[i],
164 &ivi_mb_vlc_tabs[i], 1);
165 ivi_blk_vlc_tabs[i].table = table_data + (i * 2 + 1) * 8192;
166 ivi_blk_vlc_tabs[i].table_allocated = 8192;
167 ivi_create_huff_from_desc(&ivi_blk_huff_desc[i],
168 &ivi_blk_vlc_tabs[i], 1);
170 initialized_vlcs = 1;
174 * Copy huffman codebook descriptors.
176 * @param[out] dst ptr to the destination descriptor
177 * @param[in] src ptr to the source descriptor
179 static void ivi_huff_desc_copy(IVIHuffDesc *dst, const IVIHuffDesc *src)
181 dst->num_rows = src->num_rows;
182 memcpy(dst->xbits, src->xbits, src->num_rows);
186 * Compare two huffman codebook descriptors.
188 * @param[in] desc1 ptr to the 1st descriptor to compare
189 * @param[in] desc2 ptr to the 2nd descriptor to compare
190 * @return comparison result: 0 - equal, 1 - not equal
192 static int ivi_huff_desc_cmp(const IVIHuffDesc *desc1,
193 const IVIHuffDesc *desc2)
195 return desc1->num_rows != desc2->num_rows ||
196 memcmp(desc1->xbits, desc2->xbits, desc1->num_rows);
199 int ff_ivi_dec_huff_desc(GetBitContext *gb, int desc_coded, int which_tab,
200 IVIHuffTab *huff_tab, AVCodecContext *avctx)
203 IVIHuffDesc new_huff;
206 /* select default table */
207 huff_tab->tab = (which_tab) ? &ivi_blk_vlc_tabs[7]
208 : &ivi_mb_vlc_tabs [7];
212 huff_tab->tab_sel = get_bits(gb, 3);
213 if (huff_tab->tab_sel == 7) {
214 /* custom huffman table (explicitly encoded) */
215 new_huff.num_rows = get_bits(gb, 4);
216 if (!new_huff.num_rows) {
217 av_log(avctx, AV_LOG_ERROR, "Empty custom Huffman table!\n");
218 return AVERROR_INVALIDDATA;
221 for (i = 0; i < new_huff.num_rows; i++)
222 new_huff.xbits[i] = get_bits(gb, 4);
224 /* Have we got the same custom table? Rebuild if not. */
225 if (ivi_huff_desc_cmp(&new_huff, &huff_tab->cust_desc) || !huff_tab->cust_tab.table) {
226 ivi_huff_desc_copy(&huff_tab->cust_desc, &new_huff);
228 if (huff_tab->cust_tab.table)
229 ff_free_vlc(&huff_tab->cust_tab);
230 result = ivi_create_huff_from_desc(&huff_tab->cust_desc,
231 &huff_tab->cust_tab, 0);
233 // reset faulty description
234 huff_tab->cust_desc.num_rows = 0;
235 av_log(avctx, AV_LOG_ERROR,
236 "Error while initializing custom vlc table!\n");
240 huff_tab->tab = &huff_tab->cust_tab;
242 /* select one of predefined tables */
243 huff_tab->tab = (which_tab) ? &ivi_blk_vlc_tabs[huff_tab->tab_sel]
244 : &ivi_mb_vlc_tabs [huff_tab->tab_sel];
251 * Free planes, bands and macroblocks buffers.
253 * @param[in] planes pointer to the array of the plane descriptors
255 static av_cold void ivi_free_buffers(IVIPlaneDesc *planes)
259 for (p = 0; p < 3; p++) {
261 for (b = 0; b < planes[p].num_bands; b++) {
262 av_freep(&planes[p].bands[b].bufs[0]);
263 av_freep(&planes[p].bands[b].bufs[1]);
264 av_freep(&planes[p].bands[b].bufs[2]);
266 if (planes[p].bands[b].blk_vlc.cust_tab.table)
267 ff_free_vlc(&planes[p].bands[b].blk_vlc.cust_tab);
268 for (t = 0; t < planes[p].bands[b].num_tiles; t++)
269 av_freep(&planes[p].bands[b].tiles[t].mbs);
270 av_freep(&planes[p].bands[b].tiles);
272 av_freep(&planes[p].bands);
273 planes[p].num_bands = 0;
277 av_cold int ff_ivi_init_planes(IVIPlaneDesc *planes, const IVIPicConfig *cfg)
280 uint32_t b_width, b_height, align_fac, width_aligned,
281 height_aligned, buf_size;
284 ivi_free_buffers(planes);
286 if (cfg->pic_width < 1 || cfg->pic_height < 1 ||
287 cfg->luma_bands < 1 || cfg->chroma_bands < 1)
288 return AVERROR_INVALIDDATA;
290 /* fill in the descriptor of the luminance plane */
291 planes[0].width = cfg->pic_width;
292 planes[0].height = cfg->pic_height;
293 planes[0].num_bands = cfg->luma_bands;
295 /* fill in the descriptors of the chrominance planes */
296 planes[1].width = planes[2].width = (cfg->pic_width + 3) >> 2;
297 planes[1].height = planes[2].height = (cfg->pic_height + 3) >> 2;
298 planes[1].num_bands = planes[2].num_bands = cfg->chroma_bands;
300 for (p = 0; p < 3; p++) {
301 planes[p].bands = av_mallocz(planes[p].num_bands * sizeof(IVIBandDesc));
302 if (!planes[p].bands)
303 return AVERROR(ENOMEM);
305 /* select band dimensions: if there is only one band then it
306 * has the full size, if there are several bands each of them
307 * has only half size */
308 b_width = planes[p].num_bands == 1 ? planes[p].width
309 : (planes[p].width + 1) >> 1;
310 b_height = planes[p].num_bands == 1 ? planes[p].height
311 : (planes[p].height + 1) >> 1;
313 /* luma band buffers will be aligned on 16x16 (max macroblock size) */
314 /* chroma band buffers will be aligned on 8x8 (max macroblock size) */
315 align_fac = p ? 8 : 16;
316 width_aligned = FFALIGN(b_width , align_fac);
317 height_aligned = FFALIGN(b_height, align_fac);
318 buf_size = width_aligned * height_aligned * sizeof(int16_t);
320 for (b = 0; b < planes[p].num_bands; b++) {
321 band = &planes[p].bands[b]; /* select appropriate plane/band */
324 band->width = b_width;
325 band->height = b_height;
326 band->pitch = width_aligned;
327 band->aheight = height_aligned;
328 band->bufs[0] = av_mallocz(buf_size);
329 band->bufs[1] = av_mallocz(buf_size);
330 band->bufsize = buf_size/2;
331 if (!band->bufs[0] || !band->bufs[1])
332 return AVERROR(ENOMEM);
334 /* allocate the 3rd band buffer for scalability mode */
335 if (cfg->luma_bands > 1) {
336 band->bufs[2] = av_mallocz(buf_size);
338 return AVERROR(ENOMEM);
340 /* reset custom vlc */
341 planes[p].bands[0].blk_vlc.cust_desc.num_rows = 0;
348 static int ivi_init_tiles(IVIBandDesc *band, IVITile *ref_tile,
349 int p, int b, int t_height, int t_width)
352 IVITile *tile = band->tiles;
354 for (y = 0; y < band->height; y += t_height) {
355 for (x = 0; x < band->width; x += t_width) {
358 tile->mb_size = band->mb_size;
359 tile->width = FFMIN(band->width - x, t_width);
360 tile->height = FFMIN(band->height - y, t_height);
361 tile->is_empty = tile->data_size = 0;
362 /* calculate number of macroblocks */
363 tile->num_MBs = IVI_MBs_PER_TILE(tile->width, tile->height,
366 av_freep(&tile->mbs);
367 tile->mbs = av_mallocz(tile->num_MBs * sizeof(IVIMbInfo));
369 return AVERROR(ENOMEM);
373 if (tile->num_MBs != ref_tile->num_MBs) {
374 av_log(NULL, AV_LOG_DEBUG, "ref_tile mismatch\n");
375 return AVERROR_INVALIDDATA;
377 tile->ref_mbs = ref_tile->mbs;
387 av_cold int ff_ivi_init_tiles(IVIPlaneDesc *planes,
388 int tile_width, int tile_height)
390 int p, b, x_tiles, y_tiles, t_width, t_height, ret;
393 for (p = 0; p < 3; p++) {
394 t_width = !p ? tile_width : (tile_width + 3) >> 2;
395 t_height = !p ? tile_height : (tile_height + 3) >> 2;
397 if (!p && planes[0].num_bands == 4) {
401 if(t_width<=0 || t_height<=0)
402 return AVERROR(EINVAL);
404 for (b = 0; b < planes[p].num_bands; b++) {
405 band = &planes[p].bands[b];
406 x_tiles = IVI_NUM_TILES(band->width, t_width);
407 y_tiles = IVI_NUM_TILES(band->height, t_height);
408 band->num_tiles = x_tiles * y_tiles;
410 av_freep(&band->tiles);
411 band->tiles = av_mallocz(band->num_tiles * sizeof(IVITile));
413 return AVERROR(ENOMEM);
415 /* use the first luma band as reference for motion vectors
417 ret = ivi_init_tiles(band, planes[0].bands[0].tiles,
418 p, b, t_height, t_width);
428 * Decode size of the tile data.
429 * The size is stored as a variable-length field having the following format:
430 * if (tile_data_size < 255) than this field is only one byte long
431 * if (tile_data_size >= 255) than this field four is byte long: 0xFF X1 X2 X3
432 * where X1-X3 is size of the tile data
434 * @param[in,out] gb the GetBit context
435 * @return size of the tile data in bytes
437 static int ivi_dec_tile_data_size(GetBitContext *gb)
443 len = get_bits(gb, 8);
445 len = get_bits_long(gb, 24);
448 /* align the bitstream reader on the byte boundary */
454 static int ivi_dc_transform(IVIBandDesc *band, int *prev_dc, int buf_offs,
457 int buf_size = band->pitch * band->aheight - buf_offs;
458 int min_size = (blk_size - 1) * band->pitch + blk_size;
460 if (min_size > buf_size)
461 return AVERROR_INVALIDDATA;
463 band->dc_transform(prev_dc, band->buf + buf_offs,
464 band->pitch, blk_size);
469 static int ivi_decode_coded_blocks(GetBitContext *gb, IVIBandDesc *band,
470 ivi_mc_func mc, int mv_x, int mv_y,
471 int *prev_dc, int is_intra, int mc_type,
472 uint32_t quant, int offs,
473 AVCodecContext *avctx)
475 const uint16_t *base_tab = is_intra ? band->intra_base : band->inter_base;
476 RVMapDesc *rvmap = band->rv_map;
477 uint8_t col_flags[8];
479 uint32_t sym = 0, lo, hi, q;
481 int blk_size = band->blk_size;
482 int num_coeffs = blk_size * blk_size;
483 int col_mask = blk_size - 1;
485 int min_size = band->pitch * (band->transform_size - 1) +
486 band->transform_size;
487 int buf_size = band->pitch * band->aheight - offs;
489 if (min_size > buf_size)
490 return AVERROR_INVALIDDATA;
493 av_log(avctx, AV_LOG_ERROR, "Scan pattern is not set.\n");
494 return AVERROR_INVALIDDATA;
497 /* zero transform vector */
498 memset(trvec, 0, num_coeffs * sizeof(trvec[0]));
499 /* zero column flags */
500 memset(col_flags, 0, sizeof(col_flags));
501 while (scan_pos <= num_coeffs) {
502 sym = get_vlc2(gb, band->blk_vlc.tab->table,
504 if (sym == rvmap->eob_sym)
505 break; /* End of block */
507 /* Escape - run/val explicitly coded using 3 vlc codes */
508 if (sym == rvmap->esc_sym) {
509 run = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1) + 1;
510 lo = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
511 hi = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
512 /* merge them and convert into signed val */
513 val = IVI_TOSIGNED((hi << 6) | lo);
516 av_log(avctx, AV_LOG_ERROR, "Invalid sym encountered: %d.\n", sym);
517 return AVERROR_INVALIDDATA;
519 run = rvmap->runtab[sym];
520 val = rvmap->valtab[sym];
523 /* de-zigzag and dequantize */
525 if (scan_pos >= num_coeffs || scan_pos < 0)
527 pos = band->scan[scan_pos];
530 av_dlog(avctx, "Val = 0 encountered!\n");
532 q = (base_tab[pos] * quant) >> 9;
534 val = val * q + FFSIGN(val) * (((q ^ 1) - 1) >> 1);
536 /* track columns containing non-zero coeffs */
537 col_flags[pos & col_mask] |= !!val;
540 if (scan_pos < 0 || scan_pos >= num_coeffs && sym != rvmap->eob_sym)
541 return AVERROR_INVALIDDATA; /* corrupt block data */
543 /* undoing DC coeff prediction for intra-blocks */
544 if (is_intra && band->is_2d_trans) {
545 *prev_dc += trvec[0];
547 col_flags[0] |= !!*prev_dc;
550 if(band->transform_size > band->blk_size){
551 av_log(NULL, AV_LOG_ERROR, "Too large transform\n");
552 return AVERROR_INVALIDDATA;
555 /* apply inverse transform */
556 band->inv_transform(trvec, band->buf + offs,
557 band->pitch, col_flags);
559 /* apply motion compensation */
561 return ivi_mc(band, mc, offs, mv_x, mv_y, mc_type);
567 * extract huffman-coded transform coefficients from the bitstream,
568 * dequantize them, apply inverse transform and motion compensation
569 * in order to reconstruct the picture.
571 * @param[in,out] gb the GetBit context
572 * @param[in] band pointer to the band descriptor
573 * @param[in] tile pointer to the tile descriptor
574 * @return result code: 0 - OK, -1 = error (corrupted blocks data)
576 static int ivi_decode_blocks(GetBitContext *gb, IVIBandDesc *band,
577 IVITile *tile, AVCodecContext *avctx)
579 int mbn, blk, num_blocks, blk_size, ret, is_intra, mc_type = 0;
580 int mv_x = 0, mv_y = 0;
582 uint32_t cbp, quant, buf_offs;
584 ivi_mc_func mc_with_delta_func, mc_no_delta_func;
585 const uint8_t *scale_tab;
587 /* init intra prediction for the DC coefficient */
589 blk_size = band->blk_size;
590 /* number of blocks per mb */
591 num_blocks = (band->mb_size != blk_size) ? 4 : 1;
593 mc_with_delta_func = ff_ivi_mc_8x8_delta;
594 mc_no_delta_func = ff_ivi_mc_8x8_no_delta;
596 mc_with_delta_func = ff_ivi_mc_4x4_delta;
597 mc_no_delta_func = ff_ivi_mc_4x4_no_delta;
600 for (mbn = 0, mb = tile->mbs; mbn < tile->num_MBs; mb++, mbn++) {
601 is_intra = !mb->type;
603 buf_offs = mb->buf_offs;
605 quant = band->glob_quant + mb->q_delta;
606 if (avctx->codec_id == AV_CODEC_ID_INDEO4)
607 quant = av_clip(quant, 0, 31);
609 quant = av_clip(quant, 0, 23);
611 scale_tab = is_intra ? band->intra_scale : band->inter_scale;
613 quant = scale_tab[quant];
618 if (band->is_halfpel) {
619 mc_type = ((mv_y & 1) << 1) | (mv_x & 1);
621 mv_y >>= 1; /* convert halfpel vectors into fullpel ones */
624 int dmv_x, dmv_y, cx, cy;
626 dmv_x = mb->mv_x >> band->is_halfpel;
627 dmv_y = mb->mv_y >> band->is_halfpel;
628 cx = mb->mv_x & band->is_halfpel;
629 cy = mb->mv_y & band->is_halfpel;
631 if (mb->xpos + dmv_x < 0 ||
632 mb->xpos + dmv_x + band->mb_size + cx > band->pitch ||
633 mb->ypos + dmv_y < 0 ||
634 mb->ypos + dmv_y + band->mb_size + cy > band->aheight) {
635 return AVERROR_INVALIDDATA;
640 for (blk = 0; blk < num_blocks; blk++) {
641 /* adjust block position in the buffer according to its number */
643 buf_offs += blk_size;
644 } else if (blk == 2) {
645 buf_offs -= blk_size;
646 buf_offs += blk_size * band->pitch;
649 if (cbp & 1) { /* block coded ? */
650 ret = ivi_decode_coded_blocks(gb, band, mc_with_delta_func,
651 mv_x, mv_y, &prev_dc, is_intra,
652 mc_type, quant, buf_offs, avctx);
656 /* block not coded */
657 /* for intra blocks apply the dc slant transform */
658 /* for inter - perform the motion compensation without delta */
660 ret = ivi_dc_transform(band, &prev_dc, buf_offs, blk_size);
664 ret = ivi_mc(band, mc_no_delta_func, buf_offs,
665 mv_x, mv_y, mc_type);
681 * Handle empty tiles by performing data copying and motion
682 * compensation respectively.
684 * @param[in] avctx ptr to the AVCodecContext
685 * @param[in] band pointer to the band descriptor
686 * @param[in] tile pointer to the tile descriptor
687 * @param[in] mv_scale scaling factor for motion vectors
689 static int ivi_process_empty_tile(AVCodecContext *avctx, IVIBandDesc *band,
690 IVITile *tile, int32_t mv_scale)
692 int x, y, need_mc, mbn, blk, num_blocks, mv_x, mv_y, mc_type;
693 int offs, mb_offset, row_offset, ret;
694 IVIMbInfo *mb, *ref_mb;
697 ivi_mc_func mc_no_delta_func;
699 if (tile->num_MBs != IVI_MBs_PER_TILE(tile->width, tile->height, band->mb_size)) {
700 av_log(avctx, AV_LOG_ERROR, "Allocated tile size %d mismatches "
701 "parameters %d in ivi_process_empty_tile()\n",
702 tile->num_MBs, IVI_MBs_PER_TILE(tile->width, tile->height, band->mb_size));
703 return AVERROR_INVALIDDATA;
706 offs = tile->ypos * band->pitch + tile->xpos;
708 ref_mb = tile->ref_mbs;
709 row_offset = band->mb_size * band->pitch;
710 need_mc = 0; /* reset the mc tracking flag */
712 for (y = tile->ypos; y < (tile->ypos + tile->height); y += band->mb_size) {
715 for (x = tile->xpos; x < (tile->xpos + tile->width); x += band->mb_size) {
718 mb->buf_offs = mb_offset;
720 mb->type = 1; /* set the macroblocks type = INTER */
721 mb->cbp = 0; /* all blocks are empty */
723 if (!band->qdelta_present && !band->plane && !band->band_num) {
724 mb->q_delta = band->glob_quant;
729 if (band->inherit_qdelta && ref_mb)
730 mb->q_delta = ref_mb->q_delta;
732 if (band->inherit_mv && ref_mb) {
733 /* motion vector inheritance */
735 mb->mv_x = ivi_scale_mv(ref_mb->mv_x, mv_scale);
736 mb->mv_y = ivi_scale_mv(ref_mb->mv_y, mv_scale);
738 mb->mv_x = ref_mb->mv_x;
739 mb->mv_y = ref_mb->mv_y;
741 need_mc |= mb->mv_x || mb->mv_y; /* tracking non-zero motion vectors */
743 int dmv_x, dmv_y, cx, cy;
745 dmv_x = mb->mv_x >> band->is_halfpel;
746 dmv_y = mb->mv_y >> band->is_halfpel;
747 cx = mb->mv_x & band->is_halfpel;
748 cy = mb->mv_y & band->is_halfpel;
750 if ( mb->xpos + dmv_x < 0
751 || mb->xpos + dmv_x + band->mb_size + cx > band->pitch
752 || mb->ypos + dmv_y < 0
753 || mb->ypos + dmv_y + band->mb_size + cy > band->aheight) {
754 av_log(avctx, AV_LOG_ERROR, "MV out of bounds\n");
755 return AVERROR_INVALIDDATA;
763 mb_offset += band->mb_size;
768 if (band->inherit_mv && need_mc) { /* apply motion compensation if there is at least one non-zero motion vector */
769 num_blocks = (band->mb_size != band->blk_size) ? 4 : 1; /* number of blocks per mb */
770 mc_no_delta_func = (band->blk_size == 8) ? ff_ivi_mc_8x8_no_delta
771 : ff_ivi_mc_4x4_no_delta;
773 for (mbn = 0, mb = tile->mbs; mbn < tile->num_MBs; mb++, mbn++) {
776 if (!band->is_halfpel) {
777 mc_type = 0; /* we have only fullpel vectors */
779 mc_type = ((mv_y & 1) << 1) | (mv_x & 1);
781 mv_y >>= 1; /* convert halfpel vectors into fullpel ones */
784 for (blk = 0; blk < num_blocks; blk++) {
785 /* adjust block position in the buffer according with its number */
786 offs = mb->buf_offs + band->blk_size * ((blk & 1) + !!(blk & 2) * band->pitch);
787 ret = ivi_mc(band, mc_no_delta_func, offs,
788 mv_x, mv_y, mc_type);
794 /* copy data from the reference tile into the current one */
795 src = band->ref_buf + tile->ypos * band->pitch + tile->xpos;
796 dst = band->buf + tile->ypos * band->pitch + tile->xpos;
797 for (y = 0; y < tile->height; y++) {
798 memcpy(dst, src, tile->width*sizeof(band->buf[0]));
809 static uint16_t ivi_calc_band_checksum(IVIBandDesc *band)
812 int16_t *src, checksum;
817 for (y = 0; y < band->height; src += band->pitch, y++)
818 for (x = 0; x < band->width; x++)
826 * Convert and output the current plane.
827 * This conversion is done by adding back the bias value of 128
828 * (subtracted in the encoder) and clipping the result.
830 * @param[in] plane pointer to the descriptor of the plane being processed
831 * @param[out] dst pointer to the buffer receiving converted pixels
832 * @param[in] dst_pitch pitch for moving to the next y line
834 static void ivi_output_plane(IVIPlaneDesc *plane, uint8_t *dst, int dst_pitch)
837 const int16_t *src = plane->bands[0].buf;
838 uint32_t pitch = plane->bands[0].pitch;
843 for (y = 0; y < plane->height; y++) {
844 for (x = 0; x < plane->width; x++)
845 dst[x] = av_clip_uint8(src[x] + 128);
852 * Decode an Indeo 4 or 5 band.
854 * @param[in,out] ctx ptr to the decoder context
855 * @param[in,out] band ptr to the band descriptor
856 * @param[in] avctx ptr to the AVCodecContext
857 * @return result code: 0 = OK, -1 = error
859 static int decode_band(IVI45DecContext *ctx,
860 IVIBandDesc *band, AVCodecContext *avctx)
862 int result, i, t, idx1, idx2, pos;
865 band->buf = band->bufs[ctx->dst_buf];
867 av_log(avctx, AV_LOG_ERROR, "Band buffer points to no data!\n");
868 return AVERROR_INVALIDDATA;
870 band->ref_buf = band->bufs[ctx->ref_buf];
871 band->data_ptr = ctx->frame_data + (get_bits_count(&ctx->gb) >> 3);
873 result = ctx->decode_band_hdr(ctx, band, avctx);
875 av_log(avctx, AV_LOG_ERROR, "Error while decoding band header: %d\n",
880 if (band->is_empty) {
881 av_log(avctx, AV_LOG_ERROR, "Empty band encountered!\n");
882 return AVERROR_INVALIDDATA;
885 band->rv_map = &ctx->rvmap_tabs[band->rvmap_sel];
887 /* apply corrections to the selected rvmap table if present */
888 for (i = 0; i < band->num_corr; i++) {
889 idx1 = band->corr[i * 2];
890 idx2 = band->corr[i * 2 + 1];
891 FFSWAP(uint8_t, band->rv_map->runtab[idx1], band->rv_map->runtab[idx2]);
892 FFSWAP(int16_t, band->rv_map->valtab[idx1], band->rv_map->valtab[idx2]);
893 if (idx1 == band->rv_map->eob_sym || idx2 == band->rv_map->eob_sym)
894 band->rv_map->eob_sym ^= idx1 ^ idx2;
895 if (idx1 == band->rv_map->esc_sym || idx2 == band->rv_map->esc_sym)
896 band->rv_map->esc_sym ^= idx1 ^ idx2;
899 pos = get_bits_count(&ctx->gb);
901 for (t = 0; t < band->num_tiles; t++) {
902 tile = &band->tiles[t];
904 if (tile->mb_size != band->mb_size) {
905 av_log(avctx, AV_LOG_ERROR, "MB sizes mismatch: %d vs. %d\n",
906 band->mb_size, tile->mb_size);
907 return AVERROR_INVALIDDATA;
909 tile->is_empty = get_bits1(&ctx->gb);
910 if (tile->is_empty) {
911 result = ivi_process_empty_tile(avctx, band, tile,
912 (ctx->planes[0].bands[0].mb_size >> 3) - (band->mb_size >> 3));
915 av_dlog(avctx, "Empty tile encountered!\n");
917 tile->data_size = ivi_dec_tile_data_size(&ctx->gb);
918 if (!tile->data_size) {
919 av_log(avctx, AV_LOG_ERROR, "Tile data size is zero!\n");
920 result = AVERROR_INVALIDDATA;
924 result = ctx->decode_mb_info(ctx, band, tile, avctx);
928 result = ivi_decode_blocks(&ctx->gb, band, tile, avctx);
930 av_log(avctx, AV_LOG_ERROR,
931 "Corrupted tile data encountered!\n");
935 if (((get_bits_count(&ctx->gb) - pos) >> 3) != tile->data_size) {
936 av_log(avctx, AV_LOG_ERROR,
937 "Tile data_size mismatch!\n");
938 result = AVERROR_INVALIDDATA;
942 pos += tile->data_size << 3; // skip to next tile
946 /* restore the selected rvmap table by applying its corrections in
948 for (i = band->num_corr-1; i >= 0; i--) {
949 idx1 = band->corr[i*2];
950 idx2 = band->corr[i*2+1];
951 FFSWAP(uint8_t, band->rv_map->runtab[idx1], band->rv_map->runtab[idx2]);
952 FFSWAP(int16_t, band->rv_map->valtab[idx1], band->rv_map->valtab[idx2]);
953 if (idx1 == band->rv_map->eob_sym || idx2 == band->rv_map->eob_sym)
954 band->rv_map->eob_sym ^= idx1 ^ idx2;
955 if (idx1 == band->rv_map->esc_sym || idx2 == band->rv_map->esc_sym)
956 band->rv_map->esc_sym ^= idx1 ^ idx2;
960 if (band->checksum_present) {
961 uint16_t chksum = ivi_calc_band_checksum(band);
962 if (chksum != band->checksum) {
963 av_log(avctx, AV_LOG_ERROR,
964 "Band checksum mismatch! Plane %d, band %d, "
965 "received: %x, calculated: %x\n",
966 band->plane, band->band_num, band->checksum, chksum);
971 align_get_bits(&ctx->gb);
976 int ff_ivi_decode_frame(AVCodecContext *avctx, void *data, int *got_frame,
979 IVI45DecContext *ctx = avctx->priv_data;
980 const uint8_t *buf = avpkt->data;
981 AVFrame *frame = data;
982 int buf_size = avpkt->size;
985 init_get_bits(&ctx->gb, buf, buf_size * 8);
986 ctx->frame_data = buf;
987 ctx->frame_size = buf_size;
989 result = ctx->decode_pic_hdr(ctx, avctx);
991 av_log(avctx, AV_LOG_ERROR,
992 "Error while decoding picture header: %d\n", result);
995 if (ctx->gop_invalid)
996 return AVERROR_INVALIDDATA;
998 if (ctx->gop_flags & IVI5_IS_PROTECTED) {
999 avpriv_report_missing_feature(avctx, "Password-protected clip!\n");
1000 return AVERROR_PATCHWELCOME;
1003 if (!ctx->planes[0].bands) {
1004 av_log(avctx, AV_LOG_ERROR, "Color planes not initialized yet\n");
1005 return AVERROR_INVALIDDATA;
1008 ctx->switch_buffers(ctx);
1012 if (ctx->is_nonnull_frame(ctx)) {
1013 ctx->buf_invalid[ctx->dst_buf] = 1;
1014 for (p = 0; p < 3; p++) {
1015 for (b = 0; b < ctx->planes[p].num_bands; b++) {
1016 result = decode_band(ctx, &ctx->planes[p].bands[b], avctx);
1018 av_log(avctx, AV_LOG_ERROR,
1019 "Error while decoding band: %d, plane: %d\n", b, p);
1024 ctx->buf_invalid[ctx->dst_buf] = 0;
1026 if (ctx->is_scalable)
1027 return AVERROR_INVALIDDATA;
1029 for (p = 0; p < 3; p++) {
1030 if (!ctx->planes[p].bands[0].buf)
1031 return AVERROR_INVALIDDATA;
1034 if (ctx->buf_invalid[ctx->dst_buf])
1037 //STOP_TIMER("decode_planes"); }
1039 /* If the bidirectional mode is enabled, next I and the following P
1040 * frame will be sent together. Unfortunately the approach below seems
1041 * to be the only way to handle the B-frames mode.
1042 * That's exactly the same Intel decoders do.
1044 if (avctx->codec_id == AV_CODEC_ID_INDEO4 &&
1045 ctx->frame_type == 0/*FRAMETYPE_INTRA*/) {
1046 // skip version string
1047 while (get_bits(&ctx->gb, 8)) {
1048 if (get_bits_left(&ctx->gb) < 8)
1049 return AVERROR_INVALIDDATA;
1052 skip_bits_long(&ctx->gb, 64); // skip padding, TODO: implement correct 8-bytes alignment
1053 if (get_bits_left(&ctx->gb) > 18 && show_bits(&ctx->gb, 18) == 0x3FFF8)
1054 av_log(avctx, AV_LOG_ERROR, "Buffer contains IP frames!\n");
1057 if (!ctx->is_nonnull_frame(ctx))
1060 result = ff_set_dimensions(avctx, ctx->planes[0].width, ctx->planes[0].height);
1064 if ((result = ff_get_buffer(avctx, frame, 0)) < 0)
1067 if (ctx->is_scalable) {
1068 if (avctx->codec_id == AV_CODEC_ID_INDEO4)
1069 ff_ivi_recompose_haar(&ctx->planes[0], frame->data[0], frame->linesize[0]);
1071 ff_ivi_recompose53 (&ctx->planes[0], frame->data[0], frame->linesize[0]);
1073 ivi_output_plane(&ctx->planes[0], frame->data[0], frame->linesize[0]);
1076 ivi_output_plane(&ctx->planes[2], frame->data[1], frame->linesize[1]);
1077 ivi_output_plane(&ctx->planes[1], frame->data[2], frame->linesize[2]);
1085 * Close Indeo5 decoder and clean up its context.
1087 av_cold int ff_ivi_decode_close(AVCodecContext *avctx)
1089 IVI45DecContext *ctx = avctx->priv_data;
1091 ivi_free_buffers(&ctx->planes[0]);
1093 if (ctx->mb_vlc.cust_tab.table)
1094 ff_free_vlc(&ctx->mb_vlc.cust_tab);
1096 #if IVI4_STREAM_ANALYSER
1097 if (avctx->codec_id == AV_CODEC_ID_INDEO4) {
1098 if (ctx->is_scalable)
1099 av_log(avctx, AV_LOG_ERROR, "This video uses scalability mode!\n");
1100 if (ctx->uses_tiling)
1101 av_log(avctx, AV_LOG_ERROR, "This video uses local decoding!\n");
1102 if (ctx->has_b_frames)
1103 av_log(avctx, AV_LOG_ERROR, "This video contains B-frames!\n");
1104 if (ctx->has_transp)
1105 av_log(avctx, AV_LOG_ERROR, "Transparency mode is enabled!\n");
1107 av_log(avctx, AV_LOG_ERROR, "This video uses Haar transform!\n");
1108 if (ctx->uses_fullpel)
1109 av_log(avctx, AV_LOG_ERROR, "This video uses fullpel motion vectors!\n");
1118 * Scan patterns shared between indeo4 and indeo5
1120 const uint8_t ff_ivi_vertical_scan_8x8[64] = {
1121 0, 8, 16, 24, 32, 40, 48, 56,
1122 1, 9, 17, 25, 33, 41, 49, 57,
1123 2, 10, 18, 26, 34, 42, 50, 58,
1124 3, 11, 19, 27, 35, 43, 51, 59,
1125 4, 12, 20, 28, 36, 44, 52, 60,
1126 5, 13, 21, 29, 37, 45, 53, 61,
1127 6, 14, 22, 30, 38, 46, 54, 62,
1128 7, 15, 23, 31, 39, 47, 55, 63
1131 const uint8_t ff_ivi_horizontal_scan_8x8[64] = {
1132 0, 1, 2, 3, 4, 5, 6, 7,
1133 8, 9, 10, 11, 12, 13, 14, 15,
1134 16, 17, 18, 19, 20, 21, 22, 23,
1135 24, 25, 26, 27, 28, 29, 30, 31,
1136 32, 33, 34, 35, 36, 37, 38, 39,
1137 40, 41, 42, 43, 44, 45, 46, 47,
1138 48, 49, 50, 51, 52, 53, 54, 55,
1139 56, 57, 58, 59, 60, 61, 62, 63
1142 const uint8_t ff_ivi_direct_scan_4x4[16] = {
1143 0, 1, 4, 8, 5, 2, 3, 6, 9, 12, 13, 10, 7, 11, 14, 15
1148 * Run-value (RLE) tables.
1150 const RVMapDesc ff_ivi_rvmap_tabs[9] = {
1155 {1, 1, 0, 1, 1, 0, 1, 1, 2, 2, 1, 1, 1, 1, 3, 3,
1156 1, 1, 2, 2, 1, 1, 4, 4, 1, 1, 1, 1, 2, 2, 5, 5,
1157 1, 1, 3, 3, 1, 1, 6, 6, 1, 2, 1, 2, 7, 7, 1, 1,
1158 8, 8, 1, 1, 4, 2, 1, 4, 2, 1, 3, 3, 1, 1, 1, 9,
1159 9, 1, 2, 1, 2, 1, 5, 5, 1, 1, 10, 10, 1, 1, 3, 3,
1160 2, 2, 1, 1, 11, 11, 6, 4, 4, 1, 6, 1, 2, 1, 2, 12,
1161 8, 1, 12, 7, 8, 7, 1, 16, 1, 16, 1, 3, 3, 13, 1, 13,
1162 2, 2, 1, 15, 1, 5, 14, 15, 1, 5, 14, 1, 17, 8, 17, 8,
1163 1, 4, 4, 2, 2, 1, 25, 25, 24, 24, 1, 3, 1, 3, 1, 8,
1164 6, 7, 6, 1, 18, 8, 18, 1, 7, 23, 2, 2, 23, 1, 1, 21,
1165 22, 9, 9, 22, 19, 1, 21, 5, 19, 5, 1, 33, 20, 33, 20, 8,
1166 4, 4, 1, 32, 2, 2, 8, 3, 32, 26, 3, 1, 7, 7, 26, 6,
1167 1, 6, 1, 1, 16, 1, 10, 1, 10, 2, 16, 29, 28, 2, 29, 28,
1168 1, 27, 5, 8, 5, 27, 1, 8, 3, 7, 3, 31, 41, 31, 1, 41,
1169 6, 1, 6, 7, 4, 4, 1, 1, 2, 1, 2, 11, 34, 30, 11, 1,
1170 30, 15, 15, 34, 36, 40, 36, 40, 35, 35, 37, 37, 39, 39, 38, 38},
1173 { 1, -1, 0, 2, -2, 0, 3, -3, 1, -1, 4, -4, 5, -5, 1, -1,
1174 6, -6, 2, -2, 7, -7, 1, -1, 8, -8, 9, -9, 3, -3, 1, -1,
1175 10, -10, 2, -2, 11, -11, 1, -1, 12, 4, -12, -4, 1, -1, 13, -13,
1176 1, -1, 14, -14, 2, 5, 15, -2, -5, -15, -3, 3, 16, -16, 17, 1,
1177 -1, -17, 6, 18, -6, -18, 2, -2, 19, -19, 1, -1, 20, -20, 4, -4,
1178 7, -7, 21, -21, 1, -1, 2, 3, -3, 22, -2, -22, 8, 23, -8, 1,
1179 2, -23, -1, 2, -2, -2, 24, 1, -24, -1, 25, 5, -5, 1, -25, -1,
1180 9, -9, 26, 1, -26, 3, 1, -1, 27, -3, -1, -27, 1, 3, -1, -3,
1181 28, -4, 4, 10, -10, -28, 1, -1, 1, -1, 29, 6, -29, -6, 30, -4,
1182 3, 3, -3, -30, 1, 4, -1, 31, -3, 1, 11, -11, -1, -31, 32, -1,
1183 -1, 2, -2, 1, 1, -32, 1, 4, -1, -4, 33, -1, 1, 1, -1, 5,
1184 5, -5, -33, -1, -12, 12, -5, -7, 1, 1, 7, 34, 4, -4, -1, 4,
1185 -34, -4, 35, 36, -2, -35, -2, -36, 2, 13, 2, -1, 1, -13, 1, -1,
1186 37, 1, -5, 6, 5, -1, 38, -6, -8, 5, 8, -1, 1, 1, -37, -1,
1187 5, 39, -5, -5, 6, -6, -38, -39, -14, 40, 14, 2, 1, 1, -2, -40,
1188 -1, -2, 2, -1, -1, -1, 1, 1, 1, -1, 1, -1, 1, -1, 1, -1}
1194 {0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 8, 6, 8, 7,
1195 7, 9, 9, 10, 10, 11, 11, 1, 12, 1, 12, 13, 13, 16, 14, 16,
1196 14, 15, 15, 17, 17, 18, 0, 18, 19, 20, 21, 19, 22, 21, 20, 22,
1197 25, 24, 2, 25, 24, 23, 23, 2, 26, 28, 26, 28, 29, 27, 29, 27,
1198 33, 33, 1, 32, 1, 3, 32, 30, 36, 3, 36, 30, 31, 31, 35, 34,
1199 37, 41, 34, 35, 37, 4, 41, 4, 49, 8, 8, 49, 40, 38, 5, 38,
1200 40, 39, 5, 39, 42, 43, 42, 7, 57, 6, 43, 44, 6, 50, 7, 44,
1201 57, 48, 50, 48, 45, 45, 46, 47, 51, 46, 47, 58, 1, 51, 58, 1,
1202 52, 59, 53, 9, 52, 55, 55, 59, 53, 56, 54, 56, 54, 9, 64, 64,
1203 60, 63, 60, 63, 61, 62, 61, 62, 2, 10, 2, 10, 11, 1, 11, 13,
1204 12, 1, 12, 13, 16, 16, 8, 8, 14, 3, 3, 15, 14, 15, 4, 4,
1205 1, 17, 17, 5, 1, 7, 7, 5, 6, 1, 2, 2, 6, 22, 1, 25,
1206 21, 22, 8, 24, 1, 21, 25, 24, 8, 18, 18, 23, 9, 20, 23, 33,
1207 29, 33, 20, 1, 19, 1, 29, 36, 9, 36, 19, 41, 28, 57, 32, 3,
1208 28, 3, 1, 27, 49, 49, 1, 32, 26, 26, 2, 4, 4, 7, 57, 41,
1209 2, 7, 10, 5, 37, 16, 10, 27, 8, 8, 13, 16, 37, 13, 1, 5},
1212 {0, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, 1, -1, -1, 1,
1213 -1, 1, -1, 1, -1, 1, -1, 2, 1, -2, -1, 1, -1, 1, 1, -1,
1214 -1, 1, -1, 1, -1, 1, 0, -1, 1, 1, 1, -1, 1, -1, -1, -1,
1215 1, 1, 2, -1, -1, 1, -1, -2, 1, 1, -1, -1, 1, 1, -1, -1,
1216 1, -1, 3, 1, -3, 2, -1, 1, 1, -2, -1, -1, -1, 1, 1, 1,
1217 1, 1, -1, -1, -1, 2, -1, -2, 1, 2, -2, -1, 1, 1, 2, -1,
1218 -1, 1, -2, -1, 1, 1, -1, 2, 1, 2, -1, 1, -2, -1, -2, -1,
1219 -1, 1, 1, -1, 1, -1, 1, 1, 1, -1, -1, 1, 4, -1, -1, -4,
1220 1, 1, 1, 2, -1, -1, 1, -1, -1, 1, -1, -1, 1, -2, 1, -1,
1221 1, 1, -1, -1, 1, 1, -1, -1, 3, 2, -3, -2, 2, 5, -2, 2,
1222 2, -5, -2, -2, -2, 2, -3, 3, 2, 3, -3, 2, -2, -2, 3, -3,
1223 6, 2, -2, 3, -6, 3, -3, -3, 3, 7, -4, 4, -3, 2, -7, 2,
1224 2, -2, -4, 2, 8, -2, -2, -2, 4, 2, -2, 2, 3, 2, -2, -2,
1225 2, 2, -2, -8, -2, 9, -2, 2, -3, -2, 2, -2, 2, 2, 2, 4,
1226 -2, -4, 10, 2, 2, -2, -9, -2, 2, -2, 5, 4, -4, 4, -2, 2,
1227 -5, -4, -3, 4, 2, -3, 3, -2, -5, 5, 3, 3, -2, -3, -10, -4}
1233 {1, 1, 0, 2, 2, 1, 1, 3, 3, 4, 4, 0, 1, 1, 5, 5,
1234 2, 2, 6, 6, 7, 7, 1, 8, 1, 8, 3, 3, 9, 9, 1, 2,
1235 2, 1, 4, 10, 4, 10, 11, 11, 1, 5, 12, 12, 1, 5, 13, 13,
1236 3, 3, 6, 6, 2, 2, 14, 14, 16, 16, 15, 7, 15, 8, 8, 7,
1237 1, 1, 17, 17, 4, 4, 1, 1, 18, 18, 2, 2, 5, 5, 25, 3,
1238 9, 3, 25, 9, 19, 24, 19, 24, 1, 21, 20, 1, 21, 22, 20, 22,
1239 23, 23, 8, 6, 33, 6, 8, 33, 7, 7, 26, 26, 1, 32, 1, 32,
1240 28, 4, 28, 10, 29, 27, 27, 10, 41, 4, 29, 2, 2, 41, 36, 31,
1241 49, 31, 34, 30, 34, 36, 30, 35, 1, 49, 11, 5, 35, 11, 1, 3,
1242 3, 5, 37, 37, 8, 40, 8, 40, 12, 12, 42, 42, 1, 38, 16, 57,
1243 1, 6, 16, 39, 38, 6, 7, 7, 13, 13, 39, 43, 2, 43, 57, 2,
1244 50, 9, 44, 9, 50, 4, 15, 48, 44, 4, 1, 15, 48, 14, 14, 1,
1245 45, 45, 8, 3, 5, 8, 51, 47, 3, 46, 46, 47, 5, 51, 1, 17,
1246 17, 58, 1, 58, 2, 52, 52, 2, 53, 7, 59, 6, 6, 56, 53, 55,
1247 7, 55, 1, 54, 59, 56, 54, 10, 1, 10, 4, 60, 1, 60, 8, 4,
1248 8, 64, 64, 61, 1, 63, 3, 63, 62, 61, 5, 11, 5, 3, 11, 62},
1251 { 1, -1, 0, 1, -1, 2, -2, 1, -1, 1, -1, 0, 3, -3, 1, -1,
1252 2, -2, 1, -1, 1, -1, 4, 1, -4, -1, 2, -2, 1, -1, 5, 3,
1253 -3, -5, 2, 1, -2, -1, 1, -1, 6, 2, 1, -1, -6, -2, 1, -1,
1254 3, -3, 2, -2, 4, -4, 1, -1, 1, -1, 1, 2, -1, 2, -2, -2,
1255 7, -7, 1, -1, 3, -3, 8, -8, 1, -1, 5, -5, 3, -3, 1, 4,
1256 2, -4, -1, -2, 1, 1, -1, -1, 9, 1, 1, -9, -1, 1, -1, -1,
1257 1, -1, 3, -3, 1, 3, -3, -1, 3, -3, 1, -1, 10, 1, -10, -1,
1258 1, 4, -1, 2, 1, -1, 1, -2, 1, -4, -1, 6, -6, -1, 1, 1,
1259 1, -1, 1, 1, -1, -1, -1, 1, 11, -1, -2, 4, -1, 2, -11, 5,
1260 -5, -4, -1, 1, 4, 1, -4, -1, -2, 2, 1, -1, 12, 1, -2, 1,
1261 -12, 4, 2, 1, -1, -4, 4, -4, 2, -2, -1, 1, 7, -1, -1, -7,
1262 -1, -3, 1, 3, 1, 5, 2, 1, -1, -5, 13, -2, -1, 2, -2, -13,
1263 1, -1, 5, 6, 5, -5, 1, 1, -6, 1, -1, -1, -5, -1, 14, 2,
1264 -2, 1, -14, -1, 8, 1, -1, -8, 1, 5, 1, 5, -5, 1, -1, 1,
1265 -5, -1, 15, 1, -1, -1, -1, 3, -15, -3, 6, 1, 16, -1, 6, -6,
1266 -6, 1, -1, 1, -16, 1, 7, -1, 1, -1, -6, -3, 6, -7, 3, -1}
1272 {0, 1, 1, 2, 2, 3, 3, 4, 4, 1, 1, 5, 5, 6, 6, 7,
1273 7, 8, 8, 9, 9, 2, 2, 10, 10, 1, 1, 11, 11, 12, 12, 3,
1274 3, 13, 13, 0, 14, 14, 16, 15, 16, 15, 4, 4, 17, 1, 17, 1,
1275 5, 5, 18, 18, 2, 2, 6, 6, 8, 19, 7, 8, 7, 19, 20, 20,
1276 21, 21, 22, 24, 22, 24, 23, 23, 1, 1, 25, 25, 3, 3, 26, 26,
1277 9, 9, 27, 27, 28, 28, 33, 29, 4, 33, 29, 1, 4, 1, 32, 32,
1278 2, 2, 31, 10, 30, 10, 30, 31, 34, 34, 5, 5, 36, 36, 35, 41,
1279 35, 11, 41, 11, 37, 1, 8, 8, 37, 6, 1, 6, 40, 7, 7, 40,
1280 12, 38, 12, 39, 39, 38, 49, 13, 49, 13, 3, 42, 3, 42, 16, 16,
1281 43, 43, 14, 14, 1, 1, 44, 15, 44, 15, 2, 2, 57, 48, 50, 48,
1282 57, 50, 4, 45, 45, 4, 46, 47, 47, 46, 1, 51, 1, 17, 17, 51,
1283 8, 9, 9, 5, 58, 8, 58, 5, 52, 52, 55, 56, 53, 56, 55, 59,
1284 59, 53, 54, 1, 6, 54, 7, 7, 6, 1, 2, 3, 2, 3, 64, 60,
1285 60, 10, 10, 64, 61, 62, 61, 63, 1, 63, 62, 1, 18, 24, 18, 4,
1286 25, 4, 8, 21, 21, 1, 24, 22, 25, 22, 8, 11, 19, 11, 23, 1,
1287 20, 23, 19, 20, 5, 12, 5, 1, 16, 2, 12, 13, 2, 13, 1, 16},
1290 { 0, 1, -1, 1, -1, 1, -1, 1, -1, 2, -2, 1, -1, 1, -1, 1,
1291 -1, 1, -1, 1, -1, 2, -2, 1, -1, 3, -3, 1, -1, 1, -1, 2,
1292 -2, 1, -1, 0, 1, -1, 1, 1, -1, -1, 2, -2, 1, 4, -1, -4,
1293 2, -2, 1, -1, -3, 3, 2, -2, 2, 1, 2, -2, -2, -1, 1, -1,
1294 1, -1, 1, 1, -1, -1, 1, -1, 5, -5, 1, -1, 3, -3, 1, -1,
1295 2, -2, 1, -1, 1, -1, 1, 1, 3, -1, -1, 6, -3, -6, -1, 1,
1296 4, -4, 1, 2, 1, -2, -1, -1, 1, -1, 3, -3, 1, -1, 1, 1,
1297 -1, 2, -1, -2, 1, 7, -3, 3, -1, 3, -7, -3, 1, -3, 3, -1,
1298 2, 1, -2, 1, -1, -1, 1, 2, -1, -2, -4, -1, 4, 1, 2, -2,
1299 1, -1, -2, 2, 8, -8, -1, 2, 1, -2, -5, 5, 1, -1, -1, 1,
1300 -1, 1, 4, -1, 1, -4, -1, -1, 1, 1, 9, 1, -9, 2, -2, -1,
1301 -4, 3, -3, -4, -1, 4, 1, 4, 1, -1, 1, -1, 1, 1, -1, 1,
1302 -1, -1, -1, 10, 4, 1, 4, -4, -4, -10, 6, 5, -6, -5, 1, -1,
1303 1, 3, -3, -1, 1, -1, -1, -1, 11, 1, 1, -11, -2, -2, 2, 5,
1304 -2, -5, -5, 2, -2, 12, 2, -2, 2, 2, 5, -3, -2, 3, -2, -12,
1305 -2, 2, 2, 2, -5, 3, 5, 13, -3, 7, -3, -3, -7, 3, -13, 3}
1311 {0, 1, 1, 1, 2, 2, 1, 3, 3, 1, 1, 1, 4, 4, 1, 5,
1312 2, 1, 5, 2, 1, 1, 6, 6, 1, 1, 1, 1, 1, 7, 3, 1,
1313 2, 3, 0, 1, 2, 7, 1, 1, 1, 8, 1, 1, 8, 1, 1, 1,
1314 9, 1, 9, 1, 2, 1, 1, 2, 1, 1, 10, 4, 1, 10, 1, 4,
1315 1, 1, 1, 1, 1, 3, 1, 1, 1, 3, 2, 1, 5, 1, 1, 1,
1316 2, 5, 1, 11, 1, 11, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1317 2, 1, 6, 1, 6, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 12,
1318 3, 1, 12, 1, 1, 1, 2, 1, 1, 3, 1, 1, 1, 1, 1, 1,
1319 4, 1, 1, 1, 2, 1, 1, 4, 1, 1, 1, 1, 1, 1, 2, 1,
1320 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 2, 1, 1, 5,
1321 1, 1, 1, 1, 1, 7, 1, 7, 1, 1, 2, 3, 1, 1, 1, 1,
1322 5, 1, 1, 1, 1, 1, 1, 2, 13, 1, 1, 1, 1, 1, 1, 1,
1323 1, 1, 1, 1, 1, 1, 1, 1, 13, 2, 1, 1, 4, 1, 1, 1,
1324 3, 1, 6, 1, 1, 1, 14, 1, 1, 1, 1, 1, 14, 6, 1, 1,
1325 1, 1, 15, 2, 4, 1, 2, 3, 15, 1, 1, 1, 8, 1, 1, 8,
1326 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1},
1329 { 0, 1, -1, 2, 1, -1, -2, 1, -1, 3, -3, 4, 1, -1, -4, 1,
1330 2, 5, -1, -2, -5, 6, 1, -1, -6, 7, -7, 8, -8, 1, 2, 9,
1331 3, -2, 0, -9, -3, -1, 10, -10, 11, 1, -11, 12, -1, -12, 13, -13,
1332 1, 14, -1, -14, 4, 15, -15, -4, 16, -16, 1, 2, 17, -1, -17, -2,
1333 18, -18, 19, -19, 20, 3, -20, 21, -21, -3, 5, 22, 2, -22, -23, 23,
1334 -5, -2, 24, 1, -24, -1, 25, -25, 26, -26, -27, 27, 28, 29, -28, -29,
1335 6, 30, 2, -31, -2, -30, 31, -6, -32, 32, 33, -33, 34, -35, -34, 1,
1336 4, -36, -1, 35, 37, 36, 7, -37, 38, -4, -38, 39, 41, 40, -40, -39,
1337 3, 42, -43, -41, -7, -42, 43, -3, 44, -44, 45, -45, 46, 47, 8, -47,
1338 -48, -46, 50, -50, 48, 49, 51, -49, 52, -52, 5, -51, -8, -53, 53, 3,
1339 -56, 56, 55, 54, -54, 2, 60, -2, -55, 58, 9, -5, 59, 57, -57, -63,
1340 -3, -58, -60, -61, 61, -59, -62, -9, 1, 64, 62, 69, -64, 63, 65, -67,
1341 -68, 66, -65, 68, -66, -69, 67, -70, -1, 10, 71, -71, 4, 73, 72, 70,
1342 6, -76, -3, 74, -78, -74, 1, 78, 80, -72, -75, 76, -1, 3, -73, 79,
1343 75, 77, 1, 11, -4, -79, -10, -6, -1, -77, -83, -80, 2, 81, -84, -2,
1344 83, -81, 82, -82, 84, -87, -86, 85, -11, -85, 86, -89, 87, -88, 88, 89}
1350 {1, 1, 0, 2, 1, 2, 1, 3, 3, 1, 1, 4, 4, 2, 2, 1,
1351 1, 5, 5, 6, 1, 6, 1, 7, 7, 3, 3, 2, 8, 2, 8, 1,
1352 1, 0, 9, 9, 1, 1, 10, 4, 10, 4, 11, 11, 2, 1, 2, 1,
1353 12, 12, 3, 3, 1, 1, 13, 5, 5, 13, 14, 1, 1, 14, 2, 2,
1354 6, 6, 15, 1, 1, 15, 16, 4, 7, 16, 4, 7, 1, 1, 3, 3,
1355 8, 8, 2, 2, 1, 1, 17, 17, 1, 1, 18, 18, 5, 5, 2, 2,
1356 1, 1, 9, 19, 9, 19, 20, 3, 3, 20, 1, 10, 21, 1, 10, 4,
1357 4, 21, 22, 6, 6, 22, 1, 1, 23, 24, 2, 2, 23, 24, 11, 1,
1358 1, 11, 7, 25, 7, 1, 1, 25, 8, 8, 3, 26, 3, 1, 12, 2,
1359 2, 26, 1, 12, 5, 5, 27, 4, 1, 4, 1, 27, 28, 1, 28, 13,
1360 1, 13, 2, 29, 2, 1, 32, 6, 1, 30, 14, 29, 14, 6, 3, 31,
1361 3, 1, 30, 1, 32, 31, 33, 9, 33, 1, 1, 7, 9, 7, 2, 2,
1362 1, 1, 4, 36, 34, 4, 5, 10, 10, 5, 34, 1, 1, 35, 8, 8,
1363 36, 3, 35, 1, 15, 3, 2, 1, 16, 15, 16, 2, 37, 1, 37, 1,
1364 1, 1, 6, 6, 38, 1, 38, 11, 1, 39, 39, 40, 11, 2, 41, 4,
1365 40, 1, 2, 4, 1, 1, 1, 41, 3, 1, 3, 1, 5, 7, 5, 7},
1368 { 1, -1, 0, 1, 2, -1, -2, 1, -1, 3, -3, 1, -1, 2, -2, 4,
1369 -4, 1, -1, 1, 5, -1, -5, 1, -1, 2, -2, 3, 1, -3, -1, 6,
1370 -6, 0, 1, -1, 7, -7, 1, 2, -1, -2, 1, -1, 4, 8, -4, -8,
1371 1, -1, 3, -3, 9, -9, 1, 2, -2, -1, 1, 10, -10, -1, 5, -5,
1372 2, -2, 1, 11, -11, -1, 1, 3, 2, -1, -3, -2, 12, -12, 4, -4,
1373 2, -2, -6, 6, 13, -13, 1, -1, 14, -14, 1, -1, 3, -3, 7, -7,
1374 15, -15, 2, 1, -2, -1, 1, 5, -5, -1, -16, 2, 1, 16, -2, 4,
1375 -4, -1, 1, 3, -3, -1, 17, -17, 1, 1, -8, 8, -1, -1, 2, 18,
1376 -18, -2, 3, 1, -3, 19, -19, -1, 3, -3, 6, 1, -6, 20, 2, 9,
1377 -9, -1, -20, -2, 4, -4, 1, -5, 21, 5, -21, -1, 1, -22, -1, 2,
1378 22, -2, 10, 1, -10, 23, 1, 4, -23, 1, 2, -1, -2, -4, -7, 1,
1379 7, -24, -1, 24, -1, -1, 1, 3, -1, -25, 25, 4, -3, -4, 11, -11,
1380 26, -26, 6, 1, 1, -6, -5, -3, 3, 5, -1, -27, 27, 1, 4, -4,
1381 -1, -8, -1, 28, 2, 8, -12, -28, -2, -2, 2, 12, -1, 29, 1, -29,
1382 30, -30, 5, -5, 1, -31, -1, 3, 31, -1, 1, 1, -3, -13, 1, -7,
1383 -1, -32, 13, 7, 32, 33, -33, -1, -9, -34, 9, 34, -6, 5, 6, -5}
1389 {1, 1, 0, 1, 1, 2, 2, 1, 1, 3, 3, 1, 1, 0, 2, 2,
1390 4, 1, 4, 1, 1, 1, 5, 5, 1, 1, 6, 6, 2, 2, 1, 1,
1391 3, 3, 7, 7, 1, 1, 8, 8, 1, 1, 2, 2, 1, 9, 1, 9,
1392 4, 4, 10, 1, 1, 10, 1, 1, 11, 11, 3, 3, 1, 2, 1, 2,
1393 1, 1, 12, 12, 5, 5, 1, 1, 13, 1, 1, 13, 2, 2, 1, 1,
1394 6, 6, 1, 1, 4, 14, 4, 14, 3, 1, 3, 1, 1, 1, 15, 7,
1395 15, 2, 2, 7, 1, 1, 1, 8, 1, 8, 16, 16, 1, 1, 1, 1,
1396 2, 1, 1, 2, 1, 1, 3, 5, 5, 3, 4, 1, 1, 4, 1, 1,
1397 17, 17, 9, 1, 1, 9, 2, 2, 1, 1, 10, 10, 1, 6, 1, 1,
1398 6, 18, 1, 1, 18, 1, 1, 1, 2, 2, 3, 1, 3, 1, 1, 1,
1399 4, 1, 19, 1, 19, 7, 1, 1, 20, 1, 4, 20, 1, 7, 11, 2,
1400 1, 11, 21, 2, 8, 5, 1, 8, 1, 5, 21, 1, 1, 1, 22, 1,
1401 1, 22, 1, 1, 3, 3, 1, 23, 2, 12, 24, 1, 1, 2, 1, 1,
1402 12, 23, 1, 1, 24, 1, 1, 1, 4, 1, 1, 1, 2, 1, 6, 6,
1403 4, 2, 1, 1, 1, 1, 1, 1, 1, 14, 13, 3, 1, 25, 9, 25,
1404 14, 1, 9, 3, 13, 1, 1, 1, 1, 1, 10, 1, 1, 2, 10, 2},
1407 {-20, -1, 0, 2, -2, 1, -1, 3, -3, 1, -1, 4, -4, 0, 2, -2,
1408 1, 5, -1, -5, 6, -6, 1, -1, 7, -7, 1, -1, 3, -3, 8, -8,
1409 2, -2, 1, -1, 9, -9, 1, -1, 10, -10, 4, -4, 11, 1, -11, -1,
1410 2, -2, 1, 12, -12, -1, 13, -13, 1, -1, 3, -3, 14, 5, -14, -5,
1411 -15, 15, -1, 1, 2, -2, 16, -16, 1, 17, -17, -1, 6, -6, 18, -18,
1412 2, -2, -19, 19, -3, 1, 3, -1, 4, 20, -4, 1, -21, 21, 1, 2,
1413 -1, -7, 7, -2, 22, -22, 23, 2, -23, -2, 1, -1, -24, 24, -25, 25,
1414 -8, -26, 26, 8, -27, 27, 5, 3, -3, -5, -4, 28, -28, 4, 29, -29,
1415 1, -1, -2, -30, 30, 2, 9, -9, -31, 31, 2, -2, -32, 3, 32, -33,
1416 -3, 1, 33, -34, -1, 34, -35, 35, -10, 10, -6, 36, 6, -36, 37, -37,
1417 -5, 38, 1, -38, -1, 3, 39, -39, -1, 40, 5, 1, -40, -3, 2, -11,
1418 -41, -2, 1, 11, -3, -4, 41, 3, 42, 4, -1, -43, -42, 43, 1, -44,
1419 45, -1, 44, -45, -7, 7, -46, 1, -12, 2, 1, -47, 46, 12, 47, 48,
1420 -2, -1, -48, 49, -1, -50, -49, 50, -6, -51, 51, 52, -13, 53, -4, 4,
1421 6, 13, -53, -52, -54, 55, 54, -55, -56, -2, 2, -8, 56, 1, -3, -1,
1422 2, 58, 3, 8, -2, 57, -58, -60, -59, -57, -3, 60, 59, -14, 3, 14}
1428 {1, 1, 0, 2, 2, 1, 1, 3, 3, 4, 4, 5, 5, 1, 1, 6,
1429 6, 2, 2, 7, 7, 8, 8, 1, 1, 3, 3, 9, 9, 10, 10, 1,
1430 1, 2, 2, 4, 4, 11, 0, 11, 12, 12, 13, 13, 1, 1, 5, 5,
1431 14, 14, 15, 16, 15, 16, 3, 3, 1, 6, 1, 6, 2, 2, 7, 7,
1432 8, 8, 17, 17, 1, 1, 4, 4, 18, 18, 2, 2, 1, 19, 1, 20,
1433 19, 20, 21, 21, 3, 3, 22, 22, 5, 5, 24, 1, 1, 23, 9, 23,
1434 24, 9, 2, 2, 10, 1, 1, 10, 6, 6, 25, 4, 4, 25, 7, 7,
1435 26, 8, 1, 8, 3, 1, 26, 3, 11, 11, 27, 27, 2, 28, 1, 2,
1436 28, 1, 12, 12, 5, 5, 29, 13, 13, 29, 32, 1, 1, 33, 31, 30,
1437 32, 4, 30, 33, 4, 31, 3, 14, 1, 1, 3, 34, 34, 2, 2, 14,
1438 6, 6, 35, 36, 35, 36, 1, 15, 1, 16, 16, 15, 7, 9, 7, 9,
1439 37, 8, 8, 37, 1, 1, 39, 2, 38, 39, 2, 40, 5, 38, 40, 5,
1440 3, 3, 4, 4, 10, 10, 1, 1, 1, 1, 41, 2, 41, 2, 6, 6,
1441 1, 1, 11, 42, 11, 43, 3, 42, 3, 17, 4, 43, 1, 17, 7, 1,
1442 8, 44, 4, 7, 44, 5, 8, 2, 5, 1, 2, 48, 45, 1, 12, 45,
1443 12, 48, 13, 13, 1, 9, 9, 46, 1, 46, 47, 47, 49, 18, 18, 49},
1446 { 1, -1, 0, 1, -1, 2, -2, 1, -1, 1, -1, 1, -1, 3, -3, 1,
1447 -1, -2, 2, 1, -1, 1, -1, 4, -4, -2, 2, 1, -1, 1, -1, 5,
1448 -5, -3, 3, 2, -2, 1, 0, -1, 1, -1, 1, -1, 6, -6, 2, -2,
1449 1, -1, 1, 1, -1, -1, -3, 3, 7, 2, -7, -2, -4, 4, 2, -2,
1450 2, -2, 1, -1, 8, -8, 3, -3, 1, -1, -5, 5, 9, 1, -9, 1,
1451 -1, -1, 1, -1, -4, 4, 1, -1, 3, -3, 1, -10, 10, 1, 2, -1,
1452 -1, -2, 6, -6, 2, 11, -11, -2, 3, -3, 1, -4, 4, -1, 3, -3,
1453 1, 3, 12, -3, -5, -12, -1, 5, 2, -2, 1, -1, -7, 1, 13, 7,
1454 -1, -13, 2, -2, 4, -4, 1, 2, -2, -1, 1, 14, -14, 1, 1, 1,
1455 -1, -5, -1, -1, 5, -1, -6, 2, -15, 15, 6, 1, -1, -8, 8, -2,
1456 -4, 4, 1, 1, -1, -1, 16, 2, -16, -2, 2, -2, 4, 3, -4, -3,
1457 -1, -4, 4, 1, -17, 17, -1, -9, 1, 1, 9, 1, -5, -1, -1, 5,
1458 -7, 7, 6, -6, 3, -3, 18, -18, 19, -19, 1, -10, -1, 10, -5, 5,
1459 20, -20, -3, 1, 3, 1, 8, -1, -8, 2, 7, -1, -21, -2, 5, 21,
1460 5, -1, -7, -5, 1, -6, -5, -11, 6, 22, 11, 1, 1, -22, -3, -1,
1461 3, -1, 3, -3, -23, 4, -4, 1, 23, -1, 1, -1, 1, -2, 2, -1}
1467 {1, 1, 1, 1, 0, 2, 2, 1, 1, 3, 3, 0, 1, 1, 2, 2,
1468 4, 4, 1, 1, 5, 5, 1, 1, 2, 2, 3, 3, 6, 6, 1, 1,
1469 7, 7, 8, 1, 8, 2, 2, 1, 4, 4, 1, 3, 1, 3, 9, 9,
1470 2, 2, 1, 5, 1, 5, 10, 10, 1, 1, 11, 11, 3, 6, 3, 4,
1471 4, 6, 2, 2, 1, 12, 1, 12, 7, 13, 7, 13, 1, 1, 8, 8,
1472 2, 2, 14, 14, 16, 15, 16, 5, 5, 1, 3, 15, 1, 3, 4, 4,
1473 1, 1, 17, 17, 2, 2, 6, 6, 1, 18, 1, 18, 22, 21, 22, 21,
1474 25, 24, 25, 19, 9, 20, 9, 23, 19, 24, 20, 3, 23, 7, 3, 1,
1475 1, 7, 28, 26, 29, 5, 28, 26, 5, 8, 29, 4, 8, 27, 2, 2,
1476 4, 27, 1, 1, 10, 36, 10, 33, 33, 36, 30, 1, 32, 32, 1, 30,
1477 6, 31, 31, 35, 3, 6, 11, 11, 3, 2, 35, 2, 34, 1, 34, 1,
1478 37, 37, 12, 7, 12, 5, 41, 5, 4, 7, 1, 8, 13, 4, 1, 41,
1479 13, 38, 8, 38, 9, 1, 40, 40, 9, 1, 39, 2, 2, 49, 39, 42,
1480 3, 3, 14, 16, 49, 14, 16, 42, 43, 43, 6, 6, 15, 1, 1, 15,
1481 44, 44, 1, 1, 50, 48, 4, 5, 4, 7, 5, 2, 10, 10, 48, 7,
1482 50, 45, 2, 1, 45, 8, 8, 1, 46, 46, 3, 47, 47, 3, 1, 1},
1485 { 1, -1, 2, -2, 0, 1, -1, 3, -3, 1, -1, 0, 4, -4, 2, -2,
1486 1, -1, 5, -5, 1, -1, 6, -6, 3, -3, 2, -2, 1, -1, 7, -7,
1487 1, -1, 1, 8, -1, 4, -4, -8, 2, -2, 9, 3, -9, -3, 1, -1,
1488 5, -5, 10, 2, -10, -2, 1, -1, 11, -11, 1, -1, -4, 2, 4, 3,
1489 -3, -2, 6, -6, 12, 1, -12, -1, 2, 1, -2, -1, 13, -13, 2, -2,
1490 7, -7, 1, -1, 1, 1, -1, 3, -3, 14, 5, -1, -14, -5, 4, -4,
1491 15, -15, 1, -1, 8, -8, -3, 3, 16, 1, -16, -1, 1, 1, -1, -1,
1492 1, 1, -1, 1, 2, 1, -2, 1, -1, -1, -1, 6, -1, 3, -6, 17,
1493 -17, -3, 1, 1, 1, 4, -1, -1, -4, 3, -1, 5, -3, -1, -9, 9,
1494 -5, 1, 18, -18, 2, 1, -2, 1, -1, -1, 1, 19, -1, 1, -19, -1,
1495 4, 1, -1, 1, 7, -4, -2, 2, -7, 10, -1, -10, 1, 20, -1, -20,
1496 1, -1, 2, 4, -2, 5, 1, -5, 6, -4, 21, 4, 2, -6, -21, -1,
1497 -2, 1, -4, -1, -3, 22, -1, 1, 3, -22, -1, 11, -11, 1, 1, 1,
1498 8, -8, 2, 2, -1, -2, -2, -1, 1, -1, -5, 5, 2, 23, -23, -2,
1499 1, -1, 24, -24, -1, -1, 7, 6, -7, 5, -6, 12, -3, 3, 1, -5,
1500 1, 1, -12, 25, -1, -5, 5, -25, -1, 1, 9, 1, -1, -9, 26, -26}