*****
Lab 1
*****

In this lab, we will learn how to work with an ARM processor and the basics of ARM assembly by programming some common routines. The following lecture content will be required for conducting this lab: compare instructions, branch instructions, shift instructions, load and store instructions, subroutines and function calls.


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 :code:`R0` through :code:`R3`. (If more than four arguments are required, the caller should :code:`PUSH` the arguments onto the stack.)
- Call the subroutine using :code:`BL` Function.

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

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

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

**Fibonacci calculation using iteration**

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

.. code-block:: c

    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, :code:`Fib(n)` using recursion using

.. code-block:: c

    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**

#. Write an assembly program that uses iteration to compute the nth Fibonacci number. (n: any positive integer)
#. 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 :code:`C` consists of deeply nested *for* loops:

.. code-block:: c

    // 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 :code:`C` and using pointers.

.. _algorithm: https://en.wikipedia.org/wiki/Bubble_sort

.. code-block:: c

    // 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**

#. Understand the C program of the bubble sort algorithm, add comments to the C program if necessary.

#. 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 :code:`Fib` function (**10%**).
* Part 1.2: assembly implementation of the recursive :code:`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**

.. important::
   
   Note that we will check every submission (code and report) for possible plagiarism. All suspected cases will be reported to the faculty. Please make sure to familiarize yourself with the course policies regarding Academic Integrity and remember that all the labs **are to be done individually**. Also please note that you are not allowed to use a compiler to generate the assembly code and must write it by hand.

The demo will take place in person during the week of 4-8 October 2021 on the day of you **assigned lab session day**. We will provide a registration system for the demo the week before. You will need to answer live questions during the demo and show your working programs.