查找DWORD数组中最重要的DWORD

Question

我想要找到DWORD数组中不等于0的最重要的DWORD。该算法应针对最大128字节的数据大小进行优化。

我创建了三个不同的函数，它们都返回特定DWORD的索引。

unsigned long msb_msvc(long* dw, std::intptr_t n)
{
    while( --n )
    {
        if( dw[n] )
            break;
    }
    return n;
}

static inline unsigned long msb_386(long* dw, std::intptr_t n)
{
    __asm 
    {
        mov ecx, [dw]
        mov eax, [n]

__loop: sub eax, 1
        jz  SHORT __exit
        cmp DWORD PTR [ecx + eax * 4], 0
        jz  SHORT __loop
__exit:
    }
}

static inline unsigned long msb_sse2(long* dw, std::intptr_t n)
{
    __asm 
    {
        mov  ecx, [dw]
        mov  eax, [n]
        test ecx, 0x0f
        jnz  SHORT __128_unaligned

__128_aligned:
        cmp      eax, 4
        jb       SHORT __64
        sub      eax, 4
        movdqa   xmm0, XMMWORD PTR [ecx + eax * 4]
        pxor     xmm1, xmm1
        pcmpeqd  xmm0, xmm1
        pmovmskb edx, xmm0
        not      edx
        and      edx, 0xffff
        jz       SHORT __128_aligned
        jmp      SHORT __exit

__128_unaligned:
        cmp      eax, 4
        jb       SHORT __64
        sub      eax, 4
        movdqu   xmm0, XMMWORD PTR [ecx + eax * 4]
        pxor     xmm1, xmm1
        pcmpeqd  xmm0, xmm1
        pmovmskb edx, xmm0
        not      edx
        and      edx, 0xffff
        jz       SHORT __128_unaligned
        jmp      SHORT __exit

__64:
        cmp      eax, 2
        jb       __32
        sub      eax, 2
        movq     mm0, MMWORD PTR [ecx + eax * 4]
        pxor     mm1, mm1
        pcmpeqd  mm0, mm1
        pmovmskb edx, mm0
        not      edx
        and      edx, 0xff
        emms
        jz       SHORT __64
        jmp      SHORT __exit

__32:
        test eax, eax
        jz   SHORT __exit
        xor  eax, eax
        jmp  __leave ; retn

__exit:
        bsr      edx, edx
        shr      edx, 2
        add eax, edx

__leave:
    }
}

应该使用这些函数来预先选择要相互比较的数据。因此，它需要有性能。

有人知道更好的算法吗？

Answer 1

我认为您只是在寻找给定数组中的第一个非零字。我肯定会用C编写一个简单的循环。如果这是超级性能关键的原因，我会建议你在程序的更大范围内寻找，例如，为什么你需要从数组中找到非零对象，为什么你不能知道它的位置。