Generating a pseudo-random bitstream in Rust using a Linear Feedback Shift Register
In a previous article, we saw how easy it was to get up and running with Rust on the TI Tiva/Stellaris launchpad development boards. In this post, we will write a small Rust program which generates a random stream of 1’s and 0’s and use it to randomly blink an LED.
The Linear Feedback Shift Register
An LFSR is a shift register whose input bit is a function of some of the bits already present in the register. This wikipedia article describes the idea in detail. A common use of the LFSR is to generate pseudo-random bit sequences.
Here is a C program for a 16 bit Fibonacci LFSR (taken from the Wikipedia article):
# include <stdint.h>
int main(void)
{
uint16_t start_state = 0xACE1u; /* Any nonzero start state will work. */
uint16_t lfsr = start_state;
uint16_t bit; /* Must be 16bit to allow bit<<15 later in the code */
unsigned period = 0;
do
{
/* taps: 16 14 13 11; feedback polynomial: x^16 + x^14 + x^13 + x^11 + 1 */
bit = ((lfsr >> 0) ^ (lfsr >> 2) ^ (lfsr >> 3) ^ (lfsr >> 5) ) & 1;
lfsr = (lfsr >> 1) | (bit << 15);
++period;
} while (lfsr != start_state);
return 0;
}
Let’s convert this to an iterator in Rust:
struct Lfsr {
start: u16,
}
impl Iterator for Lfsr {
type Item = u16;
fn next(&mut self) -> Option<Self::Item> {
let bit = ((self.start >> 0) ^
(self.start >> 2) ^
(self.start >> 3) ^
(self.start >> 5)) & 1;
self.start = (self.start >> 1) | (bit << 15);
Some(bit)
}
}
fn new_lfsr(n: u16) -> Lfsr {
Lfsr { start: n }
}
It’s easy to plug this into a main function:
fn main() {
portf_init();
let led = red_led();
let l = new_lfsr(0x1234);
for bit in l {
if bit == 0 {
led.off();
} else {
led.on();
}
led::delay(10000);
}
}
Now, try it out on your Launchpad board:
$ git clone http://github.com/pcein/rust-lfsr
$ cd rust-lfsr
$ make debug; make flash
$
For more random LED fun, check out my article on implementing an LFSR on FPGA’s using completely Free Software tools.