View Javadoc
1   /*
2    * Licensed to the Apache Software Foundation (ASF) under one
3    * or more contributor license agreements.  See the NOTICE file
4    * distributed with this work for additional information
5    * regarding copyright ownership.  The ASF licenses this file
6    * to you under the Apache License, Version 2.0 (the
7    * "License"); you may not use this file except in compliance
8    * with the License.  You may obtain a copy of the License at
9    *
10   * http://www.apache.org/licenses/LICENSE-2.0
11   *
12   * Unless required by applicable law or agreed to in writing,
13   * software distributed under the License is distributed on an
14   * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15   * KIND, either express or implied.  See the License for the
16   * specific language governing permissions and limitations
17   * under the License.
18   */
19  package org.apache.commons.compress.utils;
20  
21  import java.io.Closeable;
22  import java.io.IOException;
23  import java.io.InputStream;
24  import java.nio.ByteOrder;
25  
26  /**
27   * Reads bits from an InputStream.
28   *
29   * @since 1.10
30   * @NotThreadSafe
31   */
32  public class BitInputStream implements Closeable {
33      private static final int MAXIMUM_CACHE_SIZE = 63; // bits in long minus sign bit
34      private static final long[] MASKS = new long[MAXIMUM_CACHE_SIZE + 1];
35  
36      static {
37          for (int i = 1; i <= MAXIMUM_CACHE_SIZE; i++) {
38              MASKS[i] = (MASKS[i - 1] << 1) + 1;
39          }
40      }
41  
42      private final org.apache.commons.io.input.CountingInputStream in;
43      private final ByteOrder byteOrder;
44      private long bitsCached;
45      private int bitsCachedSize;
46  
47      /**
48       * Constructor taking an InputStream and its bit arrangement.
49       *
50       * @param in        the InputStream
51       * @param byteOrder the bit arrangement across byte boundaries, either BIG_ENDIAN (aaaaabbb bb000000) or LITTLE_ENDIAN (bbbaaaaa 000000bb)
52       */
53      public BitInputStream(final InputStream in, final ByteOrder byteOrder) {
54          this.in = new org.apache.commons.io.input.CountingInputStream(in);
55          this.byteOrder = byteOrder;
56      }
57  
58      /**
59       * Drops bits until the next bits will be read from a byte boundary.
60       *
61       * @since 1.16
62       */
63      public void alignWithByteBoundary() {
64          final int toSkip = bitsCachedSize % Byte.SIZE;
65          if (toSkip > 0) {
66              readCachedBits(toSkip);
67          }
68      }
69  
70      /**
71       * 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
72       * stream.
73       *
74       * @throws IOException if the underlying stream throws one when calling available
75       * @return estimate of the number of bits that can be read without blocking
76       * @since 1.16
77       */
78      public long bitsAvailable() throws IOException {
79          return bitsCachedSize + (long) Byte.SIZE * in.available();
80      }
81  
82      /**
83       * Returns the number of bits that can be read from this input stream without reading from the underlying input stream at all.
84       *
85       * @return estimate of the number of bits that can be read without reading from the underlying stream
86       * @since 1.16
87       */
88      public int bitsCached() {
89          return bitsCachedSize;
90      }
91  
92      /**
93       * Clears the cache of bits that have been read from the underlying stream but not yet provided via {@link #readBits}.
94       */
95      public void clearBitCache() {
96          bitsCached = 0;
97          bitsCachedSize = 0;
98      }
99  
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.getByteCount();
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 }