Linear feedback shift register

Posted on 2010-04-07
Medium Priority
Last Modified: 2013-11-16
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
Question by:oggiemc
  • 2

Expert Comment

ID: 30048445
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

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


Author Comment

ID: 30051777
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!!

Accepted Solution

ReedNewman earned 2000 total points
ID: 30131039

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.

Featured Post

Free Tool: ZipGrep

ZipGrep is a utility that can list and search zip (.war, .ear, .jar, etc) archives for text patterns, without the need to extract the archive's contents.

One of a set of tools we're offering as a way to say thank you for being a part of the community.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

Join & Write a Comment

An introduction to the wonderful sport of Scam Baiting.  Learn how to help fight scammers by beating them at their own game. This great pass time helps the world, while providing an endless source of entertainment. Enjoy!
The well known Cerber ransomware continues to spread this summer through spear phishing email campaigns targeting enterprises. Learn how it easily bypasses traditional defenses - and what you can do to protect your data.
Video by: Grant
The goal of this video is to provide viewers with basic examples to understand and use for-loops in the C programming language.
Email security requires an ever evolving service that stays up to date with counter-evolving threats. The Email Laundry perform Research and Development to ensure their email security service evolves faster than cyber criminals. We apply our Threat…

627 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question