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 ); }
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 ); }
"I belive this function is in many ways better than the C51 library rand() function - it is compact, fast,..." And, on a Triscend E5, you could implement it in the configurable logic - making it really compact (no code!) and fast!
"And, on a Triscend E5, you could implement it in the configurable logic - making it really compact (no code!) and fast!" Ok ok ok ok, I'll buy one! Stefan
Here is a revised version of my random number generator. It works in the same way as the one described above, but is designed to keep its LFSR in xdata (and is therefore somewhat slower). This generator returns a new 16-bit value for each call. Because 16 is not a factor of (2^32)-1, the generator is of maximum length. A list of alternative tap masks is provided. I have not tested these, but each one should cause a different sequence to be generated.
// // Masks for 32-bit galios LFSR maximum run length generator // // 32 bits, 16 taps: 44 // 32 31 29 28 27 25 24 23 21 19 17 14 10 6 4 2 // 32 31 29 27 26 25 24 22 20 15 13 6 4 3 2 1 // 32 31 29 27 26 25 24 22 16 15 13 11 10 9 8 6 // 32 31 29 27 25 24 22 20 16 15 13 11 9 8 6 4 // 32 31 29 27 24 23 21 19 18 14 12 10 9 6 4 1 // 32 31 29 27 24 23 21 19 16 15 13 11 10 6 4 1 // 32 31 29 27 24 23 21 19 16 15 13 10 8 7 5 2 // 32 31 29 27 24 23 21 19 16 15 13 9 8 7 5 1 // 32 31 29 27 24 23 21 19 16 15 12 10 8 7 4 2 // 32 31 29 27 24 23 19 17 16 15 13 11 8 7 3 1 // 32 31 29 26 24 23 21 18 16 15 13 10 9 7 5 1 // 32 31 29 26 24 23 21 18 16 15 13 10 8 7 5 1 // 32 31 29 26 24 23 21 18 16 15 13 10 8 6 5 3 // 32 31 29 26 24 23 21 18 16 15 13 10 8 6 4 2 // 32 31 29 26 24 23 21 18 16 14 12 10 8 6 4 2 // 32 31 28 27 24 23 20 19 18 15 12 11 8 7 3 2 // 32 31 28 27 24 23 20 19 17 15 12 10 9 7 4 2 // 32 31 28 27 24 23 20 19 16 15 13 11 9 6 4 2 // 32 31 28 27 24 23 20 19 16 15 12 11 8 7 5 3 // 32 31 28 27 24 23 20 19 14 13 10 9 6 5 2 1 // 32 31 28 27 23 20 19 15 12 11 10 8 7 4 3 2 // 32 31 28 27 25 23 20 18 16 15 12 11 9 7 4 2 // 32 30 29 26 25 23 20 19 16 14 13 10 9 7 4 3 // 32 30 29 26 25 22 21 18 17 15 12 11 8 7 4 3 // 32 30 28 26 24 22 20 18 16 14 12 10 6 4 3 1 // 32 29 28 27 26 19 18 17 16 13 12 11 10 3 2 1 // 32 29 28 26 25 21 20 18 17 13 12 10 9 6 5 2 // 32 29 28 25 24 21 20 17 16 13 12 9 8 6 4 2 // 32 29 28 25 24 21 20 15 14 11 10 7 6 3 2 1 // 32 28 27 26 25 20 19 18 17 12 11 10 9 4 3 2 // 32 28 25 20 17 15 14 13 11 10 8 7 6 5 3 2 // 32 28 24 23 22 21 19 18 17 12 8 7 5 4 3 1 // 32 28 24 20 16 15 14 13 11 10 9 7 6 5 4 3 // 32 28 24 20 16 15 14 12 11 10 8 7 6 4 3 2 // 32 27 26 25 24 23 22 21 20 11 10 9 8 7 5 2 // 32 27 26 25 24 21 20 19 18 11 10 9 8 6 5 3 // 32 27 26 25 24 20 19 17 16 11 10 9 8 4 3 1 // 32 27 26 25 24 19 18 17 16 11 10 9 8 7 6 2 // 32 27 25 19 17 14 12 11 10 9 8 6 4 3 2 1 // 32 26 24 23 22 21 20 19 17 12 10 7 6 5 3 1 // 32 23 22 21 20 19 18 17 16 12 8 7 6 4 3 1 // 32 23 22 21 20 19 18 17 16 9 7 6 5 4 3 1 // 32 19 18 17 16 15 14 13 12 11 10 9 8 7 5 1 // 32 17 16 15 14 13 12 11 10 9 8 7 6 5 4 1 // // 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 // /***************************************************************************** * * Random 16 * * Trigger: Call by any process. * * Input: None * * Output: returns a 16-bit pseudo random number. * * Function: Updates ready for next random number to be generated. * *****************************************************************************/ #pragma ASM $REGUSE rand16( PSW, DPH, DPL, A, B ) #pragma ENDASM static xdata unsigned long int lfsr = 0xA5871234; unsigned int rand16() large { #pragma ASM ; MOV B,#16 ; ; ?random_loop: ; ; CLR C ; MOV DPTR,#lfsr ; MOVX A,@DPTR ; RRC A ; MOVX @DPTR,A ; INC DPTR ; MOVX A,@DPTR ; RRC A ; MOVX @DPTR,A ; INC DPTR ; MOVX A,@DPTR ; RRC A ; MOVX @DPTR,A ; INC DPTR ; MOVX A,@DPTR ; RRC A ; MOVX @DPTR,A ; ; JNC ?random_x ; ; MOV DPTR,#lfsr ; MOVX A,@DPTR ; XRL A,#0xCC ; MOVX @DPTR,A ; INC DPTR ; MOVX A,@DPTR ; XRL A,#0x4C ; MOVX @DPTR,A ; INC DPTR ; MOVX A,@DPTR ; XRL A,#0x4E ; MOVX @DPTR,A ; INC DPTR ; MOVX A,@DPTR ; XRL A,#0xCE ; MOVX @DPTR,A ; INC DPTR ; ; ?random_x: ; ; DJNZ B,?random_loop ; ; #pragma ENDASM return( (unsigned int) lfsr ); } void rand16_init( unsigned int seed ) large { lfsr = 0xA5A50000L | seed; rand16(); // Stir the seed into the lfsr. }