Building a Zero-Allocation HTTP/2 HPACK Header Encoder in Go — code snippets

snippet-1.go

package hpack

// AppendVarint encodes an integer 'i' with an 'n'-bit prefix and appends it to 'dst'.
// This implementation requires zero heap allocations and operates directly on the destination slice.
func AppendVarint(dst []byte, i uint64, n uint8) []byte {
	if n < 1 || n > 8 {
		panic("invalid prefix size")
	}
	maxPrefixVal := uint64((1 << n) - 1)
	if i < maxPrefixVal {
		dst[len(dst)-1] |= byte(i)
		return dst
	}
	dst[len(dst)-1] |= byte(maxPrefixVal)
	i -= maxPrefixVal
	for i >= 128 {
		dst = append(dst, byte(i&127|128))
		i >>= 7
	}
	return append(dst, byte(i))
}

snippet-2.go

package hpack

// huffmanCode represents a code in the HPACK Huffman table.
type huffmanCode struct {
	val  uint32 // the bit pattern, right-aligned
	bits uint8  // bit length
}

// HuffmanTable is indexed by ASCII byte value according to RFC 7541 Appendix B.
// This selection is abbreviated for compilation but is syntactically complete.
var HuffmanTable = [256]huffmanCode{
	'a': {val: 0x18, bits: 6},
	'e': {val: 0x02, bits: 5},
	'i': {val: 0x19, bits: 6},
	'o': {val: 0x1a, bits: 6},
	'u': {val: 0x55, bits: 7},
	// Other indices would contain their respective RFC 7541 values.
}

// HuffmanEncoder writes encoded bits to a byte buffer without allocating memory.
type HuffmanEncoder struct {
	bitBuf uint64
	bitLen uint8
}

// AppendHuffman encodes the input byte slice and appends the result to dst.
// It avoids allocating an intermediary buffer by writing directly to the slice.
func (he *HuffmanEncoder) AppendHuffman(dst []byte, src []byte) []byte {
	he.bitBuf = 0
	he.bitLen = 0

	for _, b := range src {
		code := HuffmanTable[b]
		he.bitBuf = (he.bitBuf << code.bits) | uint64(code.val)
		he.bitLen += code.bits

		// Flush full bytes
		for he.bitLen >= 8 {
			he.bitLen -= 8
			dst = append(dst, byte(he.bitBuf>>he.bitLen))
		}
	}

	// Pad remaining bits with 1s as per HPACK specification (EOS pattern is all 1s)
	if he.bitLen > 0 {
		padLen := 8 - he.bitLen
		he.bitBuf = (he.bitBuf << padLen) | ((1 << padLen) - 1)
		dst = append(dst, byte(he.bitBuf))
	}
	return dst
}

snippet-3.go

package hpack

// HeaderField represents a header name-value pair.
// To avoid heap allocations, it points to slices of an underlying shared byte buffer
// rather than allocating strings.
type HeaderField struct {
	Name  []byte
	Value []byte
}

// DynamicTable is a fixed-size ring buffer designed to manage dynamic headers
// without triggering Go GC allocations.
type DynamicTable struct {
	storage  []byte // backing array for string data
	scratch  []byte // secondary buffer for defragmentation
	fields   []HeaderField
	head     int
	tail     int
	size     int    // current active fields count
	byteSize uint32 // sum of entry sizes (RFC 7541: name length + value length + 32)
	maxSize  uint32 // maximum allowed size in bytes (default 4096)
}

// NewDynamicTable allocates a dynamic table with pre-allocated capacities.
func NewDynamicTable(maxSize uint32, maxEntries int) *DynamicTable {
	return &DynamicTable{
		storage: make([]byte, 0, maxSize*2), // allocate double the capacity to ease defragmentation
		scratch: make([]byte, 0, maxSize*2),
		fields:  make([]HeaderField, maxEntries),
		maxSize: maxSize,
	}
}

// Reset clears the table metrics without releasing the underlying buffers.
func (dt *DynamicTable) Reset() {
	dt.storage = dt.storage[:0]
	dt.scratch = dt.scratch[:0]
	dt.head = 0
	dt.tail = 0
	dt.size = 0
	dt.byteSize = 0
}

snippet-4.go

package hpack

// Evict frees entries from the tail of the dynamic table until byteSize is within limits.
// It modifies indices in place, avoiding heap allocation.
func (dt *DynamicTable) Evict(needed uint32) {
	for dt.byteSize+needed > dt.maxSize && dt.size > 0 {
		tailField := dt.fields[dt.tail]
		entrySize := uint32(len(tailField.Name) + len(tailField.Value) + 32)
		dt.byteSize -= entrySize

		// Advance tail pointer
		dt.tail = (dt.tail + 1) % len(dt.fields)
		dt.size--
	}
}

// Add adds a new header field to the dynamic table.
// It copies the name and value bytes into the internal storage to prevent holding references to volatile stream buffers.
func (dt *DynamicTable) Add(name, value []byte) bool {
	entrySize := uint32(len(name) + len(value) + 32)
	if entrySize > dt.maxSize {
		dt.Reset()
		return false
	}

	dt.Evict(entrySize)

	neededBytes := len(name) + len(value)
	if len(dt.storage)+neededBytes > cap(dt.storage) {
		dt.defragment()
	}

	start := len(dt.storage)
	dt.storage = append(dt.storage, name...)
	nameEnd := len(dt.storage)
	dt.storage = append(dt.storage, value...)
	valueEnd := len(dt.storage)

	// Insert field at head
	dt.fields[dt.head] = HeaderField{
		Name:  dt.storage[start:nameEnd],
		Value: dt.storage[nameEnd:valueEnd],
	}

	dt.head = (dt.head + 1) % len(dt.fields)
	dt.size++
	dt.byteSize += entrySize
	return true
}

func (dt *DynamicTable) defragment() {
	dt.scratch = dt.scratch[:0]
	idx := dt.tail
	for i := 0; i < dt.size; i++ {
		f := &dt.fields[idx]
		start := len(dt.scratch)
		dt.scratch = append(dt.scratch, f.Name...)
		nameEnd := len(dt.scratch)
		dt.scratch = append(dt.scratch, f.Value...)
		valEnd := len(dt.scratch)

		// Re-slice headers to point to the scratch buffer
		f.Name = dt.scratch[start:nameEnd]
		f.Value = dt.scratch[nameEnd:valEnd]

		idx = (idx + 1) % len(dt.fields)
	}
	// Swap storage and scratch buffers
	dt.storage, dt.scratch = dt.scratch, dt.storage
}

snippet-5.go

package hpack

import "bytes"

// FindResult represents the search status in HPACK tables.
type FindResult struct {
	Index        uint64
	MatchedValue bool
}

// FindHeader searches both static and dynamic tables for a match.
// To avoid allocations, we operate solely on byte slices and index lookups.
func (dt *DynamicTable) FindHeader(name, value []byte) FindResult {
	var nameMatchIndex uint64

	// 1. Search Static Table (1-indexed, entries 1-61)
	for i := 1; i <= 61; i++ {
		stName, stVal := getStaticHeader(i)
		if bytes.Equal(stName, name) {
			if bytes.Equal(stVal, value) {
				return FindResult{Index: uint64(i), MatchedValue: true}
			}
			if nameMatchIndex == 0 {
				nameMatchIndex = uint64(i)
			}
		}
	}

	// 2. Search Dynamic Table (logical index starts at 62)
	idx := dt.tail
	for i := 0; i < dt.size; i++ {
		f := dt.fields[idx]
		logicalIndex := uint64(61 + dt.size - i)
		if bytes.Equal(f.Name, name) {
			if bytes.Equal(f.Value, value) {
				return FindResult{Index: logicalIndex, MatchedValue: true}
			}
			if nameMatchIndex == 0 {
				nameMatchIndex = logicalIndex
			}
		}
		idx = (idx + 1) % len(dt.fields)
	}

	return FindResult{Index: nameMatchIndex, MatchedValue: false}
}

// Mock implementation of static headers for compilation completeness.
func getStaticHeader(idx int) ([]byte, []byte) {
	switch idx {
	case 2:
		return []byte(":method"), []byte("GET")
	case 3:
		return []byte(":method"), []byte("POST")
	case 4:
		return []byte(":path"), []byte("/")
	default:
		return nil, nil
	}
}

snippet-6.go

package hpack

// Encoder manages the HPACK encoding state.
type Encoder struct {
	dynTab *DynamicTable
	huff   HuffmanEncoder
}

// EncodeHeader encodes a single header field into the destination byte slice.
// It selects the optimal encoding representation and appends the result to 'dst'
// with zero heap allocations.
func (e *Encoder) EncodeHeader(dst []byte, name, value []byte, sensitive bool) []byte {
	res := e.dynTab.FindHeader(name, value)

	// Case 1: Perfect match (Indexed representation)
	if res.Index > 0 && res.MatchedValue {
		dst = append(dst, 0x80) // 10000000 MSB set
		dst = AppendVarint(dst, res.Index, 7)
		return dst
	}

	// Case 2: Sensitive field (Literal representation, never index)
	if sensitive {
		dst = append(dst, 0x10) // 00010000 prefix
		if res.Index > 0 {
			dst = AppendVarint(dst, res.Index, 4)
		} else {
			dst = AppendVarint(dst, 0, 4)
			dst = e.appendString(dst, name)
		}
		dst = e.appendString(dst, value)
		return dst
	}

	// Case 3: Literal with Incremental Indexing (Add to dynamic table)
	dst = append(dst, 0x40) // 01000000 prefix
	if res.Index > 0 {
		dst = AppendVarint(dst, res.Index, 6)
	} else {
		dst = AppendVarint(dst, 0, 6)
		dst = e.appendString(dst, name)
	}
	dst = e.appendString(dst, value)

	// Append entry to dynamic table for future reference
	e.dynTab.Add(name, value)
	return dst
}

func (e *Encoder) appendString(dst []byte, s []byte) []byte {
	// Calculate the exact Huffman length without allocation
	var huffLen uint64
	for _, b := range s {
		huffLen += uint64(HuffmanTable[b].bits)
	}
	byteLen := (huffLen + 7) / 8

	dst = append(dst, 0x80) // Set MSB (Huffman compression flag)
	dst = AppendVarint(dst, byteLen, 7)
	dst = e.huff.AppendHuffman(dst, s)
	return dst
}

snippet-7.go

package hpack

import "sync"

// EncoderPool wraps the lifecycle of encoders, reusing memory across connections.
type EncoderPool struct {
	pool sync.Pool
}

// NewEncoderPool creates a pool of pre-allocated HPACK encoders.
func NewEncoderPool(maxTableSize uint32, maxEntries int) *EncoderPool {
	return &EncoderPool{
		pool: sync.Pool{
			New: func() interface{} {
				return &Encoder{
					dynTab: NewDynamicTable(maxTableSize, maxEntries),
					huff:   HuffmanEncoder{},
				}
			},
		},
	}
}

// Get retrieves an encoder from the pool and resets its dynamic table.
func (p *EncoderPool) Get() *Encoder {
	enc := p.pool.Get().(*Encoder)
	enc.dynTab.Reset()
	return enc
}

// Put returns the encoder to the pool for reuse.
func (p *EncoderPool) Put(enc *Encoder) {
	enc.dynTab.Reset()
	p.pool.Put(enc)
}