Ece252 Manual

User Manual:

Open the PDF directly: View PDF .
Page Count: 44

Download
Open PDF In Browser	View PDF

Electrical and Computer Engineering
(ECE) Systems Programming and
Concurrency ECE252 Laboratory
Manual
by

Yiqing Huang
Jeff Zarnett

Electrical and Computer Engineering Department
University of Waterloo

Waterloo, Ontario, Canada, May 29, 2019

c Y. Huang and J. Zarnett 2019

Contents
List of Tables

List of Figures

Preface

II
1

Lab Administration
Lab Projects

Introduction to Systems Programming in Linux Computing Environment

1.1

Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.1.1

Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.1.2

Topics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.2

Starter Files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.3

Pre-lab Preparation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.4

Basic Linux Commands Exercises . . . . . . . . . . . . . . . . . . . . . .

1.5

Lab Assignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.6

1.7

1.5.1

Problem statement . . . . . . . . . . . . . . . . . . . . . . . . . . 10

1.5.2

The findpng command . . . . . . . . . . . . . . . . . . . . . . . . 10

1.5.3

The catpng command . . . . . . . . . . . . . . . . . . . . . . . . 12

Deliverables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16
1.6.1

Pre-lab deliverables . . . . . . . . . . . . . . . . . . . . . . . . . . 16

1.6.2

Post-lab Deliverables . . . . . . . . . . . . . . . . . . . . . . . . . 16

Marking Rubric . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

Multi-threaded Programming with Blocking I/O

2.1

Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.2

Starter Files . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

2.3

Pre-lab Preparation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.4

Lab Assignment . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.5

2.6

2.7

2.4.1

Problem Statement . . . . . . . . . . . . . . . . . . . . . . . . . . 19

2.4.2

Requirements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

2.4.3

Man page of paster . . . . . . . . . . . . . . . . . . . . . . . . . . 21

Programming Tips . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.5.1

The libcurl API . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

2.5.2

The pthreads API . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

Deliverables . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.6.1

Pre-lab deliverables . . . . . . . . . . . . . . . . . . . . . . . . . . 23

2.6.2

Post-lab Deliverables . . . . . . . . . . . . . . . . . . . . . . . . . 23

Marking Rubric . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

III Software Development Environment Quick Reference Guide
24
1

Introduction to ECE Linux Programming Environment

1.1

ECE Linux Servers . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25

1.2

Connecting to Linux servers . . . . . . . . . . . . . . . . . . . . . . . . . 25

1.3

Basic Software Development Tools . . . . . . . . . . . . . . . . . . . . . 27

1.4

1.5

1.3.1

Editor . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28

1.3.2

C Compiler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

1.3.3

Debugger . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29

More on Development Tools . . . . . . . . . . . . . . . . . . . . . . . . . 30
1.4.1

How to Automate Build . . . . . . . . . . . . . . . . . . . . . . . 30

1.4.2

Version Control Software . . . . . . . . . . . . . . . . . . . . . . 32

1.4.3

Integrated Development Environment . . . . . . . . . . . . . . . 33

Man Page . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

A Forms

iii

References

List of Tables
0.1

Project Deliverable Weight of the Lab Grade, Scheduled Lab Sessions
and Deadlines. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1.1

IHDR data field and value . . . . . . . . . . . . . . . . . . . . . . . . . . 15

1.2

Lab1 Marking Rubric . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

2.1

Lab2 Marking Rubric . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

Programming Steps and Tools . . . . . . . . . . . . . . . . . . . . . . . . 28

List of Figures
1.1

Image Concatenation Illustration . . . . . . . . . . . . . . . . . . . . . . 10

MobaXterm Path on ECE Nexus Windows 10 Machines.

MobaXterm Welcome Page. . . . . . . . . . . . . . . . . . . . . . . . . . 26

MobaXterm Welcome Page. . . . . . . . . . . . . . . . . . . . . . . . . . 27

Linux files on P drive, a network mapped drive. . . . . . . . . . . . . . 28

. . . . . . . . 26

Preface
Who Should Read This Lab Manual?
This lab manual is written for students who are taking Electrical and Computer Engineering (ECE) Systems Programming and Concurrency course ECE252 in the University of Waterloo.

What is in This Lab Manual?
The first purpose of this document is to provide the descriptions of each laboratory
project. The second purpose of this document is a quick reference guide of the relevant development tools for completing laboratory projects. This manual is divided
into three parts.
Part I describes the lab administration policies
Part II is a set of course laboratory projects as follows.
• Lab1: Introduction to systems programming in Linux computing environment
• Lab2: Multi-threaded concurrency programming with blocking I/O
• Lab3: Inter-process communication and concurrency control
• Lab4: Parallel web crawling
• Lab5: Single-threaded concurrency programming with asynchronous I/O
Part III is a quick reference guide of the Linux software development tools. We
will be using Ubuntu 18.04 LTS operating system. Materials in this part needs to be
self-studied before lab starts. The main topics are as follows.
• Linux hardware environment
• Editors
• Compiler
• Debugger
1

• Utility to automate build
• Utility for version control

Acknowledgments
We are grateful that Professor Patrick Lam shared his ECE459 projects with us. Eric
praetzel has provided continuous IT support, which makes the Linux computing
environment available to our students.
We would like to sincerely thank our students who took ECE254 and ECE459
courses in the past few years. They provided constructive feedback every term to
make the manual more useful to address problems that students would encounter
when working on each lab assignment.

Part I
Lab Administration

Lab Administration Policy
Group Lab Policy
• Group Size. All labs are done in groups of two. A size of three is only considered in a lab section that has an odd number of students and only one group
is allowed to have a size of three. All group of three requests are processed
on a first-come first-served basis. A group size of one is not permitted except
that your group is split up. There is no workload reduction if you do the labs
individually. Everyone in the group normally gets the same mark. The Learn
at URL http://learn.uwaterloo.ca is used to signup for groups. The lab
group signup is due by 10:00pm on the Second Friday of the academic term. Late
group sign-up is not accepted and will result in losing the entire lab sign-up
mark, which is 2% of the total lab grade.
• Group Split-up. If you notice workload imbalance, try to solve it as soon as
possible within your group or split-up the group as the last resort. Group splitup is only allowed once. You are allowed to join a one member group after the
split-up. But you are not allowed to split up from the newly formed group
again. There is one grace day deduction penalty to be applied to each member in the old group. We highly recommend everyone to stay with your group
members as much as possible, for the ability to do team work will be an important skill in your future career. Please choose your lab partners carefully. A
copy of the code and documentation completed before the group split-up will
be given to each individual in the group.
• Group Split-up Deadline. To split from your group for a particular lab, you
need to notify the lab instructor in writing and sign the group slip-up form (see
Appendix). Labn (n=1,2,3,4) group split-up form needs to be submitted to the
lab instructor by 4:30pm Thursday in the week that Labn has scheduled lab sessions. If you are late to submit the split-up form, then you need to finish Labn
as a group and submit your split-up form during the week where Lab(n+1) has
scheduled sessions and split starting from Lab(n+1).

Deliverable
Group Sign-up
LAB 1
LAB 2
LAB 3
LAB 4
LAB 5

Weight
2%
18%
20%
20%
20%
20%

Lab Session Week
N/A
Week 3
Week 5
Weeks 8
Week 10
Week 12

Deadline
10:00 pm Friday in Week 2
10:00 pm Wednesday in Week 4
10:00 pm Friday in Week 6
10:00 pm Wednesday in Week 9
10:00 pm Wednesday in Week 11
10:00 pm Last day of lecture

Table 0.1: Project Deliverable Weight of the Lab Grade, Scheduled Lab Sessions and
Deadlines.

Lab Assignments Grading and Deadline Policy
Labs are graded by lab TAs based on the rubric listed in each lab. The weight of each
lab towards your final lab grade is listed in Table 0.1.
• Lab Assignment Preparation and Due Dates. Students are required to prepare
the lab well before they come to the schedule lab session. Pre-lab deliverable for
each lab is due before the scheduled lab session starts. During the scheduled lab
session, we either provide in lab help or conduct lab assignment evaluation or
do both at the same time.
The detailed deadlines of post-lab deliverables are displayed in Table 0.1.
• Lab Assignment Late Submissions. Late submission is accepted within five
days after the deadline of the lab. No late submission is accepted five days after
the lab deadline. There are five grace days 1 that can be used for some post-lab
deliverables late submissions 2 . A group split-up will consume one grace day.
After all grace days are consumed, a 10% per day late submission penalty will
be applied. However if it is five days after the lab deadline, no late submission
is accepted.
• Lab Re-grading. To initiate a re-grading process, contact the grading TA in
charge first. The re-grading is a rigid process. The entire lab will be re-graded.
Your new grades may be lower, unchanged or higher than the original grade
received. If you are still not satisfied with the grades received after the regrading, escalate your case to the lab instructor to request a review and the lab
instructor will finalize the case.
1

Grace days are calendar days. Days in weekends are counted.
A post-lab deliverable that does not accept a late submission will be clearly stated in the lab
assignment description. Normally grace days are for lab reports. Labs whose evaluation involves
demonstrations do not accept late submissions of the code.
2

Lab Repeating Policy
For a student who repeats the course, labs need to be re-done with a new lab partner.
Simply turning in the old lab code is not allowed. We understand that the student
may choose a similar route to the solution chosen last time the course was taken.
However it should not be identical. The labs will be done a second time, we expect
that the student will improve the older solutions. Also the new lab partner should
be contributing equally, which will also lead to differences in the solutions.
Note that the policy is course specific to the discretion of the course instructor
and the lab instructor.

Lab Assignments Solution Internet Policy
It is not permitted to post your lab assignment solution source code or lab report
on the internet freely for public to access. For example, it is not acceptable to host a
public repository on GitHub that contains your lab assignment solutions. A warning
with instructions to take the lab assignment solutions off the internet will be sent out
upon the first offence. If no action is taken from the offender within twenty-four
hours, then a lab grade zero will automatically be assigned to the offender.

Seeking Help Outside Scheduled Lab Hours
• Discussion Forum. We recommend students to use the Piazza discussion forum to ask the teaching team questions instead of sending individual emails to
lab teaching staff. For questions related to lab projects, our target response time
is one business day before the deadline of the particular lab in question 3 . There
is no guarantee on the response time to questions of a lab that passes the submission
deadline.
• Office Hours. The Learn system calendar gives the office hour details.
• Appointments. Students can also make appointments with lab teaching staff
should their problems are not resolved by discussion forum or during office
hours. The appointment booking is by email.
To make the appointment efficient and effective, when requesting an appointment, please specify three preferred times and roughly how long the appointment needs to be. On average, an appointment is fifteen minutes per project
group. Please also summarize the main questions to be asked in your appointment requesting email. If a question requires teaching staff to look at a
3

Our past experiences show that the number of questions spike when deadline is close.The teaching staff will not be able to guarantee one business day response time when workload is above average, though we always try our best to provide timely response.

code fragment, please bring a laptop with necessary development software installed.
Please note that teaching staff will not debug student’s program for the student. Debugging is part of the exercise of finishing a programming assignment.
Teaching staff will be able to demonstrate how to use the debugger and provide case specific debugging tips. Teaching staff will not give direct solution
to a lab assignment. Guidances and hints will be provided to help students to
find the solution by themselves.

Lab Facility After Hour Access Policy
After hour access to the lab will be given to the class when we start to use the Keil
boards in lab. However please be advised that the after hour access is a privilege.
Students are required to keep the lab equipment and furniture in good conditions to
maintain this privilege.
No food or drink is allowed in the lab. Please be informed that you may share
the lab with other classes. When resources become too tight, certain cooperation is
required such as taking turns to use the stations in the lab.

Part II
Lab Projects

Lab 1
Introduction to Systems Programming
in Linux Computing Environment
1.1
1.1.1

Introduction
Objectives

This lab is to introduce system programming in a general Linux Development Environment at ECE Department. After finishing this lab, students will be able to
• apply basic Linux commands to interact with the Linux system through shell;
• apply standard Linux C programming tools for system programming and
• create a program to interact with Linux file systems by applying the relevant
system and libray calls.

1.1.2

Topics

Concretely, the lab will cover the following topics:
• Basic Linux commands
• C programming toolchain including gcc, make, and ddd
• Linux manual pages
• Linux system calls and file I/O library calls to traverse a directory and perform
read/write operations on selected files.

1.2

Starter Files

The starter files are on GitHub at url: http://github.com/yqh/ece252/tree/master/
lab1/starter. It contains the following sub-directories where we have example code
and image files to help you get started:
• the cmd arg demonstrates how to capture command line input arguments;
• the images contains some image files;
• the ls demonstrates how to list all files under a directory and obtain file types;
• the png util provides a set of utility functions to process a PNG image file; and
• the pointer demonstrates how to use pointers to access a C structure.
Using the code in the starter files is permitted and will not be considered as plagiarism.

1.3

Pre-lab Preparation

Read the Introduction to ECE Linux Programming Environment supplementary material in Part III Chapter 1.

1.4

Basic Linux Commands Exercises

These in-lab exercises are to practice some basic commands on Linux.
1. Use the MobaXterm to login onto eceubuntu.uwaterloo.ca . You are
now inside the Linux shell and in your home directory. The home directory
usually has a path name in the format of /home/username, where username
normally is your UWID. For example, a user with UWID of jsmith has a home
directory of /home/jsmith.
2. Use the pwd command to print the full filename of the current working directory. You should see your home directory name printed on the screen. For
example: /home/jsmith.
3. Use the echo $HOME command to print your home directory path name.
You will notice that the output matches the pwd output of exercise 2.
4. Use the env command to list all the environment variables and their values.
Note that HOME is one of the many environment variables.
5. One important environment variable is PATH. It specifies a set of directories
the system searches for executible programs. Use echo $PATH to see your
PATH environment variable setting.
8

6. Execute command which ls to locate the directory the ls command is in.
You will notice the directory is listed in PATH environment variable. When
you issue a command and get an error message of “command not found”, it
means the command cannot be found after searching all the directories listed
in PATH environment variable. A commonly seen error is that a command in
your current working directory gives you “command not found“ error. This
is normally due to the fact that the current working directory . or ./ is not in
the PATH. Consequently you need to add the path to the command name for
the system to know where the command is. For example ./a.out tells the
system to run the command a.out located in the current working directory.
7. Use the ls command to list all files in your current working directory.
8. Read the online manual of the ls command by issuing man ls command to
the shell. Find out from the manual what options -l, -a and -la do. Execute
the ls command with these three options and see the execution results.
9. Create a directory as the work space of labs under your home directory. Name
the newly created directory as labs. Read the man page of the command
mkdir to see how to do it.
10. Change directory to the newly create directory of labs. Read the man page of
command cd to find out how to change directory.
11. Clone the ece252 lab repository by using the command:
git clone https://github.com/yqh/ece252.git .
A new directory named ece252 will be created. It has lab manual and starter
code of ECE252 labs.
12. Read the man page of the find command by issuing man find command
to the shell. Read what the -name option does. Use find with the -name
option to find all the files with .png file extension in the $HOME/labs/ece252
directory.
13. Change directory to where the WEEF_1.png is. Use file WEEF 1.png
command to obtain the file type and image properties such as dimensions and
bit depth.
14. Use file command to obtain the file type information of Disguise.png.
You should see that this is not an image file though the file exension is .png.
Use a text editor to open the file and see the contents. This exercise is to show
you that the file command does not obtain the file type information based
on the file extension. It looks into the contents of file to extract the file type
information 1 .
1

A file has a magic number to indicate its type. The magic number is a sequence of bytes usually
appearing near the beginning of the file. The file command checks the magic number. The PNG file’s
magic number is 89 50 4E 47 in hexadecimal, which is .PNG in ASCII.

1.5

Lab Assignment

1.5.1

Problem statement

You are given a directory under which some
files are PNG images and some files are not. The
directory may contain nested sub-directories2 .
All valid PNG images under the given directory are horizontal strips of a bigger whole image. They all have the same width. The height
of each image might be different. The PNG images have the naming convention of *_N.png,
where N is the image strip sequence number and
N=0, 1, 2, .... However a file with .png or
.PNG extension may not be a real PNG image
file. You need to located all the real PNG image files under the given directory first. Then
you will concatenate these horizontal strip images sequentially based on the sequence numFigure 1.1: Image Concatenation
ber in the file name to restore the original whole
Illustration
image. The sequence number indicates the order the image should be concatenated from top
to bottom. For example, file img_1.png is the first horizontal strip and img_2.png
is the second horizontal strip. To concatenate these two strips, the pixel data in
img_1.png should be followed immediately by the pixel data in img_2.png file.
Figure 1.1 illustrates the concatenation order.
To solve the problem, first you will create a tool named findpng to search the
given directory hierarchy to find all the real PNG files under it. Secondly you will
create an image data concatenation tool named catpng to concatenate pixel data of
a set of PNG files to form a single PNG image file. The catpng only processes PNG
images with the same width in dimension.

1.5.2

The findpng command

The expected behaviour of the findpng is given in the following manual page of
the command.
2

A nested sub-directory is a sub-directory that may contain many layers of sub-directories.

Man page of findpng
NAME
findpng - search for PNG files in a directory hierarchy
SYNOPSIS
findpng DIRECTORY
DESCRIPTION
Search for PNG files under the directory tree rooted at DIRECTORY and return the search results to the standard output. The command does not follow
symbolic links.
OUTPUT FORMAT
The output of search results is a list of PNG file relative path names, one file
pathname per line. The order of listing the search results is not specified. If the
search result is empty, then output “findpng: No PNG file found”.
EXAMPLES
findpng .
Find PNG of the current working directory. A non-empty search results might
look like the following:
./lab1/sandbox/new_bak.png
./lab1/sandbox/t1.png
./png_img/rgba_scanline.png
./png_img/v1.png
An empty search result will look like the following:
findpng: No PNG file found

Searching PNG files under a given directory
UNIX file system is organized as a tree. A file has a type. Three file types that this
assignment will deal with are regular, directory and symbolic link. A PNG file is a
regular file. A directory is a directory file. A link created by ls -n is a symblic link.
Read the section 2 of stat family system calls man page for information about
other file types. The ls/ls_ftype.c in the starter code gives a sample program to
determine the file type of a given file.
To search all the files under a given directory and its subdirectories, one need
to traverse the given directory tree to its leaf nodes. The library call of opendir
returns a directory stream for readdir to read each entry in a directory. One need
to call closedir to close the directory stream once operations on it is completed.
The control flow is to go through each entry in a directory and check the file type.
If it is a regular file, then further check whether it is a PNG file by comparing the
first 8 bytes with the PNG file header bytes (see Section 1.5.3). If it is a directory file,
then you need to check files under the sub-directory and repeat what you did in the
parent directory. The ls/ls_fname.c in the starter code gives a sample program
that lists all file entries of a given directory.
Always check the man page of the systems calls and library calls for detailed
information.

1.5.3

The catpng command

The expected behaviour of the catpng is given in the following manual page of the
command.
Man page of the catpng
NAME
catpng - concatenate PNG images vertically to a new PNG named all.png
SYNOPSIS
catpng [PNG FILE]...
DESCRIPTION
Concatenate PNG FILE(s) vertically to all.png, a new PNG file.

OUTPUT FORMAT
The concatenated image is output to a new PNG file with the name of all.png.
EXAMPLES
catpng ./img1.png ./png/img2.png
Concatenate the listed PNG images vertically to all.png.
File I/O
There are two sets of functions for file I/O operations under Linux. At system call
level, we have the unbufferred I/O functions: open , read , write , lseek and
close . At library call level, we have standard I/O functions: fopen , fread
, fwrite , fseek and fclose . The library is built on top of unbufferred
I/O functions. It handles details such as buffer allocation and performing I/O in
optimal sized chunks to minimize the number of read and write usage, hence
is recommended to be used for this lab.
The fopen returns a FILE pointer given a file name and the mode. A PNG
image file is a binary file, hence when you call fopen , use mode ” rb ” for reading
and ” wb+ ” for reading and writing, where the ”b” indicates it is a binary file that
we are opening. Read the man page of fopen for more mode options.
After the file is opened, use fread to read the number of bytes from the stream
pointed by the FILE pointer returned by fopen . Each opened file has an internal
state of file position indicator. The file position indicator sets to the beginning of the
file when it is just opened. The fread operation will advance the file position
indicator by the number of bytes that has been read from the file. The fseek sets
the file position indicator to the user specified location. The fwrite writes user
specified number of bytes to the stream pointed by the FILE pointer. The file position
indicator also advances by the number of bytes that has been written. It is important
to call fclose to close the file stream when I/O operations are finished. Failure to
do so may result in incomplete files.
The man pages of the standard I/O library is the main reference for details including function prototypes and how to use them.
PNG File Format
In order to finish this assignment, one need to have some understanding of the png
file format and how an image is represented in the file. One way to store an image
is to use an array of coloured dots referred to as pixels. A row of pixels within an
image is called a scanline. Pixels are ordered from left-to-right within each scanline.
13

Scanlines appear top-to-bottom in the pixel array. In this assignment, each pixel is
represented as four 8-bit 3 unsigned integers (ranging from 0 to 255) that specify the
red, green, blue and alpha intensity values. This encoding is often referred to as the
RGBA encoding. RGB values specify the colour and the alpha value specifies the
opacity of the pixel. The size of each pixel is determined by the number of bits per
pixel. The dimensions of an image is described in terms of horizontal and vertical
pixels.

(a) PNG File Format

(b) PNG Chunk Format

PNG stands for “Portable Network Graphics”. It is a computer file format for
storing, transmitting and displaying images[2]. A PNG file is a binary file. It starts
with an 8-byte header followed by a series of chunks. You will notice the second,
third and fourth bytes are the ASCII code of ’P’, ’N’ and ’G’ respectively (see Figure
1.2(a)).
The first chunk is the IHDR chunk, which contains meta information of the image
such as the dimensions of the pixels. The last chunk is always the IEND chunk,
which marks the end of the image datastream. In between there is at least one IDAT
chunk which contains the compressed filtered pixel array of the image. There are
other types chunks that may appear between IHDR chunk and IEND chunk. For all
the PNG files we are dealing with in this assignment, we use the format that only
has one IHDR chunk, one IDAT chunk and one IEND chunk (see Figure 1.2(a)).
Each chunk consists of four parts. A four byte length field, a four byte chunk type
code field, the chunk data field whose length is specified in the chunk length field,
and a four byte CRC (Cyclic Redundancy Check) field (see Figure 1.2(b)).
The length field stores the length of the data field in bytes. PNG file uses big
endian byte order, which is the network byte order. When we process any PNG data
that is more than one byte such as the length field, we need to convert the network
byte order to host order before doing arithmetic. The ntohl and htonl library
3

Formally, we say the image has a bit depth of 8 bits per sample.

calls convert a 32 bit unsigned integer from network order to host order and vice
versa respectively.
The chunk type code consists four ASCII character. IHDR, IDAT and IEND are
the three chunk type code that this assignment involves with.
The data field contains the data bytes appropriate to the chunk type. This field
can be of zero length.
The CRC field calculates on the proceeding bytes in the type and data fields of
the chunk. Note that the length field is not included in the CRC calculation. The
crc function under the png_util starter code can be used to calculate the CRC
value.
The IHDR chunk data field has a fixed
length of 13 bytes and they appear in the
order as shown in Table 1.1. Width and Name
Length Value
height are four-byte unsigned integers
4 bytes N/A
giving the image dimensions in pixels. Width
You will need these two values to com- Height
4 bytes N/A
plete this assignment. Bit depth gives the
1 byte
8
number of bits per sample. In this as- Bit depth
signment, all images have a bit depth of Colour type
1 byte
6
8. Colour type defines the PNG image
Compression method 1 byte
0
type. All png images in this assignment
1 byte
0
have a colour type of 6, which is truecolor Filter method
with alpha (i.e. RGBA image). The image Interlace method
1 byte
0
pixel array data are filtered to prepare
for the next step of compression. The
Table 1.1: IHDR data field and value
Compression method and Filter method
bytes encode the methods used. Both
only have 0 values defined in the current
standard. The Interlace method indicates the transmission order of the image data. 0
(no interlace) and 1 (Adam7 interlace) are the only two defined. In this assignment,
all PNG images are non-interlaced. Table 1.1 Value column gives the typical IHDR
values the PNG images you will be processing.
The IDAT chunk data field contains compressed filtered pixel data. For each scanline, first an extra byte is added at the very beginning of the pixel array to indicate
the filter method used. Filtering is for preparing the next step of compression. For
example, if the raw pixel scanline is 4 bytes long, then the scanline after applying filter will be 5 bytes long. This added one byte per scanline will help to achieve better
compression result. After all scanlines have be filtered, then the data are compressed
according to the compression method encoded in IHDR chunk. The compressed data
stream conforms to the zlib 1.0 format.
The IEND chunk marks the end of the PNG datastream. It has an empty data
field.

Concatenate the pixel data
To concatenate two horizontal image strips, the natural way of thinking is to start
with the pixel array of each image and then concatenate the two pixel arrays vertically. Then we apply the filter to each scanline. Lastly we compress the filtered pixel
array to fill the data field of the new IDAT chunk of the concatenated image. However a simpler way exists. We can start with the filtered pixel data of each image and
then concatenate the two chunks of filtered pixel data arrays vertically, then apply
the compression method to generate the data field of the new IDAT chunk.
How do we get filtered pixel data from a PNG IDAT chunk? Recall that the
data field in IDAT chunk is compressed data that conforms to zlib format 1.0. We
can use zlib functions to uncompress(i.e. inflate) the data. The mem inf in the
starter code takes in memory compressed(i.e. deflated) data as input and returns the
uncompressed data to a another memory location. For each IDAT chunk you want
to concatenate, call this function and stack the returned data in the order you wish
and then you have the concatenated filtered pixel array. To create an IDAT chunk,
we need to compress the filtered pixel data. The mem def function in the starter
code uses the zlib to compress (i.e. deflate) the input in memory data and returns
the deflated data. The png_util directory in the starter code demos how to use the
aforementioned two functions.
To create a new PNG for the concatenated images, IHDR chunk also needs to
have the new dimension information of the new PNG file. The rest of the fields of
IHDR chunk can be kept the same as one of the PNG files to be concatenated. In
this assignment, we assume that catpng can only process PNG files whose IHDR
chunks only differ in the height field. So the new image will have a different height
field, the rest of fields are the same as the input images.

1.6
1.6.1

Deliverables
Pre-lab deliverables

There is no pre-lab deliverable.

1.6.2

Post-lab Deliverables

The following are the steps to create your post-lab deliverable submission.
• Create a directory and name it lab1.
• Put the entire source code with a Makefile under the directory lab lab1. The
Makefile default target includes catpng and findpng. That is command
make should generate the aforementioned two executable files. We also ex-

pect that command make clean will remove the object code and the default
target. That is the .o files and the two executable files should be removed.
• Use zip command to zip up the contents of lab1 directory and name it lab1.zip.
We expect unzip lab1.zip will produce a lab1 sub-directory in the current
working directory and under the lab1 sub-directory is your source code and
the Makefile.
Submit the lab1.zip file to Lab1 Dropbox in Learn.

1.7

Marking Rubric
Points
10
35
55

Description
Makefile correctly builds and cleans
Implementation of findpng
Implementation of catpng
Table 1.2: Lab1 Marking Rubric

Table 1.2 shows the rubric for marking the lab.

Lab 2
Multi-threaded Programming with
Blocking I/O
2.1

Objectives

This lab is to learn about and gain practical experience in multi-threaded programming in a general Linux environment. A single-thread implementation using blocking I/O to request a resource across the network is provided. Students are asked
to reduce the latency of this operation by sending out multiple requests simultaneously to different machines by using the pthreads library. After this lab, students
will have a good understanding of
• how to design and implement a multi-threaded program by using the pthreads
library; and
• the role mutli-threading plays in reducing the latency of a program.

2.2

Starter Files

The starter files are on GitHub at url: http://github.com/yqh/ece252/tree/master/
lab2/starter. It contains the following sub-directories where we have example code
to help you get started:
• the cURL demonstrates how to use cURL to fetch an image segment from the
lab web server;
• the fn ptr demonstrates how C function pointers work;
• the getopt demonstrates how to parse command line options;
• the pthreads demonstrates how to create two threads where each thread takes
multiple input parameters and return multiple values; and
18

• the times provides helper functions to profile program execution times.
Using the code in the starter files is permitted and will not be considered as plagiarism.

2.3

Pre-lab Preparation

Build the starter code and run the executables. Work through the code and understand what they do and how they work. Create a single-threaded implementation of
the paster command.

2.4

Lab Assignment

2.4.1

Problem Statement

In the previous lab, a set of horizontal strips of a whole PNG image file were stored
on a disk and you were asked to restore the whole image from these strips. In this
lab, the horizontal image segments are on the web. I have three 400 × 300 pictures
(whole images) on three web servers. When you ask a web server to send you a
picture, the web server crops the picture into fifty 400 × 6 equally sized horizontal
strips 1 . The web server assigns a sequence number to each strip from top to bottom
starting from 0 and increments by 1 2 . Then the web server sleeps for a random
time and then sends out a random strip in a simple PNG format that we assumed
in lab1. That is the horizontal strip PNG image segment consists one IHDR chunk,
one IDAT chunk and one IEND chunk (see Figure 1.2(a)). The PNG segment is an
8-bit RGBA/color image (see Table 1.1 for details). The web server uses an HTTP
response header that includes the sequence number to tell you which strip it sends to
you. The HTTP response header has the format of “X-Ece252-Fragment: M ” where
M ∈ [0, 49]. To request a random horizontal strip of picture N , where N ∈ [1, 3], use
the following URL: http://machine:2520/image?img=N, where
machine is one of the following:
• ece252-1.uwaterloo.ca,
• ece252-2.uwaterloo.ca, and
• ece252-3.uwaterloo.ca .
For example, when you request data from the following URL:
http://ece252-1.uwaterloo.ca:2520/image?img=1,
1

Each image segment will have a size less than 8KB.
The first horizontal strip has a sequence number of 0, the second strip has a sequence number of
1. The sequence number increments by 1 from top to bottom and the last strip has a sequence number
of 49.
2

you may receive a random horizontal strip of picture 1. Assume this random strip
you receive is the third horizontal strip (from top to bottom of the original picture),
the received HTTP header will contain “X-Ece52-Fragment: 2“. The received data
will be the image segment in PNG format. You may use the browser to view a random horizontal strip of the PNG image the server sends. You will notice the same
URL displays a different image strip every time you hit enter to refresh the page.
Each strip has the same dimensions of 400 × 6 pixels and is in PNG format.
Your objective is to request all horizontal strips of a picture from the server and
then concatenate these strips to restore the original picture. Because every time the
server sends a random strip, if you use a loop to keep requesting a random strip
from a server, you may receive the same strip multiple times before you receive all
the fifty distinct strips. Due to the randomness, it will take a variable amount of time
to get all the strips you need to restore the original picture.

2.4.2

Requirements

Use the pthreads library, design and implement a threaded program to request
all image segments from a web server by using blocking I/O and concatenate these
segments together to form the whole image.
The provided starter code main_write_header_cb.c under cURL directory
is a single-threaded implementation which uses libcurl blocking I/O function
curl_easy_peform()to fetch one random horizontal strip of picure 1 from one
of the web servers into memory and then output the received image segment to a
PNG file. Your program should repeatedly fetch the image strips until you have
them all. Recall because every time you get a random strip, the amount of time to
get all the fifty distinct strips of a picture varies.
A very inefficient approach is to use a single-threaded loop to keep fetching until
you get all fifty distinct strips of a picture and paste them together. You will notice
the blocking I/O operation is the main cause of the latency. Your program will be
blocked while each time waiting for the curl_easy_perform() to finish. One
way to reduce the latency of this operation is to send out multiple blocking I/O
requests simultaneously (to different machines) by using pthreads. You will use
this approach to reduce the latency in this lab 3 .
Your program should create as many threads as specified by the user command
line input, and distribute the work among the three provided servers. Make sure
all of your library (standard glibc and libcurl) calls are thread-safe (for glibc, e.g.
man 3 printf to look at the documentation). Name your executable as paster.
The behaviour of the command paster is given in the following section.
The provided three pictures on the server are for you to test your program. Your
program should work for all these pictures. You may want to reuse part of your lab1
code to paste the received image segments together.
3

Asynchronous I/O is another method to reduce the latency and we will explore it in lab5.

2.4.3

Man page of paster

NAME
paster - pasting downloaded png files together by using multiple threads and
blocking I/O through libcurl.
SYNOPSIS
paster [OPTION]...
DESCRIPTION
With no options, the command retrieves all horizontal image segments of picture 1 from http://ece252-1.uwaterloo.ca:2520/image?img=1 and paste all distinct segments received from top to bottom in the order of the image segment
sequence number. Output the pasted image to disk and name it output.png.
-t=NUM
create NUM threads simultaneously requesting random image segments
from multiple lab web servers. When this option is not specified, assumes
a single-threaded implementation.
-n=NUM
request a random image segment of picture NUM from the web server.
Valid values are 1, 2 and 3. Default value is set to 1.
OUTPUT FORMAT
The concated image is output to a PNG file with the name of output.png.
EXAMPLES
paster -t 6 -n 2
Use 6 threads to simultaneously download all image segments of picture 2
from multiple web servers and concatenate these segments to restore picture 2.
Output the concatenated picture to disk and name it output.png.

2.5
2.5.1

Programming Tips
The libcurl API

Though the image segment download code using libcurl is provided, familiarize yourself with the libcurl API will help you understand the provided code. The
libcurl documentation URL is https://curl.haxx.se/libcurl. The man page of each
function in the libcurl API can be found at URL https://curl.haxx.se/libcurl/c/
allfuncs.html.
Note the provided example cURL code downloads the received image segment
to memory and then output the data in memory to a PNG file. The output to a
PNG file is just to make it easier for you to view the downloaded image segment
to help you understand the example code. However your paster program does
not need to output each segment received to a file. An efficient way (i.e. without
unnecessary file I/O) is to directly use the received image segment data in memory
instead of outputting the data to a file first and then reading the data back from file
into memory.
Thread Safety
Libcurl is thread safe but there are a few exceptions. The man page of libcurlthread(3) (see https://curl.haxx.se/libcurl/c/threadsafe.html) is the ultimate reference. We re-iterate key points from libcurl manual that are relevant to this lab as
follows:
• The same libcurl handle should not be shared in multiple threads.
• The libcurl is thread safe but does not have internal thread synchronization
mechanism. You will need to take care of the thread synchronization.

2.5.2

The pthreads API

The pthreads(7) man page gives an overview of POSIX threads and should be
read. The SEE ALSO section near the bottom of the man page lists functions in the
API. The man pages of pthread_create(3), pthread_join(3) and pthread_exit(3)
provide detailed information of how to create, join and terminate a thread.
The pthread Memory Leak Bug
There is a known memory leak bug related to pthread_exit(). Please refer to
https://bugzilla.redhat.com/show bug.cgi?id=483821 for details. Using return()
instead of pthread_exit() will avoid the memory leak bug.

2.6
2.6.1

Deliverables
Pre-lab deliverables

None.

2.6.2

Post-lab Deliverables

Create a multi-threaded implementation of the paster command. The following
are the steps to create your post-lab deliverable submission.
• Create a directory and name it lab2.
• Put the entire source code with a Makefile under the directory lab lab2. The
Makefile default target is paster. That is command make should generate
the paster executable file. We also expect that command make clean will
remove the object code and the default target. That is the .o files and the two
executable files should be removed.
• Use zip command to zip up the contents of lab2 directory and name it lab2.zip.
We expect unzip lab2.zip will produce a lab2 sub-directory in the current
working directory and under the lab2 sub-directory is your source code and
the Makefile.
Submit the lab2.zip file to Lab2 Dropbox in Learn.

2.7

Marking Rubric
Points
10
25
65

Description
Makefile correctly builds and cleans paster
Implementation of single-threaded paster
Implementation of multi-threaded paster
Table 2.1: Lab2 Marking Rubric

Table 2.1 shows the rubric for marking the lab.

Part III
Software Development Environment
Quick Reference Guide

Chapter 1
Introduction to ECE Linux
Programming Environment
1.1

ECE Linux Servers

There are a group of Linux Ubuntu servers that are open to ECE undergraduate
students. The machines are listed at url: https://ece.uwaterloo.ca/Nexus/arbeau/
clients. To access one of the machines, we recommend to use the alias name of
eceubuntu.uwaterloo.ca, which will direct the user to the most lightly loaded
machine at the time of login.
To access these machines from off campus. One way is to use the campus VPN.
Another way is to first connect to ecelinux4.uwaterloo.ca or eceterm.uwaterloo.ca
and then connect to other Linux servers from there. Note that the ecelinux4
should not be used for computing jobs, it is for accessing other Linux servers on
campus.

1.2

Connecting to Linux servers

A terminal client software that supports secure shell (ssh) will allow you to remotely
connect to the Linux servers. MobaXterm is a convenient application that not only
supports ssh, but also has a built-in X server that allows one to run Graphical User
Interface (GUI) applications from the Linux servers.
Use the File Explorer to navigate to Q:\eng\ece\Util folder, scroll down until
you find the MobaXterm icon and double click it (see Figure C1). The MobaXterm
window will pop up. There is a grey rectangular button labelled “Start local terminal” in the middle (see Figure C2). Click this button.
Then a terminal session starts. You will need to use the command line ssh command to connect to the Linux server. Use your UWID and password to login. The

Figure C1: MobaXterm Path on ECE Nexus Windows 10 Machines.

Figure C2: MobaXterm Welcome Page.
syntax of the command is as follows:
ssh -XY @eceubuntu.uwaterloo.ca

See Figure C3 for reference.
26

Figure C3: MobaXterm Welcome Page.
All your ECE Linux account files are accessible through P Drive on Nexus machines (See Figure C4). The P Drive is only accessible within campus network. Mapping the Linux account as a network drive off campus is not supported due to security reasons.

1.3

Basic Software Development Tools

To develop a program, there are three important steps. First, a program is started
from source code written by programmers. Second, the source code is then compiled
into object code, which is a binary. Non-trivial project normally contains more than
one source file. Each source file is compiled into one object code and the linker would
finally link all the object code to generate the final target, which is the executable that
runs. The steps of compiling and linking are also known as building a target. It is
very rare that the target will run perfectly the first time it is built. Most of time we
need to fix defects and bugs in the code and the this is the third step. The debugger
is a tool to help you identify the bug and fix it. Table C1 shows the key steps in
programming work flow and example tools provided by a general purpose Linux
operating system.
Most of you probably are more familiar with a certain Integrated Development
27

Figure C4: Linux files on P drive, a network mapped drive.
Task
Tool
Examples
Editing the source code
Editor
vi, emacs
Compiling the source code Compiler gcc
Debugging the program
Debugger gdb, ddd
Table C1: Programming Steps and Tools

Environment (IDE) which integrates all these tools into a single environment. For
example Eclipse and Visual Studio. A different approach is to select a tool in each
programming step and build your own tool chain. Many seasoned Linux programmers build their own tool chains. A few popular tools are introduced in the following
subsections.

1.3.1

Editor

Some editors are designed to better suit programmers’ needs than others. The vi (vim
and gvim belong to the vi family) and emacs (xemacs belongs to emacs family) are the
two most popular editors for programming purposes.
Two simple notepad editors pico and nano are also available for a simple editing
job. These editors are not designed for programming activity. To use one of them to
write your first Hello World program is fine though.
After you finish editing the C source code, give the file name an extension of .c.
Listing 1.1 is the source code of printing ”Hello World!” to the screen.
28

#include
#include
int main()
{
printf("Hello World!\n");
exit(0);
}
Listing 1.1: HelloWorld C source Code

1.3.2

C Compiler

The source code then gets fed into a compiler to be come an executable program.
The GNU project C and C++ compiler is gcc. To compile the HelloWorld source code
in Listing 1.1, type the following command at the prompt:
gcc helloworld.c+

You will notice that a new file named a.out is generated. This is the executable generated from the source code. To run it, type the following command at the prompt
and hit Enter.
./a.out

The result is“Hello World!” appearing on the screen.
You can also instruct the compiler to name the executable another name instead
of the default a.out. The -o option in gcc allows one to name the executable a
name. For example, the following command will generate an executable named
“helloworld.out”.
gcc helloworld.c -o helloworld.out

although there is no requirement that the name ends in .out.

1.3.3

Debugger

The GNU debugger gdb is a command line debugger. Many GUI debugger uses
gdb as the back-end engine. One GNU GUI debugger is ddd. It has a powerful data
display functionality.
29

GDB needs to read debugging information from the binary in order to be able to
help one to debug the code. The -g option in gcc tells the compiler to produce such
debugging information in the generated executable. In order to use gdb to debug our
simple HelloWorld program, we need to compile it with the following command:
gcc -g helloworld.c -o helloworld.out

The following command calls gdb to debug the helloworld.out
gdb helloworld.out

This starts a gdb session. At the (gdb) prompt, you can issue gdb command such
as b main to set up a break point at the entry point of main function. The l lists
source code. The n steps to the next statement in the same function. The s steps
into a function. The p prints a variable value provided you supply the name of the
variable. Type h to see more gdb commands.
Compared to gdb command line interface, the ddd GUI interface is more user
friendly and easy to use. To start a ddd session, type the command
ddd

and click File → Open Program to open an executable such as helloworld.out. You
will then see gdb console in the bottom window with the source window on top
of the gdb console window. You could see the value of variables of the program
through the data window, which is on top of the source code window. Select View
→ to toggle all these three windows.

1.4

Ece252 Manual

Navigation menu

Versions of this User Manual:

Views

Navigation