In the course of developing my network layer for Mythruna, I wrote some bit stream classes and thought I would share them. By this point, they are pretty well debugged and if there are any surprise bugs then I’d like to know! 
BitOutputStream:
[java]
public class BitOutputStream {
private OutputStream out;
private int currentByte = 0;
private int bits = 8;
public BitOutputStream( OutputStream out ) {
this.out = out;
}
public int getPendingBits() {
return bits;
}
public void writeBits( int value, int count ) throws IOException {
if( count == 0 )
throw new IllegalArgumentException( "Cannot write 0 bits." );
// Make sure the value is clean of extra high bits
value = value & (0xffffffff >>> (32 - count));
int remaining = count;
while( remaining > 0 ) {
int bitsToCopy = bits < remaining ? bits : remaining;
int sourceShift = remaining - bitsToCopy;
int targetShift = bits - bitsToCopy;
currentByte |= (value >>> sourceShift) << targetShift;
remaining -= bitsToCopy;
bits -= bitsToCopy;
value = value & (0xffffffff >>> (32 - remaining));
// If there are no more bits left to write to in our
// working byte then write it out and clear it.
if( bits == 0 ) {
flush();
}
}
}
public void writeLongBits( long value, int count ) throws IOException {
if( count == 0 )
throw new IllegalArgumentException( "Cannot write 0 bits." );
// Make sure the value is clean of extra high bits
value = value & (0xffffffffffffffffL >>> (64 - count));
int remaining = count;
while( remaining > 0 ) {
int bitsToCopy = bits < remaining ? bits : remaining;
int sourceShift = remaining - bitsToCopy;
int targetShift = bits - bitsToCopy;
currentByte |= (value >>> sourceShift) << targetShift;
remaining -= bitsToCopy;
bits -= bitsToCopy;
value = value & (0xffffffffffffffffL >>> (64 - remaining));
// If there are no more bits left to write to in our
// working byte then write it out and clear it.
if( bits == 0 ) {
flush();
}
}
}
protected void flush() throws IOException {
out.write(currentByte);
bits = 8;
currentByte = 0;
}
public void close() throws IOException {
flush();
out.close();
}
}
[/java]
BitInputStream
[java]
public class BitInputStream {
private InputStream in;
private int lastByte;
private int bits = 0;
public BitInputStream( InputStream in ) {
this.in = in;
}
public long readLongBits( int count ) throws IOException {
if( count == 0 )
throw new IllegalArgumentException( "Cannot read 0 bits." );
if( count > 64 )
throw new IllegalArgumentException( "Bit count overflow:" + count );
long result = 0;
// While we still have bits remaining...
int remainingCount = count;
while( remainingCount > 0 ) {
// See if we need to refill the current read byte
if( bits == 0 ) {
int b = in.read();
if( b < 0 )
throw new IOException( "End of stream reached." );
lastByte = b;
bits = 8;
}
// Copy the smaller of the two: remaining bits
// or bits left in lastByte.
int bitsToCopy = bits < remainingCount ? bits : remainingCount;
// How much do we have to shift the read byte to just
// get the high bits we want?
int sourceShift = bits - bitsToCopy;
// And how much do we have to shift those bits to graft
// them onto our result?
int targetShift = remainingCount - bitsToCopy;
// Copy the bits
result |= ((long)lastByte >> sourceShift) << targetShift;
// Keep track of how many bits we have left
remainingCount -= bitsToCopy;
bits -= bitsToCopy;
// Now we need to mask off the bits we just copied from
// lastByte. Just keep the bits that are left.
lastByte = lastByte & (0xff >> (8 - bits));
}
return result;
}
public int readBits( int count ) throws IOException {
if( count == 0 )
throw new IllegalArgumentException( "Cannot read 0 bits." );
if( count > 32 )
throw new IllegalArgumentException( "Bit count overflow:" + count );
int result = 0;
// While we still have bits remaining...
int remainingCount = count;
while( remainingCount > 0 ) {
// See if we need to refill the current read byte
if( bits == 0 ) {
int b = in.read();
if( b < 0 )
throw new IOException( "End of stream reached." );
lastByte = b;
bits = 8;
}
// Copy the smaller of the two: remaining bits
// or bits left in lastByte.
int bitsToCopy = bits < remainingCount ? bits : remainingCount;
// How much do we have to shift the read byte to just
// get the high bits we want?
int sourceShift = bits - bitsToCopy;
// And how much do we have to shift those bits to graft
// them onto our result?
int targetShift = remainingCount - bitsToCopy;
// Copy the bits
result |= (lastByte >> sourceShift) << targetShift;
// Keep track of how many bits we have left
remainingCount -= bitsToCopy;
bits -= bitsToCopy;
// Now we need to mask off the bits we just copied from
// lastByte. Just keep the bits that are left.
lastByte = lastByte & (0xff >> (8 - bits));
}
return result;
}
public void close() throws IOException {
in.close();
}
}
[/java]
Example usage using a byte array as an example. Any InputStream or OutputStream will work.
[java]
ByteArrayOutputStream bOut = new ByteArrayOutputStream();
BitOutputStream out = new BitOutputStream(bOut);
int value1 = 1;
int value2 = 0;
int value3 = 12;
long value4 = 1234567890L;
out.writeBits(value1, 1); //write a single on bit
out.writeBits(value2, 1); //write a single off bit
out.writeBits(value3, 4); //write a 3 bit number
out.writeLongBits(value4, 48) // write a 48 bit number
out.close(); // make sure everything is flushed
// This byte array should be 7 bytes long
// (1 + 1 + 4 + 48) / 8 with an extra byte for the remainder.
byte[] array = bOut.toArray();
ByteArrayInputStream bIn = new ByteArrayInputStream(array);
BitInputStream in = new BitInputStream(bIn);
int v1 = in.readBits(1);
int v2 = in.readBits(1);
int v3 = in.readBits(4);
long v4 = in.readLongBits(48);
[/java]
Because of the padding of the last byte, you can’t properly detect the end of bit streams so that is one difference between this and a regular Java stream. You can’t just keep reading until there is no more data, you have to know what you are grabbing and how many there are.
These stream are exceptionally useful for tightly packing network data. If you know some value can fit in 4 bits (0-15) or 2 bits (0-3) then you don’t have to write a whole byte for those. It’s especially useful for booleans where you get an 8 to 1 savings.
Run Length Encoding is another good use-case where can easily implement some 9-bit protocol to store run lengths and so on.
The output is always: