#!/usr/bin/perl -w
# Alternative version of zoltraak encoder where repeat instruction is
# implemented using a copy loop instead of setjmp/longjmp.

use strict;

# Syntactic sugar.
sub max($$)
{
   my ($a, $b) = @_;
   return $a > $b ? $a : $b;
}

# Count number of 1-bits in 8-bit integer.
sub bitcount($)
{
   my ($n) = @_;
   $n = ($n & 0x55) + (($n >> 1) & 0x55);
   $n = ($n & 0x33) + (($n >> 2) & 0x33);
   $n = ($n & 0x0f) + (($n >> 4) & 0x0f);
   return $n;
}


# Load prelude from DATA section.
my $prelude = "";
while( my $line = <DATA> )
{
   chomp $line;

   # Remove comments.
   $line =~ s/\/\*.*\*\///;

   # Compress spaces.
   if( $line =~ s/^\s*#/#/ )
   {
      if( $prelude ne "" && $prelude !~ /\n$/ )
      {
         $prelude .= "\n";
      }
      $prelude .= $line . "\n";
   }
   else
   {
      $line =~ s/\s//gs;
      $line =~ s/\b(char|int|void|return)(\w)/$1 $2/g;
      $prelude .= $line;
   }
}

# Output prelude.
print $prelude;

# Compress input bytes and output instructions.
my $input = join "", <>;

for(my $i = 0; $i < length($input);)
{
   # Find longest match in history.
   my $match_offset = undef;
   my $match_length = -1;
   for(my $j = max($i - 256, 0); $j < $i; $j++)
   {
      my $k = 0;
      for(; $k < 258 && $i + $k < length($input); $k++)
      {
         if( substr($input, $j + $k, 1) ne substr($input, $i + $k, 1) )
         {
            last;
         }
      }
      if( $k > $match_length ||
          ($k == $match_length &&
           bitcount($i - $j - 1) < bitcount($i - $match_offset - 1)) )
      {
         $match_offset = $j;
         $match_length = $k;
      }
   }

   my $code = 0;
   if( $match_length >= 3 )
   {
      # Output repeat code.
      $code = ($match_length - 3) |
              (($i - $match_offset - 1) << 9) |
              (1 << 17);
      $i += $match_length;
   }
   else
   {
      # Output literal code.
      $code = ord(substr($input, $i, 1)) ^ 0x120;
      $i++;
   }

   for(; $code != 0; $code >>= 1)
   {
      if( ($code & 1) != 0 )
      {
         print "zoltraak\n";
      }
      else
      {
         print "\n";
      }
   }
}


__DATA__
#ifndef zoltraak
#include<stdio.h>
char b[512];
int x, i, I;
void a(int _)
{
   if( (_ - I) % 9 )
   {
      /* Incomplete instruction, collect bits. */
      x |= 1 << (_ - I - 1);
   }
   else
   {
      if( _ - I - 18 )
      {
         /* Update ring buffer and output byte. */
         putchar(b[i++ & 511] = x ^ 32);
      }
      else
      {
         /* Copy historical byte to ring buffer and output byte. */
         for(I = x % 256 + 3; I--; i++)
            putchar(b[i & 511] =
                    b[(i - 1 - (x >> 9) % 256) & 511]);
      }
      x = 0;
      I = _;
   }
}
int main(void)
{
   /* Define instrunction and start of code section. */
   #define zoltraak a(__LINE__);
   #define s I=__LINE__+1;
   #include __FILE__

   /* Remove definitions so that rest of program expands to empty space. */
   #undef zoltraak
   #define zoltraak
   #undef s
   #define s
   return 0;
}
#else
/* Start of code section, inserted here to support concatenated programs. */
s
#endif