在AVR Studio中使用汇编确认寄存器中的值是否是3的倍数

Question

我想使用 AVR Studio 和汇编语言确定寄存器中的数字是否是 3 的倍数，但在 AVR ATmega 8515 上，所以没有 div 指令/语法

我已经尝试了几种方法，例如添加寄存器和 0b0011 期望设置进位标志，但事实并非如此。

Answer 1

所以一个直接的方法是让avr-gcc编译一段C代码，然后查看它生成的程序集¹：

对于 8 位无符号值，请考虑以下 C99：

#include <stdint.h>
#include <stdbool.h>

bool is_udiv3_8 (uint8_t x)
{
    return x % 3 == 0;
}

用类似的东西

> avr-gcc x.c -mmcu=atmega8515 -O2 -S

我们得到

x.s

（或者，将

-save-temps

添加到普通编译中，然后截取*.s文件）。

is_udiv3_8:
    ldi r25,lo8(-85) ;1
    mul r24,r25      ;2
    mov r25,r1       ;3
    clr __zero_reg__ ;4
    lsr r25          ;5
    mov r18,r25      ;6
    lsl r18          ;7
    add r25,r18      ;8
    ldi r18,lo8(1)   ;9
    cpse r24,r25     ;10
    ldi r18,0        ;11
    mov r24,r18      ;12
    ret

avr-gcc 的作用是将输入与 -256/3 相乘，并以乘积的高字节作为除以 3 后的商。经过一番调整，如果输入能被整除，则在 R24 中返回 True (1) 3 且 False (0)，否则。

您可以将其扩展到 16 位值，但您需要 16×16=32 乘法的高位字。

此时您还记得²，以 B 为基数的自然数 N 可以被 B+1 整除，当且仅当以 B 为基数的数字上的交替交叉和可以被 B+1 整除。

例如，在基 B=2 中：自然数 N 能被 3 整除，当且仅当 N 的各位的交替叉和能被 3 整除。

汇编编写：

• 首先对位进行循环以获得二进制交叉和。为了提高速度，您将展开该循环，这将获得 8

  sbrs

  和 8

  sbrc

  。

• 叉和q满足-8<= q <= 8. Negating does not change whether q is divisible by 3, thus continue with |q| which is non-negative.

• 减去 3，直到结果为 0、1 或 2。

• 如果值达到 0，则返回 True，否则返回 False（达到 1 或 2）。

.text
.global is_div3_asm

is_div3_asm:
    ;; R26 holds R25:R24 mod 3
    clr r26
.Loop_bits:
    ;; Loop over all bits of R25:R24 to compute the alternating cross sum
    ;; over the binary digits of R25:R24.
    sbiw r24, 0
    breq .Loop_done
    sbrc r24, 0 $ inc  r26
    sbrc r24, 1 $ dec  r26
    lsr  r25 $ ror r24
    lsr  r25 $ ror r24
    rjmp .Loop_bits
.Loop_done:
    ;; r26 = abs(r26)
    sbrc r26, 7
    neg  r26
    ;; Now we have 0 <= r26 <= 8, so reduce to r26 < 3...
    cpi  r26, 3
    brlt .Ltobool
    subi r26, 3
    ;; ...now we have 0 <= r26 <= 5, so at most one more sub 3 will do.
    cpi  r26, 3
    brlt .Ltobool
    subi r26, 3
.Ltobool:
    ;; Return a bool in R24 as of avr-gcc ABI.
    ldi r24, 1                  ; True
    cpi r26, 0
    breq .Ldone
    ldi r24, 0                  ; False
.Ldone:    
    ret

此函数符合 avr-gcc ABI 和调用约定。您可以通过原型在 C/C++ 中使用它

extern bool is_div3_asm (uint16_t); // C
extern "C" bool is_div3_asm (uint16_t); // C++

---

¹请注意，有不同的汇编方言。这个答案使用 GNU assemlby 方言，因为它与 GNU 汇编器兼容并由 avr-gcc 和 avr-g++ 生成。

²结果实际上更强：自然数 N 与 B+1 模相同，就像 N 在基 B 中的交替叉和一样。证明只是几行模运算，归结为到 B == -1 mod B+1.

Answer 2

这只是对 @emacs 让我发疯的答案的一点评论和阐述，但对于 Stackoverflow 评论来说太长太复杂，因此这是一个社区 wiki Stackoverflow 答案。

我在 godbolt.org 上使用不同版本的 avr-gcc（12.2.0 和 5.4.0）以及相同的编译选项（

-std=c99  -O2 -g -mmcu=atmega8515

）编译了 8、16、24 和 32 位版本。事实证明，avr-gcc 12.2.0 生成的代码明显短于 avr-gcc 5.4.0 生成的代码。

由于 @emacs 让我发疯的答案 可以解决 avr-gcc 5.4.0 中相对复杂的代码，因此查看 12.2.0 中更简单的代码也可能很有用。

avr-gcc 5.4.0 的

uint8_t

变体似乎是 @emacs 让我发疯的答案 的作用：

is_udiv8_by_3:
        ldi r25,lo8(-85)  /* 1 */
        mul r24,r25       /* 2 */
        mov r25,r1        /* 1 */
        clr __zero_reg__  /* 1 */
        lsr r25           /* 1 */
        mov r18,r25       /* 1 */
        lsl r18           /* 1 */
        add r25,r18       /* 1 */
        ldi r18,lo8(1)    /* 1 */
        cpse r24,r25      /* 1 */
        ldi r18,0         /* 1 */
        mov r24,r18       /* 1 */
        ret               /* 13 cycles plus ret */

avr-gcc 12.2.0 的

uint8_t

变体：

is_udiv8_by_3:
        ldi r25,lo8(-85)  /* 1 */
        mul r24,r25       /* 2 */
        mov r25,r0        /* 1 */
        clr r1            /* 1 */
        ldi r24,lo8(1)    /* 1 */
        cpi r25,lo8(86)   /* 1 */
        brlo .L2          /* 2/1 */
        ldi r24,0         /* -/1 */
.L2:
        ret               /* 9 cycles plus ret */

avr-gcc 12.2.0 中的

uint16_t

变体并不比 avr-gcc 5.4.0 中的

uint8_t

变体长很多：

is_udiv16_by_3:
        ldi r20,lo8(-85)  /* 1 */
        ldi r21,lo8(-86)  /* 1 */
        mul r24,r20       /* 2 */
        movw r18,r0       /* 2 */
        mul r24,r21       /* 2 */
        add r19,r0        /* 1 */
        mul r25,r20       /* 2 */
        add r19,r0        /* 1 */
        clr r1            /* 1 */
        ldi r24,lo8(1)    /* 1 */
        cpi r18,86        /* 1 */
        sbci r19,85       /* 1 */
        brlo .L5          /* 2/1 */
        ldi r24,0         /* -/1 */
.L5:
        ret               /* 18 cycles plus ret */

顺便说一句，来自

@emacs 的 

is_div3_asm 函数的周期计数让我发疯 取决于输入值，即使对于

.Loop_bits

循环的单次迭代也会超过 18 个周期。

当将类型大小增加到 24 位（

__uint24

变体）和 32 位时，avr-gcc 12.2.0 最终开始调用除法函数

__udivmodpsi4

:

is_udiv24_by_3:
        ldi r18,lo8(3)
        ldi r19,0
        ldi r20,0
        rcall __udivmodpsi4
        ldi r24,lo8(1)
        or r18,r19
        or r18,r20
        breq .L7
        ldi r24,0
.L7:
        ret

uint32_t

调用不同的除法函数

__udivmodsi4

并且也更长：

is_udiv32_by_3:
        push r28
        push r29
        rcall .
        rcall .
        in r28,__SP_L__
        in r29,__SP_H__
        ldi r18,lo8(3)
        ldi r19,0
        ldi r20,0
        ldi r21,0
        rcall __udivmodsi4
        std Y+1,r22
        std Y+2,r23
        std Y+3,r24
        std Y+4,r25
        ldi r24,lo8(1)
        ldd r18,Y+1
        ldd r19,Y+2
        ldd r20,Y+3
        ldd r21,Y+4
        or r18,r19
        or r18,r20
        or r18,r21
        breq .L12
        ldi r24,0
.L12:
        pop __tmp_reg__
        pop __tmp_reg__
        pop __tmp_reg__
        pop __tmp_reg__
        pop r29
        pop r28
        ret

因此寻找其他算法，例如来自 @emacs 的替代交叉和算法让我发疯的答案或快速整除测试（按 2,3,4,5,.., 16）？@Peter Cordes 链接到仅对于 16 位以上的整数大小看起来很有趣。

需要更仔细地考虑代码大小和循环周期。