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 FFmpeg.
   7  *
   8  * FFmpeg is free software; you can redistribute it and/or
   9  * modify it under the terms of the GNU Lesser General Public
  10  * License as published by the Free Software Foundation; either
  11  * version 2.1 of the License, or (at your option) any later version.
  12  *
  13  * FFmpeg is distributed in the hope that it will be useful,
  14  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  15  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  16  * Lesser General Public License for more details.
  17  *
  18  * You should have received a copy of the GNU Lesser General Public
  19  * License along with FFmpeg; if not, write to the Free Software
  20  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
  21  */
  22
  23 /**
  24  * @file
  25  * This file contains functions and data shared by both Indeo4 and
  26  * Indeo5 decoders.
  27  */
  28
  29 #define BITSTREAM_READER_LE
  30 #include "avcodec.h"
  31 #include "get_bits.h"
  32 #include "ivi_common.h"
  33 #include "libavutil/common.h"
  34 #include "ivi_dsp.h"
  35
  36 extern const IVIHuffDesc ff_ivi_mb_huff_desc[8];  ///< static macroblock huffman tables
  37 extern const IVIHuffDesc ff_ivi_blk_huff_desc[8]; ///< static block huffman tables
  38
  39 VLC ff_ivi_mb_vlc_tabs [8];
  40 VLC ff_ivi_blk_vlc_tabs[8];
  41
  42 /**
  43  *  Reverse "nbits" bits of the value "val" and return the result
  44  *  in the least significant bits.
  45  */
  46 static uint16_t inv_bits(uint16_t val, int nbits)
  47 {
  48     uint16_t res;
  49
  50     if (nbits <= 8) {
  51         res = av_reverse[val] >> (8-nbits);
  52     } else
  53         res = ((av_reverse[val & 0xFF] << 8) + (av_reverse[val >> 8])) >> (16-nbits);
  54
  55     return res;
  56 }
  57
  58 int ff_ivi_create_huff_from_desc(const IVIHuffDesc *cb, VLC *vlc, int flag)
  59 {
  60     int         pos, i, j, codes_per_row, prefix, not_last_row;
  61     uint16_t    codewords[256]; /* FIXME: move this temporal storage out? */
  62     uint8_t     bits[256];
  63
  64     pos = 0; /* current position = 0 */
  65
  66     for (i = 0; i < cb->num_rows; i++) {
  67         codes_per_row = 1 << cb->xbits[i];
  68         not_last_row  = (i != cb->num_rows - 1);
  69         prefix        = ((1 << i) - 1) << (cb->xbits[i] + not_last_row);
  70
  71         for (j = 0; j < codes_per_row; j++) {
  72             if (pos >= 256) /* Some Indeo5 codebooks can have more than 256 */
  73                 break;      /* elements, but only 256 codes are allowed! */
  74
  75             bits[pos] = i + cb->xbits[i] + not_last_row;
  76             if (bits[pos] > IVI_VLC_BITS)
  77                 return -1; /* invalid descriptor */
  78
  79             codewords[pos] = inv_bits((prefix | j), bits[pos]);
  80             if (!bits[pos])
  81                 bits[pos] = 1;
  82
  83             pos++;
  84         }//for j
  85     }//for i
  86
  87     /* number of codewords = pos */
  88     return init_vlc(vlc, IVI_VLC_BITS, pos, bits, 1, 1, codewords, 2, 2,
  89                     (flag ? INIT_VLC_USE_NEW_STATIC : 0) | INIT_VLC_LE);
  90 }
  91
  92 void ff_ivi_init_static_vlc(void)
  93 {
  94     int i;
  95     static VLC_TYPE table_data[8192 * 16][2];
  96     static int initialized_vlcs = 0;
  97
  98     if (initialized_vlcs)
  99         return;
 100     for (i = 0; i < 8; i++) {
 101         ff_ivi_mb_vlc_tabs[i].table = table_data + i * 2 * 8192;
 102         ff_ivi_mb_vlc_tabs[i].table_allocated = 8192;
 103         ff_ivi_create_huff_from_desc(&ff_ivi_mb_huff_desc[i],  &ff_ivi_mb_vlc_tabs[i],  1);
 104         ff_ivi_blk_vlc_tabs[i].table = table_data + (i * 2 + 1) * 8192;
 105         ff_ivi_blk_vlc_tabs[i].table_allocated = 8192;
 106         ff_ivi_create_huff_from_desc(&ff_ivi_blk_huff_desc[i], &ff_ivi_blk_vlc_tabs[i], 1);
 107     }
 108     initialized_vlcs = 1;
 109 }
 110
 111 int ff_ivi_dec_huff_desc(GetBitContext *gb, int desc_coded, int which_tab,
 112                          IVIHuffTab *huff_tab, AVCodecContext *avctx)
 113 {
 114     int         i, result;
 115     IVIHuffDesc new_huff;
 116
 117     if (!desc_coded) {
 118         /* select default table */
 119         huff_tab->tab = (which_tab) ? &ff_ivi_blk_vlc_tabs[7]
 120             : &ff_ivi_mb_vlc_tabs [7];
 121     } else {
 122         huff_tab->tab_sel = get_bits(gb, 3);
 123         if (huff_tab->tab_sel == 7) {
 124             /* custom huffman table (explicitly encoded) */
 125             new_huff.num_rows = get_bits(gb, 4);
 126
 127             for (i = 0; i < new_huff.num_rows; i++)
 128                 new_huff.xbits[i] = get_bits(gb, 4);
 129
 130             /* Have we got the same custom table? Rebuild if not. */
 131             if (ff_ivi_huff_desc_cmp(&new_huff, &huff_tab->cust_desc)) {
 132                 ff_ivi_huff_desc_copy(&huff_tab->cust_desc, &new_huff);
 133
 134                 if (huff_tab->cust_tab.table)
 135                     free_vlc(&huff_tab->cust_tab);
 136                 result = ff_ivi_create_huff_from_desc(&huff_tab->cust_desc,
 137                         &huff_tab->cust_tab, 0);
 138                 if (result) {
 139                     av_log(avctx, AV_LOG_ERROR,
 140                            "Error while initializing custom vlc table!\n");
 141                     return -1;
 142                 }
 143             }
 144             huff_tab->tab = &huff_tab->cust_tab;
 145         } else {
 146             /* select one of predefined tables */
 147             huff_tab->tab = (which_tab) ? &ff_ivi_blk_vlc_tabs[huff_tab->tab_sel]
 148                 : &ff_ivi_mb_vlc_tabs [huff_tab->tab_sel];
 149         }
 150     }
 151
 152     return 0;
 153 }
 154
 155 int ff_ivi_huff_desc_cmp(const IVIHuffDesc *desc1, const IVIHuffDesc *desc2)
 156 {
 157     return    desc1->num_rows != desc2->num_rows
 158            || memcmp(desc1->xbits, desc2->xbits, desc1->num_rows);
 159 }
 160
 161 void ff_ivi_huff_desc_copy(IVIHuffDesc *dst, const IVIHuffDesc *src)
 162 {
 163     dst->num_rows = src->num_rows;
 164     memcpy(dst->xbits, src->xbits, src->num_rows);
 165 }
 166
 167 int av_cold ff_ivi_init_planes(IVIPlaneDesc *planes, const IVIPicConfig *cfg)
 168 {
 169     int         p, b;
 170     uint32_t    b_width, b_height, align_fac, width_aligned, height_aligned, buf_size;
 171     IVIBandDesc *band;
 172
 173     ff_ivi_free_buffers(planes);
 174
 175     /* fill in the descriptor of the luminance plane */
 176     planes[0].width     = cfg->pic_width;
 177     planes[0].height    = cfg->pic_height;
 178     planes[0].num_bands = cfg->luma_bands;
 179
 180     /* fill in the descriptors of the chrominance planes */
 181     planes[1].width     = planes[2].width     = (cfg->pic_width  + 3) >> 2;
 182     planes[1].height    = planes[2].height    = (cfg->pic_height + 3) >> 2;
 183     planes[1].num_bands = planes[2].num_bands = cfg->chroma_bands;
 184
 185     for (p = 0; p < 3; p++) {
 186         planes[p].bands = av_mallocz(planes[p].num_bands * sizeof(IVIBandDesc));
 187         if (!planes[p].bands)
 188             return AVERROR(ENOMEM);
 189
 190         /* select band dimensions: if there is only one band then it
 191          *  has the full size, if there are several bands each of them
 192          *  has only half size */
 193         b_width  = planes[p].num_bands == 1 ? planes[p].width  : (planes[p].width  + 1) >> 1;
 194         b_height = planes[p].num_bands == 1 ? planes[p].height : (planes[p].height + 1) >> 1;
 195
 196         /* luma   band buffers will be aligned on 16x16 (max macroblock size) */
 197         /* chroma band buffers will be aligned on   8x8 (max macroblock size) */
 198         align_fac       = p ? 8 : 16;
 199         width_aligned   = FFALIGN(b_width , align_fac);
 200         height_aligned  = FFALIGN(b_height, align_fac);
 201         buf_size        = width_aligned * height_aligned * sizeof(int16_t);
 202
 203         for (b = 0; b < planes[p].num_bands; b++) {
 204             band = &planes[p].bands[b]; /* select appropriate plane/band */
 205             band->plane    = p;
 206             band->band_num = b;
 207             band->width    = b_width;
 208             band->height   = b_height;
 209             band->pitch    = width_aligned;
 210             band->bufs[0]  = av_malloc(buf_size);
 211             band->bufs[1]  = av_malloc(buf_size);
 212             if (!band->bufs[0] || !band->bufs[1])
 213                 return AVERROR(ENOMEM);
 214
 215             /* allocate the 3rd band buffer for scalability mode */
 216             if (cfg->luma_bands > 1) {
 217                 band->bufs[2] = av_malloc(buf_size);
 218                 if (!band->bufs[2])
 219                     return AVERROR(ENOMEM);
 220             }
 221
 222             planes[p].bands[0].blk_vlc.cust_desc.num_rows = 0; /* reset custom vlc */
 223         }
 224     }
 225
 226     return 0;
 227 }
 228
 229 void av_cold ff_ivi_free_buffers(IVIPlaneDesc *planes)
 230 {
 231     int p, b, t;
 232
 233     for (p = 0; p < 3; p++) {
 234         for (b = 0; b < planes[p].num_bands; b++) {
 235             av_freep(&planes[p].bands[b].bufs[0]);
 236             av_freep(&planes[p].bands[b].bufs[1]);
 237             av_freep(&planes[p].bands[b].bufs[2]);
 238
 239             if (planes[p].bands[b].blk_vlc.cust_tab.table)
 240                 free_vlc(&planes[p].bands[b].blk_vlc.cust_tab);
 241             for (t = 0; t < planes[p].bands[b].num_tiles; t++)
 242                 av_freep(&planes[p].bands[b].tiles[t].mbs);
 243             av_freep(&planes[p].bands[b].tiles);
 244         }
 245         av_freep(&planes[p].bands);
 246     }
 247 }
 248
 249 int av_cold ff_ivi_init_tiles(IVIPlaneDesc *planes, int tile_width, int tile_height)
 250 {
 251     int         p, b, x, y, x_tiles, y_tiles, t_width, t_height;
 252     IVIBandDesc *band;
 253     IVITile     *tile, *ref_tile;
 254
 255     for (p = 0; p < 3; p++) {
 256         t_width  = !p ? tile_width  : (tile_width  + 3) >> 2;
 257         t_height = !p ? tile_height : (tile_height + 3) >> 2;
 258
 259         if (!p && planes[0].num_bands == 4) {
 260             t_width  >>= 1;
 261             t_height >>= 1;
 262         }
 263         if(t_width<=0 || t_height<=0)
 264             return AVERROR(EINVAL);
 265
 266         for (b = 0; b < planes[p].num_bands; b++) {
 267             band = &planes[p].bands[b];
 268             x_tiles = IVI_NUM_TILES(band->width, t_width);
 269             y_tiles = IVI_NUM_TILES(band->height, t_height);
 270             band->num_tiles = x_tiles * y_tiles;
 271
 272             av_freep(&band->tiles);
 273             band->tiles = av_mallocz(band->num_tiles * sizeof(IVITile));
 274             if (!band->tiles)
 275                 return AVERROR(ENOMEM);
 276
 277             tile = band->tiles;
 278
 279             /* use the first luma band as reference for motion vectors
 280              * and quant */
 281             ref_tile = planes[0].bands[0].tiles;
 282
 283             for (y = 0; y < band->height; y += t_height) {
 284                 for (x = 0; x < band->width; x += t_width) {
 285                     tile->xpos     = x;
 286                     tile->ypos     = y;
 287                     tile->width    = FFMIN(band->width - x,  t_width);
 288                     tile->height   = FFMIN(band->height - y, t_height);
 289                     tile->is_empty = tile->data_size = 0;
 290                     /* calculate number of macroblocks */
 291                     tile->num_MBs  = IVI_MBs_PER_TILE(tile->width, tile->height,
 292                                                       band->mb_size);
 293
 294                     av_freep(&tile->mbs);
 295                     tile->mbs = av_malloc(tile->num_MBs * sizeof(IVIMbInfo));
 296                     if (!tile->mbs)
 297                         return AVERROR(ENOMEM);
 298
 299                     tile->ref_mbs = 0;
 300                     if (p || b) {
 301                         tile->ref_mbs = ref_tile->mbs;
 302                         ref_tile++;
 303                     }
 304
 305                     tile++;
 306                 }
 307             }
 308
 309         }// for b
 310     }// for p
 311
 312     return 0;
 313 }
 314
 315 int ff_ivi_dec_tile_data_size(GetBitContext *gb)
 316 {
 317     int    len;
 318
 319     len = 0;
 320     if (get_bits1(gb)) {
 321         len = get_bits(gb, 8);
 322         if (len == 255)
 323             len = get_bits_long(gb, 24);
 324     }
 325
 326     /* align the bitstream reader on the byte boundary */
 327     align_get_bits(gb);
 328
 329     return len;
 330 }
 331
 332 int ff_ivi_decode_blocks(GetBitContext *gb, IVIBandDesc *band, IVITile *tile)
 333 {
 334     int         mbn, blk, num_blocks, num_coeffs, blk_size, scan_pos, run, val,
 335                 pos, is_intra, mc_type, mv_x, mv_y, col_mask;
 336     uint8_t     col_flags[8];
 337     int32_t     prev_dc, trvec[64];
 338     uint32_t    cbp, sym, lo, hi, quant, buf_offs, q;
 339     IVIMbInfo   *mb;
 340     RVMapDesc   *rvmap = band->rv_map;
 341     void (*mc_with_delta_func)(int16_t *buf, const int16_t *ref_buf, uint32_t pitch, int mc_type);
 342     void (*mc_no_delta_func)  (int16_t *buf, const int16_t *ref_buf, uint32_t pitch, int mc_type);
 343     const uint16_t  *base_tab;
 344     const uint8_t   *scale_tab;
 345
 346     prev_dc = 0; /* init intra prediction for the DC coefficient */
 347
 348     blk_size   = band->blk_size;
 349     col_mask   = blk_size - 1; /* column mask for tracking non-zero coeffs */
 350     num_blocks = (band->mb_size != blk_size) ? 4 : 1; /* number of blocks per mb */
 351     num_coeffs = blk_size * blk_size;
 352     if (blk_size == 8) {
 353         mc_with_delta_func = ff_ivi_mc_8x8_delta;
 354         mc_no_delta_func   = ff_ivi_mc_8x8_no_delta;
 355     } else {
 356         mc_with_delta_func = ff_ivi_mc_4x4_delta;
 357         mc_no_delta_func   = ff_ivi_mc_4x4_no_delta;
 358     }
 359
 360     for (mbn = 0, mb = tile->mbs; mbn < tile->num_MBs; mb++, mbn++) {
 361         is_intra = !mb->type;
 362         cbp      = mb->cbp;
 363         buf_offs = mb->buf_offs;
 364
 365         quant = av_clip(band->glob_quant + mb->q_delta, 0, 23);
 366
 367         base_tab  = is_intra ? band->intra_base  : band->inter_base;
 368         scale_tab = is_intra ? band->intra_scale : band->inter_scale;
 369         if (scale_tab)
 370             quant = scale_tab[quant];
 371
 372         if (!is_intra) {
 373             mv_x = mb->mv_x;
 374             mv_y = mb->mv_y;
 375             if (!band->is_halfpel) {
 376                 mc_type = 0; /* we have only fullpel vectors */
 377             } else {
 378                 mc_type = ((mv_y & 1) << 1) | (mv_x & 1);
 379                 mv_x >>= 1;
 380                 mv_y >>= 1; /* convert halfpel vectors into fullpel ones */
 381             }
 382         }
 383
 384         for (blk = 0; blk < num_blocks; blk++) {
 385             /* adjust block position in the buffer according to its number */
 386             if (blk & 1) {
 387                 buf_offs += blk_size;
 388             } else if (blk == 2) {
 389                 buf_offs -= blk_size;
 390                 buf_offs += blk_size * band->pitch;
 391             }
 392
 393             if (cbp & 1) { /* block coded ? */
 394                 scan_pos = -1;
 395                 memset(trvec, 0, num_coeffs*sizeof(trvec[0])); /* zero transform vector */
 396                 memset(col_flags, 0, sizeof(col_flags));      /* zero column flags */
 397
 398                 while (scan_pos <= num_coeffs) {
 399                     sym = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
 400                     if (sym == rvmap->eob_sym)
 401                         break; /* End of block */
 402
 403                     if (sym == rvmap->esc_sym) { /* Escape - run/val explicitly coded using 3 vlc codes */
 404                         run = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1) + 1;
 405                         lo  = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
 406                         hi  = get_vlc2(gb, band->blk_vlc.tab->table, IVI_VLC_BITS, 1);
 407                         val = IVI_TOSIGNED((hi << 6) | lo); /* merge them and convert into signed val */
 408                     } else {
 409                         if (sym >= 256U) {
 410                             av_log(NULL, AV_LOG_ERROR, "Invalid sym encountered: %d.\n", sym);
 411                             return -1;
 412                         }
 413                         run = rvmap->runtab[sym];
 414                         val = rvmap->valtab[sym];
 415                     }
 416
 417                     /* de-zigzag and dequantize */
 418                     scan_pos += run;
 419                     if (scan_pos >= num_coeffs)
 420                         break;
 421                     pos = band->scan[scan_pos];
 422
 423                     if (!val)
 424                         av_dlog(NULL, "Val = 0 encountered!\n");
 425
 426                     q = (base_tab[pos] * quant) >> 9;
 427                     if (q > 1)
 428                         val = val * q + FFSIGN(val) * (((q ^ 1) - 1) >> 1);
 429                     trvec[pos] = val;
 430                     col_flags[pos & col_mask] |= !!val; /* track columns containing non-zero coeffs */
 431                 }// while
 432
 433                 if (scan_pos >= num_coeffs && sym != rvmap->eob_sym)
 434                     return -1; /* corrupt block data */
 435
 436                 /* undoing DC coeff prediction for intra-blocks */
 437                 if (is_intra && band->is_2d_trans) {
 438                     prev_dc      += trvec[0];
 439                     trvec[0]      = prev_dc;
 440                     col_flags[0] |= !!prev_dc;
 441                 }
 442
 443                 /* apply inverse transform */
 444                 band->inv_transform(trvec, band->buf + buf_offs,
 445                                     band->pitch, col_flags);
 446
 447                 /* apply motion compensation */
 448                 if (!is_intra)
 449                     mc_with_delta_func(band->buf + buf_offs,
 450                                        band->ref_buf + buf_offs + mv_y * band->pitch + mv_x,
 451                                        band->pitch, mc_type);
 452             } else {
 453                 /* block not coded */
 454                 /* for intra blocks apply the dc slant transform */
 455                 /* for inter - perform the motion compensation without delta */
 456                 if (is_intra && band->dc_transform) {
 457                     band->dc_transform(&prev_dc, band->buf + buf_offs,
 458                                        band->pitch, blk_size);
 459                 } else
 460                     mc_no_delta_func(band->buf + buf_offs,
 461                                      band->ref_buf + buf_offs + mv_y * band->pitch + mv_x,
 462                                      band->pitch, mc_type);
 463             }
 464
 465             cbp >>= 1;
 466         }// for blk
 467     }// for mbn
 468
 469     align_get_bits(gb);
 470
 471     return 0;
 472 }
 473
 474 void ff_ivi_process_empty_tile(AVCodecContext *avctx, IVIBandDesc *band,
 475                                IVITile *tile, int32_t mv_scale)
 476 {
 477     int             x, y, need_mc, mbn, blk, num_blocks, mv_x, mv_y, mc_type;
 478     int             offs, mb_offset, row_offset;
 479     IVIMbInfo       *mb, *ref_mb;
 480     const int16_t   *src;
 481     int16_t         *dst;
 482     void (*mc_no_delta_func)(int16_t *buf, const int16_t *ref_buf, uint32_t pitch,
 483                              int mc_type);
 484
 485     offs       = tile->ypos * band->pitch + tile->xpos;
 486     mb         = tile->mbs;
 487     ref_mb     = tile->ref_mbs;
 488     row_offset = band->mb_size * band->pitch;
 489     need_mc    = 0; /* reset the mc tracking flag */
 490
 491     for (y = tile->ypos; y < (tile->ypos + tile->height); y += band->mb_size) {
 492         mb_offset = offs;
 493
 494         for (x = tile->xpos; x < (tile->xpos + tile->width); x += band->mb_size) {
 495             mb->xpos     = x;
 496             mb->ypos     = y;
 497             mb->buf_offs = mb_offset;
 498
 499             mb->type = 1; /* set the macroblocks type = INTER */
 500             mb->cbp  = 0; /* all blocks are empty */
 501
 502             if (!band->qdelta_present && !band->plane && !band->band_num) {
 503                 mb->q_delta = band->glob_quant;
 504                 mb->mv_x    = 0;
 505                 mb->mv_y    = 0;
 506             }
 507
 508             if (band->inherit_qdelta && ref_mb)
 509                 mb->q_delta = ref_mb->q_delta;
 510
 511             if (band->inherit_mv && ref_mb) {
 512                 /* motion vector inheritance */
 513                 if (mv_scale) {
 514                     mb->mv_x = ivi_scale_mv(ref_mb->mv_x, mv_scale);
 515                     mb->mv_y = ivi_scale_mv(ref_mb->mv_y, mv_scale);
 516                 } else {
 517                     mb->mv_x = ref_mb->mv_x;
 518                     mb->mv_y = ref_mb->mv_y;
 519                 }
 520                 need_mc |= mb->mv_x || mb->mv_y; /* tracking non-zero motion vectors */
 521             }
 522
 523             mb++;
 524             if (ref_mb)
 525                 ref_mb++;
 526             mb_offset += band->mb_size;
 527         } // for x
 528         offs += row_offset;
 529     } // for y
 530
 531     if (band->inherit_mv && need_mc) { /* apply motion compensation if there is at least one non-zero motion vector */
 532         num_blocks = (band->mb_size != band->blk_size) ? 4 : 1; /* number of blocks per mb */
 533         mc_no_delta_func = (band->blk_size == 8) ? ff_ivi_mc_8x8_no_delta
 534                                                  : ff_ivi_mc_4x4_no_delta;
 535
 536         for (mbn = 0, mb = tile->mbs; mbn < tile->num_MBs; mb++, mbn++) {
 537             mv_x = mb->mv_x;
 538             mv_y = mb->mv_y;
 539             if (!band->is_halfpel) {
 540                 mc_type = 0; /* we have only fullpel vectors */
 541             } else {
 542                 mc_type = ((mv_y & 1) << 1) | (mv_x & 1);
 543                 mv_x >>= 1;
 544                 mv_y >>= 1; /* convert halfpel vectors into fullpel ones */
 545             }
 546
 547             for (blk = 0; blk < num_blocks; blk++) {
 548                 /* adjust block position in the buffer according with its number */
 549                 offs = mb->buf_offs + band->blk_size * ((blk & 1) + !!(blk & 2) * band->pitch);
 550                 mc_no_delta_func(band->buf + offs,
 551                                  band->ref_buf + offs + mv_y * band->pitch + mv_x,
 552                                  band->pitch, mc_type);
 553             }
 554         }
 555     } else {
 556         /* copy data from the reference tile into the current one */
 557         src = band->ref_buf + tile->ypos * band->pitch + tile->xpos;
 558         dst = band->buf     + tile->ypos * band->pitch + tile->xpos;
 559         for (y = 0; y < tile->height; y++) {
 560             memcpy(dst, src, tile->width*sizeof(band->buf[0]));
 561             src += band->pitch;
 562             dst += band->pitch;
 563         }
 564     }
 565 }
 566
 567
 568 #ifdef DEBUG
 569 uint16_t ivi_calc_band_checksum (IVIBandDesc *band)
 570 {
 571     int         x, y;
 572     int16_t     *src, checksum;
 573
 574     src = band->buf;
 575     checksum = 0;
 576
 577     for (y = 0; y < band->height; src += band->pitch, y++)
 578         for (x = 0; x < band->width; x++)
 579             checksum += src[x];
 580
 581     return checksum;
 582 }
 583
 584 int ivi_check_band (IVIBandDesc *band, const uint8_t *ref, int pitch)
 585 {
 586     int         x, y, result;
 587     uint8_t     t1, t2;
 588     int16_t    *src;
 589
 590     src = band->buf;
 591     result = 0;
 592
 593     for (y = 0; y < band->height; src += band->pitch, y++) {
 594         for (x = 0; x < band->width; x++) {
 595             t1 = av_clip(src[x] + 128, 0, 255);
 596             t2 = ref[x];
 597             if (t1 != t2) {
 598                 av_log(NULL, AV_LOG_ERROR, "Data mismatch: row %d, column %d\n",
 599                        y / band->blk_size, x / band->blk_size);
 600                 result = -1;
 601             }
 602         }
 603         ref += pitch;
 604     }
 605
 606     return result;
 607 }
 608 #endif
 609
 610 void ff_ivi_output_plane(IVIPlaneDesc *plane, uint8_t *dst, int dst_pitch)
 611 {
 612     int             x, y;
 613     const int16_t   *src  = plane->bands[0].buf;
 614     uint32_t        pitch = plane->bands[0].pitch;
 615
 616     if (!src)
 617         return;
 618
 619     for (y = 0; y < plane->height; y++) {
 620         for (x = 0; x < plane->width; x++)
 621             dst[x] = av_clip_uint8(src[x] + 128);
 622         src += pitch;
 623         dst += dst_pitch;
 624     }
 625 }
 626
 627
 628 /**
 629  * These are 2x8 predefined Huffman codebooks for coding macroblock/block
 630  * signals. They are specified using "huffman descriptors" in order to
 631  * avoid huge static tables. The decoding tables will be generated at
 632  * startup from these descriptors.
 633  */
 634 const IVIHuffDesc ff_ivi_mb_huff_desc[8] = {
 635     {8,  {0, 4, 5, 4, 4, 4, 6, 6}},
 636     {12, {0, 2, 2, 3, 3, 3, 3, 5, 3, 2, 2, 2}},
 637     {12, {0, 2, 3, 4, 3, 3, 3, 3, 4, 3, 2, 2}},
 638     {12, {0, 3, 4, 4, 3, 3, 3, 3, 3, 2, 2, 2}},
 639     {13, {0, 4, 4, 3, 3, 3, 3, 2, 3, 3, 2, 1, 1}},
 640     {9,  {0, 4, 4, 4, 4, 3, 3, 3, 2}},
 641     {10, {0, 4, 4, 4, 4, 3, 3, 2, 2, 2}},
 642     {12, {0, 4, 4, 4, 3, 3, 2, 3, 2, 2, 2, 2}}
 643 };
 644
 645 const IVIHuffDesc ff_ivi_blk_huff_desc[8] = {
 646     {10, {1, 2, 3, 4, 4, 7, 5, 5, 4, 1}},
 647     {11, {2, 3, 4, 4, 4, 7, 5, 4, 3, 3, 2}},
 648     {12, {2, 4, 5, 5, 5, 5, 6, 4, 4, 3, 1, 1}},
 649     {13, {3, 3, 4, 4, 5, 6, 6, 4, 4, 3, 2, 1, 1}},
 650     {11, {3, 4, 4, 5, 5, 5, 6, 5, 4, 2, 2}},
 651     {13, {3, 4, 5, 5, 5, 5, 6, 4, 3, 3, 2, 1, 1}},
 652     {13, {3, 4, 5, 5, 5, 6, 5, 4, 3, 3, 2, 1, 1}},
 653     {9,  {3, 4, 4, 5, 5, 5, 6, 5, 5}}
 654 };
 655
 656
 657 /**
 658  *  Scan patterns shared between indeo4 and indeo5
 659  */
 660 const uint8_t ff_ivi_vertical_scan_8x8[64] = {
 661     0,  8, 16, 24, 32, 40, 48, 56,
 662     1,  9, 17, 25, 33, 41, 49, 57,
 663     2, 10, 18, 26, 34, 42, 50, 58,
 664     3, 11, 19, 27, 35, 43, 51, 59,
 665     4, 12, 20, 28, 36, 44, 52, 60,
 666     5, 13, 21, 29, 37, 45, 53, 61,
 667     6, 14, 22, 30, 38, 46, 54, 62,
 668     7, 15, 23, 31, 39, 47, 55, 63
 669 };
 670
 671 const uint8_t ff_ivi_horizontal_scan_8x8[64] = {
 672      0,  1,  2,  3,  4,  5,  6,  7,
 673      8,  9, 10, 11, 12, 13, 14, 15,
 674     16, 17, 18, 19, 20, 21, 22, 23,
 675     24, 25, 26, 27, 28, 29, 30, 31,
 676     32, 33, 34, 35, 36, 37, 38, 39,
 677     40, 41, 42, 43, 44, 45, 46, 47,
 678     48, 49, 50, 51, 52, 53, 54, 55,
 679     56, 57, 58, 59, 60, 61, 62, 63
 680 };
 681
 682 const uint8_t ff_ivi_direct_scan_4x4[16] = {
 683     0, 1, 4, 8, 5, 2, 3, 6, 9, 12, 13, 10, 7, 11, 14, 15
 684 };
 685
 686
 687 /**
 688  *  Run-value (RLE) tables.
 689  */
 690 const RVMapDesc ff_ivi_rvmap_tabs[9] = {
 691 {   /* MapTab0 */
 692     5, /* eob_sym */
 693     2, /* esc_sym */
 694     /* run table */
 695     {1,  1,  0,  1,  1,  0,  1,  1,  2,  2,  1,  1,  1,  1,  3,  3,
 696      1,  1,  2,  2,  1,  1,  4,  4,  1,  1,  1,  1,  2,  2,  5,  5,
 697      1,  1,  3,  3,  1,  1,  6,  6,  1,  2,  1,  2,  7,  7,  1,  1,
 698      8,  8,  1,  1,  4,  2,  1,  4,  2,  1,  3,  3,  1,  1,  1,  9,
 699      9,  1,  2,  1,  2,  1,  5,  5,  1,  1, 10, 10,  1,  1,  3,  3,
 700      2,  2,  1,  1, 11, 11,  6,  4,  4,  1,  6,  1,  2,  1,  2, 12,
 701      8,  1, 12,  7,  8,  7,  1, 16,  1, 16,  1,  3,  3, 13,  1, 13,
 702      2,  2,  1, 15,  1,  5, 14, 15,  1,  5, 14,  1, 17,  8, 17,  8,
 703      1,  4,  4,  2,  2,  1, 25, 25, 24, 24,  1,  3,  1,  3,  1,  8,
 704      6,  7,  6,  1, 18,  8, 18,  1,  7, 23,  2,  2, 23,  1,  1, 21,
 705     22,  9,  9, 22, 19,  1, 21,  5, 19,  5,  1, 33, 20, 33, 20,  8,
 706      4,  4,  1, 32,  2,  2,  8,  3, 32, 26,  3,  1,  7,  7, 26,  6,
 707      1,  6,  1,  1, 16,  1, 10,  1, 10,  2, 16, 29, 28,  2, 29, 28,
 708      1, 27,  5,  8,  5, 27,  1,  8,  3,  7,  3, 31, 41, 31,  1, 41,
 709      6,  1,  6,  7,  4,  4,  1,  1,  2,  1,  2, 11, 34, 30, 11,  1,
 710     30, 15, 15, 34, 36, 40, 36, 40, 35, 35, 37, 37, 39, 39, 38, 38},
 711
 712     /* value table */
 713     { 1,  -1,   0,   2,  -2,   0,   3,  -3,   1,  -1,   4,  -4,   5,  -5,   1,  -1,
 714       6,  -6,   2,  -2,   7,  -7,   1,  -1,   8,  -8,   9,  -9,   3,  -3,   1,  -1,
 715      10, -10,   2,  -2,  11, -11,   1,  -1,  12,   4, -12,  -4,   1,  -1,  13, -13,
 716       1,  -1,  14, -14,   2,   5,  15,  -2,  -5, -15,  -3,   3,  16, -16,  17,   1,
 717      -1, -17,   6,  18,  -6, -18,   2,  -2,  19, -19,   1,  -1,  20, -20,   4,  -4,
 718       7,  -7,  21, -21,   1,  -1,   2,   3,  -3,  22,  -2, -22,   8,  23,  -8,   1,
 719       2, -23,  -1,   2,  -2,  -2,  24,   1, -24,  -1,  25,   5,  -5,   1, -25,  -1,
 720       9,  -9,  26,   1, -26,   3,   1,  -1,  27,  -3,  -1, -27,   1,   3,  -1,  -3,
 721      28,  -4,   4,  10, -10, -28,   1,  -1,   1,  -1,  29,   6, -29,  -6,  30,  -4,
 722       3,   3,  -3, -30,   1,   4,  -1,  31,  -3,   1,  11, -11,  -1, -31,  32,  -1,
 723      -1,   2,  -2,   1,   1, -32,   1,   4,  -1,  -4,  33,  -1,   1,   1,  -1,   5,
 724       5,  -5, -33,  -1, -12,  12,  -5,  -7,   1,   1,   7,  34,   4,  -4,  -1,   4,
 725     -34,  -4,  35,  36,  -2, -35,  -2, -36,   2,  13,   2,  -1,   1, -13,   1,  -1,
 726      37,   1,  -5,   6,   5,  -1,  38,  -6,  -8,   5,   8,  -1,   1,   1, -37,  -1,
 727       5,  39,  -5,  -5,   6,  -6, -38, -39, -14,  40,  14,   2,   1,   1,  -2, -40,
 728      -1,  -2,   2,  -1,  -1,  -1,   1,   1,   1,  -1,   1,  -1,   1,  -1,   1,  -1}
 729 },{
 730     /* MapTab1 */
 731     0,  /* eob_sym */
 732     38, /* esc_sym */
 733     /* run table */
 734     {0,  1,  1,  2,  2,  3,  3,  4,  4,  5,  5,  6,  8,  6,  8,  7,
 735      7,  9,  9, 10, 10, 11, 11,  1, 12,  1, 12, 13, 13, 16, 14, 16,
 736     14, 15, 15, 17, 17, 18,  0, 18, 19, 20, 21, 19, 22, 21, 20, 22,
 737     25, 24,  2, 25, 24, 23, 23,  2, 26, 28, 26, 28, 29, 27, 29, 27,
 738     33, 33,  1, 32,  1,  3, 32, 30, 36,  3, 36, 30, 31, 31, 35, 34,
 739     37, 41, 34, 35, 37,  4, 41,  4, 49,  8,  8, 49, 40, 38,  5, 38,
 740     40, 39,  5, 39, 42, 43, 42,  7, 57,  6, 43, 44,  6, 50,  7, 44,
 741     57, 48, 50, 48, 45, 45, 46, 47, 51, 46, 47, 58,  1, 51, 58,  1,
 742     52, 59, 53,  9, 52, 55, 55, 59, 53, 56, 54, 56, 54,  9, 64, 64,
 743     60, 63, 60, 63, 61, 62, 61, 62,  2, 10,  2, 10, 11,  1, 11, 13,
 744     12,  1, 12, 13, 16, 16,  8,  8, 14,  3,  3, 15, 14, 15,  4,  4,
 745      1, 17, 17,  5,  1,  7,  7,  5,  6,  1,  2,  2,  6, 22,  1, 25,
 746     21, 22,  8, 24,  1, 21, 25, 24,  8, 18, 18, 23,  9, 20, 23, 33,
 747     29, 33, 20,  1, 19,  1, 29, 36,  9, 36, 19, 41, 28, 57, 32,  3,
 748     28,  3,  1, 27, 49, 49,  1, 32, 26, 26,  2,  4,  4,  7, 57, 41,
 749      2,  7, 10,  5, 37, 16, 10, 27,  8,  8, 13, 16, 37, 13,  1,  5},
 750
 751     /* value table */
 752     {0,   1,  -1,   1,  -1,   1,  -1,   1,  -1,   1,  -1,   1,   1,  -1,  -1,   1,
 753     -1,   1,  -1,   1,  -1,   1,  -1,   2,   1,  -2,  -1,   1,  -1,   1,   1,  -1,
 754     -1,   1,  -1,   1,  -1,   1,   0,  -1,   1,   1,   1,  -1,   1,  -1,  -1,  -1,
 755      1,   1,   2,  -1,  -1,   1,  -1,  -2,   1,   1,  -1,  -1,   1,   1,  -1,  -1,
 756      1,  -1,   3,   1,  -3,   2,  -1,   1,   1,  -2,  -1,  -1,  -1,   1,   1,   1,
 757      1,   1,  -1,  -1,  -1,   2,  -1,  -2,   1,   2,  -2,  -1,   1,   1,   2,  -1,
 758     -1,   1,  -2,  -1,   1,   1,  -1,   2,   1,   2,  -1,   1,  -2,  -1,  -2,  -1,
 759     -1,   1,   1,  -1,   1,  -1,   1,   1,   1,  -1,  -1,   1,   4,  -1,  -1,  -4,
 760      1,   1,   1,   2,  -1,  -1,   1,  -1,  -1,   1,  -1,  -1,   1,  -2,   1,  -1,
 761      1,   1,  -1,  -1,   1,   1,  -1,  -1,   3,   2,  -3,  -2,   2,   5,  -2,   2,
 762      2,  -5,  -2,  -2,  -2,   2,  -3,   3,   2,   3,  -3,   2,  -2,  -2,   3,  -3,
 763      6,   2,  -2,   3,  -6,   3,  -3,  -3,   3,   7,  -4,   4,  -3,   2,  -7,   2,
 764      2,  -2,  -4,   2,   8,  -2,  -2,  -2,   4,   2,  -2,   2,   3,   2,  -2,  -2,
 765      2,   2,  -2,  -8,  -2,   9,  -2,   2,  -3,  -2,   2,  -2,   2,   2,   2,   4,
 766     -2,  -4,  10,   2,   2,  -2,  -9,  -2,   2,  -2,   5,   4,  -4,   4,  -2,   2,
 767     -5,  -4,  -3,   4,   2,  -3,   3,  -2,  -5,   5,   3,   3,  -2,  -3, -10,  -4}
 768 },{
 769     /* MapTab2 */
 770     2,  /* eob_sym */
 771     11, /* esc_sym */
 772     /* run table */
 773     {1,  1,  0,  2,  2,  1,  1,  3,  3,  4,  4,  0,  1,  1,  5,  5,
 774      2,  2,  6,  6,  7,  7,  1,  8,  1,  8,  3,  3,  9,  9,  1,  2,
 775      2,  1,  4, 10,  4, 10, 11, 11,  1,  5, 12, 12,  1,  5, 13, 13,
 776      3,  3,  6,  6,  2,  2, 14, 14, 16, 16, 15,  7, 15,  8,  8,  7,
 777      1,  1, 17, 17,  4,  4,  1,  1, 18, 18,  2,  2,  5,  5, 25,  3,
 778      9,  3, 25,  9, 19, 24, 19, 24,  1, 21, 20,  1, 21, 22, 20, 22,
 779     23, 23,  8,  6, 33,  6,  8, 33,  7,  7, 26, 26,  1, 32,  1, 32,
 780     28,  4, 28, 10, 29, 27, 27, 10, 41,  4, 29,  2,  2, 41, 36, 31,
 781     49, 31, 34, 30, 34, 36, 30, 35,  1, 49, 11,  5, 35, 11,  1,  3,
 782      3,  5, 37, 37,  8, 40,  8, 40, 12, 12, 42, 42,  1, 38, 16, 57,
 783      1,  6, 16, 39, 38,  6,  7,  7, 13, 13, 39, 43,  2, 43, 57,  2,
 784     50,  9, 44,  9, 50,  4, 15, 48, 44,  4,  1, 15, 48, 14, 14,  1,
 785     45, 45,  8,  3,  5,  8, 51, 47,  3, 46, 46, 47,  5, 51,  1, 17,
 786     17, 58,  1, 58,  2, 52, 52,  2, 53,  7, 59,  6,  6, 56, 53, 55,
 787      7, 55,  1, 54, 59, 56, 54, 10,  1, 10,  4, 60,  1, 60,  8,  4,
 788      8, 64, 64, 61,  1, 63,  3, 63, 62, 61,  5, 11,  5,  3, 11, 62},
 789
 790     /* value table */
 791     { 1,  -1,   0,   1,  -1,   2,  -2,   1,  -1,   1,  -1,   0,   3,  -3,   1,  -1,
 792       2,  -2,   1,  -1,   1,  -1,   4,   1,  -4,  -1,   2,  -2,   1,  -1,   5,   3,
 793      -3,  -5,   2,   1,  -2,  -1,   1,  -1,   6,   2,   1,  -1,  -6,  -2,   1,  -1,
 794       3,  -3,   2,  -2,   4,  -4,   1,  -1,   1,  -1,   1,   2,  -1,   2,  -2,  -2,
 795       7,  -7,   1,  -1,   3,  -3,   8,  -8,   1,  -1,   5,  -5,   3,  -3,   1,   4,
 796       2,  -4,  -1,  -2,   1,   1,  -1,  -1,   9,   1,   1,  -9,  -1,   1,  -1,  -1,
 797       1,  -1,   3,  -3,   1,   3,  -3,  -1,   3,  -3,   1,  -1,  10,   1, -10,  -1,
 798       1,   4,  -1,   2,   1,  -1,   1,  -2,   1,  -4,  -1,   6,  -6,  -1,   1,   1,
 799       1,  -1,   1,   1,  -1,  -1,  -1,   1,  11,  -1,  -2,   4,  -1,   2, -11,   5,
 800      -5,  -4,  -1,   1,   4,   1,  -4,  -1,  -2,   2,   1,  -1,  12,   1,  -2,   1,
 801     -12,   4,   2,   1,  -1,  -4,   4,  -4,   2,  -2,  -1,   1,   7,  -1,  -1,  -7,
 802      -1,  -3,   1,   3,   1,   5,   2,   1,  -1,  -5,  13,  -2,  -1,   2,  -2, -13,
 803       1,  -1,   5,   6,   5,  -5,   1,   1,  -6,   1,  -1,  -1,  -5,  -1,  14,   2,
 804      -2,   1, -14,  -1,   8,   1,  -1,  -8,   1,   5,   1,   5,  -5,   1,  -1,   1,
 805      -5,  -1,  15,   1,  -1,  -1,  -1,   3, -15,  -3,   6,   1,  16,  -1,   6,  -6,
 806      -6,   1,  -1,   1, -16,   1,   7,  -1,   1,  -1,  -6,  -3,   6,  -7,   3,  -1}
 807 },{
 808     /* MapTab3 */
 809     0,  /* eob_sym */
 810     35, /* esc_sym */
 811     /* run table */
 812     {0,  1,  1,  2,  2,  3,  3,  4,  4,  1,  1,  5,  5,  6,  6,  7,
 813      7,  8,  8,  9,  9,  2,  2, 10, 10,  1,  1, 11, 11, 12, 12,  3,
 814      3, 13, 13,  0, 14, 14, 16, 15, 16, 15,  4,  4, 17,  1, 17,  1,
 815      5,  5, 18, 18,  2,  2,  6,  6,  8, 19,  7,  8,  7, 19, 20, 20,
 816     21, 21, 22, 24, 22, 24, 23, 23,  1,  1, 25, 25,  3,  3, 26, 26,
 817      9,  9, 27, 27, 28, 28, 33, 29,  4, 33, 29,  1,  4,  1, 32, 32,
 818      2,  2, 31, 10, 30, 10, 30, 31, 34, 34,  5,  5, 36, 36, 35, 41,
 819     35, 11, 41, 11, 37,  1,  8,  8, 37,  6,  1,  6, 40,  7,  7, 40,
 820     12, 38, 12, 39, 39, 38, 49, 13, 49, 13,  3, 42,  3, 42, 16, 16,
 821     43, 43, 14, 14,  1,  1, 44, 15, 44, 15,  2,  2, 57, 48, 50, 48,
 822     57, 50,  4, 45, 45,  4, 46, 47, 47, 46,  1, 51,  1, 17, 17, 51,
 823      8,  9,  9,  5, 58,  8, 58,  5, 52, 52, 55, 56, 53, 56, 55, 59,
 824     59, 53, 54,  1,  6, 54,  7,  7,  6,  1,  2,  3,  2,  3, 64, 60,
 825     60, 10, 10, 64, 61, 62, 61, 63,  1, 63, 62,  1, 18, 24, 18,  4,
 826     25,  4,  8, 21, 21,  1, 24, 22, 25, 22,  8, 11, 19, 11, 23,  1,
 827     20, 23, 19, 20,  5, 12,  5,  1, 16,  2, 12, 13,  2, 13,  1, 16},
 828
 829     /* value table */
 830     { 0,   1,  -1,   1,  -1,   1,  -1,   1,  -1,   2,  -2,   1,  -1,   1,  -1,   1,
 831      -1,   1,  -1,   1,  -1,   2,  -2,   1,  -1,   3,  -3,   1,  -1,   1,  -1,   2,
 832      -2,   1,  -1,   0,   1,  -1,   1,   1,  -1,  -1,   2,  -2,   1,   4,  -1,  -4,
 833       2,  -2,   1,  -1,  -3,   3,   2,  -2,   2,   1,   2,  -2,  -2,  -1,   1,  -1,
 834       1,  -1,   1,   1,  -1,  -1,   1,  -1,   5,  -5,   1,  -1,   3,  -3,   1,  -1,
 835       2,  -2,   1,  -1,   1,  -1,   1,   1,   3,  -1,  -1,   6,  -3,  -6,  -1,   1,
 836       4,  -4,   1,   2,   1,  -2,  -1,  -1,   1,  -1,   3,  -3,   1,  -1,   1,   1,
 837      -1,   2,  -1,  -2,   1,   7,  -3,   3,  -1,   3,  -7,  -3,   1,  -3,   3,  -1,
 838       2,   1,  -2,   1,  -1,  -1,   1,   2,  -1,  -2,  -4,  -1,   4,   1,   2,  -2,
 839       1,  -1,  -2,   2,   8,  -8,  -1,   2,   1,  -2,  -5,   5,   1,  -1,  -1,   1,
 840      -1,   1,   4,  -1,   1,  -4,  -1,  -1,   1,   1,   9,   1,  -9,   2,  -2,  -1,
 841      -4,   3,  -3,  -4,  -1,   4,   1,   4,   1,  -1,   1,  -1,   1,   1,  -1,   1,
 842      -1,  -1,  -1,  10,   4,   1,   4,  -4,  -4, -10,   6,   5,  -6,  -5,   1,  -1,
 843       1,   3,  -3,  -1,   1,  -1,  -1,  -1,  11,   1,   1, -11,  -2,  -2,   2,   5,
 844      -2,  -5,  -5,   2,  -2,  12,   2,  -2,   2,   2,   5,  -3,  -2,   3,  -2, -12,
 845      -2,   2,   2,   2,  -5,   3,   5,  13,  -3,   7,  -3,  -3,  -7,   3, -13,   3}
 846 },{
 847     /* MapTab4 */
 848     0,  /* eob_sym */
 849     34, /* esc_sym */
 850     /* run table */
 851     {0,  1,  1,  1,  2,  2,  1,  3,  3,  1,  1,  1,  4,  4,  1,  5,
 852      2,  1,  5,  2,  1,  1,  6,  6,  1,  1,  1,  1,  1,  7,  3,  1,
 853      2,  3,  0,  1,  2,  7,  1,  1,  1,  8,  1,  1,  8,  1,  1,  1,
 854      9,  1,  9,  1,  2,  1,  1,  2,  1,  1, 10,  4,  1, 10,  1,  4,
 855      1,  1,  1,  1,  1,  3,  1,  1,  1,  3,  2,  1,  5,  1,  1,  1,
 856      2,  5,  1, 11,  1, 11,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
 857      2,  1,  6,  1,  6,  1,  1,  2,  1,  1,  1,  1,  1,  1,  1, 12,
 858      3,  1, 12,  1,  1,  1,  2,  1,  1,  3,  1,  1,  1,  1,  1,  1,
 859      4,  1,  1,  1,  2,  1,  1,  4,  1,  1,  1,  1,  1,  1,  2,  1,
 860      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  3,  1,  2,  1,  1,  5,
 861      1,  1,  1,  1,  1,  7,  1,  7,  1,  1,  2,  3,  1,  1,  1,  1,
 862      5,  1,  1,  1,  1,  1,  1,  2, 13,  1,  1,  1,  1,  1,  1,  1,
 863      1,  1,  1,  1,  1,  1,  1,  1, 13,  2,  1,  1,  4,  1,  1,  1,
 864      3,  1,  6,  1,  1,  1, 14,  1,  1,  1,  1,  1, 14,  6,  1,  1,
 865      1,  1, 15,  2,  4,  1,  2,  3, 15,  1,  1,  1,  8,  1,  1,  8,
 866      1,  1,  1,  1,  1,  1,  1,  1,  2,  1,  1,  1,  1,  1,  1,  1},
 867
 868     /* value table */
 869     { 0,   1,  -1,   2,   1,  -1,  -2,   1,  -1,   3,  -3,   4,   1,  -1,  -4,   1,
 870       2,   5,  -1,  -2,  -5,   6,   1,  -1,  -6,   7,  -7,   8,  -8,   1,   2,   9,
 871       3,  -2,   0,  -9,  -3,  -1,  10, -10,  11,   1, -11,  12,  -1, -12,  13, -13,
 872       1,  14,  -1, -14,   4,  15, -15,  -4,  16, -16,   1,   2,  17,  -1, -17,  -2,
 873      18, -18,  19, -19,  20,   3, -20,  21, -21,  -3,   5,  22,   2, -22, -23,  23,
 874      -5,  -2,  24,   1, -24,  -1,  25, -25,  26, -26, -27,  27,  28,  29, -28, -29,
 875       6,  30,   2, -31,  -2, -30,  31,  -6, -32,  32,  33, -33,  34, -35, -34,   1,
 876       4, -36,  -1,  35,  37,  36,   7, -37,  38,  -4, -38,  39,  41,  40, -40, -39,
 877       3,  42, -43, -41,  -7, -42,  43,  -3,  44, -44,  45, -45,  46,  47,   8, -47,
 878     -48, -46,  50, -50,  48,  49,  51, -49,  52, -52,   5, -51,  -8, -53,  53,   3,
 879     -56,  56,  55,  54, -54,   2,  60,  -2, -55,  58,   9,  -5,  59,  57, -57, -63,
 880      -3, -58, -60, -61,  61, -59, -62,  -9,   1,  64,  62,  69, -64,  63,  65, -67,
 881     -68,  66, -65,  68, -66, -69,  67, -70,  -1,  10,  71, -71,   4,  73,  72,  70,
 882       6, -76,  -3,  74, -78, -74,   1,  78,  80, -72, -75,  76,  -1,   3, -73,  79,
 883      75,  77,   1,  11,  -4, -79, -10,  -6,  -1, -77, -83, -80,   2,  81, -84,  -2,
 884      83, -81,  82, -82,  84, -87, -86,  85, -11, -85,  86, -89,  87, -88,  88,  89}
 885 },{
 886     /* MapTab5 */
 887     2,  /* eob_sym */
 888     33, /* esc_sym */
 889     /* run table */
 890     {1,  1,  0,  2,  1,  2,  1,  3,  3,  1,  1,  4,  4,  2,  2,  1,
 891      1,  5,  5,  6,  1,  6,  1,  7,  7,  3,  3,  2,  8,  2,  8,  1,
 892      1,  0,  9,  9,  1,  1, 10,  4, 10,  4, 11, 11,  2,  1,  2,  1,
 893     12, 12,  3,  3,  1,  1, 13,  5,  5, 13, 14,  1,  1, 14,  2,  2,
 894      6,  6, 15,  1,  1, 15, 16,  4,  7, 16,  4,  7,  1,  1,  3,  3,
 895      8,  8,  2,  2,  1,  1, 17, 17,  1,  1, 18, 18,  5,  5,  2,  2,
 896      1,  1,  9, 19,  9, 19, 20,  3,  3, 20,  1, 10, 21,  1, 10,  4,
 897      4, 21, 22,  6,  6, 22,  1,  1, 23, 24,  2,  2, 23, 24, 11,  1,
 898      1, 11,  7, 25,  7,  1,  1, 25,  8,  8,  3, 26,  3,  1, 12,  2,
 899      2, 26,  1, 12,  5,  5, 27,  4,  1,  4,  1, 27, 28,  1, 28, 13,
 900      1, 13,  2, 29,  2,  1, 32,  6,  1, 30, 14, 29, 14,  6,  3, 31,
 901      3,  1, 30,  1, 32, 31, 33,  9, 33,  1,  1,  7,  9,  7,  2,  2,
 902      1,  1,  4, 36, 34,  4,  5, 10, 10,  5, 34,  1,  1, 35,  8,  8,
 903     36,  3, 35,  1, 15,  3,  2,  1, 16, 15, 16,  2, 37,  1, 37,  1,
 904      1,  1,  6,  6, 38,  1, 38, 11,  1, 39, 39, 40, 11,  2, 41,  4,
 905     40,  1,  2,  4,  1,  1,  1, 41,  3,  1,  3,  1,  5,  7,  5,  7},
 906
 907     /* value table */
 908     { 1,  -1,   0,   1,   2,  -1,  -2,   1,  -1,   3,  -3,   1,  -1,   2,  -2,   4,
 909      -4,   1,  -1,   1,   5,  -1,  -5,   1,  -1,   2,  -2,   3,   1,  -3,  -1,   6,
 910      -6,   0,   1,  -1,   7,  -7,   1,   2,  -1,  -2,   1,  -1,   4,   8,  -4,  -8,
 911       1,  -1,   3,  -3,   9,  -9,   1,   2,  -2,  -1,   1,  10, -10,  -1,   5,  -5,
 912       2,  -2,   1,  11, -11,  -1,   1,   3,   2,  -1,  -3,  -2,  12, -12,   4,  -4,
 913       2,  -2,  -6,   6,  13, -13,   1,  -1,  14, -14,   1,  -1,   3,  -3,   7,  -7,
 914      15, -15,   2,   1,  -2,  -1,   1,   5,  -5,  -1, -16,   2,   1,  16,  -2,   4,
 915      -4,  -1,   1,   3,  -3,  -1,  17, -17,   1,   1,  -8,   8,  -1,  -1,   2,  18,
 916     -18,  -2,   3,   1,  -3,  19, -19,  -1,   3,  -3,   6,   1,  -6,  20,   2,   9,
 917      -9,  -1, -20,  -2,   4,  -4,   1,  -5,  21,   5, -21,  -1,   1, -22,  -1,   2,
 918      22,  -2,  10,   1, -10,  23,   1,   4, -23,   1,   2,  -1,  -2,  -4,  -7,   1,
 919       7, -24,  -1,  24,  -1,  -1,   1,   3,  -1, -25,  25,   4,  -3,  -4,  11, -11,
 920      26, -26,   6,   1,   1,  -6,  -5,  -3,   3,   5,  -1, -27,  27,   1,   4,  -4,
 921      -1,  -8,  -1,  28,   2,   8, -12, -28,  -2,  -2,   2,  12,  -1,  29,   1, -29,
 922      30, -30,   5,  -5,   1, -31,  -1,   3,  31,  -1,   1,   1,  -3, -13,   1,  -7,
 923      -1, -32,  13,   7,  32,  33, -33,  -1,  -9, -34,   9,  34,  -6,   5,   6,  -5}
 924 },{
 925     /* MapTab6 */
 926     2,  /* eob_sym */
 927     13, /* esc_sym */
 928     /* run table */
 929     {1,  1,  0,  1,  1,  2,  2,  1,  1,  3,  3,  1,  1,  0,  2,  2,
 930      4,  1,  4,  1,  1,  1,  5,  5,  1,  1,  6,  6,  2,  2,  1,  1,
 931      3,  3,  7,  7,  1,  1,  8,  8,  1,  1,  2,  2,  1,  9,  1,  9,
 932      4,  4, 10,  1,  1, 10,  1,  1, 11, 11,  3,  3,  1,  2,  1,  2,
 933      1,  1, 12, 12,  5,  5,  1,  1, 13,  1,  1, 13,  2,  2,  1,  1,
 934      6,  6,  1,  1,  4, 14,  4, 14,  3,  1,  3,  1,  1,  1, 15,  7,
 935     15,  2,  2,  7,  1,  1,  1,  8,  1,  8, 16, 16,  1,  1,  1,  1,
 936      2,  1,  1,  2,  1,  1,  3,  5,  5,  3,  4,  1,  1,  4,  1,  1,
 937     17, 17,  9,  1,  1,  9,  2,  2,  1,  1, 10, 10,  1,  6,  1,  1,
 938      6, 18,  1,  1, 18,  1,  1,  1,  2,  2,  3,  1,  3,  1,  1,  1,
 939      4,  1, 19,  1, 19,  7,  1,  1, 20,  1,  4, 20,  1,  7, 11,  2,
 940      1, 11, 21,  2,  8,  5,  1,  8,  1,  5, 21,  1,  1,  1, 22,  1,
 941      1, 22,  1,  1,  3,  3,  1, 23,  2, 12, 24,  1,  1,  2,  1,  1,
 942     12, 23,  1,  1, 24,  1,  1,  1,  4,  1,  1,  1,  2,  1,  6,  6,
 943      4,  2,  1,  1,  1,  1,  1,  1,  1, 14, 13,  3,  1, 25,  9, 25,
 944     14,  1,  9,  3, 13,  1,  1,  1,  1,  1, 10,  1,  1,  2, 10,  2},
 945
 946     /* value table */
 947     {-20,  -1,   0,   2,  -2,   1,  -1,   3,  -3,   1,  -1,   4,  -4,   0,   2,  -2,
 948        1,   5,  -1,  -5,   6,  -6,   1,  -1,   7,  -7,   1,  -1,   3,  -3,   8,  -8,
 949        2,  -2,   1,  -1,   9,  -9,   1,  -1,  10, -10,   4,  -4,  11,   1, -11,  -1,
 950        2,  -2,   1,  12, -12,  -1,  13, -13,   1,  -1,   3,  -3,  14,   5, -14,  -5,
 951      -15,  15,  -1,   1,   2,  -2,  16, -16,   1,  17, -17,  -1,   6,  -6,  18, -18,
 952        2,  -2, -19,  19,  -3,   1,   3,  -1,   4,  20,  -4,   1, -21,  21,   1,   2,
 953       -1,  -7,   7,  -2,  22, -22,  23,   2, -23,  -2,   1,  -1, -24,  24, -25,  25,
 954       -8, -26,  26,   8, -27,  27,   5,   3,  -3,  -5,  -4,  28, -28,   4,  29, -29,
 955        1,  -1,  -2, -30,  30,   2,   9,  -9, -31,  31,   2,  -2, -32,   3,  32, -33,
 956       -3,   1,  33, -34,  -1,  34, -35,  35, -10,  10,  -6,  36,   6, -36,  37, -37,
 957       -5,  38,   1, -38,  -1,   3,  39, -39,  -1,  40,   5,   1, -40,  -3,   2, -11,
 958      -41,  -2,   1,  11,  -3,  -4,  41,   3,  42,   4,  -1, -43, -42,  43,   1, -44,
 959       45,  -1,  44, -45,  -7,   7, -46,   1, -12,   2,   1, -47,  46,  12,  47,  48,
 960       -2,  -1, -48,  49,  -1, -50, -49,  50,  -6, -51,  51,  52, -13,  53,  -4,   4,
 961        6,  13, -53, -52, -54,  55,  54, -55, -56,  -2,   2,  -8,  56,   1,  -3,  -1,
 962        2,  58,   3,   8,  -2,  57, -58, -60, -59, -57,  -3,  60,  59, -14,   3,  14}
 963 },{
 964     /* MapTab7 */
 965     2,  /* eob_sym */
 966     38, /* esc_sym */
 967     /* run table */
 968     {1,  1,  0,  2,  2,  1,  1,  3,  3,  4,  4,  5,  5,  1,  1,  6,
 969      6,  2,  2,  7,  7,  8,  8,  1,  1,  3,  3,  9,  9, 10, 10,  1,
 970      1,  2,  2,  4,  4, 11,  0, 11, 12, 12, 13, 13,  1,  1,  5,  5,
 971     14, 14, 15, 16, 15, 16,  3,  3,  1,  6,  1,  6,  2,  2,  7,  7,
 972      8,  8, 17, 17,  1,  1,  4,  4, 18, 18,  2,  2,  1, 19,  1, 20,
 973     19, 20, 21, 21,  3,  3, 22, 22,  5,  5, 24,  1,  1, 23,  9, 23,
 974     24,  9,  2,  2, 10,  1,  1, 10,  6,  6, 25,  4,  4, 25,  7,  7,
 975     26,  8,  1,  8,  3,  1, 26,  3, 11, 11, 27, 27,  2, 28,  1,  2,
 976     28,  1, 12, 12,  5,  5, 29, 13, 13, 29, 32,  1,  1, 33, 31, 30,
 977     32,  4, 30, 33,  4, 31,  3, 14,  1,  1,  3, 34, 34,  2,  2, 14,
 978      6,  6, 35, 36, 35, 36,  1, 15,  1, 16, 16, 15,  7,  9,  7,  9,
 979     37,  8,  8, 37,  1,  1, 39,  2, 38, 39,  2, 40,  5, 38, 40,  5,
 980      3,  3,  4,  4, 10, 10,  1,  1,  1,  1, 41,  2, 41,  2,  6,  6,
 981      1,  1, 11, 42, 11, 43,  3, 42,  3, 17,  4, 43,  1, 17,  7,  1,
 982      8, 44,  4,  7, 44,  5,  8,  2,  5,  1,  2, 48, 45,  1, 12, 45,
 983     12, 48, 13, 13,  1,  9,  9, 46,  1, 46, 47, 47, 49, 18, 18, 49},
 984
 985     /* value table */
 986     { 1,  -1,   0,   1,  -1,   2,  -2,   1,  -1,   1,  -1,   1,  -1,   3,  -3,   1,
 987      -1,  -2,   2,   1,  -1,   1,  -1,   4,  -4,  -2,   2,   1,  -1,   1,  -1,   5,
 988      -5,  -3,   3,   2,  -2,   1,   0,  -1,   1,  -1,   1,  -1,   6,  -6,   2,  -2,
 989       1,  -1,   1,   1,  -1,  -1,  -3,   3,   7,   2,  -7,  -2,  -4,   4,   2,  -2,
 990       2,  -2,   1,  -1,   8,  -8,   3,  -3,   1,  -1,  -5,   5,   9,   1,  -9,   1,
 991      -1,  -1,   1,  -1,  -4,   4,   1,  -1,   3,  -3,   1, -10,  10,   1,   2,  -1,
 992      -1,  -2,   6,  -6,   2,  11, -11,  -2,   3,  -3,   1,  -4,   4,  -1,   3,  -3,
 993       1,   3,  12,  -3,  -5, -12,  -1,   5,   2,  -2,   1,  -1,  -7,   1,  13,   7,
 994      -1, -13,   2,  -2,   4,  -4,   1,   2,  -2,  -1,   1,  14, -14,   1,   1,   1,
 995      -1,  -5,  -1,  -1,   5,  -1,  -6,   2, -15,  15,   6,   1,  -1,  -8,   8,  -2,
 996      -4,   4,   1,   1,  -1,  -1,  16,   2, -16,  -2,   2,  -2,   4,   3,  -4,  -3,
 997      -1,  -4,   4,   1, -17,  17,  -1,  -9,   1,   1,   9,   1,  -5,  -1,  -1,   5,
 998      -7,   7,   6,  -6,   3,  -3,  18, -18,  19, -19,   1, -10,  -1,  10,  -5,   5,
 999      20, -20,  -3,   1,   3,   1,   8,  -1,  -8,   2,   7,  -1, -21,  -2,   5,  21,
1000       5,  -1,  -7,  -5,   1,  -6,  -5, -11,   6,  22,  11,   1,   1, -22,  -3,  -1,
1001       3,  -1,   3,  -3, -23,   4,  -4,   1,  23,  -1,   1,  -1,   1,  -2,   2,  -1}
1002 },{
1003     /* MapTab8 */
1004     4,  /* eob_sym */
1005     11, /* esc_sym */
1006     /* run table */
1007     {1,  1,  1,  1,  0,  2,  2,  1,  1,  3,  3,  0,  1,  1,  2,  2,
1008      4,  4,  1,  1,  5,  5,  1,  1,  2,  2,  3,  3,  6,  6,  1,  1,
1009      7,  7,  8,  1,  8,  2,  2,  1,  4,  4,  1,  3,  1,  3,  9,  9,
1010      2,  2,  1,  5,  1,  5, 10, 10,  1,  1, 11, 11,  3,  6,  3,  4,
1011      4,  6,  2,  2,  1, 12,  1, 12,  7, 13,  7, 13,  1,  1,  8,  8,
1012      2,  2, 14, 14, 16, 15, 16,  5,  5,  1,  3, 15,  1,  3,  4,  4,
1013      1,  1, 17, 17,  2,  2,  6,  6,  1, 18,  1, 18, 22, 21, 22, 21,
1014     25, 24, 25, 19,  9, 20,  9, 23, 19, 24, 20,  3, 23,  7,  3,  1,
1015      1,  7, 28, 26, 29,  5, 28, 26,  5,  8, 29,  4,  8, 27,  2,  2,
1016      4, 27,  1,  1, 10, 36, 10, 33, 33, 36, 30,  1, 32, 32,  1, 30,
1017      6, 31, 31, 35,  3,  6, 11, 11,  3,  2, 35,  2, 34,  1, 34,  1,
1018     37, 37, 12,  7, 12,  5, 41,  5,  4,  7,  1,  8, 13,  4,  1, 41,
1019     13, 38,  8, 38,  9,  1, 40, 40,  9,  1, 39,  2,  2, 49, 39, 42,
1020      3,  3, 14, 16, 49, 14, 16, 42, 43, 43,  6,  6, 15,  1,  1, 15,
1021     44, 44,  1,  1, 50, 48,  4,  5,  4,  7,  5,  2, 10, 10, 48,  7,
1022     50, 45,  2,  1, 45,  8,  8,  1, 46, 46,  3, 47, 47,  3,  1,  1},
1023
1024     /* value table */
1025     { 1,  -1,   2,  -2,   0,   1,  -1,   3,  -3,   1,  -1,   0,   4,  -4,   2,  -2,
1026       1,  -1,   5,  -5,   1,  -1,   6,  -6,   3,  -3,   2,  -2,   1,  -1,   7,  -7,
1027       1,  -1,   1,   8,  -1,   4,  -4,  -8,   2,  -2,   9,   3,  -9,  -3,   1,  -1,
1028       5,  -5,  10,   2, -10,  -2,   1,  -1,  11, -11,   1,  -1,  -4,   2,   4,   3,
1029      -3,  -2,   6,  -6,  12,   1, -12,  -1,   2,   1,  -2,  -1,  13, -13,   2,  -2,
1030       7,  -7,   1,  -1,   1,   1,  -1,   3,  -3,  14,   5,  -1, -14,  -5,   4,  -4,
1031      15, -15,   1,  -1,   8,  -8,  -3,   3,  16,   1, -16,  -1,   1,   1,  -1,  -1,
1032       1,   1,  -1,   1,   2,   1,  -2,   1,  -1,  -1,  -1,   6,  -1,   3,  -6,  17,
1033     -17,  -3,   1,   1,   1,   4,  -1,  -1,  -4,   3,  -1,   5,  -3,  -1,  -9,   9,
1034      -5,   1,  18, -18,   2,   1,  -2,   1,  -1,  -1,   1,  19,  -1,   1, -19,  -1,
1035       4,   1,  -1,   1,   7,  -4,  -2,   2,  -7,  10,  -1, -10,   1,  20,  -1, -20,
1036       1,  -1,   2,   4,  -2,   5,   1,  -5,   6,  -4,  21,   4,   2,  -6, -21,  -1,
1037      -2,   1,  -4,  -1,  -3,  22,  -1,   1,   3, -22,  -1,  11, -11,   1,   1,   1,
1038       8,  -8,   2,   2,  -1,  -2,  -2,  -1,   1,  -1,  -5,   5,   2,  23, -23,  -2,
1039       1,  -1,  24, -24,  -1,  -1,   7,   6,  -7,   5,  -6,  12,  -3,   3,   1,  -5,
1040       1,   1, -12,  25,  -1,  -5,   5, -25,  -1,   1,   9,   1,  -1,  -9,  26, -26}
1041 }
1042 };