git.oblomov.eu Git - ohcount/blob - test/expected_dir/assembler1.asm

   1 assembler       comment ; int gcdAsm(int a, int b)
   2 assembler       comment ;
   3 assembler       comment ; computes gcd(a,b) according to:
   4 assembler       comment ; 1. a even, b   even: gcd(a,b) = 2 * gcd(a/2,b/2),
   5 assembler       comment ;    and remember how often this happened
   6 assembler       comment ; 2. a even, b uneven: gcd(a,b) = gcd(a/2,b)
   7 assembler       comment ; 3. a uneven, b   even: gcd(a,b) = gcd(a,b/2)
   8 assembler       comment ; 4. a uneven, b uneven: a>b ? a -= b : b -= a,
   9 assembler       comment ;    i.e. gcd(a,b) = gcd(min(a,b),max(a,b) - min(a,b))
  10 assembler       comment ; do 1., repeat 2. - 4. until a = 0 or b = 0
  11 assembler       comment ; return (a + b) corrected by the remembered value from 1.
  12 assembler       blank
  13 assembler       code                    BITS 32
  14 assembler       code                    GLOBAL _gcdAsm
  15 assembler       blank
  16 assembler       code                    SECTION .text
  17 assembler       code            _gcdAsm:
  18 assembler       code                    push ebp
  19 assembler       code                    mov ebp,esp
  20 assembler       code                    push ebx
  21 assembler       code                    push ecx
  22 assembler       code                    push edx
  23 assembler       code                    push edi
  24 assembler       code                    mov eax,[ebp + 8]   ; eax = a (0 <= a <= 2^31 - 1)
  25 assembler       code                    mov ebx,[ebp + 12]  ; ebx = b (0 <= b <= 2^31 - 1)
  26 assembler       comment                 ; by definition: gcd(a,0) = a, gcd(0,b) = b, gcd(0,0) = 1 !
  27 assembler       code                    mov ecx,eax
  28 assembler       code                    or ecx,ebx
  29 assembler       code                    bsf ecx,ecx         ; greatest common power of 2 of a and b
  30 assembler       code                    jnz notBoth0
  31 assembler       code                    mov eax,1           ; if a = 0 and b = 0, return 1
  32 assembler       code                    jmp done
  33 assembler       code            notBoth0:
  34 assembler       code                    mov edi,ecx
  35 assembler       code                    test eax,eax
  36 assembler       code                    jnz aNot0
  37 assembler       code                    mov eax,ebx         ; if a = 0, return b
  38 assembler       code                    jmp done
  39 assembler       code            aNot0:
  40 assembler       code                    test ebx,ebx
  41 assembler       code                    jz done             ; if b = 0, return a
  42 assembler       code                    bsf ecx,eax         ; "simplify" a as much as possible
  43 assembler       code                    shr eax,cl
  44 assembler       code                    bsf ecx,ebx         ; "simplify" b as much as possible
  45 assembler       code                    shr ebx,cl
  46 assembler       code            mainLoop:
  47 assembler       code                    mov ecx,ebx
  48 assembler       code                    sub ecx,eax         ; b - a
  49 assembler       code                    sbb edx,edx         ; edx = 0 if b >= a or -1 if a > b
  50 assembler       code                    and ecx,edx         ; ecx = 0 if b >= a or b - a if a > b
  51 assembler       code                    add eax,ecx         ; a-new = min(a,b)
  52 assembler       code                    sub ebx,ecx         ; b-new = max(a,b)
  53 assembler       code                    sub ebx,eax         ; the difference is >= 0
  54 assembler       code                    bsf ecx,eax         ; "simplify" as much as possible by 2
  55 assembler       code                    shr eax,cl
  56 assembler       code                    bsf ecx,ebx         ; "simplify" as much as possible by 2
  57 assembler       code                    shr ebx,cl
  58 assembler       code                    jnz mainLoop        ; keep looping until ebx = 0
  59 assembler       code                    mov ecx,edi         ; shift back with common power of 2
  60 assembler       code                    shl eax,cl
  61 assembler       code            done:
  62 assembler       code                    pop edi
  63 assembler       code                    pop edx
  64 assembler       code                    pop ecx
  65 assembler       code                    pop ebx
  66 assembler       code                    mov esp,ebp
  67 assembler       code                    pop ebp
  68 assembler       code                    ret                 ; eax = gcd(a,b)