[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 #3 from Jacob Lifshay <programmerjake at gmail.com> ---
(In reply to Luke Kenneth Casson Leighton from comment #2)
> (In reply to Jacob Lifshay from comment #1)
> > I could be wrong, but from what I know of how Galois fields work, the degree
> > parameter is entirely derived from the reducing polynomial:
> 
> iirc some implementations have an implicit top bit removed similar
> to how 
> 
> > If this sounds good, I'll make the changes needed to have the reducing
> > polynomial as an input, and degree derived from it.
> 
> doesn't feel right.
> 
> i definitely need the full parameter space similar to FMAC, a full
> 4-operand MAC, for the SVP64 NTT to work.

then we need a gfmadd instruction.

we probably also want a gfdiv instruction, but that may be too complex.

also, gfadd is just xor iirc...so maybe we don't need that one.

> 
> (NTT, part of Reed Solomon, is the same algorithm as Discrete Fourier
> Transform just using GF arithmetic)
> 
> https://en.wikipedia.org/wiki/Talk%3ANumber-theoretic_transform
> 
> note in that page that:
> 
>      The modulus in a Number Theoretic Transfer doesn't necessarily have to
> be prime.

yup, here, I'm assuming the modulus (which ends up being the number of values
in the field (not to be confused with the reducing polynomial, which is a
different kind of modulus)) is 2^deg(reducing-polynomial).

also, iirc it's Number Theoretic *Transform* (like Fourier Transform).

> this tends to point towards using SPRs.

ok, sounds good!

what do you think of just using CTR? though, otoh if we had a dedicated SPR we
could precalculate stuff (degree, maybe some implementations want to
precalculate some tables) when the SPR was written.

In order to support GF(2^XLEN) as well as smaller fields, I think we should
pick an encoding for the reducing polynomial and degree:

def decode(v, XLEN):
    """returns the decoded coefficient list in LSB to MSB order,
        len(retval) == degree + 1"""
    v &= ((1 << XLEN) - 1) # mask to XLEN bits
    if v == 0 or v == 2: # GF(2)
        return [0, 1] # degree = 1, poly = x
    if v & 1:
        degree = floor_log2(v)
    else:
        # all reducing polynomials of degree > 1 must have the LSB set,
        # because they must be irreducible polynomials (meaning they
        # can't be factored), if the LSB was clear, then they would
        # have x as a factor. Therefore, we can reuse the LSB clear
        # to instead mean the polynomial has degree XLEN.
        degree = XLEN
        v |= 1 << XLEN
        v |= 1 # LSB must be set
    return [(v >> i) & 1 for i in range(1 + degree)]

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