#IFNDEF __lib_random
#DEFINE __lib_random 1

GOTO __skip_lib_random

// LFSR Random Number Generator
// Combined 16-bit (period 65535) and 15-bit (period 32767) generators
// Total period: ~2.1 billion (65535 * 32767 = 2,147,385,345)
//
// Based on Hanno Behrens' implementation (LGPL)
// Adapted for c65 by using local variable storage
//
// Usage:
//   BYTE rnd
//   rand(rnd)      // rnd now contains 0-255
//
// For ZP acceleration, change the variable declarations below
// from regular addresses to ZP addresses (e.g., @ $f6)

// Random state - initialized with default seeds
WORD rand_sr1 = $a55a
WORD rand_sr2 = $7653

// Initialize the random generator with default seeds
// Call once at startup (or just use rand_seed() with custom seed)
FUNC rand_init
  rand_sr1 = $a55a
  rand_sr2 = $7653
FEND

// Initialize with a custom seed value
// Good for seeding from user input timing
FUNC rand_seed({WORD seed})
  rand_sr1 = seed ^ $a55a
  rand_sr2 = seed ^ $7653

  // Ensure neither seed is zero
  IF rand_sr1 == 0
    rand_sr1 = $a55a
  ENDIF
  IF rand_sr2 == 0
    rand_sr2 = $7653
  ENDIF
FEND

// Internal: 16-bit LFSR with period 65535
// Taps: 10, 12, 13, 15 (polynomial)
FUNC rand_lfsr64k
  ASM
    lda |rand_sr1|+1
    asl
    asl
    eor |rand_sr1|+1
    asl
    eor |rand_sr1|+1
    asl
    asl
    eor |rand_sr1|+1
    asl
    rol |rand_sr1|
    rol |rand_sr1|+1
  ENDASM
FEND

// Internal: 15-bit LFSR with period 32767
// Taps: 13, 14 (polynomial)
FUNC rand_lfsr32k
  ASM
    lda |rand_sr2|+1
    asl
    eor |rand_sr2|+1
    asl
    asl
    ror |rand_sr2|
    rol |rand_sr2|+1
  ENDASM
FEND

// Get random byte (0-255)
// Result returned in 'result' parameter
FUNC rand(out:{BYTE result})
  rand_lfsr64k()
  rand_lfsr32k()

  ASM
    lda |rand_sr1|
    eor |rand_sr2|
    sta |result|
  ENDASM
FEND

// Get random byte in range [0, max)
// Uses rejection sampling for unbiased results
FUNC rand_max({BYTE max} out:{BYTE result})
  BYTE r
  BYTE mask

  // Calculate mask (smear highest bit down to get next power of 2 minus 1)
  mask = max - 1
  ASM
    lda |mask|
    lsr
    ora |mask|
    sta |mask|
    lsr
    lsr
    ora |mask|
    sta |mask|
    lsr
    lsr
    lsr
    lsr
    ora |mask|
    sta |mask|
  ENDASM

  // Rejection sampling loop
  WHILE 1
    rand(r)
    r = r & mask
    IF r < max
      result = r
      EXIT
    ENDIF
  WEND
FEND

LABEL __skip_lib_random

#IFEND