Programming 版 (精华区)

发信人: SwordLea (飞刀李), 信区: Programming
标  题: [程序大战]20040720 第2小板凳
发信站: 哈工大紫丁香 (Thu Jul 22 11:43:56 2004), 转信

为使比较二次确定是否符合条件减少至一次比较，使用了hash表进行字符范围匹配。

void StrFilter(LPBYTE pBuffer, DWORD dwFileSize, int nLen, CString &sResult)
{
    // 2004-7-22
    bool hashTable[256] = {false};  // 比较用hash表
    for (int k = 32; k <= 126; k ++) hashTable[k] = true;
    std::vector<Filter> vFilter;
    DWORD dwID = 0;
    int len = 0;
    for (DWORD i = 0; i < dwFileSize; i ++)
    {
        // 2004-7-22
        BYTE ch = *(pBuffer + i);
        for(int len = 0; hashTable[ch]; len ++)
            ch = *(pBuffer + i + len);

        // 2004-7-21 代码
        /*      
        BYTE ch = *(pBuffer + i);
        for(int len = 0; ch >= 32 && ch <= 126; len ++)
            ch = *(pBuffer + i + len);
        //*/

        if (len > nLen)
        {
            // 长度合格
            Filter f;
            f.dwID = dwID ++;
            f.dwOffset = i ;
            f.lpString = new char[len];
            if (!f.lpString ) return ;
            strncpy(f.lpString , (LPCTSTR)pBuffer + i, --len);
            f.lpString[len] = 0;
            f.nLength = len;
            vFilter.push_back(f);
        }
        i += len;
    }
    std::vector<char> vBuffer;
    for (PFilter p = vFilter.begin(); p != vFilter.end(); p ++)
    {
        CString sBuf;
        sBuf.Format("%u: Offset:%u   Length:%d\t%s\r\n",
                p->dwID, p->dwOffset, p->nLength,p->lpString);

        for ( int j = 0; j < sBuf.GetLength(); j ++)
                vBuffer.push_back(sBuf.GetAt(j));

        delete(p->lpString);
    }
    vBuffer.push_back(0);
    sResult = &vBuffer[0];
}

耗时：35361 ms 

居然比前次27851ms 耗时还多，遂进行反汇编代码比较：
------------------------------------------------------------------
      for(int len = 0; ch >= 32 && ch <= 126; len ++)
            ch = *(pBuffer + i + len);

; ************************************************************
.text:004015A0                 cmp     al, 20h         ; < 32 ?
.text:004015A2                 jb      short loc_4015B0
                               ~~~~~~~~~~~~~~~~~~~~~~~~ 比较 1
.text:004015A4 loc_4015A4:                            
.text:004015A4                 cmp     al, 7Eh         ; > 126 ?
.text:004015A6                 ja      short loc_4015B0
                               ~~~~~~~~~~~~~~~~~~~~~~~~ 比较 2
.text:004015A8                 mov     al, [edi+esi]
.text:004015AB                 inc     esi
.text:004015AC                 cmp     al, 20h
.text:004015AE                 jnb     short loc_4015A4
                               ~~~~~~~~~~~~~~~~~~~~~~~~ 比较 3
.text:004015B0 loc_4015B0:                             
------------------------------------------------------------------
        for(int len = 0; hashTable[ch]; len ++)
             ch = *(pBuffer + i + len);
; ************************************************************
.text:004015D6                 mov     byte ptr [esp+558h+var_544], dl
.text:004015DA                 mov     ecx, [esp+558h+var_544]
.text:004015DE                 and     ecx, 0FFh
.text:004015E4                 cmp     [esp+ecx+558h+var_50C], bl
                                       ~~~~~~~~~~~~~~~~~~~~~~~~ !!!
.text:004015E8                 jz      short loc_401602
                               ~~~~~~~~~~~~~~~~~~~~~~~~ 比较 1
.text:004015EA loc_4015EA:                             
.text:004015EA                 mov     dl, [edi+esi]
.text:004015ED                 inc     esi
.text:004015EE                 mov     byte ptr [esp+558h+var_544], dl
.text:004015F2                 mov     ecx, [esp+558h+var_544]
.text:004015F6                 and     ecx, 0FFh
.text:004015FC                 cmp     [esp+ecx+558h+var_50C], bl
                                       ~~~~~~~~~~~~~~~~~~~~~~~~ !!!
.text:00401600                 jnz     short loc_4015EA
                               ~~~~~~~~~~~~~~~~~~~~~~~~ 比较 2
; ************************************************************
.text:00401602 loc_401602:  

问题就出现在惊讶叹号部分的代码！
修改以后，虽然比较次数减少了，但由于引入了间接寻址，效率低于直接寻址。
--
    I came, I saw, I conquered ! — Caesar


※ 修改:·SwordLea 于 Jul 22 14:15:06 修改本文·[FROM: 202.118.246.241]
※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: 202.118.246.241]