### Thread: Euclid's Algorihm for Assembler

1. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
May 2010
Posts
3
Rep Power
0

#### Euclid's Algorihm for Assembler

I'm trying to write a program to find the HCF of two-digit numbers in assembler, and I keep having trouble with my output. Any help would be greatly appreciated!

Here is what I have:

.model small
.stack 400h
.data
first_num_digit_ascii db ?
first_num_digit2_ascii db ?
second_num_digit_ascii db ?
second_num_digit2_ascii db ?
prompt1 db 0ah,0dh,'Please enter the first number: \$'
prompt2 db 0ah,0dh,'Please enter the second number: \$'
prompt3 db 0ah,0dh,'The highest common factor is: \$'
confirmation_string db 0ah,0dh,'You typed ---> \$'
Finished db 0ah,0dh, 'Thank you! Have a nice day. \$'

number1 dw 0d
number2 dw 0d

.code

mov ax, @data ;establish access to the data segment
mov ds, ax ;of memory

mov number1, 0d ;just to be sure

mov ax, @data
mov ds,ax
mov ah,9d
mov dx, offset prompt1
int 21h

;----------------------------------------------------------------------
;read first digit
mov ah, 1d ;bios code for read a keystroke -- no error checking!
int 21h ;call bios, it is understood that the ascii code will be returned in al

mov first_num_digit_ascii, al ;may as well save a copy

sub al, 30h ;Convert code to an actual integer

cbw ;CONVERT BYTE TO WORD. This takes whatever number is in al and
;extends it to ax, boubling its size from 8 bits to 16 bits
;The first digit now occupies all of ax as an integer

mov cx, 100d ;This is so we can calculate 100*1st digit +10*2nd digit + 3rd digit
mul cx ;start to accumulate the 2 digit number in the variable imul cx ;it is understood that the other operand is ax
;AND that the result will use both dx::ax
;but we understand that dx will contain only leading zeros
add number1, ax ;save

;variable <number1> now contains 1st digit * 10
;----------------------------------------------------------------------
;read second digit, multiply by 10 and add in
mov ah, 1d ;bios code for read a keystroke -- no error checking!
int 21h ;call bios, it is understood that the ascii code will be returned in al

mov first_num_digit2_ascii, al ;may as well save a copy

sub al, 30h ;Convert code to an actual integer

cbw ;CONVERT BYTE TO WORD. This takes whatever number is in al and
;extends it to ax, boubling its size from 8 bits to 16 bits
;The first digit now occupies all of ax as an integer

mov cx, 10d ;continue to accumulate the 3 digit number in the variable
mul cx ;it is understood that the other operand is ax, containing first digit
;AND that the result will use both dx::ax
;but we understand that dx will contain only leading zeros. Ignore them
add number1, ax ;save -- nearly finished
;variable <number1> now contains 1st digit * 100 + second digit * 10
;----------------------------------------------------------------------

;proof of conversion
mov ah, 9d ;bios code for print a dollar delimited string
mov dx, offset confirmation_string ;address of 1st character is ds::dx
int 21h ;Do the output, printing You typed --->

;now print the digits
mov ah, 2d ;bios code for print a character
mov dl, first_num_digit_ascii ;we had saved the ascii code here
;code must be in dl
int 21h ;call to bios

mov ah, 2d ;bios code for print a character
mov dl, first_num_digit2_ascii ;we had saved the ascii code here
;code must be in dl
int 21h ;call to bios

jnz Second_digit

;------------------------------------------------------------------------
Second_digit:

mov ax, @data ;establish access to the data segment
mov ds, ax ;of memory

mov number2, 0d ;just to be sure

mov ax, @data
mov ds,ax
mov ah,9d
mov dx, offset prompt2
int 21h

;----------------------------------------------------------------------
;read first digit for second number
mov ah, 1d ;bios code for read a keystroke -- no error checking!
int 21h ;call bios, it is understood that the ascii code will be returned in al

mov second_num_digit_ascii, al ;may as well save a copy

sub al, 30h ;Convert code to an actual integer

cbw ;CONVERT BYTE TO WORD. This takes whatever number is in al and
;extends it to ax, boubling its size from 8 bits to 16 bits
;The first digit now occupies all of ax as an integer

mov cx, 100d ;This is so we can calculate 100*1st digit +10*2nd digit + 3rd digit
mul cx ;start to accumulate the 3 digit number in the variable imul cx ;it is understood that the other operand is ax
;AND that the result will use both dx::ax
;but we understand that dx will contain only leading zeros
add number2, ax ;save

;variable <number2> now contains 1st digit * 10
;----------------------------------------------------------------------
;read second digit for second number, multiply by 10 and add in
mov ah, 1d ;bios code for read a keystroke -- no error checking!
int 21h ;call bios, it is understood that the ascii code will be returned in al

mov second_num_digit2_ascii, al ;may as well save a copy

sub al, 30h ;Convert code to an actual integer

cbw ;CONVERT BYTE TO WORD. This takes whatever number is in al and
;extends it to ax, boubling its size from 8 bits to 16 bits
;The first digit now occupies all of ax as an integer

mov cx, 10d ;continue to accumulate the 3 digit number in the variable
mul cx ;it is understood that the other operand is ax, containing first digit
;AND that the result will use both dx::ax
;but we understand that dx will contain only leading zeros. Ignore them
add number2, ax ;save -- nearly finished
;variable <number2> now contains 1st digit * 100 + second digit * 10
;----------------------------------------------------------------------

;proof of conversion
mov ah, 9d ;bios code for print a dollar delimited string
mov dx, offset confirmation_string ;address of 1st character is ds::dx
int 21h ;Do the output, printing You typed --->

;now print the digits
mov ah, 2d ;bios code for print a character
mov dl, second_num_digit_ascii ;we had saved the ascii code here
;code must be in dl
int 21h ;call to bios

mov ah, 2d ;bios code for print a character
mov dl, second_num_digit2_ascii ;we had saved the ascii code here
;code must be in dl
int 21h ;call to bios

;we have our two numbers saved in the variables number1 and number2ax
;save number1 into ax and number2 into bx
;now we move on to our loop to find the greatest common factor

mov ax,number1
mov bx,number2

jnz Loop1

Loop1:
cmp ax,bx ;compares the two values
jz Loop3 ;Their equal so it jumps to Loop3 and ends
cmp ax,bx ;the two numbers are not the same so we move on
jg Loop2 ;if ax > bx then it jumps to Loop2
;If we're still in this loop then ax < bx
sub bx,ax ;Subtracts bx by ax
jmp Loop1 ;repeats around until equal

Loop2:
;To get here then that means ax > bx, then we must lower ax
sub ax, bx
jmp Loop1 ;goes back to Loop1 until they become equal

Loop3:
;The two values are equal and it comes here and prints
mov dx, offset prompt3
mov ah, 9d ;BIOS code for print a string
int 21h

mov al, cl
mov ah, 2d
mov dl, cl
add dl, 30h ;convert back to ascii
int 21h

;mov ah, 2d ;BIOS code for print
;mov dl, bx ;prints bx
;add dl, 30h ;converts to ASCII
;int 21h

mov dx, offset Finished
mov ah, 9d
int 21h

jnz skip_message ;jump to exit program

skip_message:

;exit gracefully
mov ah, 4ch
int 21h

end
2. Could you tell us which assembler this is written for? Different assemblers all use slightly different syntax, even for the same CPU; this looks like Turbo Assembler, but I'm not sure.

If you could also tell us just how it is failing, it would help us understand the problem. What output do you get, if any?

Also, if you could edit your first post to put [CODE] tags around the code, it would make it much easier to read, as the forum software doesn't maintain whitespace otherwise.
3. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
May 2010
Posts
3
Rep Power
0
Yea, sorry lol, this is my first time posting on here.

The program was written for tasm, I made a few changes to the code, i'll post that below. The problem I'm having is printing the result of the loop which is stored in ax, after the loop ends.The output i'm getting is the characters "T" "O" rather than a number.

Here is the edited code:

Code:
```.model small
.stack 400h
.data
first_num_digit_ascii db ?
first_num_digit2_ascii db ?
second_num_digit_ascii db ?
second_num_digit2_ascii db ?
prompt1 db 0ah,0dh,'Please enter the first number: \$'
prompt2 db 0ah,0dh,'Please enter the second number: \$'
prompt3 db 0ah,0dh,'The highest common factor is: \$'
confirmation_string db 0ah,0dh,'You typed ---> \$'

number1 dw 0d
number2 dw 0d
gcf     dw 0d

.code

mov ax, @data	;establish access to the data segment
mov ds, ax	;of memory

mov number1, 0d	;just to be sure

mov ax, @data
mov ds,ax
mov ah,9d
mov dx, offset prompt1  ;print prompt for first number
int 21h

;----------------------------------------------------------------------
;read first digit
mov ah, 1d	;bios code for read a keystroke -- no error checking!
int 21h		;call bios, it is understood that the ascii code will be returned in al

mov first_num_digit_ascii, al	;may as well save a copy

sub al, 30h	;Convert code to an actual integer

cbw		;CONVERT BYTE TO WORD. This takes whatever number is in al and
;extends it to ax, boubling its size from 8 bits to 16 bits
;The first digit now occupies all of ax as an integer

mov cx, 100d	;This is so we can calculate 100*1st digit +10*2nd digit
mul cx		;start to accumulate the 2 digit number in the variable	imul cx ;it is understood that the other operand is ax
;AND that the result will use both dx::ax
;but we understand that dx will contain only leading zeros
add number1, ax	;save

;variable <number1> now contains 1st digit * 10
;----------------------------------------------------------------------
;read second digit, multiply by 10 and add in
mov ah, 1d	;bios code for read a keystroke -- no error checking!
int 21h		;call bios, it is understood that the ascii code will be returned in al

mov first_num_digit2_ascii, al	;may as well save a copy

sub al, 30h	;Convert code to an actual integer

cbw		;CONVERT BYTE TO WORD. This takes whatever number is in al and
;extends it to ax, boubling its size from 8 bits to 16 bits
;The first digit now occupies all of ax as an integer

mov cx, 10d	;continue to accumulate the 2 digit number in the variable
mul cx		;it is understood that the other operand is ax, containing first digit
;AND that the result will use both dx::ax
;but we understand that dx will contain only leading zeros. Ignore them
add number1, ax	;save -- nearly finished
;variable <number1> now contains 1st digit * 100 + second digit * 10
;----------------------------------------------------------------------

;proof of conversion
mov ah, 9d	;bios code for print a dollar delimited string
mov dx, offset confirmation_string	;address of 1st character is ds::dx
int 21h		;Do the output, printing You typed --->

;now print the digits
mov ah, 2d	;bios code for print a character
mov dl, first_num_digit_ascii	;we had saved the ascii code here
;code must be in dl
int 21h		;call to bios

mov ah, 2d	;bios code for print a character
mov dl, first_num_digit2_ascii	;we had saved the ascii code here
;code must be in dl
int 21h		;call to bios

jnz Second_digit

;------------------------------------------------------------------------
Second_digit:

mov ax, @data	;establish access to the data segment
mov ds, ax	;of memory

mov number2, 0d	;just to be sure

mov ax, @data
mov ds,ax
mov ah,9d
mov dx, offset prompt2 ;print prompt for the second number
int 21h

;----------------------------------------------------------------------
;read first digit for second number
mov ah, 1d	;bios code for read a keystroke -- no error checking!
int 21h		;call bios, it is understood that the ascii code will be returned in al

mov second_num_digit_ascii, al	;may as well save a copy

sub al, 30h	;Convert code to an actual integer

cbw		;CONVERT BYTE TO WORD. This takes whatever number is in al and
;extends it to ax, boubling its size from 8 bits to 16 bits
;The first digit now occupies all of ax as an integer

mov cx, 100d	;This is so we can calculate 100*1st digit +10*2nd digit
mul cx		;start to accumulate the 2 digit number in the variable	imul cx
;it is understood that the other operand is ax
;AND that the result will use both dx::ax
;but we understand that dx will contain only leading zeros
add number2, ax	;save

;variable <number2> now contains 1st digit * 10
;----------------------------------------------------------------------
;read second digit for second number, multiply by 10 and add in
mov ah, 1d	;bios code for read a keystroke -- no error checking!
int 21h		;call bios, it is understood that the ascii code will be returned in al

mov second_num_digit2_ascii, al	;may as well save a copy

sub al, 30h	;Convert code to an actual integer

cbw		;CONVERT BYTE TO WORD. This takes whatever number is in al and
;extends it to ax, boubling its size from 8 bits to 16 bits
;The first digit now occupies all of ax as an integer

mov cx, 10d	;continue to accumulate the 2 digit number in the variable
mul cx		;it is understood that the other operand is ax, containing first digit
;AND that the result will use both dx::ax
;but we understand that dx will contain only leading zeros. Ignore them
add number2, ax	;save -- nearly finished
;variable <number2> now contains 1st digit * 100 + second digit * 10
;----------------------------------------------------------------------

;proof of conversion
mov ah, 9d	;bios code for print a dollar delimited string
mov dx, offset confirmation_string	;address of 1st character is ds::dx
int 21h		;Do the output, printing You typed --->

;now print the digits
mov ah, 2d	;bios code for print a character
mov dl, second_num_digit_ascii	;we had saved the ascii code here
;code must be in dl
int 21h		;call to bios

mov ah, 2d	;bios code for print a character
mov dl, second_num_digit2_ascii	;we had saved the ascii code here
;code must be in dl
int 21h		;call to bios

;we have our two numbers saved in the variables number1 and number2
;save number1 into ax and number2 into bx
;now we move on to our loop to find the greatest common factor

mov ax,number1
mov bx,number2

jnz Loop1

Loop1:
cmp	ax,bx   ;compares the two values
jz	Print	;Their equal so it jumps to Print and ends
cmp	ax,bx   ;the two numbers are not the same so we move on
jg	Loop2	;if ax > bx then it jumps to Loop2
;If we're still in this loop then ax < bx
sub	bx,ax   ;Subtracts bx by ax
jmp	Loop1	;repeats around until equal

Loop2:
;To get here then that means ax > bx, then we must lower ax
sub	ax,bx
jmp	Loop1	;goes back to Loop1 until they become equal

Print:
;The two values are equal and it comes here and prints
mov	dx, offset prompt3
mov	ah, 9d	;BIOS code for print a string
int	21h

mov gcf,ax ;save answer from ax to variable gcf

mov dx,0d   ;clear dx register before dividing
mov cx,10d  ;add 10 to cx and divide
div cx

mov bx,0d   ;clear bx register
mov bx,dx   ;remainder is left in dx, move remainder to bx
add bl,30h  ;convert to ascii
mov dx,gcf  ;put gcf value into dx register
add dl,30h  ;convert to ascii

mov ah,2d   ;print first digit
int 21h

mov dx,bx   ;bx holds the second digit of the answer
mov ah,2d   ;move it into dx and print
int 21h

jnz skip_message		;jump to exit program

skip_message:

;exit gracefully
mov ah, 4ch
int 21h

end```
4. Is TASM required for the class your taking or the book you're using? Just wondering, because it's rather old now (last version, 5.0, was released in 1996) and AFAIK it was never released to the public domain (nor was it sold separately). Also, do you know which version you're using?

EDIT: I managed to scratch up a copy of Turbo Assembler 5.0, and assembled the program as given. It assembled without errors, but TLINK couldn't find the start of the program with which to link it to an executable - the error message I got was
Code:
`Fatal: No program entry point`
- which implies that this listing wasn't a complete program. Was there more code than you've shown?

Continued: Apparently, you need a label named 'start' at the beginning of the code segment to make the program work correctly with TASM v.5.0 . I was able to run it, with this result:
Code:
```Please enter the first number: 12
You typed ---> 12
Please enter the second number:  3
You typed --->  3
The highest common factor is: :
Thank you! Have a nice day.```
Now, I have to admit that this isn't the best assembly code I've seen, and I am much more familiar with Netwide Assembler, so I'm having some trouble following it. I'll get back to you about what I find as soon as I am able.
Last edited by Schol-R-LEA; May 14th, 2010 at 07:05 PM.
5. No Profile Picture
Registered User
Devshed Newbie (0 - 499 posts)

Join Date
May 2010
Posts
3
Rep Power
0
Thank you for your help =) I know my assembly code isn't the best, but I finally figured the problem out! Tasm was required for this assignment, so I had no other choice, and I must have been running an older version of tasm.
6. As it happens, you may be doing better than I did with it; I had tried to re-write the program (using the more familiar NASM) according to what I consider 'good' assembly language practices, and I ended up making a botch of it. For what it's worth, here's my version:
Assembly Code:
```
[bits 16]
;;;;;;;;;;;;;;;;;;;;;;
;; EQUates for common constants, mostly the DOS and BIOS calls
DOSCALL   equ 21h
READCHAR  equ 01h
WRITECHAR equ 02h
WRITESTR  equ 09h
EXIT      equ 4Ch

ASCII_ZERO equ 30h   ;  ASCII '0' - used when converting number values
CR        equ 0Ah    ; carriage return
LF        equ 0Dh    ; line feed

[segment .data]
prompt1	db CR,LF,'Please enter the first number: \$'
prompt2 	db CR,LF,'Please enter the second number: \$'
prompt3 	db CR,LF,'The highest common factor is: \$'
confirmation_string db CR,LF,'You typed ---> \$'
gcdstring   db CR,LF, 'greatest common divisor of the two numbers is \$'
Finished 	db CR,LF, 'Thank you! Have a nice day. \$'

number1 	resw 0d
number2 	resw 0d
gcdnumber   resw 0d

[segment .stack stack]
resw 200h
stacktop:

[segment .text]

..start:
mov ax, data	;set the data segment
mov ds, ax
mov ax, stack	;set the stack segment
mov ss, ax

mov dx, prompt1
mov ah, WRITESTR
int DOSCALL

call read_int
mov [number1], ax         ; save value for later use
mov bx, ax
mov dx, confirmation_string
mov ah, WRITESTR
int DOSCALL
push bx
call print_int

mov dx, prompt2
mov ah, WRITESTR
int DOSCALL

call read_int
mov [number2], ax         ; save value for later use
mov bx, ax
mov dx, confirmation_string
mov ah, WRITESTR
int DOSCALL
push bx
call print_int

mov ax, number1
mov bx, number2
push bx
push ax
call gcd
mov [gcdnumber], ax
mov dx, gcdstring
mov ah, WRITESTR
int DOSCALL
mov ax, [gcdnumber]
push ax
call print_int

mov dx, Finished
mov ah, WRITESTR
int DOSCALL

;exit gracefully
mov ah, EXIT
int DOSCALL

print_int:
push bp       ; save the old base pointer
mov bp, sp    ; save the sp in bp
push dx
push ax
mov cl, 10d

mov ax, [bp + 4]    ; get argument from the stack frame
div cl              ; divide arg by 10
add ah, ASCII_ZERO
mov dl, ah          ; save value to be printed
cbw                 ; zero-extend AL
cmp ax, 0
jz  .print_int_end
push ax
call print_int
pop ax
.print_int_end:
mov ah, WRITECHAR
int DOSCALL
pop ax
pop dx
pop bp
ret

; read_int - reads digits from stdin and converts them to an integer
read_int:
mov ax, '\$'     ; set a delimiter
push ax
.read_digit:
mov ah, READCHAR	;bios code for read a keystroke -- no error checking!
int DOSCALL		    ;call bios, it is understood that the ascii code will be returned in al
sub al, ASCII_ZERO  ; strip the value down to a single-digit integer
cmp al, 0
jl  atoi
cmp al, 9d
jg  atoi
cbw
push ax         ; store the one-digit number on the stack,
; in order from largest place to units place
jmp short .read_digit

; atoi - convert a string of digits on the stack to an integer value
atoi:
mov cx, 1d      ; initialize the place value
mov bx, 0
.convert:
pop ax
cmp ax, '\$'
jz  short .atoi_end   ; if reached the end of the digits, finish up
mul cx
add bx, ax      ;; accumulate number in bx
mov ax, 10d     ; now multiply cx by 10 for the next decimal place value
mul cx
mov cx, ax
jmp short .convert    ; go to the next digit

.atoi_end:
mov ax, bx      ; put the final return value in ax
ret

gcd:   ; calculate the gcd using iterative version of Euclid's method
; arguments are in on stack, return value in ax
push bp       ; save the old base pointer
mov bp, sp    ; save the sp in bp

mov ax, [bp + 4]   ; ax == A
mov bx, [bp + 6]   ; bx == B
cmp	ax, 0    ; if a == 0, return b
jz	.gcd_end1
jmp .whiletest
.while_b_not_0:
cmp ax, bx
jle .b_minus_a
sub ax, bx
jmp .whiletest
.b_minus_a:
sub bx, ax

.whiletest:
cmp bx, 0
jnz .while_b_not_0
jmp .gcd_end2

.gcd_end1:
mov ax, bx
.gcd_end2:
pop cx   ; clean up two stack arguments
pop cx
pop bp
ret```

As you can see, it isn't really adequately commented, though I did at least replace a lot of magic numbers with named constants. The real problem is that I couldn't get the GCD subroutine to work right; it sometimes causes the program to loop back to the start, while at other times causes a protection fault. Given that this was meant to help you, I doubt it's worth my while to quite finish seeing how you got your version working yesterday...
7. #### I think I'm getting a bit obsessed

For some reason this particular problem won't seem to let me go. Here is my latest version of the whole program:
Code:
```[bits 16]
;;;;;;;;;;;;;;;;;;;;;;
;; EQUates for common constants, mostly the DOS and BIOS calls
DOSCALL   equ 21h
READCHAR  equ 01h
WRITECHAR equ 02h
WRITESTR  equ 09h
EXIT      equ 4Ch

ASCII_ZERO equ 30h   ;  ASCII '0' - used when converting number values
CR        equ 0Ah    ; carriage return
LF        equ 0Dh    ; line feed

[segment .data]
prompt1         db CR,LF,'Please enter the first number: \$'
prompt2         db CR,LF,'Please enter the second number: \$'
prompt3         db CR,LF,'The highest common factor is: \$'
confirmation_string db CR,LF,'You typed ---> \$'
gcdstring       db CR,LF, 'greatest common divisor of the two numbers is \$'
Finished        db CR,LF, 'Thank you! Have a nice day. \$'

number1         resw 0d
number2         resw 0d
gcdnumber       resw 0d

[segment .stack stack]
resw 200h
stacktop:

[segment .text]

..start:
mov ax, data    ;set the data segment
mov ds, ax
mov ax, stack   ;set the stack segment
mov ss, ax
mov sp, stacktop

mov dx, prompt1           ; ask for the first number
mov ah, WRITESTR
int DOSCALL

call read_int             ; read in the A value
mov [number1], ax         ; save value for later use
mov dx, confirmation_string
mov ah, WRITESTR          ; print it back to show
int DOSCALL               ; that it was read in correctly
mov ax, [number1]
push ax
call print_int
pop bx                    ; discard argument to print_int

mov dx, prompt2           ; ask for the second number
mov ah, WRITESTR
int DOSCALL

call read_int             ; read in the B value
mov [number2], ax         ; save value for later use
mov dx, confirmation_string
mov ah, WRITESTR          ; print it back to show that it was read in correctly
int DOSCALL
mov ax, [number2]
push ax
call print_int
pop bx                    ; discard argument to print_int

mov ax, [number1]
mov bx, [number2]
push bx                   ; argument B
push ax                   ; argument A
call gcd
pop bx                    ; clear away arguments to gcd
pop bx
mov [gcdnumber], ax       ; save value returned by GCD function
mov dx, gcdstring         ; print out statement about the GCD value
mov ah, WRITESTR
int DOSCALL
mov ax, [gcdnumber]       ; restore the GCD and print it out
push ax
call print_int
pop ax

mov dx, Finished
mov ah, WRITESTR
int DOSCALL

;exit gracefully
mov ah, EXIT
int DOSCALL

print_int:
push bp       ; save the old base pointer
mov bp, sp    ; save the sp in bp
push dx
push ax
mov cl, 10d

mov ax, [bp + 4]    ; get argument from the stack frame
div cl              ; divide arg by 10
add ah, ASCII_ZERO
mov dl, ah          ; save value to be printed
cbw                 ; zero-extend AL
cmp ax, 0
jz  .print_int_end
push ax
call print_int
pop ax
.print_int_end:
mov ah, WRITECHAR
int DOSCALL
pop ax
pop dx
pop bp
ret

; read_int - reads digits from stdin and converts them to an integer
read_int:
mov ax, '\$'     ; set a delimiter
push ax
.read_digit:
mov ah, READCHAR    ;bios code for read a keystroke -- no error checking!
int DOSCALL         ;call bios, it is understood that the ascii code will be returned in al
sub al, ASCII_ZERO  ; strip the value down to a single-digit integer
cmp al, 0
jl  atoi
cmp al, 9d
jg  atoi
cbw
push ax         ; store the one-digit number on the stack,
; in order from largest place to units place
jmp short .read_digit

; atoi - convert a string of digits on the stack to an integer value
atoi:
mov cx, 1d      ; initialize the place value
mov bx, 0
.convert:
pop ax
cmp ax, '\$'
jz  short .atoi_end   ; if reached the end of the digits, finish up
mul cx
add bx, ax      ;; accumulate number in bx
mov ax, 10d     ; now multiply cx by 10 for the next decimal place value
mul cx
mov cx, ax
jmp short .convert    ; go to the next digit

.atoi_end:
mov ax, bx      ; put the final return value in ax
ret

gcd:   ; calculate the gcd using tail-recursive version of Euclid's method
; arguments are on stack, return value in ax
; not an especially efficent version, but it should be correct
push bp       ; save the old base pointer
mov bp, sp    ; save the sp in bp
push bx       ; save current values of bx and dx
push dx
mov dx, 0

mov ax, [bp + 4]   ; ax == A
mov bx, [bp + 6]   ; bx == B
.fake_recurse:
cmp     bx, 0          ; if b == 0, return a
je  short .gcd_end
div  bx            ; DX == a % b, AX == a // b
mov  ax, bx        ; b -> a`
mov  bx, dx        ; a % b -> b`
jmp .fake_recurse

.gcd_end:
pop dx             ; restore dx, bx, bp
pop bx
pop bp
ret```
While I corrected the underlying issue with the GCD function causing a crash (it was a silly error in stack handling), I still can't seem to get it to work. It is frustrating me to no end, which is really odd since it isn't even my assignment. Go figure... anyway, I'd appreciate any advice anyone can give, as I continue working on it.
Last edited by Schol-R-LEA; May 18th, 2010 at 10:15 PM.
8. No Profile Picture
Contributing User
Devshed Novice (500 - 999 posts)

Join Date
May 2007
Posts
765
Rep Power
929
Bugged me enough to spend an evening.

The "mov dx, 0" instruction in gcd has to move inside of the fake_recurse loop. Otherwise the remainder from the last iteration is taken as the high bits of the divisor.
Last edited by OmegaZero; May 26th, 2010 at 07:55 PM.
9. Originally Posted by OmegaZero
Bugged me enough to spend an evening.

The "mov dx, 0" instruction in gcd has to move inside of the fake_recurse loop. Otherwise the remainder from the last iteration is taken as the high bits of the divisor.
At the risk of thread necromancy, I should mention that on revisiting the code, I realized that I was declaring the RESW as size 0; this meant that I was overwriting number1 with number2. Fixing this solved that issue, but caused the program to have a divide overflow whenever BX was larger than AX. Testing the operands and exchanging them when that occurred only resulted in the program hanging. Thus, this simple program is still frustrating me.
EDIT: I finally got it working; I somehow had undone the change OZ recommended. Here is the final working version:
assembly Code:
```

[bits 16]
;;;;;;;;;;;;;;;;;;;;;;
;; EQUates for common constants, mostly the DOS and BIOS calls
DOSCALL   equ 21h
READCHAR  equ 01h
WRITECHAR equ 02h
WRITESTR  equ 09h
EXIT      equ 4Ch

ASCII_ZERO equ 30h   ;  ASCII '0' - used when converting number values
CR        equ 0Ah    ; carriage return
LF        equ 0Dh    ; line feed

[segment .data]
prompt1         db CR,LF,'Please enter the first number: \$'
prompt2         db CR,LF,'Please enter the second number: \$'
prompt3         db CR,LF,'The highest common factor is: \$'
confirmation_string db CR,LF,'You typed ---> \$'
gcdstring       db CR,LF, 'greatest common divisor of the two numbers is \$'
Finished        db CR,LF, 'Thank you! Have a nice day. \$'

number1         resw 1d
number2         resw 1d
gcdnumber       resw 1d

[segment .stack stack]
resw 200h
stacktop:

[segment .text]

..start:
mov ax, data    ;set the data segment
mov ds, ax
mov ax, stack   ;set the stack segment
mov ss, ax
mov sp, stacktop

mov dx, prompt1           ; ask for the first number
mov ah, WRITESTR
int DOSCALL

call read_int             ; read in the A value
mov [number1], ax         ; save value for later use
mov dx, confirmation_string
mov ah, WRITESTR          ; print it back to show
int DOSCALL               ; that it was read in correctly
mov ax, [number1]
push ax
call print_int
pop bx                    ; discard argument to print_int

mov dx, prompt2           ; ask for the second number
mov ah, WRITESTR
int DOSCALL

call read_int             ; read in the B value
mov [number2], ax         ; save value for later use
mov dx, confirmation_string
mov ah, WRITESTR          ; print it back to show that it was read in correctly
int DOSCALL
mov ax, [number2]
push ax
call print_int
pop bx                    ; discard argument to print_int

mov ax, [number1]
mov bx, [number2]
push bx                   ; argument B
push ax                   ; argument A
call gcd
pop bx                    ; clear away arguments to gcd
pop bx
mov [gcdnumber], ax       ; save value returned by GCD function
mov dx, gcdstring         ; print out statement about the GCD value
mov ah, WRITESTR
int DOSCALL
mov ax, [gcdnumber]       ; restore the GCD and print it out
push ax
call print_int
pop ax

mov dx, Finished
mov ah, WRITESTR
int DOSCALL

;exit gracefully
mov ah, EXIT
int DOSCALL

print_int:
push bp       ; save the old base pointer
mov bp, sp    ; save the sp in bp
push dx
push ax
push cx
mov cl, 10d

mov ax, [bp + 4]    ; get argument from the stack frame
div cl              ; divide arg by 10
add ah, ASCII_ZERO
mov dl, ah          ; save value to be printed
cbw                 ; zero-extend AL
cmp ax, 0
jz  short .print_int_end
push ax
call print_int
pop ax
.print_int_end:
mov ah, WRITECHAR
int DOSCALL
pop cx
pop ax
pop dx
pop bp
ret

; read_int - reads digits from stdin and converts them to an integer
read_int:
mov ax, '\$'     ; set a delimiter
push ax
.read_digit:
mov ah, READCHAR
int DOSCALL
sub al, ASCII_ZERO  ; strip the value down to a single-digit integer
cmp al, 0
jl  short atoi
cmp al, 9d
jg  short atoi
cbw
push ax         ; store the one-digit number on the stack,
; in order from largest place to units place
jmp short .read_digit

; atoi - convert a string of digits on the stack to an integer value
atoi:
mov cx, 1d      ; initialize the place value
mov bx, 0
.convert:
pop ax
cmp ax, '\$'
jz  short .atoi_end   ; if reached the end of the digits, finish up
mul cx
add bx, ax      ;; accumulate number in bx
mov ax, 10d     ; now multiply cx by 10 for the next decimal place value
mul cx
mov cx, ax
jmp short .convert    ; go to the next digit

.atoi_end:
mov ax, bx      ; put the final return value in ax
ret

gcd:    ; calculate the gcd using tail-recursive version of Euclid's method
; arguments are on stack, return value in ax
; not an especially efficent version, but it should be correct
push bp       ; save the old base pointer
mov  bp, sp   ; save the sp in bp
push bx       ; save current values of bx and dx
push dx

mov ax, [bp + 4]   ; ax == A
mov bx, [bp + 6]   ; bx == B

.fake_recurse:
mov dx, 0
cmp  bx, 0          ; if b == 0, return a
je  short .gcd_end
div  bx            ; DX == a % b, AX == a // b
mov  ax, bx        ; b -> a`
mov  bx, dx        ; a % b -> b`
jmp short .fake_recurse

.gcd_end:
pop dx             ; restore dx, bx, bp
pop bx
pop bp
ret```
Last edited by Schol-R-LEA; September 4th, 2010 at 01:28 PM.
10. No Profile Picture
Contributing User
Devshed Intermediate (1500 - 1999 posts)

Join Date
Feb 2004
Location
San Francisco Bay
Posts
1,941
Rep Power
1314
Neat! A few years ago, I wrote a bunch of GCD functions in x86 assembly just for kicks (6 total). My first one used Euclid's algorithm:

[code=gcd01.s] .text
.global gcd
/* int gcd(int a, int b); */
/* Euclid's algorithm. */
gcd:
movl 8(%esp), %eax
cltd
xorl %edx, %eax
subl %edx, %eax

movl %eax, %ecx

movl 4(%esp), %eax
cltd
xorl %edx, %eax
subl %edx, %eax

jmp .zero_test

.gcd_loop:
xorl %edx, %edx
idivl %ecx
movl %ecx, %eax
movl %edx, %ecx

.zero_test:
testl %ecx, %ecx
jnz .gcd_loop

ret[/code]My others all used another algorithm that only involves division by powers of 2, which makes it a bit faster in binary arithmetic. Here's the fastest one: [code=gcd05.s] .text
.global gcd
/* int gcd(int a, int b); */
/* shift/add algorithm */
/* (variant) */
gcd:
movl 8(%esp), %eax
cltd
xorl %edx, %eax
subl %edx, %eax
jz .b_zero

movl %eax, %ecx

movl 4(%esp), %eax
cltd
xorl %edx, %eax
subl %edx, %eax
jz .a_zero

pushl %esi
pushl %edi

movl %ecx, %esi
movl %eax, %edi

bsfl %esi, %ecx
sarl %cl, %esi
movb %cl, %bl

bsfl %edi, %ecx
sarl %cl, %edi

subb %bl, %cl
movsx %cl, %cx
andb %ch, %cl
addb %cl, %bl

xorb %cl, %cl

.main_loop:
sarl %cl, %edi

/* Make sure %edi > %esi */
movl %edi, %eax
subl %esi, %eax
cltd
andl %edx, %eax
subl %eax, %edi
addl %eax, %esi

subl %esi, %edi
bsfl %edi, %ecx
jnz .main_loop

movl %esi, %eax
movb %bl, %cl
sall %cl, %eax

popl %edi
popl %esi
ret
.a_zero:
movl %ecx, %eax
ret
.b_zero:
movl 4(%esp), %eax
ret[/code]The code is a bit longer because it has to reduce to the case where both numbers are odd before executing the main loop. The main loop itself is pretty slim. As you can see, I did not implement any I/O in assembly; the driver modules are written in C. Here they are: [code=gcd-test.c]#include <stdio.h>
#include <stdlib.h>

extern int gcd(int a, int b);

int main(int argc, char **argv) {
if (argc < 3) {
fprintf(stderr, "Usage: %s n1 n2\n", argv[0]);

exit(EXIT_FAILURE);
}
printf("%d\n", gcd(atoi(argv[1]), atoi(argv[2])));

exit(EXIT_SUCCESS);
}[/code][code=gcd-timer.c]#include <stdio.h>
#include <time.h>
#include <stdlib.h>

extern int gcd(int a, int b);

int main(int argc, char **argv) {
clock_t start, end;
int seed;
int iterations;
int k;
if (argc < 2) {
fprintf(stderr, "Usage: %s num_iterations\n", argv[0]);
exit(EXIT_FAILURE);
}
seed = time(NULL);
iterations = atoi(argv[1]);

start = clock();

srand(seed);

for (k = 0; k < iterations; ++k) {
int a = rand();
int b = rand();
int c = gcd(a, b);
}

end = clock();

printf("%.02f seconds elapsed\n", 1.0*(end-start)/CLOCKS_PER_SEC);

exit(EXIT_SUCCESS);
}[/code]