Subject: [quicwg/base-drafts] Seek more clarify on Largest Reference/Base Index encoding (#1403)

From: Martin Thomson <[email-masked]>
Date: Tue, 29 May 2018 19:54:39 -0700

I made some changes in #1363 to the explanation of how these are encoded because I found the explanation baffling.  Here's that text, without the swap of the two values.

Now that I've read this 100 times, I think that it doesn't change anything material.  It does have one change: making sign=1, delta=0 a decoder error.  We could reclaim a bit by making the formula more complex, but that's a hard trade-off.
You can view, comment on, or merge this pull request online at:

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

-- Commit Summary --

  * Seek more clarify on Largest Reference/Base Index encoding

-- File Changes --

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

-- Patch Links --

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

---

From: Mike Bishop <[email-masked]>
Date: Wed, 30 May 2018 10:04:52 -0700

MikeBishop approved this pull request.

Minor stuff, except for where you obviously didn't type what you meant.

-    baseIndex = largestReference + deltaBaseIndex
+To save space, Base Index is encoded as a relative to the Base Index using a

relative to Largest Reference

-If the encoder inserted entries to the table while the encoding the block,
-Largest Reference will be greater than Base Index, so deltaBaseIndex will be
-negative and encoded with S=1.  If the block did not reference the most recent
-entry in the table and did not insert any new entries, Largest Reference will be
-less than Base Index, so deltaBaseIndex will be positive and encoded with S=0.
-When Largest Reference and Base Index are equal, deltaBaseIndex is 0 and encoded
-with S=0.
+That is, after turning a sign bit of 1 to -1 and 0 to 1, the absolute Base Index
+is:
+
+~~~
+    baseIndex = largestReference + sign * deltaBaseIndex

While order of operations makes this correct, it might be worth parentheses for clarity.

-If the encoder inserted entries to the table while the encoding the block,
-Largest Reference will be greater than Base Index, so deltaBaseIndex will be
-negative and encoded with S=1.  If the block did not reference the most recent
-entry in the table and did not insert any new entries, Largest Reference will be
-less than Base Index, so deltaBaseIndex will be positive and encoded with S=0.
-When Largest Reference and Base Index are equal, deltaBaseIndex is 0 and encoded
-with S=0.
+That is, after turning a sign bit of 1 to -1 and 0 to 1, the absolute Base Index
+is:
+
+~~~
+    baseIndex = largestReference + sign * deltaBaseIndex
+~~~
+
+If the encoder inserted entries to the table while the encoding the header

I know I wrote the previous iteration of this text, but this is baking in the assumption that Base Index was fixed before encoding began (i.e. single-pass encoding).  Should that be called out?

> +~~~
+
+If the encoder inserted entries to the table while the encoding the header
+block, Largest Reference will be greater than Base Index, so the encoded
+difference is negative and the sign bit will be 1.  If the header block did not
+reference the most recent entry in the table and did not insert any new entries,
+Base Index will be greater than the Largest Reference, so the delta will be
+positive and the sign bit will be 0.
+
+When Largest Reference and Base Index are equal, the Delta Base Index is encoded
+with a zero sign bit.  A sign bit set to 1 when the Delta Base Index is 0 MUST
+be treated as a decoder error.
+
+A header block that does not reference the dynamic table can use any value for
+Base Index and Largest Reference; sending zero values for both fields is the
+most efficient.

You can use any value for Base Index, and zero is the most efficient.  I'd argue that zero for Largest Reference is probably a SHOULD, given that it has a defined meaning and isn't just used for relative indexing.

-- 
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/1403#pullrequestreview-124498554

---

From: Mike Bishop <[email-masked]>
Date: Wed, 30 May 2018 17:05:54 +0000 (UTC)

MikeBishop commented on this pull request.

Also, "encoded relative to" rather than "encoded as a relative to".  Otherwise, I need to see how we encode second cousins....  😉

-- 
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/1403#discussion_r191847446

---

From: Martin Thomson <[email-masked]>
Date: Wed, 30 May 2018 20:51:44 -0700

martinthomson commented on this pull request.

+

Yeah, I considered that, but it's not a SHOULD really, especially since we have defined Largest Reference already (it's the largest absolute index in the block).  I'll adjust and let you decide if you want to merge.

-- 
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/1403#discussion_r191983189

---

From: Martin Thomson <[email-masked]>
Date: Wed, 30 May 2018 20:51:59 -0700

@martinthomson pushed 1 commit.

43df5c3  Tweaks from review

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/1403/files/5c3a6c1d8ae7a0e03c8bbf6c4b71ff51c6532c57..43df5c3c5e8e895c3b660ec84a70b5b0600b63bb

---

From: Mike Bishop <[email-masked]>
Date: Wed, 30 May 2018 21:07:29 -0700

+

Having no references and the value not being zero is a violation of what that field means.  More generally, I think a decoder that wanted to have an error case for "You didn't actually reference the Largest Reference" would be well within its rights, and we might want to either mention that and define the error code or explicitly prohibit that.

Alan's doc, his call.

-- 
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/1403#discussion_r191984683

---

From: Martin Thomson <[email-masked]>
Date: Wed, 30 May 2018 21:17:38 -0700

+

Rather than bog this PR down, let's fix that separately.

-- 
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/1403#discussion_r191985575

---

From: afrind <[email-masked]>
Date: Thu, 31 May 2018 16:26:35 -0700

afrind commented on this pull request.

-If the encoder inserted entries to the table while the encoding the block,
-Largest Reference will be greater than Base Index, so deltaBaseIndex will be
-negative and encoded with S=1.  If the block did not reference the most recent
-entry in the table and did not insert any new entries, Largest Reference will be
-less than Base Index, so deltaBaseIndex will be positive and encoded with S=0.
-When Largest Reference and Base Index are equal, deltaBaseIndex is 0 and encoded
-with S=0.
+That is, after turning a sign bit of 1 to -1 and 0 to 1, the absolute Base Index
+is:
+
+~~~
+    baseIndex = largestReference + (sign * deltaBaseIndex)
+~~~
+
+An encoder is expected to determine the absolute value of Base Index before

A single-pass encoder

I find the language about turning a sign bit somewhat confusing. 

Is it more clear to explain using a conditional?

```
if sign:
  baseIndex = largestReference - deltaBaseIndex
else:
  baseIndex = largestReference + deltaBaseIndex
```
Or index into an array?

```
signMultiplier = [ 1, -1 ]
baeIndex = largestReference + signMultipler[ sign ] * deltaBaseIndex
```

-entry in the table and did not insert any new entries, Largest Reference will be
-less than Base Index, so deltaBaseIndex will be positive and encoded with S=0.
-When Largest Reference and Base Index are equal, deltaBaseIndex is 0 and encoded
-with S=0.
+That is, after turning a sign bit of 1 to -1 and 0 to 1, the absolute Base Index
+is:
+
+~~~
+    baseIndex = largestReference + (sign * deltaBaseIndex)
+~~~
+
+An encoder is expected to determine the absolute value of Base Index before
+encoding a header block.  If the encoder inserted entries in the dynamic table
+while encoding the header block, Largest Reference will be greater than Base
+Index, so the encoded difference is negative and the sign bit will be 1.  If the

nit:  is vs. will be - can it be consistent?

-- 
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/1403#pullrequestreview-125006578

---

From: Martin Thomson <[email-masked]>
Date: Thu, 31 May 2018 18:24:11 -0700

fcd33ba  Alan's comments

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/1403/files/43df5c3c5e8e895c3b660ec84a70b5b0600b63bb..fcd33ba69d4a265dcf9a23850fbdb2317171a8fe

---

From: Martin Thomson <[email-masked]>
Date: Thu, 31 May 2018 18:24:48 -0700

Yes, this is always hard to explain, but the conditional is nice.  Verbose FTW.

-- 
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/1403#discussion_r192279479