共计 3081 个字符，预计需要花费 8 分钟才能阅读完成。
最近看到 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);
}
}