7.11 Loops
|
7.11 Loops
Loops represent the final basic control structure (sequences, decisions, and loops) that make up a typical program. Like so many other structures in assembly language, you'll find yourself using loops in places you've never dreamed of using loops. Most high level languages have implied loop structures hidden away. For example, consider the BASIC statement "IF A$ = B$ THEN 100". This if statement compares two strings and jumps to statement 100 if they are equal. In assembly language, you would need to write a loop to compare each character in A$ to the corresponding character in B$ and then jump to statement 100 if and only if all the characters matched. In BASIC, there is no loop to be seen in the program. In assembly language, such a simple if statement requires a loop to compare the individual characters in the string.[7] This is but a small example that shows how loops seem to pop up everywhere.
Program loops consist of three components: an optional initialization component, a loop termination test, and the body of the loop. The order with which these components are assembled can dramatically change the way the loop operates. Three permutations of these components appear over and over again. Because of their frequency, these loop structures are given special names in high level languages: while loops, repeat..until loops (do..while in C/C++), and infinite loops (e.g., forever..endfor in HLA).
7.11.1 WHILE Loops
The most general loop is the while loop. In HLA it takes the following form:
while( expression ) do <<statements>> endwhile;
There are two important points to note about the while loop. First, the test for termination appears at the beginning of the loop. Second as a direct consequence of the position of the termination test, the body of the loop may never execute. If the boolean expression is always false, the loop body will never execute.
Consider the following HLA while loop:
mov( 0, I ); while( I < 100 ) do inc( I ); endwhile;
The "mov( 0, I );" instruction is the initialization code for this loop. I is a loop control variable, because it controls the execution of the body of the loop. "I<100" is the loop termination condition. That is, the loop will not terminate as long as I is less than 100. The single instruction "inc( I );" is the loop body. This is the code that executes on each pass of the loop.
Note that an HLA while loop can be easily synthesized using if and jmp statements. For example, you may replace the HLA while loop above by:
mov( 0, I ); WhileLp: if( I < 100 ) then inc( i ); jmp WhileLp; endif;
More generally, any while loop can be built up from the following:
<< optional initialization code>> UniqueLabel: if( not_termination_condition ) then <<loop body>> jmp UniqueLabel; endif;
Therefore, you can use the techniques from earlier in this chapter to convert if statements to assembly language along with a single jmp instruction to produce a while loop. The example we've been looking at in this section translates to the following "pure" 80x86 assembly code:[8]
mov( 0, i ); WhileLp: cmp( i, 100 ); jnl WhileDone; inc( i ); jmp WhileLp; WhileDone:
7.11.2 REPEAT..UNTIL Loops
The repeat..until (do..while) loop tests for the termination condition at the end of the loop rather than at the beginning. In HLA, the repeat..until loop takes the following form:
<< optional initialization code >> repeat <<loop body>> until( termination_condition );
This sequence executes the initialization code and the loop body and then tests some condition to see if the loop should repeat. If the boolean expression evaluates to false, the loop repeats; otherwise the loop terminates. The two things to note about the repeat..until loop are that the termination test appears at the end of the loop and, as a direct consequence of this, the loop body always executes at least once.
Like the while loop, the repeat..until loop can be synthesized with an if statement and a jmp . You could use the following:
<< initialization code >> SomeUniqueLabel: << loop body >> if( not_the_termination_condition ) then jmp SomeUniqueLabel; endif;
Based on the material presented in the previous sections, you can easily synthesize repeat..until loops in assembly language. The following is a simple example:
repeat stdout.put( "Enter a number greater than 100: "); stdin.get( i ); until( i > 100 ); // This translates to the following IF/JMP code: RepeatLbl: stdout.put( "Enter a number greater than 100: "); stdin.get( i ); if( i <= 100 ) then jmp RepeatLbl; endif; // It also translates into the following "pure" assembly code: RepeatLabel:3 stdout.put( "Enter a number greater than 100: "); stdin.get( i ); cmp( i, 100 ); jng RepeatLbl;
7.11.3 FOREVER..ENDFOR Loops
If while loops test for termination at the beginning of the loop and repeat..until loops check for termination at the end of the loop, the only place left to test for termination is in the middle of the loop. The HLA forever..endfor loop, combined with the break and breakif statements, provide this capability. The forever..endfor loop takes the following form:
forever << loop body >> endfor;
Note that there is no explicit termination condition. Unless otherwise provided for, the forever..endfor construct simply forms an infinite loop. Loop termination is typically handled by a breakif statement. Consider the following HLA code that employs a forever..endfor construct:
forever stdin.get( character ); breakif( character = '.' ); stdout.put( character ); endfor;
Converting a forever loop to pure assembly language is trivial. All you need is a label and a jmp instruction. The breakif statement in this example is really nothing more than an if and a jmp instruction. The "pure" assembly language version of the code above looks something like the following:
foreverLabel: stdin.get( character ); cmp( character, '.' ); je ForIsDone; stdout.put( character ); jmp foreverLabel; ForIsDone:
7.11.4 FOR Loops
The for loop is a special form of the while loop that repeats the loop body a specific number of times. In HLA, the for loop takes the following form:
for( <<Initialization Stmt>>; <<Termination Expression>>; <<inc_Stmt>> ) do << statements >> endfor;
This is completely equivalent to the following:
<< Initialization Stmt>>; while( <<Termination Expression>> ) do << statements >> <<inc_Stmt>> endwhile;
Traditionally, the for loop has been used to process arrays and other objects accessed in sequential numeric order. One normally initializes a loop control variable with the initialization statement and then uses the loop control variable as an index into the array (or other data type), e.g.,
for( mov(0, esi); esi < 7; inc( esi )) do stdout.put( "Array Element = ", SomeArray[ esi*4], nl ); endfor;
To convert this to "pure" assembly language, begin by translating the for loop into an equivalent while loop:
mov( 0, esi ); while( esi < 7 ) do stdout.put( "Array Element = ", SomeArray[ esi*4], nl ); inc( esi ); endwhile;
Now, using the techniques from the section on while loops, translate the code into pure assembly language:
mov( 0, esi ); WhileLp: cmp( esi, 7 ); jnl EndWhileLp; stdout.put( "Array Element = ", SomeArray[ esi*4], nl ); inc( esi ); jmp WhileLp; EndWhileLp:
7.11.5 The BREAK and CONTINUE Statements
The HLA break and continue statements both translate into a single jmp instruction. The break instruction exits the loop that immediately contains the break statement; the continue statement restarts the loop that immediately contains the continue statement.
Converting a break statement to "pure" assembly language is very easy. Just emit a jmp instruction that transfers control to the first statement following the endxxxx clause of the loop to exit. You can do this by placing a label after the associated endxxxx clause and jumping to that label. The following code fragments demonstrate this technique for the various loops:
// Breaking out of a forever loop: forever <<stmts>> //break; jmp BreakFromForever; <<stmts>> endfor; BreakFromForever: // Breaking out of a FOR loop; for( <<initStmt>>; <<expr>>; <<incStmt>> ) do <<stmts>> //break; jmp BrkFromFor; <<stmts>> endfor; BrkFromFor: // Breaking out of a WHILE loop: while( <<expr>> ) do <<stmts>> //break; jmp BrkFromWhile; <<stmts>> endwhile; BrkFromWhile: // Breaking out of a REPEAT..UNTIL loop: repeat <<stmts>> //break; jmp BrkFromRpt; <<stmts>> until( <<expr>> ); BrkFromRpt:
The continue statement is slightly more difficult to implement that the break statement. The implementation still consists of a single jmp instruction, however the target label doesn't wind up going in the same spot for each of the different loops. Figures 7-2, 7-3, 7-4, and 7-5, respectively, show where the continue statement transfers control for each of the HLA loops.
Figure 7-2: CONTINUE Destination for the FOREVER Loop.
Figure 7-3: CONTINUE Destination and the WHILE Loop.
Figure 7-4: CONTINUE Destination and the FOR Loop.
Figure 7-5: CONTINUE Destination and the REPEAT..UNTIL Loop.
The following code fragments demonstrate how to convert the continue statement into an appropriate jmp instruction for each of these loop types.
forever..continue..endfor
// Conversion of forever loop w/continue // to pure assembly: forever <<stmts>> continue; <<stmts>> endfor; // Converted code: foreverLbl: <<stmts>> // continue; jmp foreverLbl; <<stmts>> jmp foreverLbl;
while..continue..endwhile
// Conversion of while loop w/continue // into pure assembly: while( <<expr>> ) do <<stmts>> continue; <<stmts>> endwhile; // Converted code: whlLabel: <<Code to evaluate expr>> Jcc EndOfWhile; // Skip loop on expr failure. <<stmts> //continue; jmp whlLabel; // Jump to start of loop on continue. <<stmts>> jmp whlLabel; // Repeat the code. EndOfwhile:
for..continue..endfor
// Conversion for a for loop w/continue // into pure assembly: for( <<initStmt>>; <<expr>>; <<incStmt>> ) do <<stmts>> continue; <<stmts>> endfor; // Converted code <<initStmt>> ForLpLbl: <<Code to evaluate expr>> Jcc EndOfFor; // Branch if expression fails. <<stmts>> //continue jmp ContFor; // Branch to <<incStmt>> on continue. <<stmts>> ContFor: <<incStmt>> jmp ForLpLbl; EndOfFor:
repeat..continue..until
repeat <<stmts>> continue; <<stmts>> until( <<expr>> ); // Converted Code: RptLpLbl: <<stmts>> // continue; jmp ContRpt; // Continue branches to loop termination test. <<stmts>> ContRpt: <<code to test expr>> Jcc RptLpLbl; // Jumps if expression evaluates false.
7.11.6 Register Usage and Loops
Given that the 80x86 accesses registers much faster than memory locations, registers are the ideal spot to place loop control variables (especially for small loops). However, there are some problems associated with using registers within a loop. The primary problem with using registers as loop control variables is that registers are a limited resource. The following will not work properly because it attempts to reuse a register (CX) that is already in use:
mov( 8, cx ); loop1: mov( 4, cx ); loop2: <<stmts>> dec( cx ); jnz loop2; dec( cx ); jnz loop1;
The intent here, of course, was to create a set of nested loops — that is, one loop inside another. The inner loop (loop2) should repeat four times for each of the eight executions of the outer loop (loop1). Unfortunately, both loops use the same register as a loop control variable. Therefore, this will form an infinite loop because CX will be set to zero at the end of the first loop. Because CX is always zero upon encountering the second dec instruction, control will always transfer to the loop1 label (because decrementing zero produces a non-zero result). The solution here is to save and restore the CX register or to use a different register in place of CX for the outer loop:
mov( 8, cx ); loop1: push( cx ); mov( 4, cx ); loop2: <<stmts>> dec( cx ); jnz loop2; pop( cx ); dec( cx ); jnz loop1;
or:
mov( 8, dx ); loop1: mov( 4, cx ); loop2: <<stmts>> dec( cx ); jnz loop2; dec( dx ); jnz loop1;
Register corruption is one of the primary sources of bugs in loops in assembly language programs; always keep an eye out for this problem.
[7]Of course, the HLA Standard Library provides the str.eq routine that compares the strings for you, effectively hiding the loop even in an assembly language program.
[8]Note that HLA will actually convert most while statements to different 80x86 code than this section presents. The reason for the difference appears a little later in this text when we explore how to write more efficient loop code.
|
EAN: 2147483647
Pages: 246