2 * common functions for Indeo Video Interactive codecs (Indeo4 and Indeo5)
4 * Copyright (c) 2009 Maxim Poliakovski
6 * This file is part of FFmpeg.
8 * FFmpeg is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU Lesser General Public
10 * License as published by the Free Software Foundation; either
11 * version 2.1 of the License, or (at your option) any later version.
13 * FFmpeg is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * Lesser General Public License for more details.
18 * You should have received a copy of the GNU Lesser General Public
19 * License along with FFmpeg; if not, write to the Free Software
20 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
25 * This file contains functions and data shared by both Indeo4 and
31 #define BITSTREAM_READER_LE
32 #include "libavutil/attributes.h"
33 #include "libavutil/imgutils.h"
34 #include "libavutil/timer.h"
43 * These are 2x8 predefined Huffman codebooks for coding macroblock/block
44 * signals. They are specified using "huffman descriptors" in order to
45 * avoid huge static tables. The decoding tables will be generated at
46 * startup from these descriptors.
48 /** static macroblock huffman tables */
49 static const IVIHuffDesc ivi_mb_huff_desc[8] = {
50 {8, {0, 4, 5, 4, 4, 4, 6, 6}},
51 {12, {0, 2, 2, 3, 3, 3, 3, 5, 3, 2, 2, 2}},
52 {12, {0, 2, 3, 4, 3, 3, 3, 3, 4, 3, 2, 2}},
53 {12, {0, 3, 4, 4, 3, 3, 3, 3, 3, 2, 2, 2}},
54 {13, {0, 4, 4, 3, 3, 3, 3, 2, 3, 3, 2, 1, 1}},
55 {9, {0, 4, 4, 4, 4, 3, 3, 3, 2}},
56 {10, {0, 4, 4, 4, 4, 3, 3, 2, 2, 2}},
57 {12, {0, 4, 4, 4, 3, 3, 2, 3, 2, 2, 2, 2}}
60 /** static block huffman tables */
61 static const IVIHuffDesc ivi_blk_huff_desc[8] = {
62 {10, {1, 2, 3, 4, 4, 7, 5, 5, 4, 1}},
63 {11, {2, 3, 4, 4, 4, 7, 5, 4, 3, 3, 2}},
64 {12, {2, 4, 5, 5, 5, 5, 6, 4, 4, 3, 1, 1}},
65 {13, {3, 3, 4, 4, 5, 6, 6, 4, 4, 3, 2, 1, 1}},
66 {11, {3, 4, 4, 5, 5, 5, 6, 5, 4, 2, 2}},
67 {13, {3, 4, 5, 5, 5, 5, 6, 4, 3, 3, 2, 1, 1}},
68 {13, {3, 4, 5, 5, 5, 6, 5, 4, 3, 3, 2, 1, 1}},
69 {9, {3, 4, 4, 5, 5, 5, 6, 5, 5}}
72 static VLC ivi_mb_vlc_tabs [8]; ///< static macroblock Huffman tables
73 static VLC ivi_blk_vlc_tabs[8]; ///< static block Huffman tables
75 typedef void (*ivi_mc_func) (int16_t *buf, const int16_t *ref_buf,
76 uint32_t pitch, int mc_type);
77 typedef void (*ivi_mc_avg_func) (int16_t *buf, const int16_t *ref_buf1,
78 const int16_t *ref_buf2,
79 uint32_t pitch, int mc_type, int mc_type2);
81 static int ivi_mc(IVIBandDesc *band, ivi_mc_func mc, ivi_mc_avg_func mc_avg,
82 int offs, int mv_x, int mv_y, int mv_x2, int mv_y2,
83 int mc_type, int mc_type2)
85 int ref_offs = offs + mv_y * band->pitch + mv_x;
86 int buf_size = band->pitch * band->aheight;
87 int min_size = band->pitch * (band->blk_size - 1) + band->blk_size;
88 int ref_size = (mc_type > 1) * band->pitch + (mc_type & 1);
91 av_assert0(offs >= 0 && ref_offs >= 0 && band->ref_buf);
92 av_assert0(buf_size - min_size >= offs);
93 av_assert0(buf_size - min_size - ref_size >= ref_offs);
97 mc(band->buf + offs, band->ref_buf + ref_offs, band->pitch, mc_type);
99 int ref_offs2 = offs + mv_y2 * band->pitch + mv_x2;
100 int ref_size2 = (mc_type2 > 1) * band->pitch + (mc_type2 & 1);
101 if (offs < 0 || ref_offs2 < 0 || !band->b_ref_buf)
102 return AVERROR_INVALIDDATA;
103 if (buf_size - min_size - ref_size2 < ref_offs2)
104 return AVERROR_INVALIDDATA;
107 mc(band->buf + offs, band->b_ref_buf + ref_offs2,
108 band->pitch, mc_type2);
110 mc_avg(band->buf + offs, band->ref_buf + ref_offs,
111 band->b_ref_buf + ref_offs2, band->pitch,
119 * Reverse "nbits" bits of the value "val" and return the result
120 * in the least significant bits.
122 static uint16_t inv_bits(uint16_t val, int nbits)
127 res = ff_reverse[val] >> (8 - nbits);
129 res = ((ff_reverse[val & 0xFF] << 8) +
130 (ff_reverse[val >> 8])) >> (16 - nbits);
136 * Generate a huffman codebook from the given descriptor
137 * and convert it into the FFmpeg VLC table.
139 * @param[in] cb pointer to codebook descriptor
140 * @param[out] vlc where to place the generated VLC table
141 * @param[in] flag flag: 1 - for static or 0 for dynamic tables
142 * @return result code: 0 - OK, -1 = error (invalid codebook descriptor)
144 static int ivi_create_huff_from_desc(const IVIHuffDesc *cb, VLC *vlc, int flag)
146 int pos, i, j, codes_per_row, prefix, not_last_row;
147 uint16_t codewords[256]; /* FIXME: move this temporal storage out? */
150 pos = 0; /* current position = 0 */
152 for (i = 0; i < cb->num_rows; i++) {
153 codes_per_row = 1 << cb->xbits[i];
154 not_last_row = (i != cb->num_rows - 1);
155 prefix = ((1 << i) - 1) << (cb->xbits[i] + not_last_row);
157 for (j = 0; j < codes_per_row; j++) {
158 if (pos >= 256) /* Some Indeo5 codebooks can have more than 256 */
159 break; /* elements, but only 256 codes are allowed! */
161 bits[pos] = i + cb->xbits[i] + not_last_row;
162 if (bits[pos] > IVI_VLC_BITS)
163 return AVERROR_INVALIDDATA; /* invalid descriptor */
165 codewords[pos] = inv_bits((prefix | j), bits[pos]);
173 /* number of codewords = pos */
174 return init_vlc(vlc, IVI_VLC_BITS, pos, bits, 1, 1, codewords, 2, 2,
175 (flag ? INIT_VLC_USE_NEW_STATIC : 0) | INIT_VLC_LE);
178 av_cold void ff_ivi_init_static_vlc(void)
181 static VLC_TYPE table_data[8192 * 16][2];
182 static int initialized_vlcs = 0;
184 if (initialized_vlcs)
186 for (i = 0; i < 8; i++) {
187 ivi_mb_vlc_tabs[i].table = table_data + i * 2 * 8192;
188 ivi_mb_vlc_tabs[i].table_allocated = 8192;
189 ivi_create_huff_from_desc(&ivi_mb_huff_desc[i],
190 &ivi_mb_vlc_tabs[i], 1);
191 ivi_blk_vlc_tabs[i].table = table_data + (i * 2 + 1) * 8192;
192 ivi_blk_vlc_tabs[i].table_allocated = 8192;
193 ivi_create_huff_from_desc(&ivi_blk_huff_desc[i],
194 &ivi_blk_vlc_tabs[i], 1);
196 initialized_vlcs = 1;
200 * Copy huffman codebook descriptors.
202 * @param[out] dst ptr to the destination descriptor
203 * @param[in] src ptr to the source descriptor
205 static void ivi_huff_desc_copy(IVIHuffDesc *dst, const IVIHuffDesc *src)
207 dst->num_rows = src->num_rows;
208 memcpy(dst->xbits, src->xbits, src->num_rows);
212 * Compare two huffman codebook descriptors.
214 * @param[in] desc1 ptr to the 1st descriptor to compare
215 * @param[in] desc2 ptr to the 2nd descriptor to compare
216 * @return comparison result: 0 - equal, 1 - not equal
218 static int ivi_huff_desc_cmp(const IVIHuffDesc *desc1,
219 const IVIHuffDesc *desc2)
221 return desc1->num_rows != desc2->num_rows ||
222 memcmp(desc1->xbits, desc2->xbits, desc1->num_rows);
225 int ff_ivi_dec_huff_desc(GetBitContext *gb, int desc_coded, int which_tab,
226 IVIHuffTab *huff_tab, AVCodecContext *avctx)
229 IVIHuffDesc new_huff;
232 /* select default table */
233 huff_tab->tab = (which_tab) ? &ivi_blk_vlc_tabs[7]
234 : &ivi_mb_vlc_tabs [7];
238 huff_tab->tab_sel = get_bits(gb, 3);
239 if (huff_tab->tab_sel == 7) {
240 /* custom huffman table (explicitly encoded) */
241 new_huff.num_rows = get_bits(gb, 4);
242 if (!new_huff.num_rows) {
243 av_log(avctx, AV_LOG_ERROR, "Empty custom Huffman table!\n");
244 return AVERROR_INVALIDDATA;
247 for (i = 0; i < new_huff.num_rows; i++)
248 new_huff.xbits[i] = get_bits(gb, 4);
250 /* Have we got the same custom table? Rebuild if not. */
251 if (ivi_huff_desc_cmp(&new_huff, &huff_tab->cust_desc) || !huff_tab->cust_tab.table) {
252 ivi_huff_desc_copy(&huff_tab->cust_desc, &new_huff);
254 if (huff_tab->cust_tab.table)
255 ff_free_vlc(&huff_tab->cust_tab);
256 result = ivi_create_huff_from_desc(&huff_tab->cust_desc,
257 &huff_tab->cust_tab, 0);
259 // reset faulty description
260 huff_tab->cust_desc.num_rows = 0;
261 av_log(avctx, AV_LOG_ERROR,
262 "Error while initializing custom vlc table!\n");
266 huff_tab->tab = &huff_tab->cust_tab;
268 /* select one of predefined tables */
269 huff_tab->tab = (which_tab) ? &ivi_blk_vlc_tabs[huff_tab->tab_sel]
270 : &ivi_mb_vlc_tabs [huff_tab->tab_sel];
277 * Free planes, bands and macroblocks buffers.
279 * @param[in] planes pointer to the array of the plane descriptors
281 static av_cold void ivi_free_buffers(IVIPlaneDesc *planes)
285 for (p = 0; p < 3; p++) {
287 for (b = 0; b < planes[p].num_bands; b++) {
288 av_freep(&planes[p].bands[b].bufs[0]);
289 av_freep(&planes[p].bands[b].bufs[1]);
290 av_freep(&planes[p].bands[b].bufs[2]);
291 av_freep(&planes[p].bands[b].bufs[3]);
293 if (planes[p].bands[b].blk_vlc.cust_tab.table)
294 ff_free_vlc(&planes[p].bands[b].blk_vlc.cust_tab);
295 for (t = 0; t < planes[p].bands[b].num_tiles; t++)
296 av_freep(&planes[p].bands[b].tiles[t].mbs);
297 av_freep(&planes[p].bands[b].tiles);
299 av_freep(&planes[p].bands);
300 planes[p].num_bands = 0;
304 av_cold int ff_ivi_init_planes(IVIPlaneDesc *planes, const IVIPicConfig *cfg,
308 uint32_t b_width, b_height, align_fac, width_aligned,
309 height_aligned, buf_size;
312 ivi_free_buffers(planes);
314 if (av_image_check_size(cfg->pic_width, cfg->pic_height, 0, NULL) < 0 ||
315 cfg->luma_bands < 1 || cfg->chroma_bands < 1)
316 return AVERROR_INVALIDDATA;
318 /* fill in the descriptor of the luminance plane */
319 planes[0].width = cfg->pic_width;
320 planes[0].height = cfg->pic_height;
321 planes[0].num_bands = cfg->luma_bands;
323 /* fill in the descriptors of the chrominance planes */
324 planes[1].width = planes[2].width = (cfg->pic_width + 3) >> 2;
325 planes[1].height = planes[2].height = (cfg->pic_height + 3) >> 2;
326 planes[1].num_bands = planes[2].num_bands = cfg->chroma_bands;
328 for (p = 0; p < 3; p++) {
329 planes[p].bands = av_mallocz_array(planes[p].num_bands, sizeof(IVIBandDesc));
330 if (!planes[p].bands)
331 return AVERROR(ENOMEM);
333 /* select band dimensions: if there is only one band then it
334 * has the full size, if there are several bands each of them
335 * has only half size */
336 b_width = planes[p].num_bands == 1 ? planes[p].width
337 : (planes[p].width + 1) >> 1;
338 b_height = planes[p].num_bands == 1 ? planes[p].height
339 : (planes[p].height + 1) >> 1;
341 /* luma band buffers will be aligned on 16x16 (max macroblock size) */
342 /* chroma band buffers will be aligned on 8x8 (max macroblock size) */
343 align_fac = p ? 8 : 16;
344 width_aligned = FFALIGN(b_width , align_fac);
345 height_aligned = FFALIGN(b_height, align_fac);
346 buf_size = width_aligned * height_aligned * sizeof(int16_t);
348 for (b = 0; b < planes[p].num_bands; b++) {
349 band = &planes[p].bands[b]; /* select appropriate plane/band */
352 band->width = b_width;
353 band->height = b_height;
354 band->pitch = width_aligned;
355 band->aheight = height_aligned;
356 band->bufs[0] = av_mallocz(buf_size);
357 band->bufs[1] = av_mallocz(buf_size);
358 band->bufsize = buf_size/2;
359 if (!band->bufs[0] || !band->bufs[1])
360 return AVERROR(ENOMEM);
362 /* allocate the 3rd band buffer for scalability mode */
363 if (cfg->luma_bands > 1) {
364 band->bufs[2] = av_mallocz(buf_size);
366 return AVERROR(ENOMEM);
369 band->bufs[3] = av_mallocz(buf_size);
371 return AVERROR(ENOMEM);
373 /* reset custom vlc */
374 planes[p].bands[0].blk_vlc.cust_desc.num_rows = 0;
381 static int ivi_init_tiles(IVIBandDesc *band, IVITile *ref_tile,
382 int p, int b, int t_height, int t_width)
385 IVITile *tile = band->tiles;
387 for (y = 0; y < band->height; y += t_height) {
388 for (x = 0; x < band->width; x += t_width) {
391 tile->mb_size = band->mb_size;
392 tile->width = FFMIN(band->width - x, t_width);
393 tile->height = FFMIN(band->height - y, t_height);
394 tile->is_empty = tile->data_size = 0;
395 /* calculate number of macroblocks */
396 tile->num_MBs = IVI_MBs_PER_TILE(tile->width, tile->height,
399 av_freep(&tile->mbs);
400 tile->mbs = av_mallocz_array(tile->num_MBs, sizeof(IVIMbInfo));
402 return AVERROR(ENOMEM);
406 if (tile->num_MBs != ref_tile->num_MBs) {
407 av_log(NULL, AV_LOG_DEBUG, "ref_tile mismatch\n");
408 return AVERROR_INVALIDDATA;
410 tile->ref_mbs = ref_tile->mbs;
420 av_cold int ff_ivi_init_tiles(IVIPlaneDesc *planes,
421 int tile_width, int tile_height)
423 int p, b, x_tiles, y_tiles, t_width, t_height, ret;
426 for (p = 0; p < 3; p++) {
427 t_width = !p ? tile_width : (tile_width + 3) >> 2;
428 t_height = !p ? tile_height : (tile_height + 3) >> 2;
430 if (!p && planes[0].num_bands == 4) {
434 if(t_width<=0 || t_height<=0)
435 return AVERROR(EINVAL);
437 for (b = 0; b < planes[p].num_bands; b++) {
438 band = &planes[p].bands[b];
439 x_tiles = IVI_NUM_TILES(band->width, t_width);
440 y_tiles = IVI_NUM_TILES(band->height, t_height);
441 band->num_tiles = x_tiles * y_tiles;
443 av_freep(&band->tiles);
444 band->tiles = av_mallocz_array(band->num_tiles, sizeof(IVITile));
446 return AVERROR(ENOMEM);
448 /* use the first luma band as reference for motion vectors
450 ret = ivi_init_tiles(band, planes[0].bands[0].tiles,
451 p, b, t_height, t_width);
461 * Decode size of the tile data.
462 * The size is stored as a variable-length field having the following format:
463 * if (tile_data_size < 255) than this field is only one byte long
464 * if (tile_data_size >= 255) than this field four is byte long: 0xFF X1 X2 X3
465 * where X1-X3 is size of the tile data
467 * @param[in,out] gb the GetBit context
468 * @return size of the tile data in bytes
470 static int ivi_dec_tile_data_size(GetBitContext *gb)
476 len = get_bits(gb, 8);
478 len = get_bits_long(gb, 24);
481 /* align the bitstream reader on the byte boundary */
487 static int ivi_dc_transform(IVIBandDesc *band, int *prev_dc, int buf_offs,
490 int buf_size = band->pitch * band->aheight - buf_offs;
491 int min_size = (blk_size - 1) * band->pitch + blk_size;
493 if (min_size > buf_size)
494 return AVERROR_INVALIDDATA;
496 band->dc_transform(prev_dc, band->buf + buf_offs,
497 band->pitch, blk_size);
502 static int ivi_decode_coded_blocks(GetBitContext *gb, IVIBandDesc *band,
503 ivi_mc_func mc, ivi_mc_avg_func mc_avg,
505 int mv_x2, int mv_y2,
506 int *prev_dc, int is_intra,
507 int mc_type, int mc_type2,
508 uint32_t quant, int offs,
509 AVCodecContext *avctx)
511 const uint16_t *base_tab = is_intra ? band->intra_base : band->inter_base;
512 RVMapDesc *rvmap = band->rv_map;
513 uint8_t col_flags[8];
515 uint32_t sym = 0, lo, hi, q;
517 int blk_size = band->blk_size;
518 int num_coeffs = blk_size * blk_size;
519 int col_mask = blk_size - 1;
521 int min_size = band->pitch * (band->transform_size - 1) +
522 band->transform_size;
523 int buf_size = band->pitch * band->aheight - offs;
525 if (min_size > buf_size)
526 return AVERROR_INVALIDDATA;
529 av_log(avctx, AV_LOG_ERROR, "Scan pattern is not set.\n");
530 return AVERROR_INVALIDDATA;
533 /* zero transform vector */
534 memset(trvec, 0, num_coeffs * sizeof(trvec[0]));
535 /* zero column flags */
536 memset(col_flags, 0, sizeof(col_flags));
537 while (scan_pos <= num_coeffs) {
538 sym = get_vlc2(gb, band->blk_vlc.tab->table,
540 if (sym == rvmap->eob_sym)
541 break; /* End of block */
543 /* Escape - run/val explicitly coded using 3 vlc codes */
544 if (sym == rvmap->esc_sym) {
545 run = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1) + 1;
546 lo = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
547 hi = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
548 /* merge them and convert into signed val */
549 val = IVI_TOSIGNED((hi << 6) | lo);
552 av_log(avctx, AV_LOG_ERROR, "Invalid sym encountered: %"PRIu32".\n", sym);
553 return AVERROR_INVALIDDATA;
555 run = rvmap->runtab[sym];
556 val = rvmap->valtab[sym];
559 /* de-zigzag and dequantize */
561 if (scan_pos >= num_coeffs || scan_pos < 0)
563 pos = band->scan[scan_pos];
566 ff_dlog(avctx, "Val = 0 encountered!\n");
568 q = (base_tab[pos] * quant) >> 9;
570 val = val * q + FFSIGN(val) * (((q ^ 1) - 1) >> 1);
572 /* track columns containing non-zero coeffs */
573 col_flags[pos & col_mask] |= !!val;
576 if (scan_pos < 0 || scan_pos >= num_coeffs && sym != rvmap->eob_sym)
577 return AVERROR_INVALIDDATA; /* corrupt block data */
579 /* undoing DC coeff prediction for intra-blocks */
580 if (is_intra && band->is_2d_trans) {
581 *prev_dc += trvec[0];
583 col_flags[0] |= !!*prev_dc;
586 if(band->transform_size > band->blk_size){
587 av_log(NULL, AV_LOG_ERROR, "Too large transform\n");
588 return AVERROR_INVALIDDATA;
591 /* apply inverse transform */
592 band->inv_transform(trvec, band->buf + offs,
593 band->pitch, col_flags);
595 /* apply motion compensation */
597 return ivi_mc(band, mc, mc_avg, offs, mv_x, mv_y, mv_x2, mv_y2,
604 * extract huffman-coded transform coefficients from the bitstream,
605 * dequantize them, apply inverse transform and motion compensation
606 * in order to reconstruct the picture.
608 * @param[in,out] gb the GetBit context
609 * @param[in] band pointer to the band descriptor
610 * @param[in] tile pointer to the tile descriptor
611 * @return result code: 0 - OK, -1 = error (corrupted blocks data)
613 static int ivi_decode_blocks(GetBitContext *gb, IVIBandDesc *band,
614 IVITile *tile, AVCodecContext *avctx)
616 int mbn, blk, num_blocks, blk_size, ret, is_intra;
617 int mc_type = 0, mc_type2 = -1;
618 int mv_x = 0, mv_y = 0, mv_x2 = 0, mv_y2 = 0;
620 uint32_t cbp, quant, buf_offs;
622 ivi_mc_func mc_with_delta_func, mc_no_delta_func;
623 ivi_mc_avg_func mc_avg_with_delta_func, mc_avg_no_delta_func;
624 const uint8_t *scale_tab;
626 /* init intra prediction for the DC coefficient */
628 blk_size = band->blk_size;
629 /* number of blocks per mb */
630 num_blocks = (band->mb_size != blk_size) ? 4 : 1;
632 mc_with_delta_func = ff_ivi_mc_8x8_delta;
633 mc_no_delta_func = ff_ivi_mc_8x8_no_delta;
634 mc_avg_with_delta_func = ff_ivi_mc_avg_8x8_delta;
635 mc_avg_no_delta_func = ff_ivi_mc_avg_8x8_no_delta;
637 mc_with_delta_func = ff_ivi_mc_4x4_delta;
638 mc_no_delta_func = ff_ivi_mc_4x4_no_delta;
639 mc_avg_with_delta_func = ff_ivi_mc_avg_4x4_delta;
640 mc_avg_no_delta_func = ff_ivi_mc_avg_4x4_no_delta;
643 for (mbn = 0, mb = tile->mbs; mbn < tile->num_MBs; mb++, mbn++) {
644 is_intra = !mb->type;
646 buf_offs = mb->buf_offs;
648 quant = band->glob_quant + mb->q_delta;
649 if (avctx->codec_id == AV_CODEC_ID_INDEO4)
650 quant = av_clip_uintp2(quant, 5);
652 quant = av_clip(quant, 0, 23);
654 scale_tab = is_intra ? band->intra_scale : band->inter_scale;
656 quant = scale_tab[quant];
663 if (band->is_halfpel) {
664 mc_type = ((mv_y & 1) << 1) | (mv_x & 1);
665 mc_type2 = ((mv_y2 & 1) << 1) | (mv_x2 & 1);
669 mv_y2 >>= 1; /* convert halfpel vectors into fullpel ones */
673 if (mb->type != 2 && mb->type != 3)
676 int dmv_x, dmv_y, cx, cy;
678 dmv_x = mb->mv_x >> band->is_halfpel;
679 dmv_y = mb->mv_y >> band->is_halfpel;
680 cx = mb->mv_x & band->is_halfpel;
681 cy = mb->mv_y & band->is_halfpel;
683 if (mb->xpos + dmv_x < 0 ||
684 mb->xpos + dmv_x + band->mb_size + cx > band->pitch ||
685 mb->ypos + dmv_y < 0 ||
686 mb->ypos + dmv_y + band->mb_size + cy > band->aheight) {
687 return AVERROR_INVALIDDATA;
690 if (mb->type == 2 || mb->type == 3) {
691 int dmv_x, dmv_y, cx, cy;
693 dmv_x = mb->b_mv_x >> band->is_halfpel;
694 dmv_y = mb->b_mv_y >> band->is_halfpel;
695 cx = mb->b_mv_x & band->is_halfpel;
696 cy = mb->b_mv_y & band->is_halfpel;
698 if (mb->xpos + dmv_x < 0 ||
699 mb->xpos + dmv_x + band->mb_size + cx > band->pitch ||
700 mb->ypos + dmv_y < 0 ||
701 mb->ypos + dmv_y + band->mb_size + cy > band->aheight) {
702 return AVERROR_INVALIDDATA;
707 for (blk = 0; blk < num_blocks; blk++) {
708 /* adjust block position in the buffer according to its number */
710 buf_offs += blk_size;
711 } else if (blk == 2) {
712 buf_offs -= blk_size;
713 buf_offs += blk_size * band->pitch;
716 if (cbp & 1) { /* block coded ? */
717 ret = ivi_decode_coded_blocks(gb, band, mc_with_delta_func,
718 mc_avg_with_delta_func,
719 mv_x, mv_y, mv_x2, mv_y2,
721 mc_type, mc_type2, quant,
726 /* block not coded */
727 /* for intra blocks apply the dc slant transform */
728 /* for inter - perform the motion compensation without delta */
730 ret = ivi_dc_transform(band, &prev_dc, buf_offs, blk_size);
734 ret = ivi_mc(band, mc_no_delta_func, mc_avg_no_delta_func,
735 buf_offs, mv_x, mv_y, mv_x2, mv_y2,
752 * Handle empty tiles by performing data copying and motion
753 * compensation respectively.
755 * @param[in] avctx ptr to the AVCodecContext
756 * @param[in] band pointer to the band descriptor
757 * @param[in] tile pointer to the tile descriptor
758 * @param[in] mv_scale scaling factor for motion vectors
760 static int ivi_process_empty_tile(AVCodecContext *avctx, IVIBandDesc *band,
761 IVITile *tile, int32_t mv_scale)
763 int x, y, need_mc, mbn, blk, num_blocks, mv_x, mv_y, mc_type;
764 int offs, mb_offset, row_offset, ret;
765 IVIMbInfo *mb, *ref_mb;
768 ivi_mc_func mc_no_delta_func;
770 if (tile->num_MBs != IVI_MBs_PER_TILE(tile->width, tile->height, band->mb_size)) {
771 av_log(avctx, AV_LOG_ERROR, "Allocated tile size %d mismatches "
772 "parameters %d in ivi_process_empty_tile()\n",
773 tile->num_MBs, IVI_MBs_PER_TILE(tile->width, tile->height, band->mb_size));
774 return AVERROR_INVALIDDATA;
777 offs = tile->ypos * band->pitch + tile->xpos;
779 ref_mb = tile->ref_mbs;
780 row_offset = band->mb_size * band->pitch;
781 need_mc = 0; /* reset the mc tracking flag */
783 for (y = tile->ypos; y < (tile->ypos + tile->height); y += band->mb_size) {
786 for (x = tile->xpos; x < (tile->xpos + tile->width); x += band->mb_size) {
789 mb->buf_offs = mb_offset;
791 mb->type = 1; /* set the macroblocks type = INTER */
792 mb->cbp = 0; /* all blocks are empty */
794 if (!band->qdelta_present && !band->plane && !band->band_num) {
795 mb->q_delta = band->glob_quant;
800 if (band->inherit_qdelta && ref_mb)
801 mb->q_delta = ref_mb->q_delta;
803 if (band->inherit_mv && ref_mb) {
804 /* motion vector inheritance */
806 mb->mv_x = ivi_scale_mv(ref_mb->mv_x, mv_scale);
807 mb->mv_y = ivi_scale_mv(ref_mb->mv_y, mv_scale);
809 mb->mv_x = ref_mb->mv_x;
810 mb->mv_y = ref_mb->mv_y;
812 need_mc |= mb->mv_x || mb->mv_y; /* tracking non-zero motion vectors */
814 int dmv_x, dmv_y, cx, cy;
816 dmv_x = mb->mv_x >> band->is_halfpel;
817 dmv_y = mb->mv_y >> band->is_halfpel;
818 cx = mb->mv_x & band->is_halfpel;
819 cy = mb->mv_y & band->is_halfpel;
821 if ( mb->xpos + dmv_x < 0
822 || mb->xpos + dmv_x + band->mb_size + cx > band->pitch
823 || mb->ypos + dmv_y < 0
824 || mb->ypos + dmv_y + band->mb_size + cy > band->aheight) {
825 av_log(avctx, AV_LOG_ERROR, "MV out of bounds\n");
826 return AVERROR_INVALIDDATA;
834 mb_offset += band->mb_size;
839 if (band->inherit_mv && need_mc) { /* apply motion compensation if there is at least one non-zero motion vector */
840 num_blocks = (band->mb_size != band->blk_size) ? 4 : 1; /* number of blocks per mb */
841 mc_no_delta_func = (band->blk_size == 8) ? ff_ivi_mc_8x8_no_delta
842 : ff_ivi_mc_4x4_no_delta;
844 for (mbn = 0, mb = tile->mbs; mbn < tile->num_MBs; mb++, mbn++) {
847 if (!band->is_halfpel) {
848 mc_type = 0; /* we have only fullpel vectors */
850 mc_type = ((mv_y & 1) << 1) | (mv_x & 1);
852 mv_y >>= 1; /* convert halfpel vectors into fullpel ones */
855 for (blk = 0; blk < num_blocks; blk++) {
856 /* adjust block position in the buffer according with its number */
857 offs = mb->buf_offs + band->blk_size * ((blk & 1) + !!(blk & 2) * band->pitch);
858 ret = ivi_mc(band, mc_no_delta_func, 0, offs,
859 mv_x, mv_y, 0, 0, mc_type, -1);
865 /* copy data from the reference tile into the current one */
866 src = band->ref_buf + tile->ypos * band->pitch + tile->xpos;
867 dst = band->buf + tile->ypos * band->pitch + tile->xpos;
868 for (y = 0; y < tile->height; y++) {
869 memcpy(dst, src, tile->width*sizeof(band->buf[0]));
880 static uint16_t ivi_calc_band_checksum(IVIBandDesc *band)
883 int16_t *src, checksum;
888 for (y = 0; y < band->height; src += band->pitch, y++)
889 for (x = 0; x < band->width; x++)
897 * Convert and output the current plane.
898 * This conversion is done by adding back the bias value of 128
899 * (subtracted in the encoder) and clipping the result.
901 * @param[in] plane pointer to the descriptor of the plane being processed
902 * @param[out] dst pointer to the buffer receiving converted pixels
903 * @param[in] dst_pitch pitch for moving to the next y line
905 static void ivi_output_plane(IVIPlaneDesc *plane, uint8_t *dst, int dst_pitch)
908 const int16_t *src = plane->bands[0].buf;
909 uint32_t pitch = plane->bands[0].pitch;
914 for (y = 0; y < plane->height; y++) {
915 for (x = 0; x < plane->width; x++)
916 dst[x] = av_clip_uint8(src[x] + 128);
923 * Decode an Indeo 4 or 5 band.
925 * @param[in,out] ctx ptr to the decoder context
926 * @param[in,out] band ptr to the band descriptor
927 * @param[in] avctx ptr to the AVCodecContext
928 * @return result code: 0 = OK, -1 = error
930 static int decode_band(IVI45DecContext *ctx,
931 IVIBandDesc *band, AVCodecContext *avctx)
933 int result, i, t, idx1, idx2, pos;
936 band->buf = band->bufs[ctx->dst_buf];
938 av_log(avctx, AV_LOG_ERROR, "Band buffer points to no data!\n");
939 return AVERROR_INVALIDDATA;
941 if (ctx->is_indeo4 && ctx->frame_type == IVI4_FRAMETYPE_BIDIR) {
942 band->ref_buf = band->bufs[ctx->b_ref_buf];
943 band->b_ref_buf = band->bufs[ctx->ref_buf];
945 band->ref_buf = band->bufs[ctx->ref_buf];
948 band->data_ptr = ctx->frame_data + (get_bits_count(&ctx->gb) >> 3);
950 result = ctx->decode_band_hdr(ctx, band, avctx);
952 av_log(avctx, AV_LOG_ERROR, "Error while decoding band header: %d\n",
957 if (band->is_empty) {
958 av_log(avctx, AV_LOG_ERROR, "Empty band encountered!\n");
959 return AVERROR_INVALIDDATA;
962 band->rv_map = &ctx->rvmap_tabs[band->rvmap_sel];
964 /* apply corrections to the selected rvmap table if present */
965 for (i = 0; i < band->num_corr; i++) {
966 idx1 = band->corr[i * 2];
967 idx2 = band->corr[i * 2 + 1];
968 FFSWAP(uint8_t, band->rv_map->runtab[idx1], band->rv_map->runtab[idx2]);
969 FFSWAP(int16_t, band->rv_map->valtab[idx1], band->rv_map->valtab[idx2]);
970 if (idx1 == band->rv_map->eob_sym || idx2 == band->rv_map->eob_sym)
971 band->rv_map->eob_sym ^= idx1 ^ idx2;
972 if (idx1 == band->rv_map->esc_sym || idx2 == band->rv_map->esc_sym)
973 band->rv_map->esc_sym ^= idx1 ^ idx2;
976 pos = get_bits_count(&ctx->gb);
978 for (t = 0; t < band->num_tiles; t++) {
979 tile = &band->tiles[t];
981 if (tile->mb_size != band->mb_size) {
982 av_log(avctx, AV_LOG_ERROR, "MB sizes mismatch: %d vs. %d\n",
983 band->mb_size, tile->mb_size);
984 return AVERROR_INVALIDDATA;
986 tile->is_empty = get_bits1(&ctx->gb);
987 if (tile->is_empty) {
988 result = ivi_process_empty_tile(avctx, band, tile,
989 (ctx->planes[0].bands[0].mb_size >> 3) - (band->mb_size >> 3));
992 ff_dlog(avctx, "Empty tile encountered!\n");
994 tile->data_size = ivi_dec_tile_data_size(&ctx->gb);
995 if (!tile->data_size) {
996 av_log(avctx, AV_LOG_ERROR, "Tile data size is zero!\n");
997 result = AVERROR_INVALIDDATA;
1001 result = ctx->decode_mb_info(ctx, band, tile, avctx);
1005 result = ivi_decode_blocks(&ctx->gb, band, tile, avctx);
1007 av_log(avctx, AV_LOG_ERROR,
1008 "Corrupted tile data encountered!\n");
1012 if (((get_bits_count(&ctx->gb) - pos) >> 3) != tile->data_size) {
1013 av_log(avctx, AV_LOG_ERROR,
1014 "Tile data_size mismatch!\n");
1015 result = AVERROR_INVALIDDATA;
1019 pos += tile->data_size << 3; // skip to next tile
1023 /* restore the selected rvmap table by applying its corrections in
1025 for (i = band->num_corr-1; i >= 0; i--) {
1026 idx1 = band->corr[i*2];
1027 idx2 = band->corr[i*2+1];
1028 FFSWAP(uint8_t, band->rv_map->runtab[idx1], band->rv_map->runtab[idx2]);
1029 FFSWAP(int16_t, band->rv_map->valtab[idx1], band->rv_map->valtab[idx2]);
1030 if (idx1 == band->rv_map->eob_sym || idx2 == band->rv_map->eob_sym)
1031 band->rv_map->eob_sym ^= idx1 ^ idx2;
1032 if (idx1 == band->rv_map->esc_sym || idx2 == band->rv_map->esc_sym)
1033 band->rv_map->esc_sym ^= idx1 ^ idx2;
1037 if (band->checksum_present) {
1038 uint16_t chksum = ivi_calc_band_checksum(band);
1039 if (chksum != band->checksum) {
1040 av_log(avctx, AV_LOG_ERROR,
1041 "Band checksum mismatch! Plane %d, band %d, "
1042 "received: %"PRIx32", calculated: %"PRIx16"\n",
1043 band->plane, band->band_num, band->checksum, chksum);
1048 align_get_bits(&ctx->gb);
1053 int ff_ivi_decode_frame(AVCodecContext *avctx, void *data, int *got_frame,
1056 IVI45DecContext *ctx = avctx->priv_data;
1057 const uint8_t *buf = avpkt->data;
1058 AVFrame *frame = data;
1059 int buf_size = avpkt->size;
1062 init_get_bits(&ctx->gb, buf, buf_size * 8);
1063 ctx->frame_data = buf;
1064 ctx->frame_size = buf_size;
1066 result = ctx->decode_pic_hdr(ctx, avctx);
1068 av_log(avctx, AV_LOG_ERROR,
1069 "Error while decoding picture header: %d\n", result);
1072 if (ctx->gop_invalid)
1073 return AVERROR_INVALIDDATA;
1075 if (ctx->is_indeo4 && ctx->frame_type == IVI4_FRAMETYPE_NULL_LAST) {
1076 if (ctx->got_p_frame) {
1077 av_frame_move_ref(data, ctx->p_frame);
1079 ctx->got_p_frame = 0;
1086 if (ctx->gop_flags & IVI5_IS_PROTECTED) {
1087 avpriv_report_missing_feature(avctx, "Password-protected clip!\n");
1088 return AVERROR_PATCHWELCOME;
1091 if (!ctx->planes[0].bands) {
1092 av_log(avctx, AV_LOG_ERROR, "Color planes not initialized yet\n");
1093 return AVERROR_INVALIDDATA;
1096 ctx->switch_buffers(ctx);
1100 if (ctx->is_nonnull_frame(ctx)) {
1101 ctx->buf_invalid[ctx->dst_buf] = 1;
1102 for (p = 0; p < 3; p++) {
1103 for (b = 0; b < ctx->planes[p].num_bands; b++) {
1104 result = decode_band(ctx, &ctx->planes[p].bands[b], avctx);
1106 av_log(avctx, AV_LOG_ERROR,
1107 "Error while decoding band: %d, plane: %d\n", b, p);
1112 ctx->buf_invalid[ctx->dst_buf] = 0;
1114 if (ctx->is_scalable)
1115 return AVERROR_INVALIDDATA;
1117 for (p = 0; p < 3; p++) {
1118 if (!ctx->planes[p].bands[0].buf)
1119 return AVERROR_INVALIDDATA;
1122 if (ctx->buf_invalid[ctx->dst_buf])
1125 //STOP_TIMER("decode_planes"); }
1127 if (!ctx->is_nonnull_frame(ctx))
1130 result = ff_set_dimensions(avctx, ctx->planes[0].width, ctx->planes[0].height);
1134 if ((result = ff_get_buffer(avctx, frame, 0)) < 0)
1137 if (ctx->is_scalable) {
1139 ff_ivi_recompose_haar(&ctx->planes[0], frame->data[0], frame->linesize[0]);
1141 ff_ivi_recompose53 (&ctx->planes[0], frame->data[0], frame->linesize[0]);
1143 ivi_output_plane(&ctx->planes[0], frame->data[0], frame->linesize[0]);
1146 ivi_output_plane(&ctx->planes[2], frame->data[1], frame->linesize[1]);
1147 ivi_output_plane(&ctx->planes[1], frame->data[2], frame->linesize[2]);
1151 /* If the bidirectional mode is enabled, next I and the following P
1152 * frame will be sent together. Unfortunately the approach below seems
1153 * to be the only way to handle the B-frames mode.
1154 * That's exactly the same Intel decoders do.
1156 if (ctx->is_indeo4 && ctx->frame_type == IVI4_FRAMETYPE_INTRA) {
1159 // skip version string
1160 while (get_bits(&ctx->gb, 8)) {
1161 if (get_bits_left(&ctx->gb) < 8)
1162 return AVERROR_INVALIDDATA;
1164 left = get_bits_count(&ctx->gb) & 0x18;
1165 skip_bits_long(&ctx->gb, 64 - left);
1166 if (get_bits_left(&ctx->gb) > 18 &&
1167 show_bits_long(&ctx->gb, 21) == 0xBFFF8) { // syncheader + inter type
1169 pkt.data = avpkt->data + (get_bits_count(&ctx->gb) >> 3);
1170 pkt.size = get_bits_left(&ctx->gb) >> 3;
1171 ff_ivi_decode_frame(avctx, ctx->p_frame, &ctx->got_p_frame, &pkt);
1179 * Close Indeo5 decoder and clean up its context.
1181 av_cold int ff_ivi_decode_close(AVCodecContext *avctx)
1183 IVI45DecContext *ctx = avctx->priv_data;
1185 ivi_free_buffers(&ctx->planes[0]);
1187 if (ctx->mb_vlc.cust_tab.table)
1188 ff_free_vlc(&ctx->mb_vlc.cust_tab);
1190 #if IVI4_STREAM_ANALYSER
1191 if (ctx->is_indeo4) {
1192 if (ctx->is_scalable)
1193 av_log(avctx, AV_LOG_ERROR, "This video uses scalability mode!\n");
1194 if (ctx->uses_tiling)
1195 av_log(avctx, AV_LOG_ERROR, "This video uses local decoding!\n");
1196 if (ctx->has_b_frames)
1197 av_log(avctx, AV_LOG_ERROR, "This video contains B-frames!\n");
1198 if (ctx->has_transp)
1199 av_log(avctx, AV_LOG_ERROR, "Transparency mode is enabled!\n");
1201 av_log(avctx, AV_LOG_ERROR, "This video uses Haar transform!\n");
1202 if (ctx->uses_fullpel)
1203 av_log(avctx, AV_LOG_ERROR, "This video uses fullpel motion vectors!\n");
1207 av_frame_free(&ctx->p_frame);
1214 * Scan patterns shared between indeo4 and indeo5
1216 const uint8_t ff_ivi_vertical_scan_8x8[64] = {
1217 0, 8, 16, 24, 32, 40, 48, 56,
1218 1, 9, 17, 25, 33, 41, 49, 57,
1219 2, 10, 18, 26, 34, 42, 50, 58,
1220 3, 11, 19, 27, 35, 43, 51, 59,
1221 4, 12, 20, 28, 36, 44, 52, 60,
1222 5, 13, 21, 29, 37, 45, 53, 61,
1223 6, 14, 22, 30, 38, 46, 54, 62,
1224 7, 15, 23, 31, 39, 47, 55, 63
1227 const uint8_t ff_ivi_horizontal_scan_8x8[64] = {
1228 0, 1, 2, 3, 4, 5, 6, 7,
1229 8, 9, 10, 11, 12, 13, 14, 15,
1230 16, 17, 18, 19, 20, 21, 22, 23,
1231 24, 25, 26, 27, 28, 29, 30, 31,
1232 32, 33, 34, 35, 36, 37, 38, 39,
1233 40, 41, 42, 43, 44, 45, 46, 47,
1234 48, 49, 50, 51, 52, 53, 54, 55,
1235 56, 57, 58, 59, 60, 61, 62, 63
1238 const uint8_t ff_ivi_direct_scan_4x4[16] = {
1239 0, 1, 4, 8, 5, 2, 3, 6, 9, 12, 13, 10, 7, 11, 14, 15
1244 * Run-value (RLE) tables.
1246 const RVMapDesc ff_ivi_rvmap_tabs[9] = {
1251 {1, 1, 0, 1, 1, 0, 1, 1, 2, 2, 1, 1, 1, 1, 3, 3,
1252 1, 1, 2, 2, 1, 1, 4, 4, 1, 1, 1, 1, 2, 2, 5, 5,
1253 1, 1, 3, 3, 1, 1, 6, 6, 1, 2, 1, 2, 7, 7, 1, 1,
1254 8, 8, 1, 1, 4, 2, 1, 4, 2, 1, 3, 3, 1, 1, 1, 9,
1255 9, 1, 2, 1, 2, 1, 5, 5, 1, 1, 10, 10, 1, 1, 3, 3,
1256 2, 2, 1, 1, 11, 11, 6, 4, 4, 1, 6, 1, 2, 1, 2, 12,
1257 8, 1, 12, 7, 8, 7, 1, 16, 1, 16, 1, 3, 3, 13, 1, 13,
1258 2, 2, 1, 15, 1, 5, 14, 15, 1, 5, 14, 1, 17, 8, 17, 8,
1259 1, 4, 4, 2, 2, 1, 25, 25, 24, 24, 1, 3, 1, 3, 1, 8,
1260 6, 7, 6, 1, 18, 8, 18, 1, 7, 23, 2, 2, 23, 1, 1, 21,
1261 22, 9, 9, 22, 19, 1, 21, 5, 19, 5, 1, 33, 20, 33, 20, 8,
1262 4, 4, 1, 32, 2, 2, 8, 3, 32, 26, 3, 1, 7, 7, 26, 6,
1263 1, 6, 1, 1, 16, 1, 10, 1, 10, 2, 16, 29, 28, 2, 29, 28,
1264 1, 27, 5, 8, 5, 27, 1, 8, 3, 7, 3, 31, 41, 31, 1, 41,
1265 6, 1, 6, 7, 4, 4, 1, 1, 2, 1, 2, 11, 34, 30, 11, 1,
1266 30, 15, 15, 34, 36, 40, 36, 40, 35, 35, 37, 37, 39, 39, 38, 38},
1269 { 1, -1, 0, 2, -2, 0, 3, -3, 1, -1, 4, -4, 5, -5, 1, -1,
1270 6, -6, 2, -2, 7, -7, 1, -1, 8, -8, 9, -9, 3, -3, 1, -1,
1271 10, -10, 2, -2, 11, -11, 1, -1, 12, 4, -12, -4, 1, -1, 13, -13,
1272 1, -1, 14, -14, 2, 5, 15, -2, -5, -15, -3, 3, 16, -16, 17, 1,
1273 -1, -17, 6, 18, -6, -18, 2, -2, 19, -19, 1, -1, 20, -20, 4, -4,
1274 7, -7, 21, -21, 1, -1, 2, 3, -3, 22, -2, -22, 8, 23, -8, 1,
1275 2, -23, -1, 2, -2, -2, 24, 1, -24, -1, 25, 5, -5, 1, -25, -1,
1276 9, -9, 26, 1, -26, 3, 1, -1, 27, -3, -1, -27, 1, 3, -1, -3,
1277 28, -4, 4, 10, -10, -28, 1, -1, 1, -1, 29, 6, -29, -6, 30, -4,
1278 3, 3, -3, -30, 1, 4, -1, 31, -3, 1, 11, -11, -1, -31, 32, -1,
1279 -1, 2, -2, 1, 1, -32, 1, 4, -1, -4, 33, -1, 1, 1, -1, 5,
1280 5, -5, -33, -1, -12, 12, -5, -7, 1, 1, 7, 34, 4, -4, -1, 4,
1281 -34, -4, 35, 36, -2, -35, -2, -36, 2, 13, 2, -1, 1, -13, 1, -1,
1282 37, 1, -5, 6, 5, -1, 38, -6, -8, 5, 8, -1, 1, 1, -37, -1,
1283 5, 39, -5, -5, 6, -6, -38, -39, -14, 40, 14, 2, 1, 1, -2, -40,
1284 -1, -2, 2, -1, -1, -1, 1, 1, 1, -1, 1, -1, 1, -1, 1, -1}
1290 {0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 8, 6, 8, 7,
1291 7, 9, 9, 10, 10, 11, 11, 1, 12, 1, 12, 13, 13, 16, 14, 16,
1292 14, 15, 15, 17, 17, 18, 0, 18, 19, 20, 21, 19, 22, 21, 20, 22,
1293 25, 24, 2, 25, 24, 23, 23, 2, 26, 28, 26, 28, 29, 27, 29, 27,
1294 33, 33, 1, 32, 1, 3, 32, 30, 36, 3, 36, 30, 31, 31, 35, 34,
1295 37, 41, 34, 35, 37, 4, 41, 4, 49, 8, 8, 49, 40, 38, 5, 38,
1296 40, 39, 5, 39, 42, 43, 42, 7, 57, 6, 43, 44, 6, 50, 7, 44,
1297 57, 48, 50, 48, 45, 45, 46, 47, 51, 46, 47, 58, 1, 51, 58, 1,
1298 52, 59, 53, 9, 52, 55, 55, 59, 53, 56, 54, 56, 54, 9, 64, 64,
1299 60, 63, 60, 63, 61, 62, 61, 62, 2, 10, 2, 10, 11, 1, 11, 13,
1300 12, 1, 12, 13, 16, 16, 8, 8, 14, 3, 3, 15, 14, 15, 4, 4,
1301 1, 17, 17, 5, 1, 7, 7, 5, 6, 1, 2, 2, 6, 22, 1, 25,
1302 21, 22, 8, 24, 1, 21, 25, 24, 8, 18, 18, 23, 9, 20, 23, 33,
1303 29, 33, 20, 1, 19, 1, 29, 36, 9, 36, 19, 41, 28, 57, 32, 3,
1304 28, 3, 1, 27, 49, 49, 1, 32, 26, 26, 2, 4, 4, 7, 57, 41,
1305 2, 7, 10, 5, 37, 16, 10, 27, 8, 8, 13, 16, 37, 13, 1, 5},
1308 {0, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, 1, -1, -1, 1,
1309 -1, 1, -1, 1, -1, 1, -1, 2, 1, -2, -1, 1, -1, 1, 1, -1,
1310 -1, 1, -1, 1, -1, 1, 0, -1, 1, 1, 1, -1, 1, -1, -1, -1,
1311 1, 1, 2, -1, -1, 1, -1, -2, 1, 1, -1, -1, 1, 1, -1, -1,
1312 1, -1, 3, 1, -3, 2, -1, 1, 1, -2, -1, -1, -1, 1, 1, 1,
1313 1, 1, -1, -1, -1, 2, -1, -2, 1, 2, -2, -1, 1, 1, 2, -1,
1314 -1, 1, -2, -1, 1, 1, -1, 2, 1, 2, -1, 1, -2, -1, -2, -1,
1315 -1, 1, 1, -1, 1, -1, 1, 1, 1, -1, -1, 1, 4, -1, -1, -4,
1316 1, 1, 1, 2, -1, -1, 1, -1, -1, 1, -1, -1, 1, -2, 1, -1,
1317 1, 1, -1, -1, 1, 1, -1, -1, 3, 2, -3, -2, 2, 5, -2, 2,
1318 2, -5, -2, -2, -2, 2, -3, 3, 2, 3, -3, 2, -2, -2, 3, -3,
1319 6, 2, -2, 3, -6, 3, -3, -3, 3, 7, -4, 4, -3, 2, -7, 2,
1320 2, -2, -4, 2, 8, -2, -2, -2, 4, 2, -2, 2, 3, 2, -2, -2,
1321 2, 2, -2, -8, -2, 9, -2, 2, -3, -2, 2, -2, 2, 2, 2, 4,
1322 -2, -4, 10, 2, 2, -2, -9, -2, 2, -2, 5, 4, -4, 4, -2, 2,
1323 -5, -4, -3, 4, 2, -3, 3, -2, -5, 5, 3, 3, -2, -3, -10, -4}
1329 {1, 1, 0, 2, 2, 1, 1, 3, 3, 4, 4, 0, 1, 1, 5, 5,
1330 2, 2, 6, 6, 7, 7, 1, 8, 1, 8, 3, 3, 9, 9, 1, 2,
1331 2, 1, 4, 10, 4, 10, 11, 11, 1, 5, 12, 12, 1, 5, 13, 13,
1332 3, 3, 6, 6, 2, 2, 14, 14, 16, 16, 15, 7, 15, 8, 8, 7,
1333 1, 1, 17, 17, 4, 4, 1, 1, 18, 18, 2, 2, 5, 5, 25, 3,
1334 9, 3, 25, 9, 19, 24, 19, 24, 1, 21, 20, 1, 21, 22, 20, 22,
1335 23, 23, 8, 6, 33, 6, 8, 33, 7, 7, 26, 26, 1, 32, 1, 32,
1336 28, 4, 28, 10, 29, 27, 27, 10, 41, 4, 29, 2, 2, 41, 36, 31,
1337 49, 31, 34, 30, 34, 36, 30, 35, 1, 49, 11, 5, 35, 11, 1, 3,
1338 3, 5, 37, 37, 8, 40, 8, 40, 12, 12, 42, 42, 1, 38, 16, 57,
1339 1, 6, 16, 39, 38, 6, 7, 7, 13, 13, 39, 43, 2, 43, 57, 2,
1340 50, 9, 44, 9, 50, 4, 15, 48, 44, 4, 1, 15, 48, 14, 14, 1,
1341 45, 45, 8, 3, 5, 8, 51, 47, 3, 46, 46, 47, 5, 51, 1, 17,
1342 17, 58, 1, 58, 2, 52, 52, 2, 53, 7, 59, 6, 6, 56, 53, 55,
1343 7, 55, 1, 54, 59, 56, 54, 10, 1, 10, 4, 60, 1, 60, 8, 4,
1344 8, 64, 64, 61, 1, 63, 3, 63, 62, 61, 5, 11, 5, 3, 11, 62},
1347 { 1, -1, 0, 1, -1, 2, -2, 1, -1, 1, -1, 0, 3, -3, 1, -1,
1348 2, -2, 1, -1, 1, -1, 4, 1, -4, -1, 2, -2, 1, -1, 5, 3,
1349 -3, -5, 2, 1, -2, -1, 1, -1, 6, 2, 1, -1, -6, -2, 1, -1,
1350 3, -3, 2, -2, 4, -4, 1, -1, 1, -1, 1, 2, -1, 2, -2, -2,
1351 7, -7, 1, -1, 3, -3, 8, -8, 1, -1, 5, -5, 3, -3, 1, 4,
1352 2, -4, -1, -2, 1, 1, -1, -1, 9, 1, 1, -9, -1, 1, -1, -1,
1353 1, -1, 3, -3, 1, 3, -3, -1, 3, -3, 1, -1, 10, 1, -10, -1,
1354 1, 4, -1, 2, 1, -1, 1, -2, 1, -4, -1, 6, -6, -1, 1, 1,
1355 1, -1, 1, 1, -1, -1, -1, 1, 11, -1, -2, 4, -1, 2, -11, 5,
1356 -5, -4, -1, 1, 4, 1, -4, -1, -2, 2, 1, -1, 12, 1, -2, 1,
1357 -12, 4, 2, 1, -1, -4, 4, -4, 2, -2, -1, 1, 7, -1, -1, -7,
1358 -1, -3, 1, 3, 1, 5, 2, 1, -1, -5, 13, -2, -1, 2, -2, -13,
1359 1, -1, 5, 6, 5, -5, 1, 1, -6, 1, -1, -1, -5, -1, 14, 2,
1360 -2, 1, -14, -1, 8, 1, -1, -8, 1, 5, 1, 5, -5, 1, -1, 1,
1361 -5, -1, 15, 1, -1, -1, -1, 3, -15, -3, 6, 1, 16, -1, 6, -6,
1362 -6, 1, -1, 1, -16, 1, 7, -1, 1, -1, -6, -3, 6, -7, 3, -1}
1368 {0, 1, 1, 2, 2, 3, 3, 4, 4, 1, 1, 5, 5, 6, 6, 7,
1369 7, 8, 8, 9, 9, 2, 2, 10, 10, 1, 1, 11, 11, 12, 12, 3,
1370 3, 13, 13, 0, 14, 14, 16, 15, 16, 15, 4, 4, 17, 1, 17, 1,
1371 5, 5, 18, 18, 2, 2, 6, 6, 8, 19, 7, 8, 7, 19, 20, 20,
1372 21, 21, 22, 24, 22, 24, 23, 23, 1, 1, 25, 25, 3, 3, 26, 26,
1373 9, 9, 27, 27, 28, 28, 33, 29, 4, 33, 29, 1, 4, 1, 32, 32,
1374 2, 2, 31, 10, 30, 10, 30, 31, 34, 34, 5, 5, 36, 36, 35, 41,
1375 35, 11, 41, 11, 37, 1, 8, 8, 37, 6, 1, 6, 40, 7, 7, 40,
1376 12, 38, 12, 39, 39, 38, 49, 13, 49, 13, 3, 42, 3, 42, 16, 16,
1377 43, 43, 14, 14, 1, 1, 44, 15, 44, 15, 2, 2, 57, 48, 50, 48,
1378 57, 50, 4, 45, 45, 4, 46, 47, 47, 46, 1, 51, 1, 17, 17, 51,
1379 8, 9, 9, 5, 58, 8, 58, 5, 52, 52, 55, 56, 53, 56, 55, 59,
1380 59, 53, 54, 1, 6, 54, 7, 7, 6, 1, 2, 3, 2, 3, 64, 60,
1381 60, 10, 10, 64, 61, 62, 61, 63, 1, 63, 62, 1, 18, 24, 18, 4,
1382 25, 4, 8, 21, 21, 1, 24, 22, 25, 22, 8, 11, 19, 11, 23, 1,
1383 20, 23, 19, 20, 5, 12, 5, 1, 16, 2, 12, 13, 2, 13, 1, 16},
1386 { 0, 1, -1, 1, -1, 1, -1, 1, -1, 2, -2, 1, -1, 1, -1, 1,
1387 -1, 1, -1, 1, -1, 2, -2, 1, -1, 3, -3, 1, -1, 1, -1, 2,
1388 -2, 1, -1, 0, 1, -1, 1, 1, -1, -1, 2, -2, 1, 4, -1, -4,
1389 2, -2, 1, -1, -3, 3, 2, -2, 2, 1, 2, -2, -2, -1, 1, -1,
1390 1, -1, 1, 1, -1, -1, 1, -1, 5, -5, 1, -1, 3, -3, 1, -1,
1391 2, -2, 1, -1, 1, -1, 1, 1, 3, -1, -1, 6, -3, -6, -1, 1,
1392 4, -4, 1, 2, 1, -2, -1, -1, 1, -1, 3, -3, 1, -1, 1, 1,
1393 -1, 2, -1, -2, 1, 7, -3, 3, -1, 3, -7, -3, 1, -3, 3, -1,
1394 2, 1, -2, 1, -1, -1, 1, 2, -1, -2, -4, -1, 4, 1, 2, -2,
1395 1, -1, -2, 2, 8, -8, -1, 2, 1, -2, -5, 5, 1, -1, -1, 1,
1396 -1, 1, 4, -1, 1, -4, -1, -1, 1, 1, 9, 1, -9, 2, -2, -1,
1397 -4, 3, -3, -4, -1, 4, 1, 4, 1, -1, 1, -1, 1, 1, -1, 1,
1398 -1, -1, -1, 10, 4, 1, 4, -4, -4, -10, 6, 5, -6, -5, 1, -1,
1399 1, 3, -3, -1, 1, -1, -1, -1, 11, 1, 1, -11, -2, -2, 2, 5,
1400 -2, -5, -5, 2, -2, 12, 2, -2, 2, 2, 5, -3, -2, 3, -2, -12,
1401 -2, 2, 2, 2, -5, 3, 5, 13, -3, 7, -3, -3, -7, 3, -13, 3}
1407 {0, 1, 1, 1, 2, 2, 1, 3, 3, 1, 1, 1, 4, 4, 1, 5,
1408 2, 1, 5, 2, 1, 1, 6, 6, 1, 1, 1, 1, 1, 7, 3, 1,
1409 2, 3, 0, 1, 2, 7, 1, 1, 1, 8, 1, 1, 8, 1, 1, 1,
1410 9, 1, 9, 1, 2, 1, 1, 2, 1, 1, 10, 4, 1, 10, 1, 4,
1411 1, 1, 1, 1, 1, 3, 1, 1, 1, 3, 2, 1, 5, 1, 1, 1,
1412 2, 5, 1, 11, 1, 11, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1413 2, 1, 6, 1, 6, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 12,
1414 3, 1, 12, 1, 1, 1, 2, 1, 1, 3, 1, 1, 1, 1, 1, 1,
1415 4, 1, 1, 1, 2, 1, 1, 4, 1, 1, 1, 1, 1, 1, 2, 1,
1416 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 2, 1, 1, 5,
1417 1, 1, 1, 1, 1, 7, 1, 7, 1, 1, 2, 3, 1, 1, 1, 1,
1418 5, 1, 1, 1, 1, 1, 1, 2, 13, 1, 1, 1, 1, 1, 1, 1,
1419 1, 1, 1, 1, 1, 1, 1, 1, 13, 2, 1, 1, 4, 1, 1, 1,
1420 3, 1, 6, 1, 1, 1, 14, 1, 1, 1, 1, 1, 14, 6, 1, 1,
1421 1, 1, 15, 2, 4, 1, 2, 3, 15, 1, 1, 1, 8, 1, 1, 8,
1422 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1},
1425 { 0, 1, -1, 2, 1, -1, -2, 1, -1, 3, -3, 4, 1, -1, -4, 1,
1426 2, 5, -1, -2, -5, 6, 1, -1, -6, 7, -7, 8, -8, 1, 2, 9,
1427 3, -2, 0, -9, -3, -1, 10, -10, 11, 1, -11, 12, -1, -12, 13, -13,
1428 1, 14, -1, -14, 4, 15, -15, -4, 16, -16, 1, 2, 17, -1, -17, -2,
1429 18, -18, 19, -19, 20, 3, -20, 21, -21, -3, 5, 22, 2, -22, -23, 23,
1430 -5, -2, 24, 1, -24, -1, 25, -25, 26, -26, -27, 27, 28, 29, -28, -29,
1431 6, 30, 2, -31, -2, -30, 31, -6, -32, 32, 33, -33, 34, -35, -34, 1,
1432 4, -36, -1, 35, 37, 36, 7, -37, 38, -4, -38, 39, 41, 40, -40, -39,
1433 3, 42, -43, -41, -7, -42, 43, -3, 44, -44, 45, -45, 46, 47, 8, -47,
1434 -48, -46, 50, -50, 48, 49, 51, -49, 52, -52, 5, -51, -8, -53, 53, 3,
1435 -56, 56, 55, 54, -54, 2, 60, -2, -55, 58, 9, -5, 59, 57, -57, -63,
1436 -3, -58, -60, -61, 61, -59, -62, -9, 1, 64, 62, 69, -64, 63, 65, -67,
1437 -68, 66, -65, 68, -66, -69, 67, -70, -1, 10, 71, -71, 4, 73, 72, 70,
1438 6, -76, -3, 74, -78, -74, 1, 78, 80, -72, -75, 76, -1, 3, -73, 79,
1439 75, 77, 1, 11, -4, -79, -10, -6, -1, -77, -83, -80, 2, 81, -84, -2,
1440 83, -81, 82, -82, 84, -87, -86, 85, -11, -85, 86, -89, 87, -88, 88, 89}
1446 {1, 1, 0, 2, 1, 2, 1, 3, 3, 1, 1, 4, 4, 2, 2, 1,
1447 1, 5, 5, 6, 1, 6, 1, 7, 7, 3, 3, 2, 8, 2, 8, 1,
1448 1, 0, 9, 9, 1, 1, 10, 4, 10, 4, 11, 11, 2, 1, 2, 1,
1449 12, 12, 3, 3, 1, 1, 13, 5, 5, 13, 14, 1, 1, 14, 2, 2,
1450 6, 6, 15, 1, 1, 15, 16, 4, 7, 16, 4, 7, 1, 1, 3, 3,
1451 8, 8, 2, 2, 1, 1, 17, 17, 1, 1, 18, 18, 5, 5, 2, 2,
1452 1, 1, 9, 19, 9, 19, 20, 3, 3, 20, 1, 10, 21, 1, 10, 4,
1453 4, 21, 22, 6, 6, 22, 1, 1, 23, 24, 2, 2, 23, 24, 11, 1,
1454 1, 11, 7, 25, 7, 1, 1, 25, 8, 8, 3, 26, 3, 1, 12, 2,
1455 2, 26, 1, 12, 5, 5, 27, 4, 1, 4, 1, 27, 28, 1, 28, 13,
1456 1, 13, 2, 29, 2, 1, 32, 6, 1, 30, 14, 29, 14, 6, 3, 31,
1457 3, 1, 30, 1, 32, 31, 33, 9, 33, 1, 1, 7, 9, 7, 2, 2,
1458 1, 1, 4, 36, 34, 4, 5, 10, 10, 5, 34, 1, 1, 35, 8, 8,
1459 36, 3, 35, 1, 15, 3, 2, 1, 16, 15, 16, 2, 37, 1, 37, 1,
1460 1, 1, 6, 6, 38, 1, 38, 11, 1, 39, 39, 40, 11, 2, 41, 4,
1461 40, 1, 2, 4, 1, 1, 1, 41, 3, 1, 3, 1, 5, 7, 5, 7},
1464 { 1, -1, 0, 1, 2, -1, -2, 1, -1, 3, -3, 1, -1, 2, -2, 4,
1465 -4, 1, -1, 1, 5, -1, -5, 1, -1, 2, -2, 3, 1, -3, -1, 6,
1466 -6, 0, 1, -1, 7, -7, 1, 2, -1, -2, 1, -1, 4, 8, -4, -8,
1467 1, -1, 3, -3, 9, -9, 1, 2, -2, -1, 1, 10, -10, -1, 5, -5,
1468 2, -2, 1, 11, -11, -1, 1, 3, 2, -1, -3, -2, 12, -12, 4, -4,
1469 2, -2, -6, 6, 13, -13, 1, -1, 14, -14, 1, -1, 3, -3, 7, -7,
1470 15, -15, 2, 1, -2, -1, 1, 5, -5, -1, -16, 2, 1, 16, -2, 4,
1471 -4, -1, 1, 3, -3, -1, 17, -17, 1, 1, -8, 8, -1, -1, 2, 18,
1472 -18, -2, 3, 1, -3, 19, -19, -1, 3, -3, 6, 1, -6, 20, 2, 9,
1473 -9, -1, -20, -2, 4, -4, 1, -5, 21, 5, -21, -1, 1, -22, -1, 2,
1474 22, -2, 10, 1, -10, 23, 1, 4, -23, 1, 2, -1, -2, -4, -7, 1,
1475 7, -24, -1, 24, -1, -1, 1, 3, -1, -25, 25, 4, -3, -4, 11, -11,
1476 26, -26, 6, 1, 1, -6, -5, -3, 3, 5, -1, -27, 27, 1, 4, -4,
1477 -1, -8, -1, 28, 2, 8, -12, -28, -2, -2, 2, 12, -1, 29, 1, -29,
1478 30, -30, 5, -5, 1, -31, -1, 3, 31, -1, 1, 1, -3, -13, 1, -7,
1479 -1, -32, 13, 7, 32, 33, -33, -1, -9, -34, 9, 34, -6, 5, 6, -5}
1485 {1, 1, 0, 1, 1, 2, 2, 1, 1, 3, 3, 1, 1, 0, 2, 2,
1486 4, 1, 4, 1, 1, 1, 5, 5, 1, 1, 6, 6, 2, 2, 1, 1,
1487 3, 3, 7, 7, 1, 1, 8, 8, 1, 1, 2, 2, 1, 9, 1, 9,
1488 4, 4, 10, 1, 1, 10, 1, 1, 11, 11, 3, 3, 1, 2, 1, 2,
1489 1, 1, 12, 12, 5, 5, 1, 1, 13, 1, 1, 13, 2, 2, 1, 1,
1490 6, 6, 1, 1, 4, 14, 4, 14, 3, 1, 3, 1, 1, 1, 15, 7,
1491 15, 2, 2, 7, 1, 1, 1, 8, 1, 8, 16, 16, 1, 1, 1, 1,
1492 2, 1, 1, 2, 1, 1, 3, 5, 5, 3, 4, 1, 1, 4, 1, 1,
1493 17, 17, 9, 1, 1, 9, 2, 2, 1, 1, 10, 10, 1, 6, 1, 1,
1494 6, 18, 1, 1, 18, 1, 1, 1, 2, 2, 3, 1, 3, 1, 1, 1,
1495 4, 1, 19, 1, 19, 7, 1, 1, 20, 1, 4, 20, 1, 7, 11, 2,
1496 1, 11, 21, 2, 8, 5, 1, 8, 1, 5, 21, 1, 1, 1, 22, 1,
1497 1, 22, 1, 1, 3, 3, 1, 23, 2, 12, 24, 1, 1, 2, 1, 1,
1498 12, 23, 1, 1, 24, 1, 1, 1, 4, 1, 1, 1, 2, 1, 6, 6,
1499 4, 2, 1, 1, 1, 1, 1, 1, 1, 14, 13, 3, 1, 25, 9, 25,
1500 14, 1, 9, 3, 13, 1, 1, 1, 1, 1, 10, 1, 1, 2, 10, 2},
1503 {-20, -1, 0, 2, -2, 1, -1, 3, -3, 1, -1, 4, -4, 0, 2, -2,
1504 1, 5, -1, -5, 6, -6, 1, -1, 7, -7, 1, -1, 3, -3, 8, -8,
1505 2, -2, 1, -1, 9, -9, 1, -1, 10, -10, 4, -4, 11, 1, -11, -1,
1506 2, -2, 1, 12, -12, -1, 13, -13, 1, -1, 3, -3, 14, 5, -14, -5,
1507 -15, 15, -1, 1, 2, -2, 16, -16, 1, 17, -17, -1, 6, -6, 18, -18,
1508 2, -2, -19, 19, -3, 1, 3, -1, 4, 20, -4, 1, -21, 21, 1, 2,
1509 -1, -7, 7, -2, 22, -22, 23, 2, -23, -2, 1, -1, -24, 24, -25, 25,
1510 -8, -26, 26, 8, -27, 27, 5, 3, -3, -5, -4, 28, -28, 4, 29, -29,
1511 1, -1, -2, -30, 30, 2, 9, -9, -31, 31, 2, -2, -32, 3, 32, -33,
1512 -3, 1, 33, -34, -1, 34, -35, 35, -10, 10, -6, 36, 6, -36, 37, -37,
1513 -5, 38, 1, -38, -1, 3, 39, -39, -1, 40, 5, 1, -40, -3, 2, -11,
1514 -41, -2, 1, 11, -3, -4, 41, 3, 42, 4, -1, -43, -42, 43, 1, -44,
1515 45, -1, 44, -45, -7, 7, -46, 1, -12, 2, 1, -47, 46, 12, 47, 48,
1516 -2, -1, -48, 49, -1, -50, -49, 50, -6, -51, 51, 52, -13, 53, -4, 4,
1517 6, 13, -53, -52, -54, 55, 54, -55, -56, -2, 2, -8, 56, 1, -3, -1,
1518 2, 58, 3, 8, -2, 57, -58, -60, -59, -57, -3, 60, 59, -14, 3, 14}
1524 {1, 1, 0, 2, 2, 1, 1, 3, 3, 4, 4, 5, 5, 1, 1, 6,
1525 6, 2, 2, 7, 7, 8, 8, 1, 1, 3, 3, 9, 9, 10, 10, 1,
1526 1, 2, 2, 4, 4, 11, 0, 11, 12, 12, 13, 13, 1, 1, 5, 5,
1527 14, 14, 15, 16, 15, 16, 3, 3, 1, 6, 1, 6, 2, 2, 7, 7,
1528 8, 8, 17, 17, 1, 1, 4, 4, 18, 18, 2, 2, 1, 19, 1, 20,
1529 19, 20, 21, 21, 3, 3, 22, 22, 5, 5, 24, 1, 1, 23, 9, 23,
1530 24, 9, 2, 2, 10, 1, 1, 10, 6, 6, 25, 4, 4, 25, 7, 7,
1531 26, 8, 1, 8, 3, 1, 26, 3, 11, 11, 27, 27, 2, 28, 1, 2,
1532 28, 1, 12, 12, 5, 5, 29, 13, 13, 29, 32, 1, 1, 33, 31, 30,
1533 32, 4, 30, 33, 4, 31, 3, 14, 1, 1, 3, 34, 34, 2, 2, 14,
1534 6, 6, 35, 36, 35, 36, 1, 15, 1, 16, 16, 15, 7, 9, 7, 9,
1535 37, 8, 8, 37, 1, 1, 39, 2, 38, 39, 2, 40, 5, 38, 40, 5,
1536 3, 3, 4, 4, 10, 10, 1, 1, 1, 1, 41, 2, 41, 2, 6, 6,
1537 1, 1, 11, 42, 11, 43, 3, 42, 3, 17, 4, 43, 1, 17, 7, 1,
1538 8, 44, 4, 7, 44, 5, 8, 2, 5, 1, 2, 48, 45, 1, 12, 45,
1539 12, 48, 13, 13, 1, 9, 9, 46, 1, 46, 47, 47, 49, 18, 18, 49},
1542 { 1, -1, 0, 1, -1, 2, -2, 1, -1, 1, -1, 1, -1, 3, -3, 1,
1543 -1, -2, 2, 1, -1, 1, -1, 4, -4, -2, 2, 1, -1, 1, -1, 5,
1544 -5, -3, 3, 2, -2, 1, 0, -1, 1, -1, 1, -1, 6, -6, 2, -2,
1545 1, -1, 1, 1, -1, -1, -3, 3, 7, 2, -7, -2, -4, 4, 2, -2,
1546 2, -2, 1, -1, 8, -8, 3, -3, 1, -1, -5, 5, 9, 1, -9, 1,
1547 -1, -1, 1, -1, -4, 4, 1, -1, 3, -3, 1, -10, 10, 1, 2, -1,
1548 -1, -2, 6, -6, 2, 11, -11, -2, 3, -3, 1, -4, 4, -1, 3, -3,
1549 1, 3, 12, -3, -5, -12, -1, 5, 2, -2, 1, -1, -7, 1, 13, 7,
1550 -1, -13, 2, -2, 4, -4, 1, 2, -2, -1, 1, 14, -14, 1, 1, 1,
1551 -1, -5, -1, -1, 5, -1, -6, 2, -15, 15, 6, 1, -1, -8, 8, -2,
1552 -4, 4, 1, 1, -1, -1, 16, 2, -16, -2, 2, -2, 4, 3, -4, -3,
1553 -1, -4, 4, 1, -17, 17, -1, -9, 1, 1, 9, 1, -5, -1, -1, 5,
1554 -7, 7, 6, -6, 3, -3, 18, -18, 19, -19, 1, -10, -1, 10, -5, 5,
1555 20, -20, -3, 1, 3, 1, 8, -1, -8, 2, 7, -1, -21, -2, 5, 21,
1556 5, -1, -7, -5, 1, -6, -5, -11, 6, 22, 11, 1, 1, -22, -3, -1,
1557 3, -1, 3, -3, -23, 4, -4, 1, 23, -1, 1, -1, 1, -2, 2, -1}
1563 {1, 1, 1, 1, 0, 2, 2, 1, 1, 3, 3, 0, 1, 1, 2, 2,
1564 4, 4, 1, 1, 5, 5, 1, 1, 2, 2, 3, 3, 6, 6, 1, 1,
1565 7, 7, 8, 1, 8, 2, 2, 1, 4, 4, 1, 3, 1, 3, 9, 9,
1566 2, 2, 1, 5, 1, 5, 10, 10, 1, 1, 11, 11, 3, 6, 3, 4,
1567 4, 6, 2, 2, 1, 12, 1, 12, 7, 13, 7, 13, 1, 1, 8, 8,
1568 2, 2, 14, 14, 16, 15, 16, 5, 5, 1, 3, 15, 1, 3, 4, 4,
1569 1, 1, 17, 17, 2, 2, 6, 6, 1, 18, 1, 18, 22, 21, 22, 21,
1570 25, 24, 25, 19, 9, 20, 9, 23, 19, 24, 20, 3, 23, 7, 3, 1,
1571 1, 7, 28, 26, 29, 5, 28, 26, 5, 8, 29, 4, 8, 27, 2, 2,
1572 4, 27, 1, 1, 10, 36, 10, 33, 33, 36, 30, 1, 32, 32, 1, 30,
1573 6, 31, 31, 35, 3, 6, 11, 11, 3, 2, 35, 2, 34, 1, 34, 1,
1574 37, 37, 12, 7, 12, 5, 41, 5, 4, 7, 1, 8, 13, 4, 1, 41,
1575 13, 38, 8, 38, 9, 1, 40, 40, 9, 1, 39, 2, 2, 49, 39, 42,
1576 3, 3, 14, 16, 49, 14, 16, 42, 43, 43, 6, 6, 15, 1, 1, 15,
1577 44, 44, 1, 1, 50, 48, 4, 5, 4, 7, 5, 2, 10, 10, 48, 7,
1578 50, 45, 2, 1, 45, 8, 8, 1, 46, 46, 3, 47, 47, 3, 1, 1},
1581 { 1, -1, 2, -2, 0, 1, -1, 3, -3, 1, -1, 0, 4, -4, 2, -2,
1582 1, -1, 5, -5, 1, -1, 6, -6, 3, -3, 2, -2, 1, -1, 7, -7,
1583 1, -1, 1, 8, -1, 4, -4, -8, 2, -2, 9, 3, -9, -3, 1, -1,
1584 5, -5, 10, 2, -10, -2, 1, -1, 11, -11, 1, -1, -4, 2, 4, 3,
1585 -3, -2, 6, -6, 12, 1, -12, -1, 2, 1, -2, -1, 13, -13, 2, -2,
1586 7, -7, 1, -1, 1, 1, -1, 3, -3, 14, 5, -1, -14, -5, 4, -4,
1587 15, -15, 1, -1, 8, -8, -3, 3, 16, 1, -16, -1, 1, 1, -1, -1,
1588 1, 1, -1, 1, 2, 1, -2, 1, -1, -1, -1, 6, -1, 3, -6, 17,
1589 -17, -3, 1, 1, 1, 4, -1, -1, -4, 3, -1, 5, -3, -1, -9, 9,
1590 -5, 1, 18, -18, 2, 1, -2, 1, -1, -1, 1, 19, -1, 1, -19, -1,
1591 4, 1, -1, 1, 7, -4, -2, 2, -7, 10, -1, -10, 1, 20, -1, -20,
1592 1, -1, 2, 4, -2, 5, 1, -5, 6, -4, 21, 4, 2, -6, -21, -1,
1593 -2, 1, -4, -1, -3, 22, -1, 1, 3, -22, -1, 11, -11, 1, 1, 1,
1594 8, -8, 2, 2, -1, -2, -2, -1, 1, -1, -5, 5, 2, 23, -23, -2,
1595 1, -1, 24, -24, -1, -1, 7, 6, -7, 5, -6, 12, -3, 3, 1, -5,
1596 1, 1, -12, 25, -1, -5, 5, -25, -1, 1, 9, 1, -1, -9, 26, -26}