Description
Learning Objectives
Here are the learning objectives of this assignment, which will be examined in this week’s quiz.
They are a subset of the unit learning objectives listed on Canvas and Slide 2 of Unit 1b.
After completing this assignment you should be able to:
1. translate between array-element offsets and indices;
2. distinguish static and dynamic computation for access to global scalars and arrays in C;
3. translate between C and assembly language for access to global scalars and arrays;
4. translate between C and assembly for code that performs simple arithmetic;
5. explain the difference between arrays in C and Java; and
6. use C’s dereference and address-of operators and pointer arithmetic to access elements of
arrays.
Overview
This assignment has three parts. First you will examine three C programs that access arrays and
translate them into assembly language. Then, you will investigate dynamic arrays and pointers
in C by writing a bit of C code. Finally, you will answer some questions about C pointer
arithmetic.
Questions 1-3: Writing Assembly [48%]
The code file for this week is found here: www.students.cs.ubc.ca/~cs-213/cur/assignments/a3/
code.zip.
This file contains a directory named examples that contains a set of example C programs and
their sm213 assemble-code implementation. The code file also contains three C files named
q1.c, q2.c, and q3.c.
Start with the examples. Carefully examine each of them. Run the assembly versions in the
simulator, step by step. Compare their execution to the C versions. Get comfortable with this
translation from C to assembly and with how assembly executes in the machine.
Now, that you’re getting comfortable, take the first of the C files that don’t have assembly,
q1.c, and produce your own sm213 file, q1.s, that does what this program does; just the parts
of it that are indicated in the C file. Note that you can run the C program, specifying input values
on the command line to see what the program should do. In the simulator you’ll enter the inputs
directly in the memory locations of variables and you’ll examine the output the same way.
Every line of your assembly file must have a comment. The comment should explain what the
line does by referencing C syntax whenever possible. For example, if an assembly instruction
loads the value of a variable into a register, the comment should name that variable. Do the same
for the other C file.
Be sure to end your programs with a “halt” instruction so that the simulated CPU stops when it
reaches the end of your program. If you don’t do this, then it will keep running, interpreting
whatever if finds in memory as instructions, probably doing very strange things.
We suggest that you start this by translating only the first line of C into assembly. Then, test this
assembly in the simulator. Be sure it works, then add the second line and repeat. This is the best
way to implement any program. You should try to almost always have something that runs and
that you’ve tested. Make small changes and re-test. Don’t try to write the whole then and then
test it.
Now do the same for q2.c and q3.c, translating it into q2.s and q3.s.
For all of this work you can either use your implementation of the simulator from Assignment 2
or the reference implementation (i.e., SimpleMachine213.jar) that was distributed with
Assignment 1 and is also available for download in the Resources section on Canvas.
How to Compile a C program
A C program consists of one or more files with extensions “.c” or “.h”. Files ending in “.c” are C
source code. Files ending in “.h” are header (i.e., interface) files. Every program has at least one
“.c” file. Some will use multiple “.c” files and the “.h” files will describe the interface each of
them provides to the other. To import an interface, a “.c” file must include initial lines of the
form ‘#include “foo.h”’. In this assignment, every program consists of a single “.c” file
and so there are no “.h” files. Subsequent assignments will be more complex.
There are many dialects of C out in the wild. In this course we will use the 2011 GNU dialect,
which is common (and the default on MacOS, but not on Linux). Dialects differ slightly in
syntax and so you have to tell the compiler which dialect you are intending to use. You do this
by adding the string “-std=gnu11” as a compiler option (note 11 is eleven, as in 2011).
Another thing you have to tell the compiler is the name of the program you want it to create.
You do this with the “-o foo” option (to make a program called foo). If you don’t include
this option, the compiler places the output in a file called a.out.
So, let’s say you want to compile e1.c to produce an executable named e1. You would type the
following at the command line.
gcc -std=gnu11 -o e1 e1.c
Question 4 [36%]
Overview
In www.students.cs.ubc.ca/~cs-213/cur/assignments/a3/code.zip, you will find a file named
bubble_sort_static.c that takes as input up to 4 integers on the command line and uses
the Bubble Sort algorithm to sort them.
You compile this program like this (again that’s “gnu eleven”)
gcc -std=gnu11 -o bubble_sort_static bubble_sort_static.c
You run it like this:
./bubble_sort_static 78 3 43 1
Read this C file carefully.
Just like q1.c and q2.c, this program’s main function has two parameters: argc and argv.
In Java it is similar: main has one parameter, an array of strings. That’s what argc and argv
are: argc is the number of stings found on the command line that started the program (5 in the
case of the example) and argv is a dynamic array that contains each of these strings. In C, a
string is simply an array of char (i.e., a char*) that is terminated by the first NUL character
(i.e., 0) in the array.
You will also see that main copies these values into a static global array named val. This array
is statically assigned a length of 4 and so the input is limited to 4 numbers.
Finally, once main has copied the input values into val, it calls sort to sort the values and
then prints out the result. Your output should be formatted the same as
bubble_sort_static.c, one number per line in ascending order and nothing else.
Step 1: Modify the C program to use a dynamic array [18%]
The first step is to create a new C program named bubble_sort_dynamic.c that removes
the static-array limitation of the original version. The only change you need to make is to turn
val into a dynamic array and to allow the program to sort arbitrary lists of integers provided on
the command line (e.g., more than 4).
Recall that you need to allocate dynamic arrays dynamically by calling the procedure malloc.
For example to allocate an array of 10 shorts you say:
short *s = malloc (10 * sizeof(*s));
Be sure to test your program.
Step 2: C Pointers [18%]
Now, create another C program called bubble_sort_awesome.c that extends your earlier
work to remove all square brackets from your program. All access to the arrays must be made
using pointer arithmetic and the dereference operator (i.e., “*”). Test this too.
Questions 5-7 [16%]
Answer These Questions
Place your answers in files named q5.txt, q6.txt, and q7.txt. Note that if you aren’t sure
of the answers, you can always write a C program and have it tell you the answer.
Assume that the array a is declared and initialized like this:
int a[10] = {0,1,1,2,3,5,8,13,21,34};
5. What is the value of: *(a+3)?
6. What is the value of: &a[7] – &a[2]?
7. What is the value of: *(a + (&a[7]-a+2))?
What to Hand In
Use the handin program from the command line.
The assignment directory is ~/cs213/a3, it should contain the following plain-text files.
1. Your code for Questions 1-3: q1.s, q2.s and q3.s.
2. You code for Question 4: bubble_sort_dynamic.c and
bubble_sort_awesome.c.
3. You answers to questions 5 to 7: q5.txt, q6.txt, and q7.txt.
