1 /* $Id: tif_lzw.c,v 1.52 2016-09-04 21:32:56 erouault Exp $ */
4 * Copyright (c) 1988-1997 Sam Leffler
5 * Copyright (c) 1991-1997 Silicon Graphics, Inc.
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.
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.
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
32 * Rev 5.0 Lempel-Ziv & Welch Compression Support
34 * This code is derived from the compress program whose code is
35 * derived from software contributed to Berkeley by James A. Woods,
36 * derived from original work by Spencer Thomas and Joseph Orost.
38 * The original Berkeley copyright notice appears below in its entirety.
40 #include "tif_predict.h"
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.
55 * Future revisions to the TIFF spec are expected to "clarify this issue".
57 #define LZW_COMPAT /* include backwards compatibility code */
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.
64 #define LZW_CHECKEOS /* include checks for strips w/o EOI code */
66 #define MAXCODE(n) ((1L<<(n))-1)
68 * The TIFF spec specifies that encoded bit
69 * strings range from 9 to 12 bits.
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 */
81 /* NB: +1024 is for compatibility with old files */
82 #define CSIZE (MAXCODE(BITS_MAX)+1024L)
84 #define CSIZE (MAXCODE(BITS_MAX)+1L)
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.
93 TIFFPredictorState predict
; /* predictor super class */
95 unsigned short nbits
; /* # of bits/code */
96 unsigned short maxcode
; /* maximum code for lzw_nbits */
97 unsigned short free_ent
; /* next free entry in hash table */
98 unsigned long nextdata
; /* next bits of i/o */
99 long nextbits
; /* # of valid bits in lzw_nextdata */
101 int rw_mode
; /* preserve rw_mode from init */
104 #define lzw_nbits base.nbits
105 #define lzw_maxcode base.maxcode
106 #define lzw_free_ent base.free_ent
107 #define lzw_nextdata base.nextdata
108 #define lzw_nextbits base.nextbits
111 * Encoding-specific state.
113 typedef uint16 hcode_t
; /* codes fit in 16 bits */
120 * Decoding-specific state.
122 typedef struct code_ent
{
123 struct code_ent
*next
;
124 unsigned short length
; /* string len, including this token */
125 unsigned char value
; /* data value */
126 unsigned char firstchar
; /* first token of string */
129 typedef int (*decodeFunc
)(TIFF
*, uint8
*, tmsize_t
, uint16
);
134 /* Decoding specific data */
135 long dec_nbitsmask
; /* lzw_nbits 1 bits, right adjusted */
136 long dec_restart
; /* restart count */
138 uint64 dec_bitsleft
; /* available bits in raw data */
140 decodeFunc dec_decode
; /* regular or backwards compatible */
141 code_t
* dec_codep
; /* current recognized code */
142 code_t
* dec_oldcodep
; /* previously recognized code */
143 code_t
* dec_free_entp
; /* next free entry */
144 code_t
* dec_maxcodep
; /* max available entry */
145 code_t
* dec_codetab
; /* kept separate for small machines */
147 /* Encoding specific data */
148 int enc_oldcode
; /* last code encountered */
149 long enc_checkpoint
; /* point at which to clear table */
150 #define CHECK_GAP 10000 /* enc_ratio check interval */
151 long enc_ratio
; /* current compression ratio */
152 long enc_incount
; /* (input) data bytes encoded */
153 long enc_outcount
; /* encoded (output) bytes */
154 uint8
* enc_rawlimit
; /* bound on tif_rawdata buffer */
155 hash_t
* enc_hashtab
; /* kept separate for small machines */
158 #define LZWState(tif) ((LZWBaseState*) (tif)->tif_data)
159 #define DecoderState(tif) ((LZWCodecState*) LZWState(tif))
160 #define EncoderState(tif) ((LZWCodecState*) LZWState(tif))
162 static int LZWDecode(TIFF
* tif
, uint8
* op0
, tmsize_t occ0
, uint16 s
);
164 static int LZWDecodeCompat(TIFF
* tif
, uint8
* op0
, tmsize_t occ0
, uint16 s
);
166 static void cl_hash(LZWCodecState
*);
174 * This check shouldn't be necessary because each
175 * strip is suppose to be terminated with CODE_EOI.
177 #define NextCode(_tif, _sp, _bp, _code, _get) { \
178 if ((_sp)->dec_bitsleft < (uint64)nbits) { \
179 TIFFWarningExt(_tif->tif_clientdata, module, \
180 "LZWDecode: Strip %d not terminated with EOI code", \
181 _tif->tif_curstrip); \
184 _get(_sp,_bp,_code); \
185 (_sp)->dec_bitsleft -= nbits; \
189 #define NextCode(tif, sp, bp, code, get) get(sp, bp, code)
193 LZWFixupTags(TIFF
* tif
)
200 LZWSetupDecode(TIFF
* tif
)
202 static const char module
[] = "LZWSetupDecode";
203 LZWCodecState
* sp
= DecoderState(tif
);
209 * Allocate state block so tag methods have storage to record
212 tif
->tif_data
= (uint8
*) _TIFFmalloc(sizeof(LZWCodecState
));
213 if (tif
->tif_data
== NULL
)
215 TIFFErrorExt(tif
->tif_clientdata
, module
, "No space for LZW state block");
219 DecoderState(tif
)->dec_codetab
= NULL
;
220 DecoderState(tif
)->dec_decode
= NULL
;
223 * Setup predictor setup.
225 (void) TIFFPredictorInit(tif
);
227 sp
= DecoderState(tif
);
232 if (sp
->dec_codetab
== NULL
) {
233 sp
->dec_codetab
= (code_t
*)_TIFFmalloc(CSIZE
*sizeof (code_t
));
234 if (sp
->dec_codetab
== NULL
) {
235 TIFFErrorExt(tif
->tif_clientdata
, module
,
236 "No space for LZW code table");
240 * Pre-load the table.
244 sp
->dec_codetab
[code
].value
= (unsigned char)code
;
245 sp
->dec_codetab
[code
].firstchar
= (unsigned char)code
;
246 sp
->dec_codetab
[code
].length
= 1;
247 sp
->dec_codetab
[code
].next
= NULL
;
250 * Zero-out the unused entries
252 _TIFFmemset(&sp
->dec_codetab
[CODE_CLEAR
], 0,
253 (CODE_FIRST
- CODE_CLEAR
) * sizeof (code_t
));
259 * Setup state for decoding a strip.
262 LZWPreDecode(TIFF
* tif
, uint16 s
)
264 static const char module
[] = "LZWPreDecode";
265 LZWCodecState
*sp
= DecoderState(tif
);
269 if( sp
->dec_codetab
== NULL
)
271 tif
->tif_setupdecode( tif
);
272 if( sp
->dec_codetab
== NULL
)
277 * Check for old bit-reversed codes.
279 if (tif
->tif_rawdata
[0] == 0 && (tif
->tif_rawdata
[1] & 0x1)) {
281 if (!sp
->dec_decode
) {
282 TIFFWarningExt(tif
->tif_clientdata
, module
,
283 "Old-style LZW codes, convert file");
285 * Override default decoding methods with
286 * ones that deal with the old coding.
287 * Otherwise the predictor versions set
288 * above will call the compatibility routines
289 * through the dec_decode method.
291 tif
->tif_decoderow
= LZWDecodeCompat
;
292 tif
->tif_decodestrip
= LZWDecodeCompat
;
293 tif
->tif_decodetile
= LZWDecodeCompat
;
295 * If doing horizontal differencing, must
296 * re-setup the predictor logic since we
297 * switched the basic decoder methods...
299 (*tif
->tif_setupdecode
)(tif
);
300 sp
->dec_decode
= LZWDecodeCompat
;
302 sp
->lzw_maxcode
= MAXCODE(BITS_MIN
);
303 #else /* !LZW_COMPAT */
304 if (!sp
->dec_decode
) {
305 TIFFErrorExt(tif
->tif_clientdata
, module
,
306 "Old-style LZW codes not supported");
307 sp
->dec_decode
= LZWDecode
;
310 #endif/* !LZW_COMPAT */
312 sp
->lzw_maxcode
= MAXCODE(BITS_MIN
)-1;
313 sp
->dec_decode
= LZWDecode
;
315 sp
->lzw_nbits
= BITS_MIN
;
316 sp
->lzw_nextbits
= 0;
317 sp
->lzw_nextdata
= 0;
320 sp
->dec_nbitsmask
= MAXCODE(BITS_MIN
);
322 sp
->dec_bitsleft
= ((uint64
)tif
->tif_rawcc
) << 3;
324 sp
->dec_free_entp
= sp
->dec_codetab
+ CODE_FIRST
;
326 * Zero entries that are not yet filled in. We do
327 * this to guard against bogus input data that causes
328 * us to index into undefined entries. If you can
329 * come up with a way to safely bounds-check input codes
330 * while decoding then you can remove this operation.
332 _TIFFmemset(sp
->dec_free_entp
, 0, (CSIZE
-CODE_FIRST
)*sizeof (code_t
));
333 sp
->dec_oldcodep
= &sp
->dec_codetab
[-1];
334 sp
->dec_maxcodep
= &sp
->dec_codetab
[sp
->dec_nbitsmask
-1];
339 * Decode a "hunk of data".
341 #define GetNextCode(sp, bp, code) { \
342 nextdata = (nextdata<<8) | *(bp)++; \
344 if (nextbits < nbits) { \
345 nextdata = (nextdata<<8) | *(bp)++; \
348 code = (hcode_t)((nextdata >> (nextbits-nbits)) & nbitsmask); \
353 codeLoop(TIFF
* tif
, const char* module
)
355 TIFFErrorExt(tif
->tif_clientdata
, module
,
356 "Bogus encoding, loop in the code table; scanline %d",
361 LZWDecode(TIFF
* tif
, uint8
* op0
, tmsize_t occ0
, uint16 s
)
363 static const char module
[] = "LZWDecode";
364 LZWCodecState
*sp
= DecoderState(tif
);
365 char *op
= (char*) op0
;
366 long occ
= (long) occ0
;
371 long nbits
, nextbits
, nbitsmask
;
372 unsigned long nextdata
;
373 code_t
*codep
, *free_entp
, *maxcodep
, *oldcodep
;
377 assert(sp
->dec_codetab
!= NULL
);
380 Fail if value does not fit in long.
382 if ((tmsize_t
) occ
!= occ0
)
385 * Restart interrupted output operation.
387 if (sp
->dec_restart
) {
390 codep
= sp
->dec_codep
;
391 residue
= codep
->length
- sp
->dec_restart
;
394 * Residue from previous decode is sufficient
395 * to satisfy decode request. Skip to the
396 * start of the decoded string, place decoded
397 * values in the output buffer, and return.
399 sp
->dec_restart
+= occ
;
402 } while (--residue
> occ
&& codep
);
406 *--tp
= codep
->value
;
408 } while (--occ
&& codep
);
413 * Residue satisfies only part of the decode request.
424 } while (--residue
&& codep
);
428 bp
= (unsigned char *)tif
->tif_rawcp
;
429 nbits
= sp
->lzw_nbits
;
430 nextdata
= sp
->lzw_nextdata
;
431 nextbits
= sp
->lzw_nextbits
;
432 nbitsmask
= sp
->dec_nbitsmask
;
433 oldcodep
= sp
->dec_oldcodep
;
434 free_entp
= sp
->dec_free_entp
;
435 maxcodep
= sp
->dec_maxcodep
;
438 NextCode(tif
, sp
, bp
, code
, GetNextCode
);
439 if (code
== CODE_EOI
)
441 if (code
== CODE_CLEAR
) {
443 free_entp
= sp
->dec_codetab
+ CODE_FIRST
;
444 _TIFFmemset(free_entp
, 0,
445 (CSIZE
- CODE_FIRST
) * sizeof (code_t
));
447 nbitsmask
= MAXCODE(BITS_MIN
);
448 maxcodep
= sp
->dec_codetab
+ nbitsmask
-1;
449 NextCode(tif
, sp
, bp
, code
, GetNextCode
);
450 } while (code
== CODE_CLEAR
); /* consecutive CODE_CLEAR codes */
451 if (code
== CODE_EOI
)
453 if (code
> CODE_CLEAR
) {
454 TIFFErrorExt(tif
->tif_clientdata
, tif
->tif_name
,
455 "LZWDecode: Corrupted LZW table at scanline %d",
461 oldcodep
= sp
->dec_codetab
+ code
;
464 codep
= sp
->dec_codetab
+ code
;
467 * Add the new entry to the code table.
469 if (free_entp
< &sp
->dec_codetab
[0] ||
470 free_entp
>= &sp
->dec_codetab
[CSIZE
]) {
471 TIFFErrorExt(tif
->tif_clientdata
, module
,
472 "Corrupted LZW table at scanline %d",
477 free_entp
->next
= oldcodep
;
478 if (free_entp
->next
< &sp
->dec_codetab
[0] ||
479 free_entp
->next
>= &sp
->dec_codetab
[CSIZE
]) {
480 TIFFErrorExt(tif
->tif_clientdata
, module
,
481 "Corrupted LZW table at scanline %d",
485 free_entp
->firstchar
= free_entp
->next
->firstchar
;
486 free_entp
->length
= free_entp
->next
->length
+1;
487 free_entp
->value
= (codep
< free_entp
) ?
488 codep
->firstchar
: free_entp
->firstchar
;
489 if (++free_entp
> maxcodep
) {
490 if (++nbits
> BITS_MAX
) /* should not happen */
492 nbitsmask
= MAXCODE(nbits
);
493 maxcodep
= sp
->dec_codetab
+ nbitsmask
-1;
498 * Code maps to a string, copy string
499 * value to output (written in reverse).
501 if(codep
->length
== 0) {
502 TIFFErrorExt(tif
->tif_clientdata
, module
,
503 "Wrong length of decoded string: "
504 "data probably corrupted at scanline %d",
508 if (codep
->length
> occ
) {
510 * String is too long for decode buffer,
511 * locate portion that will fit, copy to
512 * the decode buffer, and setup restart
513 * logic for the next decoding call.
515 sp
->dec_codep
= codep
;
518 } while (codep
&& codep
->length
> occ
);
520 sp
->dec_restart
= (long)occ
;
523 *--tp
= codep
->value
;
525 } while (--occ
&& codep
);
527 codeLoop(tif
, module
);
539 } while (codep
&& tp
> op
);
541 codeLoop(tif
, module
);
553 tif
->tif_rawcp
= (uint8
*) bp
;
554 sp
->lzw_nbits
= (unsigned short) nbits
;
555 sp
->lzw_nextdata
= nextdata
;
556 sp
->lzw_nextbits
= nextbits
;
557 sp
->dec_nbitsmask
= nbitsmask
;
558 sp
->dec_oldcodep
= oldcodep
;
559 sp
->dec_free_entp
= free_entp
;
560 sp
->dec_maxcodep
= maxcodep
;
563 #if defined(__WIN32__) && (defined(_MSC_VER) || defined(__MINGW32__))
564 TIFFErrorExt(tif
->tif_clientdata
, module
,
565 "Not enough data at scanline %d (short %I64d bytes)",
566 tif
->tif_row
, (unsigned __int64
) occ
);
568 TIFFErrorExt(tif
->tif_clientdata
, module
,
569 "Not enough data at scanline %d (short %llu bytes)",
570 tif
->tif_row
, (unsigned long long) occ
);
579 * Decode a "hunk of data" for old images.
581 #define GetNextCodeCompat(sp, bp, code) { \
582 nextdata |= (unsigned long) *(bp)++ << nextbits; \
584 if (nextbits < nbits) { \
585 nextdata |= (unsigned long) *(bp)++ << nextbits;\
588 code = (hcode_t)(nextdata & nbitsmask); \
589 nextdata >>= nbits; \
594 LZWDecodeCompat(TIFF
* tif
, uint8
* op0
, tmsize_t occ0
, uint16 s
)
596 static const char module
[] = "LZWDecodeCompat";
597 LZWCodecState
*sp
= DecoderState(tif
);
598 char *op
= (char*) op0
;
599 long occ
= (long) occ0
;
603 long nextbits
, nextdata
, nbitsmask
;
604 code_t
*codep
, *free_entp
, *maxcodep
, *oldcodep
;
610 Fail if value does not fit in long.
612 if ((tmsize_t
) occ
!= occ0
)
616 * Restart interrupted output operation.
618 if (sp
->dec_restart
) {
621 codep
= sp
->dec_codep
;
622 residue
= codep
->length
- sp
->dec_restart
;
625 * Residue from previous decode is sufficient
626 * to satisfy decode request. Skip to the
627 * start of the decoded string, place decoded
628 * values in the output buffer, and return.
630 sp
->dec_restart
+= occ
;
633 } while (--residue
> occ
);
636 *--tp
= codep
->value
;
642 * Residue satisfies only part of the decode request.
648 *--tp
= codep
->value
;
654 bp
= (unsigned char *)tif
->tif_rawcp
;
655 nbits
= sp
->lzw_nbits
;
656 nextdata
= sp
->lzw_nextdata
;
657 nextbits
= sp
->lzw_nextbits
;
658 nbitsmask
= sp
->dec_nbitsmask
;
659 oldcodep
= sp
->dec_oldcodep
;
660 free_entp
= sp
->dec_free_entp
;
661 maxcodep
= sp
->dec_maxcodep
;
664 NextCode(tif
, sp
, bp
, code
, GetNextCodeCompat
);
665 if (code
== CODE_EOI
)
667 if (code
== CODE_CLEAR
) {
669 free_entp
= sp
->dec_codetab
+ CODE_FIRST
;
670 _TIFFmemset(free_entp
, 0,
671 (CSIZE
- CODE_FIRST
) * sizeof (code_t
));
673 nbitsmask
= MAXCODE(BITS_MIN
);
674 maxcodep
= sp
->dec_codetab
+ nbitsmask
;
675 NextCode(tif
, sp
, bp
, code
, GetNextCodeCompat
);
676 } while (code
== CODE_CLEAR
); /* consecutive CODE_CLEAR codes */
677 if (code
== CODE_EOI
)
679 if (code
> CODE_CLEAR
) {
680 TIFFErrorExt(tif
->tif_clientdata
, tif
->tif_name
,
681 "LZWDecode: Corrupted LZW table at scanline %d",
687 oldcodep
= sp
->dec_codetab
+ code
;
690 codep
= sp
->dec_codetab
+ code
;
693 * Add the new entry to the code table.
695 if (free_entp
< &sp
->dec_codetab
[0] ||
696 free_entp
>= &sp
->dec_codetab
[CSIZE
]) {
697 TIFFErrorExt(tif
->tif_clientdata
, module
,
698 "Corrupted LZW table at scanline %d", tif
->tif_row
);
702 free_entp
->next
= oldcodep
;
703 if (free_entp
->next
< &sp
->dec_codetab
[0] ||
704 free_entp
->next
>= &sp
->dec_codetab
[CSIZE
]) {
705 TIFFErrorExt(tif
->tif_clientdata
, module
,
706 "Corrupted LZW table at scanline %d", tif
->tif_row
);
709 free_entp
->firstchar
= free_entp
->next
->firstchar
;
710 free_entp
->length
= free_entp
->next
->length
+1;
711 free_entp
->value
= (codep
< free_entp
) ?
712 codep
->firstchar
: free_entp
->firstchar
;
713 if (++free_entp
> maxcodep
) {
714 if (++nbits
> BITS_MAX
) /* should not happen */
716 nbitsmask
= MAXCODE(nbits
);
717 maxcodep
= sp
->dec_codetab
+ nbitsmask
;
722 * Code maps to a string, copy string
723 * value to output (written in reverse).
725 if(codep
->length
== 0) {
726 TIFFErrorExt(tif
->tif_clientdata
, module
,
727 "Wrong length of decoded "
728 "string: data probably corrupted at scanline %d",
732 if (codep
->length
> occ
) {
734 * String is too long for decode buffer,
735 * locate portion that will fit, copy to
736 * the decode buffer, and setup restart
737 * logic for the next decoding call.
739 sp
->dec_codep
= codep
;
742 } while (codep
->length
> occ
);
743 sp
->dec_restart
= occ
;
746 *--tp
= codep
->value
;
751 assert(occ
>= codep
->length
);
753 occ
-= codep
->length
;
756 *--tp
= codep
->value
;
757 } while( (codep
= codep
->next
) != NULL
);
764 tif
->tif_rawcp
= (uint8
*) bp
;
765 sp
->lzw_nbits
= (unsigned short)nbits
;
766 sp
->lzw_nextdata
= nextdata
;
767 sp
->lzw_nextbits
= nextbits
;
768 sp
->dec_nbitsmask
= nbitsmask
;
769 sp
->dec_oldcodep
= oldcodep
;
770 sp
->dec_free_entp
= free_entp
;
771 sp
->dec_maxcodep
= maxcodep
;
774 #if defined(__WIN32__) && (defined(_MSC_VER) || defined(__MINGW32__))
775 TIFFErrorExt(tif
->tif_clientdata
, module
,
776 "Not enough data at scanline %d (short %I64d bytes)",
777 tif
->tif_row
, (unsigned __int64
) occ
);
779 TIFFErrorExt(tif
->tif_clientdata
, module
,
780 "Not enough data at scanline %d (short %llu bytes)",
781 tif
->tif_row
, (unsigned long long) occ
);
787 #endif /* LZW_COMPAT */
794 LZWSetupEncode(TIFF
* tif
)
796 static const char module
[] = "LZWSetupEncode";
797 LZWCodecState
* sp
= EncoderState(tif
);
800 sp
->enc_hashtab
= (hash_t
*) _TIFFmalloc(HSIZE
*sizeof (hash_t
));
801 if (sp
->enc_hashtab
== NULL
) {
802 TIFFErrorExt(tif
->tif_clientdata
, module
,
803 "No space for LZW hash table");
810 * Reset encoding state at the start of a strip.
813 LZWPreEncode(TIFF
* tif
, uint16 s
)
815 LZWCodecState
*sp
= EncoderState(tif
);
820 if( sp
->enc_hashtab
== NULL
)
822 tif
->tif_setupencode( tif
);
825 sp
->lzw_nbits
= BITS_MIN
;
826 sp
->lzw_maxcode
= MAXCODE(BITS_MIN
);
827 sp
->lzw_free_ent
= CODE_FIRST
;
828 sp
->lzw_nextbits
= 0;
829 sp
->lzw_nextdata
= 0;
830 sp
->enc_checkpoint
= CHECK_GAP
;
833 sp
->enc_outcount
= 0;
835 * The 4 here insures there is space for 2 max-sized
836 * codes in LZWEncode and LZWPostDecode.
838 sp
->enc_rawlimit
= tif
->tif_rawdata
+ tif
->tif_rawdatasize
-1 - 4;
839 cl_hash(sp
); /* clear hash table */
840 sp
->enc_oldcode
= (hcode_t
) -1; /* generates CODE_CLEAR in LZWEncode */
844 #define CALCRATIO(sp, rat) { \
845 if (incount > 0x007fffff) { /* NB: shift will overflow */\
846 rat = outcount >> 8; \
847 rat = (rat == 0 ? 0x7fffffff : incount/rat); \
849 rat = (incount<<8) / outcount; \
852 /* Explicit 0xff masking to make icc -check=conversions happy */
853 #define PutNextCode(op, c) { \
854 nextdata = (nextdata << nbits) | c; \
856 *op++ = (unsigned char)((nextdata >> (nextbits-8))&0xff); \
858 if (nextbits >= 8) { \
859 *op++ = (unsigned char)((nextdata >> (nextbits-8))&0xff); \
866 * Encode a chunk of pixels.
868 * Uses an open addressing double hashing (no chaining) on the
869 * prefix code/next character combination. We do a variant of
870 * Knuth's algorithm D (vol. 3, sec. 6.4) along with G. Knott's
871 * relatively-prime secondary probe. Here, the modular division
872 * first probe is gives way to a faster exclusive-or manipulation.
873 * Also do block compression with an adaptive reset, whereby the
874 * code table is cleared when the compression ratio decreases,
875 * but after the table fills. The variable-length output codes
876 * are re-sized at this point, and a CODE_CLEAR is generated
880 LZWEncode(TIFF
* tif
, uint8
* bp
, tmsize_t cc
, uint16 s
)
882 register LZWCodecState
*sp
= EncoderState(tif
);
888 long incount
, outcount
, checkpoint
;
889 unsigned long nextdata
;
891 int free_ent
, maxcode
, nbits
;
899 assert(sp
->enc_hashtab
!= NULL
);
904 incount
= sp
->enc_incount
;
905 outcount
= sp
->enc_outcount
;
906 checkpoint
= sp
->enc_checkpoint
;
907 nextdata
= sp
->lzw_nextdata
;
908 nextbits
= sp
->lzw_nextbits
;
909 free_ent
= sp
->lzw_free_ent
;
910 maxcode
= sp
->lzw_maxcode
;
911 nbits
= sp
->lzw_nbits
;
913 limit
= sp
->enc_rawlimit
;
914 ent
= (hcode_t
)sp
->enc_oldcode
;
916 if (ent
== (hcode_t
) -1 && cc
> 0) {
918 * NB: This is safe because it can only happen
919 * at the start of a strip where we know there
920 * is space in the data buffer.
922 PutNextCode(op
, CODE_CLEAR
);
923 ent
= *bp
++; cc
--; incount
++;
926 c
= *bp
++; cc
--; incount
++;
927 fcode
= ((long)c
<< BITS_MAX
) + ent
;
928 h
= (c
<< HSHIFT
) ^ ent
; /* xor hashing */
931 * Check hash index for an overflow.
936 hp
= &sp
->enc_hashtab
[h
];
937 if (hp
->hash
== fcode
) {
943 * Primary hash failed, check secondary hash.
950 * Avoid pointer arithmetic because of
951 * wraparound problems with segments.
955 hp
= &sp
->enc_hashtab
[h
];
956 if (hp
->hash
== fcode
) {
960 } while (hp
->hash
>= 0);
963 * New entry, emit code and add to table.
966 * Verify there is space in the buffer for the code
967 * and any potential Clear code that might be emitted
968 * below. The value of limit is setup so that there
969 * are at least 4 bytes free--room for 2 codes.
972 tif
->tif_rawcc
= (tmsize_t
)(op
- tif
->tif_rawdata
);
974 op
= tif
->tif_rawdata
;
976 PutNextCode(op
, ent
);
978 hp
->code
= (hcode_t
)(free_ent
++);
980 if (free_ent
== CODE_MAX
-1) {
981 /* table is full, emit clear code and reset */
986 free_ent
= CODE_FIRST
;
987 PutNextCode(op
, CODE_CLEAR
);
989 maxcode
= MAXCODE(BITS_MIN
);
992 * If the next entry is going to be too big for
993 * the code size, then increase it, if possible.
995 if (free_ent
> maxcode
) {
997 assert(nbits
<= BITS_MAX
);
998 maxcode
= (int) MAXCODE(nbits
);
999 } else if (incount
>= checkpoint
) {
1002 * Check compression ratio and, if things seem
1003 * to be slipping, clear the hash table and
1004 * reset state. The compression ratio is a
1005 * 24+8-bit fractional number.
1007 checkpoint
= incount
+CHECK_GAP
;
1009 if (rat
<= sp
->enc_ratio
) {
1014 free_ent
= CODE_FIRST
;
1015 PutNextCode(op
, CODE_CLEAR
);
1017 maxcode
= MAXCODE(BITS_MIN
);
1019 sp
->enc_ratio
= rat
;
1027 * Restore global state.
1029 sp
->enc_incount
= incount
;
1030 sp
->enc_outcount
= outcount
;
1031 sp
->enc_checkpoint
= checkpoint
;
1032 sp
->enc_oldcode
= ent
;
1033 sp
->lzw_nextdata
= nextdata
;
1034 sp
->lzw_nextbits
= nextbits
;
1035 sp
->lzw_free_ent
= (unsigned short)free_ent
;
1036 sp
->lzw_maxcode
= (unsigned short)maxcode
;
1037 sp
->lzw_nbits
= (unsigned short)nbits
;
1038 tif
->tif_rawcp
= op
;
1043 * Finish off an encoded strip by flushing the last
1044 * string and tacking on an End Of Information code.
1047 LZWPostEncode(TIFF
* tif
)
1049 register LZWCodecState
*sp
= EncoderState(tif
);
1050 uint8
* op
= tif
->tif_rawcp
;
1051 long nextbits
= sp
->lzw_nextbits
;
1052 unsigned long nextdata
= sp
->lzw_nextdata
;
1053 long outcount
= sp
->enc_outcount
;
1054 int nbits
= sp
->lzw_nbits
;
1056 if (op
> sp
->enc_rawlimit
) {
1057 tif
->tif_rawcc
= (tmsize_t
)(op
- tif
->tif_rawdata
);
1058 TIFFFlushData1(tif
);
1059 op
= tif
->tif_rawdata
;
1061 if (sp
->enc_oldcode
!= (hcode_t
) -1) {
1062 PutNextCode(op
, sp
->enc_oldcode
);
1063 sp
->enc_oldcode
= (hcode_t
) -1;
1065 PutNextCode(op
, CODE_EOI
);
1066 /* Explicit 0xff masking to make icc -check=conversions happy */
1068 *op
++ = (unsigned char)((nextdata
<< (8-nextbits
))&0xff);
1069 tif
->tif_rawcc
= (tmsize_t
)(op
- tif
->tif_rawdata
);
1074 * Reset encoding hash table.
1077 cl_hash(LZWCodecState
* sp
)
1079 register hash_t
*hp
= &sp
->enc_hashtab
[HSIZE
-1];
1080 register long i
= HSIZE
-8;
1094 for (i
+= 8; i
> 0; i
--, hp
--)
1099 LZWCleanup(TIFF
* tif
)
1101 (void)TIFFPredictorCleanup(tif
);
1103 assert(tif
->tif_data
!= 0);
1105 if (DecoderState(tif
)->dec_codetab
)
1106 _TIFFfree(DecoderState(tif
)->dec_codetab
);
1108 if (EncoderState(tif
)->enc_hashtab
)
1109 _TIFFfree(EncoderState(tif
)->enc_hashtab
);
1111 _TIFFfree(tif
->tif_data
);
1112 tif
->tif_data
= NULL
;
1114 _TIFFSetDefaultCompressionState(tif
);
1118 TIFFInitLZW(TIFF
* tif
, int scheme
)
1120 static const char module
[] = "TIFFInitLZW";
1121 assert(scheme
== COMPRESSION_LZW
);
1123 * Allocate state block so tag methods have storage to record values.
1125 tif
->tif_data
= (uint8
*) _TIFFmalloc(sizeof (LZWCodecState
));
1126 if (tif
->tif_data
== NULL
)
1128 DecoderState(tif
)->dec_codetab
= NULL
;
1129 DecoderState(tif
)->dec_decode
= NULL
;
1130 EncoderState(tif
)->enc_hashtab
= NULL
;
1131 LZWState(tif
)->rw_mode
= tif
->tif_mode
;
1134 * Install codec methods.
1136 tif
->tif_fixuptags
= LZWFixupTags
;
1137 tif
->tif_setupdecode
= LZWSetupDecode
;
1138 tif
->tif_predecode
= LZWPreDecode
;
1139 tif
->tif_decoderow
= LZWDecode
;
1140 tif
->tif_decodestrip
= LZWDecode
;
1141 tif
->tif_decodetile
= LZWDecode
;
1142 tif
->tif_setupencode
= LZWSetupEncode
;
1143 tif
->tif_preencode
= LZWPreEncode
;
1144 tif
->tif_postencode
= LZWPostEncode
;
1145 tif
->tif_encoderow
= LZWEncode
;
1146 tif
->tif_encodestrip
= LZWEncode
;
1147 tif
->tif_encodetile
= LZWEncode
;
1148 tif
->tif_cleanup
= LZWCleanup
;
1150 * Setup predictor setup.
1152 (void) TIFFPredictorInit(tif
);
1155 TIFFErrorExt(tif
->tif_clientdata
, module
,
1156 "No space for LZW state block");
1161 * Copyright (c) 1985, 1986 The Regents of the University of California.
1162 * All rights reserved.
1164 * This code is derived from software contributed to Berkeley by
1165 * James A. Woods, derived from original work by Spencer Thomas
1168 * Redistribution and use in source and binary forms are permitted
1169 * provided that the above copyright notice and this paragraph are
1170 * duplicated in all such forms and that any documentation,
1171 * advertising materials, and other materials related to such
1172 * distribution and use acknowledge that the software was developed
1173 * by the University of California, Berkeley. The name of the
1174 * University may not be used to endorse or promote products derived
1175 * from this software without specific prior written permission.
1176 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
1177 * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
1178 * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
1180 #endif /* LZW_SUPPORT */
1182 /* vim: set ts=8 sts=8 sw=8 noet: */