Line data Source code
1 : /* Declares conversion functions to/from base58 for a specific size of
2 : binary data.
3 :
4 : To use this template, define:
5 :
6 : N: the length of the binary data (in bytes) to convert. N must be
7 : 32 or 64 in the current implementation.
8 : INTERMEDIATE_SZ: ceil(log_(58^5) ( (256^N) - 1)). In an ideal
9 : world, this could be computed from N, but there's no way the
10 : preprocessor can do math like that.
11 : BINARY_SIZE: N/4. Define it yourself to facilitate declaring the
12 : required tables.
13 :
14 : INTERMEDIATE_SZ and BINARY_SZ should expand to ulongs while N should
15 : be an integer literal.
16 :
17 : Expects that enc_table_N, dec_table_N, and FD_BASE58_ENCODED_N_SZ
18 : exist (substituting the numeric value of N).
19 :
20 : This file is safe for inclusion multiple times. */
21 :
22 771 : #define BYTE_CNT ((ulong) N)
23 17771280 : #define SUFFIX(s) FD_EXPAND_THEN_CONCAT3(s,_,N)
24 17118 : #define ENCODED_SZ() FD_EXPAND_THEN_CONCAT3(FD_BASE58_ENCODED_, N, _SZ)
25 572532 : #define RAW58_SZ (INTERMEDIATE_SZ*5UL)
26 :
27 : #if FD_HAS_AVX
28 277101 : #define INTERMEDIATE_SZ_W_PADDING FD_ULONG_ALIGN_UP( INTERMEDIATE_SZ, 4UL )
29 : #else
30 : #define INTERMEDIATE_SZ_W_PADDING INTERMEDIATE_SZ
31 : #endif
32 :
33 : char *
34 : SUFFIX(fd_base58_encode)( uchar const * bytes,
35 : ulong * opt_len,
36 277101 : char * out ){
37 :
38 : /* Count leading zeros (needed for final output) */
39 277101 : #if FD_HAS_AVX
40 : # if N==32
41 277059 : wuc_t _bytes = wuc_ldu( bytes );
42 : ulong in_leading_0s = count_leading_zeros_32( _bytes );
43 : # elif N==64
44 42 : wuc_t bytes_0 = wuc_ldu( bytes );
45 42 : wuc_t bytes_1 = wuc_ldu( bytes+32UL );
46 : ulong in_leading_0s = count_leading_zeros_64( bytes_0, bytes_1 );
47 : # endif
48 : #else
49 :
50 : ulong in_leading_0s = 0UL;
51 : for( ; in_leading_0s<BYTE_CNT; in_leading_0s++ ) if( bytes[ in_leading_0s ] ) break;
52 : #endif
53 :
54 : /* X = sum_i bytes[i] * 2^(8*(BYTE_CNT-1-i)) */
55 :
56 : /* Convert N to 32-bit limbs:
57 : X = sum_i binary[i] * 2^(32*(BINARY_SZ-1-i)) */
58 277101 : uint binary[ BINARY_SZ ];
59 2494245 : for( ulong i=0UL; i<BINARY_SZ; i++ ) binary[ i ] = fd_uint_bswap( fd_uint_load_4( &bytes[ i*sizeof(uint) ] ) );
60 :
61 277101 : ulong R1div = 656356768UL; /* = 58^5 */
62 :
63 : /* Convert to the intermediate format:
64 : X = sum_i intermediate[i] * 58^(5*(INTERMEDIATE_SZ-1-i))
65 : Initially, we don't require intermediate[i] < 58^5, but we do want
66 : to make sure the sums don't overflow. */
67 :
68 277101 : #if FD_HAS_AVX
69 277101 : ulong W_ATTR intermediate[ INTERMEDIATE_SZ_W_PADDING ];
70 : #else
71 : ulong intermediate[ INTERMEDIATE_SZ_W_PADDING ];
72 : #endif
73 :
74 277101 : fd_memset( intermediate, 0, INTERMEDIATE_SZ_W_PADDING * sizeof(ulong) );
75 :
76 : # if N==32
77 :
78 : /* The worst case is if binary[7] is (2^32)-1. In that case
79 : intermediate[8] will be be just over 2^63, which is fine. */
80 :
81 2493531 : for( ulong i=0UL; i < BINARY_SZ; i++ )
82 19948248 : for( ulong j=0UL; j < INTERMEDIATE_SZ-1UL; j++ )
83 17731776 : intermediate[ j+1UL ] += (ulong)binary[ i ] * (ulong)SUFFIX(enc_table)[ i ][ j ];
84 :
85 : # elif N==64
86 :
87 : /* If we do it the same way as the 32B conversion, intermediate[16]
88 : can overflow when the input is sufficiently large. We'll do a
89 : mini-reduction after the first 8 steps. After the first 8 terms,
90 : the largest intermediate[16] can be is 2^63.87. Then, after
91 : reduction it'll be at most 58^5, and after adding the last terms,
92 : it won't exceed 2^63.1. We do need to be cautious that the
93 : mini-reduction doesn't cause overflow in intermediate[15] though.
94 : Pre-mini-reduction, it's at most 2^63.05. The mini-reduction adds
95 : at most 2^64/58^5, which is negligible. With the final terms, it
96 : won't exceed 2^63.69, which is fine. Other terms are less than
97 : 2^63.76, so no problems there. */
98 :
99 378 : for( ulong i=0UL; i < 8UL; i++ )
100 6048 : for( ulong j=0UL; j < INTERMEDIATE_SZ-1UL; j++ )
101 5712 : intermediate[ j+1UL ] += (ulong)binary[ i ] * (ulong)SUFFIX(enc_table)[ i ][ j ];
102 : /* Mini-reduction */
103 : intermediate[ 15 ] += intermediate[ 16 ]/R1div;
104 : intermediate[ 16 ] %= R1div;
105 : /* Finish iterations */
106 378 : for( ulong i=8UL; i < BINARY_SZ; i++ )
107 6048 : for( ulong j=0UL; j < INTERMEDIATE_SZ-1UL; j++ )
108 5712 : intermediate[ j+1UL ] += (ulong)binary[ i ] * (ulong)SUFFIX(enc_table)[ i ][ j ];
109 :
110 : # else
111 : # error "Add support for this N"
112 : # endif
113 :
114 : /* Now we make sure each term is less than 58^5. Again, we have to be
115 : a bit careful of overflow.
116 :
117 : For N==32, in the worst case, as before, intermediate[8] will be
118 : just over 2^63 and intermediate[7] will be just over 2^62.6. In
119 : the first step, we'll add floor(intermediate[8]/58^5) to
120 : intermediate[7]. 58^5 is pretty big though, so intermediate[7]
121 : barely budges, and this is still fine.
122 :
123 : For N==64, in the worst case, the biggest entry in intermediate at
124 : this point is 2^63.87, and in the worst case, we add (2^64-1)/58^5,
125 : which is still about 2^63.87. */
126 :
127 2494287 : for( ulong i=INTERMEDIATE_SZ-1UL; i>0UL; i-- ) {
128 2217186 : intermediate[ i-1UL ] += (intermediate[ i ]/R1div);
129 2217186 : intermediate[ i ] %= R1div;
130 2217186 : }
131 :
132 : #if !FD_HAS_AVX
133 : /* Convert intermediate form to base 58. This form of conversion
134 : exposes tons of ILP, but it's more than the CPU can take advantage
135 : of.
136 : X = sum_i raw_base58[i] * 58^(RAW58_SZ-1-i) */
137 :
138 : uchar raw_base58[ RAW58_SZ ];
139 : for( ulong i=0UL; i<INTERMEDIATE_SZ; i++) {
140 : /* We know intermediate[ i ] < 58^5 < 2^32 for all i, so casting to
141 : a uint is safe. GCC doesn't seem to be able to realize this, so
142 : when it converts ulong/ulong to a magic multiplication, it
143 : generates the single-op 64b x 64b -> 128b mul instruction. This
144 : hurts the CPU's ability to take advantage of the ILP here. */
145 : uint v = (uint)intermediate[ i ];
146 : raw_base58[ 5UL*i+4UL ] = (uchar)((v/1U )%58U);
147 : raw_base58[ 5UL*i+3UL ] = (uchar)((v/58U )%58U);
148 : raw_base58[ 5UL*i+2UL ] = (uchar)((v/3364U )%58U);
149 : raw_base58[ 5UL*i+1UL ] = (uchar)((v/195112U )%58U);
150 : raw_base58[ 5UL*i+0UL ] = (uchar)( v/11316496U); /* We know this one is less than 58 */
151 : }
152 :
153 : /* Finally, actually convert to the string. We have to ignore all the
154 : leading zeros in raw_base58 and instead insert in_leading_0s
155 : leading '1' characters. We can show that raw_base58 actually has
156 : at least in_leading_0s, so we'll do this by skipping the first few
157 : leading zeros in raw_base58. */
158 :
159 : ulong raw_leading_0s = 0UL;
160 : for( ; raw_leading_0s<RAW58_SZ; raw_leading_0s++ ) if( raw_base58[ raw_leading_0s ] ) break;
161 :
162 : /* It's not immediately obvious that raw_leading_0s >= in_leading_0s,
163 : but it's true. In base b, X has floor(log_b X)+1 digits. That
164 : means in_leading_0s = N-1-floor(log_256 X) and raw_leading_0s =
165 : RAW58_SZ-1-floor(log_58 X). Let X<256^N be given and consider:
166 :
167 : raw_leading_0s - in_leading_0s =
168 : = RAW58_SZ-N + floor( log_256 X ) - floor( log_58 X )
169 : >= RAW58_SZ-N - 1 + ( log_256 X - log_58 X ) .
170 :
171 : log_256 X - log_58 X is monotonically decreasing for X>0, so it
172 : achieves it minimum at the maximum possible value for X, i.e.
173 : 256^N-1.
174 : >= RAW58_SZ-N-1 + log_256(256^N-1) - log_58(256^N-1)
175 :
176 : When N==32, RAW58_SZ is 45, so this gives skip >= 0.29
177 : When N==64, RAW58_SZ is 90, so this gives skip >= 1.59.
178 :
179 : Regardless, raw_leading_0s - in_leading_0s >= 0. */
180 :
181 : ulong skip = raw_leading_0s - in_leading_0s;
182 : for( ulong i=0UL; i<RAW58_SZ-skip; i++ ) out[ i ] = base58_chars[ raw_base58[ skip+i ] ];
183 :
184 : #else /* FD_HAS_AVX */
185 : # if N==32
186 277059 : wl_t intermediate0 = wl_ld( (long*)intermediate );
187 277059 : wl_t intermediate1 = wl_ld( (long*)intermediate+4UL );
188 277059 : wl_t intermediate2 = wl_ld( (long*)intermediate+8UL );
189 277059 : wuc_t raw0 = intermediate_to_raw( intermediate0 );
190 277059 : wuc_t raw1 = intermediate_to_raw( intermediate1 );
191 277059 : wuc_t raw2 = intermediate_to_raw( intermediate2 );
192 :
193 277059 : wuc_t compact0, compact1;
194 277059 : ten_per_slot_down_32( raw0, raw1, raw2, compact0, compact1 );
195 :
196 : ulong raw_leading_0s = count_leading_zeros_45( compact0, compact1 );
197 :
198 277059 : wuc_t base58_0 = raw_to_base58( compact0 );
199 277059 : wuc_t base58_1 = raw_to_base58( compact1 );
200 :
201 : ulong skip = raw_leading_0s - in_leading_0s;
202 : /* We know the final string is between 32 and 44 characters, so skip
203 : has to be in [1, 13].
204 :
205 : Suppose base58_0 is [ a0 a1 a2 ... af | b0 b1 b2 ... bf ] and skip
206 : is 2.
207 : It would be nice if we had something like the 128-bit barrel shifts
208 : we used in ten_per_slot_down, but they require immediates.
209 : Instead, we'll shift each ulong right by (skip%8) bytes:
210 :
211 : [ a2 a3 .. a7 0 0 aa ab .. af 0 0 | b2 b3 .. b7 0 0 ba .. bf 0 0 ]
212 : and maskstore to write just 8 bytes, skipping the first
213 : floor(skip/8) ulongs, to a starting address of out-8*floor(skip/8).
214 :
215 : out
216 : V
217 : [ a2 a3 a4 a5 a6 a7 0 0 -- -- ... ]
218 :
219 : Now we use another maskstore on the original base58_0, masking out
220 : the first floor(skip/8)+1 ulongs, and writing to out-skip:
221 : out
222 : V
223 : [ -- -- -- -- -- -- -- -- a8 a9 aa ab ... bd be bf ]
224 :
225 : Finally, we need to write the low 13 bytes from base58_1 and a '\0'
226 : terminator, starting at out-skip+32. The easiest way to do this is
227 : actually to shift in 3 more bytes, write the full 16B and do it
228 : prior to the previous write:
229 : out-skip+29
230 : V
231 : [ 0 0 0 c0 c1 c2 .. cc ]
232 : */
233 277059 : wl_t w_skip = wl_bcast( (long)skip );
234 277059 : wl_t mod8_mask = wl_bcast( 7L );
235 277059 : wl_t compare = wl( 0L, 1L, 2L, 3L );
236 :
237 277059 : wl_t shift_qty = wl_shl( wl_and( w_skip, mod8_mask ), 3 ); /* bytes->bits */
238 277059 : wl_t shifted = wl_shru_vector( base58_0, shift_qty );
239 277059 : wl_t skip_div8 = wl_shru( w_skip, 3 );
240 :
241 277059 : wc_t mask1 = wl_eq( skip_div8, compare );
242 : _mm256_maskstore_epi64( (long long int*)(out - 8UL*(skip/8UL)), mask1, shifted );
243 :
244 : __m128i last = _mm_bslli_si128( _mm256_extractf128_si256( base58_1, 0 ), 3 );
245 : _mm_storeu_si128( (__m128i*)(out+29UL-skip), last);
246 :
247 277059 : wc_t mask2 = wl_gt( compare, skip_div8 );
248 : _mm256_maskstore_epi64( (long long int*)(out - skip), mask2, base58_0 );
249 :
250 : # elif N==64
251 42 : wuc_t raw0 = intermediate_to_raw( wl_ld( (long*)intermediate ) );
252 42 : wuc_t raw1 = intermediate_to_raw( wl_ld( (long*)intermediate+4UL ) );
253 42 : wuc_t raw2 = intermediate_to_raw( wl_ld( (long*)intermediate+8UL ) );
254 42 : wuc_t raw3 = intermediate_to_raw( wl_ld( (long*)intermediate+12UL ) );
255 42 : wuc_t raw4 = intermediate_to_raw( wl_ld( (long*)intermediate+16UL ) );
256 :
257 42 : wuc_t compact0, compact1, compact2;
258 42 : ten_per_slot_down_64( raw0, raw1, raw2, raw3, raw4, compact0, compact1, compact2 );
259 :
260 : ulong raw_leading_0s_part1 = count_leading_zeros_64( compact0, compact1 );
261 : ulong raw_leading_0s_part2 = count_leading_zeros_26( compact2 );
262 : ulong raw_leading_0s = fd_ulong_if( raw_leading_0s_part1<64UL, raw_leading_0s_part1, 64UL+raw_leading_0s_part2 );
263 :
264 42 : wuc_t base58_0 = raw_to_base58( compact0 );
265 42 : wuc_t base58_1 = raw_to_base58( compact1 );
266 42 : wuc_t base58_2 = raw_to_base58( compact2 );
267 :
268 : ulong skip = raw_leading_0s - in_leading_0s;
269 : /* We'll do something similar. The final string is between 64 and 88
270 : characters, so skip is [2, 26].
271 : */
272 42 : wl_t w_skip = wl_bcast( (long)skip );
273 42 : wl_t mod8_mask = wl_bcast( 7L );
274 42 : wl_t compare = wl( 0L, 1L, 2L, 3L );
275 :
276 42 : wl_t shift_qty = wl_shl( wl_and( w_skip, mod8_mask ), 3 ); /* bytes->bits */
277 42 : wl_t shifted = wl_shru_vector( base58_0, shift_qty );
278 42 : wl_t skip_div8 = wl_shru( w_skip, 3 );
279 :
280 42 : wc_t mask1 = wl_eq( skip_div8, compare );
281 42 : wc_t mask2 = wl_gt( compare, skip_div8 );
282 : _mm256_maskstore_epi64( (long long int*)(out - 8UL*(skip/8UL)), mask1, shifted );
283 :
284 : _mm256_maskstore_epi64( (long long int*)(out - skip), mask2, base58_0 );
285 :
286 : wuc_stu( (uchar*)out+32UL-skip, base58_1 );
287 :
288 : __m128i last = _mm_bslli_si128( _mm256_extractf128_si256( base58_2, 1 ), 6 );
289 : _mm_storeu_si128( (__m128i*)(out+64UL+16UL-6UL-skip), last );
290 : _mm_storeu_si128( (__m128i*)(out+64UL-skip), _mm256_extractf128_si256( base58_2, 0 ) );
291 : # endif
292 277101 : #endif
293 :
294 277101 : out[ RAW58_SZ-skip ] = '\0';
295 277101 : fd_ulong_store_if( !!opt_len, opt_len, RAW58_SZ-skip );
296 277101 : return out;
297 277101 : }
298 :
299 : uchar *
300 : SUFFIX(fd_base58_decode)( char const * encoded,
301 390 : uchar * out ) {
302 :
303 : /* Validate string and count characters before the nul terminator */
304 :
305 390 : ulong char_cnt = 0UL;
306 17118 : for( ; char_cnt<ENCODED_SZ(); char_cnt++ ) {
307 17118 : char c = encoded[ char_cnt ];
308 17118 : if( !c ) break;
309 : /* If c<'1', this will underflow and idx will be huge */
310 16728 : ulong idx = (ulong)(uchar)c - (ulong)BASE58_INVERSE_TABLE_OFFSET;
311 16728 : idx = fd_ulong_min( idx, BASE58_INVERSE_TABLE_SENTINEL );
312 16728 : if( FD_UNLIKELY( base58_inverse[ idx ] == BASE58_INVALID_CHAR ) ) return NULL;
313 16728 : }
314 :
315 390 : if( FD_UNLIKELY( char_cnt == ENCODED_SZ() ) ) return NULL; /* too long */
316 :
317 : /* X = sum_i raw_base58[i] * 58^(RAW58_SZ-1-i) */
318 :
319 390 : uchar raw_base58[ RAW58_SZ ];
320 :
321 : /* Prepend enough 0s to make it exactly RAW58_SZ characters */
322 :
323 390 : ulong prepend_0 = RAW58_SZ-char_cnt;
324 17940 : for( ulong j=0UL; j<RAW58_SZ; j++ )
325 17550 : raw_base58[ j ] = (j<prepend_0) ? (uchar)0 : base58_inverse[ encoded[ j-prepend_0 ] - BASE58_INVERSE_TABLE_OFFSET ];
326 :
327 : /* Convert to the intermediate format (base 58^5):
328 : X = sum_i intermediate[i] * 58^(5*(INTERMEDIATE_SZ-1-i)) */
329 :
330 390 : ulong intermediate[ INTERMEDIATE_SZ ];
331 3900 : for( ulong i=0UL; i<INTERMEDIATE_SZ; i++ )
332 3510 : intermediate[ i ] = (ulong)raw_base58[ 5UL*i+0UL ] * 11316496UL +
333 3510 : (ulong)raw_base58[ 5UL*i+1UL ] * 195112UL +
334 3510 : (ulong)raw_base58[ 5UL*i+2UL ] * 3364UL +
335 3510 : (ulong)raw_base58[ 5UL*i+3UL ] * 58UL +
336 3510 : (ulong)raw_base58[ 5UL*i+4UL ] * 1UL;
337 :
338 :
339 : /* Using the table, convert to overcomplete base 2^32 (terms can be
340 : larger than 2^32). We need to be careful about overflow.
341 :
342 : For N==32, the largest anything in binary can get is binary[7]:
343 : even if intermediate[i]==58^5-1 for all i, then binary[7] < 2^63.
344 :
345 : For N==64, the largest anything in binary can get is binary[13]:
346 : even if intermediate[i]==58^5-1 for all i, then binary[13] <
347 : 2^63.998. Hanging in there, just by a thread! */
348 :
349 390 : ulong binary[ BINARY_SZ ];
350 3510 : for( ulong j=0UL; j<BINARY_SZ; j++ ) {
351 3120 : ulong acc=0UL;
352 31200 : for( ulong i=0UL; i<INTERMEDIATE_SZ; i++ )
353 28080 : acc += (ulong)intermediate[ i ] * (ulong)SUFFIX(dec_table)[ i ][ j ];
354 3120 : binary[ j ] = acc;
355 3120 : }
356 :
357 : /* Make sure each term is less than 2^32.
358 :
359 : For N==32, we have plenty of headroom in binary, so overflow is
360 : not a concern this time.
361 :
362 : For N==64, even if we add 2^32 to binary[13], it is still 2^63.998,
363 : so this won't overflow. */
364 :
365 3120 : for( ulong i=BINARY_SZ-1UL; i>0UL; i-- ) {
366 2730 : binary[ i-1UL ] += (binary[i] >> 32);
367 2730 : binary[ i ] &= 0xFFFFFFFFUL;
368 2730 : }
369 :
370 : /* If the largest term is 2^32 or bigger, it means N is larger than
371 : what can fit in BYTE_CNT bytes. This can be triggered, by passing
372 : a base58 string of all 'z's for example. */
373 :
374 390 : if( FD_UNLIKELY( binary[ 0UL ] > 0xFFFFFFFFUL ) ) return NULL;
375 :
376 : /* Convert each term to big endian for the final output */
377 :
378 390 : uint * out_as_uint = (uint*)out;
379 3510 : for( ulong i=0UL; i<BINARY_SZ; i++ ) {
380 3120 : FD_STORE( uint, &out_as_uint[ i ], fd_uint_bswap( (uint)binary[ i ] ) );
381 3120 : }
382 : /* Make sure the encoded version has the same number of leading '1's
383 : as the decoded version has leading 0s. The check doesn't read past
384 : the end of encoded, because '\0' != '1', so it will return NULL. */
385 :
386 390 : ulong leading_zero_cnt = 0UL;
387 771 : for( ; leading_zero_cnt<BYTE_CNT; leading_zero_cnt++ ) {
388 762 : if( out[ leading_zero_cnt ] ) break;
389 381 : if( FD_UNLIKELY( encoded[ leading_zero_cnt ] != '1' ) ) return NULL;
390 381 : }
391 390 : if( FD_UNLIKELY( encoded[ leading_zero_cnt ] == '1' ) ) return NULL;
392 390 : return out;
393 390 : }
394 :
395 : #undef RAW58_SZ
396 : #undef ENCODED_SZ
397 : #undef SUFFIX
398 :
399 : #undef BINARY_SZ
400 : #undef BYTE_CNT
401 : #undef INTERMEDIATE_SZ
402 : #undef N
|
