    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     * Get 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}