Last Updated: 2023-02-27 Mon 08:28

CSCI 2021 Lab07: Assembly Coding

CODE DISTRIBUTION: lab07-code.zip

DEMO VIDEO: Not Yet Available

CHANGELOG: Empty

1 Rationale

Assembly coding requires careful attention to detail and can feel quite overwhelming initially. This Lab is designed to introduce some aspects of assembly coding required to complete upcoming projects. It focuses on completing two functions from a previous HW and passing automated tests. The lab allows practice on basic assembly instructions, location of argument registers, extracting function arguments, and debugging assembly.

Associated Reading / Preparation

  • Bryant and O'Hallaron: Ch 3.1-3.7 on assembly code instructions in x86-64.
  • Any overview guide to x86-64 assembly instructions such as Brown University's x64 Cheat Sheet
  • To more easily debug assembly, it is useful to be able to run a debugger like gdb on the assembly code. Examine the CSCI 2021 Quick Guide to gdb: The GNU Debugger which contains information specific to assembly as such as how to display the register contents.

It is also advisable to configure your editing environment for assembly code. For those using VS Code, the following short video shows how to install an assembly editing mode that supports the GNU Assembler dialect and shows how to block comment/uncomment code.

Configuring VS Code for x86-64 Assembly: https://youtu.be/AgmXUFOEgIw

Grading Policy

Credit for this Lab is earned by completing the exercises here and submitting a Zip of the work to Gradescope. Students are responsible to check that the results produced locally via make test are reflected on Gradescope after submitting their completed Zip. Successful completion earns 1 Engagement Point.

Lab Exercises are open resource/open collaboration and students are encouraged to cooperate on labs. Students may submit work as groups of up to 5 to Gradescope: one person submits then adds the names of their group members to the submission.

See the full policies in the course syllabus.

2 Codepack

The codepack for the HW contains the following files:

File   Description
QUESTIONS.txt EDIT Questions to answer: fill in the multiple choice selections in this file.
coins_funcs_asm.s EDIT Incomplete Assembly functions, fill in remaining code
coins_main.c Provided main() function
coins.h Provided C header
coins_funcs.c Provided C functions to be implemented in assembly, code here can be used to test incrementally
Makefile Build Enables make test and make zip
QUESTIONS.txt.bk Backup Backup copy of the original file to help revert if needed
QUESTIONS.md5 Testing Checksum for answers in questions file
test_quiz_filter Testing Filter to extract answers from Questions file, used in testing
test_lab07.org Testing Tests for this lab
testy Testing Test running scripts

3 Two Assembly Functions

The goal of the lab is to complete working assembly code for two functions that feature in a previous HW. These are as follows:

int set_coins(int cents, coins_t *coins);
// Calculate number of quarters, dimes, nickels, pennies of
// change. Param cents is the number of cents, 0-99. Param coins is a
// pointer to a structure which will have its fields set to the number
// of coins of each type. Returns 0 on success.  If cents is out of
// range, no values are changed and 1 is returned.

int total_coins(coins_t coins);
// Returns the total number of cents in the given coins struct.

Implement these functions in the file coins_funcs_asm.s. This file contains documentation and partial implementations of the functions: complete the code in this file.

To complete the assembly code, you will need to know about layout of the coin_t data type used in the functions. This information is in the coins.h header file and is repeated below:

typedef struct {     // Type for collections of coins
  char quarters;
  char dimes;
  char nickels;
  char pennies;
} coins_t;
// coint_t has the following memory layout and argument passing
// properties:
//
// |          | Pointer | Packed | Packed |
// |          |  Memory | Struct | Struct |
// | Field    |  Offset | Arg#   | Bits   |
// |----------+---------+--------+--------|
// | quarters |      +0 | #1     | 0-7    |
// | dimes    |      +1 | #1     | 8-15   |
// | nickels  |      +2 | #1     | 16-23  |
// | pennies  |      +3 | #1     | 24-31  |
//
// Since the entire struct is less that 64-bits, it is passed in a
// single argument register on 64-bit systems when passed as a value
// such as in the below total_coins() function.

Importantly, there is information on

  1. Byte-level layout of a coin_t when it is stored in main memory, pertinent to set_coins()
  2. Bit-level layout of coin_t when the struct is packed into an argument register, pertinent to total_coins

Study this information and examine the existing code to get a sense for how to complete the rest. Ask questions of lab staff if you do understand some things that you see.

When the function are completed, the coins_main program can be used to experiment with them such as in the following examples.

> make
gcc -Wall -Werror -g  -o coins_main coins_main.c coins_funcs_asm.s

> ./coins_main 37
37 cents is...
1 quarters
1 dimes
0 nickels
2 pennies
which is 37 cents

> ./coins_main 91
91 cents is...
3 quarters
1 dimes
1 nickels
1 pennies
which is 91 cents

> ./coins_main 9
9 cents is...
0 quarters
0 dimes
1 nickels
4 pennies
which is 9 cents

# Run the tests
> make test
gcc -Wall -Werror -g  -o coins_main coins_main.c coins_funcs_asm.s
./testy test_coins_main.org 
============================================================
== test_coins_main.org : coins_main Tests
== Running 1 / 1 tests
1)  All Tests            : ok
============================================================
RESULTS: 1 / 1 tests passed

4 set_coins Assembly Function

Use of the Division Instruction

The main purpose of set_coins is to repeatedly divide the "cents" by different coin values to determine how many quarters, dimes, nickels, and pennies are required. Note the use of division instructions to accomplish this in the provided code:

        ## BLOCK B
        movl    %edi,%eax       # eax now has cents
        cqto                    # prep for division
        movl    $25,%r8d
        idivl   %r8d
        movb    %al,0(%rsi)     # coins->quarters = cents / 25
        movl    %edx,%eax       # cents = cents % 25
        ...

Take care to understand some unique quirks of the idivl instruction: it MUST have the number to be divided in the A-family register, %eax in this case and after completing, the %eax / %edx contain the quotient and remainder of the division respectively. The last movl instruction sets up the next division to compute the number of dimes by moving the remaining cents into %eax again for another division.

Setting Struct Fields in Memory

Note the use of movb to move a single byte from the A-family register into main memory.

  • %al is the lowest order byte in the %rax / %eax register. The division by 25 is expected to produce a small number which can be represented in a single byte.
  • movb is chosen to move a single byte from the register into main memory. This also matches the size of the quarters field of coins_t: it is a char which is only 1 byte big.
  • The location 0(%rsi) is used as %rsi contains a pointer to a coins_t and the quarters field is 0 bytes offset from this pointer. This is the type of assembly instruction that would be generated for C code like coins->quarters = cents / 25;

Copy this pattern to other locations noting that the fields for dimes / nickels / pennies are at different locations from the beginning of the coins_t struct so will require different move offsets such as 2(%rsi).

5 total_coins Assembly Function

Packed Struct Arguments

Consider the C prototype and assembly documentation given for the function:

int total_coins(coins_t coins);
.globl  total_coins
total_coins:
### args are
### %rdi packed coin_t struct with struct fields in the following bit rangs
###  {0-7: quarters, 8-15: dimes, 16-23-: nickels,  24-31: pennies}

At the assembly level, an entire coins_t struct is passed into total_coins() as a single argument: each field of quarters / dimes / nickels / pennies comes in via the %rdi register.

To extract each field separately, a series of shift/mask operations are performed in assembly via the sarq (shift right) and andq (bitwise-and) instructions. Each field is a single byte big so after a right shift, andq-ing onto a mask like 0xFF will leave only a single field present such as in the provided code to extract the dimes field which is in bits 8-15 of the %rdi register:

        movq    %rdi,%rdx        # extract dimes: copy arg to work register
        sarq    $8,%rdx          # move dimes to low order bits
        andq    $0xFF,%rdx       # rdx = dimes

Employ this pattern in the indicated location to complete the remainder of the function.

6 Debug Assembly Functions via gdb

Debugging assembly code is difficult as there are so many details to track. In addition, standard tactics such as use of printf() to show information are extremely difficult to employ: setting up function calls in assembly is more difficult and changes the state of the program quite a bit.

Rather, debuggers such as gdb are a more expedient option. Review information from the CSCI 2021 Quick Guide to gdb: The GNU Debugger how to set up GDB to work on your assembly code. This includes tactics such as stepping, breaking, and importantly, showing the values in registers.

The coins_main program can be used to easily test code in this way as in the following.

> make coins_main
gcc -Wall -Werror -g  -o coins_main coins_main.c coins_funcs_asm.s coins_funcs.c

> ./coins_main 27
27 cents is...
1 quarters
0 dimes
0 nickels
0 pennies
which is 25 cents

# looks wrong, fire up gdb to see what's happening in the set_coins() 
# assembly code

> gdb -tui coins_main

gdb> layout regs                # turn on registers
gdb> break set_coins            # set breakpoint at misbehaving assembly function 
gdb> set args 27                # set commandline arg to 27 cents
gdb> run                        # run to breakpoint
...

7 QUESTIONS.txt File Contents

Below are the contents of the QUESTIONS.txt file for the lab. Follow the instructions in it to complete the QUIZ and CODE questions for the lab.

                           __________________

                            LAB 07 QUESTIONS
                           __________________





Lab Instructions
================

  Follow the instructions below to experiment with topics related to
  this lab.
  - For sections marked QUIZ, fill in an (X) for the appropriate
    response in this file. Use the command `make test-quiz' to see if
    all of your answers are correct.
  - For sections marked CODE, complete the code indicated. Use the
    command `make test-code' to check if your code is complete.
  - DO NOT CHANGE any parts of this file except the QUIZ sections as it
    may interfere with the tests otherwise.
  - If your `QUESTIONS.txt' file seems corrupted, restore it by copying
    over the `QUESTIONS.txt.bk' backup file.
  - When you complete the exercises, check your answers with `make test'
    and if all is well, create a zip file with `make zip' and upload it
    to Gradescope. Ensure that the Autograder there reflects your local
    results.
  - IF YOU WORK IN A GROUP only one member needs to submit and then add
    the names of their group.


QUIZ Coding Assembly Functions
==============================

  Answer the following questions on basic techniques for assembly
  function coding.

  How are the first 6 arguments to an assembly functions mad available
  within the function?
  - ( ) Arguments are passed in registers; the first two are in the
    `%rax' and `%rbx' registers
  - ( ) Arguments are passed in registers; the first two are in the
    `$rdi' and `%rsi' registers
  - ( ) Arguments are in the stack; the first two are available using
    the stack pointer as `0(%rsp)' and `8(%rsp)'
  - ( ) Arguments are in the stack; the first two are available using
    the stack pointer as `8(%rsp)' and `12(%rsp)'

  Which of the following best describes how the kind of arguments passed
  to the FIRST function `set_coins()' function in assembly?
  - ( ) An integer in `%edi' and a pointer to a struct in `%rsi'; to
    get/set fields of the struct syntax like `2(%rsi)' is used
  - ( ) An integer in `%edi' and a packed struct in `%rsi'; to get/set
    fields of the struct bitwise shifts and AND operations are used
  - ( ) An integer in `%esi' and a pointer to a struct in `%rdi'; to
    get/set fields of the struct syntax like `2(%rsi)' is used
  - ( ) An integer in `%esi' and a packed struct in `%rdi'; to get/set
    fields of the struct bitwise shifts and AND operations are used

  Which of the following best describes how the kind of arguments passed
  to the SECOND function `total_coins()' function in assembly?
  - ( ) A pointer to a struct in `%rsi'; to get/set fields of the struct
    syntax like `2(%rsi)' is used
  - ( ) A packed struct in `%rsi'; to get/set fields of the struct
    bitwise shifts and AND operations are used
  - ( ) A pointer to a struct in `%rdi'; to get/set fields of the struct
    syntax like `2(%rsi)' is used
  - ( ) A packed struct in `%rdi'; to get/set fields of the struct
    bitwise shifts and AND operations are used


CODE coins_funcs_asm.s
======================

  Complete the two assembly functions in `coins_funcs_asm.s'. Note that
  until both functions are complete, the tests will likely fail. Correct
  output will appear something like the following:
  ,----
  | >> make
  | gcc -Wall -Werror -g  -o coins_main coins_main.c coins_funcs_asm.s
  | 
  | >> ./coins_main 88
  | set_coins():
  | 88 cents is...
  | 3 quarters
  | 1 dimes
  | 0 nickels
  | 3 pennies
  | total_coins():
  | which is 88 cents
  | 
  `----


  Make sure to complete both assembly functions and test them via
  ,----
  | make test
  `----

  before using
  ,----
  | make zip
  `----

  to create a zip to submit.

8 Submission

Follow the instructions at the end of Lab01 if you need a refresher on how to upload your completed lab zip to Gradescope.


Author: Chris Kauffman (kauffman@umn.edu)
Date: 2023-02-27 Mon 08:28