1 /* 2 * Copyright (c) 2005, 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 final static int RES_CODES = 2; 41 42 private final static short HASH_FREE = (short)0xFFFF; 43 private final static short NEXT_FIRST = (short)0xFFFF; 44 45 private final static int MAXBITS = 12; 46 private final static int MAXSTR = (1 << MAXBITS); 47 48 private final static short HASHSIZE = 9973; 49 private final static 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 static public int hash(short index, byte lastbyte) { 146 return ((int)((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 }