Consider the following high-level recursive procedure: long long int f(long long

Question

Consider the following high-level recursive procedure:

long long int f(long long int n, long long int k) {

long long int b;   

b=k+2;

if (n==0) b = 8;

else b = b + 4 * n + f(n-1,k+1);   

return b + k;

}

Translate the high-level procedure f into ARMv8 assembly language.

-Pay particular attention to properly saving and restoring registers across procedure calls;

-Use the ARMv8 preserved register convention;

-Clearly comment your code;

-Assume that the procedure starts at address 0x00400100;

-Keep local variable b in X19;

-Assume n and k are passed in X0 and X1 respectively and that the result is returned in X2.

IN ARM NOT MIPS

Explanation / Answer

Assembler level Recursion

int fact(int n) {
if (n==0)
return 1;
else
return n*fact(n-1);
}

int main(void) {
return fact(5);
}

int palindrome(char* str, int length) {
if (length<=1)
return 1;
else
return (palindrome(str+1, length-2) && (*str== *(str+length-1)));
}

Program code:
*Assembler directives:

FALSE EQU 0
TRUE EQU 1

ORG $2000
PALIN_STR DC.B 'QWWQ'
LENGTH DC.L 4


*Program code   
ORG $3000
LEA #$6000,SP
PEA PALIN_STR
ADD.L #-1,LENGTH
MOVE.L LENGTH,-(SP)
BSR PALINDROME
ADDQ.L #8,SP clean up stack (good practice)

*Our answer is now in D0 (0 = False, 1= TRUE)

  
PALINDROME: LINK A6,#-12
MOVEM.L A0/A1/D1,-(SP) save registers used in the subroutine   
MOVE.L #FALSE,D0 assume not palindrome   
TST.L 8(A6) test length
BLE PASS if length is <=0, then it is palindrome
MOVE.L 12(A6),A0 a0 now points to first char of the str
MOVE.L 12(A6),A1
ADDA.L 8(A6),A1 a1 now points to last char of the str
MOVE.B (A0),D1
CMP.B (A1),D1 check if first & last chars are the same
BNE FAIL if they aren't exit, else:   
MOVE.L 12(A6),-(SP) push str address on the stack   
ADD.L #1,(SP) take off first caracter
MOVE.L 8(A6),-(SP) push length of str on the stack
ADD.L #-2,(SP) reduce lenght by 2 (to get inner str)   
BSR PALINDROME
ADD.L #8,SP restore the stack   
TST.L D0 test if the inner str is a palindrome
BEQ FAIL exit if not (0 is already in D0)
PASS: MOVE.L #1,D0 else the str is a palindrome
MOVEM.L (SP)+,A0/A1/D1 restore registers
FAIL: UNLK A6
RTS   
END $3000
OR

loop code Recursion

import os

def get_dirlist(path):
"""
Return a sorted list of all entries in path.
This returns just the names, not the full path to the names.
"""
dirlist = os.listdir(path)
dirlist.sort()
return dirlist

def print_files(path, prefix = ""):
""" Print recursive listing of contents of path """
if prefix == "": # Detect outermost call, print a heading
print("Folder listing for", path)
prefix = "| "

dirlist = get_dirlist(path)
for f in dirlist:
print(prefix+f) # Print the line
fullname = os.path.join(path, f) # Turn name into full pathname
if os.path.isdir(fullname): # If a directory, recurse.
print_files(fullname, prefix + "| ")

import pygame, math
pygame.init() # prepare the pygame module for use

# Create a new surface and window.
surface_size = 1024
main_surface = pygame.display.set_mode((surface_size,surface_size))
my_clock = pygame.time.Clock()

def draw_tree(order, theta, sz, posn, heading, color=(0,0,0), depth=0):

trunk_ratio = 0.29 # How big is the trunk relative to whole tree?
trunk = sz * trunk_ratio # length of trunk
delta_x = trunk * math.cos(heading)
delta_y = trunk * math.sin(heading)
(u, v) = posn
newpos = (u + delta_x, v + delta_y)
pygame.draw.line(main_surface, color, posn, newpos)

if order > 0: # Draw another layer of subtrees

# These next six lines are a simple hack to make the two major halves
# of the recursion different colors. Fiddle here to change colors
# at other depths, or when depth is even, or odd, etc.
if depth == 0:
color1 = (255, 0, 0)
color2 = (0, 0, 255)
else:
color1 = color
color2 = color

# make the recursive calls to draw the two subtrees
newsz = sz*(1 - trunk_ratio)
draw_tree(order-1, theta, newsz, newpos, heading-theta, color1, depth+1)
draw_tree(order-1, theta, newsz, newpos, heading+theta, color2, depth+1)

def gameloop():

theta = 0
while True:

# Handle evente from keyboard, mouse, etc.
ev = pygame.event.poll()
if ev.type == pygame.QUIT:
break;

# Updates - change the angle
theta += 0.01

# Draw everything
main_surface.fill((255, 255, 0))
draw_tree(9, theta, surface_size*0.9, (surface_size//2, surface_size-50), -math.pi/2)

pygame.display.flip()
my_clock.tick(120)

gameloop()
pygame.quit()

test(recursive_min([2, 9, [1, 13], 8, 6]) == 1)
test(recursive_min([2, [[100, 1], 90], [10, 13], 8, 6]) == 1)
test(recursive_min([2, [[13, -7], 90], [1, 100], 8, 6]) == -7)
test(recursive_min([[[-13, 7], 90], 2, [1, 100], 8, 6]) == -13)

test(count(2, []), 0)
test(count(2, [2, 9, [2, 1, 13, 2], 8, [2, 6]]) == 4)
test(count(7, [[9, [7, 1, 13, 2], 8], [7, 6]]) == 2)
test(count(15, [[9, [7, 1, 13, 2], 8], [2, 6]]) == 0)
test(count(5, [[5, [5, [1, 5], 5], 5], [5, 6]]) == 6)
test(count("a",
[["this",["a",["thing","a"],"a"],"is"], ["a","easy"]]) == 4)

test(flatten([2,9,[2,1,13,2],8,[2,6]]) == [2,9,2,1,13,2,8,2,6])
test(flatten([[9,[7,1,13,2],8],[7,6]]) == [9,7,1,13,2,8,7,6])
test(flatten([[9,[7,1,13,2],8],[2,6]]) == [9,7,1,13,2,8,2,6])
test(flatten([["this",["a",["thing"],"a"],"is"],["a","easy"]]) ==
["this","a","thing","a","is","a","easy"])
test(flatten([]) == [])

C program for Recursion

#include <stdio.h>
#include <stdlib.h>

struct node
{
int a;
struct node *next;
};

void generate(struct node **);
void display(struct node *);
void stack_reverse(struct node **, struct node **);
void delete(struct node **);

int main()
{
struct node *head = NULL;

generate(&head);
printf(" The sequence of contents in stack ");
display(head);
printf(" Inversing the contents of the stack ");
if (head != NULL)
{
stack_reverse(&head, &(head->next));
}
printf(" The contents in stack after reversal ");
display(head);
delete(&head);

return 0;
}

void stack_reverse(struct node **head, struct node **head_next)
{
struct node *temp;

if (*head_next != NULL)
{
temp = (*head_next)->next;
(*head_next)->next = (*head);
*head = *head_next;
*head_next = temp;
stack_reverse(head, head_next);
}
}

void display(struct node *head)
{
if (head != NULL)
{
printf("%d ", head->a);
display(head->next);
}
}

void generate(struct node **head)
{
int num, i;
struct node *temp;

printf("Enter length of list: ");
scanf("%d", &num);
for (i = num; i > 0; i--)
{
temp = (struct node *)malloc(sizeof(struct node));
temp->a = i;
if (*head == NULL)
{
*head = temp;
(*head)->next = NULL;
}
else
{
temp->next = *head;
*head = temp;
}
}
}

void delete(struct node **head)
{
struct node *temp;
while (*head != NULL)
{
temp = *head;
*head = (*head)->next;
free(temp);
}
}

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.