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 IOException if reading fails 128 * @throws IllegalArgumentException if windowSize is not bigger than 0 129 */ 130 public AbstractLZ77CompressorInputStream(final InputStream is, final int windowSize) throws IOException { 131 this.in = new CountingInputStream(is); 132 if (windowSize <= 0) { 133 throw new IllegalArgumentException("windowSize must be bigger than 0"); 134 } 135 this.windowSize = windowSize; 136 buf = new byte[3 * windowSize]; 137 writeIndex = readIndex = 0; 138 bytesRemaining = 0; 139 } 140 141 /** {@inheritDoc} */ 142 @Override 143 public int read() throws IOException { 144 return read(oneByte, 0, 1) == -1 ? -1 : oneByte[0] & 0xFF; 145 } 146 147 /** {@inheritDoc} */ 148 @Override 149 public void close() throws IOException { 150 in.close(); 151 } 152 153 /** {@inheritDoc} */ 154 @Override 155 public int available() { 156 return writeIndex - readIndex; 157 } 158 159 /** 160 * Get the uncompressed size of the stream 161 * 162 * @return the uncompressed size 163 */ 164 public int getSize() { 165 return size; 166 } 167 168 /** 169 * Adds some initial data to fill the window with. 170 * 171 * <p>This is used if the stream has been cut into blocks and 172 * back-references of one block may refer to data of the previous 173 * block(s). One such example is the LZ4 frame format using block 174 * dependency.</p> 175 * 176 * @param data the data to fill the window with. 177 * @throws IllegalStateException if the stream has already started to read data 178 */ 179 public void prefill(final byte[] data) { 180 if (writeIndex != 0) { 181 throw new IllegalStateException("The stream has already been read from, can't prefill anymore"); 182 } 183 // we don't need more data than the big offset could refer to, so cap it 184 final int len = Math.min(windowSize, data.length); 185 // we need the last data as we are dealing with *back*-references 186 System.arraycopy(data, data.length - len, buf, 0, len); 187 writeIndex += len; 188 readIndex += len; 189 } 190 191 /** 192 * @since 1.17 193 */ 194 @Override 195 public long getCompressedCount() { 196 return in.getBytesRead(); 197 } 198 199 /** 200 * Used by subclasses to signal the next block contains the given 201 * amount of literal data. 202 * @param length the length of the block 203 * @throws IllegalArgumentException if length is negative 204 */ 205 protected final void startLiteral(final long length) { 206 if (length < 0) { 207 throw new IllegalArgumentException("length must not be negative"); 208 } 209 bytesRemaining = length; 210 } 211 212 /** 213 * Is there still data remaining inside the current block? 214 * @return true if there is still data remaining inside the current block. 215 */ 216 protected final boolean hasMoreDataInBlock() { 217 return bytesRemaining > 0; 218 } 219 220 /** 221 * Reads data from the current literal block. 222 * @param b buffer to write data to 223 * @param off offset to start writing to 224 * @param len maximum amount of data to read 225 * @return number of bytes read, may be 0. Will never return -1 as 226 * EOF-detection is the responsibility of the subclass 227 * @throws IOException if the underlying stream throws or signals 228 * an EOF before the amount of data promised for the block have 229 * been read 230 * @throws NullPointerException if <code>b</code> is null 231 * @throws IndexOutOfBoundsException if <code>off</code> is 232 * negative, <code>len</code> is negative, or <code>len</code> is 233 * greater than <code>b.length - off</code> 234 */ 235 protected final int readLiteral(final byte[] b, final int off, final int len) throws IOException { 236 final int avail = available(); 237 if (len > avail) { 238 tryToReadLiteral(len - avail); 239 } 240 return readFromBuffer(b, off, len); 241 } 242 243 private void tryToReadLiteral(final int bytesToRead) throws IOException { 244 // min of "what is still inside the literal", "what does the user want" and "how much can fit into the buffer" 245 final int reallyTryToRead = Math.min((int) Math.min(bytesToRead, bytesRemaining), 246 buf.length - writeIndex); 247 final int bytesRead = reallyTryToRead > 0 248 ? IOUtils.readFully(in, buf, writeIndex, reallyTryToRead) 249 : 0 /* happens for bytesRemaining == 0 */; 250 count(bytesRead); 251 if (reallyTryToRead != bytesRead) { 252 throw new IOException("Premature end of stream reading literal"); 253 } 254 writeIndex += reallyTryToRead; 255 bytesRemaining -= reallyTryToRead; 256 } 257 258 private int readFromBuffer(final byte[] b, final int off, final int len) { 259 final int readable = Math.min(len, available()); 260 if (readable > 0) { 261 System.arraycopy(buf, readIndex, b, off, readable); 262 readIndex += readable; 263 if (readIndex > 2 * windowSize) { 264 slideBuffer(); 265 } 266 } 267 size += readable; 268 return readable; 269 } 270 271 private void slideBuffer() { 272 System.arraycopy(buf, windowSize, buf, 0, windowSize * 2); 273 writeIndex -= windowSize; 274 readIndex -= windowSize; 275 } 276 277 /** 278 * Used by subclasses to signal the next block contains a back-reference with the given coordinates. 279 * @param offset the offset of the back-reference 280 * @param length the length of the back-reference 281 * @throws IllegalArgumentException if offset not bigger than 0 or 282 * bigger than the number of bytes available for back-references 283 * or if length is negative 284 */ 285 protected final void startBackReference(final int offset, final long length) { 286 if (offset <= 0 || offset > writeIndex) { 287 throw new IllegalArgumentException("offset must be bigger than 0 but not bigger than the number" 288 + " of bytes available for back-references"); 289 } 290 if (length < 0) { 291 throw new IllegalArgumentException("length must not be negative"); 292 } 293 backReferenceOffset = offset; 294 bytesRemaining = length; 295 } 296 297 /** 298 * Reads data from the current back-reference. 299 * @param b buffer to write data to 300 * @param off offset to start writing to 301 * @param len maximum amount of data to read 302 * @return number of bytes read, may be 0. Will never return -1 as 303 * EOF-detection is the responsibility of the subclass 304 * @throws NullPointerException if <code>b</code> is null 305 * @throws IndexOutOfBoundsException if <code>off</code> is 306 * negative, <code>len</code> is negative, or <code>len</code> is 307 * greater than <code>b.length - off</code> 308 */ 309 protected final int readBackReference(final byte[] b, final int off, final int len) { 310 final int avail = available(); 311 if (len > avail) { 312 tryToCopy(len - avail); 313 } 314 return readFromBuffer(b, off, len); 315 } 316 317 private void tryToCopy(final int bytesToCopy) { 318 // this will fit into the buffer without sliding and not 319 // require more than is available inside the back-reference 320 final int copy = Math.min((int) Math.min(bytesToCopy, bytesRemaining), 321 buf.length - writeIndex); 322 if (copy == 0) { 323 // NOP 324 } else if (backReferenceOffset == 1) { // pretty common special case 325 final byte last = buf[writeIndex - 1]; 326 Arrays.fill(buf, writeIndex, writeIndex + copy, last); 327 writeIndex += copy; 328 } else if (copy < backReferenceOffset) { 329 System.arraycopy(buf, writeIndex - backReferenceOffset, buf, writeIndex, copy); 330 writeIndex += copy; 331 } else { 332 // back-reference overlaps with the bytes created from it 333 // like go back two bytes and then copy six (by copying 334 // the last two bytes three time). 335 final int fullRots = copy / backReferenceOffset; 336 for (int i = 0; i < fullRots; i++) { 337 System.arraycopy(buf, writeIndex - backReferenceOffset, buf, writeIndex, backReferenceOffset); 338 writeIndex += backReferenceOffset; 339 } 340 341 final int pad = copy - (backReferenceOffset * fullRots); 342 if (pad > 0) { 343 System.arraycopy(buf, writeIndex - backReferenceOffset, buf, writeIndex, pad); 344 writeIndex += pad; 345 } 346 } 347 bytesRemaining -= copy; 348 } 349 350 /** 351 * Reads a single byte from the real input stream and ensures the data is accounted for. 352 * 353 * @return the byte read as value between 0 and 255 or -1 if EOF has been reached. 354 * @throws IOException if the underlying stream throws 355 */ 356 protected final int readOneByte() throws IOException { 357 final int b = in.read(); 358 if (b != -1) { 359 count(1); 360 return b & 0xFF; 361 } 362 return -1; 363 } 364}