count leading zero in single cycle datapath

Question

As you all might know that the MIPS instruction set supports clz (count leading zero) as follows:

clz $t0,$t1 count leading zeros t0 = # of leading zeros in t1

I am writing a single cycle datapath in verilog and was just wondering what the ALU needs to support in order for me to do this... any ideas??

Answer 1

The simplest implementation I can think of (not very optimized) is checking the word against 32 (in case of 32-bit) masks, longest first, deciding which fits first and returning its number.

Something like (pseudocode):

if word == 0: return 32
elsif (word & 1) == 0: return 31
elsif (word & 3) == 0: return 30

etc.

Answer 2

Here's a possible approach (I'm ignoring the case of an input of 0, which is probably best treated as a special case):

• The number of leading zeros in a 32-bit number is either:
  • the number of leading zeros in the top 16 bits, if any of the top 16 bits are non-zero; or
  • 16, plus the number of leading zeros in the bottom 16 bits, if the top 16 bits are all zero
• That gives the top bit of the 5-bit result (ignoring the special case of an input of 0...).
• Now you need to find the number of leading zeros in a 16-bit number, so apply the same principle again.
• etc.

In Verilog, it might look something like this:

result[4] = (value[31:16] == 16'b0);
val16     = result[4] ? value[15:0] : value[31:16];
result[3] = (val16[15:8] == 8'b0);
val8      = result[3] ? val16[7:0] : val16[15:8];
result[2] = (val8[7:4] == 4'b0);
val4      = result[2] ? val8[3:0] : val8[7:4];
result[1] = (val4[3:2] == 2'b0);
result[0] = result[1] ? ~val4[1] : ~val4[3];