CMPT 295 – Spring 2021
Assignment 5
Objectives:
 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].
CMPT 295 – Spring 2021
 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
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.
CMPT 295 – Spring 2021
 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:
1 -2 3 -4 A00 A01 A02 A03
A = -5 6 -7 8 = A10 A11 A12 A13
-1 2 -3 4 A20 A21 A22 A23
5 -6 7 -8 A30 A31 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 -1 5
A = -5 6 -7 8 AT = -2 6 2 -6
-1 2 -3 4 3 -7 -3 7
5 -6 7 -8 -4 8 4 -8
We reverse the columns of the transpose matrix AT, by swapping the last column with the
first column, the penultimate column with the second column, etc...
Using the same example as above, here is what AT looks like once it has been reversed. We
call this final matrix A’:

1 -5 -1 5 5 -1 -5 1
AT = -2 6 2 -6 A’ = -6 2 6 -2
3 -7 -3 7 7 -3 -7 3
-4 8 4 -8 -8 4 8 -4
As you can see, A’ is the rotated version of A (A has been rotated by 90 degrees clockwise).
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.

CMPT 295 – Spring 2021
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



















Register Table:









































































































































































































































学霸联盟