001/* 002 * Licensed to the Apache Software Foundation (ASF) under one 003 * or more contributor license agreements. See the NOTICE file 004 * distributed with this work for additional information 005 * regarding copyright ownership. The ASF licenses this file 006 * to you under the Apache License, Version 2.0 (the 007 * "License"); you may not use this file except in compliance 008 * with the License. You may obtain a copy of the License at 009 * 010 * http://www.apache.org/licenses/LICENSE-2.0 011 * 012 * Unless required by applicable law or agreed to in writing, 013 * software distributed under the License is distributed on an 014 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY 015 * KIND, either express or implied. See the License for the 016 * specific language governing permissions and limitations 017 * under the License. 018 */ 019package org.apache.commons.compress.compressors.lz77support; 020 021import java.io.IOException; 022import java.io.InputStream; 023import java.util.Arrays; 024 025import org.apache.commons.compress.compressors.CompressorInputStream; 026import org.apache.commons.compress.utils.ByteUtils; 027import org.apache.commons.compress.utils.CountingInputStream; 028import org.apache.commons.compress.utils.IOUtils; 029import org.apache.commons.compress.utils.InputStreamStatistics; 030 031/** 032 * Encapsulates code common to LZ77 decompressors. 033 * 034 * <p>Assumes the stream consists of blocks of literal data and 035 * back-references (called copies) in any order. Of course the first 036 * block must be a literal block for the scheme to work - unless the 037 * {@link #prefill prefill} method has been used to provide initial 038 * data that is never returned by {@link #read read} but only used for 039 * back-references.</p> 040 * 041 * <p>Subclasses must override the three-arg {@link #read read} method 042 * as the no-arg version delegates to it and the default 043 * implementation delegates to the no-arg version, leading to infinite 044 * mutual recursion and a {@code StackOverflowError} otherwise.</p> 045 * 046 * <p>The contract for subclasses' {@code read} implementation is:</p> 047 * <ul> 048 * 049 * <li>keep track of the current state of the stream. Is it inside a 050 * literal block or a back-reference or in-between blocks?</li> 051 * 052 * <li>Use {@link #readOneByte} to access the underlying stream 053 * directly.</li> 054 * 055 * <li>If a new literal block starts, use {@link #startLiteral} to 056 * tell this class about it and read the literal data using {@link 057 * #readLiteral} until it returns {@code 0}. {@link 058 * #hasMoreDataInBlock} will return {@code false} before the next 059 * call to {@link #readLiteral} would return {@code 0}.</li> 060 * 061 * <li>If a new back-reference starts, use {@link #startBackReference} to 062 * tell this class about it and read the literal data using {@link 063 * #readBackReference} until it returns {@code 0}. {@link 064 * #hasMoreDataInBlock} will return {@code false} before the next 065 * call to {@link #readBackReference} would return {@code 0}.</li> 066 * 067 * <li>If the end of the stream has been reached, return {@code -1} 068 * as this class' methods will never do so themselves.</li> 069 * 070 * </ul> 071 * 072 * <p>{@link #readOneByte} and {@link #readLiteral} update the counter 073 * for bytes read.</p> 074 * 075 * @since 1.14 076 */ 077public abstract class AbstractLZ77CompressorInputStream extends CompressorInputStream 078 implements InputStreamStatistics { 079 080 /** Size of the window - must be bigger than the biggest offset expected. */ 081 private final int windowSize; 082 083 /** 084 * Buffer to write decompressed bytes to for back-references, will 085 * be three times windowSize big. 086 * 087 * <p>Three times so we can slide the whole buffer a windowSize to 088 * the left once we've read twice windowSize and still have enough 089 * data inside of it to satisfy back-references.</p> 090 */ 091 private final byte[] buf; 092 093 /** One behind the index of the last byte in the buffer that was written, i.e. the next position to write to */ 094 private int writeIndex; 095 096 /** Index of the next byte to be read. */ 097 private int readIndex; 098 099 /** The underlying stream to read compressed data from */ 100 private final CountingInputStream in; 101 102 /** Number of bytes still to be read from the current literal or back-reference. */ 103 private long bytesRemaining; 104 105 /** Offset of the current back-reference. */ 106 private int backReferenceOffset; 107 108 /** uncompressed size */ 109 private int size; 110 111 // used in no-arg read method 112 private final byte[] oneByte = new byte[1]; 113 114 /** 115 * Supplier that delegates to {@link #readOneByte}. 116 */ 117 protected final ByteUtils.ByteSupplier supplier = this::readOneByte; 118 119 /** 120 * Creates a new LZ77 input stream. 121 * 122 * @param is 123 * An InputStream to read compressed data from 124 * @param windowSize 125 * Size of the window kept for back-references, must be bigger than the biggest offset expected. 126 * 127 * @throws IllegalArgumentException if windowSize is not bigger than 0 128 */ 129 public AbstractLZ77CompressorInputStream(final InputStream is, final int windowSize) { 130 this.in = new CountingInputStream(is); 131 if (windowSize <= 0) { 132 throw new IllegalArgumentException("windowSize must be bigger than 0"); 133 } 134 this.windowSize = windowSize; 135 buf = new byte[3 * windowSize]; 136 writeIndex = readIndex = 0; 137 bytesRemaining = 0; 138 } 139 140 /** {@inheritDoc} */ 141 @Override 142 public int available() { 143 return writeIndex - readIndex; 144 } 145 146 /** {@inheritDoc} */ 147 @Override 148 public void close() throws IOException { 149 in.close(); 150 } 151 152 /** 153 * @since 1.17 154 */ 155 @Override 156 public long getCompressedCount() { 157 return in.getBytesRead(); 158 } 159 160 /** 161 * Gets the uncompressed size of the stream 162 * 163 * @return the uncompressed size 164 */ 165 public int getSize() { 166 return size; 167 } 168 169 /** 170 * Is there still data remaining inside the current block? 171 * @return true if there is still data remaining inside the current block. 172 */ 173 protected final boolean hasMoreDataInBlock() { 174 return bytesRemaining > 0; 175 } 176 177 /** 178 * Adds some initial data to fill the window with. 179 * 180 * <p>This is used if the stream has been cut into blocks and 181 * back-references of one block may refer to data of the previous 182 * block(s). One such example is the LZ4 frame format using block 183 * dependency.</p> 184 * 185 * @param data the data to fill the window with. 186 * @throws IllegalStateException if the stream has already started to read data 187 */ 188 public void prefill(final byte[] data) { 189 if (writeIndex != 0) { 190 throw new IllegalStateException("The stream has already been read from, can't prefill anymore"); 191 } 192 // we don't need more data than the big offset could refer to, so cap it 193 final int len = Math.min(windowSize, data.length); 194 // we need the last data as we are dealing with *back*-references 195 System.arraycopy(data, data.length - len, buf, 0, len); 196 writeIndex += len; 197 readIndex += len; 198 } 199 200 /** {@inheritDoc} */ 201 @Override 202 public int read() throws IOException { 203 return read(oneByte, 0, 1) == -1 ? -1 : oneByte[0] & 0xFF; 204 } 205 206 /** 207 * Reads data from the current back-reference. 208 * @param b buffer to write data to 209 * @param off offset to start writing to 210 * @param len maximum amount of data to read 211 * @return number of bytes read, may be 0. Will never return -1 as 212 * EOF-detection is the responsibility of the subclass 213 * @throws NullPointerException if {@code b} is null 214 * @throws IndexOutOfBoundsException if {@code off} is 215 * negative, {@code len} is negative, or {@code len} is 216 * greater than {@code b.length - off} 217 */ 218 protected final int readBackReference(final byte[] b, final int off, final int len) { 219 final int avail = available(); 220 if (len > avail) { 221 tryToCopy(len - avail); 222 } 223 return readFromBuffer(b, off, len); 224 } 225 226 private int readFromBuffer(final byte[] b, final int off, final int len) { 227 final int readable = Math.min(len, available()); 228 if (readable > 0) { 229 System.arraycopy(buf, readIndex, b, off, readable); 230 readIndex += readable; 231 if (readIndex > 2 * windowSize) { 232 slideBuffer(); 233 } 234 } 235 size += readable; 236 return readable; 237 } 238 239 /** 240 * Reads data from the current literal block. 241 * @param b buffer to write data to 242 * @param off offset to start writing to 243 * @param len maximum amount of data to read 244 * @return number of bytes read, may be 0. Will never return -1 as 245 * EOF-detection is the responsibility of the subclass 246 * @throws IOException if the underlying stream throws or signals 247 * an EOF before the amount of data promised for the block have 248 * been read 249 * @throws NullPointerException if {@code b} is null 250 * @throws IndexOutOfBoundsException if {@code off} is 251 * negative, {@code len} is negative, or {@code len} is 252 * greater than {@code b.length - off} 253 */ 254 protected final int readLiteral(final byte[] b, final int off, final int len) throws IOException { 255 final int avail = available(); 256 if (len > avail) { 257 tryToReadLiteral(len - avail); 258 } 259 return readFromBuffer(b, off, len); 260 } 261 262 /** 263 * Reads a single byte from the real input stream and ensures the data is accounted for. 264 * 265 * @return the byte read as value between 0 and 255 or -1 if EOF has been reached. 266 * @throws IOException if the underlying stream throws 267 */ 268 protected final int readOneByte() throws IOException { 269 final int b = in.read(); 270 if (b != -1) { 271 count(1); 272 return b & 0xFF; 273 } 274 return -1; 275 } 276 277 private void slideBuffer() { 278 System.arraycopy(buf, windowSize, buf, 0, windowSize * 2); 279 writeIndex -= windowSize; 280 readIndex -= windowSize; 281 } 282 283 /** 284 * Used by subclasses to signal the next block contains a back-reference with the given coordinates. 285 * @param offset the offset of the back-reference 286 * @param length the length of the back-reference 287 * @throws IllegalArgumentException if offset not bigger than 0 or 288 * bigger than the number of bytes available for back-references 289 * or if length is negative 290 */ 291 protected final void startBackReference(final int offset, final long length) { 292 if (offset <= 0 || offset > writeIndex) { 293 throw new IllegalArgumentException("offset must be bigger than 0 but not bigger than the number" 294 + " of bytes available for back-references"); 295 } 296 if (length < 0) { 297 throw new IllegalArgumentException("length must not be negative"); 298 } 299 backReferenceOffset = offset; 300 bytesRemaining = length; 301 } 302 303 /** 304 * Used by subclasses to signal the next block contains the given 305 * amount of literal data. 306 * @param length the length of the block 307 * @throws IllegalArgumentException if length is negative 308 */ 309 protected final void startLiteral(final long length) { 310 if (length < 0) { 311 throw new IllegalArgumentException("length must not be negative"); 312 } 313 bytesRemaining = length; 314 } 315 316 private void tryToCopy(final int bytesToCopy) { 317 // this will fit into the buffer without sliding and not 318 // require more than is available inside the back-reference 319 final int copy = Math.min((int) Math.min(bytesToCopy, bytesRemaining), 320 buf.length - writeIndex); 321 if (copy == 0) { 322 // NOP 323 } else if (backReferenceOffset == 1) { // pretty common special case 324 final byte last = buf[writeIndex - 1]; 325 Arrays.fill(buf, writeIndex, writeIndex + copy, last); 326 writeIndex += copy; 327 } else if (copy < backReferenceOffset) { 328 System.arraycopy(buf, writeIndex - backReferenceOffset, buf, writeIndex, copy); 329 writeIndex += copy; 330 } else { 331 // back-reference overlaps with the bytes created from it 332 // like go back two bytes and then copy six (by copying 333 // the last two bytes three time). 334 final int fullRots = copy / backReferenceOffset; 335 for (int i = 0; i < fullRots; i++) { 336 System.arraycopy(buf, writeIndex - backReferenceOffset, buf, writeIndex, backReferenceOffset); 337 writeIndex += backReferenceOffset; 338 } 339 340 final int pad = copy - backReferenceOffset * fullRots; 341 if (pad > 0) { 342 System.arraycopy(buf, writeIndex - backReferenceOffset, buf, writeIndex, pad); 343 writeIndex += pad; 344 } 345 } 346 bytesRemaining -= copy; 347 } 348 349 private void tryToReadLiteral(final int bytesToRead) throws IOException { 350 // min of "what is still inside the literal", "what does the user want" and "how much can fit into the buffer" 351 final int reallyTryToRead = Math.min((int) Math.min(bytesToRead, bytesRemaining), 352 buf.length - writeIndex); 353 final int bytesRead = reallyTryToRead > 0 354 ? IOUtils.readFully(in, buf, writeIndex, reallyTryToRead) 355 : 0 /* happens for bytesRemaining == 0 */; 356 count(bytesRead); 357 if (reallyTryToRead != bytesRead) { 358 throw new IOException("Premature end of stream reading literal"); 359 } 360 writeIndex += reallyTryToRead; 361 bytesRemaining -= reallyTryToRead; 362 } 363}