R11.2.1 Count Leading Zeros for Any Width

MediumImplementVerilator + Yosys · serverReview the topic

Write a leading-zero counter with a WIDTH parameter: one loop that the synthesizer can unroll at every width.

Hardware context: A leading-zero counter with a WIDTH parameter, built at widths 1, 5, 8 and 16; and a 4-bit remainder block that subtracts in a loop. Write the leading-zero counter as one loop that works at every width.

A floating-point adder shifts its result left until the top bit is 1. To know how far, it counts the 0 bits above the highest 1. The same block serves a 5-bit exponent path and a 16-bit fraction, so the width is a parameter.

This is an Implement problem: write the body of clz. The count n is the number of 0 bits above the highest 1 of d. When d has no 1 at all, n is WIDTH. That is why n has one more value than d has bits.

The tests build four copies, at WIDTH 1, 5, 8 and 16, and feed each one four words. Hard-coded widths fail. Synthesis check: the design must build on the site's synthesis flow with no latch. The cell and level counts come from an open-source flow and are a proxy for area and depth, not a foundry result.

Signals in the Timeline

SignalWidthRole
script120input of each check
Full specification
The module (keep the name, the parameter and the ports)
module clz #(
  parameter  int WIDTH = 8,                    // 1 to 32
  localparam int NW    = $clog2(WIDTH + 1)     // bits needed to hold 0 to WIDTH
) (
  input  logic [WIDTH-1:0] d,
  output logic [NW-1:0]    n                   // zeros above the highest 1; WIDTH when d is 0
);
  // your design
endmodule
WIDTHdn
81000_00000
80001_01103
80000_00017
80000_00008
5001002
101

The result holds n of every copy after each of the four words. Word 0 gives n1, n5, n8 and n16. Words 1 to 3 follow in the same order.

Simulator note: This problem runs on Verilator 5.052, so break is available. Icarus 12 refuses it.

Examples

Example 1

The Four Corners
Input
W1: 0 W5: 00000 W8: 00000000 W16: 0000000000000000
W1: 1 W5: 11111 W8: 11111111 W16: 1111111111111111
W1: 1 W5: 10000 W8: 10000000 W16: 1000000000000000
W1: 1 W5: 00001 W8: 00000001 W16: 0000000000000001
Output
n1_word0 = 1, n5_word0 = 5, n8_word0 = 8, n16_word0 = 16, n1_word1 = 0, n5_word1 = 0, n8_word1 = 0, n16_word1 = 0, n1_word2 = 0, n5_word2 = 0, n8_word2 = 0, n16_word2 = 0, n1_word3 = 0, n5_word3 = 4, n8_word3 = 7, n16_word3 = 15

All zeros gives WIDTH: 1, 5, 8 and 16. All ones and the top bit alone give 0. The bottom bit alone gives WIDTH - 1.

Example 2

One Bit Set
Input
W1: 0 W5: 00010 W8: 00000010 W16: 0000000000000010
W1: 1 W5: 00100 W8: 00010000 W16: 0000000100000000
W1: 0 W5: 01000 W8: 01000000 W16: 0100000000000000
W1: 1 W5: 10000 W8: 00000100 W16: 0001000000000000
Output
n1_word0 = 1, n5_word0 = 3, n8_word0 = 6, n16_word0 = 14, n1_word1 = 0, n5_word1 = 2, n8_word1 = 3, n16_word1 = 7, n1_word2 = 1, n5_word2 = 1, n8_word2 = 1, n16_word2 = 1, n1_word3 = 0, n5_word3 = 0, n8_word3 = 5, n16_word3 = 3

With a single 1 at position p, the count is WIDTH - 1 - p. At WIDTH 1 the only answers are 0 and 1.

Example 3

Two Bits Set
Input
W1: 1 W5: 00101 W8: 01000001 W16: 0000000100000001
W1: 0 W5: 10010 W8: 00100010 W16: 0100000000000001
W1: 1 W5: 00011 W8: 00001001 W16: 0000000000110000
W1: 0 W5: 01100 W8: 00011000 W16: 0000000011000000
Output
n1_word0 = 0, n5_word0 = 2, n8_word0 = 1, n16_word0 = 7, n1_word1 = 1, n5_word1 = 0, n8_word1 = 2, n16_word1 = 1, n1_word2 = 0, n5_word2 = 3, n8_word2 = 4, n16_word2 = 10, n1_word3 = 1, n5_word3 = 1, n8_word3 = 3, n16_word3 = 8

Only the higher 1 counts. A loop that lets the lower one write last gives a larger number.

Constraints and Contract

  • Inputs are known 0/1 values. Each word is held one nanosecond and n is read at its end.
  • Keep the module name, the parameter WIDTH and the ports. The design is combinational: no clock and no memory.

Hints

Hint 1

Decide which end of d the loop starts from, and which copy of the body must have the last word.

Hint 2

Give n its value for "no 1 anywhere" before the loop. Then every path through the block assigns n, and no latch is built.

Hint 3

Write constants with their width from the parameter, such as NW'(WIDTH - 1 - i). A fixed width such as 3'd7 is wrong at WIDTH 16.

What the grader checks: Six directed and twelve seeded tests feed four words each to copies at WIDTH 1, 5, 8 and 16. Each n is compared with an independent model. The synthesis check builds the default WIDTH of 8 and counts latches.

The submitted design must synthesize with 0 latches and no combinational loop. Counts come from the pinned open-source synthesis flow. They are proxies for logic size and depth, not physical area or timing.

18 checks on Verilator + Yosys · server. 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 2 steps and the final capstone

Report a problem with this page

Your code SystemVerilogSaved locally
Ln 1, Col 1Tab indents · Ctrl/⌘ + Enter runs samples
Not run yet

The Four Corners

Input
W1: 0 W5: 00000 W8: 00000000 W16: 0000000000000000
W1: 1 W5: 11111 W8: 11111111 W16: 1111111111111111
W1: 1 W5: 10000 W8: 10000000 W16: 1000000000000000
W1: 1 W5: 00001 W8: 00000001 W16: 0000000000000001
Expected output
n1_word0 = 1, n5_word0 = 5, n8_word0 = 8, n16_word0 = 16, n1_word1 = 0, n5_word1 = 0, n8_word1 = 0, n16_word1 = 0, n1_word2 = 0, n5_word2 = 0, n8_word2 = 0, n16_word2 = 0, n1_word3 = 0, n5_word3 = 4, n8_word3 = 7, n16_word3 = 15

All zeros gives WIDTH: 1, 5, 8 and 16. All ones and the top bit alone give 0. The bottom bit alone gives WIDTH - 1.

Run samples executes all 3 public checks. Check all tests runs 18 checks on the server.

Verilator + Yosys · server