2 * common functions for Indeo Video Interactive codecs (Indeo4 and Indeo5)
4 * Copyright (c) 2009 Maxim Poliakovski
6 * This file is part of FFmpeg.
8 * FFmpeg is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU Lesser General Public
10 * License as published by the Free Software Foundation; either
11 * version 2.1 of the License, or (at your option) any later version.
13 * FFmpeg is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * Lesser General Public License for more details.
18 * You should have received a copy of the GNU Lesser General Public
19 * License along with FFmpeg; if not, write to the Free Software
20 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
25 * This file contains functions and data shared by both Indeo4 and
31 #include "libavutil/attributes.h"
32 #include "libavutil/imgutils.h"
33 #include "libavutil/timer.h"
35 #define BITSTREAM_READER_LE
44 * These are 2x8 predefined Huffman codebooks for coding macroblock/block
45 * signals. They are specified using "huffman descriptors" in order to
46 * avoid huge static tables. The decoding tables will be generated at
47 * startup from these descriptors.
49 /** static macroblock huffman tables */
50 static const IVIHuffDesc ivi_mb_huff_desc[8] = {
51 {8, {0, 4, 5, 4, 4, 4, 6, 6}},
52 {12, {0, 2, 2, 3, 3, 3, 3, 5, 3, 2, 2, 2}},
53 {12, {0, 2, 3, 4, 3, 3, 3, 3, 4, 3, 2, 2}},
54 {12, {0, 3, 4, 4, 3, 3, 3, 3, 3, 2, 2, 2}},
55 {13, {0, 4, 4, 3, 3, 3, 3, 2, 3, 3, 2, 1, 1}},
56 {9, {0, 4, 4, 4, 4, 3, 3, 3, 2}},
57 {10, {0, 4, 4, 4, 4, 3, 3, 2, 2, 2}},
58 {12, {0, 4, 4, 4, 3, 3, 2, 3, 2, 2, 2, 2}}
61 /** static block huffman tables */
62 static const IVIHuffDesc ivi_blk_huff_desc[8] = {
63 {10, {1, 2, 3, 4, 4, 7, 5, 5, 4, 1}},
64 {11, {2, 3, 4, 4, 4, 7, 5, 4, 3, 3, 2}},
65 {12, {2, 4, 5, 5, 5, 5, 6, 4, 4, 3, 1, 1}},
66 {13, {3, 3, 4, 4, 5, 6, 6, 4, 4, 3, 2, 1, 1}},
67 {11, {3, 4, 4, 5, 5, 5, 6, 5, 4, 2, 2}},
68 {13, {3, 4, 5, 5, 5, 5, 6, 4, 3, 3, 2, 1, 1}},
69 {13, {3, 4, 5, 5, 5, 6, 5, 4, 3, 3, 2, 1, 1}},
70 {9, {3, 4, 4, 5, 5, 5, 6, 5, 5}}
73 static VLC ivi_mb_vlc_tabs [8]; ///< static macroblock Huffman tables
74 static VLC ivi_blk_vlc_tabs[8]; ///< static block Huffman tables
76 typedef void (*ivi_mc_func) (int16_t *buf, const int16_t *ref_buf,
77 ptrdiff_t pitch, int mc_type);
78 typedef void (*ivi_mc_avg_func) (int16_t *buf, const int16_t *ref_buf1,
79 const int16_t *ref_buf2,
80 ptrdiff_t pitch, int mc_type, int mc_type2);
82 static int ivi_mc(IVIBandDesc *band, ivi_mc_func mc, ivi_mc_avg_func mc_avg,
83 int offs, int mv_x, int mv_y, int mv_x2, int mv_y2,
84 int mc_type, int mc_type2)
86 int ref_offs = offs + mv_y * band->pitch + mv_x;
87 int buf_size = band->pitch * band->aheight;
88 int min_size = band->pitch * (band->blk_size - 1) + band->blk_size;
89 int ref_size = (mc_type > 1) * band->pitch + (mc_type & 1);
92 av_assert0(offs >= 0 && ref_offs >= 0 && band->ref_buf);
93 av_assert0(buf_size - min_size >= offs);
94 av_assert0(buf_size - min_size - ref_size >= ref_offs);
98 mc(band->buf + offs, band->ref_buf + ref_offs, band->pitch, mc_type);
100 int ref_offs2 = offs + mv_y2 * band->pitch + mv_x2;
101 int ref_size2 = (mc_type2 > 1) * band->pitch + (mc_type2 & 1);
102 if (offs < 0 || ref_offs2 < 0 || !band->b_ref_buf)
103 return AVERROR_INVALIDDATA;
104 if (buf_size - min_size - ref_size2 < ref_offs2)
105 return AVERROR_INVALIDDATA;
108 mc(band->buf + offs, band->b_ref_buf + ref_offs2,
109 band->pitch, mc_type2);
111 mc_avg(band->buf + offs, band->ref_buf + ref_offs,
112 band->b_ref_buf + ref_offs2, band->pitch,
120 * Reverse "nbits" bits of the value "val" and return the result
121 * in the least significant bits.
123 static uint16_t inv_bits(uint16_t val, int nbits)
128 res = ff_reverse[val] >> (8 - nbits);
130 res = ((ff_reverse[val & 0xFF] << 8) +
131 (ff_reverse[val >> 8])) >> (16 - nbits);
137 * Generate a huffman codebook from the given descriptor
138 * and convert it into the FFmpeg VLC table.
140 * @param[in] cb pointer to codebook descriptor
141 * @param[out] vlc where to place the generated VLC table
142 * @param[in] flag flag: 1 - for static or 0 for dynamic tables
143 * @return result code: 0 - OK, -1 = error (invalid codebook descriptor)
145 static int ivi_create_huff_from_desc(const IVIHuffDesc *cb, VLC *vlc, int flag)
147 int pos, i, j, codes_per_row, prefix, not_last_row;
148 uint16_t codewords[256]; /* FIXME: move this temporal storage out? */
151 pos = 0; /* current position = 0 */
153 for (i = 0; i < cb->num_rows; i++) {
154 codes_per_row = 1 << cb->xbits[i];
155 not_last_row = (i != cb->num_rows - 1);
156 prefix = ((1 << i) - 1) << (cb->xbits[i] + not_last_row);
158 for (j = 0; j < codes_per_row; j++) {
159 if (pos >= 256) /* Some Indeo5 codebooks can have more than 256 */
160 break; /* elements, but only 256 codes are allowed! */
162 bits[pos] = i + cb->xbits[i] + not_last_row;
163 if (bits[pos] > IVI_VLC_BITS)
164 return AVERROR_INVALIDDATA; /* invalid descriptor */
166 codewords[pos] = inv_bits((prefix | j), bits[pos]);
174 /* number of codewords = pos */
175 return init_vlc(vlc, IVI_VLC_BITS, pos, bits, 1, 1, codewords, 2, 2,
176 (flag ? INIT_VLC_USE_NEW_STATIC : 0) | INIT_VLC_LE);
179 av_cold void ff_ivi_init_static_vlc(void)
182 static VLC_TYPE table_data[8192 * 16][2];
183 static int initialized_vlcs = 0;
185 if (initialized_vlcs)
187 for (i = 0; i < 8; i++) {
188 ivi_mb_vlc_tabs[i].table = table_data + i * 2 * 8192;
189 ivi_mb_vlc_tabs[i].table_allocated = 8192;
190 ivi_create_huff_from_desc(&ivi_mb_huff_desc[i],
191 &ivi_mb_vlc_tabs[i], 1);
192 ivi_blk_vlc_tabs[i].table = table_data + (i * 2 + 1) * 8192;
193 ivi_blk_vlc_tabs[i].table_allocated = 8192;
194 ivi_create_huff_from_desc(&ivi_blk_huff_desc[i],
195 &ivi_blk_vlc_tabs[i], 1);
197 initialized_vlcs = 1;
201 * Copy huffman codebook descriptors.
203 * @param[out] dst ptr to the destination descriptor
204 * @param[in] src ptr to the source descriptor
206 static void ivi_huff_desc_copy(IVIHuffDesc *dst, const IVIHuffDesc *src)
208 dst->num_rows = src->num_rows;
209 memcpy(dst->xbits, src->xbits, src->num_rows);
213 * Compare two huffman codebook descriptors.
215 * @param[in] desc1 ptr to the 1st descriptor to compare
216 * @param[in] desc2 ptr to the 2nd descriptor to compare
217 * @return comparison result: 0 - equal, 1 - not equal
219 static int ivi_huff_desc_cmp(const IVIHuffDesc *desc1,
220 const IVIHuffDesc *desc2)
222 return desc1->num_rows != desc2->num_rows ||
223 memcmp(desc1->xbits, desc2->xbits, desc1->num_rows);
226 int ff_ivi_dec_huff_desc(GetBitContext *gb, int desc_coded, int which_tab,
227 IVIHuffTab *huff_tab, AVCodecContext *avctx)
230 IVIHuffDesc new_huff;
233 /* select default table */
234 huff_tab->tab = (which_tab) ? &ivi_blk_vlc_tabs[7]
235 : &ivi_mb_vlc_tabs [7];
239 huff_tab->tab_sel = get_bits(gb, 3);
240 if (huff_tab->tab_sel == 7) {
241 /* custom huffman table (explicitly encoded) */
242 new_huff.num_rows = get_bits(gb, 4);
243 if (!new_huff.num_rows) {
244 av_log(avctx, AV_LOG_ERROR, "Empty custom Huffman table!\n");
245 return AVERROR_INVALIDDATA;
248 for (i = 0; i < new_huff.num_rows; i++)
249 new_huff.xbits[i] = get_bits(gb, 4);
251 /* Have we got the same custom table? Rebuild if not. */
252 if (ivi_huff_desc_cmp(&new_huff, &huff_tab->cust_desc) || !huff_tab->cust_tab.table) {
253 ivi_huff_desc_copy(&huff_tab->cust_desc, &new_huff);
255 if (huff_tab->cust_tab.table)
256 ff_free_vlc(&huff_tab->cust_tab);
257 result = ivi_create_huff_from_desc(&huff_tab->cust_desc,
258 &huff_tab->cust_tab, 0);
260 // reset faulty description
261 huff_tab->cust_desc.num_rows = 0;
262 av_log(avctx, AV_LOG_ERROR,
263 "Error while initializing custom vlc table!\n");
267 huff_tab->tab = &huff_tab->cust_tab;
269 /* select one of predefined tables */
270 huff_tab->tab = (which_tab) ? &ivi_blk_vlc_tabs[huff_tab->tab_sel]
271 : &ivi_mb_vlc_tabs [huff_tab->tab_sel];
278 * Free planes, bands and macroblocks buffers.
280 * @param[in] planes pointer to the array of the plane descriptors
282 static av_cold void ivi_free_buffers(IVIPlaneDesc *planes)
286 for (p = 0; p < 3; p++) {
288 for (b = 0; b < planes[p].num_bands; b++) {
289 av_freep(&planes[p].bands[b].bufs[0]);
290 av_freep(&planes[p].bands[b].bufs[1]);
291 av_freep(&planes[p].bands[b].bufs[2]);
292 av_freep(&planes[p].bands[b].bufs[3]);
294 if (planes[p].bands[b].blk_vlc.cust_tab.table)
295 ff_free_vlc(&planes[p].bands[b].blk_vlc.cust_tab);
296 for (t = 0; t < planes[p].bands[b].num_tiles; t++)
297 av_freep(&planes[p].bands[b].tiles[t].mbs);
298 av_freep(&planes[p].bands[b].tiles);
300 av_freep(&planes[p].bands);
301 planes[p].num_bands = 0;
305 av_cold int ff_ivi_init_planes(AVCodecContext *avctx, IVIPlaneDesc *planes, const IVIPicConfig *cfg,
309 uint32_t b_width, b_height, align_fac, width_aligned,
310 height_aligned, buf_size;
313 ivi_free_buffers(planes);
315 if (av_image_check_size2(cfg->pic_width, cfg->pic_height, avctx->max_pixels, AV_PIX_FMT_YUV410P, 0, avctx) < 0 ||
316 cfg->luma_bands < 1 || cfg->chroma_bands < 1)
317 return AVERROR_INVALIDDATA;
319 /* fill in the descriptor of the luminance plane */
320 planes[0].width = cfg->pic_width;
321 planes[0].height = cfg->pic_height;
322 planes[0].num_bands = cfg->luma_bands;
324 /* fill in the descriptors of the chrominance planes */
325 planes[1].width = planes[2].width = (cfg->pic_width + 3) >> 2;
326 planes[1].height = planes[2].height = (cfg->pic_height + 3) >> 2;
327 planes[1].num_bands = planes[2].num_bands = cfg->chroma_bands;
329 for (p = 0; p < 3; p++) {
330 planes[p].bands = av_mallocz_array(planes[p].num_bands, sizeof(IVIBandDesc));
331 if (!planes[p].bands)
332 return AVERROR(ENOMEM);
334 /* select band dimensions: if there is only one band then it
335 * has the full size, if there are several bands each of them
336 * has only half size */
337 b_width = planes[p].num_bands == 1 ? planes[p].width
338 : (planes[p].width + 1) >> 1;
339 b_height = planes[p].num_bands == 1 ? planes[p].height
340 : (planes[p].height + 1) >> 1;
342 /* luma band buffers will be aligned on 16x16 (max macroblock size) */
343 /* chroma band buffers will be aligned on 8x8 (max macroblock size) */
344 align_fac = p ? 8 : 16;
345 width_aligned = FFALIGN(b_width , align_fac);
346 height_aligned = FFALIGN(b_height, align_fac);
347 buf_size = width_aligned * height_aligned * sizeof(int16_t);
349 for (b = 0; b < planes[p].num_bands; b++) {
350 band = &planes[p].bands[b]; /* select appropriate plane/band */
353 band->width = b_width;
354 band->height = b_height;
355 band->pitch = width_aligned;
356 band->aheight = height_aligned;
357 band->bufs[0] = av_mallocz(buf_size);
358 band->bufs[1] = av_mallocz(buf_size);
359 band->bufsize = buf_size/2;
360 if (!band->bufs[0] || !band->bufs[1])
361 return AVERROR(ENOMEM);
363 /* allocate the 3rd band buffer for scalability mode */
364 if (cfg->luma_bands > 1) {
365 band->bufs[2] = av_mallocz(buf_size);
367 return AVERROR(ENOMEM);
370 band->bufs[3] = av_mallocz(buf_size);
372 return AVERROR(ENOMEM);
374 /* reset custom vlc */
375 planes[p].bands[0].blk_vlc.cust_desc.num_rows = 0;
382 static int ivi_init_tiles(IVIBandDesc *band, IVITile *ref_tile,
383 int p, int b, int t_height, int t_width)
386 IVITile *tile = band->tiles;
388 for (y = 0; y < band->height; y += t_height) {
389 for (x = 0; x < band->width; x += t_width) {
392 tile->mb_size = band->mb_size;
393 tile->width = FFMIN(band->width - x, t_width);
394 tile->height = FFMIN(band->height - y, t_height);
395 tile->is_empty = tile->data_size = 0;
396 /* calculate number of macroblocks */
397 tile->num_MBs = IVI_MBs_PER_TILE(tile->width, tile->height,
400 av_freep(&tile->mbs);
401 tile->mbs = av_mallocz_array(tile->num_MBs, sizeof(IVIMbInfo));
403 return AVERROR(ENOMEM);
407 if (tile->num_MBs != ref_tile->num_MBs) {
408 av_log(NULL, AV_LOG_DEBUG, "ref_tile mismatch\n");
409 return AVERROR_INVALIDDATA;
411 tile->ref_mbs = ref_tile->mbs;
421 av_cold int ff_ivi_init_tiles(IVIPlaneDesc *planes,
422 int tile_width, int tile_height)
424 int p, b, x_tiles, y_tiles, t_width, t_height, ret;
427 for (p = 0; p < 3; p++) {
428 t_width = !p ? tile_width : (tile_width + 3) >> 2;
429 t_height = !p ? tile_height : (tile_height + 3) >> 2;
431 if (!p && planes[0].num_bands == 4) {
435 if(t_width<=0 || t_height<=0)
436 return AVERROR(EINVAL);
438 for (b = 0; b < planes[p].num_bands; b++) {
439 band = &planes[p].bands[b];
440 x_tiles = IVI_NUM_TILES(band->width, t_width);
441 y_tiles = IVI_NUM_TILES(band->height, t_height);
442 band->num_tiles = x_tiles * y_tiles;
444 av_freep(&band->tiles);
445 band->tiles = av_mallocz_array(band->num_tiles, sizeof(IVITile));
447 return AVERROR(ENOMEM);
449 /* use the first luma band as reference for motion vectors
451 ret = ivi_init_tiles(band, planes[0].bands[0].tiles,
452 p, b, t_height, t_width);
462 * Decode size of the tile data.
463 * The size is stored as a variable-length field having the following format:
464 * if (tile_data_size < 255) than this field is only one byte long
465 * if (tile_data_size >= 255) than this field four is byte long: 0xFF X1 X2 X3
466 * where X1-X3 is size of the tile data
468 * @param[in,out] gb the GetBit context
469 * @return size of the tile data in bytes
471 static int ivi_dec_tile_data_size(GetBitContext *gb)
477 len = get_bits(gb, 8);
479 len = get_bits_long(gb, 24);
482 /* align the bitstream reader on the byte boundary */
488 static int ivi_dc_transform(IVIBandDesc *band, int *prev_dc, int buf_offs,
491 int buf_size = band->pitch * band->aheight - buf_offs;
492 int min_size = (blk_size - 1) * band->pitch + blk_size;
494 if (min_size > buf_size)
495 return AVERROR_INVALIDDATA;
497 band->dc_transform(prev_dc, band->buf + buf_offs,
498 band->pitch, blk_size);
503 static int ivi_decode_coded_blocks(GetBitContext *gb, IVIBandDesc *band,
504 ivi_mc_func mc, ivi_mc_avg_func mc_avg,
506 int mv_x2, int mv_y2,
507 int *prev_dc, int is_intra,
508 int mc_type, int mc_type2,
509 uint32_t quant, int offs,
510 AVCodecContext *avctx)
512 const uint16_t *base_tab = is_intra ? band->intra_base : band->inter_base;
513 RVMapDesc *rvmap = band->rv_map;
514 uint8_t col_flags[8];
516 uint32_t sym = 0, lo, hi, q;
518 int blk_size = band->blk_size;
519 int num_coeffs = blk_size * blk_size;
520 int col_mask = blk_size - 1;
522 int min_size = band->pitch * (band->transform_size - 1) +
523 band->transform_size;
524 int buf_size = band->pitch * band->aheight - offs;
526 if (min_size > buf_size)
527 return AVERROR_INVALIDDATA;
530 av_log(avctx, AV_LOG_ERROR, "Scan pattern is not set.\n");
531 return AVERROR_INVALIDDATA;
534 /* zero transform vector */
535 memset(trvec, 0, num_coeffs * sizeof(trvec[0]));
536 /* zero column flags */
537 memset(col_flags, 0, sizeof(col_flags));
538 while (scan_pos <= num_coeffs) {
539 sym = get_vlc2(gb, band->blk_vlc.tab->table,
541 if (sym == rvmap->eob_sym)
542 break; /* End of block */
544 /* Escape - run/val explicitly coded using 3 vlc codes */
545 if (sym == rvmap->esc_sym) {
546 run = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1) + 1;
547 lo = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
548 hi = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
549 /* merge them and convert into signed val */
550 val = IVI_TOSIGNED((hi << 6) | lo);
553 av_log(avctx, AV_LOG_ERROR, "Invalid sym encountered: %"PRIu32".\n", sym);
554 return AVERROR_INVALIDDATA;
556 run = rvmap->runtab[sym];
557 val = rvmap->valtab[sym];
560 /* de-zigzag and dequantize */
562 if (scan_pos >= num_coeffs || scan_pos < 0)
564 pos = band->scan[scan_pos];
567 ff_dlog(avctx, "Val = 0 encountered!\n");
569 q = (base_tab[pos] * quant) >> 9;
571 val = val * q + FFSIGN(val) * (((q ^ 1) - 1) >> 1);
573 /* track columns containing non-zero coeffs */
574 col_flags[pos & col_mask] |= !!val;
577 if (scan_pos < 0 || scan_pos >= num_coeffs && sym != rvmap->eob_sym)
578 return AVERROR_INVALIDDATA; /* corrupt block data */
580 /* undoing DC coeff prediction for intra-blocks */
581 if (is_intra && band->is_2d_trans) {
582 *prev_dc += trvec[0];
584 col_flags[0] |= !!*prev_dc;
587 if(band->transform_size > band->blk_size){
588 av_log(NULL, AV_LOG_ERROR, "Too large transform\n");
589 return AVERROR_INVALIDDATA;
592 /* apply inverse transform */
593 band->inv_transform(trvec, band->buf + offs,
594 band->pitch, col_flags);
596 /* apply motion compensation */
598 return ivi_mc(band, mc, mc_avg, offs, mv_x, mv_y, mv_x2, mv_y2,
605 * extract huffman-coded transform coefficients from the bitstream,
606 * dequantize them, apply inverse transform and motion compensation
607 * in order to reconstruct the picture.
609 * @param[in,out] gb the GetBit context
610 * @param[in] band pointer to the band descriptor
611 * @param[in] tile pointer to the tile descriptor
612 * @return result code: 0 - OK, -1 = error (corrupted blocks data)
614 static int ivi_decode_blocks(GetBitContext *gb, IVIBandDesc *band,
615 IVITile *tile, AVCodecContext *avctx)
617 int mbn, blk, num_blocks, blk_size, ret, is_intra;
618 int mc_type = 0, mc_type2 = -1;
619 int mv_x = 0, mv_y = 0, mv_x2 = 0, mv_y2 = 0;
621 uint32_t cbp, quant, buf_offs;
623 ivi_mc_func mc_with_delta_func, mc_no_delta_func;
624 ivi_mc_avg_func mc_avg_with_delta_func, mc_avg_no_delta_func;
625 const uint8_t *scale_tab;
627 /* init intra prediction for the DC coefficient */
629 blk_size = band->blk_size;
630 /* number of blocks per mb */
631 num_blocks = (band->mb_size != blk_size) ? 4 : 1;
633 mc_with_delta_func = ff_ivi_mc_8x8_delta;
634 mc_no_delta_func = ff_ivi_mc_8x8_no_delta;
635 mc_avg_with_delta_func = ff_ivi_mc_avg_8x8_delta;
636 mc_avg_no_delta_func = ff_ivi_mc_avg_8x8_no_delta;
638 mc_with_delta_func = ff_ivi_mc_4x4_delta;
639 mc_no_delta_func = ff_ivi_mc_4x4_no_delta;
640 mc_avg_with_delta_func = ff_ivi_mc_avg_4x4_delta;
641 mc_avg_no_delta_func = ff_ivi_mc_avg_4x4_no_delta;
644 for (mbn = 0, mb = tile->mbs; mbn < tile->num_MBs; mb++, mbn++) {
645 is_intra = !mb->type;
647 buf_offs = mb->buf_offs;
649 quant = band->glob_quant + mb->q_delta;
650 if (avctx->codec_id == AV_CODEC_ID_INDEO4)
651 quant = av_clip_uintp2(quant, 5);
653 quant = av_clip(quant, 0, 23);
655 scale_tab = is_intra ? band->intra_scale : band->inter_scale;
657 quant = scale_tab[quant];
664 if (band->is_halfpel) {
665 mc_type = ((mv_y & 1) << 1) | (mv_x & 1);
666 mc_type2 = ((mv_y2 & 1) << 1) | (mv_x2 & 1);
670 mv_y2 >>= 1; /* convert halfpel vectors into fullpel ones */
674 if (mb->type != 2 && mb->type != 3)
677 int dmv_x, dmv_y, cx, cy;
679 dmv_x = mb->mv_x >> band->is_halfpel;
680 dmv_y = mb->mv_y >> band->is_halfpel;
681 cx = mb->mv_x & band->is_halfpel;
682 cy = mb->mv_y & band->is_halfpel;
684 if (mb->xpos + dmv_x < 0 ||
685 mb->xpos + dmv_x + band->mb_size + cx > band->pitch ||
686 mb->ypos + dmv_y < 0 ||
687 mb->ypos + dmv_y + band->mb_size + cy > band->aheight) {
688 return AVERROR_INVALIDDATA;
691 if (mb->type == 2 || mb->type == 3) {
692 int dmv_x, dmv_y, cx, cy;
694 dmv_x = mb->b_mv_x >> band->is_halfpel;
695 dmv_y = mb->b_mv_y >> band->is_halfpel;
696 cx = mb->b_mv_x & band->is_halfpel;
697 cy = mb->b_mv_y & band->is_halfpel;
699 if (mb->xpos + dmv_x < 0 ||
700 mb->xpos + dmv_x + band->mb_size + cx > band->pitch ||
701 mb->ypos + dmv_y < 0 ||
702 mb->ypos + dmv_y + band->mb_size + cy > band->aheight) {
703 return AVERROR_INVALIDDATA;
708 for (blk = 0; blk < num_blocks; blk++) {
709 /* adjust block position in the buffer according to its number */
711 buf_offs += blk_size;
712 } else if (blk == 2) {
713 buf_offs -= blk_size;
714 buf_offs += blk_size * band->pitch;
717 if (cbp & 1) { /* block coded ? */
718 ret = ivi_decode_coded_blocks(gb, band, mc_with_delta_func,
719 mc_avg_with_delta_func,
720 mv_x, mv_y, mv_x2, mv_y2,
722 mc_type, mc_type2, quant,
727 /* block not coded */
728 /* for intra blocks apply the dc slant transform */
729 /* for inter - perform the motion compensation without delta */
731 ret = ivi_dc_transform(band, &prev_dc, buf_offs, blk_size);
735 ret = ivi_mc(band, mc_no_delta_func, mc_avg_no_delta_func,
736 buf_offs, mv_x, mv_y, mv_x2, mv_y2,
753 * Handle empty tiles by performing data copying and motion
754 * compensation respectively.
756 * @param[in] avctx ptr to the AVCodecContext
757 * @param[in] band pointer to the band descriptor
758 * @param[in] tile pointer to the tile descriptor
759 * @param[in] mv_scale scaling factor for motion vectors
761 static int ivi_process_empty_tile(AVCodecContext *avctx, IVIBandDesc *band,
762 IVITile *tile, int32_t mv_scale)
764 int x, y, need_mc, mbn, blk, num_blocks, mv_x, mv_y, mc_type;
765 int offs, mb_offset, row_offset, ret;
766 IVIMbInfo *mb, *ref_mb;
769 ivi_mc_func mc_no_delta_func;
771 if (tile->num_MBs != IVI_MBs_PER_TILE(tile->width, tile->height, band->mb_size)) {
772 av_log(avctx, AV_LOG_ERROR, "Allocated tile size %d mismatches "
773 "parameters %d in ivi_process_empty_tile()\n",
774 tile->num_MBs, IVI_MBs_PER_TILE(tile->width, tile->height, band->mb_size));
775 return AVERROR_INVALIDDATA;
778 offs = tile->ypos * band->pitch + tile->xpos;
780 ref_mb = tile->ref_mbs;
781 row_offset = band->mb_size * band->pitch;
782 need_mc = 0; /* reset the mc tracking flag */
784 for (y = tile->ypos; y < (tile->ypos + tile->height); y += band->mb_size) {
787 for (x = tile->xpos; x < (tile->xpos + tile->width); x += band->mb_size) {
790 mb->buf_offs = mb_offset;
792 mb->type = 1; /* set the macroblocks type = INTER */
793 mb->cbp = 0; /* all blocks are empty */
795 if (!band->qdelta_present && !band->plane && !band->band_num) {
796 mb->q_delta = band->glob_quant;
801 if (band->inherit_qdelta && ref_mb)
802 mb->q_delta = ref_mb->q_delta;
804 if (band->inherit_mv && ref_mb) {
805 /* motion vector inheritance */
807 mb->mv_x = ivi_scale_mv(ref_mb->mv_x, mv_scale);
808 mb->mv_y = ivi_scale_mv(ref_mb->mv_y, mv_scale);
810 mb->mv_x = ref_mb->mv_x;
811 mb->mv_y = ref_mb->mv_y;
813 need_mc |= mb->mv_x || mb->mv_y; /* tracking non-zero motion vectors */
815 int dmv_x, dmv_y, cx, cy;
817 dmv_x = mb->mv_x >> band->is_halfpel;
818 dmv_y = mb->mv_y >> band->is_halfpel;
819 cx = mb->mv_x & band->is_halfpel;
820 cy = mb->mv_y & band->is_halfpel;
822 if ( mb->xpos + dmv_x < 0
823 || mb->xpos + dmv_x + band->mb_size + cx > band->pitch
824 || mb->ypos + dmv_y < 0
825 || mb->ypos + dmv_y + band->mb_size + cy > band->aheight) {
826 av_log(avctx, AV_LOG_ERROR, "MV out of bounds\n");
827 return AVERROR_INVALIDDATA;
835 mb_offset += band->mb_size;
840 if (band->inherit_mv && need_mc) { /* apply motion compensation if there is at least one non-zero motion vector */
841 num_blocks = (band->mb_size != band->blk_size) ? 4 : 1; /* number of blocks per mb */
842 mc_no_delta_func = (band->blk_size == 8) ? ff_ivi_mc_8x8_no_delta
843 : ff_ivi_mc_4x4_no_delta;
845 for (mbn = 0, mb = tile->mbs; mbn < tile->num_MBs; mb++, mbn++) {
848 if (!band->is_halfpel) {
849 mc_type = 0; /* we have only fullpel vectors */
851 mc_type = ((mv_y & 1) << 1) | (mv_x & 1);
853 mv_y >>= 1; /* convert halfpel vectors into fullpel ones */
856 for (blk = 0; blk < num_blocks; blk++) {
857 /* adjust block position in the buffer according with its number */
858 offs = mb->buf_offs + band->blk_size * ((blk & 1) + !!(blk & 2) * band->pitch);
859 ret = ivi_mc(band, mc_no_delta_func, 0, offs,
860 mv_x, mv_y, 0, 0, mc_type, -1);
866 /* copy data from the reference tile into the current one */
867 src = band->ref_buf + tile->ypos * band->pitch + tile->xpos;
868 dst = band->buf + tile->ypos * band->pitch + tile->xpos;
869 for (y = 0; y < tile->height; y++) {
870 memcpy(dst, src, tile->width*sizeof(band->buf[0]));
881 static uint16_t ivi_calc_band_checksum(IVIBandDesc *band)
884 int16_t *src, checksum;
889 for (y = 0; y < band->height; src += band->pitch, y++)
890 for (x = 0; x < band->width; x++)
898 * Convert and output the current plane.
899 * This conversion is done by adding back the bias value of 128
900 * (subtracted in the encoder) and clipping the result.
902 * @param[in] plane pointer to the descriptor of the plane being processed
903 * @param[out] dst pointer to the buffer receiving converted pixels
904 * @param[in] dst_pitch pitch for moving to the next y line
906 static void ivi_output_plane(IVIPlaneDesc *plane, uint8_t *dst, ptrdiff_t dst_pitch)
909 const int16_t *src = plane->bands[0].buf;
910 ptrdiff_t pitch = plane->bands[0].pitch;
915 for (y = 0; y < plane->height; y++) {
917 int w = plane->width;
918 for (x = 0; x < w; x++) {
919 int t = src[x] + 128;
924 for (x = 0; x < w; x++)
925 dst[x] = av_clip_uint8(src[x] + 128);
932 * Decode an Indeo 4 or 5 band.
934 * @param[in,out] ctx ptr to the decoder context
935 * @param[in,out] band ptr to the band descriptor
936 * @param[in] avctx ptr to the AVCodecContext
937 * @return result code: 0 = OK, -1 = error
939 static int decode_band(IVI45DecContext *ctx,
940 IVIBandDesc *band, AVCodecContext *avctx)
942 int result, i, t, idx1, idx2, pos;
945 band->buf = band->bufs[ctx->dst_buf];
947 av_log(avctx, AV_LOG_ERROR, "Band buffer points to no data!\n");
948 return AVERROR_INVALIDDATA;
950 if (ctx->is_indeo4 && ctx->frame_type == IVI4_FRAMETYPE_BIDIR) {
951 band->ref_buf = band->bufs[ctx->b_ref_buf];
952 band->b_ref_buf = band->bufs[ctx->ref_buf];
954 band->ref_buf = band->bufs[ctx->ref_buf];
957 band->data_ptr = ctx->frame_data + (get_bits_count(&ctx->gb) >> 3);
959 result = ctx->decode_band_hdr(ctx, band, avctx);
961 av_log(avctx, AV_LOG_ERROR, "Error while decoding band header: %d\n",
966 if (band->is_empty) {
967 av_log(avctx, AV_LOG_ERROR, "Empty band encountered!\n");
968 return AVERROR_INVALIDDATA;
971 band->rv_map = &ctx->rvmap_tabs[band->rvmap_sel];
973 /* apply corrections to the selected rvmap table if present */
974 for (i = 0; i < band->num_corr; i++) {
975 idx1 = band->corr[i * 2];
976 idx2 = band->corr[i * 2 + 1];
977 FFSWAP(uint8_t, band->rv_map->runtab[idx1], band->rv_map->runtab[idx2]);
978 FFSWAP(int16_t, band->rv_map->valtab[idx1], band->rv_map->valtab[idx2]);
979 if (idx1 == band->rv_map->eob_sym || idx2 == band->rv_map->eob_sym)
980 band->rv_map->eob_sym ^= idx1 ^ idx2;
981 if (idx1 == band->rv_map->esc_sym || idx2 == band->rv_map->esc_sym)
982 band->rv_map->esc_sym ^= idx1 ^ idx2;
985 pos = get_bits_count(&ctx->gb);
987 for (t = 0; t < band->num_tiles; t++) {
988 tile = &band->tiles[t];
990 if (tile->mb_size != band->mb_size) {
991 av_log(avctx, AV_LOG_ERROR, "MB sizes mismatch: %d vs. %d\n",
992 band->mb_size, tile->mb_size);
993 return AVERROR_INVALIDDATA;
995 tile->is_empty = get_bits1(&ctx->gb);
996 if (tile->is_empty) {
997 result = ivi_process_empty_tile(avctx, band, tile,
998 (ctx->planes[0].bands[0].mb_size >> 3) - (band->mb_size >> 3));
1001 ff_dlog(avctx, "Empty tile encountered!\n");
1003 tile->data_size = ivi_dec_tile_data_size(&ctx->gb);
1004 if (!tile->data_size) {
1005 av_log(avctx, AV_LOG_ERROR, "Tile data size is zero!\n");
1006 result = AVERROR_INVALIDDATA;
1010 result = ctx->decode_mb_info(ctx, band, tile, avctx);
1014 result = ivi_decode_blocks(&ctx->gb, band, tile, avctx);
1016 av_log(avctx, AV_LOG_ERROR,
1017 "Corrupted tile data encountered!\n");
1021 if (((get_bits_count(&ctx->gb) - pos) >> 3) != tile->data_size) {
1022 av_log(avctx, AV_LOG_ERROR,
1023 "Tile data_size mismatch!\n");
1024 result = AVERROR_INVALIDDATA;
1028 pos += tile->data_size << 3; // skip to next tile
1032 /* restore the selected rvmap table by applying its corrections in
1034 for (i = band->num_corr-1; i >= 0; i--) {
1035 idx1 = band->corr[i*2];
1036 idx2 = band->corr[i*2+1];
1037 FFSWAP(uint8_t, band->rv_map->runtab[idx1], band->rv_map->runtab[idx2]);
1038 FFSWAP(int16_t, band->rv_map->valtab[idx1], band->rv_map->valtab[idx2]);
1039 if (idx1 == band->rv_map->eob_sym || idx2 == band->rv_map->eob_sym)
1040 band->rv_map->eob_sym ^= idx1 ^ idx2;
1041 if (idx1 == band->rv_map->esc_sym || idx2 == band->rv_map->esc_sym)
1042 band->rv_map->esc_sym ^= idx1 ^ idx2;
1046 if (band->checksum_present) {
1047 uint16_t chksum = ivi_calc_band_checksum(band);
1048 if (chksum != band->checksum) {
1049 av_log(avctx, AV_LOG_ERROR,
1050 "Band checksum mismatch! Plane %d, band %d, "
1051 "received: %"PRIx32", calculated: %"PRIx16"\n",
1052 band->plane, band->band_num, band->checksum, chksum);
1057 align_get_bits(&ctx->gb);
1062 int ff_ivi_decode_frame(AVCodecContext *avctx, void *data, int *got_frame,
1065 IVI45DecContext *ctx = avctx->priv_data;
1066 const uint8_t *buf = avpkt->data;
1067 AVFrame *frame = data;
1068 int buf_size = avpkt->size;
1071 result = init_get_bits8(&ctx->gb, buf, buf_size);
1074 ctx->frame_data = buf;
1075 ctx->frame_size = buf_size;
1077 result = ctx->decode_pic_hdr(ctx, avctx);
1079 av_log(avctx, AV_LOG_ERROR,
1080 "Error while decoding picture header: %d\n", result);
1083 if (ctx->gop_invalid)
1084 return AVERROR_INVALIDDATA;
1086 if (ctx->is_indeo4 && ctx->frame_type == IVI4_FRAMETYPE_NULL_LAST) {
1087 if (ctx->got_p_frame) {
1088 av_frame_move_ref(data, ctx->p_frame);
1090 ctx->got_p_frame = 0;
1097 if (ctx->gop_flags & IVI5_IS_PROTECTED) {
1098 avpriv_report_missing_feature(avctx, "Password-protected clip");
1099 return AVERROR_PATCHWELCOME;
1102 if (!ctx->planes[0].bands) {
1103 av_log(avctx, AV_LOG_ERROR, "Color planes not initialized yet\n");
1104 return AVERROR_INVALIDDATA;
1107 ctx->switch_buffers(ctx);
1111 if (ctx->is_nonnull_frame(ctx)) {
1112 ctx->buf_invalid[ctx->dst_buf] = 1;
1113 for (p = 0; p < 3; p++) {
1114 for (b = 0; b < ctx->planes[p].num_bands; b++) {
1115 result = decode_band(ctx, &ctx->planes[p].bands[b], avctx);
1117 av_log(avctx, AV_LOG_ERROR,
1118 "Error while decoding band: %d, plane: %d\n", b, p);
1123 ctx->buf_invalid[ctx->dst_buf] = 0;
1125 if (ctx->is_scalable)
1126 return AVERROR_INVALIDDATA;
1128 for (p = 0; p < 3; p++) {
1129 if (!ctx->planes[p].bands[0].buf)
1130 return AVERROR_INVALIDDATA;
1133 if (ctx->buf_invalid[ctx->dst_buf])
1136 //STOP_TIMER("decode_planes"); }
1138 if (!ctx->is_nonnull_frame(ctx))
1141 result = ff_set_dimensions(avctx, ctx->planes[0].width, ctx->planes[0].height);
1145 if ((result = ff_get_buffer(avctx, frame, 0)) < 0)
1148 if (ctx->is_scalable) {
1150 ff_ivi_recompose_haar(&ctx->planes[0], frame->data[0], frame->linesize[0]);
1152 ff_ivi_recompose53 (&ctx->planes[0], frame->data[0], frame->linesize[0]);
1154 ivi_output_plane(&ctx->planes[0], frame->data[0], frame->linesize[0]);
1157 ivi_output_plane(&ctx->planes[2], frame->data[1], frame->linesize[1]);
1158 ivi_output_plane(&ctx->planes[1], frame->data[2], frame->linesize[2]);
1162 /* If the bidirectional mode is enabled, next I and the following P
1163 * frame will be sent together. Unfortunately the approach below seems
1164 * to be the only way to handle the B-frames mode.
1165 * That's exactly the same Intel decoders do.
1167 if (ctx->is_indeo4 && ctx->frame_type == IVI4_FRAMETYPE_INTRA) {
1170 // skip version string
1171 while (get_bits(&ctx->gb, 8)) {
1172 if (get_bits_left(&ctx->gb) < 8)
1173 return AVERROR_INVALIDDATA;
1175 left = get_bits_count(&ctx->gb) & 0x18;
1176 skip_bits_long(&ctx->gb, 64 - left);
1177 if (get_bits_left(&ctx->gb) > 18 &&
1178 show_bits_long(&ctx->gb, 21) == 0xBFFF8) { // syncheader + inter type
1180 pkt.data = avpkt->data + (get_bits_count(&ctx->gb) >> 3);
1181 pkt.size = get_bits_left(&ctx->gb) >> 3;
1182 ff_ivi_decode_frame(avctx, ctx->p_frame, &ctx->got_p_frame, &pkt);
1186 if (ctx->show_indeo4_info) {
1187 if (ctx->is_scalable)
1188 av_log(avctx, AV_LOG_DEBUG, "This video uses scalability mode\n");
1189 if (ctx->uses_tiling)
1190 av_log(avctx, AV_LOG_DEBUG, "This video uses local decoding\n");
1191 if (ctx->has_b_frames)
1192 av_log(avctx, AV_LOG_DEBUG, "This video contains B-frames\n");
1193 if (ctx->has_transp)
1194 av_log(avctx, AV_LOG_DEBUG, "Transparency mode is enabled\n");
1196 av_log(avctx, AV_LOG_DEBUG, "This video uses Haar transform\n");
1197 if (ctx->uses_fullpel)
1198 av_log(avctx, AV_LOG_DEBUG, "This video uses fullpel motion vectors\n");
1199 ctx->show_indeo4_info = 0;
1206 * Close Indeo5 decoder and clean up its context.
1208 av_cold int ff_ivi_decode_close(AVCodecContext *avctx)
1210 IVI45DecContext *ctx = avctx->priv_data;
1212 ivi_free_buffers(&ctx->planes[0]);
1214 if (ctx->mb_vlc.cust_tab.table)
1215 ff_free_vlc(&ctx->mb_vlc.cust_tab);
1217 if (ctx->blk_vlc.cust_tab.table)
1218 ff_free_vlc(&ctx->blk_vlc.cust_tab);
1220 av_frame_free(&ctx->p_frame);
1227 * Scan patterns shared between indeo4 and indeo5
1229 const uint8_t ff_ivi_vertical_scan_8x8[64] = {
1230 0, 8, 16, 24, 32, 40, 48, 56,
1231 1, 9, 17, 25, 33, 41, 49, 57,
1232 2, 10, 18, 26, 34, 42, 50, 58,
1233 3, 11, 19, 27, 35, 43, 51, 59,
1234 4, 12, 20, 28, 36, 44, 52, 60,
1235 5, 13, 21, 29, 37, 45, 53, 61,
1236 6, 14, 22, 30, 38, 46, 54, 62,
1237 7, 15, 23, 31, 39, 47, 55, 63
1240 const uint8_t ff_ivi_horizontal_scan_8x8[64] = {
1241 0, 1, 2, 3, 4, 5, 6, 7,
1242 8, 9, 10, 11, 12, 13, 14, 15,
1243 16, 17, 18, 19, 20, 21, 22, 23,
1244 24, 25, 26, 27, 28, 29, 30, 31,
1245 32, 33, 34, 35, 36, 37, 38, 39,
1246 40, 41, 42, 43, 44, 45, 46, 47,
1247 48, 49, 50, 51, 52, 53, 54, 55,
1248 56, 57, 58, 59, 60, 61, 62, 63
1251 const uint8_t ff_ivi_direct_scan_4x4[16] = {
1252 0, 1, 4, 8, 5, 2, 3, 6, 9, 12, 13, 10, 7, 11, 14, 15
1257 * Run-value (RLE) tables.
1259 const RVMapDesc ff_ivi_rvmap_tabs[9] = {
1264 {1, 1, 0, 1, 1, 0, 1, 1, 2, 2, 1, 1, 1, 1, 3, 3,
1265 1, 1, 2, 2, 1, 1, 4, 4, 1, 1, 1, 1, 2, 2, 5, 5,
1266 1, 1, 3, 3, 1, 1, 6, 6, 1, 2, 1, 2, 7, 7, 1, 1,
1267 8, 8, 1, 1, 4, 2, 1, 4, 2, 1, 3, 3, 1, 1, 1, 9,
1268 9, 1, 2, 1, 2, 1, 5, 5, 1, 1, 10, 10, 1, 1, 3, 3,
1269 2, 2, 1, 1, 11, 11, 6, 4, 4, 1, 6, 1, 2, 1, 2, 12,
1270 8, 1, 12, 7, 8, 7, 1, 16, 1, 16, 1, 3, 3, 13, 1, 13,
1271 2, 2, 1, 15, 1, 5, 14, 15, 1, 5, 14, 1, 17, 8, 17, 8,
1272 1, 4, 4, 2, 2, 1, 25, 25, 24, 24, 1, 3, 1, 3, 1, 8,
1273 6, 7, 6, 1, 18, 8, 18, 1, 7, 23, 2, 2, 23, 1, 1, 21,
1274 22, 9, 9, 22, 19, 1, 21, 5, 19, 5, 1, 33, 20, 33, 20, 8,
1275 4, 4, 1, 32, 2, 2, 8, 3, 32, 26, 3, 1, 7, 7, 26, 6,
1276 1, 6, 1, 1, 16, 1, 10, 1, 10, 2, 16, 29, 28, 2, 29, 28,
1277 1, 27, 5, 8, 5, 27, 1, 8, 3, 7, 3, 31, 41, 31, 1, 41,
1278 6, 1, 6, 7, 4, 4, 1, 1, 2, 1, 2, 11, 34, 30, 11, 1,
1279 30, 15, 15, 34, 36, 40, 36, 40, 35, 35, 37, 37, 39, 39, 38, 38},
1282 { 1, -1, 0, 2, -2, 0, 3, -3, 1, -1, 4, -4, 5, -5, 1, -1,
1283 6, -6, 2, -2, 7, -7, 1, -1, 8, -8, 9, -9, 3, -3, 1, -1,
1284 10, -10, 2, -2, 11, -11, 1, -1, 12, 4, -12, -4, 1, -1, 13, -13,
1285 1, -1, 14, -14, 2, 5, 15, -2, -5, -15, -3, 3, 16, -16, 17, 1,
1286 -1, -17, 6, 18, -6, -18, 2, -2, 19, -19, 1, -1, 20, -20, 4, -4,
1287 7, -7, 21, -21, 1, -1, 2, 3, -3, 22, -2, -22, 8, 23, -8, 1,
1288 2, -23, -1, 2, -2, -2, 24, 1, -24, -1, 25, 5, -5, 1, -25, -1,
1289 9, -9, 26, 1, -26, 3, 1, -1, 27, -3, -1, -27, 1, 3, -1, -3,
1290 28, -4, 4, 10, -10, -28, 1, -1, 1, -1, 29, 6, -29, -6, 30, -4,
1291 3, 3, -3, -30, 1, 4, -1, 31, -3, 1, 11, -11, -1, -31, 32, -1,
1292 -1, 2, -2, 1, 1, -32, 1, 4, -1, -4, 33, -1, 1, 1, -1, 5,
1293 5, -5, -33, -1, -12, 12, -5, -7, 1, 1, 7, 34, 4, -4, -1, 4,
1294 -34, -4, 35, 36, -2, -35, -2, -36, 2, 13, 2, -1, 1, -13, 1, -1,
1295 37, 1, -5, 6, 5, -1, 38, -6, -8, 5, 8, -1, 1, 1, -37, -1,
1296 5, 39, -5, -5, 6, -6, -38, -39, -14, 40, 14, 2, 1, 1, -2, -40,
1297 -1, -2, 2, -1, -1, -1, 1, 1, 1, -1, 1, -1, 1, -1, 1, -1}
1303 {0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 8, 6, 8, 7,
1304 7, 9, 9, 10, 10, 11, 11, 1, 12, 1, 12, 13, 13, 16, 14, 16,
1305 14, 15, 15, 17, 17, 18, 0, 18, 19, 20, 21, 19, 22, 21, 20, 22,
1306 25, 24, 2, 25, 24, 23, 23, 2, 26, 28, 26, 28, 29, 27, 29, 27,
1307 33, 33, 1, 32, 1, 3, 32, 30, 36, 3, 36, 30, 31, 31, 35, 34,
1308 37, 41, 34, 35, 37, 4, 41, 4, 49, 8, 8, 49, 40, 38, 5, 38,
1309 40, 39, 5, 39, 42, 43, 42, 7, 57, 6, 43, 44, 6, 50, 7, 44,
1310 57, 48, 50, 48, 45, 45, 46, 47, 51, 46, 47, 58, 1, 51, 58, 1,
1311 52, 59, 53, 9, 52, 55, 55, 59, 53, 56, 54, 56, 54, 9, 64, 64,
1312 60, 63, 60, 63, 61, 62, 61, 62, 2, 10, 2, 10, 11, 1, 11, 13,
1313 12, 1, 12, 13, 16, 16, 8, 8, 14, 3, 3, 15, 14, 15, 4, 4,
1314 1, 17, 17, 5, 1, 7, 7, 5, 6, 1, 2, 2, 6, 22, 1, 25,
1315 21, 22, 8, 24, 1, 21, 25, 24, 8, 18, 18, 23, 9, 20, 23, 33,
1316 29, 33, 20, 1, 19, 1, 29, 36, 9, 36, 19, 41, 28, 57, 32, 3,
1317 28, 3, 1, 27, 49, 49, 1, 32, 26, 26, 2, 4, 4, 7, 57, 41,
1318 2, 7, 10, 5, 37, 16, 10, 27, 8, 8, 13, 16, 37, 13, 1, 5},
1321 {0, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, 1, -1, -1, 1,
1322 -1, 1, -1, 1, -1, 1, -1, 2, 1, -2, -1, 1, -1, 1, 1, -1,
1323 -1, 1, -1, 1, -1, 1, 0, -1, 1, 1, 1, -1, 1, -1, -1, -1,
1324 1, 1, 2, -1, -1, 1, -1, -2, 1, 1, -1, -1, 1, 1, -1, -1,
1325 1, -1, 3, 1, -3, 2, -1, 1, 1, -2, -1, -1, -1, 1, 1, 1,
1326 1, 1, -1, -1, -1, 2, -1, -2, 1, 2, -2, -1, 1, 1, 2, -1,
1327 -1, 1, -2, -1, 1, 1, -1, 2, 1, 2, -1, 1, -2, -1, -2, -1,
1328 -1, 1, 1, -1, 1, -1, 1, 1, 1, -1, -1, 1, 4, -1, -1, -4,
1329 1, 1, 1, 2, -1, -1, 1, -1, -1, 1, -1, -1, 1, -2, 1, -1,
1330 1, 1, -1, -1, 1, 1, -1, -1, 3, 2, -3, -2, 2, 5, -2, 2,
1331 2, -5, -2, -2, -2, 2, -3, 3, 2, 3, -3, 2, -2, -2, 3, -3,
1332 6, 2, -2, 3, -6, 3, -3, -3, 3, 7, -4, 4, -3, 2, -7, 2,
1333 2, -2, -4, 2, 8, -2, -2, -2, 4, 2, -2, 2, 3, 2, -2, -2,
1334 2, 2, -2, -8, -2, 9, -2, 2, -3, -2, 2, -2, 2, 2, 2, 4,
1335 -2, -4, 10, 2, 2, -2, -9, -2, 2, -2, 5, 4, -4, 4, -2, 2,
1336 -5, -4, -3, 4, 2, -3, 3, -2, -5, 5, 3, 3, -2, -3, -10, -4}
1342 {1, 1, 0, 2, 2, 1, 1, 3, 3, 4, 4, 0, 1, 1, 5, 5,
1343 2, 2, 6, 6, 7, 7, 1, 8, 1, 8, 3, 3, 9, 9, 1, 2,
1344 2, 1, 4, 10, 4, 10, 11, 11, 1, 5, 12, 12, 1, 5, 13, 13,
1345 3, 3, 6, 6, 2, 2, 14, 14, 16, 16, 15, 7, 15, 8, 8, 7,
1346 1, 1, 17, 17, 4, 4, 1, 1, 18, 18, 2, 2, 5, 5, 25, 3,
1347 9, 3, 25, 9, 19, 24, 19, 24, 1, 21, 20, 1, 21, 22, 20, 22,
1348 23, 23, 8, 6, 33, 6, 8, 33, 7, 7, 26, 26, 1, 32, 1, 32,
1349 28, 4, 28, 10, 29, 27, 27, 10, 41, 4, 29, 2, 2, 41, 36, 31,
1350 49, 31, 34, 30, 34, 36, 30, 35, 1, 49, 11, 5, 35, 11, 1, 3,
1351 3, 5, 37, 37, 8, 40, 8, 40, 12, 12, 42, 42, 1, 38, 16, 57,
1352 1, 6, 16, 39, 38, 6, 7, 7, 13, 13, 39, 43, 2, 43, 57, 2,
1353 50, 9, 44, 9, 50, 4, 15, 48, 44, 4, 1, 15, 48, 14, 14, 1,
1354 45, 45, 8, 3, 5, 8, 51, 47, 3, 46, 46, 47, 5, 51, 1, 17,
1355 17, 58, 1, 58, 2, 52, 52, 2, 53, 7, 59, 6, 6, 56, 53, 55,
1356 7, 55, 1, 54, 59, 56, 54, 10, 1, 10, 4, 60, 1, 60, 8, 4,
1357 8, 64, 64, 61, 1, 63, 3, 63, 62, 61, 5, 11, 5, 3, 11, 62},
1360 { 1, -1, 0, 1, -1, 2, -2, 1, -1, 1, -1, 0, 3, -3, 1, -1,
1361 2, -2, 1, -1, 1, -1, 4, 1, -4, -1, 2, -2, 1, -1, 5, 3,
1362 -3, -5, 2, 1, -2, -1, 1, -1, 6, 2, 1, -1, -6, -2, 1, -1,
1363 3, -3, 2, -2, 4, -4, 1, -1, 1, -1, 1, 2, -1, 2, -2, -2,
1364 7, -7, 1, -1, 3, -3, 8, -8, 1, -1, 5, -5, 3, -3, 1, 4,
1365 2, -4, -1, -2, 1, 1, -1, -1, 9, 1, 1, -9, -1, 1, -1, -1,
1366 1, -1, 3, -3, 1, 3, -3, -1, 3, -3, 1, -1, 10, 1, -10, -1,
1367 1, 4, -1, 2, 1, -1, 1, -2, 1, -4, -1, 6, -6, -1, 1, 1,
1368 1, -1, 1, 1, -1, -1, -1, 1, 11, -1, -2, 4, -1, 2, -11, 5,
1369 -5, -4, -1, 1, 4, 1, -4, -1, -2, 2, 1, -1, 12, 1, -2, 1,
1370 -12, 4, 2, 1, -1, -4, 4, -4, 2, -2, -1, 1, 7, -1, -1, -7,
1371 -1, -3, 1, 3, 1, 5, 2, 1, -1, -5, 13, -2, -1, 2, -2, -13,
1372 1, -1, 5, 6, 5, -5, 1, 1, -6, 1, -1, -1, -5, -1, 14, 2,
1373 -2, 1, -14, -1, 8, 1, -1, -8, 1, 5, 1, 5, -5, 1, -1, 1,
1374 -5, -1, 15, 1, -1, -1, -1, 3, -15, -3, 6, 1, 16, -1, 6, -6,
1375 -6, 1, -1, 1, -16, 1, 7, -1, 1, -1, -6, -3, 6, -7, 3, -1}
1381 {0, 1, 1, 2, 2, 3, 3, 4, 4, 1, 1, 5, 5, 6, 6, 7,
1382 7, 8, 8, 9, 9, 2, 2, 10, 10, 1, 1, 11, 11, 12, 12, 3,
1383 3, 13, 13, 0, 14, 14, 16, 15, 16, 15, 4, 4, 17, 1, 17, 1,
1384 5, 5, 18, 18, 2, 2, 6, 6, 8, 19, 7, 8, 7, 19, 20, 20,
1385 21, 21, 22, 24, 22, 24, 23, 23, 1, 1, 25, 25, 3, 3, 26, 26,
1386 9, 9, 27, 27, 28, 28, 33, 29, 4, 33, 29, 1, 4, 1, 32, 32,
1387 2, 2, 31, 10, 30, 10, 30, 31, 34, 34, 5, 5, 36, 36, 35, 41,
1388 35, 11, 41, 11, 37, 1, 8, 8, 37, 6, 1, 6, 40, 7, 7, 40,
1389 12, 38, 12, 39, 39, 38, 49, 13, 49, 13, 3, 42, 3, 42, 16, 16,
1390 43, 43, 14, 14, 1, 1, 44, 15, 44, 15, 2, 2, 57, 48, 50, 48,
1391 57, 50, 4, 45, 45, 4, 46, 47, 47, 46, 1, 51, 1, 17, 17, 51,
1392 8, 9, 9, 5, 58, 8, 58, 5, 52, 52, 55, 56, 53, 56, 55, 59,
1393 59, 53, 54, 1, 6, 54, 7, 7, 6, 1, 2, 3, 2, 3, 64, 60,
1394 60, 10, 10, 64, 61, 62, 61, 63, 1, 63, 62, 1, 18, 24, 18, 4,
1395 25, 4, 8, 21, 21, 1, 24, 22, 25, 22, 8, 11, 19, 11, 23, 1,
1396 20, 23, 19, 20, 5, 12, 5, 1, 16, 2, 12, 13, 2, 13, 1, 16},
1399 { 0, 1, -1, 1, -1, 1, -1, 1, -1, 2, -2, 1, -1, 1, -1, 1,
1400 -1, 1, -1, 1, -1, 2, -2, 1, -1, 3, -3, 1, -1, 1, -1, 2,
1401 -2, 1, -1, 0, 1, -1, 1, 1, -1, -1, 2, -2, 1, 4, -1, -4,
1402 2, -2, 1, -1, -3, 3, 2, -2, 2, 1, 2, -2, -2, -1, 1, -1,
1403 1, -1, 1, 1, -1, -1, 1, -1, 5, -5, 1, -1, 3, -3, 1, -1,
1404 2, -2, 1, -1, 1, -1, 1, 1, 3, -1, -1, 6, -3, -6, -1, 1,
1405 4, -4, 1, 2, 1, -2, -1, -1, 1, -1, 3, -3, 1, -1, 1, 1,
1406 -1, 2, -1, -2, 1, 7, -3, 3, -1, 3, -7, -3, 1, -3, 3, -1,
1407 2, 1, -2, 1, -1, -1, 1, 2, -1, -2, -4, -1, 4, 1, 2, -2,
1408 1, -1, -2, 2, 8, -8, -1, 2, 1, -2, -5, 5, 1, -1, -1, 1,
1409 -1, 1, 4, -1, 1, -4, -1, -1, 1, 1, 9, 1, -9, 2, -2, -1,
1410 -4, 3, -3, -4, -1, 4, 1, 4, 1, -1, 1, -1, 1, 1, -1, 1,
1411 -1, -1, -1, 10, 4, 1, 4, -4, -4, -10, 6, 5, -6, -5, 1, -1,
1412 1, 3, -3, -1, 1, -1, -1, -1, 11, 1, 1, -11, -2, -2, 2, 5,
1413 -2, -5, -5, 2, -2, 12, 2, -2, 2, 2, 5, -3, -2, 3, -2, -12,
1414 -2, 2, 2, 2, -5, 3, 5, 13, -3, 7, -3, -3, -7, 3, -13, 3}
1420 {0, 1, 1, 1, 2, 2, 1, 3, 3, 1, 1, 1, 4, 4, 1, 5,
1421 2, 1, 5, 2, 1, 1, 6, 6, 1, 1, 1, 1, 1, 7, 3, 1,
1422 2, 3, 0, 1, 2, 7, 1, 1, 1, 8, 1, 1, 8, 1, 1, 1,
1423 9, 1, 9, 1, 2, 1, 1, 2, 1, 1, 10, 4, 1, 10, 1, 4,
1424 1, 1, 1, 1, 1, 3, 1, 1, 1, 3, 2, 1, 5, 1, 1, 1,
1425 2, 5, 1, 11, 1, 11, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1426 2, 1, 6, 1, 6, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 12,
1427 3, 1, 12, 1, 1, 1, 2, 1, 1, 3, 1, 1, 1, 1, 1, 1,
1428 4, 1, 1, 1, 2, 1, 1, 4, 1, 1, 1, 1, 1, 1, 2, 1,
1429 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 2, 1, 1, 5,
1430 1, 1, 1, 1, 1, 7, 1, 7, 1, 1, 2, 3, 1, 1, 1, 1,
1431 5, 1, 1, 1, 1, 1, 1, 2, 13, 1, 1, 1, 1, 1, 1, 1,
1432 1, 1, 1, 1, 1, 1, 1, 1, 13, 2, 1, 1, 4, 1, 1, 1,
1433 3, 1, 6, 1, 1, 1, 14, 1, 1, 1, 1, 1, 14, 6, 1, 1,
1434 1, 1, 15, 2, 4, 1, 2, 3, 15, 1, 1, 1, 8, 1, 1, 8,
1435 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1},
1438 { 0, 1, -1, 2, 1, -1, -2, 1, -1, 3, -3, 4, 1, -1, -4, 1,
1439 2, 5, -1, -2, -5, 6, 1, -1, -6, 7, -7, 8, -8, 1, 2, 9,
1440 3, -2, 0, -9, -3, -1, 10, -10, 11, 1, -11, 12, -1, -12, 13, -13,
1441 1, 14, -1, -14, 4, 15, -15, -4, 16, -16, 1, 2, 17, -1, -17, -2,
1442 18, -18, 19, -19, 20, 3, -20, 21, -21, -3, 5, 22, 2, -22, -23, 23,
1443 -5, -2, 24, 1, -24, -1, 25, -25, 26, -26, -27, 27, 28, 29, -28, -29,
1444 6, 30, 2, -31, -2, -30, 31, -6, -32, 32, 33, -33, 34, -35, -34, 1,
1445 4, -36, -1, 35, 37, 36, 7, -37, 38, -4, -38, 39, 41, 40, -40, -39,
1446 3, 42, -43, -41, -7, -42, 43, -3, 44, -44, 45, -45, 46, 47, 8, -47,
1447 -48, -46, 50, -50, 48, 49, 51, -49, 52, -52, 5, -51, -8, -53, 53, 3,
1448 -56, 56, 55, 54, -54, 2, 60, -2, -55, 58, 9, -5, 59, 57, -57, -63,
1449 -3, -58, -60, -61, 61, -59, -62, -9, 1, 64, 62, 69, -64, 63, 65, -67,
1450 -68, 66, -65, 68, -66, -69, 67, -70, -1, 10, 71, -71, 4, 73, 72, 70,
1451 6, -76, -3, 74, -78, -74, 1, 78, 80, -72, -75, 76, -1, 3, -73, 79,
1452 75, 77, 1, 11, -4, -79, -10, -6, -1, -77, -83, -80, 2, 81, -84, -2,
1453 83, -81, 82, -82, 84, -87, -86, 85, -11, -85, 86, -89, 87, -88, 88, 89}
1459 {1, 1, 0, 2, 1, 2, 1, 3, 3, 1, 1, 4, 4, 2, 2, 1,
1460 1, 5, 5, 6, 1, 6, 1, 7, 7, 3, 3, 2, 8, 2, 8, 1,
1461 1, 0, 9, 9, 1, 1, 10, 4, 10, 4, 11, 11, 2, 1, 2, 1,
1462 12, 12, 3, 3, 1, 1, 13, 5, 5, 13, 14, 1, 1, 14, 2, 2,
1463 6, 6, 15, 1, 1, 15, 16, 4, 7, 16, 4, 7, 1, 1, 3, 3,
1464 8, 8, 2, 2, 1, 1, 17, 17, 1, 1, 18, 18, 5, 5, 2, 2,
1465 1, 1, 9, 19, 9, 19, 20, 3, 3, 20, 1, 10, 21, 1, 10, 4,
1466 4, 21, 22, 6, 6, 22, 1, 1, 23, 24, 2, 2, 23, 24, 11, 1,
1467 1, 11, 7, 25, 7, 1, 1, 25, 8, 8, 3, 26, 3, 1, 12, 2,
1468 2, 26, 1, 12, 5, 5, 27, 4, 1, 4, 1, 27, 28, 1, 28, 13,
1469 1, 13, 2, 29, 2, 1, 32, 6, 1, 30, 14, 29, 14, 6, 3, 31,
1470 3, 1, 30, 1, 32, 31, 33, 9, 33, 1, 1, 7, 9, 7, 2, 2,
1471 1, 1, 4, 36, 34, 4, 5, 10, 10, 5, 34, 1, 1, 35, 8, 8,
1472 36, 3, 35, 1, 15, 3, 2, 1, 16, 15, 16, 2, 37, 1, 37, 1,
1473 1, 1, 6, 6, 38, 1, 38, 11, 1, 39, 39, 40, 11, 2, 41, 4,
1474 40, 1, 2, 4, 1, 1, 1, 41, 3, 1, 3, 1, 5, 7, 5, 7},
1477 { 1, -1, 0, 1, 2, -1, -2, 1, -1, 3, -3, 1, -1, 2, -2, 4,
1478 -4, 1, -1, 1, 5, -1, -5, 1, -1, 2, -2, 3, 1, -3, -1, 6,
1479 -6, 0, 1, -1, 7, -7, 1, 2, -1, -2, 1, -1, 4, 8, -4, -8,
1480 1, -1, 3, -3, 9, -9, 1, 2, -2, -1, 1, 10, -10, -1, 5, -5,
1481 2, -2, 1, 11, -11, -1, 1, 3, 2, -1, -3, -2, 12, -12, 4, -4,
1482 2, -2, -6, 6, 13, -13, 1, -1, 14, -14, 1, -1, 3, -3, 7, -7,
1483 15, -15, 2, 1, -2, -1, 1, 5, -5, -1, -16, 2, 1, 16, -2, 4,
1484 -4, -1, 1, 3, -3, -1, 17, -17, 1, 1, -8, 8, -1, -1, 2, 18,
1485 -18, -2, 3, 1, -3, 19, -19, -1, 3, -3, 6, 1, -6, 20, 2, 9,
1486 -9, -1, -20, -2, 4, -4, 1, -5, 21, 5, -21, -1, 1, -22, -1, 2,
1487 22, -2, 10, 1, -10, 23, 1, 4, -23, 1, 2, -1, -2, -4, -7, 1,
1488 7, -24, -1, 24, -1, -1, 1, 3, -1, -25, 25, 4, -3, -4, 11, -11,
1489 26, -26, 6, 1, 1, -6, -5, -3, 3, 5, -1, -27, 27, 1, 4, -4,
1490 -1, -8, -1, 28, 2, 8, -12, -28, -2, -2, 2, 12, -1, 29, 1, -29,
1491 30, -30, 5, -5, 1, -31, -1, 3, 31, -1, 1, 1, -3, -13, 1, -7,
1492 -1, -32, 13, 7, 32, 33, -33, -1, -9, -34, 9, 34, -6, 5, 6, -5}
1498 {1, 1, 0, 1, 1, 2, 2, 1, 1, 3, 3, 1, 1, 0, 2, 2,
1499 4, 1, 4, 1, 1, 1, 5, 5, 1, 1, 6, 6, 2, 2, 1, 1,
1500 3, 3, 7, 7, 1, 1, 8, 8, 1, 1, 2, 2, 1, 9, 1, 9,
1501 4, 4, 10, 1, 1, 10, 1, 1, 11, 11, 3, 3, 1, 2, 1, 2,
1502 1, 1, 12, 12, 5, 5, 1, 1, 13, 1, 1, 13, 2, 2, 1, 1,
1503 6, 6, 1, 1, 4, 14, 4, 14, 3, 1, 3, 1, 1, 1, 15, 7,
1504 15, 2, 2, 7, 1, 1, 1, 8, 1, 8, 16, 16, 1, 1, 1, 1,
1505 2, 1, 1, 2, 1, 1, 3, 5, 5, 3, 4, 1, 1, 4, 1, 1,
1506 17, 17, 9, 1, 1, 9, 2, 2, 1, 1, 10, 10, 1, 6, 1, 1,
1507 6, 18, 1, 1, 18, 1, 1, 1, 2, 2, 3, 1, 3, 1, 1, 1,
1508 4, 1, 19, 1, 19, 7, 1, 1, 20, 1, 4, 20, 1, 7, 11, 2,
1509 1, 11, 21, 2, 8, 5, 1, 8, 1, 5, 21, 1, 1, 1, 22, 1,
1510 1, 22, 1, 1, 3, 3, 1, 23, 2, 12, 24, 1, 1, 2, 1, 1,
1511 12, 23, 1, 1, 24, 1, 1, 1, 4, 1, 1, 1, 2, 1, 6, 6,
1512 4, 2, 1, 1, 1, 1, 1, 1, 1, 14, 13, 3, 1, 25, 9, 25,
1513 14, 1, 9, 3, 13, 1, 1, 1, 1, 1, 10, 1, 1, 2, 10, 2},
1516 {-20, -1, 0, 2, -2, 1, -1, 3, -3, 1, -1, 4, -4, 0, 2, -2,
1517 1, 5, -1, -5, 6, -6, 1, -1, 7, -7, 1, -1, 3, -3, 8, -8,
1518 2, -2, 1, -1, 9, -9, 1, -1, 10, -10, 4, -4, 11, 1, -11, -1,
1519 2, -2, 1, 12, -12, -1, 13, -13, 1, -1, 3, -3, 14, 5, -14, -5,
1520 -15, 15, -1, 1, 2, -2, 16, -16, 1, 17, -17, -1, 6, -6, 18, -18,
1521 2, -2, -19, 19, -3, 1, 3, -1, 4, 20, -4, 1, -21, 21, 1, 2,
1522 -1, -7, 7, -2, 22, -22, 23, 2, -23, -2, 1, -1, -24, 24, -25, 25,
1523 -8, -26, 26, 8, -27, 27, 5, 3, -3, -5, -4, 28, -28, 4, 29, -29,
1524 1, -1, -2, -30, 30, 2, 9, -9, -31, 31, 2, -2, -32, 3, 32, -33,
1525 -3, 1, 33, -34, -1, 34, -35, 35, -10, 10, -6, 36, 6, -36, 37, -37,
1526 -5, 38, 1, -38, -1, 3, 39, -39, -1, 40, 5, 1, -40, -3, 2, -11,
1527 -41, -2, 1, 11, -3, -4, 41, 3, 42, 4, -1, -43, -42, 43, 1, -44,
1528 45, -1, 44, -45, -7, 7, -46, 1, -12, 2, 1, -47, 46, 12, 47, 48,
1529 -2, -1, -48, 49, -1, -50, -49, 50, -6, -51, 51, 52, -13, 53, -4, 4,
1530 6, 13, -53, -52, -54, 55, 54, -55, -56, -2, 2, -8, 56, 1, -3, -1,
1531 2, 58, 3, 8, -2, 57, -58, -60, -59, -57, -3, 60, 59, -14, 3, 14}
1537 {1, 1, 0, 2, 2, 1, 1, 3, 3, 4, 4, 5, 5, 1, 1, 6,
1538 6, 2, 2, 7, 7, 8, 8, 1, 1, 3, 3, 9, 9, 10, 10, 1,
1539 1, 2, 2, 4, 4, 11, 0, 11, 12, 12, 13, 13, 1, 1, 5, 5,
1540 14, 14, 15, 16, 15, 16, 3, 3, 1, 6, 1, 6, 2, 2, 7, 7,
1541 8, 8, 17, 17, 1, 1, 4, 4, 18, 18, 2, 2, 1, 19, 1, 20,
1542 19, 20, 21, 21, 3, 3, 22, 22, 5, 5, 24, 1, 1, 23, 9, 23,
1543 24, 9, 2, 2, 10, 1, 1, 10, 6, 6, 25, 4, 4, 25, 7, 7,
1544 26, 8, 1, 8, 3, 1, 26, 3, 11, 11, 27, 27, 2, 28, 1, 2,
1545 28, 1, 12, 12, 5, 5, 29, 13, 13, 29, 32, 1, 1, 33, 31, 30,
1546 32, 4, 30, 33, 4, 31, 3, 14, 1, 1, 3, 34, 34, 2, 2, 14,
1547 6, 6, 35, 36, 35, 36, 1, 15, 1, 16, 16, 15, 7, 9, 7, 9,
1548 37, 8, 8, 37, 1, 1, 39, 2, 38, 39, 2, 40, 5, 38, 40, 5,
1549 3, 3, 4, 4, 10, 10, 1, 1, 1, 1, 41, 2, 41, 2, 6, 6,
1550 1, 1, 11, 42, 11, 43, 3, 42, 3, 17, 4, 43, 1, 17, 7, 1,
1551 8, 44, 4, 7, 44, 5, 8, 2, 5, 1, 2, 48, 45, 1, 12, 45,
1552 12, 48, 13, 13, 1, 9, 9, 46, 1, 46, 47, 47, 49, 18, 18, 49},
1555 { 1, -1, 0, 1, -1, 2, -2, 1, -1, 1, -1, 1, -1, 3, -3, 1,
1556 -1, -2, 2, 1, -1, 1, -1, 4, -4, -2, 2, 1, -1, 1, -1, 5,
1557 -5, -3, 3, 2, -2, 1, 0, -1, 1, -1, 1, -1, 6, -6, 2, -2,
1558 1, -1, 1, 1, -1, -1, -3, 3, 7, 2, -7, -2, -4, 4, 2, -2,
1559 2, -2, 1, -1, 8, -8, 3, -3, 1, -1, -5, 5, 9, 1, -9, 1,
1560 -1, -1, 1, -1, -4, 4, 1, -1, 3, -3, 1, -10, 10, 1, 2, -1,
1561 -1, -2, 6, -6, 2, 11, -11, -2, 3, -3, 1, -4, 4, -1, 3, -3,
1562 1, 3, 12, -3, -5, -12, -1, 5, 2, -2, 1, -1, -7, 1, 13, 7,
1563 -1, -13, 2, -2, 4, -4, 1, 2, -2, -1, 1, 14, -14, 1, 1, 1,
1564 -1, -5, -1, -1, 5, -1, -6, 2, -15, 15, 6, 1, -1, -8, 8, -2,
1565 -4, 4, 1, 1, -1, -1, 16, 2, -16, -2, 2, -2, 4, 3, -4, -3,
1566 -1, -4, 4, 1, -17, 17, -1, -9, 1, 1, 9, 1, -5, -1, -1, 5,
1567 -7, 7, 6, -6, 3, -3, 18, -18, 19, -19, 1, -10, -1, 10, -5, 5,
1568 20, -20, -3, 1, 3, 1, 8, -1, -8, 2, 7, -1, -21, -2, 5, 21,
1569 5, -1, -7, -5, 1, -6, -5, -11, 6, 22, 11, 1, 1, -22, -3, -1,
1570 3, -1, 3, -3, -23, 4, -4, 1, 23, -1, 1, -1, 1, -2, 2, -1}
1576 {1, 1, 1, 1, 0, 2, 2, 1, 1, 3, 3, 0, 1, 1, 2, 2,
1577 4, 4, 1, 1, 5, 5, 1, 1, 2, 2, 3, 3, 6, 6, 1, 1,
1578 7, 7, 8, 1, 8, 2, 2, 1, 4, 4, 1, 3, 1, 3, 9, 9,
1579 2, 2, 1, 5, 1, 5, 10, 10, 1, 1, 11, 11, 3, 6, 3, 4,
1580 4, 6, 2, 2, 1, 12, 1, 12, 7, 13, 7, 13, 1, 1, 8, 8,
1581 2, 2, 14, 14, 16, 15, 16, 5, 5, 1, 3, 15, 1, 3, 4, 4,
1582 1, 1, 17, 17, 2, 2, 6, 6, 1, 18, 1, 18, 22, 21, 22, 21,
1583 25, 24, 25, 19, 9, 20, 9, 23, 19, 24, 20, 3, 23, 7, 3, 1,
1584 1, 7, 28, 26, 29, 5, 28, 26, 5, 8, 29, 4, 8, 27, 2, 2,
1585 4, 27, 1, 1, 10, 36, 10, 33, 33, 36, 30, 1, 32, 32, 1, 30,
1586 6, 31, 31, 35, 3, 6, 11, 11, 3, 2, 35, 2, 34, 1, 34, 1,
1587 37, 37, 12, 7, 12, 5, 41, 5, 4, 7, 1, 8, 13, 4, 1, 41,
1588 13, 38, 8, 38, 9, 1, 40, 40, 9, 1, 39, 2, 2, 49, 39, 42,
1589 3, 3, 14, 16, 49, 14, 16, 42, 43, 43, 6, 6, 15, 1, 1, 15,
1590 44, 44, 1, 1, 50, 48, 4, 5, 4, 7, 5, 2, 10, 10, 48, 7,
1591 50, 45, 2, 1, 45, 8, 8, 1, 46, 46, 3, 47, 47, 3, 1, 1},
1594 { 1, -1, 2, -2, 0, 1, -1, 3, -3, 1, -1, 0, 4, -4, 2, -2,
1595 1, -1, 5, -5, 1, -1, 6, -6, 3, -3, 2, -2, 1, -1, 7, -7,
1596 1, -1, 1, 8, -1, 4, -4, -8, 2, -2, 9, 3, -9, -3, 1, -1,
1597 5, -5, 10, 2, -10, -2, 1, -1, 11, -11, 1, -1, -4, 2, 4, 3,
1598 -3, -2, 6, -6, 12, 1, -12, -1, 2, 1, -2, -1, 13, -13, 2, -2,
1599 7, -7, 1, -1, 1, 1, -1, 3, -3, 14, 5, -1, -14, -5, 4, -4,
1600 15, -15, 1, -1, 8, -8, -3, 3, 16, 1, -16, -1, 1, 1, -1, -1,
1601 1, 1, -1, 1, 2, 1, -2, 1, -1, -1, -1, 6, -1, 3, -6, 17,
1602 -17, -3, 1, 1, 1, 4, -1, -1, -4, 3, -1, 5, -3, -1, -9, 9,
1603 -5, 1, 18, -18, 2, 1, -2, 1, -1, -1, 1, 19, -1, 1, -19, -1,
1604 4, 1, -1, 1, 7, -4, -2, 2, -7, 10, -1, -10, 1, 20, -1, -20,
1605 1, -1, 2, 4, -2, 5, 1, -5, 6, -4, 21, 4, 2, -6, -21, -1,
1606 -2, 1, -4, -1, -3, 22, -1, 1, 3, -22, -1, 11, -11, 1, 1, 1,
1607 8, -8, 2, 2, -1, -2, -2, -1, 1, -1, -5, 5, 2, 23, -23, -2,
1608 1, -1, 24, -24, -1, -1, 7, 6, -7, 5, -6, 12, -3, 3, 1, -5,
1609 1, 1, -12, 25, -1, -5, 5, -25, -1, 1, 9, 1, -1, -9, 26, -26}