Embedded Data Structures and Algorithms Practice

Practice the embedded version of the problem

Generic algorithm questions become different when allocation is forbidden, interrupt latency matters, memory is shared with DMA, or a counter can wrap. Each challenge states the execution context, capacity, ownership, failure policy, and complexity target. This prevents elegant desktop solutions from being mistaken for safe firmware.

Trace before coding

A learner must identify the representation and invariant before writing loops. Queue head and tail positions, linked-list ownership, heap order, search boundaries, and parser state are drawn across operations. The trace exposes off-by-one errors and illegal transitions while they are still easy to correct.

Complete code means complete failure behavior

Solutions define return values, integer widths, overflow handling, aliasing assumptions, capacity limits, and behavior for invalid input. Tests cover minimum and maximum sizes, repeated values, wraparound, full and empty structures, partial records, and corruption. Interview prompts then require the learner to defend the tradeoffs rather than recite complexity notation.

What you will be able to do

• Select structures using bounded-memory and timing constraints
• Explain every solution using invariants
• Implement portable C with explicit edge behavior
• Test empty, full, rollover, duplicate, and malformed-input cases

Checked 32-bit field writer

Returns false for an invalid field. On success, changes only [lsb,lsb+width) and masks value to width.

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

bool field_write(uint32_t reg, uint8_t lsb, uint8_t width,
                 uint32_t value, uint32_t *out) {
    if (out == NULL || width == 0u || width > 32u ||
        lsb >= 32u || width > (uint8_t)(32u - lsb)) {
        return false;
    }
    uint32_t low_mask = width == 32u
        ? UINT32_MAX
        : ((UINT32_C(1) << width) - UINT32_C(1));
    uint32_t mask = low_mask << lsb;
    *out = (reg & ~mask) | ((value & low_mask) << lsb);
    return true;
}

• Validation makes every later shift count legal.
• The width==32 branch avoids shifting 1 by 32.
• Clear with reg & ~mask, then merge only masked input bits.

Cases the tests must cover

• width 1 at bit 0
• field spanning bit 31
• width 32 with lsb 0
• reject width 0 and lsb+width>32
• prove untouched bits remain equal

Pitfalls

• Do not return a sentinel uint32_t; every bit pattern is valid output.
• Use unsigned constants so shifts and complements have the intended width.

Calibration-table lower bound

Returns the first index i with table[i]>=query, or n when none exists. An empty table may use NULL.

#include <stddef.h>
#include <stdint.h>

size_t lower_bound_u16(const uint16_t *table, size_t n,
                       uint16_t query) {
    size_t lo = 0u;
    size_t hi = n;
    while (lo < hi) {
        size_t mid = lo + (hi - lo) / 2u;
        if (table[mid] < query) {
            lo = mid + 1u;
        } else {
            hi = mid;
        }
    }
    return lo;
}

• The active range is half-open [lo,hi).
• Everything before lo is too small; everything at or after hi is a candidate.
• lo+(hi-lo)/2 avoids lo+hi overflow and every branch shrinks the range.

Cases the tests must cover

• empty table
• query before first and after last
• exact first/last match
• duplicate values return first
• single element

Pitfalls

• Caller must supply a sorted table.
• Do not dereference table when n is zero.

Overlap-safe byte move

Copies n bytes as if through a temporary array, including overlapping source/destination ranges.

#include <stddef.h>
#include <stdint.h>

void *rb_memmove(void *dst, const void *src, size_t n) {
    unsigned char *d = (unsigned char *)dst;
    const unsigned char *s = (const unsigned char *)src;
    if (d == s || n == 0u) return dst;
    uintptr_t da = (uintptr_t)d;
    uintptr_t sa = (uintptr_t)s;
    if (da < sa || (da > sa && da - sa >= n)) {
        for (size_t i = 0u; i < n; ++i) d[i] = s[i];
    } else {
        for (size_t i = n; i != 0u; --i) d[i - 1u] = s[i - 1u];
    }
    return dst;
}

• Numeric byte addresses avoid relational comparison of unrelated pointers in the overlap decision.
• When destination starts inside the source range, copy backward so unread bytes are not overwritten.
• unsigned char may inspect and copy object representation bytes.

Cases the tests must cover

• no overlap
• dst==src
• overlap left
• overlap right
• n==0

Pitfalls

• Pointer-to-uintptr_t mapping is implementation-defined and uintptr_t is optional; this model targets embedded implementations that provide meaningful flat byte addresses.
• Both ranges must be valid for n bytes.

Bounded byte ring with explicit full status

Single-context or externally serialized ring. Capacity includes one reserved slot; push never overwrites unread data.

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

typedef struct {
    uint8_t *data;
    size_t capacity;
    size_t head;
    size_t tail;
} byte_ring_t;

bool ring_init(byte_ring_t *r, uint8_t *storage, size_t capacity) {
    if (r == NULL || storage == NULL || capacity < 2u) return false;
    *r = (byte_ring_t){ .data=storage, .capacity=capacity, .head=0u, .tail=0u };
    return true;
}

bool ring_push(byte_ring_t *r, uint8_t value) {
    size_t next = r->head + 1u;
    if (next == r->capacity) next = 0u;
    if (next == r->tail) return false;
    r->data[r->head] = value;
    r->head = next;
    return true;
}

bool ring_pop(byte_ring_t *r, uint8_t *out) {
    if (out == NULL || r->tail == r->head) return false;
    *out = r->data[r->tail];
    if (++r->tail == r->capacity) r->tail = 0u;
    return true;
}

• head names the next write slot and tail names the next read slot.
• head==tail is empty; next(head)==tail is full.
• Write data before moving head; read data before moving tail.

Cases the tests must cover

• capacity two
• fill then reject
• wrap head and tail
• FIFO order
• pop empty

Pitfalls

• This version is not automatically thread/ISR safe.
• Never add a shared count without synchronization.

C11 SPSC event queue

Exactly one producer calls push and one consumer calls pop. Capacity is a power of two and one slot is reserved.

#include <stdatomic.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

typedef uint32_t event_t;
typedef struct {
    event_t *data;
    size_t mask;
    _Atomic size_t head;
    _Atomic size_t tail;
} spsc_t;

bool spsc_init(spsc_t *q, event_t *storage, size_t capacity) {
    if (q == NULL || storage == NULL || capacity < 2u ||
        (capacity & (capacity - 1u)) != 0u) return false;
    q->data=storage; q->mask=capacity-1u;
    atomic_init(&q->head,0u); atomic_init(&q->tail,0u);
    return true;
}

bool spsc_push(spsc_t *q, event_t value) {
    size_t head=atomic_load_explicit(&q->head,memory_order_relaxed);
    size_t next=(head+1u)&q->mask;
    if (next==atomic_load_explicit(&q->tail,memory_order_acquire)) return false;
    q->data[head]=value;
    atomic_store_explicit(&q->head,next,memory_order_release);
    return true;
}

bool spsc_pop(spsc_t *q, event_t *out) {
    size_t tail=atomic_load_explicit(&q->tail,memory_order_relaxed);
    if (out==NULL || tail==atomic_load_explicit(&q->head,memory_order_acquire)) return false;
    *out=q->data[tail];
    atomic_store_explicit(&q->tail,(tail+1u)&q->mask,memory_order_release);
    return true;
}

• Single-writer ownership avoids atomic RMW on the indices.
• Release publishes the preceding slot write; acquire observes it before the slot read.
• The mask replaces modulus only because capacity is validated as a power of two.

Cases the tests must cover

• publish/consume one event
• wrap repeatedly
• full reject preserves data
• FIFO sequence
• stress with one producer and one consumer

Pitfalls

• Not MPSC or MPMC.
• C atomics may not be lock-free for every type/target; verify toolchain and ISR rules.

Fixed-block pool with allocation bitmap

Manages at most 32 equal blocks in caller storage. Rejects foreign, misaligned, and double-freed pointers.

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

typedef struct block { struct block *next; } block_t;
typedef struct { uint8_t *base; size_t block_size,count; block_t *free; uint32_t used; } pool_t;

bool pool_init(pool_t *p, void *memory, size_t bytes,
               size_t block_size, size_t count) {
    size_t align = _Alignof(block_t);
    if (!p || !memory || count==0u || count>32u || block_size<sizeof(block_t) ||
        (uintptr_t)memory % align != 0u || block_size % align != 0u ||
        count > bytes / block_size) return false;
    p->base=memory; p->block_size=block_size; p->count=count; p->free=NULL; p->used=0u;
    for (size_t i=count; i!=0u; --i) {
        block_t *b=(block_t *)(p->base+(i-1u)*block_size);
        b->next=p->free; p->free=b;
    }
    return true;
}

void *pool_alloc(pool_t *p) {
    if (!p || !p->free) return NULL;
    block_t *b=p->free; p->free=b->next;
    size_t slot=((uint8_t *)b-p->base)/p->block_size;
    p->used|=UINT32_C(1)<<slot; return b;
}

bool pool_free(pool_t *p, void *ptr) {
    if (!p || !ptr) return false;
    uintptr_t base=(uintptr_t)p->base, address=(uintptr_t)ptr;
    if (address<base || address-base>=p->count*p->block_size ||
        (address-base)%p->block_size!=0u) return false;
    size_t slot=(address-base)/p->block_size; uint32_t bit=UINT32_C(1)<<slot;
    if ((p->used&bit)==0u) return false;
    p->used&=~bit; block_t *b=ptr; b->next=p->free; p->free=b; return true;
}

• The free list lives inside currently unused blocks.
• A bitmap records allocation state so double-free is rejected.
• Alignment and division checks make every block a valid block_t without overflowing geometry arithmetic.

Cases the tests must cover

• allocate all then exhaust
• free/reuse
• foreign pointer
• interior pointer
• double free
• invalid geometry and alignment

Pitfalls

• Payload types may require stricter alignment than block_t; choose block geometry for the strongest stored type.
• Concurrent or ISR access needs a critical section or a separately proven lock-free design.

Fixed timer min-heap

Caller provides capacity. Earlier deadline wins; equal deadlines use lower sequence for deterministic FIFO order.

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

typedef struct { uint32_t deadline,sequence; uint16_t id; } timer_t;
typedef struct { timer_t *items; size_t size,capacity; } timer_heap_t;
static bool before(timer_t a,timer_t b){return a.deadline<b.deadline || (a.deadline==b.deadline && a.sequence<b.sequence);}
static void swap(timer_t *a,timer_t *b){timer_t t=*a;*a=*b;*b=t;}

bool timer_push(timer_heap_t *h,timer_t value){
    if(!h||!h->items||h->size==h->capacity)return false;
    size_t i=h->size++; h->items[i]=value;
    while(i>0u){size_t p=(i-1u)/2u;if(!before(h->items[i],h->items[p]))break;swap(&h->items[i],&h->items[p]);i=p;}
    return true;
}

bool timer_pop(timer_heap_t *h,timer_t *out){
    if(!h||!out||h->size==0u)return false;
    *out=h->items[0]; h->items[0]=h->items[--h->size]; size_t p=0u;
    for(;;){size_t l=2u*p+1u,r=l+1u,b=p;if(l<h->size&&before(h->items[l],h->items[b]))b=l;if(r<h->size&&before(h->items[r],h->items[b]))b=r;if(b==p)break;swap(&h->items[p],&h->items[b]);p=b;}
    return true;
}

• The comparator defines a total deterministic order.
• Push repairs only the new node's ancestor path.
• Pop repairs only the replacement root's descendant path.

Cases the tests must cover

• ascending/descending insertion
• equal deadline sequence order
• capacity full
• pop empty
• heap invariant after every operation

Pitfalls

• Plain unsigned deadline comparison is not wrap-safe; use a documented horizon comparator when deadlines wrap.
• Cancelable heaps must update ID→index maps on every swap.

Bounds-safe TLV iterator

Parses one-byte type/length records and invokes a callback only for complete values. Stops on first malformed record.

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

typedef bool (*tlv_fn)(uint8_t type,const uint8_t *value,size_t length,void *ctx);
typedef enum { TLV_OK,TLV_TRUNCATED,TLV_REJECTED } tlv_status_t;

tlv_status_t tlv_parse(const uint8_t *buf,size_t len,tlv_fn visit,void *ctx){
    if((buf==NULL&&len!=0u)||visit==NULL)return TLV_REJECTED;
    size_t offset=0u;
    while(offset<len){
        size_t remaining=len-offset;
        if(remaining<2u)return TLV_TRUNCATED;
        uint8_t type=buf[offset++]; uint8_t length=buf[offset++];
        remaining=len-offset;
        if((size_t)length>remaining)return TLV_TRUNCATED;
        if(!visit(type,&buf[offset],length,ctx))return TLV_REJECTED;
        offset+=(size_t)length;
    }
    return TLV_OK;
}

• Every header and payload access is preceded by a remaining-length proof.
• Subtraction avoids overflowing offset+length in the check.
• The callback can enforce singleton fields and semantic ranges without the parser knowing the schema.

Cases the tests must cover

• empty input
• zero-length value
• truncated header
• declared length beyond buffer
• callback rejection
• multiple complete records

Pitfalls

• Do not retain value pointers after the input buffer lifetime ends.
• A production schema should commit output only after all required fields validate.

Bounded topological sort

Sorts a directed graph of at most 32 vertices represented by adjacency bitmasks. Returns false for a cycle or invalid edge.

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

bool topo_sort(const uint32_t *edges,size_t vertices,uint8_t *order){
    if(!edges||!order||vertices==0u||vertices>32u)return false;
    uint8_t indegree[32]={0}; uint8_t queue[32]; size_t head=0u,tail=0u,out=0u;
    uint32_t valid=vertices==32u?UINT32_MAX:((UINT32_C(1)<<vertices)-1u);
    for(size_t u=0u;u<vertices;++u){
        if((edges[u]&~valid)!=0u)return false;
        for(size_t v=0u;v<vertices;++v)if((edges[u]&(UINT32_C(1)<<v))!=0u)++indegree[v];
    }
    for(size_t v=0u;v<vertices;++v)if(indegree[v]==0u)queue[tail++]=(uint8_t)v;
    while(head<tail){size_t u=queue[head++];order[out++]=(uint8_t)u;uint32_t row=edges[u];for(size_t v=0u;v<vertices;++v)if((row&(UINT32_C(1)<<v))!=0u&&--indegree[v]==0u)queue[tail++]=(uint8_t)v;}
    return out==vertices;
}

• indegree counts unmet prerequisites for each vertex.
• The queue owns exactly the zero-indegree vertices ready to emit.
• If fewer than V are emitted, remaining vertices participate in or depend on a cycle.

Cases the tests must cover

• single vertex
• chain
• diamond dependencies
• disconnected DAG
• self-loop
• multi-node cycle
• edge outside vertex range

Pitfalls

• This representation intentionally favors tiny dense embedded graphs; adjacency lists give O(V+E) for larger sparse graphs.
• Returning false detects a cycle but does not enumerate one.

Monotonic-deque sliding maximum

Writes one maximum for each complete window. Caller supplies k index slots; input and output must not overlap.

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

bool sliding_max(const int16_t *in,size_t n,size_t k,
                 int16_t *out,size_t out_cap,size_t *deque,
                 size_t deque_cap,size_t *written){
    if(!written)return false;
    *written=0u;
    if(k==0u||k>n)return true;
    size_t need=n-k+1u;
    if(!in||!out||!deque||out_cap<need||deque_cap<k)return false;
    size_t front=0u,count=0u;
    for(size_t i=0u;i<n;++i){
        while(count>0u&&deque[front]+k<=i){front=(front+1u)%deque_cap;--count;}
        while(count>0u){
            size_t back=(front+count-1u)%deque_cap;
            if(in[deque[back]]>in[i])break;
            --count;
        }
        deque[(front+count)%deque_cap]=i; ++count;
        if(i+1u>=k)out[(*written)++]=in[deque[front]];
    }
    return true;
}

• Deque indices always increase logically and remain inside the current window.
• Their values decrease from front to back, so the front is the maximum.
• A circular k-slot index deque keeps fixed workspace while every index enters and leaves once.

Cases the tests must cover

• k zero and k>n
• k one
• duplicates
• strictly rising/falling
• negative samples
• insufficient output/deque capacity

Pitfalls

• Define aliasing policy explicitly; this version requires disjoint input/output.
• Modulo may be expensive on tiny MCUs; a power-of-two deque can use a validated mask.

Non-blocking debounce FSM

Consumes timestamped raw samples and emits one event only after a candidate level remains unchanged for debounce_ticks.

#include <stdbool.h>
#include <stdint.h>

typedef enum { BUTTON_NONE,BUTTON_PRESSED,BUTTON_RELEASED } button_event_t;
typedef struct { bool stable,candidate; uint32_t candidate_since,debounce_ticks; } debounce_t;

void debounce_init(debounce_t *d,bool initial,uint32_t ticks,uint32_t now){
    d->stable=initial; d->candidate=initial; d->candidate_since=now; d->debounce_ticks=ticks;
}

button_event_t debounce_update(debounce_t *d,bool raw,uint32_t now){
    if(raw!=d->candidate){d->candidate=raw;d->candidate_since=now;return BUTTON_NONE;}
    if(raw==d->stable)return BUTTON_NONE;
    if((uint32_t)(now-d->candidate_since)<d->debounce_ticks)return BUTTON_NONE;
    d->stable=raw;
    return raw?BUTTON_PRESSED:BUTTON_RELEASED;
}

• A raw transition starts a new candidate interval rather than blocking.
• Unsigned subtraction measures elapsed ticks across one wrap.
• Only a sustained candidate changes stable state and emits an event.

Cases the tests must cover

• clean press/release
• bounce restarts timer
• tick wrap
• zero debounce
• repeated stable samples emit once

Pitfalls

• debounce_ticks must be less than half the uint32_t range for unambiguous elapsed-time reasoning.
• Sampling cadence determines when the threshold is observed.

DMA ping-pong ownership machine

Models legal buffer ownership transitions. Platform code must serialize ISR/task access and perform required DMA cache maintenance separately.

#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

typedef enum { BUF_FREE,BUF_DMA,BUF_READY,BUF_CPU } buffer_owner_t;
typedef struct { buffer_owner_t owner[2]; uint32_t overruns,illegal; } pingpong_t;

void pingpong_init(pingpong_t *p){p->owner[0]=BUF_FREE;p->owner[1]=BUF_FREE;p->overruns=0u;p->illegal=0u;}
bool dma_begin(pingpong_t *p,size_t id){if(id>=2u||p->owner[id]!=BUF_FREE){++p->illegal;return false;}p->owner[id]=BUF_DMA;return true;}
bool dma_complete(pingpong_t *p,size_t id){if(id>=2u||p->owner[id]!=BUF_DMA){++p->illegal;return false;}p->owner[id]=BUF_READY;return true;}
bool cpu_take(pingpong_t *p,size_t *id){if(!id)return false;for(size_t i=0u;i<2u;++i)if(p->owner[i]==BUF_READY){p->owner[i]=BUF_CPU;*id=i;return true;}++p->overruns;return false;}
bool cpu_release(pingpong_t *p,size_t id){if(id>=2u||p->owner[id]!=BUF_CPU){++p->illegal;return false;}p->owner[id]=BUF_FREE;return true;}

• Each buffer occupies exactly one ownership state.
• DMA completion transfers DMA→READY; task take transfers READY→CPU.
• Release returns CPU→FREE so DMA may reuse the buffer.

Cases the tests must cover

• complete before begin rejected
• normal cycle
• double take/release rejected
• slow consumer overrun telemetry
• independent alternating buffers

Pitfalls

• Portable C state changes alone do not make ISR/task access atomic or ordered.
• DMA mapping, cache clean/invalidate, and device barriers are platform-specific integration steps.

Kernighan popcount

Returns the number of set bits in a 32-bit word. Loops once per set bit; zero input returns zero.

#include <assert.h>
#include <stdint.h>

/* Brian Kernighan's trick: v & (v-1) clears the lowest set bit,
   so the loop runs once per 1-bit instead of once per position. */
uint8_t popcount32(uint32_t v)
{
    uint8_t n = 0U;
    while (v != 0U) {
        v &= v - 1U;
        ++n;
    }
    return n;
}

int main(void)
{
    assert(popcount32(0U) == 0U);
    assert(popcount32(1U) == 1U);
    assert(popcount32(0x80000000U) == 1U);
    assert(popcount32(0xA5A5A5A5U) == 16U);
    assert(popcount32(0xFFFFFFFFU) == 32U);
    return 0;
}

• v-1 flips the lowest set bit and every bit below it; ANDing removes exactly one 1-bit.
• Unsigned arithmetic makes v-1 defined even at v==0 (loop never executes).
• The count fits in uint8_t: a 32-bit word has at most 32 set bits.

Cases the tests must cover

• 0 returns 0
• single top bit 0x80000000
• alternating pattern A5A5A5A5 is 16
• all ones is 32
• dense pattern 0xF0F0F0F0 is 16

Pitfalls

• A per-bit loop costs 32 iterations even for sparse status words.
• Do not use __builtin_popcount in portable code paths without a fallback.

Lowest set bit and trailing-zero count

lowest_set_bit returns only the lowest 1-bit (0 for 0). count_trailing_zeros returns the word width for a zero input, per the stated contract.

#include <assert.h>
#include <stdint.h>

/* Two's complement: v & (0u - v) keeps exactly the lowest set bit. */
uint32_t lowest_set_bit(uint32_t v)
{
    return v & (0U - v);
}

uint8_t count_trailing_zeros(uint32_t v)
{
    uint8_t n = 0U;
    if (v == 0U) return 32U;   /* contract: no set bit -> word width */
    while ((v & 1U) == 0U) {
        v >>= 1;
        ++n;
    }
    return n;
}

int main(void)
{
    assert(lowest_set_bit(0x28U) == 0x08U);
    assert(lowest_set_bit(0U) == 0U);
    assert(count_trailing_zeros(0x28U) == 3U);
    assert(count_trailing_zeros(1U) == 0U);
    assert(count_trailing_zeros(0U) == 32U);
    assert(count_trailing_zeros(0x80000000U) == 31U);
    return 0;
}

• 0U - v is unsigned negation: defined modulo 2^32, no signed-negation UB.
• The zero case must be in the contract; CLZ-style intrinsics are undefined there too.
• The shift loop is bounded by the word width: at most 31 iterations for nonzero input.

Cases the tests must cover

• 0x28 -> lowest 0x08, 3 trailing zeros
• 1 -> 0 trailing zeros
• 0 -> 32 per contract
• top bit only -> 31
• all ones -> 0 trailing zeros

Pitfalls

• -v on a signed int is UB at INT_MIN; stay unsigned.
• ctz(v)==0 does not mean v==1; it means the lowest bit is set.

Run-length encoder with overflow splitting

Counts the runs first and returns false without touching output when capacity is insufficient. Runs longer than 65535 are split into multiple entries.

#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

typedef struct { int16_t value; uint16_t count; } run_t;

bool rle_encode(const int16_t *in, size_t n, run_t *out, size_t cap, size_t *runs)
{
    size_t needed = 0U;
    size_t i, w = 0U;
    if ((out == NULL) || (runs == NULL)) return false;
    if ((in == NULL) && (n != 0U)) return false;
    for (i = 0U; i < n; ) {                 /* pass 1: how many entries? */
        int16_t v = in[i];
        uint32_t run = 0U;
        while ((i < n) && (in[i] == v)) { ++run; ++i; }
        needed += (run + 65534U) / 65535U;   /* chunks of at most 65535 */
    }
    if (needed > cap) return false;          /* no partial output */
    for (i = 0U; i < n; ) {                 /* pass 2: write */
        int16_t v = in[i];
        uint32_t run = 0U;
        while ((i < n) && (in[i] == v)) { ++run; ++i; }
        while (run > 65535U) { out[w].value = v; out[w].count = 65535U; ++w; run -= 65535U; }
        out[w].value = v;
        out[w].count = (uint16_t)run;
        ++w;
    }
    *runs = w;
    return true;
}

int main(void)
{
    int16_t in[] = { 7, 7, 7, 2, 2, 9 };
    run_t out[8];
    size_t runs = 0U;
    assert(rle_encode(in, 6U, out, 8U, &runs));
    assert(runs == 3U);
    assert(out[0].value == 7 && out[0].count == 3U);
    assert(out[1].value == 2 && out[1].count == 2U);
    assert(out[2].value == 9 && out[2].count == 1U);
    assert(!rle_encode(in, 6U, out, 2U, &runs));   /* capacity: untouched output */
    assert(rle_encode(NULL, 0U, out, 8U, &runs) && runs == 0U);
    return 0;
}

• Two passes keep failure atomic: sizing never writes, writing never fails.
• uint32_t run prevents count overflow before the 65535 split.
• A run of exactly 65535 fits one entry; 65536 needs two.

Cases the tests must cover

• three mixed runs
• capacity too small returns false with output untouched
• empty input yields zero runs
• NULL input with n>0 rejected
• a run of 65536 splits into two entries

Pitfalls

• Writing before knowing the total leaves a corrupt partial stream.
• uint16_t run counting would wrap at 65536 before the split logic sees it.

Byte histogram and mode

bins must be a caller-provided zeroed array of 256 uint32_t. histogram_peak returns the first byte with the maximal count and stores that count.

#include <assert.h>
#include <stddef.h>
#include <stdint.h>

void histogram_u8(const uint8_t *data, size_t n, uint32_t *bins)
{
    size_t i;
    for (i = 0U; i < n; ++i) bins[data[i]] += 1U;
}

uint8_t histogram_peak(const uint32_t *bins, uint32_t *count)
{
    uint8_t best = 0U;
    uint16_t b;
    for (b = 0U; b < 256U; ++b) {
        if (bins[b] > bins[best]) best = (uint8_t)b;
    }
    *count = bins[best];
    return best;
}

int main(void)
{
    uint8_t data[] = { 5U, 1U, 5U, 5U, 2U, 1U };
    uint32_t bins[256] = { 0U };
    uint32_t count = 0U;
    histogram_u8(data, sizeof data, bins);
    assert(bins[5] == 3U && bins[1] == 2U && bins[2] == 1U);
    assert(histogram_peak(bins, &count) == 5U && count == 3U);
    return 0;
}

• The byte value is the index: direct addressing, O(1) per sample.
• uint32_t bins survive 4 GiSamples; uint16_t would wrap on long DMA captures.
• Strictly-greater comparison keeps the LOWEST byte on ties: deterministic.

Cases the tests must cover

• counts per bin
• peak is the most frequent byte
• tie keeps the lower byte value
• all-equal input peaks at that byte with count n
• empty input leaves every bin zero

Pitfalls

• A uint16_t bin overflows on streams longer than 65535 samples.
• Zeroing is the caller's contract: document it or counts leak between captures.

Upper bound over a calibration table

Returns the first index whose entry is strictly greater than query, or n when none exists. Empty tables return 0.

#include <assert.h>
#include <stddef.h>
#include <stdint.h>

/* Invariant over half-open [lo,hi): entries left of lo are <= query. */
size_t upper_bound_u16(const uint16_t *table, size_t n, uint16_t query)
{
    size_t lo = 0U, hi = n;
    while (lo < hi) {
        size_t mid = lo + (hi - lo) / 2U;   /* overflow-free midpoint */
        if (table[mid] <= query) lo = mid + 1U;
        else hi = mid;
    }
    return lo;
}

int main(void)
{
    uint16_t t[] = { 10U, 20U, 20U, 30U };
    assert(upper_bound_u16(t, 4U, 20U) == 3U);
    assert(upper_bound_u16(t, 4U, 5U) == 0U);
    assert(upper_bound_u16(t, 4U, 30U) == 4U);
    assert(upper_bound_u16(NULL, 0U, 1U) == 0U);
    return 0;
}

• <= moves lo past duplicates, so the result sits AFTER every equal entry.
• lo + (hi - lo)/2 cannot overflow; (lo + hi)/2 can on huge tables.
• n is a valid result meaning every entry is <= query.

Cases the tests must cover

• duplicates: first index after the run
• query below all returns 0
• query above all returns n
• empty table returns 0
• single entry less than query returns 1

Pitfalls

• Using < instead of <= returns the FIRST equal entry (that is lower_bound).
• A closed-interval loop with hi = n-1 re-tests and can loop forever.

Peak of a unimodal sweep

Requires a non-empty strictly unimodal array (rises then falls). Returns the index of the maximum.

#include <assert.h>
#include <stddef.h>
#include <stdint.h>

size_t peak_index(const int16_t *a, size_t n)
{
    size_t lo = 0U, hi = n - 1U;
    while (lo < hi) {
        size_t mid = lo + (hi - lo) / 2U;
        if (a[mid] < a[mid + 1U]) lo = mid + 1U;   /* still climbing: peak right */
        else hi = mid;                             /* falling: peak at or left */
    }
    return lo;
}

int main(void)
{
    int16_t a[] = { 1, 3, 8, 9, 7, 2 };
    int16_t one[] = { 42 };
    assert(peak_index(a, 6U) == 3U);
    assert(peak_index(one, 1U) == 0U);
    return 0;
}

• Comparing a[mid] with a[mid+1] tells you which side of the peak you are on.
• hi = mid (not mid-1) keeps the peak inside the range; lo = mid+1 guarantees progress.
• The loop ends with lo == hi on the maximum.

Cases the tests must cover

• peak interior
• single element
• two-element rising array returns index 1
• peak at index 0 of a falling pair
• long plateau-free sweep stays logarithmic

Pitfalls

• A linear max scan is O(n): too slow per sweep on a small MCU at high rates.
• Equal neighbors violate strict unimodality; state the contract instead of guessing.

Fixed double-ended queue

All four operations are O(1) and return false on overflow/underflow. A count field, not head==tail, defines empty and full.

#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

typedef struct { uint8_t buf[8]; size_t head; size_t count; } deque_t;
/* head = index of the front element; count removes full/empty ambiguity. */

static void deque_init(deque_t *d) { d->head = 0U; d->count = 0U; }

bool deque_push_back(deque_t *d, uint8_t v)
{
    size_t tail;
    if (d->count == sizeof d->buf) return false;
    tail = (d->head + d->count) % sizeof d->buf;
    d->buf[tail] = v;
    ++d->count;
    return true;
}

bool deque_push_front(deque_t *d, uint8_t v)
{
    if (d->count == sizeof d->buf) return false;
    d->head = (d->head + sizeof d->buf - 1U) % sizeof d->buf;
    d->buf[d->head] = v;
    ++d->count;
    return true;
}

bool deque_pop_front(deque_t *d, uint8_t *out)
{
    if ((out == NULL) || (d->count == 0U)) return false;
    *out = d->buf[d->head];
    d->head = (d->head + 1U) % sizeof d->buf;
    --d->count;
    return true;
}

bool deque_pop_back(deque_t *d, uint8_t *out)
{
    if ((out == NULL) || (d->count == 0U)) return false;
    *out = d->buf[(d->head + d->count - 1U) % sizeof d->buf];
    --d->count;
    return true;
}

int main(void)
{
    deque_t d;
    uint8_t v = 0U;
    deque_init(&d);
    assert(deque_push_back(&d, 1U) && deque_push_back(&d, 2U));
    assert(deque_push_front(&d, 0U));                  /* 0 1 2 */
    assert(deque_pop_back(&d, &v) && v == 2U);
    assert(deque_pop_front(&d, &v) && v == 0U);
    assert(deque_pop_front(&d, &v) && v == 1U);
    assert(!deque_pop_front(&d, &v));                  /* underflow */
    return 0;
}

• head + count addresses the back without storing a second index.
• push_front wraps by adding capacity-1 instead of subtracting: no unsigned underflow.
• count==capacity is the full test; head==tail would sacrifice a slot.

Cases the tests must cover

• back/front push then both pop directions
• underflow rejected
• wraparound after several cycles
• full rejected
• count field disambiguates full from empty

Pitfalls

• Decrementing an unsigned head at 0 wraps to SIZE_MAX; add (cap-1) instead.
• Modulo works for any capacity; mask tricks need power-of-two.

O(1) minimum stack

push/pop/min are O(1) and report false on overflow/underflow. min on an empty stack is rejected, never a sentinel.

#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

typedef struct { int32_t data[8]; int32_t mins[8]; size_t top; } minstack_t;

static void ms_init(minstack_t *s) { s->top = 0U; }

bool minstack_push(minstack_t *s, int32_t v)
{
    if (s->top == 8U) return false;
    s->data[s->top] = v;
    s->mins[s->top] = ((s->top == 0U) || (v < s->mins[s->top - 1U]))
        ? v : s->mins[s->top - 1U];
    ++s->top;
    return true;
}

bool minstack_pop(minstack_t *s, int32_t *out)
{
    if ((out == NULL) || (s->top == 0U)) return false;
    --s->top;
    *out = s->data[s->top];
    return true;
}

bool minstack_min(const minstack_t *s, int32_t *out)
{
    if ((out == NULL) || (s->top == 0U)) return false;
    *out = s->mins[s->top - 1U];
    return true;
}

int main(void)
{
    minstack_t s;
    int32_t v = 0;
    ms_init(&s);
    assert(!minstack_min(&s, &v));                     /* empty: rejected */
    assert(minstack_push(&s, 5) && minstack_push(&s, 3) && minstack_push(&s, 7));
    assert(minstack_min(&s, &v) && v == 3);
    assert(minstack_pop(&s, &v) && v == 7);
    assert(minstack_min(&s, &v) && v == 3);
    assert(minstack_pop(&s, &v) && v == 3);
    assert(minstack_min(&s, &v) && v == 5);            /* min restored after pop */
    return 0;
}

• mins[i] is the minimum of data[0..i]: one extra word per slot buys O(1) minimum.
• Pop needs no fix-up because both stacks shrink together.
• The empty-min case is an API error, not a magic INT32_MAX return.

Cases the tests must cover

• min falls then restores after pops
• empty min rejected
• overflow at capacity rejected
• duplicate minima survive one pop
• pop returns the removed value

Pitfalls

• Tracking one 'current min' variable cannot restore the previous min on pop.
• A sentinel minimum collides with a legitimate INT32_MAX sample.

FIFO from two fixed stacks

push is O(1); pop is O(1) amortized because elements move to the output stack only when it is empty. Both report false on full/empty.

#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

typedef struct { uint8_t in[4]; uint8_t out[4]; size_t in_n; size_t out_n; } tsqueue_t;

static void tq_init(tsqueue_t *q) { q->in_n = 0U; q->out_n = 0U; }

bool tsqueue_push(tsqueue_t *q, uint8_t v)
{
    if (q->in_n == sizeof q->in) return false;
    q->in[q->in_n++] = v;
    return true;
}

bool tsqueue_pop(tsqueue_t *q, uint8_t *out_v)
{
    if (out_v == NULL) return false;
    if (q->out_n == 0U) {
        while (q->in_n > 0U) q->out[q->out_n++] = q->in[--q->in_n];   /* one move per element */
    }
    if (q->out_n == 0U) return false;
    *out_v = q->out[--q->out_n];
    return true;
}

int main(void)
{
    tsqueue_t q;
    uint8_t v = 0U;
    tq_init(&q);
    assert(tsqueue_push(&q, 1U) && tsqueue_push(&q, 2U));
    assert(tsqueue_pop(&q, &v) && v == 1U);
    assert(tsqueue_push(&q, 3U));
    assert(tsqueue_pop(&q, &v) && v == 2U);
    assert(tsqueue_pop(&q, &v) && v == 3U);
    assert(!tsqueue_pop(&q, &v));
    return 0;
}

• Reversing the in-stack into the out-stack puts the oldest element on top.
• Each element is moved at most once: n pops cost O(n) total, i.e. amortized O(1).
• Full capacity is in+out split; a mixed state can report full with physical room left.

Cases the tests must cover

• FIFO order preserved across interleaved push/pop
• empty pop rejected
• elements migrate lazily, not per push
• full input stack rejects push
• migration happens only when output stack empties

Pitfalls

• Moving elements on every push makes push O(n).
• A single pop after k pushes is O(k): amortized, not worst-case.

Arena save/restore marks

arena_save returns the current offset. arena_restore rewinds to an older mark in O(1) and rejects marks from beyond the current offset. Allocation is checked against remaining capacity.

#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

typedef struct { uint8_t *base; size_t cap; size_t off; } arena_t;
typedef struct { size_t off; } arena_mark_t;

static void arena_init(arena_t *a, uint8_t *mem, size_t cap)
{
    a->base = mem; a->cap = cap; a->off = 0U;
}

static void *arena_alloc(arena_t *a, size_t size)
{
    void *p;
    if (size > a->cap - a->off) return NULL;   /* subtraction form: no overflow */
    p = a->base + a->off;
    a->off += size;
    return p;
}

arena_mark_t arena_save(const arena_t *a)
{
    arena_mark_t m = { a->off };
    return m;
}

bool arena_restore(arena_t *a, arena_mark_t mark)
{
    if (mark.off > a->off) return false;   /* mark from the future: invalid */
    a->off = mark.off;                     /* rollback is just an offset move */
    return true;
}

int main(void)
{
    uint8_t mem[16];
    arena_t a;
    arena_mark_t m;
    uint8_t *p1, *p2;
    arena_init(&a, mem, sizeof mem);
    p1 = (uint8_t *)arena_alloc(&a, 4U);
    m = arena_save(&a);
    p2 = (uint8_t *)arena_alloc(&a, 8U);
    assert(p1 == mem && p2 == mem + 4U);
    assert(arena_alloc(&a, 5U) == NULL);       /* 12 used, 4 left */
    assert(arena_restore(&a, m));
    assert(arena_alloc(&a, 12U) == mem + 4U);  /* space reused after restore */
    return 0;
}

• A mark is just an offset; restore never touches memory, so it is O(1) and cannot fail on content.
• Nested scopes restore in LIFO order; restoring an inner mark invalidates outer marks taken after it.
• cap - off cannot underflow because off <= cap is the arena invariant.

Cases the tests must cover

• alloc after restore reuses the same address
• exhaustion returns NULL
• future mark rejected
• restore to the same mark twice is idempotent
• zero-size allocation returns the current offset

Pitfalls

• Objects restored away must be dead: dangling pointers into rewound space are use-after-free.
• Restore does not zero memory; stale bytes remain visible.

In-place heapsort

Sorts ascending in place. NULL or n<2 is a tolerated no-op. No recursion, no auxiliary buffer, not stable.

#include <assert.h>
#include <stddef.h>
#include <stdint.h>

static void sift_down(int16_t *a, size_t root, size_t n)
{
    for (;;) {
        size_t child = 2U * root + 1U;
        int16_t t;
        if (child >= n) return;
        if ((child + 1U < n) && (a[child] < a[child + 1U])) ++child;
        if (a[root] >= a[child]) return;
        t = a[root]; a[root] = a[child]; a[child] = t;
        root = child;
    }
}

void heap_sort(int16_t *a, size_t n)
{
    size_t i;
    if ((a == NULL) || (n < 2U)) return;
    for (i = n / 2U; i-- > 0U; ) sift_down(a, i, n);       /* build max-heap */
    for (i = n - 1U; i > 0U; --i) {
        int16_t t = a[0]; a[0] = a[i]; a[i] = t;           /* max to the end */
        sift_down(a, 0U, i);
    }
}

int main(void)
{
    int16_t a[] = { 5, -2, 9, 0, 9, -7, 3 };
    size_t i;
    heap_sort(a, 7U);
    for (i = 1U; i < 7U; ++i) assert(a[i - 1U] <= a[i]);
    assert(a[0] == -7 && a[6] == 9);
    heap_sort(NULL, 0U);
    return 0;
}

• Building the heap bottom-up from n/2 down is O(n), not O(n log n).
• i-- > 0 on size_t iterates n/2..0 without signed indices or underflow.
• After each swap the unsorted prefix [0,i) is a heap again after one sift.

Cases the tests must cover

• duplicates and negatives sorted
• already-sorted input
• NULL/empty no-op
• single element unchanged
• reverse-sorted input sorted

Pitfalls

• Heapsort is NOT stable: equal keys may reorder; use a key+sequence comparator if order matters.
• 2*root+1 overflows size_t only near SIZE_MAX; impossible for real buffers.

Hex decoder without partial output

Rejects NULLs, odd length, non-hex characters, and insufficient capacity before writing anything. On success stores len/2 bytes and reports the count.

#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

static int hex_nibble(char c)
{
    if (c >= '0' && c <= '9') return c - '0';
    if (c >= 'a' && c <= 'f') return c - 'a' + 10;
    if (c >= 'A' && c <= 'F') return c - 'A' + 10;
    return -1;
}

bool hex_decode(const char *hex, size_t len, uint8_t *out, size_t cap, size_t *written)
{
    size_t i;
    if ((hex == NULL) || (out == NULL) || (written == NULL)) return false;
    if ((len % 2U) != 0U) return false;          /* odd length */
    if (len / 2U > cap) return false;            /* checked before any write */
    for (i = 0U; i < len; i += 2U) {
        int hi = hex_nibble(hex[i]);
        int lo = hex_nibble(hex[i + 1U]);
        if ((hi < 0) || (lo < 0)) return false;
        out[i / 2U] = (uint8_t)((hi << 4) | lo);
    }
    *written = len / 2U;
    return true;
}

int main(void)
{
    uint8_t out[4];
    size_t n = 0U;
    assert(hex_decode("0aFF", 4U, out, sizeof out, &n));
    assert(n == 2U && out[0] == 0x0AU && out[1] == 0xFFU);
    assert(!hex_decode("0aF", 3U, out, sizeof out, &n));   /* odd */
    assert(!hex_decode("0xZZ", 4U, out, sizeof out, &n));  /* bad chars */
    assert(!hex_decode("0102030405", 10U, out, 4U, &n));   /* capacity */
    return 0;
}

• All structural checks (parity, capacity) run before the write loop: failure leaves out untouched.
• Explicit nibble mapping avoids locale-dependent library functions.
• Written bytes are reported separately so the caller can size buffers generously.

Cases the tests must cover

• mixed case round trip
• odd length rejected
• invalid character rejected
• capacity checked before writes
• empty string decodes to zero bytes

Pitfalls

• scanf %x parses signed-width-dependent values and accepts prefixes; avoid for protocols.
• Validating while writing leaves a half-written buffer on the first bad byte.

In-place CSV splitter with quotes

Splits line in place into NUL-terminated fields. Quoted fields may contain commas; a doubled quote inside quotes means one quote. Unmatched quotes and field-array overflow are errors.

#include <assert.h>
#include <stdbool.h>
#include <stddef.h>

typedef enum { CSV_OK = 0, CSV_ERR_QUOTE, CSV_ERR_FULL } csv_status_t;

csv_status_t csv_split(char *line, char **fields, size_t cap, size_t *count)
{
    size_t n = 0U;
    char *r = line;
    char *w = line;
    if ((line == NULL) || (fields == NULL) || (count == NULL)) return CSV_ERR_QUOTE;
    for (;;) {
        bool quoted = false;
        if (n == cap) return CSV_ERR_FULL;
        fields[n++] = w;
        if (*r == '"') { quoted = true; ++r; }
        for (;;) {
            if (*r == '\0') {
                if (quoted) return CSV_ERR_QUOTE;      /* unmatched quote */
                *w = '\0';
                *count = n;
                return CSV_OK;
            }
            if (!quoted && (*r == ',')) { *w++ = '\0'; ++r; break; }   /* w++: next field starts AFTER the terminator */
            if (quoted && (*r == '"')) {
                if (*(r + 1) == '"') { *w++ = '"'; r += 2; continue; }
                ++r;
                quoted = false;                        /* closing quote */
                continue;
            }
            *w++ = *r++;
        }
    }
}

int main(void)
{
    char line[] = "alpha,\"be,ta\",\"q\"\"z\"";
    char *fields[4];
    size_t n = 0U;
    assert(csv_split(line, fields, 4U, &n) == CSV_OK);
    assert(n == 3U);
    assert(fields[0][0] == 'a' && fields[0][5] == '\0');
    assert(fields[1][0] == 'b' && fields[1][3] == 't');   /* be,ta */
    assert(fields[2][0] == 'q' && fields[2][1] == '"' && fields[2][2] == 'z');
    {
        char bad[] = "\"oops";
        assert(csv_split(bad, fields, 4U, &n) == CSV_ERR_QUOTE);
    }
    return 0;
}

• Read and write cursors share one buffer because output is never longer than input.
• Doubled quotes are consumed as data before the closing-quote test runs.
• Field pointers index into the caller's line: zero allocation, but the line is destroyed.

Cases the tests must cover

• quoted comma kept inside the field
• doubled quote becomes one quote
• unmatched quote rejected
• field overflow rejected
• empty trailing field kept

Pitfalls

• strtok collapses empty fields and is not reentrant; this splitter keeps both.
• The input line is modified; callers needing the original must copy first.

BFS reachability with a bitmap

Counts nodes reachable from start (start included). Invalid arguments return 0. Caller provides the queue and a zeroed visited bitmap.

#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

typedef struct {
    uint8_t nodes;
    uint8_t edge_src[8];
    uint8_t edge_dst[8];
    uint8_t edge_count;
} graph_t;

static void mark(uint8_t *visited, uint8_t node)
{
    visited[node / 8U] |= (uint8_t)(1U << (node % 8U));
}

static bool seen(const uint8_t *visited, uint8_t node)
{
    return (visited[node / 8U] & (uint8_t)(1U << (node % 8U))) != 0U;
}

size_t reachable_count(const graph_t *g, uint8_t start, uint8_t *queue, uint8_t *visited_bitmap)
{
    size_t qh = 0U, qt = 0U, count = 0U;
    uint8_t i;
    if ((g == NULL) || (queue == NULL) || (visited_bitmap == NULL) || (start >= g->nodes)) return 0U;
    queue[qt++] = start;
    mark(visited_bitmap, start);
    while (qh < qt) {
        uint8_t cur = queue[qh++];
        ++count;
        for (i = 0U; i < g->edge_count; ++i) {       /* edge list: no matrix */
            if ((g->edge_src[i] == cur) && !seen(visited_bitmap, g->edge_dst[i])) {
                mark(visited_bitmap, g->edge_dst[i]);
                queue[qt++] = g->edge_dst[i];
            }
        }
    }
    return count;
}

int main(void)
{
    graph_t g = { 6U, { 0U, 0U, 1U, 3U }, { 1U, 2U, 3U, 4U }, 4U };  /* 0>1 0>2 1>3 3>4; 5 isolated */
    uint8_t queue[6];
    uint8_t visited[1] = { 0U };
    assert(reachable_count(&g, 0U, queue, visited) == 5U);
    visited[0] = 0U;
    assert(reachable_count(&g, 2U, queue, visited) == 1U);
    visited[0] = 0U;
    assert(reachable_count(&g, 9U, queue, visited) == 0U);
    return 0;
}

• Marking at enqueue time (not dequeue) prevents duplicate queue entries.
• A bitmap costs nodes/8 bytes; a bool array costs nodes bytes.
• The queue never holds more than nodes entries: bounded workspace.

Cases the tests must cover

• chain plus branch counts all five
• leaf reaches only itself
• out-of-range start returns 0
• isolated node counts itself only
• cycle does not re-enqueue visited nodes

Pitfalls

• Marking at dequeue time enqueues duplicates and can overflow the queue.
• Forgetting to zero the visited bitmap poisons every later query.

Delta codec with resync markers

First value absolute (LE), then int8 deltas. Deltas outside [-127,127] emit 0x80 0x80 plus a new absolute LE value. Encode returns bytes written (0 on error); decode rejects truncated streams and never writes past capacity.

#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>

#define DELTA_RESYNC 0x80U   /* 0x80 0x80 + 2 LE bytes = absolute value */

size_t delta_encode(const uint16_t *in, size_t n, uint8_t *out, size_t cap)
{
    size_t i, w = 0U;
    uint16_t prev;
    if (n == 0U) return 0U;
    if ((in == NULL) || (out == NULL) || (cap < 2U)) return 0U;
    out[w++] = (uint8_t)(in[0] & 0xFFU);        /* first value absolute, LE */
    out[w++] = (uint8_t)(in[0] >> 8);
    prev = in[0];
    for (i = 1U; i < n; ++i) {
        int32_t d = (int32_t)in[i] - (int32_t)prev;
        if ((d >= -127) && (d <= 127)) {
            if (w + 1U > cap) return 0U;
            out[w++] = (uint8_t)(int8_t)d;
        } else {
            if (w + 4U > cap) return 0U;
            out[w++] = DELTA_RESYNC;
            out[w++] = DELTA_RESYNC;
            out[w++] = (uint8_t)(in[i] & 0xFFU);
            out[w++] = (uint8_t)(in[i] >> 8);
        }
        prev = in[i];
    }
    return w;
}

bool delta_decode(const uint8_t *in, size_t n, uint16_t *out, size_t cap, size_t *written)
{
    size_t r, w = 0U;
    uint16_t prev;
    if ((in == NULL) || (out == NULL) || (written == NULL) || (n < 2U)) return false;
    prev = (uint16_t)(in[0] | ((uint16_t)in[1] << 8));
    r = 2U;
    if (cap == 0U) return false;
    out[w++] = prev;
    while (r < n) {
        uint16_t v;
        if ((in[r] == DELTA_RESYNC) && (r + 1U < n) && (in[r + 1U] == DELTA_RESYNC)) {
            if (r + 3U >= n) return false;               /* truncated resync */
            v = (uint16_t)(in[r + 2U] | ((uint16_t)in[r + 3U] << 8));
            r += 4U;
        } else {
            v = (uint16_t)(prev + (int16_t)(int8_t)in[r]);
            ++r;
        }
        if (w == cap) return false;
        out[w++] = v;
        prev = v;
    }
    *written = w;
    return true;
}

int main(void)
{
    uint16_t in[] = { 1000U, 1005U, 990U, 990U, 2000U, 1900U };
    uint8_t enc[32];
    uint16_t dec[8];
    size_t enc_n, dec_n = 0U, i;
    enc_n = delta_encode(in, 6U, enc, sizeof enc);
    assert(enc_n == 10U);                    /* 2 absolute + 4 deltas + 4 resync */
    assert(delta_decode(enc, enc_n, dec, 8U, &dec_n));
    assert(dec_n == 6U);
    for (i = 0U; i < 6U; ++i) assert(dec[i] == in[i]);
    return 0;
}

• int32_t difference avoids signed 16-bit overflow before the range test.
• Excluding -128 keeps byte 0x80 free for the doubled resync marker: an unambiguous stream.
• Decoder capacity is checked before every store, so a hostile stream cannot overrun output.

Cases the tests must cover

• round trip with an out-of-range jump resyncs
• encoded size matches expectation
• truncated stream rejected
• delta reconstruction wraps mod 2^16 symmetrically
• empty input encodes zero bytes

Pitfalls

• Emitting -128 as a plain delta makes 0x80 ambiguous with the resync marker.
• uint16_t prev arithmetic in decode wraps modulo 65536: matches encoder deltas exactly.

Start with contracts, not code

An embedded algorithm is defined by more than its happy-path output. Its contract includes buffer capacities, ownership, allowed execution contexts, worst-case time, maximum memory, overflow behavior, failure reporting, and what remains unchanged after failure.

Desktop algorithm exercises often hide allocation, recursion depth, integer width, scheduling, and malformed input. Firmware cannot. A function may run in an ISR, operate on DMA-owned memory, consume untrusted bytes, or execute under a hard deadline. Begin by writing preconditions, postconditions, invariants, and resource bounds before choosing a data structure.

Big-O describes growth, not a timing guarantee. O(1) can contain an unbounded retry loop, a cache miss, a critical section, or a slow divide. O(n) over a compile-time maximum of eight items can be safer and faster than a complex O(log n) structure. Embedded design pairs asymptotic analysis with a concrete maximum and execution context.

Failure is part of the API. A bounded function should reject invalid pointers, impossible capacities, arithmetic overflow, full queues, truncated frames, and exhausted pools without corrupting existing state. Prefer status plus out-parameter when every value in the result type is valid data.

Patterns and when they apply

contract table

Write inputs, outputs, bounds, ownership, context, failure, and complexity before implementation. Cost: Minutes of design work. Avoid when: Coding first and discovering ambiguous edge cases in tests.

caller-owned workspace

Make scratch memory visible and statically budgetable. Cost: More parameters. Avoid when: Hidden malloc or variable stack spikes.

status + out

Separate failure from all possible result values. Cost: Caller checks status. Avoid when: Magic sentinel values that can collide with data.

Bounded parser contract

1. Declare maximum frame size and caller-owned output capacity.
2. Validate header availability before reading it.
3. Check length using subtraction rather than an overflowing addition.
4. Publish decoded fields only after the entire frame validates.

Malformed input becomes an ordinary status, not an out-of-bounds access or partially trusted message.

Checklist

• What is the exact maximum n?
• Who owns every buffer before, during, and after the call?
• Can size arithmetic wrap?
• Is recursion permitted?
• Can the function run in an ISR?
• What state changes on failure?

Bits, bytes, widths, and representation

Use fixed-width unsigned types for bit operations, validate shift counts before shifting, assemble wire values byte-by-byte, and perform size arithmetic only after proving it cannot overflow. Representation-level code should be explicit about endianness and alignment.

A shift by the type width is undefined in C, signed overflow is undefined, and integer promotion can move an eight-bit operand into signed int before arithmetic. Convert intentionally, validate width and lsb values, and form masks in a type wide enough for the final operation.

Wire formats are byte sequences, not native structs. Casting an unaligned buffer to uint32_t can violate alignment, aliasing, object lifetime, and endianness assumptions. Decode with byte loads and shifts or a documented library primitive, then validate semantic ranges.

Bit tricks are valuable when they make an invariant obvious, but obscure cleverness is not free. A five-step SWAR reversal is excellent when tested across all bit positions; an inscrutable expression copied from the internet is a maintenance hazard. Explain why every mask exists.

Patterns and when they apply

mask-and-merge

Update one register field while preserving neighbors. Cost: Constant operations. Avoid when: Unvalidated width==type width shifts.

byte assembly

Decode unaligned big/little-endian packets portably. Cost: O(width) byte operations. Avoid when: Pointer punning into integer types.

saturating/checked arithmetic

Prevent silent control or buffer errors. Cost: Branches or wider intermediates. Avoid when: Relying on signed overflow or accidental wrap.

Safe field update

1. Reject width 0, lsb>=32, or width>32-lsb.
2. Use UINT32_MAX directly when width is 32.
3. Shift a validated mask to lsb.
4. Clear the field and OR the masked value into it.

Every non-field bit remains identical and no undefined shift occurs.

Checklist

• What type does integer promotion produce?
• Can shift equal the width?
• Is the buffer aligned?
• Which endian is the wire?
• Can the value fit the field?

Arrays, two pointers, windows, and locality

Arrays give contiguous storage, predictable footprint, cache-friendly traversal, and simple serialization. Two-pointer, prefix, sliding-window, monotonic-deque, and in-place partition patterns solve a wide range of streaming problems without per-element allocation.

The best embedded data structure is often a plain array plus a carefully maintained logical length. Contiguous storage minimizes metadata and pointer chasing, works naturally with DMA, and lets the linker account for every byte. Capacity and current length must be separate concepts.

A sliding window avoids recomputing a property for every position. Sum can update by subtracting the outgoing value and adding the incoming one. Maximum needs a monotonic deque of candidate indices: each index enters and leaves once, producing O(n) total work and O(k) workspace.

In-place algorithms trade scratch memory for mutation complexity. memmove chooses copy direction from overlap; dedup uses a read index and a write index; Dutch partition maintains three regions. The proof is a loop invariant describing which prefix or suffix is already final.

Patterns and when they apply

read/write cursors

Compaction, filtering, escaping, and deduplication. Cost: O(n), constant extra storage. Avoid when: Publishing new length before writes complete.

monotonic deque

Window minima/maxima and stable-range constraints. Cost: O(n) time, O(k) caller workspace. Avoid when: Storing values when duplicate indices matter.

three-way partition

Classify events or samples in one pass. Cost: Destroys within-class order. Avoid when: Using it when stable order is required.

Sliding maximum

1. Drop deque-front indices that left the window.
2. Drop deque-back indices whose values cannot beat the new sample.
3. Append the new index.
4. Once the first full window exists, emit the value at the front index.

Every index is pushed and popped at most once, giving linear total work.

Checklist

• Can input and output overlap?
• Is stable order required?
• What happens for n==0 or k>n?
• Does an accumulator need a wider type?
• Is caller workspace large enough?

Search, lookup tables, hashing, and dispatch

Use sorted arrays and binary search when data changes rarely and deterministic logarithmic lookup matters. Use direct indexing or bitmaps for small dense key spaces. Use bounded open addressing when average constant-time lookup justifies fixed table memory and explicit full-table behavior.

Binary search is an invariant over a half-open interval [lo,hi). For lower_bound, every index before lo is known too small and every index at or after hi is known large enough. The midpoint lo+(hi-lo)/2 avoids overflow and termination follows because each branch strictly shrinks the interval.

A hash table needs more design than a hash function: capacity, load factor, collision policy, empty/tombstone representation, duplicate semantics, probe termination, and denial-of-service bounds. In hard real-time paths, worst-case linear probing can be unacceptable even if average lookup is O(1).

Static command tables are often better than general maps. Sort at build time, binary-search string views without copying, and store function pointers or IDs in flash. A perfect hash or trie becomes worthwhile only when measured requirements justify its additional generator or node storage.

Patterns and when they apply

lower_bound

Calibration brackets, timestamp ranges, sorted command tables. Cost: O(log n), no allocation. Avoid when: Mixing closed and half-open interval formulas.

direct table/bitmap

Dense IDs, resource slots, ready priorities. Cost: Memory proportional to key space. Avoid when: Sparse huge keys.

open addressing

Bounded fixed map with good average lookup. Cost: Performance collapses near full. Avoid when: No probe bound or missing full-table status.

Calibration lower bound

1. Start lo=0 and hi=n.
2. Probe the overflow-safe midpoint.
3. If table[mid]<query, exclude mid and everything before it.
4. Otherwise keep mid as a candidate by setting hi=mid.

lo ends at the first entry not less than the query, including n when none exists.

Checklist

• Is the table sorted under the exact comparator?
• What is returned when no key matches?
• Can duplicate keys exist?
• How full may the hash table become?
• Is worst-case lookup bounded enough?

Stacks, queues, rings, and ownership

A stack provides LIFO state for parsing and traversal; a queue provides FIFO work ordering; a ring maps an unbounded logical stream onto bounded storage. Correctness depends on precise full/empty conventions, index ownership, overflow policy, and publication ordering.

A ring with head==tail needs another rule to distinguish empty from full. Reserve one slot, keep a count, or add a generation bit. The sacrifice-slot convention gives simple SPSC ownership because the producer alone writes head and the consumer alone writes tail.

Lock-free does not mean barrier-free. The producer writes an element before release-publishing head; the consumer acquire-loads head before reading the element. Similarly, the consumer finishes reading before release-publishing tail. C atomic types are not universally lock-free, and volatile is neither atomicity nor inter-thread ordering: verify the chosen type, compiler, target, and ISR contract.

Overflow policy belongs to product behavior: reject newest, overwrite oldest, block, backpressure, or reset. A diagnostic log may overwrite old data; a command stream usually must surface loss. Track high-water mark and rejected pushes so field failures are observable.

Patterns and when they apply

bounded stack

Expression parsing, DFS, iterative tree traversal. Cost: O(depth) fixed storage. Avoid when: Ignoring capacity or malformed nesting.

SPSC ring

ISR-to-task or one-thread-to-one-thread streams. Cost: One reserved slot and ordering discipline. Avoid when: Multiple producers without serialization.

priority queues

Several urgency bands with independent FIFOs. Cost: Policy needed to prevent starvation. Avoid when: Calling a strict-priority queue fair.

Ring wraparound

1. Use capacity 8 and reserve one slot.
2. Producer writes at head then advances head modulo capacity.
3. Consumer reads at tail then advances tail.
4. Full is next(head)==tail; empty is head==tail.

Indices may be equal after many wraps without ambiguity because the reserved slot encodes full separately.

Checklist

• Which side writes each field?
• What exactly means full?
• What is the overflow policy?
• Are capacity assumptions validated?
• What ordering primitive publishes data?

Lists, intrusive nodes, pools, arenas, and fragmentation

Intrusive lists store linkage inside caller-owned objects. Fixed-block pools recycle equal-sized objects in constant time. Arenas perform aligned bump allocation with bulk reset. These patterns provide dynamic lifetimes while retaining a predictable maximum footprint.

Linked lists make insertion and removal cheap only when you already have the node or position. Search remains O(n), every node costs pointers, and pointer chasing destroys locality. Arrays are usually better unless stable addresses, intrusive membership, or frequent O(1) splice operations are the real requirement.

A fixed-block pool threads its free list through unused blocks. Allocation removes the head; free validates address, alignment, membership, and allocation state before returning a block. O(1) alone is insufficient if double free can create a cycle or two clients can receive one block.

An arena aligns the current offset upward, checks both alignment arithmetic and size addition for overflow/capacity, then advances monotonically. It cannot free individual objects, which is precisely why allocation is simple and fragmentation-free. Reset occurs only when every arena object is dead.

Patterns and when they apply

intrusive list

Tasks, timers, descriptors with stable ownership. Cost: Link fields in every object; poor locality. Avoid when: Allocating wrapper nodes unnecessarily.

fixed-block pool

Packets, events, control objects of one size. Cost: Internal fragmentation to block size. Avoid when: Unvalidated foreign or double free.

arena

Phase-scoped parsing or initialization objects. Cost: Bulk lifetime only. Avoid when: Reset while references survive.

Pool allocation

1. Partition caller memory into aligned equal blocks.
2. Link every free block through its first bytes.
3. Pop one block and mark its slot allocated.
4. On free, validate range/alignment/state before pushing it back.

Allocation and free have bounded constant work with no external heap fragmentation.

Checklist

• Can a pointer be foreign or misaligned?
• How is double free detected?
• Who serializes pool access?
• What is internal fragmentation?
• When is arena reset legal?

Heaps, timers, scheduling, and wrap-safe time

An array-backed binary min-heap stores the next deadline at index zero and supports bounded O(log n) insertion/removal without pointers. Correct timer systems also require deterministic tie-breaking, cancellation bookkeeping, and a documented modular-time comparison horizon.

The heap invariant is local: every parent compares no greater than its children. Insert appends then sifts up; pop replaces the root with the last element then sifts down. The array is compact, but it is not sorted—only the minimum is guaranteed at the root.

Equal deadlines need a total comparator such as (deadline,insertion_sequence,id). Without deterministic tie-breaking, tests and callback order may vary. Cancel-by-ID requires an index map updated during every swap; stale reverse mappings are a classic heap corruption bug.

Unsigned tick subtraction can compare wrapping time when all relevant distances stay within half the counter range. This is a bounded modular-order technique, not a total order over arbitrary historical timestamps. State the horizon explicitly.

Patterns and when they apply

binary min-heap

Timers, deadlines, running top-k. Cost: O(log n) mutation, O(1) peek. Avoid when: Assuming array iteration is sorted.

ready bitmap

Small fixed priority set with bit-scan/CLZ. Cost: Constant storage and selection. Avoid when: Undefined zero-input intrinsic behavior.

token bucket

Bounded average rate with configurable burst. Cost: Fixed-point/time arithmetic. Avoid when: Unbounded token accumulation or wrap bugs.

Insert deadline 3

1. Append 3 at the heap's logical end.
2. Compare it with its parent.
3. Swap while the parent is greater.
4. Stop at root or when parent<=child.

Only the ancestor path changes, so insertion takes at most heap height O(log n).

Checklist

• What is the capacity-full status?
• How are equal keys ordered?
• Does every swap update auxiliary maps?
• What happens at tick wrap?
• Is the comparator transitive?

Strings, protocols, parsers, and adversarial input

Treat every byte sequence as untrusted until structural and integrity checks finish. Parse incrementally with explicit states, subtraction-based remaining-length checks, caller-owned storage, and a recovery rule that guarantees progress after malformed or partial input.

Never compute end=offset+length and then check end<=size unless overflow was already excluded. Prefer length<=size-offset after first proving offset<=size. Validate headers before fields, field lengths before payload reads, and semantic values before exposing the result.

A streaming parser cannot assume one read equals one frame. It must accept arbitrary chunks, retain bounded partial state, emit zero or more frames, and recover from bad lengths, delimiters, escapes, or CRC. State transitions should consume a byte or deliberately reset so malformed input cannot cause an infinite loop.

Text is also bytes with policies. Tokenizers need quote/escape rules, argv capacity, output mutation semantics, and a decision on UTF-8 versus ASCII. Avoid locale-dependent character functions in wire protocols unless locale is fixed and unsigned-char conversion is correct.

Patterns and when they apply

cursor + remaining

Bounds-safe TLV and binary message parsing. Cost: Explicit checks before every consume. Avoid when: Unchecked offset+length.

stream FSM

UART/TCP/DMA chunks and partial frames. Cost: Persistent bounded state. Avoid when: Assuming packet-aligned reads.

two-pass encode

Report required output before writing anything. Cost: May scan input twice. Avoid when: Partial output on capacity failure.

TLV consume

1. Require at least two header bytes.
2. Read type and length without advancing past them.
3. Prove length<=remaining payload bytes.
4. Validate and commit the field, then advance exactly length bytes.

Truncation and malicious lengths return status before any out-of-bounds access or partial publication.

Checklist

• Can any length addition wrap?
• Can input end in every state?
• What resynchronizes after corruption?
• Is output modified on failure?
• Are duplicate fields permitted?

Trees, tries, graphs, union-find, and state machines

Trees index hierarchical or ordered relationships; tries index prefixes; graphs represent arbitrary dependencies or reachability; union-find tracks evolving connectivity; finite-state machines encode temporal behavior. Embedded versions replace recursion and dynamic nodes with caller-provided arrays, indices, and explicit capacity failures.

A breadth-first search uses a queue to discover the fewest unweighted edges; depth-first search uses a stack for reachability and cycle reasoning. Both need visited state or they can repeat forever. Fixed graphs should use an adjacency representation chosen from actual density and maximum vertices.

Topological sorting repeatedly removes zero-indegree vertices. Producing fewer than V vertices proves a cycle exists, but identifying the actual cycle requires an additional DFS/parent trace. Do not promise cycle nodes from Kahn's count alone.

Finite-state machines are graphs whose edges are events and guards. They replace blocking delays with timestamp comparisons and make retries, debouncing, and protocol recovery testable. Every state/event pair needs a documented action, including ignored or impossible events.

Patterns and when they apply

BFS queue

Shortest path in unweighted grid/graph. Cost: O(V+E) and O(V) visited/workspace. Avoid when: Marking visited only when dequeued, causing duplicates.

topological sort

Peripheral initialization dependencies. Cost: O(V+E), detects but does not automatically exhibit a cycle. Avoid when: Treating a cyclic partial order as valid.

union-find

Incremental undirected connectivity and cycle detection. Cost: Near-constant amortized with rank+compression. Avoid when: Using it for directed reachability.

FSM

Non-blocking temporal control. Cost: Explicit state/event matrix. Avoid when: Scattered flags with impossible combinations.

Peripheral ordering

1. Compute indegree for each dependency node.
2. Queue every zero-indegree peripheral.
3. Pop one, append it to order, and decrement its outgoing neighbors.
4. If output count<V, report a dependency cycle.

Every emitted peripheral appears after all prerequisites, using bounded O(V+E) storage and work.

Checklist

• Directed or undirected?
• Weighted or unweighted?
• How is visited represented?
• Is recursion depth bounded?
• Must a cycle merely be detected or exhibited?
• Are all FSM events covered?

Firmware capstones: ownership, persistence, and proof

Real firmware composes pools, queues, parsers, indexes, CRCs, state machines, DMA ownership, and recovery scans. The system-level invariant must cover every resource and power-loss point, then tests must attack boundaries, interleavings, exhaustion, wraparound, and reset recovery.

A zero-copy telemetry path might allocate a descriptor from a pool, attach blocks, enqueue ownership to a driver, hand buffers to DMA, and recycle on completion. Every failure and cancellation edge must return each resource exactly once. A diagram of ownership states is often more useful than another algorithm name.

Persistent flash algorithms must respect erase granularity, one-way programming, torn writes, wear, and wrap-safe sequence numbers. Recovery treats flash as untrusted input: scan validated committed records, ignore incomplete tails, and never overwrite the last recoverable state before a replacement is durable.

Testing proceeds from invariants. Use boundary tables, deterministic unit vectors, property/fuzz tests for parsers, model traces for queues, injected allocation exhaustion, simulated power loss at every write, and concurrency tools where available. Measure stack, static RAM, worst-case operation count, and high-water marks on the target.

Patterns and when they apply

ownership state machine

DMA, pools, zero-copy descriptors. Cost: More explicit states and assertions. Avoid when: Two owners or ownerless resources.

append/commit/recover

Power-fail-safe flash records. Cost: Metadata, scans, and spare space. Avoid when: Publishing validity before payload integrity.

property-based testing

Large input spaces and invariant checking. Cost: Oracle/model design. Avoid when: Only example-based happy paths.

Zero-copy packet lifetime

1. Allocate descriptor and blocks from bounded pools.
2. Producer fills data while it owns them.
3. Queue transfer atomically hands ownership to the driver.
4. Completion or cancellation returns every object exactly once.

Exhaustion produces backpressure, not leaks, use-after-free, or DMA touching recycled memory.

Checklist

• Can every failure edge release resources?
• What survives reset?
• Where is commit made durable?
• Can DMA and CPU own a buffer simultaneously?
• Which invariants can tests assert after every step?
• What are measured high-water marks?

Sorting under firmware constraints

Pick the sort from the constraint that binds, not from the average complexity table. Small and nearly sorted means insertion sort. A hard worst-case bound with no recursion means heapsort. A small key space means counting sort. Only k items matter means a bounded heap, not a sort at all. Library qsort is the one to justify rather than the one to default to, because its recursion depth is not something you control.

The complexity table taught in a general course ranks sorts by average time, which is the least useful axis in firmware. A microcontroller cares about the worst case, the extra memory, and whether the routine recurses - and on those three axes the ranking is completely different. Heapsort is unfashionable and is often the correct answer, because it is the only common sort that is simultaneously O(n log n) worst case, O(1) space, and entirely iterative.

Insertion sort is not a beginner's mistake. It is O(n) on already-sorted input, has almost no constant factor, needs no memory, and is stable. For the n under about thirty-two that firmware actually sorts - a window of samples, a handful of events - it beats every asymptotically better algorithm, which is why every serious library falls back to it below a threshold.

Sorting is often the wrong tool entirely. If you need the largest k, a bounded heap costs O(n log k) and O(k) memory instead of sorting everything. If the keys are bytes, counting sort is O(n) with a fixed table. If there are three categories, a single three-way partition pass is enough. Reaching for a general sort when the problem has structure is how an O(n) job becomes an O(n log n) one.

Patterns and when they apply

insertion sort

n below ~32, nearly sorted data, stability required. Cost: O(n²) worst, O(n) on sorted input, O(1) space. Avoid when: Large n with random order.

heapsort

A hard worst-case bound with no recursion and no extra RAM. Cost: O(n log n) always, O(1) space. Avoid when: When stability matters - heapsort is not stable.

counting sort

Small known key space, such as byte-valued samples. Cost: O(n + k) time, O(k) fixed table. Avoid when: Wide or unbounded key ranges.

bounded heap for top-k

Only the k best matter out of n. Cost: O(n log k) time, O(k) space. Avoid when: When you actually need the whole order.

Choosing a sort for a 24-sample median filter

1. n is 24 and fixed, so asymptotic behaviour is irrelevant - the constant factor decides.
2. The window moves by one sample, so the input is almost sorted every time.
3. The filter runs in a control loop, so the worst case must be bounded and the stack must not grow.
4. Insertion sort: O(n) on nearly sorted data, no recursion, no memory, and about twenty lines.

Insertion sort wins on every axis that binds here, and qsort would have been slower and less predictable.

Checklist

• What is n, really?
• Is the input nearly sorted already?
• Does the worst case have to be bounded?
• How much stack does it use?
• Does stability matter?
• Do you need the whole order, or just the top few?

Complexity, bounds, and worst-case execution time

A real-time system needs a bound, and a bound is something you derive rather than observe. Give every loop a compile-time iteration limit, identify the longest path through the branches instead of the typical one, treat amortised costs as the single expensive operation they hide, and replace recursion with an explicit stack whose depth is a checked constant. Measurement tells you what happened on the inputs you tried; analysis tells you what cannot happen.

Average-case complexity is the wrong question for a deadline. A function that is O(1) on average and O(n) once in a thousand calls will miss its deadline once in a thousand calls, and in a control loop or a motor commutation that is a fault rather than a statistic. The number that matters is the worst case over all inputs the system can actually present.

Amortised bounds are the most common trap, because they are genuinely true and genuinely useless here. A dynamic array with amortised O(1) append pays for it with one O(n) reallocation-and-copy, and that single operation lands wherever it lands - including inside the interrupt that had eight microseconds to finish. The right response is to bound the individual operation, which usually means preallocating so the expensive case cannot occur.

Recursion is not banned because it is inelegant but because its stack cost is a function of the input rather than a constant you can put in a budget. A recursive traversal of a structure read from flash has a depth set by whatever is in that flash, which may be corrupted. Converting to an explicit stack of fixed capacity turns an unbounded, silent stack overflow into a checked rejection.

Patterns and when they apply

compile-time loop bound

Every loop whose count comes from data. Cost: One comparison per iteration. Avoid when: while (*p) with no length limit.

worst-path analysis

Branchy code whose cost varies by input. Cost: Analysis time, not runtime. Avoid when: Profiling with typical data and calling it a bound.

preallocate to remove amortisation

Anywhere an amortised structure would be used in a deadline path. Cost: Peak memory up front. Avoid when: Growth inside an ISR or a control loop.

explicit stack

Replacing recursion in a traversal. Cost: A fixed array plus a depth check. Avoid when: Recursion over data whose depth you do not control.

Bounding a frame parser

1. State the maximum frame the protocol allows: 256 bytes.
2. Count operations on the longest path - escape processing on every byte is the worst case, not the typical one.
3. Multiply: 256 bytes times the per-byte worst path gives the operation count.
4. Add the fixed cost of the CRC over 256 bytes.
5. Compare the total against the inter-frame time at the maximum line rate.

A number that holds for every input, rather than a measurement that held for the inputs tried.

Checklist

• Does every loop have a bound that does not come from the data?
• What input produces the longest path?
• Is any cost here amortised rather than worst case?
• How deep can the call stack get?
• Was the bound derived or measured?

Integer and fixed-point arithmetic

Scale into integers, order the operations so the intermediate cannot overflow, and round deliberately instead of letting C truncate toward zero. Multiply before dividing to keep the low bits, choose an intermediate type wide enough for the product, and add half the divisor before dividing to round to nearest. Division by a constant becomes a multiply and a shift; square roots and averages have exact integer forms. A float on a part without an FPU costs a library and hundreds of cycles for an answer integers could have given exactly.

Fixed point is just an integer with an agreed binary point. A value in Q16.16 is the real number times 65536, stored in an int32_t. Addition and subtraction work unchanged; multiplication doubles the number of fractional bits and needs a shift back; division needs a shift up first. Writing the Q format in the variable name is the cheapest bug prevention available, because the compiler cannot check it for you.

Order of operations decides both overflow and precision, and the two pull in opposite directions. Multiplying first keeps the low bits but risks overflowing the intermediate; dividing first is safe but throws away precision that cannot be recovered. The resolution is to multiply first in an intermediate type wide enough to hold the product - which usually means casting one operand up before the multiply, not after.

C's integer division truncates toward zero, which is a biased rounding mode: repeated use pulls an average steadily downward. Adding half the divisor before dividing gives round-to-nearest for positive values, and for signed values the correction has to depend on the sign. In a filter or an accumulator this is the difference between a stable value and a slow drift.

Patterns and when they apply

Q format fixed point

Fractional values with no FPU. Cost: A shift on multiply and divide. Avoid when: Mixing Q formats without renaming the variable.

widen-then-multiply

Scaling where the product exceeds the operand width. Cost: A wider intermediate. Avoid when: Casting the result instead of an operand.

add half before dividing

Round to nearest instead of toward zero. Cost: One addition. Avoid when: Applying it unchanged to negative values.

multiply-and-shift for division

Dividing by a compile-time constant. Cost: One multiply, one shift. Avoid when: Runtime divisors, where the reciprocal cannot be precomputed.

12-bit ADC count to millivolts

1. The relationship is mv = counts * vref / 4095.
2. Dividing first loses everything: counts/4095 is zero for every count below 4095.
3. Multiplying first: counts times vref for a 3300 mV reference reaches about 13.5 million, which needs more than 16 bits but fits an uint32_t.
4. Round to nearest: add 4095/2 before the divide.
5. Result: (counts * vref + 2047) / 4095, entirely in uint32_t.

An exact integer conversion with correct rounding, no library, and a provable absence of overflow.

Checklist

• What is the Q format, and is it in the name?
• Can the intermediate overflow at the extremes of the range?
• Does the division round or truncate?
• Is the divisor a compile-time constant?
• Would a float have pulled in a library on this part?

More in Embedded DSA

• Arrays & WindowsTwo pointers, sliding windows, in-place compaction and streaming filters over sample buffers. Twelve problems with complete C11 solutions, complexity targets and edge-case tests.
• Search & LookupBinary search that actually terminates, lookup tables, perfect hashing and command dispatch. Eleven problems on getting a bounded answer out of a table without a heap allocation in sight.
• Lists, Pools & ArenasIntrusive linked lists, fixed-block pools, arena allocators and why malloc is banned in most firmware. Ten problems on owning memory with a bound you can prove before the board ships.
• Trees, Graphs & StateTries for command tables, union-find for connectivity, and state machines that cannot reach an undefined state. Nine problems on structures that encode relationships rather than sequences.
• Parsing & ProtocolsFraming, COBS, incremental parsers and adversarial input. Nine problems on decoding a byte stream from a hostile world without a buffer overflow or an unbounded loop.
• Linked ListsEvery list variant, written for embedded C rather than for a whiteboard: singly and doubly linked, circular lists and sentinels that delete the boundary cases, the intrusive form kernels and firmware actually use, static pools and free lists for systems without malloc, reversal and cycle detection, and an honest account of when an array is the better answer.
• Sorting Under ConstraintWhich sort survives a 512-byte stack and a fixed deadline. Insertion sort for small nearly-sorted windows, heapsort when the worst case must be provable, counting sort for byte keys, and a bounded-depth quicksort - six problems with complete C11 solutions.
• Heaps & SchedulingBinary heaps as timer wheels and task schedulers, and wrap-safe time comparison - the bug that only shows up 49 days after the board is deployed. Eight problems with complete solutions.
• Integer & Fixed-Point MathComputing the right number with no floating-point unit. Q formats, multiply-before-divide, rounding instead of truncating, division by a constant as a multiply and shift, running averages that do not stall, and LFSR jitter for backoff.
• Stacks, Queues & RingsThe ring buffer and the SPSC queue: the two structures every firmware project actually ships. Ownership between an ISR and a main loop, overflow policy, and why the full/empty test is where the bugs are.
• Bits & BytesRegister fields, bit reversal, parity, endianness and portable packet decoding, without invoking undefined behaviour. Seven problems with complete C11 solutions and a step-by-step trace for each.
• Firmware CapstonesSix full-system problems: DMA ownership, wear-levelled persistence, crash-safe logging and proving a design meets its RAM and WCET budget. This is where every earlier stage gets used at once.