November 8, 2017

Bit Reading in Go

By Liam Mueller

Bit Reading in Go

Last week, I was skimming over programming entries on Freelancer.com (I find it gives you new, practical problems to solve other than FizzBuzz and Linked List implementations) and came across an item requesting an implementation of the BIP-0039 spec. The poster mentioned it must be written in Go, a "fast, statically typed, compiled language that feels like a dynamically typed, interpreted language." After reading the spec, it seemed like a neat weekend project (though, the current bids were already low enough to discard a payout) Instead, I decided to take up the project in spite!

Kidding; I just like spending time with obscure languages to accomplish something that could be (and has been) done in other languages quicker and simpler.

BIP-0039 Background

As the link to the BIP-0039 spec before states, BIP-0039 is a description of how to implement a conversion from mnemonic codes or sentences to deterministic Bitcoin wallets. It begins with generation of words programatically, then spawns a binary seed from those words. The intent is to essentially create a memorable, human-language phrase that can be fed into a computer and digested into a Bitcoin wallet address. It is important to note, however, that humans are not supposed to be able to create their own phrases that are inherently supported.

The process for getting the random mnemonic sentences can be abstracted into the following steps:

  1. Generate entropy (random bytes). Must be multiple of 32; must be within the interval [128, 256].
  2. Generate checksum from taking the first (length of entropy / 32) bits from the SHA256 hash of the entropy.
  3. Append checksum to end of entropy.
  4. Split the joined bits into sections, 11 bits in length. All of these sections are indices, between 0 and 2047, to a list of words.
  5. Get the words by indexing the word list with the sections of bits.

As you can see, at step 2 and 4, we find ourselves reading individual bits. Thus, I found myself in the situation of needing to read to and from odd bit offsets. Such an opprotunity presented a valid reason (the kind I rarely get) for me to force this language on others, and so, we're going to talk about the theory and implementation of a bit reader in Go.

The PlainBitReader struct

Let's begin by taking a look at our PlainBitReader declaration.

// We need the io.ByteReader, so import io package
import (
    "io"
)

type PlainBitReader struct {
    reader io.ByteReader
    byte byte
    offset uint8
}

// Simple method to return a pointer to new instance
func NewPlainBitReader(reader io.ByteReader) *PlainBitReader {
    return &PlainBitReader{reader, 0, 0}
}

It's a struct that has unexported properties reader (our ByteReader), byte for holding the current read byte, and offset to hold our current offset in our byte.

Now comes the theory (although, simple) portion. If we need to read a bit, we will first start with our current offset. If the offset is 0, we need to read the next byte from our reader. If the offset is 8, we need to set it back to 0, then read the next byte from our reader. If the offset does not satisify either condition, we can read the next bit in the byte, incrementing the offset. This can be done by comparing the whole 8 bits of the byte to the byte 10000000 (0x80) shifted right by our offset.

The implementation for this method would then look like

// We may encounter a read error from our reader.
// If so, we'll return that and the returned bit is considered invalid.
func (bitReader *PlainBitReader) ReadBit() (bool, error) {
    if (bitReader.offset == 8) { bitReader.offset = 0 }

    // Get next byte
    if (bitReader.offset == 0) {
        var err error

        bitReader.byte, err = bitReader.reader.ReadByte()

        if (err != nil) {
            return false, err
        }
    }

    // Compare current byte to 10000000 shifted right bitReader.offset times
    bit := bitReader.byte & (0x80 >> bitReader.offset)
    // Increment our offset
    bitReader.offset++
    // Comparison will turn byte to boolean, and no error is returned
    return bit != 0, nil
}

Here, a little more theory to explain reading our x amount of bits now. We're going to return a uint64 for maximimum (unsigned) size. To get the value for this uint64, we are going to need to read the uint from left to right, comparing each bit of it to 1 with a logical OR operation. To align the 1 all the way with the left side of the uint64, we will have to shift the 1 left by ((the amount of bits we want to read) - 1), decreasing that value by 1 as we read through bits. Phew! That might sound a bit esoteric, but the implementation should clear up some confusion.

// We may encounter errors again, so we'll have the same return behavior as last time.
func (bitReader *PlainBitReader) ReadBits(bits int64) (uint64, error) {
    var bitRange uint64

    // Read from bits - 1 to 0
    for i := bits - 1; i >= 0; i-- {
        bit, err := bitReader.ReadBit()

        if (err != nil) { return uint64(0), err }

        if (bit) {
            // xxxxxxxxx
            //         1 << bits - 1 - amount of iterations
            // Compared via OR.
            // We're altering each individual bit of our uint64 each iteration, essentially.
            bitRange |= (1 << uint64(i))
        }
    }

    return bitRange, nil
}

And now we have a simple implementation of a bit reader that doesn't care about being aligned and can read from and to odd offsets!

Usage example

package main

import (
    "bytes"
    "fmt"
    "BitReader" // Assuming you've packaged the implementation elsewhere
)

func main() {
    // Bytes:
    // 11111111 == 256
    // 00000000 == 0
    // 00001111 == 15
    bits = []byte { 0xFF, 0x00, 0x0F }

    bitReader := BitReader.NewPlainBitReader(bytes.NewBuffer(bits))

    // Read first 6 bits of our byte buffer.
    // Bits: 111111 (== 63)
    uintValue, err := bitReader.ReadBits(6)

    // Error catching
    // For brevity, I omitted the rest of these
    if (err != nil) { panic(err) }

    fmt.Println(uintValue)

    // Read next 10 bits.
    // Bits: 1100000000 (== 768)
    uintValue, _ = bitReader.ReadBits(10)

    fmt.Println(uintValue)

    // Read next 4 bits.
    // Bits: 0000 (== 0, obviously)
    uintValue, _ = bitReader.ReadBits(4)

    fmt.Println(uintValue)

    // Read last 4 bits.
    // Bits: 1111 (== 15)
    uintValue, _ = bitReader.ReadBits(4)

    fmt.Println(uintValue)

    // Output:
    // 63
    // 768
    // 0
    // 15
}

There you have it! You can now read individual bits from a buffer in Go! All this code can be found here, albeit altered to work in a single file.


About Liam Mueller

Liam is a consultant dedicated to concise, clean, correct solutions. He is driven by the intent of delivering a comfortable, but enriching experience to any responsibility he is given.