Bijou64: 可変長整数エンコーディングの決定版

Bijou64は、効率的な可変長整数エンコーディングを実現するための手法です。データ圧縮や通信プロトコルの最適化において、整数値を柔軟かつ省スペースに表現したい場面で非常に役立ちます。

LEB128（正規化付き）を使い倒してきた身からすると、ほとんどのユースケースでこれの方がずっと良さそう。長さがプレフィックスとして付くし、10バイト目という余計なバイトなしでuint64の全範囲をサポートしてるし。

欠点はエンコーディングサイズだね。LEB128はすぐに2バイトになるけど、2^14まではずっと2バイトのままだ。これはmulticodec 1 プロジェクトで数字をタグや識別子として使っていたときや、ネットワークメッセージの長さなんかには重要だった。bijou64だと2バイトで収まる数字は500個しかない。

仕事でC++のライブラリを書いていて、トークンやモデルのレイヤーを介してワイヤーデータとアプリケーションデータをバインドしてる。その中にはJSON、CBOR、BSON、CSVといった色々なフォーマットのトークナイザーやコンポーザーもそこそこ含まれてるよ。

これは良さそうだけど、エンコード/デコードのパフォーマンスが重要で、ペイロードサイズが重要ではなく、整数に範囲制限があるなら、単に固定サイズの整数をそのままペイロードに詰めるな。

LEB128（JSONもそうだけど）は任意の長さの整数をエンコードできる。これはそれができないから、重要かどうかにかかわらず挙動が違うね。

正直に言うと、自分のライブラリでは暗号化関連の処理は全くしていないから、ユースケースにおいて正規表現（canonical representations）はあまり重要じゃない。無限に長いドキュメントがトークナイザーを占拠するのを防ぐために、設定可能な制限（最大値の長さ、最大深度、コレクションあたりの最大アイテム数）を提供しているだけだよ。

UTF-8にも同じ問題（いわゆる「過長符号化」）があるよね。同じコードポイントに対して複数の表現が可能なやつ。誰かが1バイトより長いバイトシーケンスのベースオフセットを調整することで、重なっている範囲を取り除く修正案を出してたよ。ここでの議論がこれ：

https://news.ycombinator.com/item?id=44456073 (https://news.ycombinator.com/item?id=44456073) - Corrected UTF-8 (2025-07-03, 54件のコメント)

この「修正版UTF-8」には別の問題もあるけど、オフセットをずらすというアイデアが他に引き継がれているのは面白いと思った。

問題は、SIMD命令を使おうとした瞬間にこれだと破綻することなんだ。数年前に整数（とieee774浮動小数点数）をエンコードする似たようなアプローチを開発したことがある（最初のバイトで長さとデータの最初のビットをエンコードする：https://github.com/kstenerud/bonjson/blob/05b91f6fe7d6b07186... ）。あれはかなり巧妙で、コンパイラの組み込み関数を使って1命令で長さを取得し、2命令で最終的な値を取得するという分岐なしの実装だった。

でもテストしてみると、SIMD命令に移るとULEB128 (https://github.com/kstenerud/bonjson/blob/main/bonjson.md#ty... ) やセンチネル値 (https://github.com/kstenerud/bonjson/blob/main/bonjson.md#lo... ) の方が、並列化のしやすさから常に勝つことが分かったんだ。

皮肉なことに、SIMDテキスト解析ですらこれより高速なんだよね。SIMDっていうのはそれくらい強力ってこと。

どこで見たか忘れたけど、長さの情報を値の一部に含めることで、同じ数字に対して複数のエンコード方法が存在する可能性を排除した似たようなエンコーディングを見たことがある。

0〜127の値は1バイトだけど、最初のバイトに継続ビット（continuation bit）が立っていれば、それが次のバイトに7ビットの続きがあることを示すだけでなく、ベースを次のウィンドウに引き上げる仕組みだった。

10000000 00000000 が128を表す唯一の方法になる。

10000000 10000000 00000000 が16512を表す唯一の方法になる。

このエンコーディングに名前ってあるのかな？

非正規（non-canonical）なエンコーディングは、可変長整数を必要とする一部のアプリケーションでは実はかなり役に立つ。DWARFもWASMもLEB128を使ってるね。

問題になるのはリンクだよ。コンパイラは独立した翻訳単位にコードを出力する必要があるんだけど、そこには他の翻訳単位のシンボルへの「未解決」な参照が含まれていて、最終的な実行ファイルのどこに配置されるかはまだ分からない。場所が分からないから、その位置を表す数字がどれだけの大きさになるかも分からず、可変長エンコーディングの幅がどれくらい必要かも分からない。もしリンク後に幅が変わってしまうと、周囲のコードを動かして広い整数用のスペースを確保しなきゃいけない。すると今度は周囲のコードの場所が変わるから、全ての参照を再計算しなきゃいけない！

解決策は、未リンクの可変長整数を常に最も広い形式（LEB128なら5バイト）で出力しておくことだ。そうすればリンク中に参照がパッチされるときにコードが動かなくて済む。これは「無駄」だけど、この問題を解決する価値あるトレードオフなんだ。リンクする必要のない他の整数は、スペースを節約するために小さい形式でパックできるしね。

これ、SQLiteのvarints 0 にかなり近いね。

GraphQL専用のバイナリフォーマット（結果としてArgoになった：https://github.com/msolomon/argo ）のために色々なvarintエンコーディングを調べたよ。結局protobuf形式のzig-zag varintを選んだんだけど、他にも興味深いものを見つけた：

vu128: https://john-millikin.com/vu128-efficient-variable-length-in...

metric/imperial varint: https://dcreager.net/2021/03/a-better-varint/

vectorizing VByte: https://arxiv.org/abs/1503.07387

これはISO 7816-4のBER-TLVエンコーディングを思い出す。ISO/IEC 8825-1（ASN.1関連の仕様）で定義された形式だね。0〜127の長さの整数値は1バイトでエンコードされる。もし上位ビットがセットされていれば、最初の7ビットが後続するオクテットの数を示す。だからオフセットの仕組みはない分、少し圧縮率は下がるけど、死ぬほどシンプルだよ。

追記：ただ、BER-TLVは過長符号化（overlong encodings）を許容してしまっている。以前Yubikey 4でこれに関連するバグを見つけて報告したことがある。その時のワークアラウンドに関するコードコメントがこれ：

  -- Yubikey 4にはオフバイワン（添字のずれ）バグがあって、
  -- 返信データに残り254バイトしかないのに、
  -- (証明書DOの0x53タグに対して) 255バイトのタグ長だと宣言してしまう。
  -- 返信は2つのパケットに分割されているけど、このずれは
  -- おそらく過長な長さエンコード (0x81 0xff ではなく 0x82 0x00 0xff)
  -- に起因するものだろう。
  --
  -- [パケットキャプチャ省略]
  --
  -- Yubicoのykpiv.cにあるykpiv_fetch_object関数は
  -- (1.4.3から1.5.0で確認)、宣言されたBER-TLVの内部長
  -- (0x53タグのもの) が実際にワイヤー越しに受け取ったものより
  -- 長いと、読み取り（memmove）オーバーフローが発生する。
  -- そのため、Yubicoのライブラリはこの問題に気づかない。
  -- 関連して、set_length関数にもオフバイワンバグがあり
  -- (length <= 0xff ではなく length < 0xff)、これが
  -- 過長な長さエンコードを生成している。ただ、これ自体は
  -- 同じコードが使われていない限り、なぜYubikey 4が
  -- 切り詰められた論理的返信を送信するのかを説明するものではない。

これが根本的に非正規性（non-canonicality）の問題を解決していない、という議論がないことに少し驚いた。

first_byte == 255 のケースで範囲チェックを忘れて64ビットのラップアラウンドを起こさせるのは、LEB128で範囲チェックを忘れるのと同じくらい「ありえる」バグだよ。正規化をカバーすることを目的としたテストスイートなら、どちらも適切にカバーできるはずだし、仕様を7単語くらい読んで「ああ、分かった」と言って実装し始めるプログラマは、どっちのバージョンでも壊れた実装を書くよ。

おそらく最大のメリットは、他の場所で非正規性を許容するフォーマットと関連付けられないことくらいかな（まあ、もしbijou64が普及すれば、ラップアラウンドのチェックがないバージョンが、それが許される場所で出現し始めるのは時間の問題だろうけど）。あとは正規化チェックを実装するのが多少楽という点かな。まあ、セキュリティが重要なソフトウェアを書いている人が「面倒だから」という理由で正確性のチェックをスキップしないことを願うよ。

ある意味、bijou64の方が問題があるかもしれない。小さい入力に対しては当然チェックが不要なので範囲チェックを書かなくなり、結果として最大長のケースを特別扱いするのを忘れる、ということが起きやすい。一方でLEB128なら、そもそもLEB128である最初の段階からそこを意識させられるからね。

（もちろん、このフォーマットには他にもメリットはあるよ。強制的な正規化というのは、その一つではないというだけでね）