手臂组件中的popcount，没有霓虹灯

Question

我已阅读this以及wiki 我理解以下代码应该在 asm 中产生 12 条指令。

 i = i - ((i >> 1) & 0x55555555);        // add pairs of bits
 i = (i & 0x33333333) + ((i >> 2) & 0x33333333);  // quads
 i = (i + (i >> 4)) & 0x0F0F0F0F;        // groups of 8
 return (i * 0x01010101) >> 24;          // horizontal sum of bytes

我目前正在解决这个问题，迄今为止我最好的正确解决方案在 10 次测试中总共执行了 190 条指令（每个测试 19 条）。

// A test case to test your function with
.global _start
_start:
    mov r0, #5
    bl popcount
    1: b 1b    // Done

// Only your function (starting at popcount) is judged. The test code above is not executed.
    
popcount:

    PUSH    {r1,r2, r3, r4, r5, r6, r7, r8, r9, r10}
    
    ldr r2, =0x55555555 // 2bits
    ldr r3, =0x33333333 // 4bits
    ldr r4, =0x0F0F0F0F // 8bits
    ldr r6, =0x01010101 // 8bits
    
    
    //x -= (x >> 1) & m1;             //put count of each 2 bits into those 2 bits
    lsr r1, r0, #0x1 // one shift
    and r1, r1, r2
    sub r0, r0, r1

    //x = (x & m2) + ((x >> 2) & m2); //put count of each 4 bits into those 4 bits 
    lsr r1, r0, #0x2 // two shift
    and r1, r1, r3
    and r5, r0, r3  
    add r0, r5, r1
    
    //x = (x + (x >> 4)) & m4;        //put count of each 8 bits into those 8 bits 
    lsr r1, r0, #0x4 // two shift
    add r1, r1, r0
    and r0, r1, r4

    //return (i * 0x01010101) >> 24;
    mul r0, r0, r6
    lsr r0, r0, #0x18

    POP    {r1,r2, r3, r4, r5, r6, r7, r8, r9, r10}
    
    bx lr
    

目前最好的运行成绩是120条指令。但问题是：

1. 我需要压入/弹出而不是破坏寄存器（2条指令）
2. 我需要 LDR 指令，因为常量对于立即数（4 条指令）来说太大，而且没有旋转也不起作用。
3. 我需要从函数返回（1 条指令）
4. Neon SIMD 指令不可用（我尝试过）

这些正是每次测试的 7 条额外说明。

---

---

如何才能只执行 12 条指令？

Answer 1

movw    r1, #0x5555
movw    r2, #0x3333
movt    r1, #0x5555
movt    r2, #0x3333

and     r3, r0, r1
bic     r12, r0, r1

add     r0, r3, r12, lsr #1
movw    r1, #0x0f0f

and     r3, r0, r2
bic     r12, r0, r2
add     r0, r3, r12, lsr #2
movt    r1, #0x0f0f

add     r0, r0, r0, lsr #4
mov     r2, #0
and     r0, r0, r1
usad8   r0, r0, r2

bx      lr  

• 4+4 不会溢出 4 位，因此在添加之前不需要

  and

  操作。

• usad8

  （8 位绝对差的无符号和）为零可以增加 4 个字节。

上述例程在 Cortex-A8 上需要 12 个周期，在较弱的 Cortex-A7 上需要 15 个周期。调度是关键，以便尽可能多的指令得到双重发出。

Answer 2

我有理由优化 Cortex M4 的 popcount，并且我相信我找到的解决方案比之前分享的任何其他解决方案更小、更快：

0002fbe4 <_ZN3BitILj4EE8PopCountEm>:
   2fbe4:   f020 3355   bic.w   r3, r0, #1431655765 @ 0x55555555
   2fbe8:   eba0 0053   sub.w   r0, r0, r3, lsr #1
   2fbec:   f020 3333   bic.w   r3, r0, #858993459  @ 0x33333333
   2fbf0:   f000 3033   and.w   r0, r0, #858993459  @ 0x33333333
   2fbf4:   eb00 0093   add.w   r0, r0, r3, lsr #2
   2fbf8:   eb00 1010   add.w   r0, r0, r0, lsr #4
   2fbfc:   f020 330f   bic.w   r3, r0, #252645135  @ 0xf0f0f0f
   2fc00:   fb70 f003   usad8   r0, r0, r3
   2fc04:   4770        bx  lr

第一部分非常标准，可以映射到现有的解决方案。关键区别在于（新颖？）使用 usad8 并行添加字节：

来自原帖：

 i = (i + (i >> 4)) & 0x0F0F0F0F;        // groups of 8
 return (i * 0x01010101) >> 24;          // horizontal sum of bytes

出于解释目的，我将其分为：

 i = (i + (i >> 4));
 i &= 0x0F0F0F0F;
 return (i * 0x01010101) >> 24;          // horizontal sum of bytes

最后两行是每个字节低4位的水平和。

usad8 指令对每个字节的绝对差进行水平求和，您可以将最后两行重写为：

 i &= 0x0F0F0F0F;
 return usad8(i, 0);          // horizontal sum of bytes

但是更好的解决方案是利用指令的“绝对差异”部分。这两行可以简化为：

 return usad8(i, i & 0xf0f0f0f0);

这只会对低 4 位求和，因为

i & 0xf0f0f0f0

位将导致差异仅为低 4 位。

是的，仍然需要按位运算，但现在不需要零值寄存器。

请注意，这将不适用于共享的网站模拟器，因为该模拟器不支持 usad8 命令。

Answer 3

可以重写 15 条这样的指令

流行计数：

PUSH    {r1,r2, r3, r4, r5, r6, r7, r8, r9, r10}     

//x -= (x >> 1) & m1;             //put count of each 2 bits into those 2 bits
lsr r1, r0, #0x1 // one shift
and r1, r1, #0x55555555
sub r0, r0, r1

//x = (x & m2) + ((x >> 2) & m2); //put count of each 4 bits into those 4 bits 
lsr r1, r0, #0x2 // two shift
and r1, r1, #0x33333333
and r5, r0, #0x33333333
add r0, r5, r1

//x = (x + (x >> 4)) & m4;        //put count of each 8 bits into those 8 bits 
lsr r1, r0, #0x4 // two shift
add r1, r1, r0
and r0, r1, #0x0F0F0F0F

//return (i * 0x01010101) >> 24;
mul r0, r0, #0x01010101
lsr r0, r0, #0x18

POP    {r1,r2, r3, r4, r5, r6, r7, r8, r9, r10}

bx lr