#!/usr/bin/perl -w
# Interpret and run output generated by zoltraak20.c and later versions.
# Reads from stdin and writes output to stdout.
#
# This script is used to run the generated output directly, without having
# to go through a C compiler.  This is needed because the output gets really
# expensive to compile as it grows past a certain size, so we use this script
# to verify that the encoder still works as expected for larger inputs.

use strict;
use constant START_HEADER => "#ifndef";
use constant END_HEADER => "#endif";
use constant XOR_KEY => 0x20;
use constant MAX_STACK_DEPTH => (999 - 1) / 2;
use constant MAX_STACK_SIZE => MAX_STACK_DEPTH * 3 + 1;
use constant MAX_STEPS => 64 * 1024 * 1024;
use constant TRACE => 0;

# Load input as a list of numbers.
sub load_input()
{
   my @code = ();

   my $seen_header = 0;
   my $inside_header = 0;
   my $incomplete_instruction = 0;
   while( my $line = <> )
   {
      if( $inside_header )
      {
         if( index($line, END_HEADER) >= 0 )
         {
            $inside_header = 0;
         }
         next;
      }
      else
      {
         if( index($line, START_HEADER) >= 0 )
         {
            $seen_header = $inside_header = 1;
            next;
         }
      }

      my $n = $line =~ /^\s*[zs]/ ? 1 : 0;
      for(my $i = 1; $i < 9; $i++)
      {
         unless( defined($line = <>) )
         {
            die "Unexpected end of file\n";
         }
         $n |= $line =~ /^\s*[zs]/ ? (1 << $i) : 0;
      }
      push @code, $n;

      if( ($n & 0x100) != 0 )
      {
         $incomplete_instruction = 0;

         # Check branch target.
         if( $#code > 0 && ($code[$#code - 1] & 0x100) == 0 )
         {
            my $offset = ($n & 0xff) + 1;
            my $target = $#code - 1 - $offset;
            if( $target < 0 )
            {
               die "Branch out of bounds at line $.\n";
            }
            if( $target > 0 && ($code[$target - 1] & 0x100) == 0 )
            {
               die "Branch into incomplete instruction at line $.\n";
            }
         }
      }
      else
      {
         if( ++$incomplete_instruction > 1 )
         {
            die "Incomplete instruction at line $.\n";
         }
      }
   }
   unless( $seen_header )
   {
      die "Missing header\n";
   }
   return @code;
}

# Return the smaller of two numbers.
sub min($$)
{
   my ($a, $b) = @_;
   return $a < $b ? $a : $b;
}

# Interpret code.
sub run(@)
{
   my (@code) = @_;

   my $interpretor_steps = 0;

   # Stack with 1+3*N entries:
   # 1 = total number of steps remaining.
   # 3*N+1 = return address.
   # 3*N+2 = maximum number of steps to run at this stack frame.
   # 3*N+3 = number of steps remaining at this stack frame.
   my @stack = (1 << 30);
   for(my $ip = 0; $ip < scalar @code;)
   {
      if( ++$interpretor_steps > MAX_STEPS )
      {
         die "Stopping after $interpretor_steps steps\n";
      }

      if( ($code[$ip] & 0x100) != 0 )
      {
         # Output literal.
         if( TRACE )
         {
            my $frame = "";
            if( (scalar @stack) > 1 )
            {
               $frame = sprintf ' [%d,%d,%d]',
                      $stack[$#stack - 2],
                      $stack[$#stack - 1],
                      $stack[$#stack],
            }
            printf '%s%d:%s output %02x'."\n",
                   ' ' x (((scalar @stack) - 1) / 3),
                   $ip,
                   $frame,
                   ($code[$ip] & 0xff) ^ XOR_KEY;
         }
         else
         {
            print chr(($code[$ip] & 0xff) ^ XOR_KEY);
         }
         $stack[$#stack]--;
         if( $stack[$#stack] > 0 )
         {
            $ip++;
         }
         else
         {
            # Return from repeat command.
            die "Stack underflow (empty)\n" if $#stack < 0;
            for(my $steps = 0; (scalar @stack) > 1;)
            {
               if( TRACE )
               {
                  printf '%s%d: [%d,%d,%d] return'."\n",
                         ' ' x (((scalar @stack) - 1) / 3),
                         $ip,
                         $stack[$#stack - 2],
                         $stack[$#stack - 1],
                         $stack[$#stack];
               }
               $stack[$#stack] -= $steps;
               last if $stack[$#stack] > 0;

               if( $#stack < 3 )
               {
                  die "Stack underflow\n";
               }
               pop @stack;
               $steps = pop @stack;
               $ip = pop @stack;
            }
         }
      }
      else
      {
         # Repeat.
         if( (scalar @stack) >= MAX_STACK_SIZE )
         {
            die "Stack overflow\n";
         }
         my $length = $code[$ip++] + 3;
         my $offset = ($code[$ip] & 0xff) + 1;
         if( TRACE )
         {
            my $frame = "";
            if( (scalar @stack) > 1 )
            {
               $frame = sprintf ' [%d,%d,%d]',
                      $stack[$#stack - 2],
                      $stack[$#stack - 1],
                      $stack[$#stack],
            }
            printf '%s%d:%s branch(length=%d, offset=%d)'."\n",
                   ' ' x (((scalar @stack) - 1) / 3),
                   $ip,
                   $frame,
                   $length,
                   $offset;
         }

         my $remaining_steps = min($stack[$#stack], $length);
         push @stack, ($ip + 1, $remaining_steps, $remaining_steps);
         $ip -= 1 + $offset;

         # New address is guaranteed to be at a good spot since we already
         # checked all the branch instructions at load time.
      }
   }
}


run(load_input());