Lab 5 BCD
Lab 5: Register-based Assembler Code
Dates
Early Saturday 6-Nov-2021 at 11:58PM
On Time by Tuesday 9-Nov-2021 at 11:58 PM
Late cutoff at Wed 10-Nov-2021 at 1158 PM
Topics
Bitwise operations
Loops & conditions
Register allocation
Contents
Dates …………………………………………………………………………………………………………………………………………. 1
Early Saturday 6-Nov-2021 at 11:58PM ………………………………………………………………………………………. 1
On Time by Tuesday 9-Nov-2021 at 11:58 PM …………………………………………………………………………….. 1
Late cutoff at Wed 10-Nov-2021 at 1158 PM ………………………………………………………………………………. 1
Topics ………………………………………………………………………………………………………………………………………… 1
Overview ……………………………………………………………………………………………………………………………………. 2
Lab Requirements: 3 parts ……………………………………………………………………………………………………………. 2
Reverse …………………………………………………………………………………………………………………………………… 3
Adjust …………………………………………………………………………………………………………………………………….. 3
Everything ………………………………………………………………………………………………………………………………. 4
Shims …………………………………………………………………………………………………………………………………………. 4
Input and Output ………………………………………………………………………………………………………………………… 5
How on Earth… ……………………………………………………………………………………………………………………………. 5
Register Allocation ………………………………………………………………………………………………………………………. 6
Required Stuff …………………………………………………………………………………………………………………………….. 6
Comments ………………………………………………………………………………………………………………………………….. 6
GDB …………………………………………………………………………………………………………………………………………… 6
Readme ……………………………………………………………………………………………………………………………………… 7
Submission …………………………………………………………………………………………………………………………………. 7
Overview
This lab deals with packed Binary Coded Decimal (BCD) data. Packed BCD places one decimal digit in
each nibble of data format such as a 4-byte integer. For our purposes, it is unsigned. Thus the decimal
number 12345678 is stored as 0x12345678. So you read the number in hex and treat it as a binary
number. This makes the hex digits A-F invalid in our number.
Our lab deals with correcting a BCD number that is the result of adding two BCD numbers. Consider:
12345678
+ 55555555
———-
67901233
However, our adder is binary and thus adds as if these were hexadecimal numbers:
12345678
+ 55555555
———-
6789ABCD
We could write cod that adds a nibble at a time and adjusts each nibble, possibly generating a carry to
the next higher nibble at each stage. We won’t do that. Instead, we can adjust the hex sum, nibble by
nibble, going right to left, turning any value higher than 10 into the right number and introducing a carry
to the next stage.
For example 0xD (the least significat nibble of the sum) is 13 decimal and bigger than 9. If we add 6 to
13 we get 19 decimal which is 0x13. The 3 is the number we want and the one represents the carry we
need to add to the next higher nibble (the C, which is how 12 turns into 13). We will always add 6 to any
number higher than 9 to get the hex to yield the right BCD.
Lab Requirements: 3 parts
The regular lab 5 will have three assembler functions, named adjust, reverse, and everything:
1. Adjust an unsigned int, yielding an unsigned int with the nibbles in the wrong order
2. Reverse the nibbles of an unsigned int yielding another unsigned int
3. A function that does everything (calls adjust then calls reverse)
In C terms:
Your three functions must meet the following C code interface:
unsigned int reverse(unsigned int broken);
unsigned int adjust(unsigned int broken);
unsigned int everything(unsigned int sum);
It’s best to do these in 2-1-3 order. Reverse is easier than adjust and will give you practice with the kind
of assembler code you will need to write for the more involved adjust function. The everything function
is extremely short and simple and can be considered a victory lap once adjust is working. Each function
should be written in its own dot s file and named accordingly – see the supplied makefile.
All functions must make appropriate decisions about what registers they use. The steps given below
each convert to between one and perhaps six assembler instructions each. Before writing any code,
carefully examine the method to determine how many different data values you will need. All functions
must establish and correctly tear down a stack frame, even those functions that don’t need one.
“Isolate the lower nibble” means “and with 0x0F.” Be careful about not trashing data you still need.
Reverse
Reverse is less complex than adjust, so do reverse first for experience. The basic method is something
like this:
1. Start with 0 for an answer
2. Shift the answer left by 4 bits to make room for the next nibble
3. Isolate the low order nibble from the reversed value
4. Or that nibble onto the answer
5. Since we have dealt with the lowest order nibble of the reversed value, shift the broken value 4
bits right
6. Repeat 2-5 for a total of eight times to get the final answer and return it
Since we start with the low order nibble of the reversed value and keep shifting it left in the answer, we
re-order the nibbles. Test this code with the rtest target in the makefile. Carefully go over just how
many registers you will need and write down what each one means.
Adjust
Adjust is similar to reverse, but more work happens to get the job done. (The loop could be upwards of
16 or more assembler instructions.)
1. Start with 0 for an answer and 0 for the carry value
2. Shift the answer left by 4 bits to make room for the next nibble
3. Isolate the low order nibble from the input (into a byte value with a zero in the high nibble)
4. Add the carry value for the previous stage to the nibble
5. If the nibble is now greater than 9, add 6 to it. This will put a 1 in the high nibble and leave the
low nibble with the value we want.
6. Isolate the low 4 bits of that nibble into a temporary
7. Or the temporary into the answer
8. Right shift the byte holding the isolated nibble by 4 bits, getting rid of the 4 bits you just isolated
and leaving the upper nibble as the lower nibble. It will be 1 if you had generated a carry and
zero if you didn’t.
9. Set the carry to that value so we have the carry for the next stage
10. Shift the input 4 bits to the right since we are finished with the lowest nibble.
11. Repeat steps 2-10 for a total of eight times
12. Return the answer
Use the attest target in the makefile to test the code. The result will be the adjusted value in reverse
order. Carefully go over just how many registers you will need and write down what each one means.
Copy the text of the above steps and start expanding them into assembler steps, noting any variable
that you need.
Everything
This one is quite simple. Call ashim, the first parameter is already in the right place. Move the return
value of that call to the first parameter and call rshim. The return result we want is already in the
correct register.
Shims
Note that none of your code ever calls the 3 functions directly. There are 3 “shims” that fit between
your code and any function that calls your code. These come from the l5files.zip archive on Piazza.
There are 3 such shims:
ashim is used when you want to call adjust. It calls adjust for you.
rshim is used when you want to call reverse. It calls reverse for you.
eshim is used when code wants to call everything. It calls everything for you.
In C terms:
unsigned int rshim(unsigned int broken);
unsigned int ashim(unsigned int broken);
unsigned int eshim(unsigned int sum);
These shims serve a few purposes:
If your calling code depends on a caller saved register not getting trashed, the shims will
disabuse it of any such notion. No matter what your functions do, the shims will scramble every
caller-saved register that they can get away with.
If any of your three functions fails to properly save and restore any callee-saved registers that
they use, the shim will detect it for any register other than %rbp. This will become important in
lab 6 when you are likely to use more callee-saved registers.
Each shim lives in its own dot o file supplied in the l5files.zip archive.
Input and Output
The above screenshot shows correct output for each test. There are no input files.
How on Earth…
You might find the following assembler operations useful:
Bitwise AND – for masking off bits you don’t need
Bitwise OR – for setting select bits you want set.
Shifting both left and right (logical, not arithmetic)
Inc and dec (The increment and decrement opcodes) – handy for loop indices
Test and compare – sets those flags
Conditional jumps – use those flag bits to alter control flow
https://en.wikibooks.org/wiki/X86_Assembly
Along with that consider:
How do you write a loop?
How do you write an if statement?
Conditional move might be handy
Math tricks with lea might be handy
movzbl or movzbq might be handy
https://en.wikibooks.org/wiki/X86_Assembly
Register Allocation
Register allocation policy is graded.
The adjust and reverse functions are leaf level functions and should not make any function calls. This
tells you loads about what registers you will need to use.
The everything function makes function calls, so the choice of which set of registers to prefer is not
automatic. The question to ask yourself is, “Does this function have data that needs to survive a
functions call?” The answer guides you to which tribe of registers should be used. The issue of register
pressure will be in lab 6, not here.
You really do want a firm grasp on register allocation before you take the final exam, so work it out here
and in lab 6. Before you write any code, figure out how many “variables” you will need and assign them
to registers of the appropriate type.
Required Stuff
All of your functions must create a stack frame upon entry and tear it down upon exit.
The first usage of any register in a function must have a comment telling what that register means. For
example:
xorq %rax, %rax # rax is both a subscript and return value at the same time.
This is usually near the top of your function. It is your pocket guide to the registers. In your comments
you should refer to the registers not by name but by what they mean.
Comments
Comment your code. Comments should say things that are not obvious from the code. In assembler
you could easily have something to say for every line of code. You could easily have more comment lines
than code lines. Comment what each register holds. Comment about how the operation has a higher
level meaning. Try to avid comments that say the exact same thing as the code.
Put your name and the assignment number in your initial comments. Also add the statement that says
that you wrote all of the code in the file (see below). Or you can forget it and get a zero on the lab.
GDB
The first time it builds, run it under gdb and step through your code. Invoke tui reg general and predict
how each register will change before you take each step. Watch the digits appear (in hex) in your
answer register.
Probable bugs: Reversing the sense of a condition runs very high on the list!
Probable bugs: Mixing up two register names. This language is hot revenge for all those times you might
have slacked off and picked a less-than-stellar variable name when you had 32 characters at your
disposal.
DO NOT CALL PRINTF! Trying to debug with printf is negative progress; it makes things worse.
Imagine a grainy blue hologram: “Help me, GDB. You’re my only hope.”
Readme
As always, create a text README file, and submit it with your code. All labs require a readme file.
Include:
Your name
Hours worked on the lab
Short description of any concerns, interesting problems, or discoveries encountered. General
comments about the lab are welcome.
Submission
No surprises here. Your zip file needs:
A readme file
All of your .s files
Makefile
The supplied .c files and shim .o files
Be sure to add this text to ALL of your .s files:
# BY SUBMITTING THIS FILE AS PART OF MY LAB ASSIGNMENT, I CERTIFY THAT
# ALL OF THE CODE FOUND WITHIN THIS FILE WAS CREATED BY ME WITH NO
# ASSISTANCE FROM ANY PERSON OTHER THAN THE INSTRUCTOR OF THIS COURSE
# OR ONE OF OUR UNDERGRADUATE GRADERS. I WROTE THIS CODE BY HAND,
# IT IS NOT MACHINE GENRATED OR TAKEN FROM MACHINE GENERATED CODE.
If you omit a required file, you get zero points.
If you fail to add the above comment you get zero points
If the make command as given generates any warnings or errors you get zero points
This is one of the easiest labs to get full marks on, don’t blow it.
Bonus +2 points
Write main as an assembler function to give an all-assembler lab. Create a new target in the makefile
for this. Be careful about register selection and proper usage – main does make many calls and it does
have values that need to survive a function call.
Do points math early on in development. An early lab with this bonus should score well even if it lacks a
working adjust function. (If you get into trouble, have adjust return the value it was given. That way it
compiles and everything can be shown to work with your reverse.)