[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 #49 from Jacob Lifshay <programmerjake at gmail.com> ---
(In reply to Luke Kenneth Casson Leighton from comment #48)
> (In reply to Jacob Lifshay from comment #46)
> 
> > I'd guess divmod is used here for API compatibility with Rings, where a
> > remainder is actually useful, such as the Ring of integers.
> 
> rright.  ok.  yes, i have seen code which provides divmod then later
> a separate class embeds the one providing divmod into a GFPolynomial
> one.
> 
> (In reply to Jacob Lifshay from comment #47)
> 
> > clmul is polynomial multiplication where the coefficients are GF(2), not
> > GF(2^k) multiplication.
> 
> 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.

> 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, otherwise you would
usually end up doing many cycles of extra work for the polynomial division by
the reducing polynomial. multGF2 takes an iterative polynomial mul (iterative
version of clmul) and merges it with a polynomial remainder operation, making
it hard to run fast because remainders are serial 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.

> > GF(2^k) multiplication has the additional step of calculating the polynomial
> > remainder of dividing by the reducing polynomial -- essentially taking what
> > would be the top half and merging it into the bottom half, leaving the top
> > half now empty. This is similar to why the integers mod 16 have zeros
> > everywhere except the least significant hex digit, because the mod 16
> > operation removed them, leaving zeros.
> 
> ok. vaguely starting to make sense.
> 
> if the reducing polynomial is set to 2^XLEN (switched off in effect)
> does divmodGF2 and multGF2 effectively become "ring of integer" thingies?

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.

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

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