| GNU Classpath (0.95) | |
| 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: @Deprecated 250: public int getTotalIn() 251: { 252: return (int) (totalIn - getRemaining()); 253: } 254: 255: /** 256: * Gets the total number of processed compressed input bytes. 257: * @return the total number of bytes of processed input bytes. 258: * @since 1.5 259: */ 260: public long getBytesRead() 261: { 262: return totalIn - getRemaining(); 263: } 264: 265: /** 266: * Gets the total number of output bytes returned by inflate(). 267: * @return the total number of output bytes. 268: */ 269: @Deprecated 270: public int getTotalOut() 271: { 272: return (int) totalOut; 273: } 274: 275: /** 276: * Gets the total number of output bytes returned by inflate(). 277: * @return the total number of output bytes. 278: * @since 1.5 279: */ 280: public long getBytesWritten() 281: { 282: return totalOut; 283: } 284: 285: /** 286: * Inflates the compressed stream to the output buffer. If this 287: * returns 0, you should check, whether needsDictionary(), 288: * needsInput() or finished() returns true, to determine why no 289: * further output is produced. 290: * @param buf the output buffer. 291: * @return the number of bytes written to the buffer, 0 if no further 292: * output can be produced. 293: * @exception DataFormatException if deflated stream is invalid. 294: * @exception IllegalArgumentException if buf has length 0. 295: */ 296: public int inflate (byte[] buf) throws DataFormatException 297: { 298: return inflate (buf, 0, buf.length); 299: } 300: 301: /** 302: * Inflates the compressed stream to the output buffer. If this 303: * returns 0, you should check, whether needsDictionary(), 304: * needsInput() or finished() returns true, to determine why no 305: * further output is produced. 306: * @param buf the output buffer. 307: * @param off the offset into buffer where the output should start. 308: * @param len the maximum length of the output. 309: * @return the number of bytes written to the buffer, 0 if no further 310: * output can be produced. 311: * @exception DataFormatException if deflated stream is invalid. 312: * @exception IndexOutOfBoundsException if the off and/or len are wrong. 313: */ 314: public int inflate (byte[] buf, int off, int len) throws DataFormatException 315: { 316: /* Special case: len may be zero */ 317: if (len == 0) 318: return 0; 319: /* Check for correct buff, off, len triple */ 320: if (0 > off || off > off + len || off + len > buf.length) 321: throw new ArrayIndexOutOfBoundsException(); 322: int count = 0; 323: int more; 324: do 325: { 326: if (mode != DECODE_CHKSUM) 327: { 328: /* Don't give away any output, if we are waiting for the 329: * checksum in the input stream. 330: * 331: * With this trick we have always: 332: * needsInput() and not finished() 333: * implies more output can be produced. 334: */ 335: more = outputWindow.copyOutput(buf, off, len); 336: adler.update(buf, off, more); 337: off += more; 338: count += more; 339: totalOut += more; 340: len -= more; 341: if (len == 0) 342: return count; 343: } 344: } 345: while (decode() || (outputWindow.getAvailable() > 0 346: && mode != DECODE_CHKSUM)); 347: return count; 348: } 349: 350: /** 351: * Returns true, if a preset dictionary is needed to inflate the input. 352: */ 353: public boolean needsDictionary () 354: { 355: return mode == DECODE_DICT && neededBits == 0; 356: } 357: 358: /** 359: * Returns true, if the input buffer is empty. 360: * You should then call setInput(). <br> 361: * 362: * <em>NOTE</em>: This method also returns true when the stream is finished. 363: */ 364: public boolean needsInput () 365: { 366: return input.needsInput (); 367: } 368: 369: /** 370: * Resets the inflater so that a new stream can be decompressed. All 371: * pending input and output will be discarded. 372: */ 373: public void reset () 374: { 375: mode = nowrap ? DECODE_BLOCKS : DECODE_HEADER; 376: totalIn = totalOut = 0; 377: input.reset(); 378: outputWindow.reset(); 379: dynHeader = null; 380: litlenTree = null; 381: distTree = null; 382: isLastBlock = false; 383: adler.reset(); 384: } 385: 386: /** 387: * Sets the preset dictionary. This should only be called, if 388: * needsDictionary() returns true and it should set the same 389: * dictionary, that was used for deflating. The getAdler() 390: * function returns the checksum of the dictionary needed. 391: * @param buffer the dictionary. 392: * @exception IllegalStateException if no dictionary is needed. 393: * @exception IllegalArgumentException if the dictionary checksum is 394: * wrong. 395: */ 396: public void setDictionary (byte[] buffer) 397: { 398: setDictionary(buffer, 0, buffer.length); 399: } 400: 401: /** 402: * Sets the preset dictionary. This should only be called, if 403: * needsDictionary() returns true and it should set the same 404: * dictionary, that was used for deflating. The getAdler() 405: * function returns the checksum of the dictionary needed. 406: * @param buffer the dictionary. 407: * @param off the offset into buffer where the dictionary starts. 408: * @param len the length of the dictionary. 409: * @exception IllegalStateException if no dictionary is needed. 410: * @exception IllegalArgumentException if the dictionary checksum is 411: * wrong. 412: * @exception IndexOutOfBoundsException if the off and/or len are wrong. 413: */ 414: public void setDictionary (byte[] buffer, int off, int len) 415: { 416: if (!needsDictionary()) 417: throw new IllegalStateException(); 418: 419: adler.update(buffer, off, len); 420: if ((int) adler.getValue() != readAdler) 421: throw new IllegalArgumentException("Wrong adler checksum"); 422: adler.reset(); 423: outputWindow.copyDict(buffer, off, len); 424: mode = DECODE_BLOCKS; 425: } 426: 427: /** 428: * Sets the input. This should only be called, if needsInput() 429: * returns true. 430: * @param buf the input. 431: * @exception IllegalStateException if no input is needed. 432: */ 433: public void setInput (byte[] buf) 434: { 435: setInput (buf, 0, buf.length); 436: } 437: 438: /** 439: * Sets the input. This should only be called, if needsInput() 440: * returns true. 441: * @param buf the input. 442: * @param off the offset into buffer where the input starts. 443: * @param len the length of the input. 444: * @exception IllegalStateException if no input is needed. 445: * @exception IndexOutOfBoundsException if the off and/or len are wrong. 446: */ 447: public void setInput (byte[] buf, int off, int len) 448: { 449: input.setInput (buf, off, len); 450: totalIn += len; 451: } 452: 453: /** 454: * Decodes the deflate header. 455: * @return false if more input is needed. 456: * @exception DataFormatException if header is invalid. 457: */ 458: private boolean decodeHeader () throws DataFormatException 459: { 460: int header = input.peekBits(16); 461: if (header < 0) 462: return false; 463: input.dropBits(16); 464: 465: /* The header is written in "wrong" byte order */ 466: header = ((header << 8) | (header >> 8)) & 0xffff; 467: if (header % 31 != 0) 468: throw new DataFormatException("Header checksum illegal"); 469: 470: if ((header & 0x0f00) != (Deflater.DEFLATED << 8)) 471: throw new DataFormatException("Compression Method unknown"); 472: 473: /* Maximum size of the backwards window in bits. 474: * We currently ignore this, but we could use it to make the 475: * inflater window more space efficient. On the other hand the 476: * full window (15 bits) is needed most times, anyway. 477: int max_wbits = ((header & 0x7000) >> 12) + 8; 478: */ 479: 480: if ((header & 0x0020) == 0) // Dictionary flag? 481: { 482: mode = DECODE_BLOCKS; 483: } 484: else 485: { 486: mode = DECODE_DICT; 487: neededBits = 32; 488: } 489: return true; 490: } 491: 492: /** 493: * Decodes the dictionary checksum after the deflate header. 494: * @return false if more input is needed. 495: */ 496: private boolean decodeDict () 497: { 498: while (neededBits > 0) 499: { 500: int dictByte = input.peekBits(8); 501: if (dictByte < 0) 502: return false; 503: input.dropBits(8); 504: readAdler = (readAdler << 8) | dictByte; 505: neededBits -= 8; 506: } 507: return false; 508: } 509: 510: /** 511: * Decodes the huffman encoded symbols in the input stream. 512: * @return false if more input is needed, true if output window is 513: * full or the current block ends. 514: * @exception DataFormatException if deflated stream is invalid. 515: */ 516: private boolean decodeHuffman () throws DataFormatException 517: { 518: int free = outputWindow.getFreeSpace(); 519: while (free >= 258) 520: { 521: int symbol; 522: switch (mode) 523: { 524: case DECODE_HUFFMAN: 525: /* This is the inner loop so it is optimized a bit */ 526: while (((symbol = litlenTree.getSymbol(input)) & ~0xff) == 0) 527: { 528: outputWindow.write(symbol); 529: if (--free < 258) 530: return true; 531: } 532: if (symbol < 257) 533: { 534: if (symbol < 0) 535: return false; 536: else 537: { 538: /* symbol == 256: end of block */ 539: distTree = null; 540: litlenTree = null; 541: mode = DECODE_BLOCKS; 542: return true; 543: } 544: } 545: 546: try 547: { 548: repLength = CPLENS[symbol - 257]; 549: neededBits = CPLEXT[symbol - 257]; 550: } 551: catch (ArrayIndexOutOfBoundsException ex) 552: { 553: throw new DataFormatException("Illegal rep length code"); 554: } 555: /* fall through */ 556: case DECODE_HUFFMAN_LENBITS: 557: if (neededBits > 0) 558: { 559: mode = DECODE_HUFFMAN_LENBITS; 560: int i = input.peekBits(neededBits); 561: if (i < 0) 562: return false; 563: input.dropBits(neededBits); 564: repLength += i; 565: } 566: mode = DECODE_HUFFMAN_DIST; 567: /* fall through */ 568: case DECODE_HUFFMAN_DIST: 569: symbol = distTree.getSymbol(input); 570: if (symbol < 0) 571: return false; 572: try 573: { 574: repDist = CPDIST[symbol]; 575: neededBits = CPDEXT[symbol]; 576: } 577: catch (ArrayIndexOutOfBoundsException ex) 578: { 579: throw new DataFormatException("Illegal rep dist code"); 580: } 581: /* fall through */ 582: case DECODE_HUFFMAN_DISTBITS: 583: if (neededBits > 0) 584: { 585: mode = DECODE_HUFFMAN_DISTBITS; 586: int i = input.peekBits(neededBits); 587: if (i < 0) 588: return false; 589: input.dropBits(neededBits); 590: repDist += i; 591: } 592: outputWindow.repeat(repLength, repDist); 593: free -= repLength; 594: mode = DECODE_HUFFMAN; 595: break; 596: default: 597: throw new IllegalStateException(); 598: } 599: } 600: return true; 601: } 602: 603: /** 604: * Decodes the adler checksum after the deflate stream. 605: * @return false if more input is needed. 606: * @exception DataFormatException if checksum doesn't match. 607: */ 608: private boolean decodeChksum () throws DataFormatException 609: { 610: while (neededBits > 0) 611: { 612: int chkByte = input.peekBits(8); 613: if (chkByte < 0) 614: return false; 615: input.dropBits(8); 616: readAdler = (readAdler << 8) | chkByte; 617: neededBits -= 8; 618: } 619: if ((int) adler.getValue() != readAdler) 620: throw new DataFormatException("Adler chksum doesn't match: " 621: +Integer.toHexString((int)adler.getValue()) 622: +" vs. "+Integer.toHexString(readAdler)); 623: mode = FINISHED; 624: return false; 625: } 626: 627: /** 628: * Decodes the deflated stream. 629: * @return false if more input is needed, or if finished. 630: * @exception DataFormatException if deflated stream is invalid. 631: */ 632: private boolean decode () throws DataFormatException 633: { 634: switch (mode) 635: { 636: case DECODE_HEADER: 637: return decodeHeader(); 638: case DECODE_DICT: 639: return decodeDict(); 640: case DECODE_CHKSUM: 641: return decodeChksum(); 642: 643: case DECODE_BLOCKS: 644: if (isLastBlock) 645: { 646: if (nowrap) 647: { 648: mode = FINISHED; 649: return false; 650: } 651: else 652: { 653: input.skipToByteBoundary(); 654: neededBits = 32; 655: mode = DECODE_CHKSUM; 656: return true; 657: } 658: } 659: 660: int type = input.peekBits(3); 661: if (type < 0) 662: return false; 663: input.dropBits(3); 664: 665: if ((type & 1) != 0) 666: isLastBlock = true; 667: switch (type >> 1) 668: { 669: case DeflaterConstants.STORED_BLOCK: 670: input.skipToByteBoundary(); 671: mode = DECODE_STORED_LEN1; 672: break; 673: case DeflaterConstants.STATIC_TREES: 674: litlenTree = InflaterHuffmanTree.defLitLenTree; 675: distTree = InflaterHuffmanTree.defDistTree; 676: mode = DECODE_HUFFMAN; 677: break; 678: case DeflaterConstants.DYN_TREES: 679: dynHeader = new InflaterDynHeader(); 680: mode = DECODE_DYN_HEADER; 681: break; 682: default: 683: throw new DataFormatException("Unknown block type "+type); 684: } 685: return true; 686: 687: case DECODE_STORED_LEN1: 688: { 689: if ((uncomprLen = input.peekBits(16)) < 0) 690: return false; 691: input.dropBits(16); 692: mode = DECODE_STORED_LEN2; 693: } 694: /* fall through */ 695: case DECODE_STORED_LEN2: 696: { 697: int nlen = input.peekBits(16); 698: if (nlen < 0) 699: return false; 700: input.dropBits(16); 701: if (nlen != (uncomprLen ^ 0xffff)) 702: throw new DataFormatException("broken uncompressed block"); 703: mode = DECODE_STORED; 704: } 705: /* fall through */ 706: case DECODE_STORED: 707: { 708: int more = outputWindow.copyStored(input, uncomprLen); 709: uncomprLen -= more; 710: if (uncomprLen == 0) 711: { 712: mode = DECODE_BLOCKS; 713: return true; 714: } 715: return !input.needsInput(); 716: } 717: 718: case DECODE_DYN_HEADER: 719: if (!dynHeader.decode(input)) 720: return false; 721: litlenTree = dynHeader.buildLitLenTree(); 722: distTree = dynHeader.buildDistTree(); 723: mode = DECODE_HUFFMAN; 724: /* fall through */ 725: case DECODE_HUFFMAN: 726: case DECODE_HUFFMAN_LENBITS: 727: case DECODE_HUFFMAN_DIST: 728: case DECODE_HUFFMAN_DISTBITS: 729: return decodeHuffman(); 730: case FINISHED: 731: return false; 732: default: 733: throw new IllegalStateException(); 734: } 735: } 736: }
| GNU Classpath (0.95) |