Elias Gamma/Delta Codes

medium · compression, universal-codes, bit-io

Elias Gamma & Delta Codes

Implement Elias gamma and delta codes for positive integers using MSB-first bit order.

Functions

func EncodeGamma(n uint64) []byte
func DecodeGamma(data []byte) (uint64, bool)

func EncodeDelta(n uint64) []byte
func DecodeDelta(data []byte) (uint64, bool)

Behavior

Inputs are positive integers (n >= 1).
Encoders return a byte slice containing a single codeword padded with trailing zeros to the next byte.
Decoders read exactly one codeword from data and ignore any trailing zero padding.
Return ok=false if the codeword is invalid, incomplete, or represents a value outside uint64. Gamma may have at most 63 leading zeros; delta's decoded bit length must be 1..64.
After that one codeword, all remaining bits must be zero; a trailing one is invalid. This API does not decode a concatenated sequence.

Definitions

Gamma:

Let L = floor(log2 n) + 1.
Write L-1 zeros, then the L-bit binary of n.

Delta:

Let L = floor(log2 n) + 1.
Write gamma(L), then the lower L-1 bits of n.

package solution

// BitWriter writes bits MSB-first.
type BitWriter struct {
	buf   []byte
	cur   byte
	nbits uint8
}

func NewBitWriter() *BitWriter { return &BitWriter{} }

func (bw *BitWriter) WriteBit(bit uint8) {
	if bit&1 == 1 {
		bw.cur |= 1 << (7 - bw.nbits)
	}
	bw.nbits++
	if bw.nbits == 8 {
		bw.buf = append(bw.buf, bw.cur)
		bw.cur = 0
		bw.nbits = 0
	}
}

func (bw *BitWriter) WriteBits(value uint64, n int) {
	for i := n - 1; i >= 0; i-- {
		bw.WriteBit(uint8((value >> uint(i)) & 1))
	}
}

func (bw *BitWriter) Bytes() []byte {
	out := make([]byte, len(bw.buf))
	copy(out, bw.buf)
	if bw.nbits > 0 {
		out = append(out, bw.cur)
	}
	return out
}

// BitReader reads bits MSB-first.
type BitReader struct {
	data  []byte
	idx   int
	nbits uint8
}

func NewBitReader(data []byte) *BitReader { return &BitReader{data: data} }

func (br *BitReader) ReadBit() (uint8, bool) {
	if br.idx >= len(br.data) {
		return 0, false
	}
	b := br.data[br.idx]
	bit := (b >> (7 - br.nbits)) & 1
	br.nbits++
	if br.nbits == 8 {
		br.idx++
		br.nbits = 0
	}
	return bit, true
}

// EncodeGamma encodes n using Elias gamma code.
func EncodeGamma(n uint64) []byte {
	// TODO: implement
	return nil
}

// DecodeGamma decodes a single Elias gamma codeword from data.
func DecodeGamma(data []byte) (uint64, bool) {
	// TODO: implement
	return 0, false
}

// EncodeDelta encodes n using Elias delta code.
func EncodeDelta(n uint64) []byte {
	// TODO: implement
	return nil
}

// DecodeDelta decodes a single Elias delta codeword from data.
func DecodeDelta(data []byte) (uint64, bool) {
	// TODO: implement
	return 0, false
}