Best way to check if an element is contained in a circular buffer?

[Vincent]

Hi Everyone,

I am facing the following issue: I implemented a circular buffer that can be drained, and I want to provide functionality (over IO or another way if that is better) to check whether a certain element is in the circular buffer.

Consider the code/my attempt below. That code does not work, because if the circular buffer is drained, it will still check all "stale elements" in the buffer, and therefore return the wrong result.

What is the best way in Chisel to actually check whether an addr is in any of the buffer elements before index writePtr?

This is mainly for verification purposes, so performance is not really much of an issue, but I would like to get it right.

Best and thank you!

import chisel3._

import chisel3.util._

class CircularBuffer[T <: Data](gen: T, size: Int) extends Module {

require(isPow2(size), "Buffer size must be a power of 2")

val io = IO(new Bundle {

val enq = Flipped(Decoupled(gen)) // Input for enqueueing data

//val deq = Decoupled(gen) // Output for dequeueing data

val drain = Input(Bool()) // Signal to drain the buffer

val checkAddr = Input(gen) // Address to check for presence in the buffer

val addrFound = Output(Bool()) // Indicates if the address is in the buffer

})

val buffer = Reg(Vec(size, gen)) // Storage for the buffer

val writePtr = RegInit(0.U(log2Ceil(size).W)) // Write pointer

// Write logic

when(io.enq.fire) {

buffer(writePtr) := io.enq.bits

writePtr := writePtr + 1.U

printf("writePtr %x \n", writePtr)

}

when(io.drain){

writePtr := 0.U

}

val addrMatches = buffer.map(_ === io.checkAddr) // Compare all entries to the input address

io.addrFound := addrMatches.reduce(_ || _)

// Connect IO

io.enq.ready := true.B

}

[Edward Wang]

Hi Vincent,

Not sure if this is a Chisel-specific question -- for the logic in
addrMatches, you probably want to consider/use writePtr to restrict
the elements you compare.

Best regards,
Edward

> --
> You received this message because you are subscribed to the Google Groups "chisel-users" group.
> To unsubscribe from this group and stop receiving emails from it, send an email to chisel-users...@googlegroups.com.
> To view this discussion visit https://groups.google.com/d/msgid/chisel-users/7d500893-0e0d-4bb4-ad16-8c67ac1f9e62n%40googlegroups.com.

[Vincent]

Hi Edward,

Thanks! Let me rephrase my question. As you write I  want to consider/use writePtr to restrict
the elements you compare.

What is the appropriate Chisel construct to do so? For example, can I somehow restrict the map or the reduce function to only consider the first writePtr elements in buffer?

Best,
Vincent

[Edward Wang]

Hi Vincent,

You could consider something like this to ensure that the particular
index is currently used (untested). There are probably other ways to
do it as well.

buffer.zipWithIndex.map { case (e, i) => i < writePtr && e === io.checkAddr }

Best regards,
Edward

> To view this discussion visit https://groups.google.com/d/msgid/chisel-users/90b24c71-fbe2-45b1-966c-7b930e2b156dn%40googlegroups.com.