CSCI 2122 Assignment 2
Due date: 11:59pm, Friday, October 13, 2023, submitted via git
Objectives
The purpose of this assignment is to practice your coding in C, focusing on low-level bit manipulation with
continued use basic constructs such as functions, loops, arrays, and functions from the C standard library.
This assignment is divided into two problems, where the second problem builds on the first. As the second
problem subsumes the first. If you complete Problem 2, you have also completed Problem 1.
Preparation:
1. Complete Assignment 0 or ensure that the tools you would need to complete it are installed.
2. Clone your assignment repository:
https://git.cs.dal.ca/courses/2023-fall/csci-2122/assignment-2 git
where ???? is your CSID. Please see instructions in Assignment 0 and the tutorials on Brightspace if
you are not sure how.
Inside the repository there are two directories: marsdec1 and marsdecx, where code is to be written.
You should set up a separate CLion project for each of these directories, like the labs. Inside each directory
is a tests directory that contains tests that will be executed each time you submit your code. Please do
not modify the tests directory or the .gitlab-ci.yml file that is found in the root directory. Modifying these files may break the tests. These files will be replaced with originals when the assignments are
graded. You are provided with sample Makefile files that can be used to build your program. If you
are using CLion, a Makefile will be generated from the CMakeLists.txt file generated by CLion.
Background
The Mars Reconnaissance Orbiter1 (MRO) is a satellite that orbits Mars. One of its
roles is to receive communications from Earth, decode them, and pass them on to
the rovers on the surface of Mars. The challenge is that sending to Mars is expensive. Consequently, the communications are compressed to reduce the number of
bits that need to be sent. Once the MRO receives a communication, it unpacks the
bits into a sequence of standard size integers and then sends the integer values to
the rovers. You have been hired to develop the unpacking algorithm for the MRO. It needs to be small
and efficient (written in C) and be able to unpack the incoming communication quickly. To help you develop the unpacking decoder, the task has been broken down into two parts. You will first implement a
decoder for the simple version of the communication protocol and then extend the decoder to handle the
full communication protocol.
Problem 1: Just One Byte
Write a C program in main.c in directory marsdec1 that will be compiled into an executable
marsdec1. Your program will read in a series of bytes in hexadecimal notation and decode the stream
of bytes, outputting the decoded integers.
1
https://en.wikipedia.org/wiki/Mars_Reconnaissance_Orbiter
Input
Your program will read its input from stdin. The first line contains a single integer denoting the number
of lines N in the communication. This is followed by N lines, each containing an integer B denoting the
number of bytes on the line, followed by B bytes in hexadecimal notation. (Hint: Use scanf to read
integers and bytes). For the hexadecimal, use the format specifier with "%x".
4
3 0x62 0x69 0x00
4 0xca 0xf1 0x85 0x38
5 0xfb 0xff 0xff 0xff 0xf0
5 0xfc 0x00 0x00 0x00 0x10
For problem 1, the number of bytes will range from 0 to 5. This will increase for Problems 2. Each line
corresponds to an encoding of a single integer. The first 5
bits represent a 5-bit unsigned integer L, followed by an Lbit signed integer. The remaining bits are ignored.
Bit Order
The bits are ordered left to right, with the bytes ordered 0
… 3 and the bits in each byte ordered most significant to
least significant bit (in big-endian). E.g., bit 0 in the figure
on the right is the first bit in the stream and is the most
significant bit of byte 0. Bit 31 is the last bit in the stream
and is the least significant bit of byte 3. The bits are to be
processed in increasing order from 0 to 31.
Processing
For each of the N lines, the program must
• Read in the B bytes and unpack the integer.
• The packed integer is stored in the order of most-significant to least significant bit.
• The number of bytes can range from 0 up to 5 bytes. If there are 0 bytes, then the line has no
integers to unpack.
• The last byte may not be filled. The extra bits can be ignored.
• In this program there is no upper limit on N, the number of lines. But, the program can process
one line at a time and does not need to store anything once the line is processed.
Output
All output should be performed to stdout. The output must be exactly as specified. The output consists
of a list of unpacked integers, one per line. For each unpacked integer, output a line in the format:
Line L, integer 1: X
where L denotes the line in the input containing the packed integer and X is the unpacked integer. Note
that since there is only one integer packed per line, the integer number will always be 1, in Problem 1
Examples
Input Output
8
1 0x08
1 0x0c
1 0x12
2 0x43 0xd8
3 0x62 0x69 0x00
4 0xca 0xf1 0x85 0x38
5 0xfb 0xff 0xff 0xff 0xf0
5 0xfc 0x00 0x00 0x00 0x10
Line 1, integer 1: 0
Line 2, integer 1: -1
Line 3, integer 1: 1
Line 4, integer 1: 123
Line 5, integer 1: 1234
Line 6, integer 1: 12345678
Line 7, integer 1: 1073741823
Line 8, integer 1: -1073741823
Problem 2: The Full Unpack
Copy your main.c from marsdec1 to marsdecx. Extend your program from Problem 1 to handle
multiple encoded integers in a single stream of bytes, as it is more efficient to send multiple integers in a
single bitstream.
Input
The input format is the same as in Problem 1, except
that the bitstream may have consist of more than 5
bytes, and multiple integers may be encoded one after
the other in one bitstream. For example, the bit stream
on the right contains two packed integers. Each integer
consists of a 5-bit length L, followed by an L-bit integer. The end of the byte stream is indicated by either
a length of 0, as shown above, or if the remaining bitstream has 5 or fewer bits, which is not enough to
encode another integer.
Processing
Same as problem 1, except that
• Your program must unpack all integers encoded in a bit stream, not just the first one.
• Your program should stop unpacking a bitstream if it encounters a length of 0 or fewer than 6 bits
remain in the bitstream.
Output
Same output format as for Problem 1, except that the integer number 1 will change. Instead of always
being 1, it will denote the order of the unpacked integers in the bitstream. (See example.)
Examples
Input Output
4
2 0x08 0x30
4 0x12 0x28 0x6c 0x70
8 0x43 0xdb 0x13 0x4b 0x2b 0xc6 0x14 0xe0
9 0xfb 0xff 0xff 0xff 0xff 0xc0 0x00 0x00 0x01
Line 1, integer 1: 0
Line 1, integer 2: -1
Line 2, integer 1: 1
Line 2, integer 2: -2
Line 2, integer 3: 3
Line 2, integer 4: -4
Line 3, integer 1: 123
Line 3, integer 2: 1234
Line 3, integer 3: 12345678
Grading
If your program does not compile, it is considered non-functional and of extremely poor quality, meaning you will receive 0 for the solution.
The assignment will be graded based on three criteria:
Functionality: “Does it work according to specifications?”. This is determined in an automated fashion by
running your program on several inputs and ensuring that the outputs match the expected outputs. The
score is determined based on the number of tests that your program passes. So, if your program passes
t/T tests, you will receive that proportion of the marks.
Quality of Solution: “Is it a good solution?” This considers whether the approach and algorithm in your
solution is correct. This is determined by visual inspection of the code. It is possible to get a good grade
on this part even if you have bugs that cause your code to fail some of the tests.
Code Clarity: “Is it well written?” This considers whether the solution is properly formatted, well documented, and follows coding style guidelines. A single overall mark will be assigned for clarity. Please see
the Style Guide in the Assignment section of the course in Brightspace.
The following grading scheme will be used:
Task 100% 80% 60% 40% 20% 0%
Functionality
(20 marks) Equal to the number of tests passed.
Solution Quality
(20 marks)
Appropriate algorithm and data
structures used for
Problem 1 and 2.
Appropriate algorithm and data
structures for
Problem 1.
Algorithm or data
structure used for
Problem 1 are
functional but not
appropriate.
Algorithm or
data structure
for Problem 1
has major
flaws.
An attempt has
been
made.
code
No code submitted or
does not compile
Code Clarity
(10 marks)
Indentation, formatting, naming,
comments
Code looks professional and follows
all style guidelines
Code looks good
and mostly follows style guidelines.
Code is mostly
readable and
mostly follows
some of the style
guidelines
Code is hard to
read and follows
few of the style
guidelines
Code is illegible
Hints and Suggestions
• Lab 3 will be very helpful for doing Assignment 2.
• Start early. The sample solution is under 100 lines of code, but bit manipulations can be tricky.
• The Standard Library functions I found most useful are: scanf(), printf(), and memset().
• I found it helpful to create a couple helper functions. I recommend keeping all functions together in
your main.c but having a couple helper functions will make your main() function simpler.
Assignment Submission
Submission and testing are done using Git, Gitlab, and Gitlab CI/CD. You can submit as many times as you
wish, up to the deadline. Every time a submission occurs, functional tests are executed, and you can view
the results of the tests. To submit use the same procedure as Assignment 0.
Assignment Testing without Submission
Testing via submission can take some time, especially if the server is loaded. You can run the tests without
submitting your code by using the provided runtests.sh script. Running the script with no arguments
will run all the tests. Running the script with the test number, i.e., 00, 01, 02, 03, … 09, will run that specific
test. Please see below for how run the script.
Get your program ready to run
If you are developing directly on the unix server,
1. SSH into the remote server and be sure you are in the marsdec1 or marsdecx directory.
2. Be sure the program is compiled by running make.
If you are using CLion
1. Run your program on the remote server as described in the CLion tutorials.
2. Open a remote host terminal via Tools → Open Remote Host Terminal
If you are using VSCode
1. Run your program on the remote server as described in VSCode tutorials.
2. Click on the Terminal pane in the bottom half of the window or via Terminal → New Terminal
Run the script
3. Run the script in the terminal by using the command:
./runtest.sh
to run all the tests, or specify the test number to run a specific test, e.g. :
./runtest.sh 07
You will see the test run in the terminal window.