2 * common functions for Indeo Video Interactive codecs (Indeo4 and Indeo5)
4 * Copyright (c) 2009 Maxim Poliakovski
6 * This file is part of FFmpeg.
8 * FFmpeg is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU Lesser General Public
10 * License as published by the Free Software Foundation; either
11 * version 2.1 of the License, or (at your option) any later version.
13 * FFmpeg is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * Lesser General Public License for more details.
18 * You should have received a copy of the GNU Lesser General Public
19 * License along with FFmpeg; if not, write to the Free Software
20 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
25 * This file contains functions and data shared by both Indeo4 and
29 #define BITSTREAM_READER_LE
30 #include "libavutil/attributes.h"
35 #include "ivi_common.h"
38 extern const IVIHuffDesc ff_ivi_mb_huff_desc[8]; ///< static macroblock huffman tables
39 extern const IVIHuffDesc ff_ivi_blk_huff_desc[8]; ///< static block huffman tables
41 static VLC ivi_mb_vlc_tabs [8]; ///< static macroblock Huffman tables
42 static VLC ivi_blk_vlc_tabs[8]; ///< static block Huffman tables
44 typedef void (*ivi_mc_func) (int16_t *buf, const int16_t *ref_buf,
45 uint32_t pitch, int mc_type);
47 static int ivi_mc(IVIBandDesc *band, ivi_mc_func mc,
48 int offs, int mv_x, int mv_y, int mc_type)
50 int ref_offs = offs + mv_y * band->pitch + mv_x;
51 int buf_size = band->pitch * band->aheight;
52 int min_size = band->pitch * (band->blk_size - 1) + band->blk_size;
53 int ref_size = (mc_type > 1) * band->pitch + (mc_type & 1);
55 av_assert0(offs >= 0 && ref_offs >= 0 && band->ref_buf);
56 av_assert0(buf_size - min_size >= offs);
57 av_assert0(buf_size - min_size - ref_size >= ref_offs);
59 mc(band->buf + offs, band->ref_buf + ref_offs, band->pitch, mc_type);
65 * Reverse "nbits" bits of the value "val" and return the result
66 * in the least significant bits.
68 static uint16_t inv_bits(uint16_t val, int nbits)
73 res = ff_reverse[val] >> (8 - nbits);
75 res = ((ff_reverse[val & 0xFF] << 8) +
76 (ff_reverse[val >> 8])) >> (16 - nbits);
82 * Generate a huffman codebook from the given descriptor
83 * and convert it into the FFmpeg VLC table.
85 * @param[in] cb pointer to codebook descriptor
86 * @param[out] vlc where to place the generated VLC table
87 * @param[in] flag flag: 1 - for static or 0 for dynamic tables
88 * @return result code: 0 - OK, -1 = error (invalid codebook descriptor)
90 static int ivi_create_huff_from_desc(const IVIHuffDesc *cb, VLC *vlc, int flag)
92 int pos, i, j, codes_per_row, prefix, not_last_row;
93 uint16_t codewords[256]; /* FIXME: move this temporal storage out? */
96 pos = 0; /* current position = 0 */
98 for (i = 0; i < cb->num_rows; i++) {
99 codes_per_row = 1 << cb->xbits[i];
100 not_last_row = (i != cb->num_rows - 1);
101 prefix = ((1 << i) - 1) << (cb->xbits[i] + not_last_row);
103 for (j = 0; j < codes_per_row; j++) {
104 if (pos >= 256) /* Some Indeo5 codebooks can have more than 256 */
105 break; /* elements, but only 256 codes are allowed! */
107 bits[pos] = i + cb->xbits[i] + not_last_row;
108 if (bits[pos] > IVI_VLC_BITS)
109 return AVERROR_INVALIDDATA; /* invalid descriptor */
111 codewords[pos] = inv_bits((prefix | j), bits[pos]);
119 /* number of codewords = pos */
120 return init_vlc(vlc, IVI_VLC_BITS, pos, bits, 1, 1, codewords, 2, 2,
121 (flag ? INIT_VLC_USE_NEW_STATIC : 0) | INIT_VLC_LE);
124 av_cold void ff_ivi_init_static_vlc(void)
127 static VLC_TYPE table_data[8192 * 16][2];
128 static int initialized_vlcs = 0;
130 if (initialized_vlcs)
132 for (i = 0; i < 8; i++) {
133 ivi_mb_vlc_tabs[i].table = table_data + i * 2 * 8192;
134 ivi_mb_vlc_tabs[i].table_allocated = 8192;
135 ivi_create_huff_from_desc(&ff_ivi_mb_huff_desc[i],
136 &ivi_mb_vlc_tabs[i], 1);
137 ivi_blk_vlc_tabs[i].table = table_data + (i * 2 + 1) * 8192;
138 ivi_blk_vlc_tabs[i].table_allocated = 8192;
139 ivi_create_huff_from_desc(&ff_ivi_blk_huff_desc[i],
140 &ivi_blk_vlc_tabs[i], 1);
142 initialized_vlcs = 1;
146 * Copy huffman codebook descriptors.
148 * @param[out] dst ptr to the destination descriptor
149 * @param[in] src ptr to the source descriptor
151 static void ivi_huff_desc_copy(IVIHuffDesc *dst, const IVIHuffDesc *src)
153 dst->num_rows = src->num_rows;
154 memcpy(dst->xbits, src->xbits, src->num_rows);
158 * Compare two huffman codebook descriptors.
160 * @param[in] desc1 ptr to the 1st descriptor to compare
161 * @param[in] desc2 ptr to the 2nd descriptor to compare
162 * @return comparison result: 0 - equal, 1 - not equal
164 static int ivi_huff_desc_cmp(const IVIHuffDesc *desc1,
165 const IVIHuffDesc *desc2)
167 return desc1->num_rows != desc2->num_rows ||
168 memcmp(desc1->xbits, desc2->xbits, desc1->num_rows);
171 int ff_ivi_dec_huff_desc(GetBitContext *gb, int desc_coded, int which_tab,
172 IVIHuffTab *huff_tab, AVCodecContext *avctx)
175 IVIHuffDesc new_huff;
178 /* select default table */
179 huff_tab->tab = (which_tab) ? &ivi_blk_vlc_tabs[7]
180 : &ivi_mb_vlc_tabs [7];
184 huff_tab->tab_sel = get_bits(gb, 3);
185 if (huff_tab->tab_sel == 7) {
186 /* custom huffman table (explicitly encoded) */
187 new_huff.num_rows = get_bits(gb, 4);
188 if (!new_huff.num_rows) {
189 av_log(avctx, AV_LOG_ERROR, "Empty custom Huffman table!\n");
190 return AVERROR_INVALIDDATA;
193 for (i = 0; i < new_huff.num_rows; i++)
194 new_huff.xbits[i] = get_bits(gb, 4);
196 /* Have we got the same custom table? Rebuild if not. */
197 if (ivi_huff_desc_cmp(&new_huff, &huff_tab->cust_desc) || !huff_tab->cust_tab.table) {
198 ivi_huff_desc_copy(&huff_tab->cust_desc, &new_huff);
200 if (huff_tab->cust_tab.table)
201 ff_free_vlc(&huff_tab->cust_tab);
202 result = ivi_create_huff_from_desc(&huff_tab->cust_desc,
203 &huff_tab->cust_tab, 0);
205 // reset faulty description
206 huff_tab->cust_desc.num_rows = 0;
207 av_log(avctx, AV_LOG_ERROR,
208 "Error while initializing custom vlc table!\n");
212 huff_tab->tab = &huff_tab->cust_tab;
214 /* select one of predefined tables */
215 huff_tab->tab = (which_tab) ? &ivi_blk_vlc_tabs[huff_tab->tab_sel]
216 : &ivi_mb_vlc_tabs [huff_tab->tab_sel];
223 * Free planes, bands and macroblocks buffers.
225 * @param[in] planes pointer to the array of the plane descriptors
227 static av_cold void ivi_free_buffers(IVIPlaneDesc *planes)
231 for (p = 0; p < 3; p++) {
233 for (b = 0; b < planes[p].num_bands; b++) {
234 av_freep(&planes[p].bands[b].bufs[0]);
235 av_freep(&planes[p].bands[b].bufs[1]);
236 av_freep(&planes[p].bands[b].bufs[2]);
238 if (planes[p].bands[b].blk_vlc.cust_tab.table)
239 ff_free_vlc(&planes[p].bands[b].blk_vlc.cust_tab);
240 for (t = 0; t < planes[p].bands[b].num_tiles; t++)
241 av_freep(&planes[p].bands[b].tiles[t].mbs);
242 av_freep(&planes[p].bands[b].tiles);
244 av_freep(&planes[p].bands);
248 av_cold int ff_ivi_init_planes(IVIPlaneDesc *planes, const IVIPicConfig *cfg)
251 uint32_t b_width, b_height, align_fac, width_aligned,
252 height_aligned, buf_size;
255 ivi_free_buffers(planes);
257 /* fill in the descriptor of the luminance plane */
258 planes[0].width = cfg->pic_width;
259 planes[0].height = cfg->pic_height;
260 planes[0].num_bands = cfg->luma_bands;
262 /* fill in the descriptors of the chrominance planes */
263 planes[1].width = planes[2].width = (cfg->pic_width + 3) >> 2;
264 planes[1].height = planes[2].height = (cfg->pic_height + 3) >> 2;
265 planes[1].num_bands = planes[2].num_bands = cfg->chroma_bands;
267 for (p = 0; p < 3; p++) {
268 planes[p].bands = av_mallocz(planes[p].num_bands * sizeof(IVIBandDesc));
269 if (!planes[p].bands)
270 return AVERROR(ENOMEM);
272 /* select band dimensions: if there is only one band then it
273 * has the full size, if there are several bands each of them
274 * has only half size */
275 b_width = planes[p].num_bands == 1 ? planes[p].width
276 : (planes[p].width + 1) >> 1;
277 b_height = planes[p].num_bands == 1 ? planes[p].height
278 : (planes[p].height + 1) >> 1;
280 /* luma band buffers will be aligned on 16x16 (max macroblock size) */
281 /* chroma band buffers will be aligned on 8x8 (max macroblock size) */
282 align_fac = p ? 8 : 16;
283 width_aligned = FFALIGN(b_width , align_fac);
284 height_aligned = FFALIGN(b_height, align_fac);
285 buf_size = width_aligned * height_aligned * sizeof(int16_t);
287 for (b = 0; b < planes[p].num_bands; b++) {
288 band = &planes[p].bands[b]; /* select appropriate plane/band */
291 band->width = b_width;
292 band->height = b_height;
293 band->pitch = width_aligned;
294 band->aheight = height_aligned;
295 band->bufs[0] = av_mallocz(buf_size);
296 band->bufs[1] = av_mallocz(buf_size);
297 band->bufsize = buf_size/2;
298 if (!band->bufs[0] || !band->bufs[1])
299 return AVERROR(ENOMEM);
301 /* allocate the 3rd band buffer for scalability mode */
302 if (cfg->luma_bands > 1) {
303 band->bufs[2] = av_mallocz(buf_size);
305 return AVERROR(ENOMEM);
307 /* reset custom vlc */
308 planes[p].bands[0].blk_vlc.cust_desc.num_rows = 0;
315 static int ivi_init_tiles(IVIBandDesc *band, IVITile *ref_tile,
316 int p, int b, int t_height, int t_width)
319 IVITile *tile = band->tiles;
321 for (y = 0; y < band->height; y += t_height) {
322 for (x = 0; x < band->width; x += t_width) {
325 tile->mb_size = band->mb_size;
326 tile->width = FFMIN(band->width - x, t_width);
327 tile->height = FFMIN(band->height - y, t_height);
328 tile->is_empty = tile->data_size = 0;
329 /* calculate number of macroblocks */
330 tile->num_MBs = IVI_MBs_PER_TILE(tile->width, tile->height,
333 av_freep(&tile->mbs);
334 tile->mbs = av_malloc(tile->num_MBs * sizeof(IVIMbInfo));
336 return AVERROR(ENOMEM);
340 if (tile->num_MBs <= ref_tile->num_MBs) {
341 tile->ref_mbs = ref_tile->mbs;
343 av_log(NULL, AV_LOG_DEBUG, "Cannot use ref_tile, too few mbs\n");
354 av_cold int ff_ivi_init_tiles(IVIPlaneDesc *planes,
355 int tile_width, int tile_height)
357 int p, b, x_tiles, y_tiles, t_width, t_height, ret;
360 for (p = 0; p < 3; p++) {
361 t_width = !p ? tile_width : (tile_width + 3) >> 2;
362 t_height = !p ? tile_height : (tile_height + 3) >> 2;
364 if (!p && planes[0].num_bands == 4) {
368 if(t_width<=0 || t_height<=0)
369 return AVERROR(EINVAL);
371 for (b = 0; b < planes[p].num_bands; b++) {
372 band = &planes[p].bands[b];
373 x_tiles = IVI_NUM_TILES(band->width, t_width);
374 y_tiles = IVI_NUM_TILES(band->height, t_height);
375 band->num_tiles = x_tiles * y_tiles;
377 av_freep(&band->tiles);
378 band->tiles = av_mallocz(band->num_tiles * sizeof(IVITile));
380 return AVERROR(ENOMEM);
382 /* use the first luma band as reference for motion vectors
384 ret = ivi_init_tiles(band, planes[0].bands[0].tiles,
385 p, b, t_height, t_width);
395 * Decode size of the tile data.
396 * The size is stored as a variable-length field having the following format:
397 * if (tile_data_size < 255) than this field is only one byte long
398 * if (tile_data_size >= 255) than this field four is byte long: 0xFF X1 X2 X3
399 * where X1-X3 is size of the tile data
401 * @param[in,out] gb the GetBit context
402 * @return size of the tile data in bytes
404 static int ivi_dec_tile_data_size(GetBitContext *gb)
410 len = get_bits(gb, 8);
412 len = get_bits_long(gb, 24);
415 /* align the bitstream reader on the byte boundary */
421 static int ivi_dc_transform(IVIBandDesc *band, int *prev_dc, int buf_offs,
424 int buf_size = band->pitch * band->aheight - buf_offs;
425 int min_size = (blk_size - 1) * band->pitch + blk_size;
427 if (min_size > buf_size)
428 return AVERROR_INVALIDDATA;
430 band->dc_transform(prev_dc, band->buf + buf_offs,
431 band->pitch, blk_size);
436 static int ivi_decode_coded_blocks(GetBitContext *gb, IVIBandDesc *band,
437 ivi_mc_func mc, int mv_x, int mv_y,
438 int *prev_dc, int is_intra, int mc_type,
439 uint32_t quant, int offs,
440 AVCodecContext *avctx)
442 const uint16_t *base_tab = is_intra ? band->intra_base : band->inter_base;
443 RVMapDesc *rvmap = band->rv_map;
444 uint8_t col_flags[8];
446 uint32_t sym = 0, lo, hi, q;
448 int blk_size = band->blk_size;
449 int num_coeffs = blk_size * blk_size;
450 int col_mask = blk_size - 1;
452 int min_size = band->pitch * (band->transform_size - 1) +
453 band->transform_size;
454 int buf_size = band->pitch * band->aheight - offs;
456 if (min_size > buf_size)
457 return AVERROR_INVALIDDATA;
460 av_log(avctx, AV_LOG_ERROR, "Scan pattern is not set.\n");
461 return AVERROR_INVALIDDATA;
464 /* zero transform vector */
465 memset(trvec, 0, num_coeffs * sizeof(trvec[0]));
466 /* zero column flags */
467 memset(col_flags, 0, sizeof(col_flags));
468 while (scan_pos <= num_coeffs) {
469 sym = get_vlc2(gb, band->blk_vlc.tab->table,
471 if (sym == rvmap->eob_sym)
472 break; /* End of block */
474 /* Escape - run/val explicitly coded using 3 vlc codes */
475 if (sym == rvmap->esc_sym) {
476 run = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1) + 1;
477 lo = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
478 hi = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
479 /* merge them and convert into signed val */
480 val = IVI_TOSIGNED((hi << 6) | lo);
483 av_log(avctx, AV_LOG_ERROR, "Invalid sym encountered: %d.\n", sym);
484 return AVERROR_INVALIDDATA;
486 run = rvmap->runtab[sym];
487 val = rvmap->valtab[sym];
490 /* de-zigzag and dequantize */
492 if (scan_pos >= num_coeffs || scan_pos < 0)
494 pos = band->scan[scan_pos];
497 av_dlog(avctx, "Val = 0 encountered!\n");
499 q = (base_tab[pos] * quant) >> 9;
501 val = val * q + FFSIGN(val) * (((q ^ 1) - 1) >> 1);
503 /* track columns containing non-zero coeffs */
504 col_flags[pos & col_mask] |= !!val;
507 if (scan_pos < 0 || scan_pos >= num_coeffs && sym != rvmap->eob_sym)
508 return AVERROR_INVALIDDATA; /* corrupt block data */
510 /* undoing DC coeff prediction for intra-blocks */
511 if (is_intra && band->is_2d_trans) {
512 *prev_dc += trvec[0];
514 col_flags[0] |= !!*prev_dc;
517 if(band->transform_size > band->blk_size){
518 av_log(NULL, AV_LOG_ERROR, "Too large transform\n");
519 return AVERROR_INVALIDDATA;
522 /* apply inverse transform */
523 band->inv_transform(trvec, band->buf + offs,
524 band->pitch, col_flags);
526 /* apply motion compensation */
528 return ivi_mc(band, mc, offs, mv_x, mv_y, mc_type);
534 * extract huffman-coded transform coefficients from the bitstream,
535 * dequantize them, apply inverse transform and motion compensation
536 * in order to reconstruct the picture.
538 * @param[in,out] gb the GetBit context
539 * @param[in] band pointer to the band descriptor
540 * @param[in] tile pointer to the tile descriptor
541 * @return result code: 0 - OK, -1 = error (corrupted blocks data)
543 static int ivi_decode_blocks(GetBitContext *gb, IVIBandDesc *band,
544 IVITile *tile, AVCodecContext *avctx)
546 int mbn, blk, num_blocks, blk_size, ret, is_intra, mc_type = 0;
547 int mv_x = 0, mv_y = 0;
549 uint32_t cbp, quant, buf_offs;
551 ivi_mc_func mc_with_delta_func, mc_no_delta_func;
552 const uint8_t *scale_tab;
554 /* init intra prediction for the DC coefficient */
556 blk_size = band->blk_size;
557 /* number of blocks per mb */
558 num_blocks = (band->mb_size != blk_size) ? 4 : 1;
560 mc_with_delta_func = ff_ivi_mc_8x8_delta;
561 mc_no_delta_func = ff_ivi_mc_8x8_no_delta;
563 mc_with_delta_func = ff_ivi_mc_4x4_delta;
564 mc_no_delta_func = ff_ivi_mc_4x4_no_delta;
567 for (mbn = 0, mb = tile->mbs; mbn < tile->num_MBs; mb++, mbn++) {
568 is_intra = !mb->type;
570 buf_offs = mb->buf_offs;
572 quant = band->glob_quant + mb->q_delta;
573 if (avctx->codec_id == AV_CODEC_ID_INDEO4)
574 quant = av_clip(quant, 0, 31);
576 quant = av_clip(quant, 0, 23);
578 scale_tab = is_intra ? band->intra_scale : band->inter_scale;
580 quant = scale_tab[quant];
585 if (band->is_halfpel) {
586 mc_type = ((mv_y & 1) << 1) | (mv_x & 1);
588 mv_y >>= 1; /* convert halfpel vectors into fullpel ones */
591 int dmv_x, dmv_y, cx, cy;
593 dmv_x = mb->mv_x >> band->is_halfpel;
594 dmv_y = mb->mv_y >> band->is_halfpel;
595 cx = mb->mv_x & band->is_halfpel;
596 cy = mb->mv_y & band->is_halfpel;
598 if (mb->xpos + dmv_x < 0 ||
599 mb->xpos + dmv_x + band->mb_size + cx > band->pitch ||
600 mb->ypos + dmv_y < 0 ||
601 mb->ypos + dmv_y + band->mb_size + cy > band->aheight) {
602 return AVERROR_INVALIDDATA;
607 for (blk = 0; blk < num_blocks; blk++) {
608 /* adjust block position in the buffer according to its number */
610 buf_offs += blk_size;
611 } else if (blk == 2) {
612 buf_offs -= blk_size;
613 buf_offs += blk_size * band->pitch;
616 if (cbp & 1) { /* block coded ? */
617 ret = ivi_decode_coded_blocks(gb, band, mc_with_delta_func,
618 mv_x, mv_y, &prev_dc, is_intra,
619 mc_type, quant, buf_offs, avctx);
623 /* block not coded */
624 /* for intra blocks apply the dc slant transform */
625 /* for inter - perform the motion compensation without delta */
627 ret = ivi_dc_transform(band, &prev_dc, buf_offs, blk_size);
631 ret = ivi_mc(band, mc_no_delta_func, buf_offs,
632 mv_x, mv_y, mc_type);
648 * Handle empty tiles by performing data copying and motion
649 * compensation respectively.
651 * @param[in] avctx ptr to the AVCodecContext
652 * @param[in] band pointer to the band descriptor
653 * @param[in] tile pointer to the tile descriptor
654 * @param[in] mv_scale scaling factor for motion vectors
656 static int ivi_process_empty_tile(AVCodecContext *avctx, IVIBandDesc *band,
657 IVITile *tile, int32_t mv_scale)
659 int x, y, need_mc, mbn, blk, num_blocks, mv_x, mv_y, mc_type;
660 int offs, mb_offset, row_offset, ret;
661 IVIMbInfo *mb, *ref_mb;
664 ivi_mc_func mc_no_delta_func;
666 if (tile->num_MBs != IVI_MBs_PER_TILE(tile->width, tile->height, band->mb_size)) {
667 av_log(avctx, AV_LOG_ERROR, "Allocated tile size %d mismatches "
668 "parameters %d in ivi_process_empty_tile()\n",
669 tile->num_MBs, IVI_MBs_PER_TILE(tile->width, tile->height, band->mb_size));
670 return AVERROR_INVALIDDATA;
673 offs = tile->ypos * band->pitch + tile->xpos;
675 ref_mb = tile->ref_mbs;
676 row_offset = band->mb_size * band->pitch;
677 need_mc = 0; /* reset the mc tracking flag */
679 for (y = tile->ypos; y < (tile->ypos + tile->height); y += band->mb_size) {
682 for (x = tile->xpos; x < (tile->xpos + tile->width); x += band->mb_size) {
685 mb->buf_offs = mb_offset;
687 mb->type = 1; /* set the macroblocks type = INTER */
688 mb->cbp = 0; /* all blocks are empty */
690 if (!band->qdelta_present && !band->plane && !band->band_num) {
691 mb->q_delta = band->glob_quant;
696 if (band->inherit_qdelta && ref_mb)
697 mb->q_delta = ref_mb->q_delta;
699 if (band->inherit_mv && ref_mb) {
700 /* motion vector inheritance */
702 mb->mv_x = ivi_scale_mv(ref_mb->mv_x, mv_scale);
703 mb->mv_y = ivi_scale_mv(ref_mb->mv_y, mv_scale);
705 mb->mv_x = ref_mb->mv_x;
706 mb->mv_y = ref_mb->mv_y;
708 need_mc |= mb->mv_x || mb->mv_y; /* tracking non-zero motion vectors */
710 int dmv_x, dmv_y, cx, cy;
712 dmv_x = mb->mv_x >> band->is_halfpel;
713 dmv_y = mb->mv_y >> band->is_halfpel;
714 cx = mb->mv_x & band->is_halfpel;
715 cy = mb->mv_y & band->is_halfpel;
717 if ( mb->xpos + dmv_x < 0
718 || mb->xpos + dmv_x + band->mb_size + cx > band->pitch
719 || mb->ypos + dmv_y < 0
720 || mb->ypos + dmv_y + band->mb_size + cy > band->aheight) {
721 av_log(avctx, AV_LOG_ERROR, "MV out of bounds\n");
722 return AVERROR_INVALIDDATA;
730 mb_offset += band->mb_size;
735 if (band->inherit_mv && need_mc) { /* apply motion compensation if there is at least one non-zero motion vector */
736 num_blocks = (band->mb_size != band->blk_size) ? 4 : 1; /* number of blocks per mb */
737 mc_no_delta_func = (band->blk_size == 8) ? ff_ivi_mc_8x8_no_delta
738 : ff_ivi_mc_4x4_no_delta;
740 for (mbn = 0, mb = tile->mbs; mbn < tile->num_MBs; mb++, mbn++) {
743 if (!band->is_halfpel) {
744 mc_type = 0; /* we have only fullpel vectors */
746 mc_type = ((mv_y & 1) << 1) | (mv_x & 1);
748 mv_y >>= 1; /* convert halfpel vectors into fullpel ones */
751 for (blk = 0; blk < num_blocks; blk++) {
752 /* adjust block position in the buffer according with its number */
753 offs = mb->buf_offs + band->blk_size * ((blk & 1) + !!(blk & 2) * band->pitch);
754 ret = ivi_mc(band, mc_no_delta_func, offs,
755 mv_x, mv_y, mc_type);
761 /* copy data from the reference tile into the current one */
762 src = band->ref_buf + tile->ypos * band->pitch + tile->xpos;
763 dst = band->buf + tile->ypos * band->pitch + tile->xpos;
764 for (y = 0; y < tile->height; y++) {
765 memcpy(dst, src, tile->width*sizeof(band->buf[0]));
776 static uint16_t ivi_calc_band_checksum(IVIBandDesc *band)
779 int16_t *src, checksum;
784 for (y = 0; y < band->height; src += band->pitch, y++)
785 for (x = 0; x < band->width; x++)
793 * Convert and output the current plane.
794 * This conversion is done by adding back the bias value of 128
795 * (subtracted in the encoder) and clipping the result.
797 * @param[in] plane pointer to the descriptor of the plane being processed
798 * @param[out] dst pointer to the buffer receiving converted pixels
799 * @param[in] dst_pitch pitch for moving to the next y line
801 static void ivi_output_plane(IVIPlaneDesc *plane, uint8_t *dst, int dst_pitch)
804 const int16_t *src = plane->bands[0].buf;
805 uint32_t pitch = plane->bands[0].pitch;
810 for (y = 0; y < plane->height; y++) {
811 for (x = 0; x < plane->width; x++)
812 dst[x] = av_clip_uint8(src[x] + 128);
819 * Decode an Indeo 4 or 5 band.
821 * @param[in,out] ctx ptr to the decoder context
822 * @param[in,out] band ptr to the band descriptor
823 * @param[in] avctx ptr to the AVCodecContext
824 * @return result code: 0 = OK, -1 = error
826 static int decode_band(IVI45DecContext *ctx,
827 IVIBandDesc *band, AVCodecContext *avctx)
829 int result, i, t, idx1, idx2, pos;
832 band->buf = band->bufs[ctx->dst_buf];
834 av_log(avctx, AV_LOG_ERROR, "Band buffer points to no data!\n");
835 return AVERROR_INVALIDDATA;
837 band->ref_buf = band->bufs[ctx->ref_buf];
838 band->data_ptr = ctx->frame_data + (get_bits_count(&ctx->gb) >> 3);
840 result = ctx->decode_band_hdr(ctx, band, avctx);
842 av_log(avctx, AV_LOG_ERROR, "Error while decoding band header: %d\n",
847 if (band->is_empty) {
848 av_log(avctx, AV_LOG_ERROR, "Empty band encountered!\n");
849 return AVERROR_INVALIDDATA;
852 band->rv_map = &ctx->rvmap_tabs[band->rvmap_sel];
854 /* apply corrections to the selected rvmap table if present */
855 for (i = 0; i < band->num_corr; i++) {
856 idx1 = band->corr[i * 2];
857 idx2 = band->corr[i * 2 + 1];
858 FFSWAP(uint8_t, band->rv_map->runtab[idx1], band->rv_map->runtab[idx2]);
859 FFSWAP(int16_t, band->rv_map->valtab[idx1], band->rv_map->valtab[idx2]);
860 if (idx1 == band->rv_map->eob_sym || idx2 == band->rv_map->eob_sym)
861 band->rv_map->eob_sym ^= idx1 ^ idx2;
862 if (idx1 == band->rv_map->esc_sym || idx2 == band->rv_map->esc_sym)
863 band->rv_map->esc_sym ^= idx1 ^ idx2;
866 pos = get_bits_count(&ctx->gb);
868 for (t = 0; t < band->num_tiles; t++) {
869 tile = &band->tiles[t];
871 if (tile->mb_size != band->mb_size) {
872 av_log(avctx, AV_LOG_ERROR, "MB sizes mismatch: %d vs. %d\n",
873 band->mb_size, tile->mb_size);
874 return AVERROR_INVALIDDATA;
876 tile->is_empty = get_bits1(&ctx->gb);
877 if (tile->is_empty) {
878 result = ivi_process_empty_tile(avctx, band, tile,
879 (ctx->planes[0].bands[0].mb_size >> 3) - (band->mb_size >> 3));
882 av_dlog(avctx, "Empty tile encountered!\n");
884 tile->data_size = ivi_dec_tile_data_size(&ctx->gb);
885 if (!tile->data_size) {
886 av_log(avctx, AV_LOG_ERROR, "Tile data size is zero!\n");
887 result = AVERROR_INVALIDDATA;
891 result = ctx->decode_mb_info(ctx, band, tile, avctx);
895 result = ivi_decode_blocks(&ctx->gb, band, tile, avctx);
897 av_log(avctx, AV_LOG_ERROR,
898 "Corrupted tile data encountered!\n");
902 if (((get_bits_count(&ctx->gb) - pos) >> 3) != tile->data_size) {
903 av_log(avctx, AV_LOG_ERROR,
904 "Tile data_size mismatch!\n");
905 result = AVERROR_INVALIDDATA;
909 pos += tile->data_size << 3; // skip to next tile
913 /* restore the selected rvmap table by applying its corrections in
915 for (i = band->num_corr-1; i >= 0; i--) {
916 idx1 = band->corr[i*2];
917 idx2 = band->corr[i*2+1];
918 FFSWAP(uint8_t, band->rv_map->runtab[idx1], band->rv_map->runtab[idx2]);
919 FFSWAP(int16_t, band->rv_map->valtab[idx1], band->rv_map->valtab[idx2]);
920 if (idx1 == band->rv_map->eob_sym || idx2 == band->rv_map->eob_sym)
921 band->rv_map->eob_sym ^= idx1 ^ idx2;
922 if (idx1 == band->rv_map->esc_sym || idx2 == band->rv_map->esc_sym)
923 band->rv_map->esc_sym ^= idx1 ^ idx2;
927 if (band->checksum_present) {
928 uint16_t chksum = ivi_calc_band_checksum(band);
929 if (chksum != band->checksum) {
930 av_log(avctx, AV_LOG_ERROR,
931 "Band checksum mismatch! Plane %d, band %d, "
932 "received: %x, calculated: %x\n",
933 band->plane, band->band_num, band->checksum, chksum);
938 align_get_bits(&ctx->gb);
943 int ff_ivi_decode_frame(AVCodecContext *avctx, void *data, int *got_frame,
946 IVI45DecContext *ctx = avctx->priv_data;
947 const uint8_t *buf = avpkt->data;
948 AVFrame *frame = data;
949 int buf_size = avpkt->size;
952 init_get_bits(&ctx->gb, buf, buf_size * 8);
953 ctx->frame_data = buf;
954 ctx->frame_size = buf_size;
956 result = ctx->decode_pic_hdr(ctx, avctx);
958 av_log(avctx, AV_LOG_ERROR,
959 "Error while decoding picture header: %d\n", result);
962 if (ctx->gop_invalid)
963 return AVERROR_INVALIDDATA;
965 if (ctx->gop_flags & IVI5_IS_PROTECTED) {
966 avpriv_report_missing_feature(avctx, "Password-protected clip!\n");
967 return AVERROR_PATCHWELCOME;
970 ctx->switch_buffers(ctx);
974 if (ctx->is_nonnull_frame(ctx)) {
975 ctx->buf_invalid[ctx->dst_buf] = 1;
976 for (p = 0; p < 3; p++) {
977 for (b = 0; b < ctx->planes[p].num_bands; b++) {
978 result = decode_band(ctx, &ctx->planes[p].bands[b], avctx);
980 av_log(avctx, AV_LOG_ERROR,
981 "Error while decoding band: %d, plane: %d\n", b, p);
986 ctx->buf_invalid[ctx->dst_buf] = 0;
988 if (ctx->buf_invalid[ctx->dst_buf])
991 //STOP_TIMER("decode_planes"); }
993 /* If the bidirectional mode is enabled, next I and the following P
994 * frame will be sent together. Unfortunately the approach below seems
995 * to be the only way to handle the B-frames mode.
996 * That's exactly the same Intel decoders do.
998 if (avctx->codec_id == AV_CODEC_ID_INDEO4 &&
999 ctx->frame_type == 0/*FRAMETYPE_INTRA*/) {
1000 while (get_bits(&ctx->gb, 8)); // skip version string
1001 skip_bits_long(&ctx->gb, 64); // skip padding, TODO: implement correct 8-bytes alignment
1002 if (get_bits_left(&ctx->gb) > 18 && show_bits(&ctx->gb, 18) == 0x3FFF8)
1003 av_log(avctx, AV_LOG_ERROR, "Buffer contains IP frames!\n");
1006 if (!ctx->is_nonnull_frame(ctx))
1009 avcodec_set_dimensions(avctx, ctx->planes[0].width, ctx->planes[0].height);
1010 if ((result = ff_get_buffer(avctx, frame, 0)) < 0)
1013 if (ctx->is_scalable) {
1014 if (avctx->codec_id == AV_CODEC_ID_INDEO4)
1015 ff_ivi_recompose_haar(&ctx->planes[0], frame->data[0], frame->linesize[0]);
1017 ff_ivi_recompose53 (&ctx->planes[0], frame->data[0], frame->linesize[0]);
1019 ivi_output_plane(&ctx->planes[0], frame->data[0], frame->linesize[0]);
1022 ivi_output_plane(&ctx->planes[2], frame->data[1], frame->linesize[1]);
1023 ivi_output_plane(&ctx->planes[1], frame->data[2], frame->linesize[2]);
1031 * Close Indeo5 decoder and clean up its context.
1033 av_cold int ff_ivi_decode_close(AVCodecContext *avctx)
1035 IVI45DecContext *ctx = avctx->priv_data;
1037 ivi_free_buffers(&ctx->planes[0]);
1039 if (ctx->mb_vlc.cust_tab.table)
1040 ff_free_vlc(&ctx->mb_vlc.cust_tab);
1042 #if IVI4_STREAM_ANALYSER
1043 if (avctx->codec_id == AV_CODEC_ID_INDEO4) {
1044 if (ctx->is_scalable)
1045 av_log(avctx, AV_LOG_ERROR, "This video uses scalability mode!\n");
1046 if (ctx->uses_tiling)
1047 av_log(avctx, AV_LOG_ERROR, "This video uses local decoding!\n");
1048 if (ctx->has_b_frames)
1049 av_log(avctx, AV_LOG_ERROR, "This video contains B-frames!\n");
1050 if (ctx->has_transp)
1051 av_log(avctx, AV_LOG_ERROR, "Transparency mode is enabled!\n");
1053 av_log(avctx, AV_LOG_ERROR, "This video uses Haar transform!\n");
1054 if (ctx->uses_fullpel)
1055 av_log(avctx, AV_LOG_ERROR, "This video uses fullpel motion vectors!\n");
1064 * These are 2x8 predefined Huffman codebooks for coding macroblock/block
1065 * signals. They are specified using "huffman descriptors" in order to
1066 * avoid huge static tables. The decoding tables will be generated at
1067 * startup from these descriptors.
1069 const IVIHuffDesc ff_ivi_mb_huff_desc[8] = {
1070 {8, {0, 4, 5, 4, 4, 4, 6, 6}},
1071 {12, {0, 2, 2, 3, 3, 3, 3, 5, 3, 2, 2, 2}},
1072 {12, {0, 2, 3, 4, 3, 3, 3, 3, 4, 3, 2, 2}},
1073 {12, {0, 3, 4, 4, 3, 3, 3, 3, 3, 2, 2, 2}},
1074 {13, {0, 4, 4, 3, 3, 3, 3, 2, 3, 3, 2, 1, 1}},
1075 {9, {0, 4, 4, 4, 4, 3, 3, 3, 2}},
1076 {10, {0, 4, 4, 4, 4, 3, 3, 2, 2, 2}},
1077 {12, {0, 4, 4, 4, 3, 3, 2, 3, 2, 2, 2, 2}}
1080 const IVIHuffDesc ff_ivi_blk_huff_desc[8] = {
1081 {10, {1, 2, 3, 4, 4, 7, 5, 5, 4, 1}},
1082 {11, {2, 3, 4, 4, 4, 7, 5, 4, 3, 3, 2}},
1083 {12, {2, 4, 5, 5, 5, 5, 6, 4, 4, 3, 1, 1}},
1084 {13, {3, 3, 4, 4, 5, 6, 6, 4, 4, 3, 2, 1, 1}},
1085 {11, {3, 4, 4, 5, 5, 5, 6, 5, 4, 2, 2}},
1086 {13, {3, 4, 5, 5, 5, 5, 6, 4, 3, 3, 2, 1, 1}},
1087 {13, {3, 4, 5, 5, 5, 6, 5, 4, 3, 3, 2, 1, 1}},
1088 {9, {3, 4, 4, 5, 5, 5, 6, 5, 5}}
1093 * Scan patterns shared between indeo4 and indeo5
1095 const uint8_t ff_ivi_vertical_scan_8x8[64] = {
1096 0, 8, 16, 24, 32, 40, 48, 56,
1097 1, 9, 17, 25, 33, 41, 49, 57,
1098 2, 10, 18, 26, 34, 42, 50, 58,
1099 3, 11, 19, 27, 35, 43, 51, 59,
1100 4, 12, 20, 28, 36, 44, 52, 60,
1101 5, 13, 21, 29, 37, 45, 53, 61,
1102 6, 14, 22, 30, 38, 46, 54, 62,
1103 7, 15, 23, 31, 39, 47, 55, 63
1106 const uint8_t ff_ivi_horizontal_scan_8x8[64] = {
1107 0, 1, 2, 3, 4, 5, 6, 7,
1108 8, 9, 10, 11, 12, 13, 14, 15,
1109 16, 17, 18, 19, 20, 21, 22, 23,
1110 24, 25, 26, 27, 28, 29, 30, 31,
1111 32, 33, 34, 35, 36, 37, 38, 39,
1112 40, 41, 42, 43, 44, 45, 46, 47,
1113 48, 49, 50, 51, 52, 53, 54, 55,
1114 56, 57, 58, 59, 60, 61, 62, 63
1117 const uint8_t ff_ivi_direct_scan_4x4[16] = {
1118 0, 1, 4, 8, 5, 2, 3, 6, 9, 12, 13, 10, 7, 11, 14, 15
1123 * Run-value (RLE) tables.
1125 const RVMapDesc ff_ivi_rvmap_tabs[9] = {
1130 {1, 1, 0, 1, 1, 0, 1, 1, 2, 2, 1, 1, 1, 1, 3, 3,
1131 1, 1, 2, 2, 1, 1, 4, 4, 1, 1, 1, 1, 2, 2, 5, 5,
1132 1, 1, 3, 3, 1, 1, 6, 6, 1, 2, 1, 2, 7, 7, 1, 1,
1133 8, 8, 1, 1, 4, 2, 1, 4, 2, 1, 3, 3, 1, 1, 1, 9,
1134 9, 1, 2, 1, 2, 1, 5, 5, 1, 1, 10, 10, 1, 1, 3, 3,
1135 2, 2, 1, 1, 11, 11, 6, 4, 4, 1, 6, 1, 2, 1, 2, 12,
1136 8, 1, 12, 7, 8, 7, 1, 16, 1, 16, 1, 3, 3, 13, 1, 13,
1137 2, 2, 1, 15, 1, 5, 14, 15, 1, 5, 14, 1, 17, 8, 17, 8,
1138 1, 4, 4, 2, 2, 1, 25, 25, 24, 24, 1, 3, 1, 3, 1, 8,
1139 6, 7, 6, 1, 18, 8, 18, 1, 7, 23, 2, 2, 23, 1, 1, 21,
1140 22, 9, 9, 22, 19, 1, 21, 5, 19, 5, 1, 33, 20, 33, 20, 8,
1141 4, 4, 1, 32, 2, 2, 8, 3, 32, 26, 3, 1, 7, 7, 26, 6,
1142 1, 6, 1, 1, 16, 1, 10, 1, 10, 2, 16, 29, 28, 2, 29, 28,
1143 1, 27, 5, 8, 5, 27, 1, 8, 3, 7, 3, 31, 41, 31, 1, 41,
1144 6, 1, 6, 7, 4, 4, 1, 1, 2, 1, 2, 11, 34, 30, 11, 1,
1145 30, 15, 15, 34, 36, 40, 36, 40, 35, 35, 37, 37, 39, 39, 38, 38},
1148 { 1, -1, 0, 2, -2, 0, 3, -3, 1, -1, 4, -4, 5, -5, 1, -1,
1149 6, -6, 2, -2, 7, -7, 1, -1, 8, -8, 9, -9, 3, -3, 1, -1,
1150 10, -10, 2, -2, 11, -11, 1, -1, 12, 4, -12, -4, 1, -1, 13, -13,
1151 1, -1, 14, -14, 2, 5, 15, -2, -5, -15, -3, 3, 16, -16, 17, 1,
1152 -1, -17, 6, 18, -6, -18, 2, -2, 19, -19, 1, -1, 20, -20, 4, -4,
1153 7, -7, 21, -21, 1, -1, 2, 3, -3, 22, -2, -22, 8, 23, -8, 1,
1154 2, -23, -1, 2, -2, -2, 24, 1, -24, -1, 25, 5, -5, 1, -25, -1,
1155 9, -9, 26, 1, -26, 3, 1, -1, 27, -3, -1, -27, 1, 3, -1, -3,
1156 28, -4, 4, 10, -10, -28, 1, -1, 1, -1, 29, 6, -29, -6, 30, -4,
1157 3, 3, -3, -30, 1, 4, -1, 31, -3, 1, 11, -11, -1, -31, 32, -1,
1158 -1, 2, -2, 1, 1, -32, 1, 4, -1, -4, 33, -1, 1, 1, -1, 5,
1159 5, -5, -33, -1, -12, 12, -5, -7, 1, 1, 7, 34, 4, -4, -1, 4,
1160 -34, -4, 35, 36, -2, -35, -2, -36, 2, 13, 2, -1, 1, -13, 1, -1,
1161 37, 1, -5, 6, 5, -1, 38, -6, -8, 5, 8, -1, 1, 1, -37, -1,
1162 5, 39, -5, -5, 6, -6, -38, -39, -14, 40, 14, 2, 1, 1, -2, -40,
1163 -1, -2, 2, -1, -1, -1, 1, 1, 1, -1, 1, -1, 1, -1, 1, -1}
1169 {0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 8, 6, 8, 7,
1170 7, 9, 9, 10, 10, 11, 11, 1, 12, 1, 12, 13, 13, 16, 14, 16,
1171 14, 15, 15, 17, 17, 18, 0, 18, 19, 20, 21, 19, 22, 21, 20, 22,
1172 25, 24, 2, 25, 24, 23, 23, 2, 26, 28, 26, 28, 29, 27, 29, 27,
1173 33, 33, 1, 32, 1, 3, 32, 30, 36, 3, 36, 30, 31, 31, 35, 34,
1174 37, 41, 34, 35, 37, 4, 41, 4, 49, 8, 8, 49, 40, 38, 5, 38,
1175 40, 39, 5, 39, 42, 43, 42, 7, 57, 6, 43, 44, 6, 50, 7, 44,
1176 57, 48, 50, 48, 45, 45, 46, 47, 51, 46, 47, 58, 1, 51, 58, 1,
1177 52, 59, 53, 9, 52, 55, 55, 59, 53, 56, 54, 56, 54, 9, 64, 64,
1178 60, 63, 60, 63, 61, 62, 61, 62, 2, 10, 2, 10, 11, 1, 11, 13,
1179 12, 1, 12, 13, 16, 16, 8, 8, 14, 3, 3, 15, 14, 15, 4, 4,
1180 1, 17, 17, 5, 1, 7, 7, 5, 6, 1, 2, 2, 6, 22, 1, 25,
1181 21, 22, 8, 24, 1, 21, 25, 24, 8, 18, 18, 23, 9, 20, 23, 33,
1182 29, 33, 20, 1, 19, 1, 29, 36, 9, 36, 19, 41, 28, 57, 32, 3,
1183 28, 3, 1, 27, 49, 49, 1, 32, 26, 26, 2, 4, 4, 7, 57, 41,
1184 2, 7, 10, 5, 37, 16, 10, 27, 8, 8, 13, 16, 37, 13, 1, 5},
1187 {0, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, 1, -1, -1, 1,
1188 -1, 1, -1, 1, -1, 1, -1, 2, 1, -2, -1, 1, -1, 1, 1, -1,
1189 -1, 1, -1, 1, -1, 1, 0, -1, 1, 1, 1, -1, 1, -1, -1, -1,
1190 1, 1, 2, -1, -1, 1, -1, -2, 1, 1, -1, -1, 1, 1, -1, -1,
1191 1, -1, 3, 1, -3, 2, -1, 1, 1, -2, -1, -1, -1, 1, 1, 1,
1192 1, 1, -1, -1, -1, 2, -1, -2, 1, 2, -2, -1, 1, 1, 2, -1,
1193 -1, 1, -2, -1, 1, 1, -1, 2, 1, 2, -1, 1, -2, -1, -2, -1,
1194 -1, 1, 1, -1, 1, -1, 1, 1, 1, -1, -1, 1, 4, -1, -1, -4,
1195 1, 1, 1, 2, -1, -1, 1, -1, -1, 1, -1, -1, 1, -2, 1, -1,
1196 1, 1, -1, -1, 1, 1, -1, -1, 3, 2, -3, -2, 2, 5, -2, 2,
1197 2, -5, -2, -2, -2, 2, -3, 3, 2, 3, -3, 2, -2, -2, 3, -3,
1198 6, 2, -2, 3, -6, 3, -3, -3, 3, 7, -4, 4, -3, 2, -7, 2,
1199 2, -2, -4, 2, 8, -2, -2, -2, 4, 2, -2, 2, 3, 2, -2, -2,
1200 2, 2, -2, -8, -2, 9, -2, 2, -3, -2, 2, -2, 2, 2, 2, 4,
1201 -2, -4, 10, 2, 2, -2, -9, -2, 2, -2, 5, 4, -4, 4, -2, 2,
1202 -5, -4, -3, 4, 2, -3, 3, -2, -5, 5, 3, 3, -2, -3, -10, -4}
1208 {1, 1, 0, 2, 2, 1, 1, 3, 3, 4, 4, 0, 1, 1, 5, 5,
1209 2, 2, 6, 6, 7, 7, 1, 8, 1, 8, 3, 3, 9, 9, 1, 2,
1210 2, 1, 4, 10, 4, 10, 11, 11, 1, 5, 12, 12, 1, 5, 13, 13,
1211 3, 3, 6, 6, 2, 2, 14, 14, 16, 16, 15, 7, 15, 8, 8, 7,
1212 1, 1, 17, 17, 4, 4, 1, 1, 18, 18, 2, 2, 5, 5, 25, 3,
1213 9, 3, 25, 9, 19, 24, 19, 24, 1, 21, 20, 1, 21, 22, 20, 22,
1214 23, 23, 8, 6, 33, 6, 8, 33, 7, 7, 26, 26, 1, 32, 1, 32,
1215 28, 4, 28, 10, 29, 27, 27, 10, 41, 4, 29, 2, 2, 41, 36, 31,
1216 49, 31, 34, 30, 34, 36, 30, 35, 1, 49, 11, 5, 35, 11, 1, 3,
1217 3, 5, 37, 37, 8, 40, 8, 40, 12, 12, 42, 42, 1, 38, 16, 57,
1218 1, 6, 16, 39, 38, 6, 7, 7, 13, 13, 39, 43, 2, 43, 57, 2,
1219 50, 9, 44, 9, 50, 4, 15, 48, 44, 4, 1, 15, 48, 14, 14, 1,
1220 45, 45, 8, 3, 5, 8, 51, 47, 3, 46, 46, 47, 5, 51, 1, 17,
1221 17, 58, 1, 58, 2, 52, 52, 2, 53, 7, 59, 6, 6, 56, 53, 55,
1222 7, 55, 1, 54, 59, 56, 54, 10, 1, 10, 4, 60, 1, 60, 8, 4,
1223 8, 64, 64, 61, 1, 63, 3, 63, 62, 61, 5, 11, 5, 3, 11, 62},
1226 { 1, -1, 0, 1, -1, 2, -2, 1, -1, 1, -1, 0, 3, -3, 1, -1,
1227 2, -2, 1, -1, 1, -1, 4, 1, -4, -1, 2, -2, 1, -1, 5, 3,
1228 -3, -5, 2, 1, -2, -1, 1, -1, 6, 2, 1, -1, -6, -2, 1, -1,
1229 3, -3, 2, -2, 4, -4, 1, -1, 1, -1, 1, 2, -1, 2, -2, -2,
1230 7, -7, 1, -1, 3, -3, 8, -8, 1, -1, 5, -5, 3, -3, 1, 4,
1231 2, -4, -1, -2, 1, 1, -1, -1, 9, 1, 1, -9, -1, 1, -1, -1,
1232 1, -1, 3, -3, 1, 3, -3, -1, 3, -3, 1, -1, 10, 1, -10, -1,
1233 1, 4, -1, 2, 1, -1, 1, -2, 1, -4, -1, 6, -6, -1, 1, 1,
1234 1, -1, 1, 1, -1, -1, -1, 1, 11, -1, -2, 4, -1, 2, -11, 5,
1235 -5, -4, -1, 1, 4, 1, -4, -1, -2, 2, 1, -1, 12, 1, -2, 1,
1236 -12, 4, 2, 1, -1, -4, 4, -4, 2, -2, -1, 1, 7, -1, -1, -7,
1237 -1, -3, 1, 3, 1, 5, 2, 1, -1, -5, 13, -2, -1, 2, -2, -13,
1238 1, -1, 5, 6, 5, -5, 1, 1, -6, 1, -1, -1, -5, -1, 14, 2,
1239 -2, 1, -14, -1, 8, 1, -1, -8, 1, 5, 1, 5, -5, 1, -1, 1,
1240 -5, -1, 15, 1, -1, -1, -1, 3, -15, -3, 6, 1, 16, -1, 6, -6,
1241 -6, 1, -1, 1, -16, 1, 7, -1, 1, -1, -6, -3, 6, -7, 3, -1}
1247 {0, 1, 1, 2, 2, 3, 3, 4, 4, 1, 1, 5, 5, 6, 6, 7,
1248 7, 8, 8, 9, 9, 2, 2, 10, 10, 1, 1, 11, 11, 12, 12, 3,
1249 3, 13, 13, 0, 14, 14, 16, 15, 16, 15, 4, 4, 17, 1, 17, 1,
1250 5, 5, 18, 18, 2, 2, 6, 6, 8, 19, 7, 8, 7, 19, 20, 20,
1251 21, 21, 22, 24, 22, 24, 23, 23, 1, 1, 25, 25, 3, 3, 26, 26,
1252 9, 9, 27, 27, 28, 28, 33, 29, 4, 33, 29, 1, 4, 1, 32, 32,
1253 2, 2, 31, 10, 30, 10, 30, 31, 34, 34, 5, 5, 36, 36, 35, 41,
1254 35, 11, 41, 11, 37, 1, 8, 8, 37, 6, 1, 6, 40, 7, 7, 40,
1255 12, 38, 12, 39, 39, 38, 49, 13, 49, 13, 3, 42, 3, 42, 16, 16,
1256 43, 43, 14, 14, 1, 1, 44, 15, 44, 15, 2, 2, 57, 48, 50, 48,
1257 57, 50, 4, 45, 45, 4, 46, 47, 47, 46, 1, 51, 1, 17, 17, 51,
1258 8, 9, 9, 5, 58, 8, 58, 5, 52, 52, 55, 56, 53, 56, 55, 59,
1259 59, 53, 54, 1, 6, 54, 7, 7, 6, 1, 2, 3, 2, 3, 64, 60,
1260 60, 10, 10, 64, 61, 62, 61, 63, 1, 63, 62, 1, 18, 24, 18, 4,
1261 25, 4, 8, 21, 21, 1, 24, 22, 25, 22, 8, 11, 19, 11, 23, 1,
1262 20, 23, 19, 20, 5, 12, 5, 1, 16, 2, 12, 13, 2, 13, 1, 16},
1265 { 0, 1, -1, 1, -1, 1, -1, 1, -1, 2, -2, 1, -1, 1, -1, 1,
1266 -1, 1, -1, 1, -1, 2, -2, 1, -1, 3, -3, 1, -1, 1, -1, 2,
1267 -2, 1, -1, 0, 1, -1, 1, 1, -1, -1, 2, -2, 1, 4, -1, -4,
1268 2, -2, 1, -1, -3, 3, 2, -2, 2, 1, 2, -2, -2, -1, 1, -1,
1269 1, -1, 1, 1, -1, -1, 1, -1, 5, -5, 1, -1, 3, -3, 1, -1,
1270 2, -2, 1, -1, 1, -1, 1, 1, 3, -1, -1, 6, -3, -6, -1, 1,
1271 4, -4, 1, 2, 1, -2, -1, -1, 1, -1, 3, -3, 1, -1, 1, 1,
1272 -1, 2, -1, -2, 1, 7, -3, 3, -1, 3, -7, -3, 1, -3, 3, -1,
1273 2, 1, -2, 1, -1, -1, 1, 2, -1, -2, -4, -1, 4, 1, 2, -2,
1274 1, -1, -2, 2, 8, -8, -1, 2, 1, -2, -5, 5, 1, -1, -1, 1,
1275 -1, 1, 4, -1, 1, -4, -1, -1, 1, 1, 9, 1, -9, 2, -2, -1,
1276 -4, 3, -3, -4, -1, 4, 1, 4, 1, -1, 1, -1, 1, 1, -1, 1,
1277 -1, -1, -1, 10, 4, 1, 4, -4, -4, -10, 6, 5, -6, -5, 1, -1,
1278 1, 3, -3, -1, 1, -1, -1, -1, 11, 1, 1, -11, -2, -2, 2, 5,
1279 -2, -5, -5, 2, -2, 12, 2, -2, 2, 2, 5, -3, -2, 3, -2, -12,
1280 -2, 2, 2, 2, -5, 3, 5, 13, -3, 7, -3, -3, -7, 3, -13, 3}
1286 {0, 1, 1, 1, 2, 2, 1, 3, 3, 1, 1, 1, 4, 4, 1, 5,
1287 2, 1, 5, 2, 1, 1, 6, 6, 1, 1, 1, 1, 1, 7, 3, 1,
1288 2, 3, 0, 1, 2, 7, 1, 1, 1, 8, 1, 1, 8, 1, 1, 1,
1289 9, 1, 9, 1, 2, 1, 1, 2, 1, 1, 10, 4, 1, 10, 1, 4,
1290 1, 1, 1, 1, 1, 3, 1, 1, 1, 3, 2, 1, 5, 1, 1, 1,
1291 2, 5, 1, 11, 1, 11, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1292 2, 1, 6, 1, 6, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 12,
1293 3, 1, 12, 1, 1, 1, 2, 1, 1, 3, 1, 1, 1, 1, 1, 1,
1294 4, 1, 1, 1, 2, 1, 1, 4, 1, 1, 1, 1, 1, 1, 2, 1,
1295 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 2, 1, 1, 5,
1296 1, 1, 1, 1, 1, 7, 1, 7, 1, 1, 2, 3, 1, 1, 1, 1,
1297 5, 1, 1, 1, 1, 1, 1, 2, 13, 1, 1, 1, 1, 1, 1, 1,
1298 1, 1, 1, 1, 1, 1, 1, 1, 13, 2, 1, 1, 4, 1, 1, 1,
1299 3, 1, 6, 1, 1, 1, 14, 1, 1, 1, 1, 1, 14, 6, 1, 1,
1300 1, 1, 15, 2, 4, 1, 2, 3, 15, 1, 1, 1, 8, 1, 1, 8,
1301 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1},
1304 { 0, 1, -1, 2, 1, -1, -2, 1, -1, 3, -3, 4, 1, -1, -4, 1,
1305 2, 5, -1, -2, -5, 6, 1, -1, -6, 7, -7, 8, -8, 1, 2, 9,
1306 3, -2, 0, -9, -3, -1, 10, -10, 11, 1, -11, 12, -1, -12, 13, -13,
1307 1, 14, -1, -14, 4, 15, -15, -4, 16, -16, 1, 2, 17, -1, -17, -2,
1308 18, -18, 19, -19, 20, 3, -20, 21, -21, -3, 5, 22, 2, -22, -23, 23,
1309 -5, -2, 24, 1, -24, -1, 25, -25, 26, -26, -27, 27, 28, 29, -28, -29,
1310 6, 30, 2, -31, -2, -30, 31, -6, -32, 32, 33, -33, 34, -35, -34, 1,
1311 4, -36, -1, 35, 37, 36, 7, -37, 38, -4, -38, 39, 41, 40, -40, -39,
1312 3, 42, -43, -41, -7, -42, 43, -3, 44, -44, 45, -45, 46, 47, 8, -47,
1313 -48, -46, 50, -50, 48, 49, 51, -49, 52, -52, 5, -51, -8, -53, 53, 3,
1314 -56, 56, 55, 54, -54, 2, 60, -2, -55, 58, 9, -5, 59, 57, -57, -63,
1315 -3, -58, -60, -61, 61, -59, -62, -9, 1, 64, 62, 69, -64, 63, 65, -67,
1316 -68, 66, -65, 68, -66, -69, 67, -70, -1, 10, 71, -71, 4, 73, 72, 70,
1317 6, -76, -3, 74, -78, -74, 1, 78, 80, -72, -75, 76, -1, 3, -73, 79,
1318 75, 77, 1, 11, -4, -79, -10, -6, -1, -77, -83, -80, 2, 81, -84, -2,
1319 83, -81, 82, -82, 84, -87, -86, 85, -11, -85, 86, -89, 87, -88, 88, 89}
1325 {1, 1, 0, 2, 1, 2, 1, 3, 3, 1, 1, 4, 4, 2, 2, 1,
1326 1, 5, 5, 6, 1, 6, 1, 7, 7, 3, 3, 2, 8, 2, 8, 1,
1327 1, 0, 9, 9, 1, 1, 10, 4, 10, 4, 11, 11, 2, 1, 2, 1,
1328 12, 12, 3, 3, 1, 1, 13, 5, 5, 13, 14, 1, 1, 14, 2, 2,
1329 6, 6, 15, 1, 1, 15, 16, 4, 7, 16, 4, 7, 1, 1, 3, 3,
1330 8, 8, 2, 2, 1, 1, 17, 17, 1, 1, 18, 18, 5, 5, 2, 2,
1331 1, 1, 9, 19, 9, 19, 20, 3, 3, 20, 1, 10, 21, 1, 10, 4,
1332 4, 21, 22, 6, 6, 22, 1, 1, 23, 24, 2, 2, 23, 24, 11, 1,
1333 1, 11, 7, 25, 7, 1, 1, 25, 8, 8, 3, 26, 3, 1, 12, 2,
1334 2, 26, 1, 12, 5, 5, 27, 4, 1, 4, 1, 27, 28, 1, 28, 13,
1335 1, 13, 2, 29, 2, 1, 32, 6, 1, 30, 14, 29, 14, 6, 3, 31,
1336 3, 1, 30, 1, 32, 31, 33, 9, 33, 1, 1, 7, 9, 7, 2, 2,
1337 1, 1, 4, 36, 34, 4, 5, 10, 10, 5, 34, 1, 1, 35, 8, 8,
1338 36, 3, 35, 1, 15, 3, 2, 1, 16, 15, 16, 2, 37, 1, 37, 1,
1339 1, 1, 6, 6, 38, 1, 38, 11, 1, 39, 39, 40, 11, 2, 41, 4,
1340 40, 1, 2, 4, 1, 1, 1, 41, 3, 1, 3, 1, 5, 7, 5, 7},
1343 { 1, -1, 0, 1, 2, -1, -2, 1, -1, 3, -3, 1, -1, 2, -2, 4,
1344 -4, 1, -1, 1, 5, -1, -5, 1, -1, 2, -2, 3, 1, -3, -1, 6,
1345 -6, 0, 1, -1, 7, -7, 1, 2, -1, -2, 1, -1, 4, 8, -4, -8,
1346 1, -1, 3, -3, 9, -9, 1, 2, -2, -1, 1, 10, -10, -1, 5, -5,
1347 2, -2, 1, 11, -11, -1, 1, 3, 2, -1, -3, -2, 12, -12, 4, -4,
1348 2, -2, -6, 6, 13, -13, 1, -1, 14, -14, 1, -1, 3, -3, 7, -7,
1349 15, -15, 2, 1, -2, -1, 1, 5, -5, -1, -16, 2, 1, 16, -2, 4,
1350 -4, -1, 1, 3, -3, -1, 17, -17, 1, 1, -8, 8, -1, -1, 2, 18,
1351 -18, -2, 3, 1, -3, 19, -19, -1, 3, -3, 6, 1, -6, 20, 2, 9,
1352 -9, -1, -20, -2, 4, -4, 1, -5, 21, 5, -21, -1, 1, -22, -1, 2,
1353 22, -2, 10, 1, -10, 23, 1, 4, -23, 1, 2, -1, -2, -4, -7, 1,
1354 7, -24, -1, 24, -1, -1, 1, 3, -1, -25, 25, 4, -3, -4, 11, -11,
1355 26, -26, 6, 1, 1, -6, -5, -3, 3, 5, -1, -27, 27, 1, 4, -4,
1356 -1, -8, -1, 28, 2, 8, -12, -28, -2, -2, 2, 12, -1, 29, 1, -29,
1357 30, -30, 5, -5, 1, -31, -1, 3, 31, -1, 1, 1, -3, -13, 1, -7,
1358 -1, -32, 13, 7, 32, 33, -33, -1, -9, -34, 9, 34, -6, 5, 6, -5}
1364 {1, 1, 0, 1, 1, 2, 2, 1, 1, 3, 3, 1, 1, 0, 2, 2,
1365 4, 1, 4, 1, 1, 1, 5, 5, 1, 1, 6, 6, 2, 2, 1, 1,
1366 3, 3, 7, 7, 1, 1, 8, 8, 1, 1, 2, 2, 1, 9, 1, 9,
1367 4, 4, 10, 1, 1, 10, 1, 1, 11, 11, 3, 3, 1, 2, 1, 2,
1368 1, 1, 12, 12, 5, 5, 1, 1, 13, 1, 1, 13, 2, 2, 1, 1,
1369 6, 6, 1, 1, 4, 14, 4, 14, 3, 1, 3, 1, 1, 1, 15, 7,
1370 15, 2, 2, 7, 1, 1, 1, 8, 1, 8, 16, 16, 1, 1, 1, 1,
1371 2, 1, 1, 2, 1, 1, 3, 5, 5, 3, 4, 1, 1, 4, 1, 1,
1372 17, 17, 9, 1, 1, 9, 2, 2, 1, 1, 10, 10, 1, 6, 1, 1,
1373 6, 18, 1, 1, 18, 1, 1, 1, 2, 2, 3, 1, 3, 1, 1, 1,
1374 4, 1, 19, 1, 19, 7, 1, 1, 20, 1, 4, 20, 1, 7, 11, 2,
1375 1, 11, 21, 2, 8, 5, 1, 8, 1, 5, 21, 1, 1, 1, 22, 1,
1376 1, 22, 1, 1, 3, 3, 1, 23, 2, 12, 24, 1, 1, 2, 1, 1,
1377 12, 23, 1, 1, 24, 1, 1, 1, 4, 1, 1, 1, 2, 1, 6, 6,
1378 4, 2, 1, 1, 1, 1, 1, 1, 1, 14, 13, 3, 1, 25, 9, 25,
1379 14, 1, 9, 3, 13, 1, 1, 1, 1, 1, 10, 1, 1, 2, 10, 2},
1382 {-20, -1, 0, 2, -2, 1, -1, 3, -3, 1, -1, 4, -4, 0, 2, -2,
1383 1, 5, -1, -5, 6, -6, 1, -1, 7, -7, 1, -1, 3, -3, 8, -8,
1384 2, -2, 1, -1, 9, -9, 1, -1, 10, -10, 4, -4, 11, 1, -11, -1,
1385 2, -2, 1, 12, -12, -1, 13, -13, 1, -1, 3, -3, 14, 5, -14, -5,
1386 -15, 15, -1, 1, 2, -2, 16, -16, 1, 17, -17, -1, 6, -6, 18, -18,
1387 2, -2, -19, 19, -3, 1, 3, -1, 4, 20, -4, 1, -21, 21, 1, 2,
1388 -1, -7, 7, -2, 22, -22, 23, 2, -23, -2, 1, -1, -24, 24, -25, 25,
1389 -8, -26, 26, 8, -27, 27, 5, 3, -3, -5, -4, 28, -28, 4, 29, -29,
1390 1, -1, -2, -30, 30, 2, 9, -9, -31, 31, 2, -2, -32, 3, 32, -33,
1391 -3, 1, 33, -34, -1, 34, -35, 35, -10, 10, -6, 36, 6, -36, 37, -37,
1392 -5, 38, 1, -38, -1, 3, 39, -39, -1, 40, 5, 1, -40, -3, 2, -11,
1393 -41, -2, 1, 11, -3, -4, 41, 3, 42, 4, -1, -43, -42, 43, 1, -44,
1394 45, -1, 44, -45, -7, 7, -46, 1, -12, 2, 1, -47, 46, 12, 47, 48,
1395 -2, -1, -48, 49, -1, -50, -49, 50, -6, -51, 51, 52, -13, 53, -4, 4,
1396 6, 13, -53, -52, -54, 55, 54, -55, -56, -2, 2, -8, 56, 1, -3, -1,
1397 2, 58, 3, 8, -2, 57, -58, -60, -59, -57, -3, 60, 59, -14, 3, 14}
1403 {1, 1, 0, 2, 2, 1, 1, 3, 3, 4, 4, 5, 5, 1, 1, 6,
1404 6, 2, 2, 7, 7, 8, 8, 1, 1, 3, 3, 9, 9, 10, 10, 1,
1405 1, 2, 2, 4, 4, 11, 0, 11, 12, 12, 13, 13, 1, 1, 5, 5,
1406 14, 14, 15, 16, 15, 16, 3, 3, 1, 6, 1, 6, 2, 2, 7, 7,
1407 8, 8, 17, 17, 1, 1, 4, 4, 18, 18, 2, 2, 1, 19, 1, 20,
1408 19, 20, 21, 21, 3, 3, 22, 22, 5, 5, 24, 1, 1, 23, 9, 23,
1409 24, 9, 2, 2, 10, 1, 1, 10, 6, 6, 25, 4, 4, 25, 7, 7,
1410 26, 8, 1, 8, 3, 1, 26, 3, 11, 11, 27, 27, 2, 28, 1, 2,
1411 28, 1, 12, 12, 5, 5, 29, 13, 13, 29, 32, 1, 1, 33, 31, 30,
1412 32, 4, 30, 33, 4, 31, 3, 14, 1, 1, 3, 34, 34, 2, 2, 14,
1413 6, 6, 35, 36, 35, 36, 1, 15, 1, 16, 16, 15, 7, 9, 7, 9,
1414 37, 8, 8, 37, 1, 1, 39, 2, 38, 39, 2, 40, 5, 38, 40, 5,
1415 3, 3, 4, 4, 10, 10, 1, 1, 1, 1, 41, 2, 41, 2, 6, 6,
1416 1, 1, 11, 42, 11, 43, 3, 42, 3, 17, 4, 43, 1, 17, 7, 1,
1417 8, 44, 4, 7, 44, 5, 8, 2, 5, 1, 2, 48, 45, 1, 12, 45,
1418 12, 48, 13, 13, 1, 9, 9, 46, 1, 46, 47, 47, 49, 18, 18, 49},
1421 { 1, -1, 0, 1, -1, 2, -2, 1, -1, 1, -1, 1, -1, 3, -3, 1,
1422 -1, -2, 2, 1, -1, 1, -1, 4, -4, -2, 2, 1, -1, 1, -1, 5,
1423 -5, -3, 3, 2, -2, 1, 0, -1, 1, -1, 1, -1, 6, -6, 2, -2,
1424 1, -1, 1, 1, -1, -1, -3, 3, 7, 2, -7, -2, -4, 4, 2, -2,
1425 2, -2, 1, -1, 8, -8, 3, -3, 1, -1, -5, 5, 9, 1, -9, 1,
1426 -1, -1, 1, -1, -4, 4, 1, -1, 3, -3, 1, -10, 10, 1, 2, -1,
1427 -1, -2, 6, -6, 2, 11, -11, -2, 3, -3, 1, -4, 4, -1, 3, -3,
1428 1, 3, 12, -3, -5, -12, -1, 5, 2, -2, 1, -1, -7, 1, 13, 7,
1429 -1, -13, 2, -2, 4, -4, 1, 2, -2, -1, 1, 14, -14, 1, 1, 1,
1430 -1, -5, -1, -1, 5, -1, -6, 2, -15, 15, 6, 1, -1, -8, 8, -2,
1431 -4, 4, 1, 1, -1, -1, 16, 2, -16, -2, 2, -2, 4, 3, -4, -3,
1432 -1, -4, 4, 1, -17, 17, -1, -9, 1, 1, 9, 1, -5, -1, -1, 5,
1433 -7, 7, 6, -6, 3, -3, 18, -18, 19, -19, 1, -10, -1, 10, -5, 5,
1434 20, -20, -3, 1, 3, 1, 8, -1, -8, 2, 7, -1, -21, -2, 5, 21,
1435 5, -1, -7, -5, 1, -6, -5, -11, 6, 22, 11, 1, 1, -22, -3, -1,
1436 3, -1, 3, -3, -23, 4, -4, 1, 23, -1, 1, -1, 1, -2, 2, -1}
1442 {1, 1, 1, 1, 0, 2, 2, 1, 1, 3, 3, 0, 1, 1, 2, 2,
1443 4, 4, 1, 1, 5, 5, 1, 1, 2, 2, 3, 3, 6, 6, 1, 1,
1444 7, 7, 8, 1, 8, 2, 2, 1, 4, 4, 1, 3, 1, 3, 9, 9,
1445 2, 2, 1, 5, 1, 5, 10, 10, 1, 1, 11, 11, 3, 6, 3, 4,
1446 4, 6, 2, 2, 1, 12, 1, 12, 7, 13, 7, 13, 1, 1, 8, 8,
1447 2, 2, 14, 14, 16, 15, 16, 5, 5, 1, 3, 15, 1, 3, 4, 4,
1448 1, 1, 17, 17, 2, 2, 6, 6, 1, 18, 1, 18, 22, 21, 22, 21,
1449 25, 24, 25, 19, 9, 20, 9, 23, 19, 24, 20, 3, 23, 7, 3, 1,
1450 1, 7, 28, 26, 29, 5, 28, 26, 5, 8, 29, 4, 8, 27, 2, 2,
1451 4, 27, 1, 1, 10, 36, 10, 33, 33, 36, 30, 1, 32, 32, 1, 30,
1452 6, 31, 31, 35, 3, 6, 11, 11, 3, 2, 35, 2, 34, 1, 34, 1,
1453 37, 37, 12, 7, 12, 5, 41, 5, 4, 7, 1, 8, 13, 4, 1, 41,
1454 13, 38, 8, 38, 9, 1, 40, 40, 9, 1, 39, 2, 2, 49, 39, 42,
1455 3, 3, 14, 16, 49, 14, 16, 42, 43, 43, 6, 6, 15, 1, 1, 15,
1456 44, 44, 1, 1, 50, 48, 4, 5, 4, 7, 5, 2, 10, 10, 48, 7,
1457 50, 45, 2, 1, 45, 8, 8, 1, 46, 46, 3, 47, 47, 3, 1, 1},
1460 { 1, -1, 2, -2, 0, 1, -1, 3, -3, 1, -1, 0, 4, -4, 2, -2,
1461 1, -1, 5, -5, 1, -1, 6, -6, 3, -3, 2, -2, 1, -1, 7, -7,
1462 1, -1, 1, 8, -1, 4, -4, -8, 2, -2, 9, 3, -9, -3, 1, -1,
1463 5, -5, 10, 2, -10, -2, 1, -1, 11, -11, 1, -1, -4, 2, 4, 3,
1464 -3, -2, 6, -6, 12, 1, -12, -1, 2, 1, -2, -1, 13, -13, 2, -2,
1465 7, -7, 1, -1, 1, 1, -1, 3, -3, 14, 5, -1, -14, -5, 4, -4,
1466 15, -15, 1, -1, 8, -8, -3, 3, 16, 1, -16, -1, 1, 1, -1, -1,
1467 1, 1, -1, 1, 2, 1, -2, 1, -1, -1, -1, 6, -1, 3, -6, 17,
1468 -17, -3, 1, 1, 1, 4, -1, -1, -4, 3, -1, 5, -3, -1, -9, 9,
1469 -5, 1, 18, -18, 2, 1, -2, 1, -1, -1, 1, 19, -1, 1, -19, -1,
1470 4, 1, -1, 1, 7, -4, -2, 2, -7, 10, -1, -10, 1, 20, -1, -20,
1471 1, -1, 2, 4, -2, 5, 1, -5, 6, -4, 21, 4, 2, -6, -21, -1,
1472 -2, 1, -4, -1, -3, 22, -1, 1, 3, -22, -1, 11, -11, 1, 1, 1,
1473 8, -8, 2, 2, -1, -2, -2, -1, 1, -1, -5, 5, 2, 23, -23, -2,
1474 1, -1, 24, -24, -1, -1, 7, 6, -7, 5, -6, 12, -3, 3, 1, -5,
1475 1, 1, -12, 25, -1, -5, 5, -25, -1, 1, 9, 1, -1, -9, 26, -26}