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