CSE 378 Homework 2

Out: Monday 4/6/09
Due: Monday 4/13/09

Purpose

Become more comfortable with assembler programming, as a way of understanding what is going on under the covers when you write code in more reasonable languages.

There are two small programs, followed by a slightly longer one. The slightly longer one should be easily managable once you've done the first two.

This assignment is coming out before we will have talked about how procedure call is implemented. It is intended that you not use any procedures. Further, Cebollita uses a procedure call linkage that is different from the one described in the book, meaning you really should avoid using procedures - nothing here requires them.

Implied by this is that you should use only heap allocated variables (plus registers, of course) - that is, no stack allocated variables. You won't need stack allocated variables to implement anything. (Heap allocated variables appear in the .data section, as shown in the next section of this assignmnet.)

If what this all means isn't clear at this point, it will be in a moment. Just follow the directions for how your assembler code should start and end, and how it can print or read input. Understanding everything about "why" for those things will come late this week or early next week.

Preliminaries

You code should start something like this. This example shows the three types of heap allocated variables that Cebollita supports. You can create as many, or as few, of each as you need.

.data
myInitializedVar:   .word     10    # allocates 32-bits and initialzes to decimal 10
myUninitializedVar: .space    12    # allocates 12 bytes of memory, word aligned
myString:           .asciiz   "Test string\n" 

.text
      .global main
main:
# Your code comes here.
# Formatting is usually aligned in columns, like this:
#         ori   $4, $5, 2
#mylab:   beq   $4, $5, skip
#         addi  $4, $4, 1
#skip:
# (Note: that code doesn't do anything sensible)

# DO NOT USE REGISTERS 28-31 IN YOUR CODE.  All other registers are okay.

# To load a heap allocated variable into memory, you have to add
# it's label (as an immediate) to the value of register 28 (also known
# as $gp) to form the address.  (Cebollita doesn't support addui, so
# we have to use addi.)  For example:

       addi  $8, $28, myInitializedVar
       lw    $9, 0($8)                   # $9 now has the value of myInitializedVar (i.e., 10)

# To terminate execution, execute this instruction
       jr    $31    # $31 is also known as $ra

To run your code:

• cebasm myFile.s
• ceblink .../cebollita/apps/prologues/prologue-noos.o myFile.o
• cebsim a.exe
• You can toggle breakpoints by right-clicking on a line of code in the top pane of the GUI that appears.
• You can step through the program (execute n lines of code and then pausing execution, with 1 being the default) or you can simply run it.

Without subroutines, we can't perform IO. That means you can't output anything. Correctness will be assessed by the contents of registers just before your code terminates.

Your goal is to write fast code - code that completes after executing the fewest instructions possible. Normally, this corresponds to code that is short - the .s file contains very few instructions. (The former is called the dynamic program length (instructions executed) and the latter the static program length (number of lines of code).)

You are implementing in Cebollita, so you can use only those instructions it supports: Cebollita Instruction Set

Part 1: floor(log(N))

Find floor(log(N)), where N is a positive integer and the log is taken base 2. Leave the value in $10.

Your code file should start like this:

.data
N:     .word  2000000

Hint: This is the highest order position of any 1 bit in the 2's-complement representation of the integer. You can compute it by shifting the word right one bit repeatedly, until the value you end up with is zero. The result is one fewer than the number of shifts you make.

Example:

22 = 0x00000016 = 00....010110 (as a 32 bit integer)
After 5 right shifts, the value is 0, so floor(log(22)) is 4.

Part 2: max(array)

Put the maximum of an array of 32-bit signed integers in $10. You are given two heap variables: the array, and a word containing the array length. The beginning of your .s file should look something like this:

.data
length:    .word 5   # the number of words in the array
# This syntax doesn't seem to work in Cebollita.
# In fact, there's no way to statically initialize an array in Cebollita.
# The revised version (below) initializes the array in code.
array:     .word 2   # 'array' starts here, and...
           .word 7   # continues here and...
           .word -2  # here and....
           .word 10  # here and...
           .word 10  # ends here (because length == 5)

array:     .space 20

.text
	.global main
main:
# Create a pointer to array in $8, then use it as a 
# base register to initialize the 5 array elements.

	addi	$8, $gp, array  # create pointer to array

	ori	$9, $0, 2    
	sw	$9, 0($8)       # array[0] = 2

	ori	$9, $0, 7
	sw	$9, 4($8)	# array[1] = 7

	addi	$9, $0, -2	# (addi required to sign extended result)
	sw	$9, 8($8)	# array[2] = -2

	ori	$9, $0, 10
	sw	$9, 12($8)	# array[3] = 10

	sw	$9, 16($8)	# array[4] = 10

Part 3: Palindrome Checker

A palindrome is a sentence that reads the same forwards and backwards, ignoring punctuation and blanks. For example:

A man, a plan, a canal, Panama!

Your code should include this heap allocated variable:

.data
testString: .asciiz "A man, a plan, a canal, Panama!"

Note that testString is "zero terminated" - there is a byte with value 0 at the end of the string (and not before).

Leave the value 1 in $10 if testString is a palindrome, and 0 otherwise.

Table 2.15 (page 122) in the text gives a table of ASCII character codes, but it's in decimal only. This Wikipedia page has the codes in decimal and hex (and octal -- base 8). Hex is useful here because it points out that if you OR the value 0x20 with any of the 26 upper case letters you end up with the corresponding lower case letter, and that if you OR 0x20 with a lower case letter you end up with that same lower case letter. Both tables point out that the 26 letters have consecutive ASCII values.