关于simd:avx2-使用vpshufb指令做字符分类

最近看到 simdjson 的论文，其中应用 vpshufb 指令做的字符匹配和分类，感觉这个办法很有播种，想分享以下。

先说 simdjson 中为啥用这个指令，它须要从字符数组中提取出 6 种控制字符(‘:’, \’,‘:’,‘”’,‘{’,‘}’), 以及空格换行等 4 种无实际意义的字符(‘\r’,‘\n’,‘\t’,‘’)。

vpshufb 是汇编指令，在 C ++ 中能够用__m256i _mm256_shuffle_epi8 (__m256i a, __m256i b)。

__m256i _mm256_shuffle_epi8 (__m256i a, __m256i b)

算法过程:
FOR j := 0 to 15
    i := j*8
    IF b[i+7] == 1
        dst[i+7:i] := 0
    ELSE
        index[3:0] := b[i+3:i]
        dst[i+7:i] := a[index*8+7:index*8]
    FI
    IF b[128+i+7] == 1
        dst[128+i+7:128+i] := 0
    ELSE
        index[3:0] := b[128+i+3:128+i]
        dst[128+i+7:128+i] := a[128+index*8+7:128+index*8]
    FI
ENDFOR
dst[MAX:256] := 0

简略解释一下, __m256i 能够当做有 256 个 bit 位，假如 i =8, 那么 b[i+3:i]就是 b[11:8]，也就是第 8 到 11bit, 这四个 bit 组成一个无符号整数。四个比特最大是 1111，也就是十六进制的 f。

_mm256_shuffle_epi8 能够当作是一种查表形式，然而只能用每个字节的低四位去查。从 b 中获取每个字节的低四位。其值只能是 0 -15 中的一种，把这个值当作索引，而后从 a 中找这个索引对应的值。
总之，能够认为_mm256_shuffle_epi8 是一种映射关系，将一个数映射到另一个数。

下边是_mm256_shuffle_epi8 的两个应用例子。

如果有一个字节数组，存的都是 ascii，你须要从中找到小写字母。
a- z 对应的十六进制示意是：61-6f，70-7a (这里没写成 61-7a 是因为后边解决须要)

将 61-6f 分成一组，是因为它们高四位都是 6，70-7a 高四位都是 7。因为高四位一样的数能够被分到一个组里边。

算法思路是将一个字节的高四位，低四位别离应用_mm256_shuffle_epi8 做映射，两个映射后的后果做与运算，最终后果不为 0，就代表是须要的字符。

要害就是如何结构这个映射表了。
以字母 a 和 b 举例：

a (0110 0001)和 b(0110 0010), 他们高四位雷同，所以他们高四位的映射后果也是一样的。

对于高四位:

咱们假如 0110 通过_mm256_shuffle_epi8 映射后是，0000 0001

对于低四位:

那么咱们把 a 和 b 的低四位映射后，只须要最低为含有 1(xxxx xxx1), 比方 0000 0001 或 0000 0011 等, 那么这两个数的与运算的后果肯定是 0000 0001.

如果是匹配 a,b,p,q 四种字符

a (0110 0001)，b(0110 0010)，p(0111 0000),q(0111 0001)

对于高四位:

假如 0110 通过_mm256_shuffle_epi8 映射后是是 0000 0001
假如 0111 通过_mm256_shuffle_epi8 映射后是是 0000 0010

对于低四位:

把 a 和 b 的低四位映射后，只须要最低位含有 1(xxxx xxx1),p 和 q 映射后须要第二位是 1(xxxx xx1x), 然而你会发现，a 和 q 的低四位是一样的, 也就是他们映射后也是雷同的。所以映射后果是:
0000-->0010,0001-->0011,0010-->0001。

下边不推到了，只是分享例子
对字母 a -z A-Z
高 4bit：

0110 和 0100，映射到  0001
0111 和 0101，映射到  0001
其余映射到 0 

低 4bit:

0000 映射到 0010
0001 到 1010 映射到 0011
1011 到 1111 映射到 0001

其实对字母的提取，齐全能够用 'a'>= 字符 && 字符 <='z'这样的形式来解决，真正用_mm256_shuffle_epi8 的话，还是要对一些更简单的分类做解决. 我是用来对 HTML 中一些构造提取时:
我须要获取三种类型的字符
第一种: a-z A-Z ! ? /（因为 <+ 字母可能是一个 html 标签的开始，</ <? 可能是正文 </ 可能是闭合标签）
第二种: = ” ‘ > (字符串用 ” 或 ’ 包裹 标签属性用 = 号链接 > 可能是标签闭合)
第三种: \n \f \r \t \0 空格 (这些是没意义的字符，须要被跳过)

间接上代码:

void strExtractTestAvx2(char* ms ,unsigned int length) {

    // 低四位的转换
    __m256i vpshufbCharMaskn = _mm256_setr_epi64x(0x1303030303130bc2L, 0x0d21a18101838303L, 0x1303030303130bc2L, 0x0d21a18101838303L);
    // 高四位的转换
    __m256i vpshufbCharMaskh = _mm256_setr_epi64x(0x0201020124580080L, 0, 0x0201020124580080L, 0);
    // 字符类型判断
    __m256i alphaMask = _mm256_set1_epi8(0b00001111);
    __m256i constructMask = _mm256_set1_epi8(0b00110000);
    __m256i emptyMask = _mm256_set1_epi8(0b11000000);
    // 全 0
    __m256i zero = _mm256_set1_epi64x(0);
    // 每个字节高四地位 0
    __m256i vpshufbMask = _mm256_set1_epi64x(0x0f0f0f0f0f0f0f0fL);

    const unsigned int length1 = length - 31;

    for (int i = 0; i < length1; i += 32)
    {__m256i ymm1 = _mm256_lddqu_si256((__m256i*) & ms[i]);

        __m256i ymm2 = _mm256_srli_epi16(ymm1, 4);
        ymm2 = _mm256_and_si256(ymm2, vpshufbMask);
        __m256i ymm3 = _mm256_shuffle_epi8(vpshufbCharMaskn, ymm1);
        ymm2 = _mm256_shuffle_epi8(vpshufbCharMaskh, ymm2);
        ymm3 = _mm256_and_si256(ymm3, ymm2);
        
        __m256i  alpha = _mm256_and_si256(ymm3, alphaMask);
        __m256i construct = _mm256_and_si256(ymm3, constructMask);
        __m256i  empty = _mm256_and_si256(ymm3, emptyMask);
        // <
        __m256i less = _mm256_cmpeq_epi8(ymm1, lessSignMask);

        // 字母 ? ! /
        alpha = _mm256_cmpgt_epi8(alpha, zero);
        
        //= " ' >
        construct = _mm256_cmpgt_epi8(construct, zero);

        empty = _mm256_srli_epi64(empty, 1);
        // 6 种空格
        empty = _mm256_cmpgt_epi8(empty, zero);

    }
}