Project 3
How to Succeed on this Project
1. Read the entirety of this specification in detail. It contains a lot of information that will make the project go more smoothly in you take the time to understand it before starting the project.
2. Know the purpose of each file in the starter code. You will not need to modify any files to complete the project, but you should read this specification to understand why the other files are present.
3. Expect to get stuck, and exercise patience and persistence. This project does not involve writing a large quantity of code. Rather, it involves solving a series of "puzzle" problems that will take time and thinking to solve. Do not expect the solutions to these puzzles to be immediately clear to you. Instead, you will initially be stuck and will have to think through them, perhaps using a pen and paper to work through different examples. Getting stuck like this is a normal part of the learning process in STEM subjects. We are happy to help in office hours but will not give out answers -- we can only point you in the right direction or suggest helpful examples to consider.
4. Start early. Give yourself time to get stuck, discover insights about the puzzles, and overcome obstacles. It can be hard to think creatively about solutions to programming problems like those in this project when you feel the pressure of an imminent deadline.
5. If you have questions, your best option is to ask in a public Piazza post. This gets your question in front of as many people as quickly as possible, and also lets others benefit later by seeing the answer to your question.
6. Familiarize yourself with the late submission policy detailed in the syllabus so that you are not caught off-guard. No submissions are accepted more than 48 hours after the deadline. Extensions are generally not granted for projects except in the case of a documented and acute emergency.
7. The two parts of this project are independent, so you should feel free to switch between them. If you get stuck in Part 1, try making some progress on Part 2, and vice versa.
Introduction
This project consists of two parts. In the first part, you will (again) solve a series of programming problems involving bitwise operations and data representations. In the second part, you will (again) use a debugger to run and inspect the workings of a puzzle program to reverse engineer it and deduce the input values needed to run the program successfully to completion. In Part 1 of this assignment, you will write assembly code involving these operations. You will do this by solving a series of programming "puzzles." Debugging code is also a critical aspect of real programming that is greatly aided through use of 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."
Grading Criteria
Credit for this assignment will be awarded based on two categories:
Automated Testing of Bitwise Puzzles (26%): The starter code includes two programs that will test your bitwise puzzle solutions. The first program checks that your code adheres to the requirements stated below, while the second program runs your puzzle solutions against a variety of inputs. We will use these same programs when autograding your work.
Bomb Defusing (74%): You will follow the instructions on this page for obtaining and defusing your binary bomb. Scoring for the binary bomb is based on number of phases defused, and is handled automatically as you defuse it.
Starter Code
Download the zip file linked at the top of this page to obtain the starter code for this project. You should see the following files. You may only modify the files marked "Edit" under the "Purpose" column below. The autograder will use the starter versions of all other files when grading your work.
|
File
|
Purpose
|
Notes
|
|
Makefile
|
Build and Test
|
Build file to compile code and run test cases for both parts
|
|
bitwise/bits_impl .h
|
Provided
|
Header file for solutions to bitwise puzzles
|
|
bitwise/bits .s
|
EDIT
|
Solutions to bitwise problems for part 1. We have defined a procedure for each problem and you need to fill in each assembly
procedure's body with your solution.
|
|
bitwise/bits_test.h
|
Testing
|
Testing code for bitwise puzzle problems
|
|
bitwise/bits_test .c
|
Testing
|
Testing code for bitwise puzzle problems
|
|
bitwise/btest .c
|
Testing
|
Testing code for bitwise puzzle problems
|
|
bitwise/check_bitwise
|
Testing
|
Testing code for bitwise puzzle problems
|
|
bitwise/cc_check
|
Testing
|
Testing code for bitwise puzzle problems
|
|
bitwise/tests .c
|
Testing
|
Testing code for bitwise puzzle problems
|
|
bitwise/ishow .c
|
Utility
|
Helpful program for showing integer representations
|
|
bitwise/fshow .c
|
Utility
|
Helpful program for showing float representations
|
|
bitwise/Makefile
|
Build and Test
|
Automates compiling and testing for part 1 only
|
Part 1: Bitwise Puzzles (now in assembly!)
Read the material below and the comments at the top of bits.s to understand how to complete this part of the project.
The first part of the project focuses on the files in the bitwise directory. We recommend that you work within this subdirectory of the starter code for the duration of this part of the project (e.g., by 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.s file with solutions to 10 bitwise puzzle problems.
As before, you can only use straightline assembly code for the integer-related puzzles (i.e., no jumps or calls). Other than those two flow control instructions, you may use any instruction introduced in the book through chapter 3.7.
You must respect the register conventions: Each function's input arguments will be stored in registers %edi, %esi, ..., etc. Each function's return values will be returned by storing it in %eax. If you want to use a callee-save register, it will be your job to save the value that was there, and restore that value when you are finished.
Also, you are not allowed to use any immediate values larger than 8 bits (e.g., you can use $0xFF but not $0xFFF).
Note: There is now a single floating point-related puzzle. On this puzzle, the restrictions are lifted: You may use conditionals, jumps and large constants.
The Puzzles
The puzzles that you will be solving in bits.s are described below, in the same order as their appearance 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 bits_tests.c to see reference functions that express correct behavior. of your functions.
|
Name
|
Description
|
Rating
|
|
isZero
|
Return 1 if x is 0, 0 otherwise
|
1
|
|
bitNor
|
Implement bitwise nor (=not or)
|
1
|
|
distinctNegation
|
returns 1 if x != -x
|
1
|
|
dividePower2
|
Compute x/(2^n), for 0 <= n <= 30
|
2
|
|
getByte
|
Extract byte n from word x
|
2
|
|
isPositive
|
return 1 if x > 0, return 0 otherwise
|
2
|
|
floatNegate
|
Return bit-level equivalent of expression -f for floating point argument f
|
2
|
|
isLessOrEqual
|
if x <= y then return 1, else return 0
|
3
|
|
bitMask
|
Generate a mask consisting of all 1's between lowbit and highbit
|
3
|
|
addOK
|
Determine if can compute x+y without overflow
|
3
|