Computer Science Canada

The Joys of MIPS
Author:  md [ Fri Jan 20, 2006 6:28 pm ]
Post subject:  The Joys of MIPS
For all of you who are thinking about taking CS at UW, and anyone else who wants to hurt their brains here is some of the code I've had to write thus far in MIPS. MIPS is an assembly language/processor design a la RISC.

Since the assigments that this was for is now due you'd be hard pressed to copy my stuff, and I figured someone might be interested in the mind blowing drugery that is assembly.

code:
#       Course:                CS241
#       Assignment:    1, Part 4
#       UserID:                jblackwo
#
#

.globl a1p4

#######################################
#       Function a1p4
#              Calculates the fibonacci sequence and stores it in the passed
#              array.
#
#       Registers:
#              $2, $3 are used to store the last two numbers
#              $4 is used to count how many numbers we've saved
#              $5 is the total we're suppsed to save
#              $6 is the address of the current element in the array
#              $10 is a temporary storage variable
#
#       case_1: total = 1
#       case_2: total = 2
#       case_3: total > 2

a1p4:   addi $30, $30, -24 # save registers, 6*4 = 24 bytes needed
        sw $2,   0($30)
        sw $3,   4($30)
        sw $4,   8($30)
        sw $5,  12($30)
        sw $6,  16($30)
        sw $10, 20($30)

        lw $5, 24($30)    # load the total number of elements to find              
        lw $6, 28($30)    # load the address of the array
               
        # check for nothing
        beq $5, $0, return      # if( $5 = 0) return
       
        # check for case 1
        addi $10, $0, 1  # set $10 to 1
        beq $5, $10, case_1     # if( $5 = 1) do case 1
       
        # check for case 2
        addi $10, $0, 2  # set $10 to 2
        beq $5, $10, case_2     # if( $5 = 2) do case 2

        # else run case 3
case_3: addi $4, $0, 0      # initialize counter to 0
        addi $2, $0, 1    # first number is 1
        addi $3, $0, 1    # second number is 1
       
        # n = 1
        sw $2, 0($6)        # store 1 in the first spot in the array
        addi $6, $6, 4    # increment the address pointer (4 byte words)
        addi $4, $4, 1    # increment the counter
       
        # n = 2
        sw $2, 0($6)        # store 1 in the second spot in the array
        addi $6, $6, 4    # increment the address pointer (4 byte words)
        addi $4, $4, 1    # increment the counter
       
        # for $5 > n > 2
c3_lp:  sub $10, $5, $4      # $10 = $5 - $4
        blez $10, return        # if $10 <= 0 ($5 <= $4), we're done so return
       
                # otherwise calculate the next part of the fib
                add $10, $3, $2  # $10 = $2 + $3, get the next number in the fib
                addi $2, $3, 0    # $2 = $3, drop the smaller number
                addi $3, $10, 0  # $3 = $10, make $3 the new larger number
                       
                # store it
                sw $3, 0($6)        # store the new larger number ($3) in the array
                addi $6, $6, 4    # increment the address pointer (4 byte words)
                addi $4, $4, 1    # increment the counter
        j c3_lp   # jump to the conditional


case_2:
        addi $10, $0, 1  # store a 1
       
        # n = 1
        sw $10, 0($6)      # store 1 in the first spot in the array
        addi $6, $6, 4    # increment the address pointer (4 byte words)
       
        # n = 2
        sw $10, 0($6)      # store 1 in the second spot in the array

        # return
        j return

case_1: 
        addi $10, $0, 1  # store a 1
       
        # n = 1
        sw $10, 0($6)      # store 1 in the first spot in the array

        # return

       
       
return: lw $2,   0($30)
        lw $3,   4($30)
        lw $4,   8($30)
        lw $5,  12($30)
        lw $6,  16($30)
        lw $10, 20($30)
        addi $30, $30, 24       # restore stack        pointer
        jr $31



code:
#       Course:                CS241
#       Assignment:    1, Part 4
#       UserID:                jblackwo
#
#

.globl a1p5

#######################################
#       Function a1p5
#              returns the sum of all the nodes in the tree given, recursively
#
#       Registers:
#              $2 is the address of the current node
#              $4 is the value of the current node
#              $3, $5 are child node addresses
#              $1 returns the result
#

a1p5:   addi $30, $30, -20 # save registers, 6*4 = 20 bytes needed
        sw $2,   0($30)
        sw $3,   4($30)
        sw $4,   8($30)
        sw $5,  12($30)
        sw $31, 16($30)

        lw $2, 20($30)    # load the address of the node       
        lw $4, 0($2)        # get the current nodes value
        lw $3, 4($2)        # get the left node's address
        lw $5, 8($2)        # get the right node's address
       
step_1: beq $3, $2, step_2       # if the left node is an actual node ( $3 != $2)
        addi $30, $30, -4       # allocate space for the address of the left node
        sw $3, 0($30)      # push $3
        jal a1p5                # call
        addi $30, $30, 4        # de-allocate stack space
        add $4, $4, $1    # add the result to the current node's stored value

step_2: beq $5, $2, return       # if the right node is an actual node ( $5 != $2)
        addi $30, $30, -4       # allocate space for the address of the right node
        sw $5, 0($30)      # push $5
        jal a1p5                # call
        addi $30, $30, 4        # de-allocate stack space
        add $4, $4, $1    # add the result to the current node's stored value

return: addi $1, $4, 0      # save the result in $1
        lw $2,   0($30)  # restore registers
        lw $3,   4($30)
        lw $4,   8($30)
        lw $5,  12($30)
        lw $31, 16($30)
        addi $30, $30, 20       # restore stack        pointer
        jr $31



Enjoy Wink
Author:  codemage [ Mon Jan 23, 2006 1:03 pm ]
Post subject: 
Cruel - but I had to do an assignment in machine code (binary) once. Evil or Very Mad

I believe it was "hello world" or a keyboard input echo or somesuch.
Author:  blaster009 [ Mon Jan 23, 2006 5:01 pm ]
Post subject: 
That makes me sad and worried for my future Sad
Author:  wtd [ Mon Jan 23, 2006 5:53 pm ]
Post subject: 
MIPS is heaven. I once wrote Pong in x86 assembly. It wasn't very good, and even getting that involved a considerable amount of black magic.
Author:  md [ Mon Jan 23, 2006 5:55 pm ]
Post subject: 
codemage wrote:
Cruel - but I had to do an assignment in machine code (binary) once. Evil or Very Mad

I believe it was "hello world" or a keyboard input echo or somesuch.


I would very much like to see this... as I find it to be almost completely unlikely. The difference between assembly and binary encoded istructions is that the assembly is in english and isn't binary encoded.

Not that I think your full of it... just that I think your full of it Wink
Author:  Martin [ Mon Jan 23, 2006 6:21 pm ]
Post subject: 
MIPS was a lot of fun. I got like 65% total on my assignments, even though I only lost like 1 mark on the actual test cases.

Differing philosophies.
Me. Commenting should be used to help explain algorithms used.
CS241 Tutors. Commenting should be used to the extent that a retarded blind monkey will be able to learn MIPS from just having your code on a computer that's in the same room as them.

Pesonally, I don't think that beq $5, $0, return # if( $5 = 0) return is a useful comment. Not that I'm criticizing you Cornflake - you'd have lost a ton of marks if you didn't put it.

And that's why I got out of CS.
Author:  md [ Mon Jan 23, 2006 10:56 pm ]
Post subject: 
Martin wrote:
MIPS was a lot of fun. I got like 65% total on my assignments, even though I only lost like 1 mark on the actual test cases.

Differing philosophies.
Me. Commenting should be used to help explain algorithms used.
CS241 Tutors. Commenting should be used to the extent that a retarded blind monkey will be able to learn MIPS from just having your code on a computer that's in the same room as them.

Pesonally, I don't think that beq $5, $0, return # if( $5 = 0) return is a useful comment. Not that I'm criticizing you Cornflake - you'd have lost a ton of marks if you didn't put it.

And that's why I got out of CS.

Oh yeah, comments in CS courses are retarded, but since you don't ever lose marks for having too many, and you do for not having enough it's a no-brainer. Rule of thumb for anything more complex then a bubble sort in java: 1 comment/line plus a comment at the start of each block of code. If a 3 year old can't understand it then your CS tutors might not be able to either.
Author:  codemage [ Tue Jan 24, 2006 10:52 am ]
Post subject: 
Cornflake wrote:
codemage wrote:
Cruel - but I had to do an assignment in machine code (binary) once. Evil or Very Mad

I believe it was "hello world" or a keyboard input echo or somesuch.


I would very much like to see this... as I find it to be almost completely unlikely. The difference between assembly and binary encoded istructions is that the assembly is in english and isn't binary encoded.

Not that I think your full of it... just that I think your full of it Wink


It's in a big box full of dot-matrix printouts at my parent's house - so I can't dig it out right at the moment. You're right about the encoding though (and not about the full of it part). The assignment basically had two parts:

#1 - write the program in assembly
#2 - convert the program (by hand) to the binary coding using an instruction-set-architecture-specific reference manual.

#2 was the cruel part - but the assignment looked cool.
Author:  md [ Tue Jan 24, 2006 1:19 pm ]
Post subject: 
codemage wrote:
Cornflake wrote:
codemage wrote:
Cruel - but I had to do an assignment in machine code (binary) once. Evil or Very Mad

I believe it was "hello world" or a keyboard input echo or somesuch.


I would very much like to see this... as I find it to be almost completely unlikely. The difference between assembly and binary encoded istructions is that the assembly is in english and isn't binary encoded.

Not that I think your full of it... just that I think your full of it Wink


It's in a big box full of dot-matrix printouts at my parent's house - so I can't dig it out right at the moment. You're right about the encoding though (and not about the full of it part). The assignment basically had two parts:

#1 - write the program in assembly
#2 - convert the program (by hand) to the binary coding using an instruction-set-architecture-specific reference manual.

#2 was the cruel part - but the assignment looked cool.

Gotcha... definitely sounds like an evil assignment... Ahh well, I is done mips now; just need to do the compiler stuff now... which I should really get started on...
Author:  Andy [ Tue Jan 24, 2006 3:11 pm ]
Post subject: 
codemage, why didnt u just write a compiler to do it? it would have been alot easier
Author:  bugzpodder [ Tue Jan 24, 2006 9:08 pm ]
Post subject: 
I've written four versions of the same assignment (yes, I am THAT bored) and compared their run times. Of course, that resulted in the lecturer(Vasiga) cracking jokes about this in class.

Look at my Rabin-Miller strong pseudoprime test implemented in MIPS, ten times more brain ****ing than the program listed on the top

code:

# documentation of each subroutine is below
# main routine (a1p3) computers the number of composite integers in an array
# returns result in $1, no other register is modified

# tier 0 - leaf
# tier 1 - routine that calls tier 0 routine(s)
# etc

# Register Usage:
# $1 - Return result
# $2-$7   Main Variables (a1p4)
# $8-$9   Parameter passing in subroutine
# $10     Result holder of subroutines
# $11-$15 temp variables used freely by tier 0
# $16-$17 global variables and constants used by all routines
# $18-$22 temp variables used by tier 1
# $23-$27 more temp variables used by tier 2
# $28-$29 tier 2/1 register savers

# Constants in this program
# $16=the modding value
# $17=1

.globl a1p3

a1p3:

# Register Usage:
# $1 - accumulates result
# $2 - address of array
# $3 - number of elements
# $4 - current array index
# $5 - test condition
# $6 - array element address/data
# $7 - divisor
# $30 - stack
# $31 - return address

        #addi $8, $0, 2
        #addi $9, $0, 1
        #addi $16, $0, 3
        #add $3, $31, $0
        #jal modexp
        #add $1, $10, $0
        #add $31, $3, $0
        #jr $31

        addi $30, $30, -116               #allocate stack space
        sw $2, 0($30)            #saves registers $2-$29
        sw $3, 4($30)
        sw $4, 8($30)
        sw $5, 12($30)
        sw $6, 16($30)
        sw $7, 20($30)
        sw $8, 24($30)
        sw $9, 28($30)
        sw $10, 32($30)
        sw $11, 36($30)
        sw $12, 40($30)
        sw $13, 44($30)
        sw $14, 48($30)
        sw $15, 52($30)
        sw $16, 56($30)
        sw $17, 60($30)
        sw $18, 64($30)
        sw $19, 68($30)
        sw $20, 72($30)
        sw $21, 76($30)
        sw $22, 80($30)
        sw $23, 84($30)
        sw $24, 88($30)
        sw $25, 92($30)
        sw $26, 96($30)
        sw $27, 100($30)
        sw $28, 104($30)
        sw $29, 108($30)
        sw $31, 112($30)
        lw $2, 120($30)    #loads number of elements
        lw $3, 116($30)    #loads address of array

        add $1, $0, $0        #init result
        add $4, $0, $0        #init index
        addi $17, $0, 1

loop:   sub $5, $3, $4                    #Array size - current index
        blez $5, end                #exit loop if no more elements

        sll $6, $4, 2            #calculate the next address
        add $6, $6, $2

        lw $6, 0($6)                #read next element
        add $5, $0, $0        #resets counter
       
        beq $6, $17, stop                     #exit if $6 is 1
       
        add $8, $6, $0       
        jal isprime                    #test if prime or not

        sub $5, $17, $10                        #get result

stop:   addi $4, $4, 1                    #increase counter
        add $1, $5, $1        #update result
        j loop          #go back to loop

end:    lw $2, 0($30)                           #saves registers $2-$29
        lw $3, 4($30)
        lw $4, 8($30)
        lw $5, 12($30)
        lw $6, 16($30)
        lw $7, 20($30)
        lw $8, 24($30)
        lw $9, 28($30)
        lw $10, 32($30)
        lw $11, 36($30)
        lw $12, 40($30)
        lw $13, 44($30)
        lw $14, 48($30)
        lw $15, 52($30)
        lw $16, 56($30)
        lw $17, 60($30)
        lw $18, 64($30)
        lw $19, 68($30)
        lw $20, 72($30)
        lw $21, 76($30)
        lw $22, 80($30)
        lw $23, 84($30)
        lw $24, 88($30)
        lw $25, 92($30)
        lw $26, 96($30)
        lw $27, 100($30)
        lw $28, 104($30)
        lw $29, 108($30)
        lw $31, 112($30)
        addi $30, $30, 112                  #deallocates stack space
        jr $31          #returns

isprime: #tier 2
        #Determines if $8 is prime.  save it in $10    
        #All negative numbers are considered not prime
        #calls modexp, which is tier 1
       
        add $28, $31, $0                        #saves $31 for tier 2   
        andi $23, $8, 1    #check if $8 is even
        bne $23, $0, isprimeodd   #branch if odd
                               
        slti $23, $8, 3    #check if $8 is 2        
        j isprimeend                #quit

isprimeodd:                         #Rabin-Miller Primality Testing
                                                #deterministic up to 3215131751>0x7fffffff
               
        addi $23, $0, 1    #assume the number has passed
        add $16, $8, $0    #save param
       
        addi $30, $30, -4                     #allocate space                       
        addi $8, $0, 2        #prime 2
        sw $8, 0($30)            #save on stack
        addi $27, $0, 1    #update counter
        llo $9, 2047                #load constant
        lhi $9, 2047
        sub $9, $9, $16 
        bgtz $9, isprimeloop            #if prime is less than constant, branch

        addi $30, $30, -4                     #same as above
        addi $8, $0, 3
        sw $8, 0($30)
        addi $27, $0, 2
        llo $9, 1373653
        lhi $9, 1373653
        sub $9, $9, $16
        bgtz $9, isprimeloop

        addi $30, $30, -4                     #same as above
        addi $8, $0, 5
        sw $8, 0($30)
        addi $27, $0, 3
        llo $9, 25326001
        lhi $9, 25326001
        sub $9, $9, $16
        bgtz $9, isprimeloop


        addi $30, $30, -4                     #same as above
        addi $8, $0, 7
        sw $8, 0($30)
        addi $27, $0, 4
       

isprimeloop:
        addi $27, $27, -1                     #dec counter by 1
        lw $8, 0($30)            #peek top element in stack
        addi $30, $30, 4                        #pop element
        beq $23, $0, isprimecheck              #failed, stop testing

        addi $25, $16, -1                     #$25 is $16-1, which is even         
        add $9, $25, $0    
        add $26, $0, $0    #counter for number of factors of 2 in $26

isprimeloop2:
        srl $9, $9, 1            #divide $9 by 2
        addi $26, $26, 1                        #inc counter
        andi $24, $9, 1                        #tests if still even
        bne $24, $0, isprimecont                #branch if $9 is not even
        j isprimeloop2        #continue in loop

isprimecont:
        jal modexp
        #add $4, $10, $0
        #trap 1
        #add $4, $17, $0
        add $24, $10, $0                        #get result
        beq $24, $17, isprimecheck            #passes test
       
isprimeloop3:
        beq $24, $25, isprimecheck            #branch if passed
        beq $26, $0, isprimefail                #branch if failed
        addi $26, $26, -1                     #dec counter
        add $8, $24, $0
        add $9, $24, $0
        jal modmul                        #compute $24^2 (mod $16)
        add $24, $10, $0                        #get result
        j isprimeloop3  

isprimefail:
        add $23, $0, $0    #failed test

isprimecheck:
        beq $27, $0, isprimeend   #check if end
        j isprimeloop

isprimeend:
        add $10, $23, $0                        #save result
        add $31, $28, $0                        #restore $31 register
        jr $31


#pre conditions for all modular arithmetic functions below (modxxx)
#$16>0 (the modding value)
#$8>=0, $9>=0 (if applicable)
# a=b mod c =>  0<=a<c

       
modmul: #tier 0        
        #Computes $10=($8*$9) % $16
                               
        mult $8, $9
        mfhi $11                                #get higher 32-bits
        mflo $10                                #get lower 32-bits
        beq $11, $0, mulend               #no overflow

        addi $15, $0, 32                     #loop index

muloop:
        beq $15, $0, mulend               #branch when counter is 0
        sll $11, $11, 1    #multiply $11 by 2
        addi $15, $15, -1
        divu $11, $16            #compute modulo
        mfhi $11
        j muloop                                #repeat

mulend:
        divu $10, $16            #compute lower bits mod $16
        mfhi $10                               
        addu $10, $11, $10                  #computes (Hi mod $16 + Lo mod $16) mod 16
        divu $10, $16
        mfhi $10
        jr $31


modexp: #tier 1
        #Computes ($8 ^ $9) mod $16
        #pre: $8 and $9 are not both 0
        #calls modmul, which is tier 0. 

        div $8, $16                    #take mod of param
        mfhi $8   
       
        add $29, $31, $0                        #save $31, tier 1

        addi $18, $0, 1    #accumulates result
       
        add $21, $8, $0    #input #1
        add $22, $9, $0    #input #2

       
exploop:
        beq $22, $0, expstoploop                #branch when nothing to do
        andi $19, $22, 1                       
        srl $22, $22, 1    #divide $22 by 2

       
        beq $19, $0, expskip            #if $22 is even, dont mult

        add $8, $21, $0    #compute ($10*$18) mod $16
        add $9, $18, $0
        jal modmul

        add $18, $10, $0

expskip:
        add $8, $21, $0    
        add $9, $21, $0
        jal modmul                              #compute ($21^2) mod $16

        add $21, $10, $0
 
        j exploop

expstoploop:
        add $10, $18, $0                        #get result to $10
        add $31, $29, $0                        #return address
        jr $31


primality (how ever the *** u spell that) test #2
trival divisor test
code:

# subroutine that determines number of composite integers in an array
# return result in $1
# no other registers are modified

# Register Usage:
# $1 - accumulates result
# $2 - address of array
# $3 - number of elements
# $4 - current array index
# $5 - test condition
# $6 - array element address/data
# $7 - divisor
# $30 - stack

.globl a1p3

a1p3:   addi $30, $30, -24   #allocate stack space
        sw $2, 0($30)            #saves registers $2-$7
        sw $3, 4($30)
        sw $4, 8($30)
        sw $5, 12($30)
        sw $6, 16($30)
        sw $7, 20($30)
        lw $2, 28($30)        #loads number of elements
        lw $3, 24($30)        #loads address of array

        add $1, $0, $0        #init result
        add $4, $0, $0        #init index

loop:   sub $5, $3, $4                    #Array size - current index
        blez $5, end                #exit loop if no more elements

        sll $6, $4, 2            #calculate the next address
        add $6, $6, $2

        lw $6, 0($6)                #read next element
        add $5, $0, $0        #resets counter

        addi $7, $0, 1        #sets $7 to 1 for comparsion     
        beq $6, $7, stop                        #exit if $6 is 1
        addi $7, $0, 2        #set divisor to 2

factor: beq $6, $7, stop   #divisor=number, stop testing
        div $6, $7                        #divide
        mfhi $5     #get remainder
        slti $5, $5, 1        #check if remainder is 0
        bgtz $5, stop            #if it is, exit
        addi $7, $7, 1        #otherwise increase the divisor
        j factor                                #keep testing

stop:   addi $4, $4, 1                    #increase counter
        add $1, $5, $1        #update result
        j loop          #go back to loop

end:    lw $2, 0($30)                            #loads registers $2-$7
        lw $3, 4($30)
        lw $4, 8($30)
        lw $5, 12($30)
        lw $6, 16($30)   
        lw $7, 20($30)   
        addi $30, $30, 24                     #deallocates stack space
        jr $31          #returns



primality test #3: stop testing when divisor ^2 > n
code:


# subroutine that determines number of composite integers in an array
# return result in $1
# no other registers are modified

# Register Usage:
# $1 - accumulates result
# $2 - address of array
# $3 - number of elements
# $4 - current array index
# $5 - test condition
# $6 - array element address/data
# $7 - divisor
# $30 - stack

.globl a1p3

a1p3:   addi $30, $30, -24   #allocate stack space
        sw $2, 0($30)            #saves registers $2-$7
        sw $3, 4($30)
        sw $4, 8($30)
        sw $5, 12($30)
        sw $6, 16($30)
        sw $7, 20($30)
        lw $2, 28($30)        #loads number of elements
        lw $3, 24($30)        #loads address of array

        add $1, $0, $0        #init result
        add $4, $0, $0        #init index

loop:   sub $5, $3, $4                    #Array size - current index
        blez $5, end                #exit loop if no more elements

        sll $6, $4, 2            #calculate the next address
        add $6, $6, $2

        lw $6, 0($6)                #read next element
        add $5, $0, $0        #resets counter

        addi $7, $0, 1        #sets $7 to 1 for comparsion     
        beq $6, $7, stop                        #exit if $6 is 1
        addi $7, $0, 2        #set divisor to 2

        andi $5, $6, 1        #test for n being even
        bne $5, $0, cont1                     #branch if n is odd
        slt $5, $7, $6        #test if n=2
        j stop          #stop
cont1:  addi $7, $0, 3
       
factor: mult $7, $7                        #square $7
        mflo $5     #get result
        sub $5, $5, $6        #$5:=$5-$6

        slti $5, $5, 1        #stop testing if $5>0
        beq $5, $0, stop                       

        beq $6, $7, stop                        #divisor=number, stop testing
        div $6, $7                        #divide
        mfhi $5     #get remainder
        slti $5, $5, 1        #check if remainder is 0
        bgtz $5, stop            #if it is, exit
        addi $7, $7, 2        #otherwise increase the divisor
        j factor                                #keep testing

stop:   addi $4, $4, 1                    #increase counter
        add $1, $5, $1        #update result
        j loop          #go back to loop

end:    lw $2, 0($30)                            #loads registers $2-$7
        lw $3, 4($30)
        lw $4, 8($30)
        lw $5, 12($30)
        lw $6, 16($30)   
        lw $7, 20($30)   
        addi $30, $30, 24                     #deallocates stack space
        jr $31          #returns


primality test #4: checks only 6k+/-1
code:


# subroutine that determines number of composite integers in an array
# return result in $1
# no other registers are modified

# Register Usage:
# $1 - accumulates result
# $2 - address of array
# $3 - number of elements
# $4 - current array index
# $5 - test condition
# $6 - array element address/data
# $7 - divisor
# $30 - stack

.globl a1p3

a1p3:   addi $30, $30, -24   #allocate stack space
        sw $2, 0($30)            #saves registers $2-$7
        sw $3, 4($30)
        sw $4, 8($30)
        sw $5, 12($30)
        sw $6, 16($30)
        sw $7, 20($30)
        lw $2, 28($30)        #loads number of elements
        lw $3, 24($30)        #loads address of array

        add $1, $0, $0        #init result
        add $4, $0, $0        #init index

loop:   sub $5, $3, $4                    #Array size - current index
        blez $5, end                #exit loop if no more elements

        sll $6, $4, 2            #calculate the next address
        add $6, $6, $2

        lw $6, 0($6)                #read next element
        add $5, $0, $0        #resets counter

        addi $7, $0, 1        #sets $7 to 1 for comparsion     
        beq $6, $7, stop                        #exit if $6 is 1
        addi $7, $0, 2        #set divisor to 2

        andi $5, $6, 1        #test for n being even
        bne $5, $0, cont1                     #branch if n is odd
        slt $5, $7, $6        #test if n=2
        j stop          #stop

cont1:           
        addi $7, $0, 3        #set divisor to 3
        add $5, $0, $0        #reset counter
        beq $6, $7, stop                        #if equal to 3, branch
        div $6, $7                        #otherwise test for 3 as factor
        mfhi $5     #get remainder
        slti $5, $5, 1        #check if 0
        bgtz $5, stop            #branch if it is, branch

        addi $7, $0, 5        #if not, then all the factors
                                                #must be in the form 6k+/-1
                                                #since 6k, 6k+2, 6k+3, 6k+4
                                                #are divisible by 2 or 3


factor: mult $7, $7                        #square the divisor
        mfhi $5     #get hi result
        slti $5, $5, 1        #check if 0
        beq $5, $0, stop                        #if equal 0, then divisotr^2>n
       
                                                #otherwise no overflow
        mflo $5     #get lo result
        sub $5, $5, $6        #$5:=$5-$6

        slti $5, $5, 1        #stop testing if divisor^2>n
        beq $5, $0, stop                       

        div $6, $7                        #$7 is 6k-1, divide
        mfhi $5     #get remainder
        slti $5, $5, 1        #check if remainder is 0
        bgtz $5, stop            #if it is, exit
       
        addi $7, $7, 2        #$7 is now 6k+1
        div $6, $7                        #same as above
        mfhi $5     
        slti $5, $5, 1
        bgtz $5, stop

        addi $7, $7, 4        #otherwise increase the divisor
        j factor                                #keep testing

stop:   addi $4, $4, 1                    #increase counter
        add $1, $5, $1        #update result
        j loop          #go back to loop

end:    lw $2, 0($30)                            #loads registers $2-$7
        lw $3, 4($30)
        lw $4, 8($30)
        lw $5, 12($30)
        lw $6, 16($30)   
        lw $7, 20($30)   
        addi $30, $30, 24                     #deallocates stack space
        jr $31          #returns


:


You can syndicate this boards posts using the file backend.php or view the topic map using sitemap.php.

Terms of Use | Privacy Policy