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} 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} 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      */
LZWStringTable()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      */
addCharString(short index, byte b)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      */
findCharString(short index, byte b)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      */
clearTable(int codesize)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 
hash(short index, byte lastbyte)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      */
expandCode(byte[] buf, int offset, short code, int skipHead)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 
dump(PrintStream out)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 }
219