RE: JavaScript header compressor/decompressor updated to HPACK-03

In HPACK-03, section 3.2.4 says that "To achieve this [size within bounds], repeatedly, the first entry of the header table is removed, until enough space is available for the modification."  I don't see any references in the spec to "oldest" or entry age.

Or are we talking about different things?

From: Roberto Peon [mailto:grmocg@gmail.com]
Sent: Wednesday, September 18, 2013 2:34 PM
To: Fred Akalin
Cc: HTTP Working Group
Subject: Re: JavaScript header compressor/decompressor updated to HPACK-03


If you added an item A at index 0, then B at 1, then substituted C in at 0, then B is the oldest.

-=R
On Sep 18, 2013 2:28 PM, "Fred Akalin" <akalin@google.com<mailto:akalin@google.com>> wrote:
Just to clarify, is the oldest item the one with index 0, or some other definition of oldest?

On Fri, Sep 13, 2013 at 3:16 PM, Roberto Peon <grmocg@gmail.com<mailto:grmocg@gmail.com>> wrote:

Awesome!

The expiry mechanism should always be oldest item first.

-=R
On Sep 13, 2013 2:53 PM, "Fred Akalin" <akalin@google.com<mailto:akalin@google.com>> wrote:
Hey all,

I updated http://akalin-chromium.github.io/httpbis-header-compression/compressor_test.html to implement the HPACK-03 draft. In particular, I tried to make it a complete an implementation as possible, and I added copious comments and references to the spec to make it easy to validate and understand.

The only thing I didn't implement is UTF-8 validation for header values. Hopefully, the need for that will go away.

Some thoughts:

- There aren't any tests. I wanted to see how correct I can make the implementation without them (which will be measured when the compliance suite comes out). I'm sure there are bugs.

- I didn't try very hard to make the encoder smart, but I did try to make it exercise all the opcodes.

- I found it quite helpful that the encoding context was precisely defined (as a header table plus the reference set). However, I ultimately found it better to encode the reference set as part of the header table (by having a bit per entry) instead of having a separate data structure, since it eliminates a bunch of logic to keep the indices in the two in sync. This may have been obvious to some people, but not to me. I wonder if it's in the scope of the spec to suggest this.

- I also found it helpful to have a 'touch' flag per entry since encoding/decoding requires processing of the untouched subset of the reference set.

- For encoding I also needed to keep track of the number of touches (representing the number of times the entry would be explicitly emitted), and I needed to make a distinction between no touches and 0 touches (representing an implicit emission). This is to support duplicate headers, which was tricky to get right.

- It would be nice to have explicit bounds for encoded integers, string lengths, header lengths, etc. I didn't try to make the encoder/decoder streaming, since that would complicate the implementation, but it seems difficult to guarantee memory bounds without the above explicit bounds.

- It would be nice to clarify the behavior when the max header table size is reduced. I just implemented popping from the front until the new bound is satisfied.

- I didn't find the need to encode index vs. index + 1 too confusing this time around. I feel like making the header table start at 1 would simply move the off-by-one bugs someplace else. I don't feel too strongly about this, though.

Comments, pull requests, etc. welcome!

-- Fred