Q031FreeFirmware
Coalesce a frame of DMA ranges
Interview prompt
Question
Buffer one frame of up to eight half-open direct-memory-access (DMA) ranges, sort them by start then end, and emit the smallest sorted set covering the same addresses. Merge overlap and exact adjacency. Use positive AW and 1 <= MAX_RANGES <= 8. Supply a nonempty frame with at most MAX_RANGES ranges, each satisfying in_start < in_end. Assert in_last only on the final accepted input range.
Candidate starting point
Implementation scaffold
module dma_range_coalescer #(
parameter int unsigned MAX_RANGES = 8,
parameter int unsigned AW = 16
) (
input logic clk,
input logic rst_n,
input logic in_valid,
output logic in_ready,
input logic in_last,
input logic [AW-1:0] in_start,
input logic [AW-1:0] in_end,
output logic out_valid,
input logic out_ready,
output logic out_last,
output logic [AW-1:0] out_start,
output logic [AW-1:0] out_end
);
typedef enum logic [2:0] {LOAD, SORT, MERGE_INIT, MERGE_SCAN, MERGE_FLUSH, DRAIN} state_t;
state_t state_q;
logic [AW-1:0] start_q [0:MAX_RANGES-1];
logic [AW-1:0] end_q [0:MAX_RANGES-1];
logic [AW-1:0] merged_start_q [0:MAX_RANGES-1];
logic [AW-1:0] merged_end_q [0:MAX_RANGES-1];
logic [AW-1:0] current_start_q, current_end_q;
int unsigned count_q, pass_q, pair_q, scan_q, merged_q, total_q, out_q;
assign in_ready = (state_q == LOAD) && (count_q < MAX_RANGES);
assign out_valid = (state_q == DRAIN);
assign out_start = merged_start_q[out_q];
assign out_end = merged_end_q[out_q];
assign out_last = out_valid && (out_q == total_q - 1);
always_ff @(posedge clk) begin : sort_merge_and_drain
// TODO: Implement sort_merge_and_drain using the supplied state and interface.
end
endmoduleReviewed example
Trace one case
Input
input half-open ranges=[10,20),[5,8),[8,10),[15,25)Expected output
one output range=[5,25) with out_last=1Sorting places [5,8) first; exact adjacency at 8 and 10 plus overlap at 15 coalesce every range into one cover.
What to cover
Requirements
- Accept 1 through 8 valid ranges satisfying start < end before producing output.
- Interpret ranges as [start, end) and merge whenever next_start <= current_end.
- Handle arbitrary order, duplicate starts, contained ranges, and adjacent ranges deterministically.
- Assert out_last only with the final coalesced token and hold every output field stable while stalled.