【Rust】文字列型のUTF-8検証の中身

Rustの文字列型`str`はバイト列`[u8]`と同じデータ形式だが、安全なコードでは常に有効なUTF-8が保持されるという特殊な性質をもっている。`str`のUTF-8の有効性がどのように保証されているのか気になったので、UTF-8の復習も兼ねてライブラリの実装を調べてみた。

* 調査したRustのバージョン：1.46

# 有効なUTF-8とは

UTF-8はUnicodeの表現方式（エンコード）の1つで、最大`0x10ffff`（1114111）までの文字コードを1〜4バイトの可変長で表現する。各文字の表現に必要なバイト数は文字コードの範囲によって異なり、0〜127の範囲（いわゆるASCII文字）であればそのまま1バイトで表現できるのがひとつの特徴である。

文字コードの範囲と必要なバイト数の関係は下記表のようになる。必要ビット数はコード値を2進数で表記するときに必要な桁数を表す。

|コード値の範囲|必要ビット数|バイト数（UTF-8）|
|:---------:|:--------:|:-----------:|
|`0x000000-0x00007f`|1-7|1|
|`0x000080-0x0007ff`|8-11|2|
|`0x000800-0x00ffff`|12-16|3|
|`0x010000-0x10ffff`|17-21|4|

各範囲の文字コードは以下のようなパターンでUTF-8のバイト列に変換される（コード値、UTF-8ともに2進数表記）。

```
コード値：00000000_00000000_0xxxxxxx（1-7ビット）
⇒ UTF-8：0xxxxxxx（1バイト）

コード値：00000000_00000yyy_yyxxxxxx（8-11ビット）
⇒ UTF-8：110yyyyy 10xxxxxx（2バイト）

コード値：00000000_zzzzyyyy_yyxxxxxx（12-16ビット）
⇒ UTF-8：1110zzzz 10yyyyyy 10xxxxxx（3バイト）

コード値：000wwwzz_zzzzyyyy_yyxxxxxx（17-21ビット）
⇒ UTF-8：11110www 10zzzzzz 10yyyyyy 10xxxxxx（4バイト）
```

特に重要な点は以下の2つである。

* 1バイト目（開始バイト）の先頭のビットパターンによって全体のバイト数を判定できる。
  （`0...`：1バイト、`110...`：2バイト、`1110...`：3バイト、`11110...`：4バイト）
* 2バイト目以降（継続バイト）は必ず`10...`で始まる。

同じ要領で`111110...`を5バイト、`1111110...`を6バイトのように拡張できそうだが、現在は必要がないため認められていない。

## 不正なUTF-8の例

以下のバイト列はすべて不正なUTF-8である（判定に関係しないビットは`*`としている）。

* `10******`：継続バイトで始まっている
* `0******* 10******`：1バイト形式の開始バイトに継続バイトが続いている（1バイト目までは正常なので本質的には上と同じ）
* `1110**** 10****** 0*******`：3バイト形式の開始バイトに対して継続バイトが1つしか続かない）
* `11111***`：開始バイトが認められていない範囲の値である

## 不正なUTF-8の特殊なケース

開始バイトと継続バイトの並び方によって不正と判定されるケースの他に、対応するコード値の範囲によって不正と判定されるケースがある。

### 上限オーバー

4バイト形式の一部は、コード値がUnicodeの上限である`0x10ffff`を超過する。このようなバイト列は不正と判定される。

* `11110[100] 10[01****] 10[******] 10[******]`（⇒`1_0001_****_****_****_****`＝`0x11hhhh`）

### 冗長な表現

* `110[00001] 10[******]`

上記のバイト列は2バイト形式として問題ないように見えるが、対応するコード値が7ビット（`1******`）であるため不正とされる。7ビット以下のコード値は1バイト形式（`0*******`）で表現できるため、同じコード値を2バイト以上で表現したものは冗長とされ認められない。同様に、nバイト形式で表現可能なコード値を(n+1)バイト以上の形式で表現したものは不正と判定される。

この制約により、コード値とUTF-8のバイト列の対応は一意（1対1）に定まる。

### サロゲートペアのための文字コード

Unicodeに馴染みのある方はサロゲートペアという言葉を聞いたことがあると思う。サロゲート（surrogate）は「代用」を意味する。まずはサロゲートペアについて簡単に説明しておこう。

Unicodeが制定された当初は、2バイト分（65536個）のコード値があれば全ての文字を収録できるだろうと考えられていた。その想定の下、すべての文字を2バイトで表現するコード体系`UTF-16`が広く普及する。ところがコード表がある程度埋まってくると「やっぱり足りないのでは」という雰囲気が出てきた。そこで未使用だった範囲のコード値を2つ組み合わせることにより、2バイトの限界を越えた1つのコード値を表現するというサロゲートペアの仕組みがUTF-16に導入された。

サロゲートペアに使用されるコード値は、混同を避けるために上位（highまたはleading）と下位（lowまたはtrailing）の2種類に分けられている。それぞれ以下の範囲から1024個のコード値が割り当てられ、いずれも上位6ビットで識別可能である。

|区分|範囲（16進）|ビットパターン（2進）|
|:-:|:--------:|:-----------:|
|上位|`D800-DBFF`|`1101_10**_****_****`|
|下位|`DC00-DFFF`|`1101_11**_****_****`|

上位、下位のサロゲートペアによるコード値は以下のように計算される。

```
（上位、下位）：(1101_10xx_xxxx_xxxx, 1101_11yy_yyyy_yyyy)
 ↓
コード値：0b_xxxx_xxxx_xxyy_yyyy_yyyy + 0x_10000 (65536)
```

コード値に65536を加えるのは、サロゲートペアで表現するコード値の範囲を2バイトで表現できるコード値の範囲の後ろに置くためである。

* `0x0000-0xffff`：従来通り2バイトで表現
* `0x10000-...`：サロゲートペア（2バイト×2）で表現

サロゲートペアで表現可能なコード値は2の20乗（=1048576=`0x100000`）個であり、UTF-16は65536個のコード値から2048個を犠牲にすることで約100万個のコード値を召喚することに成功した。表現可能なコード値の上限は2バイトの上限`0xffff`からサロゲートペア分の`0x100000`を加えた`0x10ffff`まで増加し、これが現在のUnicodeのコード値の上限となっている。

話をUTF-8に戻そう。結論から言えば、UTF-16の拡張で導入されたサロゲートペアはUTF-8では必要なかった。というのも、サロゲートペアによって拡張されたコード値の範囲（`0x10000-0x10ffff`）は、UTF-8では4バイト形式で表現可能だからである。

UTF-8は（おそらく）以下の理由でサロゲートペアの使用を禁止した。それに伴い、UTF-8に含まれるサロゲート用のコード値（に対応するバイト列）は不正と判定される。

* サロゲートペアを使用すると、4バイトで表現できるコード値が6バイト（3バイト形式2つ）で表現されるため効率が悪い。
* サロゲートペアを認めると、同じコード値に対して2通りの表現が可能になるため比較処理などで都合が悪い。
* サロゲート用のコード値を別の目的で使用すると、UTF-16との互換性を維持できない（そのコード値をサロゲートに使えなくなるため）。

サロゲート用のコード値に対応するUTF-8のバイト列のパターンは以下のようになる。

```
上位：1101_10**_****_****（0xD800-0xDBFF）
下位：1101_11**_****_****（0xDC00-0xDFFF）
全体：1101_1***_****_****（0xD800-0xDFFF）
対応するUTF-8：1110[1101] 10[1*****] 10[******]
```

## 余談

不正なUTF-8と判定される条件は現在の規定では以上であり、Rustの実装もこれに従っている。

筆者は`0xffef`や`0xffff`を含む場合も不正と判定されるような気がしていたが、そのような判定は実装されていなかった。Unicodeのサイトで調べたところ、現在これらのコード値は「文字が割り当てられることはないが、これらのコード値が含まれてもUnicode文字列としては不正でない（not ill-formed）」という微妙な扱いになっている。

参考：[Private-Use Characters, Noncharacters & Sentinels FAQ](http://www.unicode.org/faq/private_use.html#nonchar8)

# RustのUTF-8検証

ここからはRustの標準ライブラリのソースコードを見ながら検証処理の実装を説明する。対象は`core`クレートの`str`モジュールである（`Version 1.46.0 (04488afe3 2020-08-24)`）。

* [`Module core::str`ドキュメントのリンク](https://doc.rust-lang.org/core/str/index.html)
* [`Module core::str`ソースコードのリンク](https://doc.rust-lang.org/src/core/str/mod.rs.html)

主な内容はバイト列全体を走査してUTF-8検証を行う処理の説明になるが、部分文字列（スライス）取得時のUTF-8検証についても別途説明する。なお、内容は非公開の（`pub`でない）部分が多いため、関数などの名称や実装は今後変更される可能性がある。また、コードを省略する関係でコメントを一部追加／省略した箇所がある。

## 全体走査による検証処理

ここではバイト列`[u8]`を`str`に変換する（正確には`str`として認識する）ときに実行されるUTF-8検証の内容について説明する。

```rust
#[stable(feature = "rust1", since = "1.0.0")]
pub fn from_utf8(v: &[u8]) -> Result<&str, Utf8Error> {
    run_utf8_validation(v)?;
    // SAFETY: Just ran validation.
    Ok(unsafe { from_utf8_unchecked(v) })
}

#[inline]
#[stable(feature = "rust1", since = "1.0.0")]
pub unsafe fn from_utf8_unchecked(v: &[u8]) -> &str {
    // SAFETY: the caller must guarantee that the bytes `v`
    // are valid UTF-8, thus the cast to `*const str` is safe.
    // Also, the pointer dereference is safe because that pointer
    // comes from a reference which is guaranteed to be valid for reads.
    unsafe { &*(v as *const [u8] as *const str) }
}
```

UTF-8検証は`str::from_utf8()`から呼ばれる`run_utf8_validaction()`の中で行われる。なお見ているのは`core`クレートのコードだが、`std::str::from_utf8()`も本体はこの関数である。

まずは`run_utf8_validaction()`の全体像を見てみよう。この関数は非公開（`pub`なし）である。

```rust
/// Walks through `v` checking that it's a valid UTF-8 sequence,
/// returning `Ok(())` in that case, or, if it is invalid, `Err(err)`.
#[inline(always)]
fn run_utf8_validation(v: &[u8]) -> Result<(), Utf8Error> {
    let mut index = 0;
    let len = v.len();

    let usize_bytes = mem::size_of::<usize>();
    let ascii_block_size = 2 * usize_bytes;
    let blocks_end = if len >= ascii_block_size { len - ascii_block_size + 1 } else { 0 };
    let align = v.as_ptr().align_offset(usize_bytes);

    while index < len {
        //...（略）...
    }

    Ok(())
}
```

`while`の中身は省略しているが、`index`を0から`len`まで動かして全体を走査し、エラーがなければ`Ok`、エラーが見つかったらそこで`Err`が返される動きは理解いただけるだろう。`index`、`len`の後ろで定義されている変数については後述することにし、`while`の中身を見ていく。

```rust
    ...
    while index < len {
        let old_offset = index;
        macro_rules! err {
            ($error_len: expr) => {
                return Err(Utf8Error { valid_up_to: old_offset, error_len: $error_len });
            };
        }

        macro_rules! next {
            () => {{
                index += 1;
                // we needed data, but there was none: error!
                if index >= len {
                    err!(None)
                }
                v[index]
            }};
        }
        ...
```

いきなりマクロが2つ定義される。1つ目の`err`マクロは`Err`を`return`するためのマクロで、`valid_up_to`にはUTF-8として正常だった範囲の終端、`error_len: Option<u8>`には`valid_up_to`から何バイト進めれば不正な箇所を飛ばせるかが設定される。ループ内で`index`を進めても`valid_up_to`を設定できるように、ループ開始時点の`index`を`old_offset`に保存している。

2つ目の`next`マクロは`index`を1つ進めた後に入力バイト列`v`のその位置の値をとる。ただし`index`が`v`からはみ出す場合は関数に`Err`を返させる。C言語やJavaなどの前置インクリメント配列アクセス（`v[++index]`）に近い（境界検査のおまけ付き）。

続きを見ていこう。

```rust
    while index < len {
        ...
        let first = v[index];
        if first >= 128 {
            let w = UTF8_CHAR_WIDTH[first as usize];
            match w {
                2 => ...
                3 => ...
                4 => ...
                _ => err!(Some(1)),
            }
            index += 1;
        } else {
            // if w == 1 { index += 1; }
            ...
        }
    } // while index < len
```

ここから本格的にUTF-8の検査が始まる。まず開始バイト`first`を読み取り、現在位置から始まる文字のバイト数を判定する。`first >= 128`であれば2バイト以上、そうでなければ1バイトのASCII文字である。

2バイト以上の場合はさらに`UTF8_CHAR_WIDTH`という配列（後述）を使って実際のバイト数`w`を求める。`first`が不正な値であればここで`w`に0が設定され、続く`match`の中でエラーが返される。適正であれば`match`の中でさらに検証が続く。

なお`match`内の処理で`index`は現在位置の文字の最後のバイトまで進められるので、`match`後は`index`を1だけ進めれば次の文字に移る。

バイト数`w`の決定に使用した`UTF8_CHAR_WIDTH`は以下のような配列である。

```rust
static UTF8_CHAR_WIDTH: [u8; 256] = [
    1, 1, 1, ..., 1, 1, 1, // 0x1F
    ...
    1, 1, 1, ..., 1, 1, 1, // 0x7F
    0, 0, 0, ..., 0, 0, 0, // 0x9F
    ...
    0, 0, 2, ..., 2, 2, 2, // 0xDF
    3, 3, 3, ..., 0, 0, 0, // 0xFF
];
```

一部省略しているが、雰囲気は伝わると思う。添字に`first`を使えるように長さは256で、各範囲に以下の表の値が設定されている。なお`first`のみで判定できるエラーはすべてここで検出される。

|`first`の範囲（16進）|`first`の範囲（2進）|`w`|補足|
|:----------:|:-------:|:----------:|:------------|
|`0x00-0x7f`|`00000000-01111111`|1|ASCII文字|
|`0x80-0xbf`|`10000000-10111111`|0（エラー）|継続バイト|
|`0xc0-0xc1`|`11000000-11000001`|0（エラー）|(1)|
|`0xc2-0xdf`|`11000010-11011111`|2|2バイト形式|
|`0xe0-0xef`|`11100000-11101111`|3|3バイト形式|
|`0xf0-0xf4`|`11110000-11110100`|4|4バイト形式|
|`0xf5-0xf7`|`11110101-11110111`|0（エラー）|(2)|
|`0xf8-0xff`|`11111000-11111111`|0（エラー）|(3)|

* (1) 2バイト形式に合致するが、この範囲はコード値が7ビット以下なので1バイト（ASCII文字）で表現できる。
* (2) 4バイト形式に合致するが、この範囲はコード値がUnicodeの上限`0x10ffff`を超える。
* (3) 現在のUTF-8ではこの範囲は使用しない。

それでは`match w {...}`の`2`, `3`, `4`の各処理を順番に見ていこう。

```rust
            match w {
                2 => {
                    if next!() & !CONT_MASK != TAG_CONT_U8 {
                        err!(Some(1))
                    }
                }
                ...
            }
            ...
```

`w == 2`の場合の処理は比較的シンプルで、確認しているのは2バイト目が継続バイト（`10******`）であることだけである。使用されている定数の値は以下の通りである。

```rust
/// Mask of the value bits of a continuation byte.
const CONT_MASK: u8 = 0b0011_1111;
/// Value of the tag bits (tag mask is !CONT_MASK) of a continuation byte.
const TAG_CONT_U8: u8 = 0b1000_0000;
```

以下のように書き換えれば、2バイト目が`10******`でなければエラーとしているのが分かると思う。この判定条件は以降の`w == 3`、`w == 4`でも使用される。

```rust
if next!() & !CONT_MASK != TAG_CONT_U8 { err!(...) }
// ↓
let second = next!();
if (second & 0b_11000000) != 0b_10000000 { err!(...) }
```

`w == 3`の場合に移る。

```rust
            match w {
                ...
                3 => {
                    match (first, next!()) {
                        (0xE0, 0xA0..=0xBF)
                        | (0xE1..=0xEC, 0x80..=0xBF)
                        | (0xED, 0x80..=0x9F)
                        | (0xEE..=0xEF, 0x80..=0xBF) => {}
                        _ => err!(Some(1)),
                    }
                    if next!() & !CONT_MASK != TAG_CONT_U8 {
                        err!(Some(2))
                    }
                }
                ...
            }
            ...
```

`w == 2`の場合より複雑になっているが、最初の`match`で1バイト目と2バイト目、次の`if`で3バイト目をチェックしている。3バイト目の判定は前述したものと同じなので、1バイト目と2バイト目の`match`の内容を整理しよう。

`w`が3になる`first`の範囲が`0xe0-0xef`で、継続バイト（`10******`）の範囲が`0x80-0xbf`であることに注意すると、この`match`の判定内容は以下の表のようになる。ただし2バイト目が継続バイトの範囲外である場合のエラーは表には含めていない。

|1バイト目|2バイト目|判定|補足|
|:-:|:-:|:-:|:--|
|`0xe0`（`11100000`）|`0x80-0x9f`（`100*****`）|エラー|(1)|
|（同上）|`0xa0-0xbf`（`101*****`）|OK||
|`0xe1`（`11100001`）<br>:<br>`0xec`（`11101100`）|`0x80-0xbf`（`10******`）|OK||
|`0xed`（`11101101`）|`0x80-0x9f`（`100*****`）|OK||
|（同上）|`0xa0-0xbf`（`101*****`）|エラー|(2)|
|`0xee`（`11101110`）<br>:<br>`0xef`（`11101111`）|`0x80-0xbf`（`10******`）|OK||

* (1) コード値が11ビット以下になるため2バイト形式で表現できる。
* (2) サロゲート用のコード値。

続いて`w == 4`の場合に移る。

```rust
            match w {
                ...
                4 => {
                    match (first, next!()) {
                        (0xF0, 0x90..=0xBF) | (0xF1..=0xF3, 0x80..=0xBF) | (0xF4, 0x80..=0x8F) => {}
                        _ => err!(Some(1)),
                    }
                    if next!() & !CONT_MASK != TAG_CONT_U8 {
                        err!(Some(2))
                    }
                    if next!() & !CONT_MASK != TAG_CONT_U8 {
                        err!(Some(3))
                    }
                }
                ...
            }
            ...
```

`w == 4`は`w == 3`の場合とほぼ同じ流れであり、最初の`match`で1バイト目と2バイト目、後続の`if`で3バイト目と4バイト目をチェックしている。こちらも`w == 3`の場合と同様に最初の`match`の判定表を作ると以下のようになる。`first`の範囲は`0xf0-0xf4`である。

|1バイト目|2バイト目|判定|補足|
|:-:|:-:|:-:|:--|
|`0xf0`（`11110000`）|`0x80-0x8f`（`1000****`）|エラー|(1)|
|（同上）|`0x90-0xbf`（`1001****`）|OK||
|`0xf1`（`11110001`）<br>:<br>`0xf3`（`11110011`）|`0x80-0xbf`（`10******`）|OK||
|`0xf4`（`11110100`）|`0x80-0x8f`（`1000****`）|OK||
|（同上）|`0x90-0xbf`（`1001****`）|エラー|(2)|

* (1) コード値が16ビット以下になるため3バイト形式で表現できる。
* (2) コード値がUnicodeの上限`10ffff`を超える。

`match w {...}`の`2`, `3`, `4`の各処理は以上である。いずれの処理もエラーがなければ`next!()`が必要回数実行され、`index`が文字の最終バイトを指していることが確認できる。

最後に残っていた`w == 1`（`first < 128`）の場合を見てみよう。1バイト形式（ASCII文字）ではエラーになる余地がないため、単純に`index`を1つ進めるだけでいいのだが、Rustは少し複雑な実装で高速化を試みている。

```rust
        let first = v[index];
        if first >= 128 {
            ...
        } else {
            // Ascii case, try to skip forward quickly.
            // When the pointer is aligned, read 2 words of data per iteration
            // until we find a word containing a non-ascii byte.
            if align != usize::MAX && align.wrapping_sub(index) % usize_bytes == 0 {
                let ptr = v.as_ptr();
                while index < blocks_end {
                    // SAFETY: since `align - index` and `ascii_block_size` are
                    // multiples of `usize_bytes`, `block = ptr.add(index)` is
                    // always aligned with a `usize` so it's safe to dereference
                    // both `block` and `block.offset(1)`.
                    unsafe {
                        let block = ptr.add(index) as *const usize;
                        // break if there is a nonascii byte
                        let zu = contains_nonascii(*block);
                        let zv = contains_nonascii(*block.offset(1));
                        if zu | zv {
                            break;
                        }
                    }
                    index += ascii_block_size;
                }
                // step from the point where the wordwise loop stopped
                while index < len && v[index] < 128 {
                    index += 1;
                }
            } else {
                index += 1;
            }
        } // if !(first >= 128)
    } // while index < len
```

条件が満たされれば`index`を一気に進める高速処理が実行され、満たされなければ1ずつ進める地道な処理が実行される。細部に触れる前に処理の概要をまとめておこう。

1. 入力バイト列の現在位置から4バイトまたは8バイトを数値として読み取る（2セット）。ただし現在位置が数値の読み取りに適さなければ、高速処理を諦めて地道な処理に切り換える。
2. 読み取った数値の各バイトがすべてASCII文字であるか判定する。判定は簡単なビット演算で実現される。
3. すべてのバイトがASCII文字ならば、その範囲にはエラーがないので読み飛ばして次に進む（1に戻る）。ASCII文字以外が1つでも含まれるなら高速処理を諦めて地道な処理に切り換える。

関数の最初に宣言されていた以下の変数はすべてここで使用される。

```rust
fn run_utf8_validation(v: &[u8]) -> Result<(), Utf8Error> {
    ...
    let usize_bytes = mem::size_of::<usize>();
    let ascii_block_size = 2 * usize_bytes;
    let blocks_end = if len >= ascii_block_size { len - ascii_block_size + 1 } else { 0 };
    let align = v.as_ptr().align_offset(usize_bytes);
```

ポインタ演算やアライメントは苦手分野なので十分な説明はできないが、少しずつ見ていこう。
まずは最初の`if`条件を見てみる。

```rust
if align != usize::MAX && align.wrapping_sub(index) % usize_bytes == 0 {
```

変数`align`には、入力バイト列`v`の開始アドレスから次の`usize`のアラインまでのバイト数（正確には`u8`の要素数）が設定されている（[pointer::align_offset()](https://doc.rust-lang.org/std/primitive.pointer.html#method.align_offset)）。`usize`のアラインというのは`usize`の値を安全かつ効率的に読み取れるアドレス（メモリ上の位置）で、基本的に`usize`のバイト数（4または8）の倍数になっている。例えば`usize`のバイト数（`usize_bytes`）が8、`v`の開始アドレスが8003であれば、次のアラインのアドレスは8008で`align`は5となる。何らかの事情でアラインを計算できない場合は`align`に`usize::MAX`が設定され、この場合は`if`の条件を満たさず高速処理に入らない。

`(align-index)`が`usize_bytes`の倍数であれば`index`の位置がアラインであるとみなされ高速処理に入る。ただし、減算の結果が0を下回っても剰余を計算できるように、`-`演算子ではなく`wrapping_sub()`が使用されている。

`index`がアラインと重なる場合、`if`ブロック内の最初の`while`ループで、`index`が`block_end`に達するかASCII文字以外が検出されるまで、2つの`usize`の読み取りとASCII文字の有無の判定が繰り返される。`block_end`は`usize`を2つ読み取っても安全なように事前に計算された境界である。ループ内でなぜ2つずつ読み取るのか正確な理由は分からないが、`usize`のバイト数が4でアラインの間隔が8であるような動作環境を想定したものと思われる（単純にパフォーマンスのためかもしれない）。

ループ内の処理はC言語などの配列とポインタに関する知識がないと難しそうだが、各変数には以下のような値が設定されている。ポインタ演算の`+1`はバイト単位ではなく対象の型のサイズ単位で進むことに注意したい。

* `let ptr = v.as_ptr();`の`ptr`は、`v`（入力バイト列）の開始位置のアドレスの`u8`型ポインタ
* `let block = ptr.add(index) as *const usize;`の`block`は、`v[index]`のアドレスの`usize`型ポインタ
* `*block`は`block`ポインタから読み取れる`usize`値
* `let zu = contains_nonascii(*block);`の`zu`は、その値がASCII文字以外を含むか否かの真偽値
* `block.offset(1)`は`block`から`usize`1つ分だけ進めたアドレスの`usize`型ポインタ
* `let zv = contains_nonascii(*block.offset(1));`の`zv`は、そのポインタから読み取れる`usize`値がASCII文字以外を含むか否かの真偽値

途中で使用された`contains_nonascii()`は以下のように実装されている。

```rust
// use truncation to fit u64 into usize
const NONASCII_MASK: usize = 0x80808080_80808080u64 as usize;

/// Returns `true` if any byte in the word `x` is nonascii (>= 128).
#[inline]
fn contains_nonascii(x: usize) -> bool {
    (x & NONASCII_MASK) != 0
}
```

この関数のビット演算を2進数表記で表すと以下のようになり、結果が0になればすべてのバイトがASCII文字（`0*******`）、どこかに1が残れば（`!= 0`ならば）いずれかのバイトがASCII文字以外だとわかる。なお、この判定では数値のバイトオーダー（エンディアン）は影響しない。

```
（usizeが4バイトの場合）
    w*******_x*******_y*******_z*******  (x)
  & 10000000_10000000_10000000_10000000  (NONASCII_MASK)
  -------------------------------------
    w0000000_x0000000_y0000000_z0000000
```

以上で、全体走査によるUTF-8検証処理の内容は一通り網羅した。

## 部分文字列（スライス）取得時の検証処理

既に有効なUTF-8と分かっている`str`値から部分文字列を取得するときは、前節のように全体を走査する検証は必要ない。切断する箇所で開始バイトと継続バイトが分断されないことを確認すれば、部分文字列も有効なUTF-8になることが保証されるからである。このため、範囲`start..end`の部分文字列を取得する時のUTF-8検証では、`start`と`end`の位置が継続バイト（`10******`）でないことだけをチェックしている。

以下は`Range`（`start..end`）に対する`str`型のスライス取得処理の実装（一部）である。`get()`の中の`str::is_char_boundary()`によって、`start`と`end`の位置が開始バイトであること（継続バイトでないこと）を確認している。

```rust
    impl SliceIndex<str> for ops::Range<usize> {
        type Output = str;
        #[inline]
        fn get(self, slice: &str) -> Option<&Self::Output> {
            if self.start <= self.end
                && slice.is_char_boundary(self.start)
                && slice.is_char_boundary(self.end)
            {
                // SAFETY: just checked that `start` and `end` are on a char boundary.
                Some(unsafe { self.get_unchecked(slice) })
            } else {
                None
            }
        }
        ...
        #[inline]
        unsafe fn get_unchecked(self, slice: &str) -> &Self::Output {
            // SAFETY: the caller guarantees that `self` is in bounds of `slice`
            // which satisfies all the conditions for `add`.
            let ptr = unsafe { slice.as_ptr().add(self.start) };
            let len = self.end - self.start;
            // SAFETY: ...
            unsafe { super::from_utf8_unchecked(slice::from_raw_parts(ptr, len)) }
        }
        ...
    }
```

なお`str::is_char_boundary()`は`str`の公開関数で、こちらもマニアックな実装がされている。興味がある方は調べてみてほしい。

以上のように、部分文字列を取得する際のUTF-8検証は境界部分しかチェックしないため、文字列の長さによって処理が重くなることはない。したがって、パフォーマンスの観点では`get()`／`get_unchecked()`の使い分けの重要性は`from_utf8()`／`from_utf8_unchecked()`に比べれば小さくなる（使用頻度にもよるが）。ただし、何らかの理由で`str`に不正なUTF-8が混入していた場合、部分文字列を取得する時のUTF-8検証では見逃される可能性が高いことには注意したい。

# まとめ

* RustのUTF-8検証は必要最小限のチェックのみ行う。
* バイト列全体のUTF-8検証は効率化のための工夫が色々と施されている。
* 部分文字列（スライス）取得時のUTF-8検証は軽い。

誤字、脱字、内容の誤りや不備などがありましたらコメント頂けると助かります。