|
Table of Content | Chapter Fifteen (Part 5) |
|
Table of Content | Chapter Fifteen (Part 5) |
| CHAPTER
FIFTEEN: STRINGS AND CHARACTER SETS (Part 4) |
|
| 15.3 -
Character String Functions 15.3.1 - Substr 15.3.2 - Index 15.3.3 - Repeat |
15.3.4
- Insert 15.3.5 - Delete 15.3.6 - Concatenation |
| 15.3 Character String Functions | |
Most high level languages like Pascal BASIC "C" and PL/I provide several string functions and procedures (either built into the language or as part of a standard library). Other than the five string operations provided above the 80x86 doesn't support any string functions. Therefore if you need a particular string function you'll have to write it yourself. The following sections describe many of the more popular string functions and how to implement them in assembly language.
The Substr (substring) function copies a
portion of one string to another. In a high level language
this function usually takes
the form:
DestStr := Substr(SrcStr Index Length);
where:
DestStr is the name of the string variable
where you want to store the substring
SrcStr is the name of the source string (from
which the substring is to be taken)
Index is the starting character position within
the string (1..length(SrcStr))
and DestStr.
The following examples show how Substr works.
SrcStr := 'This is an example of a string'; DestStr := Substr(SrcStr 11 7); write(DestStr);
This prints 'example'. The index value is eleven
so
the Substr
function will begin copying data starting at the eleventh character in the string. The
eleventh character is the 'e' in 'example'. The length of the string is seven.
This invocation copies the seven characters 'example' to DestStr.
SrcStr := 'This is an example of a string'; DestStr := Substr(SrcStr 1 10); write(DestStr);
This prints 'This is an'. Since the index is one
this
occurrence of the Substr function starts copying 10 characters starting with
the first character in the string.
SrcStr := 'This is an example of a string'; DestStr := Substr(SrcStr 20 11); write(DestStr);
This prints 'of a string'. This call to Substr
extracts the last eleven characters in the string.
What happens if the index and length values are out of
bounds? For example
what happens if Index is zero or is greater than the
length of the string? What happens if Index is fine
but the sum of Index
and Length is greater than the length of the source string? You can handle
these abnormal situations in one of three ways: (1)ignore the possibility of error;
(2)abort the program with a run-time error; (3)process some reasonable number of
characters in response to the request.
The first solution operates under the assumption that the
caller never makes a mistake computing the values for the parameters to the Substr
function. It blindly assumes that the values passed to the Substr function
are correct and processes the string based on that assumption. This can produce some
bizarre effects. Consider the following examples
which use length-prefixed strings:
SourceStr :='1234567890ABCDEFGHIJKLMNOPQRSTUVWXYZ';
DestStr := Substr(SourceStr
0
5);
Write('DestStr');
prints '$1234'. The reason
of course
is that SourceStr
is a length-prefixed string. Therefore the length
36
appears at offset zero within the
string. If Substr uses the illegal index of zero then the length of the
string will be returned as the first character. In this particular case
the length of the
string
36
just happened to correspond to the ASCII code for the '$' character.
The situation is considerably worse if the value specified
for Index is negative or is greater than the length of the string. In such a
case
the Substr function would be returning a substring containing
characters appearing before or after the source string. This is not a reasonable result.
Despite the problems with ignoring the possibility of error
in the Substr function
there is one big advantage to processing substrings
in this manner: the resulting Substr code is more efficient if it doesn't
have to perform any run-time checking on the data. If you know that the index and length
values are always within an acceptable range
then there is no need to do this checking
within Substr function. If you can guarantee that an error will not occur
your programs will run (somewhat) faster by eliminating the run-time check.
Since most programs are rarely error-free
you're taking a
big gamble if you assume that all calls to the Substr routine are passing
reasonable values. Therefore
some sort of run-time check is often necessary to catch
errors in your program. An error occurs under the following conditions:
Index) is less than one. Index is greater than the length of the string.
Substr length parameter (Length)
is greater than the length of the string. Index and Length is
greater than the length of the string. An alternative to ignoring any of these errors is to abort
with an error message. This is probably fine during the program development phase
but
once your program is in the hands of users it could be a real disaster. Your customers
wouldn't be very happy if they'd spent all day entering data into a program and it
aborted
causing them to lose the data they've entered. An alternative to aborting when an
error occurs is to have the Substr function return an error condition. Then
leave it up to the calling code to determine if an error has occurred. This technique
works well with the third alternative to handling errors: processing the substring as best
you can.
The third alternative handling the error as best you can is probably the best alternative. Handle the error conditions in the following manner:
Index) is less than one.
There are two ways to handle this error condition. One way is to automatically set the Index
parameter to one and return the substring beginning with the first character of the source
string. The other alternative is to return the empty string
a string of length zero
as
the substring. Variations on this theme are also possible. You might return the substring
beginning with the first character if the index is zero and an empty string if the index
is negative. Another alternative is to use unsigned numbers. Then you've only got to worry
about the case where Index is zero. A negative number
should the calling
code accidentally generate one
would look like a large positive number. Substr function should return an empty string.
Intuitively
this is the proper response in this situation. Substr length parameter (Length)
is greater than the length of the string. -or- Index and Length is
greater than the length of the string. Points three and four are the same problem
the
length of the desired substring extends beyond the end of the source string. In this
event
Substr should return the substring consisting of those characters
starting at Index through the end of the source string. The following code for the Substr function
expects four parameters: the addresses of the source and destination strings
the starting
index
and the length of the desired substring. Substr expects the parameters
in the following registers:
ds:si- The address of the source string.
es:di- The address of the destination string.
ch- The starting index.
cl- The length of the substring.
Substr returns the following values:
es:di. Substr clears the carry flag if there were no
errors. Substr sets the carry flag if there was an error. Substr preserves all the registers. If an error occurs
then the calling code must examine the
values in si
di and cx to determine the exact cause of the
error (if this is necessary). In the event of an error
the Substr function
returns the following substrings:
Index parameter (ch) is
zero
Substr uses one instead. Index and Length parameters
are both unsigned byte values
therefore they are never negative. Index parameter is greater than the
length of the source string
Substr returns an empty string. Index and Length
parameters is greater than the length of the source string
Substr returns
only those characters from Index through the end of the source string. The
following code realizes the substring function. ; Substring function. ; ; HLL form: ; ;procedure substring(var Src:string; ; Index Length:integer; ; var Dest:string); ; ; Src- Address of a source string. ; Index- Index into the source string. ; Length- Length of the substring to extract. ; Dest- Address of a destination string. ; ; Copies the source string from address [Src+index] of length ; Length to the destination string. ; ; If an error occurs the carry flag is returned set otherwise ; clear. ; ; Parameters are passed as follows: ; ; DS:SI- Source string address. ; ES:DI- Destination string address. ; CH- Index into source string. ; CL- Length of source string. ; ; Note: the strings pointed at by the SI and DI registers are ; length-prefixed strings. That is the first byte of each ; string contains the length of that string. Substring proc near push ax push cx push di push si clc ;Assume no error. pushf ;Save direction flag status. ; Check the validity of the parameters. cmp ch [si] ;Is index beyond the length of ja ReturnEmpty ; the source string? mov al ch ;See if the sum of index and dec al ; length is beyond the end of the add al cl ; string. jc TooLong ;Error if > 255. cmp al [si] ;Beyond the length of the source? jbe OkaySoFar ; If the substring isn't completely contained within the source ; string truncate it: TooLong: popf stc ;Return an error flag. pushf mov al [si] ;Get maximum length. sub al ch ;Subtract index value. inc al ;Adjust as appropriate. mov cl al ;Save as new length. OkaySoFar: mov es:[di] cl ;Save destination string length. inc di mov al ch ;Get index into source. mov ch 0 ;Zero extend length value into CX. mov ah 0 ;Zero extend index into AX. add si ax ;Compute address of substring. cld rep movsb ;Copy the substring. popf SubStrDone: pop si pop di pop cx pop ax ret ; Return an empty string here: ReturnEmpty: mov byte ptr es:[di] 0 popf stc jmp SubStrDone SubString endp
The Index string function searches for the
first occurrence of one string within another and returns the offset to that occurrence.
Consider the following HLL form:
SourceStr := 'Hello world'; TestStr := 'world'; I := INDEX(SourceStr TestStr);
The Index function scans through the source
string looking for the first occurrence of the test string. If found
it returns the index
into the source string where the test string begins. In the example above
the Index
function would return seven since the substring 'world' starts at the seventh
character position in the source string.
The only possible error occurs if Index cannot
find the test string in the source string. In such a situation
most implementations
return zero. Our version will do likewise. The Index function which follows
operates in the following fashion:
1) It compares the length of the test string to the length
of the source string. If the test string is longer
Index immediately returns
zero since there is no way the test string will be found in the source string in this
situation.
2) The index function operates as follows:
i := 1; while (i < (length(source)-length(test)) and test <> substr(source i length(test)) do i := i+1;
When this loop terminates if (i < length(source)-length(test)) then it contains the index into source where test begins. Otherwise test is not a substring of source. Using the previous example this loop compares test to source in the following manner:
i=1 test: world No match source: Hello world i=2 test: world No match source: Hello world i=3 test: world No match source: Hello world i=4 test: world No match source: Hello world i=5 test: world No match source: Hello world i=6 test: world No match source: Hello world i=7 test: world Match source: Hello world
There are (algorithmically) better ways to do this
comparison[7]
however
the algorithm above lends itself to the
use of 80x86 string instructions and is very easy to understand. Index's code
follows:
; INDEX- computes the offset of one string within another. ; ; On entry: ; ; ES:DI- Points at the test string that INDEX will search for ; in the source string. ; DS:SI- Points at the source string which (presumably) ; contains the string INDEX is searching for. ; ; On exit: ; ; AX- Contains the offset into the source string where the ; test string was found. INDEX proc near push si push di push bx push cx pushf ;Save direction flag value. cld mov al es:[di] ;Get the length of the test string. cmp al [si] ;See if it is longer than the length ja NotThere ; of the source string. ; Compute the index of the last character we need to compare the ; test string against in the source string. mov al es:[di] ;Length of test string. mov cl al ;Save for later. mov ch 0 sub al [si] ;Length of source string. mov bl al ;# of times to repeat loop. inc di ;Skip over length byte. xor ax ax ;Init index to zero. CmpLoop: inc ax ;Bump index by one. inc si ;Move on to the next char in source. push si ;Save string pointers and the push di ; length of the test string. push cx rep cmpsb ;Compare the strings. pop cx ;Restore string pointers pop di ; and length. pop si je Foundindex ;If we found the substring. dec bl jnz CmpLoop ;Try next entry in source string. ; If we fall down here the test string doesn't appear inside the ; source string. NotThere: xor ax ax ;Return INDEX = 0 ; If the substring was found in the loop above remove the ; garbage left on the stack FoundIndex: popf pop cx pop bx pop di pop si ret INDEX endp
The Repeat string function expects three
parameters- the address of a string
a length
and a character. It constructs a string of
the specified length containing "length" copies of the specified character. For
example
Repeat(STR
5
'*') stores the string '*****' into the STR
string variable. This is a very easy string function to write
thanks to the stosb instruction:
; REPEAT- Constructs a string of length CX where each element ; is initialized to the character passed in AL. ; ; On entry: ; ; ES:DI- Points at the string to be constructed. ; CX- Contains the length of the string. ; AL- Contains the character with which each element of ; the string is to be initialized. REPEAT proc near push di push ax push cx pushf ;Save direction flag value. cld mov es:[di] cl ;Save string length. mov ch 0 ;Just in case. inc di ;Start string at next location. rep stosb popf pop cx pop ax pop di ret REPEAT endp
The Insert string function inserts one string
into another. It expects three parameters
a source string
a destination string
and an
index. Insert inserts the source string into the destination string starting
at the offset specified by the index parameter. HLLs usually call the Insert procedure
as follows:
source := ' there'; dest := 'Hello world'; INSERT(source dest 6);
The call to Insert above would change source
to contain the string 'Hello there world'. It does this by inserting the string ' there'
before the sixth character in 'Hello world'.
The insert procedure using the following algorithm:
Insert(Src
dest
index);
1) Move the characters from location dest+index
through the end of the destination string length (Src) bytes up
in memory.
2) Copy the characters from the Src string to
location dest+index.
3) Adjust the length of the destination string so that it is the sum of the destination and source lengths. The following code implements this algorithm:
; INSERT- Inserts one string into another. ; ; On entry: ; ; DS:SI Points at the source string to be inserted ; ; ES:DI Points at the destination string into which the source ; string will be inserted. ; ; DX Contains the offset into the destination string where the ; source string is to be inserted. ; ; ; All registers are preserved. ; ; Error condition- ; ; If the length of the newly created string is greater than 255 ; the insert operation will not be performed and the carry flag ; will be returned set. ; ; If the index is greater than the length of the destination ; string ; then the source string will be appended to the end of the destin- ; ation string. INSERT proc near push si push di push dx push cx push bx push ax clc ;Assume no error. pushf mov dh 0 ;Just to be safe. ; First see if the new string will be too long. mov ch 0 mov ah ch mov bh ch mov al es:[di] ;AX = length of dest string. mov cl [si] ;CX = length of source string. mov bl al ;BX = length of new string. add bl cl jc TooLong ;Abort if too long. mov es:[di] bl ;Update length. ; See if the index value is too large: cmp dl al jbe IndexIsOK mov dl al IndexIsOK: ; Now make room for the string that's about to be inserted. push si ;Save for later. push cx mov si di ;Point SI at the end of current add si ax ; destination string. add di bx ;Point DI at the end of new str. std rep movsb ;Open up space for new string. ; Now copy the source string into the space opened up. pop cx pop si add si cx ;Point at end of source string. rep movsb jmp INSERTDone TooLong: popf stc pushf INSERTDone: popf pop ax pop bx pop cx pop dx pop di pop si ret INSERT endp
The Delete string removes characters from a
string. It expects three parameters - the address of a string
an index into that string
and the number of characters to remove from that string. A HLL call to Delete usually
takes the form:
Delete(Str index length);
For example
Str := 'Hello there world'; Delete(str 7 6);
This call to Delete will leave str containing
'Hello world'. The algorithm for the delete operation is the following:
1) Subtract the length parameter value from the length of the destination string and update the length of the destination string with this new value.
2) Copy any characters following the deleted substring over the top of the deleted substring.
There are a couple of errors that may occur when using the
delete procedure. The index value could be zero or larger than the size of the specified
string. In this case
the Delete procedure shouldn't do anything to the
string. If the sum of the index and length parameters is greater than the length of the
string
then the Delete procedure should delete all the characters to the end
of the string. The following code implements the Delete procedure:
; DELETE - removes some substring from a string. ; ; On entry: ; ; DS:SI Points at the source string. ; DX Index into the string of the start of the substring ; to delete. ; CX Length of the substring to be deleted. ; ; Error conditions- ; ; If DX is greater than the length of the string then the ; operation is aborted. ; ; If DX+CX is greater than the length of the string DELETE only ; deletes those characters from DX through the end of the string. DELETE proc near push es push si push di push ax push cx push dx pushf ;Save direction flag. mov ax ds ;Source and destination strings mov es ax ; are the same. mov ah 0 mov dh ah ;Just to be safe. mov ch ah ; See if any error conditions exist. mov al [si] ;Get the string length cmp dl al ;Is the index too big? ja TooBig mov al dl ;Now see if INDEX+LENGTH add al cl ;is too large jc Truncate cmp al [si] jbe LengthIsOK ; If the substring is too big truncate it to fit. Truncate: mov cl [si] ;Compute maximum length sub cl dl inc cl ; Compute the length of the new string. LengthIsOK: mov al [si] sub al cl mov [si] al ; Okay now delete the specified substring. add si dx ;Compute address of the substring mov di si ; to be deleted and the address of add di cx ; the first character following it. cld rep movsb ;Delete the string. TooBig: popf pop dx pop cx pop ax pop di pop si pop es ret DELETE endp
The concatenation operation takes two strings and appends
one to the end of the other. For example
Concat('Hello '
'world') produces
the string 'Hello world'. Some high level languages treat concatenation as a function
call
others as a procedure call. Since in assembly language everything is a procedure
call anyway
we'll adopt the procedural syntax. Our Concat procedure will
take the following form:
Concat(source1 source2 dest);
This procedure will copy source1 to dest
then it will concatenate source2 to the end of dest. Concat
follows:
; Concat- Copies the string pointed at by SI to the string ; rointed at by DI and then concatenates the string; ; pointed at by BX to the destination string. ; ; On entry- ; ; DS:SI- Points at the first source string ; DS:BX- Points at the second source string ; ES:DI- Points at the destination string. ; ; Error condition- ; ; The sum of the lengths of the two strings is greater than 255. ; In this event the second string will be truncated so that the ; entire string is less than 256 characters in length. CONCAT proc near push si push di push cx push ax pushf ; Copy the first string to the destination string: mov al [si] mov cl al mov ch 0 mov ah ch add al [bx] ;Compute the sum of the string's adc ah 0 ; lengths. cmp ax 256 jb SetNewLength mov ah [si] ;Save original string length. mov al 255 ;Fix string length at 255. SetNewLength: mov es:[di] al ;Save new string length. inc di ;Skip over length bytes. inc si rep movsb ;Copy source1 to dest string. ; If the sum of the two strings is too long the second string ; must be truncated. mov cl [bx] ;Get length of second string. cmp ax 256 jb LengthsAreOK mov cl ah ;Compute truncated length. neg cl ;CL := 256-Length(Str1). LengthsAreOK: lea si 1[bx] ;Point at second string and ; ; skip the string length. cld rep movsb ;Perform the concatenation. popf pop ax pop cx pop di pop si ret CONCAT endp
[7] The interested reader should look up the Knuth-Morris-Pratt algorithm in "Data Structure Techniques" by Thomas A. Standish. The Boyer-Moore algorithm is another fast string search routine although somewhat more complex.
|
Table of Content | Chapter Fifteen (Part 5) |
Chapter Fifteen: Strings And
Character Sets (Part 4)
28 SEP 1996