How do I perform modulus on ARM7?

Question

I am having a lot of trouble doing modulus on ARM7.

Currently, I have this code:

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

But it doesn't work at all.

It seems from what my classmates have done that we are supposed to do it by bit shifts, but I don't understand how would this work.

Answer 1

Indeed, the syntax you have is not correct. Although most (all?) ARM assemblers support the MOD operator, it only works when both operands are assembly-time constants. It just does assembly-time arithmetic and constant expression folding. So, you could do:

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

which would essentially be transformed into:

mov  r0, #2

thus moving the value 2 into the R0 register.

This is nice, because it allows you to perform modulus on declared constants (which you use for readability), and also to write expressions so that they are human-readable and thus more maintainable.

It doesn't, however, work when you are dealing with registers, variables, or anything which is not an assembly-time constant.

---

Based on the code you have in the question, it looks like you are adding the contents of the R1 register to the R0register, and then trying to compute R0 modulo 2.

Assuming that the integers are unsigned, that is as simple as:

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

This works because x % 2 is equivalent to x & 1 for unsigned integers. In general, x % n is equivalent to x & (n - 1) as long as n (the divisor) is a power of two. This not only easier to write, but it is also a performance optimization, because bitwise operations are faster than division.

Now that you know the pattern for modulo by powers of two, you can easily do (r0 + r1) % 4:

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

---

If you want to do modulo by a constant that is not a power of two, then things get more complicated. I would not try to write this out by hand in assembly. Instead, I'd look to see what a compiler would generate. Here's the way you'd perform (r0 + r1) % 3 in assembly:

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

The compiler has generated optimized code to compute the integer modulus. Instead of doing a full division, it has transformed this into multiplication by a magic number (the multiplicative inverse). This is a standard trick from Hacker's Delight, and a common strength-reduction optimization used by many compilers.

---

So far, we've looked at modulo operations on unsigned integer types. What about when you want to do modular arithmetic on signed integers? Well, you need to take the sign bit (which is the MSB) into account.

For (r0 + r1) % 2, where r0 and r1 are signed, and thus r0 + r1 produces a signed result:

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

This is very similar to the code we had for unsigned modulus, except for the IT+RSBMI instructions to conditional negate, based on whether or not the input value is negative (in other words, to take the absolute value).

(You only specified ARMv7 in the question, not which profile you were targeting. If your chip has the "A" (application) profile, you can omit the IT instruction. But otherwise, you are targeting the Thumb-2 instruction set, which doesn't support conditional execution of non-branch instructions, so you need the IT before the RSBMI instruction. See Conditional Execution in Thumb-2.)

Unfortunately, calculating (r0 + r1) % 4 isn't a simple matter of changing the constant operand of the AND instruction. You need more code, even for modulo by constants powers of two. Again, ask a compiler how to do it. Definitely ask a compiler for signed modulo of non-powers of two.

---

If you want to do a general modulus operation on two variables, things are much more difficult, because you can't simply use bit-twiddling. C compilers are going to emit a call to a library function:

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}

Here, GCC dispatched to the __aeabi_uidivmod library function for unsigned and the __aeabi_idivmod library function for signed modulo/division. Other compilers will have their own library functions.

Don't try and write this sort of code by hand in assembly. It simply isn't worth the effort. If necessary, extract the function from a C compiler's standard library, and call it to do the heavy lifting. (Your teacher is not expecting you to do this.)