Subject: [HPACK]Looking for huffman frequency tables

From: Ashok Kumar <[email-masked]>
Date: Fri, 7 Mar 2014 10:03:29 +0530

Hi, I'm unable to find the huffman frequency tables for any of the drafts.
Is this available somewhere? I'm not entirely clear on how to generate the
huffman tree with the codes already given.

Thanks in advance,
Ashok

---

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 7 Mar 2014 07:00:02 +0200

On Fri, Mar 07, 2014 at 10:03:29AM +0530, Ashok Kumar wrote:
> Is this available somewhere?

Some very old expired drafts about header compression (not HPACK) might have
that data (assuming the tables haven't been tweaked).

Other than that, I don't think the frequencies are documented anywhere.

> I'm not entirely clear on how to generate the

You don't really need to:

Each entry explicitly gives the bit sequence coding each symbol.
The string encoding is concatenation of those, followed by however
many set bits (it is specified to pad with EOS, but first 7 bits of
EOS are currently all ones) required to reach next octet boundary.

E.g. ABC is:

1101111 11101011 11101100 1 
=> DF D7 D9

1 padding bit.

And abc is:

01000 101111 01001  (2 octets)
=> 45 E9

The string happens to end on octet boundary, so no padding.

-Ilari

---

From: Ashok Kumar <[email-masked]>
Date: Fri, 7 Mar 2014 11:13:27 +0530

Thanks, encoding part was easy with the codes, but i was unsure about the
decoding side.

-- 
.- ... .... --- -.-

---

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 7 Mar 2014 09:11:08 +0200

> Thanks, encoding part was easy with the codes, but i was unsure about the

Search the table for code that is prefix of remaining bits. If found, that's
the next symbol. If not, the string ends.

This search can be implemented as state machine, that takes 4 bits at a time
and on each transition emits 0 or 1 symbols (taking 8 bits at a time leads
into larger tables and having to deal with 2 symbols at once).

The set of states of such state machine is the set of all prefixes of all
codes (I think there are 256 of those).

-Ilari