[Libre-soc-bugs] [Bug 782] add galois field bitmanip instructions

[bugzilla-daemon at libre-soc.org]

https://bugs.libre-soc.org/show_bug.cgi?id=782

--- Comment #33 from Jacob Lifshay <programmerjake at gmail.com> ---
I found a paper that references a VLSI-optimized version of gfinv:
https://scholar.archive.org/work/ktlygagf6jhslhx42gpuwwzc44/access/wayback/http://acsel-lab.com/arithmetic/arith18/papers/ARITH18_Kobayashi.pdf
(Algorithm 3, from [7])

GF(2^m) inversion.
G(x) is the reducing polynomial. m is the degree of G(x).
A(x) is the input polynomial.
r[m] is the mth coefficient of R(x).
s[m] is the mth coefficient of S(x).

Algorithm 3:
S(x) := G(x); V(x) := 0;
R(x) := A(x); U(x) := 1;
δ := 0;
for i = 1 to 2*m do
    if r[m] = 0 then
        R(x) := x × R(x); # shift left by 1
        U(x) := x × U(x); # shift left by 1
        δ = δ + 1; # integer increment
    else
        if s[m] = 1 then
            S(x) := S(x) − R(x); # polynomial subtraction aka. xor
            V(x) := V(x) − U(x); # polynomial subtraction aka. xor
        end if
        S(x) := x × S(x); # shift left by 1
        if δ = 0 then
            {R(x) := S(x), S(x) := R(x)}; # swap S(x) and R(x)
            # shift V(x) left by one, then swap V(x) and U(x)
            {U(x) := x × V(x), V(x) := U(x)};
            δ := 1;
        else
            U(x) := U/x; # shift right 1
            δ := δ − 1;
        end if
    end if
end for
output U(x) as the result.
(U(x) = A^−1(x))

-- 
You are receiving this mail because:
You are on the CC list for the bug.