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 23457 : #define FD_SHA256_ALIGN (128UL)
16 11727 : #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 0 : #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 56851 : #define FD_SHA256_LG_BLOCK_SZ (6)
28 66330 : #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 11735 : #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 56851 : #define FD_SHA256_PRIVATE_LG_BUF_MAX FD_SHA256_LG_BLOCK_SZ
41 66330 : #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 x86 with SHA-NI (interleaved chains) or
172 : AVX-512 and on armv8 (NEON, FEAT_SHA2). The latency of any
173 : individual computation is worse than fd_sha256_hash_32_repeated,
174 : possibly by ~8x depending on arch. But this version has higher
175 : throughput at batch widths of fd_sha256_simd_lane_min and higher
176 : (assuming no pipeline bubbles in cnt). lane_cnt must be in
177 : [0,simd_lane_max], otherwise the process 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 with lane_cnt lanes in units of one
200 : iteration of fd_sha256_hash_32_repeated, as a fixed point number
201 : with 8 fractional bits (256 is 1.0x). Lets a caller size a batched
202 : call to a wall clock budget. Returns 256*lane_cnt if there is no
203 : fast SIMD option. lane_cnt should be in [1,simd_lane_max]. */
204 :
205 : FD_FN_CONST ulong
206 : fd_sha256_simd_iter_cost_q8( ulong lane_cnt );
207 :
208 : FD_PROTOTYPES_END
209 :
210 : #if 0 /* SHA256 batch API details */
211 :
212 : /* FD_SHA256_BATCH_{ALIGN,FOOTPRINT} return the alignment and footprint
213 : in bytes required for a region of memory to can hold the state of an
214 : in-progress set of SHA-256 calculations. ALIGN will be an integer
215 : power of 2 and FOOTPRINT will be a multiple of ALIGN. These are to
216 : facilitate compile time declarations. */
217 :
218 : #define FD_SHA256_BATCH_ALIGN ...
219 : #define FD_SHA256_BATCH_FOOTPRINT ...
220 :
221 : /* FD_SHA256_BATCH_MAX returns the batch size used under the hood.
222 : Will be positive. Users should not normally need use this for
223 : anything. */
224 :
225 : #define FD_SHA256_BATCH_MAX ...
226 :
227 : /* A fd_sha256_batch_t is an opaque handle for a set of SHA-256
228 : calculations. */
229 :
230 : struct fd_sha256_private_batch;
231 : typedef struct fd_sha256_private_batch fd_sha256_batch_t;
232 :
233 : /* fd_sha256_batch_{align,footprint} return
234 : FD_SHA256_BATCH_{ALIGN,FOOTPRINT} respectively. */
235 :
236 : ulong fd_sha256_batch_align ( void );
237 : ulong fd_sha256_batch_footprint( void );
238 :
239 : /* fd_sha256_batch_init starts a new batch of SHA-256 calculations. The
240 : state of the in-progress calculation will be held in the memory
241 : region whose first byte in the local address space is pointed to by
242 : mem. The region should have the appropriate alignment and footprint
243 : and should not be read, changed or deleted until fini or abort is
244 : called on the in-progress calculation.
245 :
246 : Returns a handle to the in-progress batch calculation. As this is
247 : used in HPC contexts, does no input validation. */
248 :
249 : fd_sha256_batch_t *
250 : fd_sha256_batch_init( void * mem );
251 :
252 : /* fd_sha256_batch_add adds the sz byte message whose first byte in the
253 : local address space is pointed to by data to the in-progress batch
254 : calculation whose handle is batch. The result of the calculation
255 : will be stored at the 32-byte memory region whose first byte in the
256 : local address space is pointed to by hash.
257 :
258 : There are _no_ alignment restrictions on data and hash and _no_
259 : restrictions on sz. After a message is added, that message should
260 : not be changed or deleted until the fini or abort is called on the
261 : in-progress calculation. Likewise, the hash memory region shot not
262 : be read, written or deleted until the calculation has completed.
263 :
264 : Messages can overlap and/or be added to a batch multiple times. Each
265 : hash location added to a batch should not overlap any other hash
266 : location of calculation state or message region. (Hash reuse /
267 : overlap have indeterminant but non-crashing behavior as the
268 : implementation under the hood is free to execute the elements of the
269 : batch in whatever order it sees fit and potentially do those
270 : calculations incrementally / in the background / ... as the batch is
271 : assembled.)
272 :
273 : Depending on the implementation, it might help performance to cluster
274 : adds of similar sized messages together. Likewise, it can be
275 : advantageous to use aligned message regions, aligned hash regions and
276 : messages sizes that are a multiple of a SHA block size. None of this
277 : is required though.
278 :
279 : Returns batch (which will still be an in progress batch calculation).
280 : As this is used in HPC contexts, does no input validation. */
281 :
282 : fd_sha256_batch_t *
283 : fd_sha256_batch_add( fd_sha256_batch_t * batch,
284 : void const * data,
285 : ulong sz,
286 : void * hash );
287 :
288 : /* fd_sha256_batch_fini finishes a set of SHA-256 calculations. On
289 : return, all the hash memory regions will be populated with the
290 : corresponding message hash. Returns a pointer to the memory region
291 : used to hold the calculation state (contents undefined) and the
292 : calculation will no longer be in progress. As this is used in HPC
293 : contexts, does no input validation. */
294 :
295 : void *
296 : fd_sha256_batch_fini( fd_sha256_batch_t * batch );
297 :
298 : /* fd_sha256_batch_abort aborts an in-progress set of SHA-256
299 : calculations. There is no guarantee which individual messages (if
300 : any) had their hashes computed and the contents of the hash memory
301 : regions is undefined. Returns a pointer to the memory region used to
302 : hold the calculation state (contents undefined) and the calculation
303 : will no longer be in progress. As this is used in HPC contexts, does
304 : no input validation. */
305 :
306 : void *
307 : fd_sha256_batch_abort( fd_sha256_batch_t * batch );
308 :
309 : #endif
310 :
311 : #ifndef FD_SHA256_BATCH_IMPL
312 : #if FD_HAS_AVX512
313 : #define FD_SHA256_BATCH_IMPL 2
314 : #elif FD_HAS_AVX && !defined(__tune_znver1__) && !defined(__tune_znver2__) && !defined(__tune_znver3__)
315 : #define FD_SHA256_BATCH_IMPL 1
316 : #else
317 : #define FD_SHA256_BATCH_IMPL 0
318 : #endif
319 : #endif
320 :
321 : #if FD_SHA256_BATCH_IMPL==0 /* Reference batching implementation */
322 :
323 : #define FD_SHA256_BATCH_ALIGN (1UL)
324 : #define FD_SHA256_BATCH_FOOTPRINT (1UL)
325 : #define FD_SHA256_BATCH_MAX (1UL)
326 :
327 : typedef uchar fd_sha256_batch_t;
328 :
329 : FD_PROTOTYPES_BEGIN
330 :
331 : FD_FN_CONST static inline ulong fd_sha256_batch_align ( void ) { return alignof(fd_sha256_batch_t); }
332 : FD_FN_CONST static inline ulong fd_sha256_batch_footprint( void ) { return sizeof (fd_sha256_batch_t); }
333 :
334 : static inline fd_sha256_batch_t * fd_sha256_batch_init( void * mem ) { return (fd_sha256_batch_t *)mem; }
335 :
336 : static inline fd_sha256_batch_t *
337 : fd_sha256_batch_add( fd_sha256_batch_t * batch,
338 : void const * data,
339 : ulong sz,
340 : void * hash ) {
341 : fd_sha256_hash( data, sz, hash );
342 : return batch;
343 : }
344 :
345 : static inline void * fd_sha256_batch_fini ( fd_sha256_batch_t * batch ) { return (void *)batch; }
346 : static inline void * fd_sha256_batch_abort( fd_sha256_batch_t * batch ) { return (void *)batch; }
347 :
348 : FD_PROTOTYPES_END
349 :
350 : #elif FD_SHA256_BATCH_IMPL==1 /* AVX accelerated batching implementation */
351 :
352 : #define FD_SHA256_BATCH_ALIGN (128UL)
353 : #define FD_SHA256_BATCH_FOOTPRINT (256UL)
354 : #define FD_SHA256_BATCH_MAX (8UL)
355 :
356 : /* This is exposed here to facilitate inlining various operations */
357 :
358 : struct __attribute__((aligned(FD_SHA256_BATCH_ALIGN))) fd_sha256_private_batch {
359 : void const * data[ FD_SHA256_BATCH_MAX ]; /* AVX aligned */
360 : ulong sz [ FD_SHA256_BATCH_MAX ]; /* AVX aligned */
361 : void * hash[ FD_SHA256_BATCH_MAX ]; /* AVX aligned */
362 : ulong cnt;
363 : };
364 :
365 : typedef struct fd_sha256_private_batch fd_sha256_batch_t;
366 :
367 : FD_PROTOTYPES_BEGIN
368 :
369 : /* Internal use only */
370 :
371 : void
372 : fd_sha256_private_batch_avx( ulong batch_cnt, /* In [1,FD_SHA256_BATCH_MAX] */
373 : void const * batch_data, /* Indexed [0,FD_SHA256_BATCH_MAX), aligned 32,
374 : only [0,batch_cnt) used, essentially a msg_t const * const * */
375 : ulong const * batch_sz, /* Indexed [0,FD_SHA256_BATCH_MAX), aligned 32,
376 : only [0,batch_cnt) used */
377 : void * const * batch_hash ); /* Indexed [0,FD_SHA256_BATCH_MAX), aligned 32,
378 : only [0,batch_cnt) used */
379 :
380 0 : FD_FN_CONST static inline ulong fd_sha256_batch_align ( void ) { return alignof(fd_sha256_batch_t); }
381 0 : FD_FN_CONST static inline ulong fd_sha256_batch_footprint( void ) { return sizeof (fd_sha256_batch_t); }
382 :
383 : static inline fd_sha256_batch_t *
384 0 : fd_sha256_batch_init( void * mem ) {
385 0 : fd_sha256_batch_t * batch = (fd_sha256_batch_t *)mem;
386 0 : batch->cnt = 0UL;
387 0 : return batch;
388 0 : }
389 :
390 : static inline fd_sha256_batch_t *
391 : fd_sha256_batch_add( fd_sha256_batch_t * batch,
392 : void const * data,
393 : ulong sz,
394 0 : void * hash ) {
395 0 : ulong batch_cnt = batch->cnt;
396 0 : batch->data[ batch_cnt ] = data;
397 0 : batch->sz [ batch_cnt ] = sz;
398 0 : batch->hash[ batch_cnt ] = hash;
399 0 : batch_cnt++;
400 0 : if( FD_UNLIKELY( batch_cnt==FD_SHA256_BATCH_MAX ) ) {
401 0 : fd_sha256_private_batch_avx( batch_cnt, batch->data, batch->sz, batch->hash );
402 0 : batch_cnt = 0UL;
403 0 : }
404 0 : batch->cnt = batch_cnt;
405 0 : return batch;
406 0 : }
407 :
408 : static inline void *
409 0 : fd_sha256_batch_fini( fd_sha256_batch_t * batch ) {
410 0 : ulong batch_cnt = batch->cnt;
411 0 : if( FD_LIKELY( batch_cnt ) ) fd_sha256_private_batch_avx( batch_cnt, batch->data, batch->sz, batch->hash );
412 0 : return (void *)batch;
413 0 : }
414 :
415 : static inline void *
416 0 : fd_sha256_batch_abort( fd_sha256_batch_t * batch ) {
417 0 : return (void *)batch;
418 0 : }
419 :
420 : FD_PROTOTYPES_END
421 :
422 : #elif FD_SHA256_BATCH_IMPL==2 /* AVX-512 accelerated batching implementation */
423 :
424 : #define FD_SHA256_BATCH_ALIGN (128UL)
425 : #define FD_SHA256_BATCH_FOOTPRINT (512UL)
426 0 : #define FD_SHA256_BATCH_MAX (16UL)
427 :
428 : /* This is exposed here to facilitate inlining various operations */
429 :
430 : struct __attribute__((aligned(FD_SHA256_BATCH_ALIGN))) fd_sha256_private_batch {
431 : void const * data[ FD_SHA256_BATCH_MAX ]; /* AVX aligned */
432 : ulong sz [ FD_SHA256_BATCH_MAX ]; /* AVX aligned */
433 : void * hash[ FD_SHA256_BATCH_MAX ]; /* AVX aligned */
434 : ulong cnt;
435 : };
436 :
437 : typedef struct fd_sha256_private_batch fd_sha256_batch_t;
438 :
439 : FD_PROTOTYPES_BEGIN
440 :
441 : /* Internal use only */
442 :
443 : void
444 : fd_sha256_private_batch_avx512( ulong batch_cnt, /* In [1,FD_SHA256_BATCH_MAX] */
445 : void const * batch_data, /* Indexed [0,FD_SHA256_BATCH_MAX), aligned 32,
446 : only [0,batch_cnt) used, essentially a msg_t const * const * */
447 : ulong const * batch_sz, /* Indexed [0,FD_SHA256_BATCH_MAX), aligned 32,
448 : only [0,batch_cnt) used */
449 : void * const * batch_hash ); /* Indexed [0,FD_SHA256_BATCH_MAX), aligned 32,
450 : only [0,batch_cnt) used */
451 :
452 0 : FD_FN_CONST static inline ulong fd_sha256_batch_align ( void ) { return alignof(fd_sha256_batch_t); }
453 0 : FD_FN_CONST static inline ulong fd_sha256_batch_footprint( void ) { return sizeof (fd_sha256_batch_t); }
454 :
455 : static inline fd_sha256_batch_t *
456 0 : fd_sha256_batch_init( void * mem ) {
457 0 : fd_sha256_batch_t * batch = (fd_sha256_batch_t *)mem;
458 0 : batch->cnt = 0UL;
459 0 : return batch;
460 0 : }
461 :
462 : static inline fd_sha256_batch_t *
463 : fd_sha256_batch_add( fd_sha256_batch_t * batch,
464 : void const * data,
465 : ulong sz,
466 0 : void * hash ) {
467 0 : ulong batch_cnt = batch->cnt;
468 0 : batch->data[ batch_cnt ] = data;
469 0 : batch->sz [ batch_cnt ] = sz;
470 0 : batch->hash[ batch_cnt ] = hash;
471 0 : batch_cnt++;
472 0 : if( FD_UNLIKELY( batch_cnt==FD_SHA256_BATCH_MAX ) ) {
473 0 : fd_sha256_private_batch_avx512( batch_cnt, batch->data, batch->sz, batch->hash );
474 0 : batch_cnt = 0UL;
475 0 : }
476 0 : batch->cnt = batch_cnt;
477 0 : return batch;
478 0 : }
479 :
480 : static inline void *
481 0 : fd_sha256_batch_fini( fd_sha256_batch_t * batch ) {
482 0 : ulong batch_cnt = batch->cnt;
483 0 : if( FD_LIKELY( batch_cnt ) ) fd_sha256_private_batch_avx512( batch_cnt, batch->data, batch->sz, batch->hash );
484 0 : return (void *)batch;
485 0 : }
486 :
487 : static inline void *
488 0 : fd_sha256_batch_abort( fd_sha256_batch_t * batch ) {
489 0 : return (void *)batch;
490 0 : }
491 :
492 : FD_PROTOTYPES_END
493 :
494 : #else
495 : #error "Unsupported FD_SHA256_BATCH_IMPL"
496 : #endif
497 :
498 : #endif /* HEADER_fd_src_ballet_sha256_fd_sha256_h */
|
