keccak: rewrite for improved performance
authorJussi Kivilinna <jussi.kivilinna@iki.fi>
Fri, 23 Oct 2015 19:30:48 +0000 (22:30 +0300)
committerJussi Kivilinna <jussi.kivilinna@iki.fi>
Wed, 28 Oct 2015 18:08:56 +0000 (20:08 +0200)
commit74184c28fbe7ff58cf57f0094ef957d94045da7d
tree3d1c33a07e749439aa010abbdfbdd6fff0364356
parent909644ef5883927262366c356eed530e55aba478
keccak: rewrite for improved performance

* cipher/Makefile.am: Add 'keccak_permute_32.h' and
'keccak_permute_64.h'.
* cipher/hash-common.h [USE_SHA3] (MD_BLOCK_MAX_BLOCKSIZE): Remove.
* cipher/keccak.c (USE_64BIT, USE_32BIT, USE_64BIT_BMI2)
(USE_64BIT_SHLD, USE_32BIT_BMI2, NEED_COMMON64, NEED_COMMON32BI)
(keccak_ops_t): New.
(KECCAK_STATE): Add 'state64' and 'state32bi' members.
(KECCAK_CONTEXT): Remove 'bctx'; add 'blocksize', 'count' and 'ops'.
(rol64, keccak_f1600_state_permute): Remove.
[NEED_COMMON64] (round_consts_64bit, keccak_extract_inplace64): New.
[NEED_COMMON32BI] (round_consts_32bit, keccak_extract_inplace32bi)
(keccak_absorb_lane32bi): New.
[USE_64BIT] (ANDN64, ROL64, keccak_f1600_state_permute64)
(keccak_absorb_lanes64, keccak_generic64_ops): New.
[USE_64BIT_SHLD] (ANDN64, ROL64, keccak_f1600_state_permute64_shld)
(keccak_absorb_lanes64_shld, keccak_shld_64_ops): New.
[USE_64BIT_BMI2] (ANDN64, ROL64, keccak_f1600_state_permute64_bmi2)
(keccak_absorb_lanes64_bmi2, keccak_bmi2_64_ops): New.
[USE_32BIT] (ANDN64, ROL64, keccak_f1600_state_permute32bi)
(keccak_absorb_lanes32bi, keccak_generic32bi_ops): New.
[USE_32BIT_BMI2] (ANDN64, ROL64, keccak_f1600_state_permute32bi_bmi2)
(pext, pdep, keccak_absorb_lane32bi_bmi2, keccak_absorb_lanes32bi_bmi2)
(keccak_extract_inplace32bi_bmi2, keccak_bmi2_32bi_ops): New.
(keccak_write): New.
(keccak_init): Adjust to KECCAK_CONTEXT changes; add implementation
selection based on HWF features.
(keccak_final): Adjust to KECCAK_CONTEXT changes; use selected 'ops'
for state manipulation.
(keccak_read): Adjust to KECCAK_CONTEXT changes.
(_gcry_digest_spec_sha3_224, _gcry_digest_spec_sha3_256)
(_gcry_digest_spec_sha3_348, _gcry_digest_spec_sha3_512): Use
'keccak_write' instead of '_gcry_md_block_write'.
* cipher/keccak_permute_32.h: New.
* cipher/keccak_permute_64.h: New.
--

Patch adds new generic 64-bit and 32-bit implementations and
optimized implementations for SHA3:
 - Generic 64-bit implementation based on 'simple' implementation
   from SUPERCOP package.
 - Generic 32-bit bit-inteleaved implementataion based on
   'simple32bi' implementation from SUPERCOP package.
 - Intel BMI2 optimized variants of 64-bit and 32-bit BI
   implementations.
 - Intel SHLD optimized variant of 64-bit implementation.

Patch also makes proper use of sponge construction to avoid
use of addition input buffer.

Below are bench-slope benchmarks for new 64-bit implementations
made on Intel Core i5-4570 (no turbo, 3.2 Ghz, gcc-4.9.2).

Before (amd64):

 SHA3-224       |      3.92 ns/B     243.2 MiB/s     12.55 c/B
 SHA3-256       |      4.15 ns/B     230.0 MiB/s     13.27 c/B
 SHA3-384       |      5.40 ns/B     176.6 MiB/s     17.29 c/B
 SHA3-512       |      7.77 ns/B     122.7 MiB/s     24.87 c/B

After (generic 64-bit, amd64), 1.10x faster):

 SHA3-224       |      3.57 ns/B     267.4 MiB/s     11.42 c/B
 SHA3-256       |      3.77 ns/B     252.8 MiB/s     12.07 c/B
 SHA3-384       |      4.91 ns/B     194.1 MiB/s     15.72 c/B
 SHA3-512       |      7.06 ns/B     135.0 MiB/s     22.61 c/B

After (Intel SHLD 64-bit, amd64, 1.13x faster):

 SHA3-224       |      3.48 ns/B     273.7 MiB/s     11.15 c/B
 SHA3-256       |      3.68 ns/B     258.9 MiB/s     11.79 c/B
 SHA3-384       |      4.80 ns/B     198.7 MiB/s     15.36 c/B
 SHA3-512       |      6.89 ns/B     138.4 MiB/s     22.05 c/B

After (Intel BMI2 64-bit, amd64, 1.45x faster):

 SHA3-224       |      2.71 ns/B     352.1 MiB/s      8.67 c/B
 SHA3-256       |      2.86 ns/B     333.2 MiB/s      9.16 c/B
 SHA3-384       |      3.72 ns/B     256.2 MiB/s     11.91 c/B
 SHA3-512       |      5.34 ns/B     178.5 MiB/s     17.10 c/B

Benchmarks of new 32-bit implementations on Intel Core i5-4570
(no turbo, 3.2 Ghz, gcc-4.9.2):

Before (win32):

 SHA3-224       |     12.05 ns/B     79.16 MiB/s     38.56 c/B
 SHA3-256       |     12.75 ns/B     74.78 MiB/s     40.82 c/B
 SHA3-384       |     16.63 ns/B     57.36 MiB/s     53.22 c/B
 SHA3-512       |     23.97 ns/B     39.79 MiB/s     76.72 c/B

After (generic 32-bit BI, win32, 1.23x to 1.29x faster):

 SHA3-224       |      9.76 ns/B     97.69 MiB/s     31.25 c/B
 SHA3-256       |     10.27 ns/B     92.82 MiB/s     32.89 c/B
 SHA3-384       |     13.22 ns/B     72.16 MiB/s     42.31 c/B
 SHA3-512       |     18.65 ns/B     51.13 MiB/s     59.70 c/B

After (Intel BMI2 32-bit BI, win32, 1.66x to 1.70x faster):

 SHA3-224       |      7.26 ns/B     131.4 MiB/s     23.23 c/B
 SHA3-256       |      7.65 ns/B     124.7 MiB/s     24.47 c/B
 SHA3-384       |      9.87 ns/B     96.67 MiB/s     31.58 c/B
 SHA3-512       |     14.05 ns/B     67.85 MiB/s     44.99 c/B

Benchmarks of new 32-bit implementation on ARM Cortex-A8
(1008 Mhz, gcc-4.9.1):

Before:

 SHA3-224       |     148.6 ns/B      6.42 MiB/s     149.8 c/B
 SHA3-256       |     157.2 ns/B      6.07 MiB/s     158.4 c/B
 SHA3-384       |     205.3 ns/B      4.65 MiB/s     206.9 c/B
 SHA3-512       |     296.3 ns/B      3.22 MiB/s     298.6 c/B

After (1.56x faster):

 SHA3-224       |     96.12 ns/B      9.92 MiB/s     96.89 c/B
 SHA3-256       |     101.5 ns/B      9.40 MiB/s     102.3 c/B
 SHA3-384       |     131.4 ns/B      7.26 MiB/s     132.5 c/B
 SHA3-512       |     188.2 ns/B      5.07 MiB/s     189.7 c/B

Signed-off-by: Jussi Kivilinna <jussi.kivilinna@iki.fi>
cipher/Makefile.am
cipher/hash-common.h
cipher/keccak.c
cipher/keccak_permute_32.h [new file with mode: 0644]
cipher/keccak_permute_64.h [new file with mode: 0644]