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