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

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