LEB128 - LEB128

LEB128 nebo Základna Little Endian 128 je forma kód s proměnnou délkou komprese použitá k uložení libovolně velkého celého čísla v malém počtu bajtů. LEB128 se používá v TRPASLÍK ladit formát souboru[1][2] a WebAssembly binární kódování pro všechny celočíselné literály.[3]

Formát kódování

Formát LEB128 je velmi podobný formátu množství proměnné délky formát; primární rozdíl je v tom, že LEB128 je malý endian, zatímco veličiny s proměnnou délkou jsou big-endian. Oba umožňují uložit malá čísla do jednoho bajtu a zároveň umožňují kódování libovolně dlouhých čísel. Existují 2 verze LEB128: nepodepsaný LEB128 a podepsaný LEB128. Dekodér musí vědět, zda je zakódovaná hodnota nepodepsaná LEB128 nebo podepsaná LEB128.

Nepodepsaný LEB128

Chcete-li zakódovat nepodepsané číslo pomocí nepodepsaného LEB128, nejprve představujte číslo v binární podobě. Pak nulové prodloužení počet až do násobku 7 bitů (takový, že pokud je číslo nenulové, nejvýznamnějších 7 bitů není všech 0). Rozdělte počet na skupiny 7 bitů. Výstup jednoho kódovaného bajtu pro každou 7bitovou skupinu, od nejméně významné po nejvýznamnější skupinu. Každý bajt bude mít skupinu ve svých 7 nejméně významných bitech. Nastavte nejvýznamnější bit na každém bajtu kromě posledního bajtu. Číslo nula je zakódováno jako jeden bajt 0x00.

Jako příklad lze uvést, jak se kóduje nepodepsané číslo 624485:

MSB ------------------ LSB 10011000011101100101 In raw binary 010011000011101100101 Padded to a multiple of 7 bits 0100110 0001110 1100101 Split into 7-bit groups00100110 10001110 11100101 Add high 1 bits on all but poslední (nejvýznamnější) skupina tvořící bajty 0x26 0x8E 0xE5 v hexadecimálním → 0xE5 0x8E 0x26 výstupní proud (LSB do MSB)

Nepodepsané LEB128 a VLQ (množství proměnné délky ) oba komprimují libovolné dané celé číslo nejen na stejný počet bitů, ale přesně na stejné bity - dva formáty se liší pouze v přesném uspořádání těchto bitů.

Podepsáno LEB128

Podepsané číslo je znázorněno podobně: Počínaje znakem -bit doplněk dvou zastoupení, kde je násobkem 7, číslo je rozděleno do skupin jako pro nepodepsané kódování.

Například podepsané číslo -123456 je zakódováno jako 0xC0 0xBB 0x78:

MSB ------------------ LSB 11110001001000000 Binární kódování 123456 000011110001001000000 Jako 21bitové číslo 111100001110110111111 Negování všech bitů (jeden doplněk) 111100001110111000000 Přidání jednoho (doplněk dvou) 1111000 0111011 1000000 Rozděleno do 7bitových skupin 01111000 10111011 11000000 Přidejte vysoké 1 bity do všech skupin kromě poslední (nejvýznamnější) a vytvořte bajty 0x78 0xBB 0xC0 v šestnáctkové soustavě → 0xC0 0xBB 0x78 Výstupní proud (LSB do MSB)

C-jako pseudokód

Zakódujte celé číslo bez znaménka

dělat {  byte = nízký objednat 7 bity z hodnota;  hodnota >>= 7;  -li (hodnota != 0) / * další bajty přijít * /    soubor vysoký objednat bit z byte;  vysílat byte;} zatímco (hodnota != 0);

Zakódujte celé číslo se znaménkem

více = 1;negativní = (hodnota < 0);/ * velikost proměnné v bitech, např. 64, pokud je typ hodnoty int64_t * /velikost = Ne. z bity v podepsaný celé číslo; zatímco (více) {  byte = nízký objednat 7 bity z hodnota;  hodnota >>= 7;  / * následující je nutné pouze v případě, že implementace >> = používá a      spíše logický posun než aritmetický posun pro podepsaný levý operand * /  -li (negativní)    hodnota |= (~0 << (velikost - 7)); / * podepsat prodloužení * /  / * bit znaménka bajtu je druhý bit vyššího řádu (0x40) * /  -li ((hodnota == 0 && podepsat bit z byte je Průhledná) || (hodnota == -1 && podepsat bit z byte je soubor))    více = 0;  jiný    soubor vysoký objednat bit z byte;  vysílat byte;}

Dekódujte celé číslo bez znaménka

výsledek = 0;posun = 0;zatímco (skutečný) {  byte = další byte v vstup;  výsledek |= (nízký objednat 7 bity z byte) << posun;  -li (vysoký objednat bit z byte == 0)    přestávka;  posun += 7;}

Dekódovat celé číslo se znaménkem

výsledek = 0;posun = 0;/ * velikost výsledné proměnné v bitech, např. 64, pokud je typ výsledku int64_t * /velikost = číslo z bity v podepsaný celé číslo;dělat {  byte = další byte v vstup;  výsledek |= (nízký objednat 7 bity z byte << posun);  posun += 7;} zatímco (vysoký objednat bit z byte != 0);/ * bit znaménka bajtu je druhý bit vyššího řádu (0x40) * /-li ((posun <velikost) && (podepsat bit z byte je soubor))  / * podepsat prodloužení * /  výsledek |= (~0 << posun);

JavaScriptový kód

Zakódujte podepsané 32bitové celé číslo

konst encodeSignedLeb128FromInt32 = (hodnota) => {  hodnota |= 0;  konst výsledek = [];  zatímco (skutečný) {    konst byte = hodnota & 0x7f;    hodnota >>= 7;    -li (      (hodnota === 0 && (byte & 0x40) === 0) ||      (hodnota === -1 && (byte & 0x40) !== 0)    ) {      výsledek.tlačit(byte);      vrátit se výsledek;    }    výsledek.tlačit(byte | 0x80);  }};

Dekódovat podepsané 32bitové celé číslo

konst decodeSignedLeb128 = (vstup) => {  nechat výsledek = 0;  nechat posun = 0;  zatímco (skutečný) {    konst byte = vstup.posun();    výsledek |= (byte & 0x7f) << posun;    posun += 7;    -li ((0x80 & byte) === 0) {      -li (posun < 32 && (byte & 0x40) !== 0) {        vrátit se výsledek | (~0 << posun);      }      vrátit se výsledek;    }  }};

Použití

  • The TRPASLÍK formát souboru používá pro různá pole nepodepsané i podepsané kódování LEB128.[2]
  • The mpatrol ladicí nástroj používá LEB128 v jeho formátu trasovacího souboru.[4]
  • The Android Projekt používá LEB128 ve formátu souboru Dalvik Executable Format (.dex).[5]
  • Komprimace tabulek při zpracování výjimek Hewlett-Packard IA-64.[6]
  • Používá se v jádře Linuxu pro implementaci DWARF.[7]
  • Používá se v WebAssembly přenosné binární kódování modulů.[8]
  • Používá se v LLVM Formát mapování pokrytí.[9] Vedle výše uvedeného pseudokódu je užitečná implementace LLVM kódování a dekódování LEB128.[10]
  • osu! používá LEB128 ve svém osu! formát přehrávání (.osr).[11]
  • Používá se ve formátu xz.[12]
  • Minecraft používá ve svém protokolu LEB128 pro zasílání délek dat v paketech.[13]

Související kódování

  • The LLVM formát souboru bitcode používá podobnou techniku[14] kromě toho, že je hodnota rozdělena do skupin bitů kontextově závislé velikosti, přičemž nejvyšší bit označuje pokračování, místo pevných 7 bitů.
  • Dlugoszovo celé číslo s proměnnou délkou používá násobky 7 bitů pro první tři přestávky velikosti, ale poté se přírůstky liší. Také umístí všechny prefixové bity na začátek slova, místo na začátek každého bajtu.
  • Vyrovnávací paměti protokolu použijte stejné kódování pro celá čísla bez znaménka, ale zakódujte celá čísla se znaménkem tak, že znaménko přepíšete jako nejméně významný bit.
  • Efektivní výměna XML W3C (EXI)[15] představuje celá čísla bez znaménka pomocí LEB128, přesně stejným způsobem, jak je popsáno zde.
  • HID bajty deskriptoru sestavy používají bitové pole pro počítání bajtů 2 bity ke kódování velikosti následujícího celého čísla o nule, jednom, dvou nebo čtyřech bajtech, vždy s malým endianem. Podepsanost, tj. Zda rozšířit zkrácené celé číslo se znaménkem, či nikoli, závisí na typu deskriptoru.

Reference

  1. ^ UNIX International (červenec 1993), "7.8", Specifikace formátu ladění informací DWARF verze 2.0, koncept (PDF), vyvoláno 2009-07-19
  2. ^ A b Skupina bezplatných standardů (prosinec 2005). „Specifikace formátu ladění informací DWARF verze 3.0“ (PDF). str. 70. Citováno 2009-07-19.
  3. ^ Komunitní skupina WebAssembly (leden 2020). „Specifikace WebAssembly Release 1.0“. Citováno 2020-01-13.
  4. ^ "Dokumentace MPatrol". Prosinec 2008. Citováno 2009-07-19.
  5. ^ "Spustitelný formát Dalvik". 2007. Citováno 2009-07-19.
  6. ^ Christophe de Dinechin (říjen 2000). "Zpracování výjimek C ++ pro IA-64". Citováno 2009-07-19.
  7. ^ Matt Fleming (2009). "Implementace DWARF". Citováno 2011-05-22.
  8. ^ WebAssembly (2016). "Binární kódování WebAssembly". Citováno 2016-03-15.
  9. ^ Projekt LLVM (2016). „Formát mapování pokrytí kódu LLVM“. Citováno 2016-10-20.
  10. ^ Projekt LLVM (2019). „LLVM LEB128 kódování a dekódování“. Citováno 2019-11-02.
  11. ^ "Osr (formát souboru) - osu! Wiki". osu.ppy.sh. Citováno 2017-03-18.
  12. ^ "Formát souboru .xz". tukaani.org. 2009. Citováno 2017-10-30.
  13. ^ "Minecraft Modern Varint & Varlong". wiki.vg. 2020. Citováno 2020-11-29.
  14. ^ http://llvm.org/docs/BitCodeFormat.html#variable-width-value
  15. ^ „Efficient XML Interchange (EXI) Format 1.0 (Second Edition)“. www.w3.org. Citováno 2020-11-01.

Viz také