Posted on 2011-10-27 04:02
djx_zh 閱讀(4014)
評論(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)