Homework 3: Binary Product
This is the first of two assignments in which you will write binary code for the simple machine you created a simulator for in lab. Both homework 3 and homework 4 assume that you have understood that lab’s content well.
The instructions
icode
Behaviors: for each icode (3-bit) value, which operation to perform given the operands.
icode | operation | ||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|
0 |
| ||||||||||
1 |
| ||||||||||
2 |
| ||||||||||
3 | do different things for different values of
| ||||||||||
4 |
| ||||||||||
5 | write | ||||||||||
6 | do different things for different values of
In all 4 cases, increase | ||||||||||
7 | Compare |
Running programs
You should create two files
- One you work with, that has comments and notes to keep you sane. Call this anything you like.
- One you run and submit, which contains nothing but hex bytes separated by white space. You’ll submit this as a file named
product.binary
(orproduct.binary.txt
if needed)
To test your code, do one of
python3 sim_base.py product.binary
or
java SimBase product.binary
or using the online simulator below, and click the “Browse…” button at the top of the callout pane to load your product.binary
into the simulator’s memory.
Online Simulator
this should vanishthis should also
with
Your task
Your code should
- Load the values in memory at addresses
0x01
and0x03
into registers- Note: since we have not discussed ways to get other data into our memory yet, we will directly modify your code so that the second (
0x01
) and fourth (0x03
) bytes are the input values. This means your first (0x00
) and third (0x02
) bytes (instructions) should be very specific operations.
- Note: since we have not discussed ways to get other data into our memory yet, we will directly modify your code so that the second (
- Compute the product of the absolute value of those values (i.e., abs(what’s at
0x01
) × abs(what’s at0x03
)), as described below - Store the product at address
0xE0
- Halt once it is done
You should ignore overflow, so since 0x79
× 0x23
= 0x108B
, the answer should be 0x8B
. This is likely to happen automatically without your explicit planning for it.
For example, if product.binary
begins __ 10 __ 06
then when it is finished it should have 60
in address 0xE0
; in decimal, that is 16 × 6, which is 96. If product.binary
begins __ F8 __ FB
then when it is finished it should have 28
in address 0xE0
; in decimal, that is -8 × -5, which is 40. Similarly, if product.binary
begins __ F8 __ 06
then when it is finished it should have 30
in address 0xE0
; in decimal, that is abs(-8) × 6 = 8 × 6, which is 48.
Note: We should be able to change the second and fourth bytes of your program to do other product calculations, too.
Either operand may be negative or zero! If either operand is 0, your code should set the value at 0xE0
to 00
, which will likely happen automatically in the course of calculating the product. However, if either operand is negative, you may want to change your inputs before calculating the product.
Note: For full credit, your binary program should calculate the product of absolute values (see the note below) and store the result in 0xE0
. You should ignore overflow when performing the calculation.
Bonus Opportunity
For up to 12 bonus points (a 2-point bonus on each of 6 autograder tests), your program should account for negative result values, which requires keeping track of the number of negative inputs. This will require storing some information in memory, as you’ll need more than the 4 variables (i.e., registers) available. Remember, you should ignore overflow when performing the calculation.
For example: if
product.binary
begins__ F8 __ 06
then when it is finished it should haveD0
in address0xE0
; in decimal, that is -8 × 6, which is -48.
Hints, tips, and suggestions
How to compute product
You may be familiar with fancier ways, but a simple definition of multiplication that will result in reasonable-to-write code is
- Definition
x
×y
means the sum ofy
x
s; that is,x
+x
+x
+ … +x
, where the number ofx
s isy
.
Negative values: If either x
or y
are negative, then the definition above still works as long as we convert the negative numbers to positive numbers. Essentially, calculate the absolute value abs()
of both x
and y
and use the definition above (abs(x)
× abs(y)
). If both x
and y
are negative (or positive), then the result should be positive. If only one of x
and y
is negative, and we want to calculate the true product, then the result should be negative.
You definitely want to make sure you can write working code for this in some language you know well before trying to convert that code into binary.
How to write binary
We suggest following these steps, carefully, saving the result of each in a file so you can go back and fix them if they were wrong:
- Write pseudocode that does the desired task
- Convert any
for
loops towhile
loops with explicit counters - Change any
if
orwhile
guards to the formsomething <= 0
a <= b
becomesa-b <= 0
a < b
becomesa+1 <= b
becomesa+1-b <= 0
a >= b
becomes0 >= b-a
becomesb-a <= 0
a > b
becomes0 > b-a
becomesb+1-a <= 0
a == b
becomesa-b == 0
becomes!(a-b) == 1
becomes!!(a-b) <= 0
a != b
becomesa-b != 0
becomes!(a-b) == 0
becomes!(a-b) <= 0
- Add more variables to split multi-operation lines into a series of single-operation lines
- Add more operations to convert ones not in the instruction set into ones in the instruction set
- Change each loop into a pair of instructions, opening with “
spot1
=pc
” and closing with “if …, gotospot1
” - Count the number of variables needed
- Pick a memory address for each variable. Make these big enough your code is unlikely to get that big; for example, you might pick
0x80
through0x80
+ number of variables - Convert each statement that uses variables into
- register ← load variable’s memory
- original statement
- store variable’s memory ← register
- translate each instruction into numeric (
icode
,a
,b
) triples, possibly followed by aM[pc+1]
immediate value - turn (
icode
,a
,b
) into hex - Write all the hex into
product.binary
Debugging binary is hard. That’s part of why we don’t generally write code in binary. If you get stuck, you should probably try pulling just the part you are stuck on separate from the rest and test it until it works, then put it back in the main solution.
Submit
Submit your product.binary
file via Gradescope.