Crate guff_matrix[−][src]

Expand description

Fast SIMD matrix multiplication for finite fields

This crate implements two things:

  1. Fast SIMD-based multiplication of vectors of finite field elements (GF(28) with the polynomial 0x11b)

  2. A (cache-friendly) matrix multiplication routine based on achieving 100% utilisation of the above

This crate supports x86_64 and Arm (v7, v8) with NEON extensions.

The matrix multiplication routine is heavily geared towards use in implementing Reed-Solomon or Information Dispersal Algorithm error-correcting codes.

Building

For x86_64 and Armv8 (Aarch64), building should require no extra options:

cargo build

Optional Features

Currently available options are:

  • simulator — Software simulation of “wrap-around read matrix” (“warm”) multiply
  • arm_dsp — Armv6 (dsp) 4-way SIMD multiply
  • arm_long — Armv7/Armv8 8-way NEON reimplementation of Armv6 code
  • arm_vmull — Armv7/Armv8 8-way NEON vmull/vtbl multiply

To enable building these, use the --features option when building, eg:

RUSTFLAGS="-C target-cpu=native" cargo build --features arm_vmull

Software Simulation Feature

I’ve implemented two Rust version of the matrix multiplication code. See the simulator module for details.

The overall organisation of the main functionality of this crate is modelled on the second simulation (SIMD version).

Modules

simulator

Non-SIMD, pure Rust simulation of matrix multiplication algorithm

x86

x86_64-specific SIMD

Traits

Simd

SIMD support, based on simulator module

SimdMatrix

Trait for a matrix that supports Simd iteration

Functions

_monomorph
gcd

Greatest Common Divisor for two integers

gcd3

Greatest Common Divisor for three integers

gcd4

Greatest Common Divisor for four integers

lcm

Least Common Multiple for two integers

lcm3

Least Common Multiple for three integers

lcm4

Least Common Multiple for four integers

reference_matrix_multiply

Reference matrix multiply. Doesn’t use SIMD at all, but uses generic Simd types to be compatible with actual Simd implementations. Note that this multiply routine does not check the gcd condition so it can be used to multiply matrices of arbitrary sizes.

simd_warm_multiply⚠