Linear Feedback Shift Register

I haven't found any implementation in C# of the LFSR so accordling to Wikipedia i have implment it to myself.

https://en.wikipedia.org/wiki/Linear-feedback_shift_register

My implementation accept some parameter so can be adapted to various feedback polynomials (my refernce table)

https://web.archive.org/web/20161007061934/http://courses.cse.tamu.edu/csce680/walker/lfsr_table.pdf

For the testing pahse i generate as many number as the cycle will allow before a repetiton (i use a byte to my testing purpose).

EDITED (PROBLEM SOLVED IT WAS DUE A TYPO, QUESTION REPHRASED AT THE END)

The strange thing is in my test the period is exactly half of what expected/declared by the paper (not (2^n)-1 but 2^(n-1)).

Here is my LFSR implementation

public class Register
{
private bool[] _register = null ;
private bool[] _feedbackPoints = new bool[256] ;
private int _registerLength = 0 ;

public Register ( int length, int [] feedbackPoints ) : this ( length , feedbackPoints , new byte [0] ) {}

public Register ( int length, int [] feedbackPoints, byte [] seed )
{
if ( length > 256 )
throw new ArgumentOutOfRangeException ( "length" , "Alloewed vaues need to be between 1 and 256" ) ;

_registerLength = length ;

_register = new bool[length] ;

foreach ( int feedbackPoint in feedbackPoints )
if ( feedbackPoint > 256 )
throw new ArgumentOutOfRangeException ( "feedbackPoints", "Alloewed vaues of item of array need to be between 1 and 256" ) ;
else
_feedbackPoints[feedbackPoint] = true ;

byte [] randomizedSeed = this.SeedRandomization ( seed ) ;

string temporaryRegisterRepresantation = string.Empty ;
foreach ( byte seedItem in randomizedSeed )
temporaryRegisterRepresantation += Convert.ToString ( seedItem , 2 ) ;

int index = 0 ;
foreach ( char bit in temporaryRegisterRepresantation )
if ( index < length )
_register[index++] = bit == '1' ;
}

public bool Clock ()
{
lock ( this )
{
bool output = _register[0] ;

for ( int index = 0; index < _registerLength - 1; index++ )
_register[index] = _feedbackPoints[index] ? _register [index+1] ^ output : _register [index+1] ;

_register [_registerLength - 1] = output ;

return output ;
}
}

private byte[] SeedRandomization ( byte[] inputSeed )
{
SHA256Managed sha256 = new SHA256Managed ();
int seedLength = inputSeed.Length ;

byte [] seed = new byte [seedLength] ;
Array.Copy ( inputSeed , seed , seedLength ) ;

Array.Resize<byte> ( ref seed , seedLength + 4 ) ;
byte[] dateTime = BitConverter.GetBytes ( DateTime.Now.Ticks ) ;
seed[seedLength] = dateTime[0] ;
seed[seedLength+1] = dateTime[1] ;
seed[seedLength+2] = dateTime[2] ;
seed[seedLength+3] = dateTime[3] ;

return sha256.ComputeHash ( seed , 0 , seed.Length ) ;
}
}


And there is my testing code

class Program
{
static void Main ( string [] args )
{
Dictionary<int, bool> tester = new Dictionary<int, bool> ();
List<int> duplicate = new List<int> ();

Register register_1 = new Register ( 8 , new int[] { 5,4,3 } ) ;

for ( int index = 0; index < 256; index++ )
{
bool b00 = register_1.Clock ();
bool b01 = register_1.Clock ();
bool b02 = register_1.Clock ();
bool b03 = register_1.Clock ();
bool b04 = register_1.Clock ();
bool b05 = register_1.Clock ();
bool b06 = register_1.Clock ();
bool b07 = register_1.Clock ();

BitArray bitArray = new BitArray ( new bool [] { b00, b01, b02, b03, b04, b05, b06, b07 } );
int [] array = new int [1];
bitArray.CopyTo ( array, 0 );

if ( !tester.ContainsKey ( array[0] ) )
tester.Add ( array [0], true ) ;
else
duplicate.Add ( array[0] ) ;
}

duplicate = duplicate.OrderBy ( x => x ).ToList() ;
}
}


I have manually followed the implementation with 2bit LFSR and i see nothing wrong about it, so i would ask if there are any fallacies in my test or implementation.

EDITED

I have found my fault, i have omitted to write b00 so is correct that the period is exactly half of what expected.

I keep the code but renew my question, now i wold ask if you found any issue with current implementation (that seems to work with current test).

2 Answers

I totally agree with @Maxim about the spacing but need to say, that you didn't use spaces where you should for the sake of readability.
This

seed[seedLength] = dateTime[0] ;
seed[seedLength+1] = dateTime[1] ;
seed[seedLength+2] = dateTime[2] ;
seed[seedLength+3] = dateTime[3] ;


would be more readable if you place spaces like so

seed[seedLength] = dateTime[0];
seed[seedLength + 1] = dateTime[1];
seed[seedLength + 2] = dateTime[2];
seed[seedLength + 3] = dateTime[3];


Omitting braces {}, although they might be optional, can lead to hidden and therefor hard to track bugs. I would like to encourage you to always use them. This will avoid hidden bugs and the code looks better structured.

SeedRandomization ()

The SHA256Managed class implements IDisposable through inheriting HashAlgorithm so you should enclose its usage in a using block.

These variables

private bool[] _register = null ;
private bool[] _feedbackPoints = new bool[256] ;
private int _registerLength = 0 ;


should be made readonly because they won't change anywhere except in the constructor.

A little LINQ could simplify this

foreach ( int feedbackPoint in feedbackPoints )
if ( feedbackPoint > 256 )
throw new ArgumentOutOfRangeException ( "feedbackPoints", "Alloewed vaues of item of array need to be between 1 and 256" ) ;
else
_feedbackPoints[feedbackPoint] = true ;


but do you spot the spelling error which happened by using copy&pasta not carefully ?

At least I would place the part about feedbackPoint > 256 at the top of the constructor where the input parameter validation belongs.

A simple

if (feedbackPoints.Any(p => p > 256))
{
throw new ArgumentOutOfRangeException ( "feedbackPoints", "Allowed vaues of item of array need to be between 1 and 256" ) ;
}


could do the validation.

But what about the length parameter ? Passing length == -1 seems valid but will throw an OverflowException at _register = new bool[length] ;.

In addition the messages of the ArgumentOutOfRangeException's states "..... need to be between 1 and 256" but you only check in both cases value > 256 without checking the lower boundaries. If I read "between 1 and 256" I will think that the allowed values are 2...255 but this could be because I am not native english.

string temporaryRegisterRepresantation = string.Empty ;
foreach ( byte seedItem in randomizedSeed )
temporaryRegisterRepresantation += Convert.ToString ( seedItem , 2 ) ;


each time string += string happens a new string object is created because strings are immutable. If you want to concatenate strings in a loop most of the times it is better (time and space) to use a StringBuilder.

• Since I'm not native English speaker too you got me interested in the "between" meaning and I found this post: "Between A and B" or "from A to B" :) Commented Aug 3, 2017 at 7:03
• @Heslacher thanks for your review, expecially for the hint about readonly variables. I didn't know that a readonly variable can be assigned in the custructor. Thanks a lot for underline my blunder in boundaries check, reading that part of code twice i found a lot of problems indeed. Commented Aug 3, 2017 at 15:15

Just some notes about the code.

Read this: Why is lock(this) {…} bad?.

Also why do you use so many spaces? :) if ( !tester.ContainsKey ( array[0] ) ) looks strange, it is far from common practice. 99.9% of C# programmers will write it like

if (!tester.ContainsKey(array[0]))


In this code

List<int> duplicate = new List<int> ();
...
duplicate = duplicate.OrderBy ( x => x ).ToList() ;


you don't need OrderBy since the List<T> provides Sort method which doesn't require additional memory allocation.

I recommend to use var for all variables where the type is obvious from the right part of expression. I hope you'll agree that

var tester = new Dictionary<int, bool>();
var duplicate = new List<int>();


is nicer than

Dictionary<int, bool> tester = new Dictionary<int, bool> ();
List<int> duplicate = new List<int> ();


Also consider using Buffer.BlockCopy instead of Array.Copy for byte arrays. It will improve performance.

• i have read the article about the bad of lock(this), interesting but i doubt that is an issue in my situation (anyway it has really a cost zero the effort needed to modify my code, so probably i'll do; surely i'll keep in mind the drawback underlined in the article). Thanks for the Buffer.BlockCopy suggestion. Commented Aug 3, 2017 at 15:30