gf256

A Rust library containing Galois-field types and utilities, leveraging hardware instructions when available.

This project started as a learning project to learn more about these "Galois-field thingies" after seeing them pop up in far too many subjects. So this crate may be more educational than practical.

``` rust use ::gf256::*;

let a = gf256(0xfd); let b = gf256(0xfe); let c = gf256(0xff); assert_eq!(a(b+c), ab + a*c); ```

If you, like me, are interested in learning more about the fascinating utility of Galois-fields, take a look at the documentation of gf256's modules. I've tried to comprehensively capture what I've learned, hopefully provided a decent entry point into learning more about this useful field of math.

I also want to point out that the Rust examples in each module are completely functional and tested in CI thanks to Rust's doctest runner. Feel free to copy and tweak them to see what happens.

Reed-Solomon error-correction using gf256

text ..:::::::::::... .:::....:::.:.:.'':.'.:.'::: : :' '' ''' .:::::::::::::::::::.. :::::::::::: .:....'.. '.:... :' :'':': .' .::::::::::::::::::::::::. ::::::::::' . :..:..:' : '.'::: :.':'' ' : .:::::::::::::::::::::::::::. . :::::::::: :: '::' .: '' ''. : :: .:..::. ' .:::::::::::::::::::::::::::::: ... :: :'::::::' ::':. ':' .: '.:'::'::: ': '...: :::::::::::::::::::::::::::::'' .. '::: ' ''' ''..:.:'.''::. .:.' .'': '. .: :::::::::::::::::::::::::::''..::::: ' : .: .'. : :::.'.:':.:':: .. : :::::::::::::::::::::::'' ..:::::'' ' :... .': ::.''':' .''. . ' .. :::::::::::::::::::'' ..:::::'' . : :..':::.:. : .:' :. .':'.': ..: ::::::::::::::''' ..:::::'' ..::: :' . :.' .'.'::. ' ::' ': .:. ..:::' :::::::::'' ..::::::'' ..::::::: :' . '.'::'.: : .:'' .:.'.:::' :::' ':::'' ...::::::''...:::::::::: '' ' .'::...' :':...':.. . .' : ::' ...::::::'' ..:::::::::::::' . .. ' .:::.'':::. .':''':::... ....:::::::'' ..:::::::::::::::::' : '.' .': :. .:.': . .' . ::' '::::::::''' :::::::::::::::::::'' '.. .: ::: ': ::'::. ' '.': : ' '':::::::::::''' .:.':.. '''. : : ':'':.': '.:':

What are Galois-fields?

Galois-fields, also called finite-fields, are a finite set of "numbers" (for some definition of number), that you can do "math" on (for some definition of math).

More specifically, Galois-fields support addition, subtraction, multiplication, and division, which follow a set of rules called "field axioms":

  1. Subtraction is the inverse of addition, and division is the inverse of multiplication:

    ``` rust

    use ::gf256::*;

    #

    let a = gf256(1);

    let b = gf256(2);

    asserteq!((a+b)-b, a); asserteq!((a*b)/b, a); ```

    Except for 0, over which division is undefined:

    ``` rust

    use ::gf256::*;

    #

    let a = gf256(1);

    asserteq!(a.checkeddiv(gf256(0)), None); ```

  2. There exists an element 0 that is the identity of addition, and an element 1 that is the identity of multiplication:

    ``` rust

    use ::gf256::*;

    #

    let a = gf256(1);

    asserteq!(a + gf256(0), a); asserteq!(a * gf256(1), a); ```

  3. Addition and multiplication are associative:

    ``` rust

    use ::gf256::*;

    #

    let a = gf256(1);

    let b = gf256(2);

    let c = gf256(3);

    asserteq!(a+(b+c), (a+b)+c); asserteq!(a(bc), (ab)c); ```

  4. Addition and multiplication are commutative:

    ``` rust

    use ::gf256::*;

    #

    let a = gf256(1);

    let b = gf256(2);

    asserteq!(a+b, b+a); asserteq!(ab, ba); ```

  5. Multiplication is distributive over addition:

    ``` rust

    use ::gf256::*;

    #

    let a = gf256(1);

    let b = gf256(2);

    let c = gf256(3);

    assert_eq!(a(b+c), ab + a*c); ```

Keep in mind these aren't your normal integer operations! The operations defined in a Galois-field types satisfy the above rules, but they may have unintuitive results:

``` rust

use ::gf256::*;

# assert_eq!(gf256(1) + gf256(1), gf256(0)); ```

This also means not all of math works in a Galois-field:

``` rust

use ::gf256::*;

#

let a = gf256(1);

assert_ne!(a + a, gf256(2)*a); ```

Finite-fields can be very useful for applying high-level math onto machine words, since machine words (u8, u16, u32, etc) are inherently finite. Normally we just ignore this until an integer overflow occurs and then we just waive our hands around wailing that math has failed us.

In Rust this has the fun side-effect that the Galois-field types are incapable of overflowing, so Galois-field types don't need the set of overflowing operations normally found in other Rust types:

``` rust

use ::gf256::*;

# let a = (u8::MAX).checked_add(1); // overflows :( let b = gf256(u8::MAX) + gf256(1); // does not overflow :) ```

For more information on Galois-fields and how we construct them, see the relevant documentation in gf's module-level documentation.

Included in gf256

gf256 contains a bit more than the Galois-field types. It also contains a number of other utilities that rely on the math around finite-fields:

Since this math depends on some rather arbitrary constants, each of these utilities is available as both a normal Rust API, defined using reasonable defaults, and as a highly configurable proc_macro:

``` rust

pub use ::gf256::*;

use gf256::gf::gf;

[gf(polynomial=0x11b, generator=0x3)]

type gf256_rijndael;

fn main() {

let a = gf256rijndael(0xfd); let b = gf256rijndael(0xfe); let c = gf256rijndael(0xff); asserteq!(a(b+c), ab + a*c);

}

```

Hardware support

Most modern 64-bit hardware contains instructions for accelerating this sort of math. This usually comes in the form of a carry-less multiplication instruction.

Carry-less multiplication, also called polynomial multiplication and xor multiplication, is the multiplication analog for xor. Where traditional multiplication can be implemented as a series of shifts and adds, carry-less multiplication can be implemented as a series of shifts and xors:

``` text Multiplication:

1011 * 1101 = 1011 + 1011 + 1011 ---------- = 10001111

Carry-less multiplication:

1011 * 1101 = 1011 ^ 1011 ^ 1011 ---------- = 01111111 ```

64-bit carry-less multiplication is available on x86_64 with the pclmulqdq, and on aarch64 with the slightly less wordy pmull instruction.

gf256 takes advantage of these instructions when possible. However, at the time of writing, pmull support in Rust is only available on nightly. To take advantage of pmull on aarch64 you will need to use a nightly compiler and enable gf256's nightly feature (tracking issue).

``` rust

use ::gf256::*;

# // uses carry-less multiplication instructions if available let a = p32(0b1011); let b = p32(0b1101); assert_eq!(a * b, p32(0b01111111)); ```

gf256 also exposes the flag [HAS_XMUL], which can be used to choose algorithms based on whether or not hardware accelerated carry-less multiplication is available:

``` rust

use gf256::p::p32;

# let a = p32(0b1011); let b = if gf256::HAS_XMUL { a * p32(0b11) } else { (a << 1) ^ a }; ```

gf256 also leverages the hardware accelrated carry-less addition instructions, sometimes called polynomial addition, or simply xor. But this is much less notable.

const fn support

Due to the use of traits and intrinsics, it's not possible to use the polynomial/Galois-field operators in const fns.

As an alternative, gf256 provides a set of "naive" functions, which provide less efficient, well, naive, implementations that can be used in const fns.

These are very useful for calculating complex constants at compile-time, which is common in these sort of algorithms:

``` rust

use ::gf256::*;

# const POLYNOMIAL: p64 = p64(0x104c11db7); const CRCTABLE: [u32; 256] = { let mut table = [0; 256]; let mut i = 0; while i < table.len() { let x = (i as u32).reversebits(); let x = p64((x as u64) << 8).naiverem(POLYNOMIAL).0 as u32; table[i] = x.reversebits(); i += 1; } table }; ```

no_std support

gf256 is just a pile of math, so it is mostly no_std compatible.

The exceptions are the extra utilities rs and shamir, which currently require alloc.

Constant-time

gf256 provides "best-effort" constant-time implementations for certain useful operations. Though it should be emphasized this was primarily an educational project, so the constant-time properties should be externally evaluated before use, and you use this library at your own risk.

Features

Testing

gf256 comes with a number of tests implemented in Rust's test runner, these can be run with make:

bash make test

Additionally all of the code samples in these docs can be ran with Rust's doctest runner:

bash make docs

Benchmarking

gf256 also has a number of benchmarks implemented in Criterion. These were used to determine the best default implementations, and can be ran with make:

bash make bench

A full summary of the benchmark results can be found in [BENCHMARKS.md][benchmarks].

[benchmarks]: