    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.utils;
    020
    021import java.io.Closeable;
    022import java.io.IOException;
    023import java.io.InputStream;
    024import java.nio.ByteOrder;
    025
    026/**
    027 * Reads bits from an InputStream.
    028 * @since 1.10
    029 * @NotThreadSafe
    030 */
    031public class BitInputStream implements Closeable {
    032    private static final int MAXIMUM_CACHE_SIZE = 63; // bits in long minus sign bit
    033    private static final long[] MASKS = new long[MAXIMUM_CACHE_SIZE + 1];
    034
    035    static {
    036        for (int i = 1; i <= MAXIMUM_CACHE_SIZE; i++) {
    037            MASKS[i] = (MASKS[i - 1] << 1) + 1;
    038        }
    039    }
    040
    041    private final CountingInputStream in;
    042    private final ByteOrder byteOrder;
    043    private long bitsCached;
    044    private int bitsCachedSize;
    045
    046    /**
    047     * Constructor taking an InputStream and its bit arrangement.
    048     * @param in the InputStream
    049     * @param byteOrder the bit arrangement across byte boundaries,
    050     *      either BIG_ENDIAN (aaaaabbb bb000000) or LITTLE_ENDIAN (bbbaaaaa 000000bb)
    051     */
    052    public BitInputStream(final InputStream in, final ByteOrder byteOrder) {
    053        this.in = new CountingInputStream(in);
    054        this.byteOrder = byteOrder;
    055    }
    056
    057    /**
    058     * Drops bits until the next bits will be read from a byte boundary.
    059     * @since 1.16
    060     */
    061    public void alignWithByteBoundary() {
    062        final int toSkip = bitsCachedSize % Byte.SIZE;
    063        if (toSkip > 0) {
    064            readCachedBits(toSkip);
    065        }
    066    }
    067
    068    /**
    069     * Returns an estimate of the number of bits that can be read from
    070     * this input stream without blocking by the next invocation of a
    071     * method for this input stream.
    072     * @throws IOException if the underlying stream throws one when calling available
    073     * @return estimate of the number of bits that can be read without blocking
    074     * @since 1.16
    075     */
    076    public long bitsAvailable() throws IOException {
    077        return bitsCachedSize + ((long) Byte.SIZE) * in.available();
    078    }
    079
    080    /**
    081     * Returns the number of bits that can be read from this input
    082     * stream without reading from the underlying input stream at all.
    083     * @return estimate of the number of bits that can be read without reading from the underlying stream
    084     * @since 1.16
    085     */
    086    public int bitsCached() {
    087        return bitsCachedSize;
    088    }
    089
    090    /**
    091     * Clears the cache of bits that have been read from the
    092     * underlying stream but not yet provided via {@link #readBits}.
    093     */
    094    public void clearBitCache() {
    095        bitsCached = 0;
    096        bitsCachedSize = 0;
    097    }
    098
    099    @Override
    100    public void close() throws IOException {
    101        in.close();
    102    }
    103
    104    /**
    105     * Fills the cache up to 56 bits
    106     * @param count
    107     * @return return true, when EOF
    108     * @throws IOException
    109     */
    110    private boolean ensureCache(final int count) throws IOException {
    111        while (bitsCachedSize < count && bitsCachedSize < 57) {
    112            final long nextByte = in.read();
    113            if (nextByte < 0) {
    114                return true;
    115            }
    116            if (byteOrder == ByteOrder.LITTLE_ENDIAN) {
    117                bitsCached |= (nextByte << bitsCachedSize);
    118            } else {
    119                bitsCached <<= Byte.SIZE;
    120                bitsCached |= nextByte;
    121            }
    122            bitsCachedSize += Byte.SIZE;
    123        }
    124        return false;
    125    }
    126
    127    /**
    128     * Returns the number of bytes read from the underlying stream.
    129     *
    130     * <p>This includes the bytes read to fill the current cache and
    131     * not read as bits so far.</p>
    132     * @return the number of bytes read from the underlying stream
    133     * @since 1.17
    134     */
    135    public long getBytesRead() {
    136        return in.getBytesRead();
    137    }
    138
    139    private long processBitsGreater57(final int count) throws IOException {
    140        final long bitsOut;
    141        final int overflowBits;
    142        long overflow = 0L;
    143
    144        // bitsCachedSize >= 57 and left-shifting it 8 bits would cause an overflow
    145        final int bitsToAddCount = count - bitsCachedSize;
    146        overflowBits = Byte.SIZE - bitsToAddCount;
    147        final long nextByte = in.read();
    148        if (nextByte < 0) {
    149            return nextByte;
    150        }
    151        if (byteOrder == ByteOrder.LITTLE_ENDIAN) {
    152            final long bitsToAdd = nextByte & MASKS[bitsToAddCount];
    153            bitsCached |= (bitsToAdd << bitsCachedSize);
    154            overflow = (nextByte >>> bitsToAddCount) & MASKS[overflowBits];
    155        } else {
    156            bitsCached <<= bitsToAddCount;
    157            final long bitsToAdd = (nextByte >>> (overflowBits)) & MASKS[bitsToAddCount];
    158            bitsCached |= bitsToAdd;
    159            overflow = nextByte & MASKS[overflowBits];
    160        }
    161        bitsOut = bitsCached & MASKS[count];
    162        bitsCached = overflow;
    163        bitsCachedSize = overflowBits;
    164        return bitsOut;
    165    }
    166
    167    /**
    168     * Returns at most 63 bits read from the underlying stream.
    169     *
    170     * @param count the number of bits to read, must be a positive
    171     * number not bigger than 63.
    172     * @return the bits concatenated as a long using the stream's byte order.
    173     *         -1 if the end of the underlying stream has been reached before reading
    174     *         the requested number of bits
    175     * @throws IOException on error
    176     */
    177    public long readBits(final int count) throws IOException {
    178        if (count < 0 || count > MAXIMUM_CACHE_SIZE) {
    179            throw new IOException("count must not be negative or greater than " + MAXIMUM_CACHE_SIZE);
    180        }
    181        if (ensureCache(count)) {
    182            return -1;
    183        }
    184
    185        if (bitsCachedSize < count) {
    186            return processBitsGreater57(count);
    187        }
    188        return readCachedBits(count);
    189    }
    190
    191    private long readCachedBits(final int count) {
    192        final long bitsOut;
    193        if (byteOrder == ByteOrder.LITTLE_ENDIAN) {
    194            bitsOut = (bitsCached & MASKS[count]);
    195            bitsCached >>>= count;
    196        } else {
    197            bitsOut = (bitsCached >> (bitsCachedSize - count)) & MASKS[count];
    198        }
    199        bitsCachedSize -= count;
    200        return bitsOut;
    201    }
    202
    203}