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
// 原始实现来自 rust-memchr。
// 版权所有 2015 Andrew Gallant,bluss 和 Nicolas Koch

use crate::cmp;
use crate::mem;

const LO_U64: u64 = 0x0101010101010101;
const HI_U64: u64 = 0x8080808080808080;

// 使用截断。
const LO_USIZE: usize = LO_U64 as usize;
const HI_USIZE: usize = HI_U64 as usize;
const USIZE_BYTES: usize = mem::size_of::<usize>();

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

#[cfg(target_pointer_width = "16")]
#[inline]
fn repeat_byte(b: u8) -> usize {
    (b as usize) << 8 | b as usize
}

#[cfg(not(target_pointer_width = "16"))]
#[inline]
fn repeat_byte(b: u8) -> usize {
    (b as usize) * (usize::MAX / 255)
}

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

    memchr_general_case(x, text)
}

fn memchr_general_case(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 {
        offset = cmp::min(offset, len);
        if let Some(index) = text[..offset].iter().position(|elt| *elt == x) {
            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;
    }

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

/// 返回与 `text` 中的字节 `x` 匹配的最后一个索引。
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.offset(offset as isize - 2 * chunk_bytes as isize) as *const Chunk);
            let v = *(ptr.offset(offset as isize - chunk_bytes as isize) 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)
}