1 /* 2 * Licensed to the Apache Software Foundation (ASF) under one 3 * or more contributor license agreements. See the NOTICE file 4 * distributed with this work for additional information 5 * regarding copyright ownership. The ASF licenses this file 6 * to you under the Apache License, Version 2.0 (the 7 * "License"); you may not use this file except in compliance 8 * with the License. You may obtain a copy of the License at 9 * 10 * http://www.apache.org/licenses/LICENSE-2.0 11 * 12 * Unless required by applicable law or agreed to in writing, 13 * software distributed under the License is distributed on an 14 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY 15 * KIND, either express or implied. See the License for the 16 * specific language governing permissions and limitations 17 * under the License. 18 */ 19 20 package org.apache.commons.compress.archivers.zip; 21 22 import org.apache.commons.compress.utils.CountingInputStream; 23 import org.apache.commons.compress.utils.InputStreamStatistics; 24 25 import java.io.IOException; 26 import java.io.InputStream; 27 28 /** 29 * The implode compression method was added to PKZIP 1.01 released in 1989. 30 * It was then dropped from PKZIP 2.0 released in 1993 in favor of the deflate 31 * method. 32 * <p> 33 * The algorithm is described in the ZIP File Format Specification. 34 * 35 * @see <a href="https://www.pkware.com/documents/casestudies/APPNOTE.TXT">ZIP File Format Specification</a> 36 * 37 * @author Emmanuel Bourg 38 * @since 1.7 39 */ 40 class ExplodingInputStream extends InputStream implements InputStreamStatistics { 41 42 /** The underlying stream containing the compressed data */ 43 private final InputStream in; 44 45 /** The stream of bits read from the input stream */ 46 private BitStream bits; 47 48 /** The size of the sliding dictionary (4K or 8K) */ 49 private final int dictionarySize; 50 51 /** The number of Shannon-Fano trees (2 or 3) */ 52 private final int numberOfTrees; 53 54 private final int minimumMatchLength; 55 56 /** The binary tree containing the 256 encoded literals (null when only two trees are used) */ 57 private BinaryTree literalTree; 58 59 /** The binary tree containing the 64 encoded lengths */ 60 private BinaryTree lengthTree; 61 62 /** The binary tree containing the 64 encoded distances */ 63 private BinaryTree distanceTree; 64 65 /** Output buffer holding the decompressed data */ 66 private final CircularBuffer buffer = new CircularBuffer(32 * 1024); 67 68 private long uncompressedCount = 0; 69 70 private long treeSizes = 0; 71 72 /** 73 * Create a new stream decompressing the content of the specified stream 74 * using the explode algorithm. 75 * 76 * @param dictionarySize the size of the sliding dictionary (4096 or 8192) 77 * @param numberOfTrees the number of trees (2 or 3) 78 * @param in the compressed data stream 79 */ 80 public ExplodingInputStream(final int dictionarySize, final int numberOfTrees, final InputStream in) { 81 if (dictionarySize != 4096 && dictionarySize != 8192) { 82 throw new IllegalArgumentException("The dictionary size must be 4096 or 8192"); 83 } 84 if (numberOfTrees != 2 && numberOfTrees != 3) { 85 throw new IllegalArgumentException("The number of trees must be 2 or 3"); 86 } 87 this.dictionarySize = dictionarySize; 88 this.numberOfTrees = numberOfTrees; 89 this.minimumMatchLength = numberOfTrees; 90 this.in = in; 91 } 92 93 /** 94 * Reads the encoded binary trees and prepares the bit stream. 95 * 96 * @throws IOException 97 */ 98 private void init() throws IOException { 99 if (bits == null) { 100 try (CountingInputStream i = new CountingInputStream(in) { 101 @Override 102 public void close() { 103 // we do not want to close in 104 } 105 }) { 106 if (numberOfTrees == 3) { 107 literalTree = BinaryTree.decode(i, 256); 108 } 109 110 lengthTree = BinaryTree.decode(i, 64); 111 distanceTree = BinaryTree.decode(i, 64); 112 treeSizes += i.getBytesRead(); 113 } 114 115 bits = new BitStream(in); 116 } 117 } 118 119 @Override 120 public int read() throws IOException { 121 if (!buffer.available()) { 122 fillBuffer(); 123 } 124 125 final int ret = buffer.get(); 126 if (ret > -1) { 127 uncompressedCount++; 128 } 129 return ret; 130 } 131 132 /** 133 * @since 1.17 134 */ 135 @Override 136 public long getCompressedCount() { 137 return bits.getBytesRead() + treeSizes; 138 } 139 140 /** 141 * @since 1.17 142 */ 143 @Override 144 public long getUncompressedCount() { 145 return uncompressedCount; 146 } 147 148 /** 149 * @since 1.17 150 */ 151 @Override 152 public void close() throws IOException { 153 in.close(); 154 } 155 156 /** 157 * Fill the sliding dictionary with more data. 158 * @throws IOException 159 */ 160 private void fillBuffer() throws IOException { 161 init(); 162 163 final int bit = bits.nextBit(); 164 if (bit == 1) { 165 // literal value 166 int literal; 167 if (literalTree != null) { 168 literal = literalTree.read(bits); 169 } else { 170 literal = bits.nextByte(); 171 } 172 173 if (literal == -1) { 174 // end of stream reached, nothing left to decode 175 return; 176 } 177 178 buffer.put(literal); 179 180 } else if (bit == 0) { 181 // back reference 182 final int distanceLowSize = dictionarySize == 4096 ? 6 : 7; 183 final int distanceLow = (int) bits.nextBits(distanceLowSize); 184 final int distanceHigh = distanceTree.read(bits); 185 if (distanceHigh == -1 && distanceLow <= 0) { 186 // end of stream reached, nothing left to decode 187 return; 188 } 189 final int distance = distanceHigh << distanceLowSize | distanceLow; 190 191 int length = lengthTree.read(bits); 192 if (length == 63) { 193 length += bits.nextBits(8); 194 } 195 length += minimumMatchLength; 196 197 buffer.copy(distance + 1, length); 198 } 199 } 200 201 } 202
