// 原始实现来自 rust-memchr。
// 版权所有 2015 Andrew Gallant，bluss 和 Nicolas Koch

use crate::mem;

const LO_USIZE: usize = usize::repeat_u8(0x01);
const HI_USIZE: usize = usize::repeat_u8(0x80);
const USIZE_BYTES: usize = mem::size_of::<usize>();

/// 如果 `x` 包含任何零字节，则返回 `true`。
///
/// 从 *Matters 计算*，J. Arndt:
///
/// ` 这个想法是从每个字节中减去一个，然后寻找借用一直传播到最高有效位的字节。
///
/// bit."
#[inline]
#[rustc_const_stable(feature = "const_memchr", since = "1.65.0")]
const fn contains_zero_byte(x: usize) -> bool {
    x.wrapping_sub(LO_USIZE) & !x & HI_USIZE != 0
}

#[inline]
#[cfg(target_pointer_width = "16")]
#[rustc_const_stable(feature = "const_memchr", since = "1.65.0")]
const fn repeat_byte(b: u8) -> usize {
    (b as usize) << 8 | b as usize
}

#[inline]
#[cfg(not(target_pointer_width = "16"))]
#[rustc_const_stable(feature = "const_memchr", since = "1.65.0")]
const fn repeat_byte(b: u8) -> usize {
    (b as usize) * (usize::MAX / 255)
}

/// 返回与 `text` 中的字节 `x` 匹配的第一个索引。
#[inline]
#[must_use]
#[rustc_const_stable(feature = "const_memchr", since = "1.65.0")]
pub const fn memchr(x: u8, text: &[u8]) -> Option<usize> {
    // 小切片的快速路径。
    if text.len() < 2 * USIZE_BYTES {
        return memchr_naive(x, text);
    }

    memchr_aligned(x, text)
}

#[inline]
#[rustc_const_stable(feature = "const_memchr", since = "1.65.0")]
const fn memchr_naive(x: u8, text: &[u8]) -> Option<usize> {
    let mut i = 0;

    // FIXME(const-hack): 更换为 `text.iter().pos(|c| *c == x)`。
    while i < text.len() {
        if text[i] == x {
            return Some(i);
        }

        i += 1;
    }

    None
}

#[rustc_allow_const_fn_unstable(const_cmp)]
#[rustc_allow_const_fn_unstable(const_slice_index)]
#[rustc_allow_const_fn_unstable(const_align_offset)]
#[rustc_const_stable(feature = "const_memchr", since = "1.65.0")]
const fn memchr_aligned(x: u8, text: &[u8]) -> Option<usize> {
    // 通过一次读取两个 `usize` 字来扫描单个字节值。
    //
    // 将 `text` 分为三部分
    // - 未对齐的初始部分，在文本中第一个单词对齐的地址之前
    // - 身体，一次扫描 2 个字
    // - 最后剩下的部分，<2 字大小

    // 搜索到对齐的边界
    let len = text.len();
    let ptr = text.as_ptr();
    let mut offset = ptr.align_offset(USIZE_BYTES);

    if offset > 0 {
        // FIXME(const-hack, fee1-dead): 替换为最小值
        offset = if offset < len { offset } else { len };
        // FIXME(const-hack, fee1-dead): 替换为范围切片
        // SAFETY: 偏移量在范围内
        let slice = unsafe { super::from_raw_parts(text.as_ptr(), offset) };
        if let Some(index) = memchr_naive(x, slice) {
            return Some(index);
        }
    }

    // 搜索正文
    let repeated_x = repeat_byte(x);
    while offset <= len - 2 * USIZE_BYTES {
        // SAFETY: while 的谓词保证偏移量和切片末尾之间至少有 2 * usize_bytes 的距离。
        //
        unsafe {
            let u = *(ptr.add(offset) as *const usize);
            let v = *(ptr.add(offset + USIZE_BYTES) as *const usize);

            // 如果有匹配的字节则中断
            let zu = contains_zero_byte(u ^ repeated_x);
            let zv = contains_zero_byte(v ^ repeated_x);
            if zu || zv {
                break;
            }
        }
        offset += USIZE_BYTES * 2;
    }

    // 在主体循环停止的点之后找到字节。
    // FIXME(const-hack): 请改用 `?`。
    // FIXME(const-hack, fee1-dead): 使用范围切片
    // SAFETY: 偏移量在范围内
    let slice = unsafe { super::from_raw_parts(text.as_ptr().add(offset), text.len() - offset) };
    if let Some(i) = memchr_naive(x, slice) { Some(offset + i) } else { None }
}

/// 返回与 `text` 中的字节 `x` 匹配的最后一个索引。
#[must_use]
pub fn memrchr(x: u8, text: &[u8]) -> Option<usize> {
    // 通过一次读取两个 `usize` 字来扫描单个字节值。
    //
    // 将 `text` 分为三个部分：
    // - 未对齐的尾部，在文本中最后一个单词对齐的地址之后，
    // - 身体，一次扫描 2 个字，
    // - 剩余的前一个字节，<2 个字长。
    let len = text.len();
    let ptr = text.as_ptr();
    type Chunk = usize;

    let (min_aligned_offset, max_aligned_offset) = {
        // 我们称其为仅仅是获得前缀和后缀的长度。
        // 在中间，我们总是一次处理两个块。
        // SAFETY: 将 `[u8]` 转换为 `[usize]` 是安全的，但 `align_to` 处理的大小差异除外。
        //
        let (prefix, _, suffix) = unsafe { text.align_to::<(Chunk, Chunk)>() };
        (prefix.len(), len - suffix.len())
    };

    let mut offset = max_aligned_offset;
    if let Some(index) = text[offset..].iter().rposition(|elt| *elt == x) {
        return Some(offset + index);
    }

    // 搜索文本的正文，确保我们不跨越 min_aligned_offset。
    // 偏移量总是对齐的，因此仅测试 `>` 就足够了，并避免了可能的溢出。
    //
    let repeated_x = repeat_byte(x);
    let chunk_bytes = mem::size_of::<Chunk>();

    while offset > min_aligned_offset {
        // SAFETY: 偏移量从 len-suffix.len() 开始，只要大于 min_aligned_offset (prefix.len())，则剩余距离至少为 2 * chunk_bytes。
        //
        unsafe {
            let u = *(ptr.add(offset - 2 * chunk_bytes) as *const Chunk);
            let v = *(ptr.add(offset - chunk_bytes) as *const Chunk);

            // 如果有匹配的字节，则中断。
            let zu = contains_zero_byte(u ^ repeated_x);
            let zv = contains_zero_byte(v ^ repeated_x);
            if zu || zv {
                break;
            }
        }
        offset -= 2 * chunk_bytes;
    }

    // 在主体循环停止的点之前找到字节。
    text[..offset].iter().rposition(|elt| *elt == x)
}