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 #define BITSTREAM_READER_LE
32 #include "libavutil/attributes.h"
33 #include "libavutil/timer.h"
38 #include "ivi_common.h"
42 * These are 2x8 predefined Huffman codebooks for coding macroblock/block
43 * signals. They are specified using "huffman descriptors" in order to
44 * avoid huge static tables. The decoding tables will be generated at
45 * startup from these descriptors.
47 /** static macroblock huffman tables */
48 static const IVIHuffDesc ivi_mb_huff_desc[8] = {
49 {8, {0, 4, 5, 4, 4, 4, 6, 6}},
50 {12, {0, 2, 2, 3, 3, 3, 3, 5, 3, 2, 2, 2}},
51 {12, {0, 2, 3, 4, 3, 3, 3, 3, 4, 3, 2, 2}},
52 {12, {0, 3, 4, 4, 3, 3, 3, 3, 3, 2, 2, 2}},
53 {13, {0, 4, 4, 3, 3, 3, 3, 2, 3, 3, 2, 1, 1}},
54 {9, {0, 4, 4, 4, 4, 3, 3, 3, 2}},
55 {10, {0, 4, 4, 4, 4, 3, 3, 2, 2, 2}},
56 {12, {0, 4, 4, 4, 3, 3, 2, 3, 2, 2, 2, 2}}
59 /** static block huffman tables */
60 static const IVIHuffDesc ivi_blk_huff_desc[8] = {
61 {10, {1, 2, 3, 4, 4, 7, 5, 5, 4, 1}},
62 {11, {2, 3, 4, 4, 4, 7, 5, 4, 3, 3, 2}},
63 {12, {2, 4, 5, 5, 5, 5, 6, 4, 4, 3, 1, 1}},
64 {13, {3, 3, 4, 4, 5, 6, 6, 4, 4, 3, 2, 1, 1}},
65 {11, {3, 4, 4, 5, 5, 5, 6, 5, 4, 2, 2}},
66 {13, {3, 4, 5, 5, 5, 5, 6, 4, 3, 3, 2, 1, 1}},
67 {13, {3, 4, 5, 5, 5, 6, 5, 4, 3, 3, 2, 1, 1}},
68 {9, {3, 4, 4, 5, 5, 5, 6, 5, 5}}
71 static VLC ivi_mb_vlc_tabs [8]; ///< static macroblock Huffman tables
72 static VLC ivi_blk_vlc_tabs[8]; ///< static block Huffman tables
74 typedef void (*ivi_mc_func) (int16_t *buf, const int16_t *ref_buf,
75 uint32_t pitch, int mc_type);
76 typedef void (*ivi_mc_avg_func) (int16_t *buf, const int16_t *ref_buf1,
77 const int16_t *ref_buf2,
78 uint32_t pitch, int mc_type, int mc_type2);
80 static int ivi_mc(IVIBandDesc *band, ivi_mc_func mc, ivi_mc_avg_func mc_avg,
81 int offs, int mv_x, int mv_y, int mv_x2, int mv_y2,
82 int mc_type, int mc_type2)
84 int ref_offs = offs + mv_y * band->pitch + mv_x;
85 int buf_size = band->pitch * band->aheight;
86 int min_size = band->pitch * (band->blk_size - 1) + band->blk_size;
87 int ref_size = (mc_type > 1) * band->pitch + (mc_type & 1);
90 if (offs < 0 || ref_offs < 0 || !band->ref_buf)
91 return AVERROR_INVALIDDATA;
92 if (buf_size - min_size < offs)
93 return AVERROR_INVALIDDATA;
94 if (buf_size - min_size - ref_size < ref_offs)
95 return AVERROR_INVALIDDATA;
99 mc(band->buf + offs, band->ref_buf + ref_offs, band->pitch, mc_type);
101 int ref_offs2 = offs + mv_y2 * band->pitch + mv_x2;
102 int ref_size2 = (mc_type2 > 1) * band->pitch + (mc_type2 & 1);
103 if (offs < 0 || ref_offs2 < 0 || !band->b_ref_buf)
104 return AVERROR_INVALIDDATA;
105 if (buf_size - min_size - ref_size2 < ref_offs2)
106 return AVERROR_INVALIDDATA;
109 mc(band->buf + offs, band->b_ref_buf + ref_offs2,
110 band->pitch, mc_type2);
112 mc_avg(band->buf + offs, band->ref_buf + ref_offs,
113 band->b_ref_buf + ref_offs2, band->pitch,
121 * Reverse "nbits" bits of the value "val" and return the result
122 * in the least significant bits.
124 static uint16_t inv_bits(uint16_t val, int nbits)
129 res = ff_reverse[val] >> (8 - nbits);
131 res = ((ff_reverse[val & 0xFF] << 8) +
132 (ff_reverse[val >> 8])) >> (16 - nbits);
138 * Generate a huffman codebook from the given descriptor
139 * and convert it into the Libav VLC table.
141 * @param[in] cb pointer to codebook descriptor
142 * @param[out] vlc where to place the generated VLC table
143 * @param[in] flag flag: 1 - for static or 0 for dynamic tables
144 * @return result code: 0 - OK, -1 = error (invalid codebook descriptor)
146 static int ivi_create_huff_from_desc(const IVIHuffDesc *cb, VLC *vlc, int flag)
148 int pos, i, j, codes_per_row, prefix, not_last_row;
149 uint16_t codewords[256]; /* FIXME: move this temporal storage out? */
152 pos = 0; /* current position = 0 */
154 for (i = 0; i < cb->num_rows; i++) {
155 codes_per_row = 1 << cb->xbits[i];
156 not_last_row = (i != cb->num_rows - 1);
157 prefix = ((1 << i) - 1) << (cb->xbits[i] + not_last_row);
159 for (j = 0; j < codes_per_row; j++) {
160 if (pos >= 256) /* Some Indeo5 codebooks can have more than 256 */
161 break; /* elements, but only 256 codes are allowed! */
163 bits[pos] = i + cb->xbits[i] + not_last_row;
164 if (bits[pos] > IVI_VLC_BITS)
165 return AVERROR_INVALIDDATA; /* invalid descriptor */
167 codewords[pos] = inv_bits((prefix | j), bits[pos]);
175 /* number of codewords = pos */
176 return init_vlc(vlc, IVI_VLC_BITS, pos, bits, 1, 1, codewords, 2, 2,
177 (flag ? INIT_VLC_USE_NEW_STATIC : 0) | INIT_VLC_LE);
180 av_cold void ff_ivi_init_static_vlc(void)
183 static VLC_TYPE table_data[8192 * 16][2];
184 static int initialized_vlcs = 0;
186 if (initialized_vlcs)
188 for (i = 0; i < 8; i++) {
189 ivi_mb_vlc_tabs[i].table = table_data + i * 2 * 8192;
190 ivi_mb_vlc_tabs[i].table_allocated = 8192;
191 ivi_create_huff_from_desc(&ivi_mb_huff_desc[i],
192 &ivi_mb_vlc_tabs[i], 1);
193 ivi_blk_vlc_tabs[i].table = table_data + (i * 2 + 1) * 8192;
194 ivi_blk_vlc_tabs[i].table_allocated = 8192;
195 ivi_create_huff_from_desc(&ivi_blk_huff_desc[i],
196 &ivi_blk_vlc_tabs[i], 1);
198 initialized_vlcs = 1;
202 * Copy huffman codebook descriptors.
204 * @param[out] dst ptr to the destination descriptor
205 * @param[in] src ptr to the source descriptor
207 static void ivi_huff_desc_copy(IVIHuffDesc *dst, const IVIHuffDesc *src)
209 dst->num_rows = src->num_rows;
210 memcpy(dst->xbits, src->xbits, src->num_rows);
214 * Compare two huffman codebook descriptors.
216 * @param[in] desc1 ptr to the 1st descriptor to compare
217 * @param[in] desc2 ptr to the 2nd descriptor to compare
218 * @return comparison result: 0 - equal, 1 - not equal
220 static int ivi_huff_desc_cmp(const IVIHuffDesc *desc1,
221 const IVIHuffDesc *desc2)
223 return desc1->num_rows != desc2->num_rows ||
224 memcmp(desc1->xbits, desc2->xbits, desc1->num_rows);
227 int ff_ivi_dec_huff_desc(GetBitContext *gb, int desc_coded, int which_tab,
228 IVIHuffTab *huff_tab, AVCodecContext *avctx)
231 IVIHuffDesc new_huff;
234 /* select default table */
235 huff_tab->tab = (which_tab) ? &ivi_blk_vlc_tabs[7]
236 : &ivi_mb_vlc_tabs [7];
240 huff_tab->tab_sel = get_bits(gb, 3);
241 if (huff_tab->tab_sel == 7) {
242 /* custom huffman table (explicitly encoded) */
243 new_huff.num_rows = get_bits(gb, 4);
244 if (!new_huff.num_rows) {
245 av_log(avctx, AV_LOG_ERROR, "Empty custom Huffman table!\n");
246 return AVERROR_INVALIDDATA;
249 for (i = 0; i < new_huff.num_rows; i++)
250 new_huff.xbits[i] = get_bits(gb, 4);
252 /* Have we got the same custom table? Rebuild if not. */
253 if (ivi_huff_desc_cmp(&new_huff, &huff_tab->cust_desc)) {
254 ivi_huff_desc_copy(&huff_tab->cust_desc, &new_huff);
256 if (huff_tab->cust_tab.table)
257 ff_free_vlc(&huff_tab->cust_tab);
258 result = ivi_create_huff_from_desc(&huff_tab->cust_desc,
259 &huff_tab->cust_tab, 0);
261 // reset faulty description
262 huff_tab->cust_desc.num_rows = 0;
263 av_log(avctx, AV_LOG_ERROR,
264 "Error while initializing custom vlc table!\n");
268 huff_tab->tab = &huff_tab->cust_tab;
270 /* select one of predefined tables */
271 huff_tab->tab = (which_tab) ? &ivi_blk_vlc_tabs[huff_tab->tab_sel]
272 : &ivi_mb_vlc_tabs [huff_tab->tab_sel];
279 * Free planes, bands and macroblocks buffers.
281 * @param[in] planes pointer to the array of the plane descriptors
283 static av_cold void ivi_free_buffers(IVIPlaneDesc *planes)
287 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(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 (cfg->pic_width < 1 || cfg->pic_height < 1 ||
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(planes[p].num_bands * sizeof(IVIBandDesc));
331 if (!planes[p].bands)
332 return AVERROR(ENOMEM);
334 /* select band dimensions: if there is only one band then it
335 * has the full size, if there are several bands each of them
336 * has only half size */
337 b_width = planes[p].num_bands == 1 ? planes[p].width
338 : (planes[p].width + 1) >> 1;
339 b_height = planes[p].num_bands == 1 ? planes[p].height
340 : (planes[p].height + 1) >> 1;
342 /* luma band buffers will be aligned on 16x16 (max macroblock size) */
343 /* chroma band buffers will be aligned on 8x8 (max macroblock size) */
344 align_fac = p ? 8 : 16;
345 width_aligned = FFALIGN(b_width , align_fac);
346 height_aligned = FFALIGN(b_height, align_fac);
347 buf_size = width_aligned * height_aligned * sizeof(int16_t);
349 for (b = 0; b < planes[p].num_bands; b++) {
350 band = &planes[p].bands[b]; /* select appropriate plane/band */
353 band->width = b_width;
354 band->height = b_height;
355 band->pitch = width_aligned;
356 band->aheight = height_aligned;
357 band->bufs[0] = av_mallocz(buf_size);
358 band->bufs[1] = av_mallocz(buf_size);
359 if (!band->bufs[0] || !band->bufs[1])
360 return AVERROR(ENOMEM);
362 /* allocate the 3rd band buffer for scalability mode */
363 if (cfg->luma_bands > 1) {
364 band->bufs[2] = av_mallocz(buf_size);
366 return AVERROR(ENOMEM);
369 band->bufs[3] = av_mallocz(buf_size);
371 return AVERROR(ENOMEM);
373 /* reset custom vlc */
374 planes[p].bands[0].blk_vlc.cust_desc.num_rows = 0;
381 static int ivi_init_tiles(IVIBandDesc *band, IVITile *ref_tile,
382 int p, int b, int t_height, int t_width)
385 IVITile *tile = band->tiles;
387 for (y = 0; y < band->height; y += t_height) {
388 for (x = 0; x < band->width; x += t_width) {
391 tile->mb_size = band->mb_size;
392 tile->width = FFMIN(band->width - x, t_width);
393 tile->height = FFMIN(band->height - y, t_height);
394 tile->is_empty = tile->data_size = 0;
395 /* calculate number of macroblocks */
396 tile->num_MBs = IVI_MBs_PER_TILE(tile->width, tile->height,
399 av_freep(&tile->mbs);
400 tile->mbs = av_malloc(tile->num_MBs * sizeof(IVIMbInfo));
402 return AVERROR(ENOMEM);
406 if (tile->num_MBs != ref_tile->num_MBs)
407 return AVERROR_INVALIDDATA;
408 tile->ref_mbs = ref_tile->mbs;
418 av_cold int ff_ivi_init_tiles(IVIPlaneDesc *planes,
419 int tile_width, int tile_height)
421 int p, b, x_tiles, y_tiles, t_width, t_height, ret;
424 for (p = 0; p < 3; p++) {
425 t_width = !p ? tile_width : (tile_width + 3) >> 2;
426 t_height = !p ? tile_height : (tile_height + 3) >> 2;
428 if (!p && planes[0].num_bands == 4) {
433 for (b = 0; b < planes[p].num_bands; b++) {
434 band = &planes[p].bands[b];
435 x_tiles = IVI_NUM_TILES(band->width, t_width);
436 y_tiles = IVI_NUM_TILES(band->height, t_height);
437 band->num_tiles = x_tiles * y_tiles;
439 av_freep(&band->tiles);
440 band->tiles = av_mallocz(band->num_tiles * sizeof(IVITile));
442 return AVERROR(ENOMEM);
444 /* use the first luma band as reference for motion vectors
446 ret = ivi_init_tiles(band, planes[0].bands[0].tiles,
447 p, b, t_height, t_width);
457 * Decode size of the tile data.
458 * The size is stored as a variable-length field having the following format:
459 * if (tile_data_size < 255) than this field is only one byte long
460 * if (tile_data_size >= 255) than this field four is byte long: 0xFF X1 X2 X3
461 * where X1-X3 is size of the tile data
463 * @param[in,out] gb the GetBit context
464 * @return size of the tile data in bytes
466 static int ivi_dec_tile_data_size(GetBitContext *gb)
472 len = get_bits(gb, 8);
474 len = get_bits_long(gb, 24);
477 /* align the bitstream reader on the byte boundary */
483 static int ivi_dc_transform(IVIBandDesc *band, int *prev_dc, int buf_offs,
486 int buf_size = band->pitch * band->aheight - buf_offs;
487 int min_size = (blk_size - 1) * band->pitch + blk_size;
489 if (!band->dc_transform)
493 if (min_size > buf_size)
494 return AVERROR_INVALIDDATA;
496 band->dc_transform(prev_dc, band->buf + buf_offs,
497 band->pitch, blk_size);
502 static int ivi_decode_coded_blocks(GetBitContext *gb, IVIBandDesc *band,
503 ivi_mc_func mc, ivi_mc_avg_func mc_avg,
505 int mv_x2, int mv_y2,
506 int *prev_dc, int is_intra,
507 int mc_type, int mc_type2,
508 uint32_t quant, int offs,
509 AVCodecContext *avctx)
511 const uint16_t *base_tab = is_intra ? band->intra_base : band->inter_base;
512 RVMapDesc *rvmap = band->rv_map;
513 uint8_t col_flags[8];
515 uint32_t sym = 0, lo, hi, q;
517 int blk_size = band->blk_size;
518 int num_coeffs = blk_size * blk_size;
519 int col_mask = blk_size - 1;
521 int min_size = band->pitch * (band->transform_size - 1) +
522 band->transform_size;
523 int buf_size = band->pitch * band->aheight - offs;
525 if (min_size > buf_size)
526 return AVERROR_INVALIDDATA;
529 av_log(avctx, AV_LOG_ERROR, "Scan pattern is not set.\n");
530 return AVERROR_INVALIDDATA;
533 /* zero transform vector */
534 memset(trvec, 0, num_coeffs * sizeof(trvec[0]));
535 /* zero column flags */
536 memset(col_flags, 0, sizeof(col_flags));
537 while (scan_pos <= num_coeffs) {
538 sym = get_vlc2(gb, band->blk_vlc.tab->table,
540 if (sym == rvmap->eob_sym)
541 break; /* End of block */
543 /* Escape - run/val explicitly coded using 3 vlc codes */
544 if (sym == rvmap->esc_sym) {
545 run = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1) + 1;
546 lo = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
547 hi = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
548 /* merge them and convert into signed val */
549 val = IVI_TOSIGNED((hi << 6) | lo);
552 av_log(avctx, AV_LOG_ERROR, "Invalid sym encountered: %"PRIu32".\n", sym);
553 return AVERROR_INVALIDDATA;
555 run = rvmap->runtab[sym];
556 val = rvmap->valtab[sym];
559 /* de-zigzag and dequantize */
561 if (scan_pos >= num_coeffs || scan_pos < 0)
563 pos = band->scan[scan_pos];
566 av_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] 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, 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(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 /* 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, int dst_pitch)
887 const int16_t *src = plane->bands[0].buf;
888 uint32_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 + (get_bits_count(&ctx->gb) >> 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 = get_bits_count(&ctx->gb);
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 = get_bits1(&ctx->gb);
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 av_dlog(avctx, "Empty tile encountered!\n");
969 tile->data_size = ivi_dec_tile_data_size(&ctx->gb);
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->gb, band, tile, avctx);
981 av_log(avctx, AV_LOG_ERROR,
982 "Corrupted tile data encountered!\n");
986 if (((get_bits_count(&ctx->gb) - 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 align_get_bits(&ctx->gb);
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 init_get_bits(&ctx->gb, buf, buf_size * 8);
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!\n");
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 (get_bits(&ctx->gb, 8)); // skip version string
1125 left = get_bits_count(&ctx->gb) & 0x18;
1126 skip_bits_long(&ctx->gb, 64 - left);
1127 if (get_bits_left(&ctx->gb) > 18 &&
1128 show_bits_long(&ctx->gb, 21) == 0xBFFF8) { // syncheader + inter type
1130 pkt.data = avpkt->data + (get_bits_count(&ctx->gb) >> 3);
1131 pkt.size = get_bits_left(&ctx->gb) >> 3;
1132 ff_ivi_decode_frame(avctx, ctx->p_frame, &ctx->got_p_frame, &pkt);
1140 * Close Indeo5 decoder and clean up its context.
1142 av_cold int ff_ivi_decode_close(AVCodecContext *avctx)
1144 IVI45DecContext *ctx = avctx->priv_data;
1146 ivi_free_buffers(&ctx->planes[0]);
1148 if (ctx->mb_vlc.cust_tab.table)
1149 ff_free_vlc(&ctx->mb_vlc.cust_tab);
1151 #if IVI4_STREAM_ANALYSER
1152 if (ctx->is_indeo4) {
1153 if (ctx->is_scalable)
1154 av_log(avctx, AV_LOG_ERROR, "This video uses scalability mode!\n");
1155 if (ctx->uses_tiling)
1156 av_log(avctx, AV_LOG_ERROR, "This video uses local decoding!\n");
1157 if (ctx->has_b_frames)
1158 av_log(avctx, AV_LOG_ERROR, "This video contains B-frames!\n");
1159 if (ctx->has_transp)
1160 av_log(avctx, AV_LOG_ERROR, "Transparency mode is enabled!\n");
1162 av_log(avctx, AV_LOG_ERROR, "This video uses Haar transform!\n");
1163 if (ctx->uses_fullpel)
1164 av_log(avctx, AV_LOG_ERROR, "This video uses fullpel motion vectors!\n");
1168 av_frame_free(&ctx->p_frame);
1175 * Scan patterns shared between indeo4 and indeo5
1177 const uint8_t ff_ivi_vertical_scan_8x8[64] = {
1178 0, 8, 16, 24, 32, 40, 48, 56,
1179 1, 9, 17, 25, 33, 41, 49, 57,
1180 2, 10, 18, 26, 34, 42, 50, 58,
1181 3, 11, 19, 27, 35, 43, 51, 59,
1182 4, 12, 20, 28, 36, 44, 52, 60,
1183 5, 13, 21, 29, 37, 45, 53, 61,
1184 6, 14, 22, 30, 38, 46, 54, 62,
1185 7, 15, 23, 31, 39, 47, 55, 63
1188 const uint8_t ff_ivi_horizontal_scan_8x8[64] = {
1189 0, 1, 2, 3, 4, 5, 6, 7,
1190 8, 9, 10, 11, 12, 13, 14, 15,
1191 16, 17, 18, 19, 20, 21, 22, 23,
1192 24, 25, 26, 27, 28, 29, 30, 31,
1193 32, 33, 34, 35, 36, 37, 38, 39,
1194 40, 41, 42, 43, 44, 45, 46, 47,
1195 48, 49, 50, 51, 52, 53, 54, 55,
1196 56, 57, 58, 59, 60, 61, 62, 63
1199 const uint8_t ff_ivi_direct_scan_4x4[16] = {
1200 0, 1, 4, 8, 5, 2, 3, 6, 9, 12, 13, 10, 7, 11, 14, 15
1205 * Run-value (RLE) tables.
1207 const RVMapDesc ff_ivi_rvmap_tabs[9] = {
1212 {1, 1, 0, 1, 1, 0, 1, 1, 2, 2, 1, 1, 1, 1, 3, 3,
1213 1, 1, 2, 2, 1, 1, 4, 4, 1, 1, 1, 1, 2, 2, 5, 5,
1214 1, 1, 3, 3, 1, 1, 6, 6, 1, 2, 1, 2, 7, 7, 1, 1,
1215 8, 8, 1, 1, 4, 2, 1, 4, 2, 1, 3, 3, 1, 1, 1, 9,
1216 9, 1, 2, 1, 2, 1, 5, 5, 1, 1, 10, 10, 1, 1, 3, 3,
1217 2, 2, 1, 1, 11, 11, 6, 4, 4, 1, 6, 1, 2, 1, 2, 12,
1218 8, 1, 12, 7, 8, 7, 1, 16, 1, 16, 1, 3, 3, 13, 1, 13,
1219 2, 2, 1, 15, 1, 5, 14, 15, 1, 5, 14, 1, 17, 8, 17, 8,
1220 1, 4, 4, 2, 2, 1, 25, 25, 24, 24, 1, 3, 1, 3, 1, 8,
1221 6, 7, 6, 1, 18, 8, 18, 1, 7, 23, 2, 2, 23, 1, 1, 21,
1222 22, 9, 9, 22, 19, 1, 21, 5, 19, 5, 1, 33, 20, 33, 20, 8,
1223 4, 4, 1, 32, 2, 2, 8, 3, 32, 26, 3, 1, 7, 7, 26, 6,
1224 1, 6, 1, 1, 16, 1, 10, 1, 10, 2, 16, 29, 28, 2, 29, 28,
1225 1, 27, 5, 8, 5, 27, 1, 8, 3, 7, 3, 31, 41, 31, 1, 41,
1226 6, 1, 6, 7, 4, 4, 1, 1, 2, 1, 2, 11, 34, 30, 11, 1,
1227 30, 15, 15, 34, 36, 40, 36, 40, 35, 35, 37, 37, 39, 39, 38, 38},
1230 { 1, -1, 0, 2, -2, 0, 3, -3, 1, -1, 4, -4, 5, -5, 1, -1,
1231 6, -6, 2, -2, 7, -7, 1, -1, 8, -8, 9, -9, 3, -3, 1, -1,
1232 10, -10, 2, -2, 11, -11, 1, -1, 12, 4, -12, -4, 1, -1, 13, -13,
1233 1, -1, 14, -14, 2, 5, 15, -2, -5, -15, -3, 3, 16, -16, 17, 1,
1234 -1, -17, 6, 18, -6, -18, 2, -2, 19, -19, 1, -1, 20, -20, 4, -4,
1235 7, -7, 21, -21, 1, -1, 2, 3, -3, 22, -2, -22, 8, 23, -8, 1,
1236 2, -23, -1, 2, -2, -2, 24, 1, -24, -1, 25, 5, -5, 1, -25, -1,
1237 9, -9, 26, 1, -26, 3, 1, -1, 27, -3, -1, -27, 1, 3, -1, -3,
1238 28, -4, 4, 10, -10, -28, 1, -1, 1, -1, 29, 6, -29, -6, 30, -4,
1239 3, 3, -3, -30, 1, 4, -1, 31, -3, 1, 11, -11, -1, -31, 32, -1,
1240 -1, 2, -2, 1, 1, -32, 1, 4, -1, -4, 33, -1, 1, 1, -1, 5,
1241 5, -5, -33, -1, -12, 12, -5, -7, 1, 1, 7, 34, 4, -4, -1, 4,
1242 -34, -4, 35, 36, -2, -35, -2, -36, 2, 13, 2, -1, 1, -13, 1, -1,
1243 37, 1, -5, 6, 5, -1, 38, -6, -8, 5, 8, -1, 1, 1, -37, -1,
1244 5, 39, -5, -5, 6, -6, -38, -39, -14, 40, 14, 2, 1, 1, -2, -40,
1245 -1, -2, 2, -1, -1, -1, 1, 1, 1, -1, 1, -1, 1, -1, 1, -1}
1251 {0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 8, 6, 8, 7,
1252 7, 9, 9, 10, 10, 11, 11, 1, 12, 1, 12, 13, 13, 16, 14, 16,
1253 14, 15, 15, 17, 17, 18, 0, 18, 19, 20, 21, 19, 22, 21, 20, 22,
1254 25, 24, 2, 25, 24, 23, 23, 2, 26, 28, 26, 28, 29, 27, 29, 27,
1255 33, 33, 1, 32, 1, 3, 32, 30, 36, 3, 36, 30, 31, 31, 35, 34,
1256 37, 41, 34, 35, 37, 4, 41, 4, 49, 8, 8, 49, 40, 38, 5, 38,
1257 40, 39, 5, 39, 42, 43, 42, 7, 57, 6, 43, 44, 6, 50, 7, 44,
1258 57, 48, 50, 48, 45, 45, 46, 47, 51, 46, 47, 58, 1, 51, 58, 1,
1259 52, 59, 53, 9, 52, 55, 55, 59, 53, 56, 54, 56, 54, 9, 64, 64,
1260 60, 63, 60, 63, 61, 62, 61, 62, 2, 10, 2, 10, 11, 1, 11, 13,
1261 12, 1, 12, 13, 16, 16, 8, 8, 14, 3, 3, 15, 14, 15, 4, 4,
1262 1, 17, 17, 5, 1, 7, 7, 5, 6, 1, 2, 2, 6, 22, 1, 25,
1263 21, 22, 8, 24, 1, 21, 25, 24, 8, 18, 18, 23, 9, 20, 23, 33,
1264 29, 33, 20, 1, 19, 1, 29, 36, 9, 36, 19, 41, 28, 57, 32, 3,
1265 28, 3, 1, 27, 49, 49, 1, 32, 26, 26, 2, 4, 4, 7, 57, 41,
1266 2, 7, 10, 5, 37, 16, 10, 27, 8, 8, 13, 16, 37, 13, 1, 5},
1269 {0, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, 1, -1, -1, 1,
1270 -1, 1, -1, 1, -1, 1, -1, 2, 1, -2, -1, 1, -1, 1, 1, -1,
1271 -1, 1, -1, 1, -1, 1, 0, -1, 1, 1, 1, -1, 1, -1, -1, -1,
1272 1, 1, 2, -1, -1, 1, -1, -2, 1, 1, -1, -1, 1, 1, -1, -1,
1273 1, -1, 3, 1, -3, 2, -1, 1, 1, -2, -1, -1, -1, 1, 1, 1,
1274 1, 1, -1, -1, -1, 2, -1, -2, 1, 2, -2, -1, 1, 1, 2, -1,
1275 -1, 1, -2, -1, 1, 1, -1, 2, 1, 2, -1, 1, -2, -1, -2, -1,
1276 -1, 1, 1, -1, 1, -1, 1, 1, 1, -1, -1, 1, 4, -1, -1, -4,
1277 1, 1, 1, 2, -1, -1, 1, -1, -1, 1, -1, -1, 1, -2, 1, -1,
1278 1, 1, -1, -1, 1, 1, -1, -1, 3, 2, -3, -2, 2, 5, -2, 2,
1279 2, -5, -2, -2, -2, 2, -3, 3, 2, 3, -3, 2, -2, -2, 3, -3,
1280 6, 2, -2, 3, -6, 3, -3, -3, 3, 7, -4, 4, -3, 2, -7, 2,
1281 2, -2, -4, 2, 8, -2, -2, -2, 4, 2, -2, 2, 3, 2, -2, -2,
1282 2, 2, -2, -8, -2, 9, -2, 2, -3, -2, 2, -2, 2, 2, 2, 4,
1283 -2, -4, 10, 2, 2, -2, -9, -2, 2, -2, 5, 4, -4, 4, -2, 2,
1284 -5, -4, -3, 4, 2, -3, 3, -2, -5, 5, 3, 3, -2, -3, -10, -4}
1290 {1, 1, 0, 2, 2, 1, 1, 3, 3, 4, 4, 0, 1, 1, 5, 5,
1291 2, 2, 6, 6, 7, 7, 1, 8, 1, 8, 3, 3, 9, 9, 1, 2,
1292 2, 1, 4, 10, 4, 10, 11, 11, 1, 5, 12, 12, 1, 5, 13, 13,
1293 3, 3, 6, 6, 2, 2, 14, 14, 16, 16, 15, 7, 15, 8, 8, 7,
1294 1, 1, 17, 17, 4, 4, 1, 1, 18, 18, 2, 2, 5, 5, 25, 3,
1295 9, 3, 25, 9, 19, 24, 19, 24, 1, 21, 20, 1, 21, 22, 20, 22,
1296 23, 23, 8, 6, 33, 6, 8, 33, 7, 7, 26, 26, 1, 32, 1, 32,
1297 28, 4, 28, 10, 29, 27, 27, 10, 41, 4, 29, 2, 2, 41, 36, 31,
1298 49, 31, 34, 30, 34, 36, 30, 35, 1, 49, 11, 5, 35, 11, 1, 3,
1299 3, 5, 37, 37, 8, 40, 8, 40, 12, 12, 42, 42, 1, 38, 16, 57,
1300 1, 6, 16, 39, 38, 6, 7, 7, 13, 13, 39, 43, 2, 43, 57, 2,
1301 50, 9, 44, 9, 50, 4, 15, 48, 44, 4, 1, 15, 48, 14, 14, 1,
1302 45, 45, 8, 3, 5, 8, 51, 47, 3, 46, 46, 47, 5, 51, 1, 17,
1303 17, 58, 1, 58, 2, 52, 52, 2, 53, 7, 59, 6, 6, 56, 53, 55,
1304 7, 55, 1, 54, 59, 56, 54, 10, 1, 10, 4, 60, 1, 60, 8, 4,
1305 8, 64, 64, 61, 1, 63, 3, 63, 62, 61, 5, 11, 5, 3, 11, 62},
1308 { 1, -1, 0, 1, -1, 2, -2, 1, -1, 1, -1, 0, 3, -3, 1, -1,
1309 2, -2, 1, -1, 1, -1, 4, 1, -4, -1, 2, -2, 1, -1, 5, 3,
1310 -3, -5, 2, 1, -2, -1, 1, -1, 6, 2, 1, -1, -6, -2, 1, -1,
1311 3, -3, 2, -2, 4, -4, 1, -1, 1, -1, 1, 2, -1, 2, -2, -2,
1312 7, -7, 1, -1, 3, -3, 8, -8, 1, -1, 5, -5, 3, -3, 1, 4,
1313 2, -4, -1, -2, 1, 1, -1, -1, 9, 1, 1, -9, -1, 1, -1, -1,
1314 1, -1, 3, -3, 1, 3, -3, -1, 3, -3, 1, -1, 10, 1, -10, -1,
1315 1, 4, -1, 2, 1, -1, 1, -2, 1, -4, -1, 6, -6, -1, 1, 1,
1316 1, -1, 1, 1, -1, -1, -1, 1, 11, -1, -2, 4, -1, 2, -11, 5,
1317 -5, -4, -1, 1, 4, 1, -4, -1, -2, 2, 1, -1, 12, 1, -2, 1,
1318 -12, 4, 2, 1, -1, -4, 4, -4, 2, -2, -1, 1, 7, -1, -1, -7,
1319 -1, -3, 1, 3, 1, 5, 2, 1, -1, -5, 13, -2, -1, 2, -2, -13,
1320 1, -1, 5, 6, 5, -5, 1, 1, -6, 1, -1, -1, -5, -1, 14, 2,
1321 -2, 1, -14, -1, 8, 1, -1, -8, 1, 5, 1, 5, -5, 1, -1, 1,
1322 -5, -1, 15, 1, -1, -1, -1, 3, -15, -3, 6, 1, 16, -1, 6, -6,
1323 -6, 1, -1, 1, -16, 1, 7, -1, 1, -1, -6, -3, 6, -7, 3, -1}
1329 {0, 1, 1, 2, 2, 3, 3, 4, 4, 1, 1, 5, 5, 6, 6, 7,
1330 7, 8, 8, 9, 9, 2, 2, 10, 10, 1, 1, 11, 11, 12, 12, 3,
1331 3, 13, 13, 0, 14, 14, 16, 15, 16, 15, 4, 4, 17, 1, 17, 1,
1332 5, 5, 18, 18, 2, 2, 6, 6, 8, 19, 7, 8, 7, 19, 20, 20,
1333 21, 21, 22, 24, 22, 24, 23, 23, 1, 1, 25, 25, 3, 3, 26, 26,
1334 9, 9, 27, 27, 28, 28, 33, 29, 4, 33, 29, 1, 4, 1, 32, 32,
1335 2, 2, 31, 10, 30, 10, 30, 31, 34, 34, 5, 5, 36, 36, 35, 41,
1336 35, 11, 41, 11, 37, 1, 8, 8, 37, 6, 1, 6, 40, 7, 7, 40,
1337 12, 38, 12, 39, 39, 38, 49, 13, 49, 13, 3, 42, 3, 42, 16, 16,
1338 43, 43, 14, 14, 1, 1, 44, 15, 44, 15, 2, 2, 57, 48, 50, 48,
1339 57, 50, 4, 45, 45, 4, 46, 47, 47, 46, 1, 51, 1, 17, 17, 51,
1340 8, 9, 9, 5, 58, 8, 58, 5, 52, 52, 55, 56, 53, 56, 55, 59,
1341 59, 53, 54, 1, 6, 54, 7, 7, 6, 1, 2, 3, 2, 3, 64, 60,
1342 60, 10, 10, 64, 61, 62, 61, 63, 1, 63, 62, 1, 18, 24, 18, 4,
1343 25, 4, 8, 21, 21, 1, 24, 22, 25, 22, 8, 11, 19, 11, 23, 1,
1344 20, 23, 19, 20, 5, 12, 5, 1, 16, 2, 12, 13, 2, 13, 1, 16},
1347 { 0, 1, -1, 1, -1, 1, -1, 1, -1, 2, -2, 1, -1, 1, -1, 1,
1348 -1, 1, -1, 1, -1, 2, -2, 1, -1, 3, -3, 1, -1, 1, -1, 2,
1349 -2, 1, -1, 0, 1, -1, 1, 1, -1, -1, 2, -2, 1, 4, -1, -4,
1350 2, -2, 1, -1, -3, 3, 2, -2, 2, 1, 2, -2, -2, -1, 1, -1,
1351 1, -1, 1, 1, -1, -1, 1, -1, 5, -5, 1, -1, 3, -3, 1, -1,
1352 2, -2, 1, -1, 1, -1, 1, 1, 3, -1, -1, 6, -3, -6, -1, 1,
1353 4, -4, 1, 2, 1, -2, -1, -1, 1, -1, 3, -3, 1, -1, 1, 1,
1354 -1, 2, -1, -2, 1, 7, -3, 3, -1, 3, -7, -3, 1, -3, 3, -1,
1355 2, 1, -2, 1, -1, -1, 1, 2, -1, -2, -4, -1, 4, 1, 2, -2,
1356 1, -1, -2, 2, 8, -8, -1, 2, 1, -2, -5, 5, 1, -1, -1, 1,
1357 -1, 1, 4, -1, 1, -4, -1, -1, 1, 1, 9, 1, -9, 2, -2, -1,
1358 -4, 3, -3, -4, -1, 4, 1, 4, 1, -1, 1, -1, 1, 1, -1, 1,
1359 -1, -1, -1, 10, 4, 1, 4, -4, -4, -10, 6, 5, -6, -5, 1, -1,
1360 1, 3, -3, -1, 1, -1, -1, -1, 11, 1, 1, -11, -2, -2, 2, 5,
1361 -2, -5, -5, 2, -2, 12, 2, -2, 2, 2, 5, -3, -2, 3, -2, -12,
1362 -2, 2, 2, 2, -5, 3, 5, 13, -3, 7, -3, -3, -7, 3, -13, 3}
1368 {0, 1, 1, 1, 2, 2, 1, 3, 3, 1, 1, 1, 4, 4, 1, 5,
1369 2, 1, 5, 2, 1, 1, 6, 6, 1, 1, 1, 1, 1, 7, 3, 1,
1370 2, 3, 0, 1, 2, 7, 1, 1, 1, 8, 1, 1, 8, 1, 1, 1,
1371 9, 1, 9, 1, 2, 1, 1, 2, 1, 1, 10, 4, 1, 10, 1, 4,
1372 1, 1, 1, 1, 1, 3, 1, 1, 1, 3, 2, 1, 5, 1, 1, 1,
1373 2, 5, 1, 11, 1, 11, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1374 2, 1, 6, 1, 6, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 12,
1375 3, 1, 12, 1, 1, 1, 2, 1, 1, 3, 1, 1, 1, 1, 1, 1,
1376 4, 1, 1, 1, 2, 1, 1, 4, 1, 1, 1, 1, 1, 1, 2, 1,
1377 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 2, 1, 1, 5,
1378 1, 1, 1, 1, 1, 7, 1, 7, 1, 1, 2, 3, 1, 1, 1, 1,
1379 5, 1, 1, 1, 1, 1, 1, 2, 13, 1, 1, 1, 1, 1, 1, 1,
1380 1, 1, 1, 1, 1, 1, 1, 1, 13, 2, 1, 1, 4, 1, 1, 1,
1381 3, 1, 6, 1, 1, 1, 14, 1, 1, 1, 1, 1, 14, 6, 1, 1,
1382 1, 1, 15, 2, 4, 1, 2, 3, 15, 1, 1, 1, 8, 1, 1, 8,
1383 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1},
1386 { 0, 1, -1, 2, 1, -1, -2, 1, -1, 3, -3, 4, 1, -1, -4, 1,
1387 2, 5, -1, -2, -5, 6, 1, -1, -6, 7, -7, 8, -8, 1, 2, 9,
1388 3, -2, 0, -9, -3, -1, 10, -10, 11, 1, -11, 12, -1, -12, 13, -13,
1389 1, 14, -1, -14, 4, 15, -15, -4, 16, -16, 1, 2, 17, -1, -17, -2,
1390 18, -18, 19, -19, 20, 3, -20, 21, -21, -3, 5, 22, 2, -22, -23, 23,
1391 -5, -2, 24, 1, -24, -1, 25, -25, 26, -26, -27, 27, 28, 29, -28, -29,
1392 6, 30, 2, -31, -2, -30, 31, -6, -32, 32, 33, -33, 34, -35, -34, 1,
1393 4, -36, -1, 35, 37, 36, 7, -37, 38, -4, -38, 39, 41, 40, -40, -39,
1394 3, 42, -43, -41, -7, -42, 43, -3, 44, -44, 45, -45, 46, 47, 8, -47,
1395 -48, -46, 50, -50, 48, 49, 51, -49, 52, -52, 5, -51, -8, -53, 53, 3,
1396 -56, 56, 55, 54, -54, 2, 60, -2, -55, 58, 9, -5, 59, 57, -57, -63,
1397 -3, -58, -60, -61, 61, -59, -62, -9, 1, 64, 62, 69, -64, 63, 65, -67,
1398 -68, 66, -65, 68, -66, -69, 67, -70, -1, 10, 71, -71, 4, 73, 72, 70,
1399 6, -76, -3, 74, -78, -74, 1, 78, 80, -72, -75, 76, -1, 3, -73, 79,
1400 75, 77, 1, 11, -4, -79, -10, -6, -1, -77, -83, -80, 2, 81, -84, -2,
1401 83, -81, 82, -82, 84, -87, -86, 85, -11, -85, 86, -89, 87, -88, 88, 89}
1407 {1, 1, 0, 2, 1, 2, 1, 3, 3, 1, 1, 4, 4, 2, 2, 1,
1408 1, 5, 5, 6, 1, 6, 1, 7, 7, 3, 3, 2, 8, 2, 8, 1,
1409 1, 0, 9, 9, 1, 1, 10, 4, 10, 4, 11, 11, 2, 1, 2, 1,
1410 12, 12, 3, 3, 1, 1, 13, 5, 5, 13, 14, 1, 1, 14, 2, 2,
1411 6, 6, 15, 1, 1, 15, 16, 4, 7, 16, 4, 7, 1, 1, 3, 3,
1412 8, 8, 2, 2, 1, 1, 17, 17, 1, 1, 18, 18, 5, 5, 2, 2,
1413 1, 1, 9, 19, 9, 19, 20, 3, 3, 20, 1, 10, 21, 1, 10, 4,
1414 4, 21, 22, 6, 6, 22, 1, 1, 23, 24, 2, 2, 23, 24, 11, 1,
1415 1, 11, 7, 25, 7, 1, 1, 25, 8, 8, 3, 26, 3, 1, 12, 2,
1416 2, 26, 1, 12, 5, 5, 27, 4, 1, 4, 1, 27, 28, 1, 28, 13,
1417 1, 13, 2, 29, 2, 1, 32, 6, 1, 30, 14, 29, 14, 6, 3, 31,
1418 3, 1, 30, 1, 32, 31, 33, 9, 33, 1, 1, 7, 9, 7, 2, 2,
1419 1, 1, 4, 36, 34, 4, 5, 10, 10, 5, 34, 1, 1, 35, 8, 8,
1420 36, 3, 35, 1, 15, 3, 2, 1, 16, 15, 16, 2, 37, 1, 37, 1,
1421 1, 1, 6, 6, 38, 1, 38, 11, 1, 39, 39, 40, 11, 2, 41, 4,
1422 40, 1, 2, 4, 1, 1, 1, 41, 3, 1, 3, 1, 5, 7, 5, 7},
1425 { 1, -1, 0, 1, 2, -1, -2, 1, -1, 3, -3, 1, -1, 2, -2, 4,
1426 -4, 1, -1, 1, 5, -1, -5, 1, -1, 2, -2, 3, 1, -3, -1, 6,
1427 -6, 0, 1, -1, 7, -7, 1, 2, -1, -2, 1, -1, 4, 8, -4, -8,
1428 1, -1, 3, -3, 9, -9, 1, 2, -2, -1, 1, 10, -10, -1, 5, -5,
1429 2, -2, 1, 11, -11, -1, 1, 3, 2, -1, -3, -2, 12, -12, 4, -4,
1430 2, -2, -6, 6, 13, -13, 1, -1, 14, -14, 1, -1, 3, -3, 7, -7,
1431 15, -15, 2, 1, -2, -1, 1, 5, -5, -1, -16, 2, 1, 16, -2, 4,
1432 -4, -1, 1, 3, -3, -1, 17, -17, 1, 1, -8, 8, -1, -1, 2, 18,
1433 -18, -2, 3, 1, -3, 19, -19, -1, 3, -3, 6, 1, -6, 20, 2, 9,
1434 -9, -1, -20, -2, 4, -4, 1, -5, 21, 5, -21, -1, 1, -22, -1, 2,
1435 22, -2, 10, 1, -10, 23, 1, 4, -23, 1, 2, -1, -2, -4, -7, 1,
1436 7, -24, -1, 24, -1, -1, 1, 3, -1, -25, 25, 4, -3, -4, 11, -11,
1437 26, -26, 6, 1, 1, -6, -5, -3, 3, 5, -1, -27, 27, 1, 4, -4,
1438 -1, -8, -1, 28, 2, 8, -12, -28, -2, -2, 2, 12, -1, 29, 1, -29,
1439 30, -30, 5, -5, 1, -31, -1, 3, 31, -1, 1, 1, -3, -13, 1, -7,
1440 -1, -32, 13, 7, 32, 33, -33, -1, -9, -34, 9, 34, -6, 5, 6, -5}
1446 {1, 1, 0, 1, 1, 2, 2, 1, 1, 3, 3, 1, 1, 0, 2, 2,
1447 4, 1, 4, 1, 1, 1, 5, 5, 1, 1, 6, 6, 2, 2, 1, 1,
1448 3, 3, 7, 7, 1, 1, 8, 8, 1, 1, 2, 2, 1, 9, 1, 9,
1449 4, 4, 10, 1, 1, 10, 1, 1, 11, 11, 3, 3, 1, 2, 1, 2,
1450 1, 1, 12, 12, 5, 5, 1, 1, 13, 1, 1, 13, 2, 2, 1, 1,
1451 6, 6, 1, 1, 4, 14, 4, 14, 3, 1, 3, 1, 1, 1, 15, 7,
1452 15, 2, 2, 7, 1, 1, 1, 8, 1, 8, 16, 16, 1, 1, 1, 1,
1453 2, 1, 1, 2, 1, 1, 3, 5, 5, 3, 4, 1, 1, 4, 1, 1,
1454 17, 17, 9, 1, 1, 9, 2, 2, 1, 1, 10, 10, 1, 6, 1, 1,
1455 6, 18, 1, 1, 18, 1, 1, 1, 2, 2, 3, 1, 3, 1, 1, 1,
1456 4, 1, 19, 1, 19, 7, 1, 1, 20, 1, 4, 20, 1, 7, 11, 2,
1457 1, 11, 21, 2, 8, 5, 1, 8, 1, 5, 21, 1, 1, 1, 22, 1,
1458 1, 22, 1, 1, 3, 3, 1, 23, 2, 12, 24, 1, 1, 2, 1, 1,
1459 12, 23, 1, 1, 24, 1, 1, 1, 4, 1, 1, 1, 2, 1, 6, 6,
1460 4, 2, 1, 1, 1, 1, 1, 1, 1, 14, 13, 3, 1, 25, 9, 25,
1461 14, 1, 9, 3, 13, 1, 1, 1, 1, 1, 10, 1, 1, 2, 10, 2},
1464 {-20, -1, 0, 2, -2, 1, -1, 3, -3, 1, -1, 4, -4, 0, 2, -2,
1465 1, 5, -1, -5, 6, -6, 1, -1, 7, -7, 1, -1, 3, -3, 8, -8,
1466 2, -2, 1, -1, 9, -9, 1, -1, 10, -10, 4, -4, 11, 1, -11, -1,
1467 2, -2, 1, 12, -12, -1, 13, -13, 1, -1, 3, -3, 14, 5, -14, -5,
1468 -15, 15, -1, 1, 2, -2, 16, -16, 1, 17, -17, -1, 6, -6, 18, -18,
1469 2, -2, -19, 19, -3, 1, 3, -1, 4, 20, -4, 1, -21, 21, 1, 2,
1470 -1, -7, 7, -2, 22, -22, 23, 2, -23, -2, 1, -1, -24, 24, -25, 25,
1471 -8, -26, 26, 8, -27, 27, 5, 3, -3, -5, -4, 28, -28, 4, 29, -29,
1472 1, -1, -2, -30, 30, 2, 9, -9, -31, 31, 2, -2, -32, 3, 32, -33,
1473 -3, 1, 33, -34, -1, 34, -35, 35, -10, 10, -6, 36, 6, -36, 37, -37,
1474 -5, 38, 1, -38, -1, 3, 39, -39, -1, 40, 5, 1, -40, -3, 2, -11,
1475 -41, -2, 1, 11, -3, -4, 41, 3, 42, 4, -1, -43, -42, 43, 1, -44,
1476 45, -1, 44, -45, -7, 7, -46, 1, -12, 2, 1, -47, 46, 12, 47, 48,
1477 -2, -1, -48, 49, -1, -50, -49, 50, -6, -51, 51, 52, -13, 53, -4, 4,
1478 6, 13, -53, -52, -54, 55, 54, -55, -56, -2, 2, -8, 56, 1, -3, -1,
1479 2, 58, 3, 8, -2, 57, -58, -60, -59, -57, -3, 60, 59, -14, 3, 14}
1485 {1, 1, 0, 2, 2, 1, 1, 3, 3, 4, 4, 5, 5, 1, 1, 6,
1486 6, 2, 2, 7, 7, 8, 8, 1, 1, 3, 3, 9, 9, 10, 10, 1,
1487 1, 2, 2, 4, 4, 11, 0, 11, 12, 12, 13, 13, 1, 1, 5, 5,
1488 14, 14, 15, 16, 15, 16, 3, 3, 1, 6, 1, 6, 2, 2, 7, 7,
1489 8, 8, 17, 17, 1, 1, 4, 4, 18, 18, 2, 2, 1, 19, 1, 20,
1490 19, 20, 21, 21, 3, 3, 22, 22, 5, 5, 24, 1, 1, 23, 9, 23,
1491 24, 9, 2, 2, 10, 1, 1, 10, 6, 6, 25, 4, 4, 25, 7, 7,
1492 26, 8, 1, 8, 3, 1, 26, 3, 11, 11, 27, 27, 2, 28, 1, 2,
1493 28, 1, 12, 12, 5, 5, 29, 13, 13, 29, 32, 1, 1, 33, 31, 30,
1494 32, 4, 30, 33, 4, 31, 3, 14, 1, 1, 3, 34, 34, 2, 2, 14,
1495 6, 6, 35, 36, 35, 36, 1, 15, 1, 16, 16, 15, 7, 9, 7, 9,
1496 37, 8, 8, 37, 1, 1, 39, 2, 38, 39, 2, 40, 5, 38, 40, 5,
1497 3, 3, 4, 4, 10, 10, 1, 1, 1, 1, 41, 2, 41, 2, 6, 6,
1498 1, 1, 11, 42, 11, 43, 3, 42, 3, 17, 4, 43, 1, 17, 7, 1,
1499 8, 44, 4, 7, 44, 5, 8, 2, 5, 1, 2, 48, 45, 1, 12, 45,
1500 12, 48, 13, 13, 1, 9, 9, 46, 1, 46, 47, 47, 49, 18, 18, 49},
1503 { 1, -1, 0, 1, -1, 2, -2, 1, -1, 1, -1, 1, -1, 3, -3, 1,
1504 -1, -2, 2, 1, -1, 1, -1, 4, -4, -2, 2, 1, -1, 1, -1, 5,
1505 -5, -3, 3, 2, -2, 1, 0, -1, 1, -1, 1, -1, 6, -6, 2, -2,
1506 1, -1, 1, 1, -1, -1, -3, 3, 7, 2, -7, -2, -4, 4, 2, -2,
1507 2, -2, 1, -1, 8, -8, 3, -3, 1, -1, -5, 5, 9, 1, -9, 1,
1508 -1, -1, 1, -1, -4, 4, 1, -1, 3, -3, 1, -10, 10, 1, 2, -1,
1509 -1, -2, 6, -6, 2, 11, -11, -2, 3, -3, 1, -4, 4, -1, 3, -3,
1510 1, 3, 12, -3, -5, -12, -1, 5, 2, -2, 1, -1, -7, 1, 13, 7,
1511 -1, -13, 2, -2, 4, -4, 1, 2, -2, -1, 1, 14, -14, 1, 1, 1,
1512 -1, -5, -1, -1, 5, -1, -6, 2, -15, 15, 6, 1, -1, -8, 8, -2,
1513 -4, 4, 1, 1, -1, -1, 16, 2, -16, -2, 2, -2, 4, 3, -4, -3,
1514 -1, -4, 4, 1, -17, 17, -1, -9, 1, 1, 9, 1, -5, -1, -1, 5,
1515 -7, 7, 6, -6, 3, -3, 18, -18, 19, -19, 1, -10, -1, 10, -5, 5,
1516 20, -20, -3, 1, 3, 1, 8, -1, -8, 2, 7, -1, -21, -2, 5, 21,
1517 5, -1, -7, -5, 1, -6, -5, -11, 6, 22, 11, 1, 1, -22, -3, -1,
1518 3, -1, 3, -3, -23, 4, -4, 1, 23, -1, 1, -1, 1, -2, 2, -1}
1524 {1, 1, 1, 1, 0, 2, 2, 1, 1, 3, 3, 0, 1, 1, 2, 2,
1525 4, 4, 1, 1, 5, 5, 1, 1, 2, 2, 3, 3, 6, 6, 1, 1,
1526 7, 7, 8, 1, 8, 2, 2, 1, 4, 4, 1, 3, 1, 3, 9, 9,
1527 2, 2, 1, 5, 1, 5, 10, 10, 1, 1, 11, 11, 3, 6, 3, 4,
1528 4, 6, 2, 2, 1, 12, 1, 12, 7, 13, 7, 13, 1, 1, 8, 8,
1529 2, 2, 14, 14, 16, 15, 16, 5, 5, 1, 3, 15, 1, 3, 4, 4,
1530 1, 1, 17, 17, 2, 2, 6, 6, 1, 18, 1, 18, 22, 21, 22, 21,
1531 25, 24, 25, 19, 9, 20, 9, 23, 19, 24, 20, 3, 23, 7, 3, 1,
1532 1, 7, 28, 26, 29, 5, 28, 26, 5, 8, 29, 4, 8, 27, 2, 2,
1533 4, 27, 1, 1, 10, 36, 10, 33, 33, 36, 30, 1, 32, 32, 1, 30,
1534 6, 31, 31, 35, 3, 6, 11, 11, 3, 2, 35, 2, 34, 1, 34, 1,
1535 37, 37, 12, 7, 12, 5, 41, 5, 4, 7, 1, 8, 13, 4, 1, 41,
1536 13, 38, 8, 38, 9, 1, 40, 40, 9, 1, 39, 2, 2, 49, 39, 42,
1537 3, 3, 14, 16, 49, 14, 16, 42, 43, 43, 6, 6, 15, 1, 1, 15,
1538 44, 44, 1, 1, 50, 48, 4, 5, 4, 7, 5, 2, 10, 10, 48, 7,
1539 50, 45, 2, 1, 45, 8, 8, 1, 46, 46, 3, 47, 47, 3, 1, 1},
1542 { 1, -1, 2, -2, 0, 1, -1, 3, -3, 1, -1, 0, 4, -4, 2, -2,
1543 1, -1, 5, -5, 1, -1, 6, -6, 3, -3, 2, -2, 1, -1, 7, -7,
1544 1, -1, 1, 8, -1, 4, -4, -8, 2, -2, 9, 3, -9, -3, 1, -1,
1545 5, -5, 10, 2, -10, -2, 1, -1, 11, -11, 1, -1, -4, 2, 4, 3,
1546 -3, -2, 6, -6, 12, 1, -12, -1, 2, 1, -2, -1, 13, -13, 2, -2,
1547 7, -7, 1, -1, 1, 1, -1, 3, -3, 14, 5, -1, -14, -5, 4, -4,
1548 15, -15, 1, -1, 8, -8, -3, 3, 16, 1, -16, -1, 1, 1, -1, -1,
1549 1, 1, -1, 1, 2, 1, -2, 1, -1, -1, -1, 6, -1, 3, -6, 17,
1550 -17, -3, 1, 1, 1, 4, -1, -1, -4, 3, -1, 5, -3, -1, -9, 9,
1551 -5, 1, 18, -18, 2, 1, -2, 1, -1, -1, 1, 19, -1, 1, -19, -1,
1552 4, 1, -1, 1, 7, -4, -2, 2, -7, 10, -1, -10, 1, 20, -1, -20,
1553 1, -1, 2, 4, -2, 5, 1, -5, 6, -4, 21, 4, 2, -6, -21, -1,
1554 -2, 1, -4, -1, -3, 22, -1, 1, 3, -22, -1, 11, -11, 1, 1, 1,
1555 8, -8, 2, 2, -1, -2, -2, -1, 1, -1, -5, 5, 2, 23, -23, -2,
1556 1, -1, 24, -24, -1, -1, 7, 6, -7, 5, -6, 12, -3, 3, 1, -5,
1557 1, 1, -12, 25, -1, -5, 5, -25, -1, 1, 9, 1, -1, -9, 26, -26}