CSCI 2122代写、代做Python/c++程序

日期：2023-10-15 11:00

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.