[!WARNING] This library was made with the help of AI. Audit the code yourself, or with your own agent before using.

[!WARNING] fgf is variable-time throughout and guarantees no constant-time operation. Security applications are not a supported use: any handling of secret field elements, coefficients, or buffers must be audited separately.

fgf — Faster Galois Fields

fgf provides finite-field elements and high-throughput operations over packed buffers. It targets the arithmetic underneath erasure coding, proof systems, and other workloads that repeatedly scale, combine, or reconstruct rows.

fgf is an arithmetic library, not a codec. It does not construct coding matrices, own shards, invert matrices, or implement a recovery protocol.

Installation

The minimum supported Rust version is 1.93.

[dependencies]
fgf = "2.1.0"

For the portable no_std surface without allocation:

[dependencies]
fgf = { version = "2.1.0", default-features = false }

Quick start

Scalar elements expose inherent const arithmetic:

use fgf::gf16;

const A: gf16::Elem = gf16::Elem::from_raw(0x1234);
const B: gf16::Elem = gf16::Elem::from_raw(0x0108);
const PRODUCT: gf16::Elem = A.mul(B);

assert_eq!(PRODUCT.div(B), A);

Packed operations use the field marker as their generic parameter. Buffers contain consecutive little-endian elements and may be unaligned.

use fgf::{Gf8B, gf8b, ops};

let src = [0x01u8, 0x02, 0x03, 0x04];
let mut dst = [0u8; 4];

ops::mul_add::<Gf8B>(&mut dst, gf8b::Elem::from_raw(0x03), &src);
assert_eq!(dst, [0x03, 0x06, 0x05, 0x0c]);

Runnable examples

The examples/ programs use the stable API, print their results, and assert the demonstrated identities or recovered data. Each file is self-contained.

Run one example with Cargo:

cargo run --example shard_recovery

From a repository checkout, the recipes run one example or the complete educational set:

just example shard_recovery
just examples
just examples --all-features
just examples --no-default-features --features alloc
just example field_arithmetic --no-default-features
SIMD_BACKEND=scalar just examples

shard_recovery, streaming_encode, and prime_vectors require alloc; the other examples also work with the library's features disabled. The executables themselves use the host's standard library. The scalar override exercises the portable backend; packed examples report the backend for their field.

The coding examples supply fixed coefficients and cover only their stated error or erasure patterns. They illustrate field operations, not production codecs or general matrix solvers. Prime-field packing preserves raw lanes, so canonicalization happens explicitly before packed arithmetic. These examples do not make the library suitable for secret inputs.

peel_probe is a timing diagnostic, not a usage tutorial, and is excluded from just examples.

Supported fields

All element families support arithmetic operators including unary negation, assignment operators, Sum, Product, ordering, formatting, and named raw conversions. In characteristic two negation is the identity. Import fgf::field::Elem when generic code needs the trait methods.

By convention, inversion and division are total: inv(0) == 0 and x / 0 == 0.

Packed operations

The _with forms consume prepared coefficients. Preparation does not weaken validation: prepared and one-shot operations enforce the same public geometry.

use fgf::{Gf16, gf16, ops};

let coeff = ops::Coeff::<Gf16>::new(gf16::Elem::from_raw(0x0108));
let src = 0x1234u16.to_le_bytes();
let mut dst = [0u8; 2];

for _ in 0..3 {
    ops::mul_add_with::<Gf16>(&mut dst, &coeff, &src);
}

let once = gf16::Elem::from_raw(0x1234).mul(gf16::Elem::from_raw(0x0108));
assert_eq!(dst, once.to_bytes());

Coeff<F> prepares one coefficient without allocation. With alloc, CoeffVec<F> and CoeffMatrix<F> own reusable prepared collections; a single entry borrows as CoeffRef<'_, F>, which the single-coefficient _with operations accept directly. Prepared values are process-backend-specific and should be rebuilt rather than serialized.

ops::pack, ops::unpack, and ops::pack_to_vec convert between typed elements and packed byte buffers.

Bit-packed GF(2)

The bits module stores one GF(2) element per bit, least-significant bit first. Operations that depend on the logical element count take it explicitly.

use fgf::bits;

let mut row = [0u8; 1];
bits::set_range(&mut row, 7, 0, 7);
bits::clear_range(&mut row, 7, 1, 3);

assert_eq!(row[0], 0b0111_1001);
assert_eq!(bits::weight(&row, 7), 5);

Range operations leave padding bits untouched. Whole-buffer operations process the complete supplied slices.

Features

Nothing behind internals is a compatibility promise; the facade groups the implementation modules under fgf::internals and may change shape in any release. Normal users should use ops, which handles backend selection and capability proofs internally.

Platforms and backends

backend() reports the process-wide selection. backend_for::<F>() reports the backend implemented by a particular field. SIMD_BACKEND may request a weaker backend at process startup; unsupported upgrades are ignored.

Frozen encodings

These are the wire conventions a consumer above this crate depends on. Each is stated in full by the module that owns it.

Safety and scope

The stable API is safe, but the implementation is variable-time. Table lookups, cache behavior, and data-dependent work make fgf unsuitable for secret field elements or coefficients.

Packed prime-field operations expect canonical input lanes and preserve canonical output. Scalar prime-field operations accept any raw lane and reduce arithmetic results canonically.

Performance

BENCHMARKS.md reports current public API timings and interleaved competitor comparisons on Tiger Lake and Golden Cove, with paired values in each result cell. The complete snapshot campaign runs on each host's isolated CPU:

FEC_GOLDEN_CORE=<cpu> just bench-gf-comp
FEC_GOLDEN_CORE=<cpu> just bench-gdl-comp
FEC_GOLDEN_CORE=<cpu> just bench-m31-comp
FEC_GOLDEN_CORE=<cpu> just bench-gf2-comp

Building

cargo build
cargo build --no-default-features
cargo test --all-features

License

MIT — see LICENSE.