Minneapolis Community and Technical College C Programming Project – Description
This project consists of two parts. In the first part, you will solve a series of programming problems involving bitwise operations and data representations devised by the smart people behind our course textbook. In the second part, you will use a debugger to run and inspect the workings of a puzzle program in order to reverse engineer it and deduce the input values needed to run the program successfully to completion.
Bit-level operations are common in C and in systems programming. In part 1 of this assignment, you will write code involving these operations to become more familiar with the bit-level representations of integers and floating-point numbers. You will do this by solving a series of programming “puzzles”. Many of these puzzles are artificial, but you’ll find yourself thinking much more deeply about bits in order to solve them.
Debugging code is also a critical aspect of programming that is greatly aided through a debugger tool. In part 2 of this project, you will use the GNU Debugger, gdb, to work through a puzzle program requiring specific inputs to pass its sequence of “phases”.
Part 1: Bitwise Puzzles
Based on an assignment originally from Randy Bryant and David O’Halloran.
Read the material below and the comments at the top of bits.c to understand how to complete this part of the project.
The first part of the project focuses on the files in the bitwisedirectory. We recommend that you work within this subdirectory of the starter code for the duration of this part of the project (e.g., using cd in your terminal).
The first thing you will likely want to do is run the make command within this subdirectory to compile the starter code and the useful utilities it provides (described below).
Note: If you wish to compile this code in your own Linux environment rather than the CSE Labs machines, you will need to install 32-bit variants of the standard C libraries. With Ubuntu, you can do this with the following command:
sudo apt install gcc-multilib
Your task is to fill in the skeleton code in the bits.c file with solutions to 12 bitwise puzzle problems.
You can use only straightline C code for the integer-related puzzles (i.e., no loops or conditionals) and a limited number of C arithmetic and logical operations. Specifically, you are onlyallowed to use the following eight operators:
! ~ & ^ | + >
A few of the problems further restrict this list. Also, you are not allowed to use any constants larger than 8 bits (e.g., you can use 0xFF but not 0xFFF). You also are not allowed to use binary constants like 0b1001 in your solutions.
For floating-point problems, you will implement some common single-precision (32-bit) floating point operations. For these puzzles, you are allowed to use standard control structures (conditionals, loops) and you may use both int and unsigneddata types, including arbitrary integer and unsigned constants. You may not use any unions, structs, or arrays. Most significantly, you may not use any floating-point data types, operations, or constants. Instead, any floating-point operand will be passed to the function as having type unsigned, and any returned floating-point value will also be of type unsigned. Your code should perform the bit manipulations that implement the specified floating-point operations.
The Puzzles
The puzzles that you will be solving in bits.c are described below, in the same order as the functions defined in the provided code.
The puzzles are ordered roughly from least difficult to most difficult. The “Rating” column gives the difficulty rating (which also corresponds to the number of points awarded for solving the puzzle). The Max Ops column gives the maximum number of operations you are allowed to use in your solution.
You may also want to look at the contents of tests.c to see reference functions that express the correct behavior of your functions, although they do not satisfy the coding rules expected of your solutions.
Checking Your Work
To check if your puzzle solutions comply with the required coding standards (number of ops, no conditionals, etc.), use the provided dlc program. Note that this program is provided to you as a binary, and it will only work within Linux environments.
If your solutions are all compliant, dlc will not produce any output, like so:
> ./dlc bits.c
If one of your solutions violates a coding rule, dlc will provide an error message like so:
> ./dlc bits.c
dlc:bits.c:145:bitAnd: Illegal constant (0xFFF) (only 0x0 – 0xff allowed)
Note that dlc identifies both the puzzle solution that violates the rule as well as the rule violated.
You will not receive autograder credit for your bitwise puzzle solutions if the dlc check does not pass. If you are unable to solve a puzzle within the constraints, your best option is to remove the non-compliant solution before submission so that you still receive credit for the rest of your solutions.
Next, you can use the very helpful btest program to check your solutions. To check all solutions, run btest like so:
> ./btest
Score Rating Errors Function
ERROR: Test bitAnd(-2147483648[0x80000000],-2147483648[0x80000000]) failed…
…Gives 2[0x2]. Should be -2147483648[0x80000000]
ERROR: Test fitsShort(-2147483648[0x80000000]) failed…
…Gives 2[0x2]. Should be 0[0x0]
ERROR: Test allEvenBits(-2147483648[0x80000000]) failed…
…Gives 2[0x2]. Should be 0[0x0]
ERROR: Test anyOddBit(-2147483648[0x80000000]) failed…
…Gives 2[0x2]. Should be 1[0x1]
ERROR: Test isEqual(-2147483648[0x80000000],-2147483648[0x80000000]) failed…
…Gives 2[0x2]. Should be 1[0x1]
ERROR: Test floatIsEqual(0[0x0],0[0x0]) failed…
…Gives 2[0x2]. Should be 1[0x1]
ERROR: Test sign(-2147483647[0x80000001]) failed…
…Gives 2[0x2]. Should be -1[0xffffffff]
ERROR: Test isAsciiDigit(-2147483648[0x80000000]) failed…
…Gives 2[0x2]. Should be 0[0x0]
ERROR: Test floatIsLess(0[0x0],0[0x0]) failed…
…Gives 2[0x2]. Should be 0[0x0]
ERROR: Test rotateLeft(-2147483648[0x80000000],0[0x0]) failed…
…Gives 2[0x2]. Should be -2147483648[0x80000000]
ERROR: Test absVal(-2147483647[0x80000001]) failed…
…Gives 2[0x2]. Should be 2147483647[0x7fffffff]
ERROR: Test floatScale2(0[0x0]) failed…
…Gives 2[0x2]. Should be 0[0x0]
Total points: 0/29
This output is from running btest on the starter code, which initially fails all tests. Code with solutions to all puzzles will produce the following output:
> ./btest
Score Rating Errors Function
1 1 0 bitAnd
1 1 0 fitsShort
2 2 0 allEvenBits
2 2 0 anyOddBit
2 2 0 isEqual
2 2 0 floatIsEqual
2 2 0 sign
3 3 0 isAsciiDigit
3 3 0 floatIsLess
3 3 0 rotateLeft
4 4 0 absVal
4 4 0 floatScale2
Total points: 29/29
Learn how to use the features of the btest program to test your solutions individually and with specific input values. This will be much more helpful than running btest in its default configuration.
The btest program will provide you with helpful documentation when run with the -h argument:
./btest -h
Usage: ./btest [-hg] [-r ] [-f [-1|-2|-3 ]*] [-T ]
-1 Specify first function argument
-2 Specify second function argument
-3 Specify third function argument
-f Test only the named function
-g Compact output for grading (with no error msgs)
-h Print this message
-r Give uniform weight of n for all problems
-T Set timeout limit to lim
You can use btest to test a specific puzzle solution and with specific input values. For example, to test your solution to the rotateLeft puzzle with input values 0xABCD and 8, you would run:
> ./btest -f copyLSB -1 0xABCD -2 8
Score Rating Errors Function
3 3 0 rotateLeft
Total points: 3/3
Other Advice
Don’t include the header file in your bits.c file, as it will confuse the dlc checker and results in some non-intuitive error messages. You will still be able to use printf in your code if you want to, although gcc will print a warning that you can ignore.
Also, the dlc program enforces a stricter form of C declarations than what is enforced by gcc. In particular, any declaration must appear in a block (i.e., a chunk of code enclosed in curly braces) before any statement that is not a declaration. For example, it will complain about the following code:
int foo(int x) {
int a = x;
a *= 3; // Statement that is not a declaration
int b = a; // dlc ERROR: Declaration not allowed here
…
}
Use the provided ishow and fshow tools, which are generated when you compile code with make. These can help you see how integers and floating point values are represented. For example, use fshow to see what an arbitrary pattern represents as a floating-point number:
> ./fshow 2080374784
Floating point value 2.658455992e+36
Bit Representation 0x7c000000, sign = 0, exponent = f8m fraction = 000000
Normalized. 1.0000000000 x 2^(121)
You can use the file bitwise/Makefile to automate the compilation and testing processes. The command make will compile your code, while make test will run the dlc and btest programs for you.
Part 2: Debugging the Puzzlebox
The file puzzlebox/puzzlebox.c contains source code that reads input from a file named on the command line (usually input.txt in this project). If the inputs are correct, points are awarded. If inputs are incorrect, error messages are printed.
The puzzlebox is arranged into a series of phases each of which has some points associated with it.
Each phase reads inputs from the file provided on the command line and performs calculations on them to see if they are “correct” according to various criteria specified in the source code.
The very first input is your UMN Internet ID like kolb0128 (the first part of your UMN email address). This input is used to add an element of randomness to the puzzle so that your answers will be different from most other students. You must use your own Internet ID, and we will be verifying this when manually grading project submissions. If you do not adhere to this rule, you will not receive credit for this part of the project.
The purpose of this problem is to get familiar using a debugger. This is a powerful tool that pauses program execution, allows internal values to be printed and inspected, and code to be stepped through line by line. It is nearly essential to use here as the code in puzzlebox is intentionally convoluted in places. Being able to pause execution and print values at various points makes it much easier to solve the puzzles.
input.txt Input File
Name your input file input.txt and put your Internet ID in the first line along with some initial numbers for the first phase like 1 2 3. Then, compile and run the puzzlebox program on it.
> make # compile puzzlebox
gcc -Wall -Werror -g -o puzzlebox puzzlebox.c
> cat input.txt # show contents of input.txt
kolb0128
1 2 3
> ./puzzlebox input.txt # run puzzlebox with input.txt
===========================================
PROBLEM 2: Puzzlebox
UserID ‘kolb0128’ accepted: hash value = 1516133979
PHASE 1: A puzzle you say? Challenge accepted!
Ah ah ah, you didn’t say the magic word…
Failure: Double debugger burger, order up!
RESULTS: 0 / 60 points
Initially, you will not see positive results (0/60 points) but the real meat of the problem is in examining the source code and determining the correct inputs for input.txt.
The GNU Debugger (gdb)
You will definitely need to use a debugger to solve the puzzlebox and gdb is the quintessential debugger associated with our compiler, gcc. It is installed by default on all CSE Labs machines and is an easy install on most Linux machines.
For a quick overview of GDB, here are some resources:
CSCI 2021 Quick Guide to gdb: The GNU Debugger: A guide describing how to start the debugger, a sample session using puzzlebox, and an overview of the most common commands.
CppCon 2015: Greg Law ” Give me 15 minutes & I’ll change your view of GDB”: Video giving basic overview of how to run gdb on simple programs with an emphasis on differences between “normal” mode and TUI mode.
GNU GDB Debugger Command Cheat Sheet: Extensive list of commands
Debugging with GDB: Official manual for gdb
Typical Workflow
A typical cycle of working on puzzlebox might involve the following commands:
Start the debugger with puzzleboxgdb -tui ./puzzlebox
Set the arguments array to input.txtset args input.txt
Set a breakpoint at a phase like phase01break phase01
Run the programrun
View active breakpoints:info breakpoints
Remove existing breakpoint #1:del 1
Do some stepping / nextingstep next
Print the value of a variable:print a
Print the value of a variable in hexadecimal:print/x a
Print the value of a variable in binary:print/t a
Make some changes to input.txt in a different window
Re-run the program to see if things have changed favorably
kill
run
These are just a few examples of the gdb features you will find useful in this project. Study the resources linked above for a more comprehensive discussion of the commands and features of gdb.
Kinds of Puzzles
The puzzles presented in the different phases make use of a variety of C programming techniques including:
Bit-wise operations and their use in place of arithmetic
String and character array manipulations
Interpreting bits as one of several kinds of things (integer, float, character) through pointers and unions
More extensive C control structures like goto and labels
The post Minneapolis Community and Technical College C Programming Project first appeared on .
