This algorithm produces eventually all numbers between 0 and 255, but the sequence does not repeat until 59748 values. The routine has a 16bit state, but yields an 8 bit value. The randomization is a combination of an ASL, EOR and ADC command. The name AX+ is derived from comes from the ASL, XOR and addition operation. I have tested several other triplets of similar operations, this version here gave the longest period.

This version stores the seed as arguments and uses self-modifying code and requires only 15 bytes for the random function. The execution time is constant at 18 cycles and much faster than for example a 789-Xorshift.

The seeding function was tricky, since putting any two values into b1 and c1 comes with a 10% risk of ending up in a cycle with shorter period. Therefore, a seeding function is provided that takes an 8 bit value and generates a seed that is guaranteed to be in cycle with a period of 59748. Thus, there are 256 different states reachable after seeding.

In a test, I plotted the output of 51200 random values, which don't seem to reveal any visible patterns:

;; AX+ Tinyrand8
;; A fast 8-bit random generator with an internal 16bit state
;;
;; Algorithm, implementation and evaluation by Wil
;; This version stores the seed as arguments and uses self-modifying code
;; The name AX+ comes from the ASL, XOR and addition operation
;;
;; Size: 15 Bytes (not counting the set_seed function)
;; Execution time: 18 (without RTS)
;; Period 59748

rand8:	
b1=*+1
	lda #31
	asl
a1=*+1
	eor #53
	sta b1
	adc a1
	sta a1
	rts

; sets the seed based on the value in A
; always sets a1 and b1 so that a cycle with maximum period is chosen
; constants 217 and 21263 have been derived by simulation
set_seed:
	pha
	and #217
	clc
	adc #<21263
	sta a1
	pla
	and #255-217
	adc #>21263
	sta b1
	rts