[Chapter Twelve][Previous] [Art of Assembly][Randall Hyde]

Art of Assembly Language: Chapter Twelve


12.6 - Sample Programs
12.6.1 - An Example of an Iterator
12.6.2 - Another Iterator Example

12.6 Sample Programs


The sample programs in this chapter provide two examples of iterators. The first example is a simple iterator that processes characters in a string and returns the vowels found in that string. The second iterator is a synthetic program (i.e., written just to demonstrate iterators) that is considerably more complex since it deals with static links. The second sample program also demonstrates another way to build the resume frame for an iterator. Take a good look at the macros that this program uses. They can simplify the user of iterators in your programs.


12.6.1 An Example of an Iterator


The following example demonstrates a simple iterator. This piece of code reads a string from the user and then locates all the vowels (a, e, i, o, u, w, y) on the line and prints their index into the string, the vowel at that position, and counts the occurrences of each vowel. This isn't a particularly good example of an iterator, however it does serve to demonstrate an implementation and use.

First, a pseudo-Pascal version of the program:




program DoVowels(input,output);
const
        Vowels = ['a', 'e', 'i', 'o', 'u', 'y', 'w',
                    'A', 'E', 'I', 'O', 'U', 'Y', 'W'];

var
        ThisVowel : integer;
        VowelCnt : array [char] of integer;

        iterator GetVowel(s:string) : integer;
        var
                CurIndex : integer;
        begin

                for CurIndex := 1 to length(s) do
                        if (s [CurIndex] in Vowels) then begin

                           { If we have a vowel, bump the cnt by 1 }
                           Vowels[s[CurIndex]] := Vowels[s[CurIndex]]+1;

                           ( Return index into string of current vowel }
                           yield CurIndex;

                        end;
        end;

begin {main}

        { First, initialize our vowel counters }

        VowelCnt ['a'] := 0;
        VowelCnt ['e'] := 0;
        VowelCnt ['i'] := 0;
        VowelCnt ['o'] := 0;
        VowelCnt ['u'] := 0;
        VowelCnt ['w'] := 0;
        VowelCnt ['y'] := 0;
        VowelCnt ['A'] := 0;
        VowelCnt ['E'] := 0;
        VowelCnt ['I'] := 0;
        VowelCnt ['O'] := 0;
        VowelCnt ['U'] := 0;
        VowelCnt ['W'] := 0;
        VowelCnt ['Y'] := 0;

        { Read and process the input string}

        Write('Enter a string: ');
        ReadLn(InputStr);
        foreach ThisVowel in GetVowel(InputStr) do
                WriteLn('Vowel ',InputStr [ThisVowel],
                                ' at position ', ThisVowel);

        { Output the vowel counts }

        WriteLn('# of A''s:',VowelCnt['a'] + VowelCnt['A']);
        WriteLn('# of E''s:',VowelCnt['e'] + VowelCnt['E']);
        WriteLn('# of I''s:',VowelCnt['i'] + VowelCnt['I']);
        WriteLn('# of O''s:',VowelCnt['o'] + VowelCnt['O']);
        WriteLn('# of U''s:',VowelCnt['u'] + VowelCnt['U']);
        WriteLn('# of W''s:',VowelCnt['w'] + VowelCnt['W']);
        WriteLn('# of Y''s:',VowelCnt['y'] + VowelCnt['Y']);

end.

Here's the working assembly language version:





                .286            ;For PUSH imm instr.
                .xlist
                include         stdlib.a
                includelib      stdlib.lib
                .list

; Some "cute" equates:

Iterator        textequ <proc>
endi            textequ <endp>
wp              textequ <word ptr>


; Yield is a macro which emits the necessary code for the YIELD operation.

Yield           macro
                mov     dx, [bp+2]              ;Place to yield back to.
                push    bp                      ;Save Iterator link
                mov     bp, [bp]                ;Get ptr to caller's A.R.
                call    dx                      ;Push resume address and rtn.
                pop     bp                      ;Restore ptr to our A. R.
                endm

; Necessary global variables:

dseg            segment para public 'data'

; As per UCR StdLib instructions, InputStr must hold
; at least 128 characters.

InputStr        byte    128 dup (?)

; Note that the following statement initializes the
; VowelCnt array to zeros, saving us from having to
; do this in the main program.

VowelCnt        word    256 dup (0)

dseg            ends



cseg            segment para public 'code'
                assume  cs:cseg, ds:dseg

; GetVowel-     This iterator searches for the next vowel in the
;               input string and returns the index to the value
;               as the iterator result. On entry, ES:DI points
;               at the string to process.  On yield, AX returns
;               the zero-based index into the string of the
;               current vowel.
;
; GVYield-      Address to call when performing the yield.
; GVStrPtr-     A local variable which points at our string.

GVYield         textequ <word ptr [bp+2]>
GVStrPtr        textequ <dword ptr [bp-4]>

GetVowel        Iterator
                push    bp
                mov     bp, sp

; Create and initialize GVStrPtr.  This is a pointer to the
; next character to process in the input string.

                push    es
                push    di

; Save original ES:DI values so we can restore them on YIELD
; and on termination.

                push    es
                push    di

; Okay, here's the main body of the iterator.  Fetch each
; character until the end of the string and see if it is
; a vowel.  If it is a vowel, yield the index to it.  If
; it is not a vowel, move on to the next character.

GVLoop:         les     di, GVStrPtr    ;Ptr to next char.
                mov     al, es:[di]     ;Get this character.
                cmp     al, 0           ;End of string?
                je      GVDone

; The following statement will convert all lower case
; characters to upper case.  It will also translate other
; characters to who knows what, but we don't care since
; we only look at A, E, I, O, U, W, and Y.

                and     al, 5fh

; See if this character is a vowel.  This is a disgusting
; set membership operation.  See Chapter Ten to learn how
; to do it right.

                cmp     al, 'A'
                je      IsAVowel
                cmp     al, 'E'
                je      IsAVowel
                cmp     al, 'I'
                je      IsAVowel
                cmp     al, 'O'
                je      IsAVowel
                cmp     al, 'U'
                je      IsAVowel
                cmp     al, 'W'
                je      IsAVowel
                cmp     al, 'Y'
                jne     NotAVowel

; If we've got a vowel we need to yield the index into
; the string to that vowel.  To compute the index, we
; restore the original ES:DI values (which pointer at
; the beginning of the string) and subtract the current
; position (now in AX) from the first position.  This
; produces a zero-based index into the string.
; This code must also increment the corresponding entry
; in the VowelCnt array so we can print the results
; later.  Unlike the Pascal code, we've converted lower
; case to upper case so the count for upper and lower
; case characters will appear in the upper case slot.

IsAVowel:       push    bx              ;Bump the vowel
                mov     ah, 0           ; count by one.
                mov     bx, ax
                shl     bx, 1
                inc     VowelCnt[bx]
                pop     bx

                mov     ax, di
                pop     di              ;Restore original DI
                sub     ax, di          ;Compute index.
                pop     es              ;Restore original ES

                yield

                push    es              ;Save ES:DI again
                push    di

; Whether it was a vowel or not, we've now got to move
; on to the next character in the string.  Increment
; our string pointer by one and repeat the process
; over again.

NotAVowel:      inc     wp GVStrPtr
                jmp     GVLoop

; If we've reached the end of the string, terminate
; the iterator here.  We need to restore the original
; ES:DI values, remove local variables, pop the YIELD
; address, and then return to the termination address.

GVDone:         pop     di              ;Restore ES:DI
                pop     es
                mov     sp, bp          ;Remove locals
                add     sp, 4           ;Pop YIELD/S.L.
                pop     bp
                ret
GetVowel        endi



Main            proc
                mov     ax, dseg
                mov     ds, ax
                mov     es, ax

                print
                byte    "Enter a string: ",0
                lesi    InputStr
                gets                    ;Read input line.

; The following is the foreach loop.  Note that the label
; "FOREACH" is present for documentation purpose only.
; In fact, the foreach loop always begins with the first
; instruction after the call to GetVowel.
;
; One other note: this assembly language code uses
; zero-based indexes for the string.  The Pascal version
; uses one-based indexes for strings.  So the actual
; numbers printed will be different.  If you want the
; values printed by both programs to be identical,
; uncomment the INC instruction below.

                push    offset ForDone  ;Termination address.
                push    bp              ;Static link.
                call    GetVowel        ;Start iterator
FOREACH:        mov     bx, ax
                print
                byte    "Vowel ",0
                mov     al, InputStr[bx]
                putc
                print
                byte    " at position ",0
                mov     ax, bx
;               inc     ax
                puti
                putcr
                ret                     ;Iterator resume.

ForDone:        printf
                byte    "# of A's: %d\n"
                byte    "# of E's: %d\n"
                byte    "# of I's: %d\n"
                byte    "# of O's: %d\n"
                byte    "# of U's: %d\n"
                byte    "# of W's: %d\n"
                byte    "# of Y's: %d\n",0
                dword   VowelCnt + ('A'*2)
                dword   VowelCnt + ('E'*2)
                dword   VowelCnt + ('I'*2)
                dword   VowelCnt + ('O'*2)
                dword   VowelCnt + ('U'*2)
                dword   VowelCnt + ('W'*2)
                dword   VowelCnt + ('Y'*2)


Quit:           ExitPgm                 ;DOS macro to quit program.
Main            endp

cseg            ends

sseg            segment para stack 'stack'
stk             db      1024 dup ("stack   ")
sseg            ends

zzzzzzseg       segment para public 'zzzzzz'
LastBytes       db      16 dup (?)
zzzzzzseg       ends
                end     Main


12.6.2 Another Iterator Example


One problem with the iterator examples appearing in this chapter up to this point is that they do not access any global or intermediate variables. Furthermore, these examples do not work if an iterator is recursive or calls other procedures that yield the value to the foreach loop. The major problem with the examples up to this point has been that the foreach loop body has been responsible for reloading the bp register with a pointer to the foreach loop's procedure's activation record. Unfortunately, the foreach loop body has to assume that bp currently points at the iterator's activation record so it can get a pointer to its own activation record from that activation record. This will not be the case if the iterator's activation record is not the one on the top of the stack.

To rectify this problem, the code doing the yield operation must set up the bp register so that it points at the activation record of the procedure containing the foreach loop before returning back to the loop. This is a somewhat complex operation. The following macro accomplishes this from inside an iterator:




Yield           macro
                mov     dx, [BP+2]      ;Place to yield back to.
                push    bp              ;Save Iterator link
                mov     bp, [bp]        ;Get ptr to caller's A.R.
                call    dx              ;Push resume address and rtn.
                pop     bp              ;Restore ptr to our A. R.
                endm

Note an unfortunate side effect of this code is that it modifies the dx register. Therefore, the iterator does not preserve the dx register across a call to the iterator function.

The macro above assumes that the bp register points at the iterator's activation record. If it does not, then you must execution some additional instructions to follow the static links back to the iterator's activation record to obtain the address of the foreach loop procedure's activation record.





; Iterator example.
;
; Roughly corresponds to the example in Ghezzi & Jazayeri's
; "Programming Language Concepts" text.
;
; Randall Hyde
;
;
; This program demonstrates an implementation of:
;
;  l := 0;
;  foreach i in range(1,3) do
;       foreach j in iter2() do
;               writeln(i, ',', j, ',', l):
;
;
;  iterator range(start,stop):integer;
;  begin
;
;       while start <= stop do begin
;
;               yield start;
;               start := start+1;
;       end;
;  end;
;
;  iterator iter2:integer;
;  var k:integer;
;  begin
;
;       foreach k in iter3 do
;               yield k;
;  end;
;
;  iterator iter3:integer;
;  begin
;
;       l := l + 1;
;       yield 1;
;       l := l + 1;
;       yield 2;
;       l := l + 1;
;       yield 0;
;  end;
;
;
; This code will print:
;
;       1, 1, 1
;       1, 2, 2
;       1, 0, 3
;       2, 1, 4
;       2, 2, 5
;       2, 0, 6
;       3, 1, 7
;       3, 2, 8
;       3, 0, 9




                .xlist
                include         stdlib.a
                includelib      stdlib.lib
                .list

                .286                            ;Allow extra adrs modes.



dseg            segment para stack 'data'



; Put the stack in the data segment so we can use the small memory model
; to simplify addressing:

stk             byte    1024 dup ('stack')
EndStk          word    0

dseg            ends





cseg            segment para public 'code'
                assume  cs:cseg, ds:dseg, ss:dseg




; Here's the structure of a resume frame.  Note that this structure isn't
; actually used in this code.  It is only provided to show you what data
; is sitting on the stack when Yield builds a resume frame.

RsmFrm          struct
ResumeAdrs      word    ?
IteratorLink    word    ?
RsmFrm          ends




; The following macro builds a resume frame and the returns to the caller
; of an iterator.  It assumes that the iterator and whoever called the
; iterator have the standard activation record defined above and that we
; are building the standard resume frame described above.
;
; This code wipes out the DX register.  Whoever calls the iterator cannot
; count on DX being preserved, likewise, the iterator cannot count on DX
; being preserved across a yield.  Presumably, the iterator returns its
; value in AX.

ActRec          struct
DynamicLink     word    ?               ;Saved BP value.
YieldAdrs       word    ?               ;Return Adrs for proc.
StaticLink      word    ?               ;Static link for proc.
ActRec          ends

AR              equ     [bp].ActRec

Yield           macro
                mov     dx, AR.YieldAdrs        ;Place to yield back to.
                push    bp                      ;Save Iterator link
                mov     bp, AR.DynamicLink      ;Get ptr to caller's A.R.
                call    dx                      ;Push resume address and rtn.
                pop     bp                      ;Restore ptr to our A. R.
                endm






; Range(start, stop) - Yields start..stop and then fails.

; The following structure defines the activation record for Range:

rngAR           struct
DynamicLink     word    ?               ;Saved BP value.
YieldAdrs       word    ?               ;Return Adrs for proc.
StaticLink      word    ?               ;Static link for proc.
FailAdrs        word    ?               ;Go here when we fail
Stop            word    ?               ;Stop parameter
Start           word    ?               ;Start parameter

rngAR           ends


rAR             equ     [bp].rngAR


Range           proc
                push    bp
                mov     bp, sp

; While start <= stop, yield start:

WhlStartLEStop: mov     ax, rAR.Start           ;Also puts return value
                cmp     ax, rAR.Stop            ; in AX.
                jnle    RangeFail

                yield

                inc     rAR.Start
                jmp     WhlStartLEStop

RangeFail:      pop     bp                      ;Restore Dynamic Link.
                add     sp, 4                   ;Skip ret adrs and S.L.
                ret     4                       ;Return through fail address.
Range           endp




; Iter2- Just calls iter3() and returns whatever value it generates.
;
; Note: Since iter2 and iter3 are at the same lex level, the static link
; passed to iter3 must be the same as the static link passed to iter2.
; This is why the "push [bp]" instruction appears below (as opposed to the
; "push bp" instruction which appears in the calls to Range and iter2).
; Keep in mind, Range and iter2 are only called from main and bp contains
; the static link at that point.  This is not true when iter2 calls iter3.

iter2           proc
                push    bp
                mov     bp, sp

                push    offset i3Fail           ;Failure address.
                push    [bp]                    ;Static link is link to main.
                call    iter3
                yield                           ;Return value returned by iter3
                ret                             ;Resume Iter3.

i3Fail:         pop     bp                      ;Restore Dynamic Link.
                add     sp, 4                   ;Skip return address & S.L.
                ret                             ;Return through fail address.
iter2           endp



; Iter3() simply yields the values 1, 2, and 0:

iter3           proc
                push    bp
                mov     bp, sp

                mov     bx, AR.StaticLink       ;Point BX at main's AR.
                inc     word ptr [bx-6]         ;Increment L in main.
                mov     ax, 1
                yield

                mov     bx, AR.StaticLink
                inc     word ptr [bx-6]
                mov     ax, 2
                yield
                mov     bx, AR.StaticLink
                inc     word ptr [bx-6]
                mov     ax, 0
                yield

                pop     bp                      ;Restore Dynamic Link.
                add     sp, 4                   ;Skip return address & S.L.
                ret                             ;Return through fail address.
iter3           endp






; Main's local variables are allocated on the stack in order to justify
; the use of static links.

i               equ     [bp-2]
j               equ     [bp-4]
l               equ     [bp-6]


Main            proc
                mov     ax, dseg
                mov     ds, ax
                mov     es, ax
                mov     ss, ax
                mov     sp, offset EndStk

; Allocate storage for i, j, and l on the stack:

                mov     bp, sp
                sub     sp, 6

                meminit

                mov     word ptr l, 0           ;Initialize l.

; foreach i in range(1,3) do:

                push    1                       ;Parameters.
                push    3
                push    offset iFail            ;Failure address.
                push    bp                      ;Static link points at our AR.
                call    Range

; Yield from range comes here.  The label is for your benefit.

RangeYield:     mov     i, ax                   ;Save away loop control value.

; foreach j in iter2 do:

                push    offset jfail            ;Failure address.
                push    bp                      ;Static link points at our AR.
                call    iter2


; Yield from iter2 comes here:

iter2Yield:     mov     j, ax

                mov     ax, i
                puti
                print
                byte    ", ",0
                mov     ax, j
                puti
                print
                byte    ", ",0
                mov     ax, l
                puti
                putcr

; Restart iter2:

                ret                             ;Resume iterator.


; Restart Range down here:

jFail:          ret                             ;Resume iterator.

; All Done!

iFail:          print
                byte    cr,lf,"All Done!",cr,lf,0




Quit:           ExitPgm                 ;DOS macro to quit program.
Main            endp

cseg            ends



; zzzzzzseg must be the last segment that gets loaded into memory!
; This is where the heap begins.

zzzzzzseg       segment para public 'zzzzzz'
LastBytes       db      16 dup (?)
zzzzzzseg       ends
                end     Main
12.6 - Sample Programs
12.6.1 - An Example of an Iterator
12.6.2 - Another Iterator Example


Art of Assembly Language: Chapter Twelve - 27 SEP 1996

[Chapter Twelve][Previous] [Art of Assembly][Randall Hyde]



Number of Web Site Hits since Jan 1, 2000: