Величина переменной длины ( VLQ ) является универсальным кодом , который использует произвольное число двоичных октетов (восьми- битовых байт ) , чтобы представлять сколь угодно большое целое число . VLQ - это, по сути, представление целого числа без знака в формате base-128 с добавлением восьмого бита для обозначения продолжения байтов. VLQ идентичен LEB128, за исключением порядка байтов . См. Пример ниже.
Приложения и история
Сжатие Base-128 известно под многими именами - VB (Variable Byte), VByte , Varint , VInt , EncInt и т. Д. [1]
Величина переменной длины ( VLQ ) была определена для использования в стандартных MIDI файлов формата [2] , чтобы сохранить дополнительное пространство для ресурсов ограничены системой, а также используется в дальнейшем расширяемый формат музыки (XMF) .
Base-128 также используется в кодировке ASN.1 BER для кодирования номеров тегов и идентификаторов объектов . [3] Он также используется в среде WAP , где называется целым числом без знака переменной длины или uintvar . DWARF формат отладки [4] определяет вариант , называемый LEB128 (или ULEB128 для чисел без знака), где по меньшей мере значительная группа из 7 битов кодируют в первом байте и наиболее значимых битов в последнем байте (так эффективно это little-endian аналог VLQ). Буферы протокола Google используют аналогичный формат для компактного представления целочисленных значений [5], как и Oracle Portable Object Format (POF) [6] и Microsoft .NET Framework «7-битное закодированное целое число» в классах BinaryReader и BinaryWriter . [7]
Он также широко используется в веб-браузерах для сопоставления источников, которые содержат множество сопоставлений целых строк и номеров столбцов, чтобы минимизировать размер карты. [8]
Целые числа переменной ширины в LLVM используют аналогичный принцип. Фрагменты кодирования имеют прямой порядок байтов и не обязательно должны иметь размер 8 бит. Документация LLVM описывает поле, которое использует 4-битный фрагмент, причем каждый фрагмент состоит из 1-битного продолжения и 3-битной полезной нагрузки. [9]
Общая структура
Кодирование предполагает октет (восьмибитовый байт), где старший значащий бит (MSB), также широко известный как бит знака , зарезервирован для указания, следует ли за ним другой октет VLQ.
7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
---|---|---|---|---|---|---|---|
2 7 | 2 6 | 2 5 | 2 4 | 2 3 | 2 2 | 2 1 | 2 0 |
А | B n |
Если A равно 0, то это последний октет VLQ целого числа. Если A равен 1, то следует другой октет VLQ.
B - это 7-битное число [0x00, 0x7F], а n - позиция октета VLQ, где B 0 является наименее значимым . Октеты VLQ располагаются первыми в потоке.
Варианты
Общая кодировка VLQ проста, но в базовой форме определена только для целых чисел без знака (неотрицательных, положительных или нулевых) и в некоторой степени избыточна, поскольку добавление октетов 0x80 соответствует заполнению нулями. Существуют различные представления чисел со знаком для обработки отрицательных чисел и методы удаления избыточности.
Групповое кодирование Varint
Google разработал Group Varint Encoding (GVE) после того, как заметил, что традиционное VLQ-кодирование вызывает множество ветвей ЦП во время декомпрессии. GVE использует один байт в качестве заголовка для 4 значений uint32 переменной длины. Байт заголовка имеет 4 2-битных числа, представляющих длину хранения каждого из следующих 4 uint32. Такая компоновка устраняет необходимость проверять и удалять биты продолжения VLQ. Байты данных можно копировать прямо в место назначения. Такая компоновка сокращает количество ветвей ЦП , что делает GVE быстрее, чем VLQ на современных конвейерных ЦП. [10]
PrefixVarint - аналогичный дизайн, но с максимумом uint64. Говорят, что он «был изобретен несколько раз независимо друг от друга». [11] Возможно преобразование в цепную версию с бесконечным числом продолжений.
Подписанные номера
Знаковый бит
Отрицательные числа можно обрабатывать с помощью знакового бита , который должен присутствовать только в первом октете.
В формате данных для Unreal Packages, используемом Unreal Engine , используется количественная схема переменной длины, называемая Compact Indices [12] . Единственная разница в этом кодировании состоит в том, что первый VLQ имеет шестой бит, зарезервированный для указания, является ли закодированное целое число положительным или отрицательным. Любой последовательный октет VLQ следует общей структуре.
Первый октет VLQ | Другие октеты VLQ | ||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |
2 7 | 2 6 | 2 5 | 2 4 | 2 3 | 2 2 | 2 1 | 2 0 | 2 7 | 2 6 | 2 5 | 2 4 | 2 3 | 2 2 | 2 1 | 2 0 |
А | B | С 0 | А | C n (n> 0) |
Если A равно 0, то это последний октет VLQ целого числа. Если A равен 1, то следует другой октет VLQ.
Если B равно 0, то VLQ представляет собой положительное целое число. Если B равно 1, то VLQ представляет собой отрицательное число.
C - кодируемый фрагмент номера, а n - позиция октета VLQ, где C 0 является наименее значимым . Октеты VLQ располагаются первыми в потоке. [ сомнительно ]
Зигзагообразное кодирование
Альтернативный способ кодирования отрицательных чисел - использовать младший бит для знака. Это, в частности, сделано для буферов протокола Google и известно как зигзагообразное кодирование для целых чисел со знаком . [13] Можно закодировать числа так, чтобы закодированный 0 соответствовал 0, от 1 до −1, от 10 до 1, от 11 до −2, от 100 до 2 и т. Д .: подсчет чередуется между неотрицательными (начиная с 0) и отрицательными ( поскольку каждый шаг изменяет младший бит, отсюда и знак), откуда и произошло название «зигзагообразное кодирование». Конкретно, преобразовать целое число, как (n << 1) ^ (n >> k - 1)
для фиксированных k- битных целых чисел.
Два дополнения
LEB128 использует дополнение до двух для представления чисел со знаком . В этой схеме представления n битов кодирует диапазон от -2 n до 2 n -1, и все отрицательные числа начинаются с 1 в старшем разряде. В подписанном LEB128 вход расширен по знаку, так что его длина кратна 7 битам. Оттуда кодирование продолжается как обычно. [14]
В LEB128 поток располагается в первую очередь с наименьшей значимостью. [14]
Удаление избыточности
С помощью VLQ-кодирования, описанного выше, любое число, которое может быть закодировано с помощью N октетов, также может быть закодировано с помощью более чем N октетов, просто путем добавления дополнительных октетов 0x80 в качестве заполнения нулями. Например, десятичное число 358 может быть закодировано как 2-октетный VLQ 0x8266 или число 0358 может быть закодировано как 3-октетное VLQ 0x808266 или 00358 как 4-октетное VLQ 0x80808266 и так далее.
Однако формат VLQ, используемый в Git [15], удаляет эту добавочную избыточность и расширяет представимый диапазон более коротких VLQ, добавляя смещение к VLQ в 2 или более октета таким образом, чтобы минимально возможное значение для такого (N + 1 ) -octet VLQ становится ровно на единицу больше, чем максимально возможное значение для N-октетного VLQ. В частности, поскольку 1-октетный VLQ может хранить максимальное значение 127, минимальному 2-октетному VLQ (0x8000) присваивается значение 128 вместо 0. И наоборот, максимальное значение такого 2-октетного VLQ (0xff7f) равно 16511 вместо 16383. Точно так же минимальный 3-октетный VLQ (0x808000) имеет значение 16512 вместо нуля, что означает, что максимальный 3-октетный VLQ (0xffff7f) равен 2113663 вместо 2097151.
Таким образом, для каждого целого числа используется одна и только одна кодировка, что делает его биективной нумерацией по основанию 128 .
Примеры
Вот проработанный пример десятичного числа 137 :
- Представьте значение в двоичной системе счисления (например, 137 как 10001001).
- Разбейте его на группы по 7 бит, начиная с младшего значащего бита (например, 137 как 0000001 0001001). Это эквивалентно представлению числа в базе 128.
- Возьмите 7 младших битов, и вы получите младший байт ( 0 000 1001). Этот байт идет последним.
- Для всех остальных групп из 7 бит (в примере это 000 0001) установите MSB равным 1 (что дает 1 000 0001 в нашем примере). Таким образом, 137 становится 1 000 0001 0 000 1001, где биты, выделенные жирным шрифтом, - это то, что мы добавили. Эти добавленные биты обозначают, следует ли следующий байт или нет. Таким образом, по определению, самый последний байт целого числа переменной длины будет иметь 0 в качестве своего MSB .
Другой способ взглянуть на это - представить значение в формате base-128, а затем установить MSB всех, кроме последней цифры base-128, равным 1.
В спецификации формата стандартного MIDI-файла приведено больше примеров: [2] [16]
Целое (десятичное) | Целое число (шестнадцатеричное) | Целое (двоичное) | Количество переменной длины (шестнадцатеричное) | Величина переменной длины (двоичная) |
---|---|---|---|---|
0 | 0x00000000 | 00000000 00000000 00000000 00000000 | 0x00 | 00000000 |
127 | 0x0000007F | 00000000 00000000 00000000 01111111 | 0x7F | 01111111 |
128 | 0x00000080 | 00000000 00000000 00000000 10000000 | 0x81 0x00 | 10000001 00000000 |
8192 | 0x00002000 | 00000000 00000000 00100000 00000000 | 0xC0 0x00 | 11000000 00000000 |
16383 | 0x00003FFF | 00000000 00000000 00111111 11111111 | 0xFF 0x7F | 11111111 01111111 |
16384 | 0x00004000 | 00000000 00000000 01000000 00000000 | 0x81 0x80 0x00 | 10000001 10000000 00000000 |
2097151 | 0x001FFFFF | 00000000 00011111 11111111 11111111 | 0xFF 0xFF 0x7F | 11111111 11111111 01111111 |
2097152 | 0x00200000 | 00000000 00100000 00000000 00000000 | 0x81 0x80 0x80 0x00 | 10000001 10000000 10000000 00000000 |
134217728 | 0x08000000 | 00001000 00000000 00000000 00000000 | 0xC0 0x80 0x80 0x00 | 11000000 10000000 10000000 00000000 |
268435455 | 0x0FFFFFFF | 00001111 11111111 11111111 11111111 | 0xFF 0xFF 0xFF 0x7F | 11111111 11111111 11111111 01111111 |
Рекомендации
- ^ Цзяньго Ван; Чунбин Линь; Яннис Папаконстантину; Стивен Суонсон. «Экспериментальное исследование сжатия растровых изображений по сравнению со сжатием с инвертированным списком» . 2017. doi : 10.1145 / 3035918.3064007
- ^ a b Формат файла MIDI: переменное количество
- ^ http://www.itu.int/ITU-T/studygroups/com17/languages/X.690-0207.pdf
- ^ Стандарт DWARF
- ^ Буферы протокола Google
- ^ Oracle Portable Object Format (POF)
- ^ Метод System.IO.BinaryWriter.Write7BitEncodedInt (INT) и System.IO.BinaryReader.Read7BitEncodedInt метод ()
- ^ Введение в исходные карты javascript
- ^ «Формат файла битового кода LLVM», раздел «Целые числа переменной ширины» . Проверено 01.10.2019.
- ^ Джефф Дин. «Проблемы построения крупномасштабных систем поиска информации» (PDF) . п. 58 . Проверено 30 мая 2020 .
- ^ Олесен, Якоб Стоклунд (31 мая 2020 г.). "стоклунд / варинт" .
- ^ http://unreal.epicgames.com/Packages.htm
- ^ Буферы протокола: кодирование: целые числа со знаком
- ^ а б Free Standards Group (декабрь 2005 г.). «Спецификация формата отладочной информации DWARF, версия 3.0» (PDF) . п. 70 . Проверено 19 июля 2009 .
- ^ https://github.com/git/git/blob/7fb6aefd2aaffe66e614f7f7b83e5b7ab16d4806/varint.c#L4
- ^ Стандартные спецификации формата MIDI-файлов. 1.1 (PDF)
Внешние ссылки
- Ассоциация производителей MIDI (MMA) - Источник спецификаций MIDI на английском языке
- Ассоциация индустрии музыкальной электроники (AMEI) - источник спецификаций MIDI на японском языке