State Machines & Protocol Implementation Questions

What is a ring buffer (circular buffer)
A ring buffer is a fixed-size array used as a FIFO where head (write) and tail (read) indexes advance and wrap to 0 when they hit the end. It stores streaming data without reallocations.

Typical embedded uses (concrete examples)

• UART + DMA RX: DMA writes bytes into a circular buffer; firmware advances tail to consume bytes when parsing frames. No mallocs, predictable latency.
• Audio sample buffering: Continuous ADC samples are pushed at ISR time; playback reads from buffer at audio interrupt rate, smoothing producer/consumer rate differences.
• Sensor logs, telemetry queues, inter-task message passing in RTOS.

Head/tail behavior & wrap-around

• head = index where next byte is written; tail = index where next byte is read.
• After increment: if (idx == size) idx = 0; (wrap-around)
• Full vs empty: common rule is keep one slot free or track count/overrun flag.
  • empty when head == tail (and count == 0)
  • full when (head + 1) % N == tail (one-slot-reserved)
• Increment atomically or with IRQ/lock to avoid races.

Advantages vs linked lists / dynamic arrays

• Predictable memory: single static array, no fragmentation.
• Low CPU: O(1) push/pop with simple index math.
• Deterministic timing and small code size—critical for constrained MCUs.
• Better cache locality than linked lists.

Implementation notes / pitfalls

• Use power-of-two size to replace modulo with bitmask: idx = (idx + 1) & (N-1).
• Handle overruns: set an error flag or drop oldest/newest per policy.
• Ensure atomic updates between ISR and main context (disable IRQs or use atomic counters).

Approach — brief
Use a compact bitwise implementation: small flash, simple logic, correct CRC-CCITT (poly 0x1021). Initialize to 0xFFFF (common), process each byte MSB-first, xor and shift 8 times.

Code

#include <stdint.h>

uint16_t crc16_ccitt(const uint8_t *data, uint16_t len)
{
    uint16_t crc = 0xFFFF;               /* initial value */
    while (len--) {
        crc ^= (uint16_t)(*data++) << 8; /* bring byte into MSB side */
        for (uint8_t i = 0; i < 8; ++i) {
            if (crc & 0x8000)
                crc = (crc << 1) ^ 0x1021;
            else
                crc <<= 1;
        }
    }
    return crc;
}

Explanation & trade-offs

• Bitwise implementation: minimal code size, no extra RAM/flash for tables, easy to audit and portable. Trade-off: slower (per-bit loops).
• Table-driven (byte-wise) implementation: far faster (one lookup + xor per byte) but needs a 256×2B = 512B table (or smaller 16/32-entry nibble tables) increasing flash. Also slightly more complex code and potential alignment/constants overhead.
• For tiny MCUs favor bitwise or a small nibble lookup if you need moderate speed but limited memory.

Situation & summary
Choosing between (A) RTOS with preemptive threads/mutexes and (B) event-driven state machine (no kernel). Both are viable for an IoT gateway handling BLE, Wi‑Fi, and sensors. Below I compare across the requested dimensions and give practical recommendations.

Latency

• RTOS: Lower worst-case latency for high-priority tasks due to preemption. ISR → high-priority thread wake gives predictable, bounded response (if priority inversion controlled). Example: BLE connection events can be serviced within microseconds to low milliseconds depending on scheduler tick and context-switch cost.
• Event-driven: Very low average latency for simple handlers (no context switch), but a long-running event handler can block others. Requires careful splitting into short handlers and deferred work to keep tail latency bounded.

Power consumption

• RTOS: Potentially higher due to periodic scheduler ticks and context switches, but modern tickless RTOS modes (tickless idle) mitigate this. Sleep entry/exit overhead per thread wake must be managed.
• Event-driven: Typically lower steady-state power—sleep/wakeup is explicit and fewer context switches. Good for infrequent events and deep sleep scenarios.

Determinism

• RTOS: Stronger determinism if priorities, mutexes (with priority inheritance), and IRQ latencies are tuned. Easier to guarantee deadlines for strict real-time tasks (e.g., BLE timing).
• Event-driven: Determinism depends on disciplined design (max handler duration, queue bounds). Harder to prove timing for mixed workloads (Wi‑Fi stack + BLE + sensors) without formal analysis.

Development complexity

• RTOS: Higher initial complexity (threading, synchronization, deadlock, race conditions). Offers modularity: separate threads for Wi‑Fi stack, BLE stack, sensor sampling.
• Event-driven: Simpler concurrency model (single-threaded) — fewer races/sync bugs. But complexity grows with state-machine interactions, flattening into spaghetti callbacks for multiple protocols.

Long-term maintainability

• RTOS: Better for larger teams and feature growth—clear separation of concerns, easier to add blocking drivers. Testability with thread-level unit tests and isolated modules.
• Event-driven: Good for small codebase and constrained HW; maintenance becomes harder as features grow (many timers, event priorities, deferred work).

Recommendation

• If strict BLE timing, multiple concurrent stacks, and future feature growth are expected → RTOS (use tickless mode, priority inheritance, limit kernel calls in ISRs).
• If ultra-low-power, minimal feature set, and very constrained RAM/flash → event-driven state machine.
• Hybrid: Use a minimal RTOS or tiny scheduler for critical concurrency and keep noncritical logic event-driven.

Key action: quantify deadlines (BLE connection interval, Wi‑Fi throughput), memory budget, and power budget, then pick RTOS for concurrency/determinism or event loop for minimal power/simple products.

Overview / goal
I would implement a small, deterministic FSM that decodes framed, byte‑stuffed packets (0x7E delimiter, 0x7D escape + XOR 0x20) while tolerating noise, misalignment, and partial buffers. The parser must stream bytes into a consumer buffer with minimal RAM and fast resynchronization.

States

• IDLE: waiting for 0x7E start. Ignore all other bytes.
• IN_FRAME: collecting payload bytes into consumer buffer until 0x7E seen.
• ESCAPE: last byte was 0x7D; next incoming byte is XORed with 0x20 and appended.
• DISCARD: frame being dropped due to error (overflow, invalid escape); wait for next 0x7E to re-enter IN_FRAME.

Actions per state

• IDLE: on 0x7E -> transition to IN_FRAME and reset length; else remain.
• IN_FRAME:
  • 0x7E -> if length>0, emit complete frame to consumer; stay in IN_FRAME (handles back-to-back frames).
  • 0x7D -> transition to ESCAPE.
  • normal byte -> append if space; on overflow -> set error, transition to DISCARD.
• ESCAPE:
  • if byte present -> decoded = byte ^ 0x20; append if space; transition to IN_FRAME.
  • if unexpected (e.g., EOF) -> handle as partial; transition accordingly.

Error handling

• Buffer overflow: move to DISCARD; increment drop counters; continue scanning for next 0x7E.
• Invalid escape (e.g., missing byte): treat as corrupted frame; DISCARD until 0x7E.
• Corrupted frame detection: optional CRC check performed on emit; if CRC fails, record error and continue.

Resynchronization strategy

• Always treat 0x7E as strong resync marker. In DISCARD or after error, scan incoming stream for next 0x7E; upon seeing it, start new IN_FRAME.
• Support streaming chunks: maintain current state across buffer boundaries so partial escape or partial frame resumes correctly.
• To handle run‑in noise (many non-0x7E bytes), IDLE simply ignores until delimiter—cheap and fast.

Memory & performance

• Single small fixed-size ring or linear buffer sized to max expected frame (no dynamic allocation).
• Minimal state (enum + index + counters). Append-only writes; consumer reads completed frames or processes bytes incrementally (callback) to avoid large buffering.

Example robustness tweaks

• If high noise causes frequent single 0x7E spurious bytes, require minimal frame length or CRC to accept frames.
• Expose counters for drops, escapes, and CRC failures for telemetry and adaptive tuning.

Approach summary
Guarantee deterministic latency by (1) bounding ISR execution and entry delay, (2) designing critical sections to be short and priority-aware, (3) configuring NVIC and CPU priority bits properly, and (4) computing worst‑case response time (WCRT).

Bounding ISR latency

• Keep ISRs minimal: defer work to bottom halves/tasks (RTOS threads, workqueues).
• Make ISRs O(1) with fixed loops; measure worst-case cycles with static timing analysis or cycle-accurate profiling.
• Account for stacking/unstacking, pipeline effects, and cache (if present).

Critical sections: tail‑chaining vs priority masking

• Use priority masking (BASEPRI on Cortex‑M) to block only below a threshold, allowing higher-priority interrupts to preempt.
• Prefer short critical sections (< few microseconds). For longer sequences, use lock-free algorithms or split into reentrant segments.
• Tail‑chaining (automatic on PendSV/exception return) reduces context switch overhead but doesn’t replace masking—design so high-priority ISRs can run while low-priority critical sections are masked.

NVIC / Cortex‑M tips

• Use 8/priority-levels consistent with hardware PRIGROUP. Configure priorities as contiguous MSBs.
• Use BASEPRI to disable interrupts below a level; use PRIMASK only for full-disable (avoid).
• Enable tail-chaining by ensuring proper priority assignments; keep fault handlers highest priority.
• Measure entry latency: instruction timing + stack push (store registers) + NVIC latency.

Quantify WCRT

• Model response to an interrupt I:

WCRT_I = blocking_time + queuing_delay + ISR_execution_time

• Blocking_time = max critical-section duration that masks I (use BASEPRI level).
• Queuing_delay = sum of all higher-or-equal priority ISRs that can execute before I.
• ISR_execution_time = worst-case cycles for I (including handlers it triggers) / CPU_freq.
  Provide numeric example in interview: e.g., 30 µs blocking + 10 µs higher-priority = 50 µs WCRT, validated by measurement and static analysis.

Validation

• Static timing analysis, measurement with GPIO toggle + oscilloscope, and stress tests with interrupt storms. Add watchdogs and fail-safe if bounds exceeded.