;======================================================================
; Example of a "good" pseudo random number generator. Has extremely
;  long cycle. (2^55 - 1) Uses Additive Congruential Method. (linear
;  feedback shift register.) See Knuth for details...

; by Richard Mulder, 2:281/500.3
;                    v942519@si.hhs.nl
; - TASM with simplified segments, 286 code
; - REQUIRES VGA -
;======================================================================
.MODEL      TINY            ; .COM-file,
.CODE                       ;  so "tlink /t random" !
.286                        ; for SHL <reg>, 8
            ORG     100h

;======================================================================
Start:
;======================================================================
    ; Startup code
    CALL    RndInit         ; Init the generator

    MOV     AX, 0013h       ; Mode 13h, 320x200x255
    INT     10h             ; Vid Fn Set Video Mode

    MOV     AX, 0A000h
    MOV     ES, AX          ; ES    = VidSeg

PlotLoop:
    ; Plot a random pixel with a random (EGA) color
    MOV     AX, 64000       ; Range = 0..63999
    CALL    RndRanged

    MOV     DI, AX          ; DI    = pixel position

    MOV     AX, 16          ; Range = 0..15
    CALL    RndRanged       ; AX    = pixel color

    STOSB                   ; ES:DI < AX

    MOV     AH, 1
    INT     16h             ; Keyboard Fn Check Keyboard Buffer
    JZ      PlotLoop        ; UNTIL KeyPressed;

    ; Cleanup code
    MOV     AH, 0           ;
    INT     16h             ; Keyboard Fn Read Char from Buffer

    MOV     AX, 0003h       ; Mode 03h, 80x25 Text
    INT     10h             ; Vid Fn Set Video Mode

    MOV     AX, 4C00h       ; Errorlevel 0
    INT     21h             ; Dos Fn Exit to OS

;======================================================================
RndInit:
;======================================================================
; initializes the random number generator
; In        None
; Out       None
; Destroyed AX, BX, CX, DX, SI, DI
;----------------------------------------------------------------------
    ; First seed comes from clock. Remove this to get repeatable series.
    MOV AH, 0
    INT 1Ah                 ; Clock Fn Get Time of Day (also works on XT!)
    MOV SeedArr[0], DX      ; First seed is clock count

    MOV DI, 1               ; DI    = Ptr
    MOV SI, 0               ; SI    = Ptr - 1

FillArrLoop:
    ; We fill the seed array with some "randomlooking" numbers.
    ; (This is a LINEAR Congruential generator (introduced by D.Lehmer))
    MOV AX, SeedArr[SI]     ; AX    = SeedArr[SI]
    MOV BX, Multiplier
    MUL BX                  ; DX:AX = AX * Multiplier
    INC AX                  ; DX:AX = AX * Multiplier + 1
    MOV SeedArr[DI], AX     ; AX    = above MOD 65535
    INC SI
    INC DI                  ; Next element
    CMP DI, 55
    JNE FillArrLoop         ; Done all elements yet?

    ; We start at a random (aHEM) position in the seed array
    MOV SeedPtr, 42         ; DON'T PANIC! :)
    RET

;======================================================================
RndRanged:
;======================================================================
; generates a pseudo-random number
; In        AX = Range of number
; Out       AX = number (0..Range-1)
; Destroyed AX
;----------------------------------------------------------------------
    ; Save some registers
    PUSH    SI              ;
    PUSH    DX              ; Ofcourse, with some juggling we
    PUSH    CX              ;  don't need SI, but it's not
    PUSH    BX              ;  worth it. IMHO.
    PUSH    AX              ; Store range until we need it

    ; -- SeedPtr := (SeedPtr + 1) MOD 55;
    MOV BX, SeedPtr
    INC BX
    CMP BX, 55              ; Yes, a jump, so the cache is flushed
    JNE SeedPtrNoWrap       ;  but I avoid a DIV this way.
SeedPtrWrap:
    XOR BX, BX
SeedPtrNoWrap:
    MOV SeedPtr, BX         ; BX    = SeedPtr

    ; -- SeedArr[SeedPtr] := SeedArr[(SeedPtr + 23) MOD 55] +
    ; --                    SeedArr[(SeedPtr + 54) MOD 55]) MOD MaxWord;

    ; Get seed from first tap point
    MOV AX, BX              ; First tap point:
    ADD AX, 23              ;  SeedArr[(SeedPtr + 23) MOD 55]
    MOV DX, 55
    DIV DL
    SHR AX, 8               ; Or, in other words:
    MOV SI, AX              ;  MOV SI, AH

    MOV CX, SeedArr[SI]     ; Tap from first point

    ; Get seed from second tap point
    MOV AX, BX              ; Second tap point:
    ADD AX, 54              ;  SeedArr[(SeedPtr + 54) MOD 55]
    MOV DX, 55
    DIV DL
    SHR AX, 8               ; Or, in other words:
    MOV SI, AX              ;  MOV SI, AH

; _Algorithms_ by Robert Sedgewick, ISBN 0-201-066673-4 says XOR should be
; better. It aint. (There's also a C++ version of this book)
;   XOR CX, SeedArr[SI]
    ADD CX, SeedArr[SI]     ; Add the two
    MOV SeedArr[BX], CX     ; And make that a new seed

    ; -- number := (SeedArr[SeedPtr] * range) DIV MaxWord;
    POP AX                  ; Get the desired range
    MUL CX                  ; DX:AX = range * new SeedArr[SeedPtr]

    ; Therefore DX is a pseudorandom number within 0..range-1. TaDAAA!
    MOV AX, DX

    ; Restore some registers
    POP BX
    POP CX
    POP DX
    POP SI
    RET

;======================================================================
Multiplier  EQU 15821       ; wordsized magic multiplier

SeedArr     DW  55 DUP (?)  ; Array of seeds, [0..54]
SeedPtr     DW  ?           ; Ptr to current seed

; Index registers are word-sizes. ie. it is illegal to:
;     MOV BL, SeedPtr; MOV AX, SeedArr[BL]
; So, MOV BX, SeedPtr; MOV AX, SeedArr[BX].
; So SeedPtr is a word, even if its range is 0..55.

;======================================================================
    END Start

