/*
* @(#)LZWStringTable.java 1.2 05/11/17
*
* Copyright 2006 Sun Microsystems, Inc. All rights reserved.
* SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
*/
package com.sun.imageio.plugins.common;
import java.io.PrintStream;
/**
* General purpose LZW String Table.
* Extracted from GIFEncoder by Adam Doppelt
* Comments added by Robin Luiten
* <code>expandCode</code> added by Robin Luiten
* The strLen table to give quick access to the lenght of an expanded
* code for use by the <code>expandCode</code> method added by Robin.
**/
public class LZWStringTable {
/** codesize + Reserved Codes */
private final static int RES_CODES = 2;
private final static short HASH_FREE = (short)0xFFFF;
private final static short NEXT_FIRST = (short)0xFFFF;
private final static int MAXBITS = 12;
private final static int MAXSTR = (1 << MAXBITS);
private final static short HASHSIZE = 9973;
private final static short HASHSTEP = 2039;
byte[] strChr; // after predecessor character
short[] strNxt; // predecessor string
short[] strHsh; // hash table to find predecessor + char pairs
short numStrings; // next code if adding new prestring + char
/*
* each entry corresponds to a code and contains the length of data
* that the code expands to when decoded.
*/
int[] strLen;
/*
* Constructor allocate memory for string store data
*/
public LZWStringTable() {
strChr = new byte[MAXSTR];
strNxt = new short[MAXSTR];
strLen = new int[MAXSTR];
strHsh = new short[HASHSIZE];
}
/*
* @param index value of -1 indicates no predecessor [used in initialisation]
* @param b the byte [character] to add to the string store which follows
* the predecessor string specified the index.
* @return 0xFFFF if no space in table left for addition of predecesor
* index and byte b. Else return the code allocated for combination index + b.
*/
public int addCharString(short index, byte b) {
int hshidx;
if (numStrings >= MAXSTR) { // if used up all codes
return 0xFFFF;
}
hshidx = hash(index, b);
while (strHsh[hshidx] != HASH_FREE) {
hshidx = (hshidx + HASHSTEP) % HASHSIZE;
}
strHsh[hshidx] = numStrings;
strChr[numStrings] = b;
if (index == HASH_FREE) {
strNxt[numStrings] = NEXT_FIRST;
strLen[numStrings] = 1;
} else {
strNxt[numStrings] = index;
strLen[numStrings] = strLen[index] + 1;
}
return numStrings++; // return the code and inc for next code
}
/*
* @param index index to prefix string
* @param b the character that follws the index prefix
* @return b if param index is HASH_FREE. Else return the code
* for this prefix and byte successor
*/
public short findCharString(short index, byte b) {
int hshidx, nxtidx;
if (index == HASH_FREE) {
return (short)(b & 0xFF); // Rob fixed used to sign extend
}
hshidx = hash(index, b);
while ((nxtidx = strHsh[hshidx]) != HASH_FREE) { // search
if (strNxt[nxtidx] == index && strChr[nxtidx] == b) {
return (short)nxtidx;
}
hshidx = (hshidx + HASHSTEP) % HASHSIZE;
}
return (short)0xFFFF;
}
/*
* @param codesize the size of code to be preallocated for the
* string store.
*/
public void clearTable(int codesize) {
numStrings = 0;
for (int q = 0; q < HASHSIZE; q++) {
strHsh[q] = HASH_FREE;
}
int w = (1 << codesize) + RES_CODES;
for (int q = 0; q < w; q++) {
addCharString((short)0xFFFF, (byte)q); // init with no prefix
}
}
static public int hash(short index, byte lastbyte) {
return ((int)((short)(lastbyte << 8) ^ index) & 0xFFFF) % HASHSIZE;
}
/*
* If expanded data doesn't fit into array only what will fit is written
* to buf and the return value indicates how much of the expanded code has
* been written to the buf. The next call to expandCode() should be with
* the same code and have the skip parameter set the negated value of the
* previous return. Succesive negative return values should be negated and
* added together for next skip parameter value with same code.
*
* @param buf buffer to place expanded data into
* @param offset offset to place expanded data
* @param code the code to expand to the byte array it represents.
* PRECONDITION This code must already be in the LZSS
* @param skipHead is the number of bytes at the start of the expanded code to
* be skipped before data is written to buf. It is possible that skipHead is
* equal to codeLen.
* @return the length of data expanded into buf. If the expanded code is longer
* than space left in buf then the value returned is a negative number which when
* negated is equal to the number of bytes that were used of the code being expanded.
* This negative value also indicates the buffer is full.
*/
public int expandCode(byte[] buf, int offset, short code, int skipHead) {
if (offset == -2) {
if (skipHead == 1) {
skipHead = 0;
}
}
if (code == (short)0xFFFF || // just in case
skipHead == strLen[code]) // DONE no more unpacked
{
return 0;
}
int expandLen; // how much data we are actually expanding
int codeLen = strLen[code] - skipHead; // length of expanded code left
int bufSpace = buf.length - offset; // how much space left
if (bufSpace > codeLen) {
expandLen = codeLen; // only got this many to unpack
} else {
expandLen = bufSpace;
}
int skipTail = codeLen - expandLen; // only > 0 if codeLen > bufSpace [left overs]
int idx = offset + expandLen; // initialise to exclusive end address of buffer area
// NOTE: data unpacks in reverse direction and we are placing the
// unpacked data directly into the array in the correct location.
while ((idx > offset) && (code != (short)0xFFFF)) {
if (--skipTail < 0) { // skip required of expanded data
buf[--idx] = strChr[code];
}
code = strNxt[code]; // to predecessor code
}
if (codeLen > expandLen) {
return -expandLen; // indicate what part of codeLen used
} else {
return expandLen; // indicate length of dat unpacked
}
}
public void dump(PrintStream out) {
int i;
for (i = 258; i < numStrings; ++i) {
out.println(" strNxt[" + i + "] = " + strNxt[i]
+ " strChr " + Integer.toHexString(strChr[i] & 0xFF)
+ " strLen " + Integer.toHexString(strLen[i]));
}
}
}
|
