Subject: [quicwg/base-drafts] VarInt decoding pseudocode (#4316)

From: Mike Bishop <[email-masked]>
Date: Thu, 29 Oct 2020 09:13:28 -0700

Fixes #4300, if we decide we need/want it.
You can view, comment on, or merge this pull request online at:

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

-- Commit Summary --

  * VarInt decoding pseudocode

-- File Changes --

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

-- Patch Links --

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

---

From: Mike Bishop <[email-masked]>
Date: Thu, 29 Oct 2020 09:14:49 -0700

And yes, this handwaves over coercing the mask into the right size integer for the number of bytes you read.

-- 
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/4316#issuecomment-718860706

---

From: Martin Thomson <[email-masked]>
Date: Thu, 29 Oct 2020 16:55:44 -0700

@martinthomson commented on this pull request.

I think that this is a fine improvement, but I will be moving all these microalgorithm pieces under a single appendix once we're done.

> +  first_byte = data.peek()
+  prefix = first_byte >> 6
+  num_bytes = 1 << prefix
+  mask = (1 << (num_bytes * 8 - 2)) - 1
+
+  return data.read(num_bytes) & mask

```suggestion
  v = data.next_byte()
  length = (1 << (v >> 6))
  v = v & 0x3f
  repeat length-1 times:
    v = (v << 8) + data.next_byte()
```

This is not efficient in any way (I implemented it this way and it is slow), but it should be clearer.  And it doesn't rely on peeking or a read() function that returns something other than a byte.

-- 
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/4316#pullrequestreview-520167670

---

From: Jana Iyengar <[email-masked]>
Date: Thu, 29 Oct 2020 17:41:12 -0700

@janaiyengar commented on this pull request.

Thanks, @MikeBishop -- I think this is a useful improvement. 

I would just add comments above these two lines:
```
  // Length is encoded in the two most significant bits of the first byte;
  // see {{summary-of-integer-encoding}}.
  length = (1 << (v >> 6))
  // Remove the size encoding from the data
  v = v & 0x3f

-- 
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/4316#pullrequestreview-520229234

---

From: Martin Thomson <[email-masked]>
Date: Thu, 29 Oct 2020 17:42:45 -0700

Note that moustaches in figures don't get expanded into section references, so you might want to lose the reference.

-- 
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/4316#discussion_r514645048

---

From: Mike Bishop <[email-masked]>
Date: Fri, 30 Oct 2020 08:01:58 -0700

@MikeBishop pushed 1 commit.

75a56bf5d9a03bbdef8ba13b5a8f988d381e045d  Apply suggestions from code review

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/4316/files/63c950d09ec71869ee86fd4d5e007f3be1cac888..75a56bf5d9a03bbdef8ba13b5a8f988d381e045d

---

From: Lars Eggert <[email-masked]>
Date: Fri, 30 Oct 2020 08:04:19 -0700

@larseggert commented on this pull request.

> +The pseudo-code in {{alg-varint}} shows how a variable-length integer can be
+read from a stream of bytes.  The function ReadVarint takes a single argument, a
+sequence of bytes to read from.

You might want to say that this reads in network byte-order?

-- 
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/4316#pullrequestreview-520756676

---

From: Mike Bishop <[email-masked]>
Date: Fri, 30 Oct 2020 08:06:25 -0700

> I think that this is a fine improvement, but I will be moving all these microalgorithm pieces under a single appendix once we're done.

When you do that, it's probably worth copying the "Code Components" language from -recovery.

-- 
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/4316#issuecomment-719607579

---

From: Mike Bishop <[email-masked]>
Date: Fri, 30 Oct 2020 08:06:34 -0700

@MikeBishop pushed 2 commits.

e4213677504e4b326bc5beba0a4a98f78bbc699f  Add comments
5b60a9a8a0b3da85214e448d590a9fb8b0c48a42  Lars's comment

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/4316/files/75a56bf5d9a03bbdef8ba13b5a8f988d381e045d..5b60a9a8a0b3da85214e448d590a9fb8b0c48a42

---

From: Lars Eggert <[email-masked]>
Date: Fri, 30 Oct 2020 08:08:59 -0700

> +read from a stream of bytes.  The function ReadVarint takes a single argument, a
+sequence of bytes which can be read in network byte order.
+
+~~~
+ReadVarint(data):
+  // The length of variable-length integers is encoded in the
+  // first two bits of the first byte.
+  v = data.next_byte()
+  length = (1 << (v >> 6))
+
+  // Once the length is known, remove these bits and read any
+  // remaining bytes.
+  v = v & 0x3f
+  repeat length-1 times:
+    v = (v << 8) + data.next_byte()
+  return v

`v` is also in network byte-order, no?

-- 
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/4316#pullrequestreview-520760942

---

From: Mike Bishop <[email-masked]>
Date: Fri, 30 Oct 2020 08:12:09 -0700

5c18ee9353f87f9f70bfcba806ef9699a7752030  Expand for clarity

-- 
You are receiving this because you are subscribed to this thread.
View it on GitHub:
https://github.com/quicwg/base-drafts/pull/4316/files/5b60a9a8a0b3da85214e448d590a9fb8b0c48a42..5c18ee9353f87f9f70bfcba806ef9699a7752030

---

From: Mike Bishop <[email-masked]>
Date: Fri, 30 Oct 2020 08:13:09 -0700

@MikeBishop commented on this pull request.

Yes, but I'm not sure that's necessary to mention.  We haven't changed it over the course of 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/4316#discussion_r515170570

---

From: Martin Thomson <[email-masked]>
Date: Fri, 30 Oct 2020 14:44:17 -0700

How could it not be in network byte order? Unless next_byte does something other than read the next byte.

-- 
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/4316#discussion_r515396097

---

From: Lars Eggert <[email-masked]>
Date: Sat, 31 Oct 2020 02:53:24 -0700

What I meant is that we might want to say that the value still needs to co vetted into host byte order before it can be used.

-- 
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/4316#discussion_r515479483

---

From: Martin Thomson <[email-masked]>
Date: Sat, 31 Oct 2020 03:23:05 -0700

Doesn't this do that? I mean, the operations here are numeric, so unless `<<` means "divide by 2^n", we're good, right?

-- 
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/4316#discussion_r515481973