Binary Huffman Coding
- Create an instance of a FileInputStream with the file name passed into constructor
- Pass the FileInputStream to the constructor of the BufferedInputStream
- Attempts to read b.length bytes into b
- Returns total number of bytes read or -1 if nothing was read
- Need to know size of file beforehand
- Useful in current assignment to read in first 4 bytes
- Reads the next byte from the stream
- Returns the byte value or -1 if the end of the stream has been reached
- Easiest to set up a while loop and continually byte for -1 (similar to BufferedReader example in lab, except we're now checking for -1 instead of null).
- Java handles bytes in odd ways, often times converting them to ints when you least expect it
- Make sure you cast all byte literals (i.e. 0xE8 -> (byte) 0xE8)
- Make sure that for all bit operations with bytes, BIT-AND each byte with 0xFF
byte b = ...
b = (b & 0xFF) >>> 8
- Java integers are 32 bits
- Each byte is 8 bits
- Therefore, 4 bytes exactly fit into 1 integer
- It's easy to concatenate 4 bytes into an integer
- Repeatedly shift the resulting integer to the left by 8 bits and AND with next byte
let result = 0
let byte[] be an array of bytes
for index 0 to 3:
shift result to left by 8 bits
result = result BIT-OR (byte[index] BIT-AND 0xFF)
return result
- ByteBuffer API
- [ByteBuffer.wrap(byte[] array)](http://docs.oracle.com/javase/7/docs/api/java/nio/ByteBuffer.html#wrap(byte[]\)) - Returns an instance of a ByteBuffer given an array of bytes
- [ByteBuffer.getInt()](http://docs.oracle.com/javase/7/docs/api/java/nio/ByteBuffer.html#getInt(\)) - Returns the integer value of an instance of a ByteBuffer
- Need an abstract way traverse bits from array of bytes
- Create a BitReader class which takes an array of bytes and provides methods for traversing of bits
- Easiest to read entire file into byte array and then extract individual bits from there
- To find any particular bit, need to know which byte it is contained in and which index in the byte the bit is
- For example, bit 19 is the 3rd bit in the 2nd byte, but how can we determine this?
- Index into array = bit index / 8 (i.e. 19 / 8 = 2)
- Index into byte = bit index % 8 (i.e. 19 % 8 = 3)
- I might recommend the method get(int bitIndex) which returns the bit value from the BitReader
- Or you could create an iterator which does the above behind the scenes, and iterates over bit values
- Often times we want to know the value of a specific bit
- To query a specific bit, we need the use of a bitmask
- A bitmask if a set of bits used with bitwise operations
- To find the value for a specific bit, we perform a bitwise AND with a string of bits and a mask
- If the result is 0, then the bit is 0, otherwise 1
- Each mask should have a single 1 bit where you wish to query
The following table lists all of the masks needed to query bits from a byte:
| Index into Byte | Hex Value | Binary |
|---|---|---|
| 0 | 0x80 | 10000000 |
| 1 | 0x40 | 01000000 |
| 2 | 0x20 | 00100000 |
| 3 | 0x10 | 00010000 |
| 4 | 0x08 | 00001000 |
| 5 | 0x04 | 00000100 |
| 6 | 0x02 | 00000010 |
| 7 | 0x01 | 00000001 |
Let byte b = 10010001
If we want to query the first bit, AND it with it's mask:
10010001
AND 10000000
--------
10000000
Since 10000000 is not equal to 0, then we know the first bit is a 1.
If we want to query the second bit, AND it with it's mask:
10010001
AND 01000000
--------
00000000
Since 00000000 is equal to 0, then we know the second bit is 0.
- Create an array of 8 bitmasks where the array index corresponds to the index into the byte
- Create a single bitmask 0x80, and shift it to the right for as many positions as you need for the index into the byte
let b be a byte of data
let m be a bitmask for b
let i be the index into the byte
(b BIT-AND 0xFF) BIT-AND ((m BIT-AND 0xFF) UNSIGNED-RIGHT-SHIFT i)