// Copyright 2014 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// Package hpack implements HPACK, a compression format for // efficiently representing HTTP header fields in the context of HTTP/2. // // See http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-09
package hpack import ( ) // A DecodingError is something the spec defines as a decoding error. type DecodingError struct { Err error } func ( DecodingError) () string { return fmt.Sprintf("decoding error: %v", .Err) } // An InvalidIndexError is returned when an encoder references a table // entry before the static table or after the end of the dynamic table. type InvalidIndexError int func ( InvalidIndexError) () string { return fmt.Sprintf("invalid indexed representation index %d", int()) } // A HeaderField is a name-value pair. Both the name and value are // treated as opaque sequences of octets. type HeaderField struct { Name, Value string // Sensitive means that this header field should never be // indexed. Sensitive bool } // IsPseudo reports whether the header field is an http2 pseudo header. // That is, it reports whether it starts with a colon. // It is not otherwise guaranteed to be a valid pseudo header field, // though. func ( HeaderField) () bool { return len(.Name) != 0 && .Name[0] == ':' } func ( HeaderField) () string { var string if .Sensitive { = " (sensitive)" } return fmt.Sprintf("header field %q = %q%s", .Name, .Value, ) } // Size returns the size of an entry per RFC 7541 section 4.1. func ( HeaderField) () uint32 { // http://http2.github.io/http2-spec/compression.html#rfc.section.4.1 // "The size of the dynamic table is the sum of the size of // its entries. The size of an entry is the sum of its name's // length in octets (as defined in Section 5.2), its value's // length in octets (see Section 5.2), plus 32. The size of // an entry is calculated using the length of the name and // value without any Huffman encoding applied." // This can overflow if somebody makes a large HeaderField // Name and/or Value by hand, but we don't care, because that // won't happen on the wire because the encoding doesn't allow // it. return uint32(len(.Name) + len(.Value) + 32) } // A Decoder is the decoding context for incremental processing of // header blocks. type Decoder struct { dynTab dynamicTable emit func(f HeaderField) emitEnabled bool // whether calls to emit are enabled maxStrLen int // 0 means unlimited // buf is the unparsed buffer. It's only written to // saveBuf if it was truncated in the middle of a header // block. Because it's usually not owned, we can only // process it under Write. buf []byte // not owned; only valid during Write // saveBuf is previous data passed to Write which we weren't able // to fully parse before. Unlike buf, we own this data. saveBuf bytes.Buffer firstField bool // processing the first field of the header block } // NewDecoder returns a new decoder with the provided maximum dynamic // table size. The emitFunc will be called for each valid field // parsed, in the same goroutine as calls to Write, before Write returns. func ( uint32, func( HeaderField)) *Decoder { := &Decoder{ emit: , emitEnabled: true, firstField: true, } .dynTab.table.init() .dynTab.allowedMaxSize = .dynTab.setMaxSize() return } // ErrStringLength is returned by Decoder.Write when the max string length // (as configured by Decoder.SetMaxStringLength) would be violated. var ErrStringLength = errors.New("hpack: string too long") // SetMaxStringLength sets the maximum size of a HeaderField name or // value string. If a string exceeds this length (even after any // decompression), Write will return ErrStringLength. // A value of 0 means unlimited and is the default from NewDecoder. func ( *Decoder) ( int) { .maxStrLen = } // SetEmitFunc changes the callback used when new header fields // are decoded. // It must be non-nil. It does not affect EmitEnabled. func ( *Decoder) ( func( HeaderField)) { .emit = } // SetEmitEnabled controls whether the emitFunc provided to NewDecoder // should be called. The default is true. // // This facility exists to let servers enforce MAX_HEADER_LIST_SIZE // while still decoding and keeping in-sync with decoder state, but // without doing unnecessary decompression or generating unnecessary // garbage for header fields past the limit. func ( *Decoder) ( bool) { .emitEnabled = } // EmitEnabled reports whether calls to the emitFunc provided to NewDecoder // are currently enabled. The default is true. func ( *Decoder) () bool { return .emitEnabled } // TODO: add method *Decoder.Reset(maxSize, emitFunc) to let callers re-use Decoders and their // underlying buffers for garbage reasons. func ( *Decoder) ( uint32) { .dynTab.setMaxSize() } // SetAllowedMaxDynamicTableSize sets the upper bound that the encoded // stream (via dynamic table size updates) may set the maximum size // to. func ( *Decoder) ( uint32) { .dynTab.allowedMaxSize = } type dynamicTable struct { // http://http2.github.io/http2-spec/compression.html#rfc.section.2.3.2 table headerFieldTable size uint32 // in bytes maxSize uint32 // current maxSize allowedMaxSize uint32 // maxSize may go up to this, inclusive } func ( *dynamicTable) ( uint32) { .maxSize = .evict() } func ( *dynamicTable) ( HeaderField) { .table.addEntry() .size += .Size() .evict() } // If we're too big, evict old stuff. func ( *dynamicTable) () { var int for .size > .maxSize && < .table.len() { .size -= .table.ents[].Size() ++ } .table.evictOldest() } func ( *Decoder) () int { // This should never overflow. RFC 7540 Section 6.5.2 limits the size of // the dynamic table to 2^32 bytes, where each entry will occupy more than // one byte. Further, the staticTable has a fixed, small length. return .dynTab.table.len() + staticTable.len() } func ( *Decoder) ( uint64) ( HeaderField, bool) { // See Section 2.3.3. if == 0 { return } if <= uint64(staticTable.len()) { return staticTable.ents[-1], true } if > uint64(.maxTableIndex()) { return } // In the dynamic table, newer entries have lower indices. // However, dt.ents[0] is the oldest entry. Hence, dt.ents is // the reversed dynamic table. := .dynTab.table return .ents[.len()-(int()-staticTable.len())], true } // Decode decodes an entire block. // // TODO: remove this method and make it incremental later? This is // easier for debugging now. func ( *Decoder) ( []byte) ([]HeaderField, error) { var []HeaderField := .emit defer func() { .emit = }() .emit = func( HeaderField) { = append(, ) } if , := .Write(); != nil { return nil, } if := .Close(); != nil { return nil, } return , nil } // Close declares that the decoding is complete and resets the Decoder // to be reused again for a new header block. If there is any remaining // data in the decoder's buffer, Close returns an error. func ( *Decoder) () error { if .saveBuf.Len() > 0 { .saveBuf.Reset() return DecodingError{errors.New("truncated headers")} } .firstField = true return nil } func ( *Decoder) ( []byte) ( int, error) { if len() == 0 { // Prevent state machine CPU attacks (making us redo // work up to the point of finding out we don't have // enough data) return } // Only copy the data if we have to. Optimistically assume // that p will contain a complete header block. if .saveBuf.Len() == 0 { .buf = } else { .saveBuf.Write() .buf = .saveBuf.Bytes() .saveBuf.Reset() } for len(.buf) > 0 { = .parseHeaderFieldRepr() if == errNeedMore { // Extra paranoia, making sure saveBuf won't // get too large. All the varint and string // reading code earlier should already catch // overlong things and return ErrStringLength, // but keep this as a last resort. const = 8 // conservative if .maxStrLen != 0 && int64(len(.buf)) > 2*(int64(.maxStrLen)+) { return 0, ErrStringLength } .saveBuf.Write(.buf) return len(), nil } .firstField = false if != nil { break } } return len(), } // errNeedMore is an internal sentinel error value that means the // buffer is truncated and we need to read more data before we can // continue parsing. var errNeedMore = errors.New("need more data") type indexType int const ( indexedTrue indexType = iota indexedFalse indexedNever ) func ( indexType) () bool { return == indexedTrue } func ( indexType) () bool { return == indexedNever } // returns errNeedMore if there isn't enough data available. // any other error is fatal. // consumes d.buf iff it returns nil. // precondition: must be called with len(d.buf) > 0 func ( *Decoder) () error { := .buf[0] switch { case &128 != 0: // Indexed representation. // High bit set? // http://http2.github.io/http2-spec/compression.html#rfc.section.6.1 return .parseFieldIndexed() case &192 == 64: // 6.2.1 Literal Header Field with Incremental Indexing // 0b10xxxxxx: top two bits are 10 // http://http2.github.io/http2-spec/compression.html#rfc.section.6.2.1 return .parseFieldLiteral(6, indexedTrue) case &240 == 0: // 6.2.2 Literal Header Field without Indexing // 0b0000xxxx: top four bits are 0000 // http://http2.github.io/http2-spec/compression.html#rfc.section.6.2.2 return .parseFieldLiteral(4, indexedFalse) case &240 == 16: // 6.2.3 Literal Header Field never Indexed // 0b0001xxxx: top four bits are 0001 // http://http2.github.io/http2-spec/compression.html#rfc.section.6.2.3 return .parseFieldLiteral(4, indexedNever) case &224 == 32: // 6.3 Dynamic Table Size Update // Top three bits are '001'. // http://http2.github.io/http2-spec/compression.html#rfc.section.6.3 return .parseDynamicTableSizeUpdate() } return DecodingError{errors.New("invalid encoding")} } // (same invariants and behavior as parseHeaderFieldRepr) func ( *Decoder) () error { := .buf , , := readVarInt(7, ) if != nil { return } , := .at() if ! { return DecodingError{InvalidIndexError()} } .buf = return .callEmit(HeaderField{Name: .Name, Value: .Value}) } // (same invariants and behavior as parseHeaderFieldRepr) func ( *Decoder) ( uint8, indexType) error { := .buf , , := readVarInt(, ) if != nil { return } var HeaderField := .emitEnabled || .indexed() if > 0 { , := .at() if ! { return DecodingError{InvalidIndexError()} } .Name = .Name } else { .Name, , = .readString(, ) if != nil { return } } .Value, , = .readString(, ) if != nil { return } .buf = if .indexed() { .dynTab.add() } .Sensitive = .sensitive() return .callEmit() } func ( *Decoder) ( HeaderField) error { if .maxStrLen != 0 { if len(.Name) > .maxStrLen || len(.Value) > .maxStrLen { return ErrStringLength } } if .emitEnabled { .emit() } return nil } // (same invariants and behavior as parseHeaderFieldRepr) func ( *Decoder) () error { // RFC 7541, sec 4.2: This dynamic table size update MUST occur at the // beginning of the first header block following the change to the dynamic table size. if !.firstField && .dynTab.size > 0 { return DecodingError{errors.New("dynamic table size update MUST occur at the beginning of a header block")} } := .buf , , := readVarInt(5, ) if != nil { return } if > uint64(.dynTab.allowedMaxSize) { return DecodingError{errors.New("dynamic table size update too large")} } .dynTab.setMaxSize(uint32()) .buf = return nil } var errVarintOverflow = DecodingError{errors.New("varint integer overflow")} // readVarInt reads an unsigned variable length integer off the // beginning of p. n is the parameter as described in // http://http2.github.io/http2-spec/compression.html#rfc.section.5.1. // // n must always be between 1 and 8. // // The returned remain buffer is either a smaller suffix of p, or err != nil. // The error is errNeedMore if p doesn't contain a complete integer. func readVarInt( byte, []byte) ( uint64, []byte, error) { if < 1 || > 8 { panic("bad n") } if len() == 0 { return 0, , errNeedMore } = uint64([0]) if < 8 { &= (1 << uint64()) - 1 } if < (1<<uint64())-1 { return , [1:], nil } := = [1:] var uint64 for len() > 0 { := [0] = [1:] += uint64(&127) << if &128 == 0 { return , , nil } += 7 if >= 63 { // TODO: proper overflow check. making this up. return 0, , errVarintOverflow } } return 0, , errNeedMore } // readString decodes an hpack string from p. // // wantStr is whether s will be used. If false, decompression and // []byte->string garbage are skipped if s will be ignored // anyway. This does mean that huffman decoding errors for non-indexed // strings past the MAX_HEADER_LIST_SIZE are ignored, but the server // is returning an error anyway, and because they're not indexed, the error // won't affect the decoding state. func ( *Decoder) ( []byte, bool) ( string, []byte, error) { if len() == 0 { return "", , errNeedMore } := [0]&128 != 0 , , := readVarInt(7, ) if != nil { return "", , } if .maxStrLen != 0 && > uint64(.maxStrLen) { return "", nil, ErrStringLength } if uint64(len()) < { return "", , errNeedMore } if ! { if { = string([:]) } return , [:], nil } if { := bufPool.Get().(*bytes.Buffer) .Reset() // don't trust others defer bufPool.Put() if := huffmanDecode(, .maxStrLen, [:]); != nil { .Reset() return "", nil, } = .String() .Reset() // be nice to GC } return , [:], nil }