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