Fix a cache address splitter that takes the set index from the byte offset bits.
Hardware context: Single-core cache with explicit geometry, write policy and replacement policy. Split a CPU address into cache tag, set and line offset.
A cache sent every address of a line to a different set. The bug is in the helper that splits an address into its parts.
A cache splits a byte address into three fields. The offset picks a byte inside a line. The set index picks the set. The tag is the rest, and records which line is stored.
The function cache_address() does this split for a 16-bit address. It also checks the cache shape. line_bytes and sets must each be a power of two, with at most 32 bytes per line and 16 sets.
The tests try 363 address and shape combinations, valid and invalid. They compare all fields with a model that uses division. Find the bug and fix it.
Signals in the Timeline
| Signal | Width | Role |
|---|---|---|
address | 16 | input of each check |
line_bytes | 8 | input of each check |
sets | 8 | input of each check |
Full specification
function automatic logic [79:0] cache_address(input logic [15:0] address,
input logic [7:0] line_bytes, sets);
| Result bits | Holds |
|---|---|
| 79:73 | Always 0. |
| 72 | invalid: 1 when the shape is not allowed. Every other bit is then 0. |
| 71:64 | Always 0. |
| 63:48 | tag: address / (line_bytes * sets). |
| 47:32 | line_base: the address with the offset bits cleared. |
| 31:16 | Always 0. |
| 15:8 | set: (address / line_bytes) % sets. |
| 7:0 | offset: address % line_bytes. |
| Shape rule | Meaning |
|---|---|
| line_bytes | 1, 2, 4, 8, 16 or 32. Anything else is invalid. |
| sets | 1, 2, 4, 8 or 16. Anything else is invalid. |
| Field widths | The offset has log2(line_bytes) bits and the set has log2(sets) bits. The tag gets all the bits above them. |
| Zero-width fields | One-byte lines have no offset bits, so offset is 0. One set has no index bits, so set is 0. |
With these powers of two, shifts and masks give the same answers as the divisions above. The bit order of an address is tag, then set, then offset, from the top down.
Examples
Example 1
A 16-byte Line in an 8-set Cache- Input
address = 0x1234, line_bytes = 16, sets = 8
- Output
invalid = no, tag = 0x24, line_base = 0x1230, set = 3, offset = 4
The low 4 bits give offset 4, so the line starts at 0x1230. The next 3 bits of 0x123 give set 3. The rest is tag 0x24.
Example 2
The Last Byte of a Line- Input
address = 0x003f, line_bytes = 4, sets = 2
- Output
invalid = no, tag = 0x7, line_base = 0x3c, set = 1, offset = 3
Byte 63 is offset 3 of the line at 0x3c. That is line 15, so the set is 1 and the tag is 7.
Example 3
A Line Size That Is Not a Power of Two- Input
address = 0x0040, line_bytes = 6, sets = 4
- Output
invalid = yes, tag = 0x0, line_base = 0x0, set = 0, offset = 0
Six-byte lines are not allowed. Only the invalid bit is set, and no partial fields are returned.
Example 4
One-Byte Lines and One Set- Input
address = 0x1234, line_bytes = 1, sets = 1
- Output
invalid = no, tag = 0x1234, line_base = 0x1234, set = 0, offset = 0
Both the offset and the set have zero bits, so both are 0. The whole address is the tag, and the line starts at the address itself.
Constraints and Contract
- Check the shape before any shift or mask. An invalid shape returns only bit 72.
- Inputs are always known 0 and 1 values.
- Keep the function name, the argument types and the result layout.
Hints
Hint 1
Draw the address as three boxes: tag on the left, set in the middle, offset on the right. Which bits does each box use?
Hint 2
Try address 0x1234 with 16-byte lines and 8 sets by hand. The offset is the low 4 bits. Which 3 bits form the set?
Hint 3
Look at the set_index line. It masks the address without first shifting the offset bits away.
What the grader checks: Each case checks one address and shape against a model that uses division and remainder. The 363 cases cover all valid shapes, many invalid ones, and the first and last addresses. This checks the arithmetic, not a cache that uses it.
363 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