Trait galois_2p8::field::Field

source · 
pub trait Field {

Show 23 methods    fn polynomial(&self) -> IrreducablePolynomial;
    fn mult(&self, src: u8, scale: u8) -> u8;
    fn div(&self, src: u8, scale: u8) -> u8;
    fn two_pow(&self, x: u8) -> u8;
    fn mult_two_pow(&self, scale: u8, x: u8) -> u8;
    unsafe fn add_ptr_scaled_len(
        &self,
        dst: *mut u8,
        src: *const u8,
        scale: u8,
        len: usize
    );
    unsafe fn mult_ptr_len(&self, dst: *mut u8, scale: u8, len: usize);
    unsafe fn div_ptr_len(&self, dst: *mut u8, scale: u8, len: usize);

    fn add(&self, left: u8, right: u8) -> u8 { ... }
    fn sub(&self, left: u8, right: u8) -> u8 { ... }
    unsafe fn add_ptr_len(&self, dst: *mut u8, src: *const u8, len: usize) { ... }
    fn add_multiword(&self, dst: &mut [u8], src: &[u8]) { ... }
    fn add_multiword_len(&self, dst: &mut [u8], src: &[u8], len: usize) { ... }
    fn add_scaled_multiword(&self, dst: &mut [u8], src: &[u8], scale: u8) { ... }
    fn add_scaled_multiword_len(
        &self,
        dst: &mut [u8],
        src: &[u8],
        scale: u8,
        len: usize
    ) { ... }
    unsafe fn sub_ptr_len(&self, dst: *mut u8, src: *const u8, len: usize) { ... }
    unsafe fn sub_ptr_scaled_len(
        &self,
        dst: *mut u8,
        src: *const u8,
        scale: u8,
        len: usize
    ) { ... }
    fn sub_multiword(&self, dst: &mut [u8], src: &[u8]) { ... }
    fn sub_multiword_len(&self, dst: &mut [u8], src: &[u8], len: usize) { ... }
    fn sub_scaled_multiword(&self, dst: &mut [u8], src: &[u8], scale: u8) { ... }
    fn sub_scaled_multiword_len(
        &self,
        dst: &mut [u8],
        src: &[u8],
        scale: u8,
        len: usize
    ) { ... }
    fn mult_multiword(&self, dst: &mut [u8], scale: u8) { ... }
    fn div_multiword(&self, dst: &mut [u8], scale: u8) { ... }

}
Expand description

Establishes GF(2^8) arithmetic for scalar and vector operands.

In all instances of GF(2^8), over every possible IrreducablePolynomial, addition and subtraction is defined as XOR, as in GF(2). Addition and subtraction are accordingly provided as default implementations of this trait.

Multiplication and division are more complicated, and the optimal strategy for implementing them in a scalar context depends on whether the IrreducablePolynomial over which the field is implemented is a primitive polynomial.

Recall that if a p: IrreducablePolynomial is primitive, then all members of the field in which operations are performed modulo p can be represented as 2^n for n in [0..255], with the exception of 0.

In these cases, we can represent multiplication and division as addition and subtraction within logarithmic representations of the operands. This requires fewer instructions to implement at the scalar level. Note that this cannot be done for an IrreducablePolynomial that is not also primitive. As a consequence, we provide two concrete implementations of this trait: GeneralField and PrimitivePolynomialField, where the slightly faster logarithm arithmetic is only used in the latter.

This trait also exposes operations over vectors containing GF(2^8) members.

Common operations over GF(2^8) operands can exploit long-word vector operations as implemented by the target hardware. A trivial example is the addition and subtraction of vectors: this is a simple bitwise XOR across a very long word. This already functions as expected in Rust 1.25 as a consequence of LLVM optimizations. A less trivial example involves multiplication and division: vector processors require a specialized long-word lookup function to implement these operations.

The x86_64 architecture mandates SSE4.2 and earlier, as is found in the earlier x86 architecture; in SSE3, an intrinsic _mm_shuffle_epi8 was added that allows the entries of a vector register a to function as indices of the vector register b in the lower four bits, effectively implementing an accelerated 16-entry table lookup. These SSE3 intrinsics are used for multiword operations if the "simd" feature is enabled.

As of Rust 1.27.2, code generation for AVX on the default ABI results in the generation of incorrect code. Because of this, galois_2p8 only uses AVX 2 intrinsics for optimized multiplication and division if the rustc target feature avx2 is enabled, e.g. exporting RUSTFLAGS="-C target-feature=avx2 before running rustc or cargo.

Required Methods§

Returns the polynomial modulo which all operations are performed.

Returns the result of src * scale in this field.

Returns the result of src / scale in this field.

Implementations of this method are expected to panic if the scale argument is zero. The contents of the resulting error message are not defined.

Returns the result of 2^x in this field.

Returns the result of scale * 2^x in this field.

Adds scale * src[0..len] into dst[0..len] in place.

Multiplies dst[0..len] by scale in place.

Divides dst[0..len] by scale in place.

Implementations of this method are expected to panic if the scale argument is zero. The contents of the resulting error message are not defined.

Provided Methods§

Adds left and right, returning their sum.

Subtracts right from left, returning the difference.

Adds src[0..len] into dst[0..len].

Adds src into dst in place, over the smallest common length.

The length used in operation is set to the minimum of src.len() and dst.len().

Adds src[0..len] into dst[0..len].

This method will panic if src.len() or dst.len() is less than the supplied len parameter.

Adds src * scale into dst in place, over the smallest common length.

The length used in the operation is set to the minimum of src.len() and dst.len().

Adds src[0..len] * scale into dst[0..len].

This method will panic if src.len() or dst.len() is less than the supplied len parameter.

Subtracts src[0..len] from dst[0..len] in place.

Subracts scale * src[0..len] from dst[0..len] in place.

Subtracts src from dst in place, over the smallest common length.

The length used in the operation is set to the minimum of src.len() and dst.len().

Subtracts src[0..len] from dst[0..len] in place.

This method will panic if src.len() or dst.len() is less than the supplied len parameter.

Subtracts scale * src from dst in place, over the smallest common length.

The length used in the operation is set to the minimum of src.len() and dst.len().

Subtracts scale * src[0..len] from dst[0..len] in place.

This method will panic if src.len() or dst.len() is less than the supplied len parameter.

Multiplies dst by scale in place.

Divides dst by scale in place.

This method will panic if scale is zero. The contents of the resulting error message are not defined.

Implementors§