7
\$\begingroup\$

I've done some programming in the past, but I'm new to MIPS, which I'm trying to learn on my own. This program lists the first five perfect numbers. It uses the Lucas-Lehmer and Miller-Rabin primality tests. Any suggestions on how I could improve will be most appreciated.

    .data                           # marks the following as data
seed:
    .word       127                 # seed for random number sequence
newline:
    .asciiz     "\n"                # newline character
tabchar:
    .asciiz     "\t"                # tab character
header:
    .asciiz     "n\tp\tm\tpn\n" 
    .text                           # required - beginning of executable code
###############################################################################
#   displays the first five perfect numbers 
#
#   register usage:
#   $s0 n perfect number counter    $s4 unused  
#   $s1 current prime               $s5 unused
#   $s2 mersenne number             $s6 unused
#   $s3 unused                      $s7 unused 
#
#   $t0 scratch                     $t5 unused
#   $t1 scratch                     $t6 unused 
#   $t2 scratch                     $t7 unused
#   $t3 unused                      $t8 unused 
#   $t4 unused                      $t9 unused 
#
main:                               # required - address of first instruction
    addiu   $sp,$sp,-36             # make room for ra & s registers
    sw      $ra,0($sp)              # preserve return address
    sw      $s0,4($sp)
    sw      $s1,8($sp)
    sw      $s2,12($sp)
    sw      $s3,16($sp)
    sw      $s4,20($sp)
    sw      $s5,24($sp)
    sw      $s6,28($sp)
    sw      $s7,32($sp)
    la      $a0,header              # load address of string to print
    li      $v0,4                   # os service "print_string"
    syscall                         # call the os
    li      $s0,5                   # get this many perfect numbers
    move    $s1,$zero               # want first prime
main_loop:
    move    $a0,$s1                 # get last prime
    jal     next_prime              # get another prime 
    nop
    move    $s1,$v0                 # preserve prime number (p)
    move    $a0,$s1                 # for lucas_lehmer primality test
    jal     lucas_lehmer            # test p
    nop
    beqz    $v0,main_loop           # iterate if mersenne number is not prime
    move    $s2,$v0                 # save m
    addi    $t0,$s0,-5              # gives [-4,0]
    neg     $t0,$t0                 # gives [0,4]
    addiu   $a0,$t0,1               # gives [1,5]
    li      $v0,1                   # os service "print_int"
    syscall                         # call the os
    la      $a0,tabchar             # load address of string to print
    li      $v0,4                   # os service "print_string"
    syscall                         # call the os
    move    $a0,$s1                 # p 
    li      $v0,1                   # os service "print_int"
    syscall                         # call the os
    la      $a0,tabchar             # load address of string to print
    li      $v0,4                   # os service "print_string"
    syscall                         # call the os
    move    $a0,$s2                 # mersenne prime
    li      $v0,1                   # os service "print_int"
    syscall                         # call the os
    la      $a0,tabchar             # load address of string to print
    li      $v0,4                   # os service "print_string"
    syscall                         # call the os
    addiu   $t0,$s1,-1              # p - 1
    li      $t1,1                   # 2^0
    sllv    $t1,$t1,$t0             # 2^(p-1)
    mult    $t1,$s2                 # 2^(p-1) * 2^p - 1
    mflo    $a0                     # perfect number for printing
    li      $v0,1                   # os service "print_int"
    syscall                         # call the os
    la      $a0,newline             # load address of string to print
    li      $v0,4                   # os service "print_string"
    syscall                         # call the os
    addi    $s0,$s0,-1              # decrement counter
    bgtz    $s0,main_loop           # iterate, if there are not enough output
    move    $v0,$s0                 # return code
    lw      $ra,0($sp)
    lw      $s0,4($sp)
    lw      $s1,8($sp)
    lw      $s2,12($sp)
    lw      $s3,16($sp)
    lw      $s4,20($sp)
    lw      $s5,24($sp)
    lw      $s6,28($sp)
    lw      $s7,32($sp)
    addiu   $sp,$sp,36              # return stack space
    jr      $ra
    nop

###############################################################################
# Returns the first prime after $a0 in $v0.
#
# register usage
#   $s0 n
#   $t0 scratch
#
next_prime:
    addiu   $sp,$sp,-8
    sw      $ra,0($sp)
    sw      $s0,4($sp)
    li      $v0,2
    blt     $a0,$v0,np_return       # return 2
    andi    $t0,$a0,1               #test for even
    bne     $t0,$zero,np_odd 
    nop 
    addiu   $a0,$a0,1
    b       np_loop
    nop 
np_odd:
    addiu   $a0,$a0,2
np_loop:
    move    $s0,$a0                 # save n
    li      $a1,5                   # passes
    jal     miller_rabin            # test
    nop 
    bgtz    $v0,np_return           # return if prime
    addiu   $a0,$s0,2               # else add 2 and
    b       np_loop                 # try again
    nop 
np_return:
    lw      $ra,0($sp)  
    lw      $s0,4($sp)
    addiu   $sp,$sp,8
    jr      $ra
    nop 

###############################################################################
# Miller-Rabin Primality test
# Returns zero in $v0 if $a0 (n) is composite. Else, returns $a0 in $v0
# $a1 contains the pass counter
#
# register usage
#   $s0 n - 1                       $s4 pass counter
#   $s1 s                           $s5 used for working copy of s
#   $s2 d                           $s6 constant one
#   $s3 x                           $s7 unused
#
#   $t0 scratch                     $t5 unused
#   $t1 scratch                     $t6 unused 
#   $t2 scratch                     $t7 unused
#   $t3 scratch                     $t8 unused 
#   $t4 unused                      $t9 unused 
#
miller_rabin:
    addiu   $sp,$sp,-36             # make room for ra & s registers
    sw      $ra,0($sp)              # preserve return address
    sw      $s0,4($sp)
    sw      $s1,8($sp)
    sw      $s2,12($sp)
    sw      $s3,16($sp)
    sw      $s4,20($sp)
    sw      $s5,24($sp)
    sw      $s6,28($sp)
    sw      $s7,32($sp)
    li      $s6,1                   # constant
    sub     $s0,$a0,$s6             # n - 1
    move    $s4,$a1                 # passes
    li      $t0,2                   # test value
    blt     $a0,$t0,mr_composite    # no primes less than 2
    li      $t0,4                   # test value
    blt     $a0,$t0,mr_n_is_prime   # n is 2 or 3
    and     $t0,$a0,$s6             # t0 = n & 1
    beqz    $t0,mr_composite        # n is greater than 2 and even
    move    $s2,$s0                 # d = n - 1
    move    $s1,$zero               # s (iteration counter)
mr_loop0:                           # do while d is even
    sra     $s2,$s2,1               # d >>= 1
    addu    $s1,$s1,$s6             # s++
    and     $t0,$s2,$s6             # d still even?
    beqz    $t0,mr_loop0            # iterate
    nop 
mr_loop_1:                          # do $s4 times
    lw      $t2,seed                # load previous random number
    sll     $t3,$t2,17              # algorithm from Hyatt & Rittman
    xor     $t2,$t2,$t3             # algorithm from Hyatt & Rittman
    srl     $t3,$t2,15              # algorithm from Hyatt & Rittman
    xor     $t2,$t2,$t3             # algorithm from Hyatt & Rittman
    sw      $t2,seed                # save for next time
    bgez    $t2,mr_no_neg           # is the seed negative?
    nop 
    neg     $t2,$t2                 # yes, get the opposite
mr_no_neg:                          # 0 <= $t2
    addiu   $t3,$s0,-2              # get the range
    div     $t2,$t3                 # for the remainder
    mfhi    $t2                     # [0,n-4]
    addiu   $a0,$t0,2               # add the lower limit 2 <= $a0 <= n - 2
    move    $a1,$s2                 # d (exponent)
    addu    $a2,$s0,$s6             # n (mod on n)
    jal     mod_exp                 # x = random^d % n 
    beq     $v0,$s0,mr_continue     # x == n - 1
    nop 
    beq     $v0,$s6,mr_continue     # x == 1
    move    $s3,$v0                 # x 
    move    $s5,$s1                 # copy of s (used as a counter)
mr_loop_2:
    move    $a0,$v0                 # x (base)
    li      $a1,2                   # e (exponent)
    addu    $a2,$s0,$s6             # n (modulas)
    jal     mod_exp                 # x = x^2 % n
    nop 
    beq     $v0,$s6,mr_composite    # return false if x == 1
    nop 
    beq     $v0,$s0,mr_continue     # break, iterate if x == n - 1
    sub     $s5,$s5,$s6             # decrement s counter
    nop 
    bgtz    $s5,mr_loop_2           # iterate if counter is positive
mr_composite:
    move    $v0,$zero               # false
    b       mr_return
mr_continue:
    sub     $s4,$s4,$s6             # decrement pass counter
    bgtz    $s4,mr_loop_1           # iterate if positive
mr_n_is_prime:
    add     $v0,$s0,$s6             # n 
mr_return:
    lw      $ra,0($sp)
    lw      $s0,4($sp)
    lw      $s1,8($sp)
    lw      $s2,12($sp)
    lw      $s3,16($sp)
    lw      $s4,20($sp)
    lw      $s5,24($sp)
    lw      $s6,28($sp)
    lw      $s7,32($sp)
    addiu   $sp,$sp,36              # return stack space
    jr      $ra
    nop 

################################################################################
#   returns $a0 ^ $a1 % $a2 in $v0 
#
# register usage
#   $a0 base                        $a1 exponent
#   $a2 modulas                     $v0 r 
#
#   $t0 scratch 
#
mod_exp:
    li      $v0,1                   # r
    beqz    $a1,me_exit             # exponent zero, return
me_loop:
    andi    $t0,$a1,1               # test low order bit
    beqz    $t0,me_skip             # skip augmentation if low order bit is zero
    mult    $v0,$a0             
    mflo    $t0
    div     $t0,$a2
    mfhi    $v0                     # r * b % m
me_skip:
    mult    $a0,$a0                 # b *= b
    mflo    $a0
    div     $a0,$a2
    mfhi    $a0                     # b^2 % m 
    sra     $a1,$a1,1               # e >>= 1
    bgt     $a1,$zero,me_loop
    nop 
me_exit:
    jr      $ra
    nop 

################################################################################
#   returns 0 (composite) or 2^p - 1 (prime)
#
# register usage
#   $a0 p
#
#   $t0 m (mersenne number)
#   $t1 s 
#   $t2 loop counter
#
lucas_lehmer:
    li      $t0,1                   # 2^0
    sllv    $t0,$t0,$a0             # 2^p 
    addiu   $t0,$t0,-1              # 2^p - 1
    li      $t1,4                   # s 
    addiu   $t2,$a0,-2              # iterate this many times
    beqz    $t2,ll_prime            # special case when p == 2
ll_loop:
    mult    $t1,$t1                 # s *= s 
    mflo    $t1
    addiu   $t1,$t1,-2              # s -= 2
    div     $t1,$t0
    mfhi    $t1                     # s = (s^2 - 2) % m
    addi    $t2,$t2,-1
    bgtz    $t2,ll_loop             # iterate when non-negative
    nop 
    beqz    $t1,ll_prime            # prime if s == 0
    move    $v0,$zero               # return false
    b       ll_exit
    nop 
ll_prime:
    move    $v0,$t0                 # return a mersenne prime
ll_exit:
    jr      $ra
###############################################################################
\$\endgroup\$
5
\$\begingroup\$

Comments

Overall, I think you do a really great job with your comments. You clearly separate each section of code, state its purpose, list the register usage (very important for assembly), and do not have many obvious comments spread throughout. You pretty much have that part nailed down.

I just have a few minor things to address:

  • You don't need to add a comment for every syscall. This can be added as a general comment at the top of the procedure(s) or the program.

  • Don't be afraid to add a summary comment on top or to the side of a block of similar code. This may be beneficial for large procedures that execute instructions that can be explained with one comment on top or to the side (like you did with the # preserve return address comment).

Structure

You also do pretty well with structure. It's not too difficult to follow the code. Labels clearly stand out and the respective instructions are indented well.

I do still have some additional things to say about this:

  • Put appropriate linebreaks within procedures:

    You may separate the syscalls, especially since there are so many of them.

    For larger procedures, you may separate the jmps and branches, especially if there are around the middle of the procedure. The ones at the end are okay as-is, especially since they're most commonly there. It would be good to make it clear if a procedure will ever jump or branch, otherwise it may be assumed that it will always fall to the next one (no change in the flow).

  • It may help to give the loop labels more accurate names.

    You should especially give distinction for nested loops. Even then, you would probably indent nested loops further unless this common style is to be maintained.

    Consider stating the type of loop used, such as for (counter), while (pre-test), or do-while (post-test). This may be an important distinction as it would otherwise take close reading of the code to determine the type of loop being used.

|improve this answer|||||
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.