2 * common functions for Indeo Video Interactive codecs (Indeo4 and Indeo5)
4 * Copyright (c) 2009 Maxim Poliakovski
6 * This file is part of FFmpeg.
8 * FFmpeg is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU Lesser General Public
10 * License as published by the Free Software Foundation; either
11 * version 2.1 of the License, or (at your option) any later version.
13 * FFmpeg is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * Lesser General Public License for more details.
18 * You should have received a copy of the GNU Lesser General Public
19 * License along with FFmpeg; if not, write to the Free Software
20 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
25 * This file contains functions and data shared by both Indeo4 and
31 #include "libavutil/attributes.h"
32 #include "libavutil/imgutils.h"
33 #include "libavutil/timer.h"
35 #define BITSTREAM_READER_LE
44 * These are 2x8 predefined Huffman codebooks for coding macroblock/block
45 * signals. They are specified using "huffman descriptors" in order to
46 * avoid huge static tables. The decoding tables will be generated at
47 * startup from these descriptors.
49 /** static macroblock huffman tables */
50 static const IVIHuffDesc ivi_mb_huff_desc[8] = {
51 {8, {0, 4, 5, 4, 4, 4, 6, 6}},
52 {12, {0, 2, 2, 3, 3, 3, 3, 5, 3, 2, 2, 2}},
53 {12, {0, 2, 3, 4, 3, 3, 3, 3, 4, 3, 2, 2}},
54 {12, {0, 3, 4, 4, 3, 3, 3, 3, 3, 2, 2, 2}},
55 {13, {0, 4, 4, 3, 3, 3, 3, 2, 3, 3, 2, 1, 1}},
56 {9, {0, 4, 4, 4, 4, 3, 3, 3, 2}},
57 {10, {0, 4, 4, 4, 4, 3, 3, 2, 2, 2}},
58 {12, {0, 4, 4, 4, 3, 3, 2, 3, 2, 2, 2, 2}}
61 /** static block huffman tables */
62 static const IVIHuffDesc ivi_blk_huff_desc[8] = {
63 {10, {1, 2, 3, 4, 4, 7, 5, 5, 4, 1}},
64 {11, {2, 3, 4, 4, 4, 7, 5, 4, 3, 3, 2}},
65 {12, {2, 4, 5, 5, 5, 5, 6, 4, 4, 3, 1, 1}},
66 {13, {3, 3, 4, 4, 5, 6, 6, 4, 4, 3, 2, 1, 1}},
67 {11, {3, 4, 4, 5, 5, 5, 6, 5, 4, 2, 2}},
68 {13, {3, 4, 5, 5, 5, 5, 6, 4, 3, 3, 2, 1, 1}},
69 {13, {3, 4, 5, 5, 5, 6, 5, 4, 3, 3, 2, 1, 1}},
70 {9, {3, 4, 4, 5, 5, 5, 6, 5, 5}}
73 static VLC ivi_mb_vlc_tabs [8]; ///< static macroblock Huffman tables
74 static VLC ivi_blk_vlc_tabs[8]; ///< static block Huffman tables
76 typedef void (*ivi_mc_func) (int16_t *buf, const int16_t *ref_buf,
77 ptrdiff_t pitch, int mc_type);
78 typedef void (*ivi_mc_avg_func) (int16_t *buf, const int16_t *ref_buf1,
79 const int16_t *ref_buf2,
80 ptrdiff_t pitch, int mc_type, int mc_type2);
82 static int ivi_mc(const IVIBandDesc *band, ivi_mc_func mc, ivi_mc_avg_func mc_avg,
83 int offs, int mv_x, int mv_y, int mv_x2, int mv_y2,
84 int mc_type, int mc_type2)
86 int ref_offs = offs + mv_y * band->pitch + mv_x;
87 int buf_size = band->pitch * band->aheight;
88 int min_size = band->pitch * (band->blk_size - 1) + band->blk_size;
89 int ref_size = (mc_type > 1) * band->pitch + (mc_type & 1);
92 av_assert0(offs >= 0 && ref_offs >= 0 && band->ref_buf);
93 av_assert0(buf_size - min_size >= offs);
94 av_assert0(buf_size - min_size - ref_size >= ref_offs);
98 mc(band->buf + offs, band->ref_buf + ref_offs, band->pitch, mc_type);
100 int ref_offs2 = offs + mv_y2 * band->pitch + mv_x2;
101 int ref_size2 = (mc_type2 > 1) * band->pitch + (mc_type2 & 1);
102 if (offs < 0 || ref_offs2 < 0 || !band->b_ref_buf)
103 return AVERROR_INVALIDDATA;
104 if (buf_size - min_size - ref_size2 < ref_offs2)
105 return AVERROR_INVALIDDATA;
108 mc(band->buf + offs, band->b_ref_buf + ref_offs2,
109 band->pitch, mc_type2);
111 mc_avg(band->buf + offs, band->ref_buf + ref_offs,
112 band->b_ref_buf + ref_offs2, band->pitch,
120 * Reverse "nbits" bits of the value "val" and return the result
121 * in the least significant bits.
123 static uint16_t inv_bits(uint16_t val, int nbits)
128 res = ff_reverse[val] >> (8 - nbits);
130 res = ((ff_reverse[val & 0xFF] << 8) +
131 (ff_reverse[val >> 8])) >> (16 - nbits);
137 * Generate a huffman codebook from the given descriptor
138 * and convert it into the FFmpeg VLC table.
140 * @param[in] cb pointer to codebook descriptor
141 * @param[out] vlc where to place the generated VLC table
142 * @param[in] flag flag: 1 - for static or 0 for dynamic tables
143 * @return result code: 0 - OK, -1 = error (invalid codebook descriptor)
145 static int ivi_create_huff_from_desc(const IVIHuffDesc *cb, VLC *vlc, int flag)
147 int pos, i, j, codes_per_row, prefix, not_last_row;
148 uint16_t codewords[256]; /* FIXME: move this temporal storage out? */
151 pos = 0; /* current position = 0 */
153 for (i = 0; i < cb->num_rows; i++) {
154 codes_per_row = 1 << cb->xbits[i];
155 not_last_row = (i != cb->num_rows - 1);
156 prefix = ((1 << i) - 1) << (cb->xbits[i] + not_last_row);
158 for (j = 0; j < codes_per_row; j++) {
159 if (pos >= 256) /* Some Indeo5 codebooks can have more than 256 */
160 break; /* elements, but only 256 codes are allowed! */
162 bits[pos] = i + cb->xbits[i] + not_last_row;
163 if (bits[pos] > IVI_VLC_BITS)
164 return AVERROR_INVALIDDATA; /* invalid descriptor */
166 codewords[pos] = inv_bits((prefix | j), bits[pos]);
174 /* number of codewords = pos */
175 return init_vlc(vlc, IVI_VLC_BITS, pos, bits, 1, 1, codewords, 2, 2,
176 (flag ? INIT_VLC_USE_NEW_STATIC : 0) | INIT_VLC_LE);
179 av_cold void ff_ivi_init_static_vlc(void)
182 static VLC_TYPE table_data[8192 * 16][2];
183 static int initialized_vlcs = 0;
185 if (initialized_vlcs)
187 for (i = 0; i < 8; i++) {
188 ivi_mb_vlc_tabs[i].table = table_data + i * 2 * 8192;
189 ivi_mb_vlc_tabs[i].table_allocated = 8192;
190 ivi_create_huff_from_desc(&ivi_mb_huff_desc[i],
191 &ivi_mb_vlc_tabs[i], 1);
192 ivi_blk_vlc_tabs[i].table = table_data + (i * 2 + 1) * 8192;
193 ivi_blk_vlc_tabs[i].table_allocated = 8192;
194 ivi_create_huff_from_desc(&ivi_blk_huff_desc[i],
195 &ivi_blk_vlc_tabs[i], 1);
197 initialized_vlcs = 1;
201 * Copy huffman codebook descriptors.
203 * @param[out] dst ptr to the destination descriptor
204 * @param[in] src ptr to the source descriptor
206 static void ivi_huff_desc_copy(IVIHuffDesc *dst, const IVIHuffDesc *src)
208 dst->num_rows = src->num_rows;
209 memcpy(dst->xbits, src->xbits, src->num_rows);
213 * Compare two huffman codebook descriptors.
215 * @param[in] desc1 ptr to the 1st descriptor to compare
216 * @param[in] desc2 ptr to the 2nd descriptor to compare
217 * @return comparison result: 0 - equal, 1 - not equal
219 static int ivi_huff_desc_cmp(const IVIHuffDesc *desc1,
220 const IVIHuffDesc *desc2)
222 return desc1->num_rows != desc2->num_rows ||
223 memcmp(desc1->xbits, desc2->xbits, desc1->num_rows);
226 int ff_ivi_dec_huff_desc(GetBitContext *gb, int desc_coded, int which_tab,
227 IVIHuffTab *huff_tab, AVCodecContext *avctx)
230 IVIHuffDesc new_huff;
233 /* select default table */
234 huff_tab->tab = (which_tab) ? &ivi_blk_vlc_tabs[7]
235 : &ivi_mb_vlc_tabs [7];
239 huff_tab->tab_sel = get_bits(gb, 3);
240 if (huff_tab->tab_sel == 7) {
241 /* custom huffman table (explicitly encoded) */
242 new_huff.num_rows = get_bits(gb, 4);
243 if (!new_huff.num_rows) {
244 av_log(avctx, AV_LOG_ERROR, "Empty custom Huffman table!\n");
245 return AVERROR_INVALIDDATA;
248 for (i = 0; i < new_huff.num_rows; i++)
249 new_huff.xbits[i] = get_bits(gb, 4);
251 /* Have we got the same custom table? Rebuild if not. */
252 if (ivi_huff_desc_cmp(&new_huff, &huff_tab->cust_desc) || !huff_tab->cust_tab.table) {
253 ivi_huff_desc_copy(&huff_tab->cust_desc, &new_huff);
255 if (huff_tab->cust_tab.table)
256 ff_free_vlc(&huff_tab->cust_tab);
257 result = ivi_create_huff_from_desc(&huff_tab->cust_desc,
258 &huff_tab->cust_tab, 0);
260 // reset faulty description
261 huff_tab->cust_desc.num_rows = 0;
262 av_log(avctx, AV_LOG_ERROR,
263 "Error while initializing custom vlc table!\n");
267 huff_tab->tab = &huff_tab->cust_tab;
269 /* select one of predefined tables */
270 huff_tab->tab = (which_tab) ? &ivi_blk_vlc_tabs[huff_tab->tab_sel]
271 : &ivi_mb_vlc_tabs [huff_tab->tab_sel];
278 * Free planes, bands and macroblocks buffers.
280 * @param[in] planes pointer to the array of the plane descriptors
282 static av_cold void ivi_free_buffers(IVIPlaneDesc *planes)
286 for (p = 0; p < 3; p++) {
288 for (b = 0; b < planes[p].num_bands; b++) {
289 av_freep(&planes[p].bands[b].bufs[0]);
290 av_freep(&planes[p].bands[b].bufs[1]);
291 av_freep(&planes[p].bands[b].bufs[2]);
292 av_freep(&planes[p].bands[b].bufs[3]);
294 if (planes[p].bands[b].blk_vlc.cust_tab.table)
295 ff_free_vlc(&planes[p].bands[b].blk_vlc.cust_tab);
296 for (t = 0; t < planes[p].bands[b].num_tiles; t++)
297 av_freep(&planes[p].bands[b].tiles[t].mbs);
298 av_freep(&planes[p].bands[b].tiles);
300 av_freep(&planes[p].bands);
301 planes[p].num_bands = 0;
305 av_cold int ff_ivi_init_planes(AVCodecContext *avctx, IVIPlaneDesc *planes, const IVIPicConfig *cfg,
309 uint32_t b_width, b_height, align_fac, width_aligned,
310 height_aligned, buf_size;
313 ivi_free_buffers(planes);
315 if (av_image_check_size2(cfg->pic_width, cfg->pic_height, avctx->max_pixels, AV_PIX_FMT_YUV410P, 0, avctx) < 0 ||
316 cfg->luma_bands < 1 || cfg->chroma_bands < 1)
317 return AVERROR_INVALIDDATA;
319 /* fill in the descriptor of the luminance plane */
320 planes[0].width = cfg->pic_width;
321 planes[0].height = cfg->pic_height;
322 planes[0].num_bands = cfg->luma_bands;
324 /* fill in the descriptors of the chrominance planes */
325 planes[1].width = planes[2].width = (cfg->pic_width + 3) >> 2;
326 planes[1].height = planes[2].height = (cfg->pic_height + 3) >> 2;
327 planes[1].num_bands = planes[2].num_bands = cfg->chroma_bands;
329 for (p = 0; p < 3; p++) {
330 planes[p].bands = av_mallocz_array(planes[p].num_bands, sizeof(IVIBandDesc));
331 if (!planes[p].bands)
332 return AVERROR(ENOMEM);
334 /* select band dimensions: if there is only one band then it
335 * has the full size, if there are several bands each of them
336 * has only half size */
337 b_width = planes[p].num_bands == 1 ? planes[p].width
338 : (planes[p].width + 1) >> 1;
339 b_height = planes[p].num_bands == 1 ? planes[p].height
340 : (planes[p].height + 1) >> 1;
342 /* luma band buffers will be aligned on 16x16 (max macroblock size) */
343 /* chroma band buffers will be aligned on 8x8 (max macroblock size) */
344 align_fac = p ? 8 : 16;
345 width_aligned = FFALIGN(b_width , align_fac);
346 height_aligned = FFALIGN(b_height, align_fac);
347 buf_size = width_aligned * height_aligned * sizeof(int16_t);
349 for (b = 0; b < planes[p].num_bands; b++) {
350 band = &planes[p].bands[b]; /* select appropriate plane/band */
353 band->width = b_width;
354 band->height = b_height;
355 band->pitch = width_aligned;
356 band->aheight = height_aligned;
357 av_assert0(!band->bufs[0] && !band->bufs[1] &&
358 !band->bufs[2] && !band->bufs[3]);
359 band->bufsize = buf_size/2;
360 av_assert0(buf_size % 2 == 0);
362 /* reset custom vlc */
363 planes[p].bands[0].blk_vlc.cust_desc.num_rows = 0;
370 static int ivi_init_tiles(const IVIBandDesc *band, IVITile *ref_tile,
371 int p, int b, int t_height, int t_width)
374 IVITile *tile = band->tiles;
376 for (y = 0; y < band->height; y += t_height) {
377 for (x = 0; x < band->width; x += t_width) {
380 tile->mb_size = band->mb_size;
381 tile->width = FFMIN(band->width - x, t_width);
382 tile->height = FFMIN(band->height - y, t_height);
383 tile->is_empty = tile->data_size = 0;
384 /* calculate number of macroblocks */
385 tile->num_MBs = IVI_MBs_PER_TILE(tile->width, tile->height,
388 av_freep(&tile->mbs);
389 tile->mbs = av_mallocz_array(tile->num_MBs, sizeof(IVIMbInfo));
391 return AVERROR(ENOMEM);
395 if (tile->num_MBs != ref_tile->num_MBs) {
396 av_log(NULL, AV_LOG_DEBUG, "ref_tile mismatch\n");
397 return AVERROR_INVALIDDATA;
399 tile->ref_mbs = ref_tile->mbs;
409 av_cold int ff_ivi_init_tiles(IVIPlaneDesc *planes,
410 int tile_width, int tile_height)
412 int p, b, x_tiles, y_tiles, t_width, t_height, ret;
415 for (p = 0; p < 3; p++) {
416 t_width = !p ? tile_width : (tile_width + 3) >> 2;
417 t_height = !p ? tile_height : (tile_height + 3) >> 2;
419 if (!p && planes[0].num_bands == 4) {
420 if (t_width % 2 || t_height % 2) {
421 avpriv_request_sample(NULL, "Odd tiles");
422 return AVERROR_PATCHWELCOME;
427 if(t_width<=0 || t_height<=0)
428 return AVERROR(EINVAL);
430 for (b = 0; b < planes[p].num_bands; b++) {
431 band = &planes[p].bands[b];
435 for (t = 0; t < band->num_tiles; t++) {
436 av_freep(&band->tiles[t].mbs);
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(const IVIBandDesc *band, int *prev_dc, int buf_offs,
491 band->dc_transform(prev_dc, band->buf + buf_offs,
492 band->pitch, blk_size);
497 static int ivi_decode_coded_blocks(GetBitContext *gb, const IVIBandDesc *band,
498 ivi_mc_func mc, ivi_mc_avg_func mc_avg,
500 int mv_x2, int mv_y2,
501 int *prev_dc, int is_intra,
502 int mc_type, int mc_type2,
503 uint32_t quant, int offs,
504 AVCodecContext *avctx)
506 const uint16_t *base_tab = is_intra ? band->intra_base : band->inter_base;
507 RVMapDesc *rvmap = band->rv_map;
508 uint8_t col_flags[8];
510 uint32_t sym = 0, lo, hi, q;
512 int blk_size = band->blk_size;
513 int num_coeffs = blk_size * blk_size;
514 int col_mask = blk_size - 1;
516 int min_size = band->pitch * (band->transform_size - 1) +
517 band->transform_size;
518 int buf_size = band->pitch * band->aheight - offs;
520 if (min_size > buf_size)
521 return AVERROR_INVALIDDATA;
524 av_log(avctx, AV_LOG_ERROR, "Scan pattern is not set.\n");
525 return AVERROR_INVALIDDATA;
528 /* zero transform vector */
529 memset(trvec, 0, num_coeffs * sizeof(trvec[0]));
530 /* zero column flags */
531 memset(col_flags, 0, sizeof(col_flags));
532 while (scan_pos <= num_coeffs) {
533 sym = get_vlc2(gb, band->blk_vlc.tab->table,
535 if (sym == rvmap->eob_sym)
536 break; /* End of block */
538 /* Escape - run/val explicitly coded using 3 vlc codes */
539 if (sym == rvmap->esc_sym) {
540 run = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1) + 1;
541 lo = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
542 hi = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
543 /* merge them and convert into signed val */
544 val = IVI_TOSIGNED((hi << 6) | lo);
547 av_log(avctx, AV_LOG_ERROR, "Invalid sym encountered: %"PRIu32".\n", sym);
548 return AVERROR_INVALIDDATA;
550 run = rvmap->runtab[sym];
551 val = rvmap->valtab[sym];
554 /* de-zigzag and dequantize */
556 if (scan_pos >= num_coeffs || scan_pos < 0)
558 pos = band->scan[scan_pos];
561 ff_dlog(avctx, "Val = 0 encountered!\n");
563 q = (base_tab[pos] * quant) >> 9;
565 val = val * q + FFSIGN(val) * (((q ^ 1) - 1) >> 1);
567 /* track columns containing non-zero coeffs */
568 col_flags[pos & col_mask] |= !!val;
571 if (scan_pos < 0 || scan_pos >= num_coeffs && sym != rvmap->eob_sym)
572 return AVERROR_INVALIDDATA; /* corrupt block data */
574 /* undoing DC coeff prediction for intra-blocks */
575 if (is_intra && band->is_2d_trans) {
576 *prev_dc += trvec[0];
578 col_flags[0] |= !!*prev_dc;
581 if(band->transform_size > band->blk_size){
582 av_log(NULL, AV_LOG_ERROR, "Too large transform\n");
583 return AVERROR_INVALIDDATA;
586 /* apply inverse transform */
587 band->inv_transform(trvec, band->buf + offs,
588 band->pitch, col_flags);
590 /* apply motion compensation */
592 return ivi_mc(band, mc, mc_avg, offs, mv_x, mv_y, mv_x2, mv_y2,
599 * extract huffman-coded transform coefficients from the bitstream,
600 * dequantize them, apply inverse transform and motion compensation
601 * in order to reconstruct the picture.
603 * @param[in,out] gb the GetBit context
604 * @param[in] band pointer to the band descriptor
605 * @param[in] tile pointer to the tile descriptor
606 * @return result code: 0 - OK, -1 = error (corrupted blocks data)
608 static int ivi_decode_blocks(GetBitContext *gb, const IVIBandDesc *band,
609 IVITile *tile, AVCodecContext *avctx)
611 int mbn, blk, num_blocks, blk_size, ret, is_intra;
612 int mc_type = 0, mc_type2 = -1;
613 int mv_x = 0, mv_y = 0, mv_x2 = 0, mv_y2 = 0;
615 uint32_t cbp, quant, buf_offs;
617 ivi_mc_func mc_with_delta_func, mc_no_delta_func;
618 ivi_mc_avg_func mc_avg_with_delta_func, mc_avg_no_delta_func;
619 const uint8_t *scale_tab;
621 /* init intra prediction for the DC coefficient */
623 blk_size = band->blk_size;
624 /* number of blocks per mb */
625 num_blocks = (band->mb_size != blk_size) ? 4 : 1;
627 mc_with_delta_func = ff_ivi_mc_8x8_delta;
628 mc_no_delta_func = ff_ivi_mc_8x8_no_delta;
629 mc_avg_with_delta_func = ff_ivi_mc_avg_8x8_delta;
630 mc_avg_no_delta_func = ff_ivi_mc_avg_8x8_no_delta;
632 mc_with_delta_func = ff_ivi_mc_4x4_delta;
633 mc_no_delta_func = ff_ivi_mc_4x4_no_delta;
634 mc_avg_with_delta_func = ff_ivi_mc_avg_4x4_delta;
635 mc_avg_no_delta_func = ff_ivi_mc_avg_4x4_no_delta;
638 for (mbn = 0, mb = tile->mbs; mbn < tile->num_MBs; mb++, mbn++) {
639 is_intra = !mb->type;
641 buf_offs = mb->buf_offs;
643 quant = band->glob_quant + mb->q_delta;
644 if (avctx->codec_id == AV_CODEC_ID_INDEO4)
645 quant = av_clip_uintp2(quant, 5);
647 quant = av_clip(quant, 0, 23);
649 scale_tab = is_intra ? band->intra_scale : band->inter_scale;
651 quant = scale_tab[quant];
658 if (band->is_halfpel) {
659 mc_type = ((mv_y & 1) << 1) | (mv_x & 1);
660 mc_type2 = ((mv_y2 & 1) << 1) | (mv_x2 & 1);
664 mv_y2 >>= 1; /* convert halfpel vectors into fullpel ones */
668 if (mb->type != 2 && mb->type != 3)
671 int dmv_x, dmv_y, cx, cy;
673 dmv_x = mb->mv_x >> band->is_halfpel;
674 dmv_y = mb->mv_y >> band->is_halfpel;
675 cx = mb->mv_x & band->is_halfpel;
676 cy = mb->mv_y & band->is_halfpel;
678 if (mb->xpos + dmv_x < 0 ||
679 mb->xpos + dmv_x + band->mb_size + cx > band->pitch ||
680 mb->ypos + dmv_y < 0 ||
681 mb->ypos + dmv_y + band->mb_size + cy > band->aheight) {
682 return AVERROR_INVALIDDATA;
685 if (mb->type == 2 || mb->type == 3) {
686 int dmv_x, dmv_y, cx, cy;
688 dmv_x = mb->b_mv_x >> band->is_halfpel;
689 dmv_y = mb->b_mv_y >> band->is_halfpel;
690 cx = mb->b_mv_x & band->is_halfpel;
691 cy = mb->b_mv_y & band->is_halfpel;
693 if (mb->xpos + dmv_x < 0 ||
694 mb->xpos + dmv_x + band->mb_size + cx > band->pitch ||
695 mb->ypos + dmv_y < 0 ||
696 mb->ypos + dmv_y + band->mb_size + cy > band->aheight) {
697 return AVERROR_INVALIDDATA;
702 for (blk = 0; blk < num_blocks; blk++) {
703 /* adjust block position in the buffer according to its number */
705 buf_offs += blk_size;
706 } else if (blk == 2) {
707 buf_offs -= blk_size;
708 buf_offs += blk_size * band->pitch;
711 if (cbp & 1) { /* block coded ? */
712 ret = ivi_decode_coded_blocks(gb, band, mc_with_delta_func,
713 mc_avg_with_delta_func,
714 mv_x, mv_y, mv_x2, mv_y2,
716 mc_type, mc_type2, quant,
721 int buf_size = band->pitch * band->aheight - buf_offs;
722 int min_size = (blk_size - 1) * band->pitch + blk_size;
724 if (min_size > buf_size)
725 return AVERROR_INVALIDDATA;
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, const 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;
769 int clear_first = !band->qdelta_present && !band->plane && !band->band_num;
770 int mb_size = band->mb_size;
771 int xend = tile->xpos + tile->width;
772 int is_halfpel = band->is_halfpel;
773 int pitch = band->pitch;
775 if (tile->num_MBs != IVI_MBs_PER_TILE(tile->width, tile->height, mb_size)) {
776 av_log(avctx, AV_LOG_ERROR, "Allocated tile size %d mismatches "
777 "parameters %d in ivi_process_empty_tile()\n",
778 tile->num_MBs, IVI_MBs_PER_TILE(tile->width, tile->height, mb_size));
779 return AVERROR_INVALIDDATA;
782 offs = tile->ypos * pitch + tile->xpos;
784 ref_mb = tile->ref_mbs;
785 row_offset = mb_size * pitch;
786 need_mc = 0; /* reset the mc tracking flag */
788 for (y = tile->ypos; y < (tile->ypos + tile->height); y += mb_size) {
791 for (x = tile->xpos; x < xend; x += mb_size) {
794 mb->buf_offs = mb_offset;
796 mb->type = 1; /* set the macroblocks type = INTER */
797 mb->cbp = 0; /* all blocks are empty */
800 mb->q_delta = band->glob_quant;
806 if (band->inherit_qdelta)
807 mb->q_delta = ref_mb->q_delta;
809 if (band->inherit_mv) {
810 /* motion vector inheritance */
812 mb->mv_x = ivi_scale_mv(ref_mb->mv_x, mv_scale);
813 mb->mv_y = ivi_scale_mv(ref_mb->mv_y, mv_scale);
815 mb->mv_x = ref_mb->mv_x;
816 mb->mv_y = ref_mb->mv_y;
818 need_mc |= mb->mv_x || mb->mv_y; /* tracking non-zero motion vectors */
820 int dmv_x, dmv_y, cx, cy;
822 dmv_x = mb->mv_x >> is_halfpel;
823 dmv_y = mb->mv_y >> is_halfpel;
824 cx = mb->mv_x & is_halfpel;
825 cy = mb->mv_y & is_halfpel;
827 if ( mb->xpos + dmv_x < 0
828 || mb->xpos + dmv_x + mb_size + cx > pitch
829 || mb->ypos + dmv_y < 0
830 || mb->ypos + dmv_y + mb_size + cy > band->aheight) {
831 av_log(avctx, AV_LOG_ERROR, "MV out of bounds\n");
832 return AVERROR_INVALIDDATA;
840 mb_offset += mb_size;
845 if (band->inherit_mv && need_mc) { /* apply motion compensation if there is at least one non-zero motion vector */
846 num_blocks = (mb_size != band->blk_size) ? 4 : 1; /* number of blocks per mb */
847 mc_no_delta_func = (band->blk_size == 8) ? ff_ivi_mc_8x8_no_delta
848 : ff_ivi_mc_4x4_no_delta;
850 for (mbn = 0, mb = tile->mbs; mbn < tile->num_MBs; mb++, mbn++) {
853 if (!band->is_halfpel) {
854 mc_type = 0; /* we have only fullpel vectors */
856 mc_type = ((mv_y & 1) << 1) | (mv_x & 1);
858 mv_y >>= 1; /* convert halfpel vectors into fullpel ones */
861 for (blk = 0; blk < num_blocks; blk++) {
862 /* adjust block position in the buffer according with its number */
863 offs = mb->buf_offs + band->blk_size * ((blk & 1) + !!(blk & 2) * pitch);
864 ret = ivi_mc(band, mc_no_delta_func, 0, offs,
865 mv_x, mv_y, 0, 0, mc_type, -1);
871 /* copy data from the reference tile into the current one */
872 src = band->ref_buf + tile->ypos * pitch + tile->xpos;
873 dst = band->buf + tile->ypos * pitch + tile->xpos;
874 for (y = 0; y < tile->height; y++) {
875 memcpy(dst, src, tile->width*sizeof(band->buf[0]));
886 static uint16_t ivi_calc_band_checksum(const IVIBandDesc *band)
889 int16_t *src, checksum;
894 for (y = 0; y < band->height; src += band->pitch, y++)
895 for (x = 0; x < band->width; x++)
903 * Convert and output the current plane.
904 * This conversion is done by adding back the bias value of 128
905 * (subtracted in the encoder) and clipping the result.
907 * @param[in] plane pointer to the descriptor of the plane being processed
908 * @param[out] dst pointer to the buffer receiving converted pixels
909 * @param[in] dst_pitch pitch for moving to the next y line
911 static void ivi_output_plane(IVIPlaneDesc *plane, uint8_t *dst, ptrdiff_t dst_pitch)
914 const int16_t *src = plane->bands[0].buf;
915 ptrdiff_t pitch = plane->bands[0].pitch;
920 for (y = 0; y < plane->height; y++) {
922 int w = plane->width;
923 for (x = 0; x < w; x++) {
924 int t = src[x] + 128;
929 for (x = 0; x < w; x++)
930 dst[x] = av_clip_uint8(src[x] + 128);
936 static void *prepare_buf(IVI45DecContext *ctx, IVIBandDesc *band, int i)
938 if (ctx->pic_conf.luma_bands <= 1 && i == 2)
941 band->bufs[i] = av_mallocz(2 * band->bufsize);
942 return band->bufs[i];
946 * Decode an Indeo 4 or 5 band.
948 * @param[in,out] ctx ptr to the decoder context
949 * @param[in,out] band ptr to the band descriptor
950 * @param[in] avctx ptr to the AVCodecContext
951 * @return result code: 0 = OK, -1 = error
953 static int decode_band(IVI45DecContext *ctx,
954 IVIBandDesc *band, AVCodecContext *avctx)
956 int result, i, t, idx1, idx2, pos;
959 band->buf = prepare_buf(ctx, band, ctx->dst_buf);
961 av_log(avctx, AV_LOG_ERROR, "Band buffer points to no data!\n");
962 return AVERROR_INVALIDDATA;
964 if (ctx->is_indeo4 && ctx->frame_type == IVI4_FRAMETYPE_BIDIR) {
965 band->ref_buf = prepare_buf(ctx, band, ctx->b_ref_buf);
966 band->b_ref_buf = prepare_buf(ctx, band, ctx->ref_buf);
967 if (!band->b_ref_buf)
968 return AVERROR(ENOMEM);
970 band->ref_buf = prepare_buf(ctx, band, ctx->ref_buf);
974 return AVERROR(ENOMEM);
975 band->data_ptr = ctx->frame_data + (get_bits_count(&ctx->gb) >> 3);
977 result = ctx->decode_band_hdr(ctx, band, avctx);
979 av_log(avctx, AV_LOG_ERROR, "Error while decoding band header: %d\n",
984 if (band->is_empty) {
985 av_log(avctx, AV_LOG_ERROR, "Empty band encountered!\n");
986 return AVERROR_INVALIDDATA;
989 band->rv_map = &ctx->rvmap_tabs[band->rvmap_sel];
991 /* apply corrections to the selected rvmap table if present */
992 for (i = 0; i < band->num_corr; i++) {
993 idx1 = band->corr[i * 2];
994 idx2 = band->corr[i * 2 + 1];
995 FFSWAP(uint8_t, band->rv_map->runtab[idx1], band->rv_map->runtab[idx2]);
996 FFSWAP(int16_t, band->rv_map->valtab[idx1], band->rv_map->valtab[idx2]);
997 if (idx1 == band->rv_map->eob_sym || idx2 == band->rv_map->eob_sym)
998 band->rv_map->eob_sym ^= idx1 ^ idx2;
999 if (idx1 == band->rv_map->esc_sym || idx2 == band->rv_map->esc_sym)
1000 band->rv_map->esc_sym ^= idx1 ^ idx2;
1003 pos = get_bits_count(&ctx->gb);
1005 for (t = 0; t < band->num_tiles; t++) {
1006 tile = &band->tiles[t];
1008 if (tile->mb_size != band->mb_size) {
1009 av_log(avctx, AV_LOG_ERROR, "MB sizes mismatch: %d vs. %d\n",
1010 band->mb_size, tile->mb_size);
1011 return AVERROR_INVALIDDATA;
1013 tile->is_empty = get_bits1(&ctx->gb);
1014 if (tile->is_empty) {
1015 result = ivi_process_empty_tile(avctx, band, tile,
1016 (ctx->planes[0].bands[0].mb_size >> 3) - (band->mb_size >> 3));
1019 ff_dlog(avctx, "Empty tile encountered!\n");
1021 tile->data_size = ivi_dec_tile_data_size(&ctx->gb);
1022 if (!tile->data_size) {
1023 av_log(avctx, AV_LOG_ERROR, "Tile data size is zero!\n");
1024 result = AVERROR_INVALIDDATA;
1028 result = ctx->decode_mb_info(ctx, band, tile, avctx);
1032 result = ivi_decode_blocks(&ctx->gb, band, tile, avctx);
1034 av_log(avctx, AV_LOG_ERROR,
1035 "Corrupted tile data encountered!\n");
1039 if (((get_bits_count(&ctx->gb) - pos) >> 3) != tile->data_size) {
1040 av_log(avctx, AV_LOG_ERROR,
1041 "Tile data_size mismatch!\n");
1042 result = AVERROR_INVALIDDATA;
1046 pos += tile->data_size << 3; // skip to next tile
1050 /* restore the selected rvmap table by applying its corrections in
1052 for (i = band->num_corr-1; i >= 0; i--) {
1053 idx1 = band->corr[i*2];
1054 idx2 = band->corr[i*2+1];
1055 FFSWAP(uint8_t, band->rv_map->runtab[idx1], band->rv_map->runtab[idx2]);
1056 FFSWAP(int16_t, band->rv_map->valtab[idx1], band->rv_map->valtab[idx2]);
1057 if (idx1 == band->rv_map->eob_sym || idx2 == band->rv_map->eob_sym)
1058 band->rv_map->eob_sym ^= idx1 ^ idx2;
1059 if (idx1 == band->rv_map->esc_sym || idx2 == band->rv_map->esc_sym)
1060 band->rv_map->esc_sym ^= idx1 ^ idx2;
1064 if (band->checksum_present) {
1065 uint16_t chksum = ivi_calc_band_checksum(band);
1066 if (chksum != band->checksum) {
1067 av_log(avctx, AV_LOG_ERROR,
1068 "Band checksum mismatch! Plane %d, band %d, "
1069 "received: %"PRIx32", calculated: %"PRIx16"\n",
1070 band->plane, band->band_num, band->checksum, chksum);
1075 align_get_bits(&ctx->gb);
1080 int ff_ivi_decode_frame(AVCodecContext *avctx, void *data, int *got_frame,
1083 IVI45DecContext *ctx = avctx->priv_data;
1084 const uint8_t *buf = avpkt->data;
1085 AVFrame *frame = data;
1086 int buf_size = avpkt->size;
1089 result = init_get_bits8(&ctx->gb, buf, buf_size);
1092 ctx->frame_data = buf;
1093 ctx->frame_size = buf_size;
1095 result = ctx->decode_pic_hdr(ctx, avctx);
1097 av_log(avctx, AV_LOG_ERROR,
1098 "Error while decoding picture header: %d\n", result);
1101 if (ctx->gop_invalid)
1102 return AVERROR_INVALIDDATA;
1104 if (ctx->is_indeo4 && ctx->frame_type == IVI4_FRAMETYPE_NULL_LAST) {
1105 if (ctx->got_p_frame) {
1106 av_frame_move_ref(data, ctx->p_frame);
1108 ctx->got_p_frame = 0;
1115 if (ctx->gop_flags & IVI5_IS_PROTECTED) {
1116 avpriv_report_missing_feature(avctx, "Password-protected clip");
1117 return AVERROR_PATCHWELCOME;
1120 if (!ctx->planes[0].bands) {
1121 av_log(avctx, AV_LOG_ERROR, "Color planes not initialized yet\n");
1122 return AVERROR_INVALIDDATA;
1125 ctx->switch_buffers(ctx);
1129 if (ctx->is_nonnull_frame(ctx)) {
1130 ctx->buf_invalid[ctx->dst_buf] = 1;
1131 for (p = 0; p < 3; p++) {
1132 for (b = 0; b < ctx->planes[p].num_bands; b++) {
1133 result = decode_band(ctx, &ctx->planes[p].bands[b], avctx);
1135 av_log(avctx, AV_LOG_ERROR,
1136 "Error while decoding band: %d, plane: %d\n", b, p);
1141 ctx->buf_invalid[ctx->dst_buf] = 0;
1143 if (ctx->is_scalable)
1144 return AVERROR_INVALIDDATA;
1146 for (p = 0; p < 3; p++) {
1147 if (!ctx->planes[p].bands[0].buf)
1148 return AVERROR_INVALIDDATA;
1151 if (ctx->buf_invalid[ctx->dst_buf])
1154 //STOP_TIMER("decode_planes"); }
1156 if (!ctx->is_nonnull_frame(ctx))
1159 result = ff_set_dimensions(avctx, ctx->planes[0].width, ctx->planes[0].height);
1163 if ((result = ff_get_buffer(avctx, frame, 0)) < 0)
1166 if (ctx->is_scalable) {
1168 ff_ivi_recompose_haar(&ctx->planes[0], frame->data[0], frame->linesize[0]);
1170 ff_ivi_recompose53 (&ctx->planes[0], frame->data[0], frame->linesize[0]);
1172 ivi_output_plane(&ctx->planes[0], frame->data[0], frame->linesize[0]);
1175 ivi_output_plane(&ctx->planes[2], frame->data[1], frame->linesize[1]);
1176 ivi_output_plane(&ctx->planes[1], frame->data[2], frame->linesize[2]);
1180 /* If the bidirectional mode is enabled, next I and the following P
1181 * frame will be sent together. Unfortunately the approach below seems
1182 * to be the only way to handle the B-frames mode.
1183 * That's exactly the same Intel decoders do.
1185 if (ctx->is_indeo4 && ctx->frame_type == IVI4_FRAMETYPE_INTRA) {
1188 // skip version string
1189 while (get_bits(&ctx->gb, 8)) {
1190 if (get_bits_left(&ctx->gb) < 8)
1191 return AVERROR_INVALIDDATA;
1193 left = get_bits_count(&ctx->gb) & 0x18;
1194 skip_bits_long(&ctx->gb, 64 - left);
1195 if (get_bits_left(&ctx->gb) > 18 &&
1196 show_bits_long(&ctx->gb, 21) == 0xBFFF8) { // syncheader + inter type
1198 pkt.data = avpkt->data + (get_bits_count(&ctx->gb) >> 3);
1199 pkt.size = get_bits_left(&ctx->gb) >> 3;
1200 ff_ivi_decode_frame(avctx, ctx->p_frame, &ctx->got_p_frame, &pkt);
1204 if (ctx->show_indeo4_info) {
1205 if (ctx->is_scalable)
1206 av_log(avctx, AV_LOG_DEBUG, "This video uses scalability mode\n");
1207 if (ctx->uses_tiling)
1208 av_log(avctx, AV_LOG_DEBUG, "This video uses local decoding\n");
1209 if (ctx->has_b_frames)
1210 av_log(avctx, AV_LOG_DEBUG, "This video contains B-frames\n");
1211 if (ctx->has_transp)
1212 av_log(avctx, AV_LOG_DEBUG, "Transparency mode is enabled\n");
1214 av_log(avctx, AV_LOG_DEBUG, "This video uses Haar transform\n");
1215 if (ctx->uses_fullpel)
1216 av_log(avctx, AV_LOG_DEBUG, "This video uses fullpel motion vectors\n");
1217 ctx->show_indeo4_info = 0;
1224 * Close Indeo5 decoder and clean up its context.
1226 av_cold int ff_ivi_decode_close(AVCodecContext *avctx)
1228 IVI45DecContext *ctx = avctx->priv_data;
1230 ivi_free_buffers(&ctx->planes[0]);
1232 if (ctx->mb_vlc.cust_tab.table)
1233 ff_free_vlc(&ctx->mb_vlc.cust_tab);
1235 if (ctx->blk_vlc.cust_tab.table)
1236 ff_free_vlc(&ctx->blk_vlc.cust_tab);
1238 av_frame_free(&ctx->p_frame);
1245 * Scan patterns shared between indeo4 and indeo5
1247 const uint8_t ff_ivi_vertical_scan_8x8[64] = {
1248 0, 8, 16, 24, 32, 40, 48, 56,
1249 1, 9, 17, 25, 33, 41, 49, 57,
1250 2, 10, 18, 26, 34, 42, 50, 58,
1251 3, 11, 19, 27, 35, 43, 51, 59,
1252 4, 12, 20, 28, 36, 44, 52, 60,
1253 5, 13, 21, 29, 37, 45, 53, 61,
1254 6, 14, 22, 30, 38, 46, 54, 62,
1255 7, 15, 23, 31, 39, 47, 55, 63
1258 const uint8_t ff_ivi_horizontal_scan_8x8[64] = {
1259 0, 1, 2, 3, 4, 5, 6, 7,
1260 8, 9, 10, 11, 12, 13, 14, 15,
1261 16, 17, 18, 19, 20, 21, 22, 23,
1262 24, 25, 26, 27, 28, 29, 30, 31,
1263 32, 33, 34, 35, 36, 37, 38, 39,
1264 40, 41, 42, 43, 44, 45, 46, 47,
1265 48, 49, 50, 51, 52, 53, 54, 55,
1266 56, 57, 58, 59, 60, 61, 62, 63
1269 const uint8_t ff_ivi_direct_scan_4x4[16] = {
1270 0, 1, 4, 8, 5, 2, 3, 6, 9, 12, 13, 10, 7, 11, 14, 15
1275 * Run-value (RLE) tables.
1277 const RVMapDesc ff_ivi_rvmap_tabs[9] = {
1282 {1, 1, 0, 1, 1, 0, 1, 1, 2, 2, 1, 1, 1, 1, 3, 3,
1283 1, 1, 2, 2, 1, 1, 4, 4, 1, 1, 1, 1, 2, 2, 5, 5,
1284 1, 1, 3, 3, 1, 1, 6, 6, 1, 2, 1, 2, 7, 7, 1, 1,
1285 8, 8, 1, 1, 4, 2, 1, 4, 2, 1, 3, 3, 1, 1, 1, 9,
1286 9, 1, 2, 1, 2, 1, 5, 5, 1, 1, 10, 10, 1, 1, 3, 3,
1287 2, 2, 1, 1, 11, 11, 6, 4, 4, 1, 6, 1, 2, 1, 2, 12,
1288 8, 1, 12, 7, 8, 7, 1, 16, 1, 16, 1, 3, 3, 13, 1, 13,
1289 2, 2, 1, 15, 1, 5, 14, 15, 1, 5, 14, 1, 17, 8, 17, 8,
1290 1, 4, 4, 2, 2, 1, 25, 25, 24, 24, 1, 3, 1, 3, 1, 8,
1291 6, 7, 6, 1, 18, 8, 18, 1, 7, 23, 2, 2, 23, 1, 1, 21,
1292 22, 9, 9, 22, 19, 1, 21, 5, 19, 5, 1, 33, 20, 33, 20, 8,
1293 4, 4, 1, 32, 2, 2, 8, 3, 32, 26, 3, 1, 7, 7, 26, 6,
1294 1, 6, 1, 1, 16, 1, 10, 1, 10, 2, 16, 29, 28, 2, 29, 28,
1295 1, 27, 5, 8, 5, 27, 1, 8, 3, 7, 3, 31, 41, 31, 1, 41,
1296 6, 1, 6, 7, 4, 4, 1, 1, 2, 1, 2, 11, 34, 30, 11, 1,
1297 30, 15, 15, 34, 36, 40, 36, 40, 35, 35, 37, 37, 39, 39, 38, 38},
1300 { 1, -1, 0, 2, -2, 0, 3, -3, 1, -1, 4, -4, 5, -5, 1, -1,
1301 6, -6, 2, -2, 7, -7, 1, -1, 8, -8, 9, -9, 3, -3, 1, -1,
1302 10, -10, 2, -2, 11, -11, 1, -1, 12, 4, -12, -4, 1, -1, 13, -13,
1303 1, -1, 14, -14, 2, 5, 15, -2, -5, -15, -3, 3, 16, -16, 17, 1,
1304 -1, -17, 6, 18, -6, -18, 2, -2, 19, -19, 1, -1, 20, -20, 4, -4,
1305 7, -7, 21, -21, 1, -1, 2, 3, -3, 22, -2, -22, 8, 23, -8, 1,
1306 2, -23, -1, 2, -2, -2, 24, 1, -24, -1, 25, 5, -5, 1, -25, -1,
1307 9, -9, 26, 1, -26, 3, 1, -1, 27, -3, -1, -27, 1, 3, -1, -3,
1308 28, -4, 4, 10, -10, -28, 1, -1, 1, -1, 29, 6, -29, -6, 30, -4,
1309 3, 3, -3, -30, 1, 4, -1, 31, -3, 1, 11, -11, -1, -31, 32, -1,
1310 -1, 2, -2, 1, 1, -32, 1, 4, -1, -4, 33, -1, 1, 1, -1, 5,
1311 5, -5, -33, -1, -12, 12, -5, -7, 1, 1, 7, 34, 4, -4, -1, 4,
1312 -34, -4, 35, 36, -2, -35, -2, -36, 2, 13, 2, -1, 1, -13, 1, -1,
1313 37, 1, -5, 6, 5, -1, 38, -6, -8, 5, 8, -1, 1, 1, -37, -1,
1314 5, 39, -5, -5, 6, -6, -38, -39, -14, 40, 14, 2, 1, 1, -2, -40,
1315 -1, -2, 2, -1, -1, -1, 1, 1, 1, -1, 1, -1, 1, -1, 1, -1}
1321 {0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 8, 6, 8, 7,
1322 7, 9, 9, 10, 10, 11, 11, 1, 12, 1, 12, 13, 13, 16, 14, 16,
1323 14, 15, 15, 17, 17, 18, 0, 18, 19, 20, 21, 19, 22, 21, 20, 22,
1324 25, 24, 2, 25, 24, 23, 23, 2, 26, 28, 26, 28, 29, 27, 29, 27,
1325 33, 33, 1, 32, 1, 3, 32, 30, 36, 3, 36, 30, 31, 31, 35, 34,
1326 37, 41, 34, 35, 37, 4, 41, 4, 49, 8, 8, 49, 40, 38, 5, 38,
1327 40, 39, 5, 39, 42, 43, 42, 7, 57, 6, 43, 44, 6, 50, 7, 44,
1328 57, 48, 50, 48, 45, 45, 46, 47, 51, 46, 47, 58, 1, 51, 58, 1,
1329 52, 59, 53, 9, 52, 55, 55, 59, 53, 56, 54, 56, 54, 9, 64, 64,
1330 60, 63, 60, 63, 61, 62, 61, 62, 2, 10, 2, 10, 11, 1, 11, 13,
1331 12, 1, 12, 13, 16, 16, 8, 8, 14, 3, 3, 15, 14, 15, 4, 4,
1332 1, 17, 17, 5, 1, 7, 7, 5, 6, 1, 2, 2, 6, 22, 1, 25,
1333 21, 22, 8, 24, 1, 21, 25, 24, 8, 18, 18, 23, 9, 20, 23, 33,
1334 29, 33, 20, 1, 19, 1, 29, 36, 9, 36, 19, 41, 28, 57, 32, 3,
1335 28, 3, 1, 27, 49, 49, 1, 32, 26, 26, 2, 4, 4, 7, 57, 41,
1336 2, 7, 10, 5, 37, 16, 10, 27, 8, 8, 13, 16, 37, 13, 1, 5},
1339 {0, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, 1, -1, -1, 1,
1340 -1, 1, -1, 1, -1, 1, -1, 2, 1, -2, -1, 1, -1, 1, 1, -1,
1341 -1, 1, -1, 1, -1, 1, 0, -1, 1, 1, 1, -1, 1, -1, -1, -1,
1342 1, 1, 2, -1, -1, 1, -1, -2, 1, 1, -1, -1, 1, 1, -1, -1,
1343 1, -1, 3, 1, -3, 2, -1, 1, 1, -2, -1, -1, -1, 1, 1, 1,
1344 1, 1, -1, -1, -1, 2, -1, -2, 1, 2, -2, -1, 1, 1, 2, -1,
1345 -1, 1, -2, -1, 1, 1, -1, 2, 1, 2, -1, 1, -2, -1, -2, -1,
1346 -1, 1, 1, -1, 1, -1, 1, 1, 1, -1, -1, 1, 4, -1, -1, -4,
1347 1, 1, 1, 2, -1, -1, 1, -1, -1, 1, -1, -1, 1, -2, 1, -1,
1348 1, 1, -1, -1, 1, 1, -1, -1, 3, 2, -3, -2, 2, 5, -2, 2,
1349 2, -5, -2, -2, -2, 2, -3, 3, 2, 3, -3, 2, -2, -2, 3, -3,
1350 6, 2, -2, 3, -6, 3, -3, -3, 3, 7, -4, 4, -3, 2, -7, 2,
1351 2, -2, -4, 2, 8, -2, -2, -2, 4, 2, -2, 2, 3, 2, -2, -2,
1352 2, 2, -2, -8, -2, 9, -2, 2, -3, -2, 2, -2, 2, 2, 2, 4,
1353 -2, -4, 10, 2, 2, -2, -9, -2, 2, -2, 5, 4, -4, 4, -2, 2,
1354 -5, -4, -3, 4, 2, -3, 3, -2, -5, 5, 3, 3, -2, -3, -10, -4}
1360 {1, 1, 0, 2, 2, 1, 1, 3, 3, 4, 4, 0, 1, 1, 5, 5,
1361 2, 2, 6, 6, 7, 7, 1, 8, 1, 8, 3, 3, 9, 9, 1, 2,
1362 2, 1, 4, 10, 4, 10, 11, 11, 1, 5, 12, 12, 1, 5, 13, 13,
1363 3, 3, 6, 6, 2, 2, 14, 14, 16, 16, 15, 7, 15, 8, 8, 7,
1364 1, 1, 17, 17, 4, 4, 1, 1, 18, 18, 2, 2, 5, 5, 25, 3,
1365 9, 3, 25, 9, 19, 24, 19, 24, 1, 21, 20, 1, 21, 22, 20, 22,
1366 23, 23, 8, 6, 33, 6, 8, 33, 7, 7, 26, 26, 1, 32, 1, 32,
1367 28, 4, 28, 10, 29, 27, 27, 10, 41, 4, 29, 2, 2, 41, 36, 31,
1368 49, 31, 34, 30, 34, 36, 30, 35, 1, 49, 11, 5, 35, 11, 1, 3,
1369 3, 5, 37, 37, 8, 40, 8, 40, 12, 12, 42, 42, 1, 38, 16, 57,
1370 1, 6, 16, 39, 38, 6, 7, 7, 13, 13, 39, 43, 2, 43, 57, 2,
1371 50, 9, 44, 9, 50, 4, 15, 48, 44, 4, 1, 15, 48, 14, 14, 1,
1372 45, 45, 8, 3, 5, 8, 51, 47, 3, 46, 46, 47, 5, 51, 1, 17,
1373 17, 58, 1, 58, 2, 52, 52, 2, 53, 7, 59, 6, 6, 56, 53, 55,
1374 7, 55, 1, 54, 59, 56, 54, 10, 1, 10, 4, 60, 1, 60, 8, 4,
1375 8, 64, 64, 61, 1, 63, 3, 63, 62, 61, 5, 11, 5, 3, 11, 62},
1378 { 1, -1, 0, 1, -1, 2, -2, 1, -1, 1, -1, 0, 3, -3, 1, -1,
1379 2, -2, 1, -1, 1, -1, 4, 1, -4, -1, 2, -2, 1, -1, 5, 3,
1380 -3, -5, 2, 1, -2, -1, 1, -1, 6, 2, 1, -1, -6, -2, 1, -1,
1381 3, -3, 2, -2, 4, -4, 1, -1, 1, -1, 1, 2, -1, 2, -2, -2,
1382 7, -7, 1, -1, 3, -3, 8, -8, 1, -1, 5, -5, 3, -3, 1, 4,
1383 2, -4, -1, -2, 1, 1, -1, -1, 9, 1, 1, -9, -1, 1, -1, -1,
1384 1, -1, 3, -3, 1, 3, -3, -1, 3, -3, 1, -1, 10, 1, -10, -1,
1385 1, 4, -1, 2, 1, -1, 1, -2, 1, -4, -1, 6, -6, -1, 1, 1,
1386 1, -1, 1, 1, -1, -1, -1, 1, 11, -1, -2, 4, -1, 2, -11, 5,
1387 -5, -4, -1, 1, 4, 1, -4, -1, -2, 2, 1, -1, 12, 1, -2, 1,
1388 -12, 4, 2, 1, -1, -4, 4, -4, 2, -2, -1, 1, 7, -1, -1, -7,
1389 -1, -3, 1, 3, 1, 5, 2, 1, -1, -5, 13, -2, -1, 2, -2, -13,
1390 1, -1, 5, 6, 5, -5, 1, 1, -6, 1, -1, -1, -5, -1, 14, 2,
1391 -2, 1, -14, -1, 8, 1, -1, -8, 1, 5, 1, 5, -5, 1, -1, 1,
1392 -5, -1, 15, 1, -1, -1, -1, 3, -15, -3, 6, 1, 16, -1, 6, -6,
1393 -6, 1, -1, 1, -16, 1, 7, -1, 1, -1, -6, -3, 6, -7, 3, -1}
1399 {0, 1, 1, 2, 2, 3, 3, 4, 4, 1, 1, 5, 5, 6, 6, 7,
1400 7, 8, 8, 9, 9, 2, 2, 10, 10, 1, 1, 11, 11, 12, 12, 3,
1401 3, 13, 13, 0, 14, 14, 16, 15, 16, 15, 4, 4, 17, 1, 17, 1,
1402 5, 5, 18, 18, 2, 2, 6, 6, 8, 19, 7, 8, 7, 19, 20, 20,
1403 21, 21, 22, 24, 22, 24, 23, 23, 1, 1, 25, 25, 3, 3, 26, 26,
1404 9, 9, 27, 27, 28, 28, 33, 29, 4, 33, 29, 1, 4, 1, 32, 32,
1405 2, 2, 31, 10, 30, 10, 30, 31, 34, 34, 5, 5, 36, 36, 35, 41,
1406 35, 11, 41, 11, 37, 1, 8, 8, 37, 6, 1, 6, 40, 7, 7, 40,
1407 12, 38, 12, 39, 39, 38, 49, 13, 49, 13, 3, 42, 3, 42, 16, 16,
1408 43, 43, 14, 14, 1, 1, 44, 15, 44, 15, 2, 2, 57, 48, 50, 48,
1409 57, 50, 4, 45, 45, 4, 46, 47, 47, 46, 1, 51, 1, 17, 17, 51,
1410 8, 9, 9, 5, 58, 8, 58, 5, 52, 52, 55, 56, 53, 56, 55, 59,
1411 59, 53, 54, 1, 6, 54, 7, 7, 6, 1, 2, 3, 2, 3, 64, 60,
1412 60, 10, 10, 64, 61, 62, 61, 63, 1, 63, 62, 1, 18, 24, 18, 4,
1413 25, 4, 8, 21, 21, 1, 24, 22, 25, 22, 8, 11, 19, 11, 23, 1,
1414 20, 23, 19, 20, 5, 12, 5, 1, 16, 2, 12, 13, 2, 13, 1, 16},
1417 { 0, 1, -1, 1, -1, 1, -1, 1, -1, 2, -2, 1, -1, 1, -1, 1,
1418 -1, 1, -1, 1, -1, 2, -2, 1, -1, 3, -3, 1, -1, 1, -1, 2,
1419 -2, 1, -1, 0, 1, -1, 1, 1, -1, -1, 2, -2, 1, 4, -1, -4,
1420 2, -2, 1, -1, -3, 3, 2, -2, 2, 1, 2, -2, -2, -1, 1, -1,
1421 1, -1, 1, 1, -1, -1, 1, -1, 5, -5, 1, -1, 3, -3, 1, -1,
1422 2, -2, 1, -1, 1, -1, 1, 1, 3, -1, -1, 6, -3, -6, -1, 1,
1423 4, -4, 1, 2, 1, -2, -1, -1, 1, -1, 3, -3, 1, -1, 1, 1,
1424 -1, 2, -1, -2, 1, 7, -3, 3, -1, 3, -7, -3, 1, -3, 3, -1,
1425 2, 1, -2, 1, -1, -1, 1, 2, -1, -2, -4, -1, 4, 1, 2, -2,
1426 1, -1, -2, 2, 8, -8, -1, 2, 1, -2, -5, 5, 1, -1, -1, 1,
1427 -1, 1, 4, -1, 1, -4, -1, -1, 1, 1, 9, 1, -9, 2, -2, -1,
1428 -4, 3, -3, -4, -1, 4, 1, 4, 1, -1, 1, -1, 1, 1, -1, 1,
1429 -1, -1, -1, 10, 4, 1, 4, -4, -4, -10, 6, 5, -6, -5, 1, -1,
1430 1, 3, -3, -1, 1, -1, -1, -1, 11, 1, 1, -11, -2, -2, 2, 5,
1431 -2, -5, -5, 2, -2, 12, 2, -2, 2, 2, 5, -3, -2, 3, -2, -12,
1432 -2, 2, 2, 2, -5, 3, 5, 13, -3, 7, -3, -3, -7, 3, -13, 3}
1438 {0, 1, 1, 1, 2, 2, 1, 3, 3, 1, 1, 1, 4, 4, 1, 5,
1439 2, 1, 5, 2, 1, 1, 6, 6, 1, 1, 1, 1, 1, 7, 3, 1,
1440 2, 3, 0, 1, 2, 7, 1, 1, 1, 8, 1, 1, 8, 1, 1, 1,
1441 9, 1, 9, 1, 2, 1, 1, 2, 1, 1, 10, 4, 1, 10, 1, 4,
1442 1, 1, 1, 1, 1, 3, 1, 1, 1, 3, 2, 1, 5, 1, 1, 1,
1443 2, 5, 1, 11, 1, 11, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1444 2, 1, 6, 1, 6, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 12,
1445 3, 1, 12, 1, 1, 1, 2, 1, 1, 3, 1, 1, 1, 1, 1, 1,
1446 4, 1, 1, 1, 2, 1, 1, 4, 1, 1, 1, 1, 1, 1, 2, 1,
1447 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 2, 1, 1, 5,
1448 1, 1, 1, 1, 1, 7, 1, 7, 1, 1, 2, 3, 1, 1, 1, 1,
1449 5, 1, 1, 1, 1, 1, 1, 2, 13, 1, 1, 1, 1, 1, 1, 1,
1450 1, 1, 1, 1, 1, 1, 1, 1, 13, 2, 1, 1, 4, 1, 1, 1,
1451 3, 1, 6, 1, 1, 1, 14, 1, 1, 1, 1, 1, 14, 6, 1, 1,
1452 1, 1, 15, 2, 4, 1, 2, 3, 15, 1, 1, 1, 8, 1, 1, 8,
1453 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1},
1456 { 0, 1, -1, 2, 1, -1, -2, 1, -1, 3, -3, 4, 1, -1, -4, 1,
1457 2, 5, -1, -2, -5, 6, 1, -1, -6, 7, -7, 8, -8, 1, 2, 9,
1458 3, -2, 0, -9, -3, -1, 10, -10, 11, 1, -11, 12, -1, -12, 13, -13,
1459 1, 14, -1, -14, 4, 15, -15, -4, 16, -16, 1, 2, 17, -1, -17, -2,
1460 18, -18, 19, -19, 20, 3, -20, 21, -21, -3, 5, 22, 2, -22, -23, 23,
1461 -5, -2, 24, 1, -24, -1, 25, -25, 26, -26, -27, 27, 28, 29, -28, -29,
1462 6, 30, 2, -31, -2, -30, 31, -6, -32, 32, 33, -33, 34, -35, -34, 1,
1463 4, -36, -1, 35, 37, 36, 7, -37, 38, -4, -38, 39, 41, 40, -40, -39,
1464 3, 42, -43, -41, -7, -42, 43, -3, 44, -44, 45, -45, 46, 47, 8, -47,
1465 -48, -46, 50, -50, 48, 49, 51, -49, 52, -52, 5, -51, -8, -53, 53, 3,
1466 -56, 56, 55, 54, -54, 2, 60, -2, -55, 58, 9, -5, 59, 57, -57, -63,
1467 -3, -58, -60, -61, 61, -59, -62, -9, 1, 64, 62, 69, -64, 63, 65, -67,
1468 -68, 66, -65, 68, -66, -69, 67, -70, -1, 10, 71, -71, 4, 73, 72, 70,
1469 6, -76, -3, 74, -78, -74, 1, 78, 80, -72, -75, 76, -1, 3, -73, 79,
1470 75, 77, 1, 11, -4, -79, -10, -6, -1, -77, -83, -80, 2, 81, -84, -2,
1471 83, -81, 82, -82, 84, -87, -86, 85, -11, -85, 86, -89, 87, -88, 88, 89}
1477 {1, 1, 0, 2, 1, 2, 1, 3, 3, 1, 1, 4, 4, 2, 2, 1,
1478 1, 5, 5, 6, 1, 6, 1, 7, 7, 3, 3, 2, 8, 2, 8, 1,
1479 1, 0, 9, 9, 1, 1, 10, 4, 10, 4, 11, 11, 2, 1, 2, 1,
1480 12, 12, 3, 3, 1, 1, 13, 5, 5, 13, 14, 1, 1, 14, 2, 2,
1481 6, 6, 15, 1, 1, 15, 16, 4, 7, 16, 4, 7, 1, 1, 3, 3,
1482 8, 8, 2, 2, 1, 1, 17, 17, 1, 1, 18, 18, 5, 5, 2, 2,
1483 1, 1, 9, 19, 9, 19, 20, 3, 3, 20, 1, 10, 21, 1, 10, 4,
1484 4, 21, 22, 6, 6, 22, 1, 1, 23, 24, 2, 2, 23, 24, 11, 1,
1485 1, 11, 7, 25, 7, 1, 1, 25, 8, 8, 3, 26, 3, 1, 12, 2,
1486 2, 26, 1, 12, 5, 5, 27, 4, 1, 4, 1, 27, 28, 1, 28, 13,
1487 1, 13, 2, 29, 2, 1, 32, 6, 1, 30, 14, 29, 14, 6, 3, 31,
1488 3, 1, 30, 1, 32, 31, 33, 9, 33, 1, 1, 7, 9, 7, 2, 2,
1489 1, 1, 4, 36, 34, 4, 5, 10, 10, 5, 34, 1, 1, 35, 8, 8,
1490 36, 3, 35, 1, 15, 3, 2, 1, 16, 15, 16, 2, 37, 1, 37, 1,
1491 1, 1, 6, 6, 38, 1, 38, 11, 1, 39, 39, 40, 11, 2, 41, 4,
1492 40, 1, 2, 4, 1, 1, 1, 41, 3, 1, 3, 1, 5, 7, 5, 7},
1495 { 1, -1, 0, 1, 2, -1, -2, 1, -1, 3, -3, 1, -1, 2, -2, 4,
1496 -4, 1, -1, 1, 5, -1, -5, 1, -1, 2, -2, 3, 1, -3, -1, 6,
1497 -6, 0, 1, -1, 7, -7, 1, 2, -1, -2, 1, -1, 4, 8, -4, -8,
1498 1, -1, 3, -3, 9, -9, 1, 2, -2, -1, 1, 10, -10, -1, 5, -5,
1499 2, -2, 1, 11, -11, -1, 1, 3, 2, -1, -3, -2, 12, -12, 4, -4,
1500 2, -2, -6, 6, 13, -13, 1, -1, 14, -14, 1, -1, 3, -3, 7, -7,
1501 15, -15, 2, 1, -2, -1, 1, 5, -5, -1, -16, 2, 1, 16, -2, 4,
1502 -4, -1, 1, 3, -3, -1, 17, -17, 1, 1, -8, 8, -1, -1, 2, 18,
1503 -18, -2, 3, 1, -3, 19, -19, -1, 3, -3, 6, 1, -6, 20, 2, 9,
1504 -9, -1, -20, -2, 4, -4, 1, -5, 21, 5, -21, -1, 1, -22, -1, 2,
1505 22, -2, 10, 1, -10, 23, 1, 4, -23, 1, 2, -1, -2, -4, -7, 1,
1506 7, -24, -1, 24, -1, -1, 1, 3, -1, -25, 25, 4, -3, -4, 11, -11,
1507 26, -26, 6, 1, 1, -6, -5, -3, 3, 5, -1, -27, 27, 1, 4, -4,
1508 -1, -8, -1, 28, 2, 8, -12, -28, -2, -2, 2, 12, -1, 29, 1, -29,
1509 30, -30, 5, -5, 1, -31, -1, 3, 31, -1, 1, 1, -3, -13, 1, -7,
1510 -1, -32, 13, 7, 32, 33, -33, -1, -9, -34, 9, 34, -6, 5, 6, -5}
1516 {1, 1, 0, 1, 1, 2, 2, 1, 1, 3, 3, 1, 1, 0, 2, 2,
1517 4, 1, 4, 1, 1, 1, 5, 5, 1, 1, 6, 6, 2, 2, 1, 1,
1518 3, 3, 7, 7, 1, 1, 8, 8, 1, 1, 2, 2, 1, 9, 1, 9,
1519 4, 4, 10, 1, 1, 10, 1, 1, 11, 11, 3, 3, 1, 2, 1, 2,
1520 1, 1, 12, 12, 5, 5, 1, 1, 13, 1, 1, 13, 2, 2, 1, 1,
1521 6, 6, 1, 1, 4, 14, 4, 14, 3, 1, 3, 1, 1, 1, 15, 7,
1522 15, 2, 2, 7, 1, 1, 1, 8, 1, 8, 16, 16, 1, 1, 1, 1,
1523 2, 1, 1, 2, 1, 1, 3, 5, 5, 3, 4, 1, 1, 4, 1, 1,
1524 17, 17, 9, 1, 1, 9, 2, 2, 1, 1, 10, 10, 1, 6, 1, 1,
1525 6, 18, 1, 1, 18, 1, 1, 1, 2, 2, 3, 1, 3, 1, 1, 1,
1526 4, 1, 19, 1, 19, 7, 1, 1, 20, 1, 4, 20, 1, 7, 11, 2,
1527 1, 11, 21, 2, 8, 5, 1, 8, 1, 5, 21, 1, 1, 1, 22, 1,
1528 1, 22, 1, 1, 3, 3, 1, 23, 2, 12, 24, 1, 1, 2, 1, 1,
1529 12, 23, 1, 1, 24, 1, 1, 1, 4, 1, 1, 1, 2, 1, 6, 6,
1530 4, 2, 1, 1, 1, 1, 1, 1, 1, 14, 13, 3, 1, 25, 9, 25,
1531 14, 1, 9, 3, 13, 1, 1, 1, 1, 1, 10, 1, 1, 2, 10, 2},
1534 {-20, -1, 0, 2, -2, 1, -1, 3, -3, 1, -1, 4, -4, 0, 2, -2,
1535 1, 5, -1, -5, 6, -6, 1, -1, 7, -7, 1, -1, 3, -3, 8, -8,
1536 2, -2, 1, -1, 9, -9, 1, -1, 10, -10, 4, -4, 11, 1, -11, -1,
1537 2, -2, 1, 12, -12, -1, 13, -13, 1, -1, 3, -3, 14, 5, -14, -5,
1538 -15, 15, -1, 1, 2, -2, 16, -16, 1, 17, -17, -1, 6, -6, 18, -18,
1539 2, -2, -19, 19, -3, 1, 3, -1, 4, 20, -4, 1, -21, 21, 1, 2,
1540 -1, -7, 7, -2, 22, -22, 23, 2, -23, -2, 1, -1, -24, 24, -25, 25,
1541 -8, -26, 26, 8, -27, 27, 5, 3, -3, -5, -4, 28, -28, 4, 29, -29,
1542 1, -1, -2, -30, 30, 2, 9, -9, -31, 31, 2, -2, -32, 3, 32, -33,
1543 -3, 1, 33, -34, -1, 34, -35, 35, -10, 10, -6, 36, 6, -36, 37, -37,
1544 -5, 38, 1, -38, -1, 3, 39, -39, -1, 40, 5, 1, -40, -3, 2, -11,
1545 -41, -2, 1, 11, -3, -4, 41, 3, 42, 4, -1, -43, -42, 43, 1, -44,
1546 45, -1, 44, -45, -7, 7, -46, 1, -12, 2, 1, -47, 46, 12, 47, 48,
1547 -2, -1, -48, 49, -1, -50, -49, 50, -6, -51, 51, 52, -13, 53, -4, 4,
1548 6, 13, -53, -52, -54, 55, 54, -55, -56, -2, 2, -8, 56, 1, -3, -1,
1549 2, 58, 3, 8, -2, 57, -58, -60, -59, -57, -3, 60, 59, -14, 3, 14}
1555 {1, 1, 0, 2, 2, 1, 1, 3, 3, 4, 4, 5, 5, 1, 1, 6,
1556 6, 2, 2, 7, 7, 8, 8, 1, 1, 3, 3, 9, 9, 10, 10, 1,
1557 1, 2, 2, 4, 4, 11, 0, 11, 12, 12, 13, 13, 1, 1, 5, 5,
1558 14, 14, 15, 16, 15, 16, 3, 3, 1, 6, 1, 6, 2, 2, 7, 7,
1559 8, 8, 17, 17, 1, 1, 4, 4, 18, 18, 2, 2, 1, 19, 1, 20,
1560 19, 20, 21, 21, 3, 3, 22, 22, 5, 5, 24, 1, 1, 23, 9, 23,
1561 24, 9, 2, 2, 10, 1, 1, 10, 6, 6, 25, 4, 4, 25, 7, 7,
1562 26, 8, 1, 8, 3, 1, 26, 3, 11, 11, 27, 27, 2, 28, 1, 2,
1563 28, 1, 12, 12, 5, 5, 29, 13, 13, 29, 32, 1, 1, 33, 31, 30,
1564 32, 4, 30, 33, 4, 31, 3, 14, 1, 1, 3, 34, 34, 2, 2, 14,
1565 6, 6, 35, 36, 35, 36, 1, 15, 1, 16, 16, 15, 7, 9, 7, 9,
1566 37, 8, 8, 37, 1, 1, 39, 2, 38, 39, 2, 40, 5, 38, 40, 5,
1567 3, 3, 4, 4, 10, 10, 1, 1, 1, 1, 41, 2, 41, 2, 6, 6,
1568 1, 1, 11, 42, 11, 43, 3, 42, 3, 17, 4, 43, 1, 17, 7, 1,
1569 8, 44, 4, 7, 44, 5, 8, 2, 5, 1, 2, 48, 45, 1, 12, 45,
1570 12, 48, 13, 13, 1, 9, 9, 46, 1, 46, 47, 47, 49, 18, 18, 49},
1573 { 1, -1, 0, 1, -1, 2, -2, 1, -1, 1, -1, 1, -1, 3, -3, 1,
1574 -1, -2, 2, 1, -1, 1, -1, 4, -4, -2, 2, 1, -1, 1, -1, 5,
1575 -5, -3, 3, 2, -2, 1, 0, -1, 1, -1, 1, -1, 6, -6, 2, -2,
1576 1, -1, 1, 1, -1, -1, -3, 3, 7, 2, -7, -2, -4, 4, 2, -2,
1577 2, -2, 1, -1, 8, -8, 3, -3, 1, -1, -5, 5, 9, 1, -9, 1,
1578 -1, -1, 1, -1, -4, 4, 1, -1, 3, -3, 1, -10, 10, 1, 2, -1,
1579 -1, -2, 6, -6, 2, 11, -11, -2, 3, -3, 1, -4, 4, -1, 3, -3,
1580 1, 3, 12, -3, -5, -12, -1, 5, 2, -2, 1, -1, -7, 1, 13, 7,
1581 -1, -13, 2, -2, 4, -4, 1, 2, -2, -1, 1, 14, -14, 1, 1, 1,
1582 -1, -5, -1, -1, 5, -1, -6, 2, -15, 15, 6, 1, -1, -8, 8, -2,
1583 -4, 4, 1, 1, -1, -1, 16, 2, -16, -2, 2, -2, 4, 3, -4, -3,
1584 -1, -4, 4, 1, -17, 17, -1, -9, 1, 1, 9, 1, -5, -1, -1, 5,
1585 -7, 7, 6, -6, 3, -3, 18, -18, 19, -19, 1, -10, -1, 10, -5, 5,
1586 20, -20, -3, 1, 3, 1, 8, -1, -8, 2, 7, -1, -21, -2, 5, 21,
1587 5, -1, -7, -5, 1, -6, -5, -11, 6, 22, 11, 1, 1, -22, -3, -1,
1588 3, -1, 3, -3, -23, 4, -4, 1, 23, -1, 1, -1, 1, -2, 2, -1}
1594 {1, 1, 1, 1, 0, 2, 2, 1, 1, 3, 3, 0, 1, 1, 2, 2,
1595 4, 4, 1, 1, 5, 5, 1, 1, 2, 2, 3, 3, 6, 6, 1, 1,
1596 7, 7, 8, 1, 8, 2, 2, 1, 4, 4, 1, 3, 1, 3, 9, 9,
1597 2, 2, 1, 5, 1, 5, 10, 10, 1, 1, 11, 11, 3, 6, 3, 4,
1598 4, 6, 2, 2, 1, 12, 1, 12, 7, 13, 7, 13, 1, 1, 8, 8,
1599 2, 2, 14, 14, 16, 15, 16, 5, 5, 1, 3, 15, 1, 3, 4, 4,
1600 1, 1, 17, 17, 2, 2, 6, 6, 1, 18, 1, 18, 22, 21, 22, 21,
1601 25, 24, 25, 19, 9, 20, 9, 23, 19, 24, 20, 3, 23, 7, 3, 1,
1602 1, 7, 28, 26, 29, 5, 28, 26, 5, 8, 29, 4, 8, 27, 2, 2,
1603 4, 27, 1, 1, 10, 36, 10, 33, 33, 36, 30, 1, 32, 32, 1, 30,
1604 6, 31, 31, 35, 3, 6, 11, 11, 3, 2, 35, 2, 34, 1, 34, 1,
1605 37, 37, 12, 7, 12, 5, 41, 5, 4, 7, 1, 8, 13, 4, 1, 41,
1606 13, 38, 8, 38, 9, 1, 40, 40, 9, 1, 39, 2, 2, 49, 39, 42,
1607 3, 3, 14, 16, 49, 14, 16, 42, 43, 43, 6, 6, 15, 1, 1, 15,
1608 44, 44, 1, 1, 50, 48, 4, 5, 4, 7, 5, 2, 10, 10, 48, 7,
1609 50, 45, 2, 1, 45, 8, 8, 1, 46, 46, 3, 47, 47, 3, 1, 1},
1612 { 1, -1, 2, -2, 0, 1, -1, 3, -3, 1, -1, 0, 4, -4, 2, -2,
1613 1, -1, 5, -5, 1, -1, 6, -6, 3, -3, 2, -2, 1, -1, 7, -7,
1614 1, -1, 1, 8, -1, 4, -4, -8, 2, -2, 9, 3, -9, -3, 1, -1,
1615 5, -5, 10, 2, -10, -2, 1, -1, 11, -11, 1, -1, -4, 2, 4, 3,
1616 -3, -2, 6, -6, 12, 1, -12, -1, 2, 1, -2, -1, 13, -13, 2, -2,
1617 7, -7, 1, -1, 1, 1, -1, 3, -3, 14, 5, -1, -14, -5, 4, -4,
1618 15, -15, 1, -1, 8, -8, -3, 3, 16, 1, -16, -1, 1, 1, -1, -1,
1619 1, 1, -1, 1, 2, 1, -2, 1, -1, -1, -1, 6, -1, 3, -6, 17,
1620 -17, -3, 1, 1, 1, 4, -1, -1, -4, 3, -1, 5, -3, -1, -9, 9,
1621 -5, 1, 18, -18, 2, 1, -2, 1, -1, -1, 1, 19, -1, 1, -19, -1,
1622 4, 1, -1, 1, 7, -4, -2, 2, -7, 10, -1, -10, 1, 20, -1, -20,
1623 1, -1, 2, 4, -2, 5, 1, -5, 6, -4, 21, 4, 2, -6, -21, -1,
1624 -2, 1, -4, -1, -3, 22, -1, 1, 3, -22, -1, 11, -11, 1, 1, 1,
1625 8, -8, 2, 2, -1, -2, -2, -1, 1, -1, -5, 5, 2, 23, -23, -2,
1626 1, -1, 24, -24, -1, -1, 7, 6, -7, 5, -6, 12, -3, 3, 1, -5,
1627 1, 1, -12, 25, -1, -5, 5, -25, -1, 1, 9, 1, -1, -9, 26, -26}