State Machine

Now it is finally time to write some code. The swim template project contains some example code in main.spade, feel free to run swim upload to test it if you'd like. However, for this project, we won't need any of it, so once you are done playing around with it, remove all code from main.spade.

We'll start off by writing the state machine that generates the drive signals for the rest of the circuit. Before we do that though, it is a good idea to think about the input and output signals we want.

For simplicity, the state machine will not take any input control signals, it will start running as soon as the reset signal is turned off, and write data as fast as possible until the end of time.

Output type

The output is a bit more interesting. As stated before, we want the Finite State Machine (FSM) to emit information about what we are currently drawing.

For those unfamiliar, a Finite State Machine is less scary than the words make it seem. It is a way to do computation by describing a series of states and how and when to change between the states.

For example, if we want to build a circuit to toggle an LED whenever a short pulse arrives ¹, our FSM would consist of two states: On and Off. If no pulse arrives, the current state remains. If the pulse arrives, we transition from the current state to the opposite state.

It is usually convenient to look at small FSMs graphically, the following figure shows the states and transitions of the pulse example

¹

perhaps a pulse from a button, though some extra circuitry would be needed to turn the "short" pulse of a human pressing the button into a pulse that is "short" for an electronics circuit :)

Before we discuss our state machine further, we should consider what output we want it to generate. Initially, we might do something like this:

enum OutputControl<#IndexWidth> {
    /// Currently emitting the RET signal
    Ret,
    /// Currently emitting the specified bit of the color for LED `index`
    Led{index: int<IndexWidth>, bit: int<6>}
}

We make this enum generic over the width of the led indices to not waste bits and allow an arbitrary number of LEDs

The bit field is an int<6> because we want to be able to express 0..24. If spade had better unsigned support, we'd be able to use uint<5> :)

This enum has a few issues though, so let's make some improvements.

First, the data coming out of the color translation block will end up being quite similar to this enum, so we can use generics to share some code. The user will translate the index into a color, so we will allow arbitrary payload instead of that index

enum OutputControl<T> {
    /// Currently emitting the Ret signal
    Ret,
    /// Currently emitting the specified bit of the color for LED `index`
    Led{payload: T, bit: int<6>}
}

This is enough information to write the color translator, but to generate the output, it would be nice to have some more information. Specifically, because this is a time based interface, we could more easily generate the output waveforms if we knew how long we've been emitting the current bit. Let's add that to the enum

enum OutputControl<T> {
    /// Currently emitting the RET signal
    Ret,
    /// Currently emitting the specified bit of the color for LED `index`
    Led{payload: T, bit: int<6>, duration: int<12>}
}

If you are curious, the width of the duration field is 12 to support a counter counting from 0 to 1250. This was chosen because the total duration of a data bit is 1.25 microseconds, which takes 1250 clock cycles at 1 GHz, and we are unlikely to run our FPGA above that frequency. Better generics over clock frequencies is something that might happen down the line

State machine entity

We can finally stop talking about interfaces and write some actual code. Let's start off writing an entity where we can put the logic to generate the OutputControl enum. This entity will be generic over the index width as discussed previously, and will take a number of LEDs to control as a normal parameter.

In practice, it would be a lot nicer to set the number of LEDs at compile time too, but spade generics are not quite there yet.

entity state_gen<#IndexWidth>(
    clk: clock,
    rst: bool,
    num_leds: int<IndexWidth>
) -> OutputControl<int<IndexWidth>> {
    // TODO
}

Let's work on that // TODO next. Recall that when working in spade, we always describe the behaviour of our circuit between one clock cycle and the next. However, we want to implement an interface that is time dependent, so we need to do some thinking. In a high level language, we'd want to do something like

#![allow(unused_variables)]
fn main() {
while true {
    for t in 0..ret_duration {
        output = Ret;
        wait_clock_cycle;
    }

    for i in 0..num_leds {
        for bit in 0..24 {
            for t in 0..bit_duration {
                output = Led(i, bit, t)
                wait_clock_cycle;
            }
        }
    }
}
}

Unfortunately, loops are out of reach, so we will need to encode this logic in some other way. Most of the time, this is done by writing a state machine. The exact method is somewhat situation dependent and takes some practice. To be successful at this task, we have two basic constrains: we need enough information to know what state to jump to at all times, and we need enough information to know what output to generate. In spade, we'll almost always represent the states with an enum

enum State {
    // TODO
}

The RET signal

Let's start off with the first for loop to generate the RET signal. We need to keep track of how long we've been in RET, so we know when to jump over to the output generation loop. A good starting point is therefore a state, with a duration

enum State {
    Ret{duration: int<17>},
    // ...
}

The state_gen will need an instance of the state enum, which is updated at every clock cycle. A perfect use for the reg statement and match expression

entity state_gen<#IndexWidth>(
    clk: clock,
    rst: bool,
    num_leds: int<IndexWidth>
) -> OutputControl<int<IndexWidth>> {
    reg(clk) state reset(rst: State::Ret(0)) = match state {
        // Compute next state here
    };
}

What happened here? We have a register called state which we update by checking the state in the current clock cycle, to build a circuit that gives the state in the next. Since state depends on itself, it needs to be reset back to an initial value when the FPGA, which is why write reset(rst: State::Ret(0)). This will make the circuit send the RET signal to the LEDs when starting up, then operate as normal. We could have started emitting LED values too, but this makes the description easier and gives the LEDs a few microseconds to get up and running during power up.

How do we compute the next state in the Ret state? That depends on how long we have been in Ret already. If that time is longer than the minimum time in Ret, we can start emitting LED data, otherwise we'll stay in the Ret state. We'll write this logic as

entity state_gen<#IndexWidth>(
    clk: clock,
    rst: bool,
    num_leds: int<IndexWidth>
) -> OutputControl<int<IndexWidth>> {
    reg(clk) state reset(rst: State::Ret(0)) = match state {
        State::Ret(duration) => {
            if duration >= Tret {
                // First LED state
            }
            else {
                State::Ret(trunc(duration + 1))
            }
        },
        // ...
    };
}

You may be curious why we need trunc there. That's because spade does not implicitly cast away overflow. duration+1 is 1 bit larger than duration if it overflows. To make it fit back into our state, we truncate the result of the addition, since we know that we have chosen duration to be large enough for it not to be an issue.

Timing

The keen eyed might have noticed Tret there. What is its value? It represents the minimum time that we should emit the ret signal, but duration is in clock cycles. Eventually, Spade might support being generic over clock cycles and allow you to reason about time natively. For now, we need to compute how many clock cycles Tret is manually. This of course depends on the clock frequency, a value which varies between FPGAs. At the time of writing this guide, out of the boards that swim currently supports natively, there are 4 different clock frequencies, so we probably want to be generic over it in order to write a library.

Since we'll need a few more time dependent parameters down the line, we'll define a Timing struct which we pass to the modules, which contains the relevant timings. We might write something like this

struct Timing {
    Tret: int<17>,
    T0h: int<12>,
    T0l: int<12>,
    T1h: int<12>,
    T1l: int<12>,
    bit_time: int<12>,
}

However, now the user needs to know what those implementation dependent times are, which probably requires going to the data sheet. To make their life simpler, let's change it to

struct Timing {
    // 280 microseconds
    us280: int<17>,
    // 0.4 microseconds
    us0_4: int<12>,
    // 0.8 microseconds
    us0_8: int<12>,
    // 0.45 microseconds
    us0_45: int<12>,
    // 0.85 microseconds
    us0_85: int<12>,
    // 1.25 microseconds
    us1_25: int<12>,
}

and update our entity

entity state_gen<#IndexWidth>(
    clk: clock,
    rst: bool,
    num_leds: int<IndexWidth>
    t: Timing,
) -> OutputControl<int<IndexWidth>> {
    let t_ret = t.us280;
    reg(clk) state reset(rst: State::Ret(0)) = match state {
        State::Ret(duration) => {
            if duration >= t_ret {
                // First LED state
            }
            else {
                State::Ret(trunc(duration + 1))
            }
        },
        // TODO: next states
    };
    // TODO: Output
}

NOTE: If you've been following along with a datasheet, for example the first result on duck duck go, or the first result from google you may be confused by why we use 280 microseconds and not 50. It turns out that the manufacturers of the LEDs updated the protocol at some point without updating model numbers or datasheets. this took quite a few hours of debugging when the code worked on old LEDs, but not a new strip.

Bit signals

To generate the bit signals, i.e. the nested for loop in the example above, we need to keep track of 3 things: which LED we're working on, which bit on that LED we're working on, and how long we've been in that state. Essentially 1 variable per loop level. We'll extend the state enum to fit:

enum State<#IndexWidth> {
    Ret{duration: int<17>},
    Led{idx: int<IndexWidth>, bit: int<6>, duration: int<12>}
}

How do we want the logic to work? At the "innermost level", if we aren't done emitting the current bit, we increase the duration by 1. If the duration reaches the bit time, we move on to the next bit, and if we are done with all bits, we move on to the next LED. Finally, if we reached the last LED, we'll go back to the RET state.

In spade, we'll write that as

entity state_gen<#IndexWidth>(
    clk: clock,
    rst: bool,
    num_leds: int<IndexWidth>,
    t: Timing,
) -> OutputControl<int<IndexWidth>> {
    let t_ret = t.us280;
    let t_bit = t.us1_25;
    reg(clk) state reset(rst: State::Ret(0)) = match state {
        State::Ret(duration) => {
            if duration >= t_ret {
                State::Led(0, 0, 0)
            }
            else {
                State::Ret(trunc(duration + 1))
            }
        },
        State::Led$(idx, bit, duration) => {
            if duration == t_bit {
                if bit == 23 {
                    if idx == trunc(num_leds-1) {
                        State::Ret(0)
                    }
                    else {
                        State::Led$(idx: trunc(idx+1), bit: 0, duration: 0)
                    }
                }
                else {
                    State::Led$(idx, bit: trunc(bit+1), duration: 0)
                }
            }
            else {
                State::Led$(idx, bit, duration: trunc(duration + 1))
            }
        },
    };
    // TODO: Output
}

Spade supports passing arguments to units both by position, i.e. argument 1 is passed to parameter 1, 2 to 2 and so on, and also by name. To specify parameters by name, the calling parenthesis are preceded by $, i.e. State::Led$(idx, bit, duration: trunc(duration + 1)) says to pass the variable called idx to the parameter idx, bit to bit, and trunc(duration + 1) to duration. This works the same way as the rust struct initialisation syntax

Finally, generating the output signal can be done by another match statement. Since State and OutputControl are very similar in this case, the resulting match statement is not very complex:

    match state {
        State::Ret(_) => OutputControl::Ret(),
        State::Led$(idx, bit, duration) => OutputControl::Led$(payload: idx, bit, duration)
    }

Putting it all together, we end up with the following code:

enum OutputControl<T> {
    /// Currently emitting the RET signal
    Ret,
    /// Currently emitting the specified bit of the color for LED `index`
    Led{payload: T, bit: int<6>, duration: int<12>}
}

struct Timing {
    // 50 microseconds
    us280: int<17>,
    // 0.4 microseconds
    us0_4: int<12>,
    // 0.8 microseconds
    us0_8: int<12>,
    // 0.45 microseconds
    us0_45: int<12>,
    // 0.85 microseconds
    us0_85: int<12>,
    // 1.25 microseconds
    us1_25: int<12>,
}

enum State<#IndexWidth> {
    Ret{duration: int<17>},
    Led{idx: int<IndexWidth>, bit: int<6>, duration: int<12>}
}

entity state_gen<#IndexWidth>(
    clk: clock,
    rst: bool,
    num_leds: int<IndexWidth>,
    t: Timing,
) -> OutputControl<int<IndexWidth>> {
    let t_ret = t.us280;
    let t_bit = t.us1_25;
    reg(clk) state reset(rst: State::Ret(0)) = match state {
        State::Ret(duration) => {
            if duration >= t_ret {
                State::Led(0, 0, 0)
            }
            else {
                State::Ret(trunc(duration + 1))
            }
        },
        State::Led$(idx, bit, duration) => {
            if duration == t_bit {
                if bit == 23 {
                    if idx == trunc(num_leds-1) {
                        State::Ret(0)
                    }
                    else {
                        State::Led$(idx: trunc(idx+1), bit: 0, duration: 0)
                    }
                }
                else {
                    State::Led$(idx, bit: trunc(bit+1), duration: 0)
                }
            }
            else {
                State::Led$(idx, bit, duration: trunc(duration + 1))
            }
        }
    };
    match state {
        State::Ret(_) => OutputControl::Ret(),
        State::Led$(idx, bit, duration) => OutputControl::Led$(payload: idx, bit, duration)
    }
}

While we hope that the above code will work on the first try, that is rarely the case in practice. The next section will discuss how we can test our design