SIMD 加速字符串查找（strchr / strstr）系统指南

目录

本篇在 Wojciech Mula “SIMD string find” 思路基础上编写。参考原文链接: http://0x80.pl/notesen/2016-11-28-simd-strfind.html

1. 速览（TL;DR）

  1. strchr: 并行比较目标字符与 NUL；movemask 压缩成位；tzcnt 得到首匹配位；比较字符位与 NUL 位决定返回指针/NULL。
  2. strstr(前缀过滤): 用前两字节 p0/p1 建两个掩码 m0/m1；候选 = m0 & (m1 >> 1)；逐候选 memcmp 验证；出现 NUL 截断。
  3. 跨块: 候选计算需处理“块末字节 + 下块首字节”连接；用 carry 或简单重叠扫描避免漏匹配。
  4. 页边界: 计算 remain = 4096 - (addr & 4095)，不足向量宽退回标量，防止非映射页 SIGSEGV。
  5. 性能核心: 少分支、批量比较、位运算筛选、按需 memcmp；根据 CPU 特性派发 SSE2/AVX2/AVX-512 版本。

2. 章节导航

  1. 原理总览：并行比较→位掩码→定位首匹配。
  2. strchr 流程（精简可视化）。
  3. strstr 双字节前缀过滤与候选生成。
  4. 跨块与页边界安全。
  5. 参考实现与接口说明（SSE2 / AVX2）。
  6. 性能要点与常见陷阱。
  7. 可视化/调试辅助工具。
  8. 速查总结表。

3. 1. 原理总览

核心数据流（适用于 strchr 与前缀过滤第一阶段）：

  • 非对齐加载 16/32/64 字节块。
  • 广播常量：单字符 c 与 0，或前缀 p0/p1。
  • 向量比较：eq(c)/eq(0)/eq(p0)/eq(p1)。
  • movemask：把每字节结果最高位压缩为位掩码（宽度 16/32/64 位）。
  • 位运算：
    • strchr: 比较 mc 与 m0 的首个 1 的位置。
    • strstr: cand = m0 & (m1 >> 1)（跨块加 carry）。
  • tzcnt/bsf：O(1) 找最低位 1 的索引（首匹配）。
  • 精确验证（strstr 第二阶段）：对候选位置执行 memcmp。

优点：减少分支、提升带宽利用、将遍历与判断分离（先生成位集，再逐候选验证）。

术语统一：

  • 块(block)：一次向量加载的宽度。
  • 掩码(mask)：movemask 得到的位图。
  • 候选(candidate)：可能匹配起点的位。
  • carry：跨两个块边界的前缀匹配衔接信息。
  • 页(page)：内存分页（通常 4KB）。

下文所有示例默认 SSE2（16 字节块），其它宽度思想一致。

4. 2. strchr 流程（示例精简）

4.1. 场景设定

我们要在字符串 "hello world" 中查找字符 'o'。

4.2. 步骤 0: 广播与零向量

目标字符:  'o' (ASCII 111, 0x6F)

广播到 128 位向量（16 字节）:
┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ o │ o │ o │ o │ o │ o │ o │ o │ o │ o │ o │ o │ o │ o │ o │ o │
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
C 代码: const __m128i vc = _mm_set1_epi8('o');

零向量（用于检测 NUL 终止符）:
┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
│ 0 │ 0 │ 0 │ 0 │ 0 │ 0 │ 0 │ 0 │ 0 │ 0 │ 0 │ 0 │ 0 │ 0 │ 0 │ 0 │
└───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
C 代码: const __m128i vz = _mm_setzero_si128();

4.3. 步骤 1: 非对齐加载文本块

内存布局（假设字符串起始地址 0x1000）:
地址:     0x1000 0x1001 0x1002 0x1003 0x1004 0x1005 0x1006 0x1007 ...
         ┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
内容:    │  h  │  e  │  l  │  l  │  o  │  _  │  w  │  o  │  r  │  l  │  d  │  \0 │  ?  │  ?  │  ?  │  ?  │
         └─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘
字节位置:   0     1     2     3     4     5     6     7     8     9    10    11    12    13    14    15

ASCII:     104   101   108   108   111    32   119   111   114   108   100     0    ??    ??    ??    ??
(十进制)

C 代码: __m128i block = _mm_loadu_si128((const __m128i*)s);
       (非对齐加载，允许从任意地址读取)

4.4. 步骤 2: 并行比较目标字符

SIMD 并行比较（16 个字节同时比较）:

加载的文本块:
┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│  h  │  e  │  l  │  l  │  o  │  _  │  w  │  o  │  r  │  l  │  d  │  \0 │  ?  │  ?  │  ?  │  ?  │
└─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘

目标向量 (全是 'o'):
┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│  o  │  o  │  o  │  o  │  o  │  o  │  o  │  o  │  o  │  o  │  o  │  o  │  o  │  o  │  o  │  o  │
└─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘
                                  ↓ 比较（==）↓
相等比较结果（_mm_cmpeq_epi8）:
┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│0x00 │0x00 │0x00 │0x00 │0xFF │0x00 │0x00 │0xFF │0x00 │0x00 │0x00 │0x00 │0x00 │0x00 │0x00 │0x00 │
└─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘
 字节0  字节1  字节2  字节3  字节4  字节5  字节6  字节7  字节8  字节9 字节10 字节11 字节12 字节13 字节14 字节15
   ✗     ✗     ✗     ✗     ✓     ✗     ✗     ✓     ✗     ✗     ✗     ✗     ✗     ✗     ✗     ✗

说明: 0xFF (二进制 11111111) 表示匹配，0x00 (二进制 00000000) 表示不匹配

C 代码: __m128i eqc = _mm_cmpeq_epi8(block, vc);

4.5. 步骤 3: 并行比较 NUL 终止符

同时检测字符串结束位置:

加载的文本块:
┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│  h  │  e  │  l  │  l  │  o  │  _  │  w  │  o  │  r  │  l  │  d  │  \0 │  ?  │  ?  │  ?  │  ?  │
└─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘

零向量:
┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│  0  │  0  │  0  │  0  │  0  │  0  │  0  │  0  │  0  │  0  │  0  │  0  │  0  │  0  │  0  │  0  │
└─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘
                                  ↓ 比较（==）↓
零匹配结果:
┌─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┬─────┐
│0x00 │0x00 │0x00 │0x00 │0x00 │0x00 │0x00 │0x00 │0x00 │0x00 │0x00 │0xFF │0x00 │0x00 │0x00 │0x00 │
└─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┴─────┘
   ✗     ✗     ✗     ✗     ✗     ✗     ✗     ✗     ✗     ✗     ✗     ✓     ✗     ✗     ✗     ✗

C 代码: __m128i eq0 = _mm_cmpeq_epi8(block, vz);

4.6. 步骤 4: movemask 压缩为位掩码

将 16 个字节的比较结果压缩成 16 个比特:

字符匹配向量:
┌──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┐
│ 0x00 │ 0x00 │ 0x00 │ 0x00 │ 0xFF │ 0x00 │ 0x00 │ 0xFF │ 0x00 │ 0x00 │ 0x00 │ 0x00 │ 0x00 │ 0x00 │ 0x00 │ 0x00 │
└──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┘
提取每个字节的最高位(MSB):
   ↓      ↓      ↓      ↓      ↓      ↓      ↓      ↓      ↓      ↓      ↓      ↓      ↓      ↓      ↓      ↓
   0      0      0      0      1      0      0      1      0      0      0      0      0      0      0      0

打包成 16 位整数（右边是 bit0，左边是 bit15）:
bit 位置: 15  14  13  12  11  10   9   8   7   6   5   4   3   2   1   0
         ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
mask_c:  │ 0 │ 0 │ 0 │ 0 │ 0 │ 0 │ 0 │ 1 │ 0 │ 0 │ 0 │ 1 │ 0 │ 0 │ 0 │ 0 │  = 0x0110 = 0b0000_0001_0001_0000
         └───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
                                      ↑           ↑
                                    bit 7       bit 4
                               （字节7='o'）  （字节4='o'）

零匹配向量:
┌──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┬──────┐
│ 0x00 │ 0x00 │ 0x00 │ 0x00 │ 0x00 │ 0x00 │ 0x00 │ 0x00 │ 0x00 │ 0x00 │ 0x00 │ 0xFF │ 0x00 │ 0x00 │ 0x00 │ 0x00 │
└──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┴──────┘

bit 位置: 15  14  13  12  11  10   9   8   7   6   5   4   3   2   1   0
         ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
mask_0:  │ 0 │ 0 │ 0 │ 0 │ 1 │ 0 │ 0 │ 0 │ 0 │ 0 │ 0 │ 0 │ 0 │ 0 │ 0 │ 0 │  = 0x0800 = 0b0000_1000_0000_0000
         └───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
                          ↑
                        bit 11
                    （字节11='\0'）

C 代码:
int mc = _mm_movemask_epi8(eqc);  // 0x0110
int m0 = _mm_movemask_epi8(eq0);  // 0x0800

4.7. 步骤 5: tzcnt/bsf 定位首匹配位

使用 tzcnt (Trailing Zero Count) 或 bsf (Bit Scan Forward) 找第一个 1:

字符匹配掩码 mc = 0x0110:
二进制: 0000_0001_0001_0000
        ││││ ││││ │││└─ bit 0: 0
        ││││ ││││ ││└── bit 1: 0
        ││││ ││││ │└─── bit 2: 0
        ││││ ││││ └──── bit 3: 0
        ││││ │││└────── bit 4: 1  ← 第一个 1！
        ...

tzcnt(0x0110) = 4  →  第一个 'o' 在偏移 4

零匹配掩码 m0 = 0x0800:
二进制: 0000_1000_0000_0000
                 └─────── bit 11: 1  ← 第一个 1！

tzcnt(0x0800) = 11  →  NUL 在偏移 11

C 代码:
unsigned pos_c = mc ? __builtin_ctz(mc) : 32;  // 4
unsigned pos_0 = m0 ? __builtin_ctz(m0) : 32;  // 11

4.8. 步骤 6: 决策：比较字符位与 NUL 位

比较两个位置，决定返回值:

pos_c = 4   (第一个 'o' 的位置)
pos_0 = 11  (NUL 的位置)

判断:
if (pos_c < pos_0):  // 4 < 11 → true
    return s + pos_c  // 返回指向字符的指针

流程图:
                  ┌──────────────┐
                  │ 找到匹配位置 │
                  └──────┬───────┘
                         │
            ┌────────────┴────────────┐
            │                         │
      pos_c < pos_0?            pos_0 < pos_c?
      (目标在前)                (NUL在前)
            │                         │
            ↓                         ↓
     返回 s + pos_c             返回 NULL
     (找到字符)                 (未找到)

最终结果: 返回指向 "hello world" 中第一个 'o' 的指针（偏移 4）

5. 第二部分：strstr 双字节前缀过滤详解

5.1. 场景设定

在字符串 "abracadabra" 中查找子串 "abra"。

5.2. 前缀过滤策略

策略: 不是逐字节匹配整个 needle，而是:
1. 快速找到 needle 前两字节 "ab" 的所有候选位置
2. 只对候选位置做完整的 memcmp 验证

为什么有效？
- 双字节匹配已经能过滤掉 99.6% 的无关位置 (1/256)
- SIMD 可以并行检查 16/32/64 个位置
- memcmp 次数大幅减少

5.3. 步骤 1: 准备并加载

needle = "abra"
前缀字符: p0 = 'a', p1 = 'b'

广播到向量:
v0 (全是 'a'):  [ a a a a a a a a a a a a a a a a ]
v1 (全是 'b'):  [ b b b b b b b b b b b b b b b b ]

加载文本块:
索引:          0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15
            ┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┐
文本块:     │ a│ b│ r│ a│ c│ a│ d│ a│ b│ r│ a│\0│ ?│ ?│ ?│ ?│
            └──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘

5.4. 步骤 2: 生成两个匹配掩码

比较 1: 哪些位置是 'a'?

文本:  [ a  b  r  a  c  a  d  a  b  r  a  \0  ?  ?  ?  ? ]
v0:    [ a  a  a  a  a  a  a  a  a  a  a  a  a  a  a  a ]
       ────────────────────────────────────────────────────
eq:    [✓  ✗  ✗  ✓  ✗  ✓  ✗  ✓  ✗  ✗  ✓  ✗  ✗  ✗  ✗  ✗ ]

movemask 提取 MSB:
位置:   15 14 13 12 11 10  9  8  7  6  5  4  3  2  1  0
       ┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┐
m0:    │ 0│ 0│ 0│ 0│ 0│ 1│ 0│ 1│ 0│ 1│ 0│ 1│ 0│ 0│ 1│ 0│
       └──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘
m0 = 0b0000_0101_0010_1001 = 0x0529

解读: 位置 0, 3, 5, 8, 10 的字符是 'a'


比较 2: 哪些位置是 'b'?

文本:  [ a  b  r  a  c  a  d  a  b  r  a  \0  ?  ?  ?  ? ]
v1:    [ b  b  b  b  b  b  b  b  b  b  b  b  b  b  b  b ]
       ────────────────────────────────────────────────────
eq:    [✗  ✓  ✗  ✗  ✗  ✗  ✗  ✗  ✓  ✗  ✗  ✗  ✗  ✗  ✗  ✗ ]

位置:   15 14 13 12 11 10  9  8  7  6  5  4  3  2  1  0
       ┌──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┬──┐
m1:    │ 0│ 0│ 0│ 0│ 0│ 0│ 0│ 0│ 0│ 0│ 0│ 0│ 0│ 1│ 0│ 1│
       └──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┴──┘
m1 = 0b0000_0001_0000_0010 = 0x0102

解读: 位置 1, 8 的字符是 'b'

5.5. 步骤 3: 位运算找候选（核心）

我们要找: text[i] == 'a' AND text[i+1] == 'b'

位运算技巧:
1. m1 >> 1  将位置 i+1 的 'b' 信息移动到位置 i；
2. m0 & (m1 >> 1) 得到 text[i]=='a' 且 text[i+1]=='b' 的所有 i（块内候选）。

可视化:

位置:     15 14 13 12 11 10  9  8  7  6  5  4  3  2  1  0
文本:      ?  ?  ?  ?  ? [a][r][a][d][a][c][a][r][b][a][b]
         ─────────────────────────────────────────────────
m0:        0  0  0  0  0  1  0  1  0  1  0  1  0  0  1  0   ('a' 的位置)
m1:        0  0  0  0  0  0  0  0  0  0  0  0  0  1  0  1   ('b' 的位置)

说明：m1>>1 的第 i 位为 1，当且仅当原始第 i+1 字节为 'b'；与 m0 的第 i 位相与，即得到 "ab" 前缀的起点集合。

计算:
m0:        0b0000_0101_0010_1001
m1>>1:     0b0000_0000_1000_0001
AND:       0b0000_0000_0000_0001 = 0x0001
              └──────────────┘
                  bit 0 = 1

候选位置: 0


详细验证:
─────────────────────────────────────────────────────────────────
位置 0: text[0] = 'a', text[1] = 'b'  → 匹配前缀 "ab" ✓

tzcnt(0x0001) = 0  → 第一个候选在位置 0

5.6. 步骤 4: 精确验证

候选位置 0 找到后，进行完整匹配:

text + 0: "abra..."
needle:   "abra"
          ────
memcmp(text+0, needle, 4) == 0  → 完全匹配！

返回: text + 0


如果有多个候选:
─────────────────────────────────────────────────────────────────
假设 cand = 0x0081 (bit 0 和 bit 7):

while (cand) {
    pos = tzcnt(cand);        // 先处理 bit 0
    验证 text[pos..pos+len];
    if (匹配) return text + pos;
    cand &= (cand - 1);       // 清除最低位，继续下一个候选
}

cand = 0x0081 = 0b1000_0001
     & 0x0080 = 0b1000_0000  (cand - 1 清除了 bit 0)
     ─────────────────────
       0x0080 = 0b1000_0000

下次循环: tzcnt(0x0080) = 7，检查位置 7

6. 3. 跨块边界处理（carry）

6.1. 为何需要

needle 前缀过滤阶段 cand = m0 & (m1 >> 1)。若前缀 "ab" 恰好跨两个块：块A最后字节 'a' + 块B首字节 'b'，则：

  • m0_A 最高位（bit W-1）= 1
  • m1_B 最低位（bit 0）= 1
  • 但 (m1_B >> 1) 会丢弃 bit 0，导致该跨块候选丢失。

6.2. 两种常用方案

  1. 重叠扫描：每次前进 W-1 字节（例如 15、31、63）。简单可靠，代价是 ~6% 额外加载。
  2. carry 位注入：保存上一块 m0 的最高位 prev_last_p0，并与当前块 m1 的最低位相与；条件成立时在 cand 中用最高位作为“跨块候选”的标记位。

6.3. 正确的位构造

设：

  • W = 块宽（16/32/64）
  • m0: 本块等于 p0 的位图
  • m1: 本块等于 p1 的位图
  • prev_last_p0: 上一块末字节是否等于 p0（布尔 0/1）

跨块候选：如果 prev_last_p0 && (m1 & 1)，说明存在上一块末位置 i = -1（对当前块局部坐标），与当前块位置 0 组成的 "p0 p1"。在当前 cand 里需要一个代表“上一块末尾”的位。我们自然把它放在 cand 的最高位 (bit W-1)，因为正常块内 i 范围是 [0, W-2] 对应 (m1 >> 1) 后与 m0 的对齐；最高位不会被块内 (m1 >> 1) 产生（因为右移填 0）。

因此： intra = m0 & (m1 >> 1) cross = (prev_last_p0 && (m1 & 1)) ? (1 << (W-1)) : 0 cand = intra | cross

当 cand 的最高位被置 1 时，表示“真实起点是上一块的最后 1 字节”。处理时： if (pos == W-1 && cross) hit_ptr = block_start - 1; else hit_ptr = block_start + pos;

循环尾部更新： prev_last_p0 = (m0 >> (W-1)) & 1; （用于下一块）

6.4. 与常见错误的区别

  • 错误 1：用 (m1 & 1) 作为 carry 传递并左移 (W-1)；会错误地表达“上一块首字节 == p1”。
  • 错误 2：直接把 carry 与 (m1 >> 1) OR 后再与 m0；含义混乱且可能覆盖真实最高位。

6.5. 可替换策略

如果不想特殊处理 pos == W-1，可采用重叠扫描（前进 W-1 字节），候选逻辑不变，代价接受即可。

6.6. 伪代码（SSE2 W=16）

int prev_last_p0 = 0; // 初始上一块末字节不构成前缀
while (...) {
        __m128i blk = _mm_loadu_si128((const __m128i*)s);
        int m0 = _mm_movemask_epi8(_mm_cmpeq_epi8(blk, v0));
        int m1 = _mm_movemask_epi8(_mm_cmpeq_epi8(blk, v1));
        int intra = m0 & (m1 >> 1);
        int cross = (prev_last_p0 && (m1 & 1)) ? (1 << 15) : 0; // 15 = W-1
        int cand = intra | cross;
        // 处理 NUL 掩码截断（若需要）...
        while (cand) {
                int pos = __builtin_ctz(cand);
                const char *hit = (pos == 15 && cross) ? s - 1 : s + pos;
                // 验证 hit
                cand &= cand - 1;
        }
        prev_last_p0 = (m0 >> 15) & 1; // 下一轮
        s += 16;
}

6.7. 何时优先哪种

  • 字符串超长、缓存友好：carry 更高效。
  • 代码维护成本优先：重叠扫描最简单。
  • 追求极致：AVX-512 可用跨块拼接思路 + 掩码加载进一步减少边界复杂度。

7. 第四部分：页边界安全详解

7.1. 问题根源

Linux/Unix 内存管理以页为单位（通常 4KB = 4096 字节）

虚拟内存布局示例:
┌─────────────────────┬─────────────────────┬─────────────────────┐
│   页 0 (已映射)     │   页 1 (已映射)     │   页 2 (未映射)     │
│   0x0000 - 0x0FFF   │   0x1000 - 0x1FFF   │   0x2000 - 0x2FFF   │
│   可读可写          │   可读可写          │   PROT_NONE         │
└─────────────────────┴─────────────────────┴─────────────────────┘

问题: 如果字符串在页末尾:
地址:  0x0FF5 ... 0x0FFF | 0x1000 (页边界)
文本:  "hello\0" ?  ?  ? | ← 未映射 → 访问会 SIGSEGV!

SIMD 加载是非对齐的，会一次读取 16/32/64 字节:
_mm_loadu_si128(0x0FF5) 读取 [0x0FF5, 0x1004]
                                       ^^^^ 越界！崩溃！

7.2. 安全策略

策略 1: 计算页内剩余字节
───────────────────────────────────────────────────────────────
remain = 4096 - (ptr & 0xFFF)

ptr & 0xFFF  取地址的低 12 位，即页内偏移（0-4095）
4096 - 偏移  得到到页末的字节数

示例:
ptr = 0x1FF5
页内偏移 = 0x1FF5 & 0xFFF = 0xFF5 = 4085
remain = 4096 - 4085 = 11 字节


策略 2: 不足时回退到标量
───────────────────────────────────────────────────────────────
if (remain < 16) {  // SSE2 宽度
    for (i = 0; i < remain; i++) {
        标量处理每个字节
    }
    ptr += remain;  // 前进到下一页开头
    继续向量处理
}


策略 3: 边界条件处理
───────────────────────────────────────────────────────────────
1. 如果在剩余字节内找到 NUL → 返回结果
2. 如果在剩余字节内找到目标 → 返回结果
3. 如果都没找到 → 前进到下一页，恢复 SIMD 路径

7.3. 可视化示例

场景: ptr = 0x1FF5, 字符串 "end\0"

内存布局:
地址:      0x1FF0                    0x1FFF 0x2000
          ┌───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┬───┐
页1:      │...│...│...│...│...│ e │ n │ d │\0 │...│...│...│...│...│...│...│
          └───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┴───┘
                               ↑                                           ↑
                             ptr=0x1FF5                                页边界
                               └────────── remain=11 ─────────────────┘

步骤 1: 计算剩余
remain = 4096 - (0x1FF5 & 0xFFF) = 4096 - 4085 = 11

步骤 2: 判断
remain (11) < 16  → 不安全进行 SIMD

步骤 3: 标量扫描
for (i = 0; i < 11; i++) {
    if (ptr[i] == target) return ptr + i;
    if (ptr[i] == 0) return NULL;  // 在 i=3 处遇到 '\0'
}

结果: 在页内找到结果，安全返回，未触及页 2

7.4. 优化技巧

1. 对齐到块边界开始
───────────────────────────────────────────────────────────────
初始时，如果 ptr 未对齐，先用标量处理到下一个 16 字节边界
之后大部分循环都是对齐加载，可能略快（微架构相关）


2. AVX-512 掩码加载
───────────────────────────────────────────────────────────────
__mmask64 k = (1ULL << remain) - 1;  // 只加载 remain 个字节
__m512i v = _mm512_maskz_loadu_epi8(k, ptr);
减少页末回退频率，但仍需检查 remain


3. 软件预取
───────────────────────────────────────────────────────────────
如果确定下一页已映射（如在已知缓冲区内），可预取:
_mm_prefetch(ptr + 64, _MM_HINT_T0);

8. 第五部分：交互式学习工具

8.1. 手动模拟工具

#include <stdio.h>
#include <immintrin.h>

// 打印 16 位掩码的二进制表示
void print_mask(int mask, const char* label) {
    printf("%s: 0x%04X = ", label, mask & 0xFFFF);
    for (int i = 15; i >= 0; i--) {
        printf("%d", (mask >> i) & 1);
        if (i % 4 == 0) printf(" ");
    }
    printf("\n");
}

// 打印向量内容（作为字符）
void print_vec(__m128i v, const char* label) {
    char buf[17];
    _mm_storeu_si128((__m128i*)buf, v);
    buf[16] = 0;
    printf("%s: ", label);
    for (int i = 0; i < 16; i++) {
        if (buf[i] >= 32 && buf[i] < 127)
            printf(" %c ", buf[i]);
        else
            printf("%02X ", (unsigned char)buf[i]);
    }
    printf("\n");
}

// 可视化 strchr
void visualize_strchr(const char* text, char target) {
    printf("=== 查找 '%c' 在 \"%s\" 中 ===\n\n", target, text);

    __m128i vc = _mm_set1_epi8(target);
    __m128i vz = _mm_setzero_si128();
    __m128i block = _mm_loadu_si128((const __m128i*)text);

    print_vec(block, "文本块 ");
    print_vec(vc, "目标向量");

    __m128i eqc = _mm_cmpeq_epi8(block, vc);
    __m128i eq0 = _mm_cmpeq_epi8(block, vz);

    print_vec(eqc, "字符匹配");
    print_vec(eq0, "零匹配 ");

    int mc = _mm_movemask_epi8(eqc);
    int m0 = _mm_movemask_epi8(eq0);

    print_mask(mc, "字符掩码");
    print_mask(m0, "零掩码 ");

    if (mc) {
        int pos = __builtin_ctz(mc);
        printf("\n结果: 在位置 %d 找到 '%c'\n", pos, target);
    } else {
        printf("\n结果: 未找到 '%c'\n", target);
    }
}

int main() {
    visualize_strchr("hello world!!!!!", 'o');
    printf("\n");
    visualize_strchr("abcdefghijklmnop", 'x');
    return 0;
}

编译运行: 

gcc -O2 -msse2 visualizer.c -o viz && ./viz

8.2. 预期输出

=== 查找 'o' 在 "hello world!!!!!" 中 ===

文本块 :  h  e  l  l  o     w  o  r  l  d  !  !  !  !  !  ! 
目标向量:  o  o  o  o  o  o  o  o  o  o  o  o  o  o  o  o 
字符匹配: 00 00 00 00 FF 00 00 FF 00 00 00 00 00 00 00 00 
零匹配 : 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
字符掩码: 0x0110 = 0000 0001 0001 0000 
零掩码 : 0x0000 = 0000 0000 0000 0000 

结果: 在位置 4 找到 'o'

=== 查找 'x' 在 "abcdefghijklmnop" 中 ===

文本块 :  a  b  c  d  e  f  g  h  i  j  k  l  m  n  o  p 
目标向量:  x  x  x  x  x  x  x  x  x  x  x  x  x  x  x  x 
字符匹配: 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
零匹配 : 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 
字符掩码: 0x0000 = 0000 0000 0000 0000 
零掩码 : 0x0000 = 0000 0000 0000 0000 

结果: 未找到 'x'

9. 总结与要点

1. SIMD 的核心: 并行比较 + 位掩码 + 快速定位
   - 一次处理 16/32/64 字节
   - movemask 把向量结果压缩为标量位掩码
   - tzcnt/bsf O(1) 找到第一个匹配

2. 双字节前缀过滤: 减少 99%+ 无效比较
   - 用前2字节快速筛选候选
   - 位运算 (m0 & (m1>>1)) 找到连续匹配
   - 只对少数候选做完整 memcmp

3. 页边界安全: 避免越界读取崩溃
   - 计算 remain = 4096 - (ptr & 4095)
   - 不足时回退标量
   - AVX-512 可用掩码加载优化

4. 跨块处理: carry 传递边界信息
   - 保存上一块末尾状态
   - 注入到下一块的候选计算
   - 或简单地允许 1 字节重叠扫描

5. 性能关键:
   - 减少分支（用位运算）
   - 向量指令延迟低、吞吐高
   - 多版本派发（SSE2/AVX2/AVX-512）

10. （合并）页边界安全

关于页边界的原因与策略，见上文“4. 跨块与页边界安全”。此处不再重复。

11. 基础实现：SIMD strchr（SSE2 / AVX2）

以下实现演示了：

  • 按页安全加载；
  • 同步检测目标字符与 NUL；
  • 用 tzcnt 找“目标 vs NUL”的先后，确保语义正确。
#include <immintrin.h>
#include <stdint.h>
#include <stddef.h>

static inline size_t end_of_page(const void *p) {
    return 4096u - ((uintptr_t)p & 4095u);
}

// 返回首次出现 c 的地址；若遇到 NUL 先于 c，则返回 NULL。
static inline const char* simd_strchr_sse2(const char *s, char c) {
    const __m128i vz = _mm_setzero_si128();
    const __m128i vc = _mm_set1_epi8((char)c);

    for (;;) {
        size_t remain = end_of_page(s);
        if (remain < 16) {
            for (size_t i = 0; i < remain; ++i) {
                if (s[i] == c) return s + i;
                if (!s[i]) return NULL;
            }
            s += remain;
            continue;
        }
        __m128i block = _mm_loadu_si128((const __m128i*)s);
        __m128i eqc   = _mm_cmpeq_epi8(block, vc);
        __m128i eq0   = _mm_cmpeq_epi8(block, vz);
        int mc = _mm_movemask_epi8(eqc);
        int m0 = _mm_movemask_epi8(eq0);
        if ((mc | m0) != 0) {
            unsigned pos_c = mc ? (unsigned)__builtin_ctz((unsigned)mc) : 32u;
            unsigned pos_0 = m0 ? (unsigned)__builtin_ctz((unsigned)m0) : 32u;
            if (pos_c < pos_0) return s + pos_c;
            if (pos_0 < pos_c) return NULL;
            // 不可能相等：同一字节既为 c 又为 0
        }
        s += 16;
    }
}

static inline const char* simd_strchr_avx2(const char *s, char c) {
    const __m256i vz = _mm256_setzero_si256();
    const __m256i vc = _mm256_set1_epi8((char)c);

    for (;;) {
        size_t remain = end_of_page(s);
        if (remain < 32) {
            for (size_t i = 0; i < remain; ++i) {
                if (s[i] == c) return s + i;
                if (!s[i]) return NULL;
            }
            s += remain;
            continue;
        }
        __m256i block = _mm256_loadu_si256((const __m256i*)s);
        __m256i eqc   = _mm256_cmpeq_epi8(block, vc);
        __m256i eq0   = _mm256_cmpeq_epi8(block, vz);
        unsigned mc = (unsigned)_mm256_movemask_epi8(eqc);
        unsigned m0 = (unsigned)_mm256_movemask_epi8(eq0);
        if ((mc | m0) != 0) {
            unsigned pos_c = mc ? (unsigned)__builtin_ctz(mc) : 64u;
            unsigned pos_0 = m0 ? (unsigned)__builtin_ctz(m0) : 64u;
            if (pos_c < pos_0) return s + pos_c;
            if (pos_0 < pos_c) return NULL;
        }
        s += 32;
    }
}

使用方式与编译： 

# SSE2 版本（x86_64 默认具备）：
gcc -O3 -msse2 demo.c -o demo

# AVX2（需 CPU 支持）：
gcc -O3 -mavx2 demo.c -o demo

提示：若以库形式提供，可在运行时通过 cpuid/ifunc 选择最佳路径（SSE2→AVX2→AVX-512）。

12. strstr 的“双字节前缀过滤”

思路：仅用模式串 needle 的前两字节 p0/p1 做快速筛选，得到候选起点，再对每个候选处做精确比较。

  • 构造两个“相等掩码”：m1 表示等于 p0 的字节位置；m2 表示等于 p1 的位置。
  • 候选起点满足：m1[i] 且 m2[i+1]，即 candidate_mask = m1 & (m2 >> 1)。
  • 跨块时需“携带”上一块 m2 的最低有效位给下一块（作为下一块第 0 位的 m2[-1]）。
  • NUL 处理：零位一旦出现，截断掩码在首个零位之前并结束。
#include <string.h>

static inline const char* fallback_memcmp(const char* s, const char* n, size_t len) {
    return memcmp(s, n, len) == 0 ? s : NULL;
}

// 简化版：needle_len >= 2，返回首次匹配；若遇到 NUL 则失败。
static inline const char* simd_strstr2_sse2(const char *hay, const char *needle, size_t nlen) {
    const char p0 = needle[0], p1 = needle[1];
    const __m128i v0 = _mm_set1_epi8(p0);
    const __m128i v1 = _mm_set1_epi8(p1);
    const __m128i vz = _mm_setzero_si128();

    // 记录上一块“末字节是否等于 p0”（用于跨块候选）
    int prev_last_p0 = 0;
    const char *s = hay;

    for (;;) {
        size_t remain = end_of_page(s);
        if (remain < 16) {
            // 标量过页；注意避免 i+1 越界与 memcmp 跨页。
            for (size_t i = 0; i + 1 < remain; ++i) {
                if (!s[i]) return NULL;
                if (s[i] == p0 && s[i+1] == p1) {
                    if (nlen == 2) return s + i;
                    if (i + nlen <= remain) { // 仅在本页内安全验证
                        if (fallback_memcmp(s + i, needle, nlen)) return s + i;
                    }
                    // 否则：跨页验证留给下一页（通过重叠推进捕获）
                }
            }
            // 在页切换处保留 nlen-1 字节重叠，避免跨页漏匹配
            size_t overlap = nlen > 0 ? (nlen - 1) : 0;
            size_t step = remain > overlap ? (remain - overlap) : remain;
            s += step;
            continue;
        }
        __m128i blk = _mm_loadu_si128((const __m128i*)s);
        __m128i m0v = _mm_cmpeq_epi8(blk, v0);
        __m128i m1v = _mm_cmpeq_epi8(blk, v1);
        int m0 = _mm_movemask_epi8(m0v);
        int m1 = _mm_movemask_epi8(m1v);
        int mz = _mm_movemask_epi8(_mm_cmpeq_epi8(blk, vz));

        // 候选位：块内 + 跨块（上一块末位==p0 且本块首位==p1）
        int intra = m0 & (m1 >> 1);
        int cross = (prev_last_p0 && (m1 & 1)) ? (1 << 15) : 0;
        int cand = intra | cross;

        // 若出现零，截断到首个零位之前
        if (mz) {
            unsigned zpos = (unsigned)__builtin_ctz((unsigned)mz);
            cand &= (1 << zpos) - 1; // 保留零前的候选
        }

        while (cand) {
            unsigned pos = (unsigned)__builtin_ctz((unsigned)cand);
            const char *hit = (pos == 15 && cross) ? (s - 1) : (s + pos);
            if (nlen == 2) return hit;

            // 如块内出现 NUL，则禁止跨越 NUL 的验证
            if (mz && !(pos == 15 && cross)) {
                unsigned zpos = (unsigned)__builtin_ctz((unsigned)mz);
                if (pos + nlen > zpos) { cand &= (cand - 1); continue; }
            }
            // 避免 memcmp 跨页：仅当从 hit 起的页剩余足够时才验证
            size_t safe = end_of_page(hit);
            if (nlen <= safe && fallback_memcmp(hit, needle, nlen)) return hit;
            cand &= (cand - 1); // 清除最低位
        }

        if (mz) return NULL; // 首个零已在本块，且无命中

        // 更新跨块状态：本块末字节是否等于 p0
        prev_last_p0 = (m0 >> 15) & 1;
        s += 16;
    }
}

AVX2/AVX-512 版本仅把 16 改为 32/64，并替换对应 intrinsics：

  • AVX2: _mm256_cmpeq_epi8, _mm256_movemask_epi8。
  • AVX-512: _mm512_cmpeq_epi8_mask 直接得到 64 位 k-mask；可用掩码加载避免页边界 fallback。

13. 教程：从零跑起的最小工程

  1. 准备文件 demo.c，把上述两个函数粘贴进去，并写 main：
#include <stdio.h>
int main() {
    const char *s = "hello SIMD world!";
    const char *p = simd_strchr_sse2(s, 'S');
    printf("strchr -> %ld\n", p ? (long)(p - s) : -1L);

    const char *n = "SIMD";
    const char *q = simd_strstr2_sse2(s, n, 4);
    printf("strstr -> %ld\n", q ? (long)(q - s) : -1L);
    return 0;
}
  1. 编译运行：
gcc -O3 -msse2 demo.c -o demo && ./demo
  1. 简单基准：
# 1GB 随机文本（ASCII），查找字符/短子串
dd if=/dev/urandom bs=1M count=1024 of=rand.bin status=none
# 写一个基准循环，或以 perf stat 粗测 CPI、分支失败、指令数
perf stat -e cycles,instructions,branches,branch-misses ./bench

14. 微架构与性能提示

  • movemask 与 tzcnt/bsf：在多数 uarch 上延迟小、吞吐高，成为热路径的常客。
  • 载入带宽：保持循环内依赖短，利于乱序执行隐藏内存延迟；避免每字节分支。
  • 预取：对超长文本可轻量预取（_mm_prefetch），但收益依数据/平台而异。
  • 代码尺寸：SSE2/AVX2/AVX-512 多版本可通过 ifunc/函数指针表在启动时选择。

15. 常见陷阱与局限

  • 编码：UTF-8 多字节语义与“字符”不同于字节；本文按字节匹配语义。
  • 不区分大小写匹配：需先规范化文本（如 tolower）或用表驱动广播两版字符。
  • 未定义行为：绝不越页读；维持 strict-aliasing、安全对齐与 const 正确。
  • 小 needle：nlen==1 退化为 strchr；nlen==0 依实现决定（通常返回 hay）。

16. 进一步阅读

17. 更详细的算法图解

  • strchr/strstr SIMD 流水线（按字节→按位）
[ 非对齐加载 16/32/64B ]
                |
                v
[ 广播常量: c, 0 或 p0/p1 ]
                |
                v
[ 向量比较: eq(c), eq(0), eq(p0), eq(p1) ]
                |
                v
[ movemask 挤出位掩码: m_c, m_0, m0, m1 ]
                |
                v
[ 组合/移位: 候选 cand = m0 & (m1 >> 1)  或  m_c vs m_0 ]
                |
                v
[ tzcnt/bsf 找首个 1 位 ]
                |
         +------+------+
         |             |
         v             v
   命中/返回     无命中/前进
  • strstr 前缀过滤位图示意（needle = "ab"）
文本块:  [ a  x  a  a  b  a  b  x  a  b  ]
等于'a':   1  0  1  1  0  1  0  0  1  0   => m0 = 0b0100101101
等于'b':   0  0  0  0  1  0  1  0  0  1   => m1 = 0b1001010000
右移一位:     0  0  0  0  0  1  0  1  0   => m1>>1
候选位 = m0 & (m1>>1):
             0  0  0  0  0  1  0  0  0
             ^                ^
             i=4（ab）        i=8（ab）
  • 跨块携带（carry）
块A宽度=W（16/32/64），块B紧随其后
m1_A 的最高位 -> 作为 carry 注入到 块B 组合：cand_B = m0_B & ((m1_B >> 1) | (carry << (W-1)))
示例：W=16，若 A 的最后1字节等于 p1，则 carry=1，使得 B 的第0字节若等于 p0 也能成为候选。
  • 页末安全回退流程
+-------------------------------+
| remain = 4096 - (ptr & 4095) |
+-------------------------------+
               |
remain < W? ---+---- yes --> [ 标量扫描到页末 ] -> 前进
               |
              no
               v
         [ 向量路径 ]
  • NUL 终止的剪枝
m_0 = eq(0) 的位掩码；zpos = tzcnt(m_0)
只保留 cand/m_c 中 < zpos 的位；zpos 存在且未命中则返回 NULL。

18. 进阶 tutorial（从工程化到验证）

  1. 运行时派发（根据 CPU 特性选择最优实现）
#include <stdatomic.h>
#include <stdbool.h>

static const char* (*p_strchr)(const char*, char);

static const char* strchr_init(const char* s, char c) {
    bool has_avx2 = __builtin_cpu_supports("avx2");
    atomic_store_explicit((_Atomic(void**)&p_strchr),
        has_avx2 ? (void*)simd_strchr_avx2 : (void*)simd_strchr_sse2, memory_order_relaxed);
    return p_strchr(s, c);
}

__attribute__((ifunc("strchr_resolver")))
static const char* simd_strchr_auto(const char*, char);
static void* strchr_resolver(void) {
    return __builtin_cpu_supports("avx2") ? simd_strchr_avx2 : simd_strchr_sse2;
}
  1. 正确性测试（随机+边界）
  2. 与 libc 对拍：随机生成长度/内容，插入 0 作为终止，比较 strchr/strstr 结果与偏移。
  3. 页边界保护：mmap 两页，后一页 PROT_NONE；在前一页尾部起点调用，验证无越页读取。
#include <sys/mman.h>
#include <string.h>
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

static void page_guard_test(void) {
    const size_t PS = 4096;
    char* p = mmap(NULL, PS*2, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0);
    mprotect(p+PS, PS, PROT_NONE); // 后一页禁用
    memset(p, 'A', PS);
    p[PS-1] = 0; // 在最后一个字节放 NUL，任何跨页读都会崩
    const char* r1 = simd_strchr_sse2(p+PS-32, 'B');
    const char* r2 = strchr(p+PS-32, 'B');
    assert((r1==NULL) == (r2==NULL));
    munmap(p, PS*2);
}

static void fuzz_strchr(void) {
    srand(0xC0FFEE);
    for (int t=0; t<10000; ++t) {
        size_t n = rand()%10000 + 1;
        char* s = (char*)malloc(n+1);
        for (size_t i=0;i<n;i++) s[i] = (char)(rand()%128);
        s[n] = 0;
        char c = (char)(rand()%128);
        const char* a = simd_strchr_sse2(s, c);
        const char* b = strchr(s, c);
        assert(a==b);
        free(s);
    }
}
  1. 基准设计与指标
  2. 方法：构造 64MB+ 缓冲区，避免缓存命中；多次热身后取 P50/P90；记录 ns/byte、GiB/s、IPC、分支失败率。
  3. 工具：perf stat、perf record；可选火焰图；注意固定 CPU 频率与隔离核。
#include <time.h>
static double now_ns(){ struct timespec ts; clock_gettime(CLOCK_MONOTONIC, &ts); return ts.tv_sec*1e9+ts.tv_nsec; }
static void bench_strchr(void) {
    size_t N = 64u<<20; char* buf = (char*)aligned_alloc(64, N+1); memset(buf,'A',N); buf[N]=0;
    for(int w=0; w<5; ++w) simd_strchr_sse2(buf,'Z'); // warmup
    double t0=now_ns(); const char* r=NULL; for(int rds=0;rds<50;++rds) r=simd_strchr_sse2(buf,'Z'); double t1=now_ns();
    printf("ns/byte=%.3f\n", (t1-t0)/(N*50)); free(buf);
}
  1. 位操作可视化辅助
static void bits16(unsigned x){ for(int i=15;i>=0;--i) putchar((x>>i)&1?'1':'0'); putchar('\n'); }
  1. AVX-512 提示
  2. 使用 _mm512_cmpeq_epu8_mask 得到 k-mask；_mm512_maskz_loadu_epi8 可按字节掩码安全加载，减少页末回退频率。
  3. 仍需计算 remain 以构造加载掩码；跨块 carry 逻辑保持不变，W=64。
  4. 常见边界用例清单
  5. needle 长度 0/1/2/n：分别处理为空串、退化为 strchr、双字节过滤、n>2 精确比较。
  6. 文本极短/极长、完全不命中、命中在首/末、包含大量 0 字节的二进制缓冲。

19. 速查总结表（Cheat Sheet）

项目 strchr strstr（双字节前缀）
比较指令 eq(c), eq(0) eq(p0), eq(p1)
掩码获取 movemask movemask × 2
候选构造 tzcnt(mc) vs tzcnt(m0) cand = (m0 & (m1 >> 1)) cross
跨块处理 无 cross = (prev_last_p0 && (m1 & 1)) ? 1 << (W-1) : 0
NUL 处理 比较 pos_c 与 pos_0 用 m_0 截断 cand；块内出现 NUL 则返回失败
页末策略 remain < W → 标量扫描到页末 remain < W → 标量扫描（含 nlen-1 重叠）
精确验证 不需要 对候选执行 memcmp（需页内安全与 NUL 前检查）
版本派发 SSE2/AVX2/AVX-512 SSE2/AVX2/AVX-512

术语统一：

  • 块（block）：单次向量加载的宽度（16/32/64）。
  • 掩码（mask）：movemask 的位图结果。
  • 候选（candidate）：可能的匹配起点位。
  • carry：跨块的前缀衔接布尔信息（上一块末字节是否为 p0）。
  • 页（page）：通常为 4KB；页末需要标量回退避免越页读取。

By .