git.sesse.net Git - ffmpeg/blob - libavcodec/ivi_common.c

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