1 /* $Id: tif_lzw.c,v 1.55 2017-05-17 09:38:58 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
LZWFixupTags(TIFF * tif)192 LZWFixupTags(TIFF* tif)
193 {
194 (void) tif;
195 return (1);
196 }
197
198 static int
LZWSetupDecode(TIFF * tif)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 = (unsigned char)code;
244 sp->dec_codetab[code].firstchar = (unsigned char)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
LZWPreDecode(TIFF * tif,uint16 s)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 = 0;
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
codeLoop(TIFF * tif,const char * module)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
LZWDecode(TIFF * tif,uint8 * op0,tmsize_t occ0,uint16 s)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;
415 occ -= residue;
416 tp = op;
417 do {
418 int t;
419 --tp;
420 t = codep->value;
421 codep = codep->next;
422 *tp = (char)t;
423 } while (--residue && codep);
424 sp->dec_restart = 0;
425 }
426
427 bp = (unsigned char *)tif->tif_rawcp;
428 #ifdef LZW_CHECKEOS
429 sp->dec_bitsleft = (((uint64)tif->tif_rawcc) << 3);
430 #endif
431 nbits = sp->lzw_nbits;
432 nextdata = sp->lzw_nextdata;
433 nextbits = sp->lzw_nextbits;
434 nbitsmask = sp->dec_nbitsmask;
435 oldcodep = sp->dec_oldcodep;
436 free_entp = sp->dec_free_entp;
437 maxcodep = sp->dec_maxcodep;
438
439 while (occ > 0) {
440 NextCode(tif, sp, bp, code, GetNextCode);
441 if (code == CODE_EOI)
442 break;
443 if (code == CODE_CLEAR) {
444 do {
445 free_entp = sp->dec_codetab + CODE_FIRST;
446 _TIFFmemset(free_entp, 0,
447 (CSIZE - CODE_FIRST) * sizeof (code_t));
448 nbits = BITS_MIN;
449 nbitsmask = MAXCODE(BITS_MIN);
450 maxcodep = sp->dec_codetab + nbitsmask-1;
451 NextCode(tif, sp, bp, code, GetNextCode);
452 } while (code == CODE_CLEAR); /* consecutive CODE_CLEAR codes */
453 if (code == CODE_EOI)
454 break;
455 if (code > CODE_CLEAR) {
456 TIFFErrorExt(tif->tif_clientdata, tif->tif_name,
457 "LZWDecode: Corrupted LZW table at scanline %d",
458 tif->tif_row);
459 return (0);
460 }
461 *op++ = (char)code;
462 occ--;
463 oldcodep = sp->dec_codetab + code;
464 continue;
465 }
466 codep = sp->dec_codetab + code;
467
468 /*
469 * Add the new entry to the code table.
470 */
471 if (free_entp < &sp->dec_codetab[0] ||
472 free_entp >= &sp->dec_codetab[CSIZE]) {
473 TIFFErrorExt(tif->tif_clientdata, module,
474 "Corrupted LZW table at scanline %d",
475 tif->tif_row);
476 return (0);
477 }
478
479 free_entp->next = oldcodep;
480 if (free_entp->next < &sp->dec_codetab[0] ||
481 free_entp->next >= &sp->dec_codetab[CSIZE]) {
482 TIFFErrorExt(tif->tif_clientdata, module,
483 "Corrupted LZW table at scanline %d",
484 tif->tif_row);
485 return (0);
486 }
487 free_entp->firstchar = free_entp->next->firstchar;
488 free_entp->length = free_entp->next->length+1;
489 free_entp->value = (codep < free_entp) ?
490 codep->firstchar : free_entp->firstchar;
491 if (++free_entp > maxcodep) {
492 if (++nbits > BITS_MAX) /* should not happen */
493 nbits = BITS_MAX;
494 nbitsmask = MAXCODE(nbits);
495 maxcodep = sp->dec_codetab + nbitsmask-1;
496 }
497 oldcodep = codep;
498 if (code >= 256) {
499 /*
500 * Code maps to a string, copy string
501 * value to output (written in reverse).
502 */
503 if(codep->length == 0) {
504 TIFFErrorExt(tif->tif_clientdata, module,
505 "Wrong length of decoded string: "
506 "data probably corrupted at scanline %d",
507 tif->tif_row);
508 return (0);
509 }
510 if (codep->length > occ) {
511 /*
512 * String is too long for decode buffer,
513 * locate portion that will fit, copy to
514 * the decode buffer, and setup restart
515 * logic for the next decoding call.
516 */
517 sp->dec_codep = codep;
518 do {
519 codep = codep->next;
520 } while (codep && codep->length > occ);
521 if (codep) {
522 sp->dec_restart = (long)occ;
523 tp = op + occ;
524 do {
525 *--tp = codep->value;
526 codep = codep->next;
527 } while (--occ && codep);
528 if (codep)
529 codeLoop(tif, module);
530 }
531 break;
532 }
533 len = codep->length;
534 tp = op + len;
535 do {
536 int t;
537 --tp;
538 t = codep->value;
539 codep = codep->next;
540 *tp = (char)t;
541 } while (codep && tp > op);
542 if (codep) {
543 codeLoop(tif, module);
544 break;
545 }
546 assert(occ >= len);
547 op += len;
548 occ -= len;
549 } else {
550 *op++ = (char)code;
551 occ--;
552 }
553 }
554
555 tif->tif_rawcc -= (tmsize_t)( (uint8*) bp - tif->tif_rawcp );
556 tif->tif_rawcp = (uint8*) bp;
557 sp->lzw_nbits = (unsigned short) nbits;
558 sp->lzw_nextdata = nextdata;
559 sp->lzw_nextbits = nextbits;
560 sp->dec_nbitsmask = nbitsmask;
561 sp->dec_oldcodep = oldcodep;
562 sp->dec_free_entp = free_entp;
563 sp->dec_maxcodep = maxcodep;
564
565 if (occ > 0) {
566 #if defined(__WIN32__) && (defined(_MSC_VER) || defined(__MINGW32__))
567 TIFFErrorExt(tif->tif_clientdata, module,
568 "Not enough data at scanline %d (short %I64d bytes)",
569 tif->tif_row, (unsigned __int64) occ);
570 #else
571 TIFFErrorExt(tif->tif_clientdata, module,
572 "Not enough data at scanline %d (short %llu bytes)",
573 tif->tif_row, (unsigned long long) occ);
574 #endif
575 return (0);
576 }
577 return (1);
578 }
579
580 #ifdef LZW_COMPAT
581 /*
582 * Decode a "hunk of data" for old images.
583 */
584 #define GetNextCodeCompat(sp, bp, code) { \
585 nextdata |= (unsigned long) *(bp)++ << nextbits; \
586 nextbits += 8; \
587 if (nextbits < nbits) { \
588 nextdata |= (unsigned long) *(bp)++ << nextbits;\
589 nextbits += 8; \
590 } \
591 code = (hcode_t)(nextdata & nbitsmask); \
592 nextdata >>= nbits; \
593 nextbits -= nbits; \
594 }
595
596 static int
LZWDecodeCompat(TIFF * tif,uint8 * op0,tmsize_t occ0,uint16 s)597 LZWDecodeCompat(TIFF* tif, uint8* op0, tmsize_t occ0, uint16 s)
598 {
599 static const char module[] = "LZWDecodeCompat";
600 LZWCodecState *sp = DecoderState(tif);
601 char *op = (char*) op0;
602 long occ = (long) occ0;
603 char *tp;
604 unsigned char *bp;
605 int code, nbits;
606 long nextbits, nextdata, nbitsmask;
607 code_t *codep, *free_entp, *maxcodep, *oldcodep;
608
609 (void) s;
610 assert(sp != NULL);
611
612 /*
613 Fail if value does not fit in long.
614 */
615 if ((tmsize_t) occ != occ0)
616 return (0);
617
618 /*
619 * Restart interrupted output operation.
620 */
621 if (sp->dec_restart) {
622 long residue;
623
624 codep = sp->dec_codep;
625 residue = codep->length - sp->dec_restart;
626 if (residue > occ) {
627 /*
628 * Residue from previous decode is sufficient
629 * to satisfy decode request. Skip to the
630 * start of the decoded string, place decoded
631 * values in the output buffer, and return.
632 */
633 sp->dec_restart += occ;
634 do {
635 codep = codep->next;
636 } while (--residue > occ);
637 tp = op + occ;
638 do {
639 *--tp = codep->value;
640 codep = codep->next;
641 } while (--occ);
642 return (1);
643 }
644 /*
645 * Residue satisfies only part of the decode request.
646 */
647 op += residue;
648 occ -= residue;
649 tp = op;
650 do {
651 *--tp = codep->value;
652 codep = codep->next;
653 } while (--residue);
654 sp->dec_restart = 0;
655 }
656
657 bp = (unsigned char *)tif->tif_rawcp;
658 nbits = sp->lzw_nbits;
659 nextdata = sp->lzw_nextdata;
660 nextbits = sp->lzw_nextbits;
661 nbitsmask = sp->dec_nbitsmask;
662 oldcodep = sp->dec_oldcodep;
663 free_entp = sp->dec_free_entp;
664 maxcodep = sp->dec_maxcodep;
665
666 while (occ > 0) {
667 NextCode(tif, sp, bp, code, GetNextCodeCompat);
668 if (code == CODE_EOI)
669 break;
670 if (code == CODE_CLEAR) {
671 do {
672 free_entp = sp->dec_codetab + CODE_FIRST;
673 _TIFFmemset(free_entp, 0,
674 (CSIZE - CODE_FIRST) * sizeof (code_t));
675 nbits = BITS_MIN;
676 nbitsmask = MAXCODE(BITS_MIN);
677 maxcodep = sp->dec_codetab + nbitsmask;
678 NextCode(tif, sp, bp, code, GetNextCodeCompat);
679 } while (code == CODE_CLEAR); /* consecutive CODE_CLEAR codes */
680 if (code == CODE_EOI)
681 break;
682 if (code > CODE_CLEAR) {
683 TIFFErrorExt(tif->tif_clientdata, tif->tif_name,
684 "LZWDecode: Corrupted LZW table at scanline %d",
685 tif->tif_row);
686 return (0);
687 }
688 *op++ = (char)code;
689 occ--;
690 oldcodep = sp->dec_codetab + code;
691 continue;
692 }
693 codep = sp->dec_codetab + code;
694
695 /*
696 * Add the new entry to the code table.
697 */
698 if (free_entp < &sp->dec_codetab[0] ||
699 free_entp >= &sp->dec_codetab[CSIZE]) {
700 TIFFErrorExt(tif->tif_clientdata, module,
701 "Corrupted LZW table at scanline %d", tif->tif_row);
702 return (0);
703 }
704
705 free_entp->next = oldcodep;
706 if (free_entp->next < &sp->dec_codetab[0] ||
707 free_entp->next >= &sp->dec_codetab[CSIZE]) {
708 TIFFErrorExt(tif->tif_clientdata, module,
709 "Corrupted LZW table at scanline %d", tif->tif_row);
710 return (0);
711 }
712 free_entp->firstchar = free_entp->next->firstchar;
713 free_entp->length = free_entp->next->length+1;
714 free_entp->value = (codep < free_entp) ?
715 codep->firstchar : free_entp->firstchar;
716 if (++free_entp > maxcodep) {
717 if (++nbits > BITS_MAX) /* should not happen */
718 nbits = BITS_MAX;
719 nbitsmask = MAXCODE(nbits);
720 maxcodep = sp->dec_codetab + nbitsmask;
721 }
722 oldcodep = codep;
723 if (code >= 256) {
724 /*
725 * Code maps to a string, copy string
726 * value to output (written in reverse).
727 */
728 if(codep->length == 0) {
729 TIFFErrorExt(tif->tif_clientdata, module,
730 "Wrong length of decoded "
731 "string: data probably corrupted at scanline %d",
732 tif->tif_row);
733 return (0);
734 }
735 if (codep->length > occ) {
736 /*
737 * String is too long for decode buffer,
738 * locate portion that will fit, copy to
739 * the decode buffer, and setup restart
740 * logic for the next decoding call.
741 */
742 sp->dec_codep = codep;
743 do {
744 codep = codep->next;
745 } while (codep->length > occ);
746 sp->dec_restart = occ;
747 tp = op + occ;
748 do {
749 *--tp = codep->value;
750 codep = codep->next;
751 } while (--occ);
752 break;
753 }
754 assert(occ >= codep->length);
755 op += codep->length;
756 occ -= codep->length;
757 tp = op;
758 do {
759 *--tp = codep->value;
760 } while( (codep = codep->next) != NULL );
761 } else {
762 *op++ = (char)code;
763 occ--;
764 }
765 }
766
767 tif->tif_rawcp = (uint8*) bp;
768 sp->lzw_nbits = (unsigned short)nbits;
769 sp->lzw_nextdata = nextdata;
770 sp->lzw_nextbits = nextbits;
771 sp->dec_nbitsmask = nbitsmask;
772 sp->dec_oldcodep = oldcodep;
773 sp->dec_free_entp = free_entp;
774 sp->dec_maxcodep = maxcodep;
775
776 if (occ > 0) {
777 #if defined(__WIN32__) && (defined(_MSC_VER) || defined(__MINGW32__))
778 TIFFErrorExt(tif->tif_clientdata, module,
779 "Not enough data at scanline %d (short %I64d bytes)",
780 tif->tif_row, (unsigned __int64) occ);
781 #else
782 TIFFErrorExt(tif->tif_clientdata, module,
783 "Not enough data at scanline %d (short %llu bytes)",
784 tif->tif_row, (unsigned long long) occ);
785 #endif
786 return (0);
787 }
788 return (1);
789 }
790 #endif /* LZW_COMPAT */
791
792 /*
793 * LZW Encoding.
794 */
795
796 static int
LZWSetupEncode(TIFF * tif)797 LZWSetupEncode(TIFF* tif)
798 {
799 static const char module[] = "LZWSetupEncode";
800 LZWCodecState* sp = EncoderState(tif);
801
802 assert(sp != NULL);
803 sp->enc_hashtab = (hash_t*) _TIFFmalloc(HSIZE*sizeof (hash_t));
804 if (sp->enc_hashtab == NULL) {
805 TIFFErrorExt(tif->tif_clientdata, module,
806 "No space for LZW hash table");
807 return (0);
808 }
809 return (1);
810 }
811
812 /*
813 * Reset encoding state at the start of a strip.
814 */
815 static int
LZWPreEncode(TIFF * tif,uint16 s)816 LZWPreEncode(TIFF* tif, uint16 s)
817 {
818 LZWCodecState *sp = EncoderState(tif);
819
820 (void) s;
821 assert(sp != NULL);
822
823 if( sp->enc_hashtab == NULL )
824 {
825 tif->tif_setupencode( tif );
826 }
827
828 sp->lzw_nbits = BITS_MIN;
829 sp->lzw_maxcode = MAXCODE(BITS_MIN);
830 sp->lzw_free_ent = CODE_FIRST;
831 sp->lzw_nextbits = 0;
832 sp->lzw_nextdata = 0;
833 sp->enc_checkpoint = CHECK_GAP;
834 sp->enc_ratio = 0;
835 sp->enc_incount = 0;
836 sp->enc_outcount = 0;
837 /*
838 * The 4 here insures there is space for 2 max-sized
839 * codes in LZWEncode and LZWPostDecode.
840 */
841 sp->enc_rawlimit = tif->tif_rawdata + tif->tif_rawdatasize-1 - 4;
842 cl_hash(sp); /* clear hash table */
843 sp->enc_oldcode = (hcode_t) -1; /* generates CODE_CLEAR in LZWEncode */
844 return (1);
845 }
846
847 #define CALCRATIO(sp, rat) { \
848 if (incount > 0x007fffff) { /* NB: shift will overflow */\
849 rat = outcount >> 8; \
850 rat = (rat == 0 ? 0x7fffffff : incount/rat); \
851 } else \
852 rat = (incount<<8) / outcount; \
853 }
854
855 /* Explicit 0xff masking to make icc -check=conversions happy */
856 #define PutNextCode(op, c) { \
857 nextdata = (nextdata << nbits) | c; \
858 nextbits += nbits; \
859 *op++ = (unsigned char)((nextdata >> (nextbits-8))&0xff); \
860 nextbits -= 8; \
861 if (nextbits >= 8) { \
862 *op++ = (unsigned char)((nextdata >> (nextbits-8))&0xff); \
863 nextbits -= 8; \
864 } \
865 outcount += nbits; \
866 }
867
868 /*
869 * Encode a chunk of pixels.
870 *
871 * Uses an open addressing double hashing (no chaining) on the
872 * prefix code/next character combination. We do a variant of
873 * Knuth's algorithm D (vol. 3, sec. 6.4) along with G. Knott's
874 * relatively-prime secondary probe. Here, the modular division
875 * first probe is gives way to a faster exclusive-or manipulation.
876 * Also do block compression with an adaptive reset, whereby the
877 * code table is cleared when the compression ratio decreases,
878 * but after the table fills. The variable-length output codes
879 * are re-sized at this point, and a CODE_CLEAR is generated
880 * for the decoder.
881 */
882 static int
LZWEncode(TIFF * tif,uint8 * bp,tmsize_t cc,uint16 s)883 LZWEncode(TIFF* tif, uint8* bp, tmsize_t cc, uint16 s)
884 {
885 register LZWCodecState *sp = EncoderState(tif);
886 register long fcode;
887 register hash_t *hp;
888 register int h, c;
889 hcode_t ent;
890 long disp;
891 long incount, outcount, checkpoint;
892 unsigned long nextdata;
893 long nextbits;
894 int free_ent, maxcode, nbits;
895 uint8* op;
896 uint8* limit;
897
898 (void) s;
899 if (sp == NULL)
900 return (0);
901
902 assert(sp->enc_hashtab != NULL);
903
904 /*
905 * Load local state.
906 */
907 incount = sp->enc_incount;
908 outcount = sp->enc_outcount;
909 checkpoint = sp->enc_checkpoint;
910 nextdata = sp->lzw_nextdata;
911 nextbits = sp->lzw_nextbits;
912 free_ent = sp->lzw_free_ent;
913 maxcode = sp->lzw_maxcode;
914 nbits = sp->lzw_nbits;
915 op = tif->tif_rawcp;
916 limit = sp->enc_rawlimit;
917 ent = (hcode_t)sp->enc_oldcode;
918
919 if (ent == (hcode_t) -1 && cc > 0) {
920 /*
921 * NB: This is safe because it can only happen
922 * at the start of a strip where we know there
923 * is space in the data buffer.
924 */
925 PutNextCode(op, CODE_CLEAR);
926 ent = *bp++; cc--; incount++;
927 }
928 while (cc > 0) {
929 c = *bp++; cc--; incount++;
930 fcode = ((long)c << BITS_MAX) + ent;
931 h = (c << HSHIFT) ^ ent; /* xor hashing */
932 #ifdef _WINDOWS
933 /*
934 * Check hash index for an overflow.
935 */
936 if (h >= HSIZE)
937 h -= HSIZE;
938 #endif
939 hp = &sp->enc_hashtab[h];
940 if (hp->hash == fcode) {
941 ent = hp->code;
942 continue;
943 }
944 if (hp->hash >= 0) {
945 /*
946 * Primary hash failed, check secondary hash.
947 */
948 disp = HSIZE - h;
949 if (h == 0)
950 disp = 1;
951 do {
952 /*
953 * Avoid pointer arithmetic because of
954 * wraparound problems with segments.
955 */
956 if ((h -= disp) < 0)
957 h += HSIZE;
958 hp = &sp->enc_hashtab[h];
959 if (hp->hash == fcode) {
960 ent = hp->code;
961 goto hit;
962 }
963 } while (hp->hash >= 0);
964 }
965 /*
966 * New entry, emit code and add to table.
967 */
968 /*
969 * Verify there is space in the buffer for the code
970 * and any potential Clear code that might be emitted
971 * below. The value of limit is setup so that there
972 * are at least 4 bytes free--room for 2 codes.
973 */
974 if (op > limit) {
975 tif->tif_rawcc = (tmsize_t)(op - tif->tif_rawdata);
976 if( !TIFFFlushData1(tif) )
977 return 0;
978 op = tif->tif_rawdata;
979 }
980 PutNextCode(op, ent);
981 ent = (hcode_t)c;
982 hp->code = (hcode_t)(free_ent++);
983 hp->hash = fcode;
984 if (free_ent == CODE_MAX-1) {
985 /* table is full, emit clear code and reset */
986 cl_hash(sp);
987 sp->enc_ratio = 0;
988 incount = 0;
989 outcount = 0;
990 free_ent = CODE_FIRST;
991 PutNextCode(op, CODE_CLEAR);
992 nbits = BITS_MIN;
993 maxcode = MAXCODE(BITS_MIN);
994 } else {
995 /*
996 * If the next entry is going to be too big for
997 * the code size, then increase it, if possible.
998 */
999 if (free_ent > maxcode) {
1000 nbits++;
1001 assert(nbits <= BITS_MAX);
1002 maxcode = (int) MAXCODE(nbits);
1003 } else if (incount >= checkpoint) {
1004 long rat;
1005 /*
1006 * Check compression ratio and, if things seem
1007 * to be slipping, clear the hash table and
1008 * reset state. The compression ratio is a
1009 * 24+8-bit fractional number.
1010 */
1011 checkpoint = incount+CHECK_GAP;
1012 CALCRATIO(sp, rat);
1013 if (rat <= sp->enc_ratio) {
1014 cl_hash(sp);
1015 sp->enc_ratio = 0;
1016 incount = 0;
1017 outcount = 0;
1018 free_ent = CODE_FIRST;
1019 PutNextCode(op, CODE_CLEAR);
1020 nbits = BITS_MIN;
1021 maxcode = MAXCODE(BITS_MIN);
1022 } else
1023 sp->enc_ratio = rat;
1024 }
1025 }
1026 hit:
1027 ;
1028 }
1029
1030 /*
1031 * Restore global state.
1032 */
1033 sp->enc_incount = incount;
1034 sp->enc_outcount = outcount;
1035 sp->enc_checkpoint = checkpoint;
1036 sp->enc_oldcode = ent;
1037 sp->lzw_nextdata = nextdata;
1038 sp->lzw_nextbits = nextbits;
1039 sp->lzw_free_ent = (unsigned short)free_ent;
1040 sp->lzw_maxcode = (unsigned short)maxcode;
1041 sp->lzw_nbits = (unsigned short)nbits;
1042 tif->tif_rawcp = op;
1043 return (1);
1044 }
1045
1046 /*
1047 * Finish off an encoded strip by flushing the last
1048 * string and tacking on an End Of Information code.
1049 */
1050 static int
LZWPostEncode(TIFF * tif)1051 LZWPostEncode(TIFF* tif)
1052 {
1053 register LZWCodecState *sp = EncoderState(tif);
1054 uint8* op = tif->tif_rawcp;
1055 long nextbits = sp->lzw_nextbits;
1056 unsigned long nextdata = sp->lzw_nextdata;
1057 long outcount = sp->enc_outcount;
1058 int nbits = sp->lzw_nbits;
1059
1060 if (op > sp->enc_rawlimit) {
1061 tif->tif_rawcc = (tmsize_t)(op - tif->tif_rawdata);
1062 if( !TIFFFlushData1(tif) )
1063 return 0;
1064 op = tif->tif_rawdata;
1065 }
1066 if (sp->enc_oldcode != (hcode_t) -1) {
1067 int free_ent = sp->lzw_free_ent;
1068
1069 PutNextCode(op, sp->enc_oldcode);
1070 sp->enc_oldcode = (hcode_t) -1;
1071 free_ent ++;
1072
1073 if (free_ent == CODE_MAX-1) {
1074 /* table is full, emit clear code and reset */
1075 outcount = 0;
1076 PutNextCode(op, CODE_CLEAR);
1077 nbits = BITS_MIN;
1078 } else {
1079 /*
1080 * If the next entry is going to be too big for
1081 * the code size, then increase it, if possible.
1082 */
1083 if (free_ent > sp->lzw_maxcode) {
1084 nbits++;
1085 assert(nbits <= BITS_MAX);
1086 }
1087 }
1088 }
1089 PutNextCode(op, CODE_EOI);
1090 /* Explicit 0xff masking to make icc -check=conversions happy */
1091 if (nextbits > 0)
1092 *op++ = (unsigned char)((nextdata << (8-nextbits))&0xff);
1093 tif->tif_rawcc = (tmsize_t)(op - tif->tif_rawdata);
1094 return (1);
1095 }
1096
1097 /*
1098 * Reset encoding hash table.
1099 */
1100 static void
cl_hash(LZWCodecState * sp)1101 cl_hash(LZWCodecState* sp)
1102 {
1103 register hash_t *hp = &sp->enc_hashtab[HSIZE-1];
1104 register long i = HSIZE-8;
1105
1106 do {
1107 i -= 8;
1108 hp[-7].hash = -1;
1109 hp[-6].hash = -1;
1110 hp[-5].hash = -1;
1111 hp[-4].hash = -1;
1112 hp[-3].hash = -1;
1113 hp[-2].hash = -1;
1114 hp[-1].hash = -1;
1115 hp[ 0].hash = -1;
1116 hp -= 8;
1117 } while (i >= 0);
1118 for (i += 8; i > 0; i--, hp--)
1119 hp->hash = -1;
1120 }
1121
1122 static void
LZWCleanup(TIFF * tif)1123 LZWCleanup(TIFF* tif)
1124 {
1125 (void)TIFFPredictorCleanup(tif);
1126
1127 assert(tif->tif_data != 0);
1128
1129 if (DecoderState(tif)->dec_codetab)
1130 _TIFFfree(DecoderState(tif)->dec_codetab);
1131
1132 if (EncoderState(tif)->enc_hashtab)
1133 _TIFFfree(EncoderState(tif)->enc_hashtab);
1134
1135 _TIFFfree(tif->tif_data);
1136 tif->tif_data = NULL;
1137
1138 _TIFFSetDefaultCompressionState(tif);
1139 }
1140
1141 int
TIFFInitLZW(TIFF * tif,int scheme)1142 TIFFInitLZW(TIFF* tif, int scheme)
1143 {
1144 static const char module[] = "TIFFInitLZW";
1145 assert(scheme == COMPRESSION_LZW);
1146 /*
1147 * Allocate state block so tag methods have storage to record values.
1148 */
1149 tif->tif_data = (uint8*) _TIFFmalloc(sizeof (LZWCodecState));
1150 if (tif->tif_data == NULL)
1151 goto bad;
1152 DecoderState(tif)->dec_codetab = NULL;
1153 DecoderState(tif)->dec_decode = NULL;
1154 EncoderState(tif)->enc_hashtab = NULL;
1155 LZWState(tif)->rw_mode = tif->tif_mode;
1156
1157 /*
1158 * Install codec methods.
1159 */
1160 tif->tif_fixuptags = LZWFixupTags;
1161 tif->tif_setupdecode = LZWSetupDecode;
1162 tif->tif_predecode = LZWPreDecode;
1163 tif->tif_decoderow = LZWDecode;
1164 tif->tif_decodestrip = LZWDecode;
1165 tif->tif_decodetile = LZWDecode;
1166 tif->tif_setupencode = LZWSetupEncode;
1167 tif->tif_preencode = LZWPreEncode;
1168 tif->tif_postencode = LZWPostEncode;
1169 tif->tif_encoderow = LZWEncode;
1170 tif->tif_encodestrip = LZWEncode;
1171 tif->tif_encodetile = LZWEncode;
1172 tif->tif_cleanup = LZWCleanup;
1173 /*
1174 * Setup predictor setup.
1175 */
1176 (void) TIFFPredictorInit(tif);
1177 return (1);
1178 bad:
1179 TIFFErrorExt(tif->tif_clientdata, module,
1180 "No space for LZW state block");
1181 return (0);
1182 }
1183
1184 /*
1185 * Copyright (c) 1985, 1986 The Regents of the University of California.
1186 * All rights reserved.
1187 *
1188 * This code is derived from software contributed to Berkeley by
1189 * James A. Woods, derived from original work by Spencer Thomas
1190 * and Joseph Orost.
1191 *
1192 * Redistribution and use in source and binary forms are permitted
1193 * provided that the above copyright notice and this paragraph are
1194 * duplicated in all such forms and that any documentation,
1195 * advertising materials, and other materials related to such
1196 * distribution and use acknowledge that the software was developed
1197 * by the University of California, Berkeley. The name of the
1198 * University may not be used to endorse or promote products derived
1199 * from this software without specific prior written permission.
1200 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
1201 * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
1202 * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
1203 */
1204 #endif /* LZW_SUPPORT */
1205
1206 /* vim: set ts=8 sts=8 sw=8 noet: */
1207 /*
1208 * Local Variables:
1209 * mode: c
1210 * c-basic-offset: 8
1211 * fill-column: 78
1212 * End:
1213 */
1214