Documentation
¶
Overview ¶
Package bitstream implements a zero-alloc, MSB-first bit stream reader and writer.
It is the foundation of every codec in encoding/chunk (delta-of-delta, Gorilla XOR, T64, dictionary, scaled-decimal+nearest-delta): DoubleDelta and Gorilla live or die on a correct, fast bit packer (DESIGN.md §10, §14 M0). The reader is modeled on the Prometheus/dgryski bstream (an 8-byte refill buffer with a valid-bit count); the writer is append-style (Writer.WriteBits appends to a caller-owned []byte).
All hot-path methods are leaf functions kept small for inlining. The Writer never allocates beyond the append growth of its backing slice; callers may [Reset] it onto a pooled buffer. The Reader takes a []byte view and performs no allocation after construction.
Index ¶
- func LeadingZeros64(u uint64) int
- type Reader
- func (r *Reader) AlignToByte()
- func (r *Reader) Buffered() uint8
- func (r *Reader) ConsumedBytes() int
- func (r *Reader) Peek(nbits uint8) uint64
- func (r *Reader) ReadBit() (bool, error)
- func (r *Reader) ReadBits(nbits uint8) (uint64, error)
- func (r *Reader) ReadByte() (byte, error)
- func (r *Reader) ReadBytes(p []byte) error
- func (r *Reader) ReadBytesView(n int) ([]byte, error)
- func (r *Reader) ReadUvarint() (uint64, error)
- func (r *Reader) ReadVarint() (int64, error)
- func (r *Reader) Remaining() int
- func (r *Reader) Reset(b []byte)
- func (r *Reader) Skip(n uint8)
- func (r *Reader) SkipBits(nbits uint8) error
- type Writer
- func (w *Writer) AppendBytes(n int) []byte
- func (w *Writer) AppendString(s string)
- func (w *Writer) AppendTo(dst []byte) []byte
- func (w *Writer) Bytes() []byte
- func (w *Writer) Len() int
- func (w *Writer) PadToByte()
- func (w *Writer) Reset(buf []byte)
- func (w *Writer) WriteBit(bit bool)
- func (w *Writer) WriteBits(u uint64, nbits int)
- func (w *Writer) WriteByte(b byte) error
- func (w *Writer) WriteBytes(p []byte)
- func (w *Writer) WriteUvarint(u uint64)
- func (w *Writer) WriteVarint(i int64)
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
func LeadingZeros64 ¶
LeadingZeros64 is a convenience for codecs that need the bit-width of a value; it returns bits.LeadingZeros64(u). Exposed so codecs don't import math/bits directly.
Types ¶
type Reader ¶
type Reader struct {
// contains filtered or unexported fields
}
Reader is an MSB-first bit reader over a []byte view. It performs no allocation after construction. The design (an 8-byte refill buffer with a valid-bit count) is modeled on the Prometheus/dgryski bstream; [loadNextBuffer] refills 8 bytes at a time so most reads are a shift-and-mask against [Reader.buffer] with no bounds check.
func NewReader ¶
NewReader returns a Reader over b. The Reader aliases b; callers must not mutate b until the Reader is done. A zero-length b yields a Reader that returns io.EOF from every read.
func (*Reader) AlignToByte ¶
func (r *Reader) AlignToByte()
AlignToByte discards the buffered bits up to the next byte boundary (so the next read begins at a byte boundary in the refill buffer).
func (*Reader) Buffered ¶ added in v0.10.0
Buffered returns the number of bits currently available without a stream refill. A decoder of a short variable-length prefix takes a fast Peek/Skip path when Buffered() >= the prefix width and falls back to bit-at-a-time ReadBit only at the rare buffer boundary — avoiding a function call per bit on the common path.
func (*Reader) ConsumedBytes ¶
ConsumedBytes reports how many bytes of the source stream have been fully consumed (every bit read). It is the byte offset at which the next byte-aligned field or column stream begins. Callers that Writer.PadToByte at the end of encoding can use this to slice the source for the next column.
func (*Reader) Peek ¶ added in v0.10.0
Peek returns the next nbits bits (right-justified) without consuming them. The caller must ensure 1 <= nbits <= Buffered() (typically by checking Buffered() first).
func (*Reader) ReadBits ¶
ReadBits reads nbits bits (nbits in [0,64]) and returns them in the low nbits of a uint64. Returns io.EOF if the stream is exhausted.
func (*Reader) ReadBytes ¶
ReadBytes reads n bytes into p (which must have length n) when the reader is byte-aligned, which is the common case after [AlignToByte] or a whole-byte field. When not aligned, it falls back to per-byte [ReadByte]. This is the bulk read path for dictionary entries and row-id arrays.
func (*Reader) ReadBytesView ¶
ReadBytesView returns the next n byte-aligned bytes as a view into the source stream. The returned slice aliases the reader input and is valid until that input is mutated or released.
func (*Reader) ReadUvarint ¶
ReadUvarint reads an unsigned varint (7 bits per byte, continuation in the high bit), matching Writer.WriteUvarint and encoding/binary Uvarint. Direct method calls (not io.ByteReader) avoid the receiver escaping to the heap.
func (*Reader) ReadVarint ¶
ReadVarint reads a zig-zag varint, matching Writer.WriteVarint and encoding/binary Varint.
func (*Reader) Remaining ¶
Remaining reports the number of bytes still unread, including the partial byte held in the refill buffer. It is approximate (rounds the buffered bits up to a byte).
func (*Reader) Reset ¶
Reset re-binds r onto b, discarding prior state. Cheaper than allocating a new Reader; use with a pooled *Reader.
type Writer ¶
type Writer struct {
// contains filtered or unexported fields
}
Writer is an MSB-first bit writer that appends to a caller-owned []byte. It is the foundation of every encoder in encoding/chunk (DESIGN.md §10, §14 M0).
Zero-alloc discipline: Writer.WriteBits and friends only grow the backing slice via append; there is no per-write allocation. [Reset] re-binds a Writer onto a pooled buffer so callers can reuse a *Writer from a sync.Pool:
w := pool.Get().(*Writer) w.Reset(buf[:0]) defer pool.Put(w)
The bit order is MSB-first: the first bit written occupies the high bit of the first byte. Partial trailing bits are flushed into the last byte, high-justified. [Bytes] returns the consumed prefix; the Writer is then ready for more writes (remaining low bits of the last byte are preserved across [Bytes]).
func NewWriter ¶
NewWriter binds w onto buf for writing. buf is taken as the initial backing slice (its existing content is preserved and writing continues after it). Pass nil or a zero-length slice to start empty. The capacity of buf determines the first growth.
func (*Writer) AppendBytes ¶
AppendBytes reserves n byte-aligned bytes in the stream and returns the writable tail. The returned slice aliases the writer buffer until the next write.
func (*Writer) AppendString ¶
AppendString appends a string's bytes directly when byte-aligned, with no copy (append([]byte, string...) is a compiler intrinsic). Falls back to per-byte [WriteByte] when not aligned.
func (*Writer) AppendTo ¶
AppendTo returns the written bytes as a newly-owned copy (for when the caller needs a stable slice independent of the backing buffer). Allocates.
func (*Writer) Bytes ¶
Bytes returns the bytes consumed so far, including the partial last byte. It is safe to call mid-stream; subsequent writes continue into the unused low bits of the last returned byte. The returned slice aliases the backing buffer.
func (*Writer) Len ¶
Len returns the number of bytes consumed so far (including a partial trailing byte).
func (*Writer) PadToByte ¶
func (w *Writer) PadToByte()
PadToByte pads the stream with zero bits up to the next byte boundary. After this, Writer.Len increases by at most one and [Bytes] is byte-aligned.
func (*Writer) Reset ¶
Reset re-binds w onto buf, discarding any previous state. The bit position resets to the start of buf (any existing bytes in buf are kept as-is and writing continues after them only if [Reset] is called with a non-empty buf — but count is always reset to 0, so the first new write begins a fresh byte after the existing content). Use this to reuse a *Writer from a sync.Pool onto a pooled buffer.
func (*Writer) WriteBits ¶
WriteBits appends the nbits least-significant bits of u, MSB-first within the field. nbits must be in [0, 64]; WriteBits(0, 0) is a no-op.
This is the fast inline path (modeled on Prometheus writeBitsFast): it fills the partial last byte first, then writes whole bytes directly, then any trailing partial byte — avoiding per-byte call overhead.
func (*Writer) WriteByte ¶
WriteByte appends a full byte. It conforms to io.ByteWriter (always returns a nil error) so a *Writer can be passed to helpers that write byte-by-byte; the append-style bit methods ([WriteBits], [WriteBit]) do not return an error because they cannot fail.
func (*Writer) WriteBytes ¶
WriteBytes appends a slice of bytes. When the writer is byte-aligned (the common case after [PadToByte] or a whole-byte field), this is a single append — the fast path for bulk byte writes like dictionary entries and row-id arrays. When not aligned, it falls back to per-byte [WriteByte].
Go's `append([]byte, string...)` is a compiler special case that avoids a copy, so callers may pass a string directly: w.WriteBytes([]byte(s)) is still a copy, but w.stream = append(w.stream, s...) is not. For the zero-copy string path, use Writer.AppendString instead.
func (*Writer) WriteUvarint ¶
WriteUvarint appends u as an unsigned varint (7 bits per byte, continuation bit in the high bit), matching encoding/binary Uvarint. Max 10 bytes.
func (*Writer) WriteVarint ¶
WriteVarint appends i as a zig-zag varint, matching encoding/binary Varint.
Source Files