The Art of
ASSEMBLY LANGUAGE PROGRAMMING

Chapter Twelve (Part 6)

Table of Content

Chapter Thirteen 

CHAPTER TWELVE:
PROCEDURES: ADVANCED TOPICS (Part 7)
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

Chapter Twelve (Part 6)

Table of Content

Chapter Thirteen  

Chapter Twelve: Procedures: Advanced Topics (Part 7)
27 SEP 1996