ЛЕБ128
LEB128 или Little Endian Base 128 — это сжатие кода переменной длины, используемое для хранения произвольно больших целых чисел в небольшом количестве байтов. LEB128 используется в DWARF. формате файла отладки [1] [2] и двоичная кодировка WebAssembly для всех целочисленных литералов. [3]
Формат кодирования
[ редактировать ]Формат LEB128 очень похож на формат величин переменной длины (VLQ); Основное отличие состоит в том, что LEB128 имеет прямой порядок байтов , тогда как величины переменной длины имеют обратный порядок байтов . Оба позволяют хранить небольшие числа в одном байте, а также позволяют кодировать числа произвольной длины. Существует две версии LEB128: беззнаковый LEB128 и подписанный LEB128. Декодер должен знать, является ли закодированное значение беззнаковым LEB128 или знаковым LEB128.
Без знака LEB128
[ редактировать ]Чтобы закодировать беззнаковое число с помощью беззнакового LEB128 ( ULEB128 ), сначала представьте число в двоичном формате. Затем ноль расширяет число до числа, кратного 7 битам (так что, если число не равно нулю, старшие 7 бит не все равны 0). Разбейте число на группы по 7 бит. Выведите один закодированный байт для каждой 7-битной группы, от наименее значимой до наиболее значимой группы. Каждый байт будет содержать группу из 7 младших битов. Установите старший бит для каждого байта, кроме последнего. Число ноль кодируется одним байтом 0x00.
В качестве примера, вот как кодируется беззнаковое число 624485:
MSB ------------------ LSB 10011000011101100101 In raw binary 010011000011101100101 Padded to a multiple of 7 bits 0100110 0001110 1100101 Split into 7-bit groups 00100110 10001110 11100101 Add high 1 bits on all but last (most significant) group to form bytes 0x26 0x8E 0xE5 In hexadecimal → 0xE5 0x8E 0x26 Output stream (LSB to MSB)
Беззнаковые LEB128 и VLQ ( количество переменной длины ) сжимают любое целое число не только в одинаковое количество битов, но и в одни и те же биты — эти два формата отличаются только тем, как именно расположены эти биты.
Подписано ЛЕБ128
[ редактировать ]Число со знаком представляется аналогично: начиная с представление дополнения до двух битов , где кратно 7, число разбито на группы как для беззнаковой кодировки.
Например, число со знаком -123456 кодируется как 0xC0 0xBB 0x78:
MSB ------------------ LSB 11110001001000000 Binary encoding of 123456 000011110001001000000 As a 21-bit number 111100001110110111111 Negating all bits (ones' complement) 111100001110111000000 Adding one (two's complement) 1111000 0111011 1000000 Split into 7-bit groups 01111000 10111011 11000000 Add high 1 bits on all but last (most significant) group to form bytes 0x78 0xBB 0xC0 In hexadecimal → 0xC0 0xBB 0x78 Output stream (LSB to MSB)
Быстрое декодирование
[ редактировать ]Простая скалярная реализация декодирования LEB128 довольно медленная, особенно на современном оборудовании, где неверное предсказание перехода обходится относительно дорого. В серии статей представлены методы SIMD для ускорения декодирования (в этих статьях они называются VByte, но это другое название той же кодировки). Статья «Векторизованное декодирование VByte». [4] представил «Masked VByte», который продемонстрировал скорость 650–2700 миллионов целых чисел в секунду на обычном оборудовании Haswell , в зависимости от плотности кодирования. В последующем документе был представлен вариант кодировки «Stream VByte: более быстрое байт-ориентированное целочисленное сжатие». [5] что увеличило скорость до более чем 4 миллиардов целых чисел в секунду. Это кодирование потока отделяет поток управления от закодированных данных, поэтому несовместимо с двоичным кодом с LEB128.
C-подобный псевдокод
[ редактировать ]Кодировать целое число без знака
[ редактировать ]do {
byte = low-order 7 bits of value;
value >>= 7;
if (value != 0) /* more bytes to come */
set high-order bit of byte;
emit byte;
} while (value != 0);
Закодировать целое число со знаком
[ редактировать ]more = 1;
negative = (value < 0);
/* the size in bits of the variable value, e.g., 64 if value's type is int64_t */
size = no. of bits in signed integer;
while (more) {
byte = low-order 7 bits of value;
value >>= 7;
/* the following is only necessary if the implementation of >>= uses a
logical shift rather than an arithmetic shift for a signed left operand */
if (negative)
value |= (~0 << (size - 7)); /* sign extend */
/* sign bit of byte is second high-order bit (0x40) */
if ((value == 0 && sign bit of byte is clear) || (value == -1 && sign bit of byte is set))
more = 0;
else
set high-order bit of byte;
emit byte;
}
Декодировать целое число без знака
[ редактировать ]result = 0;
shift = 0;
while (true) {
byte = next byte in input;
result |= (low-order 7 bits of byte) << shift;
if (high-order bit of byte == 0)
break;
shift += 7;
}
Декодировать целое число со знаком
[ редактировать ]result = 0;
shift = 0;
/* the size in bits of the result variable, e.g., 64 if result's type is int64_t */
size = number of bits in signed integer;
do {
byte = next byte in input;
result |= (low-order 7 bits of byte << shift);
shift += 7;
} while (high-order bit of byte != 0);
/* sign bit of byte is second high-order bit (0x40) */
if ((shift <size) && (sign bit of byte is set))
/* sign extend */
result |= (~0 << shift);
JavaScript-код
[ редактировать ]Закодировать 32-битное целое число со знаком
[ редактировать ]const encodeSignedLeb128FromInt32 = (value) => {
value |= 0;
const result = [];
while (true) {
const byte_ = value & 0x7f;
value >>= 7;
if (
(value === 0 && (byte_ & 0x40) === 0) ||
(value === -1 && (byte_ & 0x40) !== 0)
) {
result.push(byte_);
return result;
}
result.push(byte_ | 0x80);
}
};
Декодировать 32-битное целое число со знаком
[ редактировать ]const decodeSignedLeb128 = (input) => {
let result = 0;
let shift = 0;
while (true) {
const byte = input.shift();
result |= (byte & 0x7f) << shift;
shift += 7;
if ((0x80 & byte) === 0) {
if (shift < 32 && (byte & 0x40) !== 0) {
return result | (~0 << shift);
}
return result;
}
}
};
Использование
[ редактировать ]- Проект Android использует LEB128 в формате исполняемого файла Dalvik (.dex). [6]
- Сжатие таблиц в обработке исключений Hewlett-Packard IA-64. [7]
- Формат файла DWARF использует как беззнаковую, так и знаковую кодировку LEB128 для различных полей. [2]
- LLVM в формате отображения покрытия [8] Реализация кодирования и декодирования LEB128 в LLVM полезна наряду с приведенным выше псевдокодом. [9]
- Microsoft классах .NET Framework поддерживает формат «7-битное целое число» в BinaryReader и BinaryWriter . [10] При записи строки в BinaryWriter длина строки кодируется с помощью этого метода.
- Minecraft использует LEB128 в своем протоколе для измерения длины данных в пакетах. [11]
- Средство отладки mpatrol использует LEB128 в формате файла трассировки. [12]
- осу! использует LEB128 в своем osu! формат воспроизведения (.osr). [13]
- W3C Efficient XML Interchange (EXI) представляет целые числа без знака с использованием LEB128 точно так же, как описано здесь. [14]
- WebAssembly в переносимой двоичной кодировке модулей. [3]
- В формате файла xz [15]
Связанные кодировки
[ редактировать ]- Кодирование целых чисел переменной длины Длугоша ( оригинал ) использует кратные 7 битам для первых трех разрывов размера, но после этого приращения меняются. Он также помещает все биты префикса в начало слова, а не в начало каждого байта.
- Байты дескриптора отчета устройства пользовательского интерфейса используют битовое поле счетчика байтов длиной 2 бита для кодирования размера следующего целого числа, равного нулю, одному, двум или четырем байтам, всегда с прямым порядком байтов. Знаковое значение, т.е. следует ли расширять сокращенное целое число знаком или нет, зависит от типа дескриптора.
- Формат файла битового кода LLVM использует аналогичную технику. [16] за исключением того, что значение разбито на группы битов контекстно-зависимого размера, причем старший бит указывает на продолжение вместо фиксированных 7 бит.
- Протокол Buffers (Protobuf) использует ту же кодировку для целых чисел без знака, но кодирует целые числа со знаком, добавляя знак в качестве младшего бита первого байта.
- ASN.1 BER, DER Кодирует значения каждого типа ASN.1 в виде строки из восьмибитных октетов.
Ссылки
[ редактировать ]- ^ UNIX International (июль 1993 г.), «7.8», Спецификация формата отладочной информации DWARF, версия 2.0, черновик (PDF) , получено 19 июля 2009 г.
- ^ Jump up to: а б Группа свободных стандартов (декабрь 2005 г.). «Спецификация формата отладочной информации DWARF, версия 3.0» (PDF) . п. 70 . Проверено 19 июля 2009 г.
- ^ Jump up to: а б Группа сообщества WebAssembly (12 ноября 2020 г.). «Значения — Двоичный формат — WebAssembly 1.1» . Проверено 31 декабря 2020 г.
- ^ Плезанс, Джефф; Курц, Натан; Лемир, Дэниел (2015). «Векторизованное декодирование VByte». arXiv : 1503.07387 .
{{cite journal}}
: Для цитирования журнала требуется|journal=
( помощь ) - ^ Лемир, Дэниел; Курц, Натан; Рупп, Кристоф (февраль 1028 г.). «Stream VByte: более быстрое байт-ориентированное сжатие целых чисел». Письма об обработке информации . 130 . Первый международный симпозиум по веб-алгоритмам (опубликовано в июне 2015 г.): 1–6. arXiv : 1709.08990 . дои : 10.1016/j.ipl.2017.09.011 . S2CID 8265597 .
- ^ «Формат исполняемого файла Dalvik» . Проверено 18 мая 2021 г.
- ^ Кристоф де Динешен (октябрь 2000 г.). «Обработка исключений C++ для IA-64» . Проверено 19 июля 2009 г.
- ^ Проект ЛЛВМ (2016). «Формат отображения покрытия кода LLVM» . Проверено 20 октября 2016 г.
- ^ Проект ЛЛВМ (2019). «Кодирование и декодирование LLVM LEB128» . Проверено 2 ноября 2019 г.
- ^ Метод System.IO.BinaryWriter.Write7BitEncodedInt(int) и метод System.IO.BinaryReader.Read7BitEncodedInt() .
- ^ «Майнкрафт Модерн Варинт и Варлонг» . wiki.vg. 2020 . Проверено 29 ноября 2020 г.
- ^ «Документация MPatrol» . Декабрь 2008 года . Проверено 19 июля 2009 г.
- ^ «Osr (формат файла) — osu!wiki» . osu.ppy.sh . Проверено 18 марта 2017 г.
- ^ «Эффективный формат обмена XML (EXI) 1.0» . www.w3.org (второе изд.). Консорциум Всемирной паутины . 11 февраля 2014 г. Проверено 31 декабря 2020 г.
- ^ «Формат файла .xz» . сайт тукаани.орг . 2009 . Проверено 30 октября 2017 г.
- ^ «Формат файла битового кода LLVM — документация LLVM 13» .