#!/usr/bin/ruby -w
# xxxx xxxx 1 = output byte.
# aaaa aaaa 0 bbbb bbbb 1 = repeat: length=a+3, offset=b*9+1

# Minimum length for repeat instructions.  A single repeat instruction costs
# the same amount of space as two output instructions, so we the repeat
# length needs to be at least 3 for it to be worthwhile.
MIN_REPEAT = 3

# Minimum offset for repeat targets.
MIN_OFFSET = 1

# Instruction return states.
RS_NORMAL = 0
RS_FIRST_INSTRUCTION_AFTER_BRANCH = RS_NORMAL + 1
RS_SECOND_INSTRUCTION_AFTER_RETURN = 2
RS_FIRST_INSTRUCTION_AFTER_RETURN = RS_SECOND_INSTRUCTION_AFTER_RETURN + 1

# Maximum number of steps to run.
MAX_STEPS = 5000

# True to enable tracing.
TRACE = false

# Insert an output command.
def output(c)
   return ".#{c}"
end

# Insert a repeat label.
def label(l)
   return ":#{l}"
end

# Insert an unresolved repeat instruction.
def repeat(steps, target)
   fail unless steps >= MIN_REPEAT
   return "+#{target},#{steps}"
end

# Encode an 8-bit number, least significant bit first.
def encode_number(n)
   fail if n < 0
   fail if n > 255
   return (sprintf '%08b', n).reverse
end

# Assemble instruction into bits.
def assemble(code)
   bit_string = ""
   offset_map = {}
   code.each{|c|
      if c[0] == ":"
         # Label.
         offset_map[c[1..]] = bit_string.size
      elsif c[0] == "+"
         # Repeat.
         m = c.match(/^\+([^,]+),(\d+)$/)
         fail unless m
         fail "Undefined label #{m[1]}" unless offset_map[m[1]]
         offset = bit_string.size - offset_map[m[1]]
         fail unless offset % 9 == 0
         bit_string += encode_number(m[2].to_i - MIN_REPEAT) + "0" +
                       encode_number(offset / 9 - MIN_OFFSET) + "1"
      else
         # Output.
         bit_string += encode_number(c[1].ord) + "1"
      end
   }
   return bit_string
end

# Run assembled bitcode.
def run(code)
   # Control flow stack:
   # stack[2*N] = return address.
   # stack[2*N+1] = output bytes remaining.
   #
   # Output bytes remaining is decremented each time a byte is printed, and
   # control flow is returned to parent frame once the counter reaches zero.
   stack = [0, 100]

   # Stack pointer.
   sp = 1
   fail unless stack[sp] > 0

   # Instruction pointer.
   ip = -1

   # Instruction start.
   is = nil

   # Return state.  See RS_* constants near the top.
   rs = RS_FIRST_INSTRUCTION_AFTER_BRANCH

   # Accumulator.
   x = nil

   # Number of steps executed, used to detect runaway loops.
   steps = 0

   # Output current states.
   define_method :trace do |line, msg|
      return unless TRACE
      print " " * (sp - 1),
            "#{line}: steps=#{steps}, ip=#{ip}, ",
            "x=#{x ? '0x' + x.to_s(16) : 'nil'}, ",
            "stack[#{sp - 1}]=#{stack[sp - 1]}, ",
            "stack[#{sp}]=#{stack[sp]}, ",
            "is=#{is}, rs=#{rs}, #{msg}\n"
   end

   while ip < code.size
      steps += 1
      fail if steps > MAX_STEPS

      # First instruction after a branch or return is always ignored.
      # We always return to the end of the previous instruction because
      # "1" bits are only guaranteed to appear at the end of instructions,
      # and only "1" bits are valid branch targets.
      if rs & 1 != 0
         trace(__LINE__, "next")
         fail unless ip >= -1
         fail unless (ip + 1) % 9 == 0
         rs -= 1
         fail unless (rs == 0 || rs == 2)
         x = 0
         is = ip + 1
         ip += 1
         next
      end

      # Instruction execution only happens at "1" bits.
      fail unless ip >= 0
      if code[ip] == "0"
         ip += 1
         next
      end
      fail unless is
      fail unless x
      fail unless x >= 0

      # Check if instruction pointer has reached the end of a complete
      # instruction.  If not, update accumulator and move on.
      if (ip + 1) % 9 != 0
         trace(__LINE__, "accumulate")
         x |= 1 << (ip - is)
         ip += 1
         next
      end
      fail unless (ip - is == 8 || ip - is == 17)

      # Check for repeat instruction.
      if ip - is == 17
         length = (x & 0xff) + MIN_REPEAT
         offset = ((x >> 9) + 2 + MIN_OFFSET) * 9

         if rs == RS_SECOND_INSTRUCTION_AFTER_RETURN
            # Recursive return.
            trace(__LINE__, "recursive_return: length=#{length}")
            stack[sp] -= length
            if stack[sp] <= 0
               rs = RS_FIRST_INSTRUCTION_AFTER_RETURN
               ip = stack[sp - 1]
               sp -= 2
               fail unless sp >= 1
               next
            end

            # Completed return chain.
            trace(__LINE__, "completed_return")
            rs = RS_NORMAL
            is = ip + 1
            ip += 1
            x = 0
            next
         end
         trace(__LINE__, "branch: offset=#{offset}, length=#{length}")
         fail unless rs == RS_NORMAL

         # Set return address to be start of previous instruction, and
         # branch to earlier part of the code.
         fail unless is - 1 == ip - 18
         stack[sp + 1] = is - 1
         stack[sp + 2] = [stack[sp], length].min
         ip -= offset
         rs = RS_FIRST_INSTRUCTION_AFTER_BRANCH
         sp += 2
         next
      end

      # Output byte.
      trace(__LINE__, "output")
      fail unless ip - is == 8
      fail unless rs == 0
      if TRACE
         print " " * (sp - 1), "#{__LINE__}: output(#{x.chr.dump})\n"
      else
         print x.chr
      end
      x = 0

      # Return when enough bytes have been printed.
      stack[sp] -= 1
      if stack[sp] == 0
         fail unless sp > 1
         rs = RS_FIRST_INSTRUCTION_AFTER_RETURN
         ip = stack[sp - 1]
         sp -= 2
         next
      end

      is = ip + 1
      ip += 1
   end
end


code =
[
   label("start"),
   output("1"),
   output("2"),
   label("tail"),
   output("3"),
   repeat(3, "tail"),
   repeat(18, "start"),
   output("\n"),
]

print code, "\n"
print assemble(code), "\n"
run(assemble(code))