String Operations

Computers are frequently used to manipulate characters strings as well as numeric data. In data processing applications names, addresses, and so forth must be stored and sometimes rearranged. Text editor and word processor programs must be capable of searching for and moving strings of characters. An assembler must be able to separate assembly language statement elements, identifying those that are reserved mnemonics. Even when computation is primarily numerical, it is often necessary to convert either a character string to an internal numerical format when a number is entered at the keyboard or an internal format to a character string for display purposes.

An 80x86 microprocessor has instructions to manipulate character strings. The same instructions can manipulate strings of doublewords or words. This chapter covers 80x86 instructions that are used to handle strings, with emphasis on character strings. A variety of applications are given, including procedures that are similar to those in some high-level languages and the procedure called by the dtoa macro.

Using String Instructions

Five 80x86 instructions are designed for string manipulation: movs (move string), cmps (compare string), scas (scan string), stos (store string), and lods (load string). The movs instruction is used to copy a string from one memory location to another. The cmps instruction is designed to compare the contents of two strings. The scas instruction can be used to search a string for one particular value. The stos instruction can store a new value in some position of a string. Finally, the lods instruction copies a value out of some position of a string.

A string in the 80x86 architecture refers to a contiguous collection of bytes, words, or doublewords in memory. Strings are commonly defined in a program's data segment using such directives as

response BYTE 20 DUP (?) label1 BYTE 'The results are ', 0 wordString WORD 50 DUP (?) arrayD DWORD 60 DUP (0)

Note that strings and arrays are actually the same except for the way we look at them.

Each string instruction applies to a source string, a destination string, or both. The bytes, words, or doublewords of these strings are processed one at a time by the string instruction. Register indirect addressing is used to locate the individual byte, word, or doubleword elements. The 80x86 instructions access elements of the source string using the address in the source index register ESI. Elements in the destination string are accessed using the address in the destination index register EDI. If you program using a segmented memory model, then you also must know that the source element is in the data segment (at address DS:ESI) while the destination element is in the extra segment (at address ES:EDI). With flat memory model programming, both segment registers contain the same segment number and no distinction between segments.

Since the source and destination addresses of string elements are always given by ESI and EDI, respectively, no operands are needed to identify these locations. Without any operand, however, the assembler cannot tell the size of the string element to be used. For example, just movs by itself could say to move a byte, a word, or a doubleword. The Microsoft Macro Assembler offers two ways around this dilemma. The first method is to use destination and source operands; these are ignored except that MASM notes their type (both operands must be the same type) and uses that element size. The second method is to use special versions of the mnemonics that define the element size-instructions that operate on bytes use a b suffix, word string instructions use a w suffix, and doubleword string instructions use a d suffix. For example, movsb is used to move byte strings, movsw is used to move word strings, and movsd is used to move doubleword strings. Any of these instructions assemble as a movs and none uses an operand since the assembler knows the element size from the mnemonic. This book will use mnemonics with b, w, and d suffixes rather than operands for string instructions.

Although a string instruction operates on only one string element at a time, it always gets ready to operate on the next element. It does this by changing the source index register ESI and/or the destination index register EDI to contain the address of the next element of the string(s). When byte-size elements are being used, the index registers are changed by one; for words, ESI and EDI are changed by two; and for doublewords, the registers are changed by four. The 80x86 can move either forward through a string, from lower to higher addresses, or backward, from higher to lower addresses. The movement direction is determined by the value of the direction flag DF, bit 10 of the EFLAGS register. If DF is set to 1, then the addresses in ESI and EDI are decremented by string instructions, causing right to left string operations. If DF is clear (0), then the values in ESI and EDI are incremented by string instructions, so that strings are processed left to right.

The 80x86 has two instructions whose sole purpose is to reset or set the direction flag DF. The cld instruction clears DF to 0 so that ESI and EDI are incremented by string instructions and strings are processed left to right. The std instruction sets DF to 1 so that strings are processed backward. Neither instruction affects any flag other than DF. Technical data about these instructions appear in Fig. 7.1.

Figure 7.1: cld and std instructions

Finally it is time to present all the details about a string instruction. The move string instruction movs transfers one string element (byte, word, or doubleword) from a source string to a destination string. The source element at address DS:ESI is copied to address ES:EDI. After the string element is copied, both index registers are changed by the element size (1, 2, or 4), incremented if the direction flag DF is 0 or decremented if DF is 1. The movs instruction does not affect any flag. It comes in movsb, movsw, and movsd versions; Fig. 7.2 gives information about each form.

Figure 7.2: movs instructions (use ESI and EDI)

Figure 7.3 gives an example of a program that uses the movs instruction. The important part of the example is the procedure strcopy. This procedure has two parameters passed on the stack, which give the destination and source addresses of byte or character strings. The source string is assumed to be null-terminated. Procedure strcopy produces an exact copy of the source string at the destination location, terminating the destination string by a null byte.

; test of "strcopy" procedure ; author: R. Detmer revised: 10/97 .386 .MODEL FLAT ExitProcess PROTO NEAR32 stdcall, dwExitCode:DWORD INCLUDE io.h ; header file for input/output cr equ 0dh ; carriage return character Lf equ 0ah ; line feed .STACK 4096 ; reserve 4096-byte stack .DATA ; reserve storage for data prompt BYTE cr, Lf, "Original string? ",0 stringIn BYTE 80 DUP (?) display BYTE cr, Lf, "Your string was...", cr, Lf stringOut BYTE 80 DUP (?) .CODE _start: output prompt ; ask for string input stringIn, 80 ; get source string lea eax, stringOut ; destination address push eax ; first parameter lea eax, stringIn ; source push eax ; second parameter call strcopy ; call string copy procedure output display ; print result INVOKE ExitProcess, 0 ; exit with return code 0 PUBLIC _start ; make entry point public strcopy PROC NEAR32 ; Procedure to copy string until null byte in source is copied. ; It is assumed that destination location is long enough for copy. ; Parameters are passed on the stack: ; (1) address of destination ; (2) address of source push ebp ;save base pointer mov ebp,esp ;copy stack pointer push edi ;save registers and flags push esi pushf mov esi,[ebp+8] ;initial source address mov edi,[ebp+12] ;destination cld ;clear direction flag whileNoNull: cmp BYTE PTR [esi],0 ;null source byte? je endWhileNoNull ;stop copying if null movsb ;copy one byte jmp whileNoNull ;go check next byte endWhileNoNull: mov BYTE PTR [edi],0 ;terminate destination string popf ;restore flags and registers pop esi pop edi pop ebp ret 8 ;exit procedure, discarding parameters strcopy ENDP END

Figure 7.3: String copy program

The procedure only uses registers ESI and EDI. It saves each of these and the flag register on the stack so that the procedure will return with them unchanged. The index registers ESI and EDI must be initialized to the addresses of the first string bytes to be processed. The values for ESI and EDI are the arguments that were pushed on the stack. The direction flag is cleared for left-to-right copying.

After initialization, the procedure executes the following pseudocode design:

while next source byte is not null copy source byte to destination; increment source index; increment destination index; end while; put null byte at end of destination string;

To check whether the next source byte is null, the statement

cmp BYTE PTR [esi],0 ; null source byte?

is used. Recall that the notation [esi] indicates register indirect addressing, so that the element at the address in ESI is used, that is, the current byte of the source string. The operator BYTE PTR is necessary since MASM cannot tell from the operands [esi] and 0 whether byte, word, or doubleword comparison is needed. Copying the source byte and incrementing both index registers is accomplished by the movsb instruction. Finally,

mov BYTE PTR [edi],0 ; terminate destination string

serves to move a null byte to the end of the destination string since EDI was incremented after the last byte of the source was copied to the destination. Again, the operator BYTE PTR tells MASM that the destination is a byte rather than a word or doubleword.

The program to test strcopy simply inputs a string from the keyboard, calls strcopy to copy it somewhere else, and finally displays the string copy. The most interesting part of the code is the collection of instructions needed to call the procedure. The arguments are not removed from the stack since the procedure does that job.

Normally the source string for a movs instruction does not overlap the destination string. However, occasionally this is useful. Suppose that you want to initialize a 80 character-long string at starSlash with the pattern */, repeated 40 times. The following code can do this task.

starSlash BYTE 80 DUP (?) ... mov starSlash, '*' ; first * mov starSlash+1, '/' ; first / lea esi, starSlash ; source address lea edi, starSlash+2 ; destination cld ; process left to right mov ecx, 78 ; characters to copy forCount: movsb ; copy next character loop forCount ; repeat

In this example, the first time movsb is executed, a * from the first string position is copied to the third position. The next iteration, a / is copied from the second to the fourth position. The third time, a * is copied from the third to the fifth position, and so on. The next section introduces an easier way to repeat a movs instruction.

Exercises 7.1

1. What will be the output of the following program?

   .386 .MODEL FLAT ExitProcess PROTO NEAR32 stdcall, dwExitCode:DWORD INCLUDE io.h ; header file for input/output cr equ 0dh ; carriage return character Lf equ 0ah ; line feed .STACK 4096 ; reserve 4096-byte stack .DATA ; global data string BYTE 'ABCDEFGHIJ' BYTE cr, Lf, 0 .CODE setup1 PROC NEAR32 lea esi, string ; beginning of string lea edi, string+5 ; address of 'F' cld ; forward movement ret setup1 ENDP _start: call setup1 ; set source, destination, direction movsb ; move 4 characters movsb movsb movsb output string ; display modified string INVOKE ExitProcess, 0 ; exit with return code 0 PUBLIC _start ; make entry point public END

2. Repeat Problem 1, replacing the procedure setup1 by

   setup2 PROC NEAR32 lea esi, string ; beginning of string lea edi, string+2 ; address of 'C' cld ; forward movement ret setup2 ENDP

3. Repeat Problem 1, replacing the procedure setup1 by

   setup3 PROC NEAR32 lea esi, string+9 ; end of string lea edi, string+4 ; address of 'E' std ; backward movement ret setup3 ENDP

4. Repeat Problem 1, replacing the procedure setup1 by

   setup4 PROC NEAR32 lea esi, string+9 ; end of string lea edi, string+7 ; address of 'H' std ; backward movement ret setup4 ENDP

Programming Exercises 7.1

1. Write a program that copies strings read in one at a time from the keyboard into a large storage area for later processing. Specifically, use the input macro to input a string, then copy the string to the first of a 1024 byte block of storage that has been reserved in the data segment. (Recall that the input macro produces a null-terminated string.) Follow the string by a carriage return and a linefeed character in this storage area. Repeat the process with additional strings, copying each subsequent string to the storage area so that it immediately follows the linefeed after the last string. Exit the loop when the first character of the source string is $-do not copy this last string to the storage area. Do, however, place a null byte after the linefeed of the last string in the storage area. Finally, use the output macro to display all the characters in the data area. The result should be the strings that were entered, one per line.

Repeat Prefixes and More String Instructions

Each 80x86 string instruction operates on one string element at a time. However, the 80x86 architecture includes three repeat prefixes that change the string instructions into versions that repeat automatically either for a fixed number of iterations or until some condition is satisfied. The three repeat prefixes actually correspond to two different single-byte codes; these are not themselves instructions, but supplement machine codes for the primitive string instructions, making new instructions.

Figure 7.4 shows two program fragments, each of which copies a fixed number of characters from sourceStr to destStr. The number of characters is loaded into the ECX register from count. The code in part (a) uses a loop. Since the count of characters might be zero, the loop is guarded by a jecxz instruction. The body of the loop uses movsb to copy one character at a time. The loop instruction takes care of counting loop iterations. The program fragment in part (b) is functionally equivalent to the one in part (a). After the count is copied into ECX, it uses the repeat prefix rep with a movsb instruction; the rep movsb instruction does the same thing as the last four lines in part (a).

lea esi, sourceStr ; source string lea edi, destStr ; destination cld ; forward movement mov ecx, count ; count of characters to copy jecxz endCopy ; skip loop if count is zero copy: movsb ; move 1 character loop copy ; decrement count and continue endCopy: (a) movsbiterated in a loop lea esi, sourceStr ; source string lea edi, destStr ; destination cld ; forward movement mov ecx, count ; count of characters to copy rep movsb ; move characters (b) repeat prefix with movsb

Figure 7.4: Copying a fixed number of characters of a string

The rep prefix is normally used with the movs instructions and with the stos instruction (discussed below). It causes the following design to be executed:

while count in ECX > 0 loop perform primitive instruction; decrement ECX by 1; end while;

Note that this is a while loop. The primitive instruction is not executed at all if ECX contains zero. It is not necessary to guard a repeated string instruction as it often is with an ordinary for loop implemented with the loop instruction.

The other two repeat prefixes are repe, with equivalent mnemonic repz, and repne, which is the same as repnz. The mnemonic repe stands for "repeat while equal" and repz stands for "repeat while zero." Similarly repne and repnz mean "repeat while not equal" and "repeat while not zero," respectively. Each of these repeat prefixes is appropriate for use with the two string instructions cmps and scas, which affect the zero flag ZF.

The names of these mnemonics partially describe their actions. Each instruction works the same as rep, iterating a primitive instruction while ECX is not zero. However, each also examines ZF after the string instruction is executed. The repe and repz continue iterating while ZF=1, as it would be following a comparison where two operands were equal. The repne and repnz continue iterating while ZF=0, as it would be following a comparison where two operands were different. Repeat prefixes themselves do not affect any flag. The three repeat prefixes are summarized in Fig. 7.5. Note that rep and repz (repe) generate exactly the same code.

Figure 7.5: Repeat prefixes

The repz and repnz prefixes do not quite produce true while loops with the conditions shown in Fig. 7.5. The value in ECX is checked prior to the first iteration of the primitive instruction, as it should be with a while loop. However, ZF is not checked until after the primitive instruction is executed. In practice, this is very convenient since the instruction is skipped for a zero count, but the programmer does not have to do anything special to initialize ZF prior to repeated instructions.

Figure 7.6 shows how the repeat prefix rep combines with the movs instructions. In the clock cycles columns, there is a "set up" time plus a time for each iteration. The n in the table represents the number of iterations, so that, for example, a rep movsb takes 33 (13+4×5) clock cycles on a Pentium to move five bytes. (The table entries are not strictly accurate since there are special timings for the 486 and Pentium when n=0 or n=1.)

Figure 7.6: rep movs instructions

The cmps instructions, summarized in Fig. 7.7, compare elements of source and destination strings. Chapter 5 explained how a cmp instruction subtracts two operands and sets flags based on the difference. Similarly, cmps subtracts two string elements and sets flags based on the difference; neither operand is changed. If a cmps instruction is used in a loop, it is appropriate to follow cmps by almost any of the conditional jump instructions, depending on the design being implemented.

Figure 7.7: cmps instructions

Repeat prefixes are often used with cmps instructions. In fact, for the task of finding if two strings are identical, the repe prefix is a perfect companion for cmps. Figure 7.7 summarizes all the cmps instructions, including repeated ones. Again, the timings are not strictly accurate for 486 and Pentium CPUs; for rep cmps there are special timings when n=0.

It is often necessary to search for one string embedded in another. Suppose that the task at hand is to find the position, if any, at which the string at key appears in the string at target. One simple algorithm to do this is

position := 1; while position < (targetLength - keyLength + 1) loop if key matches the substring of target starting at position then report success; exit process; end if; add 1 to position; end while; report failure;

This algorithm checks to see if the key string matches the portion of the target string starting at each possible position. Using 80x86 registers, checking for one match can be done as follows:

ESI := address of key; EDI := address of target + position - 1; ECX := length of key; forever loop if ECX = 0 then exit loop; end if; compare [ESI] and [EDI] setting ZF; increment ESI; increment EDI; decrement ECX; if ZF = 0 then exit loop; end if; end loop; if ZF = 1 then match was found; end if;

The forever loop is exactly what is done by the repeated string instruction repe cmpsb. Since the loop is terminated when either ECX = 0 or when ZF = 0, it is necessary to be sure that the last pair of characters compared were the same; this is the reason for the extra if structure at the end of the design. Figure 7.8 shows a complete program that implements this design.

; program to search for one string embedded in another ; author: R. Detmer revised: 10/97 .386 .MODEL FLAT ExitProcess PROTO NEAR32 stdcall, dwExitCode:DWORD INCLUDE io.h cr EQU 0dh ; carriage return character Lf EQU 0ah ; linefeed character .STACK 4096 ; reserve 4096-byte stack .DATA prompt1 BYTE "String to search? ", 0 prompt2 BYTE cr, Lf, "Key to search for? ", 0 target BYTE 80 DUP (?) key BYTE 80 DUP (?) trgtLength DWORD ? keyLength DWORD ? lastPosn DWORD ? failure BYTE cr,Lf,Lf,"The key does not appear in the string.",cr,Lf,0 success BYTE cr,Lf,Lf,'The key appears at position' position BYTE 11 DUP (?) BYTE " in the string.", cr, Lf, 0 PUBLIC _start ; make entry point public .CODE _start: output prompt1 ; ask for input target,80 ; and input target string lea eax, target ; find length of string push eax ; length parameter call strlen mov trgtLength,eax ; save length of target output prompt2 ; ask for input key,80 ; and input key string lea eax, key ; find length of string push eax ; length parameter call strlen mov keyLength,eax ; save length of key ; calculate last position of target to check mov eax,trgtLength sub eax,keyLength inc eax ; trgtLength − keyLength + 1 mov lastPosn, eax cld ; left to right comparison mov eax,1 ; starting position whilePosn: cmp eax,lastPosn ; position <= last_posn? jnle endWhilePosn ; exit if past last position lea esi,target ; address of target string add esi,eax ; add position dec esi ; address of position to check lea edi,key ; address of key mov ecx,keyLength ; number of positions to check repe cmpsb ; check jz found ; exit on success inc eax ; increment position jmp whilePosn ; repeat endWhilePosn: output failure ; the search failed jmp quit ; exit found: dtoa position,eax ; convert position to ASCII output success ; search succeeded quit: INVOKE ExitProcess, 0 ; exit with return code 0 strlen PROC NEAR32 ; find length of string whose address is passed on stack ; length returned in EAX push ebp ; establish stack frame mov ebp, esp pushf ; save flags push ebx ; and EBX sub eax, eax ; length := 0 mov ebx, [ebp+8] ; address of string whileChar: cmp BYTE PTR [ebx], 0 ; null byte? je endWhileChar ; exit if so inc eax ; increment length inc ebx ; point at next character jmp whileChar ; repeat endWhileChar: pop ebx ; restore registers and flags popf pop ebp ret 4 ; return, discarding parameter strlen ENDP END

Figure 7.8: String search program

The scan string instruction scas is used to scan a string for the presence or absence of a particular string element. The string that is examined is a destination string; that is, the address of the element being examined is in the destination index register EDI. With a scasb instruction, the element searched for is the byte in the AL register; with a scasw, it is the word in the AX register; and with a scasd, it is the doubleword in the EAX register. The scasb, scasw, and scasd instructions use no operand since the mnemonics tell the element size. Figure 7.9 summarizes the scas instructions; as with the previous repeated instructions, there are special timings for n=0 on the 486 and Pentium.

Figure 7.9: scas instructions (use EDI)

The program shown in Fig. 7.10 inputs a string and a character and uses repne scasb to locate the position of the first occurrence of the character in the string. It then displays the part of the string from the character to the end. The length of the string is calculated using the strlen procedure that previously appeared in Fig. 7.8; this time we assume that strlen is separately assembled. The lea instruction is used to load the offset of the string to be searched and cld ensures a forward search.

; Program to locate a character within a string. ; The string is displayed from the character to the end. ; author: R. Detmer revised: 10/97 .386 .MODEL FLAT ExitProcess PROTO NEAR32 stdcall, dwExitCode:DWORD INCLUDE io.h EXTRN strlen:NEAR32 PUBLIC _start cr EQU 0dh ; carriage return character Lf EQU 0ah ; linefeed character .STACK 4096 ; reserve 4096-byte stack .DATA prompt1 BYTE "String? ", 0 prompt2 BYTE cr, Lf, Lf, "Character? ", 0 string BYTE 80 DUP (?) char BYTE 5 DUP (?) label1 BYTE cr, Lf, Lf, "The rest of the string is ---", 0 crlf BYTE cr, Lf, 0 .CODE _start: output prompt1 ; prompt for string input string,80 ; get string lea eax, string ; find length of string push eax ; length parameter call strlen inc ecx ; include null in string length mov ecx, eax ; save length of string output prompt2 ; prompt for character input char,5 ; get character mov al, char ; character to AL lea edi, string ; offset of string cld ; forward movement repne scasb ; scan while character not found dec edi ; back up to null or matching character output label1 ; print label output [edi] ; output string output crlf ; skip to new line INVOKE ExitProcess, 0 ; exit with return code 0 END

Figure 7.10: Program to find character in string

After the search, the destination index EDI will be one greater than desired since a string instruction always increments index registers whether or not flags were set. If the search succeeded, EDI will contain the address of the character following the one that matched with AL, or the address of the character after the end of the string if ECX was decremented to zero. The dec edi instruction takes care of both cases, backing up to the position of the matching character if there was one, or to the null byte at the end of the string otherwise. The string length was incremented so that the null character would be included in the search. The output macro displays the last portion of the string, whose address is in EDI.

The store string instruction stos copies a byte, a word, or a doubleword from AL, AX, or EAX to an element of a destination string. A stos instruction affects no flag, so that when it is repeated with rep, it copies the same value into consecutive positions of a string. For example, the following code will store spaces in the first 30 bytes of string.

mov ecx,30 ; 30 bytes mov al, ' ' ; character to store lea edi, string ; address of string cld ; forward direction rep stosb ; store spaces

Information about the stos instructions is in Fig. 7.11. As with previous repeated string instructions, the 80486 and Pentium have special timings when n=0.

Figure 7.11: stos instructions (use EDI)

The load string instruction lods is the final string instruction. This instruction copies a source string element to the AL, AX, or EAX register, depending on the string element size. A lods instruction sets no flag. It is possible to use a rep prefix with lods but it is not helpful-all values except for the last string element would be replaced as successive values were copied to the destination register. A lods instruction is useful in a loop set up with other instructions, making it possible to easily process string elements one at a time. The lods instructions are summarized in Fig. 7.12. Repeated versions are not included since they are not used.

Figure 7.12: lods instructions (use ESI)

Exercises 7.2

For each exercise below, assume that the data segment contains

source BYTE "brown" dest BYTE "brine"

1. Suppose that the following instructions are executed:

   lea esi, source lea edi, dest cld mov ecx, 5 repne cmpsb

   Assuming that ESI starts at 00010000 and EDI starts at 00010005, what will be the values stored in ESI and EDI following the repne cmpsb instruction? What will be stored in ECX?

2. Suppose that the following instructions are executed:

   lea esi, source lea edi, dest cld mov ecx, 5 repe cmpsb

   Assuming that ESI starts at 00010000 and EDI starts at 00010005, what will be the values stored in ESI and EDI following the repe cmpsb instruction? What will be stored in ECX?

3. Suppose that the following instructions are executed:

   mov al, 'w' lea edi, dest cld mov ecx, 5 repe scasb

   Assuming that EDI starts at 00010005, what will be the value stored in EDI following the repe scasb instruction? What will be stored in ECX?

4. Suppose that the following instructions are executed:

   mov al, 'n' lea edi, dest cld mov ecx, 5 repne scasb

   Assuming that EDI starts at 00010005, what will be the value stored in EDI following the repne scasb instruction? What will be stored in ECX?

5. Suppose that the following instructions are executed:

   mov al, '*' lea edi, dest cld mov ecx, 5 rep stosb

   Assuming that EDI starts at 00010005, what will be the value stored in EDI following the rep stosb instruction? What will be stored in ECX? What will be stored in the destination string?

6. Suppose that the following instructions are executed:

   lea esi, source lea edi, dest cld mov ecx, 5 for6: lodsb inc al stosb loop for6 endFor6:

   Assuming that ESI starts at 00010000 and EDI starts at 00010005, what will be the values stored in ESI and EDI following the for loop? What will be stored in ECX? What will be stored in the destination string?

7. Suppose that the following instructions are executed:

   lea esi, source lea edi, dest cld mov ecx, 3 rep movsb

   Assuming that ESI starts at 00010000 and EDI starts at 00010005, what will be the values stored in ESI and EDI following the rep movsb instruction? What will be stored in ECX? What will be stored in the destination string?

8. Suppose that the following instructions are executed:

   lea esi, source+4 lea edi, dest+4 std mov ecx, 3 rep movsb

   Assuming that ESI starts at 00010010 and EDI starts at 00010015, what will be the values stored in ESI and EDI following the rep movsb instruction? What will be stored in ECX? What will be stored in the destination string?

Programming Exercises 7.2

1. Write a NEAR32 procedure index to find the position of the first occurrence of a character in a null-terminated string. Specifically, the procedure must have two parameters: (1) a character and (2) the address of a string in the data segment. Use the stack to pass the parameters: For the character, use an entire word with the character in the low-order byte. Use the EAX register to return the position of the character within the string; return zero if the character is not found. No other register should be altered. Procedure index will not remove parameters from the stack.
2. Write a NEAR32 procedure append that will append one null-terminated string to the end of another. Specifically, the procedure must have two parameters: (1) the address of string1 in the data segment and (2) the address of string2 in the data segment. Use the stack to pass the parameters. The procedure should copy the characters of string2 to the end of string1 with the first character of string2 replacing the null byte at the end of string1, and so on. (Warning: In the data section, enough space must be reserved after the null byte of the first string to hold the characters from the second string.) All registers used by the procedure should be saved and restored. Procedure append will not remove parameters from the stack.
3. Write a complete program that prompts for and inputs a person's name in the "LastName, FirstName" format and builds a new string with the name in the format "FirstName LastName." A comma and a space separate the names originally and there is no character except the null following FirstName; only a space separates the names in the new string. After you generate the new string in memory, display it.
4. Write a complete program which prompts for and inputs a person's name in the "LastName, FirstName" format and builds a new string with the name in the format "FirstName LastName." One or more spaces separate the names originally and there may be spaces following FirstName. Only a single space separates the names in the new string. After you generate the new string in memory, display it.
5. Write a complete program that prompts for and inputs a string and a single character. Construct a new string that is identical to the old one except that it is shortened by removing each occurrence of the character. After you generate the new string in memory, display it.
6. Write a complete program that prompts for and inputs a sentence and a single word. Construct a new sentence that is identical to the old one except that it is shortened by removing each occurrence of the word. After you generate the new sentence in memory, display it.
7. Write a complete program that prompts for and inputs a sentence and two words. Construct a new sentence that is identical to the old one except that each occurrence of the first word is replaced by the second word. After you generate the new sentence in memory, display it.

Character Translation

Sometimes character data are available in one format but need to be in another format for processing. One instance of this occurs when characters are transmitted between two computer systems, one normally using ASCII character codes and the other normally using EBCDIC character codes. Another time character codes need to be altered is to transmit them to a device that cannot process all possible codes; it is sometimes easier to replace the unsuitable codes by acceptable codes than to delete them entirely.

The 80x86 instruction set includes the xlat instruction to translate one character to another character. In combination with other string-processing instructions, it can easily translate all the characters in a string.

The xlat instruction requires only one byte of object code, the opcode D7. It takes five clock cycles to execute on an 80386, and four clock cycles on an 80486 or a Pentium. Prior to execution, the character to be translated is in the AL register. The instruction works by using a translation table in the data segment to look up the translation of the byte in AL. This translation table normally contains 256 bytes of data, one for each possible 8-bit value in AL. The byte at offset zero in the table-the first byte-is the character to which 00 is translated. The byte at offset one is the character to which 01 is translated. In general xlat uses the character being translated as an offset into the table, and the byte at that offset then replaces the character in AL.

The xlat instruction has no operand. The EBX register must contain the address of the translation table.

Figure 7.13 illustrates a short program which translates each character of string in place; that is, it replaces each character by its translation using the original location in memory. The heart of the program is the translation table and the sequence of instructions

; Translate uppercase letters to lowercase; don't change lower ; case letters and digits. Translate other characters to spaces. ; author: R. Detmer revised: 10/97 .386 .MODEL FLAT ExitProcess PROTO NEAR32 stdcall, dwExitCode:DWORD INCLUDE io.h PUBLIC _start cr EQU 0dh ; carriage return character Lf EQU 0ah ; linefeed character .STACK 4096 ; reserve 4096-byte stack .DATA string BYTE 'This is a #!$& STRING',0 strLength EQU $ - string - 1 label1 BYTE 'Original string ->',0 label2 BYTE cr, Lf, 'Translated string ->',0 crlf BYTE cr, Lf, 0 table BYTE 48 DUP (' '), '0123456789', 7 DUP (' ') BYTE 'abcdefghijklmnopqrstuvwxyz', 6 DUP (' ') BYTE 'abcdefghijklmnopqrstuvwxyz', 133 DUP (' ') .CODE _start: output label1 ; display original string output string output crlf mov ecx, strLength ; string length lea ebx, table ; address of translation table lea esi, string ; address of string lea edi, string ; destination also string forIndex: lodsb ; copy next character to AL xlat ; translate character stosb ; copy character back into string loop forIndex ; repeat for all characters output label2 ; display altered string output string output crlf INVOKE ExitProcess, 0 END

Figure 7.13: Translation program

mov ecx, strLength ; string length lea ebx, table ; address of translation table lea esi, string ; address of string lea edi, string ; destination also string forIndex: lodsb ; copy next character to AL xlat ; translate character stosb ; copy character back into string loop forIndex ; repeat for all characters

These instructions implement a for loop with the design

for index := 1 to stringLength loop load source character into AL; translate character in AL; copy character in AL to destination; end for;

One new feature in this program is the use of the location counter symbol $. Recall that the assembler calculates addresses as if they start at 00000000, and increments a counter every time it generates bytes of object code. The dollar sign symbol refers to the value of this counter at the time it is encountered in assembly. In this particular program, it will be at the address just beyond the null byte of the string. Since the symbol string actually references its address, the expression string - $ is the length of string, including the null byte. The value equated to strLength is string - $ - 1, which excludes the null byte. The assembly process will be discussed more in Chapter 9.

Each ASCII code is translated to another ASCII code by this program. Uppercase letters are translated to lowercase, lowercase letters and digits are unchanged, and all other characters are translated to spaces. Construction of such a table involves looking at a table of ASCII codes (see Appendix A). For this program the translation table is defined by

table BYTE 48 DUP (' '), '0123456789', 7 DUP (' ') BYTE 'abcdefghijklmnopqrstuvwxyz', 6 DUP (' ') BYTE 'abcdefghijklmnopqrstuvwxyz', 133 DUP (' ')

Careful counting will show that exactly 256 bytes are defined. Recall that a BYTE directive stores the ASCII code of each character operand. Each of the first 48 bytes of the table will contain the ASCII code for a space (i.e., blank), 2016. Therefore if the code in the AL register represents any of the first 48 ASCII characters-a control character, or one of the printable characters from 2016 (space) to 2F16 (/)-it will be translated to a space.

Note that it is legal to translate a character to itself. Indeed, this is what will happen for digits; the ASCII codes 3016 to 3916 for digits 0 through 9 appear at offsets 3016 to 3916. The codes for the seven characters : through @ are next in an ASCII chart; each of these will be translated to a space. The next ASCII characters are the uppercase letters and the next entries in the table are codes for the lowercase letters. For example, the table contains 6116 at offset 4116, so an uppercase A (ASCII code 4116) will be translated to a lower case a (ASCII code 6116). The next six blanks are at the offsets 9116 ([) through 9616 (‘), so that each of these characters is translated to a blank. The ASCII code for each lowercase letter is assembled at an offset equal to its value, so each lowercase letter is translated to itself. Finally, the translation table contains 133 ASCII codes for blanks; these are the destinations for {, |, }, ~, DEL, and each of the 128 bit patterns starting with a one, none of them codes for ASCII characters.

Figure 7.14 shows the output of the program in Fig. 7.13. Notice that "strange" characters are not deleted, they are replaced by blanks.

Original string ->This is a #!$& STRING Translated string ->this is a string

Figure 7.14: Output from translation program

Exercises 7.3

1. Here is a partial hexadecimal/EBCDIC conversion table:

   81 a	C1 A	40 space
   82 b	C2 B	4B .
   83 c	C3 C	6B ,
   84 d	C4 D
   85 e	C5 E	F0 0
   86 f	C6 F	F1 1
   87 g	C7 G	F2 2
   88 h	C8 H	F3 3
   89 i	C9 I	F4 4
   91 j	D1 J	F5 5
   92 k	D2 K	F6 6
   93 l	D3 L	F7 7
   94 m	D4 M	F8 8
   95 n	D5 N	F9 9
   96 o	D6 O
   97 p	D7 P
   98 q	D8 Q
   99 r	D9 R
   A2 s	E2 S
   A3 t	E3 T
   A4 u	E4 U
   A5 v	E5 V
   A6 w	E6 W
   A7 X	E7 X
   A8 y	E8 Y
   A9 z	E9 Z

   Give a translation table that would be suitable for xlat translation of EBCDIC codes for letters, digits, space, period, and comma to the corresponding ASCII codes, translating every other EBCDIC code to a null character.

2. Give a translation table that would be suitable for xlat translation of ASCII codes for lowercase letters to the corresponding uppercase letters, leaving all other characters unchanged.
3. Here is an alternative to the xlat instruction.

   movzx eax, al ; clear high order bits in EAX mov al, [ebx+eax] ; copy new character from table to AL

   Given that [ebx+eax] references the memory byte at the address that is the sum of the contents of EBX and EAX, explain why this pair of instructions is equivalent to a single xlat instruction.

Programming Exercises 7.3

1. In the United States, decimal numbers are written with a decimal point separating the integral part from the fractional part and with commas every three positions to the left of the decimal point. In many European countries, decimal numbers are written with the roles of commas and decimal points reversed. For example, the number 1,234,567.89 would be written 1.234.567,89. Write a program that will interchange commas and periods, translating a string of characters representing either format of number to the other format. Use the xlat instruction with a translation table that translates a period to a comma, a comma to a period, each digit to itself, and any other character to a space. Prompt for and input the number to be translated. Translate the string. Display the new number format with an appropriate label.

Converting a 2 s Complement Integer to an ASCII String

The dtoa and itoa macros have been used to convert 2’s complement integers to strings of ASCII characters for output. The code for these operations is similar. In this section we examine the slightly shorter code for itoa.

The itoa macro expands into the following sequence of instructions.

push ebx ; save EBX mov bx, source push bx ; source parameter lea ebx, dest ; destination address push ebx ; destination parameter call itoaproc ; call itoaproc(source,dest) pop ebx ; restore EBX

These instructions call procedure itoaproc after pushing the source value and the destination address on the stack. The actual source and destination are used in the expanded macro, not the names source and dest. So that the user does not need to worry about any register contents being altered, EBX is initially saved on the stack and is restored at the end of the sequence. The parameters are removed from the stack by procedure itoaproc since the alternative add esp,6 following the call instruction potentially changes the flags.

The real work of 2’s complement integer to ASCII conversion is done by the procedure itoaproc. The assembled version of this procedure is contained in the file IO.OBJ. The source code from file IO.ASM is shown in Fig. 7.15. The procedure begins by saving all of the registers that it alters on the stack; the flag register is also saved so that the procedure call to itoaproc will not change flag settings. The flag register and other registers are restored immediately before returning from the procedure.

; itoaproc(source, dest) ; convert integer (source) to string of 6 characters at destination address itoaproc PROC NEAR32 push ebp ; save base pointer mov ebp, esp ; establish stack frame push eax ; Save registers push ebx ; used by push ecx ; procedure push edx push edi pushf ; save flags mov ax, [ebp+12] ; first parameter (source integer) mov edi, [ebp+8] ; second parameter (dest address) ifSpecial: cmp ax,8000h ; special case −32,768? jne EndIfSpecial ; if not, then normal case mov BYTE PTR [edi],'-' ; manually put in ASCII codes mov BYTE PTR [edi+1],'3' ; for −32,768 mov BYTE PTR [edi+2],'2' mov BYTE PTR [edi+3],'7' mov BYTE PTR [edi+4],'6' mov BYTE PTR [edi+5],'8' jmp ExitIToA ; done with special case EndIfSpecial: mov dx, ax ; save source number mov al,' ' ; put blanks in mov ecx,5 ; first five cld ; bytes of rep stosb ; destination field mov ax, dx ; copy source number mov cl,' ' ; default sign (blank for +) IfNeg: cmp ax,0 ; check sign of number jge EndIfNeg ; skip if not negative mov cl,'-' ; sign for negative number neg ax ; number in AX now >= 0 EndIfNeg: mov bx,10 ; divisor WhileMore: mov dx,0 ; extend number to doubleword div bx ; divide by 10 add dl,30h ; convert remainder to character mov [edi],dl ; put character in string dec edi ; move forward to next position cmp ax,0 ; check quotient jnz WhileMore ; continue if quotient not zero mov [edi],cl ; insert blank or "-" for sign ExitIToA: popf ; restore flags and registers pop edi pop edx pop ecx pop ebx pop eax pop ebp ret 6 ;exit, discarding parameters itoaproc ENDP

Figure 7.15: Integer to ASCII conversion procedure

The basic idea of the procedure is to build a string of characters right to left by repeatedly dividing the number by 10, using the remainder to determine the rightmostcharacter. For instance, dividing the number 2895 (0B4F16) by 10 gives a remainder of 5 and a quotient of 289 (012116), the last digit of the number and a new number with which to repeat the process. This scheme works nicely for positive numbers, but a negative number must be changed to its absolute value before starting the division loop. To complicate things further, the bit pattern 800016 represents the negative number −32,76810, but +32,768 cannot be represented in 2’s complement form in a 16-bit word.

After standard entry code, the value parameter is copied to AX and the destination address to EDI. The procedure then checks for the special case 800016. If this is the value, then the ASCII codes for 32768 are moved one at a time to the destination, using the fact that the destination address is in EDI. The location for the minus sign is in the EDI register, so register indirect addressing can be used to put this character in the correct memory byte. The location for the character 3 is one byte beyond the address contained in EDI; this address is referenced by [edi+1]. The remaining four characters are similarly put in place, and the procedure is exited.

The next step of the procedure is to put five leading blanks in the six-byte-long destination field. The procedure does this with a rep stosb, which uses EDI to point to successive bytes in destination field. Note that EDI is left pointing at the last byte of the destination field.

The procedure next stores the correct "sign" in the CL register. A blank is used for a number greater than or equal to zero, and minus character (−) is used for a negative number. A negative number is also negated, giving its absolute value for subsequent processing.

Finally the main idea is executed. The divisor 10 is placed in the BX register. The non-negative number is extended to a doubleword by moving zeros to DX. Division by 10 in BX gives a remainder from 0 to 9 in DX, the last decimal digit of the number. This is converted to the corresponding ASCII code by adding 3016; recall that the ASCII codes for digits 0 through 9 are 3016 through 3916. A mov using register indirect addressing puts the character in place in the destination string, and EDI is decremented to point at the next position to the left.

This process is repeated until the quotient is zero. Finally the "sign" stored in CL (blank or –) is copied to the immediate left of the last code for a digit. Other positions to the left, if any, were previously filled with blanks.

Exercises 7.4

1. Why does itoaproc use a destination string six bytes long?
2. Suppose that negative numbers are not changed before the division loop of itoaproc begins and that an idiv instruction is used rather than a div instruction in this loop. Recall that when a negative number is divided by a positive number, both quotient and remainder will be negative. For instance, −1273 = 10*(−127) + (−3). How could the rest of the division loop be modified to produce the correct ASCII codes for both positive and negative numbers?

Programming Exercises 7.4

1. Rewrite itoaproc, adding a length parameter. Specifically, the new itoaNew will be a NEAR32 procedure with three parameters, passed on the stack:
   1. the 2’s complement number to convert to ASCII characters (a word)
   2. the address of the ASCII string (a doubleword)
   3. the desired length of the ASCII string (a word)

   The number will be converted to a string of ASCII characters starting at the offset in the data segment. Do not use a blank in front of a positive number. If the length is less than or equal to the actual number of characters needed to display the number, fill the entire field with pound signs (#). If the length is larger than needed, pad with extra spaces to the left of the number. The procedure will remove parameters from the stack and must modify no register.

2. Write a NEAR32 procedure hexString that converts a 32-bit integer to a string of exactly eight characters representing its value as a hexadecimal number. (That is, the output characters will be 0–9 and A–F, with no blanks.) The procedure will have two parameters, passed on the stack:
   1. the number
   2. the address of the destination string

   The procedure will remove parameters from the stack and must modify no register. (The remainder upon division by 16 produces a decimal value corresponding to the rightmost hex digit.)

3. Write a NEAR32 procedure binaryString that converts a 32-bit integer to a string of exactly 32 characters representing its value as a binary number. The procedure will have two parameters, passed on the stack:
   1. the number
   2. the address of the destination string

   The procedure will remove parameters from the stack and must modify no register. (The remainder upon division by 2 gives the rightmost bit.)

Other Architectures CISC versus RISC Designs

Early digital computers had very simple instruction sets. When designers began to use microcode to implement instructions in the 1960s, it became possible to have much more complex instructions. At the same time high-level programming languages were becoming popular, but language compilers were fairly primitive. This made it desirable to have machine language statements that almost directly implemented high-level language statements, increasing the pressure to produce computer architectures with many complex instructions.

The Intel 80x86 machines use complex instruction set computer (CISC) designs. Instructions such as the string instructions discussed in this chapter would never have appeared in early computers. CISC machines also have a variety of memory addressing modes, and the 80x86 family is typical in this respect, although you have only seen a few of its modes so far. Often CISC instructions take several clock cycles to execute.

Reduced instruction set computer (RISC) designs began to appear in the 1980s. These machines have relatively few instructions and few memory addressing modes. Their instructions are so simple that any one can be executed in a single clock cycle. As compiler technology improved, it became possible to produce efficient code for RISC machines. Of course, it often takes many more instructions to implement a given high-level language statement on a RISC than on a CISC machine, but the overall operation is often faster because of the speed with which individual instructions execute.

In RISC architectures, instructions are all the same format; that is, the same number of bytes are encoded in a common pattern. This is not the case with CISC architectures. If the 80x86 chips were RISC designs, then this book would have no questions asking "How many clock cycles?" or "How many bytes?" When we look at the many 80x86 instruction formats in Chapter 9, you may wish for the simplicity of a RISC machine.

One unusual feature of many RISC designs is a relatively large collection of registers (sometimes over 500), of which only a small number (often 32) are visible at one time. Registers are used to pass parameters to procedures, and the registers that are used to store arguments in the calling program overlap the registers that are used to receive the parameter values in the procedure. This provides a simple but very efficient method of communication between a calling program and a procedure.

There are proponents of both CICS and RISC designs. At this point in time it is not obvious that one is clearly better than the other. However, the popular Intel 80x86 and Motorola 680x0 families are both CISC designs, so we will be dealing with CISC systems at least in the near future.

Summary

The word string refers to a collection of consecutive bytes, words, or doublewords in memory. The 80x86 instruction set includes five instructions for operating on strings: movs (to move or copy a string from a source to a destination location), cmps (to compare two strings), scas (to scan a string for a particular element), stos (to store a given value in a string), and lods (to copy a string element into EAX, AX, or AL). Each of these has mnemonic forms ending with b, w, or d to give the size of the string element.

A string instruction operates on one string element at a time. When a source string is involved, the source index register ESI contains the address of the string element. When a destination string is involved, the destination index register EDI contains the address of the string element. An index register is incremented or decremented after the string element is accessed, depending on whether the direction flag DF is reset to zero or set to one; the cld and std instructions are used to give the direction flag a desired value.

Repeat prefixes rep, repe (repz), and repne (repnz) are used with some string instructions to cause them to repeat automatically. The number of times to execute a primitive instruction is placed in the ECX register. The conditional repeat forms use the count in ECX but will also terminate instruction execution if the zero flag gets a certain value; these are appropriate for use with the cmps and scas instructions that set or reset ZF.

The xlat instruction is used to translate the characters of a string. It requires a 256-byte-long translation table that starts with the destination byte to which the source byte 00 is translated and ends with the destination byte to which the source byte FF is translated. The xlat instruction can be used for such applications as changing ASCII codes to EBCDIC codes or for changing the case of letters within a given character coding system.

The itoa macro expands to code that calls a procedure itoaproc. Basically this procedure works by repeatedly dividing a non-negative number by 10 and using the remainder to get the rightmost character of the destination string.

The 80x86 chips are examples of complex instruction set computer (CISC) architecture. They include many complex instructions and offer many different addressing modes. Reduced instruction set computer (RISC) architectures implement fewer and simpler instructions and have more limited addressing options. Even though RISC computers take more instructions to accomplish a task, they are usually quite fast since they execute their simple instructions very rapidly.