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