Calculating LCM in assembly x86

user_11918269 0
Viewed 676

I have the following assembly code

.global _start

.section .text
_start:
    movq a, %rax
    movq b, %rbx
    imul %rbx, %rax
    cmp %rbx, %rax
    je gcd_calculated
    ja l1
    sub %rax, %rbx
    jmp _start
l1:
    sub %rbx, %rax
    jmp _start
gcd_calculated:
    div %rax
    movq %rax, (c)

a,b are quads that I need to calculate their lcm and I need to assign the result to c

I get wrong results with the above code and I can't spot why.

generally, i'm relaying on the the lcm = (a*b)/gcd so I store a*b in %rax and then calculate the gcd which will be stored at %eax and finally divide between them.

att x86-64 x86 assembly
2 Answers
/* x86-64 gcc / clang support the __int128 type: */

/*

#include <stdint.h>

unsigned __int128 lcm (uint64_t a, uint64_t b)
{
    uint64_t u = a, v = b;

    for (uint64_t t = 0; (t = v) != 0; u = t)
        v = u % v;

    if (u != 0) /* gcd(a, b) != (0) : */
        return (((unsigned __int128) a) * (b / u));

    return (0);
}

*/

/* x86-64 Mach-O (OSX) / ELF calling conventions:
 * first arg (a) in %rdi, second arg (b) in %rsi;
 * 128-bit integer returned in %rdx:%rax [hi:lo] */

/* no caller-reserved registers or stack are used: */

        .text
        .globl _lcm
_lcm:
        movq    %rdi, %r8
        movq    %rsi, %rdi
        movq    %r8, %rcx
L_gcd:
        testq   %rdi, %rdi
        je      L_lcm         # %rcx = gcd(a, b)
        movq    %rcx, %rax
        xorl    %edx, %edx
        movq    %rdi, %rcx
        divq    %rdi
        movq    %rdx, %rdi
        jmp     L_gcd
L_lcm:                        # lcm(0, 0) returns (0) :
        xorl    %eax, %eax
        xorl    %edx, %edx
        testq   %rcx, %rcx    # if gcd(a, b) == 0, then:
        je      L_done        # %rdx:%rax = 0:0; return.
        movq    %rsi, %rax
        xorl    %edx, %edx    # %rdx:%rax = 0:b
        divq    %rcx          # %rax = (b / g)
        mulq    %r8           # %rdx:%rax = a * (b / g)
L_done:
        ret
user_9068390

Like 1201ProgramAlarm said, you are calculating and comparing the original values of a and b in each iteration of your loop. If you want to follow your current approach, you would have to store these values in memory each time before looping.

What I would actually do instead is just do the gcd calculation first and then calculate (a*b)/gcd at the end.

_start:
    movq a(%rip), %rbx
    movq b(%rip), %rcx
gcd:
    cmp %rbx, %rcx
    je gcd_calculated
    ja l1
    sub %rcx, %rbx
    jmp gcd
l1:
    sub %rbx, %rcx
    jmp gcd
gcd_calculated:
    movq a(%rip), %rax
    xor %rdx, %rdx
    div %rbx
    imul b(%rip), %rax
    movq %rax, c(%rip)
user_74488800
Related