Fix a DMA burst planner that lets a burst cross a 4 KiB page on the source side.
Hardware context: Memory-to-memory DMA with owned descriptors and bounded bus bursts. Plan legal DMA bursts from byte-copy geometry and address boundaries.
A DMA engine copied a block that started just before a 4 KiB page boundary. The bus rejected one burst, because a burst must never cross a page. The planner that cut the copy into bursts has one bug.
The function dma_plan splits a copy of length bytes into segments. The bus moves four bytes per beat, and each segment is one burst of up to max_beats beats. The function returns a text plan with one entry per segment, or an error code.
The tests call dma_plan with 84 requests. They mix aligned and unaligned addresses, lengths from 0 to 28, every burst limit and addresses near a page end. Each plan is compared in full.
Find the bug and fix it. The rules in brief: check the request first. When either address is unaligned, a segment stays inside one word on both sides. No segment crosses a 4 KiB page on either side.
Signals in the Timeline
| Signal | Width | Role |
|---|---|---|
source_address | 17 | input of each check |
destination | 17 | input of each check |
length | 9 | input of each check |
max_beats | 3 | input of each check |
Full specification
function automatic string dma_plan(input int source_address, destination, length, max_beats);
| Error value | Set when |
|---|---|
| 1 | max_beats is not 1 to 4, or length is not 0 to 256. |
| 2 | An address is below 0 or above 65535, or a range runs past 65535 (address + length > 65536). |
| 4 | Both ranges hold at least one byte and they overlap. |
Check all three before planning and add up the bits that apply. If any is set, return ERROR= and the mask in decimal, for example ERROR=4.
| Segment rule | Meaning |
|---|---|
| Start | Begin at both addresses with all length bytes left. |
| Burst limit | A segment holds at most max_beats × 4 bytes. |
| Unaligned | Either address is not a multiple of 4. The segment then ends at the first word boundary that either address reaches. It is one beat. |
| Aligned | Both addresses are multiples of 4. With at least 4 bytes left, round the size down to a multiple of 4. Fewer than 4 bytes form a short last segment. |
| Page | A segment never crosses a multiple of 4096 on the source side or on the destination side. |
| Next | Both addresses move forward by the segment size. |
A plan starts with OK:. Each segment adds ssss>dddd:n/b; where ssss and dddd are the two addresses as four lowercase hex digits. n is the byte count and b the beats (n / 4 rounded up), both in decimal. The plan ends with BYTES= and length. A zero-length copy gives OK:BYTES=0.
This planner is careful, not optimal. When the two addresses sit at different places in their words, it uses more one-beat segments than a bus strictly needs.
The whole report string is compared with the expected one. The result shows the length of your report, the expected length and whether the two match.
Examples
Example 1
Both Addresses 1 Byte into a Word- Input
source 0x0001, destination 0x0065 (101), length 11, max_beats 4
- Output
report_length = 39, expected_length = 39, match = yes
The first segment takes 3 bytes to reach the word boundary. Both addresses are then aligned, so the last 8 bytes go as 2 beats. The plan is OK:0001>0065:3/1;0004>0068:8/2;BYTES=11.
Example 2
The Source Page Ends Early- Input
source 0x0ffc (4092), destination 0x2000 (8192), length 12, max_beats 4
- Output
report_length = 39, expected_length = 39, match = yes
Both addresses are aligned, and 12 bytes would fit in one burst. But the source page ends 4 bytes later. The plan is OK:0ffc>2000:4/1;1000>2004:8/2;BYTES=12.
Example 3
Overlapping Ranges- Input
source 32, destination 36, length 8, max_beats 2
- Output
report_length = 7, expected_length = 7, match = yes
Bytes 32 to 39 and bytes 36 to 43 overlap. The request is rejected as ERROR=4, and no segment is planned.
Example 4
Different Offsets in the Word- Input
source 0x0000, destination 0x2003 (8195), length 7, max_beats 4
- Output
report_length = 66, expected_length = 66, match = yes
The destination is 3 bytes into its word, so the first segment holds 1 byte. Then the source is 1 byte in, so the next holds 3. The plan has four one-beat segments of 1, 3, 1 and 2 bytes.
Example 5
A Burst Limit of 0- Input
source 0, destination 80, length 0, max_beats 0
- Output
report_length = 7, expected_length = 7, match = yes
max_beats must be 1 to 4, so error value 1 is set. The length is 0, so the ranges cannot overlap. The result is ERROR=1.
Constraints and Contract
- Inputs are known binary values. The tests never drive x or z.
- Do the range checks in int arithmetic. Cutting a sum to 16 bits first hides an overflow.
- Keep the function name, its arguments and the return type.
Hints
Hint 1
Five limits can shorten a segment: the burst limit, a word end on each side and a page end on each side. Each one must apply.
Hint 2
Trace the second example by hand. The source starts at 0x0ffc, four bytes before the page boundary at 0x1000. How long can the first segment be?
Hint 3
Look at the page check near the end of the loop. Only the destination page is checked. Also clip n to 4096 - s % 4096.
What the grader checks: The tests check 84 plans, with addresses near word and page ends and every burst limit. They compare the whole plan. They do not drive a bus or move any data.
84 checks on Icarus · browser samples / server checks. Run the examples first, then check the full regression. Full checks use the server judge. Downloads contain public samples only. A passing result establishes the tested cases, not a proof for all possible inputs.
See all 8 steps and the final capstone