assembly 需要使用程序集计算二进制中1的个数

ztyzrc3y  于 2022-12-13  发布在  其他
关注(0)|答案(3)|浏览(252)

我有一个任务,我应该计算我设置的奇数二进制1的数量,然后我需要在7段显示器上显示。
在代码中,我写了一个注解,说明我应该在什么地方执行此操作。
我正在与德州仪器msp430。我看了其他解决方案,但他们与C,而不是与组装,不幸的是不能想出如何做它的组装。

bis.b #11111111b, &P1DIR
       bic.b #11111111b, &P1OUT

loop_1:
       ; do stuff with &P1OUT
       call #delay
       ...

delay

       mov #0, R5
       mov #0, R4

odd_even:
           ;Over here i need to count number of 1's in binary but cant figure out how to do it
           jnz try
           jz delay_over

      ...
           ret
r3i60tvu

r3i60tvu1#

@rcgldr的答案对于16位或32位popcount是一个有用的开始。参见How to count the number of set bits in a 32-bit integer?了解一些bithack和其他算法,包括表查找。
您可以考虑使用4位查找表。MSP430移位比较慢(每位1个周期,如果没有MSP430 X,则每位1条指令)。或者使用较大的8位查找表。
或者循环设置位,用v &= v - 1;清除低位。在MSP430中,需要MOV、DEC和AND。如果通常只设置几个位,这很好,但它们通常是分散的。

但最简单、代码长度最小的方法是一次循环所有位。
如果您打算一次循环一位以保持简单紧凑,则需要利用进位标志,方法是移位到进位并使用ADDC(进位加)。

我试图编写C语言,编译器可以使用ADDC将其转换为不错的asm,但https://godbolt.org/z/2Ev2IC是我管理的最好的。愚者和clang对于MSP430来说并不太好,因为它们使用tmp = a+a; carry = tmp<a;习惯用法,而x86和大多数其他架构都可以识别。
总之,你一开始就想要asm:

;; simple naive bit-count.  Small code-size and not too slow for 8 bits

;; input in r12,  result: r11 = popcount(r12)
mov.w     #0, r11        ; retval = 0
.popcount_loop:          ; do{
    add.b   r12,r12          ; shift a bit into carry flag
    addc    #0, r11          ; add that bit to r11:  r11 += 0 + C

    tst.b    r12
    jnz   .popcount_loop ; } while( (uint8_t)r12 != 0);

add使用字节操作数大小意味着位7进入C,而不是位15。

我们可以改为使用右移将低位放入C标志,特别是当我们预计许多输入都是小数字时(所以非零位都是往低端)根据google发现的this copy of a MSP430 / MSP430X instruction-set reference,普通的MSP430没有右移,MSP430 X具有一些实际上以零移位“循环”,所以它们实际上是移位。但如果我们在运行之前确保C=0,就不需要这样做了。由于人口计数不会回绕,ADDC将可靠地为我们清除C。
我们可以将其优化为更少的 * 循环 * 内 * 指令(代码大小相同,但运行速度更快)。因为ADDC也写入标志,这意味着它必须在下一次迭代中。所以我们必须倾斜循环。我们可以剥离第一次迭代,并在循环外执行其ADD。之后我们不会检查零,但这没关系,为input = 0x80运行一次额外的迭代不是正确性问题,也不值得在上面花费额外的指令。

; simple looping popcount, optimized for small numbers (right shift)
; and optimized for fewer instructions inside the loop

;; input in r12,  result: r11 = popcount(r12)
xor.w     r11, r11        ; r11=0,  C=!Z=0.   (mov doesn't set flags; this saves a CLRC)

rrc.b     r12             ; C = lsb(r12);   r12 >>= 1  ; prep for first iter

.popcount_loop:            ; do{
    addc    #0, r11          ; result += C;  Clears C because r11 won't wrap
    rrc.b   r12              ; C = lsb(r12);   r12 >>= 1;  Z = (r12==0)
    jnz    .popcount_loop  ; } while( (uint8_t)r12 != 0);

    addc    #0, r11        ; we left the loop with the last bit still in C

如果你的输入值是零扩展的,你可以使用rrc.w r12,这样循环就可以处理8位或16位的值,但它并不慢,因为它仍然会在所有位向右移位后退出。
倾斜循环,剥离第一次迭代的前半部分和最后一次迭代的后半部分,只需要额外花费一条指令(而且它们仍然都是单字指令)。
你提到了奇/偶。**你实际上只想得到奇偶性吗?(人口计数是奇数还是偶数)?**这与所有位的水平XOR是一样的。

; Needs MSP430X for rrum, otherwise you can only shift by 1 bit per instruction

;; input in r12,  result: r12=parity(r12)
;; clobbers: r11
mov.b   r12, r11       ; copy the low byte, zero the upper byte of R11 (not that it matters)
rrum     #4, r11       ; costs 4 cycles for shift-count = 4
xor     r11, r12       ; low 4 bits ^= (high 4 bits >> 4)

mov.b   r12, r11
rrum     #2, r11       ; costs 2 cycles for shift-count = 2
xor     r11, r12       ; narrow again to 2 bits

mov.b   r12, r11
rrum    #1,  r11       ; costs 1 cycle for shift-count = 1.  
xor     r11, r12       ; narrow again to 2 bits

and      #1, r12       ; clear high garbage from the high bits.

; ret  if this isn't inline

你可以用一个循环来完成这个任务,例如,使用popcount循环并在最后执行and #1, r12
我觉得如果我们左移(先移4,然后移2),然后用add.b r12,r12执行最后一步(移1),也许可以保存指令,因为有符号溢出(V标志)= carry_in XOR carry_out for the sign bit。对于加法,两个输入相同,现有的符号位将始终是0+0=00或1+1=10,因此符号位= carry_in到符号位。
因此,对于r12.b = XY??????这样的位模式,add.b r12,r12设置V = X^Y,即输入的最高两位的水平XOR。因为Y是到MSB的进位输入,X是进位输出。
如果你想在其上分支,这将是很好的,但MSP430似乎没有一个jXX,在V上分支被设置或没有。(即有符号比较),但N将等于MSB,因此N ^ V只是C,在我们的左移位V设置V = N ^ C之后。我猜你必须从标志寄存器中取出标志字,并对其进行移位/掩码!或者测试该标志位和JNZ。

gkn4icbw

gkn4icbw2#

在大多数计算机上,没有硬件可以在几个指令中完成这一任务。
你要做的是一组掩码和移位:

unsigned char to_count, nbr=0, mask=0x1, m;
for (int i=0; i<8; i++) {
    m = to_count&mask ; //1 if LSB=1, 0 otherwise
    nbr += m;
    to_count >>=1 ;
}

对于更大的位数,您可以使用更聪明的策略以统计方式减少计算时间,但对于8位数,您将没有任何收益。

wooyq4lh

wooyq4lh3#

此逻辑可能比循环稍短:

unsigned char popcnt(unsigned char a)
{
    a = a - ((a >> 1) & 0x55);            // 2 bit fields 0 -> 2
    a = (a & 0x33) + ((a >> 2) & 0x33);   // 4 bit fields 0 -> 4
    a = (a & 0x0f) +  (a >> 4);           // a = bit count
    return a;
}

相关问题