Loading article…
可変長整数とは、バイト列を用いて整数値を可変長で符号化した表現です。必要なバイト数は表現する値によって異なり、大きな値ほど小さな値よりも多くのバイトを使用します。可変長整数には、特定のアプリケーションで制限が課されない限り、表現できる値の範囲に固有の制限はありません。このような方式は、少なくとも1983年のMIDIファイルフォーマットの仕様以来、アプリケーションで使用されています。符号付き整数と符号なし整数を表現するためのバリエーションが存在します。
可変長整数は、広範囲の整数値をサポートすることが重要であり、かつ大きな数値よりも小さな数値の方が頻繁に使用されるアプリケーションで使用されます。
このようなフォーマットにはいくつかのバリエーションが存在する。MIDIファイルフォーマットや抽象構文記法1 （ ASN.1）で使用された初期バージョンはビッグエンディアン表現を使用していた。後に開発されたリトルエンディアンのバリエーションは LEB128と呼ばれている。
ほとんどの可変長整数表現方式には、ある程度の冗長性が組み込まれているため、特定のアプリケーションでより長い表現が禁止されていない限り（例えば、特定の先頭または末尾のバイト値を禁止するなど）、必要以上に多くのバイトを使用して値を表現できます。
可変長整数をエンコードするフォーマットには、Varint、VInt、VB（可変バイト）、VByte、EncIntなど、さまざまな名前が存在します。[ 1 ]
可変長量（VLQ）は、標準MIDIファイルフォーマットで使用するために定義され、そのバージョン1.0は1983年に公開されました[ 2 ]。これは、 2001年に初めて公開された拡張音楽フォーマット（XMF）でも使用されています。
Base-128 は、タグ番号とオブジェクト識別子をエンコードするための抽象構文記法 One (ASN.1)の基本エンコード規則でも使用されています(1984 年に初めて公開されました)。[ 3 ]また、1999 年に導入された(現在は廃止された) WAP環境でも使用されており、可変長符号なし整数またはuintvarと呼ばれています。2011 年 5 月に発行された RFC 6256 では、同じ形式が定義されており、遅延耐性のあるネットワーク プロトコルで使用するための自己区切り数値( SDNV ) と呼ばれています。 [ 4 ] DWARFデバッグフォーマット[ 5 ]では、 LEB128 (符号なし数の場合はULEB128 )と呼ばれるバリアントが定義されており、7 ビットの最下位グループが最初のバイトにエンコードされ、最上位ビットが最後のバイトにエンコードされます (そのため、実質的には VLQ のリトルエンディアン版です)。Google Protocol Buffers は、整数値をコンパクトに表現するために同様の形式を使用しています[ 6 ]。Oracle Portable Object Format (POF) [ 7 ]や、Microsoft .NET Framework のBinaryReaderおよびBinaryWriterクラスの「7 ビットエンコードされた int」も同様です[ 8 ] 。
また、Webブラウザではソースマッピングにも広く使用されており、ソースマッピングには多くの整数行番号と列番号のマッピングが含まれているため、マップのサイズを最小限に抑えることができます。[ 9 ]
LLVMの可変長整数は同様の原理を使用しています。エンコードチャンクはリトルエンディアンであり、 サイズが 8 ビットである必要はありません。LLVM のドキュメントでは、4 ビットチャンクを使用するフィールドについて説明されており、各チャンクは 1 ビットの継続と 3 ビットのペイロードで構成されています。[ 10 ]
可変長整数符号化の主な利点は、そのコンパクトさと、あらゆる範囲の値に対応できる柔軟性である。
ほとんどのアプリケーションでは、非常に大きな整数よりも小さな整数の方がよく使われます。可変長整数エンコーディングでは、小さな数値ほど使用するバイト数が少なくなるため、大量の整数値をこの方法でエンコードする場合、平均して使用するバイト数が少なくなるのが一般的です。
同時に、可変長整数エンコーディングは、 8ビットバイト、16ビットワード、32ビット整数、64ビット長整数などの固定ワード長表現とは異なり、任意の大きさの整数を表現できます。可変長整数エンコーディングで表現できる値の範囲には、本質的な上限はありません。これに対し、固定長整数表現では、ワード長が短い場合は表現可能な値の範囲が不十分になるか、ワード長が長い場合は各整数を表現するために過剰なデータが必要になるのが一般的です。
可変長整数符号化は、ハフマン符号などの他のほとんどの可変長符号よりもエンコードとデコードが容易です。これは、VLQ符号がバイト単位のデータを使用するためです。より一般的な可変長符号は、エンコードとデコードに、より多くのビット指向の操作を必要とします。
このエンコーディングでは、オクテット（8ビットのバイト）を前提としており、最上位ビット（MSB）、一般に符号ビットとも呼ばれるビットは、次のVLQオクテットが続くかどうかを示すために予約されています。
Aが0の場合、これは整数の最後のVLQオクテットです。Aが1の場合、次のVLQオクテットが続きます。
Bは7ビットの数値[0x00, 0x7F]であり、nはVLQオクテットの位置を表します。B0は最下位ビットです。VLQオクテットは、ストリーム内で最上位ビットから順に並べられます。
一般的なVLQエンコーディングは単純ですが、基本形式では符号なし整数（非負、正またはゼロ）のみに定義されており、0x80オクテットを先頭に追加することはゼロパディングに相当するため、やや冗長です。負の数を扱うためのさまざまな符号付き数値表現や、冗長性を解消するための手法が存在します。
Google は、従来の VLQ エンコーディングでは解凍時に多くの CPU 分岐が発生することに着目し、グループ可変長エンコーディング (GVE) を開発しました。GVE は、4 つの可変長 uint32 値のヘッダーとして 1 バイトを使用します。ヘッダー バイトには、後続の 4 つの uint32 のそれぞれの記憶長を表す 4 つの 2 ビットの数値が含まれています。このようなレイアウトにより、VLQ 継続ビットのチェックと削除が不要になります。データ バイトは直接宛先にコピーできます。このレイアウトによりCPU 分岐が削減され、最新のパイプライン CPU では GVE が VLQ よりも高速になります。[ 11 ]
PrefixVarint は同様の設計ですが、最大値は uint64 です。これは「複数回独立して発明された」と言われています。[ 12 ]無限に続く連鎖バージョンに変更することも可能です。
負の数は符号ビットを使って処理することができ、符号ビットは最初のオクテットにのみ存在すればよい。
Unreal Engineで使用されるUnrealパッケージのデータ形式では、Compact Indices [ 13 ]と呼ばれる可変長数量スキームが使用されます。このエンコーディングの唯一の違いは、最初のVLQオクテットの7番目のビットが、エンコードされた整数が正か負かを示すために予約されていることです。連続するVLQオクテットは、一般的な構造に従います。
Sが0の場合、VLQは正の整数を表します。Sが1の場合、 VLQは負の数を表します。
Aが0の場合、これは整数の最後のVLQオクテットです。Aが1の場合、次のVLQオクテットが続きます。
Bはエンコードされる数値チャンクであり、nはVLQオクテットの位置で、B₀が最下位です。VLQオクテットはストリーム内で最下位から順に並べられます。
負の数をエンコードする別の方法として、最下位ビットを符号に使用する方法があります。これは特にGoogle Protocol Buffersで採用されており、符号付き整数のジグザグエンコードとして知られています。[ 14 ]エンコードされた0は0、1は-1、10は1、11は-2、100は2などに対応するように数値をエンコードできます。カウントアップは非負（0から始まる）と負（各ステップで最下位ビット、つまり符号が変わるため）を交互に繰り返すため、「ジグザグエンコード」という名前が付けられています。具体的には、固定kビット整数の場合と同様に整数を変換します。これにより、次の効果が得られます。(n << 1) ^ (n >> k - 1)
n << 1は と同等ですn x 2。例: 0、1、2、3 は 0、2、4、6 にマッピングされます。1xxx...ので、n >> 31すべてのビットを 1 で埋めます。2の補数で表現された負の数をすべて 1 と XOR すると、正の数になり、1 が減算されます。また、 を使って元の数を 2 倍したことを思い出してくださいn << 1。したがって、-1、-2、-3 は 1、3、5 にマッピングされます。LEB128 は、符号付き数を表現するために2 の補数を使用します。この表現方式では、nビットが -2 nから2 n - 1 まで の範囲をエンコードし、すべての負の数は最上位ビットが 1 で始まります。符号付き LEB128 では、入力は符号拡張されて長さが 7 ビットの倍数になります。そこからエンコードは通常どおりに進み ます。[ 15 ]
LEB128では、ストリームは重要度の低いものから順に並べられています。[ 15 ]
上述のVLQエンコーディングでは、Nオクテットでエンコードできる数値は、0x80オクテットをゼロパディングとして先頭に追加するだけで、Nオクテットを超える数値でもエンコードできます。例えば、10進数の358は2オクテットのVLQ 0x8266としてエンコードでき、0358は3オクテットのVLQ 0x808266としてエンコードでき、00358は4オクテットのVLQ 0x80808266としてエンコードできます。
しかし、 Git [ 16 ]で使用されている VLQ フォーマットでは、この先頭の冗長性を削除し、2 オクテット以上の VLQ にオフセットを追加することで、より短い VLQ の表現可能な範囲を拡張しています。オフセットは、( N + 1) オクテットの VLQ の最小値が、 N オクテットの VLQの最大値よりちょうど 1 大きくなるように設定されています。具体的には、1 オクテットの VLQ は最大値 127 を格納できるため、最小の 2 オクテット VLQ (0x8000) には 0 ではなく値 128 が割り当てられます。逆に、このような 2 オクテット VLQ (0xFF7F) の最大値は、16 511の代わりに16 383。同様に、最小の 3 オクテット VLQ (0x808000) の値はゼロではなく16 512なので、最大3オクテットVLQ（0xFFFF7F）は2 113 663の代わりに2 097 151。
このようにして、各整数にはただ1つのエンコードが存在し、これは128進数による全単射の記数法となる。
以下に、10進数137の計算例を示します。
別の見方としては、値を128進数で表し、最後の128進数桁を除くすべての桁の最上位ビットを1に設定するという方法があります。