001: /*
002: *
003: * Copyright 1990-2007 Sun Microsystems, Inc. All Rights Reserved.
004: * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER
005: *
006: * This program is free software; you can redistribute it and/or
007: * modify it under the terms of the GNU General Public License version
008: * 2 only, as published by the Free Software Foundation.
009: *
010: * This program is distributed in the hope that it will be useful, but
011: * WITHOUT ANY WARRANTY; without even the implied warranty of
012: * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
013: * General Public License version 2 for more details (a copy is
014: * included at /legal/license.txt).
015: *
016: * You should have received a copy of the GNU General Public License
017: * version 2 along with this work; if not, write to the Free Software
018: * Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA
019: * 02110-1301 USA
020: *
021: * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa
022: * Clara, CA 95054 or visit www.sun.com if you need additional
023: * information or have any questions.
024: */
025:
026: package com.sun.perseus.platform;
027:
028: import java.io.InputStream;
029: import java.io.IOException;
030: import java.util.Hashtable;
031:
032: class HuffmanTable {
033:
034: GZIPInputStream in;
035: Hashtable codeTable;
036: int minLen;
037:
038: public HuffmanTable(GZIPInputStream in, int[] lengths) {
039: this .in = in;
040: this .codeTable = buildHuffman(lengths);
041: this .minLen = Integer.MAX_VALUE;
042: for (int i = 0; i < lengths.length; i++) {
043: if (lengths[i] < minLen) {
044: minLen = lengths[i];
045: }
046: }
047: }
048:
049: private static Integer getKey(int code, int len) {
050: return new Integer((code << 8) | len);
051: }
052:
053: private static Hashtable buildHuffman(int[] tlen) {
054: int len = tlen.length;
055:
056: int[] bl_count = new int[33];
057: int[] next_code = new int[33];
058:
059: int maxlen = -1;
060: for (int i = 0; i < len; i++) {
061: if (tlen[i] > maxlen) {
062: maxlen = tlen[i];
063: }
064: ++bl_count[tlen[i]];
065: }
066:
067: int code = 0;
068: bl_count[0] = 0;
069: for (int bits = 1; bits <= maxlen; bits++) {
070: code = (code + bl_count[bits - 1]) << 1;
071: next_code[bits] = code;
072: }
073:
074: Hashtable codeTable = new Hashtable(len);
075: for (int n = 0; n < len; n++) {
076: int l = tlen[n];
077: if (l != 0) {
078: codeTable.put(getKey(next_code[l], l), new Integer(n));
079: ++next_code[l];
080: }
081: }
082:
083: return codeTable;
084: }
085:
086: private int getVal(int code, int len) {
087: Object o = codeTable.get(getKey(code, len));
088: if (o != null) {
089: return ((Integer) o).intValue();
090: }
091: return -1;
092: }
093:
094: public int readSymbol() throws IOException {
095: int code = in.readHuffmanBits(minLen);
096: int len = minLen;
097:
098: while (true) {
099: int val = getVal(code, len);
100: if (val != -1) {
101: return val;
102: }
103: code = (code << 1) | in.readBit();
104: ++len;
105: }
106: }
107: }
108:
109: /**
110: * A simple implementation of the gzip/deflate compression scheme.
111: * The entire source stream is read and decoded at once; although this
112: * requires allocating storage for the entire output, it avoids the
113: * need for a pair of 32K buffers that would normally be used for
114: * decompression purposes. For the common use case of loading font
115: * files, which will be decompressed and parsed into a
116: * <code>PiscesFont</code> object immediately, there is no real
117: * drawback to this eager approach.
118: *
119: * <p> For simplicitly, <code>mark</code> and <code>reset</code> are
120: * not supported.
121: *
122: * @author Daniel Rice
123: */
124: class GZIPInputStream extends InputStream {
125:
126: private static final int[] perm = { 16, 17, 18, 0, 8, 7, 9, 6, 10,
127: 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 };
128:
129: private static final int[] lengthsTable;
130: /* {
131: 3, 4, 5, 6, 7, 8, 9, 10,
132: 11, 13, 15, 17,
133: 19, 23, 27, 31,
134: 35, 43, 51, 59,
135: 67, 83, 99, 115,
136: 131, 163, 195, 227,
137: 258
138: } */
139:
140: private static final int[] lengthExtraBitsTable;
141: /* {
142: 0, 0, 0, 0, 0, 0, 0, 0,
143: 1, 1, 1, 1,
144: 2, 2, 2, 2,
145: 3, 3, 3, 3,
146: 4, 4, 4, 4,
147: 5, 5, 5, 5,
148: 0
149: } */
150:
151: private static final int[] distancesTable;
152: /* {
153: 1, 2, 3, 4,
154: 5, 7,
155: 9, 13,
156: 17, 25,
157: 33, 49,
158: 65, 97,
159: 129, 193,
160: 257, 385,
161: 513, 769,
162: 1025, 1537,
163: 2049, 3073,
164: 4097, 6145,
165: 8193, 12289,
166: 16385, 24577,
167: } */
168:
169: private static final int[] distanceExtraBitsTable;
170: /* {
171: 0, 0, 0, 0,
172: 1, 1,
173: 2, 2,
174: 3, 3,
175: 4, 4,
176: 5, 5,
177: 6, 6,
178: 7, 7,
179: 8, 8,
180: 9, 9,
181: 10, 10,
182: 11, 11,
183: 12, 12,
184: 13, 13
185: } */
186:
187: InputStream in;
188:
189: byte[] data = new byte[100];
190: int count = 0;
191: int idx = 0;
192:
193: int curByte;
194: int curPos = 8;
195:
196: // It takes less space to initialize the literal/length and
197: // distance tables programmatically than using explicit initialzers
198: // due to the verbose way initializers are translated into bytecode.
199: static {
200: lengthExtraBitsTable = new int[29];
201: lengthsTable = new int[29];
202: distanceExtraBitsTable = new int[30];
203: distancesTable = new int[30];
204:
205: int idx = 0;
206: for (int i = 4; i < 29; i++) {
207: lengthExtraBitsTable[i] = idx;
208: if ((i % 4) == 3) {
209: ++idx;
210: }
211: }
212:
213: int len = 3;
214: for (int i = 0; i < lengthExtraBitsTable.length; i++) {
215: lengthsTable[i] = len;
216: len += 1 << lengthExtraBitsTable[i];
217: }
218: lengthsTable[28] = 258; // that's what the spec says...
219:
220: idx = 0;
221: for (int i = 2; i < 30; i++) {
222: distanceExtraBitsTable[i] = idx;
223: if ((i % 2) == 1) {
224: ++idx;
225: }
226: }
227:
228: int code = 1;
229: for (int i = 0; i < distancesTable.length; i++) {
230: distancesTable[i] = code;
231: code += 1 << distanceExtraBitsTable[i];
232: }
233: }
234:
235: public GZIPInputStream(InputStream in) throws IOException {
236: this .in = in;
237:
238: // Read GZIP header
239: readGZIPHeader();
240:
241: // Read blocks until final block is reached
242: while (!readBlock()) {
243: }
244: }
245:
246: private void readGZIPHeader() throws IOException {
247: int id1 = in.read(); // 31
248: int id2 = in.read(); // 139
249: int cm = in.read();
250:
251: int flg = in.read();
252: int ftext = flg & 0x1;
253: int fhcrc = (flg >> 1) & 0x1;
254: int fextra = (flg >> 2) & 0x1;
255: int fname = (flg >> 3) & 0x1;
256: int fcomment = (flg >> 4) & 0x1;
257:
258: int mtime0 = in.read();
259: int mtime1 = in.read();
260: int mtime2 = in.read();
261: int mtime3 = in.read();
262: long mtime = ((long) mtime3 << 24) | ((long) mtime2 << 16)
263: | ((long) mtime1 << 8) | ((long) mtime0);
264:
265: int xfl = in.read();
266: int os = in.read();
267:
268: // Skip optional header fields
269: if (fextra == 0x1) {
270: int xlen = (in.read() << 8) | in.read();
271: for (int i = 0; i < xlen; i++) {
272: in.read();
273: }
274: }
275:
276: if (fname == 0x1) {
277: while (in.read() != 0) {
278: }
279: }
280: if (fcomment == 0x1) {
281: while (in.read() != 0) {
282: }
283: }
284: if (fhcrc == 0x1) {
285: int crc = (in.read() << 8) | in.read();
286: }
287: }
288:
289: int readBit() throws IOException {
290: if (curPos == 8) {
291: curByte = in.read();
292: curPos = 0;
293: }
294:
295: int bit = (curByte >> curPos++) & 0x1;
296: return bit;
297: }
298:
299: int readBits(int numBits) throws IOException {
300: int val = 0;
301: for (int i = 0; i < numBits; i++) {
302: val |= readBit() << i;
303: }
304: return val;
305: }
306:
307: int readHuffmanBits(int numBits) throws IOException {
308: int val = 0;
309: for (int i = 0; i < numBits; i++) {
310: val <<= 1;
311: val |= readBit();
312: }
313: return val;
314: }
315:
316: private void emit(int b) {
317: if (count >= data.length) {
318: byte[] tmp = new byte[data.length + 512];
319: System.arraycopy(data, 0, tmp, 0, data.length);
320: data = tmp;
321: }
322: data[count++] = (byte) b;
323: }
324:
325: private boolean readBlock() throws IOException {
326: int bfinal = readBits(1);
327: int btype = readBits(2);
328:
329: if (btype == 0) {
330: // Uncompressed data
331: readBits(5); // skip extra bits
332: int len = (in.read() << 8) | in.read();
333: in.read();
334: in.read();
335: for (int i = 0; i < len; i++) {
336: emit(in.read());
337: }
338: } else if (btype == 1 || btype == 2) {
339: HuffmanTable lltable = null;
340: HuffmanTable dtable = null;
341:
342: if (btype == 2) {
343: // Dynamic Huffman codes
344:
345: int hlit = readBits(5) + 257;
346: int hdist = readBits(5) + 1;
347: int hclen = readBits(4) + 4;
348:
349: int[] hlengths = new int[19];
350: for (int i = 0; i < hclen; i++) {
351: int len = readBits(3);
352: hlengths[perm[i]] = len;
353: }
354: HuffmanTable htable = new HuffmanTable(this , hlengths);
355:
356: int[] lengths = new int[hlit + hdist];
357: int idx = 0;
358:
359: do {
360: int sym = htable.readSymbol();
361: if (sym <= 15) {
362: lengths[idx++] = sym;
363: } else if (sym == 16) {
364: int repeat = readBits(2) + 3;
365: int prev = lengths[idx - 1];
366: for (int i = 0; i < repeat; i++) {
367: lengths[idx++] = prev;
368: }
369: } else {
370: int bits = (sym == 17) ? 3 : 7;
371: int repeat = readBits(bits);
372: repeat += (sym == 17) ? 3 : 11;
373: for (int i = 0; i < repeat; i++) {
374: lengths[idx++] = 0;
375: }
376: }
377: } while (idx < hlit + hdist);
378:
379: int[] hlitlengths = new int[hlit];
380: System.arraycopy(lengths, 0, hlitlengths, 0, hlit);
381: lltable = new HuffmanTable(this , hlitlengths);
382:
383: int[] hdistlengths = new int[hdist];
384: System.arraycopy(lengths, hlit, hdistlengths, 0, hdist);
385: dtable = new HuffmanTable(this , hdistlengths);
386: }
387:
388: // Decompress actual data
389: while (true) {
390: int llcode = -1;
391: if (btype == 1) {
392: int code = readHuffmanBits(7);
393:
394: if (code <= 23) {
395: llcode = 256 + code;
396: } else {
397: // 8 bit codes
398: code <<= 1;
399: code |= readBit();
400:
401: if (code < 192) {
402: llcode = code - 48;
403: } else if (code < 200) {
404: llcode = 280 + code - 192;
405: } else {
406: // 9 bit codes
407: code <<= 1;
408: code |= readBit();
409: llcode = 144 + code - 400;
410: }
411: }
412: } else if (btype == 2) {
413: llcode = lltable.readSymbol();
414: }
415:
416: if (llcode < 256) {
417: emit(llcode);
418: } else if (llcode == 256) {
419: break;
420: } else if (llcode <= 285) {
421: int length = lengthsTable[llcode - 257];
422: int extraLengthBits = lengthExtraBitsTable[llcode - 257];
423: if (extraLengthBits > 0) {
424: int extra = readBits(extraLengthBits);
425: length += extra;
426: }
427:
428: int distanceCode = -1;
429: if (btype == 1) {
430: distanceCode = readHuffmanBits(5);
431: } else if (btype == 2) {
432: distanceCode = dtable.readSymbol();
433: }
434:
435: int distance = distancesTable[distanceCode];
436: int extraDistBits = distanceExtraBitsTable[distanceCode];
437: if (extraDistBits > 0) {
438: int extra = readBits(extraDistBits);
439: distance += extra;
440: }
441:
442: for (int i = 0; i < length; i++) {
443: emit(data[count - distance]);
444: }
445: } else {
446: // error
447: }
448: }
449: } else {
450: // error
451: }
452:
453: return (bfinal == 0x1);
454: }
455:
456: public int available() throws IOException {
457: return count - idx;
458: }
459:
460: public int read() throws IOException {
461: if (idx == count) {
462: return -1;
463: } else {
464: return data[idx++] & 0xff;
465: }
466: }
467:
468: public int read(byte[] buf, int off, int len) throws IOException {
469:
470: //If no byte is available because the stream is at end of file
471: //the value -1 is returned
472: if (idx == count) {
473: return -1;
474: }
475:
476: //otherwise, at least one byte is read and stored into b.
477: for (int i = off; i < off + len; i++) {
478: if (idx == count) {
479: return (i - off);
480: }
481: buf[i] = data[idx++];
482: }
483: return len;
484: }
485:
486: public long skip(long n) throws IOException {
487: int saveIdx = idx;
488: idx = Math.min((int) (idx + n), count);
489: return idx - saveIdx;
490: }
491:
492: public void close() throws IOException {
493: // do nothing
494: }
495:
496: public boolean markSupported() {
497: return false;
498: }
499:
500: public synchronized void mark(int readlimit) {
501: // do nothing
502: }
503:
504: public synchronized void reset() throws IOException {
505: throw new IOException("mark/reset not supported");
506: }
507:
508: public static final int GZIP_MAGIC = 35615;
509:
510: }
|