Fast 32-Bit LFSR

rand32() is a pseudo random number generator based on a galois LFSR generator. It is a fuction that others may find useful. For details on how it works and alternative tap lists see: http://www.newwaveinstruments.com/resources/articles/m_sequence_linear_feedback_shift_register_lfsr.htm#Table%20of%20M-Sequence%20Feedback%20Taps

I belive this function is in many ways better than the C51 library rand() function - it is compact, fast, easily modified to produce different sequences of a variety of lengths and maximum run length is garanteed (test!). The run length will be (2^n)-1 where n is the number of bits in the LFSR.

This generator has masks for the 31-bit LFSR. To use alternative tap lists write out the contents of a 32-bit word, put a "1" on the bit corresponding to a tap list entry and a 0 otherwise; shift all the bits one to the right and then split in to 4 8-bit masks and place these in the code. Some tap lists have been worked out already and those up to 31 bits have been tested. Many, many alternative tap lists are given by the web-site mentioned above.

rand32() returns a long from which the required number of bits may be taken. Always take the least significant bits. rand32() should always be called with a parameter that indicates the number of required iterations, this number should always be greater than or equal to the required number of bits. It is a good idea to avoid a parameter value that is a factor of the maximum run length of the generator.

The code is easily modified to provide a different seed value (anything other than 0 - assigned to the variable lfsr) or to return a different variable (eg a 16-bit int). If always returning a 16-bit value, a 32-bit LFSR may be implemented and the number of iterations fixed at 16.

#include <REG52.H>

//  Masks for 3-bit galios LFSR maximum run length generator
//
//  [3, 1]
//
//    3                   2                   1                   0
//  1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0
//  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1
//
//  0 0 0 0 0 0 0 0  = 0x00
//  0 0 0 0 0 0 0 0  = 0x00
//  0 0 0 0 0 0 0 0  = 0x00
//  0 0 0 0 0 0 0 0  = 0x05
//
//  Masks for 8-bit galios LFSR maximum run length generator
//
//  [8, 7, 6, 1]
//
//    3                   2                   1                   0
//  1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0
//  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1
//
//  0 0 0 0 0 0 0 0  = 0x00
//  0 0 0 0 0 0 0 0  = 0x00
//  0 0 0 0 0 0 0 0  = 0x00
//  0 0 0 0 0 0 0 0  = 0xE1
//
//  Masks for 10-bit galios LFSR maximum run length generator
//
//  [10, 9, 8, 7, 5, 4]
//
//    3                   2                   1                   0
//  1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0
//  0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 1 1 1 0 1 1 0 0 0
//
//  0 0 0 0 0 0 0 0  = 0x00
//  0 0 0 0 0 0 0 0  = 0x00
//  0 0 0 0 0 0 1 1  = 0x03
//  1 1 0 1 1 0 0 0  = 0xD8
//
//  Masks for 31-bit galios LFSR maximum run length generator
//
//  [31, 29, 27, 24, 23, 21, 19, 16, 15, 13, 11, 9, 7, 5, 3, 1]
//
//    3                   2                   1                   0
//  1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0
//  0 1 0 1 0 1 0 0 1 1 0 1 0 1 0 0 1 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
//
//  0 1 0 1 0 1 0 0  = 0x54
//  1 1 0 1 0 1 0 0  = 0xD4
//  1 1 0 1 0 1 0 1  = 0xD5
//  0 1 0 1 0 1 0 1  = 0x55
//
//  Masks for 3-bit galios LFSR maximum run length generator
//
//  NB (2^32)-1 has prime factors: 3,5,17,257,65537
//
//  [32, 31, 28, 27, 23, 20, 19, 15, 12, 11, 10, 8, 7, 4, 3, 2]
//
//    3                   2                   1                   0
//  1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0 9 8 7 6 5 4 3 2 1 0
//  1 1 0 0 1 1 0 0 0 1 0 0 1 1 0 0 0 1 0 0 1 1 1 0 1 1 0 0 1 1 1 0
//
//
//  1 1 0 0 1 1 0 0  = 0xCC
//  0 1 0 0 1 1 0 0  = 0x4C
//  0 1 0 0 1 1 1 0  = 0x4E
//  1 1 0 0 1 1 1 0  = 0xCE
//

#pragma ASM

$REGUSE _rand32( PSW, A, R4, R5, R6, R7 )

#pragma ENDASM

static data unsigned long int	lfsr = 0x0001;

unsigned long int rand32( unsigned char n )
{
    n = n;                          // Supress warning.

    #pragma ASM
                                    ;
        MOV     A,R7                ;
        MOV     R0,A                ;
                                    ;
?random_loop:                       ;
                                    ;
        CLR     C                   ;
        MOV     Acc,lfsr+0          ;
        RRC     A                   ;
        MOV     lfsr+0,A            ;
        MOV     Acc,lfsr+1          ;
        RRC     A                   ;
        MOV     lfsr+1,A            ;
        MOV     Acc,lfsr+2          ;
        RRC     A                   ;
        MOV     lfsr+2,A            ;
        MOV     Acc,lfsr+3          ;
        RRC     A                   ;
        MOV     lfsr+3,A            ;
                                    ;
        JNC     ?random_x           ;
                                    ;
        XRL     lfsr+0,#0x54        ;
        XRL     lfsr+1,#0xD4        ;
        XRL     lfsr+2,#0xD5        ;
        XRL     lfsr+3,#0x55        ;
                                    ;
?random_x:                          ;
                                    ;
        DJNZ	R0,?random_loop     ;
                                    ;
    #pragma ENDASM

    return( lfsr );
}

A test harness:

extern unsigned long int rand32( unsigned char n );

main()
{
    data  unsigned long int loop;

    data  unsigned long int v,target;

    xdata unsigned long int a[256];

    loop = 256;

    do
    {

         a[ loop ] = 0;

    } while( --loop != 0 );

    target = rand32( 1 );

    loop = 0;

    do
    {

        v = rand32( 1 );

        a[ v % 256 ]++;

        if( v == target )
        {
            target = v;
        }

    } while( ++loop != 0 );
}

You can test for maximum run length in the simulator by placing a break point on "target = v;" and noting the value of loop - it will be one less than the run length. Array a should indicate that the values of the 8 least significant bits were evenly distributed.