bitfield

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

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

 Go to latest Published: Mar 28, 2024 License: Apache-2.0 Imports: 4 Imported by: 380

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/prysmaticlabs/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 

func (b Bitvector128) Or(c Bitvector128) (Bitvector128, 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 (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 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 

func (b Bitvector8) Or(c Bitvector8) (Bitvector8, 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 (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.

Source Files

View all Source files

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.