Parsing & Protocols

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?

Medium - Bounds-Safe TLV Parser

Decoding any tag-length-value structure: BLE advertising data, smartcard APDUs, configuration blobs, most binary sensor protocols.

Iterate type-length-value records in an untrusted byte buffer. Reject truncated headers, overflowing lengths, and duplicate singleton fields.

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

How it gets written wrong

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

Hard - In-Place COBS Decoder

Framing a byte stream so a delimiter can never appear inside a payload - the standard way to get reliable packet boundaries over a raw UART.

Decode one COBS frame in place, reject zero code bytes and impossible jumps, and return the decoded length without reading past input.

In-place COBS decoder with strict validation

Decodes one COBS frame in place and writes the decoded length. Rejects (DECODE_ERR, buffer contents unspecified) zero code bytes, jumps past the input end, and a trailing implicit-zero claim that overruns. Never reads or writes outside [0, encoded_len).

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

typedef enum { DECODE_OK, DECODE_ERR } decode_status_t;

decode_status_t cobs_decode(uint8_t *buf, size_t encoded_len, size_t *decoded_len) {
    if (buf == NULL || decoded_len == NULL || encoded_len == 0u) {
        return DECODE_ERR;
    }
    size_t read = 0u;    /* where the next code byte lives */
    size_t write = 0u;   /* decoded output position (write <= read always) */
    while (read < encoded_len) {
        uint8_t code = buf[read];
        if (code == 0u) return DECODE_ERR;              /* delimiter leaked in */
        if (read + code > encoded_len) return DECODE_ERR; /* jump runs off the end */
        read++;                                          /* consume the code byte */
        /* Copy code-1 data bytes forward over the code byte slot. */
        for (uint8_t i = 1u; i < code; i++) {
            buf[write++] = buf[read++];
        }
        /* A non-terminal short code stands for an implicit 0x00. */
        if (code < 0xFFu && read < encoded_len) {
            buf[write++] = 0u;
        }
    }
    *decoded_len = write;
    return DECODE_OK;
}

• COBS (Consistent Overhead Byte Stuffing) banishes 0x00 from a frame so 0x00 can be the packet delimiter on a UART. Each block starts with a code byte saying how far the next code byte is; a code below 0xFF implies a zero was removed at that spot.
• Decoding in place works because the output is always shorter than the input (every code byte is replaced by at most one zero). The write cursor therefore never overtakes the read cursor, so no decoded byte is ever clobbered before it is read.
• Both attack surfaces of untrusted input are checked before use: a zero code byte (which would desync the walk forever) and a code whose jump exceeds the buffer (which would read out of bounds — the classic parser CVE).
• The terminal-block rule: a short code (< 0xFF) adds an implicit zero only when data follows; a short code exactly at the end encodes the frame's final block without a trailing zero.

Cases the tests must cover

• [0x02, 0x41] decodes to [0x41], length 1
• [0x03, 0x41, 0x42] → [0x41, 0x42, 0x00] (implicit trailing zero of short block)
• Buffer containing 0x00 inside → DECODE_ERR
• Code 0x05 with only 2 bytes following → DECODE_ERR (jump overrun)
• Round-trip: decode(encode(x)) == x for buffers with and without zeros

How it gets written wrong

• Checking the jump after copying: the out-of-bounds read already happened.
• Appending the implicit zero unconditionally — a final 0xFF block or end-of-frame short code then adds a phantom zero.
• Decoding into a separate output buffer without checking its capacity; in-place removes that failure mode entirely.

Hard - Streaming Frame State Machine

Any protocol decoder driven from a UART interrupt, where bytes arrive one at a time and a frame may be split across dozens of interrupts.

Consume arbitrary byte chunks and emit length-prefixed frames with CRC. Recover after invalid lengths, CRC failures, and partial frames without allocation.

Chunked framing state machine with CRC recovery

Consumes arbitrary byte chunks, emits complete length-prefixed frames (sync, len, payload, CRC-16) via the emit callback, and resynchronizes after bad lengths or CRC failures. State persists across calls; no allocation; payload cap is fixed at compile time.

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

#define FRAME_MAX 64u
#define SYNC_BYTE 0xA5u

typedef enum { S_SYNC, S_LEN, S_PAYLOAD, S_CRC_HI, S_CRC_LO } parse_state_t;

typedef void (*frame_fn)(const uint8_t *payload, uint8_t len);

typedef struct {
    parse_state_t state;
    uint8_t buf[FRAME_MAX];
    uint8_t len;        /* expected payload length */
    uint8_t pos;        /* payload bytes collected */
    uint16_t crc;       /* running CRC of header+payload */
    uint16_t crc_rx;    /* CRC received, assembled high byte first */
} parser_t;

static uint16_t crc16_ccitt(uint16_t crc, uint8_t byte) {
    crc ^= (uint16_t)byte << 8;
    for (int i = 0; i < 8; i++) {
        crc = (crc & 0x8000u) ? (uint16_t)((crc << 1) ^ 0x1021u)
                              : (uint16_t)(crc << 1);
    }
    return crc;
}

void parser_init(parser_t *p) { p->state = S_SYNC; p->pos = 0u; p->len = 0u; p->crc = 0xFFFFu; p->crc_rx = 0u; }

void parser_feed(parser_t *p, const uint8_t *data, size_t len, frame_fn emit) {
    for (size_t i = 0u; i < len; i++) {
        uint8_t b = data[i];
        switch (p->state) {
        case S_SYNC:
            if (b == SYNC_BYTE) { p->crc = crc16_ccitt(0xFFFFu, b); p->state = S_LEN; }
            break;  /* anything else: stay hunting, cost is one byte */
        case S_LEN:
            if (b == 0u || b > FRAME_MAX) { p->state = S_SYNC; break; } /* bail, resync */
            p->len = b;
            p->pos = 0u;
            p->crc = crc16_ccitt(p->crc, b);
            p->state = S_PAYLOAD;
            break;
        case S_PAYLOAD:
            p->buf[p->pos++] = b;
            p->crc = crc16_ccitt(p->crc, b);
            if (p->pos == p->len) { p->state = S_CRC_HI; p->crc_rx = 0u; }
            break;
        case S_CRC_HI:
            p->crc_rx = (uint16_t)b << 8;
            p->state = S_CRC_LO;
            break;
        case S_CRC_LO:
            p->crc_rx |= b;
            if (p->crc_rx == p->crc && emit != NULL) emit(p->buf, p->len);
            p->state = S_SYNC;   /* success or CRC fail: hunt for the next frame */
            break;
        }
    }
}

• A UART delivers bytes in arbitrary chunks — 3 bytes now, 17 later. A state machine with persistent state handles this naturally: each call just advances the machine; it never assumes a chunk boundary matches a frame boundary.
• Every state transition is per-byte and O(1): SYNC hunts for 0xA5, LEN validates the length before a single payload byte is accepted (a bogus 250-length never allocates or overflows because the cap check comes first).
• The CRC runs incrementally over sync+len+payload, so no second pass is needed when the frame completes; a mismatch drops the frame and returns to hunting for the next sync — that is the recovery path.
• Resynchronization is deliberately simple: after any error the machine treats the next byte as a potential sync. False syncs inside payloads are absorbed by the length and CRC checks failing downstream.
• The emit callback receives a pointer into the parser's own buffer, valid only during the call — zero-copy with an explicit lifetime, the standard embedded framing contract.

Cases the tests must cover

• A valid frame split across 1-byte feeds still emits exactly once
• Garbage bytes before the sync are skipped, frame parses
• Length byte > FRAME_MAX resets to sync hunt without overflow
• Corrupted CRC: frame dropped, the following valid frame still parses
• Two frames back-to-back in one feed emit in order

How it gets written wrong

• Assuming one feed equals one frame — the byte-stream reality breaks any such code in the field.
• Buffering len bytes before validating len <= FRAME_MAX: the overflow happens before the check.
• Restarting the sync hunt inside the current byte after a CRC failure, risking an infinite loop within one feed; advancing to the next input byte is simpler and correct here.

Medium - Modbus RTU Request Validator

Validating an industrial request before acting on it: function code, address range, quantity limits, and CRC, in that order.

Validate address, function-specific length, byte count, and CRC-16 of a Modbus RTU request before exposing any fields.

Modbus RTU request validator

Validates a Modbus RTU request ADU: minimum length, function-specific frame length, byte-count consistency for write-multiple, and CRC-16 (little-endian on the wire). No field is exposed through *out until every check passes.

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

typedef enum { MODBUS_OK, MODBUS_ERR_LEN, MODBUS_ERR_FUNCTION,
               MODBUS_ERR_COUNT, MODBUS_ERR_CRC } modbus_status_t;

typedef struct {
    uint8_t address;
    uint8_t function;
    uint16_t start_reg;     /* for 0x03/0x06/0x10 */
    uint16_t quantity;      /* register/coil count or written value */
} request_t;

static uint16_t modbus_crc(const uint8_t *data, size_t len) {
    uint16_t crc = 0xFFFFu;
    for (size_t i = 0u; i < len; i++) {
        crc ^= data[i];
        for (int b = 0; b < 8; b++) {
            crc = (crc & 1u) ? (uint16_t)((crc >> 1) ^ 0xA001u)
                             : (uint16_t)(crc >> 1);   /* reflected poly */
        }
    }
    return crc;
}

static uint16_t rd_be16(const uint8_t *p) {
    return (uint16_t)(((uint16_t)p[0] << 8) | p[1]);
}

modbus_status_t validate_request(const uint8_t *adu, size_t len, request_t *out) {
    if (adu == NULL || out == NULL) return MODBUS_ERR_LEN;
    if (len < 4u) return MODBUS_ERR_LEN;          /* addr + func + CRC minimum */
    /* CRC covers everything except its own 2 bytes; wire order is low-high. */
    uint16_t want = (uint16_t)(adu[len - 2u] | ((uint16_t)adu[len - 1u] << 8));
    if (modbus_crc(adu, len - 2u) != want) return MODBUS_ERR_CRC;
    uint8_t fn = adu[1];
    switch (fn) {
    case 0x03:   /* read holding registers */
    case 0x06: { /* write single register */
        if (len != 8u) return MODBUS_ERR_LEN;
        out->start_reg = rd_be16(&adu[2]);
        out->quantity = rd_be16(&adu[4]);
        if (fn == 0x03 && (out->quantity == 0u || out->quantity > 125u))
            return MODBUS_ERR_COUNT;
        break;
    }
    case 0x10: { /* write multiple registers */
        if (len < 9u) return MODBUS_ERR_LEN;
        out->start_reg = rd_be16(&adu[2]);
        out->quantity = rd_be16(&adu[4]);
        uint8_t bytes = adu[6];
        if (out->quantity == 0u || out->quantity > 123u) return MODBUS_ERR_COUNT;
        if (bytes != (uint8_t)(out->quantity * 2u)) return MODBUS_ERR_COUNT;
        if (len != (size_t)(9u + bytes)) return MODBUS_ERR_LEN;
        break;
    }
    default:
        return MODBUS_ERR_FUNCTION;
    }
    out->address = adu[0];
    out->function = fn;
    return MODBUS_OK;
}

• Rule one of protocol handling: nothing is trusted until everything is checked. The output struct is only written after length, CRC, function, and byte-count all pass, so a malformed frame can never leak half-parsed fields to the application.
• Modbus CRC-16 uses the reflected polynomial 0xA001 and a little-endian wire order — the opposite of the big-endian data fields. Mixing those two orderings is the most common Modbus bug; the code makes both explicit.
• Function-specific length checks matter: a 0x03 request is exactly 8 bytes, while 0x10 carries a byte count that must equal 2 x quantity AND the frame length must equal 9 + count. Attackers (and broken masters) exploit inconsistent lengths.
• Register quantity limits (125/123 per the spec) are enforced so a wild quantity cannot drive a giant read of the register map downstream.

Cases the tests must cover

• A known-good 0x03 frame from the spec validates with correct fields
• One flipped payload bit → MODBUS_ERR_CRC
• Truncated frame → MODBUS_ERR_LEN
• 0x10 with byte count != 2*quantity → MODBUS_ERR_COUNT
• Unsupported function 0x2B → MODBUS_ERR_FUNCTION, *out untouched

How it gets written wrong

• Parsing fields into the output before the CRC check — a corrupt frame then steers the application.
• Reading the CRC big-endian; on the wire the low byte comes first.
• Accepting any length for fixed-size functions; strict equality catches both truncation and glued-together frames.

Easy - Escaped Serial Encoder

Encoding a payload for a link that reserves certain bytes - a debug protocol over a terminal, or a stream where a control character must not appear.

Encode delimiter and escape bytes into a caller-provided output buffer. Report required size without partially writing when capacity is insufficient.

Two-phase escaped encoder (size-then-write)

Escapes DELIM and ESC bytes into out. When out is NULL or cap is too small, returns ENCODE_NOSPACE with *written set to the required size and nothing written. Otherwise returns ENCODE_OK and the encoded length.

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

#define DELIM 0x7Eu
#define ESC   0x7Du
#define XOR   0x20u

typedef enum { ENCODE_OK, ENCODE_NOSPACE } encode_status_t;

encode_status_t escape_encode(const uint8_t *in, size_t n,
                              uint8_t *out, size_t cap, size_t *written) {
    if (in == NULL || written == NULL) return ENCODE_NOSPACE;
    /* Phase 1: count the exact encoded size without touching out. */
    size_t need = 0u;
    for (size_t i = 0u; i < n; i++) {
        need += (in[i] == DELIM || in[i] == ESC) ? 2u : 1u;
    }
    *written = need;
    if (out == NULL || cap < need) return ENCODE_NOSPACE;  /* nothing written */
    /* Phase 2: the write itself cannot fail — capacity is proven. */
    size_t w = 0u;
    for (size_t i = 0u; i < n; i++) {
        uint8_t b = in[i];
        if (b == DELIM || b == ESC) {
            out[w++] = ESC;
            out[w++] = (uint8_t)(b ^ XOR);
        } else {
            out[w++] = b;
        }
    }
    return ENCODE_OK;
}

• SLIP/HDLC-style framing reserves a delimiter byte; when the delimiter appears in the payload it is replaced by the two-byte sequence ESC, byte^0x20. ESC itself gets the same treatment so the decoder stays unambiguous.
• The two-phase pattern is the point of this challenge: count first, write second. Callers can ask 'how big?' with out == NULL, allocate or reject, then call again — and the writer never has to check bounds mid-stream.
• Because capacity is proven before phase 2, the function never leaves a half-written frame in the caller's buffer. Partial output is a protocol bug factory: the peer sees a truncated frame with a valid-looking start.
• Decoding mirrors it: copy bytes, and after an ESC output the next byte XOR 0x20. Cost stays O(n) in both directions.

Cases the tests must cover

• Payload without special bytes encodes to itself
• [0x7E] → [0x7D, 0x5E]; [0x7D] → [0x7D, 0x5D]
• out == NULL returns the needed size and writes nothing
• cap == need - 1 fails with zero bytes written
• Round-trip decode(encode(x)) == x including delimiter-heavy payloads

How it gets written wrong

• Writing as you go and bailing when full — the caller now owns a partial frame and no reliable signal of how much is valid.
• Forgetting to escape ESC itself; the decoder then misreads every literal ESC as an escape introducer.
• Reporting a 'required size' that differs from the actual encoded length (count and write logic drifted apart) — keep both loops structurally identical.

Medium - Longest Unique Command Span

Finding the longest run without a repeated token - detecting the longest non-repeating command sequence, or the longest unique span in a captured id stream.

Return the longest substring containing no repeated byte using a fixed 256-entry last-seen table. Input is not necessarily ASCII text.

Longest repeat-free span with a last-seen table

Returns start and length of the longest substring with no repeated byte. Works on arbitrary binary input (not just text) using a fixed 256-entry table of last-seen positions. Empty input yields {0,0}.

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

typedef struct { size_t start; size_t len; } span_t;

span_t longest_unique(const uint8_t *input, size_t n) {
    span_t best = { 0u, 0u };
    if (input == NULL || n == 0u) return best;
    /* last[b] + 1 = index after the most recent occurrence of byte b;
       0 means 'never seen'. Caller contract: table is fixed 256 entries. */
    size_t last[256];
    for (size_t i = 0u; i < 256u; i++) last[i] = 0u;
    size_t lo = 0u;   /* current window is [lo, i) */
    for (size_t i = 0u; i < n; i++) {
        uint8_t b = input[i];
        if (last[b] > lo) {
            lo = last[b];   /* jump the window past the previous occurrence */
        }
        last[b] = i + 1u;
        if (i + 1u - lo > best.len) {
            best.start = lo;
            best.len = i + 1u - lo;
        }
    }
    return best;
}

• Sliding window, one pass: the window [lo, i) never contains a repeat. When byte b was last seen inside the window, jumping lo to just after that occurrence restores the invariant instantly — no shrinking loop needed.
• The 256-entry last-seen table turns 'where did I see this byte?' into an O(1) lookup, which is where the O(n) total comes from. Storing position+1 lets 0 mean 'never seen' without a separate validity array.
• Because the table is indexed by byte value, the algorithm is encoding-agnostic — it works on UTF-8, binary telemetry, or random bytes alike, per the contract.
• Each index updates one table entry and one comparison, so this is genuinely O(n) with 256 words of fixed state: fine even on an 8 KB MCU.

Cases the tests must cover

• "abcabcbb" → length 3 ("abc")
• "bbbbb" → length 1
• "pwwkew" → length 3 ("wke", not "pwke")
• All 256 byte values once → length 256
• n = 1 → {0,1}; empty → {0,0}

How it gets written wrong

• Shrinking lo one step at a time with a nested loop — worst case degrades to O(n^2).
• Setting lo = last[b] without the last[b] > lo guard: an occurrence before the window must not drag lo backwards.
• Using a hash map when a byte-indexed array is O(1), faster, and fixed-size.

Medium - In-Place Command Tokenizer

Splitting a received command line into arguments in place, which every debug shell and AT-command handler does on every line.

Split a mutable command line into argv tokens with quotes and backslash escapes. Reject unmatched quotes and argv overflow without heap allocation.

Shell-style tokenizer with quotes and escapes

Splits a mutable line into NUL-terminated argv tokens in place. Double quotes group spaces; backslash escapes the next byte anywhere. Returns TOKEN_OK, TOKEN_UNMATCHED_QUOTE, or TOKEN_TOO_MANY (argv overflow). argv gets a terminating NULL slot.

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

typedef enum { TOKEN_OK, TOKEN_UNMATCHED_QUOTE, TOKEN_TOO_MANY } token_status_t;

token_status_t tokenize(char *line, char **argv, size_t argv_cap, size_t *argc) {
    if (line == NULL || argv == NULL || argc == NULL || argv_cap < 2u)
        return TOKEN_TOO_MANY;
    size_t out = 0u;
    char *p = line;
    while (*p != '\0') {
        while (*p == ' ' || *p == '\t') p++;      /* skip inter-token space */
        if (*p == '\0') break;
        if (out == argv_cap - 1u) return TOKEN_TOO_MANY;
        char *dst = p;                              /* compact token in place */
        argv[out++] = dst;
        bool in_quote = false;
        while (*p != '\0') {
            char c = *p;
            if (c == '\\') {                      /* escape: next byte is literal */
                p++;
                if (*p == '\0') return TOKEN_UNMATCHED_QUOTE;
                *dst++ = *p++;
                continue;
            }
            if (c == '"') { in_quote = !in_quote; p++; continue; }
            if (!in_quote && (c == ' ' || c == '\t')) break;
            *dst++ = *p++;
        }
        if (in_quote) return TOKEN_UNMATCHED_QUOTE;
        *dst = '\0';                               /* terminate the compacted token */
        if (*p != '\0') p++;                       /* skip the separator space */
    }
    argv[out] = NULL;
    *argc = out;
    return TOKEN_OK;
}

• In-place tokenizing exploits a length fact: the compacted token (quotes and backslashes removed) is never longer than its raw spelling, so writing the clean token over the raw text can never overwrite unread input.
• Quotes only toggle a flag — they vanish from the output but disable the space-separator test while active, which is exactly how a shell turns a b into one token.
• Backslash is handled before every other test, so \ , \ , and \t-as-text all become literal characters; an escape at end of line is a syntax error, not a read past the NUL.
• argv gets a NULL terminator one past the last token — exec-style APIs and for-loops over argv both depend on it, and reserving that slot is why a full argv returns TOKEN_TOO_MANY instead of overflowing.
• Failure modes return distinct status codes so the shell can print 'unmatched quote' vs 'too many arguments' — debuggability is part of the interface.

Cases the tests must cover

• led on → argc 2, argv ["led","on"]
• set name "John Doe" → argv[2] is "John Doe" as one token
• a\ b → single token "a b"
• Unterminated "abc → TOKEN_UNMATCHED_QUOTE
• More tokens than argv_cap - 1 → TOKEN_TOO_MANY, earlier tokens intact

How it gets written wrong

• strtok: it collapses runs of delimiters, destroys quote semantics, and keeps hidden global state — banned in re-entrant firmware.
• Writing the NUL terminator at the raw position instead of the compacted dst, leaking quote characters into the token.
• Off-by-one on argv_cap: the NULL sentinel needs a slot too.

Easy - Hex Text to Bytes

Reading hex from a human or a text protocol: Intel HEX firmware images, a debug shell taking an address, a text-mode sensor protocol.

Decode an even-length hex string into a caller buffer. Reject odd length, non-hex characters, and insufficient capacity without partial output.

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

How it gets written wrong

• 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.

Medium - CSV Field Splitter

Reading a configuration or calibration table from a text file on an SD card or an EEPROM region.

Split a mutable CSV record into field pointers in place, handling quoted fields with doubled-quote escapes. Reject unmatched quotes and field-array overflow.

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

How it gets written wrong

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

More in Embedded DSA

• The WorkbenchA complete embedded-first DSA course with theory, 80 challenges, complete C11 implementations, visual traces, mastery tracking, interview drills, and a constraint-driven firmware design arena.
• 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.
• 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.