Linear Feedback Shift Register

Question

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).

Answer 1

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.

• Maxim: 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" :)
• Skary: @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.

Answer 2

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.

• Skary: 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.