从6502汇编中获取随机数

Question

我正尝试使用JSR $E09A在Commodore 64 (C64)上生成一系列随机数，并从$63和$64中检索数字。（根据我看到的所有文档，这与在BASIC中使用RND（0）时相同。但是不能迭代。以下内容将在单独执行时起作用，并放置不同的数字在$63和$64中。

. C000  A5 00    LDA $00
. C002  20 9A E0 JSR $E09A
. C005  00       BRK

现在当我尝试使用以下代码进行10次迭代时，它永远不会返回。

. C000  A0 0A    LDY #$0A
. C002  A9 00    LDA #$00
. C004  20 9A E0 JSR $E09A
. C007  88       DEY
. C008  D0 F8    BNE $C002
. C00A  00       BRK

我是不是忽略了显而易见的事情，以至于看不到它？我并不担心这些数字的“随机性”，在这一点上我只希望得到一系列随机的数字。

- Kenny

---

我没有答案，但我想知道在 Stack Exchange 上的新复古计算机论坛上是否有一些人可以帮助你。 - TomServo

你所调用的函数可能会改变Y寄存器中的值。 - Ross Ridge

就是这样，我知道我漏掉了什么显而易见的东西。 - Kenny

JLH提到[Retrocomputing.SE]，但在Stack Overflow上，无论你的目标机器有多老，编程问题都是完全合适的。 :-) - Cody Gray

谢谢@CodyGray，我会查看Retrocomputing部分。最近我找到了一些旧的Commodore软盘，并成功地将它们转移到了USB上。我发现了VICE commodore模拟器，现在我正在通过调整一些基本程序和汇编例程来愉快地重温80年代中期。 - Kenny

@Kenny JSR $E09E 更好。 - Zibri

Answer 1

SID芯片实际上可以生成比BASIC伪随机数更随机的数字。使用以下命令启动生成器：

LDA #$FF  ; maximum frequency value
STA $D40E ; voice 3 frequency low byte
STA $D40F ; voice 3 frequency high byte
LDA #$80  ; noise waveform, gate bit off
STA $D412 ; voice 3 control register
RTS

然后，您可以使用以下代码随时获取随机数：

LDA $D41B ; get random value from 0-255

- Mike

---

如果您的程序正在使用SID（同时播放所有三个音轨）播放音乐，那么您仍然可以使用这种技术吗？ - Psychonaut

可以从缓存中提取预先生成的随机数，并在不使用语音3时关闭输出并重新填充缓存，然后重置语音3以准备进行下一次输出。这只涉及到更改播放音乐例程以在间隙期间使用它。 - Mike

你在什么上运行它？我不能代表模拟器说话，但是硬件方法被用来为高级债券生成随机数。SID芯片实际上会产生噪音，我想。 - Mike

我猜你在得到那个相同的序列时使用了模拟器。模拟器无法真正模拟硬件。真正的SID芯片能够产生看似真实的随机数。我曾经在所有的c64游戏/应用程序中使用过这种技术，而且随机数比我见过的任何现代伪随机数生成器都要好。 - iPaul

在快速连续读取随机数时，你必须小心。如果你编写超快手工汇编代码从$D41B中提取值的速度过快，你会得到重复的数字对。因此，对于某人建议的缓存技术，你必须丢弃每个其他值或在你的LDAs和STAs之间插入NOP指令。 - iPaul

Answer 2

感谢Ross Ridge提出的建议，指出被调用的函数正在更改Y寄存器中的值。我知道这一定是显而易见的问题！

通过在JSR之前存储Y，并在之后恢复，现在可以正确地迭代。以下是快速修复：

编辑：更新于7/10/17-显示完整代码并合并JeremyP的建议。这本质上是一个硬币翻转迭代器（50000次重复），用于随机实验。

.C 033c  A9 00       LDA #$00
.C 033e  85 FB       STA $FB    ; set up register for counter
.C 0340  85 FC       STA $FC
.C 0342  A2 C8       LDX #$C8   ; outer loop= 200
.C 0344  86 FD       STX $FD
.C 0346  A0 FA       LDY #$FA   ; inner loop=250
.C 0348  84 FE       STY $FE
.C 034a  20 94 E0    JSR $E094  ; Get random# Vic20 Address (E09B for C64)
.C 034d  A5 63       LDA $64
.C 034f  C9 80       CMP #$80   ; >128 = HEADS
.C 0351  90 0D       BCC $0360  ; else continue loop
.C 0353  18          CLC        ; increment 2 byte number
.C 0354  A5 FB       LDA $FB
.C 0356  69 01       ADC #$01   ; LSB
.C 0358  85 FB       STA $FB
.C 035a  A5 FC       LDA $FC
.C 035c  69 00       ADC #$00   ; MSB
.C 035e  85 FC       STA $FC
.C 0360  C6 FE       DEC $FE
.C 0362  D0 E6       BNE $034A  ; end inner loop
.C 0364  C6 FD       DEC $FD
.C 0366  D0 DE       BNE $0346  ; end outer loop
.C 0368  60          RTS        ; return to basic

我可以在循环内使用LDA $63或LDA $64来获取随机数，并将其用于我的目的。

结果比预期慢得多，只需要BASIC所需时间的一半。RND函数需要很多周期，但是我发现这篇Compute! article文章使用SID芯片作为随机数生成器。

LDA #$FF  ; maximum frequency value
STA $D40E ; voice 3 frequency low byte
STA $D40F ; voice 3 frequency high byte
LDA #$80  ; noise waveform, gate bit off
STA $D412 ; voice 3 control register  

一旦启动，它会独立生成数字，不需要再次执行。重复调用 LDA $D41B 的循环将在每次迭代中为您获取一个新的随机数。在我的测试中，50000次迭代花费了1.25秒，而100万次迭代则花费了略微超过24秒。对于一台1MHz的计算机来说非常令人印象深刻！

- Kenny

Answer 3

你实际上是在调用 RND(0)，它使用计时器生成种子。然而，在汇编中无法直接使用该种子。首先尝试切换到正数（任何数字），看看它是否开始产生值。

- Chet

---

正如Ross所说，该函数正在更改“Y”寄存器。另请参阅完全注释的Commodore 64 ROM反汇编。 - Jester

哦，对了。所以我的答案完全错了。我不确定关于 Stack Overflow 的礼仪，我应该删除它吗？ - Chet

根据文档，JSR $E09A 将使用累加器中的值来确定种子，其中情况 0 将获取计时器寄存器中的当前值。因此，它的行为就像 BASIC 中的 RND(0)。 - Kenny

@Kenny：你只需要“种子”一次随机数生成器，所以RND（0）仅用于第一次调用，之后应该保持当前种子。一直重新初始化种子对结果有害，实际上，如果你调用得足够快，计时器寄存器仍然具有相同的值，你可能会收到相同的随机值。（这是一般的随机数生成器原理解释，我没有研究C64的情况，所以我不知道在初始化后如何正确处理种子值，最后一个随机数是否也是下一个随机数的种子等）。 - Ped7g

好的，要么使用“LDA $01”，要么使用“JSR $E0BE”来完全跳过符号检查。 - Chet

Answer 4

如果您没有带有定时光栅IRQ或类似功能的程序，您可以使用lda $d012获取一个“随机”数字。

- A.vH

---

即使没有定时中断，由于CPU周期已经硬连到VIC上，这种方式存在重复序列的风险...自答案中展示的SID方法更好;) - user2371524

没错，如果你的程序在没有用户交互的情况下运行。Sid 方法会为音乐窃取一个声音通道。 - A.vH

是的，在交互式程序中发生这种情况的可能性很小，你说得对 :) 只是说“SID方法”根本不会暴露出这种风险。当然，对于游戏来说，随机性的质量并不太重要。 - user2371524

Answer 5

C64的真正问题是：

1. SID生成的数字也是伪随机的，它们会重复出现在一个序列中（我找不到讨论这个问题的链接）

2. 光栅位置不是随机的。

C64中唯一的真正随机源是用户输入。

所以我的做法是：

1. 初始化SID噪声波形
2. 在启动时获取CIA计时器1的LSB（在普通的C64上很好，但在模拟器上不是随机的）
3. 启动CIA计时器2
4. 等待用户按下任意键（或摇杆方向/按钮）
5. 获取CIA计时器2的LSB
6. 获取SID幅度值
7. 可选地获取光栅位置，但取决于您是从基本语言还是汇编语言调用此例程，您可能无法获得完全随机的值。

然后您就有了您最喜欢的伪随机例程的随机种子。或者只是一个一次性的16/24/32位随机数。

例如，在游戏中，当用户移动操纵杆时，可以获取CIA计时器并获得一个随机字节。

注意：在模拟器中放置prg或d64与编写“load…”非常不同，因为每个用户每次编写的方式都不同，并且在这种情况下计时器LSB是“随机”的。

因此，在某些模拟器中，会添加随机延迟以启动计算机。

- Zibri

---

我不确定仅仅是伪随机数在这里是否是一个问题。这些数字很可能不是为了加密目的而生成的。 - Ross Ridge

仅供参考，基于斐波那契数列的 PRNG 通过了所有随机性检查...看看这个：https://github.com/Zibri/rand2 - Zibri

@RossRidge 在这里给你：https://dev59.com/daPia4cB1Zd3GeqPui44#76500260 - Zibri

Answer 6

我在搜索C64汇编中更通用的RND（start，end）例程时找到了这个线程。类似于这个BASIC示例实现的东西：

INT(RND(1) * (end- start + 1)) + start

虽然这里有许多有用的答案，但我缺少这种解决方案，所以我不得不找到自己的方法；这可能对来到这个线程的另一个人有所帮助，所以我分享一下：

            lda #<end   
            sta $FD
            lda #>end
            sta $FE
            lda #<start
            sta $FB
            lda #>start
            sta $FC
rnd:
            //reseed, to avoid repeated sequence; RND(0)
            lda #00
            jsr $E09A
            //++end 
            inc $FD
            bne skip1
            inc $FE
skip1:
            //- start
            lda $FD
            sec
            sbc $FB
            sta $FD
            lda $FE
            sbc $FC
            sta $FE         

            //++end-start to FAC
            ldy $FD
            lda $FE
            jsr $B391 //A(h),Y(L) - FAC 
            ldx #<flt
            ldy #>flt
            jsr $BBD4   //store FAC to flt
            //get actual RND(1)
            lda #$7f
            jsr $E09A
            //multiply by ++end - start
            lda #<flt
            ldy #>flt
            jsr $BA28
            //to integer
            jsr $BCCC
            //FAC to int;
            jsr $B1BF
            lda $65         
            clc
            adc $FB
            sta $14
            lda $64
            adc $FC
            sta $15
            rts     
flt:        .byte 0,0,0,0,0

该程序处理范围在0-32767之间的16位数字。参数从251,252开始；以253,254结束。 16位结果存储在$14中。

- Lovro

Answer 7

LDA #$FF
STA $D40E ; set maximum frequency
STA $D40F ; set maximum frequency
LDA #$81
STA $D412 ; set NOISE waveform

JSR RND  ; A will contain a random byte
RTS

RND:
   LDA $DC04 ; read Timer A of CIA#1
   STA YY+1
XX:
   EOR #$FF
   STA ($fd),y
   EOR $D41B ; read Waveform Amplitude
YY:
   EOR #$00
   STA XX+1
   RTS

- Zibri

---

这个算法使用了什么？看起来它只是与内存中的一些值进行异或运算，并在YY: EOR中更新立即数。所以我没有看到种子值内部水平混合位的任何操作。它是否读取由中断或I/O端口修改的内存位置？ - Peter Cordes

不。它将SID的白噪声随机发生器的内容与CIA1的计时器A混合在一起。 - Zibri

在你的回答中提到这一点是个好主意，可以通过代码注释和/或文本来说明。我看到你之前对这个问题有过回答；你可以将新的部分编辑到其中，或者如果这个问题足够独立，也可以单独解释。 - Peter Cordes

@PeterCordes 好的..我已经对代码进行了注释。 - Zibri

Answer 8

现在已经很晚了，但根据要求，您也可以自己编写 PRNG。有些算法足够简单，可以实现。例如，我将在此处展示一个使用参数[3,25,24]的32位xorshift实现（因为这使得两个移位使用非常少的代码）。返回的随机数有16位：

rnd_seed:
                sta     $22             ; store pointer to PRNG state
                stx     $23
                lda     #$00            ; initialize with 0
                ldy     #$03
rs_clrloop:     sta     ($22),y
                dey
                bne     rs_clrloop
                lda     $d012           ; except for LSB, use current raster
                bne     seed_ok
                lda     #$7f            ; or a fixed value if 0
seed_ok:        sta     ($22),y
                rts

rnd:
                sta     $22             ; store pointer to PRNG state
                stx     $23
                ldy     #$03
r_cpyloop:      lda     ($22),y         ; copy to ZP $fb - $fe
                sta     $fb,y
                dey
                bpl     r_cpyloop
                ldy     #$03            ; and shift left 3 bits
r_shiftloop:    asl     $fb
                rol     $fc
                rol     $fd
                rol     $fe
                dey
                bpl     r_shiftloop
                ldy     #$03
r_xorloop:      lda     ($22),y         ; xor with original state
                eor     $fb,y
                sta     ($22),y
                dey
                bpl     r_xorloop
                ldy     #$03
                lda     ($22),y
                lsr     a               ; MSB >> 1 gives ">> 25"
                ldy     #$00
                eor     ($22),y         ; xor with original state
                sta     ($22),y
                ldy     #$03            ; this is also value for "<< 24"
                eor     ($22),y         ; so xor with MSB
                sta     ($22),y
                tax                     ; use the two "higher" bytes as result ...
                dey
                lda     ($22),y         ; ... in A/X
                rts

使用示例：

main:
                lda     init
                bne     noinit
                lda     #<prng
                ldx     #>prng
                inc     init
                jsr     rnd_seed
noinit:         lda     #<prng
                ldx     #>prng
                jsr     rnd
                jmp     $bdcd        ; C64 BASIC routine output 16bit int in A/X

init:           .byte   $00
prng:           .res    4            ; 32bit PRNG state

- user2371524

---

我发现了这个LFSR https://www.maximintegrated.com/en/app-notes/index.mvp/id/4400 （代码在这里https://gist.github.com/nurpax/d32529b017f71fd0e77c89a9b5a5e328）。看起来这是一个很容易移植到6510的随机数生成器。我会试一试。 - Nurpax

这包括为LFSR塑造宏，以及一些来自通常良好来源（如VIC扫描线和CIA计时器）的示例种子代码。 - user2371524

我已经重新在6510中实现了C LFSR。令人惊讶的是，我至少可以让6510版本完全匹配我的C rng输出。https://gist.github.com/nurpax/d32529b017f71fd0e77c89a9b5a5e328#file-lfsr_6510-asm。不过还是很想看看你的更新 :) - Nurpax

@Nurpax，这很酷，谢谢你提供链接。也许你想添加自己的答案？:) 但据我所知，在C中，“经典”的PRNG不是LFSR，而是类似于这样的东西（我的MS-DOS实现）。 - user2371524

我从未为我的PRNG添加答案。我最终在其上运行了一个RNG评估套件，但它的表现并不好。可能是因为我的PRNG被调整为输出8-16位输出比特。 - Nurpax