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 *
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
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     * Returns 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     * Returns at most 63 bits read from the underlying stream.
172     *
173     * @param count the number of bits to read, must be a positive number not bigger than 63.
174     * @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
175     *         requested number of bits
176     * @throws IOException on error
177     */
178    public long readBits(final int count) throws IOException {
179        if (count < 0 || count > MAXIMUM_CACHE_SIZE) {
180            throw new IOException("count must not be negative or greater than " + MAXIMUM_CACHE_SIZE);
181        }
182        if (ensureCache(count)) {
183            return -1;
184        }
185
186        if (bitsCachedSize < count) {
187            return processBitsGreater57(count);
188        }
189        return readCachedBits(count);
190    }
191
192    private long readCachedBits(final int count) {
193        final long bitsOut;
194        if (byteOrder == ByteOrder.LITTLE_ENDIAN) {
195            bitsOut = bitsCached & MASKS[count];
196            bitsCached >>>= count;
197        } else {
198            bitsOut = bitsCached >> bitsCachedSize - count & MASKS[count];
199        }
200        bitsCachedSize -= count;
201        return bitsOut;
202    }
203
204}