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
31 #define BITSTREAM_READER_LE
32 #include "libavutil/attributes.h"
33 #include "libavutil/timer.h"
38 #include "ivi_common.h"
42 * These are 2x8 predefined Huffman codebooks for coding macroblock/block
43 * signals. They are specified using "huffman descriptors" in order to
44 * avoid huge static tables. The decoding tables will be generated at
45 * startup from these descriptors.
47 /** static macroblock huffman tables */
48 static const IVIHuffDesc ivi_mb_huff_desc[8] = {
49 {8, {0, 4, 5, 4, 4, 4, 6, 6}},
50 {12, {0, 2, 2, 3, 3, 3, 3, 5, 3, 2, 2, 2}},
51 {12, {0, 2, 3, 4, 3, 3, 3, 3, 4, 3, 2, 2}},
52 {12, {0, 3, 4, 4, 3, 3, 3, 3, 3, 2, 2, 2}},
53 {13, {0, 4, 4, 3, 3, 3, 3, 2, 3, 3, 2, 1, 1}},
54 {9, {0, 4, 4, 4, 4, 3, 3, 3, 2}},
55 {10, {0, 4, 4, 4, 4, 3, 3, 2, 2, 2}},
56 {12, {0, 4, 4, 4, 3, 3, 2, 3, 2, 2, 2, 2}}
59 /** static block huffman tables */
60 static const IVIHuffDesc ivi_blk_huff_desc[8] = {
61 {10, {1, 2, 3, 4, 4, 7, 5, 5, 4, 1}},
62 {11, {2, 3, 4, 4, 4, 7, 5, 4, 3, 3, 2}},
63 {12, {2, 4, 5, 5, 5, 5, 6, 4, 4, 3, 1, 1}},
64 {13, {3, 3, 4, 4, 5, 6, 6, 4, 4, 3, 2, 1, 1}},
65 {11, {3, 4, 4, 5, 5, 5, 6, 5, 4, 2, 2}},
66 {13, {3, 4, 5, 5, 5, 5, 6, 4, 3, 3, 2, 1, 1}},
67 {13, {3, 4, 5, 5, 5, 6, 5, 4, 3, 3, 2, 1, 1}},
68 {9, {3, 4, 4, 5, 5, 5, 6, 5, 5}}
71 static VLC ivi_mb_vlc_tabs [8]; ///< static macroblock Huffman tables
72 static VLC ivi_blk_vlc_tabs[8]; ///< static block Huffman tables
74 typedef void (*ivi_mc_func) (int16_t *buf, const int16_t *ref_buf,
75 uint32_t pitch, int mc_type);
77 static int ivi_mc(IVIBandDesc *band, ivi_mc_func mc,
78 int offs, int mv_x, int mv_y, int mc_type)
80 int ref_offs = offs + mv_y * band->pitch + mv_x;
81 int buf_size = band->pitch * band->aheight;
82 int min_size = band->pitch * (band->blk_size - 1) + band->blk_size;
83 int ref_size = (mc_type > 1) * band->pitch + (mc_type & 1);
85 av_assert0(offs >= 0 && ref_offs >= 0 && band->ref_buf);
86 av_assert0(buf_size - min_size >= offs);
87 av_assert0(buf_size - min_size - ref_size >= ref_offs);
89 mc(band->buf + offs, band->ref_buf + ref_offs, band->pitch, mc_type);
95 * Reverse "nbits" bits of the value "val" and return the result
96 * in the least significant bits.
98 static uint16_t inv_bits(uint16_t val, int nbits)
103 res = ff_reverse[val] >> (8 - nbits);
105 res = ((ff_reverse[val & 0xFF] << 8) +
106 (ff_reverse[val >> 8])) >> (16 - nbits);
112 * Generate a huffman codebook from the given descriptor
113 * and convert it into the FFmpeg VLC table.
115 * @param[in] cb pointer to codebook descriptor
116 * @param[out] vlc where to place the generated VLC table
117 * @param[in] flag flag: 1 - for static or 0 for dynamic tables
118 * @return result code: 0 - OK, -1 = error (invalid codebook descriptor)
120 static int ivi_create_huff_from_desc(const IVIHuffDesc *cb, VLC *vlc, int flag)
122 int pos, i, j, codes_per_row, prefix, not_last_row;
123 uint16_t codewords[256]; /* FIXME: move this temporal storage out? */
126 pos = 0; /* current position = 0 */
128 for (i = 0; i < cb->num_rows; i++) {
129 codes_per_row = 1 << cb->xbits[i];
130 not_last_row = (i != cb->num_rows - 1);
131 prefix = ((1 << i) - 1) << (cb->xbits[i] + not_last_row);
133 for (j = 0; j < codes_per_row; j++) {
134 if (pos >= 256) /* Some Indeo5 codebooks can have more than 256 */
135 break; /* elements, but only 256 codes are allowed! */
137 bits[pos] = i + cb->xbits[i] + not_last_row;
138 if (bits[pos] > IVI_VLC_BITS)
139 return AVERROR_INVALIDDATA; /* invalid descriptor */
141 codewords[pos] = inv_bits((prefix | j), bits[pos]);
149 /* number of codewords = pos */
150 return init_vlc(vlc, IVI_VLC_BITS, pos, bits, 1, 1, codewords, 2, 2,
151 (flag ? INIT_VLC_USE_NEW_STATIC : 0) | INIT_VLC_LE);
154 av_cold void ff_ivi_init_static_vlc(void)
157 static VLC_TYPE table_data[8192 * 16][2];
158 static int initialized_vlcs = 0;
160 if (initialized_vlcs)
162 for (i = 0; i < 8; i++) {
163 ivi_mb_vlc_tabs[i].table = table_data + i * 2 * 8192;
164 ivi_mb_vlc_tabs[i].table_allocated = 8192;
165 ivi_create_huff_from_desc(&ivi_mb_huff_desc[i],
166 &ivi_mb_vlc_tabs[i], 1);
167 ivi_blk_vlc_tabs[i].table = table_data + (i * 2 + 1) * 8192;
168 ivi_blk_vlc_tabs[i].table_allocated = 8192;
169 ivi_create_huff_from_desc(&ivi_blk_huff_desc[i],
170 &ivi_blk_vlc_tabs[i], 1);
172 initialized_vlcs = 1;
176 * Copy huffman codebook descriptors.
178 * @param[out] dst ptr to the destination descriptor
179 * @param[in] src ptr to the source descriptor
181 static void ivi_huff_desc_copy(IVIHuffDesc *dst, const IVIHuffDesc *src)
183 dst->num_rows = src->num_rows;
184 memcpy(dst->xbits, src->xbits, src->num_rows);
188 * Compare two huffman codebook descriptors.
190 * @param[in] desc1 ptr to the 1st descriptor to compare
191 * @param[in] desc2 ptr to the 2nd descriptor to compare
192 * @return comparison result: 0 - equal, 1 - not equal
194 static int ivi_huff_desc_cmp(const IVIHuffDesc *desc1,
195 const IVIHuffDesc *desc2)
197 return desc1->num_rows != desc2->num_rows ||
198 memcmp(desc1->xbits, desc2->xbits, desc1->num_rows);
201 int ff_ivi_dec_huff_desc(GetBitContext *gb, int desc_coded, int which_tab,
202 IVIHuffTab *huff_tab, AVCodecContext *avctx)
205 IVIHuffDesc new_huff;
208 /* select default table */
209 huff_tab->tab = (which_tab) ? &ivi_blk_vlc_tabs[7]
210 : &ivi_mb_vlc_tabs [7];
214 huff_tab->tab_sel = get_bits(gb, 3);
215 if (huff_tab->tab_sel == 7) {
216 /* custom huffman table (explicitly encoded) */
217 new_huff.num_rows = get_bits(gb, 4);
218 if (!new_huff.num_rows) {
219 av_log(avctx, AV_LOG_ERROR, "Empty custom Huffman table!\n");
220 return AVERROR_INVALIDDATA;
223 for (i = 0; i < new_huff.num_rows; i++)
224 new_huff.xbits[i] = get_bits(gb, 4);
226 /* Have we got the same custom table? Rebuild if not. */
227 if (ivi_huff_desc_cmp(&new_huff, &huff_tab->cust_desc) || !huff_tab->cust_tab.table) {
228 ivi_huff_desc_copy(&huff_tab->cust_desc, &new_huff);
230 if (huff_tab->cust_tab.table)
231 ff_free_vlc(&huff_tab->cust_tab);
232 result = ivi_create_huff_from_desc(&huff_tab->cust_desc,
233 &huff_tab->cust_tab, 0);
235 // reset faulty description
236 huff_tab->cust_desc.num_rows = 0;
237 av_log(avctx, AV_LOG_ERROR,
238 "Error while initializing custom vlc table!\n");
242 huff_tab->tab = &huff_tab->cust_tab;
244 /* select one of predefined tables */
245 huff_tab->tab = (which_tab) ? &ivi_blk_vlc_tabs[huff_tab->tab_sel]
246 : &ivi_mb_vlc_tabs [huff_tab->tab_sel];
253 * Free planes, bands and macroblocks buffers.
255 * @param[in] planes pointer to the array of the plane descriptors
257 static av_cold void ivi_free_buffers(IVIPlaneDesc *planes)
261 for (p = 0; p < 3; p++) {
263 for (b = 0; b < planes[p].num_bands; b++) {
264 av_freep(&planes[p].bands[b].bufs[0]);
265 av_freep(&planes[p].bands[b].bufs[1]);
266 av_freep(&planes[p].bands[b].bufs[2]);
268 if (planes[p].bands[b].blk_vlc.cust_tab.table)
269 ff_free_vlc(&planes[p].bands[b].blk_vlc.cust_tab);
270 for (t = 0; t < planes[p].bands[b].num_tiles; t++)
271 av_freep(&planes[p].bands[b].tiles[t].mbs);
272 av_freep(&planes[p].bands[b].tiles);
274 av_freep(&planes[p].bands);
275 planes[p].num_bands = 0;
279 av_cold int ff_ivi_init_planes(IVIPlaneDesc *planes, const IVIPicConfig *cfg)
282 uint32_t b_width, b_height, align_fac, width_aligned,
283 height_aligned, buf_size;
286 ivi_free_buffers(planes);
288 if (cfg->pic_width < 1 || cfg->pic_height < 1 ||
289 cfg->luma_bands < 1 || cfg->chroma_bands < 1)
290 return AVERROR_INVALIDDATA;
292 /* fill in the descriptor of the luminance plane */
293 planes[0].width = cfg->pic_width;
294 planes[0].height = cfg->pic_height;
295 planes[0].num_bands = cfg->luma_bands;
297 /* fill in the descriptors of the chrominance planes */
298 planes[1].width = planes[2].width = (cfg->pic_width + 3) >> 2;
299 planes[1].height = planes[2].height = (cfg->pic_height + 3) >> 2;
300 planes[1].num_bands = planes[2].num_bands = cfg->chroma_bands;
302 for (p = 0; p < 3; p++) {
303 planes[p].bands = av_mallocz_array(planes[p].num_bands, sizeof(IVIBandDesc));
304 if (!planes[p].bands)
305 return AVERROR(ENOMEM);
307 /* select band dimensions: if there is only one band then it
308 * has the full size, if there are several bands each of them
309 * has only half size */
310 b_width = planes[p].num_bands == 1 ? planes[p].width
311 : (planes[p].width + 1) >> 1;
312 b_height = planes[p].num_bands == 1 ? planes[p].height
313 : (planes[p].height + 1) >> 1;
315 /* luma band buffers will be aligned on 16x16 (max macroblock size) */
316 /* chroma band buffers will be aligned on 8x8 (max macroblock size) */
317 align_fac = p ? 8 : 16;
318 width_aligned = FFALIGN(b_width , align_fac);
319 height_aligned = FFALIGN(b_height, align_fac);
320 buf_size = width_aligned * height_aligned * sizeof(int16_t);
322 for (b = 0; b < planes[p].num_bands; b++) {
323 band = &planes[p].bands[b]; /* select appropriate plane/band */
326 band->width = b_width;
327 band->height = b_height;
328 band->pitch = width_aligned;
329 band->aheight = height_aligned;
330 band->bufs[0] = av_mallocz(buf_size);
331 band->bufs[1] = av_mallocz(buf_size);
332 band->bufsize = buf_size/2;
333 if (!band->bufs[0] || !band->bufs[1])
334 return AVERROR(ENOMEM);
336 /* allocate the 3rd band buffer for scalability mode */
337 if (cfg->luma_bands > 1) {
338 band->bufs[2] = av_mallocz(buf_size);
340 return AVERROR(ENOMEM);
342 /* reset custom vlc */
343 planes[p].bands[0].blk_vlc.cust_desc.num_rows = 0;
350 static int ivi_init_tiles(IVIBandDesc *band, IVITile *ref_tile,
351 int p, int b, int t_height, int t_width)
354 IVITile *tile = band->tiles;
356 for (y = 0; y < band->height; y += t_height) {
357 for (x = 0; x < band->width; x += t_width) {
360 tile->mb_size = band->mb_size;
361 tile->width = FFMIN(band->width - x, t_width);
362 tile->height = FFMIN(band->height - y, t_height);
363 tile->is_empty = tile->data_size = 0;
364 /* calculate number of macroblocks */
365 tile->num_MBs = IVI_MBs_PER_TILE(tile->width, tile->height,
368 av_freep(&tile->mbs);
369 tile->mbs = av_mallocz_array(tile->num_MBs, sizeof(IVIMbInfo));
371 return AVERROR(ENOMEM);
375 if (tile->num_MBs != ref_tile->num_MBs) {
376 av_log(NULL, AV_LOG_DEBUG, "ref_tile mismatch\n");
377 return AVERROR_INVALIDDATA;
379 tile->ref_mbs = ref_tile->mbs;
389 av_cold int ff_ivi_init_tiles(IVIPlaneDesc *planes,
390 int tile_width, int tile_height)
392 int p, b, x_tiles, y_tiles, t_width, t_height, ret;
395 for (p = 0; p < 3; p++) {
396 t_width = !p ? tile_width : (tile_width + 3) >> 2;
397 t_height = !p ? tile_height : (tile_height + 3) >> 2;
399 if (!p && planes[0].num_bands == 4) {
403 if(t_width<=0 || t_height<=0)
404 return AVERROR(EINVAL);
406 for (b = 0; b < planes[p].num_bands; b++) {
407 band = &planes[p].bands[b];
408 x_tiles = IVI_NUM_TILES(band->width, t_width);
409 y_tiles = IVI_NUM_TILES(band->height, t_height);
410 band->num_tiles = x_tiles * y_tiles;
412 av_freep(&band->tiles);
413 band->tiles = av_mallocz_array(band->num_tiles, sizeof(IVITile));
415 return AVERROR(ENOMEM);
417 /* use the first luma band as reference for motion vectors
419 ret = ivi_init_tiles(band, planes[0].bands[0].tiles,
420 p, b, t_height, t_width);
430 * Decode size of the tile data.
431 * The size is stored as a variable-length field having the following format:
432 * if (tile_data_size < 255) than this field is only one byte long
433 * if (tile_data_size >= 255) than this field four is byte long: 0xFF X1 X2 X3
434 * where X1-X3 is size of the tile data
436 * @param[in,out] gb the GetBit context
437 * @return size of the tile data in bytes
439 static int ivi_dec_tile_data_size(GetBitContext *gb)
445 len = get_bits(gb, 8);
447 len = get_bits_long(gb, 24);
450 /* align the bitstream reader on the byte boundary */
456 static int ivi_dc_transform(IVIBandDesc *band, int *prev_dc, int buf_offs,
459 int buf_size = band->pitch * band->aheight - buf_offs;
460 int min_size = (blk_size - 1) * band->pitch + blk_size;
462 if (min_size > buf_size)
463 return AVERROR_INVALIDDATA;
465 band->dc_transform(prev_dc, band->buf + buf_offs,
466 band->pitch, blk_size);
471 static int ivi_decode_coded_blocks(GetBitContext *gb, IVIBandDesc *band,
472 ivi_mc_func mc, int mv_x, int mv_y,
473 int *prev_dc, int is_intra, int mc_type,
474 uint32_t quant, int offs,
475 AVCodecContext *avctx)
477 const uint16_t *base_tab = is_intra ? band->intra_base : band->inter_base;
478 RVMapDesc *rvmap = band->rv_map;
479 uint8_t col_flags[8];
481 uint32_t sym = 0, lo, hi, q;
483 int blk_size = band->blk_size;
484 int num_coeffs = blk_size * blk_size;
485 int col_mask = blk_size - 1;
487 int min_size = band->pitch * (band->transform_size - 1) +
488 band->transform_size;
489 int buf_size = band->pitch * band->aheight - offs;
491 if (min_size > buf_size)
492 return AVERROR_INVALIDDATA;
495 av_log(avctx, AV_LOG_ERROR, "Scan pattern is not set.\n");
496 return AVERROR_INVALIDDATA;
499 /* zero transform vector */
500 memset(trvec, 0, num_coeffs * sizeof(trvec[0]));
501 /* zero column flags */
502 memset(col_flags, 0, sizeof(col_flags));
503 while (scan_pos <= num_coeffs) {
504 sym = get_vlc2(gb, band->blk_vlc.tab->table,
506 if (sym == rvmap->eob_sym)
507 break; /* End of block */
509 /* Escape - run/val explicitly coded using 3 vlc codes */
510 if (sym == rvmap->esc_sym) {
511 run = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1) + 1;
512 lo = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
513 hi = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
514 /* merge them and convert into signed val */
515 val = IVI_TOSIGNED((hi << 6) | lo);
518 av_log(avctx, AV_LOG_ERROR, "Invalid sym encountered: %"PRIu32".\n", sym);
519 return AVERROR_INVALIDDATA;
521 run = rvmap->runtab[sym];
522 val = rvmap->valtab[sym];
525 /* de-zigzag and dequantize */
527 if (scan_pos >= num_coeffs || scan_pos < 0)
529 pos = band->scan[scan_pos];
532 av_dlog(avctx, "Val = 0 encountered!\n");
534 q = (base_tab[pos] * quant) >> 9;
536 val = val * q + FFSIGN(val) * (((q ^ 1) - 1) >> 1);
538 /* track columns containing non-zero coeffs */
539 col_flags[pos & col_mask] |= !!val;
542 if (scan_pos < 0 || scan_pos >= num_coeffs && sym != rvmap->eob_sym)
543 return AVERROR_INVALIDDATA; /* corrupt block data */
545 /* undoing DC coeff prediction for intra-blocks */
546 if (is_intra && band->is_2d_trans) {
547 *prev_dc += trvec[0];
549 col_flags[0] |= !!*prev_dc;
552 if(band->transform_size > band->blk_size){
553 av_log(NULL, AV_LOG_ERROR, "Too large transform\n");
554 return AVERROR_INVALIDDATA;
557 /* apply inverse transform */
558 band->inv_transform(trvec, band->buf + offs,
559 band->pitch, col_flags);
561 /* apply motion compensation */
563 return ivi_mc(band, mc, offs, mv_x, mv_y, mc_type);
569 * extract huffman-coded transform coefficients from the bitstream,
570 * dequantize them, apply inverse transform and motion compensation
571 * in order to reconstruct the picture.
573 * @param[in,out] gb the GetBit context
574 * @param[in] band pointer to the band descriptor
575 * @param[in] tile pointer to the tile descriptor
576 * @return result code: 0 - OK, -1 = error (corrupted blocks data)
578 static int ivi_decode_blocks(GetBitContext *gb, IVIBandDesc *band,
579 IVITile *tile, AVCodecContext *avctx)
581 int mbn, blk, num_blocks, blk_size, ret, is_intra, mc_type = 0;
582 int mv_x = 0, mv_y = 0;
584 uint32_t cbp, quant, buf_offs;
586 ivi_mc_func mc_with_delta_func, mc_no_delta_func;
587 const uint8_t *scale_tab;
589 /* init intra prediction for the DC coefficient */
591 blk_size = band->blk_size;
592 /* number of blocks per mb */
593 num_blocks = (band->mb_size != blk_size) ? 4 : 1;
595 mc_with_delta_func = ff_ivi_mc_8x8_delta;
596 mc_no_delta_func = ff_ivi_mc_8x8_no_delta;
598 mc_with_delta_func = ff_ivi_mc_4x4_delta;
599 mc_no_delta_func = ff_ivi_mc_4x4_no_delta;
602 for (mbn = 0, mb = tile->mbs; mbn < tile->num_MBs; mb++, mbn++) {
603 is_intra = !mb->type;
605 buf_offs = mb->buf_offs;
607 quant = band->glob_quant + mb->q_delta;
608 if (avctx->codec_id == AV_CODEC_ID_INDEO4)
609 quant = av_clip(quant, 0, 31);
611 quant = av_clip(quant, 0, 23);
613 scale_tab = is_intra ? band->intra_scale : band->inter_scale;
615 quant = scale_tab[quant];
620 if (band->is_halfpel) {
621 mc_type = ((mv_y & 1) << 1) | (mv_x & 1);
623 mv_y >>= 1; /* convert halfpel vectors into fullpel ones */
626 int dmv_x, dmv_y, cx, cy;
628 dmv_x = mb->mv_x >> band->is_halfpel;
629 dmv_y = mb->mv_y >> band->is_halfpel;
630 cx = mb->mv_x & band->is_halfpel;
631 cy = mb->mv_y & band->is_halfpel;
633 if (mb->xpos + dmv_x < 0 ||
634 mb->xpos + dmv_x + band->mb_size + cx > band->pitch ||
635 mb->ypos + dmv_y < 0 ||
636 mb->ypos + dmv_y + band->mb_size + cy > band->aheight) {
637 return AVERROR_INVALIDDATA;
642 for (blk = 0; blk < num_blocks; blk++) {
643 /* adjust block position in the buffer according to its number */
645 buf_offs += blk_size;
646 } else if (blk == 2) {
647 buf_offs -= blk_size;
648 buf_offs += blk_size * band->pitch;
651 if (cbp & 1) { /* block coded ? */
652 ret = ivi_decode_coded_blocks(gb, band, mc_with_delta_func,
653 mv_x, mv_y, &prev_dc, is_intra,
654 mc_type, quant, buf_offs, avctx);
658 /* block not coded */
659 /* for intra blocks apply the dc slant transform */
660 /* for inter - perform the motion compensation without delta */
662 ret = ivi_dc_transform(band, &prev_dc, buf_offs, blk_size);
666 ret = ivi_mc(band, mc_no_delta_func, buf_offs,
667 mv_x, mv_y, mc_type);
683 * Handle empty tiles by performing data copying and motion
684 * compensation respectively.
686 * @param[in] avctx ptr to the AVCodecContext
687 * @param[in] band pointer to the band descriptor
688 * @param[in] tile pointer to the tile descriptor
689 * @param[in] mv_scale scaling factor for motion vectors
691 static int ivi_process_empty_tile(AVCodecContext *avctx, IVIBandDesc *band,
692 IVITile *tile, int32_t mv_scale)
694 int x, y, need_mc, mbn, blk, num_blocks, mv_x, mv_y, mc_type;
695 int offs, mb_offset, row_offset, ret;
696 IVIMbInfo *mb, *ref_mb;
699 ivi_mc_func mc_no_delta_func;
701 if (tile->num_MBs != IVI_MBs_PER_TILE(tile->width, tile->height, band->mb_size)) {
702 av_log(avctx, AV_LOG_ERROR, "Allocated tile size %d mismatches "
703 "parameters %d in ivi_process_empty_tile()\n",
704 tile->num_MBs, IVI_MBs_PER_TILE(tile->width, tile->height, band->mb_size));
705 return AVERROR_INVALIDDATA;
708 offs = tile->ypos * band->pitch + tile->xpos;
710 ref_mb = tile->ref_mbs;
711 row_offset = band->mb_size * band->pitch;
712 need_mc = 0; /* reset the mc tracking flag */
714 for (y = tile->ypos; y < (tile->ypos + tile->height); y += band->mb_size) {
717 for (x = tile->xpos; x < (tile->xpos + tile->width); x += band->mb_size) {
720 mb->buf_offs = mb_offset;
722 mb->type = 1; /* set the macroblocks type = INTER */
723 mb->cbp = 0; /* all blocks are empty */
725 if (!band->qdelta_present && !band->plane && !band->band_num) {
726 mb->q_delta = band->glob_quant;
731 if (band->inherit_qdelta && ref_mb)
732 mb->q_delta = ref_mb->q_delta;
734 if (band->inherit_mv && ref_mb) {
735 /* motion vector inheritance */
737 mb->mv_x = ivi_scale_mv(ref_mb->mv_x, mv_scale);
738 mb->mv_y = ivi_scale_mv(ref_mb->mv_y, mv_scale);
740 mb->mv_x = ref_mb->mv_x;
741 mb->mv_y = ref_mb->mv_y;
743 need_mc |= mb->mv_x || mb->mv_y; /* tracking non-zero motion vectors */
745 int dmv_x, dmv_y, cx, cy;
747 dmv_x = mb->mv_x >> band->is_halfpel;
748 dmv_y = mb->mv_y >> band->is_halfpel;
749 cx = mb->mv_x & band->is_halfpel;
750 cy = mb->mv_y & band->is_halfpel;
752 if ( mb->xpos + dmv_x < 0
753 || mb->xpos + dmv_x + band->mb_size + cx > band->pitch
754 || mb->ypos + dmv_y < 0
755 || mb->ypos + dmv_y + band->mb_size + cy > band->aheight) {
756 av_log(avctx, AV_LOG_ERROR, "MV out of bounds\n");
757 return AVERROR_INVALIDDATA;
765 mb_offset += band->mb_size;
770 if (band->inherit_mv && need_mc) { /* apply motion compensation if there is at least one non-zero motion vector */
771 num_blocks = (band->mb_size != band->blk_size) ? 4 : 1; /* number of blocks per mb */
772 mc_no_delta_func = (band->blk_size == 8) ? ff_ivi_mc_8x8_no_delta
773 : ff_ivi_mc_4x4_no_delta;
775 for (mbn = 0, mb = tile->mbs; mbn < tile->num_MBs; mb++, mbn++) {
778 if (!band->is_halfpel) {
779 mc_type = 0; /* we have only fullpel vectors */
781 mc_type = ((mv_y & 1) << 1) | (mv_x & 1);
783 mv_y >>= 1; /* convert halfpel vectors into fullpel ones */
786 for (blk = 0; blk < num_blocks; blk++) {
787 /* adjust block position in the buffer according with its number */
788 offs = mb->buf_offs + band->blk_size * ((blk & 1) + !!(blk & 2) * band->pitch);
789 ret = ivi_mc(band, mc_no_delta_func, offs,
790 mv_x, mv_y, mc_type);
796 /* copy data from the reference tile into the current one */
797 src = band->ref_buf + tile->ypos * band->pitch + tile->xpos;
798 dst = band->buf + tile->ypos * band->pitch + tile->xpos;
799 for (y = 0; y < tile->height; y++) {
800 memcpy(dst, src, tile->width*sizeof(band->buf[0]));
811 static uint16_t ivi_calc_band_checksum(IVIBandDesc *band)
814 int16_t *src, checksum;
819 for (y = 0; y < band->height; src += band->pitch, y++)
820 for (x = 0; x < band->width; x++)
828 * Convert and output the current plane.
829 * This conversion is done by adding back the bias value of 128
830 * (subtracted in the encoder) and clipping the result.
832 * @param[in] plane pointer to the descriptor of the plane being processed
833 * @param[out] dst pointer to the buffer receiving converted pixels
834 * @param[in] dst_pitch pitch for moving to the next y line
836 static void ivi_output_plane(IVIPlaneDesc *plane, uint8_t *dst, int dst_pitch)
839 const int16_t *src = plane->bands[0].buf;
840 uint32_t pitch = plane->bands[0].pitch;
845 for (y = 0; y < plane->height; y++) {
846 for (x = 0; x < plane->width; x++)
847 dst[x] = av_clip_uint8(src[x] + 128);
854 * Decode an Indeo 4 or 5 band.
856 * @param[in,out] ctx ptr to the decoder context
857 * @param[in,out] band ptr to the band descriptor
858 * @param[in] avctx ptr to the AVCodecContext
859 * @return result code: 0 = OK, -1 = error
861 static int decode_band(IVI45DecContext *ctx,
862 IVIBandDesc *band, AVCodecContext *avctx)
864 int result, i, t, idx1, idx2, pos;
867 band->buf = band->bufs[ctx->dst_buf];
869 av_log(avctx, AV_LOG_ERROR, "Band buffer points to no data!\n");
870 return AVERROR_INVALIDDATA;
872 band->ref_buf = band->bufs[ctx->ref_buf];
873 band->data_ptr = ctx->frame_data + (get_bits_count(&ctx->gb) >> 3);
875 result = ctx->decode_band_hdr(ctx, band, avctx);
877 av_log(avctx, AV_LOG_ERROR, "Error while decoding band header: %d\n",
882 if (band->is_empty) {
883 av_log(avctx, AV_LOG_ERROR, "Empty band encountered!\n");
884 return AVERROR_INVALIDDATA;
887 band->rv_map = &ctx->rvmap_tabs[band->rvmap_sel];
889 /* apply corrections to the selected rvmap table if present */
890 for (i = 0; i < band->num_corr; i++) {
891 idx1 = band->corr[i * 2];
892 idx2 = band->corr[i * 2 + 1];
893 FFSWAP(uint8_t, band->rv_map->runtab[idx1], band->rv_map->runtab[idx2]);
894 FFSWAP(int16_t, band->rv_map->valtab[idx1], band->rv_map->valtab[idx2]);
895 if (idx1 == band->rv_map->eob_sym || idx2 == band->rv_map->eob_sym)
896 band->rv_map->eob_sym ^= idx1 ^ idx2;
897 if (idx1 == band->rv_map->esc_sym || idx2 == band->rv_map->esc_sym)
898 band->rv_map->esc_sym ^= idx1 ^ idx2;
901 pos = get_bits_count(&ctx->gb);
903 for (t = 0; t < band->num_tiles; t++) {
904 tile = &band->tiles[t];
906 if (tile->mb_size != band->mb_size) {
907 av_log(avctx, AV_LOG_ERROR, "MB sizes mismatch: %d vs. %d\n",
908 band->mb_size, tile->mb_size);
909 return AVERROR_INVALIDDATA;
911 tile->is_empty = get_bits1(&ctx->gb);
912 if (tile->is_empty) {
913 result = ivi_process_empty_tile(avctx, band, tile,
914 (ctx->planes[0].bands[0].mb_size >> 3) - (band->mb_size >> 3));
917 av_dlog(avctx, "Empty tile encountered!\n");
919 tile->data_size = ivi_dec_tile_data_size(&ctx->gb);
920 if (!tile->data_size) {
921 av_log(avctx, AV_LOG_ERROR, "Tile data size is zero!\n");
922 result = AVERROR_INVALIDDATA;
926 result = ctx->decode_mb_info(ctx, band, tile, avctx);
930 result = ivi_decode_blocks(&ctx->gb, band, tile, avctx);
932 av_log(avctx, AV_LOG_ERROR,
933 "Corrupted tile data encountered!\n");
937 if (((get_bits_count(&ctx->gb) - pos) >> 3) != tile->data_size) {
938 av_log(avctx, AV_LOG_ERROR,
939 "Tile data_size mismatch!\n");
940 result = AVERROR_INVALIDDATA;
944 pos += tile->data_size << 3; // skip to next tile
948 /* restore the selected rvmap table by applying its corrections in
950 for (i = band->num_corr-1; i >= 0; i--) {
951 idx1 = band->corr[i*2];
952 idx2 = band->corr[i*2+1];
953 FFSWAP(uint8_t, band->rv_map->runtab[idx1], band->rv_map->runtab[idx2]);
954 FFSWAP(int16_t, band->rv_map->valtab[idx1], band->rv_map->valtab[idx2]);
955 if (idx1 == band->rv_map->eob_sym || idx2 == band->rv_map->eob_sym)
956 band->rv_map->eob_sym ^= idx1 ^ idx2;
957 if (idx1 == band->rv_map->esc_sym || idx2 == band->rv_map->esc_sym)
958 band->rv_map->esc_sym ^= idx1 ^ idx2;
962 if (band->checksum_present) {
963 uint16_t chksum = ivi_calc_band_checksum(band);
964 if (chksum != band->checksum) {
965 av_log(avctx, AV_LOG_ERROR,
966 "Band checksum mismatch! Plane %d, band %d, "
967 "received: %"PRIx32", calculated: %"PRIx16"\n",
968 band->plane, band->band_num, band->checksum, chksum);
973 align_get_bits(&ctx->gb);
978 int ff_ivi_decode_frame(AVCodecContext *avctx, void *data, int *got_frame,
981 IVI45DecContext *ctx = avctx->priv_data;
982 const uint8_t *buf = avpkt->data;
983 AVFrame *frame = data;
984 int buf_size = avpkt->size;
987 init_get_bits(&ctx->gb, buf, buf_size * 8);
988 ctx->frame_data = buf;
989 ctx->frame_size = buf_size;
991 result = ctx->decode_pic_hdr(ctx, avctx);
993 av_log(avctx, AV_LOG_ERROR,
994 "Error while decoding picture header: %d\n", result);
997 if (ctx->gop_invalid)
998 return AVERROR_INVALIDDATA;
1000 if (ctx->gop_flags & IVI5_IS_PROTECTED) {
1001 avpriv_report_missing_feature(avctx, "Password-protected clip!\n");
1002 return AVERROR_PATCHWELCOME;
1005 if (!ctx->planes[0].bands) {
1006 av_log(avctx, AV_LOG_ERROR, "Color planes not initialized yet\n");
1007 return AVERROR_INVALIDDATA;
1010 ctx->switch_buffers(ctx);
1014 if (ctx->is_nonnull_frame(ctx)) {
1015 ctx->buf_invalid[ctx->dst_buf] = 1;
1016 for (p = 0; p < 3; p++) {
1017 for (b = 0; b < ctx->planes[p].num_bands; b++) {
1018 result = decode_band(ctx, &ctx->planes[p].bands[b], avctx);
1020 av_log(avctx, AV_LOG_ERROR,
1021 "Error while decoding band: %d, plane: %d\n", b, p);
1026 ctx->buf_invalid[ctx->dst_buf] = 0;
1028 if (ctx->is_scalable)
1029 return AVERROR_INVALIDDATA;
1031 for (p = 0; p < 3; p++) {
1032 if (!ctx->planes[p].bands[0].buf)
1033 return AVERROR_INVALIDDATA;
1036 if (ctx->buf_invalid[ctx->dst_buf])
1039 //STOP_TIMER("decode_planes"); }
1041 /* If the bidirectional mode is enabled, next I and the following P
1042 * frame will be sent together. Unfortunately the approach below seems
1043 * to be the only way to handle the B-frames mode.
1044 * That's exactly the same Intel decoders do.
1046 if (avctx->codec_id == AV_CODEC_ID_INDEO4 &&
1047 ctx->frame_type == 0/*FRAMETYPE_INTRA*/) {
1048 // skip version string
1049 while (get_bits(&ctx->gb, 8)) {
1050 if (get_bits_left(&ctx->gb) < 8)
1051 return AVERROR_INVALIDDATA;
1054 skip_bits_long(&ctx->gb, 64); // skip padding, TODO: implement correct 8-bytes alignment
1055 if (get_bits_left(&ctx->gb) > 18 && show_bits(&ctx->gb, 18) == 0x3FFF8)
1056 av_log(avctx, AV_LOG_ERROR, "Buffer contains IP frames!\n");
1059 if (!ctx->is_nonnull_frame(ctx))
1062 result = ff_set_dimensions(avctx, ctx->planes[0].width, ctx->planes[0].height);
1066 if ((result = ff_get_buffer(avctx, frame, 0)) < 0)
1069 if (ctx->is_scalable) {
1070 if (avctx->codec_id == AV_CODEC_ID_INDEO4)
1071 ff_ivi_recompose_haar(&ctx->planes[0], frame->data[0], frame->linesize[0]);
1073 ff_ivi_recompose53 (&ctx->planes[0], frame->data[0], frame->linesize[0]);
1075 ivi_output_plane(&ctx->planes[0], frame->data[0], frame->linesize[0]);
1078 ivi_output_plane(&ctx->planes[2], frame->data[1], frame->linesize[1]);
1079 ivi_output_plane(&ctx->planes[1], frame->data[2], frame->linesize[2]);
1087 * Close Indeo5 decoder and clean up its context.
1089 av_cold int ff_ivi_decode_close(AVCodecContext *avctx)
1091 IVI45DecContext *ctx = avctx->priv_data;
1093 ivi_free_buffers(&ctx->planes[0]);
1095 if (ctx->mb_vlc.cust_tab.table)
1096 ff_free_vlc(&ctx->mb_vlc.cust_tab);
1098 #if IVI4_STREAM_ANALYSER
1099 if (avctx->codec_id == AV_CODEC_ID_INDEO4) {
1100 if (ctx->is_scalable)
1101 av_log(avctx, AV_LOG_ERROR, "This video uses scalability mode!\n");
1102 if (ctx->uses_tiling)
1103 av_log(avctx, AV_LOG_ERROR, "This video uses local decoding!\n");
1104 if (ctx->has_b_frames)
1105 av_log(avctx, AV_LOG_ERROR, "This video contains B-frames!\n");
1106 if (ctx->has_transp)
1107 av_log(avctx, AV_LOG_ERROR, "Transparency mode is enabled!\n");
1109 av_log(avctx, AV_LOG_ERROR, "This video uses Haar transform!\n");
1110 if (ctx->uses_fullpel)
1111 av_log(avctx, AV_LOG_ERROR, "This video uses fullpel motion vectors!\n");
1120 * Scan patterns shared between indeo4 and indeo5
1122 const uint8_t ff_ivi_vertical_scan_8x8[64] = {
1123 0, 8, 16, 24, 32, 40, 48, 56,
1124 1, 9, 17, 25, 33, 41, 49, 57,
1125 2, 10, 18, 26, 34, 42, 50, 58,
1126 3, 11, 19, 27, 35, 43, 51, 59,
1127 4, 12, 20, 28, 36, 44, 52, 60,
1128 5, 13, 21, 29, 37, 45, 53, 61,
1129 6, 14, 22, 30, 38, 46, 54, 62,
1130 7, 15, 23, 31, 39, 47, 55, 63
1133 const uint8_t ff_ivi_horizontal_scan_8x8[64] = {
1134 0, 1, 2, 3, 4, 5, 6, 7,
1135 8, 9, 10, 11, 12, 13, 14, 15,
1136 16, 17, 18, 19, 20, 21, 22, 23,
1137 24, 25, 26, 27, 28, 29, 30, 31,
1138 32, 33, 34, 35, 36, 37, 38, 39,
1139 40, 41, 42, 43, 44, 45, 46, 47,
1140 48, 49, 50, 51, 52, 53, 54, 55,
1141 56, 57, 58, 59, 60, 61, 62, 63
1144 const uint8_t ff_ivi_direct_scan_4x4[16] = {
1145 0, 1, 4, 8, 5, 2, 3, 6, 9, 12, 13, 10, 7, 11, 14, 15
1150 * Run-value (RLE) tables.
1152 const RVMapDesc ff_ivi_rvmap_tabs[9] = {
1157 {1, 1, 0, 1, 1, 0, 1, 1, 2, 2, 1, 1, 1, 1, 3, 3,
1158 1, 1, 2, 2, 1, 1, 4, 4, 1, 1, 1, 1, 2, 2, 5, 5,
1159 1, 1, 3, 3, 1, 1, 6, 6, 1, 2, 1, 2, 7, 7, 1, 1,
1160 8, 8, 1, 1, 4, 2, 1, 4, 2, 1, 3, 3, 1, 1, 1, 9,
1161 9, 1, 2, 1, 2, 1, 5, 5, 1, 1, 10, 10, 1, 1, 3, 3,
1162 2, 2, 1, 1, 11, 11, 6, 4, 4, 1, 6, 1, 2, 1, 2, 12,
1163 8, 1, 12, 7, 8, 7, 1, 16, 1, 16, 1, 3, 3, 13, 1, 13,
1164 2, 2, 1, 15, 1, 5, 14, 15, 1, 5, 14, 1, 17, 8, 17, 8,
1165 1, 4, 4, 2, 2, 1, 25, 25, 24, 24, 1, 3, 1, 3, 1, 8,
1166 6, 7, 6, 1, 18, 8, 18, 1, 7, 23, 2, 2, 23, 1, 1, 21,
1167 22, 9, 9, 22, 19, 1, 21, 5, 19, 5, 1, 33, 20, 33, 20, 8,
1168 4, 4, 1, 32, 2, 2, 8, 3, 32, 26, 3, 1, 7, 7, 26, 6,
1169 1, 6, 1, 1, 16, 1, 10, 1, 10, 2, 16, 29, 28, 2, 29, 28,
1170 1, 27, 5, 8, 5, 27, 1, 8, 3, 7, 3, 31, 41, 31, 1, 41,
1171 6, 1, 6, 7, 4, 4, 1, 1, 2, 1, 2, 11, 34, 30, 11, 1,
1172 30, 15, 15, 34, 36, 40, 36, 40, 35, 35, 37, 37, 39, 39, 38, 38},
1175 { 1, -1, 0, 2, -2, 0, 3, -3, 1, -1, 4, -4, 5, -5, 1, -1,
1176 6, -6, 2, -2, 7, -7, 1, -1, 8, -8, 9, -9, 3, -3, 1, -1,
1177 10, -10, 2, -2, 11, -11, 1, -1, 12, 4, -12, -4, 1, -1, 13, -13,
1178 1, -1, 14, -14, 2, 5, 15, -2, -5, -15, -3, 3, 16, -16, 17, 1,
1179 -1, -17, 6, 18, -6, -18, 2, -2, 19, -19, 1, -1, 20, -20, 4, -4,
1180 7, -7, 21, -21, 1, -1, 2, 3, -3, 22, -2, -22, 8, 23, -8, 1,
1181 2, -23, -1, 2, -2, -2, 24, 1, -24, -1, 25, 5, -5, 1, -25, -1,
1182 9, -9, 26, 1, -26, 3, 1, -1, 27, -3, -1, -27, 1, 3, -1, -3,
1183 28, -4, 4, 10, -10, -28, 1, -1, 1, -1, 29, 6, -29, -6, 30, -4,
1184 3, 3, -3, -30, 1, 4, -1, 31, -3, 1, 11, -11, -1, -31, 32, -1,
1185 -1, 2, -2, 1, 1, -32, 1, 4, -1, -4, 33, -1, 1, 1, -1, 5,
1186 5, -5, -33, -1, -12, 12, -5, -7, 1, 1, 7, 34, 4, -4, -1, 4,
1187 -34, -4, 35, 36, -2, -35, -2, -36, 2, 13, 2, -1, 1, -13, 1, -1,
1188 37, 1, -5, 6, 5, -1, 38, -6, -8, 5, 8, -1, 1, 1, -37, -1,
1189 5, 39, -5, -5, 6, -6, -38, -39, -14, 40, 14, 2, 1, 1, -2, -40,
1190 -1, -2, 2, -1, -1, -1, 1, 1, 1, -1, 1, -1, 1, -1, 1, -1}
1196 {0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 8, 6, 8, 7,
1197 7, 9, 9, 10, 10, 11, 11, 1, 12, 1, 12, 13, 13, 16, 14, 16,
1198 14, 15, 15, 17, 17, 18, 0, 18, 19, 20, 21, 19, 22, 21, 20, 22,
1199 25, 24, 2, 25, 24, 23, 23, 2, 26, 28, 26, 28, 29, 27, 29, 27,
1200 33, 33, 1, 32, 1, 3, 32, 30, 36, 3, 36, 30, 31, 31, 35, 34,
1201 37, 41, 34, 35, 37, 4, 41, 4, 49, 8, 8, 49, 40, 38, 5, 38,
1202 40, 39, 5, 39, 42, 43, 42, 7, 57, 6, 43, 44, 6, 50, 7, 44,
1203 57, 48, 50, 48, 45, 45, 46, 47, 51, 46, 47, 58, 1, 51, 58, 1,
1204 52, 59, 53, 9, 52, 55, 55, 59, 53, 56, 54, 56, 54, 9, 64, 64,
1205 60, 63, 60, 63, 61, 62, 61, 62, 2, 10, 2, 10, 11, 1, 11, 13,
1206 12, 1, 12, 13, 16, 16, 8, 8, 14, 3, 3, 15, 14, 15, 4, 4,
1207 1, 17, 17, 5, 1, 7, 7, 5, 6, 1, 2, 2, 6, 22, 1, 25,
1208 21, 22, 8, 24, 1, 21, 25, 24, 8, 18, 18, 23, 9, 20, 23, 33,
1209 29, 33, 20, 1, 19, 1, 29, 36, 9, 36, 19, 41, 28, 57, 32, 3,
1210 28, 3, 1, 27, 49, 49, 1, 32, 26, 26, 2, 4, 4, 7, 57, 41,
1211 2, 7, 10, 5, 37, 16, 10, 27, 8, 8, 13, 16, 37, 13, 1, 5},
1214 {0, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, 1, -1, -1, 1,
1215 -1, 1, -1, 1, -1, 1, -1, 2, 1, -2, -1, 1, -1, 1, 1, -1,
1216 -1, 1, -1, 1, -1, 1, 0, -1, 1, 1, 1, -1, 1, -1, -1, -1,
1217 1, 1, 2, -1, -1, 1, -1, -2, 1, 1, -1, -1, 1, 1, -1, -1,
1218 1, -1, 3, 1, -3, 2, -1, 1, 1, -2, -1, -1, -1, 1, 1, 1,
1219 1, 1, -1, -1, -1, 2, -1, -2, 1, 2, -2, -1, 1, 1, 2, -1,
1220 -1, 1, -2, -1, 1, 1, -1, 2, 1, 2, -1, 1, -2, -1, -2, -1,
1221 -1, 1, 1, -1, 1, -1, 1, 1, 1, -1, -1, 1, 4, -1, -1, -4,
1222 1, 1, 1, 2, -1, -1, 1, -1, -1, 1, -1, -1, 1, -2, 1, -1,
1223 1, 1, -1, -1, 1, 1, -1, -1, 3, 2, -3, -2, 2, 5, -2, 2,
1224 2, -5, -2, -2, -2, 2, -3, 3, 2, 3, -3, 2, -2, -2, 3, -3,
1225 6, 2, -2, 3, -6, 3, -3, -3, 3, 7, -4, 4, -3, 2, -7, 2,
1226 2, -2, -4, 2, 8, -2, -2, -2, 4, 2, -2, 2, 3, 2, -2, -2,
1227 2, 2, -2, -8, -2, 9, -2, 2, -3, -2, 2, -2, 2, 2, 2, 4,
1228 -2, -4, 10, 2, 2, -2, -9, -2, 2, -2, 5, 4, -4, 4, -2, 2,
1229 -5, -4, -3, 4, 2, -3, 3, -2, -5, 5, 3, 3, -2, -3, -10, -4}
1235 {1, 1, 0, 2, 2, 1, 1, 3, 3, 4, 4, 0, 1, 1, 5, 5,
1236 2, 2, 6, 6, 7, 7, 1, 8, 1, 8, 3, 3, 9, 9, 1, 2,
1237 2, 1, 4, 10, 4, 10, 11, 11, 1, 5, 12, 12, 1, 5, 13, 13,
1238 3, 3, 6, 6, 2, 2, 14, 14, 16, 16, 15, 7, 15, 8, 8, 7,
1239 1, 1, 17, 17, 4, 4, 1, 1, 18, 18, 2, 2, 5, 5, 25, 3,
1240 9, 3, 25, 9, 19, 24, 19, 24, 1, 21, 20, 1, 21, 22, 20, 22,
1241 23, 23, 8, 6, 33, 6, 8, 33, 7, 7, 26, 26, 1, 32, 1, 32,
1242 28, 4, 28, 10, 29, 27, 27, 10, 41, 4, 29, 2, 2, 41, 36, 31,
1243 49, 31, 34, 30, 34, 36, 30, 35, 1, 49, 11, 5, 35, 11, 1, 3,
1244 3, 5, 37, 37, 8, 40, 8, 40, 12, 12, 42, 42, 1, 38, 16, 57,
1245 1, 6, 16, 39, 38, 6, 7, 7, 13, 13, 39, 43, 2, 43, 57, 2,
1246 50, 9, 44, 9, 50, 4, 15, 48, 44, 4, 1, 15, 48, 14, 14, 1,
1247 45, 45, 8, 3, 5, 8, 51, 47, 3, 46, 46, 47, 5, 51, 1, 17,
1248 17, 58, 1, 58, 2, 52, 52, 2, 53, 7, 59, 6, 6, 56, 53, 55,
1249 7, 55, 1, 54, 59, 56, 54, 10, 1, 10, 4, 60, 1, 60, 8, 4,
1250 8, 64, 64, 61, 1, 63, 3, 63, 62, 61, 5, 11, 5, 3, 11, 62},
1253 { 1, -1, 0, 1, -1, 2, -2, 1, -1, 1, -1, 0, 3, -3, 1, -1,
1254 2, -2, 1, -1, 1, -1, 4, 1, -4, -1, 2, -2, 1, -1, 5, 3,
1255 -3, -5, 2, 1, -2, -1, 1, -1, 6, 2, 1, -1, -6, -2, 1, -1,
1256 3, -3, 2, -2, 4, -4, 1, -1, 1, -1, 1, 2, -1, 2, -2, -2,
1257 7, -7, 1, -1, 3, -3, 8, -8, 1, -1, 5, -5, 3, -3, 1, 4,
1258 2, -4, -1, -2, 1, 1, -1, -1, 9, 1, 1, -9, -1, 1, -1, -1,
1259 1, -1, 3, -3, 1, 3, -3, -1, 3, -3, 1, -1, 10, 1, -10, -1,
1260 1, 4, -1, 2, 1, -1, 1, -2, 1, -4, -1, 6, -6, -1, 1, 1,
1261 1, -1, 1, 1, -1, -1, -1, 1, 11, -1, -2, 4, -1, 2, -11, 5,
1262 -5, -4, -1, 1, 4, 1, -4, -1, -2, 2, 1, -1, 12, 1, -2, 1,
1263 -12, 4, 2, 1, -1, -4, 4, -4, 2, -2, -1, 1, 7, -1, -1, -7,
1264 -1, -3, 1, 3, 1, 5, 2, 1, -1, -5, 13, -2, -1, 2, -2, -13,
1265 1, -1, 5, 6, 5, -5, 1, 1, -6, 1, -1, -1, -5, -1, 14, 2,
1266 -2, 1, -14, -1, 8, 1, -1, -8, 1, 5, 1, 5, -5, 1, -1, 1,
1267 -5, -1, 15, 1, -1, -1, -1, 3, -15, -3, 6, 1, 16, -1, 6, -6,
1268 -6, 1, -1, 1, -16, 1, 7, -1, 1, -1, -6, -3, 6, -7, 3, -1}
1274 {0, 1, 1, 2, 2, 3, 3, 4, 4, 1, 1, 5, 5, 6, 6, 7,
1275 7, 8, 8, 9, 9, 2, 2, 10, 10, 1, 1, 11, 11, 12, 12, 3,
1276 3, 13, 13, 0, 14, 14, 16, 15, 16, 15, 4, 4, 17, 1, 17, 1,
1277 5, 5, 18, 18, 2, 2, 6, 6, 8, 19, 7, 8, 7, 19, 20, 20,
1278 21, 21, 22, 24, 22, 24, 23, 23, 1, 1, 25, 25, 3, 3, 26, 26,
1279 9, 9, 27, 27, 28, 28, 33, 29, 4, 33, 29, 1, 4, 1, 32, 32,
1280 2, 2, 31, 10, 30, 10, 30, 31, 34, 34, 5, 5, 36, 36, 35, 41,
1281 35, 11, 41, 11, 37, 1, 8, 8, 37, 6, 1, 6, 40, 7, 7, 40,
1282 12, 38, 12, 39, 39, 38, 49, 13, 49, 13, 3, 42, 3, 42, 16, 16,
1283 43, 43, 14, 14, 1, 1, 44, 15, 44, 15, 2, 2, 57, 48, 50, 48,
1284 57, 50, 4, 45, 45, 4, 46, 47, 47, 46, 1, 51, 1, 17, 17, 51,
1285 8, 9, 9, 5, 58, 8, 58, 5, 52, 52, 55, 56, 53, 56, 55, 59,
1286 59, 53, 54, 1, 6, 54, 7, 7, 6, 1, 2, 3, 2, 3, 64, 60,
1287 60, 10, 10, 64, 61, 62, 61, 63, 1, 63, 62, 1, 18, 24, 18, 4,
1288 25, 4, 8, 21, 21, 1, 24, 22, 25, 22, 8, 11, 19, 11, 23, 1,
1289 20, 23, 19, 20, 5, 12, 5, 1, 16, 2, 12, 13, 2, 13, 1, 16},
1292 { 0, 1, -1, 1, -1, 1, -1, 1, -1, 2, -2, 1, -1, 1, -1, 1,
1293 -1, 1, -1, 1, -1, 2, -2, 1, -1, 3, -3, 1, -1, 1, -1, 2,
1294 -2, 1, -1, 0, 1, -1, 1, 1, -1, -1, 2, -2, 1, 4, -1, -4,
1295 2, -2, 1, -1, -3, 3, 2, -2, 2, 1, 2, -2, -2, -1, 1, -1,
1296 1, -1, 1, 1, -1, -1, 1, -1, 5, -5, 1, -1, 3, -3, 1, -1,
1297 2, -2, 1, -1, 1, -1, 1, 1, 3, -1, -1, 6, -3, -6, -1, 1,
1298 4, -4, 1, 2, 1, -2, -1, -1, 1, -1, 3, -3, 1, -1, 1, 1,
1299 -1, 2, -1, -2, 1, 7, -3, 3, -1, 3, -7, -3, 1, -3, 3, -1,
1300 2, 1, -2, 1, -1, -1, 1, 2, -1, -2, -4, -1, 4, 1, 2, -2,
1301 1, -1, -2, 2, 8, -8, -1, 2, 1, -2, -5, 5, 1, -1, -1, 1,
1302 -1, 1, 4, -1, 1, -4, -1, -1, 1, 1, 9, 1, -9, 2, -2, -1,
1303 -4, 3, -3, -4, -1, 4, 1, 4, 1, -1, 1, -1, 1, 1, -1, 1,
1304 -1, -1, -1, 10, 4, 1, 4, -4, -4, -10, 6, 5, -6, -5, 1, -1,
1305 1, 3, -3, -1, 1, -1, -1, -1, 11, 1, 1, -11, -2, -2, 2, 5,
1306 -2, -5, -5, 2, -2, 12, 2, -2, 2, 2, 5, -3, -2, 3, -2, -12,
1307 -2, 2, 2, 2, -5, 3, 5, 13, -3, 7, -3, -3, -7, 3, -13, 3}
1313 {0, 1, 1, 1, 2, 2, 1, 3, 3, 1, 1, 1, 4, 4, 1, 5,
1314 2, 1, 5, 2, 1, 1, 6, 6, 1, 1, 1, 1, 1, 7, 3, 1,
1315 2, 3, 0, 1, 2, 7, 1, 1, 1, 8, 1, 1, 8, 1, 1, 1,
1316 9, 1, 9, 1, 2, 1, 1, 2, 1, 1, 10, 4, 1, 10, 1, 4,
1317 1, 1, 1, 1, 1, 3, 1, 1, 1, 3, 2, 1, 5, 1, 1, 1,
1318 2, 5, 1, 11, 1, 11, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1319 2, 1, 6, 1, 6, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 12,
1320 3, 1, 12, 1, 1, 1, 2, 1, 1, 3, 1, 1, 1, 1, 1, 1,
1321 4, 1, 1, 1, 2, 1, 1, 4, 1, 1, 1, 1, 1, 1, 2, 1,
1322 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 2, 1, 1, 5,
1323 1, 1, 1, 1, 1, 7, 1, 7, 1, 1, 2, 3, 1, 1, 1, 1,
1324 5, 1, 1, 1, 1, 1, 1, 2, 13, 1, 1, 1, 1, 1, 1, 1,
1325 1, 1, 1, 1, 1, 1, 1, 1, 13, 2, 1, 1, 4, 1, 1, 1,
1326 3, 1, 6, 1, 1, 1, 14, 1, 1, 1, 1, 1, 14, 6, 1, 1,
1327 1, 1, 15, 2, 4, 1, 2, 3, 15, 1, 1, 1, 8, 1, 1, 8,
1328 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1},
1331 { 0, 1, -1, 2, 1, -1, -2, 1, -1, 3, -3, 4, 1, -1, -4, 1,
1332 2, 5, -1, -2, -5, 6, 1, -1, -6, 7, -7, 8, -8, 1, 2, 9,
1333 3, -2, 0, -9, -3, -1, 10, -10, 11, 1, -11, 12, -1, -12, 13, -13,
1334 1, 14, -1, -14, 4, 15, -15, -4, 16, -16, 1, 2, 17, -1, -17, -2,
1335 18, -18, 19, -19, 20, 3, -20, 21, -21, -3, 5, 22, 2, -22, -23, 23,
1336 -5, -2, 24, 1, -24, -1, 25, -25, 26, -26, -27, 27, 28, 29, -28, -29,
1337 6, 30, 2, -31, -2, -30, 31, -6, -32, 32, 33, -33, 34, -35, -34, 1,
1338 4, -36, -1, 35, 37, 36, 7, -37, 38, -4, -38, 39, 41, 40, -40, -39,
1339 3, 42, -43, -41, -7, -42, 43, -3, 44, -44, 45, -45, 46, 47, 8, -47,
1340 -48, -46, 50, -50, 48, 49, 51, -49, 52, -52, 5, -51, -8, -53, 53, 3,
1341 -56, 56, 55, 54, -54, 2, 60, -2, -55, 58, 9, -5, 59, 57, -57, -63,
1342 -3, -58, -60, -61, 61, -59, -62, -9, 1, 64, 62, 69, -64, 63, 65, -67,
1343 -68, 66, -65, 68, -66, -69, 67, -70, -1, 10, 71, -71, 4, 73, 72, 70,
1344 6, -76, -3, 74, -78, -74, 1, 78, 80, -72, -75, 76, -1, 3, -73, 79,
1345 75, 77, 1, 11, -4, -79, -10, -6, -1, -77, -83, -80, 2, 81, -84, -2,
1346 83, -81, 82, -82, 84, -87, -86, 85, -11, -85, 86, -89, 87, -88, 88, 89}
1352 {1, 1, 0, 2, 1, 2, 1, 3, 3, 1, 1, 4, 4, 2, 2, 1,
1353 1, 5, 5, 6, 1, 6, 1, 7, 7, 3, 3, 2, 8, 2, 8, 1,
1354 1, 0, 9, 9, 1, 1, 10, 4, 10, 4, 11, 11, 2, 1, 2, 1,
1355 12, 12, 3, 3, 1, 1, 13, 5, 5, 13, 14, 1, 1, 14, 2, 2,
1356 6, 6, 15, 1, 1, 15, 16, 4, 7, 16, 4, 7, 1, 1, 3, 3,
1357 8, 8, 2, 2, 1, 1, 17, 17, 1, 1, 18, 18, 5, 5, 2, 2,
1358 1, 1, 9, 19, 9, 19, 20, 3, 3, 20, 1, 10, 21, 1, 10, 4,
1359 4, 21, 22, 6, 6, 22, 1, 1, 23, 24, 2, 2, 23, 24, 11, 1,
1360 1, 11, 7, 25, 7, 1, 1, 25, 8, 8, 3, 26, 3, 1, 12, 2,
1361 2, 26, 1, 12, 5, 5, 27, 4, 1, 4, 1, 27, 28, 1, 28, 13,
1362 1, 13, 2, 29, 2, 1, 32, 6, 1, 30, 14, 29, 14, 6, 3, 31,
1363 3, 1, 30, 1, 32, 31, 33, 9, 33, 1, 1, 7, 9, 7, 2, 2,
1364 1, 1, 4, 36, 34, 4, 5, 10, 10, 5, 34, 1, 1, 35, 8, 8,
1365 36, 3, 35, 1, 15, 3, 2, 1, 16, 15, 16, 2, 37, 1, 37, 1,
1366 1, 1, 6, 6, 38, 1, 38, 11, 1, 39, 39, 40, 11, 2, 41, 4,
1367 40, 1, 2, 4, 1, 1, 1, 41, 3, 1, 3, 1, 5, 7, 5, 7},
1370 { 1, -1, 0, 1, 2, -1, -2, 1, -1, 3, -3, 1, -1, 2, -2, 4,
1371 -4, 1, -1, 1, 5, -1, -5, 1, -1, 2, -2, 3, 1, -3, -1, 6,
1372 -6, 0, 1, -1, 7, -7, 1, 2, -1, -2, 1, -1, 4, 8, -4, -8,
1373 1, -1, 3, -3, 9, -9, 1, 2, -2, -1, 1, 10, -10, -1, 5, -5,
1374 2, -2, 1, 11, -11, -1, 1, 3, 2, -1, -3, -2, 12, -12, 4, -4,
1375 2, -2, -6, 6, 13, -13, 1, -1, 14, -14, 1, -1, 3, -3, 7, -7,
1376 15, -15, 2, 1, -2, -1, 1, 5, -5, -1, -16, 2, 1, 16, -2, 4,
1377 -4, -1, 1, 3, -3, -1, 17, -17, 1, 1, -8, 8, -1, -1, 2, 18,
1378 -18, -2, 3, 1, -3, 19, -19, -1, 3, -3, 6, 1, -6, 20, 2, 9,
1379 -9, -1, -20, -2, 4, -4, 1, -5, 21, 5, -21, -1, 1, -22, -1, 2,
1380 22, -2, 10, 1, -10, 23, 1, 4, -23, 1, 2, -1, -2, -4, -7, 1,
1381 7, -24, -1, 24, -1, -1, 1, 3, -1, -25, 25, 4, -3, -4, 11, -11,
1382 26, -26, 6, 1, 1, -6, -5, -3, 3, 5, -1, -27, 27, 1, 4, -4,
1383 -1, -8, -1, 28, 2, 8, -12, -28, -2, -2, 2, 12, -1, 29, 1, -29,
1384 30, -30, 5, -5, 1, -31, -1, 3, 31, -1, 1, 1, -3, -13, 1, -7,
1385 -1, -32, 13, 7, 32, 33, -33, -1, -9, -34, 9, 34, -6, 5, 6, -5}
1391 {1, 1, 0, 1, 1, 2, 2, 1, 1, 3, 3, 1, 1, 0, 2, 2,
1392 4, 1, 4, 1, 1, 1, 5, 5, 1, 1, 6, 6, 2, 2, 1, 1,
1393 3, 3, 7, 7, 1, 1, 8, 8, 1, 1, 2, 2, 1, 9, 1, 9,
1394 4, 4, 10, 1, 1, 10, 1, 1, 11, 11, 3, 3, 1, 2, 1, 2,
1395 1, 1, 12, 12, 5, 5, 1, 1, 13, 1, 1, 13, 2, 2, 1, 1,
1396 6, 6, 1, 1, 4, 14, 4, 14, 3, 1, 3, 1, 1, 1, 15, 7,
1397 15, 2, 2, 7, 1, 1, 1, 8, 1, 8, 16, 16, 1, 1, 1, 1,
1398 2, 1, 1, 2, 1, 1, 3, 5, 5, 3, 4, 1, 1, 4, 1, 1,
1399 17, 17, 9, 1, 1, 9, 2, 2, 1, 1, 10, 10, 1, 6, 1, 1,
1400 6, 18, 1, 1, 18, 1, 1, 1, 2, 2, 3, 1, 3, 1, 1, 1,
1401 4, 1, 19, 1, 19, 7, 1, 1, 20, 1, 4, 20, 1, 7, 11, 2,
1402 1, 11, 21, 2, 8, 5, 1, 8, 1, 5, 21, 1, 1, 1, 22, 1,
1403 1, 22, 1, 1, 3, 3, 1, 23, 2, 12, 24, 1, 1, 2, 1, 1,
1404 12, 23, 1, 1, 24, 1, 1, 1, 4, 1, 1, 1, 2, 1, 6, 6,
1405 4, 2, 1, 1, 1, 1, 1, 1, 1, 14, 13, 3, 1, 25, 9, 25,
1406 14, 1, 9, 3, 13, 1, 1, 1, 1, 1, 10, 1, 1, 2, 10, 2},
1409 {-20, -1, 0, 2, -2, 1, -1, 3, -3, 1, -1, 4, -4, 0, 2, -2,
1410 1, 5, -1, -5, 6, -6, 1, -1, 7, -7, 1, -1, 3, -3, 8, -8,
1411 2, -2, 1, -1, 9, -9, 1, -1, 10, -10, 4, -4, 11, 1, -11, -1,
1412 2, -2, 1, 12, -12, -1, 13, -13, 1, -1, 3, -3, 14, 5, -14, -5,
1413 -15, 15, -1, 1, 2, -2, 16, -16, 1, 17, -17, -1, 6, -6, 18, -18,
1414 2, -2, -19, 19, -3, 1, 3, -1, 4, 20, -4, 1, -21, 21, 1, 2,
1415 -1, -7, 7, -2, 22, -22, 23, 2, -23, -2, 1, -1, -24, 24, -25, 25,
1416 -8, -26, 26, 8, -27, 27, 5, 3, -3, -5, -4, 28, -28, 4, 29, -29,
1417 1, -1, -2, -30, 30, 2, 9, -9, -31, 31, 2, -2, -32, 3, 32, -33,
1418 -3, 1, 33, -34, -1, 34, -35, 35, -10, 10, -6, 36, 6, -36, 37, -37,
1419 -5, 38, 1, -38, -1, 3, 39, -39, -1, 40, 5, 1, -40, -3, 2, -11,
1420 -41, -2, 1, 11, -3, -4, 41, 3, 42, 4, -1, -43, -42, 43, 1, -44,
1421 45, -1, 44, -45, -7, 7, -46, 1, -12, 2, 1, -47, 46, 12, 47, 48,
1422 -2, -1, -48, 49, -1, -50, -49, 50, -6, -51, 51, 52, -13, 53, -4, 4,
1423 6, 13, -53, -52, -54, 55, 54, -55, -56, -2, 2, -8, 56, 1, -3, -1,
1424 2, 58, 3, 8, -2, 57, -58, -60, -59, -57, -3, 60, 59, -14, 3, 14}
1430 {1, 1, 0, 2, 2, 1, 1, 3, 3, 4, 4, 5, 5, 1, 1, 6,
1431 6, 2, 2, 7, 7, 8, 8, 1, 1, 3, 3, 9, 9, 10, 10, 1,
1432 1, 2, 2, 4, 4, 11, 0, 11, 12, 12, 13, 13, 1, 1, 5, 5,
1433 14, 14, 15, 16, 15, 16, 3, 3, 1, 6, 1, 6, 2, 2, 7, 7,
1434 8, 8, 17, 17, 1, 1, 4, 4, 18, 18, 2, 2, 1, 19, 1, 20,
1435 19, 20, 21, 21, 3, 3, 22, 22, 5, 5, 24, 1, 1, 23, 9, 23,
1436 24, 9, 2, 2, 10, 1, 1, 10, 6, 6, 25, 4, 4, 25, 7, 7,
1437 26, 8, 1, 8, 3, 1, 26, 3, 11, 11, 27, 27, 2, 28, 1, 2,
1438 28, 1, 12, 12, 5, 5, 29, 13, 13, 29, 32, 1, 1, 33, 31, 30,
1439 32, 4, 30, 33, 4, 31, 3, 14, 1, 1, 3, 34, 34, 2, 2, 14,
1440 6, 6, 35, 36, 35, 36, 1, 15, 1, 16, 16, 15, 7, 9, 7, 9,
1441 37, 8, 8, 37, 1, 1, 39, 2, 38, 39, 2, 40, 5, 38, 40, 5,
1442 3, 3, 4, 4, 10, 10, 1, 1, 1, 1, 41, 2, 41, 2, 6, 6,
1443 1, 1, 11, 42, 11, 43, 3, 42, 3, 17, 4, 43, 1, 17, 7, 1,
1444 8, 44, 4, 7, 44, 5, 8, 2, 5, 1, 2, 48, 45, 1, 12, 45,
1445 12, 48, 13, 13, 1, 9, 9, 46, 1, 46, 47, 47, 49, 18, 18, 49},
1448 { 1, -1, 0, 1, -1, 2, -2, 1, -1, 1, -1, 1, -1, 3, -3, 1,
1449 -1, -2, 2, 1, -1, 1, -1, 4, -4, -2, 2, 1, -1, 1, -1, 5,
1450 -5, -3, 3, 2, -2, 1, 0, -1, 1, -1, 1, -1, 6, -6, 2, -2,
1451 1, -1, 1, 1, -1, -1, -3, 3, 7, 2, -7, -2, -4, 4, 2, -2,
1452 2, -2, 1, -1, 8, -8, 3, -3, 1, -1, -5, 5, 9, 1, -9, 1,
1453 -1, -1, 1, -1, -4, 4, 1, -1, 3, -3, 1, -10, 10, 1, 2, -1,
1454 -1, -2, 6, -6, 2, 11, -11, -2, 3, -3, 1, -4, 4, -1, 3, -3,
1455 1, 3, 12, -3, -5, -12, -1, 5, 2, -2, 1, -1, -7, 1, 13, 7,
1456 -1, -13, 2, -2, 4, -4, 1, 2, -2, -1, 1, 14, -14, 1, 1, 1,
1457 -1, -5, -1, -1, 5, -1, -6, 2, -15, 15, 6, 1, -1, -8, 8, -2,
1458 -4, 4, 1, 1, -1, -1, 16, 2, -16, -2, 2, -2, 4, 3, -4, -3,
1459 -1, -4, 4, 1, -17, 17, -1, -9, 1, 1, 9, 1, -5, -1, -1, 5,
1460 -7, 7, 6, -6, 3, -3, 18, -18, 19, -19, 1, -10, -1, 10, -5, 5,
1461 20, -20, -3, 1, 3, 1, 8, -1, -8, 2, 7, -1, -21, -2, 5, 21,
1462 5, -1, -7, -5, 1, -6, -5, -11, 6, 22, 11, 1, 1, -22, -3, -1,
1463 3, -1, 3, -3, -23, 4, -4, 1, 23, -1, 1, -1, 1, -2, 2, -1}
1469 {1, 1, 1, 1, 0, 2, 2, 1, 1, 3, 3, 0, 1, 1, 2, 2,
1470 4, 4, 1, 1, 5, 5, 1, 1, 2, 2, 3, 3, 6, 6, 1, 1,
1471 7, 7, 8, 1, 8, 2, 2, 1, 4, 4, 1, 3, 1, 3, 9, 9,
1472 2, 2, 1, 5, 1, 5, 10, 10, 1, 1, 11, 11, 3, 6, 3, 4,
1473 4, 6, 2, 2, 1, 12, 1, 12, 7, 13, 7, 13, 1, 1, 8, 8,
1474 2, 2, 14, 14, 16, 15, 16, 5, 5, 1, 3, 15, 1, 3, 4, 4,
1475 1, 1, 17, 17, 2, 2, 6, 6, 1, 18, 1, 18, 22, 21, 22, 21,
1476 25, 24, 25, 19, 9, 20, 9, 23, 19, 24, 20, 3, 23, 7, 3, 1,
1477 1, 7, 28, 26, 29, 5, 28, 26, 5, 8, 29, 4, 8, 27, 2, 2,
1478 4, 27, 1, 1, 10, 36, 10, 33, 33, 36, 30, 1, 32, 32, 1, 30,
1479 6, 31, 31, 35, 3, 6, 11, 11, 3, 2, 35, 2, 34, 1, 34, 1,
1480 37, 37, 12, 7, 12, 5, 41, 5, 4, 7, 1, 8, 13, 4, 1, 41,
1481 13, 38, 8, 38, 9, 1, 40, 40, 9, 1, 39, 2, 2, 49, 39, 42,
1482 3, 3, 14, 16, 49, 14, 16, 42, 43, 43, 6, 6, 15, 1, 1, 15,
1483 44, 44, 1, 1, 50, 48, 4, 5, 4, 7, 5, 2, 10, 10, 48, 7,
1484 50, 45, 2, 1, 45, 8, 8, 1, 46, 46, 3, 47, 47, 3, 1, 1},
1487 { 1, -1, 2, -2, 0, 1, -1, 3, -3, 1, -1, 0, 4, -4, 2, -2,
1488 1, -1, 5, -5, 1, -1, 6, -6, 3, -3, 2, -2, 1, -1, 7, -7,
1489 1, -1, 1, 8, -1, 4, -4, -8, 2, -2, 9, 3, -9, -3, 1, -1,
1490 5, -5, 10, 2, -10, -2, 1, -1, 11, -11, 1, -1, -4, 2, 4, 3,
1491 -3, -2, 6, -6, 12, 1, -12, -1, 2, 1, -2, -1, 13, -13, 2, -2,
1492 7, -7, 1, -1, 1, 1, -1, 3, -3, 14, 5, -1, -14, -5, 4, -4,
1493 15, -15, 1, -1, 8, -8, -3, 3, 16, 1, -16, -1, 1, 1, -1, -1,
1494 1, 1, -1, 1, 2, 1, -2, 1, -1, -1, -1, 6, -1, 3, -6, 17,
1495 -17, -3, 1, 1, 1, 4, -1, -1, -4, 3, -1, 5, -3, -1, -9, 9,
1496 -5, 1, 18, -18, 2, 1, -2, 1, -1, -1, 1, 19, -1, 1, -19, -1,
1497 4, 1, -1, 1, 7, -4, -2, 2, -7, 10, -1, -10, 1, 20, -1, -20,
1498 1, -1, 2, 4, -2, 5, 1, -5, 6, -4, 21, 4, 2, -6, -21, -1,
1499 -2, 1, -4, -1, -3, 22, -1, 1, 3, -22, -1, 11, -11, 1, 1, 1,
1500 8, -8, 2, 2, -1, -2, -2, -1, 1, -1, -5, 5, 2, 23, -23, -2,
1501 1, -1, 24, -24, -1, -1, 7, 6, -7, 5, -6, 12, -3, 3, 1, -5,
1502 1, 1, -12, 25, -1, -5, 5, -25, -1, 1, 9, 1, -1, -9, 26, -26}