###############################################################################
#
#       Computer architecture assignment E1
#
###############################################################################
#
#    Write a subroutine, which pattern1es for given byte pattern from an
#    byte array. 
#
#    The arguments of the subroutine are passed as follows:
#
#    $a0 contains the address of byte array
#    $a1 contains the length of array
#    $a2 contains the address of byte pattern
#    $a3 contains the length of pattern
#
#    Subroutine should not alter the array nor byte pattern.
#
#    The C-prototype of the subroutine is as follows:
#
#    int memmem(void *m1, int size1, void *m2, int size2);
#
#    The subroutine should return in register $v0:
#     1) the address of first match or
#     2) zero, if there were no matches.
#
###############################################################################
#
# Main program to test memmem()
#
    .text
    .globl main
	
main:

# Create a stack frame for main program
    subu    $sp $sp,8
    sw      $ra 4($sp)  # return address
    sw      $fp 0($sp)  # old frame pointer
    addu    $fp $sp,8   # update frame pointer

#
# Test data
#
    .data
array1:		.byte    0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15
pattern1:	.byte    5,6,7,8
pattern2:	.byte    0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15
pattern3:	.byte    0
pattern4:	.byte    0,1,2
pattern5:	.byte    15
pattern6:	.byte    13,14,15
pattern7:	.byte    16,17
pattern8:	.byte    4,5,6,8
array2:		.asciiz  "This is test test string"
pattern9:	.asciiz  "test"
pattern10:	.asciiz  "test string that fails"
pattern11:	.asciiz  "This string is too long!!"
array3:		.byte    7
pattern13:	.byte    7

    .text

#
# Test 1: Search pattern that is found at the middle of the array
#
    la      $a0 array1
    li      $a1 16			# The last number is the size of byte array
    la      $a2 pattern1
    li      $a3 4			# The last number is the size of byte pattern
    jal     memmem

#
# Check result from test 1
#
    la      $t0 array1+5		# The last number is the index where the first occurence should be
    li      $a0 1				# Put test number to register a0
    bne     $v0,$t0 .failure	# Check that the memory address got from memmem and above are the same

	
#
# Test 2: The pattern and the array are the same
#
    la      $a0 array1
    li      $a1 16			# The last number is the size of byte array
    la      $a2 pattern2
    li      $a3 16			# The last number is the size of byte pattern
    jal     memmem

#
# Check result from test 2
#
    la      $t0 array1+0		# The last number is the index where the first occurence should be
    li      $a0 2				# Put test number to register a0
    bne     $v0,$t0 .failure	# Check that the memory address got from memmem and above are the same


#
# Test 3: Search only one byte that is at the beginning of the array
#
    la      $a0 array1
    li      $a1 16			# The last number is the size of byte array
    la      $a2 pattern3
    li      $a3 1			# The last number is the size of byte pattern
    jal     memmem

#
# Check result from test 3
#
    la      $t0 array1+0		# The last number is the index where the first occurence should be
    li      $a0 3				# Put test number to register a0
    bne     $v0,$t0 .failure	# Check that the memory address got from memmem and above are the same


#
# Test 4: Search a three length of byte pattern that begins at the beginning of the array
#
    la      $a0 array1
    li      $a1 16			# The last number is the size of byte array
    la      $a2 pattern4
    li      $a3 3			# The last number is the size of byte pattern
    jal     memmem

#
# Check result from test 4
#
    la      $t0 array1+0		# The last number is the index where the first occurence should be
    li      $a0 4				# Put test number to register a0
    bne     $v0,$t0 .failure	# Check that the memory address got from memmem and above are the same


#
# Test 5: Search a byte that is found at the end of the byte array
#
    la      $a0 array1
    li      $a1 16			# The last number is the size of byte array
    la      $a2 pattern5
    li      $a3 1			# The last number is the size of byte pattern
    jal     memmem

#
# Check result from test 5
#
    la      $t0 array1+15		# The last number is the index where the first occurence should be
    li      $a0 5				# Put test number to register a0
    bne     $v0,$t0 .failure	# Check that the memory address got from memmem and above are the same


#
# Test 6: Search a pattern length of three that is found at the end of the byte array
#
    la      $a0 array1
    li      $a1 16			# The last number is the size of byte array
    la      $a2 pattern6
    li      $a3 3			# The last number is the size of byte pattern
    jal     memmem

#
# Check result from test 6
#
    la      $t0 array1+13		# The last number is the index where the first occurence should be
    li      $a0 6				# Put test number to register a0
    bne     $v0,$t0 .failure	# Check that the memory address got from memmem and above are the same

	
#
# Test 7: Search a pattern that is not found in the array (no pattern's bytes are in array)
#
    la      $a0 array1
    li      $a1 16			# The last number is the size of byte array
    la      $a2 pattern7
    li      $a3 2			# The last number is the size of byte pattern
    jal     memmem

#
# Check result from test 7
#
    li      $a0 7				# Put test number to register a0
    bne     $v0,$zero .failure	# Check that the memory address is zero

	
#
# Test 8: Search a pattern that is not found in the array (some of pattern's bytes are in array)
#
    la      $a0 array1
    li      $a1 16			# The last number is the size of byte array
    la      $a2 pattern8
    li      $a3 4			# The last number is the size of byte pattern
    jal     memmem

#
# Check result from test 8
#
    li      $a0 8				# Put test number to register a0
    bne     $v0,$zero .failure	# Check that the memory address is zero
	

#
# Test 9: Search a pattern that is found two times from the byte array
#
    la      $a0 array2
    li      $a1 24			# The last number is the size of byte array
    la      $a2 pattern9
    li      $a3 4			# The last number is the size of byte pattern
    jal     memmem

#
# Check result from test 9
#
    la      $t0 array2+8		# The last number is the index where the first occurence should be
    li      $a0 9				# Put test number to register a0
    bne     $v0,$t0 .failure	# Check that the memory address got from memmem and above are the same


#
# Test 10: Search a pattern whose beginning is found at the end of
# the array but whose end exceeds beyound the array
#
    la      $a0 array2
    li      $a1 24			# The last number is the size of byte array
    la      $a2 pattern10
    li      $a3 22			# The last number is the size of byte pattern
    jal     memmem

#
# Check result from test 10
#
    li      $a0 10				# Put test number to register a0
    bne     $v0,$zero .failure	# Check that the memory address is zero


#
# Test 11: Search a pattern whose length is more than the byte array's
#
    la      $a0 array2
    li      $a1 24			# The last number is the size of byte array
    la      $a2 pattern11
    li      $a3 25			# The last number is the size of byte pattern
    jal     memmem

#
# Check result from test 11
#
    li      $a0 11				# Put test number to register a0
    bne     $v0,$zero .failure	# Check that the memory address is zero


#
# Test 12: The same as test number 9 but now the size parameters are abnormal
#
    la      $a0 array2
    li      $a1 0			# The last number is the size of byte array
    la      $a2 pattern9
    li      $a3 0			# The last number is the size of byte pattern
    jal     memmem

#
# Check result from test 12
#
    li      $a0 12				# Put test number to register a0
    bne     $v0,$zero .failure	# Check that the memory address is zero


#
# Test 13: Search a pattern from array with size of 1
#
    la      $a0 array3
    li      $a1 1			# The last number is the size of byte array
    la      $a2 pattern13
    li      $a3 1			# The last number is the size of byte pattern
    jal     memmem

#
# Check result from test 13
#
    la      $t0 array3+0		# The last number is the index where the first occurence should be
    li      $a0 13				# Put test number to register a0
    bne     $v0,$t0 .failure	# Check that the memory address got from memmem and above are the same

	
#
# If there is no failure, tell it to user
#
    .data
.ok:    .asciiz "The memmem() passed all tests\n"
    .text
    li      $v0 4
    la      $a0 .ok
    syscall

#
# Exit from test program
#
.exit:
    li      $v0 10
    syscall

#
# Test failed, print what test was failed
#
.failure:
    .data
.fail:     .asciiz " The memmem() failed test "
.newline:  .asciiz "\n"
    .text
    li      $v0 4		# This tells the system to print a string
	move	$t0, $a0	# Copy the test number from a0
    la      $a0 .fail	# Syscall prints that what is at register a0
    syscall
    li      $v0 1		# This tells the system to print an integer
	move	$a0, $t0	# Copy test number back to a0
    syscall
    li      $v0 4
    la      $a0 .newline
    syscall
    j       .exit

###############################################################################
#
# The subroutine memmem
#
    .text
    .globl  memmem
	
memmem: 
    
# First initialize some variables
	li		$t0, 0				# Byte array iterator i = 0
	li		$t1, 0				# Byte pattern iterator j = 0
	move	$v0, $zero			# The memory address v = 0 which is returned
	move	$t2, $a0 			# Memory address of byte table bTable, stored in $a0
	move	$t3, $a2 			# Memory address of byte pattern bPattern, stored in $a2
	
# Check that the size paramaters are reasonable, if (size2<=0 || size1<=0) return 0
	blez	$a1, exit			# Exit if size1 <=0
	blez	$a3, exit			# Exit if size2 <=0

# The beginning of the for loop	
loop:
	bge		$t0, $a1, exit		# For loop's condition: i< size1, so exit loop if (i >= size1)
	
# Exit if the remaining byte pattern is longer than the remaining byte array
	sub		$t4, $a3, $t1		# size2-j
	sub		$t5, $a1, $t0		# size1-i
	bgt		$t4, $t5, exit		# (if (size2-j)>size1-i) return 0
	
	lb 		$t4, 0($t2)			# Load byte value from byte array: *bTable
	lb 		$t5, 0($t3)			# Load byte value from byte pattern: *bPattern

# Increment the array iterator i for the next loop
	addi	$t0, $t0, 1  		# for loop's clause: i++
	
# The condition "if (*bTable != *bPattern)" inside the for loop
	bne 	$t4, $t5, notSame 	# if the byte values are not the same, skip everything till notSame

# The bytes compared above are same (the else clause inside the loop)
	bnez	$v0, skipAddr		# Do the following instruction if v==0, otherwise skip it
	move 	$v0, $t2			# Copy the memory address to v: v=(int)&(*bTable)
	
# Increment the values bTable, bPattern and j
skipAddr:
	addi	$t2, $t2, 1  		# bTable++
	addi	$t3, $t3, 1  		# bPattern++
	addi	$t1, $t1, 1  		# j++

# Check that if j ($t1) equals size2 ($a3), 
# we have found the byte pattern, so return
	bne		$t1, $a3, loop		# Continue loop if j!=size2
	jr      $ra					# if (j==size2) return v

# The byte values in byte array and byte pattern were not the same	
notSame:
	addi	$t2, $t2, 1  	# bTable++
	move	$v0, $zero 		# v = 0
	move	$t1, $zero 		# j = 0
	move	$t3, $a2		# bPattern = bPatternBegin 
	b 		loop			# Go back to loop

# If loop exits here, it means that the byte pattern has not been found, so return 0
exit:
	move	$v0, $zero 		# v = 0
    jr      $ra				# return to prosedure that called memmem

    .end
