//! 用于有效计算 UTF-8 编码字符串中的 `char` 数量的代码。
//!
//! 广义上讲，UTF-8 将 `char` 编码为一个 "leading" 字节，它以 `char` 开头，后跟一些 (可能为 0) 的连续字节。
//!
//! 前导字节可以有多个位模式 (特定的模式指示后面有多少个延续字节)，但连续字节的格式始终为 `0b10XX_XXXX` 格式 (其中 `X` 可以取任何值)。
//! 也就是说，设置了最高有效位，未设置第二个最高有效位。
//!
//! 为了计算字符的数量，我们可以只计算字符串中非连续字节的字节数，这可以很容易地一次计算多个字节。
//!
//! Note: 因为术语 "leading byte" 有时可能是模棱两可的 (例如，它也可以指切片的第一个字节)，所以我们经常使用术语 "non-continuation byte" 来指代代码中的这些字节。
//!
//!
//!
//!
//!
//!
//!
//!
//!
use core::intrinsics::unlikely;

const USIZE_SIZE: usize = core::mem::size_of::<usize>();
const UNROLL_INNER: usize = 4;

#[inline]
pub(super) fn count_chars(s: &str) -> usize {
    if s.len() < USIZE_SIZE * UNROLL_INNER {
        // 避免输入字符串的优化实现，因为差异可能无关紧要，或者可能会更慢。
        //
        // 也就是说，除了 "这个值似乎有意义" 之外，没有花太多心思在这个特定的门槛上。
        //
        char_count_general_case(s.as_bytes())
    } else {
        do_count_chars(s)
    }
}

fn do_count_chars(s: &str) -> usize {
    // 为了正确起见，`CHUNK_SIZE` 必须是:
    //
    // - 小于或等于 255，否则我们将在 `counts` 中溢出字节。
    // - `UNROLL_INNER` 的倍数，否则我们在 `body.chunks(CHUNK_SIZE)` 循环里面的 `break` 是不正确的。
    //
    //
    // 对于性能，`CHUNK_SIZE` 应该是:
    // - 相对于 `/` 来说相对便宜 (所以一些简单的 2 次方之和)。
    // - 足够大，可以避免过于频繁地支付 `sum_bytes_in_usize` 的费用。
    //
    const CHUNK_SIZE: usize = 192;

    // 检查正确性所需的 `CHUNK_SIZE` 和 `UNROLL_INNER` 的属性。
    //
    const _: () = assert!(CHUNK_SIZE < 256);
    const _: () = assert!(CHUNK_SIZE % UNROLL_INNER == 0);

    // SAFETY: 将 `[u8]` 转换为 `[usize]` 是安全的，但 `align_to` 处理的大小差异除外。
    //
    let (head, body, tail) = unsafe { s.as_bytes().align_to::<usize>() };

    // 这应该是非常罕见的，并且基本上存在处理 align_to 失败的退化情况 (以及符号对齐模式下的 miri )。
    //
    // `unlikely` 有助于阻止 LLVM 内联主体，这很好，因为我们宁愿不将 `char_count_general_case` 函数标记为冷。
    //
    //
    //
    //
    if unlikely(body.is_empty() || head.len() > USIZE_SIZE || tail.len() > USIZE_SIZE) {
        return char_count_general_case(s.as_bytes());
    }

    let mut total = char_count_general_case(head) + char_count_general_case(tail);
    // 将 `body` 拆分为 `CHUNK_SIZE` 块以减少调用 `sum_bytes_in_usize` 的频率。
    //
    for chunk in body.chunks(CHUNK_SIZE) {
        // 我们在 `counts` 中累积中间和，其中每个字节包含这个块的总和的子集，就像 `[u8; size_of::<usize>()]`。
        //
        let mut counts = 0;

        let (unrolled_chunks, remainder) = chunk.as_chunks::<UNROLL_INNER>();
        for unrolled in unrolled_chunks {
            for &word in unrolled {
                // 因为 `CHUNK_SIZE` < 256，所以这个加法不会导致任何字节中的计数溢出到后续字节中。
                //
                counts += contains_non_continuation_byte(word);
            }
        }

        // 对 `counts` 中的值求和 (同样，它在概念上是一个 `[u8;
        // size_of::<usize>()]`)，并将结果累加到 `total` 中。
        total += sum_bytes_in_usize(counts);

        // 如果 `remainder` 中有数据，则进行处理。
        // 这只会发生在 `body.chunks()` 中的最后一个 `chunk` 上 (因为 `CHUNK_SIZE` 可以被 `UNROLL_INNER` 整除)，所以我们在最后显式中断 (这似乎有助于 LLVM)。
        //
        //
        if !remainder.is_empty() {
            // 将余数中的所有数据累加。
            let mut counts = 0;
            for &word in remainder {
                counts += contains_non_continuation_byte(word);
            }
            total += sum_bytes_in_usize(counts);
            break;
        }
    }
    total
}

// 检查 `w` 的每个字节以查看它是否包含 UTF-8 序列中的第一个字节。
// `w` 中作为连续字节的字节保留为 `0x00` (例如
// false)，非连续字节的字节保留为 `0x01` (例如 true)
//
#[inline]
fn contains_non_continuation_byte(w: usize) -> usize {
    const LSB: usize = usize::repeat_u8(0x01);
    ((!w >> 7) | (w >> 6)) & LSB
}

// 道德上相当于 `values.to_ne_bytes().into_iter().sum::<usize>()`，但效率更高。
//
#[inline]
fn sum_bytes_in_usize(values: usize) -> usize {
    const LSB_SHORTS: usize = usize::repeat_u16(0x0001);
    const SKIP_BYTES: usize = usize::repeat_u16(0x00ff);

    let pair_sum: usize = (values & SKIP_BYTES) + ((values >> 8) & SKIP_BYTES);
    pair_sum.wrapping_mul(LSB_SHORTS) >> ((USIZE_SIZE - 2) * 8)
}

// 这是 "count the number of bytes in the string which are not continuation bytes" 概念最直接的实现，用于输入字符串的首尾 (`slice::align_to` 返回的元组中的第一个和最后一个项)。
//
//
//
fn char_count_general_case(s: &[u8]) -> usize {
    s.iter().filter(|&&byte| !super::validations::utf8_is_cont_byte(byte)).count()
}