// Copyright 2009 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// go/src/unicode/utf8/utf8.go
// version 1.7

// 關于 UTF-8 編碼方式請參考：http://www.cnblogs.com/golove/p/3222096.html

package utf8

// 編碼所需的基本數(shù)字
const (
    RuneError = '\uFFFD'     // 錯誤的 Rune 或 Unicode 代理字符
    RuneSelf  = 0x80         // ASCII 字符范圍
    MaxRune   = '\U0010FFFF' // Unicode 碼點的最大值
    UTFMax    = 4            // 一個字符編碼的最大長度
)

// Unicode 代理字符對 UTF-8 編碼而言是無效的。
const (
    surrogateMin = 0xD800
    surrogateMax = 0xDFFF
)

// 用詞說明：
// 單字節(jié)字符：該字符的 UTF-8 編碼需要一個字節(jié)存放
// 雙字節(jié)字符：該字符的 UTF-8 編碼需要兩個字節(jié)存放
// 三字節(jié)字符：該字符的 UTF-8 編碼需要三個字節(jié)存放
// 四字節(jié)字符：該字符的 UTF-8 編碼需要四個字節(jié)存放
// 字符首字節(jié)：某字符的 UTF-8 編碼中的第一個字節(jié)
// 字符次字節(jié)：某字符的 UTF-8 編碼中的第二個字節(jié)
// 字符后續(xù)字節(jié)：某字符的 UTF-8 編碼中首字節(jié)后面的其它字節(jié)

const (
    // 位標記（用于判斷字節(jié)有效性）
    t1 = 0x00 // 0000 0000 單字節(jié)字符的首字節(jié)標記（二進制以 0     開頭）
    tx = 0x80 // 1000 0000 所有字符的后續(xù)字節(jié)標記（二進制以 10    開頭）
    t2 = 0xC0 // 1100 0000 雙字節(jié)字符的首字節(jié)標記（二進制以 110   開頭）
    t3 = 0xE0 // 1110 0000 三字節(jié)字符的首字節(jié)標記（二進制以 1110  開頭）
    t4 = 0xF0 // 1111 0000 四字節(jié)字符的首字節(jié)標記（二進制以 11110 開頭）
    t5 = 0xF8 // 1111 1000 好像未使用

    // 位掩碼（用于獲取標記之外的二進制位）
    maskx = 0x3F // 0011 1111 所有字符的后續(xù)字節(jié)掩碼
    mask2 = 0x1F // 0001 1111 雙字節(jié)字符的首字節(jié)掩碼
    mask3 = 0x0F // 0000 1111 三字節(jié)字符的首字節(jié)掩碼
    mask4 = 0x07 // 0000 0111 四字節(jié)字符的首字節(jié)掩碼

    rune1Max = 1<<7 - 1  // 單字節(jié)字符的總數(shù)（127   個）
    rune2Max = 1<<11 - 1 // 雙字節(jié)字符的總數(shù)（2047  個）
    rune3Max = 1<<16 - 1 // 三字節(jié)字符的總數(shù)（65535 個）

    // UTF-8 字符的后續(xù)字節(jié)的一般取值范圍
    locb = 0x80 // 1000 0000
    hicb = 0xBF // 1011 1111

    // 字符首字節(jié)分類標記潮售，用于將所有的字符首字節(jié)分成下面九類痊项，分別處理。
    // 以下十六進制常量的高位和低位分別表示不同的含義：
    // 高位：“次字節(jié)取值范圍列表”的索引饲做，如果高位是 F 則表示字符是單字節(jié)字符
    // 低位：字符的編碼長度线婚，如果高位是 F 則低位表示單字節(jié)字符的狀態(tài)：有效遏弱、無效
    xx = 0xF1 // 無索引盆均，長度 1，對應無效 UTF-8 編碼
    as = 0xF0 // 無索引漱逸，長度 1泪姨，對應普通 ASCII 字符
    s1 = 0x02 // 索引 0, 長度 2游沿，對應普通“雙字節(jié)字符”的首字節(jié)
    s2 = 0x13 // 索引 1, 長度 3，對應特殊“雙字節(jié)字符”的首字節(jié) 0xE0（用于編碼長度跨越）
    s3 = 0x03 // 索引 0, 長度 3肮砾，對應普通“三字節(jié)字符”的首字節(jié)
    s4 = 0x23 // 索引 2, 長度 3诀黍，對應特殊“三字節(jié)字符”的首字節(jié) 0xED（用于代理區(qū)檢測）
    s5 = 0x34 // 索引 3, 長度 4，對應特殊“四字節(jié)字符”的首字節(jié) 0xF0（用于編碼長度跨越）
    s6 = 0x04 // 索引 0, 長度 4仗处，對應普通“四字節(jié)字符”的首字節(jié)
    s7 = 0x44 // 索引 4, 長度 4眯勾，對應特殊“四字節(jié)字符”的首字節(jié) 0xF4（用于范圍檢測）
)

// first 是關于 UTF-8 字符中首字節(jié)的編碼信息。
// 將所有的首字節(jié)進行分類婆誓，分為：xx吃环、as、s1洋幻、s2郁轻、s3、s4文留、s5好唯、s6、s7 九類燥翅，
// 其中 xx 代表無效首字節(jié)骑篙，s1 代表雙字節(jié)字符的首字節(jié)
// s2、s3森书、s4 代表三字節(jié)字符的首字節(jié)
// s5替蛉、s6、a7 代表四字節(jié)字符的首字節(jié)
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
}

// acceptRange 給出次字節(jié)的取值范圍拄氯。
type acceptRange struct {
    lo uint8 // 次字節(jié)最小取值
    hi uint8 // 次字節(jié)最大取值
}

// 不同的首字節(jié)字符有不同的次字節(jié)取值范圍躲查，
// UTF-8 編碼編不出這些范圍之外的次字節(jié)內容。
var acceptRanges = [...]acceptRange{
    // 普通字符的次字節(jié)译柏，范圍之外為無效編碼（即二進制位不是以 10 開頭）
    0: {locb, hicb},
    // 三字節(jié)特殊字符（首字節(jié)為 0xE0）的次字節(jié)：
    // 如果次字節(jié)低于 0xA0 則該字符應該用兩個字節(jié)表示镣煮，而不是三個字節(jié)。
    // 如果次字節(jié)高于 hicb 則該字節(jié)為無效編碼（即二進制位不是以 10 開頭）
    1: {0xA0, hicb},
    // 三字節(jié)特殊字符（首字節(jié)為 0xED）的次字節(jié)：
    // 如果次字節(jié)低于 locb 則該字節(jié)為無效編碼（即二進制位不是以 10 開頭）
    // 如果次字節(jié)高于 0x9F 則該字符為代理區(qū)字符（[ED A0 80] - [ED BF BF]）
    2: {locb, 0x9F},
    // 四字節(jié)特殊字符（首字節(jié)為 0xF0）的次字節(jié)：
    // 如果次字節(jié)低于 0x90 則該字符應該用三個字節(jié)表示鄙麦，而不是四個字節(jié)典唇。
    // 如果次字節(jié)高于 hicb 則該字節(jié)為無效編碼（即二進制位不是以 10 開頭）
    3: {0x90, hicb},
    // 四字節(jié)特殊字符（首字節(jié)為 0xF4）的次字節(jié)：
    // 如果次字節(jié)低于 locb 則該字節(jié)為無效編碼（即二進制位不是以 10 開頭）
    // 如果次字節(jié)高于 0x8F 則該字符超出 Unicode 范圍（超出 MaxRune）
    4: {locb, 0x8F},

    // 相鄰字符的編碼長度跨越：

    // [11011111 10111111]          [DF BF]    // U+07FF 的后一個字符為三字節(jié)
    // [11100000 10100000 10000000] [E0 A0 80] // U+0800 的前一個字符為兩字節(jié)

    // [11101111 10111111 10111111]          [EF BF BF]    // U+FFFF  的后一個字符為四字節(jié)
    // [11110000 10010000 10000000 10000000] [F0 90 80 80] // U+10000 的前一個字符為三字節(jié)
}

// FullRune 判斷 p 是否以一個完整（但不一定有效）的 UTF-8 字符開頭。
// 一個無效的編碼也被認為是完整字符胯府，因為它將被轉換為一個 RuneError 字符介衔。
// 只有“編碼有效但長度不夠”的字符才被認為是不完整字符。
// 也就是說骂因，只有截去一個有效字符的一個或多個后續(xù)字節(jié)炎咖，該字符才算是不完整字符。
// 舉例：
// "好"     是完整字符
// "好"[1:] 是完整字符（首字節(jié)無效，轉換為 RuneError 字符）
// "好"[2:] 是完整字符（首字節(jié)無效乘盼，轉換為 RuneError 字符）
// "好"[:2] 是不完整字符（編碼有效但長度不夠）
// "好"[:1] 是不完整字符（編碼有效但長度不夠）
func FullRune(p []byte) bool {
    n := len(p)
    if n == 0 {
        return false
    }
    // 查表并計算升熊，獲取編碼長度，判斷 p 的長度是否滿足編碼長度
    x := first[p[0]]
    if n >= int(x&7) { // x&7 獲取的就是編碼長度
        // p 的長度滿足編碼長度绸栅，表示 p 是一個完整的字符開頭级野。
        return true
    }

    // 此時 p 的長度不夠，應該是不完整的字符了粹胯，但是如果 p 中是無效編碼蓖柔，也算完整。
    // 此時 n 肯定小于 4风纠，否則長度不可能不夠渊抽。

    // 獲取首字節(jié)對應的次字節(jié)有效范圍
    accept := acceptRanges[x>>4]
    if n > 1 {
        if c := p[1]; c < accept.lo || accept.hi < c {
            // 有一個無效字節(jié)，算完整字符
            return true
        } else if n > 2 && (p[2] < locb || hicb < p[2]) {
            // 有一個無效字節(jié)议忽，算完整字符
            return true
        }
    }
    // 全是有效字節(jié)懒闷，但長度不夠，算不完整
    return false
}

// 功能同 FullRune栈幸，只不過參數(shù)為字符串愤估。
func FullRuneInString(s string) bool {
    n := len(s)
    if n == 0 {
        return false
    }
    x := first[s[0]]
    if n >= int(x&7) {
        return true
    }
    accept := acceptRanges[x>>4]
    if n > 1 {
        if c := s[1]; c < accept.lo || accept.hi < c {
            return true
        } else if n > 2 && (s[2] < locb || hicb < s[2]) {
            return true
        }
    }
    return false
}

// 解碼 UTF-8 序列 p 中的第一個 Unicode 字符。
// r   ：解碼出的字符
// size：該字符的 UTF-8 編碼長度
// 如果 p 為空速址，則返回 RuneError, 0
// 如果 p 為無效的 UTF-8 編碼玩焰，則返回 RuneError, 1
// 無效 UTF-8 編碼：UTF-8 編碼不正確（比如長度不夠）、結果超出 Unicode 范圍芍锚、
// 編碼不是最短的昔园。
// 可以用四個字節(jié)編碼一個單字節(jié)字符，但它不是最短的并炮，比如：
// [111100000 10000000 10000000 10111000] 不是最短的默刚，應該使用 [00111000]
func DecodeRune(p []byte) (r rune, size int) {
    n := len(p)
    if n < 1 {
        return RuneError, 0
    }
    // 處理單字節(jié)字符
    p0 := p[0]
    x := first[p0]
    if x >= as { // x 為 F0 或 F1
        // 生成 0x0000 或 0xFFFF
        mask := rune(x) << 31 >> 31
        // return 保留 ASCII 字符 | 保留 RuneError, 1
        return rune(p[0])&^mask | RuneError&mask, 1
    }

    // 處理多字節(jié)字符

    // 獲取編碼長度
    sz := x & 7
    // 獲取次字節(jié)有效范圍
    accept := acceptRanges[x>>4]
    // p 長度不夠
    if n < int(sz) {
        return RuneError, 1
    }

    // p 長度滿足

    // 次字節(jié)編碼有效
    b1 := p[1]
    if b1 < accept.lo || accept.hi < b1 {
        return RuneError, 1
    }
    // 處理有效的雙字節(jié)字符
    if sz == 2 {
        return rune(p0&mask2)<<6 | rune(b1&maskx), 2
    }
    // 超過雙字節(jié)，第三字節(jié)編碼有效
    b2 := p[2]
    if b2 < locb || hicb < b2 {
        return RuneError, 1
    }
    // 處理有效的三字節(jié)字符
    if sz == 3 {
        return rune(p0&mask3)<<12 | rune(b1&maskx)<<6 | rune(b2&maskx), 3
    }
    // 超過三字節(jié)逃魄，第四字節(jié)編碼有效
    b3 := p[3]
    if b3 < locb || hicb < b3 {
        return RuneError, 1
    }
    // 處理有效的四字節(jié)字符
    return rune(p0&mask4)<<18 | rune(b1&maskx)<<12 | rune(b2&maskx)<<6 | rune(b3&maskx), 4
}

// 功能同 DecodeRune荤西，只不過參數(shù)為字符串
func DecodeRuneInString(s string) (r rune, size int) {
    n := len(s)
    if n < 1 {
        return RuneError, 0
    }
    s0 := s[0]
    x := first[s0]
    if x >= as {
        mask := rune(x) << 31 >> 31
        return rune(s[0])&^mask | RuneError&mask, 1
    }
    sz := x & 7
    accept := acceptRanges[x>>4]
    if n < int(sz) {
        return RuneError, 1
    }
    s1 := s[1]
    if s1 < accept.lo || accept.hi < s1 {
        return RuneError, 1
    }
    if sz == 2 {
        return rune(s0&mask2)<<6 | rune(s1&maskx), 2
    }
    s2 := s[2]
    if s2 < locb || hicb < s2 {
        return RuneError, 1
    }
    if sz == 3 {
        return rune(s0&mask3)<<12 | rune(s1&maskx)<<6 | rune(s2&maskx), 3
    }
    s3 := s[3]
    if s3 < locb || hicb < s3 {
        return RuneError, 1
    }
    return rune(s0&mask4)<<18 | rune(s1&maskx)<<12 | rune(s2&maskx)<<6 | rune(s3&maskx), 4
}

// 功能同 DecodeRune，只不過解碼的是最后一個字符伍俘。
func DecodeLastRune(p []byte) (r rune, size int) {
    end := len(p)
    if end == 0 {
        return RuneError, 0
    }
    // 處理 p 的最后一個字節(jié)
    start := end - 1
    r = rune(p[start])
    if r < RuneSelf { // 單字節(jié)字符直接返回
        return r, 1
    }
    // 一次最多遍歷 4 個字節(jié)邪锌，避免因無效 UTF8 編碼造成的過度循環(huán)
    lim := end - UTFMax
    if lim < 0 {
        lim = 0
    }
    // 按字節(jié)反向遍歷
    for start--; start >= lim; start-- {
        if RuneStart(p[start]) { // 遇到首字節(jié)編碼即可
            break
        }
    }
    // 遍歷完了也沒遇到首字節(jié)，則解碼整個 p
    if start < 0 {
        start = 0
    }
    r, size = DecodeRune(p[start:end])
    // 遇到無效編碼癌瘾，則只將最后一個字節(jié)解碼為 RuneError
    if start+size != end {
        return RuneError, 1
    }
    // 解碼成功
    return r, size
}

// 功能同 DecodeLastRune觅丰，只不過參數(shù)為字符串
func DecodeLastRuneInString(s string) (r rune, size int) {
    end := len(s)
    if end == 0 {
        return RuneError, 0
    }
    start := end - 1
    r = rune(s[start])
    if r < RuneSelf {
        return r, 1
    }
    lim := end - UTFMax
    if lim < 0 {
        lim = 0
    }
    for start--; start >= lim; start-- {
        if RuneStart(s[start]) {
            break
        }
    }
    if start < 0 {
        start = 0
    }
    r, size = DecodeRuneInString(s[start:end])
    if start+size != end {
        return RuneError, 1
    }
    return r, size
}

// RuneLen 返回 r 的 UTF-8 編碼所占用的字節(jié)數(shù)。
// 如果 r 不是一個有效的值（代理區(qū)或超出范圍）妨退，則返回 -1妇萄。
func RuneLen(r rune) int {
    switch {
    case r < 0: // 超出范圍
        return -1
    case r <= rune1Max: // 單字節(jié)字符范圍
        return 1
    case r <= rune2Max: // 雙字節(jié)字符范圍
        return 2
    case surrogateMin <= r && r <= surrogateMax: // 代理區(qū)范圍
        return -1
    case r <= rune3Max: // 三字節(jié)字符范圍
        return 3
    case r <= MaxRune: // 四字節(jié)字符范圍
        return 4
    }
    return -1 // 超出范圍
}

// EncodeRune 將 r 編碼為 UTF-8 序列蜕企，結果寫入 p 中（p 必須足夠長，一般為 4）
// 返回寫入的字節(jié)數(shù)
func EncodeRune(p []byte, r rune) int {
    // 負數(shù)是錯誤的嚣伐，將其轉換為無符號數(shù)糖赔，以使其超出范圍萍丐，進而處理掉這個錯誤轩端。
    switch i := uint32(r); {
    case i <= rune1Max: // 單字節(jié)字符
        p[0] = byte(r)
        return 1
    case i <= rune2Max: // 雙字節(jié)字符
        p[0] = t2 | byte(r>>6)
        p[1] = tx | byte(r)&maskx
        return 2
    // 超出范圍或代理區(qū)字符
    case i > MaxRune, surrogateMin <= i && i <= surrogateMax:
        r = RuneError
        fallthrough
    case i <= rune3Max: // 三字節(jié)字符
        p[0] = t3 | byte(r>>12)
        p[1] = tx | byte(r>>6)&maskx
        p[2] = tx | byte(r)&maskx
        return 3
    default: // 四字節(jié)字符
        p[0] = t4 | byte(r>>18)
        p[1] = tx | byte(r>>12)&maskx
        p[2] = tx | byte(r>>6)&maskx
        p[3] = tx | byte(r)&maskx
        return 4
    }
}

// RuneCount 返回 p 中的字符數(shù)（不是字節(jié)數(shù)）
// 錯誤的和長度無效的編碼中的每一個字節(jié)都會被當做一個字符處理。
// RuneError 被視為一個字符
func RuneCount(p []byte) int {
    np := len(p)
    var n int
    for i := 0; i < np; {
        n++
        c := p[i]
        if c < RuneSelf {
            i++ // 單字節(jié)字符
            continue
        }
        // 查表判斷首字節(jié)的有效性
        x := first[c]
        if x == xx {
            i++ // 首字節(jié)無效逝变，字節(jié)當做一個字符處理
            continue
        }
        // 首字節(jié)有效
        size := int(x & 7)
        if i+size > np {
            i++ // 但長度不足基茵，字節(jié)當做一個字符處理
            continue
        }
        // 首字節(jié)有效，長度也夠壳影，判斷后續(xù)字節(jié)的有效性
        accept := acceptRanges[x>>4]
        if c := p[i+1]; c < accept.lo || accept.hi < c { // 次字節(jié)無效
            size = 1
        } else if size == 2 { // 次字節(jié)有效拱层，長度剛好為 2
        } else if c := p[i+2]; c < locb || hicb < c { // 第三字節(jié)無效
            size = 1
        } else if size == 3 { // 第三字節(jié)也有效，長度剛好為 3
        } else if c := p[i+3]; c < locb || hicb < c { // 第四字節(jié)無效
            size = 1
        } // 第四字節(jié)也有效宴咧，長度不是 1根灯、2、3掺栅，肯定為 4（size == 4）
        i += size
    }
    return n
}

// 功能同 RuneCount烙肺，只不過參數(shù)為字符串
func RuneCountInString(s string) (n int) {
    ns := len(s)
    for i := 0; i < ns; n++ {
        c := s[i]
        if c < RuneSelf {
            i++
            continue
        }
        x := first[c]
        if x == xx {
            i++
            continue
        }
        size := int(x & 7)
        if i+size > ns {
            i++
            continue
        }
        accept := acceptRanges[x>>4]
        if c := s[i+1]; c < accept.lo || accept.hi < c {
            size = 1
        } else if size == 2 {
        } else if c := s[i+2]; c < locb || hicb < c {
            size = 1
        } else if size == 3 {
        } else if c := s[i+3]; c < locb || hicb < c {
            size = 1
        }
        i += size
    }
    return n
}

// RuneStart 判斷 b 是否為 UTF-8 字符編碼的首字節(jié)（有可能是無效字節(jié)）。
// UTF-8 編碼的后續(xù)字節(jié)的二進制位都是以 10 開始的氧卧。
func RuneStart(b byte) bool { return b&0xC0 != 0x80 }

// Valid 判斷 p 是否完全由有效的 UTF-8 編碼組成桃笙。
func Valid(p []byte) bool {
    // 代碼同 RuneCount 類似
    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
}

// 功能同 Valid，只不過參數(shù)為字符串
func ValidString(s string) bool {
    n := len(s)
    for i := 0; i < n; {
        si := s[i]
        if si < RuneSelf {
            i++
            continue
        }
        x := first[si]
        if x == xx {
            return false
        }
        size := int(x & 7)
        if i+size > n {
            return false
        }
        accept := acceptRanges[x>>4]
        if c := s[i+1]; c < accept.lo || accept.hi < c {
            return false
        } else if size == 2 {
        } else if c := s[i+2]; c < locb || hicb < c {
            return false
        } else if size == 3 {
        } else if c := s[i+3]; c < locb || hicb < c {
            return false
        }
        i += size
    }
    return true
}

// ValidRune 判斷 r 是否可以被編碼成 UTF-8 序列沙绝。
// 代理區(qū)字符或超出范圍則返回 false搏明。
func ValidRune(r rune) bool {
    switch {
    case r < 0: // 超出范圍
        return false
    case surrogateMin <= r && r <= surrogateMax: // 代理區(qū)字符
        return false
    case r > MaxRune: // 超出范圍
        return false
    }
    return true
}