不带 neon 的 arm assembly 中的 popcount

lb3vh1jj  于 2022-11-13  发布在  其他
关注(0)|答案(1)|浏览(111)

我已经阅读了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

我目前正在求解this problem,迄今为止我最正确的解决方案在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条指令)
1.我需要LDR指令,因为常量对于立即(4个指令)来说太大了,而且没有旋转会起作用。
1.我需要从函数返回(1条指令)
1.氖SIMD指令不可用(我尝试过)
这正是每次测试的7条额外指令。

您将如何继续执行仅12条指令?

jslywgbw

jslywgbw1#

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个周期。调度是关键,以便尽可能多的指令获得双发布。

相关问题