// See LICENSE for license details.

/** Miscellaneous circuit generators operating on bits.
  */

package chisel3.util

import chisel3._
import chisel3.core.SeqUtils

object FillInterleaved
{
  def apply(n: Int, in: UInt): UInt = apply(n, in.toBools)
  def apply(n: Int, in: Seq[Bool]): UInt = Cat(in.map(Fill(n, _)).reverse)
}

/** Returns the number of bits set (i.e value is 1) in the input signal.
  */
object PopCount
{
  def apply(in: Iterable[Bool]): UInt = SeqUtils.count(in.toSeq)
  def apply(in: Bits): UInt = apply((0 until in.getWidth).map(in(_)))
}

/** Fill fans out a UInt to multiple copies */
object Fill {
  /** Fan out x n times */
  def apply(n: Int, x: UInt): UInt = {
    n match {
      case 0 => UInt.width(0)
      case 1 => x
      case _ if x.widthKnown && x.getWidth == 1 =>
        Mux(x.toBool, UInt((BigInt(1) << n) - 1, n), UInt(0, n))
      case _ if n > 1 =>
        val p2 = Array.ofDim[UInt](log2Up(n + 1))
        p2(0) = x
        for (i <- 1 until p2.length)
          p2(i) = Cat(p2(i-1), p2(i-1))
        Cat((0 until log2Up(n + 1)).filter(i => (n & (1 << i)) != 0).map(p2(_)))
      case _ => throw new IllegalArgumentException(s"n (=$n) must be nonnegative integer.")
    }
  }
}

/** Litte/big bit endian convertion: reverse the order of the bits in a UInt.
*/
object Reverse
{
  private def doit(in: UInt, length: Int): UInt = {
    if (length == 1) {
      in
    } else if (isPow2(length) && length >= 8 && length <= 64) {
      // This esoterica improves simulation performance
      var res = in
      var shift = length >> 1
      var mask = UInt((BigInt(1) << length) - 1, length)
      do {
        mask = mask ^ (mask(length-shift-1,0) << shift)
        res = ((res >> shift) & mask) | ((res(length-shift-1,0) << shift) & ~mask)
        shift = shift >> 1
      } while (shift > 0)
      res
    } else {
      val half = (1 << log2Up(length))/2
      Cat(doit(in(half-1,0), half), doit(in(length-1,half), length-half))
    }
  }
  def apply(in: UInt): UInt = doit(in, in.getWidth)
}