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

나는 주어진 배열에서 첫 번째 0이 아닌 단어를 찾고 있다고 생각한다. 나는 C로 쓰여진 간단한 루프로 갈 것입니다. 이것이 super의 중요한 이유가 있다면 프로그램의 더 큰 맥락을 살펴보고 예를 들어 물어 보는 것이 좋습니다. 배열에서 0이 아닌 객체를 찾아야하는 이유와 왜 그 위치를 이미 알 수 없는지에 대한 질문.