GNU Classpath (0.98) | |
Frames | No Frames |
1: /* Inflater.java - Decompress a data stream 2: Copyright (C) 1999, 2000, 2001, 2003, 2005 Free Software Foundation, Inc. 3: 4: This file is part of GNU Classpath. 5: 6: GNU Classpath is free software; you can redistribute it and/or modify 7: it under the terms of the GNU General Public License as published by 8: the Free Software Foundation; either version 2, or (at your option) 9: any later version. 10: 11: GNU Classpath is distributed in the hope that it will be useful, but 12: WITHOUT ANY WARRANTY; without even the implied warranty of 13: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14: General Public License for more details. 15: 16: You should have received a copy of the GNU General Public License 17: along with GNU Classpath; see the file COPYING. If not, write to the 18: Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 19: 02110-1301 USA. 20: 21: Linking this library statically or dynamically with other modules is 22: making a combined work based on this library. Thus, the terms and 23: conditions of the GNU General Public License cover the whole 24: combination. 25: 26: As a special exception, the copyright holders of this library give you 27: permission to link this library with independent modules to produce an 28: executable, regardless of the license terms of these independent 29: modules, and to copy and distribute the resulting executable under 30: terms of your choice, provided that you also meet, for each linked 31: independent module, the terms and conditions of the license of that 32: module. An independent module is a module which is not derived from 33: or based on this library. If you modify this library, you may extend 34: this exception to your version of the library, but you are not 35: obligated to do so. If you do not wish to do so, delete this 36: exception statement from your version. */ 37: 38: package java.util.zip; 39: 40: /* Written using on-line Java Platform 1.2 API Specification 41: * and JCL book. 42: * Believed complete and correct. 43: */ 44: 45: /** 46: * Inflater is used to decompress data that has been compressed according 47: * to the "deflate" standard described in rfc1950. 48: * 49: * The usage is as following. First you have to set some input with 50: * <code>setInput()</code>, then inflate() it. If inflate doesn't 51: * inflate any bytes there may be three reasons: 52: * <ul> 53: * <li>needsInput() returns true because the input buffer is empty. 54: * You have to provide more input with <code>setInput()</code>. 55: * NOTE: needsInput() also returns true when, the stream is finished. 56: * </li> 57: * <li>needsDictionary() returns true, you have to provide a preset 58: * dictionary with <code>setDictionary()</code>.</li> 59: * <li>finished() returns true, the inflater has finished.</li> 60: * </ul> 61: * Once the first output byte is produced, a dictionary will not be 62: * needed at a later stage. 63: * 64: * @author John Leuner, Jochen Hoenicke 65: * @author Tom Tromey 66: * @date May 17, 1999 67: * @since JDK 1.1 68: */ 69: public class Inflater 70: { 71: /* Copy lengths for literal codes 257..285 */ 72: private static final int CPLENS[] = 73: { 74: 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 15, 17, 19, 23, 27, 31, 75: 35, 43, 51, 59, 67, 83, 99, 115, 131, 163, 195, 227, 258 76: }; 77: 78: /* Extra bits for literal codes 257..285 */ 79: private static final int CPLEXT[] = 80: { 81: 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 2, 2, 2, 2, 82: 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 0 83: }; 84: 85: /* Copy offsets for distance codes 0..29 */ 86: private static final int CPDIST[] = { 87: 1, 2, 3, 4, 5, 7, 9, 13, 17, 25, 33, 49, 65, 97, 129, 193, 88: 257, 385, 513, 769, 1025, 1537, 2049, 3073, 4097, 6145, 89: 8193, 12289, 16385, 24577 90: }; 91: 92: /* Extra bits for distance codes */ 93: private static final int CPDEXT[] = { 94: 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 95: 7, 7, 8, 8, 9, 9, 10, 10, 11, 11, 96: 12, 12, 13, 13 97: }; 98: 99: /* This are the state in which the inflater can be. */ 100: private static final int DECODE_HEADER = 0; 101: private static final int DECODE_DICT = 1; 102: private static final int DECODE_BLOCKS = 2; 103: private static final int DECODE_STORED_LEN1 = 3; 104: private static final int DECODE_STORED_LEN2 = 4; 105: private static final int DECODE_STORED = 5; 106: private static final int DECODE_DYN_HEADER = 6; 107: private static final int DECODE_HUFFMAN = 7; 108: private static final int DECODE_HUFFMAN_LENBITS = 8; 109: private static final int DECODE_HUFFMAN_DIST = 9; 110: private static final int DECODE_HUFFMAN_DISTBITS = 10; 111: private static final int DECODE_CHKSUM = 11; 112: private static final int FINISHED = 12; 113: 114: /** This variable contains the current state. */ 115: private int mode; 116: 117: /** 118: * The adler checksum of the dictionary or of the decompressed 119: * stream, as it is written in the header resp. footer of the 120: * compressed stream. <br> 121: * 122: * Only valid if mode is DECODE_DICT or DECODE_CHKSUM. 123: */ 124: private int readAdler; 125: /** 126: * The number of bits needed to complete the current state. This 127: * is valid, if mode is DECODE_DICT, DECODE_CHKSUM, 128: * DECODE_HUFFMAN_LENBITS or DECODE_HUFFMAN_DISTBITS. 129: */ 130: private int neededBits; 131: private int repLength, repDist; 132: private int uncomprLen; 133: /** 134: * True, if the last block flag was set in the last block of the 135: * inflated stream. This means that the stream ends after the 136: * current block. 137: */ 138: private boolean isLastBlock; 139: 140: /** 141: * The total number of inflated bytes. 142: */ 143: private long totalOut; 144: /** 145: * The total number of bytes set with setInput(). This is not the 146: * value returned by getTotalIn(), since this also includes the 147: * unprocessed input. 148: */ 149: private long totalIn; 150: /** 151: * This variable stores the nowrap flag that was given to the constructor. 152: * True means, that the inflated stream doesn't contain a header nor the 153: * checksum in the footer. 154: */ 155: private boolean nowrap; 156: 157: private StreamManipulator input; 158: private OutputWindow outputWindow; 159: private InflaterDynHeader dynHeader; 160: private InflaterHuffmanTree litlenTree, distTree; 161: private Adler32 adler; 162: 163: /** 164: * Creates a new inflater. 165: */ 166: public Inflater () 167: { 168: this (false); 169: } 170: 171: /** 172: * Creates a new inflater. 173: * @param nowrap true if no header and checksum field appears in the 174: * stream. This is used for GZIPed input. For compatibility with 175: * Sun JDK you should provide one byte of input more than needed in 176: * this case. 177: */ 178: public Inflater (boolean nowrap) 179: { 180: this.nowrap = nowrap; 181: this.adler = new Adler32(); 182: input = new StreamManipulator(); 183: outputWindow = new OutputWindow(); 184: mode = nowrap ? DECODE_BLOCKS : DECODE_HEADER; 185: } 186: 187: /** 188: * Finalizes this object. 189: */ 190: protected void finalize () 191: { 192: /* Exists only for compatibility */ 193: } 194: 195: /** 196: * Frees all objects allocated by the inflater. There's no reason 197: * to call this, since you can just rely on garbage collection (even 198: * for the Sun implementation). Exists only for compatibility 199: * with Sun's JDK, where the compressor allocates native memory. 200: * If you call any method (even reset) afterwards the behaviour is 201: * <i>undefined</i>. 202: */ 203: public void end () 204: { 205: outputWindow = null; 206: input = null; 207: dynHeader = null; 208: litlenTree = null; 209: distTree = null; 210: adler = null; 211: } 212: 213: /** 214: * Returns true, if the inflater has finished. This means, that no 215: * input is needed and no output can be produced. 216: */ 217: public boolean finished() 218: { 219: return mode == FINISHED && outputWindow.getAvailable() == 0; 220: } 221: 222: /** 223: * Gets the adler checksum. This is either the checksum of all 224: * uncompressed bytes returned by inflate(), or if needsDictionary() 225: * returns true (and thus no output was yet produced) this is the 226: * adler checksum of the expected dictionary. 227: * @returns the adler checksum. 228: */ 229: public int getAdler() 230: { 231: return needsDictionary() ? readAdler : (int) adler.getValue(); 232: } 233: 234: /** 235: * Gets the number of unprocessed input. Useful, if the end of the 236: * stream is reached and you want to further process the bytes after 237: * the deflate stream. 238: * @return the number of bytes of the input which were not processed. 239: */ 240: public int getRemaining() 241: { 242: return input.getAvailableBytes(); 243: } 244: 245: /** 246: * Gets the total number of processed compressed input bytes. 247: * @return the total number of bytes of processed input bytes. 248: */ 249: public int getTotalIn() 250: { 251: return (int) (totalIn - getRemaining()); 252: } 253: 254: /** 255: * Gets the total number of processed compressed input bytes. 256: * @return the total number of bytes of processed input bytes. 257: * @since 1.5 258: */ 259: public long getBytesRead() 260: { 261: return totalIn - getRemaining(); 262: } 263: 264: /** 265: * Gets the total number of output bytes returned by inflate(). 266: * @return the total number of output bytes. 267: */ 268: public int getTotalOut() 269: { 270: return (int) totalOut; 271: } 272: 273: /** 274: * Gets the total number of output bytes returned by inflate(). 275: * @return the total number of output bytes. 276: * @since 1.5 277: */ 278: public long getBytesWritten() 279: { 280: return totalOut; 281: } 282: 283: /** 284: * Inflates the compressed stream to the output buffer. If this 285: * returns 0, you should check, whether needsDictionary(), 286: * needsInput() or finished() returns true, to determine why no 287: * further output is produced. 288: * @param buf the output buffer. 289: * @return the number of bytes written to the buffer, 0 if no further 290: * output can be produced. 291: * @exception DataFormatException if deflated stream is invalid. 292: * @exception IllegalArgumentException if buf has length 0. 293: */ 294: public int inflate (byte[] buf) throws DataFormatException 295: { 296: return inflate (buf, 0, buf.length); 297: } 298: 299: /** 300: * Inflates the compressed stream to the output buffer. If this 301: * returns 0, you should check, whether needsDictionary(), 302: * needsInput() or finished() returns true, to determine why no 303: * further output is produced. 304: * @param buf the output buffer. 305: * @param off the offset into buffer where the output should start. 306: * @param len the maximum length of the output. 307: * @return the number of bytes written to the buffer, 0 if no further 308: * output can be produced. 309: * @exception DataFormatException if deflated stream is invalid. 310: * @exception IndexOutOfBoundsException if the off and/or len are wrong. 311: */ 312: public int inflate (byte[] buf, int off, int len) throws DataFormatException 313: { 314: /* Special case: len may be zero */ 315: if (len == 0) 316: return 0; 317: /* Check for correct buff, off, len triple */ 318: if (0 > off || off > off + len || off + len > buf.length) 319: throw new ArrayIndexOutOfBoundsException(); 320: int count = 0; 321: int more; 322: do 323: { 324: if (mode != DECODE_CHKSUM) 325: { 326: /* Don't give away any output, if we are waiting for the 327: * checksum in the input stream. 328: * 329: * With this trick we have always: 330: * needsInput() and not finished() 331: * implies more output can be produced. 332: */ 333: more = outputWindow.copyOutput(buf, off, len); 334: adler.update(buf, off, more); 335: off += more; 336: count += more; 337: totalOut += more; 338: len -= more; 339: if (len == 0) 340: return count; 341: } 342: } 343: while (decode() || (outputWindow.getAvailable() > 0 344: && mode != DECODE_CHKSUM)); 345: return count; 346: } 347: 348: /** 349: * Returns true, if a preset dictionary is needed to inflate the input. 350: */ 351: public boolean needsDictionary () 352: { 353: return mode == DECODE_DICT && neededBits == 0; 354: } 355: 356: /** 357: * Returns true, if the input buffer is empty. 358: * You should then call setInput(). <br> 359: * 360: * <em>NOTE</em>: This method also returns true when the stream is finished. 361: */ 362: public boolean needsInput () 363: { 364: return input.needsInput (); 365: } 366: 367: /** 368: * Resets the inflater so that a new stream can be decompressed. All 369: * pending input and output will be discarded. 370: */ 371: public void reset () 372: { 373: mode = nowrap ? DECODE_BLOCKS : DECODE_HEADER; 374: totalIn = totalOut = 0; 375: input.reset(); 376: outputWindow.reset(); 377: dynHeader = null; 378: litlenTree = null; 379: distTree = null; 380: isLastBlock = false; 381: adler.reset(); 382: } 383: 384: /** 385: * Sets the preset dictionary. This should only be called, if 386: * needsDictionary() returns true and it should set the same 387: * dictionary, that was used for deflating. The getAdler() 388: * function returns the checksum of the dictionary needed. 389: * @param buffer the dictionary. 390: * @exception IllegalStateException if no dictionary is needed. 391: * @exception IllegalArgumentException if the dictionary checksum is 392: * wrong. 393: */ 394: public void setDictionary (byte[] buffer) 395: { 396: setDictionary(buffer, 0, buffer.length); 397: } 398: 399: /** 400: * Sets the preset dictionary. This should only be called, if 401: * needsDictionary() returns true and it should set the same 402: * dictionary, that was used for deflating. The getAdler() 403: * function returns the checksum of the dictionary needed. 404: * @param buffer the dictionary. 405: * @param off the offset into buffer where the dictionary starts. 406: * @param len the length of the dictionary. 407: * @exception IllegalStateException if no dictionary is needed. 408: * @exception IllegalArgumentException if the dictionary checksum is 409: * wrong. 410: * @exception IndexOutOfBoundsException if the off and/or len are wrong. 411: */ 412: public void setDictionary (byte[] buffer, int off, int len) 413: { 414: if (!needsDictionary()) 415: throw new IllegalStateException(); 416: 417: adler.update(buffer, off, len); 418: if ((int) adler.getValue() != readAdler) 419: throw new IllegalArgumentException("Wrong adler checksum"); 420: adler.reset(); 421: outputWindow.copyDict(buffer, off, len); 422: mode = DECODE_BLOCKS; 423: } 424: 425: /** 426: * Sets the input. This should only be called, if needsInput() 427: * returns true. 428: * @param buf the input. 429: * @exception IllegalStateException if no input is needed. 430: */ 431: public void setInput (byte[] buf) 432: { 433: setInput (buf, 0, buf.length); 434: } 435: 436: /** 437: * Sets the input. This should only be called, if needsInput() 438: * returns true. 439: * @param buf the input. 440: * @param off the offset into buffer where the input starts. 441: * @param len the length of the input. 442: * @exception IllegalStateException if no input is needed. 443: * @exception IndexOutOfBoundsException if the off and/or len are wrong. 444: */ 445: public void setInput (byte[] buf, int off, int len) 446: { 447: input.setInput (buf, off, len); 448: totalIn += len; 449: } 450: 451: /** 452: * Decodes the deflate header. 453: * @return false if more input is needed. 454: * @exception DataFormatException if header is invalid. 455: */ 456: private boolean decodeHeader () throws DataFormatException 457: { 458: int header = input.peekBits(16); 459: if (header < 0) 460: return false; 461: input.dropBits(16); 462: 463: /* The header is written in "wrong" byte order */ 464: header = ((header << 8) | (header >> 8)) & 0xffff; 465: if (header % 31 != 0) 466: throw new DataFormatException("Header checksum illegal"); 467: 468: if ((header & 0x0f00) != (Deflater.DEFLATED << 8)) 469: throw new DataFormatException("Compression Method unknown"); 470: 471: /* Maximum size of the backwards window in bits. 472: * We currently ignore this, but we could use it to make the 473: * inflater window more space efficient. On the other hand the 474: * full window (15 bits) is needed most times, anyway. 475: int max_wbits = ((header & 0x7000) >> 12) + 8; 476: */ 477: 478: if ((header & 0x0020) == 0) // Dictionary flag? 479: { 480: mode = DECODE_BLOCKS; 481: } 482: else 483: { 484: mode = DECODE_DICT; 485: neededBits = 32; 486: } 487: return true; 488: } 489: 490: /** 491: * Decodes the dictionary checksum after the deflate header. 492: * @return false if more input is needed. 493: */ 494: private boolean decodeDict () 495: { 496: while (neededBits > 0) 497: { 498: int dictByte = input.peekBits(8); 499: if (dictByte < 0) 500: return false; 501: input.dropBits(8); 502: readAdler = (readAdler << 8) | dictByte; 503: neededBits -= 8; 504: } 505: return false; 506: } 507: 508: /** 509: * Decodes the huffman encoded symbols in the input stream. 510: * @return false if more input is needed, true if output window is 511: * full or the current block ends. 512: * @exception DataFormatException if deflated stream is invalid. 513: */ 514: private boolean decodeHuffman () throws DataFormatException 515: { 516: int free = outputWindow.getFreeSpace(); 517: while (free >= 258) 518: { 519: int symbol; 520: switch (mode) 521: { 522: case DECODE_HUFFMAN: 523: /* This is the inner loop so it is optimized a bit */ 524: while (((symbol = litlenTree.getSymbol(input)) & ~0xff) == 0) 525: { 526: outputWindow.write(symbol); 527: if (--free < 258) 528: return true; 529: } 530: if (symbol < 257) 531: { 532: if (symbol < 0) 533: return false; 534: else 535: { 536: /* symbol == 256: end of block */ 537: distTree = null; 538: litlenTree = null; 539: mode = DECODE_BLOCKS; 540: return true; 541: } 542: } 543: 544: try 545: { 546: repLength = CPLENS[symbol - 257]; 547: neededBits = CPLEXT[symbol - 257]; 548: } 549: catch (ArrayIndexOutOfBoundsException ex) 550: { 551: throw new DataFormatException("Illegal rep length code"); 552: } 553: /* fall through */ 554: case DECODE_HUFFMAN_LENBITS: 555: if (neededBits > 0) 556: { 557: mode = DECODE_HUFFMAN_LENBITS; 558: int i = input.peekBits(neededBits); 559: if (i < 0) 560: return false; 561: input.dropBits(neededBits); 562: repLength += i; 563: } 564: mode = DECODE_HUFFMAN_DIST; 565: /* fall through */ 566: case DECODE_HUFFMAN_DIST: 567: symbol = distTree.getSymbol(input); 568: if (symbol < 0) 569: return false; 570: try 571: { 572: repDist = CPDIST[symbol]; 573: neededBits = CPDEXT[symbol]; 574: } 575: catch (ArrayIndexOutOfBoundsException ex) 576: { 577: throw new DataFormatException("Illegal rep dist code"); 578: } 579: /* fall through */ 580: case DECODE_HUFFMAN_DISTBITS: 581: if (neededBits > 0) 582: { 583: mode = DECODE_HUFFMAN_DISTBITS; 584: int i = input.peekBits(neededBits); 585: if (i < 0) 586: return false; 587: input.dropBits(neededBits); 588: repDist += i; 589: } 590: outputWindow.repeat(repLength, repDist); 591: free -= repLength; 592: mode = DECODE_HUFFMAN; 593: break; 594: default: 595: throw new IllegalStateException(); 596: } 597: } 598: return true; 599: } 600: 601: /** 602: * Decodes the adler checksum after the deflate stream. 603: * @return false if more input is needed. 604: * @exception DataFormatException if checksum doesn't match. 605: */ 606: private boolean decodeChksum () throws DataFormatException 607: { 608: while (neededBits > 0) 609: { 610: int chkByte = input.peekBits(8); 611: if (chkByte < 0) 612: return false; 613: input.dropBits(8); 614: readAdler = (readAdler << 8) | chkByte; 615: neededBits -= 8; 616: } 617: if ((int) adler.getValue() != readAdler) 618: throw new DataFormatException("Adler chksum doesn't match: " 619: +Integer.toHexString((int)adler.getValue()) 620: +" vs. "+Integer.toHexString(readAdler)); 621: mode = FINISHED; 622: return false; 623: } 624: 625: /** 626: * Decodes the deflated stream. 627: * @return false if more input is needed, or if finished. 628: * @exception DataFormatException if deflated stream is invalid. 629: */ 630: private boolean decode () throws DataFormatException 631: { 632: switch (mode) 633: { 634: case DECODE_HEADER: 635: return decodeHeader(); 636: case DECODE_DICT: 637: return decodeDict(); 638: case DECODE_CHKSUM: 639: return decodeChksum(); 640: 641: case DECODE_BLOCKS: 642: if (isLastBlock) 643: { 644: if (nowrap) 645: { 646: mode = FINISHED; 647: return false; 648: } 649: else 650: { 651: input.skipToByteBoundary(); 652: neededBits = 32; 653: mode = DECODE_CHKSUM; 654: return true; 655: } 656: } 657: 658: int type = input.peekBits(3); 659: if (type < 0) 660: return false; 661: input.dropBits(3); 662: 663: if ((type & 1) != 0) 664: isLastBlock = true; 665: switch (type >> 1) 666: { 667: case DeflaterConstants.STORED_BLOCK: 668: input.skipToByteBoundary(); 669: mode = DECODE_STORED_LEN1; 670: break; 671: case DeflaterConstants.STATIC_TREES: 672: litlenTree = InflaterHuffmanTree.defLitLenTree; 673: distTree = InflaterHuffmanTree.defDistTree; 674: mode = DECODE_HUFFMAN; 675: break; 676: case DeflaterConstants.DYN_TREES: 677: dynHeader = new InflaterDynHeader(); 678: mode = DECODE_DYN_HEADER; 679: break; 680: default: 681: throw new DataFormatException("Unknown block type "+type); 682: } 683: return true; 684: 685: case DECODE_STORED_LEN1: 686: { 687: if ((uncomprLen = input.peekBits(16)) < 0) 688: return false; 689: input.dropBits(16); 690: mode = DECODE_STORED_LEN2; 691: } 692: /* fall through */ 693: case DECODE_STORED_LEN2: 694: { 695: int nlen = input.peekBits(16); 696: if (nlen < 0) 697: return false; 698: input.dropBits(16); 699: if (nlen != (uncomprLen ^ 0xffff)) 700: throw new DataFormatException("broken uncompressed block"); 701: mode = DECODE_STORED; 702: } 703: /* fall through */ 704: case DECODE_STORED: 705: { 706: int more = outputWindow.copyStored(input, uncomprLen); 707: uncomprLen -= more; 708: if (uncomprLen == 0) 709: { 710: mode = DECODE_BLOCKS; 711: return true; 712: } 713: return !input.needsInput(); 714: } 715: 716: case DECODE_DYN_HEADER: 717: if (!dynHeader.decode(input)) 718: return false; 719: litlenTree = dynHeader.buildLitLenTree(); 720: distTree = dynHeader.buildDistTree(); 721: mode = DECODE_HUFFMAN; 722: /* fall through */ 723: case DECODE_HUFFMAN: 724: case DECODE_HUFFMAN_LENBITS: 725: case DECODE_HUFFMAN_DIST: 726: case DECODE_HUFFMAN_DISTBITS: 727: return decodeHuffman(); 728: case FINISHED: 729: return false; 730: default: 731: throw new IllegalStateException(); 732: } 733: } 734: }
GNU Classpath (0.98) |