Hamming重量(数为1)将C与装配混合

Question

我想数一数一个数组中有多少个数字。

首先，我有一个用C lenguaje编写的代码(工作正常)：

int popcount2(int* array, int len){
    int i;
    unsigned x;
    int result=0;
    for (i=0; i<len; i++){
        x = array[i];
        do{
           result+= x & 0x1;
           x>>= 1;
       } while(x);
    }
return result;
}

现在，我需要使用3-6行代码将do-while循环转换为Assembly。我写了一些代码，但结果不正确。(我是装配界的新手)

int popcount3(int* array, int len){
int  i;
unsigned x;
int result=0;   
for (i=0; i<len; i++){
    x = array[i];
    asm(
    "ini3:               \n"
        "adc $0,%[r]     \n"
        "shr %[x]        \n"
        "jnz ini3        \n"

        : [r]"+r" (result)
        : [x] "r" (x)       );
  }
}

我正在使用GCC (在linux上)与英特尔处理器。

Answer 1

您是从一个非常低效的算法开始--如果您使用了更好的算法，那么您可能不需要在汇编程序上浪费时间。有关更有效的方法，请参见黑客之乐和/或钻头缠绕式黑客。

还请注意，较新的x86 CPU有一个POPCNT指令，它在一条指令中完成上述所有操作(您也可以使用通过一个内在的，因此不需要使用通过一个内在的)。

最后，gcc有一个内置的：__builtin_popcount，它同样可以满足您的需要--它将在较新的CPU上使用POPCNT，在旧CPU上使用等效的asm。

Answer 2

当我需要创建一个popcount时，我最终使用了钻头缠绕式黑客 @PaulR中提到的5和3的方法。但如果我想用循环来做这件事，也许是这样的：

#include <stdio.h>
#include <stdlib.h>

int popcount2(int v) {
   int result = 0;
   int junk;

   asm (
        "shr $1, %[v]      \n\t"   // shift low bit into CF
        "jz done           \n"     // and skip the loop if that was the only set bit
     "start:               \n\t"
        "adc $0, %[result] \n\t"   // add CF (0 or 1) to result
        "shr $1, %[v]      \n\t"
        "jnz start         \n"     // leave the loop after shifting out the last bit
     "done:                \n\t"
        "adc $0, %[result] \n\t"   // and add that last bit

        : [result] "+r" (result), "=r" (junk)
        : [v] "1" (v)
        : "cc"
   );

   return result;
}

int main(int argc, char *argv[])
{
   for (int x=0; x < argc-1; x++)
   {
      int v = atoi(argv[x+1]);

      printf("%d %d\n", v, popcount2(v));
   }
}

adc几乎总是比在CF上分支更有效。

"=r" (junk)是一个虚拟输出操作数，它与v ( "1"约束)位于同一个寄存器中。我们使用它来告诉编译器，asm语句破坏了v输入。我们本可以使用[v] "+r"(v)来获得读写操作数，但是我们不希望C变量v被更新。

请注意，此实现的循环行程计数是最高设置位的位置。(bsr，或32 - clz(v))。@rcgldr的实现(每次迭代清除最低的set位)通常在set位数较低时会更快，但它们并不都接近整数的底部。

Answer 3

使用3-6行代码进行组装。

这个例子使用了一个4指令循环：

popcntx proc    near
        mov     ecx,[esp+4]             ;ecx = value to popcnt
        xor     eax,eax                 ;will be popcnt
        test    ecx,ecx                 ;br if ecx == 0
        jz      popc1
popc0:  lea     edx,[ecx-1]             ;edx = ecx-1
        inc     eax                     ;eax += 1
        and     ecx,edx                 ;ecx &= (ecx-1)
        jnz     short popc0
popc1:  ret
popcntx endp

此示例使用3指令循环，但它将比大多数处理器上的4指令循环版本慢。

popcntx proc    near
        mov     eax,[esp+4]             ;eax = value to popcnt
        mov     ecx,32                  ;ecx = max # 1 bits
        test    eax,eax                 ;br if eax == 0
        jz      popc1
popc0:  lea     edx,[eax-1]             ;eax &= (eax-1)
        and     eax,edx
        loopnz  popc0
popc1:  neg     ecx
        lea     eax,[ecx+32]
        ret
popcntx endp

这是另一个非循环的例子：

popcntx proc    near
        mov     ecx,[esp+4]             ;ecx = value to popcnt
        mov     edx,ecx                 ;edx = ecx
        shr     edx,1                   ;mov upr 2 bit field bits to lwr
        and     edx,055555555h          ; and mask them
        sub     ecx,edx                 ;ecx = 2 bit field counts
                                        ; 0->0, 1->1, 2->1, 3->1
        mov     eax,ecx
        shr     ecx,02h                 ;mov upr 2 bit field counts to lwr
        and     eax,033333333h          ;eax = lwr 2 bit field counts
        and     ecx,033333333h          ;edx = upr 2 bit field counts
        add     ecx,eax                 ;ecx = 4 bit field counts
        mov     eax,ecx
        shr     eax,04h                 ;mov upr 4 bit field counts to lwr
        add     eax,ecx                 ;eax = 8 bit field counts
        and     eax,00f0f0f0fh          ; after the and
        imul    eax,eax,01010101h       ;eax bit 24->28 = bit count
        shr     eax,018h                ;eax bit 0->4 = bit count
        ret
popcntx endp