Modular Exponentiation using mips

Question

Write a program which prompts the user for three positive numbers x, n and p, and outputs x^n mod p. Your program should use the recursive version of modular exponentiation.

 .text
main: 
      sub  $sp,$sp,4                # save return address on stack
      sw   $ra, 0($sp)
    
    li   $v0, 4             # prompt user for int x
    la   $a0, S1
      syscall

      li   $v0, 5                  # read int
      syscall
      move $s0, $v0                # cin >> x //and store x in $s0

    li   $v0, 4             # prompt user for int n
    la   $a0, S1
      syscall

      li   $v0, 5                  # read int
      syscall
      move $s1, $v0                # cin >> n //and store n in $s1
    
    li   $v0, 4             # prompt user for int p
    la   $a0, S1
      syscall

      li   $v0, 5                   # read int
      syscall
      move $s2, $v0                 # cin >> p //and store n in $s2

        
    li $t0, 0               #return value 
    li $t1, 2               #constant 2
    li $t2, 0               #variable y

    beq $s0, $zero, L1      #if x == 0, return 1
    beq $s1, $zero, L2      #if n is 0, return 0

    jal evenMod

L0: 
    lw   $ra, 0($sp)        # read registers from stack
        lw   $s0, 4($sp)
      lw   $s1, 8($sp)
      addi $sp, $sp, 12       # bring back stack pointer
      jr $ra

L1:         
    li $v0, 4
    la $a0, S3
    syscall
    j L0
    

L2:
    li $v0, 4
    la $a0, S4
    syscall
    j L0

L3:
    li $v0, 1
    move $a0, $s1
    syscall
    j L0

evenMod:
    
    beq $s0, $zero, L1      #if x == 0, return 1
    beq $s1, $zero, L2      #if n is 0, return 0
    rem $s3, $s1, $t1           #s3 = s1 % 2
    
    bne $s3, $zero, oddMod      #if n%2 == 0, recursive call for odd

    div $s1, $s1, 2         #n = n/2
    mult $t2, $t2           #y = y*y
    rem $t2, $t2, $s2           #y= (y*y)%c
    jal evenMod
    j L3
    
oddMod:
    
    beq $s0, $zero, L1      #if x == 0, return 1
    beq $s1, $zero, L2      #if n is 0, return 0
    
    rem $s3, $s1, $t1           #s3 = s1 % 2
    
    bne $s3, $zero, evenMod     #if n%2 == 0, recursive call for even

    rem $s3, $s1, $s2           #s3 = s1 % P
    addi $s0, 0             #x stays the same
    add $s1, $s1, -1            #n = n-1
    addi $s2, 0             #p stays the same

    jal oddMod              #call oddmod with updated values
    mult $t2, $t2           #multiply y*y
    rem $t2, $t2, $s2           #y = y%P
    
    j L3
    

.data
S1:
      .asciiz "Enter an integer --> "
S3: 
    .asciiz "0"
S4: 
    .asciiz "1"

This is what I have so far, but I'm getting stuck on where the JALs should occur.

Answer 1

C code:

public static int exponentMod(int A, int B, int C) { 

    //base cases 
    if (A == 0) return 0; 

    if (B == 0) return 1; 

    //If B is even 
    long y; 
    if (B % 2 == 0) { 
        y = exponentMod(A, B / 2, C); 
        y = (y * y) % C; 
    }
    //if B is odd 
    else { 
        y = A % C; 
        y = (y * exponentMod(A, B - 1, C) % C) % C;
    }
 
    //return the modular exponent 
    return (int)((y + C) % C); 

}

Transformation, still in C, to if-goto-label as follows:

public static int exponentMod(int A, int B, int C) { 

    //base cases
    if (A != 0) goto endIf1;
    return 0;
endIf1: 

    if (B != 0) goto endIf2;
    return 1; 
endIf2:

    long y; 
    if (B % 2 != 0) goto elseIf3; 
    // B is even 
    y = exponentMod(A, B / 2, C); 
    y = (y * y) % C;
    goto endIf3;
elseIf3:
    // B is odd 
    y = A % C; 
    y = (y * exponentMod(A, B - 1, C) % C) % C;
endIf3:
 
    //return the modular exponent 
    return (int)((y + C) % C); 

}

The control flow has been converted to the if-goto-label style of assembly, using logical transformations.  (Note that the above transformation remains valid and runnable C, and will run the same as the structured-statement original.)  The if-goto-label version is closer to assembly. 

Of course, there are many other ways to translate the control flow, such as moving blocks of code to different places; however, I prefer the above form that stays true to the statement ordering of original C code, making it easier to follow when comparing the original and the assembly version.

So, what's left to do is transform the non-control flow statements and expressions, which should appear in orientation exactly where they are in this transformation result.