KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > com > sun > imageio > plugins > common > LZWStringTable


1 /*
2  * @(#)LZWStringTable.java 1.2 05/11/17
3  *
4  * Copyright 2006 Sun Microsystems, Inc. All rights reserved.
5  * SUN PROPRIETARY/CONFIDENTIAL. Use is subject to license terms.
6  */
7
8 package com.sun.imageio.plugins.common;
9
10 import java.io.PrintStream JavaDoc;
11
12 /**
13  * General purpose LZW String Table.
14  * Extracted from GIFEncoder by Adam Doppelt
15  * Comments added by Robin Luiten
16  * <code>expandCode</code> added by Robin Luiten
17  * The strLen table to give quick access to the lenght of an expanded
18  * code for use by the <code>expandCode</code> method added by Robin.
19  **/
20 public class LZWStringTable {
21     /** codesize + Reserved Codes */
22     private final static int RES_CODES = 2;
23
24     private final static short HASH_FREE = (short)0xFFFF;
25     private final static short NEXT_FIRST = (short)0xFFFF;
26     
27     private final static int MAXBITS = 12;
28     private final static int MAXSTR = (1 << MAXBITS);
29     
30     private final static short HASHSIZE = 9973;
31     private final static short HASHSTEP = 2039;
32
33     byte[] strChr; // after predecessor character
34 short[] strNxt; // predecessor string
35 short[] strHsh; // hash table to find predecessor + char pairs
36 short numStrings; // next code if adding new prestring + char
37
38     /*
39      * each entry corresponds to a code and contains the length of data
40      * that the code expands to when decoded.
41      */
42     int[] strLen;
43
44     /*
45      * Constructor allocate memory for string store data
46      */
47     public LZWStringTable() {
48         strChr = new byte[MAXSTR];
49         strNxt = new short[MAXSTR];
50         strLen = new int[MAXSTR];
51         strHsh = new short[HASHSIZE];
52     }
53
54     /*
55      * @param index value of -1 indicates no predecessor [used in initialisation]
56      * @param b the byte [character] to add to the string store which follows
57      * the predecessor string specified the index.
58      * @return 0xFFFF if no space in table left for addition of predecesor
59      * index and byte b. Else return the code allocated for combination index + b.
60      */
61     public int addCharString(short index, byte b) {
62         int hshidx;
63         
64         if (numStrings >= MAXSTR) { // if used up all codes
65 return 0xFFFF;
66         }
67   
68         hshidx = hash(index, b);
69         while (strHsh[hshidx] != HASH_FREE) {
70             hshidx = (hshidx + HASHSTEP) % HASHSIZE;
71         }
72   
73         strHsh[hshidx] = numStrings;
74         strChr[numStrings] = b;
75         if (index == HASH_FREE) {
76             strNxt[numStrings] = NEXT_FIRST;
77             strLen[numStrings] = 1;
78         } else {
79             strNxt[numStrings] = index;
80             strLen[numStrings] = strLen[index] + 1;
81         }
82
83         return numStrings++; // return the code and inc for next code
84 }
85
86     /*
87      * @param index index to prefix string
88      * @param b the character that follws the index prefix
89      * @return b if param index is HASH_FREE. Else return the code
90      * for this prefix and byte successor
91      */
92     public short findCharString(short index, byte b) {
93         int hshidx, nxtidx;
94         
95         if (index == HASH_FREE) {
96             return (short)(b & 0xFF); // Rob fixed used to sign extend
97 }
98
99         hshidx = hash(index, b);
100         while ((nxtidx = strHsh[hshidx]) != HASH_FREE) { // search
101 if (strNxt[nxtidx] == index && strChr[nxtidx] == b) {
102                 return (short)nxtidx;
103             }
104             hshidx = (hshidx + HASHSTEP) % HASHSIZE;
105         }
106         
107         return (short)0xFFFF;
108     }
109
110     /*
111      * @param codesize the size of code to be preallocated for the
112      * string store.
113      */
114     public void clearTable(int codesize) {
115         numStrings = 0;
116         
117         for (int q = 0; q < HASHSIZE; q++) {
118             strHsh[q] = HASH_FREE;
119         }
120
121         int w = (1 << codesize) + RES_CODES;
122         for (int q = 0; q < w; q++) {
123             addCharString((short)0xFFFF, (byte)q); // init with no prefix
124 }
125     }
126
127     static public int hash(short index, byte lastbyte) {
128         return ((int)((short)(lastbyte << 8) ^ index) & 0xFFFF) % HASHSIZE;
129     }
130
131     /*
132      * If expanded data doesn't fit into array only what will fit is written
133      * to buf and the return value indicates how much of the expanded code has
134      * been written to the buf. The next call to expandCode() should be with
135      * the same code and have the skip parameter set the negated value of the
136      * previous return. Succesive negative return values should be negated and
137      * added together for next skip parameter value with same code.
138      *
139      * @param buf buffer to place expanded data into
140      * @param offset offset to place expanded data
141      * @param code the code to expand to the byte array it represents.
142      * PRECONDITION This code must already be in the LZSS
143      * @param skipHead is the number of bytes at the start of the expanded code to
144      * be skipped before data is written to buf. It is possible that skipHead is
145      * equal to codeLen.
146      * @return the length of data expanded into buf. If the expanded code is longer
147      * than space left in buf then the value returned is a negative number which when
148      * negated is equal to the number of bytes that were used of the code being expanded.
149      * This negative value also indicates the buffer is full.
150      */
151     public int expandCode(byte[] buf, int offset, short code, int skipHead) {
152         if (offset == -2) {
153             if (skipHead == 1) {
154                 skipHead = 0;
155             }
156         }
157         if (code == (short)0xFFFF || // just in case
158 skipHead == strLen[code]) // DONE no more unpacked
159 {
160             return 0;
161         }
162
163         int expandLen; // how much data we are actually expanding
164 int codeLen = strLen[code] - skipHead; // length of expanded code left
165 int bufSpace = buf.length - offset; // how much space left
166 if (bufSpace > codeLen) {
167             expandLen = codeLen; // only got this many to unpack
168 } else {
169             expandLen = bufSpace;
170         }
171
172         int skipTail = codeLen - expandLen; // only > 0 if codeLen > bufSpace [left overs]
173
174         int idx = offset + expandLen; // initialise to exclusive end address of buffer area
175
176         // NOTE: data unpacks in reverse direction and we are placing the
177 // unpacked data directly into the array in the correct location.
178 while ((idx > offset) && (code != (short)0xFFFF)) {
179             if (--skipTail < 0) { // skip required of expanded data
180 buf[--idx] = strChr[code];
181             }
182             code = strNxt[code]; // to predecessor code
183 }
184
185         if (codeLen > expandLen) {
186             return -expandLen; // indicate what part of codeLen used
187 } else {
188             return expandLen; // indicate length of dat unpacked
189 }
190     }
191     
192     public void dump(PrintStream JavaDoc out) {
193         int i;
194         for (i = 258; i < numStrings; ++i) {
195             out.println(" strNxt[" + i + "] = " + strNxt[i]
196                         + " strChr " + Integer.toHexString(strChr[i] & 0xFF)
197                         + " strLen " + Integer.toHexString(strLen[i]));
198         }
199     }
200 }
201
Popular Tags