xref: /aosp_15_r20/external/pigweed/pw_grpc/gen/hpack_gen.go (revision 61c4878ac05f98d0ceed94b57d316916de578985)

// Copyright 2024 The Pigweed Authors
//
// Licensed under the Apache License, Version 2.0 (the "License"); you may not
// use this file except in compliance with the License. You may obtain a copy of
// the License at
//
//     https://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS, WITHOUT
// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the
// License for the specific language governing permissions and limitations under
// the License.

// Program hpack_gen generates a C++ file to help parse and emit HPACK.
package main

import (
	"fmt"
)

func main() {
	var statsBefore, statsAfter Stats

	buildTree()
	validate(&rootNode)
	computeStats(&statsBefore, &rootNode)

	optimize(&rootNode)
	validate(&rootNode)
	computeStats(&statsAfter, &rootNode)

	assignTableIndices(&rootNode, 0)

	fmt.Println("// Copyright 2024 The Pigweed Authors")
	fmt.Println("//")
	fmt.Println("// Licensed under the Apache License, Version 2.0 (the \"License\"); you may not")
	fmt.Println("// use this file except in compliance with the License. You may obtain a copy of")
	fmt.Println("// the License at")
	fmt.Println("//")
	fmt.Println("//     https://www.apache.org/licenses/LICENSE-2.0")
	fmt.Println("//")
	fmt.Println("// Unless required by applicable law or agreed to in writing, software")
	fmt.Println("// distributed under the License is distributed on an \"AS IS\" BASIS, WITHOUT")
	fmt.Println("// WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. See the")
	fmt.Println("// License for the specific language governing permissions and limitations under")
	fmt.Println("// the License.")
	fmt.Println("//")
	fmt.Println("// AUTOGENERATED FILE, DO NOT EDIT")
	fmt.Println("//")
	fmt.Println("// To regenerate, run `go run gen/hpack_gen.go > hpack.autogen.inc`.")
	fmt.Println("// This file should be included in exactly one *.cc file.")
	fmt.Println("//")
	fmt.Println()
	fmt.Println("// clang-format off")
	printDecoderTable(&statsAfter)
	fmt.Println()
	fmt.Printf("// Decoder table stats:\n")
	fmt.Printf("//   before optimization = %+v\n", statsBefore)
	fmt.Printf("//   after  optimization = %+v\n", statsAfter)
	fmt.Println()
	printStaticResponses()
}

type NodeType int

const (
	BranchNode NodeType = iota
	OutputNode
	UnprintableNode
	EOSNode
)

type Node struct {
	t          NodeType
	output     int // if t == OutputNode, byte to output
	tableIndex int // if t == BranchNode, index in the decoder table
	child      [2]*Node
}

var rootNode = Node{t: BranchNode}

type Stats struct {
	numBranchNodes      int
	numOutputNodes      int
	numUnprintableNodes int
	numInvalidNodes     int
}

func buildTree() {
	for out, code := range huffmanTable {
		updateTree(out, code)
	}
}

func updateTree(out int, code string) {
	if len(code) == 0 {
		panic(fmt.Sprintf("code for byte %v is empty", out))
	}

	curr := &rootNode

	for i := 0; i < len(code); i++ {
		if code[i] != '0' && code[i] != '1' {
			panic(fmt.Sprintf("code for byte %v has invalid bit '%v'", out, code[i]))
		}

		bit := code[i] - '0'

		// Middle of the code: create a branch node if needed.
		if i < len(code)-1 {
			next := curr.child[bit]
			if next == nil {
				next = &Node{t: BranchNode}
				curr.child[bit] = next
			} else if next.t != BranchNode {
				panic(fmt.Sprintf("code for byte %v found non-branch node at bit number %v", out, i))
			}
			curr = next
			continue
		}

		// End of the code: create a leaf node.
		// Each code should lead to a unique leaf node.
		if curr.child[bit] != nil {
			panic(fmt.Sprintf("code for byte %v reached a duplicate leaf node", out))
		}

		switch {
		case out == EOS:
			curr.child[bit] = &Node{t: EOSNode}
		case out < 32 || 127 < out:
			// Unprintable characters are allowed by the Huffman code but not in gRPC.
			// See: https://github.com/grpc/grpc/blob/v1.60.x/doc/PROTOCOL-HTTP2.md#requests.
			curr.child[bit] = &Node{t: UnprintableNode}
		default:
			curr.child[bit] = &Node{t: OutputNode, output: out}
		}
	}
}

func validate(node *Node) {
	// The binary tree should be complete: there should not be missing leaf nodes.
	if node == nil {
		panic("unexpected nil in binary tree")
	}
	if node.t != BranchNode {
		if node.child[0] != nil || node.child[1] != nil {
			panic(fmt.Sprintf("unexpected child under node %+v", node))
		}
		return
	}
	validate(node.child[0])
	validate(node.child[1])
}

func optimize(node *Node) {
	if node.t != BranchNode {
		return
	}
	optimize(node.child[0])
	optimize(node.child[1])
	// Collapse each unprintable subtree into a single unprintable node.
	if node.child[0].t == UnprintableNode && node.child[1].t == UnprintableNode {
		node.t = UnprintableNode
		node.child[0] = nil
		node.child[1] = nil
	}
}

func computeStats(stats *Stats, node *Node) {
	if node == nil {
		stats.numInvalidNodes++
		return
	}
	switch node.t {
	case BranchNode:
		stats.numBranchNodes++
		computeStats(stats, node.child[0])
		computeStats(stats, node.child[1])
	case OutputNode:
		stats.numOutputNodes++
	case UnprintableNode:
		stats.numUnprintableNodes++
	case EOSNode:
		stats.numInvalidNodes++
	}
}

func assignTableIndices(node *Node, idx int) int {
	if node.t != BranchNode {
		return idx
	}
	node.tableIndex = idx
	idx++
	// We use a preorder traversal to ensure the root node has index 0.
	idx = assignTableIndices(node.child[0], idx)
	idx = assignTableIndices(node.child[1], idx)
	return idx
}

const decoderTablePrefix = `
// Huffman decoder table. Decoding starts at index=0. For each bit, we inspect
// kHuffmanDecoderTable[index][bit] and take an action based on that value:
//
//   * If the value matches 0b0..._...., set index=value
//   * If the value matches 0b1xxx_xxxx, output byte 32 + xx_xxxx, set index=0
//   * If the value matches 0b1111_1110, fail: unprintable character
//   * If the value matches 0b1111_1111, fail: decoder entered an invalid state
//
static constexpr std::array<uint8_t[2], %d> kHuffmanDecoderTable = {{
`
const decoderTableSuffix = `
}};
`

func printDecoderTable(stats *Stats) {
	fmt.Printf(decoderTablePrefix, stats.numBranchNodes)
	printDecoderTableEntries(&rootNode)
	fmt.Print(decoderTableSuffix)
}

func printDecoderTableEntries(node *Node) {
	if node.t != BranchNode {
		return
	}

	// Print nodes in preorder, which is the same order the indices were created.
	fmt.Printf("  /*%v=*/ {%v, %v},\n",
		node.tableIndex,
		toDecoderTableEntry(node.child[0]),
		toDecoderTableEntry(node.child[1]))

	printDecoderTableEntries(node.child[0])
	printDecoderTableEntries(node.child[1])
}

func toDecoderTableEntry(node *Node) uint8 {
	switch node.t {
	case BranchNode:
		if node.tableIndex > 127 {
			panic(fmt.Sprintf("BranchNode index %d > 127", node.tableIndex))
		}
		return uint8(node.tableIndex)
	case OutputNode:
		return uint8(node.output-32) | 0b1000_0000
	case UnprintableNode:
		return 0b1111_1110
	case EOSNode:
		// RFC 7541 §5.2: "A Huffman-encoded string literal containing the EOS
		// symbol MUST be treated as a decoding error."
		return 0b1111_1111
	}
	panic(fmt.Sprintf("unexpected node type %v", node.t))
}

const responseHeaderFieldsPrefix = `
// HPACK-encoded header fields which form grpc Response-Headers.
// These are the same for every response.
static constexpr std::array<uint8_t, %d> kResponseHeaderFields = {
`

const responseHeaderFieldsSuffix = `
};
`

const maxStatusCode = 16
const responseTrailerFieldsPrefix = `
// HPACK-encoded header fields which form grpc Trailers. All response Trailers
// are identical except for the status code.
//
// This is indexed by pw::Status::Code, which happens to be identical to grpc's
// status code.
struct ResponseTrailerPayload {
  uint32_t size;
  std::array<uint8_t, %d> bytes;
};
static constexpr std::array<ResponseTrailerPayload, %d> kResponseTrailerFields = {{
`

const responseTrailerFieldsSuffix = `
}};
`

func printStaticResponses() {
	respHeaderFields := buildResponseHeaderFields()
	fmt.Printf(responseHeaderFieldsPrefix, len(respHeaderFields))
	fmt.Printf("  %s", fmtBytes(respHeaderFields))
	fmt.Printf("%s", responseHeaderFieldsSuffix)

	maxLen := len(buildResponseTrailerFields(maxStatusCode))
	fmt.Printf(responseTrailerFieldsPrefix, maxLen, maxStatusCode+1)
	for code := 0; code <= maxStatusCode; code++ {
		payload := buildResponseTrailerFields(code)
		fmt.Printf("  {.size=%d, .bytes={%s}},\n", len(payload), fmtBytes(payload))
	}
	fmt.Printf("%s", responseTrailerFieldsSuffix)
}

func fmtBytes(bytes []byte) string {
	var out string
	for i, b := range bytes {
		if i < len(bytes)-1 {
			out += fmt.Sprintf("0x%x, ", b)
		} else {
			out += fmt.Sprintf("0x%x", b)
		}
	}
	return out
}

// Response-Headers → ":status 200" "content-type application/grpc"
func buildResponseHeaderFields() []byte {
	var out []byte
	out = append(out, 0b1000_1000) // RFC 7541 §6.1: index 8 is ":status" "200"
	out = append(out, 0b0101_1111) // RFC 7541 §6.2.1: index 31 is "content-type"
	out = append(out, literalEncodeWithLength("application/grpc")...)
	return out
}

// Trailers → "grpc-status <DIGITS>"
func buildResponseTrailerFields(statusCode int) []byte {
	var out []byte
	out = append(out, 0b0100_0000) // RFC 7541 §6.2.1: literal name and value
	out = append(out, literalEncodeWithLength("grpc-status")...)
	if statusCode >= 10 {
		out = append(out, 0b0000_0010)             // RFC 7541 §6.2.1: length of value w/out huffman
		out = append(out, byte(statusCode/10)+'0') // RFC 7541 §6.2.1: value
		out = append(out, byte(statusCode%10)+'0')
	} else {
		out = append(out, 0b0000_0001)          // RFC 7541 §6.2.1: length of value w/out huffman
		out = append(out, byte(statusCode)+'0') // RFC 7541 §6.2.1: value
	}
	return out
}

func literalEncodeWithLength(str string) []byte {
	// RFC 7541 §6.2.1: we are generating this structure with H=0. Since the
	// strings are short, there is minimal benefit to using a Huffman encoding,
	// at most 2-3 bytes per string.
	// +---+---+-----------------------+
	// | H |     Value Length (7+)     |
	// +---+---------------------------+
	// | Value String (Length octets)  |
	// +-------------------------------+
	//
	// The length must be encoded across multiple bytes if 128 or larger. See RFC
	// 7541 §5.2. We don't write any strings that large.
	if len(str) >= 128 {
		panic(fmt.Sprintf("cannot encode string of length %v: %#v", len(str), str))
	}
	return append([]byte{byte(len(str))}, str...)
}

// Special symbol for Huffman EOS.
// See RFC 7541 Appendix B.
const EOS = 256

// Mapping from symbol to Huffman code.
// Taken verbatim from RFC 7541 Appendix B.
var huffmanTable = map[int]string{
	0:   "1111111111000",
	1:   "11111111111111111011000",
	2:   "1111111111111111111111100010",
	3:   "1111111111111111111111100011",
	4:   "1111111111111111111111100100",
	5:   "1111111111111111111111100101",
	6:   "1111111111111111111111100110",
	7:   "1111111111111111111111100111",
	8:   "1111111111111111111111101000",
	9:   "111111111111111111101010",
	10:  "111111111111111111111111111100",
	11:  "1111111111111111111111101001",
	12:  "1111111111111111111111101010",
	13:  "111111111111111111111111111101",
	14:  "1111111111111111111111101011",
	15:  "1111111111111111111111101100",
	16:  "1111111111111111111111101101",
	17:  "1111111111111111111111101110",
	18:  "1111111111111111111111101111",
	19:  "1111111111111111111111110000",
	20:  "1111111111111111111111110001",
	21:  "1111111111111111111111110010",
	22:  "111111111111111111111111111110",
	23:  "1111111111111111111111110011",
	24:  "1111111111111111111111110100",
	25:  "1111111111111111111111110101",
	26:  "1111111111111111111111110110",
	27:  "1111111111111111111111110111",
	28:  "1111111111111111111111111000",
	29:  "1111111111111111111111111001",
	30:  "1111111111111111111111111010",
	31:  "1111111111111111111111111011",
	32:  "010100",
	33:  "1111111000",
	34:  "1111111001",
	35:  "111111111010",
	36:  "1111111111001",
	37:  "010101",
	38:  "11111000",
	39:  "11111111010",
	40:  "1111111010",
	41:  "1111111011",
	42:  "11111001",
	43:  "11111111011",
	44:  "11111010",
	45:  "010110",
	46:  "010111",
	47:  "011000",
	48:  "00000",
	49:  "00001",
	50:  "00010",
	51:  "011001",
	52:  "011010",
	53:  "011011",
	54:  "011100",
	55:  "011101",
	56:  "011110",
	57:  "011111",
	58:  "1011100",
	59:  "11111011",
	60:  "111111111111100",
	61:  "100000",
	62:  "111111111011",
	63:  "1111111100",
	64:  "1111111111010",
	65:  "100001",
	66:  "1011101",
	67:  "1011110",
	68:  "1011111",
	69:  "1100000",
	70:  "1100001",
	71:  "1100010",
	72:  "1100011",
	73:  "1100100",
	74:  "1100101",
	75:  "1100110",
	76:  "1100111",
	77:  "1101000",
	78:  "1101001",
	79:  "1101010",
	80:  "1101011",
	81:  "1101100",
	82:  "1101101",
	83:  "1101110",
	84:  "1101111",
	85:  "1110000",
	86:  "1110001",
	87:  "1110010",
	88:  "11111100",
	89:  "1110011",
	90:  "11111101",
	91:  "1111111111011",
	92:  "1111111111111110000",
	93:  "1111111111100",
	94:  "11111111111100",
	95:  "100010",
	96:  "111111111111101",
	97:  "00011",
	98:  "100011",
	99:  "00100",
	100: "100100",
	101: "00101",
	102: "100101",
	103: "100110",
	104: "100111",
	105: "00110",
	106: "1110100",
	107: "1110101",
	108: "101000",
	109: "101001",
	110: "101010",
	111: "00111",
	112: "101011",
	113: "1110110",
	114: "101100",
	115: "01000",
	116: "01001",
	117: "101101",
	118: "1110111",
	119: "1111000",
	120: "1111001",
	121: "1111010",
	122: "1111011",
	123: "111111111111110",
	124: "11111111100",
	125: "11111111111101",
	126: "1111111111101",
	127: "1111111111111111111111111100",
	128: "11111111111111100110",
	129: "1111111111111111010010",
	130: "11111111111111100111",
	131: "11111111111111101000",
	132: "1111111111111111010011",
	133: "1111111111111111010100",
	134: "1111111111111111010101",
	135: "11111111111111111011001",
	136: "1111111111111111010110",
	137: "11111111111111111011010",
	138: "11111111111111111011011",
	139: "11111111111111111011100",
	140: "11111111111111111011101",
	141: "11111111111111111011110",
	142: "111111111111111111101011",
	143: "11111111111111111011111",
	144: "111111111111111111101100",
	145: "111111111111111111101101",
	146: "1111111111111111010111",
	147: "11111111111111111100000",
	148: "111111111111111111101110",
	149: "11111111111111111100001",
	150: "11111111111111111100010",
	151: "11111111111111111100011",
	152: "11111111111111111100100",
	153: "111111111111111011100",
	154: "1111111111111111011000",
	155: "11111111111111111100101",
	156: "1111111111111111011001",
	157: "11111111111111111100110",
	158: "11111111111111111100111",
	159: "111111111111111111101111",
	160: "1111111111111111011010",
	161: "111111111111111011101",
	162: "11111111111111101001",
	163: "1111111111111111011011",
	164: "1111111111111111011100",
	165: "11111111111111111101000",
	166: "11111111111111111101001",
	167: "111111111111111011110",
	168: "11111111111111111101010",
	169: "1111111111111111011101",
	170: "1111111111111111011110",
	171: "111111111111111111110000",
	172: "111111111111111011111",
	173: "1111111111111111011111",
	174: "11111111111111111101011",
	175: "11111111111111111101100",
	176: "111111111111111100000",
	177: "111111111111111100001",
	178: "1111111111111111100000",
	179: "111111111111111100010",
	180: "11111111111111111101101",
	181: "1111111111111111100001",
	182: "11111111111111111101110",
	183: "11111111111111111101111",
	184: "11111111111111101010",
	185: "1111111111111111100010",
	186: "1111111111111111100011",
	187: "1111111111111111100100",
	188: "11111111111111111110000",
	189: "1111111111111111100101",
	190: "1111111111111111100110",
	191: "11111111111111111110001",
	192: "11111111111111111111100000",
	193: "11111111111111111111100001",
	194: "11111111111111101011",
	195: "1111111111111110001",
	196: "1111111111111111100111",
	197: "11111111111111111110010",
	198: "1111111111111111101000",
	199: "1111111111111111111101100",
	200: "11111111111111111111100010",
	201: "11111111111111111111100011",
	202: "11111111111111111111100100",
	203: "111111111111111111111011110",
	204: "111111111111111111111011111",
	205: "11111111111111111111100101",
	206: "111111111111111111110001",
	207: "1111111111111111111101101",
	208: "1111111111111110010",
	209: "111111111111111100011",
	210: "11111111111111111111100110",
	211: "111111111111111111111100000",
	212: "111111111111111111111100001",
	213: "11111111111111111111100111",
	214: "111111111111111111111100010",
	215: "111111111111111111110010",
	216: "111111111111111100100",
	217: "111111111111111100101",
	218: "11111111111111111111101000",
	219: "11111111111111111111101001",
	220: "1111111111111111111111111101",
	221: "111111111111111111111100011",
	222: "111111111111111111111100100",
	223: "111111111111111111111100101",
	224: "11111111111111101100",
	225: "111111111111111111110011",
	226: "11111111111111101101",
	227: "111111111111111100110",
	228: "1111111111111111101001",
	229: "111111111111111100111",
	230: "111111111111111101000",
	231: "11111111111111111110011",
	232: "1111111111111111101010",
	233: "1111111111111111101011",
	234: "1111111111111111111101110",
	235: "1111111111111111111101111",
	236: "111111111111111111110100",
	237: "111111111111111111110101",
	238: "11111111111111111111101010",
	239: "11111111111111111110100",
	240: "11111111111111111111101011",
	241: "111111111111111111111100110",
	242: "11111111111111111111101100",
	243: "11111111111111111111101101",
	244: "111111111111111111111100111",
	245: "111111111111111111111101000",
	246: "111111111111111111111101001",
	247: "111111111111111111111101010",
	248: "111111111111111111111101011",
	249: "1111111111111111111111111110",
	250: "111111111111111111111101100",
	251: "111111111111111111111101101",
	252: "111111111111111111111101110",
	253: "111111111111111111111101111",
	254: "111111111111111111111110000",
	255: "11111111111111111111101110",
	256: "111111111111111111111111111111",
}