Assignment 11: Assembly Puzzles Part 2
You can access the repository for this assignment here.
Overview
In this assignment you’re tasked with creating more functions using assembly language. There are two big differences between this assignment and the last:
 This assignment requires control logic (loops, if statements, etc.).
 This assignment uses arrays (one dimensional).
As before, you will likely want to keep the AVR Assembly Reference handy as well as the rules for register usage. Make sure you are using registers appropriately  we will be checking for this when you demo. Some of the functions you have to complete are both called and call another function — they need to follow both the callsaved and the callused conventions!!! Use the Stack!
Goals
The goal of this assignment is to implement basic functions in assembly language. The functions chosen are examples that may actually be implemented in assembly rather than a higher level language.
The main concepts are:
 Division: As you may have noticed, the AVR we’re using doesn’t have a division instruction! You’ll implement two types of division: 8bit unsigned integer division and 16bit unsigned integer division. Both will do division the “slow” way. Remember that multiplication is basically repeated addition. Division, as the inverse of multiplication, can be accomplished via repeated subtraction.
For example: to compute 9/4 we could try to repeatedly subtract 4 from 9:Step 1: 94 = 5 Step 2: 54 = 1 We have less than 4 left, so we're done. There were just 2 steps, so 9/4 must be 2.
Another example. 36/7:
Step 1: 367 = 29 Step 2: 297 = 22 Step 3: 227 = 15 Step 4: 157 = 8 Step 5: 87 = 1 We have less than 7 left, so we're done. There were just 5 steps, so 36/7 must be 5.
(This, of course, isn’t the approach used by “long division” that you learned in school. Using the BigO notation covered in CSE247, the approach shown here does steps. Typically computers use a different approach that is quite like “long division” and only does steps, which is much faster. Consequently we’re referring to the approach here as “slow”).

Modulus: Modulus is related to division however instead of the quotient, we are looking for the remainder. For this problem, we want you to use the division function you wrote (by calling it from your modulus function), taking the result and performing multiplication (using the AVR Instruction, NOT the method you wrote in studio), then finally some subtraction to determine the remainder. Note again, that this is not the most efficient way of performing modulus, but it does give you good practice using various AVR instructions.
 Summing odd numbers within a range: You will be given two values, and then must sum all of the odd values within that range (inclusive). For example, if the values you are given are 2 and 7 then the result would be 3 + 5 + 7 = 15.
To keep things as simple as possible all values are unsigned. In C the 8bit values are uint8_t
(which is the same as a byte
and 16bit values are uint16_t
.
The assignment
In your repository you will find an cse132assignment11/assignment11Demo
Arduino project. This project contains the prototypes for the functions we are asking you to write as well as code to test your work.
The Assembly language functions may be easier to write if you have already tested the logic using C. There are four Cfunctions you’ll need to complete in assignment11Demo.ino
:
uint16_t slowDivisionAlgorithm8(uint8_t dividend, uint8_t divisor)
: This function will do division of 8bit values the “slow” way.uint16_t slowDivisionAlgorithm16(uint16_t dividend, uint16_t divisor)
: This function will do division of 16bit values the “slow” way. (And may look a lot like the 8bit version. None the less, note the differences!)uint16_t slowModulusAlgorithm(uint8_t dividend, uint8_t divisor)
: This function will return the remainder of the dividend divided by the divisor, and should call yourslowDivisionAlgorithm8
function.uint16_t sumOdds(uint8_t a, uint8_t b)
: This function will sum all of the odd values that occur between a and b (inclusive). You should use yourmodulus
function to solve this problem.
There are five functions to complete entirely in assembly language:
uint8_t slowDivisionUint8(uint8_t a, uint8_t b)
: An 8bit division using assembly language. Use the Ccode version as a guide for the logic of your assembly language version.bool greaterThanOrEqualUInt16(uint16_t a, uint16_t b)
: Testing logic conditions on multibyte values is a little trickier than just thecp
based comparisons we’ve covered so far. Create a multibyte comparison function. It may help to think carefully about a variety of test cases (and even write them out as 2byte hex values).uint16_t slowDivisionUint16(uint16_t a, uint16_t b)
: Implement a 16bit division algorithm. Again, use your Ccode version as a prototype. (Hint: You may need to do comparisons of 16bit values. You may want to try tocall
on some of your earlier work)unit16_t slowModulusUint8(unit8_t a, uint8_t b)
: Implement a modulus operation on 8bit operators, using yourslowDivisionUint8
function.uint16_t sumOddsUint8(uint8_t a, uint8_t b)
: This function will sum all of the odd values that occur between a and b (inclusive). You should use yourslowModulusUint8
function to solve this problem.
Getting Started
Assembly language can be challenging. The provided files include several test cases to help you with your work. Here’s the approach we suggest:
 assignment11Demo.ino includes a lot of code to help you with testing. The
setup()
includes calls to all test cases. There are two styles of tests:
Standalone test cases, like:
uint8_t dividend8 = 175; uint8_t divisor8 = 26; uint8_t quotient8ASM = slowDivisionUint8(dividend8,divisor8); uint8_t quotient8Alg = slowDivisionAlgorithm8(dividend8,divisor8); pprintf("slowDivisionAlgorithm8(%u,%u) is %u (algorithm) and %u (assembly); Should be %u\n", dividend8, divisor8, quotient8Alg, quotient8ASM, dividend8/divisor8);
These tests will run just a single test case, which is probably what you need to do when debugging.

More rigorous tests are included in “test functions”, like on Assignment 10. They can be run via function call, like:
// Full Test: testSlowDivisionUint8();
You will want to comment/uncomment test cases so you can focus on each part independently.


It’s probably best start with the Ccode version of 8bit division. I.e., complete
slowDivisionAlgorithm8()
in assignment11Demo.ino. Use the test functions to test it (they will indicate the values printed by both the algorithm, which should be correct when you’re done with the Ccode, and the assembly language, which will still be incorrect) 
Write and test the assembly language version of 8bit division:
slowDivisionUint8
in assignment11.S. 
Try the assembly language version of comparisons — do
greaterThanOrEqualUInt16
in assignment11.S. Again, test your work. 
Do the C version of 16bit division. Complete
slowDivisionAlgorithm16()
in assignment11Demo.ino. 
Now try the assembly language version of 16bit division:
slowDivisionUint16
in assignment11.S. This may be the most difficult part of the assignment. (Hint: 16bit subtraction can be done with just two instructions) 
Complete the two modulus functions:
slowModulusAlgorithm
andslowModulusUint8
. Don’t forget to use your division functions in your solution  we will be checking for this.  Complete the two functions for summing odd numbers within a given range. Keep in mind that the range is inclusive, so if the min or max is an odd number it should be included in the sum. You may assume that the first argument will always be less than or equal to the second argument (you do not have to check for this in your code).
A Word on Multiplication
It is in your best interest to read up on the AVR Multiplication Instruction before attempting to complete the modulus function.
Note that the multiplication instruction is expecting two unsigned 8bit values as input, producing a 16 bit result. This does not quite match up with what we will have since one of our values will be an 8bit unsigned integer (the divisor), but one of them will be a 16bit unsigned integer (the output from the slowDivision
function). For the purposes of this function, you may simply ignore the most significant byte of the 16bit value and perform the multiplication with the least significant byte.
The output of the multiplication instruction will be placed in r0 and r1. Note, however, that r1 is a special register that is expected to contain zero. What this means is that if you use a multiplication instruction, you must read the value out of r1 and set it back to zero as soon as possible.
Checkout
 Commit your code and verify in your web browser that is is all there.
 Check out with a TA.
The rubric
 100pts total:
 C functions
 slowDivisionAlgorithm8 (5 pts)
 slowDivisionAlgorithm16 (5 pts)
 slowModulusAlgorithm (5 pts)
 sumOdds (5 pts)
 AVR Assembly functions
 slowDivisionUint8 (10 pts)
 slowDivisionUint16 (10 pts)
 slowModulusAlgorithm (10 points)
 greaterThanOrEqualUInt16 (10 pts)
 sumOddsUint8 (15 pts)
 Correct usage of callsaved registers (10 pts)
 Misc. (5 pts)
 Code style (10 pts)
 C functions