Close

Moonlighting as a PRNG

A project log for Pisano-carry Checksum algorithm

Add X to Y and Y to X, says the song. And carry on.

Yann Guidon / YGDESYann Guidon / YGDES 04/21/2021 at 02:500 Comments

The previous logs Two hairy orbits and How to deal with black holes have analysed the checksum in a "freewheeling" configuration, where the input data is always 0, to check the behaviour and ensure the output keeps changing despite the absence/nullity of the input. In fact this amounts to observing the behaviour of a PRNG (Pseudo Random Number generator) that will then be perturbed by incoming data.

This Checksum/PRNG duality is already well known, in particular with the CRC/LFSR duality, so the only surprise was to discover the topology of the orbits of the PRNG equivalent of the algorithm.

Thus I can already state the PRNG behaviour of the algorithm, as it was totally mapped in the log Two hairy orbits. Starting from state (1,0,0) for example, we already know the period, which is about 1/4th of the available entropy. It's not stellar but already a huge and unexpected win, considering the relatively poor 1.5×2¹⁶ of the version without carry, otherwise called Pisano period. The carry changes everything !

I have not studied the distribution of these values but I know they are not to be trusted for any statistically-relevant applications. It's practical if you need to perform some fake stuff on your Arduino or create some crude noise but even this might sound weird. Just like a LFSR, it has the natural tendency of making sequences of increasing numbers so the spectrum will not be flat. I'll have to make a Web Audio demo !

Of course, if you need something better, you can use a LFSR to disturb the input data, or XOR the output. Make sure the LFSR shifts right/down to prevent "interference patterns" with the Pisano/Fibonacci structure, which tends to shift bits left/up. The combined generators with their distinct characteristics would likely create a smoother output with little effort, and the period will be CRC's period  (2^n)-1 times PRNG's period ( 2³¹+2¹⁵-1), assuming you draw 1 bit of CRC per cycle (yet use the whole state).

I tend to favor the configuration where the LFSR disturbs the Fibonacci Checksum, because a simple XOR of both generators might not mix things well enough. Disturbing the LFSR with the Fibonacci generator might not work well either because the LFSR has the forbidden state of 0 and takes longer to compute more than 1 bit (unless you allocate a large table). The chosen configuration is suitable if you need to draw numbers here and there, for example in your Arduino program, and using only 16 bits (X or Y) will reduce intra-word correlations. Of course, if you have an unused ADC input, it can be used as a source of noise or entropy.

If you need huge amounts of fast values with crazy long periods, you can use "Mersenne twisters" but that requires a larger amount of data and code.

Otherwise, I have provided an example C program: prng.c where a LFSR32 disturbs the checksum, and the results speak for themselves: only one bit from the LFSR is generated but 16 bits disturb the checksum, which neatly scrambles the bits, removing the stripe patterns of the LFSR.

CRC32 states :                      Checksum scrambled output
* ** * *    * *   *    ***     * -  ***   ***  *    
* ** ***  **** **  *  ****       -   ********    *  
 * ** ***  **** **  *  ****      -   *    ***  * ** 
  * ** ***  **** **  *  ****     -    * ****** ***  
   * ** ***  **** **  *  ****    -  * *** *  * * *  
    * ** ***  **** **  *  ****   -       * **       
     * ** ***  **** **  *  ****  - *    ** ** * *** 
      * ** ***  **** **  *  **** -  *** * *  ** * * 
*** **  ** * ** *****        *** - ***  * ***  ***  
*  ** **** *  **********  *   ** -  ***  **         
* *      * *   * *****  * **   * - *   ** **** ***  
* **** **  *      **** * ****    - *  *** **  ***** 
 * **** **  *      **** * ****   -  *  ***   ** * * 
  * **** **  *      **** * ****  - ** *   * * **  * 
   * **** **  *      **** * **** -    *  * **   *   
***  **  **    **       **** *** - *** *  ** *** ** 
*  **** *   *    *    ** * ** ** -  **** ***** ***  
* *   * ******  * *   * *   ** * -   *  ** **  **** 
* ****  **   ** ** *  *  **  **  -           **  ** 
 * ****  **   ** ** *  *  **  ** - **** *  ** *** * 
**    * *   *  *  ** **** ***  * -  * *** *** *** * 
*   **  ******     **   ******   -   *    * *    *  
 *   **  ******     **   ******  -  **  **  **  *   
  *   **  ******     **   ****** - *  *  *** *      
******    *  ***          ****** - ****  ******* ** 
*  *  *** * * **      **  ****** - *    ****  ** *  
* *  *   ** ** *      * * ****** -  ****    * ***** 
* *******   ***       *  ******* - ****** **    * * 
* **  *  ********     *    ***** -  *** **** *  * * 
* ** *  *    *** *    *   * **** - **** *** *       
* ** ******** **  *   *   ** *** -   * **  **  * *  
* ** **  *   * *   *  *   *** ** -       *  *    *  
* ** ** *  ** *     * *   **** * -  *     *  ** *   
* ** ** **** * **    **   *****  -  *  *  ** **  ** 
 * ** ** **** * **    **   ***** -    *    * **** * 

The computation step is easy :

#define CRC32_POLY_REV (0xEDB88320UL)

...

  uint32_t s, LFSR = 42, t, X=1, Y=0, C=0;

...

    // LFSR32 step
    s= 0- (LFSR & 1); // extend the LSB
    LFSR>>=1;
    LFSR^= s & CRC32_POLY_REV;

    // Pisano-Carry step
    t = X + Y + C;    Y = X ^ (uint16_t)LFSR;
    C = t >> 16;      X = t & 0xFFFF;

I'll let you play with it.

Discussions