[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 #10 from Luke Kenneth Casson Leighton <lkcl at lkcl.net> ---
(In reply to Jacob Lifshay from comment #8)
> 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,

nono, not predication, two ops in one instruction. look at the pseudocode
https://libre-soc.org/openpower/isa/svfparith/

the reason why i was able to do inplace FFT is the twin butterfly ops.
otherwise you need a temp reg and two instructions and obviously that
doesnt fit with Horizontal SVP64.

> > 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.

mrhhm mumble mumble we need to be 100% certain.

> > 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.

ok excellent. i knew that, but sometimes reading wikipedia talk they help
you lose track of the facts rather than give you insights :)

> 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.

eep. bad.

and also fascinating.

ok then i like the encoding.

(In reply to Jacob Lifshay from comment #9)

> > isn't it beautifully completely nuts? :)  i tracked down a simple version
> > based on long division, see bitmanip page section "gf invert", it looks
> > half decent, reminds me of the arithmetic div pipeline and of CORDIC.
> 
> yeah, that's for binary GF. prime GF is a whole other beast.

ok i get the message i need to look this up. if you know of some simple
easy to understand implementation do put it in the wiki.

give me a day or a few to read up on it, any papers/academic tutorials
you know of do let me know.

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