Q151FreeSystemVerilog
Minimize descriptor count for a payload
Interview prompt
Question
Express a target payload length as an exact sum of supported transfer-block sizes while using the fewest descriptors. Return one count per original size slot, or report that no decomposition exists. Use size_count from 1 through 4; the active block sizes occupy slots 0 through size_count-1 and are distinct integers from 1 through 127. target_len is from 0 through 64. Inactive slots are ignored and their output counts are zero.
Candidate starting point
Implementation scaffold
module minimum_descriptor_packetizer (
input logic clk,
input logic rst_n,
input logic cmd_valid,
input logic [6:0] target_len,
input logic [2:0] size_count,
input logic [6:0] block_size [0:3],
input logic rsp_ready,
output logic cmd_ready,
output logic rsp_valid,
output logic impossible,
output logic [6:0] min_blocks,
output logic [6:0] block_count [0:3]
);
typedef enum logic [1:0] {S_IDLE, S_CLEAR, S_FILL, S_RESULT} state_t;
state_t state_q;
logic [6:0] size_q [0:3];
logic [2:0] size_count_q;
logic [6:0] target_q, clear_q, amount_q;
logic dp_valid [0:64];
logic [6:0] dp_min [0:64];
logic [6:0] dp_count [0:64][0:3];
logic next_valid;
logic [6:0] next_min;
logic [6:0] next_count [0:3];
logic [6:0] cand_min;
logic [6:0] cand_count [0:3];
logic tie_winner, diff_found;
logic [6:0] largest_diff_size;
logic result_impossible_q;
logic [6:0] result_min_q;
logic [6:0] result_count_q [0:3];
always_comb begin : evaluate_amount_candidates
// TODO: Implement evaluate_amount_candidates using the supplied state and interface.
end
assign cmd_ready = (state_q == S_IDLE);
assign rsp_valid = (state_q == S_RESULT);
assign impossible = result_impossible_q;
assign min_blocks = result_min_q;
generate
for (genvar g = 0; g < 4; g++) begin : g_outputs
assign block_count[g] = result_count_q[g];
end
endgenerate
always_ff @(posedge clk) begin : clear_fill_and_publish
// TODO: Implement clear_fill_and_publish using the supplied state and interface.
end
endmoduleReviewed example
Trace one case
Input
target_len=18; size_count=3; block_size=[6,4,9,0]Expected output
impossible=0; min_blocks=2; block_count=[0,0,2,0]Two 9-byte blocks exactly total 18, and no configured single block equals 18. Counts retain the original input slot order.
What to cover
Requirements
- Support target lengths from 0 to 64 and one to four unique positive block sizes supplied in any order.
- Treat target zero as a valid zero-descriptor result and represent unreachable totals explicitly.
- On equal descriptor counts, prefer more uses of the largest block size, then the next largest.
- Keep enough fixed-size metadata to return counts in the original input-slot order.
- Hold the response stable under backpressure.