Practice one explanation at a time

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

Practice one explanation at a time

Reproducing code from memory is different from explaining why each operation is needed.

Choose a problem from a lesson you have read. Write one tiny input, the expected output and the state after each operation. If a variable changes, explain what it now represents.

Implement the straightforward version before optimizing it. Test empty input, one item, a boundary value and a full-capacity case. Compare against the reference only after predicting the outcome; disagreements reveal a missing assumption or a bug.

Then explain the resource cost in terms of actual loops and storage. If you use the phrase constant time, point to the bounded operations. If you claim ownership is safe, name the point at which another user may access or reuse the data.

Follow the worked example

• Choose array compaction and input [0,5,0,7].
• Predict kept values [5,7] and returned length 2.
• Trace read indices 0..3 and a write index that advances only for kept values.
• Try [0,0] and [5,7] before reading the reference.

Connect the steps to code

/* Paper trace columns for compaction: */
/* read | value | write before | action | write after */
/*   0  |   0   |      0       | skip   |     0       */
/*   1  |   5   |      0       | copy   |     1       */

• The write index counts kept elements.
• The unused suffix is not necessarily cleared.
• A caller should use the returned logical length, not assume the whole capacity is valid.

Check your understanding

Is a reference solution a substitute for testing your own assumptions?

No. The reference follows its stated contract. Your implementation must be tested against the same input, overlap, capacity and error rules.

Open the workbench and complete one problem before switching families.

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.

More in Embedded DSA

• Sorting Under ConstraintLearn nine sorting algorithms with record-by-record traces: insertion, selection, bubble, Shell, merge, quick, heap, counting and radix. Compare stability, temporary storage and input-dependent work, then solve the C11 firmware exercises.
• 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 & ArenasFollow packet storage through allocation, use and release. Compare fixed-block pools, linked lists and arenas, including exhaustion, lifetime and allocation trade-offs.
• 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.
• Heaps & SchedulingInsert and remove deadlines in a binary min-heap, then study scheduling and wrapping tick counters. Heaps and timer wheels are different timer-management structures.
• 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.
• 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.
• 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.