Merge branch 'master' into sdtwigg_connectwrap_renamechisel3

1 files changed, 12 insertions, 4 deletions

diff --git a/src/main/scala/chisel3/util/CircuitMath.scala b/src/main/scala/chisel3/util/CircuitMath.scala
index 8f8bde4a..27bd7bfb 100644
--- a/src/main/scala/chisel3/util/CircuitMath.scala
+++ b/src/main/scala/chisel3/util/CircuitMath.scala
@@ -7,11 +7,11 @@ package chisel3.util
 
 import chisel3._
 
-/** Compute Log2 with truncation of a UInt in hardware using a Mux Tree
-  * An alternative interpretation is it computes the minimum number of bits needed to represent x
+/** Compute the base-2 integer logarithm of a UInt
   * @example
   * {{{ data_out := Log2(data_in) }}}
-  * @note Truncation is used so Log2(UInt.Lit(12412)) = 13*/
+  * @note The result is truncated, so e.g. Log2(13.U) = 3
+  */
 object Log2 {
   /** Compute the Log2 on the least significant n bits of x */
   def apply(x: Bits, width: Int): UInt = {
@@ -19,10 +19,18 @@ object Log2 {
       UInt.Lit(0)
     } else if (width == 2) {
       x(1)
+    } else if (width <= divideAndConquerThreshold) {
+      Mux(x(width-1), UInt.Lit(width-1), apply(x, width-1))
     } else {
-      Mux(x(width-1), UInt.width(width-1), apply(x, width-1))
+      val mid = 1 << (log2Ceil(width) - 1)
+      val hi = x(width-1, mid)
+      val lo = x(mid-1, 0)
+      val useHi = hi.orR
+      Cat(useHi, Mux(useHi, Log2(hi, width - mid), Log2(lo, mid)))
     }
   }
 
   def apply(x: Bits): UInt = apply(x, x.getWidth)
+
+  private def divideAndConquerThreshold = 4
 }