CMSC216 Project 3: Assembly Coding and Debugging

As discussed in class, one can generate assembly code from C code with appropriate compiler flags. This can be useful for getting oriented and as a beginning to the code your assembly versions of the functions. However, this exercise is about writing assembly yourself to gain a deeper understanding of it.

Code that is clearly compiler-generated with no hand coding will receive 0 credit.

• No credit will be given on manual inspection
• Penalties will be assessed for Automated Tests which lower credit to 0

Do not let that dissuade you from looking at compiler-generated assembly code from you C solution to the functions. Make sure that you take the following steps which are part of the manual inspection criteria.

1. Get your editor set up to make coding assembly easier. If you are using VS Code, the following video will show you how to install an extension to do syntax highlighting and block comment/uncomment operations in assembly: https://youtu.be/AgmXUFOEgIw
2. Be disciplined about your register use: comment what "variables" are in which registers as it is up to you to keep track. The #1 advice from past students to future students is "Comment the Crap out of your assembly code" on this project.

3. Be Careful with constants: forgetting a $ in constants will lead to a bare, absolute memory address which will likely segfault your program. Contrast:

      movq    $0,%rax                 # rax = 0
      movq    0, %rax                 # rax = *(0): segfault
                                      # bare 0 is memory address 0 - out of bounds
   

   Running your programs, assembly code included, in Valgrind can help to identify these problems. In Valgrind output, look for a line number in the assembly code which has absolute memory addresses or a register that has an invalid address.

4. Recognize that in x86-64 function parameters are passed in registers for up to 6 arguments. These are arranged as follows

   1. rdi / edi / di (arg 1)
   2. rsi / esi / si (arg 2)
   3. rdx / edx / dx (arg 3)
   4. rcx / ecx / cx (arg 4)
   5. r8 / r8d / r8w (arg 5)
   6. r9 / r9d / r9w (arg 6)

   and the specific register corresponds to how argument sizes (64 bit args in rdi, 32 bit in edi, etc). The functions you will write have few arguments so they will all be in registers.

5. Use registers sparingly. The following registers (64-bit names) are "scratch" registers or "caller save." Functions may alter them freely (though some may contain function arguments).

   rax rcx rdx rdi rsi r8 r9 r10 r11  # Caller save registers
   

   No special actions need to be taken at the end of the function regarding these registers except that rax should contain the function return value.

   Remaining registers are "callee save": if used, their original values must be restored before returning from the function.

   rbx rbp r12 r13 r14 r15            # Callee save registers
   

   This is typically done by pushing the callee registers to be used on the stack, using them, them popping them off the stack in reverse order. Avoid this if you can (and you probably can in our case).

6. Be careful to adjust the stack pointer using pushX/popX or subq/addq . Keep in mind the stack must be aligned to 16-byte boundaries for function calls to work correctly. Above all, don't treat rsp as a general purpose register.
7. Note carefully which function use which conventions for struct arguments; e.g. pointers to structs VERSUS actual structs. Use appropriate assembly techniques to access fields each (they are not the same).

8. To access a global variable and copy it into a register, use the following assembly syntax

      movw GLOB_VAR_NAME(%rip), %cx    # copy global var to reg cx
   

   Many functions access the global PORT variables but only a few change those variables.

9. Use comparisons and jumps a separate sections of code that are clearly marked as "error" or "out of bounds" if you detect bad arguments to functions.
10. When required, used bit shifting and masking to efficiently perform division by powers of two and check for remainders if rounding is required.
11. Make use of division to extract digits in base 10 if the situation requires it. Keep in mind that the idivX instruction must have rax/eax/ax as the dividend, rdx sign-extended out via cwtl / cltq / cqto instructions. Any register can contain the divisor. After the instruction, rax/eax/ax will hold the quotient and rdx/edx/dx the remainder. With cleverness, you'll only need to do a couple divisions.
12. Use shifts and ORs to combine the digit bit patterns to create the final display bit pattern.

13. The final function in the problem requires the previous functions to be called to to create the struct and manipulate the bits of the display. Calling a function requires that the stack be aligned to 16-bytes; there is always an 8-byte quantity on the stack (previous value of the rsp stack pointer). This means the stack must be extended with a subq instruction before any calls. A typical sequence is

        subq $<NUM>,%rsp    # adjust the stack pointer to make space for local      
                            # values AND align to a 16-byte boundary
    
        call    some_func   # stack aligned, call function
        ## return val from func in rax or eax
    
        call    other_func  # stack still aligned, call other function
        ## return val from func in rax or eax
    
        addq $<NUM>,%rsp    # restore the stack pointer to its original value
    

    NOTE: the specific value for <NUM> is dependent on the situation. Common total adjustments are 8 bytes, 24 bytes, and 40 bytes. Pick one that fits the situation here: how much space for local variables is needed in the function. Most implementations will need space for a local struct so knowing the total size required for it is a good start.

14. Structs that are stored in the stack can be "packed" into registers by moving their fields into those registers. For small structs, a single movq / movl / movw may be enough to move the entire struct into an argument register. For larger structs, several moves may be required.

For reference, here is a picture that appears in the lecture slides that summarizes the names and special uses for the registers in x86-64.

Below is a rough outline of the structure of required assmebly file. Consider copying this file as you get started and commenting parts of it out as needed.

.text                           # IMPORTANT: subsequent stuff is executable
.global set_batt_from_ports
        
## ENTRY POINT FOR REQUIRED FUNCTION
set_batt_from_ports:
        ## assembly instructions here

        ## a useful technique for this problem
        movX    SOME_GLOBAL_VAR(%rip), %reg
        # load global variable into register
        # Check the C type of the variable
        #    char / short / int / long
        # and use one of
        #    movb / movw / movl / movq 
        # and appropriately sized destination register                                            

        ## DON'T FORGET TO RETURN FROM FUNCTIONS

### Change to definint semi-global variables used with the next function 
### via the '.data' directive
.data                           # IMPORTANT: use .data directive for data section
	
my_int:                         # declare location an single int
        .int 1234               # value 1234

other_int:                      # declare another accessible via name 'other_int'
        .int 0b0101             # binary value as per C '0b' convention

my_array:                       # declare multiple ints sequentially starting at location
        .int 20                 # 'my_array' for an array. Each are spaced 4 bytes from the
        .int 0x00014            # next and can be given values using the same prefixes as 
        .int 0b11110            # are understood by gcc.


## WARNING: Don't forget to switch back to .text as below
## Otherwise you may get weird permission errors when executing 

.global  set_display_from_batt

## ENTRY POINT FOR REQUIRED FUNCTION
set_display_from_batt:

        ## DON'T FORGET TO RETURN FROM FUNCTIONS


.global batt_update
        
## ENTRY POINT FOR REQUIRED FUNCTION
batt_update:
	## assembly instructions here
        ## DON'T FORGET TO RETURN FROM FUNCTIONS

Below is a repeat of the documentation from project 2 on the expected behavior of the required functions.

// batt_update.c: functions that read the battery voltage and convert
// its value to percent, then adjust the display to reflect the
// reading.

#include "batt.h"

int set_batt_from_ports(batt_t *batt);
// Uses the two global variables (ports) BATT_VOLTAGE_PORT and
// BATT_STATUS_PORT to set the fields of the parameter 'batt'.  If
// BATT_VOLTAGE_PORT is negative, then battery has been wired wrong;
// no fields of 'batt' are changed and 1 is returned to indicate an
// error.  Otherwise, sets fields of batt based on reading the voltage
// value and converting to percent using the provided formula. Returns
// 0 on a successful execution with no errors. This function DOES NOT
// modify any global variables but may access global variables.
//
// CONSTRAINT: Avoids the use of the division operation as much as
// possible. Makes use of shift operations in place of division where
// possible.
//
// CONSTRAINT: Uses only integer operations. No floating point
// operations are used as the target machine does not have a FPU.

int set_display_from_batt(batt_t batt, int *display);
// Alters the bits of integer pointed to by 'display' to reflect the
// data in struct param 'batt'.  Does not assume any specific bit
// pattern stored at 'display' and completely resets all bits in it on
// successfully completing.  Selects either to show Percent (mode=1) or
// Volts (mode=2). If Volts are displayed, only displays 3 digits
// rounding the lowest digit up or down appropriate to the last digit.
// Calculates each digit to display changes bits at 'display' to show
// the volts/percent according to the pattern for each digit. Modifies
// additional bits to show a decimal place for volts and a 'V' or '%'
// indicator appropriate to the mode. In both modes, places bars in
// the level display as indicated by percentage cutoffs in provided
// diagrams. This function DOES NOT modify any global variables but
// may access global variables.
//
// ERRORS: Early in the function checks that the `mlvolts` field is
// positive and the `mode` field is either 1 or 2. If not, immediately
// returns 1 without changing the `display` parameter. (This error
// checking is new and was not presnet in the Project 2 version)

int batt_update();
// Called to update the battery meter display.  Makes use of
// set_batt_from_ports() and set_display_from_batt() to access battery
// voltage sensor then set the display. Checks these functions and if
// they indicate an error, does NOT change the display.  If functions
// succeed, modifies BATT_DISPLAY_PORT to show current battery level.
// 
// CONSTRAINT: Does not allocate any heap memory as malloc() is NOT
// available on the target microcontroller.  Uses stack and global
// memory only.

Accessing struct fields in C involves use of either the dot (.) or arrow (->) field access operators depending on whether the struct is locally stored (an "actual struct") or is available via its memory location (a "pointer to a struct"). In assembly, different techniques are also required. These are demonstrated in a recent Lab and students wanting a quick overview should review that lab. The provided header file has tables of where the struct fields for the required data types are stored. These are show below for quick reference:

// Breaks battery stats down into constituent parts
typedef struct{
  short mlvolts;     // voltage read from port, units of 0.001 Volts (milli Volts)
  char  percent;     // percent full converted from voltage
  char  mode;        // 1 for percent, 2 for volts, set based on bit 4 of BATT_STATUS_PORT
} batt_t;

// Accessing fields via a batt_t * pointer
// |----------------+---------+-------------+-------------------|
// |                |         | Destination | Assembly          |
// | C Field Access | Offset  | Size        | Assign 5 to field |
// |----------------+---------+-------------+-------------------|
// | batt->mlvolts  | 0 bytes | 2 bytes     | movw $5, 0(%reg)  |
// | batt->percent  | 2 bytes | 1 bytes     | movb $5, 2(%reg)  |
// | batt->mode     | 3 bytes | 1 bytes     | movb $5, 3(%reg)  |
// |----------------+---------+-------------+-------------------|
//
// Accessing fields via a batt_t packed struct
// |----------------+--------+-------------+---------|
// |                |   Bits | Shift       |         |
// | C Field Access | in reg | Required    | Size    |
// |----------------+--------+-------------+---------|
// | batt.mlvolts   |   0-15 | None        | 2 bytes |
// | batt.percent   |  16-23 | Right by 16 | 1 byte  |
// | batt.mode      |  24-31 | Right by 24 | 1 byte  |
// |----------------+--------+-------------+---------|

The nature of this problem is similar to the previous project's puzzlebox: there is a program called puzzlebin which expects certain inputs from a parameter file as input. If the inputs are "correct", a phase will be "passed" earning points and allowing access to a subsequent phases. The major change is that puzzlebin is in binary so must be debugged in assembly. The GDB guide above has a special section on debugging binaries which is worth reading. The typical startup regime is:

>> gdb -tui puzzlebin
(gdb) set args input.txt      # set the command line arguments
(gdb) layout asm              # show disassembled instructions
(gdb) layout regs             # show the register file
(gdb) break phase01           # break at the start of the first phase01
(gdb) run                     # get cracking

Below is a summary of useful information concerning the puzzlebin.

Input File

Data for input should be placed in the input.txt file. The first value in this file will be the userID (first part of your UMD email address) which is 8 or fewer characters.

UserID Randomization

Each phase has some randomization based on the UserID so that the specific answers of an one students will not necessarily work for another student.

One Phase Input per Line

Place the input for each phase on its own line. Some input phases read a whole line and then dissect it for individual data. Putting each input on its own line ensures you won't confuse the input processing.

Passing Phases Earns Points

As with the earlier puzzlebox, points for this problem are earned based on how many phases are completed. Each phase that is completed will earn points.

Use GDB to work with Puzzlebin

The debugger is the best tool to work with running the given program. It may be tempting to try to brute force the puzzlebin by trying many possible inputs but in most cases, a little exploration will suffice to solve most phases.

The input line "SKIP" will skip a phase with a small penalty

Students woefully stuck on a phase may skip it to the next phase with the input line SKIP. Be aware that this applies a small penalty to the overall score AND changes the state of the random number generator so that if you revisit an earlier skipped phase, answers to later phases may change.

In some cases, the process of zipping an executable like puzzlebin then unzipping it leads to the permissions on it being set incorrectly. Below is a common permissions error and how to fix it by changing the permissions on puzzlebin.

>> ./puzzlebin input.txt
bash: ./puzzlebin: Permission denied

# Permission error on puzzlebin: it is not set to be executable. The
# fix is:

>> chmod u+x puzzlebin
# Manually add the execute 'x' permission
# OR
>> make
chmod u+x puzzlebin
# use the provided Makefile to run that command

>> ./puzzlebin input.txt
========================================
Puzzlebin (release Tue 10-Oct-2024)
'YOUR_DIRECTORY_ID' is a userID and must be max 8 characters
# Now running normally albeit with the need to modify the input file

• Most of the time you should run puzzlebin in gdb as in

    >> gdb -tui ./puzzlebin
  

  Refer to the Quick Guide to GDB if you have forgotten how to use gdb and pay particular attention to the sections on debugging assembly.

• Most phases process input via calls to scanf()-style functions. Quick insight to the expected input for a phase comes from analyzing the format strings like "%d %d" and "%s %f %d" to those calls. Figure out how to do this early so you can determine the quantity and types of input to each phase.
• It is worthwhile to look at the Failure Messages when a phase is not going to be passed. These are passed to the failure() function: printing them out may give you some hints.
• Make use of other tools to analyze puzzlebin aside from the debugger. Some of these like strings are described at the end of the Quick Guide to GDB. They will allow you to search for "interesting" data in the executable puzzlebin.
• Disassemble the executable to look at its entire source assembly code as a text file. The Quick Guide to GDB shows how to use objdump to do this. Looking at the whole source code reveals that one cannot hide secrets easily in programs.
• Feel free to do some internet research. There is a well-known "Binary Bomb Lab" assignment by Bryant and O'Hallaron, our textbook authors, that inspired Puzzlebin. It has a long history and there are some useful guides out there that can help you through rough patches. Keep in mind that your code will differ from any online tutorials BUT the techniques to defuse it may be similar to what is required to solve puzzles.

puzzlebin is a binary executable file and these are always a bit flaky to distribute as is. It has been tested on GRACE and is know to run normally there and is likely to run normally on most Linux systems. If you see strange behavior on a different Linux platform such as segmentation faults, revert to working on GRACE to for immediate relief but also email Prof. Kauffman resolving incompatibilities is of interest.