読者です 読者をやめる 読者になる 読者になる

clock-up-blog

go-mi-tech

Ｎ進数計算およびエンコード／デコードのロジック

乱文 ちょっと長めの文章 アルゴリズム Bitcoin C#

※なんだか思ったよりも長くなってしまったので、電車の移動時間とかそういう隙間時間の時間潰しにでもご活用いただければと思います。

前書き

今更ですが情報基礎に立ち返り、進数計算について改めて書き起こしてみようと思います。

近年の情報技術はまだまだ発展途上ではありながらもその進歩は目覚ましく、進数計算程度の話であれば、そのロジックはいくらでも探せば転がっていますし、そもそもロジックを意識することなくライブラリ利用により「一般的な生産行為」は済ませられることが多く、そしてそのような選択がほとんどの場合の最適解です。

ただ、あまりにもライブラリ機能に依存するばかりにロジックの理解が疎かになる傾向が広く見られます。プログラムを日々組んでいる方であれば一度は意識したことのある世界だと思いますが、一度通過したきりで忘れがちな世界でもあります。このあたりの理解がおぼろげな方は、是非教養のひとつとして再度意識を向けてみてください。プログラミングにおける「コク」が増します。

なお、記述の厳密さについてですが、あまり文章量が増えるのも良くないので端折れるところは割り切って端折っています。進数について一度くらいはかじったことのある読者を想定しているので、分からない単語等については適宜ググる等してください。

進数を意識する意義

学術的な言葉を使うと、今回の記事では「記数法」の話をするのですが、記数法を端的に説明すると「数という概念を文字列として表現する技術」です。

コンピュータに限った話でいえば、「数」は「バイナリデータ」として保管されており、それを人間等が読める形式で表現することが、コンピュータにおける記数法の活用となります。ところでしっかりとした理解はしてもしなくても良いですが、「数は概念に過ぎない」ということを頭の片隅に置いておいてください。（バイナリもまた数の表現手段のひとつに過ぎません）

さて、今回のテーマを理解する「意義」についてですが、具体的な実用の話をすると例えば「エンコード／デコード処理」を自前で実装したり、または既存実装を読み解く際に「進数」的な発想がしばしば必要になります。

そんな処理を今更ゼロから書いたり読んだりするのはある意味馬鹿らしくもあるのですが、現実問題として「実装が存在しないから自分で実装する必要がある」とか「発明されたばかりのロジックがあり、慎重に読み解く必要がある」とか「特定の領域で高速化やメモリ節約のために再実装する必要がある」とか、そういう部類の場面に遭遇する確率はたぶん交通事故のそれよりも高いです。

筆者が最近遭遇している実例を挙げると、例えば Bitcoin というソフトウェアでは独自の Base58 というエンコーディングによりアドレス表現が行われています。（余談ですが Base58 という名前のエンコーディングには数種類の派生があり、 Base58 - Wikipedia を見る限り、今のところ Bitcoin, Ripple, Flickr でバラバラの体系の Base58 エンコーディングの存在が見受けられます）

Base58 の実装は他のメジャーなエンコーディングに比べると実装や解説の数が少ないので、ちゃんと読んでおかないと思わぬ罠があったりするし、オリジナル実装とは別に自分の好きな言語で Base58 を使いたい場合、ライブラリがあればラッキーですがライブラリがなければ自前でアレコレやる必要があります。アレコレするためには当然ロジックの「理解」が必要です。

あと、独自のエンコーディングを発明する際にも進数の理解は必要です。たとえば「任意のバイナリデータを『🍣』『🌎』『🐼』の3文字のみで表現する」のような不思議な要件があったとしても、進数の理解がキッチリと理解できていれば動揺せずに秒速で3進法に則ったロジックを思いつき、実装または適切なグーグリングおよびコピペをすることができるでしょう。

今回用いるプログラミング言語

この記事では具体例を示すためにプログラムのサンプルコードを挟みますが、今回は C# により記述することとします。今回 C# を選ぶ特別な理由は特に無く、単なる筆者の趣味に過ぎません。なので各々自分の好きな言語で読み替えてもらって構いません。

プリフィックスについて

例えば進数について明記するために「16進法における11」のような言い方をする必要がしばしば生じますが、このような表現はなかなか冗長であるため、これをもう少し短く示すために「0x11」と表記することがあります。頭に「0x」を付けることによって「16進法における」のような長い言い回しを避けているわけです。これは明確なルールではありませんが、プログラマの間で広く普及している慣習となっていますし、処理系にもよりますがコンパイラに対して進数を伝える手段としてもプリフィックスが使われます。

以下によく使われるプリフィックスの例を示します。

  • 11 … 10進法における 11 を示す (※プリフィックス無し)
  • 0d11 … 10進法における 11 を示す
  • 0b11 … 2進法における 11 を示す
  • 011 … 8進法における 11 を示す
  • 0o11 … 8進法における 11 を示す
  • 0x11 … 16進法における 11 を示す

8進法のプリフィックスが「0」となることがあり、若干の曖昧性があることに注意してください。
頭に「0」が付いていても文脈によっては8進法以外の表記の可能性はある（例えば単純に桁数を揃えるためだけに頭に「0」を付けること等がある）ので、そのあたりは適切に文脈を読み解いてください。

10進法の紹介

「1文字（1桁）で10段階の値を表記することができる」、これが10進法の特性です。
一般的にはアラビア数字の「0」「1」「2」「3」「4」「5」「6」「7」「8」「9」の文字が使われますが、これは見分けが付けば何の文字でも良いです。

日常生活で最もよく目にする記法です。

インクリメント

10進正数はインクリメント操作が行われる毎に、最下位桁の表記文字が「0」→「1」→「2」…と段階を進めていき、10段階の範囲「9」を超えた時点で、その桁の表記文字は先頭の段階「0」に戻り、副作用として桁上がりが発生し、対象桁の上位の桁の表記の段階がひとつ上がります。例えば、

  • 「28」に対してインクリメント操作を行った場合、最下位桁の表記文字は「8」から「9」へ段階を進め、全体の表記は「29」になります。
  • 「29」に対してインクリメント操作を行った場合、最下位桁の表記文字は「9」から先頭の「0」に戻り、桁上がりの効果として上位桁の「2」が「3」に上がり、全体の表記は「30」となります。
  • 「9」に対してインクリメント操作を行った場合、最下位桁の表記文字は「9」から先頭の「0」に戻り、桁上がりの効果として上位桁の暗黙の「0」が「1」に上がり、全体の表記は「10」となります。

桁の重み

一番右の桁から順に、桁の重みは 10^0、10^1、10^2、10^3、… と増えていきます。例えば、

  • 「261」は (1 * 10^0) + (6 * 10^1) + (2 * 10^2) を示します。
  • 「301」は (1 * 10^0) + (0 * 10^1) + (3 * 10^2) を示します。

桁の左シフト

任意の10進正数に10を掛けると、桁全体がひとつ左にずれます（右に空いた隙間には 0 が入る）。例えば、

  • 「1894」に10を掛けると桁が左にひとつずれて「18940」となります。
  • 「1894」に10を掛ける操作を2回繰り返せば桁は左にふたつずれて「189400」となります。

桁の右シフト

任意の10進正数を10で割る（小数点以下は切り捨て）と、桁全体がひとつ右にずれます（右に溢れた下位桁は消える）。例えば、

  • 「1894」を10で割ると、桁が右にひとつずれて「189」となります。
  • 「1894」を10で割る操作を2回繰り返せば桁は右にふたつずれて「18」となります。

最下位桁の取得

任意の10進正数を10で割った余りを求めると、その数の最下位桁の値が得られます。例えば、

  • 「1894」を10で割った余りを求めると、最下位桁である「4」が求まります。
  • 「189」を10で割った余りを求めると、最下位桁である「9」が求まります。

8進法の紹介

「1文字（1桁）で8段階の値を表記することができる」、これが8進法の特性です。
一般的にはアラビア数字の「0」「1」「2」「3」「4」「5」「6」「7」の文字が使われますが、これは見分けが付けば何の文字でも良いです。

インクリメント

8進正数はインクリメント操作が行われる毎に、最下位桁の表記文字が「0」→「1」→「2」…と段階を進めていき、8段階の範囲「7」を超えた時点で、その桁の表記文字は先頭の段階「0」に戻り、副作用として桁上がりが発生し、対象桁の上位の桁の表記の段階がひとつ上がります。例えば、

  • 「0o26」に対してインクリメント操作を行った場合、最下位桁の表記文字は「6」から「7」へ段階を進め、全体の表記は「0o27」になります。
  • 「0o27」に対してインクリメント操作を行った場合、最下位桁の表記文字は「7」から先頭の「0」に戻り、桁上がりの効果として上位桁の「2」が「3」に上がり、全体の表記は「0o30」となります。
  • 「0o7」に対してインクリメント操作を行った場合、最下位桁の表記文字は「7」から先頭の「0」に戻り、桁上がりの効果として上位桁の暗黙の「0」が「1」に上がり、全体の表記は「0o10」となります。

桁の重み

一番右の桁から順に、桁の重みは 8^0、8^1、8^2、8^3、… と増えていきます。例えば、

  • 「0o261」の実際の値は (1 * 8^0) + (6 * 8^1) + (2 * 8^2) = 177 となります。
  • 「0o301」の実際の値は (1 * 8^0) + (0 * 8^1) + (3 * 8^2) = 193 となります。

桁の左シフト

任意の8進正数に8を掛けると、桁全体がひとつ左にずれます（右に空いた隙間には 0 が入る）。例えば、

  • 「0o2614」に8を掛けると桁が左にひとつずれて「0o26140」となります。
  • 「0o2614」に8を掛ける操作を2回繰り返せば桁は左にふたつずれて「0o261400」となります。

桁の右シフト

任意の8進正数を8で割る（小数点以下は切り捨て）と、桁全体がひとつ右にずれます（右に溢れた下位桁は消える）。例えば、

  • 「0o2614」を8で割ると、桁が右にひとつずれて「0o261」となります。
  • 「0o2614」を8で割る操作を2回繰り返せば桁は右にふたつずれて「0o26」となります。

最下位桁の取得

任意の8進正数を8で割った余りを求めると、その数の最下位桁の値が得られます。例えば、

  • 「0o2614」を8で割った余りを求めると、最下位桁である「4」が求まります。
  • 「0o261」を8で割った余りを求めると、最下位桁である「1」が求まります。

8進表記の文字列生成（エンコード）

上で紹介した8進数の性質を利用して、8進表記の文字列を作り出してみます。

int num = 100; // 10進でいうところの100
string str = ""; // ここに8進表記の文字列を構築する
while (num != 0)
{
    int k = num % 8; // 8進における最下位桁を取得
    str = k + str; // 取得した桁の値を文字列の左側に追加していく
    num /= 8; // 8進における桁を右にひとつずらす
}
Console.WriteLine("0o" + str); // "0o144" という結果が得られる

8進表記の文字列を解釈する（デコード）

上で紹介した8進数の性質を利用して、8進表記の文字列を数値として読み取ります。

string str = "144"; // 8進で表記された "144"
int num = 0; // ここに読み取った値を構築する
for(int i = 0; i < str.Length; i++)
{
    num *= 8; // 桁の重みを付けていく
    num += (str[i] - '0'); // 1文字ずつ 0～7 の値として読み取っていく
}
Console.WriteLine(num); // 100 という結果が得られる

エンコード／デコードのロジックの香り

ソラで書ける必要はそれほどありませんが、形を軽く覚えておくと、似た形のコードを見たときに「これは進数のエンコード／デコード的な処理をしているのだな」みたいなアタリを付けることができます。

特定の数値（これが基数となる）で割ったり割った余りを求めたり掛けたりしているコードの「香り」を感じ取ってみてください。

m = n % 8; // 8進の世界で最下位桁を取得している
m = n / 8; // 8進の世界で右シフトを行っている
m = n * 8; // 8進の世界で左シフトを行っている

// 基数が 2 のべき乗になっている場合はビット演算もしばしば用いられる
m = n & 7; // n % 8 と同じ効果
m = n >> 3; // n / 8 と同じ効果
m = n << 3; // n * 8 と同じ効果

特に低レイヤー層を触る機会の多いエンジニアほどこのあたりの感覚が活きることが多いでしょう。

文字テーブルの利用

8進数のサンプルコードではしれっと「0」～「7」の文字と数値の変換処理を計算でやってしまいましたが、実際のところ10進数を超える体系では半角アラビア数字だけでは文字種が足りないので桁の表記に英字等を取り入れていきます。

例えば16進数では1桁で16段階の値を表現する必要あるので、16種類の文字が必要であり、一般的には「0」「1」「2」「3」「4」「5」「6」「7」「8」「9」「A」「B」「C」「D」「E」「F」の文字が使われます（英字部分は小文字大文字どっちでも良い）。

文字種が半角アラビア数字だけであれば文字コードが連続しているので単純な計算一発で数値←→文字の変換処理が行えますが、英字等の文字種が加わってくると文字コードが連続しなくなるので変換に一工夫が必要になります。

手法としては、条件分岐による計算、または文字テーブルの利用、等がありますが、リソース効率を気にしないのであれば文字テーブルを利用するのが分かりやすいしメンテナンスもしやすいです。

以下に文字テーブルを利用した16進数のエンコード／デコードのサンプルコードを示します。

// 文字テーブル (ここで文字種を定義する)
string table = "0123456789ABCDEF";

// 16進エンコード
{
    int num = 200; // 10進でいうところの200
    string str = ""; // ここに16進表記の文字列を構築する
    while (num != 0)
    {
        int k = num % 16; // 16進における最下位桁を取得 (0～15)
        char c = table[k]; // 取得した値 (0～15) に対応する文字 ('0'～'9' or 'A'～'F')
        str = c + str; // 取得した文字 ('0'～'9' or 'A'～'F') を、文字列の左側に追加していく
        num /= 16; // 16進における桁を右にひとつずらす
    }
    Console.WriteLine("0x" + str); // "0xC8" という結果が得られる
}

// 16進デコード (※逆引きテーブルを作るとより高速になるが今回は省略する)
{
    string str = "C8"; // 16進で表記された "C8"
    int num = 0; // ここに読み取った値を構築する
    for (int i = 0; i < str.Length; i++)
    {
        num *= 16; // 桁の重みを付けていく
        char c = str[i]; // 1文字ずつ読み取っていく ('0'～'9' or 'A'～'F')
        int k = table.IndexOf(c); // 文字 ('0'～'9' or 'A'～'F') に対応した数値 (0～15) に変換
        num += k; // 取得した数値 (0～15) を加算していく
    }
    Console.WriteLine(num); // 200 という結果が得られる
}

文字テーブルの仕組みを導入することで文字種の定義に自由度が生まれました。

今回は「table = "0123456789ABCDEF"」としていますが、ここを例えば「table = "〇一二三四五六七八九ＡＢＣＤＥＦ"」のようなふざけた定義にしてもプログラムは動作します。

Ｎ進数の特性およびエンコード／デコードのロジック

ここまでに10進数、8進数、16進数を紹介しましたが、ここまで来るとＮ進数の抽象的な特性（共通項的な特性）が見えてくるでしょう。

「1文字（1桁）でＮ段階の値を表記することができる」、これがＮ進法の特性です。
一般的にはアラビア数字および英字が使われますが、これは見分けが付けば何の文字でも良いです。

今回は説明の便宜上、先頭10段階までの文字はアラビア数字を用いることとします。

インクリメント

Ｎ進正数はインクリメント操作が行われる毎に、最下位桁の表記文字が「0」→「1」→「2」…と段階を進めていき、Ｎ段階の範囲を超えた時点で、その桁の表記文字は先頭の段階「0」に戻り、副作用として桁上がりが発生し、対象桁の上位の桁の表記の段階がひとつ上がります。

桁の重み

一番右の桁から順に、桁の重みは N^0、N^1、N^2、N^3、… と増えていきます。例えば、

  • 「261」の実際の値は (1 * N^0) + (6 * N^1) + (2 * N^2) となります。
  • 「301」の実際の値は (1 * N^0) + (0 * N^1) + (3 * N^2) となります。

桁の左シフト

任意のN進正数にNを掛けると、桁全体がひとつ左にずれます（右に空いた隙間には 0 が入る）。

桁の右シフト

任意のN進正数をNで割る（小数点以下は切り捨て）と、桁全体がひとつ右にずれます（右に溢れた下位桁は消える）。

最下位桁の取得

任意のN進正数をNで割った余りを求めると、その数の最下位桁の値が得られます。

エンコード／デコード

汎用的にＮ進数をエンコード／デコードするコードを以下に示します。
今回は定数「N」を暫定で 20 にすることで20進数の処理を行っていますが、この定数値を変更すれば任意の進数の計算ができます。

// 基数 (今回は20進数を処理してみる)
const int N = 20;

// 文字テーブル
// 今回は36種の文字を用意しておくことで36進数まで対応
string table = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";

// Ｎ進エンコード
{
    int num = 119; // 10進でいうところの119
    string str = ""; // ここにＮ進表記の文字列を構築する
    while (num != 0)
    {
        int k = num % N; // Ｎ進における最下位桁を取得 (0～N-1)
        char c = table[k]; // 取得した値 (0～N-1) に対応する文字
        str = c + str; // 取得した文字を、文字列の左側に追加していく
        num /= N; // Ｎ進における桁を右にひとつずらす
    }
    Console.WriteLine(str); // "5J" という結果が得られる
}

// Ｎ進デコード
{
    string str = "5J"; // Ｎ進で表記された "5J"
    int num = 0; // ここに読み取った値を構築する
    for (int i = 0; i < str.Length; i++)
    {
        num *= N; // 桁の重みを付けていく
        char c = str[i]; // 1文字ずつ読み取っていく
        int k = table.IndexOf(c); // 文字に対応した数値 (0～N-1) に変換
        num += k; // 取得した数値 (0～N-1) を加算していく
    }
    Console.WriteLine(num); // 119 という結果が得られる
}

バイト列の扱い

ここまでは数値、すなわち int 型に収まりそうな値に対して変換処理を行ってきましたが、同じ操作をバイト列に対して行う必要もしばしばあります。バイト列とは例えば「byte data = { 60, 20, 100, 8, 190, 1, 5, 150, 9, 1, 2, 3 };」のようなバイト値の集合です。ファイルシステム上のファイル内容等はバイト列として保管されていると考えて良いでしょう。

「byte data = { 60, 20, 100, 8, 190, 1, 5, 150, 9, 1, 2, 3 };」を進数表示する方法についてですが、実用性はさておき最も簡単な処理方法は「バイト列全体をひとつの数値としてみなす」です。

以下に例を示します。

// このバイナリ列をビッグエンディアンな数値として解釈したいが、
byte[] data = { 60, 20, 100, 8, 190, 1, 5, 150, 9, 1, 2, 59 };

// BigInteger のコンストラクタはリトルエンディアンなバイト列を受け取るので反転させる
byte[] rdata = data.Reverse().ToArray();

// BigInteger に変換して数値として解釈
BigInteger num = new BigInteger(rdata);

// 18593751503586466745316082235 という数値が得られる
Console.WriteLine(num);

// 数値なので普通にエンコードできる (ここは16進)
{
    BigInteger tmp = num;
    string table = "0123456789ABCDEF";
    string str = ""; // ここに16進表記の文字列を構築する
    while (tmp != 0)
    {
        int k = (int)(tmp % 16); // 16進における最下位桁を取得 (0～15)
        char c = table[k]; // 取得した値 (0～15) に対応する文字
        str = c + str; // 取得した文字を、文字列の左側に追加していく
        tmp /= 16; // 16進における桁を右にひとつずらす
    }
    Console.WriteLine("0x" + str); // "0x3C146408BE0105960901023B" という結果が得られる
}

// 数値なので普通にエンコードできる (ここは64進)
{
    BigInteger tmp = num;
    string table = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
    string str = ""; // ここに64進表記の文字列を構築する
    while (tmp != 0)
    {
        int k = (int)(tmp % 64); // 64進における最下位桁を取得 (0～63)
        char c = table[k]; // 取得した値 (0～63) に対応する文字
        str = c + str; // 取得した文字を、文字列の左側に追加していく
        tmp /= 64; // 64進における桁を右にひとつずらす
    }
    Console.WriteLine(str); // "PBRkCL4BBZYJAQI7" という結果が得られる
}

ちゃんと効率的な処理をするのであればしっかりとループを回してバイト列を処理するのが正当なのですが、バイト列全体を数値として解釈すると、さきほど示した数値の進数変換と同じロジックがそのまま適用できるのです。今回は16進と64進の変換を行っています。

さて今回のサンプルコードにはちょっとしたエッセンスを混ぜ込んでいまして、実のところ今回のバイト列→数値→64進エンコードした結果は Base64 エンコードした結果と等しいです。正確な説明ではありませんが Base64 エンコーディングとはデータを64進表記することと言えます。（後ほどもっと正確な Base64 の規格についても紹介します）

64進数表記のインクリメント

数値をインクリメントしていったときに64進表記がどのように変化していくか確認してみましょう。

さきほど用いた数値 18593751503586466745316082235 を引用し、数値をインクリメントさせながら64進表記の変化を見てみます。

// さきほどの64進表記生成処理を関数化したもの
static string BigIntegerTo64basedString(BigInteger num)
{
    string table = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
    string str = ""; // ここに64進表記の文字列を構築する
    while (num != 0)
    {
        int k = (int)(num % 64); // 64進における最下位桁を取得 (0～63)
        char c = table[k]; // 取得した値 (0～63) に対応する文字
        str = c + str; // 取得した文字を、文字列の左側に追加していく
        num /= 64; // 64進における桁を右にひとつずらす
    }
    return str;
}

// さきほど用いた数値をインクリメントしたときの64進表記の変化を見る
static void Main(string[] args)
{
    BigInteger num = BigInteger.Parse("18593751503586466745316082235");
    for(int i = 0; i < 7; i++)
    {
        // 64進表記
        string str = BigIntegerTo64basedString(num);

        // 本物の Base64 表記
        string realBase64 = Convert.ToBase64String(num.ToByteArray().Reverse().ToArray());

        // 表示
        Console.WriteLine(num + " -> " + str + " (RealBase64:" + realBase64 + ")");

        // インクリメント
        num++;
    }
}

さきほど、64進数変換の結果と Base64 エンコーディングの結果が同一になると書きましたが、信じられない人のために本物の Base64 エンコーディング処理（Convert.ToBase64String）も確認用に挟みました。

実行結果は以下の通りです。

18593751503586466745316082235 -> PBRkCL4BBZYJAQI7 (RealBase64:PBRkCL4BBZYJAQI7)
18593751503586466745316082236 -> PBRkCL4BBZYJAQI8 (RealBase64:PBRkCL4BBZYJAQI8)
18593751503586466745316082237 -> PBRkCL4BBZYJAQI9 (RealBase64:PBRkCL4BBZYJAQI9)
18593751503586466745316082238 -> PBRkCL4BBZYJAQI+ (RealBase64:PBRkCL4BBZYJAQI+)
18593751503586466745316082239 -> PBRkCL4BBZYJAQI/ (RealBase64:PBRkCL4BBZYJAQI/)
18593751503586466745316082240 -> PBRkCL4BBZYJAQJA (RealBase64:PBRkCL4BBZYJAQJA)
18593751503586466745316082241 -> PBRkCL4BBZYJAQJB (RealBase64:PBRkCL4BBZYJAQJB)

最下位の桁が「7」「8」「9」「+」「/」と段階を進めていき、64段階の範囲「/」を超えた時点で、その桁の表記文字は先頭の「A」に戻り、副作用として桁上がりが発生し、対象桁の上位の桁が「I」から「J」に進んだことが確認できます。

これは一般的なＮ進数の特性であり、なおかつ、正確な Base64 エンコーディング表現とも一致します。

Base64 エンコーディングが一種の64進数的なものであることが分かるかと思います。

本物の Base64 エンコーディング

上述のように Base64 エンコーディングは64進数的な性質を持っていることは確かなのですが、実際のところ Base64 は大きなバイナリデータを文字列表現するために作られた規格であり、さきほどのようにバイト列全体を一旦数値に変換して進数計算をするような手法は不経済的ですし、実はバイト列の長さが3の倍数になっていないと上述のようなピッタリの64進表現にはなりません。

Base64 を定義する規格には派生がいくつかあるのですが、GNU coreutils (最新版) の base64 コマンド が RFC 4648 を採用している点を考えると、そのあたりの RFC を見ておくのが良いかと思います。

具体的にはバイト列を 6bits の単位で分割していき、その単位ひとつひとつを1文字に変換します。
これは言い換えると 3bytes (24bits) を 6bits x 4 に分割し、それを4文字で表すことになります。

データ長さが 3bytes の倍数だとピッタリ変換ができるのですが、余りが出た場合には、エンコード結果の文字列長が4の倍数になるように、残りを「=」で埋めます。

以下に本来の規格に沿った Base64 の変換コードを載せます。

// バイト列を Base64 エンコードする
static string base64encode(byte[] data)
{
    // 文字テーブル
    string table = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";

    // result
    string result = "";

    // 3bytes ずつ処理を行う
    for (int i = 0; i < data.Length; i += 3)
    {
        // 3bytes (24bits) 分のデータをひとつの int n にまとめる
        int n = ((int)data[i]) << 16;
        if (i + 1 < data.Length) n |= (((int)data[i + 1]) << 8);
        if (i + 2 < data.Length) n |= (((int)data[i + 2]) << 0);

        // 24bits を 6bits x 4 に分割。
        byte n0 = (byte)((n >> 18) & 0x3F);
        byte n1 = (byte)((n >> 12) & 0x3F);
        byte n2 = (byte)((n >> 6) & 0x3F);
        byte n3 = (byte)((n >> 0) & 0x3F);

        // 文字の追加
        result += table[n0]; // 必ずある
        result += table[n1]; // 必ずある (ただしビットが欠けることもある)
        if (i + 1 < data.Length) result += table[n2]; else result += '='; // 無い場合は '='
        if (i + 2 < data.Length) result += table[n3]; else result += '='; // 無い場合は '='
    }

    // 結果
    return result;
}

// Base64 文字列をデコードする
static byte[] base64decode(string str)
{
    // 文字テーブル
    string table = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/=";

    // ここに結果を詰めていく
    List<byte> result = new List<byte>();

    // 空白等取り除き
    str = Regex.Replace(str, "[ \t\r\n]", "");

    // 4文字ずつ処理
    for (int i = 0; i < str.Length; i += 4)
    {
        // 有効なバイト数
        int bytes = 0;

        // 4つの文字に対応する値 (6bits値) を取得
        int c0 = table.IndexOf(str[i + 0]); bytes++;
        int c1 = table.IndexOf(str[i + 1]);
        int c2 = table.IndexOf(str[i + 2]); if (c2 == 64) c2 = 0; else bytes++;
        int c3 = table.IndexOf(str[i + 3]); if (c3 == 64) c3 = 0; else bytes++;

        // 6bits x 4 の値を結合して 3bytes 値を作る
        int n = (c0 << 18) | (c1 << 12) | (c2 << 6) | (c3 << 0);

        // バイト列にデータ追加
        if (bytes >= 1) result.Add((byte)((n >> 16) & 0xFF));
        if (bytes >= 2) result.Add((byte)((n >> 8) & 0xFF));
        if (bytes >= 3) result.Add((byte)((n >> 0) & 0xFF));
    }

    // 結果
    return result.ToArray();
}

// Base64 エンコード／デコード呼び出し
static void Main(string[] args)
{
    // 元データ
    byte[] data = new byte[] { 0, 0, 1, 0, 100, 200, 255, 51 };
    Console.WriteLine("-- Data --");
    Console.WriteLine("{" + string.Join(", ", data) + "}");

    // 自作関数による Base64 エンコード／デコード
    {
        Console.WriteLine("\n-- User-defined Base64 --");

        // Base64 エンコード
        string encoded = base64encode(data);
        Console.WriteLine(encoded);

        // Base64 デコード
        byte[] decoded = base64decode(encoded);
        Console.WriteLine("{" + string.Join(", ", decoded) + "}");
    }

    // .NET による Base64 エンコード／デコード (確認用)
    {
        Console.WriteLine("\n-- .NET Base64 --");

        // Base64 エンコード
        string encoded = Convert.ToBase64String(data);
        Console.WriteLine(encoded);

        // Base64 デコード
        byte[] decoded = Convert.FromBase64String(encoded);
        Console.WriteLine("{" + string.Join(", ", decoded) + "}");
    }
}


実行結果

-- Data --
{0, 0, 1, 0, 100, 200, 255, 51}

-- User-defined Base64 --
AAABAGTI/zM=
{0, 0, 1, 0, 100, 200, 255, 51}

-- .NET Base64 --
AAABAGTI/zM=
{0, 0, 1, 0, 100, 200, 255, 51}

自作関数による Base64 エンコード／デコードの結果が .NET による結果と変わらないことが確認できます。（ちなみにエラー処理は入れてないので変な文字列を入れるとバグります）

Base{N} エンコーディングについて

Base{N} という名前の付いたエンコーディング規格については、おそらく Base64 が最も有名かと思いますが、他にも Base16, Base32, Base58 等等等（いろいろあるので全部は挙げない）あります。基本的には Base64 の性質と同じく、Base{N} エンコーディングはＮ進数のような性質を持っていると考えれば良いです。

Base58 エンコーディング

Base{N} エンコーディングの中でも筆者が最近個人的に注目しているエンコーディングとして Base58 があります。

記事冒頭付近でも述べましたが、Base58 は主に Bitcoin, Ripple, Flickr で利用されているエンコーディングです。Base58 という同じ名前を使いながらもそれぞれのプラットフォームで別体系のエンコーディングが実装されていることに注意してください（58進数的な性質は同じだが、使われている文字テーブルが異なる）。今回は Bitcoin における Base58 エンコーディングを紹介します。

Base58 の性質

Base58 という名前の通り、58進数的な性質を持っています。
桁表示に用いられる文字は 123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz の58種です。

Base64 との性能差はそれほどありませんが、文字種として人間が読み間違えやすい「0(ゼロ)」「I(大文字アイ)」「O(大文字オー)」「l(小文字エル)」および記号が除外されています。結果として「見間違えにくい」かつ、記号が無いので「多くの環境でダブルクリック一発で文字列全体が選択できる」などの利点があります。

Bitcoin における Base58 実装

上記コード base58.cpp 内の「EncodeBase58()」「DecodeBase58()」が Bitcoin における Base58 エンコード／デコードの実装です。グローバルスコープに「pszBase58 = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz";」として文字テーブルが定義されています。

C# による Base58 実装例

細かい Base58 仕様は Bitcoin のソースコードそのものを見れば分かるものとして、これを C# に移植してみます。

// バイト列を Base58 エンコードする
static string base58encode(byte[] data)
{
    const string table = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz";

    // 先頭ゼロスキップ (スキップしたバイト数分だけ先頭を '1' で埋める準備)
    int idata = 0;
    string head = "";
    while (idata < data.Length && data[idata] == 0)
    {
        idata++;
        head += '1';
    }

    // バイト列をビッグエンディアンの数値として解釈する
    List<byte> listData = data.ToList();
    listData.Insert(0, 0);
    listData.Reverse();
    BigInteger num = new BigInteger(listData.ToArray());

    // 数値なので普通にエンコードできる (58進数)
    string result = "";
    {
        BigInteger tmp = num;
        while (tmp != 0)
        {
            BigInteger k = tmp % 58; // 58進数における最下位桁を取得 (0～57)
            char c = table[(int)k]; // 取得した値 (0～57) に対応する文字
            result = c + result; // 取得した文字を、文字列の左側に追加していく
            tmp /= 58; // 58進における桁を右にひとつずらす
        }
        if (result.Length == 0) result = table[0].ToString();
    }

    // バイト列先頭のゼロ個数分だけ '1' を先頭に詰める
    result = head + result;

    // 結果
    return result;
}

// Base58 文字列をデコードする
static byte[] base58decode(string str)
{
    const string table = "123456789ABCDEFGHJKLMNPQRSTUVWXYZabcdefghijkmnopqrstuvwxyz";

    // 前後空白除去
    str = str.Trim();

    // ここに結果を詰めていく
    List<byte> result = new List<byte>();

    // 先頭の '1' の個数分だけバイト列先頭にゼロを詰める
    int istr = 0;
    while(istr < str.Length && str[istr] == '1')
    {
        istr++;
        result.Add(0);
    }

    // 残りの文字列を58進デコードにより数値に変換
    BigInteger num = 0;
    for (; istr < str.Length; istr++)
    {
        num *= 58; // 桁の重みを付けていく
        char c = str[istr]; // 1文字読み取り
        int k = table.IndexOf(c); // 文字に対応した数値 (0～57) に変換
        if (k < 0) return null; // error
        num += k; // 取得した数値 (0～57) を加算していく
    }

    // ビッグエンディアンのバイト列として追加
    result.AddRange(num.ToByteArray().Reverse());

    // 結果
    return result.ToArray();
}

細かい解説は省きますが、ほとんどシンプルに58進数計算をするだけでエンコード／デコードが実現できました。（効率は一旦無視）

Bitcoin のソースコード上から Base58 を読み解く上での注意

Bitcoin は2009年1月にソースコードが公開されて以来、何人もの人間によっていくつもの実装が追加されており、これはオープンソースソフトウェアの宿命ではあるのですが、機能のカプセル化の程度にバラツキがあります。

Base58 エンコーディングについて理解しようとする際には特に CBase58Data 等のクラスに紛らわされないでください。このクラスはバージョン情報等のメンバ変数を持っていますが、これは Base58 エンコーディングの本質ではありません。あくまでも Base58 はバイナリを文字列表現するためのエンコーディング手段に過ぎず、そのロジックは「EncodeBase58()」「DecodeBase58()」の2関数に集約されています。

おわりに：理解の濃度調整

この文章はできる限りではありますが、一通り読むと「なんだかいろんな具体例が見えて質感を感じ取れる」ように考えて書きました。

そもそもこの長文をここまで読み切れる人間はかなり良い意味でヤバいと思うのですが、質感といった気分ではなく本当の意味でアルゴリズムの理解をしたい人は自分の頭で考えながら写経でも良いので自分でコードを書いて実行してみることをお勧めします。ブレークポイントを張り、ひとつひとつステップ実行しながらアルゴリズムの流れを状態変化と併せて見ると理解が捗るかと思います。

参考

});