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