rleplus

Documentation

Index

• Constants
• Variables
• func Decode(buf []byte) (ints []uint64, err error)
• func Encode(ints []uint64) ([]byte, uint, error)
• func RunLengths(ints []uint64) (firstBit byte, runs []uint64)
• type BitNumbering
• type BitVector
  • func NewBitVector(buf []byte, bytePacking BitNumbering) *BitVector
  • func (v *BitVector) Extend(val byte, count uint, order BitNumbering)
  • func (v *BitVector) Get(idx uint) (byte, error)
  • func (v *BitVector) Iterator(order BitNumbering) func(uint) byte
  • func (v *BitVector) Push(val byte)
  • func (v *BitVector) Take(index uint, count uint, order BitNumbering) (out byte)
  • func (v *BitVector) Trim()

Constants

const Version = 0

Version is the 2 lowest bits of this constant

Variables

var (
	// ErrRunLengthTooLarge - data implies a run-length which isn't supported
	ErrRunLengthTooLarge = fmt.Errorf("run length too large for RLE+ version %d", Version)

	// ErrDecode - invalid encoding for this version
	ErrDecode = fmt.Errorf("invalid encoding for RLE+ version %d", Version)

	// ErrWrongVersion - wrong version of RLE+
	ErrWrongVersion = errors.New("invalid RLE+ version")
)

var (
	// ErrOutOfRange - the index passed is out of range for the BitVector
	ErrOutOfRange = errors.New("index out of range")
)

Functions

func Decode

func Decode(buf []byte) (ints []uint64, err error)

Decode returns integers represented by the given RLE+ encoding

The passed []byte should be packed in LSB0 bit numbering

func Encode

func Encode(ints []uint64) ([]byte, uint, error)

Encode returns the RLE+ representation of the provided integers. Also returned is the number of bits required by this encoding, which is not necessarily on a byte boundary.

The RLE+ spec is here: https://github.com/chenjianmei111/specs/blob/master/data-structures.md#rle-bitset-encoding and is described by the BNF Grammar:

<encoding> ::= <header> <blocks>
<header> ::= <version> <bit>
<version> ::= "00"
<blocks> ::= <block> <blocks> | ""
<block> ::= <block_single> | <block_short> | <block_long>
<block_single> ::= "1"
<block_short> ::= "01" <bit> <bit> <bit> <bit>
<block_long> ::= "00" <unsigned_varint>
<bit> ::= "0" | "1"

Filecoin specific: The encoding is returned as a []byte, each byte packed starting with the low-order bit (LSB0)

func RunLengths

func RunLengths(ints []uint64) (firstBit byte, runs []uint64)

RunLengths transforms integers into its bit-set-run-length representation.

A set of unsigned integers { 0, 2, 4, 5, 6 } can be thought of as indices into a bitset { 1, 0, 1, 0, 1, 1, 1 } where bitset[index] == 1.

The bit set run lengths of this set would then be { 1, 1, 1, 1, 3 }, representing lengths of runs alternating between 1 and 0, starting with a first bit of 1.

Duplicated numbers are ignored.

This is a helper function for Encode()

Types

type BitNumbering

type BitNumbering int

BitNumbering indicates the ordering of bits, either least-significant bit in position 0, or most-significant bit in position 0.

It it used in 3 ways with BitVector: 1. Ordering of bits within the Buf []byte structure 2. What order to add bits when using Extend() 3. What order to read bits when using Take()

https://en.wikipedia.org/wiki/Bit_numbering

const (
	// LSB0 - bit ordering starts with the low-order bit
	LSB0 BitNumbering = iota

	// MSB0 - bit ordering starts with the high-order bit
	MSB0
)

type BitVector

type BitVector struct {
	Buf []byte

	// BytePacking is the bit ordering within bytes
	BytePacking BitNumbering

	// Len is the logical number of bits in the vector.
	// The last byte in Buf may have undefined bits if Len is not a multiple of 8
	Len uint
}

BitVector is used to manipulate ordered collections of bits

func NewBitVector

func NewBitVector(buf []byte, bytePacking BitNumbering) *BitVector

NewBitVector constructs a new BitVector from a slice of bytes.

The bytePacking parameter is required to know how to interpret the bit ordering within the bytes.

func (*BitVector) Extend

func (v *BitVector) Extend(val byte, count uint, order BitNumbering)

Extend adds up to 8 bits to the receiver

Given a byte b == 0b11010101 v.Extend(b, 4, LSB0) would add < 1, 0, 1, 0 > v.Extend(b, 4, MSB0) would add < 1, 1, 0, 1 >

Panics if count is out of range

func (*BitVector) Get

func (v *BitVector) Get(idx uint) (byte, error)

Get returns a single bit as a byte -- either 0 or 1

func (*BitVector) Iterator

func (v *BitVector) Iterator(order BitNumbering) func(uint) byte

Iterator returns a function, which when invoked, returns the number of bits requested, and increments an internal cursor.

When the end of the BitVector is reached, it returns zeroes indefinitely

Panics if count is out of range

func (*BitVector) Push

func (v *BitVector) Push(val byte)

Push adds a single bit to the BitVector.

Although it takes a byte, only the low-order bit is used, so just use 0 or 1.

func (*BitVector) Take

func (v *BitVector) Take(index uint, count uint, order BitNumbering) (out byte)

Take reads up to 8 bits at the given index.

Given a BitVector < 1, 1, 0, 1, 0, 1, 0, 1 > v.Take(0, 4, LSB0) would return 0b00001011 v.Take(0, 4, MSB0) would return 0b11010000

Panics if count is out of range

func (*BitVector) Trim

func (v *BitVector) Trim()

Trims zero bits from the end of the bit vector.