Line data Source code
1 : /*
2 : * Copyright (c) 1988-1997 Sam Leffler
3 : * Copyright (c) 1991-1997 Silicon Graphics, Inc.
4 : * Copyright (c) 2022 Even Rouault
5 : *
6 : * Permission to use, copy, modify, distribute, and sell this software and
7 : * its documentation for any purpose is hereby granted without fee, provided
8 : * that (i) the above copyright notices and this permission notice appear in
9 : * all copies of the software and related documentation, and (ii) the names of
10 : * Sam Leffler and Silicon Graphics may not be used in any advertising or
11 : * publicity relating to the software without the specific, prior written
12 : * permission of Sam Leffler and Silicon Graphics.
13 : *
14 : * THE SOFTWARE IS PROVIDED "AS-IS" AND WITHOUT WARRANTY OF ANY KIND,
15 : * EXPRESS, IMPLIED OR OTHERWISE, INCLUDING WITHOUT LIMITATION, ANY
16 : * WARRANTY OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
17 : *
18 : * IN NO EVENT SHALL SAM LEFFLER OR SILICON GRAPHICS BE LIABLE FOR
19 : * ANY SPECIAL, INCIDENTAL, INDIRECT OR CONSEQUENTIAL DAMAGES OF ANY KIND,
20 : * OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS,
21 : * WHETHER OR NOT ADVISED OF THE POSSIBILITY OF DAMAGE, AND ON ANY THEORY OF
22 : * LIABILITY, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE
23 : * OF THIS SOFTWARE.
24 : */
25 :
26 : #include "tiffiop.h"
27 : #ifdef LZW_SUPPORT
28 : /*
29 : * TIFF Library.
30 : * Rev 5.0 Lempel-Ziv & Welch Compression Support
31 : *
32 : * This code is derived from the compress program whose code is
33 : * derived from software contributed to Berkeley by James A. Woods,
34 : * derived from original work by Spencer Thomas and Joseph Orost.
35 : *
36 : * The original Berkeley copyright notice appears below in its entirety.
37 : */
38 : #include "tif_predict.h"
39 :
40 : #include <stdbool.h>
41 : #include <stdio.h>
42 : #include <stdlib.h>
43 :
44 : /* Select the plausible largest natural integer type for the architecture */
45 : #define SIZEOF_WORDTYPE SIZEOF_SIZE_T
46 : typedef size_t WordType;
47 :
48 : /*
49 : * NB: The 5.0 spec describes a different algorithm than Aldus
50 : * implements. Specifically, Aldus does code length transitions
51 : * one code earlier than should be done (for real LZW).
52 : * Earlier versions of this library implemented the correct
53 : * LZW algorithm, but emitted codes in a bit order opposite
54 : * to the TIFF spec. Thus, to maintain compatibility w/ Aldus
55 : * we interpret MSB-LSB ordered codes to be images written w/
56 : * old versions of this library, but otherwise adhere to the
57 : * Aldus "off by one" algorithm.
58 : *
59 : * Future revisions to the TIFF spec are expected to "clarify this issue".
60 : */
61 : #define LZW_COMPAT /* include backwards compatibility code */
62 :
63 : #define MAXCODE(n) ((1 << (n)) - 1)
64 : /*
65 : * The TIFF spec specifies that encoded bit
66 : * strings range from 9 to 12 bits.
67 : */
68 : #define BITS_MIN 9 /* start with 9 bits */
69 : #define BITS_MAX 12 /* max of 12 bit strings */
70 : /* predefined codes */
71 : #define CODE_CLEAR 256 /* code to clear string table */
72 : #define CODE_EOI 257 /* end-of-information code */
73 : #define CODE_FIRST 258 /* first free code entry */
74 : #define CODE_MAX MAXCODE(BITS_MAX)
75 : #define HSIZE 9001L /* 91% occupancy */
76 : #define HSHIFT (13 - 8)
77 : #ifdef LZW_COMPAT
78 : /* NB: +1024 is for compatibility with old files */
79 : #define CSIZE (MAXCODE(BITS_MAX) + 1024L)
80 : #else
81 : #define CSIZE (MAXCODE(BITS_MAX) + 1L)
82 : #endif
83 :
84 : /*
85 : * State block for each open TIFF file using LZW
86 : * compression/decompression. Note that the predictor
87 : * state block must be first in this data structure.
88 : */
89 : typedef struct
90 : {
91 : TIFFPredictorState predict; /* predictor super class */
92 :
93 : unsigned short nbits; /* # of bits/code */
94 : unsigned short maxcode; /* maximum code for lzw_nbits */
95 : unsigned short free_ent; /* next free entry in hash table */
96 : WordType nextdata; /* next bits of i/o */
97 : long nextbits; /* # of valid bits in lzw_nextdata */
98 :
99 : int rw_mode; /* preserve rw_mode from init */
100 : } LZWBaseState;
101 :
102 : #define lzw_nbits base.nbits
103 : #define lzw_maxcode base.maxcode
104 : #define lzw_free_ent base.free_ent
105 : #define lzw_nextdata base.nextdata
106 : #define lzw_nextbits base.nextbits
107 :
108 : /*
109 : * Encoding-specific state.
110 : */
111 : typedef uint16_t hcode_t; /* codes fit in 16 bits */
112 : typedef struct
113 : {
114 : long hash;
115 : hcode_t code;
116 : } hash_t;
117 :
118 : /*
119 : * Decoding-specific state.
120 : */
121 : typedef struct code_ent
122 : {
123 : struct code_ent *next;
124 : unsigned short length; /* string len, including this token */
125 : /* firstchar should be placed immediately before value in this structure */
126 : unsigned char firstchar; /* first token of string */
127 : unsigned char value; /* data value */
128 : bool repeated;
129 : } code_t;
130 :
131 : typedef int (*decodeFunc)(TIFF *, uint8_t *, tmsize_t, uint16_t);
132 :
133 : typedef struct
134 : {
135 : LZWBaseState base;
136 :
137 : /* Decoding specific data */
138 : long dec_nbitsmask; /* lzw_nbits 1 bits, right adjusted */
139 : tmsize_t dec_restart; /* restart count */
140 : uint64_t dec_bitsleft; /* available bits in raw data */
141 : tmsize_t old_tif_rawcc; /* value of tif_rawcc at the end of the previous
142 : TIFLZWDecode() call */
143 : decodeFunc dec_decode; /* regular or backwards compatible */
144 : code_t *dec_codep; /* current recognized code */
145 : code_t *dec_oldcodep; /* previously recognized code */
146 : code_t *dec_free_entp; /* next free entry */
147 : code_t *dec_maxcodep; /* max available entry */
148 : code_t *dec_codetab; /* kept separate for small machines */
149 : int read_error; /* whether a read error has occurred, and which should cause
150 : further reads in the same strip/tile to be aborted */
151 :
152 : /* Encoding specific data */
153 : int enc_oldcode; /* last code encountered */
154 : tmsize_t enc_checkpoint; /* point at which to clear table */
155 : #define CHECK_GAP 10000 /* enc_ratio check interval */
156 : tmsize_t enc_ratio; /* current compression ratio */
157 : tmsize_t enc_incount; /* (input) data bytes encoded */
158 : tmsize_t enc_outcount; /* encoded (output) bytes */
159 : uint8_t *enc_rawlimit; /* bound on tif_rawdata buffer */
160 : hash_t *enc_hashtab; /* kept separate for small machines */
161 : } LZWCodecState;
162 :
163 : #define LZWState(tif) ((LZWBaseState *)(tif)->tif_data)
164 : #define LZWDecoderState(tif) ((LZWCodecState *)LZWState(tif))
165 : #define LZWEncoderState(tif) ((LZWCodecState *)LZWState(tif))
166 :
167 : static int LZWDecode(TIFF *tif, uint8_t *op0, tmsize_t occ0, uint16_t s);
168 : #ifdef LZW_COMPAT
169 : static int LZWDecodeCompat(TIFF *tif, uint8_t *op0, tmsize_t occ0, uint16_t s);
170 : #endif
171 :
172 : /*
173 : * LZW Decoder.
174 : */
175 :
176 5125 : static int LZWFixupTags(TIFF *tif)
177 : {
178 : (void)tif;
179 5125 : return (1);
180 : }
181 :
182 2684 : static int LZWSetupDecode(TIFF *tif)
183 : {
184 : static const char module[] = "LZWSetupDecode";
185 2684 : LZWCodecState *sp = LZWDecoderState(tif);
186 : int code;
187 :
188 2684 : if (sp == NULL)
189 : {
190 : /*
191 : * Allocate state block so tag methods have storage to record
192 : * values.
193 : */
194 0 : tif->tif_data = (uint8_t *)_TIFFmallocExt(tif, sizeof(LZWCodecState));
195 0 : if (tif->tif_data == NULL)
196 : {
197 0 : TIFFErrorExtR(tif, module, "No space for LZW state block");
198 0 : return (0);
199 : }
200 :
201 0 : sp = LZWDecoderState(tif);
202 0 : sp->dec_codetab = NULL;
203 0 : sp->dec_decode = NULL;
204 :
205 : /*
206 : * Setup predictor setup.
207 : */
208 0 : (void)TIFFPredictorInit(tif);
209 : }
210 :
211 2681 : if (sp->dec_codetab == NULL)
212 : {
213 2678 : sp->dec_codetab = (code_t *)_TIFFmallocExt(tif, CSIZE * sizeof(code_t));
214 2681 : if (sp->dec_codetab == NULL)
215 : {
216 0 : TIFFErrorExtR(tif, module, "No space for LZW code table");
217 0 : return (0);
218 : }
219 : /*
220 : * Pre-load the table.
221 : */
222 2681 : code = 255;
223 18870 : do
224 : {
225 685125 : sp->dec_codetab[code].firstchar = (unsigned char)code;
226 685125 : sp->dec_codetab[code].value = (unsigned char)code;
227 685125 : sp->dec_codetab[code].repeated = true;
228 685125 : sp->dec_codetab[code].length = 1;
229 685125 : sp->dec_codetab[code].next = NULL;
230 685125 : } while (code--);
231 : /*
232 : * Zero-out the unused entries */
233 : /* Silence false positive */
234 : /* coverity[overrun-buffer-arg] */
235 2681 : memset(&sp->dec_codetab[CODE_CLEAR], 0,
236 : (CODE_FIRST - CODE_CLEAR) * sizeof(code_t));
237 : }
238 2684 : return (1);
239 : }
240 :
241 : /*
242 : * Setup state for decoding a strip.
243 : */
244 6606 : static int LZWPreDecode(TIFF *tif, uint16_t s)
245 : {
246 : static const char module[] = "LZWPreDecode";
247 6606 : LZWCodecState *sp = LZWDecoderState(tif);
248 :
249 : (void)s;
250 6606 : assert(sp != NULL);
251 6606 : if (sp->dec_codetab == NULL)
252 : {
253 109 : tif->tif_setupdecode(tif);
254 109 : if (sp->dec_codetab == NULL)
255 0 : return (0);
256 : }
257 :
258 : /*
259 : * Check for old bit-reversed codes.
260 : */
261 6606 : if (tif->tif_rawcc >= 2 && tif->tif_rawdata[0] == 0 &&
262 104 : (tif->tif_rawdata[1] & 0x1))
263 : {
264 : #ifdef LZW_COMPAT
265 104 : if (!sp->dec_decode)
266 : {
267 3 : TIFFWarningExtR(tif, module, "Old-style LZW codes, convert file");
268 : /*
269 : * Override default decoding methods with
270 : * ones that deal with the old coding.
271 : * Otherwise the predictor versions set
272 : * above will call the compatibility routines
273 : * through the dec_decode method.
274 : */
275 3 : tif->tif_decoderow = LZWDecodeCompat;
276 3 : tif->tif_decodestrip = LZWDecodeCompat;
277 3 : tif->tif_decodetile = LZWDecodeCompat;
278 : /*
279 : * If doing horizontal differencing, must
280 : * re-setup the predictor logic since we
281 : * switched the basic decoder methods...
282 : */
283 3 : (*tif->tif_setupdecode)(tif);
284 3 : sp->dec_decode = LZWDecodeCompat;
285 : }
286 104 : sp->lzw_maxcode = MAXCODE(BITS_MIN);
287 : #else /* !LZW_COMPAT */
288 : if (!sp->dec_decode)
289 : {
290 : TIFFErrorExtR(tif, module, "Old-style LZW codes not supported");
291 : sp->dec_decode = LZWDecode;
292 : }
293 : return (0);
294 : #endif /* !LZW_COMPAT */
295 : }
296 : else
297 : {
298 6502 : sp->lzw_maxcode = MAXCODE(BITS_MIN) - 1;
299 6502 : sp->dec_decode = LZWDecode;
300 : }
301 6606 : sp->lzw_nbits = BITS_MIN;
302 6606 : sp->lzw_nextbits = 0;
303 6606 : sp->lzw_nextdata = 0;
304 :
305 6606 : sp->dec_restart = 0;
306 6606 : sp->dec_nbitsmask = MAXCODE(BITS_MIN);
307 6606 : sp->dec_bitsleft = 0;
308 6606 : sp->old_tif_rawcc = 0;
309 6606 : sp->dec_free_entp = sp->dec_codetab - 1; // + CODE_FIRST;
310 : /*
311 : * Zero entries that are not yet filled in. We do
312 : * this to guard against bogus input data that causes
313 : * us to index into undefined entries. If you can
314 : * come up with a way to safely bounds-check input codes
315 : * while decoding then you can remove this operation.
316 : */
317 6606 : sp->dec_oldcodep = &sp->dec_codetab[0];
318 6606 : sp->dec_maxcodep = &sp->dec_codetab[sp->dec_nbitsmask - 1];
319 6606 : sp->read_error = 0;
320 6606 : return (1);
321 : }
322 :
323 : /*
324 : * Decode a "hunk of data".
325 : */
326 :
327 : /* Get the next 32 or 64-bit from the input data */
328 : #ifdef WORDS_BIGENDIAN
329 : #define GetNextData(nextdata, bp) memcpy(&nextdata, bp, sizeof(nextdata))
330 : #elif SIZEOF_WORDTYPE == 8
331 : #if defined(_M_X64)
332 : #define GetNextData(nextdata, bp) nextdata = _byteswap_uint64(*(uint64_t *)(bp))
333 : #elif defined(__GNUC__)
334 : #define GetNextData(nextdata, bp) \
335 : memcpy(&nextdata, bp, sizeof(nextdata)); \
336 : nextdata = __builtin_bswap64(nextdata)
337 : #else
338 : #define GetNextData(nextdata, bp) \
339 : nextdata = (((uint64_t)bp[0]) << 56) | (((uint64_t)bp[1]) << 48) | \
340 : (((uint64_t)bp[2]) << 40) | (((uint64_t)bp[3]) << 32) | \
341 : (((uint64_t)bp[4]) << 24) | (((uint64_t)bp[5]) << 16) | \
342 : (((uint64_t)bp[6]) << 8) | (((uint64_t)bp[7]))
343 : #endif
344 : #elif SIZEOF_WORDTYPE == 4
345 : #if defined(_M_X86)
346 : #define GetNextData(nextdata, bp) \
347 : nextdata = _byteswap_ulong(*(unsigned long *)(bp))
348 : #elif defined(__GNUC__)
349 : #define GetNextData(nextdata, bp) \
350 : memcpy(&nextdata, bp, sizeof(nextdata)); \
351 : nextdata = __builtin_bswap32(nextdata)
352 : #else
353 : #define GetNextData(nextdata, bp) \
354 : nextdata = (((uint32_t)bp[0]) << 24) | (((uint32_t)bp[1]) << 16) | \
355 : (((uint32_t)bp[2]) << 8) | (((uint32_t)bp[3]))
356 : #endif
357 : #else
358 : #error "Unhandled SIZEOF_WORDTYPE"
359 : #endif
360 :
361 : #define GetNextCodeLZW() \
362 : do \
363 : { \
364 : nextbits -= nbits; \
365 : if (nextbits < 0) \
366 : { \
367 : if (dec_bitsleft >= 8 * SIZEOF_WORDTYPE) \
368 : { \
369 : unsigned codetmp = (unsigned)(nextdata << (-nextbits)); \
370 : GetNextData(nextdata, bp); \
371 : bp += SIZEOF_WORDTYPE; \
372 : nextbits += 8 * SIZEOF_WORDTYPE; \
373 : dec_bitsleft -= 8 * SIZEOF_WORDTYPE; \
374 : code = (WordType)((codetmp | (nextdata >> nextbits)) & \
375 : (WordType)nbitsmask); \
376 : break; \
377 : } \
378 : else \
379 : { \
380 : if (dec_bitsleft < 8) \
381 : { \
382 : goto no_eoi; \
383 : } \
384 : nextdata = (nextdata << 8) | *(bp)++; \
385 : nextbits += 8; \
386 : dec_bitsleft -= 8; \
387 : if (nextbits < 0) \
388 : { \
389 : if (dec_bitsleft < 8) \
390 : { \
391 : goto no_eoi; \
392 : } \
393 : nextdata = (nextdata << 8) | *(bp)++; \
394 : nextbits += 8; \
395 : dec_bitsleft -= 8; \
396 : } \
397 : } \
398 : } \
399 : code = (WordType)((nextdata >> nextbits) & (WordType)nbitsmask); \
400 : } while (0)
401 :
402 114714 : static int LZWDecode(TIFF *tif, uint8_t *op0, tmsize_t occ0, uint16_t s)
403 : {
404 : static const char module[] = "LZWDecode";
405 114714 : LZWCodecState *sp = LZWDecoderState(tif);
406 114714 : uint8_t *op = (uint8_t *)op0;
407 114714 : tmsize_t occ = occ0;
408 : uint8_t *bp;
409 : long nbits, nextbits, nbitsmask;
410 : WordType nextdata;
411 : code_t *free_entp, *maxcodep, *oldcodep;
412 :
413 : (void)s;
414 114714 : assert(sp != NULL);
415 114714 : assert(sp->dec_codetab != NULL);
416 :
417 114714 : if (sp->read_error)
418 : {
419 0 : memset(op, 0, (size_t)occ);
420 0 : TIFFErrorExtR(tif, module,
421 : "LZWDecode: Scanline %" PRIu32 " cannot be read due to "
422 : "previous error",
423 : tif->tif_row);
424 0 : return 0;
425 : }
426 :
427 : /*
428 : * Restart interrupted output operation.
429 : */
430 114714 : if (sp->dec_restart)
431 : {
432 : tmsize_t residue;
433 :
434 104113 : code_t *codep = sp->dec_codep;
435 104113 : residue = codep->length - sp->dec_restart;
436 104113 : if (residue > occ)
437 : {
438 : /*
439 : * Residue from previous decode is sufficient
440 : * to satisfy decode request. Skip to the
441 : * start of the decoded string, place decoded
442 : * values in the output buffer, and return.
443 : */
444 99868 : sp->dec_restart += occ;
445 0 : do
446 : {
447 3160750 : codep = codep->next;
448 3160750 : } while (--residue > occ && codep);
449 99868 : if (codep)
450 : {
451 99868 : uint8_t *tp = op + occ;
452 0 : do
453 : {
454 176900 : *--tp = codep->value;
455 176900 : codep = codep->next;
456 176900 : } while (--occ && codep);
457 : }
458 99868 : return (1);
459 : }
460 : /*
461 : * Residue satisfies only part of the decode request.
462 : */
463 4245 : op += residue;
464 4245 : occ -= residue;
465 4245 : uint8_t *tp = op;
466 0 : do
467 : {
468 6912 : *--tp = codep->value;
469 6912 : codep = codep->next;
470 6912 : } while (--residue && codep);
471 4245 : sp->dec_restart = 0;
472 : }
473 :
474 14846 : bp = (uint8_t *)tif->tif_rawcp;
475 14846 : sp->dec_bitsleft +=
476 14846 : (((uint64_t)tif->tif_rawcc - (uint64_t)sp->old_tif_rawcc) << 3);
477 14846 : uint64_t dec_bitsleft = sp->dec_bitsleft;
478 14846 : nbits = sp->lzw_nbits;
479 14846 : nextdata = sp->lzw_nextdata;
480 14846 : nextbits = sp->lzw_nextbits;
481 14846 : nbitsmask = sp->dec_nbitsmask;
482 14846 : oldcodep = sp->dec_oldcodep;
483 14846 : free_entp = sp->dec_free_entp;
484 14846 : maxcodep = sp->dec_maxcodep;
485 14846 : code_t *const dec_codetab = sp->dec_codetab;
486 : code_t *codep;
487 :
488 14846 : if (occ == 0)
489 : {
490 2276 : goto after_loop;
491 : }
492 :
493 12570 : begin:
494 : {
495 : WordType code;
496 117922017 : GetNextCodeLZW();
497 117922017 : codep = dec_codetab + (unsigned long)code;
498 117922017 : if (code >= CODE_FIRST)
499 48477418 : goto code_above_or_equal_to_258;
500 69444599 : if (code < 256)
501 69406444 : goto code_below_256;
502 38221 : if (code == CODE_EOI)
503 10 : goto after_loop;
504 38211 : goto code_clear;
505 :
506 69406444 : code_below_256:
507 : {
508 69406444 : if (codep > free_entp)
509 0 : goto error_code;
510 69406444 : free_entp->next = oldcodep;
511 69406444 : free_entp->firstchar = oldcodep->firstchar;
512 69406444 : free_entp->length = oldcodep->length + 1;
513 69406444 : free_entp->value = (uint8_t)code;
514 69406444 : free_entp->repeated =
515 69406444 : (bool)(oldcodep->repeated & (oldcodep->value == code));
516 69406444 : if (++free_entp > maxcodep)
517 : {
518 57156 : if (++nbits > BITS_MAX) /* should not happen for a conformant encoder */
519 0 : nbits = BITS_MAX;
520 57156 : nbitsmask = MAXCODE(nbits);
521 57156 : maxcodep = dec_codetab + nbitsmask - 1;
522 57156 : if (free_entp >= &dec_codetab[CSIZE])
523 : {
524 : /* At that point, the next valid states are either EOI or a */
525 : /* CODE_CLEAR. If a regular code is read, at the next */
526 : /* attempt at registering a new entry, we will error out */
527 : /* due to setting free_entp before any valid code */
528 0 : free_entp = dec_codetab - 1;
529 : }
530 : }
531 69406444 : oldcodep = codep;
532 69406444 : *op++ = (uint8_t)code;
533 69406444 : occ--;
534 69406444 : if (occ == 0)
535 2737 : goto after_loop;
536 69403648 : goto begin;
537 : }
538 :
539 48477418 : code_above_or_equal_to_258:
540 : {
541 : /*
542 : * Add the new entry to the code table.
543 : */
544 :
545 48477418 : if (codep >= free_entp)
546 : {
547 704293 : if (codep != free_entp)
548 2 : goto error_code;
549 704291 : free_entp->value = oldcodep->firstchar;
550 : }
551 : else
552 : {
553 47773046 : free_entp->value = codep->firstchar;
554 : }
555 48477417 : free_entp->repeated =
556 48477417 : (bool)(oldcodep->repeated & (oldcodep->value == free_entp->value));
557 48477417 : free_entp->next = oldcodep;
558 :
559 48477417 : free_entp->firstchar = oldcodep->firstchar;
560 48477417 : free_entp->length = oldcodep->length + 1;
561 48477417 : if (++free_entp > maxcodep)
562 : {
563 37836 : if (++nbits > BITS_MAX) /* should not happen for a conformant encoder */
564 0 : nbits = BITS_MAX;
565 37836 : nbitsmask = MAXCODE(nbits);
566 37836 : maxcodep = dec_codetab + nbitsmask - 1;
567 37836 : if (free_entp >= &dec_codetab[CSIZE])
568 : {
569 : /* At that point, the next valid states are either EOI or a */
570 : /* CODE_CLEAR. If a regular code is read, at the next */
571 : /* attempt at registering a new entry, we will error out */
572 : /* due to setting free_entp before any valid code */
573 0 : free_entp = dec_codetab - 1;
574 : }
575 : }
576 48477417 : oldcodep = codep;
577 :
578 : /*
579 : * Code maps to a string, copy string
580 : * value to output (written in reverse).
581 : */
582 : /* tiny bit faster on x86_64 to store in unsigned short than int */
583 48477417 : unsigned short len = codep->length;
584 :
585 48477417 : if (len < 3) /* equivalent to len == 2 given all other conditions */
586 : {
587 38556021 : if (occ <= 2)
588 : {
589 964 : if (occ == 2)
590 : {
591 915 : memcpy(op, &(codep->firstchar), 2);
592 915 : op += 2;
593 915 : occ -= 2;
594 915 : goto after_loop;
595 : }
596 49 : goto too_short_buffer;
597 : }
598 :
599 38555098 : memcpy(op, &(codep->firstchar), 2);
600 38555098 : op += 2;
601 38555098 : occ -= 2;
602 38555098 : goto begin; /* we can save the comparison occ > 0 */
603 : }
604 :
605 9921326 : if (len == 3)
606 : {
607 5596078 : if (occ <= 3)
608 : {
609 344 : if (occ == 3)
610 : {
611 282 : op[0] = codep->firstchar;
612 282 : op[1] = codep->next->value;
613 282 : op[2] = codep->value;
614 282 : op += 3;
615 282 : occ -= 3;
616 282 : goto after_loop;
617 : }
618 62 : goto too_short_buffer;
619 : }
620 :
621 5595737 : op[0] = codep->firstchar;
622 5595737 : op[1] = codep->next->value;
623 5595737 : op[2] = codep->value;
624 5595737 : op += 3;
625 5595737 : occ -= 3;
626 5595737 : goto begin; /* we can save the comparison occ > 0 */
627 : }
628 :
629 4325238 : if (len > occ)
630 : {
631 4390 : goto too_short_buffer;
632 : }
633 :
634 4320848 : if (codep->repeated)
635 : {
636 945439 : memset(op, codep->value, len);
637 945439 : op += len;
638 945439 : occ -= len;
639 945439 : if (occ == 0)
640 3366 : goto after_loop;
641 942073 : goto begin;
642 : }
643 :
644 3375416 : uint8_t *tp = op + len;
645 :
646 3375416 : assert(len >= 4);
647 :
648 3375416 : *--tp = codep->value;
649 3375416 : codep = codep->next;
650 3375416 : *--tp = codep->value;
651 3375416 : codep = codep->next;
652 3375416 : *--tp = codep->value;
653 3375416 : codep = codep->next;
654 3375416 : *--tp = codep->value;
655 3375416 : if (tp > op)
656 : {
657 309809 : do
658 : {
659 25510191 : codep = codep->next;
660 25510191 : *--tp = codep->value;
661 25510191 : } while (tp > op);
662 : }
663 :
664 3375416 : assert(occ >= len);
665 3375416 : op += len;
666 3375416 : occ -= len;
667 3375416 : if (occ == 0)
668 731 : goto after_loop;
669 3374680 : goto begin;
670 : }
671 :
672 38211 : code_clear:
673 : {
674 38211 : free_entp = dec_codetab + CODE_FIRST;
675 38211 : nbits = BITS_MIN;
676 38211 : nbitsmask = MAXCODE(BITS_MIN);
677 38211 : maxcodep = dec_codetab + (unsigned long)nbitsmask - 1;
678 0 : do
679 : {
680 35887 : GetNextCodeLZW();
681 35887 : } while (code == CODE_CLEAR); /* consecutive CODE_CLEAR codes */
682 38211 : if (code == CODE_EOI)
683 0 : goto after_loop;
684 38211 : if (code > CODE_EOI)
685 : {
686 0 : goto error_code;
687 : }
688 38211 : *op++ = (uint8_t)code;
689 38211 : occ--;
690 38211 : oldcodep = dec_codetab + code;
691 38211 : if (occ == 0)
692 26 : goto after_loop;
693 38185 : goto begin;
694 : }
695 : }
696 :
697 4501 : too_short_buffer:
698 : {
699 : /*
700 : * String is too long for decode buffer,
701 : * locate portion that will fit, copy to
702 : * the decode buffer, and setup restart
703 : * logic for the next decoding call.
704 : */
705 4501 : sp->dec_codep = codep;
706 0 : do
707 : {
708 204454 : codep = codep->next;
709 204454 : } while (codep->length > occ);
710 :
711 4501 : sp->dec_restart = occ;
712 4501 : uint8_t *tp = op + occ;
713 0 : do
714 : {
715 26809 : *--tp = codep->value;
716 26809 : codep = codep->next;
717 26809 : } while (--occ);
718 : }
719 :
720 4501 : after_loop:
721 14844 : tif->tif_rawcc -= (tmsize_t)((uint8_t *)bp - tif->tif_rawcp);
722 14844 : tif->tif_rawcp = (uint8_t *)bp;
723 14844 : sp->old_tif_rawcc = tif->tif_rawcc;
724 14844 : sp->dec_bitsleft = dec_bitsleft;
725 14844 : sp->lzw_nbits = (unsigned short)nbits;
726 14844 : sp->lzw_nextdata = nextdata;
727 14844 : sp->lzw_nextbits = nextbits;
728 14844 : sp->dec_nbitsmask = nbitsmask;
729 14844 : sp->dec_oldcodep = oldcodep;
730 14844 : sp->dec_free_entp = free_entp;
731 14844 : sp->dec_maxcodep = maxcodep;
732 :
733 14844 : if (occ > 0)
734 : {
735 10 : memset(op, 0, (size_t)occ);
736 10 : sp->read_error = 1;
737 10 : TIFFErrorExtR(tif, module,
738 : "Not enough data at scanline %" PRIu32 " (short %" PRIu64
739 : " bytes)",
740 : tif->tif_row, (uint64_t)occ);
741 10 : return (0);
742 : }
743 14834 : return (1);
744 :
745 0 : no_eoi:
746 0 : memset(op, 0, (size_t)occ);
747 0 : sp->read_error = 1;
748 0 : TIFFErrorExtR(tif, module,
749 : "LZWDecode: Strip %" PRIu32 " not terminated with EOI code",
750 : tif->tif_curstrip);
751 0 : return 0;
752 2 : error_code:
753 2 : memset(op, 0, (size_t)occ);
754 2 : sp->read_error = 1;
755 2 : TIFFErrorExtR(tif, tif->tif_name, "Using code not yet in table");
756 2 : return 0;
757 : }
758 :
759 : #ifdef LZW_COMPAT
760 :
761 : /*
762 : * This check shouldn't be necessary because each
763 : * strip is suppose to be terminated with CODE_EOI.
764 : */
765 : #define NextCode(_tif, _sp, _bp, _code, _get, dec_bitsleft) \
766 : { \
767 : if (dec_bitsleft < (uint64_t)nbits) \
768 : { \
769 : TIFFWarningExtR(_tif, module, \
770 : "LZWDecode: Strip %" PRIu32 \
771 : " not terminated with EOI code", \
772 : _tif->tif_curstrip); \
773 : _code = CODE_EOI; \
774 : } \
775 : else \
776 : { \
777 : _get(_sp, _bp, _code); \
778 : dec_bitsleft -= (uint64_t)nbits; \
779 : } \
780 : }
781 :
782 : /*
783 : * Decode a "hunk of data" for old images.
784 : */
785 : #define GetNextCodeCompat(sp, bp, code) \
786 : { \
787 : nextdata |= (unsigned long)*(bp)++ << nextbits; \
788 : nextbits += 8; \
789 : if (nextbits < nbits) \
790 : { \
791 : nextdata |= (unsigned long)*(bp)++ << nextbits; \
792 : nextbits += 8; \
793 : } \
794 : code = (hcode_t)(nextdata & (unsigned long)nbitsmask); \
795 : nextdata >>= nbits; \
796 : nextbits -= nbits; \
797 : }
798 :
799 104 : static int LZWDecodeCompat(TIFF *tif, uint8_t *op0, tmsize_t occ0, uint16_t s)
800 : {
801 : static const char module[] = "LZWDecodeCompat";
802 104 : LZWCodecState *sp = LZWDecoderState(tif);
803 104 : uint8_t *op = (uint8_t *)op0;
804 104 : tmsize_t occ = occ0;
805 : uint8_t *tp;
806 : uint8_t *bp;
807 : int code, nbits;
808 : int len;
809 : long nextbits, nbitsmask;
810 : WordType nextdata;
811 : code_t *codep, *free_entp, *maxcodep, *oldcodep;
812 :
813 : (void)s;
814 104 : assert(sp != NULL);
815 :
816 : /*
817 : * Restart interrupted output operation.
818 : */
819 104 : if (sp->dec_restart)
820 : {
821 : tmsize_t residue;
822 :
823 0 : codep = sp->dec_codep;
824 0 : residue = codep->length - sp->dec_restart;
825 0 : if (residue > occ)
826 : {
827 : /*
828 : * Residue from previous decode is sufficient
829 : * to satisfy decode request. Skip to the
830 : * start of the decoded string, place decoded
831 : * values in the output buffer, and return.
832 : */
833 0 : sp->dec_restart += occ;
834 0 : do
835 : {
836 0 : codep = codep->next;
837 0 : } while (--residue > occ);
838 0 : tp = op + occ;
839 0 : do
840 : {
841 0 : *--tp = codep->value;
842 0 : codep = codep->next;
843 0 : } while (--occ);
844 0 : return (1);
845 : }
846 : /*
847 : * Residue satisfies only part of the decode request.
848 : */
849 0 : op += residue;
850 0 : occ -= residue;
851 0 : tp = op;
852 0 : do
853 : {
854 0 : *--tp = codep->value;
855 0 : codep = codep->next;
856 0 : } while (--residue);
857 0 : sp->dec_restart = 0;
858 : }
859 :
860 104 : bp = (uint8_t *)tif->tif_rawcp;
861 :
862 104 : sp->dec_bitsleft +=
863 104 : (((uint64_t)tif->tif_rawcc - (uint64_t)sp->old_tif_rawcc) << 3);
864 104 : uint64_t dec_bitsleft = sp->dec_bitsleft;
865 :
866 104 : nbits = sp->lzw_nbits;
867 104 : nextdata = sp->lzw_nextdata;
868 104 : nextbits = sp->lzw_nextbits;
869 104 : nbitsmask = sp->dec_nbitsmask;
870 104 : oldcodep = sp->dec_oldcodep;
871 104 : free_entp = sp->dec_free_entp;
872 104 : maxcodep = sp->dec_maxcodep;
873 :
874 208335 : while (occ > 0)
875 : {
876 208231 : NextCode(tif, sp, bp, code, GetNextCodeCompat, dec_bitsleft);
877 208231 : if (code == CODE_EOI)
878 0 : break;
879 208231 : if (code == CODE_CLEAR)
880 : {
881 0 : do
882 : {
883 104 : free_entp = sp->dec_codetab + CODE_FIRST;
884 104 : _TIFFmemset(free_entp, 0,
885 : (CSIZE - CODE_FIRST) * sizeof(code_t));
886 104 : nbits = BITS_MIN;
887 104 : nbitsmask = MAXCODE(BITS_MIN);
888 104 : maxcodep = sp->dec_codetab + nbitsmask;
889 104 : NextCode(tif, sp, bp, code, GetNextCodeCompat, dec_bitsleft);
890 104 : } while (code == CODE_CLEAR); /* consecutive CODE_CLEAR codes */
891 104 : if (code == CODE_EOI)
892 0 : break;
893 104 : if (code > CODE_CLEAR)
894 : {
895 0 : TIFFErrorExtR(
896 0 : tif, tif->tif_name,
897 : "LZWDecode: Corrupted LZW table at scanline %" PRIu32,
898 : tif->tif_row);
899 0 : return (0);
900 : }
901 104 : *op++ = (uint8_t)code;
902 104 : occ--;
903 104 : oldcodep = sp->dec_codetab + code;
904 104 : continue;
905 : }
906 208127 : codep = sp->dec_codetab + code;
907 :
908 : /*
909 : * Add the new entry to the code table.
910 : */
911 208127 : if (free_entp < &sp->dec_codetab[0] ||
912 208127 : free_entp >= &sp->dec_codetab[CSIZE])
913 : {
914 0 : TIFFErrorExtR(tif, module,
915 : "Corrupted LZW table at scanline %" PRIu32,
916 : tif->tif_row);
917 0 : return (0);
918 : }
919 :
920 208127 : free_entp->next = oldcodep;
921 208127 : if (free_entp->next < &sp->dec_codetab[0] ||
922 208127 : free_entp->next >= &sp->dec_codetab[CSIZE])
923 : {
924 0 : TIFFErrorExtR(tif, module,
925 : "Corrupted LZW table at scanline %" PRIu32,
926 : tif->tif_row);
927 0 : return (0);
928 : }
929 208127 : free_entp->firstchar = free_entp->next->firstchar;
930 208127 : free_entp->length = free_entp->next->length + 1;
931 208127 : free_entp->value =
932 123 : (codep < free_entp) ? codep->firstchar : free_entp->firstchar;
933 208127 : if (++free_entp > maxcodep)
934 : {
935 8825 : if (++nbits > BITS_MAX) /* should not happen */
936 8645 : nbits = BITS_MAX;
937 8825 : nbitsmask = MAXCODE(nbits);
938 8825 : maxcodep = sp->dec_codetab + nbitsmask;
939 : }
940 208127 : oldcodep = codep;
941 208127 : if (code >= 256)
942 : {
943 : /*
944 : * Code maps to a string, copy string
945 : * value to output (written in reverse).
946 : */
947 69239 : if (codep->length == 0)
948 : {
949 0 : TIFFErrorExtR(
950 : tif, module,
951 : "Wrong length of decoded "
952 : "string: data probably corrupted at scanline %" PRIu32,
953 : tif->tif_row);
954 0 : return (0);
955 : }
956 69239 : if (codep->length > occ)
957 : {
958 : /*
959 : * String is too long for decode buffer,
960 : * locate portion that will fit, copy to
961 : * the decode buffer, and setup restart
962 : * logic for the next decoding call.
963 : */
964 0 : sp->dec_codep = codep;
965 0 : do
966 : {
967 0 : codep = codep->next;
968 0 : } while (codep->length > occ);
969 0 : sp->dec_restart = occ;
970 0 : tp = op + occ;
971 0 : do
972 : {
973 0 : *--tp = codep->value;
974 0 : codep = codep->next;
975 0 : } while (--occ);
976 0 : break;
977 : }
978 69239 : len = codep->length;
979 69239 : tp = op + len;
980 7556 : do
981 : {
982 658192 : *--tp = codep->value;
983 658192 : codep = codep->next;
984 658192 : } while (codep && tp > op);
985 69239 : assert(occ >= len);
986 69239 : op += len;
987 69239 : occ -= len;
988 : }
989 : else
990 : {
991 138888 : *op++ = (uint8_t)code;
992 138888 : occ--;
993 : }
994 : }
995 :
996 104 : tif->tif_rawcc -= (tmsize_t)((uint8_t *)bp - tif->tif_rawcp);
997 104 : tif->tif_rawcp = (uint8_t *)bp;
998 :
999 104 : sp->old_tif_rawcc = tif->tif_rawcc;
1000 104 : sp->dec_bitsleft = dec_bitsleft;
1001 :
1002 104 : sp->lzw_nbits = (unsigned short)nbits;
1003 104 : sp->lzw_nextdata = nextdata;
1004 104 : sp->lzw_nextbits = nextbits;
1005 104 : sp->dec_nbitsmask = nbitsmask;
1006 104 : sp->dec_oldcodep = oldcodep;
1007 104 : sp->dec_free_entp = free_entp;
1008 104 : sp->dec_maxcodep = maxcodep;
1009 :
1010 104 : if (occ > 0)
1011 : {
1012 0 : TIFFErrorExtR(tif, module,
1013 : "Not enough data at scanline %" PRIu32 " (short %" PRIu64
1014 : " bytes)",
1015 : tif->tif_row, (uint64_t)occ);
1016 0 : return (0);
1017 : }
1018 104 : return (1);
1019 : }
1020 : #endif /* LZW_COMPAT */
1021 :
1022 : #ifndef LZW_READ_ONLY
1023 :
1024 : static void cl_hash(LZWCodecState *);
1025 :
1026 : /*
1027 : * LZW Encoding.
1028 : */
1029 :
1030 11825 : static int LZWSetupEncode(TIFF *tif)
1031 : {
1032 : static const char module[] = "LZWSetupEncode";
1033 11825 : LZWCodecState *sp = LZWEncoderState(tif);
1034 :
1035 11825 : assert(sp != NULL);
1036 11825 : sp->enc_hashtab = (hash_t *)_TIFFmallocExt(tif, HSIZE * sizeof(hash_t));
1037 11825 : if (sp->enc_hashtab == NULL)
1038 : {
1039 0 : TIFFErrorExtR(tif, module, "No space for LZW hash table");
1040 0 : return (0);
1041 : }
1042 11825 : return (1);
1043 : }
1044 :
1045 : /*
1046 : * Reset encoding state at the start of a strip.
1047 : */
1048 13621 : static int LZWPreEncode(TIFF *tif, uint16_t s)
1049 : {
1050 13621 : LZWCodecState *sp = LZWEncoderState(tif);
1051 :
1052 : (void)s;
1053 13621 : assert(sp != NULL);
1054 :
1055 13621 : if (sp->enc_hashtab == NULL)
1056 : {
1057 2 : tif->tif_setupencode(tif);
1058 : }
1059 :
1060 13621 : sp->lzw_nbits = BITS_MIN;
1061 13621 : sp->lzw_maxcode = MAXCODE(BITS_MIN);
1062 13621 : sp->lzw_free_ent = CODE_FIRST;
1063 13621 : sp->lzw_nextbits = 0;
1064 13621 : sp->lzw_nextdata = 0;
1065 13621 : sp->enc_checkpoint = CHECK_GAP;
1066 13621 : sp->enc_ratio = 0;
1067 13621 : sp->enc_incount = 0;
1068 13621 : sp->enc_outcount = 0;
1069 : /*
1070 : * The 4 here insures there is space for 2 max-sized
1071 : * codes in LZWEncode and LZWPostDecode.
1072 : */
1073 13621 : sp->enc_rawlimit = tif->tif_rawdata + tif->tif_rawdatasize - 1 - 4;
1074 13621 : cl_hash(sp); /* clear hash table */
1075 13621 : sp->enc_oldcode = (hcode_t)-1; /* generates CODE_CLEAR in LZWEncode */
1076 13621 : return (1);
1077 : }
1078 :
1079 : #define CALCRATIO(sp, rat) \
1080 : { \
1081 : if (incount > 0x007fffff) \
1082 : { /* NB: shift will overflow */ \
1083 : rat = outcount >> 8; \
1084 : rat = (rat == 0 ? 0x7fffffff : incount / rat); \
1085 : } \
1086 : else \
1087 : rat = (incount << 8) / outcount; \
1088 : }
1089 :
1090 : /* Explicit 0xff masking to make icc -check=conversions happy */
1091 : #define PutNextCode(op, c) \
1092 : { \
1093 : nextdata = (nextdata << nbits) | c; \
1094 : nextbits += nbits; \
1095 : *op++ = (unsigned char)((nextdata >> (nextbits - 8)) & 0xff); \
1096 : nextbits -= 8; \
1097 : if (nextbits >= 8) \
1098 : { \
1099 : *op++ = (unsigned char)((nextdata >> (nextbits - 8)) & 0xff); \
1100 : nextbits -= 8; \
1101 : } \
1102 : outcount += nbits; \
1103 : }
1104 :
1105 : /*
1106 : * Encode a chunk of pixels.
1107 : *
1108 : * Uses an open addressing double hashing (no chaining) on the
1109 : * prefix code/next character combination. We do a variant of
1110 : * Knuth's algorithm D (vol. 3, sec. 6.4) along with G. Knott's
1111 : * relatively-prime secondary probe. Here, the modular division
1112 : * first probe is gives way to a faster exclusive-or manipulation.
1113 : * Also do block compression with an adaptive reset, whereby the
1114 : * code table is cleared when the compression ratio decreases,
1115 : * but after the table fills. The variable-length output codes
1116 : * are re-sized at this point, and a CODE_CLEAR is generated
1117 : * for the decoder.
1118 : */
1119 35617 : static int LZWEncode(TIFF *tif, uint8_t *bp, tmsize_t cc, uint16_t s)
1120 : {
1121 35617 : LZWCodecState *sp = LZWEncoderState(tif);
1122 : long fcode;
1123 : hash_t *hp;
1124 : int h, c;
1125 : hcode_t ent;
1126 : long disp;
1127 : tmsize_t incount, outcount, checkpoint;
1128 : WordType nextdata;
1129 : long nextbits;
1130 : int free_ent, maxcode, nbits;
1131 : uint8_t *op;
1132 : uint8_t *limit;
1133 :
1134 : (void)s;
1135 35617 : if (sp == NULL)
1136 0 : return (0);
1137 :
1138 35617 : assert(sp->enc_hashtab != NULL);
1139 :
1140 : /*
1141 : * Load local state.
1142 : */
1143 35617 : incount = sp->enc_incount;
1144 35617 : outcount = sp->enc_outcount;
1145 35617 : checkpoint = sp->enc_checkpoint;
1146 35617 : nextdata = sp->lzw_nextdata;
1147 35617 : nextbits = sp->lzw_nextbits;
1148 35617 : free_ent = sp->lzw_free_ent;
1149 35617 : maxcode = sp->lzw_maxcode;
1150 35617 : nbits = sp->lzw_nbits;
1151 35617 : op = tif->tif_rawcp;
1152 35617 : limit = sp->enc_rawlimit;
1153 35617 : ent = (hcode_t)sp->enc_oldcode;
1154 :
1155 35617 : if (ent == (hcode_t)-1 && cc > 0)
1156 : {
1157 : /*
1158 : * NB: This is safe because it can only happen
1159 : * at the start of a strip where we know there
1160 : * is space in the data buffer.
1161 : */
1162 13621 : PutNextCode(op, CODE_CLEAR);
1163 13621 : ent = *bp++;
1164 13621 : cc--;
1165 13621 : incount++;
1166 : }
1167 35617 : while (cc > 0)
1168 : {
1169 708661000 : c = *bp++;
1170 708661000 : cc--;
1171 708661000 : incount++;
1172 708661000 : fcode = ((long)c << BITS_MAX) + ent;
1173 708661000 : h = (c << HSHIFT) ^ ent; /* xor hashing */
1174 : #ifdef _WINDOWS
1175 : /*
1176 : * Check hash index for an overflow.
1177 : */
1178 : if (h >= HSIZE)
1179 : h -= HSIZE;
1180 : #endif
1181 708661000 : hp = &sp->enc_hashtab[h];
1182 708661000 : if (hp->hash == fcode)
1183 : {
1184 506575000 : ent = hp->code;
1185 506575000 : continue;
1186 : }
1187 202087000 : if (hp->hash >= 0)
1188 : {
1189 : /*
1190 : * Primary hash failed, check secondary hash.
1191 : */
1192 121460000 : disp = HSIZE - h;
1193 121460000 : if (h == 0)
1194 32697 : disp = 1;
1195 : do
1196 : {
1197 : /*
1198 : * Avoid pointer arithmetic because of
1199 : * wraparound problems with segments.
1200 : */
1201 179863000 : if ((h -= (int)disp) < 0)
1202 143215000 : h += HSIZE;
1203 179863000 : hp = &sp->enc_hashtab[h];
1204 179863000 : if (hp->hash == fcode)
1205 : {
1206 87252400 : ent = hp->code;
1207 87252400 : goto hit;
1208 : }
1209 92610200 : } while (hp->hash >= 0);
1210 : }
1211 : /*
1212 : * New entry, emit code and add to table.
1213 : */
1214 : /*
1215 : * Verify there is space in the buffer for the code
1216 : * and any potential Clear code that might be emitted
1217 : * below. The value of limit is setup so that there
1218 : * are at least 4 bytes free--room for 2 codes.
1219 : */
1220 114835000 : if (op > limit)
1221 : {
1222 1 : tif->tif_rawcc = (tmsize_t)(op - tif->tif_rawdata);
1223 1 : if (!TIFFFlushData1(tif))
1224 0 : return 0;
1225 1 : op = tif->tif_rawdata;
1226 : }
1227 114835000 : PutNextCode(op, ent);
1228 114835000 : ent = (hcode_t)c;
1229 114835000 : hp->code = (hcode_t)(free_ent++);
1230 114835000 : hp->hash = fcode;
1231 114835000 : if (free_ent == CODE_MAX - 1)
1232 : {
1233 : /* table is full, emit clear code and reset */
1234 29463 : cl_hash(sp);
1235 29463 : sp->enc_ratio = 0;
1236 29463 : incount = 0;
1237 29463 : outcount = 0;
1238 29463 : free_ent = CODE_FIRST;
1239 29463 : PutNextCode(op, CODE_CLEAR);
1240 29463 : nbits = BITS_MIN;
1241 29463 : maxcode = MAXCODE(BITS_MIN);
1242 : }
1243 : else
1244 : {
1245 : /*
1246 : * If the next entry is going to be too big for
1247 : * the code size, then increase it, if possible.
1248 : */
1249 114805000 : if (free_ent > maxcode)
1250 : {
1251 95632 : nbits++;
1252 95632 : assert(nbits <= BITS_MAX);
1253 95632 : maxcode = (int)MAXCODE(nbits);
1254 : }
1255 114709000 : else if (incount >= checkpoint)
1256 : {
1257 : tmsize_t rat;
1258 : /*
1259 : * Check compression ratio and, if things seem
1260 : * to be slipping, clear the hash table and
1261 : * reset state. The compression ratio is a
1262 : * 24+8-bit fractional number.
1263 : */
1264 48120 : checkpoint = incount + CHECK_GAP;
1265 48120 : CALCRATIO(sp, rat);
1266 48120 : if (rat <= sp->enc_ratio)
1267 : {
1268 207 : cl_hash(sp);
1269 207 : sp->enc_ratio = 0;
1270 207 : incount = 0;
1271 207 : outcount = 0;
1272 207 : free_ent = CODE_FIRST;
1273 207 : PutNextCode(op, CODE_CLEAR);
1274 207 : nbits = BITS_MIN;
1275 207 : maxcode = MAXCODE(BITS_MIN);
1276 : }
1277 : else
1278 47913 : sp->enc_ratio = rat;
1279 : }
1280 : }
1281 708697000 : hit:;
1282 : }
1283 :
1284 : /*
1285 : * Restore global state.
1286 : */
1287 35617 : sp->enc_incount = incount;
1288 35617 : sp->enc_outcount = outcount;
1289 35617 : sp->enc_checkpoint = checkpoint;
1290 35617 : sp->enc_oldcode = ent;
1291 35617 : sp->lzw_nextdata = nextdata;
1292 35617 : sp->lzw_nextbits = nextbits;
1293 35617 : sp->lzw_free_ent = (unsigned short)free_ent;
1294 35617 : sp->lzw_maxcode = (unsigned short)maxcode;
1295 35617 : sp->lzw_nbits = (unsigned short)nbits;
1296 35617 : tif->tif_rawcp = op;
1297 35617 : return (1);
1298 : }
1299 :
1300 : /*
1301 : * Finish off an encoded strip by flushing the last
1302 : * string and tacking on an End Of Information code.
1303 : */
1304 13621 : static int LZWPostEncode(TIFF *tif)
1305 : {
1306 13621 : LZWCodecState *sp = LZWEncoderState(tif);
1307 13621 : uint8_t *op = tif->tif_rawcp;
1308 13621 : long nextbits = sp->lzw_nextbits;
1309 13621 : WordType nextdata = sp->lzw_nextdata;
1310 13621 : tmsize_t outcount = sp->enc_outcount;
1311 13621 : int nbits = sp->lzw_nbits;
1312 :
1313 13621 : if (op > sp->enc_rawlimit)
1314 : {
1315 0 : tif->tif_rawcc = (tmsize_t)(op - tif->tif_rawdata);
1316 0 : if (!TIFFFlushData1(tif))
1317 0 : return 0;
1318 0 : op = tif->tif_rawdata;
1319 : }
1320 13621 : if (sp->enc_oldcode != (hcode_t)-1)
1321 : {
1322 13621 : int free_ent = sp->lzw_free_ent;
1323 :
1324 13621 : PutNextCode(op, (WordType)sp->enc_oldcode);
1325 13621 : sp->enc_oldcode = (hcode_t)-1;
1326 13621 : free_ent++;
1327 :
1328 13621 : if (free_ent == CODE_MAX - 1)
1329 : {
1330 : /* table is full, emit clear code and reset */
1331 0 : outcount = 0;
1332 0 : PutNextCode(op, CODE_CLEAR);
1333 0 : nbits = BITS_MIN;
1334 : }
1335 : else
1336 : {
1337 : /*
1338 : * If the next entry is going to be too big for
1339 : * the code size, then increase it, if possible.
1340 : */
1341 13621 : if (free_ent > sp->lzw_maxcode)
1342 : {
1343 2 : nbits++;
1344 2 : assert(nbits <= BITS_MAX);
1345 : }
1346 : }
1347 : }
1348 13621 : PutNextCode(op, CODE_EOI);
1349 : /* Explicit 0xff masking to make icc -check=conversions happy */
1350 13621 : if (nextbits > 0)
1351 13486 : *op++ = (unsigned char)((nextdata << (8 - nextbits)) & 0xff);
1352 13621 : tif->tif_rawcc = (tmsize_t)(op - tif->tif_rawdata);
1353 : (void)outcount;
1354 13621 : return (1);
1355 : }
1356 :
1357 : /*
1358 : * Reset encoding hash table.
1359 : */
1360 43291 : static void cl_hash(LZWCodecState *sp)
1361 : {
1362 43291 : hash_t *hp = &sp->enc_hashtab[HSIZE - 1];
1363 43291 : long i = HSIZE - 8;
1364 :
1365 : do
1366 : {
1367 48700300 : i -= 8;
1368 48700300 : hp[-7].hash = -1;
1369 48700300 : hp[-6].hash = -1;
1370 48700300 : hp[-5].hash = -1;
1371 48700300 : hp[-4].hash = -1;
1372 48700300 : hp[-3].hash = -1;
1373 48700300 : hp[-2].hash = -1;
1374 48700300 : hp[-1].hash = -1;
1375 48700300 : hp[0].hash = -1;
1376 48700300 : hp -= 8;
1377 48700300 : } while (i >= 0);
1378 86582 : for (i += 8; i > 0; i--, hp--)
1379 43291 : hp->hash = -1;
1380 43291 : }
1381 :
1382 : #endif
1383 :
1384 19405 : static void LZWCleanup(TIFF *tif)
1385 : {
1386 19405 : (void)TIFFPredictorCleanup(tif);
1387 :
1388 19404 : assert(tif->tif_data != NULL);
1389 :
1390 19404 : if (LZWDecoderState(tif)->dec_codetab)
1391 2680 : _TIFFfreeExt(tif, LZWDecoderState(tif)->dec_codetab);
1392 :
1393 19405 : if (LZWEncoderState(tif)->enc_hashtab)
1394 11825 : _TIFFfreeExt(tif, LZWEncoderState(tif)->enc_hashtab);
1395 :
1396 19405 : _TIFFfreeExt(tif, tif->tif_data);
1397 19407 : tif->tif_data = NULL;
1398 :
1399 19407 : _TIFFSetDefaultCompressionState(tif);
1400 19405 : }
1401 :
1402 19407 : int TIFFInitLZW(TIFF *tif, int scheme)
1403 : {
1404 : static const char module[] = "TIFFInitLZW";
1405 : (void)scheme;
1406 19407 : assert(scheme == COMPRESSION_LZW);
1407 : /*
1408 : * Allocate state block so tag methods have storage to record values.
1409 : */
1410 19407 : tif->tif_data = (uint8_t *)_TIFFmallocExt(tif, sizeof(LZWCodecState));
1411 19407 : if (tif->tif_data == NULL)
1412 0 : goto bad;
1413 19407 : LZWDecoderState(tif)->dec_codetab = NULL;
1414 19407 : LZWDecoderState(tif)->dec_decode = NULL;
1415 19407 : LZWEncoderState(tif)->enc_hashtab = NULL;
1416 19407 : LZWState(tif)->rw_mode = tif->tif_mode;
1417 :
1418 : /*
1419 : * Install codec methods.
1420 : */
1421 19407 : tif->tif_fixuptags = LZWFixupTags;
1422 19407 : tif->tif_setupdecode = LZWSetupDecode;
1423 19407 : tif->tif_predecode = LZWPreDecode;
1424 19407 : tif->tif_decoderow = LZWDecode;
1425 19407 : tif->tif_decodestrip = LZWDecode;
1426 19407 : tif->tif_decodetile = LZWDecode;
1427 : #ifndef LZW_READ_ONLY
1428 19333 : tif->tif_setupencode = LZWSetupEncode;
1429 19333 : tif->tif_preencode = LZWPreEncode;
1430 19333 : tif->tif_postencode = LZWPostEncode;
1431 19333 : tif->tif_encoderow = LZWEncode;
1432 19333 : tif->tif_encodestrip = LZWEncode;
1433 19333 : tif->tif_encodetile = LZWEncode;
1434 : #endif
1435 19407 : tif->tif_cleanup = LZWCleanup;
1436 : /*
1437 : * Setup predictor setup.
1438 : */
1439 19407 : (void)TIFFPredictorInit(tif);
1440 19408 : return (1);
1441 0 : bad:
1442 0 : TIFFErrorExtR(tif, module, "No space for LZW state block");
1443 0 : return (0);
1444 : }
1445 :
1446 : /*
1447 : * Copyright (c) 1985, 1986 The Regents of the University of California.
1448 : * All rights reserved.
1449 : *
1450 : * This code is derived from software contributed to Berkeley by
1451 : * James A. Woods, derived from original work by Spencer Thomas
1452 : * and Joseph Orost.
1453 : *
1454 : * Redistribution and use in source and binary forms are permitted
1455 : * provided that the above copyright notice and this paragraph are
1456 : * duplicated in all such forms and that any documentation,
1457 : * advertising materials, and other materials related to such
1458 : * distribution and use acknowledge that the software was developed
1459 : * by the University of California, Berkeley. The name of the
1460 : * University may not be used to endorse or promote products derived
1461 : * from this software without specific prior written permission.
1462 : * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR
1463 : * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED
1464 : * WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE.
1465 : */
1466 : #endif /* LZW_SUPPORT */
|
