1 #ifndef lint
2 static char rcsid[] = "$Header: /usr/people/sam/tiff/libtiff/RCS/tif_lzw.c,v 1.37 92/02/12 11:27:28 sam Exp $";
3 #endif
4
5 /*
6 * Copyright (c) 1988, 1989, 1990, 1991, 1992 Sam Leffler
7 * Copyright (c) 1991, 1992 Silicon Graphics, Inc.
8 *
9 * Permission to use, copy, modify, distribute, and sell this software and
10 * its documentation for any purpose is hereby granted without fee, provided
11 * that (i) the above copyright notices and this permission notice appear in
12 * all copies of the software and related documentation, and (ii) the names of
13 * Sam Leffler and Silicon Graphics may not be used in any advertising or
14 * publicity relating to the software without the specific, prior written
15 * permission of Sam Leffler and Silicon Graphics.
16 *
17 * THE SOFTWARE IS PROVIDED "AS-IS" AND WITHOUT WARRANTY OF ANY KIND,
18 * EXPRESS, IMPLIED OR OTHERWISE, INCLUDING WITHOUT LIMITATION, ANY
19 * WARRANTY OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
20 *
21 * IN NO EVENT SHALL SAM LEFFLER OR SILICON GRAPHICS BE LIABLE FOR
22 * ANY SPECIAL, INCIDENTAL, INDIRECT OR CONSEQUENTIAL DAMAGES OF ANY KIND,
23 * OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
24 * WHETHER OR NOT ADVISED OF THE POSSIBILITY OF DAMAGE, AND ON ANY THEORY OF
25 * LIABILITY, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE
26 * OF THIS SOFTWARE.
27 */
28
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 "tiffioP.h"
40 #include <stdio.h>
41 #include <assert.h>
42 #include "prototypes.h"
43
44 #define MAXCODE(n) ((1 << (n)) - 1)
45 /*
46 * The TIFF spec specifies that encoded bit strings range
47 * from 9 to 12 bits. This is somewhat unfortunate in that
48 * experience indicates full color RGB pictures often need
49 * ~14 bits for reasonable compression.
50 */
51 #define BITS_MIN 9 /* start with 9 bits */
52 #define BITS_MAX 12 /* max of 12 bit strings */
53 /* predefined codes */
54 #define CODE_CLEAR 256 /* code to clear string table */
55 #define CODE_EOI 257 /* end-of-information code */
56 #define CODE_FIRST 258 /* first free code entry */
57 #define CODE_MAX MAXCODE(BITS_MAX)
58 #ifdef notdef
59 #define HSIZE 9001 /* 91% occupancy */
60 #define HSHIFT (8-(16-13))
61 #else
62 #define HSIZE 5003 /* 80% occupancy */
63 #define HSHIFT (8-(16-12))
64 #endif
65
66 /*
67 * NB: The 5.0 spec describes a different algorithm than Aldus
68 * implements. Specifically, Aldus does code length transitions
69 * one code earlier than should be done (for real LZW).
70 * Earlier versions of this library implemented the correct
71 * LZW algorithm, but emitted codes in a bit order opposite
72 * to the TIFF spec. Thus, to maintain compatibility w/ Aldus
73 * we interpret MSB-LSB ordered codes to be images written w/
74 * old versions of this library, but otherwise adhere to the
75 * Aldus "off by one" algorithm.
76 *
77 * Future revisions to the TIFF spec are expected to "clarify this issue".
78 */
79 #define SetMaxCode(sp, v) { \
80 (sp)->lzw_maxcode = (v)-1; \
81 if ((sp)->lzw_flags & LZW_COMPAT) \
82 (sp)->lzw_maxcode++; \
83 }
84
85 /*
86 * Decoding-specific state.
87 */
88 struct decode {
89 short prefixtab[HSIZE]; /* prefix(code) */
90 u_char suffixtab[CODE_MAX+1]; /* suffix(code) */
91 u_char stack[HSIZE-(CODE_MAX+1)];
92 u_char *stackp; /* stack pointer */
93 int firstchar; /* of string associated w/ last code */
94 };
95
96 /*
97 * Encoding-specific state.
98 */
99 struct encode {
100 long checkpoint; /* point at which to clear table */
101 #define CHECK_GAP 10000 /* enc_ratio check interval */
102 long ratio; /* current compression ratio */
103 long incount; /* (input) data bytes encoded */
104 long outcount; /* encoded (output) bytes */
105 long htab[HSIZE]; /* hash table */
106 short codetab[HSIZE]; /* code table */
107 };
108
109 #if USE_PROTOTYPES
110 typedef void (*predictorFunc)(char* data, int nbytes, int stride);
111 #else
112 typedef void (*predictorFunc)();
113 #endif
114
115 /*
116 * State block for each open TIFF
117 * file using LZW compression/decompression.
118 */
119 typedef struct {
120 int lzw_oldcode; /* last code encountered */
121 u_short lzw_flags;
122 #define LZW_RESTART 0x01 /* restart interrupted decode */
123 #define LZW_COMPAT 0x02 /* read old bit-reversed codes */
124 u_short lzw_nbits; /* number of bits/code */
125 u_short lzw_stride; /* horizontal diferencing stride */
126 u_short lzw_rowsize; /* XXX maybe should be a long? */
127 predictorFunc lzw_hordiff;
128 int lzw_maxcode; /* maximum code for lzw_nbits */
129 long lzw_bitoff; /* bit offset into data */
130 long lzw_bitsize; /* size of strip in bits */
131 int lzw_free_ent; /* next free entry in hash table */
132 union {
133 struct decode dec;
134 struct encode enc;
135 } u;
136 } LZWState;
137 #define dec_prefix u.dec.prefixtab
138 #define dec_suffix u.dec.suffixtab
139 #define dec_stack u.dec.stack
140 #define dec_stackp u.dec.stackp
141 #define dec_firstchar u.dec.firstchar
142
143 #define enc_checkpoint u.enc.checkpoint
144 #define enc_ratio u.enc.ratio
145 #define enc_incount u.enc.incount
146 #define enc_outcount u.enc.outcount
147 #define enc_htab u.enc.htab
148 #define enc_codetab u.enc.codetab
149
150 /* masks for extracting/inserting variable length bit codes */
151 static const u_char rmask[9] =
152 { 0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff };
153 static const u_char lmask[9] =
154 { 0x00, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe, 0xff };
155
156 #if USE_PROTOTYPES
157 static int LZWPreEncode(TIFF*);
158 static int LZWEncode(TIFF*, u_char*, int, u_int);
159 static int LZWEncodePredRow(TIFF*, u_char*, int, u_int);
160 static int LZWEncodePredTile(TIFF*, u_char*, int, u_int);
161 static int LZWPostEncode(TIFF*);
162 static int LZWDecode(TIFF*, u_char*, int, u_int);
163 static int LZWDecodePredRow(TIFF*, u_char*, int, u_int);
164 static int LZWDecodePredTile(TIFF*, u_char*, int, u_int);
165 static int LZWPreDecode(TIFF*);
166 static int LZWCleanup(TIFF*);
167 static int GetNextCode(TIFF*);
168 static void PutNextCode(TIFF*, int);
169 static void cl_block(TIFF*);
170 static void cl_hash(LZWState*);
171 extern int TIFFFlushData1(TIFF *);
172 #else
173 static int LZWPreEncode(), LZWEncode(), LZWPostEncode();
174 static int LZWEncodePredRow(), LZWEncodePredTile();
175 static int LZWPreDecode(), LZWDecode();
176 static int LZWDecodePredRow(), LZWDecodePredTile();
177 static int LZWCleanup();
178 static int GetNextCode();
179 static void PutNextCode();
180 static void cl_block();
181 static void cl_hash();
182 extern int TIFFFlushData1();
183 #endif
184
TIFFInitLZW(tif)185 TIFFInitLZW(tif)
186 TIFF *tif;
187 {
188 tif->tif_predecode = LZWPreDecode;
189 tif->tif_decoderow = LZWDecode;
190 tif->tif_decodestrip = LZWDecode;
191 tif->tif_decodetile = LZWDecode;
192 tif->tif_preencode = LZWPreEncode;
193 tif->tif_postencode = LZWPostEncode;
194 tif->tif_encoderow = LZWEncode;
195 tif->tif_encodestrip = LZWEncode;
196 tif->tif_encodetile = LZWEncode;
197 tif->tif_cleanup = LZWCleanup;
198 return (1);
199 }
200
201 static
DECLARE4(LZWCheckPredictor,TIFF *,tif,LZWState *,sp,predictorFunc,pred8bit,predictorFunc,pred16bit)202 DECLARE4(LZWCheckPredictor,
203 TIFF*, tif,
204 LZWState*, sp,
205 predictorFunc, pred8bit,
206 predictorFunc, pred16bit
207 )
208 {
209 TIFFDirectory *td = &tif->tif_dir;
210
211 switch (td->td_predictor) {
212 case 1:
213 break;
214 case 2:
215 sp->lzw_stride = (td->td_planarconfig == PLANARCONFIG_CONTIG ?
216 td->td_samplesperpixel : 1);
217 switch (td->td_bitspersample) {
218 case 8:
219 sp->lzw_hordiff = pred8bit;
220 break;
221 case 16:
222 sp->lzw_hordiff = pred16bit;
223 break;
224 default:
225 TIFFError(tif->tif_name,
226 "Horizontal differencing \"Predictor\" not supported with %d-bit samples",
227 td->td_bitspersample);
228 return (0);
229 }
230 break;
231 default:
232 TIFFError(tif->tif_name, "\"Predictor\" value %d not supported",
233 td->td_predictor);
234 return (0);
235 }
236 if (sp->lzw_hordiff) {
237 /*
238 * Calculate the scanline/tile-width size in bytes.
239 */
240 if (isTiled(tif))
241 sp->lzw_rowsize = TIFFTileRowSize(tif);
242 else
243 sp->lzw_rowsize = TIFFScanlineSize(tif);
244 }
245 return (1);
246 }
247
248 /*
249 * LZW Decoder.
250 */
251
252 #define REPEAT4(n, op) \
253 switch (n) { \
254 default: { int i; for (i = n-4; i > 0; i--) { op; } } \
255 case 4: op; \
256 case 3: op; \
257 case 2: op; \
258 case 1: op; \
259 case 0: ; \
260 }
261
262 static void
DECLARE3(horizontalAccumulate8,register char *,cp,register int,cc,register int,stride)263 DECLARE3(horizontalAccumulate8,
264 register char*, cp,
265 register int, cc,
266 register int, stride
267 )
268 {
269 if (cc > stride) {
270 cc -= stride;
271 do {
272 REPEAT4(stride, cp[stride] += cp[0]; cp++)
273 cc -= stride;
274 } while (cc > 0);
275 }
276 }
277
278 static void
DECLARE3(horizontalAccumulate16,char *,cp,int,cc,register int,stride)279 DECLARE3(horizontalAccumulate16,
280 char*, cp,
281 int, cc,
282 register int, stride
283 )
284 {
285 register short* wp = (short *)cp;
286 register int wc = cc / 2;
287
288 if (wc > stride) {
289 wc -= stride;
290 do {
291 REPEAT4(stride, wp[stride] += wp[0]; wp++)
292 wc -= stride;
293 } while (wc > 0);
294 }
295 }
296
297 /*
298 * Setup state for decoding a strip.
299 */
300 static
LZWPreDecode(tif)301 LZWPreDecode(tif)
302 TIFF *tif;
303 {
304 register LZWState *sp = (LZWState *)tif->tif_data;
305 register int code;
306
307 if (sp == NULL) {
308 tif->tif_data = malloc(sizeof (LZWState));
309 if (tif->tif_data == NULL) {
310 TIFFError("LZWPreDecode",
311 "No space for LZW state block");
312 return (0);
313 }
314 sp = (LZWState *)tif->tif_data;
315 sp->lzw_flags = 0;
316 sp->lzw_hordiff = 0;
317 sp->lzw_rowsize = 0;
318 if (!LZWCheckPredictor(tif, sp,
319 horizontalAccumulate8, horizontalAccumulate16))
320 return (0);
321 if (sp->lzw_hordiff) {
322 /*
323 * Override default decoding method with
324 * one that does the predictor stuff.
325 */
326 tif->tif_decoderow = LZWDecodePredRow;
327 tif->tif_decodestrip = LZWDecodePredTile;
328 tif->tif_decodetile = LZWDecodePredTile;
329 }
330 } else
331 sp->lzw_flags &= ~LZW_RESTART;
332 sp->lzw_nbits = BITS_MIN;
333 /*
334 * Pre-load the table.
335 */
336 for (code = 255; code >= 0; code--)
337 sp->dec_suffix[code] = (u_char)code;
338 sp->lzw_free_ent = CODE_FIRST;
339 sp->lzw_bitoff = 0;
340 /* calculate data size in bits */
341 sp->lzw_bitsize = tif->tif_rawdatasize;
342 sp->lzw_bitsize = (sp->lzw_bitsize << 3) - (BITS_MAX-1);
343 sp->dec_stackp = sp->dec_stack;
344 sp->lzw_oldcode = -1;
345 sp->dec_firstchar = -1;
346 /*
347 * Check for old bit-reversed codes. All the flag
348 * manipulations are to insure only one warning is
349 * given for a file.
350 */
351 if (tif->tif_rawdata[0] == 0 && (tif->tif_rawdata[1] & 0x1)) {
352 if ((sp->lzw_flags & LZW_COMPAT) == 0)
353 TIFFWarning(tif->tif_name,
354 "Old-style LZW codes, convert file");
355 sp->lzw_flags |= LZW_COMPAT;
356 } else
357 sp->lzw_flags &= ~LZW_COMPAT;
358 SetMaxCode(sp, MAXCODE(BITS_MIN));
359 return (1);
360 }
361
362 /*
363 * Decode a "hunk of data".
364 */
365 static
LZWDecode(tif,op0,occ0,s)366 LZWDecode(tif, op0, occ0, s)
367 TIFF *tif;
368 u_char *op0;
369 u_int s;
370 {
371 register char *op = (char *)op0;
372 register int occ = occ0;
373 register LZWState *sp = (LZWState *)tif->tif_data;
374 register int code;
375 register u_char *stackp;
376 int firstchar, oldcode, incode;
377
378 stackp = sp->dec_stackp;
379 /*
380 * Restart interrupted unstacking operations.
381 */
382 if (sp->lzw_flags & LZW_RESTART) {
383 do {
384 if (--occ < 0) { /* end of scanline */
385 sp->dec_stackp = stackp;
386 return (1);
387 }
388 *op++ = *--stackp;
389 } while (stackp > sp->dec_stack);
390 sp->lzw_flags &= ~LZW_RESTART;
391 }
392 oldcode = sp->lzw_oldcode;
393 firstchar = sp->dec_firstchar;
394 while (occ > 0 && (code = GetNextCode(tif)) != CODE_EOI) {
395 if (code == CODE_CLEAR) {
396 bzero(sp->dec_prefix, sizeof (sp->dec_prefix));
397 sp->lzw_free_ent = CODE_FIRST;
398 sp->lzw_nbits = BITS_MIN;
399 SetMaxCode(sp, MAXCODE(BITS_MIN));
400 if ((code = GetNextCode(tif)) == CODE_EOI)
401 break;
402 *op++ = code, occ--;
403 oldcode = firstchar = code;
404 continue;
405 }
406 incode = code;
407 /*
408 * When a code is not in the table we use (as spec'd):
409 * StringFromCode(oldcode) +
410 * FirstChar(StringFromCode(oldcode))
411 */
412 if (code >= sp->lzw_free_ent) { /* code not in table */
413 *stackp++ = firstchar;
414 code = oldcode;
415 }
416
417 /*
418 * Generate output string (first in reverse).
419 */
420 for (; code >= 256; code = sp->dec_prefix[code])
421 *stackp++ = sp->dec_suffix[code];
422 *stackp++ = firstchar = sp->dec_suffix[code];
423 do {
424 if (--occ < 0) { /* end of scanline */
425 sp->lzw_flags |= LZW_RESTART;
426 break;
427 }
428 *op++ = *--stackp;
429 } while (stackp > sp->dec_stack);
430
431 /*
432 * Add the new entry to the code table.
433 */
434 if ((code = sp->lzw_free_ent) < CODE_MAX) {
435 sp->dec_prefix[code] = (u_short)oldcode;
436 sp->dec_suffix[code] = firstchar;
437 sp->lzw_free_ent++;
438 /*
439 * If the next entry is too big for the
440 * current code size, then increase the
441 * size up to the maximum possible.
442 */
443 if (sp->lzw_free_ent > sp->lzw_maxcode) {
444 sp->lzw_nbits++;
445 if (sp->lzw_nbits > BITS_MAX)
446 sp->lzw_nbits = BITS_MAX;
447 SetMaxCode(sp, MAXCODE(sp->lzw_nbits));
448 }
449 }
450 oldcode = incode;
451 }
452 sp->dec_stackp = stackp;
453 sp->lzw_oldcode = oldcode;
454 sp->dec_firstchar = firstchar;
455 if (occ > 0) {
456 TIFFError(tif->tif_name,
457 "LZWDecode: Not enough data at scanline %d (short %d bytes)",
458 tif->tif_row, occ);
459 return (0);
460 }
461 return (1);
462 }
463
464 /*
465 * Decode a scanline and apply the predictor routine.
466 */
467 static
LZWDecodePredRow(tif,op0,occ0,s)468 LZWDecodePredRow(tif, op0, occ0, s)
469 TIFF *tif;
470 u_char *op0;
471 u_int s;
472 {
473 LZWState *sp = (LZWState *)tif->tif_data;
474
475 if (LZWDecode(tif, op0, occ0, s)) {
476 (*sp->lzw_hordiff)((char *)op0, occ0, sp->lzw_stride);
477 return (1);
478 } else
479 return (0);
480 }
481
482 /*
483 * Decode a tile/strip and apply the predictor routine.
484 * Note that horizontal differencing must be done on a
485 * row-by-row basis. The width of a "row" has already
486 * been calculated at pre-decode time according to the
487 * strip/tile dimensions.
488 */
489 static
LZWDecodePredTile(tif,op0,occ0,s)490 LZWDecodePredTile(tif, op0, occ0, s)
491 TIFF *tif;
492 u_char *op0;
493 u_int s;
494 {
495 LZWState *sp = (LZWState *)tif->tif_data;
496
497 if (!LZWDecode(tif, op0, occ0, s))
498 return (0);
499 while (occ0 > 0) {
500 (*sp->lzw_hordiff)((char *)op0, sp->lzw_rowsize, sp->lzw_stride);
501 occ0 -= sp->lzw_rowsize;
502 op0 += sp->lzw_rowsize;
503 }
504 return (1);
505 }
506
507 /*
508 * Get the next code from the raw data buffer.
509 */
510 static
GetNextCode(tif)511 GetNextCode(tif)
512 TIFF *tif;
513 {
514 register LZWState *sp = (LZWState *)tif->tif_data;
515 register int code, bits;
516 register long r_off;
517 register u_char *bp;
518
519 /*
520 * This check shouldn't be necessary because each
521 * strip is suppose to be terminated with CODE_EOI.
522 * At worst it's a substitute for the CODE_EOI that's
523 * supposed to be there (see calculation of lzw_bitsize
524 * in LZWPreDecode()).
525 */
526 if (sp->lzw_bitoff > sp->lzw_bitsize) {
527 TIFFWarning(tif->tif_name,
528 "LZWDecode: Strip %d not terminated with EOI code",
529 tif->tif_curstrip);
530 return (CODE_EOI);
531 }
532 r_off = sp->lzw_bitoff;
533 bits = sp->lzw_nbits;
534 /*
535 * Get to the first byte.
536 */
537 bp = (u_char *)tif->tif_rawdata + (r_off >> 3);
538 r_off &= 7;
539 if (sp->lzw_flags & LZW_COMPAT) {
540 /* Get first part (low order bits) */
541 code = (*bp++ >> r_off);
542 r_off = 8 - r_off; /* now, offset into code word */
543 bits -= r_off;
544 /* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */
545 if (bits >= 8) {
546 code |= *bp++ << r_off;
547 r_off += 8;
548 bits -= 8;
549 }
550 /* high order bits. */
551 code |= (*bp & rmask[bits]) << r_off;
552 } else {
553 r_off = 8 - r_off; /* convert offset to count */
554 code = *bp++ & rmask[r_off]; /* high order bits */
555 bits -= r_off;
556 if (bits >= 8) {
557 code = (code<<8) | *bp++;
558 bits -= 8;
559 }
560 /* low order bits */
561 code = (code << bits) |
562 (((unsigned)(*bp & lmask[bits])) >> (8 - bits));
563 }
564 sp->lzw_bitoff += sp->lzw_nbits;
565 return (code);
566 }
567
568 /*
569 * LZW Encoding.
570 */
571
572 static void
DECLARE3(horizontalDifference8,register char *,cp,register int,cc,register int,stride)573 DECLARE3(horizontalDifference8,
574 register char*, cp,
575 register int, cc,
576 register int, stride
577 )
578 {
579 if (cc > stride) {
580 cc -= stride;
581 cp += cc - 1;
582 do {
583 REPEAT4(stride, cp[stride] -= cp[0]; cp--)
584 cc -= stride;
585 } while (cc > 0);
586 }
587 }
588
589 static void
DECLARE3(horizontalDifference16,char *,cp,int,cc,register int,stride)590 DECLARE3(horizontalDifference16,
591 char*, cp,
592 int, cc,
593 register int, stride
594 )
595 {
596 register short *wp = (short *)cp;
597 register int wc = cc/2;
598
599 if (wc > stride) {
600 wc -= stride;
601 wp += wc - 1;
602 do {
603 REPEAT4(stride, wp[stride] -= wp[0]; wp--)
604 wc -= stride;
605 } while (wc > 0);
606 }
607 }
608
609 /*
610 * Reset encoding state at the start of a strip.
611 */
612 static
LZWPreEncode(tif)613 LZWPreEncode(tif)
614 TIFF *tif;
615 {
616 register LZWState *sp = (LZWState *)tif->tif_data;
617
618 if (sp == NULL) {
619 tif->tif_data = malloc(sizeof (LZWState));
620 if (tif->tif_data == NULL) {
621 TIFFError("LZWPreEncode",
622 "No space for LZW state block");
623 return (0);
624 }
625 sp = (LZWState *)tif->tif_data;
626 sp->lzw_flags = 0;
627 sp->lzw_hordiff = 0;
628 if (!LZWCheckPredictor(tif, sp,
629 horizontalDifference8, horizontalDifference16))
630 return (0);
631 if (sp->lzw_hordiff) {
632 tif->tif_encoderow = LZWEncodePredRow;
633 tif->tif_encodestrip = LZWEncodePredTile;
634 tif->tif_encodetile = LZWEncodePredTile;
635 }
636 }
637 sp->enc_checkpoint = CHECK_GAP;
638 SetMaxCode(sp, MAXCODE(sp->lzw_nbits = BITS_MIN)+1);
639 cl_hash(sp); /* clear hash table */
640 sp->lzw_bitoff = 0;
641 sp->lzw_bitsize = (tif->tif_rawdatasize << 3) - (BITS_MAX-1);
642 sp->lzw_oldcode = -1; /* generates CODE_CLEAR in LZWEncode */
643 return (1);
644 }
645
646 /*
647 * Encode a scanline of pixels.
648 *
649 * Uses an open addressing double hashing (no chaining) on the
650 * prefix code/next character combination. We do a variant of
651 * Knuth's algorithm D (vol. 3, sec. 6.4) along with G. Knott's
652 * relatively-prime secondary probe. Here, the modular division
653 * first probe is gives way to a faster exclusive-or manipulation.
654 * Also do block compression with an adaptive reset, whereby the
655 * code table is cleared when the compression ratio decreases,
656 * but after the table fills. The variable-length output codes
657 * are re-sized at this point, and a CODE_CLEAR is generated
658 * for the decoder.
659 */
660 static
LZWEncode(tif,bp,cc,s)661 LZWEncode(tif, bp, cc, s)
662 TIFF *tif;
663 u_char *bp;
664 int cc;
665 u_int s;
666 {
667 static char module[] = "LZWEncode";
668 register LZWState *sp;
669 register long fcode;
670 register int h, c, ent, disp;
671
672 if ((sp = (LZWState *)tif->tif_data) == NULL)
673 return (0);
674 ent = sp->lzw_oldcode;
675 if (ent == -1 && cc > 0) {
676 PutNextCode(tif, CODE_CLEAR);
677 ent = *bp++; cc--; sp->enc_incount++;
678 }
679 while (cc > 0) {
680 c = *bp++; cc--; sp->enc_incount++;
681 fcode = ((long)c << BITS_MAX) + ent;
682 h = (c << HSHIFT) ^ ent; /* xor hashing */
683 if (sp->enc_htab[h] == fcode) {
684 ent = sp->enc_codetab[h];
685 continue;
686 }
687 if (sp->enc_htab[h] >= 0) {
688 /*
689 * Primary hash failed, check secondary hash.
690 */
691 disp = HSIZE - h;
692 if (h == 0)
693 disp = 1;
694 do {
695 if ((h -= disp) < 0)
696 h += HSIZE;
697 if (sp->enc_htab[h] == fcode) {
698 ent = sp->enc_codetab[h];
699 goto hit;
700 }
701 } while (sp->enc_htab[h] >= 0);
702 }
703 /*
704 * New entry, emit code and add to table.
705 */
706 PutNextCode(tif, ent);
707 ent = c;
708 sp->enc_codetab[h] = sp->lzw_free_ent++;
709 sp->enc_htab[h] = fcode;
710 if (sp->lzw_free_ent == CODE_MAX-1) {
711 /* table is full, emit clear code and reset */
712 cl_hash(sp);
713 PutNextCode(tif, CODE_CLEAR);
714 SetMaxCode(sp, MAXCODE(sp->lzw_nbits = BITS_MIN)+1);
715 } else {
716 /*
717 * If the next entry is going to be too big for
718 * the code size, then increase it, if possible.
719 */
720 if (sp->lzw_free_ent > sp->lzw_maxcode) {
721 sp->lzw_nbits++;
722 assert(sp->lzw_nbits <= BITS_MAX);
723 SetMaxCode(sp, MAXCODE(sp->lzw_nbits)+1);
724 } else if (sp->enc_incount >= sp->enc_checkpoint)
725 cl_block(tif);
726 }
727 hit:
728 ;
729 }
730 sp->lzw_oldcode = ent;
731 return (1);
732 }
733
734 static
LZWEncodePredRow(tif,bp,cc,s)735 LZWEncodePredRow(tif, bp, cc, s)
736 TIFF *tif;
737 u_char *bp;
738 int cc;
739 u_int s;
740 {
741 LZWState *sp = (LZWState *)tif->tif_data;
742
743 /* XXX horizontal differencing alters user's data XXX */
744 (*sp->lzw_hordiff)((char *)bp, cc, sp->lzw_stride);
745 return (LZWEncode(tif, bp, cc, s));
746 }
747
748 static
LZWEncodePredTile(tif,bp0,cc0,s)749 LZWEncodePredTile(tif, bp0, cc0, s)
750 TIFF *tif;
751 u_char *bp0;
752 int cc0;
753 u_int s;
754 {
755 LZWState *sp = (LZWState *)tif->tif_data;
756 int cc = cc0;
757 u_char *bp = bp0;
758
759 while (cc > 0) {
760 (*sp->lzw_hordiff)((char *)bp, sp->lzw_rowsize, sp->lzw_stride);
761 cc -= sp->lzw_rowsize;
762 bp += sp->lzw_rowsize;
763 }
764 return (LZWEncode(tif, bp0, cc0, s));
765 }
766
767 /*
768 * Finish off an encoded strip by flushing the last
769 * string and tacking on an End Of Information code.
770 */
771 static
LZWPostEncode(tif)772 LZWPostEncode(tif)
773 TIFF *tif;
774 {
775 LZWState *sp = (LZWState *)tif->tif_data;
776
777 if (sp->lzw_oldcode != -1) {
778 PutNextCode(tif, sp->lzw_oldcode);
779 sp->lzw_oldcode = -1;
780 }
781 PutNextCode(tif, CODE_EOI);
782 return (1);
783 }
784
785 static void
PutNextCode(tif,c)786 PutNextCode(tif, c)
787 TIFF *tif;
788 int c;
789 {
790 register LZWState *sp = (LZWState *)tif->tif_data;
791 register long r_off;
792 register int bits, code = c;
793 register char *bp;
794
795 r_off = sp->lzw_bitoff;
796 bits = sp->lzw_nbits;
797 /*
798 * Flush buffer if code doesn't fit.
799 */
800 if (r_off + bits > sp->lzw_bitsize) {
801 /*
802 * Calculate the number of full bytes that can be
803 * written and save anything else for the next write.
804 */
805 if (r_off & 7) {
806 tif->tif_rawcc = r_off >> 3;
807 bp = tif->tif_rawdata + tif->tif_rawcc;
808 (void) TIFFFlushData1(tif);
809 tif->tif_rawdata[0] = *bp;
810 } else {
811 /*
812 * Otherwise, on a byte boundary (in
813 * which tiff_rawcc is already correct).
814 */
815 (void) TIFFFlushData1(tif);
816 }
817 bp = tif->tif_rawdata;
818 sp->lzw_bitoff = (r_off &= 7);
819 } else {
820 /*
821 * Get to the first byte.
822 */
823 bp = tif->tif_rawdata + (r_off >> 3);
824 r_off &= 7;
825 }
826 /*
827 * Note that lzw_bitoff is maintained as the bit offset
828 * into the buffer w/ a right-to-left orientation (i.e.
829 * lsb-to-msb). The bits, however, go in the file in
830 * an msb-to-lsb order.
831 */
832 bits -= (8 - r_off);
833 *bp = (*bp & lmask[r_off]) | (code >> bits);
834 bp++;
835 if (bits >= 8) {
836 bits -= 8;
837 *bp++ = code >> bits;
838 }
839 if (bits)
840 *bp = (code & rmask[bits]) << (8 - bits);
841 /*
842 * enc_outcount is used by the compression analysis machinery
843 * which resets the compression tables when the compression
844 * ratio goes up. lzw_bitoff is used here (in PutNextCode) for
845 * inserting codes into the output buffer. tif_rawcc must
846 * be updated for the mainline write code in TIFFWriteScanline()
847 * so that data is flushed when the end of a strip is reached.
848 * Note that the latter is rounded up to ensure that a non-zero
849 * byte count is present.
850 */
851 sp->enc_outcount += sp->lzw_nbits;
852 sp->lzw_bitoff += sp->lzw_nbits;
853 tif->tif_rawcc = (sp->lzw_bitoff + 7) >> 3;
854 }
855
856 /*
857 * Check compression ratio and, if things seem to
858 * be slipping, clear the hash table and reset state.
859 */
860 static void
cl_block(tif)861 cl_block(tif)
862 TIFF *tif;
863 {
864 register LZWState *sp = (LZWState *)tif->tif_data;
865 register long rat;
866
867 sp->enc_checkpoint = sp->enc_incount + CHECK_GAP;
868 if (sp->enc_incount > 0x007fffff) { /* shift will overflow */
869 rat = sp->enc_outcount >> 8;
870 rat = (rat == 0 ? 0x7fffffff : sp->enc_incount / rat);
871 } else
872 rat = (sp->enc_incount<<8)/sp->enc_outcount; /* 8 fract bits */
873 if (rat <= sp->enc_ratio) {
874 cl_hash(sp);
875 PutNextCode(tif, CODE_CLEAR);
876 SetMaxCode(sp, MAXCODE(sp->lzw_nbits = BITS_MIN)+1);
877 } else
878 sp->enc_ratio = rat;
879 }
880
881 /*
882 * Reset code table and related statistics.
883 */
884 static void
cl_hash(sp)885 cl_hash(sp)
886 LZWState *sp;
887 {
888 register long *htab_p = sp->enc_htab+HSIZE;
889 register long i, m1 = -1;
890
891 i = HSIZE - 16;
892 do {
893 *(htab_p-16) = m1;
894 *(htab_p-15) = m1;
895 *(htab_p-14) = m1;
896 *(htab_p-13) = m1;
897 *(htab_p-12) = m1;
898 *(htab_p-11) = m1;
899 *(htab_p-10) = m1;
900 *(htab_p-9) = m1;
901 *(htab_p-8) = m1;
902 *(htab_p-7) = m1;
903 *(htab_p-6) = m1;
904 *(htab_p-5) = m1;
905 *(htab_p-4) = m1;
906 *(htab_p-3) = m1;
907 *(htab_p-2) = m1;
908 *(htab_p-1) = m1;
909 htab_p -= 16;
910 } while ((i -= 16) >= 0);
911 for (i += 16; i > 0; i--)
912 *--htab_p = m1;
913
914 sp->enc_ratio = 0;
915 sp->enc_incount = 0;
916 sp->enc_outcount = 0;
917 sp->lzw_free_ent = CODE_FIRST;
918 }
919
920 static
LZWCleanup(tif)921 LZWCleanup(tif)
922 TIFF *tif;
923 {
924 if (tif->tif_data) {
925 free(tif->tif_data);
926 tif->tif_data = NULL;
927 }
928 }
929
930 /*
931 * Copyright (c) 1985, 1986 The Regents of the University of California.
932 * All rights reserved.
933 *
934 * This code is derived from software contributed to Berkeley by
935 * James A. Woods, derived from original work by Spencer Thomas
936 * and Joseph Orost.
937 *
938 * Redistribution and use in source and binary forms are permitted
939 * provided that the above copyright notice and this paragraph are
940 * duplicated in all such forms and that any documentation,
941 * advertising materials, and other materials related to such
942 * distribution and use acknowledge that the software was developed
943 * by the University of California, Berkeley. The name of the
944 * University may not be used to endorse or promote products derived
945 * from this software without specific prior written permission.
946 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
947 * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
948 * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE.
949 */
950