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 (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 ¶
Decode returns integers represented by the given RLE+ encoding
The passed []byte should be packed in LSB0 bit numbering
func Encode ¶
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 ¶
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) 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 ¶
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
Source Files