Posted on 2011-10-27 04:02
djx_zh 閱讀(3999)
評論(0) 編輯 收藏 引用
SSE4.2指令集提供了字符串處理指令，詳細(xì)用法可參閱intel開發(fā)手冊。現(xiàn)簡單說明一下幾個指令的用法，因為我們一般用c接口來開發(fā)程序，所以我們主要關(guān)注C接口的用法。
首先看int _mm_cmpistri ( __m128i a, __m128i b, const int mode); 因為本文講述串匹配，所以我們把mode的值設(shè)為0xc0. 輸入a,b是以0結(jié)尾的字符串。這條指令將返回[0, 16]之間的一個整數(shù)。如果在b的后綴中發(fā)現(xiàn)了a的前綴，這個整數(shù)用來表示這個后綴的位置； 如果沒發(fā)現(xiàn)，返回值為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表示本字節(jié)所有位都是1， 即本字節(jié)為0xFF)
一個很自然的想法就是根據(jù)返回值在文本串中移動(返回n則往后移動n個字符)，直到返回值為0. 仔細(xì)閱讀glibc中用SSE4.2指令集做的strstr函數(shù)，就會發(fā)現(xiàn)他采用了此種方法。 此方法的問題在于每次從文本串中加載16個字節(jié)到sse寄存器時，地址是不對齊的，極大的影響了執(zhí)行效率。怎樣才能保證每次加載時的地址都是對齊的呢？
我的方法是每次移動16字節(jié)，然后從前一個塊（16字節(jié)塊）中找后綴，從后一個塊中找前綴，然后看前面塊的后綴和后面塊的前綴能不能組合成我們要查找的字串。實驗表明此算法要優(yōu)于前一種算法.
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);
}
相關(guān)宏的定義如下
#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)