如何在 ARM7 上执行模运算？

Question

我在 ARM7 上做模数时遇到很多麻烦。

目前，我有这个代码：

ADD R0,R0,R1
MOV R0, R0 MOD 2
BX LR

但这根本不起作用。

从我的同学所做的来看，我们应该通过位移来完成，但我不明白这是如何工作的。

Answer 1

事实上，您的语法不正确。尽管大多数（全部？）ARM 汇编器都支持该运算符，但它仅在两个操作数均为汇编时间常量MOD时才有效。它只进行汇编时算术和常量表达式折叠。所以，你可以这样做：

mov  r0, #11 MOD 3     ; R0 = 2 = (11 % 3)

本质上会转化为：

mov  r0, #2

从而将值 2 移入寄存器R0。

这很好，因为它允许您对声明的常量（用于提高可读性）执行取模，还可以编写表达式，使它们易于人类阅读，从而更易于维护。

但是，当您处理寄存器、变量或任何非汇编时间常量的内容时，它不起作用。

根据问题中的代码，您似乎正在将寄存器的内容添加R1到寄存器中R0，然后尝试计算R0模 2。

假设整数是unsigned，那就很简单：

add  r0, r0, r1     ; R0 = (R0 + R1)
and  r0, r0, #1     ; R0 = (R0 & 1)
bx   lr

这是有效的，因为x % 2它相当于x & 1无符号整数。一般来说，只要（除数）是2的幂x % n就相当于。这不仅更容易编写，而且也是一种性能优化，因为按位运算比除法更快。x & (n - 1) n

现在您已经知道了以 2 的幂为模的模式，您可以轻松地执行以下操作(r0 + r1) % 4：

add  r0, r0, r1     ; R0 = (R0 + R1)
and  r0, r0, #3     ; R0 = (R0 & 1)
bx   lr

如果你想对一个不是2的幂的常数取模，那么事情会变得更加复杂。我不会尝试在汇编中用手写出来。相反，我想看看编译器会生成什么。(r0 + r1) % 3这是您在汇编中执行的方式：

add     r0, r0, r1           ; R0 = (R0 + R1)
movw    r3, #43691           ; \ R3 = 0xAAAAAAAB
movt    r3, 43690            ; /
umull   r2, r3, r3, r0       ; R3:R2 = (R3 * R0)  [R3 holds upper and R2 holds lower bits of result]
lsrs    r3, r3, #1           ; R3 = (R3 >> 1)
add     r3, r3, r3, lsl #1   ; R3 = (R3 + R3 * 2)
subs    r0, r0, r3           ; R0 = (R0 - R3)
bx      lr

编译器已生成优化代码来计算整数模数。它没有进行完全除法，而是将其转换为乘以一个幻数（乘法逆元）。这是来自 Hacker's Delight 的标准技巧，也是许多编译器使用的常见强度降低优化。

到目前为止，我们已经了解了无符号整数类型的模运算。当您想对有符号整数进行模运算时该怎么办？那么，您需要考虑符号位（即 MSB）。

对于(r0 + r1) % 2，其中r0和r1是带符号的，因此r0 + r1产生带符号的结果：

adds   r0, r0, r1     ; R0 = (R0 + R1)   <-- note "s" suffix for "signed"
and    r0, r0, #1     ; R0 = (R0 & 1)    <-- same as before for unsigned
it     mi             ; conditionally execute based on sign bit (negative/minus)
rsbmi  r0, r0, #0     ; negate R0 if signed (R0 = abs(R0))
bx     lr

这与我们用于无符号模数的代码非常相似，除了IT+RSBMI指令根据输入值是否为负（换句话说，取绝对值）进行条件否定。

（您在问题中只指定了 ARMv7，而不是您的目标配置文件。如果您的芯片具有“A”（应用程序）配置文件，则可以省略该IT指令。但否则，您的目标是 Thumb-2 指令集，这不会不支持非分支指令的条件执行，因此您需要在指令IT之前添加RSBMI。请参阅Thumb-2 中的条件执行。）

不幸的是，计算(r0 + r1) % 4并不是改变AND指令的常量操作数那么简单。您需要更多代码，即使是对常数 2 的幂进行模运算。再次询问编译器如何做到这一点。一定要向编译器询问非 2 的幂的有符号模。

如果你想对两个变量进行一般的模运算，事情会困难得多，因为你不能简单地使用位旋转。C 编译器将发出对库函数的调用：

UnsignedModulo(unsigned int i, unsigned int j, unsigned int m):
    push    {r3, lr}
    add     r0, r0, r1
    mov     r1, r2
    bl      __aeabi_uidivmod
    mov     r0, r1
    pop     {r3, pc}

SignedModulo(int i, int j, int m):
    push    {r3, lr}
    add     r0, r0, r1
    mov     r1, r2
    bl      __aeabi_idivmod
    mov     r0, r1
    pop     {r3, pc}

在这里，GCC 调度到__aeabi_uidivmod无符号库函数和__aeabi_idivmod有符号模/除法库函数。其他编译器将有自己的库函数。

不要尝试在汇编中手动编写此类代码。这根本不值得付出努力。如有必要，从 C 编译器的标准库中提取该函数，并调用它来完成繁重的工作。（你的老师并不希望你这样做。）