Linux Assembly - Greatest common divisor
========================================

Public domain

********************************************************************************
### gcd-reg.asm 

    ; Greatest common divisor
    ; nasm -f elf gcd-reg.asm -o gcd-asm.o -g
    section .text
    global gcd 
    gcd:
            push    ebp               ; function prologue
            mov     ebp, esp
            mov     eax, [ebp+8]      ; first parameter
            mov     ecx, [ebp+12]     ; second parameter
    _@begin:
            cmp     eax, 0            ; if remainder is 0, gcd is in ecx
            jz      _@done
            cmp     eax, ecx          ; eax should be greater
            jge     _@sorted
            xchg    eax, ecx
    _@sorted:
            ; converting doubleword to quadword before signed division
            cdq                       ; extends eax into edx 
            idiv    ecx               ; eax = edx:eax / ecx (signed)
            mov     eax, edx          ; edx = edx:eax % ecx (signed) 
            jmp     _@begin
    _@done:
            mov     eax, ecx          ; return value
            mov     esp,ebp           ; function epilogue
            pop     ebp
            ret

********************************************************************************
### gcd-mem.asm

    ; Greatest common divisor
    ; nasm -f elf gcd-mem.asm -o gcd-asm.o -g
    section .bss
    $x:     resd    1
    $y:     resd    1
    section .text
    global gcd 
    gcd:
            push    ebp                    ; function prologue
            mov     ebp, esp
            mov     eax, [ebp+8]           ; first parameter
            mov     [$x], eax
            mov     eax, [ebp+12]          ; second parameter
            mov     [$y], eax
    _@begin:
            cmp     dword [$x], 0          ; if remainder is 0, gcd is in $y
            jz      _@done
            mov     eax, [$x]
            cmp     eax, [$y]              ; $x (eax) should be greater
            jge     _@sorted
            mov     ecx, [$y]              ; swap $x & $y
            mov     [$y], eax
            mov     [$x], ecx
    _@sorted:
            mov     eax, [$x]
            mov     ecx, [$y]
            ; converting doubleword to quadword before signed division
            cdq                            ; extends eax into edx
            idiv    ecx                    ; eax = edx:eax / ecx (signed)
            mov     [$x], edx              ; edx = edx:eax % ecx (signed)
            jmp     _@begin
    _@done:
            mov     eax, [$y]              ; return value
            mov     esp,ebp                ; function epilogue
            pop     ebp
            ret

********************************************************************************
### gcd.c

    /* Greatest common divisor */
    /* gcc gcd.c gcd-asm.o -o gcd -g */

    #include <stdio.h>

    int gcd(int a, int b);

    int main()
    {
            int a, b, result;

            a = 84;
            b = 18;
            result = gcd(a, b);
            printf("Greatest common divisor of %d and %d is %d\n", a, b, result);

            a = 56;
            b = 42;
            result = gcd(a, b);
            printf("Greatest common divisor of %d and %d is %d\n", a, b, result);

            return(0);
    }

********************************************************************************
_BY: Pejman Moghadam_  
_TAG: asm, idiv, cdq_  
_DATE: 2013-01-12 23:56:48_