simd-rs63 0.1.2

SIMD-accelerated Reed-Solomon RS(9,6) erasure coding over GF(2^8), with no unsafe code
Documentation 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106

use crate::gf8::GF8;

#[derive(Copy, Clone)]
pub struct MulLookup {
    pub hi: [u8; 16],
    pub lo: [u8; 16],
}

pub const GF8_MUL_LOOKUP: [MulLookup; 256] = build_lookup();
pub const MUL_TABLE: [[u8; 256]; 256] = build_mul_table();
pub const INV_TABLE: [u8; 256] = build_inv_table();

/// Builds lookup tables for fast multiplication by a fixed GF(2^8) element.
/// 
/// For all n, this precomputes:
///   lo[nibble] = n * i
///   hi[nibble] = n * (i << 4)
/// 
/// where i ranges over all nibles values (256)
/// 
/// Any byte `x` can be decomposed:
///   x = high_nibble << 4 + low_nibble
/// So
///     n * x
///   = n * ((hi_nibble << 4) + lo_nibble)
///   = n *  (hi_nibble << 4) + n * lo_nibble
/// 
/// Therefore (xor is equivalent to + in GF(8)):
///   n * x = hi[byte >> 4] ^ lo[byte & 0x0f] 
const fn build_lookup() -> [MulLookup; 256] {
    let mut result_hi = [[0_u8; 16]; 256];
    let mut result_lo = [[0_u8; 16]; 256];

    let mut x: usize = 0;
    while x < 256 {
        let mut y: usize = 0;
        while y < 16 {
            let lo = GF8::new(y as u8).mul(GF8::new(x as u8));
            let hi = lo.mul(GF8::new(16));

            result_hi[x][y] = hi.value();
            result_lo[x][y] = lo.value();

            y += 1;
        }
        x += 1;
    }

    let mut result = [MulLookup { hi: [0; 16], lo: [0; 16] }; 256];
    let mut x: usize = 0;
    while x < 256 {
        result[x].hi = result_hi[x];
        result[x].lo = result_lo[x];
        x += 1;
    }

    result
}

const fn build_mul_table() -> [[u8; 256]; 256] {
    let mut t = [[0u8; 256]; 256];
    let mut i = 0usize;
    while i < 256 {
        let mut j = 0usize;
        while j < 256 {
            t[i][j] = gf_mul_scalar(i as u8, j as u8);
            j += 1;
        }
        i += 1;
    }
    t
}

const fn build_inv_table() -> [u8; 256] {
    let mut t = [0u8; 256];
    let mut i = 1usize;
    while i < 256 {
        // a^(-1) = a^254 by Fermat's little theorem (|GF(2^8)*| = 255)
        let mut result = 1u8;
        let mut base = i as u8;
        let mut exp = 254u8;
        while exp > 0 {
            if exp & 1 != 0 { result = gf_mul_scalar(result, base); }
            base = gf_mul_scalar(base, base);
            exp >>= 1;
        }
        t[i] = result;
        i += 1;
    }
    t
}

const fn gf_double(a: u8) -> u8 {
    let shifted = (a as u16) << 1;
    if a & 0x80 != 0 { (shifted ^ 0x11D) as u8 } else { shifted as u8 }
}

const fn gf_mul_scalar(mut a: u8, mut b: u8) -> u8 {
    let mut result = 0u8;
    while b > 0 {
        if b & 1 != 0 { result ^= a; }
        a = gf_double(a);
        b >>= 1;
    }
    result
}