Return to Revisions

As a generic remark, note that your FIFO always satisfies the invariant:

write_idx == (read_idx + size) % FIFO_CAPACITY

Thus, if you wanted to save some space, you could get rid of the write_idx property entirely and rewrite your push method as:

pub fn push(&mut self, item: u8) -> Result<(), &'static str> {
    if self.buffer_full() {
       Err("Buffer full.")
    } else {
        let write_idx = (self.read_idx + self.size) % FIFO_CAPACITY;
        self.buffer[write_idx] = item;

        self.size = self.size + 1;

        Ok(())
    }
}

(I hope that's syntactically correct, anyway... my Rust is rather, um, rusty and I haven't actually tested to see if the code above compiles. If not, please assume it's meant to be pseudocode.)

Note that storing only read_idx and write_idx and getting rid of size instead would not work, since there are two different situations where read_idx == write_idx: when the buffer is empty, and when it is full. Storing size explicitly lets you differentiate between those two cases, since an empty FIFO has size == 0 while a full one has size == FIFO_CAPACITY.

Also, since you say this code is intended for a microcontroller, it's worth keeping in mind that division and remainder can be rather slow operations on low-end microcontrollers.

If your FIFO capacity is always a power of two (like it is in your example code), and given that you're working with unsigned integers, it's likely that the compiler will be able to optimize the % FIFO_CAPACITY operation into a bitwise AND, in which case your current code is probably fine. Otherwise, however, you may want to consider manually replacing the remainder operation with a comparison, something like this:

fn increment_index(idx: usize) -> usize {
    if idx + 1 < FIFO_CAPACITY {
       idx + 1;
    } else {
       0;
    }
}

The compiler will probably not be able to make this optimization automatically, since this function will behave differently than your original if idx >= FIFO_CAPACITY. We know that can never actually happen in your code, but the compiler (probably) isn't that smart.

Of course, you should probably benchmark both versions of the code, and/or to examine the generated assembly code, to see what the compiler actually does with them and whether it actually makes any difference in practice. You might even consider using different code paths for the cases where FIFO_CAPACITY is a power of two, since in those cases using bit masking is probably faster.

Also, to combine the two optimizations above, I would recommend replacing

self.read_idx = Fifo::increment_index(self.read_idx);

in your pop method with something like

self.read_idx = Fifo::wrap_around(self.read_idx + 1);

where the wrap_around function would look e.g. like this:

fn wrap_around(idx: usize) -> usize {
    if idx < FIFO_CAPACITY {
       idx;
    } else {
       idx - FIFO_CAPACITY;
    }
}

This returns the same results as idx % FIFO_CAPACITY for all values of idx < 2*FIFO_CAPACITY, and thus allows you to also replace:

let write_idx = (self.read_idx + self.size) % FIFO_CAPACITY;

with:

let write_idx = Fifo::wrap_around(self.read_idx + self.size);