Sweet16 CPU Emulator

by SysOps
This entry is part 5 of 8 in the series Sweet16-GP CPU: A Complete Development Cycle

Part 5

Last time we implemented all the register type instructions. I hope you played around with the emulator and got a feel for how the housekeeping methods were used to implement each instruction. Today we’re going to add support for non-register instructions. Since most of these instructions are branch instructions they will all be very similar.

If you look back at the first post, you’ll notice most of the branch instructions require an offset value. This value can range from -128 to +127. You may be wondering how we get negative numbers when we only have bytes that range from 0 – 255 and words that range from 0 – 65535. The answer is two’s complement. If you don’t know what two’s complement representation is, may I suggest you watch a few youtube videos on the subject. One of my favorites is the compuphile video found here:

So now you know that we can take our 255 numbers and split them in two parts. To do this however we’ll have to do a bit of bit twiddling. Recall from the video that the algorithm for converting a number into two’s complement representation is as follows:

  • Take the one’s complement of the number by inverting every bit.
  • Add 1 to the result

That’s all there is to it. Simple really.

What we’ll need is a method that will take the two’s complement representation and return the abs (absolute value) of that number. The idea here is to test the sign bit and then, depending on its value, add or subtract the offset to/from the current location. So let’s see what this looks like in code:

# Two's Complement
def get_abs_from_signed(self, val) -> int:
    if val > 127:
        val = val - 1
        val = (~val & 0b11111111)
    return val

As you can see, all we do is reverse the two’s complement encoding process by testing if the byte value is greater than 127. If so, it’s a negative value and we must subtract 1 from that value then invert it. Then we mask off the value to ensure an 8-bit value is returned.

Try writing some tests for the get_abs_from_signed() method and verify that when you pass it a negative number like -6 you get back 6. Make sure to represent the value you pass in as an 8-bit value by masking it to 8 bits using & 0xff or & ob11111111. Otherwise you’ll end up getting garbage values back.

Now let’s move on to the decode_non_register_instr() method. This method, like the decode_register_type_instr() method, is just a set of if, elif, else statements to filter the various opcodes and call the proper exec_xxx() method.

def decode_non_register_instr(self, opcode: int):
    if opcode == 0x00:
        self.exec_halt()
    elif opcode == 0x01:
        self.exec_bra()
    elif opcode == 0x02:
        self.exec_brc()
    elif opcode == 0x03:
        self.exec_brz()
    elif opcode == 0x04:
        self.exec_brn()
    elif opcode == 0x05:
        self.exec_brv()
    elif opcode == 0x06:
        self.exec_bsr()
    elif opcode == 0x07:
        self.exec_rts()
    else:
        print(f'Unknown opcode: {opcode}')

We already implemented the HALT instructions, so we can move on to the BRA (Branch Always) instruction, opcode 0x01. This instruction first needs to get the current address from the PC. Then increment the PC to point to the offset byte that immediately follows the opcode. Once we have the offset byte we can check if it’s a forward or reverse jump by testing its sign. If negative, we are jumping back and if positive, we are jumping forward. Once we know the sign, we can obtain the absolute value of the offset and either add or subtract it from the saved instruction address. It sounds much more complex than it is. Here’s the code for the exec_bra() method:

def exec_bra(self):
    ea = self.get_register(self.PC)
    self.inc_register(self.PC)
    displacement = self.peek_byte(self.get_register(self.PC))
    offset = self.get_abs_from_signed(displacement)
    if displacement > 127:
        ea -= (offset+1)
    else:
        ea += (offset)
    self.set_register(self.PC, ea)

Read the code and make sure you know what it’s doing before moving on.

The rest of the branch instructions are all conditional branches. They all require the same process as the BRA instruction with the exception that they must test the condition bits in the STATUS register and determine, based on the state of those bits, whether to take the branch or not. Because these instructions will all require the same steps (and the same code) and we follow the “DRY” principle, we’ll create a single method to do the heavy lifting. Then we’ll have our exec_bxx() methods call the common routine passing it the status flag (condition bit) to check in the STATUS register.

def exec_conditional_branch(self, flag: str):
    if self.test_flag(flag):
        displacement = self.peek_byte(self.get_register(self.PC))
        offset = self.get_abs_from_signed(displacement)
        ea = self.get_register(self.PC)
        if displacement > 127:
            ea -= offset
        else:
            ea += offset+1
        self.set_register(self.PC, ea)
        self.set_value_flags(self.get_register(self.ACC))
        self.clear_flags('C')
    else:
        self.set_value_flags(self.get_register(self.ACC))
        self.clear_flags('C')
        self.inc_register(self.PC)

As you can see, this method expects a flag (C, Z, N, V) as input. Notice we don’t need to send any address information to this method. It can handle getting the current instruction address and the offset to calculate the branch address. The only real difference here from the exec_bra() method is that we are testing a flag to see if we should take the branch.

Now that we have our exec_conditional_branch() method we can call it for all conditional branches passing in the proper flag value for each.

def exec_brc(self):
    self.exec_conditional_branch('C')

def exec_brz(self):
    self.exec_conditional_branch('Z')

def exec_brn(self):
    self.exec_conditional_branch('N')

def exec_brv(self):
    self.exec_conditional_branch('V')

Write some tests and try out these instructions. We only have two more to go and you’ll have working Sweet16 emulator. 

OK, now that you have a handle on the conditional branch instructions, let’s look at a more complex instruction (actually a pair of instructions). The BSR (branch to subroutine) and RTS (return from subroutine) instructions are our last two instructions to implement. These two instructions work together to allow you to call subroutines and then return to the instruction following the branch. They are indeed the most complex instructions in the ISA (instruction set architecture) of the Sweet16-GP. However, all the work is done in the BSR method.

To branch to a subroutine and expect to return requires that we save the return address somewhere. But where? Well, we can store the return address in memory. Recall that register R4 is the RETSTACK. This register acts as a stack pointer to a stack of return addresses. The first thing we need to do is get the current instruction address and use it to calculate the return address by adding the length of the current instruction. Luckily, the length of the BSR instruction doesn’t change so calculating the return address is no harder than calculating the offset for the conditional branches. We will, however, use a helper method to put the return address on the return stack. Let’s see the exec_bsr() code now:

def exec_bsr(self):
    """Branch to Subroutine:
    Entry: PC points to current instruction +1
            (LSB of target address). We want to
            store the PC's value + 2 so the return
            address pushed to the stack points
            to the instruction right after the
            target address. The offset here is
            a word sized (two byte) value.
    Exit: PC + 2 is pushed to the memory location
            whose address resides in RETSTACK.
            Then the PC is set to the target
            address.
    """
    self.inc_register(self.PC)
    lo = self.peek_byte(self.get_register(self.PC))
    self.inc_register(self.PC)
    hi = self.peek_byte(self.get_register(self.PC))
    target_addr = (hi << 8) + lo
    self.push_return_addr(self.get_register(self.PC)+1)
    self.set_register(self.PC, target_addr)

As you can see, it’s mostly comment text to document it’s functionality. The one big difference is the call to push_return_addr() which we will implement next. The push_return_addr() method simply pushes the return address onto the stack pointed to by R4 the RETSTACK pointer. Note that to use this stack you must first set it to a value that will not overwrite your program code. We’ll be discussing this in a later post. For now just set R4 to the first 16 byte boundary after the end of your program code. 

We will also be needing a pop_return_addr() method to take the return address back out of the stack when we call RTS. So what do these methods look like?

# Misc Helpers
def push_return_addr(self, ret_addr):
    # Pushes ret_addr to the memory location
    # whose address resides in RETSTACK
    # Then increments RETSTACK by 2.
    hi = (ret_addr & 0xff00) >> 8
    lo = ret_addr & 0xff
    self.poke_byte(self.get_register(self.RETSTACK), lo)
    self.inc_register(self.RETSTACK)
    self.poke_byte(self.get_register(self.RETSTACK), hi)
    self.inc_register(self.RETSTACK)

def pop_return_addr(self):
    # RETSTACK will be pointing passed top of
    # stack. So first we need to decrement once
    # Now we are pointing to the low byte
    self.dec_register(self.RETSTACK)
    hi = self.peek_byte(self.get_register(self.RETSTACK))
    self.dec_register(self.RETSTACK)
    lo = self.peek_byte(self.get_register(self.RETSTACK))
    ret_addr = ((hi << 8) + lo) & 0xffff
    return ret_addr

As you can see, our most complicated instructions are still very simple. I’m sure you understand this by now. So the only instruction we have left to implement is the RTS instruction. This instruction simply pops the return address off the return stack and places the return address into the PC. I’m sure you could write this yourself. However, for completeness here is the exec_rts() method:

def exec_rts(self):
    # Return from Subroutine:
    # The return address is
    ret_addr = self.pop_return_addr()
    self.set_register(self.PC, ret_addr)

Congratulations! You now have a working Sweet16-GP emulator. You can use the same techniques and even much of the same code to emulate almost any processor. 

We’ve completed the emulator instructions but we still have some work to do. It would be nice if we could write our programs in files and pass them to the emulator rather than having to poke them into ram all the time. So now we need to decide on what format these files should have. We could put all our instructions in the file in binary format but that would take a lot of ones and zeros, even for a small program. I suggest we use hexadecimal. We are already using hex when we hand-code things and the emulator expects hex values for instruction codes. Hex should work well and require little processing. Below is a simple method to add to the emulator that will allow you to pass it a file.

def load_hex(self, filename: str, delim=' '):
    import os.path
    from os import path
    """
    Load a program assembled into a hex file and store in memory.
    File format is: each line contains 18 bytes. First two bytes
    are the beginning address of the data in the current line.
    The following 16 bytes are the memory values. All values are
    in hexadecimal. If the 0x character pair is used, it will be 
    stripped. All values are space delimited.
    The file must end with a new line
    """
    if path.exists(filename):
        with open(filename, 'r') as fh:
            addr = 0
            data = fh.readline()
            while data != '':
                # ignore comment lines
                if data[0] == '#':
                    data = fh.readline()
                    continue
                prog_bytes = data.split(delim)
                byte_count = 0
                addr_lo = 0
                addr_hi = 0
                for byte in prog_bytes:
                    if byte == '\n':
                        continue
                    # handle line address
                    if byte_count == 0 or byte_count == 1:
                        if byte_count == 0:
                            addr_lo = int('0x'+byte, 16)
                        else:
                            addr_hi = int('0x'+byte, 16)
                            addr = (addr_hi << 8) + addr_lo
                    # store byte in memory
                    if byte_count > 1:
                        self.MEM[addr] = int('0x'+byte, 16)
                        addr += 1
                    byte_count += 1
                addr = 0
                data = fh.readline()
    else:
        print(f"Can't open file: {filename}")
if __name__ == '__main__':
    import sys
    if len(sys.argv) != 2:
        print("Usage {} infile.asm outfile.hex".format(sys.argv[0]))
        raise SystemExit(1)

    # Remove comments and blank lines
    lines = strip_lines(open(sys.argv[1]))

    if 1:
        rom = write_hexfile(assemble(lines))
        dump_rom(rom)

This is great but we still need to get the filename and path from somewhere. The command line seems like a great way to pass in the file name. Here is some code to read the filename from the command line.

if __name__ == '__main__':
    import sys
    
    # check for file and exit if it does not exist
    if len(sys.argv) != 2:
        print("Usage {} prog.hex".format(sys.argv[0]))
        raise SystemExit(1)

    # get program file name
    program = sys.argv[1]

    cpu = Sweet16GP()
    # init_ram() must be called before loading a
    # program or it will erase it from memory.
    cpu.init_ram()
    cpu.load_hex(program)
    cpu.run()
    cpu.dump()

As always, we want to test this. Let’s create a file called add.hex in the same directory as our emulator. Our file format is very simple. Every line will contain 18 bytes separated by a space. The first two bytes will be the beginning address for that line and the remaining 16-byte values will be the values to poke into memory at each consecutive address.

Example: Our program counter starts at address 0x00 so the first two bytes (each byte requires two hex characters), will be “00 00”. Then we follow that address with the instruction and data to be placed in 16 consecutive memory locations beginning at address 0x0000 like this:

08 05 00 0A 05 00 52 00 00 00 00 00 00 00 00 00

The loader allows for comments in the file, beginning with the hash (or pound symbol if you’re over 40). So we can write the whole file as:

# Place 5 in ACC (R0) and 5 in R2
# Add R2 to ACC and store result in ACC
# On Exit ACC = 0x0A or 10 dec.
00 00 08 05 00 0A 05 00 52 00 00 00 00 00 00 00 00 00

Now that you have a program, let’s run it. Call your emulator from the command line, passing it the filename of the test file. Like so:

>$ python3 sweet16gp.py add.hex

You should get the following output:

PC: 0x0, cur_instr: 0x8
 PC: 0x3, cur_instr: 0xa
 PC: 0x6, cur_instr: 0x52
 PC: 0x7, cur_instr: 0x0
 Sweet16-GP CPU
 Status Flags: 0b0000
 Registers
 ACC (R00): 0x000a,  R01: 0x0000,  R02: 0x0005,  R03: 0x0000,  
 RETPTR (R04): 0x0000,  COMPARE (R05): 0x0000,  STATUS (R06):0x0000,  PC (R07): 0x0008,  
 Addr   Data                                  MEMORY DUMP
 0x0000:  0x08, 0x05, 0x00, 0x0a, 0x05, 0x00, 0x52, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 
...

For brevity, I’ve only shown the first 16 bytes of ram. The program should actually dump 256 bytes due to the default parameter we set on the init_ram() method. I kind of snuck that one past you when I presented the init_ram() method. Did you notice?

We now have a processor emulator but now we need software to run on it! We could just keep hand assembling the instructions for small programs but that gets tedious and is error-prone. So our next task will be to write a simple assembler. The assembler will help us develop more complex programs.

Now take your emulator and write a few simple programs to add, subtract, multiply and divide numbers. See if you can write some multiply and divide routines without using the multiply and divide instructions. How about writing a GCD (Greatest common divisor) routine. Then try moving a block of memory. For a real test of your skills, try adding negative numbers.

In our next post, we will change gears and begin work on a simple 2-pass assembler for the Sweet16-GP. It will be a barebones assembler but it will allow us to begin writing larger, more complex assembly language programs for the Sweet16-GP.

Until next time, enjoy playing with the emulator!

Series Navigation<< Sweet16 CPU EmulatorSweet16-GP Assembler >>