huffman.go

package http2

import (
	"fmt"
	"sync"
)

// huffmanEncoder provides RFC 7541 compliant Huffman encoding (internal use only)
type huffmanEncoder struct {
	codes   [256]uint32 // Huffman codes for each byte
	lengths [256]uint8  // Bit lengths for each code
}

// huffmanDecoder provides RFC 7541 compliant Huffman decoding (internal use only)
type huffmanDecoder struct {
	root *huffmanNode
}

// huffmanNode represents a node in the Huffman decode tree
type huffmanNode struct {
	left   *huffmanNode
	right  *huffmanNode
	symbol int // -1 for internal nodes, byte value for leaves
	isLeaf bool
}

// Global instances using singleton pattern
var (
	globalEncoder   *huffmanEncoder
	globalDecoder   *huffmanDecoder
	huffmanInitOnce sync.Once
)

// eosSymbol is the End-of-String symbol constant
const eosSymbol = 256

// Huffman table from RFC 7541 Appendix B - CORRECTED VERSION
var huffmanTable = [][3]uint32{
	{0, 0x1ff8, 13},       // symbol 0
	{1, 0x7fffd8, 23},     // symbol 1
	{2, 0xfffffe2, 28},    // symbol 2
	{3, 0xfffffe3, 28},    // symbol 3
	{4, 0xfffffe4, 28},    // symbol 4
	{5, 0xfffffe5, 28},    // symbol 5
	{6, 0xfffffe6, 28},    // symbol 6
	{7, 0xfffffe7, 28},    // symbol 7
	{8, 0xfffffe8, 28},    // symbol 8
	{9, 0xffffea, 24},     // symbol 9 (tab)
	{10, 0x3ffffffc, 30},  // symbol 10 (LF)
	{11, 0xfffffe9, 28},   // symbol 11
	{12, 0xfffffea, 28},   // symbol 12
	{13, 0x3ffffffd, 30},  // symbol 13 (CR)
	{14, 0xfffffeb, 28},   // symbol 14
	{15, 0xfffffec, 28},   // symbol 15
	{16, 0xfffffed, 28},   // symbol 16
	{17, 0xfffffee, 28},   // symbol 17
	{18, 0xfffffef, 28},   // symbol 18
	{19, 0xffffff0, 28},   // symbol 19
	{20, 0xffffff1, 28},   // symbol 20
	{21, 0xffffff2, 28},   // symbol 21
	{22, 0x3ffffffe, 30},  // symbol 22
	{23, 0xffffff3, 28},   // symbol 23
	{24, 0xffffff4, 28},   // symbol 24
	{25, 0xffffff5, 28},   // symbol 25
	{26, 0xffffff6, 28},   // symbol 26
	{27, 0xffffff7, 28},   // symbol 27
	{28, 0xffffff8, 28},   // symbol 28
	{29, 0xffffff9, 28},   // symbol 29
	{30, 0xffffffa, 28},   // symbol 30
	{31, 0xffffffb, 28},   // symbol 31
	{32, 0x14, 6},         // symbol 32 (space)
	{33, 0x3f8, 10},       // symbol 33 (!)
	{34, 0x3f9, 10},       // symbol 34 (")
	{35, 0xffa, 12},       // symbol 35 (#)
	{36, 0x1ff9, 13},      // symbol 36 ($)
	{37, 0x15, 6},         // symbol 37 (%)
	{38, 0xf8, 8},         // symbol 38 (&)
	{39, 0x7fa, 11},       // symbol 39 (')
	{40, 0x3fa, 10},       // symbol 40 (()
	{41, 0x3fb, 10},       // symbol 41 ())
	{42, 0xf9, 8},         // symbol 42 (*)
	{43, 0x7fb, 11},       // symbol 43 (+)
	{44, 0xfa, 8},         // symbol 44 (,)
	{45, 0x16, 6},         // symbol 45 (-)
	{46, 0x17, 6},         // symbol 46 (.)
	{47, 0x18, 6},         // symbol 47 (/)
	{48, 0x0, 5},          // symbol 48 (0)
	{49, 0x1, 5},          // symbol 49 (1)
	{50, 0x2, 5},          // symbol 50 (2)
	{51, 0x19, 6},         // symbol 51 (3)
	{52, 0x1a, 6},         // symbol 52 (4)
	{53, 0x1b, 6},         // symbol 53 (5)
	{54, 0x1c, 6},         // symbol 54 (6)
	{55, 0x1d, 6},         // symbol 55 (7)
	{56, 0x1e, 6},         // symbol 56 (8)
	{57, 0x1f, 6},         // symbol 57 (9)
	{58, 0x5c, 7},         // symbol 58 (:)
	{59, 0xfb, 8},         // symbol 59 (;)
	{60, 0x7ffc, 15},      // symbol 60 (<)
	{61, 0x20, 6},         // symbol 61 (=)
	{62, 0xffb, 12},       // symbol 62 (>)
	{63, 0x3fc, 10},       // symbol 63 (?)
	{64, 0x1ffa, 13},      // symbol 64 (@)
	{65, 0x21, 6},         // symbol 65 (A)
	{66, 0x5d, 7},         // symbol 66 (B)
	{67, 0x5e, 7},         // symbol 67 (C)
	{68, 0x5f, 7},         // symbol 68 (D)
	{69, 0x60, 7},         // symbol 69 (E)
	{70, 0x61, 7},         // symbol 70 (F)
	{71, 0x62, 7},         // symbol 71 (G)
	{72, 0x63, 7},         // symbol 72 (H)
	{73, 0x64, 7},         // symbol 73 (I)
	{74, 0x65, 7},         // symbol 74 (J)
	{75, 0x66, 7},         // symbol 75 (K)
	{76, 0x67, 7},         // symbol 76 (L)
	{77, 0x68, 7},         // symbol 77 (M)
	{78, 0x69, 7},         // symbol 78 (N)
	{79, 0x6a, 7},         // symbol 79 (O)
	{80, 0x6b, 7},         // symbol 80 (P)
	{81, 0x6c, 7},         // symbol 81 (Q)
	{82, 0x6d, 7},         // symbol 82 (R)
	{83, 0x6e, 7},         // symbol 83 (S)
	{84, 0x6f, 7},         // symbol 84 (T)
	{85, 0x70, 7},         // symbol 85 (U)
	{86, 0x71, 7},         // symbol 86 (V)
	{87, 0x72, 7},         // symbol 87 (W)
	{88, 0xfc, 8},         // symbol 88 (X)
	{89, 0x73, 7},         // symbol 89 (Y)
	{90, 0xfd, 8},         // symbol 90 (Z)
	{91, 0x1ffb, 13},      // symbol 91 ([)
	{92, 0x7fff0, 19},     // symbol 92 (\)
	{93, 0x1ffc, 13},      // symbol 93 (])
	{94, 0x3ffc, 14},      // symbol 94 (^)
	{95, 0x22, 6},         // symbol 95 (_)
	{96, 0x7ffd, 15},      // symbol 96 (`)
	{97, 0x3, 5},          // symbol 97 (a)
	{98, 0x23, 6},         // symbol 98 (b)
	{99, 0x4, 5},          // symbol 99 (c)
	{100, 0x24, 6},        // symbol 100 (d)
	{101, 0x5, 5},         // symbol 101 (e)
	{102, 0x25, 6},        // symbol 102 (f)
	{103, 0x26, 6},        // symbol 103 (g)
	{104, 0x27, 6},        // symbol 104 (h)
	{105, 0x6, 5},         // symbol 105 (i)
	{106, 0x74, 7},        // symbol 106 (j)
	{107, 0x75, 7},        // symbol 107 (k)
	{108, 0x28, 6},        // symbol 108 (l)
	{109, 0x29, 6},        // symbol 109 (m)
	{110, 0x2a, 6},        // symbol 110 (n)
	{111, 0x7, 5},         // symbol 111 (o)
	{112, 0x2b, 6},        // symbol 112 (p)
	{113, 0x76, 7},        // symbol 113 (q)
	{114, 0x2c, 6},        // symbol 114 (r)
	{115, 0x8, 5},         // symbol 115 (s)
	{116, 0x9, 5},         // symbol 116 (t)
	{117, 0x2d, 6},        // symbol 117 (u)
	{118, 0x77, 7},        // symbol 118 (v)
	{119, 0x78, 7},        // symbol 119 (w)
	{120, 0x79, 7},        // symbol 120 (x)
	{121, 0x7a, 7},        // symbol 121 (y)
	{122, 0x7b, 7},        // symbol 122 (z)
	{123, 0x7ffe, 15},     // symbol 123 ({)
	{124, 0x7fc, 11},      // symbol 124 (|)
	{125, 0x3ffd, 14},     // symbol 125 (})
	{126, 0x1ffd, 13},     // symbol 126 (~)
	{127, 0xffffffc, 28},  // symbol 127 (DEL)
	{128, 0xfffe6, 20},    // symbol 128
	{129, 0x3fffd2, 22},   // symbol 129
	{130, 0xfffe7, 20},    // symbol 130
	{131, 0xfffe8, 20},    // symbol 131
	{132, 0x3fffd3, 22},   // symbol 132
	{133, 0x3fffd4, 22},   // symbol 133
	{134, 0x3fffd5, 22},   // symbol 134
	{135, 0x7fffd9, 23},   // symbol 135
	{136, 0x3fffd6, 22},   // symbol 136
	{137, 0x7fffda, 23},   // symbol 137
	{138, 0x7fffdb, 23},   // symbol 138
	{139, 0x7fffdc, 23},   // symbol 139
	{140, 0x7fffdd, 23},   // symbol 140
	{141, 0x7fffde, 23},   // symbol 141
	{142, 0xffffeb, 24},   // symbol 142
	{143, 0x7fffdf, 23},   // symbol 143
	{144, 0xffffec, 24},   // symbol 144
	{145, 0xffffed, 24},   // symbol 145
	{146, 0x3fffd7, 22},   // symbol 146
	{147, 0x7fffe0, 23},   // symbol 147
	{148, 0xffffee, 24},   // symbol 148
	{149, 0x7fffe1, 23},   // symbol 149
	{150, 0x7fffe2, 23},   // symbol 150
	{151, 0x7fffe3, 23},   // symbol 151
	{152, 0x7fffe4, 23},   // symbol 152
	{153, 0x1fffdc, 21},   // symbol 153
	{154, 0x3fffd8, 22},   // symbol 154
	{155, 0x7fffe5, 23},   // symbol 155
	{156, 0x3fffd9, 22},   // symbol 156
	{157, 0x7fffe6, 23},   // symbol 157
	{158, 0x7fffe7, 23},   // symbol 158
	{159, 0xffffef, 24},   // symbol 159
	{160, 0x3fffda, 22},   // symbol 160
	{161, 0x1fffdd, 21},   // symbol 161
	{162, 0xfffe9, 20},    // symbol 162
	{163, 0x3fffdb, 22},   // symbol 163
	{164, 0x3fffdc, 22},   // symbol 164
	{165, 0x7fffe8, 23},   // symbol 165
	{166, 0x7fffe9, 23},   // symbol 166
	{167, 0x1fffde, 21},   // symbol 167
	{168, 0x7fffea, 23},   // symbol 168
	{169, 0x3fffdd, 22},   // symbol 169
	{170, 0x3fffde, 22},   // symbol 170
	{171, 0xfffff0, 24},   // symbol 171
	{172, 0x1fffdf, 21},   // symbol 172
	{173, 0x3fffdf, 22},   // symbol 173
	{174, 0x7fffeb, 23},   // symbol 174
	{175, 0x7fffec, 23},   // symbol 175
	{176, 0x1fffe0, 21},   // symbol 176
	{177, 0x1fffe1, 21},   // symbol 177
	{178, 0x3fffe0, 22},   // symbol 178
	{179, 0x1fffe2, 21},   // symbol 179
	{180, 0x7fffed, 23},   // symbol 180
	{181, 0x3fffe1, 22},   // symbol 181
	{182, 0x7fffee, 23},   // symbol 182
	{183, 0x7fffef, 23},   // symbol 183
	{184, 0xfffea, 20},    // symbol 184
	{185, 0x3fffe2, 22},   // symbol 185
	{186, 0x3fffe3, 22},   // symbol 186
	{187, 0x3fffe4, 22},   // symbol 187
	{188, 0x7ffff0, 23},   // symbol 188
	{189, 0x3fffe5, 22},   // symbol 189
	{190, 0x3fffe6, 22},   // symbol 190
	{191, 0x7ffff1, 23},   // symbol 191
	{192, 0x3ffffe0, 26},  // symbol 192
	{193, 0x3ffffe1, 26},  // symbol 193
	{194, 0xfffeb, 20},    // symbol 194
	{195, 0x7fff1, 19},    // symbol 195
	{196, 0x3fffe7, 22},   // symbol 196
	{197, 0x7ffff2, 23},   // symbol 197
	{198, 0x3fffe8, 22},   // symbol 198
	{199, 0x1ffffec, 25},  // symbol 199
	{200, 0x3ffffe2, 26},  // symbol 200
	{201, 0x3ffffe3, 26},  // symbol 201
	{202, 0x3ffffe4, 26},  // symbol 202
	{203, 0x7ffffde, 27},  // symbol 203
	{204, 0x7ffffdf, 27},  // symbol 204
	{205, 0x3ffffe5, 26},  // symbol 205
	{206, 0xfffff1, 24},   // symbol 206
	{207, 0x1ffffed, 25},  // symbol 207
	{208, 0x7fff2, 19},    // symbol 208
	{209, 0x1fffe3, 21},   // symbol 209
	{210, 0x3ffffe6, 26},  // symbol 210
	{211, 0x7ffffe0, 27},  // symbol 211
	{212, 0x7ffffe1, 27},  // symbol 212
	{213, 0x3ffffe7, 26},  // symbol 213
	{214, 0x7ffffe2, 27},  // symbol 214
	{215, 0xfffff2, 24},   // symbol 215
	{216, 0x1fffe4, 21},   // symbol 216
	{217, 0x1fffe5, 21},   // symbol 217
	{218, 0x3ffffe8, 26},  // symbol 218
	{219, 0x3ffffe9, 26},  // symbol 219
	{220, 0xffffffd, 28},  // symbol 220
	{221, 0x7ffffe3, 27},  // symbol 221
	{222, 0x7ffffe4, 27},  // symbol 222
	{223, 0x7ffffe5, 27},  // symbol 223
	{224, 0xfffec, 20},    // symbol 224
	{225, 0xfffff3, 24},   // symbol 225
	{226, 0xfffed, 20},    // symbol 226
	{227, 0x1fffe6, 21},   // symbol 227
	{228, 0x3fffe9, 22},   // symbol 228
	{229, 0x1fffe7, 21},   // symbol 229
	{230, 0x1fffe8, 21},   // symbol 230
	{231, 0x7ffff3, 23},   // symbol 231
	{232, 0x3fffea, 22},   // symbol 232
	{233, 0x3fffeb, 22},   // symbol 233
	{234, 0x1ffffee, 25},  // symbol 234
	{235, 0x1ffffef, 25},  // symbol 235
	{236, 0xfffff4, 24},   // symbol 236
	{237, 0xfffff5, 24},   // symbol 237
	{238, 0x3ffffea, 26},  // symbol 238
	{239, 0x7ffff4, 23},   // symbol 239
	{240, 0x3ffffeb, 26},  // symbol 240
	{241, 0x7ffffe6, 27},  // symbol 241
	{242, 0x3ffffec, 26},  // symbol 242
	{243, 0x3ffffed, 26},  // symbol 243
	{244, 0x7ffffe7, 27},  // symbol 244
	{245, 0x7ffffe8, 27},  // symbol 245
	{246, 0x7ffffe9, 27},  // symbol 246
	{247, 0x7ffffea, 27},  // symbol 247
	{248, 0x7ffffeb, 27},  // symbol 248
	{249, 0xffffffe, 28},  // symbol 249
	{250, 0x7ffffec, 27},  // symbol 250
	{251, 0x7ffffed, 27},  // symbol 251
	{252, 0x7ffffee, 27},  // symbol 252
	{253, 0x7ffffef, 27},  // symbol 253
	{254, 0x7fffff0, 27},  // symbol 254
	{255, 0x3ffffeff, 30}, // symbol 255
	{256, 0x3fffffff, 30}, // EOS symbol
}

// Initialize global Huffman encoder/decoder
func initHuffman() {
	globalEncoder = newHuffmanEncoder()
	globalDecoder = newHuffmanDecoder()
}

// getHuffmanEncoder returns the global Huffman encoder instance (internal use only)
func getHuffmanEncoder() *huffmanEncoder {
	huffmanInitOnce.Do(initHuffman)
	return globalEncoder
}

// getHuffmanDecoder returns the global Huffman decoder instance (internal use only)
func getHuffmanDecoder() *huffmanDecoder {
	huffmanInitOnce.Do(initHuffman)
	return globalDecoder
}

// newHuffmanEncoder creates and initializes a new Huffman encoder
func newHuffmanEncoder() *huffmanEncoder {
	encoder := &huffmanEncoder{}

	// Populate lookup tables from the Huffman table
	for _, entry := range huffmanTable {
		if entry[0] < 256 { // Skip EOS symbol for encoding
			symbol := entry[0]
			code := entry[1]
			length := uint8(entry[2])

			encoder.codes[symbol] = code
			encoder.lengths[symbol] = length
		}
	}

	return encoder
}

// encode encodes a string using Huffman coding per RFC 7541 Section 5.2
func (e *huffmanEncoder) encode(input string) []byte {
	if len(input) == 0 {
		return nil
	}

	// Calculate total bits needed
	totalBits := 0
	for i := 0; i < len(input); i++ {
		totalBits += int(e.lengths[input[i]])
	}

	if totalBits == 0 {
		return nil
	}

	// Allocate result buffer
	numBytes := (totalBits + 7) / 8
	result := make([]byte, numBytes)

	// Encode bits into bytes
	var bitBuffer uint64 // Use 64-bit buffer for better handling
	var bitsInBuffer int
	var resultIndex int

	for i := 0; i < len(input); i++ {
		symbol := input[i]
		code := uint64(e.codes[symbol])
		length := int(e.lengths[symbol])

		// Add code to bit buffer
		bitBuffer = (bitBuffer << uint(length)) | code
		bitsInBuffer += length

		// Extract complete bytes
		for bitsInBuffer >= 8 && resultIndex < len(result) {
			// Extract top 8 bits
			result[resultIndex] = byte(bitBuffer >> uint(bitsInBuffer-8))
			resultIndex++
			bitsInBuffer -= 8
			bitBuffer &= (1 << uint(bitsInBuffer)) - 1 // Clear extracted bits
		}
	}

	// Handle remaining bits with proper EOS padding per RFC 7541
	if bitsInBuffer > 0 && resultIndex < len(result) {
		// Pad with most significant bits of EOS (all 1s)
		padBits := 8 - bitsInBuffer
		padding := (uint64(1) << uint(padBits)) - 1 // All 1s for padding
		finalByte := (bitBuffer << uint(padBits)) | padding
		result[resultIndex] = byte(finalByte)
	}

	return result
}

// newHuffmanDecoder creates and initializes a new Huffman decoder
func newHuffmanDecoder() *huffmanDecoder {
	decoder := &huffmanDecoder{
		root: &huffmanNode{symbol: -1, isLeaf: false},
	}

	// Build decode tree from Huffman table
	for _, entry := range huffmanTable {
		symbol := int(entry[0])
		code := entry[1]
		length := int(entry[2])

		// Insert symbol into tree
		node := decoder.root
		for i := length - 1; i >= 0; i-- {
			bit := (code >> uint(i)) & 1

			if bit == 0 {
				if node.left == nil {
					node.left = &huffmanNode{symbol: -1, isLeaf: false}
				}
				node = node.left
			} else {
				if node.right == nil {
					node.right = &huffmanNode{symbol: -1, isLeaf: false}
				}
				node = node.right
			}
		}

		// Mark as leaf and set symbol
		node.isLeaf = true
		node.symbol = symbol
	}

	return decoder
}

// decode decodes Huffman-encoded data per RFC 7541 Section 5.2
func (d *huffmanDecoder) decode(encoded []byte) (string, error) {
	if len(encoded) == 0 {
		return "", nil
	}

	var result []byte
	node := d.root

	for byteIndex, b := range encoded {
		for bitIndex := 7; bitIndex >= 0; bitIndex-- {
			bit := (b >> uint(bitIndex)) & 1

			// Navigate tree
			if bit == 0 {
				node = node.left
			} else {
				node = node.right
			}

			if node == nil {
				return "", fmt.Errorf("invalid Huffman code at byte %d, bit %d",
					byteIndex, 7-bitIndex)
			}

			if node.isLeaf {
				if node.symbol == eosSymbol {
					// EOS symbol encountered - check if it's valid padding
					if byteIndex == len(encoded)-1 {
						// This is the last byte, check remaining bits are all 1s
						remainingBits := bitIndex
						if remainingBits > 0 {
							mask := (1 << uint(remainingBits)) - 1
							if (int(b) & mask) == mask {
								// Valid EOS padding
								return string(result), nil
							}
						}
						return string(result), nil // EOS at end is OK
					}
					return "", fmt.Errorf("unexpected EOS symbol in middle of data")
				}

				// Regular symbol - add to result
				result = append(result, byte(node.symbol))
				node = d.root // Reset to root
			}
		}
	}

	// Check final state - should be at root or in valid EOS padding
	// Per RFC 7541 Section 5.2: padding bits are MSB of EOS (all 1s)
	// If we're not at root, verify we're in a valid EOS padding path
	if node != d.root {
		// Check if the current path leads only to EOS
		// Valid padding means all remaining bits would be 1s leading to EOS
		if !d.isValidEOSPadding(node) {
			return "", fmt.Errorf("incomplete Huffman code at end of input")
		}
	}

	return string(result), nil
}

// isValidEOSPadding checks if a node is in a valid EOS padding path
// Per RFC 7541 Section 5.2: padding must be MSB of EOS (all 1s)
// This means if we follow all right branches (1 bits), we should reach EOS
func (d *huffmanDecoder) isValidEOSPadding(node *huffmanNode) bool {
	if node == nil {
		return false
	}

	// If this is a leaf, it must be EOS
	if node.isLeaf {
		return node.symbol == eosSymbol
	}

	// For internal nodes, padding (all 1s) means we follow right branch
	// Valid padding means right branch eventually leads to EOS
	if node.right == nil {
		return false
	}

	return d.isValidEOSPadding(node.right)
}

// calculateEncodedSize calculates the size of encoded output
func (e *huffmanEncoder) calculateEncodedSize(input string) int {
	totalBits := 0
	for i := 0; i < len(input); i++ {
		totalBits += int(e.lengths[input[i]])
	}
	return (totalBits + 7) / 8
}

// isWorthEncoding checks if Huffman encoding would save space
func (e *huffmanEncoder) isWorthEncoding(input string) bool {
	if len(input) == 0 {
		return false
	}

	encodedSize := e.calculateEncodedSize(input)
	return encodedSize < len(input)
}