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
R0throughR3. (If more than four arguments are required, the caller shouldPUSHthe arguments onto the stack.)Call the subroutine using
BLFunction.
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
POPing arguments off of the stack.Use
BX LRLR 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
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 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
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
Fibfunction (10%).Part 1.2: assembly implementation of the recursive
Fibfunction (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.