🧠 MIPS Bloom Filter Membership Evaluator

A high-performance, low-level implementation of a Bloom Filter probabilistic data structure, written entirely in MIPS Assembly. This project showcases complex bitwise manipulation, custom hashing algorithms, and efficient memory management.

🚀 Overview

A Bloom Filter is a space-efficient data structure used to test whether an element is a member of a set. This implementation evaluates a target_str against a 160-bit bloom_matrix using multiple hash iterations to provide fast membership testing.

Key Technical Features:

• Custom Mathematical Hashing: Implements a multiplicative hash (hash * 31 + char) with an Avalanche Effect created by 15-bit left and 17-bit right rotations.
• Bit-Matrix Traversal: Efficiently maps hash values to a 5-word (160-bit) matrix using modular arithmetic.
• Sophisticated Bit Manipulation: Uses srlv and andi instructions to isolate and verify specific bits within 32-bit registers.
• Strict Stack Protocol: Follows standard calling conventions, preserving seven $s registers and the return address ($ra) via stack pointers.

🧠 Technical Deep Dive

1. Hashing Algorithm

The hash function uses a seed-based approach to generate unique results for each iteration.

• Multiplier: 31 (Prime number to minimize collisions).
• Bitwise Rotation: Ensures that even a 1-bit difference in input results in a significantly different hash (avalanche effect).

2. Matrix Indexing Logic

The evaluator treats the memory as a grid:

• Row Selection: Hash % 5 determines which of the 5 words in the matrix to load.
• Column Selection: Hash % 32 determines the exact bit position within that word.

🛠 Register Mapping

To maintain high performance and readability, the following registers are dedicated to core tasks:

Register	Purpose
$s0	Pointer to the input string (Target)
$s1	Base address of the Bloom Matrix
$s2	Total number of hash iterations (hash_count)
$s3	Calculated length of the input string
$s4	Current loop counter for hashing
$v0	Return Value: 1 (Match found) / 0 (No match)

💻 How to Run

1. Load the .asm file into MARS or SPIM simulator.

2. The bloom_matrix is currently initialized to 0xFFFFFFFF (all bits set) for demonstration. change inputs if you want.

3. Assemble and Run. The program will output 1 if the string passes all hash checks, indicating a potential match.

📝 Performance Note

This implementation focuses on the Evaluation (membership check) phase. For production use, the matrix would be populated during an ingestion phase using the same hashing logic to set bits via OR operations.