Reed-Solomon optimised

[Vladimir 'φ-coder/phcoder' Serbinenko]

Hello, all. When I was implementing raidz, I thought of a more
convenient, compact and faster representation of GF(256). Using it I
could make raid6_recover more compact and Reed-Solomon more fast. Later
is very important since we have to run Reed-Solomon check (but not
necessarily much slower recovery) on every boot. I expected 8-fold
speedup but got 16-18-fold one. The idea was the following:
- In standard representation of GF(256) it's fast to add 2 numbers: it's
just a XOR.
- We also know that every non-zero number in GF(256) is represented as a
power of X: a=X^s
So if we know that a=X^s and b=X^t then
c=ab=X^sX^t=X^(s+t)
Since there are only 255 such elements for each one of them we can
precompute s s.t. X^s=a and we can also precompute powers of X. By
choosing s in interval 0...254 we ensure that 0<=s+t<=508, so we need to
store only 508 elements and then we can multiply any 2 elements by first
checking that both are non-zero (and output 0 if any of them is), one
addition and 3 table lookups (which are probably in cache given their
tiny size) which is much faster than the loop with shifts.
Same idea is usable for GF(2^n) up to n=16. Currently in the code we
have GF(256), GF(2^32), GF(2^64) and GF(2^128).
GF(2^32) and GF(2^64) are used for CRC-32/CRC-64 where they are implicit
with all 256 values precomputed.
GF(2^128) is used in cryptodisk and ZFS-crypto. In cryptodisk it's used
in LRW and XTS. In LRW thanks to the trick from LRW we need only 2
multiplications per sector. XTS does only multiplications with X which
are fast (although the version in GRUB could be optimised by shifting
uint64 and not uint8 at time but it needs care to avoid endianness
problems).
ZFS-crypto in GCM on the other hand probably has the problem of slow
GF(2^128) multiplication. It's possible to optimise it somehow using
some precomputation but it hasn't been done.
Also if you notice any other ways to speed up the boot or make critical
modules or kernel more compact, please share your ideas.

-- 
Regards
Vladimir 'φ-coder/phcoder' Serbinenko

signature.asc
Description: OpenPGP digital signature