Add scanLeftOr and scanRightOr utilies (#2407) (#2437)

Co-authored-by: Jiuyang Liu <liu@jiuyang.me>
Co-authored-by: Megan Wachs <megan@sifive.com>
Co-authored-by: Jack Koenig <koenig@sifive.com>
(cherry picked from commit 73d3c26029c07c17ce179dfead092eab4fb8ae2c)

Co-authored-by: Liu Xiaoyi <circuitcoder0@gmail.com>

2 files changed, 95 insertions, 0 deletions

diff --git a/integration-tests/src/test/scala/chiselTests/util/experimental/algorithm/Bitwise.scala b/integration-tests/src/test/scala/chiselTests/util/experimental/algorithm/Bitwise.scala
new file mode 100644
index 00000000..6c8eb4b4
--- /dev/null
+++ b/integration-tests/src/test/scala/chiselTests/util/experimental/algorithm/Bitwise.scala
@@ -0,0 +1,47 @@
+// SPDX-License-Identifier: Apache-2.0
+
+import chisel3._
+import chisel3.util._
+import chiseltest._
+import chiseltest.formal._
+import org.scalatest.flatspec.AnyFlatSpec
+import scala.math.min
+
+class ScanLeftOrTestModule(width: Int) extends Module {
+  val input = IO(Input(UInt(width.W)))
+
+  var lsb = false.B
+  val vec = for(b <- input.asBools) yield {
+    val cur = b || lsb
+    lsb = cur
+    cur
+  }
+  val ref = VecInit(vec).asUInt
+
+  val testee = scanLeftOr(input)
+
+  assert(testee === ref)
+}
+
+class ScanRightOrTestModule(width: Int) extends Module {
+  val input = IO(Input(UInt(width.W)))
+
+  val ref = Reverse(scanLeftOr(Reverse(input)))
+  val testee = scanRightOr(input)
+
+  assert(testee === ref)
+}
+
+class scanOrTest extends AnyFlatSpec with ChiselScalatestTester with Formal {
+  "scanLeftOr" should "compute correctly" in {
+    for(i <- 1 to 16) {
+      verify(new ScanLeftOrTestModule(i), Seq(BoundedCheck(1)))
+    }
+  }
+
+  "scanRightOr" should "compute correctly" in {
+    for(i <- 1 to 16) {
+      verify(new ScanRightOrTestModule(i), Seq(BoundedCheck(1)))
+    }
+  }
+}
diff --git a/src/main/scala/chisel3/experimental/util/algorithm/Bitwise.scala b/src/main/scala/chisel3/experimental/util/algorithm/Bitwise.scala
new file mode 100644
index 00000000..6b4bb8f0
--- /dev/null
+++ b/src/main/scala/chisel3/experimental/util/algorithm/Bitwise.scala
@@ -0,0 +1,48 @@
+// SPDX-License-Identifier: Apache-2.0
+
+package chisel3.util
+
+import chisel3._
+
+/** Map each bit to the logical OR of itself and all bits with lower index
+  *
+  * Here `scanLeft` means "start from the left and iterate to the right, where left is the lowest index", a common operation on arrays and lists.
+  * @example {{{
+  * scanLeftOr("b00001000".U(8.W)) // Returns "b11111000".U
+  * scanLeftOr("b00010100".U(8.W)) // Returns "b11111100".U
+  * scanLeftOr("b00000000".U(8.W)) // Returns "b00000000".U
+  * }}}
+  */
+object scanLeftOr {
+  def apply(data: UInt): UInt = {
+    val width = data.widthOption match {
+      case Some(w) => w
+      case None    => throw new IllegalArgumentException("Cannot call scanLeftOr on data with unknown width.")
+    }
+
+    def helper(s: Int, x: UInt): UInt =
+      if (s >= width) x else helper(s + s, x | (x << s)(width - 1, 0))
+    helper(1, data)(width - 1, 0)
+  }
+}
+
+/** Map each bit to the logical OR of itself and all bits with higher index
+  *
+  * Here `scanRight` means "start from the right and iterate to the left, where right is the highest index", a common operation on arrays and lists.
+  * @example {{{
+  * scanRightOr("b00001000".U) // Returns "b00001111".U
+  * scanRightOr("b00010100".U) // Returns "b00011111".U
+  * scanRightOr("b00000000".U) // Returns "b00000000".U
+  * }}}
+  */
+object scanRightOr {
+  def apply(data: UInt): UInt = {
+    val width = data.widthOption match {
+      case Some(w) => w
+      case None    => throw new IllegalArgumentException("Cannot call scanRightOr on data with unknown width.")
+    }
+    def helper(s: Int, x: UInt): UInt =
+      if (s >= width) x else helper(s + s, x | (x >> s))
+    helper(1, data)(width - 1, 0)
+  }
+}