1 /*
2 * Copyright (c) 2005, 2014, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 package com.sun.imageio.plugins.common;
27
28 import java.io.PrintStream;
29
30 /**
31 * General purpose LZW String Table.
32 * Extracted from GIFEncoder by Adam Doppelt
33 * Comments added by Robin Luiten
34 * <code>expandCode</code> added by Robin Luiten
35 * The strLen table to give quick access to the lenght of an expanded
36 * code for use by the <code>expandCode</code> method added by Robin.
37 **/
38 public class LZWStringTable {
39 /** codesize + Reserved Codes */
40 private static final int RES_CODES = 2;
41
42 private static final short HASH_FREE = (short)0xFFFF;
43 private static final short NEXT_FIRST = (short)0xFFFF;
44
45 private static final int MAXBITS = 12;
46 private static final int MAXSTR = (1 << MAXBITS);
47
48 private static final short HASHSIZE = 9973;
49 private static final short HASHSTEP = 2039;
50
51 byte[] strChr; // after predecessor character
52 short[] strNxt; // predecessor string
53 short[] strHsh; // hash table to find predecessor + char pairs
54 short numStrings; // next code if adding new prestring + char
55
56 /*
57 * each entry corresponds to a code and contains the length of data
58 * that the code expands to when decoded.
59 */
60 int[] strLen;
61
62 /*
63 * Constructor allocate memory for string store data
64 */
65 public LZWStringTable() {
66 strChr = new byte[MAXSTR];
67 strNxt = new short[MAXSTR];
68 strLen = new int[MAXSTR];
69 strHsh = new short[HASHSIZE];
70 }
71
72 /*
73 * @param index value of -1 indicates no predecessor [used in initialisation]
74 * @param b the byte [character] to add to the string store which follows
75 * the predecessor string specified the index.
76 * @return 0xFFFF if no space in table left for addition of predecesor
77 * index and byte b. Else return the code allocated for combination index + b.
78 */
79 public int addCharString(short index, byte b) {
80 int hshidx;
81
82 if (numStrings >= MAXSTR) { // if used up all codes
83 return 0xFFFF;
84 }
85
86 hshidx = hash(index, b);
87 while (strHsh[hshidx] != HASH_FREE) {
88 hshidx = (hshidx + HASHSTEP) % HASHSIZE;
89 }
90
91 strHsh[hshidx] = numStrings;
92 strChr[numStrings] = b;
93 if (index == HASH_FREE) {
94 strNxt[numStrings] = NEXT_FIRST;
95 strLen[numStrings] = 1;
96 } else {
97 strNxt[numStrings] = index;
98 strLen[numStrings] = strLen[index] + 1;
99 }
100
101 return numStrings++; // return the code and inc for next code
102 }
103
104 /*
105 * @param index index to prefix string
106 * @param b the character that follws the index prefix
107 * @return b if param index is HASH_FREE. Else return the code
108 * for this prefix and byte successor
109 */
110 public short findCharString(short index, byte b) {
111 int hshidx, nxtidx;
112
113 if (index == HASH_FREE) {
114 return (short)(b & 0xFF); // Rob fixed used to sign extend
115 }
116
117 hshidx = hash(index, b);
118 while ((nxtidx = strHsh[hshidx]) != HASH_FREE) { // search
119 if (strNxt[nxtidx] == index && strChr[nxtidx] == b) {
120 return (short)nxtidx;
121 }
122 hshidx = (hshidx + HASHSTEP) % HASHSIZE;
123 }
124
125 return (short)0xFFFF;
126 }
127
128 /*
129 * @param codesize the size of code to be preallocated for the
130 * string store.
131 */
132 public void clearTable(int codesize) {
133 numStrings = 0;
134
135 for (int q = 0; q < HASHSIZE; q++) {
136 strHsh[q] = HASH_FREE;
137 }
138
139 int w = (1 << codesize) + RES_CODES;
140 for (int q = 0; q < w; q++) {
141 addCharString((short)0xFFFF, (byte)q); // init with no prefix
142 }
143 }
144
145 public static int hash(short index, byte lastbyte) {
146 return (((short)(lastbyte << 8) ^ index) & 0xFFFF) % HASHSIZE;
147 }
148
149 /*
150 * If expanded data doesn't fit into array only what will fit is written
151 * to buf and the return value indicates how much of the expanded code has
152 * been written to the buf. The next call to expandCode() should be with
153 * the same code and have the skip parameter set the negated value of the
154 * previous return. Succesive negative return values should be negated and
155 * added together for next skip parameter value with same code.
156 *
157 * @param buf buffer to place expanded data into
158 * @param offset offset to place expanded data
159 * @param code the code to expand to the byte array it represents.
160 * PRECONDITION This code must already be in the LZSS
161 * @param skipHead is the number of bytes at the start of the expanded code to
162 * be skipped before data is written to buf. It is possible that skipHead is
163 * equal to codeLen.
164 * @return the length of data expanded into buf. If the expanded code is longer
165 * than space left in buf then the value returned is a negative number which when
166 * negated is equal to the number of bytes that were used of the code being expanded.
167 * This negative value also indicates the buffer is full.
168 */
169 public int expandCode(byte[] buf, int offset, short code, int skipHead) {
170 if (offset == -2) {
171 if (skipHead == 1) {
172 skipHead = 0;
173 }
174 }
175 if (code == (short)0xFFFF || // just in case
176 skipHead == strLen[code]) // DONE no more unpacked
177 {
178 return 0;
179 }
180
181 int expandLen; // how much data we are actually expanding
182 int codeLen = strLen[code] - skipHead; // length of expanded code left
183 int bufSpace = buf.length - offset; // how much space left
184 if (bufSpace > codeLen) {
185 expandLen = codeLen; // only got this many to unpack
186 } else {
187 expandLen = bufSpace;
188 }
189
190 int skipTail = codeLen - expandLen; // only > 0 if codeLen > bufSpace [left overs]
191
192 int idx = offset + expandLen; // initialise to exclusive end address of buffer area
193
194 // NOTE: data unpacks in reverse direction and we are placing the
195 // unpacked data directly into the array in the correct location.
196 while ((idx > offset) && (code != (short)0xFFFF)) {
197 if (--skipTail < 0) { // skip required of expanded data
198 buf[--idx] = strChr[code];
199 }
200 code = strNxt[code]; // to predecessor code
201 }
202
203 if (codeLen > expandLen) {
204 return -expandLen; // indicate what part of codeLen used
205 } else {
206 return expandLen; // indicate length of dat unpacked
207 }
208 }
209
210 public void dump(PrintStream out) {
211 int i;
212 for (i = 258; i < numStrings; ++i) {
213 out.println(" strNxt[" + i + "] = " + strNxt[i]
214 + " strChr " + Integer.toHexString(strChr[i] & 0xFF)
215 + " strLen " + Integer.toHexString(strLen[i]));
216 }
217 }
218 }