Subject: [quicwg/base-drafts] Add an appendix related to packet number decoding. (#1493)

From: Rui Paulo <[email-masked]>
Date: Wed, 27 Jun 2018 17:45:10 -0700

This PR adds an appendix with some pseudo code that show how to decode packet numbers.
The explanation in the draft was a bit terse so I think some example code might help.
You can view, comment on, or merge this pull request online at:

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

-- Commit Summary --

  * Add an appendix related to packet number decoding.

-- File Changes --

    M draft-ietf-quic-transport.md (32)

-- Patch Links --

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

---

From: Rui Paulo <[email-masked]>
Date: Wed, 27 Jun 2018 17:48:09 -0700

@rpaulo pushed 1 commit.

e52c8f9  Remove whitespace

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

---

From: Martin Thomson <[email-masked]>
Date: Wed, 27 Jun 2018 17:57:35 -0700

martinthomson commented on this pull request.

Thanks!  We've been meaning to do this for a while now.

> @@ -4778,6 +4780,36 @@ from 0xFF00 to 0xFFFF are reserved for Private Use {{!RFC8126}}.
 
 --- back
 
+# Sample code for packet number decoding {#sample-packet-number-decoding}
+
+The following pseudo-code shows how an implementation can decode packet
+numbers after packet protection has been removed.
+
+~~~
+rcv_nxt        = 0xaa82f30e + 1
+pktn           = 0x9b3
+pktn_nbits     = 14
+pktn_len       = 1 << pktn_nbits
+pktn_win       = pktn_len / 2          // 0x2000
+
+// The incoming packet number is between:
+//     [rcv_nxt - pktn_win ; rcv_nxt + pktn_win[

I would instead say the incoming packet number is greater than (rcv_next - pktn_win) and less than or equal to (rcv_next + pktn_win).  The use of '[' here implies a different interpretation, and it's not so obvious.

> @@ -4778,6 +4780,36 @@ from 0xFF00 to 0xFFFF are reserved for Private Use {{!RFC8126}}.
 
 --- back
 
+# Sample code for packet number decoding {#sample-packet-number-decoding}
+
+The following pseudo-code shows how an implementation can decode packet
+numbers after packet protection has been removed.
+
+~~~
+rcv_nxt        = 0xaa82f30e + 1

Maybe start with a function declaration:
InterpretPacketNumber(largest_received_pn, truncated_pn, truncated_pn_bits):

then you can include comments on each line that show the result of the step, as you do for pktn_win.

> +# Sample code for packet number decoding {#sample-packet-number-decoding}
+
+The following pseudo-code shows how an implementation can decode packet
+numbers after packet protection has been removed.
+
+~~~
+rcv_nxt        = 0xaa82f30e + 1
+pktn           = 0x9b3
+pktn_nbits     = 14
+pktn_len       = 1 << pktn_nbits
+pktn_win       = pktn_len / 2          // 0x2000
+
+// The incoming packet number is between:
+//     [rcv_nxt - pktn_win ; rcv_nxt + pktn_win[
+//
+// However, we can't just perform the exclusive-or of rcv_nxt

Exclusive-or might be misleading.  Also, we're concerned about being outside the window on both sides.

Maybe, "However, we can't just remove the trailing bits from rcv_nxt and add the truncated packet number because that might be outside the window."

> +rcv_nxt        = 0xaa82f30e + 1
+pktn           = 0x9b3
+pktn_nbits     = 14
+pktn_len       = 1 << pktn_nbits
+pktn_win       = pktn_len / 2          // 0x2000
+
+// The incoming packet number is between:
+//     [rcv_nxt - pktn_win ; rcv_nxt + pktn_win[
+//
+// However, we can't just perform the exclusive-or of rcv_nxt
+// (with the appropriate bits removed)  with pktn because that
+// would yield 0xaa82c9b3 which is lower than rcv_nxt - pktn_win.
+//
+// We need to find a packet number that fits the window,
+// so we add the window to the expected packet number and check
+// for overflow.

Here we find the top of the window and use that as the basis for calculating the value.  Then, the value can only be too large.

> +pktn           = 0x9b3
+pktn_nbits     = 14
+pktn_len       = 1 << pktn_nbits
+pktn_win       = pktn_len / 2          // 0x2000
+
+// The incoming packet number is between:
+//     [rcv_nxt - pktn_win ; rcv_nxt + pktn_win[
+//
+// However, we can't just perform the exclusive-or of rcv_nxt
+// (with the appropriate bits removed)  with pktn because that
+// would yield 0xaa82c9b3 which is lower than rcv_nxt - pktn_win.
+//
+// We need to find a packet number that fits the window,
+// so we add the window to the expected packet number and check
+// for overflow.
+rcv_nxt_masked  = (rcv_nxt + pktn_win) & ~(pktn_len - 1)

I would add a temporary for rcv_max = rcv_nxt + pktn_win so that you can a) explain it better, and b) use it in two places.

> +pktn_win       = pktn_len / 2          // 0x2000
+
+// The incoming packet number is between:
+//     [rcv_nxt - pktn_win ; rcv_nxt + pktn_win[
+//
+// However, we can't just perform the exclusive-or of rcv_nxt
+// (with the appropriate bits removed)  with pktn because that
+// would yield 0xaa82c9b3 which is lower than rcv_nxt - pktn_win.
+//
+// We need to find a packet number that fits the window,
+// so we add the window to the expected packet number and check
+// for overflow.
+rcv_nxt_masked  = (rcv_nxt + pktn_win) & ~(pktn_len - 1)
+decoded_pktn    = rcv_nxt_masked + pktn
+
+// Note that we also check for underflow.

"Note the extra check for underflow when the next packet number is near zero."

-- 
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/1493#pullrequestreview-132656969

---

From: Masakazu Kitajo <[email-masked]>
Date: Wed, 27 Jun 2018 18:00:44 -0700

Although I'm +1 on adding some pseudo code and this code seems nice as an implementation, I'm not sure this is also nice as a pseudo code to help understanding.

Maybe comparing two candidate packet numbers and choosing one from them (like `candidate1 - expected < candidate2 - expected`) is more straightforward approach.

-- 
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/1493#issuecomment-400877448

---

From: Martin Thomson <[email-masked]>
Date: Wed, 27 Jun 2018 18:04:36 -0700

Note that you can avoid one if statement with:

  decoded_pktn -= ((rcv_nxt + pktn_win) & (pktn_len - 1) + pktn) & (pktn_len - 1)

But no one wants to see that in a spec.

@maskit, are you suggesting the simpler code:

```python
expected = next + 1
range = 1 << nbits
mask = range - 1
candidate = (expected & mask) | truncated
if candidate <= expected - range/2:
  return candidate + range
if candidate > expected + range/2 and candidate > range:
  return candidate - range
return candidate
```

That might be better, I agree.

-- 
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/1493#issuecomment-400878018

---

From: Martin Thomson <[email-masked]>
Date: Wed, 27 Jun 2018 18:06:00 -0700

Just to be clear, the challenge with assembling candidates is that you end up with 3, not 2.

-- 
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/1493#issuecomment-400878197

---

From: Masakazu Kitajo <[email-masked]>
Date: Wed, 27 Jun 2018 18:16:33 -0700

@martinthomson Yeah, something like that. It probably make the code redundant and longer, but we shouldn't be too clever. The point is straightforwardness.

-- 
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/1493#issuecomment-400879637

---

From: Rui Paulo <[email-masked]>
Date: Wed, 27 Jun 2018 20:36:47 -0700

rpaulo commented on this pull request.

 --- back

I wanted to use this appendix as the basis for the example above but I agree we can follow the status quo

-- 
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/1493#discussion_r198699834

---

From: Rui Paulo <[email-masked]>
Date: Thu, 28 Jun 2018 17:02:35 -0700

@rpaulo pushed 1 commit.

6d2376b  Use an alternative approach to decoding the packet number.

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/1493/files/e52c8f947d9edee689aebed3546059ddf5b44759..6d2376ba3cb035ae30d6cb6a725bea096cf84f29

---

From: Rui Paulo <[email-masked]>
Date: Thu, 28 Jun 2018 17:04:28 -0700

@rpaulo pushed 1 commit.

d42c1f1  Wrap at 65

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/1493/files/6d2376ba3cb035ae30d6cb6a725bea096cf84f29..d42c1f1ad56bc5fd3045fc0fed2fe93192282451

---

From: Rui Paulo <[email-masked]>
Date: Thu, 28 Jun 2018 17:06:10 -0700

@rpaulo pushed 1 commit.

e607539  Whitespace lint

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

---

From: Martin Thomson <[email-masked]>
Date: Thu, 28 Jun 2018 17:19:06 -0700

@martinthomson pushed 1 commit.

52ba67e  Small editorial tweaks

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/1493/files/e607539abcf41f7cd57b6de8869dddb7b01de361..52ba67e4eb75b1b71e613073a86fbfeca296f70c

---

From: Martin Thomson <[email-masked]>
Date: Thu, 28 Jun 2018 17:21:01 -0700

Merged #1493.

-- 
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/1493#event-1707602158