From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from list by lists.gnu.org with archive (Exim 4.71) id 1RPtjw-0008Ly-7q for mharc-grub-devel@gnu.org; Mon, 14 Nov 2011 05:26:12 -0500 Received: from eggs.gnu.org ([140.186.70.92]:52897) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1RPtjt-0008KL-2D for grub-devel@gnu.org; Mon, 14 Nov 2011 05:26:10 -0500 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1RPtjr-00013l-VY for grub-devel@gnu.org; Mon, 14 Nov 2011 05:26:09 -0500 Received: from mail-bw0-f41.google.com ([209.85.214.41]:45642) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1RPtjr-00013f-PX for grub-devel@gnu.org; Mon, 14 Nov 2011 05:26:07 -0500 Received: by bke17 with SMTP id 17so5529662bke.0 for ; Mon, 14 Nov 2011 02:26:07 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=message-id:date:from:user-agent:mime-version:to:subject:references :in-reply-to:x-enigmail-version:content-type; bh=UGEeRPZjYHStgwB/ylNAFnMzumDwV3jq5lGaUPgCJLg=; b=oTEmtOwCHPR6JDVcXNIkkEeX3kopiQHKDzN03Ew6jGU8IPOR/fbpBBGtBmaJOHQcq+ 00PBzi0FJPPX2cv8p3VQDCWXtNP8wiWo2vBPZHeR+okr8xTxgagstcOIbUmqAnnTNngu 4hcnhIMCWLznYVxT7UlWNXH0OFa6XBVa3roUI= Received: by 10.205.128.13 with SMTP id hc13mr10912051bkc.140.1321266366896; Mon, 14 Nov 2011 02:26:06 -0800 (PST) Received: from debian.x201.phnet (17-232.197-178.cust.bluewin.ch. [178.197.232.17]) by mx.google.com with ESMTPS id e18sm10509028bkr.15.2011.11.14.02.26.04 (version=TLSv1/SSLv3 cipher=OTHER); Mon, 14 Nov 2011 02:26:05 -0800 (PST) Message-ID: <4EC0ECBA.1080402@gmail.com> Date: Mon, 14 Nov 2011 11:26:02 +0100 From: =?UTF-8?B?VmxhZGltaXIgJ8+GLWNvZGVyL3BoY29kZXInIFNlcmJpbmVua28=?= User-Agent: Mozilla/5.0 (X11; U; Linux x86_64; en-US; rv:1.9.2.23) Gecko/20111010 Iceowl/1.0b2 Icedove/3.1.15 MIME-Version: 1.0 To: The development of GRUB 2 Subject: Re: Reed-Solomon optimised References: <4EC047B1.9010404@gmail.com> In-Reply-To: <4EC047B1.9010404@gmail.com> X-Enigmail-Version: 1.1.2 Content-Type: multipart/signed; micalg=pgp-sha512; protocol="application/pgp-signature"; boundary="------------enigC381C2B8CB31FB0DC16B1E8F" X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6 (newer, 2) X-Received-From: 209.85.214.41 X-BeenThere: grub-devel@gnu.org X-Mailman-Version: 2.1.14 Precedence: list Reply-To: The development of GNU GRUB List-Id: The development of GNU GRUB List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Mon, 14 Nov 2011 10:26:10 -0000 This is an OpenPGP/MIME signed message (RFC 2440 and 3156) --------------enigC381C2B8CB31FB0DC16B1E8F Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable On 13.11.2011 23:41, Vladimir '=CF=86-coder/phcoder' Serbinenko wrote: > 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=3DX^s > So if we know that a=3DX^s and b=3DX^t then > c=3Dab=3DX^sX^t=3DX^(s+t) > Since there are only 255 such elements for each one of them we can > precompute s s.t. X^s=3Da and we can also precompute powers of X. By > choosing s in interval 0...254 we ensure that 0<=3Ds+t<=3D508, so we ne= ed to > store only 508 elements and then we can multiply any 2 elements by firs= t > 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=3D16. 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 implici= t > with all 256 values precomputed. Correction,only CRC with irreducible polynomial is connected with GF. Other CRC are connected with other rings which aren't even integral domains. And it looks like the polynoms in the CRCs used by GRUB aren't irreducible. Sorry for this mistake. > 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. > --=20 Regards Vladimir '=CF=86-coder/phcoder' Serbinenko --------------enigC381C2B8CB31FB0DC16B1E8F Content-Type: application/pgp-signature; name="signature.asc" Content-Description: OpenPGP digital signature Content-Disposition: attachment; filename="signature.asc" -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.11 (GNU/Linux) Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org/ iF4EAREKAAYFAk7A7LoACgkQNak7dOguQglbawD7BWOZzKIggs+VShMOXg31WSdT 0oOlERyjYIJcY4PJGd4BALG3N6VPtzfQSM5RMhEGtmse165AVTMV8VWHUKZsikLN =UOUB -----END PGP SIGNATURE----- --------------enigC381C2B8CB31FB0DC16B1E8F--