1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
// 原始实现来自 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)
}