[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 #9 from Jacob Lifshay <programmerjake at gmail.com> ---
(In reply to Luke Kenneth Casson Leighton from comment #7)
> (In reply to Jacob Lifshay from comment #4)
> 
> > we probably won't want division or inverse cuz iirc those are crazy complex.

For GF(p) for prime p (we can assume that p can get quite large, close to
2^64), a modular inversion essentially a loop over integer divmod and
multiplication, divmod itself is already kinda a loop. Then we get the outer
loops from SV. We're going to get a like 5 or 6-deep loop all running from 1
instruction, which imho is kinda overboard. That sounds like CISC, but even
more so -- super CISC. Next we'll be adding a javascript parser as 1
instruction...:P
> 
> 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.

> the ultimate goal here, the big test, is to do NTT in around 11 instructions
> similar to DCT. the entire main NTT triple loop with SV REMAP, on top of
> the appropriate twin butterfly ops.

well, iirc NTT is only gfmadd, no gfdiv for prime GF needed there.
> 
> (In reply to Jacob Lifshay from comment #5)
> 
> > modular inverse algorithm:
> > https://en.m.wikipedia.org/wiki/Extended_Euclidean_algorithm#Modular_integers
> 
> euclidean not galileo :)
> 
> see gf invert section you will likely find it is that one.
> 
> div can then be invert followed by mul.  no accuracy is lost because
> both are ring fields. when prime polynomial.

yeah, for binary GF, gfinv or gfdiv is totally feasible, if a bit slow.

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