This is my re-discovery of the nicely-identified Linear feedback shift register type of PRNG, having seen a bit of its implementation elsewhere. Shift left, and if the high bit was set, EOR it with a worth to twiddle the decrease bits as the high ones are lost. The problem is that setting ‘seed’ to zero would merely trigger it to stay at zero. The excessive bit is all the time clear, so the EOR is rarely utilized. If we modify the algorithm to perform the EOR when the excessive bit is evident as an alternative, the pattern is misplaced and never all numbers are reached, regardless of which EOR worth is used (yes, I examined all 256 of them). This solved the problem of ‘seed’ being initially set to zero. However, the algorithm will nonetheless never output a zero itself. 00 and $80 will end in an output of $1d. We want these 2 values to provide distinctive outputs, so that all the 256 inputs will yield a novel output, conserving the total interval of 256 bytes intact.
This yields a sequence of all 256 8-bit values in pseudo-random, repeating order. The 256 completely different possible seeds you may give it would merely start the chain at a special point. To get a unique chain (essentially a special PRNG altogether), the value of the EOR must be changed. This gives sixteen possible PRNGs, each with 256 doable beginning seed factors. Thus, by specifying 2 bytes as the seed (one for the value of ‘seed’ and one for the which PRNG’s EOR worth to use), you possibly can have 4096 completely different chains of 256 numbers. To be a bit extra clever, a 12-bit seed might embrace the 8-bit ‘seed’ value and a 4-bit index into the desk of sixteen potential EOR values. Of course, that is all non-obligatory and you would just as properly hardcode the EOR instruction to one of many above values to get a consistent PRNG of interval 256 that’s seeded by a single 8-bit value, as in the above examples. This algorithm might be extended to sixteen or more bits with no problem, especially on architectures of that bit width. The 16-bit version has 2048 EOR values that work, and who knows what number of the higher ones have.
