Linear feedback shift register

Hi People,

Ive bee given an assignment to check out two simple pseudorandom number generators
and compare them in terms of the statistical properties of their outputs. One of them is a Linear feedback shift register. We've been given the code implemented in C (please see attached file)  but im prety new to programming and would greatly appreciate if somone could perhaps explain to me whats going on line per line. I prety much understand the theory behind LFSRs, its the actual implementation that has me confused..

Thanks in advance
LFSR.txt
oggiemcAsked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

ReedNewmanCommented:
Hopefully this doesn't wrap poorly.  Should be a line by line explanation of what this program does.
#include <stdlib.h>		//include standard libraries that this program requires
#include<stdio.h>
#include<stdint.h>
#include<stdbool.h>

uint16_t rand16();		//declare the function rand16 so that it may be used later in the program
					//this function takes no arguments and returns a unsigned integer of size 16 bits
uint32_t rand32();		//same as rand16 except that it returns an unsigned integer of 32 bits.

uint16_t n, userChosenValue = 0; //Change this for different seed values.
uint16_t numberOfValues = 100; //Change this depending on your needs.
uint16_t shiftReg;
uint16_t initSeed;
uint16_t mask;


int main(){							//the starting point for all c programs
  
  /*Calculate and print a series of 16 bit random numbers */
  shiftReg = 119 * 119 * (userChosenValue + 1);	//initialize shiftReg to 14,161 (will change when userChosenValue is not 0, 
								//as it's your seed value)
  initSeed = shiftReg;					//initialize initSeed to be the same as shiftReg
  mask = 137 * 29 * (userChosenValue + 1);	//initialize mask to be 3,973 (will also change when userChosenValue is not 0)
  
  printf("16 Bit:\n\n");				//prints "16 Bit: followed by two newline characters to the screen
								//Looks like:
								//16 Bit:
								//
								//--other print statements begin here
  for (n=0;n<numberOfValues;n++){			//loops through the function rand16() (see below) numberOfValues times (100) 
    printf("%.4x\n",rand16());			//prints a hexidecimal number of percision 4 to the screen (so 0xbeef for example)
								//it's really just to show the padded 0's in the beginning.  0x64 would print as 0x0064
  }


//this does almost exactly the same thing as above, just with 32 bit numbers
//instead of 16 bit numbers.  I've indicated where the values differ.  
  /*Calculate and print a series of 32 bit random numbers */
  shiftReg = 119 * 119 * (userChosenValue + 1);
  initSeed = shiftReg;
  mask = 137 * 29 * (userChosenValue + 1);
  
  printf("\n\n32 Bit:\n\n");				//prints two newlines, "32 Bit:", and another two newlines
  for (n=0;n<numberOfValues;n++){			
    printf("%.8x\t\t\n",rand32());			//print's hexidecimal digits with a percision of 8 instead of four
								//e.g. 0xdeadbeef
  }
  
  system("PAUSE");					//makes a call to the system to run the executable "PAUSE"
    return EXIT_SUCCESS;				//return to signal successful run of program
  
}


/* Return the next 16 bit random number */
uint16_t rand16() {
  bool endbit;
  uint16_t tmpShiftReg;
 
  tmpShiftReg = shiftReg;				//initializes tmpShiftReg to be shiftReg (which was initialized in main
  endbit = ((tmpShiftReg & 0x8000) != 0);		//initializes endbit to be true or false depending on
								//if (tmpShiftReg AND 0x8000) is equal to 0 (which it is based on the starting value
								//true would be 1, false would be 0
  tmpShiftReg <<= 1;					//This is short hand for tmpShiftReg = tmpShiftReg << 1
								//which means shift the value 1 position to the left.
  if (endbit) 						//if endbit is anything other than 0, execute the next line.  Otherwise, ignore it.
    tmpShiftReg ^= 0x100b;				//this expands to tmpShiftReg = tmpShiftReg ^ 0x100b (which means tmpShiftReg OR 0x100b)
  tmpShiftReg++;						//add 1 to tmpShiftReg (tmpShiftReg = tmpShiftReg + 1)
  shiftReg = tmpShiftReg;				//set shiftReg to tmpShiftReg (to reseed for the next run to get a different random number)
  tmpShiftReg = tmpShiftReg ^ mask;			//set tmpShiftReg to be tmpShiftReg OR mask (which was the original value of shiftReg set
								//in main
  
  return tmpShiftReg;					//returns tmpShiftReg (which in this program is just being printed out in main.
  
}

/* Return the next 32 bit random number */
uint32_t rand32() {
  return (uint32_t)rand16() << 16 | rand16();	//calls rand16(), takes the result and stores it in a 32 bit data type.
								//it then shifts that value over 16 positions (into the high order bits) and
								//calls rand16() again.  The result of the second call is OR'd into the low order
								//bits.  (so it's a 32 bit random number made up of two subsequent random 16 bit numbers)
}

Open in new window

0
oggiemcAuthor Commented:
Many thanks indeed ReedNewman for the quick and detailed response..Ill have a read over this and hopefully it will become clear to me!! One quick question for now though:

 Can you explain to me why we use uint32_t / uint16_t types?? Ive read some online material but i dont really understand..Does it mean that the integer returned takes up 32/16 bits of memory??Like the way individual characters take up a byte??

Once again,
Many thanks!!
0
ReedNewmanCommented:
oggiemc,

Yes, that's correct.  uint32_t specifies a specific size for the integer type.  If you were to just state 'int', you would receive whatever the system default type was (for example: on a 16 bit system an int would consist of 16 bits; on a 32 bit system and it would consist of 32 bits; 64 on a 64, etc).  The C language provides these types (on some systems, but not universally I believe) to explicitly state your desired type.
0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
Anti-Virus Apps

From novice to tech pro — start learning today.