| #ifndef lint |
| static char rcsid[] = "$Header: /cvs/bao-parsec/ext/splash2/apps/volrend/src/libtiff/tif_lzw.c,v 1.1.1.1 2012/03/29 17:22:40 uid42307 Exp $"; |
| #endif |
| |
| /* |
| * Copyright (c) 1988, 1989, 1990, 1991, 1992 Sam Leffler |
| * Copyright (c) 1991, 1992 Silicon Graphics, Inc. |
| * |
| * Permission to use, copy, modify, distribute, and sell this software and |
| * its documentation for any purpose is hereby granted without fee, provided |
| * that (i) the above copyright notices and this permission notice appear in |
| * all copies of the software and related documentation, and (ii) the names of |
| * Sam Leffler and Silicon Graphics may not be used in any advertising or |
| * publicity relating to the software without the specific, prior written |
| * permission of Sam Leffler and Silicon Graphics. |
| * |
| * THE SOFTWARE IS PROVIDED "AS-IS" AND WITHOUT WARRANTY OF ANY KIND, |
| * EXPRESS, IMPLIED OR OTHERWISE, INCLUDING WITHOUT LIMITATION, ANY |
| * WARRANTY OF MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE. |
| * |
| * IN NO EVENT SHALL SAM LEFFLER OR SILICON GRAPHICS BE LIABLE FOR |
| * ANY SPECIAL, INCIDENTAL, INDIRECT OR CONSEQUENTIAL DAMAGES OF ANY KIND, |
| * OR ANY DAMAGES WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, |
| * WHETHER OR NOT ADVISED OF THE POSSIBILITY OF DAMAGE, AND ON ANY THEORY OF |
| * LIABILITY, ARISING OUT OF OR IN CONNECTION WITH THE USE OR PERFORMANCE |
| * OF THIS SOFTWARE. |
| */ |
| |
| /* |
| * TIFF Library. |
| * Rev 5.0 Lempel-Ziv & Welch Compression Support |
| * |
| * This code is derived from the compress program whose code is |
| * derived from software contributed to Berkeley by James A. Woods, |
| * derived from original work by Spencer Thomas and Joseph Orost. |
| * |
| * The original Berkeley copyright notice appears below in its entirety. |
| */ |
| #include "tiffioP.h" |
| #include <stdio.h> |
| #include <assert.h> |
| #include "prototypes.h" |
| |
| #define MAXCODE(n) ((1 << (n)) - 1) |
| /* |
| * The TIFF spec specifies that encoded bit strings range |
| * from 9 to 12 bits. This is somewhat unfortunate in that |
| * experience indicates full color RGB pictures often need |
| * ~14 bits for reasonable compression. |
| */ |
| #define BITS_MIN 9 /* start with 9 bits */ |
| #define BITS_MAX 12 /* max of 12 bit strings */ |
| /* predefined codes */ |
| #define CODE_CLEAR 256 /* code to clear string table */ |
| #define CODE_EOI 257 /* end-of-information code */ |
| #define CODE_FIRST 258 /* first free code entry */ |
| #define CODE_MAX MAXCODE(BITS_MAX) |
| #ifdef notdef |
| #define HSIZE 9001 /* 91% occupancy */ |
| #define HSHIFT (8-(16-13)) |
| #else |
| #define HSIZE 5003 /* 80% occupancy */ |
| #define HSHIFT (8-(16-12)) |
| #endif |
| |
| /* |
| * NB: The 5.0 spec describes a different algorithm than Aldus |
| * implements. Specifically, Aldus does code length transitions |
| * one code earlier than should be done (for real LZW). |
| * Earlier versions of this library implemented the correct |
| * LZW algorithm, but emitted codes in a bit order opposite |
| * to the TIFF spec. Thus, to maintain compatibility w/ Aldus |
| * we interpret MSB-LSB ordered codes to be images written w/ |
| * old versions of this library, but otherwise adhere to the |
| * Aldus "off by one" algorithm. |
| * |
| * Future revisions to the TIFF spec are expected to "clarify this issue". |
| */ |
| #define SetMaxCode(sp, v) { \ |
| (sp)->lzw_maxcode = (v)-1; \ |
| if ((sp)->lzw_flags & LZW_COMPAT) \ |
| (sp)->lzw_maxcode++; \ |
| } |
| |
| /* |
| * Decoding-specific state. |
| */ |
| struct decode { |
| short prefixtab[HSIZE]; /* prefix(code) */ |
| u_char suffixtab[CODE_MAX+1]; /* suffix(code) */ |
| u_char stack[HSIZE-(CODE_MAX+1)]; |
| u_char *stackp; /* stack pointer */ |
| int firstchar; /* of string associated w/ last code */ |
| }; |
| |
| /* |
| * Encoding-specific state. |
| */ |
| struct encode { |
| long checkpoint; /* point at which to clear table */ |
| #define CHECK_GAP 10000 /* enc_ratio check interval */ |
| long ratio; /* current compression ratio */ |
| long incount; /* (input) data bytes encoded */ |
| long outcount; /* encoded (output) bytes */ |
| long htab[HSIZE]; /* hash table */ |
| short codetab[HSIZE]; /* code table */ |
| }; |
| |
| #if USE_PROTOTYPES |
| typedef void (*predictorFunc)(char* data, int nbytes, int stride); |
| #else |
| typedef void (*predictorFunc)(); |
| #endif |
| |
| /* |
| * State block for each open TIFF |
| * file using LZW compression/decompression. |
| */ |
| typedef struct { |
| int lzw_oldcode; /* last code encountered */ |
| u_short lzw_flags; |
| #define LZW_RESTART 0x01 /* restart interrupted decode */ |
| #define LZW_COMPAT 0x02 /* read old bit-reversed codes */ |
| u_short lzw_nbits; /* number of bits/code */ |
| u_short lzw_stride; /* horizontal diferencing stride */ |
| u_short lzw_rowsize; /* XXX maybe should be a long? */ |
| predictorFunc lzw_hordiff; |
| int lzw_maxcode; /* maximum code for lzw_nbits */ |
| long lzw_bitoff; /* bit offset into data */ |
| long lzw_bitsize; /* size of strip in bits */ |
| int lzw_free_ent; /* next free entry in hash table */ |
| union { |
| struct decode dec; |
| struct encode enc; |
| } u; |
| } LZWState; |
| #define dec_prefix u.dec.prefixtab |
| #define dec_suffix u.dec.suffixtab |
| #define dec_stack u.dec.stack |
| #define dec_stackp u.dec.stackp |
| #define dec_firstchar u.dec.firstchar |
| |
| #define enc_checkpoint u.enc.checkpoint |
| #define enc_ratio u.enc.ratio |
| #define enc_incount u.enc.incount |
| #define enc_outcount u.enc.outcount |
| #define enc_htab u.enc.htab |
| #define enc_codetab u.enc.codetab |
| |
| /* masks for extracting/inserting variable length bit codes */ |
| static const u_char rmask[9] = |
| { 0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff }; |
| static const u_char lmask[9] = |
| { 0x00, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe, 0xff }; |
| |
| #if USE_PROTOTYPES |
| static int LZWPreEncode(TIFF*); |
| static int LZWEncode(TIFF*, u_char*, int, u_int); |
| static int LZWEncodePredRow(TIFF*, u_char*, int, u_int); |
| static int LZWEncodePredTile(TIFF*, u_char*, int, u_int); |
| static int LZWPostEncode(TIFF*); |
| static int LZWDecode(TIFF*, u_char*, int, u_int); |
| static int LZWDecodePredRow(TIFF*, u_char*, int, u_int); |
| static int LZWDecodePredTile(TIFF*, u_char*, int, u_int); |
| static int LZWPreDecode(TIFF*); |
| static int LZWCleanup(TIFF*); |
| static int GetNextCode(TIFF*); |
| static void PutNextCode(TIFF*, int); |
| static void cl_block(TIFF*); |
| static void cl_hash(LZWState*); |
| extern int TIFFFlushData1(TIFF *); |
| #else |
| static int LZWPreEncode(), LZWEncode(), LZWPostEncode(); |
| static int LZWEncodePredRow(), LZWEncodePredTile(); |
| static int LZWPreDecode(), LZWDecode(); |
| static int LZWDecodePredRow(), LZWDecodePredTile(); |
| static int LZWCleanup(); |
| static int GetNextCode(); |
| static void PutNextCode(); |
| static void cl_block(); |
| static void cl_hash(); |
| extern int TIFFFlushData1(); |
| #endif |
| |
| TIFFInitLZW(tif) |
| TIFF *tif; |
| { |
| tif->tif_predecode = LZWPreDecode; |
| tif->tif_decoderow = LZWDecode; |
| tif->tif_decodestrip = LZWDecode; |
| tif->tif_decodetile = LZWDecode; |
| tif->tif_preencode = LZWPreEncode; |
| tif->tif_postencode = LZWPostEncode; |
| tif->tif_encoderow = LZWEncode; |
| tif->tif_encodestrip = LZWEncode; |
| tif->tif_encodetile = LZWEncode; |
| tif->tif_cleanup = LZWCleanup; |
| return (1); |
| } |
| |
| static |
| DECLARE4(LZWCheckPredictor, |
| TIFF*, tif, |
| LZWState*, sp, |
| predictorFunc, pred8bit, |
| predictorFunc, pred16bit |
| ) |
| { |
| TIFFDirectory *td = &tif->tif_dir; |
| |
| switch (td->td_predictor) { |
| case 1: |
| break; |
| case 2: |
| sp->lzw_stride = (td->td_planarconfig == PLANARCONFIG_CONTIG ? |
| td->td_samplesperpixel : 1); |
| switch (td->td_bitspersample) { |
| case 8: |
| sp->lzw_hordiff = pred8bit; |
| break; |
| case 16: |
| sp->lzw_hordiff = pred16bit; |
| break; |
| default: |
| TIFFError(tif->tif_name, |
| "Horizontal differencing \"Predictor\" not supported with %d-bit samples", |
| td->td_bitspersample); |
| return (0); |
| } |
| break; |
| default: |
| TIFFError(tif->tif_name, "\"Predictor\" value %d not supported", |
| td->td_predictor); |
| return (0); |
| } |
| if (sp->lzw_hordiff) { |
| /* |
| * Calculate the scanline/tile-width size in bytes. |
| */ |
| if (isTiled(tif)) |
| sp->lzw_rowsize = TIFFTileRowSize(tif); |
| else |
| sp->lzw_rowsize = TIFFScanlineSize(tif); |
| } |
| return (1); |
| } |
| |
| /* |
| * LZW Decoder. |
| */ |
| |
| #define REPEAT4(n, op) \ |
| switch (n) { \ |
| default: { int i; for (i = n-4; i > 0; i--) { op; } } \ |
| case 4: op; \ |
| case 3: op; \ |
| case 2: op; \ |
| case 1: op; \ |
| case 0: ; \ |
| } |
| |
| static void |
| DECLARE3(horizontalAccumulate8, |
| register char*, cp, |
| register int, cc, |
| register int, stride |
| ) |
| { |
| if (cc > stride) { |
| cc -= stride; |
| do { |
| REPEAT4(stride, cp[stride] += cp[0]; cp++) |
| cc -= stride; |
| } while (cc > 0); |
| } |
| } |
| |
| static void |
| DECLARE3(horizontalAccumulate16, |
| char*, cp, |
| int, cc, |
| register int, stride |
| ) |
| { |
| register short* wp = (short *)cp; |
| register int wc = cc / 2; |
| |
| if (wc > stride) { |
| wc -= stride; |
| do { |
| REPEAT4(stride, wp[stride] += wp[0]; wp++) |
| wc -= stride; |
| } while (wc > 0); |
| } |
| } |
| |
| /* |
| * Setup state for decoding a strip. |
| */ |
| static |
| LZWPreDecode(tif) |
| TIFF *tif; |
| { |
| register LZWState *sp = (LZWState *)tif->tif_data; |
| register int code; |
| |
| if (sp == NULL) { |
| tif->tif_data = malloc(sizeof (LZWState)); |
| if (tif->tif_data == NULL) { |
| TIFFError("LZWPreDecode", |
| "No space for LZW state block"); |
| return (0); |
| } |
| sp = (LZWState *)tif->tif_data; |
| sp->lzw_flags = 0; |
| sp->lzw_hordiff = 0; |
| sp->lzw_rowsize = 0; |
| if (!LZWCheckPredictor(tif, sp, |
| horizontalAccumulate8, horizontalAccumulate16)) |
| return (0); |
| if (sp->lzw_hordiff) { |
| /* |
| * Override default decoding method with |
| * one that does the predictor stuff. |
| */ |
| tif->tif_decoderow = LZWDecodePredRow; |
| tif->tif_decodestrip = LZWDecodePredTile; |
| tif->tif_decodetile = LZWDecodePredTile; |
| } |
| } else |
| sp->lzw_flags &= ~LZW_RESTART; |
| sp->lzw_nbits = BITS_MIN; |
| /* |
| * Pre-load the table. |
| */ |
| for (code = 255; code >= 0; code--) |
| sp->dec_suffix[code] = (u_char)code; |
| sp->lzw_free_ent = CODE_FIRST; |
| sp->lzw_bitoff = 0; |
| /* calculate data size in bits */ |
| sp->lzw_bitsize = tif->tif_rawdatasize; |
| sp->lzw_bitsize = (sp->lzw_bitsize << 3) - (BITS_MAX-1); |
| sp->dec_stackp = sp->dec_stack; |
| sp->lzw_oldcode = -1; |
| sp->dec_firstchar = -1; |
| /* |
| * Check for old bit-reversed codes. All the flag |
| * manipulations are to insure only one warning is |
| * given for a file. |
| */ |
| if (tif->tif_rawdata[0] == 0 && (tif->tif_rawdata[1] & 0x1)) { |
| if ((sp->lzw_flags & LZW_COMPAT) == 0) |
| TIFFWarning(tif->tif_name, |
| "Old-style LZW codes, convert file"); |
| sp->lzw_flags |= LZW_COMPAT; |
| } else |
| sp->lzw_flags &= ~LZW_COMPAT; |
| SetMaxCode(sp, MAXCODE(BITS_MIN)); |
| return (1); |
| } |
| |
| /* |
| * Decode a "hunk of data". |
| */ |
| static |
| LZWDecode(tif, op0, occ0, s) |
| TIFF *tif; |
| u_char *op0; |
| u_int s; |
| { |
| register char *op = (char *)op0; |
| register int occ = occ0; |
| register LZWState *sp = (LZWState *)tif->tif_data; |
| register int code; |
| register u_char *stackp; |
| int firstchar, oldcode, incode; |
| |
| stackp = sp->dec_stackp; |
| /* |
| * Restart interrupted unstacking operations. |
| */ |
| if (sp->lzw_flags & LZW_RESTART) { |
| do { |
| if (--occ < 0) { /* end of scanline */ |
| sp->dec_stackp = stackp; |
| return (1); |
| } |
| *op++ = *--stackp; |
| } while (stackp > sp->dec_stack); |
| sp->lzw_flags &= ~LZW_RESTART; |
| } |
| oldcode = sp->lzw_oldcode; |
| firstchar = sp->dec_firstchar; |
| while (occ > 0 && (code = GetNextCode(tif)) != CODE_EOI) { |
| if (code == CODE_CLEAR) { |
| bzero(sp->dec_prefix, sizeof (sp->dec_prefix)); |
| sp->lzw_free_ent = CODE_FIRST; |
| sp->lzw_nbits = BITS_MIN; |
| SetMaxCode(sp, MAXCODE(BITS_MIN)); |
| if ((code = GetNextCode(tif)) == CODE_EOI) |
| break; |
| *op++ = code, occ--; |
| oldcode = firstchar = code; |
| continue; |
| } |
| incode = code; |
| /* |
| * When a code is not in the table we use (as spec'd): |
| * StringFromCode(oldcode) + |
| * FirstChar(StringFromCode(oldcode)) |
| */ |
| if (code >= sp->lzw_free_ent) { /* code not in table */ |
| *stackp++ = firstchar; |
| code = oldcode; |
| } |
| |
| /* |
| * Generate output string (first in reverse). |
| */ |
| for (; code >= 256; code = sp->dec_prefix[code]) |
| *stackp++ = sp->dec_suffix[code]; |
| *stackp++ = firstchar = sp->dec_suffix[code]; |
| do { |
| if (--occ < 0) { /* end of scanline */ |
| sp->lzw_flags |= LZW_RESTART; |
| break; |
| } |
| *op++ = *--stackp; |
| } while (stackp > sp->dec_stack); |
| |
| /* |
| * Add the new entry to the code table. |
| */ |
| if ((code = sp->lzw_free_ent) < CODE_MAX) { |
| sp->dec_prefix[code] = (u_short)oldcode; |
| sp->dec_suffix[code] = firstchar; |
| sp->lzw_free_ent++; |
| /* |
| * If the next entry is too big for the |
| * current code size, then increase the |
| * size up to the maximum possible. |
| */ |
| if (sp->lzw_free_ent > sp->lzw_maxcode) { |
| sp->lzw_nbits++; |
| if (sp->lzw_nbits > BITS_MAX) |
| sp->lzw_nbits = BITS_MAX; |
| SetMaxCode(sp, MAXCODE(sp->lzw_nbits)); |
| } |
| } |
| oldcode = incode; |
| } |
| sp->dec_stackp = stackp; |
| sp->lzw_oldcode = oldcode; |
| sp->dec_firstchar = firstchar; |
| if (occ > 0) { |
| TIFFError(tif->tif_name, |
| "LZWDecode: Not enough data at scanline %d (short %d bytes)", |
| tif->tif_row, occ); |
| return (0); |
| } |
| return (1); |
| } |
| |
| /* |
| * Decode a scanline and apply the predictor routine. |
| */ |
| static |
| LZWDecodePredRow(tif, op0, occ0, s) |
| TIFF *tif; |
| u_char *op0; |
| u_int s; |
| { |
| LZWState *sp = (LZWState *)tif->tif_data; |
| |
| if (LZWDecode(tif, op0, occ0, s)) { |
| (*sp->lzw_hordiff)((char *)op0, occ0, sp->lzw_stride); |
| return (1); |
| } else |
| return (0); |
| } |
| |
| /* |
| * Decode a tile/strip and apply the predictor routine. |
| * Note that horizontal differencing must be done on a |
| * row-by-row basis. The width of a "row" has already |
| * been calculated at pre-decode time according to the |
| * strip/tile dimensions. |
| */ |
| static |
| LZWDecodePredTile(tif, op0, occ0, s) |
| TIFF *tif; |
| u_char *op0; |
| u_int s; |
| { |
| LZWState *sp = (LZWState *)tif->tif_data; |
| |
| if (!LZWDecode(tif, op0, occ0, s)) |
| return (0); |
| while (occ0 > 0) { |
| (*sp->lzw_hordiff)((char *)op0, sp->lzw_rowsize, sp->lzw_stride); |
| occ0 -= sp->lzw_rowsize; |
| op0 += sp->lzw_rowsize; |
| } |
| return (1); |
| } |
| |
| /* |
| * Get the next code from the raw data buffer. |
| */ |
| static |
| GetNextCode(tif) |
| TIFF *tif; |
| { |
| register LZWState *sp = (LZWState *)tif->tif_data; |
| register int code, bits; |
| register long r_off; |
| register u_char *bp; |
| |
| /* |
| * This check shouldn't be necessary because each |
| * strip is suppose to be terminated with CODE_EOI. |
| * At worst it's a substitute for the CODE_EOI that's |
| * supposed to be there (see calculation of lzw_bitsize |
| * in LZWPreDecode()). |
| */ |
| if (sp->lzw_bitoff > sp->lzw_bitsize) { |
| TIFFWarning(tif->tif_name, |
| "LZWDecode: Strip %d not terminated with EOI code", |
| tif->tif_curstrip); |
| return (CODE_EOI); |
| } |
| r_off = sp->lzw_bitoff; |
| bits = sp->lzw_nbits; |
| /* |
| * Get to the first byte. |
| */ |
| bp = (u_char *)tif->tif_rawdata + (r_off >> 3); |
| r_off &= 7; |
| if (sp->lzw_flags & LZW_COMPAT) { |
| /* Get first part (low order bits) */ |
| code = (*bp++ >> r_off); |
| r_off = 8 - r_off; /* now, offset into code word */ |
| bits -= r_off; |
| /* Get any 8 bit parts in the middle (<=1 for up to 16 bits). */ |
| if (bits >= 8) { |
| code |= *bp++ << r_off; |
| r_off += 8; |
| bits -= 8; |
| } |
| /* high order bits. */ |
| code |= (*bp & rmask[bits]) << r_off; |
| } else { |
| r_off = 8 - r_off; /* convert offset to count */ |
| code = *bp++ & rmask[r_off]; /* high order bits */ |
| bits -= r_off; |
| if (bits >= 8) { |
| code = (code<<8) | *bp++; |
| bits -= 8; |
| } |
| /* low order bits */ |
| code = (code << bits) | |
| (((unsigned)(*bp & lmask[bits])) >> (8 - bits)); |
| } |
| sp->lzw_bitoff += sp->lzw_nbits; |
| return (code); |
| } |
| |
| /* |
| * LZW Encoding. |
| */ |
| |
| static void |
| DECLARE3(horizontalDifference8, |
| register char*, cp, |
| register int, cc, |
| register int, stride |
| ) |
| { |
| if (cc > stride) { |
| cc -= stride; |
| cp += cc - 1; |
| do { |
| REPEAT4(stride, cp[stride] -= cp[0]; cp--) |
| cc -= stride; |
| } while (cc > 0); |
| } |
| } |
| |
| static void |
| DECLARE3(horizontalDifference16, |
| char*, cp, |
| int, cc, |
| register int, stride |
| ) |
| { |
| register short *wp = (short *)cp; |
| register int wc = cc/2; |
| |
| if (wc > stride) { |
| wc -= stride; |
| wp += wc - 1; |
| do { |
| REPEAT4(stride, wp[stride] -= wp[0]; wp--) |
| wc -= stride; |
| } while (wc > 0); |
| } |
| } |
| |
| /* |
| * Reset encoding state at the start of a strip. |
| */ |
| static |
| LZWPreEncode(tif) |
| TIFF *tif; |
| { |
| register LZWState *sp = (LZWState *)tif->tif_data; |
| |
| if (sp == NULL) { |
| tif->tif_data = malloc(sizeof (LZWState)); |
| if (tif->tif_data == NULL) { |
| TIFFError("LZWPreEncode", |
| "No space for LZW state block"); |
| return (0); |
| } |
| sp = (LZWState *)tif->tif_data; |
| sp->lzw_flags = 0; |
| sp->lzw_hordiff = 0; |
| if (!LZWCheckPredictor(tif, sp, |
| horizontalDifference8, horizontalDifference16)) |
| return (0); |
| if (sp->lzw_hordiff) { |
| tif->tif_encoderow = LZWEncodePredRow; |
| tif->tif_encodestrip = LZWEncodePredTile; |
| tif->tif_encodetile = LZWEncodePredTile; |
| } |
| } |
| sp->enc_checkpoint = CHECK_GAP; |
| SetMaxCode(sp, MAXCODE(sp->lzw_nbits = BITS_MIN)+1); |
| cl_hash(sp); /* clear hash table */ |
| sp->lzw_bitoff = 0; |
| sp->lzw_bitsize = (tif->tif_rawdatasize << 3) - (BITS_MAX-1); |
| sp->lzw_oldcode = -1; /* generates CODE_CLEAR in LZWEncode */ |
| return (1); |
| } |
| |
| /* |
| * Encode a scanline of pixels. |
| * |
| * Uses an open addressing double hashing (no chaining) on the |
| * prefix code/next character combination. We do a variant of |
| * Knuth's algorithm D (vol. 3, sec. 6.4) along with G. Knott's |
| * relatively-prime secondary probe. Here, the modular division |
| * first probe is gives way to a faster exclusive-or manipulation. |
| * Also do block compression with an adaptive reset, whereby the |
| * code table is cleared when the compression ratio decreases, |
| * but after the table fills. The variable-length output codes |
| * are re-sized at this point, and a CODE_CLEAR is generated |
| * for the decoder. |
| */ |
| static |
| LZWEncode(tif, bp, cc, s) |
| TIFF *tif; |
| u_char *bp; |
| int cc; |
| u_int s; |
| { |
| static char module[] = "LZWEncode"; |
| register LZWState *sp; |
| register long fcode; |
| register int h, c, ent, disp; |
| |
| if ((sp = (LZWState *)tif->tif_data) == NULL) |
| return (0); |
| ent = sp->lzw_oldcode; |
| if (ent == -1 && cc > 0) { |
| PutNextCode(tif, CODE_CLEAR); |
| ent = *bp++; cc--; sp->enc_incount++; |
| } |
| while (cc > 0) { |
| c = *bp++; cc--; sp->enc_incount++; |
| fcode = ((long)c << BITS_MAX) + ent; |
| h = (c << HSHIFT) ^ ent; /* xor hashing */ |
| if (sp->enc_htab[h] == fcode) { |
| ent = sp->enc_codetab[h]; |
| continue; |
| } |
| if (sp->enc_htab[h] >= 0) { |
| /* |
| * Primary hash failed, check secondary hash. |
| */ |
| disp = HSIZE - h; |
| if (h == 0) |
| disp = 1; |
| do { |
| if ((h -= disp) < 0) |
| h += HSIZE; |
| if (sp->enc_htab[h] == fcode) { |
| ent = sp->enc_codetab[h]; |
| goto hit; |
| } |
| } while (sp->enc_htab[h] >= 0); |
| } |
| /* |
| * New entry, emit code and add to table. |
| */ |
| PutNextCode(tif, ent); |
| ent = c; |
| sp->enc_codetab[h] = sp->lzw_free_ent++; |
| sp->enc_htab[h] = fcode; |
| if (sp->lzw_free_ent == CODE_MAX-1) { |
| /* table is full, emit clear code and reset */ |
| cl_hash(sp); |
| PutNextCode(tif, CODE_CLEAR); |
| SetMaxCode(sp, MAXCODE(sp->lzw_nbits = BITS_MIN)+1); |
| } else { |
| /* |
| * If the next entry is going to be too big for |
| * the code size, then increase it, if possible. |
| */ |
| if (sp->lzw_free_ent > sp->lzw_maxcode) { |
| sp->lzw_nbits++; |
| assert(sp->lzw_nbits <= BITS_MAX); |
| SetMaxCode(sp, MAXCODE(sp->lzw_nbits)+1); |
| } else if (sp->enc_incount >= sp->enc_checkpoint) |
| cl_block(tif); |
| } |
| hit: |
| ; |
| } |
| sp->lzw_oldcode = ent; |
| return (1); |
| } |
| |
| static |
| LZWEncodePredRow(tif, bp, cc, s) |
| TIFF *tif; |
| u_char *bp; |
| int cc; |
| u_int s; |
| { |
| LZWState *sp = (LZWState *)tif->tif_data; |
| |
| /* XXX horizontal differencing alters user's data XXX */ |
| (*sp->lzw_hordiff)((char *)bp, cc, sp->lzw_stride); |
| return (LZWEncode(tif, bp, cc, s)); |
| } |
| |
| static |
| LZWEncodePredTile(tif, bp0, cc0, s) |
| TIFF *tif; |
| u_char *bp0; |
| int cc0; |
| u_int s; |
| { |
| LZWState *sp = (LZWState *)tif->tif_data; |
| int cc = cc0; |
| u_char *bp = bp0; |
| |
| while (cc > 0) { |
| (*sp->lzw_hordiff)((char *)bp, sp->lzw_rowsize, sp->lzw_stride); |
| cc -= sp->lzw_rowsize; |
| bp += sp->lzw_rowsize; |
| } |
| return (LZWEncode(tif, bp0, cc0, s)); |
| } |
| |
| /* |
| * Finish off an encoded strip by flushing the last |
| * string and tacking on an End Of Information code. |
| */ |
| static |
| LZWPostEncode(tif) |
| TIFF *tif; |
| { |
| LZWState *sp = (LZWState *)tif->tif_data; |
| |
| if (sp->lzw_oldcode != -1) { |
| PutNextCode(tif, sp->lzw_oldcode); |
| sp->lzw_oldcode = -1; |
| } |
| PutNextCode(tif, CODE_EOI); |
| return (1); |
| } |
| |
| static void |
| PutNextCode(tif, c) |
| TIFF *tif; |
| int c; |
| { |
| register LZWState *sp = (LZWState *)tif->tif_data; |
| register long r_off; |
| register int bits, code = c; |
| register char *bp; |
| |
| r_off = sp->lzw_bitoff; |
| bits = sp->lzw_nbits; |
| /* |
| * Flush buffer if code doesn't fit. |
| */ |
| if (r_off + bits > sp->lzw_bitsize) { |
| /* |
| * Calculate the number of full bytes that can be |
| * written and save anything else for the next write. |
| */ |
| if (r_off & 7) { |
| tif->tif_rawcc = r_off >> 3; |
| bp = tif->tif_rawdata + tif->tif_rawcc; |
| (void) TIFFFlushData1(tif); |
| tif->tif_rawdata[0] = *bp; |
| } else { |
| /* |
| * Otherwise, on a byte boundary (in |
| * which tiff_rawcc is already correct). |
| */ |
| (void) TIFFFlushData1(tif); |
| } |
| bp = tif->tif_rawdata; |
| sp->lzw_bitoff = (r_off &= 7); |
| } else { |
| /* |
| * Get to the first byte. |
| */ |
| bp = tif->tif_rawdata + (r_off >> 3); |
| r_off &= 7; |
| } |
| /* |
| * Note that lzw_bitoff is maintained as the bit offset |
| * into the buffer w/ a right-to-left orientation (i.e. |
| * lsb-to-msb). The bits, however, go in the file in |
| * an msb-to-lsb order. |
| */ |
| bits -= (8 - r_off); |
| *bp = (*bp & lmask[r_off]) | (code >> bits); |
| bp++; |
| if (bits >= 8) { |
| bits -= 8; |
| *bp++ = code >> bits; |
| } |
| if (bits) |
| *bp = (code & rmask[bits]) << (8 - bits); |
| /* |
| * enc_outcount is used by the compression analysis machinery |
| * which resets the compression tables when the compression |
| * ratio goes up. lzw_bitoff is used here (in PutNextCode) for |
| * inserting codes into the output buffer. tif_rawcc must |
| * be updated for the mainline write code in TIFFWriteScanline() |
| * so that data is flushed when the end of a strip is reached. |
| * Note that the latter is rounded up to ensure that a non-zero |
| * byte count is present. |
| */ |
| sp->enc_outcount += sp->lzw_nbits; |
| sp->lzw_bitoff += sp->lzw_nbits; |
| tif->tif_rawcc = (sp->lzw_bitoff + 7) >> 3; |
| } |
| |
| /* |
| * Check compression ratio and, if things seem to |
| * be slipping, clear the hash table and reset state. |
| */ |
| static void |
| cl_block(tif) |
| TIFF *tif; |
| { |
| register LZWState *sp = (LZWState *)tif->tif_data; |
| register long rat; |
| |
| sp->enc_checkpoint = sp->enc_incount + CHECK_GAP; |
| if (sp->enc_incount > 0x007fffff) { /* shift will overflow */ |
| rat = sp->enc_outcount >> 8; |
| rat = (rat == 0 ? 0x7fffffff : sp->enc_incount / rat); |
| } else |
| rat = (sp->enc_incount<<8)/sp->enc_outcount; /* 8 fract bits */ |
| if (rat <= sp->enc_ratio) { |
| cl_hash(sp); |
| PutNextCode(tif, CODE_CLEAR); |
| SetMaxCode(sp, MAXCODE(sp->lzw_nbits = BITS_MIN)+1); |
| } else |
| sp->enc_ratio = rat; |
| } |
| |
| /* |
| * Reset code table and related statistics. |
| */ |
| static void |
| cl_hash(sp) |
| LZWState *sp; |
| { |
| register long *htab_p = sp->enc_htab+HSIZE; |
| register long i, m1 = -1; |
| |
| i = HSIZE - 16; |
| do { |
| *(htab_p-16) = m1; |
| *(htab_p-15) = m1; |
| *(htab_p-14) = m1; |
| *(htab_p-13) = m1; |
| *(htab_p-12) = m1; |
| *(htab_p-11) = m1; |
| *(htab_p-10) = m1; |
| *(htab_p-9) = m1; |
| *(htab_p-8) = m1; |
| *(htab_p-7) = m1; |
| *(htab_p-6) = m1; |
| *(htab_p-5) = m1; |
| *(htab_p-4) = m1; |
| *(htab_p-3) = m1; |
| *(htab_p-2) = m1; |
| *(htab_p-1) = m1; |
| htab_p -= 16; |
| } while ((i -= 16) >= 0); |
| for (i += 16; i > 0; i--) |
| *--htab_p = m1; |
| |
| sp->enc_ratio = 0; |
| sp->enc_incount = 0; |
| sp->enc_outcount = 0; |
| sp->lzw_free_ent = CODE_FIRST; |
| } |
| |
| static |
| LZWCleanup(tif) |
| TIFF *tif; |
| { |
| if (tif->tif_data) { |
| free(tif->tif_data); |
| tif->tif_data = NULL; |
| } |
| } |
| |
| /* |
| * Copyright (c) 1985, 1986 The Regents of the University of California. |
| * All rights reserved. |
| * |
| * This code is derived from software contributed to Berkeley by |
| * James A. Woods, derived from original work by Spencer Thomas |
| * and Joseph Orost. |
| * |
| * Redistribution and use in source and binary forms are permitted |
| * provided that the above copyright notice and this paragraph are |
| * duplicated in all such forms and that any documentation, |
| * advertising materials, and other materials related to such |
| * distribution and use acknowledge that the software was developed |
| * by the University of California, Berkeley. The name of the |
| * University may not be used to endorse or promote products derived |
| * from this software without specific prior written permission. |
| * THIS SOFTWARE IS PROVIDED ``AS IS'' AND WITHOUT ANY EXPRESS OR |
| * IMPLIED WARRANTIES, INCLUDING, WITHOUT LIMITATION, THE IMPLIED |
| * WARRANTIES OF MERCHANTIBILITY AND FITNESS FOR A PARTICULAR PURPOSE. |
| */ |