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 #include "libavutil/attributes.h"
32 #include "libavutil/imgutils.h"
33 #include "libavutil/timer.h"
35 #define BITSTREAM_READER_LE
44 * These are 2x8 predefined Huffman codebooks for coding macroblock/block
45 * signals. They are specified using "huffman descriptors" in order to
46 * avoid huge static tables. The decoding tables will be generated at
47 * startup from these descriptors.
49 /** static macroblock huffman tables */
50 static const IVIHuffDesc ivi_mb_huff_desc[8] = {
51 {8, {0, 4, 5, 4, 4, 4, 6, 6}},
52 {12, {0, 2, 2, 3, 3, 3, 3, 5, 3, 2, 2, 2}},
53 {12, {0, 2, 3, 4, 3, 3, 3, 3, 4, 3, 2, 2}},
54 {12, {0, 3, 4, 4, 3, 3, 3, 3, 3, 2, 2, 2}},
55 {13, {0, 4, 4, 3, 3, 3, 3, 2, 3, 3, 2, 1, 1}},
56 {9, {0, 4, 4, 4, 4, 3, 3, 3, 2}},
57 {10, {0, 4, 4, 4, 4, 3, 3, 2, 2, 2}},
58 {12, {0, 4, 4, 4, 3, 3, 2, 3, 2, 2, 2, 2}}
61 /** static block huffman tables */
62 static const IVIHuffDesc ivi_blk_huff_desc[8] = {
63 {10, {1, 2, 3, 4, 4, 7, 5, 5, 4, 1}},
64 {11, {2, 3, 4, 4, 4, 7, 5, 4, 3, 3, 2}},
65 {12, {2, 4, 5, 5, 5, 5, 6, 4, 4, 3, 1, 1}},
66 {13, {3, 3, 4, 4, 5, 6, 6, 4, 4, 3, 2, 1, 1}},
67 {11, {3, 4, 4, 5, 5, 5, 6, 5, 4, 2, 2}},
68 {13, {3, 4, 5, 5, 5, 5, 6, 4, 3, 3, 2, 1, 1}},
69 {13, {3, 4, 5, 5, 5, 6, 5, 4, 3, 3, 2, 1, 1}},
70 {9, {3, 4, 4, 5, 5, 5, 6, 5, 5}}
73 static VLC ivi_mb_vlc_tabs [8]; ///< static macroblock Huffman tables
74 static VLC ivi_blk_vlc_tabs[8]; ///< static block Huffman tables
76 typedef void (*ivi_mc_func) (int16_t *buf, const int16_t *ref_buf,
77 ptrdiff_t pitch, int mc_type);
78 typedef void (*ivi_mc_avg_func) (int16_t *buf, const int16_t *ref_buf1,
79 const int16_t *ref_buf2,
80 ptrdiff_t pitch, int mc_type, int mc_type2);
82 static int ivi_mc(IVIBandDesc *band, ivi_mc_func mc, ivi_mc_avg_func mc_avg,
83 int offs, int mv_x, int mv_y, int mv_x2, int mv_y2,
84 int mc_type, int mc_type2)
86 int ref_offs = offs + mv_y * band->pitch + mv_x;
87 int buf_size = band->pitch * band->aheight;
88 int min_size = band->pitch * (band->blk_size - 1) + band->blk_size;
89 int ref_size = (mc_type > 1) * band->pitch + (mc_type & 1);
92 av_assert0(offs >= 0 && ref_offs >= 0 && band->ref_buf);
93 av_assert0(buf_size - min_size >= offs);
94 av_assert0(buf_size - min_size - ref_size >= ref_offs);
98 mc(band->buf + offs, band->ref_buf + ref_offs, band->pitch, mc_type);
100 int ref_offs2 = offs + mv_y2 * band->pitch + mv_x2;
101 int ref_size2 = (mc_type2 > 1) * band->pitch + (mc_type2 & 1);
102 if (offs < 0 || ref_offs2 < 0 || !band->b_ref_buf)
103 return AVERROR_INVALIDDATA;
104 if (buf_size - min_size - ref_size2 < ref_offs2)
105 return AVERROR_INVALIDDATA;
108 mc(band->buf + offs, band->b_ref_buf + ref_offs2,
109 band->pitch, mc_type2);
111 mc_avg(band->buf + offs, band->ref_buf + ref_offs,
112 band->b_ref_buf + ref_offs2, band->pitch,
120 * Reverse "nbits" bits of the value "val" and return the result
121 * in the least significant bits.
123 static uint16_t inv_bits(uint16_t val, int nbits)
128 res = ff_reverse[val] >> (8 - nbits);
130 res = ((ff_reverse[val & 0xFF] << 8) +
131 (ff_reverse[val >> 8])) >> (16 - nbits);
137 * Generate a huffman codebook from the given descriptor
138 * and convert it into the FFmpeg VLC table.
140 * @param[in] cb pointer to codebook descriptor
141 * @param[out] vlc where to place the generated VLC table
142 * @param[in] flag flag: 1 - for static or 0 for dynamic tables
143 * @return result code: 0 - OK, -1 = error (invalid codebook descriptor)
145 static int ivi_create_huff_from_desc(const IVIHuffDesc *cb, VLC *vlc, int flag)
147 int pos, i, j, codes_per_row, prefix, not_last_row;
148 uint16_t codewords[256]; /* FIXME: move this temporal storage out? */
151 pos = 0; /* current position = 0 */
153 for (i = 0; i < cb->num_rows; i++) {
154 codes_per_row = 1 << cb->xbits[i];
155 not_last_row = (i != cb->num_rows - 1);
156 prefix = ((1 << i) - 1) << (cb->xbits[i] + not_last_row);
158 for (j = 0; j < codes_per_row; j++) {
159 if (pos >= 256) /* Some Indeo5 codebooks can have more than 256 */
160 break; /* elements, but only 256 codes are allowed! */
162 bits[pos] = i + cb->xbits[i] + not_last_row;
163 if (bits[pos] > IVI_VLC_BITS)
164 return AVERROR_INVALIDDATA; /* invalid descriptor */
166 codewords[pos] = inv_bits((prefix | j), bits[pos]);
174 /* number of codewords = pos */
175 return init_vlc(vlc, IVI_VLC_BITS, pos, bits, 1, 1, codewords, 2, 2,
176 (flag ? INIT_VLC_USE_NEW_STATIC : 0) | INIT_VLC_LE);
179 av_cold void ff_ivi_init_static_vlc(void)
182 static VLC_TYPE table_data[8192 * 16][2];
183 static int initialized_vlcs = 0;
185 if (initialized_vlcs)
187 for (i = 0; i < 8; i++) {
188 ivi_mb_vlc_tabs[i].table = table_data + i * 2 * 8192;
189 ivi_mb_vlc_tabs[i].table_allocated = 8192;
190 ivi_create_huff_from_desc(&ivi_mb_huff_desc[i],
191 &ivi_mb_vlc_tabs[i], 1);
192 ivi_blk_vlc_tabs[i].table = table_data + (i * 2 + 1) * 8192;
193 ivi_blk_vlc_tabs[i].table_allocated = 8192;
194 ivi_create_huff_from_desc(&ivi_blk_huff_desc[i],
195 &ivi_blk_vlc_tabs[i], 1);
197 initialized_vlcs = 1;
201 * Copy huffman codebook descriptors.
203 * @param[out] dst ptr to the destination descriptor
204 * @param[in] src ptr to the source descriptor
206 static void ivi_huff_desc_copy(IVIHuffDesc *dst, const IVIHuffDesc *src)
208 dst->num_rows = src->num_rows;
209 memcpy(dst->xbits, src->xbits, src->num_rows);
213 * Compare two huffman codebook descriptors.
215 * @param[in] desc1 ptr to the 1st descriptor to compare
216 * @param[in] desc2 ptr to the 2nd descriptor to compare
217 * @return comparison result: 0 - equal, 1 - not equal
219 static int ivi_huff_desc_cmp(const IVIHuffDesc *desc1,
220 const IVIHuffDesc *desc2)
222 return desc1->num_rows != desc2->num_rows ||
223 memcmp(desc1->xbits, desc2->xbits, desc1->num_rows);
226 int ff_ivi_dec_huff_desc(GetBitContext *gb, int desc_coded, int which_tab,
227 IVIHuffTab *huff_tab, AVCodecContext *avctx)
230 IVIHuffDesc new_huff;
233 /* select default table */
234 huff_tab->tab = (which_tab) ? &ivi_blk_vlc_tabs[7]
235 : &ivi_mb_vlc_tabs [7];
239 huff_tab->tab_sel = get_bits(gb, 3);
240 if (huff_tab->tab_sel == 7) {
241 /* custom huffman table (explicitly encoded) */
242 new_huff.num_rows = get_bits(gb, 4);
243 if (!new_huff.num_rows) {
244 av_log(avctx, AV_LOG_ERROR, "Empty custom Huffman table!\n");
245 return AVERROR_INVALIDDATA;
248 for (i = 0; i < new_huff.num_rows; i++)
249 new_huff.xbits[i] = get_bits(gb, 4);
251 /* Have we got the same custom table? Rebuild if not. */
252 if (ivi_huff_desc_cmp(&new_huff, &huff_tab->cust_desc) || !huff_tab->cust_tab.table) {
253 ivi_huff_desc_copy(&huff_tab->cust_desc, &new_huff);
255 if (huff_tab->cust_tab.table)
256 ff_free_vlc(&huff_tab->cust_tab);
257 result = ivi_create_huff_from_desc(&huff_tab->cust_desc,
258 &huff_tab->cust_tab, 0);
260 // reset faulty description
261 huff_tab->cust_desc.num_rows = 0;
262 av_log(avctx, AV_LOG_ERROR,
263 "Error while initializing custom vlc table!\n");
267 huff_tab->tab = &huff_tab->cust_tab;
269 /* select one of predefined tables */
270 huff_tab->tab = (which_tab) ? &ivi_blk_vlc_tabs[huff_tab->tab_sel]
271 : &ivi_mb_vlc_tabs [huff_tab->tab_sel];
278 * Free planes, bands and macroblocks buffers.
280 * @param[in] planes pointer to the array of the plane descriptors
282 static av_cold void ivi_free_buffers(IVIPlaneDesc *planes)
286 for (p = 0; p < 3; p++) {
288 for (b = 0; b < planes[p].num_bands; b++) {
289 av_freep(&planes[p].bands[b].bufs[0]);
290 av_freep(&planes[p].bands[b].bufs[1]);
291 av_freep(&planes[p].bands[b].bufs[2]);
292 av_freep(&planes[p].bands[b].bufs[3]);
294 if (planes[p].bands[b].blk_vlc.cust_tab.table)
295 ff_free_vlc(&planes[p].bands[b].blk_vlc.cust_tab);
296 for (t = 0; t < planes[p].bands[b].num_tiles; t++)
297 av_freep(&planes[p].bands[b].tiles[t].mbs);
298 av_freep(&planes[p].bands[b].tiles);
300 av_freep(&planes[p].bands);
301 planes[p].num_bands = 0;
305 av_cold int ff_ivi_init_planes(AVCodecContext *avctx, IVIPlaneDesc *planes, const IVIPicConfig *cfg,
309 uint32_t b_width, b_height, align_fac, width_aligned,
310 height_aligned, buf_size;
313 ivi_free_buffers(planes);
315 if (av_image_check_size2(cfg->pic_width, cfg->pic_height, avctx->max_pixels, AV_PIX_FMT_YUV410P, 0, avctx) < 0 ||
316 cfg->luma_bands < 1 || cfg->chroma_bands < 1)
317 return AVERROR_INVALIDDATA;
319 /* fill in the descriptor of the luminance plane */
320 planes[0].width = cfg->pic_width;
321 planes[0].height = cfg->pic_height;
322 planes[0].num_bands = cfg->luma_bands;
324 /* fill in the descriptors of the chrominance planes */
325 planes[1].width = planes[2].width = (cfg->pic_width + 3) >> 2;
326 planes[1].height = planes[2].height = (cfg->pic_height + 3) >> 2;
327 planes[1].num_bands = planes[2].num_bands = cfg->chroma_bands;
329 for (p = 0; p < 3; p++) {
330 planes[p].bands = av_mallocz_array(planes[p].num_bands, sizeof(IVIBandDesc));
331 if (!planes[p].bands)
332 return AVERROR(ENOMEM);
334 /* select band dimensions: if there is only one band then it
335 * has the full size, if there are several bands each of them
336 * has only half size */
337 b_width = planes[p].num_bands == 1 ? planes[p].width
338 : (planes[p].width + 1) >> 1;
339 b_height = planes[p].num_bands == 1 ? planes[p].height
340 : (planes[p].height + 1) >> 1;
342 /* luma band buffers will be aligned on 16x16 (max macroblock size) */
343 /* chroma band buffers will be aligned on 8x8 (max macroblock size) */
344 align_fac = p ? 8 : 16;
345 width_aligned = FFALIGN(b_width , align_fac);
346 height_aligned = FFALIGN(b_height, align_fac);
347 buf_size = width_aligned * height_aligned * sizeof(int16_t);
349 for (b = 0; b < planes[p].num_bands; b++) {
350 band = &planes[p].bands[b]; /* select appropriate plane/band */
353 band->width = b_width;
354 band->height = b_height;
355 band->pitch = width_aligned;
356 band->aheight = height_aligned;
357 band->bufs[0] = av_mallocz(buf_size);
358 band->bufs[1] = av_mallocz(buf_size);
359 band->bufsize = buf_size/2;
360 if (!band->bufs[0] || !band->bufs[1])
361 return AVERROR(ENOMEM);
363 /* allocate the 3rd band buffer for scalability mode */
364 if (cfg->luma_bands > 1) {
365 band->bufs[2] = av_mallocz(buf_size);
367 return AVERROR(ENOMEM);
370 band->bufs[3] = av_mallocz(buf_size);
372 return AVERROR(ENOMEM);
374 /* reset custom vlc */
375 planes[p].bands[0].blk_vlc.cust_desc.num_rows = 0;
382 static int ivi_init_tiles(IVIBandDesc *band, IVITile *ref_tile,
383 int p, int b, int t_height, int t_width)
386 IVITile *tile = band->tiles;
388 for (y = 0; y < band->height; y += t_height) {
389 for (x = 0; x < band->width; x += t_width) {
392 tile->mb_size = band->mb_size;
393 tile->width = FFMIN(band->width - x, t_width);
394 tile->height = FFMIN(band->height - y, t_height);
395 tile->is_empty = tile->data_size = 0;
396 /* calculate number of macroblocks */
397 tile->num_MBs = IVI_MBs_PER_TILE(tile->width, tile->height,
400 av_freep(&tile->mbs);
401 tile->mbs = av_mallocz_array(tile->num_MBs, sizeof(IVIMbInfo));
403 return AVERROR(ENOMEM);
407 if (tile->num_MBs != ref_tile->num_MBs) {
408 av_log(NULL, AV_LOG_DEBUG, "ref_tile mismatch\n");
409 return AVERROR_INVALIDDATA;
411 tile->ref_mbs = ref_tile->mbs;
421 av_cold int ff_ivi_init_tiles(IVIPlaneDesc *planes,
422 int tile_width, int tile_height)
424 int p, b, x_tiles, y_tiles, t_width, t_height, ret;
427 for (p = 0; p < 3; p++) {
428 t_width = !p ? tile_width : (tile_width + 3) >> 2;
429 t_height = !p ? tile_height : (tile_height + 3) >> 2;
431 if (!p && planes[0].num_bands == 4) {
435 if(t_width<=0 || t_height<=0)
436 return AVERROR(EINVAL);
438 for (b = 0; b < planes[p].num_bands; b++) {
439 band = &planes[p].bands[b];
443 for (t = 0; t < band->num_tiles; t++) {
444 av_freep(&band->tiles[t].mbs);
448 x_tiles = IVI_NUM_TILES(band->width, t_width);
449 y_tiles = IVI_NUM_TILES(band->height, t_height);
450 band->num_tiles = x_tiles * y_tiles;
452 av_freep(&band->tiles);
453 band->tiles = av_mallocz_array(band->num_tiles, sizeof(IVITile));
455 return AVERROR(ENOMEM);
457 /* use the first luma band as reference for motion vectors
459 ret = ivi_init_tiles(band, planes[0].bands[0].tiles,
460 p, b, t_height, t_width);
470 * Decode size of the tile data.
471 * The size is stored as a variable-length field having the following format:
472 * if (tile_data_size < 255) than this field is only one byte long
473 * if (tile_data_size >= 255) than this field four is byte long: 0xFF X1 X2 X3
474 * where X1-X3 is size of the tile data
476 * @param[in,out] gb the GetBit context
477 * @return size of the tile data in bytes
479 static int ivi_dec_tile_data_size(GetBitContext *gb)
485 len = get_bits(gb, 8);
487 len = get_bits_long(gb, 24);
490 /* align the bitstream reader on the byte boundary */
496 static int ivi_dc_transform(IVIBandDesc *band, int *prev_dc, int buf_offs,
499 int buf_size = band->pitch * band->aheight - buf_offs;
500 int min_size = (blk_size - 1) * band->pitch + blk_size;
502 if (min_size > buf_size)
503 return AVERROR_INVALIDDATA;
505 band->dc_transform(prev_dc, band->buf + buf_offs,
506 band->pitch, blk_size);
511 static int ivi_decode_coded_blocks(GetBitContext *gb, IVIBandDesc *band,
512 ivi_mc_func mc, ivi_mc_avg_func mc_avg,
514 int mv_x2, int mv_y2,
515 int *prev_dc, int is_intra,
516 int mc_type, int mc_type2,
517 uint32_t quant, int offs,
518 AVCodecContext *avctx)
520 const uint16_t *base_tab = is_intra ? band->intra_base : band->inter_base;
521 RVMapDesc *rvmap = band->rv_map;
522 uint8_t col_flags[8];
524 uint32_t sym = 0, lo, hi, q;
526 int blk_size = band->blk_size;
527 int num_coeffs = blk_size * blk_size;
528 int col_mask = blk_size - 1;
530 int min_size = band->pitch * (band->transform_size - 1) +
531 band->transform_size;
532 int buf_size = band->pitch * band->aheight - offs;
534 if (min_size > buf_size)
535 return AVERROR_INVALIDDATA;
538 av_log(avctx, AV_LOG_ERROR, "Scan pattern is not set.\n");
539 return AVERROR_INVALIDDATA;
542 /* zero transform vector */
543 memset(trvec, 0, num_coeffs * sizeof(trvec[0]));
544 /* zero column flags */
545 memset(col_flags, 0, sizeof(col_flags));
546 while (scan_pos <= num_coeffs) {
547 sym = get_vlc2(gb, band->blk_vlc.tab->table,
549 if (sym == rvmap->eob_sym)
550 break; /* End of block */
552 /* Escape - run/val explicitly coded using 3 vlc codes */
553 if (sym == rvmap->esc_sym) {
554 run = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1) + 1;
555 lo = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
556 hi = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
557 /* merge them and convert into signed val */
558 val = IVI_TOSIGNED((hi << 6) | lo);
561 av_log(avctx, AV_LOG_ERROR, "Invalid sym encountered: %"PRIu32".\n", sym);
562 return AVERROR_INVALIDDATA;
564 run = rvmap->runtab[sym];
565 val = rvmap->valtab[sym];
568 /* de-zigzag and dequantize */
570 if (scan_pos >= num_coeffs || scan_pos < 0)
572 pos = band->scan[scan_pos];
575 ff_dlog(avctx, "Val = 0 encountered!\n");
577 q = (base_tab[pos] * quant) >> 9;
579 val = val * q + FFSIGN(val) * (((q ^ 1) - 1) >> 1);
581 /* track columns containing non-zero coeffs */
582 col_flags[pos & col_mask] |= !!val;
585 if (scan_pos < 0 || scan_pos >= num_coeffs && sym != rvmap->eob_sym)
586 return AVERROR_INVALIDDATA; /* corrupt block data */
588 /* undoing DC coeff prediction for intra-blocks */
589 if (is_intra && band->is_2d_trans) {
590 *prev_dc += trvec[0];
592 col_flags[0] |= !!*prev_dc;
595 if(band->transform_size > band->blk_size){
596 av_log(NULL, AV_LOG_ERROR, "Too large transform\n");
597 return AVERROR_INVALIDDATA;
600 /* apply inverse transform */
601 band->inv_transform(trvec, band->buf + offs,
602 band->pitch, col_flags);
604 /* apply motion compensation */
606 return ivi_mc(band, mc, mc_avg, offs, mv_x, mv_y, mv_x2, mv_y2,
613 * extract huffman-coded transform coefficients from the bitstream,
614 * dequantize them, apply inverse transform and motion compensation
615 * in order to reconstruct the picture.
617 * @param[in,out] gb the GetBit context
618 * @param[in] band pointer to the band descriptor
619 * @param[in] tile pointer to the tile descriptor
620 * @return result code: 0 - OK, -1 = error (corrupted blocks data)
622 static int ivi_decode_blocks(GetBitContext *gb, IVIBandDesc *band,
623 IVITile *tile, AVCodecContext *avctx)
625 int mbn, blk, num_blocks, blk_size, ret, is_intra;
626 int mc_type = 0, mc_type2 = -1;
627 int mv_x = 0, mv_y = 0, mv_x2 = 0, mv_y2 = 0;
629 uint32_t cbp, quant, buf_offs;
631 ivi_mc_func mc_with_delta_func, mc_no_delta_func;
632 ivi_mc_avg_func mc_avg_with_delta_func, mc_avg_no_delta_func;
633 const uint8_t *scale_tab;
635 /* init intra prediction for the DC coefficient */
637 blk_size = band->blk_size;
638 /* number of blocks per mb */
639 num_blocks = (band->mb_size != blk_size) ? 4 : 1;
641 mc_with_delta_func = ff_ivi_mc_8x8_delta;
642 mc_no_delta_func = ff_ivi_mc_8x8_no_delta;
643 mc_avg_with_delta_func = ff_ivi_mc_avg_8x8_delta;
644 mc_avg_no_delta_func = ff_ivi_mc_avg_8x8_no_delta;
646 mc_with_delta_func = ff_ivi_mc_4x4_delta;
647 mc_no_delta_func = ff_ivi_mc_4x4_no_delta;
648 mc_avg_with_delta_func = ff_ivi_mc_avg_4x4_delta;
649 mc_avg_no_delta_func = ff_ivi_mc_avg_4x4_no_delta;
652 for (mbn = 0, mb = tile->mbs; mbn < tile->num_MBs; mb++, mbn++) {
653 is_intra = !mb->type;
655 buf_offs = mb->buf_offs;
657 quant = band->glob_quant + mb->q_delta;
658 if (avctx->codec_id == AV_CODEC_ID_INDEO4)
659 quant = av_clip_uintp2(quant, 5);
661 quant = av_clip(quant, 0, 23);
663 scale_tab = is_intra ? band->intra_scale : band->inter_scale;
665 quant = scale_tab[quant];
672 if (band->is_halfpel) {
673 mc_type = ((mv_y & 1) << 1) | (mv_x & 1);
674 mc_type2 = ((mv_y2 & 1) << 1) | (mv_x2 & 1);
678 mv_y2 >>= 1; /* convert halfpel vectors into fullpel ones */
682 if (mb->type != 2 && mb->type != 3)
685 int dmv_x, dmv_y, cx, cy;
687 dmv_x = mb->mv_x >> band->is_halfpel;
688 dmv_y = mb->mv_y >> band->is_halfpel;
689 cx = mb->mv_x & band->is_halfpel;
690 cy = mb->mv_y & band->is_halfpel;
692 if (mb->xpos + dmv_x < 0 ||
693 mb->xpos + dmv_x + band->mb_size + cx > band->pitch ||
694 mb->ypos + dmv_y < 0 ||
695 mb->ypos + dmv_y + band->mb_size + cy > band->aheight) {
696 return AVERROR_INVALIDDATA;
699 if (mb->type == 2 || mb->type == 3) {
700 int dmv_x, dmv_y, cx, cy;
702 dmv_x = mb->b_mv_x >> band->is_halfpel;
703 dmv_y = mb->b_mv_y >> band->is_halfpel;
704 cx = mb->b_mv_x & band->is_halfpel;
705 cy = mb->b_mv_y & band->is_halfpel;
707 if (mb->xpos + dmv_x < 0 ||
708 mb->xpos + dmv_x + band->mb_size + cx > band->pitch ||
709 mb->ypos + dmv_y < 0 ||
710 mb->ypos + dmv_y + band->mb_size + cy > band->aheight) {
711 return AVERROR_INVALIDDATA;
716 for (blk = 0; blk < num_blocks; blk++) {
717 /* adjust block position in the buffer according to its number */
719 buf_offs += blk_size;
720 } else if (blk == 2) {
721 buf_offs -= blk_size;
722 buf_offs += blk_size * band->pitch;
725 if (cbp & 1) { /* block coded ? */
726 ret = ivi_decode_coded_blocks(gb, band, mc_with_delta_func,
727 mc_avg_with_delta_func,
728 mv_x, mv_y, mv_x2, mv_y2,
730 mc_type, mc_type2, quant,
735 /* block not coded */
736 /* for intra blocks apply the dc slant transform */
737 /* for inter - perform the motion compensation without delta */
739 ret = ivi_dc_transform(band, &prev_dc, buf_offs, blk_size);
743 ret = ivi_mc(band, mc_no_delta_func, mc_avg_no_delta_func,
744 buf_offs, mv_x, mv_y, mv_x2, mv_y2,
761 * Handle empty tiles by performing data copying and motion
762 * compensation respectively.
764 * @param[in] avctx ptr to the AVCodecContext
765 * @param[in] band pointer to the band descriptor
766 * @param[in] tile pointer to the tile descriptor
767 * @param[in] mv_scale scaling factor for motion vectors
769 static int ivi_process_empty_tile(AVCodecContext *avctx, IVIBandDesc *band,
770 IVITile *tile, int32_t mv_scale)
772 int x, y, need_mc, mbn, blk, num_blocks, mv_x, mv_y, mc_type;
773 int offs, mb_offset, row_offset, ret;
774 IVIMbInfo *mb, *ref_mb;
777 ivi_mc_func mc_no_delta_func;
779 if (tile->num_MBs != IVI_MBs_PER_TILE(tile->width, tile->height, band->mb_size)) {
780 av_log(avctx, AV_LOG_ERROR, "Allocated tile size %d mismatches "
781 "parameters %d in ivi_process_empty_tile()\n",
782 tile->num_MBs, IVI_MBs_PER_TILE(tile->width, tile->height, band->mb_size));
783 return AVERROR_INVALIDDATA;
786 offs = tile->ypos * band->pitch + tile->xpos;
788 ref_mb = tile->ref_mbs;
789 row_offset = band->mb_size * band->pitch;
790 need_mc = 0; /* reset the mc tracking flag */
792 for (y = tile->ypos; y < (tile->ypos + tile->height); y += band->mb_size) {
795 for (x = tile->xpos; x < (tile->xpos + tile->width); x += band->mb_size) {
798 mb->buf_offs = mb_offset;
800 mb->type = 1; /* set the macroblocks type = INTER */
801 mb->cbp = 0; /* all blocks are empty */
803 if (!band->qdelta_present && !band->plane && !band->band_num) {
804 mb->q_delta = band->glob_quant;
809 if (band->inherit_qdelta && ref_mb)
810 mb->q_delta = ref_mb->q_delta;
812 if (band->inherit_mv && ref_mb) {
813 /* motion vector inheritance */
815 mb->mv_x = ivi_scale_mv(ref_mb->mv_x, mv_scale);
816 mb->mv_y = ivi_scale_mv(ref_mb->mv_y, mv_scale);
818 mb->mv_x = ref_mb->mv_x;
819 mb->mv_y = ref_mb->mv_y;
821 need_mc |= mb->mv_x || mb->mv_y; /* tracking non-zero motion vectors */
823 int dmv_x, dmv_y, cx, cy;
825 dmv_x = mb->mv_x >> band->is_halfpel;
826 dmv_y = mb->mv_y >> band->is_halfpel;
827 cx = mb->mv_x & band->is_halfpel;
828 cy = mb->mv_y & band->is_halfpel;
830 if ( mb->xpos + dmv_x < 0
831 || mb->xpos + dmv_x + band->mb_size + cx > band->pitch
832 || mb->ypos + dmv_y < 0
833 || mb->ypos + dmv_y + band->mb_size + cy > band->aheight) {
834 av_log(avctx, AV_LOG_ERROR, "MV out of bounds\n");
835 return AVERROR_INVALIDDATA;
843 mb_offset += band->mb_size;
848 if (band->inherit_mv && need_mc) { /* apply motion compensation if there is at least one non-zero motion vector */
849 num_blocks = (band->mb_size != band->blk_size) ? 4 : 1; /* number of blocks per mb */
850 mc_no_delta_func = (band->blk_size == 8) ? ff_ivi_mc_8x8_no_delta
851 : ff_ivi_mc_4x4_no_delta;
853 for (mbn = 0, mb = tile->mbs; mbn < tile->num_MBs; mb++, mbn++) {
856 if (!band->is_halfpel) {
857 mc_type = 0; /* we have only fullpel vectors */
859 mc_type = ((mv_y & 1) << 1) | (mv_x & 1);
861 mv_y >>= 1; /* convert halfpel vectors into fullpel ones */
864 for (blk = 0; blk < num_blocks; blk++) {
865 /* adjust block position in the buffer according with its number */
866 offs = mb->buf_offs + band->blk_size * ((blk & 1) + !!(blk & 2) * band->pitch);
867 ret = ivi_mc(band, mc_no_delta_func, 0, offs,
868 mv_x, mv_y, 0, 0, mc_type, -1);
874 /* copy data from the reference tile into the current one */
875 src = band->ref_buf + tile->ypos * band->pitch + tile->xpos;
876 dst = band->buf + tile->ypos * band->pitch + tile->xpos;
877 for (y = 0; y < tile->height; y++) {
878 memcpy(dst, src, tile->width*sizeof(band->buf[0]));
889 static uint16_t ivi_calc_band_checksum(IVIBandDesc *band)
892 int16_t *src, checksum;
897 for (y = 0; y < band->height; src += band->pitch, y++)
898 for (x = 0; x < band->width; x++)
906 * Convert and output the current plane.
907 * This conversion is done by adding back the bias value of 128
908 * (subtracted in the encoder) and clipping the result.
910 * @param[in] plane pointer to the descriptor of the plane being processed
911 * @param[out] dst pointer to the buffer receiving converted pixels
912 * @param[in] dst_pitch pitch for moving to the next y line
914 static void ivi_output_plane(IVIPlaneDesc *plane, uint8_t *dst, ptrdiff_t dst_pitch)
917 const int16_t *src = plane->bands[0].buf;
918 ptrdiff_t pitch = plane->bands[0].pitch;
923 for (y = 0; y < plane->height; y++) {
925 int w = plane->width;
926 for (x = 0; x < w; x++) {
927 int t = src[x] + 128;
932 for (x = 0; x < w; x++)
933 dst[x] = av_clip_uint8(src[x] + 128);
940 * Decode an Indeo 4 or 5 band.
942 * @param[in,out] ctx ptr to the decoder context
943 * @param[in,out] band ptr to the band descriptor
944 * @param[in] avctx ptr to the AVCodecContext
945 * @return result code: 0 = OK, -1 = error
947 static int decode_band(IVI45DecContext *ctx,
948 IVIBandDesc *band, AVCodecContext *avctx)
950 int result, i, t, idx1, idx2, pos;
953 band->buf = band->bufs[ctx->dst_buf];
955 av_log(avctx, AV_LOG_ERROR, "Band buffer points to no data!\n");
956 return AVERROR_INVALIDDATA;
958 if (ctx->is_indeo4 && ctx->frame_type == IVI4_FRAMETYPE_BIDIR) {
959 band->ref_buf = band->bufs[ctx->b_ref_buf];
960 band->b_ref_buf = band->bufs[ctx->ref_buf];
962 band->ref_buf = band->bufs[ctx->ref_buf];
965 band->data_ptr = ctx->frame_data + (get_bits_count(&ctx->gb) >> 3);
967 result = ctx->decode_band_hdr(ctx, band, avctx);
969 av_log(avctx, AV_LOG_ERROR, "Error while decoding band header: %d\n",
974 if (band->is_empty) {
975 av_log(avctx, AV_LOG_ERROR, "Empty band encountered!\n");
976 return AVERROR_INVALIDDATA;
979 band->rv_map = &ctx->rvmap_tabs[band->rvmap_sel];
981 /* apply corrections to the selected rvmap table if present */
982 for (i = 0; i < band->num_corr; i++) {
983 idx1 = band->corr[i * 2];
984 idx2 = band->corr[i * 2 + 1];
985 FFSWAP(uint8_t, band->rv_map->runtab[idx1], band->rv_map->runtab[idx2]);
986 FFSWAP(int16_t, band->rv_map->valtab[idx1], band->rv_map->valtab[idx2]);
987 if (idx1 == band->rv_map->eob_sym || idx2 == band->rv_map->eob_sym)
988 band->rv_map->eob_sym ^= idx1 ^ idx2;
989 if (idx1 == band->rv_map->esc_sym || idx2 == band->rv_map->esc_sym)
990 band->rv_map->esc_sym ^= idx1 ^ idx2;
993 pos = get_bits_count(&ctx->gb);
995 for (t = 0; t < band->num_tiles; t++) {
996 tile = &band->tiles[t];
998 if (tile->mb_size != band->mb_size) {
999 av_log(avctx, AV_LOG_ERROR, "MB sizes mismatch: %d vs. %d\n",
1000 band->mb_size, tile->mb_size);
1001 return AVERROR_INVALIDDATA;
1003 tile->is_empty = get_bits1(&ctx->gb);
1004 if (tile->is_empty) {
1005 result = ivi_process_empty_tile(avctx, band, tile,
1006 (ctx->planes[0].bands[0].mb_size >> 3) - (band->mb_size >> 3));
1009 ff_dlog(avctx, "Empty tile encountered!\n");
1011 tile->data_size = ivi_dec_tile_data_size(&ctx->gb);
1012 if (!tile->data_size) {
1013 av_log(avctx, AV_LOG_ERROR, "Tile data size is zero!\n");
1014 result = AVERROR_INVALIDDATA;
1018 result = ctx->decode_mb_info(ctx, band, tile, avctx);
1022 result = ivi_decode_blocks(&ctx->gb, band, tile, avctx);
1024 av_log(avctx, AV_LOG_ERROR,
1025 "Corrupted tile data encountered!\n");
1029 if (((get_bits_count(&ctx->gb) - pos) >> 3) != tile->data_size) {
1030 av_log(avctx, AV_LOG_ERROR,
1031 "Tile data_size mismatch!\n");
1032 result = AVERROR_INVALIDDATA;
1036 pos += tile->data_size << 3; // skip to next tile
1040 /* restore the selected rvmap table by applying its corrections in
1042 for (i = band->num_corr-1; i >= 0; i--) {
1043 idx1 = band->corr[i*2];
1044 idx2 = band->corr[i*2+1];
1045 FFSWAP(uint8_t, band->rv_map->runtab[idx1], band->rv_map->runtab[idx2]);
1046 FFSWAP(int16_t, band->rv_map->valtab[idx1], band->rv_map->valtab[idx2]);
1047 if (idx1 == band->rv_map->eob_sym || idx2 == band->rv_map->eob_sym)
1048 band->rv_map->eob_sym ^= idx1 ^ idx2;
1049 if (idx1 == band->rv_map->esc_sym || idx2 == band->rv_map->esc_sym)
1050 band->rv_map->esc_sym ^= idx1 ^ idx2;
1054 if (band->checksum_present) {
1055 uint16_t chksum = ivi_calc_band_checksum(band);
1056 if (chksum != band->checksum) {
1057 av_log(avctx, AV_LOG_ERROR,
1058 "Band checksum mismatch! Plane %d, band %d, "
1059 "received: %"PRIx32", calculated: %"PRIx16"\n",
1060 band->plane, band->band_num, band->checksum, chksum);
1065 align_get_bits(&ctx->gb);
1070 int ff_ivi_decode_frame(AVCodecContext *avctx, void *data, int *got_frame,
1073 IVI45DecContext *ctx = avctx->priv_data;
1074 const uint8_t *buf = avpkt->data;
1075 AVFrame *frame = data;
1076 int buf_size = avpkt->size;
1079 result = init_get_bits8(&ctx->gb, buf, buf_size);
1082 ctx->frame_data = buf;
1083 ctx->frame_size = buf_size;
1085 result = ctx->decode_pic_hdr(ctx, avctx);
1087 av_log(avctx, AV_LOG_ERROR,
1088 "Error while decoding picture header: %d\n", result);
1091 if (ctx->gop_invalid)
1092 return AVERROR_INVALIDDATA;
1094 if (ctx->is_indeo4 && ctx->frame_type == IVI4_FRAMETYPE_NULL_LAST) {
1095 if (ctx->got_p_frame) {
1096 av_frame_move_ref(data, ctx->p_frame);
1098 ctx->got_p_frame = 0;
1105 if (ctx->gop_flags & IVI5_IS_PROTECTED) {
1106 avpriv_report_missing_feature(avctx, "Password-protected clip");
1107 return AVERROR_PATCHWELCOME;
1110 if (!ctx->planes[0].bands) {
1111 av_log(avctx, AV_LOG_ERROR, "Color planes not initialized yet\n");
1112 return AVERROR_INVALIDDATA;
1115 ctx->switch_buffers(ctx);
1119 if (ctx->is_nonnull_frame(ctx)) {
1120 ctx->buf_invalid[ctx->dst_buf] = 1;
1121 for (p = 0; p < 3; p++) {
1122 for (b = 0; b < ctx->planes[p].num_bands; b++) {
1123 result = decode_band(ctx, &ctx->planes[p].bands[b], avctx);
1125 av_log(avctx, AV_LOG_ERROR,
1126 "Error while decoding band: %d, plane: %d\n", b, p);
1131 ctx->buf_invalid[ctx->dst_buf] = 0;
1133 if (ctx->is_scalable)
1134 return AVERROR_INVALIDDATA;
1136 for (p = 0; p < 3; p++) {
1137 if (!ctx->planes[p].bands[0].buf)
1138 return AVERROR_INVALIDDATA;
1141 if (ctx->buf_invalid[ctx->dst_buf])
1144 //STOP_TIMER("decode_planes"); }
1146 if (!ctx->is_nonnull_frame(ctx))
1149 result = ff_set_dimensions(avctx, ctx->planes[0].width, ctx->planes[0].height);
1153 if ((result = ff_get_buffer(avctx, frame, 0)) < 0)
1156 if (ctx->is_scalable) {
1158 ff_ivi_recompose_haar(&ctx->planes[0], frame->data[0], frame->linesize[0]);
1160 ff_ivi_recompose53 (&ctx->planes[0], frame->data[0], frame->linesize[0]);
1162 ivi_output_plane(&ctx->planes[0], frame->data[0], frame->linesize[0]);
1165 ivi_output_plane(&ctx->planes[2], frame->data[1], frame->linesize[1]);
1166 ivi_output_plane(&ctx->planes[1], frame->data[2], frame->linesize[2]);
1170 /* If the bidirectional mode is enabled, next I and the following P
1171 * frame will be sent together. Unfortunately the approach below seems
1172 * to be the only way to handle the B-frames mode.
1173 * That's exactly the same Intel decoders do.
1175 if (ctx->is_indeo4 && ctx->frame_type == IVI4_FRAMETYPE_INTRA) {
1178 // skip version string
1179 while (get_bits(&ctx->gb, 8)) {
1180 if (get_bits_left(&ctx->gb) < 8)
1181 return AVERROR_INVALIDDATA;
1183 left = get_bits_count(&ctx->gb) & 0x18;
1184 skip_bits_long(&ctx->gb, 64 - left);
1185 if (get_bits_left(&ctx->gb) > 18 &&
1186 show_bits_long(&ctx->gb, 21) == 0xBFFF8) { // syncheader + inter type
1188 pkt.data = avpkt->data + (get_bits_count(&ctx->gb) >> 3);
1189 pkt.size = get_bits_left(&ctx->gb) >> 3;
1190 ff_ivi_decode_frame(avctx, ctx->p_frame, &ctx->got_p_frame, &pkt);
1194 if (ctx->show_indeo4_info) {
1195 if (ctx->is_scalable)
1196 av_log(avctx, AV_LOG_DEBUG, "This video uses scalability mode\n");
1197 if (ctx->uses_tiling)
1198 av_log(avctx, AV_LOG_DEBUG, "This video uses local decoding\n");
1199 if (ctx->has_b_frames)
1200 av_log(avctx, AV_LOG_DEBUG, "This video contains B-frames\n");
1201 if (ctx->has_transp)
1202 av_log(avctx, AV_LOG_DEBUG, "Transparency mode is enabled\n");
1204 av_log(avctx, AV_LOG_DEBUG, "This video uses Haar transform\n");
1205 if (ctx->uses_fullpel)
1206 av_log(avctx, AV_LOG_DEBUG, "This video uses fullpel motion vectors\n");
1207 ctx->show_indeo4_info = 0;
1214 * Close Indeo5 decoder and clean up its context.
1216 av_cold int ff_ivi_decode_close(AVCodecContext *avctx)
1218 IVI45DecContext *ctx = avctx->priv_data;
1220 ivi_free_buffers(&ctx->planes[0]);
1222 if (ctx->mb_vlc.cust_tab.table)
1223 ff_free_vlc(&ctx->mb_vlc.cust_tab);
1225 if (ctx->blk_vlc.cust_tab.table)
1226 ff_free_vlc(&ctx->blk_vlc.cust_tab);
1228 av_frame_free(&ctx->p_frame);
1235 * Scan patterns shared between indeo4 and indeo5
1237 const uint8_t ff_ivi_vertical_scan_8x8[64] = {
1238 0, 8, 16, 24, 32, 40, 48, 56,
1239 1, 9, 17, 25, 33, 41, 49, 57,
1240 2, 10, 18, 26, 34, 42, 50, 58,
1241 3, 11, 19, 27, 35, 43, 51, 59,
1242 4, 12, 20, 28, 36, 44, 52, 60,
1243 5, 13, 21, 29, 37, 45, 53, 61,
1244 6, 14, 22, 30, 38, 46, 54, 62,
1245 7, 15, 23, 31, 39, 47, 55, 63
1248 const uint8_t ff_ivi_horizontal_scan_8x8[64] = {
1249 0, 1, 2, 3, 4, 5, 6, 7,
1250 8, 9, 10, 11, 12, 13, 14, 15,
1251 16, 17, 18, 19, 20, 21, 22, 23,
1252 24, 25, 26, 27, 28, 29, 30, 31,
1253 32, 33, 34, 35, 36, 37, 38, 39,
1254 40, 41, 42, 43, 44, 45, 46, 47,
1255 48, 49, 50, 51, 52, 53, 54, 55,
1256 56, 57, 58, 59, 60, 61, 62, 63
1259 const uint8_t ff_ivi_direct_scan_4x4[16] = {
1260 0, 1, 4, 8, 5, 2, 3, 6, 9, 12, 13, 10, 7, 11, 14, 15
1265 * Run-value (RLE) tables.
1267 const RVMapDesc ff_ivi_rvmap_tabs[9] = {
1272 {1, 1, 0, 1, 1, 0, 1, 1, 2, 2, 1, 1, 1, 1, 3, 3,
1273 1, 1, 2, 2, 1, 1, 4, 4, 1, 1, 1, 1, 2, 2, 5, 5,
1274 1, 1, 3, 3, 1, 1, 6, 6, 1, 2, 1, 2, 7, 7, 1, 1,
1275 8, 8, 1, 1, 4, 2, 1, 4, 2, 1, 3, 3, 1, 1, 1, 9,
1276 9, 1, 2, 1, 2, 1, 5, 5, 1, 1, 10, 10, 1, 1, 3, 3,
1277 2, 2, 1, 1, 11, 11, 6, 4, 4, 1, 6, 1, 2, 1, 2, 12,
1278 8, 1, 12, 7, 8, 7, 1, 16, 1, 16, 1, 3, 3, 13, 1, 13,
1279 2, 2, 1, 15, 1, 5, 14, 15, 1, 5, 14, 1, 17, 8, 17, 8,
1280 1, 4, 4, 2, 2, 1, 25, 25, 24, 24, 1, 3, 1, 3, 1, 8,
1281 6, 7, 6, 1, 18, 8, 18, 1, 7, 23, 2, 2, 23, 1, 1, 21,
1282 22, 9, 9, 22, 19, 1, 21, 5, 19, 5, 1, 33, 20, 33, 20, 8,
1283 4, 4, 1, 32, 2, 2, 8, 3, 32, 26, 3, 1, 7, 7, 26, 6,
1284 1, 6, 1, 1, 16, 1, 10, 1, 10, 2, 16, 29, 28, 2, 29, 28,
1285 1, 27, 5, 8, 5, 27, 1, 8, 3, 7, 3, 31, 41, 31, 1, 41,
1286 6, 1, 6, 7, 4, 4, 1, 1, 2, 1, 2, 11, 34, 30, 11, 1,
1287 30, 15, 15, 34, 36, 40, 36, 40, 35, 35, 37, 37, 39, 39, 38, 38},
1290 { 1, -1, 0, 2, -2, 0, 3, -3, 1, -1, 4, -4, 5, -5, 1, -1,
1291 6, -6, 2, -2, 7, -7, 1, -1, 8, -8, 9, -9, 3, -3, 1, -1,
1292 10, -10, 2, -2, 11, -11, 1, -1, 12, 4, -12, -4, 1, -1, 13, -13,
1293 1, -1, 14, -14, 2, 5, 15, -2, -5, -15, -3, 3, 16, -16, 17, 1,
1294 -1, -17, 6, 18, -6, -18, 2, -2, 19, -19, 1, -1, 20, -20, 4, -4,
1295 7, -7, 21, -21, 1, -1, 2, 3, -3, 22, -2, -22, 8, 23, -8, 1,
1296 2, -23, -1, 2, -2, -2, 24, 1, -24, -1, 25, 5, -5, 1, -25, -1,
1297 9, -9, 26, 1, -26, 3, 1, -1, 27, -3, -1, -27, 1, 3, -1, -3,
1298 28, -4, 4, 10, -10, -28, 1, -1, 1, -1, 29, 6, -29, -6, 30, -4,
1299 3, 3, -3, -30, 1, 4, -1, 31, -3, 1, 11, -11, -1, -31, 32, -1,
1300 -1, 2, -2, 1, 1, -32, 1, 4, -1, -4, 33, -1, 1, 1, -1, 5,
1301 5, -5, -33, -1, -12, 12, -5, -7, 1, 1, 7, 34, 4, -4, -1, 4,
1302 -34, -4, 35, 36, -2, -35, -2, -36, 2, 13, 2, -1, 1, -13, 1, -1,
1303 37, 1, -5, 6, 5, -1, 38, -6, -8, 5, 8, -1, 1, 1, -37, -1,
1304 5, 39, -5, -5, 6, -6, -38, -39, -14, 40, 14, 2, 1, 1, -2, -40,
1305 -1, -2, 2, -1, -1, -1, 1, 1, 1, -1, 1, -1, 1, -1, 1, -1}
1311 {0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 8, 6, 8, 7,
1312 7, 9, 9, 10, 10, 11, 11, 1, 12, 1, 12, 13, 13, 16, 14, 16,
1313 14, 15, 15, 17, 17, 18, 0, 18, 19, 20, 21, 19, 22, 21, 20, 22,
1314 25, 24, 2, 25, 24, 23, 23, 2, 26, 28, 26, 28, 29, 27, 29, 27,
1315 33, 33, 1, 32, 1, 3, 32, 30, 36, 3, 36, 30, 31, 31, 35, 34,
1316 37, 41, 34, 35, 37, 4, 41, 4, 49, 8, 8, 49, 40, 38, 5, 38,
1317 40, 39, 5, 39, 42, 43, 42, 7, 57, 6, 43, 44, 6, 50, 7, 44,
1318 57, 48, 50, 48, 45, 45, 46, 47, 51, 46, 47, 58, 1, 51, 58, 1,
1319 52, 59, 53, 9, 52, 55, 55, 59, 53, 56, 54, 56, 54, 9, 64, 64,
1320 60, 63, 60, 63, 61, 62, 61, 62, 2, 10, 2, 10, 11, 1, 11, 13,
1321 12, 1, 12, 13, 16, 16, 8, 8, 14, 3, 3, 15, 14, 15, 4, 4,
1322 1, 17, 17, 5, 1, 7, 7, 5, 6, 1, 2, 2, 6, 22, 1, 25,
1323 21, 22, 8, 24, 1, 21, 25, 24, 8, 18, 18, 23, 9, 20, 23, 33,
1324 29, 33, 20, 1, 19, 1, 29, 36, 9, 36, 19, 41, 28, 57, 32, 3,
1325 28, 3, 1, 27, 49, 49, 1, 32, 26, 26, 2, 4, 4, 7, 57, 41,
1326 2, 7, 10, 5, 37, 16, 10, 27, 8, 8, 13, 16, 37, 13, 1, 5},
1329 {0, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, 1, -1, -1, 1,
1330 -1, 1, -1, 1, -1, 1, -1, 2, 1, -2, -1, 1, -1, 1, 1, -1,
1331 -1, 1, -1, 1, -1, 1, 0, -1, 1, 1, 1, -1, 1, -1, -1, -1,
1332 1, 1, 2, -1, -1, 1, -1, -2, 1, 1, -1, -1, 1, 1, -1, -1,
1333 1, -1, 3, 1, -3, 2, -1, 1, 1, -2, -1, -1, -1, 1, 1, 1,
1334 1, 1, -1, -1, -1, 2, -1, -2, 1, 2, -2, -1, 1, 1, 2, -1,
1335 -1, 1, -2, -1, 1, 1, -1, 2, 1, 2, -1, 1, -2, -1, -2, -1,
1336 -1, 1, 1, -1, 1, -1, 1, 1, 1, -1, -1, 1, 4, -1, -1, -4,
1337 1, 1, 1, 2, -1, -1, 1, -1, -1, 1, -1, -1, 1, -2, 1, -1,
1338 1, 1, -1, -1, 1, 1, -1, -1, 3, 2, -3, -2, 2, 5, -2, 2,
1339 2, -5, -2, -2, -2, 2, -3, 3, 2, 3, -3, 2, -2, -2, 3, -3,
1340 6, 2, -2, 3, -6, 3, -3, -3, 3, 7, -4, 4, -3, 2, -7, 2,
1341 2, -2, -4, 2, 8, -2, -2, -2, 4, 2, -2, 2, 3, 2, -2, -2,
1342 2, 2, -2, -8, -2, 9, -2, 2, -3, -2, 2, -2, 2, 2, 2, 4,
1343 -2, -4, 10, 2, 2, -2, -9, -2, 2, -2, 5, 4, -4, 4, -2, 2,
1344 -5, -4, -3, 4, 2, -3, 3, -2, -5, 5, 3, 3, -2, -3, -10, -4}
1350 {1, 1, 0, 2, 2, 1, 1, 3, 3, 4, 4, 0, 1, 1, 5, 5,
1351 2, 2, 6, 6, 7, 7, 1, 8, 1, 8, 3, 3, 9, 9, 1, 2,
1352 2, 1, 4, 10, 4, 10, 11, 11, 1, 5, 12, 12, 1, 5, 13, 13,
1353 3, 3, 6, 6, 2, 2, 14, 14, 16, 16, 15, 7, 15, 8, 8, 7,
1354 1, 1, 17, 17, 4, 4, 1, 1, 18, 18, 2, 2, 5, 5, 25, 3,
1355 9, 3, 25, 9, 19, 24, 19, 24, 1, 21, 20, 1, 21, 22, 20, 22,
1356 23, 23, 8, 6, 33, 6, 8, 33, 7, 7, 26, 26, 1, 32, 1, 32,
1357 28, 4, 28, 10, 29, 27, 27, 10, 41, 4, 29, 2, 2, 41, 36, 31,
1358 49, 31, 34, 30, 34, 36, 30, 35, 1, 49, 11, 5, 35, 11, 1, 3,
1359 3, 5, 37, 37, 8, 40, 8, 40, 12, 12, 42, 42, 1, 38, 16, 57,
1360 1, 6, 16, 39, 38, 6, 7, 7, 13, 13, 39, 43, 2, 43, 57, 2,
1361 50, 9, 44, 9, 50, 4, 15, 48, 44, 4, 1, 15, 48, 14, 14, 1,
1362 45, 45, 8, 3, 5, 8, 51, 47, 3, 46, 46, 47, 5, 51, 1, 17,
1363 17, 58, 1, 58, 2, 52, 52, 2, 53, 7, 59, 6, 6, 56, 53, 55,
1364 7, 55, 1, 54, 59, 56, 54, 10, 1, 10, 4, 60, 1, 60, 8, 4,
1365 8, 64, 64, 61, 1, 63, 3, 63, 62, 61, 5, 11, 5, 3, 11, 62},
1368 { 1, -1, 0, 1, -1, 2, -2, 1, -1, 1, -1, 0, 3, -3, 1, -1,
1369 2, -2, 1, -1, 1, -1, 4, 1, -4, -1, 2, -2, 1, -1, 5, 3,
1370 -3, -5, 2, 1, -2, -1, 1, -1, 6, 2, 1, -1, -6, -2, 1, -1,
1371 3, -3, 2, -2, 4, -4, 1, -1, 1, -1, 1, 2, -1, 2, -2, -2,
1372 7, -7, 1, -1, 3, -3, 8, -8, 1, -1, 5, -5, 3, -3, 1, 4,
1373 2, -4, -1, -2, 1, 1, -1, -1, 9, 1, 1, -9, -1, 1, -1, -1,
1374 1, -1, 3, -3, 1, 3, -3, -1, 3, -3, 1, -1, 10, 1, -10, -1,
1375 1, 4, -1, 2, 1, -1, 1, -2, 1, -4, -1, 6, -6, -1, 1, 1,
1376 1, -1, 1, 1, -1, -1, -1, 1, 11, -1, -2, 4, -1, 2, -11, 5,
1377 -5, -4, -1, 1, 4, 1, -4, -1, -2, 2, 1, -1, 12, 1, -2, 1,
1378 -12, 4, 2, 1, -1, -4, 4, -4, 2, -2, -1, 1, 7, -1, -1, -7,
1379 -1, -3, 1, 3, 1, 5, 2, 1, -1, -5, 13, -2, -1, 2, -2, -13,
1380 1, -1, 5, 6, 5, -5, 1, 1, -6, 1, -1, -1, -5, -1, 14, 2,
1381 -2, 1, -14, -1, 8, 1, -1, -8, 1, 5, 1, 5, -5, 1, -1, 1,
1382 -5, -1, 15, 1, -1, -1, -1, 3, -15, -3, 6, 1, 16, -1, 6, -6,
1383 -6, 1, -1, 1, -16, 1, 7, -1, 1, -1, -6, -3, 6, -7, 3, -1}
1389 {0, 1, 1, 2, 2, 3, 3, 4, 4, 1, 1, 5, 5, 6, 6, 7,
1390 7, 8, 8, 9, 9, 2, 2, 10, 10, 1, 1, 11, 11, 12, 12, 3,
1391 3, 13, 13, 0, 14, 14, 16, 15, 16, 15, 4, 4, 17, 1, 17, 1,
1392 5, 5, 18, 18, 2, 2, 6, 6, 8, 19, 7, 8, 7, 19, 20, 20,
1393 21, 21, 22, 24, 22, 24, 23, 23, 1, 1, 25, 25, 3, 3, 26, 26,
1394 9, 9, 27, 27, 28, 28, 33, 29, 4, 33, 29, 1, 4, 1, 32, 32,
1395 2, 2, 31, 10, 30, 10, 30, 31, 34, 34, 5, 5, 36, 36, 35, 41,
1396 35, 11, 41, 11, 37, 1, 8, 8, 37, 6, 1, 6, 40, 7, 7, 40,
1397 12, 38, 12, 39, 39, 38, 49, 13, 49, 13, 3, 42, 3, 42, 16, 16,
1398 43, 43, 14, 14, 1, 1, 44, 15, 44, 15, 2, 2, 57, 48, 50, 48,
1399 57, 50, 4, 45, 45, 4, 46, 47, 47, 46, 1, 51, 1, 17, 17, 51,
1400 8, 9, 9, 5, 58, 8, 58, 5, 52, 52, 55, 56, 53, 56, 55, 59,
1401 59, 53, 54, 1, 6, 54, 7, 7, 6, 1, 2, 3, 2, 3, 64, 60,
1402 60, 10, 10, 64, 61, 62, 61, 63, 1, 63, 62, 1, 18, 24, 18, 4,
1403 25, 4, 8, 21, 21, 1, 24, 22, 25, 22, 8, 11, 19, 11, 23, 1,
1404 20, 23, 19, 20, 5, 12, 5, 1, 16, 2, 12, 13, 2, 13, 1, 16},
1407 { 0, 1, -1, 1, -1, 1, -1, 1, -1, 2, -2, 1, -1, 1, -1, 1,
1408 -1, 1, -1, 1, -1, 2, -2, 1, -1, 3, -3, 1, -1, 1, -1, 2,
1409 -2, 1, -1, 0, 1, -1, 1, 1, -1, -1, 2, -2, 1, 4, -1, -4,
1410 2, -2, 1, -1, -3, 3, 2, -2, 2, 1, 2, -2, -2, -1, 1, -1,
1411 1, -1, 1, 1, -1, -1, 1, -1, 5, -5, 1, -1, 3, -3, 1, -1,
1412 2, -2, 1, -1, 1, -1, 1, 1, 3, -1, -1, 6, -3, -6, -1, 1,
1413 4, -4, 1, 2, 1, -2, -1, -1, 1, -1, 3, -3, 1, -1, 1, 1,
1414 -1, 2, -1, -2, 1, 7, -3, 3, -1, 3, -7, -3, 1, -3, 3, -1,
1415 2, 1, -2, 1, -1, -1, 1, 2, -1, -2, -4, -1, 4, 1, 2, -2,
1416 1, -1, -2, 2, 8, -8, -1, 2, 1, -2, -5, 5, 1, -1, -1, 1,
1417 -1, 1, 4, -1, 1, -4, -1, -1, 1, 1, 9, 1, -9, 2, -2, -1,
1418 -4, 3, -3, -4, -1, 4, 1, 4, 1, -1, 1, -1, 1, 1, -1, 1,
1419 -1, -1, -1, 10, 4, 1, 4, -4, -4, -10, 6, 5, -6, -5, 1, -1,
1420 1, 3, -3, -1, 1, -1, -1, -1, 11, 1, 1, -11, -2, -2, 2, 5,
1421 -2, -5, -5, 2, -2, 12, 2, -2, 2, 2, 5, -3, -2, 3, -2, -12,
1422 -2, 2, 2, 2, -5, 3, 5, 13, -3, 7, -3, -3, -7, 3, -13, 3}
1428 {0, 1, 1, 1, 2, 2, 1, 3, 3, 1, 1, 1, 4, 4, 1, 5,
1429 2, 1, 5, 2, 1, 1, 6, 6, 1, 1, 1, 1, 1, 7, 3, 1,
1430 2, 3, 0, 1, 2, 7, 1, 1, 1, 8, 1, 1, 8, 1, 1, 1,
1431 9, 1, 9, 1, 2, 1, 1, 2, 1, 1, 10, 4, 1, 10, 1, 4,
1432 1, 1, 1, 1, 1, 3, 1, 1, 1, 3, 2, 1, 5, 1, 1, 1,
1433 2, 5, 1, 11, 1, 11, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1434 2, 1, 6, 1, 6, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 12,
1435 3, 1, 12, 1, 1, 1, 2, 1, 1, 3, 1, 1, 1, 1, 1, 1,
1436 4, 1, 1, 1, 2, 1, 1, 4, 1, 1, 1, 1, 1, 1, 2, 1,
1437 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 2, 1, 1, 5,
1438 1, 1, 1, 1, 1, 7, 1, 7, 1, 1, 2, 3, 1, 1, 1, 1,
1439 5, 1, 1, 1, 1, 1, 1, 2, 13, 1, 1, 1, 1, 1, 1, 1,
1440 1, 1, 1, 1, 1, 1, 1, 1, 13, 2, 1, 1, 4, 1, 1, 1,
1441 3, 1, 6, 1, 1, 1, 14, 1, 1, 1, 1, 1, 14, 6, 1, 1,
1442 1, 1, 15, 2, 4, 1, 2, 3, 15, 1, 1, 1, 8, 1, 1, 8,
1443 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1},
1446 { 0, 1, -1, 2, 1, -1, -2, 1, -1, 3, -3, 4, 1, -1, -4, 1,
1447 2, 5, -1, -2, -5, 6, 1, -1, -6, 7, -7, 8, -8, 1, 2, 9,
1448 3, -2, 0, -9, -3, -1, 10, -10, 11, 1, -11, 12, -1, -12, 13, -13,
1449 1, 14, -1, -14, 4, 15, -15, -4, 16, -16, 1, 2, 17, -1, -17, -2,
1450 18, -18, 19, -19, 20, 3, -20, 21, -21, -3, 5, 22, 2, -22, -23, 23,
1451 -5, -2, 24, 1, -24, -1, 25, -25, 26, -26, -27, 27, 28, 29, -28, -29,
1452 6, 30, 2, -31, -2, -30, 31, -6, -32, 32, 33, -33, 34, -35, -34, 1,
1453 4, -36, -1, 35, 37, 36, 7, -37, 38, -4, -38, 39, 41, 40, -40, -39,
1454 3, 42, -43, -41, -7, -42, 43, -3, 44, -44, 45, -45, 46, 47, 8, -47,
1455 -48, -46, 50, -50, 48, 49, 51, -49, 52, -52, 5, -51, -8, -53, 53, 3,
1456 -56, 56, 55, 54, -54, 2, 60, -2, -55, 58, 9, -5, 59, 57, -57, -63,
1457 -3, -58, -60, -61, 61, -59, -62, -9, 1, 64, 62, 69, -64, 63, 65, -67,
1458 -68, 66, -65, 68, -66, -69, 67, -70, -1, 10, 71, -71, 4, 73, 72, 70,
1459 6, -76, -3, 74, -78, -74, 1, 78, 80, -72, -75, 76, -1, 3, -73, 79,
1460 75, 77, 1, 11, -4, -79, -10, -6, -1, -77, -83, -80, 2, 81, -84, -2,
1461 83, -81, 82, -82, 84, -87, -86, 85, -11, -85, 86, -89, 87, -88, 88, 89}
1467 {1, 1, 0, 2, 1, 2, 1, 3, 3, 1, 1, 4, 4, 2, 2, 1,
1468 1, 5, 5, 6, 1, 6, 1, 7, 7, 3, 3, 2, 8, 2, 8, 1,
1469 1, 0, 9, 9, 1, 1, 10, 4, 10, 4, 11, 11, 2, 1, 2, 1,
1470 12, 12, 3, 3, 1, 1, 13, 5, 5, 13, 14, 1, 1, 14, 2, 2,
1471 6, 6, 15, 1, 1, 15, 16, 4, 7, 16, 4, 7, 1, 1, 3, 3,
1472 8, 8, 2, 2, 1, 1, 17, 17, 1, 1, 18, 18, 5, 5, 2, 2,
1473 1, 1, 9, 19, 9, 19, 20, 3, 3, 20, 1, 10, 21, 1, 10, 4,
1474 4, 21, 22, 6, 6, 22, 1, 1, 23, 24, 2, 2, 23, 24, 11, 1,
1475 1, 11, 7, 25, 7, 1, 1, 25, 8, 8, 3, 26, 3, 1, 12, 2,
1476 2, 26, 1, 12, 5, 5, 27, 4, 1, 4, 1, 27, 28, 1, 28, 13,
1477 1, 13, 2, 29, 2, 1, 32, 6, 1, 30, 14, 29, 14, 6, 3, 31,
1478 3, 1, 30, 1, 32, 31, 33, 9, 33, 1, 1, 7, 9, 7, 2, 2,
1479 1, 1, 4, 36, 34, 4, 5, 10, 10, 5, 34, 1, 1, 35, 8, 8,
1480 36, 3, 35, 1, 15, 3, 2, 1, 16, 15, 16, 2, 37, 1, 37, 1,
1481 1, 1, 6, 6, 38, 1, 38, 11, 1, 39, 39, 40, 11, 2, 41, 4,
1482 40, 1, 2, 4, 1, 1, 1, 41, 3, 1, 3, 1, 5, 7, 5, 7},
1485 { 1, -1, 0, 1, 2, -1, -2, 1, -1, 3, -3, 1, -1, 2, -2, 4,
1486 -4, 1, -1, 1, 5, -1, -5, 1, -1, 2, -2, 3, 1, -3, -1, 6,
1487 -6, 0, 1, -1, 7, -7, 1, 2, -1, -2, 1, -1, 4, 8, -4, -8,
1488 1, -1, 3, -3, 9, -9, 1, 2, -2, -1, 1, 10, -10, -1, 5, -5,
1489 2, -2, 1, 11, -11, -1, 1, 3, 2, -1, -3, -2, 12, -12, 4, -4,
1490 2, -2, -6, 6, 13, -13, 1, -1, 14, -14, 1, -1, 3, -3, 7, -7,
1491 15, -15, 2, 1, -2, -1, 1, 5, -5, -1, -16, 2, 1, 16, -2, 4,
1492 -4, -1, 1, 3, -3, -1, 17, -17, 1, 1, -8, 8, -1, -1, 2, 18,
1493 -18, -2, 3, 1, -3, 19, -19, -1, 3, -3, 6, 1, -6, 20, 2, 9,
1494 -9, -1, -20, -2, 4, -4, 1, -5, 21, 5, -21, -1, 1, -22, -1, 2,
1495 22, -2, 10, 1, -10, 23, 1, 4, -23, 1, 2, -1, -2, -4, -7, 1,
1496 7, -24, -1, 24, -1, -1, 1, 3, -1, -25, 25, 4, -3, -4, 11, -11,
1497 26, -26, 6, 1, 1, -6, -5, -3, 3, 5, -1, -27, 27, 1, 4, -4,
1498 -1, -8, -1, 28, 2, 8, -12, -28, -2, -2, 2, 12, -1, 29, 1, -29,
1499 30, -30, 5, -5, 1, -31, -1, 3, 31, -1, 1, 1, -3, -13, 1, -7,
1500 -1, -32, 13, 7, 32, 33, -33, -1, -9, -34, 9, 34, -6, 5, 6, -5}
1506 {1, 1, 0, 1, 1, 2, 2, 1, 1, 3, 3, 1, 1, 0, 2, 2,
1507 4, 1, 4, 1, 1, 1, 5, 5, 1, 1, 6, 6, 2, 2, 1, 1,
1508 3, 3, 7, 7, 1, 1, 8, 8, 1, 1, 2, 2, 1, 9, 1, 9,
1509 4, 4, 10, 1, 1, 10, 1, 1, 11, 11, 3, 3, 1, 2, 1, 2,
1510 1, 1, 12, 12, 5, 5, 1, 1, 13, 1, 1, 13, 2, 2, 1, 1,
1511 6, 6, 1, 1, 4, 14, 4, 14, 3, 1, 3, 1, 1, 1, 15, 7,
1512 15, 2, 2, 7, 1, 1, 1, 8, 1, 8, 16, 16, 1, 1, 1, 1,
1513 2, 1, 1, 2, 1, 1, 3, 5, 5, 3, 4, 1, 1, 4, 1, 1,
1514 17, 17, 9, 1, 1, 9, 2, 2, 1, 1, 10, 10, 1, 6, 1, 1,
1515 6, 18, 1, 1, 18, 1, 1, 1, 2, 2, 3, 1, 3, 1, 1, 1,
1516 4, 1, 19, 1, 19, 7, 1, 1, 20, 1, 4, 20, 1, 7, 11, 2,
1517 1, 11, 21, 2, 8, 5, 1, 8, 1, 5, 21, 1, 1, 1, 22, 1,
1518 1, 22, 1, 1, 3, 3, 1, 23, 2, 12, 24, 1, 1, 2, 1, 1,
1519 12, 23, 1, 1, 24, 1, 1, 1, 4, 1, 1, 1, 2, 1, 6, 6,
1520 4, 2, 1, 1, 1, 1, 1, 1, 1, 14, 13, 3, 1, 25, 9, 25,
1521 14, 1, 9, 3, 13, 1, 1, 1, 1, 1, 10, 1, 1, 2, 10, 2},
1524 {-20, -1, 0, 2, -2, 1, -1, 3, -3, 1, -1, 4, -4, 0, 2, -2,
1525 1, 5, -1, -5, 6, -6, 1, -1, 7, -7, 1, -1, 3, -3, 8, -8,
1526 2, -2, 1, -1, 9, -9, 1, -1, 10, -10, 4, -4, 11, 1, -11, -1,
1527 2, -2, 1, 12, -12, -1, 13, -13, 1, -1, 3, -3, 14, 5, -14, -5,
1528 -15, 15, -1, 1, 2, -2, 16, -16, 1, 17, -17, -1, 6, -6, 18, -18,
1529 2, -2, -19, 19, -3, 1, 3, -1, 4, 20, -4, 1, -21, 21, 1, 2,
1530 -1, -7, 7, -2, 22, -22, 23, 2, -23, -2, 1, -1, -24, 24, -25, 25,
1531 -8, -26, 26, 8, -27, 27, 5, 3, -3, -5, -4, 28, -28, 4, 29, -29,
1532 1, -1, -2, -30, 30, 2, 9, -9, -31, 31, 2, -2, -32, 3, 32, -33,
1533 -3, 1, 33, -34, -1, 34, -35, 35, -10, 10, -6, 36, 6, -36, 37, -37,
1534 -5, 38, 1, -38, -1, 3, 39, -39, -1, 40, 5, 1, -40, -3, 2, -11,
1535 -41, -2, 1, 11, -3, -4, 41, 3, 42, 4, -1, -43, -42, 43, 1, -44,
1536 45, -1, 44, -45, -7, 7, -46, 1, -12, 2, 1, -47, 46, 12, 47, 48,
1537 -2, -1, -48, 49, -1, -50, -49, 50, -6, -51, 51, 52, -13, 53, -4, 4,
1538 6, 13, -53, -52, -54, 55, 54, -55, -56, -2, 2, -8, 56, 1, -3, -1,
1539 2, 58, 3, 8, -2, 57, -58, -60, -59, -57, -3, 60, 59, -14, 3, 14}
1545 {1, 1, 0, 2, 2, 1, 1, 3, 3, 4, 4, 5, 5, 1, 1, 6,
1546 6, 2, 2, 7, 7, 8, 8, 1, 1, 3, 3, 9, 9, 10, 10, 1,
1547 1, 2, 2, 4, 4, 11, 0, 11, 12, 12, 13, 13, 1, 1, 5, 5,
1548 14, 14, 15, 16, 15, 16, 3, 3, 1, 6, 1, 6, 2, 2, 7, 7,
1549 8, 8, 17, 17, 1, 1, 4, 4, 18, 18, 2, 2, 1, 19, 1, 20,
1550 19, 20, 21, 21, 3, 3, 22, 22, 5, 5, 24, 1, 1, 23, 9, 23,
1551 24, 9, 2, 2, 10, 1, 1, 10, 6, 6, 25, 4, 4, 25, 7, 7,
1552 26, 8, 1, 8, 3, 1, 26, 3, 11, 11, 27, 27, 2, 28, 1, 2,
1553 28, 1, 12, 12, 5, 5, 29, 13, 13, 29, 32, 1, 1, 33, 31, 30,
1554 32, 4, 30, 33, 4, 31, 3, 14, 1, 1, 3, 34, 34, 2, 2, 14,
1555 6, 6, 35, 36, 35, 36, 1, 15, 1, 16, 16, 15, 7, 9, 7, 9,
1556 37, 8, 8, 37, 1, 1, 39, 2, 38, 39, 2, 40, 5, 38, 40, 5,
1557 3, 3, 4, 4, 10, 10, 1, 1, 1, 1, 41, 2, 41, 2, 6, 6,
1558 1, 1, 11, 42, 11, 43, 3, 42, 3, 17, 4, 43, 1, 17, 7, 1,
1559 8, 44, 4, 7, 44, 5, 8, 2, 5, 1, 2, 48, 45, 1, 12, 45,
1560 12, 48, 13, 13, 1, 9, 9, 46, 1, 46, 47, 47, 49, 18, 18, 49},
1563 { 1, -1, 0, 1, -1, 2, -2, 1, -1, 1, -1, 1, -1, 3, -3, 1,
1564 -1, -2, 2, 1, -1, 1, -1, 4, -4, -2, 2, 1, -1, 1, -1, 5,
1565 -5, -3, 3, 2, -2, 1, 0, -1, 1, -1, 1, -1, 6, -6, 2, -2,
1566 1, -1, 1, 1, -1, -1, -3, 3, 7, 2, -7, -2, -4, 4, 2, -2,
1567 2, -2, 1, -1, 8, -8, 3, -3, 1, -1, -5, 5, 9, 1, -9, 1,
1568 -1, -1, 1, -1, -4, 4, 1, -1, 3, -3, 1, -10, 10, 1, 2, -1,
1569 -1, -2, 6, -6, 2, 11, -11, -2, 3, -3, 1, -4, 4, -1, 3, -3,
1570 1, 3, 12, -3, -5, -12, -1, 5, 2, -2, 1, -1, -7, 1, 13, 7,
1571 -1, -13, 2, -2, 4, -4, 1, 2, -2, -1, 1, 14, -14, 1, 1, 1,
1572 -1, -5, -1, -1, 5, -1, -6, 2, -15, 15, 6, 1, -1, -8, 8, -2,
1573 -4, 4, 1, 1, -1, -1, 16, 2, -16, -2, 2, -2, 4, 3, -4, -3,
1574 -1, -4, 4, 1, -17, 17, -1, -9, 1, 1, 9, 1, -5, -1, -1, 5,
1575 -7, 7, 6, -6, 3, -3, 18, -18, 19, -19, 1, -10, -1, 10, -5, 5,
1576 20, -20, -3, 1, 3, 1, 8, -1, -8, 2, 7, -1, -21, -2, 5, 21,
1577 5, -1, -7, -5, 1, -6, -5, -11, 6, 22, 11, 1, 1, -22, -3, -1,
1578 3, -1, 3, -3, -23, 4, -4, 1, 23, -1, 1, -1, 1, -2, 2, -1}
1584 {1, 1, 1, 1, 0, 2, 2, 1, 1, 3, 3, 0, 1, 1, 2, 2,
1585 4, 4, 1, 1, 5, 5, 1, 1, 2, 2, 3, 3, 6, 6, 1, 1,
1586 7, 7, 8, 1, 8, 2, 2, 1, 4, 4, 1, 3, 1, 3, 9, 9,
1587 2, 2, 1, 5, 1, 5, 10, 10, 1, 1, 11, 11, 3, 6, 3, 4,
1588 4, 6, 2, 2, 1, 12, 1, 12, 7, 13, 7, 13, 1, 1, 8, 8,
1589 2, 2, 14, 14, 16, 15, 16, 5, 5, 1, 3, 15, 1, 3, 4, 4,
1590 1, 1, 17, 17, 2, 2, 6, 6, 1, 18, 1, 18, 22, 21, 22, 21,
1591 25, 24, 25, 19, 9, 20, 9, 23, 19, 24, 20, 3, 23, 7, 3, 1,
1592 1, 7, 28, 26, 29, 5, 28, 26, 5, 8, 29, 4, 8, 27, 2, 2,
1593 4, 27, 1, 1, 10, 36, 10, 33, 33, 36, 30, 1, 32, 32, 1, 30,
1594 6, 31, 31, 35, 3, 6, 11, 11, 3, 2, 35, 2, 34, 1, 34, 1,
1595 37, 37, 12, 7, 12, 5, 41, 5, 4, 7, 1, 8, 13, 4, 1, 41,
1596 13, 38, 8, 38, 9, 1, 40, 40, 9, 1, 39, 2, 2, 49, 39, 42,
1597 3, 3, 14, 16, 49, 14, 16, 42, 43, 43, 6, 6, 15, 1, 1, 15,
1598 44, 44, 1, 1, 50, 48, 4, 5, 4, 7, 5, 2, 10, 10, 48, 7,
1599 50, 45, 2, 1, 45, 8, 8, 1, 46, 46, 3, 47, 47, 3, 1, 1},
1602 { 1, -1, 2, -2, 0, 1, -1, 3, -3, 1, -1, 0, 4, -4, 2, -2,
1603 1, -1, 5, -5, 1, -1, 6, -6, 3, -3, 2, -2, 1, -1, 7, -7,
1604 1, -1, 1, 8, -1, 4, -4, -8, 2, -2, 9, 3, -9, -3, 1, -1,
1605 5, -5, 10, 2, -10, -2, 1, -1, 11, -11, 1, -1, -4, 2, 4, 3,
1606 -3, -2, 6, -6, 12, 1, -12, -1, 2, 1, -2, -1, 13, -13, 2, -2,
1607 7, -7, 1, -1, 1, 1, -1, 3, -3, 14, 5, -1, -14, -5, 4, -4,
1608 15, -15, 1, -1, 8, -8, -3, 3, 16, 1, -16, -1, 1, 1, -1, -1,
1609 1, 1, -1, 1, 2, 1, -2, 1, -1, -1, -1, 6, -1, 3, -6, 17,
1610 -17, -3, 1, 1, 1, 4, -1, -1, -4, 3, -1, 5, -3, -1, -9, 9,
1611 -5, 1, 18, -18, 2, 1, -2, 1, -1, -1, 1, 19, -1, 1, -19, -1,
1612 4, 1, -1, 1, 7, -4, -2, 2, -7, 10, -1, -10, 1, 20, -1, -20,
1613 1, -1, 2, 4, -2, 5, 1, -5, 6, -4, 21, 4, 2, -6, -21, -1,
1614 -2, 1, -4, -1, -3, 22, -1, 1, 3, -22, -1, 11, -11, 1, 1, 1,
1615 8, -8, 2, 2, -1, -2, -2, -1, 1, -1, -5, 5, 2, 23, -23, -2,
1616 1, -1, 24, -24, -1, -1, 7, 6, -7, 5, -6, 12, -3, 3, 1, -5,
1617 1, 1, -12, 25, -1, -5, 5, -25, -1, 1, 9, 1, -1, -9, 26, -26}