在一个DWORD数组中找到最重要的DWORD

Question

我希望找到DWORD数组中最重要的非零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:
    }
}

这些函数应该用于预选数据，这些数据将相互比较。因此，它需要具有高性能。

有人知道更好的算法吗？

- 0xbadf00d

---

查看 BitScanReverse http://msdn.microsoft.com/en-US/library/fbxyd7zd(v=VS.80).aspx 或者 __builtin_clz （对于非微软平台）。 - FigmentEngine

感谢您的回答。首先，_BitScanRever和_BitScanForward返回最高位和最低位（我想获取一个字节或双字）。其次，这些函数使用bsf和bsr指令..没有其他的。 - 0xbadf00d

Answer 1

我认为你只是在寻找给定数组中第一个非零单词。我肯定会选择用C语言编写的简单循环。如果有某些原因使这个过程变得超级关键，我建议你查看程序的更大上下文，并问一些问题，例如为什么需要从数组中找到非零对象，为什么不能已经知道它的位置。

- Antti Huima