7. Byte and Halfword Addressing, Text Strings.

A Programming Problem, Text Manipulation

The Hawk monitor borrows its convention for recording the length of text strings from the C programming language. This is used in only one place, the PUTS routine, but it would be convenient to have access to the string processing routines of the C standard library. These include:

puts( src );

Given that src is the address of the first byte of a null-terminated string, output that string to the standard output device. Our PUTS does exactly this.

strncpy( dst, src, count );

Given src, a pointer to the first byte of a null-terminated string, copy the string, including the final null, to memory starting at the address dst but copy no more than count bytes. Usually, count is the size of the array pointed to by dst. The return value is the original value of dst.

strncat( dst, src, count );

Given src and dst, pointers to the first bytes of two null-terminated strings, concatenate the string pointed to by src onto the end of the string pointed to by dst, terminating the result with a null. As with strncpy(), count limits the number of characters copied from src to dst. A result longer than count characters will be truncated. The return value is the original value of dst.

strlen( src );

Given src, a pointer to the first byte of a null-terminated string, return the length of that string, up to but not including the null. Note that this returns the size of the string itself, not the size of the array it is stored in.

On most Unix systems, the man command gives full documentation for any of these routines; for example, to get the official documentation for strlen(), type the man strlen command into the shell interface. The book The C Programming Language by Kernighan and Ritchie (Prentice Hall, 1988) also documents these routines.

If we wish to write code for these functions, we need a way to load individual bytes from memory. As we saw in Chapter 2, Hawk memory addresses allow us to give a distinct address to each byte of memory, but the variations on the LOAD and STORE instructions introduced in Chapters 4, 5 and 6 all ignore the two least significant bits of the memory address and load or store a full 32-bit word.

The IBM System/360 was the first computer to offer support for 8-bit bytes, 16-bit halfwords and 32-bit words. This machine had load and store instructions for each operand size: load byte, load halfword and load word, along with store byte, store halfword and store word. This poses two problems:

First, if we commit to this idea, we need 6 opcodes for variants on load and store, and it is hard to find spare opcodes for these.

Second, loading and storing fractional words is inefficient. If the instruction set of the computer offers convenient load and store instructions for bytes and halfwords, this encourages programmers to make excessive use of them. Loading a byte on a machine with a 32-bit word generally involves loading the word holding that byte and then extracting the byte. If the instruction set exposes this, programmers will not be mislead into thinking that byte manipultion is as fast and efficient as word manipulation.

Exercises

a) One puzzle about the above interface definition is worth thinking about. Why do strncpy() and strncat() return their first argument as their return value? To demonstrate why, use this feature to compactly encode this list of string operations:

                strncpy( str, "Hello, ", 20 );
                strncat( str, "world", 12 );
                strncat( str, "!", 2 );

This loads the string pointed to by str with "Hello, world!" but not over 20 characters.

Byte and Halfword Extraction

The Hawk architecture offers two special instructions for extracting bytes and halfwords from full-word operands. These are designed for use after LOADS for fast loading of bytes and halfwords. The EXTB instruction is for extracting bytes; EXTH is similar, but operates on halfwords.

The Hawk EXTB instruction

07	06	05	04	03	02	01	00		15	14	13	12	11	10	09	08
0 1 0 1				dst				s1				s2

Formally, this does r[dst]=(r[s1]>>((r[s2]&3)<<3))&255. This formal notation is based entirely on the syntax common to C, C++ and Java, but it is not easy to read. Here an explanation:

r[dst]=(r[s1] ... )&255

A byte is taken from the register designated by the s1 field and moved to the destination register. The high 24 bits of the result is zero.

r[dst]= ... r[s1]>>((r[s2] ... ) ... ) ...

The byte extracted is determined by what is in the register designated by the s2 field.

... (R[S2] ... )<<3 ...

The shift count for byte selection is be a multiple of 8. (x<<3 is the same as x×8.)

... r[s2]&3 ...

The shift count depends only on the least significant two bits of the register designated by the s2 field because anding a bit pattern with 3₁₀ which is 11₂ forces all but those two bits to zero. These 2 bits of the second source register are the bits that select the byte within the word.

... (r[s2]&3)<<3 ...

From the above, we conclude that if the least significant two bits are 00, we get a shift count of 0, if they are 01, we get a shift count of 8, if they are 10, we get a shift count of 16, and if they are 11, we get a shift count of 24.

In long-winded English, this says that if the least significant 2 bits of the byte pointer Rp are 00, EXTB Rd,Rs,Rp will load the destination Rd with the least significant byte of the source register Rs. If the least significant 2 bits of Rp are 01, Rd will be loaded with the second to the least significant byte of Rs. If the least significant 2 bits are 10, Rd will be loaded with third byte of Rs and If the least significant 2 bits are 11, Rd will be loaded with the top byte of Rs. The result is always truncated to just 8 bits in the destination register.

As a result, if Rp contains a pointer, or memory address, and Rs contains a word that was loaded using that pointer, then the instruction EXTB Rd,Rs,Rp will pick, from Rs the byte pointed to by Rp and put that byte in Rd. The result will be in the range 0 — 255. So, if Rp contains a pointer to a byte, we can load that byte into a register as follows:

Loading an unsigned byte from memory

; given: R4, a pointer to a byte in memory LOADS R3,R4 ; get the word containing the desired byte EXTB R3,R3,R4 ; extract the desired byte from that word ; result: R3 now holds the desired byte; R3=M[R4]

EXTB and EXTH both set the condition codes to report on whether the extracted byte or halfword is zero or nonzero, so we can easily test for end-of-string as we extract bytes from a string during a string operation.

What if we wanted to extract signed halfwords in the range –32768 — +32727 or signed bytes in the range –128 — +127? The Hawk architecture solves this problem with a special instruction for sign extending any unsigned quantity. Recall that, to sign extend a two's complement number, you duplicate the sign bit to widen that number to the desired number of bits. For example if the the 4-bit numbers 1010 and 0101 are sign extended to 8 bits, the results will be 11111010 and 00000101. This operation preserves the value of the number while enlarging its representation. The above two's complement numbers, in either their 4-bit or 8-bit forms have the decimal values –6 and +5.

The Hawk sign extend instruction is called SXT. This takes a register and a count of the number of bits to be preserved, so SXT R3,8 extends the value in R3 by replacing its top 24 bits with whatever was in bit number 7. It is worth noting that another instruction, with the identical format, takes a signed quantity and forces all of the higher bits to zero; this is called truncation, and the instruction is called TRUNC.

Loading a signed byte from memory

; given R4, a pointer to a byte in memory LOADS R3,R4 ; get the word containing the desired byte EXTB R3,R3,R4 ; extract the desired byte from that word SXT R3,8 ; force a signed interpretation on it ; result R3 now holds the desired byte, sign extended to 32 bits

Exercises

b) Given that R1 holds ABCDEF₁₆, what value is left in the register after TRUNC R1,8? after TRUNC R1,6? after TRUNC R1,5? You can check your answer empirically using a Hawk emulator or debugger.

c) If the instruction EXTB R3,R3,R0 is used (In this context, register zero the constant zero), what is the result in R3 if its initial is ABCDEF₁₆? If its initial value is 123456₁₆? What useful function does this particular variant of the EXTB statement do?

Array Addressing

Consider the problem of writing code to access an element a[i] of an array a of characters. We'll assume that the integer i is within the array bounds, so we don't need to worry about bounds checking. Bounds checking is, after all, just a matter of if statements comparing with the upper and lower bounds of the array. To evaluate a[i], we proceed as follows:

1. Get the address of a[0].
2. Add the product of the subscript i and the size of an array element.
3. Use the resulting pointer to reference the indicated element.

In C or C++, the expression a[i] is always equivalent to *(a+i). In these languages, the unary * operator means "follow the pointer to the object it references in memory." Also, in C and C++, an array name is almost the same thing as a pointer to the first element of the array, and adding an integer to a pointer implicitly multiplies the integer by the size of the referenced object before adding. In the case of arrays of characters in C, each character is just one byte so the multiplication is trivial.

On the Hawk, the code for a[i] depends on whether a is a local variable, an array of constants embedded in the program text (such as the "hello world" array), or a global variable.
 

The expression A[i] for an array of bytes

; assume A is a local array of characters, i is in R3 LEA R4,R2,A ; get the address of A into R4 ADD R4,R3,R4 ; R4 now holds the address of A[i] LOADS R3,R4 ; R3 now holds the word at this address EXTB R3,R3,R4 ; R3 now holds the the array element A[i]

; assume A is a constant array of characters, i is in R3 LEA R4,A ; get the address of A into R4 ADD R4,R3,R4 ; R4 now holds the address of A[i] LOADS R3,R4 ; R3 now holds the word at this address EXTB R3,R3,R4 ; R3 now holds the the array element A[i]

; assume A is a global, allocated using COMMON, i is in R3 LIL R4,A ; get the address of A into R4 ADD R4,R3,R4 ; R4 now holds the address of A[i] LOADS R3,R4 ; R3 now holds the word at this address EXTB R3,R3,R4 ; R3 now holds the the array element A[i]

The above code fragments differ only in the initial instructions that load the address of the first array element. For local variables, the address is computed relative to the stack pointer, R2; for constants in the code, implicit PC-relative addressing is used, while for global variables, direct addressing is used. After that, everything is the same. The story for arrays of words is similar, except that we can use a simple LOADS to load each array element, but we must first multiply the array subscript by four before using it.
 

The expression A[i] for an array of words

; assume A is a local array of words, i is in R3 LEA R4,R2,A ; get the address of A into R4 SL R3,2 ; multiply R3 by 4 by shifting 2 places left ADD R4,R3,R4 ; R4 now holds the address of A[i] LOADS R3,R4 ; R3 now holds the word at this address

; assume A is a local array of words, i is in R3 LEA R4,R2,A ; get the address of A into R4 ADDSL R3,R4,2 ; multiply R3 by 4 and add R4 to the result LOADS R3,R3 ; R3 now holds the word at this address

In the above code fragments, the SL R3,2 instruction shifts the contents of R3 left two places, throwing away any bits shifted out the left end of the register and padding with zeros on the right. This is equivalent to multiplication by four; in general, SL R3,n multiplies by 2ⁿ, and because the sequence of shifting and then adding is common, the instruction ADDSL is available to combine these functions.

Both fragments coded for arrays of words illustrate only the case where the array is local, a part of the activation record. The problem of loading the starting address of the array does not depend on the size of the array elements, so the examples from the previous figure cover what is needed for constant or for global arrays.
 

Counting the Bytes in a Null Terminated String

We have now covered enough ground to write a subroutine to count the bytes in a null terminated string. In a high level language like C or C++, the following code works:

C code for strlen(src)

unsigned int strlen( char src[] ) { /* count the bytes in the null terminated string src */ int n = 0; while ( src[n] != '\0' ) { n = n + 1; } return n; }

This first version of the code views the string to be measured as an array of characters. Each iteration of the loop examines one character in this array, testing to see if it is the null character that marks the end of the string. Using the material on array addressing from the previous section, we can translate this code directly to Hawk assembly language as follows:

Hawk code for STRLEN using arrays

; receiving sequence assumptions for STRLEN (SLN) STRLEN: ; expects R3 -- src, the string's address ; uses R4 -- the address of src[n] ; R5 -- used to extract characters ; R6 -- holds n, the count of the length ; returns R3 -- the length of the string src LIS R6,0 ; n = 0; SLNLP: ; while (TRUE) { ADD R4,R3,R6 ; -- compute address of src[n] LOADS R5,R4 ; -- get word holding src[n] EXTB R5,R5,R4 ; -- extract the byte src[n] BZS SLNLX ; if (src[n] == '\0') break; ADDSI R6,1 ; n = n + 1; BR SLNLP SLNLX: ; } MOVE R3,R6 JUMPS R1 ; return n in R3

In C and C++, the name of an array is almost the same as a pointer to its first element. As a result, the declarations char src[] and char * src declare the parameter src to have exactly the same type, the address of a character in memory. Since strings in C and C++ are represented by arrays of consecutive characters, the natural way to pass a string to a function is by passing a pointer to its first character. This feature of the C and C++ languages is sometimes a source of serious confusion Here, though, we can exploit this to it to write an alternative version of strlen().

C code for strlen(src)

unsigned int strlen( char * src ) { int n = 0; while ( *src != '\0' ) { src = src + 1; n = n + 1; } return n; }

In the above, note that the asterisk operator applied as a prefix to a pointer causes pointer dereferencing. That is, it causes the computer to follow the pointer to the object it references. In this case, *src is the character pointed to by src and could also have been written as src[0].

In C and C++, adding an integer to a pointer produces a new pointer; the amount by which the memory address is incremented depends on the number of bytes occupied by the objects to which the pointer refers. In this case, since we are assuming that a char object occupies one byte, adding one to a char pointer increments the address by one. Adding one to an int pointer would incrment the address by 4 if we assume that int objects occupy 4 bytes. Note the word assume above! The C standard does not fix the number of bytes in objects of any of the standard types. We have covered enough detail now to translate the second version of the above code into Hawk assembly language.

Hawk code for STRLEN using pointer arithmetic

; receiving sequence assumptions for STRLEN (SLN) STRLEN: ; expects R3 -- src, the string's address ; uses R4 -- used to extract characters ; R5 -- holds n, the count of the length ; returns R3 -- the length of the string src LIS R5,0 ; n = 0; SLNLP: ; while (TRUE) { LOADS R4,R3 ; -- get word holding *src EXTB R4,R4,R3 ; -- extract the byte *src BZS SLNLX ; if (*src == '\0') break; ADDSI R3,1 ; src = src + 1; ADDSI R5,1 ; n = n + 1; BR SLNLP SLNLX: ; } MOVE R3,R5 JUMPS R1 ; return n in R3

Note that both versions of this code have exactly the same complexity One has an extra increment in the loop body, while the other must add in the base of the array during each iteration. If the array had been an array of integers, the second version would have been a bit faster, and there are optimizations that can make it even faster.

Both versions of this code have an important shortcoming: Each block of 4 consecutive iterations of the loop body will load exactly the same data into register 4 prior to extracting a byte. This is inefficient, and later, we will discuss some interesting tricks for eliminating this that have become common on new computers designed since the mid 1980's.

This code can also be tightened by some local optimizations that ignore these larger issues. There are two registers being incremented in the loop body; if we compute the string length from the difference of the initial and final values of the string pointer, we can eliminate one increment. In addition, there are two branches within the loop, one conditional and one unconditional; rewriting the loop so the termination test is at the end of the loop can eliminate one of these. Combining these optimizations, we can reduce the cost of the loop from 6 instructions per iteration down to 4.

Exercises

d) Improve the above code for STRLEN by eliminating one increment operator from the loop body, as suggested above.

e) Improve the above code for STRLEN by changing the control structure so that the loop exit test is done by a conditional branch back to the top of the loop from the end, as suggested above.

Stuffing Bytes into Words

On machines where all data transfers between processor and memory move 32-bit quantities, storing a byte or halfword into a word in memory involves first loading that word, then replacing the correct byte or halfword and finally storing the modified word back into memory. This is usually true even when the instruction set of the computer offers store byte or store halfword instructions.

In the case of the Hawk, the three steps described above must be carried out explicitly. The first and last steps are easily done with LOADS and STORES instructions. Two special instructions are provided for the middle step, one to stuff bytes into a register and the other to stuff halfwords. Here is the former:

The Hawk STUFFB instruction

07	06	05	04	03	02	01	00		15	14	13	12	11	10	09	08
0 1 1 1				dst				s1				s2

This is r[dst]=(r[dst]&~(0xFF<<((r[s2]&3)<<3))|((r[s1]&0xFF)<<((r[s2]&3)<<3)) in our formal notation. Unfortunately, as with the EXTB instruction, this formal notation neither compact nor very informative! The following comments should help in understanding this:

... (r[s2]&3)<<3 ...

This subexpression shows up twice above, and it also shows up in the description of EXTB. This takes the least significant 2 bits of r[s2] and multiplies by 8 to give values of 0, 8, 16 or 24.

... ~(0xFF<<((r[s2]&3)<<3)) ...

Here, we take the value 11111111₂ and shift it over 0, 8, 16 or 24 places so that the 8 ones line up with the byte to be stuffed. Then we invert the value making ones where there were zeros and zeros where there were ones. This is the value that is anded with the destination register in order to set the selected byte of the destination to zero.

... ((r[s1]&0xFF)<<((r[s2]&3)<<3)).

Here, we take the least significant byte of r[s1] and shift it over 0, 8, 16 or 24 places so that it lines up with the byte to be stuffed in place. Finally, we or it into place.

In long winded English, this says that if the least significant 2 bits of the byte pointer Rp are 00, STUFFB Rt,Rs,Rp will replace the least significant byte of the temporary register Rt with the least significant byte of the source register Rs. If the least significant 2 bits of Rp are 01, it will replace the second to the least significant byte of Rt with the least significant byte of Rs. If the least significant 2 bits of Rp are 10, it will replace the third byte of Rt with the low byte of Rs and if the least significant 2 bits of Rp are 11, it will replace the top byte of Rt with the low byte of Rs.

In effect, the instruction STUFFB Rt,Rs,Rp replaces the byte in the temporary register Rt selected by the least significant bits of the pointer register Rp with the low byte of Rs. Suppose we want to store the low byte of Rs in the memory location pointed to by Rp. To do this, we first load the word pointed to by Rp into a tempory register Rt, then stuff the byte into it before we store the word back in memory.
 

Stuffing a byte into memory

; given: R3, a byte pointer and R4, a byte to store LOADS R1,R3 ; get the word containing the desired byte STUFFB R1,R4,R3 ; insert the desired byte into that word STORES R1,R3 ; put the modified word back in memory ; result: R1 now holds a copy of the updated word, M[R3] = R4

Byte manipulation on the Hawk may appear cumbersome compared to byte manipulation on machines such as the IBM 360, the DEC PDP-11 or the Intel 80x86/Pentium family. On those machines, there is a single instruction that will load a byte from memory to register or store a byte from register to memory. The fact that it can be done in one instruction does not, however, make this a fast instruction. The instruction may still load an entire word from memory for modification, and in order to support this instruction, every word loaded from memory must pass through an alignment network that slightly slows every memory reference. The designers of some modern machines have opted to expose this complexity in the instruction set, allowing fast access to memory for words at the price of explicit byte extraction. The DEC Alpha processor provided the model for Hawk byte addressing.

Programmers who want to avoid knowing about byte extraction and stuffing can hide these details within macros. The macros given here will not be used later, but are given as examples. The naming convention we have used is that LOADBS and STOREBS indicate that these instructions are kin to LOADS and STORES, with B added to the suffix to indicate that they operate on bytes.

The STOREBS macro definition assumes that R1 can be used as a temporary location for byte stuffing. This is compatble with the use of R1 for subroutine linkage, since that use guarantees that R1 will be needed for every call, and therefore, between calls, it will usually be available for short-term use.
 

Byte manipulation macros

MACRO LOADBS =dst,=x LOADS dst,x EXTB dst,dst,x ENDMAC MACRO STOREBS =dst,=x LOADS R1,x STUFFB R1,dst,x STORES R1,x ENDMAC

Exercises

f) Given that the hardware interprets R0 as the constant zero in this context, what does STUFFB R3,R0,R0 do?

g) Write a LOADB macro that behaves like LOAD r,x,disp except that it loads a single byte into the destination register instead of loading a word. Use R1 as a temporary if needed.
 

A String Copy Subroutine

In setting out to write a Hawk assembly language version of the strncpy() routine from the C standard library, a reasonable first step is to write it in a high level language. The central part of our routine will be a loop copying one character per iteration from the source string to the destination string. This loop has two distinct terminating conditions: It must exit when we have copied the null marking the end of the string, and it must exit when the number of characters copied reaches the length limit.

Loops with two exit points are usually easier to read if the exits are coded similarly, so we will write this as an infinite loop with two explicit break statements instead of mixing break statements with other kinds of loop exits. The following code is written with no complex statements, in the hope that each assignment is simple enough to be replaced by a single machine instruction.
 

C code for strncpy(dst,src,len)

char * strncpy( char * dst, char * src, unsigned int len ) { char ch; char * return_value = src; while (TRUE) { if (len == 0) break; ch = *src; *dst = ch; if (ch = '\0') break; src = src + 1; dst = dst + 1; len = len - 1; } return return_value; }

STRNCPY in assembly language

; activation record format for STRNCPY string copy routine RETAD = 0 ; the return address ARSIZE = 4 ; size of activation record in bytes ; receiving sequence and assumptions STRNCPY:; expects R3 -- dst, the destination string address ; R4 -- src, the source address ; R5 -- len, the maximum length to copy ; uses R6 -- the return value ; R7 -- the character being copied ; returns R3 -- dst, unchanged STORES R1,R2 MOVE R6,R3 ; return_value = src STNCLP: ; while (TRUE) do { TESTR R5 BZS STNCLX ; if (len == 0) break ;* LOADS R7,R4 EXTB R7,R7,R4 ; ch = *src LOADS R1,R3 STUFFB R1,R7,R3 STORES R1,R3 ; *dst = ch TESTR R7 BZS STNCLX ; if (ch == '\0') break ADDSI R4,1 ; src = src + 1 ADDSI R3,1 ; dst = dst + 1 ADDSI R5,-1 ; len = len - 1 BR STNCLP STNCLX: ; } MOVE R3,R6 LOADS R1,R2 JUMPS R1 ; return dst pointer in R3

 
To begin the translation to assembly code, we worked out the register usage. By convention, parameters are passed in R3 and up, so dst goes in R3, src in R4, and len in R5. We can use R6 to hold the copy of dst needed as a return value, and R7 to hold the character being copied. Our convention that registers 3 to 7 can be used freely in any subroutine suggests that the above code should not need an activation record. Unfortunately, we needed one more register as a temporary for use with STUFFB. We used R1, and that forced us to save the return address.

This code is far from optimal. Like our assembly-code version of strlen(), it accesses each word of memory 4 times, once per byte. We can do better if we can process blocks of bytes.

We can improve the code by making local optimizations. For example, since the ADDSI R5,-1 right before the end of the loop sets the condition codes, we can replace the BR at the loop end with a BNZ to exit the loop when the count hits zero. This lets us move the loop-top label down to the point in the code marked with a star. We can eliminate the TESTR R7 in midloop, because EXTB sets the condition codes to report on the byte extracted and no instruction between the EXTB and the TESTR touches the condition codes. These changes let us eliminate 3 of the 13 instructions per iteration.

Finally, we can use R6 as the working pointer in the destination string, so that we never modify the copy in R3. This eliminates an instruction outside the loop, but it has no impact on the loop itself.

Exercises

h) Incorporate all of the suggested optimizations into STRNCPY.

i) Write Hawk code for strncat() that first finds the end of the destination string using logic from STRLEN and then copies the source string using logic from STRNCPY.

j) Suppose we eliminate one ADDSI per iteration of STRNCPY by changing the use of R5. Before the loop, we compute the highest permitted value of the destination pointer, and then compare the destination with this maximum value on each iteration. Does this lead to a faster version of STRNCPY? Compare with both the original and optimized versions.

k) Rewrite STRNCPY so it uses array addressing instead of pointer arithmetic.
 

Testing the String Processing Subroutines

A simple test of the above routines is to print the copy of a string and its length. Writing this in C, but using Hawk monitor calls, we get this:
 

Testing strncpy() and strlen()

main() { char buffer[12]; buffer[11]='/0'; putat( 6, 1 ) puts( strncpy( buffer, "String!", 11 )); putat( 1, 1 ) putdecu( strlen( buffer), 0 ); }

 
Those used to object oriented languages may not like explicitly declaring the memory into which the string is copied. The local variable buffer serves that purpose. It is an array of 12 characters or 3 words. We set buffer[11] to zero in case strncpy does not copy the null terminator. Our test program only lets strncpy change buffer[0] to buffer[10], leaving the null in buffer[11] to end overlength strings. These kinds of safety precautions are not needed when programming with the string types of languages like Java or Python, but are essential in C; forgetting to take these protective measures is the root cause of many security loopholes in C software.

The word buffer comes from electronics, where a buffer is an amplifier that passes its input to its output while changes at its output cannot leak back to the input. In software, the word refers to variables that sit between stages of a computation to serve a similar purpose.

The code given here uses the monitor routine PUTDECU. Note that, unlike the decimal print routine given in Chapter 6, this routine takes two parameters, the number to print and the field width. Passing zero as the second parameter tells it not to print any extra blanks around the number. Also, this code assumes that the STRCPY and STRLEN routines are be embedded in the same source file as the test routine. This code has not been optimized at all, and it includes many changes to the stack pointer that could easily be eliminated. They are left in in order to emphasize the mechanical rules for calling sequences we have been following.

This is the first main program we have seen that uses an non-trivial activation record. Main programs running under the Hawk monitor follow exactly the same calling conventions as all other subroutines discussed here. Local variables can be declared and addressed in exactly the same way as in any other subroutine. In this example, we have a local variable that is an array of 12 bytes. The instruction LEA R3,R2,BUFFER in the code that follows loads register 3 with a pointer to the first byte in the local variable BUFFER.
 

Testing STRNCPY and STRLEN

; activation record format for MAIN RETAD = 0 ; the return address BUFFER = 4 ; an array of 12 bytes (3 words) ARSIZE = 16 ; entry point for MAIN MAIN: ; expects nothing ; returns nothing STORES R1,R2 STORE R0,R2,BUFFER+8 ; buffer[8-11] = "\0\0\0\0" LIS R3,6 ; -- parameter x = 6 LIS R4,1 ; -- parameter y = 1 ADDI R2,ARSIZE LIL R1,PUTAT JSRS R1,R1 ADDI R2,-ARSIZE ; putat( 6, 1 ) LEA R3,R2,BUFFER ; -- parameter dst = buffer LEA R4,STRING ; -- parameter src = string LIS R5,11 ; -- parameter len = 11 ADDI R2,ARSIZE JSR R1,STRNCPY ADDI R2,-ARSIZE ; -- parameter s = strncpy( ... ) ADDI R2,ARSIZE LIL R1,PUTS JSRS R1,R1 ADDI R2,-ARSIZE ; puts(strncpy(buffer,string,11)) LIS R3,1 ; -- parameter x = 1 LIS R4,1 ; -- parameter y = 1 ADDI R2,ARSIZE LIL R1,PUTAT JSRS R1,R1 ADDI R2,-ARSIZE ; putat( 1, 1 ) LEA R3,R2,BUFFER ; -- parameter s = buffer ADDI R2,ARSIZE JSR R1,STRLEN ADDI R2,-ARSIZE ; -- parameter n = strlen( buffer ) LIS R4,0 ; -- parameter w ADDI R2,ARSIZE LIL R1,PUTDECU JSRS R1,R1 ; putdecu( strlen( buffer ), 0 ) ADDI R2,-ARSIZE LOADS R1,R2 JSRS R1,R1 ; return STRING: ASCII "String!",0

The above test program tests only one string, and it fails to test what happens when the string is longer than the buffer. A better test would test a variety of string lengths, some longer than the buffer and some shorter. One way to do this would be to use a loop to copy a variety of different substrings of the same source string, perhaps by varying the starting point within that string. At the end of each iteration, such a test should output both the result of the copy and the length of the copy.
 

Exercises

l) Optimize the test program by removing all unnecessary code to increment and decrement the stack pointer, and by substituting more efficient instructions wherever this is possible.

m) Write a test program that prints successively shorter substrings of "abcdefghijklmnop" using a for loop to select the starting point in the string (so all substrings end with the letter p, if it fits in the buffer). This program should copy each substring into an 11 byte buffer with the 12th byte set to zero, print the buffer, and print the string length.
 

String Concatenation

The C standard library routine for string concatenation, strncat(dst,src,len), provides an interesting exercise. This concatenates the null-terminated strings pointed to by dst and src, storing the result in the same buffer that held the original value of dst, copying no more than len bytes, and returning the pointer to the result.

This routine can be written from scratch, without using strlen() or strncpy(), but if we use them, the result as a very small routine. First, we use strlen() to find the length of the dst string, and then we offset a copy of the dst pointer so it points to the end of the string. Finally, strncpy() is used to copy src onto the end of the dst string, up to but not over the end of the buffer. In C, this can be done as follows:
 

C code for strncat(dst,src,len)

char * strncat( char * dst, char * src, unsigned int len ) { int dstlen = strlen(dst); strncpy( dst + dstlen, src, len ); return dst; }

This approach to concatenating strings is an excellent test of the strlen() and strncpy() routines, and in addition, it is a good way to illustrate, at the assembly language level, how we can call two routines we have already written from within another routine.

If we intend to put all of the routines in our string package in the same source file, we must eliminate labels that are the same in different routines. The C string routine names all begin with str and those with an explicit parameter giving the buffer length have names that begin strn. As a result, the unique prefix for strncat could be no shorter than strnc, but this is also the prefix on the name strncpy. Fortunately, our preliminary versions of these routines are very short.

If the code were more complex, we might have needed to use a more elaborate naming system for local labels in these routines. Keeping all of the string routines in the same source file could force us to use longer identifiers for local labels. The alternative is to abbreviate the STR prefix used on local labels. For example, we might prefix all local labels in STRNCAT with SCAT or even SCT, the local labels in STRNCPY with SCPY or SCP, and the local labels in STRLEN with SLEN or SLN.

The STRLEN code given above made no use of its activation record and the STRNCPY code used it for just one thing, the return address. In writing STRNCAT, we need a more fully developed activation record for two reasons. First, since STRNCAT calls other subroutines, it needs to save its own return address somewhere, and second, it needs to save the values of its parameters through the call to STRLEN so it can pass them (or values derived from them) to STRNCPY.

Note that our calling conventions allow us to assume that registers R8 — R15 are not changed by a call, so we could use those registers to hold variables we need after the call to STRLEN. The problem is, if we use any of these registers, we must first save their values because whoever calls STRNCAT is also allowed to assume that R8 — R15 will not change. In this case, cost of saving these registers exceeds the benefit of using them. This leads to the following code:

Hawk code for STRNCAT

; activation record format for STRNCAT string concatenation routine RETAD = 0 ; the return address DST = 4 ; destination string address SRC = 8 ; source string address LEN = 12 ; length of destination buffer (unsigned) ARSIZE = 16 ; receiving sequence assumptions STRNCAT:; expects R3 -- dst, the destination string ; R4 -- src, the source string ; R5 -- len, the destination buffer length ; uses R4-7 ; returns R3 -- dst, unchanged STORES R1,R2 ; -- save return address STORE R3,R2,DST STORE R4,R2,SRC STORE R5,R2,LEN ; -- parameters are saved ; -- parameter s = dst (already in R3) ADDI R2,R2,ARSIZE JSR R1,STRLEN ADDI R2,R2,-ARSIZE ; dstlen = strlen( dst ) -- in R3 LOAD R4,R2,DST ADD R3,R3,R4 ; -- parameter dst = dst+dstlen LOAD R4,R2,SRC ; -- parameter src LOAD R5,R2,LEN ; -- parameter len = len-dstlen (in R5) ADDI R2,R2,ARSIZE JSR R1,STRNCPY ADDI R2,R2,-ARSIZE ; strncpy( dst+dstlen,src,len ) LOAD R3,R2,DST LOADS R1,R2 JUMPS R1 ; return dst

 
The above code can be optimized significantly, and a little optimization has already been done: We did not allocate space in the activation record for the result returned by STRLEN, instead we kept it in register 3 until it was needed.

Another optimization we could make is to avoid wasted space in activation record. Everything in the activation record is needed after the call to STRLEN from STRNCAT, but only some of it is still relevant during the call to STRNCPY. This lets us shorten the activation record during the second call. The way to do this is simple: Merely assign a new shorter value to ARSIZE at the point when some fields become irrelevant. Of course, the fields of the activation record must be arranged so that the fields that become irrelevant later in the code are at the end. This optimization is of little value here, but the memory savings from such optimization in a recursive subroutine can be important.

We could eliminate unneeded changes to the stack pointer between the two internal calls. This change is a bit tricky because the second call is inside an if statement while the first call is outside it. This optimization is only possible if the activation record size is fixed, so we must decide between efficient use of space on the stack and optimizing for speed by eliminating changes to the stack pointer.

All of the above discussion was based on ignorance of the real use made of the stack by STRLEN and STRNCPY. If those routines had been written by other programmers and were likely to be changed, it would be fair to keep the code we have above, but if those routines were completely debugged and part of the same library as this code, we could take advantage of our knowledge that STRLEN does not use the stack at all, and that STRNCAT makes only the slightest use of the stack.

Exercises

n) Improve STRNCAT by minimizing wasted space on the stack during the call to STRNCPY.

o) Improve STRNCAT by minimizing the incrementing and decrementing of the stack pointer, assuming that both called routines might need their activation records.

p) Improve STRNCAT by taking advantage of all the information you have about the called routines, so that there is no unneeded stack manipulation.
 

A Big Optimization, Working With Words

As pointed out in the context of both the STRLEN and STRCPY routines, working with one character at a time does nothing to take advantage of the fact that the computer we are using is able to work with 32-bit data. If we were dealing with an 8-bit microprocessor, the algorithms we used would be appropriate, but on a 32-bit machine, we should move data in 32-bit increments if possible.

In the mid 1960's, Control Data Corporation introduced the 6600 architecture. This packed ten 6-bit characters into each 60-bit word, with much less support for byte-addressing than the Hawk. This forced programmers to learn how to do efficient text manipulation in terms of words. By the mid 1980's, the developers of Digital Equipment Corporation's 64-bit Alpha processor had developed byte manipulation instructions like those of the Hawk, and they finished developing efficient string operations using words. The MMX extensions to the Intel Pentium architecture are based on many of the same ideas.

Long after these techniques were developed, the term SIMD within a register (abbreviated SWAR) was coined. A SIMD or single instruction multiple data stream computer is one where there are machine instructions that operate on entire arrays in parallel. Similar techniques for manipulating arrays of pixels packed into machine words have become quite common on graphics coprocessors.

What we want to do here is deal with individual characters only at the beginning and end of each string, and operate on full words in between. Since we are packing 4 characters per word, we will deal with only 0 to 3 individual characters at the start and 0 to 3 individual characters at the end. In doing this, we face two distinct problems: How do we check an address to see if it is a word address, something we must do at the start of the string, and how do we check a word to see if it includes the end-of-string character at the end?

A C or Java programmer wanting to check the variable n to see if it is divisible by 4 can write if(n%4==0), but taking the remainder after division is expensive. We can take advantage of the binary number system by rewriting this as if(n&3==0), and because the Hawk architecture includes an AND instruction do compute the logical and of two registers, we can convert the above directly to Hawk instructions.

The Hawk offers some special instructions that improve on this general solution. First, it has a special instruction for inspecting and testing the least significant bits of a word. The truncate instruction, TRUNC dst,n zeros out all but the least significant n bits of a register. This can be used to snip the 2 least significant bits from an address and set the Z condition code if they are zero. To help solve the second problem, detecting ene of string, the LOADCC and LOADSCC instructions set the C condition code if any byte of the loaded word is zero.

The Hawk also provides a special instruction to select between different cases, for example, the 0 to 3 bytes that must be handled separately at the start and end of each string. The BTRUNC instruction truncates its operand just like the TRUNC instruction, but instead of saving the result, it adds it to the program counter, so that the next instruction will be selected from among the instructions immediately after the BTRUNC. Usually, the next few instructions are branch instructions.

The tricks used in the fast STRLEN routine given below cannot be easily expressed in languages like C, although the comments in the code try to do this. Assembly language programmers are still employed to write carefully crafted and very fast code like this, not only for key routines such in the string library, but also for pixel-oriented graphics libraries. Game developers and search-engine developers make extensive use of such custom crafted code in order to achieve the fastest possible performance.

Efficient Hawk code for STRLEN

; receiving sequence assumptions for STRLEN (SLN) STRLEN: ; expects R3 -- src, the address of the string ; uses R4 -- ch, the character *src ; R5 -- start, the starting address of src ; returns R3 -- len, length of the string src MOVE R5,R3 ; start = src LOADSCC R4,R3 ; ch = *src -- the whole word BTRUNC R3,2 ; select (src & 3) { BR SLNB0 ; -- branch table 0 (byte number) BR SLNB1 ; -- 1 BR SLNB2 ; -- 2 BR SLNB3 ; -- 3 SLNB1: ; case 1 EXTB R0,R4,R3 ; -- finish ch = *src BZS SLNQT ; if (ch == NUL) break ADDSI R3,1 ; src = src + 1 SLNB2: ; case 2 EXTB R0,R4,R3 ; -- finish ch = *src BZS SLNQT ; if (ch == NUL) break ADDSI R3,1 ; src = src + 1 SLNB3: ; case 3 EXTB R0,R4,R3 ; -- finish ch = *src BZS SLNQT ; if (ch == NUL) break ADDSI R3,1 ; src = src + 1 LOADSCC R4,R3 ; ch = *src -- the whole word SLNB0: ; case 0 -- src divisible by 4 ; -- note ch=*src, LOADSCC set C bit BCS SLNLX ; if no byte in this word is zero { SLNLP: ; do { ADDSI R3,4 ; src = src + 4 LOADSCC R4,R3 ; ch = *src -- the whole word BCR SLNLP ; while no byte in this word is zero SLNLX: ; } -- some byte in R4 is zero EXTB R0,R4,R3 ; -- finish ch = *src BZS SLNQT ; if (ch == NUL) break ADDSI R3,1 ; src = src + 1 EXTB R0,R4,R3 ; -- finish ch = *src BZS SLNQT ; if (ch == NUL) break ADDSI R3,1 ; src = src + 1 EXTB R0,R4,R3 ; -- finish ch = *src BZS SLNQT ; if (ch == NUL) break ADDSI R3,1 ; src = src + 1 SLNQT: ; } -- assert *src == NUL SUB R3,R5,R3 ; len = start - src JUMPS R1 ; return len

Note that the inner loop above tests 4 bytes for each iteration, using only 3 instructions. Thus, for long strings, this STRLEN subroutine will use fewer instructions than there are bytes in the string being tested. The cost is 3 instructions per byte at the start and end of the string, while the optimized version of the byte-oriented code required a uniform 4 instructions per byte. Counting instructions is a very crude way to measure performance, particularly on modern pipelined processors. Ultimately, on any real CPU, physical testing against the clock is the final judge.

It is significantly harder to apply these optimizations to STRNCP because we must consider not only how the source string is broken into words but also how the destination buffer is broken up. If the least significant two bits of the source and destination addresses are equal, we can use the logic given for STRLEN. If the only the second to the least significant bits differ, we can copy a halfword at a time, but if the least significant bits differ, the byte alignment of the two string operands is different and we may be reduced to copying a byte at a time.

In C or Java, if you want to find out which bits of a and b are equal, you can use a^b to exclusive-or them. In the result, any bits that were equal in the originals will be zero. For the Hawk, the EQU instruction gives the logical inverse of the exclusive-or, so each result bit will be set if the corresponding bits of the operands were equal.

Exercises

q) Write a version of STRNCPY that uses the original code given earlier if the source and destination pointers are aligned differently, and uses logic based on the above version of STRLEN if the source and destination pointers are aligned identically.

r) Write a version of STRNCPY that uses halfword stuffing and halfword extraction, so that it can copy strings when the source and destination addresses are off by 2 from each other. How many instructions per byte copied does it average for long strings.