Q059FreeFirmware
Verify keypad expansion and FIFO draining
Question
Write the ordered-string predictor and transaction plan for a memory-mapped keypad expander with a 16-entry first-in, first-out (FIFO) result queue. Implement the predictor and complete wrapper, and explain the tests using these supplied platform hooks. Calls are ordered uncached MMIO under one exclusive driver owner. clear_completion clears stale DONE/ERROR/FIFO contents before start; abort returns only after the active job is quiescent and its FIFO/status are cleared. RESULT_LEN peeks the head without popping; RESULT_DATA pops once and packs character i in bits 8*i+7:8*i, with the first character in bits 7:0. A retained head is stable between its length/data reads unless reset occurs. FIFO count is 0..16; DONE is sticky and means no further entries can be produced. The 64-bit reset generation changes on every reset and never wraps during a call; reset cancels the old producer. lock_result_commit validates that generation and excludes reset until unlock, so a canceled job cannot publish late output. Result storage and out_count are separate writable live objects, disjoint from the input and each other; validate whole-capacity spans, alignment and byte/address arithmetic on the stated C11 flat-address platform. Input digits stay unchanged for the call. Timer subtraction is modulo 2^32 and a call lasts less than one full wrap. The hard deadline is checked before every FIFO pop and before committing; a zero timeout expires immediately after start. Detected hardware error or reset maps to KP_HW_ERROR, incomplete/malformed/extra output also maps to KP_HW_ERROR, and elapsed deadline maps to KP_TIMEOUT. Every post-start failure invokes abort and leaves both caller outputs unchanged.
Implementation scaffold
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
typedef enum { KP_OK, KP_BAD_ARG, KP_HW_ERROR, KP_TIMEOUT } kp_status_t;
enum { KP_BUSY = 1u << 0, KP_DONE = 1u << 1, KP_ERROR = 1u << 2 };
extern uint32_t kp_status_register(void);
extern uint8_t kp_fifo_count(void);
extern uint8_t kp_result_len(void);
extern uint32_t kp_result_data(void); // One accepted read pops one entry.
extern void kp_program_digits(const char *digits, uint8_t length);
extern void kp_clear_completion(void);
extern void kp_start(void);
extern void kp_abort(void);
extern uint32_t platform_ticks(void);
// Supplied platform hooks: successful lock excludes reset until unlock.
extern uint64_t kp_reset_generation(void);
extern bool kp_lock_result_commit(uint64_t expected_generation);
extern void kp_unlock_result_commit(void);
static bool kp_span(const void *ptr, size_t bytes, size_t alignment) {
if (bytes == 0) return true;
uintptr_t first = (uintptr_t)ptr;
return ptr != NULL && first % alignment == 0 && bytes <= UINTPTR_MAX - first;
}
static bool kp_overlap(const void *a, size_t an, const void *b, size_t bn) {
if (an == 0 || bn == 0) return false;
uintptr_t aa = (uintptr_t)a, bb = (uintptr_t)b;
return aa < bb + bn && bb < aa + an;
}
static const char *letters_for(char digit) {
static const char *const map[8] =
{"abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
return (digit >= '2' && digit <= '9') ? map[digit - '2'] : NULL;
}
// Inputs have already been validated as 1..4 keypad digits.
static size_t keypad_generate(const char *digits, size_t length,
char output[256][5]) {
// TODO: enumerate the exact dictionary-ordered Cartesian product.
}
static kp_status_t kp_guard(uint64_t generation, uint32_t began,
uint32_t timeout_ticks, uint32_t *status) {
// TODO: check reset generation, sticky hardware error and unsigned deadline.
}
kp_status_t keypad_expand(const char *digits, size_t len,
char (*out)[5], size_t out_cap,
size_t *out_count, uint32_t timeout_ticks) {
// TODO: validate, start, drain and compare results, then commit or abort.
}
// TODO: explain tests for validation, exact order, active FIFO draining, malformed
// results, sticky faults, timeout/wrap, reset races and all-or-nothing publication.
Trace one case
digits="23"9 outputs in order: ["ad","ae","af","bd","be","bf","cd","ce","cf"]The 3x3 Cartesian product follows keypad letter order, making the generated stream dictionary ordered.
Requirements
- Validate one through four digits from 2 through 9 and calculate the exact output count before MMIO.
- Generate strings in dictionary order using abc through wxyz and drain the 16-entry FIFO while the job is still active.
- Pop exactly one result per accepted data read and publish out_count only after all expected entries and DONE are observed.
- Handle sticky status, busy START rejection, unsigned timer wrap, reset, timeout and incomplete completion using the stated adapter contract. Check fault/reset/deadline even during continuous FIFO draining, abort on every post-start failure, and publish the staged result only while holding the generation-checked commit lock.