Subject: [quicwg/base-drafts] Alternative Largest Reference Decoding algorithm. (#2248)

From: Bence Béky <[email-masked]>
Date: Sun, 23 Dec 2018 12:57:30 -0800

A Largest Reference Decoding algorithm with two fewer branches (but one more modulo operation).
You can view, comment on, or merge this pull request online at:

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

-- Commit Summary --

  * Alternative Largest Reference Decoding algorithm.

-- File Changes --

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

-- Patch Links --

https://github.com/quicwg/base-drafts/pull/2248.patch
https://github.com/quicwg/base-drafts/pull/2248.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/2248

---

From: Bence Béky <[email-masked]>
Date: Sun, 23 Dec 2018 13:01:37 -0800

This algorithm should be safe from overflow and underflow when using signed arithmetic, as long as the same width integers are used for SETTINGS_TABLE_SIZE and Largest Reference on the wire and TotalInsertionCount, because MaxEntries is bounded from above by the maximum representable number divided by 32.

When using unsigned integers, one can add 3 * MaxEntries instead of 1 * Maxentries in the first line to avoid underflow in the second line, and can break up the last line into two, checking before doing the subtraction.  A sane decoder would need to do some checking anyway to make sure that the resulting Largest Reference is at least 1.

-- 
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/2248#issuecomment-449663012

---

From: Martin Thomson <[email-masked]>
Date: Sun, 23 Dec 2018 22:28:18 -0800

The problem with code like this is that it is indecipherable.  It's short, but I don't think that it improves readability much.  Not that this code is ever readable...

-- 
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/2248#issuecomment-449692152

---

From: Bence Béky <[email-masked]>
Date: Mon, 24 Dec 2018 05:55:53 -0800

> The problem with code like this is that it is indecipherable. It's short, but I don't think that it improves readability much. Not that this code is ever readable...

I appreciate your concern.  Indeed if one is focused on the mechanics of how the decoder or Largest Reference wraps around and what that does to different quantities, the current code is easier to read.

On the other hand, if you focus on the requirement that "Largest Reference is the unique integer that is congruent with wire Largest Reference - 1 modulo 2 * MaxEntries and falls in the interval [TotalNumberOfInserts - MaxEntries, TotalNumberOfInserts + MaxEntries)", then the proposed code is easier to read.

So I believe readability is largely dependent on the mental model that readers have in their heads.

-- 
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/2248#issuecomment-449737179