A nearly working one cycle per input hardware bitwise run-length encoder written in Chisel

RunLengthEncoderSpec

// See README.md for license details.

package runlengthencoder

import chisel3._
import chisel3.iotesters
import chisel3.iotesters.{ChiselFlatSpec, Driver, PeekPokeTester}
import org.scalatest.{FreeSpec, Matchers}
import chisel3.util.log2Ceil

object BitRunSequence {
  /**
    * This returns a sequence of the number of consecutive bits in a row in a
    * value of the given bit width. for example
    * the value 11101110 returns the sequence List(BitCount(0,1), BitCount(1,3), BitCount(0,1), BitCount(1,3))
    * which means from least bit to most significant bit, this value has 1 zero it, 3 one bits, 1 zero bits and
    * 3 one bits.
    *
    * @param value
    * @param width
    * @return
    */
  def apply(value: Int, width: Int): Seq[BitCount] = {
    var accumulator = 1
    var lastBit = value & 1
    var shiftBuffer = value >> 1
    var result = Seq.empty[BitCount]
    for(bitIndex <- 1 until width) {
      val bottomBit = shiftBuffer & 1
      if((bottomBit) == lastBit) {
        accumulator += 1
      }
      else {
        result = result :+ BitCount(lastBit, accumulator)
        lastBit = bottomBit
        accumulator = 1
      }
      shiftBuffer >>= 1
    }
    result :+ BitCount(lastBit, accumulator)
  }
}

case class BitCount(bitValue: Int, count: Int)


/**
  * This is a bit-wise run length encoder that reads through a vector writes a separate vector
  * with the run-length encoded data. Basically it is a lookup table for each word using [[BitRunSequence]]
  * to set the output. Most of the complexity here is involved with handling the matching of the bits with the
  * previous word. The other minor complexity is that, as designed, the count of the number of the consecutive
  * bits is constrained by the words size.
  *
  * @param inputSize
  * @param outputSize
  * @param wordSize
  */
class RunLengthEncoder(val inputSize: Int, val outputSize: Int, val wordSize: Int) extends Module {
  val io = IO(new Bundle {
    val vectorLoaded = Input(Bool()) // enables-disables the module
    val input        = Input(Vec(inputSize, UInt(wordSize.W)))
    val output       = Output(Vec(outputSize, UInt(wordSize.W)))
    val outputReady  = Output(Bool())
    val busy         = Output(Bool())
  })

  val maxCount: Int = (1 << wordSize) - 1

  val busy        = RegInit(false.B)
  val outputReady = RegInit(true.B)
  val inputIndex  = RegInit(0.U((log2Ceil(inputSize) + 1).W))
  val outputIndex = RegInit(0.U((log2Ceil(outputSize) + 1).W))
  val wordBuffer  = RegInit(0.U(wordSize.W))

  val countFromPreviousWord     = RegInit(0.U(wordSize.W))
  val lastBitFromPreviousWord   = RegInit(false.B)

  io.outputReady := outputReady
  io.output := DontCare
  io.busy := busy

  //
  // Start the engine, here, this could probably be done better with a decoupled interface
  //
  when(io.vectorLoaded) {
    inputIndex := 0.U
    outputIndex := 0.U
    busy := true.B
    outputReady := false.B
    lastBitFromPreviousWord := io.input(0)(0)
    wordBuffer := io.input(0)
    countFromPreviousWord := 0.U
    for (index <- 0 until outputSize) {
      io.output(index.U) := 0.U
    }
  }

  when(busy && ! io.vectorLoaded) {

    for(patternWord <- 0 to maxCount) {
      //
      // For ever possible match value, generate the hardware to handle that case
      //
      when(io.input(inputIndex) === patternWord.U) {
        //
        // Only one of the possible matches can happen in a cycle
        //
        printf("inputIndex %d match %d against pattern %x\n", inputIndex,
          io.input(inputIndex), patternWord.U)
        val consecutiveBitSequence = BitRunSequence(patternWord, width = wordSize)

        //
        // Special case handling for all bits in input word being the same
        // If they are different from previous then push out the previous count
        // If they are the same then you have to be careful that you have not exceeded your
        // count word size. If you will exceed then push out a max count followed by a zero
        // count for the opposite bit value, and then continue accumulating
        //
        val firstElement = consecutiveBitSequence.head
        if(firstElement.count == wordSize) {
          when(firstElement.bitValue.U === lastBitFromPreviousWord && inputIndex > 0.U) {
            countFromPreviousWord := countFromPreviousWord + firstElement.count.U
            when(countFromPreviousWord > maxCount.U) {
              io.output(outputIndex) := maxCount.U
              io.output(outputIndex + 1.U) := 0.U

              countFromPreviousWord := countFromPreviousWord - maxCount.U
              outputIndex := outputIndex + 2.U
            }
          }
                  .otherwise {
                    io.output(outputIndex) := countFromPreviousWord
                    outputIndex := outputIndex + 1.U
                    lastBitFromPreviousWord := ! lastBitFromPreviousWord
                  }
        }
        else {
          //
          // If here then write out the counts using the sequence of values computed in the consecutiveBitSequence
          // The last element does not get pushed out though, it contributes to the carry over.
          // The first one is special cased because it may have to include the count from the last bits of the
          // previous input word
          val incrementFromLastWord = Wire(UInt(1.W))

          val lastElement :: tail = consecutiveBitSequence.reverse
          val firstElement :: middle = tail.reverse
          var numberOfPushes = 1

          when(firstElement.bitValue.U === lastBitFromPreviousWord && inputIndex > 0.U) {
            printf("Case Carryover BitPattern %x Setting output(%d) = %d\n", patternWord.U, outputIndex, countFromPreviousWord + firstElement.count.U)
            io.output(outputIndex) := countFromPreviousWord + firstElement.count.U
            incrementFromLastWord := 0.U
          }
                  .elsewhen(inputIndex === 0.U) {
                    printf("Case No Carryover BitPattern %x Setting output(%d) = %d\n", patternWord.U, outputIndex, firstElement.count.U)
                    io.output(outputIndex) := firstElement.count.U
                    incrementFromLastWord := 0.U
                  }
                  .otherwise {
                    printf("Case input > 0 Carryover BitPattern %x Setting output(%d) = %d\n", patternWord.U, outputIndex, countFromPreviousWord + firstElement.count.U)
                    io.output(outputIndex) := countFromPreviousWord
                    io.output(outputIndex + 1.U) := firstElement.count.U
                    incrementFromLastWord := 1.U
                    numberOfPushes += 1
                  }


          for(element <- middle) {
            io.output(outputIndex + numberOfPushes.U + incrementFromLastWord) := element.count.U
            numberOfPushes += 1
          }

          outputIndex := outputIndex + numberOfPushes.U + incrementFromLastWord

          lastBitFromPreviousWord := lastElement.bitValue.U.toBool()
          countFromPreviousWord := lastElement.count.U
        }
      }
    }

    //
    // increment the input pointer
    // send done signal and turn things off when input exhausted
    //
    inputIndex := inputIndex + 1.U
    when(inputIndex >= inputSize.U) {
      io.output(outputIndex) := countFromPreviousWord
      outputReady := true.B
      busy := false.B
    }
    printf("inputIndex %d outputIndex %d busy %d outputReady %d\n",
      inputIndex, outputIndex, busy, outputReady
    )
  }
}

class RunLengthEncoderTester(c: RunLengthEncoder) extends PeekPokeTester(c) {
  for(i <- 0 until c.inputSize) {
    poke(c.io.input(i), 7)
  }
  poke(c.io.vectorLoaded, 1)
  step(1)
  poke(c.io.vectorLoaded, 0)


  for(j <- 0 to c.inputSize) {
    step(1)

    for (i <- 0 until c.outputSize) {
      println(s"output($i) is ${peek(c.io.output(i))}, busy is ${peek(c.io.busy)} " +
              s"outputReady is ${peek(c.io.outputReady)}")
    }
  }
}

//scalastyle:off magic.number
class RunLengthEncoderSpec extends FreeSpec with Matchers {
  "simple test" in {
    iotesters.Driver.execute(
      Array("--target-dir", "test_run_dir/RLE(4, 8, 8)", "--top-name", "RLE",
      "-tiwv"),
      () => new RunLengthEncoder(1, 8, 8)
    ) {

      c => new RunLengthEncoderTester(c)

    } should be (true)
  }

  "test of bit run sequencer" in {
    for(i <- 0 until 256) {
      val seq = BitRunSequence(value = i, width = 8)
      println(f"${i.toBinaryString.toInt}%08d ${seq}")
      seq.map(_.count).sum should be (8)
    }
  }
}