Objectives:
Assignment 5
CMPT 295 – Spring 2021
x86-64 function calls and stack
Recursion in x86-64 assembly code
Manipulating 2D arrays (matrices) in x86-64 assembly code
Submission:
Submit your document called Assignment_5.pdf om CourSys.
o Add your full name and student number at the top of the first page of your document Assignment_5.pdf.
You will need to submit your code on CourSys as well. Refer to the Submission section of Q2 and Q3 for further submission instructions.
Due:
Thursday, March 11 at 3pm
Late assignments will receive a grade of 0, but they will be marked in order to provide
feedback to the student.
Marking scheme:
This assignment will be marked as follows:
o All questions will be marked for correctness.
The amount of marks for each question is indicated as part of the question.
A solution will be posted after the due date.
1. [5 marks] x86-64 function calls and stack
a. Hand trace the code from our Lab 4 (main.c , main.s, p1.c, p1.s, p2.c and p2.s) using the test case, i.e., x = 6, y = 9, buf[40].
As you do so, draw the corresponding Stack Diagram for the entire program, i.e., until you reach (but have not yet executed) the ret instruction of the main function. To do so, you can either print the “Stack Diagram” sheet at the end of this assignment and do the drawing by hand, then scan the result and include it into this assignment document OR do the drawing by electronically annotating the “Stack Diagram” sheet at the end of this assignment then include the result into this assignment document.
The use of the Register Table is optional: use it only if you find it useful. You do not have to include it as part of your assignment document.
Indicate the movement of %rsp by crossing its old location and rewriting “%rsp” to indicate its new location (as we have done in our lectures).
Cross the content of the stack that has been popped.
When the value of a stack location is changed, cross its old value and write the
new value in the same stack location.
Make sure you include the content of buf in your Stack Diagram.
b. Modify main.c by reducing the size of buf[] from 40 to 24.
Remake the code and hand trace it using the following test case, i.e., x = 6, y =
9, buf[24].
Repeat the instructions found in the section a. above and create a second drawing
of the stack using the Stack Diagram sheet found at the end of this assignment.
Make sure you include the content of buf in your Stack Diagram drawing.
Asnwer the question: What happens to the “canary value” in this situation?
2. [5 marks] Recursion in x86-64 assembly code
In this problem, you are asked to rewrite the mul function you wrote in Assisgnment 4. This time, instead of using a loop, you are to use recursion. In doing so, you must use the stack (so we can get some practice), either by pushing/popping or by getting a section of it (e.g., subq $24, %rsp) and releasing it (e.g., addq $24, %rsp) at the end of your program.
Yes, it is certainly possible to recursively implement mul without saving the values of the argument registers (edi and esi) onto the stack. However, for practice’s sake, let’s save them onto the stack as stated in the question.
CMPT 295 – Spring 2021
CMPT 295 – Spring 2021 Use your files from Assignment 4: main.c, makefile and calculator.s. Then, copy
the following and paste it over (replace) your entire mul function in calculator.s:
mul: # performs integer multiplication – when both operands
are non-negative!
# x in edi, y in esi
# Requirements:
# – cannot use imul* instruction
# – you must use recursion (no loop) and the stack
Then go ahead and implement your recursive version of mul.
While doing so, you must satisfy its new requirements (above in green). You must also satisfy
the requirements below. Requirements:
Your code must be commented such that others (i.e., TA’s) can read your code and understand what each instruction does.
About comments:
o Comment of Type 1: Here is an example of a useful comment:
cmpl %edx, %r8d # loop while j < N
o Comment of Type 2: Here is an example of a not so useful comment: cmpl %edx, %r8d # compare %edx with %r8d
Do you see the difference? Make sure you write comments of Type 1.
Make sure you update the header comment block in calculator.s.
You must use the makefile provided in Assignment 4 when compiling your code. This
makefile cannot be modified.
You cannot modify the prototype of the function mul. The reason is that your code may be tested using a test driver built based on this function prototype.
Your code must compile (using gcc) on our target machine and execute on our target machine.
You must follow the x86-64 function call and register saving conventions described in class and in the textbook.
Do not push/pop registers unless you make use of them in your function mul and their content needs to be preseved. Memory accesses are expensive!
Submission:
Electronically submit your file calculator.s via CourSys.
Also copy and paste the content of your calculator.s in this assignment. Make sure it is the same version of calculator.s that compiles and executes on our target machine.
3. [10 marks] Manipulating 2D arrays (matrices) in x86-64 assembly code
In linear algebra, a matrix is a rectangular grid of numbers. Its dimensions are specified by its number of rows and of columns. This question focuses on the representation and manipulation of square matrices, i.e., where the number of rows and the number of columns both equal n.
Here is an example of a square matrix where n = 4:
CMPT 295 – Spring 2021
1 -2 3 -4 A00 A01 A=-56-78 = A10 A11 -1 2 -3 4 A20 A21 5 -6 7 -8 A30 A31
A02 A03 A12 A13 A22 A23 A32 A33
Note the notation Aij refers to the matrix entry at the ith row and the jth column of A. Each row of the matrix A resembles a one dimensional array in the programming language C, with the value of j increasing for each element. The matrix A has i such rows.
Because of this resemblance, matrices can be represented (modeled) in our C programs using two dimensional arrays. One dimensional arrays are stored in contiguous memory space, where their element 0 is followed by their element 1 which is followed by their element 2, etc... Two-dimensional arrays follow a similar pattern when stored in memory: the one row following the other. In other words, the elements from row 0 are followed by the elements from row 1, which are followed by elements of row 2, and so on. Thus, a two dimensional array, representing a n x n matrix, has n2 elements, and the base pointer A, contains the address of the first element of the array, i.e., the 0th element of row 0.
Because of this regular pattern, accessing a two dimensional array element can be done in a
random fashion, where the address of Aij = A + L (i * n + j), where L is the size (in bytes) of each array element. For example, when L = 1, as it is for this assignment, then the element A32 can be found at address A + 1 ( 3 * 4 + 2 ) = A + 14.
In this question, you are asked to rotate a matrix 90 degrees clockwise. One way to do this is to first transpose the matrix then to reverse its columns.
Wikipedia says that, in linear algebra, the transpose of a matrix is an operator which flips a matrix over its diagonal, i.e., it switches the row and column indices of the matrix by producing another matrix denoted as AT. Thank you, Wikipedia.
CMPT 295 – Spring 2021
CMPT 295 – Spring 2021 Here is an example where AT is the transpose of matrix A (using the diagonal “1, 6, -3, -8”):
1 -2 3 -4 1 -5
A=-5 6-78 AT=-2
-1 2 -3 4 3 -7 5 -6 7 -8 -4 8
We reverse the columns of the transpose first column, the penultimate column with
Using the same example as above, here is call this final matrix A’:
-1 5 2 -6 -3 7 4 -8
matrix AT, by swapping the last column with the the second column, etc...
what AT looks like once it has been reversed. We
-5 1 6 -2 -7 3 8 -4
6
1 -5 -1 5 AT=-262-6 3 -7 -3 7 -4 8 4 -8
5 -1 A’= -6 2 7 -3 -8 4
As you can see, A’ is the rotated version of
Your task is to implement these two functions in x86-64 assembly code:
void transpose(void *, int );
void reverseColumns(void *, int n);
When they are called in this order, using a two dimensional array as their first argument, the effect will be to rotate this array by 90 degrees clockwise.
Download Assn5-Files_Q3.zip, expand it and open the files (makefile, main.c and an incomplete matrix.s. ). Have a look at main.c and notice its content. Have a look at matrix.s. It contains functions manipulating matrices such as copy, transpose and reverseColumns. You need to complete the implementation of the functions transpose and reverseColumns. The function copy has already been implemented for you. You may find hand tracing its code useful. You may also want to “make” the given code and see what it does.
A (A has been rotated by 90 degrees clockwise).
Requirements:
Your code must be commented such that others (i.e., TA’s) can read your code and understand what each instruction does.
About comments:
o Comment of Type 1: Here is an example of a useful comment:
cmpl %edx, %r8d # loop while j < N
o Comment of Type 2: Here is an example of a not so useful comment: cmpl %edx, %r8d # compare %edx with %r8d
Do you see the difference? Make sure you write comments of Type 1.
You must add a header comment block to the file matrix.s. This header comment block must include the filename, the purpose/description of its functions, your name, your student number and the date.
You must use the makefile provided when compiling your code. This makefile cannot be modified.
You cannot modify the code that has been supplied to you in the zip file. This signifies that, amongst other things, you must not change the prototype of the functions given. The reason is that these functions may be tested using a test driver built based on these function prototypes.
Your code must compile (using gcc) on our target machine and execute on our target machine.
You must follow the x86-64 function call and register saving conventions described in class and in the textbook.
Do not push/pop registers unless you make use of them in your function mul and their content needs to be preseved. Memory accesses are expensive!
Submission:
Electronically submit your file matrix.s via CourSys.
Also copy and paste the content of your matrix.s in this assignment. Make sure it is the same version of matrix.s that compiles and executes on our target machine.
CMPT 295 – Spring 2021
Base + Displacement Stack Purpose
CMPT 295 – Spring 2021
Register Table: