2

我试图计算一个数组中有多少个数字 1。

首先，我在 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 循环转换为汇编。我写了一些代码，但结果不正确。（我是汇编世界的新手）

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 上）。

4

4 回答 4

4

您从一个非常低效的算法开始 - 如果您使用更好的算法，那么您可能不需要在汇编程序上浪费时间。有关更有效的方法，请参阅Hacker's Delight和/或Bit Twiddling Hacks 。

另请注意，较新的 x86 CPU 有一条POPCNT指令，它在一条指令中完成上述所有操作（您也可以通过内部函数调用它，因此不需要 asm）。

最后 gcc 有一个内置的: __builtin_popcount，它再次满足您的所有需求 - 它将在较新的 CPU 上使用POPCNT，在较旧的 CPU 上使用等效的 asm。

于 2014-11-20T22:18:04.043 回答
3

当我需要创建 popcount 时，我最终使用了来自Bit Twiddling Hacks @PaulR 提到的 5's 和 3's 方法。但是如果我想用一个循环来做这个，也许是这样的：

#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)获取读写操作数，但我们不希望v更新 C 变量。

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

于 2014-11-21T02:28:41.053 回答
2

汇编使用 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
于 2014-11-21T13:02:33.437 回答
1

您可以做的最好的想法是使用Paul R 建议的内置popcount函数，但是由于您需要在汇编中编写它，这对我有用：

asm (
"start:                  \n"
        "and %0, %1      \n"
        "jz end          \n"
        "shr $0, %1      \n"
        "jnc start       \n"
        "inc %1          \n"
        "jmp start       \n"
"end:                    \n"
        : "+g" (result),
          "+r" (x)
        :
        : "cc"
);

在前两行中，您只需检查x（如果为零，则转到 end Jump Zero）的内容。比你x向右移动一位并且：

在移位操作结束时，CF标志包含从目标操作数移出的最后一位。*

如果没有CF设置，只需转到开始（Jump Not Carry），否则增加结果然后开始。

组装的美妙之处在于您可以通过多种方式做事……

asm (
"start:                  \n"
        "shr $1, %1      \n"
        "jnc loop_cond   \n"
        "inc %0          \n"
        "and %1, %1      \n"
"loop_cond:              \n"
        "jnz start       \n"

        : "+g" (result),
          "+r" (x)
        :
        : "cc"
);

在这里您再次使用SHift Right指令，如果不CF存在，则进入循环条件。

否则再次增加结果并调用二进制AND（INC 确实修改ZF）。

使用LOOP和ECX

我很好奇如何在 3 条指令中做到这一点（如果不可能的话，我认为你的老师不会给你 3 的下限）并且我意识到 x86 也有LOOP指令：

每次执行 LOOP 指令时，计数寄存器递减，然后检查是否为 0。如果计数为 0，则终止循环并继续执行 LOOP 指令之后的指令。如果计数不为零，则执行近跳转到目标（目标）操作数，这可能是循环开始处的指令。*

您可以使用GCC 输入约束添加输入参数：

c-c登记册。

asm (
"start:              \n"
    "shr $1, %1      \n"
    "adc $0, %0      \n"
    "loop start      \n"

    : "+g" (result)
    : "r" (x),
      "c" (8)             // Assuming 8b type (char)
);

只是为了确保它编译为正确的程序集：

0x000000000040051f <+25>:   mov    $0x8,%ecx
0x0000000000400524 <+30>:   mov    -0x8(%rbp),%eax
0x0000000000400527 <+33>:   shr    %edx
0x0000000000400529 <+35>:   adc    $0x0,%eax
0x000000000040052c <+38>:   loop   0x400527 <main+33>

我认为第一个应该有更好的性能，特别是如果只有 1 位设置，这种方法总是k*8迭代。

SSE4 和单指令

我知道你必须使用循环，但只是为了好玩......使用SSE4 扩展，你可以通过一条指令来做到这一点POPCNT：

该指令计算第二个操作数（源）中设置为 1 的位数，并返回第一个操作数（目标寄存器）中的计数。*

我认为（我的笔记本电脑上有一个相当旧的 CPU，所以我无法为你测试这个）你应该能够只用一个简单的指令来做到这一点：

asm (   
    "POPCNT %1, %0   \n"
    : "=r" (result)
    : "mr" (x)
    : "cc"                                                                                                                                       
);

（如果你尝试这个并且你确实有 SSE4 扩展，请让我知道它是否有效）

表现

我测量了进行 100,000,000 次 popcounts 所需的时间，并将我的第一种和第二种方法与David Wohlferd 的. [原始数据] 

+--------------+------------+------------+------------+
|              | 0x00000000 | 0x80000001 | 0xffffffff |
+--------------+------------+------------+------------+
| 1st solution |  0.543     |  5.040     |  3.833     |
| LOOP         | 11.530     | 11.523     | 11.523     |
| Davids       |  0.750     |  4.893     |  4.890     |
+--------------+------------+------------+------------+

如果有人可以将这 3 个与 SSE4 的POPCNT指令进行比较，我会很高兴。

于 2014-11-20T23:45:22.190 回答