ハクソク

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

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

2026年5月30日原文(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...

Hacker Newsで議論の続きを見る