Q064FreeFirmware
Enumerate calibration sums with fixed memory
Question
Enumerate dictionary-ordered combinations of distinct positive calibration values that sum to a target, allowing reuse without heap allocation or partial output. Use C11 on a flat-address platform where uintptr_t preserves byte addresses. Nonempty spans refer to live objects of the declared types and capacities. The input, both complete destination buffers and both size_t metadata objects must be mutually disjoint; validate byte-count arithmetic, address wrap and alignment before reading input or publishing sizes. The need_* objects are required even for a zero-capacity query. Null destination pointers are allowed only when the matching capacity is zero. Invalid descriptors take priority over no-space.
Implementation scaffold
#include <assert.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <string.h>
typedef struct { uint32_t first; uint8_t len; } combo_ref_t;
typedef enum { CS_OK, CS_BAD_ARG, CS_NO_SPACE, CS_SEARCH_LIMIT } cs_status_t;
typedef struct {
uint8_t next;
uint8_t remaining;
uint8_t path_len;
} cs_frame_t;
typedef struct {
size_t flat_count;
size_t ref_count;
size_t states;
} cs_counts_t;
// Supplied helpers for the stated flat-address platform.
static bool cs_valid_span(const void *ptr, size_t bytes, size_t alignment) {
if (bytes == 0) return true;
const uintptr_t start = (uintptr_t)ptr;
return ptr != NULL && start % alignment == 0 && bytes <= UINTPTR_MAX - start;
}
static bool cs_overlap(const void *a, size_t an, const void *b, size_t bn) {
if (an == 0 || bn == 0) return false;
const uintptr_t aa = (uintptr_t)a, bb = (uintptr_t)b;
return aa < bb + bn && bb < aa + an;
}
static cs_status_t calibration_pass(const uint8_t sorted[12], size_t n,
uint8_t target, bool write,
uint8_t *flat, size_t flat_cap,
combo_ref_t *ref, size_t ref_cap,
cs_counts_t *counts) {
// TODO: run the bounded explicit-stack enumeration in sizing or writing mode.
}
cs_status_t calibration_sets(const uint8_t *value, size_t n,
uint8_t target, uint8_t *flat, size_t flat_cap,
combo_ref_t *ref, size_t ref_cap,
size_t *need_flat, size_t *need_ref) {
// TODO: validate disjoint spans and values, size, then write and publish counts.
}
Trace one case
values=[2,3,6,7]; target=7combinations=[[2,2,3],[7]]Values may be reused within a combination, but traversal indices keep combinations ordered and prevent permutation duplicates.
Requirements
- Validate, copy, and sort 1 through 12 distinct values from 1 through 32 and a target from 1 through 64. Before reading, reject invalid or overlapping input, destination and metadata spans.
- Use an explicit stack of at most 65 frames and stop before entering search state 20001.
- Run identical sizing and writing traversals, checking every count and output-index calculation.
- Publish required sizes only for success or no-space and preserve both destination buffers on every non-success return.