Document rand.s thoroughly. Also save 1 byte, now 9007.

1 files changed, 109 insertions, 23 deletions

diff --git a/rand.s b/rand.s
index f1b2c72..89ee85c 100644
--- a/rand.s
+++ b/rand.s
@@ -1,9 +1,13 @@
+; Random number generator and wrappers for Taipan.
+
+; Originally I used POKEY's RANDOM register. It made for smaller code,
+; and seemed OK...
+; After some crude statistical analysis, I've decided to go with cc65's
+; rand() implementation. It seems to return more evenly distributed
+; results.
 
  .export _randl, _rand1to3
-; .export _randb, _randi, _randl
-; .export _rand1in5
-; .export _randbit
- .importzp sreg, tmp3
+ .importzp sreg
 
  .include "atari.inc"
 
@@ -13,6 +17,8 @@
   .code
  .endif
 
+;;; Wrappers for rand():
+
 ; unsigned long __fastcall__ randl(void);
 ; this returns the full range of an unsigned long, 0 to 2**32-1
 _randl:
@@ -21,9 +27,10 @@ _randl:
  jsr _rand
  sta sreg+1
  jsr _rand
- sta tmp3
+ pha
  jsr _rand
- ldx tmp3
+ tax
+ pla
  rts
 
 ; return 1, 2, or 3. equivalent to: randi()%3+1
@@ -36,6 +43,7 @@ _rand1to3:
 	ldx #0         ; now A is 1..3, but we have to force X to 0...
 	rts
 
+;;; rand() itself.
 ;;; This rand() function copied from cc65-2.19's libsrc/common/rand.s
 ;;; and modified for my nefarious purposes.
 ;;; srand() is not present (we don't use it).
@@ -77,14 +85,14 @@ _rand1to3:
 ;  multiplication, adding only 1 additional adc instruction.
 ;
 
- .export _rand, _randseed, _randseedl, _randseedh, _initrand, _addrandbits
+ .export _rand, _randseed, _initrand, _addrandbits
 
 .bss
 
 ; The seed. Not ANSI C compliant: we default to 0 rather than 1.
-_randseedl:
+; Yes, this means we get a constant stream of 0 from rand()
+; if we never seed it. No, we haven't forgot to seed it!
 _randseed:   .res 4
-_randseedh = _randseed+2
 
 .code
 
@@ -103,9 +111,69 @@ _rand:  clc
         sta     _randseed+3
         rts                     ; return bit (16-22,24-31) in (X,A)
 
+;;; End of cc65 code.
+
+; cc65's srand() is ANSI/ISO compliant... meaning it takes an int
+; argument, which on 6502 means only 16 bits for the initial seed.
+; So even though rand() generates a list of 4.3 billion nonrepeating
+; results, there would only be 65535 starting points. To keep things
+; less predictable, replace srand() with initrand() and addrandbits().
+; initrand() sets the initial 32-bit random state from 4 successive
+; reads of the Atari's POKEY pseudo-random register. The register
+; keeps clocking all the time, so essentially its state is dependent
+; on how long the Atari has been powered up. If we just used that for
+; a random seed, the game might be too predictable (a given copy of
+; the game will possibly take the same amount of time to load on the
+; same drive, plus the cartridge doesn't load from disk so it's 100%
+; deterministic). So addrandbits() adds entropy based on user actions:
+; characters typed and the timing of the typing, to 1 jiffy precision.
+
+; Initial plan was to generate a 32-bit seed value in the range 1 to
+; 2**32-1. However I fudged it a little: none of the bytes will ever
+; be initialized to 0, so it's really 1 to 255**4-1 (which is 98.5%
+; of the full range: still over 4 billion possibilities).
+
+;;; The next 2 paragraphs are speculative, don't relate to any actual code:
+
+; Note: I came up with an elaborate scheme to sample the KBCODE
+; register every scanline. Some users might actually be able to time
+; their typing to 1/60 sec precision, but nobody could do that at
+; scanline precision (a scanline is something like 64 microseconds).
+; We could use the raw scanline number as the random value, or even
+; do some calculations to get the color clock when the register
+; changed (no idea whether that's useful, whether POKEY's keyboard
+; hardware is that precise).
+; Unfortunately it probably won't work in emulators because they
+; generally process keyboard events once per frame. I didn't bother
+; to code it & test it because it's overkill anyway.
+
+; Note: I came up with a weird idea that might be useful to someone.
+; When you enable players and/or missiles, but don't enable their DMA,
+; they display garbage, which as I understand it is the contents of
+; the data bus being read by ANTIC while the 6502 is still running.
+; You could position a player or missile so one bit of it (bit 0 or
+; 7) overlaps the playfield, then loop every scanline and read the
+; collision register, shifting the bits into a result register. This
+; would get you a lot of potentially-random bits, but since the
+; 6502 is executing real code, they might not really be all that
+; random. I'd like to code it up and analyze the results someday, but
+; that's *way* outside the scope of this game!
+
+;;; End of speculations, back to code.
+
+; If you're trying to debug initrand() and/or addrandbits(), uncomment
+; the #define RANDSEED_TEST at the top of taipan.c
+
+; extern void __fastcall__ initrand(void);
 ; Initially the seed comes from sequential reads of POKEY's random
 ; register. It never returns 0 so we're guaranteed to have a usable
-; seed.
+; seed. However, the sequential reads and the fact that initrand()
+; gets called a constant amount of time after startup, means the
+; initial seed won't be very random by itself. It'll get mutated
+; by agetc() and addrandbits() as the user types the firm name. Even
+; if he only types a 1-character name followed by Return, that's still
+; going to give us a decent random seed.
+
 _initrand:
  ldx #3
 @l:
@@ -115,31 +183,53 @@ _initrand:
  bpl @l
  rts
 
+; extern void __fastcall__ addrandbits(char);
+; Called by init_game() after each character is typed.
+; The point of this is to turn the little bit of entropy in the
+; user's input and timing into more entropy from POKEY. The less
+; frequently you read RANDOM, the less correlated (and more random)
+; the results will be.
 ; Caller passes us a user keystroke as ATASCII, in A. We take bits 0
-; to 2, wait that many scanlines, get a random number from POKEY, and
+; to 2 [*], wait that many scanlines, get a random number from POKEY, and
 ; EOR it into the _randseed byte pointed to by the low 2 bits of the
 ; frame counter (RTCLOK+2).
+; Doing it this way, it's guaranteed that at least one byte of
+; _randseed will be modified by addrandbits(). It's likely that
+; more than one will be, but not guaranteed.
 ; Note that agetc() is still calling rand() on odd frames while all
-; this is going on.
+; this is going on, so the bytes in the seed might not be the ones
+; initrand() or addrandbits() put there!
+
 _addrandbits:
  and #$07
  tax
-@l1:
+@scanloop:    ; wait X scanlines
  sta WSYNC
  dex
- bpl @l1
- lda RTCLOK+2
- and #$03
+ bpl @scanloop
+ lda RTCLOK+2 ; the jiffy timer
+ and #$03     ; destination byte (offset 0-3 from _randseed)
  tax
  lda RANDOM
 @e:
- eor _randseed,x
- beq @e ; if the result is 0, undo the eor.
+ eor _randseed,x ; combine with the existing bits
+ beq @e          ; if the result is 0, undo the eor.
  sta _randseed,x
  rts
 
+; [*] I did some analysis of English text (various novels in ASCII
+; e-book form) and it appears that normally bits 0 and 2 are set on
+; 50% of the bytes on average (and clear the other 50% of course). Bit
+; 1 is only set 33% of the time on average. This is a result of the
+; frequency-of-use of the characters. Remember ETAOIN SHRDLU? Look at
+; bits 0-2 of each byte... Also spaces are very common, and bits 0-2
+; are of course all 0 there. So using bits 0-2 of the user's typing
+; is actually biased (we get 0 to 7, but the values 0, 1, 4, 5 occur
+; twice as often as 2, 3, 6, 7). This doesn't matter much, as we're
+; using the result as a scanline counter to delay a read from RANDOM:
+; the original bits don't end up in the seed.
 
- ;;; rest of file is commented out
+;;; rest of file is commented out, left for reference.
 
 ; RANDOM is the POKEY LFSR read address. According to the POKEY data
 ; sheet, this is the high 8 bits bits of a 17-bit LFSR (Atari calls it
@@ -148,10 +238,6 @@ _addrandbits:
 ; we're only reading 8 bits of it, we should be able to get a 0 (some
 ; of the other 9 bits would still be 1).
 
-; After some crude statistical analysis, I've decided to go with cc65's
-; rand() implementation. It seems to return more evenly distributed
-; results.
-
 ; Might use this at some point:
 ;_randbit:
 ; lda RANDOM