Line data Source code
1 : #ifndef HEADER_fd_src_ballet_sha256_fd_sha256_h
2 : #define HEADER_fd_src_ballet_sha256_fd_sha256_h
3 :
4 : /* fd_sha256 provides APIs for SHA-256 hashing of messages. */
5 :
6 : #include "../fd_ballet_base.h"
7 :
8 : /* FD_SHA256_{ALIGN,FOOTPRINT} describe the alignment and footprint needed
9 : for a memory region to hold a fd_sha256_t. ALIGN is a positive
10 : integer power of 2. FOOTPRINT is a multiple of align. ALIGN is
11 : recommended to be at least double cache line to mitigate various
12 : kinds of false sharing. These are provided to facilitate compile
13 : time declarations. */
14 :
15 1092321 : #define FD_SHA256_ALIGN (128UL)
16 546150 : #define FD_SHA256_FOOTPRINT (128UL)
17 :
18 : /* FD_SHA256_{LG_HASH_SZ,HASH_SZ} describe the size of a SHA256 hash
19 : in bytes. HASH_SZ==2^LG_HASH_SZ==32. */
20 :
21 : #define FD_SHA256_LG_HASH_SZ (5)
22 543540 : #define FD_SHA256_HASH_SZ (32UL) /* == 2^FD_SHA256_LG_HASH_SZ, explicit to workaround compiler limitations */
23 :
24 : /* FD_SHA256_{LG_BLOCK_SZ,BLOCK_SZ} describe the size of a SHA256
25 : hash block in byte. BLOCK_SZ==2^LG_BLOCK_SZ==64. */
26 :
27 68781160 : #define FD_SHA256_LG_BLOCK_SZ (6)
28 158565662 : #define FD_SHA256_BLOCK_SZ (64UL) /* == 2^FD_SHA256_LG_BLOCK_SZ, explicit to workaround compiler limitations */
29 :
30 : /* A fd_sha256_t should be treated as an opaque handle of a sha256
31 : calculation state. (It technically isn't here facilitate compile
32 : time declarations of fd_sha256_t memory.) */
33 :
34 546147 : #define FD_SHA256_MAGIC (0xF17EDA2CE54A2560) /* FIREDANCE SHA256 V0 */
35 :
36 : /* FD_SHA256_PRIVATE_{LG_BUF_MAX,BUF_MAX} describe the size of the
37 : internal buffer used by the sha256 computation object. This is for
38 : internal use only. BUF_MAX==2^LG_BUF_MAX==2*FD_SHA256_HASH_SZ==64. */
39 :
40 68781160 : #define FD_SHA256_PRIVATE_LG_BUF_MAX FD_SHA256_LG_BLOCK_SZ
41 120548102 : #define FD_SHA256_PRIVATE_BUF_MAX FD_SHA256_BLOCK_SZ
42 :
43 : struct __attribute__((aligned(FD_SHA256_ALIGN))) fd_sha256_private {
44 :
45 : /* This point is 128-byte aligned */
46 :
47 : uchar buf[ FD_SHA256_PRIVATE_BUF_MAX ];
48 :
49 : /* This point is 64-byte aligned */
50 :
51 : uint state[ FD_SHA256_HASH_SZ / sizeof(uint) ];
52 :
53 : /* This point is 32-byte aligned */
54 :
55 : ulong magic; /* ==FD_SHA256_MAGIC */
56 : ulong buf_used; /* Number of buffered bytes, in [0,FD_SHA256_BUF_MAX) */
57 : ulong bit_cnt; /* How many bits have been appended total */
58 :
59 : /* Padding to 128-byte here */
60 : };
61 :
62 : typedef struct fd_sha256_private fd_sha256_t;
63 :
64 : FD_PROTOTYPES_BEGIN
65 :
66 : /* fd_sha256_{align,footprint,new,join,leave,delete} usage is identical to
67 : that of their fd_sha512 counterparts. See ../sha512/fd_sha512.h */
68 :
69 : FD_FN_CONST ulong
70 : fd_sha256_align( void );
71 :
72 : FD_FN_CONST ulong
73 : fd_sha256_footprint( void );
74 :
75 : void *
76 : fd_sha256_new( void * shmem );
77 :
78 : fd_sha256_t *
79 : fd_sha256_join( void * shsha );
80 :
81 : void *
82 : fd_sha256_leave( fd_sha256_t * sha );
83 :
84 : void *
85 : fd_sha256_delete( void * shsha );
86 :
87 : /* fd_sha256_init starts a sha256 calculation. sha is assumed to be a
88 : current local join to a sha256 calculation state with no other
89 : concurrent operation that would modify the state while this is
90 : executing. Any preexisting state for an in-progress or recently
91 : completed calculation will be discarded. Returns sha (on return, sha
92 : will have the state of a new in-progress calculation). */
93 :
94 : fd_sha256_t *
95 : fd_sha256_init( fd_sha256_t * sha );
96 :
97 : /* fd_sha256_append adds sz bytes locally pointed to by data an
98 : in-progress sha256 calculation. sha, data and sz are assumed to be
99 : valid (i.e. sha is a current local join to a sha256 calculation state
100 : with no other concurrent operations that would modify the state while
101 : this is executing, data points to the first of the sz bytes and will
102 : be unmodified while this is running with no interest retained after
103 : return ... data==NULL is fine if sz==0). Returns sha (on return, sha
104 : will have the updated state of the in-progress calculation).
105 :
106 : It does not matter how the user group data bytes for a sha256
107 : calculation; the final hash will be identical. It is preferable for
108 : performance to try to append as many bytes as possible as a time
109 : though. It is also preferable for performance if sz is a multiple of
110 : 64 for all but the last append (it is also preferable if sz is less
111 : than 56 for the last append). */
112 :
113 : fd_sha256_t *
114 : fd_sha256_append( fd_sha256_t * sha,
115 : void const * data,
116 : ulong sz );
117 :
118 : /* fd_sha256_fini finishes a sha256 calculation. sha and hash are
119 : assumed to be valid (i.e. sha is a local join to a sha256 calculation
120 : state that has an in-progress calculation with no other concurrent
121 : operations that would modify the state while this is executing and
122 : hash points to the first byte of a 32-byte memory region where the
123 : result of the calculation should be stored). Returns hash (on
124 : return, there will be no calculation in-progress on sha and 32-byte
125 : buffer pointed to by hash will be populated with the calculation
126 : result). */
127 : /* FIXME: THIS SHOULD PROBABLY RETURN A FD_SHA256_T */
128 :
129 : void *
130 : fd_sha256_fini( fd_sha256_t * sha,
131 : void * hash );
132 :
133 : /* fd_sha256_hash is a streamlined implementation of:
134 :
135 : fd_sha256_t sha[1];
136 : return fd_sha256_fini( fd_sha256_append( fd_sha256_init( sha ), data, sz ), hash )
137 :
138 : This can be faster for small messages because it can eliminate
139 : function call overheads, branches, copies and data marshalling under
140 : the hood (things like binary Merkle tree construction were designed
141 : do lots of such operations). */
142 : /* FIXME: ADD NEW/JOIN/LEAVE/DELETE TO DOCUMENTATION */
143 : /* FIXME: PROBABLY SHOULD HAVE AN ABORT API */
144 : /* FIXME: UPDATE OTHER HASH FUNCTIONS SIMILARLY */
145 :
146 : void *
147 : fd_sha256_hash( void const * data,
148 : ulong sz,
149 : void * hash );
150 :
151 : /* fd_sha256_hash_32_repeated hashes the 32 bytes pointed to by data,
152 : then hashes the hash, and repeats, doing a total of cnt hashes. It
153 : is a streamlined version of:
154 :
155 : uchar temp[32];
156 : memcpy( temp, data, 32UL );
157 : for( ulong i=0UL; i<cnt; i++ ) fd_sha256_hash( temp, 32UL, temp );
158 : memcpy( hash, temp, 32UL );
159 : return hash;
160 :
161 : This eliminates function call overhead and data marshalling. cnt==0
162 : is okay, in which case this just copies data to hash. Always returns
163 : hash. data and hash must be valid, non-NULL pointers, even when
164 : cnt==0. */
165 : void *
166 : fd_sha256_hash_32_repeated( void const * data,
167 : void * hash,
168 : ulong cnt );
169 :
170 : /* fd_sha256_hash_32_repeated_batch is a SIMD-parallel version of the
171 : above. Currently faster on AVX-512 and armv8 (NEON, FEAT_SHA2).
172 : The latency of any individual computation is worse
173 : than fd_sha256_hash_32_repeated, possibly by ~8x depending on arch.
174 : But this version has higher throughput at batch widths of
175 : fd_sha256_simd_lane_min and higher (assuming no pipeline bubbles in
176 : cnt). lane_cnt must be in [0,simd_lane_max], otherwise the process
177 : is aborted. */
178 :
179 : void
180 : fd_sha256_hash_32_repeated_batch( void const * hashes_in, /* 32 byte stride */
181 : void * hashes_out, /* 32 byte stride */
182 : ulong hash_cnt, /* iterations to run across all lanes */
183 : ulong lane_cnt ); /* number of hashes/lanes */
184 :
185 : /* fd_sha256_simd_lane_min returns the threshold at which SIMD
186 : parallelism gains higher throughput than the scalar path, or
187 : ULONG_MAX if there is no fast SIMD option. */
188 :
189 : FD_FN_CONST ulong
190 : fd_sha256_simd_lane_min( void );
191 :
192 : /* fd_sha256_simd_lane_max returns the max number of hash calculations
193 : that can be done in parallel using SIMD. */
194 :
195 : FD_FN_CONST ulong
196 : fd_sha256_simd_lane_max( void );
197 :
198 : /* fd_sha256_simd_iter_cost_q8 returns the cost of one iteration of
199 : fd_sha256_hash_32_repeated_batch in units of one iteration of
200 : fd_sha256_hash_32_repeated, as a fixed point number with 8 fractional
201 : bits (256 is 1.0x). Lets a caller size a batched call to a wall
202 : clock budget. Returns 256 if there is no fast SIMD option. */
203 :
204 : FD_FN_CONST ulong
205 : fd_sha256_simd_iter_cost_q8( void );
206 :
207 : FD_PROTOTYPES_END
208 :
209 : #if 0 /* SHA256 batch API details */
210 :
211 : /* FD_SHA256_BATCH_{ALIGN,FOOTPRINT} return the alignment and footprint
212 : in bytes required for a region of memory to can hold the state of an
213 : in-progress set of SHA-256 calculations. ALIGN will be an integer
214 : power of 2 and FOOTPRINT will be a multiple of ALIGN. These are to
215 : facilitate compile time declarations. */
216 :
217 : #define FD_SHA256_BATCH_ALIGN ...
218 : #define FD_SHA256_BATCH_FOOTPRINT ...
219 :
220 : /* FD_SHA256_BATCH_MAX returns the batch size used under the hood.
221 : Will be positive. Users should not normally need use this for
222 : anything. */
223 :
224 : #define FD_SHA256_BATCH_MAX ...
225 :
226 : /* A fd_sha256_batch_t is an opaque handle for a set of SHA-256
227 : calculations. */
228 :
229 : struct fd_sha256_private_batch;
230 : typedef struct fd_sha256_private_batch fd_sha256_batch_t;
231 :
232 : /* fd_sha256_batch_{align,footprint} return
233 : FD_SHA256_BATCH_{ALIGN,FOOTPRINT} respectively. */
234 :
235 : ulong fd_sha256_batch_align ( void );
236 : ulong fd_sha256_batch_footprint( void );
237 :
238 : /* fd_sha256_batch_init starts a new batch of SHA-256 calculations. The
239 : state of the in-progress calculation will be held in the memory
240 : region whose first byte in the local address space is pointed to by
241 : mem. The region should have the appropriate alignment and footprint
242 : and should not be read, changed or deleted until fini or abort is
243 : called on the in-progress calculation.
244 :
245 : Returns a handle to the in-progress batch calculation. As this is
246 : used in HPC contexts, does no input validation. */
247 :
248 : fd_sha256_batch_t *
249 : fd_sha256_batch_init( void * mem );
250 :
251 : /* fd_sha256_batch_add adds the sz byte message whose first byte in the
252 : local address space is pointed to by data to the in-progress batch
253 : calculation whose handle is batch. The result of the calculation
254 : will be stored at the 32-byte memory region whose first byte in the
255 : local address space is pointed to by hash.
256 :
257 : There are _no_ alignment restrictions on data and hash and _no_
258 : restrictions on sz. After a message is added, that message should
259 : not be changed or deleted until the fini or abort is called on the
260 : in-progress calculation. Likewise, the hash memory region shot not
261 : be read, written or deleted until the calculation has completed.
262 :
263 : Messages can overlap and/or be added to a batch multiple times. Each
264 : hash location added to a batch should not overlap any other hash
265 : location of calculation state or message region. (Hash reuse /
266 : overlap have indeterminant but non-crashing behavior as the
267 : implementation under the hood is free to execute the elements of the
268 : batch in whatever order it sees fit and potentially do those
269 : calculations incrementally / in the background / ... as the batch is
270 : assembled.)
271 :
272 : Depending on the implementation, it might help performance to cluster
273 : adds of similar sized messages together. Likewise, it can be
274 : advantageous to use aligned message regions, aligned hash regions and
275 : messages sizes that are a multiple of a SHA block size. None of this
276 : is required though.
277 :
278 : Returns batch (which will still be an in progress batch calculation).
279 : As this is used in HPC contexts, does no input validation. */
280 :
281 : fd_sha256_batch_t *
282 : fd_sha256_batch_add( fd_sha256_batch_t * batch,
283 : void const * data,
284 : ulong sz,
285 : void * hash );
286 :
287 : /* fd_sha256_batch_fini finishes a set of SHA-256 calculations. On
288 : return, all the hash memory regions will be populated with the
289 : corresponding message hash. Returns a pointer to the memory region
290 : used to hold the calculation state (contents undefined) and the
291 : calculation will no longer be in progress. As this is used in HPC
292 : contexts, does no input validation. */
293 :
294 : void *
295 : fd_sha256_batch_fini( fd_sha256_batch_t * batch );
296 :
297 : /* fd_sha256_batch_abort aborts an in-progress set of SHA-256
298 : calculations. There is no guarantee which individual messages (if
299 : any) had their hashes computed and the contents of the hash memory
300 : regions is undefined. Returns a pointer to the memory region used to
301 : hold the calculation state (contents undefined) and the calculation
302 : will no longer be in progress. As this is used in HPC contexts, does
303 : no input validation. */
304 :
305 : void *
306 : fd_sha256_batch_abort( fd_sha256_batch_t * batch );
307 :
308 : #endif
309 :
310 : #ifndef FD_SHA256_BATCH_IMPL
311 : #if FD_HAS_AVX512
312 : #define FD_SHA256_BATCH_IMPL 2
313 : #elif FD_HAS_AVX && !defined(__tune_znver1__) && !defined(__tune_znver2__) && !defined(__tune_znver3__)
314 : #define FD_SHA256_BATCH_IMPL 1
315 : #else
316 : #define FD_SHA256_BATCH_IMPL 0
317 : #endif
318 : #endif
319 :
320 : #if FD_SHA256_BATCH_IMPL==0 /* Reference batching implementation */
321 :
322 : #define FD_SHA256_BATCH_ALIGN (1UL)
323 : #define FD_SHA256_BATCH_FOOTPRINT (1UL)
324 : #define FD_SHA256_BATCH_MAX (1UL)
325 :
326 : typedef uchar fd_sha256_batch_t;
327 :
328 : FD_PROTOTYPES_BEGIN
329 :
330 : FD_FN_CONST static inline ulong fd_sha256_batch_align ( void ) { return alignof(fd_sha256_batch_t); }
331 : FD_FN_CONST static inline ulong fd_sha256_batch_footprint( void ) { return sizeof (fd_sha256_batch_t); }
332 :
333 : static inline fd_sha256_batch_t * fd_sha256_batch_init( void * mem ) { return (fd_sha256_batch_t *)mem; }
334 :
335 : static inline fd_sha256_batch_t *
336 : fd_sha256_batch_add( fd_sha256_batch_t * batch,
337 : void const * data,
338 : ulong sz,
339 : void * hash ) {
340 : fd_sha256_hash( data, sz, hash );
341 : return batch;
342 : }
343 :
344 : static inline void * fd_sha256_batch_fini ( fd_sha256_batch_t * batch ) { return (void *)batch; }
345 : static inline void * fd_sha256_batch_abort( fd_sha256_batch_t * batch ) { return (void *)batch; }
346 :
347 : FD_PROTOTYPES_END
348 :
349 : #elif FD_SHA256_BATCH_IMPL==1 /* AVX accelerated batching implementation */
350 :
351 : #define FD_SHA256_BATCH_ALIGN (128UL)
352 : #define FD_SHA256_BATCH_FOOTPRINT (256UL)
353 2651188 : #define FD_SHA256_BATCH_MAX (8UL)
354 :
355 : /* This is exposed here to facilitate inlining various operations */
356 :
357 : struct __attribute__((aligned(FD_SHA256_BATCH_ALIGN))) fd_sha256_private_batch {
358 : void const * data[ FD_SHA256_BATCH_MAX ]; /* AVX aligned */
359 : ulong sz [ FD_SHA256_BATCH_MAX ]; /* AVX aligned */
360 : void * hash[ FD_SHA256_BATCH_MAX ]; /* AVX aligned */
361 : ulong cnt;
362 : };
363 :
364 : typedef struct fd_sha256_private_batch fd_sha256_batch_t;
365 :
366 : FD_PROTOTYPES_BEGIN
367 :
368 : /* Internal use only */
369 :
370 : void
371 : fd_sha256_private_batch_avx( ulong batch_cnt, /* In [1,FD_SHA256_BATCH_MAX] */
372 : void const * batch_data, /* Indexed [0,FD_SHA256_BATCH_MAX), aligned 32,
373 : only [0,batch_cnt) used, essentially a msg_t const * const * */
374 : ulong const * batch_sz, /* Indexed [0,FD_SHA256_BATCH_MAX), aligned 32,
375 : only [0,batch_cnt) used */
376 : void * const * batch_hash ); /* Indexed [0,FD_SHA256_BATCH_MAX), aligned 32,
377 : only [0,batch_cnt) used */
378 :
379 2 : FD_FN_CONST static inline ulong fd_sha256_batch_align ( void ) { return alignof(fd_sha256_batch_t); }
380 2 : FD_FN_CONST static inline ulong fd_sha256_batch_footprint( void ) { return sizeof (fd_sha256_batch_t); }
381 :
382 : static inline fd_sha256_batch_t *
383 2135046 : fd_sha256_batch_init( void * mem ) {
384 2135046 : fd_sha256_batch_t * batch = (fd_sha256_batch_t *)mem;
385 2135046 : batch->cnt = 0UL;
386 2135046 : return batch;
387 2135046 : }
388 :
389 : static inline fd_sha256_batch_t *
390 : fd_sha256_batch_add( fd_sha256_batch_t * batch,
391 : void const * data,
392 : ulong sz,
393 18147406 : void * hash ) {
394 18147406 : ulong batch_cnt = batch->cnt;
395 18147406 : batch->data[ batch_cnt ] = data;
396 18147406 : batch->sz [ batch_cnt ] = sz;
397 18147406 : batch->hash[ batch_cnt ] = hash;
398 18147406 : batch_cnt++;
399 18147406 : if( FD_UNLIKELY( batch_cnt==FD_SHA256_BATCH_MAX ) ) {
400 2021744 : fd_sha256_private_batch_avx( batch_cnt, batch->data, batch->sz, batch->hash );
401 2021744 : batch_cnt = 0UL;
402 2021744 : }
403 18147406 : batch->cnt = batch_cnt;
404 18147406 : return batch;
405 18147406 : }
406 :
407 : static inline void *
408 2132978 : fd_sha256_batch_fini( fd_sha256_batch_t * batch ) {
409 2132978 : ulong batch_cnt = batch->cnt;
410 2132978 : if( FD_LIKELY( batch_cnt ) ) fd_sha256_private_batch_avx( batch_cnt, batch->data, batch->sz, batch->hash );
411 2132978 : return (void *)batch;
412 2132978 : }
413 :
414 : static inline void *
415 2068 : fd_sha256_batch_abort( fd_sha256_batch_t * batch ) {
416 2068 : return (void *)batch;
417 2068 : }
418 :
419 : FD_PROTOTYPES_END
420 :
421 : #elif FD_SHA256_BATCH_IMPL==2 /* AVX-512 accelerated batching implementation */
422 :
423 : #define FD_SHA256_BATCH_ALIGN (128UL)
424 : #define FD_SHA256_BATCH_FOOTPRINT (512UL)
425 1015726 : #define FD_SHA256_BATCH_MAX (16UL)
426 :
427 : /* This is exposed here to facilitate inlining various operations */
428 :
429 : struct __attribute__((aligned(FD_SHA256_BATCH_ALIGN))) fd_sha256_private_batch {
430 : void const * data[ FD_SHA256_BATCH_MAX ]; /* AVX aligned */
431 : ulong sz [ FD_SHA256_BATCH_MAX ]; /* AVX aligned */
432 : void * hash[ FD_SHA256_BATCH_MAX ]; /* AVX aligned */
433 : ulong cnt;
434 : };
435 :
436 : typedef struct fd_sha256_private_batch fd_sha256_batch_t;
437 :
438 : FD_PROTOTYPES_BEGIN
439 :
440 : /* Internal use only */
441 :
442 : void
443 : fd_sha256_private_batch_avx512( ulong batch_cnt, /* In [1,FD_SHA256_BATCH_MAX] */
444 : void const * batch_data, /* Indexed [0,FD_SHA256_BATCH_MAX), aligned 32,
445 : only [0,batch_cnt) used, essentially a msg_t const * const * */
446 : ulong const * batch_sz, /* Indexed [0,FD_SHA256_BATCH_MAX), aligned 32,
447 : only [0,batch_cnt) used */
448 : void * const * batch_hash ); /* Indexed [0,FD_SHA256_BATCH_MAX), aligned 32,
449 : only [0,batch_cnt) used */
450 :
451 1 : FD_FN_CONST static inline ulong fd_sha256_batch_align ( void ) { return alignof(fd_sha256_batch_t); }
452 1 : FD_FN_CONST static inline ulong fd_sha256_batch_footprint( void ) { return sizeof (fd_sha256_batch_t); }
453 :
454 : static inline fd_sha256_batch_t *
455 879813 : fd_sha256_batch_init( void * mem ) {
456 879813 : fd_sha256_batch_t * batch = (fd_sha256_batch_t *)mem;
457 879813 : batch->cnt = 0UL;
458 879813 : return batch;
459 879813 : }
460 :
461 : static inline fd_sha256_batch_t *
462 : fd_sha256_batch_add( fd_sha256_batch_t * batch,
463 : void const * data,
464 : ulong sz,
465 9106479 : void * hash ) {
466 9106479 : ulong batch_cnt = batch->cnt;
467 9106479 : batch->data[ batch_cnt ] = data;
468 9106479 : batch->sz [ batch_cnt ] = sz;
469 9106479 : batch->hash[ batch_cnt ] = hash;
470 9106479 : batch_cnt++;
471 9106479 : if( FD_UNLIKELY( batch_cnt==FD_SHA256_BATCH_MAX ) ) {
472 467976 : fd_sha256_private_batch_avx512( batch_cnt, batch->data, batch->sz, batch->hash );
473 467976 : batch_cnt = 0UL;
474 467976 : }
475 9106479 : batch->cnt = batch_cnt;
476 9106479 : return batch;
477 9106479 : }
478 :
479 : static inline void *
480 878779 : fd_sha256_batch_fini( fd_sha256_batch_t * batch ) {
481 878779 : ulong batch_cnt = batch->cnt;
482 878779 : if( FD_LIKELY( batch_cnt ) ) fd_sha256_private_batch_avx512( batch_cnt, batch->data, batch->sz, batch->hash );
483 878779 : return (void *)batch;
484 878779 : }
485 :
486 : static inline void *
487 1034 : fd_sha256_batch_abort( fd_sha256_batch_t * batch ) {
488 1034 : return (void *)batch;
489 1034 : }
490 :
491 : FD_PROTOTYPES_END
492 :
493 : #else
494 : #error "Unsupported FD_SHA256_BATCH_IMPL"
495 : #endif
496 :
497 : #endif /* HEADER_fd_src_ballet_sha256_fd_sha256_h */
|
