2 * common functions for Indeo Video Interactive codecs (Indeo4 and Indeo5)
4 * Copyright (c) 2009 Maxim Poliakovski
6 * This file is part of Libav.
8 * Libav 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 * Libav 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 Libav; 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/timer.h"
34 #define BITSTREAM_READER_LE
36 #include "bitstream.h"
43 * These are 2x8 predefined Huffman codebooks for coding macroblock/block
44 * signals. They are specified using "huffman descriptors" in order to
45 * avoid huge static tables. The decoding tables will be generated at
46 * startup from these descriptors.
48 /** static macroblock huffman tables */
49 static const IVIHuffDesc ivi_mb_huff_desc[8] = {
50 {8, {0, 4, 5, 4, 4, 4, 6, 6}},
51 {12, {0, 2, 2, 3, 3, 3, 3, 5, 3, 2, 2, 2}},
52 {12, {0, 2, 3, 4, 3, 3, 3, 3, 4, 3, 2, 2}},
53 {12, {0, 3, 4, 4, 3, 3, 3, 3, 3, 2, 2, 2}},
54 {13, {0, 4, 4, 3, 3, 3, 3, 2, 3, 3, 2, 1, 1}},
55 {9, {0, 4, 4, 4, 4, 3, 3, 3, 2}},
56 {10, {0, 4, 4, 4, 4, 3, 3, 2, 2, 2}},
57 {12, {0, 4, 4, 4, 3, 3, 2, 3, 2, 2, 2, 2}}
60 /** static block huffman tables */
61 static const IVIHuffDesc ivi_blk_huff_desc[8] = {
62 {10, {1, 2, 3, 4, 4, 7, 5, 5, 4, 1}},
63 {11, {2, 3, 4, 4, 4, 7, 5, 4, 3, 3, 2}},
64 {12, {2, 4, 5, 5, 5, 5, 6, 4, 4, 3, 1, 1}},
65 {13, {3, 3, 4, 4, 5, 6, 6, 4, 4, 3, 2, 1, 1}},
66 {11, {3, 4, 4, 5, 5, 5, 6, 5, 4, 2, 2}},
67 {13, {3, 4, 5, 5, 5, 5, 6, 4, 3, 3, 2, 1, 1}},
68 {13, {3, 4, 5, 5, 5, 6, 5, 4, 3, 3, 2, 1, 1}},
69 {9, {3, 4, 4, 5, 5, 5, 6, 5, 5}}
72 static VLC ivi_mb_vlc_tabs [8]; ///< static macroblock Huffman tables
73 static VLC ivi_blk_vlc_tabs[8]; ///< static block Huffman tables
75 typedef void (*ivi_mc_func) (int16_t *buf, const int16_t *ref_buf,
76 ptrdiff_t pitch, int mc_type);
77 typedef void (*ivi_mc_avg_func) (int16_t *buf, const int16_t *ref_buf1,
78 const int16_t *ref_buf2,
79 ptrdiff_t pitch, int mc_type, int mc_type2);
81 static int ivi_mc(IVIBandDesc *band, ivi_mc_func mc, ivi_mc_avg_func mc_avg,
82 int offs, int mv_x, int mv_y, int mv_x2, int mv_y2,
83 int mc_type, int mc_type2)
85 int ref_offs = offs + mv_y * band->pitch + mv_x;
86 int buf_size = band->pitch * band->aheight;
87 int min_size = band->pitch * (band->blk_size - 1) + band->blk_size;
88 int ref_size = (mc_type > 1) * band->pitch + (mc_type & 1);
91 if (offs < 0 || ref_offs < 0 || !band->ref_buf)
92 return AVERROR_INVALIDDATA;
93 if (buf_size - min_size < offs)
94 return AVERROR_INVALIDDATA;
95 if (buf_size - min_size - ref_size < ref_offs)
96 return AVERROR_INVALIDDATA;
100 mc(band->buf + offs, band->ref_buf + ref_offs, band->pitch, mc_type);
102 int ref_offs2 = offs + mv_y2 * band->pitch + mv_x2;
103 int ref_size2 = (mc_type2 > 1) * band->pitch + (mc_type2 & 1);
104 if (offs < 0 || ref_offs2 < 0 || !band->b_ref_buf)
105 return AVERROR_INVALIDDATA;
106 if (buf_size - min_size - ref_size2 < ref_offs2)
107 return AVERROR_INVALIDDATA;
110 mc(band->buf + offs, band->b_ref_buf + ref_offs2,
111 band->pitch, mc_type2);
113 mc_avg(band->buf + offs, band->ref_buf + ref_offs,
114 band->b_ref_buf + ref_offs2, band->pitch,
122 * Reverse "nbits" bits of the value "val" and return the result
123 * in the least significant bits.
125 static uint16_t inv_bits(uint16_t val, int nbits)
130 res = ff_reverse[val] >> (8 - nbits);
132 res = ((ff_reverse[val & 0xFF] << 8) +
133 (ff_reverse[val >> 8])) >> (16 - nbits);
139 * Generate a huffman codebook from the given descriptor
140 * and convert it into the Libav VLC table.
142 * @param[in] cb pointer to codebook descriptor
143 * @param[out] vlc where to place the generated VLC table
144 * @param[in] flag flag: 1 - for static or 0 for dynamic tables
145 * @return result code: 0 - OK, -1 = error (invalid codebook descriptor)
147 static int ivi_create_huff_from_desc(const IVIHuffDesc *cb, VLC *vlc, int flag)
149 int pos, i, j, codes_per_row, prefix, not_last_row;
150 uint16_t codewords[256]; /* FIXME: move this temporal storage out? */
153 pos = 0; /* current position = 0 */
155 for (i = 0; i < cb->num_rows; i++) {
156 codes_per_row = 1 << cb->xbits[i];
157 not_last_row = (i != cb->num_rows - 1);
158 prefix = ((1 << i) - 1) << (cb->xbits[i] + not_last_row);
160 for (j = 0; j < codes_per_row; j++) {
161 if (pos >= 256) /* Some Indeo5 codebooks can have more than 256 */
162 break; /* elements, but only 256 codes are allowed! */
164 bits[pos] = i + cb->xbits[i] + not_last_row;
165 if (bits[pos] > IVI_VLC_BITS)
166 return AVERROR_INVALIDDATA; /* invalid descriptor */
168 codewords[pos] = inv_bits((prefix | j), bits[pos]);
176 /* number of codewords = pos */
177 return init_vlc(vlc, IVI_VLC_BITS, pos, bits, 1, 1, codewords, 2, 2,
178 (flag ? INIT_VLC_USE_NEW_STATIC : 0) | INIT_VLC_LE);
181 av_cold void ff_ivi_init_static_vlc(void)
184 static VLC_TYPE table_data[8192 * 16][2];
185 static int initialized_vlcs = 0;
187 if (initialized_vlcs)
189 for (i = 0; i < 8; i++) {
190 ivi_mb_vlc_tabs[i].table = table_data + i * 2 * 8192;
191 ivi_mb_vlc_tabs[i].table_allocated = 8192;
192 ivi_create_huff_from_desc(&ivi_mb_huff_desc[i],
193 &ivi_mb_vlc_tabs[i], 1);
194 ivi_blk_vlc_tabs[i].table = table_data + (i * 2 + 1) * 8192;
195 ivi_blk_vlc_tabs[i].table_allocated = 8192;
196 ivi_create_huff_from_desc(&ivi_blk_huff_desc[i],
197 &ivi_blk_vlc_tabs[i], 1);
199 initialized_vlcs = 1;
203 * Copy huffman codebook descriptors.
205 * @param[out] dst ptr to the destination descriptor
206 * @param[in] src ptr to the source descriptor
208 static void ivi_huff_desc_copy(IVIHuffDesc *dst, const IVIHuffDesc *src)
210 dst->num_rows = src->num_rows;
211 memcpy(dst->xbits, src->xbits, src->num_rows);
215 * Compare two huffman codebook descriptors.
217 * @param[in] desc1 ptr to the 1st descriptor to compare
218 * @param[in] desc2 ptr to the 2nd descriptor to compare
219 * @return comparison result: 0 - equal, 1 - not equal
221 static int ivi_huff_desc_cmp(const IVIHuffDesc *desc1,
222 const IVIHuffDesc *desc2)
224 return desc1->num_rows != desc2->num_rows ||
225 memcmp(desc1->xbits, desc2->xbits, desc1->num_rows);
228 int ff_ivi_dec_huff_desc(BitstreamContext *bc, int desc_coded, int which_tab,
229 IVIHuffTab *huff_tab, AVCodecContext *avctx)
232 IVIHuffDesc new_huff;
235 /* select default table */
236 huff_tab->tab = (which_tab) ? &ivi_blk_vlc_tabs[7]
237 : &ivi_mb_vlc_tabs [7];
241 huff_tab->tab_sel = bitstream_read(bc, 3);
242 if (huff_tab->tab_sel == 7) {
243 /* custom huffman table (explicitly encoded) */
244 new_huff.num_rows = bitstream_read(bc, 4);
245 if (!new_huff.num_rows) {
246 av_log(avctx, AV_LOG_ERROR, "Empty custom Huffman table!\n");
247 return AVERROR_INVALIDDATA;
250 for (i = 0; i < new_huff.num_rows; i++)
251 new_huff.xbits[i] = bitstream_read(bc, 4);
253 /* Have we got the same custom table? Rebuild if not. */
254 if (ivi_huff_desc_cmp(&new_huff, &huff_tab->cust_desc)) {
255 ivi_huff_desc_copy(&huff_tab->cust_desc, &new_huff);
257 if (huff_tab->cust_tab.table)
258 ff_free_vlc(&huff_tab->cust_tab);
259 result = ivi_create_huff_from_desc(&huff_tab->cust_desc,
260 &huff_tab->cust_tab, 0);
262 // reset faulty description
263 huff_tab->cust_desc.num_rows = 0;
264 av_log(avctx, AV_LOG_ERROR,
265 "Error while initializing custom vlc table!\n");
269 huff_tab->tab = &huff_tab->cust_tab;
271 /* select one of predefined tables */
272 huff_tab->tab = (which_tab) ? &ivi_blk_vlc_tabs[huff_tab->tab_sel]
273 : &ivi_mb_vlc_tabs [huff_tab->tab_sel];
280 * Free planes, bands and macroblocks buffers.
282 * @param[in] planes pointer to the array of the plane descriptors
284 static av_cold void ivi_free_buffers(IVIPlaneDesc *planes)
288 for (p = 0; p < 3; p++) {
289 for (b = 0; b < planes[p].num_bands; b++) {
290 av_freep(&planes[p].bands[b].bufs[0]);
291 av_freep(&planes[p].bands[b].bufs[1]);
292 av_freep(&planes[p].bands[b].bufs[2]);
293 av_freep(&planes[p].bands[b].bufs[3]);
295 if (planes[p].bands[b].blk_vlc.cust_tab.table)
296 ff_free_vlc(&planes[p].bands[b].blk_vlc.cust_tab);
297 for (t = 0; t < planes[p].bands[b].num_tiles; t++)
298 av_freep(&planes[p].bands[b].tiles[t].mbs);
299 av_freep(&planes[p].bands[b].tiles);
301 av_freep(&planes[p].bands);
302 planes[p].num_bands = 0;
306 av_cold int ff_ivi_init_planes(IVIPlaneDesc *planes, const IVIPicConfig *cfg,
310 uint32_t b_width, b_height, align_fac, width_aligned,
311 height_aligned, buf_size;
314 ivi_free_buffers(planes);
316 if (cfg->pic_width < 1 || cfg->pic_height < 1 ||
317 cfg->luma_bands < 1 || cfg->chroma_bands < 1)
318 return AVERROR_INVALIDDATA;
320 /* fill in the descriptor of the luminance plane */
321 planes[0].width = cfg->pic_width;
322 planes[0].height = cfg->pic_height;
323 planes[0].num_bands = cfg->luma_bands;
325 /* fill in the descriptors of the chrominance planes */
326 planes[1].width = planes[2].width = (cfg->pic_width + 3) >> 2;
327 planes[1].height = planes[2].height = (cfg->pic_height + 3) >> 2;
328 planes[1].num_bands = planes[2].num_bands = cfg->chroma_bands;
330 for (p = 0; p < 3; p++) {
331 planes[p].bands = av_mallocz(planes[p].num_bands * sizeof(IVIBandDesc));
332 if (!planes[p].bands)
333 return AVERROR(ENOMEM);
335 /* select band dimensions: if there is only one band then it
336 * has the full size, if there are several bands each of them
337 * has only half size */
338 b_width = planes[p].num_bands == 1 ? planes[p].width
339 : (planes[p].width + 1) >> 1;
340 b_height = planes[p].num_bands == 1 ? planes[p].height
341 : (planes[p].height + 1) >> 1;
343 /* luma band buffers will be aligned on 16x16 (max macroblock size) */
344 /* chroma band buffers will be aligned on 8x8 (max macroblock size) */
345 align_fac = p ? 8 : 16;
346 width_aligned = FFALIGN(b_width , align_fac);
347 height_aligned = FFALIGN(b_height, align_fac);
348 buf_size = width_aligned * height_aligned * sizeof(int16_t);
350 for (b = 0; b < planes[p].num_bands; b++) {
351 band = &planes[p].bands[b]; /* select appropriate plane/band */
354 band->width = b_width;
355 band->height = b_height;
356 band->pitch = width_aligned;
357 band->aheight = height_aligned;
358 band->bufs[0] = av_mallocz(buf_size);
359 band->bufs[1] = av_mallocz(buf_size);
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_malloc(tile->num_MBs * sizeof(IVIMbInfo));
403 return AVERROR(ENOMEM);
407 if (tile->num_MBs != ref_tile->num_MBs)
408 return AVERROR_INVALIDDATA;
409 tile->ref_mbs = ref_tile->mbs;
419 av_cold int ff_ivi_init_tiles(IVIPlaneDesc *planes,
420 int tile_width, int tile_height)
422 int p, b, x_tiles, y_tiles, t_width, t_height, ret;
425 for (p = 0; p < 3; p++) {
426 t_width = !p ? tile_width : (tile_width + 3) >> 2;
427 t_height = !p ? tile_height : (tile_height + 3) >> 2;
429 if (!p && planes[0].num_bands == 4) {
434 for (b = 0; b < planes[p].num_bands; b++) {
435 band = &planes[p].bands[b];
436 x_tiles = IVI_NUM_TILES(band->width, t_width);
437 y_tiles = IVI_NUM_TILES(band->height, t_height);
438 band->num_tiles = x_tiles * y_tiles;
440 av_freep(&band->tiles);
441 band->tiles = av_mallocz(band->num_tiles * sizeof(IVITile));
443 return AVERROR(ENOMEM);
445 /* use the first luma band as reference for motion vectors
447 ret = ivi_init_tiles(band, planes[0].bands[0].tiles,
448 p, b, t_height, t_width);
458 * Decode size of the tile data.
459 * The size is stored as a variable-length field having the following format:
460 * if (tile_data_size < 255) than this field is only one byte long
461 * if (tile_data_size >= 255) than this field four is byte long: 0xFF X1 X2 X3
462 * where X1-X3 is size of the tile data
464 * @param[in,out] bc the Bitstream context
465 * @return size of the tile data in bytes
467 static int ivi_dec_tile_data_size(BitstreamContext *bc)
472 if (bitstream_read_bit(bc)) {
473 len = bitstream_read(bc, 8);
475 len = bitstream_read(bc, 24);
478 /* align the bitstream reader on the byte boundary */
484 static int ivi_dc_transform(IVIBandDesc *band, int *prev_dc, int buf_offs,
487 int buf_size = band->pitch * band->aheight - buf_offs;
488 int min_size = (blk_size - 1) * band->pitch + blk_size;
490 if (!band->dc_transform)
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(BitstreamContext *bc, 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 = bitstream_read_vlc(bc, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
540 if (sym == rvmap->eob_sym)
541 break; /* End of block */
543 /* Escape - run/val explicitly coded using 3 vlc codes */
544 if (sym == rvmap->esc_sym) {
545 run = bitstream_read_vlc(bc, band->blk_vlc.tab->table, IVI_VLC_BITS, 1) + 1;
546 lo = bitstream_read_vlc(bc, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
547 hi = bitstream_read_vlc(bc, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
548 /* merge them and convert into signed val */
549 val = IVI_TOSIGNED((hi << 6) | lo);
552 av_log(avctx, AV_LOG_ERROR, "Invalid sym encountered: %"PRIu32".\n", sym);
553 return AVERROR_INVALIDDATA;
555 run = rvmap->runtab[sym];
556 val = rvmap->valtab[sym];
559 /* de-zigzag and dequantize */
561 if (scan_pos >= num_coeffs || scan_pos < 0)
563 pos = band->scan[scan_pos];
566 ff_dlog(avctx, "Val = 0 encountered!\n");
568 q = (base_tab[pos] * quant) >> 9;
570 val = val * q + FFSIGN(val) * (((q ^ 1) - 1) >> 1);
572 /* track columns containing non-zero coeffs */
573 col_flags[pos & col_mask] |= !!val;
576 if (scan_pos < 0 || scan_pos >= num_coeffs && sym != rvmap->eob_sym)
577 return AVERROR_INVALIDDATA; /* corrupt block data */
579 /* undoing DC coeff prediction for intra-blocks */
580 if (is_intra && band->is_2d_trans) {
581 *prev_dc += trvec[0];
583 col_flags[0] |= !!*prev_dc;
586 /* 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] bc the Bitstream 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(BitstreamContext *bc, 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(quant, 0, 31);
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(bc, 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 /* block not coded */
722 /* for intra blocks apply the dc slant transform */
723 /* for inter - perform the motion compensation without delta */
725 ret = ivi_dc_transform(band, &prev_dc, buf_offs, blk_size);
729 ret = ivi_mc(band, mc_no_delta_func, mc_avg_no_delta_func,
730 buf_offs, mv_x, mv_y, mv_x2, mv_y2,
747 * Handle empty tiles by performing data copying and motion
748 * compensation respectively.
750 * @param[in] avctx ptr to the AVCodecContext
751 * @param[in] band pointer to the band descriptor
752 * @param[in] tile pointer to the tile descriptor
753 * @param[in] mv_scale scaling factor for motion vectors
755 static int ivi_process_empty_tile(AVCodecContext *avctx, IVIBandDesc *band,
756 IVITile *tile, int32_t mv_scale)
758 int x, y, need_mc, mbn, blk, num_blocks, mv_x, mv_y, mc_type;
759 int offs, mb_offset, row_offset, ret;
760 IVIMbInfo *mb, *ref_mb;
763 ivi_mc_func mc_no_delta_func;
765 if (tile->num_MBs != IVI_MBs_PER_TILE(tile->width, tile->height, band->mb_size)) {
766 av_log(avctx, AV_LOG_ERROR, "Allocated tile size %d mismatches "
767 "parameters %d in ivi_process_empty_tile()\n",
768 tile->num_MBs, IVI_MBs_PER_TILE(tile->width, tile->height, band->mb_size));
769 return AVERROR_INVALIDDATA;
772 offs = tile->ypos * band->pitch + tile->xpos;
774 ref_mb = tile->ref_mbs;
775 row_offset = band->mb_size * band->pitch;
776 need_mc = 0; /* reset the mc tracking flag */
778 for (y = tile->ypos; y < (tile->ypos + tile->height); y += band->mb_size) {
781 for (x = tile->xpos; x < (tile->xpos + tile->width); x += band->mb_size) {
784 mb->buf_offs = mb_offset;
786 mb->type = 1; /* set the macroblocks type = INTER */
787 mb->cbp = 0; /* all blocks are empty */
789 if (!band->qdelta_present && !band->plane && !band->band_num) {
790 mb->q_delta = band->glob_quant;
795 if (band->inherit_qdelta && ref_mb)
796 mb->q_delta = ref_mb->q_delta;
798 if (band->inherit_mv && ref_mb) {
799 /* motion vector inheritance */
801 mb->mv_x = ivi_scale_mv(ref_mb->mv_x, mv_scale);
802 mb->mv_y = ivi_scale_mv(ref_mb->mv_y, mv_scale);
804 mb->mv_x = ref_mb->mv_x;
805 mb->mv_y = ref_mb->mv_y;
807 need_mc |= mb->mv_x || mb->mv_y; /* tracking non-zero motion vectors */
813 mb_offset += band->mb_size;
818 if (band->inherit_mv && need_mc) { /* apply motion compensation if there is at least one non-zero motion vector */
819 num_blocks = (band->mb_size != band->blk_size) ? 4 : 1; /* number of blocks per mb */
820 mc_no_delta_func = (band->blk_size == 8) ? ff_ivi_mc_8x8_no_delta
821 : ff_ivi_mc_4x4_no_delta;
823 for (mbn = 0, mb = tile->mbs; mbn < tile->num_MBs; mb++, mbn++) {
826 if (!band->is_halfpel) {
827 mc_type = 0; /* we have only fullpel vectors */
829 mc_type = ((mv_y & 1) << 1) | (mv_x & 1);
831 mv_y >>= 1; /* convert halfpel vectors into fullpel ones */
834 for (blk = 0; blk < num_blocks; blk++) {
835 /* adjust block position in the buffer according with its number */
836 offs = mb->buf_offs + band->blk_size * ((blk & 1) + !!(blk & 2) * band->pitch);
837 ret = ivi_mc(band, mc_no_delta_func, 0, offs,
838 mv_x, mv_y, 0, 0, mc_type, -1);
844 /* copy data from the reference tile into the current one */
845 src = band->ref_buf + tile->ypos * band->pitch + tile->xpos;
846 dst = band->buf + tile->ypos * band->pitch + tile->xpos;
847 for (y = 0; y < tile->height; y++) {
848 memcpy(dst, src, tile->width*sizeof(band->buf[0]));
859 static uint16_t ivi_calc_band_checksum(IVIBandDesc *band)
862 int16_t *src, checksum;
867 for (y = 0; y < band->height; src += band->pitch, y++)
868 for (x = 0; x < band->width; x++)
876 * Convert and output the current plane.
877 * This conversion is done by adding back the bias value of 128
878 * (subtracted in the encoder) and clipping the result.
880 * @param[in] plane pointer to the descriptor of the plane being processed
881 * @param[out] dst pointer to the buffer receiving converted pixels
882 * @param[in] dst_pitch pitch for moving to the next y line
884 static void ivi_output_plane(IVIPlaneDesc *plane, uint8_t *dst, ptrdiff_t dst_pitch)
887 const int16_t *src = plane->bands[0].buf;
888 ptrdiff_t pitch = plane->bands[0].pitch;
893 for (y = 0; y < plane->height; y++) {
894 for (x = 0; x < plane->width; x++)
895 dst[x] = av_clip_uint8(src[x] + 128);
902 * Decode an Indeo 4 or 5 band.
904 * @param[in,out] ctx ptr to the decoder context
905 * @param[in,out] band ptr to the band descriptor
906 * @param[in] avctx ptr to the AVCodecContext
907 * @return result code: 0 = OK, -1 = error
909 static int decode_band(IVI45DecContext *ctx,
910 IVIBandDesc *band, AVCodecContext *avctx)
912 int result, i, t, idx1, idx2, pos;
915 band->buf = band->bufs[ctx->dst_buf];
917 av_log(avctx, AV_LOG_ERROR, "Band buffer points to no data!\n");
918 return AVERROR_INVALIDDATA;
920 if (ctx->is_indeo4 && ctx->frame_type == IVI4_FRAMETYPE_BIDIR) {
921 band->ref_buf = band->bufs[ctx->b_ref_buf];
922 band->b_ref_buf = band->bufs[ctx->ref_buf];
924 band->ref_buf = band->bufs[ctx->ref_buf];
927 band->data_ptr = ctx->frame_data + (bitstream_tell(&ctx->bc) >> 3);
929 result = ctx->decode_band_hdr(ctx, band, avctx);
931 av_log(avctx, AV_LOG_ERROR, "Error while decoding band header: %d\n",
936 if (band->is_empty) {
937 av_log(avctx, AV_LOG_ERROR, "Empty band encountered!\n");
938 return AVERROR_INVALIDDATA;
941 band->rv_map = &ctx->rvmap_tabs[band->rvmap_sel];
943 /* apply corrections to the selected rvmap table if present */
944 for (i = 0; i < band->num_corr; i++) {
945 idx1 = band->corr[i * 2];
946 idx2 = band->corr[i * 2 + 1];
947 FFSWAP(uint8_t, band->rv_map->runtab[idx1], band->rv_map->runtab[idx2]);
948 FFSWAP(int16_t, band->rv_map->valtab[idx1], band->rv_map->valtab[idx2]);
951 pos = bitstream_tell(&ctx->bc);
953 for (t = 0; t < band->num_tiles; t++) {
954 tile = &band->tiles[t];
956 if (tile->mb_size != band->mb_size) {
957 av_log(avctx, AV_LOG_ERROR, "MB sizes mismatch: %d vs. %d\n",
958 band->mb_size, tile->mb_size);
959 return AVERROR_INVALIDDATA;
961 tile->is_empty = bitstream_read_bit(&ctx->bc);
962 if (tile->is_empty) {
963 result = ivi_process_empty_tile(avctx, band, tile,
964 (ctx->planes[0].bands[0].mb_size >> 3) - (band->mb_size >> 3));
967 ff_dlog(avctx, "Empty tile encountered!\n");
969 tile->data_size = ivi_dec_tile_data_size(&ctx->bc);
970 if (!tile->data_size) {
971 av_log(avctx, AV_LOG_ERROR, "Tile data size is zero!\n");
972 return AVERROR_INVALIDDATA;
975 result = ctx->decode_mb_info(ctx, band, tile, avctx);
979 result = ivi_decode_blocks(&ctx->bc, band, tile, avctx);
981 av_log(avctx, AV_LOG_ERROR,
982 "Corrupted tile data encountered!\n");
986 if (((bitstream_tell(&ctx->bc) - pos) >> 3) != tile->data_size) {
987 av_log(avctx, AV_LOG_ERROR,
988 "Tile data_size mismatch!\n");
989 result = AVERROR_INVALIDDATA;
993 pos += tile->data_size << 3; // skip to next tile
997 /* restore the selected rvmap table by applying its corrections in
999 for (i = band->num_corr-1; i >= 0; i--) {
1000 idx1 = band->corr[i*2];
1001 idx2 = band->corr[i*2+1];
1002 FFSWAP(uint8_t, band->rv_map->runtab[idx1], band->rv_map->runtab[idx2]);
1003 FFSWAP(int16_t, band->rv_map->valtab[idx1], band->rv_map->valtab[idx2]);
1007 if (band->checksum_present) {
1008 uint16_t chksum = ivi_calc_band_checksum(band);
1009 if (chksum != band->checksum) {
1010 av_log(avctx, AV_LOG_ERROR,
1011 "Band checksum mismatch! Plane %d, band %d, "
1012 "received: %"PRIx32", calculated: %"PRIx16"\n",
1013 band->plane, band->band_num, band->checksum, chksum);
1018 bitstream_align(&ctx->bc);
1023 int ff_ivi_decode_frame(AVCodecContext *avctx, void *data, int *got_frame,
1026 IVI45DecContext *ctx = avctx->priv_data;
1027 const uint8_t *buf = avpkt->data;
1028 AVFrame *frame = data;
1029 int buf_size = avpkt->size;
1032 bitstream_init8(&ctx->bc, buf, buf_size);
1033 ctx->frame_data = buf;
1034 ctx->frame_size = buf_size;
1036 result = ctx->decode_pic_hdr(ctx, avctx);
1038 av_log(avctx, AV_LOG_ERROR,
1039 "Error while decoding picture header: %d\n", result);
1042 if (ctx->gop_invalid)
1043 return AVERROR_INVALIDDATA;
1045 if (ctx->is_indeo4 && ctx->frame_type == IVI4_FRAMETYPE_NULL_LAST) {
1046 if (ctx->got_p_frame) {
1047 av_frame_move_ref(data, ctx->p_frame);
1049 ctx->got_p_frame = 0;
1056 if (ctx->gop_flags & IVI5_IS_PROTECTED) {
1057 avpriv_report_missing_feature(avctx, "Password-protected clip");
1058 return AVERROR_PATCHWELCOME;
1061 if (!ctx->planes[0].bands) {
1062 av_log(avctx, AV_LOG_ERROR, "Color planes not initialized yet\n");
1063 return AVERROR_INVALIDDATA;
1066 ctx->switch_buffers(ctx);
1070 if (ctx->is_nonnull_frame(ctx)) {
1071 for (p = 0; p < 3; p++) {
1072 for (b = 0; b < ctx->planes[p].num_bands; b++) {
1073 result = decode_band(ctx, &ctx->planes[p].bands[b], avctx);
1075 av_log(avctx, AV_LOG_ERROR,
1076 "Error while decoding band: %d, plane: %d\n", b, p);
1082 if (ctx->is_scalable)
1083 return AVERROR_INVALIDDATA;
1085 for (p = 0; p < 3; p++) {
1086 if (!ctx->planes[p].bands[0].buf)
1087 return AVERROR_INVALIDDATA;
1091 //STOP_TIMER("decode_planes"); }
1093 result = ff_set_dimensions(avctx, ctx->planes[0].width, ctx->planes[0].height);
1097 if ((result = ff_get_buffer(avctx, frame, 0)) < 0) {
1098 av_log(avctx, AV_LOG_ERROR, "get_buffer() failed\n");
1102 if (ctx->is_scalable) {
1104 ff_ivi_recompose_haar(&ctx->planes[0], frame->data[0], frame->linesize[0]);
1106 ff_ivi_recompose53 (&ctx->planes[0], frame->data[0], frame->linesize[0]);
1108 ivi_output_plane(&ctx->planes[0], frame->data[0], frame->linesize[0]);
1111 ivi_output_plane(&ctx->planes[2], frame->data[1], frame->linesize[1]);
1112 ivi_output_plane(&ctx->planes[1], frame->data[2], frame->linesize[2]);
1116 /* If the bidirectional mode is enabled, next I and the following P
1117 * frame will be sent together. Unfortunately the approach below seems
1118 * to be the only way to handle the B-frames mode.
1119 * That's exactly the same Intel decoders do.
1121 if (ctx->is_indeo4 && ctx->frame_type == IVI4_FRAMETYPE_INTRA) {
1124 while (bitstream_read(&ctx->bc, 8)); // skip version string
1125 left = bitstream_tell(&ctx->bc) & 0x18;
1126 bitstream_skip(&ctx->bc, 64 - left);
1127 if (bitstream_bits_left(&ctx->bc) > 18 &&
1128 bitstream_peek(&ctx->bc, 21) == 0xBFFF8) { // syncheader + inter type
1130 pkt.data = avpkt->data + (bitstream_tell(&ctx->bc) >> 3);
1131 pkt.size = bitstream_bits_left(&ctx->bc) >> 3;
1132 ff_ivi_decode_frame(avctx, ctx->p_frame, &ctx->got_p_frame, &pkt);
1136 if (ctx->show_indeo4_info) {
1137 if (ctx->is_scalable)
1138 av_log(avctx, AV_LOG_DEBUG, "This video uses scalability mode\n");
1139 if (ctx->uses_tiling)
1140 av_log(avctx, AV_LOG_DEBUG, "This video uses local decoding\n");
1141 if (ctx->has_b_frames)
1142 av_log(avctx, AV_LOG_DEBUG, "This video contains B-frames\n");
1143 if (ctx->has_transp)
1144 av_log(avctx, AV_LOG_DEBUG, "Transparency mode is enabled\n");
1146 av_log(avctx, AV_LOG_DEBUG, "This video uses Haar transform\n");
1147 if (ctx->uses_fullpel)
1148 av_log(avctx, AV_LOG_DEBUG, "This video uses fullpel motion vectors\n");
1149 ctx->show_indeo4_info = 0;
1156 * Close Indeo5 decoder and clean up its context.
1158 av_cold int ff_ivi_decode_close(AVCodecContext *avctx)
1160 IVI45DecContext *ctx = avctx->priv_data;
1162 ivi_free_buffers(&ctx->planes[0]);
1164 if (ctx->mb_vlc.cust_tab.table)
1165 ff_free_vlc(&ctx->mb_vlc.cust_tab);
1167 av_frame_free(&ctx->p_frame);
1174 * Scan patterns shared between indeo4 and indeo5
1176 const uint8_t ff_ivi_vertical_scan_8x8[64] = {
1177 0, 8, 16, 24, 32, 40, 48, 56,
1178 1, 9, 17, 25, 33, 41, 49, 57,
1179 2, 10, 18, 26, 34, 42, 50, 58,
1180 3, 11, 19, 27, 35, 43, 51, 59,
1181 4, 12, 20, 28, 36, 44, 52, 60,
1182 5, 13, 21, 29, 37, 45, 53, 61,
1183 6, 14, 22, 30, 38, 46, 54, 62,
1184 7, 15, 23, 31, 39, 47, 55, 63
1187 const uint8_t ff_ivi_horizontal_scan_8x8[64] = {
1188 0, 1, 2, 3, 4, 5, 6, 7,
1189 8, 9, 10, 11, 12, 13, 14, 15,
1190 16, 17, 18, 19, 20, 21, 22, 23,
1191 24, 25, 26, 27, 28, 29, 30, 31,
1192 32, 33, 34, 35, 36, 37, 38, 39,
1193 40, 41, 42, 43, 44, 45, 46, 47,
1194 48, 49, 50, 51, 52, 53, 54, 55,
1195 56, 57, 58, 59, 60, 61, 62, 63
1198 const uint8_t ff_ivi_direct_scan_4x4[16] = {
1199 0, 1, 4, 8, 5, 2, 3, 6, 9, 12, 13, 10, 7, 11, 14, 15
1204 * Run-value (RLE) tables.
1206 const RVMapDesc ff_ivi_rvmap_tabs[9] = {
1211 {1, 1, 0, 1, 1, 0, 1, 1, 2, 2, 1, 1, 1, 1, 3, 3,
1212 1, 1, 2, 2, 1, 1, 4, 4, 1, 1, 1, 1, 2, 2, 5, 5,
1213 1, 1, 3, 3, 1, 1, 6, 6, 1, 2, 1, 2, 7, 7, 1, 1,
1214 8, 8, 1, 1, 4, 2, 1, 4, 2, 1, 3, 3, 1, 1, 1, 9,
1215 9, 1, 2, 1, 2, 1, 5, 5, 1, 1, 10, 10, 1, 1, 3, 3,
1216 2, 2, 1, 1, 11, 11, 6, 4, 4, 1, 6, 1, 2, 1, 2, 12,
1217 8, 1, 12, 7, 8, 7, 1, 16, 1, 16, 1, 3, 3, 13, 1, 13,
1218 2, 2, 1, 15, 1, 5, 14, 15, 1, 5, 14, 1, 17, 8, 17, 8,
1219 1, 4, 4, 2, 2, 1, 25, 25, 24, 24, 1, 3, 1, 3, 1, 8,
1220 6, 7, 6, 1, 18, 8, 18, 1, 7, 23, 2, 2, 23, 1, 1, 21,
1221 22, 9, 9, 22, 19, 1, 21, 5, 19, 5, 1, 33, 20, 33, 20, 8,
1222 4, 4, 1, 32, 2, 2, 8, 3, 32, 26, 3, 1, 7, 7, 26, 6,
1223 1, 6, 1, 1, 16, 1, 10, 1, 10, 2, 16, 29, 28, 2, 29, 28,
1224 1, 27, 5, 8, 5, 27, 1, 8, 3, 7, 3, 31, 41, 31, 1, 41,
1225 6, 1, 6, 7, 4, 4, 1, 1, 2, 1, 2, 11, 34, 30, 11, 1,
1226 30, 15, 15, 34, 36, 40, 36, 40, 35, 35, 37, 37, 39, 39, 38, 38},
1229 { 1, -1, 0, 2, -2, 0, 3, -3, 1, -1, 4, -4, 5, -5, 1, -1,
1230 6, -6, 2, -2, 7, -7, 1, -1, 8, -8, 9, -9, 3, -3, 1, -1,
1231 10, -10, 2, -2, 11, -11, 1, -1, 12, 4, -12, -4, 1, -1, 13, -13,
1232 1, -1, 14, -14, 2, 5, 15, -2, -5, -15, -3, 3, 16, -16, 17, 1,
1233 -1, -17, 6, 18, -6, -18, 2, -2, 19, -19, 1, -1, 20, -20, 4, -4,
1234 7, -7, 21, -21, 1, -1, 2, 3, -3, 22, -2, -22, 8, 23, -8, 1,
1235 2, -23, -1, 2, -2, -2, 24, 1, -24, -1, 25, 5, -5, 1, -25, -1,
1236 9, -9, 26, 1, -26, 3, 1, -1, 27, -3, -1, -27, 1, 3, -1, -3,
1237 28, -4, 4, 10, -10, -28, 1, -1, 1, -1, 29, 6, -29, -6, 30, -4,
1238 3, 3, -3, -30, 1, 4, -1, 31, -3, 1, 11, -11, -1, -31, 32, -1,
1239 -1, 2, -2, 1, 1, -32, 1, 4, -1, -4, 33, -1, 1, 1, -1, 5,
1240 5, -5, -33, -1, -12, 12, -5, -7, 1, 1, 7, 34, 4, -4, -1, 4,
1241 -34, -4, 35, 36, -2, -35, -2, -36, 2, 13, 2, -1, 1, -13, 1, -1,
1242 37, 1, -5, 6, 5, -1, 38, -6, -8, 5, 8, -1, 1, 1, -37, -1,
1243 5, 39, -5, -5, 6, -6, -38, -39, -14, 40, 14, 2, 1, 1, -2, -40,
1244 -1, -2, 2, -1, -1, -1, 1, 1, 1, -1, 1, -1, 1, -1, 1, -1}
1250 {0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 8, 6, 8, 7,
1251 7, 9, 9, 10, 10, 11, 11, 1, 12, 1, 12, 13, 13, 16, 14, 16,
1252 14, 15, 15, 17, 17, 18, 0, 18, 19, 20, 21, 19, 22, 21, 20, 22,
1253 25, 24, 2, 25, 24, 23, 23, 2, 26, 28, 26, 28, 29, 27, 29, 27,
1254 33, 33, 1, 32, 1, 3, 32, 30, 36, 3, 36, 30, 31, 31, 35, 34,
1255 37, 41, 34, 35, 37, 4, 41, 4, 49, 8, 8, 49, 40, 38, 5, 38,
1256 40, 39, 5, 39, 42, 43, 42, 7, 57, 6, 43, 44, 6, 50, 7, 44,
1257 57, 48, 50, 48, 45, 45, 46, 47, 51, 46, 47, 58, 1, 51, 58, 1,
1258 52, 59, 53, 9, 52, 55, 55, 59, 53, 56, 54, 56, 54, 9, 64, 64,
1259 60, 63, 60, 63, 61, 62, 61, 62, 2, 10, 2, 10, 11, 1, 11, 13,
1260 12, 1, 12, 13, 16, 16, 8, 8, 14, 3, 3, 15, 14, 15, 4, 4,
1261 1, 17, 17, 5, 1, 7, 7, 5, 6, 1, 2, 2, 6, 22, 1, 25,
1262 21, 22, 8, 24, 1, 21, 25, 24, 8, 18, 18, 23, 9, 20, 23, 33,
1263 29, 33, 20, 1, 19, 1, 29, 36, 9, 36, 19, 41, 28, 57, 32, 3,
1264 28, 3, 1, 27, 49, 49, 1, 32, 26, 26, 2, 4, 4, 7, 57, 41,
1265 2, 7, 10, 5, 37, 16, 10, 27, 8, 8, 13, 16, 37, 13, 1, 5},
1268 {0, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, 1, -1, -1, 1,
1269 -1, 1, -1, 1, -1, 1, -1, 2, 1, -2, -1, 1, -1, 1, 1, -1,
1270 -1, 1, -1, 1, -1, 1, 0, -1, 1, 1, 1, -1, 1, -1, -1, -1,
1271 1, 1, 2, -1, -1, 1, -1, -2, 1, 1, -1, -1, 1, 1, -1, -1,
1272 1, -1, 3, 1, -3, 2, -1, 1, 1, -2, -1, -1, -1, 1, 1, 1,
1273 1, 1, -1, -1, -1, 2, -1, -2, 1, 2, -2, -1, 1, 1, 2, -1,
1274 -1, 1, -2, -1, 1, 1, -1, 2, 1, 2, -1, 1, -2, -1, -2, -1,
1275 -1, 1, 1, -1, 1, -1, 1, 1, 1, -1, -1, 1, 4, -1, -1, -4,
1276 1, 1, 1, 2, -1, -1, 1, -1, -1, 1, -1, -1, 1, -2, 1, -1,
1277 1, 1, -1, -1, 1, 1, -1, -1, 3, 2, -3, -2, 2, 5, -2, 2,
1278 2, -5, -2, -2, -2, 2, -3, 3, 2, 3, -3, 2, -2, -2, 3, -3,
1279 6, 2, -2, 3, -6, 3, -3, -3, 3, 7, -4, 4, -3, 2, -7, 2,
1280 2, -2, -4, 2, 8, -2, -2, -2, 4, 2, -2, 2, 3, 2, -2, -2,
1281 2, 2, -2, -8, -2, 9, -2, 2, -3, -2, 2, -2, 2, 2, 2, 4,
1282 -2, -4, 10, 2, 2, -2, -9, -2, 2, -2, 5, 4, -4, 4, -2, 2,
1283 -5, -4, -3, 4, 2, -3, 3, -2, -5, 5, 3, 3, -2, -3, -10, -4}
1289 {1, 1, 0, 2, 2, 1, 1, 3, 3, 4, 4, 0, 1, 1, 5, 5,
1290 2, 2, 6, 6, 7, 7, 1, 8, 1, 8, 3, 3, 9, 9, 1, 2,
1291 2, 1, 4, 10, 4, 10, 11, 11, 1, 5, 12, 12, 1, 5, 13, 13,
1292 3, 3, 6, 6, 2, 2, 14, 14, 16, 16, 15, 7, 15, 8, 8, 7,
1293 1, 1, 17, 17, 4, 4, 1, 1, 18, 18, 2, 2, 5, 5, 25, 3,
1294 9, 3, 25, 9, 19, 24, 19, 24, 1, 21, 20, 1, 21, 22, 20, 22,
1295 23, 23, 8, 6, 33, 6, 8, 33, 7, 7, 26, 26, 1, 32, 1, 32,
1296 28, 4, 28, 10, 29, 27, 27, 10, 41, 4, 29, 2, 2, 41, 36, 31,
1297 49, 31, 34, 30, 34, 36, 30, 35, 1, 49, 11, 5, 35, 11, 1, 3,
1298 3, 5, 37, 37, 8, 40, 8, 40, 12, 12, 42, 42, 1, 38, 16, 57,
1299 1, 6, 16, 39, 38, 6, 7, 7, 13, 13, 39, 43, 2, 43, 57, 2,
1300 50, 9, 44, 9, 50, 4, 15, 48, 44, 4, 1, 15, 48, 14, 14, 1,
1301 45, 45, 8, 3, 5, 8, 51, 47, 3, 46, 46, 47, 5, 51, 1, 17,
1302 17, 58, 1, 58, 2, 52, 52, 2, 53, 7, 59, 6, 6, 56, 53, 55,
1303 7, 55, 1, 54, 59, 56, 54, 10, 1, 10, 4, 60, 1, 60, 8, 4,
1304 8, 64, 64, 61, 1, 63, 3, 63, 62, 61, 5, 11, 5, 3, 11, 62},
1307 { 1, -1, 0, 1, -1, 2, -2, 1, -1, 1, -1, 0, 3, -3, 1, -1,
1308 2, -2, 1, -1, 1, -1, 4, 1, -4, -1, 2, -2, 1, -1, 5, 3,
1309 -3, -5, 2, 1, -2, -1, 1, -1, 6, 2, 1, -1, -6, -2, 1, -1,
1310 3, -3, 2, -2, 4, -4, 1, -1, 1, -1, 1, 2, -1, 2, -2, -2,
1311 7, -7, 1, -1, 3, -3, 8, -8, 1, -1, 5, -5, 3, -3, 1, 4,
1312 2, -4, -1, -2, 1, 1, -1, -1, 9, 1, 1, -9, -1, 1, -1, -1,
1313 1, -1, 3, -3, 1, 3, -3, -1, 3, -3, 1, -1, 10, 1, -10, -1,
1314 1, 4, -1, 2, 1, -1, 1, -2, 1, -4, -1, 6, -6, -1, 1, 1,
1315 1, -1, 1, 1, -1, -1, -1, 1, 11, -1, -2, 4, -1, 2, -11, 5,
1316 -5, -4, -1, 1, 4, 1, -4, -1, -2, 2, 1, -1, 12, 1, -2, 1,
1317 -12, 4, 2, 1, -1, -4, 4, -4, 2, -2, -1, 1, 7, -1, -1, -7,
1318 -1, -3, 1, 3, 1, 5, 2, 1, -1, -5, 13, -2, -1, 2, -2, -13,
1319 1, -1, 5, 6, 5, -5, 1, 1, -6, 1, -1, -1, -5, -1, 14, 2,
1320 -2, 1, -14, -1, 8, 1, -1, -8, 1, 5, 1, 5, -5, 1, -1, 1,
1321 -5, -1, 15, 1, -1, -1, -1, 3, -15, -3, 6, 1, 16, -1, 6, -6,
1322 -6, 1, -1, 1, -16, 1, 7, -1, 1, -1, -6, -3, 6, -7, 3, -1}
1328 {0, 1, 1, 2, 2, 3, 3, 4, 4, 1, 1, 5, 5, 6, 6, 7,
1329 7, 8, 8, 9, 9, 2, 2, 10, 10, 1, 1, 11, 11, 12, 12, 3,
1330 3, 13, 13, 0, 14, 14, 16, 15, 16, 15, 4, 4, 17, 1, 17, 1,
1331 5, 5, 18, 18, 2, 2, 6, 6, 8, 19, 7, 8, 7, 19, 20, 20,
1332 21, 21, 22, 24, 22, 24, 23, 23, 1, 1, 25, 25, 3, 3, 26, 26,
1333 9, 9, 27, 27, 28, 28, 33, 29, 4, 33, 29, 1, 4, 1, 32, 32,
1334 2, 2, 31, 10, 30, 10, 30, 31, 34, 34, 5, 5, 36, 36, 35, 41,
1335 35, 11, 41, 11, 37, 1, 8, 8, 37, 6, 1, 6, 40, 7, 7, 40,
1336 12, 38, 12, 39, 39, 38, 49, 13, 49, 13, 3, 42, 3, 42, 16, 16,
1337 43, 43, 14, 14, 1, 1, 44, 15, 44, 15, 2, 2, 57, 48, 50, 48,
1338 57, 50, 4, 45, 45, 4, 46, 47, 47, 46, 1, 51, 1, 17, 17, 51,
1339 8, 9, 9, 5, 58, 8, 58, 5, 52, 52, 55, 56, 53, 56, 55, 59,
1340 59, 53, 54, 1, 6, 54, 7, 7, 6, 1, 2, 3, 2, 3, 64, 60,
1341 60, 10, 10, 64, 61, 62, 61, 63, 1, 63, 62, 1, 18, 24, 18, 4,
1342 25, 4, 8, 21, 21, 1, 24, 22, 25, 22, 8, 11, 19, 11, 23, 1,
1343 20, 23, 19, 20, 5, 12, 5, 1, 16, 2, 12, 13, 2, 13, 1, 16},
1346 { 0, 1, -1, 1, -1, 1, -1, 1, -1, 2, -2, 1, -1, 1, -1, 1,
1347 -1, 1, -1, 1, -1, 2, -2, 1, -1, 3, -3, 1, -1, 1, -1, 2,
1348 -2, 1, -1, 0, 1, -1, 1, 1, -1, -1, 2, -2, 1, 4, -1, -4,
1349 2, -2, 1, -1, -3, 3, 2, -2, 2, 1, 2, -2, -2, -1, 1, -1,
1350 1, -1, 1, 1, -1, -1, 1, -1, 5, -5, 1, -1, 3, -3, 1, -1,
1351 2, -2, 1, -1, 1, -1, 1, 1, 3, -1, -1, 6, -3, -6, -1, 1,
1352 4, -4, 1, 2, 1, -2, -1, -1, 1, -1, 3, -3, 1, -1, 1, 1,
1353 -1, 2, -1, -2, 1, 7, -3, 3, -1, 3, -7, -3, 1, -3, 3, -1,
1354 2, 1, -2, 1, -1, -1, 1, 2, -1, -2, -4, -1, 4, 1, 2, -2,
1355 1, -1, -2, 2, 8, -8, -1, 2, 1, -2, -5, 5, 1, -1, -1, 1,
1356 -1, 1, 4, -1, 1, -4, -1, -1, 1, 1, 9, 1, -9, 2, -2, -1,
1357 -4, 3, -3, -4, -1, 4, 1, 4, 1, -1, 1, -1, 1, 1, -1, 1,
1358 -1, -1, -1, 10, 4, 1, 4, -4, -4, -10, 6, 5, -6, -5, 1, -1,
1359 1, 3, -3, -1, 1, -1, -1, -1, 11, 1, 1, -11, -2, -2, 2, 5,
1360 -2, -5, -5, 2, -2, 12, 2, -2, 2, 2, 5, -3, -2, 3, -2, -12,
1361 -2, 2, 2, 2, -5, 3, 5, 13, -3, 7, -3, -3, -7, 3, -13, 3}
1367 {0, 1, 1, 1, 2, 2, 1, 3, 3, 1, 1, 1, 4, 4, 1, 5,
1368 2, 1, 5, 2, 1, 1, 6, 6, 1, 1, 1, 1, 1, 7, 3, 1,
1369 2, 3, 0, 1, 2, 7, 1, 1, 1, 8, 1, 1, 8, 1, 1, 1,
1370 9, 1, 9, 1, 2, 1, 1, 2, 1, 1, 10, 4, 1, 10, 1, 4,
1371 1, 1, 1, 1, 1, 3, 1, 1, 1, 3, 2, 1, 5, 1, 1, 1,
1372 2, 5, 1, 11, 1, 11, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1373 2, 1, 6, 1, 6, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 12,
1374 3, 1, 12, 1, 1, 1, 2, 1, 1, 3, 1, 1, 1, 1, 1, 1,
1375 4, 1, 1, 1, 2, 1, 1, 4, 1, 1, 1, 1, 1, 1, 2, 1,
1376 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 2, 1, 1, 5,
1377 1, 1, 1, 1, 1, 7, 1, 7, 1, 1, 2, 3, 1, 1, 1, 1,
1378 5, 1, 1, 1, 1, 1, 1, 2, 13, 1, 1, 1, 1, 1, 1, 1,
1379 1, 1, 1, 1, 1, 1, 1, 1, 13, 2, 1, 1, 4, 1, 1, 1,
1380 3, 1, 6, 1, 1, 1, 14, 1, 1, 1, 1, 1, 14, 6, 1, 1,
1381 1, 1, 15, 2, 4, 1, 2, 3, 15, 1, 1, 1, 8, 1, 1, 8,
1382 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1},
1385 { 0, 1, -1, 2, 1, -1, -2, 1, -1, 3, -3, 4, 1, -1, -4, 1,
1386 2, 5, -1, -2, -5, 6, 1, -1, -6, 7, -7, 8, -8, 1, 2, 9,
1387 3, -2, 0, -9, -3, -1, 10, -10, 11, 1, -11, 12, -1, -12, 13, -13,
1388 1, 14, -1, -14, 4, 15, -15, -4, 16, -16, 1, 2, 17, -1, -17, -2,
1389 18, -18, 19, -19, 20, 3, -20, 21, -21, -3, 5, 22, 2, -22, -23, 23,
1390 -5, -2, 24, 1, -24, -1, 25, -25, 26, -26, -27, 27, 28, 29, -28, -29,
1391 6, 30, 2, -31, -2, -30, 31, -6, -32, 32, 33, -33, 34, -35, -34, 1,
1392 4, -36, -1, 35, 37, 36, 7, -37, 38, -4, -38, 39, 41, 40, -40, -39,
1393 3, 42, -43, -41, -7, -42, 43, -3, 44, -44, 45, -45, 46, 47, 8, -47,
1394 -48, -46, 50, -50, 48, 49, 51, -49, 52, -52, 5, -51, -8, -53, 53, 3,
1395 -56, 56, 55, 54, -54, 2, 60, -2, -55, 58, 9, -5, 59, 57, -57, -63,
1396 -3, -58, -60, -61, 61, -59, -62, -9, 1, 64, 62, 69, -64, 63, 65, -67,
1397 -68, 66, -65, 68, -66, -69, 67, -70, -1, 10, 71, -71, 4, 73, 72, 70,
1398 6, -76, -3, 74, -78, -74, 1, 78, 80, -72, -75, 76, -1, 3, -73, 79,
1399 75, 77, 1, 11, -4, -79, -10, -6, -1, -77, -83, -80, 2, 81, -84, -2,
1400 83, -81, 82, -82, 84, -87, -86, 85, -11, -85, 86, -89, 87, -88, 88, 89}
1406 {1, 1, 0, 2, 1, 2, 1, 3, 3, 1, 1, 4, 4, 2, 2, 1,
1407 1, 5, 5, 6, 1, 6, 1, 7, 7, 3, 3, 2, 8, 2, 8, 1,
1408 1, 0, 9, 9, 1, 1, 10, 4, 10, 4, 11, 11, 2, 1, 2, 1,
1409 12, 12, 3, 3, 1, 1, 13, 5, 5, 13, 14, 1, 1, 14, 2, 2,
1410 6, 6, 15, 1, 1, 15, 16, 4, 7, 16, 4, 7, 1, 1, 3, 3,
1411 8, 8, 2, 2, 1, 1, 17, 17, 1, 1, 18, 18, 5, 5, 2, 2,
1412 1, 1, 9, 19, 9, 19, 20, 3, 3, 20, 1, 10, 21, 1, 10, 4,
1413 4, 21, 22, 6, 6, 22, 1, 1, 23, 24, 2, 2, 23, 24, 11, 1,
1414 1, 11, 7, 25, 7, 1, 1, 25, 8, 8, 3, 26, 3, 1, 12, 2,
1415 2, 26, 1, 12, 5, 5, 27, 4, 1, 4, 1, 27, 28, 1, 28, 13,
1416 1, 13, 2, 29, 2, 1, 32, 6, 1, 30, 14, 29, 14, 6, 3, 31,
1417 3, 1, 30, 1, 32, 31, 33, 9, 33, 1, 1, 7, 9, 7, 2, 2,
1418 1, 1, 4, 36, 34, 4, 5, 10, 10, 5, 34, 1, 1, 35, 8, 8,
1419 36, 3, 35, 1, 15, 3, 2, 1, 16, 15, 16, 2, 37, 1, 37, 1,
1420 1, 1, 6, 6, 38, 1, 38, 11, 1, 39, 39, 40, 11, 2, 41, 4,
1421 40, 1, 2, 4, 1, 1, 1, 41, 3, 1, 3, 1, 5, 7, 5, 7},
1424 { 1, -1, 0, 1, 2, -1, -2, 1, -1, 3, -3, 1, -1, 2, -2, 4,
1425 -4, 1, -1, 1, 5, -1, -5, 1, -1, 2, -2, 3, 1, -3, -1, 6,
1426 -6, 0, 1, -1, 7, -7, 1, 2, -1, -2, 1, -1, 4, 8, -4, -8,
1427 1, -1, 3, -3, 9, -9, 1, 2, -2, -1, 1, 10, -10, -1, 5, -5,
1428 2, -2, 1, 11, -11, -1, 1, 3, 2, -1, -3, -2, 12, -12, 4, -4,
1429 2, -2, -6, 6, 13, -13, 1, -1, 14, -14, 1, -1, 3, -3, 7, -7,
1430 15, -15, 2, 1, -2, -1, 1, 5, -5, -1, -16, 2, 1, 16, -2, 4,
1431 -4, -1, 1, 3, -3, -1, 17, -17, 1, 1, -8, 8, -1, -1, 2, 18,
1432 -18, -2, 3, 1, -3, 19, -19, -1, 3, -3, 6, 1, -6, 20, 2, 9,
1433 -9, -1, -20, -2, 4, -4, 1, -5, 21, 5, -21, -1, 1, -22, -1, 2,
1434 22, -2, 10, 1, -10, 23, 1, 4, -23, 1, 2, -1, -2, -4, -7, 1,
1435 7, -24, -1, 24, -1, -1, 1, 3, -1, -25, 25, 4, -3, -4, 11, -11,
1436 26, -26, 6, 1, 1, -6, -5, -3, 3, 5, -1, -27, 27, 1, 4, -4,
1437 -1, -8, -1, 28, 2, 8, -12, -28, -2, -2, 2, 12, -1, 29, 1, -29,
1438 30, -30, 5, -5, 1, -31, -1, 3, 31, -1, 1, 1, -3, -13, 1, -7,
1439 -1, -32, 13, 7, 32, 33, -33, -1, -9, -34, 9, 34, -6, 5, 6, -5}
1445 {1, 1, 0, 1, 1, 2, 2, 1, 1, 3, 3, 1, 1, 0, 2, 2,
1446 4, 1, 4, 1, 1, 1, 5, 5, 1, 1, 6, 6, 2, 2, 1, 1,
1447 3, 3, 7, 7, 1, 1, 8, 8, 1, 1, 2, 2, 1, 9, 1, 9,
1448 4, 4, 10, 1, 1, 10, 1, 1, 11, 11, 3, 3, 1, 2, 1, 2,
1449 1, 1, 12, 12, 5, 5, 1, 1, 13, 1, 1, 13, 2, 2, 1, 1,
1450 6, 6, 1, 1, 4, 14, 4, 14, 3, 1, 3, 1, 1, 1, 15, 7,
1451 15, 2, 2, 7, 1, 1, 1, 8, 1, 8, 16, 16, 1, 1, 1, 1,
1452 2, 1, 1, 2, 1, 1, 3, 5, 5, 3, 4, 1, 1, 4, 1, 1,
1453 17, 17, 9, 1, 1, 9, 2, 2, 1, 1, 10, 10, 1, 6, 1, 1,
1454 6, 18, 1, 1, 18, 1, 1, 1, 2, 2, 3, 1, 3, 1, 1, 1,
1455 4, 1, 19, 1, 19, 7, 1, 1, 20, 1, 4, 20, 1, 7, 11, 2,
1456 1, 11, 21, 2, 8, 5, 1, 8, 1, 5, 21, 1, 1, 1, 22, 1,
1457 1, 22, 1, 1, 3, 3, 1, 23, 2, 12, 24, 1, 1, 2, 1, 1,
1458 12, 23, 1, 1, 24, 1, 1, 1, 4, 1, 1, 1, 2, 1, 6, 6,
1459 4, 2, 1, 1, 1, 1, 1, 1, 1, 14, 13, 3, 1, 25, 9, 25,
1460 14, 1, 9, 3, 13, 1, 1, 1, 1, 1, 10, 1, 1, 2, 10, 2},
1463 {-20, -1, 0, 2, -2, 1, -1, 3, -3, 1, -1, 4, -4, 0, 2, -2,
1464 1, 5, -1, -5, 6, -6, 1, -1, 7, -7, 1, -1, 3, -3, 8, -8,
1465 2, -2, 1, -1, 9, -9, 1, -1, 10, -10, 4, -4, 11, 1, -11, -1,
1466 2, -2, 1, 12, -12, -1, 13, -13, 1, -1, 3, -3, 14, 5, -14, -5,
1467 -15, 15, -1, 1, 2, -2, 16, -16, 1, 17, -17, -1, 6, -6, 18, -18,
1468 2, -2, -19, 19, -3, 1, 3, -1, 4, 20, -4, 1, -21, 21, 1, 2,
1469 -1, -7, 7, -2, 22, -22, 23, 2, -23, -2, 1, -1, -24, 24, -25, 25,
1470 -8, -26, 26, 8, -27, 27, 5, 3, -3, -5, -4, 28, -28, 4, 29, -29,
1471 1, -1, -2, -30, 30, 2, 9, -9, -31, 31, 2, -2, -32, 3, 32, -33,
1472 -3, 1, 33, -34, -1, 34, -35, 35, -10, 10, -6, 36, 6, -36, 37, -37,
1473 -5, 38, 1, -38, -1, 3, 39, -39, -1, 40, 5, 1, -40, -3, 2, -11,
1474 -41, -2, 1, 11, -3, -4, 41, 3, 42, 4, -1, -43, -42, 43, 1, -44,
1475 45, -1, 44, -45, -7, 7, -46, 1, -12, 2, 1, -47, 46, 12, 47, 48,
1476 -2, -1, -48, 49, -1, -50, -49, 50, -6, -51, 51, 52, -13, 53, -4, 4,
1477 6, 13, -53, -52, -54, 55, 54, -55, -56, -2, 2, -8, 56, 1, -3, -1,
1478 2, 58, 3, 8, -2, 57, -58, -60, -59, -57, -3, 60, 59, -14, 3, 14}
1484 {1, 1, 0, 2, 2, 1, 1, 3, 3, 4, 4, 5, 5, 1, 1, 6,
1485 6, 2, 2, 7, 7, 8, 8, 1, 1, 3, 3, 9, 9, 10, 10, 1,
1486 1, 2, 2, 4, 4, 11, 0, 11, 12, 12, 13, 13, 1, 1, 5, 5,
1487 14, 14, 15, 16, 15, 16, 3, 3, 1, 6, 1, 6, 2, 2, 7, 7,
1488 8, 8, 17, 17, 1, 1, 4, 4, 18, 18, 2, 2, 1, 19, 1, 20,
1489 19, 20, 21, 21, 3, 3, 22, 22, 5, 5, 24, 1, 1, 23, 9, 23,
1490 24, 9, 2, 2, 10, 1, 1, 10, 6, 6, 25, 4, 4, 25, 7, 7,
1491 26, 8, 1, 8, 3, 1, 26, 3, 11, 11, 27, 27, 2, 28, 1, 2,
1492 28, 1, 12, 12, 5, 5, 29, 13, 13, 29, 32, 1, 1, 33, 31, 30,
1493 32, 4, 30, 33, 4, 31, 3, 14, 1, 1, 3, 34, 34, 2, 2, 14,
1494 6, 6, 35, 36, 35, 36, 1, 15, 1, 16, 16, 15, 7, 9, 7, 9,
1495 37, 8, 8, 37, 1, 1, 39, 2, 38, 39, 2, 40, 5, 38, 40, 5,
1496 3, 3, 4, 4, 10, 10, 1, 1, 1, 1, 41, 2, 41, 2, 6, 6,
1497 1, 1, 11, 42, 11, 43, 3, 42, 3, 17, 4, 43, 1, 17, 7, 1,
1498 8, 44, 4, 7, 44, 5, 8, 2, 5, 1, 2, 48, 45, 1, 12, 45,
1499 12, 48, 13, 13, 1, 9, 9, 46, 1, 46, 47, 47, 49, 18, 18, 49},
1502 { 1, -1, 0, 1, -1, 2, -2, 1, -1, 1, -1, 1, -1, 3, -3, 1,
1503 -1, -2, 2, 1, -1, 1, -1, 4, -4, -2, 2, 1, -1, 1, -1, 5,
1504 -5, -3, 3, 2, -2, 1, 0, -1, 1, -1, 1, -1, 6, -6, 2, -2,
1505 1, -1, 1, 1, -1, -1, -3, 3, 7, 2, -7, -2, -4, 4, 2, -2,
1506 2, -2, 1, -1, 8, -8, 3, -3, 1, -1, -5, 5, 9, 1, -9, 1,
1507 -1, -1, 1, -1, -4, 4, 1, -1, 3, -3, 1, -10, 10, 1, 2, -1,
1508 -1, -2, 6, -6, 2, 11, -11, -2, 3, -3, 1, -4, 4, -1, 3, -3,
1509 1, 3, 12, -3, -5, -12, -1, 5, 2, -2, 1, -1, -7, 1, 13, 7,
1510 -1, -13, 2, -2, 4, -4, 1, 2, -2, -1, 1, 14, -14, 1, 1, 1,
1511 -1, -5, -1, -1, 5, -1, -6, 2, -15, 15, 6, 1, -1, -8, 8, -2,
1512 -4, 4, 1, 1, -1, -1, 16, 2, -16, -2, 2, -2, 4, 3, -4, -3,
1513 -1, -4, 4, 1, -17, 17, -1, -9, 1, 1, 9, 1, -5, -1, -1, 5,
1514 -7, 7, 6, -6, 3, -3, 18, -18, 19, -19, 1, -10, -1, 10, -5, 5,
1515 20, -20, -3, 1, 3, 1, 8, -1, -8, 2, 7, -1, -21, -2, 5, 21,
1516 5, -1, -7, -5, 1, -6, -5, -11, 6, 22, 11, 1, 1, -22, -3, -1,
1517 3, -1, 3, -3, -23, 4, -4, 1, 23, -1, 1, -1, 1, -2, 2, -1}
1523 {1, 1, 1, 1, 0, 2, 2, 1, 1, 3, 3, 0, 1, 1, 2, 2,
1524 4, 4, 1, 1, 5, 5, 1, 1, 2, 2, 3, 3, 6, 6, 1, 1,
1525 7, 7, 8, 1, 8, 2, 2, 1, 4, 4, 1, 3, 1, 3, 9, 9,
1526 2, 2, 1, 5, 1, 5, 10, 10, 1, 1, 11, 11, 3, 6, 3, 4,
1527 4, 6, 2, 2, 1, 12, 1, 12, 7, 13, 7, 13, 1, 1, 8, 8,
1528 2, 2, 14, 14, 16, 15, 16, 5, 5, 1, 3, 15, 1, 3, 4, 4,
1529 1, 1, 17, 17, 2, 2, 6, 6, 1, 18, 1, 18, 22, 21, 22, 21,
1530 25, 24, 25, 19, 9, 20, 9, 23, 19, 24, 20, 3, 23, 7, 3, 1,
1531 1, 7, 28, 26, 29, 5, 28, 26, 5, 8, 29, 4, 8, 27, 2, 2,
1532 4, 27, 1, 1, 10, 36, 10, 33, 33, 36, 30, 1, 32, 32, 1, 30,
1533 6, 31, 31, 35, 3, 6, 11, 11, 3, 2, 35, 2, 34, 1, 34, 1,
1534 37, 37, 12, 7, 12, 5, 41, 5, 4, 7, 1, 8, 13, 4, 1, 41,
1535 13, 38, 8, 38, 9, 1, 40, 40, 9, 1, 39, 2, 2, 49, 39, 42,
1536 3, 3, 14, 16, 49, 14, 16, 42, 43, 43, 6, 6, 15, 1, 1, 15,
1537 44, 44, 1, 1, 50, 48, 4, 5, 4, 7, 5, 2, 10, 10, 48, 7,
1538 50, 45, 2, 1, 45, 8, 8, 1, 46, 46, 3, 47, 47, 3, 1, 1},
1541 { 1, -1, 2, -2, 0, 1, -1, 3, -3, 1, -1, 0, 4, -4, 2, -2,
1542 1, -1, 5, -5, 1, -1, 6, -6, 3, -3, 2, -2, 1, -1, 7, -7,
1543 1, -1, 1, 8, -1, 4, -4, -8, 2, -2, 9, 3, -9, -3, 1, -1,
1544 5, -5, 10, 2, -10, -2, 1, -1, 11, -11, 1, -1, -4, 2, 4, 3,
1545 -3, -2, 6, -6, 12, 1, -12, -1, 2, 1, -2, -1, 13, -13, 2, -2,
1546 7, -7, 1, -1, 1, 1, -1, 3, -3, 14, 5, -1, -14, -5, 4, -4,
1547 15, -15, 1, -1, 8, -8, -3, 3, 16, 1, -16, -1, 1, 1, -1, -1,
1548 1, 1, -1, 1, 2, 1, -2, 1, -1, -1, -1, 6, -1, 3, -6, 17,
1549 -17, -3, 1, 1, 1, 4, -1, -1, -4, 3, -1, 5, -3, -1, -9, 9,
1550 -5, 1, 18, -18, 2, 1, -2, 1, -1, -1, 1, 19, -1, 1, -19, -1,
1551 4, 1, -1, 1, 7, -4, -2, 2, -7, 10, -1, -10, 1, 20, -1, -20,
1552 1, -1, 2, 4, -2, 5, 1, -5, 6, -4, 21, 4, 2, -6, -21, -1,
1553 -2, 1, -4, -1, -3, 22, -1, 1, 3, -22, -1, 11, -11, 1, 1, 1,
1554 8, -8, 2, 2, -1, -2, -2, -1, 1, -1, -5, 5, 2, 23, -23, -2,
1555 1, -1, 24, -24, -1, -1, 7, 6, -7, 5, -6, 12, -3, 3, 1, -5,
1556 1, 1, -12, 25, -1, -5, 5, -25, -1, 1, 9, 1, -1, -9, 26, -26}