1 /* $Id: tif_lzw.c,v 1.29.2.6 2010-06-08 18:50:42 bfriesen 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
31 * Rev 5.0 Lempel-Ziv & Welch Compression Support
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.
37 * The original Berkeley copyright notice appears below in its entirety.
39 #include "tif_predict.h"
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.
54 * Future revisions to the TIFF spec are expected to "clarify this issue".
56 #define LZW_COMPAT /* include backwards compatibility code */
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.
63 #define LZW_CHECKEOS /* include checks for strips w/o EOI code */
65 #define MAXCODE(n) ((1L<<(n))-1)
67 * The TIFF spec specifies that encoded bit
68 * strings range from 9 to 12 bits.
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 */
80 /* NB: +1024 is for compatibility with old files */
81 #define CSIZE (MAXCODE(BITS_MAX)+1024L)
83 #define CSIZE (MAXCODE(BITS_MAX)+1L)
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.
92 TIFFPredictorState predict
; /* predictor super class */
94 unsigned short nbits
; /* # of bits/code */
95 unsigned short maxcode
; /* maximum code for lzw_nbits */
96 unsigned short free_ent
; /* next free entry in hash table */
97 long nextdata
; /* next bits of i/o */
98 long nextbits
; /* # of valid bits in lzw_nextdata */
100 int rw_mode
; /* preserve rw_mode from init */
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
110 * Encoding-specific state.
112 typedef uint16 hcode_t
; /* codes fit in 16 bits */
119 * Decoding-specific state.
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 */
128 typedef int (*decodeFunc
)(TIFF
*, tidata_t
, tsize_t
, tsample_t
);
133 /* Decoding specific data */
134 long dec_nbitsmask
; /* lzw_nbits 1 bits, right adjusted */
135 long dec_restart
; /* restart count */
137 long dec_bitsleft
; /* available bits in raw data */
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 */
146 /* Encoding specific data */
147 int enc_oldcode
; /* last code encountered */
148 long enc_checkpoint
; /* point at which to clear table */
149 #define CHECK_GAP 10000 /* enc_ratio check interval */
150 long enc_ratio
; /* current compression ratio */
151 long enc_incount
; /* (input) data bytes encoded */
152 long enc_outcount
; /* encoded (output) bytes */
153 tidata_t enc_rawlimit
; /* bound on tif_rawdata buffer */
154 hash_t
* enc_hashtab
; /* kept separate for small machines */
157 #define LZWState(tif) ((LZWBaseState*) (tif)->tif_data)
158 #define DecoderState(tif) ((LZWCodecState*) LZWState(tif))
159 #define EncoderState(tif) ((LZWCodecState*) LZWState(tif))
161 static int LZWDecode(TIFF
*, tidata_t
, tsize_t
, tsample_t
);
163 static int LZWDecodeCompat(TIFF
*, tidata_t
, tsize_t
, tsample_t
);
165 static void cl_hash(LZWCodecState
*);
173 * This check shouldn't be necessary because each
174 * strip is suppose to be terminated with CODE_EOI.
176 #define NextCode(_tif, _sp, _bp, _code, _get) { \
177 if ((_sp)->dec_bitsleft < nbits) { \
178 TIFFWarningExt(_tif->tif_clientdata, _tif->tif_name, \
179 "LZWDecode: Strip %d not terminated with EOI code", \
180 _tif->tif_curstrip); \
183 _get(_sp,_bp,_code); \
184 (_sp)->dec_bitsleft -= nbits; \
188 #define NextCode(tif, sp, bp, code, get) get(sp, bp, code)
192 LZWSetupDecode(TIFF
* tif
)
194 LZWCodecState
* sp
= DecoderState(tif
);
195 static const char module
[] = " LZWSetupDecode";
201 * Allocate state block so tag methods have storage to record
204 tif
->tif_data
= (tidata_t
) _TIFFmalloc(sizeof(LZWCodecState
));
205 if (tif
->tif_data
== NULL
)
207 TIFFErrorExt(tif
->tif_clientdata
, "LZWPreDecode", "No space for LZW state block");
211 DecoderState(tif
)->dec_codetab
= NULL
;
212 DecoderState(tif
)->dec_decode
= NULL
;
215 * Setup predictor setup.
217 (void) TIFFPredictorInit(tif
);
219 sp
= DecoderState(tif
);
224 if (sp
->dec_codetab
== NULL
) {
225 sp
->dec_codetab
= (code_t
*)_TIFFmalloc(CSIZE
*sizeof (code_t
));
226 if (sp
->dec_codetab
== NULL
) {
227 TIFFErrorExt(tif
->tif_clientdata
, module
,
228 "No space for LZW code table");
232 * Pre-load the table.
236 sp
->dec_codetab
[code
].value
= code
;
237 sp
->dec_codetab
[code
].firstchar
= code
;
238 sp
->dec_codetab
[code
].length
= 1;
239 sp
->dec_codetab
[code
].next
= NULL
;
242 * Zero-out the unused entries
244 _TIFFmemset(&sp
->dec_codetab
[CODE_CLEAR
], 0,
245 (CODE_FIRST
- CODE_CLEAR
) * sizeof (code_t
));
251 * Setup state for decoding a strip.
254 LZWPreDecode(TIFF
* tif
, tsample_t s
)
256 LZWCodecState
*sp
= DecoderState(tif
);
260 if( sp
->dec_codetab
== NULL
)
262 tif
->tif_setupdecode( tif
);
266 * Check for old bit-reversed codes.
268 if (tif
->tif_rawdata
[0] == 0 && (tif
->tif_rawdata
[1] & 0x1)) {
270 if (!sp
->dec_decode
) {
271 TIFFWarningExt(tif
->tif_clientdata
, tif
->tif_name
,
272 "Old-style LZW codes, convert file");
274 * Override default decoding methods with
275 * ones that deal with the old coding.
276 * Otherwise the predictor versions set
277 * above will call the compatibility routines
278 * through the dec_decode method.
280 tif
->tif_decoderow
= LZWDecodeCompat
;
281 tif
->tif_decodestrip
= LZWDecodeCompat
;
282 tif
->tif_decodetile
= LZWDecodeCompat
;
284 * If doing horizontal differencing, must
285 * re-setup the predictor logic since we
286 * switched the basic decoder methods...
288 (*tif
->tif_setupdecode
)(tif
);
289 sp
->dec_decode
= LZWDecodeCompat
;
291 sp
->lzw_maxcode
= MAXCODE(BITS_MIN
);
292 #else /* !LZW_COMPAT */
293 if (!sp
->dec_decode
) {
294 TIFFErrorExt(tif
->tif_clientdata
, tif
->tif_name
,
295 "Old-style LZW codes not supported");
296 sp
->dec_decode
= LZWDecode
;
299 #endif/* !LZW_COMPAT */
301 sp
->lzw_maxcode
= MAXCODE(BITS_MIN
)-1;
302 sp
->dec_decode
= LZWDecode
;
304 sp
->lzw_nbits
= BITS_MIN
;
305 sp
->lzw_nextbits
= 0;
306 sp
->lzw_nextdata
= 0;
309 sp
->dec_nbitsmask
= MAXCODE(BITS_MIN
);
311 sp
->dec_bitsleft
= tif
->tif_rawcc
<< 3;
313 sp
->dec_free_entp
= sp
->dec_codetab
+ CODE_FIRST
;
315 * Zero entries that are not yet filled in. We do
316 * this to guard against bogus input data that causes
317 * us to index into undefined entries. If you can
318 * come up with a way to safely bounds-check input codes
319 * while decoding then you can remove this operation.
321 _TIFFmemset(sp
->dec_free_entp
, 0, (CSIZE
-CODE_FIRST
)*sizeof (code_t
));
322 sp
->dec_oldcodep
= &sp
->dec_codetab
[-1];
323 sp
->dec_maxcodep
= &sp
->dec_codetab
[sp
->dec_nbitsmask
-1];
328 * Decode a "hunk of data".
330 #define GetNextCode(sp, bp, code) { \
331 nextdata = (nextdata<<8) | *(bp)++; \
333 if (nextbits < nbits) { \
334 nextdata = (nextdata<<8) | *(bp)++; \
337 code = (hcode_t)((nextdata >> (nextbits-nbits)) & nbitsmask); \
344 TIFFErrorExt(tif
->tif_clientdata
, tif
->tif_name
,
345 "LZWDecode: Bogus encoding, loop in the code table; scanline %d",
350 LZWDecode(TIFF
* tif
, tidata_t op0
, tsize_t occ0
, tsample_t s
)
352 LZWCodecState
*sp
= DecoderState(tif
);
353 char *op
= (char*) op0
;
354 long occ
= (long) occ0
;
359 long nbits
, nextbits
, nextdata
, nbitsmask
;
360 code_t
*codep
, *free_entp
, *maxcodep
, *oldcodep
;
364 assert(sp
->dec_codetab
!= NULL
);
366 * Restart interrupted output operation.
368 if (sp
->dec_restart
) {
371 codep
= sp
->dec_codep
;
372 residue
= codep
->length
- sp
->dec_restart
;
375 * Residue from previous decode is sufficient
376 * to satisfy decode request. Skip to the
377 * start of the decoded string, place decoded
378 * values in the output buffer, and return.
380 sp
->dec_restart
+= occ
;
383 } while (--residue
> occ
&& codep
);
387 *--tp
= codep
->value
;
389 } while (--occ
&& codep
);
394 * Residue satisfies only part of the decode request.
396 op
+= residue
, occ
-= residue
;
404 } while (--residue
&& codep
);
408 bp
= (unsigned char *)tif
->tif_rawcp
;
409 nbits
= sp
->lzw_nbits
;
410 nextdata
= sp
->lzw_nextdata
;
411 nextbits
= sp
->lzw_nextbits
;
412 nbitsmask
= sp
->dec_nbitsmask
;
413 oldcodep
= sp
->dec_oldcodep
;
414 free_entp
= sp
->dec_free_entp
;
415 maxcodep
= sp
->dec_maxcodep
;
418 NextCode(tif
, sp
, bp
, code
, GetNextCode
);
419 if (code
== CODE_EOI
)
421 if (code
== CODE_CLEAR
) {
422 free_entp
= sp
->dec_codetab
+ CODE_FIRST
;
423 _TIFFmemset(free_entp
, 0,
424 (CSIZE
- CODE_FIRST
) * sizeof (code_t
));
426 nbitsmask
= MAXCODE(BITS_MIN
);
427 maxcodep
= sp
->dec_codetab
+ nbitsmask
-1;
428 NextCode(tif
, sp
, bp
, code
, GetNextCode
);
429 if (code
== CODE_EOI
)
431 if (code
== CODE_CLEAR
) {
432 TIFFErrorExt(tif
->tif_clientdata
, tif
->tif_name
,
433 "LZWDecode: Corrupted LZW table at scanline %d",
437 *op
++ = (char)code
, occ
--;
438 oldcodep
= sp
->dec_codetab
+ code
;
441 codep
= sp
->dec_codetab
+ code
;
444 * Add the new entry to the code table.
446 if (free_entp
< &sp
->dec_codetab
[0] ||
447 free_entp
>= &sp
->dec_codetab
[CSIZE
]) {
448 TIFFErrorExt(tif
->tif_clientdata
, tif
->tif_name
,
449 "LZWDecode: Corrupted LZW table at scanline %d",
454 free_entp
->next
= oldcodep
;
455 if (free_entp
->next
< &sp
->dec_codetab
[0] ||
456 free_entp
->next
>= &sp
->dec_codetab
[CSIZE
]) {
457 TIFFErrorExt(tif
->tif_clientdata
, tif
->tif_name
,
458 "LZWDecode: Corrupted LZW table at scanline %d",
462 free_entp
->firstchar
= free_entp
->next
->firstchar
;
463 free_entp
->length
= free_entp
->next
->length
+1;
464 free_entp
->value
= (codep
< free_entp
) ?
465 codep
->firstchar
: free_entp
->firstchar
;
466 if (++free_entp
> maxcodep
) {
467 if (++nbits
> BITS_MAX
) /* should not happen */
469 nbitsmask
= MAXCODE(nbits
);
470 maxcodep
= sp
->dec_codetab
+ nbitsmask
-1;
475 * Code maps to a string, copy string
476 * value to output (written in reverse).
478 if(codep
->length
== 0) {
479 TIFFErrorExt(tif
->tif_clientdata
, tif
->tif_name
,
480 "LZWDecode: Wrong length of decoded string: "
481 "data probably corrupted at scanline %d",
485 if (codep
->length
> occ
) {
487 * String is too long for decode buffer,
488 * locate portion that will fit, copy to
489 * the decode buffer, and setup restart
490 * logic for the next decoding call.
492 sp
->dec_codep
= codep
;
495 } while (codep
&& codep
->length
> occ
);
497 sp
->dec_restart
= occ
;
500 *--tp
= codep
->value
;
502 } while (--occ
&& codep
);
516 } while (codep
&& tp
> op
);
521 op
+= len
, occ
-= len
;
523 *op
++ = (char)code
, occ
--;
526 tif
->tif_rawcp
= (tidata_t
) bp
;
527 sp
->lzw_nbits
= (unsigned short) nbits
;
528 sp
->lzw_nextdata
= nextdata
;
529 sp
->lzw_nextbits
= nextbits
;
530 sp
->dec_nbitsmask
= nbitsmask
;
531 sp
->dec_oldcodep
= oldcodep
;
532 sp
->dec_free_entp
= free_entp
;
533 sp
->dec_maxcodep
= maxcodep
;
536 TIFFErrorExt(tif
->tif_clientdata
, tif
->tif_name
,
537 "LZWDecode: Not enough data at scanline %d (short %ld bytes)",
546 * Decode a "hunk of data" for old images.
548 #define GetNextCodeCompat(sp, bp, code) { \
549 nextdata |= (unsigned long) *(bp)++ << nextbits; \
551 if (nextbits < nbits) { \
552 nextdata |= (unsigned long) *(bp)++ << nextbits;\
555 code = (hcode_t)(nextdata & nbitsmask); \
556 nextdata >>= nbits; \
561 LZWDecodeCompat(TIFF
* tif
, tidata_t op0
, tsize_t occ0
, tsample_t s
)
563 LZWCodecState
*sp
= DecoderState(tif
);
564 char *op
= (char*) op0
;
565 long occ
= (long) occ0
;
569 long nextbits
, nextdata
, nbitsmask
;
570 code_t
*codep
, *free_entp
, *maxcodep
, *oldcodep
;
575 * Restart interrupted output operation.
577 if (sp
->dec_restart
) {
580 codep
= sp
->dec_codep
;
581 residue
= codep
->length
- sp
->dec_restart
;
584 * Residue from previous decode is sufficient
585 * to satisfy decode request. Skip to the
586 * start of the decoded string, place decoded
587 * values in the output buffer, and return.
589 sp
->dec_restart
+= occ
;
592 } while (--residue
> occ
);
595 *--tp
= codep
->value
;
601 * Residue satisfies only part of the decode request.
603 op
+= residue
, occ
-= residue
;
606 *--tp
= codep
->value
;
612 bp
= (unsigned char *)tif
->tif_rawcp
;
613 nbits
= sp
->lzw_nbits
;
614 nextdata
= sp
->lzw_nextdata
;
615 nextbits
= sp
->lzw_nextbits
;
616 nbitsmask
= sp
->dec_nbitsmask
;
617 oldcodep
= sp
->dec_oldcodep
;
618 free_entp
= sp
->dec_free_entp
;
619 maxcodep
= sp
->dec_maxcodep
;
622 NextCode(tif
, sp
, bp
, code
, GetNextCodeCompat
);
623 if (code
== CODE_EOI
)
625 if (code
== CODE_CLEAR
) {
626 free_entp
= sp
->dec_codetab
+ CODE_FIRST
;
627 _TIFFmemset(free_entp
, 0,
628 (CSIZE
- CODE_FIRST
) * sizeof (code_t
));
630 nbitsmask
= MAXCODE(BITS_MIN
);
631 maxcodep
= sp
->dec_codetab
+ nbitsmask
;
632 NextCode(tif
, sp
, bp
, code
, GetNextCodeCompat
);
633 if (code
== CODE_EOI
)
635 if (code
== CODE_CLEAR
) {
636 TIFFErrorExt(tif
->tif_clientdata
, tif
->tif_name
,
637 "LZWDecode: Corrupted LZW table at scanline %d",
642 oldcodep
= sp
->dec_codetab
+ code
;
645 codep
= sp
->dec_codetab
+ code
;
648 * Add the new entry to the code table.
650 if (free_entp
< &sp
->dec_codetab
[0] ||
651 free_entp
>= &sp
->dec_codetab
[CSIZE
]) {
652 TIFFErrorExt(tif
->tif_clientdata
, tif
->tif_name
,
653 "LZWDecodeCompat: Corrupted LZW table at scanline %d",
658 free_entp
->next
= oldcodep
;
659 if (free_entp
->next
< &sp
->dec_codetab
[0] ||
660 free_entp
->next
>= &sp
->dec_codetab
[CSIZE
]) {
661 TIFFErrorExt(tif
->tif_clientdata
, tif
->tif_name
,
662 "LZWDecodeCompat: Corrupted LZW table at scanline %d",
666 free_entp
->firstchar
= free_entp
->next
->firstchar
;
667 free_entp
->length
= free_entp
->next
->length
+1;
668 free_entp
->value
= (codep
< free_entp
) ?
669 codep
->firstchar
: free_entp
->firstchar
;
670 if (++free_entp
> maxcodep
) {
671 if (++nbits
> BITS_MAX
) /* should not happen */
673 nbitsmask
= MAXCODE(nbits
);
674 maxcodep
= sp
->dec_codetab
+ nbitsmask
;
680 * Code maps to a string, copy string
681 * value to output (written in reverse).
683 if(codep
->length
== 0) {
684 TIFFErrorExt(tif
->tif_clientdata
, tif
->tif_name
,
685 "LZWDecodeCompat: Wrong length of decoded "
686 "string: data probably corrupted at scanline %d",
690 if (codep
->length
> occ
) {
692 * String is too long for decode buffer,
693 * locate portion that will fit, copy to
694 * the decode buffer, and setup restart
695 * logic for the next decoding call.
697 sp
->dec_codep
= codep
;
700 } while (codep
->length
> occ
);
701 sp
->dec_restart
= occ
;
704 *--tp
= codep
->value
;
709 op
+= codep
->length
, occ
-= codep
->length
;
712 *--tp
= codep
->value
;
713 } while( (codep
= codep
->next
) != NULL
&& tp
> op_orig
);
718 tif
->tif_rawcp
= (tidata_t
) bp
;
719 sp
->lzw_nbits
= nbits
;
720 sp
->lzw_nextdata
= nextdata
;
721 sp
->lzw_nextbits
= nextbits
;
722 sp
->dec_nbitsmask
= nbitsmask
;
723 sp
->dec_oldcodep
= oldcodep
;
724 sp
->dec_free_entp
= free_entp
;
725 sp
->dec_maxcodep
= maxcodep
;
728 TIFFErrorExt(tif
->tif_clientdata
, tif
->tif_name
,
729 "LZWDecodeCompat: Not enough data at scanline %d (short %ld bytes)",
735 #endif /* LZW_COMPAT */
742 LZWSetupEncode(TIFF
* tif
)
744 LZWCodecState
* sp
= EncoderState(tif
);
745 static const char module
[] = "LZWSetupEncode";
748 sp
->enc_hashtab
= (hash_t
*) _TIFFmalloc(HSIZE
*sizeof (hash_t
));
749 if (sp
->enc_hashtab
== NULL
) {
750 TIFFErrorExt(tif
->tif_clientdata
, module
, "No space for LZW hash table");
757 * Reset encoding state at the start of a strip.
760 LZWPreEncode(TIFF
* tif
, tsample_t s
)
762 LZWCodecState
*sp
= EncoderState(tif
);
767 if( sp
->enc_hashtab
== NULL
)
769 tif
->tif_setupencode( tif
);
772 sp
->lzw_nbits
= BITS_MIN
;
773 sp
->lzw_maxcode
= MAXCODE(BITS_MIN
);
774 sp
->lzw_free_ent
= CODE_FIRST
;
775 sp
->lzw_nextbits
= 0;
776 sp
->lzw_nextdata
= 0;
777 sp
->enc_checkpoint
= CHECK_GAP
;
780 sp
->enc_outcount
= 0;
782 * The 4 here insures there is space for 2 max-sized
783 * codes in LZWEncode and LZWPostDecode.
785 sp
->enc_rawlimit
= tif
->tif_rawdata
+ tif
->tif_rawdatasize
-1 - 4;
786 cl_hash(sp
); /* clear hash table */
787 sp
->enc_oldcode
= (hcode_t
) -1; /* generates CODE_CLEAR in LZWEncode */
791 #define CALCRATIO(sp, rat) { \
792 if (incount > 0x007fffff) { /* NB: shift will overflow */\
793 rat = outcount >> 8; \
794 rat = (rat == 0 ? 0x7fffffff : incount/rat); \
796 rat = (incount<<8) / outcount; \
798 #define PutNextCode(op, c) { \
799 nextdata = (nextdata << nbits) | c; \
801 *op++ = (unsigned char)(nextdata >> (nextbits-8)); \
803 if (nextbits >= 8) { \
804 *op++ = (unsigned char)(nextdata >> (nextbits-8)); \
811 * Encode a chunk of pixels.
813 * Uses an open addressing double hashing (no chaining) on the
814 * prefix code/next character combination. We do a variant of
815 * Knuth's algorithm D (vol. 3, sec. 6.4) along with G. Knott's
816 * relatively-prime secondary probe. Here, the modular division
817 * first probe is gives way to a faster exclusive-or manipulation.
818 * Also do block compression with an adaptive reset, whereby the
819 * code table is cleared when the compression ratio decreases,
820 * but after the table fills. The variable-length output codes
821 * are re-sized at this point, and a CODE_CLEAR is generated
825 LZWEncode(TIFF
* tif
, tidata_t bp
, tsize_t cc
, tsample_t s
)
827 register LZWCodecState
*sp
= EncoderState(tif
);
833 long incount
, outcount
, checkpoint
;
834 long nextdata
, nextbits
;
835 int free_ent
, maxcode
, nbits
;
842 assert(sp
->enc_hashtab
!= NULL
);
847 incount
= sp
->enc_incount
;
848 outcount
= sp
->enc_outcount
;
849 checkpoint
= sp
->enc_checkpoint
;
850 nextdata
= sp
->lzw_nextdata
;
851 nextbits
= sp
->lzw_nextbits
;
852 free_ent
= sp
->lzw_free_ent
;
853 maxcode
= sp
->lzw_maxcode
;
854 nbits
= sp
->lzw_nbits
;
856 limit
= sp
->enc_rawlimit
;
857 ent
= sp
->enc_oldcode
;
859 if (ent
== (hcode_t
) -1 && cc
> 0) {
861 * NB: This is safe because it can only happen
862 * at the start of a strip where we know there
863 * is space in the data buffer.
865 PutNextCode(op
, CODE_CLEAR
);
866 ent
= *bp
++; cc
--; incount
++;
869 c
= *bp
++; cc
--; incount
++;
870 fcode
= ((long)c
<< BITS_MAX
) + ent
;
871 h
= (c
<< HSHIFT
) ^ ent
; /* xor hashing */
874 * Check hash index for an overflow.
879 hp
= &sp
->enc_hashtab
[h
];
880 if (hp
->hash
== fcode
) {
886 * Primary hash failed, check secondary hash.
893 * Avoid pointer arithmetic 'cuz of
894 * wraparound problems with segments.
898 hp
= &sp
->enc_hashtab
[h
];
899 if (hp
->hash
== fcode
) {
903 } while (hp
->hash
>= 0);
906 * New entry, emit code and add to table.
909 * Verify there is space in the buffer for the code
910 * and any potential Clear code that might be emitted
911 * below. The value of limit is setup so that there
912 * are at least 4 bytes free--room for 2 codes.
915 tif
->tif_rawcc
= (tsize_t
)(op
- tif
->tif_rawdata
);
917 op
= tif
->tif_rawdata
;
919 PutNextCode(op
, ent
);
921 hp
->code
= free_ent
++;
923 if (free_ent
== CODE_MAX
-1) {
924 /* table is full, emit clear code and reset */
929 free_ent
= CODE_FIRST
;
930 PutNextCode(op
, CODE_CLEAR
);
932 maxcode
= MAXCODE(BITS_MIN
);
935 * If the next entry is going to be too big for
936 * the code size, then increase it, if possible.
938 if (free_ent
> maxcode
) {
940 assert(nbits
<= BITS_MAX
);
941 maxcode
= (int) MAXCODE(nbits
);
942 } else if (incount
>= checkpoint
) {
945 * Check compression ratio and, if things seem
946 * to be slipping, clear the hash table and
947 * reset state. The compression ratio is a
948 * 24+8-bit fractional number.
950 checkpoint
= incount
+CHECK_GAP
;
952 if (rat
<= sp
->enc_ratio
) {
957 free_ent
= CODE_FIRST
;
958 PutNextCode(op
, CODE_CLEAR
);
960 maxcode
= MAXCODE(BITS_MIN
);
970 * Restore global state.
972 sp
->enc_incount
= incount
;
973 sp
->enc_outcount
= outcount
;
974 sp
->enc_checkpoint
= checkpoint
;
975 sp
->enc_oldcode
= ent
;
976 sp
->lzw_nextdata
= nextdata
;
977 sp
->lzw_nextbits
= nextbits
;
978 sp
->lzw_free_ent
= free_ent
;
979 sp
->lzw_maxcode
= maxcode
;
980 sp
->lzw_nbits
= nbits
;
986 * Finish off an encoded strip by flushing the last
987 * string and tacking on an End Of Information code.
990 LZWPostEncode(TIFF
* tif
)
992 register LZWCodecState
*sp
= EncoderState(tif
);
993 tidata_t op
= tif
->tif_rawcp
;
994 long nextbits
= sp
->lzw_nextbits
;
995 long nextdata
= sp
->lzw_nextdata
;
996 long outcount
= sp
->enc_outcount
;
997 int nbits
= sp
->lzw_nbits
;
999 if (op
> sp
->enc_rawlimit
) {
1000 tif
->tif_rawcc
= (tsize_t
)(op
- tif
->tif_rawdata
);
1001 TIFFFlushData1(tif
);
1002 op
= tif
->tif_rawdata
;
1004 if (sp
->enc_oldcode
!= (hcode_t
) -1) {
1005 PutNextCode(op
, sp
->enc_oldcode
);
1006 sp
->enc_oldcode
= (hcode_t
) -1;
1008 PutNextCode(op
, CODE_EOI
);
1010 *op
++ = (unsigned char)(nextdata
<< (8-nextbits
));
1011 tif
->tif_rawcc
= (tsize_t
)(op
- tif
->tif_rawdata
);
1016 * Reset encoding hash table.
1019 cl_hash(LZWCodecState
* sp
)
1021 register hash_t
*hp
= &sp
->enc_hashtab
[HSIZE
-1];
1022 register long i
= HSIZE
-8;
1036 for (i
+= 8; i
> 0; i
--, hp
--)
1041 LZWCleanup(TIFF
* tif
)
1043 (void)TIFFPredictorCleanup(tif
);
1045 assert(tif
->tif_data
!= 0);
1047 if (DecoderState(tif
)->dec_codetab
)
1048 _TIFFfree(DecoderState(tif
)->dec_codetab
);
1050 if (EncoderState(tif
)->enc_hashtab
)
1051 _TIFFfree(EncoderState(tif
)->enc_hashtab
);
1053 _TIFFfree(tif
->tif_data
);
1054 tif
->tif_data
= NULL
;
1056 _TIFFSetDefaultCompressionState(tif
);
1060 TIFFInitLZW(TIFF
* tif
, int scheme
)
1062 assert(scheme
== COMPRESSION_LZW
);
1064 * Allocate state block so tag methods have storage to record values.
1066 tif
->tif_data
= (tidata_t
) _TIFFmalloc(sizeof (LZWCodecState
));
1067 if (tif
->tif_data
== NULL
)
1069 DecoderState(tif
)->dec_codetab
= NULL
;
1070 DecoderState(tif
)->dec_decode
= NULL
;
1071 EncoderState(tif
)->enc_hashtab
= NULL
;
1072 LZWState(tif
)->rw_mode
= tif
->tif_mode
;
1075 * Install codec methods.
1077 tif
->tif_setupdecode
= LZWSetupDecode
;
1078 tif
->tif_predecode
= LZWPreDecode
;
1079 tif
->tif_decoderow
= LZWDecode
;
1080 tif
->tif_decodestrip
= LZWDecode
;
1081 tif
->tif_decodetile
= LZWDecode
;
1082 tif
->tif_setupencode
= LZWSetupEncode
;
1083 tif
->tif_preencode
= LZWPreEncode
;
1084 tif
->tif_postencode
= LZWPostEncode
;
1085 tif
->tif_encoderow
= LZWEncode
;
1086 tif
->tif_encodestrip
= LZWEncode
;
1087 tif
->tif_encodetile
= LZWEncode
;
1088 tif
->tif_cleanup
= LZWCleanup
;
1090 * Setup predictor setup.
1092 (void) TIFFPredictorInit(tif
);
1095 TIFFErrorExt(tif
->tif_clientdata
, "TIFFInitLZW",
1096 "No space for LZW state block");
1101 * Copyright (c) 1985, 1986 The Regents of the University of California.
1102 * All rights reserved.
1104 * This code is derived from software contributed to Berkeley by
1105 * James A. Woods, derived from original work by Spencer Thomas
1108 * Redistribution and use in source and binary forms are permitted
1109 * provided that the above copyright notice and this paragraph are
1110 * duplicated in all such forms and that any documentation,
1111 * advertising materials, and other materials related to such
1112 * distribution and use acknowledge that the software was developed
1113 * by the University of California, Berkeley. The name of the
1114 * University may not be used to endorse or promote products derived
1115 * from this software without specific prior written permission.
1116 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
1117 * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
1118 * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
1120 #endif /* LZW_SUPPORT */
1122 /* vim: set ts=8 sts=8 sw=8 noet: */