src/tiff/tif_lzw.c

   1 /* $Header$ */
   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 <assert.h>
  42 #include <stdio.h>
  43
  44 /*
  45  * NB: The 5.0 spec describes a different algorithm than Aldus
  46  *     implements.  Specifically, Aldus does code length transitions
  47  *     one code earlier than should be done (for real LZW).
  48  *     Earlier versions of this library implemented the correct
  49  *     LZW algorithm, but emitted codes in a bit order opposite
  50  *     to the TIFF spec.  Thus, to maintain compatibility w/ Aldus
  51  *     we interpret MSB-LSB ordered codes to be images written w/
  52  *     old versions of this library, but otherwise adhere to the
  53  *     Aldus "off by one" algorithm.
  54  *
  55  * Future revisions to the TIFF spec are expected to "clarify this issue".
  56  */
  57 #define LZW_COMPAT              /* include backwards compatibility code */
  58 /*
  59  * Each strip of data is supposed to be terminated by a CODE_EOI.
  60  * If the following #define is included, the decoder will also
  61  * check for end-of-strip w/o seeing this code.  This makes the
  62  * library more robust, but also slower.
  63  */
  64 #define LZW_CHECKEOS            /* include checks for strips w/o EOI code */
  65
  66 #define MAXCODE(n)      ((1L<<(n))-1)
  67 /*
  68  * The TIFF spec specifies that encoded bit
  69  * strings range from 9 to 12 bits.
  70  */
  71 #define BITS_MIN        9               /* start with 9 bits */
  72 #define BITS_MAX        12              /* max of 12 bit strings */
  73 /* predefined codes */
  74 #define CODE_CLEAR      256             /* code to clear string table */
  75 #define CODE_EOI        257             /* end-of-information code */
  76 #define CODE_FIRST      258             /* first free code entry */
  77 #define CODE_MAX        MAXCODE(BITS_MAX)
  78 #define HSIZE           9001L           /* 91% occupancy */
  79 #define HSHIFT          (13-8)
  80 #ifdef LZW_COMPAT
  81 /* NB: +1024 is for compatibility with old files */
  82 #define CSIZE           (MAXCODE(BITS_MAX)+1024L)
  83 #else
  84 #define CSIZE           (MAXCODE(BITS_MAX)+1L)
  85 #endif
  86
  87 /*
  88  * State block for each open TIFF file using LZW
  89  * compression/decompression.  Note that the predictor
  90  * state block must be first in this data structure.
  91  */
  92 typedef struct {
  93         TIFFPredictorState predict;     /* predictor super class */
  94
  95         u_short         nbits;          /* # of bits/code */
  96         u_short         maxcode;        /* maximum code for lzw_nbits */
  97         u_short         free_ent;       /* next free entry in hash table */
  98         long            nextdata;       /* next bits of i/o */
  99         long            nextbits;       /* # of valid bits in lzw_nextdata */
 100 } LZWBaseState;
 101
 102 #define lzw_nbits       base.nbits
 103 #define lzw_maxcode     base.maxcode
 104 #define lzw_free_ent    base.free_ent
 105 #define lzw_nextdata    base.nextdata
 106 #define lzw_nextbits    base.nextbits
 107
 108 /*
 109  * Encoding-specific state.
 110  */
 111 typedef uint16 hcode_t;                 /* codes fit in 16 bits */
 112
 113 /*
 114  * Decoding-specific state.
 115  */
 116 typedef struct code_ent {
 117         struct code_ent *next;
 118         u_short length;                 /* string len, including this token */
 119         u_char  value;                  /* data value */
 120         u_char  firstchar;              /* first token of string */
 121 } code_t;
 122
 123 typedef int (*decodeFunc)(TIFF*, tidata_t, tsize_t, tsample_t);
 124
 125 typedef struct {
 126         LZWBaseState base;
 127
 128         /* Decoding specific data */
 129         long    dec_nbitsmask;          /* lzw_nbits 1 bits, right adjusted */
 130         long    dec_restart;            /* restart count */
 131 #ifdef LZW_CHECKEOS
 132         long    dec_bitsleft;           /* available bits in raw data */
 133 #endif
 134         decodeFunc dec_decode;          /* regular or backwards compatible */
 135         code_t* dec_codep;              /* current recognized code */
 136         code_t* dec_oldcodep;           /* previously recognized code */
 137         code_t* dec_free_entp;          /* next free entry */
 138         code_t* dec_maxcodep;           /* max available entry */
 139         code_t* dec_codetab;            /* kept separate for small machines */
 140 } LZWCodecState;
 141
 142 #define LZWState(tif)           ((LZWBaseState*) (tif)->tif_data)
 143 #define DecoderState(tif)       ((LZWCodecState*) LZWState(tif))
 144
 145 static  int LZWDecode(TIFF*, tidata_t, tsize_t, tsample_t);
 146 #ifdef LZW_COMPAT
 147 static  int LZWDecodeCompat(TIFF*, tidata_t, tsize_t, tsample_t);
 148 #endif
 149
 150 /*
 151  * LZW Decoder.
 152  */
 153
 154 #ifdef LZW_CHECKEOS
 155 /*
 156  * This check shouldn't be necessary because each
 157  * strip is suppose to be terminated with CODE_EOI.
 158  */
 159 #define NextCode(_tif, _sp, _bp, _code, _get) {                         \
 160         if ((_sp)->dec_bitsleft < nbits) {                              \
 161                 TIFFWarning(_tif->tif_name,                             \
 162                     "LZWDecode: Strip %d not terminated with EOI code", \
 163                     _tif->tif_curstrip);                                \
 164                 _code = CODE_EOI;                                       \
 165         } else {                                                        \
 166                 _get(_sp,_bp,_code);                                    \
 167                 (_sp)->dec_bitsleft -= nbits;                           \
 168         }                                                               \
 169 }
 170 #else
 171 #define NextCode(tif, sp, bp, code, get) get(sp, bp, code)
 172 #endif
 173
 174 static int
 175 LZWSetupDecode(TIFF* tif)
 176 {
 177         LZWCodecState* sp = DecoderState(tif);
 178         static const char module[] = "LZWSetupDecode";
 179         int code;
 180
 181         assert(sp != NULL);
 182
 183         if (sp->dec_codetab == NULL) {
 184                 sp->dec_codetab = (code_t*)_TIFFmalloc(CSIZE*sizeof (code_t));
 185                 if (sp->dec_codetab == NULL) {
 186                         TIFFError(module, "No space for LZW code table");
 187                         return (0);
 188                 }
 189                 /*
 190                  * Pre-load the table.
 191                  */
 192                 code = 255;
 193                 do {
 194                     sp->dec_codetab[code].value = (u_char) code;
 195                     sp->dec_codetab[code].firstchar = (u_char) code;
 196                     sp->dec_codetab[code].length = 1;
 197                     sp->dec_codetab[code].next = NULL;
 198                 } while (code--);
 199         }
 200         return (1);
 201 }
 202
 203 /*
 204  * Setup state for decoding a strip.
 205  */
 206 static int
 207 LZWPreDecode(TIFF* tif, tsample_t s)
 208 {
 209         LZWCodecState *sp = DecoderState(tif);
 210
 211         (void) s;
 212         assert(sp != NULL);
 213         /*
 214          * Check for old bit-reversed codes.
 215          */
 216         if (tif->tif_rawdata[0] == 0 && (tif->tif_rawdata[1] & 0x1)) {
 217 #ifdef LZW_COMPAT
 218                 if (!sp->dec_decode) {
 219                         TIFFWarning(tif->tif_name,
 220                             "Old-style LZW codes, convert file");
 221                         /*
 222                          * Override default decoding methods with
 223                          * ones that deal with the old coding.
 224                          * Otherwise the predictor versions set
 225                          * above will call the compatibility routines
 226                          * through the dec_decode method.
 227                          */
 228                         tif->tif_decoderow = LZWDecodeCompat;
 229                         tif->tif_decodestrip = LZWDecodeCompat;
 230                         tif->tif_decodetile = LZWDecodeCompat;
 231                         /*
 232                          * If doing horizontal differencing, must
 233                          * re-setup the predictor logic since we
 234                          * switched the basic decoder methods...
 235                          */
 236                         (*tif->tif_setupdecode)(tif);
 237                         sp->dec_decode = LZWDecodeCompat;
 238                 }
 239                 sp->lzw_maxcode = MAXCODE(BITS_MIN);
 240 #else /* !LZW_COMPAT */
 241                 if (!sp->dec_decode) {
 242                         TIFFError(tif->tif_name,
 243                             "Old-style LZW codes not supported");
 244                         sp->dec_decode = LZWDecode;
 245                 }
 246                 return (0);
 247 #endif/* !LZW_COMPAT */
 248         } else {
 249                 sp->lzw_maxcode = MAXCODE(BITS_MIN)-1;
 250                 sp->dec_decode = LZWDecode;
 251         }
 252         sp->lzw_nbits = BITS_MIN;
 253         sp->lzw_nextbits = 0;
 254         sp->lzw_nextdata = 0;
 255
 256         sp->dec_restart = 0;
 257         sp->dec_nbitsmask = MAXCODE(BITS_MIN);
 258 #ifdef LZW_CHECKEOS
 259         sp->dec_bitsleft = tif->tif_rawcc << 3;
 260 #endif
 261         sp->dec_free_entp = sp->dec_codetab + CODE_FIRST;
 262         /*
 263          * Zero entries that are not yet filled in.  We do
 264          * this to guard against bogus input data that causes
 265          * us to index into undefined entries.  If you can
 266          * come up with a way to safely bounds-check input codes
 267          * while decoding then you can remove this operation.
 268          */
 269         _TIFFmemset(sp->dec_free_entp, 0, (CSIZE-CODE_FIRST)*sizeof (code_t));
 270         sp->dec_oldcodep = &sp->dec_codetab[-1];
 271         sp->dec_maxcodep = &sp->dec_codetab[sp->dec_nbitsmask-1];
 272         return (1);
 273 }
 274
 275 /*
 276  * Decode a "hunk of data".
 277  */
 278 #define GetNextCode(sp, bp, code) {                             \
 279         nextdata = (nextdata<<8) | *(bp)++;                     \
 280         nextbits += 8;                                          \
 281         if (nextbits < nbits) {                                 \
 282                 nextdata = (nextdata<<8) | *(bp)++;             \
 283                 nextbits += 8;                                  \
 284         }                                                       \
 285         code = (hcode_t)((nextdata >> (nextbits-nbits)) & nbitsmask);   \
 286         nextbits -= nbits;                                      \
 287 }
 288
 289 static void
 290 codeLoop(TIFF* tif)
 291 {
 292         TIFFError(tif->tif_name,
 293             "LZWDecode: Bogus encoding, loop in the code table; scanline %d",
 294             tif->tif_row);
 295 }
 296
 297 static int
 298 LZWDecode(TIFF* tif, tidata_t op0, tsize_t occ0, tsample_t s)
 299 {
 300         LZWCodecState *sp = DecoderState(tif);
 301         char *op = (char*) op0;
 302         long occ = (long) occ0;
 303         char *tp;
 304         u_char *bp;
 305         hcode_t code;
 306         int len;
 307         long nbits, nextbits, nextdata, nbitsmask;
 308         code_t *codep, *free_entp, *maxcodep, *oldcodep;
 309
 310         (void) s;
 311         assert(sp != NULL);
 312         /*
 313          * Restart interrupted output operation.
 314          */
 315         if (sp->dec_restart) {
 316                 long residue;
 317
 318                 codep = sp->dec_codep;
 319                 residue = codep->length - sp->dec_restart;
 320                 if (residue > occ) {
 321                         /*
 322                          * Residue from previous decode is sufficient
 323                          * to satisfy decode request.  Skip to the
 324                          * start of the decoded string, place decoded
 325                          * values in the output buffer, and return.
 326                          */
 327                         sp->dec_restart += occ;
 328                         do {
 329                                 codep = codep->next;
 330                         } while (--residue > occ && codep);
 331                         if (codep) {
 332                                 tp = op + occ;
 333                                 do {
 334                                         *--tp = codep->value;
 335                                         codep = codep->next;
 336                                 } while (--occ && codep);
 337                         }
 338                         return (1);
 339                 }
 340                 /*
 341                  * Residue satisfies only part of the decode request.
 342                  */
 343                 op += residue, occ -= residue;
 344                 tp = op;
 345                 do {
 346                         int t;
 347                         --tp;
 348                         t = codep->value;
 349                         codep = codep->next;
 350                         *tp = (char) t;
 351                 } while (--residue && codep);
 352                 sp->dec_restart = 0;
 353         }
 354
 355         bp = (u_char *)tif->tif_rawcp;
 356         nbits = sp->lzw_nbits;
 357         nextdata = sp->lzw_nextdata;
 358         nextbits = sp->lzw_nextbits;
 359         nbitsmask = sp->dec_nbitsmask;
 360         oldcodep = sp->dec_oldcodep;
 361         free_entp = sp->dec_free_entp;
 362         maxcodep = sp->dec_maxcodep;
 363
 364         while (occ > 0) {
 365                 NextCode(tif, sp, bp, code, GetNextCode);
 366                 if (code == CODE_EOI)
 367                         break;
 368                 if (code == CODE_CLEAR) {
 369                         free_entp = sp->dec_codetab + CODE_FIRST;
 370                         nbits = BITS_MIN;
 371                         nbitsmask = MAXCODE(BITS_MIN);
 372                         maxcodep = sp->dec_codetab + nbitsmask-1;
 373                         NextCode(tif, sp, bp, code, GetNextCode);
 374                         if (code == CODE_EOI)
 375                                 break;
 376                         *op++ = (char)code, occ--;
 377                         oldcodep = sp->dec_codetab + code;
 378                         continue;
 379                 }
 380                 codep = sp->dec_codetab + code;
 381
 382                 /*
 383                  * Add the new entry to the code table.
 384                  */
 385                 if (free_entp < &sp->dec_codetab[0] ||
 386                         free_entp >= &sp->dec_codetab[CSIZE]) {
 387                         TIFFError(tif->tif_name,
 388                         "LZWDecode: Corrupted LZW table at scanline %d",
 389                         tif->tif_row);
 390                         return (0);
 391                 }
 392
 393                 free_entp->next = oldcodep;
 394                 if (free_entp->next < &sp->dec_codetab[0] ||
 395                         free_entp->next >= &sp->dec_codetab[CSIZE]) {
 396                         TIFFError(tif->tif_name,
 397                         "LZWDecode: Corrupted LZW table at scanline %d",
 398                         tif->tif_row);
 399                         return (0);
 400                 }
 401                 free_entp->firstchar = free_entp->next->firstchar;
 402                 free_entp->length = free_entp->next->length+1;
 403                 free_entp->value = (codep < free_entp) ?
 404                     codep->firstchar : free_entp->firstchar;
 405                 if (++free_entp > maxcodep) {
 406                         if (++nbits > BITS_MAX)         /* should not happen */
 407                                 nbits = BITS_MAX;
 408                         nbitsmask = MAXCODE(nbits);
 409                         maxcodep = sp->dec_codetab + nbitsmask-1;
 410                 }
 411                 oldcodep = codep;
 412                 if (code >= 256) {
 413                         /*
 414                          * Code maps to a string, copy string
 415                          * value to output (written in reverse).
 416                          */
 417                         if(codep->length == 0) {
 418                             TIFFError(tif->tif_name,
 419                             "LZWDecode: Wrong length of decoded string: "
 420                             "data probably corrupted at scanline %d",
 421                             tif->tif_row);
 422                             return (0);
 423                         }
 424                         if (codep->length > occ) {
 425                                 /*
 426                                  * String is too long for decode buffer,
 427                                  * locate portion that will fit, copy to
 428                                  * the decode buffer, and setup restart
 429                                  * logic for the next decoding call.
 430                                  */
 431                                 sp->dec_codep = codep;
 432                                 do {
 433                                         codep = codep->next;
 434                                 } while (codep && codep->length > occ);
 435                                 if (codep) {
 436                                         sp->dec_restart = occ;
 437                                         tp = op + occ;
 438                                         do  {
 439                                                 *--tp = codep->value;
 440                                                 codep = codep->next;
 441                                         }  while (--occ && codep);
 442                                         if (codep)
 443                                                 codeLoop(tif);
 444                                 }
 445                                 break;
 446                         }
 447                         len = codep->length;
 448                         tp = op + len;
 449                         do {
 450                                 int t;
 451                                 --tp;
 452                                 t = codep->value;
 453                                 codep = codep->next;
 454                                 *tp = (char) t;
 455                         } while (codep && tp > op);
 456                         if (codep) {
 457                             codeLoop(tif);
 458                             break;
 459                         }
 460                         op += len, occ -= len;
 461                 } else
 462                         *op++ = (char)code, occ--;
 463         }
 464
 465         tif->tif_rawcp = (tidata_t) bp;
 466         sp->lzw_nbits = (u_short) nbits;
 467         sp->lzw_nextdata = nextdata;
 468         sp->lzw_nextbits = nextbits;
 469         sp->dec_nbitsmask = nbitsmask;
 470         sp->dec_oldcodep = oldcodep;
 471         sp->dec_free_entp = free_entp;
 472         sp->dec_maxcodep = maxcodep;
 473
 474         if (occ > 0) {
 475                 TIFFError(tif->tif_name,
 476                 "LZWDecode: Not enough data at scanline %d (short %d bytes)",
 477                     tif->tif_row, occ);
 478                 return (0);
 479         }
 480         return (1);
 481 }
 482
 483 #ifdef LZW_COMPAT
 484 /*
 485  * Decode a "hunk of data" for old images.
 486  */
 487 #define GetNextCodeCompat(sp, bp, code) {                       \
 488         nextdata |= (u_long) *(bp)++ << nextbits;               \
 489         nextbits += 8;                                          \
 490         if (nextbits < nbits) {                                 \
 491                 nextdata |= (u_long) *(bp)++ << nextbits;       \
 492                 nextbits += 8;                                  \
 493         }                                                       \
 494         code = (hcode_t)(nextdata & nbitsmask);                 \
 495         nextdata >>= nbits;                                     \
 496         nextbits -= nbits;                                      \
 497 }
 498
 499 static int
 500 LZWDecodeCompat(TIFF* tif, tidata_t op0, tsize_t occ0, tsample_t s)
 501 {
 502         LZWCodecState *sp = DecoderState(tif);
 503         char *op = (char*) op0;
 504         long occ = (long) occ0;
 505         char *tp;
 506         u_char *bp;
 507         int code, nbits;
 508         long nextbits, nextdata, nbitsmask;
 509         code_t *codep, *free_entp, *maxcodep, *oldcodep;
 510
 511         (void) s;
 512         assert(sp != NULL);
 513         /*
 514          * Restart interrupted output operation.
 515          */
 516         if (sp->dec_restart) {
 517                 long residue;
 518
 519                 codep = sp->dec_codep;
 520                 residue = codep->length - sp->dec_restart;
 521                 if (residue > occ) {
 522                         /*
 523                          * Residue from previous decode is sufficient
 524                          * to satisfy decode request.  Skip to the
 525                          * start of the decoded string, place decoded
 526                          * values in the output buffer, and return.
 527                          */
 528                         sp->dec_restart += occ;
 529                         do {
 530                                 codep = codep->next;
 531                         } while (--residue > occ);
 532                         tp = op + occ;
 533                         do {
 534                                 *--tp = codep->value;
 535                                 codep = codep->next;
 536                         } while (--occ);
 537                         return (1);
 538                 }
 539                 /*
 540                  * Residue satisfies only part of the decode request.
 541                  */
 542                 op += residue, occ -= residue;
 543                 tp = op;
 544                 do {
 545                         *--tp = codep->value;
 546                         codep = codep->next;
 547                 } while (--residue);
 548                 sp->dec_restart = 0;
 549         }
 550
 551         bp = (u_char *)tif->tif_rawcp;
 552         nbits = sp->lzw_nbits;
 553         nextdata = sp->lzw_nextdata;
 554         nextbits = sp->lzw_nextbits;
 555         nbitsmask = sp->dec_nbitsmask;
 556         oldcodep = sp->dec_oldcodep;
 557         free_entp = sp->dec_free_entp;
 558         maxcodep = sp->dec_maxcodep;
 559
 560         while (occ > 0) {
 561                 NextCode(tif, sp, bp, code, GetNextCodeCompat);
 562                 if (code == CODE_EOI)
 563                         break;
 564                 if (code == CODE_CLEAR) {
 565                         free_entp = sp->dec_codetab + CODE_FIRST;
 566                         nbits = BITS_MIN;
 567                         nbitsmask = MAXCODE(BITS_MIN);
 568                         maxcodep = sp->dec_codetab + nbitsmask;
 569                         NextCode(tif, sp, bp, code, GetNextCodeCompat);
 570                         if (code == CODE_EOI)
 571                                 break;
 572                         *op++ = (char) code, occ--;
 573                         oldcodep = sp->dec_codetab + code;
 574                         continue;
 575                 }
 576                 codep = sp->dec_codetab + code;
 577
 578                 /*
 579                  * Add the new entry to the code table.
 580                  */
 581                 if (free_entp < &sp->dec_codetab[0] ||
 582                         free_entp >= &sp->dec_codetab[CSIZE]) {
 583                         TIFFError(tif->tif_name,
 584                         "LZWDecodeCompat: Corrupted LZW table at scanline %d",
 585                         tif->tif_row);
 586                         return (0);
 587                 }
 588
 589                 free_entp->next = oldcodep;
 590                 if (free_entp->next < &sp->dec_codetab[0] ||
 591                         free_entp->next >= &sp->dec_codetab[CSIZE]) {
 592                         TIFFError(tif->tif_name,
 593                         "LZWDecodeCompat: Corrupted LZW table at scanline %d",
 594                         tif->tif_row);
 595                         return (0);
 596                 }
 597                 free_entp->firstchar = free_entp->next->firstchar;
 598                 free_entp->length = free_entp->next->length+1;
 599                 free_entp->value = (codep < free_entp) ?
 600                     codep->firstchar : free_entp->firstchar;
 601                 if (++free_entp > maxcodep) {
 602                         if (++nbits > BITS_MAX)         /* should not happen */
 603                                 nbits = BITS_MAX;
 604                         nbitsmask = MAXCODE(nbits);
 605                         maxcodep = sp->dec_codetab + nbitsmask;
 606                 }
 607                 oldcodep = codep;
 608                 if (code >= 256) {
 609                         /*
 610                          * Code maps to a string, copy string
 611                          * value to output (written in reverse).
 612                          */
 613                         if(codep->length == 0) {
 614                             TIFFError(tif->tif_name,
 615                             "LZWDecodeCompat: Wrong length of decoded "
 616                             "string: data probably corrupted at scanline %d",
 617                             tif->tif_row);
 618                             return (0);
 619                         }
 620                         if (codep->length > occ) {
 621                                 /*
 622                                  * String is too long for decode buffer,
 623                                  * locate portion that will fit, copy to
 624                                  * the decode buffer, and setup restart
 625                                  * logic for the next decoding call.
 626                                  */
 627                                 sp->dec_codep = codep;
 628                                 do {
 629                                         codep = codep->next;
 630                                 } while (codep->length > occ);
 631                                 sp->dec_restart = occ;
 632                                 tp = op + occ;
 633                                 do  {
 634                                         *--tp = codep->value;
 635                                         codep = codep->next;
 636                                 }  while (--occ);
 637                                 break;
 638                         }
 639                         op += codep->length, occ -= codep->length;
 640                         tp = op;
 641                         do {
 642                                 *--tp = codep->value;
 643                         } while( (codep = codep->next) != NULL);
 644                 } else
 645                         *op++ = (char) code, occ--;
 646         }
 647
 648         tif->tif_rawcp = (tidata_t) bp;
 649         sp->lzw_nbits = (u_short) nbits;
 650         sp->lzw_nextdata = nextdata;
 651         sp->lzw_nextbits = nextbits;
 652         sp->dec_nbitsmask = nbitsmask;
 653         sp->dec_oldcodep = oldcodep;
 654         sp->dec_free_entp = free_entp;
 655         sp->dec_maxcodep = maxcodep;
 656
 657         if (occ > 0) {
 658                 TIFFError(tif->tif_name,
 659             "LZWDecodeCompat: Not enough data at scanline %d (short %d bytes)",
 660                     tif->tif_row, occ);
 661                 return (0);
 662         }
 663         return (1);
 664 }
 665 #endif /* LZW_COMPAT */
 666
 667
 668
 669 static void
 670 LZWCleanup(TIFF* tif)
 671 {
 672     if (tif->tif_data) {
 673         if (DecoderState(tif)->dec_codetab)
 674             _TIFFfree(DecoderState(tif)->dec_codetab);
 675         _TIFFfree(tif->tif_data);
 676         tif->tif_data = NULL;
 677     }
 678 }
 679
 680 static int
 681 LZWSetupEncode(TIFF* tif)
 682 {
 683     TIFFError(tif->tif_name,
 684               "LZW compression is not available to due to Unisys patent enforcement");
 685     return (0);
 686 }
 687
 688 int
 689 TIFFInitLZW(TIFF* tif, int scheme)
 690 {
 691         assert(scheme == COMPRESSION_LZW);
 692
 693         /*
 694          * Allocate state block so tag methods have storage to record values.
 695          */
 696         tif->tif_data = (tidata_t) _TIFFmalloc(sizeof (LZWCodecState));
 697         if (tif->tif_data == NULL)
 698                 goto bad;
 699         DecoderState(tif)->dec_codetab = NULL;
 700         DecoderState(tif)->dec_decode = NULL;
 701
 702         /*
 703          * Install codec methods.
 704          */
 705         tif->tif_setupencode = LZWSetupEncode;
 706         tif->tif_setupdecode = LZWSetupDecode;
 707         tif->tif_predecode = LZWPreDecode;
 708         tif->tif_decoderow = LZWDecode;
 709         tif->tif_decodestrip = LZWDecode;
 710         tif->tif_decodetile = LZWDecode;
 711         tif->tif_cleanup = LZWCleanup;
 712
 713         /*
 714          * Setup predictor setup.
 715          */
 716         (void) TIFFPredictorInit(tif);
 717
 718         return (1);
 719
 720 bad:
 721         TIFFError("TIFFInitLZW", "No space for LZW state block");
 722         return (0);
 723 }
 724
 725 /*
 726  * Copyright (c) 1985, 1986 The Regents of the University of California.
 727  * All rights reserved.
 728  *
 729  * This code is derived from software contributed to Berkeley by
 730  * James A. Woods, derived from original work by Spencer Thomas
 731  * and Joseph Orost.
 732  *
 733  * Redistribution and use in source and binary forms are permitted
 734  * provided that the above copyright notice and this paragraph are
 735  * duplicated in all such forms and that any documentation,
 736  * advertising materials, and other materials related to such
 737  * distribution and use acknowledge that the software was developed
 738  * by the University of California, Berkeley.  The name of the
 739  * University may not be used to endorse or promote products derived
 740  * from this software without specific prior written permission.
 741  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
 742  * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
 743  * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
 744  */
 745 #endif /* LZW_SUPPORT */