[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 #84 from Jacob Lifshay <programmerjake at gmail.com> ---
(In reply to Luke Kenneth Casson Leighton from comment #83)
> (In reply to Jacob Lifshay from comment #82)
> > I added python implementations and tests for all the gfb* instructions
> 
> great. btw i altered the twin-instruction to be mul-add for RT
> and just add for RS. this matches with the DCT twin-instruction
> interestingly, and i believe is the basis of additive NTT.

imho that needs some testing to ensure it gives the same answers as other
algorithms, such as that one I found in sympy, otherwise we may need both (or
even more) kinds of twin-mul-add-subr.

> 
> about which: i am beginning to question the value of adding GF-Prime.

yeah, it may not be used much by common cryptography, but it definitely isn't
useless...assuming it's fast enough, it would definitely be useful for modular
arithmetic for small (<=64-bit) moduli, which is used in a bunch of core
algorithms for computer algebra systems (e.g. polynomial factorization by the
currently fastest known method, which is used for exact computations involving
algebraic numbers (the "real" type in SMTLIB2, the interface language used by
most of the formal proof software we've been using such as z3, yices, etc.).
algebraic numbers are also used by the simple-soft-float library I wrote.
algebraic numbers are what you get if you ask a symbolic math library to find
all roots of some arbitrary polynomial with rational coefficients, which is
pretty core functionality to solving most equations.)

> reason is: ecc25519 requires 256-bit arithmetic and we ain't addin'
> tha' so have to use bigint math anyway.
> 
> therefore if doing bigint math is there anything that can be added
> which will speed that up?

hmm, for generic bigint math, a 128 by 64-bit div and rem (used by bigint
div/rem)? openpower only provides a version where the 128-bit dividend has all
zeros in the lower half, requiring a bunch of extra instructions to
resynthesize what the hardware can already do at low additional cost.

A 128-bit to 64-bit shift like x86 shld https://www.felixcloutier.com/x86/shld
would also be nice (used by bigint shifting).

also, some instructions for getting the high half of a 64-bit * 64-bit +
128-bit muladd/mulsub (used for bigint * 64-bit number, and probably
bigint*bigint), but that would require some thought to avoid being 4-in 1-out
instructions.

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