#!/usr/bin/perl -w
# Proof of concept for using LFSR to encode a stream.

use strict;

# Run a single step of LFSR.
sub LSFR($)
{
   my ($x) = @_;

   my $bit = $$x ^ ($$x >> 2) ^ ($$x >> 3) ^ ($$x >> 5);
   $$x = (($$x >> 1) | ($bit << 15)) & 0xffff;
}

# Form a byte by collecting bits at various positions from seed.
sub CollectBits($@)
{
   my ($x, @indices) = @_;

   my $byte = 0;
   for(my $i = 0; $i < 8; $i++)
   {
      if( ($x & (1 << $indices[$i])) != 0 )
      {
         $byte |= 1 << $i;
      }
   }
   return $byte;
}

# Select 8 random bit indices (out of 16).
sub SelectIndices()
{
   my @indices = ();
   for(my $i = 0; $i < 16; $i++)
   {
      push @indices, $i;
   }

   # Fisher-Yates shuffle
   for(my $i = 15; $i > 1; $i--)
   {
      my $j = int(rand($i + 1));
      @indices[$i, $j] = @indices[$j, $i];
   }
   $#indices = 7;
   return @indices;
}

# Output decoder header
sub Header(@)
{
   my (@indices) = @_;

   my $decode_expression = "";
   for(my $bit = 0; $bit < 8; $bit++)
   {
      if( $bit > 0 )
      {
         $decode_expression .= " |\n" . (" " x 10);
      }
      my $right_shift = $indices[$bit] - $bit;
      if( $right_shift > 0 )
      {
         $decode_expression .= "((seed >> $right_shift) & " . (1 << $bit) . ')';
      }
      elsif( $right_shift < 0 )
      {
         $decode_expression .= '((seed << ' . (-$right_shift) . ') & ' .
                               (1 << $bit) . ')';
      }
      else
      {
         $decode_expression .= '(seed & ' . (1 << $bit) . ')';
      }
   }

   print <<"EOT";
#include<stdio.h>

static int seed;

static int LFSR(int steps)
{
   int bit;
   while( steps-- )
   {
      bit = seed ^ (seed >> 2) ^ (seed >> 3) ^ (seed >> 5);
      seed = ((seed >> 1) | (bit << 15)) & 0xffff;
   }
   return $decode_expression;
}

int main(int argc, char **argv)
{
   if( argc < 2 || sscanf(argv[1], "%d", &seed) != 1 )
      return printf("%s <PIN>\\n", *argv);
EOT
}

sub Footer()
{
   print <<EOT;
   return 0;
}
EOT
}


# Initialize seed.
if( $#ARGV < 0 )
{
   die "$0 <seed>\n";
}
my $seed = $ARGV[0] =~ /^\d+$/ ? shift @ARGV : 0;
if( $seed < 1 || $seed > 65535 )
{
   die "<seed> must be in the range of [1, 65535]\n";
}

# Initialize decoder.
my @indices = SelectIndices();
Header(@indices);

# Translate bytes.
while( my $line = <> )
{
   foreach my $byte (unpack 'C*', $line)
   {
      my $min_steps = int(rand(8) + 1);
      my $steps = 0;
      for(; $steps < $min_steps || CollectBits($seed, @indices) != $byte;
          $steps++)
      {
         LSFR(\$seed);
      }
      print "   putchar(LFSR($steps));\n";
   }
}

# Output footer.
Footer();