ЛЕБ128

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

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

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

Неподписанный LEB128

Чтобы закодировать беззнаковое число с помощью unsigned LEB128 ( ULEB128 ), сначала представьте число в двоичном виде. Затем увеличьте число до кратного 7 бит (так, чтобы если число не равно нулю, то 7 старших бит не были бы все 0). Разбейте число на группы по 7 бит. Выведите один закодированный байт для каждой 7-битной группы, от наименее значимой к наиболее значимой группе. Каждый байт будет иметь группу в своих 7 наименее значимых битах. Установите наиболее значимый бит в каждом байте, кроме последнего байта. Число ноль обычно кодируется как один байт 0x00. WebAssembly допускает альтернативные кодировки нуля (0x80 0x00, 0x80 0x80 0x00, ...). ^[3]

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

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

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

Подписано LEB128

Знаковое число представляется аналогичным образом: начиная с -битного представления в дополнительном коде , где — кратно 7, число разбивается на группы, как и для беззнакового кодирования. $N$ $N$

Например, знаковое число -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 Выходной поток (от младшего байта к старшему)

Быстрое декодирование

Простая скалярная реализация декодирования LEB128 довольно медленная, тем более на современном оборудовании, где неверное предсказание ветвления относительно дорого. В ряде статей представлены методы SIMD для ускорения декодирования (в этих статьях он называется VByte, но это другое название для того же кодирования). В статье «Vectorized VByte Decoding» ^[4] представлен «Masked VByte», который продемонстрировал скорость 650–2700 миллионов целых чисел в секунду на обычном оборудовании Haswell в зависимости от плотности кодирования. В последующей статье представлен вариант кодирования «Stream VByte: Faster Byte Oriented Integer Compression» ^[5] , который увеличил скорость до более чем 4 миллиардов целых чисел в секунду. Это потоковое кодирование отделяет поток управления от закодированных данных, поэтому оно несовместимо с LEB128 на двоичном уровне.

C-подобный псевдокод

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

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

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

больше = 1 ; отрицательно = ( значение < 0 );      /* размер в битах значения переменной, например, 64, если тип значения int64_t * / размер = количество бит в знаковом целом числе ;       while ( more ) { byte = младшие 7 бит значения ; value >>= 7 ; / * следующее необходимо только в том случае, если реализация >>= использует логический сдвиг ,  а не арифметический сдвиг для знакового левого операнда */ if ( negative ) value |= ( ~ 0 << ( size - 7 )); /* расширение знака */                        / * знаковый бит байта - второй старший бит (0x40) */ if (( value == 0 && знаковый бит байта очищен ) || ( value == -1 && знаковый бит байта установлен ) ) more = 0 ; else установить старший бит байта ; выдать байт ; }

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

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

Расшифровать знаковое целое число

результат = 0 ; сдвиг = 0 ;    /* размер в битах переменной результата, например, 64, если тип результата — int64_t */ размер = количество бит в знаковом целом числе ;       do { byte = следующий байт на входе ; result | = ( младшие 7 бит байта << shift ) ; shift + = 7 ; } while ( старший бит байта ! = 0 ) ;                          / * знаковый бит байта - второй старший бит (0x40) */ if (( shift < size ) && ( установлен знаковый бит байта ) ) /* расширение знака */ result |= ( ~ 0 << shift );

JavaScript-код

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

функция encodeUnSignedInt32toLeb128 ( значение ) {   var rawbine = value . toString ( 2 ); // В необработанном двоичном формате var paded = rawbine . padStart ( Math . ceil ((( rawbine . length ) / 7 )) * 7 , '0' ) // Дополняется до кратного 7 бит var splited = paded . match ( /. {1,7}/g ); // Разбивается на 7-битные группы const result = []; // Добавляет старшие 1-е биты ко всем группам, кроме последней (самой значимой), для формирования байтов var y = splited . length - 1 for ( let i = 0 ; i < splited . length ; i ++ ) { if ( i === 0 ) { var str = "0" + splited [ i ]; result [ y ] = parseInt ( str , 2 ). toString ( 16 ). padStart ( 2 , '0' ); } else { var str = "1" + разделенный [ i ]; результат [ y ] = parseInt ( str , 2 ). toString ( 16 ). PadStart ( 2 , '0' ); } y -- ; }                                                                          вернуть результат . join ( '' ); };

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

function decodeLeb128toUnSignedInt32 ( value ) { var tabvalue = value.split ( "" ); var result = " " ; const tabtemp = []; var y = tabvalue.length / 2-1 ; for ( let i = 0 ; i < tabvalue.length ; i ++ ) { if ( i % 2 != 0 ) { tabtemp [ y ] = (( parseInt ( tabvalue [ i - 1 ] , 16 ) .toString ( 2 )). padStart ( 4 , ' 0 ' ) + ( parseInt ( tabvalue [ i ], 16 ) .toString ( 2 )). padStart ( 4 , ' 0 ' ) ). slice ( 1 ) ; y -- ; } } result = parseInt ( tabtemp.join ( ' ' ) , 2 ) . toString ( 10 ) вернуть результат ; };

Кодировать знаковое 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 Executable Format (.dex). ^[6]
Сжатие таблиц в обработке исключений Hewlett-Packard IA-64. ^[7]
Формат файла DWARF использует как беззнаковую, так и знаковую кодировку LEB128 для различных полей. ^[2]
LLVM , в его формате отображения покрытия ^[8] реализация LLVM кодирования и декодирования LEB128 полезна наряду с псевдокодом выше. ^[9]
.NET поддерживает формат «7-битного кодированного целого числа» в классах BinaryReader и BinaryWriter . ^[10] При записи строки в BinaryWriter длина строки кодируется с помощью этого метода.
Minecraft использует LEB128 в своем протоколе для измерения длины данных в пакетах.^[11]
Инструмент отладки mpatrol использует LEB128 в своем формате файла трассировки. ^[12]
osu! использует LEB128 в своем формате osu! replay (.osr).^[13]
Эффективный обмен XML W3C (EXI) представляет беззнаковые целые числа с использованием LEB128, точно так же, как описано здесь. ^[14]
WebAssembly , в его переносимом двоичном кодировании модулей ^[3]
В формате файла xz ^[15]

Связанные кодировки

Кодировка целых чисел переменной длины Длугоша (оригинал) использует кратные 7 битам для первых трех разрывов размера, но после этого приращения меняются. Она также помещает все префиксные биты в начало слова, а не в начало каждого байта.
Байты дескриптора отчета устройства интерфейса человека используют битовое поле счетчика байтов из 2 бит для кодирования размера следующего целого числа из нуля, одного, двух или четырех байтов, всегда с прямым порядком байтов. Знаковость, т. е. расширять ли сокращенное целое число знаком или нет, зависит от типа дескриптора.
Формат файла битового кода LLVM использует похожую технику ^[16],за исключением того, что значение разбивается на группы битов, размер которых зависит от контекста, причем самый высокий бит указывает на продолжение, а не на фиксированные 7 бит.
Протокольные буферы (Protobuf) используют ту же кодировку для беззнаковых целых чисел, но кодируют знаковые целые числа, добавляя знак в качестве младшего бита первого байта.
ASN.1 BER, DER Кодирует значения каждого типа ASN.1 как строку восьмибитных октетов

Ссылки

↑ UNIX International (июль 1993 г.), "7.8", Спецификация формата отладочной информации DWARF версии 2.0, черновик (PDF) , получено 19 июля 2009 г.
^ ab Free Standards Group (декабрь 2005 г.). "Спецификация формата отладочной информации DWARF версии 3.0" (PDF) . стр. 70 . Получено 19 июля 2009 г. .
^ abc WebAssembly Community Group (2020-11-12). "Значения — Двоичный формат — WebAssembly 1.1" . Получено 2020-12-31 .
^ Плезанс, Джефф; Курц, Натан; Лемир, Дэниел (2015). «Векторизованное декодирование VByte». arXiv : 1503.07387 . {{cite journal}}: Цитировать журнал требует |journal=( помощь )
^ Lemire, Daniel; Kurz, Nathan; Rupp, Christoph (февраль 1028). «Stream VByte: Faster Byte-Oriented Integer Compression». Information Processing Letters . 130. First International Symposium on Web Algorithms (опубликовано в июне 2015 г.): 1–6. arXiv : 1709.08990 . doi : 10.1016/j.ipl.2017.09.011. S2CID 8265597.
^ "Формат исполняемого файла Dalvik" . Получено 2021-05-18 .
^ Кристоф де Динешен (октябрь 2000 г.). "Обработка исключений C++ для IA-64" . Получено 19 июля 2009 г.
^ Проект LLVM (2016). "Формат отображения покрытия кода LLVM" . Получено 20 октября 2016 г.
^ Проект LLVM (2019). "Кодирование и декодирование LLVM LEB128" . Получено 2019-11-02 .
^ Метод System.IO.BinaryWriter.Write7BitEncodedInt(int) и метод System.IO.BinaryReader.Read7BitEncodedInt().
^ "Minecraft Modern Varint & Varlong". wiki.vg . 2020 . Получено 29.11.2020 .
^ "Документация MPatrol". Декабрь 2008 г. Получено 19 июля 2009 г.
^ "Osr (формат файла) - osu!wiki". osu.ppy.sh . Получено 2017-03-18 .
^ "Efficient XML Interchange (EXI) Format 1.0". www.w3.org (Второе изд.). World Wide Web Consortium . 2014-02-11 . Получено 2020-12-31 .
^ "Формат файла .xz". tukaani.org . 2009 . Получено 2017-10-30 .
^ «Формат файла биткода LLVM — документация LLVM 13».