Module openj9.dtfj

Package com.ibm.j9ddr.corereaders.tdump.zebedee.util

Class BitStream

java.lang.Object

com.ibm.j9ddr.corereaders.tdump.zebedee.util.BitStream

All Implemented Interfaces:

Serializable

public final class BitStream
extends Object
implements Serializable

This class provides a mechanism for writing and reading numbers in a bit stream. In other words you can for instance write the number 3 in 2 bits followed by the number 1 in 3 bits and so on, then rewind the stream and read a 2 bit number followed by a 3 bit number etc. The stream is implemented as an array of 32-bit ints (hereafter referred to as "words") and methods are provided to move to the next word and to get and set the current index into the array of words. This enables you to (eg) store a number of sequences of numbers in the same BitStream and to store the index for each sequence externally somewhere.

In addition to writing and reading numbers of fixed length, this stream also supports variable length numbers using a variety of encodings. A good overview of the encodings used can be found here. This Wikipedia article also has some cool graphs showing the scalability of the encodings.

Note that all ints are treated as unsigned. You will still get back what you put in if you write a negative number but if you're using encoded numbers then bear in mind that (eg) -1 will be output as 0xffffffff.

Todo: might be good to wrap this class round a generic Input/OutputStream.

See Also:

• Serialized Form

Constructor Summary

Constructors

Constructor	Description
BitStream()	Create a new BitStream with a default size of 100 bytes.
BitStream(int numInts)	Create a new BitStream containing the given number of ints.

Method Summary

Modifier and Type	Method	Description
int	getIndex()	Returns the current word index
static int	log2(int n)	Returns the log2 of the given number.
static void	main(String[] args)	This method is provided to test the BitStream.
int	memoryUsage()	Give a rough estimate of how many bytes of storage we use.
void	nextWord()	Move to the next full word boundary.
int	readDelta()	Reads a delta coded integer.
int	readGamma()	Reads a gamma coded integer.
int	readGolombRice(int k)	Read a number using Golomb-Rice coding.
int	readIntBits(int len)	Read an int from given number of bits.
long	readLongBits(int len)	Read a long from given number of bits.
int	readUnary()	Read a unary coded integer.
int	readVariableByte()	Read a number using variable byte code.
void	reset()	Resets the stream so that it may be used again for writing.
void	rewind()	Rewinds the stream ready for reading.
void	setIndex(int index)	Sets the word index to the given value.
int	writeDelta(int n)	Outputs the unsigned integer using delta coding.
int	writeGamma(int n)	Outputs the given unsigned integer using gamma coding.
int	writeGolombRice(int n, int k)	Write a number using Golomb-Rice coding.
void	writeIntBits(int n, int len)	Write a number into the given number of bits.
void	writeLongBits(long n, int len)	Write a number into the given number of bits.
int	writeUnary(int n)	Outputs the given unsigned integer as a unary number.
int	writeVariableByte(int n)	Write a number using variable byte code.

Methods declared in class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Details

BitStream

public BitStream()

Create a new BitStream with a default size of 100 bytes.

BitStream

public BitStream(int numInts)

Create a new BitStream containing the given number of ints. The BitStream is implemented as an array of ints which will grow if necessary.

Parameters:

numInts - the initial size of the array of ints

Method Details

rewind

public void rewind()

Rewinds the stream ready for reading.

reset

public void reset()

Resets the stream so that it may be used again for writing.

writeLongBits

public void writeLongBits(long n,
 int len)

Write a number into the given number of bits.

Parameters:

n - the number to write

len - the number of bits to write the number to

writeIntBits

public void writeIntBits(int n,
 int len)

Write a number into the given number of bits. Note that there is no requirement that the given number be small enough to fit, the number written will be masked appropriately.

Parameters:

n - the number to write

len - the number of bits to write the number to

nextWord

public void nextWord()

Move to the next full word boundary.

getIndex

public int getIndex()

Returns the current word index

setIndex

public void setIndex(int index)

Sets the word index to the given value. This also resets the bit offset to the beginning of the word. This method must only be used when reading to start reading a number stream from a saved position.

readIntBits

public int readIntBits(int len)

Read an int from given number of bits.

Parameters:

len - the number of bits to read the number from

readLongBits

public long readLongBits(int len)

Read a long from given number of bits.

Parameters:

len - the number of bits to read the number from

log2

public static int log2(int n)

Returns the log2 of the given number.

writeDelta

public int writeDelta(int n)

Outputs the unsigned integer using delta coding. Delta coding gives better results than gamma when larger numbers are more frequent.

Returns:

the number of bits used

writeGamma

public int writeGamma(int n)

Outputs the given unsigned integer using gamma coding. Gamma coding is good when you know small numbers are much more frequent than large numbers.

Returns:

the number of bits used

writeUnary

public int writeUnary(int n)

Outputs the given unsigned integer as a unary number. Unary numbers are good for small integers.

Returns:

the number of bits used

readDelta

public int readDelta()

Reads a delta coded integer.

readGamma

public int readGamma()

Reads a gamma coded integer.

readUnary

public int readUnary()

Read a unary coded integer.

writeVariableByte

public int writeVariableByte(int n)

Write a number using variable byte code. This is good when you have lots of medium size numbers.

Returns:

the number of bits used

readVariableByte

public int readVariableByte()

Read a number using variable byte code.

writeGolombRice

public int writeGolombRice(int n,
 int k)

Write a number using Golomb-Rice coding. Good all rounder if you choose the right value of k, absolute rubbish otherwise!

Parameters:

n - the unsigned number to write

k - the number of bits to use for the remainder

Returns:

the number of bits used

readGolombRice

public int readGolombRice(int k)

Read a number using Golomb-Rice coding.

Parameters:

k - the number of bits to use for the remainder

memoryUsage

public int memoryUsage()

Give a rough estimate of how many bytes of storage we use. This is the actual storage allocated so may be more that what is in use at any one time.

main

public static void main(String[] args)

This method is provided to test the BitStream. We need to change this to use unit tests at some point.