# zoran graonic 260110350
# -- COMP 273  -- Dynamic Memory Drivers --

# ---- void *malloc(int number_of_bytes) -------
#	When malloc is called it first checks the Allocation Table. This table contains
#	three entries: address, used flag, size in bytes. This table records the status of all
#	the blocks of memory allocated when malloc() is called. If there is en entry that
#	has been freed (ie. Its used flag is false) and whose size in bytes is less than or
#	equal to the number_of_bytes, then malloc returns that address with all its size in
#	bytes (does not update it with number_of_bytes). If there is nothing available in
#	the table then malloc grabs the next available space on the head. The Heap is
#	implemented as a simple 1D array of memory with a maximum size N. A pointer
#	called TOP keeps track of the next available space on the heap. If there is no
#	more space then malloc returns the address 0 (zero). If there is space then TOP is
#	updated and an entry is added to the Allocation Table and the address is returned by malloc, in register $A0.

# ---- void free(void *ptr)  ------
#	When free is called it first verifies if the address exists in the Allocation Table. 
#	If it does not, the program just ignores the call and returns early without an error
#	message. If the address exists in the Allocation Table then the used flag is set to false, nothing else occurs.

# ----- Exit on STOP input -----
# After the user enters STOP the program should display on the screen the contents of
# the Allocation Table and the contents of the Heap.


	
	.text
	#.align 2
	.globl main


	
main: 	
	# save the start address of The Heap into "top"
	la $t0,heap
	la $t1,top
	sw $t0,($t1)
	# set number of the rows to zero
	la $t0,row
						# addi $t1,$zero,2  sw $t1,($t0)  set the nmr of rows test****
	sw $zero,($t0)

 #------main the first STOP --------------

main1:	# Ask for a string input
	li $v0, 4 	# load appropriate system call code into register $v0;
			# code for printing string is 4
	la $a0, str1 	# load address of string to be printed into $a0
	syscall		# call operating system
	
	# Save the string from input
	li $v0, 8 	# load appropriate system call code into register $v0;
			# code for READ string is 8
	la $a0,temp     #buffer
	addi $a1,1024	#size
	syscall
        
	#-----  determine the size and sum of the inputed string  - input $a0 adrress , return $v0-size, $v1-sum of string in ASCII
	la $a0,temp	# function - sizeS(address)
	jal sizeS   	# call function sizeS
	
	#---- Exit on "stop:--------
	addi $t0,$v1,-464       # 464 - sum of the string "stop"
	beq $t0,$zero,main2    # if there is no "stop" save on the heap and ask for the new string
        
	# -----  call malloc function -input $a0-size,$a1-sum -----return free address of the heap in $V0----
		move $a0,$v0  # size of string	               
		move $a1,$v1  # sum of characters(ASCII)
		jal malloc

	# -----  STRCPY----copy string from temp to the heap --input - address in the heap where temp should be copied
		move $a0,$v0  # size of string
        	jal strcpy
	j main1  # next string

main2:	
	#----------PRINT ALLOCATION Table and HEAP--------

	jal prALLh
	 
#------main the second STOP --------------

main3:	# Ask for a string input
	li $v0, 4 	# load appropriate system call code into register $v0;
			# code for printing string is 4
	la $a0, str1 	# load address of string to be printed into $a0
	syscall		# call operating system
	
	# Save the from input
	li $v0, 8 	# load appropriate system call code into register $v0;
			# code for READ string is 8
	la $a0,temp     #buffer
	addi $a1,1024	#size
	syscall
        
	#-----  determine the size and sum of the inputed string - input $a0 adrress , return $v0-size, $v1-sum of string in ASCII
	la $a0,temp	
	jal sizeS   	# get size of string	  		
	
	#---- Exit on "stop:--------
	addi $t0,$v1,-464       # 464 - sum of the string "stop"
	beq $t0,$zero,main4    # if there is no "stop" save on the heap and ask for the new string
        
	# -----  findA()   input $a0- sum-----return free address of the heap in $V0 or 0 if there is no address----
		# if the two strings are identical than the "sum" of character in ASCII are the same
		# we have fourth col in allocation table which keeps the value of sum (Ex: stop = 464(in ASCII))
		
		move $a0,$v1  # load sum as an input
		jal findA     # call function
		beq $v0,$zero,main5    # if string is not found $v0=0 then print "Not Found", otherwise free the heap
	
	# -----  free()  -  input $a0-address
		move $a0,$v0   # free the address,set the flag to zero
		jal free
	
	j main3
main5:			li $v0, 4 	# load appropriate system call code into register $v0;
					# code for printing string is 4
			la $a0, str10	# load address of string to be printed into $a0
			syscall		# call operating system


	j main3
main4:	
	#----------PRINT ALLOCATION Table and HEAP--------

	jal prALLh




	#  -- call Exit --
	jal Exit        


##*************************FUNCTIONS*****************************************

# --- SIZE OF THE STRING (number of character + end of line + zero)
sizeS:	# ---- input $a0 string address 
	# ---- output size of string $v0, and sum of character(ASCII int values) in the str $v1 (to compare strings)
	# --reg in use $t1,$t2 and $t3
	
	move $t3,$zero
	move $t4,$zero
	move $t1,$a0            # load the start address
sizeS1:	lb $t2,($t1)		# load byte
	addi $t1,$t1,1  	# next byte address		
	add $t3,$t3,$t2  	# sum of bytes in ascii	
	bne $t2,$zero,sizeS1    # brunch if the char is not null char
	sub  $v0,$t1,$a0  	# size of string including end of line and null-char
	move $v1,$t3   		# TOTAL sum of bytes in ascii 
	
	jr $ra		

#-----------MALLOC----------- input $a0-size  and $a1-sum,output the heap address
malloc:
	la $t0,row
	lw $t1,($t0)  # number of rows in table
	beq $t1,$zero,mall1  # allocation table is empty
	
	# load addresses from  allocation table or
	la $t0,addr
	la $t2,flag
	la $t3,size
	la $t5,sum
mall2:  # Check if there is a space in table
		lw $t4,($t3)   		# load  size of the row	
		slt $t4,$t4,$a0  	#   zero if $a0=<$t4(Size of allocated block - table row size), one if $a0>$t4
		bne $t4,$zero,mall3  	# if there are not the size of the raw greater or equl to the $a0,then check the next
		lw $t4,($t2)   		# load  flag of the row		
		bne $t4,$zero,mall3  	# if flage is not zero check next
		  # free space found in the table
			addi $t4,$t4,1  # flag is now 1
			lw $t4,($t2)    # set flag to the one
			lw $v0,($t0)
			sw $a1,($t5)    # update the sum of existing row (heap reserved block)

			j mallEx 		#return if the table has free space

mall3:	addi $t1,$t1,-1 # Counter for loop
	
	# load next addresses of table's columns
	add $t0,$t0,4
	add $t2,$t2,4
	add $t3,$t3,4
	add $t5,$t5,4
        bne $t1,$zero,mall2




mall1:  # check for max size overlapping (if new address is out of the range return address=zero)
		move $v0,$zero       # set return address to zero
		la $t0,top
		lw $t1,($t0)	     # load the address of the pointer top
		add $t1,$t1,$a0      # address of the top + size = new top address
		la $t2,heap	     # start address of the heap
		la $t3,N	     # address of N
		lw $t4,($t3)	     # size of the heap
		add $t2,$t2,$t4	     #  end of the heap
		slt $t5,$t2,$t1	     #   zero $t2(End of heap)>=$t0(new top address)
		bne $t5,$zero,mallEx
						

	# when there is no space in table or table is empty  
	# RETURN top and add a new row in the table		

	# increase num of rows
	la $t0,row
	lw $t1,($t0)
	addi $t1,$t1,1
	sw $t1,($t0)
        		
		# address offset
		addi $t1,$t1,-1
		sll  $t1,$t1,2   # (4 times number of the row) + a start address {adr,flag,size,sum}
	
	#save new address
	la $t2,addr
	add $t2,$t2,$t1  # address + offset = start position of the new row
        la $t3,top
	lw $t4,($t3)   #load pointer from top
	sw $t4,($t2)
	

	#set flag to 1
	la $t2,flag
	add $t2,$t2,$t1  # address + offset = start position of the new row
        addi $t3,$zero,1    
	sw $t3,($t2)
	
	#set new size
	la $t2,size
	add $t2,$t2,$t1  # address + offset = start position of the new row
        move $t3,$a0
	sw $t3,($t2)

	#set the sum
	la $t2,sum
	add $t2,$t2,$t1  # address + offset = start position of the new row
        move $t3,$a1
	sw $t3,($t2)
	

	# return the addresse
	la $t0,top
	lw $v0,($t0)
		
	
	#set the new top address
	la $t0,top
	add $t1,$v0,$a0      # address of the top + size = new top address
	sw  $t1,($t0)

mallEx:	jr $ra




#-----------STRCPY ---STRING COPY---input $a0 address in the heap where temp should be 
strcpy:
		move $t0,$a0  	# address in the heap
		la $t1,temp   	# start address of the string which we should copy into heap
strcpy1:	lb $t2,($t1)
		sb $t2,($t0)  	#save all char includin zero	
		beq $t2,$zero,strcpyEx		
		addi $t0,$t0,1	#increment addresses
		addi $t1,$t1,1
		j strcpy1
		

strcpyEx: jr $ra

#----------PRINT ALLOCATION Table and HEAP--------

prALLh:
	# --- print allocation table----		
	
	la $t0,row
	lw $t1,($t0)  # number of the rows ion the Allocation table
			li $v0, 1 	# load appropriate system call code into register $v0;
					# code for printing string is 4
			move $a0,$t1	# load address of string to be printed into $a0
	  		syscall		# call operating system
	beq $t1,$zero,prALLhEx	        # if The All table is empty exit the function

	# $t1 holds number of the rows
	
				#Allocation table
				li $v0, 4 	# load appropriate system call code into register $v0;
						# code for printing string is 4
				la $a0, str4	# load address of string to be printed into $a0
				syscall		# call operating system

	la $t0,addr
	la $t2,flag
	la $t3,size
	la $t4,sum
prALLh1:
	#print the row in Allocation table:
				##print new line and Adr:
				li $v0, 4 	# load appropriate system call code into register $v0;
						# code for printing string is 4
				la $a0, str9	# load address of string to be printed into $a0
				syscall		# call operating system	
			 li $v0, 1 	# load appropriate system call code into register $v0;
					# code for printing int is 1
			 lw $a0, ($t0)	# load integer to be printed into $a0
			 syscall	# call operating system
				#print new line and Flag:
				li $v0, 4 	# load appropriate system call code into register $v0;
						# code for printing string is 4
				la $a0, str8	# load address of string to be printed into $a0
				syscall		# call operating system	

			 li $v0, 1 	# load appropriate system call code into register $v0;
					# code for printing int is 1
			 lw $a0, ($t2)	# load integer to be printed into $a0
			 syscall	# call operating system
				#print new line and Size:
				li $v0, 4 	# load appropriate system call code into register $v0;
						# code for printing string is 4
				la $a0, str7	# load address of string to be printed into $a0
				syscall		# call operating system
			 
			 li $v0, 1 	# load appropriate system call code into register $v0;
					# code for printing int is 1
			 lw $a0, ($t3)	# load integer to be printed into $a0
			 syscall

				# separate new record --------------------
				li $v0, 4 	# load appropriate system call code into register $v0;
						# code for printing string is 4
				la $a0, str5	# load address of string to be printed into $a0
				syscall		# call operating system



	addi $t1,$t1,-1	
	add $t0,$t0,4
	add $t2,$t2,4
	add $t3,$t3,4
	add $t4,$t4,4
        bne $t1,$zero,prALLh1

prALLhEx:	
	# -- print heap ---
	la $t0,N
	lw $t1,($t0)	#  counter 
	la $t0,heap    	# get start address of the heap
			#  print title "HEAP"
			li $v0, 4 	# load appropriate system call code into register $v0;
					# code for printing string is 4
			la $a0,str3	# load address of the HEAP to be printed into $a0
			syscall		# call operating system

prAllh2:
	lb $t3,($t0)
	li $v0, 11 	# load appropriate system call code into register $v0;
			# code for printing char is 11
	move $a0,$t3	# load address of char into $a0
	syscall		# call operating system
	
	addi $t1,$t1,-1   #dec counter
	add  $t0,$t0,1	  #inc address
	bne $t1,$zero,prAllh2
	jr $ra



# -----  findA()   input $a0- sum-----return free address of the heap in $V0 or 0 if there is no address----
findA:	
	move $v0,$zero    	# set return to zero
	la $t3,addr		# address of the address row in Alloc table
	la $t0,row		# address of the  sum row
	lw $t1,($t0)  		# number of the rows in the allocation table
	beq $t1,$zero,findAEx	# if The All table is empty exit the function
	la $t0,sum		# address of the sum
findA1: 
	
	lw $t2,($t0)		#load value of the sum
	sub $t2,$t2,$a0		# if two strings are identical than the sum of character in ASCII are the same
	beq $t2,$zero,findA2
	
	addi $t1,$t1,-1		# counter -1
	add $t0,$t0,4		# address of the next sum row
        add $t3,$t3,4		# address of the next address row in allocation table
	bne $t1,$zero,findA1    # next row
        j findAEx		# return zero
findA2:  
	lw $v0,($t3)		# return the heap address(of the string with the same sum) from address row in the Allocation table

findAEx:   jr $ra

# -----  free()  -  input $a0-address which should be free in the Allocation table-------
free:	
	la $t0,row		# address of the  sum row
	lw $t1,($t0)  		# number of the rows in the allocation table
	beq $t1,$zero,freeEx	# if The All table is empty exit the function
	
	la $t0,addr		# address of the address row in Alloc table
	la $t3,flag		# address of the flag row in Alloc table
	la $t4,sum		# address of the sum row in Alloc table
free1:
	lw $t2,($t0)		#load value of the address
	sub $t2,$t2,$a0		# if two addresses are equal = zero
	beq $t2,$zero,free2
	
	addi $t1,$t1,-1		# counter -1
	add $t0,$t0,4		# address of the next address row in allocation table
        add $t3,$t3,4		# address of the next flag row
	add $t4,$t4,4		# address of the next sum row
	bne $t1,$zero,free1     # next row
		
		#  print "Word was NOT freed!"
		li $v0, 4 	# load appropriate system call code into register $v0;
				# code for printing string is 4
		la $a0, str12	# load address of string to be printed into $a0
		syscall		# call operating system
      
	j freeEx
free2:	      
	# -- free the space---
	sw $zero,($t3)	# set flag to zero
	sw $zero,($t4)	# set sum to zero


		#  print "Word was freed!"
		li $v0, 4 	# load appropriate system call code into register $v0;
				# code for printing string is 4
		la $a0, str11	# load address of string to be printed into $a0
		syscall		# call operating system

freeEx:	jr $ra


# --- EXIT---
Exit:
	li $v0,10	 # load appropriate system call code into register $v0;
			 # code for sys exit is 10
	syscall 	 # call operating system


.data
#--------Heap----------------
top:    .space  4
heap:  .space  3072
N:     .word   3072
#-----Allocation Table ------
row:	.space  1024
addr:	.space  1024
flag:	.space  1024
size:	.space  1024
sum:    .space  1024  # additional column for ease search
#-----Temp storage for the string --
temp: 	.space  1024

str1: .asciiz "\nInput the string:[type 'stop' for exit]\n"
str2: .asciiz "\n"
str3: .asciiz "\nHEAP:\n"
str4: .asciiz "\n Allocation Table:\n--------------------\n"
str5: .asciiz "\n--------------------\n"
str6: .asciiz "\nSum:\t"
str7: .asciiz "\nSize:\t"
str8: .asciiz "\nFlage:"
str9: .asciiz "\nAdr:\t"
str10: .asciiz "\nNot found!\n"
str11: .asciiz "\nWord was freed!\n"
str12: .asciiz "\nWord was NOT freed!\n"