Subject: HPACK, Draft 09, Integer Representation

From: Pavel Rappo <[email-masked]>
Date: Thu, 28 Aug 2014 16:25:30 +0100

Hi everyone,

I have several questions regarding Integer Representation, if you don't mind.

(1) First of all, the section "6.1. Integer Representation" contains a
link to Wikipedia's VLQ article. The article states that: "...The VLQ
octets are arranged most significant first in a stream..." (Big Endian
from the byte stream point of view). On the other hand (from what I
understand), encoding/decoding algorithms described in the HPACK draft
works exactly the opposite -- they assume Little Endian:

decode I from the next N bits
   if I < 2^N - 1, return I
   else
       M = 0
       repeat
           B = next octet
           I = I + (B & 127) * 2^M (*)
           M = M + 7
       while B & 128 == 128
       return I

In other words there is: I = I + (B & 127) * 2^M instead of I = I* 2^M
+ (B & 127).
Either there's an error in the draft or I'm not getting it right. So
which one is it?
(2) The second question is this. Does the decoding algorithm "forget"
to add (2^N - 1) to the result in the end?
...
       while B & 128 == 128
       return I + 2^N - 1

though encoding one "remembers" to do this:

if I < 2^N - 1, encode I on N bits
   else
(*)   encode (2^N - 1) on N bits
       I = I - (2^N - 1)
       while I >= 128
            encode (I % 128 + 128) on 8 bits
            I = I / 128
       encode I on 8 bits

(3) And the third question is a minor one. When decoding algorithm
mentions "I", which "I" exactly is that?

decode I from the next N bits
   if I < 2^N - 1, return I (*)
...

If I'm not mistaken, we don't know it in that point. The whole purpose
of this code snippet is to get the "I".

-Pavel

---

From: Tatsuhiro Tsujikawa <[email-masked]>
Date: Fri, 29 Aug 2014 00:42:11 +0900

> Either there's an error in the draft or I'm not getting it right. So

​HPACK uses little endian.​

> to add (2^N - 1) to the result in the end?
"​I" is updated while loop:

       repeat
           B = next octet
           I = I + (B & 127) * 2^M

​                     ~~~~~~~~~~~~~~~~~~~~~​

           M = M + 7
       while B & 128 == 128

​
​So, initial "I" is not forgotten.​

> ​​

​"I" comes from next N bits as algorithm exactly says:​

    ​
​
decode I from the next N bits​

HPACK integer encoding uses specific prefix bits, which is described as N
here in algorithm.
So when decoding integer encoded with 7 prefix bits, decode initial "I"
from next 7 bits.

​Best regards,
Tatsuhiro Tsujikawa​

---

From: Pavel Rappo <[email-masked]>
Date: Thu, 28 Aug 2014 17:00:08 +0100

> HPACK uses little endian.

I think this difference should be mentioned explicitly.

> "I" is updated while loop:
>
>        repeat
>            B = next octet
>            I = I + (B & 127) * 2^M
>
>                      ~~~~~~~~~~~~~~~~~~~~~
>            M = M + 7
>        while B & 128 == 128
>
> So, initial "I" is not forgotten.

Thanks, Tatsuhiro! It's indeed updated. I overlooked it.

> "I" comes from next N bits as algorithm exactly says:
>
>
> So when decoding integer encoded with 7 prefix bits, decode initial "I" from
> next 7 bits.

The only thing then, the meaning of "I" is different for the encoding
and decoding parts. Isn't it?
"The algorithm to represent an integer I is as follows:" and "For
informational purpose, the algorithm to decode an integer I is as
follows:". i.e. same "I" different meanings.

On Thu, Aug 28, 2014 at 4:42 PM, Tatsuhiro Tsujikawa
<[email-masked]> wrote:
> HPACK uses little endian.
>
>
>>
> "I" is updated while loop:
>
>        repeat
>            B = next octet
>            I = I + (B & 127) * 2^M
>
>                      ~~~~~~~~~~~~~~~~~~~~~
>            M = M + 7
>        while B & 128 == 128
>
> So, initial "I" is not forgotten.
>
>
>>
> "I" comes from next N bits as algorithm exactly says:
>
>
> So when decoding integer encoded with 7 prefix bits, decode initial "I" from
> next 7 bits.
>
> Best regards,
> Tatsuhiro Tsujikawa
>
>
>>
>>

---

From: Tatsuhiro Tsujikawa <[email-masked]>
Date: Fri, 29 Aug 2014 01:12:05 +0900

> I think this difference should be mentioned explicitly.
FYI, wikipedia reference was deleted.
​
​
https://github.com/http2/http2-spec/commit/bd8d7688a9dd8708bae543a9abe889ea7797e139

​

> from
​If integer X is encoded to some byte string B and then B is decoded to
integer Y, then X should be equal to Y, so in that sense, both "I" mean
same integer.
For decoding algorithm, "I" in the sentence you quoted means the result of
the algorithm, and not just the first N bits.

​Best regards,
Tatsuhiro Tsujikawa​

---

From: Mark Nottingham <[email-masked]>
Date: Fri, 29 Aug 2014 10:47:01 +1000

See:
  https://github.com/http2/http2-spec/issues/595

I tend to think we need some text to replace it... any volunteers?

On 29 Aug 2014, at 2:12 am, Tatsuhiro Tsujikawa <[email-masked]> wrote:

> FYI, wikipedia reference was deleted. ​
> ​https://github.com/http2/http2-spec/commit/bd8d7688a9dd8708bae543a9abe889ea7797e139
> 
> ​
> ​If integer X is encoded to some byte string B and then B is decoded to integer Y, then X should be equal to Y, so in that sense, both "I" mean same integer.
> For decoding algorithm, "I" in the sentence you quoted means the result of the algorithm, and not just the first N bits.
> 
> ​Best regards,
> Tatsuhiro Tsujikawa​
> 
>  
> 
> 

--
Mark Nottingham   https://www.mnot.net/

---

From: Pavel Rappo <[email-masked]>
Date: Fri, 29 Aug 2014 16:10:52 +0100

It looks like I'm not too familiar with the spec language after all :)
Anyway, I believe "6.1." it should be as visual as it is in
Wikipedia's article and at the same time a lot more concise.

On Fri, Aug 29, 2014 at 1:47 AM, Mark Nottingham <[email-masked]> wrote:
>> If integer X is encoded to some byte string B and then B is decoded to integer Y, then X should be equal to Y, so in that sense, both "I" mean same integer.

---

From: RUELLAN Herve <[email-masked]>
Date: Fri, 29 Aug 2014 16:51:16 +0000

I made some more modifications to 6.1, to describe how variable length integer works, but I think this could be further improved. I'll try to add some drawings to this.

Hervé.

> -----Original Message-----
> From: Pavel Rappo [mailto:[email-masked]]
> Sent: vendredi 29 août 2014 17:11
> To: Mark Nottingham
> Cc: Tatsuhiro Tsujikawa; [email-masked]
> Subject: Re: HPACK, Draft 09, Integer Representation
> 
> >> https://github.com/http2/http2-
> spec/commit/bd8d7688a9dd8708bae543a9abe889ea7797e139
> >>
> >>
> >> If integer X is encoded to some byte string B and then B is decoded to
> integer Y, then X should be equal to Y, so in that sense, both "I" mean same
> integer.

---

From: Ilari Liusvaara <[email-masked]>
Date: Fri, 29 Aug 2014 21:59:41 +0300

On Fri, Aug 29, 2014 at 04:51:16PM +0000, RUELLAN Herve wrote:
> I made some more modifications to 6.1, to describe how variable
> length integer works, but I think this could be further improved.
> I'll try to add some drawings to this.

The prose seems to be missing the substraction of (2^N-1) if value
is at least that large.

That is, the second byte would contain the low 7 bits of the raw
value ("the value"), not low 7 bits of value - (2^N-1).

This would give xF 81 02 for 257@4b, whereas pseudocode gives
xF F2 01.

I presume the pseudocode is correct and 2^N-1 should be substracted.

-Ilari