Posted on 2011-10-27 04:02
djx_zh 阅读(3898)
评论(0) 编辑 收藏 引用
SSE4.2指令集提供了字符串处理指令，详细用法可参阅intel开发手册。现简单说明一下几个指令的用法，因为我们一般用c接口来开发程序，所以我们主要关注C接口的用法。
首先看int _mm_cmpistri ( __m128i a, __m128i b, const int mode); 因为本文讲述串匹配，所以我们把mode的值设为0xc0. 输入a,b是以0结尾的字符串。这条指令将返回[0, 16]之间的一个整数。如果在b的后缀中发现了a的前缀，这个整数用来表示这个后缀的位置； 如果没发现，返回值为16. 例如 a="EFGHX", b="abcdefghABCDEFGH"
0123456789ABCDEF(index)
b = abcdefghABCDEFGH
a = EFGHX
返回值为12.
再比如 a="abcde"
0123456789ABCDEF(index)
b = abcdefghABCDEFGH
a = abcde
返回值为0.
如果a="ABCE",则返回值为16.
__m128i _mm_cmpistrm ( __m128i a, __m128i b, const int mode); 这条指令返回的是mask，不像_mm_cmpistri那样返回一个值。
例如 a="abcd", b="abcdefghABCDEabc"
0123456789ABCDEF(index)
b = abcdefghABCDEabc
a = abcd
abc
ret=1000000000000100（1表示本字节所有位都是1， 即本字节为0xFF)
一个很自然的想法就是根据返回值在文本串中移动(返回n则往后移动n个字符)，直到返回值为0. 仔细阅读glibc中用SSE4.2指令集做的strstr函数，就会发现他采用了此种方法。 此方法的问题在于每次从文本串中加载16个字节到sse寄存器时，地址是不对齐的，极大的影响了执行效率。怎样才能保证每次加载时的地址都是对齐的呢？
我的方法是每次移动16字节，然后从前一个块（16字节块）中找后缀，从后一个块中找前缀，然后看前面块的后缀和后面块的前缀能不能组合成我们要查找的字串。实验表明此算法要优于前一种算法.
alignStart:
{
if(plen <= 16){
shf_indexV = SIMD_LOAD(IndexVector[plen]);
__attribute__ ((aligned (16))) char pbuf[16];
int i=0, j=0;
for(i =0;i<16-plen ;i++){
pbuf[i] = 0xff;
}
for(;i<16;i++)
pbuf[i] = pattern[j++];
sseiPattern2 = SIMD_LOAD(pbuf);
}
}
sseiPattern = SIMD_LOADU(pattern);
sseiWord0 = SIMD_LOAD(sseiPtr) ;
pref = SEARCH_PRE_F(sseiPattern, sseiWord0);
ret_z = has_byte_null(sseiWord0);
while(!ret_z){
//! find out the prefix
__m128i postmV2;
__m128i flagV;
u32 flag16;
while(( pref==16)&&( ret_z ==0)){
sseiPtr ++;
sseiWord0 = SIMD_LOAD(sseiPtr) ;
ret_z = has_byte_null(sseiWord0);
pref = SEARCH_PRE_F(sseiPattern, sseiWord0);
}
if(pref <= 16 - plen){
REPORT((((char*)sseiPtr)+pref));
}
premV = SEARCH_PRE_M(sseiPattern, sseiWord0);
sseiPtr ++;
sseiWord0 = SIMD_LOAD(sseiPtr) ;
postmV = SEARCH_PRE_M(sseiWord0, sseiPattern2);
postmV2= bit_reverse(postmV);
flagV = SS_XAND(premV, postmV2);
flag16 = SS_GET_MASK(flagV);
if(flag16){
int idx = bsf(flag16);
REPORT((((char*)sseiPtr)-16+idx));
}
pref = SEARCH_PRE_F(sseiPattern, sseiWord0);
ret_z = has_byte_null(sseiWord0);
}
相关宏的定义如下
#define SEARCH_PRE_F(s2,s1) _mm_cmpistri(s2,s1,0x0c)
#define SEARCH_PRE_M(s2,s1) _mm_cmpistrm(s2,s1,_SIDD_UNIT_MASK|_SIDD_CMP_EQUAL_ORDERED)
#define SIMD_LOAD(p) _mm_load_si128((__m128i*)(p))
#define SIMD_LOADU(p) _mm_loadu_si128((__m128i*)(p))
#define SS_GET_MASK(V) _mm_movemask_epi8(V)
#define SS_XAND(s1,s2) _mm_and_si128(s1,s2)
#define bit_reverse(x) _mm_shuffle_epi8(x,shf_indexV)