Conversion of Recursive C Function into Arm Assembly?

Question

For a homework assignment, I've been given a recursive C function to count integer partitions that I need to convert to ARM assembly. Things I know about ARM assembly:

1) R0 will hold the return value of a call

2) R1, R2, and R3 are argument registers

The code is as follows:

int count_partitions(int n, int m) { 

if (n == 0) 
    return 1; 

else if(n < 0) 
    return 0; 

else if (m == 0) 
    return 0; 

else 
    return count_partitions(n - m, m) + count_partitions(n, m - 1); 
}

I believe I have done the first 3 if & else-if statements correctly. My logic for the final else statement was to find count_partitions(n, m-1), store that onto the stack, then find count_partitions(n-m, m), and add that to the previous return value I got from the stack - however my code does not seem to work?

I've attached my attempted solution and have color coded the different segments of C code and their corresponding assembly code. Could anyone let me know what's wrong?

Accepted Answer

I think I see several problems:

You assume that n is in r1. This is actually in r0. m will be in r1, not r2.
For this reason, you need to save both r0 and r1.

One cleaner solution would be to use something like this:

_count_partitions:
    ...             ; First part with comparison
                    ; but r1->r0 and r2->r1

    push {r4-r5}
    mov r4, r0      ; saved value of n
    mov r5, r1      ; saved value of m
    sub r0, r4, r5  ; n = n-m
    bl _count_partitions

    sub r1, r5, #1  ; m = m-1
    mov r5, r1      ; result of first function
    mov r0, r4      ; restore n
    bl _count_partitions

    add r0, r0, r5  ; cumulative result
    pop {r4,r5}
    pop {pc}

Answer 2

You can use this after the CMP command and jump your function:

BEQ label ; BRANCH EQUAL

BNE label ; BRANCH NOT EQUAL

BLE label ; BRANCH LESS THAN EQUAL

BLT label ; BRANCH LESS THAN

BGE label ; BRANCH GREATER THAN EQUAL

BGT label ; BRANCH GREATER THAN

Conversion of Recursive C Function into Arm Assembly?

2 Answers

Must Read

Your Answer

David Miller

Conversion of Recursive C Function into Arm Assembly?

2 Answers

Must Read

Your Answer

Sign up or log in

Post as a guest

David Miller