如何在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。

假设整数是无符号的，这很简单，如：

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

这是因为对于无符号整数，x % 2等价于x & 1。通常，只要x % n (除数)是2的幂，x & (n - 1)就等于n。这不仅更容易编写，而且也是性能优化，因为按位操作比除法更快。

现在您已经了解了模块化的模式，您可以轻松地执行(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

编译器生成了计算整数模数的优化代码。它没有进行完全除法，而是通过一个幻数(乘法逆)将其转化为乘法。这是哈克乐中的标准把戏和许多编译器使用的一种通用的强度缩减优化方法。

到目前为止，我们已经研究了对无符号整数类型的模块化操作。那么当你想对有符号整数做模运算时呢？那么，您需要考虑到符号位(也就是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指令。但是，否则，您的目标是拇指-2指令集，它不支持非分支指令的条件执行，因此您需要在IT指令之前使用RSBMI。见拇指条件执行-2.)

不幸的是，计算(r0 + r1) % 4并不是简单的更改AND指令的常量操作数的问题。您需要更多的代码，即使是模块化的常量幂为2。再说一遍，问编译器是怎么做的。绝对是问编译器的符号模的非幂二。

如果你想对两个变量做一个普通的模数运算，事情就会变得更加困难，因为你不能简单地使用位旋转。编译器将发出对库函数的调用。

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编译器的标准库中提取函数，并调用它来完成繁重的工作。(你的老师不指望你这么做。)