hpack编码整数显著性



看完后,https://httpwg.org/specs/rfc7541.html#integer.representation我对很多事情感到困惑,尽管我似乎掌握了这个想法的总体要点。首先,"前缀"究竟是什么/它们的用途是什么
对于两个:

C.1.1. Example 1: Encoding 10 Using a 5-Bit Prefix
The value 10 is to be encoded with a 5-bit prefix.
10 is less than 31 (2^5 - 1) and is represented using the 5-bit prefix.
0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| X | X | X | 0 | 1 | 0 | 1 | 0 |   10 stored on 5 bits
+---+---+---+---+---+---+---+---+

领先的X是什么?开始的0用于什么?

>>> bin(10)
'0b1010'
>>> 

在python IDE中键入此内容,您会看到几乎相同的输出。。。为什么不同?不过,这是指数字与前缀位数相匹配,使其看起来很简单。

C.1.2. Example 2: Encoding 1337 Using a 5-Bit Prefix
The value I=1337 is to be encoded with a 5-bit prefix.
1337 is greater than 31 (25 - 1).
The 5-bit prefix is filled with its max value (31).
I = 1337 - (25 - 1) = 1306.
I (1306) is greater than or equal to 128, so the while loop body executes:
I % 128 == 26
26 + 128 == 154
154 is encoded in 8 bits as: 10011010
I is set to 10 (1306 / 128 == 10)
I is no longer greater than or equal to 128, so the while loop terminates.
I, now 10, is encoded in 8 bits as: 00001010.
The process ends.
0   1   2   3   4   5   6   7
+---+---+---+---+---+---+---+---+
| X | X | X | 1 | 1 | 1 | 1 | 1 |  Prefix = 31, I = 1306
| 1 | 0 | 0 | 1 | 1 | 0 | 1 | 0 |  1306>=128, encode(154), I=1306/128
| 0 | 0 | 0 | 0 | 1 | 0 | 1 | 0 |  10<128, encode(10), done
+---+---+---+---+---+---+---+---+

类似八位位组的图表显示了正在产生的三个不同的数字。。。由于数字是在整个循环中产生的,如何在整数中复制这个类似八位位组的图?实际的最终结果是什么?图或";我"为10或00001010。

def f(a, b):
if a < 2**b - 1:
print(a)
else:
c = 2**b - 1
remain = a - c
print(c)
if remain >= 128:
while 1:
e = remain % 128
g = e + 128
remain = remain / 128
if remain >= 128:
continue
else:
print(remain)
c+=int(remain)
print(c)
break

在我试图弄清楚这一点的时候,我写了一个快速的python实现,似乎只剩下几个useless变量,其中一个是g,在文档中是26+128==154。
最后,128从哪里来?除了2的7次方是128之外,我找不到这些数字之间的任何关系,但为什么这很重要?这是因为第一位被保留为延续标志吗?一个八位位组包含8位,所以8-1=7?

首先,"前缀"究竟是什么/它们的用途是什么?

在HPACK消息中的一些地方使用整数,它们通常具有不能用于实际整数的前导位。因此,通常会有几个前导数字无法用于整数本身。它们由X表示。为了这个计算的目的,它不确定这些X是什么:可以是000、111、010或。。。等等。此外,不会总是有3个X——这只是一个例子。可能只有一个领先的X,或者两个,或者四个。。。等

例如,要查找先前HPACK解码的标头,我们使用6.1。索引头字段表示法,以前导1开头,后跟表索引值。因此,1是前面例子中的X。我们有7位(而不是您问题的原始示例中只有5位)。如果表索引值是127或更小,我们可以使用这7位来表示它。如果是>=127然后我们需要做一些额外的工作(我们会回到这个问题上来)。

如果它是我们想要添加到表中的新值(以便在将来的请求中重用),但表中已经有了该头名称(所以它只是我们想要作为新条目的名称的新值),那么我们使用6.2.1。带增量索引的文字标题字段。它的开头有2个比特(01-是X),这次我们只有6个比特来表示我们想要重用的名称的索引。在这种情况下,有两个X。

所以不要担心有3个X——这只是一个例子。在上述示例中,分别存在一个X(因为第一位必须是1)和两个X(由于前两位必须是01)。Integer Representation部分告诉您如何处理任何带前缀的整数,无论前缀是1、2、3…等等,都是不可用的";X〃;位。

领先的X是什么?开始的0用于什么?

前面讨论了领先的X。起始的0只是因为,在这个例子中,我们有5位来表示整数,只需要4位。所以我们用0填充它。如果要编码的值是20,则它将是10100。如果值是40,我们无法将其放入5位,因此需要做其他操作。

在python IDE中键入此项,您会看到几乎相同的输出。。。为什么不同?

Python使用0b来显示它是一个二进制数。它不需要显示任何前导零。所以0b10100b01010相同,也与0b00001010相同。

这是指数字符合前缀位数,使其看起来很简单。

没错。如果你需要的比特数超过了现有的比特数,那么你就没有空间了。你不能只使用更多的比特,因为HPACK不知道你是打算使用更多的字节(所以应该看看下一个字节),还是它只是一个直数(所以只看这个字节)。它需要一个信号来知道这一点。该信号使用所有1。

因此,为了在5比特中编码40,我们需要使用11111来表示"0";它不够大";,溢出到下一个字节。二进制中的11111是31,所以我们知道它比这个大,所以我们不会浪费它,而是使用它,从40中减去它,剩下9,以便在下一个字节中编码。一个新的额外字节给了我们8个新的比特(实际上只有7个,我们很快就会发现,因为第一个比特用于发出进一步溢出的信号)。这就足够了,所以我们可以使用00001001来编码我们的9。所以我们的复数用两个字节表示:XXX1111100001001

如果我们想在第一个带前缀的比特中编码一个大于可以固定的值,并且剩余的值大于127,这将适合第二个字节的可用7个比特,那么我们不能使用这种使用两个字节的溢出机制。相反,我们使用另一个";溢出,溢出";使用三个字节的机制:

为此;溢出,溢出";机制,我们像往常一样将第一个字节位设置为1以用于溢出(XXX11111),然后将第二个字节的第一个位设置为1。这留下了7位可用于对值进行编码,再加上我们必须使用的第三字节中的下8位(实际上第三字节只有7位,因为它再次使用第一位来指示另一个溢出)。

使用第二个和第三个字节,他们可以通过各种方式来实现这一点。他们决定将其编码为两个数字:128模和128乘法器。

1337 = 31 + (128 * 10) + 26

这意味着根据上一个例子,第一个字节被设置为31,第二个字节被设为26(即11010)加上前导1,以表明我们正在使用溢出溢出方法(即100011010),第三个字节被设定为10(或00001010)。

因此,1337被编码为三个字节:XXX11111 100011010 00001010(包括将X设置为这些值的任何值)。

使用128 mod和乘法器是非常有效的,这意味着这个大的数字(事实上,高达16383的任何数字)可以用三个字节表示,这不是偶然的,也是可以用7+7=14比特表示的最大整数)。但这确实需要一点头脑清醒!

如果它大于16383,那么我们需要以类似的方式进行另一轮溢出。

所有这些看起来极其复杂,但实际上是相对简单、有效地编码的。计算机可以很容易很快地做到这一点。

我似乎只剩下几个无用的变量,其中一个是g

您不会在if语句中打印此值。只有else中的剩余值。您需要打印这两个。

在文档中是26+128==154。最后,128是从哪里来的?除了2的7次方是128之外,我找不到这些数字之间的任何关系,但为什么这很重要?这是因为第一位被保留为延续标志吗?一个八位位组包含8位,所以8-1=7?

没错,这是因为第一位(值128)需要按照上面的解释进行设置,以表明我们正在继续/溢出,需要第三个字节。

最新更新