UTF-8とバイナリの分離処理を半分自前でいい感じに処理してみる。

# やりたいこと
バイナリの中に埋め込まれているテキストデータを抽出したい。

言い方を変えよう。
バイナリデータに含まれるUTF-8 encodedなデータをいい感じにバイナリと分離したい。

こういうことをしたい
`XXXXXXXXAAAAAAAAAXXXXAAAA`
みたいなデータがあったとして
A：UTF-8
X：バイナリ値（UTF-8で表現不能な値）

このデータを読み込ませたら

``` Rust
[
    ByteSequence(XXXXXXXX),
    Utf8Sequence(AAAAAAAAA),
    ByteSequence(XXXX),
    Utf8Sequence(AAAA)
]
```
みたいな配列データを作りたい。

配列データを作ること自体は列挙体使えばできるけど、問題はUTF-8とバイナリ値の分離が問題なんだよな。

# 方向性
Rustの機能を使ってUTF-8のデコードロジックを実装していく。

## すべきこと
1. UTF-8っぽいバイト列を「バイトシーケンス」か「UTF-8シーケンス」かの判定する
1. もし、UTF-8っぽいバイト列でもUTF-8のルールに違反していたらバイトシーケンスとして記録する
    1. 「UTF-8シーケンス」ならStringとして保持する
    1. 「バイトシーケンス」ならVec<u8>として保持する
1. 1～3を繰り返して、StringとVec<u8>の要素を持った配列にする

## この記事によれば簡単にできるらしいよ
[UTF-8の冗長なエンコード(2009年) - はせがわようすけ](https://gihyo.jp/admin/serial/01/charcode/0004)

> UTF-8からUTF-16などへの変換は、比較的簡単にビット操作などで書くことができてしまうため、つい自前で実装してしまいたくなりますが、よほどの理由がない限りそういった処理はライブラリやフレームワークなどの信頼できる処理系に任せるべきでしょう。

ほら、簡単にできるって書いてある。（大事なところを読み飛ばしていくスタイル）

## Rustの機能って具体的には？
Rustは先生ですよ。
> ライブラリやフレームワークなどの信頼できる処理系に任せるべきでしょう

って書いてあるしね、やっぱり信頼できるRust先生の指導の下やるべきですよ。素人が手を出す分野ではないね。

`String::from_utf8`
この関数にデータ食わせて、エラー吐いたらWikipedia見て修正していく方向性でやっていく。

何も工夫のない、脳筋主義的なやり方をやっていきます。

## Wikipediaによると？
### UTF-8のバイトシーケンス
| 1バイト目|2バイト目|3バイト目|4バイト目|意味合い
|---|---|---|---|---|
|0xF0～0xF4|0x80～0xBF|0x80～0xBF|0x80～0xBF|4バイトシーケンス
|0xE0～0xEF|0x80～0xBF|0x80～0xBF|-|3バイトシーケンス
|0xC2～0xDF|0x80～0xBF|-|-|2バイトシーケンス
|0x00～0x7F|-|-|-|1バイトシーケンス（Asciiコード）

### NGなバイトシーケンス
上記のシーケンスのうち以下のシーケンスはルール違反
| 1バイト目|2バイト目|NGの意味合い
|---|---|---|
|0xF0|0x80～0x8F|冗長な符号化であるため
|0xE0|0x80～0x9F|冗長な符号化であるため
|0xED|0xA0～|サロゲートペアの符号位置であるため
|0xF4|0x90～|Unicodeコードポイントの範囲外であるため

## というわけで実装してみる
``` rust
#[derive(Debug, Clone, PartialEq, PartialOrd)]
pub enum DataSequence {
    Utf8Sequence(String), // UTF-8として有効なデータ、文字列として扱います。utf-8シーケンスと表記します
    ByteSequence(Vec<u8>), // バイナリデータ、ここではバイトシーケンスと表記します
}

// UTF-8とバイトシーケンスを分離した表現「DataSequence」を作成するする関数です
pub fn collect_utf8_sequences(byte: &Vec<u8>) -> Vec<DataSequence> {
    let mut i = 0;
    let mut seqdata_list = Vec::new();
    let mut utf8_seq = Vec::new();
    let mut bin_seq = Vec::new();

    while i < byte.len() {
        // utf-8として有効なシーケンスであるかどうかを検査します。
        // 配列と今検査しているオフセットを渡して、今読もうとしているところが
        // バイトシーケンスなのかutf-8シーケンスなのかの識別をします。
        let (len, valid) = utf8_len(byte, i);
        if valid {
            // 有効なutf-8シーケンスがあったら記録していきます
            if bin_seq.len() > 0 {
                seqdata_list.push(DataSequence::ByteSequence(bin_seq.clone()));
                bin_seq.truncate(0);
            }
            // マルチバイトなので、長さ分書き込みます
            for off in 0..len {
                utf8_seq.push(byte[i + off]);
            }
        } else {
            // バイトシーケンスであればこちらへ分岐します
            // 今までに収集された有効なUTF-8シーケンスがあれば、シーケンスをStringにして保存します。
            if utf8_seq.len() > 0 {
                seqdata_list.push(DataSequence::Utf8Sequence(
                    String::from_utf8(utf8_seq.clone()).unwrap(),
                ));
                utf8_seq.truncate(0);
            }
            // バイトシーケンスを保存します
            // [0xE0,0x00,0x8A]のような不正なシーケンスがあれば、以下のようにすべて保存していきます。
            // ByteSequence([0xE0,0x00,0x8A])
            // 一方で
            // ByteSequence([0xE0]),Utf8Sequence("\0"),ByteSequence([0x8A])
            // というような感じでも良かったのですが、扱いにくそうだなと思ったので前者の形で実装しました。
            for off in 0..len {
                bin_seq.push(byte[i + off]);
            }
        }
        i += len;
    }
    if utf8_seq.len() > 0 {
        seqdata_list.push(DataSequence::Utf8Sequence(
            String::from_utf8(utf8_seq.clone()).unwrap(),
        ));
    }
    if bin_seq.len() > 0 {
        seqdata_list.push(DataSequence::ByteSequence(bin_seq.clone()));
    }
    seqdata_list
}

// indexの位置にあるバイトデータをUTF-8の1文字目と仮定して扱います。
// 明らかに1文字目でもないしUTF-8のルールに違反している場合は
// バイナリデータとして扱うように(n,false)を返します。なお、n>=1としています。
// 返却値は、(シーケンス長,妥当性) の意味合いを持つタプル型を返します。
// 妥当性：UTF-8として妥当なシーケンスならtrue、妥当でなければfalseとなります。
// シーケンス長：妥当であろうがなかろうが、シーケンスの長さ（バイト数）を返します。
fn utf8_len(byte_array: &Vec<u8>, index: usize) -> (usize, bool) {
    let byte = byte_array[index];
    let i = index;
    let len = byte_array.len();
    // 不正なUTF-8エンコードかどうかを確認するクロージャ
    let is_invalid_encode = |off| -> bool {
        let second = byte_array[off + 1];
        let first = byte_array[off + 0];
        if first == 0xE0 && 0x80 <= second && second <= 0x9F // 冗長な符号化
                || first == 0xF0 && 0x80 <= second && second <= 0x8F // 冗長な符号化
                || first == 0xED && 0xA0 <= second // サロゲートペアの符号位置
                || first == 0xF4 && 0x90 <= second // Unicodeの範囲外
        {
            true
        } else {
            false
        }
    };
    // バリデーションを担うクロージャ
    let validation = |seq_len| -> (usize, bool) {
        if (len - i) >= seq_len {
            for off in 1..seq_len {
                if !(0x80 <= byte_array[off + i] && byte_array[off + i] < 0xBF)
                    || is_invalid_encode(i)
                {
                    return (seq_len, false);
                }
            }
            (seq_len, true)
        } else if len > i {
            (len - i, false)
        } else {
            // あり得ないが、一応処理を入れておきます。
            // ありえないので、ここに来たらpanicするようにします。
            panic!("illegal index");
        }
    };
    // 1バイト目の値をチェックするクロージャ
    let condition = |start: u8, end: u8| -> bool {
        let first = byte;
        start <= first && first <= end
    };

    if condition(0xF0, 0xF4) {
        // 4バイト文字
        validation(4)
    } else if condition(0xE0, 0xEF) {
        // 3バイト文字
        validation(3)
    } else if condition(0xC2, 0xDF) {
        // 2バイト文字
        validation(2)
    } else if byte & 0xff < 0x7f {
        // Ascii文字
        (1, true)
    } else {
        // UTF-8では表現不能なバイト
        (1, false)
    }
}
```

これに
``` rust
// あくまでもイメージ、実際はコンパイルとおらん
let bytes = "Helloほげ\x01\x02\x00\xff\xff\xffふが\xf8NVAlid"
```

こういう配列を食わせると

``` rust
[
    Utf8Sequence("Helloほげ\u{1}\u{2}\0"),
    ByteSequence([255, 255, 255]),
    Utf8Sequence("ふが"),
    ByteSequence([248]),
    Utf8Sequence("NVAlid")
] 
```

というような出力を得られるように成った。
めでたしめでたし。

### 番外編（テスト）
有名な冗長な符号化の例としてディレクトリトラバーサルに悪用可能な`/`(0x2F)を2～4バイトで符号化するというのが有る。
果たしてここで作ったやつにそいつは通用するのだろうか？やってみた。
ついでに、BOMもUTF-8符号化したものをどう解釈するかテストしてみた。

``` rust
#[test]
fn 冗長な符号化() {
    let mut bytes = [0x2F, 0xC0, 0xAF, 0xE0, 0x80, 0xAF, 0xF0, 0x80, 0x80, 0xAF].to_vec();
    dump(&bytes);
    let actual_seq = collect_utf8_sequences(&bytes).sequence;
    let expect_seq = [
        DataSequence::Utf8Sequence("/".to_owned()),
        DataSequence::ByteSequence(vec![0xC0, 0xAF, 0xE0, 0x80, 0xAF, 0xF0, 0x80, 0x80, 0xAF]),
    ];
    assert_eq!(actual_seq.len(), expect_seq.len());
    for (i, seq) in actual_seq.iter().enumerate() {
        assert_eq!(seq, &expect_seq[i]);
    }
}

// ついでにやる
#[test]
fn 符号化されたBOM() {
    let mut bytes = [0xEF, 0xBB, 0xBF].to_vec();
    dump(&bytes);
    let actual_seq = collect_utf8_sequences(&bytes).sequence;
    let expect_seq = [DataSequence::ByteSequence(vec![0xEF, 0xBB, 0xBF])];
    assert_eq!(actual_seq.len(), expect_seq.len());
    for (i, seq) in actual_seq.iter().enumerate() {
        assert_eq!(seq, &expect_seq[i]);
    }
}
```
実行結果

``` bash
test utf8_sequence_collector::冗長な符号化 ... ok
test utf8_sequence_collector::符号化されたBOM ... ok
```

めでたしめでたし。（しらんけど。）

出来立てのソースなので冗長だなぁ。リファクタしよ。
このロジックはなにかに使えそうだから、秘伝のタレにはしたくない。