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.pisces;
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: */
123: class GZIPInputStream extends InputStream {
124:
125: private static final int[] perm = { 16, 17, 18, 0, 8, 7, 9, 6, 10,
126: 5, 11, 4, 12, 3, 13, 2, 14, 1, 15 };
127:
128: private static final int[] lengthsTable;
129: /* {
130: 3, 4, 5, 6, 7, 8, 9, 10,
131: 11, 13, 15, 17,
132: 19, 23, 27, 31,
133: 35, 43, 51, 59,
134: 67, 83, 99, 115,
135: 131, 163, 195, 227,
136: 258
137: } */
138:
139: private static final int[] lengthExtraBitsTable;
140: /* {
141: 0, 0, 0, 0, 0, 0, 0, 0,
142: 1, 1, 1, 1,
143: 2, 2, 2, 2,
144: 3, 3, 3, 3,
145: 4, 4, 4, 4,
146: 5, 5, 5, 5,
147: 0
148: } */
149:
150: private static final int[] distancesTable;
151: /* {
152: 1, 2, 3, 4,
153: 5, 7,
154: 9, 13,
155: 17, 25,
156: 33, 49,
157: 65, 97,
158: 129, 193,
159: 257, 385,
160: 513, 769,
161: 1025, 1537,
162: 2049, 3073,
163: 4097, 6145,
164: 8193, 12289,
165: 16385, 24577,
166: } */
167:
168: private static final int[] distanceExtraBitsTable;
169: /* {
170: 0, 0, 0, 0,
171: 1, 1,
172: 2, 2,
173: 3, 3,
174: 4, 4,
175: 5, 5,
176: 6, 6,
177: 7, 7,
178: 8, 8,
179: 9, 9,
180: 10, 10,
181: 11, 11,
182: 12, 12,
183: 13, 13
184: } */
185:
186: InputStream in;
187:
188: byte[] data = new byte[100];
189: int count = 0;
190: int idx = 0;
191:
192: int curByte;
193: int curPos = 8;
194:
195: // It takes less space to initialize the literal/length and
196: // distance tables programatically than using explicit initialzers
197: // due to the verbose way initializers are translated into bytecode.
198: static {
199: lengthExtraBitsTable = new int[29];
200: lengthsTable = new int[29];
201: distanceExtraBitsTable = new int[30];
202: distancesTable = new int[30];
203:
204: int idx = 0;
205: for (int i = 4; i < 29; i++) {
206: lengthExtraBitsTable[i] = idx;
207: if ((i % 4) == 3) {
208: ++idx;
209: }
210: }
211:
212: int len = 3;
213: for (int i = 0; i < lengthExtraBitsTable.length; i++) {
214: lengthsTable[i] = len;
215: len += 1 << lengthExtraBitsTable[i];
216: }
217: lengthsTable[28] = 258; // that's what the spec says...
218:
219: idx = 0;
220: for (int i = 2; i < 30; i++) {
221: distanceExtraBitsTable[i] = idx;
222: if ((i % 2) == 1) {
223: ++idx;
224: }
225: }
226:
227: int code = 1;
228: for (int i = 0; i < distancesTable.length; i++) {
229: distancesTable[i] = code;
230: code += 1 << distanceExtraBitsTable[i];
231: }
232: }
233:
234: public GZIPInputStream(InputStream in) throws IOException {
235: this .in = in;
236:
237: // Read GZIP header
238: readGZIPHeader();
239:
240: // Read blocks until final block is reached
241: while (!readBlock()) {
242: }
243: }
244:
245: private void readGZIPHeader() throws IOException {
246: int id1 = in.read(); // 31
247: int id2 = in.read(); // 139
248: int cm = in.read();
249:
250: int flg = in.read();
251: int ftext = flg & 0x1;
252: int fhcrc = (flg >> 1) & 0x1;
253: int fextra = (flg >> 2) & 0x1;
254: int fname = (flg >> 3) & 0x1;
255: int fcomment = (flg >> 4) & 0x1;
256:
257: int mtime0 = in.read();
258: int mtime1 = in.read();
259: int mtime2 = in.read();
260: int mtime3 = in.read();
261: long mtime = ((long) mtime3 << 24) | ((long) mtime2 << 16)
262: | ((long) mtime1 << 8) | ((long) mtime0);
263:
264: int xfl = in.read();
265: int os = in.read();
266:
267: // Skip optional header fields
268: if (fextra == 0x1) {
269: int xlen = (in.read() << 8) | in.read();
270: for (int i = 0; i < xlen; i++) {
271: in.read();
272: }
273: }
274:
275: if (fname == 0x1) {
276: while (in.read() != 0) {
277: }
278: }
279: if (fcomment == 0x1) {
280: while (in.read() != 0) {
281: }
282: }
283: if (fhcrc == 0x1) {
284: int crc = (in.read() << 8) | in.read();
285: }
286: }
287:
288: int readBit() throws IOException {
289: if (curPos == 8) {
290: curByte = in.read();
291: curPos = 0;
292: }
293:
294: int bit = (curByte >> curPos++) & 0x1;
295: return bit;
296: }
297:
298: int readBits(int numBits) throws IOException {
299: int val = 0;
300: for (int i = 0; i < numBits; i++) {
301: val |= readBit() << i;
302: }
303: return val;
304: }
305:
306: int readHuffmanBits(int numBits) throws IOException {
307: int val = 0;
308: for (int i = 0; i < numBits; i++) {
309: val <<= 1;
310: val |= readBit();
311: }
312: return val;
313: }
314:
315: private void emit(int b) {
316: if (count >= data.length) {
317: byte[] tmp = new byte[data.length + 512];
318: System.arraycopy(data, 0, tmp, 0, data.length);
319: data = tmp;
320: }
321: data[count++] = (byte) b;
322: }
323:
324: private boolean readBlock() throws IOException {
325: int bfinal = readBits(1);
326: int btype = readBits(2);
327:
328: if (btype == 0) {
329: // Uncompressed data
330: readBits(5); // skip extra bits
331: int len = (in.read() << 8) | in.read();
332: in.read();
333: in.read();
334: for (int i = 0; i < len; i++) {
335: emit(in.read());
336: }
337: } else if (btype == 1 || btype == 2) {
338: HuffmanTable lltable = null;
339: HuffmanTable dtable = null;
340:
341: if (btype == 2) {
342: // Dynamic Huffman codes
343:
344: int hlit = readBits(5) + 257;
345: int hdist = readBits(5) + 1;
346: int hclen = readBits(4) + 4;
347:
348: int[] hlengths = new int[19];
349: for (int i = 0; i < hclen; i++) {
350: int len = readBits(3);
351: hlengths[perm[i]] = len;
352: }
353: HuffmanTable htable = new HuffmanTable(this , hlengths);
354:
355: int[] lengths = new int[hlit + hdist];
356: int idx = 0;
357:
358: do {
359: int sym = htable.readSymbol();
360: if (sym <= 15) {
361: lengths[idx++] = sym;
362: } else if (sym == 16) {
363: int repeat = readBits(2) + 3;
364: int prev = lengths[idx - 1];
365: for (int i = 0; i < repeat; i++) {
366: lengths[idx++] = prev;
367: }
368: } else {
369: int bits = (sym == 17) ? 3 : 7;
370: int repeat = readBits(bits);
371: repeat += (sym == 17) ? 3 : 11;
372: for (int i = 0; i < repeat; i++) {
373: lengths[idx++] = 0;
374: }
375: }
376: } while (idx < hlit + hdist);
377:
378: int[] hlitlengths = new int[hlit];
379: System.arraycopy(lengths, 0, hlitlengths, 0, hlit);
380: lltable = new HuffmanTable(this , hlitlengths);
381:
382: int[] hdistlengths = new int[hdist];
383: System.arraycopy(lengths, hlit, hdistlengths, 0, hdist);
384: dtable = new HuffmanTable(this , hdistlengths);
385: }
386:
387: // Decompress actual data
388: while (true) {
389: int llcode = -1;
390: if (btype == 1) {
391: int code = readHuffmanBits(7);
392:
393: if (code <= 23) {
394: llcode = 256 + code;
395: } else {
396: // 8 bit codes
397: code <<= 1;
398: code |= readBit();
399:
400: if (code < 192) {
401: llcode = code - 48;
402: } else if (code < 200) {
403: llcode = 280 + code - 192;
404: } else {
405: // 9 bit codes
406: code <<= 1;
407: code |= readBit();
408: llcode = 144 + code - 400;
409: }
410: }
411: } else if (btype == 2) {
412: llcode = lltable.readSymbol();
413: }
414:
415: if (llcode < 256) {
416: emit(llcode);
417: } else if (llcode == 256) {
418: break;
419: } else if (llcode <= 285) {
420: int length = lengthsTable[llcode - 257];
421: int extraLengthBits = lengthExtraBitsTable[llcode - 257];
422: if (extraLengthBits > 0) {
423: int extra = readBits(extraLengthBits);
424: length += extra;
425: }
426:
427: int distanceCode = -1;
428: if (btype == 1) {
429: distanceCode = readHuffmanBits(5);
430: } else if (btype == 2) {
431: distanceCode = dtable.readSymbol();
432: }
433:
434: int distance = distancesTable[distanceCode];
435: int extraDistBits = distanceExtraBitsTable[distanceCode];
436: if (extraDistBits > 0) {
437: int extra = readBits(extraDistBits);
438: distance += extra;
439: }
440:
441: for (int i = 0; i < length; i++) {
442: emit(data[count - distance]);
443: }
444: } else {
445: // error
446: }
447: }
448: } else {
449: // error
450: }
451:
452: return (bfinal == 0x1);
453: }
454:
455: public int available() throws IOException {
456: return count - idx;
457: }
458:
459: public int read() throws IOException {
460: if (idx == count) {
461: return -1;
462: } else {
463: return data[idx++] & 0xff;
464: }
465: }
466:
467: public int read(byte[] buf, int off, int len) throws IOException {
468: for (int i = off; i < off + len; i++) {
469: if (idx == count) {
470: return i - off;
471: }
472: buf[i] = data[idx++];
473: }
474: return len;
475: }
476:
477: public long skip(long n) throws IOException {
478: int saveIdx = idx;
479: idx = Math.min((int) (idx + n), count);
480: return idx - saveIdx;
481: }
482:
483: public void close() throws IOException {
484: // do nothing
485: }
486:
487: public boolean markSupported() {
488: return false;
489: }
490:
491: public synchronized void mark(int readlimit) {
492: // do nothing
493: }
494:
495: public synchronized void reset() throws IOException {
496: throw new IOException("mark/reset not supported");
497: }
498: }
|