<jupyter_start><jupyter_text>HW2: Computer Architecturev1.0 (2021 Spring): <NAME>, <NAME>**Time budget: 6 hours**In this part we will take a shallow dive into the deep topic of computer architecture. In the first part of this project we will explore the world of assembly, the very simple class of operations underneath the execution of every program you run.For this assignment we have created the Catatonic Processor, an imaginary Instruction Set Architecture (ISA) that should hopefully be fairly easy to learn compared to the convoluted mess of ISAs like [x86](https://www.felixcloutier.com/x86/). (If you'd like to learn more about a real ISA, take a look at Berkeley's very own [RISC-V](https://github.com/jameslzhu/riscv-card/blob/master/riscv-card.pdf)). Catatonic ProcessorCatatonic instructions are formed with Python tuples and execute from an instance of the `Memory` class, which is essentially a wrapper around a list. (A class instance is, roughly speaking, a custom object that the programmer can define: `MachineState` and `Memory` below are both these kinds of objects.) For example the following code would instantiate an instance of the catatonic processor with 256 memory slots, add two registers, and output the result:```pythonm = MachineState(Memory(256))program = Memory([    (ADD, T0, T2, A0),    (OUT, T0)])m.run_program(program)```Below is a lot of code that instantiates the simulator. At the top, you can see all of the instructions we have defined. If you're interested, feel free to peruse the code. Then you can run the cell, and minimize it if you're on JupyterLab.**Fun CS Principles Teaching Moment**: this is a fun example of an abstraction barrier! You don't have to know how the instruction set works internally to be able to use it in later questions. It might help you understand some things, but you can understand bigger objects by themselves. For example you don't need to know *how* `MachineState` interprets register names and retrieves values: you just need to know that it *does*.Remember throughout that you can get the docstring of any function with `help(...)`<jupyter_code>from numpy import int32

# Format: (INST, A, B, C)

# Registers:
# A[0..7] -> Function argument and return value registers
# T[0..7] -> Temporary Registers
# S[0..7] -> Saved Registers
# RA      -> Return Address
# IP      -> Instruction Pointer
# ZZ      -> Zero Register

ADD = "ADD" # A = B + C
SUB = "SUB" # A = B - C
MUL = "MUL" # A = B * C
DIV = "DIV" # A = B // C
REM = "REM" # A = B % C

AND = "AND" # A = B & C
OR  = "OR"  # A = B | C
XOR = "XOR" # A = B ^ C
NOT = "NOT" # A = ~B

SHL = "SHL" # A = B << C
SHR = "SHR" # A = B >> C

MOV = "MOV" # A = B
SLT = "SLT" # if B < C then A = 1 else A = 0

BEQ = "BEQ" # if B == C; IP = IP + A
BNE = "BNE" # if B != C; IP = IP + A
BGE = "BGE" # if B >= C; IP = IP + A
BLT = "BLT" # if B < C ; IP = IP + A

JAL = "JAL" # A = IP + 1; IP = B

LD  = "LD"  # A = M[B + C]
ST  = "ST"  # M[B + C] = A

PSH = "PSH" # S[SP + 1] = A; SP = SP + 1
POP = "POP" # A = S[SP]; SP = SP - 1

OUT = "OUT" # print(A)
HLT = "HLT" # Stop program

# Psuedoinstructions
CALL= "CALL" # JAL RA, A
RET = "RET" # JAL ZZ, RA

A0 = "A0"
A1 = "A1"
A2 = "A2"
A3 = "A3"
A4 = "A4"
A5 = "A5"
A6 = "A6"
A7 = "A7"

S0 = "S0"
S1 = "S1"
S2 = "S2"
S3 = "S3"
S4 = "S4"
S5 = "S5"
S6 = "S6"
S7 = "S7"

T0 = "T0"
T1 = "T1"
T2 = "T2"
T3 = "T3"
T4 = "T4"
T5 = "T5"
T6 = "T6"
T7 = "T7"

RA = "RA"
IP = "IP"
ZZ = "ZZ"

class Stack:
    """
    Create a stack (https://en.wikipedia.org/wiki/Stack_(abstract_data_type))
    with an optional size limit. If the size limit is exceeded, then drop the
    oldest data in the stack.
    
    This is essentially just a Python list with a limit on the maximum length.
    
    Attributes
    ----------
    storage : list
        The elements in the stack.
    size : int
        The maximum number of elements in the stack.
    """
    def __init__(self, size = 0):
        """
        Initilize a stack with a given size. If size is 0 then the stack is
        infinitely deep.
        
        Arguments
        ---------
        size : int
            The maximum number of elements in the stack.
            
        Returns
        -------
        None
        """
        self.size = size
        self.storage = []
    
    def push(self, val):
        """
        Push an item to the bottom of the stack, and resize if we exceed the
        size.
        
        Arguments
        ---------
        val : any
            The value to push to the stack.
            
        Returns
        -------
        None
        """
        self.storage.append(val)
        if self.size != 0 and len(self.storage) > self.size:
            self.storage = self.storage[len(self.storage) - self.size:]
    
    def pop(self):
        """
        Pop an item off of the bottom of the stack.
        
        Arguments
        ---------
        None
        
        Returns
        -------
        None
        """
        return self.storage.pop()
    
    def contains(self, obj):
        """
        Check if the stack contains obj.
        (We use this to cache addresses and implement our sized-cache).
        
        Arguments
        ---------
        obj : any
            The object we want to check.
            
        Returns
        -------
        bool
            True if obj is in the stack, False otherwise
        """
        if self.size == 0:
            return True
        return obj in self.storage

class Memory:
    """
    A simple wrapper around lists to provide a memory-like interface.
    ("")
    
    Parameters
    ----------
    mem : list
        The underlying list.
    """
    def __init__(self, dat):
        """
        If dat is an integer, initialize memory filed with zeros of that size
        If dat is a list, copy that list into our memory.
        
        Arguments
        ---------
        dat : int or list
            The initial data.
        """
        if type(dat) == int:
            self.mem = [int32(0) for i in range(dat)]
        elif type(dat) == list:
            self.mem = dat.copy()

    def load(self, address):
        """
        Load data from 'address'.
        
        Arguments
        ---------
        address : int
            The address we want to access.
        
        Returns
        -------
        int
        The data at that address.
        
        Quick comment: This isn't a very complicated function.
        You might wonder why we would bother doing m.load(address) when we could just do m.mem[address] explicitly.
        The answer, again, is abstraction barriers! We shouldn't *have* to know that Memory works based on a list
        to use it. So if it has bugs, or we want to change it later, or we just don't want to read the code,
        we have the freedom to do that without causing a bunch of changes downstream.
        
        Some languages have features that actually prevent you from doing things like m.mem[address]: the class will
        *hide* details like that from you, to be sure you don't accidentally break abstraction. Python doesn't do that,
        but you should pretend it does.
        """
        return self.mem[address]

    def store(self, address, data):
        """
        Store data to 'address'.
        
        Arguments
        ---------
        address : int
            The address where we want to store data.
        data : int
            The data to store.
            
        Returns
        -------
        None
        """
        self.mem[address] = data

class MachineState:
    """
    Store machine state (registers, memory, stack, and instruction pointer).
    
    Parameters
    ----------
    memory : Memory
        The memory. (A shock, I know)
    stack : Stack
        Contains values pushed to the stack with push, useful for saving/restoring registers across calls
    argregs : Memory
        The registers containing arguments and return values.
    saved : Memory
        Contains registers intended to be preserved across calls
    temporaries : Memory
        Registers that can be safely overwritten through calls
    instruction_pointer : int
        Contains the address of the instruction that's currently executing 
    return_address : int
        Holds the address of the caller function during a call, so that the called function knows where to return to
    output_print : bool
        Whether to print the output or not. (This is a super common setting in many functions: often it's called something like "verbose")
    output_stack : list
        Stores outputed data for one execution finishes, so that we can test your programs
    cache : Stack
        Simulates a cache by keeping the addresses of the last n=cachesize accessed memory values so that we know that these have a lower access cost
    """
    def __init__(self, memory, output_print = True, cachesize = 0):
        self.memory = memory
        self.stack = Stack()

        self.argregs     = Memory(8) # Argument/Return Value registers
        self.saved       = Memory(8) # Callee-saved Registers
        self.temporaries = Memory(8) # Caller-saved Registers

        self.instruction_pointer = 0
        self.return_address = int32(0)

        self.output_print = output_print
        self.output_stack = []
        self.cache = Stack(cachesize)

    def get_reg(self, reg):
        """
        Interperet a register name/immediate and retrieve its value
        
        Arguments
        ---------
        reg : int or str
            The register name.
        
        Returns
        -------
        register : int32
            The value at the register.
        """
        # Handle Immediates
        if type(reg) == int:
            return int32(reg)

        if len(reg) != 2 or type(reg) != str:
            raise ValueError("{} is not a valid register name".format(reg))

        if reg[0] == "A" and int(reg[1]) < 8:
            return self.argregs.load(int(reg[1]))
        elif reg[0] == "S" and reg[1] != "P" and int(reg[1]) < 8:
            return self.saved.load(int(reg[1]))
        elif reg[0] == "T" and int(reg[1]) < 8:
            return self.temporaries.load(int(reg[1]))
        elif reg == "RA":
            return int32(self.return_address)
        elif reg == "IP":
            return int32(self.instruction_pointer)
        elif reg == "ZZ":
            return int32(0)
        raise ValueError("{} is not a valid register name".format(reg))
    
    def set_reg(self, reg, value):
        """
        Interperet a register name and set its value
        
        Arguments
        ---------
        reg : int or str
            The register name.
            
        value : int
            The value to set.
        """
        if len(reg) != 2 or type(reg) != str:
            raise ValueError("{} is not a valid register name".format(reg))

        if type(value) != int32:
            raise ValueError("Registers can only store integers")

        if reg[0] == "A" and int(reg[1]) < 8:
            self.argregs.store(int(reg[1]), value)
        elif reg[0] == "S" and reg[1] != "P" and int(reg[1]) < 8:
            self.saved.store(int(reg[1]), value)
        elif reg[0] == "T" and int(reg[1]) < 8:
            self.temporaries.store(int(reg[1]), value)
        elif reg == "RA":
            self.return_address = value
        elif reg == "IP":
            self.instruction_pointer = value
        elif reg == "ZZ":
            return
        else:
            raise ValueError("{} is not a valid register name".format(reg))
    
    def reset(self):
        """
        Resets the instruction pointer and clears the output stack.
        
        Arguments
        ---------
        None
        
        Returns
        -------
        None
        """
        self.set_reg("IP", int32(0))
        self.output_stack = []
        

    def run_program(self, progmem):
        """
        Run the program in progmem until we hit a HLT (halt) instruction, then
        return a cycle count and the output stack.
        
        Arguments
        ---------
        progmem : Memory(tuple)
            The stored instructions to execute.
            
        Returns
        -------
        cycles : int
            The number of times the main loop is run.
        output_stack : list
            The outputs throughout the program.
        """
        cycles = 0
        while True:
            cycles += 1
            A = B = C = ZZ
            instruction = progmem.load(self.instruction_pointer)
            assert (type(instruction) == tuple and len(instruction) > 0 and len(instruction) < 5) or type(instruction) == str
            if type(instruction) == str:
                OP = instruction
            else:
                OP = instruction[0]
            if len(instruction) > 1:
                A = instruction[1]
            if len(instruction) > 2:
                B = instruction[2]
            if len(instruction) > 3:
                C = instruction[3]

            if OP == HLT:
                return (cycles, self.output_stack)
            elif OP == ADD:
                self.set_reg(A, int32(self.get_reg(B) + self.get_reg(C)))
            elif OP == SUB:
                self.set_reg(A, int32(self.get_reg(B) - self.get_reg(C)))
            elif OP == MUL:
                self.set_reg(A, int32(self.get_reg(B) * self.get_reg(C)))
            elif OP == DIV:
                self.set_reg(A, int32(self.get_reg(B) // self.get_reg(C)))
            elif OP == REM:
                self.set_reg(A, int32(self.get_reg(B) % self.get_reg(C)))
            elif OP == AND:
                self.set_reg(A, int32(self.get_reg(B) & self.get_reg(C)))
            elif OP == OR:
                self.set_reg(A, int32(self.get_reg(B) | self.get_reg(C)))
            elif OP == XOR:
                self.set_reg(A, int32(self.get_reg(B) ^ self.get_reg(C)))
            elif OP == NOT:
                self.set_reg(A, int32(~self.get_reg(B)))
            elif OP == SHL:
                self.set_reg(A, int32(self.get_reg(B) << self.get_reg(C)))
            elif OP == SHR:
                self.set_reg(A, int32(self.get_reg(B) >> self.get_reg(C)))
            elif OP == MOV:
                self.set_reg(A, int32(self.get_reg(B)))
            elif OP == SLT:
                if self.get_reg(B) < self.get_reg(C):
                    self.set_reg(A, int32(1))
                else:
                    self.set_reg(A, int32(0))
            elif OP == LD:
                address = self.get_reg(B) + self.get_reg(C)
                if not self.cache.contains(address):
                    cycles += 1000
                    self.cache.push(address)
                else:
                    cycles += 10
                self.set_reg(A, int32(self.memory.load(address)))
            elif OP == ST:
                address = self.get_reg(B) + self.get_reg(C)
                if not self.cache.contains(address):
                    self.cache.push(address)
                cycles += 10
                self.memory.store(address, self.get_reg(A))
            elif OP == OUT:
                blah = self.get_reg(A)
                if self.output_print:
                    print(blah)
                self.output_stack.append(blah)
            elif OP == PSH:
                cycles += 10
                self.stack.push(self.get_reg(A))
            elif OP == POP:
                cycles += 10
                self.set_reg(A, self.stack.pop())
            
            if OP == BEQ:
                if self.get_reg(B) == self.get_reg(C):
                    self.instruction_pointer += self.get_reg(A)
                else:
                    self.instruction_pointer += 1
            elif OP == BNE:
                if self.get_reg(B) != self.get_reg(C):
                    self.instruction_pointer += self.get_reg(A)
                else:
                    self.instruction_pointer += 1
            elif OP == BGE:
                if self.get_reg(B) >= self.get_reg(C):
                    self.instruction_pointer += self.get_reg(A)
                else:
                    self.instruction_pointer += 1
            elif OP == BLT:
                if self.get_reg(B) < self.get_reg(C):
                    self.instruction_pointer += self.get_reg(A)
                else:
                    self.instruction_pointer += 1
            elif OP == JAL:
                self.set_reg(A, int32(self.instruction_pointer + 1))
                self.instruction_pointer = self.get_reg(B)
            else:
                self.instruction_pointer = self.instruction_pointer + 1<jupyter_output><empty_output><jupyter_text>This is all you need to start with, but we'll also give you a few extra functions to help:<jupyter_code>def map_field(s, func_table):
    """
    Map a field from a function name to an immediate.
    Function names in assembly should be proceeded by the
    'f_' identifier
    
    s : any
        A function name
        
    """
    if type(s) == str and len(s) > 2 and s[0:2] == "f_":
        return func_table[s]
    return s 

def map_pseudoinstructions(inst):
    """
    Map the CALL and RET pseudo instructions to JAL
    """
    if type(inst) == str:
        inst = (inst,)
    if inst[0] == CALL:
        return (JAL, RA, inst[1])
    if inst[0] == RET:
        return (JAL, ZZ, RA)
    return inst

def assemble(funcs):
    """
    Assemble several functions into a program and replace
    any instances of 'f_' identifiers with the address of the 
    function
    """
    assert "f_main" in funcs

    prog = []
    func_table = {"f_main": 0}
    next_loc = len(funcs["f_main"])
    prog.extend(funcs["f_main"])
    for name in funcs.keys():
        if name == "f_main":
            continue
        func_table[name] = next_loc
        next_loc = next_loc + len(funcs[name])
        prog.extend(funcs[name])
        
    prog = [i if type(i) == tuple else (i,) for i in prog]
    mapped_prog = [tuple([map_field(i, func_table) for i in line]) for line in prog]
    return Memory([map_pseudoinstructions(inst) for inst in mapped_prog])

def test(result, expected):
    print("Running this program took {} cycles".format(result[0]))
    if len(result[1]) != len(expected):
        print(
            """
            The program outputed a different number of values than we were
            expecting. If you have debug (OUT) statements inserted, this is
            fine and is expected.
            
            GOT: {}
            EXPECTED: {}
            """.format(result[1], expected)
        )
        return
    for i, v in enumerate(result[1]):
        if v != expected[i]:
            print("Test {} FAILED: Got {}, Expected {}".format(i + 1, v, expected[i]))
        else:
            print("Test {} PASSED".format(i + 1))<jupyter_output><empty_output><jupyter_text>AssemblerIn order to simplify your life, we provide an assemble function. It takes a [dictionary](https://docs.python.org/3/tutorial/datastructures.htmldictionaries) of `(function names) -> (lists of instructions)`, and returns a Memory object of your program with every function combined, and all instances of function names replaced with their addresses in the program (function names are strings and must begin with "f_").The Memory object this returns can be run directly by the `run_program` method. The assemble function will always place the function `f_main` at the beginning of the program to act as the entry point (and main function should therefore halt instead of returning).For example to assemble three functions into a program, and run, you would do:<jupyter_code>source = {
    'f_main' : [
        (CALL, 'f_get1'),
        (OUT, A0),
        (CALL, 'f_get2'),
        (OUT, A0),
        (HLT)
    ],
    'f_get1' : [
        (PSH, RA),
        (MOV, A0, 1),
        (POP, RA),
        (RET)
    ],
    'f_get2' : [
        (PSH, RA),
        (MOV, A0, 2),
        (POP, RA),
        (RET)
    ]
}

m = MachineState(Memory(256))
prog = assemble(source)
result = m.run_program(prog)<jupyter_output><empty_output><jupyter_text>Before we move on, let's break this down a little more. We did several things in just a few lines of code, so let's recap. We- made a Memory object with 256 slots- made a MachineState object that uses that Memory object as its memory- gave that MachineState the name `m`- defined a "source", which gives names to sets of instructions (a list of tuples of strings)- assembled that source, converting those tuples of strings to functions we can call- ran the programEssentially, it's converting these sets of instructions to things we can call with Python. Let's take a look at what the instructions look like!<jupyter_code>source['f_get1']<jupyter_output><empty_output><jupyter_text>This is the assembly way of saying what we'd express in Python as `A0 = 1`, except here it also prints the result.  RegistersCatatonic is what is often referred to as a "[RISC](https://en.wikipedia.org/wiki/Reduced_instruction_set_computer)" ISA. One consequence of this is that most of its operations are *Register to Register* operations. This makes it very important to understand what registers are, and how to use them appropriately and safely.Almost all computers built today are what's called [register machines](https://en.wikipedia.org/wiki/Register_machine). This roughly means your computer has a fixed number of prenamed variables that can be operated on by the instructions. They are generally very fast to access (the computer I am writing this on can access them in less then a quarter of a nanosecond, the amount of time it takes for light to travel 3 inches). In comparison the main memory of your computer (your RAM) has an access latency hundreds to thousands of times larger. Therefore, to extract maximum performance from a computer, you want as much of your computation as possible to happen in registers.Catatonic has 3 sets of 8 general-purpose registers. These are functionally identical, but have distinct intended usages that I strongly recommend you adhere to.The A0-A7 registers are there for passing arguments and storing return values, so if I wrote a function to count the number of even numbers in a list, it might take the address of the list in A0, the length of the list in A1, and return the number of evens it found back in A0.The T0-T7 registers are there for storing temporary data, so you might store an intermediate result of some sum computation in T2 for example. By convention T0-T7 are not preserved across function calls. This means if your function calls another function, the function you called may overwrite these registers without care if it so wishes. (See Section: Calling convention)The S0-S7 are the opposite of the temporaries (saved registers). If you call a function, then by convention if that function uses any of these for its own purposes, it must save the original value somewhere and restore it upon returning.Catatonic also has 3 "Special" registers.The simplest of these is ZZ, reading from ZZ will always result in a zero, and writing to it will simply discard the result.The IP (instruction pointer) register stores the address of the instruction currently executing. It is not intended to be directly read or written to, but you can do this if you're very brave.After that we have the RA register; by convention RA is used to save the instruction pointer during a call, so the called function knows where to go back to when it returns its result. Arithmetic InstructionsThe majority of the ISA is made up of arithmetic instructions that take 1-2 source operands and a destination operand. (We've also been calling operands "arguments".) For example```python    (ADD, DEST, SOURCEA, SOURCEB),```would add SOURCEA and SOURCEB and store them into the destination operand.Source operands may be either registers or literal numbers, so both of the following are valid:```python    (ADD, T0, A0, S0),    (SUB, T1, A1, 3),```Arithmetic instructions are generally executed the way you would read them, so the first instruction there would perform T0 = A0 + S0, and the second would perform T1 = A1 - 3, as is generally the convention for most assembly languages. For a full listing of these, see the cell at the top. ADD through SLT are all of the arithmetic instructions that follow this form. Misilaneous InstructionsCatatonic has two instructions that don't really fit into any other category;The HLT (halt) instruction ends the execution of your program and causes the simulator to exit. We use this to end the program when our test is complete:```python    (ADD, T0, 1, 3),  Runs    (HLT),    (MUL, T0, 2, 3),  Doesn't Run```The other instruction that doesn't really fit is the OUT instruction. This prints out its argument to the console (additionally the `run_program` function provides a list of all outputs upon exiting). This is intended to be used for debugging, and to export the results of your function to the user/a test.```python    (OUT, 5),   Would print "5" to the console    (OUT, T0),  Would print the contents of T0 to the console```  **Question 1**Now that you know what registers and arithmetic instructions do, fill in the functions below so that they match their descriptions.<jupyter_code>source = {
    'f_main' : [
        (MOV, A0, 1),
        (MOV, A1, 2),
        (CALL, 'f_add'),
        (OUT, A0),
        (CALL, 'f_mul'),
        (OUT, A0),
        (MOV, A0, 7),
        (MOV, A1, 3),
        (CALL, 'f_bypowerof2'),
        (OUT, A0),
        (HLT)
    ],
    'f_add' : [
        (PSH, RA),
        # Fill in your code here to add A0 and A1
        # and store the result back in A0:
        
        (POP, RA),
        (RET)
    ],
    'f_mul' : [
        (PSH, RA),
        # Fill in your code here to multiply A0 and A1
        # and store the result back in A0:
        
        (POP, RA),
        (RET)
    ],
    'f_bypowerof2' : [
        (PSH, RA),
        # (BONUS)
        # Fill in your code here to take A0 and multiply
        # it by (2^A1) and store the result back in A0:
        
        (POP, RA),
        (RET)
    ]
}

m = MachineState(Memory(256), output_print = False)
result = m.run_program(assemble(source))

expected = [3, 6, 56]
test(result, expected)<jupyter_output><empty_output><jupyter_text>Branching InstructionsOf course as we discussed in lecture 2, arithmetic instructions don't make a turing complete language on their own. We also need flow control instructions. Because assembly mostly consists of contiguous flat blocks of instructions, we don't have instructions like if/else/while/for. Instead we have branching instructions that tell the processor to jump backwards or forwards a given number of instructions when a condition is met, as opposed to simply continuing on to the next instruction. They have the following format:```python    (BGE/BLT/BNE/BEQ, TARGET, SOURCE1, SOURCE2),```The four branch instructions are Branch Greater than or Equal To (BGE), Branch Less Than (BLT), Branch Not Equal (BNE), and Branch Equal (BEQ); so for example```python    (BLT, 2, T0, T1)```Would jump forward 2 instructions if `T0 < T1`.You can use these to implement loops, for example the code below would count T0 from 0 to 10;```python    (MOV, T0, ZZ),  Set T0 to 0    (ADD, T0, T0, 1),  Increment T0 by 1 (branch jumps back here)    (BLT, -1, T0, 10),```Using these instructions and a little bit of thonking you can construct any if, else, while or for structure you should need.(Note, Remember the zero register ZZ, if you need an unconditional branch to a target you can do `(BEQ, TARGET, ZZ, ZZ)`)  **Question 2**Now that you're familiar with branching instructions, fill out the following functions where you perform a simple if/else branch, and a simple loop:<jupyter_code>source = {
    'f_main' : [
        (MOV, A0, 4),
        (CALL, 'f_evenorodd'),
        (OUT, A0),
        
        (MOV, A0, 1293),
        (CALL, 'f_evenorodd'),
        (OUT, A0),
        
        (MOV, A0, 76),
        (CALL, 'f_evenorodd'),
        (OUT, A0),
        
        (MOV, A0, 4),
        (MOV, A1, 8),
        (CALL, 'f_mulwithoutmul'),
        (OUT, A0),
        
        (MOV, A0, 3),
        (MOV, A1, 4),
        (CALL, 'f_mulwithoutmul'),
        (OUT, A0),
        (HLT)
    ],
    'f_evenorodd' : [
        (PSH, RA),
        # Fill in your code here to add check if A0
        # is even or odd. If it is even return 222 in
        # A0, and if it is odd return 111 in A0
        #
        # The following instructions may be useful:
        # REM
        # MOV
        # BEQ
        
        (POP, RA),
        (RET)
    ],
    'f_mulwithoutmul' : [
        (PSH, RA),
        # Fill in your code here to multiply A0 and A1
        # and store the result back in A0, but do not
        # use MUL, instead write a loop and use ADD
        
        (POP, RA),
        (RET)
    ]
}

m = MachineState(Memory(256), output_print = False)
result = m.run_program(assemble(source))

expected = [222, 111, 222, 32, 12]
test(result, expected)<jupyter_output><empty_output><jupyter_text>Memory/Stack InstructionsCatatonic has two types of storage beyond registers, the stack and main memory. MemoryMain memory is basically one big list/array that can be accessed by the indexes (generally called pointers) of the data inside that you would like to access. These pointers generally need to be stored in registers (you can store them in memory, but then you need pointers to those pointers). In order to copy data between the registers and main memory Catatonic provides two instructions, load (LD) and store (ST).Load takes a value from some location in memory and copies that into the register of your choosing, so for example```python    (LD, T0, A0),```would take the data at the address given by A0 and copy it into T0.For your convenience, load also supports indexed loads, with a base address and an offset, so for example if A0 stored the address of an array, and you wanted to access element 7, you would do```python    (LD, T0, A0, 7)```which would grab the value at `A0 + 7` (fun fact, this is why most languages index arrays and lists starting from zero, because the first element is at BASE + 0).Store works essentially the same way, but in reverse, so:```python    (ST, T0, A0, 4)```Would copy the contents of T0 into the memory location `A0 + 4`Main memory is generally very slow, so most processors have a small amount of RAM directly on their silicon dies that only take a couple of clock cycles to read from. For example, [my computer](https://www.anandtech.com/show/15708/amds-mobile-revival-redefining-the-notebook-business-with-the-ryzen-9-4900hs-a-review/2Caching) can read from cache in 4 clock cycles, 4 times the time it takes to access a register). Stack[Stacks](https://en.wikipedia.org/wiki/Stack_(abstract_data_type)) are very common data structures in computer science and are incredibly simple. The generally have two operations, push which adds a value to the end of the stack, and pop, which removes a value from the end (these were originally called Bury and Unbury by <NAME>). You can think of push like the append function, and pop as reading the last value in a list and then removing it.Most computers store their stack as a data structure in memory, but in order to simplify things we have a completely seperate stack data structure. It can be accessed with the two instructions PSH and POP:```python    (PSH, A0),  Would push the value in A0 onto the bottom of the stack    (POP, T0),  Takes the value pushed by the previous instruction and stores it in T0```Stacks are a great way to store data that you don't have room for in registers because they are relatively fast (generally your stack will always be in cache), and you don't need to keep around a pointer to access data because it is always on a predictable place on the stack. The price you pay for this is that stacks can't easily handle data that lack a fixed length, like lists. Instead, these are typically stored in main memory with a pointer to them kept on the stack or in a register. (If you hear someone talking about storing stuff on the 'heap' this is what they mean).The Stack is a perfect place to save registers in called functions. For example, if your function used the register S2 you would need to save and restore it upon entry and exit, in case the function calling you used it. You could express that quite simply by doing:```python    (PSH, S2),  Save the original value of S2    ...Your Computation Here...    (POP, S2),  Restore your saved value to S2```  **Question 3**A lot of scientific computation happens on arrays. In this problem we have preloaded the memory of the computer with two simple arrays, with a pointer to one in `A0` and a pointer to the other in `A1`; They both have the same length which is being passed in A2. Fill out the `f_add_arrays` function so that it adds the two arrays element by element, storing the result back into the array at `A0` and overwritting it.**BONUS:** If anyone can explain how my function (which prints out the first array after calling your function) works, my dog will join us in the next lecture.<jupyter_code># Create a new machine containing our arrays with a cachesize of 16 elements
m = MachineState(Memory([
    1, 2, 3, 4, 5, 6, 7, 8,
    1, 2, 3, 4, 5, 6, 7, 8
]), output_print = False, cachesize = 16)

source = {
    'f_main' : [
        (MOV, A0, 0), # Store the index of the first array in A0
        (MOV, A1, 8), # Store the index of our second array in A1
        (MOV, A2, 8), # Store their length in A2
        (CALL, 'f_add_arrays'),

        # BONUS PUZZLE
        # If anyone can explain what this does, and how, I will try to get my dog
        # to join the next lecture over zoom
        (XOR, T0, T0, T0),
        (CALL, 6),
        (LD, T1, T0),
        (OUT, T1),
        (NOT, T0, T0),
        (MUL, T0, T0, -1),
        (BGE, 2, T0, 8),
        (RET),

        (HLT),
    ],
    'f_add_arrays' : [
        (PSH, RA),
        # A pointer to one array will be passed in A0, and a pointer to another
        # will be passed in A1, the length of both of them will be passeed in
        # A2. Add each element of both arrays together, and store the result
        # back to the array pointed to by A0, overwriting its original content.
        #
        # Indexed loads might be useful here
        #
        # Fill in your code to complete this operation here:

        (POP, RA),
        (RET)
    ]
}

print("Initial contents of memory: ", m.memory.mem)

print("")
print("Running our program once:")
result = m.run_program(assemble(source))
expected = [2, 4, 6, 8, 10, 12, 14, 16]
test(result, expected)
print("Contents after one run: ", m.memory.mem)
print("")
print("Running our program a second time: ")
# Reset the instruction pointer to the top of main, and run again to show the speedup due to the arrays being cached by the first run
m.reset()
result = m.run_program(assemble(source))
expected = [3, 6, 9, 12, 15, 18, 21, 24]
test(result, expected)<jupyter_output><empty_output><jupyter_text>**Question 4**a. If your code worked properly, you should notice that the second run through the program took drastically fewer cycles. Explain why! (note the `cachesize` parameter on the machine instantiation):*Answer*b. Now change the machine's `cachesize` to 15. Most of your speedup is probably gone, which might be surprising. Explain why!*Answer*(Note these kind of steep dropoffs are actually reflective of how real caching systems behave, for example the [latest Qualcomm phone chip](https://images.anandtech.com/doci/16463/lat-888-X1.png)).  Calling ConventionThe calling convention of a system defines how different functions are supposed to interact with each other. This is a very basic example of an abstraction barrier that lets multiple components work together seamlessly without beating each other over the head.Catatonic functions should fulfil the following guarentees:- If a function uses an S0-S7 register or the RA register, it should save its state before it uses it, and restore its state before it returns- If a function uses a T0-T7 register, it should not assume that the value in that register will be preserved after it calls another function- Functions should pass arguments and return values through A0-A7 (And they should treat these values as temporaries when calling other functions- When calling another function, a function should store the address of the instruction after the call in RA- In order to return, a function should jump to the address stored in RAThose last two are probably a little confusing, so we provide two "pseudo-instructions" to help you manage them that assemble to the Jump-and-Link (JAL) instruction: CALL and RET.JAL jumps to the instruction at the address of its second argument, storing the position of the instruction directly following it in its first argument:```python    (JAL, RA, 75),  Jumps to instruction 75    (MOV, T0, ZZ),  <-- RA now contains the address of this instruction```To make your life easier `(CALL, func)` is shorthand for `(JAL, RA, FUNC)` which lets you satisfy that second to last bulletpoint more easily.We also provide `(RET)` which is shorthand for `(JAL, ZZ, RA)` which lets you achieve that last bullet point eaisly.You may notice that in every skeleton we gave you there was a `(PSH RA)` at the begining and a `(POP RA)` just before the return. This is because we need to treat RA like a saved register, and if your function calls another function you should push the value of RA to the stack before calling another function, and pop it back off before returning so that you remember the call. In order to avoid any messy bugs in your program, I recommend wrapping every function you write with a `(PSH RA)` at the beginning, and a `(POP RA)` right before the return:```python    (PSH, RA),    ... Do stuff ...    (CALL, 'f_scary_func'),    ... Do more stuff ...    (POP, RA),    (RET)```  **Question 5**Now that you understand the safety barriers that let functions call one another without clobbering eachother over the head, modify your `f_add_arrays` function to `f_combine_arrays` and place it below to take the address of one array in `A0`, the address of another in `A1`, their length in `A2`, and the address of another function in `A0`. Instead of adding the elements in the lists at `A0` and `A1`, call the function passed in `A3` (call can take an address in a register too, not just a function name) on every set of elements and take the result and place it in the first array.The function passed in `A3` will take its arguments from `A0` and `A1` and return the result in `A0`.Things to remember:- The called function may clobber temporaries, so keep everything you need to be preserved across calls in a saved register, or on the stack- If you use a saved register, you have to save the old value of that register to the stack, and restore it before you return!- Treat argument registers as temporaries!!! When you call the combiner function you need to place its argument in `A0` and `A1`, so you need to copy the addresses of the arrays to a saved register- The same thing goes for `A2` and `A3`, as the called function may call another function that takes an argument in that register, so save that too!You will want to copy your answers from problem one into the appropriate slots<jupyter_code># Create a new machine containing our arrays with a cachesize of 16 elements
m = MachineState(Memory([
    1, 2, 3, 4, 5, 6, 7, 8,
    1, 2, 3, 4, 5, 6, 7, 8
]), output_print = True, cachesize = 16)

source = {
    'f_main' : [
        (MOV, A3, 'f_add'),
        (MOV, A4, 3),
        (CALL, 'f_test'), # TEST 1

        (MOV, A3, 'f_mul'),
        (MOV, A4, 4),
        (CALL, 'f_test'), # TEST 2

        (MOV, A3, 'f_add_clobber'),
        (MOV, A4, 7),
        (CALL, 'f_test'), # TEST 3

        (HLT),
    ],
    'f_test' : [
        (PSH, RA),
        (MOV, A0, 0),
        (MOV, A1, 8),
        (MOV, A2, 8),
        (MOV, S7, A4),
        (CALL, 'f_combine_arrays'),
        (LD, T0, S7),
        (OUT, T0),
        (POP, RA),
        (RET)
    ],
    'f_combine_arrays' : [
        (PSH, RA),
        # A pointer to one array will be passed in A0, and a pointer to another
        # will be passed in A1, the length of both of them will be passeed in
        # A2. A combiner function will be passed in A3, and will take one number
        # in A0 and one number in A1, returning its result in A0. Call this on
        # each pair of elements and replace the first array with the result
        #
        # Indexed loads might be useful here
        # You can call a function address stored in a register like (CALL, A)3
        #
        # Fill in your code to complete this operation here:

        (POP, RA),
        (RET)
    ],
    'f_add' : [
        (PSH, RA),
        # COPY ME FROM QUESTION 1

        (POP, RA),
        (RET)
    ],
    'f_mul' : [
        (PSH, RA),
        # COPY ME FROM QUESTION 1

        (POP, RA),
        (RET)
    ],
    'f_add_clobber' : [
        (MOV, T0, 0),
        (MOV, T1, 0),
        (MOV, T2, 0),
        (MOV, T3, 0),
        (MOV, T4, 0),
        (MOV, T5, 0),
        (MOV, T6, 0),
        (MOV, T7, 0),
        (MOV, A2, 0),
        (JAL, ZZ, 'f_add') # I picked this wacky trick up from gcc
    ]
}

expected = [8, 50, 136]
result = m.run_program(assemble(source))
test(result, expected)<jupyter_output><empty_output>
{'fraction_non_alphanumeric': 0.09215790234732732, 'fraction_numerical': 0.01496601918349641, 'mean_word_length': 2.382101230744152, 'pattern_counts': {'":': 9, '<': 53, '<?xml version=': 0, '>': 55, 'https://': 9, 'lorem ipsum': 0, 'www.': 2, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 1, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '8', 'dir': 'jupyter-structured-clean-dedup', 'id': '441010', 'license': 'CC-BY-4.0', 'n_tokens_mistral': 12334, 'n_tokens_neox': 11629, 'n_words': 5275, 'path': 'static/homeworks/physcat_sp21_hw2.ipynb', 'repo_name': 'physcatdecal/physcatdecal.github.io', 'size': '41511'}