Loading article…
LEB128（Little Endian Base 128）は、任意の大きさの整数を少数のバイトに格納するために使用される可変長コード圧縮です。LEB128は、 DWARFデバッグファイル形式[ 1 ] [ 2 ]およびすべての整数リテラルのWebAssemblyバイナリエンコーディング[ 3 ]で使用されています。
LEB128形式は可変長数量（VLQ）形式と非常によく似ています。主な違いは、LEB128がリトルエンディアンであるのに対し、可変長数量はビッグエンディアンである点です。どちらも、小さな数値を1バイトに格納できるだけでなく、任意の長さの数値をエンコードすることも可能です。LEB128には、符号なしLEB128と符号付きLEB128の2種類があります。デコーダは、エンコードされた値が符号なしLEB128なのか符号付きLEB128なのかを知る必要があります。
符号なし LEB128 ( ULEB128 )を使用して符号なし数をエンコードするには、まずその数をバイナリで表現します。次に、その数を 7 ビットの倍数までゼロ拡張します(つまり、その数がゼロでない場合、最上位 7 ビットがすべて 0 にならないようにします)。その数を 7 ビットのグループに分割します。最下位から最上位のグループまで、各 7 ビットのグループごとに 1 バイトのエンコードされた値を出力します。各バイトの最下位 7 ビットにグループが含まれます。最後のバイトを除く各バイトの最上位ビットを設定します。数ゼロは通常、1 バイト 0x00 としてエンコードされます。WebAssembly では、ゼロの代替エンコード (0x80 0x00、0x80 0x80 0x00、...) が可能です。[ 3 ]
例として、符号なし数624485は次のようにエンコードされます。
MSB ------------------ LSB 10011000011101100101 生のバイナリ 010011000011101100101 7ビットの倍数にパディング 0100110 0001110 1100101 7ビットグループに分割 00100110 10001110 11100101 最後の（最上位）グループを除くすべてのグループに上位1ビットを追加してバイトを形成します 16進数で0x26 0x8E 0xE5 → 0xE5 0x8E 0x26 出力ストリーム（最下位ビットから最上位ビット）
符号なしLEB128とVLQ（可変長数量）はどちらも、任意の整数を同じビット数だけでなく、まったく同じビットに圧縮します。この2つの形式の違いは、ビットの配置方法のみです。
符号付き数も同様に表現されます。-ビット2の補数表現、が 7 の倍数である場合、その数値は符号なしエンコーディングの場合と同様にグループに分割されます。
例えば、符号付き数 -123456 は 0xC0 0xBB 0x78 とエンコードされます。
MSB ------------------ LSB 11110001001000000 123456 のバイナリエンコード (符号なしから開始) 000011110001001000000 21ビットの数値として 111100001110110111111 すべてのビットを否定します（1の補数） 111100001110111000000 1を加える（2の補数） 1111000 0111011 1000000 7ビットグループに分割 01111000 10111011 11000000 最後の（最上位）グループを除くすべてのグループに上位1ビットを追加してバイトを形成します 16進数で0x78 0xBB 0xC0 → 0xC0 0xBB 0x78 出力ストリーム（最下位ビットから最上位ビット）
LEB128 復号の単純なスカラー実装はかなり遅く、分岐予測ミスが比較的コストのかかる最新のハードウェアではさらに遅くなります。一連の論文では、復号を高速化するための SIMD 技術が紹介されています (これらの論文では VByte と呼ばれていますが、同じエンコーディングの別の名前です)。「Vectorized VByte Decoding」論文[ 4 ]では、「Masked VByte」が紹介されており、エンコード密度に応じて、市販のHaswellハードウェアで毎秒 650 ～ 2700 万整数の速度が実証されています。
後続の論文では、速度を毎秒 40 億以上の整数に向上させた「Stream VByte: Faster Byte Oriented Integer Compression」[ 5 ]というバリアントエンコーディングが発表されました。このストリームエンコーディングは制御ストリームとエンコードされたデータを分離するため、LEB128 とバイナリ互換性がありません。
do { byte = value & 0x7f ; /* value の下位 7 ビット */ value >>= 7 ; if ( value != 0 ) /* さらにバイトが続く */ byte |= 0x80 ; /* byte の上位ビットを設定 */ emit ( byte ); } while ( value != 0 );more = 1 ; negative = ( value < 0 );/* 変数「value」のビット単位のサイズ。例えば、value の型が int64_t の場合は 64 */ size = sizeof ( value ) * CHAR_BITS ; /* 符号付き整数のビット数 */while ( more ) { byte = value & 0x7f ; /* value の下位 7 ビット */ value >>= 7 ; /* >>= の実装が 符号付き左オペランドに対して算術シフトではなく論理シフトを使用する場合にのみ、以下が必要です 。これは、ほとんどのプログラミング言語で、"value" が最初から符号付き型である場合は発生しません。 */ if ( negative ) value |= ( ~ 0 << ( size - 7 )); /* 符号拡張 *//* バイトの符号ビットは2番目の上位ビット (0x40) */ sign_bit = byte & 0x40 ; if (( value == 0 && sign_bit == 0 ) || ( value == -1 && sign_bit != 0 )) more = 0 ; else byte |= 0x80 ; /* バイトの上位ビットを設定 */ emit ( byte ); }result = 0 ; shift = 0 ; unsigned char byte ; do { byte = get_next_byte_in_input (); result |= ( byte & 0x7f ) << shift ; /* バイトの下位 7 ビット */ shift += 7 ; } while (( byte & 0x80 ) != 0 ); /* バイトの上位ビットを取得 */結果= 0 ;シフト= 0 ;/* 結果変数のビット単位のサイズ。例: result の型が int64_t の場合は 64 */ size = sizeof ( result ) * CHAR_BITS ; /* 符号付き整数のビット数 *//* do-whileループ内で代入されますが、その後参照されます */ unsigned char byte ;do { byte = get_next_byte_in_input (); result |= ( byte & 0x7f ) << shift ; /* バイトの下位 7 ビット */ shift += 7 ; } while (( byte & 0x80 ) != 0 ); /* バイトの上位ビットを取得 *//* バイトの符号ビットは2番目の上位ビット (0x40) */ if (( shift < size ) && (( byte & 0x40 ) != 0 )) /* 符号拡張 */ result |= ( ~ 0 << shift );const encodeSignedLeb128FromBigInt = ( value ) => { value = BigInt ( value ); const result = []; while ( true ) { const byte_ = Number ( value & 0x7fn ); value >>= 7n ; if ( ( value === 0n && ( byte_ & 0x40 ) === 0 ) || ( value === - 1n && ( byte_ & 0x40 ) !== 0 ) ) { result . push ( byte_ ); return result ; } result . push ( byte_ | 0x80 ); } };const decodeSignedBigInt = ( input ) => { let result = 0n ; let shift = 0 ; while ( true ) { const byte = input . shift (); result |= BigInt (( byte & 0x7f ) << shift ); shift += 7 ; if (( byte & 0x80 ) === 0 ) { // bigint には固定サイズがないため、「符号拡張」は適用されません// 代わりに、 BigInt.asIntN によって提供される、長さ「shift」ビットの 2 の補数として処理しますreturn BigInt . asIntN ( shift , result ); } } };