6502.org • View topic - Random-number generation

View unanswered posts | View active topics

Board index » 6502.org Users Forum » Programming

All times are UTC

Random-number generation

Page 2 of 17

[ 245 posts ]

Go to page Previous 1, 2, 3, 4, 5 ... 17 Next

Previous topic | Next topic

Author

Message

Proxy

Post subject: Re: Random-number generation

Posted: Sat Jan 28, 2023 8:33 pm

Joined: Fri Aug 03, 2018 8:52 am
Posts: 746
Location: Germany

so far my go-to RNG has been a function that takes a 32-bit number, splits it into 4x 8-bit pointers that point to a predefined set of 256 values. a number is read from each pointer, Added together, XOR'd, and Added again, to get a final result. and then increments the 32-bit number by 1.
so it uses 4 bytes of Memory, and 256 bytes for the table+function (because the code of the function is used as part of the table, to save some memory)

Code:

.data
rng_ptr:    .res 4

.code
rng_func:
    .A8
    .I8
    LDX a:rng_ptr
    LDY a:rng_ptr + 1   ; Get Pointers 0 and 1
    
    LDA a:rng_func,X    ; Get a byte from the RNG Table (using Pointer 0)
    CLC
    ADC rng_func,Y      ; Add a byte from the RNG Table (using Pointer 1) to the Value
    LDX rng_ptr + 2
    LDY rng_ptr + 3     ; Get Pointers 2 and 3
    EOR a:rng_func,X    ; XOR the Value with a byte from the RNG Table (using Pointer 2)
    ADC rng_func,Y      ; And finally, Add a byte from the RNG Table (using Pointer 3) to the Value
    PHA                 ; Save the Output on the Stack
    
    INC a:rng_ptr
    BNE @s
    INC a:rng_ptr + 1
    BNE @s
    INC a:rng_ptr + 2
    BNE @s
    INC a:rng_ptr + 3
@s: PLA                 ; Get the Output from the Stack again, then Return
RTS

; Function takes up 46 Bytes, so another 210 Bytes are required to fill the table
.byte $54, $67, $87, $EC, $DF, $A0, $0F, $A0, $9E, $F9, $40, $03, $9A, $B7, $EE, $68
.byte $3C, $8E, $79, $B4, $D6, $1D, $E5, $43, $54, $65, $DB, $59, $A2, $A6, $AD, $A9
.byte $75, $50, $BB, $BA, $82, $F4, $D3, $3C, $50, $5E, $6A, $98, $2E, $49, $CB, $3F
.byte $02, $53, $93, $8F, $EA, $24, $1C, $57, $F5, $F0, $AD, $3F, $65, $BA, $94, $A7
.byte $43, $12, $79, $CB, $30, $2F, $93, $2F, $BB, $94, $92, $A8, $BE, $AE, $5F, $88
.byte $66, $11, $0B, $BA, $FE, $48, $8C, $E2, $A4, $64, $21, $BF, $75, $A6, $78, $62
.byte $D8, $0A, $F9, $0F, $FA, $89, $CB, $BF, $A4, $47, $70, $A9, $F5, $1D, $16, $3F
.byte $B3, $20, $F9, $90, $33, $1B, $74, $F6, $16, $25, $90, $79, $4D, $BA, $46, $61
.byte $30, $0B, $B5, $CA, $95, $6E, $FA, $48, $2E, $15, $7F, $E2, $A0, $7F, $DF, $F4
.byte $17, $4D, $BA, $BE, $54, $64, $12, $B7, $64, $8D, $17, $E2, $90, $F9, $70, $BE
.byte $2D, $5B, $6B, $95, $5D, $80, $A1, $37, $E6, $92, $FE, $73, $B3, $71, $2F, $CB
.byte $A6, $D7, $EE, $48, $CA, $1C, $AD, $5E, $09, $E8, $98, $3F, $01, $1B, $EC, $25
.byte $95, $B5, $1D, $5B, $4E, $93, $4A, $11, $B9, $44, $F2, $4C, $44, $46, $FE, $7D
.byte $58, $73

since it just uses a 32-bit incrementing number it will repeat after 2^32-1 calls.

Top

gfoot

Post subject: Re: Random-number generation

Posted: Sat Jan 28, 2023 10:49 pm

Joined: Fri Jul 09, 2021 10:12 pm
Posts: 741

For a general case you probably do want to err on the side of more randomness, but in a lot of cases not so much is required. I recently made a procedural world generator - at its core it needs to be able to take an x,y location and decide whether it is filled or empty. In order to do this I ended up needing to generate a random number from 0 to 15 in order to pick between five options with different weights; then within most of those options I needed to pick between a further four options. So I needed to generate six bits of entropy - no need for any more, as they wouldn't be used. The technical randomness wasn't too important so long as there weren't perceptible patterns. Being fairly fast to calculate on a 6502 was important though.

The code I used so far is just adding various shifts of the X and Y coordinates, I believe, then reducing to the target number of bits. It is random enough for my purpose but if I find it's not at some point I can easily change a shift or add an extra term in.

I guess this is actually more like hashing than random number generation but I think there's a lot in common.

I prototyped the algorithm in Shadertoy, you can play with it here if you like - the core randomness comes from the "scrog" routine. And if you drag the mouse around the viewport it will scroll over a large area.

https://www.shadertoy.com/view/cdBSRt

Top

Arlet

Post subject: Re: Random-number generation

Posted: Fri Feb 10, 2023 8:01 am

Joined: Tue Nov 16, 2010 8:00 am
Posts: 2353
Location: Gouda, The Netherlands

I was working on AVR 8 bit CPU, and I came up with an idea for a random generator that should also work well on the 6502. It uses some RAM to contain the state, which is an array of bytes, called S[]. It also uses a 256 byte substitution table, called SBOX[], which maps every byte to a different one. The table must be complete, so every value between 0-255 should only appear once. The design of the table is very important, so I recommend using the S-Box table from the AES encryption algorithm

Read P = state byte S[0].
Table lookup Q = SBOX[P]
Write back S[0] = Q
Add Q to next byte of state: P = Q + S[1]
Table lookup Q = SBOX[P]
Write back S[1] = Q
Add Q to next byte of state: P = Q + S[2]
Loop through all state bytes. When you reach the last byte, add Q back to S[0] = S[0] + Q

It's very simple code, but it works quite well. For good level of randomness, run the whole loop twice. I use 4 state bytes(*), but you can increase that for longer periods. You can also improve randomness by alternating between addition and XOR. Make sure to use CLC before the addition. You might think that using ADC and letting the carry propagate from one byte to the next would add some extra randomness, but it actually makes it worse.

(*) Note that the algorithm might get stuck in a short repetition cycle for some seed values. In my application, I constantly add a few fresh random bits from outside. If you don't do that, I recommend using a few more state bytes. If you modify the code to start with P = Q + S[0] you could call the subroutine with a Q parameter to add some external randomness.

Last edited by Arlet on Fri Feb 10, 2023 3:11 pm, edited 1 time in total.

Top

teamtempest

Post subject: Re: Random-number generation

Posted: Fri Feb 10, 2023 3:00 pm

Joined: Sun Nov 08, 2009 1:56 am
Posts: 411
Location: Minnesota

Quote:

Make sure to use CLC before the addition. You might think that using ADC and letting the carry propagate from one byte to the next would add some extra randomness, but it actually makes it worse.

I was wondering about that!

Top

White Flame

Post subject: Re: Random-number generation

Posted: Sun Feb 12, 2023 8:35 pm

Joined: Tue Jul 24, 2012 2:27 am
Posts: 679

For really compact but dumb PRNGs, a while ago I ported the basic LFSR algorithm and gave it a full 256|65536 period, as opposed to the default of just 255|65535. Of course, the period is only as long as the number itself, but I wanted something where graphical effects would go through all 256 values of a grid once in a "random" order.

https://codebase64.org/doku.php?id=base:small_fast_8-bit_prng
https://codebase64.org/doku.php?id=base:small_fast_16-bit_prng

The 8-bit one is quite tiny, even with the fixup for full range:

Code:

        lda seed
        beq doEor
         asl
         beq noEor
         bcc noEor
doEor:    eor #$1d  ; 16 possible magic numbers work here, see the link
noEor:  sta seed

_________________
WFDis Interactive 6502 Disassembler
AcheronVM: A Reconfigurable 16-bit Virtual CPU for the 6502 Microprocessor

Top

Alex1

Post subject: Re: Random-number generation

Posted: Tue Mar 14, 2023 12:08 am

Joined: Mon Mar 13, 2023 9:38 pm
Posts: 80

Hi all. I take this opportunity to post you the code I did in 1988 because it may interest someone.

It generates a random sequence of 2^32-1 bits (4.3 billion bits). It's a 32-bit GALOIS LFSR. Each call to the routine generates an 8-bit byte. We can therefore obtain (2^32)/8 bytes before repeating the sequence. There is no short cycle for all seed values.

Code:

//----------------------------------------------------
//          Pukall LFSR 32
//             1988
//----------------------------------------------------


//----------------------------------------------------
//          Main Program
//----------------------------------------------------

start:   
bit0:   lda #0
   sta rndbyte
   sta tmp
   jsr begin
   lda tmp
   cmp #0
   beq bit1
   sta rndbyte
      
bit1:   lda #0
   sta tmp
   jsr begin
   lda tmp
   cmp #0
   beq bit2
   lda rndbyte
   ora #$2
   sta rndbyte

bit2:   lda #0
   sta tmp
   jsr begin
   lda tmp
   cmp #0
   beq bit3
   lda rndbyte
   ora #$4
   sta rndbyte

bit3:   lda #0
   sta tmp
   jsr begin
   lda tmp
   cmp #0
   beq bit4
   lda rndbyte
   ora #$8
   sta rndbyte

bit4:   lda #0
   sta tmp
   jsr begin
   lda tmp
   cmp #0
   beq bit5
   lda rndbyte
   ora #$10
   sta rndbyte
   
bit5:   lda #0
   sta tmp
   jsr begin
   lda tmp
   cmp #0
   beq bit6
   lda rndbyte
   ora #$20
   sta rndbyte

bit6:   lda #0
   sta tmp
   jsr begin
   lda tmp
   cmp #0
   beq bit7
   lda rndbyte
   ora #$40
   sta rndbyte

bit7:   lda #0
   sta tmp
   jsr begin
   lda tmp
   cmp #0
   beq ret
   lda rndbyte
   ora #$80
   sta rndbyte
ret:   rts

begin:
        asl seed
        rol seed+1
        rol seed+2
        rol seed+3
        bcc not
        lda seed
        eor #$01
        sta seed
        lda seed+3
        eor #$EA
        sta seed+3
   lda #1
   sta tmp
not:
   rts

seed: .byte $FF,$FF,$FF,$FF
tmp:  .byte $00
rndbyte: .byte $00

First a 4-byte seed must be put at seed:
The seed can vary from 1 to $FFFFFFFF but never 0 otherwise the LFSR produces only bits to 0.

Each call to the start: function returns a pseudorandom byte in rndbyte:

To mix the LFSR it is recommended to do 4 calls to the start: function before using the generated bytes in rndbyte:.
Not 4 calls to the start: function for each generated byte (rndbyte:) but only the first time. Then the generated bytes (rndbyte:) can be use directly.

The test vector is :

For a seed = $FFFFFFFF
the first 50 bytes are :

Quote:

F1 64 75 CB 0B A0 29 DD 2E E5 E6 A9 2B 5C 40 A6 1E F0 55 DF 52 70 B3 DA 60 32 27 94 B1 2E 1C 3B 5E 8B 21 92 26 77 5A A9 B3 A2 BB 7F 93 E2 45 9A FE F9

A search on the integer space shows that there is no repetition of the sequence of the first 20 bytes for the example seed $FFFFFFFF:

Quote:

Found 'F16475CBBA029DD2EE5E6A92B5C40A61EF055DF' at index 0 !

A FIPS 140-2 test shows that bytes are seen as random:

Quote:

rngtest: starting FIPS tests...
rngtest: bits received from input: 40000032
rngtest: FIPS 140-2 successes: 2000
rngtest: FIPS 140-2 failures: 0
rngtest: FIPS 140-2(2001-10-10) Monobit: 0
rngtest: FIPS 140-2(2001-10-10) Poker: 0
rngtest: FIPS 140-2(2001-10-10) Runs: 0
rngtest: FIPS 140-2(2001-10-10) Long run: 0
rngtest: FIPS 140-2(2001-10-10) Continuous run: 0
rngtest: input channel speed: (min=70.905; avg=3035.005; max=6357.829)Mibits/s
rngtest: FIPS tests speed: (min=5.208; avg=16.153; max=16.731)Mibits/s
rngtest: Program run time: 2378917 microseconds

Some people use a picture to test randomness but it's not reliable, only FIPS 140-2 tests are reliable :

Attachment:

pukall-lfsr-32.jpg [ 308.42 KiB | Viewed 2238 times ]

sorry for my English this is not my native language.

Here is the optimized code by Teamtempest:

Code:

//----------------------------------------------------
//          Pukall LFSR 32
//             1988
//   Optimized by Teamtempest 2023
//----------------------------------------------------

//----------------------------------------------------
//          Main Program
//----------------------------------------------------

start:   lda #$00
        sta randombyte
        lda #$01
        sta mask

loop:

        asl seed
        rol seed+1
        rol seed+2
        rol seed+3
        bcc noupdate
       
        lda seed
        eor #$01
        sta seed
        lda seed+3
        eor #$EA
        sta seed+3

        lda randombyte
        ora mask
        sta randombyte

noupdate:

        asl mask
        bcc loop
        rts

seed: .byte $FF,$FF,$FF,$FF
mask:  .byte $00
randombyte: .byte $00

Last edited by Alex1 on Tue Mar 21, 2023 7:12 pm, edited 13 times in total.

Top

Alex1

Post subject: Re: Random-number generation

Posted: Tue Mar 14, 2023 1:25 pm

Joined: Mon Mar 13, 2023 9:38 pm
Posts: 80

Proxy wrote:

Code:

.data
rng_ptr:    .res 4

.code
rng_func:
    .A8
    .I8
    LDX a:rng_ptr
    LDY a:rng_ptr + 1   ; Get Pointers 0 and 1
    
    LDA a:rng_func,X    ; Get a byte from the RNG Table (using Pointer 0)
    CLC
    ADC rng_func,Y      ; Add a byte from the RNG Table (using Pointer 1) to the Value
    LDX rng_ptr + 2
    LDY rng_ptr + 3     ; Get Pointers 2 and 3
    EOR a:rng_func,X    ; XOR the Value with a byte from the RNG Table (using Pointer 2)
    ADC rng_func,Y      ; And finally, Add a byte from the RNG Table (using Pointer 3) to the Value
    PHA                 ; Save the Output on the Stack
    
    INC a:rng_ptr
    BNE @s
    INC a:rng_ptr + 1
    BNE @s
    INC a:rng_ptr + 2
    BNE @s
    INC a:rng_ptr + 3
@s: PLA                 ; Get the Output from the Stack again, then Return
RTS

; Function takes up 46 Bytes, so another 210 Bytes are required to fill the table
.byte $54, $67, $87, $EC, $DF, $A0, $0F, $A0, $9E, $F9, $40, $03, $9A, $B7, $EE, $68
.byte $3C, $8E, $79, $B4, $D6, $1D, $E5, $43, $54, $65, $DB, $59, $A2, $A6, $AD, $A9
.byte $75, $50, $BB, $BA, $82, $F4, $D3, $3C, $50, $5E, $6A, $98, $2E, $49, $CB, $3F
.byte $02, $53, $93, $8F, $EA, $24, $1C, $57, $F5, $F0, $AD, $3F, $65, $BA, $94, $A7
.byte $43, $12, $79, $CB, $30, $2F, $93, $2F, $BB, $94, $92, $A8, $BE, $AE, $5F, $88
.byte $66, $11, $0B, $BA, $FE, $48, $8C, $E2, $A4, $64, $21, $BF, $75, $A6, $78, $62
.byte $D8, $0A, $F9, $0F, $FA, $89, $CB, $BF, $A4, $47, $70, $A9, $F5, $1D, $16, $3F
.byte $B3, $20, $F9, $90, $33, $1B, $74, $F6, $16, $25, $90, $79, $4D, $BA, $46, $61
.byte $30, $0B, $B5, $CA, $95, $6E, $FA, $48, $2E, $15, $7F, $E2, $A0, $7F, $DF, $F4
.byte $17, $4D, $BA, $BE, $54, $64, $12, $B7, $64, $8D, $17, $E2, $90, $F9, $70, $BE
.byte $2D, $5B, $6B, $95, $5D, $80, $A1, $37, $E6, $92, $FE, $73, $B3, $71, $2F, $CB
.byte $A6, $D7, $EE, $48, $CA, $1C, $AD, $5E, $09, $E8, $98, $3F, $01, $1B, $EC, $25
.byte $95, $B5, $1D, $5B, $4E, $93, $4A, $11, $B9, $44, $F2, $4C, $44, $46, $FE, $7D
.byte $58, $73

since it just uses a 32-bit incrementing number it will repeat after 2^32-1 calls.

I'm really sorry to tell you and I hope you won't get offended but your algorithm is not random at all and is full of short cycles. not at all 2^32. I guess you never did any tests on it, did you?

The 46 bytes code + 210 bytes i used are :

Code:

$AE,$0D,$10,$AC,$0E,$10,$BD,$12,$10,$18,$79,$12,$10,$AE,
 $0F,$10,$AC,$10,$10,$5D,$12,$10,$79,$12,$10,$48,$EE,$0D,$10,$D0,$0D,$EE,$0E,
 $10,$D0,$08,$EE,$0F,$10,$D0,$03,$EE,$10,$10,$68,$60, $54, $67, $87, $EC, $DF,
 $A0, $0F, $A0, $9E, $F9, $40, $03, $9A, $B7, $EE, $68, $3C, $8E, $79, $B4, $D6,
 $1D, $E5, $43, $54, $65, $DB, $59, $A2, $A6, $AD, $A9, $75, $50, $BB, $BA, $82,
 $F4, $D3, $3C, $50, $5E, $6A, $98, $2E, $49, $CB, $3F, $02, $53, $93, $8F, $EA,
 $24, $1C, $57, $F5, $F0, $AD, $3F, $65, $BA, $94, $A7, $43, $12, $79, $CB, $30,
 $2F, $93, $2F, $BB, $94, $92, $A8, $BE, $AE, $5F, $88, $66, $11, $0B, $BA, $FE,
 $48, $8C, $E2, $A4, $64, $21, $BF, $75, $A6, $78, $62, $D8, $0A, $F9, $0F, $FA,
 $89, $CB, $BF, $A4, $47, $70, $A9, $F5, $1D, $16, $3F, $B3, $20, $F9, $90, $33,
 $1B, $74, $F6, $16, $25, $90, $79, $4D, $BA, $46, $61, $30, $0B, $B5, $CA, $95,
 $6E, $FA, $48, $2E, $15, $7F, $E2, $A0, $7F, $DF, $F4, $17, $4D, $BA, $BE, $54,
 $64, $12, $B7, $64, $8D, $17, $E2, $90, $F9, $70, $BE, $2D, $5B, $6B, $95, $5D,
 $80, $A1, $37, $E6, $92, $FE, $73, $B3, $71, $2F, $CB, $A6, $D7, $EE, $48, $CA,
 $1C, $AD, $5E, $09, $E8, $98, $3F, $01, $1B, $EC, $25,$95, $B5, $1D, $5B, $4E,
 $93, $4A, $11, $B9, $44, $F2, $4C, $44, $46, $FE, $7D, $58, $73

A lot of FIPS 140-2 tests failed :

Quote:

rngtest: starting FIPS tests...
rngtest: bits received from input: 40000032
rngtest: FIPS 140-2 successes: 1162
rngtest: FIPS 140-2 failures: 838
rngtest: FIPS 140-2(2001-10-10) Monobit: 54
rngtest: FIPS 140-2(2001-10-10) Poker: 788
rngtest: FIPS 140-2(2001-10-10) Runs: 279
rngtest: FIPS 140-2(2001-10-10) Long run: 0
rngtest: FIPS 140-2(2001-10-10) Continuous run: 0
rngtest: input channel speed: (min=22.980; avg=2929.425; max=9536.743)Mibits/s
rngtest: FIPS tests speed: (min=2.272; avg=16.170; max=16.894)Mibits/s
rngtest: Program run time: 2374486 microseconds

All al lot of short cycles, I stopped the test well before 2^32 :
The first 20-byte sequence repeats non-stop :

Quote:

Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 0 !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 194E !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index EE72 !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 1933CE !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 194D1C !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 1A2240 !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index AF0D5D !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index AFBF9A !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index EE505C !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index EE69AA !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index EF3ECE !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 1614E00 !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 162003D !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 19304FE3 !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 19306931 !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 19313E55 !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 194983B1 !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 19499CFF !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 194A7223 !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 19DF5D40 !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 19E00F7D !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 1A1EA03F !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 1A1EB98D !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 1A1F8EB1 !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 1A919DE3 !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 1A925020 !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 3261FF8E !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 327B296C !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 330F2737 !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 330F30EF !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 330F3AAE !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 330F446D !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 330F6965 !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 3310A765 !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 33503E8A !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 33C16908 !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 33C172C0 !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 33C17C7F !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 33C1863E !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 33C1AB36 !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 33C2E936 !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 3C1204AE !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 3C2B2E8C !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 3CBF2C57 !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 3CBF360F !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 3CBF3FCE !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 3CBF498D !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 3CBF6E85 !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 3CC0AC85 !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 3D0043AA !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 3D716E28 !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 3D7177E0 !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 3D71819F !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 3D718B5E !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 3D71B056 !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 3D72EE56 !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 45C21AB1 !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 45DB448F !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 466F425A !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 466F4C12 !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 466F55D1 !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 466F5F90 !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 466F8488 !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 4670C288 !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 46B059AD !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 4721842B !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 47218DE3 !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 472197A2 !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 4721A161 !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 4721C659 !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 47230459 !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 4F7224BD !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 4F8B4E9B !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 501F4C66 !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 501F561E !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 501F5FDD !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 501F699C !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 501F8E94 !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 5020CC94 !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 506063B9 !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 50D18E37 !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 50D197EF !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 50D1A1AE !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 50D1AB6D !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 50D1D065 !
Found 'A0C3BEA2C0BE731CBE16371CBEA0C1BEA2BEBE53' at index 50D30E65 !

Last edited by Alex1 on Tue Mar 14, 2023 2:23 pm, edited 1 time in total.

Top

Dr Jefyll

Post subject: Re: Random-number generation

Posted: Tue Mar 14, 2023 1:52 pm

Joined: Fri Dec 11, 2009 3:50 pm
Posts: 3367
Location: Ontario, Canada

Alex1 wrote:

Hi all. I take this opportunity to post you the code I did in 1988 because it may interest someone.

Welcome, Alex1, and thanks for sharing this code with us. And BTW your English seems just fine to me.

Truthfully, I myself don't have much expertise where random numbers are concerned (although I did once implement a LFSR in x86 assembly language using a feedback equation I obtained elsewhere). Perhaps someone more qualified than I will respond to your posts soon.

Meanwhile, please feel free to browse the other topics here on this forum, and to share more of your 65xx-related activity with us if you feel so inclined.

-- Jeff

_________________
In 1988 my 65C02 got six new registers and 44 new full-speed instructions!
https://laughtonelectronics.com/Arcana/ ... mmary.html

Top

drogon

Post subject: Re: Random-number generation

Posted: Tue Mar 14, 2023 1:57 pm

Joined: Wed Feb 14, 2018 2:33 pm
Posts: 1488
Location: Scotland

May I ask how you're testing the 6502 code with FIPS 140-2?

ie. do you have a 6502 version of the FIPS test code, or are you generating bytes on a 6502 to feed into some other test program?

Interested as I have another system (65816 based) where I'd like to test it's RNG and I don't fancy copying bytes over to a Python test program...

Thanks,

-Gordon

_________________
--
Gordon Henderson.
See my Ruby 6502 and 65816 SBC projects here: https://projects.drogon.net/ruby/

Top

Alex1

Post subject: Re: Random-number generation

Posted: Tue Mar 14, 2023 2:05 pm

Joined: Mon Mar 13, 2023 9:38 pm
Posts: 80

Thanks Dr Jefyll.

Drogon, I simply generate the bytes of the 6502 and import the file on my Linux. The FIPS 140-2 test program is on Linux.

I use the rngtest, here is the command line i use :

Quote:

rngtest <random.bin

rngtest 2-unofficial-mt.14
Copyright (c) 2004 by Henrique de Moraes Holschuh
This is free software; see the source for copying conditions. There is NO warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

rngtest: starting FIPS tests...
rngtest: entropy source exhausted!
rngtest: bits received from input: 32964608
rngtest: FIPS 140-2 successes: 1648
rngtest: FIPS 140-2 failures: 0
rngtest: FIPS 140-2(2001-10-10) Monobit: 0
rngtest: FIPS 140-2(2001-10-10) Poker: 0
rngtest: FIPS 140-2(2001-10-10) Runs: 0
rngtest: FIPS 140-2(2001-10-10) Long run: 0
rngtest: FIPS 140-2(2001-10-10) Continuous run: 0
rngtest: input channel speed: (min=244.532; avg=2880.600; max=6357.829)Mibits/s
rngtest: FIPS tests speed: (min=6.262; avg=16.121; max=16.731)Mibits/s
rngtest: Program run time: 1962810 microseconds

Top

teamtempest

Post subject: Re: Random-number generation

Posted: Tue Mar 14, 2023 2:17 pm

Joined: Sun Nov 08, 2009 1:56 am
Posts: 411
Location: Minnesota

I think this might be the equivalent of alex1's 1988 code:

Code:

LFSR: .byte $FF,$FF,$FF,$FF
mask       .ds 1
randombyte .ds 1

        lda #$00
        sta randombyte
        lda #$01
        sta mask

loop:

        asl LFSR
        rol LFSR+1
        rol LFSR+2
        rol LFSR+3
        bcc noupdate
        
        lda LFSR
        eor #$01
        sta LFSR
        lda LFSR+3
        eor #$EA
        sta LFSR+3

        lda randombyte
        ora mask
        sta randombyte

noupdate:

        rol mask
        bcc :loop
        rts

Top

Alex1

Post subject: Re: Random-number generation

Posted: Tue Mar 14, 2023 2:39 pm

Joined: Mon Mar 13, 2023 9:38 pm
Posts: 80

teamtempest wrote:

I think this might be the equivalent of alex1's 1988 code:

There must be a problem because I don't get the same test vector with your code.

First bytes with seed $FFFFFFFF are different with your code :

FF 6D 7F FF 0F A2

Here is the code i used :

Code:

start: 
        lda #$00
        sta randombyte
        lda #$01
        sta mask

loop:

        asl lfsr
        rol lfsr+1
        rol lfsr+2
        rol lfsr+3
        bcc noupdate
       
        lda lfsr
        eor #$01
        sta lfsr
        lda lfsr+3
        eor #$EA
        sta lfsr+3

        lda randombyte
        ora mask
        sta randombyte

noupdate:

        rol mask
        bcc loop
        rts

lfsr: .byte $FF,$FF,$FF,$FF
mask:  .byte $00
randombyte: .byte $00

Last edited by Alex1 on Tue Mar 14, 2023 2:52 pm, edited 1 time in total.

Top

Arlet

Post subject: Re: Random-number generation

Posted: Tue Mar 14, 2023 2:45 pm

Joined: Tue Nov 16, 2010 8:00 am
Posts: 2353
Location: Gouda, The Netherlands

Quote:

I think this might be the equivalent of alex1's 1988 code:

You can optimize it even more by rotating the carry into the output byte instead of using the separate mask.

Code:

        asl LFSR
        rol LFSR+1
        rol LFSR+2
        rol LFSR+3
        bcc noupdate   
        lda LFSR
        eor #$01
        sta LFSR
        lda LFSR+3
        eor #$EA
        sta LFSR+3
noupdate:
        ror randombyte

And then repeat that code 8 times in a loop.

Top

Alex1

Post subject: Re: Random-number generation

Posted: Tue Mar 14, 2023 2:49 pm

Joined: Mon Mar 13, 2023 9:38 pm
Posts: 80

You can optimize it even more by rotating the carry into the output byte instead of using the separate mask.

yes the optimization would be nice but the optimized code by teamtempest is not compatible with my LFSR. Maybe we should find the bug before optimizing the first optimization?

Top

Alex1

Post subject: Re: Random-number generation

Posted: Tue Mar 14, 2023 2:58 pm

Joined: Mon Mar 13, 2023 9:38 pm
Posts: 80

Quote:

I was working on AVR 8 bit CPU, and I came up with an idea for a random generator that should also work well on the 6502.

Arlet, by the way if you have 6502 code of your code, i could test it to verify if it's FIPS 140-2 compatible or not...

Top

Page 2 of 17

[ 245 posts ]

Go to page Previous 1, 2, 3, 4, 5 ... 17 Next

Board index » 6502.org Users Forum » Programming

All times are UTC

Who is online

Users browsing this forum: No registered users and 10 guests

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot post attachments in this forum