[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 #8 from Jacob Lifshay <programmerjake at gmail.com> ---
Please don't edit old comments...I didn't notice till now that you had changed
what you wrote...

(In reply to Luke Kenneth Casson Leighton from comment #6)
> (In reply to Jacob Lifshay from comment #3)
>  
> > then we need a gfmadd instruction.
> 
> and a twin version.

If you mean something that can use twin predication, I'm not sure how we'd do
that, since basically all these ops have multiple inputs, iirc thereby using up
the space in the SVP64 encoding that could have been used for twin predication.
> 
> > we probably also want a gfdiv instruction, but that may be too complex.
> 
> i knoow, aren't they fun?  best way is inverse then mul.
> galileo something inverse.
> 
> https://libre-soc.org/openpower/isa/svfparith/
> 
> twin butterfly.  
> 
> > also, gfadd is just xor iirc...so maybe we don't need that one.
> 
> yes because on exceeding polynomial you need a cleanup.
> as long as both inputs are below polynomial the cleanup
> is i believe a simple check.

I'd just expect the inputs to nearly always be in-range (100% of the time in
>99% of programs), meaning that xor is completely sufficient. I don't think
this justifies a separate instruction.

If we need an instruction to change some input to fit in range (cleanup), we
can just do gfmadd with both multiplicands be constant zeros (RA|0), which the
decoder can easily decode specially to skip the multiplication if we really
need the extra speed.

> > > 
> > > (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).
> 
> do they mean e.g. Gf 2^5 

yes, when you have any degree 5 reducing polynomial. If you have a polynomial
that is some other degree, such as 6, then the field described is some instance
of GF(2^6) for degree 6, GF(2^3) for degree 3, etc.

> > what do you think of just using CTR?
> 
> see sv.bc for how much functionality would be lost.
> sv.bc is stunningly powerful, a "simple" bc gets something
> mad like 128 additional options half of which rely on CTR.

yeah, I wasn't thinking that through. CTR is too important for looping.
> 
> 
> >         # all reducing polynomials of degree > 1 must have the LSB set,
> >         # because they must be irreducible polynomials (meaning they
> >         # can't be factored),
> 
> 
> take a look again at the wikipedia NTT talk page apparently nonprime
> polynomials are actually useful, and LSB=0 is nonprime.

as you already probably figured out, the non-prime part is the size of the
field (so for GF(27), the field has size 27), not the reducing polynomial.

AFAIK the reducing polynomial always 
> 
> oh right GF 2^5 i.e.the degree.
> 
> can you doublexheck to see if there are any circumstances where
> a polyynomial with LSB=0 is useful or not?

there's one, when you're using GF(p) for some prime p. in this case, the only
applicable one is GF(2), which I already have the special case for.

The polynomial must always be irreducible (the polynomial equivalent of being a
prime number), otherwise you don't get a Galois Field (you get a Ring instead),
which means that the LSB must be non-zero for degree > 2 polynomials, otherwise
it would be divisible by the polynomial x^1+0, which would mean that your
polynomial wasn't irreducible after all, making your nice Galois Field no
longer a Field, essentially breaking the math. Think of it as like dividing by
zero.

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