I ran into the concept of a Linear Feedback Shift Register
so I wrote one:
#!/usr/bin/perl -w
use strict;
# Generate a closure that implements a Feedback Shift Register:
# Usage:
# my $fsr= genFSR( $bits, $seed, \&feedBack, [@taps] );
# my $nextBit= $fsr->();
sub genFSR {
my( $bits, $seed, $code, $avTaps )= @_;
return sub {
my $ret= $seed & 1;
my $b= $code->( map $seed & 1<<$_ ? 1 : 0, @$avTaps );
$seed >>= 1;
$seed |= (1&$b)<<$bits;
return $ret;
};
}
# XOR all arguments:
sub xorList {
my $b= 0;
$b ^= pop while @_;
return $b;
}
# Generate a Linear Feedback Shift Register closure:
# Usage:
# my $lfsr= genFSR( $bits, $seed, [@taps] );
# $nextBit= $lfsr->();
sub genLFSR {
my( $bits, $seed, $avTaps )= @_;
return genFSR( $bits, $seed, \&xorList, $avTaps );
}
# Test the above using command-line arguments:
# Usage: lfsr nBits Seed tap tap [tap [...]]
# perl lfsr.pl 5 10 3 5
# perl lfsr.pl 5 0b1010 3 5 # Same if using perl 5.6 or later
# Both of the above use:
# genLFSR( 5, 10, [3,5] );
my $bits= shift;
my $seed= shift;
$seed= oct($seed) if $seed =~ /^0/;
my $lfsr= genLFSR( $bits, $seed, [@ARGV] );
while( 1 ) {
print join( " ", map $lfsr->(), 1..$bits ), $/;
}
To make playing golf on this easier, you only have to
implement a Linear FSR, and you don't have to accept the
list of taps from an anonymous array.
So write a function that generates a closure that implements
an N-bit LFSR with 2 or more taps:
my $lfsr= golfGenLFSR( $nBits, $iSeed, $tap0, $tap1, $tap2 );
my $nextBit= $lfsr->();
You may choose to use packed bit strings instead of
integers (see
vec).
-
tye
(but my friends call me "Tye")