SIMD CSV 解析：nibble 分类

基于SIMD与位掩码的向量化CSV解析技术

根据RFC4180标准解析CSV文件，需要识别结构字符：逗号分隔列，\r\n分隔行，引号用于转义。SIMD技术无需分支即可每周期处理16字节，通过半字节查找表实现分类。

该算法适用于ARM NEON（类似于x86 AVX2）。每个字节被拆分为高半字节和低半字节。两个16元素查找表返回类别位：逗号=1，引号=2，换行=3。

对于逗号（0x2C）：高半字节0x2 → 逗号|引号，低半字节0xC → 逗号。AND操作后保留逗号。

误报检查：某类别中的字节数必须等于唯一半字节的乘积。

向量化分类器实现

标量循环被替换为16字节块处理：

use std::arch::aarch64::*;


const LO_LOOKUP: [u8; 16] = {
    let mut t = [0u8; 16];
    t[0x2] = QUOTE;
    t[0xA] = NEWLINE;
    t[0xC] = COMMA;
    t[0xD] = NEWLINE;
    t
};

const HI_LOOKUP: [u8; 16] = {
    let mut t = [0u8; 16];
    t[0x0] = NEWLINE;
    t[0x2] = COMMA | QUOTE;
    t
};

unsafe {
    let lo_lut = vld1q_u8(LO_LOOKUP.as_ptr());
    let hi_lut = vld1q_u8(HI_LOOKUP.as_ptr());
    let mask = vdupq_n_u8(0x0F);

    for chunk in bytes.chunks_exact(16) {
        let input = vld1q_u8(chunk.as_ptr());
        let lo_nibbles = vandq_u8(input, mask);
        let hi_nibbles = vandq_u8(vshrq_n_u8::<4>(input), mask);
        
        let lo_result = vqtbl1q_u8(lo_lut, lo_nibbles);
        let hi_result = vqtbl1q_u8(hi_lut, hi_nibbles);
        let classified = vandq_u8(lo_result, hi_result);
        
        let mut out = [0u8; 16];
        vst1q_u8(out.as_mut_ptr(), classified);
        classified_bytes.extend_from_slice(&out);
    }
}

内联函数vqtbl1q_u8执行查找，vandq_u8执行AND操作。剩余部分通过填充处理。

压缩为位掩码

分类后的字节被转换为三个Vec<u64>，其中掩码中的每个位对应一个字符类别位置。u64描述数据流中的64字节。

示例alice,30,Irvine\n：

• 逗号掩码：位置5、8
• 引号掩码：空
• 换行掩码：位置15

过滤引号字段

分类器标记所有字符，包括内部字符。过滤时使用引号掩码的前缀XOR。

引号奇偶性决定状态：

• 位置后奇数次 → 字段内
• 位置后偶数次 → 字段外

转义""自平衡。示例"where she said, ""hi"\nto me：

• 位置0（"）：1次引号 → 字段内
• 位置17（"）：2次 → 字段外
• 位置29（"）：6次 → 字段外

内部逗号和\n被忽略。

状态的前缀XOR

对于16字节块，计算引号掩码的累积XOR。位i等于从位置i到末尾的引号奇偶性。

// 伪代码
let prefix_xor = 0;
for (i, &bit) in quote_mask.iter().enumerate() {
    prefix_xor ^= bit;
    if prefix_xor == 0 {
        // 字段外
    }
}

SIMD版本使用水平XOR跨块处理，配合popcount或bitscan的掩码。

收集分隔符位置

过滤后的掩码被扫描以提取真实分隔符的位置：

• 字段外的逗号 → 列边界
• 字段外的\n → 行边界

位置保存在偏移数组中。这允许在不复制数据的情况下分割数据流。

该方法的优势：

• 核心无分支
• 每块16倍并行
• 紧凑的位表示
• 易于扩展至32/64字节（AVX512）

关键要点

• 两个16字节半字节查找表替代256字节LUT，适用于SIMD。
• 两次查找的AND操作无需条件即可消除误分类。
• 前缀XOR在O(n)时间内确定引号字段边界。
• 位掩码将数据压缩至原始大小的3/8。
• 算法可移植：NEON → SSE4/AVX2，使用pshufb/_mm_shuffle_epi8。

— Editorial Team