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}