To avoid de-railing the choplifter thread, I’m opening this thread to discuss random number generators on the Arduboy.
Idea: Remove the random and regain 300 bytes of Flash
Here’s a simple test program:
#include <Arduboy2.h>
Arduboy2 arduboy;
unsigned long jsr;
void setup() {
arduboy.boot();
arduboy.clear();
power_adc_enable();
ADCSRA |= _BV(ADSC);
while (bit_is_set(ADCSRA, ADSC)) { }
jsr = ((unsigned long)ADC << 16) + micros();
power_adc_disable();
// randomSeed( seed ); // uncomment when testing regular random()
}
void drawPixel(int16_t x, int16_t y )
{
if (x < 0 || x > (WIDTH-1) || y < 0 || y > (HEIGHT-1))
{
return;
}
uint16_t row_offset;
uint8_t bit;
uint8_t row = (uint8_t)y / 8;
row_offset = (row*WIDTH) + (uint8_t)x;
bit = _BV((uint8_t)y % 8);
Arduboy2::sBuffer[row_offset] ^= bit;
}
// Marsaglia's XOR-shift RNG, sans left-shift
// http://www.cse.yorku.ca/~oz/marsaglia-rng.html
long xrandom( long min, long max ){
(jsr^=(jsr*(1<<17)), jsr^=(jsr>>13), jsr^=(jsr*(1<<5)));
return jsr%(max-min) + min;
}
// same as above, but with 8-bit input/output. 32-bit seed.
uint8_t xrand8( uint8_t min, uint8_t max ){
(jsr^=(jsr*(1<<17)), jsr^=(jsr>>13), jsr^=(jsr*(1<<5)));
return jsr%(max-min) + min;
}
void loop() {
uint8_t x, y;
/* * /
// standard random.
// total: 6606
x = random(0, 128);
y = random(0, 64);
/**/
/* * /
// total: 6280
x = xrandom(0, 128);
y = xrandom(0, 64);
/* */
/* */
// total: 6280
x = xrand8(0, 128);
y = xrand8(0, 64);
/* */
drawPixel(x, y);
arduboy.display();
}
The standard random produces white noise in this test (therefore passes), LCGs fail terribly (they form a visible pattern), and a XOR-shift RNG passes using less code than the standard random. The seed is still 32 bits in the 8-bit version because changing its size would impact the RNG’s period.
I tried it as a drop-in replacement in Karateka and freed 316 bytes, by means of a macro:
#define random( min, max ) xrand8( min, max )
Can it be made even smaller?