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