Line data Source code
1 : #include "fd_blake3.h"
2 : #include "fd_blake3_private.h"
3 :
4 : /* Hash state machine *************************************************/
5 :
6 : static FD_FN_UNUSED fd_blake3_pos_t *
7 : fd_blake3_pos_init( fd_blake3_pos_t * s,
8 : uchar const * data,
9 11591438 : ulong sz ) {
10 11591438 : *s = (fd_blake3_pos_t) {
11 11591438 : .input = data,
12 11591438 : .input_sz = sz,
13 11591438 : .magic = FD_BLAKE3_MAGIC,
14 11591438 : };
15 11591438 : return s;
16 11591438 : }
17 :
18 : /* fd_blake3_l0_complete returns 1 if all leaf nodes have been hashed,
19 : 0 otherwise. */
20 :
21 : FD_FN_PURE static inline int
22 49871509 : fd_blake3_l0_complete( fd_blake3_pos_t const * s ) {
23 49871509 : return ( s->leaf_idx<<FD_BLAKE3_CHUNK_LG_SZ ) >= fd_ulong_max( s->input_sz, 64 );
24 49871509 : }
25 :
26 : FD_FN_PURE static inline int
27 : fd_blake3_is_finished( fd_blake3_pos_t const * s,
28 21742683 : ulong tick ) {
29 21742683 : int l0_complete = fd_blake3_l0_complete( s );
30 21742683 : int ln_complete = s->live_cnt == 1UL;
31 21742683 : int idle = tick >= s->next_tick;
32 21742683 : return l0_complete & ln_complete & idle;
33 21742683 : }
34 :
35 : static fd_blake3_op_t *
36 : fd_blake3_prepare_leaf( fd_blake3_pos_t * restrict s,
37 : fd_blake3_buf_t * restrict buf,
38 : fd_blake3_op_t * restrict op,
39 14904861 : ulong tick ) {
40 :
41 14904861 : ulong msg_off = s->leaf_idx << FD_BLAKE3_CHUNK_LG_SZ;
42 14904861 : ulong msg_sz = fd_ulong_min( s->input_sz - msg_off, 1024UL );
43 14904861 : uchar const * msg = s->input + msg_off;
44 14904861 : uchar * out = buf->slots[ s->layer ][ s->head.uc[ s->layer ] ];
45 :
46 14904861 : int flags = fd_int_if( s->input_sz <= FD_BLAKE3_CHUNK_SZ, FD_BLAKE3_FLAG_ROOT, 0 );
47 :
48 14904861 : *op = (fd_blake3_op_t) {
49 14904861 : .msg = msg,
50 14904861 : .out = out,
51 14904861 : .counter = s->leaf_idx,
52 14904861 : .sz = (ushort)msg_sz,
53 14904861 : .flags = (uchar)flags
54 14904861 : };
55 :
56 14904861 : s->head.uc[ 0 ] = (uchar)( s->head.uc[ 0 ]+1 );
57 14904861 : s->leaf_idx++;
58 14904861 : s->live_cnt++;
59 14904861 : s->next_tick = tick+1;
60 :
61 14904861 : return op;
62 :
63 14904861 : }
64 :
65 : static int
66 : fd_blake3_seek_branch( fd_blake3_pos_t * restrict s,
67 : fd_blake3_buf_t * restrict buf,
68 15962111 : ulong tick ) {
69 :
70 15962111 : if( s->live_cnt == 1UL )
71 77763 : return 0;
72 :
73 15884348 : if( !fd_blake3_l0_complete( s ) )
74 2188880 : return ( s->tail.uc[ s->layer - 1 ] + 1 ) <
75 2188880 : ( s->head.uc[ s->layer - 1 ] );
76 :
77 13695468 : # if FD_HAS_AVX
78 :
79 13695468 : wb_t diff = wb_sub( wb_ld( s->head.uc ), wb_ld( s->tail.uc ) );
80 :
81 13695468 : uint mergeable_layers = (uint)_mm256_movemask_epi8( wb_gt( diff, wb_bcast( 1 ) ) );
82 13695468 : int merge_layer = fd_uint_find_lsb_w_default( mergeable_layers, -1 );
83 13695468 : if( merge_layer>=0 ) {
84 12467697 : if( ((uint)merge_layer >= s->layer) & (tick < s->next_tick) )
85 2373579 : return 0; /* still waiting for previous merge */
86 10094118 : s->layer = (uint)merge_layer+1U;
87 10094118 : return 1;
88 12467697 : }
89 :
90 1227771 : uint single_layers = (uint)_mm256_movemask_epi8( wb_eq( diff, wb_bcast( 1 ) ) );
91 1227771 : uint single_lo = (uint)fd_uint_find_lsb( single_layers );
92 1227771 : uint single_hi = (uint)fd_uint_find_lsb( single_layers & ( ~fd_uint_mask_lsb( (int)(single_lo+1U) ) ) );
93 :
94 1227771 : wb_t node = wb_ld( buf->slots[ single_lo ][ s->tail.uc[ single_lo ] ] );
95 1227771 : wb_st( buf->slots[ single_hi ][ s->head.uc[ single_hi ] ], node );
96 :
97 : # else /* FD_HAS_AVX */
98 :
99 : uchar diff[ 32 ];
100 : for( ulong j=0UL; j<32UL; j++ ) diff[j] = (uchar)( s->head.uc[j] - s->tail.uc[j] );
101 :
102 : int merge_layer = -1;
103 : for( uint j=0U; j<32U; j++ ) {
104 : if( diff[j]>1 ) {
105 : merge_layer = (int)j;
106 : break;
107 : }
108 : }
109 : if( merge_layer>=0 ) {
110 : if( ((uint)merge_layer >= s->layer) & (tick < s->next_tick) )
111 : return 0; /* still waiting for previous merge */
112 : s->layer = (uint)(merge_layer+1);
113 : return 1;
114 : }
115 :
116 : uint j=0U;
117 : uint single_lo = 0UL;
118 : uint single_hi = 0UL;
119 : for( ; j<32U; j++ ) {
120 : if( diff[j] ) {
121 : single_lo = j;
122 : break;
123 : }
124 : }
125 : j++;
126 : for( ; j<32U; j++ ) {
127 : if( diff[j] ) {
128 : single_hi = j;
129 : break;
130 : }
131 : }
132 :
133 : memcpy( buf->slots[ single_hi ][ s->head.uc[ single_hi ] ],
134 : buf->slots[ single_lo ][ s->tail.uc[ single_lo ] ],
135 : 32UL );
136 :
137 : # endif /* FD_HAS_AVX */
138 :
139 1227771 : FD_BLAKE3_TRACE(( "fd_blake3_seek_branch: moving up %u/%u to %u/%u",
140 1227771 : single_lo, s->tail.uc[ single_lo ],
141 1227771 : single_hi, s->head.uc[ single_hi ] ));
142 :
143 1227771 : if( ((uint)single_hi >= s->layer) & (tick < s->next_tick) )
144 447570 : return 0; /* still waiting for previous merge */
145 :
146 780201 : s->head.uc[ single_lo ] = (uchar)( s->head.uc[ single_lo ]-1 );
147 780201 : s->head.uc[ single_hi ] = (uchar)( s->head.uc[ single_hi ]+1 );
148 :
149 780201 : s->layer = (uint)single_hi+1U;
150 780201 : return 1;
151 1227771 : }
152 :
153 : static fd_blake3_op_t *
154 : fd_blake3_prepare_branch( fd_blake3_pos_t * restrict s,
155 : fd_blake3_buf_t * restrict buf,
156 : fd_blake3_op_t * restrict op,
157 15962111 : ulong tick ) {
158 :
159 15962111 : if( !fd_blake3_seek_branch( s, buf, tick ) )
160 2898912 : return NULL;
161 :
162 13063199 : FD_DCHECK_CRIT( s->layer < FD_BLAKE3_ROW_CNT, "invariant violation" );
163 :
164 13063199 : uchar const * msg = buf->slots[ s->layer-1U ][ s->tail.uc[ s->layer-1U ] ];
165 13063199 : uchar * out = buf->slots[ s->layer ][ s->head.uc[ s->layer ] ];
166 :
167 13063199 : s->head.uc[ s->layer ] = (uchar)( s->head.uc[ s->layer ]+1 );
168 13063199 : s->tail.uc[ s->layer-1 ] = (uchar)( s->tail.uc[ s->layer-1 ]+2 );
169 13063199 : s->live_cnt--;
170 13063199 : s->next_tick = tick+1;
171 :
172 13063199 : uint flags = FD_BLAKE3_FLAG_PARENT |
173 13063199 : fd_uint_if( s->live_cnt==1UL, FD_BLAKE3_FLAG_ROOT, 0u );
174 :
175 13063199 : *op = (fd_blake3_op_t) {
176 13063199 : .msg = msg,
177 13063199 : .out = out,
178 13063199 : .counter = 0UL,
179 13063199 : .sz = 64U,
180 13063199 : .flags = (uchar)flags
181 13063199 : };
182 13063199 : return op;
183 :
184 15962111 : }
185 :
186 : static void
187 4676942 : fd_blake3_advance( fd_blake3_pos_t * restrict s ) {
188 :
189 4676942 : # if FD_HAS_AVX
190 :
191 4676942 : wb_t tail = wb_ld( s->tail.uc );
192 4676942 : wb_t head = wb_ld( s->head.uc );
193 4676942 : wb_t mask = wb_eq( tail, head );
194 4676942 : wb_st( s->tail.uc, wb_andnot( mask, tail ) );
195 4676942 : wb_st( s->head.uc, wb_andnot( mask, head ) );
196 :
197 : # else /* FD_HAS_AVX */
198 :
199 : for( ulong j=0UL; j<32UL; j++ ) {
200 : if( s->tail.uc[j] == s->head.uc[j] ) {
201 : s->tail.uc[j] = 0;
202 : s->head.uc[j] = 0;
203 : }
204 : }
205 :
206 : # endif /* FD_HAS_AVX */
207 :
208 4676942 : if( s->head.uc[ s->layer ]==FD_BLAKE3_COL_CNT ) {
209 114590 : s->layer++;
210 114590 : }
211 4562352 : else if( ( s->layer > 0UL ) &&
212 4562352 : ( s->tail.uc[ s->layer-1 ] < s->head.uc[ s->layer-1 ] ) ) {
213 : /* pass */
214 1105191 : }
215 3457161 : else if( fd_blake3_l0_complete( s ) ) {
216 2659484 : s->layer++;
217 2659484 : }
218 797677 : else if( s->layer > 0UL ) {
219 156224 : s->layer = 0UL;
220 156224 : }
221 :
222 4676942 : }
223 :
224 : static fd_blake3_op_t *
225 : fd_blake3_prepare( fd_blake3_pos_t * restrict s,
226 : fd_blake3_buf_t * restrict buf,
227 : fd_blake3_op_t * restrict op,
228 20818416 : ulong tick ) {
229 :
230 20818416 : FD_DCHECK_CRIT( s->layer < FD_BLAKE3_ROW_CNT, "invariant violation" );
231 :
232 20818416 : if( fd_blake3_is_finished( s, tick ) )
233 0 : return NULL;
234 :
235 20818416 : if( tick >= s->next_tick )
236 4676942 : fd_blake3_advance( s );
237 :
238 20818416 : if( s->layer != 0 )
239 15962111 : return fd_blake3_prepare_branch( s, buf, op, tick );
240 :
241 4856305 : if( ( s->head.uc[0] >= FD_BLAKE3_COL_CNT ) |
242 4856305 : ( fd_blake3_l0_complete( s ) ) ) {
243 742974 : return NULL;
244 742974 : }
245 :
246 4113331 : return fd_blake3_prepare_leaf( s, buf, op, tick );
247 :
248 4856305 : }
249 :
250 : #if FD_BLAKE3_PARA_MAX>1
251 :
252 : /* fd_blake3_prepare_fast does streamlined hashing of full chunks or
253 : full branches. */
254 :
255 : static fd_blake3_op_t *
256 : fd_blake3_prepare_fast( fd_blake3_pos_t * restrict s,
257 : fd_blake3_buf_t * restrict buf,
258 : fd_blake3_op_t * restrict op,
259 : ulong n,
260 8672586 : ulong min ) {
261 :
262 8672586 : if( s->layer && s->head.uc[ s->layer-1 ]==FD_BLAKE3_COL_CNT ) {
263 3835820 : op->msg = buf->rows[ s->layer-1 ];
264 3835820 : op->out = buf->rows[ s->layer ] + (s->head.uc[ s->layer ]<<FD_BLAKE3_OUTCHAIN_LG_SZ);
265 3835820 : op->counter = 0UL;
266 3835820 : op->flags = FD_BLAKE3_FLAG_PARENT;
267 :
268 : /* Assume that branch layer is fully hashed (up to col cnt) */
269 3835820 : s->head.uc[ s->layer-1 ] = 0;
270 3835820 : s->head.uc[ s->layer ] = (uchar)( (ulong)s->head.uc[ s->layer ]+n );
271 3835820 : s->live_cnt -= n;
272 3835820 : s->layer = fd_uint_if( s->head.uc[ s->layer ]==FD_BLAKE3_COL_CNT,
273 3835820 : s->layer+1U, 0U );
274 :
275 3835820 : return op;
276 3835820 : }
277 :
278 4836766 : ulong pos = s->leaf_idx << FD_BLAKE3_CHUNK_LG_SZ;
279 4836766 : ulong avail = fd_ulong_align_dn( s->input_sz - pos, FD_BLAKE3_CHUNK_SZ ) >> FD_BLAKE3_CHUNK_LG_SZ;
280 4836766 : n = fd_ulong_min( n, avail );
281 :
282 : /* This constants controls the threshold when to use the (slow)
283 : scheduler instead of fast single-message hashing. Carefully tuned
284 : for best overall performance. */
285 4836766 : if( n<min ) return NULL;
286 :
287 4810687 : op->msg = s->input + (s->leaf_idx<<FD_BLAKE3_CHUNK_LG_SZ);
288 4810687 : op->out = buf->rows[0] + (s->head.uc[0]<<FD_BLAKE3_OUTCHAIN_LG_SZ);
289 4810687 : op->counter = s->leaf_idx;
290 4810687 : op->flags = 0;
291 :
292 4810687 : s->head.uc[0] = (uchar)( (ulong)s->head.uc[0]+n );
293 4810687 : s->leaf_idx += n;
294 4810687 : s->live_cnt += n;
295 4810687 : s->layer = fd_uint_if( s->head.uc[0]==FD_BLAKE3_COL_CNT, 1U, 0U );
296 :
297 4810687 : return op;
298 4836766 : }
299 :
300 : static void
301 : fd_blake3_batch_hash( fd_blake3_op_t const * ops,
302 3668571 : ulong op_cnt ) {
303 3668571 : uchar const * batch_data [ FD_BLAKE3_PARA_MAX ] __attribute__((aligned(64)));
304 3668571 : uint batch_data_sz[ FD_BLAKE3_PARA_MAX ] = {0};
305 3668571 : uchar * batch_hash [ FD_BLAKE3_PARA_MAX ] __attribute__((aligned(64)));
306 3668571 : ulong batch_ctr [ FD_BLAKE3_PARA_MAX ];
307 3668571 : uint batch_flags [ FD_BLAKE3_PARA_MAX ];
308 20124063 : for( ulong j=0UL; j<op_cnt; j++ ) {
309 16455492 : batch_data [ j ] = ops[ j ].msg;
310 16455492 : batch_hash [ j ] = ops[ j ].out;
311 16455492 : batch_data_sz[ j ] = ops[ j ].sz;
312 16455492 : batch_ctr [ j ] = ops[ j ].counter;
313 16455492 : batch_flags [ j ] = ops[ j ].flags;
314 16455492 : }
315 1200061 : #if FD_HAS_AVX512
316 : /* Both kernels mask off dead lanes, so a batch of at most 8 live ops
317 : does the same rounds either way; the 8 lane kernel finishes them
318 : in half the vector work (a full win on cores that split 512-bit
319 : ops in two). Output is identical. */
320 1200061 : if( FD_LIKELY( op_cnt<=8UL ) ) {
321 878464 : fd_blake3_avx_compress8 ( op_cnt, batch_data, batch_data_sz, batch_ctr, batch_flags, fd_type_pun( batch_hash ), NULL, 32U, NULL );
322 878464 : } else {
323 321597 : fd_blake3_avx512_compress16( op_cnt, batch_data, batch_data_sz, batch_ctr, batch_flags, fd_type_pun( batch_hash ), NULL, 32U, NULL );
324 321597 : }
325 : #elif FD_HAS_AVX
326 2468510 : fd_blake3_avx_compress8 ( op_cnt, batch_data, batch_data_sz, batch_ctr, batch_flags, fd_type_pun( batch_hash ), NULL, 32U, NULL );
327 : #elif FD_HAS_SVE2
328 : fd_blake3_sve2_compress4 ( op_cnt, batch_data, batch_data_sz, batch_ctr, batch_flags, fd_type_pun( batch_hash ), 32U, NULL );
329 : #else
330 : #error "FIXME missing para support"
331 : #endif
332 3668571 : }
333 :
334 : #endif
335 :
336 : /* Simple API *********************************************************/
337 :
338 : ulong
339 516 : fd_blake3_align( void ) {
340 516 : return FD_BLAKE3_ALIGN;
341 516 : }
342 :
343 : ulong
344 198 : fd_blake3_footprint( void ) {
345 198 : return FD_BLAKE3_FOOTPRINT;
346 198 : }
347 :
348 : void *
349 201 : fd_blake3_new( void * shmem ) {
350 201 : fd_blake3_t * sha = (fd_blake3_t *)shmem;
351 :
352 201 : if( FD_UNLIKELY( !shmem ) ) {
353 3 : FD_LOG_WARNING(( "NULL shmem" ));
354 3 : return NULL;
355 3 : }
356 :
357 198 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmem, fd_blake3_align() ) ) ) {
358 3 : FD_LOG_WARNING(( "misaligned shmem" ));
359 3 : return NULL;
360 3 : }
361 :
362 195 : ulong footprint = fd_blake3_footprint();
363 :
364 195 : fd_memset( sha, 0, footprint );
365 :
366 195 : FD_COMPILER_MFENCE();
367 195 : FD_VOLATILE( sha->pos.magic ) = FD_BLAKE3_MAGIC;
368 195 : FD_COMPILER_MFENCE();
369 :
370 195 : return (void *)sha;
371 198 : }
372 :
373 : fd_blake3_t *
374 201 : fd_blake3_join( void * shsha ) {
375 :
376 201 : if( FD_UNLIKELY( !shsha ) ) {
377 3 : FD_LOG_WARNING(( "NULL shsha" ));
378 3 : return NULL;
379 3 : }
380 :
381 198 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shsha, fd_blake3_align() ) ) ) {
382 3 : FD_LOG_WARNING(( "misaligned shsha" ));
383 3 : return NULL;
384 3 : }
385 :
386 195 : fd_blake3_t * sha = (fd_blake3_t *)shsha;
387 :
388 195 : if( FD_UNLIKELY( sha->pos.magic!=FD_BLAKE3_MAGIC ) ) {
389 0 : FD_LOG_WARNING(( "bad magic" ));
390 0 : return NULL;
391 0 : }
392 :
393 195 : return sha;
394 195 : }
395 :
396 : void *
397 117 : fd_blake3_leave( fd_blake3_t * sha ) {
398 :
399 117 : if( FD_UNLIKELY( !sha ) ) {
400 3 : FD_LOG_WARNING(( "NULL sha" ));
401 3 : return NULL;
402 3 : }
403 :
404 114 : return (void *)sha;
405 117 : }
406 :
407 : void *
408 120 : fd_blake3_delete( void * shsha ) {
409 :
410 120 : if( FD_UNLIKELY( !shsha ) ) {
411 3 : FD_LOG_WARNING(( "NULL shsha" ));
412 3 : return NULL;
413 3 : }
414 :
415 117 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shsha, fd_blake3_align() ) ) ) {
416 3 : FD_LOG_WARNING(( "misaligned shsha" ));
417 3 : return NULL;
418 3 : }
419 :
420 114 : fd_blake3_t * sha = (fd_blake3_t *)shsha;
421 :
422 114 : if( FD_UNLIKELY( sha->pos.magic!=FD_BLAKE3_MAGIC ) ) {
423 0 : FD_LOG_WARNING(( "bad magic" ));
424 0 : return NULL;
425 0 : }
426 :
427 114 : FD_COMPILER_MFENCE();
428 114 : FD_VOLATILE( sha->pos.magic ) = 0UL;
429 114 : FD_COMPILER_MFENCE();
430 :
431 114 : return (void *)sha;
432 114 : }
433 :
434 :
435 : fd_blake3_t *
436 11565359 : fd_blake3_init( fd_blake3_t * sha ) {
437 11565359 : FD_BLAKE3_TRACE(( "fd_blake3_init(sha=%p)", (void *)sha ));
438 11565359 : fd_blake3_pos_init( &sha->pos, NULL, 0UL );
439 11565359 : sha->block_sz = 0UL;
440 11565359 : return sha;
441 11565359 : }
442 :
443 : #if FD_BLAKE3_PARA_MAX>1
444 :
445 : static void
446 : fd_blake3_append_blocks( fd_blake3_pos_t * s,
447 : fd_blake3_buf_t * tbl,
448 : uchar const * data,
449 531401 : ulong buf_cnt ) {
450 531401 : s->input = data - (s->leaf_idx << FD_BLAKE3_CHUNK_LG_SZ); /* TODO HACKY!! */
451 4666712 : for( ulong i=0UL; i<buf_cnt; i++ ) {
452 4135311 : fd_blake3_op_t op[1];
453 7368945 : do {
454 7368945 : if( !fd_blake3_prepare_fast( s, tbl, op, FD_BLAKE3_PARA_MAX, FD_BLAKE3_PARA_MAX ) )
455 0 : return;
456 1368727 : #if FD_HAS_AVX512
457 1368727 : fd_blake3_avx512_compress16_fast( op->msg, op->out, op->counter, op->flags );
458 : #elif FD_HAS_AVX
459 6000218 : fd_blake3_avx_compress8_fast( op->msg, op->out, op->counter, op->flags );
460 : #elif FD_HAS_SVE2
461 : fd_blake3_sve2_compress4_fast( op->msg, op->out, op->counter, op->flags );
462 : #else
463 : #error "missing para support"
464 : #endif
465 7368945 : } while( op->flags & FD_BLAKE3_FLAG_PARENT );
466 4135311 : }
467 531401 : }
468 :
469 : #else
470 :
471 : static void
472 : fd_blake3_append_blocks( fd_blake3_pos_t * s,
473 : fd_blake3_buf_t * tbl,
474 : uchar const * data,
475 : ulong buf_cnt ) {
476 : (void)buf_cnt;
477 : s->input = data - (s->leaf_idx << FD_BLAKE3_CHUNK_LG_SZ); /* TODO HACKY!! */
478 : fd_blake3_op_t op[1];
479 : while( buf_cnt ) {
480 : if( !fd_blake3_prepare( s, tbl, op, s->next_tick ) ) {
481 : FD_BLAKE3_TRACE(( "fd_blake3_append_blocks: no more ops to prepare" ));
482 : break;
483 : }
484 : if( op->flags & FD_BLAKE3_FLAG_PARENT ) {
485 : FD_BLAKE3_TRACE(( "fd_blake3_append_blocks: compressing output chaining values (layer %u)", s->layer ));
486 : fd_blake3_ref_compress1( op->out, op->msg, 64UL, op->counter, op->flags, NULL, NULL );
487 : } else {
488 : FD_BLAKE3_TRACE(( "fd_blake3_append_blocks: compressing %lu leaf chunks", FD_BLAKE3_COL_CNT ));
489 : fd_blake3_ref_compress1( op->out, op->msg, FD_BLAKE3_CHUNK_SZ, op->counter, op->flags, NULL, NULL );
490 : buf_cnt--;
491 : }
492 : s->next_tick++;
493 : }
494 : }
495 :
496 : #endif
497 :
498 : fd_blake3_t *
499 : fd_blake3_append( fd_blake3_t * sha,
500 : void const * _data,
501 15085124 : ulong sz ) {
502 :
503 : /* If no data to append, we are done */
504 :
505 15085124 : if( FD_UNLIKELY( !sz ) ) return sha;
506 15043347 : FD_BLAKE3_TRACE(( "fd_blake3_append(sha=%p,data=%p,sz=%lu)", (void *)sha, _data, sz ));
507 :
508 : /* Unpack inputs */
509 :
510 15043347 : fd_blake3_pos_t * s = &sha->pos;
511 15043347 : fd_blake3_buf_t * tbl = &sha->buf;
512 15043347 : uchar * buf = sha->block;
513 15043347 : ulong buf_used = sha->block_sz;
514 :
515 15043347 : uchar const * data = (uchar const *)_data;
516 :
517 : /* Update input_sz */
518 :
519 15043347 : s->input_sz += sz;
520 :
521 : /* Edge case: For the first completed 1024 bytes of input, don't
522 : immediately hash, since it is not clear whether this chunk has
523 : the root flag set. */
524 15043347 : if( FD_UNLIKELY( FD_BLAKE3_PARA_MAX==1 && s->input_sz==1024UL ) ) {
525 0 : fd_memcpy( buf + buf_used, data, sz );
526 0 : sha->block_sz = FD_BLAKE3_CHUNK_SZ;
527 0 : return sha;
528 0 : }
529 :
530 : /* Handle buffered bytes from previous appends */
531 :
532 15043347 : if( FD_UNLIKELY( buf_used ) ) { /* optimized for well aligned use of append */
533 :
534 : /* If the append isn't large enough to complete the current block,
535 : buffer these bytes too and return */
536 :
537 3483251 : ulong buf_rem = FD_BLAKE3_PRIVATE_BUF_MAX - buf_used; /* In (0,FD_BLAKE3_PRIVATE_BUF_MAX) */
538 3483251 : if( FD_UNLIKELY( sz < buf_rem ) ) { /* optimize for large append */
539 3286347 : fd_memcpy( buf + buf_used, data, sz );
540 3286347 : sha->block_sz = buf_used + sz;
541 3286347 : return sha;
542 3286347 : }
543 :
544 : /* Otherwise, buffer enough leading bytes of data to complete the
545 : block, update the hash and then continue processing any remaining
546 : bytes of data. */
547 :
548 196904 : fd_memcpy( buf + buf_used, data, buf_rem );
549 196904 : data += buf_rem;
550 196904 : sz -= buf_rem;
551 :
552 196904 : fd_blake3_append_blocks( s, tbl, buf, 1UL );
553 196904 : sha->block_sz = 0UL;
554 196904 : }
555 :
556 : /* Append the bulk of the data */
557 :
558 11757000 : ulong buf_cnt = sz >> FD_BLAKE3_PRIVATE_LG_BUF_MAX;
559 11757000 : if( FD_LIKELY( buf_cnt ) ) fd_blake3_append_blocks( s, tbl, data, buf_cnt ); /* optimized for large append */
560 :
561 : /* Buffer any leftover bytes */
562 :
563 11757000 : buf_used = sz & (FD_BLAKE3_PRIVATE_BUF_MAX-1UL); /* In [0,FD_BLAKE3_PRIVATE_BUF_MAX) */
564 11757000 : if( FD_UNLIKELY( buf_used ) ) { /* optimized for well aligned use of append */
565 11753605 : fd_memcpy( buf, data + (buf_cnt << FD_BLAKE3_PRIVATE_LG_BUF_MAX), buf_used );
566 11753605 : sha->block_sz = buf_used; /* In (0,FD_BLAKE3_PRIVATE_BUF_MAX) */
567 11753605 : }
568 :
569 11757000 : FD_BLAKE3_TRACE(( "fd_blake3_append: done" ));
570 11757000 : return sha;
571 15043347 : }
572 :
573 : static void const *
574 : fd_blake3_single_hash( fd_blake3_pos_t * s,
575 78870 : fd_blake3_buf_t * tbl ) {
576 78870 : #if FD_BLAKE3_PARA_MAX>1
577 78870 : ulong tick = 0UL;
578 924267 : while( !fd_blake3_is_finished( s, tick ) ) {
579 845397 : fd_blake3_op_t ops[ FD_BLAKE3_PARA_MAX ] = {0};
580 845397 : ulong op_cnt = 0UL;
581 4419147 : while( op_cnt<FD_BLAKE3_PARA_MAX ) {
582 4358373 : fd_blake3_op_t * op = &ops[ op_cnt ];
583 4358373 : if( !fd_blake3_prepare( s, tbl, op, tick ) )
584 784623 : break;
585 3573750 : op_cnt++;
586 3573750 : }
587 :
588 845397 : fd_blake3_batch_hash( ops, op_cnt );
589 845397 : tick++;
590 845397 : }
591 : #else
592 : while( !fd_blake3_is_finished( s, s->next_tick ) ) {
593 : fd_blake3_op_t op[1] = {0};
594 : if( !fd_blake3_prepare( s, tbl, op, s->next_tick ) )
595 : break;
596 : s->next_tick++;
597 : FD_BLAKE3_TRACE(( "fd_blake3_single_hash: compressing %hu bytes at layer %u, counter %lu, flags 0x%x",
598 : op->sz, s->layer, op->counter, op->flags ));
599 : # if FD_HAS_SSE
600 : fd_blake3_sse_compress1( op->out, op->msg, op->sz, op->counter, op->flags, NULL, NULL );
601 : # else
602 : fd_blake3_ref_compress1( op->out, op->msg, op->sz, op->counter, op->flags, NULL, NULL );
603 : # endif
604 : }
605 : #endif
606 78870 : return tbl->slots[ s->layer ][0];
607 78870 : }
608 :
609 : void *
610 : fd_blake3_fini( fd_blake3_t * sha,
611 52791 : void * hash ) {
612 :
613 : /* Unpack inputs */
614 :
615 52791 : fd_blake3_pos_t * s = &sha->pos;
616 52791 : fd_blake3_buf_t * tbl = &sha->buf;
617 52791 : uchar * buf = sha->block;
618 52791 : ulong buf_used = sha->block_sz;
619 52791 : FD_BLAKE3_TRACE(( "fd_blake3_fini(sha=%p,sz=%lu)", (void *)sha, s->input_sz ));
620 :
621 : /* TODO HACKY!! */
622 52791 : s->input = buf - ( s->leaf_idx << FD_BLAKE3_CHUNK_LG_SZ );
623 52791 : s->input_sz = ( s->leaf_idx << FD_BLAKE3_CHUNK_LG_SZ ) + buf_used;
624 :
625 52791 : void const * hash_ = fd_blake3_single_hash( s, tbl );
626 52791 : memcpy( hash, hash_, 32UL );
627 52791 : return hash;
628 52791 : }
629 :
630 : static void
631 11653421 : fd_blake3_fini_xof_setup( fd_blake3_t * sha ) {
632 11653421 : fd_blake3_pos_t * s = &sha->pos;
633 11653421 : uchar const * buf = sha->block;
634 :
635 : /* TODO HACKY!! */
636 11653421 : s->input = buf - ( s->leaf_idx << FD_BLAKE3_CHUNK_LG_SZ );
637 11653421 : s->input_sz = ( s->leaf_idx << FD_BLAKE3_CHUNK_LG_SZ ) + sha->block_sz;
638 11653421 : }
639 :
640 : #if FD_BLAKE3_PARA_MAX>1
641 :
642 : static ulong
643 : fd_blake3_fini_xof_prepare( fd_blake3_t * sha,
644 : fd_blake3_op_t * ops,
645 3931012 : ulong tick ) {
646 3931012 : fd_blake3_pos_t * s = &sha->pos;
647 :
648 3931012 : int l0_complete = fd_blake3_l0_complete( s );
649 3931012 : int ln_complete = s->live_cnt == 2UL;
650 3931012 : if( l0_complete & ln_complete ) return 0UL;
651 :
652 3110507 : ulong op_cnt = 0UL;
653 15992249 : while( op_cnt<FD_BLAKE3_PARA_MAX ) {
654 15739005 : if( !fd_blake3_prepare( s, &sha->buf, ops+op_cnt, tick ) ) break;
655 12881742 : op_cnt++;
656 12881742 : }
657 3110507 : if( FD_UNLIKELY( !op_cnt ) ) {
658 0 : FD_LOG_ERR(( "fd_blake3_fini_xof_compress invariant violation: failed to prepare branch compression with live_cnt=%lu (duplicate call to fini?)", s->live_cnt ));
659 0 : }
660 3110507 : return op_cnt;
661 3110507 : }
662 :
663 : #endif
664 :
665 : /* fd_blake3_fini_xof_compress performs BLAKE3 compression (input
666 : hashing) for all blocks in the hash tree except for the root block.
667 : Root compression inputs are returned via the function's out pointers:
668 : On return, root_msg[0..64] contains the padded message input for the
669 : root block, root_cv_pre[0..64] contains the output chaining value of
670 : the previous block (or the BLAKE3 IV if root block is the only block
671 : in the hash operation, i.e. <=64 byte hash input).
672 : Other values (counter, flags, size) are re-derived by the XOF
673 : implementation using the blake3 state object. */
674 :
675 : void
676 : fd_blake3_fini_xof_compress( fd_blake3_t * sha,
677 : uchar * root_msg,
678 11245181 : uchar * root_cv_pre ) {
679 11245181 : fd_blake3_pos_t * s = &sha->pos;
680 11245181 : fd_blake3_buf_t * tbl = &sha->buf;
681 :
682 11245181 : fd_blake3_fini_xof_setup( sha );
683 :
684 : /* The root block is contained in a leaf. Process all but the last
685 : blocks of the chunk. (The last block is the "root" block) */
686 11245181 : if( s->input_sz<=FD_BLAKE3_CHUNK_SZ ) {
687 10791530 : fd_blake3_op_t op[1];
688 10791530 : if( !fd_blake3_prepare_leaf( s, tbl, op, s->next_tick ) )
689 0 : FD_LOG_ERR(( "fd_blake3_fini_xof_compress invariant violation: failed to prepare compression of <=1024 byte message (duplicate call to fini?)" ));
690 10791530 : #if FD_HAS_SSE
691 10791530 : fd_blake3_sse_compress1( root_msg, op->msg, op->sz, op->counter, op->flags, root_cv_pre, NULL );
692 : #else
693 : fd_blake3_ref_compress1( root_msg, op->msg, op->sz, op->counter, op->flags, root_cv_pre, NULL );
694 : #endif
695 10791530 : return;
696 10791530 : }
697 :
698 : /* The root block is a branch node. Continue working until there are
699 : only two blocks remaining. */
700 453651 : ulong tick = sha->pos.next_tick+1;
701 2769951 : for(;;) {
702 2769951 : #if FD_BLAKE3_PARA_MAX>1
703 2769951 : fd_blake3_op_t ops[ FD_BLAKE3_PARA_MAX ] = {0};
704 2769951 : ulong op_cnt = fd_blake3_fini_xof_prepare( sha, ops, tick );
705 2769951 : if( !op_cnt ) break;
706 :
707 2316300 : fd_blake3_batch_hash( ops, op_cnt );
708 : #else
709 : int l0_complete = fd_blake3_l0_complete( s );
710 : int ln_complete = s->live_cnt == 2UL;
711 : if( l0_complete & ln_complete ) break;
712 :
713 : fd_blake3_op_t op[1] = {0};
714 : if( !fd_blake3_prepare( s, tbl, op, tick ) )
715 : break;
716 : # if FD_HAS_SSE
717 : fd_blake3_sse_compress1( op->out, op->msg, op->sz, op->counter, op->flags, NULL, NULL );
718 : # else
719 : fd_blake3_ref_compress1( op->out, op->msg, op->sz, op->counter, op->flags, NULL, NULL );
720 : # endif
721 : #endif
722 2316300 : tick++;
723 2316300 : }
724 453651 : }
725 :
726 : static void
727 : fd_blake3_fini_xof_expand( fd_blake3_t * sha,
728 : uchar * root_msg,
729 : uchar * root_cv_pre,
730 11512504 : void * hash ) {
731 :
732 : /* Restore root block details */
733 11512504 : uint last_block_sz = 64u;
734 11512504 : uint last_block_flags = FD_BLAKE3_FLAG_ROOT | FD_BLAKE3_FLAG_PARENT;
735 11512504 : ulong ctr0 = 0UL;
736 11512504 : if( sha->pos.input_sz<=FD_BLAKE3_CHUNK_SZ ) {
737 10791466 : last_block_sz = (uint)sha->pos.input_sz & 63u;
738 10791466 : if( fd_ulong_is_aligned( sha->pos.input_sz, 64 ) ) last_block_sz = 64;
739 10791466 : if( FD_UNLIKELY( sha->pos.input_sz==0UL ) ) last_block_sz = 0u;
740 10791466 : last_block_flags = FD_BLAKE3_FLAG_ROOT | FD_BLAKE3_FLAG_CHUNK_END;
741 10791466 : if( sha->pos.input_sz<=FD_BLAKE3_BLOCK_SZ ) last_block_flags |= FD_BLAKE3_FLAG_CHUNK_START;
742 10791466 : ctr0 = sha->pos.leaf_idx-1UL;
743 10791466 : } else {
744 721038 : fd_blake3_op_t op[1];
745 721038 : if( FD_UNLIKELY( !fd_blake3_prepare( &sha->pos, &sha->buf, op, sha->pos.next_tick+1UL ) ) ) {
746 0 : FD_LOG_ERR(( "fd_blake3_fini_2048 invariant violation: failed to prepare branch root compression (duplicate call to fini?)" ));
747 0 : }
748 721038 : memcpy( root_msg, op->msg, 64UL );
749 721038 : memcpy( root_cv_pre, FD_BLAKE3_IV, 32UL );
750 721038 : }
751 11512504 : FD_BLAKE3_TRACE(( "fd_blake3_fini_2048: sz=%lu ctr0=%lu flags=%x",
752 11512504 : sha->pos.input_sz, ctr0, last_block_flags ));
753 :
754 : /* Expand LtHash */
755 47746440 : for( ulong i=0UL; i<32UL; i+=FD_BLAKE3_PARA_MAX ) {
756 9816080 : #if FD_HAS_AVX512
757 9816080 : fd_blake3_avx512_xof16( root_msg, root_cv_pre, ctr0+i, last_block_sz, last_block_flags, (uchar *)hash + i*64UL );
758 : #elif FD_HAS_AVX
759 237760704 : ulong batch_data [ 8 ] __attribute__((aligned(32))); for( ulong j=0; j<8; j++ ) batch_data [ j ] = (ulong)root_msg;
760 237760704 : uint batch_sz [ 8 ] __attribute__((aligned(32))); for( ulong j=0; j<8; j++ ) batch_sz [ j ] = last_block_sz;
761 237760704 : ulong batch_ctr [ 8 ] __attribute__((aligned(32))); for( ulong j=0; j<8; j++ ) batch_ctr [ j ] = ctr0+i+j;
762 237760704 : uint batch_flags[ 8 ] __attribute__((aligned(32))); for( ulong j=0; j<8; j++ ) batch_flags[ j ] = last_block_flags;
763 237760704 : void * batch_hash [ 8 ] __attribute__((aligned(32))); for( ulong j=0; j<8; j++ ) batch_hash [ j ] = (uchar *)hash + (i+j)*64;
764 237760704 : void * batch_cv [ 8 ] __attribute__((aligned(32))); for( ulong j=0; j<8; j++ ) batch_cv [ j ] = root_cv_pre;
765 26417856 : fd_blake3_avx_compress8( 8UL, batch_data, batch_sz, batch_ctr, batch_flags, batch_hash, NULL, 64U, batch_cv );
766 : #elif FD_HAS_SVE2
767 : fd_blake3_sve2_xof4( root_msg, root_cv_pre, ctr0+i, last_block_sz, last_block_flags, (uchar *)hash + i*64UL );
768 : #elif FD_HAS_SSE
769 : fd_blake3_sse_compress1( (uchar *)hash+i*64, root_msg, last_block_sz, ctr0+i, last_block_flags, NULL, root_cv_pre );
770 : #else
771 : fd_blake3_ref_compress1( (uchar *)hash+i*64, root_msg, last_block_sz, ctr0+i, last_block_flags, NULL, root_cv_pre );
772 : #endif
773 36233936 : }
774 11512504 : }
775 :
776 : void *
777 : fd_blake3_fini_2048( fd_blake3_t * sha,
778 11245117 : void * hash ) {
779 11245117 : FD_BLAKE3_TRACE(( "fd_blake3_fini_2048(sha=%p,hash=%p)", (void *)sha, hash ));
780 :
781 11245117 : uchar root_msg [ 64 ] __attribute__((aligned(64)));
782 11245117 : uchar root_cv_pre[ 32 ] __attribute__((aligned(32)));
783 11245117 : fd_blake3_fini_xof_compress( sha, root_msg, root_cv_pre );
784 11245117 : fd_blake3_fini_xof_expand( sha, root_msg, root_cv_pre, hash );
785 :
786 11245117 : FD_BLAKE3_TRACE(( "fd_blake3_fini_2048: done" ));
787 11245117 : return hash;
788 11245117 : }
789 :
790 : void
791 : fd_blake3_fini_2048_xn( ulong n,
792 : fd_blake3_t ** sha,
793 195498 : void ** hash ) {
794 195498 : #if FD_BLAKE3_PARA_MAX>1
795 195498 : int single = 0;
796 603738 : for( ulong i=0UL; i<n; i++ ) {
797 408240 : fd_blake3_fini_xof_setup( sha[ i ] );
798 408240 : single |= sha[ i ]->pos.input_sz<=FD_BLAKE3_CHUNK_SZ;
799 408240 : }
800 :
801 195498 : if( FD_UNLIKELY( single ) ) {
802 208023 : for( ulong i=0UL; i<n; i++ ) fd_blake3_fini_2048( sha[ i ], hash[ i ] );
803 67170 : return;
804 67170 : }
805 :
806 128328 : ulong tick[ FD_BLAKE3_XN_MAX ];
807 395715 : for( ulong i=0UL; i<n; i++ ) tick[ i ] = sha[ i ]->pos.next_tick+1UL;
808 554274 : for(;;) {
809 554274 : fd_blake3_op_t ops[ FD_BLAKE3_XN_MAX*FD_BLAKE3_PARA_MAX ];
810 554274 : ulong op_cnt = 0UL;
811 1715335 : for( ulong i=0UL; i<n; i++ ) op_cnt += fd_blake3_fini_xof_prepare( sha[ i ], ops+op_cnt, tick[ i ]++ );
812 554274 : if( !op_cnt ) break;
813 :
814 932820 : for( ulong off=0UL; off<op_cnt; off+=FD_BLAKE3_PARA_MAX ) {
815 506874 : fd_blake3_batch_hash( ops+off, fd_ulong_min( op_cnt-off, FD_BLAKE3_PARA_MAX ) );
816 506874 : }
817 425946 : }
818 :
819 128328 : uchar root_msg [ 64 ] __attribute__((aligned(64)));
820 128328 : uchar root_cv_pre[ 32 ] __attribute__((aligned(32)));
821 395715 : for( ulong i=0UL; i<n; i++ ) fd_blake3_fini_xof_expand( sha[ i ], root_msg, root_cv_pre, hash[ i ] );
822 : #else
823 : for( ulong i=0UL; i<n; i++ ) fd_blake3_fini_2048( sha[ i ], hash[ i ] );
824 : #endif
825 128328 : }
826 :
827 : void *
828 : fd_blake3_hash( void const * data,
829 : ulong sz,
830 26079 : void * hash ) {
831 :
832 26079 : fd_blake3_buf_t tbl[1];
833 26079 : fd_blake3_pos_t s[1];
834 26079 : fd_blake3_pos_init( s, data, sz );
835 :
836 26079 : #if FD_BLAKE3_PARA_MAX>1
837 1303641 : for(;;) {
838 1303641 : fd_blake3_op_t op[1];
839 1303641 : if( !fd_blake3_prepare_fast( s, tbl, op, FD_BLAKE3_PARA_MAX, FD_BLAKE3_PARA_MAX ) )
840 26079 : break;
841 245228 : #if FD_HAS_AVX512
842 245228 : fd_blake3_avx512_compress16_fast( op->msg, op->out, op->counter, op->flags );
843 : #elif FD_HAS_AVX
844 1032334 : fd_blake3_avx_compress8_fast( op->msg, op->out, op->counter, op->flags );
845 : #elif FD_HAS_SVE2
846 : fd_blake3_sve2_compress4_fast( op->msg, op->out, op->counter, op->flags );
847 : #else
848 : #error "missing para support"
849 : #endif
850 1277562 : }
851 26079 : #endif
852 :
853 26079 : void const * hash_ = fd_blake3_single_hash( s, tbl );
854 26079 : memcpy( hash, hash_, 32UL );
855 26079 : return hash;
856 26079 : }
857 :
858 : #if FD_HAS_AVX
859 :
860 : void
861 : fd_blake3_lthash_batch8(
862 : void const * batch_data[8], /* align=32 ele_align=1 */
863 : uint const batch_sz [8], /* align=32 */
864 : void * out_lthash /* align=32 */
865 1378478 : ) {
866 1378478 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)batch_data, 32 ) ) ) {
867 0 : FD_LOG_ERR(( "misaligned batch_data: %p", (void *)batch_data ));
868 0 : }
869 1378478 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)batch_sz, 32 ) ) ) {
870 0 : FD_LOG_ERR(( "misaligned batch_sz: %p", (void *)batch_sz ));
871 0 : }
872 1378478 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)out_lthash, 32 ) ) ) {
873 0 : FD_LOG_ERR(( "misaligned out_lthash: %p", (void *)out_lthash ));
874 0 : }
875 :
876 1378478 : ulong batch_ctr [ 8 ] = {0};
877 12406302 : uint batch_flags[ 8 ]; for( uint i=0; i<8; i++ ) batch_flags[ i ] = FD_BLAKE3_FLAG_ROOT;
878 1378478 : fd_blake3_avx_compress8( 8UL, batch_data, batch_sz, batch_ctr, batch_flags, NULL, out_lthash, 32U, NULL );
879 1378478 : }
880 :
881 : #endif
882 :
883 : #if FD_HAS_AVX512
884 :
885 : void
886 : fd_blake3_lthash_batch16(
887 : void const * batch_data[16], /* align=64 ele_align=1 */
888 : uint const batch_sz [16], /* align=64 */
889 : void * out_lthash /* align=64 */
890 369256 : ) {
891 369256 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)batch_data, 64 ) ) ) {
892 0 : FD_LOG_ERR(( "misaligned batch_data: %p", (void *)batch_data ));
893 0 : }
894 369256 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)batch_sz, 64 ) ) ) {
895 0 : FD_LOG_ERR(( "misaligned batch_sz: %p", (void *)batch_sz ));
896 0 : }
897 369256 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)out_lthash, 64 ) ) ) {
898 0 : FD_LOG_ERR(( "misaligned out_lthash: %p", (void *)out_lthash ));
899 0 : }
900 :
901 369256 : ulong batch_ctr [ 16 ] = {0};
902 6277352 : uint batch_flags[ 16 ]; for( uint i=0; i<16; i++ ) batch_flags[ i ] = FD_BLAKE3_FLAG_ROOT;
903 369256 : fd_blake3_avx512_compress16( 16UL, batch_data, batch_sz, batch_ctr, batch_flags, NULL, out_lthash, 32U, NULL );
904 369256 : }
905 :
906 : #endif
|
