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)

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")
)

Functions

func Decode

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

Decode returns integers represented by the given RLE+ encoding

The length of the encoding is not specified. It is inferred by reading zeroes from the (possibly depleted) BitVector, by virtue of the behavior of BitVector.Take() returning 0 when the end of the BitVector has been reached. This has the downside of not being able to detect corrupt encodings.

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/filecoin-project/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()