【Rust】Base64を実装する

## はじめに

本記事ではBase64についての説明と、実際に開発したツールの解説をします。

https://github.com/yt2b/base64/tree/d1392fe00742d4e9d5ff822adb09eaf920bf297f

## Base64とは

バイナリデータを64種類の印字可能な文字に変換するエンコード方式です。
インターネット上でバイナリデータをやりとりする際、この形式に変換することで
画像や音声データ等をテキストとして送信することができます。

例としてJSONでバイナリデータをやり取りする場合等にBase64形式へエンコードします。
また、Base64形式にエンコードすると元のデータサイズより33%程度増加します。

## アルゴリズム

Base64形式へエンコードする手順は以下の通りです。

1. データを6ビットずつに分割する
2. 末尾のデータが6ビットになるように0ビットを追加する
3. 変換表を元に6ビットのデータを文字に変換する
4. 変換した文字列の長さが4の倍数になるように末尾に`=`を追加

バイナリにデコードする手順は以下の通りです。

1. 変換表を元に文字を6ビットのデータに変換する
※ パディングの`=`は000000に変換する
2. データを8ビットずつに分割する
3. パディング`=`の数だけ末尾のバイトを削除する

### 変換表

エンコードやデコードの際は、以下の表の通りにビットと文字を対応付けします。

|ビット|文字|ビット|文字|ビット|文字|ビット|文字|
|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|
|000000|A|010000|Q|100000|g|110000|w|
|000001|B|010001|R|100001|h|110001|x|
|000010|C|010010|S|100010|i|110010|y|
|000011|D|010011|T|100011|j|110011|z|
|000100|E|010100|U|100100|k|110100|0|
|000101|F|010101|V|100101|l|110101|1|
|000110|G|010110|W|100110|m|110110|2|
|000111|H|010111|X|100111|n|110111|3|
|001000|I|011000|Y|101000|o|111000|4|
|001001|J|011001|Z|101001|p|111001|5|
|001010|K|011010|a|101010|q|111010|6|
|001011|L|011011|b|101011|r|111011|7|
|001100|M|011100|c|101100|s|111100|8|
|001101|N|011101|d|101101|t|111101|9|
|001110|O|011110|e|101110|u|111110|+|
|001111|P|011111|f|101111|v|111111|/|

<details><summary>おまけ: 変換表を出力するコード</summary>

変換表を手入力するのはしんどかったので、Markdown形式の変換表を出力するコードを書きました。

```rust
    println!("|ビット|文字|ビット|文字|ビット|文字|ビット|文字|");
    println!("|:---:|:---:|:---:|:---:|:---:|:---:|:---:|:---:|");
    let string = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/";
    for i in 0..16 {
        let row = (0..4)
            .map(|j| {
                let idx: usize = 16 * j + i;
                (idx, string.chars().nth(idx).unwrap())
            })
            .fold("|".to_string(), |row, (idx, ch)| {
                format!("{row}{:06b}|{ch}|", idx)
            });
        println!("{row}");
    }
```

</details>

### サンプル

例として文字列「ABCD」をエンコードする手順を載せます。
(テキストデータを変換するのはあまり意味のないことですが。。。)

```
ABCD
↓ 2進数で表す
01000001 01000010 01000011 01000100
↓ 6ビットずつに分割
010000 010100 001001 000011 010001 00
↓ 末尾に0ビットを追加
010000 010100 001001 000011 010001 000000
↓ 変換表を元に変換
QUJDRA
↓ 長さが4の倍数になるようにパディングとして「=」を追加
QUJDRA==
```

デコードする手順は以下のようになります。

```
QUJDRA==
↓ 変換表を元に変換
010000 010100 001001 000011 010001 000000 000000 000000
↓ 8ビットずつに分割
01000001 01000010 01000011 01000100 00000000 00000000
↓ パディングの「=」が2つあるので、末尾の2バイトを削除
01000001 01000010 01000011 01000100
↓ ASCIIで表す
ABCD
```

## ソースコードの説明

実装したコードの一部を説明します。
まずはエンコード時に行う、データを6ビットに分割する手順についてです。
以下の処理を3バイトごとに行います。

最初に3バイトのデータを1つの変数にまとめます。
この時、値が重ならないように8の倍数分左シフトしてからOR演算します。
下記の例では`A`を16ビット、`B`を8ビット左シフトしています。

```
A:      01000001
B:      ↓       01000010
C:      ↓       ↓       01000011
        ↓       ↓       ↓
merged: 010000010100001001000011
```

この処理をイテレータとメソッドチェーンで実装しました。
`fold`関数を使うことで、各データを左にシフトしながらまとめることができます。

```rust
fn encode(input: Vec<u8>) -> Vec<u8> {
    ...
            // 複数のデータを1つの変数にまとめる
            let merged = bytes
                .iter()
                .enumerate()
                .fold(0u32, |merged, (i, x)| merged | (*x as u32) << (16 - 8 * i));
    ...
}
```

次にまとめた変数を6ビットごとに分割します。
まとめた変数を6の倍数分右シフトして、63(2進数で`111111`)とのAND演算を行います。
この演算で必要な値を6ビット分取得することができます。
下記の例では`bytes[0]`は18ビット、`bytes[1]`は12ビット右シフトしてからAND演算を行います。

```
merged:   010000010100001001000011
               ↓     ↓     ↓     ↓
bytes[0]: 010000     ↓     ↓     ↓
bytes[1]:       010100     ↓     ↓
bytes[2]:             001001     ↓
bytes[3]:                   000011
```

値を分割後、HashMapを使って6ビットの値をBase64文字のバイトに変換します。
この一連の処理も下記の様にメソッドチェーンで実装しています。

```rust
fn encode(input: Vec<u8>) -> Vec<u8> {
    ...
            // 6ビットずつに分割してBase64文字に変換する
            let len = (8 * bytes.len()).div_ceil(6);
            (0..len)
                .map(|i| (merged >> (18 - 6 * i)) & 63)
                .filter_map(|i| table.get(&(i as u8)))
                .copied()
                .collect::<Vec<u8>>()
    ...
}
```

デコード時のデータを8ビットずつ戻す手順も上記の要領で行っています。
Base64文字を4文字ごとに1つの変数にまとめて、8ビットずつビット演算で取得しています。

## 実践

今回開発した変換ツールで画像データをBase64形式にエンコードします。
その後、デコードして元に戻せることを確認します。
エンコードするのは以下の画像です。

![rustacean-flat-noshadow.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2693350/070252ec-274e-41d4-b57c-fcc5efca7b6c.png)

画像を実行ファイルの標準入力に渡して、エンコード結果をファイルに保存します。
ファイルを開くと長い文字列が書き込まれているのが確認できます。
```
$ cat image.png | ./target/release/base64 encode > encoded.txt
$ cat encoded.txt
iVBORw0KGgoAAAANSUhEUgAAAcwAAAEzCAYAAAC8HzNKAAAAAXNSR0IArs4c6QAAAJZlWElmTU0AKgAAAAgABQESAAMAAAABAAEAAAEaAAUAAAABAAAASgEbAAU...
```

今度は同じ要領でデコードします。
デコード結果と元ファイルのハッシュ値を比較すると完全に一致しています。


```
$ cat encoded.txt | ./target/release/base64 decode > decoded.png
$ md5 ./image.png ./decoded.png
MD5 (image.png) = 25e50ff2e0a31ddaaf79ab96e9c171ae
MD5 (decoded.png) = 25e50ff2e0a31ddaaf79ab96e9c171ae
```

## 参考文献

https://ja.wikipedia.org/wiki/Base64

https://rustacean.net

https://linux.command-ref.com/command-base64.html