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}