Author Topic: Problem with translation C to NASM greatest common divisor loop  (Read 18037 times)

Offline margor

  • Jr. Member
  • *
  • Posts: 2
Problem with translation C to NASM greatest common divisor loop
« on: November 25, 2010, 08:48:35 PM »
Hello,
This is my first post. I try to write program using Euclidean algorithm. I made the fallowing C prototype main.c (I am aware not to use goto, but it's only prototype for assembly jumps):
Code: [Select]
#include<stdio.h>
#include<stdlib.h>

int main()
{

  int a = 18;
  int b = 81;
  int c;

  beginwhile:
    if(b == 0)
       goto endwhile;
    
    c = a % b;
    a = b;
    b = c;
    
    if(b != 0)
      goto beginwhile;
  endwhile:

  printf("\n%d\n", a);

  return 0;
}

It works. This is my asembler program main.asm:
Code: [Select]
section .text ; begin of the code section
global main ; gcc needs that label

; load library
%include "library.asm"

main:
  ; printf("read a: ")
  mov eax, read_a
  call print_c_str
  ; scanf("%d", &a)
  call read_c_int ; scanf("%d", EAX)
  mov [a], eax

  ; printf("You typed: %d\n", a)
  mov eax, test_str
  call print_c_str
  mov eax, [a]
  call print_c_int
  call print_c_nl

  ; printf("read b: ")
  mov eax, read_b
  call print_c_str
  call read_c_int ; scanf("%d", EAX)
  mov [b], eax

  ; printf("You typed: %d\n", b)
  mov eax, test_str
  call print_c_str
  mov eax, [b]
  call print_c_int
  call print_c_nl

  ; Search the greatest common divisor of a and b.
  mov eax, [a] ; EAX = a
  mov ebx, [b] ; EBX = b
               ; EDX = c
 
  ; while (b != 0) {
  ;     c = a % b;
  ;     a = b;
  ;     b = c;
  ; }
  ; GCD: a
  while:
    cmp ebx, 0
    je endwhile
    push eax
    idiv ebx ; EDX = EAX % EBX
               ; EAX = EAX div EBX
    pop eax
    mov eax, ebx ; a  = b
    mov ebx, edx ; b = c

    cmp ebx, 0  ; if(b == 0)
    jne while ; jump not equal
  endwhile:

  ; print GCD
  push eax
  mov eax, print_gcd
  call print_c_str
  pop eax
  call print_c_int ; EAX
  call print_c_nl

  ; exit to C
  mov eax, 0
  ret

section .bss ; uninitialized data section
  a resw 2 ; long a - reserve 2 words (4 bytes)
  b resw 2 ; long b

section .data ; initialized data section
  read_a db "Read a: ", 0
  read_b db "Read b: ", 0
  print_gcd db "GCD is: ", 0
  test_str db "You typed: ", 0


To compile program it is necessary to use library.asm:
Code: [Select]
; external libc functions
extern printf
extern puts
extern scanf


; ************************ ;
; * library C procedures * ;
; ************************ ;

print_c_nl: ; puts("");
  pusha

  push 0

  push dword str_empty
  call puts ; call C
  pop ecx ; pop stack 1 times 4 bytes
  pop eax

  popa
retn ; return to previous block

; print_string: prints string which pointer is stored in EAX
print_c_str: ; printf("%s", EAX)
  pusha

  ; do: printf("%s", EAX)
  push eax ; address of string to printf
  push dword str_string ; address of: "%s", 0
  call printf ; call C function
  pop ecx
  pop ecx ; pop stack 2 times 4 bytes

  popa
ret ; return to previous block

; print_char: prints char stored in EAX
print_c_char: ; printf("%c", EAX)
  pusha

  ; do: printf("%c", EAX)
  push eax ; value of char to print
  push dword str_char ; address of: "%c", 0
  call printf ; call C function
  pop ecx
  pop ecx ; pop stack 2 times 4 bytes

  popa
ret ; return to previous block

; read_int: scanf("%d", EAX)
read_c_int:

  push 0 ; push local integer
  push esp
  push dword str_int
  call scanf ; call C
  pop ecx
  pop ecx ; pop 8 bytes
  pop eax

ret ; return to previous block

; print_c_int: printf("%d", EAX)
print_c_int:
  pusha

  ; do: printf("%d", EAX)
  push eax ; value of int to printf
  push dword str_int ; address of: "%d", 0
  call printf ; call C function
  pop ecx
  pop ecx ; pop 2 times 4 bytes

  popa
ret ; return to previous block

section .data ; initialized data section
  str_int db "%d", 0
  str_char db "%c", 0
  str_string db "%s", 0
  str_empty db 0
 
  nl db 0ah

It seems to me that loops are analogous. I get floting point error. Thanks for any help.
« Last Edit: November 25, 2010, 08:55:26 PM by margor »

Offline Frank Kotler

  • NASM Developer
  • Hero Member
  • *****
  • Posts: 2667
  • Country: us
Re: Problem with translation C to NASM greatest common divisor loop
« Reply #1 on: November 25, 2010, 11:08:11 PM »
As soon as I read "floating point error" I guessed the problem.

Code: [Select]
idiv ebx ; EDX = EAX % EBX
               ; EAX = EAX div EBX

The comment isn't quite right. Should be:

Code: [Select]
  ; EDX = EDX:EAX % EBX
  ; EAX = EDX:EAX div EBX

Idiv considers edx, too! If the result won't fit in eax - which is fairly likely if edx is "garbage" - it causes an exception, which is reported (in Linux) as "floating point error". Last I knew, DOS called it "division by zero". Either is confusing!

The "fix" is to do "cdq" just before the "idiv" - it sign-extends eax into edx. Thus edx will be the proper "high part" of your number.

Best,
Frank


Offline margor

  • Jr. Member
  • *
  • Posts: 2
Re: Problem with translation C to NASM greatest common divisor loop
« Reply #2 on: November 27, 2010, 11:21:22 AM »
It works! Thanks. It will help me very much in my future programs.