Re: [quicwg/base-drafts] QPACK: Encode Largest Reference modulo MaxEntries (#1763)

[afrind <[e-mail]>]

afrind commented on this pull request.



> @@ -149,7 +149,9 @@ peer's SETTINGS frame.
 
 Before a new entry is added to the dynamic table, entries are evicted from the
 end of the dynamic table until the size of the dynamic table is less than or
-equal to (maximum size - new entry size) or until the table is empty.
+equal to (maximum size - new entry size) or until the table is empty. The
+encoder MUST NOT evict a dynamic table entry unless it has first been

Ah.  That's a subtle difference I had missed.  This PR already has a couple things in it (how to calculate table size, for example).

> -safe to process the rest of the block.
+safe to process the rest of the block.  If Largest Reference is greater than
+zero, the encoder transforms it as follows before encoding:
+
+~~~
+   LargestReference = LargestReference mod 2*MaxEntries + 1
+~~~
+
+The decoder reconstructs the Largest Reference using the following algorithm:
+
+~~~
+   if LargestReference > 0:
+      LargestReference -= 1
+      CurrentWrapped = TableLargestAbsoluteIndex mod 2*MaxEntries
+
+      if CurrentWrapped >= LargestReference + MaxEntries:

If you have a more compact or straightforward way to express the logic I'll happily accept it.  I agree this is hard to read.  I wrote the conditionals using addition rather than subtraction to avoid underflow/negative number cases.

In my C++ code I also have an error check that LargestReference on the wire is in the range [0, 2*MaxEntries +1].  Perhaps we need a line saying that receiving an LR outside the valid range must result in a connection error?

That said, I'm pretty sure it works - I wrote a script to test it with a lot (~100B combinations) of different table sizes, decoder base and largest reference values and I get the correct decoded LR each time.

-- 
You are receiving this because you are subscribed to this thread.
Reply to this email directly or view it on GitHub:
https://github.com/quicwg/base-drafts/pull/1763#discussion_r221289630