Subject: Optimizing Huffman inputs

From: Martin Thomson <[email-masked]>
Date: Sat, 12 Apr 2014 12:01:21 -0700

Now that we have a (promised) final Huffman table in HPACK, I was able
to do the little project I've been meaning to do.

With differing encoded lengths the Huffman tables add, it's not better
to use certain characters in preference to others.  Combined with the
restrictions on the strings we encode, this can make encoding binary
blobs less than optimal.

Base64 (and the URI-safe variant) manage pretty well because those
characters are favoured by HPACK.  Same goes for the cookie
characters.

I wanted to see if it was possible to do better.

It is.  But not by much.

I've put my code on github [1] and npm [2]. This module is essentially
a replacement for base64 that is optimized for HPACK and for different
character sets: the characters permitted in cookies, the characters
permitted in URI path components, and the characters permitted in
query components.

The results for 100,000 different 20 byte sequences, chosen at random,
are interesting:

Average sizes: min/ave/max (size compared against Base64+Huffman)
Raw Huffman coding (invalid):           25/48.20803/64 (203.13%)
Base 64 (no Huffman):                   27/27/27 (113.77%)
Base 64 with Huffman:                   20/23.73286/27 (100%)
bhpack cookie with Huffman:             19/23.6052/30 (99.46%)
bhpack URI safe with Huffman:           20/22.98342/28 (96.84%)
bhpack URI query with Huffman:          20/23.01238/28 (96.96%) [3]

This shows that HPACK is pretty good at encoding cookies, but there
are small gains to be had for URI components.  If character
restrictions are wildly different to these common values, this could
be even better.

This hasn't been completely optimized, so there might be a few bits
left to save.  I'm using Huffman encoding as the basis of this - in
reverse, of course - which isn't quite as good as arithmetic or range
coding.  I could probably manage the trailing bits more elegantly.
Pull requests happily accepted.

--Martin

[1] https://github.com/martinthomson/bhpack
[2] npm install bhpack
[3] In theory, this is better than the URI safe option, but as chance
would have it, not in this run.

---

From: David Krauss <[email-masked]>
Date: Sun, 13 Apr 2014 13:49:03 +0800

On 2014–04–13, at 3:01 AM, Martin Thomson <[email-masked]> wrote:

> left to save.  

Please see my earlier message on this topic, "Improving on Huffman” sent 3/17/14. In all the use cases, we tend to see sequences of similar characters: numeric, uppercase, lowercase. This corresponds to two bits of reliable prediction.

State was eliminated from the compression for security reasons, but as I argue in the previous message, I think that giving drastically different compression characteristics to uppercase, lowercase, and binary opens more security problems than carrying over two bits from the previous character does.

> I'm using Huffman encoding as the basis of this - in

Arithmetic and range codings save only up to one bit per symbol, as I understand. The current symbols tend to be larger because the coding isn’t very efficient, but a better coding with smaller symbols would see a bigger incremental gain.

---

From: Ilari Liusvaara <[email-masked]>
Date: Sun, 13 Apr 2014 12:04:08 +0300

> restrictions are wildly different to these common values, this could

The character set of cookies seems odd. Is '(' allowed without quoting?
And why is there '>' but not '<'?

> coding. 

Is the idea to choose encoding of random octet strings so that it is of
minimal size after Huffman?

I tried to calculate how well one could theoretically[1] do at this
(20 input octets):
- URI safe: 159-168 bits (average ~167 bits).
- URI safe (constant length): 169 bits.
- URI query: 158-166 bits (average ~165 bits).
- URI query (constant length): 167 bits.

The cookies have token and quoted-string forms, making calculating these
figures quite nasty...

The non-constant codes take variable length octet-string inputs and have
property that shorter input produces shorter output.

The constant length ones compress strings of given length so that output
is of constant length after Huffman (but not of constant length before
Huffman pass).

[1] There seems to be encoding and decoding algorithms for these codes
that run in polynomial time, but those are likely too slow for actual use.

-Ilari

---

From: Amos Jeffries <[email-masked]>
Date: Sun, 13 Apr 2014 21:44:54 +1200

> The cookies have token and quoted-string forms, making calculating these

Another twist to throw into this mix while you are all trying to figure
it out... Anyone interested in figuring out the answer?

With these huffman tables the DIGIT characters are represented by 4-5
huffman bits, the a-f lower case hex represented by 4-6 huffman bits and
the '%' is represented by 6 huffman bits.

Therefore selectively URL-encoding characters whose huffman
representation is over 17 bits in length will result in a compression
savings.

Encoders can trivially be written with short Huffman table where some
characters huffman symbol is actually the sequence of the three
URL-encoding characters.

Question is whether a decoder can be written with a special case to also
perform url-decode when locating the % symbol and still be fast overall ?

Secondary question; What if the Huffman symbols were further optimized
to reduce the bit length of the URL-encoding characters, and in
particular the %.

Amos

---

From: Martin Thomson <[email-masked]>
Date: Sun, 13 Apr 2014 15:09:53 -0700

> And why is there '>' but not '<'?

I ripped the list of characters from RFC 6265.  I thought that this
was odd, but I'm fairly certain that the folks writing this spec knew
what they were doing.  It's entirely possible that I introduced an
error when transcribing, but that one is (I think) right.

> minimal size after Huffman?

That's right.  The idea is to favour '0' or '1', which have four bit
encodings, over symbols with longer encodings.

---

From: Martin Thomson <[email-masked]>
Date: Sun, 13 Apr 2014 15:16:01 -0700

> perform url-decode when locating the % symbol and still be fast overall ?

That would work, but not as well as what I did, which (as Ilari
calculates) is close to ideal, less the partial bit-per-symbol loss in
comparison to using more efficient codings.  Most of the 17-bit
sequences are illegal anyway.

(You can run the experiment yourself by adding one of the high-valued
octets to the set of valid "characters".  I'm using Unicode code
points for octet values so that they fit in strings.  You'll see that
the encoder avoids using the octet as much as possible, in favour of
'0', '1', and other values with shorter encodings.)

> to reduce the bit length of the URL-encoding characters, and in

See above.  Yes it would make it more feasible to %-encode, but it
would also have a negative impact on existing strings.  There are more
existing strings, so it would have a negative net effect.

---

From: Ilari Liusvaara <[email-masked]>
Date: Mon, 14 Apr 2014 01:39:59 +0300

> error when transcribing, but that one is (I think) right.

< is 0x3C, which looks acceptable for 'cookie-octet' rule in RFC 6265.
And 'cookie-value' is formed from 'cookie-octet'...

So I think < is allowed.

-Ilari

---

From: Martin Thomson <[email-masked]>
Date: Sun, 13 Apr 2014 15:59:13 -0700

> And 'cookie-value' is formed from 'cookie-octet'...

I agree.  Transcription error on my part.