Generating a pseudo-random bitstream in Rust using a Linear Feedback Shift Register

Published on: 2017-12-10

Home | Archive

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
$

randomled.gif

For more random LED fun, check out my article on implementing an LFSR on FPGA’s using completely Free Software tools.