# cpct_getRandom_glfsr16

Pseudo-random number generator that uses a 16-bits Galois Linear-Feedback Shift Register

Summary

cpct_getRandom_glfsr16 | Pseudo-random number generator that uses a 16-bits Galois Linear-Feedback Shift Register
Functions |
cpct_getRandom_glfsr16_u8 | Return a pseudo-random byte using Galois Linear-Feedback Shift Register (G-LFSR) method, with a 16-bits state register.
cpct_getRandom_glfsr16_u16 | Return a pseudo-random 16-bits value using Galois Linear-Feedback Shift Register (G-LFSR) method, with a 16-bits state register.

### Functions

### cpct_getRandom_glfsr16_u8

Return a pseudo-random byte using Galois Linear-Feedback Shift Register (G-LFSR) method, with a 16-bits state register.

#### C Definition

u8 cpct_getRandom_glfsr16_u8 ();

#### Assembly call (Input parameter on L)

>     call cpct_getRandom_glfsr16_u8_asm

#### Return value (Assembly calls, return L=A=random 8-bits, HL=random 16-bits)

<u8> | Next 8-bits pseudo-random value.

#### Known limitations

- This function will not work from a ROM, as it uses self-modifying code.
- Seed (machine state) must never be zero.
- Returned value using all 16 bits (u16) will never be 0, so it is advisable to use returned value-1 as final random number. This limitation does not affect u8 return values.
- Although the whole sequence has a period of 65535 numbers without repetition, the way numbers are traversed is quite predictable. This function is not recommended when good quality random numbers are required. However, a combination with other functions may yield much better results.

#### Details

This function implements a Galois Linear-Feedback Shift Register with a 16 bits state. This Shift Register does produce 65535 16-bits values without repetition, then cycles again. That is, it is like having the 65536 (excluding 0) possible 16-bits values ordered in a pseudo-random manner, and getting each one at a time.

The implementation of the Shift Register is based on some specific 16-bits values denominated TAPS (Check GLFSR16_TAPSET). These values are bit-masks that select some bits to implement a linear polynomial shifting operation. Depending on the bits selected in the bit-mask, the polynomial implemented changes. There exists 1024 different polynomials that mathematically ensure a 65535-value traversal without repetition. Any other polynomial will have a shorter period. These 1024 TAPSETs that implement the polynomials with full 16-bits traversals are defined in GLFSR16_TAPSET enumeration. Use cpct_setTaps_glfsr16 with any of the these tapsets to select your desired traversal.

#### Use example

Basic use of this function does not require any kind of set-up, just calling the function each time you want a pseudo-random number

>     // Get next pseudo-random 8-bits number
>     u8 getRandomNumber() {
>        return cpct_getRandom_glfsr16_u8();
>     }

However, this will return always the same sequence, in the same order. You might consider setting the staring seed at some initialization point,

>     // Count loops until user presses a key
>     u16 countUntilUserPressesAKey() {
>        u16 loops;
>        do {
>           loops++;
>           cpct_scanKeyboard();
>        } while ( !cpct_isAnyKeyPressed() );

>        return loops;
>     }

>     // Initialization code (set initial seed)
>     u16 loops = countUntilUserPressesAKey();
>     cpct_setSeed_glfsr16(loops);

This code will set the starting state of the internal shift register to a value depending on when the user has pressed a key, which will randomize the starting point in the 65535-values sequence that the pseudo-random generator produces. However, take into account that the 65535-value traversal will be in the same order, unless you changed it calling cpct_setTaps_glfsr16.

#### Destroyed Register values

AF, HL

#### Required memory

22 bytes

#### Time Measures

>       Case | microSecs(us) | CPU Cycles
>     -------------------------------------
>      Best  |      19       |     76
>     -------------------------------------
>      Worst |      26       |    104
>     -------------------------------------

#### Credits and References

This function is based on Galois Linear-Feedback Shift Register method.

- On Linear-Feedback Shift Registers: https://es.wikipedia.org/wiki/LFSR
- Theory on LSFRs: http://web.archive.org/web/20010605005727/homepage.mac.com/afj/lfsr.html

### cpct_getRandom_glfsr16_u16

Return a pseudo-random 16-bits value using Galois Linear-Feedback Shift Register (G-LFSR) method, with a 16-bits state register.

#### C Definition

u16 cpct_getRandom_glfsr16_u16 ();

#### Assembly call (Input parameter on L)

>     call cpct_getRandom_glfsr16_u16_asm

#### Return value (Assembly calls, return HL=random 16-bits)

<u16> | Next 16-bits pseudo-random value.

#### Consult for more information

cpct_getRandom_glfsr16_u8, which is the same function.

#### Details

This function is exactly the same as cpct_getRandom_glfsr16_u8. Both functions share the 100% of their code. The only difference is the return type: cpct_getRandom_glfsr16_u8 returns a u8 (in L register) and cpct_getRandom_glfsr16_u16 returns a u16 (in HL register). So, from C perspective, same code is called, and 16 bits are returned, but sometimes only 8 bits are used (when cpct_getRandom_glfsr16_u8). From assembly point of view, you call the same function, and may decide to use return in L (8 bits) or in HL (16 bits) at your will.

unsigned char (u8 = unsigned 8-bits, 1 byte )
Return a pseudo-random byte using Galois Linear-Feedback Shift Register (G-LFSR) method, with a 16-bits state register.
unsigned int (u16 = unsigned 16-bits, 2 bytes)
This enumeration hold sets of valid TAPS for generating complete pseudo-random sequences using 16-bits Galois LFSR method.
Returns a pseudo-random byte uniformly distributed using fast method (33*Seed mod 257)
Return a pseudo-random 16-bits value using Galois Linear-Feedback Shift Register (G-LFSR) method, with a 16-bits state register.
Close