# Copyright, 2018, by Samuel G. D. Williams. <http://www.codeotaku.com>
# Copyrigh, 2013, by Ilya Grigorik.
# 
# Permission is hereby granted, free of charge, to any person obtaining a copy
# of this software and associated documentation files (the "Software"), to deal
# in the Software without restriction, including without limitation the rights
# to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
# copies of the Software, and to permit persons to whom the Software is
# furnished to do so, subject to the following conditions:
# 
# The above copyright notice and this permission notice shall be included in
# all copies or substantial portions of the Software.
# 
# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
# THE SOFTWARE.

require_relative 'huffman/machine'

module Protocol
	module HPACK
		class CompressionError < RuntimeError
		end
		
		# Implementation of huffman encoding for HPACK
		#
		# - http://tools.ietf.org/html/draft-ietf-httpbis-header-compression-10
		class Huffman
			BITS_AT_ONCE = 4
			EOS = 256

			# Encodes provided value via huffman encoding.
			# Length is not encoded in this method.
			#
			# @param str [String]
			# @return [String] binary string
			def encode(str)
				bitstring = str.each_byte.map {|chr| ENCODE_TABLE[chr]}.join
				bitstring << '1' * ((8 - bitstring.size) % 8)
				[bitstring].pack('B*')
			end

			# Decodes provided Huffman coded string.
			#
			# @param buf [Buffer]
			# @return [String] binary string
			# @raise [CompressionError] when Huffman coded string is malformed
			def decode(buf)
				emit = ''
				state = 0 # start state

				mask = (1 << BITS_AT_ONCE) - 1
				buf.each_byte do |chr|
					(8 / BITS_AT_ONCE - 1).downto(0) do |shift|
						branch = (chr >> (shift * BITS_AT_ONCE)) & mask
						# MACHINE[state] = [final, [transitions]]
						#  [final] unfinished bits so far are prefix of the EOS code.
						# Each transition is [emit, next]
						#  [emit] character to be emitted on this transition, empty string, or EOS.
						#  [next] next state number.
						trans = MACHINE[state][branch]
						raise CompressionError, 'Huffman decode error (EOS found)' if trans.first == EOS
						emit << trans.first.chr if trans.first
						state = trans.last
					end
				end
				# Check whether partial input is correctly filled
				unless state <= MAX_FINAL_STATE
					raise CompressionError, 'Huffman decode error (EOS invalid)'
				end
				emit.force_encoding(Encoding::BINARY)
			end

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

			ENCODE_TABLE = CODES.map {|c, l| [c].pack('N').unpack('B*').first[-l..-1]}.each(&:freeze).freeze
		end
	end
end