Finding Greatest Common Divisor (GCD)

[unktehi]

ok, so I made some adjustments (per my instructor who I finally heard back from), I changed the JMP back to Loops, and changed the first loop as you suggested - still getting an error and it looks like edx is still acting weird:

INCLUDE Irvine32.inc

.data
str1 BYTE "Number was positive", 0
str2 BYTE "Number converted to positive", 0
str3 BYTE "The GCD is: ", 0

count DWORD ?
enterInt BYTE "Enter an integer: ", 0

.code
main PROC
   
   mov  edx, OFFSET enterInt   ; "Enter an integer:"
   call WriteString         ; displays string
   call ReadInt            ; read integer into EAX   
   
   cdq
   xor eax, edx
   sub eax, edx
   
   mov esi,eax               ; Assign X to esi
   
   mov edx, OFFSET enterInt      ; "Enter an integer:"
   call WriteString         ; displays string
   call ReadInt            ; read integer into EAX 
   
   cdq
   xor eax, edx
   sub eax, edx
   
   mov edi, eax         ; Assign Y to edi
   
   CALL Dumpregs
   
L1:   mov   eax, esi
   mov   ebx, edi
   sub   edx,edx
   div   ebx                  ;EAX/EBX quotient is in eax, remainder in edx   
   mov   esi, edi
   mov   edi, edx
   .if   edi > 0
   loop L1      
   .endif
   

L2:   mov  edx, OFFSET str3         ; "The GCD is: "
   call WriteString            ; displays string
   MOV eax, esi               ; Return X
   CALL WriteInt   
   
   
exit
main ENDP



END main

[unktehi]

Nevermind.  I got it to work.  Thanks for all of your help - I really needed it!!

[MichaelW]

I put this together before your last post, so instead of letting it go to waste:

The loop instruction decrements ECX and jumps to the specified label if ECX is not zero. Since you are not controlling the value in ECX, you need to close your loop differently. One alternative is to keep your condition test as is and use an unconditional jump to close the loop:

Code Select Expand


.if edi > 0
    jmp L1
.endif


And another is to use the TEST instruction (which is basically and AND instruction that sets the flags based on the result but does not store the result to the destination operand) and a conditional jump that jumps only if the TEST instruction did not set the zero flag:

Code Select Expand


test edi, edi
jnz L1


BTW, your code is not protecting against a divide by zero exception when EBX == 0.

[Mark Jones]

Now that you've got it working, take a look at a robust factorization routine:

Code Select Expand


; ****** Prime number factorization example by Mark Jones 2007 ******
include masm32rt.inc                    ; masm32 v9.2 assemble-time libs

T MACRO _jump:VARARG                    ; Branch Hint: Taken
    DB 2Eh
    _jump
ENDM

NT MACRO _jump:VARARG                   ; Branch Hint: Not Taken
    DB 3Eh
    _jump
ENDM

.data?
    nVal        dd  ?                   ; entered value
    nDivisor    dd  ?                   ; divisors buffer
    nDividend   dd  ?                   ; factoring buffer
    szTemp      db  16 dup(?)           ; ascii string buffer

.code
start:
    mov eax,input("Enter a number: ")
    cmp byte ptr [eax+1],10             ; break on pressing enter
NT  jz gb                               ; and exit
    cmp byte ptr [eax],"-"              ; do not allow negative numbers
NT  jz start                            ;
    invoke atodw,eax                    ; else convert ascii to dword
    mov nVal,eax                        ; save entered number as nVal
    cmp eax,0                           ; check input value
NT  jz start                            ; do not allow 0
NT  js start                            ; do not allow negatives
    mov nDivisor,0                      ; and reset divisor
    print "Divisors: ",0                ; we're showing divisors now
align 4                                 ; alignment speeds up loops
fl: xor edx,edx                         ; first loop - show all divisors
    inc nDivisor                        ; increase divisor by one
    mov eax,nVal                        ; load dividend into eax
    mov ecx,nDivisor                    ; load divisor into ecx
    div ecx                             ; divide eax by ecx, edx=remainder
    test edx,-1
T   jnz fl                              ; loop, else fall through
    invoke dwtoa,[nDivisor],addr szTemp ; convert dword to ascii
    print addr szTemp,","               ; print result and comma
    mov ecx,nDivisor                    ; restore ecx
    cmp nVal,ecx                        ; compare it with original value
T   jnz fl                              ; if they don't match, loop
    print chr$(8,20h,10)                ; all divisors reported, newline

    print "Factors:  ",0                ; we're factoring now
    xor esi,esi                         ; clear esi, using this as prime flag
    mov nDivisor,2                      ; start with 2
    m2m nDividend,nVal                  ; copy initial value
align 4
sl: xor edx,edx                         ; loop, clear edx
    mov eax,nDividend                   ; load dividend into eax
    mov ecx,nDivisor                    ; load factor under test into ecx
    cmp eax,ecx                         ; if we've reached equalization,
    jl dn                               ; then we're done factoring.
    div ecx                             ; divide eax by ecx, remainder in edx
    test edx,-1                         ; anything in there?
NT  jnz ck                              ; if remainder (bad), jump forward
    mov nDividend,eax                   ; no remainder, save dividend
    mov si,1                            ; set flag to "no longer prime"
    invoke dwtoa,[nDivisor],addr szTemp ; convert int to ascii
    print addr szTemp,"x"               ; print this factor
    jmp sl                              ; and loop
ck: inc nDivisor                        ; try next factor
    mov eax,nDivisor                    ; load factor into eax
    cmp eax,nVal                        ; compare this with original value
T   jl sl                               ; loop if factor less than nVal
    test si,si                          ; were there any factors?
T   jnz dn                              ; if so, jump to done
    print "PRIME! ",0                   ; else show there were no factors
dn: print chr$(8,20h,10,10)             ; done factoring, newlines
    jmp start                           ; and back to beginning
   
gb: invoke ExitProcess,0                ; exit gracefully

end start


Enter a number: 0
Enter a number: -2121
Enter a number: 123
Divisors: 1,3,41,123
Factors:  3x41

Enter a number: 12345
Divisors: 1,3,5,15,823,2469,4115,12345
Factors:  3x5x823

Enter a number: 12345678
Divisors: 1,2,3,6,9,18,47,94,141,282,423,846,14593,29186,43779,87558,
    131337,262674,685871,1371742,2057613,4115226,6172839,12345678
Factors:  2x3x3x47x14593

Enter a number: 34572479
Divisors: 1,34572479
Factors:  PRIME!

You should be able to see that dispite all the added complexity, the remainder of a DIV is still being checked to determine wether or not the chosen value was a factor. Notice that EDX is always being reset to zero before the DIV by means of the XOR EDX,EDX.

Of course, something this convoluted would be nearly impossible to write one-off purely by memory, and the calculation routine itself is not all that fast and could be further optimized. A debugger was necessary while writing the code to verify what each instruction was doing.

Your class will probably have a section on debugging, but if you want to "skip ahead" and see how a powerful assembly-level debugger can help your code now, take a stroll over to http://www.ollydbg.de/ and get OllyDbg v1.10. That will show you what each instruction does as it is executed. Simply load your executable into Olly and press F7 to "step" through each instruction. Move to a line of code and press F2 to place a breakpoint there, then press F9 to execute code up to that breakpoint. Also, when building the executable, if you add /Zi to the ML.EXE command-line parameters and /DEBUG to the LINK.EXE command-line, then Olly will be able to see variable names, procedure names, jump labels, and the source code while debugging. Such a tool is an absolute necessity when writing tricky code.

Happy experimenting. :bg