bitfield

package module
v0.0.0-...-f3b877b Latest Latest
Warning

This package is not in the latest version of its module.

Go to latest
Published: Dec 4, 2023 License: Apache-2.0 Imports: 4 Imported by: 27

README

go-bitfield

GoDoc Go Report Card Build status

Bitfields are a bytes abstraction to represent a list of bits.

See the godoc reference for more details.

Usage

go get github.com/theQRL/go-bitfield

Contributing

Pull requests are welcome. For major changes, please open an issue first to discuss what you would like to change.

License

Apache License 2.0

Documentation

Overview

Package bitfield is an abstraction type for bitfield operations.

A bitfield is also known as a Bitlist or BitvectorN in Ethereum 2.0 spec. Both variants are static arrays in that they cannot dynamically change in size after being constructed. These data types represent a list of bits whose value is treated akin to a boolean. The bits are in little endian order.

BitvectorN - A list of bits that is fixed in size.
Bitlist - A list of bits that is determined at runtime.

The key difference between a bitvector and a bitlist is how they track the number of bits in the array. A bitvectorN is known to have N bits at compile time, so the length is always N no matter how the bitvector is instantiated. Whereas the bitlist can be created with size N at runtime. The bitlist uses the most significant bit in little endian order to indicate the start of the bitlist while in the byte representation.

Index

Constants

This section is empty.

Variables

View Source
var (
	ErrBitlistDifferentLength   = errors.New("bitlists are different lengths")
	ErrBitvectorDifferentLength = errors.New("bitvectors are different lengths")
	ErrWrongLen                 = errors.New("bitvector is wrong length")
)

Functions

This section is empty.

Types

type Bitfield

type Bitfield interface {
	// BitAt returns true if the bit at the given index is 1.
	BitAt(idx uint64) bool
	// SetBitAt sets the bit at the given index to val.
	SetBitAt(idx uint64, val bool)
	// Len returns the length of the bitfield.
	Len() uint64
	// Count returns the number of 1s in the bitfield.
	Count() uint64
	// Bytes returns the bytes value of the bitfield, without the length bit.
	Bytes() []byte
	// BitIndices returns the indices which have a 1.
	BitIndices() []int
}

Bitfield is the abstraction implemented by Bitlist or BitvectorN.

type Bitlist

type Bitlist []byte

Bitlist is a bitfield implementation backed by an array of bytes. The most significant bit in the array of bytes indicates the start position of the bitfield.

Examples of the underlying byte array as bitlist:

byte{0b00001000} is a bitlist with 3 bits which are all zero. bits=[0,0,0]
byte{0b00011111} is a bitlist with 4 bits which are all one.  bits=[1,1,1,1]
byte{0b00011000, 0b00000001} is a bitlist with 8 bits.        bits=[0,0,0,1,1,0,0,0]
byte{0b00011000, 0b00000010} is a bitlist with 9 bits.        bits=[0,0,0,0,1,1,0,0,0]

func NewBitlist

func NewBitlist(n uint64) Bitlist

NewBitlist creates a new bitlist of size N.

func (Bitlist) And

func (b Bitlist) And(c Bitlist) (Bitlist, error)

And returns the AND result of the two bitfields. This method will return an error if the bitlists are not the same length.

func (Bitlist) BitAt

func (b Bitlist) BitAt(idx uint64) bool

BitAt returns the bit value at the given index. If the index requested exceeds the number of bits in the bitlist, then this method returns false.

func (Bitlist) BitIndices

func (b Bitlist) BitIndices() []int

BitIndices returns the list of indices that are set to 1.

func (Bitlist) Bytes

func (b Bitlist) Bytes() []byte

Bytes returns the trimmed underlying byte array without the length bit. The leading zeros in the bitlist will be trimmed to the smallest byte length representation of the bitlist. This may produce an empty byte slice if all bits were zero.

func (Bitlist) BytesNoTrim

func (b Bitlist) BytesNoTrim() []byte

BytesNoTrim returns the underlying byte array without the length bit. No trimming of leading zeros occurs, only size bit is cleared.

func (Bitlist) Contains

func (b Bitlist) Contains(c Bitlist) (bool, error)

Contains returns true if the bitlist contains all of the bits from the provided argument bitlist. This method will return an error if bitlists are not the same length.

func (Bitlist) Count

func (b Bitlist) Count() uint64

Count returns the number of 1s in the bitlist.

func (Bitlist) Len

func (b Bitlist) Len() uint64

Len of the bitlist returns the number of bits available in the underlying byte array.

func (Bitlist) Not

func (b Bitlist) Not() Bitlist

Not returns the NOT result of the bitfield.

func (Bitlist) Or

func (b Bitlist) Or(c Bitlist) (Bitlist, error)

Or returns the OR result of the two bitfields. This method will return an error if the bitlists are not the same length.

func (Bitlist) Overlaps

func (b Bitlist) Overlaps(c Bitlist) (bool, error)

Overlaps returns true if the bitlist contains one of the bits from the provided argument bitlist. This method will return an error if bitlists are not the same length.

func (Bitlist) SetBitAt

func (b Bitlist) SetBitAt(idx uint64, val bool)

SetBitAt will set the bit at the given index to the given value. If the index requested exceeds the number of bits in the bitlist, then this method returns false.

func (Bitlist) ToBitlist64

func (b Bitlist) ToBitlist64() (*Bitlist64, error)

ToBitlist64 converts []byte backed bitlist into []uint64 backed bitlist.

func (Bitlist) Xor

func (b Bitlist) Xor(c Bitlist) (Bitlist, error)

Xor returns the XOR result of the two bitfields. This method will return an error if the bitlists are not the same length.

type Bitlist64

type Bitlist64 struct {
	// contains filtered or unexported fields
}

Bitlist64 is a bitfield implementation backed by an array of uint64.

func NewBitlist64

func NewBitlist64(n uint64) *Bitlist64

NewBitlist64 creates a new bitlist of size `n`.

func NewBitlist64From

func NewBitlist64From(data []uint64) *Bitlist64

NewBitlist64From creates a new bitlist for a given uint64 array.

func NewBitlist64FromBytes

func NewBitlist64FromBytes(n uint64, b []byte) (*Bitlist64, error)

NewBitlist64FromBytes creates a new bitlist for a given array of bytes. Size of the bitlist is explicitly specified via `n` (since number of bits required may not align perfectly to the word size).

func (*Bitlist64) And

func (b *Bitlist64) And(c *Bitlist64) (*Bitlist64, error)

And returns the AND result of the two bitfields (intersection). This method will return an error if the bitlists are not the same length.

func (*Bitlist64) AndCount

func (b *Bitlist64) AndCount(c *Bitlist64) (uint64, error)

AndCount calculates number of bits set in an intersection of two bitfields. This method will return an error if the bitlists are not the same length.

func (*Bitlist64) BitAt

func (b *Bitlist64) BitAt(idx uint64) bool

BitAt returns the bit value at the given index. If the index requested exceeds the number of bits in the bitlist, then this method returns false.

func (*Bitlist64) BitIndices

func (b *Bitlist64) BitIndices() []int

BitIndices returns list of bit indexes of bitlist where value is set to true.

func (*Bitlist64) Bytes

func (b *Bitlist64) Bytes() []byte

Bytes returns underlying array of uint64s as an array of bytes. The leading zeros in the bitlist will be trimmed to the smallest byte length representation of the bitlist. This may produce an empty byte slice if all bits were zero.

func (*Bitlist64) Clone

func (b *Bitlist64) Clone() *Bitlist64

Clone safely copies a given bitlist.

func (*Bitlist64) Contains

func (b *Bitlist64) Contains(c *Bitlist64) (bool, error)

Contains returns true if the bitlist contains all of the bits from the provided argument bitlist i.e. if `b` is a superset of `c`. This method will return an error if bitlists are not the same length.

func (*Bitlist64) Count

func (b *Bitlist64) Count() uint64

Count returns the number of 1s in the bitlist.

func (*Bitlist64) Len

func (b *Bitlist64) Len() uint64

Len returns the number of bits in a bitlist (note that underlying array can be bigger).

func (*Bitlist64) NoAllocAnd

func (b *Bitlist64) NoAllocAnd(c, ret *Bitlist64) error

NoAllocAnd computes the AND result of the two bitfields (intersection). Result is written into provided variable, so no allocation takes place inside the function. This method will return an error if the bitlists are not the same length.

func (*Bitlist64) NoAllocBitIndices

func (b *Bitlist64) NoAllocBitIndices(ret []int)

NoAllocBitIndices returns list of bit indexes of bitlist where value is set to true. No allocation happens inside the function, so number of returned indexes is capped by the capacity of the ret param.

Expected usage pattern:

b := NewBitlist64(n) indices := make([]int, b.Count()) b.NoAllocBitIndices(indices)

func (*Bitlist64) NoAllocNot

func (b *Bitlist64) NoAllocNot(ret *Bitlist64)

NoAllocNot returns the NOT result of the bitfield (complement). Result is written into provided variable, so no allocation takes place inside the function.

func (*Bitlist64) NoAllocOr

func (b *Bitlist64) NoAllocOr(c, ret *Bitlist64) error

NoAllocOr computes the OR result of the two bitfields (union). Result is written into provided variable, so no allocation takes place inside the function. This method will return an error if the bitlists are not the same length.

func (*Bitlist64) NoAllocXor

func (b *Bitlist64) NoAllocXor(c, ret *Bitlist64) error

NoAllocXor returns the XOR result of the two bitfields (symmetric difference). Result is written into provided variable, so no allocation takes place inside the function. This method will return an error if the bitlists are not the same length.

func (*Bitlist64) Not

func (b *Bitlist64) Not() *Bitlist64

Not returns the NOT result of the bitfield (complement).

func (*Bitlist64) Or

func (b *Bitlist64) Or(c *Bitlist64) (*Bitlist64, error)

Or returns the OR result of the two bitfields (union). This method will return an error if the bitlists are not the same length.

func (*Bitlist64) OrCount

func (b *Bitlist64) OrCount(c *Bitlist64) (uint64, error)

OrCount calculates number of bits set in a union of two bitfields. This method will return an error if the bitlists are not the same length.

func (*Bitlist64) Overlaps

func (b *Bitlist64) Overlaps(c *Bitlist64) (bool, error)

Overlaps returns true if the bitlist contains one of the bits from the provided argument bitlist. This method will return an error if bitlists are not the same length.

func (*Bitlist64) SetBitAt

func (b *Bitlist64) SetBitAt(idx uint64, val bool)

SetBitAt will set the bit at the given index to the given value. If the index requested exceeds the number of bits in the bitlist, then this method returns false.

func (*Bitlist64) ToBitlist

func (b *Bitlist64) ToBitlist() Bitlist

ToBitlist converts []uint64 backed bitlist into []byte backed bitlist.

func (*Bitlist64) Xor

func (b *Bitlist64) Xor(c *Bitlist64) (*Bitlist64, error)

Xor returns the XOR result of the two bitfields (symmetric difference). This method will return an error if the bitlists are not the same length.

func (*Bitlist64) XorCount

func (b *Bitlist64) XorCount(c *Bitlist64) (uint64, error)

XorCount calculates number of bits set in a symmetric difference of two bitfields. This method will return an error if the bitlists are not the same length.

type Bitvector128

type Bitvector128 []byte

Bitvector128 is a bitfield with a fixed defined size of 128. There is no length bit present in the underlying byte array.

func NewBitvector128

func NewBitvector128() Bitvector128

NewBitvector128 creates a new bitvector of size 128.

func (Bitvector128) BitAt

func (b Bitvector128) BitAt(idx uint64) bool

BitAt returns the bit value at the given index. If the index requested exceeds the number of bits in the bitvector, then this method returns false.

func (Bitvector128) BitIndices

func (b Bitvector128) BitIndices() []int

BitIndices returns the list of indices that are set to 1.

func (Bitvector128) Bytes

func (b Bitvector128) Bytes() []byte

Bytes returns the bytes data representing the Bitvector128.

func (Bitvector128) Contains

func (b Bitvector128) Contains(c Bitvector128) (bool, error)

Contains returns true if the bitlist contains all of the bits from the provided argument bitlist. This method will return an error if bitlists are not the same length.

func (Bitvector128) Count

func (b Bitvector128) Count() uint64

Count returns the number of 1s in the bitvector.

func (Bitvector128) Len

func (b Bitvector128) Len() uint64

Len returns the number of bits in the bitvector.

func (Bitvector128) Or

Or returns the OR result of the two bitfields. This method will return an error if the bitlists are not the same length.

func (Bitvector128) Overlaps

func (b Bitvector128) Overlaps(c Bitvector128) (bool, error)

Overlaps returns true if the bitlist contains one of the bits from the provided argument bitlist. This method will return an error if bitlists are not the same length.

func (Bitvector128) SetBitAt

func (b Bitvector128) SetBitAt(idx uint64, val bool)

SetBitAt will set the bit at the given index to the given value. If the index requested exceeds the number of bits in the bitvector, then this method returns false.

func (Bitvector128) Shift

func (b Bitvector128) Shift(i int)

Shift bitvector by i. If i >= 0, perform left shift, otherwise right shift.

type Bitvector16

type Bitvector16 []byte

Bitvector16 is a bitfield with a fixed defined size of 16. There is no length bit present in the underlying byte array.

func NewBitvector16

func NewBitvector16() Bitvector16

NewBitvector16 creates a new bitvector of size 16.

func (Bitvector16) BitAt

func (b Bitvector16) BitAt(idx uint64) bool

BitAt returns the bit value at the given index. If the index requested exceeds the number of bits in the bitvector, then this method returns false.

func (Bitvector16) BitIndices

func (b Bitvector16) BitIndices() []int

BitIndices returns the list of indices which are set to 1.

func (Bitvector16) Bytes

func (b Bitvector16) Bytes() []byte

Bytes returns the bytes data representing the bitvector16.

func (Bitvector16) Contains

func (b Bitvector16) Contains(c Bitvector16) (bool, error)

Contains returns true if the bitlist contains all of the bits from the provided argument bitlist. This method will return an error if bitlists are not the same length.

func (Bitvector16) Count

func (b Bitvector16) Count() uint64

Count returns the number of 1s in the bitvector.

func (Bitvector16) Len

func (b Bitvector16) Len() uint64

Len returns the number of bits in the bitvector.

func (Bitvector16) Or

Or returns the OR result of the two bitfields. This method will return an error if the bitlists are not the same length.

func (Bitvector16) Overlaps

func (b Bitvector16) Overlaps(c Bitvector16) (bool, error)

Overlaps returns true if the bitlist contains one of the bits from the provided argument bitlist. This method will return an error if bitlists are not the same length.

func (Bitvector16) SetBitAt

func (b Bitvector16) SetBitAt(idx uint64, val bool)

SetBitAt will set the bit at the given index to the given value. If the index requested exceeds the number of bits in the bitvector, then this method returns false.

func (Bitvector16) Shift

func (b Bitvector16) Shift(i int)

Shift bitvector by i. If i >= 0, perform left shift, otherwise right shift.

type Bitvector256

type Bitvector256 []byte

Bitvector256 is a bitfield with a fixed defined size of 256. There is no length bit present in the underlying byte array.

func NewBitvector256

func NewBitvector256() Bitvector256

NewBitvector256 creates a new bitvector of size 256.

func (Bitvector256) BitAt

func (b Bitvector256) BitAt(idx uint64) bool

BitAt returns the bit value at the given index. If the index requested exceeds the number of bits in the bitvector, then this method returns false.

func (Bitvector256) BitIndices

func (b Bitvector256) BitIndices() []int

BitIndices returns the list of indices that are set to 1.

func (Bitvector256) Bytes

func (b Bitvector256) Bytes() []byte

Bytes returns the bytes data representing the Bitvector256.

func (Bitvector256) Count

func (b Bitvector256) Count() uint64

Count returns the number of 1s in the bitvector.

func (Bitvector256) Len

func (b Bitvector256) Len() uint64

Len returns the number of bits in the bitvector.

func (Bitvector256) SetBitAt

func (b Bitvector256) SetBitAt(idx uint64, val bool)

SetBitAt will set the bit at the given index to the given value. If the index requested exceeds the number of bits in the bitvector, then this method returns false.

func (Bitvector256) Shift

func (b Bitvector256) Shift(i int)

Shift bitvector by i. If i >= 0, perform left shift, otherwise right shift.

type Bitvector32

type Bitvector32 []byte

Bitvector32 is a bitfield with a fixed defined size of 32. There is no length bit present in the underlying byte array.

func NewBitvector32

func NewBitvector32() Bitvector32

NewBitvector32 creates a new bitvector of size 32.

func (Bitvector32) BitAt

func (b Bitvector32) BitAt(idx uint64) bool

BitAt returns the bit value at the given index. If the index requested exceeds the number of bits in the bitvector, then this method returns false.

func (Bitvector32) BitIndices

func (b Bitvector32) BitIndices() []int

BitIndices returns the list of indices which are set to 1.

func (Bitvector32) Bytes

func (b Bitvector32) Bytes() []byte

Bytes returns the bytes data representing the bitvector32.

func (Bitvector32) Count

func (b Bitvector32) Count() uint64

Count returns the number of 1s in the bitvector.

func (Bitvector32) Len

func (b Bitvector32) Len() uint64

Len returns the number of bits in the bitvector.

func (Bitvector32) SetBitAt

func (b Bitvector32) SetBitAt(idx uint64, val bool)

SetBitAt will set the bit at the given index to the given value. If the index requested exceeds the number of bits in the bitvector, then this method returns false.

type Bitvector4

type Bitvector4 []byte

Bitvector4 is a bitfield with a known size of 4. There is no length bit present in the underlying byte array.

func NewBitvector4

func NewBitvector4() Bitvector4

NewBitvector4 creates a new bitvector of size 4.

func (Bitvector4) BitAt

func (b Bitvector4) BitAt(idx uint64) bool

BitAt returns the bit value at the given index. If the index requested exceeds the number of bits in the bitvector, then this method returns false.

func (Bitvector4) BitIndices

func (b Bitvector4) BitIndices() []int

BitIndices returns the list of indices that are set to 1.

func (Bitvector4) Bytes

func (b Bitvector4) Bytes() []byte

Bytes returns the bytes data representing the bitvector4. This method bitmasks the underlying data to ensure that it is an accurate representation.

func (Bitvector4) Count

func (b Bitvector4) Count() uint64

Count returns the number of 1s in the bitvector.

func (Bitvector4) Len

func (b Bitvector4) Len() uint64

Len returns the number of bits in the bitvector.

func (Bitvector4) SetBitAt

func (b Bitvector4) SetBitAt(idx uint64, val bool)

SetBitAt will set the bit at the given index to the given value. If the index requested exceeds the number of bits in the bitvector, then this method returns false.

func (Bitvector4) Shift

func (b Bitvector4) Shift(i int)

Shift bitvector by i. If i >= 0, perform left shift, otherwise right shift.

type Bitvector512

type Bitvector512 []byte

Bitvector512 is a bitfield with a fixed defined size of 512. There is no length bit present in the underlying byte array.

func NewBitvector512

func NewBitvector512() Bitvector512

NewBitvector512 creates a new bitvector of size 512.

func (Bitvector512) BitAt

func (b Bitvector512) BitAt(idx uint64) bool

BitAt returns the bit value at the given index. If the index requested exceeds the number of bits in the bitvector, then this method returns false.

func (Bitvector512) BitIndices

func (b Bitvector512) BitIndices() []int

BitIndices returns the list of indices that are set to 1.

func (Bitvector512) Bytes

func (b Bitvector512) Bytes() []byte

Bytes returns the bytes data representing the Bitvector512.

func (Bitvector512) Count

func (b Bitvector512) Count() uint64

Count returns the number of 1s in the bitvector.

func (Bitvector512) Len

func (b Bitvector512) Len() uint64

Len returns the number of bits in the bitvector.

func (Bitvector512) SetBitAt

func (b Bitvector512) SetBitAt(idx uint64, val bool)

SetBitAt will set the bit at the given index to the given value. If the index requested exceeds the number of bits in the bitvector, then this method returns false.

func (Bitvector512) Shift

func (b Bitvector512) Shift(i int)

Shift bitvector by i. If i >= 0, perform left shift, otherwise right shift.

type Bitvector64

type Bitvector64 []byte

Bitvector64 is a bitfield with a fixed defined size of 64. There is no length bit present in the underlying byte array.

func NewBitvector64

func NewBitvector64() Bitvector64

NewBitvector64 creates a new bitvector of size 64.

func (Bitvector64) BitAt

func (b Bitvector64) BitAt(idx uint64) bool

BitAt returns the bit value at the given index. If the index requested exceeds the number of bits in the bitvector, then this method returns false.

func (Bitvector64) BitIndices

func (b Bitvector64) BitIndices() []int

BitIndices returns the list of indices which are set to 1.

func (Bitvector64) Bytes

func (b Bitvector64) Bytes() []byte

Bytes returns the bytes data representing the bitvector64.

func (Bitvector64) Count

func (b Bitvector64) Count() uint64

Count returns the number of 1s in the bitvector.

func (Bitvector64) Len

func (b Bitvector64) Len() uint64

Len returns the number of bits in the bitvector.

func (Bitvector64) SetBitAt

func (b Bitvector64) SetBitAt(idx uint64, val bool)

SetBitAt will set the bit at the given index to the given value. If the index requested exceeds the number of bits in the bitvector, then this method returns false.

func (Bitvector64) Shift

func (b Bitvector64) Shift(i int)

Shift bitvector by i. If i >= 0, perform left shift, otherwise right shift.

type Bitvector8

type Bitvector8 []byte

Bitvector8 is a bitfield with a fixed defined size of 8. There is no length bit present in the underlying byte array.

func NewBitvector8

func NewBitvector8() Bitvector8

NewBitvector8 creates a new bitvector of size 8.

func (Bitvector8) BitAt

func (b Bitvector8) BitAt(idx uint64) bool

BitAt returns the bit value at the given index. If the index requested exceeds the number of bits in the bitvector, then this method returns false.

func (Bitvector8) BitIndices

func (b Bitvector8) BitIndices() []int

BitIndices returns the list of indices that are set to 1.

func (Bitvector8) Bytes

func (b Bitvector8) Bytes() []byte

Bytes returns the bytes data representing the Bitvector8.

func (Bitvector8) Contains

func (b Bitvector8) Contains(c Bitvector8) (bool, error)

Contains returns true if the bitlist contains all of the bits from the provided argument bitlist. This method will return an error if bitlists are not the same length or not `bitvector8BitSize`.

func (Bitvector8) Count

func (b Bitvector8) Count() uint64

Count returns the number of 1s in the bitvector.

func (Bitvector8) Len

func (b Bitvector8) Len() uint64

Len returns the number of bits in the bitvector.

func (Bitvector8) Or

Or returns the OR result of the two bitfields. This method will return an error if the bitlists are not the same length.

func (Bitvector8) Overlaps

func (b Bitvector8) Overlaps(c Bitvector8) (bool, error)

Overlaps returns true if the bitlist contains one of the bits from the provided argument bitlist. This method will return an error if bitlists are not the same length.

func (Bitvector8) SetBitAt

func (b Bitvector8) SetBitAt(idx uint64, val bool)

SetBitAt will set the bit at the given index to the given value. If the index requested exceeds the number of bits in the bitvector, then this method returns false.

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL