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 10978835 : ulong sz ) {
10 10978835 : *s = (fd_blake3_pos_t) {
11 10978835 : .input = data,
12 10978835 : .input_sz = sz,
13 10978835 : .magic = FD_BLAKE3_MAGIC,
14 10978835 : };
15 10978835 : return s;
16 10978835 : }
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 32014122 : fd_blake3_l0_complete( fd_blake3_pos_t const * s ) {
23 32014122 : return ( s->leaf_idx<<FD_BLAKE3_CHUNK_LG_SZ ) >= fd_ulong_max( s->input_sz, 64 );
24 32014122 : }
25 :
26 : FD_FN_PURE static inline int
27 : fd_blake3_is_finished( fd_blake3_pos_t const * s,
28 14613135 : ulong tick ) {
29 14613135 : int l0_complete = fd_blake3_l0_complete( s );
30 14613135 : int ln_complete = s->live_cnt == 1UL;
31 14613135 : int idle = tick >= s->next_tick;
32 14613135 : return l0_complete & ln_complete & idle;
33 14613135 : }
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 12433601 : ulong tick ) {
40 :
41 12433601 : ulong msg_off = s->leaf_idx << FD_BLAKE3_CHUNK_LG_SZ;
42 12433601 : ulong msg_sz = fd_ulong_min( s->input_sz - msg_off, 1024UL );
43 12433601 : uchar const * msg = s->input + msg_off;
44 12433601 : uchar * out = buf->slots[ s->layer ][ s->head.uc[ s->layer ] ];
45 :
46 12433601 : int flags = fd_int_if( s->input_sz <= FD_BLAKE3_CHUNK_SZ, FD_BLAKE3_FLAG_ROOT, 0 );
47 :
48 12433601 : *op = (fd_blake3_op_t) {
49 12433601 : .msg = msg,
50 12433601 : .out = out,
51 12433601 : .counter = s->leaf_idx,
52 12433601 : .sz = (ushort)msg_sz,
53 12433601 : .flags = (uchar)flags
54 12433601 : };
55 :
56 12433601 : s->head.uc[ 0 ] = (uchar)( s->head.uc[ 0 ]+1 );
57 12433601 : s->leaf_idx++;
58 12433601 : s->live_cnt++;
59 12433601 : s->next_tick = tick+1;
60 :
61 12433601 : return op;
62 :
63 12433601 : }
64 :
65 : static int
66 : fd_blake3_seek_branch( fd_blake3_pos_t * restrict s,
67 : fd_blake3_buf_t * restrict buf,
68 11615424 : ulong tick ) {
69 :
70 11615424 : if( s->live_cnt == 1UL )
71 77571 : return 0;
72 :
73 11537853 : if( !fd_blake3_l0_complete( s ) )
74 1722608 : return ( s->tail.uc[ s->layer - 1 ] + 1 ) <
75 1722608 : ( s->head.uc[ s->layer - 1 ] );
76 :
77 9815245 : # if FD_HAS_AVX
78 :
79 9815245 : wb_t diff = wb_sub( wb_ld( s->head.uc ), wb_ld( s->tail.uc ) );
80 :
81 9815245 : uint mergeable_layers = (uint)_mm256_movemask_epi8( wb_gt( diff, wb_bcast( 1 ) ) );
82 9815245 : int merge_layer = fd_uint_find_lsb_w_default( mergeable_layers, -1 );
83 9815245 : if( merge_layer>=0 ) {
84 9035851 : if( ((uint)merge_layer >= s->layer) & (tick < s->next_tick) )
85 1641071 : return 0; /* still waiting for previous merge */
86 7394780 : s->layer = (uint)merge_layer+1U;
87 7394780 : return 1;
88 9035851 : }
89 :
90 779394 : uint single_layers = (uint)_mm256_movemask_epi8( wb_eq( diff, wb_bcast( 1 ) ) );
91 779394 : uint single_lo = (uint)fd_uint_find_lsb( single_layers );
92 779394 : uint single_hi = (uint)fd_uint_find_lsb( single_layers & ( ~fd_uint_mask_lsb( (int)(single_lo+1U) ) ) );
93 :
94 779394 : wb_t node = wb_ld( buf->slots[ single_lo ][ s->tail.uc[ single_lo ] ] );
95 779394 : 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 779394 : FD_BLAKE3_TRACE(( "fd_blake3_seek_branch: moving up %u/%u to %u/%u",
140 779394 : single_lo, s->tail.uc[ single_lo ],
141 779394 : single_hi, s->head.uc[ single_hi ] ));
142 :
143 779394 : if( ((uint)single_hi >= s->layer) & (tick < s->next_tick) )
144 266118 : return 0; /* still waiting for previous merge */
145 :
146 513276 : s->head.uc[ single_lo ] = (uchar)( s->head.uc[ single_lo ]-1 );
147 513276 : s->head.uc[ single_hi ] = (uchar)( s->head.uc[ single_hi ]+1 );
148 :
149 513276 : s->layer = (uint)single_hi+1U;
150 513276 : return 1;
151 779394 : }
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 11615424 : ulong tick ) {
158 :
159 11615424 : if( !fd_blake3_seek_branch( s, buf, tick ) )
160 1984760 : return NULL;
161 :
162 9630664 : FD_DCHECK_CRIT( s->layer < FD_BLAKE3_ROW_CNT, "invariant violation" );
163 :
164 9630664 : uchar const * msg = buf->slots[ s->layer-1U ][ s->tail.uc[ s->layer-1U ] ];
165 9630664 : uchar * out = buf->slots[ s->layer ][ s->head.uc[ s->layer ] ];
166 :
167 9630664 : s->head.uc[ s->layer ] = (uchar)( s->head.uc[ s->layer ]+1 );
168 9630664 : s->tail.uc[ s->layer-1 ] = (uchar)( s->tail.uc[ s->layer-1 ]+2 );
169 9630664 : s->live_cnt--;
170 9630664 : s->next_tick = tick+1;
171 :
172 9630664 : uint flags = FD_BLAKE3_FLAG_PARENT |
173 9630664 : fd_uint_if( s->live_cnt==1UL, FD_BLAKE3_FLAG_ROOT, 0u );
174 :
175 9630664 : *op = (fd_blake3_op_t) {
176 9630664 : .msg = msg,
177 9630664 : .out = out,
178 9630664 : .counter = 0UL,
179 9630664 : .sz = 64U,
180 9630664 : .flags = (uchar)flags
181 9630664 : };
182 9630664 : return op;
183 :
184 11615424 : }
185 :
186 : static void
187 2758822 : fd_blake3_advance( fd_blake3_pos_t * restrict s ) {
188 :
189 2758822 : # if FD_HAS_AVX
190 :
191 2758822 : wb_t tail = wb_ld( s->tail.uc );
192 2758822 : wb_t head = wb_ld( s->head.uc );
193 2758822 : wb_t mask = wb_eq( tail, head );
194 2758822 : wb_st( s->tail.uc, wb_andnot( mask, tail ) );
195 2758822 : 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 2758822 : if( s->head.uc[ s->layer ]==FD_BLAKE3_COL_CNT ) {
209 95366 : s->layer++;
210 95366 : }
211 2663456 : else if( ( s->layer > 0UL ) &&
212 2663456 : ( s->tail.uc[ s->layer-1 ] < s->head.uc[ s->layer-1 ] ) ) {
213 : /* pass */
214 790512 : }
215 1872944 : else if( fd_blake3_l0_complete( s ) ) {
216 1547822 : s->layer++;
217 1547822 : }
218 325122 : else if( s->layer > 0UL ) {
219 118188 : s->layer = 0UL;
220 118188 : }
221 :
222 2758822 : }
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 13690785 : ulong tick ) {
229 :
230 13690785 : FD_DCHECK_CRIT( s->layer < FD_BLAKE3_ROW_CNT, "invariant violation" );
231 :
232 13690785 : if( fd_blake3_is_finished( s, tick ) )
233 0 : return NULL;
234 :
235 13690785 : if( tick >= s->next_tick )
236 2758822 : fd_blake3_advance( s );
237 :
238 13690785 : if( s->layer != 0 )
239 11615424 : return fd_blake3_prepare_branch( s, buf, op, tick );
240 :
241 2075361 : if( ( s->head.uc[0] >= FD_BLAKE3_COL_CNT ) |
242 2075361 : ( fd_blake3_l0_complete( s ) ) ) {
243 295344 : return NULL;
244 295344 : }
245 :
246 1780017 : return fd_blake3_prepare_leaf( s, buf, op, tick );
247 :
248 2075361 : }
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 8451130 : ulong min ) {
261 :
262 8451130 : if( s->layer && s->head.uc[ s->layer-1 ]==FD_BLAKE3_COL_CNT ) {
263 3808198 : op->msg = buf->rows[ s->layer-1 ];
264 3808198 : op->out = buf->rows[ s->layer ] + (s->head.uc[ s->layer ]<<FD_BLAKE3_OUTCHAIN_LG_SZ);
265 3808198 : op->counter = 0UL;
266 3808198 : op->flags = FD_BLAKE3_FLAG_PARENT;
267 :
268 : /* Assume that branch layer is fully hashed (up to col cnt) */
269 3808198 : s->head.uc[ s->layer-1 ] = 0;
270 3808198 : s->head.uc[ s->layer ] = (uchar)( (ulong)s->head.uc[ s->layer ]+n );
271 3808198 : s->live_cnt -= n;
272 3808198 : s->layer = fd_uint_if( s->head.uc[ s->layer ]==FD_BLAKE3_COL_CNT,
273 3808198 : s->layer+1U, 0U );
274 :
275 3808198 : return op;
276 3808198 : }
277 :
278 4642932 : ulong pos = s->leaf_idx << FD_BLAKE3_CHUNK_LG_SZ;
279 4642932 : ulong avail = fd_ulong_align_dn( s->input_sz - pos, FD_BLAKE3_CHUNK_SZ ) >> FD_BLAKE3_CHUNK_LG_SZ;
280 4642932 : 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 4642932 : if( n<min ) return NULL;
286 :
287 4616955 : op->msg = s->input + (s->leaf_idx<<FD_BLAKE3_CHUNK_LG_SZ);
288 4616955 : op->out = buf->rows[0] + (s->head.uc[0]<<FD_BLAKE3_OUTCHAIN_LG_SZ);
289 4616955 : op->counter = s->leaf_idx;
290 4616955 : op->flags = 0;
291 :
292 4616955 : s->head.uc[0] = (uchar)( (ulong)s->head.uc[0]+n );
293 4616955 : s->leaf_idx += n;
294 4616955 : s->live_cnt += n;
295 4616955 : s->layer = fd_uint_if( s->head.uc[0]==FD_BLAKE3_COL_CNT, 1U, 0U );
296 :
297 4616955 : return op;
298 4642932 : }
299 :
300 : static void
301 : fd_blake3_batch_hash( fd_blake3_op_t const * ops,
302 2511928 : ulong op_cnt ) {
303 2511928 : uchar const * batch_data [ FD_BLAKE3_PARA_MAX ] __attribute__((aligned(64)));
304 2511928 : uint batch_data_sz[ FD_BLAKE3_PARA_MAX ] = {0};
305 2511928 : uchar * batch_hash [ FD_BLAKE3_PARA_MAX ] __attribute__((aligned(64)));
306 2511928 : ulong batch_ctr [ FD_BLAKE3_PARA_MAX ];
307 2511928 : uint batch_flags [ FD_BLAKE3_PARA_MAX ];
308 13675715 : for( ulong j=0UL; j<op_cnt; j++ ) {
309 11163787 : batch_data [ j ] = ops[ j ].msg;
310 11163787 : batch_hash [ j ] = ops[ j ].out;
311 11163787 : batch_data_sz[ j ] = ops[ j ].sz;
312 11163787 : batch_ctr [ j ] = ops[ j ].counter;
313 11163787 : batch_flags [ j ] = ops[ j ].flags;
314 11163787 : }
315 832946 : #if FD_HAS_AVX512
316 832946 : fd_blake3_avx512_compress16( op_cnt, batch_data, batch_data_sz, batch_ctr, batch_flags, fd_type_pun( batch_hash ), NULL, 32U, NULL );
317 : #elif FD_HAS_AVX
318 1678982 : fd_blake3_avx_compress8 ( op_cnt, batch_data, batch_data_sz, batch_ctr, batch_flags, fd_type_pun( batch_hash ), NULL, 32U, NULL );
319 : #else
320 : #error "FIXME missing para support"
321 : #endif
322 2511928 : }
323 :
324 : #endif
325 :
326 : /* Simple API *********************************************************/
327 :
328 : ulong
329 66 : fd_blake3_align( void ) {
330 66 : return FD_BLAKE3_ALIGN;
331 66 : }
332 :
333 : ulong
334 21 : fd_blake3_footprint( void ) {
335 21 : return FD_BLAKE3_FOOTPRINT;
336 21 : }
337 :
338 : void *
339 24 : fd_blake3_new( void * shmem ) {
340 24 : fd_blake3_t * sha = (fd_blake3_t *)shmem;
341 :
342 24 : if( FD_UNLIKELY( !shmem ) ) {
343 3 : FD_LOG_WARNING(( "NULL shmem" ));
344 3 : return NULL;
345 3 : }
346 :
347 21 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shmem, fd_blake3_align() ) ) ) {
348 3 : FD_LOG_WARNING(( "misaligned shmem" ));
349 3 : return NULL;
350 3 : }
351 :
352 18 : ulong footprint = fd_blake3_footprint();
353 :
354 18 : fd_memset( sha, 0, footprint );
355 :
356 18 : FD_COMPILER_MFENCE();
357 18 : FD_VOLATILE( sha->pos.magic ) = FD_BLAKE3_MAGIC;
358 18 : FD_COMPILER_MFENCE();
359 :
360 18 : return (void *)sha;
361 21 : }
362 :
363 : fd_blake3_t *
364 24 : fd_blake3_join( void * shsha ) {
365 :
366 24 : if( FD_UNLIKELY( !shsha ) ) {
367 3 : FD_LOG_WARNING(( "NULL shsha" ));
368 3 : return NULL;
369 3 : }
370 :
371 21 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shsha, fd_blake3_align() ) ) ) {
372 3 : FD_LOG_WARNING(( "misaligned shsha" ));
373 3 : return NULL;
374 3 : }
375 :
376 18 : fd_blake3_t * sha = (fd_blake3_t *)shsha;
377 :
378 18 : if( FD_UNLIKELY( sha->pos.magic!=FD_BLAKE3_MAGIC ) ) {
379 0 : FD_LOG_WARNING(( "bad magic" ));
380 0 : return NULL;
381 0 : }
382 :
383 18 : return sha;
384 18 : }
385 :
386 : void *
387 21 : fd_blake3_leave( fd_blake3_t * sha ) {
388 :
389 21 : if( FD_UNLIKELY( !sha ) ) {
390 3 : FD_LOG_WARNING(( "NULL sha" ));
391 3 : return NULL;
392 3 : }
393 :
394 18 : return (void *)sha;
395 21 : }
396 :
397 : void *
398 24 : fd_blake3_delete( void * shsha ) {
399 :
400 24 : if( FD_UNLIKELY( !shsha ) ) {
401 3 : FD_LOG_WARNING(( "NULL shsha" ));
402 3 : return NULL;
403 3 : }
404 :
405 21 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)shsha, fd_blake3_align() ) ) ) {
406 3 : FD_LOG_WARNING(( "misaligned shsha" ));
407 3 : return NULL;
408 3 : }
409 :
410 18 : fd_blake3_t * sha = (fd_blake3_t *)shsha;
411 :
412 18 : if( FD_UNLIKELY( sha->pos.magic!=FD_BLAKE3_MAGIC ) ) {
413 0 : FD_LOG_WARNING(( "bad magic" ));
414 0 : return NULL;
415 0 : }
416 :
417 18 : FD_COMPILER_MFENCE();
418 18 : FD_VOLATILE( sha->pos.magic ) = 0UL;
419 18 : FD_COMPILER_MFENCE();
420 :
421 18 : return (void *)sha;
422 18 : }
423 :
424 :
425 : fd_blake3_t *
426 10952858 : fd_blake3_init( fd_blake3_t * sha ) {
427 10952858 : FD_BLAKE3_TRACE(( "fd_blake3_init(sha=%p)", (void *)sha ));
428 10952858 : fd_blake3_pos_init( &sha->pos, NULL, 0UL );
429 10952858 : sha->block_sz = 0UL;
430 10952858 : return sha;
431 10952858 : }
432 :
433 : #if FD_BLAKE3_PARA_MAX>1
434 :
435 : static void
436 : fd_blake3_append_blocks( fd_blake3_pos_t * s,
437 : fd_blake3_buf_t * tbl,
438 : uchar const * data,
439 354838 : ulong buf_cnt ) {
440 354838 : s->input = data - (s->leaf_idx << FD_BLAKE3_CHUNK_LG_SZ); /* TODO HACKY!! */
441 4281435 : for( ulong i=0UL; i<buf_cnt; i++ ) {
442 3926597 : fd_blake3_op_t op[1];
443 7132644 : do {
444 7132644 : if( !fd_blake3_prepare_fast( s, tbl, op, FD_BLAKE3_PARA_MAX, FD_BLAKE3_PARA_MAX ) )
445 0 : return;
446 1339278 : #if FD_HAS_AVX512
447 1339278 : fd_blake3_avx512_compress16_fast( op->msg, op->out, op->counter, op->flags );
448 : #elif FD_HAS_AVX
449 5793366 : fd_blake3_avx_compress8_fast( op->msg, op->out, op->counter, op->flags );
450 : #else
451 : #error "missing para support"
452 : #endif
453 7132644 : } while( op->flags & FD_BLAKE3_FLAG_PARENT );
454 3926597 : }
455 354838 : }
456 :
457 : #else
458 :
459 : static void
460 : fd_blake3_append_blocks( fd_blake3_pos_t * s,
461 : fd_blake3_buf_t * tbl,
462 : uchar const * data,
463 : ulong buf_cnt ) {
464 : (void)buf_cnt;
465 : s->input = data - (s->leaf_idx << FD_BLAKE3_CHUNK_LG_SZ); /* TODO HACKY!! */
466 : fd_blake3_op_t op[1];
467 : while( buf_cnt ) {
468 : if( !fd_blake3_prepare( s, tbl, op, s->next_tick ) ) {
469 : FD_BLAKE3_TRACE(( "fd_blake3_append_blocks: no more ops to prepare" ));
470 : break;
471 : }
472 : if( op->flags & FD_BLAKE3_FLAG_PARENT ) {
473 : FD_BLAKE3_TRACE(( "fd_blake3_append_blocks: compressing output chaining values (layer %u)", s->layer ));
474 : fd_blake3_ref_compress1( op->out, op->msg, 64UL, op->counter, op->flags, NULL, NULL );
475 : } else {
476 : FD_BLAKE3_TRACE(( "fd_blake3_append_blocks: compressing %lu leaf chunks", FD_BLAKE3_COL_CNT ));
477 : fd_blake3_ref_compress1( op->out, op->msg, FD_BLAKE3_CHUNK_SZ, op->counter, op->flags, NULL, NULL );
478 : buf_cnt--;
479 : }
480 : s->next_tick++;
481 : }
482 : }
483 :
484 : #endif
485 :
486 : fd_blake3_t *
487 : fd_blake3_append( fd_blake3_t * sha,
488 : void const * _data,
489 11157530 : ulong sz ) {
490 :
491 : /* If no data to append, we are done */
492 :
493 11157530 : if( FD_UNLIKELY( !sz ) ) return sha;
494 11117731 : FD_BLAKE3_TRACE(( "fd_blake3_append(sha=%p,data=%p,sz=%lu)", (void *)sha, _data, sz ));
495 :
496 : /* Unpack inputs */
497 :
498 11117731 : fd_blake3_pos_t * s = &sha->pos;
499 11117731 : fd_blake3_buf_t * tbl = &sha->buf;
500 11117731 : uchar * buf = sha->block;
501 11117731 : ulong buf_used = sha->block_sz;
502 :
503 11117731 : uchar const * data = (uchar const *)_data;
504 :
505 : /* Update input_sz */
506 :
507 11117731 : s->input_sz += sz;
508 :
509 : /* Edge case: For the first completed 1024 bytes of input, don't
510 : immediately hash, since it is not clear whether this chunk has
511 : the root flag set. */
512 11117731 : if( FD_UNLIKELY( FD_BLAKE3_PARA_MAX==1 && s->input_sz==1024UL ) ) {
513 0 : fd_memcpy( buf + buf_used, data, sz );
514 0 : sha->block_sz = FD_BLAKE3_CHUNK_SZ;
515 0 : return sha;
516 0 : }
517 :
518 : /* Handle buffered bytes from previous appends */
519 :
520 11117731 : if( FD_UNLIKELY( buf_used ) ) { /* optimized for well aligned use of append */
521 :
522 : /* If the append isn't large enough to complete the current block,
523 : buffer these bytes too and return */
524 :
525 168884 : ulong buf_rem = FD_BLAKE3_PRIVATE_BUF_MAX - buf_used; /* In (0,FD_BLAKE3_PRIVATE_BUF_MAX) */
526 168884 : if( FD_UNLIKELY( sz < buf_rem ) ) { /* optimize for large append */
527 106316 : fd_memcpy( buf + buf_used, data, sz );
528 106316 : sha->block_sz = buf_used + sz;
529 106316 : return sha;
530 106316 : }
531 :
532 : /* Otherwise, buffer enough leading bytes of data to complete the
533 : block, update the hash and then continue processing any remaining
534 : bytes of data. */
535 :
536 62568 : fd_memcpy( buf + buf_used, data, buf_rem );
537 62568 : data += buf_rem;
538 62568 : sz -= buf_rem;
539 :
540 62568 : fd_blake3_append_blocks( s, tbl, buf, 1UL );
541 62568 : sha->block_sz = 0UL;
542 62568 : }
543 :
544 : /* Append the bulk of the data */
545 :
546 11011415 : ulong buf_cnt = sz >> FD_BLAKE3_PRIVATE_LG_BUF_MAX;
547 11011415 : if( FD_LIKELY( buf_cnt ) ) fd_blake3_append_blocks( s, tbl, data, buf_cnt ); /* optimized for large append */
548 :
549 : /* Buffer any leftover bytes */
550 :
551 11011415 : buf_used = sz & (FD_BLAKE3_PRIVATE_BUF_MAX-1UL); /* In [0,FD_BLAKE3_PRIVATE_BUF_MAX) */
552 11011415 : if( FD_UNLIKELY( buf_used ) ) { /* optimized for well aligned use of append */
553 11011341 : fd_memcpy( buf, data + (buf_cnt << FD_BLAKE3_PRIVATE_LG_BUF_MAX), buf_used );
554 11011341 : sha->block_sz = buf_used; /* In (0,FD_BLAKE3_PRIVATE_BUF_MAX) */
555 11011341 : }
556 :
557 11011415 : FD_BLAKE3_TRACE(( "fd_blake3_append: done" ));
558 11011415 : return sha;
559 11117731 : }
560 :
561 : static void const *
562 : fd_blake3_single_hash( fd_blake3_pos_t * s,
563 78357 : fd_blake3_buf_t * tbl ) {
564 78357 : #if FD_BLAKE3_PARA_MAX>1
565 78357 : ulong tick = 0UL;
566 922350 : while( !fd_blake3_is_finished( s, tick ) ) {
567 843993 : fd_blake3_op_t ops[ FD_BLAKE3_PARA_MAX ] = {0};
568 843993 : ulong op_cnt = 0UL;
569 4304584 : while( op_cnt<FD_BLAKE3_PARA_MAX ) {
570 4246530 : fd_blake3_op_t * op = &ops[ op_cnt ];
571 4246530 : if( !fd_blake3_prepare( s, tbl, op, tick ) )
572 785939 : break;
573 3460591 : op_cnt++;
574 3460591 : }
575 :
576 843993 : fd_blake3_batch_hash( ops, op_cnt );
577 843993 : tick++;
578 843993 : }
579 : #else
580 : while( !fd_blake3_is_finished( s, s->next_tick ) ) {
581 : fd_blake3_op_t op[1] = {0};
582 : if( !fd_blake3_prepare( s, tbl, op, s->next_tick ) )
583 : break;
584 : s->next_tick++;
585 : FD_BLAKE3_TRACE(( "fd_blake3_single_hash: compressing %hu bytes at layer %u, counter %lu, flags 0x%x",
586 : op->sz, s->layer, op->counter, op->flags ));
587 : # if FD_HAS_SSE
588 : fd_blake3_sse_compress1( op->out, op->msg, op->sz, op->counter, op->flags, NULL, NULL );
589 : # else
590 : fd_blake3_ref_compress1( op->out, op->msg, op->sz, op->counter, op->flags, NULL, NULL );
591 : # endif
592 : }
593 : #endif
594 78357 : return tbl->slots[ s->layer ][0];
595 78357 : }
596 :
597 : void *
598 : fd_blake3_fini( fd_blake3_t * sha,
599 52380 : void * hash ) {
600 :
601 : /* Unpack inputs */
602 :
603 52380 : fd_blake3_pos_t * s = &sha->pos;
604 52380 : fd_blake3_buf_t * tbl = &sha->buf;
605 52380 : uchar * buf = sha->block;
606 52380 : ulong buf_used = sha->block_sz;
607 52380 : FD_BLAKE3_TRACE(( "fd_blake3_fini(sha=%p,sz=%lu)", (void *)sha, s->input_sz ));
608 :
609 : /* TODO HACKY!! */
610 52380 : s->input = buf - ( s->leaf_idx << FD_BLAKE3_CHUNK_LG_SZ );
611 52380 : s->input_sz = ( s->leaf_idx << FD_BLAKE3_CHUNK_LG_SZ ) + buf_used;
612 :
613 52380 : void const * hash_ = fd_blake3_single_hash( s, tbl );
614 52380 : memcpy( hash, hash_, 32UL );
615 52380 : return hash;
616 52380 : }
617 :
618 : /* fd_blake3_fini_xof_compress performs BLAKE3 compression (input
619 : hashing) for all blocks in the hash tree except for the root block.
620 : Root compression inputs are returned via the function's out pointers:
621 : On return, root_msg[0..64] contains the padded message input for the
622 : root block, root_cv_pre[0..64] contains the output chaining value of
623 : the previous block (or the BLAKE3 IV if root block is the only block
624 : in the hash operation, i.e. <=64 byte hash input).
625 : Other values (counter, flags, size) are re-derived by the XOF
626 : implementation using the blake3 state object. */
627 :
628 : void
629 : fd_blake3_fini_xof_compress( fd_blake3_t * sha,
630 : uchar * root_msg,
631 10900478 : uchar * root_cv_pre ) {
632 10900478 : fd_blake3_pos_t * s = &sha->pos;
633 10900478 : fd_blake3_buf_t * tbl = &sha->buf;
634 10900478 : uchar * buf = sha->block;
635 10900478 : ulong buf_used = sha->block_sz;
636 :
637 : /* TODO HACKY!! */
638 10900478 : s->input = buf - ( s->leaf_idx << FD_BLAKE3_CHUNK_LG_SZ );
639 10900478 : s->input_sz = ( s->leaf_idx << FD_BLAKE3_CHUNK_LG_SZ ) + buf_used;
640 :
641 : /* The root block is contained in a leaf. Process all but the last
642 : blocks of the chunk. (The last block is the "root" block) */
643 10900478 : if( s->input_sz<=FD_BLAKE3_CHUNK_SZ ) {
644 10653584 : fd_blake3_op_t op[1];
645 10653584 : if( !fd_blake3_prepare_leaf( s, tbl, op, s->next_tick ) )
646 0 : FD_LOG_ERR(( "fd_blake3_fini_xof_compress invariant violation: failed to prepare compression of <=1024 byte message (duplicate call to fini?)" ));
647 10653584 : #if FD_HAS_SSE
648 10653584 : fd_blake3_sse_compress1( root_msg, op->msg, op->sz, op->counter, op->flags, root_cv_pre, NULL );
649 : #else
650 : fd_blake3_ref_compress1( root_msg, op->msg, op->sz, op->counter, op->flags, root_cv_pre, NULL );
651 : #endif
652 10653584 : return;
653 10653584 : }
654 :
655 : /* The root block is a branch node. Continue working until there are
656 : only two blocks remaining. */
657 246894 : ulong tick = sha->pos.next_tick+1;
658 1914829 : for(;;) {
659 1914829 : int l0_complete = fd_blake3_l0_complete( s );
660 1914829 : int ln_complete = s->live_cnt == 2UL;
661 1914829 : if( l0_complete & ln_complete ) break;
662 :
663 1667935 : #if FD_BLAKE3_PARA_MAX>1
664 1667935 : fd_blake3_op_t ops[ FD_BLAKE3_PARA_MAX ] = {0};
665 1667935 : ulong op_cnt = 0UL;
666 9371131 : while( op_cnt<FD_BLAKE3_PARA_MAX ) {
667 9197361 : fd_blake3_op_t * op = &ops[ op_cnt ];
668 9197361 : if( !fd_blake3_prepare( s, tbl, op, tick ) )
669 1494165 : break;
670 7703196 : op_cnt++;
671 7703196 : }
672 1667935 : if( FD_UNLIKELY( !op_cnt ) ) {
673 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 ));
674 0 : }
675 :
676 1667935 : fd_blake3_batch_hash( ops, op_cnt );
677 : #else
678 : fd_blake3_op_t op[1] = {0};
679 : if( !fd_blake3_prepare( s, tbl, op, tick ) )
680 : break;
681 : # if FD_HAS_SSE
682 : fd_blake3_sse_compress1( op->out, op->msg, op->sz, op->counter, op->flags, NULL, NULL );
683 : # else
684 : fd_blake3_ref_compress1( op->out, op->msg, op->sz, op->counter, op->flags, NULL, NULL );
685 : # endif
686 : #endif
687 1667935 : tick++;
688 1667935 : }
689 246894 : }
690 :
691 : void *
692 : fd_blake3_fini_2048( fd_blake3_t * sha,
693 10900414 : void * hash ) {
694 10900414 : FD_BLAKE3_TRACE(( "fd_blake3_fini_2048(sha=%p,hash=%p)", (void *)sha, hash ));
695 :
696 : /* Compress input until the last remaining piece of work is the BLAKE3
697 : root block. This root block is put through the compression
698 : function repeatedly to "expand" the hash output (XOF hashing).
699 : Solana uses this to generate a 2048 byte 'LtHash' value.
700 : fd_blake3 does this SIMD-parallel for better performance. */
701 10900414 : uchar root_msg [ 64 ] __attribute__((aligned(64)));
702 10900414 : uchar root_cv_pre[ 32 ] __attribute__((aligned(32)));
703 10900414 : fd_blake3_fini_xof_compress( sha, root_msg, root_cv_pre );
704 :
705 : /* Restore root block details */
706 10900414 : uint last_block_sz = 64u;
707 10900414 : uint last_block_flags = FD_BLAKE3_FLAG_ROOT | FD_BLAKE3_FLAG_PARENT;
708 10900414 : ulong ctr0 = 0UL;
709 10900414 : if( sha->pos.input_sz<=FD_BLAKE3_CHUNK_SZ ) {
710 10653520 : last_block_sz = (uint)sha->pos.input_sz & 63u;
711 10653520 : if( fd_ulong_is_aligned( sha->pos.input_sz, 64 ) ) last_block_sz = 64;
712 10653520 : if( FD_UNLIKELY( sha->pos.input_sz==0UL ) ) last_block_sz = 0u;
713 10653520 : last_block_flags = FD_BLAKE3_FLAG_ROOT | FD_BLAKE3_FLAG_CHUNK_END;
714 10653520 : if( sha->pos.input_sz<=FD_BLAKE3_BLOCK_SZ ) last_block_flags |= FD_BLAKE3_FLAG_CHUNK_START;
715 10653520 : ctr0 = sha->pos.leaf_idx-1UL;
716 10653520 : } else {
717 246894 : fd_blake3_op_t op[1];
718 246894 : if( FD_UNLIKELY( !fd_blake3_prepare( &sha->pos, &sha->buf, op, sha->pos.next_tick+1UL ) ) ) {
719 0 : FD_LOG_ERR(( "fd_blake3_fini_2048 invariant violation: failed to prepare branch root compression (duplicate call to fini?)" ));
720 0 : }
721 246894 : memcpy( root_msg, op->msg, 64UL );
722 246894 : memcpy( root_cv_pre, FD_BLAKE3_IV, 32UL );
723 246894 : }
724 10900414 : FD_BLAKE3_TRACE(( "fd_blake3_fini_2048: sz=%lu ctr0=%lu flags=%x",
725 10900414 : sha->pos.input_sz, ctr0, last_block_flags ));
726 :
727 : /* Expand LtHash
728 : For now, this uses the generic AVX2/AVX512 compress backend.
729 : Could write a more optimized version in the future saving some of
730 : the matrix transpose work. */
731 45094050 : for( ulong i=0UL; i<32UL; i+=FD_BLAKE3_PARA_MAX ) {
732 9408020 : #if FD_HAS_AVX512
733 9408020 : ulong batch_data [ 16 ] __attribute__((aligned(64)));
734 159936340 : /* */ for( ulong j=0; j<16; j++ ) batch_data [ j ] = (ulong)root_msg;
735 159936340 : uint batch_sz [ 16 ]; for( ulong j=0; j<16; j++ ) batch_sz [ j ] = last_block_sz;
736 159936340 : ulong batch_ctr [ 16 ]; for( ulong j=0; j<16; j++ ) batch_ctr [ j ] = ctr0+i+j;
737 159936340 : uint batch_flags[ 16 ]; for( ulong j=0; j<16; j++ ) batch_flags[ j ] = last_block_flags;
738 159936340 : void * batch_hash [ 16 ]; for( ulong j=0; j<16; j++ ) batch_hash [ j ] = (uchar *)hash + (i+j)*64;
739 159936340 : void * batch_cv [ 16 ]; for( ulong j=0; j<16; j++ ) batch_cv [ j ] = root_cv_pre;
740 9408020 : fd_blake3_avx512_compress16( 16UL, batch_data, batch_sz, batch_ctr, batch_flags, batch_hash, NULL, 64U, batch_cv );
741 : #elif FD_HAS_AVX
742 223070544 : ulong batch_data [ 8 ]; for( ulong j=0; j<8; j++ ) batch_data [ j ] = (ulong)root_msg;
743 223070544 : uint batch_sz [ 8 ]; for( ulong j=0; j<8; j++ ) batch_sz [ j ] = last_block_sz;
744 223070544 : ulong batch_ctr [ 8 ]; for( ulong j=0; j<8; j++ ) batch_ctr [ j ] = ctr0+i+j;
745 223070544 : uint batch_flags[ 8 ]; for( ulong j=0; j<8; j++ ) batch_flags[ j ] = last_block_flags;
746 223070544 : void * batch_hash [ 8 ]; for( ulong j=0; j<8; j++ ) batch_hash [ j ] = (uchar *)hash + (i+j)*64;
747 223070544 : void * batch_cv [ 8 ]; for( ulong j=0; j<8; j++ ) batch_cv [ j ] = root_cv_pre;
748 24785616 : fd_blake3_avx_compress8( 8UL, batch_data, batch_sz, batch_ctr, batch_flags, batch_hash, NULL, 64U, batch_cv );
749 : #elif FD_HAS_SSE
750 : fd_blake3_sse_compress1( (uchar *)hash+i*64, root_msg, last_block_sz, ctr0+i, last_block_flags, NULL, root_cv_pre );
751 : #else
752 : fd_blake3_ref_compress1( (uchar *)hash+i*64, root_msg, last_block_sz, ctr0+i, last_block_flags, NULL, root_cv_pre );
753 : #endif
754 34193636 : }
755 :
756 10900414 : FD_BLAKE3_TRACE(( "fd_blake3_fini_2048: done" ));
757 10900414 : return hash;
758 10900414 : }
759 :
760 : void *
761 : fd_blake3_hash( void const * data,
762 : ulong sz,
763 25977 : void * hash ) {
764 :
765 25977 : fd_blake3_buf_t tbl[1];
766 25977 : fd_blake3_pos_t s[1];
767 25977 : fd_blake3_pos_init( s, data, sz );
768 :
769 25977 : #if FD_BLAKE3_PARA_MAX>1
770 1318486 : for(;;) {
771 1318486 : fd_blake3_op_t op[1];
772 1318486 : if( !fd_blake3_prepare_fast( s, tbl, op, FD_BLAKE3_PARA_MAX, 4 ) )
773 25977 : break;
774 251627 : #if FD_HAS_AVX512
775 251627 : fd_blake3_avx512_compress16_fast( op->msg, op->out, op->counter, op->flags );
776 : #elif FD_HAS_AVX
777 1040882 : fd_blake3_avx_compress8_fast( op->msg, op->out, op->counter, op->flags );
778 : #else
779 : #error "missing para support"
780 : #endif
781 1292509 : }
782 25977 : #endif
783 :
784 25977 : void const * hash_ = fd_blake3_single_hash( s, tbl );
785 25977 : memcpy( hash, hash_, 32UL );
786 25977 : return hash;
787 25977 : }
788 :
789 : #if FD_HAS_AVX
790 :
791 : void
792 : fd_blake3_lthash_batch8(
793 : void const * batch_data[8], /* align=32 ele_align=1 */
794 : uint const batch_sz [8], /* align=32 */
795 : void * out_lthash /* align=32 */
796 1378478 : ) {
797 1378478 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)batch_data, 32 ) ) ) {
798 0 : FD_LOG_ERR(( "misaligned batch_data: %p", (void *)batch_data ));
799 0 : }
800 1378478 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)batch_sz, 32 ) ) ) {
801 0 : FD_LOG_ERR(( "misaligned batch_sz: %p", (void *)batch_sz ));
802 0 : }
803 1378478 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)out_lthash, 32 ) ) ) {
804 0 : FD_LOG_ERR(( "misaligned out_lthash: %p", (void *)out_lthash ));
805 0 : }
806 :
807 1378478 : ulong batch_ctr [ 8 ] = {0};
808 12406302 : uint batch_flags[ 8 ]; for( uint i=0; i<8; i++ ) batch_flags[ i ] = FD_BLAKE3_FLAG_ROOT;
809 1378478 : fd_blake3_avx_compress8( 8UL, batch_data, batch_sz, batch_ctr, batch_flags, NULL, out_lthash, 32U, NULL );
810 1378478 : }
811 :
812 : #endif
813 :
814 : #if FD_HAS_AVX512
815 :
816 : void
817 : fd_blake3_lthash_batch16(
818 : void const * batch_data[16], /* align=32 ele_align=1 */
819 : uint const batch_sz [16], /* align=32 */
820 : void * out_lthash /* align=32 */
821 369256 : ) {
822 369256 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)batch_data, 64 ) ) ) {
823 0 : FD_LOG_ERR(( "misaligned batch_data: %p", (void *)batch_data ));
824 0 : }
825 369256 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)batch_sz, 64 ) ) ) {
826 0 : FD_LOG_ERR(( "misaligned batch_sz: %p", (void *)batch_sz ));
827 0 : }
828 369256 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)out_lthash, 64 ) ) ) {
829 0 : FD_LOG_ERR(( "misaligned out_lthash: %p", (void *)out_lthash ));
830 0 : }
831 :
832 369256 : ulong batch_ctr [ 16 ] = {0};
833 6277352 : uint batch_flags[ 16 ]; for( uint i=0; i<16; i++ ) batch_flags[ i ] = FD_BLAKE3_FLAG_ROOT;
834 369256 : fd_blake3_avx512_compress16( 16UL, batch_data, batch_sz, batch_ctr, batch_flags, NULL, out_lthash, 32U, NULL );
835 369256 : }
836 :
837 : #endif
|
