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 8619 : ulong sz ) {
10 8619 : *s = (fd_blake3_pos_t) {
11 8619 : .input = data,
12 8619 : .input_sz = sz,
13 8619 : .magic = FD_BLAKE3_MAGIC,
14 8619 : };
15 8619 : return s;
16 8619 : }
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 341302 : fd_blake3_l0_complete( fd_blake3_pos_t const * s ) {
23 341302 : return ( s->leaf_idx<<FD_BLAKE3_CHUNK_LG_SZ ) >= fd_ulong_max( s->input_sz, 64 );
24 341302 : }
25 :
26 : FD_FN_PURE static inline int
27 : fd_blake3_is_finished( fd_blake3_pos_t const * s,
28 148274 : ulong tick ) {
29 148274 : int l0_complete = fd_blake3_l0_complete( s );
30 148274 : int ln_complete = s->live_cnt == 1UL;
31 148274 : int idle = tick >= s->next_tick;
32 148274 : return l0_complete & ln_complete & idle;
33 148274 : }
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 21530 : ulong tick ) {
40 :
41 21530 : ulong msg_off = s->leaf_idx << FD_BLAKE3_CHUNK_LG_SZ;
42 21530 : ulong msg_sz = fd_ulong_min( s->input_sz - msg_off, 1024UL );
43 21530 : uchar const * msg = s->input + msg_off;
44 21530 : uchar * out = buf->slots[ s->layer ][ s->head.uc[ s->layer ] ];
45 :
46 21530 : int flags = fd_int_if( s->input_sz <= FD_BLAKE3_CHUNK_SZ, FD_BLAKE3_FLAG_ROOT, 0 );
47 :
48 21530 : *op = (fd_blake3_op_t) {
49 21530 : .msg = msg,
50 21530 : .out = out,
51 21530 : .counter = s->leaf_idx,
52 21530 : .sz = (ushort)msg_sz,
53 21530 : .flags = (uchar)flags
54 21530 : };
55 :
56 21530 : s->head.uc[ 0 ] = (uchar)( s->head.uc[ 0 ]+1 );
57 21530 : s->leaf_idx++;
58 21530 : s->live_cnt++;
59 21530 : s->next_tick = tick+1;
60 :
61 21530 : return op;
62 :
63 21530 : }
64 :
65 : static int
66 : fd_blake3_seek_branch( fd_blake3_pos_t * restrict s,
67 : fd_blake3_buf_t * restrict buf,
68 126255 : ulong tick ) {
69 :
70 126255 : if( s->live_cnt == 1UL )
71 0 : return 0;
72 :
73 126255 : if( !fd_blake3_l0_complete( s ) )
74 58821 : return ( s->tail.uc[ s->layer - 1 ] + 1 ) <
75 58821 : ( s->head.uc[ s->layer - 1 ] );
76 :
77 67434 : # if FD_HAS_AVX
78 :
79 67434 : wb_t diff = wb_sub( wb_ld( s->head.uc ), wb_ld( s->tail.uc ) );
80 :
81 67434 : uint mergeable_layers = (uint)_mm256_movemask_epi8( wb_gt( diff, wb_bcast( 1 ) ) );
82 67434 : int merge_layer = fd_uint_find_lsb_w_default( mergeable_layers, -1 );
83 67434 : if( merge_layer>=0 ) {
84 58984 : if( ((uint)merge_layer >= s->layer) & (tick < s->next_tick) )
85 9726 : return 0; /* still waiting for previous merge */
86 49258 : s->layer = (uint)merge_layer+1U;
87 49258 : return 1;
88 58984 : }
89 :
90 8450 : uint single_layers = (uint)_mm256_movemask_epi8( wb_eq( diff, wb_bcast( 1 ) ) );
91 8450 : uint single_lo = (uint)fd_uint_find_lsb( single_layers );
92 8450 : uint single_hi = (uint)fd_uint_find_lsb( single_layers & ( ~fd_uint_mask_lsb( (int)(single_lo+1U) ) ) );
93 :
94 8450 : wb_t node = wb_ld( buf->slots[ single_lo ][ s->tail.uc[ single_lo ] ] );
95 8450 : 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 8450 : FD_BLAKE3_TRACE(( "fd_blake3_seek_branch: moving up %u/%u to %u/%u",
140 8450 : single_lo, s->tail.uc[ single_lo ],
141 8450 : single_hi, s->head.uc[ single_hi ] ));
142 :
143 8450 : if( ((uint)single_hi >= s->layer) & (tick < s->next_tick) )
144 3667 : return 0; /* still waiting for previous merge */
145 :
146 4783 : s->head.uc[ single_lo ] = (uchar)( s->head.uc[ single_lo ]-1 );
147 4783 : s->head.uc[ single_hi ] = (uchar)( s->head.uc[ single_hi ]+1 );
148 :
149 4783 : s->layer = (uint)single_hi+1U;
150 4783 : return 1;
151 8450 : }
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 126252 : ulong tick ) {
158 :
159 126252 : if( !fd_blake3_seek_branch( s, buf, tick ) )
160 13389 : return NULL;
161 :
162 112863 : FD_DCHECK_CRIT( s->layer < FD_BLAKE3_ROW_CNT, "invariant violation" );
163 :
164 112863 : uchar const * msg = buf->slots[ s->layer-1U ][ s->tail.uc[ s->layer-1U ] ];
165 112863 : uchar * out = buf->slots[ s->layer ][ s->head.uc[ s->layer ] ];
166 :
167 112863 : s->head.uc[ s->layer ] = (uchar)( s->head.uc[ s->layer ]+1 );
168 112863 : s->tail.uc[ s->layer-1 ] = (uchar)( s->tail.uc[ s->layer-1 ]+2 );
169 112863 : s->live_cnt--;
170 112863 : s->next_tick = tick+1;
171 :
172 112863 : uint flags = FD_BLAKE3_FLAG_PARENT |
173 112863 : fd_uint_if( s->live_cnt==1UL, FD_BLAKE3_FLAG_ROOT, 0u );
174 :
175 112863 : *op = (fd_blake3_op_t) {
176 112863 : .msg = msg,
177 112863 : .out = out,
178 112863 : .counter = 0UL,
179 112863 : .sz = 64U,
180 112863 : .flags = (uchar)flags
181 112863 : };
182 112863 : return op;
183 :
184 126252 : }
185 :
186 : static void
187 26298 : fd_blake3_advance( fd_blake3_pos_t * restrict s ) {
188 :
189 26298 : # if FD_HAS_AVX
190 :
191 26298 : wb_t tail = wb_ld( s->tail.uc );
192 26298 : wb_t head = wb_ld( s->head.uc );
193 26298 : wb_t mask = wb_eq( tail, head );
194 26298 : wb_st( s->tail.uc, wb_andnot( mask, tail ) );
195 26298 : 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 26298 : if( s->head.uc[ s->layer ]==FD_BLAKE3_COL_CNT ) {
209 2450 : s->layer++;
210 2450 : }
211 23848 : else if( ( s->layer > 0UL ) &&
212 23848 : ( s->tail.uc[ s->layer-1 ] < s->head.uc[ s->layer-1 ] ) ) {
213 : /* pass */
214 4897 : }
215 18951 : else if( fd_blake3_l0_complete( s ) ) {
216 14345 : s->layer++;
217 14345 : }
218 4606 : else if( s->layer > 0UL ) {
219 1228 : s->layer = 0UL;
220 1228 : }
221 :
222 26298 : }
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 148288 : ulong tick ) {
229 :
230 148288 : FD_DCHECK_CRIT( s->layer < FD_BLAKE3_ROW_CNT, "invariant violation" );
231 :
232 148288 : if( fd_blake3_is_finished( s, tick ) )
233 0 : return NULL;
234 :
235 148288 : if( tick >= s->next_tick )
236 26300 : fd_blake3_advance( s );
237 :
238 148288 : if( s->layer != 0 )
239 126262 : return fd_blake3_prepare_branch( s, buf, op, tick );
240 :
241 22026 : if( ( s->head.uc[0] >= FD_BLAKE3_COL_CNT ) |
242 22026 : ( fd_blake3_l0_complete( s ) ) ) {
243 4636 : return NULL;
244 4636 : }
245 :
246 17390 : return fd_blake3_prepare_leaf( s, buf, op, tick );
247 :
248 22026 : }
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 16094 : ulong min ) {
261 :
262 16094 : if( s->layer && s->head.uc[ s->layer-1 ]==FD_BLAKE3_COL_CNT ) {
263 4916 : op->msg = buf->rows[ s->layer-1 ];
264 4916 : op->out = buf->rows[ s->layer ] + (s->head.uc[ s->layer ]<<FD_BLAKE3_OUTCHAIN_LG_SZ);
265 4916 : op->counter = 0UL;
266 4916 : op->flags = FD_BLAKE3_FLAG_PARENT;
267 :
268 : /* Assume that branch layer is fully hashed (up to col cnt) */
269 4916 : s->head.uc[ s->layer-1 ] = 0;
270 4916 : s->head.uc[ s->layer ] = (uchar)( (ulong)s->head.uc[ s->layer ]+n );
271 4916 : s->live_cnt -= n;
272 4916 : s->layer = fd_uint_if( s->head.uc[ s->layer ]==FD_BLAKE3_COL_CNT,
273 4916 : s->layer+1U, 0U );
274 :
275 4916 : return op;
276 4916 : }
277 :
278 11178 : ulong pos = s->leaf_idx << FD_BLAKE3_CHUNK_LG_SZ;
279 11178 : ulong avail = fd_ulong_align_dn( s->input_sz - pos, FD_BLAKE3_CHUNK_SZ ) >> FD_BLAKE3_CHUNK_LG_SZ;
280 11178 : 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 11178 : if( n<min ) return NULL;
286 :
287 11178 : op->msg = s->input + (s->leaf_idx<<FD_BLAKE3_CHUNK_LG_SZ);
288 11178 : op->out = buf->rows[0] + (s->head.uc[0]<<FD_BLAKE3_OUTCHAIN_LG_SZ);
289 11178 : op->counter = s->leaf_idx;
290 11178 : op->flags = 0;
291 :
292 11178 : s->head.uc[0] = (uchar)( (ulong)s->head.uc[0]+n );
293 11178 : s->leaf_idx += n;
294 11178 : s->live_cnt += n;
295 11178 : s->layer = fd_uint_if( s->head.uc[0]==FD_BLAKE3_COL_CNT, 1U, 0U );
296 :
297 11178 : return op;
298 11178 : }
299 :
300 : static void
301 : fd_blake3_batch_hash( fd_blake3_op_t const * ops,
302 19437 : ulong op_cnt ) {
303 19437 : uchar const * batch_data [ FD_BLAKE3_PARA_MAX ] __attribute__((aligned(64)));
304 19437 : uint batch_data_sz[ FD_BLAKE3_PARA_MAX ] = {0};
305 19437 : uchar * batch_hash [ FD_BLAKE3_PARA_MAX ] __attribute__((aligned(64)));
306 19437 : ulong batch_ctr [ FD_BLAKE3_PARA_MAX ];
307 19437 : uint batch_flags [ FD_BLAKE3_PARA_MAX ];
308 145495 : for( ulong j=0UL; j<op_cnt; j++ ) {
309 126058 : batch_data [ j ] = ops[ j ].msg;
310 126058 : batch_hash [ j ] = ops[ j ].out;
311 126058 : batch_data_sz[ j ] = ops[ j ].sz;
312 126058 : batch_ctr [ j ] = ops[ j ].counter;
313 126058 : batch_flags [ j ] = ops[ j ].flags;
314 126058 : }
315 19437 : #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 19437 : if( FD_LIKELY( op_cnt<=8UL ) ) {
321 13997 : fd_blake3_avx_compress8 ( op_cnt, batch_data, batch_data_sz, batch_ctr, batch_flags, fd_type_pun( batch_hash ), NULL, 32U, NULL );
322 13997 : } else {
323 5440 : fd_blake3_avx512_compress16( op_cnt, batch_data, batch_data_sz, batch_ctr, batch_flags, fd_type_pun( batch_hash ), NULL, 32U, NULL );
324 5440 : }
325 : #elif FD_HAS_AVX
326 : 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 19437 : }
333 :
334 : #endif
335 :
336 : /* Simple API *********************************************************/
337 :
338 : ulong
339 0 : fd_blake3_align( void ) {
340 0 : return FD_BLAKE3_ALIGN;
341 0 : }
342 :
343 : ulong
344 0 : fd_blake3_footprint( void ) {
345 0 : return FD_BLAKE3_FOOTPRINT;
346 0 : }
347 :
348 : void *
349 0 : fd_blake3_new( void * shmem ) {
350 0 : fd_blake3_t * sha = (fd_blake3_t *)shmem;
351 :
352 0 : if( FD_UNLIKELY( !shmem ) ) {
353 0 : FD_LOG_WARNING(( "NULL shmem" ));
354 0 : return NULL;
355 0 : }
356 :
357 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmem, fd_blake3_align() ) ) ) {
358 0 : FD_LOG_WARNING(( "misaligned shmem" ));
359 0 : return NULL;
360 0 : }
361 :
362 0 : ulong footprint = fd_blake3_footprint();
363 :
364 0 : fd_memset( sha, 0, footprint );
365 :
366 0 : FD_COMPILER_MFENCE();
367 0 : FD_VOLATILE( sha->pos.magic ) = FD_BLAKE3_MAGIC;
368 0 : FD_COMPILER_MFENCE();
369 :
370 0 : return (void *)sha;
371 0 : }
372 :
373 : fd_blake3_t *
374 0 : fd_blake3_join( void * shsha ) {
375 :
376 0 : if( FD_UNLIKELY( !shsha ) ) {
377 0 : FD_LOG_WARNING(( "NULL shsha" ));
378 0 : return NULL;
379 0 : }
380 :
381 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shsha, fd_blake3_align() ) ) ) {
382 0 : FD_LOG_WARNING(( "misaligned shsha" ));
383 0 : return NULL;
384 0 : }
385 :
386 0 : fd_blake3_t * sha = (fd_blake3_t *)shsha;
387 :
388 0 : if( FD_UNLIKELY( sha->pos.magic!=FD_BLAKE3_MAGIC ) ) {
389 0 : FD_LOG_WARNING(( "bad magic" ));
390 0 : return NULL;
391 0 : }
392 :
393 0 : return sha;
394 0 : }
395 :
396 : void *
397 0 : fd_blake3_leave( fd_blake3_t * sha ) {
398 :
399 0 : if( FD_UNLIKELY( !sha ) ) {
400 0 : FD_LOG_WARNING(( "NULL sha" ));
401 0 : return NULL;
402 0 : }
403 :
404 0 : return (void *)sha;
405 0 : }
406 :
407 : void *
408 0 : fd_blake3_delete( void * shsha ) {
409 :
410 0 : if( FD_UNLIKELY( !shsha ) ) {
411 0 : FD_LOG_WARNING(( "NULL shsha" ));
412 0 : return NULL;
413 0 : }
414 :
415 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shsha, fd_blake3_align() ) ) ) {
416 0 : FD_LOG_WARNING(( "misaligned shsha" ));
417 0 : return NULL;
418 0 : }
419 :
420 0 : fd_blake3_t * sha = (fd_blake3_t *)shsha;
421 :
422 0 : if( FD_UNLIKELY( sha->pos.magic!=FD_BLAKE3_MAGIC ) ) {
423 0 : FD_LOG_WARNING(( "bad magic" ));
424 0 : return NULL;
425 0 : }
426 :
427 0 : FD_COMPILER_MFENCE();
428 0 : FD_VOLATILE( sha->pos.magic ) = 0UL;
429 0 : FD_COMPILER_MFENCE();
430 :
431 0 : return (void *)sha;
432 0 : }
433 :
434 :
435 : fd_blake3_t *
436 8619 : fd_blake3_init( fd_blake3_t * sha ) {
437 8619 : FD_BLAKE3_TRACE(( "fd_blake3_init(sha=%p)", (void *)sha ));
438 8619 : fd_blake3_pos_init( &sha->pos, NULL, 0UL );
439 8619 : sha->block_sz = 0UL;
440 8619 : return sha;
441 8619 : }
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 3813 : ulong buf_cnt ) {
450 3813 : s->input = data - (s->leaf_idx << FD_BLAKE3_CHUNK_LG_SZ); /* TODO HACKY!! */
451 14994 : for( ulong i=0UL; i<buf_cnt; i++ ) {
452 11181 : fd_blake3_op_t op[1];
453 16098 : do {
454 16098 : if( !fd_blake3_prepare_fast( s, tbl, op, FD_BLAKE3_PARA_MAX, FD_BLAKE3_PARA_MAX ) )
455 0 : return;
456 16098 : #if FD_HAS_AVX512
457 16098 : fd_blake3_avx512_compress16_fast( op->msg, op->out, op->counter, op->flags );
458 : #elif FD_HAS_AVX
459 : 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 16098 : } while( op->flags & FD_BLAKE3_FLAG_PARENT );
466 11181 : }
467 3813 : }
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 41901 : ulong sz ) {
502 :
503 : /* If no data to append, we are done */
504 :
505 41901 : if( FD_UNLIKELY( !sz ) ) return sha;
506 40364 : FD_BLAKE3_TRACE(( "fd_blake3_append(sha=%p,data=%p,sz=%lu)", (void *)sha, _data, sz ));
507 :
508 : /* Unpack inputs */
509 :
510 40364 : fd_blake3_pos_t * s = &sha->pos;
511 40364 : fd_blake3_buf_t * tbl = &sha->buf;
512 40364 : uchar * buf = sha->block;
513 40364 : ulong buf_used = sha->block_sz;
514 :
515 40364 : uchar const * data = (uchar const *)_data;
516 :
517 : /* Update input_sz */
518 :
519 40364 : 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 40364 : 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 40364 : 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 31797 : ulong buf_rem = FD_BLAKE3_PRIVATE_BUF_MAX - buf_used; /* In (0,FD_BLAKE3_PRIVATE_BUF_MAX) */
538 31797 : if( FD_UNLIKELY( sz < buf_rem ) ) { /* optimize for large append */
539 29216 : fd_memcpy( buf + buf_used, data, sz );
540 29216 : sha->block_sz = buf_used + sz;
541 29216 : return sha;
542 29216 : }
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 2581 : fd_memcpy( buf + buf_used, data, buf_rem );
549 2581 : data += buf_rem;
550 2581 : sz -= buf_rem;
551 :
552 2581 : fd_blake3_append_blocks( s, tbl, buf, 1UL );
553 2581 : sha->block_sz = 0UL;
554 2581 : }
555 :
556 : /* Append the bulk of the data */
557 :
558 11148 : ulong buf_cnt = sz >> FD_BLAKE3_PRIVATE_LG_BUF_MAX;
559 11148 : 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 11148 : buf_used = sz & (FD_BLAKE3_PRIVATE_BUF_MAX-1UL); /* In [0,FD_BLAKE3_PRIVATE_BUF_MAX) */
564 11207 : if( FD_UNLIKELY( buf_used ) ) { /* optimized for well aligned use of append */
565 11207 : fd_memcpy( buf, data + (buf_cnt << FD_BLAKE3_PRIVATE_LG_BUF_MAX), buf_used );
566 11207 : sha->block_sz = buf_used; /* In (0,FD_BLAKE3_PRIVATE_BUF_MAX) */
567 11207 : }
568 :
569 11148 : FD_BLAKE3_TRACE(( "fd_blake3_append: done" ));
570 11148 : return sha;
571 40364 : }
572 :
573 : static void const *
574 : fd_blake3_single_hash( fd_blake3_pos_t * s,
575 0 : fd_blake3_buf_t * tbl ) {
576 0 : #if FD_BLAKE3_PARA_MAX>1
577 0 : ulong tick = 0UL;
578 0 : while( !fd_blake3_is_finished( s, tick ) ) {
579 0 : fd_blake3_op_t ops[ FD_BLAKE3_PARA_MAX ] = {0};
580 0 : ulong op_cnt = 0UL;
581 0 : while( op_cnt<FD_BLAKE3_PARA_MAX ) {
582 0 : fd_blake3_op_t * op = &ops[ op_cnt ];
583 0 : if( !fd_blake3_prepare( s, tbl, op, tick ) )
584 0 : break;
585 0 : op_cnt++;
586 0 : }
587 :
588 0 : fd_blake3_batch_hash( ops, op_cnt );
589 0 : tick++;
590 0 : }
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 0 : return tbl->slots[ s->layer ][0];
607 0 : }
608 :
609 : void *
610 : fd_blake3_fini( fd_blake3_t * sha,
611 0 : void * hash ) {
612 :
613 : /* Unpack inputs */
614 :
615 0 : fd_blake3_pos_t * s = &sha->pos;
616 0 : fd_blake3_buf_t * tbl = &sha->buf;
617 0 : uchar * buf = sha->block;
618 0 : ulong buf_used = sha->block_sz;
619 0 : FD_BLAKE3_TRACE(( "fd_blake3_fini(sha=%p,sz=%lu)", (void *)sha, s->input_sz ));
620 :
621 : /* TODO HACKY!! */
622 0 : s->input = buf - ( s->leaf_idx << FD_BLAKE3_CHUNK_LG_SZ );
623 0 : s->input_sz = ( s->leaf_idx << FD_BLAKE3_CHUNK_LG_SZ ) + buf_used;
624 :
625 0 : void const * hash_ = fd_blake3_single_hash( s, tbl );
626 0 : memcpy( hash, hash_, 32UL );
627 0 : return hash;
628 0 : }
629 :
630 : static void
631 11753 : fd_blake3_fini_xof_setup( fd_blake3_t * sha ) {
632 11753 : fd_blake3_pos_t * s = &sha->pos;
633 11753 : uchar const * buf = sha->block;
634 :
635 : /* TODO HACKY!! */
636 11753 : s->input = buf - ( s->leaf_idx << FD_BLAKE3_CHUNK_LG_SZ );
637 11753 : s->input_sz = ( s->leaf_idx << FD_BLAKE3_CHUNK_LG_SZ ) + sha->block_sz;
638 11753 : }
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 26484 : ulong tick ) {
646 26484 : fd_blake3_pos_t * s = &sha->pos;
647 :
648 26484 : int l0_complete = fd_blake3_l0_complete( s );
649 26484 : int ln_complete = s->live_cnt == 2UL;
650 26484 : if( l0_complete & ln_complete ) return 0UL;
651 :
652 21661 : ulong op_cnt = 0UL;
653 147343 : while( op_cnt<FD_BLAKE3_PARA_MAX ) {
654 143702 : if( !fd_blake3_prepare( s, &sha->buf, ops+op_cnt, tick ) ) break;
655 125682 : op_cnt++;
656 125682 : }
657 21661 : 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 21661 : return op_cnt;
661 21661 : }
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 6739 : uchar * root_cv_pre ) {
679 6739 : fd_blake3_pos_t * s = &sha->pos;
680 6739 : fd_blake3_buf_t * tbl = &sha->buf;
681 :
682 6739 : 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 6739 : if( s->input_sz<=FD_BLAKE3_CHUNK_SZ ) {
687 3984 : fd_blake3_op_t op[1];
688 3984 : 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 3984 : #if FD_HAS_SSE
691 3984 : 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 3984 : return;
696 3984 : }
697 :
698 : /* The root block is a branch node. Continue working until there are
699 : only two blocks remaining. */
700 2755 : ulong tick = sha->pos.next_tick+1;
701 19728 : for(;;) {
702 19728 : #if FD_BLAKE3_PARA_MAX>1
703 19728 : fd_blake3_op_t ops[ FD_BLAKE3_PARA_MAX ] = {0};
704 19728 : ulong op_cnt = fd_blake3_fini_xof_prepare( sha, ops, tick );
705 19728 : if( !op_cnt ) break;
706 :
707 16975 : 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 16975 : tick++;
723 16975 : }
724 2755 : }
725 :
726 : static void
727 : fd_blake3_fini_xof_expand( fd_blake3_t * sha,
728 : uchar * root_msg,
729 : uchar * root_cv_pre,
730 8622 : void * hash ) {
731 :
732 : /* Restore root block details */
733 8622 : uint last_block_sz = 64u;
734 8622 : uint last_block_flags = FD_BLAKE3_FLAG_ROOT | FD_BLAKE3_FLAG_PARENT;
735 8622 : ulong ctr0 = 0UL;
736 8622 : if( sha->pos.input_sz<=FD_BLAKE3_CHUNK_SZ ) {
737 3988 : last_block_sz = (uint)sha->pos.input_sz & 63u;
738 3988 : if( fd_ulong_is_aligned( sha->pos.input_sz, 64 ) ) last_block_sz = 64;
739 3988 : if( FD_UNLIKELY( sha->pos.input_sz==0UL ) ) last_block_sz = 0u;
740 3988 : last_block_flags = FD_BLAKE3_FLAG_ROOT | FD_BLAKE3_FLAG_CHUNK_END;
741 3988 : if( sha->pos.input_sz<=FD_BLAKE3_BLOCK_SZ ) last_block_flags |= FD_BLAKE3_FLAG_CHUNK_START;
742 3988 : ctr0 = sha->pos.leaf_idx-1UL;
743 4634 : } else {
744 4634 : fd_blake3_op_t op[1];
745 4634 : 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 4634 : memcpy( root_msg, op->msg, 64UL );
749 4634 : memcpy( root_cv_pre, FD_BLAKE3_IV, 32UL );
750 4634 : }
751 8622 : FD_BLAKE3_TRACE(( "fd_blake3_fini_2048: sz=%lu ctr0=%lu flags=%x",
752 8622 : sha->pos.input_sz, ctr0, last_block_flags ));
753 :
754 : /* Expand LtHash */
755 25830 : for( ulong i=0UL; i<32UL; i+=FD_BLAKE3_PARA_MAX ) {
756 17208 : #if FD_HAS_AVX512
757 17208 : 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 : ulong batch_data [ 8 ]; for( ulong j=0; j<8; j++ ) batch_data [ j ] = (ulong)root_msg;
760 : uint batch_sz [ 8 ]; for( ulong j=0; j<8; j++ ) batch_sz [ j ] = last_block_sz;
761 : ulong batch_ctr [ 8 ]; for( ulong j=0; j<8; j++ ) batch_ctr [ j ] = ctr0+i+j;
762 : uint batch_flags[ 8 ]; for( ulong j=0; j<8; j++ ) batch_flags[ j ] = last_block_flags;
763 : void * batch_hash [ 8 ]; for( ulong j=0; j<8; j++ ) batch_hash [ j ] = (uchar *)hash + (i+j)*64;
764 : void * batch_cv [ 8 ]; for( ulong j=0; j<8; j++ ) batch_cv [ j ] = root_cv_pre;
765 : 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 : ulong batch_data [ 4 ]; for( ulong j=0; j<4; j++ ) batch_data [ j ] = (ulong)root_msg;
768 : uint batch_sz [ 4 ]; for( ulong j=0; j<4; j++ ) batch_sz [ j ] = last_block_sz;
769 : ulong batch_ctr [ 4 ]; for( ulong j=0; j<4; j++ ) batch_ctr [ j ] = ctr0+i+j;
770 : uint batch_flags[ 4 ]; for( ulong j=0; j<4; j++ ) batch_flags[ j ] = last_block_flags;
771 : void * batch_hash [ 4 ]; for( ulong j=0; j<4; j++ ) batch_hash [ j ] = (uchar *)hash + (i+j)*64;
772 : void * batch_cv [ 4 ]; for( ulong j=0; j<4; j++ ) batch_cv [ j ] = root_cv_pre;
773 : fd_blake3_sve2_compress4( 4UL, batch_data, batch_sz, batch_ctr, batch_flags, batch_hash, 64U, batch_cv );
774 : #elif FD_HAS_SSE
775 : fd_blake3_sse_compress1( (uchar *)hash+i*64, root_msg, last_block_sz, ctr0+i, last_block_flags, NULL, root_cv_pre );
776 : #else
777 : fd_blake3_ref_compress1( (uchar *)hash+i*64, root_msg, last_block_sz, ctr0+i, last_block_flags, NULL, root_cv_pre );
778 : #endif
779 17208 : }
780 8622 : }
781 :
782 : void *
783 : fd_blake3_fini_2048( fd_blake3_t * sha,
784 6741 : void * hash ) {
785 6741 : FD_BLAKE3_TRACE(( "fd_blake3_fini_2048(sha=%p,hash=%p)", (void *)sha, hash ));
786 :
787 6741 : uchar root_msg [ 64 ] __attribute__((aligned(64)));
788 6741 : uchar root_cv_pre[ 32 ] __attribute__((aligned(32)));
789 6741 : fd_blake3_fini_xof_compress( sha, root_msg, root_cv_pre );
790 6741 : fd_blake3_fini_xof_expand( sha, root_msg, root_cv_pre, hash );
791 :
792 6741 : FD_BLAKE3_TRACE(( "fd_blake3_fini_2048: done" ));
793 6741 : return hash;
794 6741 : }
795 :
796 : void
797 : fd_blake3_fini_2048_xn( ulong n,
798 : fd_blake3_t ** sha,
799 2512 : void ** hash ) {
800 2512 : #if FD_BLAKE3_PARA_MAX>1
801 2512 : int single = 0;
802 7528 : for( ulong i=0UL; i<n; i++ ) {
803 5016 : fd_blake3_fini_xof_setup( sha[ i ] );
804 5016 : single |= sha[ i ]->pos.input_sz<=FD_BLAKE3_CHUNK_SZ;
805 5016 : }
806 :
807 2512 : if( FD_UNLIKELY( single ) ) {
808 4715 : for( ulong i=0UL; i<n; i++ ) fd_blake3_fini_2048( sha[ i ], hash[ i ] );
809 1573 : return;
810 1573 : }
811 :
812 939 : ulong tick[ FD_BLAKE3_XN_MAX ];
813 2812 : for( ulong i=0UL; i<n; i++ ) tick[ i ] = sha[ i ]->pos.next_tick+1UL;
814 3379 : for(;;) {
815 3379 : fd_blake3_op_t ops[ FD_BLAKE3_XN_MAX*FD_BLAKE3_PARA_MAX ];
816 3379 : ulong op_cnt = 0UL;
817 10144 : for( ulong i=0UL; i<n; i++ ) op_cnt += fd_blake3_fini_xof_prepare( sha[ i ], ops+op_cnt, tick[ i ]++ );
818 3379 : if( !op_cnt ) break;
819 :
820 4890 : for( ulong off=0UL; off<op_cnt; off+=FD_BLAKE3_PARA_MAX ) {
821 2451 : fd_blake3_batch_hash( ops+off, fd_ulong_min( op_cnt-off, FD_BLAKE3_PARA_MAX ) );
822 2451 : }
823 2439 : }
824 :
825 939 : uchar root_msg [ 64 ] __attribute__((aligned(64)));
826 939 : uchar root_cv_pre[ 32 ] __attribute__((aligned(32)));
827 2820 : for( ulong i=0UL; i<n; i++ ) fd_blake3_fini_xof_expand( sha[ i ], root_msg, root_cv_pre, hash[ i ] );
828 : #else
829 : for( ulong i=0UL; i<n; i++ ) fd_blake3_fini_2048( sha[ i ], hash[ i ] );
830 : #endif
831 939 : }
832 :
833 : void *
834 : fd_blake3_hash( void const * data,
835 : ulong sz,
836 0 : void * hash ) {
837 :
838 0 : fd_blake3_buf_t tbl[1];
839 0 : fd_blake3_pos_t s[1];
840 0 : fd_blake3_pos_init( s, data, sz );
841 :
842 0 : #if FD_BLAKE3_PARA_MAX>1
843 0 : for(;;) {
844 0 : fd_blake3_op_t op[1];
845 0 : if( !fd_blake3_prepare_fast( s, tbl, op, FD_BLAKE3_PARA_MAX, FD_BLAKE3_PARA_MAX ) )
846 0 : break;
847 0 : #if FD_HAS_AVX512
848 0 : fd_blake3_avx512_compress16_fast( op->msg, op->out, op->counter, op->flags );
849 : #elif FD_HAS_AVX
850 : fd_blake3_avx_compress8_fast( op->msg, op->out, op->counter, op->flags );
851 : #elif FD_HAS_SVE2
852 : fd_blake3_sve2_compress4_fast( op->msg, op->out, op->counter, op->flags );
853 : #else
854 : #error "missing para support"
855 : #endif
856 0 : }
857 0 : #endif
858 :
859 0 : void const * hash_ = fd_blake3_single_hash( s, tbl );
860 0 : memcpy( hash, hash_, 32UL );
861 0 : return hash;
862 0 : }
863 :
864 : #if FD_HAS_AVX
865 :
866 : void
867 : fd_blake3_lthash_batch8(
868 : void const * batch_data[8], /* align=32 ele_align=1 */
869 : uint const batch_sz [8], /* align=32 */
870 : void * out_lthash /* align=32 */
871 0 : ) {
872 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)batch_data, 32 ) ) ) {
873 0 : FD_LOG_ERR(( "misaligned batch_data: %p", (void *)batch_data ));
874 0 : }
875 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)batch_sz, 32 ) ) ) {
876 0 : FD_LOG_ERR(( "misaligned batch_sz: %p", (void *)batch_sz ));
877 0 : }
878 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)out_lthash, 32 ) ) ) {
879 0 : FD_LOG_ERR(( "misaligned out_lthash: %p", (void *)out_lthash ));
880 0 : }
881 :
882 0 : ulong batch_ctr [ 8 ] = {0};
883 0 : uint batch_flags[ 8 ]; for( uint i=0; i<8; i++ ) batch_flags[ i ] = FD_BLAKE3_FLAG_ROOT;
884 0 : fd_blake3_avx_compress8( 8UL, batch_data, batch_sz, batch_ctr, batch_flags, NULL, out_lthash, 32U, NULL );
885 0 : }
886 :
887 : #endif
888 :
889 : #if FD_HAS_AVX512
890 :
891 : void
892 : fd_blake3_lthash_batch16(
893 : void const * batch_data[16], /* align=64 ele_align=1 */
894 : uint const batch_sz [16], /* align=64 */
895 : void * out_lthash /* align=64 */
896 0 : ) {
897 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)batch_data, 64 ) ) ) {
898 0 : FD_LOG_ERR(( "misaligned batch_data: %p", (void *)batch_data ));
899 0 : }
900 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)batch_sz, 64 ) ) ) {
901 0 : FD_LOG_ERR(( "misaligned batch_sz: %p", (void *)batch_sz ));
902 0 : }
903 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)out_lthash, 64 ) ) ) {
904 0 : FD_LOG_ERR(( "misaligned out_lthash: %p", (void *)out_lthash ));
905 0 : }
906 :
907 0 : ulong batch_ctr [ 16 ] = {0};
908 0 : uint batch_flags[ 16 ]; for( uint i=0; i<16; i++ ) batch_flags[ i ] = FD_BLAKE3_FLAG_ROOT;
909 0 : fd_blake3_avx512_compress16( 16UL, batch_data, batch_sz, batch_ctr, batch_flags, NULL, out_lthash, 32U, NULL );
910 0 : }
911 :
912 : #endif
|
