rand: Add an example with PRNG

Signed-off-by: Miquel Sabaté Solà <mikisabate@gmail.com>

8 files changed, 595 insertions, 2 deletions

diff --git a/Makefile b/Makefile
index 930fc0b..e7e7901 100644
--- a/Makefile
+++ b/Makefile
@@ -18,14 +18,14 @@ clean:
 	@rm -rf out
 	@find . -type f -name "*.o" -delete
 	@find . -type f -name "*.nes" -delete
-	@mkdir -p out/basics out/scroll out/space out/fx
+	@mkdir -p out/basics out/scroll out/space out/fx out/rand
 
 .PHONY: deps
 deps:
 	@which $(CC65) >/dev/null 2>/dev/null || (echo "ERROR: $(CC65) not found." && false)
 
 .PHONY: build
-build: basics space scroll fx
+build: basics space scroll fx rand
 
 .PHONY: basics
 basics:
@@ -73,3 +73,8 @@ scroll:
 fx:
 	$(E) "	CC	 fx/blink"
 	$(Q) $(CC65) $(CCOPTS) fx/blink.s -C config/mmc3.cfg -o out/fx/blink.nes
+
+.PHONY: rand
+rand:
+	$(E) "	CC	 rand/rand"
+	$(Q) $(CC65) $(CCOPTS) rand/rand.s -C config/nrom.cfg -o out/rand/rand.nes
diff --git a/README.md b/README.md
index 5c4e800..380282e 100644
--- a/README.md
+++ b/README.md
@@ -40,6 +40,7 @@ The examples are distributed like this:
   bullets.
 - [scroll](./scroll/README.md): different scrolling tactics.
 - [fx](./fx/README.md): simple graphical effects that can be pulled off.
+- [rand](./rand/README.md): different strategies for producing random numbers.
 
 ## Other projects
 
diff --git a/assets/alphanum.chr b/assets/alphanum.chr
new file mode 100644
index 0000000..0233fbb
--- /dev/null
+++ b/assets/alphanum.chr
diff --git a/docs/rand.gif b/docs/rand.gif
new file mode 100644
index 0000000..8a2916a
--- /dev/null
+++ b/docs/rand.gif
diff --git a/rand/README.md b/rand/README.md
new file mode 100644
index 0000000..12f8902
--- /dev/null
+++ b/rand/README.md
@@ -0,0 +1,33 @@
+## Generating pseudo-random numbers
+
+Usually there is a requirement from NES/Famicom games to have access to random
+numbers. This is not entirely possible on the NES/Famicom since there is no
+hardware-specific implementation for any of this (i.e. as it happens on modern
+CPUs). But there's this common saying: if you can't make it, fake it! That's a
+common mentality when programming on the NES/Famicom due to its shortcomings in
+comparison to modern hardware.
+
+In this case, there are quite clever algorithms for generating **pseudo** random
+numbers. That is, numbers which are not absolutely random, but they are quite
+close to it.
+
+First of all, you need to generate a **seed**: from which number you start
+generating new random numbers. The approach taken here is the same as in many
+other games: the player is presented with a `Start` screen. On `nmi` code we
+count the frames until the player actually presses the `Start` button.
+Obviously, this is not really random, but unless you are on a TAS or you are an
+amazing player with frame-perfect input skills, it's good enough.
+
+All of this is implemented on the [rand.s](./rand.s) file. After the "Start"
+screen the player is presented with the algorithm being used and the random
+value that we got. The player can then press `Select` to change the algorithm
+being used, or press `A` to select a new number. There are a total of two PRNG
+algorithms being tested here:
+
+- [linear.s](./linear.s): A Galois linear feedback shift register (16-bit).
+- [precalc.s](./precalc.s): Indexing a pre-computed set of random numbers.
+
+These algorithms are better explained at the top comment from their respective
+files. All in all, we get the following result:
+
+![rand.gif](../docs/rand.gif)
diff --git a/rand/linear.s b/rand/linear.s
new file mode 100644
index 0000000..9ab7aa1
--- /dev/null
+++ b/rand/linear.s
@@ -0,0 +1,61 @@
+;;;
+;; Pseudo-random number implementation by a linear feedback shift register.
+;;
+;; This is one of the most common techniques developed on NES/Famicom games, and
+;; it's based on the algorithm from french mathematician Évariste Galois:
+;; https://en.wikipedia.org/wiki/Linear-feedback_shift_register#Galois_LFSRs.
+;; That is, we have a wider-than-8-bit register which keeps on shifting and
+;; "taps" on some bits whenever the carry flag is set. This sounds complicated
+;; but it really is not, and it can be further optimized as Brad Smith proved:
+;; https://github.com/bbbradsmith/prng_6502.
+;;
+;; All in all, the implementation here is based on the "basic" implementation
+;; from NesHacker: https://github.com/NesHacker/NES-RNG/blob/main/nes-rng.s; as
+;; it's easier to reason about. Other than that, refer to the NESDev wiki for
+;; more information: https://www.nesdev.org/wiki/Random_number_generator.
+
+;; Producing random numbers with a linear feedback shift register require at
+;; least 16-bit. In this case, we have the low byte which will be the end result
+;; upon each call to `linear_feedback_shift_register`; and the high byte which
+;; will be messed up to feed the low byte on each iteration. If we wanted more
+;; random numbers (i.e. how many random numbers can be generated before they
+;; start repeating all over again), we would need to add more bytes. For a
+;; simple 8-bit computer like the NES/Famicom, a 16-bit register for this is
+;; more than enough.
+.scope Linear
+    zp_register_lo = $40
+    zp_register_hi = $41
+.endscope
+
+;; Updates the 'a' register with a new random number as extracted from the
+;; linear feedback shift register referenced in the `Linear` scope.
+;;
+;; See: https://github.com/NesHacker/NES-RNG/blob/main/nes-rng.s
+.proc linear_feedback_shift_register
+    lda Linear::zp_register_hi
+    ldy #8
+
+@loop:
+    ;; Shift the least significant bit from the high byte to the low byte of the
+    ;; 16-bit register.
+    lsr
+    ror Linear::zp_register_lo
+
+    ;; Following the Galois algorithm, if the carry flag was set, then we need
+    ;; to tap on some specific bits of the low byte with an xor. Hence, if the
+    ;; carry flag is clear, skip the `eor` instruction.
+    bcc @skip_eor
+    eor #$B4
+
+@skip_eor:
+    ;; Save the current state of the high register and decrement the loop index.
+    sta Linear::zp_register_hi
+    dey
+    bne @loop
+
+    ;; The low byte now contains the shifted values from the loop. That's our
+    ;; final "random" number!
+    lda Linear::zp_register_lo
+
+    rts
+.endproc
diff --git a/rand/precalc.s b/rand/precalc.s
new file mode 100644
index 0000000..0b6da86
--- /dev/null
+++ b/rand/precalc.s
@@ -0,0 +1,55 @@
+;;;
+;; Pseudo-random number implementation by using a pre-calculated table.
+;;
+;; The implementation for this is extremely simple, as the given input parameter
+;; is used to index the random table below. Note that the table is 256 bytes
+;; long. This has the benefit that you never need to worry about bad indexing,
+;; and that the implementation is kept simple and fast. The inconvenience is
+;; that, obviously, you lose 256 bytes of data.
+;;
+;; From a programmer's happiness perspective, this solution also feels quite
+;; uninspired, but it gets the job done and there will be no surprises.
+;;
+;; From the player's perspective, of course, if they are messing with the code
+;; itself, it's pretty easy to manipulate the randomness of it all. As in, if
+;; they are using a TAS or they have mad frame-perfect input skills, they can
+;; predict the seed and get the value they want.
+;;
+;; All of the above being said, Final Fantasy is famous for using this technique
+;; for their random number generation, so it's not as unhinged as you would
+;; think.
+;;
+;; NOTE: to avoid the cost of having to have a 256 byte table, one idea I've had
+;; is that instead of using the `rand_table` we could use simply `main` (or
+;; better yet, `$8000`), as that spans more than 256 bytes. Moreover, the linker
+;; can have a configuration for random fill values, so any gaps could also have
+;; random bytes in it.
+
+;; Given a number passed via the 'a' register, it updates this same 'a' register
+;; with the next random number.
+;;
+;; NOTE: implemented by indexing a pre-calculated random table.
+.proc precalc
+    tax
+    lda rand_table, x
+    rts
+.endproc
+
+;; Pre-computed table, hopefully it feels random enough :)
+rand_table:
+    .byte $D7, $3A, $1C, $8F, $09, $B2, $E6, $54, $A3, $91, $2B, $F5, $78, $0D, $4C, $6E
+    .byte $FF, $C0, $52, $33, $6A, $E9, $9B, $1A, $47, $88, $7D, $21, $0E, $F4, $B3, $9C
+    .byte $15, $67, $A8, $41, $D2, $39, $80, $76, $C9, $E5, $0A, $1B, $5F, $22, $73, $DA
+    .byte $B4, $96, $3C, $E0, $8D, $F7, $2A, $05, $9E, $43, $11, $6D, $A7, $58, $C1, $32
+    .byte $28, $0F, $79, $BE, $51, $64, $9D, $A9, $3B, $71, $8E, $C6, $4A, $13, $F0, $27
+    .byte $E2, $5C, $06, $D3, $95, $B8, $4F, $70, $19, $A4, $6B, $38, $82, $C7, $5E, $01
+    .byte $F3, $2D, $9A, $65, $7C, $D1, $0B, $E8, $57, $36, $84, $1F, $B0, $92, $45, $AC
+    .byte $60, $7E, $A1, $53, $C8, $29, $D4, $FB, $07, $42, $E3, $99, $16, $8A, $3D, $C5
+    .byte $24, $B1, $6F, $03, $7A, $E7, $8C, $59, $D0, $46, $93, $1E, $A5, $2C, $B7, $F1
+    .byte $89, $55, $C3, $30, $62, $98, $04, $D6, $7F, $A0, $E4, $12, $3B, $81, $F9, $23
+    .byte $C4, $0D, $5A, $71, $9F, $B6, $2E, $85, $37, $A9, $18, $6C, $E1, $4B, $D9, $02
+    .byte $F8, $63, $B5, $40, $97, $0C, $7A, $51, $A2, $3E, $8F, $D5, $14, $69, $E0, $B8
+    .byte $4D, $77, $25, $9B, $0A, $F2, $3C, $86, $E9, $1F, $68, $A3, $50, $C1, $7D, $04
+    .byte $B2, $8E, $56, $1D, $73, $9C, $F5, $2A, $61, $D7, $09, $3E, $84, $A0, $E6, $1B
+    .byte $3F, $C8, $94, $05, $72, $D6, $A7, $4C, $1A, $5F, $B3, $29, $80, $E1, $6D, $9E
+    .byte $0C, $43, $F7, $8B, $52, $16, $A8, $3D, $91, $2B, $E5, $70, $C6, $4A, $D9, $F8
diff --git a/rand/rand.s b/rand/rand.s
new file mode 100644
index 0000000..abf944f
--- /dev/null
+++ b/rand/rand.s
@@ -0,0 +1,438 @@
+;;;
+;; Showcase different strategies for Random Number Generation (RNG).
+;;
+;; Refer to the README.md file for documentation. Here I have left comments
+;; whenever there's something "new" if you are coming from the `basics/`
+;; directory.
+
+.segment "HEADER"
+    .byte 'N', 'E', 'S', $1A
+    .byte $02, $01
+    .byte $00, $00
+
+.segment "VECTORS"
+    .addr nmi, reset, irq
+
+.segment "CHARS"
+.incbin "../assets/alphanum.chr"
+
+.segment "CODE"
+
+.include "../shared/ppu.s"
+.include "../shared/clear.s"
+.include "../shared/joypad.s"
+
+;; Different algorithms.
+.include "linear.s"
+.include "precalc.s"
+
+;; Number of algorithms for this game.
+ALGORITHM_SIZE = $02
+
+;; See Vars::zp_button_timer.
+KEY_TIMER = 15
+
+;; Variables used by this game.
+.scope Vars
+    ;; 0: "Press start" state; 1: "number generation" state.
+    zp_state = $30
+
+    ;; Timer for key presses. A button press will only be considered if the
+    ;; button timer is zero. Whenever that's the case, the code will reset the
+    ;; timer to this new value, and decrement it whenever a new press is found.
+    ;; Whenever we reach back to zero, then the button press will be considered
+    ;; again. All of this is because whenever the player presses a button, it
+    ;; actually presses it for more than one frame, and things can go crazy from
+    ;; this fact.
+    zp_button_timer = $31
+
+    ;; Algorithm that has been selected.
+    zp_algorithm = $32
+
+    ;; The random seed for this game. As described in the README.md file, this
+    ;; is actually a frame counter for the "Press start" state, and whenever the
+    ;; player hits "Start", it will be paused. That is, our random seed is
+    ;; simply the number of frames that the player took to press "Start" at the
+    ;; beginning.
+    ;;
+    ;; NOTE: it's not going to be initialized to get a more random feeling on
+    ;; real hardware from unknown RAM state.
+    zp_seed = $33
+
+    ;; The number to be displayed.
+    zp_number = $34
+.endscope
+
+;; Main function, this takes care of reading input, changing the state, and
+;; calling the relevant algorithm to get new numbers.
+.proc main
+    ;; Initialize all variables (except Vars::zp_seed as explained above).
+    lda #0
+    sta Vars::zp_state
+    sta Vars::zp_button_timer
+    sta Vars::zp_algorithm
+    sta Vars::zp_number
+
+    ;; Clear both screens. Yes, over the top, but it gets the job done.
+    CLEAR_SCREENS $20, $28
+
+    ;; Initialize palettes and show the "Press start" message.
+    jsr init_palettes
+    jsr show_init_screen
+
+    cli
+    lda #%10001000
+    sta $2000                   ; PPUCTRL
+    lda #%00011110
+    sta $2001                   ; PPUMASK
+
+@main_game_loop:
+    ;; Should we actually read the joypad? This is handled via the button timer
+    ;; as explained above.
+    lda Vars::zp_button_timer
+    beq @check_joypad
+    dec Vars::zp_button_timer
+    jmp @end
+
+@check_joypad:
+    ;; Yes! Then read the joypad.
+    READ_JOYPAD1
+
+    ;; What's the current game state?
+    lda Vars::zp_state
+    bne @check_change_algorithm
+
+    ;; "Press start" state. If the player is not pressing "Start", ignore
+    ;; everything and go to the end.
+    lda Joypad::zp_buttons1
+    and #Joypad::BUTTON_START
+    beq @end
+
+    ;; Reset the button timer.
+    lda #KEY_TIMER
+    sta Vars::zp_button_timer
+
+    ;; The random seed has a proper value and we can use that as a first random
+    ;; number.
+    lda Vars::zp_seed
+    sta Vars::zp_number
+
+    ;; The 'linear' algorithm actually disregards any parameters and needs a
+    ;; 16-bit register. Let's initialize this register with the current seed.
+    sta Linear::zp_register_lo
+    sta Linear::zp_register_hi
+
+    ;; Move into the next state.
+    inc Vars::zp_state
+
+    jmp @end
+
+@check_change_algorithm:
+    ;; We are in a running state. Check if the player is asking to change the
+    ;; algorithm.
+    lda Joypad::zp_buttons1
+    and #Joypad::BUTTON_SELECT
+    beq @check_a_button
+
+    ;; Reset the button timer.
+    lda #KEY_TIMER
+    sta Vars::zp_button_timer
+
+    ;; The player asked to change the algorithm. Do it now and go generate a new
+    ;; number with that.
+    ldx Vars::zp_algorithm
+    inx
+    cpx #ALGORITHM_SIZE
+    bne @store_algorithm
+    ldx #0
+@store_algorithm:
+    stx Vars::zp_algorithm
+    jmp @next_number
+
+@check_a_button:
+    ;; Is the player asking for a new number? If not go to the end.
+    lda Joypad::zp_buttons1
+    and #Joypad::BUTTON_A
+    beq @end
+
+    ;; Reset the button timer.
+    lda #KEY_TIMER
+    sta Vars::zp_button_timer
+
+@next_number:
+    ;; Setup parameters depending on the algorithm and actually call it.
+    ldx Vars::zp_algorithm
+    bne @precalc
+    jsr linear_feedback_shift_register
+    jmp @store_number
+@precalc:
+    lda Vars::zp_number
+    jsr precalc
+@store_number:
+    sta Vars::zp_number
+
+@end:
+    ;; And wait for the render to happen as it's done in any other example.
+    lda #%10000000
+    ora $20
+    sta $20
+@wait_for_render:
+    bit $20
+    bmi @wait_for_render
+
+    jmp @main_game_loop
+.endproc
+
+;; NMI code is pretty standard. I have added comments for the code which is
+;; specific to this game.
+.proc nmi
+    bit $20
+    bpl @next
+
+    pha
+    txa
+    pha
+    tya
+    pha
+
+    lda #$00
+    sta $2003                   ; OAMADDR
+    lda #$02
+    sta $4014                   ; OAMDMA
+
+    ;; What's the current game state?
+    lda Vars::zp_state
+    beq @seed_inc
+
+    ;; Running state. Print the current algorithm and number.
+    jsr print_algorithm
+    jsr print_value
+
+    ;; The running state is displayed on the other nametable. Update the PPU
+    ;; control register for this (it's of course stupid to update it every time,
+    ;; but I didn't feel like doing the proper thing of shadowing the PPU
+    ;; control register and update only on changes, etc.).
+    lda #%10001010
+    sta $2000                   ; PPUCTRL
+    bne @after_seed
+
+@seed_inc:
+    ;; "Press start" state: just increase the frame counter which is used as a
+    ;; seed.
+    inc Vars::zp_seed
+
+@after_seed:
+    bit $2002                   ; PPUSTATUS
+    lda #$00
+    sta $2005                   ; PPUSCROLL
+    sta $2005                   ; PPUSCROLL
+
+    lda #%01111111
+    and $20
+    sta $20
+
+    pla
+    tay
+    pla
+    tax
+    pla
+@next:
+    rti
+.endproc
+
+;; Show the "Alg: <algorithm>" message on screen.
+.proc print_algorithm
+    ;; "ALG: "
+    WRITE_PPU_DATA $298B, $1A
+    WRITE_PPU_DATA $298C, $25
+    WRITE_PPU_DATA $298D, $20
+    WRITE_PPU_DATA $298E, $34
+    WRITE_PPU_DATA $298F, $00
+
+    lda Vars::zp_algorithm
+    beq @linear
+
+    ;; "PRECALC"
+    WRITE_PPU_DATA $2990, $29
+    WRITE_PPU_DATA $2991, $2B
+    WRITE_PPU_DATA $2992, $1E
+    WRITE_PPU_DATA $2993, $1C
+    WRITE_PPU_DATA $2994, $1A
+    WRITE_PPU_DATA $2995, $25
+    WRITE_PPU_DATA $2996, $1C
+    rts
+
+    ;; "LINEAR "
+@linear:
+    WRITE_PPU_DATA $2990, $25
+    WRITE_PPU_DATA $2991, $22
+    WRITE_PPU_DATA $2992, $27
+    WRITE_PPU_DATA $2993, $1E
+    WRITE_PPU_DATA $2994, $1A
+    WRITE_PPU_DATA $2995, $2B
+    WRITE_PPU_DATA $2996, $00
+    rts
+.endproc
+
+;; Show the "Val: $<number>" message on screen.
+.proc print_value
+    ;; "VAL: $"
+    WRITE_PPU_DATA $29AB, $2F
+    WRITE_PPU_DATA $29AC, $1A
+    WRITE_PPU_DATA $29AD, $25
+    WRITE_PPU_DATA $29AE, $34
+    WRITE_PPU_DATA $29AF, $00
+    WRITE_PPU_DATA $29B0, $35
+
+    ;; Set the high byte on the 'y' register, and the low byte on the 'x'
+    ;; register.
+    lda #$F0
+    and Vars::zp_number
+    lsr
+    lsr
+    lsr
+    lsr
+    clc
+    adc #$10
+    tay
+    lda #$0F
+    and Vars::zp_number
+    clc
+    adc #$10
+    tax
+
+    ;; Display the actual number.
+    bit $2002
+    lda #$29
+    sta $2006
+    lda #$B1
+    sta $2006
+    sty $2007
+    stx $2007
+
+    rts
+.endproc
+
+;; Show the "Press start" message.
+.proc show_init_screen
+    ;; "PRESS"
+    WRITE_PPU_DATA $21AB, $29
+    WRITE_PPU_DATA $21AC, $2B
+    WRITE_PPU_DATA $21AD, $1E
+    WRITE_PPU_DATA $21AE, $2C
+    WRITE_PPU_DATA $21AF, $2C
+
+    ;; "START"
+    WRITE_PPU_DATA $21B1, $2C
+    WRITE_PPU_DATA $21B2, $2D
+    WRITE_PPU_DATA $21B3, $1A
+    WRITE_PPU_DATA $21B4, $2B
+    WRITE_PPU_DATA $21B5, $2D
+
+    rts
+.endproc
+
+;; Initialize palettes. A bit over the top since only two colors are used.
+.proc init_palettes
+    lda #$3F
+    sta $2006                   ; PPUADDR
+    lda #$00
+    sta $2006                   ; PPUADDR
+
+    ldx #0
+@load_palettes_loop:
+    lda palettes, x
+    sta $2007                   ; PPUDATA
+    inx
+    cpx #$20
+    bne @load_palettes_loop
+    rts
+palettes:
+    DEFAULT_COLOR = $0F
+
+    ;; Background
+    .byte DEFAULT_COLOR, $20, $FF, $FF
+    .byte DEFAULT_COLOR, $20, $FF, $FF
+    .byte DEFAULT_COLOR, $20, $FF, $FF
+    .byte DEFAULT_COLOR, $20, $FF, $FF
+
+    ;; Foreground
+    .byte DEFAULT_COLOR, $20, $FF, $FF
+    .byte DEFAULT_COLOR, $20, $FF, $FF
+    .byte DEFAULT_COLOR, $20, $FF, $FF
+    .byte DEFAULT_COLOR, $20, $FF, $FF
+
+    rts
+.endproc
+
+;;;
+;; NOTE: down below just boilerplate. Nothing special from the `basics/`
+;; examples.
+
+.proc reset
+    sei
+    cld
+
+    ldx #$40
+    stx $4017                   ; APU Frame Counter
+
+    ldx #$FF
+    txs
+
+    inx
+    stx $2000                   ; PPUCTRL
+    stx $2001                   ; PPUMASK
+    stx $4010                   ; APU DMC
+
+    bit $2002                   ; PPUSTATUS
+@vblankwait1:
+    bit $2002                   ; PPUSTATUS
+    bpl @vblankwait1
+
+    ldx #0
+    lda #0
+@ram_reset_loop:
+    sta $000, x
+    sta $100, x
+    sta $300, x
+    sta $400, x
+    sta $500, x
+    sta $600, x
+    sta $700, x
+    inx
+    bne @ram_reset_loop         ; if x overflows back to #00, then we are done.
+
+    lda #$EF
+@sprite_reset_loop:
+    sta $200, x
+    inx
+    bne @sprite_reset_loop
+
+    lda #$00
+    sta $2003                   ; OAMADDR
+    lda #$02
+    sta $4014                   ; OAMDMA
+
+@vblankwait2:
+    bit $2002                   ; PPUSTATUS
+    bpl @vblankwait2
+
+    lda #$3F
+    sta $2006                   ; PPUADDR
+    lda #$00
+    sta $2006                   ; PPUADDR
+
+    lda #$0F
+    ldx #$20
+@palettes_reset_loop:
+    sta $2007                   ; PPUDATA
+    dex
+    bne @palettes_reset_loop
+
+    jmp main
+.endproc
+
+.proc irq
+    rti
+.endproc
+