Question

. Finally the penny drops with your boss. He realises this all has some impact on how he writes his programs. He says he doesn’t understand how the simple instructions you described can be used to implement his complex programs. He knows the compiler must achieve this somehow, but has no clue what it might do. You decide to show him using the iterative solution to a most frequently recursive problem – determining fibonacci numbers. You focus on the body of the function rather than the function call elements of the code.
In doing so you recall learning in Programming Languages that in C we are guaranteed that logic expressions will be “short cut”, that is only as many terms of the expression will be evaluated as is necessary to determine the logic value. In the case of ||, as soon as one of the expressions evaluates to true, then no more of the expressions will be evaluated.

int fibonacci(int number) {
int f, d, t, i;
if (number == 0 || number == 1) {
f = number;
} else {
}
}
return f; }
f = 1;
d = 1;
for (i = 0; i < number - 2; i++) {
t = f;
f = f + d;
d = t;
i. Translate the above C source code into ARM assembly language, showing each stage in the process. (You don’t need to translate the function call and return parts).
ii. Explain why we might get unexpected results when using bitwise and (&) instead of logical and (&&)
iii. Explain how shortcutting simplifies the evaluation of the || expression in the code you have just translated.

Answer 1

The given above code must be written as,

int fibonacci(int number) {

int f, d, t, i;

if (number == 0 || number == 1) {

f = number;

}

else

{

f = 1;

d = 1;

for (i = 0; i < number - 2; i++) {

t = f;

f = f + d;

d = t;

}

}

return f; }

i. The Fibonacci sequence Translation

Each new term in the Fibonacci sequence is generated by adding the previous two terms. By starting with 1 and 2, the first 10 terms will be:

1, 2, 3, 5, 8, 13, 21, 34, 55, 89 and so on...

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

fibonacci(int):

        push    rbp

        mov     rbp, rsp

        mov     DWORD PTR [rbp-20], edi

        cmp     DWORD PTR [rbp-20], 0

        je      .L2

        cmp     DWORD PTR [rbp-20], 1

        jne     .L3

.L2:

        mov     eax, DWORD PTR [rbp-20]

        mov     DWORD PTR [rbp-4], eax

        jmp     .L4

.L3:

        mov     DWORD PTR [rbp-4], 1

        mov     DWORD PTR [rbp-8], 1

        mov     DWORD PTR [rbp-12], 0

.L5:

        mov     eax, DWORD PTR [rbp-20]

        sub     eax, 2

        cmp     DWORD PTR [rbp-12], eax

        jge     .L4

        mov     eax, DWORD PTR [rbp-4]

        mov     DWORD PTR [rbp-16], eax

        mov     eax, DWORD PTR [rbp-8]

        add     DWORD PTR [rbp-4], eax

        mov     eax, DWORD PTR [rbp-16]

        mov     DWORD PTR [rbp-8], eax

        add     DWORD PTR [rbp-12], 1

        jmp     .L5

.L4:

        mov     eax, DWORD PTR [rbp-4]

        pop     rbp

        ret

ii. Explanation

The logical and operator ‘&&’ expects its operands to be boolean expressions (either 1 or 0) and returns a boolean value.
The bitwise and operator ‘&’ works on Integral (short, int, unsigned, char, bool, unsigned char, long) values and return Integral value.

iii. Shortcutting the code

In c programming

int fibonacci(int number) {

int f, d, t, i;

f = number==0?1:number;

d = 1;

for (i = 0; i < number - 2; i++) {

t = f;

f = f + d;

d = t;

}

return f; }

Translation for above code in assembly language

fibonacci(int):

        push    rbp

        mov     rbp, rsp

        mov     DWORD PTR [rbp-20], edi

        cmp     DWORD PTR [rbp-20], 0

        je      .L2

        mov     eax, DWORD PTR [rbp-20]

        jmp     .L3

.L2:

        mov     eax, 1

.L3:

        mov     DWORD PTR [rbp-4], eax

        mov     DWORD PTR [rbp-8], 1

        mov     DWORD PTR [rbp-12], 0

.L5:

        mov     eax, DWORD PTR [rbp-20]

        sub     eax, 2

        cmp     DWORD PTR [rbp-12], eax

        jge     .L4

        mov     eax, DWORD PTR [rbp-4]

        mov     DWORD PTR [rbp-16], eax

        mov     eax, DWORD PTR [rbp-8]

        add     DWORD PTR [rbp-4], eax

        mov     eax, DWORD PTR [rbp-16]

        mov     DWORD PTR [rbp-8], eax

        add     DWORD PTR [rbp-12], 1

        jmp     .L5

.L4:

        mov     eax, DWORD PTR [rbp-4]

        pop     rbp

        ret

Explanation

The ternary operator is used to simplify your if-else statements that are used to assign values to variables and could reduce the lines of compilation in your code.