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

LFSR.txt
###### 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.

Commented:
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;

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,
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
}

system("PAUSE");					//makes a call to the system to run the executable "PAUSE"

}

/* 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)
}
``````
0
Author 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
Commented:
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