By Ben Nitkin on
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