LEB128

редактировать

LEB128 или Little Endian Base 128 - это форма кода переменной длины сжатие, используемое для хранения произвольно большого целого числа в небольшом количестве байтов. LEB128 используется в формате файла отладки DWARF и в двоичной кодировке WebAssembly для всех целочисленных литералов.

Содержание

1 Формат кодирования
- 1.1 Без знака LEB128
- 1.2 Подписанный LEB128
2 C-подобный псевдокод
- 2.1 Кодирование целого числа без знака
- 2.2 Кодирование целого числа со знаком
- 2.3 Декодирование целого числа без знака
- 2.4 Декодирование целого числа со знаком
3 Код JavaScript
- 3.1 Кодирование 32-битное целое число со знаком
- 3.2 Декодирование 32-битного целого числа со знаком
4 Использование
5 Связанные кодировки
6 Ссылки
7 См. также

Формат кодирования

Формат LEB128 очень похож на количество переменной длины формат; основное отличие состоит в том, что LEB128 имеет прямой порядок байтов, тогда как величины переменной длины - обратный порядок байтов. Оба позволяют хранить небольшие числа в одном байте, а также позволяют кодировать произвольно длинные числа. Существует 2 версии LEB128: беззнаковый LEB128 и подписанный LEB128. Декодер должен знать, является ли закодированное значение беззнаковым LEB128 или подписанным LEB128.

Беззнаковый LEB128

Чтобы закодировать беззнаковое число с использованием беззнакового LEB128, сначала представьте число в двоичном формате. Затем ноль расширяет число до числа, кратного 7 битам (так, что если число не равно нулю, не все старшие 7 битов равны нулю). Разбейте число на группы по 7 бит. Выведите один закодированный байт для каждой группы из 7 битов, от наименее значимой до наиболее значимой. Каждый байт будет иметь группу из 7 младших битов. Устанавливает старший бит в каждом байте, кроме последнего байта. Число ноль кодируется как один байт 0x00.

В качестве примера, вот как кодируется беззнаковое число 624485:

MSB ------------------ LSB 10011000011101100101 В необработанном двоичном формате 010011000011101100101 Дополнен до числа, кратного 7 битам 0100110 0001110 1100101 Разделить на 7-битовые группы 00100110 10001110 11100101 Добавить старшие 1 биты во всех, кроме последней (наиболее значимой) группы, чтобы сформировать байты 0x26 0x8E 0xE5 В шестнадцатеричном формате → 0xE5 0x8E 0x26 в выходной поток (LS MSB)

Беззнаковый LEB128 и VLQ (количество переменной длины ) оба сжимают любое заданное целое число не только в одно и то же количество битов, но и в одни и те же биты - эти два формата отличаются только как именно эти биты расположены.

Знаковый LEB128

Знаковое число представлено аналогичным образом: Начиная с $N {\ displaystyle N}$ $N$ -бит представление с дополнением до двух, где $N {\ displaystyle N}$ $N$ кратно 7, число разбивается на группы в соответствии с кодировкой без знака.

Например, число со знаком -123456 кодируется как 0xC0 0xBB 0x78:

MSB ------------------ LSB 11110001001000000 Двоичное кодирование 123456 000011110001001000000 Как 21-битное число 111100001110110111111 Отрицание всех битов (дополнение до единицы) 111100001110111000000 Добавление единицы (дополнение до двух) 1111000 0111011 1000000 Разделение на 7-битные группы 01111000 10111011 11000000 Добавление старших 1 битов для всех, кроме последней (наиболее значимой) группы, чтобы сформировать байты 0x78 0xBB 0xC0 В шестнадцатеричном формате → 0xC0 0xBB 0x78 Выходной поток (от LSB к MSB)

Псевдокод типа C

Кодировать целое число без знака

do {byte = 7 младших битов значения; значение>>= 7; if (value! = 0) / * впереди еще байты * / устанавливает старший бит байта; испустить байт; } while (значение! = 0);

Кодировать целое число со знаком

еще = 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; / * следующее необходимо только в том случае, если реализация>>= использует логический сдвиг, а не арифметический сдвиг для левого операнда со знаком * / if (отрицательное) значение | = (~ 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; }

Декодировать целое число без знака

результат = 0; сдвиг = 0; while (истина) {байт = следующий байт на входе; результат | = (7 младших битов байта) << shift; if (high order bit of byte == 0) break; shift += 7; }

Декодировать целое число со знаком

result = 0; shift = 0; / * размер в битах переменной результата, например, 64, если тип результата - int64_t * / size = количество бит в целочисленном со знаком; do {byte = следующий байт на входе; результат | = (младшие 7 бит байта << shift); shift += 7; } while (high order bit of byte != 0); /* sign bit of byte is second high order bit (0x40) */ if ((shift Код JavaScript
Кодировать 32-битное целое число со знаком
const encodeSignedLeb128FromInt32 = (value) =>{value | = 0; const result =; while (true) {const byte = значение 0x7f; значение>>= 7; if ((значение === 0 (байт 0x40) === 0) || (значение === -1 (байт 0x40)! == 0)) {result.push (byte); return result;} result.push (byte | 0x80);}};
Декодирование 32-битного целого числа со знаком
const decodeSignedLeb128 = ( input) =>{let result = 0; пусть shift = 0; в то время как (правда) {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; } } };
Использует
В файловом формате DWARF для различных полей используется как беззнаковая, так и подписанная кодировка LEB128.
Средство отладки использует LEB128 при трассировке
В проекте Android используется LEB128 в формате файла исполняемого файла Dalvik (.dex).
Сжатие таблиц при обработке исключений Hewlett-Packard IA-64.
Он используется в ядре Linux для реализации DWARF.
Он используется в переносимом двоичном кодировании модулей WebAssembly.
Он используется в формате отображения покрытия LLVM. Реализация кодирования и декодирования LEB128 в LLVM полезна вместе с приведенным выше псевдокодом.
osu! использует LEB128 в своем osu! формат воспроизведения (.osr).
Он используется в формате файла xz.
Связанные кодировки
Формат файла битового кода LLVM использует похожую технику, за исключением того, что значение не работает на группы битов контекстно-зависимого размера, причем самый высокий бит указывает на продолжение вместо фиксированных 7 бит.
Целочисленное кодирование переменной длины Длугоша использует кратные 7 битам для первых трех разрывов размера, но после этого приращения меняются. Он также помещает все биты префикса в начало слова, а не в начало каждого байта.
Буферы протокола используют ту же кодировку для целых чисел без знака, но кодируют целые числа со знаком, добавляя знак как наименьшее значащий бит.
W3C Efficient XML Interchange (EXI) представляет целые числа без знака с использованием LEB128 точно так же, как описано здесь.
Ссылки
^ UNIX International (июль 1993). «Спецификация формата отладочной информации DWARF, версия 2.0, проект» (PDF). Проверено 19 июля 2009 г. | section =игнорируется ()
^ Free Standards Group (декабрь 2005 г.). «Спецификация формата отладочной информации DWARF, версия 3.0» (PDF). Стр. 70. Проверено 19 июля 2009 г.
^Группа сообщества WebAssembly (январь 2020 г.). «Версия 1.0 спецификации WebAssembly». Проверено 13 января 2020 г.
^«Документация MPatrol». Декабрь 2008 г. Проверено 19 июля 2009 г.
^«Исполняемый формат Dalvik». 2007 г. Проверено 19 июля 2009 г.
^Christophe de Dinechin (октябрь 2000). «Обработка исключений C ++ для IA-64». Проверено 19 июля 2009 г.
^Мэтт Флеминг (2009). «Реализация DWARF». Проверено 22 мая 2011 г.
^WebAssembly (2016). «Двоичная кодировка WebAssembly». Проверено 15 марта 2016 г.
^Проект LLVM (2016). «Формат отображения покрытия кода LLVM». Проверено 20 октября 2016 г.
^Проект LLVM (2019). «Кодирование и декодирование LLVM LEB128». Проверено 2 ноября 2019 г.
^«Osr (формат файла) - osu! Wiki ". Osu.ppy.sh. Дата обращения: 3 марта 2017 г. -18.
^«Формат файла.xz». tukaani.org. 2009. Проверено 30 октября 2017 г.
^http://llvm.org/docs/BitCodeFormat.html#variable-width-value 
^https://www.w3.org/TR/exi/#encodingUnsignedInteger 
См. Также
Формат файла отладки DWARF 
UTF-7