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}