Subject: [quicwg/base-drafts] Replace the RequireInsertCount decoding algorithm (#2379)

From: afrind <[email-masked]>
Date: Mon, 28 Jan 2019 00:22:59 -0800

This is @mt's alternate algorithm from #1930, and includes some of @bencebeky's language from #2249.

I renamed 'rounded' to 'MaxWrapped' - it is largest possible value for RequiredInsertCount that is 0 mod 2*MaxEntries.

Fixes #1930
Fixes #2112
You can view, comment on, or merge this pull request online at:

  https://github.com/quicwg/base-drafts/pull/2379

-- Commit Summary --

  * Replace the RequireInsertCount decoding algorithm

-- File Changes --

    M draft-ietf-quic-qpack.md (24)

-- Patch Links --

https://github.com/quicwg/base-drafts/pull/2379.patch
https://github.com/quicwg/base-drafts/pull/2379.diff

-- 
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/2379

---

From: Martin Thomson <[email-masked]>
Date: Mon, 28 Jan 2019 16:15:27 -0800

martinthomson commented on this pull request.

> -
-      if CurrentWrapped >= InsertCount + MaxEntries:
-         # Insert Count wrapped around 1 extra time
-         ReqInsertCount += 2 * MaxEntries
-      else if CurrentWrapped + MaxEntries < InsertCount:
-         # Decoder wrapped around 1 extra time
-         CurrentWrapped += 2 * MaxEntries
-
-      ReqInsertCount += TotalNumberOfInserts - CurrentWrapped
+      MaxValue = TotalNumberOfInserts + MaxEntries
+      # MaxWrapped is the largest possible value of
+      # ReqInsertCount that is 0 mod 2*MaxEntries
+      MaxWrapped = floor(MaxValue / FullRange) * FullRange
+      ReqInsertCount = MaxWrapped + EncodedInsertCount - 1
+      if ReqInsertCount > MaxValue:
+         # The Encoder's value wrapped one fewer time

This comment looks like it is attached to the next if statement rather than being an explanation of what the outer if statement is.  Maybe move it above the first if and say "# If this exceeds the maximum possible value, the encoder must have wrapped one fewer time" or something along those lines.

-- 
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/2379#pullrequestreview-197324242

---

From: afrind <[email-masked]>
Date: Mon, 28 Jan 2019 17:43:46 -0800

@afrind pushed 1 commit.

c7f153f0901a54b4be908d603b7e5560dcadbc5d  Martin's feedback

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/2379/files/e9629e9209540166fe063840ce56a4db67cf0bd7..c7f153f0901a54b4be908d603b7e5560dcadbc5d

---

From: Martin Thomson <[email-masked]>
Date: Mon, 28 Jan 2019 20:56:26 -0800

martinthomson approved this pull request.

-- 
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/2379#pullrequestreview-197377633

---

From: afrind <[email-masked]>
Date: Tue, 29 Jan 2019 18:12:43 -0800

This algorithm doesn't explicitly validate that the wire value is <= 2 * MaxEntries, and if it receives a larger value, may produce a value in the future.  

I can add an explicit error check to the algorithm, or add normative text that this is an error, or both.  I'm inclined to add it to the code?

-- 
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/2379#issuecomment-458784398

---

From: Bence Béky <[email-masked]>
Date: Tue, 29 Jan 2019 18:37:07 -0800

I agree that an error should be generated in that case and I support adding the check to the code.  Since "the decoder reconstructs the Required Insert Count using the following algorithm", and not "this is an example algorithm to reconstruct the Required Insert Count", I consider the code to be normative, so I do not think it is necessary to spell this out in text.

BTW I'm not in love with this algorithm, mostly because it is longer and more complicated than the original without improving on clarity, but I can live with it.  I still think the one I proposed at #2248 would be the least error-prone (most implementers presumably don't care about how the algorithm works, they just copy it line by line, so the fewer lines, the better), but whatever is in the draft currently, or even the one proposed here, is just fine with me after all.

-- 
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/2379#issuecomment-458789140

---

From: afrind <[email-masked]>
Date: Tue, 29 Jan 2019 19:13:06 -0800

Ah, I didn't really intend that an implementation HAD to use this algorithm.  An implementation can use any algorithm that produces correct results (or not decode at all, per @dtikhonov's impl that uses the wrapped value to index directly).  Given that it's easy to screw up the algorithm, I like having the psuedocode for copy-and-paste/no brainer.  

Therefore, let me make *that* clear and add normative language for all error cases, but I may also add the check to the algorithm.

-- 
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/2379#issuecomment-458795678

---

From: Bence Béky <[email-masked]>
Date: Wed, 30 Jan 2019 05:14:11 -0800

> Therefore, let me make _that_ clear and add normative language for all error cases, but I may also add the check to the algorithm.

I understand.  In this case, I support adding normative language for checks.

Honestly, I interpret "the decoder reconstructs the Required Insert Count using the following algorithm" as indicating that the implementation must use an algorithm that has the exact same behavior as the pseudo-code.  Therefore I propose that the error check is added to the pseudo-code as well.

Maybe the text could be changed to something like "The decoder reconstructs the Required Insert Count.  If the decoder encounters an EncodedInsertCount value that could not have been produced by a conformant encoder, then the decoder MUST signal a stream error.  An example algorithm to decode the Required Insert Count is the following.".  This would indicate to me that the pseudo-code is non-normative.  But I am also just fine with the current text, as long as the requirements (on error checking and everything else) are spelled out both in the text (because you interpret that as normative) and in pseudo-code (because I interpret that as normative).  Having consistent text + pseudo-code sounds like a good idea anyway.

-- 
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/2379#issuecomment-458938830