PacMan.mips

# addr const init
lui $k0, 0xC000     # disp
lui $k1, 0xE000     # seg
# TOGGLE
# lui $fp, 0xD000     # kbd
lui $fp, 0xB000     # btn
la $gp, data
addi $sp, $zero, 0x4000    # stack seg at 16384

# other const init
addi $t8, $zero, 0x1  # const 1, used in beq to compare with flag
lui $t9, 0x1    # higher 1

main:
    addi $a3, $zero, 1
    jal hard_reset
    lui $t4, 0x000F
    read_in_loop:
        lw $a0, 0($fp)
        addi $t4, $t4, -1
        bne $t4, $zero, read_in_loop

        jal state

        add $t0, $s5, $zero
        add $t1, $zero, $zero
        digit0_loop:
            slti $at, $t0, 100
            beq $at, $t8, digit1_loop
            addi $t0, $t0, -100
            addi $t1, $t1, 0x0100
            j digit0_loop

        digit1_loop:
            slti $at, $t0, 10
            beq $at, $t8, digit2
            addi $t0, $t0, -10
            addi $t1, $t1, 0x010
            j digit1_loop

        digit2:
            add $t1, $t1, $t0

        sll $at, $a2, 16
        add $t1, $t1, $at
        sw $t1, 0($k1)

        lui $t4, 0x000F
        j read_in_loop

dead:
    j dead

# function: overall state control flow
# state stored in a3
state:
    addi $sp, $sp, -16
    sw $ra, 0($sp)
    sw $t4, 4($sp)
    sw $t0, 8($sp)
    sw $t1, 12($sp)

    beq $a3, $zero, state_frame
    addi $at, $zero, 1
    beq $a3, $at, state_start
    addi $at, $zero, 2
    beq $a3, $at, state_win
    addi $at, $zero, 3
    beq $a3, $at, state_died
    addi $at, $zero, 4
    beq $a3, $at, state_lose
    addi $at, $zero, 5
    beq $a3, $at, state_pause

    state_frame:
        # TOGGLE
        andi $t0, $a0, 0xF
        addi $at, $zero, 6
        bne $t0, $at, state_frame_not_pause   # pause
        addi $a3, $zero, 5         # pause
        j state_pause

        state_frame_not_pause:
        jal frame

        addi $at, $zero, 1
        bne $v0, $at, state_frame_not_died
        addi $a3, $zero, 3         # died
        j state_died

        state_frame_not_died:
        addi $at, $zero, 2
        bne $v0, $at, state_frame_not_lose
        addi $a3, $zero, 4         # lose
        j state_lose

        state_frame_not_lose:
        addi $at, $zero, 0x0120
        andi $t0, $s5, 0x7FFF
        bne $t0, $at, state_frame_not_win
        addi $a3, $zero, 2         # win
        j state_win

        state_frame_not_win:
        j state_end

    state_start:
        # TOGGLE
        andi $t0, $a0, 0xF
        addi $at, $zero, 0x9
        bne $t0, $at, state_start_not_frame
        add $a3, $zero, $zero   # frame
        addi $a0, $zero, 0x110b
        jal reset_block
        addi $a0, $zero, 0x110c
        jal reset_block
        addi $a0, $zero, 0x110d
        jal reset_block
        addi $a0, $zero, 0x110e
        jal reset_block
        addi $a0, $zero, 0x110f
        jal reset_block
        addi $a0, $zero, 0x1110
        jal reset_block
        addi $a3, $zero, 0         # frame
        j state_frame
        state_start_not_frame:
        addi $a0, $zero, 0x110b
        addi $a1, $zero, 0x90
        jal display_block
        addi $a0, $zero, 0x110c
        addi $a1, $zero, 0x91
        jal display_block
        addi $a0, $zero, 0x110d
        addi $a1, $zero, 0x92
        jal display_block
        addi $a0, $zero, 0x110e
        addi $a1, $zero, 0x93
        jal display_block
        addi $a0, $zero, 0x110f
        addi $a1, $zero, 0x94
        jal display_block
        addi $a0, $zero, 0x1110
        addi $a1, $zero, 0x95
        jal display_block
        j state_end

    state_win:
    # TOGGLE
    andi $t0, $a0, 0xF
    addi $at, $zero, 0xE
    bne $t0, $at, state_win_not_start
    jal hard_reset
    addi $a3, $zero, 1         # start
    j state_start
    state_win_not_start:
        addi $a0, $zero, 0x110a
        addi $a1, $zero, 0xb0
        jal display_block
        addi $a0, $zero, 0x110b
        addi $a1, $zero, 0xb1
        jal display_block
        addi $a0, $zero, 0x110c
        addi $a1, $zero, 0xb2
        jal display_block
        addi $a0, $zero, 0x110d
        addi $a1, $zero, 0xb3
        jal display_block
        addi $a0, $zero, 0x110e
        addi $a1, $zero, 0xb4
        jal display_block
        addi $a0, $zero, 0x110f
        addi $a1, $zero, 0xb5
        jal display_block
        addi $a0, $zero, 0x1110
        addi $a1, $zero, 0xb6
        jal display_block
        addi $a0, $zero, 0x1111
        addi $a1, $zero, 0xb7
        jal display_block
        andi $a0, $s0, 0x7FFF
        addi $a1, $zero, 0x30
        jal display_block
    j state_end

    state_died:
    # TOGGLE
    andi $t0, $a0, 0xF
    addi $at, $zero, 0xE
    bne $t0, $at, state_died_not_start
    jal reset
    addi $a3, $zero, 1         # start
    j state_start
    state_died_not_start:
        addi $a0, $zero, 0x1109
        addi $a1, $zero, 0x9c
        jal display_block
        addi $a0, $zero, 0x110a
        addi $a1, $zero, 0x9d
        jal display_block
        addi $a0, $zero, 0x110b
        addi $a1, $zero, 0x9e
        jal display_block
        addi $a0, $zero, 0x110c
        addi $a1, $zero, 0x9f
        jal display_block
        addi $a0, $zero, 0x110d
        addi $a1, $zero, 0xa0
        jal display_block
        addi $a0, $zero, 0x110e
        addi $a1, $zero, 0xa1
        jal display_block
        addi $a0, $zero, 0x110f
        addi $a1, $zero, 0xa2
        jal display_block
        addi $a0, $zero, 0x1110
        addi $a1, $zero, 0xa3
        jal display_block
        addi $a0, $zero, 0x1111
        addi $a1, $zero, 0xa4
        jal display_block
        addi $a0, $zero, 0x1112
        addi $a1, $zero, 0xa5
        jal display_block
        andi $a0, $s0, 0x7FFF
        addi $a1, $zero, 0x39
        jal display_block
    j state_end

    state_lose:
    # TOGGLE
    andi $t0, $a0, 0xF
    addi $at, $zero, 0xE
    bne $t0, $at, state_lose_not_start
    jal hard_reset
    addi $a3, $zero, 1         # start
    j state_start
    state_lose_not_start:
        addi $a0, $zero, 0x1109
        addi $a1, $zero, 0xa6
        jal display_block
        addi $a0, $zero, 0x110a
        addi $a1, $zero, 0xa7
        jal display_block
        addi $a0, $zero, 0x110b
        addi $a1, $zero, 0xa8
        jal display_block
        addi $a0, $zero, 0x110c
        addi $a1, $zero, 0xa9
        jal display_block
        addi $a0, $zero, 0x110d
        addi $a1, $zero, 0xaa
        jal display_block
        addi $a0, $zero, 0x110e
        addi $a1, $zero, 0xab
        jal display_block
        addi $a0, $zero, 0x110f
        addi $a1, $zero, 0xac
        jal display_block
        addi $a0, $zero, 0x1110
        addi $a1, $zero, 0xad
        jal display_block
        addi $a0, $zero, 0x1111
        addi $a1, $zero, 0xae
        jal display_block
        addi $a0, $zero, 0x1112
        addi $a1, $zero, 0xaf
        jal display_block
        andi $a0, $s0, 0x7FFF
        addi $a1, $zero, 0x39
        jal display_block

    j state_end

    state_pause:
        # TOGGLE
        andi $t0, $a0, 0xF
        addi $at, $zero, 9
        bne $t0, $at, state_pause_not_frame
        addi $a0, $zero, 0x110b
        jal reset_block
        addi $a0, $zero, 0x110c
        jal reset_block
        addi $a0, $zero, 0x110d
        jal reset_block
        addi $a0, $zero, 0x110e
        jal reset_block
        addi $a0, $zero, 0x110f
        jal reset_block
        addi $a0, $zero, 0x1110
        jal reset_block
        addi $a3, $zero, 0         # frame
        j state_frame

        state_pause_not_frame:
        addi $a0, $zero, 0x110b
        addi $a1, $zero, 0x96
        jal display_block
        addi $a0, $zero, 0x110c
        addi $a1, $zero, 0x97
        jal display_block
        addi $a0, $zero, 0x110d
        addi $a1, $zero, 0x98
        jal display_block
        addi $a0, $zero, 0x110e
        addi $a1, $zero, 0x99
        jal display_block
        addi $a0, $zero, 0x110f
        addi $a1, $zero, 0x9A
        jal display_block
        addi $a0, $zero, 0x1110
        addi $a1, $zero, 0x9B
        jal display_block
        j state_end

    state_end:
        lw $ra, 0($sp)
        lw $t4, 4($sp)
        lw $t0, 8($sp)
        lw $t1, 12($sp)
        addi $sp, $sp, 16
        jr $ra

# function: reset the life and beans
hard_reset:
    addi $sp, $sp, -16
    sw $ra, 0($sp)
    sw $a0, 4($sp)
    sw $a1, 8($sp)
    sw $t0, 12($sp)

    addi $a0, $gp, 0xE2C
    addi $a1, $gp, 0x11AC
    addi $t0, $zero, 224
    hard_reset_bean_loop:
        lw $at, 0($a1)
        sw $at, 0($a0)
        addi $a1, $a1, 4
        addi $a0, $a0, 4
        addi $t0, $t0, -1
        bne $t0, $zero, hard_reset_bean_loop

    jal reset
    addi $a2, $zero, 3
    addi $s5, $zero, 1

    lw $ra, 0($sp)
    lw $a0, 4($sp)
    lw $a1, 8($sp)
    lw $t0, 12($sp)
    addi $sp, $sp, 16
    jr $ra


# function: reset the pos and dir of spirits, display the maze
# don't reset the bean
reset:
    addi $sp, $sp, -12
    sw $ra, 0($sp)
    sw $a0, 4($sp)
    sw $a1, 8($sp)

    # game const init
    # pacman position and direction
    jal maze_init
    lui $s0, 0x1   # direction 0 1 2 3 -> u r d l
    addi $s0, $s0, 0x170e   # position y:x
    lui $s1, 0x1
    addi $s1, $s1, 0x0e0c
    lui $s2, 0x0
    addi $s2, $s2, 0x0e0d
    lui $s3, 0x0
    addi $s3, $s3, 0x0e0e
    lui $s4, 0x3
    addi $s4, $s4, 0x0e0f

    addi $a0, $zero, 0x170e
    addi $a1, $zero, 0x30
    jal display_block

    addi $a0, $zero, 0x0e0c
    addi $a1, $zero, 0x44
    jal display_block

    addi $a0, $zero, 0x0e0d
    addi $a1, $zero, 0x50
    jal display_block

    addi $a0, $zero, 0x0e0e
    addi $a1, $zero, 0x60
    jal display_block

    addi $a0, $zero, 0x0e0f
    addi $a1, $zero, 0x72
    jal display_block
    
    lw $ra, 0($sp)
    lw $a0, 4($sp)
    lw $a1, 8($sp)
    addi $sp, $sp, 12
    jr $ra

# function: displat next frame according to current state, input and maze
frame:
    addi $sp, $sp, -24
    sw $ra, 0($sp)
    sw $t0, 4($sp)
    sw $t1, 8($sp)
    sw $t2, 12($sp)
    sw $t3, 16($sp)
    sw $s6, 20($sp)

    add $s6, $a0, $zero
    add $s7, $s1, $zero  # inky uses blinky's position

    # spirit reset
    # blinky
    andi $a0, $s1, 0x7FFF
    jal reset_block
    # pinky
    andi $a0, $s2, 0x7FFF
    jal reset_block
    # inky
    andi $a0, $s3, 0x7FFF
    jal reset_block
    # clyde
    andi $a0, $s4, 0x7FFF
    jal reset_block

    # pacman
    add $a0, $s6, $zero
    add $s6, $s0, $zero
    # TOGGLE
    # 
    lui $at, 0x3
    addi $at, $at, 0x0E00
    beq $s0, $at, frame_penetrate_left
    lui $at, 0x1
    addi $at, $at, 0x0E1B
    beq $s0, $at, frame_penetrate_right
    andi $a0, $a0, 0xF
    addi $at, $zero, 0x0
    beq $a0, $at, frame_pacman_not_change
    addi $at, $zero, 0x5
    beq $a0, $at, frame_kbd_up
    addi $at, $zero, 0x8
    beq $a0, $at, frame_kbd_left
    addi $at, $zero, 0xA
    beq $a0, $at, frame_kbd_right
    addi $at, $zero, 0xD
    beq $a0, $at, frame_kbd_down
    j frame_pacman_not_change

    frame_kbd_up:
        andi $a0, $s0, 0x7FFF
        addi $a0, $a0, -0x0100   # y -= 1
        jal is_blocked
        bne $v0, $zero, frame_pacman_not_change
        addi $a0, $a0, 0x0100
        jal reset_block
        addi $a0, $a0, -0x0100
        addi $a1, $zero, 0x31
        jal eat_bean
        jal display_block
        andi $at, $s0, 0x7FFF
        lui $s0, 0x0
        add $s0, $s0, $at
        addi $s0, $s0, -0x100
        j frame_end

    frame_kbd_right:
        andi $a0, $s0, 0x7FFF
        addi $a0, $a0, 1   # x += 1
        jal is_blocked
        bne $v0, $zero, frame_pacman_not_change
        addi $a0, $a0, -1
        jal reset_block
        addi $a0, $a0, 1
        addi $a1, $zero, 0x35
        jal eat_bean
        jal display_block
        andi $at, $s0, 0x7FFF
        lui $s0, 0x1
        add $s0, $s0, $at
        addi $s0, $s0, 1
        j frame_end

    frame_kbd_down:
        andi $a0, $s0, 0x7FFF
        addi $a0, $a0, 0x0100   # y += 1
        jal is_blocked
        bne $v0, $zero, frame_pacman_not_change
        addi $a0, $a0, -0x0100
        jal reset_block
        addi $a0, $a0, 0x0100
        addi $a1, $zero, 0x37
        jal eat_bean
        jal display_block
        andi $at, $s0, 0x7FFF
        lui $s0, 0x2
        add $s0, $s0, $at
        addi $s0, $s0, 0x100
        j frame_end


    frame_kbd_left:
        andi $a0, $s0, 0x7FFF
        addi $a0, $a0, -1   # x -= 1
        jal is_blocked
        bne $v0, $zero, frame_pacman_not_change
        addi $a0, $a0, 1
        jal reset_block
        addi $a0, $a0, -1
        addi $a1, $zero, 0x33
        jal eat_bean
        jal display_block
        andi $at, $s0, 0x7FFF
        lui $s0, 0x3
        add $s0, $s0, $at
        addi $s0, $s0, -1
        j frame_end

    frame_pacman_not_change:
        srl $a0, $s0, 16
        addi $at, $zero, 0x0
        beq $a0, $at, frame_still_up
        addi $at, $zero, 0x1
        beq $a0, $at, frame_still_right
        addi $at, $zero, 0x2
        beq $a0, $at, frame_still_down
        addi $at, $zero, 0x3
        beq $a0, $at, frame_still_left
        j frame_end

    frame_still_left:
        andi $a0, $s0, 0x7FFF
        addi $a0, $a0, -1   # x -= 1
        jal is_blocked
        bne $v0, $zero, frame_end
        addi $a0, $a0, 1
        jal reset_block
        addi $a0, $a0, -1
        addi $a1, $zero, 0x33
        jal eat_bean
        jal display_block
        andi $at, $s0, 0x7FFF
        lui $s0, 0x3
        add $s0, $s0, $at
        addi $s0, $s0, -1   # x -= 1
        j frame_end

    frame_still_up:
        andi $a0, $s0, 0x7FFF
        addi $a0, $a0, -0x0100   # y -= 1
        jal is_blocked
        bne $v0, $zero, frame_end
        addi $a0, $a0, 0x0100
        jal reset_block
        addi $a0, $a0, -0x0100
        addi $a1, $zero, 0x31
        jal eat_bean
        jal display_block
        andi $at, $s0, 0x7FFF
        lui $s0, 0x0
        add $s0, $s0, $at
        addi $s0, $s0, -0x100
        j frame_end

    frame_still_down:
        andi $a0, $s0, 0x7FFF
        addi $a0, $a0, 0x0100   # y += 1
        jal is_blocked
        bne $v0, $zero, frame_end
        addi $a0, $a0, -0x0100
        jal reset_block
        addi $a0, $a0, 0x0100
        addi $a1, $zero, 0x37
        jal eat_bean
        jal display_block
        andi $at, $s0, 0x7FFF
        lui $s0, 0x2
        add $s0, $s0, $at
        addi $s0, $s0, 0x100
        j frame_end

    frame_still_right:
        andi $a0, $s0, 0x7FFF
        addi $a0, $a0, 1   # x += 1
        jal is_blocked
        bne $v0, $zero, frame_end
        addi $a0, $a0, -1
        jal reset_block
        addi $a0, $a0, 1
        addi $a1, $zero, 0x35
        jal eat_bean
        jal display_block
        andi $at, $s0, 0x7FFF
        lui $s0, 0x1
        add $s0, $s0, $at
        addi $s0, $s0, 1   # x += 1
        j frame_end

    frame_penetrate_left:
        addi $a0, $zero, 0x0E00
        jal reset_block
        addi $a0, $a0, 0x1B
        addi $a1, $zero, 0x33
        jal display_block
        lui $s0, 0x3
        addi $s0, $s0, 0x0E1B
        j frame_end

    frame_penetrate_right:
        addi $a0, $zero, 0x0E00
        addi $a0, $a0, 0x1B
        jal reset_block
        addi $a0, $zero, 0x0E00
        addi $a1, $zero, 0x33
        jal display_block
        lui $s0, 0x1
        addi $s0, $s0, 0x0E00
        j frame_end

    frame_end:

    # spirit next
    # blinky
    # target: pacman
    add $a0, $s1, $zero
    andi $a1, $s6, 0x7FFF
    jal spirit_next_dir
    beq $v1, $zero, blinky_common_move

    # 2 penetrate position at the edge of the maze
    add $s1, $v0, $zero
    beq $v1, $t8, blinky_penetrate_1
    addi $a0, $zero, 0x0e00
    addi $a1, $zero, 0x44
    jal display_block
    j blinky_done
    
    blinky_penetrate_1:
    addi $a0, $zero, 0x0e1b
    addi $a1, $zero, 0x42
    jal display_block
    j blinky_done

    # common trace
    blinky_common_move:
    addi $at, $zero, 0x0
    beq $v0, $at, frame_blinky_up
    addi $at, $zero, 0x1
    beq $v0, $at, frame_blinky_right
    addi $at, $zero, 0x2
    beq $v0, $at, frame_blinky_down
    addi $at, $zero, 0x3
    beq $v0, $at, frame_blinky_left

    frame_blinky_up:
        andi $at, $s1, 0x7FFF
        lui $s1, 0x0
        add $s1, $s1, $at
        addi $s1, $s1, -0x100

        andi $a0, $s1, 0x7FFF
        addi $a1, $zero, 0x40
        jal display_block
        j blinky_done

    frame_blinky_right:
        andi $at, $s1, 0x7FFF
        lui $s1, 0x1
        add $s1, $s1, $at
        addi $s1, $s1, 1

        andi $a0, $s1, 0x7FFF
        addi $a1, $zero, 0x44
        jal display_block
        j blinky_done

    frame_blinky_down:
        andi $at, $s1, 0x7FFF
        lui $s1, 0x2
        add $s1, $s1, $at
        addi $s1, $s1, 0x100

        andi $a0, $s1, 0x7FFF
        addi $a1, $zero, 0x46
        jal display_block
        j blinky_done

    frame_blinky_left:
        andi $at, $s1, 0x7FFF
        lui $s1, 0x3
        add $s1, $s1, $at
        addi $s1, $s1, -1

        andi $a0, $s1, 0x7FFF
        addi $a1, $zero, 0x42
        jal display_block
    blinky_done:

    # pinky
    # target: 4 blocks ahead pacman
    add $a0, $s2, $zero
    andi $a1, $s6, 0x7FFF
    # get the direction and consider the delta
    srl $t0, $s6, 16
    addi $at, $zero, 0x0
    beq $t0, $at, pinky_target_up
    addi $at, $zero, 0x1
    beq $t0, $at, pinky_target_right
    addi $at, $zero, 0x2
    beq $t0, $at, pinky_target_down
    # target left
    andi $t0, $s6, 0xFF
    slti $at, $t0, 0x4
    beq $at, $zero, pinky_left_not_out
    sub $a1, $a1, $t0
    j pinky_target_end
    pinky_left_not_out:
    addi $a1, $a1, -0x4
    j pinky_target_end

    pinky_target_up:
    srl $t0, $s6, 8
    andi $t0, $t0, 0xFF
    slti $at, $t0, 0x4
    beq $at, $zero, pinky_up_not_out
    sll $t0, $t0, 8
    sub $a1, $a1, $t0
    j pinky_target_end
    pinky_up_not_out:
    addi $a1, $a1, -0x0400
    j pinky_target_end

    pinky_target_right:
    addi $a1, $a1, 0x4
    j pinky_target_end

    pinky_target_down:
    addi $a1, $a1, 0x0400

    pinky_target_end:
    jal spirit_next_dir
    beq $v1, $zero, pinky_common_move

    add $s2, $v0, $zero
    beq $v1, $t8, pinky_penetrate_1
    addi $a0, $zero, 0x0e00
    addi $a1, $zero, 0x54
    jal display_block
    j pinky_done
    
    pinky_penetrate_1:
    addi $a0, $zero, 0x0e1b
    addi $a1, $zero, 0x52
    jal display_block
    j pinky_done

    pinky_common_move:
    addi $at, $zero, 0x0
    beq $v0, $at, frame_pinky_up
    addi $at, $zero, 0x1
    beq $v0, $at, frame_pinky_right
    addi $at, $zero, 0x2
    beq $v0, $at, frame_pinky_down
    addi $at, $zero, 0x3
    beq $v0, $at, frame_pinky_left

    frame_pinky_up:
        andi $at, $s2, 0x7FFF
        lui $s2, 0x0
        add $s2, $s2, $at
        addi $s2, $s2, -0x100

        andi $a0, $s2, 0x7FFF
        addi $a1, $zero, 0x50
        jal display_block
        j pinky_done

    frame_pinky_right:
        andi $at, $s2, 0x7FFF
        lui $s2, 0x1
        add $s2, $s2, $at
        addi $s2, $s2, 1

        andi $a0, $s2, 0x7FFF
        addi $a1, $zero, 0x54
        jal display_block
        j pinky_done

    frame_pinky_down:
        andi $at, $s2, 0x7FFF
        lui $s2, 0x2
        add $s2, $s2, $at
        addi $s2, $s2, 0x100

        andi $a0, $s2, 0x7FFF
        addi $a1, $zero, 0x56
        jal display_block
        j pinky_done

    frame_pinky_left:
        andi $at, $s2, 0x7FFF
        lui $s2, 0x3
        add $s2, $s2, $at
        addi $s2, $s2, -1

        andi $a0, $s2, 0x7FFF
        addi $a1, $zero, 0x52
        jal display_block
    pinky_done:

    # inky
    # target: mirror position of blinky with '2 blocks ahead pacman' as the center
    andi $a1, $s6, 0x7FFF
    srl $t0, $s6, 16
    addi $at, $zero, 0x0
    beq $t0, $at, inky_target_up
    addi $at, $zero, 0x1
    beq $t0, $at, inky_target_right
    addi $at, $zero, 0x2
    beq $t0, $at, inky_target_down
    # target left
    andi $t0, $s6, 0xFF
    slti $at, $t0, 0x2
    beq $at, $zero, inky_left_not_out
    sub $a1, $a1, $t0
    j inky_target_end
    inky_left_not_out:
    addi $a1, $a1, -0x2
    j inky_target_end

    inky_target_up:
    srl $t0, $s6, 8
    andi $t0, $t0, 0xFF
    slti $at, $t0, 0x2
    beq $at, $zero, inky_up_not_out
    sll $t0, $t0, 8
    sub $a1, $a1, $t0
    j inky_target_end
    inky_up_not_out:
    addi $a1, $a1, -0x0200
    j inky_target_end

    inky_target_right:
    addi $a1, $a1, 0x2
    j inky_target_end

    inky_target_down:
    addi $a1, $a1, 0x0200

    inky_target_end:
    # a1 now 2 blocks ahead pacman, with >0 bound
    andi $a0, $s7, 0x7FFF
    jal lnky_target

    add $a0, $s3, $zero
    add $a1, $v0, $zero
    jal spirit_next_dir
    beq $v1, $zero, inky_common_move

    add $s3, $v0, $zero
    beq $v1, $t8, inky_penetrate_1
    addi $a0, $zero, 0x0e00
    addi $a1, $zero, 0x64
    jal display_block
    j inky_done
    
    inky_penetrate_1:
    addi $a0, $zero, 0x0e1b
    addi $a1, $zero, 0x62
    jal display_block
    j inky_done

    inky_common_move:
    addi $at, $zero, 0x0
    beq $v0, $at, frame_inky_up
    addi $at, $zero, 0x1
    beq $v0, $at, frame_inky_right
    addi $at, $zero, 0x2
    beq $v0, $at, frame_inky_down
    addi $at, $zero, 0x3
    beq $v0, $at, frame_inky_left

    frame_inky_up:
        andi $at, $s3, 0x7FFF
        lui $s3, 0x0
        add $s3, $s3, $at
        addi $s3, $s3, -0x100

        andi $a0, $s3, 0x7FFF
        addi $a1, $zero, 0x60
        jal display_block
        j inky_done

    frame_inky_right:
        andi $at, $s3, 0x7FFF
        lui $s3, 0x1
        add $s3, $s3, $at
        addi $s3, $s3, 1

        andi $a0, $s3, 0x7FFF
        addi $a1, $zero, 0x64
        jal display_block
        j inky_done

    frame_inky_down:
        andi $at, $s3, 0x7FFF
        lui $s3, 0x2
        add $s3, $s3, $at
        addi $s3, $s3, 0x100

        andi $a0, $s3, 0x7FFF
        addi $a1, $zero, 0x66
        jal display_block
        j inky_done

    frame_inky_left:
        andi $at, $s3, 0x7FFF
        lui $s3, 0x3
        add $s3, $s3, $at
        addi $s3, $s3, -1

        andi $a0, $s3, 0x7FFF
        addi $a1, $zero, 0x62
        jal display_block
    inky_done:

    # clyde
    add $a0, $s4, $zero
    andi $a1, $s6, 0x7FFF
    jal distance2_a0_a1

    slti $at, $v0, 64
    beq $at, $zero, clyde_chase
    addi $a1, $zero, 0x1f00
    clyde_chase:

    jal spirit_next_dir
    beq $v1, $zero, clyde_common_move

    add $s4, $v0, $zero
    beq $v1, $t8, clyde_penetrate_1
    addi $a0, $zero, 0x0e00
    addi $a1, $zero, 0x74
    jal display_block
    j clyde_done
    
    clyde_penetrate_1:
    addi $a0, $zero, 0x0e1b
    addi $a1, $zero, 0x72
    jal display_block
    j clyde_done

    clyde_common_move:
    addi $at, $zero, 0x0
    beq $v0, $at, frame_clyde_up
    addi $at, $zero, 0x1
    beq $v0, $at, frame_clyde_right
    addi $at, $zero, 0x2
    beq $v0, $at, frame_clyde_down
    addi $at, $zero, 0x3
    beq $v0, $at, frame_clyde_left

    frame_clyde_up:
        andi $at, $s4, 0x7FFF
        lui $s4, 0x0
        add $s4, $s4, $at
        addi $s4, $s4, -0x100

        andi $a0, $s4, 0x7FFF
        addi $a1, $zero, 0x70
        jal display_block
        j clyde_done

    frame_clyde_right:
        andi $at, $s4, 0x7FFF
        lui $s4, 0x1
        add $s4, $s4, $at
        addi $s4, $s4, 1

        andi $a0, $s4, 0x7FFF
        addi $a1, $zero, 0x74
        jal display_block
        j clyde_done

    frame_clyde_down:
        andi $at, $s4, 0x7FFF
        lui $s4, 0x2
        add $s4, $s4, $at
        addi $s4, $s4, 0x100

        andi $a0, $s4, 0x7FFF
        addi $a1, $zero, 0x76
        jal display_block
        j clyde_done

    frame_clyde_left:
        andi $at, $s4, 0x7FFF
        lui $s4, 0x3
        add $s4, $s4, $at
        addi $s4, $s4, -1

        andi $a0, $s4, 0x7FFF
        addi $a1, $zero, 0x72
        jal display_block
    clyde_done:


    # return dead info
    add $v0, $zero, $zero
    frame_check_b:
    srl $t2, $s0, 16    # dir pac
    srl $t3, $s1, 16    # dir b
    andi $t0, $s0, 0x7FFF
    andi $t1, $s1, 0x7FFF
    beq $t0, $t1, frame_died

    addi $t0, $t0, -0x0100
    bne $t0, $t1, frame_check_b_down
    addi $at, $zero, 2
    bne $t2, $at, frame_check_b_down
    addi $at, $zero, 0
    bne $t3, $at, frame_check_b_down
    j frame_died

    frame_check_b_down:
    andi $t0, $s0, 0x7FFF
    addi $t0, $t0, 0x0100
    bne $t0, $t1, frame_check_b_right
    addi $at, $zero, 0
    bne $t2, $at, frame_check_b_right
    addi $at, $zero, 2
    bne $t3, $at, frame_check_b_right
    j frame_died

    frame_check_b_right:
    andi $t0, $s0, 0x7FFF
    addi $t0, $t0, 1
    bne $t0, $t1, frame_check_b_left
    addi $at, $zero, 3
    bne $t2, $at, frame_check_b_left
    addi $at, $zero, 1
    bne $t3, $at, frame_check_b_left
    j frame_died

    frame_check_b_left:
    andi $t0, $s0, 0x7FFF
    addi $t0, $t0, -1
    bne $t0, $t1, frame_check_p
    addi $at, $zero, 3
    bne $t2, $at, frame_check_p
    addi $at, $zero, 1
    bne $t3, $at, frame_check_p
    j frame_died

    frame_check_p:
    srl $t3, $s2, 16    # dir p
    andi $t0, $s0, 0x7FFF
    andi $t1, $s2, 0x7FFF
    beq $t0, $t1, frame_died

    addi $t0, $t0, -0x0100
    bne $t0, $t1, frame_check_p_down
    addi $at, $zero, 2
    bne $t2, $at, frame_check_p_down
    addi $at, $zero, 0
    bne $t3, $at, frame_check_p_down
    j frame_died

    frame_check_p_down:
    andi $t0, $s0, 0x7FFF
    addi $t0, $t0, 0x0100
    bne $t0, $t1, frame_check_p_right
    addi $at, $zero, 0
    bne $t2, $at, frame_check_p_right
    addi $at, $zero, 2
    bne $t3, $at, frame_check_p_right
    j frame_died

    frame_check_p_right:
    andi $t0, $s0, 0x7FFF
    addi $t0, $t0, 1
    bne $t0, $t1, frame_check_p_left
    addi $at, $zero, 3
    bne $t2, $at, frame_check_p_left
    addi $at, $zero, 1
    bne $t3, $at, frame_check_p_left
    j frame_died

    frame_check_p_left:
    andi $t0, $s0, 0x7FFF
    addi $t0, $t0, -1
    bne $t0, $t1, frame_check_i
    addi $at, $zero, 3
    bne $t2, $at, frame_check_i
    addi $at, $zero, 1
    bne $t3, $at, frame_check_i
    j frame_died

    frame_check_i:
    srl $t3, $s3, 16    # dir i
    andi $t0, $s0, 0x7FFF
    andi $t1, $s3, 0x7FFF
    beq $t0, $t1, frame_died

    addi $t0, $t0, -0x0100
    bne $t0, $t1, frame_check_i_down
    addi $at, $zero, 2
    bne $t2, $at, frame_check_i_down
    addi $at, $zero, 0
    bne $t3, $at, frame_check_i_down
    j frame_died

    frame_check_i_down:
    andi $t0, $s0, 0x7FFF
    addi $t0, $t0, 0x0100
    bne $t0, $t1, frame_check_i_right
    addi $at, $zero, 0
    bne $t2, $at, frame_check_i_right
    addi $at, $zero, 2
    bne $t3, $at, frame_check_i_right
    j frame_died

    frame_check_i_right:
    andi $t0, $s0, 0x7FFF
    addi $t0, $t0, 1
    bne $t0, $t1, frame_check_i_left
    addi $at, $zero, 3
    bne $t2, $at, frame_check_i_left
    addi $at, $zero, 1
    bne $t3, $at, frame_check_i_left
    j frame_died

    frame_check_i_left:
    andi $t0, $s0, 0x7FFF
    addi $t0, $t0, -1
    bne $t0, $t1, frame_check_c
    addi $at, $zero, 3
    bne $t2, $at, frame_check_c
    addi $at, $zero, 1
    bne $t3, $at, frame_check_c
    j frame_died

    frame_check_c:
    srl $t3, $s4, 16    # dir c
    andi $t0, $s0, 0x7FFF
    andi $t1, $s4, 0x7FFF
    beq $t0, $t1, frame_died

    addi $t0, $t0, -0x0100
    bne $t0, $t1, frame_check_c_down
    addi $at, $zero, 2
    bne $t2, $at, frame_check_c_down
    addi $at, $zero, 0
    bne $t3, $at, frame_check_c_down
    j frame_died

    frame_check_c_down:
    andi $t0, $s0, 0x7FFF
    addi $t0, $t0, 0x0100
    bne $t0, $t1, frame_check_c_right
    addi $at, $zero, 0
    bne $t2, $at, frame_check_c_right
    addi $at, $zero, 2
    bne $t3, $at, frame_check_c_right
    j frame_died

    frame_check_c_right:
    andi $t0, $s0, 0x7FFF
    addi $t0, $t0, 1
    bne $t0, $t1, frame_check_c_left
    addi $at, $zero, 3
    bne $t2, $at, frame_check_c_left
    addi $at, $zero, 1
    bne $t3, $at, frame_check_c_left
    j frame_died

    frame_check_c_left:
    andi $t0, $s0, 0x7FFF
    addi $t0, $t0, -1
    bne $t0, $t1, frame_died_not_lose
    addi $at, $zero, 3
    bne $t2, $at, frame_died_not_lose
    addi $at, $zero, 1
    bne $t3, $at, frame_died_not_lose
    j frame_died

    frame_died:
        addi $v0, $zero, 1
        addi $a2, $a2, -1
        bne $a2, $zero, frame_died_not_lose
        addi $v0, $zero, 2
    
    frame_died_not_lose:

    lw $ra, 0($sp)
    lw $t0, 4($sp)
    lw $t1, 8($sp)
    lw $t2, 12($sp)
    lw $t3, 16($sp)
    lw $s6, 20($sp)
    addi $sp, $sp, 24
    jr $ra

# function: return the target of lnky given blinky pos a0, center pos a1
lnky_target:
    addi $sp, $sp, -12
    sw $ra, 0($sp)
    sw $t0, 4($sp)
    sw $t1, 8($sp)

    # x axis
    andi $t0, $a0, 0xFF
    andi $t1, $a1, 0xFF
    sll $t1, $t1, 1
    sub $t1, $t1, $t0
    slt $at, $t1, $zero
    beq $at, $zero, lnky_target_x_ge_0
    add $t1, $zero, $zero
    lnky_target_x_ge_0:
    add $v0, $t1, $zero

    # y axis
    srl $t0, $a0, 8
    srl $t1, $a1, 8
    sll $t1, $t1, 1
    sub $t1, $t1, $t0
    slt $at, $t1, $zero
    beq $at, $zero, lnky_target_y_ge_0
    add $t1, $zero, $zero
    lnky_target_y_ge_0:
    sll $t1, $t1, 8
    add $v0, $v0, $t1

    lw $ra, 0($sp)
    lw $t0, 4($sp)
    lw $t1, 8($sp)
    addi $sp, $sp, 12
    jr $ra

# function: given the status (in a0) and the target of the spirit (in a1)
# returns the next direction
spirit_next_dir:
    addi $sp, $sp, -8
    sw $ra, 0($sp)
    sw $t0, 4($sp)

    add $v1, $zero, $zero
    andi $t0, $a0, 0x7FFF

    lui $at, 0x3
    addi $at, $at, 0x0e00
    bne $a0, $at, spirit_next_dir_not_0e00
    lui $v0, 0x3
    addi $v0, $v0, 0x0e1b
    addi $v1, $zero, 1
    j spirit_next_dir_assign_dir
    spirit_next_dir_not_0e00:

    lui $at, 0x1
    addi $at, $at, 0x0e1b
    bne $a0, $at, spirit_next_dir_not_0e1b
    lui $v0, 0x1
    addi $v0, $v0, 0x0e00
    addi $v1, $zero, 2
    j spirit_next_dir_assign_dir
    spirit_next_dir_not_0e1b:

    addi $at, $zero, 0x0e0c
    bne $t0, $at, spirit_next_dir_not_0e0c
    addi $v0, $zero, 0x1
    j spirit_next_dir_assign_dir
    spirit_next_dir_not_0e0c:

    addi $at, $zero, 0x0e0d
    bne $t0, $at, spirit_next_dir_not_0e0d
    addi $v0, $zero, 0x0
    j spirit_next_dir_assign_dir
    spirit_next_dir_not_0e0d:

    addi $at, $zero, 0x0d0d
    bne $t0, $at, spirit_next_dir_not_0d0d
    addi $v0, $zero, 0x0
    j spirit_next_dir_assign_dir
    spirit_next_dir_not_0d0d:

    addi $at, $zero, 0x0c0d
    bne $t0, $at, spirit_next_dir_not_0c0d
    addi $v0, $zero, 0x0
    j spirit_next_dir_assign_dir
    spirit_next_dir_not_0c0d:

    addi $at, $zero, 0x0e0f
    bne $t0, $at, spirit_next_dir_not_0e0f
    addi $v0, $zero, 0x3
    j spirit_next_dir_assign_dir
    spirit_next_dir_not_0e0f:

    addi $at, $zero, 0x0e0e
    bne $t0, $at, spirit_next_dir_not_0e0e
    addi $v0, $zero, 0x0
    j spirit_next_dir_assign_dir
    spirit_next_dir_not_0e0e:

    addi $at, $zero, 0x0d0e
    bne $t0, $at, spirit_next_dir_not_0d0e
    addi $v0, $zero, 0x0
    j spirit_next_dir_assign_dir
    spirit_next_dir_not_0d0e:

    addi $at, $zero, 0x0c0e
    bne $t0, $at, spirit_next_dir_not_0c0e
    addi $v0, $zero, 0x0
    j spirit_next_dir_assign_dir
    spirit_next_dir_not_0c0e:

    addi $at, $zero, 0x0b0c
    beq $t0, $at, spirit_next_dir_cant_change
    addi $at, $zero, 0x0b0d
    beq $t0, $at, spirit_next_dir_cant_change
    addi $at, $zero, 0x0b0e
    beq $t0, $at, spirit_next_dir_cant_change
    addi $at, $zero, 0x0b0f
    beq $t0, $at, spirit_next_dir_cant_change
    addi $at, $zero, 0x170c
    beq $t0, $at, spirit_next_dir_cant_change
    addi $at, $zero, 0x170f
    beq $t0, $at, spirit_next_dir_cant_change
    j spirit_next_dir_can_change

    spirit_next_dir_cant_change:
    srl $v0, $a0, 16
    addi $at, $zero, 0x1
    beq $v0, $at, spirit_next_dir_assign_dir
    addi $at, $zero, 0x3
    beq $v0, $at, spirit_next_dir_assign_dir

    spirit_next_dir_can_change:
    jal spirit_common_next_dir

    spirit_next_dir_assign_dir:

    lw $ra, 0($sp)
    lw $t0, 4($sp)
    addi $sp, $sp, 8
    jr $ra


# function: given the status (in a0) and the target of the spirit (in a1) when not in special cases
# returns the next direction
# there must be a next direction for a spirit, they won't stop until someone catch the pacman
spirit_common_next_dir:
    addi $sp, $sp, -28
    sw $ra, 0($sp)
    sw $t0, 4($sp)
    sw $a0, 8($sp)
    sw $a1, 12($sp)
    sw $s6, 16($sp)
    sw $s7, 20($sp)
    sw $v1, 24($sp)

    add $t0, $zero, $zero   # intended direction
    srl $v1, $a0, 16    # cur direction
    andi $a0, $a0, 0x7FFF
    addi $s6, $zero, 0xFFF # weight
    add $s7, $a0, $zero # a0 backup

    # check up
    addi $at, $zero, 0x2
    beq $v1, $at, spirit_next_dir_not_up
    addi $a0, $a0, -0x0100
    jal is_blocked
    bne $v0, $zero, spirit_next_dir_not_up
    jal distance2_a0_a1
    slt $at, $v0, $s6
    beq $at, $zero, spirit_next_dir_not_up
    addi $t0, $zero, 0x0
    add $s6, $v0, $zero
    spirit_next_dir_not_up:

    # check right
    add $a0, $s7, $zero
    addi $at, $zero, 0x3
    beq $v1, $at, spirit_next_dir_not_right
    addi $a0, $a0, 1
    jal is_blocked
    bne $v0, $zero, spirit_next_dir_not_right
    jal distance2_a0_a1
    slt $at, $v0, $s6
    beq $at, $zero, spirit_next_dir_not_right
    addi $t0, $zero, 0x1
    add $s6, $v0, $zero
    spirit_next_dir_not_right:

    # check down
    add $a0, $s7, $zero
    addi $at, $zero, 0x0
    beq $v1, $at, spirit_next_dir_not_down
    addi $a0, $a0, 0x0100
    jal is_blocked
    bne $v0, $zero, spirit_next_dir_not_down
    jal distance2_a0_a1
    slt $at, $v0, $s6
    beq $at, $zero, spirit_next_dir_not_down
    addi $t0, $zero, 0x2
    add $s6, $v0, $zero
    spirit_next_dir_not_down:

    # check left
    add $a0, $s7, $zero
    addi $at, $zero, 0x1
    beq $v1, $at, spirit_next_dir_not_left
    addi $a0, $a0, -1
    jal is_blocked
    bne $v0, $zero, spirit_next_dir_not_left
    jal distance2_a0_a1
    slt $at, $v0, $s6
    beq $at, $zero, spirit_next_dir_not_left
    addi $t0, $zero, 0x3
    add $s6, $v0, $zero
    spirit_next_dir_not_left:

    add $v0, $t0, $zero

    lw $ra, 0($sp)
    lw $t0, 4($sp)
    lw $a0, 8($sp)
    lw $a1, 12($sp)
    lw $s6, 16($sp)
    lw $s7, 20($sp)
    lw $v1, 24($sp)
    addi $sp, $sp, 28
    jr $ra

# function: return the distance square of two position a0 a1 (9:8 y, 1:0 x) 
distance2_a0_a1:
    addi $sp, $sp, -20
    sw $ra, 0($sp)
    sw $t0, 4($sp)
    sw $t1, 8($sp)
    sw $t2, 12($sp)
    sw $s6, 16($sp)

    andi $t0, $a0, 0xFF
    andi $t1, $a1, 0xFF
    slt $at, $t0, $t1  # at = 0 => t0 >= t1
    sub $t2, $t0, $t1
    beq $at, $zero, distance2_x_bigger
    sub $t2, $t1, $t0
    distance2_x_bigger:
    add $s6, $a0, $zero
    add $a0, $t2, $zero
    jal a0_square
    add $v0, $a0, $zero
    add $a0, $s6, $zero

    srl $t0, $a0, 8
    srl $t1, $a1, 8
    andi $t0, $t0, 0xFF
    andi $t1, $t1, 0xFF
    slt $at, $t0, $t1  # at = 0 => t0 >= t1
    sub $t2, $t0, $t1
    beq $at, $zero, distance2_y_bigger
    sub $t2, $t1, $t0
    distance2_y_bigger:
    add $s6, $a0, $zero
    add $a0, $t2, $zero
    jal a0_square
    add $v0, $v0, $a0
    add $a0, $s6, $zero

    lw $ra, 0($sp)
    lw $t0, 4($sp)
    lw $t1, 8($sp)
    lw $t2, 12($sp)
    lw $s6, 16($sp)
    addi $sp, $sp, 20
    jr $ra

# function: square a0
# ruin v1
a0_square:
    addi $sp, $sp, -4
    sw $v1, 0($sp)
    add $at, $a0, $zero
    add $v1, $a0, $zero
    add $a0, $zero, $zero
    a0_square_loop:
        beq $at, $zero, a0_square_loop_end
        add $a0, $a0, $v1
        addi $at, $at, -1
        j a0_square_loop
    a0_square_loop_end:
    lw $v1, 0($sp)
    addi $sp, $sp, 4
    jr $ra

# function: tell whether a0 (9:8 y, 1:0 x) a wall, $v0 = 1 means is wall
# ruin t1 t2 t3
is_blocked:
    addi $sp, $sp, -16
    sw $ra, 0($sp)
    sw $t1, 4($sp)
    sw $t2, 8($sp)
    sw $t3, 12($sp)

    add $at, $a0, $zero
    andi $t2, $at, 0x00FF    # x
    srl $at, $at, 8
    andi $t3, $at, 0x00FF    # y
    
    sll $at, $t3, 3
    sub $t3, $at, $t3   # y *= 7
    srl $at, $t2, 2     # x /= 4    t2 is still x
    add $t3, $at, $t3   # index of word
    sll $t3, $t3 ,2     # addr
    add $t3, $t3, $gp   # add maze addr start
    lw  $t1, 0($t3)

    andi $t2, $t2, 0x3  # x %= 4
    slti $at, $t2, 1    # x = 0
    beq $at, $t8, is_blocked_shift_3
    slti $at, $t2, 2    # x = 1
    beq $at, $t8, is_blocked_shift_2
    slti $at, $t2, 3    # x = 2
    beq $at, $t8, is_blocked_shift_1
    j is_blocked_shift_end
    is_blocked_shift_3:
    srl $t1, $t1, 24
    j is_blocked_shift_end
    is_blocked_shift_2:
    srl $t1, $t1, 16
    j is_blocked_shift_end
    is_blocked_shift_1:
    srl $t1, $t1, 8
    is_blocked_shift_end:
    andi $t3, $t1, 0xFF

    addi $v0, $zero, 0
    beq $t3, $zero, not_wall
    addi $at, $zero, 0x20
    beq $t3, $at, not_wall
    addi $at, $zero, 0x0F
    beq $t3, $at, not_wall
    addi $at, $zero, 0x2F
    beq $t3, $at, not_wall

    addi $v0, $zero, 1
    not_wall:
    lw $ra, 0($sp)
    lw $t1, 4($sp)
    lw $t2, 8($sp)
    lw $t3, 12($sp)
    addi $sp, $sp, 16
    jr $ra

# function: dispaly original maze
# ruin t4-t7 a0
maze_init:
    addi $sp, $sp, -24
    sw $ra, 0($sp)
    sw $t4, 4($sp)
    sw $t5, 8($sp)
    sw $t6, 12($sp)
    sw $t7, 16($sp)
    sw $a0, 20($sp)

    add $t4, $zero, $zero
    add $t5, $zero, $zero
    addi $t6, $zero, 28
    addi $t7, $zero, 32
    addi $a0, $zero, 0
    maze_loop:
        jal reset_block
        addi $a0, $a0, 1
        
        addi $t4, $t4, 1
        bne $t4, $t6, maze_loop
        
        sub $a0, $a0, $t4
        addi $a0, $a0, 0x0100

        add $t4, $zero, $zero
        addi $t5, $t5, 1
        bne $t5, $t7, maze_loop

    lw $ra, 0($sp)
    lw $t4, 4($sp)
    lw $t5, 8($sp)
    lw $t6, 12($sp)
    lw $t7, 16($sp)
    lw $a0, 20($sp)
    addi $sp, $sp, 24
    jr $ra

# function: display original maze block at a0 (9:8 y, 1:0 x)
reset_block:
    addi $sp, $sp, -40
    sw $ra, 0($sp)
    sw $a0, 4($sp)
    sw $a1, 8($sp)
    sw $t1, 12($sp)
    sw $t2, 16($sp)
    sw $t3, 20($sp)
    sw $t4, 24($sp)
    sw $t5, 28($sp)
    sw $t6, 32($sp)
    sw $t7, 36($sp)

    add $at, $a0, $zero
    andi $t2, $at, 0x00FF    # x
    srl $at, $at, 8
    andi $t3, $at, 0x00FF    # y
    
    sll $at, $t3, 3
    sub $t3, $at, $t3   # y *= 7
    srl $at, $t2, 2     # x /= 4    t2 is still x
    add $t3, $at, $t3   # index of word
    sll $t3, $t3 ,2     # addr
    add $t3, $t3, $gp   # add maze addr start
    lw  $t1, 0($t3)

    andi $t2, $t2, 0x3  # x %= 4
    slti $at, $t2, 1    # x = 0
    beq $at, $t8, shift_3
    slti $at, $t2, 2    # x = 1
    beq $at, $t8, shift_2
    slti $at, $t2, 3    # x = 2
    beq $at, $t8, shift_1
    j shift_end
    shift_3:
    srl $t1, $t1, 24
    j shift_end
    shift_2:
    srl $t1, $t1, 16
    j shift_end
    shift_1:
    srl $t1, $t1, 8
    shift_end:
    andi $a1, $t1, 0xFF
    jal display_block

    jal check_bean
    beq $v0, $zero, reset_block_no_bean
    addi $a1, $zero, 0x80
    jal display_block
    reset_block_no_bean:

    lw $ra, 0($sp)
    lw $a0, 4($sp)
    lw $a1, 8($sp)
    lw $t1, 12($sp)
    lw $t2, 16($sp)
    lw $t3, 20($sp)
    lw $t4, 24($sp)
    lw $t5, 28($sp)
    lw $t6, 32($sp)
    lw $t7, 36($sp)
    addi $sp, $sp,40
    jr $ra

# function: given the pos a0 (9:8 y, 1:0 x), return whether there is a bean in v0 (0x1: yes, 0x0: no)
check_bean:
    addi $sp, $sp, -12
    sw $t1, 0($sp)
    sw $t2, 4($sp)
    sw $t3, 8($sp)
    add $at, $a0, $zero
    andi $t2, $at, 0x00FF    # x
    srl $at, $at, 8
    andi $t3, $at, 0x00FF    # y
    
    sll $at, $t3, 3
    sub $t3, $at, $t3   # y *= 7
    srl $at, $t2, 2     # x /= 4    t2 is still x
    add $t3, $at, $t3   # index of word
    sll $t3, $t3 ,2     # addr
    add $t3, $t3, $gp   # add maze addr start
    addi $t3, $t3, 0x0E2C   # skip maze, pics
    lw  $t1, 0($t3)

    andi $t2, $t2, 0x3  # x %= 4
    slti $at, $t2, 1    # x = 0
    beq $at, $t8, check_bean_shift_3
    slti $at, $t2, 2    # x = 1
    beq $at, $t8, check_bean_shift_2
    slti $at, $t2, 3    # x = 2
    beq $at, $t8, check_bean_shift_1
    j check_bean_shift_end
    check_bean_shift_3:
    srl $t1, $t1, 24
    j check_bean_shift_end
    check_bean_shift_2:
    srl $t1, $t1, 16
    j check_bean_shift_end
    check_bean_shift_1:
    srl $t1, $t1, 8
    check_bean_shift_end:
    andi $v0, $t1, 0x3

    lw $t1, 0($sp)
    lw $t2, 4($sp)
    lw $t3, 8($sp)
    addi $sp, $sp, 12
    jr $ra

# function: eat the bean at pos a0 (9:8 y, 1:0 x)
eat_bean:
    addi $sp, $sp, -12
    sw $t1, 0($sp)
    sw $t2, 4($sp)
    sw $t3, 8($sp)
    add $at, $a0, $zero
    andi $t2, $at, 0x00FF    # x
    srl $at, $at, 8
    andi $t3, $at, 0x00FF    # y
    
    sll $at, $t3, 3
    sub $t3, $at, $t3   # y *= 7
    srl $at, $t2, 2     # x /= 4    t2 is still x
    add $t3, $at, $t3   # index of word
    sll $t3, $t3 ,2     # addr
    add $t3, $t3, $gp   # add maze addr start
    addi $t3, $t3, 0x0E2C   # skip maze, pics
    lw  $t1, 0($t3)

    andi $t2, $t2, 0x3  # x %= 4
    slti $at, $t2, 1    # x = 0
    beq $at, $t8, eat_bean_3
    slti $at, $t2, 2    # x = 1
    beq $at, $t8, eat_bean_2
    slti $at, $t2, 3    # x = 2
    beq $at, $t8, eat_bean_1
    j eat_bean_0

    eat_bean_3:
    srl $at, $t1, 24
    beq $at, $zero, eat_bean_end

    addi $s5, $s5, 1
    lui $at, 0x000F
    addi $at, $at, 0x0F0F
    and $t1, $t1, $at
    j eat_bean_end

    eat_bean_2:
    srl $at, $t1, 16
    andi $at, $at, 0xF
    beq $at, $zero, eat_bean_end

    addi $s5, $s5, 1
    lui $at, 0x0F00
    addi $at, $at, 0x0F0F
    and $t1, $t1, $at
    j eat_bean_end

    eat_bean_1:
    srl $at, $t1, 8
    andi $at, $at, 0xF
    beq $at, $zero, eat_bean_end

    addi $s5, $s5, 1
    lui $at, 0x0F0F
    addi $at, $at, 0x000F
    and $t1, $t1, $at
    j eat_bean_end

    eat_bean_0:
    andi $at, $t1, 0xFF
    beq $at, $zero, eat_bean_end

    addi $s5, $s5, 1
    lui $at, 0x0F0F
    addi $at, $at, 0x0F00
    and $t1, $t1, $at

    eat_bean_end:
    sw $t1, 0($t3)

    lw $t1, 0($sp)
    lw $t2, 4($sp)
    lw $t3, 8($sp)
    addi $sp, $sp, 12
    jr $ra

# function: $a0 times 640 (for emulator)
a0_times_640:
    sll $at, $a0, 7
    sll $a0, $at, 2
    add $a0, $a0, $at
    jr $ra

# function: $a0 times 420
a0_times_420:
    sll $at, $a0, 3     # at = 8x
    sub $at, $at, $a0   # at = 7x
    sll $a0, $at, 2     # a0 = 28x
    sll $at, $a0, 4     # at = 448x
    sub $a0, $at, $a0   # a0 = 420x
    jr $ra

# function: $a1 times 15
a0_times_15:
    sll $at, $a0, 4     # at = 16x
    sub $a0, $at, $a0   # a0 = 15x
    jr $ra


# function: displat block a0 with type a1
display_block:
    addi $sp, $sp, -36
    sw $ra, 0($sp)
    sw $a0, 4($sp)
    sw $a1, 8($sp)
    sw $t1, 12($sp)
    sw $t2, 16($sp)
    sw $t3, 20($sp)
    sw $t4, 24($sp)
    sw $t5, 28($sp)
    sw $t0, 32($sp)


    andi $t2, $a0, 0x00FF    # x
    srl $a0, $a0, 8
    andi $t3, $a0, 0x00FF    # y
    
    add $a0, $t3, $zero
    # TOGGLE
    # jal a0_times_420
    jal a0_times_640
    add $a0, $a0, $t2
    jal a0_times_15
    # TOGGLE
    # sll $a0, $a0, 2         #  pixel addr
    # addi $t2, $a0, 56       # 14 * 4 addr of the ending pixel
    sll $a0, $a0, 1         #  pixel addr
    addi $t2, $a0, 28       # 14 * 2 addr of the ending pixel
    add $t2, $t2, $k0


    addi $t1, $zero, 0x0F
    beq $a1, $t1, pink_door_type
    addi $t1, $zero, 0x2F
    beq $a1, $t1, pink_door_type
    slti $at, $a1, 0x16
    beq $at, $t8, black_type
    slti $at, $a1, 0x1c
    beq $at, $t8, gray_type_special
    slti $at, $a1, 0x30
    beq $at, $t8, gray_type_common
    slti $at, $a1, 0x40
    beq $at, $t8, pacman_type
    slti $at, $a1, 0x50
    beq $at, $t8, blinky_type
    slti $at, $a1, 0x60
    beq $at, $t8, pinky_type
    slti $at, $a1, 0x70
    beq $at, $t8, inky_type
    slti $at, $a1, 0x80
    beq $at, $t8, clyde_type
    slti $at, $a1, 0x90
    beq $at, $t8, bean_type
    j banner_type

    pink_door_type:
        slti $at, $a1, 0x2F     # at = 1: black
        addi $t1, $zero, 0
        bne $at, $zero, pink_door_black
        addi $a1, $a1, -0x20
        addi $t1, $zero, 1    # 1:gray
        pink_door_black:
        add $a0, $a1, $zero
        jal a0_times_15
        sll $a0, $a0, 2     #  * 4 to get addr
        add $a0, $a0, $gp
        addi $t3, $a0, 0x0364   # skip maze, pic addr starts

        addi $t4, $zero, 15
        addi $t5, $zero, 15
        pink_door_type_loop:
            lw $t0, 0($t3)
        pink_door_type_loop_inner:
            srl $t0, $t0, 2
            andi $at, $t0, 0x3  # lowest 2 bits
            beq $at, $zero, pink_door_type_loop_0
            addi $at, $zero, 0x0fbf
            j pink_door_type_loop_0_end
            pink_door_type_loop_0:
            addi $at, $zero, 0x0101
            beq $t1, $zero, pink_door_type_loop_0_end   # black
            addi $at, $zero, 0x0111
            pink_door_type_loop_0_end:
            # TOGGLE
            # sw $at, 0($t2)
            # addi $t2, $t2, -4
            sh $at, 0($t2)
            addi $t2, $t2, -2
            addi $t4, $t4, -1
            bne $t4, $0, pink_door_type_loop_inner
            addi $t3, $t3, 4
            # addi $t2, $t2, 1740     # (420 + 15) * 4
            addi $t2, $t2, 1310   # for emulator
            addi $t4, $zero, 15
            addi $t5, $t5, -1
            bne $t5, $0, pink_door_type_loop
        j display_block_end

    black_type:
        add $a0, $a1, $zero
        jal a0_times_15
        sll $a0, $a0, 2     #  * 4 to get addr
        add $a0, $a0, $gp
        addi $t3, $a0, 0x0364   # skip maze, pic addr starts

        addi $t4, $zero, 15
        addi $t5, $zero, 15
        black_type_loop:
            lw $t0, 0($t3)
        black_type_loop_inner:
            srl $t0, $t0, 2
            andi $at, $t0, 0x3  # lowest 2 bits
            beq $at, $zero, black_type_loop_0
            addi $at, $zero, 0x033d
            j black_type_loop_0_end
            black_type_loop_0:
            addi $at, $zero, 0x0101
            black_type_loop_0_end:
            # TOGGLE
            # sw $at, 0($t2)
            # addi $t2, $t2, -4
            sh $at, 0($t2)
            addi $t2, $t2, -2
            addi $t4, $t4, -1
            bne $t4, $0, black_type_loop_inner
            addi $t3, $t3, 4
            # addi $t2, $t2, 1740     # (420 + 15) * 4
            addi $t2, $t2, 1310   # for emulator
            addi $t4, $zero, 15
            addi $t5, $t5, -1
            bne $t5, $0, black_type_loop
        j display_block_end

    gray_type_special:
        add $a0, $a1, $zero
        jal a0_times_15
        sll $a0, $a0, 2     #  * 4 to get addr
        add $a0, $a0, $gp
        addi $t3, $a0, 0x0364   # skip maze, pic addr starts

        addi $t4, $zero, 15
        addi $t5, $zero, 15
        gray_type_special_loop:
            lw $t0, 0($t3)
        gray_type_special_loop_inner:
            srl $t0, $t0, 2
            andi $at, $t0, 0x3  # lowest 2 bits
            beq $at, $zero, gray_type_special_loop_0
            addi $at, $zero, 0x033d
            j gray_type_special_loop_0_end
            gray_type_special_loop_0:
            addi $at, $zero, 0x0111
            gray_type_special_loop_0_end:
            # TOGGLE
            # sw $at, 0($t2)
            # addi $t2, $t2, -4
            sh $at, 0($t2)
            addi $t2, $t2, -2
            addi $t4, $t4, -1
            bne $t4, $0, gray_type_special_loop_inner
            addi $t3, $t3, 4
            # addi $t2, $t2, 1740     # (420 + 15) * 4
            addi $t2, $t2, 1310   # for emulator
            addi $t4, $zero, 15
            addi $t5, $t5, -1
            bne $t5, $0, gray_type_special_loop
        j display_block_end

    gray_type_common:
        addi $a1, $a1, -0x20
        add $a0, $a1, $zero
        jal a0_times_15
        sll $a0, $a0, 2     #  * 4 to get addr
        add $a0, $a0, $gp
        addi $t3, $a0, 0x0364   # skip maze, pic addr starts

        addi $t4, $zero, 15
        addi $t5, $zero, 15
        gray_type_common_loop:
            lw $t0, 0($t3)
        gray_type_common_loop_inner:
            srl $t0, $t0, 2
            andi $at, $t0, 0x3  # lowest 2 bits
            beq $at, $zero, gray_type_common_loop_0
            addi $at, $zero, 0x033d
            j gray_type_common_loop_0_end
            gray_type_common_loop_0:
            addi $at, $zero, 0x0111
            gray_type_common_loop_0_end:
            # TOGGLE
            # sw $at, 0($t2)
            # addi $t2, $t2, -4
            sh $at, 0($t2)
            addi $t2, $t2, -2
            addi $t4, $t4, -1
            bne $t4, $0, gray_type_common_loop_inner
            addi $t3, $t3, 4
            # addi $t2, $t2, 1740     # (420 + 15) * 4
            addi $t2, $t2, 1310   # for emulator
            addi $t4, $zero, 15
            addi $t5, $t5, -1
            bne $t5, $0, gray_type_common_loop
        j display_block_end

    pacman_type:
        addi $a1, $a1, -0x30
        add $a0, $a1, $zero
        jal a0_times_15
        sll $a0, $a0, 2     #  * 4 to get addr
        add $a0, $a0, $gp
        addi $t3, $a0, 0x09F4   # skip maze, block pic, pacman addr starts

        addi $t4, $zero, 15
        addi $t5, $zero, 15
        pacman_type_loop:
            lw $t0, 0($t3)
        pacman_type_loop_inner:
            srl $t0, $t0, 2
            andi $at, $t0, 0x3  # lowest 2 bits
            beq $at, $zero, pacman_type_loop_0
            addi $at, $zero, 0x0fe0
            j pacman_type_loop_0_end
            pacman_type_loop_0:
            addi $at, $zero, 0x0111
            pacman_type_loop_0_end:
            # TOGGLE
            # sw $at, 0($t2)
            # addi $t2, $t2, -4
            sh $at, 0($t2)
            addi $t2, $t2, -2
            addi $t4, $t4, -1
            bne $t4, $0, pacman_type_loop_inner
            addi $t3, $t3, 4
            # addi $t2, $t2, 1740     # (420 + 15) * 4
            addi $t2, $t2, 1310   # for emulator
            addi $t4, $zero, 15
            addi $t5, $t5, -1
            bne $t5, $0, pacman_type_loop
        j display_block_end

    blinky_type:
        addi $a1, $a1, -0x40
        add $a0, $a1, $zero
        jal a0_times_15
        sll $a0, $a0, 2     #  * 4 to get addr
        add $a0, $a0, $gp
        addi $t3, $a0, 0x0C4C   # skip maze, block pic, pacman, spirit addr starts

        addi $t4, $zero, 15
        addi $t5, $zero, 15
        blinky_type_loop:
            lw $t0, 0($t3)
        blinky_type_loop_inner:
            srl $t0, $t0, 2
            andi $t1, $t0, 0x3  # lowest 2 bits
            beq $t1, $zero, blinky_type_loop_0
            addi $at, $zero, 0x1
            beq $t1, $at, blinky_type_loop_1
            addi $at, $zero, 0x2
            beq $t1, $at, blinky_type_loop_2
            addi $at, $zero, 0x3
            beq $t1, $at, blinky_type_loop_3

            blinky_type_loop_0:
            addi $at, $zero, 0x0000
            j blinky_type_loop_0_end

            blinky_type_loop_1:
            addi $at, $zero, 0x0f31
            j blinky_type_loop_0_end

            blinky_type_loop_2:
            addi $at, $zero, 0x0fff
            j blinky_type_loop_0_end

            blinky_type_loop_3:
            addi $at, $zero, 0x0238

            blinky_type_loop_0_end:
            # TOGGLE
            # sw $at, 0($t2)
            # addi $t2, $t2, -4
            sh $at, 0($t2)
            addi $t2, $t2, -2
            addi $t4, $t4, -1
            bne $t4, $0, blinky_type_loop_inner
            addi $t3, $t3, 4
            # addi $t2, $t2, 1740     # (420 + 15) * 4
            addi $t2, $t2, 1310   # for emulator
            addi $t4, $zero, 15
            addi $t5, $t5, -1
            bne $t5, $0, blinky_type_loop
        j display_block_end

    pinky_type:
        addi $a1, $a1, -0x50
        add $a0, $a1, $zero
        jal a0_times_15
        sll $a0, $a0, 2     #  * 4 to get addr
        add $a0, $a0, $gp
        addi $t3, $a0, 0x0C4C   # skip maze, block pic, pacman, spirit addr starts

        addi $t4, $zero, 15
        addi $t5, $zero, 15
        pinky_type_loop:
            lw $t0, 0($t3)
        pinky_type_loop_inner:
            srl $t0, $t0, 2
            andi $t1, $t0, 0x3  # lowest 2 bits
            beq $t1, $zero, pinky_type_loop_0
            addi $at, $zero, 0x1
            beq $t1, $at, pinky_type_loop_1
            addi $at, $zero, 0x2
            beq $t1, $at, pinky_type_loop_2
            addi $at, $zero, 0x3
            beq $t1, $at, pinky_type_loop_3

            pinky_type_loop_0:
            addi $at, $zero, 0x0000
            j pinky_type_loop_0_end

            pinky_type_loop_1:
            addi $at, $zero, 0x0fcd
            j pinky_type_loop_0_end

            pinky_type_loop_2:
            addi $at, $zero, 0x0fff
            j pinky_type_loop_0_end

            pinky_type_loop_3:
            addi $at, $zero, 0x0238

            pinky_type_loop_0_end:
            # TOGGLE
            # sw $at, 0($t2)
            # addi $t2, $t2, -4
            sh $at, 0($t2)
            addi $t2, $t2, -2
            addi $t4, $t4, -1
            bne $t4, $0, pinky_type_loop_inner
            addi $t3, $t3, 4
            # addi $t2, $t2, 1740     # (420 + 15) * 4
            addi $t2, $t2, 1310   # for emulator
            addi $t4, $zero, 15
            addi $t5, $t5, -1
            bne $t5, $0, pinky_type_loop
        j display_block_end

    inky_type:
        addi $a1, $a1, -0x60
        add $a0, $a1, $zero
        jal a0_times_15
        sll $a0, $a0, 2     #  * 4 to get addr
        add $a0, $a0, $gp
        addi $t3, $a0, 0x0C4C   # skip maze, block pic, pacman, spirit addr starts

        addi $t4, $zero, 15
        addi $t5, $zero, 15
        inky_type_loop:
            lw $t0, 0($t3)
        inky_type_loop_inner:
            srl $t0, $t0, 2
            andi $t1, $t0, 0x3  # lowest 2 bits
            beq $t1, $zero, inky_type_loop_0
            addi $at, $zero, 0x1
            beq $t1, $at, inky_type_loop_1
            addi $at, $zero, 0x2
            beq $t1, $at, inky_type_loop_2
            addi $at, $zero, 0x3
            beq $t1, $at, inky_type_loop_3

            inky_type_loop_0:
            addi $at, $zero, 0x0000
            j inky_type_loop_0_end

            inky_type_loop_1:
            addi $at, $zero, 0x04dc
            j inky_type_loop_0_end

            inky_type_loop_2:
            addi $at, $zero, 0x0fff
            j inky_type_loop_0_end

            inky_type_loop_3:
            addi $at, $zero, 0x0238

            inky_type_loop_0_end:
            # TOGGLE
            # sw $at, 0($t2)
            # addi $t2, $t2, -4
            sh $at, 0($t2)
            addi $t2, $t2, -2
            addi $t4, $t4, -1
            bne $t4, $0, inky_type_loop_inner
            addi $t3, $t3, 4
            # addi $t2, $t2, 1740     # (420 + 15) * 4
            addi $t2, $t2, 1310   # for emulator
            addi $t4, $zero, 15
            addi $t5, $t5, -1
            bne $t5, $0, inky_type_loop
        j display_block_end

    clyde_type:
        addi $a1, $a1, -0x70
        add $a0, $a1, $zero
        jal a0_times_15
        sll $a0, $a0, 2     #  * 4 to get addr
        add $a0, $a0, $gp
        addi $t3, $a0, 0x0C4C   # skip maze, block pic, pacman, spirit addr starts

        addi $t4, $zero, 15
        addi $t5, $zero, 15
        clyde_type_loop:
            lw $t0, 0($t3)
        clyde_type_loop_inner:
            srl $t0, $t0, 2
            andi $t1, $t0, 0x3  # lowest 2 bits
            beq $t1, $zero, clyde_type_loop_0
            addi $at, $zero, 0x1
            beq $t1, $at, clyde_type_loop_1
            addi $at, $zero, 0x2
            beq $t1, $at, clyde_type_loop_2
            addi $at, $zero, 0x3
            beq $t1, $at, clyde_type_loop_3

            clyde_type_loop_0:
            addi $at, $zero, 0x0000
            j clyde_type_loop_0_end

            clyde_type_loop_1:
            addi $at, $zero, 0x0fb5
            j clyde_type_loop_0_end

            clyde_type_loop_2:
            addi $at, $zero, 0x0fff
            j clyde_type_loop_0_end

            clyde_type_loop_3:
            addi $at, $zero, 0x0238

            clyde_type_loop_0_end:
            # TOGGLE
            # sw $at, 0($t2)
            # addi $t2, $t2, -4
            sh $at, 0($t2)
            addi $t2, $t2, -2
            addi $t4, $t4, -1
            bne $t4, $0, clyde_type_loop_inner
            addi $t3, $t3, 4
            # addi $t2, $t2, 1740     # (420 + 15) * 4
            addi $t2, $t2, 1310   # for emulator
            addi $t4, $zero, 15
            addi $t5, $t5, -1
            bne $t5, $0, clyde_type_loop
        j display_block_end

    bean_type:
        addi $at, $zero, 0x0fb9
        # TOGGLE
        # 
        addi $t2, $t2, 10224   # (640*8 - 8)*2 go to first pixel directly
        sh $at, 0($t2)
        sh $at, 2($t2)
        addi $t2, $t2, 1280  # 1 line
        sh $at, 0($t2)
        sh $at, 2($t2)
        j display_block_end

    banner_type:
        addi $a1, $a1, -0x90
        add $a0, $a1, $zero
        jal a0_times_15
        sll $a0, $a0, 2     #  * 4 to get addr
        add $a0, $a0, $gp
        addi $t3, $a0, 0x152C   # skip maze, block pic, pacman, beans, banner addr starts

        addi $t4, $zero, 15
        addi $t5, $zero, 15
        banner_type_loop:
            lw $t0, 0($t3)
        banner_type_loop_inner:
            andi $at, $t0, 0x3  # lowest 2 bits
            beq $at, $zero, banner_type_loop_0
            addi $at, $zero, 0x0ff1
            j banner_type_loop_0_end
            banner_type_loop_0:
            addi $at, $zero, 0x0111
            banner_type_loop_0_end:
            # TOGGLE
            # sw $at, 0($t2)
            # addi $t2, $t2, -4
            sh $at, 0($t2)
            addi $t2, $t2, -2
            srl $t0, $t0, 2
            addi $t4, $t4, -1
            bne $t4, $0, banner_type_loop_inner
            addi $t3, $t3, 4
            # addi $t2, $t2, 1740     # (420 + 15) * 4
            addi $t2, $t2, 1310   # for emulator
            addi $t4, $zero, 15
            addi $t5, $t5, -1
            bne $t5, $0, banner_type_loop
        j display_block_end

    display_block_end:
        lw $ra, 0($sp)
        lw $a0, 4($sp)
        lw $a1, 8($sp)
        lw $t1, 12($sp)
        lw $t2, 16($sp)
        lw $t3, 20($sp)
        lw $t4, 24($sp)
        lw $t5, 28($sp)
        lw $t0, 32($sp)
        addi $sp, $sp, 36
        jr $ra

data:
    sll $zero, $zero, 0