[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 #12 from Jacob Lifshay <programmerjake at gmail.com> ---
(In reply to Luke Kenneth Casson Leighton from comment #10)
> (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/

will look in the morning...I thought that was just for complex numbers tho. GF
and NTT both operate on modular integers/polynomials rather than complex
numbers, so shouldn't need a separate element for real/imag components.
> 
> 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 :)

yay :)

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

well, it took me like 2-3mo to finally let it sink in...that was when I was
trying to create an algebraic number library for use in the FP math reference
implementation a few years ago. Turns out polynomials of modular integers show
up a bunch when you want to efficiently factor polynomials with integer
coefficients.

Unfortunately, all I have at the moment is Wikipedia. Check out the elliptic
curve page too, that's where I got the terms prime/binary GF.

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