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(const 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(const 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(const 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, const 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, const 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, const 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;
778 int clear_first = !band->qdelta_present && !band->plane && !band->band_num;
779 int mb_size = band->mb_size;
780 int xend = tile->xpos + tile->width;
781 int is_halfpel = band->is_halfpel;
782 int pitch = band->pitch;
784 if (tile->num_MBs != IVI_MBs_PER_TILE(tile->width, tile->height, mb_size)) {
785 av_log(avctx, AV_LOG_ERROR, "Allocated tile size %d mismatches "
786 "parameters %d in ivi_process_empty_tile()\n",
787 tile->num_MBs, IVI_MBs_PER_TILE(tile->width, tile->height, mb_size));
788 return AVERROR_INVALIDDATA;
791 offs = tile->ypos * pitch + tile->xpos;
793 ref_mb = tile->ref_mbs;
794 row_offset = mb_size * pitch;
795 need_mc = 0; /* reset the mc tracking flag */
797 for (y = tile->ypos; y < (tile->ypos + tile->height); y += mb_size) {
800 for (x = tile->xpos; x < xend; x += mb_size) {
803 mb->buf_offs = mb_offset;
805 mb->type = 1; /* set the macroblocks type = INTER */
806 mb->cbp = 0; /* all blocks are empty */
809 mb->q_delta = band->glob_quant;
815 if (band->inherit_qdelta)
816 mb->q_delta = ref_mb->q_delta;
818 if (band->inherit_mv) {
819 /* motion vector inheritance */
821 mb->mv_x = ivi_scale_mv(ref_mb->mv_x, mv_scale);
822 mb->mv_y = ivi_scale_mv(ref_mb->mv_y, mv_scale);
824 mb->mv_x = ref_mb->mv_x;
825 mb->mv_y = ref_mb->mv_y;
827 need_mc |= mb->mv_x || mb->mv_y; /* tracking non-zero motion vectors */
829 int dmv_x, dmv_y, cx, cy;
831 dmv_x = mb->mv_x >> is_halfpel;
832 dmv_y = mb->mv_y >> is_halfpel;
833 cx = mb->mv_x & is_halfpel;
834 cy = mb->mv_y & is_halfpel;
836 if ( mb->xpos + dmv_x < 0
837 || mb->xpos + dmv_x + mb_size + cx > pitch
838 || mb->ypos + dmv_y < 0
839 || mb->ypos + dmv_y + mb_size + cy > band->aheight) {
840 av_log(avctx, AV_LOG_ERROR, "MV out of bounds\n");
841 return AVERROR_INVALIDDATA;
849 mb_offset += mb_size;
854 if (band->inherit_mv && need_mc) { /* apply motion compensation if there is at least one non-zero motion vector */
855 num_blocks = (mb_size != band->blk_size) ? 4 : 1; /* number of blocks per mb */
856 mc_no_delta_func = (band->blk_size == 8) ? ff_ivi_mc_8x8_no_delta
857 : ff_ivi_mc_4x4_no_delta;
859 for (mbn = 0, mb = tile->mbs; mbn < tile->num_MBs; mb++, mbn++) {
862 if (!band->is_halfpel) {
863 mc_type = 0; /* we have only fullpel vectors */
865 mc_type = ((mv_y & 1) << 1) | (mv_x & 1);
867 mv_y >>= 1; /* convert halfpel vectors into fullpel ones */
870 for (blk = 0; blk < num_blocks; blk++) {
871 /* adjust block position in the buffer according with its number */
872 offs = mb->buf_offs + band->blk_size * ((blk & 1) + !!(blk & 2) * pitch);
873 ret = ivi_mc(band, mc_no_delta_func, 0, offs,
874 mv_x, mv_y, 0, 0, mc_type, -1);
880 /* copy data from the reference tile into the current one */
881 src = band->ref_buf + tile->ypos * pitch + tile->xpos;
882 dst = band->buf + tile->ypos * pitch + tile->xpos;
883 for (y = 0; y < tile->height; y++) {
884 memcpy(dst, src, tile->width*sizeof(band->buf[0]));
895 static uint16_t ivi_calc_band_checksum(const IVIBandDesc *band)
898 int16_t *src, checksum;
903 for (y = 0; y < band->height; src += band->pitch, y++)
904 for (x = 0; x < band->width; x++)
912 * Convert and output the current plane.
913 * This conversion is done by adding back the bias value of 128
914 * (subtracted in the encoder) and clipping the result.
916 * @param[in] plane pointer to the descriptor of the plane being processed
917 * @param[out] dst pointer to the buffer receiving converted pixels
918 * @param[in] dst_pitch pitch for moving to the next y line
920 static void ivi_output_plane(IVIPlaneDesc *plane, uint8_t *dst, ptrdiff_t dst_pitch)
923 const int16_t *src = plane->bands[0].buf;
924 ptrdiff_t pitch = plane->bands[0].pitch;
929 for (y = 0; y < plane->height; y++) {
931 int w = plane->width;
932 for (x = 0; x < w; x++) {
933 int t = src[x] + 128;
938 for (x = 0; x < w; x++)
939 dst[x] = av_clip_uint8(src[x] + 128);
946 * Decode an Indeo 4 or 5 band.
948 * @param[in,out] ctx ptr to the decoder context
949 * @param[in,out] band ptr to the band descriptor
950 * @param[in] avctx ptr to the AVCodecContext
951 * @return result code: 0 = OK, -1 = error
953 static int decode_band(IVI45DecContext *ctx,
954 IVIBandDesc *band, AVCodecContext *avctx)
956 int result, i, t, idx1, idx2, pos;
959 band->buf = band->bufs[ctx->dst_buf];
961 av_log(avctx, AV_LOG_ERROR, "Band buffer points to no data!\n");
962 return AVERROR_INVALIDDATA;
964 if (ctx->is_indeo4 && ctx->frame_type == IVI4_FRAMETYPE_BIDIR) {
965 band->ref_buf = band->bufs[ctx->b_ref_buf];
966 band->b_ref_buf = band->bufs[ctx->ref_buf];
968 band->ref_buf = band->bufs[ctx->ref_buf];
971 band->data_ptr = ctx->frame_data + (get_bits_count(&ctx->gb) >> 3);
973 result = ctx->decode_band_hdr(ctx, band, avctx);
975 av_log(avctx, AV_LOG_ERROR, "Error while decoding band header: %d\n",
980 if (band->is_empty) {
981 av_log(avctx, AV_LOG_ERROR, "Empty band encountered!\n");
982 return AVERROR_INVALIDDATA;
985 band->rv_map = &ctx->rvmap_tabs[band->rvmap_sel];
987 /* apply corrections to the selected rvmap table if present */
988 for (i = 0; i < band->num_corr; i++) {
989 idx1 = band->corr[i * 2];
990 idx2 = band->corr[i * 2 + 1];
991 FFSWAP(uint8_t, band->rv_map->runtab[idx1], band->rv_map->runtab[idx2]);
992 FFSWAP(int16_t, band->rv_map->valtab[idx1], band->rv_map->valtab[idx2]);
993 if (idx1 == band->rv_map->eob_sym || idx2 == band->rv_map->eob_sym)
994 band->rv_map->eob_sym ^= idx1 ^ idx2;
995 if (idx1 == band->rv_map->esc_sym || idx2 == band->rv_map->esc_sym)
996 band->rv_map->esc_sym ^= idx1 ^ idx2;
999 pos = get_bits_count(&ctx->gb);
1001 for (t = 0; t < band->num_tiles; t++) {
1002 tile = &band->tiles[t];
1004 if (tile->mb_size != band->mb_size) {
1005 av_log(avctx, AV_LOG_ERROR, "MB sizes mismatch: %d vs. %d\n",
1006 band->mb_size, tile->mb_size);
1007 return AVERROR_INVALIDDATA;
1009 tile->is_empty = get_bits1(&ctx->gb);
1010 if (tile->is_empty) {
1011 result = ivi_process_empty_tile(avctx, band, tile,
1012 (ctx->planes[0].bands[0].mb_size >> 3) - (band->mb_size >> 3));
1015 ff_dlog(avctx, "Empty tile encountered!\n");
1017 tile->data_size = ivi_dec_tile_data_size(&ctx->gb);
1018 if (!tile->data_size) {
1019 av_log(avctx, AV_LOG_ERROR, "Tile data size is zero!\n");
1020 result = AVERROR_INVALIDDATA;
1024 result = ctx->decode_mb_info(ctx, band, tile, avctx);
1028 result = ivi_decode_blocks(&ctx->gb, band, tile, avctx);
1030 av_log(avctx, AV_LOG_ERROR,
1031 "Corrupted tile data encountered!\n");
1035 if (((get_bits_count(&ctx->gb) - pos) >> 3) != tile->data_size) {
1036 av_log(avctx, AV_LOG_ERROR,
1037 "Tile data_size mismatch!\n");
1038 result = AVERROR_INVALIDDATA;
1042 pos += tile->data_size << 3; // skip to next tile
1046 /* restore the selected rvmap table by applying its corrections in
1048 for (i = band->num_corr-1; i >= 0; i--) {
1049 idx1 = band->corr[i*2];
1050 idx2 = band->corr[i*2+1];
1051 FFSWAP(uint8_t, band->rv_map->runtab[idx1], band->rv_map->runtab[idx2]);
1052 FFSWAP(int16_t, band->rv_map->valtab[idx1], band->rv_map->valtab[idx2]);
1053 if (idx1 == band->rv_map->eob_sym || idx2 == band->rv_map->eob_sym)
1054 band->rv_map->eob_sym ^= idx1 ^ idx2;
1055 if (idx1 == band->rv_map->esc_sym || idx2 == band->rv_map->esc_sym)
1056 band->rv_map->esc_sym ^= idx1 ^ idx2;
1060 if (band->checksum_present) {
1061 uint16_t chksum = ivi_calc_band_checksum(band);
1062 if (chksum != band->checksum) {
1063 av_log(avctx, AV_LOG_ERROR,
1064 "Band checksum mismatch! Plane %d, band %d, "
1065 "received: %"PRIx32", calculated: %"PRIx16"\n",
1066 band->plane, band->band_num, band->checksum, chksum);
1071 align_get_bits(&ctx->gb);
1076 int ff_ivi_decode_frame(AVCodecContext *avctx, void *data, int *got_frame,
1079 IVI45DecContext *ctx = avctx->priv_data;
1080 const uint8_t *buf = avpkt->data;
1081 AVFrame *frame = data;
1082 int buf_size = avpkt->size;
1085 result = init_get_bits8(&ctx->gb, buf, buf_size);
1088 ctx->frame_data = buf;
1089 ctx->frame_size = buf_size;
1091 result = ctx->decode_pic_hdr(ctx, avctx);
1093 av_log(avctx, AV_LOG_ERROR,
1094 "Error while decoding picture header: %d\n", result);
1097 if (ctx->gop_invalid)
1098 return AVERROR_INVALIDDATA;
1100 if (ctx->is_indeo4 && ctx->frame_type == IVI4_FRAMETYPE_NULL_LAST) {
1101 if (ctx->got_p_frame) {
1102 av_frame_move_ref(data, ctx->p_frame);
1104 ctx->got_p_frame = 0;
1111 if (ctx->gop_flags & IVI5_IS_PROTECTED) {
1112 avpriv_report_missing_feature(avctx, "Password-protected clip");
1113 return AVERROR_PATCHWELCOME;
1116 if (!ctx->planes[0].bands) {
1117 av_log(avctx, AV_LOG_ERROR, "Color planes not initialized yet\n");
1118 return AVERROR_INVALIDDATA;
1121 ctx->switch_buffers(ctx);
1125 if (ctx->is_nonnull_frame(ctx)) {
1126 ctx->buf_invalid[ctx->dst_buf] = 1;
1127 for (p = 0; p < 3; p++) {
1128 for (b = 0; b < ctx->planes[p].num_bands; b++) {
1129 result = decode_band(ctx, &ctx->planes[p].bands[b], avctx);
1131 av_log(avctx, AV_LOG_ERROR,
1132 "Error while decoding band: %d, plane: %d\n", b, p);
1137 ctx->buf_invalid[ctx->dst_buf] = 0;
1139 if (ctx->is_scalable)
1140 return AVERROR_INVALIDDATA;
1142 for (p = 0; p < 3; p++) {
1143 if (!ctx->planes[p].bands[0].buf)
1144 return AVERROR_INVALIDDATA;
1147 if (ctx->buf_invalid[ctx->dst_buf])
1150 //STOP_TIMER("decode_planes"); }
1152 if (!ctx->is_nonnull_frame(ctx))
1155 result = ff_set_dimensions(avctx, ctx->planes[0].width, ctx->planes[0].height);
1159 if ((result = ff_get_buffer(avctx, frame, 0)) < 0)
1162 if (ctx->is_scalable) {
1164 ff_ivi_recompose_haar(&ctx->planes[0], frame->data[0], frame->linesize[0]);
1166 ff_ivi_recompose53 (&ctx->planes[0], frame->data[0], frame->linesize[0]);
1168 ivi_output_plane(&ctx->planes[0], frame->data[0], frame->linesize[0]);
1171 ivi_output_plane(&ctx->planes[2], frame->data[1], frame->linesize[1]);
1172 ivi_output_plane(&ctx->planes[1], frame->data[2], frame->linesize[2]);
1176 /* If the bidirectional mode is enabled, next I and the following P
1177 * frame will be sent together. Unfortunately the approach below seems
1178 * to be the only way to handle the B-frames mode.
1179 * That's exactly the same Intel decoders do.
1181 if (ctx->is_indeo4 && ctx->frame_type == IVI4_FRAMETYPE_INTRA) {
1184 // skip version string
1185 while (get_bits(&ctx->gb, 8)) {
1186 if (get_bits_left(&ctx->gb) < 8)
1187 return AVERROR_INVALIDDATA;
1189 left = get_bits_count(&ctx->gb) & 0x18;
1190 skip_bits_long(&ctx->gb, 64 - left);
1191 if (get_bits_left(&ctx->gb) > 18 &&
1192 show_bits_long(&ctx->gb, 21) == 0xBFFF8) { // syncheader + inter type
1194 pkt.data = avpkt->data + (get_bits_count(&ctx->gb) >> 3);
1195 pkt.size = get_bits_left(&ctx->gb) >> 3;
1196 ff_ivi_decode_frame(avctx, ctx->p_frame, &ctx->got_p_frame, &pkt);
1200 if (ctx->show_indeo4_info) {
1201 if (ctx->is_scalable)
1202 av_log(avctx, AV_LOG_DEBUG, "This video uses scalability mode\n");
1203 if (ctx->uses_tiling)
1204 av_log(avctx, AV_LOG_DEBUG, "This video uses local decoding\n");
1205 if (ctx->has_b_frames)
1206 av_log(avctx, AV_LOG_DEBUG, "This video contains B-frames\n");
1207 if (ctx->has_transp)
1208 av_log(avctx, AV_LOG_DEBUG, "Transparency mode is enabled\n");
1210 av_log(avctx, AV_LOG_DEBUG, "This video uses Haar transform\n");
1211 if (ctx->uses_fullpel)
1212 av_log(avctx, AV_LOG_DEBUG, "This video uses fullpel motion vectors\n");
1213 ctx->show_indeo4_info = 0;
1220 * Close Indeo5 decoder and clean up its context.
1222 av_cold int ff_ivi_decode_close(AVCodecContext *avctx)
1224 IVI45DecContext *ctx = avctx->priv_data;
1226 ivi_free_buffers(&ctx->planes[0]);
1228 if (ctx->mb_vlc.cust_tab.table)
1229 ff_free_vlc(&ctx->mb_vlc.cust_tab);
1231 if (ctx->blk_vlc.cust_tab.table)
1232 ff_free_vlc(&ctx->blk_vlc.cust_tab);
1234 av_frame_free(&ctx->p_frame);
1241 * Scan patterns shared between indeo4 and indeo5
1243 const uint8_t ff_ivi_vertical_scan_8x8[64] = {
1244 0, 8, 16, 24, 32, 40, 48, 56,
1245 1, 9, 17, 25, 33, 41, 49, 57,
1246 2, 10, 18, 26, 34, 42, 50, 58,
1247 3, 11, 19, 27, 35, 43, 51, 59,
1248 4, 12, 20, 28, 36, 44, 52, 60,
1249 5, 13, 21, 29, 37, 45, 53, 61,
1250 6, 14, 22, 30, 38, 46, 54, 62,
1251 7, 15, 23, 31, 39, 47, 55, 63
1254 const uint8_t ff_ivi_horizontal_scan_8x8[64] = {
1255 0, 1, 2, 3, 4, 5, 6, 7,
1256 8, 9, 10, 11, 12, 13, 14, 15,
1257 16, 17, 18, 19, 20, 21, 22, 23,
1258 24, 25, 26, 27, 28, 29, 30, 31,
1259 32, 33, 34, 35, 36, 37, 38, 39,
1260 40, 41, 42, 43, 44, 45, 46, 47,
1261 48, 49, 50, 51, 52, 53, 54, 55,
1262 56, 57, 58, 59, 60, 61, 62, 63
1265 const uint8_t ff_ivi_direct_scan_4x4[16] = {
1266 0, 1, 4, 8, 5, 2, 3, 6, 9, 12, 13, 10, 7, 11, 14, 15
1271 * Run-value (RLE) tables.
1273 const RVMapDesc ff_ivi_rvmap_tabs[9] = {
1278 {1, 1, 0, 1, 1, 0, 1, 1, 2, 2, 1, 1, 1, 1, 3, 3,
1279 1, 1, 2, 2, 1, 1, 4, 4, 1, 1, 1, 1, 2, 2, 5, 5,
1280 1, 1, 3, 3, 1, 1, 6, 6, 1, 2, 1, 2, 7, 7, 1, 1,
1281 8, 8, 1, 1, 4, 2, 1, 4, 2, 1, 3, 3, 1, 1, 1, 9,
1282 9, 1, 2, 1, 2, 1, 5, 5, 1, 1, 10, 10, 1, 1, 3, 3,
1283 2, 2, 1, 1, 11, 11, 6, 4, 4, 1, 6, 1, 2, 1, 2, 12,
1284 8, 1, 12, 7, 8, 7, 1, 16, 1, 16, 1, 3, 3, 13, 1, 13,
1285 2, 2, 1, 15, 1, 5, 14, 15, 1, 5, 14, 1, 17, 8, 17, 8,
1286 1, 4, 4, 2, 2, 1, 25, 25, 24, 24, 1, 3, 1, 3, 1, 8,
1287 6, 7, 6, 1, 18, 8, 18, 1, 7, 23, 2, 2, 23, 1, 1, 21,
1288 22, 9, 9, 22, 19, 1, 21, 5, 19, 5, 1, 33, 20, 33, 20, 8,
1289 4, 4, 1, 32, 2, 2, 8, 3, 32, 26, 3, 1, 7, 7, 26, 6,
1290 1, 6, 1, 1, 16, 1, 10, 1, 10, 2, 16, 29, 28, 2, 29, 28,
1291 1, 27, 5, 8, 5, 27, 1, 8, 3, 7, 3, 31, 41, 31, 1, 41,
1292 6, 1, 6, 7, 4, 4, 1, 1, 2, 1, 2, 11, 34, 30, 11, 1,
1293 30, 15, 15, 34, 36, 40, 36, 40, 35, 35, 37, 37, 39, 39, 38, 38},
1296 { 1, -1, 0, 2, -2, 0, 3, -3, 1, -1, 4, -4, 5, -5, 1, -1,
1297 6, -6, 2, -2, 7, -7, 1, -1, 8, -8, 9, -9, 3, -3, 1, -1,
1298 10, -10, 2, -2, 11, -11, 1, -1, 12, 4, -12, -4, 1, -1, 13, -13,
1299 1, -1, 14, -14, 2, 5, 15, -2, -5, -15, -3, 3, 16, -16, 17, 1,
1300 -1, -17, 6, 18, -6, -18, 2, -2, 19, -19, 1, -1, 20, -20, 4, -4,
1301 7, -7, 21, -21, 1, -1, 2, 3, -3, 22, -2, -22, 8, 23, -8, 1,
1302 2, -23, -1, 2, -2, -2, 24, 1, -24, -1, 25, 5, -5, 1, -25, -1,
1303 9, -9, 26, 1, -26, 3, 1, -1, 27, -3, -1, -27, 1, 3, -1, -3,
1304 28, -4, 4, 10, -10, -28, 1, -1, 1, -1, 29, 6, -29, -6, 30, -4,
1305 3, 3, -3, -30, 1, 4, -1, 31, -3, 1, 11, -11, -1, -31, 32, -1,
1306 -1, 2, -2, 1, 1, -32, 1, 4, -1, -4, 33, -1, 1, 1, -1, 5,
1307 5, -5, -33, -1, -12, 12, -5, -7, 1, 1, 7, 34, 4, -4, -1, 4,
1308 -34, -4, 35, 36, -2, -35, -2, -36, 2, 13, 2, -1, 1, -13, 1, -1,
1309 37, 1, -5, 6, 5, -1, 38, -6, -8, 5, 8, -1, 1, 1, -37, -1,
1310 5, 39, -5, -5, 6, -6, -38, -39, -14, 40, 14, 2, 1, 1, -2, -40,
1311 -1, -2, 2, -1, -1, -1, 1, 1, 1, -1, 1, -1, 1, -1, 1, -1}
1317 {0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 8, 6, 8, 7,
1318 7, 9, 9, 10, 10, 11, 11, 1, 12, 1, 12, 13, 13, 16, 14, 16,
1319 14, 15, 15, 17, 17, 18, 0, 18, 19, 20, 21, 19, 22, 21, 20, 22,
1320 25, 24, 2, 25, 24, 23, 23, 2, 26, 28, 26, 28, 29, 27, 29, 27,
1321 33, 33, 1, 32, 1, 3, 32, 30, 36, 3, 36, 30, 31, 31, 35, 34,
1322 37, 41, 34, 35, 37, 4, 41, 4, 49, 8, 8, 49, 40, 38, 5, 38,
1323 40, 39, 5, 39, 42, 43, 42, 7, 57, 6, 43, 44, 6, 50, 7, 44,
1324 57, 48, 50, 48, 45, 45, 46, 47, 51, 46, 47, 58, 1, 51, 58, 1,
1325 52, 59, 53, 9, 52, 55, 55, 59, 53, 56, 54, 56, 54, 9, 64, 64,
1326 60, 63, 60, 63, 61, 62, 61, 62, 2, 10, 2, 10, 11, 1, 11, 13,
1327 12, 1, 12, 13, 16, 16, 8, 8, 14, 3, 3, 15, 14, 15, 4, 4,
1328 1, 17, 17, 5, 1, 7, 7, 5, 6, 1, 2, 2, 6, 22, 1, 25,
1329 21, 22, 8, 24, 1, 21, 25, 24, 8, 18, 18, 23, 9, 20, 23, 33,
1330 29, 33, 20, 1, 19, 1, 29, 36, 9, 36, 19, 41, 28, 57, 32, 3,
1331 28, 3, 1, 27, 49, 49, 1, 32, 26, 26, 2, 4, 4, 7, 57, 41,
1332 2, 7, 10, 5, 37, 16, 10, 27, 8, 8, 13, 16, 37, 13, 1, 5},
1335 {0, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, 1, -1, -1, 1,
1336 -1, 1, -1, 1, -1, 1, -1, 2, 1, -2, -1, 1, -1, 1, 1, -1,
1337 -1, 1, -1, 1, -1, 1, 0, -1, 1, 1, 1, -1, 1, -1, -1, -1,
1338 1, 1, 2, -1, -1, 1, -1, -2, 1, 1, -1, -1, 1, 1, -1, -1,
1339 1, -1, 3, 1, -3, 2, -1, 1, 1, -2, -1, -1, -1, 1, 1, 1,
1340 1, 1, -1, -1, -1, 2, -1, -2, 1, 2, -2, -1, 1, 1, 2, -1,
1341 -1, 1, -2, -1, 1, 1, -1, 2, 1, 2, -1, 1, -2, -1, -2, -1,
1342 -1, 1, 1, -1, 1, -1, 1, 1, 1, -1, -1, 1, 4, -1, -1, -4,
1343 1, 1, 1, 2, -1, -1, 1, -1, -1, 1, -1, -1, 1, -2, 1, -1,
1344 1, 1, -1, -1, 1, 1, -1, -1, 3, 2, -3, -2, 2, 5, -2, 2,
1345 2, -5, -2, -2, -2, 2, -3, 3, 2, 3, -3, 2, -2, -2, 3, -3,
1346 6, 2, -2, 3, -6, 3, -3, -3, 3, 7, -4, 4, -3, 2, -7, 2,
1347 2, -2, -4, 2, 8, -2, -2, -2, 4, 2, -2, 2, 3, 2, -2, -2,
1348 2, 2, -2, -8, -2, 9, -2, 2, -3, -2, 2, -2, 2, 2, 2, 4,
1349 -2, -4, 10, 2, 2, -2, -9, -2, 2, -2, 5, 4, -4, 4, -2, 2,
1350 -5, -4, -3, 4, 2, -3, 3, -2, -5, 5, 3, 3, -2, -3, -10, -4}
1356 {1, 1, 0, 2, 2, 1, 1, 3, 3, 4, 4, 0, 1, 1, 5, 5,
1357 2, 2, 6, 6, 7, 7, 1, 8, 1, 8, 3, 3, 9, 9, 1, 2,
1358 2, 1, 4, 10, 4, 10, 11, 11, 1, 5, 12, 12, 1, 5, 13, 13,
1359 3, 3, 6, 6, 2, 2, 14, 14, 16, 16, 15, 7, 15, 8, 8, 7,
1360 1, 1, 17, 17, 4, 4, 1, 1, 18, 18, 2, 2, 5, 5, 25, 3,
1361 9, 3, 25, 9, 19, 24, 19, 24, 1, 21, 20, 1, 21, 22, 20, 22,
1362 23, 23, 8, 6, 33, 6, 8, 33, 7, 7, 26, 26, 1, 32, 1, 32,
1363 28, 4, 28, 10, 29, 27, 27, 10, 41, 4, 29, 2, 2, 41, 36, 31,
1364 49, 31, 34, 30, 34, 36, 30, 35, 1, 49, 11, 5, 35, 11, 1, 3,
1365 3, 5, 37, 37, 8, 40, 8, 40, 12, 12, 42, 42, 1, 38, 16, 57,
1366 1, 6, 16, 39, 38, 6, 7, 7, 13, 13, 39, 43, 2, 43, 57, 2,
1367 50, 9, 44, 9, 50, 4, 15, 48, 44, 4, 1, 15, 48, 14, 14, 1,
1368 45, 45, 8, 3, 5, 8, 51, 47, 3, 46, 46, 47, 5, 51, 1, 17,
1369 17, 58, 1, 58, 2, 52, 52, 2, 53, 7, 59, 6, 6, 56, 53, 55,
1370 7, 55, 1, 54, 59, 56, 54, 10, 1, 10, 4, 60, 1, 60, 8, 4,
1371 8, 64, 64, 61, 1, 63, 3, 63, 62, 61, 5, 11, 5, 3, 11, 62},
1374 { 1, -1, 0, 1, -1, 2, -2, 1, -1, 1, -1, 0, 3, -3, 1, -1,
1375 2, -2, 1, -1, 1, -1, 4, 1, -4, -1, 2, -2, 1, -1, 5, 3,
1376 -3, -5, 2, 1, -2, -1, 1, -1, 6, 2, 1, -1, -6, -2, 1, -1,
1377 3, -3, 2, -2, 4, -4, 1, -1, 1, -1, 1, 2, -1, 2, -2, -2,
1378 7, -7, 1, -1, 3, -3, 8, -8, 1, -1, 5, -5, 3, -3, 1, 4,
1379 2, -4, -1, -2, 1, 1, -1, -1, 9, 1, 1, -9, -1, 1, -1, -1,
1380 1, -1, 3, -3, 1, 3, -3, -1, 3, -3, 1, -1, 10, 1, -10, -1,
1381 1, 4, -1, 2, 1, -1, 1, -2, 1, -4, -1, 6, -6, -1, 1, 1,
1382 1, -1, 1, 1, -1, -1, -1, 1, 11, -1, -2, 4, -1, 2, -11, 5,
1383 -5, -4, -1, 1, 4, 1, -4, -1, -2, 2, 1, -1, 12, 1, -2, 1,
1384 -12, 4, 2, 1, -1, -4, 4, -4, 2, -2, -1, 1, 7, -1, -1, -7,
1385 -1, -3, 1, 3, 1, 5, 2, 1, -1, -5, 13, -2, -1, 2, -2, -13,
1386 1, -1, 5, 6, 5, -5, 1, 1, -6, 1, -1, -1, -5, -1, 14, 2,
1387 -2, 1, -14, -1, 8, 1, -1, -8, 1, 5, 1, 5, -5, 1, -1, 1,
1388 -5, -1, 15, 1, -1, -1, -1, 3, -15, -3, 6, 1, 16, -1, 6, -6,
1389 -6, 1, -1, 1, -16, 1, 7, -1, 1, -1, -6, -3, 6, -7, 3, -1}
1395 {0, 1, 1, 2, 2, 3, 3, 4, 4, 1, 1, 5, 5, 6, 6, 7,
1396 7, 8, 8, 9, 9, 2, 2, 10, 10, 1, 1, 11, 11, 12, 12, 3,
1397 3, 13, 13, 0, 14, 14, 16, 15, 16, 15, 4, 4, 17, 1, 17, 1,
1398 5, 5, 18, 18, 2, 2, 6, 6, 8, 19, 7, 8, 7, 19, 20, 20,
1399 21, 21, 22, 24, 22, 24, 23, 23, 1, 1, 25, 25, 3, 3, 26, 26,
1400 9, 9, 27, 27, 28, 28, 33, 29, 4, 33, 29, 1, 4, 1, 32, 32,
1401 2, 2, 31, 10, 30, 10, 30, 31, 34, 34, 5, 5, 36, 36, 35, 41,
1402 35, 11, 41, 11, 37, 1, 8, 8, 37, 6, 1, 6, 40, 7, 7, 40,
1403 12, 38, 12, 39, 39, 38, 49, 13, 49, 13, 3, 42, 3, 42, 16, 16,
1404 43, 43, 14, 14, 1, 1, 44, 15, 44, 15, 2, 2, 57, 48, 50, 48,
1405 57, 50, 4, 45, 45, 4, 46, 47, 47, 46, 1, 51, 1, 17, 17, 51,
1406 8, 9, 9, 5, 58, 8, 58, 5, 52, 52, 55, 56, 53, 56, 55, 59,
1407 59, 53, 54, 1, 6, 54, 7, 7, 6, 1, 2, 3, 2, 3, 64, 60,
1408 60, 10, 10, 64, 61, 62, 61, 63, 1, 63, 62, 1, 18, 24, 18, 4,
1409 25, 4, 8, 21, 21, 1, 24, 22, 25, 22, 8, 11, 19, 11, 23, 1,
1410 20, 23, 19, 20, 5, 12, 5, 1, 16, 2, 12, 13, 2, 13, 1, 16},
1413 { 0, 1, -1, 1, -1, 1, -1, 1, -1, 2, -2, 1, -1, 1, -1, 1,
1414 -1, 1, -1, 1, -1, 2, -2, 1, -1, 3, -3, 1, -1, 1, -1, 2,
1415 -2, 1, -1, 0, 1, -1, 1, 1, -1, -1, 2, -2, 1, 4, -1, -4,
1416 2, -2, 1, -1, -3, 3, 2, -2, 2, 1, 2, -2, -2, -1, 1, -1,
1417 1, -1, 1, 1, -1, -1, 1, -1, 5, -5, 1, -1, 3, -3, 1, -1,
1418 2, -2, 1, -1, 1, -1, 1, 1, 3, -1, -1, 6, -3, -6, -1, 1,
1419 4, -4, 1, 2, 1, -2, -1, -1, 1, -1, 3, -3, 1, -1, 1, 1,
1420 -1, 2, -1, -2, 1, 7, -3, 3, -1, 3, -7, -3, 1, -3, 3, -1,
1421 2, 1, -2, 1, -1, -1, 1, 2, -1, -2, -4, -1, 4, 1, 2, -2,
1422 1, -1, -2, 2, 8, -8, -1, 2, 1, -2, -5, 5, 1, -1, -1, 1,
1423 -1, 1, 4, -1, 1, -4, -1, -1, 1, 1, 9, 1, -9, 2, -2, -1,
1424 -4, 3, -3, -4, -1, 4, 1, 4, 1, -1, 1, -1, 1, 1, -1, 1,
1425 -1, -1, -1, 10, 4, 1, 4, -4, -4, -10, 6, 5, -6, -5, 1, -1,
1426 1, 3, -3, -1, 1, -1, -1, -1, 11, 1, 1, -11, -2, -2, 2, 5,
1427 -2, -5, -5, 2, -2, 12, 2, -2, 2, 2, 5, -3, -2, 3, -2, -12,
1428 -2, 2, 2, 2, -5, 3, 5, 13, -3, 7, -3, -3, -7, 3, -13, 3}
1434 {0, 1, 1, 1, 2, 2, 1, 3, 3, 1, 1, 1, 4, 4, 1, 5,
1435 2, 1, 5, 2, 1, 1, 6, 6, 1, 1, 1, 1, 1, 7, 3, 1,
1436 2, 3, 0, 1, 2, 7, 1, 1, 1, 8, 1, 1, 8, 1, 1, 1,
1437 9, 1, 9, 1, 2, 1, 1, 2, 1, 1, 10, 4, 1, 10, 1, 4,
1438 1, 1, 1, 1, 1, 3, 1, 1, 1, 3, 2, 1, 5, 1, 1, 1,
1439 2, 5, 1, 11, 1, 11, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1440 2, 1, 6, 1, 6, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 12,
1441 3, 1, 12, 1, 1, 1, 2, 1, 1, 3, 1, 1, 1, 1, 1, 1,
1442 4, 1, 1, 1, 2, 1, 1, 4, 1, 1, 1, 1, 1, 1, 2, 1,
1443 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 2, 1, 1, 5,
1444 1, 1, 1, 1, 1, 7, 1, 7, 1, 1, 2, 3, 1, 1, 1, 1,
1445 5, 1, 1, 1, 1, 1, 1, 2, 13, 1, 1, 1, 1, 1, 1, 1,
1446 1, 1, 1, 1, 1, 1, 1, 1, 13, 2, 1, 1, 4, 1, 1, 1,
1447 3, 1, 6, 1, 1, 1, 14, 1, 1, 1, 1, 1, 14, 6, 1, 1,
1448 1, 1, 15, 2, 4, 1, 2, 3, 15, 1, 1, 1, 8, 1, 1, 8,
1449 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1},
1452 { 0, 1, -1, 2, 1, -1, -2, 1, -1, 3, -3, 4, 1, -1, -4, 1,
1453 2, 5, -1, -2, -5, 6, 1, -1, -6, 7, -7, 8, -8, 1, 2, 9,
1454 3, -2, 0, -9, -3, -1, 10, -10, 11, 1, -11, 12, -1, -12, 13, -13,
1455 1, 14, -1, -14, 4, 15, -15, -4, 16, -16, 1, 2, 17, -1, -17, -2,
1456 18, -18, 19, -19, 20, 3, -20, 21, -21, -3, 5, 22, 2, -22, -23, 23,
1457 -5, -2, 24, 1, -24, -1, 25, -25, 26, -26, -27, 27, 28, 29, -28, -29,
1458 6, 30, 2, -31, -2, -30, 31, -6, -32, 32, 33, -33, 34, -35, -34, 1,
1459 4, -36, -1, 35, 37, 36, 7, -37, 38, -4, -38, 39, 41, 40, -40, -39,
1460 3, 42, -43, -41, -7, -42, 43, -3, 44, -44, 45, -45, 46, 47, 8, -47,
1461 -48, -46, 50, -50, 48, 49, 51, -49, 52, -52, 5, -51, -8, -53, 53, 3,
1462 -56, 56, 55, 54, -54, 2, 60, -2, -55, 58, 9, -5, 59, 57, -57, -63,
1463 -3, -58, -60, -61, 61, -59, -62, -9, 1, 64, 62, 69, -64, 63, 65, -67,
1464 -68, 66, -65, 68, -66, -69, 67, -70, -1, 10, 71, -71, 4, 73, 72, 70,
1465 6, -76, -3, 74, -78, -74, 1, 78, 80, -72, -75, 76, -1, 3, -73, 79,
1466 75, 77, 1, 11, -4, -79, -10, -6, -1, -77, -83, -80, 2, 81, -84, -2,
1467 83, -81, 82, -82, 84, -87, -86, 85, -11, -85, 86, -89, 87, -88, 88, 89}
1473 {1, 1, 0, 2, 1, 2, 1, 3, 3, 1, 1, 4, 4, 2, 2, 1,
1474 1, 5, 5, 6, 1, 6, 1, 7, 7, 3, 3, 2, 8, 2, 8, 1,
1475 1, 0, 9, 9, 1, 1, 10, 4, 10, 4, 11, 11, 2, 1, 2, 1,
1476 12, 12, 3, 3, 1, 1, 13, 5, 5, 13, 14, 1, 1, 14, 2, 2,
1477 6, 6, 15, 1, 1, 15, 16, 4, 7, 16, 4, 7, 1, 1, 3, 3,
1478 8, 8, 2, 2, 1, 1, 17, 17, 1, 1, 18, 18, 5, 5, 2, 2,
1479 1, 1, 9, 19, 9, 19, 20, 3, 3, 20, 1, 10, 21, 1, 10, 4,
1480 4, 21, 22, 6, 6, 22, 1, 1, 23, 24, 2, 2, 23, 24, 11, 1,
1481 1, 11, 7, 25, 7, 1, 1, 25, 8, 8, 3, 26, 3, 1, 12, 2,
1482 2, 26, 1, 12, 5, 5, 27, 4, 1, 4, 1, 27, 28, 1, 28, 13,
1483 1, 13, 2, 29, 2, 1, 32, 6, 1, 30, 14, 29, 14, 6, 3, 31,
1484 3, 1, 30, 1, 32, 31, 33, 9, 33, 1, 1, 7, 9, 7, 2, 2,
1485 1, 1, 4, 36, 34, 4, 5, 10, 10, 5, 34, 1, 1, 35, 8, 8,
1486 36, 3, 35, 1, 15, 3, 2, 1, 16, 15, 16, 2, 37, 1, 37, 1,
1487 1, 1, 6, 6, 38, 1, 38, 11, 1, 39, 39, 40, 11, 2, 41, 4,
1488 40, 1, 2, 4, 1, 1, 1, 41, 3, 1, 3, 1, 5, 7, 5, 7},
1491 { 1, -1, 0, 1, 2, -1, -2, 1, -1, 3, -3, 1, -1, 2, -2, 4,
1492 -4, 1, -1, 1, 5, -1, -5, 1, -1, 2, -2, 3, 1, -3, -1, 6,
1493 -6, 0, 1, -1, 7, -7, 1, 2, -1, -2, 1, -1, 4, 8, -4, -8,
1494 1, -1, 3, -3, 9, -9, 1, 2, -2, -1, 1, 10, -10, -1, 5, -5,
1495 2, -2, 1, 11, -11, -1, 1, 3, 2, -1, -3, -2, 12, -12, 4, -4,
1496 2, -2, -6, 6, 13, -13, 1, -1, 14, -14, 1, -1, 3, -3, 7, -7,
1497 15, -15, 2, 1, -2, -1, 1, 5, -5, -1, -16, 2, 1, 16, -2, 4,
1498 -4, -1, 1, 3, -3, -1, 17, -17, 1, 1, -8, 8, -1, -1, 2, 18,
1499 -18, -2, 3, 1, -3, 19, -19, -1, 3, -3, 6, 1, -6, 20, 2, 9,
1500 -9, -1, -20, -2, 4, -4, 1, -5, 21, 5, -21, -1, 1, -22, -1, 2,
1501 22, -2, 10, 1, -10, 23, 1, 4, -23, 1, 2, -1, -2, -4, -7, 1,
1502 7, -24, -1, 24, -1, -1, 1, 3, -1, -25, 25, 4, -3, -4, 11, -11,
1503 26, -26, 6, 1, 1, -6, -5, -3, 3, 5, -1, -27, 27, 1, 4, -4,
1504 -1, -8, -1, 28, 2, 8, -12, -28, -2, -2, 2, 12, -1, 29, 1, -29,
1505 30, -30, 5, -5, 1, -31, -1, 3, 31, -1, 1, 1, -3, -13, 1, -7,
1506 -1, -32, 13, 7, 32, 33, -33, -1, -9, -34, 9, 34, -6, 5, 6, -5}
1512 {1, 1, 0, 1, 1, 2, 2, 1, 1, 3, 3, 1, 1, 0, 2, 2,
1513 4, 1, 4, 1, 1, 1, 5, 5, 1, 1, 6, 6, 2, 2, 1, 1,
1514 3, 3, 7, 7, 1, 1, 8, 8, 1, 1, 2, 2, 1, 9, 1, 9,
1515 4, 4, 10, 1, 1, 10, 1, 1, 11, 11, 3, 3, 1, 2, 1, 2,
1516 1, 1, 12, 12, 5, 5, 1, 1, 13, 1, 1, 13, 2, 2, 1, 1,
1517 6, 6, 1, 1, 4, 14, 4, 14, 3, 1, 3, 1, 1, 1, 15, 7,
1518 15, 2, 2, 7, 1, 1, 1, 8, 1, 8, 16, 16, 1, 1, 1, 1,
1519 2, 1, 1, 2, 1, 1, 3, 5, 5, 3, 4, 1, 1, 4, 1, 1,
1520 17, 17, 9, 1, 1, 9, 2, 2, 1, 1, 10, 10, 1, 6, 1, 1,
1521 6, 18, 1, 1, 18, 1, 1, 1, 2, 2, 3, 1, 3, 1, 1, 1,
1522 4, 1, 19, 1, 19, 7, 1, 1, 20, 1, 4, 20, 1, 7, 11, 2,
1523 1, 11, 21, 2, 8, 5, 1, 8, 1, 5, 21, 1, 1, 1, 22, 1,
1524 1, 22, 1, 1, 3, 3, 1, 23, 2, 12, 24, 1, 1, 2, 1, 1,
1525 12, 23, 1, 1, 24, 1, 1, 1, 4, 1, 1, 1, 2, 1, 6, 6,
1526 4, 2, 1, 1, 1, 1, 1, 1, 1, 14, 13, 3, 1, 25, 9, 25,
1527 14, 1, 9, 3, 13, 1, 1, 1, 1, 1, 10, 1, 1, 2, 10, 2},
1530 {-20, -1, 0, 2, -2, 1, -1, 3, -3, 1, -1, 4, -4, 0, 2, -2,
1531 1, 5, -1, -5, 6, -6, 1, -1, 7, -7, 1, -1, 3, -3, 8, -8,
1532 2, -2, 1, -1, 9, -9, 1, -1, 10, -10, 4, -4, 11, 1, -11, -1,
1533 2, -2, 1, 12, -12, -1, 13, -13, 1, -1, 3, -3, 14, 5, -14, -5,
1534 -15, 15, -1, 1, 2, -2, 16, -16, 1, 17, -17, -1, 6, -6, 18, -18,
1535 2, -2, -19, 19, -3, 1, 3, -1, 4, 20, -4, 1, -21, 21, 1, 2,
1536 -1, -7, 7, -2, 22, -22, 23, 2, -23, -2, 1, -1, -24, 24, -25, 25,
1537 -8, -26, 26, 8, -27, 27, 5, 3, -3, -5, -4, 28, -28, 4, 29, -29,
1538 1, -1, -2, -30, 30, 2, 9, -9, -31, 31, 2, -2, -32, 3, 32, -33,
1539 -3, 1, 33, -34, -1, 34, -35, 35, -10, 10, -6, 36, 6, -36, 37, -37,
1540 -5, 38, 1, -38, -1, 3, 39, -39, -1, 40, 5, 1, -40, -3, 2, -11,
1541 -41, -2, 1, 11, -3, -4, 41, 3, 42, 4, -1, -43, -42, 43, 1, -44,
1542 45, -1, 44, -45, -7, 7, -46, 1, -12, 2, 1, -47, 46, 12, 47, 48,
1543 -2, -1, -48, 49, -1, -50, -49, 50, -6, -51, 51, 52, -13, 53, -4, 4,
1544 6, 13, -53, -52, -54, 55, 54, -55, -56, -2, 2, -8, 56, 1, -3, -1,
1545 2, 58, 3, 8, -2, 57, -58, -60, -59, -57, -3, 60, 59, -14, 3, 14}
1551 {1, 1, 0, 2, 2, 1, 1, 3, 3, 4, 4, 5, 5, 1, 1, 6,
1552 6, 2, 2, 7, 7, 8, 8, 1, 1, 3, 3, 9, 9, 10, 10, 1,
1553 1, 2, 2, 4, 4, 11, 0, 11, 12, 12, 13, 13, 1, 1, 5, 5,
1554 14, 14, 15, 16, 15, 16, 3, 3, 1, 6, 1, 6, 2, 2, 7, 7,
1555 8, 8, 17, 17, 1, 1, 4, 4, 18, 18, 2, 2, 1, 19, 1, 20,
1556 19, 20, 21, 21, 3, 3, 22, 22, 5, 5, 24, 1, 1, 23, 9, 23,
1557 24, 9, 2, 2, 10, 1, 1, 10, 6, 6, 25, 4, 4, 25, 7, 7,
1558 26, 8, 1, 8, 3, 1, 26, 3, 11, 11, 27, 27, 2, 28, 1, 2,
1559 28, 1, 12, 12, 5, 5, 29, 13, 13, 29, 32, 1, 1, 33, 31, 30,
1560 32, 4, 30, 33, 4, 31, 3, 14, 1, 1, 3, 34, 34, 2, 2, 14,
1561 6, 6, 35, 36, 35, 36, 1, 15, 1, 16, 16, 15, 7, 9, 7, 9,
1562 37, 8, 8, 37, 1, 1, 39, 2, 38, 39, 2, 40, 5, 38, 40, 5,
1563 3, 3, 4, 4, 10, 10, 1, 1, 1, 1, 41, 2, 41, 2, 6, 6,
1564 1, 1, 11, 42, 11, 43, 3, 42, 3, 17, 4, 43, 1, 17, 7, 1,
1565 8, 44, 4, 7, 44, 5, 8, 2, 5, 1, 2, 48, 45, 1, 12, 45,
1566 12, 48, 13, 13, 1, 9, 9, 46, 1, 46, 47, 47, 49, 18, 18, 49},
1569 { 1, -1, 0, 1, -1, 2, -2, 1, -1, 1, -1, 1, -1, 3, -3, 1,
1570 -1, -2, 2, 1, -1, 1, -1, 4, -4, -2, 2, 1, -1, 1, -1, 5,
1571 -5, -3, 3, 2, -2, 1, 0, -1, 1, -1, 1, -1, 6, -6, 2, -2,
1572 1, -1, 1, 1, -1, -1, -3, 3, 7, 2, -7, -2, -4, 4, 2, -2,
1573 2, -2, 1, -1, 8, -8, 3, -3, 1, -1, -5, 5, 9, 1, -9, 1,
1574 -1, -1, 1, -1, -4, 4, 1, -1, 3, -3, 1, -10, 10, 1, 2, -1,
1575 -1, -2, 6, -6, 2, 11, -11, -2, 3, -3, 1, -4, 4, -1, 3, -3,
1576 1, 3, 12, -3, -5, -12, -1, 5, 2, -2, 1, -1, -7, 1, 13, 7,
1577 -1, -13, 2, -2, 4, -4, 1, 2, -2, -1, 1, 14, -14, 1, 1, 1,
1578 -1, -5, -1, -1, 5, -1, -6, 2, -15, 15, 6, 1, -1, -8, 8, -2,
1579 -4, 4, 1, 1, -1, -1, 16, 2, -16, -2, 2, -2, 4, 3, -4, -3,
1580 -1, -4, 4, 1, -17, 17, -1, -9, 1, 1, 9, 1, -5, -1, -1, 5,
1581 -7, 7, 6, -6, 3, -3, 18, -18, 19, -19, 1, -10, -1, 10, -5, 5,
1582 20, -20, -3, 1, 3, 1, 8, -1, -8, 2, 7, -1, -21, -2, 5, 21,
1583 5, -1, -7, -5, 1, -6, -5, -11, 6, 22, 11, 1, 1, -22, -3, -1,
1584 3, -1, 3, -3, -23, 4, -4, 1, 23, -1, 1, -1, 1, -2, 2, -1}
1590 {1, 1, 1, 1, 0, 2, 2, 1, 1, 3, 3, 0, 1, 1, 2, 2,
1591 4, 4, 1, 1, 5, 5, 1, 1, 2, 2, 3, 3, 6, 6, 1, 1,
1592 7, 7, 8, 1, 8, 2, 2, 1, 4, 4, 1, 3, 1, 3, 9, 9,
1593 2, 2, 1, 5, 1, 5, 10, 10, 1, 1, 11, 11, 3, 6, 3, 4,
1594 4, 6, 2, 2, 1, 12, 1, 12, 7, 13, 7, 13, 1, 1, 8, 8,
1595 2, 2, 14, 14, 16, 15, 16, 5, 5, 1, 3, 15, 1, 3, 4, 4,
1596 1, 1, 17, 17, 2, 2, 6, 6, 1, 18, 1, 18, 22, 21, 22, 21,
1597 25, 24, 25, 19, 9, 20, 9, 23, 19, 24, 20, 3, 23, 7, 3, 1,
1598 1, 7, 28, 26, 29, 5, 28, 26, 5, 8, 29, 4, 8, 27, 2, 2,
1599 4, 27, 1, 1, 10, 36, 10, 33, 33, 36, 30, 1, 32, 32, 1, 30,
1600 6, 31, 31, 35, 3, 6, 11, 11, 3, 2, 35, 2, 34, 1, 34, 1,
1601 37, 37, 12, 7, 12, 5, 41, 5, 4, 7, 1, 8, 13, 4, 1, 41,
1602 13, 38, 8, 38, 9, 1, 40, 40, 9, 1, 39, 2, 2, 49, 39, 42,
1603 3, 3, 14, 16, 49, 14, 16, 42, 43, 43, 6, 6, 15, 1, 1, 15,
1604 44, 44, 1, 1, 50, 48, 4, 5, 4, 7, 5, 2, 10, 10, 48, 7,
1605 50, 45, 2, 1, 45, 8, 8, 1, 46, 46, 3, 47, 47, 3, 1, 1},
1608 { 1, -1, 2, -2, 0, 1, -1, 3, -3, 1, -1, 0, 4, -4, 2, -2,
1609 1, -1, 5, -5, 1, -1, 6, -6, 3, -3, 2, -2, 1, -1, 7, -7,
1610 1, -1, 1, 8, -1, 4, -4, -8, 2, -2, 9, 3, -9, -3, 1, -1,
1611 5, -5, 10, 2, -10, -2, 1, -1, 11, -11, 1, -1, -4, 2, 4, 3,
1612 -3, -2, 6, -6, 12, 1, -12, -1, 2, 1, -2, -1, 13, -13, 2, -2,
1613 7, -7, 1, -1, 1, 1, -1, 3, -3, 14, 5, -1, -14, -5, 4, -4,
1614 15, -15, 1, -1, 8, -8, -3, 3, 16, 1, -16, -1, 1, 1, -1, -1,
1615 1, 1, -1, 1, 2, 1, -2, 1, -1, -1, -1, 6, -1, 3, -6, 17,
1616 -17, -3, 1, 1, 1, 4, -1, -1, -4, 3, -1, 5, -3, -1, -9, 9,
1617 -5, 1, 18, -18, 2, 1, -2, 1, -1, -1, 1, 19, -1, 1, -19, -1,
1618 4, 1, -1, 1, 7, -4, -2, 2, -7, 10, -1, -10, 1, 20, -1, -20,
1619 1, -1, 2, 4, -2, 5, 1, -5, 6, -4, 21, 4, 2, -6, -21, -1,
1620 -2, 1, -4, -1, -3, 22, -1, 1, 3, -22, -1, 11, -11, 1, 1, 1,
1621 8, -8, 2, 2, -1, -2, -2, -1, 1, -1, -5, 5, 2, 23, -23, -2,
1622 1, -1, 24, -24, -1, -1, 7, 6, -7, 5, -6, 12, -3, 3, 1, -5,
1623 1, 1, -12, 25, -1, -5, 5, -25, -1, 1, 9, 1, -1, -9, 26, -26}