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