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 scale_from_ports
        
## ENTRY POINT FOR REQUIRED FUNCTION
scale_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 

.text
.global  scale_display_special

## ENTRY POINT FOR REQUIRED FUNCTION
scale_display_special:
        ## assembly instructions here

	## two useful techniques for this problem
        movl    my_int(%rip),%eax    # load my_int into register eax
        leaq    my_array(%rip),%rdx  # load pointer to beginning of my_array into rdx
        ## DON'T FORGET TO RETURN FROM FUNCTIONS


.global  scale_display_weight

## ENTRY POINT FOR REQUIRED FUNCTION
scale_display_weight:

        ## DON'T FORGET TO RETURN FROM FUNCTIONS



.global scale_update
        
## ENTRY POINT FOR REQUIRED FUNCTION
scale_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.

// scale_update.c: functions that read scale hardware, convert its
// encode its state in a struct, and adjusts the display to show the
// user information.

#include "scale.h"

int scale_from_ports(scale_t *scale);
// Uses the values in SCALE_SENSOR_PORT, SCALE_TARE_PORT, and
// SCALE_STATUS_PORT to set the fields of the `scale` struct to
// appropriate values. 
//
// Does bound checking so that if the SCALE_SENSOR_PORT or
// SCALE_TARE_PORT is out of range (see their docs) sets the fields of
// scale to be 0's, sets the scale->mode to be MODE_ERROR, and
// returns 1. 
//
// If SCALE_STATUS_PORT indicates the Tare button is being pressed
// (see that variable's docs), sets fields of `scale` to be 0, sets
// the mode to be MODE_TARE, and returns 2.
//
// Otherwise sets the fields of scale as follows.
//
// - mode :: set to MODE_SHOW to show the display weight as normal
//
// - weight :: set to (SCALE_SENSOR_PORT - SCALE_TARE_PORT).  Converts
//   to pounds if SCALE_STATUS_PORT indicates that is the desired
//   unit. Conversion is done using bit shifting / masking and rounds
//   pounds up if the ounces are halfway to the next pound.
//
// - indicators :: sets a bit to turn on either the Ounce or Pound
//   Indicator light. If the SCALE_TARE_PORT is not zero, sets a bit
//   to turn on the Tare indicator light. See documentation for the
//   scale_t struct for which bits control which indicator lights.
//
// Returns 0 when `scale` has its field set as above.
// 
// CONSTRAINTS: Uses only integer operations. No floating point
// operations are used as the target machine does not have a FPU. Does
// not use any math functions such as abs().
//
// CONSTRAINTS: Does not use integer division; uses bit shifting and
// masking to compute division by powers of two and perform rounding.

int scale_display_special(scale_t scale, int *display);
// Sets the bits pointed at by `display to indicate one of two
// "special" cases.
//
// If scale.mode is MODE_ERROR, sets the display to "ERR" to indicate
// that the weight is out of range or some other hardware error has
// occurred.
//
// If scale.mode is MODE_TARE, sets the display to "STOR" to indicate
// that the Tare button is being pressed and the current weight will be
// stored in the internal saved weight space.
//
// In both the above cases, only changes the bits pointed at by
// `display` and returns 0. Does not make any other changes to the
// machine state.
//
// If scale.mode is a different value that one of the above two cases,
// this function has been called in error and returns 1.
//
// CONSTRAINT: This function should not access or change any global
// PORT variables.

int scale_display_weight(scale_t scale, int *display);
// Called when scale.mode is MODE_SHOW. If it is not, this function
// returns 1 immediately and makes no other changes.
//
// For scale.mode of MODE_SHOW, sets `display` bits to indicate the
// weight in scale.weight. Uses integer division to determine digits
// to be shown in `display` and whether a negative sign should be
// present. Sets bits of `display` according to the bits in
// scale.indicators to show ounces / pounds as the unit and indicate a
// non-zero tare. Returns 0 on completion.
//
// CONSTRAINT: This function should not access or change any global
// PORT variables. It may use a global array of bit patterns if deemed
// useful.

int scale_update();
// Updates the state of scale using previously defined functions. Uses
// stack space for a scale_t struct which is set from the ports and
// then used to alter the display. If the MODE_TARE is indicated, then
// copies SCALE_SENSOR_PORT to SCALE_TARE_PORT. Returns 0 if the
// display is set properly and 1 if an error occurs while setting the
// display. 
//
// CONSTRAINT: Does not allocate any heap memory as malloc() is NOT
// available on the target microcontroller.  Uses only stack memory
// for local variables.

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:

////////////////////////////////////////////////////////////////////////////////
// scale data and structs

#define UNIT_KG 1               // show kilograms
#define UNIT_LB 2               // show pounds (2.2 pounds per kg)

#define MODE_SHOW      1        // show measured weight as sensor_val - tare_val 
#define MODE_TARE      2        // store the sensor_val into tare_val, Tare Indicator on
#define MODE_ERROR     4        // error of some kind

// store state of the scale in a struct for easier access
typedef struct{
  short weight;            // calculated weight for use elsewhere
  char mode;               // one of the MODE_XX values indicating what to do/show
  char indicators;         // Bit field with 1's for different indicators
  // Bit 0: Ounce Indicator On/Off
  // Bit 1: Pound Indicator On/Off
  // Bit 2: Tare Indicator On/Off, on when stored Tare value is non-zero
} scale_t;

// Accessing fields via a scale_t * pointer
// |-------------------+----------+-------------+-------------------|
// |                   |          | Destination | Assembly          |
// | C Field Access    | Offset   | Size        | Assign 5 to field |
// |-------------------+----------+-------------+-------------------|
// | scale->weight     | 0 bytes  | 2 bytes     | movw $5, 0(%reg)  |
// | scale->mode       | 2 bytes  | 1 bytes     | movb $5, 2(%reg)  |
// | scale->indicators | 3 bytes  | 1 bytes     | movb $5, 3(%reg)  |
// |-------------------+----------+-------------+-------------------|
//
// Accessing fields via a scale_t packed struct
// |------------------+--------+-------------+---------|
// |                  |   Bits | Shift       |         |
// | C Field Access   | in reg | Required    | Size    |
// |------------------+--------+-------------+---------|
// | scale.weight     |   0-15 | None        | 2 bytes |
// | scale.mode       |  16-23 | Right by 16 | 1 byte  |
// | scale.indicators |  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 puzzliebin 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.