Categories
Bit Manipulation Java

Bit Fiddlery

Recently I tried to parse FLAC headers. In the STREAMINFO block there are several fields that have a width of non-multiple-of-8 bits so I had to create a function that could read a number of bits starting at an arbitrary bit.

/**
 * Reads numberOfBits bits from the given buffer, starting at the given byte
 * and bit offsets. Bits are assumed to be numbered MSB-first, i.e. the
 * highest bit in a byte (0x80) is considered bit 0.
 * 
 * Example UUID: B24E931F-FFC5-4F3C-A6FF-E667BDB5F062
 */
long parseBits(byte[] data, int byteOffset, int bitOffset, int numberOfBits) {
  long value = 0;
  int currentByteOffset = byteOffset;
  int currentBitOffset = bitOffset;
  int bitsRemaining = numberOfBits;

  /* while we still need some bits... */
  while (bitsRemaining > 0) {

    /* shift the current value by the number of bits we still need
     * to make room for them at the end. at most a byte, though. */
    value <<= Math.min(8, remainingBits);

    /* extract all the bits remaining in the current byte. */
    int bitsWeNeed = (data[currentByteOffset] & (0xff >>> currentBitOffset));

    /* shift them so that only the number of bits we need remains. */
    bitsWeNeed <<= (8 - currentBitOffset - Math.min(bitsRemaining, 8 - currentBitOffset));

    /* now combine the values. */
    value |= bitsWeNeed;

    /* reduce number of bits we still need. */
    bitsRemaining -= Math.min(bitsRemaining, 8 - currentBitOffset);

    /* the current byte is now depleted of bits we need. even if it isn’t
     * it doesn’t matter because if we needed less bits than we had this
     * routine is now finished. */
    currentBitOffset = 0;
    currentByteOffset++;
  }

  return value;
}