2 * common functions for Indeo Video Interactive codecs (Indeo4 and Indeo5)
4 * Copyright (c) 2009 Maxim Poliakovski
6 * This file is part of FFmpeg.
8 * FFmpeg is free software; you can redistribute it and/or
9 * modify it under the terms of the GNU Lesser General Public
10 * License as published by the Free Software Foundation; either
11 * version 2.1 of the License, or (at your option) any later version.
13 * FFmpeg is distributed in the hope that it will be useful,
14 * but WITHOUT ANY WARRANTY; without even the implied warranty of
15 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 * Lesser General Public License for more details.
18 * You should have received a copy of the GNU Lesser General Public
19 * License along with FFmpeg; if not, write to the Free Software
20 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
25 * This file contains functions and data shared by both Indeo4 and
31 #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 av_assert0(offs
>= 0 && ref_offs
>= 0 && band
->ref_buf
);
91 av_assert0(buf_size
- min_size
>= offs
);
92 av_assert0(buf_size
- min_size
- ref_size
>= ref_offs
);
96 mc(band
->buf
+ offs
, band
->ref_buf
+ ref_offs
, band
->pitch
, mc_type
);
98 int ref_offs2
= offs
+ mv_y2
* band
->pitch
+ mv_x2
;
99 int ref_size2
= (mc_type2
> 1) * band
->pitch
+ (mc_type2
& 1);
100 if (offs
< 0 || ref_offs2
< 0 || !band
->b_ref_buf
)
101 return AVERROR_INVALIDDATA
;
102 if (buf_size
- min_size
- ref_size2
< ref_offs2
)
103 return AVERROR_INVALIDDATA
;
106 mc(band
->buf
+ offs
, band
->b_ref_buf
+ ref_offs2
,
107 band
->pitch
, mc_type2
);
109 mc_avg(band
->buf
+ offs
, band
->ref_buf
+ ref_offs
,
110 band
->b_ref_buf
+ ref_offs2
, band
->pitch
,
118 * Reverse "nbits" bits of the value "val" and return the result
119 * in the least significant bits.
121 static uint16_t inv_bits(uint16_t val
, int nbits
)
126 res
= ff_reverse
[val
] >> (8 - nbits
);
128 res
= ((ff_reverse
[val
& 0xFF] << 8) +
129 (ff_reverse
[val
>> 8])) >> (16 - nbits
);
135 * Generate a huffman codebook from the given descriptor
136 * and convert it into the FFmpeg VLC table.
138 * @param[in] cb pointer to codebook descriptor
139 * @param[out] vlc where to place the generated VLC table
140 * @param[in] flag flag: 1 - for static or 0 for dynamic tables
141 * @return result code: 0 - OK, -1 = error (invalid codebook descriptor)
143 static int ivi_create_huff_from_desc(const IVIHuffDesc
*cb
, VLC
*vlc
, int flag
)
145 int pos
, i
, j
, codes_per_row
, prefix
, not_last_row
;
146 uint16_t codewords
[256]; /* FIXME: move this temporal storage out? */
149 pos
= 0; /* current position = 0 */
151 for (i
= 0; i
< cb
->num_rows
; i
++) {
152 codes_per_row
= 1 << cb
->xbits
[i
];
153 not_last_row
= (i
!= cb
->num_rows
- 1);
154 prefix
= ((1 << i
) - 1) << (cb
->xbits
[i
] + not_last_row
);
156 for (j
= 0; j
< codes_per_row
; j
++) {
157 if (pos
>= 256) /* Some Indeo5 codebooks can have more than 256 */
158 break; /* elements, but only 256 codes are allowed! */
160 bits
[pos
] = i
+ cb
->xbits
[i
] + not_last_row
;
161 if (bits
[pos
] > IVI_VLC_BITS
)
162 return AVERROR_INVALIDDATA
; /* invalid descriptor */
164 codewords
[pos
] = inv_bits((prefix
| j
), bits
[pos
]);
172 /* number of codewords = pos */
173 return init_vlc(vlc
, IVI_VLC_BITS
, pos
, bits
, 1, 1, codewords
, 2, 2,
174 (flag
? INIT_VLC_USE_NEW_STATIC
: 0) | INIT_VLC_LE
);
177 av_cold
void ff_ivi_init_static_vlc(void)
180 static VLC_TYPE table_data
[8192 * 16][2];
181 static int initialized_vlcs
= 0;
183 if (initialized_vlcs
)
185 for (i
= 0; i
< 8; i
++) {
186 ivi_mb_vlc_tabs
[i
].table
= table_data
+ i
* 2 * 8192;
187 ivi_mb_vlc_tabs
[i
].table_allocated
= 8192;
188 ivi_create_huff_from_desc(&ivi_mb_huff_desc
[i
],
189 &ivi_mb_vlc_tabs
[i
], 1);
190 ivi_blk_vlc_tabs
[i
].table
= table_data
+ (i
* 2 + 1) * 8192;
191 ivi_blk_vlc_tabs
[i
].table_allocated
= 8192;
192 ivi_create_huff_from_desc(&ivi_blk_huff_desc
[i
],
193 &ivi_blk_vlc_tabs
[i
], 1);
195 initialized_vlcs
= 1;
199 * Copy huffman codebook descriptors.
201 * @param[out] dst ptr to the destination descriptor
202 * @param[in] src ptr to the source descriptor
204 static void ivi_huff_desc_copy(IVIHuffDesc
*dst
, const IVIHuffDesc
*src
)
206 dst
->num_rows
= src
->num_rows
;
207 memcpy(dst
->xbits
, src
->xbits
, src
->num_rows
);
211 * Compare two huffman codebook descriptors.
213 * @param[in] desc1 ptr to the 1st descriptor to compare
214 * @param[in] desc2 ptr to the 2nd descriptor to compare
215 * @return comparison result: 0 - equal, 1 - not equal
217 static int ivi_huff_desc_cmp(const IVIHuffDesc
*desc1
,
218 const IVIHuffDesc
*desc2
)
220 return desc1
->num_rows
!= desc2
->num_rows
||
221 memcmp(desc1
->xbits
, desc2
->xbits
, desc1
->num_rows
);
224 int ff_ivi_dec_huff_desc(GetBitContext
*gb
, int desc_coded
, int which_tab
,
225 IVIHuffTab
*huff_tab
, AVCodecContext
*avctx
)
228 IVIHuffDesc new_huff
;
231 /* select default table */
232 huff_tab
->tab
= (which_tab
) ? &ivi_blk_vlc_tabs
[7]
233 : &ivi_mb_vlc_tabs
[7];
237 huff_tab
->tab_sel
= get_bits(gb
, 3);
238 if (huff_tab
->tab_sel
== 7) {
239 /* custom huffman table (explicitly encoded) */
240 new_huff
.num_rows
= get_bits(gb
, 4);
241 if (!new_huff
.num_rows
) {
242 av_log(avctx
, AV_LOG_ERROR
, "Empty custom Huffman table!\n");
243 return AVERROR_INVALIDDATA
;
246 for (i
= 0; i
< new_huff
.num_rows
; i
++)
247 new_huff
.xbits
[i
] = get_bits(gb
, 4);
249 /* Have we got the same custom table? Rebuild if not. */
250 if (ivi_huff_desc_cmp(&new_huff
, &huff_tab
->cust_desc
) || !huff_tab
->cust_tab
.table
) {
251 ivi_huff_desc_copy(&huff_tab
->cust_desc
, &new_huff
);
253 if (huff_tab
->cust_tab
.table
)
254 ff_free_vlc(&huff_tab
->cust_tab
);
255 result
= ivi_create_huff_from_desc(&huff_tab
->cust_desc
,
256 &huff_tab
->cust_tab
, 0);
258 // reset faulty description
259 huff_tab
->cust_desc
.num_rows
= 0;
260 av_log(avctx
, AV_LOG_ERROR
,
261 "Error while initializing custom vlc table!\n");
265 huff_tab
->tab
= &huff_tab
->cust_tab
;
267 /* select one of predefined tables */
268 huff_tab
->tab
= (which_tab
) ? &ivi_blk_vlc_tabs
[huff_tab
->tab_sel
]
269 : &ivi_mb_vlc_tabs
[huff_tab
->tab_sel
];
276 * Free planes, bands and macroblocks buffers.
278 * @param[in] planes pointer to the array of the plane descriptors
280 static av_cold
void ivi_free_buffers(IVIPlaneDesc
*planes
)
284 for (p
= 0; p
< 3; p
++) {
286 for (b
= 0; b
< planes
[p
].num_bands
; b
++) {
287 av_freep(&planes
[p
].bands
[b
].bufs
[0]);
288 av_freep(&planes
[p
].bands
[b
].bufs
[1]);
289 av_freep(&planes
[p
].bands
[b
].bufs
[2]);
290 av_freep(&planes
[p
].bands
[b
].bufs
[3]);
292 if (planes
[p
].bands
[b
].blk_vlc
.cust_tab
.table
)
293 ff_free_vlc(&planes
[p
].bands
[b
].blk_vlc
.cust_tab
);
294 for (t
= 0; t
< planes
[p
].bands
[b
].num_tiles
; t
++)
295 av_freep(&planes
[p
].bands
[b
].tiles
[t
].mbs
);
296 av_freep(&planes
[p
].bands
[b
].tiles
);
298 av_freep(&planes
[p
].bands
);
299 planes
[p
].num_bands
= 0;
303 av_cold
int ff_ivi_init_planes(IVIPlaneDesc
*planes
, const IVIPicConfig
*cfg
,
307 uint32_t b_width
, b_height
, align_fac
, width_aligned
,
308 height_aligned
, buf_size
;
311 ivi_free_buffers(planes
);
313 if (cfg
->pic_width
< 1 || cfg
->pic_height
< 1 ||
314 cfg
->luma_bands
< 1 || cfg
->chroma_bands
< 1)
315 return AVERROR_INVALIDDATA
;
317 /* fill in the descriptor of the luminance plane */
318 planes
[0].width
= cfg
->pic_width
;
319 planes
[0].height
= cfg
->pic_height
;
320 planes
[0].num_bands
= cfg
->luma_bands
;
322 /* fill in the descriptors of the chrominance planes */
323 planes
[1].width
= planes
[2].width
= (cfg
->pic_width
+ 3) >> 2;
324 planes
[1].height
= planes
[2].height
= (cfg
->pic_height
+ 3) >> 2;
325 planes
[1].num_bands
= planes
[2].num_bands
= cfg
->chroma_bands
;
327 for (p
= 0; p
< 3; p
++) {
328 planes
[p
].bands
= av_mallocz_array(planes
[p
].num_bands
, sizeof(IVIBandDesc
));
329 if (!planes
[p
].bands
)
330 return AVERROR(ENOMEM
);
332 /* select band dimensions: if there is only one band then it
333 * has the full size, if there are several bands each of them
334 * has only half size */
335 b_width
= planes
[p
].num_bands
== 1 ? planes
[p
].width
336 : (planes
[p
].width
+ 1) >> 1;
337 b_height
= planes
[p
].num_bands
== 1 ? planes
[p
].height
338 : (planes
[p
].height
+ 1) >> 1;
340 /* luma band buffers will be aligned on 16x16 (max macroblock size) */
341 /* chroma band buffers will be aligned on 8x8 (max macroblock size) */
342 align_fac
= p
? 8 : 16;
343 width_aligned
= FFALIGN(b_width
, align_fac
);
344 height_aligned
= FFALIGN(b_height
, align_fac
);
345 buf_size
= width_aligned
* height_aligned
* sizeof(int16_t);
347 for (b
= 0; b
< planes
[p
].num_bands
; b
++) {
348 band
= &planes
[p
].bands
[b
]; /* select appropriate plane/band */
351 band
->width
= b_width
;
352 band
->height
= b_height
;
353 band
->pitch
= width_aligned
;
354 band
->aheight
= height_aligned
;
355 band
->bufs
[0] = av_mallocz(buf_size
);
356 band
->bufs
[1] = av_mallocz(buf_size
);
357 band
->bufsize
= buf_size
/2;
358 if (!band
->bufs
[0] || !band
->bufs
[1])
359 return AVERROR(ENOMEM
);
361 /* allocate the 3rd band buffer for scalability mode */
362 if (cfg
->luma_bands
> 1) {
363 band
->bufs
[2] = av_mallocz(buf_size
);
365 return AVERROR(ENOMEM
);
368 band
->bufs
[3] = av_mallocz(buf_size
);
370 return AVERROR(ENOMEM
);
372 /* reset custom vlc */
373 planes
[p
].bands
[0].blk_vlc
.cust_desc
.num_rows
= 0;
380 static int ivi_init_tiles(IVIBandDesc
*band
, IVITile
*ref_tile
,
381 int p
, int b
, int t_height
, int t_width
)
384 IVITile
*tile
= band
->tiles
;
386 for (y
= 0; y
< band
->height
; y
+= t_height
) {
387 for (x
= 0; x
< band
->width
; x
+= t_width
) {
390 tile
->mb_size
= band
->mb_size
;
391 tile
->width
= FFMIN(band
->width
- x
, t_width
);
392 tile
->height
= FFMIN(band
->height
- y
, t_height
);
393 tile
->is_empty
= tile
->data_size
= 0;
394 /* calculate number of macroblocks */
395 tile
->num_MBs
= IVI_MBs_PER_TILE(tile
->width
, tile
->height
,
398 av_freep(&tile
->mbs
);
399 tile
->mbs
= av_mallocz_array(tile
->num_MBs
, sizeof(IVIMbInfo
));
401 return AVERROR(ENOMEM
);
405 if (tile
->num_MBs
!= ref_tile
->num_MBs
) {
406 av_log(NULL
, AV_LOG_DEBUG
, "ref_tile mismatch\n");
407 return AVERROR_INVALIDDATA
;
409 tile
->ref_mbs
= ref_tile
->mbs
;
419 av_cold
int ff_ivi_init_tiles(IVIPlaneDesc
*planes
,
420 int tile_width
, int tile_height
)
422 int p
, b
, x_tiles
, y_tiles
, t_width
, t_height
, ret
;
425 for (p
= 0; p
< 3; p
++) {
426 t_width
= !p
? tile_width
: (tile_width
+ 3) >> 2;
427 t_height
= !p
? tile_height
: (tile_height
+ 3) >> 2;
429 if (!p
&& planes
[0].num_bands
== 4) {
433 if(t_width
<=0 || t_height
<=0)
434 return AVERROR(EINVAL
);
436 for (b
= 0; b
< planes
[p
].num_bands
; b
++) {
437 band
= &planes
[p
].bands
[b
];
438 x_tiles
= IVI_NUM_TILES(band
->width
, t_width
);
439 y_tiles
= IVI_NUM_TILES(band
->height
, t_height
);
440 band
->num_tiles
= x_tiles
* y_tiles
;
442 av_freep(&band
->tiles
);
443 band
->tiles
= av_mallocz_array(band
->num_tiles
, sizeof(IVITile
));
445 return AVERROR(ENOMEM
);
447 /* use the first luma band as reference for motion vectors
449 ret
= ivi_init_tiles(band
, planes
[0].bands
[0].tiles
,
450 p
, b
, t_height
, t_width
);
460 * Decode size of the tile data.
461 * The size is stored as a variable-length field having the following format:
462 * if (tile_data_size < 255) than this field is only one byte long
463 * if (tile_data_size >= 255) than this field four is byte long: 0xFF X1 X2 X3
464 * where X1-X3 is size of the tile data
466 * @param[in,out] gb the GetBit context
467 * @return size of the tile data in bytes
469 static int ivi_dec_tile_data_size(GetBitContext
*gb
)
475 len
= get_bits(gb
, 8);
477 len
= get_bits_long(gb
, 24);
480 /* align the bitstream reader on the byte boundary */
486 static int ivi_dc_transform(IVIBandDesc
*band
, int *prev_dc
, int buf_offs
,
489 int buf_size
= band
->pitch
* band
->aheight
- buf_offs
;
490 int min_size
= (blk_size
- 1) * band
->pitch
+ blk_size
;
492 if (min_size
> buf_size
)
493 return AVERROR_INVALIDDATA
;
495 band
->dc_transform(prev_dc
, band
->buf
+ buf_offs
,
496 band
->pitch
, blk_size
);
501 static int ivi_decode_coded_blocks(GetBitContext
*gb
, IVIBandDesc
*band
,
502 ivi_mc_func mc
, ivi_mc_avg_func mc_avg
,
504 int mv_x2
, int mv_y2
,
505 int *prev_dc
, int is_intra
,
506 int mc_type
, int mc_type2
,
507 uint32_t quant
, int offs
,
508 AVCodecContext
*avctx
)
510 const uint16_t *base_tab
= is_intra
? band
->intra_base
: band
->inter_base
;
511 RVMapDesc
*rvmap
= band
->rv_map
;
512 uint8_t col_flags
[8];
514 uint32_t sym
= 0, lo
, hi
, q
;
516 int blk_size
= band
->blk_size
;
517 int num_coeffs
= blk_size
* blk_size
;
518 int col_mask
= blk_size
- 1;
520 int min_size
= band
->pitch
* (band
->transform_size
- 1) +
521 band
->transform_size
;
522 int buf_size
= band
->pitch
* band
->aheight
- offs
;
524 if (min_size
> buf_size
)
525 return AVERROR_INVALIDDATA
;
528 av_log(avctx
, AV_LOG_ERROR
, "Scan pattern is not set.\n");
529 return AVERROR_INVALIDDATA
;
532 /* zero transform vector */
533 memset(trvec
, 0, num_coeffs
* sizeof(trvec
[0]));
534 /* zero column flags */
535 memset(col_flags
, 0, sizeof(col_flags
));
536 while (scan_pos
<= num_coeffs
) {
537 sym
= get_vlc2(gb
, band
->blk_vlc
.tab
->table
,
539 if (sym
== rvmap
->eob_sym
)
540 break; /* End of block */
542 /* Escape - run/val explicitly coded using 3 vlc codes */
543 if (sym
== rvmap
->esc_sym
) {
544 run
= get_vlc2(gb
, band
->blk_vlc
.tab
->table
, IVI_VLC_BITS
, 1) + 1;
545 lo
= get_vlc2(gb
, band
->blk_vlc
.tab
->table
, IVI_VLC_BITS
, 1);
546 hi
= get_vlc2(gb
, band
->blk_vlc
.tab
->table
, IVI_VLC_BITS
, 1);
547 /* merge them and convert into signed val */
548 val
= IVI_TOSIGNED((hi
<< 6) | lo
);
551 av_log(avctx
, AV_LOG_ERROR
, "Invalid sym encountered: %"PRIu32
".\n", sym
);
552 return AVERROR_INVALIDDATA
;
554 run
= rvmap
->runtab
[sym
];
555 val
= rvmap
->valtab
[sym
];
558 /* de-zigzag and dequantize */
560 if (scan_pos
>= num_coeffs
|| scan_pos
< 0)
562 pos
= band
->scan
[scan_pos
];
565 av_dlog(avctx
, "Val = 0 encountered!\n");
567 q
= (base_tab
[pos
] * quant
) >> 9;
569 val
= val
* q
+ FFSIGN(val
) * (((q
^ 1) - 1) >> 1);
571 /* track columns containing non-zero coeffs */
572 col_flags
[pos
& col_mask
] |= !!val
;
575 if (scan_pos
< 0 || scan_pos
>= num_coeffs
&& sym
!= rvmap
->eob_sym
)
576 return AVERROR_INVALIDDATA
; /* corrupt block data */
578 /* undoing DC coeff prediction for intra-blocks */
579 if (is_intra
&& band
->is_2d_trans
) {
580 *prev_dc
+= trvec
[0];
582 col_flags
[0] |= !!*prev_dc
;
585 if(band
->transform_size
> band
->blk_size
){
586 av_log(NULL
, AV_LOG_ERROR
, "Too large transform\n");
587 return AVERROR_INVALIDDATA
;
590 /* apply inverse transform */
591 band
->inv_transform(trvec
, band
->buf
+ offs
,
592 band
->pitch
, col_flags
);
594 /* apply motion compensation */
596 return ivi_mc(band
, mc
, mc_avg
, offs
, mv_x
, mv_y
, mv_x2
, mv_y2
,
603 * extract huffman-coded transform coefficients from the bitstream,
604 * dequantize them, apply inverse transform and motion compensation
605 * in order to reconstruct the picture.
607 * @param[in,out] gb the GetBit context
608 * @param[in] band pointer to the band descriptor
609 * @param[in] tile pointer to the tile descriptor
610 * @return result code: 0 - OK, -1 = error (corrupted blocks data)
612 static int ivi_decode_blocks(GetBitContext
*gb
, IVIBandDesc
*band
,
613 IVITile
*tile
, AVCodecContext
*avctx
)
615 int mbn
, blk
, num_blocks
, blk_size
, ret
, is_intra
;
616 int mc_type
= 0, mc_type2
= -1;
617 int mv_x
= 0, mv_y
= 0, mv_x2
= 0, mv_y2
= 0;
619 uint32_t cbp
, quant
, buf_offs
;
621 ivi_mc_func mc_with_delta_func
, mc_no_delta_func
;
622 ivi_mc_avg_func mc_avg_with_delta_func
, mc_avg_no_delta_func
;
623 const uint8_t *scale_tab
;
625 /* init intra prediction for the DC coefficient */
627 blk_size
= band
->blk_size
;
628 /* number of blocks per mb */
629 num_blocks
= (band
->mb_size
!= blk_size
) ? 4 : 1;
631 mc_with_delta_func
= ff_ivi_mc_8x8_delta
;
632 mc_no_delta_func
= ff_ivi_mc_8x8_no_delta
;
633 mc_avg_with_delta_func
= ff_ivi_mc_avg_8x8_delta
;
634 mc_avg_no_delta_func
= ff_ivi_mc_avg_8x8_no_delta
;
636 mc_with_delta_func
= ff_ivi_mc_4x4_delta
;
637 mc_no_delta_func
= ff_ivi_mc_4x4_no_delta
;
638 mc_avg_with_delta_func
= ff_ivi_mc_avg_4x4_delta
;
639 mc_avg_no_delta_func
= ff_ivi_mc_avg_4x4_no_delta
;
642 for (mbn
= 0, mb
= tile
->mbs
; mbn
< tile
->num_MBs
; mb
++, mbn
++) {
643 is_intra
= !mb
->type
;
645 buf_offs
= mb
->buf_offs
;
647 quant
= band
->glob_quant
+ mb
->q_delta
;
648 if (avctx
->codec_id
== AV_CODEC_ID_INDEO4
)
649 quant
= av_clip(quant
, 0, 31);
651 quant
= av_clip(quant
, 0, 23);
653 scale_tab
= is_intra
? band
->intra_scale
: band
->inter_scale
;
655 quant
= scale_tab
[quant
];
662 if (band
->is_halfpel
) {
663 mc_type
= ((mv_y
& 1) << 1) | (mv_x
& 1);
664 mc_type2
= ((mv_y2
& 1) << 1) | (mv_x2
& 1);
668 mv_y2
>>= 1; /* convert halfpel vectors into fullpel ones */
672 if (mb
->type
!= 2 && mb
->type
!= 3)
675 int dmv_x
, dmv_y
, cx
, cy
;
677 dmv_x
= mb
->mv_x
>> band
->is_halfpel
;
678 dmv_y
= mb
->mv_y
>> band
->is_halfpel
;
679 cx
= mb
->mv_x
& band
->is_halfpel
;
680 cy
= mb
->mv_y
& band
->is_halfpel
;
682 if (mb
->xpos
+ dmv_x
< 0 ||
683 mb
->xpos
+ dmv_x
+ band
->mb_size
+ cx
> band
->pitch
||
684 mb
->ypos
+ dmv_y
< 0 ||
685 mb
->ypos
+ dmv_y
+ band
->mb_size
+ cy
> band
->aheight
) {
686 return AVERROR_INVALIDDATA
;
689 if (mb
->type
== 2 || mb
->type
== 3) {
690 int dmv_x
, dmv_y
, cx
, cy
;
692 dmv_x
= mb
->b_mv_x
>> band
->is_halfpel
;
693 dmv_y
= mb
->b_mv_y
>> band
->is_halfpel
;
694 cx
= mb
->b_mv_x
& band
->is_halfpel
;
695 cy
= mb
->b_mv_y
& band
->is_halfpel
;
697 if (mb
->xpos
+ dmv_x
< 0 ||
698 mb
->xpos
+ dmv_x
+ band
->mb_size
+ cx
> band
->pitch
||
699 mb
->ypos
+ dmv_y
< 0 ||
700 mb
->ypos
+ dmv_y
+ band
->mb_size
+ cy
> band
->aheight
) {
701 return AVERROR_INVALIDDATA
;
706 for (blk
= 0; blk
< num_blocks
; blk
++) {
707 /* adjust block position in the buffer according to its number */
709 buf_offs
+= blk_size
;
710 } else if (blk
== 2) {
711 buf_offs
-= blk_size
;
712 buf_offs
+= blk_size
* band
->pitch
;
715 if (cbp
& 1) { /* block coded ? */
716 ret
= ivi_decode_coded_blocks(gb
, band
, mc_with_delta_func
,
717 mc_avg_with_delta_func
,
718 mv_x
, mv_y
, mv_x2
, mv_y2
,
720 mc_type
, mc_type2
, quant
,
725 /* block not coded */
726 /* for intra blocks apply the dc slant transform */
727 /* for inter - perform the motion compensation without delta */
729 ret
= ivi_dc_transform(band
, &prev_dc
, buf_offs
, blk_size
);
733 ret
= ivi_mc(band
, mc_no_delta_func
, mc_avg_no_delta_func
,
734 buf_offs
, mv_x
, mv_y
, mv_x2
, mv_y2
,
751 * Handle empty tiles by performing data copying and motion
752 * compensation respectively.
754 * @param[in] avctx ptr to the AVCodecContext
755 * @param[in] band pointer to the band descriptor
756 * @param[in] tile pointer to the tile descriptor
757 * @param[in] mv_scale scaling factor for motion vectors
759 static int ivi_process_empty_tile(AVCodecContext
*avctx
, IVIBandDesc
*band
,
760 IVITile
*tile
, int32_t mv_scale
)
762 int x
, y
, need_mc
, mbn
, blk
, num_blocks
, mv_x
, mv_y
, mc_type
;
763 int offs
, mb_offset
, row_offset
, ret
;
764 IVIMbInfo
*mb
, *ref_mb
;
767 ivi_mc_func mc_no_delta_func
;
769 if (tile
->num_MBs
!= IVI_MBs_PER_TILE(tile
->width
, tile
->height
, band
->mb_size
)) {
770 av_log(avctx
, AV_LOG_ERROR
, "Allocated tile size %d mismatches "
771 "parameters %d in ivi_process_empty_tile()\n",
772 tile
->num_MBs
, IVI_MBs_PER_TILE(tile
->width
, tile
->height
, band
->mb_size
));
773 return AVERROR_INVALIDDATA
;
776 offs
= tile
->ypos
* band
->pitch
+ tile
->xpos
;
778 ref_mb
= tile
->ref_mbs
;
779 row_offset
= band
->mb_size
* band
->pitch
;
780 need_mc
= 0; /* reset the mc tracking flag */
782 for (y
= tile
->ypos
; y
< (tile
->ypos
+ tile
->height
); y
+= band
->mb_size
) {
785 for (x
= tile
->xpos
; x
< (tile
->xpos
+ tile
->width
); x
+= band
->mb_size
) {
788 mb
->buf_offs
= mb_offset
;
790 mb
->type
= 1; /* set the macroblocks type = INTER */
791 mb
->cbp
= 0; /* all blocks are empty */
793 if (!band
->qdelta_present
&& !band
->plane
&& !band
->band_num
) {
794 mb
->q_delta
= band
->glob_quant
;
799 if (band
->inherit_qdelta
&& ref_mb
)
800 mb
->q_delta
= ref_mb
->q_delta
;
802 if (band
->inherit_mv
&& ref_mb
) {
803 /* motion vector inheritance */
805 mb
->mv_x
= ivi_scale_mv(ref_mb
->mv_x
, mv_scale
);
806 mb
->mv_y
= ivi_scale_mv(ref_mb
->mv_y
, mv_scale
);
808 mb
->mv_x
= ref_mb
->mv_x
;
809 mb
->mv_y
= ref_mb
->mv_y
;
811 need_mc
|= mb
->mv_x
|| mb
->mv_y
; /* tracking non-zero motion vectors */
813 int dmv_x
, dmv_y
, cx
, cy
;
815 dmv_x
= mb
->mv_x
>> band
->is_halfpel
;
816 dmv_y
= mb
->mv_y
>> band
->is_halfpel
;
817 cx
= mb
->mv_x
& band
->is_halfpel
;
818 cy
= mb
->mv_y
& band
->is_halfpel
;
820 if ( mb
->xpos
+ dmv_x
< 0
821 || mb
->xpos
+ dmv_x
+ band
->mb_size
+ cx
> band
->pitch
822 || mb
->ypos
+ dmv_y
< 0
823 || mb
->ypos
+ dmv_y
+ band
->mb_size
+ cy
> band
->aheight
) {
824 av_log(avctx
, AV_LOG_ERROR
, "MV out of bounds\n");
825 return AVERROR_INVALIDDATA
;
833 mb_offset
+= band
->mb_size
;
838 if (band
->inherit_mv
&& need_mc
) { /* apply motion compensation if there is at least one non-zero motion vector */
839 num_blocks
= (band
->mb_size
!= band
->blk_size
) ? 4 : 1; /* number of blocks per mb */
840 mc_no_delta_func
= (band
->blk_size
== 8) ? ff_ivi_mc_8x8_no_delta
841 : ff_ivi_mc_4x4_no_delta
;
843 for (mbn
= 0, mb
= tile
->mbs
; mbn
< tile
->num_MBs
; mb
++, mbn
++) {
846 if (!band
->is_halfpel
) {
847 mc_type
= 0; /* we have only fullpel vectors */
849 mc_type
= ((mv_y
& 1) << 1) | (mv_x
& 1);
851 mv_y
>>= 1; /* convert halfpel vectors into fullpel ones */
854 for (blk
= 0; blk
< num_blocks
; blk
++) {
855 /* adjust block position in the buffer according with its number */
856 offs
= mb
->buf_offs
+ band
->blk_size
* ((blk
& 1) + !!(blk
& 2) * band
->pitch
);
857 ret
= ivi_mc(band
, mc_no_delta_func
, 0, offs
,
858 mv_x
, mv_y
, 0, 0, mc_type
, -1);
864 /* copy data from the reference tile into the current one */
865 src
= band
->ref_buf
+ tile
->ypos
* band
->pitch
+ tile
->xpos
;
866 dst
= band
->buf
+ tile
->ypos
* band
->pitch
+ tile
->xpos
;
867 for (y
= 0; y
< tile
->height
; y
++) {
868 memcpy(dst
, src
, tile
->width
*sizeof(band
->buf
[0]));
879 static uint16_t ivi_calc_band_checksum(IVIBandDesc
*band
)
882 int16_t *src
, checksum
;
887 for (y
= 0; y
< band
->height
; src
+= band
->pitch
, y
++)
888 for (x
= 0; x
< band
->width
; x
++)
896 * Convert and output the current plane.
897 * This conversion is done by adding back the bias value of 128
898 * (subtracted in the encoder) and clipping the result.
900 * @param[in] plane pointer to the descriptor of the plane being processed
901 * @param[out] dst pointer to the buffer receiving converted pixels
902 * @param[in] dst_pitch pitch for moving to the next y line
904 static void ivi_output_plane(IVIPlaneDesc
*plane
, uint8_t *dst
, int dst_pitch
)
907 const int16_t *src
= plane
->bands
[0].buf
;
908 uint32_t pitch
= plane
->bands
[0].pitch
;
913 for (y
= 0; y
< plane
->height
; y
++) {
914 for (x
= 0; x
< plane
->width
; x
++)
915 dst
[x
] = av_clip_uint8(src
[x
] + 128);
922 * Decode an Indeo 4 or 5 band.
924 * @param[in,out] ctx ptr to the decoder context
925 * @param[in,out] band ptr to the band descriptor
926 * @param[in] avctx ptr to the AVCodecContext
927 * @return result code: 0 = OK, -1 = error
929 static int decode_band(IVI45DecContext
*ctx
,
930 IVIBandDesc
*band
, AVCodecContext
*avctx
)
932 int result
, i
, t
, idx1
, idx2
, pos
;
935 band
->buf
= band
->bufs
[ctx
->dst_buf
];
937 av_log(avctx
, AV_LOG_ERROR
, "Band buffer points to no data!\n");
938 return AVERROR_INVALIDDATA
;
940 if (ctx
->is_indeo4
&& ctx
->frame_type
== IVI4_FRAMETYPE_BIDIR
) {
941 band
->ref_buf
= band
->bufs
[ctx
->b_ref_buf
];
942 band
->b_ref_buf
= band
->bufs
[ctx
->ref_buf
];
944 band
->ref_buf
= band
->bufs
[ctx
->ref_buf
];
947 band
->data_ptr
= ctx
->frame_data
+ (get_bits_count(&ctx
->gb
) >> 3);
949 result
= ctx
->decode_band_hdr(ctx
, band
, avctx
);
951 av_log(avctx
, AV_LOG_ERROR
, "Error while decoding band header: %d\n",
956 if (band
->is_empty
) {
957 av_log(avctx
, AV_LOG_ERROR
, "Empty band encountered!\n");
958 return AVERROR_INVALIDDATA
;
961 band
->rv_map
= &ctx
->rvmap_tabs
[band
->rvmap_sel
];
963 /* apply corrections to the selected rvmap table if present */
964 for (i
= 0; i
< band
->num_corr
; i
++) {
965 idx1
= band
->corr
[i
* 2];
966 idx2
= band
->corr
[i
* 2 + 1];
967 FFSWAP(uint8_t, band
->rv_map
->runtab
[idx1
], band
->rv_map
->runtab
[idx2
]);
968 FFSWAP(int16_t, band
->rv_map
->valtab
[idx1
], band
->rv_map
->valtab
[idx2
]);
969 if (idx1
== band
->rv_map
->eob_sym
|| idx2
== band
->rv_map
->eob_sym
)
970 band
->rv_map
->eob_sym
^= idx1
^ idx2
;
971 if (idx1
== band
->rv_map
->esc_sym
|| idx2
== band
->rv_map
->esc_sym
)
972 band
->rv_map
->esc_sym
^= idx1
^ idx2
;
975 pos
= get_bits_count(&ctx
->gb
);
977 for (t
= 0; t
< band
->num_tiles
; t
++) {
978 tile
= &band
->tiles
[t
];
980 if (tile
->mb_size
!= band
->mb_size
) {
981 av_log(avctx
, AV_LOG_ERROR
, "MB sizes mismatch: %d vs. %d\n",
982 band
->mb_size
, tile
->mb_size
);
983 return AVERROR_INVALIDDATA
;
985 tile
->is_empty
= get_bits1(&ctx
->gb
);
986 if (tile
->is_empty
) {
987 result
= ivi_process_empty_tile(avctx
, band
, tile
,
988 (ctx
->planes
[0].bands
[0].mb_size
>> 3) - (band
->mb_size
>> 3));
991 av_dlog(avctx
, "Empty tile encountered!\n");
993 tile
->data_size
= ivi_dec_tile_data_size(&ctx
->gb
);
994 if (!tile
->data_size
) {
995 av_log(avctx
, AV_LOG_ERROR
, "Tile data size is zero!\n");
996 result
= AVERROR_INVALIDDATA
;
1000 result
= ctx
->decode_mb_info(ctx
, band
, tile
, avctx
);
1004 result
= ivi_decode_blocks(&ctx
->gb
, band
, tile
, avctx
);
1006 av_log(avctx
, AV_LOG_ERROR
,
1007 "Corrupted tile data encountered!\n");
1011 if (((get_bits_count(&ctx
->gb
) - pos
) >> 3) != tile
->data_size
) {
1012 av_log(avctx
, AV_LOG_ERROR
,
1013 "Tile data_size mismatch!\n");
1014 result
= AVERROR_INVALIDDATA
;
1018 pos
+= tile
->data_size
<< 3; // skip to next tile
1022 /* restore the selected rvmap table by applying its corrections in
1024 for (i
= band
->num_corr
-1; i
>= 0; i
--) {
1025 idx1
= band
->corr
[i
*2];
1026 idx2
= band
->corr
[i
*2+1];
1027 FFSWAP(uint8_t, band
->rv_map
->runtab
[idx1
], band
->rv_map
->runtab
[idx2
]);
1028 FFSWAP(int16_t, band
->rv_map
->valtab
[idx1
], band
->rv_map
->valtab
[idx2
]);
1029 if (idx1
== band
->rv_map
->eob_sym
|| idx2
== band
->rv_map
->eob_sym
)
1030 band
->rv_map
->eob_sym
^= idx1
^ idx2
;
1031 if (idx1
== band
->rv_map
->esc_sym
|| idx2
== band
->rv_map
->esc_sym
)
1032 band
->rv_map
->esc_sym
^= idx1
^ idx2
;
1036 if (band
->checksum_present
) {
1037 uint16_t chksum
= ivi_calc_band_checksum(band
);
1038 if (chksum
!= band
->checksum
) {
1039 av_log(avctx
, AV_LOG_ERROR
,
1040 "Band checksum mismatch! Plane %d, band %d, "
1041 "received: %"PRIx32
", calculated: %"PRIx16
"\n",
1042 band
->plane
, band
->band_num
, band
->checksum
, chksum
);
1047 align_get_bits(&ctx
->gb
);
1052 int ff_ivi_decode_frame(AVCodecContext
*avctx
, void *data
, int *got_frame
,
1055 IVI45DecContext
*ctx
= avctx
->priv_data
;
1056 const uint8_t *buf
= avpkt
->data
;
1057 AVFrame
*frame
= data
;
1058 int buf_size
= avpkt
->size
;
1061 init_get_bits(&ctx
->gb
, buf
, buf_size
* 8);
1062 ctx
->frame_data
= buf
;
1063 ctx
->frame_size
= buf_size
;
1065 result
= ctx
->decode_pic_hdr(ctx
, avctx
);
1067 av_log(avctx
, AV_LOG_ERROR
,
1068 "Error while decoding picture header: %d\n", result
);
1071 if (ctx
->gop_invalid
)
1072 return AVERROR_INVALIDDATA
;
1074 if (ctx
->is_indeo4
&& ctx
->frame_type
== IVI4_FRAMETYPE_NULL_LAST
) {
1075 if (ctx
->got_p_frame
) {
1076 av_frame_move_ref(data
, ctx
->p_frame
);
1078 ctx
->got_p_frame
= 0;
1085 if (ctx
->gop_flags
& IVI5_IS_PROTECTED
) {
1086 avpriv_report_missing_feature(avctx
, "Password-protected clip!\n");
1087 return AVERROR_PATCHWELCOME
;
1090 if (!ctx
->planes
[0].bands
) {
1091 av_log(avctx
, AV_LOG_ERROR
, "Color planes not initialized yet\n");
1092 return AVERROR_INVALIDDATA
;
1095 ctx
->switch_buffers(ctx
);
1099 if (ctx
->is_nonnull_frame(ctx
)) {
1100 ctx
->buf_invalid
[ctx
->dst_buf
] = 1;
1101 for (p
= 0; p
< 3; p
++) {
1102 for (b
= 0; b
< ctx
->planes
[p
].num_bands
; b
++) {
1103 result
= decode_band(ctx
, &ctx
->planes
[p
].bands
[b
], avctx
);
1105 av_log(avctx
, AV_LOG_ERROR
,
1106 "Error while decoding band: %d, plane: %d\n", b
, p
);
1111 ctx
->buf_invalid
[ctx
->dst_buf
] = 0;
1113 if (ctx
->is_scalable
)
1114 return AVERROR_INVALIDDATA
;
1116 for (p
= 0; p
< 3; p
++) {
1117 if (!ctx
->planes
[p
].bands
[0].buf
)
1118 return AVERROR_INVALIDDATA
;
1121 if (ctx
->buf_invalid
[ctx
->dst_buf
])
1124 //STOP_TIMER("decode_planes"); }
1126 if (!ctx
->is_nonnull_frame(ctx
))
1129 result
= ff_set_dimensions(avctx
, ctx
->planes
[0].width
, ctx
->planes
[0].height
);
1133 if ((result
= ff_get_buffer(avctx
, frame
, 0)) < 0)
1136 if (ctx
->is_scalable
) {
1138 ff_ivi_recompose_haar(&ctx
->planes
[0], frame
->data
[0], frame
->linesize
[0]);
1140 ff_ivi_recompose53 (&ctx
->planes
[0], frame
->data
[0], frame
->linesize
[0]);
1142 ivi_output_plane(&ctx
->planes
[0], frame
->data
[0], frame
->linesize
[0]);
1145 ivi_output_plane(&ctx
->planes
[2], frame
->data
[1], frame
->linesize
[1]);
1146 ivi_output_plane(&ctx
->planes
[1], frame
->data
[2], frame
->linesize
[2]);
1150 /* If the bidirectional mode is enabled, next I and the following P
1151 * frame will be sent together. Unfortunately the approach below seems
1152 * to be the only way to handle the B-frames mode.
1153 * That's exactly the same Intel decoders do.
1155 if (ctx
->is_indeo4
&& ctx
->frame_type
== IVI4_FRAMETYPE_INTRA
) {
1158 // skip version string
1159 while (get_bits(&ctx
->gb
, 8)) {
1160 if (get_bits_left(&ctx
->gb
) < 8)
1161 return AVERROR_INVALIDDATA
;
1163 left
= get_bits_count(&ctx
->gb
) & 0x18;
1164 skip_bits_long(&ctx
->gb
, 64 - left
);
1165 if (get_bits_left(&ctx
->gb
) > 18 &&
1166 show_bits_long(&ctx
->gb
, 21) == 0xBFFF8) { // syncheader + inter type
1168 pkt
.data
= avpkt
->data
+ (get_bits_count(&ctx
->gb
) >> 3);
1169 pkt
.size
= get_bits_left(&ctx
->gb
) >> 3;
1170 ff_ivi_decode_frame(avctx
, ctx
->p_frame
, &ctx
->got_p_frame
, &pkt
);
1178 * Close Indeo5 decoder and clean up its context.
1180 av_cold
int ff_ivi_decode_close(AVCodecContext
*avctx
)
1182 IVI45DecContext
*ctx
= avctx
->priv_data
;
1184 ivi_free_buffers(&ctx
->planes
[0]);
1186 if (ctx
->mb_vlc
.cust_tab
.table
)
1187 ff_free_vlc(&ctx
->mb_vlc
.cust_tab
);
1189 #if IVI4_STREAM_ANALYSER
1190 if (ctx
->is_indeo4
) {
1191 if (ctx
->is_scalable
)
1192 av_log(avctx
, AV_LOG_ERROR
, "This video uses scalability mode!\n");
1193 if (ctx
->uses_tiling
)
1194 av_log(avctx
, AV_LOG_ERROR
, "This video uses local decoding!\n");
1195 if (ctx
->has_b_frames
)
1196 av_log(avctx
, AV_LOG_ERROR
, "This video contains B-frames!\n");
1197 if (ctx
->has_transp
)
1198 av_log(avctx
, AV_LOG_ERROR
, "Transparency mode is enabled!\n");
1200 av_log(avctx
, AV_LOG_ERROR
, "This video uses Haar transform!\n");
1201 if (ctx
->uses_fullpel
)
1202 av_log(avctx
, AV_LOG_ERROR
, "This video uses fullpel motion vectors!\n");
1206 av_frame_free(&ctx
->p_frame
);
1213 * Scan patterns shared between indeo4 and indeo5
1215 const uint8_t ff_ivi_vertical_scan_8x8
[64] = {
1216 0, 8, 16, 24, 32, 40, 48, 56,
1217 1, 9, 17, 25, 33, 41, 49, 57,
1218 2, 10, 18, 26, 34, 42, 50, 58,
1219 3, 11, 19, 27, 35, 43, 51, 59,
1220 4, 12, 20, 28, 36, 44, 52, 60,
1221 5, 13, 21, 29, 37, 45, 53, 61,
1222 6, 14, 22, 30, 38, 46, 54, 62,
1223 7, 15, 23, 31, 39, 47, 55, 63
1226 const uint8_t ff_ivi_horizontal_scan_8x8
[64] = {
1227 0, 1, 2, 3, 4, 5, 6, 7,
1228 8, 9, 10, 11, 12, 13, 14, 15,
1229 16, 17, 18, 19, 20, 21, 22, 23,
1230 24, 25, 26, 27, 28, 29, 30, 31,
1231 32, 33, 34, 35, 36, 37, 38, 39,
1232 40, 41, 42, 43, 44, 45, 46, 47,
1233 48, 49, 50, 51, 52, 53, 54, 55,
1234 56, 57, 58, 59, 60, 61, 62, 63
1237 const uint8_t ff_ivi_direct_scan_4x4
[16] = {
1238 0, 1, 4, 8, 5, 2, 3, 6, 9, 12, 13, 10, 7, 11, 14, 15
1243 * Run-value (RLE) tables.
1245 const RVMapDesc ff_ivi_rvmap_tabs
[9] = {
1250 {1, 1, 0, 1, 1, 0, 1, 1, 2, 2, 1, 1, 1, 1, 3, 3,
1251 1, 1, 2, 2, 1, 1, 4, 4, 1, 1, 1, 1, 2, 2, 5, 5,
1252 1, 1, 3, 3, 1, 1, 6, 6, 1, 2, 1, 2, 7, 7, 1, 1,
1253 8, 8, 1, 1, 4, 2, 1, 4, 2, 1, 3, 3, 1, 1, 1, 9,
1254 9, 1, 2, 1, 2, 1, 5, 5, 1, 1, 10, 10, 1, 1, 3, 3,
1255 2, 2, 1, 1, 11, 11, 6, 4, 4, 1, 6, 1, 2, 1, 2, 12,
1256 8, 1, 12, 7, 8, 7, 1, 16, 1, 16, 1, 3, 3, 13, 1, 13,
1257 2, 2, 1, 15, 1, 5, 14, 15, 1, 5, 14, 1, 17, 8, 17, 8,
1258 1, 4, 4, 2, 2, 1, 25, 25, 24, 24, 1, 3, 1, 3, 1, 8,
1259 6, 7, 6, 1, 18, 8, 18, 1, 7, 23, 2, 2, 23, 1, 1, 21,
1260 22, 9, 9, 22, 19, 1, 21, 5, 19, 5, 1, 33, 20, 33, 20, 8,
1261 4, 4, 1, 32, 2, 2, 8, 3, 32, 26, 3, 1, 7, 7, 26, 6,
1262 1, 6, 1, 1, 16, 1, 10, 1, 10, 2, 16, 29, 28, 2, 29, 28,
1263 1, 27, 5, 8, 5, 27, 1, 8, 3, 7, 3, 31, 41, 31, 1, 41,
1264 6, 1, 6, 7, 4, 4, 1, 1, 2, 1, 2, 11, 34, 30, 11, 1,
1265 30, 15, 15, 34, 36, 40, 36, 40, 35, 35, 37, 37, 39, 39, 38, 38},
1268 { 1, -1, 0, 2, -2, 0, 3, -3, 1, -1, 4, -4, 5, -5, 1, -1,
1269 6, -6, 2, -2, 7, -7, 1, -1, 8, -8, 9, -9, 3, -3, 1, -1,
1270 10, -10, 2, -2, 11, -11, 1, -1, 12, 4, -12, -4, 1, -1, 13, -13,
1271 1, -1, 14, -14, 2, 5, 15, -2, -5, -15, -3, 3, 16, -16, 17, 1,
1272 -1, -17, 6, 18, -6, -18, 2, -2, 19, -19, 1, -1, 20, -20, 4, -4,
1273 7, -7, 21, -21, 1, -1, 2, 3, -3, 22, -2, -22, 8, 23, -8, 1,
1274 2, -23, -1, 2, -2, -2, 24, 1, -24, -1, 25, 5, -5, 1, -25, -1,
1275 9, -9, 26, 1, -26, 3, 1, -1, 27, -3, -1, -27, 1, 3, -1, -3,
1276 28, -4, 4, 10, -10, -28, 1, -1, 1, -1, 29, 6, -29, -6, 30, -4,
1277 3, 3, -3, -30, 1, 4, -1, 31, -3, 1, 11, -11, -1, -31, 32, -1,
1278 -1, 2, -2, 1, 1, -32, 1, 4, -1, -4, 33, -1, 1, 1, -1, 5,
1279 5, -5, -33, -1, -12, 12, -5, -7, 1, 1, 7, 34, 4, -4, -1, 4,
1280 -34, -4, 35, 36, -2, -35, -2, -36, 2, 13, 2, -1, 1, -13, 1, -1,
1281 37, 1, -5, 6, 5, -1, 38, -6, -8, 5, 8, -1, 1, 1, -37, -1,
1282 5, 39, -5, -5, 6, -6, -38, -39, -14, 40, 14, 2, 1, 1, -2, -40,
1283 -1, -2, 2, -1, -1, -1, 1, 1, 1, -1, 1, -1, 1, -1, 1, -1}
1289 {0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 8, 6, 8, 7,
1290 7, 9, 9, 10, 10, 11, 11, 1, 12, 1, 12, 13, 13, 16, 14, 16,
1291 14, 15, 15, 17, 17, 18, 0, 18, 19, 20, 21, 19, 22, 21, 20, 22,
1292 25, 24, 2, 25, 24, 23, 23, 2, 26, 28, 26, 28, 29, 27, 29, 27,
1293 33, 33, 1, 32, 1, 3, 32, 30, 36, 3, 36, 30, 31, 31, 35, 34,
1294 37, 41, 34, 35, 37, 4, 41, 4, 49, 8, 8, 49, 40, 38, 5, 38,
1295 40, 39, 5, 39, 42, 43, 42, 7, 57, 6, 43, 44, 6, 50, 7, 44,
1296 57, 48, 50, 48, 45, 45, 46, 47, 51, 46, 47, 58, 1, 51, 58, 1,
1297 52, 59, 53, 9, 52, 55, 55, 59, 53, 56, 54, 56, 54, 9, 64, 64,
1298 60, 63, 60, 63, 61, 62, 61, 62, 2, 10, 2, 10, 11, 1, 11, 13,
1299 12, 1, 12, 13, 16, 16, 8, 8, 14, 3, 3, 15, 14, 15, 4, 4,
1300 1, 17, 17, 5, 1, 7, 7, 5, 6, 1, 2, 2, 6, 22, 1, 25,
1301 21, 22, 8, 24, 1, 21, 25, 24, 8, 18, 18, 23, 9, 20, 23, 33,
1302 29, 33, 20, 1, 19, 1, 29, 36, 9, 36, 19, 41, 28, 57, 32, 3,
1303 28, 3, 1, 27, 49, 49, 1, 32, 26, 26, 2, 4, 4, 7, 57, 41,
1304 2, 7, 10, 5, 37, 16, 10, 27, 8, 8, 13, 16, 37, 13, 1, 5},
1307 {0, 1, -1, 1, -1, 1, -1, 1, -1, 1, -1, 1, 1, -1, -1, 1,
1308 -1, 1, -1, 1, -1, 1, -1, 2, 1, -2, -1, 1, -1, 1, 1, -1,
1309 -1, 1, -1, 1, -1, 1, 0, -1, 1, 1, 1, -1, 1, -1, -1, -1,
1310 1, 1, 2, -1, -1, 1, -1, -2, 1, 1, -1, -1, 1, 1, -1, -1,
1311 1, -1, 3, 1, -3, 2, -1, 1, 1, -2, -1, -1, -1, 1, 1, 1,
1312 1, 1, -1, -1, -1, 2, -1, -2, 1, 2, -2, -1, 1, 1, 2, -1,
1313 -1, 1, -2, -1, 1, 1, -1, 2, 1, 2, -1, 1, -2, -1, -2, -1,
1314 -1, 1, 1, -1, 1, -1, 1, 1, 1, -1, -1, 1, 4, -1, -1, -4,
1315 1, 1, 1, 2, -1, -1, 1, -1, -1, 1, -1, -1, 1, -2, 1, -1,
1316 1, 1, -1, -1, 1, 1, -1, -1, 3, 2, -3, -2, 2, 5, -2, 2,
1317 2, -5, -2, -2, -2, 2, -3, 3, 2, 3, -3, 2, -2, -2, 3, -3,
1318 6, 2, -2, 3, -6, 3, -3, -3, 3, 7, -4, 4, -3, 2, -7, 2,
1319 2, -2, -4, 2, 8, -2, -2, -2, 4, 2, -2, 2, 3, 2, -2, -2,
1320 2, 2, -2, -8, -2, 9, -2, 2, -3, -2, 2, -2, 2, 2, 2, 4,
1321 -2, -4, 10, 2, 2, -2, -9, -2, 2, -2, 5, 4, -4, 4, -2, 2,
1322 -5, -4, -3, 4, 2, -3, 3, -2, -5, 5, 3, 3, -2, -3, -10, -4}
1328 {1, 1, 0, 2, 2, 1, 1, 3, 3, 4, 4, 0, 1, 1, 5, 5,
1329 2, 2, 6, 6, 7, 7, 1, 8, 1, 8, 3, 3, 9, 9, 1, 2,
1330 2, 1, 4, 10, 4, 10, 11, 11, 1, 5, 12, 12, 1, 5, 13, 13,
1331 3, 3, 6, 6, 2, 2, 14, 14, 16, 16, 15, 7, 15, 8, 8, 7,
1332 1, 1, 17, 17, 4, 4, 1, 1, 18, 18, 2, 2, 5, 5, 25, 3,
1333 9, 3, 25, 9, 19, 24, 19, 24, 1, 21, 20, 1, 21, 22, 20, 22,
1334 23, 23, 8, 6, 33, 6, 8, 33, 7, 7, 26, 26, 1, 32, 1, 32,
1335 28, 4, 28, 10, 29, 27, 27, 10, 41, 4, 29, 2, 2, 41, 36, 31,
1336 49, 31, 34, 30, 34, 36, 30, 35, 1, 49, 11, 5, 35, 11, 1, 3,
1337 3, 5, 37, 37, 8, 40, 8, 40, 12, 12, 42, 42, 1, 38, 16, 57,
1338 1, 6, 16, 39, 38, 6, 7, 7, 13, 13, 39, 43, 2, 43, 57, 2,
1339 50, 9, 44, 9, 50, 4, 15, 48, 44, 4, 1, 15, 48, 14, 14, 1,
1340 45, 45, 8, 3, 5, 8, 51, 47, 3, 46, 46, 47, 5, 51, 1, 17,
1341 17, 58, 1, 58, 2, 52, 52, 2, 53, 7, 59, 6, 6, 56, 53, 55,
1342 7, 55, 1, 54, 59, 56, 54, 10, 1, 10, 4, 60, 1, 60, 8, 4,
1343 8, 64, 64, 61, 1, 63, 3, 63, 62, 61, 5, 11, 5, 3, 11, 62},
1346 { 1, -1, 0, 1, -1, 2, -2, 1, -1, 1, -1, 0, 3, -3, 1, -1,
1347 2, -2, 1, -1, 1, -1, 4, 1, -4, -1, 2, -2, 1, -1, 5, 3,
1348 -3, -5, 2, 1, -2, -1, 1, -1, 6, 2, 1, -1, -6, -2, 1, -1,
1349 3, -3, 2, -2, 4, -4, 1, -1, 1, -1, 1, 2, -1, 2, -2, -2,
1350 7, -7, 1, -1, 3, -3, 8, -8, 1, -1, 5, -5, 3, -3, 1, 4,
1351 2, -4, -1, -2, 1, 1, -1, -1, 9, 1, 1, -9, -1, 1, -1, -1,
1352 1, -1, 3, -3, 1, 3, -3, -1, 3, -3, 1, -1, 10, 1, -10, -1,
1353 1, 4, -1, 2, 1, -1, 1, -2, 1, -4, -1, 6, -6, -1, 1, 1,
1354 1, -1, 1, 1, -1, -1, -1, 1, 11, -1, -2, 4, -1, 2, -11, 5,
1355 -5, -4, -1, 1, 4, 1, -4, -1, -2, 2, 1, -1, 12, 1, -2, 1,
1356 -12, 4, 2, 1, -1, -4, 4, -4, 2, -2, -1, 1, 7, -1, -1, -7,
1357 -1, -3, 1, 3, 1, 5, 2, 1, -1, -5, 13, -2, -1, 2, -2, -13,
1358 1, -1, 5, 6, 5, -5, 1, 1, -6, 1, -1, -1, -5, -1, 14, 2,
1359 -2, 1, -14, -1, 8, 1, -1, -8, 1, 5, 1, 5, -5, 1, -1, 1,
1360 -5, -1, 15, 1, -1, -1, -1, 3, -15, -3, 6, 1, 16, -1, 6, -6,
1361 -6, 1, -1, 1, -16, 1, 7, -1, 1, -1, -6, -3, 6, -7, 3, -1}
1367 {0, 1, 1, 2, 2, 3, 3, 4, 4, 1, 1, 5, 5, 6, 6, 7,
1368 7, 8, 8, 9, 9, 2, 2, 10, 10, 1, 1, 11, 11, 12, 12, 3,
1369 3, 13, 13, 0, 14, 14, 16, 15, 16, 15, 4, 4, 17, 1, 17, 1,
1370 5, 5, 18, 18, 2, 2, 6, 6, 8, 19, 7, 8, 7, 19, 20, 20,
1371 21, 21, 22, 24, 22, 24, 23, 23, 1, 1, 25, 25, 3, 3, 26, 26,
1372 9, 9, 27, 27, 28, 28, 33, 29, 4, 33, 29, 1, 4, 1, 32, 32,
1373 2, 2, 31, 10, 30, 10, 30, 31, 34, 34, 5, 5, 36, 36, 35, 41,
1374 35, 11, 41, 11, 37, 1, 8, 8, 37, 6, 1, 6, 40, 7, 7, 40,
1375 12, 38, 12, 39, 39, 38, 49, 13, 49, 13, 3, 42, 3, 42, 16, 16,
1376 43, 43, 14, 14, 1, 1, 44, 15, 44, 15, 2, 2, 57, 48, 50, 48,
1377 57, 50, 4, 45, 45, 4, 46, 47, 47, 46, 1, 51, 1, 17, 17, 51,
1378 8, 9, 9, 5, 58, 8, 58, 5, 52, 52, 55, 56, 53, 56, 55, 59,
1379 59, 53, 54, 1, 6, 54, 7, 7, 6, 1, 2, 3, 2, 3, 64, 60,
1380 60, 10, 10, 64, 61, 62, 61, 63, 1, 63, 62, 1, 18, 24, 18, 4,
1381 25, 4, 8, 21, 21, 1, 24, 22, 25, 22, 8, 11, 19, 11, 23, 1,
1382 20, 23, 19, 20, 5, 12, 5, 1, 16, 2, 12, 13, 2, 13, 1, 16},
1385 { 0, 1, -1, 1, -1, 1, -1, 1, -1, 2, -2, 1, -1, 1, -1, 1,
1386 -1, 1, -1, 1, -1, 2, -2, 1, -1, 3, -3, 1, -1, 1, -1, 2,
1387 -2, 1, -1, 0, 1, -1, 1, 1, -1, -1, 2, -2, 1, 4, -1, -4,
1388 2, -2, 1, -1, -3, 3, 2, -2, 2, 1, 2, -2, -2, -1, 1, -1,
1389 1, -1, 1, 1, -1, -1, 1, -1, 5, -5, 1, -1, 3, -3, 1, -1,
1390 2, -2, 1, -1, 1, -1, 1, 1, 3, -1, -1, 6, -3, -6, -1, 1,
1391 4, -4, 1, 2, 1, -2, -1, -1, 1, -1, 3, -3, 1, -1, 1, 1,
1392 -1, 2, -1, -2, 1, 7, -3, 3, -1, 3, -7, -3, 1, -3, 3, -1,
1393 2, 1, -2, 1, -1, -1, 1, 2, -1, -2, -4, -1, 4, 1, 2, -2,
1394 1, -1, -2, 2, 8, -8, -1, 2, 1, -2, -5, 5, 1, -1, -1, 1,
1395 -1, 1, 4, -1, 1, -4, -1, -1, 1, 1, 9, 1, -9, 2, -2, -1,
1396 -4, 3, -3, -4, -1, 4, 1, 4, 1, -1, 1, -1, 1, 1, -1, 1,
1397 -1, -1, -1, 10, 4, 1, 4, -4, -4, -10, 6, 5, -6, -5, 1, -1,
1398 1, 3, -3, -1, 1, -1, -1, -1, 11, 1, 1, -11, -2, -2, 2, 5,
1399 -2, -5, -5, 2, -2, 12, 2, -2, 2, 2, 5, -3, -2, 3, -2, -12,
1400 -2, 2, 2, 2, -5, 3, 5, 13, -3, 7, -3, -3, -7, 3, -13, 3}
1406 {0, 1, 1, 1, 2, 2, 1, 3, 3, 1, 1, 1, 4, 4, 1, 5,
1407 2, 1, 5, 2, 1, 1, 6, 6, 1, 1, 1, 1, 1, 7, 3, 1,
1408 2, 3, 0, 1, 2, 7, 1, 1, 1, 8, 1, 1, 8, 1, 1, 1,
1409 9, 1, 9, 1, 2, 1, 1, 2, 1, 1, 10, 4, 1, 10, 1, 4,
1410 1, 1, 1, 1, 1, 3, 1, 1, 1, 3, 2, 1, 5, 1, 1, 1,
1411 2, 5, 1, 11, 1, 11, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
1412 2, 1, 6, 1, 6, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1, 12,
1413 3, 1, 12, 1, 1, 1, 2, 1, 1, 3, 1, 1, 1, 1, 1, 1,
1414 4, 1, 1, 1, 2, 1, 1, 4, 1, 1, 1, 1, 1, 1, 2, 1,
1415 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 3, 1, 2, 1, 1, 5,
1416 1, 1, 1, 1, 1, 7, 1, 7, 1, 1, 2, 3, 1, 1, 1, 1,
1417 5, 1, 1, 1, 1, 1, 1, 2, 13, 1, 1, 1, 1, 1, 1, 1,
1418 1, 1, 1, 1, 1, 1, 1, 1, 13, 2, 1, 1, 4, 1, 1, 1,
1419 3, 1, 6, 1, 1, 1, 14, 1, 1, 1, 1, 1, 14, 6, 1, 1,
1420 1, 1, 15, 2, 4, 1, 2, 3, 15, 1, 1, 1, 8, 1, 1, 8,
1421 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 1, 1},
1424 { 0, 1, -1, 2, 1, -1, -2, 1, -1, 3, -3, 4, 1, -1, -4, 1,
1425 2, 5, -1, -2, -5, 6, 1, -1, -6, 7, -7, 8, -8, 1, 2, 9,
1426 3, -2, 0, -9, -3, -1, 10, -10, 11, 1, -11, 12, -1, -12, 13, -13,
1427 1, 14, -1, -14, 4, 15, -15, -4, 16, -16, 1, 2, 17, -1, -17, -2,
1428 18, -18, 19, -19, 20, 3, -20, 21, -21, -3, 5, 22, 2, -22, -23, 23,
1429 -5, -2, 24, 1, -24, -1, 25, -25, 26, -26, -27, 27, 28, 29, -28, -29,
1430 6, 30, 2, -31, -2, -30, 31, -6, -32, 32, 33, -33, 34, -35, -34, 1,
1431 4, -36, -1, 35, 37, 36, 7, -37, 38, -4, -38, 39, 41, 40, -40, -39,
1432 3, 42, -43, -41, -7, -42, 43, -3, 44, -44, 45, -45, 46, 47, 8, -47,
1433 -48, -46, 50, -50, 48, 49, 51, -49, 52, -52, 5, -51, -8, -53, 53, 3,
1434 -56, 56, 55, 54, -54, 2, 60, -2, -55, 58, 9, -5, 59, 57, -57, -63,
1435 -3, -58, -60, -61, 61, -59, -62, -9, 1, 64, 62, 69, -64, 63, 65, -67,
1436 -68, 66, -65, 68, -66, -69, 67, -70, -1, 10, 71, -71, 4, 73, 72, 70,
1437 6, -76, -3, 74, -78, -74, 1, 78, 80, -72, -75, 76, -1, 3, -73, 79,
1438 75, 77, 1, 11, -4, -79, -10, -6, -1, -77, -83, -80, 2, 81, -84, -2,
1439 83, -81, 82, -82, 84, -87, -86, 85, -11, -85, 86, -89, 87, -88, 88, 89}
1445 {1, 1, 0, 2, 1, 2, 1, 3, 3, 1, 1, 4, 4, 2, 2, 1,
1446 1, 5, 5, 6, 1, 6, 1, 7, 7, 3, 3, 2, 8, 2, 8, 1,
1447 1, 0, 9, 9, 1, 1, 10, 4, 10, 4, 11, 11, 2, 1, 2, 1,
1448 12, 12, 3, 3, 1, 1, 13, 5, 5, 13, 14, 1, 1, 14, 2, 2,
1449 6, 6, 15, 1, 1, 15, 16, 4, 7, 16, 4, 7, 1, 1, 3, 3,
1450 8, 8, 2, 2, 1, 1, 17, 17, 1, 1, 18, 18, 5, 5, 2, 2,
1451 1, 1, 9, 19, 9, 19, 20, 3, 3, 20, 1, 10, 21, 1, 10, 4,
1452 4, 21, 22, 6, 6, 22, 1, 1, 23, 24, 2, 2, 23, 24, 11, 1,
1453 1, 11, 7, 25, 7, 1, 1, 25, 8, 8, 3, 26, 3, 1, 12, 2,
1454 2, 26, 1, 12, 5, 5, 27, 4, 1, 4, 1, 27, 28, 1, 28, 13,
1455 1, 13, 2, 29, 2, 1, 32, 6, 1, 30, 14, 29, 14, 6, 3, 31,
1456 3, 1, 30, 1, 32, 31, 33, 9, 33, 1, 1, 7, 9, 7, 2, 2,
1457 1, 1, 4, 36, 34, 4, 5, 10, 10, 5, 34, 1, 1, 35, 8, 8,
1458 36, 3, 35, 1, 15, 3, 2, 1, 16, 15, 16, 2, 37, 1, 37, 1,
1459 1, 1, 6, 6, 38, 1, 38, 11, 1, 39, 39, 40, 11, 2, 41, 4,
1460 40, 1, 2, 4, 1, 1, 1, 41, 3, 1, 3, 1, 5, 7, 5, 7},
1463 { 1, -1, 0, 1, 2, -1, -2, 1, -1, 3, -3, 1, -1, 2, -2, 4,
1464 -4, 1, -1, 1, 5, -1, -5, 1, -1, 2, -2, 3, 1, -3, -1, 6,
1465 -6, 0, 1, -1, 7, -7, 1, 2, -1, -2, 1, -1, 4, 8, -4, -8,
1466 1, -1, 3, -3, 9, -9, 1, 2, -2, -1, 1, 10, -10, -1, 5, -5,
1467 2, -2, 1, 11, -11, -1, 1, 3, 2, -1, -3, -2, 12, -12, 4, -4,
1468 2, -2, -6, 6, 13, -13, 1, -1, 14, -14, 1, -1, 3, -3, 7, -7,
1469 15, -15, 2, 1, -2, -1, 1, 5, -5, -1, -16, 2, 1, 16, -2, 4,
1470 -4, -1, 1, 3, -3, -1, 17, -17, 1, 1, -8, 8, -1, -1, 2, 18,
1471 -18, -2, 3, 1, -3, 19, -19, -1, 3, -3, 6, 1, -6, 20, 2, 9,
1472 -9, -1, -20, -2, 4, -4, 1, -5, 21, 5, -21, -1, 1, -22, -1, 2,
1473 22, -2, 10, 1, -10, 23, 1, 4, -23, 1, 2, -1, -2, -4, -7, 1,
1474 7, -24, -1, 24, -1, -1, 1, 3, -1, -25, 25, 4, -3, -4, 11, -11,
1475 26, -26, 6, 1, 1, -6, -5, -3, 3, 5, -1, -27, 27, 1, 4, -4,
1476 -1, -8, -1, 28, 2, 8, -12, -28, -2, -2, 2, 12, -1, 29, 1, -29,
1477 30, -30, 5, -5, 1, -31, -1, 3, 31, -1, 1, 1, -3, -13, 1, -7,
1478 -1, -32, 13, 7, 32, 33, -33, -1, -9, -34, 9, 34, -6, 5, 6, -5}
1484 {1, 1, 0, 1, 1, 2, 2, 1, 1, 3, 3, 1, 1, 0, 2, 2,
1485 4, 1, 4, 1, 1, 1, 5, 5, 1, 1, 6, 6, 2, 2, 1, 1,
1486 3, 3, 7, 7, 1, 1, 8, 8, 1, 1, 2, 2, 1, 9, 1, 9,
1487 4, 4, 10, 1, 1, 10, 1, 1, 11, 11, 3, 3, 1, 2, 1, 2,
1488 1, 1, 12, 12, 5, 5, 1, 1, 13, 1, 1, 13, 2, 2, 1, 1,
1489 6, 6, 1, 1, 4, 14, 4, 14, 3, 1, 3, 1, 1, 1, 15, 7,
1490 15, 2, 2, 7, 1, 1, 1, 8, 1, 8, 16, 16, 1, 1, 1, 1,
1491 2, 1, 1, 2, 1, 1, 3, 5, 5, 3, 4, 1, 1, 4, 1, 1,
1492 17, 17, 9, 1, 1, 9, 2, 2, 1, 1, 10, 10, 1, 6, 1, 1,
1493 6, 18, 1, 1, 18, 1, 1, 1, 2, 2, 3, 1, 3, 1, 1, 1,
1494 4, 1, 19, 1, 19, 7, 1, 1, 20, 1, 4, 20, 1, 7, 11, 2,
1495 1, 11, 21, 2, 8, 5, 1, 8, 1, 5, 21, 1, 1, 1, 22, 1,
1496 1, 22, 1, 1, 3, 3, 1, 23, 2, 12, 24, 1, 1, 2, 1, 1,
1497 12, 23, 1, 1, 24, 1, 1, 1, 4, 1, 1, 1, 2, 1, 6, 6,
1498 4, 2, 1, 1, 1, 1, 1, 1, 1, 14, 13, 3, 1, 25, 9, 25,
1499 14, 1, 9, 3, 13, 1, 1, 1, 1, 1, 10, 1, 1, 2, 10, 2},
1502 {-20, -1, 0, 2, -2, 1, -1, 3, -3, 1, -1, 4, -4, 0, 2, -2,
1503 1, 5, -1, -5, 6, -6, 1, -1, 7, -7, 1, -1, 3, -3, 8, -8,
1504 2, -2, 1, -1, 9, -9, 1, -1, 10, -10, 4, -4, 11, 1, -11, -1,
1505 2, -2, 1, 12, -12, -1, 13, -13, 1, -1, 3, -3, 14, 5, -14, -5,
1506 -15, 15, -1, 1, 2, -2, 16, -16, 1, 17, -17, -1, 6, -6, 18, -18,
1507 2, -2, -19, 19, -3, 1, 3, -1, 4, 20, -4, 1, -21, 21, 1, 2,
1508 -1, -7, 7, -2, 22, -22, 23, 2, -23, -2, 1, -1, -24, 24, -25, 25,
1509 -8, -26, 26, 8, -27, 27, 5, 3, -3, -5, -4, 28, -28, 4, 29, -29,
1510 1, -1, -2, -30, 30, 2, 9, -9, -31, 31, 2, -2, -32, 3, 32, -33,
1511 -3, 1, 33, -34, -1, 34, -35, 35, -10, 10, -6, 36, 6, -36, 37, -37,
1512 -5, 38, 1, -38, -1, 3, 39, -39, -1, 40, 5, 1, -40, -3, 2, -11,
1513 -41, -2, 1, 11, -3, -4, 41, 3, 42, 4, -1, -43, -42, 43, 1, -44,
1514 45, -1, 44, -45, -7, 7, -46, 1, -12, 2, 1, -47, 46, 12, 47, 48,
1515 -2, -1, -48, 49, -1, -50, -49, 50, -6, -51, 51, 52, -13, 53, -4, 4,
1516 6, 13, -53, -52, -54, 55, 54, -55, -56, -2, 2, -8, 56, 1, -3, -1,
1517 2, 58, 3, 8, -2, 57, -58, -60, -59, -57, -3, 60, 59, -14, 3, 14}
1523 {1, 1, 0, 2, 2, 1, 1, 3, 3, 4, 4, 5, 5, 1, 1, 6,
1524 6, 2, 2, 7, 7, 8, 8, 1, 1, 3, 3, 9, 9, 10, 10, 1,
1525 1, 2, 2, 4, 4, 11, 0, 11, 12, 12, 13, 13, 1, 1, 5, 5,
1526 14, 14, 15, 16, 15, 16, 3, 3, 1, 6, 1, 6, 2, 2, 7, 7,
1527 8, 8, 17, 17, 1, 1, 4, 4, 18, 18, 2, 2, 1, 19, 1, 20,
1528 19, 20, 21, 21, 3, 3, 22, 22, 5, 5, 24, 1, 1, 23, 9, 23,
1529 24, 9, 2, 2, 10, 1, 1, 10, 6, 6, 25, 4, 4, 25, 7, 7,
1530 26, 8, 1, 8, 3, 1, 26, 3, 11, 11, 27, 27, 2, 28, 1, 2,
1531 28, 1, 12, 12, 5, 5, 29, 13, 13, 29, 32, 1, 1, 33, 31, 30,
1532 32, 4, 30, 33, 4, 31, 3, 14, 1, 1, 3, 34, 34, 2, 2, 14,
1533 6, 6, 35, 36, 35, 36, 1, 15, 1, 16, 16, 15, 7, 9, 7, 9,
1534 37, 8, 8, 37, 1, 1, 39, 2, 38, 39, 2, 40, 5, 38, 40, 5,
1535 3, 3, 4, 4, 10, 10, 1, 1, 1, 1, 41, 2, 41, 2, 6, 6,
1536 1, 1, 11, 42, 11, 43, 3, 42, 3, 17, 4, 43, 1, 17, 7, 1,
1537 8, 44, 4, 7, 44, 5, 8, 2, 5, 1, 2, 48, 45, 1, 12, 45,
1538 12, 48, 13, 13, 1, 9, 9, 46, 1, 46, 47, 47, 49, 18, 18, 49},
1541 { 1, -1, 0, 1, -1, 2, -2, 1, -1, 1, -1, 1, -1, 3, -3, 1,
1542 -1, -2, 2, 1, -1, 1, -1, 4, -4, -2, 2, 1, -1, 1, -1, 5,
1543 -5, -3, 3, 2, -2, 1, 0, -1, 1, -1, 1, -1, 6, -6, 2, -2,
1544 1, -1, 1, 1, -1, -1, -3, 3, 7, 2, -7, -2, -4, 4, 2, -2,
1545 2, -2, 1, -1, 8, -8, 3, -3, 1, -1, -5, 5, 9, 1, -9, 1,
1546 -1, -1, 1, -1, -4, 4, 1, -1, 3, -3, 1, -10, 10, 1, 2, -1,
1547 -1, -2, 6, -6, 2, 11, -11, -2, 3, -3, 1, -4, 4, -1, 3, -3,
1548 1, 3, 12, -3, -5, -12, -1, 5, 2, -2, 1, -1, -7, 1, 13, 7,
1549 -1, -13, 2, -2, 4, -4, 1, 2, -2, -1, 1, 14, -14, 1, 1, 1,
1550 -1, -5, -1, -1, 5, -1, -6, 2, -15, 15, 6, 1, -1, -8, 8, -2,
1551 -4, 4, 1, 1, -1, -1, 16, 2, -16, -2, 2, -2, 4, 3, -4, -3,
1552 -1, -4, 4, 1, -17, 17, -1, -9, 1, 1, 9, 1, -5, -1, -1, 5,
1553 -7, 7, 6, -6, 3, -3, 18, -18, 19, -19, 1, -10, -1, 10, -5, 5,
1554 20, -20, -3, 1, 3, 1, 8, -1, -8, 2, 7, -1, -21, -2, 5, 21,
1555 5, -1, -7, -5, 1, -6, -5, -11, 6, 22, 11, 1, 1, -22, -3, -1,
1556 3, -1, 3, -3, -23, 4, -4, 1, 23, -1, 1, -1, 1, -2, 2, -1}
1562 {1, 1, 1, 1, 0, 2, 2, 1, 1, 3, 3, 0, 1, 1, 2, 2,
1563 4, 4, 1, 1, 5, 5, 1, 1, 2, 2, 3, 3, 6, 6, 1, 1,
1564 7, 7, 8, 1, 8, 2, 2, 1, 4, 4, 1, 3, 1, 3, 9, 9,
1565 2, 2, 1, 5, 1, 5, 10, 10, 1, 1, 11, 11, 3, 6, 3, 4,
1566 4, 6, 2, 2, 1, 12, 1, 12, 7, 13, 7, 13, 1, 1, 8, 8,
1567 2, 2, 14, 14, 16, 15, 16, 5, 5, 1, 3, 15, 1, 3, 4, 4,
1568 1, 1, 17, 17, 2, 2, 6, 6, 1, 18, 1, 18, 22, 21, 22, 21,
1569 25, 24, 25, 19, 9, 20, 9, 23, 19, 24, 20, 3, 23, 7, 3, 1,
1570 1, 7, 28, 26, 29, 5, 28, 26, 5, 8, 29, 4, 8, 27, 2, 2,
1571 4, 27, 1, 1, 10, 36, 10, 33, 33, 36, 30, 1, 32, 32, 1, 30,
1572 6, 31, 31, 35, 3, 6, 11, 11, 3, 2, 35, 2, 34, 1, 34, 1,
1573 37, 37, 12, 7, 12, 5, 41, 5, 4, 7, 1, 8, 13, 4, 1, 41,
1574 13, 38, 8, 38, 9, 1, 40, 40, 9, 1, 39, 2, 2, 49, 39, 42,
1575 3, 3, 14, 16, 49, 14, 16, 42, 43, 43, 6, 6, 15, 1, 1, 15,
1576 44, 44, 1, 1, 50, 48, 4, 5, 4, 7, 5, 2, 10, 10, 48, 7,
1577 50, 45, 2, 1, 45, 8, 8, 1, 46, 46, 3, 47, 47, 3, 1, 1},
1580 { 1, -1, 2, -2, 0, 1, -1, 3, -3, 1, -1, 0, 4, -4, 2, -2,
1581 1, -1, 5, -5, 1, -1, 6, -6, 3, -3, 2, -2, 1, -1, 7, -7,
1582 1, -1, 1, 8, -1, 4, -4, -8, 2, -2, 9, 3, -9, -3, 1, -1,
1583 5, -5, 10, 2, -10, -2, 1, -1, 11, -11, 1, -1, -4, 2, 4, 3,
1584 -3, -2, 6, -6, 12, 1, -12, -1, 2, 1, -2, -1, 13, -13, 2, -2,
1585 7, -7, 1, -1, 1, 1, -1, 3, -3, 14, 5, -1, -14, -5, 4, -4,
1586 15, -15, 1, -1, 8, -8, -3, 3, 16, 1, -16, -1, 1, 1, -1, -1,
1587 1, 1, -1, 1, 2, 1, -2, 1, -1, -1, -1, 6, -1, 3, -6, 17,
1588 -17, -3, 1, 1, 1, 4, -1, -1, -4, 3, -1, 5, -3, -1, -9, 9,
1589 -5, 1, 18, -18, 2, 1, -2, 1, -1, -1, 1, 19, -1, 1, -19, -1,
1590 4, 1, -1, 1, 7, -4, -2, 2, -7, 10, -1, -10, 1, 20, -1, -20,
1591 1, -1, 2, 4, -2, 5, 1, -5, 6, -4, 21, 4, 2, -6, -21, -1,
1592 -2, 1, -4, -1, -3, 22, -1, 1, 3, -22, -1, 11, -11, 1, 1, 1,
1593 8, -8, 2, 2, -1, -2, -2, -1, 1, -1, -5, 5, 2, 23, -23, -2,
1594 1, -1, 24, -24, -1, -1, 7, 6, -7, 5, -6, 12, -3, 3, 1, -5,
1595 1, 1, -12, 25, -1, -5, 5, -25, -1, 1, 9, 1, -1, -9, 26, -26}