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

> > the RV xbitmanip spec (see wiki) describes clmul as "GF(2^k) multiplication
> > with the reducing polynomial set to 2^k"
> 
> that's kinda like saying "a prime number p, but divisible by 32" -- it
> doesn't really make sense...anyway...

:)

> if you took the GF(2^k) multiplication
> algorithm and replaced the reducing polynomial with 2^k where k == XLEN,
> then, yes, that is the result of clmul, since clmul's result is truncated to
> XLEN bits. clmulh and clmulr would require a larger reducing polynomial to
> avoid truncating the product.

okaay.

> > does that sound about right? because if it is, it is basically a way
> > to "switch off" the "dividing by the reducing polynomial"
> 
> yes. that said, clmul should be its own instruction,

yes absolutely, messing about with setting the polynomial to 2^XLEN
before-hand would be a pain.

> operations (with most algorithms). clmul can and probably should be a
> combinatorial (with optional pipelining) multiply, like a Dadda multiplier
> -- much faster than remainder. In fact, we could modify our multiplier to
> also do clmul, just by masking out all carries.

oooOoo.

> it would be a ring of truncated polynomials with GF(2) coefficients. A Ring
> is any math thing that has addition, multiplication, and works kinda like
> the integers in that it has an additive identity 0, and a multiplicative
> identity 1, and iirc associativity and commutativity. Rings can be made of
> things that are totally not integers, like here, where they are truncated
> polynomials.

surprisingly, i get the Ring thing. i used it for a cryptographic algorithm
in 2003.  numbers that repeat, and are unique within their set, and
by a beautiful coincidence happen to have consistent arithmetic.

> divmodGF2 was always a polynomial divmod with GF(2) coefficients, it wasn't
> ever operating on GF(2^n) things, other than being used to produce the
> polynomial inside a GF(2^n). It is totally unaffected by changing reducing
> polynomials, since those only matter for GF(2^n) operations.

okaaay.

> > 
> > i would like to see both included, in effect, preferably without having
> > to have separate HDL?
> 
> we could do that...clmul would be really slow though.

best not then.

basically what i'm trying to advocate is to keep gfdiv and gfmod but not
name them... what did you use... a gfb- prefix?

can you update comment #0 so i have a full list? i'll then double-check
the wiki page for opcode allocations.

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