World's worst RNG.

I've been working on a USA medallion recently, and wanted to add a flickering effect. Something to make the lights twinkle randomly. That's not too hard on a real PC, where resources are cheap. But the ATTiny 44 I'm working on has only 128 bytes of ram. (That's 1/8th of a kilobyte, which is 1/1000th of a megabyte, which is itself 1/1000th of a gigabyte, which is what your computer has.)

Most of the RNG's around need 4 bytes or so for storage, and more for calculation. Mine doesn't! (It's also not very random, but you can't have everything for free.)

There's lots of room for improvement in the code, but it's lightweight on the heap, which is all I needed.

It's called a LSFR (Linear feedback shift register). Basically, it's a shift register (that's the x<<1 below) whose lowest bit is based on some of the other bits exclusive-or'ed together. No matter which bits you pick, you'll get a random-ish number machine. Some codes have longer cycles than others, though. Since I'm only using one byte, my maximum cycle length is 255. There just aren't any more numbers. The sequence below came from ... somewhere. Wikipedia has a list of sample polynomials for maximal-length generators.

The generator below implements the polynomial x7+x5+x4+x3+1 to create noise. (The superscripts represent a bit index - don't ask me why.)

x = x<<1 | (0x01 & (x>>7 ^ x>>5 ^ x>>4 ^ x>>3 ^ 1));And here's the fun part. Right shifts are inefficient on the AVR, but the assembly for my "RNG" is quite short. More to the point, it doesn't touch the scarce SRAM. Isn't that neat?

92c:   80 91 63 00     lds     r24, 0x0063 ; Load the variable from SRAM
 930:   28 2f           mov     r18, r24
 932:   22 1f           adc     r18, r18
 934:   22 27           eor     r18, r18
 936:   22 1f           adc     r18, r18
 938:   98 2f           mov     r25, r24
 93a:   92 95           swap    r25
 93c:   96 95           lsr     r25
 93e:   97 70           andi    r25, 0x07       ; 7
 940:   92 27           eor     r25, r18
 942:   28 2f           mov     r18, r24
 944:   22 95           swap    r18
 946:   2f 70           andi    r18, 0x0F       ; 15
 948:   92 27           eor     r25, r18
 94a:   28 2f           mov     r18, r24
 94c:   26 95           lsr     r18
 94e:   26 95           lsr     r18
 950:   26 95           lsr     r18
 952:   92 27           eor     r25, r18
 954:   90 95           com     r25
 956:   91 70           andi    r25, 0x01       ; 1
 958:   88 0f           add     r24, r24
 95a:   89 2b           or      r24, r25
 95c:   80 93 63 00     sts     0x0063, r24 ; save back to SRAM