All Articles

Adapting a Bloom Filter to Rust

Neotrellis Bloom Filter Test Indicator
Neotrellis Bloom Filter Test Indicator

I like little productivity minders, particularly when they’re a separate “thing” from one of my screens (and less likely to get buried in window management). When one of my batchmates from Recurse Center made use of an Adafruit Neotrellis for running his test suites, I knew I wanted to eventually use his hack for my own purposes (plus the idea of using a Bloom filter to display unique tests sounded really cool!)

I bought the neotrellis board probably a year ago, but never had time to test out the original code. Once I did, and understood how it works (it’s written in Haskell), I wanted to challenge myself to rewrite it in Rust. I’ve made it about halfway through The Rust Book in my spare time, but I learn a lot faster when I have a project or end goal in mind (particularly one less vague than “get a software job that uses Rust”).

First I needed to prep my Neotrellis to get the proper libraries for running Bloohm. Adafruit recommends updating the Neotrellis bootloader and then installing these libraries. To use the same python file from Bloohm, you’ll need to additionally install

from the v7.x CircuitPython library (we haven’t updated to CircuitPython 8).

I also needed to adapt the shell scripts written for capturing the test commands, as it seems that every single time I plug in the neotrellis, I get a different address for the serial device. It ended up that my device usually had the pattern ending in 4 digits, but zsh doesn’t recognize standard regex, so I had to investigate using a glob pattern to get the same effect. I ended up with my shell commands differing a bit from the source code like so:

function test () {
        export thecmd="$*"
        export port=$(ls -t /dev/tty.usbmodem[0-9][0-9][0-9][0-9] | head -n 1)
        bloomrs -s $port -t y -d $PWD:A -c $thecmd
        time $* && fin || die;

function fin () {
        bloomrs -s $port -t g -d $PWD:A -c $thecmd

function die() {
        bloomrs -s $port -t r -d $PWD:A -c $thecmd

I’ve never worked with serial ports or command line tools in Rust. I used this tutorial to learn about writing CLI applications in Rust, and then used the clap crate to be a bit more explicit about the commands needed to run the bloom filter. I particularly like that you get documentation built in via your commented code.

The idea of the bloom filter is pretty simple. Run the unique string from the command and its current directory through a hash function, and then take the result and mod 32 to map the hash to a specific LED on the neotrellis. I struggled with this because the Haskell implementation was able to actually read in and reduce the giant hash number, and I couldn’t figure out how to consume the generic array with 32 bytes returned from the hash function (Sha256 in my case) to be able to take the modulo. I initially got by just taking the modulo of the last byte, since 32 is a factor of 256.

My first implementation in Rust was pretty inefficient and used a lot of different crates to get different hash functions. I paired with another Recurser to improve the code and ultimately cut down the program to only use Rust’s hash function from its standard library. We also managed to squash a bug with the serial port where running multiple commands in the same line would sometimes trigger a panic that the serial port was busy (which meant the yellow “in progress” LEDs were never fired). I’ve got an idea for using this on an external indicator that doesn’t require a specialized piece of hardware, but that’ll be a project for another week!

Github repo:

Working Bloom Filter Test Indicator

Published Feb 12, 2023

Striving to stay curious.