CSE 378 Homework 3A Sample Solution

There has been a lot of discussion about whether isPalindrome has local variables that need stack space allocated, or not. This solution uses an approach in which there is one, the result (0 or 1). I'm going to end up needing to save it across the calls to printString in any case, so rather than allocating stack space at call time (i.e., rather that treating saving it as part of "caller saves registers") I treat it as a local variable and allocate space for it on entry. You may have done it some other way. Many other ways are okay, as how local variables are handled is something that only the routine being compiled depends on (i.e., not the caller, and not anything this routine might call).

#
# This code is written to be a translation of part3.c into assembler.
# You should look at part3.c simultaneously with reading  this.
#
# Register usage:
#   $5: scratch
#   $6: char from head of string
#   $7: char from tail of string
#   $8: headPtr
#   $9: tailPtr
#  $10: result: 0 -> not a palindrome ; 1-> is a palindrome

.data
success:	.asciiz	" is a palindrome.\n"
failure:	.asciiz	" is not a palindrome.\n"

.text
	.global isPalindrome
isPalindrome:
	addi	$sp, $sp, -12	# space for $ra / $fp / local var
	sw	$ra, 0($sp)
	sw	$fp, 4($sp)
	or	$fp, $0, $sp
	
	# initialize headPtr
	lw	$8, 12($fp)
	addi	$8, $8, -1

	# tailPtr for loop
	lw	$9, 12($fp)	# ptr to start of testString
tailLoop:
	lb	$6, 0($9)
	beq	$6, $0, forDone		# found '\0'?
	addi	$9, $9, 1		# increment by 1 byte = 1 char
	j	tailLoop
forDone:	

	# while(1)
mainLoop:

	addi	$8, $8, 1		# headPtr++
headWhileLoop:
	# fetch *headPtr
	lb	$6, 0($8)
	# note: we're lucky that no ascii alphabetic has the high bit
	#       on, because we have no lbu instruction in cebollita.
	#       (We'd probably have to use an and mask to zero the high order
	#       24 bits of $6 otherwise.)

	# force to lower case, for convenience
	ori	$6, $6, 0x20
	# isalpha(*headPtr)?
	slti	$5,$6, 0x61            	# byte has lower value than 'a'?
	bne	$5, $0, headNotAlpha	# yes
	slti	$5, $6, 0x7B	      	# byte has lower value than 'z'+1?
	bne	$5, $0, headWhileDone 	# yes - done with this loop
headNotAlpha:	
	slt	$5, $8, $9		# headPtr < tailPtr?
	beq	$5, $0, mainWhileDone	# yep - break from main loop
	addi	$8, $8, 1		# headPtr++
	j	headWhileLoop
headWhileDone:	


	addi	$9, $9, -1		# tailPtr--
tailWhileLoop:
	# fetch *tailPtr
	lb	$7, 0($9)
	ori	$7, $7, 0x20
	# isalpha(*tailPtr)?
	slti	$5,$7, 0x61            	# byte has lower value than 'a'?
	bne	$5, $0, tailNotAlpha	# yes
	slti	$5, $7, 0x7B	      	# byte has lower value than 'z'+1?
	bne	$5, $0, tailWhileDone 	# yes - done with this loop
tailNotAlpha:	
	slt	$5, $8, $9		# tailPtr < tailPtr?
	beq	$5, $0, mainWhileDone	# yep - break from main loop
	addi	$9, $9, -1		# tailPtr--
	j	tailWhileLoop
tailWhileDone:

	# tolower(*headPtr) != tolower(*tailPtr)
	bne	$6, $7, mainWhileDone

	j	mainLoop

mainWhileDone:

	# headPtr < tailPtr => not a palindrome
	# otherwise it is
	
	slt	$10, $8, $9
	xori	$10, $10, 1	# invert the lower order bit
	sw	$10, 8($fp)	# store in local var

	# print the argument string
	lw	$7, 12($fp)	# fetch argument (ptr to the input string)
	addi	$sp, $sp, -4	# space for argument to printString
	sw	$7, 0($sp)
	jal	printString

	# print the is / isn't a palindrome string
	lw	$10, 8($fp)	# fetch local (palindrome result)
	beq	$10, $0, failed
	addi	$7, $gp, success # arg to printString is an address
	j	doPrint
failed:	addi	$7, $gp, failure
doPrint: sw	$7, 0($sp)
	jal	printString
	addi	$sp, $sp, 4

	# return to caller
	lw	$v0, 8($fp)	# return value (is it a palindrome?)
	lw	$ra, 0($fp)
	lw	$fp, 4($fp)
	addi	$sp, $sp, 12

	jr	$ra