IvanM - Apr 20, 2010 - 06:16 PM Post subject: Efficient pseudorandom MLS number generator 1.625 cycle/bit Two years ago I posted very fast pseudorandom number generator. It is based on MLS generator - shift register with feedback. It is faster than other implementation as it calulates 8 random bits at once. I've stored shift register in GPIOR registers as they offered faster acces, but it can be rewritten to use RAM. I have version with 15 bit feedback register (periode 32767, [15 14] polynome) and 23 bit register (periode 8,388,607 [23 14] polynome).31 bit version can be written with minor mods, but I did not need such long periode. Each length supports 8 bits and 16 bit output. Size and timing for 15 bit register (including C call): 8 bit rnd, 26 bytes 19 cycles 16 bit rnd 40 bytes 26 cycles Size and timing for 23 bit register (including C call): 8 bit rnd, 30 bytes 21 cycles 16 bit rnd, 44 bytes 28 cycles actual calculation takes 7 cycles per output byte in all 4 cases, rest is call overhead, so it can be optimized if more random bytes is needed at once. Asm routine was written following Rowley Crossworks register convention. Note1: shift registers has to be initialized with seed >1 as bit 0 is not used. Note2: to make periode practically infinite, occasionally alter shift reg. bits with bit 0 of ADC result (1 bit is enough) C usage example: unsigned int rnd16(void); unsigned int w[200]; GPIOR0=2;GPIOR1=0; // initialize seed for (i=1;i<200;i=++) w[i]=rnd16(); Enjoy, Ivan Code: ;RND.asm ; Pseudo Random Number Generator functions 8/16 bit 15/23 bit Maximum Lengts Sequences ; (c) Ivan Mellen, Oct 2008 ; imellen at embeddedsignals dot com ; C interface ;unsigned char rnd8(void); // 8 bit rnd, 26 bytes 19 cycles [15 14] MLS ;unsigned int rnd16(void); //16 bit rnd 40 bytes 26 cycles [15 14] MLS ;unsigned char rnd8_23(void); // 8 bit rnd, 30 bytes 21 cycles [23 14] MLS ;unsigned int rnd16_23(void); //16 bit rnd, 44 bytes 28 cycles [23 14] MLS ; Crossworks C /ASM interface: ; R27 (and R26 for int) input / output from function ; asm fun can use R20-27,R0-1, R30-31 #include ; Go to code section. code even ;------------------------------------------------------------------- ;unsigned char rnd8(void); //8 bit rnd, 26 bytes 19 cycles (7c iteration) [15 14] MLS ; periode: 32,767 (4096 unique bytes, remaining 7 iteration shifted version) public _rnd8 _rnd8 proc in r27,17 ;L reg17 is L in r26,18 ;H reg 18 is H ldi r24,0 ;this will save cycles in multi byte version mov r23,r27 ;AL=L mov r22,r26 ;AH=H lsl r23 rol r22 ;AH:AL <<1 eor r26,r22 ;AH=AH eor H lsl r26; C<-AH.7, AH<<1 new L byte adc r27,r24 ;L.0 <-C out 17,r26 ; new L.1-7 is eor product0-6 (msb eor is in r27.0) out 18,r27 ;old L is new H also return value (top 8 bits HL) ret endproc ;------------------------------------------------------------------- ;unsigned int rnd16(void); //16 bit rnd 40 bytes 26 cycles (14c iteration) [15 14] MLS ; periode: 32767 (2048 unique words, remaining 15 iterations shifted version) public _rnd16 _rnd16 proc in r27,17 ;L reg17 is L in r26,18 ;H reg 18 is H ldi r24,0 ;this will save cycles in multi byte version mov r23,r27 ;AL=L mov r22,r26 ;AH=H lsl r23 rol r22 ;AH:AL <<1 eor r26,r22;AH=AH eor H lsl r26; C<-AH.7, AH<<1 new L byte new L adc r27,r24 ;L.0 <-C ;first 8 bits new H 1st return value (high part) ; get 2nd byte mov r23,r26 ;AL=L mov r22,r27 ;AH=H lsl r23 rol r22 ;AH:AL <<1 eor r27,r22 ;AH=AH eor H lsl r27; C<-AH.7, AH<<1 new L byte adc r26,r24 ;L.0 <-C ;first 8 bits new H 2nd return value (low part) out 17,r27 ; new L.1-7 is eor product0-6 (msb eor is in r26.0) out 18,r26 ;old L is new H also return value (top 8 bits HL) ret endproc ;------------------------------------------------------------------- ;unsigned char rnd8_23(void); //8 bit rnd, 30 bytes 21 cycles (7c iteration) [23 14] MLS ; periode: 8,388,607 (1,0485,576 unique bytes, remaining 7 iteration shifted version) public _rnd8_23 _rnd8_23 proc in r26,17 ;L GPIOR0 is L in r27,18 ;H GPIOR1 is M in r25,19 ;H GPIOR2 is H ldi r24,0 ;this will save cycles in multi byte version mov r20,r26 ;L2=L mov r21,r27 ;M2=M lsl r20 rol r21 ;M2:L2 <<1 eor r21,r25 ;M2 = M2 eor H lsl r21; C<-M2.7, M2<<1 new L byte adc r26,r24 ;L.0 <-C new M byte ; M is new H byte (also output) out 17,r21 ; new L.1-7 is eor product6-0 (msb eor is in r27.0) out 18,r26 ;old L + bit 0 from eor bit 7 is new M out 19,r27 ;old M is new H also return value (top 8 bits HML) ret endproc ;------------------------------------------------------------------- ;unsigned int rnd16_23(void); //16 bit rnd, 44 bytes 28 cycles (14c iteration) [23 14] MLS ; periode: 8,388,607 (524288 unique words, remaining 15 iteration shifted version) public _rnd16_23 _rnd16_23 proc in r26,17 ;L GPIOR0 is L in r25,18 ;H GPIOR1 is M in r27,19 ;H GPIOR2 is H ldi r24,0 ;this will save cycles in multi byte version mov r20,r26 ;L2=L mov r21,r25 ;M2=M lsl r20 rol r21 ;M2:L2 <<1 eor r27,r21 ;H = M2 eor H lsl r27; C<-H.7, H<<1 new L byte 27 adc r26,r24 ;L.0 <-C new M byte 26 ; M is new H byte 25 ; get 2nd byte ----------------- mov r20,r27 ;L2=L mov r21,r26 ;M2=M lsl r20 rol r21 ;M2:L2 <<1 eor r25,r21 ;H = M2 eor H lsl r25; C<-H.7, H<<1 new L byte 25 adc r27,r24 ;L.0 <-C new M byte 27(also output) ; M is new H byte 26(also output) out 17,r25 ; new L.1-7 is eor product6-0 (msb eor is in r27.0) out 18,r27 ;old L + bit 0 from eor bit 7 is new M out 19,r26 ;old M is new H ret endproc ============================================================================================