Huffman Trie about hyper

[Sriram137]

I don't understand what non-octet-aligned data is.

Disregarding that, this is the crude algorithm I came up with
Take each number as hexadecimal from the string b'\xdb\x6d\x88\x3e\x68\xd1\xcb\x12\x25\xba\x7f' and convert them to 8 bit binary string, and concatenate them. We get

1101101101101101100010000011111001101000110100011100101100010010001001011011101001111111

(110110)(110110)(110110)(00100)(0001)(11110011)(01000)(110100)(01110)(01011)(0001)(00100)(01001)(01101)(110100)1111111

Looking at the reverse mapping from HPACK specifation, we figure its www.example.com

This reverse mapping can be done using a prefix tree.

Any reason why this wont work?

[Lukasa]

That's exactly what I'd be wanting to do. =)

When I say "non-octet-aligned data", what I mean is that each prefix in the tree may not be a multiple of 8 bits. This is because, as you've spotted, the Huffman mapping in the HPACK spec uses between 3 and 27 bits per character, with no requirement that it be a multiple of 8.

Your proposed implementation above looks reasonable. It's probably easy enough to get that by building on top of your Gist, turning it into a suitable wrapping class. If you want to do that yourself, that's fine: you should make a Pull Request. =) If you don't want to, I'm happy to build on your Gist and credit you accordingly. Let me know.

[Sriram137]

I'll finish it in a couple of hours, and send you a pull request/gist.
Do you happen to have a file which contains the encoding for requests and response, so I could test it ?

[Lukasa]

The easiest examples are from the HPACK spec, in these sections: E.3 (Request examples with Huffman, which will use the Requests encoding table in Appendix C) and E.5 (Response examples with Huffman, which will use the Responses encoding table in Appendix D). The exact tests are like this:

E.3

db6d 883e 68d1 cb12 25ba 7f -> www.example.com
6365 4a13 98ff -> no-cache
4eb0 8b74 9790 fa7f -> custom-key
4eb0 8b74 979a 17a8 ff -> custom-value

E.5

409f -> 302
c31b 39bf 387f -> private
a2fb a203 20f2 ab30 3124 018b 490d 3209 e877 -> Mon, 21 Oct 2013 20:13:21 GMT
e39e 7864 dd7a fd3d 3d24 8747 db87 2849 55f6 ff -> https://www.example.com
df7d fb36 d3d9 e1fc fc3f afe7 abfc fefc bfaf 3edf 2f97 7fd3 6ff7 fd79 f6f9 77fd 3de1 6bfa 46fe 10d8 8944 7de1 ce18 e565 f76c 2f -> foo=ASDJKHQKBZXOQWEOPIUAXQWEOIU; max-age=3600; version=1

This should be a decent set of tests to begin with.

[Lukasa]

Fixed by #5.