Lab $5-$ Binary Fibonacci

This lab you will write binary code $($using our Toy ISA$)$ you will run your code on our online simulator $.$

The Instructions

The instructions from our machine are below for reference.

icode Behaviors:

icode operation

$0$

rA $=$ rB

$1$

rA $+=$ rB

$2$

rA &$=$ rB

$3$

rA $=$ read from memory at address rB

$4$

write rA to memory at address rB

$5$

do different things for different values of b:

b action

$0$ rA $=$ ~rA

$1$ rA $=-$rA

$2$ rA $=!$rA

$3$ rA $=$ pc

$6$

do different things for different values of b:

b action

$0$ rA $=$ read from memory at pc $+1$

$1$ rA $+=$ read from memory at pc $+1$

$2$ rA &$=$ read from memory at pc $+1$

$3$ rA $=$ read from memory at the address stored at pc $+1$

In all $4$ cases, increase pc by $2,$ not $1,$ at the end of this instruction

$7$

Compare rA $($as an $8-$bit $2$s$-$complement number$)$ to $0$; $-$ if rA $<=0,$ set pc $=$ rB $-$ otherwise, increment pc like normal.

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 by hex bytes separated by white space. You$$ll submit this as a file named fib.binary

To our online simulator and click the file upload button at the top of the page to load your fib.binary into the simulator$$s memory.

Your Task

Create a binary program $($i$.$e$.,$ a file containing hex bytes$)$ that runs in this language; name the file fib.binary.

When run in a simulator $(../$homework$/$files$/$toy$-$isa$-$sim.html$)),$ fib.binary should change the contents of memory for all addresses i $>=$ C$016,$ placing in address i the i$-0$xC$0$th Fibonacci number $($modulo $256,$ since these are bytes$).$

Once $0$xC$0$ through $0$xFF are set, halt by running an instruction with the reserved bit set.

The file fib.binary itself must not contain more than C$016(19210)$ hexadecimal bytes.

It should be the case that running your simulator on fib.binary for many cycles should result in output ending with the following:

$0$xc$0-$cf: $0101020305080$d $1522375990$ e$97962$ db

$0$xd$0-$df: $3$d $18556$d c$22$f f$12011314273$ b$528$ dd $05$

$0$xe$0-$ef: e$2$ e$7$ c$9$ b$07929$ a$2$ cb $6$d $38$ a$5$ dd $825$f e$140$

$0$xf$0-$ff: $216182$ e$36548$ ad f$5$ a$29739$ d$009$ d$9$ e$2$ bb

Your code should not change the byte stored in address $0$x$00$ during its run. Your code must finish within $2048$ clock cycles.

Hints, tips, and suggestions

How to compute Fibonacci numbers

Keep track of two numbers, current and previous. Start them both off at $1.$

Let next be the sum of current and previous.

Rename current $->$ previous, next $->$ current $($in that order$)$

Repeat

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 to while loops with explicit counters

Change any if or while guards to the form something $<=0$

a $<=$ b becomes a$-$b $<=0$

a $<$ b becomes a$+1<=$ b becomes a$+1-$b $<=0$

a $>=$ b becomes $0>=$ b$-$a becomes b$-$a $<=0$

a $>$ b becomes $0>$ b$-$a becomes b$+1-$a $<=0$

a $==$ b becomes a$-$b $==0$ becomes $!($a$-$b$)==1$ becomes $!!($a$-$b$)<=0$

a $!=$ b becomes a$-$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 $$spot$1=$ pc$$ and closing with $$if $...,$ goto spot$1$

Count the number of variables needed

If$1$ it is $<=4,$ skip to step $10$

else$2,$ continue with next step

Pick a memory address for each variable. Make these big enough your code is unlikely to get that big; for example, you might pick $0$x$80$ though $0$x$80+$ number of variables

Convert each statement that uses variables into a$.$ register $$ load variable$$s memory b$.$ original statement c$.$ store variable$$s memory $$ register

translate each instruction into numeric $($icode$,$ a$,$ b$)$ triples, possibly followed by a M$[$pc$+1]$ immediate value

turn $($icode$,$ a$,$ b$)$ into hex

Write all the hex into fib.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. Please know that your TAs are here in lab to help as well!

Please show me how to code this my code doesn't work.

My code: $001100130$ C$0124301201373$

Feedback:

$0)$ Check submitted files $(0/0)$

Missing fib.binary

If you submitted a file named "fib.binary.txt$"$ you may ignore this message,

butfor future labs you will have to rename and resubmit.