1/* $Id: tif_lzw.c,v 1.29.2.6 2010-06-08 18:50:42 bfriesen Exp $ */ 2 3/* 4 * Copyright (c) 1988-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#include "tiffiop.h" 28#ifdef LZW_SUPPORT 29/* 30 * TIFF Library. 31 * Rev 5.0 Lempel-Ziv & Welch Compression Support 32 * 33 * This code is derived from the compress program whose code is 34 * derived from software contributed to Berkeley by James A. Woods, 35 * derived from original work by Spencer Thomas and Joseph Orost. 36 * 37 * The original Berkeley copyright notice appears below in its entirety. 38 */ 39#include "tif_predict.h" 40 41#include <stdio.h> 42 43/* 44 * NB: The 5.0 spec describes a different algorithm than Aldus 45 * implements. Specifically, Aldus does code length transitions 46 * one code earlier than should be done (for real LZW). 47 * Earlier versions of this library implemented the correct 48 * LZW algorithm, but emitted codes in a bit order opposite 49 * to the TIFF spec. Thus, to maintain compatibility w/ Aldus 50 * we interpret MSB-LSB ordered codes to be images written w/ 51 * old versions of this library, but otherwise adhere to the 52 * Aldus "off by one" algorithm. 53 * 54 * Future revisions to the TIFF spec are expected to "clarify this issue". 55 */ 56#define LZW_COMPAT /* include backwards compatibility code */ 57/* 58 * Each strip of data is supposed to be terminated by a CODE_EOI. 59 * If the following #define is included, the decoder will also 60 * check for end-of-strip w/o seeing this code. This makes the 61 * library more robust, but also slower. 62 */ 63#define LZW_CHECKEOS /* include checks for strips w/o EOI code */ 64 65#define MAXCODE(n) ((1L<<(n))-1) 66/* 67 * The TIFF spec specifies that encoded bit 68 * strings range from 9 to 12 bits. 69 */ 70#define BITS_MIN 9 /* start with 9 bits */ 71#define BITS_MAX 12 /* max of 12 bit strings */ 72/* predefined codes */ 73#define CODE_CLEAR 256 /* code to clear string table */ 74#define CODE_EOI 257 /* end-of-information code */ 75#define CODE_FIRST 258 /* first free code entry */ 76#define CODE_MAX MAXCODE(BITS_MAX) 77#define HSIZE 9001L /* 91% occupancy */ 78#define HSHIFT (13-8) 79#ifdef LZW_COMPAT 80/* NB: +1024 is for compatibility with old files */ 81#define CSIZE (MAXCODE(BITS_MAX)+1024L) 82#else 83#define CSIZE (MAXCODE(BITS_MAX)+1L) 84#endif 85 86/* 87 * State block for each open TIFF file using LZW 88 * compression/decompression. Note that the predictor 89 * state block must be first in this data structure. 90 */ 91typedef struct { 92 TIFFPredictorState predict; /* predictor super class */ 93 94 unsigned short nbits; /* # of bits/code */ 95 unsigned short maxcode; /* maximum code for lzw_nbits */ 96 unsigned short free_ent; /* next free entry in hash table */ 97 long nextdata; /* next bits of i/o */ 98 long nextbits; /* # of valid bits in lzw_nextdata */ 99 100 int rw_mode; /* preserve rw_mode from init */ 101} LZWBaseState; 102 103#define lzw_nbits base.nbits 104#define lzw_maxcode base.maxcode 105#define lzw_free_ent base.free_ent 106#define lzw_nextdata base.nextdata 107#define lzw_nextbits base.nextbits 108 109/* 110 * Encoding-specific state. 111 */ 112typedef uint16 hcode_t; /* codes fit in 16 bits */ 113typedef struct { 114 long hash; 115 hcode_t code; 116} hash_t; 117 118/* 119 * Decoding-specific state. 120 */ 121typedef struct code_ent { 122 struct code_ent *next; 123 unsigned short length; /* string len, including this token */ 124 unsigned char value; /* data value */ 125 unsigned char firstchar; /* first token of string */ 126} code_t; 127 128typedef int (*decodeFunc)(TIFF*, tidata_t, tsize_t, tsample_t); 129 130typedef struct { 131 LZWBaseState base; 132 133 /* Decoding specific data */ 134 long dec_nbitsmask; /* lzw_nbits 1 bits, right adjusted */ 135 long dec_restart; /* restart count */ 136#ifdef LZW_CHECKEOS 137 long dec_bitsleft; /* available bits in raw data */ 138#endif 139 decodeFunc dec_decode; /* regular or backwards compatible */ 140 code_t* dec_codep; /* current recognized code */ 141 code_t* dec_oldcodep; /* previously recognized code */ 142 code_t* dec_free_entp; /* next free entry */ 143 code_t* dec_maxcodep; /* max available entry */ 144 code_t* dec_codetab; /* kept separate for small machines */ 145 146 /* Encoding specific data */ 147 int enc_oldcode; /* last code encountered */ 148 long enc_checkpoint; /* point at which to clear table */ 149#define CHECK_GAP 10000 /* enc_ratio check interval */ 150 long enc_ratio; /* current compression ratio */ 151 long enc_incount; /* (input) data bytes encoded */ 152 long enc_outcount; /* encoded (output) bytes */ 153 tidata_t enc_rawlimit; /* bound on tif_rawdata buffer */ 154 hash_t* enc_hashtab; /* kept separate for small machines */ 155} LZWCodecState; 156 157#define LZWState(tif) ((LZWBaseState*) (tif)->tif_data) 158#define DecoderState(tif) ((LZWCodecState*) LZWState(tif)) 159#define EncoderState(tif) ((LZWCodecState*) LZWState(tif)) 160 161static int LZWDecode(TIFF*, tidata_t, tsize_t, tsample_t); 162#ifdef LZW_COMPAT 163static int LZWDecodeCompat(TIFF*, tidata_t, tsize_t, tsample_t); 164#endif 165static void cl_hash(LZWCodecState*); 166 167/* 168 * LZW Decoder. 169 */ 170 171#ifdef LZW_CHECKEOS 172/* 173 * This check shouldn't be necessary because each 174 * strip is suppose to be terminated with CODE_EOI. 175 */ 176#define NextCode(_tif, _sp, _bp, _code, _get) { \ 177 if ((_sp)->dec_bitsleft < nbits) { \ 178 TIFFWarningExt(_tif->tif_clientdata, _tif->tif_name, \ 179 "LZWDecode: Strip %d not terminated with EOI code", \ 180 _tif->tif_curstrip); \ 181 _code = CODE_EOI; \ 182 } else { \ 183 _get(_sp,_bp,_code); \ 184 (_sp)->dec_bitsleft -= nbits; \ 185 } \ 186} 187#else 188#define NextCode(tif, sp, bp, code, get) get(sp, bp, code) 189#endif 190 191static int 192LZWSetupDecode(TIFF* tif) 193{ 194 LZWCodecState* sp = DecoderState(tif); 195 static const char module[] = " LZWSetupDecode"; 196 int code; 197 198 if( sp == NULL ) 199 { 200 /* 201 * Allocate state block so tag methods have storage to record 202 * values. 203 */ 204 tif->tif_data = (tidata_t) _TIFFmalloc(sizeof(LZWCodecState)); 205 if (tif->tif_data == NULL) 206 { 207 TIFFErrorExt(tif->tif_clientdata, "LZWPreDecode", "No space for LZW state block"); 208 return (0); 209 } 210 211 DecoderState(tif)->dec_codetab = NULL; 212 DecoderState(tif)->dec_decode = NULL; 213 214 /* 215 * Setup predictor setup. 216 */ 217 (void) TIFFPredictorInit(tif); 218 219 sp = DecoderState(tif); 220 } 221 222 assert(sp != NULL); 223 224 if (sp->dec_codetab == NULL) { 225 sp->dec_codetab = (code_t*)_TIFFmalloc(CSIZE*sizeof (code_t)); 226 if (sp->dec_codetab == NULL) { 227 TIFFErrorExt(tif->tif_clientdata, module, 228 "No space for LZW code table"); 229 return (0); 230 } 231 /* 232 * Pre-load the table. 233 */ 234 code = 255; 235 do { 236 sp->dec_codetab[code].value = code; 237 sp->dec_codetab[code].firstchar = code; 238 sp->dec_codetab[code].length = 1; 239 sp->dec_codetab[code].next = NULL; 240 } while (code--); 241 /* 242 * Zero-out the unused entries 243 */ 244 _TIFFmemset(&sp->dec_codetab[CODE_CLEAR], 0, 245 (CODE_FIRST - CODE_CLEAR) * sizeof (code_t)); 246 } 247 return (1); 248} 249 250/* 251 * Setup state for decoding a strip. 252 */ 253static int 254LZWPreDecode(TIFF* tif, tsample_t s) 255{ 256 LZWCodecState *sp = DecoderState(tif); 257 258 (void) s; 259 assert(sp != NULL); 260 if( sp->dec_codetab == NULL ) 261 { 262 tif->tif_setupdecode( tif ); 263 } 264 265 /* 266 * Check for old bit-reversed codes. 267 */ 268 if (tif->tif_rawdata[0] == 0 && (tif->tif_rawdata[1] & 0x1)) { 269#ifdef LZW_COMPAT 270 if (!sp->dec_decode) { 271 TIFFWarningExt(tif->tif_clientdata, tif->tif_name, 272 "Old-style LZW codes, convert file"); 273 /* 274 * Override default decoding methods with 275 * ones that deal with the old coding. 276 * Otherwise the predictor versions set 277 * above will call the compatibility routines 278 * through the dec_decode method. 279 */ 280 tif->tif_decoderow = LZWDecodeCompat; 281 tif->tif_decodestrip = LZWDecodeCompat; 282 tif->tif_decodetile = LZWDecodeCompat; 283 /* 284 * If doing horizontal differencing, must 285 * re-setup the predictor logic since we 286 * switched the basic decoder methods... 287 */ 288 (*tif->tif_setupdecode)(tif); 289 sp->dec_decode = LZWDecodeCompat; 290 } 291 sp->lzw_maxcode = MAXCODE(BITS_MIN); 292#else /* !LZW_COMPAT */ 293 if (!sp->dec_decode) { 294 TIFFErrorExt(tif->tif_clientdata, tif->tif_name, 295 "Old-style LZW codes not supported"); 296 sp->dec_decode = LZWDecode; 297 } 298 return (0); 299#endif/* !LZW_COMPAT */ 300 } else { 301 sp->lzw_maxcode = MAXCODE(BITS_MIN)-1; 302 sp->dec_decode = LZWDecode; 303 } 304 sp->lzw_nbits = BITS_MIN; 305 sp->lzw_nextbits = 0; 306 sp->lzw_nextdata = 0; 307 308 sp->dec_restart = 0; 309 sp->dec_nbitsmask = MAXCODE(BITS_MIN); 310#ifdef LZW_CHECKEOS 311 sp->dec_bitsleft = tif->tif_rawcc << 3; 312#endif 313 sp->dec_free_entp = sp->dec_codetab + CODE_FIRST; 314 /* 315 * Zero entries that are not yet filled in. We do 316 * this to guard against bogus input data that causes 317 * us to index into undefined entries. If you can 318 * come up with a way to safely bounds-check input codes 319 * while decoding then you can remove this operation. 320 */ 321 _TIFFmemset(sp->dec_free_entp, 0, (CSIZE-CODE_FIRST)*sizeof (code_t)); 322 sp->dec_oldcodep = &sp->dec_codetab[-1]; 323 sp->dec_maxcodep = &sp->dec_codetab[sp->dec_nbitsmask-1]; 324 return (1); 325} 326 327/* 328 * Decode a "hunk of data". 329 */ 330#define GetNextCode(sp, bp, code) { \ 331 nextdata = (nextdata<<8) | *(bp)++; \ 332 nextbits += 8; \ 333 if (nextbits < nbits) { \ 334 nextdata = (nextdata<<8) | *(bp)++; \ 335 nextbits += 8; \ 336 } \ 337 code = (hcode_t)((nextdata >> (nextbits-nbits)) & nbitsmask); \ 338 nextbits -= nbits; \ 339} 340 341static void 342codeLoop(TIFF* tif) 343{ 344 TIFFErrorExt(tif->tif_clientdata, tif->tif_name, 345 "LZWDecode: Bogus encoding, loop in the code table; scanline %d", 346 tif->tif_row); 347} 348 349static int 350LZWDecode(TIFF* tif, tidata_t op0, tsize_t occ0, tsample_t s) 351{ 352 LZWCodecState *sp = DecoderState(tif); 353 char *op = (char*) op0; 354 long occ = (long) occ0; 355 char *tp; 356 unsigned char *bp; 357 hcode_t code; 358 int len; 359 long nbits, nextbits, nextdata, nbitsmask; 360 code_t *codep, *free_entp, *maxcodep, *oldcodep; 361 362 (void) s; 363 assert(sp != NULL); 364 assert(sp->dec_codetab != NULL); 365 /* 366 * Restart interrupted output operation. 367 */ 368 if (sp->dec_restart) { 369 long residue; 370 371 codep = sp->dec_codep; 372 residue = codep->length - sp->dec_restart; 373 if (residue > occ) { 374 /* 375 * Residue from previous decode is sufficient 376 * to satisfy decode request. Skip to the 377 * start of the decoded string, place decoded 378 * values in the output buffer, and return. 379 */ 380 sp->dec_restart += occ; 381 do { 382 codep = codep->next; 383 } while (--residue > occ && codep); 384 if (codep) { 385 tp = op + occ; 386 do { 387 *--tp = codep->value; 388 codep = codep->next; 389 } while (--occ && codep); 390 } 391 return (1); 392 } 393 /* 394 * Residue satisfies only part of the decode request. 395 */ 396 op += residue, occ -= residue; 397 tp = op; 398 do { 399 int t; 400 --tp; 401 t = codep->value; 402 codep = codep->next; 403 *tp = t; 404 } while (--residue && codep); 405 sp->dec_restart = 0; 406 } 407 408 bp = (unsigned char *)tif->tif_rawcp; 409 nbits = sp->lzw_nbits; 410 nextdata = sp->lzw_nextdata; 411 nextbits = sp->lzw_nextbits; 412 nbitsmask = sp->dec_nbitsmask; 413 oldcodep = sp->dec_oldcodep; 414 free_entp = sp->dec_free_entp; 415 maxcodep = sp->dec_maxcodep; 416 417 while (occ > 0) { 418 NextCode(tif, sp, bp, code, GetNextCode); 419 if (code == CODE_EOI) 420 break; 421 if (code == CODE_CLEAR) { 422 free_entp = sp->dec_codetab + CODE_FIRST; 423 _TIFFmemset(free_entp, 0, 424 (CSIZE - CODE_FIRST) * sizeof (code_t)); 425 nbits = BITS_MIN; 426 nbitsmask = MAXCODE(BITS_MIN); 427 maxcodep = sp->dec_codetab + nbitsmask-1; 428 NextCode(tif, sp, bp, code, GetNextCode); 429 if (code == CODE_EOI) 430 break; 431 if (code == CODE_CLEAR) { 432 TIFFErrorExt(tif->tif_clientdata, tif->tif_name, 433 "LZWDecode: Corrupted LZW table at scanline %d", 434 tif->tif_row); 435 return (0); 436 } 437 *op++ = (char)code, occ--; 438 oldcodep = sp->dec_codetab + code; 439 continue; 440 } 441 codep = sp->dec_codetab + code; 442 443 /* 444 * Add the new entry to the code table. 445 */ 446 if (free_entp < &sp->dec_codetab[0] || 447 free_entp >= &sp->dec_codetab[CSIZE]) { 448 TIFFErrorExt(tif->tif_clientdata, tif->tif_name, 449 "LZWDecode: Corrupted LZW table at scanline %d", 450 tif->tif_row); 451 return (0); 452 } 453 454 free_entp->next = oldcodep; 455 if (free_entp->next < &sp->dec_codetab[0] || 456 free_entp->next >= &sp->dec_codetab[CSIZE]) { 457 TIFFErrorExt(tif->tif_clientdata, tif->tif_name, 458 "LZWDecode: Corrupted LZW table at scanline %d", 459 tif->tif_row); 460 return (0); 461 } 462 free_entp->firstchar = free_entp->next->firstchar; 463 free_entp->length = free_entp->next->length+1; 464 free_entp->value = (codep < free_entp) ? 465 codep->firstchar : free_entp->firstchar; 466 if (++free_entp > maxcodep) { 467 if (++nbits > BITS_MAX) /* should not happen */ 468 nbits = BITS_MAX; 469 nbitsmask = MAXCODE(nbits); 470 maxcodep = sp->dec_codetab + nbitsmask-1; 471 } 472 oldcodep = codep; 473 if (code >= 256) { 474 /* 475 * Code maps to a string, copy string 476 * value to output (written in reverse). 477 */ 478 if(codep->length == 0) { 479 TIFFErrorExt(tif->tif_clientdata, tif->tif_name, 480 "LZWDecode: Wrong length of decoded string: " 481 "data probably corrupted at scanline %d", 482 tif->tif_row); 483 return (0); 484 } 485 if (codep->length > occ) { 486 /* 487 * String is too long for decode buffer, 488 * locate portion that will fit, copy to 489 * the decode buffer, and setup restart 490 * logic for the next decoding call. 491 */ 492 sp->dec_codep = codep; 493 do { 494 codep = codep->next; 495 } while (codep && codep->length > occ); 496 if (codep) { 497 sp->dec_restart = occ; 498 tp = op + occ; 499 do { 500 *--tp = codep->value; 501 codep = codep->next; 502 } while (--occ && codep); 503 if (codep) 504 codeLoop(tif); 505 } 506 break; 507 } 508 len = codep->length; 509 tp = op + len; 510 do { 511 int t; 512 --tp; 513 t = codep->value; 514 codep = codep->next; 515 *tp = t; 516 } while (codep && tp > op); 517 if (codep) { 518 codeLoop(tif); 519 break; 520 } 521 op += len, occ -= len; 522 } else 523 *op++ = (char)code, occ--; 524 } 525 526 tif->tif_rawcp = (tidata_t) bp; 527 sp->lzw_nbits = (unsigned short) nbits; 528 sp->lzw_nextdata = nextdata; 529 sp->lzw_nextbits = nextbits; 530 sp->dec_nbitsmask = nbitsmask; 531 sp->dec_oldcodep = oldcodep; 532 sp->dec_free_entp = free_entp; 533 sp->dec_maxcodep = maxcodep; 534 535 if (occ > 0) { 536 TIFFErrorExt(tif->tif_clientdata, tif->tif_name, 537 "LZWDecode: Not enough data at scanline %d (short %ld bytes)", 538 tif->tif_row, occ); 539 return (0); 540 } 541 return (1); 542} 543 544#ifdef LZW_COMPAT 545/* 546 * Decode a "hunk of data" for old images. 547 */ 548#define GetNextCodeCompat(sp, bp, code) { \ 549 nextdata |= (unsigned long) *(bp)++ << nextbits; \ 550 nextbits += 8; \ 551 if (nextbits < nbits) { \ 552 nextdata |= (unsigned long) *(bp)++ << nextbits;\ 553 nextbits += 8; \ 554 } \ 555 code = (hcode_t)(nextdata & nbitsmask); \ 556 nextdata >>= nbits; \ 557 nextbits -= nbits; \ 558} 559 560static int 561LZWDecodeCompat(TIFF* tif, tidata_t op0, tsize_t occ0, tsample_t s) 562{ 563 LZWCodecState *sp = DecoderState(tif); 564 char *op = (char*) op0; 565 long occ = (long) occ0; 566 char *tp; 567 unsigned char *bp; 568 int code, nbits; 569 long nextbits, nextdata, nbitsmask; 570 code_t *codep, *free_entp, *maxcodep, *oldcodep; 571 572 (void) s; 573 assert(sp != NULL); 574 /* 575 * Restart interrupted output operation. 576 */ 577 if (sp->dec_restart) { 578 long residue; 579 580 codep = sp->dec_codep; 581 residue = codep->length - sp->dec_restart; 582 if (residue > occ) { 583 /* 584 * Residue from previous decode is sufficient 585 * to satisfy decode request. Skip to the 586 * start of the decoded string, place decoded 587 * values in the output buffer, and return. 588 */ 589 sp->dec_restart += occ; 590 do { 591 codep = codep->next; 592 } while (--residue > occ); 593 tp = op + occ; 594 do { 595 *--tp = codep->value; 596 codep = codep->next; 597 } while (--occ); 598 return (1); 599 } 600 /* 601 * Residue satisfies only part of the decode request. 602 */ 603 op += residue, occ -= residue; 604 tp = op; 605 do { 606 *--tp = codep->value; 607 codep = codep->next; 608 } while (--residue); 609 sp->dec_restart = 0; 610 } 611 612 bp = (unsigned char *)tif->tif_rawcp; 613 nbits = sp->lzw_nbits; 614 nextdata = sp->lzw_nextdata; 615 nextbits = sp->lzw_nextbits; 616 nbitsmask = sp->dec_nbitsmask; 617 oldcodep = sp->dec_oldcodep; 618 free_entp = sp->dec_free_entp; 619 maxcodep = sp->dec_maxcodep; 620 621 while (occ > 0) { 622 NextCode(tif, sp, bp, code, GetNextCodeCompat); 623 if (code == CODE_EOI) 624 break; 625 if (code == CODE_CLEAR) { 626 free_entp = sp->dec_codetab + CODE_FIRST; 627 _TIFFmemset(free_entp, 0, 628 (CSIZE - CODE_FIRST) * sizeof (code_t)); 629 nbits = BITS_MIN; 630 nbitsmask = MAXCODE(BITS_MIN); 631 maxcodep = sp->dec_codetab + nbitsmask; 632 NextCode(tif, sp, bp, code, GetNextCodeCompat); 633 if (code == CODE_EOI) 634 break; 635 if (code == CODE_CLEAR) { 636 TIFFErrorExt(tif->tif_clientdata, tif->tif_name, 637 "LZWDecode: Corrupted LZW table at scanline %d", 638 tif->tif_row); 639 return (0); 640 } 641 *op++ = code, occ--; 642 oldcodep = sp->dec_codetab + code; 643 continue; 644 } 645 codep = sp->dec_codetab + code; 646 647 /* 648 * Add the new entry to the code table. 649 */ 650 if (free_entp < &sp->dec_codetab[0] || 651 free_entp >= &sp->dec_codetab[CSIZE]) { 652 TIFFErrorExt(tif->tif_clientdata, tif->tif_name, 653 "LZWDecodeCompat: Corrupted LZW table at scanline %d", 654 tif->tif_row); 655 return (0); 656 } 657 658 free_entp->next = oldcodep; 659 if (free_entp->next < &sp->dec_codetab[0] || 660 free_entp->next >= &sp->dec_codetab[CSIZE]) { 661 TIFFErrorExt(tif->tif_clientdata, tif->tif_name, 662 "LZWDecodeCompat: Corrupted LZW table at scanline %d", 663 tif->tif_row); 664 return (0); 665 } 666 free_entp->firstchar = free_entp->next->firstchar; 667 free_entp->length = free_entp->next->length+1; 668 free_entp->value = (codep < free_entp) ? 669 codep->firstchar : free_entp->firstchar; 670 if (++free_entp > maxcodep) { 671 if (++nbits > BITS_MAX) /* should not happen */ 672 nbits = BITS_MAX; 673 nbitsmask = MAXCODE(nbits); 674 maxcodep = sp->dec_codetab + nbitsmask; 675 } 676 oldcodep = codep; 677 if (code >= 256) { 678 char *op_orig = op; 679 /* 680 * Code maps to a string, copy string 681 * value to output (written in reverse). 682 */ 683 if(codep->length == 0) { 684 TIFFErrorExt(tif->tif_clientdata, tif->tif_name, 685 "LZWDecodeCompat: Wrong length of decoded " 686 "string: data probably corrupted at scanline %d", 687 tif->tif_row); 688 return (0); 689 } 690 if (codep->length > occ) { 691 /* 692 * String is too long for decode buffer, 693 * locate portion that will fit, copy to 694 * the decode buffer, and setup restart 695 * logic for the next decoding call. 696 */ 697 sp->dec_codep = codep; 698 do { 699 codep = codep->next; 700 } while (codep->length > occ); 701 sp->dec_restart = occ; 702 tp = op + occ; 703 do { 704 *--tp = codep->value; 705 codep = codep->next; 706 } while (--occ); 707 break; 708 } 709 op += codep->length, occ -= codep->length; 710 tp = op; 711 do { 712 *--tp = codep->value; 713 } while( (codep = codep->next) != NULL && tp > op_orig); 714 } else 715 *op++ = code, occ--; 716 } 717 718 tif->tif_rawcp = (tidata_t) bp; 719 sp->lzw_nbits = nbits; 720 sp->lzw_nextdata = nextdata; 721 sp->lzw_nextbits = nextbits; 722 sp->dec_nbitsmask = nbitsmask; 723 sp->dec_oldcodep = oldcodep; 724 sp->dec_free_entp = free_entp; 725 sp->dec_maxcodep = maxcodep; 726 727 if (occ > 0) { 728 TIFFErrorExt(tif->tif_clientdata, tif->tif_name, 729 "LZWDecodeCompat: Not enough data at scanline %d (short %ld bytes)", 730 tif->tif_row, occ); 731 return (0); 732 } 733 return (1); 734} 735#endif /* LZW_COMPAT */ 736 737/* 738 * LZW Encoding. 739 */ 740 741static int 742LZWSetupEncode(TIFF* tif) 743{ 744 LZWCodecState* sp = EncoderState(tif); 745 static const char module[] = "LZWSetupEncode"; 746 747 assert(sp != NULL); 748 sp->enc_hashtab = (hash_t*) _TIFFmalloc(HSIZE*sizeof (hash_t)); 749 if (sp->enc_hashtab == NULL) { 750 TIFFErrorExt(tif->tif_clientdata, module, "No space for LZW hash table"); 751 return (0); 752 } 753 return (1); 754} 755 756/* 757 * Reset encoding state at the start of a strip. 758 */ 759static int 760LZWPreEncode(TIFF* tif, tsample_t s) 761{ 762 LZWCodecState *sp = EncoderState(tif); 763 764 (void) s; 765 assert(sp != NULL); 766 767 if( sp->enc_hashtab == NULL ) 768 { 769 tif->tif_setupencode( tif ); 770 } 771 772 sp->lzw_nbits = BITS_MIN; 773 sp->lzw_maxcode = MAXCODE(BITS_MIN); 774 sp->lzw_free_ent = CODE_FIRST; 775 sp->lzw_nextbits = 0; 776 sp->lzw_nextdata = 0; 777 sp->enc_checkpoint = CHECK_GAP; 778 sp->enc_ratio = 0; 779 sp->enc_incount = 0; 780 sp->enc_outcount = 0; 781 /* 782 * The 4 here insures there is space for 2 max-sized 783 * codes in LZWEncode and LZWPostDecode. 784 */ 785 sp->enc_rawlimit = tif->tif_rawdata + tif->tif_rawdatasize-1 - 4; 786 cl_hash(sp); /* clear hash table */ 787 sp->enc_oldcode = (hcode_t) -1; /* generates CODE_CLEAR in LZWEncode */ 788 return (1); 789} 790 791#define CALCRATIO(sp, rat) { \ 792 if (incount > 0x007fffff) { /* NB: shift will overflow */\ 793 rat = outcount >> 8; \ 794 rat = (rat == 0 ? 0x7fffffff : incount/rat); \ 795 } else \ 796 rat = (incount<<8) / outcount; \ 797} 798#define PutNextCode(op, c) { \ 799 nextdata = (nextdata << nbits) | c; \ 800 nextbits += nbits; \ 801 *op++ = (unsigned char)(nextdata >> (nextbits-8)); \ 802 nextbits -= 8; \ 803 if (nextbits >= 8) { \ 804 *op++ = (unsigned char)(nextdata >> (nextbits-8)); \ 805 nextbits -= 8; \ 806 } \ 807 outcount += nbits; \ 808} 809 810/* 811 * Encode a chunk of pixels. 812 * 813 * Uses an open addressing double hashing (no chaining) on the 814 * prefix code/next character combination. We do a variant of 815 * Knuth's algorithm D (vol. 3, sec. 6.4) along with G. Knott's 816 * relatively-prime secondary probe. Here, the modular division 817 * first probe is gives way to a faster exclusive-or manipulation. 818 * Also do block compression with an adaptive reset, whereby the 819 * code table is cleared when the compression ratio decreases, 820 * but after the table fills. The variable-length output codes 821 * are re-sized at this point, and a CODE_CLEAR is generated 822 * for the decoder. 823 */ 824static int 825LZWEncode(TIFF* tif, tidata_t bp, tsize_t cc, tsample_t s) 826{ 827 register LZWCodecState *sp = EncoderState(tif); 828 register long fcode; 829 register hash_t *hp; 830 register int h, c; 831 hcode_t ent; 832 long disp; 833 long incount, outcount, checkpoint; 834 long nextdata, nextbits; 835 int free_ent, maxcode, nbits; 836 tidata_t op, limit; 837 838 (void) s; 839 if (sp == NULL) 840 return (0); 841 842 assert(sp->enc_hashtab != NULL); 843 844 /* 845 * Load local state. 846 */ 847 incount = sp->enc_incount; 848 outcount = sp->enc_outcount; 849 checkpoint = sp->enc_checkpoint; 850 nextdata = sp->lzw_nextdata; 851 nextbits = sp->lzw_nextbits; 852 free_ent = sp->lzw_free_ent; 853 maxcode = sp->lzw_maxcode; 854 nbits = sp->lzw_nbits; 855 op = tif->tif_rawcp; 856 limit = sp->enc_rawlimit; 857 ent = sp->enc_oldcode; 858 859 if (ent == (hcode_t) -1 && cc > 0) { 860 /* 861 * NB: This is safe because it can only happen 862 * at the start of a strip where we know there 863 * is space in the data buffer. 864 */ 865 PutNextCode(op, CODE_CLEAR); 866 ent = *bp++; cc--; incount++; 867 } 868 while (cc > 0) { 869 c = *bp++; cc--; incount++; 870 fcode = ((long)c << BITS_MAX) + ent; 871 h = (c << HSHIFT) ^ ent; /* xor hashing */ 872#ifdef _WINDOWS 873 /* 874 * Check hash index for an overflow. 875 */ 876 if (h >= HSIZE) 877 h -= HSIZE; 878#endif 879 hp = &sp->enc_hashtab[h]; 880 if (hp->hash == fcode) { 881 ent = hp->code; 882 continue; 883 } 884 if (hp->hash >= 0) { 885 /* 886 * Primary hash failed, check secondary hash. 887 */ 888 disp = HSIZE - h; 889 if (h == 0) 890 disp = 1; 891 do { 892 /* 893 * Avoid pointer arithmetic 'cuz of 894 * wraparound problems with segments. 895 */ 896 if ((h -= disp) < 0) 897 h += HSIZE; 898 hp = &sp->enc_hashtab[h]; 899 if (hp->hash == fcode) { 900 ent = hp->code; 901 goto hit; 902 } 903 } while (hp->hash >= 0); 904 } 905 /* 906 * New entry, emit code and add to table. 907 */ 908 /* 909 * Verify there is space in the buffer for the code 910 * and any potential Clear code that might be emitted 911 * below. The value of limit is setup so that there 912 * are at least 4 bytes free--room for 2 codes. 913 */ 914 if (op > limit) { 915 tif->tif_rawcc = (tsize_t)(op - tif->tif_rawdata); 916 TIFFFlushData1(tif); 917 op = tif->tif_rawdata; 918 } 919 PutNextCode(op, ent); 920 ent = c; 921 hp->code = free_ent++; 922 hp->hash = fcode; 923 if (free_ent == CODE_MAX-1) { 924 /* table is full, emit clear code and reset */ 925 cl_hash(sp); 926 sp->enc_ratio = 0; 927 incount = 0; 928 outcount = 0; 929 free_ent = CODE_FIRST; 930 PutNextCode(op, CODE_CLEAR); 931 nbits = BITS_MIN; 932 maxcode = MAXCODE(BITS_MIN); 933 } else { 934 /* 935 * If the next entry is going to be too big for 936 * the code size, then increase it, if possible. 937 */ 938 if (free_ent > maxcode) { 939 nbits++; 940 assert(nbits <= BITS_MAX); 941 maxcode = (int) MAXCODE(nbits); 942 } else if (incount >= checkpoint) { 943 long rat; 944 /* 945 * Check compression ratio and, if things seem 946 * to be slipping, clear the hash table and 947 * reset state. The compression ratio is a 948 * 24+8-bit fractional number. 949 */ 950 checkpoint = incount+CHECK_GAP; 951 CALCRATIO(sp, rat); 952 if (rat <= sp->enc_ratio) { 953 cl_hash(sp); 954 sp->enc_ratio = 0; 955 incount = 0; 956 outcount = 0; 957 free_ent = CODE_FIRST; 958 PutNextCode(op, CODE_CLEAR); 959 nbits = BITS_MIN; 960 maxcode = MAXCODE(BITS_MIN); 961 } else 962 sp->enc_ratio = rat; 963 } 964 } 965 hit: 966 ; 967 } 968 969 /* 970 * Restore global state. 971 */ 972 sp->enc_incount = incount; 973 sp->enc_outcount = outcount; 974 sp->enc_checkpoint = checkpoint; 975 sp->enc_oldcode = ent; 976 sp->lzw_nextdata = nextdata; 977 sp->lzw_nextbits = nextbits; 978 sp->lzw_free_ent = free_ent; 979 sp->lzw_maxcode = maxcode; 980 sp->lzw_nbits = nbits; 981 tif->tif_rawcp = op; 982 return (1); 983} 984 985/* 986 * Finish off an encoded strip by flushing the last 987 * string and tacking on an End Of Information code. 988 */ 989static int 990LZWPostEncode(TIFF* tif) 991{ 992 register LZWCodecState *sp = EncoderState(tif); 993 tidata_t op = tif->tif_rawcp; 994 long nextbits = sp->lzw_nextbits; 995 long nextdata = sp->lzw_nextdata; 996 long outcount = sp->enc_outcount; 997 int nbits = sp->lzw_nbits; 998 999 if (op > sp->enc_rawlimit) { 1000 tif->tif_rawcc = (tsize_t)(op - tif->tif_rawdata); 1001 TIFFFlushData1(tif); 1002 op = tif->tif_rawdata; 1003 } 1004 if (sp->enc_oldcode != (hcode_t) -1) { 1005 PutNextCode(op, sp->enc_oldcode); 1006 sp->enc_oldcode = (hcode_t) -1; 1007 } 1008 PutNextCode(op, CODE_EOI); 1009 if (nextbits > 0) 1010 *op++ = (unsigned char)(nextdata << (8-nextbits)); 1011 tif->tif_rawcc = (tsize_t)(op - tif->tif_rawdata); 1012 return (1); 1013} 1014 1015/* 1016 * Reset encoding hash table. 1017 */ 1018static void 1019cl_hash(LZWCodecState* sp) 1020{ 1021 register hash_t *hp = &sp->enc_hashtab[HSIZE-1]; 1022 register long i = HSIZE-8; 1023 1024 do { 1025 i -= 8; 1026 hp[-7].hash = -1; 1027 hp[-6].hash = -1; 1028 hp[-5].hash = -1; 1029 hp[-4].hash = -1; 1030 hp[-3].hash = -1; 1031 hp[-2].hash = -1; 1032 hp[-1].hash = -1; 1033 hp[ 0].hash = -1; 1034 hp -= 8; 1035 } while (i >= 0); 1036 for (i += 8; i > 0; i--, hp--) 1037 hp->hash = -1; 1038} 1039 1040static void 1041LZWCleanup(TIFF* tif) 1042{ 1043 (void)TIFFPredictorCleanup(tif); 1044 1045 assert(tif->tif_data != 0); 1046 1047 if (DecoderState(tif)->dec_codetab) 1048 _TIFFfree(DecoderState(tif)->dec_codetab); 1049 1050 if (EncoderState(tif)->enc_hashtab) 1051 _TIFFfree(EncoderState(tif)->enc_hashtab); 1052 1053 _TIFFfree(tif->tif_data); 1054 tif->tif_data = NULL; 1055 1056 _TIFFSetDefaultCompressionState(tif); 1057} 1058 1059int 1060TIFFInitLZW(TIFF* tif, int scheme) 1061{ 1062 assert(scheme == COMPRESSION_LZW); 1063 /* 1064 * Allocate state block so tag methods have storage to record values. 1065 */ 1066 tif->tif_data = (tidata_t) _TIFFmalloc(sizeof (LZWCodecState)); 1067 if (tif->tif_data == NULL) 1068 goto bad; 1069 DecoderState(tif)->dec_codetab = NULL; 1070 DecoderState(tif)->dec_decode = NULL; 1071 EncoderState(tif)->enc_hashtab = NULL; 1072 LZWState(tif)->rw_mode = tif->tif_mode; 1073 1074 /* 1075 * Install codec methods. 1076 */ 1077 tif->tif_setupdecode = LZWSetupDecode; 1078 tif->tif_predecode = LZWPreDecode; 1079 tif->tif_decoderow = LZWDecode; 1080 tif->tif_decodestrip = LZWDecode; 1081 tif->tif_decodetile = LZWDecode; 1082 tif->tif_setupencode = LZWSetupEncode; 1083 tif->tif_preencode = LZWPreEncode; 1084 tif->tif_postencode = LZWPostEncode; 1085 tif->tif_encoderow = LZWEncode; 1086 tif->tif_encodestrip = LZWEncode; 1087 tif->tif_encodetile = LZWEncode; 1088 tif->tif_cleanup = LZWCleanup; 1089 /* 1090 * Setup predictor setup. 1091 */ 1092 (void) TIFFPredictorInit(tif); 1093 return (1); 1094bad: 1095 TIFFErrorExt(tif->tif_clientdata, "TIFFInitLZW", 1096 "No space for LZW state block"); 1097 return (0); 1098} 1099 1100/* 1101 * Copyright (c) 1985, 1986 The Regents of the University of California. 1102 * All rights reserved. 1103 * 1104 * This code is derived from software contributed to Berkeley by 1105 * James A. Woods, derived from original work by Spencer Thomas 1106 * and Joseph Orost. 1107 * 1108 * Redistribution and use in source and binary forms are permitted 1109 * provided that the above copyright notice and this paragraph are 1110 * duplicated in all such forms and that any documentation, 1111 * advertising materials, and other materials related to such 1112 * distribution and use acknowledge that the software was developed 1113 * by the University of California, Berkeley. The name of the 1114 * University may not be used to endorse or promote products derived 1115 * from this software without specific prior written permission. 1116 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR 1117 * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED 1118 * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE. 1119 */ 1120#endif /* LZW_SUPPORT */ 1121 1122/* vim: set ts=8 sts=8 sw=8 noet: */ 1123/* 1124 * Local Variables: 1125 * mode: c 1126 * c-basic-offset: 8 1127 * fill-column: 78 1128 * End: 1129 */ 1130