###############################################################################
# ECE 15B - Project
# FFT - Fast Fourier Transform
# Created by Isaac Liu
# 
# This program takes input signals which are stored in memory, and performs 
# Fast Fourier Transform to the signal, and stores the results back to the 
# original memory location.
#
# turnin.s
# copy your code in the appropriate functions
###############################################################################

	.data
nline:  .asciiz "\n"				#Define new line string
space:  .asciiz " "				#Define space string
dot:    .asciiz "."				#Define dot string
neg_sign:    .asciiz "-"			#Define negative string

sigreal: .space 256
sigimagine: .word 0, 0, 0, 0, 0, 0, 0, 0	#Input imaginary signal
		.word 0, 0, 0, 0, 0, 0, 0, 0	#Input imaginary signal

tempreal:  .space 256				#Space for temporary real signal
tempimagine: .space 256				#space for temporary imagniary signal

#The following is a lookup table for the sin and cos values
lookup:      .word 0x0, 0x00000477, 0x000008EF, 0x00000D65, 0x000011DB, 0x0000164F, 0x00001AC2  #6
	.word 0x00001F32, 0x000023A0, 0x0000280C, 0x00002C74, 0x000030D8, 0x00003539, 0x00003996 #13 
	.word 0x00003DEE, 0x00004241, 0x00004690, 0x00004AD8, 0x00004F1B, 0x00005358, 0x0000578E #20
	.word 0x00005BBE, 0x00005FE6, 0x00006406, 0x0000681F, 0x00006C30, 0x00007039, 0x00007438 #27
	.word 0x0000782F, 0x00007C1C, 0x00008000, 0x000083D9, 0x000087A8, 0x00008B6D, 0x00008F27 #34
	.word 0x000092D5, 0x00009679, 0x00009A10, 0x00009D9B, 0x0000A11B, 0x0000A48D, 0x0000A7F3 #41
	.word 0x0000AB4C, 0x0000AE97, 0x0000B1D5, 0x0000B504, 0x0000B26A, 0x0000BB39, 0x0000BE3E #48
	.word 0x0000C134, 0x0000C41B, 0x0000C6F3, 0x0000C9BB, 0x0000CC73, 0x0000CF1B, 0x0000D1B3 #55
	.word 0x0000D43B, 0x0000D6B3, 0x0000D919, 0x0000DB6F, 0x0000DDB3, 0x0000DFE7, 0x0000E208 #62
	.word 0x0000E419, 0x0000E617, 0x0000E803, 0x0000E9DE, 0x0000EBA6, 0x0000ED5B, 0x0000EEFF #69
	.word 0x0000F08F, 0x0000F20D, 0x0000F378, 0x0000F4D0, 0x0000F615, 0x0000F746, 0x0000F865 #76
	.word 0x0000F970, 0x0000FA67, 0x0000FB4B, 0x0000FC1C, 0x0000FCD9, 0x0000FD82, 0x0000FE17 #83
	.word 0x0000FE98, 0x0000FF06, 0x0000FF60, 0x0000FFA6, 0x0000FFD8, 0x0000FFF6, 0x00010000 #90 

	.text
	.globl main
main:				
	#Main function
	addi $sp, $sp, -4
	sw $ra 0($sp)
	la $a0, sigreal
	addi $t1, $a0, 0

	li $v0, 5
	syscall
	addi $a2, $v0, 0
	li $v0, 5
	syscall
	addi $a3, $v0, 0
	li $t0, 0

loadloop:	
	li $v0, 5
	syscall
	sll $v0, $v0, 16
	sw $v0, 0($t1)
	addi $t0, $t0, 1
	addi $t1, $t1, 4
	bne $t0, $a2, loadloop

	la $a1, sigimagine
	jal FFT_prep
	jal FFT
	#PRINTING
	la $a0, sigreal
	la $a1, sigimagine
	jal print
	lw $ra 0($sp)
	addi $sp, $sp, 4
	jr $ra
	

#################################################################################
# FFT_prep: The function that reorders the signal to prepare for FFT
# arguments: $a0 - address of the signal real coefficients
# 		 $a1 - address of the signal imaginary coefficients	
#		 $a2 - number of elements in the signal (must be power of 2)
#		 $a3 - log 2 of $a2 (or: 2^$a3 = $a2)
# returns: The signal stored in original address ordered ready for FFT
#
##################################################################################
# -----------------Copy and paste your FFT reorder code here------------------#

FFT_prep:

		jr $ra
#################################################################################
# FFT: The function that does the math part for FFT
# arguments: $a0 - address of the signal real coefficients
# 		 $a1 - address of the signal imaginary coefficients	
#		 $a2 - number of elements in the signal (must be power of 2)
#		 $a3 - log 2 of $a2 (or: 2^$a3 = $a2)
# returns: The signal stored in original address after FFT
#	
#################################################################################
# -----------------Copy and paste your FFT code here------------------#
FFT:
		jr $ra
	



#################################################################################
# Sin/Cos: 
#	Using the lookup table embedded in memory to determine the value of sin or cos
# arguments:
#	$a0 - the parameter of sin/cose 
# returns: 
#	$v0 - The value of sin/cos
#################################################################################	
cos:
	li $t9, -1
	mul $a0, $a0, $t9
	addi $a0, $a0, -90
cos_check:	
	bgtz $a0, cos_skip
	addi $a0, $a0, 360
	j cos_check
cos_skip:	
	j sin_check	
		
sin_prep:
	li $t9, -1
	mul $a0, $a0, $t9
sin_check:
	slti $t9, $a0, 360
	bgtz $t9, sin
	addi $a0, $a0, -360
	j sin_check
sin:
	li $t8, 360
	slti $t9, $a0, 90
	bgtz $t9, endsin_neg
	slti $t9, $a0, 180
	bgtz $t9, sin_90_180
	slti $t9, $a0, 270
	bgtz $t9, sin_180_270
	sub $a0, $t8, $a0
	j endsin_pos
sin_180_270:
	addi $a0, $a0, -180
	j endsin_pos
sin_90_180:
	li $t8, 180
	sub $a0, $t8, $a0
endsin_neg:
	la $t8, lookup
	sll $a0, $a0, 2
	add $t8, $a0, $t8
	lw $v0, 0($t8)
	li $t8, -1
	mul $v0, $v0, -1
	jr $ra	
endsin_pos:
	la $t8, lookup
	sll $a0, $a0, 2
	add $t8, $a0, $t8
	lw $v0, 0($t8)
	jr $ra

	
#################################################################################
# mult_unreal: 
#	This function multiplies two unreal numbers
# 
# Example:	
# 	(a+bi)(c+di)=e+fi
# 
# Arguments:  
#	$a0 - a
#	$a1 - b
#	$a2 - c
# 	$a3 - d
# 
# Returns: 
#	$v0 - real coefficient of the result - e
#	$v1 - imaginary coefficient of the result - f	
#
#################################################################################	

mult_unreal:
	mult $a0, $a2
	mfhi $t9
	li $t8, 0
	or $v0, $t9, $t8
	sll $v0, $v0, 16
	mflo $t9
	li $t8, 0
	srl $t9, $t9, 16
	or $t9, $t8, $t9
	or $v0, $t9, $v0
	mult $a1, $a3
	mfhi $t9
	li $t8, 0
	or $v1, $t9, $t8
	sll $v1, $v1, 16
	mflo $t9
	li $t8, 0
	srl $t9, $t9, 16
	or $t9, $t8, $t9
	or $v1, $t9, $v1
	sub $v0, $v0, $v1
	mult $a0, $a3
	mfhi $t9
	li $t8, 0
	or $v1, $t9, $t8
	sll $v1, $v1, 16
	mflo $t9
	li $t8, 0
	srl $t9, $t9, 16
	or $t9, $t8, $t9
	or $v1, $t9, $v1
	mult $a1, $a2
	mfhi $t9
	li $t8, 0
	or $t7, $t9, $t8
	sll $t7, $t7, 16
	mflo $t9
	li $t8, 0
	srl $t9, $t9, 16
	or $t9, $t8, $t9
	or $t7, $t9, $t7
	add $v1, $v1, $t7
	jr $ra	

#################################################################################
# print: 
#	This function prints out the input signal onto the console.
# arguments: 
#	$a0 - Real signal coefficient address
#	$a1 - Imaginary signal coefficient address
#	$a2 - number of elements
# returns: 
#	Nothing, it prints out the signal onto the console.
#
#################################################################################		
print:
	li $t3, 0
	addi $t9, $a0, 0
	addi $t8, $a1, 0
	sll $a2, $a2, 2
print_loop:
	add $t7, $t3, $t9
	lw $t1, 0($t7)
	bgez $t1, skip_neg_re
	la $a0, neg_sign
	li $v0, 4
	syscall
	li $t6, -1
	mul $t1, $t6, $t1
skip_neg_re:	
	sra $a0, $t1, 16
	li $v0, 1
	syscall
	la $a0, dot
	li $v0, 4
	syscall
	sll $t1, $t1, 16
	srl $t1, $t1, 16
	li $t2, 1000
	mul $t1, $t1, $t2
	li $t2, 65536
	div $a0, $t1, $t2
	li $v0, 1
 	syscall
	la $a0, space
	li $v0, 4
	syscall
	
	add $t7, $t3, $t8
	lw $t1, 0($t7)
	bgez $t1, skip_neg_im
	la $a0, neg_sign
	li $v0, 4
	syscall
	li $t6, -1
	mul $t1, $t6, $t1
skip_neg_im:
	sra $a0, $t1, 16
	li $v0, 1
	syscall
	la $a0, dot
	li $v0, 4
	syscall
	sll $t1, $t1, 16
	srl $t1, $t1, 16
	li $t2, 1000
	mul $t1, $t1, $t2
	li $t2, 65536
	div $a0, $t1, $t2
	li $v0, 1
 	syscall
	la $a0, nline
	li $v0, 4
	syscall
	
	addi $t3, $t3, 4
	bne $a2, $t3, print_loop
	jr $ra