ECSE324 Lab 1 solution

Part 1

In this part, your task is to implement the Fibonacci number generator using iterative and recursive algorithms.

The subroutine calling convention

It is important to carefully respect subroutine calling conventions in order to prevent call stack corruption. The convention which we will use for calling a subroutine in ARM assembly is as follows.

The caller (the code that is calling a function) must:

• Move arguments into R0 through R3. (If more than four arguments are required, the caller should PUSH the arguments onto the stack.)
• Call the subroutine using BL Function.

The callee (the code in the function that is called) must:

• Move the return value into R0.
• Ensure that the state of the processor is restored to what it was before the subroutine call by POP ing arguments off of the stack.
• Use BX LR LR to return to the calling code.

Note that the state of the processor can be saved and restored by pushing R4 through LR onto the stack at the beginning of the subroutine and popping R4 through LR off the stack at the end of the subroutine.

Fibonacci calculation using iteration

The C code below describes an iterative algorithm of the Fibonacci number generator Fib(n) (where Fib(0) = 0, Fib(1) = 1, Fib(2) = 1, Fib(3) = 2, …).

int Fib(int n) {

    int f[n + 2]; // array to store Fibonacci numbers. 1 extra to handle n = 0
    int i;

    f[0] = 0;
    f[1] = 1;

    for(i = 2; i <= n; i++)
    {
       f[i] = f[i - 1] + f[i - 2];
    }
    return f[n];
}

Fibonacci calculation using recursive subroutine calls

A recursive subroutine is a subroutine which calls itself. You can calculate the nth Fibonacci number, Fib(n) using recursion using

int Fib(int n) {

    if (n <= 1)
        return n;
    else
        return Fib(n-1) + Fib(n-2);
}

For example, Fib(5) is computed (using recursion) as follows:

Fib(5) = Fib(4) + Fib(3) = (Fib(3) + Fib(2)) + (Fib(2) + Fib(1)) = ([Fib(2) + Fib(1)] + [Fib(1) + Fib(0)]) + ([Fib(1) + Fib(0)] + Fib(1))

= ([[Fib(1) + Fib(0)] + Fib(1)] + [Fib(1) + Fib(0)]) + ([Fib(1) + Fib(0)] + Fib(1)) = 5.

Part 1 Exercises

1. Write an assembly program that uses iteration to compute the nth Fibonacci number. (n: any positive integer)
2. Write an assembly program that uses recursive function calls to compute the nth Fibonacci number. (n: any positive integer)

Part 2

In this problem you will be implementing the 2D convolution algorithm that is usually used in image processing applications. For example, 2D convolutions are used to implement image filters in your favorite social media applications and to detect objects using machine learning.

A straightforward implementation of 2D convolution in C consists of deeply nested for loops:

// Initialization
int fx [10][10] ={
    {183, 207, 128, 30, 109, 0, 14, 52, 15, 210},
    {228, 76, 48, 82, 179, 194, 22, 168, 58, 116},
    {228, 217, 180, 181, 243, 65, 24, 127, 216, 118},
    {64, 210, 138, 104, 80, 137, 212, 196, 150, 139},
    {155, 154, 36, 254, 218, 65, 3, 11, 91, 95},
    {219, 10, 45, 193, 204, 196, 25, 177, 188, 170},
    {189, 241, 102, 237, 251, 223, 10, 24, 171, 71},
    {0, 4, 81, 158, 59, 232, 155, 217, 181, 19},
    {25, 12, 80, 244, 227, 101, 250, 103, 68, 46},
    {136, 152, 144, 2, 97, 250, 47, 58, 214, 51}
}; // 2D Image

int kx [5][5] = {
    {1,   1,  0,  -1,  -1},
    {0,   1,  0,  -1,   0},
    {0,   0,  1,   0,   0},
    {0,  -1,  0,   1,   0},
    {-1, -1,  0,   1,   1}
}; // Kernel

int gx [10][10]; // Output Result

int iw = 10; // Image Width   = 10
int ih = 10; // Image Height  = 10
int kw =  5; // Kernel Width  = 5
int kh =  5; // Kernel Height = 5
int ksw = 2; // Kernel Width Stride  = (Kernel Width-1)/2
int khw = 2; // Kernel Height Stride = (Kernel Height-1)/2

// 2D Convolution Algorithm
for (int y = 0; y < ih ; y++) {
  for (int x = 0; x < iw ; x++) {
    int sum = 0;
    for (int i = 0; i < kw ; i++) {
      for (int j = 0; j < kh ; j++) {
        int temp1 = x+j -ksw;
        int temp2 = y+i -khw;
        if (temp1>=0 && temp1<=9 && temp2>=0 && temp2<=9)
          sum = sum + kx[j][i] * fx [temp1][temp2];
      }
    }

    gx[x][y] = sum;
  }
}

/* Output: Array = {
       {656 ,160 ,113 ,72 ,-51 ,-430 ,23 ,333 ,-70 ,-191 },
       {586 ,261 ,99 ,33 ,200 ,294 ,161 ,299 ,-378 ,-431},
       {217 ,631 ,482 ,311 ,86 ,-31 ,-30 ,-64 ,148 ,-9},
       {-68 ,256 ,485 ,319 ,-96 ,17 ,208 ,271 ,285 ,125},
       {-99 ,-77 ,404 ,691 ,354 ,-427 ,-389 ,0 ,211 ,205},
       {43 ,103 ,244 ,497 ,420 ,101 ,-142 ,123 ,67 ,38},
       {85 ,660 ,344 ,199 ,571 ,838 ,38 ,-468 ,-408 ,9 },
       {12 ,137 ,-40 ,-138 ,98 ,697 ,316 ,-295 ,55 ,215},
       {-170 ,-211 ,-282 ,88 ,507 ,409 ,352 ,235 ,222 ,208},
       {39 ,-142 ,-301 ,-351 ,92 ,72 ,-62 ,427 ,624 ,517},
   }
*/

Part 2 Exercise

Write an assembly program that implements 2D convolution. Note that fx, image and kernel sizes, are all parameters passed to the program. You may assume that the input image and kernel are square.

Part 3

In this part, your task is to implement the bubble sort algorithm. Below is an example of the bubble sort algorithm implemented in C and using pointers.

// Initialization
int size = 5;
int array[] = {-1, 23, 0, 12, -7};
int *ptr = &array[0];

// Bubble sort algorithm
for (int step = 0; step < size - 1; step++) {
  for (int i = 0; i < size - step - 1; i++) {

    // Sorting in ascending order.
    // To sort in descending order, change ">" to "<".
    if (*(ptr + i) > *(ptr + i + 1)) {
      // Swap if the larger element is in a later position.
      int tmp = *(ptr + i);
      *(ptr + i) = *(ptr + i + 1);
      *(ptr + i + 1) = tmp;
    }
  }
}
// Output: Array = {-7,  -1,  0,  12,  23}

Part 3 Exercises

1. Understand the C program of the bubble sort algorithm, add comments to the C program if necessary.
2. Write an assembly program that implements the bubble sort algorithm to sort a given array in ascending order. Note that the the array and its length (size) are input parameters of the program.

Grading and Report

Your grade will be evaluated through the deliverables of your work during the demo (70%) (basically showing us the working programs), your answers to the questions raised by the TA’s during the demo (10%), and your lab report (20%).

Grade distribution of the demo:

• Part 1.1: assembly implementation of the iterative Fib function (10%).
• Part 1.2: assembly implementation of the recursive Fib function (20%).
• Part 2: assembly implementation of the 2D convolution algorithm (20%).
• Part 3: assembly implementation of the bubble sort algorithm (20%).

Failure to follow subroutine calling conventions will result in 50% reduction of your grade for each part.

Write up a short report (~1 page per part) that should include the following information.

• A brief description of each part completed (do not include the entire code in the body of the report).
• The approach taken (e.g., using subroutines, stack, etc.).
• The challenges faced, if any, and your solutions.
• Possible improvevement to the programs.

Your final submission should be sumitted on myCourses. The deadline for the submission and the report is Friday, 15 October 2021. A single compressed folder should be submitted in the .zip format, that contains the following files:

• Your lab report in pdf format: StudentID_FullName_Lab1_report.pdf
• The assembly program for Part 1.1: part1_1.s
• The assembly program for Part 1.2: part1_2.s
• The assembly program for Part 2: part2.s
• The assembly program for Part 3: part3.s