    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 *   https://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.snappy;
    020
    021import java.io.IOException;
    022import java.io.InputStream;
    023
    024import org.apache.commons.compress.compressors.lz77support.AbstractLZ77CompressorInputStream;
    025import org.apache.commons.compress.utils.ByteUtils;
    026
    027/**
    028 * CompressorInputStream for the raw Snappy format.
    029 *
    030 * <p>
    031 * This implementation uses an internal buffer in order to handle the back-references that are at the heart of the LZ77 algorithm. The size of the buffer must
    032 * be at least as big as the biggest offset used in the compressed stream. The current version of the Snappy algorithm as defined by Google works on 32k blocks
    033 * and doesn't contain offsets bigger than 32k which is the default block size used by this class.
    034 * </p>
    035 *
    036 * @see <a href="https://github.com/google/snappy/blob/master/format_description.txt">Snappy compressed format description</a>
    037 * @since 1.7
    038 */
    039public class SnappyCompressorInputStream extends AbstractLZ77CompressorInputStream {
    040
    041    private enum State {
    042        NO_BLOCK, IN_LITERAL, IN_BACK_REFERENCE
    043    }
    044
    045    /** Mask used to determine the type of "tag" is being processed */
    046    private static final int TAG_MASK = 0x03;
    047
    048    /** Default block size */
    049    public static final int DEFAULT_BLOCK_SIZE = 32768;
    050
    051    /** The size of the uncompressed data */
    052    private final int size;
    053
    054    /** Number of uncompressed bytes still to be read. */
    055    private int uncompressedBytesRemaining;
    056
    057    /** Current state of the stream */
    058    private State state = State.NO_BLOCK;
    059
    060    private boolean endReached;
    061
    062    /**
    063     * Constructor using the default buffer size of 32k.
    064     *
    065     * @param is An InputStream to read compressed data from
    066     * @throws IOException if reading fails
    067     */
    068    public SnappyCompressorInputStream(final InputStream is) throws IOException {
    069        this(is, DEFAULT_BLOCK_SIZE);
    070    }
    071
    072    /**
    073     * Constructor using a configurable buffer size.
    074     *
    075     * @param is        An InputStream to read compressed data from
    076     * @param blockSize The block size used in compression
    077     * @throws IOException              if reading fails
    078     * @throws IllegalArgumentException if blockSize is not bigger than 0
    079     */
    080    public SnappyCompressorInputStream(final InputStream is, final int blockSize) throws IOException {
    081        super(is, blockSize);
    082        uncompressedBytesRemaining = size = (int) readSize();
    083    }
    084
    085    /**
    086     * Try to fill the buffer with the next block of data.
    087     */
    088    private void fill() throws IOException {
    089        if (uncompressedBytesRemaining == 0) {
    090            endReached = true;
    091            return;
    092        }
    093
    094        int b = readOneByte();
    095        if (b == -1) {
    096            throw new IOException("Premature end of stream reading block start");
    097        }
    098        int length = 0;
    099        int offset = 0;
    100
    101        switch (b & TAG_MASK) {
    102
    103        case 0x00:
    104
    105            length = readLiteralLength(b);
    106            if (length < 0) {
    107                throw new IOException("Illegal block with a negative literal size found");
    108            }
    109            uncompressedBytesRemaining -= length;
    110            startLiteral(length);
    111            state = State.IN_LITERAL;
    112            break;
    113
    114        case 0x01:
    115
    116            /*
    117             * These elements can encode lengths between [4..11] bytes and offsets between [0..2047] bytes. (len-4) occupies three bits and is stored in bits
    118             * [2..4] of the tag byte. The offset occupies 11 bits, of which the upper three are stored in the upper three bits ([5..7]) of the tag byte, and
    119             * the lower eight are stored in a byte following the tag byte.
    120             */
    121
    122            length = 4 + (b >> 2 & 0x07);
    123            uncompressedBytesRemaining -= length;
    124            offset = (b & 0xE0) << 3;
    125            b = readOneByte();
    126            if (b == -1) {
    127                throw new IOException("Premature end of stream reading back-reference length");
    128            }
    129            offset |= b;
    130
    131            try {
    132                startBackReference(offset, length);
    133            } catch (final IllegalArgumentException ex) {
    134                throw new IOException("Illegal block with bad offset found", ex);
    135            }
    136            state = State.IN_BACK_REFERENCE;
    137            break;
    138
    139        case 0x02:
    140
    141            /*
    142             * These elements can encode lengths between [1..64] and offsets from [0..65535]. (len-1) occupies six bits and is stored in the upper six bits
    143             * ([2..7]) of the tag byte. The offset is stored as a little-endian 16-bit integer in the two bytes following the tag byte.
    144             */
    145
    146            length = (b >> 2) + 1;
    147            if (length < 0) {
    148                throw new IOException("Illegal block with a negative match length found");
    149            }
    150            uncompressedBytesRemaining -= length;
    151
    152            offset = (int) ByteUtils.fromLittleEndian(supplier, 2);
    153
    154            try {
    155                startBackReference(offset, length);
    156            } catch (final IllegalArgumentException ex) {
    157                throw new IOException("Illegal block with bad offset found", ex);
    158            }
    159            state = State.IN_BACK_REFERENCE;
    160            break;
    161
    162        case 0x03:
    163
    164            /*
    165             * These are like the copies with 2-byte offsets (see previous subsection), except that the offset is stored as a 32-bit integer instead of a 16-bit
    166             * integer (and thus will occupy four bytes).
    167             */
    168
    169            length = (b >> 2) + 1;
    170            if (length < 0) {
    171                throw new IOException("Illegal block with a negative match length found");
    172            }
    173            uncompressedBytesRemaining -= length;
    174
    175            offset = (int) ByteUtils.fromLittleEndian(supplier, 4) & 0x7fffffff;
    176
    177            try {
    178                startBackReference(offset, length);
    179            } catch (final IllegalArgumentException ex) {
    180                throw new IOException("Illegal block with bad offset found", ex);
    181            }
    182            state = State.IN_BACK_REFERENCE;
    183            break;
    184        default:
    185            // impossible as TAG_MASK is two bits and all four possible cases have been covered
    186            break;
    187        }
    188    }
    189
    190    /**
    191     * Gets the uncompressed size of the stream
    192     *
    193     * @return the uncompressed size
    194     */
    195    @Override
    196    public int getSize() {
    197        return size;
    198    }
    199
    200    /**
    201     * {@inheritDoc}
    202     */
    203    @Override
    204    public int read(final byte[] b, final int off, final int len) throws IOException {
    205        if (len == 0) {
    206            return 0;
    207        }
    208        if (endReached) {
    209            return -1;
    210        }
    211        switch (state) {
    212        case NO_BLOCK:
    213            fill();
    214            return read(b, off, len);
    215        case IN_LITERAL:
    216            final int litLen = readLiteral(b, off, len);
    217            if (!hasMoreDataInBlock()) {
    218                state = State.NO_BLOCK;
    219            }
    220            return litLen > 0 ? litLen : read(b, off, len);
    221        case IN_BACK_REFERENCE:
    222            final int backReferenceLen = readBackReference(b, off, len);
    223            if (!hasMoreDataInBlock()) {
    224                state = State.NO_BLOCK;
    225            }
    226            return backReferenceLen > 0 ? backReferenceLen : read(b, off, len);
    227        default:
    228            throw new IOException("Unknown stream state " + state);
    229        }
    230    }
    231
    232    /*
    233     * For literals up to and including 60 bytes in length, the upper six bits of the tag byte contain (len-1). The literal follows immediately thereafter in
    234     * the bytestream. - For longer literals, the (len-1) value is stored after the tag byte, little-endian. The upper six bits of the tag byte describe how
    235     * many bytes are used for the length; 60, 61, 62 or 63 for 1-4 bytes, respectively. The literal itself follows after the length.
    236     */
    237    private int readLiteralLength(final int b) throws IOException {
    238        final int length;
    239        switch (b >> 2) {
    240        case 60:
    241            length = readOneByte();
    242            if (length == -1) {
    243                throw new IOException("Premature end of stream reading literal length");
    244            }
    245            break;
    246        case 61:
    247            length = (int) ByteUtils.fromLittleEndian(supplier, 2);
    248            break;
    249        case 62:
    250            length = (int) ByteUtils.fromLittleEndian(supplier, 3);
    251            break;
    252        case 63:
    253            length = (int) ByteUtils.fromLittleEndian(supplier, 4);
    254            break;
    255        default:
    256            length = b >> 2;
    257            break;
    258        }
    259
    260        return length + 1;
    261    }
    262
    263    /**
    264     * The stream starts with the uncompressed length (up to a maximum of 2^32 - 1), stored as a little-endian varint. Varints consist of a series of bytes,
    265     * where the lower 7 bits are data and the upper bit is set iff there are more bytes to be read. In other words, an uncompressed length of 64 would be
    266     * stored as 0x40, and an uncompressed length of 2097150 (0x1FFFFE) would be stored as 0xFE 0xFF 0x7F.
    267     *
    268     * @return The size of the uncompressed data
    269     * @throws IOException Could not read a byte
    270     */
    271    private long readSize() throws IOException {
    272        int index = 0;
    273        long sz = 0;
    274        int b = 0;
    275
    276        do {
    277            b = readOneByte();
    278            if (b == -1) {
    279                throw new IOException("Premature end of stream reading size");
    280            }
    281            sz |= (b & 0x7f) << index++ * 7;
    282        } while (0 != (b & 0x80));
    283        return sz;
    284    }
    285}