Chris' Blog.

My occasional thoughts on software development, careers, and updates on life in general.

SPSC

For real-time audio processing, it is necessary to communicate to your audio thread in such a way that the audio thread can never be blocked. Audio threads are hard-real-time: any delays will lead to loud pops/crackles/echoes. This is proper engineering! Fun!

So here’s my take on a simple C Lockless Single-Producer Single-Consumer queue that can be used for this (and other) applications.

This algorithm was written from a combination of reading existing C++ SPSC libraries (I couldn’t find any C ones), Wikipedia, the C atomics documentation, and Gemini. Even though Gemini helped, this was by no means remotely vibe coded, as will be explained later under the ‘heads or tails’ heading. Performance is good but note that there are faster options out there.

Have a look at the github repo: github.com/chrishulbert/spsc.

Theory

Basically we’re creating a ‘circular buffer’ where the reader chases the writer. The writer puts an item in the buffer if there’s a vacant position, and the reader consumes items from the buffer.

Seriously, go read the Wikipedia article on circular buffers, it’s surprisingly clear for a Wiki article, and does a better job than I at explaining the idea.

I’d also recommend skim-reading the references at the end of this article to understand the theory.

Heads or Tails?

These queues are often referred to as having a head and a tail. But there doesn’t seem to be a consensus as to whether you add to the tail and read from the head, or vice-versa. So there’s a terminology problem:

Linux says you write (insert) to the head: Queue.
Rust says you write (push) to the tail (back): VecDeque.
C++ STL says you write (push) to the tail (back): std::queue.
Java says you write (insert) at the tail: java.util.Queue.

In everday life, it is usual terminology that if a person is ‘at the head of the queue at the bank’ that they will be served next. Being served is analogous to being ‘read’ in our context. I suspect Linux is the one being unintuitive here.

Anyway, this is more important than a tomahto-tomayto thing, because this confusion makes it very difficult to use AI to make suggestions around queuing code, because half its training data treats head indices as writers, and the other half of its data treats heads as readers, so it tends to mix them up in code. AI aside, it makes it difficult to understand when reading examples!

Wikipedia avoids this confusion entirely by referring to them as the ‘write pointer’ and ‘read pointer’, so I’ll follow that terminology to make things unambiguous.

Circular representation in memory

Now since RAM isn’t circular, how do we represent this ring buffer?

It is a fixed-size array, with an index for where to write to, and an index for where to read from.

Since it is represented as a fixed-size array, this means that the buffer can be filled, and writes can fail. Since the writer is often the non-real-time side of the equation, if writes must not fail, some form of slower dynamic array could be used to keep track and retry later. But then you have to worry about “backpressure” when the consumer cannot keep up… 😀

It looks like this initially, for a size-4 queue. When the indices are equal (not necessarily 0, just equal) as follows, the queue is considered to be empty:

  ┌───┐
0 │   │ ← Reader index, Writer index
  ├───┤
1 │   │
  ├───┤
2 │   │
  ├───┤
3 │   │
  └───┘

To add item A, it is written at the current writer index, then the writer is incremented:

  ┌───┐
0 │ A │ ← Reader
  ├───┤
1 │   │ ← Writer
  ├───┤
2 │   │
  ├───┤
3 │   │
  └───┘

Then we add item B:

  ┌───┐
0 │ A │ ← Reader
  ├───┤
1 │ B │
  ├───┤
2 │   │ ← Writer
  ├───┤
3 │   │
  └───┘

Then we read. Since the reader index != writer, it considers it may read an item. It reads from the read index position, then increments the index:

  ┌───┐
0 │   │ A is read
  ├───┤
1 │ B │ ← Reader
  ├───┤
2 │   │ ← Writer
  ├───┤
3 │   │
  └───┘

We can read again, because the indices are unequal:

  ┌───┐
0 │   │ 
  ├───┤
1 │   │ B is read
  ├───┤
2 │   │ ← Reader, Writer
  ├───┤
3 │   │
  └───┘

There is nothing left to read, because the Reader == Writer:

  ┌───┐
0 │   │ 
  ├───┤
1 │   │
  ├───┤
2 │   │ ← Reader, Writer
  ├───┤
3 │   │
  └───┘

Now let’s add a few more, so we can see how it wraps around in a circular fashion. Let’s add X:

  ┌───┐
0 │   │ 
  ├───┤
1 │   │
  ├───┤
2 │ X │ ← Reader
  ├───┤
3 │   │ ← Writer
  └───┘

Now we add Y. Notice that the writer wraps around (circles) to index 0:

  ┌───┐
0 │   │ ← Writer
  ├───┤
1 │   │
  ├───┤
2 │ X │ ← Reader
  ├───┤
3 │ Y │
  └───┘

Now we add Z:

  ┌───┐
0 │ Z │ 
  ├───┤
1 │   │ ← Writer
  ├───┤
2 │ X │ ← Reader
  ├───┤
3 │ Y │
  └───┘

Even though the array above has an empty element, this queue is considered ‘full’ because (Writer + 1) % Length == Reader.

This ‘wasted’ element is a simple common technique to know when the queue is full, because if that extra element was filled, then Writer == Reader, which is the trigger for being considered empty, and another variable would be needed to disambiguate empty vs full.

To the best of my knowledge, this ‘wasted’ element isn’t reserved for multithreading safety, as the memory barriers (discussed later) solve that issue, it is just the way to determine full vs empty.

Atomics

Now: How is this to be made thread-safe?

Atomics are used for synchronising the threads in a lockless way, taking advantage of hardware CPU features to ensure neither thread will have to wait. In particular, this queue uses “release-acquire ordering”. More about atomics and release-acquire ordering can be read here.

In short:

An atomic_size_t foo; variable exists.
Values are ‘acquired’/loaded/read from this.
Values are ‘released’/stored/written to this.
When this acquire/release pattern is followed, the CPU guarantees: Any writes to other variables above the ‘release’ line of code will be visible to the ‘acquiring’ (reading) thread, they won’t be partially written or reordered by Out-Of-Order CPU optimisation or anything.

Thread Safety

Now we’re familiar with Atomics, how do they apply here?

A new entry is stored before the incremented write index is ‘released’.
The reader ‘acquires’ the write index, guaranteeing the data for the new entry is in a consistent state, because the entry was stored before the ‘release’.
The reader reads all the entries, then ‘releases’ the incremented read index.
The writer ‘acquires’ the read index, guaranteeing the reader has finished reading any queue entries, because the queue reading was completed before the ‘release’.

Code

Code is available at github.com/chrishulbert/spsc with benchmarking; however the important parts are here:

#include <stdatomic.h>

// You may want to have a 'type' for your queue entries:
typedef enum {
    QUEUE_ENTRY_TYPE_PLAY,
    QUEUE_ENTRY_TYPE_STOP,
} QueueEntryType;

// Put whatever you want to have in your queue entries here:
typedef struct {
    QueueEntryType type;
    int a;
    int b;
    int c;
} QueueEntry;

// If the queue size is a power of two eg 16,
// the '%' calculations later will be optimised to '& 0xF'.
#define QUEUE_SIZE 16

// This is the SPSC queue:
static struct {
    // Producer's index (writer thread, perhaps the game):
    atomic_size_t writeIndex;

    // Since the producer is the only thread that updates writeIndex,
    // it can use this 'mirror' as its source of truth,
    // thus no synchronisation is needed when reading.
    size_t writeIndexMirror; 

    // Consumer's index (reader thread, perhaps the audio thread).
    atomic_size_t readIndex;

    // Since the consumer is the only thread that updates readIndex,
    // it can use this 'mirror' as the source of truth,
    // thus no synchronisation is needed when reading.
    size_t readIndexMirror; 

    // The ring buffer.
    QueueEntry buffer[QUEUE_SIZE]; 
} queue;

// Write an item to the queue.
// To be called from the producer thread.
// Returns true on success.
bool queue_write(QueueEntry entry) {
    // Since only this thread updates the write index, use a non-atomic
    // mirror for a potentially-quicker read:
    size_t writeIndex = queue.writeIndexMirror;
    size_t nextWriteIndex = (writeIndex + 1) % QUEUE_SIZE;

    // Acquire the read index, so that any updates the reader made are visible.
    // Not that the reader makes any changes to the buffer, though.
    // Open to feedback here if this is necessary.
    size_t readIndex = atomic_load_explicit(
                           &queue.readIndex,
                           memory_order_acquire);

    // Check if queue is full.
    if (nextWriteIndex == readIndex) {
        return false; // Full!
    }

    // Store this entry in the queue.
    queue.buffer[writeIndex] = entry;
    
    // Use 'release' to ensure the entry in the buffer is visible
    // to the reader after it 'acquires' the write index.
    atomic_store_explicit(&queue.writeIndex, nextWriteIndex, memory_order_release);

    // Use this mirror as the source of truth, so it can be read next time
    // without needing synchronisation, since only this thread uses it.
    queue.writeIndexMirror = nextWriteIndex;

    return true; // Success, there was room!
}

// Read items from the queue, handling each one.
// To be called from the consumer thread.
void queue_read() {
    size_t readIndex = queue.readIndexMirror;

    // Acquire the write index from the writer thread.
    // Once acquired, any buffer updates made before updating the
    // write index will be visible to this thread.
    size_t writeIndex = atomic_load_explicit(
                            &queue.writeIndex, 
                            memory_order_acquire);

    // Loop through all entries:
    while (readIndex != writeIndex) {
        // Get this entry:
        QueueEntry* entry = &queue.buffer[readIndex];

        // Increment the read index, wrapping to 0 at the end of the queue buffer:
        readIndex = (readIndex + 1) % QUEUE_SIZE;
        
        // Deal with this entry:
        switch (entry->type) {
            case QUEUE_ENTRY_TYPE_PLAY:
                // Do something.
                break;

            case QUEUE_ENTRY_TYPE_STOP:
                // Do something.
                break;
        }
    }

    // Release the read index so the producer knows space has been cleared in
    // the buffer that it can use to store incoming entries:
    atomic_store_explicit(&queue.readIndex, readIndex, memory_order_release);

    queue.readIndexMirror = readIndex;
}

Benchmark

In my testing on a base model M4 Macbook Air:

Speed (lower is better): 14.886 nanos per entry
Throughput (higher is better): 67179 ops / millisecond

This is about 1/5th as fast as the 362Kops/sec that SPSCQueue achieves. I’m not sure why the speed difference? Perhaps because I’m running on macOS. Nevertheless, this is plenty fast enough for eg audio threads.

References

Thanks for reading, I pinky promise this was written by a human, not AI, hope you found this fascinating, at least a tiny bit, God bless!

Keen 4 Map

Recently I made Dopefish Decoder, a Rust tool for dumping the graphics from a very old-school Id software game: Commander Keen 4-6. It was a bit of work (fun work though) combining information from various sources to figure out how to read it all, so here’s the formats in rough EBNF! Further explanations are afterwards for the more complex elements.

Files

Graphics:
- graph_head
- graph_dict
- egagraph
Maps:
- map_head
- gamemaps

Non-file files

The map_head/graph_head/graph_dict “files” are actually present inside the game executable. Having said that, in many mods they are their own separate files. To get them, the executable first needs to be decompressed first, then these offsets used to extract them.

EBNF

// All multi-byte ints are little-endian.

graph_head = { graph offset }, graph length
graph length = 3 byte int // Matches length of egagraph file.
graph offset = 3 byte int 

graph_dict = { huffman node }
huffman node = node side, node side // Left, right.
node side = node value, node type
node value = byte
node type = leaf | node // Byte: 0 = leaf, else = node.

egagraph = { chunk }
egagraph = unmasked picture table chunk with header,
    masked picture table chunk with header,
    sprite table chunk with header,
    font a chunk with header,
    font b chunk with header,
    font c chunk with header,
    { unmasked picture chunk with header }, // Count from unmasked picture table.
    { masked picture chunk with header }, // Count from masked picture table.
    { sprite chunk with header }, // Count from sprite table.
    unmasked 8x8 tiles chunk without header, // One chunk for all tiles.
    masked 8x8 tiles chunk without header, // One chunk for all tiles.
    { unmasked 16x16 tile chunk without header },
    { masked 16x16 tile chunk without header },
    { text etc }
chunk without header = huffman encoded chunk
chunk with header = chunk decompressed length, huffman encoded chunk
chunk decompressed length = 4 byte int

picture table = { picture table entry }
picture table entry = width_pixels_divided_by_8, height_pixels
width_pixels_divided_by_8 = 2 byte int
height_pixels = 2 byte int

sprite table = { sprite table entry } // 18 bytes each.
sprite table entry = width_div_by_8, // All are 2 byte ints.
    height,
    x offset,
    y offset,
    clip left,
    clip top,
    clip right,
    clip bottom,
    shifts

image = picture | tile | sprite
unmasked image = red plane, green plane, blue plane, intensity plane
masked image = red plane, green plane, blue plane, intensity plane, mask plane

map_head = rlew key, { map header offset }
rlew key = 2 bytes
map header offset = 4 byte int // 0 means no map in this slot.

gamemaps = "TED5v1.0", { map }
map = map planes, map header
map header = background plane offset, // 38 bytes.
    foreground plane offset,
    sprite plane offset,
    background plane length,
    foreground plane length,
    sprite plane length,
    tile count width,
    tile count height,
    map name
plane offset = 4 byte int
plane length = 2 byte int
tile count = 2 byte int
map name = 16 bytes asciiz
map planes = background carmackized plane,
    foreground carmackized plane,
    sprite carmackized plane
carmackized plane = carmackized decompressed length, carmackized data
carmackized decompressed length = 2 byte int
carmackized data = carmack compressed(rlew plane)
rlew plane = rlew decompresed length, rlew data
rlew decompressed length = 2 byte int
rlew data = rlew compressed(decompressed plane)
decompressed plane = { map plane row }
map plane row = { map plane element }
map plane element = 2 byte int

Image planes

Images are stored in EGA planes.
Data is one whole-image plane, then the next plane, and so on.
Thus a certain pixel is represented 4-5 times across the data.
Masked image planes: RGBIM.
Red, Green, Blue, Intensity, Mask.
Unmasked image planes: RGBI.
When the mask bit = 1, it is a transparent pixel.
Each pixel in a plane is represented by 1 bit.
Inside each byte, pixels are left->right in big-endian order, 0x80 being leftmost.
All widths are multiples of 8 so you don’t have to worry about rows starting mid-byte.

Map elements

Map plane elements are ints representing which tile is displayed at that position.
Background plane corresponds to the unmasked tiles.
Foreground plane corresponds to the masked tiles.
Foreground plane elements are not always present. 0 means no element here. Which means that to represent the first masked tile, the value is 1. This means that you -1 the value to get the tile index.
Background plane always has an element, so the above -1 does not apply.

RLEW / Huffman / Carmackization

These compression techniques are big topics, far too complex for EBNF, and out of scope for an article like this.

They are are probably best described in code, which also has links to further reading. Hopefully the following code is readable enough to communicate the how-to:

Summary

I know this is the most random topic imaginable. Still, thanks for reading, I pinky promise this was written by a human, not AI, hope you found this fascinating if not useful, at least a tiny bit, God bless!

Angry Cloud from Commander Keen 4

A few weeks ago, there was a huge Cloudflare outage that knocked out half the internet for a while. As someone who has written a fair bit of Rust in my spare time (23KLOC according to cloc over the last few years), I couldn’t resist the urge to add some constructive thoughts to the discussion around the Rust code that was identified for the outage.

And I’m not going full Rust-Evangelism-Strike-Force here, as my pro-Swift conclusion will attest. Basically I’d just like to take this outage as an opportunity to recommend a couple tricks for writing safer Rust code.

The culprit

So, here’s the culprit according to Cloudflare’s postmortem:

pub fn fetch_features(
        &mut self,
        input: &dyn BotsInput,
        features: &mut Features,
) -> Result<(), (ErrorFlags, i32)> {
    features.checksum &= 0xffff_ffff_0000_0000;
    features.checksum |= u64::from(self.config.checksum);
    let (feature_values, _) = features
        .append_with_names(&self.config.feature_names)
        .unwrap();
    ...
}

Apparently it processes new configuration, and crashed at the unwrap because configuration with too many features was passed in.

Code Review

Keep in mind that I’m not seeing the greater context of this function, so the following may be affected by that, but here are my thoughts re the above code:

It returns a Result, with nothing for success case, and a combo of ErrorFlags and i32 for the failure case.
The presence of the &dyn for input indicates this uses dynamic dispatch, which means this isn’t intended as high-performance code. Which makes sense if this is just for loading configuration. Given that, they could have simply used anyhow’s all-purpose Result to make their lives simpler instead of this complex tuple for the error generic.
unwrap() is called. This is the big red flag, and something that should only generally be done in code that you are happy to have panic eg command line utilities, but less so for services. Swift’s equivalent is the force-unwrap operator !. When Swift was new, it was explained that the ! was chosen because it signifies danger, and stands out like a sore thumb in code reviews to encourage thorough examination. Rust’s unwrap isn’t as obvious at review time, and thus can sneak through unnoticed.
Since we’re already in a function that returns Result, it would be more idiomatic to use ? after the call to append_with_names, so that this function would hot-potato the error to the caller, instead of panicing.
If append_with_names returns an Option not a Result, ok_or(..)? would be a tidy option.

Alternative

Here I’ve changed the fetch_features function to be safer, with a couple options for how to gracefully handle this if append_with_names returns either a Result or an Option (it isn’t clear which it is from Cloudflare’s snippet, so I’ve done both). Note that I’ve also added some boilerplate around all this to keep the fetch_features code as similar as possible, but also commented out some stuff that’s less relevant.

fn main() {
    let mut fetcher = Fetcher::new();
    let mut features = Features::new();
    if let Err(e) = fetcher.fetch_features(&mut features) {
        // ... Gracefully handle the error here without panicing ...
        eprintln!("Error gracefully handled: {:#?}", e);
        return
    }
}

enum FeatureName {
    Foo,
    Bar,
}

struct Fetcher {
    feature_names: Vec<FeatureName>,
}

impl Fetcher {
    fn new() -> Self {
        Fetcher { feature_names: vec![] }
    }
    
    // This is the function Cloudflare said caused the outage:
    fn fetch_features(
        &mut self,
        // input: &dyn BotsInput,
        features: &mut Features,
    ) -> Result<(), (ErrorFlags, i32)> {
        // features.checksum &= 0xffff_ffff_0000_0000;
        // features.checksum |= u64::from(self.config.checksum);
        
        // If append_with_names returns a Result,
        // the question mark operator is safer than unwrap:
        let (feature_values, _) = features
            .append_with_names_result(&self.feature_names)?;
        
        // If append_with_names returns Option,
        // ok_or converts to a result, which forces you to be
        // explicit about what error is relevant,
        // which is then safely unwrapped using the question mark operator.
        let (feature_values, _) = features
            .append_with_names_option(&self.feature_names)
            .ok_or((ErrorFlags::AppendWithNamesFailed, -1))?;
        
        Ok(())
    }
}

#[derive(Debug)]
enum ErrorFlags {
    AppendWithNamesFailed,
    TooManyFeatures,
}

struct Features {
}

impl Features {
    fn new() -> Self {
        Features {}
    }
    
    // This is for if it returns a Result:
    fn append_with_names_result(
        &mut self,
        names: &[FeatureName],
    ) -> Result<(i32, i32), (ErrorFlags, i32)> {
        if names.len() > 200 { // Config is too big!
            Err((ErrorFlags::TooManyFeatures, -1))
        } else {
            Ok((42, 42))
        }
    }

    // This is for if it returns an Option:
    fn append_with_names_option(
        &mut self,
        names: &[FeatureName],
    ) -> Option<(i32, i32)> {
        if names.len() > 200 { // Config is too big!
            None
        } else {
            Some((42, 42))
        }
    }
}

Feel free to paste this into the Rust Playground and see if you have better suggestions :)

Suggestions

Instead of unwrap, the ? operator is a great option, particularly if you are already in a function that returns a Result, so please take advantage of such a situation.
ok_or is a great way to safely unwrap Options inside a Result function. If forces you to think about ‘what error should I return if there’s no value here?’.
Consider Swift! The exclamation point operator is a great way of drawing attention to danger in a code review, which is a fantastic piece of language ergonomics.

Summary

If anyone from Cloudflare is reading this, I hope this critique does not come across as unkind, much of my code is not amazingly bulletproof either! And kudos to Cloudflare for allowing us to see some of their code in the postmortem :)

Thanks for reading, I pinky promise this was written by a human, not AI, hope you found this useful, at least a tiny bit, God bless!

You can see older posts in the right panel, under 'archive'.

Chris' Blog.

Lockless FIFO SPSC (Single Producer Single Consumer) Queue in C 13 May, 2026

Theory

Heads or Tails?

Circular representation in memory

Atomics

Thread Safety

Code

Benchmark

References

Commander Keen 4-6 file formats 20 Dec, 2025

Files

Non-file files

EBNF

Image planes

Map elements

RLEW / Huffman / Carmackization

Summary

Cloudflare Rust Analysis 5 Dec, 2025

The culprit

Code Review

Alternative

Suggestions

Summary

Archive