Create BitInputStream and BitOutputStream Classes

he classes in the java.io and java.nio packages make it easy to read and write just about any kind of data?such as bytes, or arrays of bytes. Other classes make it easy to read and write other data types; however, all these classes read and write data in pieces that are at least a byte long. For example, the DataInputStream and DataOutputStream classes can write Boolean values, which require?in theory?only a single bit to store. These classes, however, use an entire byte for each Boolean value.

In contrast, this article describes a pair of stream classes that let you read and write single bits easily. Not a bit stored as a byte, but a real bit. They treat the data stream as a stream of bits, rather than a stream of bytes. You don’t have to think in terms of bytes at all.

This kind of facility is particularly useful when you are trying to save space. Some file formats store certain values using bit lengths other than 8, 16, or 32. Others?such as data compression formats?benefit from being able to forget about byte boundaries entirely, and to treat data as a homogenous stream of bits.

How BitInputStream and BitOutputStream Work
Before getting into the nitty-gritty, here’s a quick glance at how you might use these classes. In many ways, they’re like regular InputStream and OutputStream classes, except that they act on bits rather than bytes. Here’s a program fragment that writes three bits?1, 1, and 0?to a file.

   FileOutputStream fout =     new FileOutputStream( "bits.dat" );   BitOutputStream bout = new BitOutputStream( fout );      bout.writeBit( 1 );   bout.writeBit( 1 );   bout.writeBit( 0 );      bout.close();

Likewise, here’s some code to read them back in:

   FileInputStream fin = new FileInputStream( "bits.dat" );   BitInputStream bin = new BitInputStream( fin );      int b0 = bin.readBit();   int b1 = bin.readBit();   int b2 = bin.readBit();      bin.close();

Before learning how they work, you should think a little bit about how bits are stored in files.

Creating a Bit Data Format
It’s important to understand that BitInputStream and BitOutputStream don’t use a special format?they use the bits contained in traditional Java streams, except that they deal with the data one bit at a time.

There is a flaw to this approach. File systems themselves deal with data in terms of bytes. Files must contain whole bytes?it’s not possible to have a file that contains a partial byte. You can, of course, write a partial byte by padding the byte with zeros and writing the entire byte. The problem with this approach is that when you read the file in again, you can’t distinguish between the actual data bytes and the padding. Practically speaking, this means that you can write a certain number of bits to a file?but when you read the file back in, it may contain more bits than you originally wrote out.

And it’s not just files: most streams are connected, in the end, to some facility that deals with bytes, not with individual bits.

The essence of the problem is that a bit stream (a BitInputStream or BitOutputStream) is slightly more general than a byte stream (an InputStream or OutputStream). A sequence of bits can be any length; a sequence of bytes has a length, in bits, that is an even multiple of eight.

It’s possible to create a special file format that could store extra information, such as the number of padding bits, which would allow perfect reconstruction of a byte stream. However, that’s not the primary goal. The primary goal is to be able to view any data source?such as a file?as a stream of bits.

Doing Without Stream Inheritance
If you look at the source code in Listing 1 and Listing 2, you’ll find that neither BitInputStream nor BitOutputStream are subclasses of InputStream and OutputStream. Again, that underscores the basic difference between bit streams and byte streams. Most of the methods of InputStream and OutputStream would be meaningless, or at least awkward, as part of a BitInputStream or BitOutputStream implementation.

However, the methods that the BitInputStream and BitOutputStream classes have are analogous to the methods in the traditional stream classes. As you saw in the usage examples, these classes take streams in their constructors, much like traditional stream filters:

   BitOutputStream bout = new BitOutputStream( out );

Where traditional stream classes have read() or write() methods, the BitInputStream and BitOutputStream classes have readBit() and writeBit() methods.

   bout.writeBit( 1 );

And, like traditional stream methods, the classes have close() methods:

   bout.close();

Because they aren’t subclasses of InputStream and OutputStream, the bit streams classes can’t be used as simple replacements. But that’s fine?it doesn’t really make sense to try to use bit streams in places where you need byte streams.

BitOutputStream: Writing Bits
Consider the BitOutputStream. Each BitOutputStream instance has an OutputStream to which it writes bytes. That is, the user code writes bits to the BitOutputStream, and the BitOutputStream writes bytes to its OutputStream.

Each BitOutputStream also has a buffer, which is a single byte:

 
Figure 1. The BitOutputStream: Each BitOutputStream has a stream to which it writes bytes, and a buffer, which is a single byte. The buffer accumulates bits until there are eight of them, at which point they can be written to the OutputStream.

Assume three bits have already been written, using the writeBit() method. These three bits exist in the buffer. Note that the class keeps track of the position where the next bit should be stored; and advances this “cursor” after writing each bit:

 
Figure 2. Some Bytes Are Written: Bits are stored in the buffer. The class keeps track of where to store the next bit with a “cursor” advanced after each write.

After eight bits have been written, the buffer is full?no more bits can be stored in it:

 
Figure 3. The Buffer Is Full: After eight bits have been written, the buffer is full.

At this point, the BitOutputStream writes the full byte to the OutputStream.

 
Figure 4. The Buffer Is Written to the OutputStream: The full buffer is written out to the OutputStream.

The buffer is cleared, and the cursor reset:

 
Figure 5. The Buffer Cleared and Cursor Reset: The full buffer is written out to the OutputStream. The buffer is cleared, and the cursor reset.

The user code continues to write bits to the BitOutputStream. After another eight bits have been written, the class writes the filled buffer byte to the OutputStream:

 
Figure 6. Another Byte Is Written: After another eight bits have been written, a second byte is written to the OutputStream.

This process continues until the stream is closed. If the buffer is partially full when the stream is closed, it is written out as if it had contained eight bits. The remaining empty slots take on the default value of zero.

BitInputStream: Reading Bits
The process of reading from a BitInputStream is similar. Just as a BitOutputStream has an OutputStream, a BitInputStream has an InputStream. And it also has a byte buffer:

 
Figure 7. BitInputStream Transfers: The BitInputStream transfers one byte at a time from the InputStream to the buffer.

Note that the InputStream is shown already filled with data. This is because this InputStream is the source of the bits for the BitInputStream. The amount of data depends on the contents of the InputStream.

The first time that user code calls the readBit() method, there are no bits in the buffer. The BitInputStream must first read a single byte from the InputStream and store it in the buffer.

 
Figure 8. Filling the Buffer: Before reading bits, the class must fill the buffer with data from the InputStream.

Now that the buffer contains some bits, you can return the first one to the calling code. You must also remember to advance the cursor.

 
Figure 9. Returning a Bit: Now that the buffer contains some bits, it can return one to the calling code.

Each time the user calls readBit(), the BitInputStream returns another bit from the buffer.

 
Figure 10. More Calls to readBit(): Each time the user calls readBit(), the BitInputStream returns another bit from the buffer.

After reading the eighth bit, there are no more bits available in the buffer. The cursor has moved “off the end” of the buffer.

 
Figure 11. The Buffer Is Drained: There are no more bits available in the buffer.

The next time the code calls readBit() is called, you must get another byte from the InputStream and place that in the buffer.

 
Figure 12. Refilling the Buffer: The BitInputStream gets another byte from the InputStream and places it in the buffer.

After refilling the buffer, you can return the next bit and advance the cursor.

 
Figure 13. Returning Another Bit: Return the first bit from the newly-filled buffer.

Write a Unit Test
To verify that the classes work correctly, here’s a quick test program. The program called FileCopy (available with the downloadable code for this article) copies a file one bit at a time. You can use the FileCopy program from the command line as follows:

   java FileCopy fromFile toFile

This command copies a file from fromFile to toFile.

The inner loop of this program is very simple:

   while (true) {     bout.writeBit( bin.readBit() );   }

Each cycle through the loop reads a bit from the BitInputStream connected to fromFile, and writes it to the BitOutputStream connected to toFile. Verifying that this program makes a perfect copy of a file proves that the buffering code in the BitInputStream and BitOutputStream classes described in the previous section work properly.

This article describes the implementation of a pair of classes, BitInputStream and BitOutputStream, that read and write individual bits. While these classes aren’t strictly subclasses of the stream classes from the java.io package, they operate in a very similar way, and the implementation makes use of the java.io package. They can be used in ways to the more familiar stream classes.

From a design point of view, these classes are interesting because they create a filter that converts one kind of class to another. The BitInputStream hides a regular InputStream, and the BitOutputStream hides a regular OutputStream.

Share the Post:
Share on facebook
Share on twitter
Share on linkedin

Overview

Recent Articles: