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