    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}