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 8041 : ulong sz ) {
10 8041 : *s = (fd_blake3_pos_t) {
11 8041 : .input = data,
12 8041 : .input_sz = sz,
13 8041 : .magic = FD_BLAKE3_MAGIC,
14 8041 : };
15 8041 : return s;
16 8041 : }
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 324409 : fd_blake3_l0_complete( fd_blake3_pos_t const * s ) {
23 324409 : return ( s->leaf_idx<<FD_BLAKE3_CHUNK_LG_SZ ) >= fd_ulong_max( s->input_sz, 64 );
24 324409 : }
25 :
26 : FD_FN_PURE static inline int
27 : fd_blake3_is_finished( fd_blake3_pos_t const * s,
28 141752 : ulong tick ) {
29 141752 : int l0_complete = fd_blake3_l0_complete( s );
30 141752 : int ln_complete = s->live_cnt == 1UL;
31 141752 : int idle = tick >= s->next_tick;
32 141752 : return l0_complete & ln_complete & idle;
33 141752 : }
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 19005 : ulong tick ) {
40 :
41 19005 : ulong msg_off = s->leaf_idx << FD_BLAKE3_CHUNK_LG_SZ;
42 19005 : ulong msg_sz = fd_ulong_min( s->input_sz - msg_off, 1024UL );
43 19005 : uchar const * msg = s->input + msg_off;
44 19005 : uchar * out = buf->slots[ s->layer ][ s->head.uc[ s->layer ] ];
45 :
46 19005 : int flags = fd_int_if( s->input_sz <= FD_BLAKE3_CHUNK_SZ, FD_BLAKE3_FLAG_ROOT, 0 );
47 :
48 19005 : *op = (fd_blake3_op_t) {
49 19005 : .msg = msg,
50 19005 : .out = out,
51 19005 : .counter = s->leaf_idx,
52 19005 : .sz = (ushort)msg_sz,
53 19005 : .flags = (uchar)flags
54 19005 : };
55 :
56 19005 : s->head.uc[ 0 ] = (uchar)( s->head.uc[ 0 ]+1 );
57 19005 : s->leaf_idx++;
58 19005 : s->live_cnt++;
59 19005 : s->next_tick = tick+1;
60 :
61 19005 : return op;
62 :
63 19005 : }
64 :
65 : static int
66 : fd_blake3_seek_branch( fd_blake3_pos_t * restrict s,
67 : fd_blake3_buf_t * restrict buf,
68 122927 : ulong tick ) {
69 :
70 122927 : if( s->live_cnt == 1UL )
71 0 : return 0;
72 :
73 122927 : if( !fd_blake3_l0_complete( s ) )
74 58597 : return ( s->tail.uc[ s->layer - 1 ] + 1 ) <
75 58597 : ( s->head.uc[ s->layer - 1 ] );
76 :
77 64330 : # if FD_HAS_AVX
78 :
79 64330 : wb_t diff = wb_sub( wb_ld( s->head.uc ), wb_ld( s->tail.uc ) );
80 :
81 64330 : uint mergeable_layers = (uint)_mm256_movemask_epi8( wb_gt( diff, wb_bcast( 1 ) ) );
82 64330 : int merge_layer = fd_uint_find_lsb_w_default( mergeable_layers, -1 );
83 64330 : if( merge_layer>=0 ) {
84 55928 : if( ((uint)merge_layer >= s->layer) & (tick < s->next_tick) )
85 8985 : return 0; /* still waiting for previous merge */
86 46943 : s->layer = (uint)merge_layer+1U;
87 46943 : return 1;
88 55928 : }
89 :
90 8402 : uint single_layers = (uint)_mm256_movemask_epi8( wb_eq( diff, wb_bcast( 1 ) ) );
91 8402 : uint single_lo = (uint)fd_uint_find_lsb( single_layers );
92 8402 : uint single_hi = (uint)fd_uint_find_lsb( single_layers & ( ~fd_uint_mask_lsb( (int)(single_lo+1U) ) ) );
93 :
94 8402 : wb_t node = wb_ld( buf->slots[ single_lo ][ s->tail.uc[ single_lo ] ] );
95 8402 : 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 8402 : FD_BLAKE3_TRACE(( "fd_blake3_seek_branch: moving up %u/%u to %u/%u",
140 8402 : single_lo, s->tail.uc[ single_lo ],
141 8402 : single_hi, s->head.uc[ single_hi ] ));
142 :
143 8402 : if( ((uint)single_hi >= s->layer) & (tick < s->next_tick) )
144 3633 : return 0; /* still waiting for previous merge */
145 :
146 4769 : s->head.uc[ single_lo ] = (uchar)( s->head.uc[ single_lo ]-1 );
147 4769 : s->head.uc[ single_hi ] = (uchar)( s->head.uc[ single_hi ]+1 );
148 :
149 4769 : s->layer = (uint)single_hi+1U;
150 4769 : return 1;
151 8402 : }
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 122933 : ulong tick ) {
158 :
159 122933 : if( !fd_blake3_seek_branch( s, buf, tick ) )
160 12613 : return NULL;
161 :
162 110320 : FD_DCHECK_CRIT( s->layer < FD_BLAKE3_ROW_CNT, "invariant violation" );
163 :
164 110320 : uchar const * msg = buf->slots[ s->layer-1U ][ s->tail.uc[ s->layer-1U ] ];
165 110320 : uchar * out = buf->slots[ s->layer ][ s->head.uc[ s->layer ] ];
166 :
167 110320 : s->head.uc[ s->layer ] = (uchar)( s->head.uc[ s->layer ]+1 );
168 110320 : s->tail.uc[ s->layer-1 ] = (uchar)( s->tail.uc[ s->layer-1 ]+2 );
169 110320 : s->live_cnt--;
170 110320 : s->next_tick = tick+1;
171 :
172 110320 : uint flags = FD_BLAKE3_FLAG_PARENT |
173 110320 : fd_uint_if( s->live_cnt==1UL, FD_BLAKE3_FLAG_ROOT, 0u );
174 :
175 110320 : *op = (fd_blake3_op_t) {
176 110320 : .msg = msg,
177 110320 : .out = out,
178 110320 : .counter = 0UL,
179 110320 : .sz = 64U,
180 110320 : .flags = (uchar)flags
181 110320 : };
182 110320 : return op;
183 :
184 122933 : }
185 :
186 : static void
187 24178 : fd_blake3_advance( fd_blake3_pos_t * restrict s ) {
188 :
189 24178 : # if FD_HAS_AVX
190 :
191 24178 : wb_t tail = wb_ld( s->tail.uc );
192 24178 : wb_t head = wb_ld( s->head.uc );
193 24178 : wb_t mask = wb_eq( tail, head );
194 24178 : wb_st( s->tail.uc, wb_andnot( mask, tail ) );
195 24178 : 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 24178 : if( s->head.uc[ s->layer ]==FD_BLAKE3_COL_CNT ) {
209 2441 : s->layer++;
210 2441 : }
211 21737 : else if( ( s->layer > 0UL ) &&
212 21737 : ( s->tail.uc[ s->layer-1 ] < s->head.uc[ s->layer-1 ] ) ) {
213 : /* pass */
214 4854 : }
215 16883 : else if( fd_blake3_l0_complete( s ) ) {
216 12942 : s->layer++;
217 12942 : }
218 3941 : else if( s->layer > 0UL ) {
219 1221 : s->layer = 0UL;
220 1221 : }
221 :
222 24178 : }
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 141751 : ulong tick ) {
229 :
230 141751 : FD_DCHECK_CRIT( s->layer < FD_BLAKE3_ROW_CNT, "invariant violation" );
231 :
232 141751 : if( fd_blake3_is_finished( s, tick ) )
233 0 : return NULL;
234 :
235 141751 : if( tick >= s->next_tick )
236 24178 : fd_blake3_advance( s );
237 :
238 141751 : if( s->layer != 0 )
239 122933 : return fd_blake3_prepare_branch( s, buf, op, tick );
240 :
241 18818 : if( ( s->head.uc[0] >= FD_BLAKE3_COL_CNT ) |
242 18818 : ( fd_blake3_l0_complete( s ) ) ) {
243 3958 : return NULL;
244 3958 : }
245 :
246 14860 : return fd_blake3_prepare_leaf( s, buf, op, tick );
247 :
248 18818 : }
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 15977 : ulong min ) {
261 :
262 15977 : if( s->layer && s->head.uc[ s->layer-1 ]==FD_BLAKE3_COL_CNT ) {
263 4887 : op->msg = buf->rows[ s->layer-1 ];
264 4887 : op->out = buf->rows[ s->layer ] + (s->head.uc[ s->layer ]<<FD_BLAKE3_OUTCHAIN_LG_SZ);
265 4887 : op->counter = 0UL;
266 4887 : op->flags = FD_BLAKE3_FLAG_PARENT;
267 :
268 : /* Assume that branch layer is fully hashed (up to col cnt) */
269 4887 : s->head.uc[ s->layer-1 ] = 0;
270 4887 : s->head.uc[ s->layer ] = (uchar)( (ulong)s->head.uc[ s->layer ]+n );
271 4887 : s->live_cnt -= n;
272 4887 : s->layer = fd_uint_if( s->head.uc[ s->layer ]==FD_BLAKE3_COL_CNT,
273 4887 : s->layer+1U, 0U );
274 :
275 4887 : return op;
276 4887 : }
277 :
278 11090 : ulong pos = s->leaf_idx << FD_BLAKE3_CHUNK_LG_SZ;
279 11090 : ulong avail = fd_ulong_align_dn( s->input_sz - pos, FD_BLAKE3_CHUNK_SZ ) >> FD_BLAKE3_CHUNK_LG_SZ;
280 11090 : 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 11090 : if( n<min ) return NULL;
286 :
287 11090 : op->msg = s->input + (s->leaf_idx<<FD_BLAKE3_CHUNK_LG_SZ);
288 11090 : op->out = buf->rows[0] + (s->head.uc[0]<<FD_BLAKE3_OUTCHAIN_LG_SZ);
289 11090 : op->counter = s->leaf_idx;
290 11090 : op->flags = 0;
291 :
292 11090 : s->head.uc[0] = (uchar)( (ulong)s->head.uc[0]+n );
293 11090 : s->leaf_idx += n;
294 11090 : s->live_cnt += n;
295 11090 : s->layer = fd_uint_if( s->head.uc[0]==FD_BLAKE3_COL_CNT, 1U, 0U );
296 :
297 11090 : return op;
298 11090 : }
299 :
300 : static void
301 : fd_blake3_batch_hash( fd_blake3_op_t const * ops,
302 18698 : ulong op_cnt ) {
303 18698 : uchar const * batch_data [ FD_BLAKE3_PARA_MAX ] __attribute__((aligned(64)));
304 18698 : uint batch_data_sz[ FD_BLAKE3_PARA_MAX ] = {0};
305 18698 : uchar * batch_hash [ FD_BLAKE3_PARA_MAX ] __attribute__((aligned(64)));
306 18698 : ulong batch_ctr [ FD_BLAKE3_PARA_MAX ];
307 18698 : uint batch_flags [ FD_BLAKE3_PARA_MAX ];
308 140072 : for( ulong j=0UL; j<op_cnt; j++ ) {
309 121374 : batch_data [ j ] = ops[ j ].msg;
310 121374 : batch_hash [ j ] = ops[ j ].out;
311 121374 : batch_data_sz[ j ] = ops[ j ].sz;
312 121374 : batch_ctr [ j ] = ops[ j ].counter;
313 121374 : batch_flags [ j ] = ops[ j ].flags;
314 121374 : }
315 18698 : #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 18698 : if( FD_LIKELY( op_cnt<=8UL ) ) {
321 13285 : fd_blake3_avx_compress8 ( op_cnt, batch_data, batch_data_sz, batch_ctr, batch_flags, fd_type_pun( batch_hash ), NULL, 32U, NULL );
322 13285 : } else {
323 5413 : fd_blake3_avx512_compress16( op_cnt, batch_data, batch_data_sz, batch_ctr, batch_flags, fd_type_pun( batch_hash ), NULL, 32U, NULL );
324 5413 : }
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 18698 : }
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 8041 : fd_blake3_init( fd_blake3_t * sha ) {
437 8041 : FD_BLAKE3_TRACE(( "fd_blake3_init(sha=%p)", (void *)sha ));
438 8041 : fd_blake3_pos_init( &sha->pos, NULL, 0UL );
439 8041 : sha->block_sz = 0UL;
440 8041 : return sha;
441 8041 : }
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 3777 : ulong buf_cnt ) {
450 3777 : s->input = data - (s->leaf_idx << FD_BLAKE3_CHUNK_LG_SZ); /* TODO HACKY!! */
451 14875 : for( ulong i=0UL; i<buf_cnt; i++ ) {
452 11098 : fd_blake3_op_t op[1];
453 15986 : do {
454 15986 : if( !fd_blake3_prepare_fast( s, tbl, op, FD_BLAKE3_PARA_MAX, FD_BLAKE3_PARA_MAX ) )
455 0 : return;
456 15986 : #if FD_HAS_AVX512
457 15986 : 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 15986 : } while( op->flags & FD_BLAKE3_FLAG_PARENT );
466 11098 : }
467 3777 : }
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 39088 : ulong sz ) {
502 :
503 : /* If no data to append, we are done */
504 :
505 39088 : if( FD_UNLIKELY( !sz ) ) return sha;
506 37527 : FD_BLAKE3_TRACE(( "fd_blake3_append(sha=%p,data=%p,sz=%lu)", (void *)sha, _data, sz ));
507 :
508 : /* Unpack inputs */
509 :
510 37527 : fd_blake3_pos_t * s = &sha->pos;
511 37527 : fd_blake3_buf_t * tbl = &sha->buf;
512 37527 : uchar * buf = sha->block;
513 37527 : ulong buf_used = sha->block_sz;
514 :
515 37527 : uchar const * data = (uchar const *)_data;
516 :
517 : /* Update input_sz */
518 :
519 37527 : 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 37527 : 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 37527 : 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 29511 : ulong buf_rem = FD_BLAKE3_PRIVATE_BUF_MAX - buf_used; /* In (0,FD_BLAKE3_PRIVATE_BUF_MAX) */
538 29511 : if( FD_UNLIKELY( sz < buf_rem ) ) { /* optimize for large append */
539 26964 : fd_memcpy( buf + buf_used, data, sz );
540 26964 : sha->block_sz = buf_used + sz;
541 26964 : return sha;
542 26964 : }
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 2547 : fd_memcpy( buf + buf_used, data, buf_rem );
549 2547 : data += buf_rem;
550 2547 : sz -= buf_rem;
551 :
552 2547 : fd_blake3_append_blocks( s, tbl, buf, 1UL );
553 2547 : sha->block_sz = 0UL;
554 2547 : }
555 :
556 : /* Append the bulk of the data */
557 :
558 10563 : ulong buf_cnt = sz >> FD_BLAKE3_PRIVATE_LG_BUF_MAX;
559 10563 : 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 10563 : buf_used = sz & (FD_BLAKE3_PRIVATE_BUF_MAX-1UL); /* In [0,FD_BLAKE3_PRIVATE_BUF_MAX) */
564 10599 : if( FD_UNLIKELY( buf_used ) ) { /* optimized for well aligned use of append */
565 10599 : fd_memcpy( buf, data + (buf_cnt << FD_BLAKE3_PRIVATE_LG_BUF_MAX), buf_used );
566 10599 : sha->block_sz = buf_used; /* In (0,FD_BLAKE3_PRIVATE_BUF_MAX) */
567 10599 : }
568 :
569 10563 : FD_BLAKE3_TRACE(( "fd_blake3_append: done" ));
570 10563 : return sha;
571 37527 : }
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 11156 : fd_blake3_fini_xof_setup( fd_blake3_t * sha ) {
632 11156 : fd_blake3_pos_t * s = &sha->pos;
633 11156 : uchar const * buf = sha->block;
634 :
635 : /* TODO HACKY!! */
636 11156 : s->input = buf - ( s->leaf_idx << FD_BLAKE3_CHUNK_LG_SZ );
637 11156 : s->input_sz = ( s->leaf_idx << FD_BLAKE3_CHUNK_LG_SZ ) + sha->block_sz;
638 11156 : }
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 24367 : ulong tick ) {
646 24367 : fd_blake3_pos_t * s = &sha->pos;
647 :
648 24367 : int l0_complete = fd_blake3_l0_complete( s );
649 24367 : int ln_complete = s->live_cnt == 2UL;
650 24367 : if( l0_complete & ln_complete ) return 0UL;
651 :
652 20216 : ulong op_cnt = 0UL;
653 141451 : while( op_cnt<FD_BLAKE3_PARA_MAX ) {
654 137805 : if( !fd_blake3_prepare( s, &sha->buf, ops+op_cnt, tick ) ) break;
655 121235 : op_cnt++;
656 121235 : }
657 20216 : 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 20216 : return op_cnt;
661 20216 : }
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..32] 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 6888 : uchar * root_cv_pre ) {
679 6888 : fd_blake3_pos_t * s = &sha->pos;
680 6888 : fd_blake3_buf_t * tbl = &sha->buf;
681 :
682 6888 : 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 6888 : if( s->input_sz<=FD_BLAKE3_CHUNK_SZ ) {
687 4087 : fd_blake3_op_t op[1];
688 4087 : 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 4087 : #if FD_HAS_SSE
691 4087 : 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 4087 : return;
696 4087 : }
697 :
698 : /* The root block is a branch node. Continue working until there are
699 : only two blocks remaining. */
700 2801 : ulong tick = sha->pos.next_tick+1;
701 19766 : for(;;) {
702 19766 : #if FD_BLAKE3_PARA_MAX>1
703 19766 : fd_blake3_op_t ops[ FD_BLAKE3_PARA_MAX ] = {0};
704 19766 : ulong op_cnt = fd_blake3_fini_xof_prepare( sha, ops, tick );
705 19766 : if( !op_cnt ) break;
706 :
707 16964 : 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 16964 : tick++;
723 16964 : }
724 2801 : }
725 :
726 : static void
727 : fd_blake3_fini_xof_expand( fd_blake3_t * sha,
728 : uchar * root_msg,
729 : uchar * root_cv_pre,
730 8049 : void * hash ) {
731 :
732 : /* Restore root block details */
733 8049 : uint last_block_sz = 64u;
734 8049 : uint last_block_flags = FD_BLAKE3_FLAG_ROOT | FD_BLAKE3_FLAG_PARENT;
735 8049 : ulong ctr0 = 0UL;
736 8049 : if( sha->pos.input_sz<=FD_BLAKE3_CHUNK_SZ ) {
737 4088 : last_block_sz = (uint)sha->pos.input_sz & 63u;
738 4088 : if( fd_ulong_is_aligned( sha->pos.input_sz, 64 ) ) last_block_sz = 64;
739 4088 : if( FD_UNLIKELY( sha->pos.input_sz==0UL ) ) last_block_sz = 0u;
740 4088 : last_block_flags = FD_BLAKE3_FLAG_ROOT | FD_BLAKE3_FLAG_CHUNK_END;
741 4088 : if( sha->pos.input_sz<=FD_BLAKE3_BLOCK_SZ ) last_block_flags |= FD_BLAKE3_FLAG_CHUNK_START;
742 4088 : ctr0 = sha->pos.leaf_idx-1UL;
743 4088 : } else {
744 3961 : fd_blake3_op_t op[1];
745 3961 : 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 3961 : memcpy( root_msg, op->msg, 64UL );
749 3961 : memcpy( root_cv_pre, FD_BLAKE3_IV, 32UL );
750 3961 : }
751 8049 : FD_BLAKE3_TRACE(( "fd_blake3_fini_2048: sz=%lu ctr0=%lu flags=%x",
752 8049 : sha->pos.input_sz, ctr0, last_block_flags ));
753 :
754 : /* Expand LtHash */
755 24130 : for( ulong i=0UL; i<32UL; i+=FD_BLAKE3_PARA_MAX ) {
756 16081 : #if FD_HAS_AVX512
757 16081 : 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 ] __attribute__((aligned(32))); for( ulong j=0; j<8; j++ ) batch_data [ j ] = (ulong)root_msg;
760 : uint batch_sz [ 8 ] __attribute__((aligned(32))); for( ulong j=0; j<8; j++ ) batch_sz [ j ] = last_block_sz;
761 : ulong batch_ctr [ 8 ] __attribute__((aligned(32))); for( ulong j=0; j<8; j++ ) batch_ctr [ j ] = ctr0+i+j;
762 : uint batch_flags[ 8 ] __attribute__((aligned(32))); for( ulong j=0; j<8; j++ ) batch_flags[ j ] = last_block_flags;
763 : void * batch_hash [ 8 ] __attribute__((aligned(32))); for( ulong j=0; j<8; j++ ) batch_hash [ j ] = (uchar *)hash + (i+j)*64;
764 : void * batch_cv [ 8 ] __attribute__((aligned(32))); 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 : fd_blake3_sve2_xof4( root_msg, root_cv_pre, ctr0+i, last_block_sz, last_block_flags, (uchar *)hash + i*64UL );
768 : #elif FD_HAS_SSE
769 : fd_blake3_sse_compress1( (uchar *)hash+i*64, root_msg, last_block_sz, ctr0+i, last_block_flags, NULL, root_cv_pre );
770 : #else
771 : fd_blake3_ref_compress1( (uchar *)hash+i*64, root_msg, last_block_sz, ctr0+i, last_block_flags, NULL, root_cv_pre );
772 : #endif
773 16081 : }
774 8049 : }
775 :
776 : void *
777 : fd_blake3_fini_2048( fd_blake3_t * sha,
778 6889 : void * hash ) {
779 6889 : FD_BLAKE3_TRACE(( "fd_blake3_fini_2048(sha=%p,hash=%p)", (void *)sha, hash ));
780 :
781 6889 : uchar root_msg [ 64 ] __attribute__((aligned(64)));
782 6889 : uchar root_cv_pre[ 32 ] __attribute__((aligned(32)));
783 6889 : fd_blake3_fini_xof_compress( sha, root_msg, root_cv_pre );
784 6889 : fd_blake3_fini_xof_expand( sha, root_msg, root_cv_pre, hash );
785 :
786 6889 : FD_BLAKE3_TRACE(( "fd_blake3_fini_2048: done" ));
787 6889 : return hash;
788 6889 : }
789 :
790 : void
791 : fd_blake3_fini_2048_xn( ulong n,
792 : fd_blake3_t ** sha,
793 2149 : void ** hash ) {
794 2149 : #if FD_BLAKE3_PARA_MAX>1
795 2149 : int single = 0;
796 6418 : for( ulong i=0UL; i<n; i++ ) {
797 4269 : fd_blake3_fini_xof_setup( sha[ i ] );
798 4269 : single |= sha[ i ]->pos.input_sz<=FD_BLAKE3_CHUNK_SZ;
799 4269 : }
800 :
801 2149 : if( FD_UNLIKELY( single ) ) {
802 4678 : for( ulong i=0UL; i<n; i++ ) fd_blake3_fini_2048( sha[ i ], hash[ i ] );
803 1568 : return;
804 1568 : }
805 :
806 581 : ulong tick[ FD_BLAKE3_XN_MAX ];
807 1738 : for( ulong i=0UL; i<n; i++ ) tick[ i ] = sha[ i ]->pos.next_tick+1UL;
808 2304 : for(;;) {
809 2304 : fd_blake3_op_t ops[ FD_BLAKE3_XN_MAX*FD_BLAKE3_PARA_MAX ];
810 2304 : ulong op_cnt = 0UL;
811 6914 : for( ulong i=0UL; i<n; i++ ) op_cnt += fd_blake3_fini_xof_prepare( sha[ i ], ops+op_cnt, tick[ i ]++ );
812 2304 : if( !op_cnt ) break;
813 :
814 3452 : for( ulong off=0UL; off<op_cnt; off+=FD_BLAKE3_PARA_MAX ) {
815 1728 : fd_blake3_batch_hash( ops+off, fd_ulong_min( op_cnt-off, FD_BLAKE3_PARA_MAX ) );
816 1728 : }
817 1724 : }
818 :
819 581 : uchar root_msg [ 64 ] __attribute__((aligned(64)));
820 581 : uchar root_cv_pre[ 32 ] __attribute__((aligned(32)));
821 1740 : for( ulong i=0UL; i<n; i++ ) fd_blake3_fini_xof_expand( sha[ i ], root_msg, root_cv_pre, hash[ i ] );
822 : #else
823 : for( ulong i=0UL; i<n; i++ ) fd_blake3_fini_2048( sha[ i ], hash[ i ] );
824 : #endif
825 581 : }
826 :
827 : void *
828 : fd_blake3_hash( void const * data,
829 : ulong sz,
830 0 : void * hash ) {
831 :
832 0 : fd_blake3_buf_t tbl[1];
833 0 : fd_blake3_pos_t s[1];
834 0 : fd_blake3_pos_init( s, data, sz );
835 :
836 0 : #if FD_BLAKE3_PARA_MAX>1
837 0 : for(;;) {
838 0 : fd_blake3_op_t op[1];
839 0 : if( !fd_blake3_prepare_fast( s, tbl, op, FD_BLAKE3_PARA_MAX, FD_BLAKE3_PARA_MAX ) )
840 0 : break;
841 0 : #if FD_HAS_AVX512
842 0 : fd_blake3_avx512_compress16_fast( op->msg, op->out, op->counter, op->flags );
843 : #elif FD_HAS_AVX
844 : fd_blake3_avx_compress8_fast( op->msg, op->out, op->counter, op->flags );
845 : #elif FD_HAS_SVE2
846 : fd_blake3_sve2_compress4_fast( op->msg, op->out, op->counter, op->flags );
847 : #else
848 : #error "missing para support"
849 : #endif
850 0 : }
851 0 : #endif
852 :
853 0 : void const * hash_ = fd_blake3_single_hash( s, tbl );
854 0 : memcpy( hash, hash_, 32UL );
855 0 : return hash;
856 0 : }
857 :
858 : #if FD_HAS_AVX
859 :
860 : void
861 : fd_blake3_lthash_batch8(
862 : void const * batch_data[8], /* align=32 ele_align=1 */
863 : uint const batch_sz [8], /* align=32 */
864 : void * out_lthash /* align=32 */
865 0 : ) {
866 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)batch_data, 32 ) ) ) {
867 0 : FD_LOG_ERR(( "misaligned batch_data: %p", (void *)batch_data ));
868 0 : }
869 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)batch_sz, 32 ) ) ) {
870 0 : FD_LOG_ERR(( "misaligned batch_sz: %p", (void *)batch_sz ));
871 0 : }
872 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)out_lthash, 32 ) ) ) {
873 0 : FD_LOG_ERR(( "misaligned out_lthash: %p", (void *)out_lthash ));
874 0 : }
875 :
876 0 : ulong batch_ctr [ 8 ] = {0};
877 0 : uint batch_flags[ 8 ]; for( uint i=0; i<8; i++ ) batch_flags[ i ] = FD_BLAKE3_FLAG_ROOT;
878 0 : fd_blake3_avx_compress8( 8UL, batch_data, batch_sz, batch_ctr, batch_flags, NULL, out_lthash, 32U, NULL );
879 0 : }
880 :
881 : #endif
882 :
883 : #if FD_HAS_AVX512
884 :
885 : void
886 : fd_blake3_lthash_batch16(
887 : void const * batch_data[16], /* align=64 ele_align=1 */
888 : uint const batch_sz [16], /* align=64 */
889 : void * out_lthash /* align=64 */
890 0 : ) {
891 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)batch_data, 64 ) ) ) {
892 0 : FD_LOG_ERR(( "misaligned batch_data: %p", (void *)batch_data ));
893 0 : }
894 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)batch_sz, 64 ) ) ) {
895 0 : FD_LOG_ERR(( "misaligned batch_sz: %p", (void *)batch_sz ));
896 0 : }
897 0 : if( FD_UNLIKELY( !fd_ulong_is_aligned( (ulong)out_lthash, 64 ) ) ) {
898 0 : FD_LOG_ERR(( "misaligned out_lthash: %p", (void *)out_lthash ));
899 0 : }
900 :
901 0 : ulong batch_ctr [ 16 ] = {0};
902 0 : uint batch_flags[ 16 ]; for( uint i=0; i<16; i++ ) batch_flags[ i ] = FD_BLAKE3_FLAG_ROOT;
903 0 : fd_blake3_avx512_compress16( 16UL, batch_data, batch_sz, batch_ctr, batch_flags, NULL, out_lthash, 32U, NULL );
904 0 : }
905 :
906 : #endif
|
