GCD in ARM Assembly

Post date: Apr 23, 2018 10:56:34 AM

The greatest common divisor (GCD) of two positive integers is the largest integer that divides both numbers without a remainder. It is also know as Greatest Common Factors (GCF), Greatest Common Measure (GCM), Highest Common Divisor (HCD), or Highest Common Factor (HCF).

The 'official' algorithm in full 32-bit ARM instruction set. Cortex-M4 is different.

gcd     cmp    r0, r1     ;if r0 > r1

        subgt  r0, r0, r1 ;subtract r1 from r0

        sublt  r1, r1, r0 ;else subtract r0 from r1

        bne    gcd        ;reached the end?

Only 4 lines! Let us see if a compiler can do that.

Enter the following code:

int gcd(int A, int B)

{

    while( A != B )

    {

        if( A > B )

            A -= B;

        else

            B -= A;

    }

    return B;

}

Then compile it to ARM7TDMI assembly using the -Os switch (optimize for size):

$ arm-none-eabi-gcc -mcpu=arm7tdmi --specs=nosys.specs -Os -S gcd.c

Finally, inspect the code, irrelevant junk filtered out.

    .cpu arm7tdmi

gcd:

.L2:

    cmp    r0, r1

    bne    .L5

    bx     lr

.L5:

    subgt  r0, r0, r1

    suble  r1, r1, r0

    b      .L2

We can see that even when optimized for size, some redundant instructions still exist. All the more reason to know assembly language programming.

Continued in GCD in Compiler Generated Cortex-M4 Assembly.