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 InputStream in;
042    private final ByteOrder byteOrder;
043    private long bitsCached = 0;
044    private int bitsCachedSize = 0;
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 = in;
054        this.byteOrder = byteOrder;
055    }
056
057    @Override
058    public void close() throws IOException {
059        in.close();
060    }
061
062    /**
063     * Clears the cache of bits that have been read from the
064     * underlying stream but not yet provided via {@link #readBits}.
065     */
066    public void clearBitCache() {
067        bitsCached = 0;
068        bitsCachedSize = 0;
069    }
070    
071    /**
072     * Returns at most 63 bits read from the underlying stream.
073     *
074     * @param count the number of bits to read, must be a positive
075     * number not bigger than 63.
076     * @return the bits concatenated as a long using the stream's byte order.
077     *         -1 if the end of the underlying stream has been reached before reading
078     *         the requested number of bits
079     * @throws IOException on error
080     */
081    public long readBits(final int count) throws IOException {
082        if (count < 0 || count > MAXIMUM_CACHE_SIZE) {
083            throw new IllegalArgumentException("count must not be negative or greater than " + MAXIMUM_CACHE_SIZE);
084        }
085        if (ensureCache(count)) {
086            return -1;
087        }
088
089        if (bitsCachedSize < count) {
090            return processBitsGreater57(count);
091        }
092        final long bitsOut;
093        if (byteOrder == ByteOrder.LITTLE_ENDIAN) {
094            bitsOut = (bitsCached & MASKS[count]);
095            bitsCached >>>= count;
096        } else {
097            bitsOut = (bitsCached >> (bitsCachedSize - count)) & MASKS[count];
098        }
099        bitsCachedSize -= count;
100        return bitsOut;
101    }
102
103    private long processBitsGreater57(final int count) throws IOException {
104        final long bitsOut;
105        int overflowBits = 0;
106        long overflow = 0l;
107
108        // bitsCachedSize >= 57 and left-shifting it 8 bits would cause an overflow
109        int bitsToAddCount = count - bitsCachedSize;
110        overflowBits = 8 - bitsToAddCount;
111        final long nextByte = in.read();
112        if (nextByte < 0) {
113            return nextByte;
114        }
115        if (byteOrder == ByteOrder.LITTLE_ENDIAN) {
116            long bitsToAdd = nextByte & MASKS[bitsToAddCount];
117            bitsCached |= (bitsToAdd << bitsCachedSize);
118            overflow = (nextByte >>> bitsToAddCount) & MASKS[overflowBits];
119        } else {
120            bitsCached <<= bitsToAddCount;
121            long bitsToAdd = (nextByte >>> (overflowBits)) & MASKS[bitsToAddCount];
122            bitsCached |= bitsToAdd;
123            overflow = nextByte & MASKS[overflowBits];
124        }
125        bitsOut = bitsCached & MASKS[count];
126        bitsCached = overflow;
127        bitsCachedSize = overflowBits;
128        return bitsOut;
129    }
130
131    /**
132     * Fills the cache up to 56 bits
133     * @param count
134     * @return return true, when EOF
135     * @throws IOException
136     */
137    private boolean ensureCache(final int count) throws IOException {
138        while (bitsCachedSize < count && bitsCachedSize < 57) {
139            final long nextByte = in.read();
140            if (nextByte < 0) {
141                return true;
142            }
143            if (byteOrder == ByteOrder.LITTLE_ENDIAN) {
144                bitsCached |= (nextByte << bitsCachedSize);
145            } else {
146                bitsCached <<= 8;
147                bitsCached |= nextByte;
148            }
149            bitsCachedSize += 8;
150        }
151        return false;
152    }
153}