Ottimizzazione delle prestazioni SHA256 in C

Ho bisogno di eseguire hash un grande database di valori abbastanza spesso. Pertanto, è necessaria un'implementazione veloce di un hash SHA-2. Attualmente sto usando lo SHA256.Ottimizzazione delle prestazioni SHA256 in C

L'algoritmo sha256_transform che sto utilizzando in questo momento è questa: http://bradconte.com/sha256_c (codice qui sotto)

ho profilato il mio codice e questo frammento sta prendendo esattamente il 96% di tempo per ogni hash di calcolo, rendendo questa funzione critica ai miei obiettivi

Funziona su una stringa binaria lunga 64 byte denominata data[] e restituisce il risultato in .

Chiedo una versione più veloce di questa funzione. Tieni presente che anche lievi modifiche possono influire negativamente sulla velocità.

#define uchar unsigned char 
#define uint unsigned int 

#define ROTLEFT(a,b) (((a) << (b)) | ((a) >> (32-(b)))) 
#define ROTRIGHT(a,b) (((a) >> (b)) | ((a) << (32-(b)))) 

#define CH(x,y,z) (((x) & (y))^(~(x) & (z))) 
#define MAJ(x,y,z) (((x) & (y))^((x) & (z))^((y) & (z))) 
#define EP0(x) (ROTRIGHT(x,2)^ROTRIGHT(x,13)^ROTRIGHT(x,22)) 
#define EP1(x) (ROTRIGHT(x,6)^ROTRIGHT(x,11)^ROTRIGHT(x,25)) 
#define SIG0(x) (ROTRIGHT(x,7)^ROTRIGHT(x,18)^((x) >> 3)) 
#define SIG1(x) (ROTRIGHT(x,17)^ROTRIGHT(x,19)^((x) >> 10)) 

void sha256_transform(SHA256_CTX *ctx, uchar data[]) { 
    uint a,b,c,d,e,f,g,h,i,j,t1,t2,m[64]; 

    a = ctx->state[0]; 
    b = ctx->state[1]; 
    c = ctx->state[2]; 
    d = ctx->state[3]; 
    e = ctx->state[4]; 
    f = ctx->state[5]; 
    g = ctx->state[6]; 
    h = ctx->state[7]; 

    for (i=0,j=0; i < 16; i++, j += 4) 
     m[i] = (data[j] << 24) | (data[j+1] << 16) | (data[j+2] << 8) | (data[j+3]); 

    for (; i < 64; i++) 
     m[i] = SIG1(m[i-2]) + m[i-7] + SIG0(m[i-15]) + m[i-16]; 

    for (i = 0; i < 64; ++i) { 
     t1 = h + EP1(e) + CH(e,f,g) + k[i] + m[i]; 
     t2 = EP0(a) + MAJ(a,b,c); 
     h = g; 
     g = f; 
     f = e; 
     e = d + t1; 
     d = c; 
     c = b; 
     b = a; 
     a = t1 + t2; 
    } 

    ctx->state[0] += a; 
    ctx->state[1] += b; 
    ctx->state[2] += c; 
    ctx->state[3] += d; 
    ctx->state[4] += e; 
    ctx->state[5] += f; 
    ctx->state[6] += g; 
    ctx->state[7] += h; 
}

fonte

2013-08-31 user2464424

Se si è felici di limitare il codice a x86, sembra che ci potrebbero essere opportunità per l'ottimizzazione SIMD utilizzando SSE/AVX2. –

Ci vuole il 96% delle volte non perché è scritto male, ma perché è intrinsecamente complesso. Questo è stato ottimizzato abbastanza bene, quindi se hai bisogno di dedicare meno tempo al calcolo, cerca modi per chiamarlo meno spesso. – dasblinkenlight

C'è qualcosa che il tuo codice attuale non può fare al momento perché questo sta portando la tua CPU a nuove altezze termiche? – WhozCraig

Si consiglia di checkout/profilo questo implementation of SHA256.

Utilizzato in cgminer (un noto software di mining bitcoin), è stato scritto specificatamente tenendo conto delle prestazioni. Include 4-way SIMD implementations using SSE2. Segue lo stesso approccio dell'algoritmo bradconte sha256_transform citato nella domanda. Il codice è troppo lungo per essere riprodotto qui.

Anche la licenza è abbastanza permissiva, consentendo il riutilizzo/distribuzione purché gli autori originali siano accreditati.

fonte

2013-08-31 11:00:27 TheCodeArtist

Hmm, solo curioso. Da quel codice sorgente C a cui sei collegato, dove sono le "implementazioni SIMD a 4 vie che usano SSE2" di cui stai parlando? – c00000fd

@ c00000fd Aggiornamento della risposta con collegamento diretto a [** sha256_4way.c **] (https://github.com/pshep/cgminer/blob/master/sha256_4way.c#L102). – TheCodeArtist

Scopri l'implementazione del Dr Brian Gladman - http://www.gladman.me.uk/. È circa il 15% più veloce di quello in cgminer. Non credo che si può fare molto meglio senza l'utilizzo di SSE

fonte

2014-12-31 14:05:16 jj99

Questa è l'implementazione di riferimento di Intel:

http://downloadmirror.intel.com/22357/eng/sha256_code_release_v2.zip

E il codice è descritto in:

http://www.intel.com/content/www/us/en/intelligent-systems/intel-technology/sha-256-implementations-paper.html

I ottenere circa 350 MB/s su un microprocessore Xeon basato su haswell (E5-2650 v3). È implementato in assembly e sfrutta Intel AES-NI.

fonte

2015-01-26 20:30:55 Claris

Questo non ha nulla a che fare con il set di istruzioni AES-NI. Si tratta di semplici codici operativi SSE4 o AVX. –

ottimizzazione delle prestazioni SHA256 in C ...

Ora che il Goldmont micro-architettura è stato rilasciato, esso include estensioni SHA di Intel. È possibile ottenere una velocità 5x-6x nella funzione di compressione utilizzando le istruzioni della CPU. Ad esempio, proposed code for a crypto library witnessed the following (il test si è verificato su un Celeron J3455, che viene eseguito a 1,5 GHz, ma scoppia a 2.3 GHz):

C attuazione ++

estensioni

$ ./botan speed --msec=3000 SHA-1 SHA-224 SHA-256 
    SHA-160 [base] hash 274.826 MiB/sec (824.480 MiB in 3000.009 ms) 
    SHA-224 [base] hash 92.349 MiB/sec (277.051 MiB in 3000.027 ms) 
    SHA-256 [base] hash 92.364 MiB/sec (277.094 MiB in 3000.027 ms)

Intel SHA

$ ./botan speed --msec=3000 SHA-1 SHA-224 SHA-256 
    SHA-160 [base] hash 1195.907 MiB/sec (3587.723 MiB in 3000.000 ms) 
    SHA-224 [base] hash 535.740 MiB/sec (1607.219 MiB in 3000.000 ms) 
    SHA-256 [base] hash 535.970 MiB/sec (1607.914 MiB in 3000.005 ms)

Ecco il codice per la funzione SHA256 compressa utilizzando estensioni Intel SHA con intrinsics . Si basa sul blog di Sean Gulley allo Intel® SHA Extensions e il suo codice di esempio in mitls | hacl-star | experimental.

La funzione compress sotto gestisce solo blocchi completi di 64 byte. È necessario impostare lo stato iniziale e è necessario eseguire il rilievo dell'ultimo blocco. Sembra che tu abbia quello coperto nel codice di esempio.

#include <immintrin.h> 
... 

void compress(uint32_t state[8], const uint8_t input[], size_t blocks) 
{ 
    __m128i STATE0, STATE1; 
    __m128i MSG, TMP, MASK; 
    __m128i TMSG0, TMSG1, TMSG2, TMSG3; 
    __m128i ABEF_SAVE, CDGH_SAVE; 

    // Load initial values 
    TMP = _mm_loadu_si128((__m128i*) &state[0]); 
    STATE1 = _mm_loadu_si128((__m128i*) &state[4]); 
    MASK = _mm_set_epi64x(0x0c0d0e0f08090a0bULL, 0x0405060700010203ULL); 

    TMP = _mm_shuffle_epi32(TMP, 0xB1); // CDAB 
    STATE1 = _mm_shuffle_epi32(STATE1, 0x1B); // EFGH 
    STATE0 = _mm_alignr_epi8(TMP, STATE1, 8); // ABEF 
    STATE1 = _mm_blend_epi16(STATE1, TMP, 0xF0); // CDGH 

    while (blocks) 
    { 
     // Save current hash 
     ABEF_SAVE = STATE0; 
     CDGH_SAVE = STATE1; 

     // Rounds 0-3 
     MSG = _mm_loadu_si128((const __m128i*) (input+0)); 
     TMSG0 = _mm_shuffle_epi8(MSG, MASK); 
     MSG = _mm_add_epi32(TMSG0, _mm_set_epi64x(0xE9B5DBA5B5C0FBCFULL, 0x71374491428A2F98ULL)); 
     STATE1 = _mm_sha256rnds2_epu32(STATE1, STATE0, MSG); 
     MSG = _mm_shuffle_epi32(MSG, 0x0E); 
     STATE0 = _mm_sha256rnds2_epu32(STATE0, STATE1, MSG); 

     // Rounds 4-7 
     TMSG1 = _mm_loadu_si128((const __m128i*) (input+16)); 
     TMSG1 = _mm_shuffle_epi8(TMSG1, MASK); 
     MSG = _mm_add_epi32(TMSG1, _mm_set_epi64x(0xAB1C5ED5923F82A4ULL, 0x59F111F13956C25BULL)); 
     STATE1 = _mm_sha256rnds2_epu32(STATE1, STATE0, MSG); 
     MSG = _mm_shuffle_epi32(MSG, 0x0E); 
     STATE0 = _mm_sha256rnds2_epu32(STATE0, STATE1, MSG); 
     TMSG0 = _mm_sha256msg1_epu32(TMSG0, TMSG1); 

     // Rounds 8-11 
     TMSG2 = _mm_loadu_si128((const __m128i*) (input+32)); 
     TMSG2 = _mm_shuffle_epi8(TMSG2, MASK); 
     MSG = _mm_add_epi32(TMSG2, _mm_set_epi64x(0x550C7DC3243185BEULL, 0x12835B01D807AA98ULL)); 
     STATE1 = _mm_sha256rnds2_epu32(STATE1, STATE0, MSG); 
     MSG = _mm_shuffle_epi32(MSG, 0x0E); 
     STATE0 = _mm_sha256rnds2_epu32(STATE0, STATE1, MSG); 
     TMSG1 = _mm_sha256msg1_epu32(TMSG1, TMSG2); 

     // Rounds 12-15 
     TMSG3 = _mm_loadu_si128((const __m128i*) (input+48)); 
     TMSG3 = _mm_shuffle_epi8(TMSG3, MASK); 
     MSG = _mm_add_epi32(TMSG3, _mm_set_epi64x(0xC19BF1749BDC06A7ULL, 0x80DEB1FE72BE5D74ULL)); 
     STATE1 = _mm_sha256rnds2_epu32(STATE1, STATE0, MSG); 
     TMP = _mm_alignr_epi8(TMSG3, TMSG2, 4); 
     TMSG0 = _mm_add_epi32(TMSG0, TMP); 
     TMSG0 = _mm_sha256msg2_epu32(TMSG0, TMSG3); 
     MSG = _mm_shuffle_epi32(MSG, 0x0E); 
     STATE0 = _mm_sha256rnds2_epu32(STATE0, STATE1, MSG); 
     TMSG2 = _mm_sha256msg1_epu32(TMSG2, TMSG3); 

     // Rounds 16-19 
     MSG = _mm_add_epi32(TMSG0, _mm_set_epi64x(0x240CA1CC0FC19DC6ULL, 0xEFBE4786E49B69C1ULL)); 
     STATE1 = _mm_sha256rnds2_epu32(STATE1, STATE0, MSG); 
     TMP = _mm_alignr_epi8(TMSG0, TMSG3, 4); 
     TMSG1 = _mm_add_epi32(TMSG1, TMP); 
     TMSG1 = _mm_sha256msg2_epu32(TMSG1, TMSG0); 
     MSG = _mm_shuffle_epi32(MSG, 0x0E); 
     STATE0 = _mm_sha256rnds2_epu32(STATE0, STATE1, MSG); 
     TMSG3 = _mm_sha256msg1_epu32(TMSG3, TMSG0); 

     // Rounds 20-23 
     MSG = _mm_add_epi32(TMSG1, _mm_set_epi64x(0x76F988DA5CB0A9DCULL, 0x4A7484AA2DE92C6FULL)); 
     STATE1 = _mm_sha256rnds2_epu32(STATE1, STATE0, MSG); 
     TMP = _mm_alignr_epi8(TMSG1, TMSG0, 4); 
     TMSG2 = _mm_add_epi32(TMSG2, TMP); 
     TMSG2 = _mm_sha256msg2_epu32(TMSG2, TMSG1); 
     MSG = _mm_shuffle_epi32(MSG, 0x0E); 
     STATE0 = _mm_sha256rnds2_epu32(STATE0, STATE1, MSG); 
     TMSG0 = _mm_sha256msg1_epu32(TMSG0, TMSG1); 

     // Rounds 24-27 
     MSG = _mm_add_epi32(TMSG2, _mm_set_epi64x(0xBF597FC7B00327C8ULL, 0xA831C66D983E5152ULL)); 
     STATE1 = _mm_sha256rnds2_epu32(STATE1, STATE0, MSG); 
     TMP = _mm_alignr_epi8(TMSG2, TMSG1, 4); 
     TMSG3 = _mm_add_epi32(TMSG3, TMP); 
     TMSG3 = _mm_sha256msg2_epu32(TMSG3, TMSG2); 
     MSG = _mm_shuffle_epi32(MSG, 0x0E); 
     STATE0 = _mm_sha256rnds2_epu32(STATE0, STATE1, MSG); 
     TMSG1 = _mm_sha256msg1_epu32(TMSG1, TMSG2); 

     // Rounds 28-31 
     MSG = _mm_add_epi32(TMSG3, _mm_set_epi64x(0x1429296706CA6351ULL, 0xD5A79147C6E00BF3ULL)); 
     STATE1 = _mm_sha256rnds2_epu32(STATE1, STATE0, MSG); 
     TMP = _mm_alignr_epi8(TMSG3, TMSG2, 4); 
     TMSG0 = _mm_add_epi32(TMSG0, TMP); 
     TMSG0 = _mm_sha256msg2_epu32(TMSG0, TMSG3); 
     MSG = _mm_shuffle_epi32(MSG, 0x0E); 
     STATE0 = _mm_sha256rnds2_epu32(STATE0, STATE1, MSG); 
     TMSG2 = _mm_sha256msg1_epu32(TMSG2, TMSG3); 

     // Rounds 32-35 
     MSG = _mm_add_epi32(TMSG0, _mm_set_epi64x(0x53380D134D2C6DFCULL, 0x2E1B213827B70A85ULL)); 
     STATE1 = _mm_sha256rnds2_epu32(STATE1, STATE0, MSG); 
     TMP = _mm_alignr_epi8(TMSG0, TMSG3, 4); 
     TMSG1 = _mm_add_epi32(TMSG1, TMP); 
     TMSG1 = _mm_sha256msg2_epu32(TMSG1, TMSG0); 
     MSG = _mm_shuffle_epi32(MSG, 0x0E); 
     STATE0 = _mm_sha256rnds2_epu32(STATE0, STATE1, MSG); 
     TMSG3 = _mm_sha256msg1_epu32(TMSG3, TMSG0); 

     // Rounds 36-39 
     MSG = _mm_add_epi32(TMSG1, _mm_set_epi64x(0x92722C8581C2C92EULL, 0x766A0ABB650A7354ULL)); 
     STATE1 = _mm_sha256rnds2_epu32(STATE1, STATE0, MSG); 
     TMP = _mm_alignr_epi8(TMSG1, TMSG0, 4); 
     TMSG2 = _mm_add_epi32(TMSG2, TMP); 
     TMSG2 = _mm_sha256msg2_epu32(TMSG2, TMSG1); 
     MSG = _mm_shuffle_epi32(MSG, 0x0E); 
     STATE0 = _mm_sha256rnds2_epu32(STATE0, STATE1, MSG); 
     TMSG0 = _mm_sha256msg1_epu32(TMSG0, TMSG1); 

     // Rounds 40-43 
     MSG = _mm_add_epi32(TMSG2, _mm_set_epi64x(0xC76C51A3C24B8B70ULL, 0xA81A664BA2BFE8A1ULL)); 
     STATE1 = _mm_sha256rnds2_epu32(STATE1, STATE0, MSG); 
     TMP = _mm_alignr_epi8(TMSG2, TMSG1, 4); 
     TMSG3 = _mm_add_epi32(TMSG3, TMP); 
     TMSG3 = _mm_sha256msg2_epu32(TMSG3, TMSG2); 
     MSG = _mm_shuffle_epi32(MSG, 0x0E); 
     STATE0 = _mm_sha256rnds2_epu32(STATE0, STATE1, MSG); 
     TMSG1 = _mm_sha256msg1_epu32(TMSG1, TMSG2); 

     // Rounds 44-47 
     MSG = _mm_add_epi32(TMSG3, _mm_set_epi64x(0x106AA070F40E3585ULL, 0xD6990624D192E819ULL)); 
     STATE1 = _mm_sha256rnds2_epu32(STATE1, STATE0, MSG); 
     TMP = _mm_alignr_epi8(TMSG3, TMSG2, 4); 
     TMSG0 = _mm_add_epi32(TMSG0, TMP); 
     TMSG0 = _mm_sha256msg2_epu32(TMSG0, TMSG3); 
     MSG = _mm_shuffle_epi32(MSG, 0x0E); 
     STATE0 = _mm_sha256rnds2_epu32(STATE0, STATE1, MSG); 
     TMSG2 = _mm_sha256msg1_epu32(TMSG2, TMSG3); 

     // Rounds 48-51 
     MSG = _mm_add_epi32(TMSG0, _mm_set_epi64x(0x34B0BCB52748774CULL, 0x1E376C0819A4C116ULL)); 
     STATE1 = _mm_sha256rnds2_epu32(STATE1, STATE0, MSG); 
     TMP = _mm_alignr_epi8(TMSG0, TMSG3, 4); 
     TMSG1 = _mm_add_epi32(TMSG1, TMP); 
     TMSG1 = _mm_sha256msg2_epu32(TMSG1, TMSG0); 
     MSG = _mm_shuffle_epi32(MSG, 0x0E); 
     STATE0 = _mm_sha256rnds2_epu32(STATE0, STATE1, MSG); 
     TMSG3 = _mm_sha256msg1_epu32(TMSG3, TMSG0); 

     // Rounds 52-55 
     MSG = _mm_add_epi32(TMSG1, _mm_set_epi64x(0x682E6FF35B9CCA4FULL, 0x4ED8AA4A391C0CB3ULL)); 
     STATE1 = _mm_sha256rnds2_epu32(STATE1, STATE0, MSG); 
     TMP = _mm_alignr_epi8(TMSG1, TMSG0, 4); 
     TMSG2 = _mm_add_epi32(TMSG2, TMP); 
     TMSG2 = _mm_sha256msg2_epu32(TMSG2, TMSG1); 
     MSG = _mm_shuffle_epi32(MSG, 0x0E); 
     STATE0 = _mm_sha256rnds2_epu32(STATE0, STATE1, MSG); 

     // Rounds 56-59 
     MSG = _mm_add_epi32(TMSG2, _mm_set_epi64x(0x8CC7020884C87814ULL, 0x78A5636F748F82EEULL)); 
     STATE1 = _mm_sha256rnds2_epu32(STATE1, STATE0, MSG); 
     TMP = _mm_alignr_epi8(TMSG2, TMSG1, 4); 
     TMSG3 = _mm_add_epi32(TMSG3, TMP); 
     TMSG3 = _mm_sha256msg2_epu32(TMSG3, TMSG2); 
     MSG = _mm_shuffle_epi32(MSG, 0x0E); 
     STATE0 = _mm_sha256rnds2_epu32(STATE0, STATE1, MSG); 

     // Rounds 60-63 
     MSG = _mm_add_epi32(TMSG3, _mm_set_epi64x(0xC67178F2BEF9A3F7ULL, 0xA4506CEB90BEFFFAULL)); 
     STATE1 = _mm_sha256rnds2_epu32(STATE1, STATE0, MSG); 
     MSG = _mm_shuffle_epi32(MSG, 0x0E); 
     STATE0 = _mm_sha256rnds2_epu32(STATE0, STATE1, MSG); 

     // Add values back to state 
     STATE0 = _mm_add_epi32(STATE0, ABEF_SAVE); 
     STATE1 = _mm_add_epi32(STATE1, CDGH_SAVE); 

     input += 64; 
     blocks--; 
    } 

    TMP = _mm_shuffle_epi32(STATE0, 0x1B); // FEBA 
    STATE1 = _mm_shuffle_epi32(STATE1, 0xB1); // DCHG 
    STATE0 = _mm_blend_epi16(TMP, STATE1, 0xF0); // DCBA 
    STATE1 = _mm_alignr_epi8(STATE1, TMP, 8); // ABEF 

    // Save state 
    _mm_storeu_si128((__m128i*) &state[0], STATE0); 
    _mm_storeu_si128((__m128i*) &state[4], STATE1); 
}

Potete trovare fonte di entrambe le intrinseche Intel SHA e intrinseche ARMv8 SHA a Noloader GitHub | SHA-Intrinsics. Sono file sorgente C e forniscono la funzione di compressione per SHA-1, SHA-224 e SHA-256. Le implementazioni a base intrinseca aumentano il throughput approssimativamente da 3x a 4x per SHA-1 e approssimativamente da 6x a 12x per SHA-224 e SHA-256.

fonte

2017-01-05 21:30:41 jww

Ottimizzazione delle prestazioni SHA256 in C

risposta

Problemi correlati