Build the step that lines up a floating-point result

Subtract two nearly equal floating-point numbers and the mantissa that comes out can be 0x0000_0350: 22 zeros before the first 1. Before the result can be stored, the unit must find that 22, shift the mantissa left by 22 so bit 31 is 1 (0xD400_0000), and lower the exponent by 22. That step is a normaliser, and this project builds it: 32 bits, no clock, one combinational block.

It joins two ideas from this part. The count is a priority encoder that looks for the highest 1; the shift is a barrel shifter. The trick is to let the shifter's stages discover the count as they go.

Read it top to bottom. The value falls through five stages, and each one makes a single decision.

• Stage 16 first: if the top 16 bits are all zero, the first 1 is at least 16 places down, so shift by 16 and record k[4] = 1.

• Each later stage asks the same question of the already-shifted value, with half the width: 8, 4, 2, then the single bit 31.

• The answers are the count: the stage that shifts by 2ⁱ sets bit i, so k is the leading-zero count in binary. No separate encoder is needed.

The spec

1. lzc is the number of 0 bits above the highest 1 in d: 0 when d[31] is 1, 31 when d is 1.

2. When d is 0, zero is 1, lzc is 32 and y is 0. lzc needs 6 bits because 32 does not fit in 5.

3. Otherwise zero is 0 and y equals d << lzc, so y[31] is 1.

4. Purely combinational: no clock, no state, no latch. Outputs follow d in the same cycle.

Before you start

• Barrel shifter, rotate and arithmetic shift: one stage per bit of the shift amount.

• Priority encoder: finding the winning 1, the valid flag, and why a linear scan is deep.

• The complete-assignment pattern: how combinational code avoids a latch.

• Propagation delay and levels of logic: what a logic-depth number means.

Done when

The project is finished when every row is true and you have run each command yourself.

The synthesis check on the reference solution, trimmed:

$ yosys -p "read_verilog -sv lzc_norm.sv; synth -flatten -top lzc_norm; stat; ltp -noff"
...
      237 cells
       32   $_ANDNOT_
       52   $_AND_
       98   $_MUX_
       22   $_NAND_
       24   $_NOR_
        1   $_NOT_
        8   $_OR_
...
Longest topological path in lzc_norm (length=18):
    0: \d [31]
...
   18: \y [30] (via $abc$328$auto$blifparse.cc:397:parse_blif$419)

There is no latch cell. The 98 $_MUX_ cells are most of the shifter; where a stage shifts in a zero, a mux with a constant input becomes an AND gate. The longest path runs from d[31] to y[30] through 18 gates, because each stage must wait for the stage above to finish shifting before it can test its own window.

Reference solution

The full listing is under The test. Read it in three parts.

// snippet: part 1, the largest stage
assign k[4] = (d[31:16] == 16'd0);
assign s16  = k[4] ? {d[15:0], 16'd0} : d;

A 16-bit NOR answers "is the first 1 at least 16 places down?". If so, the stage shifts by 16. Either way, the first 1 of s16 now sits in its top 16 bits, unless d is 0.

1
2
3
4
5
6
7
8
9

// snippet: part 2, each later stage tests half the width of the shifted value
assign k[3] = (s16[31:24] == 8'd0);
assign s8   = k[3] ? {s16[23:0], 8'd0} : s16;
assign k[2] = (s8[31:28]  == 4'd0);
assign s4   = k[2] ? {s8[27:0], 4'd0} : s8;
assign k[1] = (s4[31:30]  == 2'd0);
assign s2   = k[1] ? {s4[29:0], 2'd0} : s4;
assign k[0] = ~s2[31];
assign s1   = k[0] ? {s2[30:0], 1'b0} : s2;

This is a binary search for the first 1. After stage 16 the answer lies within 16 places, after stage 8 within 8, and so on. Each k[i] is the bit of the count worth 2ⁱ, decided most significant first, and the five stages together shift by exactly k.

1
2
3
4

// snippet: part 3, the all-zero case
assign zero = (d == 32'd0);
assign lzc  = zero ? 6'd32 : {1'b0, k};  // k alone reads 31 when d = 0
assign y    = s1;

For d = 0 every stage shifts, k reads 11111 (31) and y is already 0. The true count is 32, which k cannot hold, so a separate 32-input NOR picks it. The design uses assign throughout: every signal has one driver and nothing can be left unassigned, so no latch is possible.

Project files

The complete listing below contains every file of this project, each starting at a // ---- file: <name> ---- line. Save each part under its name in one folder, then run the script.

run.sh

#!/bin/sh
set -e
iverilog -g2012 -Wall -o sim.out lzc_norm.sv tb_lzc_norm.sv
vvp sim.out
yosys -q -p "read_verilog -sv lzc_norm.sv; synth -flatten -top lzc_norm; stat; ltp -noff"   # optional: depth

Expected output: the line a correct design makes the simulation print at the end of its run.

PASS: lzc_norm matches the reference on 264033 inputs (zero, 32 one-hot, 32 x 2000 first-one classes, 200000 random)

The test

Only one random 32-bit value in 2ᵏ has a count of k or more, so a purely random test almost never tries a count above 20. The bench therefore tests by class, then adds random volume:

• Zero: the one input where lzc is 32.

• Every one-hot value: 32 inputs, one for each position of the single 1.

• First one at position k, random bits below: 2000 inputs for each k from 0 to 31. This is every count, with the lower bits varied so the shift is checked, not only the count.

• 200000 uniform random inputs from a fixed seed, so a failure can be repeated.

The reference model is written differently on purpose: it walks down from bit 31 counting zeros, and computes y with the << operator.

$ iverilog -g2012 -Wall -o sim.out lzc_norm.sv tb_lzc_norm.sv
$ vvp sim.out
PASS: lzc_norm matches the reference on 264033 inputs (zero, 32 one-hot, 32 x 2000 first-one classes, 200000 random)
tb_lzc_norm.sv:36: $finish called at 264033 (1s)

The design and the bench in one listing:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

// ---- file: lzc_norm.sv ----
module lzc_norm (
  input  logic [31:0] d,
  output logic [31:0] y,      // d shifted left until y[31] = 1 (all zeros when d = 0)
  output logic [5:0]  lzc,    // leading zeros of d: 0 to 32
  output logic        zero    // d == 0
);
  logic [31:0] s16, s8, s4, s2, s1;
  logic [4:0]  k;              // k[i] = 1: stage i shifted by 2^i

  // Largest stage first: each stage asks "are my top 2^i bits all zero?"
  assign k[4] = (d[31:16]   == 16'd0);
  assign s16  = k[4] ? {d[15:0], 16'd0} : d;
  assign k[3] = (s16[31:24] == 8'd0);
  assign s8   = k[3] ? {s16[23:0], 8'd0} : s16;
  assign k[2] = (s8[31:28]  == 4'd0);
  assign s4   = k[2] ? {s8[27:0], 4'd0} : s8;
  assign k[1] = (s4[31:30]  == 2'd0);
  assign s2   = k[1] ? {s4[29:0], 2'd0} : s4;
  assign k[0] = ~s2[31];
  assign s1   = k[0] ? {s2[30:0], 1'b0} : s2;

  assign zero = (d == 32'd0);
  assign lzc  = zero ? 6'd32 : {1'b0, k};  // k alone reads 31 when d = 0
  assign y    = s1;
endmodule

Common mistakes

The barrel shifter lesson lists its stages as 1, 2, 4, 8, 16, and for a shifter the order does not matter: the amount is known in advance. Copy that order into the normaliser and it breaks:

1
2
3
4
5
6

// bad-example: stages in barrel-shifter order, smallest first
assign k[0] = ~d[31];
assign s1   = k[0] ? {d[30:0], 1'b0} : d;
assign k[1] = (s1[31:30] == 2'd0);
assign s2   = k[1] ? {s1[29:0], 2'd0} : s1;
// ... then 4, 8 and 16 in the same pattern

MISMATCH d=00000002: lzc=15 want 30, y=00010000 want 80000000, zero=0
MISMATCH d=00000004: lzc=15 want 29, y=00020000 want 80000000, zero=0
...
FATAL: tb_lzc_norm.sv:34: FAIL: 88944 of 264033 checks wrong

For d = 2 the small stages fire first and shift by 1 + 2 + 4 + 8 = 15. The 1 is now at bit 16, inside the window of the 16-bit stage, so that stage says no. The right answer, 30 = 16 + 8 + 4 + 2, needed the 16 first. The one-hot class caught it on its second input.

Stretch goals

1. Compare a tree count with a linear chain. Write the count alone two ways: a for loop that overwrites lzc for every set bit, and a tree that counts each half and adds 16 when the upper half is empty. Synthesise both with synth -flatten and run ltp -noff. On our runs the chain gave 88 cells and a path of 31, and the tree 129 cells and a path of 10. Then try feeding the tree's count into a plain barrel shifter and compare with the 18 above. See Priority encoder.

2. Pipeline it. Put a register between stage 4 and stage 2, measure each half with ltp -noff, and move the bench's checks one cycle later. See A three-stage arithmetic pipeline.

3. Adjust the exponent. Add an 8-bit exp_in and output exp_out = exp_in − lzc, with a flag when the result would go below zero. See Saturation policy.

Related topics

• Barrel shifter, rotate and arithmetic shift

• Priority encoder