# Verilog - Synthesize High Speed Leading Zero Count

Using Verilog how do I synthesize the fastest leading zero count on a 64-bit number?

Initially I went with a CASEX(..), with a lot of 01xxxxx, 001xxxxx lines but I understand this synthesizes a barrel shifter which I'm not sure is quick.

My ask is this, what's the fastest way to get to output... what would the gates look like?

I finally came up with this solution but not sure if it will synthesize to something quicker than the above.

The answer to leading zeros in a 64 bit number is either the number of leading zeros in the first 32 bits (if any is a non-zero) or it's 32 + the number of leading zeros in the lower 32 bits. That gives you the answer to the 6th bit of the answer. You then need to find the number of leading zeros in the 32 bit number, so apply the same rules. I had to do an If/else to deal with all zeros.

VERILOG:

// Leading zero count of Sj
if (Sj_int[63:0] == 64'b0)
tmp_cnt = 64;
else
begin
tmp_cnt = 1'b0;
tmp_cnt = (Sj_int[63:31] == 32'b0);
val32 = tmp_cnt ? Sj_int[31:0] : Sj_int[63:32];
tmp_cnt = (val32[31:16] == 16'b0);
val16 = tmp_cnt ? val32[15:0] : val32[31:16];
tmp_cnt = (val16[15:8] == 8'b0);
val8 = tmp_cnt ? val16[7:0] : val16 [15:8];
tmp_cnt = (val8[7:4] == 4'b0);
val4 = tmp_cnt ? val8[3:0] : val8[7:4];
tmp_cnt = (val4[3:2] == 2'b0);
tmp_cnt = tmp_cnt ? ~val4 : ~val4;
end
o_Si <= tmp_cnt[6:0];
end

• Is it a programming question or hardware? In hardware can be done in a single cycle with simple combinatorial logic. – Eugene Sh. Oct 23 '15 at 14:26
• What encryption algorithm does this help you with? – pjc50 Oct 23 '15 at 14:43
• Could you elaborate on your lookup table? How would that work exactly? I think you are aiming at a binary search. A true LOT will use a huge amount of memory. – jippie Oct 23 '15 at 15:22
• I'm voting to close this question as off-topic because this question belongs on Stack Overflow. – Nick Johnson Oct 23 '15 at 15:36
• @NickJohnson I never realized there are Verilog questions on SO. Wouldn't be my first place to lookt though. – jippie Oct 23 '15 at 16:08

## 3 Answers

Leading zero encoders can be made with a nice balanced tree structure.

First, encode bits 2 by 2 :

• 00 => 10 : 2 leading zeros
• 01 => 01 : 1 leading zero
• 10 => 00 : 0 leading zero
• 11 => 00 : 0 leading zero

Then, assemble as pairs.

• If both sides start with 1xxx, the result is 10...0
• If the left side start with 0 the result is 0[left]
• If the left side starts with 1, the result is 01[right(msb-1:0)]

You only need multiplexers.

For example the 8 bits value : 00000111

• 2 by 2 : 00 00 01 11
• encoded : 10 10 01 00
• assemble : 100 001
• assemble : 0101 = 5 leading zeros.

In VHDL (I have no Verilog code at hand), you get that :

FUNCTION enc(CONSTANT a : unsigned(1 DOWNTO 0)) RETURN unsigned IS
BEGIN
CASE a IS
WHEN "00" => RETURN "10";
WHEN "01" => RETURN "01";
WHEN "10" => RETURN "00";
WHEN OTHERS => RETURN "00";
END CASE;
END FUNCTION enc;

FUNCTION clzi(
CONSTANT n : IN natural;
CONSTANT i : IN unsigned) RETURN unsigned IS
VARIABLE v : unsigned(i'length-1 DOWNTO 0):=i;
BEGIN
IF v(n-1+n)='0' THEN
RETURN (v(n-1+n) AND v(n-1)) & '0' & v(2*n-2 DOWNTO n);
ELSE
RETURN (v(n-1+n) AND v(n-1)) & NOT v(n-1) & v(n-2 DOWNTO 0);
END IF;
END FUNCTION clzi;

FUNCTION clz64 (CONSTANT v : unsigned(0 TO 63)) RETURN unsigned IS
VARIABLE e : unsigned(0 TO 63);     -- 64
VARIABLE a : unsigned(0 TO 16*3-1); -- 48
VARIABLE b : unsigned(0 TO 8*4-1);  -- 32
VARIABLE c : unsigned(0 TO 4*5-1);  -- 20
VARIABLE d : unsigned(0 TO 2*6-1);  -- 12
BEGIN
FOR i IN 0 TO 31 LOOP e(i*2 TO i*2+1):=enc(v(i*2 TO i*2+1));  END LOOP;
FOR i IN 0 TO 15 LOOP a(i*3 TO i*3+2):=clzi(2,e(i*4 TO i*4+3)); END   LOOP;
FOR i IN 0 TO 7  LOOP b(i*4 TO i*4+3):=clzi(3,a(i*6 TO i*6+5)); END   LOOP;
FOR i IN 0 TO 3  LOOP c(i*5 TO i*5+4):=clzi(4,b(i*8 TO i*8+7)); END LOOP;
FOR i IN 0 TO 1  LOOP d(i*6 TO i*6+5):=clzi(5,c(i*10 TO i*10+9)); END LOOP;
RETURN clzi(6,d(0 TO 11));
END FUNCTION clz64;


enc() does the encoding clzi() merges two vectors. clz64() is a sample implementation for a 64bits input.

• How would that compare in speed to just a lookup table with 64 items? It appears there would be quite a few clock cycles to get through these steps. – J Kula Oct 24 '15 at 19:29
• A 64bits LZC has 64inputs and 7 outputs. Implemented as a table, it is 7 * (2**64) bits. Quite large. Impossibly large. Crazy large. Larger than the RAM of all supercomputers on earth. – TEMLIB Oct 24 '15 at 19:39
• Maybe you are thinking about "content adressable memory", used mostly in network equipment. It could be possible to store a priority encoder in one such memory, but the circuit complexity is far larger than the solution above. – TEMLIB Oct 24 '15 at 19:42
• @TEMLIB: Nice trick, I didn't know this one. Upvoted. It deserves a comparison with the other natural divide-and-conquer approach. – Renaud Pacalet Oct 25 '15 at 5:41

I've just rewrote previous (and brilliant) solution on Verilog.

module enc
(
input wire     [1:0]       d,
output logic   [1:0]       q
);

always_comb begin
case (d[1:0])
2'b00    :  q = 2'b10;
2'b01    :  q = 2'b01;
default  :  q = 2'b00;
endcase
end

endmodule // enc

module clzi #
(
// external parameter
parameter   N = 2,
// internal parameters
parameter   WI = 2 * N,
parameter   WO = N + 1
)
(
input wire     [WI-1:0]    d,
output logic   [WO-1:0]    q
);

always_comb begin
if (d[N - 1 + N] == 1'b0) begin
q[WO-1] = (d[N-1+N] & d[N-1]);
q[WO-2] = 1'b0;
q[WO-3:0] = d[(2*N)-2 : N];
end else begin
q[WO-1] = d[N-1+N] & d[N-1];
q[WO-2] = ~d[N-1];
q[WO-3:0] = d[N-2 : 0];
end
end

endmodule // clzi


You can use recursion to implement your binary-search type thing succinctly.

module count_lead_zero #(
parameter W_IN = 64, // Must be power of 2, >=2
parameter W_OUT = $clog2(W_IN) // Let this default ) ( input wire [W_IN-1:0] in, output wire [W_OUT-1:0] out ); generate if (W_IN == 2) begin: base assign out = !in; end else begin: recurse wire [W_OUT-2:0] half_count; wire [W_IN / 2-1:0] lhs = in[W_IN / 2 +: W_IN / 2]; wire [W_IN / 2-1:0] rhs = in[0 +: W_IN / 2]; wire left_empty = ~|lhs; count_lead_zero #( .W_IN (W_IN / 2) ) inner ( .in (left_empty ? rhs : lhs), .out (half_count) ); assign out = {left_empty, half_count}; end endgenerate endmodule  Yosys synth results for 64 bits: === count_lead_zero === Number of cells: 121$_ANDNOT_                       1
$_AOI3_ 1$_MUX_                         56
$_NOR_ 1$_NOT_                          7
$_ORNOT_ 1$_OR_                          54


It's fairly compact, but critical path will be through one mux layer and one NOR reduction per stage (since the reduction trees don't start computing correct output til their inputs are valid), which works out to ~20 logic levels to get the LSB. I imagine the other solution with the balanced tree would be faster but similarly-sized.

Note that this will give an output of 63 (all-ones) if given an all-zeroes input; you didn't specify this in your question so not sure if this is needed. This is simple and cheap to amend: do a NOR reduction on the whole input, concatenate this bit to the LHS of the result, and mask off the rest of the result when this bit is set.