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

Question

我已经阅读了这篇文章以及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操作
• CCD_ 2(无符号绝对差之和为8位(为零，完成了添加4位字节的任务

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

Answer 2

可以重写15条类似的指令

popcount：

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