src/tiff/libtiff/tif_fax3.h

   1 /* $Id$ */
   2
   3 /*
   4  * Copyright (c) 1990-1997 Sam Leffler
   5  * Copyright (c) 1991-1997 Silicon Graphics, Inc.
   6  *
   7  * Permission to use, copy, modify, distribute, and sell this software and
   8  * its documentation for any purpose is hereby granted without fee, provided
   9  * that (i) the above copyright notices and this permission notice appear in
  10  * all copies of the software and related documentation, and (ii) the names of
  11  * Sam Leffler and Silicon Graphics may not be used in any advertising or
  12  * publicity relating to the software without the specific, prior written
  13  * permission of Sam Leffler and Silicon Graphics.
  14  *
  15  * THE SOFTWARE IS PROVIDED "AS-IS" AND WITHOUT WARRANTY OF ANY KIND,
  16  * EXPRESS, IMPLIED OR OTHERWISE, INCLUDING WITHOUT LIMITATION, ANY
  17  * WARRANTY OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
  18  *
  19  * IN NO EVENT SHALL SAM LEFFLER OR SILICON GRAPHICS BE LIABLE FOR
  20  * ANY SPECIAL, INCIDENTAL, INDIRECT OR CONSEQUENTIAL DAMAGES OF ANY KIND,
  21  * OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
  22  * WHETHER OR NOT ADVISED OF THE POSSIBILITY OF DAMAGE, AND ON ANY THEORY OF
  23  * LIABILITY, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE
  24  * OF THIS SOFTWARE.
  25  */
  26
  27 #ifndef _FAX3_
  28 #define _FAX3_
  29 /*
  30  * TIFF Library.
  31  *
  32  * CCITT Group 3 (T.4) and Group 4 (T.6) Decompression Support.
  33  *
  34  * Decoder support is derived, with permission, from the code
  35  * in Frank Cringle's viewfax program;
  36  *      Copyright (C) 1990, 1995  Frank D. Cringle.
  37  */
  38 #include "tiff.h"
  39
  40 /*
  41  * To override the default routine used to image decoded
  42  * spans one can use the pseduo tag TIFFTAG_FAXFILLFUNC.
  43  * The routine must have the type signature given below;
  44  * for example:
  45  *
  46  * fillruns(unsigned char* buf, uint32* runs, uint32* erun, uint32 lastx)
  47  *
  48  * where buf is place to set the bits, runs is the array of b&w run
  49  * lengths (white then black), erun is the last run in the array, and
  50  * lastx is the width of the row in pixels.  Fill routines can assume
  51  * the run array has room for at least lastx runs and can overwrite
  52  * data in the run array as needed (e.g. to append zero runs to bring
  53  * the count up to a nice multiple).
  54  */
  55 typedef void (*TIFFFaxFillFunc)(unsigned char*, uint32*, uint32*, uint32);
  56
  57 /*
  58  * The default run filler; made external for other decoders.
  59  */
  60 #if defined(__cplusplus)
  61 extern "C" {
  62 #endif
  63 extern  void _TIFFFax3fillruns(unsigned char*, uint32*, uint32*, uint32);
  64 #if defined(__cplusplus)
  65 }
  66 #endif
  67
  68
  69 /* finite state machine codes */
  70 #define S_Null          0
  71 #define S_Pass          1
  72 #define S_Horiz         2
  73 #define S_V0            3
  74 #define S_VR            4
  75 #define S_VL            5
  76 #define S_Ext           6
  77 #define S_TermW         7
  78 #define S_TermB         8
  79 #define S_MakeUpW       9
  80 #define S_MakeUpB       10
  81 #define S_MakeUp        11
  82 #define S_EOL           12
  83
  84 typedef struct {                /* state table entry */
  85         unsigned char State;    /* see above */
  86         unsigned char Width;    /* width of code in bits */
  87         uint32  Param;          /* unsigned 32-bit run length in bits */
  88 } TIFFFaxTabEnt;
  89
  90 extern  const TIFFFaxTabEnt TIFFFaxMainTable[];
  91 extern  const TIFFFaxTabEnt TIFFFaxWhiteTable[];
  92 extern  const TIFFFaxTabEnt TIFFFaxBlackTable[];
  93
  94 /*
  95  * The following macros define the majority of the G3/G4 decoder
  96  * algorithm using the state tables defined elsewhere.  To build
  97  * a decoder you need some setup code and some glue code. Note
  98  * that you may also need/want to change the way the NeedBits*
  99  * macros get input data if, for example, you know the data to be
 100  * decoded is properly aligned and oriented (doing so before running
 101  * the decoder can be a big performance win).
 102  *
 103  * Consult the decoder in the TIFF library for an idea of what you
 104  * need to define and setup to make use of these definitions.
 105  *
 106  * NB: to enable a debugging version of these macros define FAX3_DEBUG
 107  *     before including this file.  Trace output goes to stdout.
 108  */
 109
 110 #ifndef EndOfData
 111 #define EndOfData()     (cp >= ep)
 112 #endif
 113 /*
 114  * Need <=8 or <=16 bits of input data.  Unlike viewfax we
 115  * cannot use/assume a word-aligned, properly bit swizzled
 116  * input data set because data may come from an arbitrarily
 117  * aligned, read-only source such as a memory-mapped file.
 118  * Note also that the viewfax decoder does not check for
 119  * running off the end of the input data buffer.  This is
 120  * possible for G3-encoded data because it prescans the input
 121  * data to count EOL markers, but can cause problems for G4
 122  * data.  In any event, we don't prescan and must watch for
 123  * running out of data since we can't permit the library to
 124  * scan past the end of the input data buffer.
 125  *
 126  * Finally, note that we must handle remaindered data at the end
 127  * of a strip specially.  The coder asks for a fixed number of
 128  * bits when scanning for the next code.  This may be more bits
 129  * than are actually present in the data stream.  If we appear
 130  * to run out of data but still have some number of valid bits
 131  * remaining then we makeup the requested amount with zeros and
 132  * return successfully.  If the returned data is incorrect then
 133  * we should be called again and get a premature EOF error;
 134  * otherwise we should get the right answer.
 135  */
 136 #ifndef NeedBits8
 137 #define NeedBits8(n,eoflab) do {                                        \
 138     if (BitsAvail < (n)) {                                              \
 139         if (EndOfData()) {                                              \
 140             if (BitsAvail == 0)                 /* no valid bits */     \
 141                 goto eoflab;                                            \
 142             BitsAvail = (n);                    /* pad with zeros */    \
 143         } else {                                                        \
 144             BitAcc |= ((uint32) bitmap[*cp++])<<BitsAvail;              \
 145             BitsAvail += 8;                                             \
 146         }                                                               \
 147     }                                                                   \
 148 } while (0)
 149 #endif
 150 #ifndef NeedBits16
 151 #define NeedBits16(n,eoflab) do {                                       \
 152     if (BitsAvail < (n)) {                                              \
 153         if (EndOfData()) {                                              \
 154             if (BitsAvail == 0)                 /* no valid bits */     \
 155                 goto eoflab;                                            \
 156             BitsAvail = (n);                    /* pad with zeros */    \
 157         } else {                                                        \
 158             BitAcc |= ((uint32) bitmap[*cp++])<<BitsAvail;              \
 159             if ((BitsAvail += 8) < (n)) {                               \
 160                 if (EndOfData()) {                                      \
 161                     /* NB: we know BitsAvail is non-zero here */        \
 162                     BitsAvail = (n);            /* pad with zeros */    \
 163                 } else {                                                \
 164                     BitAcc |= ((uint32) bitmap[*cp++])<<BitsAvail;      \
 165                     BitsAvail += 8;                                     \
 166                 }                                                       \
 167             }                                                           \
 168         }                                                               \
 169     }                                                                   \
 170 } while (0)
 171 #endif
 172 #define GetBits(n)      (BitAcc & ((1<<(n))-1))
 173 #define ClrBits(n) do {                                                 \
 174     BitsAvail -= (n);                                                   \
 175     BitAcc >>= (n);                                                     \
 176 } while (0)
 177
 178 #ifdef FAX3_DEBUG
 179 static const char* StateNames[] = {
 180     "Null   ",
 181     "Pass   ",
 182     "Horiz  ",
 183     "V0     ",
 184     "VR     ",
 185     "VL     ",
 186     "Ext    ",
 187     "TermW  ",
 188     "TermB  ",
 189     "MakeUpW",
 190     "MakeUpB",
 191     "MakeUp ",
 192     "EOL    ",
 193 };
 194 #define DEBUG_SHOW putchar(BitAcc & (1 << t) ? '1' : '0')
 195 #define LOOKUP8(wid,tab,eoflab) do {                                    \
 196     int t;                                                              \
 197     NeedBits8(wid,eoflab);                                              \
 198     TabEnt = tab + GetBits(wid);                                        \
 199     printf("%08lX/%d: %s%5d\t", (long) BitAcc, BitsAvail,               \
 200            StateNames[TabEnt->State], TabEnt->Param);                   \
 201     for (t = 0; t < TabEnt->Width; t++)                                 \
 202         DEBUG_SHOW;                                                     \
 203     putchar('\n');                                                      \
 204     fflush(stdout);                                                     \
 205     ClrBits(TabEnt->Width);                                             \
 206 } while (0)
 207 #define LOOKUP16(wid,tab,eoflab) do {                                   \
 208     int t;                                                              \
 209     NeedBits16(wid,eoflab);                                             \
 210     TabEnt = tab + GetBits(wid);                                        \
 211     printf("%08lX/%d: %s%5d\t", (long) BitAcc, BitsAvail,               \
 212            StateNames[TabEnt->State], TabEnt->Param);                   \
 213     for (t = 0; t < TabEnt->Width; t++)                                 \
 214         DEBUG_SHOW;                                                     \
 215     putchar('\n');                                                      \
 216     fflush(stdout);                                                     \
 217     ClrBits(TabEnt->Width);                                             \
 218 } while (0)
 219
 220 #define SETVALUE(x) do {                                                        \
 221     *pa++ = RunLength + (x);                                            \
 222     printf("SETVALUE: %d\t%d\n", RunLength + (x), a0);                  \
 223     a0 += x;                                                            \
 224     RunLength = 0;                                                      \
 225 } while (0)
 226 #else
 227 #define LOOKUP8(wid,tab,eoflab) do {                                    \
 228     NeedBits8(wid,eoflab);                                              \
 229     TabEnt = tab + GetBits(wid);                                        \
 230     ClrBits(TabEnt->Width);                                             \
 231 } while (0)
 232 #define LOOKUP16(wid,tab,eoflab) do {                                   \
 233     NeedBits16(wid,eoflab);                                             \
 234     TabEnt = tab + GetBits(wid);                                        \
 235     ClrBits(TabEnt->Width);                                             \
 236 } while (0)
 237
 238 /*
 239  * Append a run to the run length array for the
 240  * current row and reset decoding state.
 241  */
 242 #define SETVALUE(x) do {                                                        \
 243     *pa++ = RunLength + (x);                                            \
 244     a0 += (x);                                                          \
 245     RunLength = 0;                                                      \
 246 } while (0)
 247 #endif
 248
 249 /*
 250  * Synchronize input decoding at the start of each
 251  * row by scanning for an EOL (if appropriate) and
 252  * skipping any trash data that might be present
 253  * after a decoding error.  Note that the decoding
 254  * done elsewhere that recognizes an EOL only consumes
 255  * 11 consecutive zero bits.  This means that if EOLcnt
 256  * is non-zero then we still need to scan for the final flag
 257  * bit that is part of the EOL code.
 258  */
 259 #define SYNC_EOL(eoflab) do {                                           \
 260     if (EOLcnt == 0) {                                                  \
 261         for (;;) {                                                      \
 262             NeedBits16(11,eoflab);                                      \
 263             if (GetBits(11) == 0)                                       \
 264                 break;                                                  \
 265             ClrBits(1);                                                 \
 266         }                                                               \
 267     }                                                                   \
 268     for (;;) {                                                          \
 269         NeedBits8(8,eoflab);                                            \
 270         if (GetBits(8))                                                 \
 271             break;                                                      \
 272         ClrBits(8);                                                     \
 273     }                                                                   \
 274     while (GetBits(1) == 0)                                             \
 275         ClrBits(1);                                                     \
 276     ClrBits(1);                         /* EOL bit */                   \
 277     EOLcnt = 0;                         /* reset EOL counter/flag */    \
 278 } while (0)
 279
 280 /*
 281  * Cleanup the array of runs after decoding a row.
 282  * We adjust final runs to insure the user buffer is not
 283  * overwritten and/or undecoded area is white filled.
 284  */
 285 #define CLEANUP_RUNS() do {                                             \
 286     if (RunLength)                                                      \
 287         SETVALUE(0);                                                    \
 288     if (a0 != lastx) {                                                  \
 289         badlength(a0, lastx);                                           \
 290         while (a0 > lastx && pa > thisrun)                              \
 291             a0 -= *--pa;                                                \
 292         if (a0 < lastx) {                                               \
 293             if (a0 < 0)                                                 \
 294                 a0 = 0;                                                 \
 295             if ((pa-thisrun)&1)                                         \
 296                 SETVALUE(0);                                            \
 297             SETVALUE(lastx - a0);                                               \
 298         } else if (a0 > lastx) {                                        \
 299             SETVALUE(lastx);                                            \
 300             SETVALUE(0);                                                        \
 301         }                                                               \
 302     }                                                                   \
 303 } while (0)
 304
 305 /*
 306  * Decode a line of 1D-encoded data.
 307  *
 308  * The line expanders are written as macros so that they can be reused
 309  * but still have direct access to the local variables of the "calling"
 310  * function.
 311  *
 312  * Note that unlike the original version we have to explicitly test for
 313  * a0 >= lastx after each black/white run is decoded.  This is because
 314  * the original code depended on the input data being zero-padded to
 315  * insure the decoder recognized an EOL before running out of data.
 316  */
 317 #define EXPAND1D(eoflab) do {                                           \
 318     for (;;) {                                                          \
 319         for (;;) {                                                      \
 320             LOOKUP16(12, TIFFFaxWhiteTable, eof1d);                     \
 321             switch (TabEnt->State) {                                    \
 322             case S_EOL:                                                 \
 323                 EOLcnt = 1;                                             \
 324                 goto done1d;                                            \
 325             case S_TermW:                                               \
 326                 SETVALUE(TabEnt->Param);                                        \
 327                 goto doneWhite1d;                                       \
 328             case S_MakeUpW:                                             \
 329             case S_MakeUp:                                              \
 330                 a0 += TabEnt->Param;                                    \
 331                 RunLength += TabEnt->Param;                             \
 332                 break;                                                  \
 333             default:                                                    \
 334                 unexpected("WhiteTable", a0);                           \
 335                 goto done1d;                                            \
 336             }                                                           \
 337         }                                                               \
 338     doneWhite1d:                                                        \
 339         if (a0 >= lastx)                                                \
 340             goto done1d;                                                \
 341         for (;;) {                                                      \
 342             LOOKUP16(13, TIFFFaxBlackTable, eof1d);                     \
 343             switch (TabEnt->State) {                                    \
 344             case S_EOL:                                                 \
 345                 EOLcnt = 1;                                             \
 346                 goto done1d;                                            \
 347             case S_TermB:                                               \
 348                 SETVALUE(TabEnt->Param);                                        \
 349                 goto doneBlack1d;                                       \
 350             case S_MakeUpB:                                             \
 351             case S_MakeUp:                                              \
 352                 a0 += TabEnt->Param;                                    \
 353                 RunLength += TabEnt->Param;                             \
 354                 break;                                                  \
 355             default:                                                    \
 356                 unexpected("BlackTable", a0);                           \
 357                 goto done1d;                                            \
 358             }                                                           \
 359         }                                                               \
 360     doneBlack1d:                                                        \
 361         if (a0 >= lastx)                                                \
 362             goto done1d;                                                \
 363         if( *(pa-1) == 0 && *(pa-2) == 0 )                              \
 364             pa -= 2;                                                    \
 365     }                                                                   \
 366 eof1d:                                                                  \
 367     prematureEOF(a0);                                                   \
 368     CLEANUP_RUNS();                                                     \
 369     goto eoflab;                                                        \
 370 done1d:                                                                 \
 371     CLEANUP_RUNS();                                                     \
 372 } while (0)
 373
 374 /*
 375  * Update the value of b1 using the array
 376  * of runs for the reference line.
 377  */
 378 #define CHECK_b1 do {                                                   \
 379     if (pa != thisrun) while (b1 <= a0 && b1 < lastx) {                 \
 380         b1 += pb[0] + pb[1];                                            \
 381         pb += 2;                                                        \
 382     }                                                                   \
 383 } while (0)
 384
 385 /*
 386  * Expand a row of 2D-encoded data.
 387  */
 388 #define EXPAND2D(eoflab) do {                                           \
 389     while (a0 < lastx) {                                                \
 390         LOOKUP8(7, TIFFFaxMainTable, eof2d);                            \
 391         switch (TabEnt->State) {                                        \
 392         case S_Pass:                                                    \
 393             CHECK_b1;                                                   \
 394             b1 += *pb++;                                                \
 395             RunLength += b1 - a0;                                       \
 396             a0 = b1;                                                    \
 397             b1 += *pb++;                                                \
 398             break;                                                      \
 399         case S_Horiz:                                                   \
 400             if ((pa-thisrun)&1) {                                       \
 401                 for (;;) {      /* black first */                       \
 402                     LOOKUP16(13, TIFFFaxBlackTable, eof2d);             \
 403                     switch (TabEnt->State) {                            \
 404                     case S_TermB:                                       \
 405                         SETVALUE(TabEnt->Param);                                \
 406                         goto doneWhite2da;                              \
 407                     case S_MakeUpB:                                     \
 408                     case S_MakeUp:                                      \
 409                         a0 += TabEnt->Param;                            \
 410                         RunLength += TabEnt->Param;                     \
 411                         break;                                          \
 412                     default:                                            \
 413                         goto badBlack2d;                                \
 414                     }                                                   \
 415                 }                                                       \
 416             doneWhite2da:;                                              \
 417                 for (;;) {      /* then white */                        \
 418                     LOOKUP16(12, TIFFFaxWhiteTable, eof2d);             \
 419                     switch (TabEnt->State) {                            \
 420                     case S_TermW:                                       \
 421                         SETVALUE(TabEnt->Param);                                \
 422                         goto doneBlack2da;                              \
 423                     case S_MakeUpW:                                     \
 424                     case S_MakeUp:                                      \
 425                         a0 += TabEnt->Param;                            \
 426                         RunLength += TabEnt->Param;                     \
 427                         break;                                          \
 428                     default:                                            \
 429                         goto badWhite2d;                                \
 430                     }                                                   \
 431                 }                                                       \
 432             doneBlack2da:;                                              \
 433             } else {                                                    \
 434                 for (;;) {      /* white first */                       \
 435                     LOOKUP16(12, TIFFFaxWhiteTable, eof2d);             \
 436                     switch (TabEnt->State) {                            \
 437                     case S_TermW:                                       \
 438                         SETVALUE(TabEnt->Param);                                \
 439                         goto doneWhite2db;                              \
 440                     case S_MakeUpW:                                     \
 441                     case S_MakeUp:                                      \
 442                         a0 += TabEnt->Param;                            \
 443                         RunLength += TabEnt->Param;                     \
 444                         break;                                          \
 445                     default:                                            \
 446                         goto badWhite2d;                                \
 447                     }                                                   \
 448                 }                                                       \
 449             doneWhite2db:;                                              \
 450                 for (;;) {      /* then black */                        \
 451                     LOOKUP16(13, TIFFFaxBlackTable, eof2d);             \
 452                     switch (TabEnt->State) {                            \
 453                     case S_TermB:                                       \
 454                         SETVALUE(TabEnt->Param);                                \
 455                         goto doneBlack2db;                              \
 456                     case S_MakeUpB:                                     \
 457                     case S_MakeUp:                                      \
 458                         a0 += TabEnt->Param;                            \
 459                         RunLength += TabEnt->Param;                     \
 460                         break;                                          \
 461                     default:                                            \
 462                         goto badBlack2d;                                \
 463                     }                                                   \
 464                 }                                                       \
 465             doneBlack2db:;                                              \
 466             }                                                           \
 467             CHECK_b1;                                                   \
 468             break;                                                      \
 469         case S_V0:                                                      \
 470             CHECK_b1;                                                   \
 471             SETVALUE(b1 - a0);                                          \
 472             b1 += *pb++;                                                \
 473             break;                                                      \
 474         case S_VR:                                                      \
 475             CHECK_b1;                                                   \
 476             SETVALUE(b1 - a0 + TabEnt->Param);                          \
 477             b1 += *pb++;                                                \
 478             break;                                                      \
 479         case S_VL:                                                      \
 480             CHECK_b1;                                                   \
 481             SETVALUE(b1 - a0 - TabEnt->Param);                          \
 482             b1 -= *--pb;                                                \
 483             break;                                                      \
 484         case S_Ext:                                                     \
 485             *pa++ = lastx - a0;                                         \
 486             extension(a0);                                              \
 487             goto eol2d;                                                 \
 488         case S_EOL:                                                     \
 489             *pa++ = lastx - a0;                                         \
 490             NeedBits8(4,eof2d);                                         \
 491             if (GetBits(4))                                             \
 492                 unexpected("EOL", a0);                                  \
 493             ClrBits(4);                                                 \
 494             EOLcnt = 1;                                                 \
 495             goto eol2d;                                                 \
 496         default:                                                        \
 497         badMain2d:                                                      \
 498             unexpected("MainTable", a0);                                \
 499             goto eol2d;                                                 \
 500         badBlack2d:                                                     \
 501             unexpected("BlackTable", a0);                               \
 502             goto eol2d;                                                 \
 503         badWhite2d:                                                     \
 504             unexpected("WhiteTable", a0);                               \
 505             goto eol2d;                                                 \
 506         eof2d:                                                          \
 507             prematureEOF(a0);                                           \
 508             CLEANUP_RUNS();                                             \
 509             goto eoflab;                                                \
 510         }                                                               \
 511     }                                                                   \
 512     if (RunLength) {                                                    \
 513         if (RunLength + a0 < lastx) {                                   \
 514             /* expect a final V0 */                                     \
 515             NeedBits8(1,eof2d);                                         \
 516             if (!GetBits(1))                                            \
 517                 goto badMain2d;                                         \
 518             ClrBits(1);                                                 \
 519         }                                                               \
 520         SETVALUE(0);                                                    \
 521     }                                                                   \
 522 eol2d:                                                                  \
 523     CLEANUP_RUNS();                                                     \
 524 } while (0)
 525 #endif /* _FAX3_ */