HW2: Bash, Git and C Programs

Problem 1 is a set of online questions on the Gradescope assignment HW2_p1: single-choice and multiple-choice questions about undefined behavior, integer overflow, pointers, arrays and selection sort in C.

Answer the questions directly on Gradescope. Each question is graded all-or-nothing (a multiple-select question is correct only if your selection matches exactly). Your score is visible immediately after submission, and you may resubmit as many times as you like until the deadline; the latest answers count.

Problem 2 is a separate online assignment, HW2_p2, covering the command-line and version-control skills from the recitations:

Bash (Recitation 1): common commands (ls, cd, cp, rm, mkdir, touch), output redirection (>, >>) and pipes (|), and file permissions (rwx, chmod).

Git (Recitation 3): the local workflow (git add / commit / status / log), branches and merges, undoing changes (git reset), and working with remotes (clone, push, pull, fetch) — including a few fill-in-the-blank commands.

Given a polynomial P(x) of degree n

P(x) = a₀ + a₁x + ⋯ + aₙxⁿ = Σ aᵢxⁱ  (i = 0..n)

we want to evaluate the polynomial at several points x₀, x₁, …, x_m−1.

Input format

On the first line, a nonnegative integer n, which is the degree of the polynomial.

On the second line, n+1 numbers a₀, a₁, …, a_n separated by space, which are the coefficients of the polynomial.

On the third line, a nonnegative integer m.

Then m lines follow, the i-th of which is a number x_i (i = 0, 1, …, m−1).

Output format

m lines, the i-th of which is a number P(x_i), rounded to three decimal places.

Example

2
-0.5 1 2.5
5
0
-6.6
1000
-1
32

-0.500
101.800
2500999.500
1.000
2591.500

Notes

It is guaranteed that n ≤ 30. An array is enough to store the coefficients. Do not use heap memory.

The evaluation of P(x_i) at a given point x_i should be done using only one loop without calls to standard library functions. Think about how to do this efficiently.

Problem background

To compile C/C++ code, we need to execute a command that calls the compiler with some arguments. For example:

gcc hello.c -o hello -std=c17 -Wall -Wpedantic -Wextra

This command compiles the C source code file hello.c with gcc, setting the output file to be hello, setting the language standard to be ISO C17, and enabling some kinds of warnings and errors by -Wall -Wpedantic -Wextra.

Taking a look at GCC's manual, you will find an overwhelmingly long list of supported arguments. Is there a tool that can generate some explanations of the arguments, or at least for some of the most common ones? For example, suppose the name of that tool is gcc_descriptor. It would be helpful if the following command

./gcc_descriptor hello.c -o hello -std=c17 -Wall -Wpedantic -Wextra

could print

hello.c: C source code as input file.
-o hello: Place the primary output in file hello.
-std=c17: Set the language standard to ISO C17.
-Wall: Enable all the warnings about constructions that some users consider questionable, and that are easy to avoid (or modify to prevent the warning).
-Wpedantic: Issue all the warnings demanded by strict ISO C and ISO C++ and reject all programs that use forbidden extensions.
-Wextra: Enable some extra warning flags that are not enabled by -Wall.

Your task is to implement such a tool that generates explanations for some very common GCC arguments.

Problem description

Write a program that accepts command-line arguments, which are the arguments that we want to pass to GCC, and print the descriptions for them. The supported kinds of arguments are as follows.

1. -Wall

-Wall: Enable all the warnings about constructions that some users consider questionable, and that are easy to avoid (or modify to prevent the warning).

2. -Wpedantic

-Wpedantic: Issue all the warnings demanded by strict ISO C and ISO C++ and reject all programs that use forbidden extensions.

3. -Wextra

-Wextra: Enable some extra warning flags that are not enabled by -Wall.

4. -Werror

-Werror: Make all warnings into errors.

5. -o xxx

-o xxx: Place the primary output in file xxx.

where xxx is replaced by the actual file name (see the example below). Note that this option consists of two arguments, where the first one is -o and the second one is the file name.

6. -I xxx

-I xxx: Add the directory xxx to the list of directories to be searched for header files during preprocessing.

where xxx is replaced by the actual directory name (see the example below). Note that this option consists of two arguments, where the first one is -I and the second one is the directory name.

7. -std=xxx

-std=xxx: Set the language standard to yyy.

where xxx is replaced by the actual value and yyy is replaced by the name of the standard according to the following table.

N consists of two digits. For example, the 2003 ISO C++ standard is named C++03.

8. Other

Anything that does not match the patterns above is treated as an input file.

xxx: yyy as input file.

where xxx is replaced by the file name and yyy is replaced by the type of the file according to the following table.

Notes

There is no input for this problem. The arguments to be explained are given as the command line arguments of your program.

It is guaranteed that the arguments are valid: anything that does not match the patterns in 1–7 must be a valid C/C++ source or header file name as described in the table above. For the language standards (pattern 7), you don't need to check whether the standard that it refers to actually exists. Things like -std=c++100000 won't appear.

Also, there won't be any invalid file name or something like -Wall.cpp, which means you should focus on the implementation itself, not some tricky corner cases.

The names of the files and directories involved in the arguments do not contain whitespaces or quotes. The name following -o or -I is not a C/C++ source or header file. Print the explanations in order of the arguments.

Example

If the following command is executed,

./my_program -std=c++20 -Wall -Wpedantic -Wextra a.c b.hxx c.cpp -Werror -o output_file -I /usr/local/boost_1_80_0/

the output is

-std=c++20: Set the language standard to ISO C++20.
-Wall: Enable all the warnings about constructions that some users consider questionable, and that are easy to avoid (or modify to prevent the warning).
-Wpedantic: Issue all the warnings demanded by strict ISO C and ISO C++ and reject all programs that use forbidden extensions.
-Wextra: Enable some extra warning flags that are not enabled by -Wall.
a.c: C source code as input file.
b.hxx: C++ header file as input file.
c.cpp: C++ source code as input file.
-Werror: Make all warnings into errors.
-o output_file: Place the primary output in file output_file.
-I /usr/local/boost_1_80_0/: Add the directory /usr/local/boost_1_80_0/ to the list of directories to be searched for header files during preprocessing.

To understand how the computer executes your program, let me give a short introduction to the CPU. The CPU basically contains 2 parts: a register file with registers and an ALU (more in CS110). You can consider registers as an array. Each cell of this array has a name (for example, x0, x1, x2, …, x31 in RISC-V 32), and can store 32-bit data. Arithmetic calculations (addition, subtraction, multiplication, division, …) are done by the ALU.

When executing your program, the assembly codes (written in binary) are sent to the CPU. Each line of assembly code specifies some operation on registers, and the CPU uses a special register named PC (program counter) to identify the current execution line number. For example, if the code is add x3 x1 x2, then the CPU takes the values in registers x1 and x2, adds them up and stores the result in register x3. This is shown in the figure below (only 5 registers shown here). Then, the CPU increments PC by 1 to execute the next instruction.

In this problem, you are required to implement a toy CPU which is able to execute a very simple assembly language (similar to RISC-V). You only need to consider 6 registers, named x0, x1, x2, x3, x4 and x5, all in lowercase, and each register stores a 16-bit signed integer. The x0 register is a special one, whose value is always zero (that is, whatever operation done to x0 will not affect its value). Also, there are only 6 instructions in this assembly language: add, sub, mul, div, let and print, which are introduced below.

In this problem, we use a 16-bit machine code. An example of a 16-bit instruction is as follows.

The instructions add, sub, mul and div are similar. The syntax is shown in the following table. Note that in these operations, the imm part is discarded.

The let instruction is used to assign a value to a register. The syntax is:

where r1 is the name of some register (x0 to x5), and imm is an integer within the range [0, 2⁷−1]. In this instruction, the r2 part is discarded and the imm part is used. For example, the execution of instruction let x1 80 is shown below.

Also, we need a print instruction to print the value in some register so that we can test whether the execution result is correct. For example, if the value in register x1 is 5, your emulator should print x1 = 5 on the screen when the instruction print x1 is executed. The r2 part is also discarded in this instruction.

Notes

1. In the div instruction, the division result is truncated towards zero, and the denominator will always be non-zero.

2. Values in all registers should be initialized to 0 before execution.

3. Remember that the value in x0 is always zero. Any instruction that attempts to modify it should have no effect.

4. We only consider unsigned immediates in this problem.

Input format

The first line of the input is a number n, indicating the total lines of code. The following n lines are the instructions written in hexadecimal.

Output format

Your emulator should execute the input program, and only print the result when a print instruction is executed. It is guaranteed that the input and output are both non-empty.

Example 1

2
0x8401
0xA400

x1 = 1

Example 2

10
0x8401
0x8801
0x8C01
0x9001
0x9401
0xA400
0xA800
0xAC00
0xB000
0xB400

x1 = 1
x2 = 1
x3 = 1
x4 = 1
x5 = 1

Explanation

0x8401 is 1000010000000001 in binary, whose opcode is 100, r1 is 001 (x1), r2 is 000 (x0) and imm is 0000001 (1). From the opcode we know that this is a let instruction, so the instruction is let x1 1.

0xA400 is 1010010000000000 in binary, whose opcode is 101 and r1 is 001 (x1). This is a print instruction, so the instruction is print x1.