=begin rdoc
  
== Core Wars Lab

Ruby implementation of the MARS virtual machine used in Core Wars.

The machine implemented here conforms as close as possible to the ICWS'88 standard,
as described by Mark Durham in his Introduction to Redcode (http://corewar.co.uk/guides.htm).  

Currently there is no attempt to translate instructions into a numerical format.  MARS
code is a set of Word objects.  Each Word has an opcode and two operands (A and B), all of 
which are represented as strings.  Integer data is represented by a Word where the opcode
field is DAT.  Other Word objects have executable machine instructions for opcodes.

To test a single program students can make an instance of a class named MiniMARS, passing
it the name of a test program.  The test machine will have a small memory, only big enough
to hold the test machine, and special versions of the step, dump and other methods.

The main machine that runs one, two, or three programs simultaneously is in the module
named MARS.  Methods that assemble, load, and run programs are module methods, e.g.
to assemble a program call MARS.assemble(foo).

=end

# TODO add [] and []= methods to Word, use it to extract/assign bits or ranges of bits
# TODO define ranges for fields, e.g. @@opcode = 0..3; use to get opcode of Word, e.g. instr[@@opcode]
# TODO make sure all code uses [] interface (e.g. no more instr.amode[0] == ?#)
# TODO pack words into binary -- will kill several birds at once -- speed, trim values to 0..4095, ..
# TODO color a cell black when a thread halts after executing an instruction in that cell
# TODO MARS.dump
# TODO pass load address to contest (which passes it on to Warrior.load)?

module RubyLabs
	
module MARSLab

  class MARSRuntimeException < StandardError
  end

  class RedcodeSyntaxError < StandardError
  end

	# An object of the Word class represents a single item from memory, either a machine 
	# instruction or a piece of data.  Attributes are the opcode, the A operand mode, and 
	# the B operand (all strings).  Instruction execution proceeds according to the description 
	# in Durham's spec.

	class	Word
		
		attr_reader :op, :lineno
		attr_accessor :a, :b
				
		def initialize(*args)
			@op, @a, @b, @lineno = args
		end
		
		def inspect
		  sprintf "%s %s %s", @op, @a, @b
		end
		
		alias to_s inspect
		
		# two Words are the same if the strings representing the opcode and
		# both operands are the same
		
		def ==(other)
		  return (op == other.op && a == other.a && b == other.b)
	  end
		
		def clone
		  Word.new(@op.clone, @a.clone, @b.clone, @lineno)
		end
		
    # Convert a field specification into an integer value, stripping off a leading
    # addressing mode character if it's there
    
    def field_value(field)
      return @@modes.include?(field[0]) ? field[1..-1].to_i : field.to_i
    end
		
		# Return the address of an operand; note that for immediate operands the 
		# address is the address of the current instruction.
		
		def dereference(field, pc, mem)
		  case field[0]
		  when ?#
		    return pc.current[:addr]
	    when ?@
        ptrloc = (field_value(field) + pc.current[:addr]) % mem.size
        ptr = mem.fetch(ptrloc)
        return (field_value(ptr.b) + ptrloc) % mem.size
      when ?<
        ptrloc = (field_value(field) + pc.current[:addr]) % mem.size
        ptr = mem.fetch(ptrloc)
        newb = field_value(ptr.b) - 1
        mem.store_field(ptrloc, (newb % mem.size), :b)
        return (newb + ptrloc) % mem.size
      else
		    return (field_value(field) + pc.current[:addr]) % mem.size
		  end
		end
		
		# Execute an instruction.  The first parameter is the program counter used
		# to fetch the instruction, the second is the machine's memory array.  
		
		def execute(pc, mem)
	    self.send(@op, pc, mem)
	    return (@op == "DAT") ? (:halt) : (:continue) 
		end
		
		private
		
		# The DAT instruction is effectively a "halt", but we still need to dereference
		# both its operands to generate the side effects in auto-decrement modes.
		
		def DAT(pc, mem)
      dereference(@a, pc, mem)
      dereference(@b, pc, mem)
		end
		
		# Durham isn't clear on how to handle immediate moves -- does the immediate value
		# go in the A or B field of the destination?  Guess:  B, in case the destination
		# is a DAT.
				
		def MOV(pc, mem)
		  raise MARSRuntimeException, "MOV: immediate B-field not allowed" if @b[0] == ?#
		  src = dereference(@a, pc, mem)
		  val = mem.fetch(src)
      dest = dereference(@b, pc, mem)
      if @a[0] == ?#
        mem.store_field(dest, field_value(val.a), :b)
      else
        mem.store(dest, val)
      end
      pc.log(src)
      pc.log(dest)
		end
		
		# Ambiguity on how to handle immediate A values:  add operand to the A or B
		# field of the destination?  Guess:  B (for same reasons given for MOV)

		def ADD(pc, mem)
		  raise MARSRuntimeException, "ADD: immediate B-field not allowed" if @b[0] == ?#
      src = dereference(@a, pc, mem)
		  left_operand = mem.fetch(src)
      dest = dereference(@b, pc, mem)
      right_operand = mem.fetch(dest)
      if @a[0] == ?#
        mem.store_field(dest, field_value(left_operand.a) + field_value(right_operand.b), :b)
      else
        mem.store_field(dest, field_value(left_operand.a) + field_value(right_operand.a), :a)
        mem.store_field(dest, field_value(left_operand.b) + field_value(right_operand.b), :b)
      end
      pc.log(src)
      pc.log(dest)
		end
		
		# See note for ADD, re immediate A operand.
		
		def SUB(pc, mem)
		  raise MARSRuntimeException, "SUB: immediate B-field not allowed" if @b[0] == ?#
      src = dereference(@a, pc, mem)
		  right_operand = mem.fetch(src)
      dest = dereference(@b, pc, mem)
      left_operand = mem.fetch(dest)
      if @a[0] == ?#
        mem.store_field(dest, field_value(left_operand.b) - field_value(right_operand.a), :b)
      else
        mem.store_field(dest, field_value(left_operand.a) - field_value(right_operand.a), :a)
        mem.store_field(dest, field_value(left_operand.b) - field_value(right_operand.b), :b)
      end
      pc.log(src)
      pc.log(dest)
		end
		
		# Durham doesn't mention this explicitly, but since a B operand is allowed it implies
		# we have to dereference it in case it has a side effect.
				
		def JMP(pc, mem)
		  raise MARSRuntimeException, "JMP: immediate A-field not allowed" if @a[0] == ?#
		  target = dereference(@a, pc, mem) % mem.size
      dereference(@b, pc, mem)
		  pc.branch(target)
		end
		
		# Branch to address specified by A if the B-field of the B operand is zero.
		
		def JMZ(pc, mem)
		  raise MARSRuntimeException, "JMZ: immediate A-field not allowed" if @a[0] == ?#
		  target = dereference(@a, pc, mem) % mem.size
      operand = mem.fetch(dereference(@b, pc, mem))
      if field_value(operand.b) == 0
		    pc.branch(target)
	    end
		end
		
		# As in JMZ, but branch if operand is non-zero
		
		def JMN(pc, mem)
		  raise MARSRuntimeException, "JMN: immediate A-field not allowed" if @a[0] == ?#
		  target = dereference(@a, pc, mem) % mem.size
      operand = mem.fetch(dereference(@b, pc, mem))
      if field_value(operand.b) != 0
		    pc.branch(target)
	    end
		end
		
		# DJN combines the auto-decrement mode dereference logic with a branch -- take
		# the branch if the new value of the B field of the pointer is non-zero.
		
		def DJN(pc, mem)
		  raise MARSRuntimeException, "DJN: immediate A-field not allowed" if @a[0] == ?#
		  target = dereference(@a, pc, mem)
      operand_addr = dereference(@b, pc, mem)
      operand = mem.fetch(operand_addr)
      newb = field_value(operand.b) - 1
      mem.store_field(operand_addr, (newb % mem.size), :b)
      if newb != 0
		    pc.branch(target)
	    end
      pc.log(operand_addr)
		end
		
    # Durham just says "compare two fields" if the operand is immediate.  Since
    # B can't be immediate, we just need to look at the A operand and, presumably,
    # compare it to the A operand of the dereferenced operand fetched by the B field.
    # If A is not immediate compare two full Words -- including op codes.  
    # The call to pc.next increments the program counter for this thread, which causes 
    # the skip.

		def CMP(pc, mem)
		  raise MARSRuntimeException, "CMP: immediate B-field not allowed" if @b[0] == ?#
      right = mem.fetch(dereference(@b, pc, mem))
		  if @a[0] == ?#
		    left = field_value(@a)
		    right = field_value(right.a)
	    else
  		  left = mem.fetch(dereference(@a, pc, mem))
      end
      if left == right
		    pc.next
	    end
		end
		
		# Major ambiguity here -- what does it mean for an word A to be "less than"
		# word B?  First assumption, don't compare opcodes.  Second, we're just going
		# to implement one-field comparisons of B fields.  Otherwise for full-word operands
		# we'd need to do a lexicographic compare of A and B fields of both operands, skipping
		# modes and just comparing values.
		
		def SLT(pc, mem)
		  raise MARSRuntimeException, "SLT: immediate B-field not allowed" if @b[0] == ?#
		  if @a[0] == ?#
		    left = field_value(@a)
	    else
  		  left = field_value(mem.fetch(dereference(@a, pc, mem)).b)
		  end
      right = field_value(mem.fetch(dereference(@b, pc, mem)).b)
		  if left < right 
		    pc.next
	    end
		end
		
		# Fork a new thread at the address specified by A.  The new thread goes at the end
		# of the queue.  Immediate operands are not allowed.  Durham doesn't mention it, but
		# implies only A is dereferenced, so ignore B.
		
		def SPL(pc, mem)
		  raise MARSRuntimeException, "SPL: immediate A-field not allowed" if @a[0] == ?#
		  target = dereference(@a, pc, mem)
		  pc.add_thread(target)
		end
				
	end # class Word
	
	
=begin rdoc
  A Warrior is a core warrior -- an object of this class is a simple struct that
  has the program name, assembled code, the starting location, and the symbol table.
  
  A static method (Warrior.load) will load an assembled Warrior into memory, making
  sure the max number of programs is not exceeded.  The addr attribute is set to the
  starting location of the program when it is loaded.
=end

  class Warrior
    attr_reader :name, :code, :symbols, :errors
			
  	def initialize(filename)
  	  if filename.class == Symbol
  	    filename = File.join(@@marsDirectory, filename.to_s + ".txt")
      end

      if ! File.exists?(filename)
        raise "Can't find file: #{filename}"
      end

      @name, @code, @symbols, @errors = MARS.assemble( File.open(filename).readlines )

  		if @errors.length > 0
  		  puts "Syntax errors in #{filename}:"
  	    puts errors
  	    @code.clear
  	  end
    end

  	def inspect
  	  sprintf "Name: #{@name} Code: #{@code.inspect}"
  	end
  	
  	alias to_s inspect
  	
   def Warrior.load(app, addr = :random)
      if app.class != Warrior
        puts "Argument must be a Warrior object, not a #{app.class}"
        return nil
      end
     
      if @@entries.length == @@maxEntries
        puts "Maximum #{@@maxEntries} programs can be loaded at one time"
        return nil
      end
      
      if addr == :random
        loop do
          addr = rand(@@mem.size)
          break if Warrior.check_loc(addr, addr + app.code.length - 1)
        end
      else
        if ! Warrior.check_loc(addr, addr + app.code.length - 1)
          puts "Address #{addr} too close to another program; #{app.name} not loaded"
          return nil
        end
      end
      
      loc = addr
      app.code.each do |x|
        @@mem.store(loc, x)
        loc = (loc + 1) % @@mem.size
      end

      id = @@entries.length
      @@pcs << PC.new(id, addr + app.symbols[:start])
      @@entries << app
      
      # save the range of memory locations reserved by this app
      
      lb = addr - @@params[:buffer]
      ub = addr + app.code.length + @@params[:buffer] - 1
      if lb < 0
        @@in_use << ( 0 .. (addr+app.code.length-1) )
        @@in_use << ( (@@params[:memSize] + lb) .. (@@params[:memSize]-1) )
      elsif ub > @@params[:memSize]
        @@in_use << ( addr .. (@@params[:memSize]-1) )
        @@in_use << ( 0 .. (ub - @@params[:memSize]) )
      else
        @@in_use << (lb..ub)
      end
      
      return addr
    end
    
    @@in_use = Array.new
    
    def Warrior.reset
      @@in_use = Array.new
    end
    
    private

    # Return true if a program loaded between lb and ub would not overlap another
    # program already loaded (including a buffer surrounding loaded programs).

    def Warrior.check_loc(lb, ub)
      @@in_use.each do |range|
        return false if range.include?(lb) || range.include?(ub)
      end
      return true
    end
	  
  end # class Warrior
  
  
=begin rdoc
  The PC class is used to represent the set of program counters for a running program.
  It has an array of locations to hold the next instruction from each thread, plus the
  index of the thread to use on the next instruction fetch cycle.
  
  Call next to get the address of the next instruction to execute; as a side effect this
  call bumps the thread pointer to the next thread in the program.  Call add_thread(n)
  to start a new thread running at location n.  Call kill_thread to remove the thread
  that was used in the most recent call to next (i.e. when that program dies).
  
  To help visualize the operation of a program the class keeps a history of memory
  references made by each thread.  A call to next automatically records the program counter
  value, but a semantic routine can also all log(x) to append location x to a history.
  Call history to get the history vectors for all threads. 
=end

  class PC
    attr_reader :id, :thread, :addrs, :current
    
    @@hmax = 10       # see also @@threadMax in Draw -- allowed to be a different value

    def initialize(id, addr)
      @id = id
      @addrs = [addr]
      @history = [ Array.new ]
      @thread = 0
      @current = {:thread => nil, :addr => nil}
      @first = addr
    end
    
    def reset
      @addrs = [@first]
      @history.clear
      @thread = 0
      @current = {:thread => nil, :addr => nil}
      return @first
    end
  
    def inspect
      s = "[ "
      @addrs.each_with_index do |x,i|
        s << "*" if i == @thread
        s << x.to_s
        s << " "
      end
      s << "]"
    end
    
    alias to_s inspect
    
    # Not sure if this is right -- new thread appended to list, as per Durham, but
    # the execution stays with the current thread (thread switch happens in 'next' method)

    def add_thread(addr)
      @addrs << addr
      @history << Array.new
      self
    end
        
    def next
      return nil if @addrs.empty?
      addr = @addrs[@thread]
      @current[:thread] = @thread
      @current[:addr] = addr
      @addrs[@thread] = (@addrs[@thread] + 1) % @@mem.size
      @thread = (@thread + 1) % @addrs.size
      log(addr)
      return addr
    end
    
    def branch(loc)
      @addrs[@current[:thread]] = loc
    end
  
    def kill_thread
      return 0 if @addrs.empty?
      @addrs.slice!(@current[:thread])
      @history.slice!(@current[:thread])
      @thread -= 1
      return @addrs.length
    end

=begin rdoc
  record the location of a memory operation in the history vector for the current thread
=end

    def log(loc)
    	a = @history[@current[:thread]]
    	a << loc
    	a.shift if a.length > @@hmax	
    end
    
    def history
      return @history
    end
    
  end # class PC
  
=begin rdoc
  An object of the Memory class is a 1-D array of the specified size.  Methods namde
  store and fetch operate on full words, while store_field and fetch_field operate on partial words.
=end
	
	class Memory
				
    attr_reader :array

		def initialize(size)
			@array = Array.new(size)
		end
		
		def to_s
		  sprintf "Memory [0..#{@array.size-1}]"
		end
				
=begin rdoc
  dump(loc,n) -- print the n words in memory starting at loc
=end

    def dump(loc, n)
      (loc...(loc+n)).each do |x|
        addr = x % @array.size
        printf "%04d: %s\n", addr, self.fetch(addr) 
      end
    end

		def size
		  return @array.size
	  end
				
		# Methods for fetching and storing data in memory.  According to the standard,
		# memory is initialized with DAT #0 instructions, but our array has nils; the
		# fetch method returns a DAT #0 from an uninitialized location.  
		
		def fetch(loc)
			return ( @array[loc] || Word.new("DAT", "#0", "#0", nil) )
		end
		
		def store(loc, val)
			@array[loc] = val.clone
		end
		
		# fetch and store operations that work on partial words
		
		def fetch_field(loc, field)
		  instr = self.fetch(loc)
			return field == :a ? instr.a : instr.b
		end
		
		def store_field(loc, val, field)
		  instr = self.fetch(loc)
		  part = (field == :a) ? instr.a : instr.b
		  mode = @@modes.include?(part[0]) ? part[0].chr : ""
		  part.replace(mode + val.to_s)
	    self.store(loc, instr)
		end
								
	end # class Memory
	
=begin rdoc
  A miniature machine (MiniMARS) object is used to test a program.  Pass the name of
  a Recode program to the constructor and get back a VM that has a memory where this
  program has been loaded into location 0.  Pass an extra parameter to define the size
  of the memory (otherwise the memory is just big enough to hold the program).  Call the
  step method to execute a single instruction, or run to run the program until it hits
  a DAT instruction or executes max instructions.
=end

	class MiniMARS
	  attr_reader :mem, :pc, :state
	  
    def initialize(file, size = nil)
      w = Warrior.new(file)
      @mem = size ? Memory.new(size) : Memory.new(w.code.length)
      loc = 0
      w.code.each do |x|
        @mem.store(loc, x)
        loc = loc + 1
      end
      @pc = PC.new(w.name, w.symbols[:start])
      @state = :ready
    end
	 
    def inspect
      return "#<MiniMARS mem = #{@mem.array.inspect} pc = #{@pc}>"
    end
    
    alias to_s inspect
    
    def status
      s = "Run: #{@state}"
      s += " PC: #{@pc}" unless @state == :halt
      puts s
    end

	  def step
	    return "machine halted" if @state == :halt
	    instr = @mem.fetch(@pc.next)
	    @state = instr.execute(@pc, @mem)
	    return instr
	  end
	  
	  def run(nsteps = 1000)
      count = 0
      loop do
        break if @state == :halt || nsteps <= 0
        self.step
        nsteps -= 1
        count += 1
      end
      return count 
	  end
	  
	  def reset
	    @pc.reset
	    puts "warning: memory may not be in initial state"
	  end
	  
	  def dump(*args)
	    if args.empty?
	      @mem.dump(0, @mem.array.length)
      else
        x = args[0]
        y = args[1] || x
        @mem.dump(x, y-x+1)
      end
      return nil
	  end
	 
	end # MiniMARS
	
=begin rdoc
  Make a window to display the state of the machine
=end
	
	class Draw 

  	@@cellSize = 8
  	@@cellRows = 32
  	@@cellCols = 128
  	@@padding = @@cellSize
  	@@traceSize = 10
  	@@cellColor = '#CCCCCC'

  	def paintCell(i, color)
  		@cells[i]['fill'] = color
  	end

  	def fillCanvas(mem)
  		@cells = []
  		mem.each_with_index do |val, i|	
  			x = (i % @@cellCols) * @@cellSize + @@padding
  			y = (i / @@cellCols) * @@cellSize + @@padding
  			@cells << TkcRectangle.new( @canvas, x, y, x+@@cellSize, y+@@cellSize, :outline => "#888888", :fill => @@cellColor )
  		end
  	end
  	
  	def reset
  	  @cells.each do |cell|
  	    cell['fill'] = @@cellColor
  	  end
  	end
  	
  	# Make a range of colors starting from first and going to last in n steps.
  	# First and last are expected to be 3-tuples of integer RGB values.  The
  	# result is an array that starts with first, has n-1 intermediate colors,
  	# and ends with last.  Example: 
  	#    makePalette( [255,0,0], [0,0,0], 10) 
  	# makes 11 colors starting with red and ending with black.

  	def makePalette(first, last, n)
  		d = Array.new(3)
  		3.times { |i| d[i] = (first[i] - last[i]) / n }
  		a = [first]
  		(n-1).times do |i|
  			a << a.last.clone 
  			3.times { |j| a.last[j] -= d[j] }
  		end
  		a << last
  		a.map { |c| sprintf("#%02X%02X%02X",c[0],c[1],c[2]) }
  	end

  	def updateCells(pc)
  	  id = pc.id
  	  a = pc.history[pc.current[:thread]]
  		d = @palette[id].length - a.length
  		a.each_with_index do |x, i| 
  			paintCell(x, @palette[id][i+d])
  		end
  	end

  	def initialize(parent) 
  		content = TkFrame.new(parent)
  		@canvas = TkCanvas.new(content, :borderwidth => 1,
  			:width => @@cellCols*@@cellSize+@@padding, :height => @@cellRows*@@cellSize+@@padding) 
  		fillCanvas(Array.new(4096))
  		
  		@canvas.grid :column => 0, :row => 0, :columnspan => 4, :padx => 10, :pady => 10
  		content.pack :pady => 20

  		# initialize palettes with blends from a dingy color to gray, then
  		# add a bright color as the last item

  		@palette = [
  			makePalette( [204,204,204], [204,100,100], @@traceSize ), 
  			makePalette( [204,204,204], [100,100,204], @@traceSize ),
  			makePalette( [204,204,204], [100,204,100], @@traceSize ),
  		]
  		@palette[0] << "#FF0000"
  		@palette[1] << "#0000FF"
  		@palette[2] << "#00FF00"
  	end 

  end # class Draw
  
  
=begin rdoc
  The MARS module is a package that has the methods used to assemble, load, and execute
  up to three programs at a time.
=end

  class MARS
  
  #  -------- Assembler ----------
  
  # line format:
  #     <label>   <opcode> <A-mode><A-field>, <B-mode><B-field>   <comment>
  
  # Parsing methods strip off and return the item they are looking for, or raise
  # an error if the line doesn't start with a well-formed item

    def MARS.parseLabel(s)             # labels start in column 0, can be any length
      return nil if s =~ /^\s/
      x = s[/^\w+/]               # set x to the label
      if x.nil?                   # x is nil if label didn't start with a word char
        raise RedcodeSyntaxError, "illegal label in '#{s}'"
      end
      if @@opcodes.include?(x.upcase)
        raise RedcodeSyntaxError, "can't use opcode '#{x}' as a label"
      end
      s.slice!(x)                 # remove it from the line
      return x                    # return it
    end
  
    def MARS.parseOpCode(s)
      if s !~ /^\s/               # expect opcode to be separated from label (or start of line) by white space
        raise RedcodeSyntaxError, "illegal label in '#{s}'"
      end
      s.lstrip!
      x = s[/^\w+/]               # set x to the opcode
      if x.nil? || !@@opcodes.include?(x.upcase)
        raise RedcodeSyntaxError, "unknown opcode '#{x}'"
      end
      s.slice!(x)                 # remove it from the line
      return x.upcase             # return it
    end
  
    def MARS.parseOperand(s)
      s.lstrip!
      return s if s.length == 0
      x = s[/^[#{@@modes}]?[+-]?\w+/]
      if x.nil?
        raise RedcodeSyntaxError, "illegal operand in '#{s}'"
      end
      s.slice!(x)
      return x.upcase
    end
  
    def MARS.parseSeparator(s)
      s.lstrip!
      return if s.length == 0
      if s[0] == ?,
        s.slice!(0)
      else
        raise RedcodeSyntaxError, "operands must be separated by a comma"
      end
    end
  
    def MARS.parse(s)
  	  label = MARS.parseLabel(s)
  	  op = MARS.parseOpCode(s)
  	  a = MARS.parseOperand(s)
  	  MARS.parseSeparator(s)
  	  b = MARS.parseOperand(s)
      return [label,op,a,b]
    end
  
    def MARS.saveWord(instr, label, code, symbols)		    
      if instr.op == "EQU"
        operand = instr.a
        arg = operand[/[+-]?\d+/]
        operand.slice!(arg)
        raise RedcodeSyntaxError, "EQU operand must be an integer" unless operand.length == 0
        raise RedcodeSyntaxError, "EQU must have a label" if label.nil?
        symbols[label.upcase] = arg.to_i
      elsif instr.op == "END"
        if n = symbols[instr.a]
          symbols[:start] = n
        else
          raise RedcodeSyntaxError, "unknown operand in END: #{instr.a}" if instr.a.length > 0
        end
      else
        if label
          symbols[label.upcase] = code.length      # "PC" value is number of codes saved so far
        end
        code << instr
      end
    end
      
    def MARS.translate(s, symbols, loc)
      if s.length == 0
        s.insert(0, "#0")
        return true
      end
      if md = s.match(/[#{@@modes}]?(\w+)/)
        sym = md[1]
        return true if sym =~ /^[+-]?\d+$/
        return false unless symbols.has_key?(sym) 
        val = symbols[sym] - loc
        s.sub!(sym, val.to_s)
        return true
      end
      return false
    end
  
=begin rdoc
  Assembler -- pass in an array of strings, one instruction per string, get back
  the program name, an array of Word objects, a symbol table, and an array 
  of error messages.
=end

    def MARS.assemble(strings)
      code = Array.new              # save Word objects here
      symbols = Hash.new            # symbol table
      errors = Array.new            # put error strings here
      name = "unknown"              # default program name
      name += @@entries.size.to_s
      symbols[:start] = 0           # default starting address
		
  		# Pass 1 -- create list of Word objects, build the symbol table:
		
  		strings.each_with_index do |line, lineno|
  			line.rstrip!
  			next if line.length == 0                    # skip blank lines
  			if line[0] == ?;                            # comments have ; in column 0
  			  if md = line.match(/;\s*name\s+(\w+)/)    # does comment have program name?
  			    name = md[1]                            # yes -- save it
  		    end
  			  next
  		  end
  		  if n = line.index(";")                      # if comment at end remove it
  		    line.slice!(n..-1)
  	    end
        begin
          label, op, a, b = MARS.parse(line)
          # puts "parse '#{label}' '#{op}' '#{a}' '#{b}'"
          instr = Word.new(op, a, b, lineno+1)
          MARS.saveWord(instr, label, code, symbols)		    
        rescue RedcodeSyntaxError
          errors << "  line #{lineno+1}: #{$!}"
        end
  		end
		
  		# Pass 2 -- translate labels into ints on each instruction:
      # TODO -- deal with expressions, e.g. "JMP label + 1"
		
      code.each_with_index do |instr, loc|
        if instr.op == "DAT" && instr.b.length == 0
          instr.a, instr.b = instr.b, instr.a
        end
        begin
          MARS.translate(instr.a, symbols, loc) or raise RedcodeSyntaxError, "unknown/illegal label"
          MARS.translate(instr.b, symbols, loc) or raise RedcodeSyntaxError, "unknown/illegal label"
    		rescue RedcodeSyntaxError
          errors << "  line #{instr.lineno}: #{$!}"
        end
  		end
		
  		return [name, code, symbols, errors]
  	end

    #  -------- End Assembler ----------

  
=begin rdoc
  step() -- execute one instruction from each active program.  If a thread dies remove the PC
  from the array for that program.  A program dies when its last thread dies.
=end
		
  	def MARS.step	  
      if @@entries.empty?
        puts "no programs loaded"
        return 0
      end
    
      # A list of program ids that terminate on this cycle
      done = []

      # This loop gets the current instruction from each active program and executes it.
      # The return value from the execute method is true if the thread executes a DAT
      # instruction.  The other way to stop the thread is if it has a runtime exception.
    
      @@pcs.each_with_index do |pc, id|
        loc = pc.next 
        instr = @@mem.fetch(loc)
  		  printf("%04d: %s\n", pc.current[:addr], instr) if @@params[:tracing]

        if @@drawing
          @@drawing.updateCells(pc)
          sleep(@@params[:pace])
        end
      
        begin
          signal = instr.execute(pc, @@mem)
        rescue MARSRuntimeException
          puts "runtime error: #{$!} in instruction on line #{instr.lineno}"
          signal = :halt
        end

        # If this thread halted delete the thread location from the program counter's list. 
        # The return value from kill_thread is the number of threads left -- if 0 the 
        # program is done.
      
        if signal == :halt
          if pc.kill_thread == 0
            done << id              # old C++ habit -- don't delete from container while iterating....
          end
        end
      
      end
    
      # Remove any newly terminated programs from the list of program counters, stop the machine
      # when no programs are left.

      done.each do |x|
        @@pcs.slice!(x)
      end
    
      return @@pcs.size
    
  	end
	
=begin rdoc
  run(n) -- run the programs, stopping when the number of surviving programs is n.  For a
  contest n will be 1, but for testing it can be 0.  Another way to return from this method
  is when a specified number of rounds of instruction executions have taken place.
=end
	
  	def MARS.run(nleft = 0)
      nrounds = @@params[:maxRounds]
      loop do
        nprog = MARS.step
        nrounds -= 1
        break if nprog == nleft || nrounds <= 0
      end
  	end
	
=begin rdoc
  state() -- print info about the machine and any programs in memory
=end
	
  	def MARS.state
      puts "MARS CPU with #{@@mem.size}-word memory"
      if @@entries.length == 0
        puts "no programs loaded"
      else
        for i in 0...@@entries.length
          puts "Program: #{@@entries[i].name}"
          puts "  code:     #{@@entries[i].code.inspect}"
          puts "  threads:  #{@@pcs[i]}"
        end
      end
      puts "Options:"
      @@params.each do |key, val|
        puts "  #{key}:  #{val}"
      end
      return true
  	end
	
	
=begin rdoc
  set_option(key, val) -- set the value of one of the run-time options (valid
  only when no programs are loaded)
=end

  def MARS.set_option(key, val)
    if ! @@entries.empty?
      puts "Options can be set only when no programs are loaded (call 'reset' to clear programs)"
      return false
    end
    case key
    when :memSize
      if val.class != Fixnum || val < 1024 || val > 16536
        puts ":memSize must be an integer between 1024 and 16536"
        return nil
      end
    when :maxRounds, :buffer
      if val.class != Fixnum
        puts ":#{key} must be an integer"
        return nil
      end
    when :pace
      if val.class != Float
        puts ":#{key} must be an floating point number (e.g. 0.05)"
        return nil
      end
    when :tracing
      if ! (val.class == TrueClass || val.class == FalseClass)
        puts ":tracing must be true or false"
        return nil
      end
    else
      puts "Unknown option: #{key}"
      return nil
    end
    @@params[key] = val
  end
	
=begin rdoc
  view() -- open a visual view of the machine state
=end

    def MARS.view
      require 'tk'
    
      if ! defined? @@tkroot
      	@@tkroot = TkRoot.new { title "MARS" }
    	end
  	
    	if @@drawing == nil
      	@@drawing = Draw.new(@tkroot) 
      	@@threads = []
      	@@threads << Thread.new() do
      		Tk.mainloop
      	end
    	end
    end
  
    def MARS.close_view
      @@threads[0].kill
      @@tkroot.destroy
      @@drawing = nil
    end
  
=begin rdoc
  Run a contest.  Parameters are names of up to three programs.  Make a Warrior
  object for each one, load them, and call run.
=end

    def MARS.contest(*args)
      MARS.reset
      if args.length < 1 || args.length > 3
        puts "Pass one, two, or three program names"
        return nil
      end
      args.each do |x|
        Warrior.load(Warrior.new(x))
      end
      MARS.run(1)      # the 1 means stop when only 1 program left running
    end

=begin rdoc
  reset() -- stop the current contest; clear all PCs, reset memory to all nils
=end

    def MARS.reset
      @@pcs = Array.new
    	@@mem = Memory.new(@@params[:memSize])
      @@entries = Array.new
      Warrior.reset
      @@drawing.reset if @@drawing
    end
   
=begin rdoc
  Print the code for one of the Redcode source programs.
=end

    def MARS.listing(prog, dest = nil)
      filename = prog.to_s
      filename += ".txt" unless filename =~ /\.txt$/
      filename = File.join(@@marsDirectory, filename)
      dest = STDOUT if dest.nil?
      if !File.exists?(filename)
        puts "File not found: #{filename}"
      else
    	  File.open(filename).each do |line|
    	    dest.puts line.chomp
    	  end
  	  end
  	  return nil
    end
    
=begin rdoc
  Save a copy of a Redcode source program; if no output file name specified
  make a file name from the program name.
=end

    def MARS.checkout(prog, filename = nil)
      filename = prog.to_s + ".txt" if filename.nil?
      dest = File.open(filename, "w")
      MARS.listing(prog, dest)
      dest.close
      puts "Copy of #{prog} saved in #{filename}"
    end
    
=begin rdoc
  Print a list of programs
=end

    def MARS.dir
      puts "Redcode programs in #{@@marsDirectory}:"
      Dir.open(@@marsDirectory).each do |file|
        next if file[0] == ?.
        file.slice!(/\.txt/)
        puts "  " + file
      end
      return nil
    end
  
  end # class MARS
  
  
=begin rdoc
  Make a test machine
=end
  
  def make_test_machine(file, size = nil)
    begin
      return MiniMARS.new(file, size)
    rescue Exception => e
      puts "Failed to make test machine: #{$!}"
      return nil
    end
  end

    # -- Initializations -- These are "global" vars in the outer MARSLab scope that are
    # accessible to all the classes and modules defined inside MARSLab
  
	@@marsDirectory = File.join(File.dirname(__FILE__), '..', 'data', 'mars')

  @@opcodes = ["DAT", "MOV", "ADD", "SUB", "JMP", "JMZ", "JMN", "DJN", "CMP", "SPL", "END", "SLT", "EQU"]
  @@modes = "@<#"

  @@maxEntries = 3
  @@displayMemSize = 4096

  @@params = {
    :maxRounds => 1000,
    :memSize => @@displayMemSize,
    :buffer => 100,
    :tracing => false,
    :pace => 0.01,
  }
  
	@@drawing = nil

  @@pcs = Array.new
	@@mem = Memory.new(@@params[:memSize])
  @@entries = Array.new

end # MARSLab

end # RubyLabs