qpack.go

     1  // Copyright 2025 The Go Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  package http3
     6  
     7  import (
     8  	"errors"
     9  	"io"
    10  
    11  	"golang.org/x/net/http/httpguts"
    12  	"golang.org/x/net/http2/hpack"
    13  )
    14  
    15  // QPACK (RFC 9204) header compression wire encoding.
    16  // https://www.rfc-editor.org/rfc/rfc9204.html
    17  
    18  // tableType is the static or dynamic table.
    19  //
    20  // The T bit in QPACK instructions indicates whether a table index refers to
    21  // the dynamic (T=0) or static (T=1) table. tableTypeForTBit and tableType.tbit
    22  // convert a T bit from the wire encoding to/from a tableType.
    23  type tableType byte
    24  
    25  const (
    26  	dynamicTable = 0x00 // T=0, dynamic table
    27  	staticTable  = 0xff // T=1, static table
    28  )
    29  
    30  // tableTypeForTbit returns the table type corresponding to a T bit value.
    31  // The input parameter contains a byte masked to contain only the T bit.
    32  func tableTypeForTbit(bit byte) tableType {
    33  	if bit == 0 {
    34  		return dynamicTable
    35  	}
    36  	return staticTable
    37  }
    38  
    39  // tbit produces the T bit corresponding to the table type.
    40  // The input parameter contains a byte with the T bit set to 1,
    41  // and the return is either the input or 0 depending on the table type.
    42  func (t tableType) tbit(bit byte) byte {
    43  	return bit & byte(t)
    44  }
    45  
    46  // indexType indicates a literal's indexing status.
    47  //
    48  // The N bit in QPACK instructions indicates whether a literal is "never-indexed".
    49  // A never-indexed literal (N=1) must not be encoded as an indexed literal if it
    50  // forwarded on another connection.
    51  //
    52  // (See https://www.rfc-editor.org/rfc/rfc9204.html#section-7.1 for details on the
    53  // security reasons for never-indexed literals.)
    54  type indexType byte
    55  
    56  const (
    57  	mayIndex   = 0x00 // N=0, not a never-indexed literal
    58  	neverIndex = 0xff // N=1, never-indexed literal
    59  )
    60  
    61  // indexTypeForNBit returns the index type corresponding to a N bit value.
    62  // The input parameter contains a byte masked to contain only the N bit.
    63  func indexTypeForNBit(bit byte) indexType {
    64  	if bit == 0 {
    65  		return mayIndex
    66  	}
    67  	return neverIndex
    68  }
    69  
    70  // nbit produces the N bit corresponding to the table type.
    71  // The input parameter contains a byte with the N bit set to 1,
    72  // and the return is either the input or 0 depending on the table type.
    73  func (t indexType) nbit(bit byte) byte {
    74  	return bit & byte(t)
    75  }
    76  
    77  // Indexed Field Line:
    78  //
    79  //       0   1   2   3   4   5   6   7
    80  //     +---+---+---+---+---+---+---+---+
    81  //     | 1 | T |      Index (6+)       |
    82  //     +---+---+-----------------------+
    83  //
    84  // https://www.rfc-editor.org/rfc/rfc9204.html#section-4.5.2
    85  
    86  func appendIndexedFieldLine(b []byte, ttype tableType, index int) []byte {
    87  	const tbit = 0b_01000000
    88  	return appendPrefixedInt(b, 0b_1000_0000|ttype.tbit(tbit), 6, int64(index))
    89  }
    90  
    91  func (st *stream) decodeIndexedFieldLine(b byte) (itype indexType, name, value string, err error) {
    92  	index, err := st.readPrefixedIntWithByte(b, 6)
    93  	if err != nil {
    94  		return 0, "", "", err
    95  	}
    96  	const tbit = 0b_0100_0000
    97  	if tableTypeForTbit(b&tbit) == staticTable {
    98  		ent, err := staticTableEntry(index)
    99  		if err != nil {
   100  			return 0, "", "", err
   101  		}
   102  		return mayIndex, ent.name, ent.value, nil
   103  	} else {
   104  		return 0, "", "", errors.New("dynamic table is not supported yet")
   105  	}
   106  }
   107  
   108  // Literal Field Line With Name Reference:
   109  //
   110  //      0   1   2   3   4   5   6   7
   111  //     +---+---+---+---+---+---+---+---+
   112  //     | 0 | 1 | N | T |Name Index (4+)|
   113  //     +---+---+---+---+---------------+
   114  //     | H |     Value Length (7+)     |
   115  //     +---+---------------------------+
   116  //     |  Value String (Length bytes)  |
   117  //     +-------------------------------+
   118  //
   119  // https://www.rfc-editor.org/rfc/rfc9204.html#section-4.5.4
   120  
   121  func appendLiteralFieldLineWithNameReference(b []byte, ttype tableType, itype indexType, nameIndex int, value string) []byte {
   122  	const tbit = 0b_0001_0000
   123  	const nbit = 0b_0010_0000
   124  	b = appendPrefixedInt(b, 0b_0100_0000|itype.nbit(nbit)|ttype.tbit(tbit), 4, int64(nameIndex))
   125  	b = appendPrefixedString(b, 0, 7, value)
   126  	return b
   127  }
   128  
   129  func (st *stream) decodeLiteralFieldLineWithNameReference(b byte) (itype indexType, name, value string, err error) {
   130  	nameIndex, err := st.readPrefixedIntWithByte(b, 4)
   131  	if err != nil {
   132  		return 0, "", "", err
   133  	}
   134  
   135  	const tbit = 0b_0001_0000
   136  	if tableTypeForTbit(b&tbit) == staticTable {
   137  		ent, err := staticTableEntry(nameIndex)
   138  		if err != nil {
   139  			return 0, "", "", err
   140  		}
   141  		name = ent.name
   142  	} else {
   143  		return 0, "", "", errors.New("dynamic table is not supported yet")
   144  	}
   145  
   146  	_, value, err = st.readPrefixedString(7)
   147  	if err != nil {
   148  		return 0, "", "", err
   149  	}
   150  
   151  	const nbit = 0b_0010_0000
   152  	itype = indexTypeForNBit(b & nbit)
   153  
   154  	return itype, name, value, nil
   155  }
   156  
   157  // Literal Field Line with Literal Name:
   158  //
   159  //       0   1   2   3   4   5   6   7
   160  //     +---+---+---+---+---+---+---+---+
   161  //     | 0 | 0 | 1 | N | H |NameLen(3+)|
   162  //     +---+---+---+---+---+-----------+
   163  //     |  Name String (Length bytes)   |
   164  //     +---+---------------------------+
   165  //     | H |     Value Length (7+)     |
   166  //     +---+---------------------------+
   167  //     |  Value String (Length bytes)  |
   168  //     +-------------------------------+
   169  //
   170  // https://www.rfc-editor.org/rfc/rfc9204.html#section-4.5.6
   171  
   172  func appendLiteralFieldLineWithLiteralName(b []byte, itype indexType, name, value string) []byte {
   173  	const nbit = 0b_0001_0000
   174  	b = appendPrefixedString(b, 0b_0010_0000|itype.nbit(nbit), 3, name)
   175  	b = appendPrefixedString(b, 0, 7, value)
   176  	return b
   177  }
   178  
   179  func (st *stream) decodeLiteralFieldLineWithLiteralName(b byte) (itype indexType, name, value string, err error) {
   180  	name, err = st.readPrefixedStringWithByte(b, 3)
   181  	if err != nil {
   182  		return 0, "", "", err
   183  	}
   184  	_, value, err = st.readPrefixedString(7)
   185  	if err != nil {
   186  		return 0, "", "", err
   187  	}
   188  	const nbit = 0b_0001_0000
   189  	itype = indexTypeForNBit(b & nbit)
   190  	return itype, name, value, nil
   191  }
   192  
   193  // Prefixed-integer encoding from RFC 7541, section 5.1
   194  //
   195  // Prefixed integers consist of some number of bits of data,
   196  // N bits of encoded integer, and 0 or more additional bytes of
   197  // encoded integer.
   198  //
   199  // The RFCs represent this as, for example:
   200  //
   201  //       0   1   2   3   4   5   6   7
   202  //     +---+---+---+---+---+---+---+---+
   203  //     | 0 | 0 | 1 |   Capacity (5+)   |
   204  //     +---+---+---+-------------------+
   205  //
   206  // "Capacity" is an integer with a 5-bit prefix.
   207  //
   208  // In the following functions, a "prefixLen" parameter is the number
   209  // of integer bits in the first byte (5 in the above example), and
   210  // a "firstByte" parameter is a byte containing the first byte of
   211  // the encoded value (0x001x_xxxx in the above example).
   212  //
   213  // https://www.rfc-editor.org/rfc/rfc9204.html#section-4.1.1
   214  // https://www.rfc-editor.org/rfc/rfc7541#section-5.1
   215  
   216  // readPrefixedInt reads an RFC 7541 prefixed integer from st.
   217  func (st *stream) readPrefixedInt(prefixLen uint8) (firstByte byte, v int64, err error) {
   218  	firstByte, err = st.ReadByte()
   219  	if err != nil {
   220  		return 0, 0, errQPACKDecompressionFailed
   221  	}
   222  	v, err = st.readPrefixedIntWithByte(firstByte, prefixLen)
   223  	return firstByte, v, err
   224  }
   225  
   226  // readPrefixedIntWithByte reads an RFC 7541 prefixed integer from st.
   227  // The first byte has already been read from the stream.
   228  func (st *stream) readPrefixedIntWithByte(firstByte byte, prefixLen uint8) (v int64, err error) {
   229  	prefixMask := (byte(1) << prefixLen) - 1
   230  	v = int64(firstByte & prefixMask)
   231  	if v != int64(prefixMask) {
   232  		return v, nil
   233  	}
   234  	m := 0
   235  	for {
   236  		b, err := st.ReadByte()
   237  		if err != nil {
   238  			return 0, errQPACKDecompressionFailed
   239  		}
   240  		v += int64(b&127) << m
   241  		m += 7
   242  		if b&128 == 0 {
   243  			break
   244  		}
   245  	}
   246  	return v, err
   247  }
   248  
   249  // appendPrefixedInt appends an RFC 7541 prefixed integer to b.
   250  //
   251  // The firstByte parameter includes the non-integer bits of the first byte.
   252  // The other bits must be zero.
   253  func appendPrefixedInt(b []byte, firstByte byte, prefixLen uint8, i int64) []byte {
   254  	u := uint64(i)
   255  	prefixMask := (uint64(1) << prefixLen) - 1
   256  	if u < prefixMask {
   257  		return append(b, firstByte|byte(u))
   258  	}
   259  	b = append(b, firstByte|byte(prefixMask))
   260  	u -= prefixMask
   261  	for u >= 128 {
   262  		b = append(b, 0x80|byte(u&0x7f))
   263  		u >>= 7
   264  	}
   265  	return append(b, byte(u))
   266  }
   267  
   268  // String literal encoding from RFC 7541, section 5.2
   269  //
   270  // String literals consist of a single bit flag indicating
   271  // whether the string is Huffman-encoded, a prefixed integer (see above),
   272  // and the string.
   273  //
   274  // https://www.rfc-editor.org/rfc/rfc9204.html#section-4.1.2
   275  // https://www.rfc-editor.org/rfc/rfc7541#section-5.2
   276  
   277  // readPrefixedString reads an RFC 7541 string from st.
   278  func (st *stream) readPrefixedString(prefixLen uint8) (firstByte byte, s string, err error) {
   279  	firstByte, err = st.ReadByte()
   280  	if err != nil {
   281  		return 0, "", errQPACKDecompressionFailed
   282  	}
   283  	s, err = st.readPrefixedStringWithByte(firstByte, prefixLen)
   284  	return firstByte, s, err
   285  }
   286  
   287  // readPrefixedStringWithByte reads an RFC 7541 string from st.
   288  // The first byte has already been read from the stream.
   289  func (st *stream) readPrefixedStringWithByte(firstByte byte, prefixLen uint8) (s string, err error) {
   290  	size, err := st.readPrefixedIntWithByte(firstByte, prefixLen)
   291  	if err != nil {
   292  		return "", errQPACKDecompressionFailed
   293  	}
   294  
   295  	hbit := byte(1) << prefixLen
   296  	isHuffman := firstByte&hbit != 0
   297  
   298  	// TODO: Avoid allocating here.
   299  	data := make([]byte, size)
   300  	if _, err := io.ReadFull(st, data); err != nil {
   301  		return "", errQPACKDecompressionFailed
   302  	}
   303  	if isHuffman {
   304  		// TODO: Move Huffman functions into a new package that hpack (HTTP/2)
   305  		// and this package can both import. Most of the hpack package isn't
   306  		// relevant to HTTP/3.
   307  		s, err := hpack.HuffmanDecodeToString(data)
   308  		if err != nil {
   309  			return "", errQPACKDecompressionFailed
   310  		}
   311  		return s, nil
   312  	}
   313  	return string(data), nil
   314  }
   315  
   316  // appendPrefixedString appends an RFC 7541 string to st,
   317  // applying Huffman encoding and setting the H bit (indicating Huffman encoding)
   318  // when appropriate.
   319  //
   320  // The firstByte parameter includes the non-integer bits of the first byte.
   321  // The other bits must be zero.
   322  func appendPrefixedString(b []byte, firstByte byte, prefixLen uint8, s string) []byte {
   323  	huffmanLen := hpack.HuffmanEncodeLength(s)
   324  	if huffmanLen < uint64(len(s)) {
   325  		hbit := byte(1) << prefixLen
   326  		b = appendPrefixedInt(b, firstByte|hbit, prefixLen, int64(huffmanLen))
   327  		b = hpack.AppendHuffmanString(b, s)
   328  	} else {
   329  		b = appendPrefixedInt(b, firstByte, prefixLen, int64(len(s)))
   330  		b = append(b, s...)
   331  	}
   332  	return b
   333  }
   334  
   335  // validWireHeaderFieldName reports whether v is a valid header field
   336  // name (key). See httpguts.ValidHeaderFieldName for the base rules.
   337  //
   338  // Further, http3 says:
   339  // "A request or response containing uppercase characters in field names MUST
   340  // be treated as malformed."
   341  //
   342  // This function does not validate whether a pseudo-header field name is valid.
   343  func validWireHeaderFieldName(v string) bool {
   344  	if len(v) == 0 {
   345  		return false
   346  	}
   347  	for _, r := range v {
   348  		if !httpguts.IsTokenRune(r) {
   349  			return false
   350  		}
   351  		if 'A' <= r && r <= 'Z' {
   352  			return false
   353  		}
   354  	}
   355  	return true
   356  }
   357
View as plain text