thirdparty/libtiff/tif_lzw.c

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