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