Base32 の変種を作った話

Published in

shiguredo

15 min readJul 20, 2020

あまり大層な話ではないんですが、諸事情により Clockwork Base32 という Base32 の変種 (variant) を作りました。 Base32 というのは Base64 の仲間で、バイナリを 32 種類の文字で表すためのエンコード方式です。 Base32 の需要は少ないと思いますが、もし興味がある方は試してみて下さい。

今のところ、 Clockwork Base32 は弊社ではなく私個人の責任で運用しています。使用や実装にあたって弊社に問い合わせる必要はありません。私に問い合わせる必要もないので、ご自由にどうぞ。

※ 2020/8/1 追記: C と Swift の参考実装へのリンクを追加しました。

※ 2020/7/27 追記: 設計方針、デコード時のエラーケースとコーナーケースについて追記修正しました。すでに実装されている方は、実装を変更する必要はありません。

Clockwork Base32 の特徴

一言で言えば、「解釈違いを起こさない Crockford’s Base32 」です。 Crockford’s Base32 と同じ文字を使ってバイナリをテキストで表します。また、一部の仕様を削ってシンプルにしました。

仕様書はこちらです。英語で書いてありますが、だいたいこの記事で説明するので読まなくても問題ありません。

Clockwork Base32 (Gist)

たったこれだけの仕様でも、ドキュメント化に真面目に取り組むと非常に労力がかかりました。何度もレビューしてもらって曖昧な表現を直したり、表現のニュアンスに気をつけたりとまあ疲れました。でも着実にブラッシュアップできてよかったです。

参考実装

現在、次の言語で参考実装を用意しています。

これらの実装はあくまで参考であり、高パフォーマンスや継続的なメンテナンスを保証しません。使いにくいなと思ったら、すでに参考実装のある言語でもお構いなくぜひ作ってみて (広めて) 下さい。

ライセンス

上記の仕様書のライセンスは CC BY-ND 4.0 です。実装に関して何も制限はありません。権利も主張しません。好きに実装して下さい。

開発動機と Crockford’s Base32

元々の動機は、「 128 ビットのバイナリを読みやすい文字列で出力したい」でした。そこで、あるプロジェクトで使われている Base32 の変種、 Douglas Crockford さんが提案した Base32 を使うことになりました (以下 Crockford’s と略します) 。

https://www.crockford.com/base32.html

Crockford’s はエンコード後のテキストに人間が間違えにくい英数字を使うのが特徴です。アルファベットの “O” “o” は数字の “0” として扱い、同じくアルファベットの “I” “i” “L” “l” は数字の “1” として扱い、 “V” と混同しやすい “U” は使いません。

さて、そうと決まって Erlang 版を探しましたが、数少ない既存の実装は残念ながら採用できませんでした (エンコード結果が違ったりした) 。で、あまり難しくもなさそうだったので Base32 の RFC 4648 を読んで勉強しつつ Crcokford’s を実装しました。 Crcokford’s はざっくばらんな説明しかなくて戸惑いましたが、他の言語による実装やオンラインで試せるサイトを参考にしました。

ついで Go 版が必要になりましたが、こちらでも Erlang と同じ事情で既存の実装の採用を見送りました (なぜ普通に使える実装がないのだ…) 。結局 Go 版も作るかと実装を始めてみると、 Erlang では問題にならなかった処理に気がつきました。

Crockford’s のエンコードは、 5 ビット単位の内容を英数字にマッピングしたテキストを生成します。入力データが 5 ビットで割り切れなければ 0 で「 5 ビット境界」までパディングします。エンコード後のテキストをデコードすると、 5 ビット単位のビット列が再現されます。例えば長さが 3 の ASCII 文字列 (24 ビット) をエンコードすると、出力は 5 文字のシンボルのテキストになります。これをデコードすると 25 ビットです。

Go 版の API では入出力をバイト列で扱う予定だったので、 8 ビット境界からはみでる 1 ビットの扱いに悩みました。「元の入力データが 3 バイトなんだから 1 ビットはパディング！ヨシ！」とついつい捨てたくなりますが、 RFC 4648 と違って Crockford’s に「8 ビット境界」のパディングを表すシンボルはありません。ですので、 25 ビットは 25 ビットとして扱わなければならないはずです。でも Go では実用上それは厳しい。面倒くさい。なら 7 ビットをパディングしてバイト列に合わせればいい…とはなりません。それで期待したデコード結果になったとしても、仕様に書いてないのだから実装者の独自の判断となり、 Crockford’s とは言い難い実装になります。 Erlang 版で問題にならなかったのは、 Erlang は bitstring でビット列を表せるからでした。

実は Crockford’s の実装は難しい

※注：以下の内容は Crockford’s の欠点や矛盾を意味するものではありません。外野が勝手な期待を押しつけていただけです。

入出力が整数である

「そんな (バイト列に収まらない) わけあるか？」と疑問に思って仕様を読み返すと、冒頭にえらいことが書かれているのに気づきました。

Base 32 is a textual 32-symbol notation for expressing numbers in a form …

“expressing numbers” です。そう、 Crockford’s Base32 はバイト列を表す手段ではありません。「数値（整数）」を表す手段です。「バイト列の扱いについて一言も書いてない」のです。検索しても “byte” も “binary” もヒットしません。「入力の整数を 5 ビット単位のブロックに分割した整数にマッピング」し、「各ブロックをシンボルで表す」方法です。アルゴリズムの根っこは「 (入力の整数と 5 ビット単位の整数を対応させる) 整数間のマッピング」です (受け売り) 。 Crockford’s ではチェックサム 1 文字をオプションとして追加できますが、整数を相手にするからチェックサムの計算方法が「入力の整数を (32 より大きい) 素数の 37 で割る」になるのかと思われます (受け売り) 。Crockford さんは数学にめっちゃ強いようで、整数で演算する仕様は練られたもののようです。ふふっ、ごめんな。俺じゃわからんわ。

そんなわけだから (?) 、バイナリ (ビット列を含む) の入力は仕様の範疇外なのです。 5 ビット境界にするためのパディングもあくまで整数に対してであって、バイナリではありません。デコードしたデータのビット長は 5 の倍数でいいのです。とすると、「入力がバイト列」のライブラリも「デコード結果をバイト列で返す」ライブラリも、実装者が独自の判断でバイナリを扱っていることになります。仕様に従うなら入力は整数であり、実際整数であるライブラリもありましたが、整数とバイナリ間の変換を自前で実装しないといけないので見送りました。

整数のビット表現がわからない

実は私の Erlang 版の最初の実装も間違っており (ビット列で処理していた) 、指摘されて整数の演算に直しました (入力はバイナリのまま) 。しかし Go 版を実装するにあたって任意精度整数 (big integer) を使ううちに疑問が浮かびました。

「整数の 5 ビットとは何ぞや？」

仕様では 5 ビット単位の整数について言及されていますが、ビット表現については何も書かれていません。バイト列で表すのか、 32 ビット整数のシーケンスで表すのか。後者であればバイトオーダーも考えなくてはいけません。試しに Go 版 big integer のビット表現で先頭からビットをとり出してみると、なぜか期待した通りにエンコードできました。めでたしめでたしで終わっても支障ありませんが、これは Crockford’s を実装したと言えるのでしょうか。

任意精度演算が必要になる

ひとまずビット表現の疑問は置いといて、適当なテストベクタを用意してオンラインツールと比較しながら確かめていると、また一つ疑問が浮かびました。

「入力のバイナリ長が増えたら任意精度演算の計算速度が足を引っ張る可能性あるのでは？」

現実的に Base32 で大きなサイズのファイルをエンコードするケースはあまりないでしょう。しかしいつ困るとも限りません。いやまずそんな機会は来ないでしょうけど気になってしまいました。だってバイナリ長が増えるとあっという間に桁数が増大しますから。

シンボル = ASCII 文字とは限らない

重箱の隅をつつくようなものですが…シンボル (整数 5 ビットの値に対応する文字) の文字エンコーディングは定義されていません。これが気になった理由は、 Go 版を実装中に、エンコード後の値を string で返してもいいのか迷ったからです。 Base32 のエンコードに UTF-8 を使う人もいないでしょうが…

デコード側がパディング幅を知る方法がない

整数は 5 ビット単位で分割され、最後のブロックが 5 ビットに満たない場合は 0 でパディングします。前述の通りビット表現は不明ですが、そこまではいいです。

問題はデコードです。デコードした整数 (ビット列でもいいです) の最後の数ビットに 0 が並ぶ場合、果たしてその 0 はパディングと判断していいのでしょうか。パディングを “=” で表す RFC 4648 と違って Crockford’s はパディングを表すシンボルを使いません。多くのライブラリはデコード結果をバイト列で返しますが、 8 ビット境界を超えた 0 をパディングと考えて切り捨てていいのでしょうか。入力が 8 ビット境界の文字列であれば実用上問題はないでしょう。ただ、それは仕様に準拠しているとは言えないはずです。

デコード側がチェックサムの有無を知る方法がない

Crockford’s では、エンコード結果のチェックサムを表す 1 文字を任意で追加できます。「任意で」がデコード時に足枷になります。というのは、エンコード結果にチェックサムの有無を表す何かは含まれていないからです。一応判断できるとすれば、チェックサムのみ記号を含む 37 種類の文字が使われるので (human readable/pronouceable なテキストで記号を使う…？) 、記号があればチェックサムとみなして問題ないかもしれません (もちろん勝手な判断は仕様の範疇外です) 。しかし、最後の文字が手動入力による伝達ミスである可能性もあって確実ではありません。

8 ビット境界に関する仕様はない

前述の通り、デコードしたビット列の長さは 5 の倍数になります。エンコード時は 5 ビット境界になるようにパディングされますが、 8 ビット境界に関しては何も書かれていません。

例えば、あるライブラリでは「 16 バイト (128 ビット) のバイナリをエンコードしたテキストをデコードしたら 17 バイトのバイナリが返ってきた」らしいのですが、決して間違いではないんですね。 128 ビットを 5 ビットごとに分けてパディングすると、エンコードされるビット長は 130 になります。当然デコード結果は 130 ビットになりますが、デコード時はパディング幅がわからないので、仕様に従うなら勝手に 2 ビットを削ってはいけません。とすると、バイト列で返すのならば適当に 6 ビットをパディングして 134 ビット = 17 バイトで返さざるを得ません。ほとんどの実装では入力をバイト列で受け取りますから、 8 ビット境界を前提にして余りのビットを削っても実用上支障がないだけです。むしろ素直に 17 バイトを返したライブラリは正しいほうだと思います。実用上は使いにくいでしょうけれども。

テストベクタがない

仕様書にエンコードとデコードの例がありませんので、実装が正しいのか間違っているのか判断できません。オンラインで試せる実装と結果が同一であれば実用上は問題ないでしょう。仕様に準拠していると言えるのかわかりませんが。

公式の参考実装がない

テストベクタと同じで、実装が正しいのか間違っているのか判断できません。参考実装があれば、仕様に疑問があっても実装に頭を悩ますことはなかったし、既存の実装で済んだと思うのですが…。

まとめ

以上を総合して考えると、公開されている仕様のみでは「正しい実装は作れない」はずです。従って、今現在「正しい実装は存在しない」はずです。私も一つ公開していますが、理解が進んだ今となっては胸を張って実装したと言えません。現状、既存の実装はバイナリ・テキスト間変換プロトコルの常識に実装者が忖度していると言っても間違いないと思います。

変種: Clockwork Base32 を作った

そういったわけで、仕様に準拠した Crockford’s の実装は難しいと判断しました。独自の仕様をあれこれ追加して実装する方法もありましたが、仕様の範疇を超えるライブラリに Crockford’s の名を冠するのに抵抗があったので、いっそのこと RFC 4648 の知識を活かして新しい変種を作ることにしました。 Clockwork Base32 と言います。 Clockwork という名前は Crockford’s リスペクトからつけました。日本人は Lと R の区別がつかないので問題ないでしょう (？) 。

設計方針

一番の目的は、 Crockford’s 相当の結果になる実用的な仕様の定義です。その他の仕様について最初は諸々考えましたが、有益なアドバイスを受けて最終的に Crockford’s をシンプルにした仕様になりました。ただしアルゴリズムは異なります (整数の代わりにバイト列が対象だから) 。

入力はバイト列 (オクテット) 。整数より扱いやすいからです。
出力は ASCII 文字列。
パディングを表す文字を使わない。 RFC 4648 ではパディングを表す文字 (“=”) を追加しますが、デコード時にパディング幅をテキストのバイト長から計算できます。既存の Base32 はバイト列で処理する実装を想定していたのではないでしょうか。実際こんな簡単な処理でも、ビット列を扱えない言語やライブラリなしで実装するとなると結構面倒です。
誤り検出を行わない。 Crockford’s はオプションでチェックサムを追加できます。手動による入力や音声による伝達の際のケアレスミスの検出を想定していると思われますが、 Clockwork は人間による入力を考慮しません。もし誤り検出が必要ならば他の手段を併用してください。
無視可能な文字 (“-” など) を使わない。区切りが必要であれば、今時はアプリケーション側で加工すべきです。エンコード結果は単純な ASCII 文字列ですから簡単でしょう。
実装が簡単なアルゴリズムにする。開発リソース割きたくないからね。
(2020/7/27 追記) 極力エラーケースを作らない、あるいはエラー報告を必須にしない。理由は 2 つあります。実装を簡単にすることと、前述の通り誤り検出には他の手段を併用することを想定しています。「実装がガバガバになりそう」と思われるかもしれませんが、別に Clockwork Base32 だけで問題を解決しなければならないこともないと思います。

アルゴリズム

超簡単です。ビット列を手軽に扱える言語やライブラリがあれば時間はかからないでしょう。なお、エンコード・デコード共に空のバイナリは許容します。

バイト列を左から右に向かって 5 ビットごとに切り出す。最後のブロックが 5 ビットに満たなければ 0 でパディングする。
5 ビットの数値に対応する ASCII 文字を連結した文字列を作る。アルファベットは大文字を推奨します。

奇妙な偶然で、エンコード結果のテキストは既存の Crockford’s の実装とほぼ同一になります。「ほぼ」というのは、前述の通り Crockford’s のデコード結果は 5 ビット単位であり、 8 ビット境界で扱うとビット数が足りないか余るからです。

デコードはエンコードと逆の操作になります。

文字列の各文字を左から右に向かって 5 ビットに変換し、ビット列として連結する。
ビット列の長さが 8 で割り切れない場合、 8 で割った余りのビット幅を切り捨てる。

デコード時にエラーにすべきケースは次の通りです。 (※2020/7/27追記: テキスト1文字のエラー扱いは必須ではなくなりました)

無効なシンボル文字が含まれる。

(2020/7/27 追記) コーナーケースは次の通りです。

入力データが 1 文字であれば、空のシーケンスを返してもいいしエラーにしてもよい。
パディング長は 5–7 ビットでもよい。例えば入力データ 3 文字であれば 15 ビットを表す (1 文字 + 7 ビットのパディング) 。 “f” をエンコードすると “CR” だが、 “CR0” でも “f” にデコード可能。また、アルゴリズム上 8 ビット以上のパディングは存在しない。

これだけです。なぜこんな簡単な Base32 が今までなかったのか不思議ですが、 Base32 の需要がなかったんでしょうね…。

※ と思ったら近い仕様の変種を見つけました。パディングの文字 (“=”) が不要のようです。

http://philzimmermann.com/docs/human-oriented-base-32-encoding.txt

こちらは任意の長さのビット列をエンコードできるようです。ただ、デコード時にパディング幅がわからないので、元のバイナリが 1 ビットでも 5 ビットとして解釈するようです。不完全な復号化を許容するというのは個人的はどうも好きじゃないですね。他には小文字のみかな？だいぶ違った。

まとめ

Crockford’s の実装は世にそこそこあるから簡単だろうと思っていたら大事になってしまいました。皆わりかし適当だなと思って気が楽になりました。

以上です。