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

we'd probably want to name it cldiv and clrem, since that way it matches with
clmul. they would be polynomial divmod, where the polynomial coefficients are
GF(2).

gfb implies GF(2^n), which depends on the reducing polynomial in order to make
sense.
> 
> can you update comment #0 so i have a full list? i'll then double-check
> the wiki page for opcode allocations.

yeah. i'll leave the gfp (prime) list un-elaborated for now.

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