Jump to content

ЛЕБ128

(Перенаправлено с Little Endian Base 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 в виде строки из восьмибитных октетов.
  1. ^ UNIX International (июль 1993 г.), «7.8», Спецификация формата отладочной информации DWARF, версия 2.0, черновик (PDF) , получено 19 июля 2009 г.
  2. ^ Jump up to: а б Группа свободных стандартов (декабрь 2005 г.). «Спецификация формата отладочной информации DWARF, версия 3.0» (PDF) . п. 70 . Проверено 19 июля 2009 г.
  3. ^ Jump up to: а б Группа сообщества WebAssembly (12 ноября 2020 г.). «Значения — Двоичный формат — WebAssembly 1.1» . Проверено 31 декабря 2020 г.
  4. ^ Плезанс, Джефф; Курц, Натан; Лемир, Дэниел (2015). «Векторизованное декодирование VByte». arXiv : 1503.07387 . {{cite journal}}: Для цитирования журнала требуется |journal= ( помощь )
  5. ^ Лемир, Дэниел; Курц, Натан; Рупп, Кристоф (февраль 1028 г.). «Stream VByte: более быстрое байт-ориентированное сжатие целых чисел». Письма об обработке информации . 130 . Первый международный симпозиум по веб-алгоритмам (опубликовано в июне 2015 г.): 1–6. arXiv : 1709.08990 . дои : 10.1016/j.ipl.2017.09.011 . S2CID   8265597 .
  6. ^ «Формат исполняемого файла Dalvik» . Проверено 18 мая 2021 г.
  7. ^ Кристоф де Динешен (октябрь 2000 г.). «Обработка исключений C++ для IA-64» . Проверено 19 июля 2009 г.
  8. ^ Проект ЛЛВМ (2016). «Формат отображения покрытия кода LLVM» . Проверено 20 октября 2016 г.
  9. ^ Проект ЛЛВМ (2019). «Кодирование и декодирование LLVM LEB128» . Проверено 2 ноября 2019 г.
  10. ^ Метод System.IO.BinaryWriter.Write7BitEncodedInt(int) и метод System.IO.BinaryReader.Read7BitEncodedInt() .
  11. ^ «Майнкрафт Модерн Варинт и Варлонг» . wiki.vg. ​2020 . Проверено 29 ноября 2020 г.
  12. ^ «Документация MPatrol» . Декабрь 2008 года . Проверено 19 июля 2009 г.
  13. ^ «Osr (формат файла) — osu!wiki» . osu.ppy.sh . Проверено 18 марта 2017 г.
  14. ^ «Эффективный формат обмена XML (EXI) 1.0» . www.w3.org (второе изд.). Консорциум Всемирной паутины . 11 февраля 2014 г. Проверено 31 декабря 2020 г.
  15. ^ «Формат файла .xz» . сайт тукаани.орг . 2009 . Проверено 30 октября 2017 г.
  16. ^ «Формат файла битового кода LLVM — документация LLVM 13» .

См. также

[ редактировать ]
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: e163784350a1a780fc1d805a826b6e0e__1712751480
URL1:https://arc.ask3.ru/arc/aa/e1/0e/e163784350a1a780fc1d805a826b6e0e.html
Заголовок, (Title) документа по адресу, URL1:
LEB128 - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)