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}