Java example source code file (LZWStringTable.java)

This example Java source code file (LZWStringTable.java) is included in the alvinalexander.com "Java Source Code Warehouse" project. The intent of this project is to help you "Learn Java by Example" ^TM.

Learn more about this Java project at its project page.

Java - Java tags/keywords

done, hash_free, hashsize, hashstep, lzwstringtable, maxbits, maxstr, next_first, res_codes, rob

The LZWStringTable.java Java example source code

/*
 * 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 added by Robin Luiten
 * The strLen table to give quick access to the lenght of an expanded
 * code for use by the <code>expandCode 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]));
        }
    }
}