Homework #5 Solution

Objectives:

Practice assembly language,
Working with looping,
Writing simple functions, and
Get a better understanding of the stack and how it's used,

Assignment:

Write a strlen (see here and here) method:

a0
will contain the address of a null-terminated "string" of characters (declared with .asciiz). A "null terminator" means that the end of the strength is identified by a byte with the value 0.
v0
will contain the return value.
The method should "count" the number of characters until it reaches the null terminator (i.e. the length of the string) and return it.
Be sure you follow the register usage conventions.

Write a small piece of code to test your strlen method.


.data 
  testStrlen: .asciiz "This is a test"
.text
                la $a0, testStrlen   # Setup the test 
                jal strlen           # Call it
                move $a0,$v0         # Move the int to $a0 for printing
                li $v0,1             # print an int
                syscall

                li $v0,10            # End the program
                syscall
strlen:
# Note this is like: while(a[i]!=0) i++; return i;
        move $t0,$a0      # copy the starting address to another register
strlenLoop:
        lb $t1,($t0)      # Load the byte at the current address
        add $t0,$t0,1     # Advance the address by 1
        bnez $t1,strlenLoop  # If the byte wasn't zero, loop (grab the next one)
        sub $v0,$t0,$a0  # Compute the difference between the start and stop
        sub $v0,$v0,1    # We added an extra 1 onto the counter - subtract it
        jr $ra           # Return to the caller

Write a int findFirst(char[] phrase, char[] word), complete the method to find the first occurrence of the elements in the "word" array within the "phrase" array. (Note: You wrote a Java version for Hw #1. Hw #1 also provided examples of input and output. You may want to review/revise your version from Hw #1 or review the posted solution before beginning. Also note that a char[] (or a char*) is the same as a label to an .asciiz).

Write a small piece of code to test your findFirst method.

.text
 main:
 
   la $a0,one   # Prepare to run findFirst (setup arguments)
   la $a1,two
   jal findFirst  # Call findFirst
   move $a0,$v0  # More return value to $a0
   li $v0,1
   syscall         # Print return value
   li $v0,10      # End program
   syscall
 
 .data 
 one: .asciiz "This History Channel Thing Hisses"
 two: .asciiz "His"
 
.text 
 findFirst:   ################# findFirst(char* phrase, char* word) #####################
   move $t0,$a0              # $t0 will be used to step through phrase

findFirstOuterLoop:      
   lb $t2,0($t0)                # $t2 is the character at the current location in phrase
   beqz $t2,findFirstFail  # If we've hit the end, fail

   move $t1,$a1            # $t1 will be used to step through word
   move $t4,$t0              # $t4 is the location of the current character in phrase
findFirstInnerLoop:
      lb $t3,0($t1)             # Get the current character of word               
      beqz $t3,findFirstEndInner # if we've hit the end of $t1, then we have found a match
      lb $t5,0($t4)             # Get the current character of phrase
      bne $t3,$t5,findFirstNext  # No match. Move on to next letter in phrase
      add $t1,$t1,1            # Move on to next characters
      add $t4,$t4,1
      j findFirstInnerLoop

findFirstNext:
   add $t0,$t0,1                   # Move on to next character
   j findFirstOuterLoop

   add $t0,$t0,1
   j findFirstOuterLoop

findFirstEndInner:
  sub $v0,$t0,$a0   # Store the distance travelled in $v0
  j findFirstEnd         
                           
findFirstFail:   
   li $v0,-1
findFirstEnd:      
   jr $ra

The following C/C++ program has a number of variables and initial values. Identify which memory segment each underlined part of the program would be in on a MIPS machine. Think very carefully about every part of the program! Draw a diagram of the computer memory and where each component might be located. If the underlined part is a label, indicate which segment of memory it refers to. Assume that C/C++ is already using all registers so all variables need to be stored in memory.

int size;

void function(void)
{
    int iarray[]={1,2,3,4,5,-6};
    int idx;
    for(idx=0;idx<size;idx++)
       cout << iarray[idx] << " ";    
}

void main(void)
{
    char carray[] = "Hello World";
    size=6;
    cout << carray;
    function();
}

Hints:

cout is an object used for output. You can think of it like System.out in Java.
The line cout << iarray[idx] << " " is equivalent to System.out.printlnt(iarray[idx] + " ").
size is a global variable. It's a lot like a static field in a class because they have a lifetime of the entire run of the program.

If you want to check your work, look at the assembly language that the compiler converted this program into: hw5asm.txt

int size;
Size is a global variable so it will be put in the static data segment.
void function(void)
Function refers to a set of instructions, so it's a label/pointer into the text segment
{
    int iarray[]={1,2,3,4,5,-6};
iarray is a local variable, so it will be put in the stack segment.
{1,2,3,4,5,-6} is a static array, so it will be placed in the static data segment
    int idx;
idx is also a local variable, so it will also be put in the stack segment
    for(idx=0;idx<size;idx++)
       cout << iarray[idx] << " ";    
" " is a static array, so it will be placed in the static data segment.
}

void main(void)
main refers to a set of instructions, so it's a label/pointer into the text segment.
{
    char carray[] = "Hello World";
carray is a local variable, so it will be put into the stack segment
"Hello World" is a constant array, so it will be put into the static data segment
    size=6;
    cout << carray;
cout is a global variable, so it will be in the static data segment
(I'll also accept it as being a set of instructions/label into the text segment, 
 but in the generated assemble provided, it truely is a global variable in the static data segment)
    function();
}