Re: Understanding how HPAC draft-02 works

Any removal from the state set requires that anything that pointed to it be
removed (else you'd segv or equivalent).
Thus, substitution or expiry always requires the corresponding
reference-set entry to be removed.

Your sentence: "But to
handle common header gracefully with eviction, when the entry in
the header table is removed from the header table due to the
eviction or substitution, if the entry is in the reference set
and it is not emitted in the current header processing, emit the
entry on the removal."

is thus partially correct.

The entry should be removed, but not emitted-- the draft currently
specifies emitting things only when:

   - The entry is indexed, and is not present in the reference set
   - A new entry is added
   - The entry is in the reference set after all operations have been
   processed AND it hasn't been emitted.


Much of the algorithm you define seems reasonable to me (there are a few
optimizations, but who cares right now? :) ).

Would you like to raise an issue so that we can track any confusion here?

-=R



On Fri, Aug 23, 2013 at 10:47 AM, Tatsuhiro Tsujikawa <tatsuhiro.t@gmail.com
> wrote:

> I'm trying to figure out how the HPAC works.  HPAC says that it
> clarify the eviction and index shadowing, but I'm under the
> impression that HPAC is still not clear how the entry in the
> reference set is removed from the header table because of
> eviction or substitution. This is important because, due to the
> differential encoding, the encoder and decoder must agree with
> the "common" headers, which may be removed from the header table
> because of eviction or substitution.
>
> After several tries and error, I came up with the following
> encoder/decoder procedures, which I hopefully think that
> conforming to the HPAC draft (well, I may be completely wrong).
>
> Encoder
> -------
>
> 1. For each entry in the reference set, check that it is present
>    in the current header set. If it is not, encode it as indexed
>    representation and remove it from the reference set.
>
> 2. For each entry in the reference set, check that it is present
>    in the current header set. If it is present, mark the entry
>    as "common-header" and remove the matching name/value pair
>    from current header set (if multiple name/value pairs are
>    matched, only one of them is removed from the current header
>    set).
>
> 3. Encode the rest of name/value pair in current header set. For each
>    name/value pair:
>
> 3.1. If name/value pair is present in the header table, and the
>      corresponding entry in the header table is NOT in the
>      reference set, add the entry to the reference set and encode
>      it as indexed representation. Mark the entry "emitted".
>
> 3.2. If name/value pair is present in the header table, and the
>      corresponding entry in the header table is in the reference
>      set: If the entry is marked as "common-header", then this is
>      the 2nd occurrence of the same indexed representation. To
>      encode this name/value pair, we have to encode 4 indexed
>      representation. 2 for the 1st one (which was removed in step
>      2), and the another 2 for the current name/value pair.
>      Unmark the entry "common-header" and mark it "emitted".
>
>      If the entry is marked as "emitted", then this is also the
>      occurrences of the same indexed representation. But this time,
>      we just encode 2 indexed representation.
>
> 3.3. Otherwise, encoder encodes name/value pair as literal
>      representation.  On eviction or substitution, if the removed
>      entry is in the reference set, it is removed from the
>      reference set.
>
> 4. After all current header set is processed, unmark all entries in
>    the header table.
>
> Decoder
> -------
>
> Decoder generally just performs what the encoder emitted.  But to
> handle common header gracefully with eviction, when the entry in
> the header table is removed from the header table due to the
> eviction or substitution, if the entry is in the reference set
> and it is not emitted in the current header processing, emit the
> entry on the removal.
>
> --
>
> I implemented the above encoder/decoder procedure and it seems to
> work.  But I'm not sure it conforms to the current draft,
> especially for the Encoder step 2 and Decoder's header emission
> on the eviction because they are not described in the draft at
> all. There is certainly better, correct way to go, but currently
> I failed to see it. How do you read the draft?
>
> Best regards,
>
> Tatsuhiro Tsujikawa
>
>