utf8としてvalidなバイト列を判定する方法をGoから見る

以前ソースコードを読んでいておもしろかったのでメモしておきます。Go1.8のコードを見ていますが、そんなに大きく変更されることは無いと思います。

Go言語のunicode/utf8パッケージのutf8.Valid関数の実装を見ていきます。Validであることを確認することでutf8の文字列として文字数がいくつかも分かるので、文字数についても触れていきます。utf8.RuneCount関数もほぼ同じ実装なので、このコードが読めれば、こちらのコードもすぐに分かると思います。

go/utf8.go at master · golang/go

const (
    RuneSelf  = 0x80         // characters below Runeself are represented as themselves in a single byte.
)

func Valid(p []byte) bool {
    n := len(p)
    for i := 0; i < n; {
        pi := p[i]
        if pi < RuneSelf {
            i++
            continue
        }
        x := first[pi]
        if x == xx {
            return false
        }
        size := int(x & 7)
        if i+size > n {
            return false
        }
        accept := acceptRanges[x>>4]
        if c := p[i+1]; c < accept.lo || accept.hi < c {
            return false
        } else if size == 2 {
        } else if c := p[i+2]; c < locb || hicb < c {
            return false
        } else if size == 3 {
        } else if c := p[i+3]; c < locb || hicb < c {
            return false
        }
        i += size
    }
    return true
}

1つ1つ説明していきます。

utf8はASCIIコードと互換性を保っていることは知っていると思います。つまりASCIIコードが使用している領域はutf8でも1文字としてValidです。そのためASCIIコードが使用している0x00-0x7Fは『utf8としてValidであり、1バイトで1文字分ということになります』。RuneSelf = 0x80なのでそれより小さいバイト列ならValidなので1つ先に進めます。

次の処理でfirstという配列（スライスではない）にアクセスしています。英語版Wikipediaにある表とほぼ同じテーブルがあるのでこちらを見ると良いと思います。

UTF-8 - Wikipedia

const (
    // These names of these constants are chosen to give nice alignment in the
    // table below. The first nibble is an index into acceptRanges or F for
    // special one-byte cases. The second nibble is the Rune length or the
    // Status for the special one-byte case.
    xx = 0xF1 // invalid: size 1
    as = 0xF0 // ASCII: size 1
    s1 = 0x02 // accept 0, size 2
    s2 = 0x13 // accept 1, size 3
    s3 = 0x03 // accept 0, size 3
    s4 = 0x23 // accept 2, size 3
    s5 = 0x34 // accept 3, size 4
    s6 = 0x04 // accept 0, size 4
    s7 = 0x44 // accept 4, size 4
)

// first is information about the first byte in a UTF-8 sequence.
var first = [256]uint8{
    //   1   2   3   4   5   6   7   8   9   A   B   C   D   E   F
    as, as, as, as, as, as, as, as, as, as, as, as, as, as, as, as, // 0x00-0x0F
    as, as, as, as, as, as, as, as, as, as, as, as, as, as, as, as, // 0x10-0x1F
    as, as, as, as, as, as, as, as, as, as, as, as, as, as, as, as, // 0x20-0x2F
    as, as, as, as, as, as, as, as, as, as, as, as, as, as, as, as, // 0x30-0x3F
    as, as, as, as, as, as, as, as, as, as, as, as, as, as, as, as, // 0x40-0x4F
    as, as, as, as, as, as, as, as, as, as, as, as, as, as, as, as, // 0x50-0x5F
    as, as, as, as, as, as, as, as, as, as, as, as, as, as, as, as, // 0x60-0x6F
    as, as, as, as, as, as, as, as, as, as, as, as, as, as, as, as, // 0x70-0x7F
    //   1   2   3   4   5   6   7   8   9   A   B   C   D   E   F
    xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, // 0x80-0x8F
    xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, // 0x90-0x9F
    xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, // 0xA0-0xAF
    xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, // 0xB0-0xBF
    xx, xx, s1, s1, s1, s1, s1, s1, s1, s1, s1, s1, s1, s1, s1, s1, // 0xC0-0xCF
    s1, s1, s1, s1, s1, s1, s1, s1, s1, s1, s1, s1, s1, s1, s1, s1, // 0xD0-0xDF
    s2, s3, s3, s3, s3, s3, s3, s3, s3, s3, s3, s3, s3, s4, s3, s3, // 0xE0-0xEF
    s5, s6, s6, s6, s7, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, xx, // 0xF0-0xFF
}

このテーブルでxxとされている領域はマルチバイト文字の1バイト目には出現しないバイト列です。なのでxxであることが分かった時点でValidではなくなります。xxでなければ後続のバイト列次第でValidかどうかが決まります。

そしてutf8には以下の非常にうれしい特徴があります。

• マルチバイト文字の1バイト目を見ればバイト列の長さと後続のバイト列が分かる
  • 上のテーブルにその情報が入っている。詳しくは後述
• マルチバイト文字の1バイト目は他の位置に現れない
  • つまり後続のバイト列は上のテーブルのxxの範囲（実際の範囲は後述）の中にある
  • この特徴によってバイト列の途中から見た場合でも文字の区切りを間違えない

そして上のテーブルには以下の2つの情報が入っています。

• サイズ
• 後続のバイトの範囲

サイズは下位8bitに入っているので size := int(x & 7) で取り出しています。後続のバイトの範囲はバイトの範囲を表す構造体acceptRangeの配列acceptRangesという変数に入っています。acceptRangesのどれに該当するかが16進数で2桁目に入っていて、それより上は全部0なので x>>4 で取り出しています。

const (
    // The default lowest and highest continuation byte.
    locb = 0x80 // 1000 0000
    hicb = 0xBF // 1011 1111
)

// acceptRange gives the range of valid values for the second byte in a UTF-8
// sequence.
type acceptRange struct {
    lo uint8 // lowest value for second byte.
    hi uint8 // highest value for second byte.
}

var acceptRanges = [...]acceptRange{
    0: {locb, hicb},
    1: {0xA0, hicb},
    2: {locb, 0x9F},
    3: {0x90, hicb},
    4: {locb, 0x8F},
}

3バイトと4バイトの文字に関してはさらに後続のバイト列がありますが、以下の本の147ページの表とにらめっこすれば0x80-0xBFの範囲にあることは明白です。

プログラマのための文字コード技術入門 (WEB+DB PRESS plus) (WEB+DB PRESS plusシリーズ) | 矢野 啓介 |本 | 通販 | Amazon

この表以外でも非常に参考にした本なので非常にお勧めです。

またutf8の仕様的には6バイトまでありえますが、現在のunicodeの仕様ではutf16で表現できる範囲しか定義されないことになっているので4バイトまでしか存在しません。ということでこのコードで十分utf8としてValidな文字列か判定できます。