【C#】Base32エンコード/デコード実装してみた

# Base64
よく、文字列やバイト列の圧縮で用いられるBase64。
C# であれば ` System` 空間の `Convert `クラスにてBase64 エンコード/デコードのメソッドが提供されています。
[MSドキュメント(エンコード)](https://docs.microsoft.com/ja-jp/dotnet/api/system.convert.tobase64string?view=netframework-4.8)
[MSドキュメント(デコード)](https://docs.microsoft.com/ja-jp/dotnet/api/system.convert.frombase64string?view=netframework-4.8)

## 使用文字について
Base64は64種類の文字を利用するため、エンコード後は１文字あたり6bit( 64=2^6) の情報を持ちます。
このBase64ですが利用する文字は
- 大文字英字
- 小文字英字
- 数字
- `+` , `/` or `-`, `_`(URL and Filename safeの場合)
という構成になっています。(詳しくはこちらへ[RFC4648](https://tools.ietf.org/html/rfc4648#page-5))

全部機械で入出力する場合は何でもないのですが、もしBase64エンコードされた値を手動入力する場合、この`+` , `/`などの記号がやっかいだったり、そもそも `i`, `I`, `l`, `L`, `1` とかはフォントによっては見分けるのが至難の業だったりします。

# RFC4648
```
RFCとは、インターネット技術の標準化などを行うIETF（Internet Engineering Task Force）が発行している、
技術仕様などについての文書群。
```
(http://e-words.jp/w/RFC.html より引用)

このRFCで4648ではBase64 についての仕様が載っています。
https://tools.ietf.org/html/rfc4648

このドキュメントを読んでみるとBase64 の他、
- Base32
- Base16
というものも見つけられるかと思います。

## Base32
RFC4648のBase32の構成要素ですが
- 大文字英字
- ` 2,3,4,5,6,7`
というように、大文字小文字の見間違えや`1` と` i, I, l, L` の見間違え防止のために対策がされています。

Base64 に比べ１文字あたりのBit数が減ってしまいます（32=2^5 →5bit)が、人間フレンドリーな内容になっています。


# 実装してみた
実装したスクリプトが置いてあるリポジトリはこちらです。
https://github.com/Cova8bitdots/Base32

（MITライセンスなのでご自由にお使いください）

## そもそも何で実装しようとしたの？
- C# 以外の言語ではエンコード/デコードともに提供されていたりしますが、C#ではBase64しか提供されていないこと。
- ざっとググったところ「エンコードのみ実装した記事」が多い
- 両方実装してあるものでもLinqを多用されていた(読みやすさとパフォーマンスを考えたかった)
- 勉強のため
- (仕事でユーザーの招待ID作成をどうしようかと悩んでいたため)

## 事前準備
エンコード使うテーブルはあらかじめ埋め込んでおきます
```
private static readonly char[] encode_table =
{ 
	'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H',
	'I', 'J', 'K', 'L', 'M', 'N', 'O', 'P',
	'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X',
	'Y', 'Z', '2', '3', '4', '5', '6', '7',
};
```

またデコードですが、毎回入力文字をエンコードテーブルでチェックしようとするとコストがかかるので、
エンコードテーブルの文字をアスキーコードに変換し、その値をIndexとしたデコードテーブルにエンコードテーブルの該当文字のIndexを入れておきます

```c#

private static readonly char[] decode_table = new char[128];
static bool isInitialized = false;

/// <summary>
/// DecodeTableの初期化
/// </summary>
private static void InitilizeDecodeTable()
{
	if( isInitialized )
	{
		return;
	}
	isInitialized = true;

	for ( int i = 0, count = decode_table.Length; i < count; ++ i )
	{
		decode_table[i] = (char)0xFF;	// -1 encoding_tableにありえない値
	}

	for (int i = 0; i < encode_table.Length; i++)
	{
		decode_table[ encode_table[i] ] = (char)i;
	}
}
```
これで事前準備は完了です。

## Encode
実装したメソッドについてはこちらです。

```c#

/// <summary>
/// byte[]からbase32に変換する
/// </summary>
/// <param name="bytes"></param>
/// <param name="withPadding">padding が必要かどうか</param>
/// <returns></returns>
public static string ToBase32String(byte[] bytes, bool withPadding = true)
{
	System.Text.StringBuilder builder = new System.Text.StringBuilder();
	// Base32 は1文字5bitなので 5byte ずつとりだして8文字ずつに変換する
	for ( int i = 0, count = bytes.Length; i < count; i += DIGIT)
	{
		// 40bitに統合
		ulong merge = 0;
		int parseByteCount = 0;
		for (int j = 0; j < DIGIT; j++)
		{
			// 範囲外参照チェック
			if( j+i >= count )
			{
				break;
			}
			// 4-j ビットシフトが必要
			merge |= ( (ulong)bytes[i+j] << (BYTE_LENGTH * (DIGIT-j-1)) );
			parseByteCount++;
		}
		// 5bit 毎に分割
		byte b;
		for (int j = 0; j < BYTE_LENGTH; j++)
		{
			b = (byte)((merge >> DIGIT * (BYTE_LENGTH-j-1) ) & 0x1F);
			// 取り出して来た有効byteのところまで変換をかける
			if( j < parseByteCount * BYTE_LENGTH / DIGIT +1 )
			{
				builder.Append( encode_table[b]);
			}
		}
	}
	if( withPadding )
	{
		// 4文字ずつ分割して不足分は = で埋める
		int lastWordLen = builder.Length % PADDING_UNIT;
		for (int i = 0; i < PADDING_UNIT - lastWordLen; i++)
		{
			builder.Append(PADDING);
		}
	}

	return builder.ToString();
}
```

ポイントとしては、コメントにもある通りBase32は１文字あたり5bitのため
1byte=8bit との最小公倍数である40bit 毎に変換をかけていきます。
そのため5byte ずつ読み取ってそれぞれ順番にBase32エンコードをします。

## Decode
実装したメソッドについてはこちらです。

```c#

/// <summary>
/// Base32からbyte[]に変換する
/// </summary>
/// <param name="base32"></param>
/// <returns></returns>
public static byte[] FromBase32String(string base32)
{
	if ( 0 != (base32.Length & 3 )){
		// Base32じゃないよ！
		Debug.LogError( "not base32" );
		return null;
	}

	InitilizeDecodeTable();

	List<byte> decode = new List<byte>( base32.Length);
	// 8文字( 8 x 5bit =40bit) ずつ取り出して5byteごとに変換をかけていく
	for ( int i = 0, count = base32.Length; i < count; i += BYTE_LENGTH )
	{
		ulong merge = 0;
		for (int j = 0; j < BYTE_LENGTH; j++)
		{
			if( i + j >= count )
			{
				break;
			}
			char c = base32[i+j];
			if( c == PADDING )
			{
				break;
			}
			long index = (long)decode_table[c];
			// 改行などの対象外の場合はもう一文字
			if( index < 0 )
			{
				Debug.LogError($"Cant Found:{c}");
				continue;
			}
			// 1文字5bit なので5n bit シフトを行う
			merge |= (ulong)( index << ( (BYTE_LENGTH-j-1) * DIGIT) );

		}
		// 40bit を8bitずつに分割
		for (int j = 0; j < DIGIT; j++)
		{
			decode.Add( (byte)( (merge >> ( (DIGIT-j-1) * BYTE ) ) & 0xFF) );
		}
	}
	return decode.ToArray();
}
```

こちらもエンコードと同様、1文字あたり5bit のためbyte列を作るにはやはり
最小公倍数の40bit ずつとって、5byte 分変換するというプロセスをとることにしました。

また、事前準備の項目でも説明した通り、デコードテーブルを予め作っておくことで、
都度Encodeテーブル内の文字と一致するかというForLoopによるチェックを行わないで済むようになっています。

# 終わりに
どうしてもBase64使えないとか、人間に記号を入力させたくないという事情があればBase32を使うのもまた一つの解決策でしょう。

まぁBase64使えればBase64使えばいいと思います。はい。

# 参考文献
- [ C# System.Convertクラス]( https://docs.microsoft.com/ja-jp/dotnet/api/system.convert?view=netframework-4.8)
- [IT 用語辞典 RFCとは](http://e-words.jp/w/RFC.html)
- [RFC4648](https://tools.ietf.org/html/rfc4648)
- [実装したスクリプト置き場](https://github.com/Cova8bitdots/Base32/blob/master/Base32.cs)