hpack, кодирующий целочисленное значение

Question

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'
>>>

Набрав это в IDE Python, вы увидите почти такой же вывод... Почему он отличается? Это когда число укладывается в количество битов префикса, что делает его простым.

      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
+---+---+---+---+---+---+---+---+

Октетоподобная диаграмма показывает, что создаются три разных числа... Поскольку числа создаются на протяжении всего цикла, как воспроизвести эту октетоподобную диаграмму внутри целого числа? Каков фактический конечный результат? Диаграмма или «I» равна 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?

0

http2 hpack

Источник

user18043747 08 апр '22 в 22:19

1 ответ

Другие вопросы по тегам http2 hpack

user2144578 10 апр '22 в 11:53 2022-04-10 11:53 · Answer 1 · 2022-04-10 11:53

Во-первых, что такое «префиксы» / какова их цель?

Целые числа используются в нескольких местах в сообщениях HPACK, и часто они имеют начальные биты, которые нельзя использовать для фактического целого числа. Поэтому часто будет несколько начальных цифр, которые будут недоступны для использования в самом целом числе. Они представлены X. Для целей этого расчета не имеет значения, что представляют собой эти X: могут быть 000, или 111, или 010, или... и т. д. Кроме того, не всегда будет 3 X — это просто пример. Может быть только один ведущий X, или два, или четыре... и т.д.

Например, чтобы найти предыдущий декодированный заголовок HPACK, мы используем 6.1. Индексированное представление поля заголовка , которое начинается с ведущей единицы, за которой следует значение индекса таблицы. Следовательно, 1 — это X в предыдущем примере. У нас есть 7 бит (вместо 5 бит в исходном примере в вашем вопросе). Если значение индекса таблицы равно 127 или меньше, мы можем представить его, используя эти 7 бит. Если это >= 127, то нам нужно проделать дополнительную работу (мы вернемся к этому).

Если это новое значение, которое мы хотим добавить в таблицу (для повторного использования в будущих запросах), но у нас уже есть это имя заголовка в таблице (так что это просто новое значение для этого имени, которое мы хотим использовать в качестве новой записи), тогда мы используем 6.2.1. Буквенное поле заголовка с добавочной индексацией . Это имеет 2 бита в начале ( 01- это Xs), и на этот раз у нас есть только 6 бит для представления индекса имени, которое мы хотим использовать повторно. Таким образом, в этом случае есть два X.

Так что не беспокойтесь о том, что там 3 X — это просто пример. В приведенных выше примерах был один X (поскольку первый бит должен был быть 1) и два X (поскольку первые два бита должны были быть 01) соответственно. В разделе « Целочисленное представление» рассказывается, как обрабатывать любое целое число с префиксом, независимо от того, имеет ли префикс 1, 2, 3... и т. д. неиспользуемые биты «X».

Каковы ведущие X? Для чего нужен начальный 0?

Ведущие X обсуждались выше. Начальный 0 просто потому, что в этом примере у нас есть 5 бит для представления целых чисел и нужны только 4 бита. Поэтому мы дополняем его 0. Если бы значение для кодирования было 20, это было бы 10100. Если бы значение было равно 40, мы не смогли бы уместить его в 5 бит, поэтому нужно было бы сделать что-то еще.

Набрав это в IDE Python, вы увидите почти такой же вывод... Почему он отличается?

Python использует 0bчтобы показать, что это двоичное число. Он не беспокоится о том, чтобы показывать начальные нули. Так 0b1010такой же как 0b01010а также то же, что 0b00001010.

Это когда число укладывается в количество битов префикса, что делает его простым.

В яблочко. Если вам нужно больше, чем количество бит, которое у вас есть, у вас нет места для этого. Вы не можете просто использовать больше битов, так как HPACK не будет знать, собираетесь ли вы использовать больше битов (поэтому следует смотреть на следующий байт) или это просто число (так что смотрите только на этот один байт). Чтобы это узнать, нужен сигнал. Этот сигнал использует все единицы.

Таким образом, чтобы закодировать 40 в 5 битах, нам нужно использовать, чтобы сказать «это недостаточно большое», переполнение до следующего байта. 11111в двоичном коде равно 31, поэтому мы знаем, что оно больше, поэтому мы не будем тратить его впустую, а вместо этого используем его и вычитаем из 40, чтобы получить 9, оставшиеся для кодирования в следующем байте. Новый дополнительный байт дает нам 8 новых битов для игры (на самом деле только 7, как мы скоро обнаружим, так как первый бит используется для сигнализации о дальнейшем переполнении). Этого достаточно, чтобы мы могли использовать для кодирования наши 9. Таким образом, наше комплексное число представлено двумя байтами: и 00001001.

Если мы хотим закодировать значение больше, чем можно зафиксировать в первом бите с префиксом, И оставшееся значение больше 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 и множителя весьма эффективно и означает, что это большое число (и фактически любое число до 16383) может быть представлено в трех байтах, что не случайно также является максимальным целым числом, которое может быть представлено в 7 + 7 = 14 бит. ). Но для этого нужно немного собраться с мыслями!

Если оно больше 16383, нам нужно сделать еще один раунд переполнения аналогичным образом.

Все это кажется ужасно сложным, но на самом деле закодировано относительно просто и эффективно. Компьютеры могут сделать это довольно легко и быстро.

Кажется, у меня осталось несколько бесполезных переменных, одна из которых g

Вы не печатаете это значение в ifутверждение. Только оставшееся значение в else. Вам нужно распечатать оба.

что в документации 26 + 128 == 154. Наконец, откуда берется 128? Я не могу найти никакой связи между числами, кроме того факта, что 2 в 7-й степени равно 128, но почему это важно? Это потому, что первый бит зарезервирован как флаг продолжения? а октет содержит 8 бит, поэтому 8 - 1 = 7?

Именно потому, что первый бит (значение 128) должен быть установлен в соответствии с приведенным выше объяснением, чтобы показать, что мы продолжаем/переполняемся и нуждаемся в третьем байте.