src/tiff/libtiff/tif_fax3.h

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