P1-2-2.asm

#=================================================================
# Copyright 2023 Georgia Tech.  All rights reserved.
# The materials provided by the instructor in this course are for
# the use of the students currently enrolled in the course.
# Copyrighted course materials may not be further disseminated.
# This file must not be made publicly available anywhere.
# =================================================================
#
#	 Labeling Connected Objects in Hubble-Webb Images
#
# Please fill in the following
# Your Name: Ashan Deen
# Date: 
# 
# ECE 2035 Project1-2
#
# This program takes in one 32x32 binary difference image (generated by swi 602
# by computing the difference of a pair of corresponding tiles in	
# two larger images and placed into memory at Diff).
# It replaces black pixels in the Diff array with labels in the range 1-32,
# assigning a unique label to each connected component of adjacent pixels
# (adjacency is defined by 8-connectivity: in N, NE, E, SE, S, SW, W, NW 
# directions).
# White pixels remain unchanged.
#
# The program reports the results with swi 604:
#     $1 Base addr of labeled array
#     $4 num components, $5 min size, $6 max size 
# Oracle:
#     $2 number labeling errors
#     $7 correct num components, $8 correct min size, $9 correct max size
# Labeling errors:
#     black pixel not labeled,
#     white pixel not white,
#     labels out of range [1-32] inclusive
#     labels in memory are not consistent with correct CC labeling.
#	
#===========================================================================
# CHANGE LOG: brief description of changes made from P1-2-shell.asm
# to this version of code.
# Date  Modification
# 02/21 Declared and initialised variables         
# 02/21 Initialised components array
# 02/23 Initialised equalLabels array    
# 02/23 created 1st loop inititialisation and 1st if condition\
# 02/23 created 2nd if condition to check is pixel[0] is black
# 02/25 assigned new label if pixel 0 was black
# 02/25 made elseif statement for first row
# 02/25 made elsif to check the first pixel on each row
#02/26 added sll2 to get index from equalLabels array
# 02/27 made the loops for the 2nd pass and pass to count all components
# 02/27 changed ENDIF4 to ENDIF2
# 02/27 changed ELSE23 to j IF5
# 02/27 changed ENDIF2 to ENDIF1
#02/27 made pass3 shorter by taking out counter $16
# 02/27 made pass4 shorter by taking out counter $16
#02/27 made pass2 shorter by taking out counter $16
# 02/27 removed instruction addi $14,$0,0 #set index to 0 line 110
# 02/28 changed surreounding pixels to min label
# 02/28 checked if i%32=31 for last column of pixel
# 02/28 changed ELSEIF3 AND ELSEIF4 to jump to ELSEIF9
#02/28 deleted ENDIF3, ENDIF4 and ENDIF9
#===========================================================================

.data
Diff:        .alloc	1024		# allocate binary threshold image space
equalLabels:  .alloc 33			# allocate space for label equivalancies
components:   .alloc 32			# allocate space for components
.text
# $1: Diff base address
# $2: TileNum to start
# $3: Num
# $4: numCC
# $5: min
# $6: max 

# $10: Diff base address
# $11: components base address
# $12: minLabel
# $13:label 
# $14:index
# $15:white
# $16: counter
# $17:loop limit
# $18 : predicate value
# $19: other indexes
#$20: Equivilancy label base addr

CC:	addi	$1, $0, Diff		# set memory base
	addi    $2, $0, 50	# TileNum to start with
	swi	602			# create and display images

	addi $4,$0,0 #init NumCC
	addi $6,$0,0 #init max
	addi $13,$0,0 #init label
	lui  $15,0xFF #load upperimmediate into WHITE
	ori $15,$15,0xFFFF  #init WHITE
    add $5,$0,$15 #init min to WHITE
	addi $16,$0,0 #init counter
	addi $17,$0,33 #set limit for loop for array equalLabels
	addi $14,$0,0 #set index to 0

InitEqualLabels:  sw  $16,equalLabels($14) #store word in equalLabels array
	  		      addi $16,$16,1 #increment counter
				  sll $14,$16,2 #multiple counter by 4 to get index
	  			  bne $16,$17,InitEqualLabels #loop if counter != 33
	  
	  			addi $14,$0,0 #set index to 0
				addi $16,$0,0 #init counter
				addi $17,$0,132 #set limit (33 * 4 (int)) for loop for array components to 32

InitComponents:  sw  $16,components($14) #store word in components array
	  		    addi $14,$14,4 #increment counter
	  			bne $14,$17,InitComponents #loop if counter != 32 (index != 128)

				addi $14,$0,0 #set index to zero
				addi $17,$0,4096 #set loop limit to 1024	
Pass1: 			add $12,$0,$15 #set the minLabel to WHITE

#Checks if current pixel is black
IF1:            lw $10,Diff($14)  # load Diff[i] into $10
                bne $10,$0,ENDIF1 # check if Diff[i] == BLACK, if not go to ENDIF1

    #checks for first pixel
    IF2:            bne $14,$0,IF21 #if first pixel not equal to 0 go to IF21
                    addi $13,$13,1 #increment label
                    sw $13,Diff($0) # Diff[0] = label
                    j ENDIF1   #jump to ENDIF2

    #checks for top row
    IF21:           slti $18,$14,128 #if i<32 $18 is 1
                    beq $18,$0,ELSEIF22 # if  !(i<32) jump to ELSEIF22
                    

        #Checks if pixel to the left is not white
        IF3: 			addi $19,$14,-4 # $19 is i-1
		        		lw $10,Diff($19) #load Diff[i-1]
		        		beq $10,$15,ELSE3 # if Diff[i-1] is white do ELSE3
                        sw $10,Diff($14) #set the current pixels label to previous pixels 
                        j ENDIF1   #jump to ENDIF2
        
        ELSE3: 		    j ELSE9

        				
    #checks for first pixel in row
    ELSEIF22:       addi $19,$0,128  # add value 32 to $19
                    div  $14,$19    # i/32
                    mfhi $18        # $18 i%32
                    bne $18,$0,IF5 # if  !(i%32 == 0) jump to ELSE23(j IF5)
        
        IF4:        addi $19,$14,-128 # $19 is i-32
		        	lw $10,Diff($19) #load Diff[i-32]
		        	beq $10,$15,IF41 # if Diff[i-32] is white do IF41
                    sw $10,Diff($14) #set the current pixels label to above pixels
                    j ENDIF1 # goes to end if of if statement

        IF41:       addi $19,$14,-124 # $19 is i-31
		        	lw $10,Diff($19) #load Diff[i-31]
		        	beq $10,$15,ELSE4 # if Diff[i-31] is white do ELSE4
                    sw $10,Diff($14) #set the current pixels label to above pixels 
                    j ENDIF1 # goes to end if of if statement  

        ELSE4:      j ELSE9

                    
    #checks all the other pixels
    ELSE23:  j IF5 #jump to IF5

        IF5:        addi $19,$14,-4 # $19 is i-1
		       		lw $10,Diff($19) #load Diff[i-1]
                    slt $18,$10,$12 # is Diff[i-1] < minLabel? if so $18=1
                    beq $18,$0,IF6 # if !(Diff[i-1] < minLabel) go to IF6
                    add $12,$0,$10 # minLabel = Diff[i-1]

        IF6:        addi $19,$14,-132 # $19 is i-33
		       		lw $10,Diff($19) #load Diff[i-33]
                    slt $18,$10,$12 # is Diff[i-33] < minLabel? if so $18=1
                    beq $18,$0,IF7 # if !(Diff[i-33] < minLabel) go to IF7
                    add $12,$0,$10 # minLabel = Diff[i-33]

        IF7:        addi $19,$14,-128 # $19 is i-32
		       		lw $10,Diff($19) #load Diff[i-32]
                    slt $18,$10,$12 # is Diff[i-32] < minLabel? if so $18=1
                    beq $18,$0,IF8 # if !(Diff[i-32] < minLabel) go to IF8
                    add $12,$0,$10 # minLabel = Diff[i-32]

        IF8:        addi $19,$14,-124 # $19 is i-32
		       		lw $10,Diff($19) #load Diff[i-32]
                    slt $18,$10,$12 # is Diff[i-32] < minLabel? if so $18=1
                    beq $18,$0,IF9 # if !(Diff[i-32] < minLabel) go to IF9
                    addi $21,$0,128  # add value 32 to $19
                    div  $14,$21    # i/32
                    mfhi $18        # $18 i%32
                    addi $21,$0,124 # make $21 31
                    beq $18,$21,IF9 # if  (i%32 == 31) jump to ELSE23(j IF5)
                    add $12,$0,$10 # minLabel = Diff[i-32]
                    
        IF9:        beq $12,$15,ELSE9 #if minLabel = WHITE go to ELSE9
                    sw $12,Diff($14) # store minLabel value in pixel
                   

            IF10:       addi $19,$14,-4 # $19 is i-1
		       	    	lw $10,Diff($19) #load Diff[i-1]
                        beq $10,$15,IF11 # if Diff[i-1] is white do IF11
                        sll $10,$10,2 #multiple value of diff[i-1]*4
                        lw $20,equalLabels($10) #load  equalLabels[Diff[i-1]]
                        slt $18,$12,$20 #if minLabel < equalLabels[Diff[i-1]] $18=1
                        beq $18,$0,IF11 #if $18 is 0 go to IF11
                        sw $12,Diff($19) # made Diff[i-1] = minLabel
                        sw $12,equalLabels($10)
                        
            IF11:       addi $19,$14,-132 # $19 is i-33
		           		lw $10,Diff($19) #load Diff[i-33]
                        beq $10,$15,IF12 # if Diff[i-33] is white do IF12
                        sll $10,$10,2 #multiple value of diff[i-1]*4
                        lw $20,equalLabels($10) #load  equalLabels[Diff[i-33]]
                        slt $18,$12,$20 #if minLabel < equalLabels[Diff[i-33]] $18=1
                        beq $18,$0,IF12 #if $18 is 0 go to IF12
                        sw $12,Diff($19) # made Diff[i-33] = minLabel
                        sw $12,equalLabels($10) # store new equivalance in equalLabels

            IF12:       addi $19,$14,-128 # $19 is i-32
		           		lw $10,Diff($19) #load Diff[i-32]
                        beq $10,$15,IF13 # if Diff[i-32] is white do IF13
                        sll $10,$10,2 #multiple value of diff[i-1]*4
                        lw $20,equalLabels($10) #load  equalLabels[Diff[i-32]]
                        slt $18,$12,$20 #if minLabel < equalLabels[Diff[i-32]] $18=1
                        beq $18,$0,IF13 #if $18 is 0 go to IF13
                        sw $12,Diff($19) # made Diff[i-32] = minLabel
                        sw $12,equalLabels($10)# store new equivalance in equalLabels

            IF13:       addi $19,$14,-124 # $19 is i-31
		           		lw $10,Diff($19) #load Diff[i-31]
                        beq $10,$15,ENDIF1 # if Diff[i-31] is white do ENDIF2
                        sll $10,$10,2 #multiple value of diff[i-1]*4
                        addi $21,$0,128  # add value 32 to $19
                        div  $14,$21    # i/32
                        mfhi $18        # $18 i%32
                        addi $21,$0,124 # make $21 31
                        beq $18,$21,ENDIF1 # if  (i%32 == 31) jump to ELSE23(j IF5)
                        lw $20,equalLabels($10) #load  equalLabels[Diff[i-31]]
                        slt $18,$12,$20 #if minLabel < equalLabels[Diff[i-31]] $18=1
                        beq $18,$0,ENDIF1 #if $18 is 0 go to ENDIF2 (ENDIF1)
                        sw $12,Diff($19) # made Diff[i-31] = minLabel
                        sw $12,equalLabels($10)# store new equivalance in equalLabels
                        j ENDIF1

        ELSE9:      addi $13,$13,1 #increment label
                    sw $13,Diff($14) # Diff[i] = label

        

        
ENDIF2:        j ENDIF1 # goes to end if of 1st if statement

ENDIF1:         addi $14,$14,4 #increment counter
                bne  $14,$17,Pass1 #if counter no equal to 1024 loop back
              
#Pass through equivilancy table 
          
            addi $16,$0,0 #set counter to 0
			addi $17,$0,33 #set loop limit to 33
IFLPass:    sll $14,$16,2 # convert counter to index
            lw $20,equalLabels($14) #load equalsLabel[i]
            beq $16,$20,ENDIFLPass #if (equalLabels[i] = i) jump to ENDIFLPass
            sll $20,$20,2 #convert to index
            lw $20,equalLabels($20) # load equalsLabel[equalsLabel[i]]
            sw $20,equalLabels($14)

ENDIFLPass: addi $16,$16,1 #increment counter
            bne  $16,$17,IFLPass #if counter no equal to 33 loop back
        
        #swi	603
#2nd pass through image 

            addi $14,$0,0 #set counter to 0
			addi $17,$0,4096 #set loop limit to 1024
Pass2:      lw $10,Diff($14) #load Diff[i] 
    IF14:       beq $10,$15,ENDIF14 # if (Diff[i] != WHITE) go to ENDIF14
                sll $19,$10,2 #convert Diff[i] into index
                lw $20,equalLabels($19) #load equalsLabel[Diff[i]]
                sw $20,Diff($14) #Diff[i] = equalLabels[Diff[i]]
                sll $19,$20,2 #convert Diff[i] into index
                lw $20,components($19) #load components[Diff[i]]
                addi $20,$20,1  #components[Diff[i]] + 1
                sw $20,components($19) #components[Diff[i]] = components[Diff[i]] + 1

ENDIF14:    addi $14,$14,4 #increment counter
            bne  $14,$17,Pass2 #if counter no equal to 1024 loop back



#Pass to calculate min, max and number of components

            addi $14,$0,0 #set index to 0
			addi $17,$0,132 #set loop limit to 33
Pass4:      lw $11,components($14) #load components[i]

    IF16:       beq $11,$0,IF17 #if (components[i] = 0) jump to IF17
                slt $18,$6,$11 # is max < components[i] $18 is 1
                beq $18,$0,IF17 # if not jump to IF17
                add $6,$0,$11 # max = components[i]

    IF17:       beq $11,$0,IF18 #if (components[i] = 0) jump to IF18
                slt $18,$11,$5 # is  components[i] < min $18 is 1
                beq $18,$0,IF18 # if not jump to IF18
                add $5,$0,$11 # max = components[i]

    IF18:       beq $11,$0,ENDPass4 #if (components[i] = 0) jump to ENDPass4
                addi $4,$4,1 #increment numCC

    ENDPass4:   addi $14,$14,4 #increment counter
                bne  $14,$17,Pass4 #if counter no equal to 1024 loop back


IF19: bne $5,$15,FINISH
      addi $5,$0,0
      
FINISH: j Report

#CHECK:  swi 603
	######################################################################
	# FOR DEBUGGING ONLY: comment out any use of swi 603 before submitting

	#addi    $2, $0, 5     	      	# TEMP: replace this
	#addi    $3, $0, 16		# TEMP: replace this
	#sw      $2, Diff($3)		# TEMP: replace this
	#addi    $3, $3, 4		# TEMP: replace this
	#sw      $2, Diff($3)		# TEMP: replace this
	#addi    $3, $3, 4		# TEMP: replace this
	#sw      $2, Diff($3)		# TEMP: replace this
	#addi    $3, $3, 4		# TEMP: replace this
	
	#addi    $1, $0, Diff		# Set $1 to base address of subarray
	#swi 603 	      	        # displays labeled subarray currently
	    				# in memory w/out checking answer or
					# calling the oracle.
					# This can be used to check intermediate
					# results in an incomplete program
	######################################################################


Report:	addi    $4, $4, 0		# guess number of components
	addi    $5, $5, 0	# guess min size
	addi    $6, $6, 0	# guess max size
	addi    $1, $0, Diff
	swi     604			# Report results
	jr      $31