ip/xfax.c

   1 /* libhpojip -- HP OfficeJet image-processing library. */
   2
   3 /* Copyright (C) 1995-2002 Hewlett-Packard Company
   4  *
   5  * This program is free software; you can redistribute it and/or
   6  * modify it under the terms of the GNU General Public License as
   7  * published by the Free Software Foundation; either version 2 of the
   8  * License, or (at your option) any later version.
   9  *
  10  * This program is distributed in the hope that it will be useful, but
  11  * is provided AS IS, WITHOUT ANY WARRANTY; without even the implied
  12  * warranty of MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE, and
  13  * NON-INFRINGEMENT.  See the GNU General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU General Public License
  16  * along with this program; if not, write to the Free Software
  17  * Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  18  * MA 02111-1307, USA.
  19  *
  20  * In addition, as a special exception, Hewlett-Packard Company
  21  * gives permission to link the code of this program with any
  22  * version of the OpenSSL library which is distributed under a
  23  * license identical to that listed in the included LICENSE.OpenSSL
  24  * file, and distribute linked combinations including the two.
  25  * You must obey the GNU General Public License in all respects
  26  * for all of the code used other than OpenSSL.  If you modify
  27  * this file, you may extend this exception to your version of the
  28  * file, but you are not obligated to do so.  If you do not wish to
  29  * do so, delete this exception statement from your version.
  30  */
  31
  32 /* Original author: Mark Overton and others.
  33  *
  34  * Ported to Linux by David Paschal.
  35  */
  36
  37 /*****************************************************************************\
  38  *
  39  * xfax.c - encoder and decoder for fax data (MH, MR and MMR)
  40  *
  41  *****************************************************************************
  42  *
  43  * Name of Global Jump-Table:
  44  *
  45  *    faxEncodeTbl = the encoder,
  46  *    faxDecodeTbl = the decoder.
  47  *
  48  * Items in aXformInfo array passed into setXformSpec:
  49  *
  50  *    aXformInfo[IP_FAX_FORMAT]:  Format of data (both encoder & decoder).
  51  *        Values are:  IP_FAX_MH, IP_FAX_MR, IP_FAX_MMR.
  52  *
  53  *    aXformInfo[IP_FAX_NO_EOLS]:  No EOLs in the data?
  54  *                    0 = EOLs are in data as usual;
  55  *                    1 = no EOLs in data.
  56  *                    This tells the encoder whether to output EOLs.
  57  *                    This tells the decoder if there are EOLs in the data.
  58  *
  59  *    aXformInfo[IP_FAX_MIN_ROW_LEN]:  Minimum # bits to put in each output row
  60  *                    (MH & MR only).
  61  *                    Only the encoder needs this, and guarantees that each
  62  *                    row it outputs contains at least this many bits.  It
  63  *                    inserts fill 0's as needed.  The fax standard needs
  64  *                    this to insure that a row consumes a minimum amout of
  65  *                    time when sent over the modem, hence there's a minimum
  66  *                    number of bits to be transmitted per row.
  67  *
  68  * Capabilities and Limitations:
  69  *
  70  *    Bits per pixel must be 1 (bi-level only).
  71  *    Encodes and decodes MH, MR and MMR per the fax standard.
  72  *    Encoding MR uses a k-factor of 2 if vert dpi < 150, else k-factor is 4.
  73  *    If an error occurs in MH or MR data, the previous good row is returned.
  74  *
  75  * Default Input Traits, and Output Traits:
  76  *
  77  *    For both encoder and decoder:
  78  *
  79  *          trait             default input             output
  80  *    -------------------  -------------------  ------------------------
  81  *    iPixelsPerRow         * passed into output   same as default input
  82  *    iBitsPerPixel         * must be 1            1
  83  *    iComponentsPerPixel     passed into output   same as default input
  84  *    lHorizDPI               passed into output   same as default input
  85  *    lVertDPI                passed into output   same as default input
  86  *    lNumRows                passed into output   same as default input
  87  *    iNumPages               passed into output   same as default input
  88  *    iPageNum                passed into output   same as default input
  89  *
  90  *    Above, a "*" by an item indicates it must be valid (not negative).
  91  *
  92  * Mark Overton, Jan 1998
  93  *
  94 \*****************************************************************************/
  95
  96 #include "hpip.h"
  97 #include "ipdefs.h"
  98 #include "string.h"    /* for memset and memcpy */
  99 #include "assert.h"    /* todo: eliminate all asserts */
 100
 101
 102 #if 0
 103     #include "stdio.h"
 104     #include <tchar.h>
 105
 106     #define PRINT(msg,arg1,arg2) \
 107         _ftprintf(stdout, msg, (int)arg1, (int)arg2)
 108 #else
 109     #define PRINT(msg,arg1,arg2)
 110 #endif
 111
 112 #define CHECK_VALUE    0x1ce5ca7e
 113
 114
 115
 116
 117 /*
 118 @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
 119 @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
 120 @@                                                                          @@
 121 @@                                                                          @@
 122 @@                      U  T  I  L  I  T  I  E  S                           @@
 123 @@                                                                          @@
 124 @@                                                                          @@
 125 @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
 126 @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
 127 */
 128
 129
 130 /* baLeftZeroesTbl returns number of leading zeroes in byte index */
 131
 132 static const BYTE baLeftZeroesTbl[256] =
 133 {
 134     8, 7, 6, 6, 5, 5, 5, 5, 4, 4, 4, 4, 4, 4, 4, 4,
 135     3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
 136     2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
 137     2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
 138     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
 139     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
 140     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
 141     1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
 142     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 143     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 144     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 145     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 146     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 147     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 148     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
 149     0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0
 150 };
 151
 152
 153 /* baRightZeroesTbl returns number of trailing zeroes in byte index */
 154
 155 static const BYTE baRightZeroesTbl[256] =
 156 {
 157     8, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
 158     4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
 159     5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
 160     4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
 161     6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
 162     4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
 163     5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
 164     4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
 165     7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
 166     4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
 167     5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
 168     4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
 169     6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
 170     4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
 171     5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
 172     4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
 173 };
 174
 175
 176
 177 /*____________________________________________________________________________
 178  |         |                                                                  |
 179  | scan_to | Scan pixels rightward until hitting desired color (white/black)  |
 180  |_________|__________________________________________________________________|
 181  |                                                                            |
 182  | Pos, the initial search position, must not be negative nor greater than    |
 183  | pixels_in_row+1.  This function will not return a value greater than       |
 184  | pixels_in_row.                                                             |
 185  |                                                                            |
 186  | WARNING:  Before calling this routine, the first byte after the end of the |
 187  |           buffer must be set to alternating zeroes and ones (such as 0x55).|
 188  |           This allows us to scan bytes for a pixel-change without doing    |
 189  |           the end-of-buffer boundary-check.                                |
 190  |                                                                            |
 191  | Function return value:  index of first pixel of desired color.             |
 192  |____________________________________________________________________________|
 193 */
 194 static int scan_to (
 195     UINT  skip,          /* color to skip over (FF=black, 00=white) */
 196     BYTE *buf_p,         /* buffer in which to search */
 197     int   start_pos,     /* start-index for search (0=leftmost pixel in buf) */
 198     int   pixels_in_row) /* # pixels in the buffer */
 199 {
 200     /**************************************************************************
 201      *
 202      * PERFORMANCE NOTE
 203      *
 204      * This routine skips all-white and all-black areas a *byte* at a time
 205      * using a three-instruction loop.  The old routine did this a *word*
 206      * (2 bytes) at a time using a three-instruction loop.  But this routine
 207      * results in faster G3/G4 encoding/decoding, even for mostly white areas,
 208      * because it has so little overhead outside the loop.  Also, its small
 209      * size doesn't toss as much other G3/G4 code out of the cache, improving
 210      * performance even more.
 211      *
 212      * Seconds to MMR encode+decode 1000 rows of 1728 pixels (bench_fax.c):
 213      *
 214      *    black density:           0%    10%     20%     50%
 215      *    old routine:            2.1    10.2    18.8    45.1
 216      *    this routine:           2.2     7.4    12.8    29.9
 217      *    inlining this routine:  2.2     7.9    13.8    32.4
 218      *
 219      * Inlining this routine *hurt* performance a little because more MMR
 220      * code was kicked out of the cache.
 221      *
 222      *************************************************************************/
 223
 224     BYTE *cur_p;
 225     UINT  byte_mask;
 226     UINT  byte;
 227     int   pos;
 228
 229     byte_mask = 0x00FFu;
 230     cur_p = buf_p + (start_pos >> 3);
 231     skip &= byte_mask;
 232     byte = (*cur_p ^ skip) & (byte_mask >> (start_pos & 7));
 233
 234     if (byte == 0) {
 235         do {
 236             cur_p += 1;
 237             byte = *cur_p;
 238         } while (byte == skip);
 239         byte ^= skip;
 240     }
 241
 242     pos = ((cur_p-buf_p)<<3) + baLeftZeroesTbl[byte];
 243
 244     if (pos > pixels_in_row)
 245         pos = pixels_in_row;
 246     return pos;
 247 }
 248
 249
 250
 251 /*____________________________________________________________________________
 252  |                |                                                           |
 253  | worst_buf_size | calculates worst buffer-usage for a compressed row        |
 254  |________________|___________________________________________________________|
 255 */
 256 /* worst-case failure of compression (which is expansion) */
 257 #define WORST_EXPAND_1D  (9<<1)    /* = 4.5 in 14.2 fixed-point */
 258 #define WORST_EXPAND_2D  (6<<2)    /* = 6.0 in 14.2 fixed-point */
 259
 260 static int worst_buf_size (
 261     WORD  wFmt,        /* fax format (IP_FAX_MH/MR/MMR) */
 262     int   iRowWidth)   /* width of each row of bitmap (# pixels) */
 263 {
 264     return  (  (  (wFmt==IP_FAX_MH ? WORST_EXPAND_1D : WORST_EXPAND_2D)
 265                   * ((iRowWidth+7)/8)
 266                ) >> 2
 267             ) + 4;
 268 }
 269
 270
 271
 272 /*
 273 @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
 274 @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
 275 @@                                                                          @@
 276 @@                                                                          @@
 277 @@                        E  N  C  O  D  E  R                               @@
 278 @@                                                                          @@
 279 @@                                                                          @@
 280 @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
 281 @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
 282 */
 283
 284
 285 /* ENC_INST - our instance variables */
 286
 287 typedef struct {
 288     IP_IMAGE_TRAITS traits;   /* traits of the image                 */
 289     DWORD  dwValidChk;   /* struct validity check value              */
 290     DWORD  dwInNextPos;  /* file pos for subsequent input            */
 291     DWORD  dwOutNextPos; /* file pos for subsequent output           */
 292     int    iRowLen;      /* # pixels in each uncompressed input row  */
 293     BYTE   wOutFmt;      /* output format (IP_FAX_MH/FAX_MR/FAX_MMR) */
 294     BOOL   fNoEOLs;      /* don't output any EOLs?                   */
 295     UINT   w12Cycle;     /* (MR only) # rows in [1d,2d,2d...] cycle  */
 296     UINT   wMinBits;     /* minimum # bits to output in each row     */
 297     int    iRowNum;      /* current row-number of output, 0 is first */
 298     BYTE  *prior_p;      /* (MR/MMR only) the prior row              */
 299
 300     /* Variables for "Outputting Bits" section */
 301     BYTE  *pbBufStart;   /* beginning of output buffer                  */
 302     BYTE  *pbOutByte;    /* current byte in output buffer               */
 303     DWORD  dwBitBuffer;  /* buffer of bits (to be written to pbOutByte) */
 304     UINT   wBitsAvail;   /* # of unused bits in dwBitBuffer             */
 305 } ENC_INST, *PENC_INST;
 306
 307
 308
 309 /*****************************************************************************
 310  *                                                                           *
 311  *                       O U T P U T T I N G   B I T S                       *
 312  *                                                                           *
 313  *****************************************************************************
 314
 315
 316 Interface into this section:
 317     put_init      - initializes this section
 318     put_bits      - outputs a variable-number of bits (buffered)
 319     put_fill_bits - Outputs fill bits (if necessary) to reach the minimum
 320     put_grab      - gives all bytes except the partial one to caller
 321     put_new_buf   - tells us to use a new buffer (after put_grab was called)
 322     put_done      - writes any remaining bits in the buffer
 323 */
 324
 325
 326
 327 /*____________________________________________________________________________
 328  |          |                                                                 |
 329  | put_init | Initializes this 'put' section                                  |
 330  |__________|_________________________________________________________________|
 331 */
 332 static void put_init (
 333     ENC_INST *g,
 334     BYTE     *pbOutBuf)
 335 {
 336     g->dwBitBuffer = 0;
 337     g->wBitsAvail  = 32;
 338     g->pbOutByte   = pbOutBuf;
 339     g->pbBufStart  = pbOutBuf;
 340 }
 341
 342
 343
 344 /*____________________________________________________________________________
 345  |          |                                                                 |
 346  | put_bits | Outputs (buffered) the low-order 'length' bits in 'bits'        |
 347  |__________|_________________________________________________________________|
 348  |                                                                            |
 349  | 'length' must be no larger than 25.                                        |
 350  | The bits in 'bits' that are not to be written must be zeroes.              |
 351  |                                                                            |
 352  | This routine lets dwBitBuffer fill up until data won't fit.  Then it       |
 353  | writes out as many bytes as possible from the buffer in a loop.  I         |
 354  | did it this way so the byte-write code would be in cache for more of       |
 355  | the writes, and so 'write_bytes' will be called as seldom as possible.     |
 356  |____________________________________________________________________________|
 357 */
 358
 359 static void write_bytes (ENC_INST *g)
 360 {
 361     /* PERFORMANCE NOTE:  inlining this routine slows down the encoder
 362      * due to worse cache usage.
 363      */
 364     BYTE  *byte_p;
 365     DWORD  bitbuf;
 366     UINT   bitsavail;
 367
 368     /* assert (g->wBitsAvail <= 24); */
 369     byte_p    = g->pbOutByte;
 370     bitbuf    = g->dwBitBuffer;
 371     bitsavail = g->wBitsAvail;
 372
 373     do {
 374         *byte_p++ = (BYTE )(bitbuf >> 24);
 375         bitbuf <<= 8;
 376         bitsavail += 8;
 377     } while (bitsavail <= 24);
 378
 379     g->pbOutByte  = byte_p;
 380     g->dwBitBuffer = bitbuf;;
 381     g->wBitsAvail = bitsavail;
 382 }
 383
 384
 385 #define put_bits(g, length_par, bits_par)                               \
 386 do {                                                                    \
 387     UINT   length_loc = length_par;                                     \
 388     DWORD  bits_loc   = bits_par;                                       \
 389                                                                         \
 390     if (length_loc > g->wBitsAvail)                                     \
 391         write_bytes (g);                                                \
 392                                                                         \
 393     g->wBitsAvail -= length_loc;                                        \
 394     g->dwBitBuffer |= bits_loc << g->wBitsAvail;                         \
 395 } while (0)
 396
 397
 398 static void put_bits_routine (
 399     ENC_INST *g,
 400     UINT   length,
 401     DWORD  bits)
 402 {
 403     put_bits (g, length, bits);
 404 }
 405
 406
 407
 408 /*____________________________________________________________________________
 409  |           |                                                                |
 410  | put_flush | Writes out all bytes containing any data in dwBitBuffer        |
 411  |___________|________________________________________________________________|
 412 */
 413 static void put_flush (ENC_INST *g)
 414 {
 415     if (g->wBitsAvail < 32) {
 416         g->wBitsAvail &= ~7ul;   /* reduce to a multiple of 8 (byte-boundary) */
 417         write_bytes (g);
 418     }
 419
 420     assert (g->wBitsAvail == 32);
 421 }
 422
 423
 424
 425 /*____________________________________________________________________________
 426  |               |                                                            |
 427  | put_fill_bits | Outputs fill bits (if necessary) to reach the minimum      |
 428  |_______________|____________________________________________________________|
 429  |                                                                            |
 430  | We want put_grab to return the minimum # of bits, but it returns an        |
 431  | array of bytes (not bits).  So this routine insures that at least          |
 432  | the minimum # of bits have been written (as bytes) into the output         |
 433  | buffer.                                                                    |
 434  |____________________________________________________________________________|
 435 */
 436 static void put_fill_bits (ENC_INST *g)
 437 {
 438     int iMore;
 439
 440     put_flush (g);
 441
 442     /* write out zero-bytes until we're at (or past) the minimum # bits */
 443
 444     iMore = (int)g->wMinBits - 8*(g->pbOutByte - g->pbBufStart);
 445     if (iMore > 0) {
 446         iMore = (iMore+7) / 8;
 447         memset (g->pbOutByte, 0, iMore);
 448         g->pbOutByte += iMore;
 449     }
 450 }
 451
 452
 453
 454 /*____________________________________________________________________________
 455  |          |                                                                 |
 456  | put_grab | Returns # of bytes written so far, and restarts at buffer-start |
 457  |__________|_________________________________________________________________|
 458  |                                                                            |
 459  | The caller is expected to copy N bytes from the buffer, where N is the     |
 460  | number this function returns.                                              |
 461  |____________________________________________________________________________|
 462 */
 463 static int  put_grab (ENC_INST *g)
 464 {
 465     int  n;
 466
 467     n = g->pbOutByte - g->pbBufStart;
 468     g->pbOutByte = g->pbBufStart;  /* next byte goes into beginning of buffer */
 469     return n;
 470 }
 471
 472
 473
 474 /*____________________________________________________________________________
 475  |             |                                                              |
 476  | put_new_buf | Use a new buffer (must be called after put_grab)             |
 477  |_____________|______________________________________________________________|
 478 */
 479 static void put_new_buf (
 480     ENC_INST *g,
 481     BYTE     *pbOutBuf)
 482 {
 483     assert (g->pbOutByte == g->pbBufStart);
 484     g->pbOutByte  = pbOutBuf;
 485     g->pbBufStart = pbOutBuf;
 486 }
 487
 488
 489
 490 /*____________________________________________________________________________
 491  |          |                                                                 |
 492  | put_done | Writes any buffered bits, and returns total # of bytes written  |
 493  |__________|_________________________________________________________________|
 494 */
 495 static int  put_done (
 496     ENC_INST *g)
 497 {
 498     put_flush (g);
 499     return g->pbOutByte - g->pbBufStart;
 500 }
 501
 502
 503
 504 /*
 505  *****************************************************************************
 506  *                                                                           *
 507  *                        E N C O D I N G   R O W S                          *
 508  *                                                                           *
 509  *****************************************************************************
 510
 511
 512 Interface into this section:
 513     encode_row_1d - compresses a row into 1-dim format for MH and MR
 514     encode_row_2d - compresses a row into 2-dim format for MR and MMR
 515 */
 516
 517
 518
 519 /* Structure for storing G3 codes */
 520
 521 typedef struct {
 522     USHORT bits;
 523     USHORT length;
 524 } huff_t;
 525
 526
 527 /* run-length = index, index is in 0..63 */
 528 static const huff_t MHWhiteRuns[] = {
 529    {0x35, 8},  {0x7,  6},  {0x7,  4},  {0x8,  4},
 530    {0xb,  4},  {0xc,  4},  {0xe,  4},  {0xf,  4},
 531    {0x13, 5},  {0x14, 5},  {0x7,  5},  {0x8,  5},
 532    {0x8,  6},  {0x3,  6},  {0x34, 6},  {0x35, 6},
 533    {0x2a, 6},  {0x2b, 6},  {0x27, 7},  {0xc,  7},
 534    {0x8,  7},  {0x17, 7},  {0x3,  7},  {0x4,  7},
 535    {0x28, 7},  {0x2b, 7},  {0x13, 7},  {0x24, 7},
 536    {0x18, 7},  {0x2,  8},  {0x3,  8},  {0x1a, 8},
 537    {0x1b, 8},  {0x12, 8},  {0x13, 8},  {0x14, 8},
 538    {0x15, 8},  {0x16, 8},  {0x17, 8},  {0x28, 8},
 539    {0x29, 8},  {0x2a, 8},  {0x2b, 8},  {0x2c, 8},
 540    {0x2d, 8},  {0x4,  8},  {0x5,  8},  {0xa,  8},
 541    {0xb,  8},  {0x52, 8},  {0x53, 8},  {0x54, 8},
 542    {0x55, 8},  {0x24, 8},  {0x25, 8},  {0x58, 8},
 543    {0x59, 8},  {0x5a, 8},  {0x5b, 8},  {0x4a, 8},
 544    {0x4b, 8},  {0x32, 8},  {0x33, 8},  {0x34, 8}
 545 };
 546
 547
 548 /* run-length = 64*(index+1), index is in 0..26 */
 549 static const huff_t MHMakeupWhite[] = {
 550    {0x1b, 5},  {0x12, 5},  {0x17, 6},  {0x37, 7},
 551    {0x36, 8},  {0x37, 8},  {0x64, 8},  {0x65, 8},
 552    {0x68, 8},  {0x67, 8},  {0xcc, 9},  {0xcd, 9},
 553    {0xd2, 9},  {0xd3, 9},  {0xd4, 9},  {0xd5, 9},
 554    {0xd6, 9},  {0xd7, 9},  {0xd8, 9},  {0xd9, 9},
 555    {0xda, 9},  {0xdb, 9},  {0x98, 9},  {0x99, 9},
 556    {0x9a, 9},  {0x18, 6},  {0x9b, 9}
 557 };
 558
 559
 560 /* run-length = index, index is in 0..63 */
 561 static const huff_t MHBlackRuns[] = {
 562    {0x37, 10},  {0x2,   3},  {0x3,   2},  {0x2,   2},
 563    {0x3,   3},  {0x3,   4},  {0x2,   4},  {0x3,   5},
 564    {0x5,   6},  {0x4,   6},  {0x4,   7},  {0x5,   7},
 565    {0x7,   7},  {0x4,   8},  {0x7,   8},  {0x18,  9},
 566    {0x17, 10},  {0x18, 10},  {0x8,  10},  {0x67, 11},
 567    {0x68, 11},  {0x6c, 11},  {0x37, 11},  {0x28, 11},
 568    {0x17, 11},  {0x18, 11},  {0xca, 12},  {0xcb, 12},
 569    {0xcc, 12},  {0xcd, 12},  {0x68, 12},  {0x69, 12},
 570    {0x6a, 12},  {0x6b, 12},  {0xd2, 12},  {0xd3, 12},
 571    {0xd4, 12},  {0xd5, 12},  {0xd6, 12},  {0xd7, 12},
 572    {0x6c, 12},  {0x6d, 12},  {0xda, 12},  {0xdb, 12},
 573    {0x54, 12},  {0x55, 12},  {0x56, 12},  {0x57, 12},
 574    {0x64, 12},  {0x65, 12},  {0x52, 12},  {0x53, 12},
 575    {0x24, 12},  {0x37, 12},  {0x38, 12},  {0x27, 12},
 576    {0x28, 12},  {0x58, 12},  {0x59, 12},  {0x2b, 12},
 577    {0x2c, 12},  {0x5a, 12},  {0x66, 12},  {0x67, 12}
 578 };
 579
 580
 581 /* run-length = 64*(index+1), index is in 0..26 */
 582 static const huff_t MHMakeupBlack[] = {
 583    {0xf,  10},  {0xc8, 12},  {0xc9, 12},  {0x5b, 12},
 584    {0x33, 12},  {0x34, 12},  {0x35, 12},  {0x6c, 13},
 585    {0x6d, 13},  {0x4a, 13},  {0x4b, 13},  {0x4c, 13},
 586    {0x4d, 13},  {0x72, 13},  {0x73, 13},  {0x74, 13},
 587    {0x75, 13},  {0x76, 13},  {0x77, 13},  {0x52, 13},
 588    {0x53, 13},  {0x54, 13},  {0x55, 13},  {0x5a, 13},
 589    {0x5b, 13},  {0x64, 13},  {0x65, 13}
 590 };
 591
 592
 593 /* run-length = 64*(index+28), index is in 0..12 */
 594 static const huff_t MHExtMakeup[] = {
 595     {0x8,  11},  {0xc,  11}, {0xd,  11},  {0x12, 12},
 596     {0x13, 12},  {0x14, 12}, {0x15, 12},  {0x16, 12},
 597     {0x17, 12},  {0x1c, 12}, {0x1d, 12},  {0x1e, 12},
 598     {0x1f, 12}
 599 };
 600
 601
 602 /* vertical-offset = index-3 */
 603 static const huff_t VertTbl[] = {
 604     {2, 7},
 605     {2, 6},
 606     {2, 3},
 607     {1, 1},
 608     {3, 3},
 609     {3, 6},
 610     {3, 7}
 611 };
 612
 613
 614
 615 /*____________________________________________________________________________
 616  |         |                                                                  |
 617  | put_run | Outputs a white or black run                                     |
 618  |_________|__________________________________________________________________|
 619 */
 620 static void put_run_routine(
 621     ENC_INST     *g,
 622     int           iRunLen,
 623     const huff_t *makeup_tbl,
 624     const huff_t *code_tbl)
 625 {
 626     huff_t te;
 627
 628     while (iRunLen >= 1792) {
 629         int  tpos;
 630         tpos = (iRunLen>>6) - (1792>>6);
 631         if (tpos > 12)
 632             tpos = 12;
 633         te = MHExtMakeup [tpos];
 634         put_bits_routine (g, te.length, te.bits);
 635         iRunLen -= (tpos+(1792>>6)) << 6;
 636     }
 637
 638     if (iRunLen >= 64) {
 639         te = makeup_tbl [(iRunLen>>6) - 1];
 640         put_bits_routine (g, te.length, te.bits);
 641         iRunLen &= 63;
 642     }
 643
 644     te = code_tbl [iRunLen];
 645     put_bits_routine (g, te.length, te.bits);
 646 }
 647
 648 #define put_run(g, par_run_len, par_makeup_tbl, par_code_tbl)           \
 649 do {                                                                    \
 650     huff_t te;                                                          \
 651     int    loc_run_len = par_run_len;                                   \
 652                                                                         \
 653     if (loc_run_len >= 64)                                              \
 654         put_run_routine (g, loc_run_len, par_makeup_tbl, par_code_tbl); \
 655     else {                                                              \
 656         te = par_code_tbl [loc_run_len];                                \
 657         put_bits (g, te.length, te.bits);                               \
 658     }                                                                   \
 659 } while (0)
 660
 661
 662
 663 #define PutWhiteRun(g, iRunLen) \
 664     put_run (g, iRunLen, MHMakeupWhite, MHWhiteRuns)
 665
 666
 667 #define PutBlackRun(g, iRunLen) \
 668     put_run (g, iRunLen, MHMakeupBlack, MHBlackRuns)
 669
 670
 671 static void PutEOL(ENC_INST *g)  /* output the EOL code (11 zeroes and a one) */
 672 {
 673     put_bits_routine (g, 12, 0x001);
 674 }
 675
 676
 677
 678 /*____________________________________________________________________________
 679  |               |                                                            |
 680  | encode_row_1d | Converts a pixel-row into MH (CCITT G3) format             |
 681  |_______________|____________________________________________________________|
 682  |                                                                            |
 683  | Before calling this routine, you must call put_init.                       |
 684  | After  calling this routine, you must call put_grab/put_done.              |
 685  | This routine puts the EOL at the beginning of the line.                    |
 686  |____________________________________________________________________________|
 687 */
 688 static void encode_row_1d (
 689     ENC_INST *g,
 690     BYTE     *pbPixelRow, /* ptr to pixel-row */
 691     int       iPixels,    /* # of pixels in above row */
 692     BOOL      fDoingMR)   /* Sending MR?  Ie, send a 1d/2d tag-bit after EOL? */
 693 {
 694     int    iStartPos;
 695     int    iChange;
 696     UINT   skip;    /* the color we're skipping over; 0x00=black, 0xFF=white */
 697
 698     PutEOL (g);
 699     if (fDoingMR)
 700         put_bits_routine (g,1,1);  /* tag-bit after EOL means 1-dim row-data */
 701
 702     pbPixelRow[iPixels>>3] = 0x55u;   /* scan_to requires this */
 703     iStartPos = 0;
 704     skip = 0;
 705
 706     while (iStartPos < iPixels) {
 707         iChange = scan_to (skip, pbPixelRow, iStartPos, iPixels);
 708         if (skip) PutBlackRun (g, iChange-iStartPos);
 709         else      PutWhiteRun (g, iChange-iStartPos);
 710         iStartPos = iChange;
 711         skip = ~skip;
 712     }
 713 }
 714
 715
 716
 717 /*____________________________________________________________________________
 718  |               |                                                            |
 719  | encode_row_2d | Converts a pixel-row into 2-dimensional format             |
 720  |_______________|____________________________________________________________|
 721  |                                                                            |
 722  | Before calling this routine, you must call put_init.                       |
 723  | After  calling this routine, you must call put_grab/put_done.              |
 724  | For MR data, this routine puts the EOL+tag at the beginning of the line.   |
 725  |____________________________________________________________________________|
 726 */
 727 /*
 728  * The variable 'need' below is a bit-array telling us which values (a1, b0,
 729  * etc) are needed.  It is determined by the cases below.
 730  *
 731  * b0 is not in the standard.  I've defined it as, "A pixel on the reference
 732  * line above or to the right of a0, and to the left of b1."  Since b1 is the
 733  * first changing pixel, b0 must be the same color as a0.  b0 is the point at
 734  * which the search for b1 begins.
 735  *
 736  * In the code below, b0 uses the b1 variable because if we're using b0, then
 737  * b1 is not known, so it's okay to clobber it.
 738  *
 739  * Below, a0, a1, b0, b1 etc denote positions before coding, and A0, A1,
 740  * B0, B1, etc denote positions after coding.
 741  *
 742  * Pass Mode:
 743  *
 744  *                           B0
 745  *                  b1       b2
 746  *         -  -  -  X  X  X  -  -  -
 747  *         X  -  -  -  -  -  -  X  -
 748  *            a0                a1
 749  *                           A0 A1
 750  *
 751  *         A0 = b2, specified by the standard.
 752  *         A1 = a1, because A0 is to the left of a1, a1 does not move.
 753  *         B0 = b2, which is known to be the same color as A0.
 754  *
 755  *         Needed:  B1 and B2.
 756  *
 757  * Vertical Mode:
 758  *
 759  *     Normal case:
 760  *
 761  *                           B1
 762  *                  b1       b2
 763  *         -  -  -  X  X  X  -  -  -
 764  *         -  -  X  X  -  -  -  -  -
 765  *         a0    a1
 766  *               A0
 767  *
 768  *         A0 = a1, specified by the standard.
 769  *         B1 = b2, the first changing pixel of opposite color as A0.
 770  *
 771  *         Needed: A1, B2.
 772  *
 773  *     An exception (a1=b2):
 774  *
 775  *                  b1 b2
 776  *         -  -  -  X  -  -  -  -  -
 777  *         -  -  -  -  X  -  -  -  -
 778  *            a0       a1
 779  *                     A0
 780  *
 781  *         Here, b2 is above A0, and therefore cannot be used as B1.
 782  *         And its color is opposite A0, so it's not even usable as B0.
 783  *         So B0 and B1 must be scanned.
 784  *
 785  *         Needed: A1, B0, B1, B2.
 786  *
 787  *     A subtle exception (a1 is at least 2 pixels to the left of b1):
 788  *
 789  *                        B1 B2
 790  *                           b1 b2
 791  *         -  -  X  X  X  -  X  -  -
 792  *         -  -  -  -  X  -  -  -  -
 793  *               a0    a1
 794  *                     A0
 795  *
 796  *         b1 and b2 move *backwards* after coding.
 797  *         B1 = b1-1, and B2=b1.  Since it's not worth the time to check
 798  *         for this rare pixel-arrangement, we'll just rescan B0, B1 and B2.
 799  *
 800  *         Needed: A1, B0, B1, B2.
 801  *
 802  * Horizontal Mode:
 803  *
 804  *     First case (a2 > b2):
 805  *
 806  *                        b1 b2
 807  *         -  -  -  -  -  X  -  -  -
 808  *         -  X  X  X  X  X  X  -  -
 809  *         a0 a1                a2
 810  *                              A0
 811  *
 812  *         Since b2 is left of A0, we know nothing about what's above A0.
 813  *         So everything must be scanned.
 814  *
 815  *         Needed: A1, B0, B1, B2.
 816  *
 817  *     Second case: (a2 <= b2):
 818  *
 819  *                                 B0
 820  *                        b1       b2
 821  *         -  -  -  -  -  X  X  X  -
 822  *         -  X  X  X  X  X  X  -  -
 823  *         a0 a1                a2
 824  *                              A0
 825  *
 826  *         A0 = a2, specified by the standard.
 827  *         B0 = b2, because it's the same color as A0, and not to left of A0.
 828  *
 829  *         Needed:  A1, B1, B2.
 830  *
 831  *     Exception to above case (a2 < b1):
 832  *
 833  *                           B1    B2
 834  *                           b1    b2
 835  *         -  -  -  -  -  -  X  X  -
 836  *         -  X  X  X  X  -  -  -  -
 837  *         a0 a1          a2
 838  *                        A0
 839  *
 840  *         b1 is to the right of A0, so b1 and b2 don't move.
 841  *         This case is common because it occurs whenever a row with some
 842  *         data follows a blank row.
 843  *
 844  *         Needed: A1.
 845  */
 846 static void encode_row_2d (
 847     ENC_INST *g,
 848     BYTE     *pbPixelRow,  /* ptr to pixel-row                         */
 849     BYTE     *pbRefRow,    /* ptr to reference-row                     */
 850     int       iPixels,     /* # of pixels in above row                 */
 851     BOOL      fDoingMR)    /* Sending MR? Ie, output an EOL + tag-bit? */
 852 {
 853     #define A1 1
 854     #define B0 2
 855     #define B1 4
 856     #define B2 8
 857
 858     int   a0, a1, a2;
 859     int   b1, b2;
 860     int   iDelta;
 861     UINT  skip;      /* the color we're skipping over; 00=white, FF=black */
 862     UINT  need;
 863
 864     if (fDoingMR) {
 865         PutEOL (g);
 866         put_bits_routine (g,1,0);  /* tag-bit after EOL means 2-dim row-data */
 867     }
 868
 869     pbPixelRow[iPixels>>3] = 0x55u;   /* scan_to requires this */
 870     pbRefRow  [iPixels>>3] = 0x55u;   /* scan_to requires this */
 871
 872     /* The imaginary pixel before the first is considered a white pixel.
 873      * So if the first pixel in the row is black, it is considered
 874      * a "changing" pixel (white->black).
 875      */
 876     a1 = scan_to (       0x00, pbPixelRow, 0,  iPixels);
 877     b1 = scan_to (       0x00, pbRefRow,   0,  iPixels);
 878     b2 = scan_to ((UINT)~0x00, pbRefRow, b1+1, iPixels);
 879     skip = (UINT)~0x00u;   /* white, initially */
 880     a0 = 0;
 881
 882     while (TRUE) {
 883
 884         /* output one of the modes */
 885
 886         iDelta = a1 - b1;
 887
 888         if (b2 < a1) {    /* pass mode */
 889             put_bits (g,4,1);
 890             need = B1 | B2;
 891             a0 = b2;
 892             b1 = b2;
 893         } else if (-3<=iDelta && iDelta<=3) {    /* vertical mode */
 894             huff_t te = VertTbl[iDelta+3];
 895             put_bits (g, te.length, te.bits);
 896             need = A1 | B2;
 897             if (b2==a1 || iDelta<=-2)
 898                 need = A1 | B0 | B1 | B2;
 899             a0 = a1;
 900             b1 = b2;
 901             skip = ~skip;
 902         } else {          /* horizontal mode */
 903             a2 = scan_to (skip, pbPixelRow, a1+1, iPixels);
 904             put_bits (g,3,1);
 905             if (skip) {
 906                 PutWhiteRun (g,a1-a0);
 907                 PutBlackRun (g,a2-a1);
 908             } else {
 909                 PutBlackRun (g,a1-a0);
 910                 PutWhiteRun (g,a2-a1);
 911             }
 912             if (a2 > b2) {
 913                 need = A1 | B0 | B1 | B2;
 914             } else if (a2 < b1) {
 915                 need = A1;
 916             } else {
 917                 b1 = b2;
 918                 need = A1 | B1 | B2;
 919             }
 920             a0 = a2;
 921         }
 922
 923         if (a0 >= iPixels)
 924             break;
 925
 926         /* compute next a1, b1, b2 */
 927
 928         if (need & A1) a1 = scan_to (~skip, pbPixelRow, a0+1, iPixels);
 929         if (need & B0) b1 = scan_to ( skip, pbRefRow,   a0,   iPixels);
 930         if (need & B1) b1 = scan_to (~skip, pbRefRow,   b1+1, iPixels);
 931         if (need & B2) b2 = scan_to ( skip, pbRefRow,   b1+1, iPixels);
 932     }
 933 }
 934
 935
 936
 937 /*
 938 @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
 939 @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
 940 @@                                                                          @@
 941 @@                                                                          @@
 942 @@                           E  N  C  O  D  E  R                            @@
 943 @@                                                                          @@
 944 @@                                                                          @@
 945 @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
 946 @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
 947 */
 948
 949
 950
 951 /*****************************************************************************\
 952  *
 953  * faxEncode_openXform - Creates a new instance of the transformer
 954  *
 955  *****************************************************************************
 956  *
 957  * This returns a handle for the new instance to be passed into
 958  * all subsequent calls.
 959  *
 960  * Return value: IP_DONE=success; IP_FATAL_ERROR=misc error.
 961  *
 962 \*****************************************************************************/
 963
 964 static WORD faxEncode_openXform (
 965     IP_XFORM_HANDLE *pXform)   /* out: returned handle */
 966 {
 967     PENC_INST g;
 968
 969     INSURE (pXform != NULL);
 970     IP_MEM_ALLOC (sizeof(ENC_INST), g);
 971     *pXform = g;
 972     memset (g, 0, sizeof(ENC_INST));
 973     g->dwValidChk = CHECK_VALUE;
 974     put_init (g, NULL);   /* put_new_buf will be called later */
 975
 976     return IP_DONE;
 977
 978     fatal_error:
 979     return IP_FATAL_ERROR;
 980 }
 981
 982
 983
 984 /*****************************************************************************\
 985  *
 986  * faxEncode_setDefaultInputTraits - Specifies default input image traits
 987  *
 988  *****************************************************************************
 989  *
 990  * The header of the file-type handled by the transform probably does
 991  * not include *all* the image traits we'd like to know.  Those not
 992  * specified in the file-header are filled in from info provided by
 993  * this routine.
 994  *
 995  * Return value: IP_DONE=success; IP_FATAL_ERROR=misc error.
 996  *
 997 \*****************************************************************************/
 998
 999 static WORD faxEncode_setDefaultInputTraits (
1000     IP_XFORM_HANDLE  hXform,     /* in: handle for xform */
1001     PIP_IMAGE_TRAITS pTraits)    /* in: default image traits */
1002 {
1003     PENC_INST g;
1004
1005     HANDLE_TO_PTR (hXform, g);
1006
1007     /* Insure that values we actually use or care about are known */
1008     INSURE (pTraits->iPixelsPerRow > 0);   /* we need the row-length */
1009     INSURE (pTraits->iBitsPerPixel == 1);  /* image must be bi-level */
1010
1011     g->traits = *pTraits;   /* a structure copy */
1012
1013     return IP_DONE;
1014
1015     fatal_error:
1016     return IP_FATAL_ERROR;
1017 }
1018
1019
1020
1021 /*****************************************************************************\
1022  *
1023  * faxEncode_setXformSpec - Provides xform-specific information
1024  *
1025 \*****************************************************************************/
1026
1027 static WORD faxEncode_setXformSpec (
1028     IP_XFORM_HANDLE  hXform,         /* in: handle for xform */
1029     DWORD_OR_PVOID   aXformInfo[])   /* in: xform information */
1030 {
1031     PENC_INST g;
1032
1033     HANDLE_TO_PTR (hXform, g);
1034     g->wOutFmt  = (BYTE)aXformInfo[IP_FAX_FORMAT].dword;
1035     g->fNoEOLs  = (BOOL)aXformInfo[IP_FAX_NO_EOLS].dword;
1036     g->wMinBits = (WORD)aXformInfo[IP_FAX_MIN_ROW_LEN].dword;
1037     return IP_DONE;
1038
1039     fatal_error:
1040     return IP_FATAL_ERROR;
1041 }
1042
1043
1044
1045 /*****************************************************************************\
1046  *
1047  * faxEncode_getHeaderBufSize- Returns size of input buf needed to hold header
1048  *
1049 \*****************************************************************************/
1050
1051 static WORD faxEncode_getHeaderBufSize (
1052     IP_XFORM_HANDLE  hXform,          /* in:  handle for xform */
1053     DWORD           *pdwInBufLen)     /* out: buf size for parsing header */
1054 {
1055     /* since input is raw pixels, there is no header, so set it to zero */
1056     *pdwInBufLen = 0;
1057     return IP_DONE;
1058 }
1059
1060
1061
1062 /*****************************************************************************\
1063  *
1064  * faxEncode_getActualTraits - Parses header, and returns input & output traits
1065  *
1066  *****************************************************************************
1067  *
1068  * For this fax xform driver, this routine merely returns input traits.
1069  *
1070 \*****************************************************************************/
1071
1072 static WORD faxEncode_getActualTraits (
1073     IP_XFORM_HANDLE  hXform,         /* in:  handle for xform */
1074     DWORD            dwInputAvail,   /* in:  # avail bytes in input buf */
1075     PBYTE            pbInputBuf,     /* in:  ptr to input buffer */
1076     PDWORD           pdwInputUsed,   /* out: # bytes used from input buf */
1077     PDWORD           pdwInputNextPos,/* out: file-pos to read from next */
1078     PIP_IMAGE_TRAITS pInTraits,      /* out: input image traits */
1079     PIP_IMAGE_TRAITS pOutTraits)     /* out: output image traits */
1080 {
1081     PENC_INST g;
1082     int       inBytes;
1083
1084     HANDLE_TO_PTR (hXform, g);
1085
1086     /* Since there is no header, we'll report no usage of input */
1087
1088     *pdwInputUsed    = 0;
1089     *pdwInputNextPos = 0;
1090
1091     /* Since we don't change traits, just copy out the default traits */
1092
1093     *pInTraits  = g->traits;
1094     *pOutTraits = g->traits;
1095
1096     /* Compute some stuff */
1097
1098     g->iRowLen = g->traits.iPixelsPerRow;   /* todo: eliminate redundant var */
1099
1100     /* below, if vert dpi is unknown (negative), we use cycle-len of 2 */
1101     g->w12Cycle = (g->traits.lVertDPI < (150l<<16)) ? 2 : 4;
1102
1103     /* Allocate the prior-row buffer, if needed */
1104
1105     if (g->wOutFmt != IP_FAX_MH) {
1106         if (g->prior_p != NULL)
1107             IP_MEM_FREE (g->prior_p);
1108         inBytes = (g->iRowLen+7) / 8;
1109         IP_MEM_ALLOC (inBytes, g->prior_p);
1110         memset (g->prior_p, 0, inBytes);
1111     }
1112
1113     return IP_DONE | IP_READY_FOR_DATA;
1114
1115     fatal_error:
1116     return IP_FATAL_ERROR;
1117 }
1118
1119
1120
1121 /****************************************************************************\
1122  *
1123  * faxEncode_getActualBufSizes - Returns buf sizes needed for remainder of job
1124  *
1125 \****************************************************************************/
1126
1127 static WORD faxEncode_getActualBufSizes (
1128     IP_XFORM_HANDLE  hXform,           /* in:  handle for xform */
1129     PDWORD           pdwMinInBufLen,   /* out: min input buf size */
1130     PDWORD           pdwMinOutBufLen)  /* out: min output buf size */
1131 {
1132     PENC_INST g;
1133     UINT      uWorstBuf, uMinBytes;
1134
1135     HANDLE_TO_PTR (hXform, g);
1136     *pdwMinInBufLen = (g->iRowLen+7) / 8;
1137
1138     uWorstBuf = worst_buf_size (g->wOutFmt, g->iRowLen);
1139     uMinBytes = (g->wMinBits+7) / 8;
1140     *pdwMinOutBufLen = uWorstBuf > uMinBytes ? uWorstBuf : uMinBytes;
1141     return IP_DONE;
1142
1143     fatal_error:
1144     return IP_FATAL_ERROR;
1145 }
1146
1147
1148
1149 /*****************************************************************************\
1150  *
1151  * faxEncode_convert - the work-horse routine
1152  *
1153  *****************************************************************************
1154  *
1155  * This routine (actually put_bits) hangs onto the last 1-3 bytes of
1156  * encoded row-data due to its buffering method.
1157  *
1158 \*****************************************************************************/
1159
1160 static WORD faxEncode_convert (
1161     IP_XFORM_HANDLE hXform,
1162     DWORD           dwInputAvail,     /* in:  # avail bytes in in-buf */
1163     PBYTE           pbInputBuf,       /* in:  ptr to in-buffer */
1164     PDWORD          pdwInputUsed,     /* out: # bytes used from in-buf */
1165     PDWORD          pdwInputNextPos,  /* out: file-pos to read from next */
1166     DWORD           dwOutputAvail,    /* in:  # avail bytes in out-buf */
1167     PBYTE           pbOutputBuf,      /* in:  ptr to out-buffer */
1168     PDWORD          pdwOutputUsed,    /* out: # bytes written in out-buf */
1169     PDWORD          pdwOutputThisPos) /* out: file-pos to write the data */
1170 {
1171     PENC_INST g;
1172     int       inBytes;
1173     int       i;
1174
1175     HANDLE_TO_PTR (hXform, g);
1176
1177     put_new_buf (g, pbOutputBuf);
1178
1179       /********************************************************/
1180      /* If we're being told to flush, output the ending EOLs */
1181     /********************************************************/
1182
1183     if (dwInputAvail == 0) {
1184
1185         switch (g->wOutFmt) {
1186             case IP_FAX_MH:
1187                 for (i=6; i>0; i--)
1188                     PutEOL (g);
1189             break;
1190
1191             case IP_FAX_MR:
1192                 for (i=6; i>0; i--) {
1193                     PutEOL (g);
1194                     put_bits_routine (g,1,1);
1195                 }
1196             break;
1197
1198             case IP_FAX_MMR:
1199                 PutEOL (g);
1200                 PutEOL (g);
1201             break;
1202         }
1203
1204         *pdwInputUsed     = 0;
1205         *pdwOutputUsed    = put_done (g);
1206         *pdwInputNextPos  = g->dwInNextPos;
1207         *pdwOutputThisPos = g->dwOutNextPos;
1208         return IP_DONE;
1209     }
1210
1211       /******************************/
1212      /* Normal Case (not flushing) */
1213     /******************************/
1214
1215     inBytes = (g->iRowLen+7) / 8;
1216     INSURE (dwInputAvail  >= (DWORD)inBytes);
1217     INSURE (dwOutputAvail >  0);
1218
1219     switch (g->wOutFmt) {
1220         case IP_FAX_MH:
1221             encode_row_1d (g, pbInputBuf, g->iRowLen, FALSE);
1222             put_fill_bits (g);
1223         break;
1224
1225         case IP_FAX_MR:
1226             if (g->iRowNum % g->w12Cycle == 0)
1227                 encode_row_1d (g, pbInputBuf, g->iRowLen, TRUE);
1228             else
1229                 encode_row_2d (g, pbInputBuf, g->prior_p, g->iRowLen, TRUE);
1230             put_fill_bits (g);
1231         break;
1232
1233         case IP_FAX_MMR:
1234             encode_row_2d (g, pbInputBuf, g->prior_p, g->iRowLen, FALSE);
1235         break;
1236     }
1237
1238     if (g->prior_p != NULL)
1239         memcpy (g->prior_p, pbInputBuf, inBytes);
1240
1241     *pdwInputUsed     = inBytes;
1242     g->dwInNextPos   += inBytes;
1243     *pdwInputNextPos  = g->dwInNextPos;
1244
1245     *pdwOutputUsed    = put_grab (g);
1246     *pdwOutputThisPos = g->dwOutNextPos;
1247     g->dwOutNextPos  += *pdwOutputUsed;
1248     g->iRowNum += 1;
1249
1250     return IP_CONSUMED_ROW | IP_PRODUCED_ROW | IP_READY_FOR_DATA;
1251
1252     fatal_error:
1253     return IP_FATAL_ERROR;
1254 }
1255
1256
1257
1258 /*****************************************************************************\
1259  *
1260  * faxEncode_insertedData - client inserted into our output stream
1261  *
1262 \*****************************************************************************/
1263
1264 static WORD faxEncode_insertedData (
1265     IP_XFORM_HANDLE hXform,
1266     DWORD           dwNumBytes)
1267 {
1268     fatalBreakPoint ();
1269     return IP_FATAL_ERROR;   /* must never be called (can't insert data) */
1270 }
1271
1272
1273
1274 /*****************************************************************************\
1275  *
1276  * faxEncode_newPage - Tells us to flush this page, and start a new page
1277  *
1278 \*****************************************************************************/
1279
1280 static WORD faxEncode_newPage (
1281     IP_XFORM_HANDLE hXform)
1282 {
1283     PENC_INST g;
1284
1285     HANDLE_TO_PTR (hXform, g);
1286     /* todo: output EOLs to mark a new page */
1287     return IP_DONE;
1288
1289     fatal_error:
1290     return IP_FATAL_ERROR;
1291
1292 }
1293
1294
1295
1296 /*****************************************************************************\
1297  *
1298  * faxEncode_closeXform - Destroys this instance
1299  *
1300 \*****************************************************************************/
1301
1302 static WORD faxEncode_closeXform (IP_XFORM_HANDLE hXform)
1303 {
1304     PENC_INST g;
1305
1306     HANDLE_TO_PTR (hXform, g);
1307
1308     if (g->prior_p != NULL)
1309         IP_MEM_FREE (g->prior_p);
1310
1311     g->dwValidChk = 0;
1312     IP_MEM_FREE (g);       /* free memory for the instance */
1313     return IP_DONE;
1314
1315     fatal_error:
1316     return IP_FATAL_ERROR;
1317 }
1318
1319
1320
1321 /*****************************************************************************\
1322  *
1323  * faxEncodeTbl - Jump-table for encoder
1324  *
1325 \*****************************************************************************/
1326
1327 IP_XFORM_TBL faxEncodeTbl = {
1328     faxEncode_openXform,
1329     faxEncode_setDefaultInputTraits,
1330     faxEncode_setXformSpec,
1331     faxEncode_getHeaderBufSize,
1332     faxEncode_getActualTraits,
1333     faxEncode_getActualBufSizes,
1334     faxEncode_convert,
1335     faxEncode_newPage,
1336     faxEncode_insertedData,
1337     faxEncode_closeXform
1338 };
1339
1340
1341
1342 /*
1343 @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
1344 @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
1345 @@                                                                          @@
1346 @@                                                                          @@
1347 @@                           D  E  C  O  D  E  R                            @@
1348 @@                                                                          @@
1349 @@                                                                          @@
1350 @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
1351 @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
1352 */
1353
1354
1355 /* white/nonwhite might be put in interface later on */
1356 #define NONWHITE_ROW   0x0000   /* row is not all white */
1357 #define    WHITE_ROW   0x0000   /* row is all white */
1358
1359 #define MAX_CODE_LEN   13  /* length of longest code */
1360 #define EOL_LEN        12  /* EOL is 11 zeroes and a one */
1361 #define EOLS_FOR_MH_MR 3   /* the std says 6, but some might be zapped */
1362 #define EOLS_FOR_MMR   1   /* the std says 2, but we'll stop at first because
1363                             * we might not be able to fetch the second EOL from
1364                             * the cache because we won't fetch anything unless
1365                             * it contains 13 bits, and an EOL is only 12 */
1366
1367 /* Huffman tables (at end of file): */
1368
1369 extern const BYTE   fax_vert_huff_index[];
1370 extern const USHORT fax_vert_huff[];
1371 extern const BYTE   fax_black_huff_index[];
1372 extern const USHORT fax_black_huff[];
1373 extern const BYTE   fax_white_huff_index[];
1374 extern const USHORT fax_white_huff[];
1375
1376 #define MAX_BLACK_CODELEN  13
1377 #define MAX_WHITE_CODELEN  12
1378 #define MAX_VERT_CODELEN   7
1379
1380 #define CODELEN_SHIFT  12
1381 #define VALUE_MASK     0x0fffu
1382
1383 /* items only in fax_vert_huff table: */
1384 #define LAST_VERT  6
1385 #define PASS_MODE  7
1386 #define HORIZ_MODE 8
1387
1388 enum {
1389     RET_GOT_CODE,      /* we parsed a good code (ret in *piResult)         */
1390     RET_BAD_CODE,      /* trash in row-data                                */
1391     RET_FILL,          /* got some fill-zeroes                             */
1392     RET_HIT_EOL,       /* hit EOL; no row-data was parsed or returned      */
1393     RET_NEED_MORE      /* need more input-bytes to complete the row        */
1394 };
1395
1396
1397
1398 /*____________________________________________________________________________
1399  |                                                                            |
1400  | Type-definition of our instance-variables                                  |
1401  |____________________________________________________________________________|
1402 */
1403
1404 typedef enum {
1405     NORMAL_2D,
1406     HORIZ_1ST,
1407     HORIZ_2ND
1408 } STATE_2D;
1409
1410 typedef struct {
1411     IP_IMAGE_TRAITS traits;   /* traits of the image                          */
1412     DWORD    dwInNextPos;     /* file pos for subsequent input                */
1413     DWORD    dwOutNextPos;    /* file pos for subsequent output               */
1414     DWORD    dwValidChk;      /* struct validity check value                  */
1415
1416     /* Variables for getting bits: */
1417     BYTE    *gb_buf_p;        /* beginning of our buffer                      */
1418     BYTE    *gb_buf_after_p;  /* 1st byte after our buffer                    */
1419     BYTE    *gb_byte_p;       /* ptr to next byte                             */
1420     int      gb_cache_cnt;    /* # of available bits in gb_cache              */
1421     DWORD    gb_cache;        /* 32-bit buffer to cache the next few bits     */
1422                               /* is also pos of next avail bit; msb=32, lsb=1 */
1423     int      gb_num_zeroes;   /* # of successive zero-bits we've gotten       */
1424
1425     /* Variables for row-decoding functions: */
1426     int      pixel_pos;       /* coordinate of next pixel; 0 is leftmost      */
1427     BYTE     white;           /* doing a white run? (00=black, FF=white)      */
1428     STATE_2D state_2d;        /* state of the 2-dim decoder                   */
1429     int      a0;              /* pixel before 1st is an imaginary white pixel */
1430     BYTE    *prior_p;         /* buffer containing prior row                  */
1431     BOOL     ref_row_invalid; /* (MR only) reference row invalid due to error?*/
1432
1433     /* Variables for the exported functions: */
1434     BYTE     input_format;    /* input format (IP_FAX_MH/MR/MMR)              */
1435     BYTE     num_eols;        /* number of successive EOLs we've gotten       */
1436     BOOL     no_eols;         /* are EOLs not present in input?               */
1437     BOOL     toss_everything; /* are we discarding all data due to prior err? */
1438     BOOL     flushing_to_eol; /* are we ignoring bits until an EOL?           */
1439     BOOL     got_fill;        /* gotten any fill-zeroes?                      */
1440     BOOL     got_black;       /* set any black pixels in the row?             */
1441     BOOL     two_dim;         /* next row is 2-dimensional encoding?          */
1442     int      row_len;         /* # pixels in each row                         */
1443     int      bytes_in_row;    /* # bytes in each row                          */
1444 } DEC_INST, *PDEC_INST;
1445
1446
1447
1448 /*****************************************************************************
1449  *                                                                           *
1450  *                       F E T C H I N G   B I T S                           *
1451  *                                                                           *
1452  *****************************************************************************
1453
1454
1455 Interface into this section:
1456
1457     bits_init         - inits this section
1458     bits_buf_open     - gives us (this section) a buffer to consume
1459     BITS_REFILL_CACHE - fills cache; must be called before parsing
1460     BITS_IN_CACHE     - returns # bits currently in the cache
1461     BITS_LOAD         - returns next N bits of input (no advance is done)
1462     BITS_ADVANCE      - advances input by the given # of bits
1463     bits_buf_close    - returns # bytes consumed in buffer
1464     bits_flush        - discards all unread bits
1465     bits_flush_to_eol - flushes input bits until EOL is encountered
1466 */
1467
1468
1469
1470 /*____________________________________________________________________________
1471  |           |                                                                |
1472  | bits_init | initializes this "fetching bits" section                       |
1473  |___________|________________________________________________________________|
1474 */
1475 static void bits_init (DEC_INST *g)
1476 {
1477     g->gb_num_zeroes = 0;
1478     g->gb_cache_cnt = 0;    /* the cache is empty */
1479 }
1480
1481
1482
1483 /*____________________________________________________________________________
1484  |               |                                                            |
1485  | bits_buf_open | gives us (this section) a buffer to consume                |
1486  |_______________|____________________________________________________________|
1487 */
1488 static void bits_buf_open (
1489     DEC_INST  *g,
1490     BYTE      *buf_p,
1491     int        num_bytes)
1492 {
1493     g->gb_byte_p      = buf_p;
1494     g->gb_buf_p       = buf_p;
1495     g->gb_buf_after_p = buf_p + num_bytes;
1496 }
1497
1498
1499
1500 /*____________________________________________________________________________
1501  |                |                                                           |
1502  | bits_buf_close | returns # bytes consumed in buffer                        |
1503  |________________|___________________________________________________________|
1504 */
1505 static UINT bits_buf_close (DEC_INST *g)
1506 {
1507     return (g->gb_byte_p - g->gb_buf_p);
1508 }
1509
1510
1511
1512 /*____________________________________________________________________________
1513  |            |                                                               |
1514  | bits_flush | discards all unread bits                                      |
1515  |____________|_______________________________________________________________|
1516 */
1517 static void bits_flush (DEC_INST *g)
1518 {
1519     g->gb_cache_cnt = 0;
1520     g->gb_byte_p = g->gb_buf_after_p;
1521 }
1522
1523
1524
1525 /*____________________________________________________________________________
1526  |                   |                                                        |
1527  | BITS_REFILL_CACHE | fills cache as full as possible                        |
1528  |___________________|________________________________________________________|
1529 */
1530 #define BITS_REFILL_CACHE(g)                                        \
1531 {                                                                   \
1532     int    cache_cnt   = g->gb_cache_cnt;                           \
1533     DWORD  cache       = g->gb_cache;                               \
1534     BYTE  *byte_p      = g->gb_byte_p;                              \
1535     BYTE  *buf_after_p = g->gb_buf_after_p;                         \
1536                                                                     \
1537     while (cache_cnt<=24 && byte_p<buf_after_p) {                   \
1538         cache = (cache << 8) | (*byte_p++);                         \
1539         cache_cnt += 8;                                             \
1540     }                                                               \
1541                                                                     \
1542     g->gb_cache_cnt = cache_cnt;                                    \
1543     g->gb_cache     = cache;                                        \
1544     g->gb_byte_p    = byte_p;                                       \
1545 }
1546
1547
1548
1549 /*____________________________________________________________________________
1550  |               |                                                            |
1551  | BITS_IN_CACHE | returns # bits currently in the bit-cache                  |
1552  |_______________|____________________________________________________________|
1553 */
1554 #define BITS_IN_CACHE(g)  (g->gb_cache_cnt)
1555
1556
1557
1558 /*____________________________________________________________________________
1559  |                   |                                                        |
1560  | bits_flush_to_eol | flushes input bits until EOL is encountered            |
1561  |___________________|________________________________________________________|
1562  |                                                                            |
1563  | If got_fill is TRUE, then we merely scan for a set bit.                    |
1564  | Otherwise, we first count leading zeroes until it reaches 11.              |
1565  |                                                                            |
1566  | Return value:  TRUE  = We hit an EOL.  In this case, if leave_a_bit is     |
1567  |                        TRUE, the cache will contain at least one bit so    |
1568  |                        you can fetch a 1-dim/2-dim bit.                    |
1569  |                FALSE = We need more input data.                            |
1570  |____________________________________________________________________________|
1571 */
1572 static BOOL bits_flush_to_eol (
1573     DEC_INST *g,         /* our instance vars */
1574     BOOL    got_fill,    /* have we gotten fill zeroes? */
1575     BOOL    leave_a_bit) /* after hitting EOL, insure that cache isn't empty? */
1576 {
1577     #define CLEAR_UNUSED_CACHE_BITS                             \
1578         if (g->gb_cache_cnt < 32)                               \
1579             g->gb_cache &= (1lu << g->gb_cache_cnt) - 1lu;
1580
1581     DWORD bit;
1582     BYTE  byt;
1583
1584       /*********************************************/
1585      /* Scan input until 11 zeroes have been seen */
1586     /*********************************************/
1587
1588     if (g->gb_num_zeroes >= 11)
1589         got_fill = TRUE;
1590
1591     if (! got_fill)
1592     {
1593         if (g->gb_cache_cnt != 0) {
1594             for (bit = (1lu<<(g->gb_cache_cnt-1));
1595                  bit != 0;
1596                  bit >>= 1) {
1597                 g->gb_cache_cnt -= 1;
1598                 if (bit & g->gb_cache)
1599                     g->gb_num_zeroes =0;
1600                 else {
1601                     g->gb_num_zeroes += 1;
1602                     if (g->gb_num_zeroes >= 11)
1603                         break;
1604                 }
1605             }
1606         }
1607
1608         /* the cache is now empty; start scanning bytes */
1609
1610         while (TRUE) {
1611             if (g->gb_byte_p >= g->gb_buf_after_p)
1612                 return FALSE;
1613             byt = *(g->gb_byte_p)++;
1614             g->gb_num_zeroes += baLeftZeroesTbl[byt];
1615             if (g->gb_num_zeroes >= 11) {
1616                 g->gb_byte_p -= 1;
1617                 break;
1618             }
1619             if (byt != 0)
1620                 g->gb_num_zeroes = baRightZeroesTbl[byt];
1621         }
1622     }
1623
1624       /*******************************************/
1625      /* Scan input until a non-zero bit is seen */
1626     /*******************************************/
1627
1628     while (TRUE)
1629     {
1630         BITS_REFILL_CACHE (g)
1631         if (g->gb_cache_cnt==0 || (leave_a_bit && g->gb_cache_cnt==1))
1632             return FALSE;
1633
1634         CLEAR_UNUSED_CACHE_BITS
1635
1636         if (g->gb_cache == 0)
1637             g->gb_cache_cnt = 0;   /* cache is all zeroes; discard it */
1638         else {
1639             /* we hit the EOL */
1640             for (bit = (1lu<<(g->gb_cache_cnt-1));
1641                  (bit & g->gb_cache) == 0;
1642                  bit >>= 1)
1643                 g->gb_cache_cnt -= 1;   /* discard the 0's before the 1 */
1644
1645             /* After discarding the set bit, if leave_a_bit is TRUE, we want
1646              * the cache to be non-empty so that a 1-dim/2-dim bit can then
1647              * be fetched.  Hence the check for 2 bits in cache below.
1648              */
1649             if (!leave_a_bit || g->gb_cache_cnt>=2) {
1650                 g->gb_cache_cnt -= 1;  /* discard the set bit we found above */
1651                 g->gb_num_zeroes = 0;
1652                 return TRUE;
1653             }
1654         }
1655
1656         /* discard zero bytes */
1657
1658         /* Warning: If fax_decode_convert_row was told to flush, both
1659          * pointers gb_byte_p and gb_buf_after_p can be NULL.  So the
1660          * pointer-compare below must be *before* the dereference in the
1661          * test of the while loop, to avoid dereferencing a NULL pointer.
1662          */
1663         if (g->gb_cache_cnt == 0)
1664             while (g->gb_byte_p<g->gb_buf_after_p && *(g->gb_byte_p)==0)
1665                 g->gb_byte_p++;
1666     }
1667 }
1668
1669
1670
1671 /*____________________________________________________________________________
1672  |           |                                                                |
1673  | BITS_LOAD | returns the next num_bits of input, with NO advance            |
1674  |___________|________________________________________________________________|
1675 */
1676 #define BITS_LOAD(g, num_bits, par_result) {                                 \
1677     int n_bits = (int)(num_bits);                                            \
1678                                                                              \
1679     par_result = (g->gb_cache >> (g->gb_cache_cnt-n_bits))                   \
1680                  & ((1u<<n_bits) - 1u);                                      \
1681 }
1682
1683 #if 0
1684
1685 #define BITS_LOAD(g, num_bits, par_result) {                                 \
1686     int n_bits = (int)(num_bits);                                            \
1687                                                                              \
1688     par_result = g->gb_cache;                                                \
1689                                                                              \
1690     asm ("extract %1,%2,%0"                                                  \
1691         : "=d" (par_result)                                                  \
1692         : "dI" (g->gb_cache_cnt - n_bits), "dI" (n_bits), "0" (par_result)); \
1693 }
1694
1695 #endif
1696
1697
1698
1699 /*____________________________________________________________________________
1700  |              |                                                             |
1701  | BITS_ADVANCE | advances input by num_bits bits                             |
1702  |______________|_____________________________________________________________|
1703 */
1704 #define BITS_ADVANCE(g, num_bits) {             \
1705     g->gb_cache_cnt -= (num_bits);              \
1706 }
1707
1708
1709
1710 /*****************************************************************************
1711  *                                                                           *
1712  *                           U T I L I T I E S                               *
1713  *                                                                           *
1714  *****************************************************************************/
1715
1716
1717
1718 /*____________________________________________________________________________
1719  |                    |                                                       |
1720  | parse_code_routine | Parses a Huffman code using the given code tables     |
1721  |____________________|_______________________________________________________|
1722  |                                                                            |
1723  | Function return values:  RET_GOT_CODE                                      |
1724  |                          RET_BAD_CODE                                      |
1725  |                          RET_FILL                                          |
1726  |                          RET_HIT_EOL                                       |
1727  |                          RET_NEED_MORE                                     |
1728  |                                                                            |
1729  | This function must NOT be called to scan for an EOL after it has           |
1730  | returned RET_BAD_CODE or RET_FILL.                                         |
1731  |                                                                            |
1732  | Warning:  When this returns RET_HIT_EOL, it must guarantee that the        |
1733  | bit-cache is not empty so a 1-dim/2-dim bit can be fetched.                |
1734  |____________________________________________________________________________|
1735 */
1736
1737 static UINT parse_code_routine (
1738     DEC_INST    *g,
1739     int          bits_in_index, /* in:  # bits in index for index_tbl */
1740     const BYTE   index_tbl[],   /* in:  contains indices into value_tbl */
1741     const USHORT value_tbl[],   /* in:  contains [codelen, value] pairs */
1742     int         *value_p)       /* out: the value corresponding to the code */
1743 {
1744     UINT blob, values;
1745
1746     BITS_REFILL_CACHE(g)
1747     if (BITS_IN_CACHE(g) < bits_in_index)
1748         return RET_NEED_MORE;
1749
1750     BITS_LOAD (g, bits_in_index, blob);
1751     values = value_tbl[index_tbl[blob]];
1752
1753     if (values != 0) {
1754         /* normal case: we got a valid code */
1755         BITS_ADVANCE (g, values >> CODELEN_SHIFT);
1756         *value_p = values & VALUE_MASK;
1757         return RET_GOT_CODE;
1758     }
1759
1760     if (BITS_IN_CACHE(g) < MAX_CODE_LEN)
1761         return RET_NEED_MORE;
1762
1763     BITS_LOAD (g, EOL_LEN, blob);
1764
1765     if (blob == 1) {
1766         BITS_ADVANCE (g, EOL_LEN);
1767         return RET_HIT_EOL;
1768     }
1769
1770     if (blob == 0) {
1771         BITS_ADVANCE (g, EOL_LEN);
1772         return RET_FILL;
1773     }
1774
1775     return RET_BAD_CODE;
1776 }
1777
1778
1779
1780 /*____________________________________________________________________________
1781  |            |                                                               |
1782  | PARSE_CODE | A fast macro for parsing Huffman codes                        |
1783  |____________|_______________________________________________________________|
1784 */
1785 #define PARSE_CODE(                                                           \
1786     g,                                                                        \
1787     bits_in_index,  /* in:  # bits in index for index_tbl */                  \
1788     index_tbl,      /* in:  contains indices into value_tbl */                \
1789     value_tbl,      /* in:  contains [codelen, value] pairs */                \
1790     out_result,     /* out: RET_GOT_CODE, RET_BAD_CODE, etc */                \
1791     out_value)      /* out: the value corresponding to the code */            \
1792 do {                                                                          \
1793     UINT blob, values;                                                        \
1794                                                                               \
1795     if (BITS_IN_CACHE(g) < bits_in_index)                                     \
1796         goto call##value_tbl;                                                 \
1797                                                                               \
1798     BITS_LOAD (g, bits_in_index, blob);                                       \
1799     values = value_tbl[index_tbl[blob]];                                      \
1800                                                                               \
1801     if (values == 0) {                                                        \
1802         call##value_tbl:                                                      \
1803         out_result = parse_code_routine                                       \
1804                        (g, bits_in_index, index_tbl, value_tbl, &out_value);  \
1805     } else {                                                                  \
1806         BITS_ADVANCE (g, values >> CODELEN_SHIFT);                            \
1807         out_result = RET_GOT_CODE;                                            \
1808         out_value  = values & VALUE_MASK;                                     \
1809     }                                                                         \
1810 } while (0)
1811
1812
1813
1814 /*____________________________________________________________________________
1815  |            |                                                               |
1816  | runs_array | all possible runs that fit in 16 bits                         |
1817  |____________|_______________________________________________________________|
1818  |                                                                            |
1819  | This array is indexed by (leftbit<<4)+rightbit.                            |
1820  | Leftbit and rightbit are in 0..15.  0=msb, 15=lsb.                         |
1821  |____________________________________________________________________________|
1822 */
1823
1824 static const USHORT runs_array_le[256] = {   /* little-endian array */
1825     0x0080, 0x00c0, 0x00e0, 0x00f0, 0x00f8, 0x00fc, 0x00fe, 0x00ff,
1826     0x80ff, 0xc0ff, 0xe0ff, 0xf0ff, 0xf8ff, 0xfcff, 0xfeff, 0xffff,
1827     0x0000, 0x0040, 0x0060, 0x0070, 0x0078, 0x007c, 0x007e, 0x007f,
1828     0x807f, 0xc07f, 0xe07f, 0xf07f, 0xf87f, 0xfc7f, 0xfe7f, 0xff7f,
1829     0x0000, 0x0000, 0x0020, 0x0030, 0x0038, 0x003c, 0x003e, 0x003f,
1830     0x803f, 0xc03f, 0xe03f, 0xf03f, 0xf83f, 0xfc3f, 0xfe3f, 0xff3f,
1831     0x0000, 0x0000, 0x0000, 0x0010, 0x0018, 0x001c, 0x001e, 0x001f,
1832     0x801f, 0xc01f, 0xe01f, 0xf01f, 0xf81f, 0xfc1f, 0xfe1f, 0xff1f,
1833     0x0000, 0x0000, 0x0000, 0x0000, 0x0008, 0x000c, 0x000e, 0x000f,
1834     0x800f, 0xc00f, 0xe00f, 0xf00f, 0xf80f, 0xfc0f, 0xfe0f, 0xff0f,
1835     0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0004, 0x0006, 0x0007,
1836     0x8007, 0xc007, 0xe007, 0xf007, 0xf807, 0xfc07, 0xfe07, 0xff07,
1837     0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0002, 0x0003,
1838     0x8003, 0xc003, 0xe003, 0xf003, 0xf803, 0xfc03, 0xfe03, 0xff03,
1839     0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0001,
1840     0x8001, 0xc001, 0xe001, 0xf001, 0xf801, 0xfc01, 0xfe01, 0xff01,
1841     0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000,
1842     0x8000, 0xc000, 0xe000, 0xf000, 0xf800, 0xfc00, 0xfe00, 0xff00,
1843     0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000,
1844     0x0000, 0x4000, 0x6000, 0x7000, 0x7800, 0x7c00, 0x7e00, 0x7f00,
1845     0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000,
1846     0x0000, 0x0000, 0x2000, 0x3000, 0x3800, 0x3c00, 0x3e00, 0x3f00,
1847     0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000,
1848     0x0000, 0x0000, 0x0000, 0x1000, 0x1800, 0x1c00, 0x1e00, 0x1f00,
1849     0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000,
1850     0x0000, 0x0000, 0x0000, 0x0000, 0x0800, 0x0c00, 0x0e00, 0x0f00,
1851     0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000,
1852     0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0400, 0x0600, 0x0700,
1853     0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000,
1854     0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0200, 0x0300,
1855     0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000,
1856     0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0100,
1857 };
1858
1859 static const USHORT runs_array_be[256] = {    /* big-endian array */
1860     0x8000, 0xc000, 0xe000, 0xf000, 0xf800, 0xfc00, 0xfe00, 0xff00,
1861     0xff80, 0xffc0, 0xffe0, 0xfff0, 0xfff8, 0xfffc, 0xfffe, 0xffff,
1862     0x0000, 0x4000, 0x6000, 0x7000, 0x7800, 0x7c00, 0x7e00, 0x7f00,
1863     0x7f80, 0x7fc0, 0x7fe0, 0x7ff0, 0x7ff8, 0x7ffc, 0x7ffe, 0x7fff,
1864     0x0000, 0x0000, 0x2000, 0x3000, 0x3800, 0x3c00, 0x3e00, 0x3f00,
1865     0x3f80, 0x3fc0, 0x3fe0, 0x3ff0, 0x3ff8, 0x3ffc, 0x3ffe, 0x3fff,
1866     0x0000, 0x0000, 0x0000, 0x1000, 0x1800, 0x1c00, 0x1e00, 0x1f00,
1867     0x1f80, 0x1fc0, 0x1fe0, 0x1ff0, 0x1ff8, 0x1ffc, 0x1ffe, 0x1fff,
1868     0x0000, 0x0000, 0x0000, 0x0000, 0x0800, 0x0c00, 0x0e00, 0x0f00,
1869     0x0f80, 0x0fc0, 0x0fe0, 0x0ff0, 0x0ff8, 0x0ffc, 0x0ffe, 0x0fff,
1870     0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0400, 0x0600, 0x0700,
1871     0x0780, 0x07c0, 0x07e0, 0x07f0, 0x07f8, 0x07fc, 0x07fe, 0x07ff,
1872     0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0200, 0x0300,
1873     0x0380, 0x03c0, 0x03e0, 0x03f0, 0x03f8, 0x03fc, 0x03fe, 0x03ff,
1874     0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0100,
1875     0x0180, 0x01c0, 0x01e0, 0x01f0, 0x01f8, 0x01fc, 0x01fe, 0x01ff,
1876     0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000,
1877     0x0080, 0x00c0, 0x00e0, 0x00f0, 0x00f8, 0x00fc, 0x00fe, 0x00ff,
1878     0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000,
1879     0x0000, 0x0040, 0x0060, 0x0070, 0x0078, 0x007c, 0x007e, 0x007f,
1880     0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000,
1881     0x0000, 0x0000, 0x0020, 0x0030, 0x0038, 0x003c, 0x003e, 0x003f,
1882     0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000,
1883     0x0000, 0x0000, 0x0000, 0x0010, 0x0018, 0x001c, 0x001e, 0x001f,
1884     0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000,
1885     0x0000, 0x0000, 0x0000, 0x0000, 0x0008, 0x000c, 0x000e, 0x000f,
1886     0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000,
1887     0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0004, 0x0006, 0x0007,
1888     0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000,
1889     0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0002, 0x0003,
1890     0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000,
1891     0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0000, 0x0001,
1892 };
1893
1894 static const USHORT *runs_array = runs_array_le;
1895
1896 static void initRunArray(void) {
1897     int iTest=1;
1898     char *pcTest=((char *)(&iTest));
1899
1900     if (*pcTest==1) {
1901         runs_array = runs_array_le;
1902     } else {
1903         runs_array = runs_array_be;
1904     }
1905 }
1906
1907
1908 /*____________________________________________________________________________
1909  |         |                                                                  |
1910  | set_run | Sets a run of pixels to black                                    |
1911  |_________|__________________________________________________________________|
1912  |                                                                            |
1913  | This routine does bounds-checking to avoid setting any pixels outside the  |
1914  | given buffer.                                                              |
1915  |                                                                            |
1916  | Since this is called often, it's written to be as fast as I could make it. |
1917  |____________________________________________________________________________|
1918 */
1919 static void set_run (
1920     BYTE   *buf_p,      /* buffer in which we're to set the run          */
1921     int     start_pos,  /* pixel-index of left side of run               */
1922     int     run_len,    /* # of pixels in the run (non-negative)         */
1923     int     row_len)    /* # of pixels in the buffer                     */
1924 {
1925     /*************************************************************************
1926      *
1927      * PERFORMANCE NOTE
1928      *
1929      * Inlining this routine slows it down a little.
1930      * Seconds to MMR encode+decode 1000 rows of 1728 pixels (bench_fax.c):
1931      *
1932      *    black density:           0%    10%     20%     50%
1933      *    calling this routine:   2.2     7.4    12.8    29.9
1934      *    inlining this routine:  2.2     7.5    13.2    30.6
1935      *
1936      * Inlining this routine *hurt* performance a little because more MMR
1937      * code was kicked out of the cache.
1938      *
1939      *************************************************************************/
1940
1941     int    end_pos;     /* pixel-index of rightmost pixel in run         */
1942     int    start_index; /* byte-index of first byte in run               */
1943     BYTE  *left_p;      /* ptr to byte containing leftmost pixel in run  */
1944     BYTE  *right_p;     /* ptr to byte containing rightmost pixel in run */
1945
1946     end_pos = start_pos + run_len - 1;
1947
1948     if (end_pos >= row_len)
1949         end_pos = row_len - 1;
1950
1951     start_index = start_pos >> 4;
1952
1953     if ((end_pos >> 4) == start_index) {
1954         /* the run is contained within an even-aligned 2-byte word */
1955         ((USHORT*)buf_p)[start_index] |=
1956             runs_array [((start_pos & 15)<<4) | (end_pos & 15)];
1957     } else if (end_pos > start_pos) {
1958         /* the run spans two or more bytes */
1959         left_p  = buf_p + (start_pos >> 3);
1960         right_p = buf_p + (end_pos   >> 3);
1961
1962         *left_p  |= (BYTE )0xFFu >> (UINT)(      start_pos & 7u );
1963         *right_p  = (BYTE )0xFFu << (UINT)(7u - (end_pos   & 7u));
1964         left_p++;
1965
1966         while (left_p < right_p)
1967             *left_p++ = 0xFFu;
1968     }
1969 }
1970
1971
1972 /*****************************************************************************
1973  *                                                                           *
1974  *                          DECODING ROW-DATA                                *
1975  *                                                                           *
1976  *****************************************************************************
1977
1978
1979  Interface into this section:
1980
1981         decode_row_init - inits instance-vars for this section
1982         decode_row_1d   - parses a row of 1-dim data
1983         decode_row_2d   - parses a row of 2-dim data
1984
1985  The parsing routines return these bit-values:
1986
1987         IP_PRODUCED_ROW
1988         IP_INPUT_ERROR
1989         DECODE_HIT_EOL  (defined below, not in the public interface)
1990         DECODE_HIT_FILL (ditto)
1991
1992  A return-value of zero (ie, none of the above bits are set) means that the
1993  routine wants to be called again with more input-bytes.
1994
1995  These routines fetch input by calling BITS_LOAD, so bits_init and
1996  bits_buf_open must have already been called.
1997 */
1998
1999 #define DECODE_HIT_EOL  0x4000u
2000 #define DECODE_HIT_FILL 0x8000u
2001
2002
2003 /*____________________________________________________________________________
2004  |                 |                                                          |
2005  | decode_row_init | inits instance-variables for this section                |
2006  |_________________|__________________________________________________________|
2007 */
2008 static void decode_row_init (DEC_INST *g)
2009 {
2010     g->pixel_pos = 0;
2011     g->white = 0xFFu;  /* start with a white run */
2012     g->state_2d = NORMAL_2D;
2013     g->a0 = -1;  /* pixel before 1st is an imaginary white pixel */
2014     g->got_black = FALSE;   /* haven't gotten any black pixels */
2015 }
2016
2017
2018
2019 /*____________________________________________________________________________
2020  |               |                                                            |
2021  | decode_row_1d | Decodes a row of MH (1-dimensional G3) data                |
2022  |_______________|____________________________________________________________|
2023 */
2024 static UINT decode_row_1d (
2025     DEC_INST *g,             /* in:  pointer to our instance-variables    */
2026     BYTE     *pbPrevOutBuf,  /* in:  prev output row (for error-handling) */
2027     BYTE     *pbOutBuf)      /* out: output buf                           */
2028 {
2029     int           run_len;        /* # pixels in current run */
2030     UINT          white;
2031     int           pixel_pos;
2032     UINT          result;
2033     UINT          ret_val = 0;   /* init to zap a compiler warning */
2034     int           index_length;
2035     const BYTE   *index_tbl_p;
2036     const USHORT *value_tbl_p;
2037
2038     if (g->pixel_pos == 0) {
2039         memset (pbOutBuf, 0, g->bytes_in_row);   /* set whole row to white */
2040         g->ref_row_invalid = TRUE;
2041     }
2042
2043     white = (UINT)(int )(signed char)g->white;  /* must be all 0's or all 1's */
2044     pixel_pos = g->pixel_pos;
2045
2046     while (TRUE) {
2047
2048         if (white) {
2049             index_length = MAX_WHITE_CODELEN;
2050             index_tbl_p = fax_white_huff_index;
2051             value_tbl_p = fax_white_huff;
2052         } else {
2053             index_length = MAX_BLACK_CODELEN;
2054             index_tbl_p = fax_black_huff_index;
2055             value_tbl_p = fax_black_huff;
2056         }
2057
2058         PARSE_CODE (g, index_length, index_tbl_p, value_tbl_p, result, run_len);
2059         PRINT (_T("pc result=%d, len=%d\n"), result, run_len);
2060
2061         if (result == RET_GOT_CODE) {
2062             /* todo: below, we call set_run for EVERY make-up code (slow) */
2063             if (! white) {
2064                 set_run (pbOutBuf, pixel_pos, run_len, g->row_len);
2065                 g->got_black = TRUE;
2066             }
2067
2068             pixel_pos += run_len;
2069             if (run_len <= 63)  /* this is a final run (not a make-up) */
2070                 white = ~white;
2071             continue;   /* go to top of main 'while' loop */
2072         }
2073
2074         switch (result) {    /* handle unusual condition */
2075
2076             case RET_NEED_MORE:
2077                 ret_val = 0;
2078                 goto bail_out;
2079                 break;
2080
2081             case RET_BAD_CODE:
2082                 memcpy (pbOutBuf, pbPrevOutBuf, g->bytes_in_row);
2083                 ret_val = IP_PRODUCED_ROW | IP_INPUT_ERROR;
2084                 goto bail_out;
2085                 break;
2086
2087             case RET_FILL:
2088             case RET_HIT_EOL:
2089                 ret_val = result==RET_FILL ? DECODE_HIT_FILL : DECODE_HIT_EOL;
2090                 if (pixel_pos == 0)
2091                     goto bail_out;
2092                 if (pixel_pos == g->row_len) {
2093                     ret_val |= IP_PRODUCED_ROW;
2094                     g->ref_row_invalid = FALSE;
2095                     goto bail_out;
2096                 }
2097                 memcpy (pbOutBuf, pbPrevOutBuf, g->bytes_in_row);
2098                 ret_val |= IP_PRODUCED_ROW | IP_INPUT_ERROR;
2099                 goto bail_out;
2100                 break;
2101
2102             default:
2103                 assert (FALSE);
2104         } /* end of switch */
2105     } /* end of while */
2106
2107     bail_out:
2108
2109     g->white     = white;
2110     g->pixel_pos = pixel_pos;
2111
2112     return ret_val;
2113 }
2114
2115
2116
2117 /*____________________________________________________________________________
2118  |               |                                                            |
2119  | decode_row_2d | Decodes a row of MR/MMR (2-dimensional) data               |
2120  |_______________|____________________________________________________________|
2121 */
2122 static UINT decode_row_2d (
2123     DEC_INST *g,             /* in:  pointer to our instance-variables */
2124     BYTE     *pbPrevBuf,     /* in:  prev output row ("reference row") */
2125     BYTE     *pbOutBuf)      /* out: output buffer                     */
2126 {
2127     UINT  group4;
2128     int   iAction;
2129     UINT  white;
2130     UINT  result = 0;   /* the 0 eliminates a compiler warning */
2131     int   row_len;
2132     int   run_len;
2133     int   a0, a1;
2134     int   b1=0, b2;     /* the 0 eliminates a compiler warning */
2135     UINT  need_b0;
2136     UINT  ret_val = 0;  /* the 0 eliminates a compiler warning */
2137
2138     group4 = (g->input_format == IP_FAX_MMR);
2139     row_len = g->row_len;
2140     white = (UINT)(int)(signed char)g->white;  /* must be all 0's or all 1's so sign extend */
2141     a0 = g->a0;
2142
2143     if (a0 < 0) {
2144         memset (pbOutBuf, 0, g->bytes_in_row);   /* set whole row to white */
2145         pbPrevBuf[g->bytes_in_row] = 0x55u;   /* scan_to requires this */
2146     }
2147
2148     while (TRUE) {
2149
2150           /****************************************/
2151          /* Process a usual code -- normal state */
2152         /****************************************/
2153
2154         need_b0 = TRUE;
2155
2156         while (g->state_2d == NORMAL_2D) {
2157
2158             if (a0>=row_len && group4) {
2159                 /* ret_val = IP_PRODUCED_ROW; goto bail_out;
2160                  * todo: undelete the line above? */
2161                 if (a0 == row_len) ret_val = IP_PRODUCED_ROW;
2162                 else               ret_val = IP_INPUT_ERROR;
2163                 goto bail_out;
2164             }
2165
2166             PARSE_CODE (g, MAX_VERT_CODELEN, fax_vert_huff_index,
2167                         fax_vert_huff, result, iAction);
2168             if (result != RET_GOT_CODE)
2169                 goto unusual_condition;
2170
2171             if (iAction == HORIZ_MODE) {
2172                 g->state_2d = HORIZ_1ST;
2173                 break;
2174             }
2175
2176             if (a0 < 0) {
2177                 a0 = 0;
2178                 b1 = -1;   /* a kludge so scan below will start at pixel 0 */
2179             } else if (need_b0)
2180                 b1 = scan_to (white, pbPrevBuf, a0, row_len);
2181
2182             b1 = scan_to (~white, pbPrevBuf, b1+1, row_len);
2183
2184             if (iAction <= LAST_VERT) {   /* vertical mode */
2185                 iAction -= 3;
2186                 a1 = b1 + iAction;
2187                 need_b0 = (iAction<-1 || iAction>0);
2188                 if (! white) {
2189                     set_run (pbOutBuf, a0, a1-a0, row_len);
2190                     g->got_black = TRUE;
2191                 }
2192                 if (a1<a0 || a1>row_len) goto corrupt;
2193                 a0 = a1;
2194                 white = ~white;
2195             } else {     /* pass mode */
2196                 b2 = scan_to (white, pbPrevBuf, b1+1, row_len);
2197                 if (! white) {
2198                     set_run (pbOutBuf, a0, b2-a0, row_len);
2199                     g->got_black = TRUE;
2200                 }
2201                 need_b0 = FALSE;
2202                 a0 = b2;
2203                 b1 = b2;
2204             }
2205         } /* while NORMAL_2D */
2206
2207           /*******************************************/
2208          /* Process a usual code -- horizontal mode */
2209         /*******************************************/
2210
2211         while (TRUE) {   /* HORIZ_1ST or HORIZ_2ND */
2212             int           index_length;
2213             const BYTE   *index_tbl_p;
2214             const USHORT *value_tbl_p;
2215
2216             do {
2217                 if (white) {
2218                     index_length = MAX_WHITE_CODELEN;
2219                     index_tbl_p = fax_white_huff_index;
2220                     value_tbl_p = fax_white_huff;
2221                 } else {
2222                     index_length = MAX_BLACK_CODELEN;
2223                     index_tbl_p = fax_black_huff_index;
2224                     value_tbl_p = fax_black_huff;
2225                 }
2226
2227                 PARSE_CODE (g, index_length, index_tbl_p, value_tbl_p,
2228                             result, run_len);
2229
2230                 if (result != RET_GOT_CODE)
2231                     goto unusual_condition;
2232                 if (a0 < 0)  /* Exception:  See Fascicle VII.3, */
2233                     a0 = 0;  /*   rec T.4, section 4.2.1.3.4 */
2234                 /* todo: below, we call set_run for EVERY make-up code (slow) */
2235                 if (! white) {
2236                     set_run (pbOutBuf, a0, run_len, row_len);
2237                     g->got_black = TRUE;
2238                 }
2239                 a0 += run_len;
2240             } while (run_len > 63);
2241
2242             white = ~white;
2243             if (g->state_2d == HORIZ_1ST)
2244                 g->state_2d = HORIZ_2ND;
2245             else {
2246                 g->state_2d = NORMAL_2D;
2247                 if (a0 > row_len) goto corrupt;
2248                 break;   /* exit while */
2249             }
2250         }
2251
2252         continue;   /* no unusual condition, so resume main while loop */
2253
2254           /*****************************/
2255          /* Handle unusual conditions */
2256         /*****************************/
2257
2258         corrupt:
2259             result = RET_BAD_CODE;
2260
2261         unusual_condition:
2262
2263         switch (result) {
2264
2265             case RET_GOT_CODE:
2266                 /* normal case: was handled in the block of code above */
2267                 break;
2268
2269             case RET_NEED_MORE:
2270                 ret_val = 0;
2271                 goto bail_out;
2272                 break;
2273
2274             case RET_BAD_CODE:
2275                 g->state_2d = NORMAL_2D;
2276                 memcpy (pbOutBuf, pbPrevBuf, g->bytes_in_row);
2277                 ret_val = IP_PRODUCED_ROW | IP_INPUT_ERROR;
2278                 g->ref_row_invalid = TRUE;
2279                 goto bail_out;
2280                 break;
2281
2282             case RET_FILL:
2283             case RET_HIT_EOL:
2284                 ret_val = result==RET_FILL ? DECODE_HIT_FILL : DECODE_HIT_EOL;
2285                 g->state_2d = NORMAL_2D;
2286
2287                 if (group4) {
2288                     /* We should only hit EOL when no row-data is present */
2289                     /* todo:  Always report error if fill-zeroes were seen? */
2290                     if (a0 >= 0)
2291                         ret_val |= IP_INPUT_ERROR;
2292                 } else {
2293                     if (!g->ref_row_invalid && a0==row_len)
2294                         ret_val |= IP_PRODUCED_ROW;
2295                     else if (a0 >= 0) {
2296                         memcpy (pbOutBuf, pbPrevBuf, g->bytes_in_row);
2297                         ret_val |= IP_PRODUCED_ROW | IP_INPUT_ERROR;
2298                         g->ref_row_invalid = TRUE;
2299                     }
2300                 }
2301                 goto bail_out;
2302                 break;
2303
2304             default:
2305                 assert (FALSE);
2306
2307         } /* end of switch to handle unusual condition */
2308     } /* end of while */
2309
2310     bail_out:
2311
2312     /* save variables needed in next call */
2313     g->a0 = a0;
2314     g->white = white;
2315
2316     return ret_val;
2317 }
2318
2319
2320
2321 /*****************************************************************************\
2322  *
2323  * faxDecode_openXform - Creates a new instance of the transformer
2324  *
2325  *****************************************************************************
2326  *
2327  * This returns a handle for the new instance to be passed into
2328  * all subsequent calls.
2329  *
2330  * Return value: IP_DONE=success; IP_FATAL_ERROR=misc error.
2331  *
2332 \*****************************************************************************/
2333
2334 static WORD faxDecode_openXform (
2335     IP_XFORM_HANDLE *pXform)   /* out: returned handle */
2336 {
2337     PDEC_INST g;
2338
2339     initRunArray();
2340     INSURE (pXform != NULL);
2341     IP_MEM_ALLOC (sizeof(DEC_INST), g);
2342     *pXform = g;
2343     memset (g, 0, sizeof(DEC_INST));
2344     g->dwValidChk = CHECK_VALUE;
2345
2346     bits_init (g);
2347     decode_row_init (g);
2348     return IP_DONE;
2349
2350     fatal_error:
2351     return IP_FATAL_ERROR;
2352 }
2353
2354
2355
2356 /*****************************************************************************\
2357  *
2358  * faxDecode_setDefaultInputTraits - Specifies default input image traits
2359  *
2360  *****************************************************************************
2361  *
2362  * The header of the file-type handled by the transform probably does
2363  * not include *all* the image traits we'd like to know.  Those not
2364  * specified in the file-header are filled in from info provided by
2365  * this routine.
2366  *
2367  * Return value: IP_DONE=success; IP_FATAL_ERROR=misc error.
2368  *
2369 \*****************************************************************************/
2370
2371 static WORD faxDecode_setDefaultInputTraits (
2372     IP_XFORM_HANDLE  hXform,     /* in: handle for xform */
2373     PIP_IMAGE_TRAITS pTraits)    /* in: default image traits */
2374 {
2375     PDEC_INST g;
2376
2377     HANDLE_TO_PTR (hXform, g);
2378
2379     /* Insure that values we actually use or care about are known */
2380     INSURE (pTraits->iPixelsPerRow > 0);   /* we need the row-length */
2381     INSURE (pTraits->iBitsPerPixel == 1);  /* image must be bi-level */
2382
2383     g->traits = *pTraits;   /* a structure copy */
2384
2385     return IP_DONE;
2386
2387     fatal_error:
2388     return IP_FATAL_ERROR;
2389 }
2390
2391
2392
2393 /*****************************************************************************\
2394  *
2395  * faxDecode_setXformSpec - Provides xform-specific information
2396  *
2397 \*****************************************************************************/
2398
2399 static WORD faxDecode_setXformSpec (
2400     IP_XFORM_HANDLE  hXform,         /* in: handle for xform */
2401     DWORD_OR_PVOID   aXformInfo[])   /* in: xform information */
2402 {
2403     PDEC_INST g;
2404
2405     HANDLE_TO_PTR (hXform, g);
2406     g->input_format = (BYTE)aXformInfo[IP_FAX_FORMAT].dword;
2407     g->no_eols      = (BOOL)aXformInfo[IP_FAX_NO_EOLS].dword;
2408     return IP_DONE;
2409
2410     fatal_error:
2411     return IP_FATAL_ERROR;
2412 }
2413
2414
2415
2416 /*****************************************************************************\
2417  *
2418  * faxDecode_getHeaderBufSize- Returns size of input buf needed to hold header
2419  *
2420 \*****************************************************************************/
2421
2422 static WORD faxDecode_getHeaderBufSize (
2423     IP_XFORM_HANDLE  hXform,         /* in:  handle for xform */
2424     DWORD           *pdwInBufLen)    /* out: buf size for parsing header */
2425 {
2426     /* since input is raw pixels, there is no header, so set it to zero */
2427     *pdwInBufLen = 0;
2428     return IP_DONE;
2429 }
2430
2431
2432
2433 /*****************************************************************************\
2434  *
2435  * faxDecode_getActualTraits - Parses header, and returns input & output traits
2436  *
2437  *****************************************************************************
2438  *
2439  * There is no header, so this routine merely computes some stuff
2440  *
2441 \*****************************************************************************/
2442
2443 static WORD faxDecode_getActualTraits (
2444     IP_XFORM_HANDLE  hXform,         /* in:  handle for xform */
2445     DWORD            dwInputAvail,   /* in:  # avail bytes in input buf */
2446     PBYTE            pbInputBuf,     /* in:  ptr to input buffer */
2447     PDWORD           pdwInputUsed,   /* out: # bytes used from input buf */
2448     PDWORD           pdwInputNextPos,/* out: file-pos to read from next */
2449     PIP_IMAGE_TRAITS pInTraits,      /* out: input image traits */
2450     PIP_IMAGE_TRAITS pOutTraits)     /* out: output image traits */
2451 {
2452     PDEC_INST g;
2453     int       inBytes;
2454
2455     HANDLE_TO_PTR (hXform, g);
2456
2457     /* Since there is no header, we'll report no usage of input */
2458
2459     *pdwInputUsed    = 0;
2460     *pdwInputNextPos = 0;
2461
2462     /* Since we don't change traits, just copy out the default traits */
2463
2464     *pInTraits  = g->traits;
2465     *pOutTraits = g->traits;
2466
2467     /* Compute some stuff */
2468
2469     g->row_len      = g->traits.iPixelsPerRow;   /* todo: zap redundant var */
2470     g->bytes_in_row = inBytes = (g->row_len+7) / 8;
2471     g->two_dim      = (g->input_format == IP_FAX_MMR);
2472
2473     /* For MH and MR:  Discard bits before the first EOL */
2474     g->flushing_to_eol = ! g->two_dim;
2475
2476     /* allocate the prior-row buffer */
2477
2478     if (g->prior_p != NULL)
2479         IP_MEM_FREE (g->prior_p);
2480     IP_MEM_ALLOC (inBytes, g->prior_p);
2481     memset (g->prior_p, 0, inBytes);
2482
2483     return IP_DONE | IP_READY_FOR_DATA;
2484
2485     fatal_error:
2486     return IP_FATAL_ERROR;
2487 }
2488
2489
2490
2491 /****************************************************************************\
2492  *
2493  * faxDecode_getActualBufSizes - Returns buf sizes needed for remainder of job
2494  *
2495 \****************************************************************************/
2496
2497 static WORD faxDecode_getActualBufSizes (
2498     IP_XFORM_HANDLE  hXform,           /* in:  handle for xform */
2499     PDWORD           pdwMinInBufLen,   /* out: min input buf size */
2500     PDWORD           pdwMinOutBufLen)  /* out: min output buf size */
2501 {
2502     PDEC_INST g;
2503
2504     HANDLE_TO_PTR (hXform, g);
2505     *pdwMinInBufLen  = 1;
2506     *pdwMinOutBufLen = g->bytes_in_row;
2507     return IP_DONE;
2508
2509     fatal_error:
2510     return IP_FATAL_ERROR;
2511 }
2512
2513
2514
2515 /*****************************************************************************\
2516  *
2517  * faxDecode_convert - the work-horse routine
2518  *
2519 \*****************************************************************************/
2520
2521 static WORD faxDecode_convert (
2522     IP_XFORM_HANDLE hXform,
2523     DWORD           dwInputAvail,     /* in:  # avail bytes in in-buf */
2524     PBYTE           pbInputBuf,       /* in:  ptr to in-buffer */
2525     PDWORD          pdwInputUsed,     /* out: # bytes used from in-buf */
2526     PDWORD          pdwInputNextPos,  /* out: file-pos to read from next */
2527     DWORD           dwOutputAvail,    /* in:  # avail bytes in out-buf */
2528     PBYTE           pbOutputBuf,      /* in:  ptr to out-buffer */
2529     PDWORD          pdwOutputUsed,    /* out: # bytes written in out-buf */
2530     PDWORD          pdwOutputThisPos) /* out: file-pos to write the data */
2531 {
2532     PDEC_INST g;
2533     UINT      bit;
2534     UINT      ret_val;   /* return-value of this function */
2535
2536     HANDLE_TO_PTR (hXform, g);
2537
2538     *pdwOutputUsed = 0;
2539
2540     if (dwInputAvail==0 && BITS_IN_CACHE(g)<MAX_CODE_LEN) {
2541         /* We're being told to flush; indicate we're done. */
2542         /* Our only buffer is the cache */
2543         *pdwInputUsed     = 0;
2544         *pdwInputNextPos  = g->dwInNextPos;
2545         *pdwOutputThisPos = g->dwOutNextPos;
2546         return IP_DONE;
2547     }
2548
2549     if (g->toss_everything) {
2550         *pdwInputUsed     = dwInputAvail;
2551         *pdwInputNextPos  = g->dwInNextPos = g->dwInNextPos + dwInputAvail;
2552         *pdwOutputThisPos = g->dwOutNextPos;
2553         return IP_READY_FOR_DATA;
2554     }
2555
2556     bits_buf_open (g, pbInputBuf, dwInputAvail);
2557
2558     if (g->flushing_to_eol) {
2559         ret_val = bits_flush_to_eol(g, g->got_fill,
2560                                     (BOOL)(g->input_format==IP_FAX_MR))
2561                   ? DECODE_HIT_EOL : 0;
2562     } else {
2563         if (g->two_dim) ret_val = decode_row_2d(g, g->prior_p, pbOutputBuf);
2564         else            ret_val = decode_row_1d(g, g->prior_p, pbOutputBuf);
2565         PRINT (_T("decoder returned %x\n"), ret_val, 0);
2566     }
2567
2568     if (ret_val & IP_INPUT_ERROR) {
2569         if (g->input_format == IP_FAX_MMR) {
2570             bits_flush (g);
2571             g->toss_everything = TRUE;
2572             /* This isn't fatal any more. We merely toss all following data */
2573             /* ret_val |= IP_INPUT_ERROR; */
2574         } else {
2575             g->flushing_to_eol = TRUE;
2576             g->num_eols = 0;
2577         }
2578     }
2579
2580     if (ret_val & IP_PRODUCED_ROW) {
2581         if (g->got_black) ret_val |= NONWHITE_ROW | IP_CONSUMED_ROW;
2582         else              ret_val |= WHITE_ROW    | IP_CONSUMED_ROW;
2583         *pdwOutputUsed = g->bytes_in_row;
2584         memcpy (g->prior_p, pbOutputBuf, g->bytes_in_row);
2585         decode_row_init (g);
2586         g->num_eols = 0;   /* ignore all EOLs before the row */
2587     }
2588
2589     if (ret_val & DECODE_HIT_FILL) {
2590         g->flushing_to_eol = TRUE;
2591         g->got_fill = TRUE;
2592     }
2593
2594     if (ret_val & DECODE_HIT_EOL) {
2595         if (g->input_format == IP_FAX_MR) {
2596             /* read the tag-bit for 1-dim/2-dim */
2597             BITS_LOAD (g, 1, bit)
2598             g->two_dim = (bit == 0);
2599             BITS_ADVANCE (g, 1)
2600         }
2601
2602         decode_row_init (g);
2603         g->flushing_to_eol = FALSE;
2604         g->got_fill = FALSE;
2605         g->num_eols += 1;
2606
2607         if (g->num_eols>=EOLS_FOR_MH_MR ||
2608             (g->input_format==IP_FAX_MMR && g->num_eols>=EOLS_FOR_MMR)) {
2609             /* WE HIT END OF PAGE */
2610             g->num_eols = 0;
2611             bits_flush (g);
2612             ret_val |= IP_NEW_OUTPUT_PAGE;
2613         }
2614     }
2615
2616     *pdwInputUsed     = bits_buf_close (g);
2617     g->dwInNextPos   += *pdwInputUsed;
2618     *pdwInputNextPos  = g->dwInNextPos;
2619
2620     *pdwOutputUsed    = (ret_val & IP_PRODUCED_ROW) ? g->bytes_in_row : 0;
2621     *pdwOutputThisPos = g->dwOutNextPos;
2622     g->dwOutNextPos  += *pdwOutputUsed;
2623
2624 #if 0
2625     {
2626         int i;
2627         for (i=0; i<*pdwInputUsed; i++)
2628             PRINT (_T("%02x  "), pbInputBuf[i], 0);
2629     }
2630 #endif
2631
2632     return (ret_val | IP_READY_FOR_DATA)
2633             & (IP_CONSUMED_ROW | IP_PRODUCED_ROW | IP_READY_FOR_DATA |
2634                /* NONWHITE_ROW | WHITE_ROW | */
2635                IP_NEW_OUTPUT_PAGE |
2636                IP_INPUT_ERROR | IP_FATAL_ERROR);
2637
2638     fatal_error:
2639     return IP_FATAL_ERROR;
2640 }
2641
2642
2643
2644 /*****************************************************************************\
2645  *
2646  * faxDecode_insertedData - client inserted into our output stream
2647  *
2648 \*****************************************************************************/
2649
2650 static WORD faxDecode_insertedData (
2651     IP_XFORM_HANDLE hXform,
2652     DWORD           dwNumBytes)
2653 {
2654     fatalBreakPoint ();
2655     return IP_FATAL_ERROR;   /* must never be called (can't insert data) */
2656 }
2657
2658
2659
2660 /*****************************************************************************\
2661  *
2662  * faxDecode_newPage - Tells us to flush this page, and start a new page
2663  *
2664 \*****************************************************************************/
2665
2666 static WORD faxDecode_newPage (
2667     IP_XFORM_HANDLE hXform)
2668 {
2669     PDEC_INST g;
2670
2671     HANDLE_TO_PTR (hXform, g);
2672     /* todo: flush bits until we see a page boundary */
2673     return IP_DONE;
2674
2675     fatal_error:
2676     return IP_FATAL_ERROR;
2677
2678 }
2679
2680
2681
2682 /*****************************************************************************\
2683  *
2684  * faxDecode_closeXform - Destroys this instance
2685  *
2686 \*****************************************************************************/
2687
2688 static WORD faxDecode_closeXform (IP_XFORM_HANDLE hXform)
2689 {
2690     PDEC_INST g;
2691
2692     HANDLE_TO_PTR (hXform, g);
2693
2694     if (g->prior_p != NULL)
2695         IP_MEM_FREE (g->prior_p);
2696
2697     g->dwValidChk = 0;
2698     IP_MEM_FREE (g);       /* free memory for the instance */
2699     return IP_DONE;
2700
2701     fatal_error:
2702     return IP_FATAL_ERROR;
2703 }
2704
2705
2706
2707 /*****************************************************************************\
2708  *
2709  * faxDecodeTbl - Jump-table for Decoder
2710  *
2711 \*****************************************************************************/
2712
2713 IP_XFORM_TBL faxDecodeTbl = {
2714     faxDecode_openXform,
2715     faxDecode_setDefaultInputTraits,
2716     faxDecode_setXformSpec,
2717     faxDecode_getHeaderBufSize,
2718     faxDecode_getActualTraits,
2719     faxDecode_getActualBufSizes,
2720     faxDecode_convert,
2721     faxDecode_newPage,
2722     faxDecode_insertedData,
2723     faxDecode_closeXform
2724 };
2725
2726
2727
2728
2729 /*
2730 @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
2731 @                                                                            @
2732 @                  T A B L E S   F O R   D E C O D E R                       @
2733 @                                                                            @
2734 @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
2735 */
2736
2737
2738
2739 const USHORT fax_white_huff[105] = {  0,
2740     0x4002, 0x4003, 0x4004, 0x4005, 0x4006, 0x4007, 0x500a, 0x500b,
2741     0x5080, 0x5008, 0x5009, 0x5040, 0x600d, 0x6001, 0x600c, 0x60c0,
2742     0x6680, 0x6010, 0x6011, 0x600e, 0x600f, 0x7016, 0x7017, 0x7014,
2743     0x7013, 0x701a, 0x7015, 0x701c, 0x701b, 0x7012, 0x7018, 0x7019,
2744     0x7100, 0x801d, 0x801e, 0x802d, 0x802e, 0x802f, 0x8030, 0x8021,
2745     0x8022, 0x8023, 0x8024, 0x8025, 0x8026, 0x801f, 0x8020, 0x8035,
2746     0x8036, 0x8027, 0x8028, 0x8029, 0x802a, 0x802b, 0x802c, 0x803d,
2747     0x803e, 0x803f, 0x8000, 0x8140, 0x8180, 0x803b, 0x803c, 0x8031,
2748     0x8032, 0x8033, 0x8034, 0x8037, 0x8038, 0x8039, 0x803a, 0x81c0,
2749     0x8200, 0x8280, 0x8240, 0x95c0, 0x9600, 0x9640, 0x96c0, 0x92c0,
2750     0x9300, 0x9340, 0x9380, 0x93c0, 0x9400, 0x9440, 0x9480, 0x94c0,
2751     0x9500, 0x9540, 0x9580, 0xb700, 0xb740, 0xb780, 0xc7c0, 0xc800,
2752     0xc840, 0xc880, 0xc8c0, 0xc900, 0xc940, 0xc980, 0xc9c0, 0xca00,
2753 };
2754
2755
2756 const BYTE fax_white_huff_index[4096] = {
2757      0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,
2758     92, 92, 95, 96, 97, 98, 99, 100, 93, 93, 94, 94, 101, 102, 103, 104,
2759     34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34, 34,
2760     35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35, 35,
2761     36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36, 36,
2762     37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37, 37,
2763     22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
2764     22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22, 22,
2765     23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
2766     23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23, 23,
2767     38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38, 38,
2768     39, 39, 39, 39, 39, 39, 39, 39, 39, 39, 39, 39, 39, 39, 39, 39,
2769     13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13,
2770     13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13,
2771     13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13,
2772     13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13,
2773     24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
2774     24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24, 24,
2775     40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40, 40,
2776     41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41, 41,
2777     42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42, 42,
2778     43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43, 43,
2779     44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44, 44,
2780     45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45, 45,
2781     25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
2782     25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25, 25,
2783     46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46, 46,
2784     47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47, 47,
2785     14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
2786     14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
2787     14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
2788     14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
2789     15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
2790     15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
2791     15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
2792     15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
2793     48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48, 48,
2794     49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49, 49,
2795     26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
2796     26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26, 26,
2797     50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50, 50,
2798     51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51, 51,
2799     52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52, 52,
2800     53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53, 53,
2801     54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54, 54,
2802     55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55, 55,
2803     27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
2804     27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27,
2805     28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
2806     28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28, 28,
2807     56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56, 56,
2808     57, 57, 57, 57, 57, 57, 57, 57, 57, 57, 57, 57, 57, 57, 57, 57,
2809     58, 58, 58, 58, 58, 58, 58, 58, 58, 58, 58, 58, 58, 58, 58, 58,
2810     59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59, 59,
2811     60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60, 60,
2812     61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61, 61,
2813      7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,
2814      7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,
2815      7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,
2816      7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,
2817      7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,
2818      7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,
2819      7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,
2820      7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,
2821      8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,
2822      8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,
2823      8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,
2824      8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,
2825      8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,
2826      8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,
2827      8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,
2828      8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,
2829     29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
2830     29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29, 29,
2831     62, 62, 62, 62, 62, 62, 62, 62, 62, 62, 62, 62, 62, 62, 62, 62,
2832     63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63, 63,
2833     76, 76, 76, 76, 76, 76, 76, 76, 77, 77, 77, 77, 77, 77, 77, 77,
2834     78, 78, 78, 78, 78, 78, 78, 78, 79, 79, 79, 79, 79, 79, 79, 79,
2835     30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30,
2836     30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30, 30,
2837     31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31,
2838     31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31, 31,
2839     64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64, 64,
2840     65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65, 65,
2841     66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66,
2842     67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67, 67,
2843     32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32,
2844     32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32, 32,
2845     68, 68, 68, 68, 68, 68, 68, 68, 68, 68, 68, 68, 68, 68, 68, 68,
2846     69, 69, 69, 69, 69, 69, 69, 69, 69, 69, 69, 69, 69, 69, 69, 69,
2847     70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70, 70,
2848     71, 71, 71, 71, 71, 71, 71, 71, 71, 71, 71, 71, 71, 71, 71, 71,
2849     16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,
2850     16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,
2851     16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,
2852     16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16, 16,
2853     17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17,
2854     17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17,
2855     17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17,
2856     17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17, 17,
2857     72, 72, 72, 72, 72, 72, 72, 72, 72, 72, 72, 72, 72, 72, 72, 72,
2858     73, 73, 73, 73, 73, 73, 73, 73, 73, 73, 73, 73, 73, 73, 73, 73,
2859     80, 80, 80, 80, 80, 80, 80, 80, 81, 81, 81, 81, 81, 81, 81, 81,
2860     74, 74, 74, 74, 74, 74, 74, 74, 74, 74, 74, 74, 74, 74, 74, 74,
2861     75, 75, 75, 75, 75, 75, 75, 75, 75, 75, 75, 75, 75, 75, 75, 75,
2862     82, 82, 82, 82, 82, 82, 82, 82, 83, 83, 83, 83, 83, 83, 83, 83,
2863     84, 84, 84, 84, 84, 84, 84, 84, 85, 85, 85, 85, 85, 85, 85, 85,
2864     86, 86, 86, 86, 86, 86, 86, 86, 87, 87, 87, 87, 87, 87, 87, 87,
2865     88, 88, 88, 88, 88, 88, 88, 88, 89, 89, 89, 89, 89, 89, 89, 89,
2866     90, 90, 90, 90, 90, 90, 90, 90, 91, 91, 91, 91, 91, 91, 91, 91,
2867     33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33,
2868     33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33, 33,
2869      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
2870      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
2871      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
2872      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
2873      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
2874      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
2875      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
2876      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
2877      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
2878      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
2879      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
2880      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
2881      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
2882      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
2883      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
2884      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
2885      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
2886      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
2887      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
2888      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
2889      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
2890      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
2891      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
2892      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
2893      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
2894      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
2895      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
2896      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
2897      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
2898      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
2899      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
2900      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
2901      9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,
2902      9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,
2903      9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,
2904      9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,
2905      9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,
2906      9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,
2907      9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,
2908      9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,
2909     10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
2910     10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
2911     10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
2912     10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
2913     10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
2914     10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
2915     10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
2916     10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
2917     11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11,
2918     11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11,
2919     11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11,
2920     11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11,
2921     11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11,
2922     11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11,
2923     11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11,
2924     11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11,
2925     18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
2926     18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
2927     18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
2928     18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18, 18,
2929     19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
2930     19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
2931     19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
2932     19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19, 19,
2933      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
2934      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
2935      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
2936      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
2937      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
2938      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
2939      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
2940      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
2941      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
2942      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
2943      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
2944      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
2945      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
2946      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
2947      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
2948      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
2949      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
2950      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
2951      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
2952      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
2953      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
2954      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
2955      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
2956      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
2957      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
2958      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
2959      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
2960      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
2961      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
2962      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
2963      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
2964      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
2965     20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20,
2966     20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20,
2967     20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20,
2968     20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20, 20,
2969     21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21,
2970     21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21,
2971     21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21,
2972     21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21, 21,
2973     12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
2974     12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
2975     12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
2976     12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
2977     12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
2978     12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
2979     12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
2980     12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
2981      5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,
2982      5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,
2983      5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,
2984      5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,
2985      5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,
2986      5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,
2987      5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,
2988      5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,
2989      5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,
2990      5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,
2991      5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,
2992      5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,
2993      5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,
2994      5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,
2995      5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,
2996      5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,
2997      6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,
2998      6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,
2999      6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,
3000      6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,
3001      6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,
3002      6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,
3003      6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,
3004      6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,
3005      6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,
3006      6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,
3007      6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,
3008      6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,
3009      6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,
3010      6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,
3011      6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,
3012      6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,
3013 };
3014
3015
3016 const USHORT fax_black_huff[105] = {  0,
3017     0x2003, 0x2002, 0x3001, 0x3004, 0x4006, 0x4005, 0x5007, 0x6009,
3018     0x6008, 0x700a, 0x700b, 0x700c, 0x800d, 0x800e, 0x900f, 0xa012,
3019     0xa040, 0xa010, 0xa011, 0xa000, 0xb700, 0xb740, 0xb780, 0xb018,
3020     0xb019, 0xb017, 0xb016, 0xb013, 0xb014, 0xb015, 0xc7c0, 0xc800,
3021     0xc840, 0xc880, 0xc8c0, 0xc900, 0xc940, 0xc980, 0xc9c0, 0xca00,
3022     0xc034, 0xc037, 0xc038, 0xc03b, 0xc03c, 0xc140, 0xc180, 0xc1c0,
3023     0xc035, 0xc036, 0xc032, 0xc033, 0xc02c, 0xc02d, 0xc02e, 0xc02f,
3024     0xc039, 0xc03a, 0xc03d, 0xc100, 0xc030, 0xc031, 0xc03e, 0xc03f,
3025     0xc01e, 0xc01f, 0xc020, 0xc021, 0xc028, 0xc029, 0xc080, 0xc0c0,
3026     0xc01a, 0xc01b, 0xc01c, 0xc01d, 0xc022, 0xc023, 0xc024, 0xc025,
3027     0xc026, 0xc027, 0xc02a, 0xc02b, 0xd280, 0xd2c0, 0xd300, 0xd340,
3028     0xd500, 0xd540, 0xd580, 0xd5c0, 0xd600, 0xd640, 0xd680, 0xd6c0,
3029     0xd200, 0xd240, 0xd380, 0xd3c0, 0xd400, 0xd440, 0xd480, 0xd4c0,
3030 };
3031
3032
3033 const BYTE fax_black_huff_index[8192] = {
3034      0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,
3035      0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,  0,
3036     21, 21, 21, 21, 31, 31, 32, 32, 33, 33, 34, 34, 35, 35, 36, 36,
3037     22, 22, 22, 22, 23, 23, 23, 23, 37, 37, 38, 38, 39, 39, 40, 40,
3038     16, 16, 16, 16, 16, 16, 16, 16, 41, 41, 85, 86, 87, 88, 42, 42,
3039     43, 43, 89, 90, 91, 92, 44, 44, 45, 45, 93, 94, 24, 24, 24, 24,
3040     25, 25, 25, 25, 95, 96, 46, 46, 47, 47, 48, 48, 97, 98, 49, 49,
3041     50, 50, 99, 100, 101, 102, 103, 104, 17, 17, 17, 17, 17, 17, 17, 17,
3042     13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13,
3043     13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13, 13,
3044     26, 26, 26, 26, 51, 51, 52, 52, 53, 53, 54, 54, 55, 55, 56, 56,
3045     57, 57, 58, 58, 59, 59, 60, 60, 18, 18, 18, 18, 18, 18, 18, 18,
3046     19, 19, 19, 19, 19, 19, 19, 19, 61, 61, 62, 62, 63, 63, 64, 64,
3047     65, 65, 66, 66, 67, 67, 68, 68, 69, 69, 70, 70, 27, 27, 27, 27,
3048     14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
3049     14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14, 14,
3050     10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
3051     10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
3052     10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
3053     10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
3054     11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11,
3055     11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11,
3056     11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11,
3057     11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11, 11,
3058     15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15, 15,
3059     71, 71, 72, 72, 73, 73, 74, 74, 75, 75, 76, 76, 28, 28, 28, 28,
3060     29, 29, 29, 29, 77, 77, 78, 78, 79, 79, 80, 80, 81, 81, 82, 82,
3061     30, 30, 30, 30, 83, 83, 84, 84, 20, 20, 20, 20, 20, 20, 20, 20,
3062     12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
3063     12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
3064     12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
3065     12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
3066      8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,
3067      8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,
3068      8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,
3069      8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,
3070      8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,
3071      8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,
3072      8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,
3073      8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,  8,
3074      9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,
3075      9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,
3076      9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,
3077      9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,
3078      9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,
3079      9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,
3080      9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,
3081      9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,  9,
3082      7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,
3083      7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,
3084      7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,
3085      7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,
3086      7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,
3087      7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,
3088      7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,
3089      7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,
3090      7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,
3091      7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,
3092      7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,
3093      7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,
3094      7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,
3095      7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,
3096      7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,
3097      7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,  7,
3098      5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,
3099      5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,
3100      5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,
3101      5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,
3102      5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,
3103      5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,
3104      5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,
3105      5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,
3106      5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,
3107      5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,
3108      5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,
3109      5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,
3110      5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,
3111      5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,
3112      5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,
3113      5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,
3114      5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,
3115      5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,
3116      5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,
3117      5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,
3118      5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,
3119      5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,
3120      5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,
3121      5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,
3122      5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,
3123      5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,
3124      5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,
3125      5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,
3126      5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,
3127      5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,
3128      5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,
3129      5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,  5,
3130      6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,
3131      6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,
3132      6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,
3133      6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,
3134      6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,
3135      6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,
3136      6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,
3137      6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,
3138      6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,
3139      6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,
3140      6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,
3141      6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,
3142      6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,
3143      6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,
3144      6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,
3145      6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,
3146      6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,
3147      6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,
3148      6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,
3149      6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,
3150      6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,
3151      6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,
3152      6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,
3153      6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,
3154      6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,
3155      6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,
3156      6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,
3157      6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,
3158      6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,
3159      6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,
3160      6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,
3161      6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,  6,
3162      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
3163      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
3164      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
3165      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
3166      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
3167      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
3168      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
3169      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
3170      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
3171      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
3172      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
3173      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
3174      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
3175      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
3176      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
3177      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
3178      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
3179      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
3180      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
3181      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
3182      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
3183      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
3184      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
3185      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
3186      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
3187      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
3188      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
3189      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
3190      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
3191      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
3192      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
3193      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
3194      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
3195      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
3196      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
3197      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
3198      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
3199      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
3200      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
3201      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
3202      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
3203      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
3204      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
3205      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
3206      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
3207      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
3208      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
3209      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
3210      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
3211      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
3212      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
3213      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
3214      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
3215      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
3216      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
3217      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
3218      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
3219      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
3220      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
3221      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
3222      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
3223      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
3224      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
3225      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
3226      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
3227      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
3228      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
3229      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
3230      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
3231      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
3232      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
3233      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
3234      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
3235      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
3236      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
3237      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
3238      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
3239      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
3240      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
3241      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
3242      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
3243      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
3244      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
3245      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
3246      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
3247      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
3248      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
3249      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
3250      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
3251      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
3252      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
3253      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
3254      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
3255      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
3256      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
3257      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
3258      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
3259      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
3260      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
3261      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
3262      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
3263      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
3264      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
3265      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
3266      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
3267      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
3268      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
3269      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
3270      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
3271      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
3272      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
3273      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
3274      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
3275      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
3276      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
3277      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
3278      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
3279      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
3280      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
3281      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
3282      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
3283      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
3284      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
3285      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
3286      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
3287      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
3288      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
3289      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
3290      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3291      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3292      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3293      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3294      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3295      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3296      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3297      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3298      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3299      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3300      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3301      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3302      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3303      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3304      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3305      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3306      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3307      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3308      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3309      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3310      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3311      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3312      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3313      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3314      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3315      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3316      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3317      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3318      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3319      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3320      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3321      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3322      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3323      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3324      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3325      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3326      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3327      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3328      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3329      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3330      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3331      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3332      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3333      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3334      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3335      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3336      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3337      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3338      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3339      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3340      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3341      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3342      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3343      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3344      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3345      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3346      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3347      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3348      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3349      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3350      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3351      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3352      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3353      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3354      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3355      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3356      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3357      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3358      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3359      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3360      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3361      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3362      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3363      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3364      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3365      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3366      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3367      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3368      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3369      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3370      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3371      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3372      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3373      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3374      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3375      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3376      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3377      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3378      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3379      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3380      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3381      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3382      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3383      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3384      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3385      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3386      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3387      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3388      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3389      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3390      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3391      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3392      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3393      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3394      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3395      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3396      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3397      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3398      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3399      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3400      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3401      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3402      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3403      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3404      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3405      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3406      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3407      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3408      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3409      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3410      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3411      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3412      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3413      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3414      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3415      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3416      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3417      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3418      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3419      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3420      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3421      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3422      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3423      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3424      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3425      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3426      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3427      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3428      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3429      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3430      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3431      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3432      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3433      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3434      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3435      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3436      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3437      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3438      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3439      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3440      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3441      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3442      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3443      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3444      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3445      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3446      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3447      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3448      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3449      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3450      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3451      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3452      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3453      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3454      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3455      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3456      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3457      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3458      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3459      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3460      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3461      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3462      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3463      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3464      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3465      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3466      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3467      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3468      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3469      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3470      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3471      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3472      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3473      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3474      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3475      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3476      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3477      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3478      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3479      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3480      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3481      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3482      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3483      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3484      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3485      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3486      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3487      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3488      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3489      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3490      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3491      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3492      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3493      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3494      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3495      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3496      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3497      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3498      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3499      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3500      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3501      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3502      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3503      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3504      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3505      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3506      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3507      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3508      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3509      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3510      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3511      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3512      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3513      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3514      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3515      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3516      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3517      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3518      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3519      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3520      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3521      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3522      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3523      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3524      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3525      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3526      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3527      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3528      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3529      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3530      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3531      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3532      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3533      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3534      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3535      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3536      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3537      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3538      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3539      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3540      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3541      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3542      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3543      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3544      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3545      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3546 };
3547
3548
3549 const USHORT fax_vert_huff[10] = {  0,
3550     0x1003, 0x3008, 0x3002, 0x3004, 0x4007, 0x6001, 0x6005, 0x7000,
3551     0x7006,
3552 };
3553
3554
3555 const BYTE fax_vert_huff_index[128] = {
3556      0,  0,  8,  9,  6,  6,  7,  7,  5,  5,  5,  5,  5,  5,  5,  5,
3557      2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,  2,
3558      3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,  3,
3559      4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,  4,
3560      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3561      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3562      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3563      1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,  1,
3564 };
3565
3566 /* End of File */