# Copyright (c) 2007 Liyang HU, http://liyang.hu/

# Permission is hereby granted, free of charge, to any person obtaining a copy
# of this software and associated documentation files (the "Software"), to deal
# in the Software without restriction, including without limitation the rights
# to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
# copies of the Software, and to permit persons to whom the Software is
# furnished to do so, subject to the following conditions:

# The above copyright notice and this permission notice shall be included in
# all copies or substantial portions of the Software.

# THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
# IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
# FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
# AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
# LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
# OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
# THE SOFTWARE.

	.data

# Screen buffer {{{
	.align 2
screen:
	.space 4096
# }}}

# Game data: current and next piece, total lines {{{
	.align 4
piece_next:
	.word 0
piece_current:
	.word 0 # rnd % 28 -- 7 pieces, 4 variations each
piece_pos:
	.word 0
lines:
	.word 0
# }}}

# RC4 RNG data {{{
	.align 4
rc4_pool:
	.space 256
rc4_i:
	.word 0
rc4_j:
	.word 0
rc4_key:
	.space 256
# }}}

# Messages {{{
	.align 1
str_seed:
	.asciiz "Random seed: "
str_status:
	.asciiz "Lines: "
str_info:
	.asciiz "\nLeft/Right: j/l, Rotate: i/k, Drop: spacebar\n"
str_game_over:
	.asciiz "Game over dude!\n"
# }}}

# Grid: 12 wide by 21 tall, with U shaped 0x08 padding on edges {{{
	.align 4
grid: 
	.space 252
grid_temp:
	.space 252

grid_left:
	.byte 0x08, 0x00, 0x00, 0x00
grid_right:
	.byte 0x00, 0x00, 0x00, 0x08
# }}}

# the six different pieces (including rotations) {{{

	.align 1
piece_render_lut: # 1 byte per entry {{{
	# 0: the empty `piece'
	.ascii " "
	# 1: the long one
	.ascii "X"
	# 2: the boxy one
	.ascii "O"
	# 3: the Z shaped one
	.ascii "Z"
	# 4: the anti-Z one
	.ascii "*"
	# 5: the L shaped one
	.ascii "@"
	# 6: the anti-L one
	.ascii "&"
	# 7: the pyramid
	.ascii "T"
	# 8: the wall
	.ascii "#"
	# 9: the newline
	.ascii "\n"
# }}}

	.align 4
pieces_start: # 16 bytes each per rotated piece
# 1: the long one {{{
piece_1a:
	.byte 0, 0, 0, 0
	.byte 1, 1, 1, 1
	.byte 0, 0, 0, 0
	.byte 0, 0, 0, 0
piece_1b:
	.byte 0, 0, 1, 0
	.byte 0, 0, 1, 0
	.byte 0, 0, 1, 0
	.byte 0, 0, 1, 0
piece_1c:
	.byte 0, 0, 0, 0
	.byte 0, 0, 0, 0
	.byte 1, 1, 1, 1
	.byte 0, 0, 0, 0
piece_1d:
	.byte 0, 1, 0, 0
	.byte 0, 1, 0, 0
	.byte 0, 1, 0, 0
	.byte 0, 1, 0, 0
# }}}

# 2: the boxy one {{{
piece_2a:
	.byte 0, 0, 0, 0
	.byte 0, 2, 2, 0
	.byte 0, 2, 2, 0
	.byte 0, 0, 0, 0
piece_2b:
	.byte 0, 0, 0, 0
	.byte 0, 2, 2, 0
	.byte 0, 2, 2, 0
	.byte 0, 0, 0, 0
piece_2c:
	.byte 0, 0, 0, 0
	.byte 0, 2, 2, 0
	.byte 0, 2, 2, 0
	.byte 0, 0, 0, 0
piece_2d:
	.byte 0, 0, 0, 0
	.byte 0, 2, 2, 0
	.byte 0, 2, 2, 0
	.byte 0, 0, 0, 0
# }}}

# 3: the Z shaped one {{{
piece_3a:
	.byte 0, 0, 0, 0
	.byte 3, 3, 0, 0
	.byte 0, 3, 3, 0
	.byte 0, 0, 0, 0
piece_3b:
	.byte 0, 0, 3, 0
	.byte 0, 3, 3, 0
	.byte 0, 3, 0, 0
	.byte 0, 0, 0, 0
piece_3c:
	.byte 0, 0, 0, 0
	.byte 0, 3, 3, 0
	.byte 0, 0, 3, 3
	.byte 0, 0, 0, 0
piece_3d:
	.byte 0, 0, 0, 0
	.byte 0, 0, 3, 0
	.byte 0, 3, 3, 0
	.byte 0, 3, 0, 0
# }}}

# 4: the anti-Z one {{{
piece_4a:
	.byte 0, 0, 0, 0
	.byte 0, 4, 4, 0
	.byte 4, 4, 0, 0
	.byte 0, 0, 0, 0
piece_4b:
	.byte 0, 4, 0, 0
	.byte 0, 4, 4, 0
	.byte 0, 0, 4, 0
	.byte 0, 0, 0, 0
piece_4c:
	.byte 0, 0, 0, 0
	.byte 0, 0, 4, 4
	.byte 0, 4, 4, 0
	.byte 0, 0, 0, 0
piece_4d:
	.byte 0, 0, 0, 0
	.byte 0, 4, 0, 0
	.byte 0, 4, 4, 0
	.byte 0, 0, 4, 0
# }}}

# 5: the L shaped one {{{
piece_5a:
	.byte 0, 0, 0, 0
	.byte 0, 0, 5, 0
	.byte 5, 5, 5, 0
	.byte 0, 0, 0, 0
piece_5b:
	.byte 0, 5, 0, 0
	.byte 0, 5, 0, 0
	.byte 0, 5, 5, 0
	.byte 0, 0, 0, 0
piece_5c:
	.byte 0, 0, 0, 0
	.byte 0, 5, 5, 5
	.byte 0, 5, 0, 0
	.byte 0, 0, 0, 0
piece_5d:
	.byte 0, 0, 0, 0
	.byte 0, 5, 5, 0
	.byte 0, 0, 5, 0
	.byte 0, 0, 5, 0
# }}}

# 6: the anti-L one {{{
piece_6a:
	.byte 0, 0, 0, 0
	.byte 6, 6, 6, 0
	.byte 0, 0, 6, 0
	.byte 0, 0, 0, 0
piece_6b:
	.byte 0, 0, 6, 0
	.byte 0, 0, 6, 0
	.byte 0, 6, 6, 0
	.byte 0, 0, 0, 0
piece_6c:
	.byte 0, 0, 0, 0
	.byte 0, 6, 0, 0
	.byte 0, 6, 6, 6
	.byte 0, 0, 0, 0
piece_6d:
	.byte 0, 0, 0, 0
	.byte 0, 6, 6, 0
	.byte 0, 6, 0, 0
	.byte 0, 6, 0, 0
# }}}

# 7: the pyramid {{{
piece_7a:
	.byte 0, 0, 0, 0
	.byte 7, 7, 7, 0
	.byte 0, 7, 0, 0
	.byte 0, 0, 0, 0
piece_7b:
	.byte 0, 0, 7, 0
	.byte 0, 7, 7, 0
	.byte 0, 0, 7, 0
	.byte 0, 0, 0, 0
piece_7c:
	.byte 0, 0, 0, 0
	.byte 0, 0, 7, 0
	.byte 0, 7, 7, 7
	.byte 0, 0, 0, 0
piece_7d:
	.byte 0, 0, 0, 0
	.byte 0, 7, 0, 0
	.byte 0, 7, 7, 0
	.byte 0, 7, 0, 0
# }}}

# }}}

	.text
	.globl main

main: # {{{
	addi $sp, $sp, -4
	sw $ra, ($sp)

# {{{
	# get some entropy for our random number generator
	la $a0, str_seed
	li $v0, 4 # print_string
	syscall

	la $a0, rc4_key
	li $a1, 256
	li $v0, 8 # read_string
	syscall

	jal rc4_init

	# set up game grid and line counter
	jal grid_init
	sw $zero, lines

	# initialise the current and next pieces
	jal piece_new
	jal piece_new
	jal game

	# if we get here, then time to go home
	la $a0, str_game_over
	li $v0, 4 # print_string
	syscall
# }}}

	lw $ra, ($sp)
	addi $sp, $sp, 4
	jr $ra
# }}}

itoa: # a0: dst, a1: n, v0: address of terminating NUL {{{
	addi $sp, $sp, -4
	sw $ra, 0($sp)

	li $t0, 0
	li $t1, 10
itoa_loop:
		div $a1, $t1
		mflo $a1
		mfhi $t2
		addi $t2, $t2, '0'
		sb $t2, ($a0)
		addi $a0, $a0, 1

	addi $t0, $t0, 1
	bne $a1, $zero, itoa_loop

	sb $zero, ($a0)
	move $v0, $a0

	addi $a1, $a0, -1
	sub $a0, $a0, $t0
	j itoa_rev_cond
itoa_rev_loop:
		lbu $t0, ($a0)
		lbu $t1, ($a1)
		sb $t0, ($a1)
		sb $t1, ($a0)

		addi $a0, $a0, 1
		addi $a1, $a1, -1
itoa_rev_cond:
	blt $a0, $a1, itoa_rev_loop

	lw $ra, 0($sp)
	addi $sp, $sp, 4
	jr $ra
# }}}

strcpy: # a0: dst, a1: src, v0: address of terminating NUL {{{

strcpy_loop:

		lbu $t0, ($a1)
		sb $t0, ($a0)
		addi $a0, $a0, 1
		addi $a1, $a1, 1

	bne $t0, $zero, strcpy_loop

	addi $v0, $a0, -1 # go back to the NUL byte

	jr $ra
# }}}

memcpy4: # a0: dst, a1: src, a2: bytes {{{
	li $t0, 0
	j memcpy4_cond
memcpy4_loop:

		lw $t1, ($a1)
		sw $t1, ($a0)
		addi $a0, $a0, 4
		addi $a1, $a1, 4

	addi $t0, $t0, 4
memcpy4_cond:
	blt $t0, $a2, memcpy4_loop

	jr $ra
# }}}

piece_rot: # a0: rot {{{
	addi $sp, $sp, -8
	sw $ra, 0($sp)
	sw $s0, 4($sp)

	lw $t0, piece_current

	andi $t1, $t0, 0xfffc
	add $t0, $t0, $a0
	andi $t0, $t0, 0x03
	add $s0, $t1, $t0

	lw $a0, piece_pos
	move $a1, $s0
	jal grid_hit

	bne $v0, $zero, piece_rot_hit
		sw $s0, piece_current
piece_rot_hit:

	lw $ra, 0($sp)
	lw $s0, 4($sp)
	addi $sp, $sp, 8
	jr $ra
# }}}

piece_mov: # a0: offset {{{
	addi $sp, $sp, -8
	sw $ra, 0($sp)
	sw $s0, 4($sp)

	lw $t0, piece_pos
	add $s0, $t0, $a0

	move $a0, $s0
	lw $a1, piece_current
	jal grid_hit

	bne $v0, $zero, piece_mov_hit
		la $t0, piece_pos
		sw $s0, ($t0)
piece_mov_hit:

	lw $ra, 0($sp)
	lw $s0, 4($sp)
	addi $sp, $sp, 8
	jr $ra
# }}}

piece_drop: # v0: 0 - ok, 1 - drop, 2 - game over {{{
	addi $sp, $sp, -8
	sw $ra, 0($sp)
	sw $s0, 4($sp)

	lw $a0, piece_pos
	lw $a1, piece_current

	addi $a0, $a0, 12
	move $s0, $a0
	jal grid_hit

	bne $v0, $zero, piece_drop_hit
		la $a0, piece_pos
		sw $s0, ($a0)
		# li $v0, 0
	j piece_drop_miss
piece_drop_hit:

		la $a0, grid
		jal grid_place

		jal piece_new

		lw $a0, piece_pos
		lw $a1, piece_current
		jal grid_hit

		add $v0, $v0, 1

piece_drop_miss:

	lw $ra, 0($sp)
	lw $s0, 4($sp)
	addi $sp, $sp, 8
	jr $ra
# }}}

piece_new: # {{{
	addi $sp, $sp, -4
	sw $ra, 0($sp)

	jal rc4_gen
	remu $v0, $v0, 7
	addi $v0, $v0, 1
	sw $v0, piece_pos

	jal rc4_gen
	remu $v0, $v0, 28
	lw $v1, piece_next
	sw $v0, piece_next
	sw $v1, piece_current

	lw $ra, 0($sp)
	addi $sp, $sp, 4
	jr $ra
# }}}

grid_init: # {{{

	# li $t0, 0x80000000 would be endian-specific

	lw $t0, grid_left # left boundary
	li $t1, 0
	lw $t2, grid_right # right boundary

	li $t3, 0x08080808 # bottom boundary

	la $a0, grid
	li $t4, 0
grid_init_loop:
		sw $t0, 0($a0)
		sw $t1, 4($a0)
		sw $t2, 8($a0)
		addi $a0, $a0, 12
	addi $t4, $t4, 1
	blt $t4, 20, grid_init_loop

	sw $t3, 0($a0)
	sw $t3, 4($a0)
	sw $t3, 8($a0)

	jr $ra
# }}}

grid_hit: # a0: pos, a1: piece, v0: 0 if clear {{{
	addi $sp, $sp, -4
	sw $ra, 0($sp)

	la $t0, grid
	add $a0, $t0, $a0

	la $t0, pieces_start
	sll $a1, $a1, 4
	add $a1, $t0, $a1
	
	li $t0, 0
grid_hit_row:

		li $t1, 0
grid_hit_col:

			lbu $t2, ($a0)
			lbu $t3, ($a1)

			beq $t2, $zero, grid_hit_next
			beq $t3, $zero, grid_hit_next
				li $v0, 1
				j grid_hit_exit
grid_hit_next:

			addi $a0, $a0, 1
			addi $a1, $a1, 1

		addi $t1, $t1, 1
		blt $t1, 4, grid_hit_col

		addi $a0, $a0, 8

	addi $t0, $t0, 1
	blt $t0, 4, grid_hit_row

	move $v0, $zero

grid_hit_exit:

	lw $ra, 0($sp)
	addi $sp, $sp, 4
	jr $ra
# }}}

grid_place: # a0: grid {{{
	addi $sp, $sp, -4
	sw $ra, 0($sp)

	la $t0, piece_pos
	lw $t0, ($t0)
	add $a0, $a0, $t0

	la $t0, piece_current
	la $a1, pieces_start
	lw $t0, ($t0)
	sll $t0, $t0, 4
	add $a1, $a1, $t0

	li $t0, 0
grid_place_row:

		ulw $t1, ($a0)
		lw $t2, ($a1)
		or $t1, $t1, $t2
		usw $t1, ($a0)

		addi $a0, $a0, 12
		addi $a1, $a1, 4

	addi $t0, $t0, 1
	blt $t0, 4, grid_place_row

	lw $ra, 0($sp)
	addi $sp, $sp, 4
	jr $ra
# }}}

grid_render: # a0: screen start address, v0: ptr to bottom of screen so far {{{
	addi $sp, $sp, -8
	sw $ra, 0($sp)
	sw $a0, 4($sp)

	la $a0, grid_temp
	la $a1, grid
	li $a2, 252
	jal memcpy4

	la $a0, grid_temp
	jal grid_place

	lw $a0, 4($sp)
	la $a1, grid_temp
	la $a2, piece_render_lut
	li $t0, 0 # row counter
grid_render_row:

		li $t1, 0 # column counter
grid_render_col:

			lbu $a3, ($a1)
			add $a3, $a2, $a3
			lbu $a3, ($a3)
			sb  $a3, ($a0)

			addi $a0, $a0, 1
			addi $a1, $a1, 1

		addi $t1, $t1, 1
		blt $t1, 12, grid_render_col

		lbu $a3, 9($a2)
		sb  $a3, ($a0)
		addi $a0, $a0, 1

	addi $t0, $t0, 1
	blt $t0, 21, grid_render_row

	sb $zero, ($a0)
	move $v0, $a0

	lw $ra, 0($sp)
	addi $sp, $sp, 8
	jr $ra
# }}}

grid_lines: # v0: lines {{{
	addi $sp, $sp, -4
	sw $ra, 0($sp)

	li $v0, 0

	la $a0, grid
	add $a0, $a0, 228 # dst: 252 - 24
	move $a1, $a0 # src

	li $t0, 0
grid_lines_row:

		la $a2, grid
		blt $a1, $a2, grid_lines_empty
			lw $t2, 0($a1)
			lw $t3, 4($a1)
			lw $t4, 8($a1)
		j grid_lines_copy_end
grid_lines_empty:
			lw $t2, grid_left
			li $t3, 0
			lw $t4, grid_right
grid_lines_copy_end:

		sw $t2, 0($a0)
		sw $t3, 4($a0)
		sw $t4, 8($a0)

		addi $a2, $a0, 1
		li $t1, 0
		li $t2, 1
grid_lines_col:
			lbu $t3, ($a2)
			bne $t3, $zero, grid_lines_filled
				move $t2, $zero
				j grid_lines_next
grid_lines_filled:
			addi $a2, $a2, 1

		addi $t1, $t1, 1
		blt $t1, 10, grid_lines_col

		addi $v0, $v0, 1

grid_lines_next:

		bne $t2, $zero, grid_lines_skip
			addi $a0, $a0, -12
grid_lines_skip:

		addi $a1, $a1, -12

	addi $t0, $t0, 1
	blt $t0, 20, grid_lines_row

	lw $ra, 0($sp)
	addi $sp, $sp, 4
	jr $ra
# }}}

key_poll: # v0: char, 0 if none {{{
	lw $v0, 0xffff0000
	sll $v0, $v0, 31
	bltz $v0, key_poll_pending
		move $v0, $zero
		jr $ra
key_poll_pending:
	lw $v0, 0xffff0004

	jr $ra
# }}}

game: # {{{
	addi $sp, $sp, -8
	sw $ra, 0($sp)
	sw $s0, 4($sp)

# {{{
game_next:
	li $s0, 0 # rather primitive delay mechanism

game_loop:

# {{{ redraw the screen
	la $a0, screen
	jal grid_render

	move $a0, $v0
	la $a1, str_status
	jal strcpy

	move $a0, $v0
	lw $a1, lines
	jal itoa

	move $a0, $v0
	la $a1, str_info
	jal strcpy

	la $a0, screen
	li $v0, 4 # print_string
	syscall
# }}}

# {{{ poll for user input
game_poll:
		jal key_poll

		bne $v0, 'i', game_rotl_skip
			li $a0, -1
			jal piece_rot
			j game_loop
game_rotl_skip:

		bne $v0, 'k', game_rotr_skip
			li $a0, 1
			jal piece_rot
			j game_loop
game_rotr_skip:

		bne $v0, 'j', game_movl_skip
			li $a0, -1
			jal piece_mov
			j game_loop
game_movl_skip:

		bne $v0, 'l', game_movr_skip
			li $a0, 1
			jal piece_mov
			j game_loop
game_movr_skip:

		beq $v0, ' ', game_drop

	addi $s0, $s0, 1
	blt $s0, 16384, game_poll
# }}}

	# fallthrough means time's up

# {{{ move the piece down one row
game_drop:
	jal piece_drop
	beq $v0, 2, game_over
	beq $v0, $zero, game_next

	# remove any full lines in the grid
	jal grid_lines
	lw $t0, lines
	add $t0, $t0, $v0
	sw $t0, lines
# }}}

	j game_next

game_over:
# }}}

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


# }}}

rc4_init: # {{{

	la $a0, rc4_pool
	li $t0, 0
rc4_init_id_loop:
		sb $t0, ($a0)
		addi $a0, $a0, 1
	addi $t0, $t0, 1
	blt $t0, 256, rc4_init_id_loop

	la $a0, rc4_pool
	la $a1, rc4_key
	li $t0, 0 # i
	li $t1, 0 # j
rc4_init_mix_loop:
		lbu $t3, ($a1) # key[i]
		bne $t3, $zero, rc4_init_key_next
			la $a1, rc4_key
			lbu $t3, ($a1) # key[i]
rc4_init_key_next:

		# $t2 = s[i]
		lbu $t2, ($a0) # s[i]

		# j = (j + s[i] + key[i]) & 0xff
		add $t1, $t1, $t2
		add $t1, $t1, $t3
		andi $t1, $t1, 0xff

		# $t3 = s[j]
		la $a2, rc4_pool
		add $a2, $a2, $t1
		lbu $t3, ($a2)

		# swap s[i] and s[j]
		sb $t2, ($a2)
		sb $t3, ($a0)

		# (nothing to see here) move along
		addi $a0, $a0, 1
		addi $a1, $a1, 1

	addi $t0, $t0, 1
	blt $t0, 256, rc4_init_mix_loop

	sw $zero, rc4_i
	sw $zero, rc4_j

	jr $ra
# }}}

rc4_gen: # v0: random byte {{{
	la $a0, rc4_i
	la $a1, rc4_j
	lw $t0, ($a0)
	lw $t1, ($a1)

	addi $t0, $t0, 1
	andi $t0, $t0, 0xff
	sw $t0, ($a0)
	la $a0, rc4_pool
	add $a0, $a0, $t0
	lbu $t0, ($a0)
	add $t1, $t1, $t0
	andi $t1, $t1, 0xff
	sw $t1, ($a1)

	la $a1, rc4_pool
	add $a1, $a1, $t1
	lbu $t1, ($a1)

	sb $t0, ($a1)
	sb $t1, ($a0)

	add $t0, $t0, $t1
	andi $t0, $t0, 0xff
	la $a0, rc4_pool
	add $a0, $a0, $t0
	lbu $v0, ($a0)

	jr $ra
# }}}

# vim: foldmethod=marker commentstring=#\ %s: