SHA256 implementations based on Intel SHA Extensions #13386

sipa · 2018-06-03T23:32:45Z

Based on #13191.

This adds SHA256 implementations that use Intel's SHA Extension instructions (using intrinsics). This needs GCC 4.9 or Clang 3.4.

In addition to #13191, two extra implementations are provided:

(a) A variable-length SHA256 implementation using SHA extensions.
(b) A 2-way 64-byte input double-SHA256 implementation using SHA extensions.

Benchmarks for 9001-element Merkle tree root computation on an AMD Ryzen 1800X system:

Using generic C++ code (pre-Add SSE4 optimized SHA256 #10821): 6.1ms
Using SSE4 (master, Add SSE4 optimized SHA256 #10821): 4.6ms
Using 4-way SSE4 specialized for 64-byte inputs (Specialized double-SHA256 with 64 byte inputs with SSE4.1 and AVX2 #13191): 2.8ms
Using 8-way AVX2 specialized for 64-byte inputs (Specialized double-SHA256 with 64 byte inputs with SSE4.1 and AVX2 #13191): 2.1ms
Using 2-way SHA-NI specialized for 64-byte inputs (this PR): 0.56ms

Benchmarks for 32-byte SHA256 on the same system:

Using SSE4 (master, Add SSE4 optimized SHA256 #10821): 190ns
Using SHA-NI (this PR): 53ns

Benchmarks for 1000000-byte SHA256 on the same system:

Using SSE4 (master, Add SSE4 optimized SHA256 #10821): 2.5ms
Using SHA-NI (this PR): 0.51ms

kallewoof · 2018-06-04T00:19:39Z

src/crypto/sha256.cpp

What about

ret = "sse4"; #if defined(ENABLE_SSE41) && !defined(BUILD_BITCOIN_INTERNAL) TransformD64_4way = sha256d64_sse41::Transform_4way; ret += ",sse41"; #endif }

?

ghost · 2018-06-04T09:08:40Z

@sipa

Great works as usual!

I just came cross this thread

https://github.com/armfazh/flo-shani-aesni/blob/master/README.md

I hope you will have time to look at what they did!

DrahtBot · 2018-06-04T12:41:57Z

Needs rebase

promag · 2018-06-04T12:45:37Z

Concept ACK, nice numbers.

sipa · 2018-06-04T16:54:25Z

Rebased.

@Kick1986 Nice, I'll have a look.

DrahtBot · 2018-06-05T00:49:29Z

Note to reviewers: This pull request conflicts with the following ones:

Convert the 1-way SSE4 SHA256 code from asm to intrinsics #13442 (Convert the 1-way SSE4 SHA256 code from asm to intrinsics by sipa)
Add POWER8 ASM for 4-way SHA256 #13203 (Add POWER8 ASM for 4-way SHA256 by TheBlueMatt)

If you consider this pull request important, please also help to review the conflicting pull requests. Ideally, start with the one that should be merged first.

Empact · 2018-06-05T09:34:11Z

For clang version, looks like they were added in 3.4, but never noted in the release notes.
Source: went from commit date[1] to release date[2] to file in release version[3].
Did not check for every intrinsic used.
[1] llvm-mirror/clang@b83f5a7#diff-c4f203a0f202bf56c364a657b0aecae9
[2] http://releases.llvm.org/
[3] https://github.com/llvm-mirror/clang/blob/release_34/lib/Headers/shaintrin.h

theuni · 2018-06-05T20:33:45Z

src/crypto/sha256_shani.cpp

I think these could be _mm_load_si128 if s[] was alignas(16).

theuni · 2018-06-05T20:49:02Z

src/Makefile.am

These are starting to get out of hand. I think we should take @TheBlueMatt's suggestion and treat LIBBITCOIN_CRYPTO as a collection of these helpers. That way we can just add $(LIBBITCOIN_CRYPTO) everywhere, and that will pull in the cpu-specific libs as well. Something like:

... LIBBITCOIN_CRYPTO=crypto/libbitcoin_crypto.a LIBBITCOIN_CRYPTO_AVX2=crypto/libbitcoin_crypto_avx2.a LIBBITCOIN_CRYPTO_SHANI=crypto/libbitcoin_crypto_shani.a LIBBITCOIN_CRYPTO+=$(LIBBITCOIN_CRYPTO_AVX2) LIBBITCOIN_CRYPTO+=$(LIBBITCOIN_CRYPTO_SHANI) ...

Then the cpu-specific ones can be dropped from the LDADDs all over the place. I'm happy to do up a patch on top of this if you'd like.

@theuni Actually, feel like PRing that as a separate PR, before this one goes in? Then @TheBlueMatt and I can both rebase ours on top of yours and not conflict with each other.

theuni · 2018-06-05T21:03:59Z

concept ACK.

I noticed while testing #13400 that I added a bug, but bitcoind started up fine anyway, due to missing sanity checks for the double/4way/8way hashes. Mind adding those?

DesWurstes · 2018-06-07T04:12:06Z

src/crypto/sha256_shani.cpp

I believe including immintrin.h is enough for both platforms. x86intrin includes immintrin.h, and immintrin.h includes everything that is needed: https://github.com/gcc-mirror/gcc/blob/master/gcc/config/i386/immintrin.h

EDIT: Tested on Linux GCC and Clang, including immintrin.h is enough for all platforms.

Thanks, fixed.

@sipa

f68049d crypto: cleanup sha256 build (Cory Fields) Pull request description: Requested by @sipa in #13386. Rather than appending all possible cpu variants to all targets, create a convenience variable that encompasses all. Tree-SHA512: 8e9ab2185515672b79bb7925afa4f3fbfe921bfcbe61456833d15457de4feba95290de17514344ce42ee81cc38b252476cd0c29432ac48c737c2225ed515a4bd

sipa · 2018-06-11T16:52:01Z

Rebased.

DrahtBot · 2018-06-12T19:00:32Z

Needs rebase

sipa · 2018-06-12T19:23:09Z

Rebased.

theuni · 2018-06-13T20:48:03Z

src/crypto/sha256_shani.cpp

Linter is yelling about include style here.

DrahtBot · 2018-06-24T14:19:29Z

Needs rebase

sipa · 2018-06-24T17:56:51Z

Rebased after #13471 merge.

Also split up the CPU feature detection logic change into its own commit.

I noticed while testing #13400 that I added a bug, but bitcoind started up fine anyway, due to missing sanity checks for the double/4way/8way hashes. Mind adding those?

That was addressed in #13438.

theuni · 2018-06-25T19:51:15Z


utACK otherwise.

theuni · 2018-06-26T18:56:35Z

Thanks! utACK 66b2cf1.

jb55 · 2018-06-27T03:32:05Z

Not sure what compelled me to do this, and it's probably overkill... but...

Tested ACK 66b2cf1 with 100k rounds of quickcheck at various optimization levels, but only with the non-two way transform for now.

DesWurstes · 2018-06-27T11:54:03Z

Just a nit from older pull requests: Now that it has a custom CPUID function

bitcoin/src/crypto/sha256.cpp

Lines 534 to 538 in d96bdd7

    
           // We can't use cpuid.h's __get_cpuid as it does not support subleafs. 
        
           void inline cpuid(uint32_t leaf, uint32_t subleaf, uint32_t& a, uint32_t& b, uint32_t& c, uint32_t& d) 
        
           { 
        
             __asm__ ("cpuid" : "=a"(a), "=b"(b), "=c"(c), "=d"(d) : "0"(leaf), "2"(subleaf)); 
        
           }

including <cpuid.h> is not necessary now:

bitcoin/src/crypto/sha256.cpp

Lines 12 to 16 in d96bdd7

    
           #if defined(__x86_64__) || defined(__amd64__) 
        
           #if defined(USE_ASM) 
        
           #include <cpuid.h> 
        
           namespace sha256_sse4 
        
           {

Thank you for your awesome contributions!

gmaxwell · 2018-07-07T08:06:22Z

ACK

laanwj · 2018-07-09T19:10:21Z

utACK 66b2cf1
tested that build passes on FreeBSD+OpenBSD

66b2cf1 Use immintrin.h everywhere for intrinsics (Pieter Wuille) 4c935e2 Add SHA256 implementation using using Intel SHA intrinsics (Pieter Wuille) 268400d [Refactor] CPU feature detection logic for SHA256 (Pieter Wuille) Pull request description: Based on #13191. This adds SHA256 implementations that use Intel's SHA Extension instructions (using intrinsics). This needs GCC 4.9 or Clang 3.4. In addition to #13191, two extra implementations are provided: * (a) A variable-length SHA256 implementation using SHA extensions. * (b) A 2-way 64-byte input double-SHA256 implementation using SHA extensions. Benchmarks for 9001-element Merkle tree root computation on an AMD Ryzen 1800X system: * Using generic C++ code (pre-#10821): 6.1ms * Using SSE4 (master, #10821): 4.6ms * Using 4-way SSE4 specialized for 64-byte inputs (#13191): 2.8ms * Using 8-way AVX2 specialized for 64-byte inputs (#13191): 2.1ms * Using 2-way SHA-NI specialized for 64-byte inputs (this PR): 0.56ms Benchmarks for 32-byte SHA256 on the same system: * Using SSE4 (master, #10821): 190ns * Using SHA-NI (this PR): 53ns Benchmarks for 1000000-byte SHA256 on the same system: * Using SSE4 (master, #10821): 2.5ms * Using SHA-NI (this PR): 0.51ms Tree-SHA512: 2b319e33b22579f815d91f9daf7994a5e1e799c4f73c13e15070dd54ba71f3f6438ccf77ae9cbd1ce76f972d9cbeb5f0edfea3d86f101bbc1055db70e42743b7

@sipa

f68049d crypto: cleanup sha256 build (Cory Fields) Pull request description: Requested by @sipa in bitcoin#13386. Rather than appending all possible cpu variants to all targets, create a convenience variable that encompasses all. Tree-SHA512: 8e9ab2185515672b79bb7925afa4f3fbfe921bfcbe61456833d15457de4feba95290de17514344ce42ee81cc38b252476cd0c29432ac48c737c2225ed515a4bd

…ions 66b2cf1 Use immintrin.h everywhere for intrinsics (Pieter Wuille) 4c935e2 Add SHA256 implementation using using Intel SHA intrinsics (Pieter Wuille) 268400d [Refactor] CPU feature detection logic for SHA256 (Pieter Wuille) Pull request description: Based on bitcoin#13191. This adds SHA256 implementations that use Intel's SHA Extension instructions (using intrinsics). This needs GCC 4.9 or Clang 3.4. In addition to bitcoin#13191, two extra implementations are provided: * (a) A variable-length SHA256 implementation using SHA extensions. * (b) A 2-way 64-byte input double-SHA256 implementation using SHA extensions. Benchmarks for 9001-element Merkle tree root computation on an AMD Ryzen 1800X system: * Using generic C++ code (pre-bitcoin#10821): 6.1ms * Using SSE4 (master, bitcoin#10821): 4.6ms * Using 4-way SSE4 specialized for 64-byte inputs (bitcoin#13191): 2.8ms * Using 8-way AVX2 specialized for 64-byte inputs (bitcoin#13191): 2.1ms * Using 2-way SHA-NI specialized for 64-byte inputs (this PR): 0.56ms Benchmarks for 32-byte SHA256 on the same system: * Using SSE4 (master, bitcoin#10821): 190ns * Using SHA-NI (this PR): 53ns Benchmarks for 1000000-byte SHA256 on the same system: * Using SSE4 (master, bitcoin#10821): 2.5ms * Using SHA-NI (this PR): 0.51ms Tree-SHA512: 2b319e33b22579f815d91f9daf7994a5e1e799c4f73c13e15070dd54ba71f3f6438ccf77ae9cbd1ce76f972d9cbeb5f0edfea3d86f101bbc1055db70e42743b7

sipa mentioned this pull request Jun 3, 2018

Specialized double-SHA256 with 64 byte inputs with SSE4.1 and AVX2 #13191

Merged

kallewoof reviewed Jun 4, 2018

View reviewed changes

sipa force-pushed the 201806_shani branch from 1773155 to ac43c37 Compare June 4, 2018 00:35

fanquake added the Validation label Jun 4, 2018

sipa force-pushed the 201806_shani branch from ac43c37 to bb80ab2 Compare June 4, 2018 16:54

DrahtBot mentioned this pull request Jun 5, 2018

Enable double-SHA256-for-64-byte code on 32-bit x86 #13393

Merged

theuni reviewed Jun 5, 2018

View reviewed changes

src/crypto/sha256_shani.cpp Outdated

Copy link

Member

theuni Jun 5, 2018

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I think these could be _mm_load_si128 if s[] was alignas(16).

theuni reviewed Jun 5, 2018

View reviewed changes

theuni mentioned this pull request Jun 6, 2018

crypto: cleanup sha256 build #13408

Merged

DesWurstes reviewed Jun 7, 2018

View reviewed changes

DrahtBot added the Needs rebase label Jun 11, 2018

sipa force-pushed the 201806_shani branch from bb80ab2 to a506e19 Compare June 11, 2018 16:51

DrahtBot removed the Needs rebase label Jun 11, 2018

DrahtBot added the Needs rebase label Jun 12, 2018

sipa force-pushed the 201806_shani branch from 85662f5 to b318acd Compare June 12, 2018 19:23

DrahtBot removed the Needs rebase label Jun 12, 2018

theuni reviewed Jun 13, 2018

View reviewed changes

src/crypto/sha256_shani.cpp Outdated

Copy link

Member

theuni Jun 13, 2018

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Linter is yelling about include style here.

sipa force-pushed the 201806_shani branch from b318acd to ff1ef63 Compare June 14, 2018 07:15

DrahtBot mentioned this pull request Jun 14, 2018

For AVX2 code, also check for AVX, XSAVE, and OS support #13471

Merged

This was referenced Jun 15, 2018

Make sure LC_ALL=C is set in all shell scripts #13454

Merged

rpc: have verifytxoutproof check the number of txns in proof structure #13452

Merged

[WIP] support new multisig template in wallet for Solver, signing, and signature combining #13449

Closed

DrahtBot added the Needs rebase label Jun 24, 2018

[Refactor] CPU feature detection logic for SHA256

268400d

sipa force-pushed the 201806_shani branch from ff1ef63 to 260b0fb Compare June 24, 2018 17:54

DrahtBot removed the Needs rebase label Jun 24, 2018

sipa added 2 commits June 26, 2018 10:11

Add SHA256 implementation using using Intel SHA intrinsics

4c935e2

Use immintrin.h everywhere for intrinsics

66b2cf1

sipa force-pushed the 201806_shani branch from 260b0fb to 66b2cf1 Compare June 26, 2018 17:15

laanwj merged commit 66b2cf1 into bitcoin:master Jul 9, 2018

Bushstar mentioned this pull request Jul 13, 2018

commits from bitcoin/master FeatherCoin/Feathercoin#354

Merged

sipa mentioned this pull request Aug 8, 2018

Assembly optimisations are compiled even with --disable-asm #13759

Closed

sickpig mentioned this pull request Oct 25, 2019

[port] Specialized double-SHA256 with 64 byte inputs with SSE4.1 and AVX2 BitcoinUnlimited/BitcoinUnlimited#1999

Merged

bitcoin locked as resolved and limited conversation to collaborators Sep 8, 2021

SHA256 implementations based on Intel SHA Extensions #13386

SHA256 implementations based on Intel SHA Extensions #13386

Uh oh!

Conversation

sipa commented Jun 3, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

kallewoof Jun 4, 2018

Choose a reason for hiding this comment

Uh oh!

sipa Jun 4, 2018

Choose a reason for hiding this comment

Uh oh!

ghost commented Jun 4, 2018 • edited by ghost Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

DrahtBot commented Jun 4, 2018

Uh oh!

promag commented Jun 4, 2018

Uh oh!

sipa commented Jun 4, 2018

Uh oh!

DrahtBot commented Jun 5, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Empact commented Jun 5, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

theuni Jun 5, 2018

Choose a reason for hiding this comment

Uh oh!

theuni Jun 5, 2018

Choose a reason for hiding this comment

Uh oh!

sipa Jun 6, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

theuni commented Jun 5, 2018

Uh oh!

DesWurstes Jun 7, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

sipa Jun 11, 2018

Choose a reason for hiding this comment

Uh oh!

sipa commented Jun 11, 2018

Uh oh!

DrahtBot commented Jun 12, 2018

Uh oh!

sipa commented Jun 12, 2018

Uh oh!

theuni Jun 13, 2018

Choose a reason for hiding this comment

Uh oh!

DrahtBot commented Jun 24, 2018

Uh oh!

sipa commented Jun 24, 2018

Uh oh!

theuni commented Jun 25, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

theuni commented Jun 26, 2018

Uh oh!

jb55 commented Jun 27, 2018

Uh oh!

DesWurstes commented Jun 27, 2018

Uh oh!

gmaxwell commented Jul 7, 2018

Uh oh!

laanwj commented Jul 9, 2018

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

sipa commented Jun 3, 2018 •

edited

Loading

ghost commented Jun 4, 2018 •

edited by ghost

Loading

DrahtBot commented Jun 5, 2018 •

edited

Loading

Empact commented Jun 5, 2018 •

edited

Loading

sipa Jun 6, 2018 •

edited

Loading

DesWurstes Jun 7, 2018 •

edited

Loading

theuni commented Jun 25, 2018 •

edited

Loading