Subject: First cut of Huffman encoding in compression document.

From: Roberto Peon <[email-masked]>
Date: Wed, 16 Oct 2013 12:20:08 -0700

The first cut of Humman encoding is now included in the compression
document.

Please take a look and shout about the parts that you find confusing/could
be better expressed.

-=R

---

From: Ilari Liusvaara <[email-masked]>
Date: Thu, 17 Oct 2013 17:17:13 +0300

> Please take a look and shout about the parts that you find confusing/could

- Lengths are marked as 8+. Are those 8 bit prefix or 0 bit prefix
  (IIRC, those were 0 bit in some past versions)?
- Is encountering a name/value without End-Of-String an error?
- Is encountering a name/value with more bytes after EOS an error?
  * Appears to be string delimiter for values?

-Ilari

---

From: Tatsuhiro Tsujikawa <[email-masked]>
Date: Fri, 18 Oct 2013 01:44:52 +0900

>   * Appears to be string delimiter for values?
I have the same impression.

As for huffman encoding, we experimented it and achieved 0.28 compression
ratio against 0.37 in the same algorithm of HPACK-03 (using mnot data set).
So 9 points improvement.
 To achieve 0.28 compression ratio, we need large (>64K) header table
buffers with HPACK-03, so huffman does the good job.

Best regards,
Tatsuhiro Tsujikawa

---

From: Roberto Peon <[email-masked]>
Date: Thu, 17 Oct 2013 11:11:48 -0700

>   (IIRC, those were 0 bit in some past versions)?

Do you mean the lengths in the huffman table?

>   * Appears to be string delimiter for values?

We have a few options here.
1) Represent length of huffman-encoded strings as *bits* in the length field
   I've done this, it works, but it bloats the encoding.
2) Represent length of huffman-encoded strings as bytes and
   a) include an EOF (or EOS :) ) terminal to indicate when the last valid
bit was read
   b) pad the last byte with bits from one of the 8+ bit symbols
   c) assume that the last character successfully decoded within the bytes
is the last one
       intended, regardless of choice of a/b

2b suffers if we don't have characters like this, though we could
manufacture one
(perhaps EOF/EOS?). Hmm.. this could work better than what we have now as it
would free up some a lower-bit-length code for an element of application
data.

2c is probably a good idea regardless, as it means that the EOF/EOS is
never going
to require adding additional bytes to the encoded data.

How about 2b+2c then (I'll need to regenerate the symbol tables, but that
shouldn't affect anyone)?

-=R

---

From: Ilari Liusvaara <[email-masked]>
Date: Thu, 17 Oct 2013 23:20:21 +0300

> Do you mean the lengths in the huffman table?

No, the length fields that nominally contain the length of huffman-
encoded value (or name).

> 2b suffers if we don't have characters like this

You are guaranteed to have one, unless there are at most 128 source symbols.

And since this is to be 8-bit clean, there are going to be at least
256(>128).

Even just UTF-8 first bytes would need 182(>128).

> shouldn't affect anyone)?

Yeah, sounds good.

Of course, this leaves the case where there is EOF/EOS in name field
(EOF/EOS in value field encodes multiple values, right?)

-Ilari

---

From: Roberto Peon <[email-masked]>
Date: Thu, 17 Oct 2013 13:44:11 -0700

Right now we're using NULL for that, since we have to be able to deal with
this in both the huffman-encoded and non-huffman-encoded case.

EOF/EOS is useful ONLY for delimiting the end of the name data or
value-list data.
-=R

---

From: Fred Akalin <[email-masked]>
Date: Thu, 17 Oct 2013 14:15:40 -0700

Initial comments:

- I may be missing something, but I'm not sure why we need a string literal
to be both length-delimited and have an end marker. I'd prefer just having
the length and assigning the short encoding for EOS to something else.
- Do we gain that much by having separate tables for request and response?
I was looking forward to not having to make a distinction between
request/response contexts since we now have a single static table, but this
separation blocks that again.
- I can see it being useful to encode both the Huffman-encoded length and
the original length of the string (or the delta between them), so that
buffers can be sized just once.

---

From: Roberto Peon <[email-masked]>
Date: Thu, 17 Oct 2013 14:32:19 -0700

I've closed the issue, though we can reopen. Please check the literal
encoding section in the header compression document (in github). I hope
this clarifies things quite a bit.

On Thu, Oct 17, 2013 at 2:15 PM, Fred Akalin <[email-masked]> wrote:

> Initial comments:
>
> - I may be missing something, but I'm not sure why we need a string
> literal to be both length-delimited and have an end marker. I'd prefer just
> having the length and assigning the short encoding for EOS to something
> else.
>

Since length is in bytes instead of bits, but huffman encoded things are
bit based, you need either to represent length in bits (which makes the
lengths bigger), or you need to ensure that the padding used to get to the
next byte boundary at the end of the string cannot be interpreted as a
valid huffman-code. What is in the document now is essentially what you've
requested. EOS is a code which is guaranteed to be 7 bits long or greater
and have no semantic meaning.

> separation blocks that again.

The tables are fairly different. You may want to experiment to see if it is
worth removing one. I still wonder if it is worthwhile to have a separate
one for cookies and the other for everything else (never did get around to
testing that).

> buffers can be sized just once.

That would bloat the on-the-wire format a fair bit. I'm hoping that we end
up storing the huffman-encoded values instead of the actual bytes in many
cases in the future.

-=R

---

From: Fred Akalin <[email-masked]>
Date: Thu, 17 Oct 2013 14:45:47 -0700

Thanks, makes sense. Your replies address all my concerns.

On Thu, Oct 17, 2013 at 2:32 PM, Roberto Peon <[email-masked]> wrote:

>> - Do we gain that much by having separate tables for request and
>> response? I was looking forward to not having to make a distinction between
> The tables are fairly different. You may want to experiment to see if it
> is worth removing one. I still wonder if it is worthwhile to have a
> separate one for cookies and the other for everything else (never did get
> around to testing that).
>
>

---

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 18 Oct 2013 03:14:10 +0300

On Thu, Oct 17, 2013 at 02:32:19PM -0700, Roberto Peon wrote:
> valid huffman-code.

You don't need EOS code for this.

This is because there are more than 128 source symbols and target alphabet
is binary, and thus there exists 8+ bit code. Prefix of that can act as
padding, it can't be mixed up with valid symbol.

-Ilari

---

From: Roberto Peon <[email-masked]>
Date: Thu, 17 Oct 2013 17:29:48 -0700

I know, I could instead state that the padding must be any code >= 7 bits,
but then implementations have to choose which character is to be used for
this, and that might vary based on the frequency table. Bleh.

By using EOS, we guarantee that when the table changes, then the symbol one
encodes as padding is always the same symbol.

Do you want to reopen the issue so we discuss it at Vancouver, or do you
find that persuasive?

-=R

---

From: Fred Akalin <[email-masked]>
Date: Thu, 17 Oct 2013 17:38:42 -0700

Random proposal, not sure if it's feasible.

Would it be possible to explicitly map EOS to '0000000', and therefore we
can just say to pad with 0s until the next byte boundary?

On Thu, Oct 17, 2013 at 5:29 PM, Roberto Peon <[email-masked]> wrote:

> By using EOS, we guarantee that when the table changes, then the symbol
> one encodes as padding is always the same symbol.
>

---

From: Roberto Peon <[email-masked]>
Date: Thu, 17 Oct 2013 17:44:28 -0700

That is probably what would happen.
There is an issue (in github already) about inverting the prefix sense
(i.e. 1->0 and vice versa) so that padding is zeros, however the part one
must be very careful about is that this is not guaranteed to happen for any
entry.
-=R

On Thu, Oct 17, 2013 at 5:38 PM, Fred Akalin <[email-masked]> wrote:

>> I know, I could instead state that the padding must be any code >= 7
>> bits, but then implementations have to choose which character is to be used
>> for this, and that might vary based on the frequency table. Bleh.
>>

---

From: Roberto Peon <[email-masked]>
Date: Thu, 17 Oct 2013 17:45:18 -0700

In other words, we can construct the code table such that padding with
zeroes is always acceptable, but it requires care in the construction of
the code table.
-=R

---

From: Fred Akalin <[email-masked]>
Date: Thu, 17 Oct 2013 18:56:54 -0700

An alternative is to mandate the padding character, e.g. say that it must
be the least code lexicographically that has >= 8 (not >= 7) bits. Or just
arbitrarily pick one and christen it the EOS bit, too.

Not sure if it's worth saving an 8+ code, though.