Efficient Hash-to-Index via Rejection Sampling for Online Fault Detection with Bloom/Cuckoo Filters

Recent studies indicate that resource-efficient online fault detection in dependable computing systems may rely on probabilistic data structures such as Bloom and Cuckoo filters. To be effective and lightweight, these filters require low-latency and resource-efficient hash-to-index mappings. Existing approaches, namely, modulo, power-of-two, and multiplicative indexing, either incur high implementation cost, latency overhead, or impose rigid table size constraints that can lead to over-provisioning and suboptimal memory utilization, limiting their adoption in embedded and real-time systems. To address these limitations, this work proposes a hardware-efficient hash-to-index reduction technique based on rejection sampling. The proposed method optimizes index computation, yielding a uniform distribution for arbitrary table lengths while avoiding costly division or multiplication. Implemented as a mask-then-reject datapath on FPGA, our approach enables lightweight online checkers that maintain low area and latency footprints without sacrificing correctness. Experimental results on Bloom and Cuckoo filters demonstrate similar detection accuracy compared to canonical mappings while reducing hardware cost and latency.