0

So I have an assignment where I have to translate some code in C to MIPS. It is what we are calling "Rule 1," which solves Sudoku puzzles by eliminating a number from a column, row, or 3x3 box if it is present elsewhere in that same row, column, or box. The top part of the code is given and everything under the dashed line is what we enter. We are running it on Linux Gnome on Xspim.

I feel like everything is correct and all my TA's could not find the error, but I keep getting an Exception 4 about some unaligned address. This program is due tomorrow at the latest so any help is appreciated! Thanks!

.data
newline:.asciiz "\n"		# useful for printing commands
star:	.asciiz "*"
# BOARD 1 IS THE COMPLETED BOARD
board1: .word 128 8 256 16 32 64 4 2 1 64 32 4 1 128 2 8 16 256 1 2 16 4 8 256 32 64 128 32 16 1 64 256 4 2 128 8 4 256 2 128 16 8 64 1 32 8 128 64 32 2 1 16 256 4 2 1 128 8 4 16 256 32 64 16 4 32 256 64 128 1 8 2 256 64 8 2 1 32 128 4 16
# BOARD 2 JUST HAS ONE ROW MISSING
board2: .word 511 511 511 511 511 511 511 511 511 64 32 4 1 128 2 8 16 256 1 2 16 4 8 256 32 64 128 32 16 1 64 256 4 2 128 8 4 256 2 128 16 8 64 1 32 8 128 64 32 2 1 16 256 4 2 1 128 8 4 16 256 32 64 16 4 32 256 64 128 1 8 2 256 64 8 2 1 32 128 4 16
# BOARD 3 JUST HAS ONE COLUMN MISSING
board3: .word 511 8 256 16 32 64 4 2 1 511 32 4 1 128 2 8 16 256 511 2 16 4 8 256 32 64 128 511 16 1 64 256 4 2 128 8 511 256 2 128 16 8 64 1 32 511 128 64 32 2 1 16 256 4 511 1 128 8 4 16 256 32 64 511 4 32 256 64 128 1 8 2 511 64 8 2 1 32 128 4 16
board4: # BOARD 4 HAS 3 SQUARES THAT HAVE 1 NUMBER MISSING TO TEST THE SQUARE PART.
.word 128 8 256 511 511 511 511 511 511 
.word 64 32 4 511 511 511 511 511 511 
.word 511 2 16 511 511 511 511 511 511
.word 511 511 511 64 511 256 511 511 511 
.word 511 511 511 128 32 4 511 511 511 
.word 511 511 511 8 16 2 511 511 511 
.word 511 511 511 511 511 511 128 32 16 
.word 511 511 511 511 511 511 64 8 511 
.word 511 511 511 511 511 511 1 2 256
# board 5 is the actual test for this MP
board5: .word 128 511 511 16 511 511 4 2 511 64 511 4 1 511 511 8 511 511 1 2 511 511 511 256 511 511 128 32 16 511 511 256 4 511 128 511 511 256 511 511 511 511 511 1 511 511 128 511 32 2 511 511 256 4 2 511 511 8 511 511 511 32 64 511 511 32 511 511 128 1 511 2 511 64 8 511 511 32 511 511 16
	
.text
# main function
main:
	sub  	$sp, $sp, 4
	sw   	$ra, 0($sp) # save $ra on stack

	# should print the same board a bunch of times (after you write rule1)
	la	$a0, board1
	jal	print_board
	jal	print_newline

	# uncomment these to test your code in piecemeal fashion.
	la	$a0, board2  	# tests if columns work
	jal	solve_board
	la	$a0, board2
	jal	print_board
	jal	print_newline

 	la	$a0, board3	# tests if rows work
 	jal	solve_board
 	la	$a0, board3
 	jal	print_board
 	jal	print_newline
 
 	la	$a0, board4	# tests if squares work
 	jal	solve_board
 	la	$a0, board4
 	jal	print_board
 	jal	print_newline
	
 	la	$a0, board5	# tests the whole shebang
 	jal	solve_board
 	la	$a0, board5
 	jal	print_board
 	jal	print_newline
	
	lw   	$ra, 0($sp) 	# restore $ra from stack
	add  	$sp, $sp, 4
	jr	$ra


#################### PRINT_NEWLINE #################### 	
solve_board:
	sub  	$sp, $sp, 8
	sw   	$ra, 0($sp)	# save $ra on stack
	sw   	$s0, 4($sp) 	# save $s0 on stack	<--- check out use of $s register!!
	move	$s0, $a0
main_loop:
	move	$a0, $s0
	jal	rule1
	bne	$v0, 0, main_loop	# keep running rule1 until no more changes
	
	lw   	$ra, 0($sp) 	# restore $ra
	lw   	$s0, 4($sp) 	# restore $s0 
	add  	$sp, $sp, 8
	jr	$ra


#################### PRINT_NEWLINE #################### 	
print_newline:
	lb   	$a0, newline($0)        	# read the newline char
	li   	$v0, 11        	# load the syscall option for printing chars
	syscall              	# print the char
	
	jr      $ra          	# return to the calling procedure


#################### PRINT_INT_AND_SPACE #################### 	
print_int_and_space:
	li   	$v0, 1         	# load the syscall option for printing ints
	syscall              	# print the element

	li   	$a0, 32        	# print a black space (ASCII 32)
	li   	$v0, 11        	# load the syscall option for printing chars
	syscall              	# print the char
	
	jr      $ra          	# return to the calling procedure

	
#################### SINGLETON #################### 	
singleton:
	li	$v0, 0
	beq	$a0, 0, singleton_done		# return 0 if value == 0
	sub	$a1, $a0, 1
	and	$a1, $a0, $a1
	bne	$a1, 0, singleton_done		# return 0 if (value & (value - 1)) == 0
	li	$v0, 1
singleton_done:
	jr	$ra


#################### GET_SINGLETON #################### 	
get_singleton:
	li	$v0, 0			# i
	li	$t1, 1
gs_loop:sll	$t2, $t1, $v0		# (1<<i)
	beq	$t2, $a0, get_singleton_done
	add	$v0, $v0, 1
	blt	$v0, 9, gs_loop		# repeat if (i < 9)
get_singleton_done:
	jr	$ra


#################### PRINT BOARD #################### 	
print_board:
	sub	$sp, $sp, 20
	sw	$ra, 0($sp)		# save $ra and free up 4 $s registers for
	sw	$s0, 4($sp)		# i
	sw	$s1, 8($sp)		# j
	sw	$s2, 12($sp)		# the function argument
	sw	$s3, 16($sp)		# the computed pointer (which is used for 2 calls)
	move	$s2, $a0

	li	$s0, 0			# i
pb_loop1:
	li	$s1, 0			# j
pb_loop2:
	mul	$t0, $s0, 9		# i*9
	add	$t0, $t0, $s1		# (i*9)+j
	sll	$t0, $t0, 2		# ((i*9)+j)*4
	add	$s3, $s2, $t0
	lw	$a0, 0($s3)
	jal	singleton		
	beq	$v0, 0, pb_star		# if it was not a singleton, jump
	lw	$a0, 0($s3)
	jal	get_singleton		
	add	$a0, $v0, 1		# print the value + 1
	li	$v0, 1
	syscall
	j	pb_cont

pb_star:		
	li	$v0, 4			# print a "*"
	la	$a0, star
	syscall

pb_cont:	
	add	$s1, $s1, 1		# j++
	blt	$s1, 9, pb_loop2

	li	$v0, 4			# at the end of a line, print a newline char.
	la	$a0, newline
	syscall	
	
	add	$s0, $s0, 1		# i++
	blt	$s0, 9, pb_loop1

	lw	$ra, 0($sp)		# restore registers and return
	lw	$s0, 4($sp)
	lw	$s1, 8($sp)
	lw	$s2, 12($sp)
	lw	$s3, 16($sp)
	add	$sp, $sp, 20
	jr	$ra

	
## int get_square_begin(int index) {
##   return (index/GRIDSIZE) * GRIDSIZE;
## }

get_square_begin:
	div	$v0, $a0, 3
	mul	$v0, $v0, 3
	jr	$ra
	
# ALL your code goes below this line.
#
# We will delete EVERYTHING above the line; DO NOT delete 
# the line.
#
# ---------------------------------------------------------------------

## bool
## rule1(int board[9][9]) {
##   bool changed = false;
##   for (int i = 0 ; i < GRID_SQUARED ; ++ i) {
## 	 for (int j = 0 ; j < GRID_SQUARED ; ++ j) {
## 		int value = board[i][j];
## 		if (singleton(value)) {
## 		  for (int k = 0 ; k < GRID_SQUARED ; ++ k) {
## 			 // eliminate from row
## 			 if (k != j) {
## 				if (board[i][k] & value) {
## 				  changed = true;
## 				}
## 				board[i][k] &= ~value;
## 			 }
## 			 // eliminate from column
## 			 if (k != i) {
## 				if (board[k][j] & value) {
## 				  changed = true;
## 				}
## 				board[k][j] &= ~value;
## 			 }
## 		  } // end for
## 
## 		  // eliminate from square
## 		  int ii = get_square_begin(i);
## 		  int jj = get_square_begin(j);
## 		  for (int k = ii ; k < ii + GRIDSIZE ; ++ k) {
## 		  	 for (int l = jj ; l < jj + GRIDSIZE ; ++ l) {
## 		  		if ((k == i) && (l == j)) {
## 		  		  continue;
## 		  		}
## 				if (board[k][l] & value) {
## 				  changed = true;
## 				}
## 		  		board[k][l] &= ~value;
## 		  	 }
## 		  } // end for
## 		} // end if
## 	 } //end for
##   } // end for
##   return changed;
## }

rule1:
	sub	$sp, $sp, 8
	li	$a2, 0
	sw	$ra, 0($sp)
	li	$s1, 0			#s1 is i
	move	$s7, $a0

ilikeloop: # does a cute double loop :) 
	li	$s2, 0			#s2 is j
jlikeloop:
	move	$a0, $s1
	move	$a1, $s2
	jal	computeposition
	add	$t0, $s7, $v1	 	#t0 is address of board [i][j]	
	lw	$s5, 0($t0)		#int value ($s5) = board[i][j];
	move 	$a0, $s5		
	jal 	singleton
	bne	$v0, 1, incrementer
	li	$s3, 0			#s3 is k upper
rowloop:	
	beq	$s3, $s2, column
	move	$a0, $s1
	move	$a1, $s3
	jal	computeposition
	add	$t1, $s7, $v1		#t1 is address of board [i][k]
	lw	$t2, 0($t1)		#t2 is now value of board [i][k]
	not	$t3, $s5		#~board[i][j]
	and	$t2, $t2, $t3		#board[i][k]=board[i][k]&~board[i][j] 
	sw	$t2, 0($t1)		#store back into memory address
	and	$t1, $s5, $t2		#t1 is now board[i][j]&board[i][k]
	beq	$t1, $0, column
	li	$a2, 1			#changed=true 
	
column:	
	beq	$s3, $s1, kinkymentor
	move	$a0, $s3
	move	$a1, $s2
	jal	computeposition
	add	$t1, $s7, $v1		#t1 is address of board [k][j]
	lw	$t2, 0($t1)		#t2 is now value of board [k][j]
	not	$t3, $s5		#~board[i][j]
	and	$t2, $t2, $t3		#board[k][j]=board[k][j]&~board[i][j] 
	sw	$t2, 0($t1)		#store back into memory address
	and	$t1, $s5, $t2		#t1 is now board[i][j]&board[k][j]
	beq	$t1, $0, kinkymentor
	li	$a2, 1			#changed=true 

kinkymentor:
	addi	$s3, $s3, 1
	blt	$s3, 9, rowloop

######
squarery:
	move	$a0, $s1
	jal	get_square_begin
	move	$s4, $v0		#$s4 is ii
	move	$a0, $s2
	jal	get_square_begin
	move	$s6, $v0		#$s6 is jj
	move	$s0, $s4		#s0 is k

squashyloopk:
	move	$s3, $s6		#s3 is l
	
squashyloopl:
	bne	$s0, $s1, pass
	bne	$s3, $s2, pass
	j	squashyincrement
###############################
pass:
	move	$a0, $s0
	move	$a1, $s3
	jal	computeposition
	add	$t1, $s7, $v1		#t1 is address of board [k][l]
	lw	$t2, 0($t1)		#t2 is now value of board [k][l]
	and	$t6, $t2, $s5		# board[k][l]& value
	beq	$t6, 0, fail 
	li	$a2, 1			#changed=true 
fail:
	not	$t3, $s5		#~board[i][j]
	and	$t2, $t2, $t3		#board[k][l]=board[k][l]&~board[i][j] 
	sw	$t2, 0($t1)
##############################

squashyincrement:
	addi	$s3, $s3, 1		#increment l
	addi	$t0, $s6, 3
	blt	$s3, $t0, squashyloopl	#branch back to beginning of l loop
	addi	$s0, $s0, 1		#increment k
	addi	$t1, $s4, 3
	blt	$s0, $t1, squashyloopk
#####

incrementer:	
	addi	$s2, $s2, 1		#increment j
	blt	$s2, 9, jlikeloop	#branch back to beginning of j loop
	addi	$s1, $s1, 1
	blt	$s1, 9, ilikeloop
	lw	$ra, 0($sp)	
	addi	$sp, $sp, 8
	move	$v0, $a2
	jr	$ra

computeposition: # takes in [a0][a1] and returns the value
	mul	$t0, $a0, 9
	add	$t0, $t0, $a1
	sll	$v1, $t0, 2	
	jr	$ra
1
Contributor
1
Reply
2
Views
8 Years
Discussion Span
Last Post by ryansullivan
0

Problem solved. Turns out we should have saved all our stuff to the stack, not S values. They were getting overwritten in the given code. Anyway, thanks to anyone who took a look at this.

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.