module HTTP2 # Implementation of header compression for HTTP 2.0 (HPACK) format adapted # to efficiently represent HTTP headers in the context of HTTP 2.0. # # - http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-10 module Header # To decompress header blocks, a decoder only needs to maintain a # dynamic table as a decoding context. # No other state information is needed. class EncodingContext include Error # @private # Static table # - http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-10#appendix-A STATIC_TABLE = [ [':authority', ''], [':method', 'GET'], [':method', 'POST'], [':path', '/'], [':path', '/index.html'], [':scheme', 'http'], [':scheme', 'https'], [':status', '200'], [':status', '204'], [':status', '206'], [':status', '304'], [':status', '400'], [':status', '404'], [':status', '500'], ['accept-charset', ''], ['accept-encoding', 'gzip, deflate'], ['accept-language', ''], ['accept-ranges', ''], ['accept', ''], ['access-control-allow-origin', ''], ['age', ''], ['allow', ''], ['authorization', ''], ['cache-control', ''], ['content-disposition', ''], ['content-encoding', ''], ['content-language', ''], ['content-length', ''], ['content-location', ''], ['content-range', ''], ['content-type', ''], ['cookie', ''], ['date', ''], ['etag', ''], ['expect', ''], ['expires', ''], ['from', ''], ['host', ''], ['if-match', ''], ['if-modified-since', ''], ['if-none-match', ''], ['if-range', ''], ['if-unmodified-since', ''], ['last-modified', ''], ['link', ''], ['location', ''], ['max-forwards', ''], ['proxy-authenticate', ''], ['proxy-authorization', ''], ['range', ''], ['referer', ''], ['refresh', ''], ['retry-after', ''], ['server', ''], ['set-cookie', ''], ['strict-transport-security', ''], ['transfer-encoding', ''], ['user-agent', ''], ['vary', ''], ['via', ''], ['www-authenticate', ''], ].each { |pair| pair.each(&:freeze).freeze }.freeze # Current table of header key-value pairs. attr_reader :table # Current encoding options # # :table_size Integer maximum dynamic table size in bytes # :huffman Symbol :always, :never, :shorter # :index Symbol :all, :static, :never attr_reader :options # Initializes compression context with appropriate client/server # defaults and maximum size of the dynamic table. # # @param options [Hash] encoding options # :table_size Integer maximum dynamic table size in bytes # :huffman Symbol :always, :never, :shorter # :index Symbol :all, :static, :never def initialize(**options) default_options = { huffman: :shorter, index: :all, table_size: 4096, } @table = [] @options = default_options.merge(options) @limit = @options[:table_size] end # Duplicates current compression context # @return [EncodingContext] def dup other = EncodingContext.new(@options) t = @table l = @limit other.instance_eval do @table = t.dup # shallow copy @limit = l end other end # Finds an entry in current dynamic table by index. # Note that index is zero-based in this module. # # If the index is greater than the last index in the static table, # an entry in the dynamic table is dereferenced. # # If the index is greater than the last header index, an error is raised. # # @param index [Integer] zero-based index in the dynamic table. # @return [Array] +[key, value]+ def dereference(index) # NOTE: index is zero-based in this module. value = STATIC_TABLE[index] || @table[index - STATIC_TABLE.size] fail CompressionError, 'Index too large' unless value value end # Header Block Processing # - http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-10#section-4.1 # # @param cmd [Hash] { type:, name:, value:, index: } # @return [Array] +[name, value]+ header field that is added to the decoded header list def process(cmd) emit = nil case cmd[:type] when :changetablesize self.table_size = cmd[:value] when :indexed # Indexed Representation # An _indexed representation_ entails the following actions: # o The header field corresponding to the referenced entry in either # the static table or dynamic table is added to the decoded header # list. idx = cmd[:name] k, v = dereference(idx) emit = [k, v] when :incremental, :noindex, :neverindexed # A _literal representation_ that is _not added_ to the dynamic table # entails the following action: # o The header field is added to the decoded header list. # A _literal representation_ that is _added_ to the dynamic table # entails the following actions: # o The header field is added to the decoded header list. # o The header field is inserted at the beginning of the dynamic table. if cmd[:name].is_a? Integer k, v = dereference(cmd[:name]) cmd = cmd.dup cmd[:index] ||= cmd[:name] cmd[:value] ||= v cmd[:name] = k end emit = [cmd[:name], cmd[:value]] add_to_table(emit) if cmd[:type] == :incremental else fail CompressionError, "Invalid type: #{cmd[:type]}" end emit end # Plan header compression according to +@options [:index]+ # :never Do not use dynamic table or static table reference at all. # :static Use static table only. # :all Use all of them. # # @param headers [Array] +[[name, value], ...]+ # @return [Array] array of commands def encode(headers) commands = [] # Literals commands are marked with :noindex when index is not used noindex = [:static, :never].include?(@options[:index]) headers.each do |h| cmd = addcmd(h) cmd[:type] = :noindex if noindex && cmd[:type] == :incremental commands << cmd process(cmd) end commands end # Emits command for a header. # Prefer static table over dynamic table. # Prefer exact match over name-only match. # # +@options [:index]+ controls whether to use the dynamic table, # static table, or both. # :never Do not use dynamic table or static table reference at all. # :static Use static table only. # :all Use all of them. # # @param header [Array] +[name, value]+ # @return [Hash] command def addcmd(header) exact = nil name_only = nil if [:all, :static].include?(@options[:index]) STATIC_TABLE.each_index do |i| if STATIC_TABLE[i] == header exact ||= i break elsif STATIC_TABLE[i].first == header.first name_only ||= i end end end if [:all].include?(@options[:index]) && !exact @table.each_index do |i| if @table[i] == header exact ||= i + STATIC_TABLE.size break elsif @table[i].first == header.first name_only ||= i + STATIC_TABLE.size end end end if exact { name: exact, type: :indexed } elsif name_only { name: name_only, value: header.last, type: :incremental } else { name: header.first, value: header.last, type: :incremental } end end # Alter dynamic table size. # When the size is reduced, some headers might be evicted. def table_size=(size) @limit = size size_check(nil) end # Returns current table size in octets # @return [Integer] def current_table_size @table.inject(0) { |r, (k, v)| r + k.bytesize + v.bytesize + 32 } end private # Add a name-value pair to the dynamic table. # Older entries might have been evicted so that # the new entry fits in the dynamic table. # # @param cmd [Array] +[name, value]+ def add_to_table(cmd) return unless size_check(cmd) @table.unshift(cmd) end # To keep the dynamic table size lower than or equal to @limit, # remove one or more entries at the end of the dynamic table. # # @param cmd [Hash] # @return [Boolean] whether +cmd+ fits in the dynamic table. def size_check(cmd) cursize = current_table_size cmdsize = cmd.nil? ? 0 : cmd[0].bytesize + cmd[1].bytesize + 32 while cursize + cmdsize > @limit break if @table.empty? e = @table.pop cursize -= e[0].bytesize + e[1].bytesize + 32 end cmdsize <= @limit end end # Header representation as defined by the spec. HEADREP = { indexed: { prefix: 7, pattern: 0x80 }, incremental: { prefix: 6, pattern: 0x40 }, noindex: { prefix: 4, pattern: 0x00 }, neverindexed: { prefix: 4, pattern: 0x10 }, changetablesize: { prefix: 5, pattern: 0x20 }, }.each_value(&:freeze).freeze # Predefined options set for Compressor # http://mew.org/~kazu/material/2014-hpack.pdf NAIVE = { index: :never, huffman: :never }.freeze LINEAR = { index: :all, huffman: :never }.freeze STATIC = { index: :static, huffman: :never }.freeze SHORTER = { index: :all, huffman: :never }.freeze NAIVEH = { index: :never, huffman: :always }.freeze LINEARH = { index: :all, huffman: :always }.freeze STATICH = { index: :static, huffman: :always }.freeze SHORTERH = { index: :all, huffman: :shorter }.freeze # Responsible for encoding header key-value pairs using HPACK algorithm. class Compressor # @param options [Hash] encoding options def initialize(**options) @cc = EncodingContext.new(options) end # Set dynamic table size in EncodingContext # @param size [Integer] new dynamic table size def table_size=(size) @cc.table_size = size end # Encodes provided value via integer representation. # - http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-10#section-5.1 # # If I < 2^N - 1, encode I on N bits # Else # encode 2^N - 1 on N bits # I = I - (2^N - 1) # While I >= 128 # Encode (I % 128 + 128) on 8 bits # I = I / 128 # encode (I) on 8 bits # # @param i [Integer] value to encode # @param n [Integer] number of available bits # @return [String] binary string def integer(i, n) limit = 2**n - 1 return [i].pack('C') if i < limit bytes = [] bytes.push limit unless n.zero? i -= limit while (i >= 128) bytes.push((i % 128) + 128) i /= 128 end bytes.push i bytes.pack('C*') end # Encodes provided value via string literal representation. # - http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-10#section-5.2 # # * The string length, defined as the number of bytes needed to store # its UTF-8 representation, is represented as an integer with a seven # bits prefix. If the string length is strictly less than 127, it is # represented as one byte. # * If the bit 7 of the first byte is 1, the string value is represented # as a list of Huffman encoded octets # (padded with bit 1's until next octet boundary). # * If the bit 7 of the first byte is 0, the string value is # represented as a list of UTF-8 encoded octets. # # +@options [:huffman]+ controls whether to use Huffman encoding: # :never Do not use Huffman encoding # :always Always use Huffman encoding # :shorter Use Huffman when the result is strictly shorter # # @param str [String] # @return [String] binary string def string(str) plain, huffman = nil, nil unless @cc.options[:huffman] == :always plain = integer(str.bytesize, 7) << str.dup.force_encoding(Encoding::BINARY) end unless @cc.options[:huffman] == :never huffman = Huffman.new.encode(str) huffman = integer(huffman.bytesize, 7) << huffman huffman.setbyte(0, huffman.ord | 0x80) end case @cc.options[:huffman] when :always huffman when :never plain else huffman.bytesize < plain.bytesize ? huffman : plain end end # Encodes header command with appropriate header representation. # # @param h [Hash] header command # @param buffer [String] # @return [Buffer] def header(h, buffer = Buffer.new) rep = HEADREP[h[:type]] case h[:type] when :indexed buffer << integer(h[:name] + 1, rep[:prefix]) when :changetablesize buffer << integer(h[:value], rep[:prefix]) else if h[:name].is_a? Integer buffer << integer(h[:name] + 1, rep[:prefix]) else buffer << integer(0, rep[:prefix]) buffer << string(h[:name]) end buffer << string(h[:value]) end # set header representation pattern on first byte fb = buffer.ord | rep[:pattern] buffer.setbyte(0, fb) buffer end # Encodes provided list of HTTP headers. # # @param headers [Array] +[[name, value], ...]+ # @return [Buffer] def encode(headers) buffer = Buffer.new # Literal header names MUST be translated to lowercase before # encoding and transmission. headers.map! { |hk, hv| [hk.downcase, hv] } commands = @cc.encode(headers) commands.each do |cmd| buffer << header(cmd) end buffer end end # Responsible for decoding received headers and maintaining compression # context of the opposing peer. Decompressor must be initialized with # appropriate starting context based on local role: client or server. # # @example # server_role = Decompressor.new(:request) # client_role = Decompressor.new(:response) class Decompressor # @param options [Hash] decoding options. Only :table_size is effective. def initialize(**options) @cc = EncodingContext.new(options) end # Set dynamic table size in EncodingContext # @param size [Integer] new dynamic table size def table_size=(size) @cc.table_size = size end # Decodes integer value from provided buffer. # # @param buf [String] # @param n [Integer] number of available bits # @return [Integer] def integer(buf, n) limit = 2**n - 1 i = !n.zero? ? (buf.getbyte & limit) : 0 m = 0 while (byte = buf.getbyte) i += ((byte & 127) << m) m += 7 break if (byte & 128).zero? end if (i == limit) i end # Decodes string value from provided buffer. # # @param buf [String] # @return [String] UTF-8 encoded string # @raise [CompressionError] when input is malformed def string(buf) huffman = (buf.readbyte(0) & 0x80) == 0x80 len = integer(buf, 7) str = buf.read(len) fail CompressionError, 'string too short' unless str.bytesize == len str = Huffman.new.decode(Buffer.new(str)) if huffman str.force_encoding(Encoding::UTF_8) end # Decodes header command from provided buffer. # # @param buf [Buffer] # @return [Hash] command def header(buf) peek = buf.readbyte(0) header = {} header[:type], type = HEADREP.find do |_t, desc| mask = (peek >> desc[:prefix]) << desc[:prefix] mask == desc[:pattern] end fail CompressionError unless header[:type] header[:name] = integer(buf, type[:prefix]) case header[:type] when :indexed fail CompressionError if (header[:name]).zero? header[:name] -= 1 when :changetablesize header[:value] = header[:name] else if (header[:name]).zero? header[:name] = string(buf) else header[:name] -= 1 end header[:value] = string(buf) end header end # Decodes and processes header commands within provided buffer. # # @param buf [Buffer] # @return [Array] +[[name, value], ...]+ def decode(buf) list = [] list << @cc.process(header(buf)) until buf.empty? list.compact end end end end