Assignment #4

Due October 2.

  1. Write a SPIM program to calculate and print out the 16-bit checksum of a null-terminated string. Assume that register $a0 holds the address of a null-terminated string. The 16-bit checksum is defined (as it is for TCP) as the one's complement of the sum of the 16-bit words in the string (discarding any carrys beyond 16 bits). The one's complement of a number is obtained by reversing bit values, so that 0 becomes 1 and 1 becomes 0--e.g., the one's complement of 11010101 is 00101010. You will need to calculate the 16-bit one's complement, which means reversing the bit values for each 16 bits. Note that if the 16 bits are contained in a 32 bit register you would not want to calculate the one's complement of the entire register.

    If the length of the string is odd, the final character is treated as the high byte of a 16 bit word. This means that for a null-terminated string, you can combine the final character with the null which terminates the string in order to obtain a 16-bit value. Print out the checksum obtained.

    In the real world, the checksum must be calculated and transmitted in network byte order--which is Big-Endian. So those of you using Little-Endian machines should make sure that you read the string a byte at a time, using the lb instruction instead of the lh instruction. The value obtained in a register for the half-word representing the string "Th" must be 5468, not 6854.

    For "This is a string", the sum of the 16-bit words (discarding carrys) is 06c8, and the one's complement is f937.

    For "This is an odd string" the sum discarding carrys is 9cf8, the one's complement of this is 6307, and the printed decimal checksum is 25351.


  3. Write a SPIM program that uses a recursive algorithm to calculate the greatest common divisor of two numbers -- as in the following C/Java method: 
    public int gcd(int x, int y) {

       if (x % y == 0)
               return y;
        else
               return gcd(y, x % y);
               
}
    Your program should prompt the user for the input of x and y, call the gcd function passing x and y as parameters, and finally print out the number that the function returns. The trick here is to figure out the correct register management for a recursive function. Figure 2.15 on p. 85, is helpful. Also see Appendix A, 25-33.

  5. EXTRA CREDIT: In many applications it is important to efficiently determine the first or last bit set in a given word. Intel 80x86 processors, for instance, have the instructions bsf (bit scan forward) and bsr (bit scan reverse) which return, respectively, either the first or last set bit in a 32 bit word. For instance if the word were 0x00fffff0 bsf would return the number 23 and bsr would return the number 4. PPC processors, on the other hand, only allow scanning in a single direction. The PPC instruction ctlzw returns the number of leading zeros in a word (one can obtain the first bit set by subtracting this from 31). The MIPS processor is like the PPC processor in that the instructions clz and clo only provide the number of leading zeros (or ones) in a word.

    Using SPIM, write an efficient routine for determining the number of trailing zeros in a word. It is possible, of course, to simply shift right until a one occurs in the least significant digit. But this is extremely inefficient. How can you determine the number of trailing zeros in a word without doing any looping?


Submit both electronic and printed copies of 1. and 2/3.