ЛЕБ128

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

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

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

Без знака LEB128

Чтобы закодировать беззнаковое число с помощью беззнакового LEB128 ( ULEB128 ), сначала представьте число в двоичном формате. Затем ноль расширяет число до числа, кратного 7 битам (так что, если число не равно нулю, старшие 7 бит не все равны 0). Разбейте число на группы по 7 бит. Выведите один закодированный байт для каждой 7-битной группы, от наименее значимой до наиболее значимой группы. Каждый байт будет содержать группу из 7 младших битов. Установите старший бит для каждого байта, кроме последнего. Число ноль обычно кодируется одним байтом 0x00. WebAssembly допускает альтернативные нулевые кодировки (0x80 0x00, 0x80 0x80 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

Число со знаком представляется аналогично: начиная с $N$представление дополнения до двух битов , где $N$ кратно 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». представил «Masked VByte», который продемонстрировал скорость 650–2700 миллионов целых чисел в секунду на обычном оборудовании Haswell , в зависимости от плотности кодирования. В последующем документе был представлен вариант кодировки «Stream VByte: более быстрое байт-ориентированное целочисленное сжатие». что увеличило скорость до более чем 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).
• Сжатие таблиц в обработке исключений Hewlett-Packard IA-64.
• Формат файла DWARF использует как беззнаковую, так и знаковую кодировку LEB128 для различных полей.
• LLVM в формате отображения покрытия Реализация кодирования и декодирования LEB128 в LLVM полезна наряду с приведенным выше псевдокодом.
• Microsoft классах .NET Framework поддерживает формат «7-битного целого числа» в BinaryReader и BinaryWriter . При записи строки в BinaryWriter длина строки кодируется с помощью этого метода.
• Minecraft использует LEB128 в своем протоколе для измерения длины данных в пакетах.
• Средство отладки mpatrol использует LEB128 в формате файла трассировки.
• осу! использует LEB128 в своем osu! формат воспроизведения (.osr).
• W3C Efficient XML Interchange (EXI) представляет целые числа без знака с использованием LEB128 точно так же, как описано здесь.
• WebAssembly в переносимой двоичной кодировке модулей.
• В формате файла xz

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

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

См. также

• Формат файла отладки DWARF
• UTF-7