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