Line data Source code
1 : #ifndef HEADER_fd_src_ballet_lthash_fd_lthash_adder_h
2 : #define HEADER_fd_src_ballet_lthash_fd_lthash_adder_h
3 :
4 : /* fd_lthash_adder.h is an optimized streaming LtHash adder.
5 :
6 : Uses two forms of SIMD parallelism internally to accelerate LtHash
7 : update throughput (multi-block and multi-message BLAKE3 hashing).
8 : A rate of 5 million LtHash updates per second was previously achieved
9 : on a 3.7 GHz AMD EPYC 9B45 (Zen 5 / Turin).
10 :
11 : Usage is as follows:
12 :
13 : fd_lthash_value_t sum[1];
14 : fd_lthash_zero( sum );
15 : fd_lthash_adder_t adder[1];
16 : fd_lthash_adder_new( adder );
17 : for( ... each value ... ) fd_lthash_adder_push( adder, sum, ... );
18 : fd_lthash_adder_flush( adder, sum );
19 : fd_lthash_adder_delete( adder ); */
20 :
21 : #include "../blake3/fd_blake3.h"
22 : #include "../lthash/fd_lthash.h"
23 :
24 : #define FD_LTHASH_ADDER_ALIGN 64
25 :
26 : #define FD_LTHASH_ADDER_PARA_MAX 16
27 :
28 : #if FD_HAS_AVX512 || FD_HAS_AVX
29 25938645 : #define FD_LTHASH_ADDER_PARA_CNT (FD_BLAKE3_PARA_MAX)
30 : #else
31 : #define FD_LTHASH_ADDER_PARA_CNT (1)
32 : #endif
33 :
34 : struct __attribute__((aligned(FD_LTHASH_ADDER_ALIGN))) fd_lthash_adder {
35 :
36 : uint batch_cnt;
37 :
38 : #if FD_LTHASH_ADDER_PARA_MAX>1
39 :
40 : uchar batch_data[ FD_LTHASH_ADDER_PARA_MAX*FD_BLAKE3_CHUNK_SZ ]
41 : __attribute__((aligned(64)));
42 :
43 : ulong batch_ptrs[ FD_LTHASH_ADDER_PARA_MAX ]
44 : __attribute__((aligned(64)));
45 :
46 : uint batch_sz[ FD_LTHASH_ADDER_PARA_MAX ]
47 : __attribute__((aligned(64)));
48 :
49 : #endif
50 :
51 : };
52 :
53 : typedef struct fd_lthash_adder fd_lthash_adder_t;
54 :
55 : FD_PROTOTYPES_BEGIN
56 :
57 : /* fd_lthash_adder_{new,delete} {initializes,destroys} an lthash_adder. */
58 :
59 : fd_lthash_adder_t *
60 : fd_lthash_adder_new( fd_lthash_adder_t * adder );
61 :
62 : void *
63 : fd_lthash_adder_delete( fd_lthash_adder_t * adder );
64 :
65 : /* fd_lthash_adder_push enqueues the given input for hashing. sum may
66 : or may not be updated with enqueued LtHash additions. */
67 :
68 : static inline void
69 : fd_lthash_adder_push( fd_lthash_adder_t * adder,
70 : fd_lthash_value_t * sum,
71 : void const * input,
72 12830334 : ulong input_sz ) {
73 12830334 : fd_lthash_value_t value[1];
74 12830334 : if( FD_LTHASH_ADDER_PARA_CNT<=1 || FD_UNLIKELY( input_sz>512UL ) ) {
75 9462 : fd_blake3_t blake[1];
76 9462 : fd_blake3_init( blake );
77 9462 : fd_blake3_append( blake, input, input_sz );
78 9462 : fd_blake3_fini_2048( blake, value->bytes );
79 9462 : fd_lthash_add( sum, value );
80 9462 : (void)adder;
81 9462 : return;
82 9462 : }
83 :
84 12820872 : uint batch_idx = adder->batch_cnt++;
85 12820872 : uchar * slot = (uchar *)adder->batch_ptrs[ batch_idx ];
86 12820872 : fd_memcpy( slot, input, input_sz );
87 12820872 : adder->batch_sz[ batch_idx ] = (uint)input_sz;
88 :
89 12820872 : if( batch_idx+1>=FD_LTHASH_ADDER_PARA_CNT ) {
90 266735 : # if FD_HAS_AVX512
91 266735 : fd_blake3_lthash_batch16( (void const **)fd_type_pun_const( adder->batch_ptrs ), adder->batch_sz, value->words );
92 : # elif FD_HAS_AVX
93 : fd_blake3_lthash_batch8 ( (void const **)fd_type_pun_const( adder->batch_ptrs ), adder->batch_sz, value->words );
94 1067724 : # endif
95 1334459 : adder->batch_cnt = 0;
96 1334459 : fd_lthash_add( sum, value );
97 1334459 : }
98 12820872 : }
99 :
100 : /* fd_lthash_adder_flush commits all previously enqueued additions to
101 : sum. */
102 :
103 : static inline void
104 : fd_lthash_adder_flush( fd_lthash_adder_t * adder,
105 4917 : fd_lthash_value_t * sum ) {
106 4917 : # if FD_LTHASH_ADDER_PARA_CNT>1
107 4917 : uint batch_cnt = adder->batch_cnt;
108 27132 : for( uint i=0U; i<batch_cnt; i++ ) {
109 22215 : fd_lthash_value_t value[1];
110 22215 : fd_blake3_t blake[1];
111 22215 : fd_blake3_init( blake );
112 22215 : fd_blake3_append( blake, (void const *)adder->batch_ptrs[ i ], adder->batch_sz[ i ] );
113 22215 : fd_blake3_fini_2048( blake, value->bytes );
114 22215 : fd_lthash_add( sum, value );
115 22215 : }
116 4917 : # endif
117 4917 : adder->batch_cnt = 0U;
118 4917 : (void)sum;
119 4917 : }
120 :
121 : /* fd_lthash_adder_push_solana_account wraps fd_lthash_adder_push for
122 : Solana account inputs. */
123 :
124 : static inline void
125 : fd_lthash_adder_push_solana_account(
126 : fd_lthash_adder_t * adder,
127 : fd_lthash_value_t * sum,
128 : void const * pubkey,
129 : uchar const * data,
130 : ulong data_sz,
131 : ulong lamports,
132 : uchar executable,
133 : void const * owner
134 146565 : ) {
135 146565 : fd_lthash_value_t value[1];
136 : /* FIXME opportunities for memcpy hacks here */
137 :
138 146565 : ulong const static_sz = 73UL;
139 146565 : ulong const batch_threshold = 512UL;
140 146565 : if( FD_LTHASH_ADDER_PARA_CNT<=1 ||
141 146565 : FD_UNLIKELY( data_sz > batch_threshold-static_sz ) ) {
142 9366 : fd_blake3_t blake[1];
143 9366 : fd_blake3_init( blake );
144 9366 : fd_blake3_append( blake, &lamports, sizeof(ulong) );
145 9366 : fd_blake3_append( blake, data, data_sz );
146 9366 : uchar footer[ 65 ];
147 9366 : footer[ 0 ] = executable;
148 9366 : memcpy( footer+1, owner, 32 );
149 9366 : memcpy( footer+33, pubkey, 32 );
150 9366 : fd_blake3_append( blake, footer, sizeof(footer) );
151 9366 : fd_blake3_fini_2048( blake, value->bytes );
152 9366 : fd_lthash_add( sum, value );
153 9366 : return;
154 9366 : }
155 :
156 137199 : uint batch_idx = adder->batch_cnt++;
157 137199 : uchar * slot = (uchar *)adder->batch_ptrs[ batch_idx ];
158 137199 : uchar * p = slot;
159 :
160 : /* Fixed size header */
161 137199 : FD_STORE( ulong, p, lamports );
162 137199 : p += sizeof(ulong);
163 : /* Variable size content */
164 137199 : fd_memcpy( p, data, data_sz );
165 137199 : p += data_sz;
166 : /* Fixed size footer */
167 137199 : p[0] = executable; p += 1;
168 137199 : fd_memcpy( p, owner, 32 ); p += 32;
169 137199 : fd_memcpy( p, pubkey, 32 ); p += 32;
170 :
171 137199 : adder->batch_sz[ batch_idx ] = (uint)( p-slot );
172 :
173 137199 : if( batch_idx+1>=FD_LTHASH_ADDER_PARA_CNT ) {
174 2520 : # if FD_HAS_AVX512
175 2520 : fd_blake3_lthash_batch16( (void const **)fd_type_pun_const( adder->batch_ptrs ), adder->batch_sz, value->words );
176 : # elif FD_HAS_AVX
177 : fd_blake3_lthash_batch8 ( (void const **)fd_type_pun_const( adder->batch_ptrs ), adder->batch_sz, value->words );
178 10748 : # endif
179 13268 : adder->batch_cnt = 0;
180 13268 : fd_lthash_add( sum, value );
181 13268 : }
182 137199 : }
183 :
184 : FD_PROTOTYPES_END
185 :
186 : #endif /* HEADER_fd_src_ballet_lthash_fd_lthash_adder_h */
|
