factor out common decoding code for Indeo 4 and Indeo 5
[ffmpeg.git] / libavcodec / ivi_common.c
1 /*
2  * common functions for Indeo Video Interactive codecs (Indeo4 and Indeo5)
3  *
4  * Copyright (c) 2009 Maxim Poliakovski
5  *
6  * This file is part of Libav.
7  *
8  * Libav is free software; you can redistribute it and/or
9  * modify it under the terms of the GNU Lesser General Public
10  * License as published by the Free Software Foundation; either
11  * version 2.1 of the License, or (at your option) any later version.
12  *
13  * Libav is distributed in the hope that it will be useful,
14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
16  * Lesser General Public License for more details.
17  *
18  * You should have received a copy of the GNU Lesser General Public
19  * License along with Libav; if not, write to the Free Software
20  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
21  */
22
23 /**
24  * @file
25  * This file contains functions and data shared by both Indeo4 and
26  * Indeo5 decoders.
27  */
28
29 #define BITSTREAM_READER_LE
30 #include "avcodec.h"
31 #include "get_bits.h"
32 #include "ivi_common.h"
33 #include "libavutil/common.h"
34 #include "ivi_dsp.h"
35
36 extern const IVIHuffDesc ff_ivi_mb_huff_desc[8];  ///< static macroblock huffman tables
37 extern const IVIHuffDesc ff_ivi_blk_huff_desc[8]; ///< static block huffman tables
38
39 VLC ff_ivi_mb_vlc_tabs [8];
40 VLC ff_ivi_blk_vlc_tabs[8];
41
42 /**
43  *  Reverse "nbits" bits of the value "val" and return the result
44  *  in the least significant bits.
45  */
46 static uint16_t inv_bits(uint16_t val, int nbits)
47 {
48     uint16_t res;
49
50     if (nbits <= 8) {
51         res = av_reverse[val] >> (8-nbits);
52     } else
53         res = ((av_reverse[val & 0xFF] << 8) + (av_reverse[val >> 8])) >> (16-nbits);
54
55     return res;
56 }
57
58 int ff_ivi_create_huff_from_desc(const IVIHuffDesc *cb, VLC *vlc, int flag)
59 {
60     int         pos, i, j, codes_per_row, prefix, not_last_row;
61     uint16_t    codewords[256]; /* FIXME: move this temporal storage out? */
62     uint8_t     bits[256];
63
64     pos = 0; /* current position = 0 */
65
66     for (i = 0; i < cb->num_rows; i++) {
67         codes_per_row = 1 << cb->xbits[i];
68         not_last_row  = (i != cb->num_rows - 1);
69         prefix        = ((1 << i) - 1) << (cb->xbits[i] + not_last_row);
70
71         for (j = 0; j < codes_per_row; j++) {
72             if (pos >= 256) /* Some Indeo5 codebooks can have more than 256 */
73                 break;      /* elements, but only 256 codes are allowed! */
74
75             bits[pos] = i + cb->xbits[i] + not_last_row;
76             if (bits[pos] > IVI_VLC_BITS)
77                 return -1; /* invalid descriptor */
78
79             codewords[pos] = inv_bits((prefix | j), bits[pos]);
80             if (!bits[pos])
81                 bits[pos] = 1;
82
83             pos++;
84         }//for j
85     }//for i
86
87     /* number of codewords = pos */
88     return init_vlc(vlc, IVI_VLC_BITS, pos, bits, 1, 1, codewords, 2, 2,
89                     (flag ? INIT_VLC_USE_NEW_STATIC : 0) | INIT_VLC_LE);
90 }
91
92 void ff_ivi_init_static_vlc(void)
93 {
94     int i;
95     static VLC_TYPE table_data[8192 * 16][2];
96     static int initialized_vlcs = 0;
97
98     if (initialized_vlcs)
99         return;
100     for (i = 0; i < 8; i++) {
101         ff_ivi_mb_vlc_tabs[i].table = table_data + i * 2 * 8192;
102         ff_ivi_mb_vlc_tabs[i].table_allocated = 8192;
103         ff_ivi_create_huff_from_desc(&ff_ivi_mb_huff_desc[i],  &ff_ivi_mb_vlc_tabs[i],  1);
104         ff_ivi_blk_vlc_tabs[i].table = table_data + (i * 2 + 1) * 8192;
105         ff_ivi_blk_vlc_tabs[i].table_allocated = 8192;
106         ff_ivi_create_huff_from_desc(&ff_ivi_blk_huff_desc[i], &ff_ivi_blk_vlc_tabs[i], 1);
107     }
108     initialized_vlcs = 1;
109 }
110
111 int ff_ivi_dec_huff_desc(GetBitContext *gb, int desc_coded, int which_tab,
112                          IVIHuffTab *huff_tab, AVCodecContext *avctx)
113 {
114     int         i, result;
115     IVIHuffDesc new_huff;
116
117     if (!desc_coded) {
118         /* select default table */
119         huff_tab->tab = (which_tab) ? &ff_ivi_blk_vlc_tabs[7]
120             : &ff_ivi_mb_vlc_tabs [7];
121     } else {
122         huff_tab->tab_sel = get_bits(gb, 3);
123         if (huff_tab->tab_sel == 7) {
124             /* custom huffman table (explicitly encoded) */
125             new_huff.num_rows = get_bits(gb, 4);
126
127             for (i = 0; i < new_huff.num_rows; i++)
128                 new_huff.xbits[i] = get_bits(gb, 4);
129
130             /* Have we got the same custom table? Rebuild if not. */
131             if (ff_ivi_huff_desc_cmp(&new_huff, &huff_tab->cust_desc)) {
132                 ff_ivi_huff_desc_copy(&huff_tab->cust_desc, &new_huff);
133
134                 if (huff_tab->cust_tab.table)
135                     ff_free_vlc(&huff_tab->cust_tab);
136                 result = ff_ivi_create_huff_from_desc(&huff_tab->cust_desc,
137                         &huff_tab->cust_tab, 0);
138                 if (result) {
139                     av_log(avctx, AV_LOG_ERROR,
140                            "Error while initializing custom vlc table!\n");
141                     return -1;
142                 }
143             }
144             huff_tab->tab = &huff_tab->cust_tab;
145         } else {
146             /* select one of predefined tables */
147             huff_tab->tab = (which_tab) ? &ff_ivi_blk_vlc_tabs[huff_tab->tab_sel]
148                 : &ff_ivi_mb_vlc_tabs [huff_tab->tab_sel];
149         }
150     }
151
152     return 0;
153 }
154
155 int ff_ivi_huff_desc_cmp(const IVIHuffDesc *desc1, const IVIHuffDesc *desc2)
156 {
157     return    desc1->num_rows != desc2->num_rows
158            || memcmp(desc1->xbits, desc2->xbits, desc1->num_rows);
159 }
160
161 void ff_ivi_huff_desc_copy(IVIHuffDesc *dst, const IVIHuffDesc *src)
162 {
163     dst->num_rows = src->num_rows;
164     memcpy(dst->xbits, src->xbits, src->num_rows);
165 }
166
167 av_cold int ff_ivi_init_planes(IVIPlaneDesc *planes, const IVIPicConfig *cfg)
168 {
169     int         p, b;
170     uint32_t    b_width, b_height, align_fac, width_aligned, height_aligned, buf_size;
171     IVIBandDesc *band;
172
173     ff_ivi_free_buffers(planes);
174
175     /* fill in the descriptor of the luminance plane */
176     planes[0].width     = cfg->pic_width;
177     planes[0].height    = cfg->pic_height;
178     planes[0].num_bands = cfg->luma_bands;
179
180     /* fill in the descriptors of the chrominance planes */
181     planes[1].width     = planes[2].width     = (cfg->pic_width  + 3) >> 2;
182     planes[1].height    = planes[2].height    = (cfg->pic_height + 3) >> 2;
183     planes[1].num_bands = planes[2].num_bands = cfg->chroma_bands;
184
185     for (p = 0; p < 3; p++) {
186         planes[p].bands = av_mallocz(planes[p].num_bands * sizeof(IVIBandDesc));
187         if (!planes[p].bands)
188             return AVERROR(ENOMEM);
189
190         /* select band dimensions: if there is only one band then it
191          *  has the full size, if there are several bands each of them
192          *  has only half size */
193         b_width  = planes[p].num_bands == 1 ? planes[p].width  : (planes[p].width  + 1) >> 1;
194         b_height = planes[p].num_bands == 1 ? planes[p].height : (planes[p].height + 1) >> 1;
195
196         /* luma   band buffers will be aligned on 16x16 (max macroblock size) */
197         /* chroma band buffers will be aligned on   8x8 (max macroblock size) */
198         align_fac       = p ? 8 : 16;
199         width_aligned   = FFALIGN(b_width , align_fac);
200         height_aligned  = FFALIGN(b_height, align_fac);
201         buf_size        = width_aligned * height_aligned * sizeof(int16_t);
202
203         for (b = 0; b < planes[p].num_bands; b++) {
204             band = &planes[p].bands[b]; /* select appropriate plane/band */
205             band->plane    = p;
206             band->band_num = b;
207             band->width    = b_width;
208             band->height   = b_height;
209             band->pitch    = width_aligned;
210             band->bufs[0]  = av_malloc(buf_size);
211             band->bufs[1]  = av_malloc(buf_size);
212             if (!band->bufs[0] || !band->bufs[1])
213                 return AVERROR(ENOMEM);
214
215             /* allocate the 3rd band buffer for scalability mode */
216             if (cfg->luma_bands > 1) {
217                 band->bufs[2] = av_malloc(buf_size);
218                 if (!band->bufs[2])
219                     return AVERROR(ENOMEM);
220             }
221
222             planes[p].bands[0].blk_vlc.cust_desc.num_rows = 0; /* reset custom vlc */
223         }
224     }
225
226     return 0;
227 }
228
229 av_cold void ff_ivi_free_buffers(IVIPlaneDesc *planes)
230 {
231     int p, b, t;
232
233     for (p = 0; p < 3; p++) {
234         for (b = 0; b < planes[p].num_bands; b++) {
235             av_freep(&planes[p].bands[b].bufs[0]);
236             av_freep(&planes[p].bands[b].bufs[1]);
237             av_freep(&planes[p].bands[b].bufs[2]);
238
239             if (planes[p].bands[b].blk_vlc.cust_tab.table)
240                 ff_free_vlc(&planes[p].bands[b].blk_vlc.cust_tab);
241             for (t = 0; t < planes[p].bands[b].num_tiles; t++)
242                 av_freep(&planes[p].bands[b].tiles[t].mbs);
243             av_freep(&planes[p].bands[b].tiles);
244         }
245         av_freep(&planes[p].bands);
246     }
247 }
248
249 av_cold int ff_ivi_init_tiles(IVIPlaneDesc *planes, int tile_width, int tile_height)
250 {
251     int         p, b, x, y, x_tiles, y_tiles, t_width, t_height;
252     IVIBandDesc *band;
253     IVITile     *tile, *ref_tile;
254
255     for (p = 0; p < 3; p++) {
256         t_width  = !p ? tile_width  : (tile_width  + 3) >> 2;
257         t_height = !p ? tile_height : (tile_height + 3) >> 2;
258
259         if (!p && planes[0].num_bands == 4) {
260             t_width  >>= 1;
261             t_height >>= 1;
262         }
263
264         for (b = 0; b < planes[p].num_bands; b++) {
265             band = &planes[p].bands[b];
266             x_tiles = IVI_NUM_TILES(band->width, t_width);
267             y_tiles = IVI_NUM_TILES(band->height, t_height);
268             band->num_tiles = x_tiles * y_tiles;
269
270             av_freep(&band->tiles);
271             band->tiles = av_mallocz(band->num_tiles * sizeof(IVITile));
272             if (!band->tiles)
273                 return AVERROR(ENOMEM);
274
275             tile = band->tiles;
276
277             /* use the first luma band as reference for motion vectors
278              * and quant */
279             ref_tile = planes[0].bands[0].tiles;
280
281             for (y = 0; y < band->height; y += t_height) {
282                 for (x = 0; x < band->width; x += t_width) {
283                     tile->xpos     = x;
284                     tile->ypos     = y;
285                     tile->width    = FFMIN(band->width - x,  t_width);
286                     tile->height   = FFMIN(band->height - y, t_height);
287                     tile->is_empty = tile->data_size = 0;
288                     /* calculate number of macroblocks */
289                     tile->num_MBs  = IVI_MBs_PER_TILE(tile->width, tile->height,
290                                                       band->mb_size);
291
292                     av_freep(&tile->mbs);
293                     tile->mbs = av_malloc(tile->num_MBs * sizeof(IVIMbInfo));
294                     if (!tile->mbs)
295                         return AVERROR(ENOMEM);
296
297                     tile->ref_mbs = 0;
298                     if (p || b) {
299                         tile->ref_mbs = ref_tile->mbs;
300                         ref_tile++;
301                     }
302
303                     tile++;
304                 }
305             }
306
307         }// for b
308     }// for p
309
310     return 0;
311 }
312
313 int ff_ivi_dec_tile_data_size(GetBitContext *gb)
314 {
315     int    len;
316
317     len = 0;
318     if (get_bits1(gb)) {
319         len = get_bits(gb, 8);
320         if (len == 255)
321             len = get_bits_long(gb, 24);
322     }
323
324     /* align the bitstream reader on the byte boundary */
325     align_get_bits(gb);
326
327     return len;
328 }
329
330 int ff_ivi_decode_blocks(GetBitContext *gb, IVIBandDesc *band, IVITile *tile)
331 {
332     int         mbn, blk, num_blocks, num_coeffs, blk_size, scan_pos, run, val,
333                 pos, is_intra, mc_type = 0, mv_x, mv_y, col_mask;
334     uint8_t     col_flags[8];
335     int32_t     prev_dc, trvec[64];
336     uint32_t    cbp, sym, lo, hi, quant, buf_offs, q;
337     IVIMbInfo   *mb;
338     RVMapDesc   *rvmap = band->rv_map;
339     void (*mc_with_delta_func)(int16_t *buf, const int16_t *ref_buf, uint32_t pitch, int mc_type);
340     void (*mc_no_delta_func)  (int16_t *buf, const int16_t *ref_buf, uint32_t pitch, int mc_type);
341     const uint16_t  *base_tab;
342     const uint8_t   *scale_tab;
343
344     prev_dc = 0; /* init intra prediction for the DC coefficient */
345
346     blk_size   = band->blk_size;
347     col_mask   = blk_size - 1; /* column mask for tracking non-zero coeffs */
348     num_blocks = (band->mb_size != blk_size) ? 4 : 1; /* number of blocks per mb */
349     num_coeffs = blk_size * blk_size;
350     if (blk_size == 8) {
351         mc_with_delta_func = ff_ivi_mc_8x8_delta;
352         mc_no_delta_func   = ff_ivi_mc_8x8_no_delta;
353     } else {
354         mc_with_delta_func = ff_ivi_mc_4x4_delta;
355         mc_no_delta_func   = ff_ivi_mc_4x4_no_delta;
356     }
357
358     for (mbn = 0, mb = tile->mbs; mbn < tile->num_MBs; mb++, mbn++) {
359         is_intra = !mb->type;
360         cbp      = mb->cbp;
361         buf_offs = mb->buf_offs;
362
363         quant = av_clip(band->glob_quant + mb->q_delta, 0, 23);
364
365         base_tab  = is_intra ? band->intra_base  : band->inter_base;
366         scale_tab = is_intra ? band->intra_scale : band->inter_scale;
367         if (scale_tab)
368             quant = scale_tab[quant];
369
370         if (!is_intra) {
371             mv_x = mb->mv_x;
372             mv_y = mb->mv_y;
373             if (band->is_halfpel) {
374                 mc_type = ((mv_y & 1) << 1) | (mv_x & 1);
375                 mv_x >>= 1;
376                 mv_y >>= 1; /* convert halfpel vectors into fullpel ones */
377             }
378         }
379
380         for (blk = 0; blk < num_blocks; blk++) {
381             /* adjust block position in the buffer according to its number */
382             if (blk & 1) {
383                 buf_offs += blk_size;
384             } else if (blk == 2) {
385                 buf_offs -= blk_size;
386                 buf_offs += blk_size * band->pitch;
387             }
388
389             if (cbp & 1) { /* block coded ? */
390                 scan_pos = -1;
391                 memset(trvec, 0, num_coeffs*sizeof(trvec[0])); /* zero transform vector */
392                 memset(col_flags, 0, sizeof(col_flags));      /* zero column flags */
393
394                 while (scan_pos <= num_coeffs) {
395                     sym = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
396                     if (sym == rvmap->eob_sym)
397                         break; /* End of block */
398
399                     if (sym == rvmap->esc_sym) { /* Escape - run/val explicitly coded using 3 vlc codes */
400                         run = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1) + 1;
401                         lo  = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
402                         hi  = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
403                         val = IVI_TOSIGNED((hi << 6) | lo); /* merge them and convert into signed val */
404                     } else {
405                         if (sym >= 256U) {
406                             av_log(NULL, AV_LOG_ERROR, "Invalid sym encountered: %d.\n", sym);
407                             return -1;
408                         }
409                         run = rvmap->runtab[sym];
410                         val = rvmap->valtab[sym];
411                     }
412
413                     /* de-zigzag and dequantize */
414                     scan_pos += run;
415                     if (scan_pos >= num_coeffs)
416                         break;
417                     pos = band->scan[scan_pos];
418
419                     if (!val)
420                         av_dlog(NULL, "Val = 0 encountered!\n");
421
422                     q = (base_tab[pos] * quant) >> 9;
423                     if (q > 1)
424                         val = val * q + FFSIGN(val) * (((q ^ 1) - 1) >> 1);
425                     trvec[pos] = val;
426                     col_flags[pos & col_mask] |= !!val; /* track columns containing non-zero coeffs */
427                 }// while
428
429                 if (scan_pos >= num_coeffs && sym != rvmap->eob_sym)
430                     return -1; /* corrupt block data */
431
432                 /* undoing DC coeff prediction for intra-blocks */
433                 if (is_intra && band->is_2d_trans) {
434                     prev_dc      += trvec[0];
435                     trvec[0]      = prev_dc;
436                     col_flags[0] |= !!prev_dc;
437                 }
438
439                 /* apply inverse transform */
440                 band->inv_transform(trvec, band->buf + buf_offs,
441                                     band->pitch, col_flags);
442
443                 /* apply motion compensation */
444                 if (!is_intra)
445                     mc_with_delta_func(band->buf + buf_offs,
446                                        band->ref_buf + buf_offs + mv_y * band->pitch + mv_x,
447                                        band->pitch, mc_type);
448             } else {
449                 /* block not coded */
450                 /* for intra blocks apply the dc slant transform */
451                 /* for inter - perform the motion compensation without delta */
452                 if (is_intra && band->dc_transform) {
453                     band->dc_transform(&prev_dc, band->buf + buf_offs,
454                                        band->pitch, blk_size);
455                 } else
456                     mc_no_delta_func(band->buf + buf_offs,
457                                      band->ref_buf + buf_offs + mv_y * band->pitch + mv_x,
458                                      band->pitch, mc_type);
459             }
460
461             cbp >>= 1;
462         }// for blk
463     }// for mbn
464
465     align_get_bits(gb);
466
467     return 0;
468 }
469
470 void ff_ivi_process_empty_tile(AVCodecContext *avctx, IVIBandDesc *band,
471                                IVITile *tile, int32_t mv_scale)
472 {
473     int             x, y, need_mc, mbn, blk, num_blocks, mv_x, mv_y, mc_type;
474     int             offs, mb_offset, row_offset;
475     IVIMbInfo       *mb, *ref_mb;
476     const int16_t   *src;
477     int16_t         *dst;
478     void (*mc_no_delta_func)(int16_t *buf, const int16_t *ref_buf, uint32_t pitch,
479                              int mc_type);
480
481     offs       = tile->ypos * band->pitch + tile->xpos;
482     mb         = tile->mbs;
483     ref_mb     = tile->ref_mbs;
484     row_offset = band->mb_size * band->pitch;
485     need_mc    = 0; /* reset the mc tracking flag */
486
487     for (y = tile->ypos; y < (tile->ypos + tile->height); y += band->mb_size) {
488         mb_offset = offs;
489
490         for (x = tile->xpos; x < (tile->xpos + tile->width); x += band->mb_size) {
491             mb->xpos     = x;
492             mb->ypos     = y;
493             mb->buf_offs = mb_offset;
494
495             mb->type = 1; /* set the macroblocks type = INTER */
496             mb->cbp  = 0; /* all blocks are empty */
497
498             if (!band->qdelta_present && !band->plane && !band->band_num) {
499                 mb->q_delta = band->glob_quant;
500                 mb->mv_x    = 0;
501                 mb->mv_y    = 0;
502             }
503
504             if (band->inherit_qdelta && ref_mb)
505                 mb->q_delta = ref_mb->q_delta;
506
507             if (band->inherit_mv) {
508                 /* motion vector inheritance */
509                 if (mv_scale) {
510                     mb->mv_x = ivi_scale_mv(ref_mb->mv_x, mv_scale);
511                     mb->mv_y = ivi_scale_mv(ref_mb->mv_y, mv_scale);
512                 } else {
513                     mb->mv_x = ref_mb->mv_x;
514                     mb->mv_y = ref_mb->mv_y;
515                 }
516                 need_mc |= mb->mv_x || mb->mv_y; /* tracking non-zero motion vectors */
517             }
518
519             mb++;
520             if (ref_mb)
521                 ref_mb++;
522             mb_offset += band->mb_size;
523         } // for x
524         offs += row_offset;
525     } // for y
526
527     if (band->inherit_mv && need_mc) { /* apply motion compensation if there is at least one non-zero motion vector */
528         num_blocks = (band->mb_size != band->blk_size) ? 4 : 1; /* number of blocks per mb */
529         mc_no_delta_func = (band->blk_size == 8) ? ff_ivi_mc_8x8_no_delta
530                                                  : ff_ivi_mc_4x4_no_delta;
531
532         for (mbn = 0, mb = tile->mbs; mbn < tile->num_MBs; mb++, mbn++) {
533             mv_x = mb->mv_x;
534             mv_y = mb->mv_y;
535             if (!band->is_halfpel) {
536                 mc_type = 0; /* we have only fullpel vectors */
537             } else {
538                 mc_type = ((mv_y & 1) << 1) | (mv_x & 1);
539                 mv_x >>= 1;
540                 mv_y >>= 1; /* convert halfpel vectors into fullpel ones */
541             }
542
543             for (blk = 0; blk < num_blocks; blk++) {
544                 /* adjust block position in the buffer according with its number */
545                 offs = mb->buf_offs + band->blk_size * ((blk & 1) + !!(blk & 2) * band->pitch);
546                 mc_no_delta_func(band->buf + offs,
547                                  band->ref_buf + offs + mv_y * band->pitch + mv_x,
548                                  band->pitch, mc_type);
549             }
550         }
551     } else {
552         /* copy data from the reference tile into the current one */
553         src = band->ref_buf + tile->ypos * band->pitch + tile->xpos;
554         dst = band->buf     + tile->ypos * band->pitch + tile->xpos;
555         for (y = 0; y < tile->height; y++) {
556             memcpy(dst, src, tile->width*sizeof(band->buf[0]));
557             src += band->pitch;
558             dst += band->pitch;
559         }
560     }
561 }
562
563
564 #ifdef DEBUG
565 uint16_t ivi_calc_band_checksum (IVIBandDesc *band)
566 {
567     int         x, y;
568     int16_t     *src, checksum;
569
570     src = band->buf;
571     checksum = 0;
572
573     for (y = 0; y < band->height; src += band->pitch, y++)
574         for (x = 0; x < band->width; x++)
575             checksum += src[x];
576
577     return checksum;
578 }
579
580 int ivi_check_band (IVIBandDesc *band, const uint8_t *ref, int pitch)
581 {
582     int         x, y, result;
583     uint8_t     t1, t2;
584     int16_t    *src;
585
586     src = band->buf;
587     result = 0;
588
589     for (y = 0; y < band->height; src += band->pitch, y++) {
590         for (x = 0; x < band->width; x++) {
591             t1 = av_clip(src[x] + 128, 0, 255);
592             t2 = ref[x];
593             if (t1 != t2) {
594                 av_log(NULL, AV_LOG_ERROR, "Data mismatch: row %d, column %d\n",
595                        y / band->blk_size, x / band->blk_size);
596                 result = -1;
597             }
598         }
599         ref += pitch;
600     }
601
602     return result;
603 }
604 #endif
605
606 void ff_ivi_output_plane(IVIPlaneDesc *plane, uint8_t *dst, int dst_pitch)
607 {
608     int             x, y;
609     const int16_t   *src  = plane->bands[0].buf;
610     uint32_t        pitch = plane->bands[0].pitch;
611
612     if (!src)
613         return;
614
615     for (y = 0; y < plane->height; y++) {
616         for (x = 0; x < plane->width; x++)
617             dst[x] = av_clip_uint8(src[x] + 128);
618         src += pitch;
619         dst += dst_pitch;
620     }
621 }
622
623 /**
624  *  Decode an Indeo 4 or 5 band.
625  *
626  *  @param[in,out]  ctx    ptr to the decoder context
627  *  @param[in,out]  band   ptr to the band descriptor
628  *  @param[in]      avctx  ptr to the AVCodecContext
629  *  @return         result code: 0 = OK, -1 = error
630  */
631 static int decode_band(IVI45DecContext *ctx, int plane_num,
632                        IVIBandDesc *band, AVCodecContext *avctx)
633 {
634     int         result, i, t, idx1, idx2, pos;
635     IVITile     *tile;
636
637     band->buf     = band->bufs[ctx->dst_buf];
638     band->ref_buf = band->bufs[ctx->ref_buf];
639     band->data_ptr = ctx->frame_data + (get_bits_count(&ctx->gb) >> 3);
640
641     result = ctx->decode_band_hdr(ctx, band, avctx);
642     if (result) {
643         av_log(avctx, AV_LOG_ERROR, "Error while decoding band header: %d\n",
644                result);
645         return result;
646     }
647
648     if (band->is_empty) {
649         av_log(avctx, AV_LOG_ERROR, "Empty band encountered!\n");
650         return AVERROR_INVALIDDATA;
651     }
652
653     band->rv_map = &ctx->rvmap_tabs[band->rvmap_sel];
654
655     /* apply corrections to the selected rvmap table if present */
656     for (i = 0; i < band->num_corr; i++) {
657         idx1 = band->corr[i * 2];
658         idx2 = band->corr[i * 2 + 1];
659         FFSWAP(uint8_t, band->rv_map->runtab[idx1], band->rv_map->runtab[idx2]);
660         FFSWAP(int16_t, band->rv_map->valtab[idx1], band->rv_map->valtab[idx2]);
661     }
662
663     pos = get_bits_count(&ctx->gb);
664
665     for (t = 0; t < band->num_tiles; t++) {
666         tile = &band->tiles[t];
667
668         tile->is_empty = get_bits1(&ctx->gb);
669         if (tile->is_empty) {
670             ff_ivi_process_empty_tile(avctx, band, tile,
671                                       (ctx->planes[0].bands[0].mb_size >> 3) - (band->mb_size >> 3));
672             av_dlog(avctx, "Empty tile encountered!\n");
673         } else {
674             tile->data_size = ff_ivi_dec_tile_data_size(&ctx->gb);
675             if (!tile->data_size) {
676                 av_log(avctx, AV_LOG_ERROR, "Tile data size is zero!\n");
677                 return AVERROR_INVALIDDATA;
678             }
679
680             result = ctx->decode_mb_info(ctx, band, tile, avctx);
681             if (result < 0)
682                 break;
683
684             result = ff_ivi_decode_blocks(&ctx->gb, band, tile);
685             if (result < 0 || ((get_bits_count(&ctx->gb) - pos) >> 3) != tile->data_size) {
686                 av_log(avctx, AV_LOG_ERROR, "Corrupted tile data encountered!\n");
687                 break;
688             }
689
690             pos += tile->data_size << 3; // skip to next tile
691         }
692     }
693
694     /* restore the selected rvmap table by applying its corrections in reverse order */
695     for (i = band->num_corr-1; i >= 0; i--) {
696         idx1 = band->corr[i*2];
697         idx2 = band->corr[i*2+1];
698         FFSWAP(uint8_t, band->rv_map->runtab[idx1], band->rv_map->runtab[idx2]);
699         FFSWAP(int16_t, band->rv_map->valtab[idx1], band->rv_map->valtab[idx2]);
700     }
701
702 #ifdef DEBUG
703     if (band->checksum_present) {
704         uint16_t chksum = ivi_calc_band_checksum(band);
705         if (chksum != band->checksum) {
706             av_log(avctx, AV_LOG_ERROR,
707                    "Band checksum mismatch! Plane %d, band %d, received: %x, calculated: %x\n",
708                    band->plane, band->band_num, band->checksum, chksum);
709         }
710     }
711 #endif
712
713     align_get_bits(&ctx->gb);
714
715     return result;
716 }
717
718 int ff_ivi_decode_frame(AVCodecContext *avctx, void *data, int *data_size,
719                         AVPacket *avpkt)
720 {
721     IVI45DecContext *ctx = avctx->priv_data;
722     const uint8_t   *buf = avpkt->data;
723     int             buf_size = avpkt->size;
724     int             result, p, b;
725
726     init_get_bits(&ctx->gb, buf, buf_size * 8);
727     ctx->frame_data = buf;
728     ctx->frame_size = buf_size;
729
730     result = ctx->decode_pic_hdr(ctx, avctx);
731     if (result) {
732         av_log(avctx, AV_LOG_ERROR,
733                "Error while decoding picture header: %d\n", result);
734         return -1;
735     }
736
737     if (ctx->gop_flags & IVI5_IS_PROTECTED) {
738         av_log(avctx, AV_LOG_ERROR, "Password-protected clip!\n");
739         return -1;
740     }
741
742     ctx->switch_buffers(ctx);
743
744     //{ START_TIMER;
745
746     if (ctx->is_nonnull_frame(ctx)) {
747         for (p = 0; p < 3; p++) {
748             for (b = 0; b < ctx->planes[p].num_bands; b++) {
749                 result = decode_band(ctx, p, &ctx->planes[p].bands[b], avctx);
750                 if (result) {
751                     av_log(avctx, AV_LOG_ERROR,
752                            "Error while decoding band: %d, plane: %d\n", b, p);
753                     return -1;
754                 }
755             }
756         }
757     }
758
759     //STOP_TIMER("decode_planes"); }
760
761     /* If the bidirectional mode is enabled, next I and the following P frame will */
762     /* be sent together. Unfortunately the approach below seems to be the only way */
763     /* to handle the B-frames mode. That's exactly the same Intel decoders do.     */
764     if (avctx->codec_id == CODEC_ID_INDEO4 && ctx->frame_type == 0/*FRAMETYPE_INTRA*/) {
765         while (get_bits(&ctx->gb, 8)); // skip version string
766         skip_bits_long(&ctx->gb, 64);  // skip padding, TODO: implement correct 8-bytes alignment
767         if (get_bits_left(&ctx->gb) > 18 && show_bits(&ctx->gb, 18) == 0x3FFF8)
768             av_log(avctx, AV_LOG_ERROR, "Buffer contains IP frames!\n");
769     }
770
771     if (ctx->frame.data[0])
772         avctx->release_buffer(avctx, &ctx->frame);
773
774     ctx->frame.reference = 0;
775     if ((result = avctx->get_buffer(avctx, &ctx->frame)) < 0) {
776         av_log(avctx, AV_LOG_ERROR, "get_buffer() failed\n");
777         return result;
778     }
779
780     if (ctx->is_scalable) {
781         if (avctx->codec_id == CODEC_ID_INDEO4)
782             ff_ivi_recompose_haar(&ctx->planes[0], ctx->frame.data[0], ctx->frame.linesize[0], 4);
783         else
784             ff_ivi_recompose53   (&ctx->planes[0], ctx->frame.data[0], ctx->frame.linesize[0], 4);
785     } else {
786         ff_ivi_output_plane(&ctx->planes[0], ctx->frame.data[0], ctx->frame.linesize[0]);
787     }
788
789     ff_ivi_output_plane(&ctx->planes[2], ctx->frame.data[1], ctx->frame.linesize[1]);
790     ff_ivi_output_plane(&ctx->planes[1], ctx->frame.data[2], ctx->frame.linesize[2]);
791
792     *data_size = sizeof(AVFrame);
793     *(AVFrame*)data = ctx->frame;
794
795     return buf_size;
796 }
797
798 /**
799  *  Close Indeo5 decoder and clean up its context.
800  */
801 av_cold int ff_ivi_decode_close(AVCodecContext *avctx)
802 {
803     IVI45DecContext *ctx = avctx->priv_data;
804
805     ff_ivi_free_buffers(&ctx->planes[0]);
806
807     if (ctx->mb_vlc.cust_tab.table)
808         ff_free_vlc(&ctx->mb_vlc.cust_tab);
809
810     if (ctx->frame.data[0])
811         avctx->release_buffer(avctx, &ctx->frame);
812
813 #if IVI4_STREAM_ANALYSER
814     if (avctx->codec_id == CODEC_ID_INDEO4) {
815     if (ctx->is_scalable)
816         av_log(avctx, AV_LOG_ERROR, "This video uses scalability mode!\n");
817     if (ctx->uses_tiling)
818         av_log(avctx, AV_LOG_ERROR, "This video uses local decoding!\n");
819     if (ctx->has_b_frames)
820         av_log(avctx, AV_LOG_ERROR, "This video contains B-frames!\n");
821     if (ctx->has_transp)
822         av_log(avctx, AV_LOG_ERROR, "Transparency mode is enabled!\n");
823     if (ctx->uses_haar)
824         av_log(avctx, AV_LOG_ERROR, "This video uses Haar transform!\n");
825     if (ctx->uses_fullpel)
826         av_log(avctx, AV_LOG_ERROR, "This video uses fullpel motion vectors!\n");
827     }
828 #endif
829
830     return 0;
831 }
832
833
834 /**
835  * These are 2x8 predefined Huffman codebooks for coding macroblock/block
836  * signals. They are specified using "huffman descriptors" in order to
837  * avoid huge static tables. The decoding tables will be generated at
838  * startup from these descriptors.
839  */
840 const IVIHuffDesc ff_ivi_mb_huff_desc[8] = {
841     {8,  {0, 4, 5, 4, 4, 4, 6, 6}},
842     {12, {0, 2, 2, 3, 3, 3, 3, 5, 3, 2, 2, 2}},
843     {12, {0, 2, 3, 4, 3, 3, 3, 3, 4, 3, 2, 2}},
844     {12, {0, 3, 4, 4, 3, 3, 3, 3, 3, 2, 2, 2}},
845     {13, {0, 4, 4, 3, 3, 3, 3, 2, 3, 3, 2, 1, 1}},
846     {9,  {0, 4, 4, 4, 4, 3, 3, 3, 2}},
847     {10, {0, 4, 4, 4, 4, 3, 3, 2, 2, 2}},
848     {12, {0, 4, 4, 4, 3, 3, 2, 3, 2, 2, 2, 2}}
849 };
850
851 const IVIHuffDesc ff_ivi_blk_huff_desc[8] = {
852     {10, {1, 2, 3, 4, 4, 7, 5, 5, 4, 1}},
853     {11, {2, 3, 4, 4, 4, 7, 5, 4, 3, 3, 2}},
854     {12, {2, 4, 5, 5, 5, 5, 6, 4, 4, 3, 1, 1}},
855     {13, {3, 3, 4, 4, 5, 6, 6, 4, 4, 3, 2, 1, 1}},
856     {11, {3, 4, 4, 5, 5, 5, 6, 5, 4, 2, 2}},
857     {13, {3, 4, 5, 5, 5, 5, 6, 4, 3, 3, 2, 1, 1}},
858     {13, {3, 4, 5, 5, 5, 6, 5, 4, 3, 3, 2, 1, 1}},
859     {9,  {3, 4, 4, 5, 5, 5, 6, 5, 5}}
860 };
861
862
863 /**
864  *  Scan patterns shared between indeo4 and indeo5
865  */
866 const uint8_t ff_ivi_vertical_scan_8x8[64] = {
867     0,  8, 16, 24, 32, 40, 48, 56,
868     1,  9, 17, 25, 33, 41, 49, 57,
869     2, 10, 18, 26, 34, 42, 50, 58,
870     3, 11, 19, 27, 35, 43, 51, 59,
871     4, 12, 20, 28, 36, 44, 52, 60,
872     5, 13, 21, 29, 37, 45, 53, 61,
873     6, 14, 22, 30, 38, 46, 54, 62,
874     7, 15, 23, 31, 39, 47, 55, 63
875 };
876
877 const uint8_t ff_ivi_horizontal_scan_8x8[64] = {
878      0,  1,  2,  3,  4,  5,  6,  7,
879      8,  9, 10, 11, 12, 13, 14, 15,
880     16, 17, 18, 19, 20, 21, 22, 23,
881     24, 25, 26, 27, 28, 29, 30, 31,
882     32, 33, 34, 35, 36, 37, 38, 39,
883     40, 41, 42, 43, 44, 45, 46, 47,
884     48, 49, 50, 51, 52, 53, 54, 55,
885     56, 57, 58, 59, 60, 61, 62, 63
886 };
887
888 const uint8_t ff_ivi_direct_scan_4x4[16] = {
889     0, 1, 4, 8, 5, 2, 3, 6, 9, 12, 13, 10, 7, 11, 14, 15
890 };
891
892
893 /**
894  *  Run-value (RLE) tables.
895  */
896 const RVMapDesc ff_ivi_rvmap_tabs[9] = {
897 {   /* MapTab0 */
898     5, /* eob_sym */
899     2, /* esc_sym */
900     /* run table */
901     {1,  1,  0,  1,  1,  0,  1,  1,  2,  2,  1,  1,  1,  1,  3,  3,
902      1,  1,  2,  2,  1,  1,  4,  4,  1,  1,  1,  1,  2,  2,  5,  5,
903      1,  1,  3,  3,  1,  1,  6,  6,  1,  2,  1,  2,  7,  7,  1,  1,
904      8,  8,  1,  1,  4,  2,  1,  4,  2,  1,  3,  3,  1,  1,  1,  9,
905      9,  1,  2,  1,  2,  1,  5,  5,  1,  1, 10, 10,  1,  1,  3,  3,
906      2,  2,  1,  1, 11, 11,  6,  4,  4,  1,  6,  1,  2,  1,  2, 12,
907      8,  1, 12,  7,  8,  7,  1, 16,  1, 16,  1,  3,  3, 13,  1, 13,
908      2,  2,  1, 15,  1,  5, 14, 15,  1,  5, 14,  1, 17,  8, 17,  8,
909      1,  4,  4,  2,  2,  1, 25, 25, 24, 24,  1,  3,  1,  3,  1,  8,
910      6,  7,  6,  1, 18,  8, 18,  1,  7, 23,  2,  2, 23,  1,  1, 21,
911     22,  9,  9, 22, 19,  1, 21,  5, 19,  5,  1, 33, 20, 33, 20,  8,
912      4,  4,  1, 32,  2,  2,  8,  3, 32, 26,  3,  1,  7,  7, 26,  6,
913      1,  6,  1,  1, 16,  1, 10,  1, 10,  2, 16, 29, 28,  2, 29, 28,
914      1, 27,  5,  8,  5, 27,  1,  8,  3,  7,  3, 31, 41, 31,  1, 41,
915      6,  1,  6,  7,  4,  4,  1,  1,  2,  1,  2, 11, 34, 30, 11,  1,
916     30, 15, 15, 34, 36, 40, 36, 40, 35, 35, 37, 37, 39, 39, 38, 38},
917
918     /* value table */
919     { 1,  -1,   0,   2,  -2,   0,   3,  -3,   1,  -1,   4,  -4,   5,  -5,   1,  -1,
920       6,  -6,   2,  -2,   7,  -7,   1,  -1,   8,  -8,   9,  -9,   3,  -3,   1,  -1,
921      10, -10,   2,  -2,  11, -11,   1,  -1,  12,   4, -12,  -4,   1,  -1,  13, -13,
922       1,  -1,  14, -14,   2,   5,  15,  -2,  -5, -15,  -3,   3,  16, -16,  17,   1,
923      -1, -17,   6,  18,  -6, -18,   2,  -2,  19, -19,   1,  -1,  20, -20,   4,  -4,
924       7,  -7,  21, -21,   1,  -1,   2,   3,  -3,  22,  -2, -22,   8,  23,  -8,   1,
925       2, -23,  -1,   2,  -2,  -2,  24,   1, -24,  -1,  25,   5,  -5,   1, -25,  -1,
926       9,  -9,  26,   1, -26,   3,   1,  -1,  27,  -3,  -1, -27,   1,   3,  -1,  -3,
927      28,  -4,   4,  10, -10, -28,   1,  -1,   1,  -1,  29,   6, -29,  -6,  30,  -4,
928       3,   3,  -3, -30,   1,   4,  -1,  31,  -3,   1,  11, -11,  -1, -31,  32,  -1,
929      -1,   2,  -2,   1,   1, -32,   1,   4,  -1,  -4,  33,  -1,   1,   1,  -1,   5,
930       5,  -5, -33,  -1, -12,  12,  -5,  -7,   1,   1,   7,  34,   4,  -4,  -1,   4,
931     -34,  -4,  35,  36,  -2, -35,  -2, -36,   2,  13,   2,  -1,   1, -13,   1,  -1,
932      37,   1,  -5,   6,   5,  -1,  38,  -6,  -8,   5,   8,  -1,   1,   1, -37,  -1,
933       5,  39,  -5,  -5,   6,  -6, -38, -39, -14,  40,  14,   2,   1,   1,  -2, -40,
934      -1,  -2,   2,  -1,  -1,  -1,   1,   1,   1,  -1,   1,  -1,   1,  -1,   1,  -1}
935 },{
936     /* MapTab1 */
937     0,  /* eob_sym */
938     38, /* esc_sym */
939     /* run table */
940     {0,  1,  1,  2,  2,  3,  3,  4,  4,  5,  5,  6,  8,  6,  8,  7,
941      7,  9,  9, 10, 10, 11, 11,  1, 12,  1, 12, 13, 13, 16, 14, 16,
942     14, 15, 15, 17, 17, 18,  0, 18, 19, 20, 21, 19, 22, 21, 20, 22,
943     25, 24,  2, 25, 24, 23, 23,  2, 26, 28, 26, 28, 29, 27, 29, 27,
944     33, 33,  1, 32,  1,  3, 32, 30, 36,  3, 36, 30, 31, 31, 35, 34,
945     37, 41, 34, 35, 37,  4, 41,  4, 49,  8,  8, 49, 40, 38,  5, 38,
946     40, 39,  5, 39, 42, 43, 42,  7, 57,  6, 43, 44,  6, 50,  7, 44,
947     57, 48, 50, 48, 45, 45, 46, 47, 51, 46, 47, 58,  1, 51, 58,  1,
948     52, 59, 53,  9, 52, 55, 55, 59, 53, 56, 54, 56, 54,  9, 64, 64,
949     60, 63, 60, 63, 61, 62, 61, 62,  2, 10,  2, 10, 11,  1, 11, 13,
950     12,  1, 12, 13, 16, 16,  8,  8, 14,  3,  3, 15, 14, 15,  4,  4,
951      1, 17, 17,  5,  1,  7,  7,  5,  6,  1,  2,  2,  6, 22,  1, 25,
952     21, 22,  8, 24,  1, 21, 25, 24,  8, 18, 18, 23,  9, 20, 23, 33,
953     29, 33, 20,  1, 19,  1, 29, 36,  9, 36, 19, 41, 28, 57, 32,  3,
954     28,  3,  1, 27, 49, 49,  1, 32, 26, 26,  2,  4,  4,  7, 57, 41,
955      2,  7, 10,  5, 37, 16, 10, 27,  8,  8, 13, 16, 37, 13,  1,  5},
956
957     /* value table */
958     {0,   1,  -1,   1,  -1,   1,  -1,   1,  -1,   1,  -1,   1,   1,  -1,  -1,   1,
959     -1,   1,  -1,   1,  -1,   1,  -1,   2,   1,  -2,  -1,   1,  -1,   1,   1,  -1,
960     -1,   1,  -1,   1,  -1,   1,   0,  -1,   1,   1,   1,  -1,   1,  -1,  -1,  -1,
961      1,   1,   2,  -1,  -1,   1,  -1,  -2,   1,   1,  -1,  -1,   1,   1,  -1,  -1,
962      1,  -1,   3,   1,  -3,   2,  -1,   1,   1,  -2,  -1,  -1,  -1,   1,   1,   1,
963      1,   1,  -1,  -1,  -1,   2,  -1,  -2,   1,   2,  -2,  -1,   1,   1,   2,  -1,
964     -1,   1,  -2,  -1,   1,   1,  -1,   2,   1,   2,  -1,   1,  -2,  -1,  -2,  -1,
965     -1,   1,   1,  -1,   1,  -1,   1,   1,   1,  -1,  -1,   1,   4,  -1,  -1,  -4,
966      1,   1,   1,   2,  -1,  -1,   1,  -1,  -1,   1,  -1,  -1,   1,  -2,   1,  -1,
967      1,   1,  -1,  -1,   1,   1,  -1,  -1,   3,   2,  -3,  -2,   2,   5,  -2,   2,
968      2,  -5,  -2,  -2,  -2,   2,  -3,   3,   2,   3,  -3,   2,  -2,  -2,   3,  -3,
969      6,   2,  -2,   3,  -6,   3,  -3,  -3,   3,   7,  -4,   4,  -3,   2,  -7,   2,
970      2,  -2,  -4,   2,   8,  -2,  -2,  -2,   4,   2,  -2,   2,   3,   2,  -2,  -2,
971      2,   2,  -2,  -8,  -2,   9,  -2,   2,  -3,  -2,   2,  -2,   2,   2,   2,   4,
972     -2,  -4,  10,   2,   2,  -2,  -9,  -2,   2,  -2,   5,   4,  -4,   4,  -2,   2,
973     -5,  -4,  -3,   4,   2,  -3,   3,  -2,  -5,   5,   3,   3,  -2,  -3, -10,  -4}
974 },{
975     /* MapTab2 */
976     2,  /* eob_sym */
977     11, /* esc_sym */
978     /* run table */
979     {1,  1,  0,  2,  2,  1,  1,  3,  3,  4,  4,  0,  1,  1,  5,  5,
980      2,  2,  6,  6,  7,  7,  1,  8,  1,  8,  3,  3,  9,  9,  1,  2,
981      2,  1,  4, 10,  4, 10, 11, 11,  1,  5, 12, 12,  1,  5, 13, 13,
982      3,  3,  6,  6,  2,  2, 14, 14, 16, 16, 15,  7, 15,  8,  8,  7,
983      1,  1, 17, 17,  4,  4,  1,  1, 18, 18,  2,  2,  5,  5, 25,  3,
984      9,  3, 25,  9, 19, 24, 19, 24,  1, 21, 20,  1, 21, 22, 20, 22,
985     23, 23,  8,  6, 33,  6,  8, 33,  7,  7, 26, 26,  1, 32,  1, 32,
986     28,  4, 28, 10, 29, 27, 27, 10, 41,  4, 29,  2,  2, 41, 36, 31,
987     49, 31, 34, 30, 34, 36, 30, 35,  1, 49, 11,  5, 35, 11,  1,  3,
988      3,  5, 37, 37,  8, 40,  8, 40, 12, 12, 42, 42,  1, 38, 16, 57,
989      1,  6, 16, 39, 38,  6,  7,  7, 13, 13, 39, 43,  2, 43, 57,  2,
990     50,  9, 44,  9, 50,  4, 15, 48, 44,  4,  1, 15, 48, 14, 14,  1,
991     45, 45,  8,  3,  5,  8, 51, 47,  3, 46, 46, 47,  5, 51,  1, 17,
992     17, 58,  1, 58,  2, 52, 52,  2, 53,  7, 59,  6,  6, 56, 53, 55,
993      7, 55,  1, 54, 59, 56, 54, 10,  1, 10,  4, 60,  1, 60,  8,  4,
994      8, 64, 64, 61,  1, 63,  3, 63, 62, 61,  5, 11,  5,  3, 11, 62},
995
996     /* value table */
997     { 1,  -1,   0,   1,  -1,   2,  -2,   1,  -1,   1,  -1,   0,   3,  -3,   1,  -1,
998       2,  -2,   1,  -1,   1,  -1,   4,   1,  -4,  -1,   2,  -2,   1,  -1,   5,   3,
999      -3,  -5,   2,   1,  -2,  -1,   1,  -1,   6,   2,   1,  -1,  -6,  -2,   1,  -1,
1000       3,  -3,   2,  -2,   4,  -4,   1,  -1,   1,  -1,   1,   2,  -1,   2,  -2,  -2,
1001       7,  -7,   1,  -1,   3,  -3,   8,  -8,   1,  -1,   5,  -5,   3,  -3,   1,   4,
1002       2,  -4,  -1,  -2,   1,   1,  -1,  -1,   9,   1,   1,  -9,  -1,   1,  -1,  -1,
1003       1,  -1,   3,  -3,   1,   3,  -3,  -1,   3,  -3,   1,  -1,  10,   1, -10,  -1,
1004       1,   4,  -1,   2,   1,  -1,   1,  -2,   1,  -4,  -1,   6,  -6,  -1,   1,   1,
1005       1,  -1,   1,   1,  -1,  -1,  -1,   1,  11,  -1,  -2,   4,  -1,   2, -11,   5,
1006      -5,  -4,  -1,   1,   4,   1,  -4,  -1,  -2,   2,   1,  -1,  12,   1,  -2,   1,
1007     -12,   4,   2,   1,  -1,  -4,   4,  -4,   2,  -2,  -1,   1,   7,  -1,  -1,  -7,
1008      -1,  -3,   1,   3,   1,   5,   2,   1,  -1,  -5,  13,  -2,  -1,   2,  -2, -13,
1009       1,  -1,   5,   6,   5,  -5,   1,   1,  -6,   1,  -1,  -1,  -5,  -1,  14,   2,
1010      -2,   1, -14,  -1,   8,   1,  -1,  -8,   1,   5,   1,   5,  -5,   1,  -1,   1,
1011      -5,  -1,  15,   1,  -1,  -1,  -1,   3, -15,  -3,   6,   1,  16,  -1,   6,  -6,
1012      -6,   1,  -1,   1, -16,   1,   7,  -1,   1,  -1,  -6,  -3,   6,  -7,   3,  -1}
1013 },{
1014     /* MapTab3 */
1015     0,  /* eob_sym */
1016     35, /* esc_sym */
1017     /* run table */
1018     {0,  1,  1,  2,  2,  3,  3,  4,  4,  1,  1,  5,  5,  6,  6,  7,
1019      7,  8,  8,  9,  9,  2,  2, 10, 10,  1,  1, 11, 11, 12, 12,  3,
1020      3, 13, 13,  0, 14, 14, 16, 15, 16, 15,  4,  4, 17,  1, 17,  1,
1021      5,  5, 18, 18,  2,  2,  6,  6,  8, 19,  7,  8,  7, 19, 20, 20,
1022     21, 21, 22, 24, 22, 24, 23, 23,  1,  1, 25, 25,  3,  3, 26, 26,
1023      9,  9, 27, 27, 28, 28, 33, 29,  4, 33, 29,  1,  4,  1, 32, 32,
1024      2,  2, 31, 10, 30, 10, 30, 31, 34, 34,  5,  5, 36, 36, 35, 41,
1025     35, 11, 41, 11, 37,  1,  8,  8, 37,  6,  1,  6, 40,  7,  7, 40,
1026     12, 38, 12, 39, 39, 38, 49, 13, 49, 13,  3, 42,  3, 42, 16, 16,
1027     43, 43, 14, 14,  1,  1, 44, 15, 44, 15,  2,  2, 57, 48, 50, 48,
1028     57, 50,  4, 45, 45,  4, 46, 47, 47, 46,  1, 51,  1, 17, 17, 51,
1029      8,  9,  9,  5, 58,  8, 58,  5, 52, 52, 55, 56, 53, 56, 55, 59,
1030     59, 53, 54,  1,  6, 54,  7,  7,  6,  1,  2,  3,  2,  3, 64, 60,
1031     60, 10, 10, 64, 61, 62, 61, 63,  1, 63, 62,  1, 18, 24, 18,  4,
1032     25,  4,  8, 21, 21,  1, 24, 22, 25, 22,  8, 11, 19, 11, 23,  1,
1033     20, 23, 19, 20,  5, 12,  5,  1, 16,  2, 12, 13,  2, 13,  1, 16},
1034
1035     /* value table */
1036     { 0,   1,  -1,   1,  -1,   1,  -1,   1,  -1,   2,  -2,   1,  -1,   1,  -1,   1,
1037      -1,   1,  -1,   1,  -1,   2,  -2,   1,  -1,   3,  -3,   1,  -1,   1,  -1,   2,
1038      -2,   1,  -1,   0,   1,  -1,   1,   1,  -1,  -1,   2,  -2,   1,   4,  -1,  -4,
1039       2,  -2,   1,  -1,  -3,   3,   2,  -2,   2,   1,   2,  -2,  -2,  -1,   1,  -1,
1040       1,  -1,   1,   1,  -1,  -1,   1,  -1,   5,  -5,   1,  -1,   3,  -3,   1,  -1,
1041       2,  -2,   1,  -1,   1,  -1,   1,   1,   3,  -1,  -1,   6,  -3,  -6,  -1,   1,
1042       4,  -4,   1,   2,   1,  -2,  -1,  -1,   1,  -1,   3,  -3,   1,  -1,   1,   1,
1043      -1,   2,  -1,  -2,   1,   7,  -3,   3,  -1,   3,  -7,  -3,   1,  -3,   3,  -1,
1044       2,   1,  -2,   1,  -1,  -1,   1,   2,  -1,  -2,  -4,  -1,   4,   1,   2,  -2,
1045       1,  -1,  -2,   2,   8,  -8,  -1,   2,   1,  -2,  -5,   5,   1,  -1,  -1,   1,
1046      -1,   1,   4,  -1,   1,  -4,  -1,  -1,   1,   1,   9,   1,  -9,   2,  -2,  -1,
1047      -4,   3,  -3,  -4,  -1,   4,   1,   4,   1,  -1,   1,  -1,   1,   1,  -1,   1,
1048      -1,  -1,  -1,  10,   4,   1,   4,  -4,  -4, -10,   6,   5,  -6,  -5,   1,  -1,
1049       1,   3,  -3,  -1,   1,  -1,  -1,  -1,  11,   1,   1, -11,  -2,  -2,   2,   5,
1050      -2,  -5,  -5,   2,  -2,  12,   2,  -2,   2,   2,   5,  -3,  -2,   3,  -2, -12,
1051      -2,   2,   2,   2,  -5,   3,   5,  13,  -3,   7,  -3,  -3,  -7,   3, -13,   3}
1052 },{
1053     /* MapTab4 */
1054     0,  /* eob_sym */
1055     34, /* esc_sym */
1056     /* run table */
1057     {0,  1,  1,  1,  2,  2,  1,  3,  3,  1,  1,  1,  4,  4,  1,  5,
1058      2,  1,  5,  2,  1,  1,  6,  6,  1,  1,  1,  1,  1,  7,  3,  1,
1059      2,  3,  0,  1,  2,  7,  1,  1,  1,  8,  1,  1,  8,  1,  1,  1,
1060      9,  1,  9,  1,  2,  1,  1,  2,  1,  1, 10,  4,  1, 10,  1,  4,
1061      1,  1,  1,  1,  1,  3,  1,  1,  1,  3,  2,  1,  5,  1,  1,  1,
1062      2,  5,  1, 11,  1, 11,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
1063      2,  1,  6,  1,  6,  1,  1,  2,  1,  1,  1,  1,  1,  1,  1, 12,
1064      3,  1, 12,  1,  1,  1,  2,  1,  1,  3,  1,  1,  1,  1,  1,  1,
1065      4,  1,  1,  1,  2,  1,  1,  4,  1,  1,  1,  1,  1,  1,  2,  1,
1066      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  3,  1,  2,  1,  1,  5,
1067      1,  1,  1,  1,  1,  7,  1,  7,  1,  1,  2,  3,  1,  1,  1,  1,
1068      5,  1,  1,  1,  1,  1,  1,  2, 13,  1,  1,  1,  1,  1,  1,  1,
1069      1,  1,  1,  1,  1,  1,  1,  1, 13,  2,  1,  1,  4,  1,  1,  1,
1070      3,  1,  6,  1,  1,  1, 14,  1,  1,  1,  1,  1, 14,  6,  1,  1,
1071      1,  1, 15,  2,  4,  1,  2,  3, 15,  1,  1,  1,  8,  1,  1,  8,
1072      1,  1,  1,  1,  1,  1,  1,  1,  2,  1,  1,  1,  1,  1,  1,  1},
1073
1074     /* value table */
1075     { 0,   1,  -1,   2,   1,  -1,  -2,   1,  -1,   3,  -3,   4,   1,  -1,  -4,   1,
1076       2,   5,  -1,  -2,  -5,   6,   1,  -1,  -6,   7,  -7,   8,  -8,   1,   2,   9,
1077       3,  -2,   0,  -9,  -3,  -1,  10, -10,  11,   1, -11,  12,  -1, -12,  13, -13,
1078       1,  14,  -1, -14,   4,  15, -15,  -4,  16, -16,   1,   2,  17,  -1, -17,  -2,
1079      18, -18,  19, -19,  20,   3, -20,  21, -21,  -3,   5,  22,   2, -22, -23,  23,
1080      -5,  -2,  24,   1, -24,  -1,  25, -25,  26, -26, -27,  27,  28,  29, -28, -29,
1081       6,  30,   2, -31,  -2, -30,  31,  -6, -32,  32,  33, -33,  34, -35, -34,   1,
1082       4, -36,  -1,  35,  37,  36,   7, -37,  38,  -4, -38,  39,  41,  40, -40, -39,
1083       3,  42, -43, -41,  -7, -42,  43,  -3,  44, -44,  45, -45,  46,  47,   8, -47,
1084     -48, -46,  50, -50,  48,  49,  51, -49,  52, -52,   5, -51,  -8, -53,  53,   3,
1085     -56,  56,  55,  54, -54,   2,  60,  -2, -55,  58,   9,  -5,  59,  57, -57, -63,
1086      -3, -58, -60, -61,  61, -59, -62,  -9,   1,  64,  62,  69, -64,  63,  65, -67,
1087     -68,  66, -65,  68, -66, -69,  67, -70,  -1,  10,  71, -71,   4,  73,  72,  70,
1088       6, -76,  -3,  74, -78, -74,   1,  78,  80, -72, -75,  76,  -1,   3, -73,  79,
1089      75,  77,   1,  11,  -4, -79, -10,  -6,  -1, -77, -83, -80,   2,  81, -84,  -2,
1090      83, -81,  82, -82,  84, -87, -86,  85, -11, -85,  86, -89,  87, -88,  88,  89}
1091 },{
1092     /* MapTab5 */
1093     2,  /* eob_sym */
1094     33, /* esc_sym */
1095     /* run table */
1096     {1,  1,  0,  2,  1,  2,  1,  3,  3,  1,  1,  4,  4,  2,  2,  1,
1097      1,  5,  5,  6,  1,  6,  1,  7,  7,  3,  3,  2,  8,  2,  8,  1,
1098      1,  0,  9,  9,  1,  1, 10,  4, 10,  4, 11, 11,  2,  1,  2,  1,
1099     12, 12,  3,  3,  1,  1, 13,  5,  5, 13, 14,  1,  1, 14,  2,  2,
1100      6,  6, 15,  1,  1, 15, 16,  4,  7, 16,  4,  7,  1,  1,  3,  3,
1101      8,  8,  2,  2,  1,  1, 17, 17,  1,  1, 18, 18,  5,  5,  2,  2,
1102      1,  1,  9, 19,  9, 19, 20,  3,  3, 20,  1, 10, 21,  1, 10,  4,
1103      4, 21, 22,  6,  6, 22,  1,  1, 23, 24,  2,  2, 23, 24, 11,  1,
1104      1, 11,  7, 25,  7,  1,  1, 25,  8,  8,  3, 26,  3,  1, 12,  2,
1105      2, 26,  1, 12,  5,  5, 27,  4,  1,  4,  1, 27, 28,  1, 28, 13,
1106      1, 13,  2, 29,  2,  1, 32,  6,  1, 30, 14, 29, 14,  6,  3, 31,
1107      3,  1, 30,  1, 32, 31, 33,  9, 33,  1,  1,  7,  9,  7,  2,  2,
1108      1,  1,  4, 36, 34,  4,  5, 10, 10,  5, 34,  1,  1, 35,  8,  8,
1109     36,  3, 35,  1, 15,  3,  2,  1, 16, 15, 16,  2, 37,  1, 37,  1,
1110      1,  1,  6,  6, 38,  1, 38, 11,  1, 39, 39, 40, 11,  2, 41,  4,
1111     40,  1,  2,  4,  1,  1,  1, 41,  3,  1,  3,  1,  5,  7,  5,  7},
1112
1113     /* value table */
1114     { 1,  -1,   0,   1,   2,  -1,  -2,   1,  -1,   3,  -3,   1,  -1,   2,  -2,   4,
1115      -4,   1,  -1,   1,   5,  -1,  -5,   1,  -1,   2,  -2,   3,   1,  -3,  -1,   6,
1116      -6,   0,   1,  -1,   7,  -7,   1,   2,  -1,  -2,   1,  -1,   4,   8,  -4,  -8,
1117       1,  -1,   3,  -3,   9,  -9,   1,   2,  -2,  -1,   1,  10, -10,  -1,   5,  -5,
1118       2,  -2,   1,  11, -11,  -1,   1,   3,   2,  -1,  -3,  -2,  12, -12,   4,  -4,
1119       2,  -2,  -6,   6,  13, -13,   1,  -1,  14, -14,   1,  -1,   3,  -3,   7,  -7,
1120      15, -15,   2,   1,  -2,  -1,   1,   5,  -5,  -1, -16,   2,   1,  16,  -2,   4,
1121      -4,  -1,   1,   3,  -3,  -1,  17, -17,   1,   1,  -8,   8,  -1,  -1,   2,  18,
1122     -18,  -2,   3,   1,  -3,  19, -19,  -1,   3,  -3,   6,   1,  -6,  20,   2,   9,
1123      -9,  -1, -20,  -2,   4,  -4,   1,  -5,  21,   5, -21,  -1,   1, -22,  -1,   2,
1124      22,  -2,  10,   1, -10,  23,   1,   4, -23,   1,   2,  -1,  -2,  -4,  -7,   1,
1125       7, -24,  -1,  24,  -1,  -1,   1,   3,  -1, -25,  25,   4,  -3,  -4,  11, -11,
1126      26, -26,   6,   1,   1,  -6,  -5,  -3,   3,   5,  -1, -27,  27,   1,   4,  -4,
1127      -1,  -8,  -1,  28,   2,   8, -12, -28,  -2,  -2,   2,  12,  -1,  29,   1, -29,
1128      30, -30,   5,  -5,   1, -31,  -1,   3,  31,  -1,   1,   1,  -3, -13,   1,  -7,
1129      -1, -32,  13,   7,  32,  33, -33,  -1,  -9, -34,   9,  34,  -6,   5,   6,  -5}
1130 },{
1131     /* MapTab6 */
1132     2,  /* eob_sym */
1133     13, /* esc_sym */
1134     /* run table */
1135     {1,  1,  0,  1,  1,  2,  2,  1,  1,  3,  3,  1,  1,  0,  2,  2,
1136      4,  1,  4,  1,  1,  1,  5,  5,  1,  1,  6,  6,  2,  2,  1,  1,
1137      3,  3,  7,  7,  1,  1,  8,  8,  1,  1,  2,  2,  1,  9,  1,  9,
1138      4,  4, 10,  1,  1, 10,  1,  1, 11, 11,  3,  3,  1,  2,  1,  2,
1139      1,  1, 12, 12,  5,  5,  1,  1, 13,  1,  1, 13,  2,  2,  1,  1,
1140      6,  6,  1,  1,  4, 14,  4, 14,  3,  1,  3,  1,  1,  1, 15,  7,
1141     15,  2,  2,  7,  1,  1,  1,  8,  1,  8, 16, 16,  1,  1,  1,  1,
1142      2,  1,  1,  2,  1,  1,  3,  5,  5,  3,  4,  1,  1,  4,  1,  1,
1143     17, 17,  9,  1,  1,  9,  2,  2,  1,  1, 10, 10,  1,  6,  1,  1,
1144      6, 18,  1,  1, 18,  1,  1,  1,  2,  2,  3,  1,  3,  1,  1,  1,
1145      4,  1, 19,  1, 19,  7,  1,  1, 20,  1,  4, 20,  1,  7, 11,  2,
1146      1, 11, 21,  2,  8,  5,  1,  8,  1,  5, 21,  1,  1,  1, 22,  1,
1147      1, 22,  1,  1,  3,  3,  1, 23,  2, 12, 24,  1,  1,  2,  1,  1,
1148     12, 23,  1,  1, 24,  1,  1,  1,  4,  1,  1,  1,  2,  1,  6,  6,
1149      4,  2,  1,  1,  1,  1,  1,  1,  1, 14, 13,  3,  1, 25,  9, 25,
1150     14,  1,  9,  3, 13,  1,  1,  1,  1,  1, 10,  1,  1,  2, 10,  2},
1151
1152     /* value table */
1153     {-20,  -1,   0,   2,  -2,   1,  -1,   3,  -3,   1,  -1,   4,  -4,   0,   2,  -2,
1154        1,   5,  -1,  -5,   6,  -6,   1,  -1,   7,  -7,   1,  -1,   3,  -3,   8,  -8,
1155        2,  -2,   1,  -1,   9,  -9,   1,  -1,  10, -10,   4,  -4,  11,   1, -11,  -1,
1156        2,  -2,   1,  12, -12,  -1,  13, -13,   1,  -1,   3,  -3,  14,   5, -14,  -5,
1157      -15,  15,  -1,   1,   2,  -2,  16, -16,   1,  17, -17,  -1,   6,  -6,  18, -18,
1158        2,  -2, -19,  19,  -3,   1,   3,  -1,   4,  20,  -4,   1, -21,  21,   1,   2,
1159       -1,  -7,   7,  -2,  22, -22,  23,   2, -23,  -2,   1,  -1, -24,  24, -25,  25,
1160       -8, -26,  26,   8, -27,  27,   5,   3,  -3,  -5,  -4,  28, -28,   4,  29, -29,
1161        1,  -1,  -2, -30,  30,   2,   9,  -9, -31,  31,   2,  -2, -32,   3,  32, -33,
1162       -3,   1,  33, -34,  -1,  34, -35,  35, -10,  10,  -6,  36,   6, -36,  37, -37,
1163       -5,  38,   1, -38,  -1,   3,  39, -39,  -1,  40,   5,   1, -40,  -3,   2, -11,
1164      -41,  -2,   1,  11,  -3,  -4,  41,   3,  42,   4,  -1, -43, -42,  43,   1, -44,
1165       45,  -1,  44, -45,  -7,   7, -46,   1, -12,   2,   1, -47,  46,  12,  47,  48,
1166       -2,  -1, -48,  49,  -1, -50, -49,  50,  -6, -51,  51,  52, -13,  53,  -4,   4,
1167        6,  13, -53, -52, -54,  55,  54, -55, -56,  -2,   2,  -8,  56,   1,  -3,  -1,
1168        2,  58,   3,   8,  -2,  57, -58, -60, -59, -57,  -3,  60,  59, -14,   3,  14}
1169 },{
1170     /* MapTab7 */
1171     2,  /* eob_sym */
1172     38, /* esc_sym */
1173     /* run table */
1174     {1,  1,  0,  2,  2,  1,  1,  3,  3,  4,  4,  5,  5,  1,  1,  6,
1175      6,  2,  2,  7,  7,  8,  8,  1,  1,  3,  3,  9,  9, 10, 10,  1,
1176      1,  2,  2,  4,  4, 11,  0, 11, 12, 12, 13, 13,  1,  1,  5,  5,
1177     14, 14, 15, 16, 15, 16,  3,  3,  1,  6,  1,  6,  2,  2,  7,  7,
1178      8,  8, 17, 17,  1,  1,  4,  4, 18, 18,  2,  2,  1, 19,  1, 20,
1179     19, 20, 21, 21,  3,  3, 22, 22,  5,  5, 24,  1,  1, 23,  9, 23,
1180     24,  9,  2,  2, 10,  1,  1, 10,  6,  6, 25,  4,  4, 25,  7,  7,
1181     26,  8,  1,  8,  3,  1, 26,  3, 11, 11, 27, 27,  2, 28,  1,  2,
1182     28,  1, 12, 12,  5,  5, 29, 13, 13, 29, 32,  1,  1, 33, 31, 30,
1183     32,  4, 30, 33,  4, 31,  3, 14,  1,  1,  3, 34, 34,  2,  2, 14,
1184      6,  6, 35, 36, 35, 36,  1, 15,  1, 16, 16, 15,  7,  9,  7,  9,
1185     37,  8,  8, 37,  1,  1, 39,  2, 38, 39,  2, 40,  5, 38, 40,  5,
1186      3,  3,  4,  4, 10, 10,  1,  1,  1,  1, 41,  2, 41,  2,  6,  6,
1187      1,  1, 11, 42, 11, 43,  3, 42,  3, 17,  4, 43,  1, 17,  7,  1,
1188      8, 44,  4,  7, 44,  5,  8,  2,  5,  1,  2, 48, 45,  1, 12, 45,
1189     12, 48, 13, 13,  1,  9,  9, 46,  1, 46, 47, 47, 49, 18, 18, 49},
1190
1191     /* value table */
1192     { 1,  -1,   0,   1,  -1,   2,  -2,   1,  -1,   1,  -1,   1,  -1,   3,  -3,   1,
1193      -1,  -2,   2,   1,  -1,   1,  -1,   4,  -4,  -2,   2,   1,  -1,   1,  -1,   5,
1194      -5,  -3,   3,   2,  -2,   1,   0,  -1,   1,  -1,   1,  -1,   6,  -6,   2,  -2,
1195       1,  -1,   1,   1,  -1,  -1,  -3,   3,   7,   2,  -7,  -2,  -4,   4,   2,  -2,
1196       2,  -2,   1,  -1,   8,  -8,   3,  -3,   1,  -1,  -5,   5,   9,   1,  -9,   1,
1197      -1,  -1,   1,  -1,  -4,   4,   1,  -1,   3,  -3,   1, -10,  10,   1,   2,  -1,
1198      -1,  -2,   6,  -6,   2,  11, -11,  -2,   3,  -3,   1,  -4,   4,  -1,   3,  -3,
1199       1,   3,  12,  -3,  -5, -12,  -1,   5,   2,  -2,   1,  -1,  -7,   1,  13,   7,
1200      -1, -13,   2,  -2,   4,  -4,   1,   2,  -2,  -1,   1,  14, -14,   1,   1,   1,
1201      -1,  -5,  -1,  -1,   5,  -1,  -6,   2, -15,  15,   6,   1,  -1,  -8,   8,  -2,
1202      -4,   4,   1,   1,  -1,  -1,  16,   2, -16,  -2,   2,  -2,   4,   3,  -4,  -3,
1203      -1,  -4,   4,   1, -17,  17,  -1,  -9,   1,   1,   9,   1,  -5,  -1,  -1,   5,
1204      -7,   7,   6,  -6,   3,  -3,  18, -18,  19, -19,   1, -10,  -1,  10,  -5,   5,
1205      20, -20,  -3,   1,   3,   1,   8,  -1,  -8,   2,   7,  -1, -21,  -2,   5,  21,
1206       5,  -1,  -7,  -5,   1,  -6,  -5, -11,   6,  22,  11,   1,   1, -22,  -3,  -1,
1207       3,  -1,   3,  -3, -23,   4,  -4,   1,  23,  -1,   1,  -1,   1,  -2,   2,  -1}
1208 },{
1209     /* MapTab8 */
1210     4,  /* eob_sym */
1211     11, /* esc_sym */
1212     /* run table */
1213     {1,  1,  1,  1,  0,  2,  2,  1,  1,  3,  3,  0,  1,  1,  2,  2,
1214      4,  4,  1,  1,  5,  5,  1,  1,  2,  2,  3,  3,  6,  6,  1,  1,
1215      7,  7,  8,  1,  8,  2,  2,  1,  4,  4,  1,  3,  1,  3,  9,  9,
1216      2,  2,  1,  5,  1,  5, 10, 10,  1,  1, 11, 11,  3,  6,  3,  4,
1217      4,  6,  2,  2,  1, 12,  1, 12,  7, 13,  7, 13,  1,  1,  8,  8,
1218      2,  2, 14, 14, 16, 15, 16,  5,  5,  1,  3, 15,  1,  3,  4,  4,
1219      1,  1, 17, 17,  2,  2,  6,  6,  1, 18,  1, 18, 22, 21, 22, 21,
1220     25, 24, 25, 19,  9, 20,  9, 23, 19, 24, 20,  3, 23,  7,  3,  1,
1221      1,  7, 28, 26, 29,  5, 28, 26,  5,  8, 29,  4,  8, 27,  2,  2,
1222      4, 27,  1,  1, 10, 36, 10, 33, 33, 36, 30,  1, 32, 32,  1, 30,
1223      6, 31, 31, 35,  3,  6, 11, 11,  3,  2, 35,  2, 34,  1, 34,  1,
1224     37, 37, 12,  7, 12,  5, 41,  5,  4,  7,  1,  8, 13,  4,  1, 41,
1225     13, 38,  8, 38,  9,  1, 40, 40,  9,  1, 39,  2,  2, 49, 39, 42,
1226      3,  3, 14, 16, 49, 14, 16, 42, 43, 43,  6,  6, 15,  1,  1, 15,
1227     44, 44,  1,  1, 50, 48,  4,  5,  4,  7,  5,  2, 10, 10, 48,  7,
1228     50, 45,  2,  1, 45,  8,  8,  1, 46, 46,  3, 47, 47,  3,  1,  1},
1229
1230     /* value table */
1231     { 1,  -1,   2,  -2,   0,   1,  -1,   3,  -3,   1,  -1,   0,   4,  -4,   2,  -2,
1232       1,  -1,   5,  -5,   1,  -1,   6,  -6,   3,  -3,   2,  -2,   1,  -1,   7,  -7,
1233       1,  -1,   1,   8,  -1,   4,  -4,  -8,   2,  -2,   9,   3,  -9,  -3,   1,  -1,
1234       5,  -5,  10,   2, -10,  -2,   1,  -1,  11, -11,   1,  -1,  -4,   2,   4,   3,
1235      -3,  -2,   6,  -6,  12,   1, -12,  -1,   2,   1,  -2,  -1,  13, -13,   2,  -2,
1236       7,  -7,   1,  -1,   1,   1,  -1,   3,  -3,  14,   5,  -1, -14,  -5,   4,  -4,
1237      15, -15,   1,  -1,   8,  -8,  -3,   3,  16,   1, -16,  -1,   1,   1,  -1,  -1,
1238       1,   1,  -1,   1,   2,   1,  -2,   1,  -1,  -1,  -1,   6,  -1,   3,  -6,  17,
1239     -17,  -3,   1,   1,   1,   4,  -1,  -1,  -4,   3,  -1,   5,  -3,  -1,  -9,   9,
1240      -5,   1,  18, -18,   2,   1,  -2,   1,  -1,  -1,   1,  19,  -1,   1, -19,  -1,
1241       4,   1,  -1,   1,   7,  -4,  -2,   2,  -7,  10,  -1, -10,   1,  20,  -1, -20,
1242       1,  -1,   2,   4,  -2,   5,   1,  -5,   6,  -4,  21,   4,   2,  -6, -21,  -1,
1243      -2,   1,  -4,  -1,  -3,  22,  -1,   1,   3, -22,  -1,  11, -11,   1,   1,   1,
1244       8,  -8,   2,   2,  -1,  -2,  -2,  -1,   1,  -1,  -5,   5,   2,  23, -23,  -2,
1245       1,  -1,  24, -24,  -1,  -1,   7,   6,  -7,   5,  -6,  12,  -3,   3,   1,  -5,
1246       1,   1, -12,  25,  -1,  -5,   5, -25,  -1,   1,   9,   1,  -1,  -9,  26, -26}
1247 }
1248 };