001: /*
002: * $RCSfile: LZWStringTable.java,v $
003: *
004: *
005: * Copyright (c) 2005 Sun Microsystems, Inc. All Rights Reserved.
006: *
007: * Redistribution and use in source and binary forms, with or without
008: * modification, are permitted provided that the following conditions
009: * are met:
010: *
011: * - Redistribution of source code must retain the above copyright
012: * notice, this list of conditions and the following disclaimer.
013: *
014: * - Redistribution in binary form must reproduce the above copyright
015: * notice, this list of conditions and the following disclaimer in
016: * the documentation and/or other materials provided with the
017: * distribution.
018: *
019: * Neither the name of Sun Microsystems, Inc. or the names of
020: * contributors may be used to endorse or promote products derived
021: * from this software without specific prior written permission.
022: *
023: * This software is provided "AS IS," without a warranty of any
024: * kind. ALL EXPRESS OR IMPLIED CONDITIONS, REPRESENTATIONS AND
025: * WARRANTIES, INCLUDING ANY IMPLIED WARRANTY OF MERCHANTABILITY,
026: * FITNESS FOR A PARTICULAR PURPOSE OR NON-INFRINGEMENT, ARE HEREBY
027: * EXCLUDED. SUN MIDROSYSTEMS, INC. ("SUN") AND ITS LICENSORS SHALL
028: * NOT BE LIABLE FOR ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF
029: * USING, MODIFYING OR DISTRIBUTING THIS SOFTWARE OR ITS
030: * DERIVATIVES. IN NO EVENT WILL SUN OR ITS LICENSORS BE LIABLE FOR
031: * ANY LOST REVENUE, PROFIT OR DATA, OR FOR DIRECT, INDIRECT, SPECIAL,
032: * CONSEQUENTIAL, INCIDENTAL OR PUNITIVE DAMAGES, HOWEVER CAUSED AND
033: * REGARDLESS OF THE THEORY OF LIABILITY, ARISING OUT OF THE USE OF OR
034: * INABILITY TO USE THIS SOFTWARE, EVEN IF SUN HAS BEEN ADVISED OF THE
035: * POSSIBILITY OF SUCH DAMAGES.
036: *
037: * You acknowledge that this software is not designed or intended for
038: * use in the design, construction, operation or maintenance of any
039: * nuclear facility.
040: *
041: * $Revision: 1.1 $
042: * $Date: 2005/02/11 05:01:23 $
043: * $State: Exp $
044: */
045:
046: package com.sun.media.imageioimpl.common;
047:
048: import java.io.PrintStream;
049:
050: /**
051: * General purpose LZW String Table.
052: * Extracted from GIFEncoder by Adam Doppelt
053: * Comments added by Robin Luiten
054: * <code>expandCode</code> added by Robin Luiten
055: * The strLen_ table to give quick access to the lenght of an expanded
056: * code for use by the <code>expandCode</code> method added by Robin.
057: **/
058: public class LZWStringTable {
059: /** codesize + Reserved Codes */
060: private final static int RES_CODES = 2;
061:
062: private final static short HASH_FREE = (short) 0xFFFF;
063: private final static short NEXT_FIRST = (short) 0xFFFF;
064:
065: private final static int MAXBITS = 12;
066: private final static int MAXSTR = (1 << MAXBITS);
067:
068: private final static short HASHSIZE = 9973;
069: private final static short HASHSTEP = 2039;
070:
071: byte[] strChr_; // after predecessor character
072: short[] strNxt_; // predecessor string
073: short[] strHsh_; // hash table to find predecessor + char pairs
074: short numStrings_; // next code if adding new prestring + char
075:
076: /**
077: * each entry corresponds to a code and contains the length of data
078: * that the code expands to when decoded.
079: **/
080: int[] strLen_;
081:
082: /**
083: * Constructor allocate memory for string store data
084: **/
085: public LZWStringTable() {
086: strChr_ = new byte[MAXSTR];
087: strNxt_ = new short[MAXSTR];
088: strLen_ = new int[MAXSTR];
089: strHsh_ = new short[HASHSIZE];
090: }
091:
092: /**
093: * @param index value of -1 indicates no predecessor [used in initialisation]
094: * @param b the byte [character] to add to the string store which follows
095: * the predecessor string specified the index.
096: * @return 0xFFFF if no space in table left for addition of predecesor
097: * index and byte b. Else return the code allocated for combination index + b.
098: **/
099: public int AddCharString(short index, byte b) {
100: int hshidx;
101:
102: if (numStrings_ >= MAXSTR) // if used up all codes
103: {
104: return 0xFFFF;
105: }
106:
107: hshidx = Hash(index, b);
108: while (strHsh_[hshidx] != HASH_FREE)
109: hshidx = (hshidx + HASHSTEP) % HASHSIZE;
110:
111: strHsh_[hshidx] = numStrings_;
112: strChr_[numStrings_] = b;
113: if (index == HASH_FREE) {
114: strNxt_[numStrings_] = NEXT_FIRST;
115: strLen_[numStrings_] = 1;
116: } else {
117: strNxt_[numStrings_] = index;
118: strLen_[numStrings_] = strLen_[index] + 1;
119: }
120:
121: return numStrings_++; // return the code and inc for next code
122: }
123:
124: /**
125: * @param index index to prefix string
126: * @param b the character that follws the index prefix
127: * @return b if param index is HASH_FREE. Else return the code
128: * for this prefix and byte successor
129: **/
130: public short FindCharString(short index, byte b) {
131: int hshidx, nxtidx;
132:
133: if (index == HASH_FREE)
134: return (short) (b & 0xFF); // Rob fixed used to sign extend
135:
136: hshidx = Hash(index, b);
137: while ((nxtidx = strHsh_[hshidx]) != HASH_FREE) // search
138: {
139: if (strNxt_[nxtidx] == index && strChr_[nxtidx] == b)
140: return (short) nxtidx;
141: hshidx = (hshidx + HASHSTEP) % HASHSIZE;
142: }
143:
144: return (short) 0xFFFF;
145: }
146:
147: /**
148: * @param codesize the size of code to be preallocated for the
149: * string store.
150: **/
151: public void ClearTable(int codesize) {
152: numStrings_ = 0;
153:
154: for (int q = 0; q < HASHSIZE; q++)
155: strHsh_[q] = HASH_FREE;
156:
157: int w = (1 << codesize) + RES_CODES;
158: for (int q = 0; q < w; q++)
159: AddCharString((short) 0xFFFF, (byte) q); // init with no prefix
160: }
161:
162: static public int Hash(short index, byte lastbyte) {
163: return ((int) ((short) (lastbyte << 8) ^ index) & 0xFFFF)
164: % HASHSIZE;
165: }
166:
167: /**
168: * If expanded data doesnt fit into array only what will fit is written
169: * to buf and the return value indicates how much of the expanded code has
170: * been written to the buf. The next call to expandCode() should be with
171: * the same code and have the skip parameter set the negated value of the
172: * previous return. Succesive negative return values should be negated and
173: * added together for next skip parameter value with same code.
174: *
175: * @param buf buffer to place expanded data into
176: * @param offset offset to place expanded data
177: * @param code the code to expand to the byte array it represents.
178: * PRECONDITION This code must allready be in the LZSS
179: * @param skipHead is the number of bytes at the start of the expanded code to
180: * be skipped before data is written to buf. It is possible that skipHead is
181: * equal to codeLen.
182: * @return the length of data expanded into buf. If the expanded code is longer
183: * than space left in buf then the value returned is a negative number which when
184: * negated is equal to the number of bytes that were used of the code being expanded.
185: * This negative value also indicates the buffer is full.
186: **/
187: public int expandCode(byte[] buf, int offset, short code,
188: int skipHead) {
189: if (offset == -2) {
190: if (skipHead == 1)
191: skipHead = 0;
192: }
193: if (code == (short) 0xFFFF || // just in case
194: skipHead == strLen_[code]) // DONE no more unpacked
195: return 0;
196:
197: int expandLen; // how much data we are actually expanding
198: int codeLen = strLen_[code] - skipHead; // length of expanded code left
199: int bufSpace = buf.length - offset; // how much space left
200: if (bufSpace > codeLen)
201: expandLen = codeLen; // only got this many to unpack
202: else
203: expandLen = bufSpace;
204:
205: int skipTail = codeLen - expandLen; // only > 0 if codeLen > bufSpace [left overs]
206:
207: int idx = offset + expandLen; // initialise to exclusive end address of buffer area
208:
209: // NOTE: data unpacks in reverse direction and we are placing the
210: // unpacked data directly into the array in the correct location.
211: while ((idx > offset) && (code != (short) 0xFFFF)) {
212: if (--skipTail < 0) // skip required of expanded data
213: {
214: buf[--idx] = strChr_[code];
215: }
216: code = strNxt_[code]; // to predecessor code
217: }
218:
219: if (codeLen > expandLen)
220: return -expandLen; // indicate what part of codeLen used
221: else
222: return expandLen; // indicate length of dat unpacked
223: }
224:
225: public void dump(PrintStream out) {
226: int i;
227: for (i = 258; i < numStrings_; ++i)
228: out.println(" strNxt_[" + i + "] = " + strNxt_[i]
229: + " strChr_ "
230: + Integer.toHexString(strChr_[i] & 0xFF)
231: + " strLen_ " + Integer.toHexString(strLen_[i]));
232: }
233: }
|