|
LEB128LEB128 or Little Endian Base 128 is a variable-length code compression used to store arbitrarily large integers in a small number of bytes. LEB128 is used in the DWARF debug file format[1][2] and the WebAssembly binary encoding for all integer literals.[3] Encoding formatLEB128 format is very similar to variable-length quantity (VLQ) format; the primary difference is that LEB128 is little-endian whereas variable-length quantities are big-endian. Both allow small numbers to be stored in a single byte, while also allowing encoding of arbitrarily long numbers. There are two versions of LEB128: unsigned LEB128 and signed LEB128. The decoder must know whether the encoded value is unsigned LEB128 or signed LEB128. Unsigned LEB128To encode an unsigned number using unsigned LEB128 (ULEB128) first represent the number in binary. Then zero extend the number up to a multiple of 7 bits (such that if the number is non-zero, the most significant 7 bits are not all 0). Break the number up into groups of 7 bits. Output one encoded byte for each 7 bit group, from least significant to most significant group. Each byte will have the group in its 7 least significant bits. Set the most significant bit on each byte except the last byte. The number zero is usually encoded as a single byte 0x00. WebAssembly allows alternate encodings of zero (0x80 0x00, 0x80 0x80 0x00, ...).[3] As an example, here is how the unsigned number 624485 gets encoded: 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)
Unsigned LEB128 and VLQ (variable-length quantity) both compress any given integer into not only the same number of bits, but exactly the same bits—the two formats differ only in exactly how those bits are arranged. Signed LEB128A signed number is represented similarly: Starting with an -bit two's complement representation, where is a multiple of 7, the number is broken into groups as for the unsigned encoding. For example, the signed number -123456 is encoded as 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)
Fast decodingA straightforward scalar implementation of LEB128 decoding is fairly slow, even more so on modern hardware where branch misprediction is relatively expensive. A series of papers presents SIMD techniques for accelerating decoding (it is called VByte in these papers, but is another name for the same encoding). The "Vectorized VByte Decoding" paper[4] presented "Masked VByte", which demonstrated speeds of 650–2700 million integers per second on commodity Haswell hardware, depending on encoding density. A followup paper presented a variant encoding, "Stream VByte: Faster Byte Oriented Integer Compression",[5] which increased speeds to over 4 billion integers per second. This stream encoding separates the control stream from the encoded data, so is not binary compatible with LEB128. C-like pseudocodeEncode unsigned integerdo {
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);
Encode signed integermore = 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;
}
Decode unsigned integerresult = 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;
}
Decode signed integerresult = 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 codeEncode Unsigned 32-bit integerfunction encodeUnSignedInt32toLeb128(value) {
var rawbine = value.toString(2); //In raw binary
var paded = rawbine.padStart(Math.ceil(((rawbine.length) / 7)) * 7, '0') //Padded to a multiple of 7 bits
var splited = paded.match(/.{1,7}/g); //Split into 7 - bit groups
const result = [];
//Add high 1 bits on all but last(most significant) group to form bytes
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" + splited[i];
result[y] = parseInt(str, 2).toString(16).padStart(2, '0');
}
y--;
}
return result.join('');
};
Decode Unsigned 32-bit integerfunction 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)
return result;
};
Encode signed 32-bit integerconst 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);
}
};
Decode signed 32-bit integerconst 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;
}
}
};
Uses
Related encodings
References
See also |
