# elli-gf2
`elli-gf2` is a small cross-language GF(2) elimination library with machine-first backends.
It currently provides four exact strategies:
- `SparseList` — human-semantic sparse sorted-list reduction
- `PackedCached` — packed-bitset sparse-friendly reduction
- `DenseMacro` — bit-packed dense macro-op reduction
- `Auto` — heuristic selector between backends
The current idea is simple:
> different GF(2) workloads favor different machine-level execution shapes, so `elli-gf2` chooses the best backend it knows rather than forcing one universal implementation.
## What it can do today
- exact GF(2) elimination
- backend auto-selection
- generated workload benchmarking
- user-supplied sparse matrix files
- Rust library usage
- C ABI usage
- Python usage via `ctypes`
## Quickstart
### Rust library
```rust
use elli_gf2::{generate_er_sparse, reduce};
let rows = 2048;
let cols = generate_er_sparse(rows, 2048, 0.01, 1337);
let summary = reduce(rows, &cols);
println!("rank = {}", summary.rank);
println!("pivot_count = {}", summary.pivots.len());
```
### CLI benchmark
```bash
cargo run --release --bin bench_cli -- --family er_sparse --rows 2048 --cols 2048 --density 0.01 --compare-all
cargo run --release --bin bench_cli -- --family ldpc_like --rows 2048 --cols 4096 --col-weight 6 --compare-all
cargo run --release --bin bench_cli -- --family banded --rows 2048 --cols 2048 --bandwidth 64 --weight 10 --compare-all
```
### Load your own matrix
```bash
cargo run --release --bin load_cli -- --file examples/sample_matrix.txt --strategy auto
```
Matrix file format:
- first line: `rows=<N>`
- each following non-comment line is one column
- each column line is a whitespace-separated list of row indices
- empty lines count as empty columns
- comment lines begin with `#`
Example:
```text
rows=8
0 2 4
1 4
2 3 7
0 7
1 2 5
3 6
```
## Cross-language usage
### C ABI
Header:
- `include/elli_gf2.h`
Example:
- `examples/c_file_smoke.c`
Build and run:
```bash
cargo build --release
clang -O3 examples/c_file_smoke.c -Iinclude -Ltarget/release -Wl,-rpath,"$PWD/target/release" -lelli_gf2 -o /tmp/elli_gf2_c_file_smoke
/tmp/elli_gf2_c_file_smoke
```
### Python
Recommended setup:
```bash
python3 -m venv .venv
source .venv/bin/activate
cargo build --release
python -m pip install -e .
python examples/python_file_smoke.py
```
Example:
```python
from elli_gf2 import reduce_file_auto
result = reduce_file_auto("examples/sample_matrix.txt")
print(result.rank, result.strategy, result.ok)
```
## Current backend behavior
Observed selector behavior on representative families:
- `er_sparse` → `DenseMacro`
- `ldpc_like` → `PackedCached`
- `banded` → `DenseMacro`
This is intentional: `elli-gf2` is a backend family plus selector, not a one-kernel-fits-all design.
## Project layout
```text
elli-gf2/
Cargo.toml
pyproject.toml
README.md
include/
elli_gf2.h
examples/
c_file_smoke.c
c_smoke.c
python_file_smoke.py
python_smoke.py
rust_file_smoke.rs
sample_matrix.txt
python/
elli_gf2/
__init__.py
scripts/
share_smoke.sh
src/
lib.rs
abi.rs
io.rs
bin/
bench_cli.rs
load_cli.rs
smoke.rs
```
## One-command repo smoke test
```bash
bash scripts/share_smoke.sh
```
## Status
This is an early research-driven library, but it already provides:
- exact GF(2) elimination
- multiple machine-first backends
- automatic backend selection
- Rust, C, and Python entry points
- file-based input for user-supplied matrices