Run through a maximum length LFSR of a given length and check that after 2^n iterations it reaches 0 again.

lfsr-c.cpp

// lfsr-c.cpp
// Runs through a maximum length LFSR of a given length and checks that 
// after 2^n iterations it reaches 0 again.
#include <iostream>

using namespace std;

// taps for LFSR polynomials
static unsigned tap[64][6] =
{
	{0},          {0},           {0},          {3,2},    
	{4,3},        {5,3},	     {6,5},        {7,6},  
	{8,6,5,4},    {9,5},         {10,7},       {11,9}, 
	{12,6,4,1},   {13,4,3,1},    {14,5,3,1},   {15,14},
	{16,15,13,4}, {17,14},       {18,11},      {19,6,2,1},
	{20,17},      {21,19},       {22,21},      {23,18},
	{24,23,22,17},{25,22},       {26,6,2,1},   {27,5,2,1},
	{28,25},      {29,27},       {30,6,4,1},   {31,28}, 
	{32,22,2,1},  {33,20},       {34,27,2,1},  {35,33}, 
	{36,25},      {37,5,4,3,2,1},{38,6,5,1},   {39,35},
	{40,38,21,19},{41,38},       {42,41,20,19},{43,42,38,37},
	{44,43,18,17},{45,44,42,41}, {46,45,26,25},{47,42},
	{48,47,21,20},{49,40},       {50,49,24,23},{51,50,36,35},
	{52,49},      {53,52,38,37}, {54,53,18,17},{55,31},
	{56,55,35,34},{57,50},       {58,39},      {59,58,38,37},
	{60,59},      {61,60,46,45}, {62,61,6,5},  {63,62}
};

void print_usage() {
	cout << "Usage:" << endl;
	cout << "	lfsr-c <length>" << endl;
}

int main(int argc, char * argv[])
{
	if (argc != 2)
	{
		print_usage();
	    	exit(1);
	}

	int num_bits = strtol(argv[1], NULL, 10);
	uint64_t count_val = 1 << num_bits;

	if(num_bits < 3 || num_bits>63)
	{
		cerr << "Error: Bit lenngth should be >=3 and <64" << endl;
		exit(1);
	}


	uint64_t lfsr = 0;	// starting value of the chain
	for(uint64_t i=0;i<count_val-1; i++)
	{
		uint64_t d0 = 0;
		for (int j = 0; j < 6 && tap[num_bits][j]; j++)
			d0 ^= (lfsr >> ((tap[num_bits][j]) - 1)) & 1;
		lfsr = ((lfsr << 1) & ((1 << num_bits) - 1)) ^ !d0;
	}

	if(lfsr == 0) {
		cout << "OK" << endl;
		exit(0);
	} else {
		cout << "FAIL" << endl;
		exit(1);
	}
}