teaching machines

CS 352 Lecture 21 – Assembler Cont’d

October 26, 2016 by . Filed under cs352, fall 2016, lectures.

Dear students,

Today we continue work on our assembler. In short, this is our development checklist:

  1. strip out the cruft (unnecessary whitespace, comments)
  2. identify addresses for all code labels
  3. resolve all symbols to addresses
  4. convert text instructions to binary

We accomplished steps 1 and 2 last time, but didn’t test it. Let’s write a quick infinite loop to see if it worked.

Resolving all symbols will look a bit like this:

for each instruction
  if instruction is @
    if symbol table does not have identifier
      "declare" a new symbol and resolve a slot in RAM 
    look up identifier in symbol table
    replace it with address

Once all addresses have been resolved, we have only a mathematical facade over the machine code. We can convert each instruction to its machine code cousin directly via this algorithm:

for each instruction
  if instruction is @
    '@' + 15-bit address
  else
    figure out assignment destination bits
    figure out computation bits
    figure out jump bits

    '111' + computation bits + assignment destination bits + jump bits

If we have any extra time today, I can’t think of a better way to spend it than collectively playing Human Resource Machine.

Here’s your TODO list:

See you next class!

Sincerely,

P.S. Here’s the code we wrote together…

assembler.rb

#!/usr/bin/env ruby

symbols = {
  'R0' => 0,
  'R1' => 1,
  'R2' => 2,
  'R3' => 3,
  'R4' => 4,
  'R5' => 5,
  'R6' => 6,
  'R7' => 7,
  'R8' => 8,
  'R9' => 9,
  'R10' => 10,
  'R11' => 11,
  'R12' => 12,
  'R13' => 13,
  'R14' => 14,
  'R15' => 15,
  'KBD' => 24576,
  'SCREEN' => 16384,
  'SP' => 0,
  'LCL' => 1,
  'ARG' => 2,
  'THIS' => 3,
  'THAT' => 4,
}

src = File.read(ARGV[0])

# Strip out cruft.
src.gsub!(/\/\/.*/, '')
src.gsub!(/\n{2,}/, '')
src.gsub!(/^ +/, '')
src.gsub!(/ +$/, '')

# Determine addresses for labels.
instructions = []
src.lines.each do |line|
  if line =~ /\(([A-Za-z].*)\)/
    label = $1
    symbols[label] = instructions.size
  else
    instructions << line
  end
end

next_available = 16

# Resolve symbols
instructions.map! do |instruction|
  if instruction =~ /^@([A-Za-z].*)/
    id = $1
    if !symbols.has_key?(id)

      symbols[id] = next_available
      next_available += 1
    end

    "@#{symbols[id]}"
    # '0' + '%015b' % symbols[id]
  else
    instruction
  end
end

destinations = {
    nil => '000',
    'M' => '001',
    'D' => '010',
   'MD' => '011',
    'A' => '100',
   'AM' => '101',
   'AD' => '110',
  'AMD' => '111',
}

jumps = {
    nil => '000',
  'JGT' => '001',
  'JEQ' => '010',
  'JGE' => '011',
  'JLT' => '100',
  'JNE' => '101',
  'JLE' => '110',
  'JMP' => '111',
}

expressions = {
   '0' => '0101010',
   '1' => '0111111',
  '-1' => '0111010',
   'D' => '0001100',
   'A' => '0110000',
  '!D' => '0001101',
  '!A' => '0110001',
  '-D' => '0001111',
  '-A' => '0110011',
 'D+1' => '0011111',
 'A+1' => '0110111',
 'D-1' => '0001110',
 'A-1' => '0110010',
 'D+A' => '0000010',
 'D-A' => '0010011',
 'A-D' => '0000111',
 'D&A' => '0000000',
 'D|A' => '0010101',
   'M' => '1110000',
  '!M' => '1110001',
  '-M' => '1110011',
 'M+1' => '1110111',
 'M-1' => '1110010',
 'D+M' => '1000010',
 'D-M' => '1010011',
 'M-D' => '1000111',
 'D&M' => '1000000',
 'D|M' => '1010101'
}

# puts instructions

instructions.map! do |instruction|
  if instruction =~ /^@(\d+)/
    address = $1
    '0' + '%015b' % address
  else
    instruction =~ /^(?:([AMD]{1,3})=)?(.*?)(?:;(J.*))?$/
    computation_bits = expressions[$2]
    destination_bits = destinations[$1]
    jump_bits = jumps[$3]

    "111#{computation_bits}#{destination_bits}#{jump_bits}"
  end
end

puts instructions