diff options
Diffstat (limited to 'tiff/libtiff/tif_lzw.c')
| -rw-r--r-- | tiff/libtiff/tif_lzw.c | 1129 |
1 files changed, 0 insertions, 1129 deletions
diff --git a/tiff/libtiff/tif_lzw.c b/tiff/libtiff/tif_lzw.c deleted file mode 100644 index d423866..0000000 --- a/tiff/libtiff/tif_lzw.c +++ /dev/null @@ -1,1129 +0,0 @@ -/* $Id: tif_lzw.c,v 1.29.2.6 2010-06-08 18:50:42 bfriesen Exp $ */ - -/* - * Copyright (c) 1988-1997 Sam Leffler - * Copyright (c) 1991-1997 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. - */ - -#include "tiffiop.h" -#ifdef LZW_SUPPORT -/* - * 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 "tif_predict.h" - -#include <stdio.h> - -/* - * 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 LZW_COMPAT /* include backwards compatibility code */ -/* - * Each strip of data is supposed to be terminated by a CODE_EOI. - * If the following #define is included, the decoder will also - * check for end-of-strip w/o seeing this code. This makes the - * library more robust, but also slower. - */ -#define LZW_CHECKEOS /* include checks for strips w/o EOI code */ - -#define MAXCODE(n) ((1L<<(n))-1) -/* - * The TIFF spec specifies that encoded bit - * strings range from 9 to 12 bits. - */ -#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) -#define HSIZE 9001L /* 91% occupancy */ -#define HSHIFT (13-8) -#ifdef LZW_COMPAT -/* NB: +1024 is for compatibility with old files */ -#define CSIZE (MAXCODE(BITS_MAX)+1024L) -#else -#define CSIZE (MAXCODE(BITS_MAX)+1L) -#endif - -/* - * State block for each open TIFF file using LZW - * compression/decompression. Note that the predictor - * state block must be first in this data structure. - */ -typedef struct { - TIFFPredictorState predict; /* predictor super class */ - - unsigned short nbits; /* # of bits/code */ - unsigned short maxcode; /* maximum code for lzw_nbits */ - unsigned short free_ent; /* next free entry in hash table */ - long nextdata; /* next bits of i/o */ - long nextbits; /* # of valid bits in lzw_nextdata */ - - int rw_mode; /* preserve rw_mode from init */ -} LZWBaseState; - -#define lzw_nbits base.nbits -#define lzw_maxcode base.maxcode -#define lzw_free_ent base.free_ent -#define lzw_nextdata base.nextdata -#define lzw_nextbits base.nextbits - -/* - * Encoding-specific state. - */ -typedef uint16 hcode_t; /* codes fit in 16 bits */ -typedef struct { - long hash; - hcode_t code; -} hash_t; - -/* - * Decoding-specific state. - */ -typedef struct code_ent { - struct code_ent *next; - unsigned short length; /* string len, including this token */ - unsigned char value; /* data value */ - unsigned char firstchar; /* first token of string */ -} code_t; - -typedef int (*decodeFunc)(TIFF*, tidata_t, tsize_t, tsample_t); - -typedef struct { - LZWBaseState base; - - /* Decoding specific data */ - long dec_nbitsmask; /* lzw_nbits 1 bits, right adjusted */ - long dec_restart; /* restart count */ -#ifdef LZW_CHECKEOS - long dec_bitsleft; /* available bits in raw data */ -#endif - decodeFunc dec_decode; /* regular or backwards compatible */ - code_t* dec_codep; /* current recognized code */ - code_t* dec_oldcodep; /* previously recognized code */ - code_t* dec_free_entp; /* next free entry */ - code_t* dec_maxcodep; /* max available entry */ - code_t* dec_codetab; /* kept separate for small machines */ - - /* Encoding specific data */ - int enc_oldcode; /* last code encountered */ - long enc_checkpoint; /* point at which to clear table */ -#define CHECK_GAP 10000 /* enc_ratio check interval */ - long enc_ratio; /* current compression ratio */ - long enc_incount; /* (input) data bytes encoded */ - long enc_outcount; /* encoded (output) bytes */ - tidata_t enc_rawlimit; /* bound on tif_rawdata buffer */ - hash_t* enc_hashtab; /* kept separate for small machines */ -} LZWCodecState; - -#define LZWState(tif) ((LZWBaseState*) (tif)->tif_data) -#define DecoderState(tif) ((LZWCodecState*) LZWState(tif)) -#define EncoderState(tif) ((LZWCodecState*) LZWState(tif)) - -static int LZWDecode(TIFF*, tidata_t, tsize_t, tsample_t); -#ifdef LZW_COMPAT -static int LZWDecodeCompat(TIFF*, tidata_t, tsize_t, tsample_t); -#endif -static void cl_hash(LZWCodecState*); - -/* - * LZW Decoder. - */ - -#ifdef LZW_CHECKEOS -/* - * This check shouldn't be necessary because each - * strip is suppose to be terminated with CODE_EOI. - */ -#define NextCode(_tif, _sp, _bp, _code, _get) { \ - if ((_sp)->dec_bitsleft < nbits) { \ - TIFFWarningExt(_tif->tif_clientdata, _tif->tif_name, \ - "LZWDecode: Strip %d not terminated with EOI code", \ - _tif->tif_curstrip); \ - _code = CODE_EOI; \ - } else { \ - _get(_sp,_bp,_code); \ - (_sp)->dec_bitsleft -= nbits; \ - } \ -} -#else -#define NextCode(tif, sp, bp, code, get) get(sp, bp, code) -#endif - -static int -LZWSetupDecode(TIFF* tif) -{ - LZWCodecState* sp = DecoderState(tif); - static const char module[] = " LZWSetupDecode"; - int code; - - if( sp == NULL ) - { - /* - * Allocate state block so tag methods have storage to record - * values. - */ - tif->tif_data = (tidata_t) _TIFFmalloc(sizeof(LZWCodecState)); - if (tif->tif_data == NULL) - { - TIFFErrorExt(tif->tif_clientdata, "LZWPreDecode", "No space for LZW state block"); - return (0); - } - - DecoderState(tif)->dec_codetab = NULL; - DecoderState(tif)->dec_decode = NULL; - - /* - * Setup predictor setup. - */ - (void) TIFFPredictorInit(tif); - - sp = DecoderState(tif); - } - - assert(sp != NULL); - - if (sp->dec_codetab == NULL) { - sp->dec_codetab = (code_t*)_TIFFmalloc(CSIZE*sizeof (code_t)); - if (sp->dec_codetab == NULL) { - TIFFErrorExt(tif->tif_clientdata, module, - "No space for LZW code table"); - return (0); - } - /* - * Pre-load the table. - */ - code = 255; - do { - sp->dec_codetab[code].value = code; - sp->dec_codetab[code].firstchar = code; - sp->dec_codetab[code].length = 1; - sp->dec_codetab[code].next = NULL; - } while (code--); - /* - * Zero-out the unused entries - */ - _TIFFmemset(&sp->dec_codetab[CODE_CLEAR], 0, - (CODE_FIRST - CODE_CLEAR) * sizeof (code_t)); - } - return (1); -} - -/* - * Setup state for decoding a strip. - */ -static int -LZWPreDecode(TIFF* tif, tsample_t s) -{ - LZWCodecState *sp = DecoderState(tif); - - (void) s; - assert(sp != NULL); - if( sp->dec_codetab == NULL ) - { - tif->tif_setupdecode( tif ); - } - - /* - * Check for old bit-reversed codes. - */ - if (tif->tif_rawdata[0] == 0 && (tif->tif_rawdata[1] & 0x1)) { -#ifdef LZW_COMPAT - if (!sp->dec_decode) { - TIFFWarningExt(tif->tif_clientdata, tif->tif_name, - "Old-style LZW codes, convert file"); - /* - * Override default decoding methods with - * ones that deal with the old coding. - * Otherwise the predictor versions set - * above will call the compatibility routines - * through the dec_decode method. - */ - tif->tif_decoderow = LZWDecodeCompat; - tif->tif_decodestrip = LZWDecodeCompat; - tif->tif_decodetile = LZWDecodeCompat; - /* - * If doing horizontal differencing, must - * re-setup the predictor logic since we - * switched the basic decoder methods... - */ - (*tif->tif_setupdecode)(tif); - sp->dec_decode = LZWDecodeCompat; - } - sp->lzw_maxcode = MAXCODE(BITS_MIN); -#else /* !LZW_COMPAT */ - if (!sp->dec_decode) { - TIFFErrorExt(tif->tif_clientdata, tif->tif_name, - "Old-style LZW codes not supported"); - sp->dec_decode = LZWDecode; - } - return (0); -#endif/* !LZW_COMPAT */ - } else { - sp->lzw_maxcode = MAXCODE(BITS_MIN)-1; - sp->dec_decode = LZWDecode; - } - sp->lzw_nbits = BITS_MIN; - sp->lzw_nextbits = 0; - sp->lzw_nextdata = 0; - - sp->dec_restart = 0; - sp->dec_nbitsmask = MAXCODE(BITS_MIN); -#ifdef LZW_CHECKEOS - sp->dec_bitsleft = tif->tif_rawcc << 3; -#endif - sp->dec_free_entp = sp->dec_codetab + CODE_FIRST; - /* - * Zero entries that are not yet filled in. We do - * this to guard against bogus input data that causes - * us to index into undefined entries. If you can - * come up with a way to safely bounds-check input codes - * while decoding then you can remove this operation. - */ - _TIFFmemset(sp->dec_free_entp, 0, (CSIZE-CODE_FIRST)*sizeof (code_t)); - sp->dec_oldcodep = &sp->dec_codetab[-1]; - sp->dec_maxcodep = &sp->dec_codetab[sp->dec_nbitsmask-1]; - return (1); -} - -/* - * Decode a "hunk of data". - */ -#define GetNextCode(sp, bp, code) { \ - nextdata = (nextdata<<8) | *(bp)++; \ - nextbits += 8; \ - if (nextbits < nbits) { \ - nextdata = (nextdata<<8) | *(bp)++; \ - nextbits += 8; \ - } \ - code = (hcode_t)((nextdata >> (nextbits-nbits)) & nbitsmask); \ - nextbits -= nbits; \ -} - -static void -codeLoop(TIFF* tif) -{ - TIFFErrorExt(tif->tif_clientdata, tif->tif_name, - "LZWDecode: Bogus encoding, loop in the code table; scanline %d", - tif->tif_row); -} - -static int -LZWDecode(TIFF* tif, tidata_t op0, tsize_t occ0, tsample_t s) -{ - LZWCodecState *sp = DecoderState(tif); - char *op = (char*) op0; - long occ = (long) occ0; - char *tp; - unsigned char *bp; - hcode_t code; - int len; - long nbits, nextbits, nextdata, nbitsmask; - code_t *codep, *free_entp, *maxcodep, *oldcodep; - - (void) s; - assert(sp != NULL); - assert(sp->dec_codetab != NULL); - /* - * Restart interrupted output operation. - */ - if (sp->dec_restart) { - long residue; - - codep = sp->dec_codep; - residue = codep->length - sp->dec_restart; - if (residue > occ) { - /* - * Residue from previous decode is sufficient - * to satisfy decode request. Skip to the - * start of the decoded string, place decoded - * values in the output buffer, and return. - */ - sp->dec_restart += occ; - do { - codep = codep->next; - } while (--residue > occ && codep); - if (codep) { - tp = op + occ; - do { - *--tp = codep->value; - codep = codep->next; - } while (--occ && codep); - } - return (1); - } - /* - * Residue satisfies only part of the decode request. - */ - op += residue, occ -= residue; - tp = op; - do { - int t; - --tp; - t = codep->value; - codep = codep->next; - *tp = t; - } while (--residue && codep); - sp->dec_restart = 0; - } - - bp = (unsigned char *)tif->tif_rawcp; - nbits = sp->lzw_nbits; - nextdata = sp->lzw_nextdata; - nextbits = sp->lzw_nextbits; - nbitsmask = sp->dec_nbitsmask; - oldcodep = sp->dec_oldcodep; - free_entp = sp->dec_free_entp; - maxcodep = sp->dec_maxcodep; - - while (occ > 0) { - NextCode(tif, sp, bp, code, GetNextCode); - if (code == CODE_EOI) - break; - if (code == CODE_CLEAR) { - free_entp = sp->dec_codetab + CODE_FIRST; - _TIFFmemset(free_entp, 0, - (CSIZE - CODE_FIRST) * sizeof (code_t)); - nbits = BITS_MIN; - nbitsmask = MAXCODE(BITS_MIN); - maxcodep = sp->dec_codetab + nbitsmask-1; - NextCode(tif, sp, bp, code, GetNextCode); - if (code == CODE_EOI) - break; - if (code == CODE_CLEAR) { - TIFFErrorExt(tif->tif_clientdata, tif->tif_name, - "LZWDecode: Corrupted LZW table at scanline %d", - tif->tif_row); - return (0); - } - *op++ = (char)code, occ--; - oldcodep = sp->dec_codetab + code; - continue; - } - codep = sp->dec_codetab + code; - - /* - * Add the new entry to the code table. - */ - if (free_entp < &sp->dec_codetab[0] || - free_entp >= &sp->dec_codetab[CSIZE]) { - TIFFErrorExt(tif->tif_clientdata, tif->tif_name, - "LZWDecode: Corrupted LZW table at scanline %d", - tif->tif_row); - return (0); - } - - free_entp->next = oldcodep; - if (free_entp->next < &sp->dec_codetab[0] || - free_entp->next >= &sp->dec_codetab[CSIZE]) { - TIFFErrorExt(tif->tif_clientdata, tif->tif_name, - "LZWDecode: Corrupted LZW table at scanline %d", - tif->tif_row); - return (0); - } - free_entp->firstchar = free_entp->next->firstchar; - free_entp->length = free_entp->next->length+1; - free_entp->value = (codep < free_entp) ? - codep->firstchar : free_entp->firstchar; - if (++free_entp > maxcodep) { - if (++nbits > BITS_MAX) /* should not happen */ - nbits = BITS_MAX; - nbitsmask = MAXCODE(nbits); - maxcodep = sp->dec_codetab + nbitsmask-1; - } - oldcodep = codep; - if (code >= 256) { - /* - * Code maps to a string, copy string - * value to output (written in reverse). - */ - if(codep->length == 0) { - TIFFErrorExt(tif->tif_clientdata, tif->tif_name, - "LZWDecode: Wrong length of decoded string: " - "data probably corrupted at scanline %d", - tif->tif_row); - return (0); - } - if (codep->length > occ) { - /* - * String is too long for decode buffer, - * locate portion that will fit, copy to - * the decode buffer, and setup restart - * logic for the next decoding call. - */ - sp->dec_codep = codep; - do { - codep = codep->next; - } while (codep && codep->length > occ); - if (codep) { - sp->dec_restart = occ; - tp = op + occ; - do { - *--tp = codep->value; - codep = codep->next; - } while (--occ && codep); - if (codep) - codeLoop(tif); - } - break; - } - len = codep->length; - tp = op + len; - do { - int t; - --tp; - t = codep->value; - codep = codep->next; - *tp = t; - } while (codep && tp > op); - if (codep) { - codeLoop(tif); - break; - } - op += len, occ -= len; - } else - *op++ = (char)code, occ--; - } - - tif->tif_rawcp = (tidata_t) bp; - sp->lzw_nbits = (unsigned short) nbits; - sp->lzw_nextdata = nextdata; - sp->lzw_nextbits = nextbits; - sp->dec_nbitsmask = nbitsmask; - sp->dec_oldcodep = oldcodep; - sp->dec_free_entp = free_entp; - sp->dec_maxcodep = maxcodep; - - if (occ > 0) { - TIFFErrorExt(tif->tif_clientdata, tif->tif_name, - "LZWDecode: Not enough data at scanline %d (short %ld bytes)", - tif->tif_row, occ); - return (0); - } - return (1); -} - -#ifdef LZW_COMPAT -/* - * Decode a "hunk of data" for old images. - */ -#define GetNextCodeCompat(sp, bp, code) { \ - nextdata |= (unsigned long) *(bp)++ << nextbits; \ - nextbits += 8; \ - if (nextbits < nbits) { \ - nextdata |= (unsigned long) *(bp)++ << nextbits;\ - nextbits += 8; \ - } \ - code = (hcode_t)(nextdata & nbitsmask); \ - nextdata >>= nbits; \ - nextbits -= nbits; \ -} - -static int -LZWDecodeCompat(TIFF* tif, tidata_t op0, tsize_t occ0, tsample_t s) -{ - LZWCodecState *sp = DecoderState(tif); - char *op = (char*) op0; - long occ = (long) occ0; - char *tp; - unsigned char *bp; - int code, nbits; - long nextbits, nextdata, nbitsmask; - code_t *codep, *free_entp, *maxcodep, *oldcodep; - - (void) s; - assert(sp != NULL); - /* - * Restart interrupted output operation. - */ - if (sp->dec_restart) { - long residue; - - codep = sp->dec_codep; - residue = codep->length - sp->dec_restart; - if (residue > occ) { - /* - * Residue from previous decode is sufficient - * to satisfy decode request. Skip to the - * start of the decoded string, place decoded - * values in the output buffer, and return. - */ - sp->dec_restart += occ; - do { - codep = codep->next; - } while (--residue > occ); - tp = op + occ; - do { - *--tp = codep->value; - codep = codep->next; - } while (--occ); - return (1); - } - /* - * Residue satisfies only part of the decode request. - */ - op += residue, occ -= residue; - tp = op; - do { - *--tp = codep->value; - codep = codep->next; - } while (--residue); - sp->dec_restart = 0; - } - - bp = (unsigned char *)tif->tif_rawcp; - nbits = sp->lzw_nbits; - nextdata = sp->lzw_nextdata; - nextbits = sp->lzw_nextbits; - nbitsmask = sp->dec_nbitsmask; - oldcodep = sp->dec_oldcodep; - free_entp = sp->dec_free_entp; - maxcodep = sp->dec_maxcodep; - - while (occ > 0) { - NextCode(tif, sp, bp, code, GetNextCodeCompat); - if (code == CODE_EOI) - break; - if (code == CODE_CLEAR) { - free_entp = sp->dec_codetab + CODE_FIRST; - _TIFFmemset(free_entp, 0, - (CSIZE - CODE_FIRST) * sizeof (code_t)); - nbits = BITS_MIN; - nbitsmask = MAXCODE(BITS_MIN); - maxcodep = sp->dec_codetab + nbitsmask; - NextCode(tif, sp, bp, code, GetNextCodeCompat); - if (code == CODE_EOI) - break; - if (code == CODE_CLEAR) { - TIFFErrorExt(tif->tif_clientdata, tif->tif_name, - "LZWDecode: Corrupted LZW table at scanline %d", - tif->tif_row); - return (0); - } - *op++ = code, occ--; - oldcodep = sp->dec_codetab + code; - continue; - } - codep = sp->dec_codetab + code; - - /* - * Add the new entry to the code table. - */ - if (free_entp < &sp->dec_codetab[0] || - free_entp >= &sp->dec_codetab[CSIZE]) { - TIFFErrorExt(tif->tif_clientdata, tif->tif_name, - "LZWDecodeCompat: Corrupted LZW table at scanline %d", - tif->tif_row); - return (0); - } - - free_entp->next = oldcodep; - if (free_entp->next < &sp->dec_codetab[0] || - free_entp->next >= &sp->dec_codetab[CSIZE]) { - TIFFErrorExt(tif->tif_clientdata, tif->tif_name, - "LZWDecodeCompat: Corrupted LZW table at scanline %d", - tif->tif_row); - return (0); - } - free_entp->firstchar = free_entp->next->firstchar; - free_entp->length = free_entp->next->length+1; - free_entp->value = (codep < free_entp) ? - codep->firstchar : free_entp->firstchar; - if (++free_entp > maxcodep) { - if (++nbits > BITS_MAX) /* should not happen */ - nbits = BITS_MAX; - nbitsmask = MAXCODE(nbits); - maxcodep = sp->dec_codetab + nbitsmask; - } - oldcodep = codep; - if (code >= 256) { - char *op_orig = op; - /* - * Code maps to a string, copy string - * value to output (written in reverse). - */ - if(codep->length == 0) { - TIFFErrorExt(tif->tif_clientdata, tif->tif_name, - "LZWDecodeCompat: Wrong length of decoded " - "string: data probably corrupted at scanline %d", - tif->tif_row); - return (0); - } - if (codep->length > occ) { - /* - * String is too long for decode buffer, - * locate portion that will fit, copy to - * the decode buffer, and setup restart - * logic for the next decoding call. - */ - sp->dec_codep = codep; - do { - codep = codep->next; - } while (codep->length > occ); - sp->dec_restart = occ; - tp = op + occ; - do { - *--tp = codep->value; - codep = codep->next; - } while (--occ); - break; - } - op += codep->length, occ -= codep->length; - tp = op; - do { - *--tp = codep->value; - } while( (codep = codep->next) != NULL && tp > op_orig); - } else - *op++ = code, occ--; - } - - tif->tif_rawcp = (tidata_t) bp; - sp->lzw_nbits = nbits; - sp->lzw_nextdata = nextdata; - sp->lzw_nextbits = nextbits; - sp->dec_nbitsmask = nbitsmask; - sp->dec_oldcodep = oldcodep; - sp->dec_free_entp = free_entp; - sp->dec_maxcodep = maxcodep; - - if (occ > 0) { - TIFFErrorExt(tif->tif_clientdata, tif->tif_name, - "LZWDecodeCompat: Not enough data at scanline %d (short %ld bytes)", - tif->tif_row, occ); - return (0); - } - return (1); -} -#endif /* LZW_COMPAT */ - -/* - * LZW Encoding. - */ - -static int -LZWSetupEncode(TIFF* tif) -{ - LZWCodecState* sp = EncoderState(tif); - static const char module[] = "LZWSetupEncode"; - - assert(sp != NULL); - sp->enc_hashtab = (hash_t*) _TIFFmalloc(HSIZE*sizeof (hash_t)); - if (sp->enc_hashtab == NULL) { - TIFFErrorExt(tif->tif_clientdata, module, "No space for LZW hash table"); - return (0); - } - return (1); -} - -/* - * Reset encoding state at the start of a strip. - */ -static int -LZWPreEncode(TIFF* tif, tsample_t s) -{ - LZWCodecState *sp = EncoderState(tif); - - (void) s; - assert(sp != NULL); - - if( sp->enc_hashtab == NULL ) - { - tif->tif_setupencode( tif ); - } - - sp->lzw_nbits = BITS_MIN; - sp->lzw_maxcode = MAXCODE(BITS_MIN); - sp->lzw_free_ent = CODE_FIRST; - sp->lzw_nextbits = 0; - sp->lzw_nextdata = 0; - sp->enc_checkpoint = CHECK_GAP; - sp->enc_ratio = 0; - sp->enc_incount = 0; - sp->enc_outcount = 0; - /* - * The 4 here insures there is space for 2 max-sized - * codes in LZWEncode and LZWPostDecode. - */ - sp->enc_rawlimit = tif->tif_rawdata + tif->tif_rawdatasize-1 - 4; - cl_hash(sp); /* clear hash table */ - sp->enc_oldcode = (hcode_t) -1; /* generates CODE_CLEAR in LZWEncode */ - return (1); -} - -#define CALCRATIO(sp, rat) { \ - if (incount > 0x007fffff) { /* NB: shift will overflow */\ - rat = outcount >> 8; \ - rat = (rat == 0 ? 0x7fffffff : incount/rat); \ - } else \ - rat = (incount<<8) / outcount; \ -} -#define PutNextCode(op, c) { \ - nextdata = (nextdata << nbits) | c; \ - nextbits += nbits; \ - *op++ = (unsigned char)(nextdata >> (nextbits-8)); \ - nextbits -= 8; \ - if (nextbits >= 8) { \ - *op++ = (unsigned char)(nextdata >> (nextbits-8)); \ - nextbits -= 8; \ - } \ - outcount += nbits; \ -} - -/* - * Encode a chunk 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 int -LZWEncode(TIFF* tif, tidata_t bp, tsize_t cc, tsample_t s) -{ - register LZWCodecState *sp = EncoderState(tif); - register long fcode; - register hash_t *hp; - register int h, c; - hcode_t ent; - long disp; - long incount, outcount, checkpoint; - long nextdata, nextbits; - int free_ent, maxcode, nbits; - tidata_t op, limit; - - (void) s; - if (sp == NULL) - return (0); - - assert(sp->enc_hashtab != NULL); - - /* - * Load local state. - */ - incount = sp->enc_incount; - outcount = sp->enc_outcount; - checkpoint = sp->enc_checkpoint; - nextdata = sp->lzw_nextdata; - nextbits = sp->lzw_nextbits; - free_ent = sp->lzw_free_ent; - maxcode = sp->lzw_maxcode; - nbits = sp->lzw_nbits; - op = tif->tif_rawcp; - limit = sp->enc_rawlimit; - ent = sp->enc_oldcode; - - if (ent == (hcode_t) -1 && cc > 0) { - /* - * NB: This is safe because it can only happen - * at the start of a strip where we know there - * is space in the data buffer. - */ - PutNextCode(op, CODE_CLEAR); - ent = *bp++; cc--; incount++; - } - while (cc > 0) { - c = *bp++; cc--; incount++; - fcode = ((long)c << BITS_MAX) + ent; - h = (c << HSHIFT) ^ ent; /* xor hashing */ -#ifdef _WINDOWS - /* - * Check hash index for an overflow. - */ - if (h >= HSIZE) - h -= HSIZE; -#endif - hp = &sp->enc_hashtab[h]; - if (hp->hash == fcode) { - ent = hp->code; - continue; - } - if (hp->hash >= 0) { - /* - * Primary hash failed, check secondary hash. - */ - disp = HSIZE - h; - if (h == 0) - disp = 1; - do { - /* - * Avoid pointer arithmetic 'cuz of - * wraparound problems with segments. - */ - if ((h -= disp) < 0) - h += HSIZE; - hp = &sp->enc_hashtab[h]; - if (hp->hash == fcode) { - ent = hp->code; - goto hit; - } - } while (hp->hash >= 0); - } - /* - * New entry, emit code and add to table. - */ - /* - * Verify there is space in the buffer for the code - * and any potential Clear code that might be emitted - * below. The value of limit is setup so that there - * are at least 4 bytes free--room for 2 codes. - */ - if (op > limit) { - tif->tif_rawcc = (tsize_t)(op - tif->tif_rawdata); - TIFFFlushData1(tif); - op = tif->tif_rawdata; - } - PutNextCode(op, ent); - ent = c; - hp->code = free_ent++; - hp->hash = fcode; - if (free_ent == CODE_MAX-1) { - /* table is full, emit clear code and reset */ - cl_hash(sp); - sp->enc_ratio = 0; - incount = 0; - outcount = 0; - free_ent = CODE_FIRST; - PutNextCode(op, CODE_CLEAR); - nbits = BITS_MIN; - maxcode = MAXCODE(BITS_MIN); - } else { - /* - * If the next entry is going to be too big for - * the code size, then increase it, if possible. - */ - if (free_ent > maxcode) { - nbits++; - assert(nbits <= BITS_MAX); - maxcode = (int) MAXCODE(nbits); - } else if (incount >= checkpoint) { - long rat; - /* - * Check compression ratio and, if things seem - * to be slipping, clear the hash table and - * reset state. The compression ratio is a - * 24+8-bit fractional number. - */ - checkpoint = incount+CHECK_GAP; - CALCRATIO(sp, rat); - if (rat <= sp->enc_ratio) { - cl_hash(sp); - sp->enc_ratio = 0; - incount = 0; - outcount = 0; - free_ent = CODE_FIRST; - PutNextCode(op, CODE_CLEAR); - nbits = BITS_MIN; - maxcode = MAXCODE(BITS_MIN); - } else - sp->enc_ratio = rat; - } - } - hit: - ; - } - - /* - * Restore global state. - */ - sp->enc_incount = incount; - sp->enc_outcount = outcount; - sp->enc_checkpoint = checkpoint; - sp->enc_oldcode = ent; - sp->lzw_nextdata = nextdata; - sp->lzw_nextbits = nextbits; - sp->lzw_free_ent = free_ent; - sp->lzw_maxcode = maxcode; - sp->lzw_nbits = nbits; - tif->tif_rawcp = op; - return (1); -} - -/* - * Finish off an encoded strip by flushing the last - * string and tacking on an End Of Information code. - */ -static int -LZWPostEncode(TIFF* tif) -{ - register LZWCodecState *sp = EncoderState(tif); - tidata_t op = tif->tif_rawcp; - long nextbits = sp->lzw_nextbits; - long nextdata = sp->lzw_nextdata; - long outcount = sp->enc_outcount; - int nbits = sp->lzw_nbits; - - if (op > sp->enc_rawlimit) { - tif->tif_rawcc = (tsize_t)(op - tif->tif_rawdata); - TIFFFlushData1(tif); - op = tif->tif_rawdata; - } - if (sp->enc_oldcode != (hcode_t) -1) { - PutNextCode(op, sp->enc_oldcode); - sp->enc_oldcode = (hcode_t) -1; - } - PutNextCode(op, CODE_EOI); - if (nextbits > 0) - *op++ = (unsigned char)(nextdata << (8-nextbits)); - tif->tif_rawcc = (tsize_t)(op - tif->tif_rawdata); - return (1); -} - -/* - * Reset encoding hash table. - */ -static void -cl_hash(LZWCodecState* sp) -{ - register hash_t *hp = &sp->enc_hashtab[HSIZE-1]; - register long i = HSIZE-8; - - do { - i -= 8; - hp[-7].hash = -1; - hp[-6].hash = -1; - hp[-5].hash = -1; - hp[-4].hash = -1; - hp[-3].hash = -1; - hp[-2].hash = -1; - hp[-1].hash = -1; - hp[ 0].hash = -1; - hp -= 8; - } while (i >= 0); - for (i += 8; i > 0; i--, hp--) - hp->hash = -1; -} - -static void -LZWCleanup(TIFF* tif) -{ - (void)TIFFPredictorCleanup(tif); - - assert(tif->tif_data != 0); - - if (DecoderState(tif)->dec_codetab) - _TIFFfree(DecoderState(tif)->dec_codetab); - - if (EncoderState(tif)->enc_hashtab) - _TIFFfree(EncoderState(tif)->enc_hashtab); - - _TIFFfree(tif->tif_data); - tif->tif_data = NULL; - - _TIFFSetDefaultCompressionState(tif); -} - -int -TIFFInitLZW(TIFF* tif, int scheme) -{ - assert(scheme == COMPRESSION_LZW); - /* - * Allocate state block so tag methods have storage to record values. - */ - tif->tif_data = (tidata_t) _TIFFmalloc(sizeof (LZWCodecState)); - if (tif->tif_data == NULL) - goto bad; - DecoderState(tif)->dec_codetab = NULL; - DecoderState(tif)->dec_decode = NULL; - EncoderState(tif)->enc_hashtab = NULL; - LZWState(tif)->rw_mode = tif->tif_mode; - - /* - * Install codec methods. - */ - tif->tif_setupdecode = LZWSetupDecode; - tif->tif_predecode = LZWPreDecode; - tif->tif_decoderow = LZWDecode; - tif->tif_decodestrip = LZWDecode; - tif->tif_decodetile = LZWDecode; - tif->tif_setupencode = LZWSetupEncode; - tif->tif_preencode = LZWPreEncode; - tif->tif_postencode = LZWPostEncode; - tif->tif_encoderow = LZWEncode; - tif->tif_encodestrip = LZWEncode; - tif->tif_encodetile = LZWEncode; - tif->tif_cleanup = LZWCleanup; - /* - * Setup predictor setup. - */ - (void) TIFFPredictorInit(tif); - return (1); -bad: - TIFFErrorExt(tif->tif_clientdata, "TIFFInitLZW", - "No space for LZW state block"); - return (0); -} - -/* - * 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. - */ -#endif /* LZW_SUPPORT */ - -/* vim: set ts=8 sts=8 sw=8 noet: */ -/* - * Local Variables: - * mode: c - * c-basic-offset: 8 - * fill-column: 78 - * End: - */ |