Wiki: https://en.wikipedia.org/wiki/Linear-fe ... t_register
For example, consider a PRNG that generates 5 random numbers ...
Most PRNG's might produce output like: 1,4,3,2,4 (note it has two 4's, and never used the number 5)
However, the LFSR would produce something like: 1,4,3,2,5 (no duplicate numbers, and every number used once, and once only)
However, it only has this property (what's considered a "maximal LFSR") if it has a valid maximal mask to start with.
It has a fixed period.
Interestingly, the number 0 is never output, because that would break it (it would then continually output 0).
Please note this is not a cryptographic random number generator (it is quite clearly deterministic!), but can be combined with a CRNG.
______________________________________________
Code: Select all
;LINEAR FEEDBACK SHIFT REGISTER (LFSR)
; '// Based on source: https://github.com/23ars/projects/blob/master/assembly/nasm/lfsr/lfsr.asm
; '// Sample bitmasks: http://www.maximintegrated.com/en/app-notes/index.mvp/id/4400
; '// Ultimate bitmasks: https://users.ece.cmu.edu/~koopman/lfsr/index.html
; // Supports x86 + x64
(I've only provided one maximal mask for each bit-depth/degrees, but there are many others)
Code: Select all
; '// MASK DEGREES NUMBERS
; '#LFSR_MASK = $5 ;3 bit 7
; '#LFSR_MASK = $9 ;4 bit 15
; '#LFSR_MASK = $1D ;5 bit 31
; '#LFSR_MASK = $36 ;6 bit 63
; '#LFSR_MASK = $69 ;7 bit 127
; '#LFSR_MASK = $A6 ;8 bit 255
; '#LFSR_MASK = $17C ;9 bit 511
; '#LFSR_MASK = $32D ;10 bit 1023
; '#LFSR_MASK = $4F2 ;11 bit 2047
; '#LFSR_MASK = $D34 ;12 bit 4095
; '#LFSR_MASK = $1349 ;13 bit 8191
; '#LFSR_MASK = $2532 ;14 bit 16383
; '#LFSR_MASK = $6699 ;15 bit 32767
; '#LFSR_MASK = $8016 ;16 bit 65535
; '#LFSR_MASK = $12933 ;17 bit 131071
; '#LFSR_MASK = $2C93E ;18 bit 262143
; '#LFSR_MASK = $593CA ;19 bit 524287
; '#LFSR_MASK = $AFF95 ;20 bit 1048575
; '#LFSR_MASK = $12B6BC ;21 bit 2097151
; '#LFSR_MASK = $2E652E ;22 bit 4194303
; '#LFSR_MASK = $5373D6 ;23 bit 8388607
; '#LFSR_MASK = $9CCDAE ;24 bit 16777215 i7-4790K @4GHz:
; '#LFSR_MASK = $12BA74D ;25 bit 33554431 0.27secs
; '#LFSR_MASK = $36CD5A7 ;26 bit 67108863 0.54secs
; '#LFSR_MASK = $4E5D793 ;27 bit 134217727 1.01secs
; '#LFSR_MASK = $F5CDE95 ;28 bit 268435455 2.15secs
; '#LFSR_MASK = $1A4E6FF2 ;29 bit 536870911 4.30secs equiv to (pixels)...
; '#LFSR_MASK = $29D1E9EB ;30 bit 1073741823 8.66secs 32767x32767
; '#LFSR_MASK = $7A5BC2E3 ;31 bit 2147483647 17.25secs 46340x46340
; '#LFSR_MASK = $B4BCD35C ;32 bit 4294967295 34.45secs 65535x65535
;32-64bit:
; '#LFSR_MASK = $800000001C ;40bit
; '#LFSR_MASK = $80000000005B ;48bit
; '#LFSR_MASK = $800000000000000D ;64bit
Code: Select all
DisableDebugger
#LFSR_MASK = $9 ;4 bit (15 numbers to keep it simple for the demo)
Procedure.l LFSR(seed.l, mask.l) ;note this declaration is only compatible for 32bit, but easy enough to modify for 64
! mov eax, [p.v_seed]
! mov ecx, eax
! and ecx, 1
! shr eax, 1
! cmp ecx, 1
! jne end_lfsr
! mov ecx, [p.v_mask]
! xor eax, ecx
!end_lfsr:
;! and eax, $00FFFFFF ;Use this instruction to only return the last 8 bits (al). Comment-out to return the full 32bit result.
;_BUT_ the caller can't then use that as the next seed, so really the caller should be the one extracting the 8bits, not this func
ProcedureReturn
EndProcedure
seed.l = 1 ;you can set this to any valid value within the range of the bitmask, but not 0
For i = 1 To (15*2) ;to demonstrate 2 runs of our 15-number demo
seed = LFSR(seed, #LFSR_MASK) ;the seed is updated with each call
Debug Str(seed)
Next i