TipsAndTriks/avr/random.txt

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 <avr.h>

 ; 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
============================================================================================