Back to index...

	/*
	* Copyright (c) 2005, Oracle and/or its affiliates. All rights reserved.
	* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
	*
	* This code is free software; you can redistribute it and/or modify it
	* under the terms of the GNU General Public License version 2 only, as
	* published by the Free Software Foundation. Oracle designates this
	* particular file as subject to the "Classpath" exception as provided
	* by Oracle in the LICENSE file that accompanied this code.
	*
	* This code is distributed in the hope that it will be useful, but WITHOUT
	* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
	* FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
	* version 2 for more details (a copy is included in the LICENSE file that
	* accompanied this code).
	*
	* You should have received a copy of the GNU General Public License version
	* 2 along with this work; if not, write to the Free Software Foundation,
	* Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
	*
	* Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
	* or visit www.oracle.com if you need additional information or have any
	* questions.
	*/

	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]));
	}
	}
	}

Back to index...