ハクソク

世界を動かす技術を、日本語で。

Bijou64: 可変長整数エンコーディング

11時間前原文(inkandswitch.com)

概要

bijou64 は、 Subduction CRDT sync protocol 向けに開発された新しい可変長整数エンコーディング方式。 セキュリティ のための設計が、結果的に パフォーマンス向上 ももたらした。 従来の LEB128 と比較して、 一意的なエンコーディング と高速なデコードを実現。 署名検証やカノニカル化 が重要な用途に適した設計。 Rustライブラリ や Wasm/JavaScriptラッパー も公開中。

bijou64: セキュリティとパフォーマンスを両立する新しいvarintエンコーディング

  • bijou64 は、 Subduction CRDT sync protocol のために開発された可変長整数（varint）エンコーディング方式
  • 主な目的は、 各整数値に対して一意なバイト列のみを許容 し、署名検証時などのバグや攻撃を防止
  • LEB128 や他の一般的なvarint方式は、同じ値を複数のバイト列で表現できる問題点
    • 例: 0は0x00、0x80 0x00、0x80 0x80 0x00など、何通りも表現可能
  • bijou64 はこの問題を設計段階で排除し、 カノニカル化（canonicalisation） を追加チェックなしで保証
  • セキュリティ要件 が高いプロトコル（署名、圧縮、データ重複排除など）で有用

bijou64の設計と動作原理

  • 1バイト目の役割分担 ：0〜247はそのまま値、248〜255は「タグ」として後続バイト数を示す
    • 例: 0x42 → 0x42、0xF8以降は複数バイトモード
  • オフセット方式 ：タグ＋データバイトで値を決定、各長さごとにオフセット値を加算
    • 例: 3バイト（タグ＋2バイト）の場合、0x1F8を加算
    • 各バイト長ごとにオフセットが増加、1バイト目で即座に範囲が決まる
  • 最大値制限 ：9バイト（u64最大値超え）の場合のみ範囲チェック
  • デコード時の効率性 ：最初の1バイトで必要なバイト数が分かるため、O(1)でメモリ確保可能
  • エンコーディングの一意性 ： 全ての値が唯一のバイト列で表現 される

LEB128との比較とベンチマーク

  • デコード速度 ：bijou64はLEB128より2〜10倍高速
    • 小さい値では2倍、大きい値では8〜10倍の差
    • 4096個バッチ処理でbijou64は約3µs、LEB128は約30µs
  • カノニカルチェックのコスト ：bijou64は追加コストゼロ、LEB128は追加チェックが必要
  • エンコード速度 ：ほぼ同等だが、特定の範囲（248〜65535）ではLEB128が約1.24倍速い
  • エンコードサイズ ：ほぼ同等、配列境界付近で微差
  • CPUフレンドリー設計 ：
    • ビッグエンディアン連続バイト列 →現代CPUのバイトスワップ命令が活用可能
    • 分岐予測が容易 →パターンが安定しやすい
    • 算術演算のみで高速 →条件分岐の削減

bijou64の適用場面と注意点

  • 新規プロトコル設計 や カノニカル性が重要な用途 で特に有効
    • 署名、コンテンツアドレス、複数実装間のバイト列一致が必要な場面
  • LEB128の成熟度 には及ばず、十分な実戦テストは未了
    • 現状はApple M2 Pro、AMD Zen 5、Zen 3でベンチマーク済み
  • Rustライブラリ（crates.ioのbijou64） としてMIT/Apache-2.0で公開
    • Wasm/JavaScriptラッパー や bijou32/bijou128 等の拡張も計画
  • バグ報告や他方式との比較事例 も歓迎とのこと

まとめ：bijou64の選択基準

  • カノニカル性重視 ・ パフォーマンス重視 の用途において、bijou64は有力な選択肢
  • LEB128 は引き続き多くの用途で有効、bijou64は新規設計や要件が合致する場合に検討
  • 実装・検証・ベンチマークの継続的なフィードバック が今後の発展に重要

Hackerたちの意見

LEB128（正規化あり）をかなり使ってきたけど、これってほとんどの使い方に対してすごく見栄えがいいよね（長さプレフィックス付きで、余分な10バイトなしでuint64の範囲をサポートしてる）。欠点はエンコーディングサイズかな。LEB128はすぐに2バイトに成長するけど、2^14までずっと2バイトのまま。これは、マルチコーデック[1]プロジェクトでタグや識別子としてこれらの数字を使う場合や、ネットワークメッセージの長さにとって重要だよね。bijou64は500しかないし。

└

やあ、steb、これはexpedeの作品だよ！

仕事でC++ライブラリを作ってるんだけど、ワイヤーデータとアプリケーションデータをトークンとモデル層で結びつけてるんだ。いろんなフォーマット（JSON、CBOR、BSON、CSVなど）のトークナイザーやコンポーザーを結構含んでる。これ、見た目はいいけど、エンコーディング/デコーディングのパフォーマンスが重要で、ペイロードサイズが問題じゃないなら、固定サイズの整数をそのままペイロードに入れちゃうかな。LEB128（それにJSONも）は任意の長さの整数値をエンコードできるけど、これはそうじゃないから、重要かどうかは分からないけど、違いがあるね。正直、私のライブラリでは暗号関連の作業はしてないから、正規表現はあまり気にしてない。無限に長いドキュメントがトークナイザーを占有しないように、いろんな設定可能な制限（最大値の長さ、最大深さ、コレクションあたりの最大アイテム数）を提供してるだけなんだ。

UTF-8も同じ問題があって（「オーバーロングエンコーディング」）、同じコードポイントに対して複数の表現が可能なんだ。誰かが、1バイトより長いバイトシーケンスのベースオフセットを調整することで重複範囲を取り除くような似たような修正を提案してた。ここで話し合われてたよ: https://news.ycombinator.com/item?id=44456073 - 修正されたUTF-8（2025-07-03、54コメント）この「修正されたUTF-8」には他の問題もあるけど、シフトオフセットのアイデアがどう引き継がれるかは面白いと思った。

問題は、SIMD命令を使おうとするとこれが崩れることなんだ。数年前に整数（とIEEE754浮動小数点）をエンコードするための似たようなアプローチを開発したんだけど（最初のバイトが長さをエンコードして、データの最初のビット: 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はそれだけ強力なんだ。

└

これらは使い方が違うと思う。SIMDの話をすると、CPUや大量の整数を効率的に処理することについて語ることになるよね。こういう解決策が出てくると、ストレージや伝送の話で、均一性を犠牲にして密に詰め込むことが関係してると思う。時間系列データベースがデルタエンコーディングで数字を詰め込むのに似てる。

└

SIMDにとって特に難しいことではない気がする。特にCPUアーキテクチャに「圧縮/展開」の水平命令がある場合はね。最初のバイトは長さを完全にエンコードしていて、(U)LEB128の継続ビットより難しくないよ。基本的には、追加の引き算が加わった一般的な長さプレフィックスエンコーディングだから、誰かが効率的なアルゴリズムを見つけてるかもしれない。いくつかの他のシリアルVL（可変長）整数コーデックの選択肢よりも命令が少し多いかもしれないけど、全体的にはそんなに難しくないと思う。非常に効率的なSIMD VLコーデックは、制御ビットとデータビットを分ける傾向があるから、デザインのスペースが違うしね。

└

本当の皮肉は、SIMDのテキスト解析の方がこれを上回るってことだ！SIMDはそれだけ強力なんだ。これについて少し説明してもらえる？直感的には（だから多分間違ってるけど）これらは同じような難しさを持ってると思うんだけど。

どこで見たか忘れたけど、同じ数字に対して多くのエンコーディングの可能性を排除するような似たようなエンコーディングを見たことがあるんだ。値0-127は1バイトだけど、最初のバイトに継続ビットがセットされてると、次のバイトが7ビットを追加することを示すだけじゃなくて、ベースを次のウィンドウに移動させるんだ。10000000 00000000は128を表す唯一の方法。10000000 10000000 00000000は16512を表す唯一の方法。このエンコーディングには名前があるの？

└

UTF-8？

└

それがプロトバッファで使われているvarintエンコーディングの仕組みだと思う: https://protobuf.dev/programming-guides/encoding/#varints

└

ウィキペディアによると、gitはそういうことをするらしいよ: https://en.wikipedia.org/wiki/Variable-length_quantity#Remov...

非標準エンコーディングは、可変長整数が必要なアプリケーションには結構役立つよ。DWARFやWASMはどちらもLEB128を使ってる。問題はリンクなんだよね。コンパイラは独立した翻訳ユニットにコードを出力する必要があって、他の翻訳ユニットのシンボルへの「欠けている」参照を含むんだけど、最終的な実行可能ファイルでコードがどこに行くかまだわからないから。まだ他のコードの位置がわからないから、その位置を表す数がどれくらい大きいかもわからない。だから、その数の可変長エンコーディングがどれくらい幅を持つかもわからない。リンク後に幅が変わると、周囲のコードを押し出して広い整数のためのスペースを作らなきゃいけない。残念ながら、これが周囲のコードの位置を変えちゃうから、すべての参照を再計算しなきゃいけなくなる！解決策は、常に最も広いエンコーディング（LEB128なら5バイト）でリンクされていない可変整数を出力すること。そうすれば、リンク中に参照がパッチされるときに、コードが動かないから。すべての整数は「無駄」だけど価値のあるトレードオフで、非標準の5バイト形式に変換できる。他のリンクが必要ない整数は、スペースを節約するために小さな可変整数形式に詰め込むことができる。

└

キー/バリューのペアをストリーミングしながらmsgpackマップをエンコードするのは、よくやることだよね。

これはSQLiteのvarintsにかなり近いね。[0] [0]: https://www.sqlite.org/src4/doc/1433690d7b/www/varint.wiki

└

SQLite3は少し違う実装を使ってると思う: > 可変長整数、つまり「varint」は、64ビットの2の補数整数の静的ハフマンエンコーディングで、小さな正の値に対してはスペースを節約する。varintは1バイトから9バイトの長さになる。varintは、高ビットがセットされたバイトが0個以上続き、その後に高ビットがクリアされた単一のバイトが続くか、または9バイトのいずれか短い方で構成される。最初の8バイトの下位7ビットと9バイト目の全8ビットが64ビットの2の補数整数を再構築するために使われる。varintはビッグエンディアンで、varintの前のバイトから取ったビットが、後のバイトから取ったビットよりも重要度が高い。出典: https://www.sqlite.org/fileformat2.html#varint あなたがリンクしたSQLite4（放棄されたプロジェクト）の方が多分良いアプローチだと思う。著者がSQLite3のvarint実装は残念だと言ってたのを覚えてる。

GraphQL専用のバイナリフォーマットのために、いろんなvarintエンコーディングを調べたよ（結果的にArgoになった: https://github.com/msolomon/argo）。結局、protobufスタイルのジグザグvarintsを選んだけど、これも面白いと思った: 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はオーバーロングエンコーディングを許可してる。これに関連してYubikey 4のバグを見つけて報告したことがある。ワークアラウンドのためのソースコードコメント: -- Yubikey 4にはオフバイワンのバグがあって -- 証明書DOの0x53外部タグの -- タグ長を255と宣言するけど、実際には残りが254バイトしかない。 -- 返信は2つのパケットにまたがっているけど、オフバイワンは -- おそらくオーバーロングエンコードされた長さに -- 関係してる（0x82 0x00 0xffではなく0x81 0xff）。 -- -- [パケットキャプチャのスニップ] -- -- Yubicoのykpiv_fetch_object関数（ykpiv.c内） -- （確認済み1.4.3-1.5.0）には、宣言された内部BER-TLVの長さ -- （0x53タグの）が、受信したものよりも長い場合に -- 読み取り（memmove）オーバーフローが発生する。これがYubicoの -- ライブラリをこの問題に無頓着にしてる。関連して、 -- set_length関数にもオフバイワンのバグがある（長さ --

これについて議論がないのがちょっと驚きだな。結局、これじゃ非標準性の問題は解決しないからね。最初のバイトが255のケースで範囲チェックを忘れて、64ビットのラップアラウンドを許すのは、LEB128の範囲チェックを忘れるのと同じくらいあり得るバグだと思う。標準性をカバーすることを目的としたテストスイートなら、両方をちゃんとカバーするはずだし、7語を仕様に読み込んで「お、これでいける」と思って実装に入るプログラマーは、両方とも壊れたバージョンを書いちゃうだろうね。おそらく最大の利点は、他の場所で非標準性を許容するフォーマットと関わらないことだと思う（でも、bijou64が広まったら、ラップアラウンドチェックなしのバージョンが出てくるのは時間の問題だろうけど）。標準性チェックを実装するのが面倒じゃなくなるのもいい点かな。まあ、セキュリティに敏感なソフトウェアを書く人が、面倒だからといって正確性チェックを省略しないことを願うけどね。ある意味、bijou64はもっと問題を引き起こすかもしれない。小さい入力に対して範囲チェックをしないことを誘発するから、最大長のケースを特別扱いするのを忘れちゃうかもしれないし。LEB128は、実際にLEB128である最初のポイントで気にしなきゃいけないからね。（もちろん、このフォーマットには他にも利点があるけど、強制的な標準性はその中には含まれてないね）

└

あなたの範囲チェックの要件は、これを使う人にとって必要かどうかの多くの要素の一つに過ぎないよ。すべてを考慮に入れると（もし対立する要件があったら実現不可能かもしれないし）、解決策が不必要に複雑になっちゃう。最低限の要件に集中して、できるだけシンプルな基本設計を持つ方がいいよ。追加の要件が必要なら、デザインを複雑にしてもいいけど、その複雑さのコストを払うのは自分だけだから、意味がある時だけにしてほしいな。あなたが言ってる必要に対しては、数の単語数を指定したコンテナラッパーみたいなものが役立つかもしれない。いい点は、そういうコンテナでラップされた数を特定の状況（例えば、未処理のエリアとのデータ交換）に限定できることだね。