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