name: "Triple-Hash Bloom Filter Engine"
category: "Algorithmic Hardware Primitives"
complexity: "Medium"
description: |
  Implement a synchronous accelerator for approximate membership testing of
  16-bit unsigned keys using a 128-bit Bloom filter.

  The module stores one persistent bit-vector `B[127:0]`. After reset,
  every bit of `B` is 0.

  A request is accepted on each rising edge of `clk` for which `rst=0` and
  `req_valid=1`. There are two request types:

  - Query (`req_insert=0`):
    - Do not modify `B`.
    - Compute the three hash indices `h0`, `h1`, and `h2` from `key_in`.
    - The membership result for this request is 1 if and only if
      `B[h0]`, `B[h1]`, and `B[h2]` were all 1 in the filter state
      immediately before this request was accepted. Otherwise the result is 0.

  - Insert (`req_insert=1`):
    - Compute the same three hash indices from `key_in`.
    - The membership result for this request is defined from the pre-update
      filter state exactly as for Query: it is 1 if and only if all three
      addressed bits were already 1 immediately before the request was
      accepted.
    - After that membership result is determined, set `B[h0]`, `B[h1]`, and
      `B[h2]` to 1. No other bits may change.

  HASH DEFINITIONS:
  - All hash computations treat `key_in` as an unsigned 16-bit value.
  - `>>` is logical right shift and `<<` is logical left shift.
  - Each hash index is the low 7 bits of the corresponding expression, i.e.
    the result lies in the range 0 to 127.
  - `h0 = (key_in ^ (key_in >> 7)) & 16'h007f`
  - `h1 = (key_in + (key_in >> 4) + 16'h002d) & 16'h007f`
  - `h2 = ((key_in << 3) ^ (key_in >> 2) ^ 16'h0053) & 16'h007f`

  OUTPUT TIMING:
  - Each accepted request produces its result on the next clock cycle.
  - If a request was accepted on cycle N, then on cycle N+1
    `maybe_present` must equal the membership result defined above for that
    request.
  - Requests may be accepted on back-to-back cycles. In that case,
    `maybe_present` must present the corresponding sequence of next-cycle
    results on back-to-back cycles.
  - An Insert request must not observe its own bit updates when forming its
    response. However, those updates must be visible to later requests
    accepted on later cycles.

  FALSE-POSITIVE SEMANTICS:
  - This is a Bloom filter, not an exact set.
  - A Query for a key that has never been inserted may legally return
    `maybe_present=1` if earlier inserts for other keys happened to set all
    three bits referenced by that query.
  - A Query for a key whose addressed bits are not all set must return 0.
  - The design never clears individual bits; only reset clears the filter.

  COLLISIONS:
  - Different keys may map to overlapping hash indices.
  - For a given key, `h0`, `h1`, and `h2` are allowed to be equal to each
    other in any combination. No special case is applied: reading or setting
    the same bit more than once is equivalent to using the unique set of
    referenced bit positions.

  RESET:
  - `rst` is synchronous and active-high.
  - While `rst=1`, clear all bits of `B` and drive `maybe_present=0`.
  - A cycle with `rst=1` must not accept a request, and any response that
    would otherwise have appeared on that cycle is discarded.
  - After reset is deasserted, the next accepted request starts from a fully
    empty Bloom filter.

  IDLE CYCLES:
  - If no request was accepted on the previous cycle, `maybe_present` must
    be 0.

interface:
  module_name: "bloom_filter_membership"
  clocked: true
  ports:
    - name: "clk"
      type: "input"
      width: "1"
      description: "System clock"
    - name: "rst"
      type: "input"
      width: "1"
      description: "Synchronous active-high reset"
    - name: "req_valid"
      type: "input"
      width: "1"
      description: "High when the request inputs for this cycle are valid"
    - name: "req_insert"
      type: "input"
      width: "1"
      description: "0 = Query, 1 = Insert"
    - name: "key_in"
      type: "input"
      width: "16"
      description: "Unsigned 16-bit key for the accepted request"
    - name: "maybe_present"
      type: "output"
      width: "1"
      description: "Approximate membership result for the request accepted on the previous cycle, or 0 if no request was accepted on that cycle"

target_platform:
  device_family: "AMD Xilinx Zynq-7000"

tasks:
  - name: "Area-Efficient Bloom Filter Membership Engine"
    constraints:
      max_lut: 220
      max_ff: 180
      max_bram: 0
      max_dsp: 0
      min_frequency: 180
    objective:
      goal: "minimise"
      target: "LUT"
