.data
board: .space 324 # 9x9 sudoku board. 9*9*4 bytes

.text
main:
    li      $t0, 0x4001 # flag for sudoku interrupt set, and global interrupt enable
    mtc0    $t0, $12    # Enable interrupt mask (Status register)

    li $s0, 0           # 0 = no board
                        # 1 = waiting for board
                        # 2 = unsolved board
loop:
    beq $s0, $zero, get_board
    li $t0, 1
    beq $s0, $t0, loop

solve_board:
    move  $s1, $ra
    la    $a0, board
    jal solve             # solve sudoku board
    move  $ra, $s1
    la $t0, board
    sw $t0, 0xffff00ec($zero)    # get credit for solution

    li $s0, 0                    # mark as no board now we are done with it
    j loop

get_board:
    la $t0, board
    sw $t0, 0xffff00e8($zero)    # ask for sudoku board

    li $s0, 1                    # mark as waiting for board
    j loop

    jr $ra


################
# SOLVING LOOP #
################
solve:
    sub     $sp, $sp, 12
    sw      $ra, 0($sp) # save $ra on stack
    sw      $s0, 4($sp)     # save $s0 on stack <--- check out use of $s register!!
    sw      $s1, 8($sp) # save $s1 on stack
    move    $s0, $a0
solve_loop:
    move    $a0, $s0
    jal rule1
    move $s1, $v0       # save changed

    move    $a0, $s0
    jal rule2
    #or  $v0, $s1, $v0   # changed = rule1() or rule2()
    move $v0, $s1

    bne $v0, 0, solve_loop   # keep running rule1 until no more changes

    lw      $ra, 0($sp)     # restore $ra
    lw      $s0, 4($sp)     # restore $s0
    lw      $s1, 8($sp)     # restore $s1
    add     $sp, $sp, 12
    jr $ra

.data
atsave: .word 0
a0save: .word 0
a1save: .word 0

non_intrpt_str:   .asciiz "Non-interrupt exception\n"
unhandled_str:    .asciiz "Unhandled interrupt type\n"

.ktext 0x80000080
interrupt_handler:
    .set noat
    sw  $at, atsave
    .set at
    sw  $a0, a0save     # Get some free registers
    sw  $a1, a1save     # by storing them to a global variable

    mfc0    $k0, $13        # Get Cause register
    srl     $a0, $k0, 2
    and     $a0, $a0, 0xf       # ExcCode field
    bne     $a0, 0, non_intrpt

interrupt_dispatch:         # Interrupt:
    mfc0    $k0, $13        # Get Cause register, again
    beq $k0, $zero, done    # handled all outstanding interrupts

    and     $a0, $k0, 0x4000    # is there a bonk interrupt?
    bne     $a0, 0, sudoku_interrupt

                    # add dispatch for other interrupt types here.

    #li $v0, 4          # Unhandled interrupt types
    #la $a0, unhandled_str
    #syscall
    j done

sudoku_interrupt:
    li  $s0, 2                  # mark a sudoku puzzle
    sw  $k0, 0xffff0068($zero)  # acknowledge interrupt
    j   interrupt_dispatch      # see if other interrupts are waiting

non_intrpt:             # was some non-interrupt
    #li $v0, 4
    #la $a0, non_intrpt_str
    #syscall                # print out an error message
    j done

done:
    lw  $a0, a0save
    lw  $a1, a1save
    mfc0    $k0 $14         # EPC

    .set noat
    lw  $at, atsave
    .set at

    rfe             # Return from exception handler
    jr  $k0


########################
#  SUDOKU RULE SOLVERS #
########################
.text
###
# Rule 1
###
board_address:
    mul $v0, $a1, 9     # i*9
    add $v0, $v0, $a2       # (i*9)+j
    sll $v0, $v0, 2     # ((i*9)+j)*4
    add $v0, $a0, $v0
    jr  $ra

rule1:
    sub $sp, $sp, 32
    sw  $ra, 0($sp)     # save $ra and free up 7 $s registers for
    sw  $s0, 4($sp)     # i
    sw  $s1, 8($sp)     # j
    sw  $s2, 12($sp)        # board
    sw  $s3, 16($sp)        # value
    sw  $s4, 20($sp)        # k
    sw  $s5, 24($sp)        # changed
    sw  $s6, 28($sp)        # temp
    move    $s2, $a0
    li  $s5, 0          # changed = false

    li  $s0, 0          # i = 0
r1_loop1:
    li  $s1, 0          # j = 0
r1_loop2:
    move    $a0, $s2        # board
    move    $a1, $s0        # i
    move    $a2, $s1        # j
    jal board_address
    lw  $s3, 0($v0)     # value = board[i][j]
    move    $a0, $s3
    jal is_singleton
    beq $v0, 0, r1_loop2_bot    # if not a singleton, we can go onto the next iteration

    li  $s4, 0          # k = 0
r1_loop3:
    beq $s4, $s1, r1_skip_row   # skip if (k == j)
    move    $a0, $s2        # board
    move    $a1, $s0        # i
    move    $a2, $s4        # k
    jal board_address
    lw  $t0, 0($v0)     # board[i][k]
    and $t1, $t0, $s3
    beq $t1, 0, r1_skip_row
    not $t1, $s3
    and $t1, $t0, $t1
    sw  $t1, 0($v0)     # board[i][k] = board[i][k] & ~value
    li  $s5, 1          # changed = true

r1_skip_row:
    beq $s4, $s0, r1_skip_col   # skip if (k == i)
    move    $a0, $s2        # board
    move    $a1, $s4        # k
    move    $a2, $s1        # j
    jal board_address
    lw  $t0, 0($v0)     # board[k][j]
    and $t1, $t0, $s3
    beq $t1, 0, r1_skip_col
    not $t1, $s3
    and $t1, $t0, $t1
    sw  $t1, 0($v0)     # board[k][j] = board[k][j] & ~value
    li  $s5, 1          # changed = true

r1_skip_col:
    add $s4, $s4, 1     # k++
    blt $s4, 9, r1_loop3

## doubly nested loop
    move    $a0, $s0        # i
    jal get_square_begin
    move    $s6, $v0        # ii
    move    $a0, $s1        # j
    jal get_square_begin    # jj
    move    $t0, $s6        # k = ii
    add     $s6, $v0, 3     # jj + GRIDSIZE
    add $t1, $t0, 3     # ii + GRIDSIZE

r1_loop4_outer:
    sub $t2, $s6, 3     # l = jj

r1_loop4_inner:
    bne $t0, $s0, r1_loop4_1
    beq $t2, $s1, r1_loop4_bot

r1_loop4_1:
    mul $v0, $t0, 9     # k*9
    add $v0, $v0, $t2       # (k*9)+l
    sll $v0, $v0, 2     # ((k*9)+l)*4
    add $v0, $s2, $v0       # &board[k][l]
    lw  $v1, 0($v0)     # board[k][l]
    and $t3, $v1, $s3       # board[k][l] & value
    beq $t3, 0, r1_loop4_bot

    not $t3, $s3
    and $v1, $v1, $t3
    sw  $v1, 0($v0)     # board[k][l] = board[k][l] & ~value
    li  $s5, 1          # changed = true

r1_loop4_bot:
    add $t2, $t2, 1     # l++
    blt $t2, $s6, r1_loop4_inner

    add $t0, $t0, 1     # k++
    blt $t0, $t1, r1_loop4_outer


r1_loop2_bot:
    add $s1, $s1, 1     # j++
    blt $s1, 9, r1_loop2

    add $s0, $s0, 1     # i++
    blt $s0, 9, r1_loop1

    move    $v0, $s5        # return changed
    lw  $ra, 0($sp)     # restore registers and return
    lw  $s0, 4($sp)
    lw  $s1, 8($sp)
    lw  $s2, 12($sp)
    lw  $s3, 16($sp)
    lw  $s4, 20($sp)
    lw  $s5, 24($sp)
    lw  $s6, 28($sp)
    add $sp, $sp, 32
    jr  $ra


###
# Rule 2
###

rule2:
    sub $sp,$sp,36
    sw  $ra,0($sp)
    sw  $s0,4($sp)
    sw  $s1,8($sp)
    sw  $s2,12($sp)
    sw  $s3,16($sp)
    sw  $s4,20($sp)
    sw  $s5,24($sp)
    sw  $s6,28($sp)
    sw  $s7,32($sp)

    li  $s7, 0  #s7 = returning boolean
    move    $s6, $a0 #$s6 = board[0][0]
    li  $s1,0   #i=0

i_loop:
    beq $s1,9,return_rule#i==9

    li  $s2,0       #j=0

j_loop:
    beq $s2,9,i_loop_increment  #j==9
    j   ignore_i_inc

i_loop_increment:       #increments i
    add $s1,$s1,1   #i++
    j   i_loop

ignore_i_inc:

    move    $a0,$s1
    move    $a1,$s2


    jal board_val

    move    $s3,$v0     #value at [i][j]
    move    $a0,$s3

    jal is_singleton

    bne $v0,$zero, j_loop_end  #THIS IS DIFFERENT FOR RULE2

    li  $t1,0       #isum = 0
    li  $t2,0       #jsum = 0

    li  $s4,0       #k=0

k_loop:
    beq $s4,9,k_loop_end #k==9

check_row:
    beq $s4,$s2,check_column #if(k!=j)

    move    $a0,$s1
    move    $a1,$s4

    jal board_val   #value at board[i][k]

    or  $t2,$t2,$v0 #j_sum |= board[i][k]

check_column:
    beq $s4,$s1,k_inc    #if(k!=i)

    move    $a0,$s4
    move    $a1,$s2

    jal board_val   #value at board[k][j]

k_inc:
    add $s4,$s4,1   #k++
    j   k_loop

k_loop_end:

    beq $t2,1023,skip_j_sum;    #if ALLVALUES == j_sum
    li  $s7,1           #changed = true

    move    $a0,$s1
    move    $a1,$s2

    jal board_loc

    not $t2,$t2         #j_sum = ~jsum
    and $t2,$t2,1023        #ALL_VALUES & ~j_sum
    lw  $t2,0($v0)      #board[i][j]
    j   j_loop_end

skip_j_sum:
    beq $t1,1023,skip_i_sum #if ALLVALUES == i_sum (same as above :P)
    li  $s7,1

    move    $a0,$s1
    move    $a1,$s2

    jal board_loc

    not $t1,$t1
    and $t1,$t1,1023
    lw  $t1,0($v0)
    j   j_loop_end

skip_i_sum:

#dont need t1/t2 anymore, can be reused
    li  $t0,0       #sq_sum = 0
    move    $a0,$s1

    jal get_square_begin

    move    $t1,$v0     #ii

    move    $a0,$s2

    jal get_square_begin

    move    $t2,$v0     #jj
    move    $t3,$t2     #extra copy of jj

    add $t4,$t1,3    #ii+3
    add $t5,$t2,3    #jj+3

ii_loop:
    beq $t1,$t4,after_square #k == ii+3
    move    $t2,$t3         #set l = jj

jj_loop:
    beq $t2,$t5,ii_inc  #l = jj+3
    j   ignore_ii_inc

ii_inc:
    add $t1,$t1,1       #k++
    j   ii_loop

ignore_ii_inc:
    bne $s1,$t1,skip_wierd_part     #k!=i
    bne $s2,$t2,skip_wierd_part     #l!=j

    j   jj_loop_end

skip_wierd_part:

    move    $a0,$t1
    move    $a1,$t2

    jal board_value

    or  $t0,$t0,$v0 #sum |= board[k][j]

jj_loop_end:
    add $t2,$t2,1       #l++
    j   jj_loop

after_square:

    beq $t0,1023,j_loop_end #ALLVALUES !=sq_sum
    li  $s7,1           #changed = true

    move    $a0,$s1
    move    $a1,$s2

    jal board_loc

    not $t0,$t0         #sq_sum = ~sq_sum
    and $t0,$t0,1023        #ALL_VALUES & ~sq_sum
    lw  $t0,0($v0)      #board[i][j]


j_loop_end:
    add $s2,$s2,1   #j++
    j   j_loop

return_rule:

    move    $v0,$s7 #set return value
    lw  $ra,0($sp)
    lw  $s0, 4($sp)
    lw  $s1, 8($sp)
    lw  $s2, 12($sp)
    lw  $s3, 16($sp)
    lw  $s4, 20($sp)
    lw  $s5, 24($sp)
    lw  $s6, 28($sp)
    lw  $s7, 32($sp)
    add $sp, $sp, 36
    jr  $ra





board_loc:
    sub $sp,$sp,4
    sw  $ra,0($sp)

    mul $a3,$a0,9
    add $v0,$a3,$a1
    mul $v0,$v0,4
    add $v0,$v0,$s6 #board[i][j] = (i*9 + j)*4 + starting add.


    lw  $ra,0($sp)
    add $sp,$sp,4
    jr  $ra


board_val:      #returns value of of cell[a0][a1]
            #$a0 = i, $a1 = j

    sub $sp,$sp,4
    sw  $ra,0($sp)

    mul $a3,$a0,9
    add $v0,$a3,$a1
    mul $v0,$v0,4
    add $a3,$v0,$s6
    lw  $v0,0($a3)  #board[i][j] loc.


    lw  $ra,0($sp)
    add $sp,$sp,4
    jr  $ra


#################### SINGLETON ####################
is_singleton:
    li  $v0, 0
    beq $a0, 0, is_singleton_done       # return 0 if value == 0
    sub $a1, $a0, 1
    and $a1, $a0, $a1
    bne $a1, 0, is_singleton_done       # return 0 if (value & (value - 1)) == 0
    li  $v0, 1
is_singleton_done:
    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