Module openj9.dtfj
Package com.ibm.dtfj.corereaders.zos.util

Class BitStream

java.lang.Object
com.ibm.dtfj.corereaders.zos.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:

  • 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.