Line data Source code
1 : #ifndef HEADER_fd_src_util_encoders_fd_bincode_h
2 : #define HEADER_fd_src_util_encoders_fd_bincode_h
3 :
4 : #include "../../util/fd_util.h"
5 : #include "../../util/valloc/fd_valloc.h"
6 :
7 : typedef void
8 : (* fd_types_walk_fn_t)( void * self,
9 : void const * arg,
10 : char const * name,
11 : int type,
12 : char const * type_name,
13 : uint level );
14 :
15 : typedef void
16 : (* fd_types_walk_fn_t)( void * self,
17 : void const * arg,
18 : char const * name,
19 : int type,
20 : char const * type_name,
21 : uint level );
22 :
23 : /* Context argument used for encoding */
24 : struct fd_bincode_encode_ctx {
25 : /* Current position in data buffer */
26 : void * data;
27 : /* End of buffer */
28 : void * dataend;
29 : };
30 : typedef struct fd_bincode_encode_ctx fd_bincode_encode_ctx_t;
31 :
32 : /* Context argument used for decoding */
33 : struct fd_bincode_decode_ctx {
34 : /* Current position in data buffer */
35 : void const * data;
36 : /* End of buffer */
37 : void const * dataend;
38 : /* Allocator for dynamic memory */
39 : fd_valloc_t valloc;
40 : };
41 : typedef struct fd_bincode_decode_ctx fd_bincode_decode_ctx_t;
42 :
43 : /* Context argument used for calling "destroy" on a structure */
44 : struct fd_bincode_destroy_ctx {
45 : /* Allocator for dynamic memory */
46 : fd_valloc_t valloc;
47 : };
48 : typedef struct fd_bincode_destroy_ctx fd_bincode_destroy_ctx_t;
49 :
50 305728554 : #define FD_BINCODE_SUCCESS ( 0)
51 55323 : #define FD_BINCODE_ERR_UNDERFLOW (-1001) /* Attempted to read past end of buffer */
52 3 : #define FD_BINCODE_ERR_OVERFLOW (-1002) /* Attempted to write past end of buffer */
53 35115 : #define FD_BINCODE_ERR_ENCODING (-1003) /* Invalid encoding */
54 :
55 : #define FD_BINCODE_PRIMITIVE_STUBS( name, type ) \
56 : static inline int \
57 : fd_bincode_##name##_decode( type * self, \
58 329322 : fd_bincode_decode_ctx_t * ctx ) { \
59 329322 : uchar const * ptr = (uchar const *) ctx->data; \
60 329322 : if ( FD_UNLIKELY((void const *)(ptr + sizeof(type)) > ctx->dataend ) ) \
61 329322 : return FD_BINCODE_ERR_UNDERFLOW; \
62 329322 : memcpy( self, ptr, sizeof(type) ); /* unaligned */ \
63 304713 : ctx->data = ptr + sizeof(type); \
64 304713 : return FD_BINCODE_SUCCESS; \
65 329322 : } \
66 : static inline int \
67 289746 : fd_bincode_##name##_decode_preflight( fd_bincode_decode_ctx_t * ctx ) { \
68 289746 : uchar const * ptr = (uchar const *) ctx->data; \
69 289746 : if ( FD_UNLIKELY((void const *)(ptr + sizeof(type)) > ctx->dataend ) ) \
70 289746 : return FD_BINCODE_ERR_UNDERFLOW; \
71 289746 : ctx->data = ptr + sizeof(type); \
72 288426 : return FD_BINCODE_SUCCESS; \
73 289746 : } \
74 : static inline void \
75 : fd_bincode_##name##_decode_unsafe( type * self, \
76 14702502 : fd_bincode_decode_ctx_t * ctx ) { \
77 14702502 : uchar const * ptr = (uchar const *) ctx->data; \
78 14702502 : memcpy( self, ptr, sizeof(type) ); /* unaligned */ \
79 14702502 : ctx->data = ptr + sizeof(type); \
80 14702502 : } \
81 : static inline int \
82 : fd_bincode_##name##_encode( type self, \
83 75983856 : fd_bincode_encode_ctx_t * ctx ) { \
84 75983856 : uchar * ptr = (uchar *)ctx->data; \
85 75983856 : if ( FD_UNLIKELY((void *)(ptr + sizeof(type)) > ctx->dataend ) ) \
86 75983856 : return FD_BINCODE_ERR_OVERFLOW; \
87 75983856 : memcpy( ptr, &self, sizeof(type) ); /* unaligned */ \
88 75983853 : ctx->data = ptr + sizeof(type); \
89 75983853 : return FD_BINCODE_SUCCESS; \
90 75983856 : }
91 :
92 : FD_BINCODE_PRIMITIVE_STUBS( uint8, uchar )
93 : FD_BINCODE_PRIMITIVE_STUBS( uint16, ushort )
94 : FD_BINCODE_PRIMITIVE_STUBS( uint32, uint )
95 : FD_BINCODE_PRIMITIVE_STUBS( uint64, ulong )
96 : FD_BINCODE_PRIMITIVE_STUBS( int64, long )
97 : #if FD_HAS_INT128
98 : FD_BINCODE_PRIMITIVE_STUBS( uint128, uint128 )
99 : #endif
100 : FD_BINCODE_PRIMITIVE_STUBS( double, double )
101 :
102 : static inline int
103 : fd_bincode_bool_decode( uchar * self,
104 52317 : fd_bincode_decode_ctx_t * ctx ) {
105 :
106 52317 : uchar const * ptr = (uchar const *)ctx->data;
107 52317 : if( FD_UNLIKELY( ptr+1 > (uchar const *)ctx->dataend ) )
108 1956 : return FD_BINCODE_ERR_UNDERFLOW;
109 :
110 50361 : if( FD_UNLIKELY( *ptr & (~1U) ) )
111 2775 : return FD_BINCODE_ERR_ENCODING;
112 :
113 47586 : *self = *ptr;
114 47586 : ctx->data = ptr + 1;
115 :
116 47586 : return FD_BINCODE_SUCCESS;
117 50361 : }
118 :
119 : static inline int
120 35808 : fd_bincode_bool_decode_preflight( fd_bincode_decode_ctx_t * ctx ) {
121 :
122 35808 : uchar const * ptr = (uchar const *)ctx->data;
123 35808 : if( FD_UNLIKELY( ptr+1 > (uchar const *)ctx->dataend ) )
124 42 : return FD_BINCODE_ERR_UNDERFLOW;
125 :
126 35766 : if( FD_UNLIKELY( *ptr & (~1U) ) )
127 759 : return FD_BINCODE_ERR_ENCODING;
128 :
129 35007 : ctx->data = ptr + 1;
130 :
131 35007 : return FD_BINCODE_SUCCESS;
132 35766 : }
133 :
134 : static inline void
135 : fd_bincode_bool_decode_unsafe( uchar * self,
136 74967 : fd_bincode_decode_ctx_t * ctx ) {
137 74967 : fd_bincode_uint8_decode_unsafe( self, ctx );
138 74967 : }
139 :
140 : static inline int
141 : fd_bincode_bool_encode( uchar self,
142 16599 : fd_bincode_encode_ctx_t * ctx ) {
143 :
144 16599 : uchar * ptr = (uchar *)ctx->data;
145 16599 : if ( FD_UNLIKELY( (void *)(ptr + 1) > ctx->dataend ) )
146 0 : return FD_BINCODE_ERR_OVERFLOW;
147 :
148 16599 : *ptr = !!self;
149 16599 : ctx->data = ptr + 1;
150 :
151 16599 : return FD_BINCODE_SUCCESS;
152 16599 : }
153 :
154 : static inline int
155 : fd_bincode_bytes_decode( uchar * self,
156 : ulong len,
157 0 : fd_bincode_decode_ctx_t * ctx ) {
158 0 : uchar * ptr = (uchar *) ctx->data;
159 0 : if ( FD_UNLIKELY((ulong)( (uchar *) ctx->dataend - ptr) < len ) ) // Get wrap-around case right
160 0 : return FD_BINCODE_ERR_UNDERFLOW;
161 0 :
162 0 : fd_memcpy(self, ptr, len);
163 0 : ctx->data = ptr + len;
164 0 :
165 0 : return FD_BINCODE_SUCCESS;
166 0 : }
167 :
168 : static inline int
169 : fd_bincode_bytes_decode_preflight( ulong len,
170 2851896 : fd_bincode_decode_ctx_t * ctx ) {
171 2851896 : uchar * ptr = (uchar *) ctx->data;
172 2851896 : if ( FD_UNLIKELY((ulong)( (uchar *) ctx->dataend - ptr) < len ) ) // Get wrap-around case right
173 26121 : return FD_BINCODE_ERR_UNDERFLOW;
174 :
175 2825775 : ctx->data = ptr + len;
176 :
177 2825775 : return FD_BINCODE_SUCCESS;
178 2851896 : }
179 :
180 : static inline void
181 : fd_bincode_bytes_decode_unsafe( uchar * self,
182 : ulong len,
183 3732072 : fd_bincode_decode_ctx_t * ctx ) {
184 3732072 : uchar * ptr = (uchar *) ctx->data;
185 3732072 : fd_memcpy(self, ptr, len);
186 3732072 : ctx->data = ptr + len;
187 3732072 : }
188 :
189 : static inline int
190 : fd_bincode_bytes_encode( uchar const * self,
191 : ulong len,
192 74718258 : fd_bincode_encode_ctx_t * ctx ) {
193 74718258 : uchar *ptr = (uchar *) ctx->data;
194 74718258 : if ( FD_UNLIKELY((void *) (ptr + len) > ctx->dataend ) )
195 0 : return FD_BINCODE_ERR_OVERFLOW;
196 :
197 74718258 : fd_memcpy(ptr, self, len);
198 74718258 : ctx->data = ptr + len;
199 :
200 74718258 : return FD_BINCODE_SUCCESS;
201 74718258 : }
202 :
203 : /* Alternate versions of fd_cu16_dec to make the function signature more consistent with the
204 : other fd_bincode_decode functions. */
205 : static inline int
206 : fd_bincode_compact_u16_decode( ushort * self,
207 3000 : fd_bincode_decode_ctx_t * ctx ) {
208 3000 : const uchar * ptr = (const uchar*) ctx->data;
209 3000 : if( FD_UNLIKELY( ptr==NULL ) ) {
210 0 : return FD_BINCODE_ERR_UNDERFLOW;
211 0 : }
212 :
213 3000 : if( FD_LIKELY( (void *) (ptr + 1) <= ctx->dataend && !(0x80U & ptr[0]) ) ) {
214 2013 : *self = (ushort)ptr[0];
215 2013 : ctx->data = ptr + 1;
216 2013 : return FD_BINCODE_SUCCESS;
217 2013 : }
218 :
219 987 : if( FD_LIKELY( (void *) (ptr + 2) <= ctx->dataend && !(0x80U & ptr[1]) ) ) {
220 195 : if( FD_UNLIKELY( !ptr[1] ) ) /* Detect non-minimal encoding */
221 21 : return FD_BINCODE_ERR_ENCODING;
222 174 : *self = (ushort)((ulong)(ptr[0]&0x7FUL) + (((ulong)ptr[1])<<7));
223 174 : ctx->data = ptr + 2;
224 174 : return FD_BINCODE_SUCCESS;
225 195 : }
226 :
227 792 : if( FD_LIKELY( (void *) (ptr + 3) <= ctx->dataend && !(0xFCU & ptr[2]) ) ) {
228 66 : if( FD_UNLIKELY( !ptr[2] ) ) /* Detect non-minimal encoding */
229 21 : return FD_BINCODE_ERR_ENCODING;
230 45 : *self = (ushort)((ulong)(ptr[0]&0x7FUL) + (((ulong)(ptr[1]&0x7FUL))<<7) + (((ulong)ptr[2])<<14));
231 45 : ctx->data = ptr + 3;
232 45 : return FD_BINCODE_SUCCESS;
233 66 : }
234 :
235 726 : return FD_BINCODE_ERR_UNDERFLOW;
236 792 : }
237 :
238 : static inline void
239 : fd_bincode_compact_u16_decode_unsafe( ushort * self,
240 1179 : fd_bincode_decode_ctx_t * ctx ) {
241 1179 : const uchar * ptr = (const uchar*) ctx->data;
242 :
243 1179 : if( !(0x80U & ptr[0]) ) {
244 1167 : *self = (ushort)ptr[0];
245 1167 : ctx->data = ptr + 1;
246 1167 : return;
247 1167 : }
248 :
249 12 : if( !(0x80U & ptr[1]) ) {
250 12 : *self = (ushort)((ulong)(ptr[0]&0x7FUL) + (((ulong)ptr[1])<<7));
251 12 : ctx->data = ptr + 2;
252 12 : return;
253 12 : }
254 :
255 0 : *self = (ushort)((ulong)(ptr[0]&0x7FUL) + (((ulong)(ptr[1]&0x7FUL))<<7) + (((ulong)ptr[2])<<14));
256 0 : ctx->data = ptr + 3;
257 0 : }
258 :
259 : static inline int
260 : fd_bincode_compact_u16_encode( ushort const * self,
261 89802 : fd_bincode_encode_ctx_t * ctx ) {
262 89802 : uchar * ptr = (uchar*) ctx->data;
263 89802 : ulong val = *self;
264 :
265 89802 : if ( val < 0x80UL ) {
266 85593 : if ( FD_UNLIKELY((void *) (ptr + 1) > ctx->dataend ) )
267 0 : return FD_BINCODE_ERR_OVERFLOW;
268 85593 : *ptr = (uchar)val;
269 85593 : ctx->data = ptr + 1;
270 85593 : return FD_BINCODE_SUCCESS;
271 85593 : }
272 :
273 4209 : else if ( val < 0x4000UL ) {
274 4209 : if ( FD_UNLIKELY((void *) (ptr + 2) > ctx->dataend ) )
275 0 : return FD_BINCODE_ERR_OVERFLOW;
276 4209 : ptr[0] = (uchar)((val&0x7FUL)|0x80UL);
277 4209 : ptr[1] = (uchar)(val>>7);
278 4209 : ctx->data = ptr + 2;
279 4209 : return FD_BINCODE_SUCCESS;
280 4209 : }
281 :
282 0 : else {
283 0 : if ( FD_UNLIKELY((void *) (ptr + 3) > ctx->dataend ) )
284 0 : return FD_BINCODE_ERR_OVERFLOW;
285 0 : ptr[0] = (uchar)((val&0x7FUL)|0x80UL);
286 0 : ptr[1] = (uchar)(((val>>7)&0x7FUL)|0x80UL);
287 0 : ptr[2] = (uchar)(val>>14);
288 0 : ctx->data = ptr + 3;
289 0 : return FD_BINCODE_SUCCESS;
290 0 : }
291 89802 : }
292 :
293 : static inline ulong
294 0 : fd_bincode_compact_u16_size( ushort const * self ) {
295 0 : ulong val = *self;
296 :
297 0 : if ( val < 0x80UL ) {
298 0 : return 1;
299 0 : }
300 0 : else if ( val < 0x4000UL ) {
301 0 : return 2;
302 0 : }
303 0 : else {
304 0 : return 3;
305 0 : }
306 0 : }
307 :
308 : /* Decodes an integer encoded using the serde_varint algorithm:
309 : https://github.com/solana-labs/solana/blob/master/sdk/program/src/serde_varint.rs
310 :
311 : A variable number of bytes could have been used to encode the integer.
312 : The most significant bit of each byte indicates if more bytes have been used, so we keep consuming until
313 : we reach a byte where the most significant bit is 0.
314 : */
315 : static inline int
316 : fd_bincode_varint_decode( ulong * self,
317 0 : fd_bincode_decode_ctx_t * ctx ) {
318 0 : ulong out = 0UL;
319 0 : uint shift = 0U;
320 0 :
321 0 : while( FD_LIKELY( shift < 64U ) ) {
322 0 :
323 0 : if( FD_UNLIKELY( ctx->data >= ctx->dataend ) )
324 0 : return FD_BINCODE_ERR_UNDERFLOW;
325 0 :
326 0 : uint byte = *(uchar const *)ctx->data;
327 0 : ctx->data = (uchar const *)ctx->data + 1;
328 0 : out |= (byte & 0x7FUL) << shift;
329 0 :
330 0 : if( (byte & 0x80U) == 0U ) {
331 0 : if( (out>>shift) != byte )
332 0 : return FD_BINCODE_ERR_ENCODING;
333 0 : if( byte==0U && (shift!=0U || out!=0UL) )
334 0 : return FD_BINCODE_ERR_ENCODING;
335 0 : *self = out;
336 0 : return FD_BINCODE_SUCCESS;
337 0 : }
338 0 :
339 0 : shift += 7U;
340 0 :
341 0 : }
342 0 :
343 0 : return FD_BINCODE_ERR_ENCODING;
344 0 : }
345 :
346 : static inline int
347 77856 : fd_bincode_varint_decode_preflight( fd_bincode_decode_ctx_t * ctx ) {
348 77856 : ulong out = 0UL;
349 77856 : uint shift = 0U;
350 :
351 215550 : while( FD_LIKELY( shift < 64U ) ) {
352 :
353 215538 : if( FD_UNLIKELY( ctx->data >= ctx->dataend ) )
354 132 : return FD_BINCODE_ERR_UNDERFLOW;
355 :
356 215406 : uint byte = *(uchar const *)ctx->data;
357 215406 : ctx->data = (uchar const *)ctx->data + 1;
358 215406 : out |= (byte & 0x7FUL) << shift;
359 :
360 215406 : if( (byte & 0x80U) == 0U ) {
361 77712 : if( (out>>shift) != byte )
362 15 : return FD_BINCODE_ERR_ENCODING;
363 77697 : if( byte==0U && (shift!=0U || out!=0UL) )
364 117 : return FD_BINCODE_ERR_ENCODING;
365 77580 : return FD_BINCODE_SUCCESS;
366 77697 : }
367 :
368 137694 : shift += 7U;
369 :
370 137694 : }
371 :
372 12 : return FD_BINCODE_ERR_ENCODING;
373 77856 : }
374 :
375 : static inline void
376 : fd_bincode_varint_decode_unsafe( ulong * self,
377 11703 : fd_bincode_decode_ctx_t * ctx ) {
378 11703 : ulong out = 0UL;
379 11703 : uint shift = 0U;
380 :
381 41541 : for(;;) {
382 41541 : uint byte = *(uchar const *)ctx->data;
383 41541 : ctx->data = (uchar const *)ctx->data + 1;
384 41541 : out |= (byte & 0x7FUL) << shift;
385 :
386 41541 : if( (byte & 0x80U) == 0U ) {
387 11703 : *self = out;
388 11703 : return;
389 11703 : }
390 :
391 29838 : shift += 7U;
392 29838 : }
393 11703 : }
394 :
395 : static inline int
396 : fd_bincode_varint_encode( ulong val,
397 0 : fd_bincode_encode_ctx_t * ctx ) {
398 0 : uchar * ptr = (uchar *) ctx->data;
399 0 : while (1) {
400 0 : if ( FD_UNLIKELY((void *) (ptr + 1) > ctx->dataend ) )
401 0 : return FD_BINCODE_ERR_OVERFLOW;
402 0 : if ( val < 0x80UL ) {
403 0 : *(ptr++) = (uchar)val;
404 0 : ctx->data = ptr;
405 0 : return FD_BINCODE_SUCCESS;
406 0 : }
407 0 : *(ptr++) = (uchar)((val&0x7FUL)|0x80UL);
408 0 : val >>= 7;
409 0 : }
410 0 : }
411 :
412 : static inline ulong
413 0 : fd_bincode_varint_size( ulong val ) {
414 0 : ulong sz = 0;
415 0 : while (1) {
416 0 : if ( val < 0x80UL ) {
417 0 : return sz+1;
418 0 : }
419 0 : sz++;
420 0 : val >>= 7;
421 0 : }
422 0 : }
423 :
424 : enum {
425 : /* All meta tags must fit in 6 bits */
426 :
427 : /* Primitive types with an implicit encoding length */
428 : FD_ARCHIVE_META_CHAR = 0x1,
429 : FD_ARCHIVE_META_STRING = 0x2,
430 : FD_ARCHIVE_META_CHAR32 = 0x3,
431 : FD_ARCHIVE_META_DOUBLE = 0x4,
432 : FD_ARCHIVE_META_LONG = 0x5,
433 : FD_ARCHIVE_META_UINT = 0x6,
434 : FD_ARCHIVE_META_UINT128 = 0x7,
435 : FD_ARCHIVE_META_BOOL = 0x8,
436 : FD_ARCHIVE_META_UCHAR = 0x9,
437 : FD_ARCHIVE_META_UCHAR32 = 0xa,
438 : FD_ARCHIVE_META_UCHAR128 = 0xb,
439 : FD_ARCHIVE_META_UCHAR2048 = 0xc,
440 : FD_ARCHIVE_META_ULONG = 0xd,
441 : FD_ARCHIVE_META_USHORT = 0xe,
442 :
443 : /* Meta types which have an encoding length after the short tag */
444 : FD_ARCHIVE_META_STRUCT = 0x21,
445 : FD_ARCHIVE_META_VECTOR = 0x22,
446 : FD_ARCHIVE_META_DEQUE = 0x23,
447 : FD_ARCHIVE_META_MAP = 0x24,
448 : FD_ARCHIVE_META_TREAP = 0x25,
449 : FD_ARCHIVE_META_OPTION = 0x26,
450 : FD_ARCHIVE_META_ARRAY = 0x27,
451 : FD_ARCHIVE_META_STATIC_VECTOR = 0x28,
452 : };
453 :
454 0 : #define FD_ARCHIVE_META_SENTINAL (ushort)0 /* End of structure */
455 :
456 0 : static inline int fd_archive_encode_setup_length( fd_bincode_encode_ctx_t * ctx, void ** offset_out ) {
457 0 : uchar * ptr = (uchar *)ctx->data;
458 0 : if ( FD_UNLIKELY((void *)(ptr + sizeof(uint)) > ctx->dataend ) )
459 0 : return FD_BINCODE_ERR_OVERFLOW;
460 : /* Skip over length for now but make space for it */
461 0 : *offset_out = ptr;
462 0 : ctx->data = ptr + sizeof(uint);
463 0 : return FD_BINCODE_SUCCESS;
464 0 : }
465 :
466 0 : static inline int fd_archive_encode_set_length( fd_bincode_encode_ctx_t * ctx, void * offset ) {
467 0 : *(uint *)offset = (uint)((uchar *)ctx->data - ((uchar *)offset + sizeof(uint)));
468 0 : return FD_BINCODE_SUCCESS;
469 0 : }
470 :
471 0 : static inline int fd_archive_decode_setup_length( fd_bincode_decode_ctx_t * ctx, void ** offset_out ) {
472 0 : uchar * ptr = (uchar *)ctx->data;
473 0 : if ( FD_UNLIKELY((void *)(ptr + sizeof(uint)) > ctx->dataend ) )
474 0 : return FD_BINCODE_ERR_UNDERFLOW;
475 : /* Skip over length for now and verify it later */
476 0 : *offset_out = ptr;
477 0 : ctx->data = ptr + sizeof(uint);
478 0 : return FD_BINCODE_SUCCESS;
479 0 : }
480 :
481 0 : static inline int fd_archive_decode_check_length( fd_bincode_decode_ctx_t * ctx, void * offset ) {
482 0 : if( *(uint *)offset != (uint)((uchar *)ctx->data - ((uchar *)offset + sizeof(uint))) )
483 0 : return FD_BINCODE_ERR_ENCODING;
484 0 : return FD_BINCODE_SUCCESS;
485 0 : }
486 :
487 : int fd_archive_decode_skip_field( fd_bincode_decode_ctx_t * ctx, ushort tag );
488 :
489 : #endif /* HEADER_fd_src_util_encoders_fd_bincode_h */
|
