Developing Programs in Assembler

Sample Problem: Calculation of the Greatest Common Divisor

The basic GCD algorithm is:

Enter larger_number
Enter smaller_number
While the larger_number is not equal to the smaller_number
   If larger_number < smaller_number
     Exchange values of larger_number and smaller_number
   EndIf
   Subtract smaller_number from larger_number (replacing larger_number)
Loop back to while
Output larger_number
Stop

Decomposition of the Algorithm

Our code will perform these generic activities:

  1. Enter a number
  2. Perform a loop while two data values are not equal
  3. Perform a conditional activity if one data value is less than another
  4. Exchange two data values
  5. Subtract one value from another
  6. Output a number
  7. Stop program execution

In addition to these activities explicit in the algorithm, we will need to be able to:


Enter a number

A major difficulty here is caused by the fact that the user will be entering a value in decimal (base 10) which will need to be converted into unsigned binary for internal processing. A rough algorithm to manage this process could be:

Because this is a fairly common processing requirement, it may be convenient to code it as a subroutine (called a PROC, in MASM assembler) which could easily be copied into other programs with similar needs. Limitations on the size of numeric value that is acceptable should also be considered at this point; assuming a single word is being used, the maximum value that could be encoded (in a 16-bit word) is 65535; we can not guarantee the validity of any user input which allowed 5 or more digits. Non-decimal digit characters should also cause some kind of error recognition.

; GetNum - input a maximum of 4 decimal digits and return the
; unsigned binary form of this number in AX;
;   Return with the Carry flag "on" if the input is invalid
;
; note that this particular version of the GetNum "proc" is flagged as "near"
;      indicating that it will be contained in the same segment as the
;      statement that calls it.
getnum  proc    near
        mov     num,0
        mov     bh,'9'  ;setup for valid range testing
        mov     bl,'0'
        mov     cl,4    ;maximum number of digits acceptable

get_loop:
        mov     ah,01   ;get key (with echo)
        int     21h
        cmp     al,0Dh  ;exit loop on carriage return
        je      get_exit

        cmp     bh,al   ;check that it's < '9'
        jc      bad_digit ;error if its not
        sub     al,bl
        jc      bad_digit ;error if its < '0'

        mov     ah,0
        push    ax      ;save digit value for later addition
        mov     ax,num
        mov     dx,10   ;decimal based system
        imul    dx      ;multiply ax by dx results in dx|ax
        mov     num,ax  ;value of prior digits times 10
        pop     ax      ;add this digit's value
        add     num,ax

        sub     cl,1
        jnc     get_loop
bad_digit:  ;-- if we get here something is wrong
            ;-- by careful coding we have ensured that
            ;-- the carry flag will be set
            ;-- this is the "error" return indicator
get_exit:
        mov     ax,num
        ret

;--- local data ---
num     dw      ?

getnum  endp

Perform a loop while two data values are not equal

A WHILE loop has two key parts: the test at the top of the while loop and the return to the top of the loop:

while:  mov     ax,large    ; while ( large != small )
        cmp     ax,small
        je      endwhile    ; exit loop when large == small
        ;
        ; instructions to be repeated by WHILE go here
        ;
        jmp     while       ; loop back to WHILE test
endwhile: 

Perform a conditional activity if one data value is less than another

This is a standard logic flow structure:

if:     mov     ax,large    ; if ( large < small )
        cmp     ax,small
        jae     endif       ; exit IF when large >= small
        ;
        ; instructions to be executed by IF (true) go here
        ;
endif: 

Exchange two data values

Use a temporary work data location or a register to help switch values. There are actually may ways to achieve this; one method will be given here and a different method will be included in the final combined program sample.

        push    large
        push    small
        pop     large
        pop     small

Subtract one value from another

Note that for arithmetic at least one of the values must be in a register.

        mov     ax,small    ; must put one value in register
        sub     large,ax    ; subtract small from large (replacing large)

Output a number

Together with the "Enter a number" requirement, this is one of the more difficult processes since it involves a conversion between unsigned binary and decimal digits. Again, we will consider a rough algorithm:

Repeat:

... until the number has been reduced to zero.

Repeat for each of the saved digits:

... until all digits have been output.

As with the "Get a number" routine, this is a common enough requirement that creation as a separate subroutine would likely be a good design decision. Converted to mnemonic code, this would become something like:

; ShowNum - Display the unsigned binary value in AL as a 
; decimal value
showNum proc    near
        mov     bx,10   ;divide by 10 to convert to decimal
        mov     cl,0    ;count of number of digits produced
div_loop:
        mov     dx,0    ;setup to divide dx|ax by bx
        idiv    bx      ;unsigned division: 
                        ;quotient in ax, remainder in dx
        push    dx      ;save the digit (remainder) on the LIFO stack
        inc     cl      ;keep track of number of digits
        cmp     ax,0    ;until nothing left to divide
        jnz     div_loop;  loop back

        mov     dx,offset newline ;ensure display is on a newline
        mov     ah,09
        int     21h
show_digit:
        pop     dx      ;retrieve digit value from LIFO stack
        add     dl,30h  ;convert digit to ASCII code
        mov     ah,02   ;display character
        int     21h
        dec     cl      ;loop until all digits shown
        jnz     show_digit

        ret

;-- local data --
newline   db    0Dh,0Ah,"$"
showNum endp


Stop program execution

Assuming AL has been pre-loaded with the desired return code:

        mov     ah,4Ch    ; 4C means "terminate with code"
        int     21h

Embedding in Complete Program Source File

Download the complete source: gcd.asm