countzero: Faster algorithm for count leading/trailing zeroes
authorPaul Mackerras <paulus@ozlabs.org>
Sat, 11 Jul 2020 02:05:43 +0000 (12:05 +1000)
committerPaul Mackerras <paulus@ozlabs.org>
Tue, 14 Jul 2020 23:49:08 +0000 (09:49 +1000)
commit03a3a5d326d8c79f4fd14668534571049d70eaf7
tree1e3f2f2bcbdf097b61dd4208aba20c07cac7284f
parent1f2058a0edca1d53157c3e87425118712d89004f
countzero: Faster algorithm for count leading/trailing zeroes

This uses an algorithm for count leading/trailing zeroes that is
faster on FPGAs, which makes timing easier.  cntlz* and cnttz*
still take two cycles, though.

For count trailing zeroes, we compute x & -x, which for non-zero x
has a single 1 bit in the position of the least-significant 1 bit
in x.  This one-hot representation can then be converted to a bit
number with six 32-input OR gates.  For count leading zeroes, we
simply do a bit-reversal on x and then use the same algorithm.

Signed-off-by: Paul Mackerras <paulus@ozlabs.org>
countzero.vhdl