text:
// 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

import (
	"bytes"
	"errors"
	"io"
	"sync"
)

var bufPool = sync.Pool{
	New: func() interface{} { return new(bytes.Buffer) },
}

// HuffmanDecode decodes the string in v and writes the expanded
// result to w, returning the number of bytes written to w and the
// Write call's return value. At most one Write call is made.
func HuffmanDecode(w io.Writer, v []byte) (int, error) {
	buf := bufPool.Get().(*bytes.Buffer)
	buf.Reset()
	defer bufPool.Put(buf)
	if err := huffmanDecode(buf, 0, v); err != nil {
		return 0, err
	}
	return w.Write(buf.Bytes())
}

// HuffmanDecodeToString decodes the string in v.
func HuffmanDecodeToString(v []byte) (string, error) {
	buf := bufPool.Get().(*bytes.Buffer)
	buf.Reset()
	defer bufPool.Put(buf)
	if err := huffmanDecode(buf, 0, v); err != nil {
		return "", err
	}
	return buf.String(), nil
}

// ErrInvalidHuffman is returned for errors found decoding
// Huffman-encoded strings.
var ErrInvalidHuffman = errors.New("hpack: invalid Huffman-encoded data")

// huffmanDecode decodes v to buf.
// If maxLen is greater than 0, attempts to write more to buf than
// maxLen bytes will return ErrStringLength.
func huffmanDecode(buf *bytes.Buffer, maxLen int, v []byte) error {
	n := rootHuffmanNode
	// cur is the bit buffer that has not been fed into n.
	// cbits is the number of low order bits in cur that are valid.
	// sbits is the number of bits of the symbol prefix being decoded.
	cur, cbits, sbits := uint(0), uint8(0), uint8(0)
	for _, b := range v {
		cur = cur<<8 | uint(b)
		cbits += 8
		sbits += 8
		for cbits >= 8 {
			idx := byte(cur >> (cbits - 8))
			n = n.children[idx]
			if n == nil {
				return ErrInvalidHuffman
			}
			if n.children == nil {
				if maxLen != 0 && buf.Len() == maxLen {
					return ErrStringLength
				}
				buf.WriteByte(n.sym)
				cbits -= n.codeLen
				n = rootHuffmanNode
				sbits = cbits
			} else {
				cbits -= 8
			}
		}
	}
	for cbits > 0 {
		n = n.children[byte(cur<<(8-cbits))]
		if n == nil {
			return ErrInvalidHuffman
		}
		if n.children != nil || n.codeLen > cbits {
			break
		}
		if maxLen != 0 && buf.Len() == maxLen {
			return ErrStringLength
		}
		buf.WriteByte(n.sym)
		cbits -= n.codeLen
		n = rootHuffmanNode
		sbits = cbits
	}
	if sbits > 7 {
		// Either there was an incomplete symbol, or overlong padding.
		// Both are decoding errors per RFC 7541 section 5.2.
		return ErrInvalidHuffman
	}
	if mask := uint(1<<cbits - 1); cur&mask != mask {
		// Trailing bits must be a prefix of EOS per RFC 7541 section 5.2.
		return ErrInvalidHuffman
	}

	return nil
}

type node struct {
	// children is non-nil for internal nodes
	children []*node

	// The following are only valid if children is nil:
	codeLen uint8 // number of bits that led to the output of sym
	sym     byte  // output symbol
}

func newInternalNode() *node {
	return &node{children: make([]*node, 256)}
}

var rootHuffmanNode = newInternalNode()

func init() {
	if len(huffmanCodes) != 256 {
		panic("unexpected size")
	}
	for i, code := range huffmanCodes {
		addDecoderNode(byte(i), code, huffmanCodeLen[i])
	}
}

func addDecoderNode(sym byte, code uint32, codeLen uint8) {
	cur := rootHuffmanNode
	for codeLen > 8 {
		codeLen -= 8
		i := uint8(code >> codeLen)
		if cur.children[i] == nil {
			cur.children[i] = newInternalNode()
		}
		cur = cur.children[i]
	}
	shift := 8 - codeLen
	start, end := int(uint8(code<<shift)), int(1<<shift)
	for i := start; i < start+end; i++ {
		cur.children[i] = &node{sym: sym, codeLen: codeLen}
	}
}

// AppendHuffmanString appends s, as encoded in Huffman codes, to dst
// and returns the extended buffer.
func AppendHuffmanString(dst []byte, s string) []byte {
	rembits := uint8(8)

	for i := 0; i < len(s); i++ {
		if rembits == 8 {
			dst = append(dst, 0)
		}
		dst, rembits = appendByteToHuffmanCode(dst, rembits, s[i])
	}

	if rembits < 8 {
		// special EOS symbol
		code := uint32(0x3fffffff)
		nbits := uint8(30)

		t := uint8(code >> (nbits - rembits))
		dst[len(dst)-1] |= t
	}

	return dst
}

// HuffmanEncodeLength returns the number of bytes required to encode
// s in Huffman codes. The result is round up to byte boundary.
func HuffmanEncodeLength(s string) uint64 {
	n := uint64(0)
	for i := 0; i < len(s); i++ {
		n += uint64(huffmanCodeLen[s[i]])
	}
	return (n + 7) / 8
}

// appendByteToHuffmanCode appends Huffman code for c to dst and
// returns the extended buffer and the remaining bits in the last
// element. The appending is not byte aligned and the remaining bits
// in the last element of dst is given in rembits.
func appendByteToHuffmanCode(dst []byte, rembits uint8, c byte) ([]byte, uint8) {
	code := huffmanCodes[c]
	nbits := huffmanCodeLen[c]

	for {
		if rembits > nbits {
			t := uint8(code << (rembits - nbits))
			dst[len(dst)-1] |= t
			rembits -= nbits
			break
		}

		t := uint8(code >> (nbits - rembits))
		dst[len(dst)-1] |= t

		nbits -= rembits
		rembits = 8

		if nbits == 0 {
			break
		}

		dst = append(dst, 0)
	}

	return dst, rembits
}


text:
// 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 (
	"bytes"
	"errors"
	"fmt"
)

// A DecodingError is something the spec defines as a decoding error.
type DecodingError struct {
	Err error
}

func (de DecodingError) Error() string {
	return fmt.Sprintf("decoding error: %v", de.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 (e InvalidIndexError) Error() string {
	return fmt.Sprintf("invalid indexed representation index %d", int(e))
}

// 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 (hf HeaderField) IsPseudo() bool {
	return len(hf.Name) != 0 && hf.Name[0] == ':'
}

func (hf HeaderField) String() string {
	var suffix string
	if hf.Sensitive {
		suffix = " (sensitive)"
	}
	return fmt.Sprintf("header field %q = %q%s", hf.Name, hf.Value, suffix)
}

// Size returns the size of an entry per RFC 7541 section 4.1.
func (hf HeaderField) Size() 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(hf.Name) + len(hf.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
}

// 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 NewDecoder(maxDynamicTableSize uint32, emitFunc func(f HeaderField)) *Decoder {
	d := &Decoder{
		emit:        emitFunc,
		emitEnabled: true,
	}
	d.dynTab.table.init()
	d.dynTab.allowedMaxSize = maxDynamicTableSize
	d.dynTab.setMaxSize(maxDynamicTableSize)
	return d
}

// 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 (d *Decoder) SetMaxStringLength(n int) {
	d.maxStrLen = n
}

// SetEmitFunc changes the callback used when new header fields
// are decoded.
// It must be non-nil. It does not affect EmitEnabled.
func (d *Decoder) SetEmitFunc(emitFunc func(f HeaderField)) {
	d.emit = emitFunc
}

// 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 (d *Decoder) SetEmitEnabled(v bool) { d.emitEnabled = v }

// EmitEnabled reports whether calls to the emitFunc provided to NewDecoder
// are currently enabled. The default is true.
func (d *Decoder) EmitEnabled() bool { return d.emitEnabled }

// TODO: add method *Decoder.Reset(maxSize, emitFunc) to let callers re-use Decoders and their
// underlying buffers for garbage reasons.

func (d *Decoder) SetMaxDynamicTableSize(v uint32) {
	d.dynTab.setMaxSize(v)
}

// SetAllowedMaxDynamicTableSize sets the upper bound that the encoded
// stream (via dynamic table size updates) may set the maximum size
// to.
func (d *Decoder) SetAllowedMaxDynamicTableSize(v uint32) {
	d.dynTab.allowedMaxSize = v
}

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 (dt *dynamicTable) setMaxSize(v uint32) {
	dt.maxSize = v
	dt.evict()
}

func (dt *dynamicTable) add(f HeaderField) {
	dt.table.addEntry(f)
	dt.size += f.Size()
	dt.evict()
}

// If we're too big, evict old stuff.
func (dt *dynamicTable) evict() {
	var n int
	for dt.size > dt.maxSize && n < dt.table.len() {
		dt.size -= dt.table.ents[n].Size()
		n++
	}
	dt.table.evictOldest(n)
}

func (d *Decoder) maxTableIndex() 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 d.dynTab.table.len() + staticTable.len()
}

func (d *Decoder) at(i uint64) (hf HeaderField, ok bool) {
	// See Section 2.3.3.
	if i == 0 {
		return
	}
	if i <= uint64(staticTable.len()) {
		return staticTable.ents[i-1], true
	}
	if i > uint64(d.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.
	dt := d.dynTab.table
	return dt.ents[dt.len()-(int(i)-staticTable.len())], true
}

// Decode decodes an entire block.
//
// TODO: remove this method and make it incremental later? This is
// easier for debugging now.
func (d *Decoder) DecodeFull(p []byte) ([]HeaderField, error) {
	var hf []HeaderField
	saveFunc := d.emit
	defer func() { d.emit = saveFunc }()
	d.emit = func(f HeaderField) { hf = append(hf, f) }
	if _, err := d.Write(p); err != nil {
		return nil, err
	}
	if err := d.Close(); err != nil {
		return nil, err
	}
	return hf, nil
}

func (d *Decoder) Close() error {
	if d.saveBuf.Len() > 0 {
		d.saveBuf.Reset()
		return DecodingError{errors.New("truncated headers")}
	}
	return nil
}

func (d *Decoder) Write(p []byte) (n int, err error) {
	if len(p) == 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 d.saveBuf.Len() == 0 {
		d.buf = p
	} else {
		d.saveBuf.Write(p)
		d.buf = d.saveBuf.Bytes()
		d.saveBuf.Reset()
	}

	for len(d.buf) > 0 {
		err = d.parseHeaderFieldRepr()
		if err == 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 varIntOverhead = 8 // conservative
			if d.maxStrLen != 0 && int64(len(d.buf)) > 2*(int64(d.maxStrLen)+varIntOverhead) {
				return 0, ErrStringLength
			}
			d.saveBuf.Write(d.buf)
			return len(p), nil
		}
		if err != nil {
			break
		}
	}
	return len(p), err
}

// 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 (v indexType) indexed() bool   { return v == indexedTrue }
func (v indexType) sensitive() bool { return v == 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 (d *Decoder) parseHeaderFieldRepr() error {
	b := d.buf[0]
	switch {
	case b&128 != 0:
		// Indexed representation.
		// High bit set?
		// http://http2.github.io/http2-spec/compression.html#rfc.section.6.1
		return d.parseFieldIndexed()
	case b&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 d.parseFieldLiteral(6, indexedTrue)
	case b&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 d.parseFieldLiteral(4, indexedFalse)
	case b&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 d.parseFieldLiteral(4, indexedNever)
	case b&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 d.parseDynamicTableSizeUpdate()
	}

	return DecodingError{errors.New("invalid encoding")}
}

// (same invariants and behavior as parseHeaderFieldRepr)
func (d *Decoder) parseFieldIndexed() error {
	buf := d.buf
	idx, buf, err := readVarInt(7, buf)
	if err != nil {
		return err
	}
	hf, ok := d.at(idx)
	if !ok {
		return DecodingError{InvalidIndexError(idx)}
	}
	d.buf = buf
	return d.callEmit(HeaderField{Name: hf.Name, Value: hf.Value})
}

// (same invariants and behavior as parseHeaderFieldRepr)
func (d *Decoder) parseFieldLiteral(n uint8, it indexType) error {
	buf := d.buf
	nameIdx, buf, err := readVarInt(n, buf)
	if err != nil {
		return err
	}

	var hf HeaderField
	wantStr := d.emitEnabled || it.indexed()
	if nameIdx > 0 {
		ihf, ok := d.at(nameIdx)
		if !ok {
			return DecodingError{InvalidIndexError(nameIdx)}
		}
		hf.Name = ihf.Name
	} else {
		hf.Name, buf, err = d.readString(buf, wantStr)
		if err != nil {
			return err
		}
	}
	hf.Value, buf, err = d.readString(buf, wantStr)
	if err != nil {
		return err
	}
	d.buf = buf
	if it.indexed() {
		d.dynTab.add(hf)
	}
	hf.Sensitive = it.sensitive()
	return d.callEmit(hf)
}

func (d *Decoder) callEmit(hf HeaderField) error {
	if d.maxStrLen != 0 {
		if len(hf.Name) > d.maxStrLen || len(hf.Value) > d.maxStrLen {
			return ErrStringLength
		}
	}
	if d.emitEnabled {
		d.emit(hf)
	}
	return nil
}

// (same invariants and behavior as parseHeaderFieldRepr)
func (d *Decoder) parseDynamicTableSizeUpdate() error {
	buf := d.buf
	size, buf, err := readVarInt(5, buf)
	if err != nil {
		return err
	}
	if size > uint64(d.dynTab.allowedMaxSize) {
		return DecodingError{errors.New("dynamic table size update too large")}
	}
	d.dynTab.setMaxSize(uint32(size))
	d.buf = 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(n byte, p []byte) (i uint64, remain []byte, err error) {
	if n < 1 || n > 8 {
		panic("bad n")
	}
	if len(p) == 0 {
		return 0, p, errNeedMore
	}
	i = uint64(p[0])
	if n < 8 {
		i &= (1 << uint64(n)) - 1
	}
	if i < (1<<uint64(n))-1 {
		return i, p[1:], nil
	}

	origP := p
	p = p[1:]
	var m uint64
	for len(p) > 0 {
		b := p[0]
		p = p[1:]
		i += uint64(b&127) << m
		if b&128 == 0 {
			return i, p, nil
		}
		m += 7
		if m >= 63 { // TODO: proper overflow check. making this up.
			return 0, origP, errVarintOverflow
		}
	}
	return 0, origP, 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 (d *Decoder) readString(p []byte, wantStr bool) (s string, remain []byte, err error) {
	if len(p) == 0 {
		return "", p, errNeedMore
	}
	isHuff := p[0]&128 != 0
	strLen, p, err := readVarInt(7, p)
	if err != nil {
		return "", p, err
	}
	if d.maxStrLen != 0 && strLen > uint64(d.maxStrLen) {
		return "", nil, ErrStringLength
	}
	if uint64(len(p)) < strLen {
		return "", p, errNeedMore
	}
	if !isHuff {
		if wantStr {
			s = string(p[:strLen])
		}
		return s, p[strLen:], nil
	}

	if wantStr {
		buf := bufPool.Get().(*bytes.Buffer)
		buf.Reset() // don't trust others
		defer bufPool.Put(buf)
		if err := huffmanDecode(buf, d.maxStrLen, p[:strLen]); err != nil {
			buf.Reset()
			return "", nil, err
		}
		s = buf.String()
		buf.Reset() // be nice to GC
	}
	return s, p[strLen:], nil
}

repo_name: dan-v/dosxvpn

repo_language: Go

mime_type: text/x-shellscript


text:
// 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

import (
	"io"
)

const (
	uint32Max              = ^uint32(0)
	initialHeaderTableSize = 4096
)

type Encoder struct {
	dynTab dynamicTable
	// minSize is the minimum table size set by
	// SetMaxDynamicTableSize after the previous Header Table Size
	// Update.
	minSize uint32
	// maxSizeLimit is the maximum table size this encoder
	// supports. This will protect the encoder from too large
	// size.
	maxSizeLimit uint32
	// tableSizeUpdate indicates whether "Header Table Size
	// Update" is required.
	tableSizeUpdate bool
	w               io.Writer
	buf             []byte
}

// NewEncoder returns a new Encoder which performs HPACK encoding. An
// encoded data is written to w.
func NewEncoder(w io.Writer) *Encoder {
	e := &Encoder{
		minSize:         uint32Max,
		maxSizeLimit:    initialHeaderTableSize,
		tableSizeUpdate: false,
		w:               w,
	}
	e.dynTab.table.init()
	e.dynTab.setMaxSize(initialHeaderTableSize)
	return e
}

// WriteField encodes f into a single Write to e's underlying Writer.
// This function may also produce bytes for "Header Table Size Update"
// if necessary. If produced, it is done before encoding f.
func (e *Encoder) WriteField(f HeaderField) error {
	e.buf = e.buf[:0]

	if e.tableSizeUpdate {
		e.tableSizeUpdate = false
		if e.minSize < e.dynTab.maxSize {
			e.buf = appendTableSize(e.buf, e.minSize)
		}
		e.minSize = uint32Max
		e.buf = appendTableSize(e.buf, e.dynTab.maxSize)
	}

	idx, nameValueMatch := e.searchTable(f)
	if nameValueMatch {
		e.buf = appendIndexed(e.buf, idx)
	} else {
		indexing := e.shouldIndex(f)
		if indexing {
			e.dynTab.add(f)
		}

		if idx == 0 {
			e.buf = appendNewName(e.buf, f, indexing)
		} else {
			e.buf = appendIndexedName(e.buf, f, idx, indexing)
		}
	}
	n, err := e.w.Write(e.buf)
	if err == nil && n != len(e.buf) {
		err = io.ErrShortWrite
	}
	return err
}

// searchTable searches f in both stable and dynamic header tables.
// The static header table is searched first. Only when there is no
// exact match for both name and value, the dynamic header table is
// then searched. If there is no match, i is 0. If both name and value
// match, i is the matched index and nameValueMatch becomes true. If
// only name matches, i points to that index and nameValueMatch
// becomes false.
func (e *Encoder) searchTable(f HeaderField) (i uint64, nameValueMatch bool) {
	i, nameValueMatch = staticTable.search(f)
	if nameValueMatch {
		return i, true
	}

	j, nameValueMatch := e.dynTab.table.search(f)
	if nameValueMatch || (i == 0 && j != 0) {
		return j + uint64(staticTable.len()), nameValueMatch
	}

	return i, false
}

// SetMaxDynamicTableSize changes the dynamic header table size to v.
// The actual size is bounded by the value passed to
// SetMaxDynamicTableSizeLimit.
func (e *Encoder) SetMaxDynamicTableSize(v uint32) {
	if v > e.maxSizeLimit {
		v = e.maxSizeLimit
	}
	if v < e.minSize {
		e.minSize = v
	}
	e.tableSizeUpdate = true
	e.dynTab.setMaxSize(v)
}

// SetMaxDynamicTableSizeLimit changes the maximum value that can be
// specified in SetMaxDynamicTableSize to v. By default, it is set to
// 4096, which is the same size of the default dynamic header table
// size described in HPACK specification. If the current maximum
// dynamic header table size is strictly greater than v, "Header Table
// Size Update" will be done in the next WriteField call and the
// maximum dynamic header table size is truncated to v.
func (e *Encoder) SetMaxDynamicTableSizeLimit(v uint32) {
	e.maxSizeLimit = v
	if e.dynTab.maxSize > v {
		e.tableSizeUpdate = true
		e.dynTab.setMaxSize(v)
	}
}

// shouldIndex reports whether f should be indexed.
func (e *Encoder) shouldIndex(f HeaderField) bool {
	return !f.Sensitive && f.Size() <= e.dynTab.maxSize
}

// appendIndexed appends index i, as encoded in "Indexed Header Field"
// representation, to dst and returns the extended buffer.
func appendIndexed(dst []byte, i uint64) []byte {
	first := len(dst)
	dst = appendVarInt(dst, 7, i)
	dst[first] |= 0x80
	return dst
}

// appendNewName appends f, as encoded in one of "Literal Header field
// - New Name" representation variants, to dst and returns the
// extended buffer.
//
// If f.Sensitive is true, "Never Indexed" representation is used. If
// f.Sensitive is false and indexing is true, "Inremental Indexing"
// representation is used.
func appendNewName(dst []byte, f HeaderField, indexing bool) []byte {
	dst = append(dst, encodeTypeByte(indexing, f.Sensitive))
	dst = appendHpackString(dst, f.Name)
	return appendHpackString(dst, f.Value)
}

// appendIndexedName appends f and index i referring indexed name
// entry, as encoded in one of "Literal Header field - Indexed Name"
// representation variants, to dst and returns the extended buffer.
//
// If f.Sensitive is true, "Never Indexed" representation is used. If
// f.Sensitive is false and indexing is true, "Incremental Indexing"
// representation is used.
func appendIndexedName(dst []byte, f HeaderField, i uint64, indexing bool) []byte {
	first := len(dst)
	var n byte
	if indexing {
		n = 6
	} else {
		n = 4
	}
	dst = appendVarInt(dst, n, i)
	dst[first] |= encodeTypeByte(indexing, f.Sensitive)
	return appendHpackString(dst, f.Value)
}

// appendTableSize appends v, as encoded in "Header Table Size Update"
// representation, to dst and returns the extended buffer.
func appendTableSize(dst []byte, v uint32) []byte {
	first := len(dst)
	dst = appendVarInt(dst, 5, uint64(v))
	dst[first] |= 0x20
	return dst
}

// appendVarInt appends i, as encoded in variable integer form using n
// bit prefix, to dst and returns the extended buffer.
//
// See
// http://http2.github.io/http2-spec/compression.html#integer.representation
func appendVarInt(dst []byte, n byte, i uint64) []byte {
	k := uint64((1 << n) - 1)
	if i < k {
		return append(dst, byte(i))
	}
	dst = append(dst, byte(k))
	i -= k
	for ; i >= 128; i >>= 7 {
		dst = append(dst, byte(0x80|(i&0x7f)))
	}
	return append(dst, byte(i))
}

// appendHpackString appends s, as encoded in "String Literal"
// representation, to dst and returns the extended buffer.
//
// s will be encoded in Huffman codes only when it produces strictly
// shorter byte string.
func appendHpackString(dst []byte, s string) []byte {
	huffmanLength := HuffmanEncodeLength(s)
	if huffmanLength < uint64(len(s)) {
		first := len(dst)
		dst = appendVarInt(dst, 7, huffmanLength)
		dst = AppendHuffmanString(dst, s)
		dst[first] |= 0x80
	} else {
		dst = appendVarInt(dst, 7, uint64(len(s)))
		dst = append(dst, s...)
	}
	return dst
}

// encodeTypeByte returns type byte. If sensitive is true, type byte
// for "Never Indexed" representation is returned. If sensitive is
// false and indexing is true, type byte for "Incremental Indexing"
// representation is returned. Otherwise, type byte for "Without
// Indexing" is returned.
func encodeTypeByte(indexing, sensitive bool) byte {
	if sensitive {
		return 0x10
	}
	if indexing {
		return 0x40
	}
	return 0
}


text:
// Copyright 2017 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

import (
	"bufio"
	"regexp"
	"strconv"
	"strings"
	"testing"
)

func TestHeaderFieldTable(t *testing.T) {
	table := &headerFieldTable{}
	table.init()
	table.addEntry(pair("key1", "value1-1"))
	table.addEntry(pair("key2", "value2-1"))
	table.addEntry(pair("key1", "value1-2"))
	table.addEntry(pair("key3", "value3-1"))
	table.addEntry(pair("key4", "value4-1"))
	table.addEntry(pair("key2", "value2-2"))

	// Tests will be run twice: once before evicting anything, and
	// again after evicting the three oldest entries.
	tests := []struct {
		f                 HeaderField
		beforeWantStaticI uint64
		beforeWantMatch   bool
		afterWantStaticI  uint64
		afterWantMatch    bool
	}{
		{HeaderField{"key1", "value1-1", false}, 1, true, 0, false},
		{HeaderField{"key1", "value1-2", false}, 3, true, 0, false},
		{HeaderField{"key1", "value1-3", false}, 3, false, 0, false},
		{HeaderField{"key2", "value2-1", false}, 2, true, 3, false},
		{HeaderField{"key2", "value2-2", false}, 6, true, 3, true},
		{HeaderField{"key2", "value2-3", false}, 6, false, 3, false},
		{HeaderField{"key4", "value4-1", false}, 5, true, 2, true},
		// Name match only, because sensitive.
		{HeaderField{"key4", "value4-1", true}, 5, false, 2, false},
		// Key not found.
		{HeaderField{"key5", "value5-x", false}, 0, false, 0, false},
	}

	staticToDynamic := func(i uint64) uint64 {
		if i == 0 {
			return 0
		}
		return uint64(table.len()) - i + 1 // dynamic is the reversed table
	}

	searchStatic := func(f HeaderField) (uint64, bool) {
		old := staticTable
		staticTable = table
		defer func() { staticTable = old }()
		return staticTable.search(f)
	}

	searchDynamic := func(f HeaderField) (uint64, bool) {
		return table.search(f)
	}

	for _, test := range tests {
		gotI, gotMatch := searchStatic(test.f)
		if wantI, wantMatch := test.beforeWantStaticI, test.beforeWantMatch; gotI != wantI || gotMatch != wantMatch {
			t.Errorf("before evictions: searchStatic(%+v)=%v,%v want %v,%v", test.f, gotI, gotMatch, wantI, wantMatch)
		}
		gotI, gotMatch = searchDynamic(test.f)
		wantDynamicI := staticToDynamic(test.beforeWantStaticI)
		if wantI, wantMatch := wantDynamicI, test.beforeWantMatch; gotI != wantI || gotMatch != wantMatch {
			t.Errorf("before evictions: searchDynamic(%+v)=%v,%v want %v,%v", test.f, gotI, gotMatch, wantI, wantMatch)
		}
	}

	table.evictOldest(3)

	for _, test := range tests {
		gotI, gotMatch := searchStatic(test.f)
		if wantI, wantMatch := test.afterWantStaticI, test.afterWantMatch; gotI != wantI || gotMatch != wantMatch {
			t.Errorf("after evictions: searchStatic(%+v)=%v,%v want %v,%v", test.f, gotI, gotMatch, wantI, wantMatch)
		}
		gotI, gotMatch = searchDynamic(test.f)
		wantDynamicI := staticToDynamic(test.afterWantStaticI)
		if wantI, wantMatch := wantDynamicI, test.afterWantMatch; gotI != wantI || gotMatch != wantMatch {
			t.Errorf("after evictions: searchDynamic(%+v)=%v,%v want %v,%v", test.f, gotI, gotMatch, wantI, wantMatch)
		}
	}
}

func TestHeaderFieldTable_LookupMapEviction(t *testing.T) {
	table := &headerFieldTable{}
	table.init()
	table.addEntry(pair("key1", "value1-1"))
	table.addEntry(pair("key2", "value2-1"))
	table.addEntry(pair("key1", "value1-2"))
	table.addEntry(pair("key3", "value3-1"))
	table.addEntry(pair("key4", "value4-1"))
	table.addEntry(pair("key2", "value2-2"))

	// evict all pairs
	table.evictOldest(table.len())

	if l := table.len(); l > 0 {
		t.Errorf("table.len() = %d, want 0", l)
	}

	if l := len(table.byName); l > 0 {
		t.Errorf("len(table.byName) = %d, want 0", l)
	}

	if l := len(table.byNameValue); l > 0 {
		t.Errorf("len(table.byNameValue) = %d, want 0", l)
	}
}

func TestStaticTable(t *testing.T) {
	fromSpec := `
          +-------+-----------------------------+---------------+
          | 1     | :authority                  |               |
          | 2     | :method                     | GET           |
          | 3     | :method                     | POST          |
          | 4     | :path                       | /             |
          | 5     | :path                       | /index.html   |
          | 6     | :scheme                     | http          |
          | 7     | :scheme                     | https         |
          | 8     | :status                     | 200           |
          | 9     | :status                     | 204           |
          | 10    | :status                     | 206           |
          | 11    | :status                     | 304           |
          | 12    | :status                     | 400           |
          | 13    | :status                     | 404           |
          | 14    | :status                     | 500           |
          | 15    | accept-charset              |               |
          | 16    | accept-encoding             | gzip, deflate |
          | 17    | accept-language             |               |
          | 18    | accept-ranges               |               |
          | 19    | accept                      |               |
          | 20    | access-control-allow-origin |               |
          | 21    | age                         |               |
          | 22    | allow                       |               |
          | 23    | authorization               |               |
          | 24    | cache-control               |               |
          | 25    | content-disposition         |               |
          | 26    | content-encoding            |               |
          | 27    | content-language            |               |
          | 28    | content-length              |               |
          | 29    | content-location            |               |
          | 30    | content-range               |               |
          | 31    | content-type                |               |
          | 32    | cookie                      |               |
          | 33    | date                        |               |
          | 34    | etag                        |               |
          | 35    | expect                      |               |
          | 36    | expires                     |               |
          | 37    | from                        |               |
          | 38    | host                        |               |
          | 39    | if-match                    |               |
          | 40    | if-modified-since           |               |
          | 41    | if-none-match               |               |
          | 42    | if-range                    |               |
          | 43    | if-unmodified-since         |               |
          | 44    | last-modified               |               |
          | 45    | link                        |               |
          | 46    | location                    |               |
          | 47    | max-forwards                |               |
          | 48    | proxy-authenticate          |               |
          | 49    | proxy-authorization         |               |
          | 50    | range                       |               |
          | 51    | referer                     |               |
          | 52    | refresh                     |               |
          | 53    | retry-after                 |               |
          | 54    | server                      |               |
          | 55    | set-cookie                  |               |
          | 56    | strict-transport-security   |               |
          | 57    | transfer-encoding           |               |
          | 58    | user-agent                  |               |
          | 59    | vary                        |               |
          | 60    | via                         |               |
          | 61    | www-authenticate            |               |
          +-------+-----------------------------+---------------+
`
	bs := bufio.NewScanner(strings.NewReader(fromSpec))
	re := regexp.MustCompile(`\| (\d+)\s+\| (\S+)\s*\| (\S(.*\S)?)?\s+\|`)
	for bs.Scan() {
		l := bs.Text()
		if !strings.Contains(l, "|") {
			continue
		}
		m := re.FindStringSubmatch(l)
		if m == nil {
			continue
		}
		i, err := strconv.Atoi(m[1])
		if err != nil {
			t.Errorf("Bogus integer on line %q", l)
			continue
		}
		if i < 1 || i > staticTable.len() {
			t.Errorf("Bogus index %d on line %q", i, l)
			continue
		}
		if got, want := staticTable.ents[i-1].Name, m[2]; got != want {
			t.Errorf("header index %d name = %q; want %q", i, got, want)
		}
		if got, want := staticTable.ents[i-1].Value, m[3]; got != want {
			t.Errorf("header index %d value = %q; want %q", i, got, want)
		}
	}
	if err := bs.Err(); err != nil {
		t.Error(err)
	}
}


text:
// 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

import (
	"bytes"
	"encoding/hex"
	"fmt"
	"math/rand"
	"reflect"
	"strings"
	"testing"
)

func TestEncoderTableSizeUpdate(t *testing.T) {
	tests := []struct {
		size1, size2 uint32
		wantHex      string
	}{
		// Should emit 2 table size updates (2048 and 4096)
		{2048, 4096, "3fe10f 3fe11f 82"},

		// Should emit 1 table size update (2048)
		{16384, 2048, "3fe10f 82"},
	}
	for _, tt := range tests {
		var buf bytes.Buffer
		e := NewEncoder(&buf)
		e.SetMaxDynamicTableSize(tt.size1)
		e.SetMaxDynamicTableSize(tt.size2)
		if err := e.WriteField(pair(":method", "GET")); err != nil {
			t.Fatal(err)
		}
		want := removeSpace(tt.wantHex)
		if got := hex.EncodeToString(buf.Bytes()); got != want {
			t.Errorf("e.SetDynamicTableSize %v, %v = %q; want %q", tt.size1, tt.size2, got, want)
		}
	}
}

func TestEncoderWriteField(t *testing.T) {
	var buf bytes.Buffer
	e := NewEncoder(&buf)
	var got []HeaderField
	d := NewDecoder(4<<10, func(f HeaderField) {
		got = append(got, f)
	})

	tests := []struct {
		hdrs []HeaderField
	}{
		{[]HeaderField{
			pair(":method", "GET"),
			pair(":scheme", "http"),
			pair(":path", "/"),
			pair(":authority", "www.example.com"),
		}},
		{[]HeaderField{
			pair(":method", "GET"),
			pair(":scheme", "http"),
			pair(":path", "/"),
			pair(":authority", "www.example.com"),
			pair("cache-control", "no-cache"),
		}},
		{[]HeaderField{
			pair(":method", "GET"),
			pair(":scheme", "https"),
			pair(":path", "/index.html"),
			pair(":authority", "www.example.com"),
			pair("custom-key", "custom-value"),
		}},
	}
	for i, tt := range tests {
		buf.Reset()
		got = got[:0]
		for _, hf := range tt.hdrs {
			if err := e.WriteField(hf); err != nil {
				t.Fatal(err)
			}
		}
		_, err := d.Write(buf.Bytes())
		if err != nil {
			t.Errorf("%d. Decoder Write = %v", i, err)
		}
		if !reflect.DeepEqual(got, tt.hdrs) {
			t.Errorf("%d. Decoded %+v; want %+v", i, got, tt.hdrs)
		}
	}
}

func TestEncoderSearchTable(t *testing.T) {
	e := NewEncoder(nil)

	e.dynTab.add(pair("foo", "bar"))
	e.dynTab.add(pair("blake", "miz"))
	e.dynTab.add(pair(":method", "GET"))

	tests := []struct {
		hf        HeaderField
		wantI     uint64
		wantMatch bool
	}{
		// Name and Value match
		{pair("foo", "bar"), uint64(staticTable.len()) + 3, true},
		{pair("blake", "miz"), uint64(staticTable.len()) + 2, true},
		{pair(":method", "GET"), 2, true},

		// Only name match because Sensitive == true. This is allowed to match
		// any ":method" entry. The current implementation uses the last entry
		// added in newStaticTable.
		{HeaderField{":method", "GET", true}, 3, false},

		// Only Name matches
		{pair("foo", "..."), uint64(staticTable.len()) + 3, false},
		{pair("blake", "..."), uint64(staticTable.len()) + 2, false},
		// As before, this is allowed to match any ":method" entry.
		{pair(":method", "..."), 3, false},

		// None match
		{pair("foo-", "bar"), 0, false},
	}
	for _, tt := range tests {
		if gotI, gotMatch := e.searchTable(tt.hf); gotI != tt.wantI || gotMatch != tt.wantMatch {
			t.Errorf("d.search(%+v) = %v, %v; want %v, %v", tt.hf, gotI, gotMatch, tt.wantI, tt.wantMatch)
		}
	}
}

func TestAppendVarInt(t *testing.T) {
	tests := []struct {
		n    byte
		i    uint64
		want []byte
	}{
		// Fits in a byte:
		{1, 0, []byte{0}},
		{2, 2, []byte{2}},
		{3, 6, []byte{6}},
		{4, 14, []byte{14}},
		{5, 30, []byte{30}},
		{6, 62, []byte{62}},
		{7, 126, []byte{126}},
		{8, 254, []byte{254}},

		// Multiple bytes:
		{5, 1337, []byte{31, 154, 10}},
	}
	for _, tt := range tests {
		got := appendVarInt(nil, tt.n, tt.i)
		if !bytes.Equal(got, tt.want) {
			t.Errorf("appendVarInt(nil, %v, %v) = %v; want %v", tt.n, tt.i, got, tt.want)
		}
	}
}

func TestAppendHpackString(t *testing.T) {
	tests := []struct {
		s, wantHex string
	}{
		// Huffman encoded
		{"www.example.com", "8c f1e3 c2e5 f23a 6ba0 ab90 f4ff"},

		// Not Huffman encoded
		{"a", "01 61"},

		// zero length
		{"", "00"},
	}
	for _, tt := range tests {
		want := removeSpace(tt.wantHex)
		buf := appendHpackString(nil, tt.s)
		if got := hex.EncodeToString(buf); want != got {
			t.Errorf("appendHpackString(nil, %q) = %q; want %q", tt.s, got, want)
		}
	}
}

func TestAppendIndexed(t *testing.T) {
	tests := []struct {
		i       uint64
		wantHex string
	}{
		// 1 byte
		{1, "81"},
		{126, "fe"},

		// 2 bytes
		{127, "ff00"},
		{128, "ff01"},
	}
	for _, tt := range tests {
		want := removeSpace(tt.wantHex)
		buf := appendIndexed(nil, tt.i)
		if got := hex.EncodeToString(buf); want != got {
			t.Errorf("appendIndex(nil, %v) = %q; want %q", tt.i, got, want)
		}
	}
}

func TestAppendNewName(t *testing.T) {
	tests := []struct {
		f        HeaderField
		indexing bool
		wantHex  string
	}{
		// Incremental indexing
		{HeaderField{"custom-key", "custom-value", false}, true, "40 88 25a8 49e9 5ba9 7d7f 89 25a8 49e9 5bb8 e8b4 bf"},

		// Without indexing
		{HeaderField{"custom-key", "custom-value", false}, false, "00 88 25a8 49e9 5ba9 7d7f 89 25a8 49e9 5bb8 e8b4 bf"},

		// Never indexed
		{HeaderField{"custom-key", "custom-value", true}, true, "10 88 25a8 49e9 5ba9 7d7f 89 25a8 49e9 5bb8 e8b4 bf"},
		{HeaderField{"custom-key", "custom-value", true}, false, "10 88 25a8 49e9 5ba9 7d7f 89 25a8 49e9 5bb8 e8b4 bf"},
	}
	for _, tt := range tests {
		want := removeSpace(tt.wantHex)
		buf := appendNewName(nil, tt.f, tt.indexing)
		if got := hex.EncodeToString(buf); want != got {
			t.Errorf("appendNewName(nil, %+v, %v) = %q; want %q", tt.f, tt.indexing, got, want)
		}
	}
}

func TestAppendIndexedName(t *testing.T) {
	tests := []struct {
		f        HeaderField
		i        uint64
		indexing bool
		wantHex  string
	}{
		// Incremental indexing
		{HeaderField{":status", "302", false}, 8, true, "48 82 6402"},

		// Without indexing
		{HeaderField{":status", "302", false}, 8, false, "08 82 6402"},

		// Never indexed
		{HeaderField{":status", "302", true}, 8, true, "18 82 6402"},
		{HeaderField{":status", "302", true}, 8, false, "18 82 6402"},
	}
	for _, tt := range tests {
		want := removeSpace(tt.wantHex)
		buf := appendIndexedName(nil, tt.f, tt.i, tt.indexing)
		if got := hex.EncodeToString(buf); want != got {
			t.Errorf("appendIndexedName(nil, %+v, %v) = %q; want %q", tt.f, tt.indexing, got, want)
		}
	}
}

func TestAppendTableSize(t *testing.T) {
	tests := []struct {
		i       uint32
		wantHex string
	}{
		// Fits into 1 byte
		{30, "3e"},

		// Extra byte
		{31, "3f00"},
		{32, "3f01"},
	}
	for _, tt := range tests {
		want := removeSpace(tt.wantHex)
		buf := appendTableSize(nil, tt.i)
		if got := hex.EncodeToString(buf); want != got {
			t.Errorf("appendTableSize(nil, %v) = %q; want %q", tt.i, got, want)
		}
	}
}

func TestEncoderSetMaxDynamicTableSize(t *testing.T) {
	var buf bytes.Buffer
	e := NewEncoder(&buf)
	tests := []struct {
		v           uint32
		wantUpdate  bool
		wantMinSize uint32
		wantMaxSize uint32
	}{
		// Set new table size to 2048
		{2048, true, 2048, 2048},

		// Set new table size to 16384, but still limited to
		// 4096
		{16384, true, 2048, 4096},
	}
	for _, tt := range tests {
		e.SetMaxDynamicTableSize(tt.v)
		if got := e.tableSizeUpdate; tt.wantUpdate != got {
			t.Errorf("e.tableSizeUpdate = %v; want %v", got, tt.wantUpdate)
		}
		if got := e.minSize; tt.wantMinSize != got {
			t.Errorf("e.minSize = %v; want %v", got, tt.wantMinSize)
		}
		if got := e.dynTab.maxSize; tt.wantMaxSize != got {
			t.Errorf("e.maxSize = %v; want %v", got, tt.wantMaxSize)
		}
	}
}

func TestEncoderSetMaxDynamicTableSizeLimit(t *testing.T) {
	e := NewEncoder(nil)
	// 4095 < initialHeaderTableSize means maxSize is truncated to
	// 4095.
	e.SetMaxDynamicTableSizeLimit(4095)
	if got, want := e.dynTab.maxSize, uint32(4095); got != want {
		t.Errorf("e.dynTab.maxSize = %v; want %v", got, want)
	}
	if got, want := e.maxSizeLimit, uint32(4095); got != want {
		t.Errorf("e.maxSizeLimit = %v; want %v", got, want)
	}
	if got, want := e.tableSizeUpdate, true; got != want {
		t.Errorf("e.tableSizeUpdate = %v; want %v", got, want)
	}
	// maxSize will be truncated to maxSizeLimit
	e.SetMaxDynamicTableSize(16384)
	if got, want := e.dynTab.maxSize, uint32(4095); got != want {
		t.Errorf("e.dynTab.maxSize = %v; want %v", got, want)
	}
	// 8192 > current maxSizeLimit, so maxSize does not change.
	e.SetMaxDynamicTableSizeLimit(8192)
	if got, want := e.dynTab.maxSize, uint32(4095); got != want {
		t.Errorf("e.dynTab.maxSize = %v; want %v", got, want)
	}
	if got, want := e.maxSizeLimit, uint32(8192); got != want {
		t.Errorf("e.maxSizeLimit = %v; want %v", got, want)
	}
}

func removeSpace(s string) string {
	return strings.Replace(s, " ", "", -1)
}

func BenchmarkEncoderSearchTable(b *testing.B) {
	e := NewEncoder(nil)

	// A sample of possible header fields.
	// This is not based on any actual data from HTTP/2 traces.
	var possible []HeaderField
	for _, f := range staticTable.ents {
		if f.Value == "" {
			possible = append(possible, f)
			continue
		}
		// Generate 5 random values, except for cookie and set-cookie,
		// which we know can have many values in practice.
		num := 5
		if f.Name == "cookie" || f.Name == "set-cookie" {
			num = 25
		}
		for i := 0; i < num; i++ {
			f.Value = fmt.Sprintf("%s-%d", f.Name, i)
			possible = append(possible, f)
		}
	}
	for k := 0; k < 10; k++ {
		f := HeaderField{
			Name:      fmt.Sprintf("x-header-%d", k),
			Sensitive: rand.Int()%2 == 0,
		}
		for i := 0; i < 5; i++ {
			f.Value = fmt.Sprintf("%s-%d", f.Name, i)
			possible = append(possible, f)
		}
	}

	// Add a random sample to the dynamic table. This very loosely simulates
	// a history of 100 requests with 20 header fields per request.
	for r := 0; r < 100*20; r++ {
		f := possible[rand.Int31n(int32(len(possible)))]
		// Skip if this is in the staticTable verbatim.
		if _, has := staticTable.search(f); !has {
			e.dynTab.add(f)
		}
	}

	b.ResetTimer()
	for n := 0; n < b.N; n++ {
		for _, f := range possible {
			e.searchTable(f)
		}
	}
}


text:
// 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

import (
	"fmt"
)

// headerFieldTable implements a list of HeaderFields.
// This is used to implement the static and dynamic tables.
type headerFieldTable struct {
	// For static tables, entries are never evicted.
	//
	// For dynamic tables, entries are evicted from ents[0] and added to the end.
	// Each entry has a unique id that starts at one and increments for each
	// entry that is added. This unique id is stable across evictions, meaning
	// it can be used as a pointer to a specific entry. As in hpack, unique ids
	// are 1-based. The unique id for ents[k] is k + evictCount + 1.
	//
	// Zero is not a valid unique id.
	//
	// evictCount should not overflow in any remotely practical situation. In
	// practice, we will have one dynamic table per HTTP/2 connection. If we
	// assume a very powerful server that handles 1M QPS per connection and each
	// request adds (then evicts) 100 entries from the table, it would still take
	// 2M years for evictCount to overflow.
	ents       []HeaderField
	evictCount uint64

	// byName maps a HeaderField name to the unique id of the newest entry with
	// the same name. See above for a definition of "unique id".
	byName map[string]uint64

	// byNameValue maps a HeaderField name/value pair to the unique id of the newest
	// entry with the same name and value. See above for a definition of "unique id".
	byNameValue map[pairNameValue]uint64
}

type pairNameValue struct {
	name, value string
}

func (t *headerFieldTable) init() {
	t.byName = make(map[string]uint64)
	t.byNameValue = make(map[pairNameValue]uint64)
}

// len reports the number of entries in the table.
func (t *headerFieldTable) len() int {
	return len(t.ents)
}

// addEntry adds a new entry.
func (t *headerFieldTable) addEntry(f HeaderField) {
	id := uint64(t.len()) + t.evictCount + 1
	t.byName[f.Name] = id
	t.byNameValue[pairNameValue{f.Name, f.Value}] = id
	t.ents = append(t.ents, f)
}

// evictOldest evicts the n oldest entries in the table.
func (t *headerFieldTable) evictOldest(n int) {
	if n > t.len() {
		panic(fmt.Sprintf("evictOldest(%v) on table with %v entries", n, t.len()))
	}
	for k := 0; k < n; k++ {
		f := t.ents[k]
		id := t.evictCount + uint64(k) + 1
		if t.byName[f.Name] == id {
			delete(t.byName, f.Name)
		}
		if p := (pairNameValue{f.Name, f.Value}); t.byNameValue[p] == id {
			delete(t.byNameValue, p)
		}
	}
	copy(t.ents, t.ents[n:])
	for k := t.len() - n; k < t.len(); k++ {
		t.ents[k] = HeaderField{} // so strings can be garbage collected
	}
	t.ents = t.ents[:t.len()-n]
	if t.evictCount+uint64(n) < t.evictCount {
		panic("evictCount overflow")
	}
	t.evictCount += uint64(n)
}

// search finds f in the table. If there is no match, i is 0.
// If both name and value match, i is the matched index and nameValueMatch
// becomes true. If only name matches, i points to that index and
// nameValueMatch becomes false.
//
// The returned index is a 1-based HPACK index. For dynamic tables, HPACK says
// that index 1 should be the newest entry, but t.ents[0] is the oldest entry,
// meaning t.ents is reversed for dynamic tables. Hence, when t is a dynamic
// table, the return value i actually refers to the entry t.ents[t.len()-i].
//
// All tables are assumed to be a dynamic tables except for the global
// staticTable pointer.
//
// See Section 2.3.3.
func (t *headerFieldTable) search(f HeaderField) (i uint64, nameValueMatch bool) {
	if !f.Sensitive {
		if id := t.byNameValue[pairNameValue{f.Name, f.Value}]; id != 0 {
			return t.idToIndex(id), true
		}
	}
	if id := t.byName[f.Name]; id != 0 {
		return t.idToIndex(id), false
	}
	return 0, false
}

// idToIndex converts a unique id to an HPACK index.
// See Section 2.3.3.
func (t *headerFieldTable) idToIndex(id uint64) uint64 {
	if id <= t.evictCount {
		panic(fmt.Sprintf("id (%v) <= evictCount (%v)", id, t.evictCount))
	}
	k := id - t.evictCount - 1 // convert id to an index t.ents[k]
	if t != staticTable {
		return uint64(t.len()) - k // dynamic table
	}
	return k + 1
}

// http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-07#appendix-B
var staticTable = newStaticTable()
var staticTableEntries = [...]HeaderField{
	{Name: ":authority"},
	{Name: ":method", Value: "GET"},
	{Name: ":method", Value: "POST"},
	{Name: ":path", Value: "/"},
	{Name: ":path", Value: "/index.html"},
	{Name: ":scheme", Value: "http"},
	{Name: ":scheme", Value: "https"},
	{Name: ":status", Value: "200"},
	{Name: ":status", Value: "204"},
	{Name: ":status", Value: "206"},
	{Name: ":status", Value: "304"},
	{Name: ":status", Value: "400"},
	{Name: ":status", Value: "404"},
	{Name: ":status", Value: "500"},
	{Name: "accept-charset"},
	{Name: "accept-encoding", Value: "gzip, deflate"},
	{Name: "accept-language"},
	{Name: "accept-ranges"},
	{Name: "accept"},
	{Name: "access-control-allow-origin"},
	{Name: "age"},
	{Name: "allow"},
	{Name: "authorization"},
	{Name: "cache-control"},
	{Name: "content-disposition"},
	{Name: "content-encoding"},
	{Name: "content-language"},
	{Name: "content-length"},
	{Name: "content-location"},
	{Name: "content-range"},
	{Name: "content-type"},
	{Name: "cookie"},
	{Name: "date"},
	{Name: "etag"},
	{Name: "expect"},
	{Name: "expires"},
	{Name: "from"},
	{Name: "host"},
	{Name: "if-match"},
	{Name: "if-modified-since"},
	{Name: "if-none-match"},
	{Name: "if-range"},
	{Name: "if-unmodified-since"},
	{Name: "last-modified"},
	{Name: "link"},
	{Name: "location"},
	{Name: "max-forwards"},
	{Name: "proxy-authenticate"},
	{Name: "proxy-authorization"},
	{Name: "range"},
	{Name: "referer"},
	{Name: "refresh"},
	{Name: "retry-after"},
	{Name: "server"},
	{Name: "set-cookie"},
	{Name: "strict-transport-security"},
	{Name: "transfer-encoding"},
	{Name: "user-agent"},
	{Name: "vary"},
	{Name: "via"},
	{Name: "www-authenticate"},
}

func newStaticTable() *headerFieldTable {
	t := &headerFieldTable{}
	t.init()
	for _, e := range staticTableEntries[:] {
		t.addEntry(e)
	}
	return t
}

var huffmanCodes = [256]uint32{
	0x1ff8,
	0x7fffd8,
	0xfffffe2,
	0xfffffe3,
	0xfffffe4,
	0xfffffe5,
	0xfffffe6,
	0xfffffe7,
	0xfffffe8,
	0xffffea,
	0x3ffffffc,
	0xfffffe9,
	0xfffffea,
	0x3ffffffd,
	0xfffffeb,
	0xfffffec,
	0xfffffed,
	0xfffffee,
	0xfffffef,
	0xffffff0,
	0xffffff1,
	0xffffff2,
	0x3ffffffe,
	0xffffff3,
	0xffffff4,
	0xffffff5,
	0xffffff6,
	0xffffff7,
	0xffffff8,
	0xffffff9,
	0xffffffa,
	0xffffffb,
	0x14,
	0x3f8,
	0x3f9,
	0xffa,
	0x1ff9,
	0x15,
	0xf8,
	0x7fa,
	0x3fa,
	0x3fb,
	0xf9,
	0x7fb,
	0xfa,
	0x16,
	0x17,
	0x18,
	0x0,
	0x1,
	0x2,
	0x19,
	0x1a,
	0x1b,
	0x1c,
	0x1d,
	0x1e,
	0x1f,
	0x5c,
	0xfb,
	0x7ffc,
	0x20,
	0xffb,
	0x3fc,
	0x1ffa,
	0x21,
	0x5d,
	0x5e,
	0x5f,
	0x60,
	0x61,
	0x62,
	0x63,
	0x64,
	0x65,
	0x66,
	0x67,
	0x68,
	0x69,
	0x6a,
	0x6b,
	0x6c,
	0x6d,
	0x6e,
	0x6f,
	0x70,
	0x71,
	0x72,
	0xfc,
	0x73,
	0xfd,
	0x1ffb,
	0x7fff0,
	0x1ffc,
	0x3ffc,
	0x22,
	0x7ffd,
	0x3,
	0x23,
	0x4,
	0x24,
	0x5,
	0x25,
	0x26,
	0x27,
	0x6,
	0x74,
	0x75,
	0x28,
	0x29,
	0x2a,
	0x7,
	0x2b,
	0x76,
	0x2c,
	0x8,
	0x9,
	0x2d,
	0x77,
	0x78,
	0x79,
	0x7a,
	0x7b,
	0x7ffe,
	0x7fc,
	0x3ffd,
	0x1ffd,
	0xffffffc,
	0xfffe6,
	0x3fffd2,
	0xfffe7,
	0xfffe8,
	0x3fffd3,
	0x3fffd4,
	0x3fffd5,
	0x7fffd9,
	0x3fffd6,
	0x7fffda,
	0x7fffdb,
	0x7fffdc,
	0x7fffdd,
	0x7fffde,
	0xffffeb,
	0x7fffdf,
	0xffffec,
	0xffffed,
	0x3fffd7,
	0x7fffe0,
	0xffffee,
	0x7fffe1,
	0x7fffe2,
	0x7fffe3,
	0x7fffe4,
	0x1fffdc,
	0x3fffd8,
	0x7fffe5,
	0x3fffd9,
	0x7fffe6,
	0x7fffe7,
	0xffffef,
	0x3fffda,
	0x1fffdd,
	0xfffe9,
	0x3fffdb,
	0x3fffdc,
	0x7fffe8,
	0x7fffe9,
	0x1fffde,
	0x7fffea,
	0x3fffdd,
	0x3fffde,
	0xfffff0,
	0x1fffdf,
	0x3fffdf,
	0x7fffeb,
	0x7fffec,
	0x1fffe0,
	0x1fffe1,
	0x3fffe0,
	0x1fffe2,
	0x7fffed,
	0x3fffe1,
	0x7fffee,
	0x7fffef,
	0xfffea,
	0x3fffe2,
	0x3fffe3,
	0x3fffe4,
	0x7ffff0,
	0x3fffe5,
	0x3fffe6,
	0x7ffff1,
	0x3ffffe0,
	0x3ffffe1,
	0xfffeb,
	0x7fff1,
	0x3fffe7,
	0x7ffff2,
	0x3fffe8,
	0x1ffffec,
	0x3ffffe2,
	0x3ffffe3,
	0x3ffffe4,
	0x7ffffde,
	0x7ffffdf,
	0x3ffffe5,
	0xfffff1,
	0x1ffffed,
	0x7fff2,
	0x1fffe3,
	0x3ffffe6,
	0x7ffffe0,
	0x7ffffe1,
	0x3ffffe7,
	0x7ffffe2,
	0xfffff2,
	0x1fffe4,
	0x1fffe5,
	0x3ffffe8,
	0x3ffffe9,
	0xffffffd,
	0x7ffffe3,
	0x7ffffe4,
	0x7ffffe5,
	0xfffec,
	0xfffff3,
	0xfffed,
	0x1fffe6,
	0x3fffe9,
	0x1fffe7,
	0x1fffe8,
	0x7ffff3,
	0x3fffea,
	0x3fffeb,
	0x1ffffee,
	0x1ffffef,
	0xfffff4,
	0xfffff5,
	0x3ffffea,
	0x7ffff4,
	0x3ffffeb,
	0x7ffffe6,
	0x3ffffec,
	0x3ffffed,
	0x7ffffe7,
	0x7ffffe8,
	0x7ffffe9,
	0x7ffffea,
	0x7ffffeb,
	0xffffffe,
	0x7ffffec,
	0x7ffffed,
	0x7ffffee,
	0x7ffffef,
	0x7fffff0,
	0x3ffffee,
}

var huffmanCodeLen = [256]uint8{
	13, 23, 28, 28, 28, 28, 28, 28, 28, 24, 30, 28, 28, 30, 28, 28,
	28, 28, 28, 28, 28, 28, 30, 28, 28, 28, 28, 28, 28, 28, 28, 28,
	6, 10, 10, 12, 13, 6, 8, 11, 10, 10, 8, 11, 8, 6, 6, 6,
	5, 5, 5, 6, 6, 6, 6, 6, 6, 6, 7, 8, 15, 6, 12, 10,
	13, 6, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
	7, 7, 7, 7, 7, 7, 7, 7, 8, 7, 8, 13, 19, 13, 14, 6,
	15, 5, 6, 5, 6, 5, 6, 6, 6, 5, 7, 7, 6, 6, 6, 5,
	6, 7, 6, 5, 5, 6, 7, 7, 7, 7, 7, 15, 11, 14, 13, 28,
	20, 22, 20, 20, 22, 22, 22, 23, 22, 23, 23, 23, 23, 23, 24, 23,
	24, 24, 22, 23, 24, 23, 23, 23, 23, 21, 22, 23, 22, 23, 23, 24,
	22, 21, 20, 22, 22, 23, 23, 21, 23, 22, 22, 24, 21, 22, 23, 23,
	21, 21, 22, 21, 23, 22, 23, 23, 20, 22, 22, 22, 23, 22, 22, 23,
	26, 26, 20, 19, 22, 23, 22, 25, 26, 26, 26, 27, 27, 26, 24, 25,
	19, 21, 26, 27, 27, 26, 27, 24, 21, 21, 26, 26, 28, 27, 27, 27,
	20, 24, 20, 21, 22, 21, 21, 23, 22, 22, 25, 25, 24, 24, 26, 23,
	26, 27, 26, 26, 27, 27, 27, 27, 27, 28, 27, 27, 27, 27, 27, 26,
}


text:
// 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

import (
	"bytes"
	"encoding/hex"
	"fmt"
	"math/rand"
	"reflect"
	"strings"
	"testing"
	"time"
)

func (d *Decoder) mustAt(idx int) HeaderField {
	if hf, ok := d.at(uint64(idx)); !ok {
		panic(fmt.Sprintf("bogus index %d", idx))
	} else {
		return hf
	}
}

func TestDynamicTableAt(t *testing.T) {
	d := NewDecoder(4096, nil)
	at := d.mustAt
	if got, want := at(2), (pair(":method", "GET")); got != want {
		t.Errorf("at(2) = %v; want %v", got, want)
	}
	d.dynTab.add(pair("foo", "bar"))
	d.dynTab.add(pair("blake", "miz"))
	if got, want := at(staticTable.len()+1), (pair("blake", "miz")); got != want {
		t.Errorf("at(dyn 1) = %v; want %v", got, want)
	}
	if got, want := at(staticTable.len()+2), (pair("foo", "bar")); got != want {
		t.Errorf("at(dyn 2) = %v; want %v", got, want)
	}
	if got, want := at(3), (pair(":method", "POST")); got != want {
		t.Errorf("at(3) = %v; want %v", got, want)
	}
}

func TestDynamicTableSizeEvict(t *testing.T) {
	d := NewDecoder(4096, nil)
	if want := uint32(0); d.dynTab.size != want {
		t.Fatalf("size = %d; want %d", d.dynTab.size, want)
	}
	add := d.dynTab.add
	add(pair("blake", "eats pizza"))
	if want := uint32(15 + 32); d.dynTab.size != want {
		t.Fatalf("after pizza, size = %d; want %d", d.dynTab.size, want)
	}
	add(pair("foo", "bar"))
	if want := uint32(15 + 32 + 6 + 32); d.dynTab.size != want {
		t.Fatalf("after foo bar, size = %d; want %d", d.dynTab.size, want)
	}
	d.dynTab.setMaxSize(15 + 32 + 1 /* slop */)
	if want := uint32(6 + 32); d.dynTab.size != want {
		t.Fatalf("after setMaxSize, size = %d; want %d", d.dynTab.size, want)
	}
	if got, want := d.mustAt(staticTable.len()+1), (pair("foo", "bar")); got != want {
		t.Errorf("at(dyn 1) = %v; want %v", got, want)
	}
	add(pair("long", strings.Repeat("x", 500)))
	if want := uint32(0); d.dynTab.size != want {
		t.Fatalf("after big one, size = %d; want %d", d.dynTab.size, want)
	}
}

func TestDecoderDecode(t *testing.T) {
	tests := []struct {
		name       string
		in         []byte
		want       []HeaderField
		wantDynTab []HeaderField // newest entry first
	}{
		// C.2.1 Literal Header Field with Indexing
		// http://http2.github.io/http2-spec/compression.html#rfc.section.C.2.1
		{"C.2.1", dehex("400a 6375 7374 6f6d 2d6b 6579 0d63 7573 746f 6d2d 6865 6164 6572"),
			[]HeaderField{pair("custom-key", "custom-header")},
			[]HeaderField{pair("custom-key", "custom-header")},
		},

		// C.2.2 Literal Header Field without Indexing
		// http://http2.github.io/http2-spec/compression.html#rfc.section.C.2.2
		{"C.2.2", dehex("040c 2f73 616d 706c 652f 7061 7468"),
			[]HeaderField{pair(":path", "/sample/path")},
			[]HeaderField{}},

		// C.2.3 Literal Header Field never Indexed
		// http://http2.github.io/http2-spec/compression.html#rfc.section.C.2.3
		{"C.2.3", dehex("1008 7061 7373 776f 7264 0673 6563 7265 74"),
			[]HeaderField{{"password", "secret", true}},
			[]HeaderField{}},

		// C.2.4 Indexed Header Field
		// http://http2.github.io/http2-spec/compression.html#rfc.section.C.2.4
		{"C.2.4", []byte("\x82"),
			[]HeaderField{pair(":method", "GET")},
			[]HeaderField{}},
	}
	for _, tt := range tests {
		d := NewDecoder(4096, nil)
		hf, err := d.DecodeFull(tt.in)
		if err != nil {
			t.Errorf("%s: %v", tt.name, err)
			continue
		}
		if !reflect.DeepEqual(hf, tt.want) {
			t.Errorf("%s: Got %v; want %v", tt.name, hf, tt.want)
		}
		gotDynTab := d.dynTab.reverseCopy()
		if !reflect.DeepEqual(gotDynTab, tt.wantDynTab) {
			t.Errorf("%s: dynamic table after = %v; want %v", tt.name, gotDynTab, tt.wantDynTab)
		}
	}
}

func (dt *dynamicTable) reverseCopy() (hf []HeaderField) {
	hf = make([]HeaderField, len(dt.table.ents))
	for i := range hf {
		hf[i] = dt.table.ents[len(dt.table.ents)-1-i]
	}
	return
}

type encAndWant struct {
	enc         []byte
	want        []HeaderField
	wantDynTab  []HeaderField
	wantDynSize uint32
}

// C.3 Request Examples without Huffman Coding
// http://http2.github.io/http2-spec/compression.html#rfc.section.C.3
func TestDecodeC3_NoHuffman(t *testing.T) {
	testDecodeSeries(t, 4096, []encAndWant{
		{dehex("8286 8441 0f77 7777 2e65 7861 6d70 6c65 2e63 6f6d"),
			[]HeaderField{
				pair(":method", "GET"),
				pair(":scheme", "http"),
				pair(":path", "/"),
				pair(":authority", "www.example.com"),
			},
			[]HeaderField{
				pair(":authority", "www.example.com"),
			},
			57,
		},
		{dehex("8286 84be 5808 6e6f 2d63 6163 6865"),
			[]HeaderField{
				pair(":method", "GET"),
				pair(":scheme", "http"),
				pair(":path", "/"),
				pair(":authority", "www.example.com"),
				pair("cache-control", "no-cache"),
			},
			[]HeaderField{
				pair("cache-control", "no-cache"),
				pair(":authority", "www.example.com"),
			},
			110,
		},
		{dehex("8287 85bf 400a 6375 7374 6f6d 2d6b 6579 0c63 7573 746f 6d2d 7661 6c75 65"),
			[]HeaderField{
				pair(":method", "GET"),
				pair(":scheme", "https"),
				pair(":path", "/index.html"),
				pair(":authority", "www.example.com"),
				pair("custom-key", "custom-value"),
			},
			[]HeaderField{
				pair("custom-key", "custom-value"),
				pair("cache-control", "no-cache"),
				pair(":authority", "www.example.com"),
			},
			164,
		},
	})
}

// C.4 Request Examples with Huffman Coding
// http://http2.github.io/http2-spec/compression.html#rfc.section.C.4
func TestDecodeC4_Huffman(t *testing.T) {
	testDecodeSeries(t, 4096, []encAndWant{
		{dehex("8286 8441 8cf1 e3c2 e5f2 3a6b a0ab 90f4 ff"),
			[]HeaderField{
				pair(":method", "GET"),
				pair(":scheme", "http"),
				pair(":path", "/"),
				pair(":authority", "www.example.com"),
			},
			[]HeaderField{
				pair(":authority", "www.example.com"),
			},
			57,
		},
		{dehex("8286 84be 5886 a8eb 1064 9cbf"),
			[]HeaderField{
				pair(":method", "GET"),
				pair(":scheme", "http"),
				pair(":path", "/"),
				pair(":authority", "www.example.com"),
				pair("cache-control", "no-cache"),
			},
			[]HeaderField{
				pair("cache-control", "no-cache"),
				pair(":authority", "www.example.com"),
			},
			110,
		},
		{dehex("8287 85bf 4088 25a8 49e9 5ba9 7d7f 8925 a849 e95b b8e8 b4bf"),
			[]HeaderField{
				pair(":method", "GET"),
				pair(":scheme", "https"),
				pair(":path", "/index.html"),
				pair(":authority", "www.example.com"),
				pair("custom-key", "custom-value"),
			},
			[]HeaderField{
				pair("custom-key", "custom-value"),
				pair("cache-control", "no-cache"),
				pair(":authority", "www.example.com"),
			},
			164,
		},
	})
}

// http://http2.github.io/http2-spec/compression.html#rfc.section.C.5
// "This section shows several consecutive header lists, corresponding
// to HTTP responses, on the same connection. The HTTP/2 setting
// parameter SETTINGS_HEADER_TABLE_SIZE is set to the value of 256
// octets, causing some evictions to occur."
func TestDecodeC5_ResponsesNoHuff(t *testing.T) {
	testDecodeSeries(t, 256, []encAndWant{
		{dehex(`
4803 3330 3258 0770 7269 7661 7465 611d
4d6f 6e2c 2032 3120 4f63 7420 3230 3133
2032 303a 3133 3a32 3120 474d 546e 1768
7474 7073 3a2f 2f77 7777 2e65 7861 6d70
6c65 2e63 6f6d
`),
			[]HeaderField{
				pair(":status", "302"),
				pair("cache-control", "private"),
				pair("date", "Mon, 21 Oct 2013 20:13:21 GMT"),
				pair("location", "https://www.example.com"),
			},
			[]HeaderField{
				pair("location", "https://www.example.com"),
				pair("date", "Mon, 21 Oct 2013 20:13:21 GMT"),
				pair("cache-control", "private"),
				pair(":status", "302"),
			},
			222,
		},
		{dehex("4803 3330 37c1 c0bf"),
			[]HeaderField{
				pair(":status", "307"),
				pair("cache-control", "private"),
				pair("date", "Mon, 21 Oct 2013 20:13:21 GMT"),
				pair("location", "https://www.example.com"),
			},
			[]HeaderField{
				pair(":status", "307"),
				pair("location", "https://www.example.com"),
				pair("date", "Mon, 21 Oct 2013 20:13:21 GMT"),
				pair("cache-control", "private"),
			},
			222,
		},
		{dehex(`
88c1 611d 4d6f 6e2c 2032 3120 4f63 7420
3230 3133 2032 303a 3133 3a32 3220 474d
54c0 5a04 677a 6970 7738 666f 6f3d 4153
444a 4b48 514b 425a 584f 5157 454f 5049
5541 5851 5745 4f49 553b 206d 6178 2d61
6765 3d33 3630 303b 2076 6572 7369 6f6e
3d31
`),
			[]HeaderField{
				pair(":status", "200"),
				pair("cache-control", "private"),
				pair("date", "Mon, 21 Oct 2013 20:13:22 GMT"),
				pair("location", "https://www.example.com"),
				pair("content-encoding", "gzip"),
				pair("set-cookie", "foo=ASDJKHQKBZXOQWEOPIUAXQWEOIU; max-age=3600; version=1"),
			},
			[]HeaderField{
				pair("set-cookie", "foo=ASDJKHQKBZXOQWEOPIUAXQWEOIU; max-age=3600; version=1"),
				pair("content-encoding", "gzip"),
				pair("date", "Mon, 21 Oct 2013 20:13:22 GMT"),
			},
			215,
		},
	})
}

// http://http2.github.io/http2-spec/compression.html#rfc.section.C.6
// "This section shows the same examples as the previous section, but
// using Huffman encoding for the literal values. The HTTP/2 setting
// parameter SETTINGS_HEADER_TABLE_SIZE is set to the value of 256
// octets, causing some evictions to occur. The eviction mechanism
// uses the length of the decoded literal values, so the same
// evictions occurs as in the previous section."
func TestDecodeC6_ResponsesHuffman(t *testing.T) {
	testDecodeSeries(t, 256, []encAndWant{
		{dehex(`
4882 6402 5885 aec3 771a 4b61 96d0 7abe
9410 54d4 44a8 2005 9504 0b81 66e0 82a6
2d1b ff6e 919d 29ad 1718 63c7 8f0b 97c8
e9ae 82ae 43d3
`),
			[]HeaderField{
				pair(":status", "302"),
				pair("cache-control", "private"),
				pair("date", "Mon, 21 Oct 2013 20:13:21 GMT"),
				pair("location", "https://www.example.com"),
			},
			[]HeaderField{
				pair("location", "https://www.example.com"),
				pair("date", "Mon, 21 Oct 2013 20:13:21 GMT"),
				pair("cache-control", "private"),
				pair(":status", "302"),
			},
			222,
		},
		{dehex("4883 640e ffc1 c0bf"),
			[]HeaderField{
				pair(":status", "307"),
				pair("cache-control", "private"),
				pair("date", "Mon, 21 Oct 2013 20:13:21 GMT"),
				pair("location", "https://www.example.com"),
			},
			[]HeaderField{
				pair(":status", "307"),
				pair("location", "https://www.example.com"),
				pair("date", "Mon, 21 Oct 2013 20:13:21 GMT"),
				pair("cache-control", "private"),
			},
			222,
		},
		{dehex(`
88c1 6196 d07a be94 1054 d444 a820 0595
040b 8166 e084 a62d 1bff c05a 839b d9ab
77ad 94e7 821d d7f2 e6c7 b335 dfdf cd5b
3960 d5af 2708 7f36 72c1 ab27 0fb5 291f
9587 3160 65c0 03ed 4ee5 b106 3d50 07
`),
			[]HeaderField{
				pair(":status", "200"),
				pair("cache-control", "private"),
				pair("date", "Mon, 21 Oct 2013 20:13:22 GMT"),
				pair("location", "https://www.example.com"),
				pair("content-encoding", "gzip"),
				pair("set-cookie", "foo=ASDJKHQKBZXOQWEOPIUAXQWEOIU; max-age=3600; version=1"),
			},
			[]HeaderField{
				pair("set-cookie", "foo=ASDJKHQKBZXOQWEOPIUAXQWEOIU; max-age=3600; version=1"),
				pair("content-encoding", "gzip"),
				pair("date", "Mon, 21 Oct 2013 20:13:22 GMT"),
			},
			215,
		},
	})
}

func testDecodeSeries(t *testing.T, size uint32, steps []encAndWant) {
	d := NewDecoder(size, nil)
	for i, step := range steps {
		hf, err := d.DecodeFull(step.enc)
		if err != nil {
			t.Fatalf("Error at step index %d: %v", i, err)
		}
		if !reflect.DeepEqual(hf, step.want) {
			t.Fatalf("At step index %d: Got headers %v; want %v", i, hf, step.want)
		}
		gotDynTab := d.dynTab.reverseCopy()
		if !reflect.DeepEqual(gotDynTab, step.wantDynTab) {
			t.Errorf("After step index %d, dynamic table = %v; want %v", i, gotDynTab, step.wantDynTab)
		}
		if d.dynTab.size != step.wantDynSize {
			t.Errorf("After step index %d, dynamic table size = %v; want %v", i, d.dynTab.size, step.wantDynSize)
		}
	}
}

func TestHuffmanDecodeExcessPadding(t *testing.T) {
	tests := [][]byte{
		{0xff},                                   // Padding Exceeds 7 bits
		{0x1f, 0xff},                             // {"a", 1 byte excess padding}
		{0x1f, 0xff, 0xff},                       // {"a", 2 byte excess padding}
		{0x1f, 0xff, 0xff, 0xff},                 // {"a", 3 byte excess padding}
		{0xff, 0x9f, 0xff, 0xff, 0xff},           // {"a", 29 bit excess padding}
		{'R', 0xbc, '0', 0xff, 0xff, 0xff, 0xff}, // Padding ends on partial symbol.
	}
	for i, in := range tests {
		var buf bytes.Buffer
		if _, err := HuffmanDecode(&buf, in); err != ErrInvalidHuffman {
			t.Errorf("test-%d: decode(%q) = %v; want ErrInvalidHuffman", i, in, err)
		}
	}
}

func TestHuffmanDecodeEOS(t *testing.T) {
	in := []byte{0xff, 0xff, 0xff, 0xff, 0xfc} // {EOS, "?"}
	var buf bytes.Buffer
	if _, err := HuffmanDecode(&buf, in); err != ErrInvalidHuffman {
		t.Errorf("error = %v; want ErrInvalidHuffman", err)
	}
}

func TestHuffmanDecodeMaxLengthOnTrailingByte(t *testing.T) {
	in := []byte{0x00, 0x01} // {"0", "0", "0"}
	var buf bytes.Buffer
	if err := huffmanDecode(&buf, 2, in); err != ErrStringLength {
		t.Errorf("error = %v; want ErrStringLength", err)
	}
}

func TestHuffmanDecodeCorruptPadding(t *testing.T) {
	in := []byte{0x00}
	var buf bytes.Buffer
	if _, err := HuffmanDecode(&buf, in); err != ErrInvalidHuffman {
		t.Errorf("error = %v; want ErrInvalidHuffman", err)
	}
}

func TestHuffmanDecode(t *testing.T) {
	tests := []struct {
		inHex, want string
	}{
		{"f1e3 c2e5 f23a 6ba0 ab90 f4ff", "www.example.com"},
		{"a8eb 1064 9cbf", "no-cache"},
		{"25a8 49e9 5ba9 7d7f", "custom-key"},
		{"25a8 49e9 5bb8 e8b4 bf", "custom-value"},
		{"6402", "302"},
		{"aec3 771a 4b", "private"},
		{"d07a be94 1054 d444 a820 0595 040b 8166 e082 a62d 1bff", "Mon, 21 Oct 2013 20:13:21 GMT"},
		{"9d29 ad17 1863 c78f 0b97 c8e9 ae82 ae43 d3", "https://www.example.com"},
		{"9bd9 ab", "gzip"},
		{"94e7 821d d7f2 e6c7 b335 dfdf cd5b 3960 d5af 2708 7f36 72c1 ab27 0fb5 291f 9587 3160 65c0 03ed 4ee5 b106 3d50 07",
			"foo=ASDJKHQKBZXOQWEOPIUAXQWEOIU; max-age=3600; version=1"},
	}
	for i, tt := range tests {
		var buf bytes.Buffer
		in, err := hex.DecodeString(strings.Replace(tt.inHex, " ", "", -1))
		if err != nil {
			t.Errorf("%d. hex input error: %v", i, err)
			continue
		}
		if _, err := HuffmanDecode(&buf, in); err != nil {
			t.Errorf("%d. decode error: %v", i, err)
			continue
		}
		if got := buf.String(); tt.want != got {
			t.Errorf("%d. decode = %q; want %q", i, got, tt.want)
		}
	}
}

func TestAppendHuffmanString(t *testing.T) {
	tests := []struct {
		in, want string
	}{
		{"www.example.com", "f1e3 c2e5 f23a 6ba0 ab90 f4ff"},
		{"no-cache", "a8eb 1064 9cbf"},
		{"custom-key", "25a8 49e9 5ba9 7d7f"},
		{"custom-value", "25a8 49e9 5bb8 e8b4 bf"},
		{"302", "6402"},
		{"private", "aec3 771a 4b"},
		{"Mon, 21 Oct 2013 20:13:21 GMT", "d07a be94 1054 d444 a820 0595 040b 8166 e082 a62d 1bff"},
		{"https://www.example.com", "9d29 ad17 1863 c78f 0b97 c8e9 ae82 ae43 d3"},
		{"gzip", "9bd9 ab"},
		{"foo=ASDJKHQKBZXOQWEOPIUAXQWEOIU; max-age=3600; version=1",
			"94e7 821d d7f2 e6c7 b335 dfdf cd5b 3960 d5af 2708 7f36 72c1 ab27 0fb5 291f 9587 3160 65c0 03ed 4ee5 b106 3d50 07"},
	}
	for i, tt := range tests {
		buf := []byte{}
		want := strings.Replace(tt.want, " ", "", -1)
		buf = AppendHuffmanString(buf, tt.in)
		if got := hex.EncodeToString(buf); want != got {
			t.Errorf("%d. encode = %q; want %q", i, got, want)
		}
	}
}

func TestHuffmanMaxStrLen(t *testing.T) {
	const msg = "Some string"
	huff := AppendHuffmanString(nil, msg)

	testGood := func(max int) {
		var out bytes.Buffer
		if err := huffmanDecode(&out, max, huff); err != nil {
			t.Errorf("For maxLen=%d, unexpected error: %v", max, err)
		}
		if out.String() != msg {
			t.Errorf("For maxLen=%d, out = %q; want %q", max, out.String(), msg)
		}
	}
	testGood(0)
	testGood(len(msg))
	testGood(len(msg) + 1)

	var out bytes.Buffer
	if err := huffmanDecode(&out, len(msg)-1, huff); err != ErrStringLength {
		t.Errorf("err = %v; want ErrStringLength", err)
	}
}

func TestHuffmanRoundtripStress(t *testing.T) {
	const Len = 50 // of uncompressed string
	input := make([]byte, Len)
	var output bytes.Buffer
	var huff []byte

	n := 5000
	if testing.Short() {
		n = 100
	}
	seed := time.Now().UnixNano()
	t.Logf("Seed = %v", seed)
	src := rand.New(rand.NewSource(seed))
	var encSize int64
	for i := 0; i < n; i++ {
		for l := range input {
			input[l] = byte(src.Intn(256))
		}
		huff = AppendHuffmanString(huff[:0], string(input))
		encSize += int64(len(huff))
		output.Reset()
		if err := huffmanDecode(&output, 0, huff); err != nil {
			t.Errorf("Failed to decode %q -> %q -> error %v", input, huff, err)
			continue
		}
		if !bytes.Equal(output.Bytes(), input) {
			t.Errorf("Roundtrip failure on %q -> %q -> %q", input, huff, output.Bytes())
		}
	}
	t.Logf("Compressed size of original: %0.02f%% (%v -> %v)", 100*(float64(encSize)/(Len*float64(n))), Len*n, encSize)
}

func TestHuffmanDecodeFuzz(t *testing.T) {
	const Len = 50 // of compressed
	var buf, zbuf bytes.Buffer

	n := 5000
	if testing.Short() {
		n = 100
	}
	seed := time.Now().UnixNano()
	t.Logf("Seed = %v", seed)
	src := rand.New(rand.NewSource(seed))
	numFail := 0
	for i := 0; i < n; i++ {
		zbuf.Reset()
		if i == 0 {
			// Start with at least one invalid one.
			zbuf.WriteString("00\x91\xff\xff\xff\xff\xc8")
		} else {
			for l := 0; l < Len; l++ {
				zbuf.WriteByte(byte(src.Intn(256)))
			}
		}

		buf.Reset()
		if err := huffmanDecode(&buf, 0, zbuf.Bytes()); err != nil {
			if err == ErrInvalidHuffman {
				numFail++
				continue
			}
			t.Errorf("Failed to decode %q: %v", zbuf.Bytes(), err)
			continue
		}
	}
	t.Logf("%0.02f%% are invalid (%d / %d)", 100*float64(numFail)/float64(n), numFail, n)
	if numFail < 1 {
		t.Error("expected at least one invalid huffman encoding (test starts with one)")
	}
}

func TestReadVarInt(t *testing.T) {
	type res struct {
		i        uint64
		consumed int
		err      error
	}
	tests := []struct {
		n    byte
		p    []byte
		want res
	}{
		// Fits in a byte:
		{1, []byte{0}, res{0, 1, nil}},
		{2, []byte{2}, res{2, 1, nil}},
		{3, []byte{6}, res{6, 1, nil}},
		{4, []byte{14}, res{14, 1, nil}},
		{5, []byte{30}, res{30, 1, nil}},
		{6, []byte{62}, res{62, 1, nil}},
		{7, []byte{126}, res{126, 1, nil}},
		{8, []byte{254}, res{254, 1, nil}},

		// Doesn't fit in a byte:
		{1, []byte{1}, res{0, 0, errNeedMore}},
		{2, []byte{3}, res{0, 0, errNeedMore}},
		{3, []byte{7}, res{0, 0, errNeedMore}},
		{4, []byte{15}, res{0, 0, errNeedMore}},
		{5, []byte{31}, res{0, 0, errNeedMore}},
		{6, []byte{63}, res{0, 0, errNeedMore}},
		{7, []byte{127}, res{0, 0, errNeedMore}},
		{8, []byte{255}, res{0, 0, errNeedMore}},

		// Ignoring top bits:
		{5, []byte{255, 154, 10}, res{1337, 3, nil}}, // high dummy three bits: 111
		{5, []byte{159, 154, 10}, res{1337, 3, nil}}, // high dummy three bits: 100
		{5, []byte{191, 154, 10}, res{1337, 3, nil}}, // high dummy three bits: 101

		// Extra byte:
		{5, []byte{191, 154, 10, 2}, res{1337, 3, nil}}, // extra byte

		// Short a byte:
		{5, []byte{191, 154}, res{0, 0, errNeedMore}},

		// integer overflow:
		{1, []byte{255, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128, 128}, res{0, 0, errVarintOverflow}},
	}
	for _, tt := range tests {
		i, remain, err := readVarInt(tt.n, tt.p)
		consumed := len(tt.p) - len(remain)
		got := res{i, consumed, err}
		if got != tt.want {
			t.Errorf("readVarInt(%d, %v ~ %x) = %+v; want %+v", tt.n, tt.p, tt.p, got, tt.want)
		}
	}
}

// Fuzz crash, originally reported at https://github.com/bradfitz/http2/issues/56
func TestHuffmanFuzzCrash(t *testing.T) {
	got, err := HuffmanDecodeToString([]byte("00\x91\xff\xff\xff\xff\xc8"))
	if got != "" {
		t.Errorf("Got %q; want empty string", got)
	}
	if err != ErrInvalidHuffman {
		t.Errorf("Err = %v; want ErrInvalidHuffman", err)
	}
}

func pair(name, value string) HeaderField {
	return HeaderField{Name: name, Value: value}
}

func dehex(s string) []byte {
	s = strings.Replace(s, " ", "", -1)
	s = strings.Replace(s, "\n", "", -1)
	b, err := hex.DecodeString(s)
	if err != nil {
		panic(err)
	}
	return b
}

func TestEmitEnabled(t *testing.T) {
	var buf bytes.Buffer
	enc := NewEncoder(&buf)
	enc.WriteField(HeaderField{Name: "foo", Value: "bar"})
	enc.WriteField(HeaderField{Name: "foo", Value: "bar"})

	numCallback := 0
	var dec *Decoder
	dec = NewDecoder(8<<20, func(HeaderField) {
		numCallback++
		dec.SetEmitEnabled(false)
	})
	if !dec.EmitEnabled() {
		t.Errorf("initial emit enabled = false; want true")
	}
	if _, err := dec.Write(buf.Bytes()); err != nil {
		t.Error(err)
	}
	if numCallback != 1 {
		t.Errorf("num callbacks = %d; want 1", numCallback)
	}
	if dec.EmitEnabled() {
		t.Errorf("emit enabled = true; want false")
	}
}

func TestSaveBufLimit(t *testing.T) {
	const maxStr = 1 << 10
	var got []HeaderField
	dec := NewDecoder(initialHeaderTableSize, func(hf HeaderField) {
		got = append(got, hf)
	})
	dec.SetMaxStringLength(maxStr)
	var frag []byte
	frag = append(frag[:0], encodeTypeByte(false, false))
	frag = appendVarInt(frag, 7, 3)
	frag = append(frag, "foo"...)
	frag = appendVarInt(frag, 7, 3)
	frag = append(frag, "bar"...)

	if _, err := dec.Write(frag); err != nil {
		t.Fatal(err)
	}

	want := []HeaderField{{Name: "foo", Value: "bar"}}
	if !reflect.DeepEqual(got, want) {
		t.Errorf("After small writes, got %v; want %v", got, want)
	}

	frag = append(frag[:0], encodeTypeByte(false, false))
	frag = appendVarInt(frag, 7, maxStr*3)
	frag = append(frag, make([]byte, maxStr*3)...)

	_, err := dec.Write(frag)
	if err != ErrStringLength {
		t.Fatalf("Write error = %v; want ErrStringLength", err)
	}
}


text:
// Copyright 2017 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.

// +build go1.9

package httpproxy_test

import "testing"

func init() {
	setHelper = func(t *testing.T) { t.Helper() }
}


text:
// Copyright 2017 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 httpproxy_test

import (
	"bytes"
	"errors"
	"fmt"
	"net/url"
	"os"
	"strings"
	"testing"

	"golang.org/x/net/http/httpproxy"
)

// setHelper calls t.Helper() for Go 1.9+ (see go19_test.go) and does nothing otherwise.
var setHelper = func(t *testing.T) {}

type proxyForURLTest struct {
	cfg     httpproxy.Config
	req     string // URL to fetch; blank means "http://example.com"
	want    string
	wanterr error
}

func (t proxyForURLTest) String() string {
	var buf bytes.Buffer
	space := func() {
		if buf.Len() > 0 {
			buf.WriteByte(' ')
		}
	}
	if t.cfg.HTTPProxy != "" {
		fmt.Fprintf(&buf, "http_proxy=%q", t.cfg.HTTPProxy)
	}
	if t.cfg.HTTPSProxy != "" {
		space()
		fmt.Fprintf(&buf, "https_proxy=%q", t.cfg.HTTPSProxy)
	}
	if t.cfg.NoProxy != "" {
		space()
		fmt.Fprintf(&buf, "no_proxy=%q", t.cfg.NoProxy)
	}
	req := "http://example.com"
	if t.req != "" {
		req = t.req
	}
	space()
	fmt.Fprintf(&buf, "req=%q", req)
	return strings.TrimSpace(buf.String())
}

var proxyForURLTests = []proxyForURLTest{{
	cfg: httpproxy.Config{
		HTTPProxy: "127.0.0.1:8080",
	},
	want: "http://127.0.0.1:8080",
}, {
	cfg: httpproxy.Config{
		HTTPProxy: "cache.corp.example.com:1234",
	},
	want: "http://cache.corp.example.com:1234",
}, {
	cfg: httpproxy.Config{
		HTTPProxy: "cache.corp.example.com",
	},
	want: "http://cache.corp.example.com",
}, {
	cfg: httpproxy.Config{
		HTTPProxy: "https://cache.corp.example.com",
	},
	want: "https://cache.corp.example.com",
}, {
	cfg: httpproxy.Config{
		HTTPProxy: "http://127.0.0.1:8080",
	},
	want: "http://127.0.0.1:8080",
}, {
	cfg: httpproxy.Config{
		HTTPProxy: "https://127.0.0.1:8080",
	},
	want: "https://127.0.0.1:8080",
}, {
	cfg: httpproxy.Config{
		HTTPProxy: "socks5://127.0.0.1",
	},
	want: "socks5://127.0.0.1",
}, {
	// Don't use secure for http
	cfg: httpproxy.Config{
		HTTPProxy:  "http.proxy.tld",
		HTTPSProxy: "secure.proxy.tld",
	},
	req:  "http://insecure.tld/",
	want: "http://http.proxy.tld",
}, {
	// Use secure for https.
	cfg: httpproxy.Config{
		HTTPProxy:  "http.proxy.tld",
		HTTPSProxy: "secure.proxy.tld",
	},
	req:  "https://secure.tld/",
	want: "http://secure.proxy.tld",
}, {
	cfg: httpproxy.Config{
		HTTPProxy:  "http.proxy.tld",
		HTTPSProxy: "https://secure.proxy.tld",
	},
	req:  "https://secure.tld/",
	want: "https://secure.proxy.tld",
}, {
	// Issue 16405: don't use HTTP_PROXY in a CGI environment,
	// where HTTP_PROXY can be attacker-controlled.
	cfg: httpproxy.Config{
		HTTPProxy: "http://10.1.2.3:8080",
		CGI:       true,
	},
	want:    "<nil>",
	wanterr: errors.New("refusing to use HTTP_PROXY value in CGI environment; see golang.org/s/cgihttpproxy"),
}, {
	// HTTPS proxy is still used even in CGI environment.
	// (perhaps dubious but it's the historical behaviour).
	cfg: httpproxy.Config{
		HTTPSProxy: "https://secure.proxy.tld",
		CGI:        true,
	},
	req:  "https://secure.tld/",
	want: "https://secure.proxy.tld",
}, {
	want: "<nil>",
}, {
	cfg: httpproxy.Config{
		NoProxy:   "example.com",
		HTTPProxy: "proxy",
	},
	req:  "http://example.com/",
	want: "<nil>",
}, {
	cfg: httpproxy.Config{
		NoProxy:   ".example.com",
		HTTPProxy: "proxy",
	},
	req:  "http://example.com/",
	want: "<nil>",
}, {
	cfg: httpproxy.Config{
		NoProxy:   "ample.com",
		HTTPProxy: "proxy",
	},
	req:  "http://example.com/",
	want: "http://proxy",
}, {
	cfg: httpproxy.Config{
		NoProxy:   "example.com",
		HTTPProxy: "proxy",
	},
	req:  "http://foo.example.com/",
	want: "<nil>",
}, {
	cfg: httpproxy.Config{
		NoProxy:   ".foo.com",
		HTTPProxy: "proxy",
	},
	req:  "http://example.com/",
	want: "http://proxy",
}}

func testProxyForURL(t *testing.T, tt proxyForURLTest) {
	setHelper(t)
	reqURLStr := tt.req
	if reqURLStr == "" {
		reqURLStr = "http://example.com"
	}
	reqURL, err := url.Parse(reqURLStr)
	if err != nil {
		t.Errorf("invalid URL %q", reqURLStr)
		return
	}
	cfg := tt.cfg
	proxyForURL := cfg.ProxyFunc()
	url, err := proxyForURL(reqURL)
	if g, e := fmt.Sprintf("%v", err), fmt.Sprintf("%v", tt.wanterr); g != e {
		t.Errorf("%v: got error = %q, want %q", tt, g, e)
		return
	}
	if got := fmt.Sprintf("%s", url); got != tt.want {
		t.Errorf("%v: got URL = %q, want %q", tt, url, tt.want)
	}

	// Check that changing the Config doesn't change the results
	// of the functuon.
	cfg = httpproxy.Config{}
	url, err = proxyForURL(reqURL)
	if g, e := fmt.Sprintf("%v", err), fmt.Sprintf("%v", tt.wanterr); g != e {
		t.Errorf("(after mutating config) %v: got error = %q, want %q", tt, g, e)
		return
	}
	if got := fmt.Sprintf("%s", url); got != tt.want {
		t.Errorf("(after mutating config) %v: got URL = %q, want %q", tt, url, tt.want)
	}
}

func TestProxyForURL(t *testing.T) {
	for _, tt := range proxyForURLTests {
		testProxyForURL(t, tt)
	}
}

func TestFromEnvironment(t *testing.T) {
	os.Setenv("HTTP_PROXY", "httpproxy")
	os.Setenv("HTTPS_PROXY", "httpsproxy")
	os.Setenv("NO_PROXY", "noproxy")
	os.Setenv("REQUEST_METHOD", "")
	got := httpproxy.FromEnvironment()
	want := httpproxy.Config{
		HTTPProxy:  "httpproxy",
		HTTPSProxy: "httpsproxy",
		NoProxy:    "noproxy",
	}
	if *got != want {
		t.Errorf("unexpected proxy config, got %#v want %#v", got, want)
	}
}

func TestFromEnvironmentWithRequestMethod(t *testing.T) {
	os.Setenv("HTTP_PROXY", "httpproxy")
	os.Setenv("HTTPS_PROXY", "httpsproxy")
	os.Setenv("NO_PROXY", "noproxy")
	os.Setenv("REQUEST_METHOD", "PUT")
	got := httpproxy.FromEnvironment()
	want := httpproxy.Config{
		HTTPProxy:  "httpproxy",
		HTTPSProxy: "httpsproxy",
		NoProxy:    "noproxy",
		CGI:        true,
	}
	if *got != want {
		t.Errorf("unexpected proxy config, got %#v want %#v", got, want)
	}
}

func TestFromEnvironmentLowerCase(t *testing.T) {
	os.Setenv("http_proxy", "httpproxy")
	os.Setenv("https_proxy", "httpsproxy")
	os.Setenv("no_proxy", "noproxy")
	os.Setenv("REQUEST_METHOD", "")
	got := httpproxy.FromEnvironment()
	want := httpproxy.Config{
		HTTPProxy:  "httpproxy",
		HTTPSProxy: "httpsproxy",
		NoProxy:    "noproxy",
	}
	if *got != want {
		t.Errorf("unexpected proxy config, got %#v want %#v", got, want)
	}
}

var UseProxyTests = []struct {
	host  string
	match bool
}{
	// Never proxy localhost:
	{"localhost", false},
	{"127.0.0.1", false},
	{"127.0.0.2", false},
	{"[::1]", false},
	{"[::2]", true}, // not a loopback address

	{"barbaz.net", false},     // match as .barbaz.net
	{"foobar.com", false},     // have a port but match
	{"foofoobar.com", true},   // not match as a part of foobar.com
	{"baz.com", true},         // not match as a part of barbaz.com
	{"localhost.net", true},   // not match as suffix of address
	{"local.localhost", true}, // not match as prefix as address
	{"barbarbaz.net", true},   // not match because NO_PROXY have a '.'
	{"www.foobar.com", false}, // match because NO_PROXY includes "foobar.com"
}

func TestUseProxy(t *testing.T) {
	cfg := &httpproxy.Config{
		NoProxy: "foobar.com, .barbaz.net",
	}
	for _, test := range UseProxyTests {
		if httpproxy.ExportUseProxy(cfg, test.host+":80") != test.match {
			t.Errorf("useProxy(%v) = %v, want %v", test.host, !test.match, test.match)
		}
	}
}

func TestInvalidNoProxy(t *testing.T) {
	cfg := &httpproxy.Config{
		NoProxy: ":1",
	}
	ok := httpproxy.ExportUseProxy(cfg, "example.com:80") // should not panic
	if !ok {
		t.Errorf("useProxy unexpected return; got false; want true")
	}
}


text:
// Copyright 2017 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 httpproxy provides support for HTTP proxy determination
// based on environment variables, as provided by net/http's
// ProxyFromEnvironment function.
//
// The API is not subject to the Go 1 compatibility promise and may change at
// any time.
package httpproxy

import (
	"errors"
	"fmt"
	"net"
	"net/url"
	"os"
	"strings"
	"unicode/utf8"

	"golang.org/x/net/idna"
)

// Config holds configuration for HTTP proxy settings. See
// FromEnvironment for details.
type Config struct {
	// HTTPProxy represents the value of the HTTP_PROXY or
	// http_proxy environment variable. It will be used as the proxy
	// URL for HTTP requests and HTTPS requests unless overridden by
	// HTTPSProxy or NoProxy.
	HTTPProxy string

	// HTTPSProxy represents the HTTPS_PROXY or https_proxy
	// environment variable. It will be used as the proxy URL for
	// HTTPS requests unless overridden by NoProxy.
	HTTPSProxy string

	// NoProxy represents the NO_PROXY or no_proxy environment
	// variable. It specifies URLs that should be excluded from
	// proxying as a comma-separated list of domain names or a
	// single asterisk (*) to indicate that no proxying should be
	// done. A domain name matches that name and all subdomains. A
	// domain name with a leading "." matches subdomains only. For
	// example "foo.com" matches "foo.com" and "bar.foo.com";
	// ".y.com" matches "x.y.com" but not "y.com".
	NoProxy string

	// CGI holds whether the current process is running
	// as a CGI handler (FromEnvironment infers this from the
	// presence of a REQUEST_METHOD environment variable).
	// When this is set, ProxyForURL will return an error
	// when HTTPProxy applies, because a client could be
	// setting HTTP_PROXY maliciously. See https://golang.org/s/cgihttpproxy.
	CGI bool
}

// FromEnvironment returns a Config instance populated from the
// environment variables HTTP_PROXY, HTTPS_PROXY and NO_PROXY (or the
// lowercase versions thereof). HTTPS_PROXY takes precedence over
// HTTP_PROXY for https requests.
//
// The environment values may be either a complete URL or a
// "host[:port]", in which case the "http" scheme is assumed. An error
// is returned if the value is a different form.
func FromEnvironment() *Config {
	return &Config{
		HTTPProxy:  getEnvAny("HTTP_PROXY", "http_proxy"),
		HTTPSProxy: getEnvAny("HTTPS_PROXY", "https_proxy"),
		NoProxy:    getEnvAny("NO_PROXY", "no_proxy"),
		CGI:        os.Getenv("REQUEST_METHOD") != "",
	}
}

func getEnvAny(names ...string) string {
	for _, n := range names {
		if val := os.Getenv(n); val != "" {
			return val
		}
	}
	return ""
}

// ProxyFunc returns a function that determines the proxy URL to use for
// a given request URL. Changing the contents of cfg will not affect
// proxy functions created earlier.
//
// A nil URL and nil error are returned if no proxy is defined in the
// environment, or a proxy should not be used for the given request, as
// defined by NO_PROXY.
//
// As a special case, if req.URL.Host is "localhost" (with or without a
// port number), then a nil URL and nil error will be returned.
func (cfg *Config) ProxyFunc() func(reqURL *url.URL) (*url.URL, error) {
	// Prevent Config changes from affecting the function calculation.
	// TODO Preprocess proxy settings for more efficient evaluation.
	cfg1 := *cfg
	return cfg1.proxyForURL
}

func (cfg *Config) proxyForURL(reqURL *url.URL) (*url.URL, error) {
	var proxy string
	if reqURL.Scheme == "https" {
		proxy = cfg.HTTPSProxy
	}
	if proxy == "" {
		proxy = cfg.HTTPProxy
		if proxy != "" && cfg.CGI {
			return nil, errors.New("refusing to use HTTP_PROXY value in CGI environment; see golang.org/s/cgihttpproxy")
		}
	}
	if proxy == "" {
		return nil, nil
	}
	if !cfg.useProxy(canonicalAddr(reqURL)) {
		return nil, nil
	}
	proxyURL, err := url.Parse(proxy)
	if err != nil ||
		(proxyURL.Scheme != "http" &&
			proxyURL.Scheme != "https" &&
			proxyURL.Scheme != "socks5") {
		// proxy was bogus. Try prepending "http://" to it and
		// see if that parses correctly. If not, we fall
		// through and complain about the original one.
		if proxyURL, err := url.Parse("http://" + proxy); err == nil {
			return proxyURL, nil
		}
	}
	if err != nil {
		return nil, fmt.Errorf("invalid proxy address %q: %v", proxy, err)
	}
	return proxyURL, nil
}

// useProxy reports whether requests to addr should use a proxy,
// according to the NO_PROXY or no_proxy environment variable.
// addr is always a canonicalAddr with a host and port.
func (cfg *Config) useProxy(addr string) bool {
	if len(addr) == 0 {
		return true
	}
	host, _, err := net.SplitHostPort(addr)
	if err != nil {
		return false
	}
	if host == "localhost" {
		return false
	}
	if ip := net.ParseIP(host); ip != nil {
		if ip.IsLoopback() {
			return false
		}
	}

	noProxy := cfg.NoProxy
	if noProxy == "*" {
		return false
	}

	addr = strings.ToLower(strings.TrimSpace(addr))
	if hasPort(addr) {
		addr = addr[:strings.LastIndex(addr, ":")]
	}

	for _, p := range strings.Split(noProxy, ",") {
		p = strings.ToLower(strings.TrimSpace(p))
		if len(p) == 0 {
			continue
		}
		if hasPort(p) {
			p = p[:strings.LastIndex(p, ":")]
		}
		if addr == p {
			return false
		}
		if len(p) == 0 {
			// There is no host part, likely the entry is malformed; ignore.
			continue
		}
		if p[0] == '.' && (strings.HasSuffix(addr, p) || addr == p[1:]) {
			// no_proxy ".foo.com" matches "bar.foo.com" or "foo.com"
			return false
		}
		if p[0] != '.' && strings.HasSuffix(addr, p) && addr[len(addr)-len(p)-1] == '.' {
			// no_proxy "foo.com" matches "bar.foo.com"
			return false
		}
	}
	return true
}

var portMap = map[string]string{
	"http":   "80",
	"https":  "443",
	"socks5": "1080",
}

// canonicalAddr returns url.Host but always with a ":port" suffix
func canonicalAddr(url *url.URL) string {
	addr := url.Hostname()
	if v, err := idnaASCII(addr); err == nil {
		addr = v
	}
	port := url.Port()
	if port == "" {
		port = portMap[url.Scheme]
	}
	return net.JoinHostPort(addr, port)
}

// Given a string of the form "host", "host:port", or "[ipv6::address]:port",
// return true if the string includes a port.
func hasPort(s string) bool { return strings.LastIndex(s, ":") > strings.LastIndex(s, "]") }

func idnaASCII(v string) (string, error) {
	// TODO: Consider removing this check after verifying performance is okay.
	// Right now punycode verification, length checks, context checks, and the
	// permissible character tests are all omitted. It also prevents the ToASCII
	// call from salvaging an invalid IDN, when possible. As a result it may be
	// possible to have two IDNs that appear identical to the user where the
	// ASCII-only version causes an error downstream whereas the non-ASCII
	// version does not.
	// Note that for correct ASCII IDNs ToASCII will only do considerably more
	// work, but it will not cause an allocation.
	if isASCII(v) {
		return v, nil
	}
	return idna.Lookup.ToASCII(v)
}

func isASCII(s string) bool {
	for i := 0; i < len(s); i++ {
		if s[i] >= utf8.RuneSelf {
			return false
		}
	}
	return true
}


text:
// Copyright 2017 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 httpproxy

var ExportUseProxy = (*Config).useProxy


text:
// Copyright 2009 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 httplex

import (
	"testing"
)

func isChar(c rune) bool { return c <= 127 }

func isCtl(c rune) bool { return c <= 31 || c == 127 }

func isSeparator(c rune) bool {
	switch c {
	case '(', ')', '<', '>', '@', ',', ';', ':', '\\', '"', '/', '[', ']', '?', '=', '{', '}', ' ', '\t':
		return true
	}
	return false
}

func TestIsToken(t *testing.T) {
	for i := 0; i <= 130; i++ {
		r := rune(i)
		expected := isChar(r) && !isCtl(r) && !isSeparator(r)
		if IsTokenRune(r) != expected {
			t.Errorf("isToken(0x%x) = %v", r, !expected)
		}
	}
}

func TestHeaderValuesContainsToken(t *testing.T) {
	tests := []struct {
		vals  []string
		token string
		want  bool
	}{
		{
			vals:  []string{"foo"},
			token: "foo",
			want:  true,
		},
		{
			vals:  []string{"bar", "foo"},
			token: "foo",
			want:  true,
		},
		{
			vals:  []string{"foo"},
			token: "FOO",
			want:  true,
		},
		{
			vals:  []string{"foo"},
			token: "bar",
			want:  false,
		},
		{
			vals:  []string{" foo "},
			token: "FOO",
			want:  true,
		},
		{
			vals:  []string{"foo,bar"},
			token: "FOO",
			want:  true,
		},
		{
			vals:  []string{"bar,foo,bar"},
			token: "FOO",
			want:  true,
		},
		{
			vals:  []string{"bar , foo"},
			token: "FOO",
			want:  true,
		},
		{
			vals:  []string{"foo ,bar "},
			token: "FOO",
			want:  true,
		},
		{
			vals:  []string{"bar, foo ,bar"},
			token: "FOO",
			want:  true,
		},
		{
			vals:  []string{"bar , foo"},
			token: "FOO",
			want:  true,
		},
	}
	for _, tt := range tests {
		got := HeaderValuesContainsToken(tt.vals, tt.token)
		if got != tt.want {
			t.Errorf("headerValuesContainsToken(%q, %q) = %v; want %v", tt.vals, tt.token, got, tt.want)
		}
	}
}

func TestPunycodeHostPort(t *testing.T) {
	tests := []struct {
		in, want string
	}{
		{"www.google.com", "www.google.com"},
		{"гофер.рф", "xn--c1ae0ajs.xn--p1ai"},
		{"bücher.de", "xn--bcher-kva.de"},
		{"bücher.de:8080", "xn--bcher-kva.de:8080"},
		{"[1::6]:8080", "[1::6]:8080"},
	}
	for _, tt := range tests {
		got, err := PunycodeHostPort(tt.in)
		if tt.want != got || err != nil {
			t.Errorf("PunycodeHostPort(%q) = %q, %v, want %q, nil", tt.in, got, err, tt.want)
		}
	}
}