Writing a Disassembler in Elixir

November 10, 2018

Writing a Disassembler in Elixir

Before we can emulate the processor, we have to understand how to read the firmware. In order to do that we’re going to write a “disassembler”. A disassembler is a program that takes the raw binary instructions and translates it into human-readable assembly language.

From the docs (note, I removed the hardware specifics as they’re irrelevant for emulation):

After a hardware reset, cog 0 loads and executes a booter program from an internal ROM.  The booter program (ROM_Booter.spin2) performs the following steps:

Load the first 1024 bytes (256 longs) from SPI into the hub starting at $00000.
Compute the 32-bit sum of the 256 longs.
  If the sum is "Prop" ($706F7250):
    Copy the first 256 longs from hub into cog registers $000..$0FF.
    Execute JMP #$000 to run the SPI program.

This tells us that the ROM only loads the first 1024 bytes and executes. In other words, if the programmer wants any of the data above the 1024th byte copied to the P2, they have to write the routine to do that manually.

Our image could be 1 Meg in size… but we still only read the first 1024 if we’re emulating.

Examining the P2 Assembly

As I mentioned in the previous post, every P2 Assembly Instruction is exactly 32 bits wide. To add awesome to fscking awesome, they’re almost completely consistent in how they’re assembled and disassembled:

From the documentation:


3322 2222222 211 111111110 000000000  <<-- Individual bits, numbered 31-0
1098 7654321 098 765432109 876543210 

Cond OpCode  Flg Dest      Source     Instr   Params  Tests
=================================================================
EEEE 0000000 CZI DDDDDDDDD SSSSSSSSS  ROR     D,S/#   {WC/WZ/WCZ}
EEEE 0000001 CZI DDDDDDDDD SSSSSSSSS  ROL     D,S/#   {WC/WZ/WCZ}
EEEE 0000010 CZI DDDDDDDDD SSSSSSSSS  SHR     D,S/#   {WC/WZ/WCZ}
EEEE 0000011 CZI DDDDDDDDD SSSSSSSSS  SHL     D,S/#   {WC/WZ/WCZ}
EEEE 0000100 CZI DDDDDDDDD SSSSSSSSS  RCR     D,S/#   {WC/WZ/WCZ}
EEEE 0000101 CZI DDDDDDDDD SSSSSSSSS  RCL     D,S/#   {WC/WZ/WCZ}
EEEE 0000110 CZI DDDDDDDDD SSSSSSSSS  SAR     D,S/#   {WC/WZ/WCZ}
EEEE 0000111 CZI DDDDDDDDD SSSSSSSSS  SAL     D,S/#   {WC/WZ/WCZ}

EEEE 0001000 CZI DDDDDDDDD SSSSSSSSS  ADD     D,S/#   {WC/WZ/WCZ}
EEEE 0001001 CZI DDDDDDDDD SSSSSSSSS  ADDX    D,S/#   {WC/WZ/WCZ}
EEEE 0001010 CZI DDDDDDDDD SSSSSSSSS  ADDS    D,S/#   {WC/WZ/WCZ}
EEEE 0001011 CZI DDDDDDDDD SSSSSSSSS  ADDSX   D,S/#   {WC/WZ/WCZ}

EEEE 0001100 CZI DDDDDDDDD SSSSSSSSS  SUB     D,S/#   {WC/WZ/WCZ}
EEEE 0001101 CZI DDDDDDDDD SSSSSSSSS  SUBX    D,S/#   {WC/WZ/WCZ}
EEEE 0001110 CZI DDDDDDDDD SSSSSSSSS  SUBS    D,S/#   {WC/WZ/WCZ}
EEEE 0001111 CZI DDDDDDDDD SSSSSSSSS  SUBSX   D,S/#   {WC/WZ/WCZ}
... (and so on) ...

You probably don’t need to know much about assembly to see a consistent pattern here.

  1. Don’t get stressed about fully understanding the above table. Just take in the ‘big picture’.
  2. Every instruction is 32bits long. The least significant bit is bit 0.
  3. Instructions seem to have a common format, 4bits, 7bits, 3 bits, 9 bits, 9 bits.
  4. At least in the instructions above, those represent “Conditionals”, “Opcode”, “Modifiers”, “Destination”, “Source”, “Tests”
  5. Elixir has binary pattern matching which means that so long as this remains consistent, dispatch / disassembly should be as simple as a single function with many clauses (spoiler: it won’t be).

Let’s talk about flags.

If you’re familiar with writing code in other assembly languages, like Z80 for example - there’s the concept of “flags”. Z80 and P2 assembly have two of those flags in common, the “C” flag, and the “Z” flag.

The Z flag, or the “Zero Flag” was set automatically any time an executed instruction resulted in the value 0. The C flag, or “Carry Flag” was set any time you performed some operation which “overflowed” the result such that it wouldn’t fit in the 8 or 16 bit location you operated on.

From what I remember about Z80 assembly (it has been 35 years) I would typically test for some value and the result of that boolean (yes/no | true/false | 10) test would be set in the ‘Z’, or “Zero Flag”. Unfortunately, Z80 had limited instructions for responding to conditionals (like jpz (jump if Z flag is set), and jpnz (jump if Z flag is NOT set) a lot of my code consisted of tiny 2-3 instruction subroutines that I would call and return from. It was very ineffecient.

P2 assembly in contrast allows every opcode (except NOP) to be conditional by reserving the first four bits (31:28) to that purpose. Four bits seems like a lot to encode for two flags (you’d think you’d only need two). If the check is successful, then whatever the instruction is, executes. If the check isn’t successful, the command is executed as a NOP (no Operation).

Here are the tests from the documentation (full disclosure, I don’t know what half of these mean yet):

_CLR                    =       %0000
_NC_AND_NZ              =       %0001
_NZ_AND_NC              =       %0001
_GT                     =       %0001
_NC_AND_Z               =       %0010
_Z_AND_NC               =       %0010
_NC                     =       %0011
_GE                     =       %0011
_C_AND_NZ               =       %0100
_NZ_AND_C               =       %0100
_NZ                     =       %0101
_NE                     =       %0101
_C_NE_Z                 =       %0110
_Z_NE_C                 =       %0110
_NC_OR_NZ               =       %0111
_NZ_OR_NC               =       %0111
_C_AND_Z                =       %1000
_Z_AND_C                =       %1000
_C_EQ_Z                 =       %1001
_Z_EQ_C                 =       %1001
_Z                      =       %1010
_E                      =       %1010
_NC_OR_Z                =       %1011
_Z_OR_NC                =       %1011
_C                      =       %1100
_LT                     =       %1100
_C_OR_NZ                =       %1101
_NZ_OR_C                =       %1101
_C_OR_Z                 =       %1110
_Z_OR_C                 =       %1110
_LE                     =       %1110
_SET                    =       %1111

Starting our Disassembler

So, let’s end today’s brief adventure writing a function to disassemble. I’ll start assuming zero elixir knowledge so if you’re fluent, feel free to skip some.

Creating the project

[red@evil:~/projects]$ mix new p2_dasm
* creating README.md
* creating .formatter.exs
* creating .gitignore
* creating mix.exs
* creating config
* creating config/config.exs
* creating lib
* creating lib/p2_dasm.ex
* creating test
* creating test/test_helper.exs
* creating test/p2_dasm_test.exs

Your Mix project was created successfully.
You can use "mix" to compile it, test it, and more:

    cd p2_dasm
    mix test

Run "mix help" for more commands.

[red@evil:~/projects]$ cd p2_dasm
[red@evil:~/projects/p2_dasm]$ mkdir lib/p2_dasm
[red@evil:~/projects/p2_dasm]$ vi lib/p2_dasm/conditionals.ex

Rememeber that Elixir is a functional language which means that we write code telling our computer what to do per se, we tell it things that are true.

Elixir Organizes code in Modules. Our first module will be called: P2Dasm.Conditionals so lives in the file lib/p2_dasm/conditionals.ex

Here’s what our empty module looks like:

defmodule P2Dasm.Conditionals do
  ## Our code / functions go here
end

Pay attention to the “do” and the “end”. Those are your braces in this syntax.

An implementation of this in an imperative language might look something like this:

sub decode {
  my $binary = shift;

  if    ($binary eq "0000") { return "_CLR"; }
  elsif ($binary eq "0001") { return "_NC_AND_NZ"; }
  elsif ($binary eq "0001") { return "_NZ_AND_NC"; }
  elsif ($binary eq "0001") { return "_GT"; }
  elsif ($binary eq "0010") { return "_NC_AND_Z"; }
  elsif ($binary eq "0010") { return "_Z_AND_NC"; }
  elsif ($binary eq "0011") { return "_NC"; }
  elsif ($binary eq "0011") { return "_GE"; }
  else { return undef };
};

In Elixir, we don’t use if statements. We define a ‘version’ of the function for every outcome like so:

defmodule P2Dasm.Conditionals do
  def decode(<<0b0000>>), do: "_CLR"
  def decode(<<0b0001>>), do: "_NC_AND_NZ"
  def decode(<<0b0001>>), do: "_NZ_AND_NC"
  def decode(<<0b0001>>), do: "_GT"
  def decode(<<0b0010>>), do: "_NC_AND_Z"
  def decode(<<0b0010>>), do: "_Z_AND_NC"
  def decode(<<0b0011>>), do: "_NC"
  def decode(<<0b0011>>), do: "_GE"
  def decode(_anything), do: false
end

Let’s compile it and enter the shell!

[red@evil:~/projects/p2_dasm]$ iex -S mix
Erlang/OTP 20 [erts-9.3.3.3] [source] [64-bit] [smp:2:2] [ds:2:2:10] [async-threads:10] [hipe] [kernel-poll:false]

Compiling 1 file (.ex)
warning: this clause cannot match because a previous clause at line 3 always matches
  lib/p2_dasm/conditionals.ex:4

warning: this clause cannot match because a previous clause at line 6 always matches
  lib/p2_dasm/conditionals.ex:7

warning: this clause cannot match because a previous clause at line 8 always matches
  lib/p2_dasm/conditionals.ex:9

Interactive Elixir (1.7.4) - press Ctrl+C to exit (type h() ENTER for help)
iex(1)> 

Huh, Elixir gave us some warnings - what’s that all about? Let’s look at the code at lines 4,7,9:

defmodule P2Dasm.Conditionals do
  def decode(<<0b0000>>), do: "_CLR"
  def decode(<<0b0001>>), do: "_NC_AND_NZ"           
  def decode(<<0b0001>>), do: "_NZ_AND_NC" # Line 4 
  def decode(<<0b0001>>), do: "_GT"        
  def decode(<<0b0010>>), do: "_NC_AND_Z"  
  def decode(<<0b0010>>), do: "_Z_AND_NC"  # Line 7
  def decode(<<0b0011>>), do: "_NC"        
  def decode(<<0b0011>>), do: "_GE"        # Line 9
  def decode(_anything), do: false         
end

Of course, now we can see it. There are multiple definitions as to what each of these values can represent. As we specified earlier, Elixir will go down each function definition in order until it finds a match. As such, the _NZ_AND_NC, _GT, _Z_AND_NC, _GE lines will never execute.

Functional language compilers excel in finding bugs like these.

So, remove the redundant lines and load an Elixir shell so we can test it:

[red@evil:~/projects/p2_dasm]$ iex -S mix
Erlang/OTP 20 [erts-9.3.3.3] [source] [64-bit] [smp:2:2] [ds:2:2:10] [async-threads:10] [hipe] [kernel-poll:false]

Compiling 1 file (.ex)
Interactive Elixir (1.7.4) - press Ctrl+C to exit (type h() ENTER for help)
iex(1)> P2Dasm.Conditionals.decode(<<0b0000>>)
"_CLR"
iex(2)> P2Dasm.Conditionals.decode(<<0b0001>>)
"_NC_AND_NZ"
iex(3)> P2Dasm.Conditionals.decode(<<0b0010>>)
"_NC_AND_Z"
iex(4)> P2Dasm.Conditionals.decode(<<0b0011>>)
"_NC"
iex(5)>

Success! (Now go implement the rest of the conditionals - I’ll wait)

Syntax Notes

  1. The ‘def’ functions didn’t have a matching end. Not because def is different than defmodule but because we used , do: … instead of do … end (note the lack of comma and colon)
  2. The <<>> syntax means we’re matching on bits. The 0b prefix means what follows is binary. It defaults to 8 bits which means it’s working “by accident”. When it comes to integrating it with the actual disassembler we’ll specify that it’s specifically for 4 bits. (If you’re curious, the syntax is this: <<0b0001::size(4)>>)
  3. The value _anything is special because the _ means “throw this away, I don’t care”. It’s very common to just see “_” used by itself, but I like giving it a name so I can look at my code and see what I was throwing away at a glance.