Generating a screen of random colors as quickly as possible ..

Here you can ask questions or provide insights about how to use efficiently 6502 assembly code on the Oric.
User avatar
ibisum
Wing Commander
Posts: 1816
Joined: Fri Apr 03, 2009 8:56 am
Location: Vienna, Austria
Contact:

Generating a screen of random colors as quickly as possible ..

Post by ibisum »

In my SOUNDTOY project, which is a scratch/playground for a synthesizer project I (eventually) hope to create for the Oric, I've been playing around with different techniques for generating a screen full of Oric color, and having a few mixed results - so I thought I'd ask for some guru advice from the gang.

Repo here: https://github.com/seclorum/soundToy/

In toy.c is the function:

Code: Select all

void gen_rnd_colors(){

	int j;
	int k;

	volatile char r;
	char s;

	// s = peek(0x276); //LFSR
	// seed_lfsr(s);

	j = (unsigned int)HIRES_START;
	k = (unsigned int)HIRES_START + 160;

	do {

		// // Somewhat slow C-based implementation with assembly RNG - works
		do {
			r  = qrandomJ(peek(0x276)) % 255;
		} while (((r & 0x78) == 0x08 || (r & 0x78) == 0x18) || ((r & 0x78) == 0x88 || (r & 0x78) == 0x98));

		// Linear-feedback shift register method
		// r = lfsr_random();

		// table-based with 
		// r = fastbloop();

		// Chema's randgen:
		// r == randgen();

		poke(j, r);
		// printf("j: %x r: %x\n", j, r);

	} while (++j < k);

}

This is a C implementation of the concept - basically, get a random value, check if its one of the attribute values that would 'corrupt' the HIRES screen, if not - poke it to the HIRES screen address, if so, regenerate until a 'valid' value is produced, continue until the first 4 HIRES lines are filled with colors.

(To test this on an Oric/Emulator, load SOUNDTOY.TAP and press the 'G' key)

As you can see, I've got a few other functions commented out - these are my newbie attempts at putting the whole 'generate a valid value' code into assembly, to see which method produces the 'fastest' (or lets say 'quickest') colorful screen.

There is an LFSR-based method, and a lookup-table based implementation - basically I'm just hacking around, none of these methods actually work. I also found Chema's random number generator, and plugged it in, but this doesn't seem to work either.

Can anyone give me a quick shoulder-surf review and tell me what I'm doing wrong, vis a vis the assembly methods? The relevant files are 'fastbloop.s' for the lookup table method, and 'qrandom.s' for the LFSR- and Chema- methods. I feel I'm overlooking something terribly obvious here, but I've been looking at this code for too long this afternoon and am a bit bug-blind.

Here are the two files mentioned, for anyone who doesn't want to dig into the repo:

Code: Select all

; qrandom.s - experiment with different ways to generate 'valid' colour values randomly using a lookup table

; -----------------------------------------------------
; Random number table (pre-filtered values)
; Excludes values where (r & 0x78) == 0x08, 0x18, 0x88, 0x98

random_table:
    .byte $00, $01, $02, $03, $04, $05, $06, $07
    .byte $10, $11, $12, $13, $14, $15, $16, $17
    .byte $20, $21, $22, $23, $24, $25, $26, $27
    .byte $30, $31, $32, $33, $34, $35, $36, $37
    .byte $40, $41, $42, $43, $44, $45, $46, $47
    .byte $50, $51, $52, $53, $54, $55, $56, $57
    .byte $60, $61, $62, $63, $64, $65, $66, $67
    .byte $70, $71, $72, $73, $74, $75, $76, $77
    .byte $80, $81, $82, $83, $84, $85, $86, $87
    .byte $A0, $A1, $A2, $A3, $A4, $A5, $A6, $A7
    .byte $B0, $B1, $B2, $B3, $B4, $B5, $B6, $B7
    .byte $C0, $C1, $C2, $C3, $C4, $C5, $C6, $C7
    .byte $D0, $D1, $D2, $D3, $D4, $D5, $D6, $D7
    .byte $E0, $E1, $E2, $E3, $E4, $E5, $E6, $E7
    .byte $F0, $F1, $F2, $F3, $F4, $F5, $F6, $F7

    ; Seed for random number generation
seed: .byte $42
_fastbloop:

    lda $276           ; Load seed for random function
    sta seed

    lda #$02           ; Initialize high byte for storing in page $0200
    sta addr_high      ; Store in high byte variable
    lda #$00           ; Initialize low byte
    sta addr_low

    lda #$00           ; Initialize iteration counter
    sta iteration_count

start_loop:
    ldx #$00           ; X-register for indexing the table
    lda seed
    jsr _randgen        ; _qrandomJ      ; Call random generator
    tax                ; Store random result in X for indexing

    lda random_table, x ; Get a random value from the table

    ; Calculate the address to store the value
    lda addr_high       ; Load the high byte of the address
    sta temp_high       ; Store in temporary variable
    lda addr_low        ; Load the low byte of the address
    sta temp_low        ; Store in temporary variable

    ; Store the value at the address (absolute indexed)
    sta temp_store      ; Save the random value temporarily
    ldy #$00            ; Clear Y for addressing calculation

    ; Form full address manually
    lda temp_low        ; Load low byte of address
    sta $00             ; Save it to memory
    lda temp_high       ; Load high byte of address
    sta $01             ; Save it to memory

    ; Store value using absolute indexed addressing
    lda temp_store
    sta ($00), y        ; Store value at the address

    ; Increment the low byte of the address
    inc addr_low        
    lda addr_low        ; Check if low byte has overflowed
    bne continue_loop   ; If not overflowed, continue

    inc addr_high       ; Increment high byte if low byte overflowed

continue_loop:
    ; Increment the iteration counter
    inc iteration_count
    lda iteration_count
    cmp #$10            ; Set the loop to run for 16 iterations (or another value)
    beq done            ; If iterations reached the limit, exit the loop

    jmp start_loop      ; Otherwise, loop back

done:
    lda random_table, x  ; Return the last random value in A register
    rts                 ; Return to C with value in A


; Temporary variables for address calculations
temp_high:     .byte $00
temp_low:      .byte $00
temp_store:    .byte $00
addr_low:      .byte $00  ; High and low byte variables
addr_high:     .byte $00
iteration_count: .byte $00 ; Loop counter

Code: Select all

; qrandom.s - experiment with different ways to generate 'valid' colour values randomly

_qrandomJ
		ldy #8
		lda $0
_qrback
		asl
		rol $FF
		bcc _qrnoEor
		eor #$39
_qrnoEor
		dey
		bne _qrback
		sta $0
		cmp #0
		rts

_lfsr
   .byt 20,42        ; 16-bit LFSR storage (2 bytes)

; Seed the LFSR with an initial value
; Input: A = low byte, X = high byte (seed values)
_seed_lfsr:
    sta _lfsr          ; Store A in the low byte of LFSR
    stx _lfsr+1        ; Store X in the high byte of LFSR
    rts               ; Return

; LFSR random number generator
; Output: A = random number between 0–255, excluding 8-18 and 88-98
_lfsr_random:
    ; Load the current LFSR value
    lda _lfsr
    ldx _lfsr+1

    ; Perform the LFSR shift and feedback (16-bit LFSR with polynomial)
    lda _lfsr+1        ; Load high byte
    lsr               ; Shift right (low bit goes into carry)
    ror _lfsr          ; Rotate carry into low byte
    lda _lfsr+1        ; Reload high byte
    ror               ; Rotate carry into high byte
    lda _lfsr          ; Load low byte (A)
    eor #$B4          ; XOR feedback with a chosen polynomial value
    sta _lfsr          ; Store back into LFSR low byte

    ; Get the new random number (low byte of LFSR)
    lda _lfsr

    ; Check for exclusion range 8-18 (0x08–0x12)
check_exclusion:
    cmp #8
    bcc return_random   ; If number is below 8, it's valid
    cmp #19
    bcs check_next      ; If number is above 18, go to next check

    ; If we are here, the number is in the excluded range 8-18, generate again
    jmp _lfsr_random

check_next:
    ; Check for exclusion range 88-98 (0x58–0x62)
    cmp #88
    bcc return_random   ; If number is below 88, it's valid
    cmp #99
    bcs return_random   ; If number is above 98, it's valid

    ; If we are here, the number is in the excluded range 88-98, generate again
    jmp _lfsr_random

return_random:
    rts               ; Return with the valid random number in A

; Example usage:
; 1. Call 'seed_lfsr' to initialize the LFSR.
; 2. Call '_lfsr_random' to obtain random numbers, excluding 8-18 and 88-98.


// Chema's RNG from https://forum.defence-force.org/viewtopic.php?p=19108&hilit=random#p19108
; A real random generator... 
randseed .word $dead 	; will it be $dead again? 
_randgen
.(
   lda randseed     	; get old lsb of seed. 
   ora $308		; lsb of VIA T2L-L/T2C-L. 
   rol			; this is even, but the carry fixes this. 
   adc $304		; lsb of VIA TK-L/T1C-L.  This is taken mod 256. 
   sta randseed     	; random enough yet. 
   sbc randseed+1   	; minus the hsb of seed... 
   rol			; same comment than before.  Carry is fairly random. 
   sta randseed+1   	; we are set. 

check_exc:
    cmp #8
    bcc return_randgen   ; If number is below 8, it's valid
    cmp #19
    bcs check_nxt      ; If number is above 18, go to next check

    ; If we are here, the number is in the excluded range 8-18, generate again
    jmp _randgen

check_nxt:
    ; Check for exclusion range 88-98 (0x58–0x62)
    cmp #88
    bcc return_randgen   ; If number is below 88, it's valid
    cmp #99
    bcs return_randgen   ; If number is above 98, it's valid

    ; If we are here, the number generated is in the excluded range, so regenerate 
    jmp _randgen

return_randgen:
   rts			; see you later alligator. 
.)
User avatar
Dbug
Site Admin
Posts: 4821
Joined: Fri Jan 06, 2006 10:00 pm
Location: Oslo, Norway
Contact:

Re: Generating a screen of random colors as quickly as possible ..

Post by Dbug »

Why not simply do something like

Code: Select all

paper_color = 16+(random_value & 7);
User avatar
ibisum
Wing Commander
Posts: 1816
Joined: Fri Apr 03, 2009 8:56 am
Location: Vienna, Austria
Contact:

Re: Generating a screen of random colors as quickly as possible ..

Post by ibisum »

I want to fill the screen with as much color as possible.

Like this, but in Assembly (this is the C version):
soundtoy_colorscreen.png
Thats it in a nutshell, but I want to do it in Assembly, as quickly as possible ..

Anyway, working on another implementation ..

EDIT: your code suggestion produces this, which is neat but not quite all the color possible...

Code: Select all

paper_color = 16+(random_value & 7);
soundtoy_colorscreen2.png
User avatar
Chema
Game master
Posts: 3113
Joined: Tue Jan 17, 2006 10:55 am
Location: Gijón, SPAIN
Contact:

Re: Generating a screen of random colors as quickly as possible ..

Post by Chema »

I think that Dbug means that you do not generate numbers until you find one >16, but generate one get the lower bits and add 16. In asm could be jsr randgen; and #%111; ora #%10000
User avatar
ibisum
Wing Commander
Posts: 1816
Joined: Fri Apr 03, 2009 8:56 am
Location: Vienna, Austria
Contact:

Re: Generating a screen of random colors as quickly as possible ..

Post by ibisum »

Hmm .. you mean like this?

Code: Select all

; Called from C like this: 		r  = qrandomJ(peek(0x276)) % 255;

_qrandomJ
		ldy #8
		lda $0
_qrback
		asl
		rol $FF
		bcc _qrnoEor
		eor #$39
_qrnoEor
		dey
		bne _qrback
		sta $0
		and #%111
		ora #%10000
		cmp #0
		rts
.. tried it quickly, but it doesn't produce attributes in the same range that this code (admittedly inefficient) does:

Code: Select all

	do {
	 	r  = qrandomJ(peek(0x276)) % 255;
	 } while (((r & 0x78) == 0x08 || (r & 0x78) == 0x18) || ((r & 0x78) == 0x88 || (r & 0x78) == 0x98));

I guess I need to think about this a bit more rigorously, I'm a bit burned out on this already ..
Post Reply