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