Conversion of recursive C function into ARM assembly?

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?

2 Answers

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}

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