1 // Fast decoder: ~3x the speed of decode.c, but x86-64 specific.
2 // Also the table size grows by 2x.
3 //
4 // Could potentially be ported to ARM64 or other 64-bit archs that pass at
5 // least six arguments in registers.
6 //
7 // The overall design is to create specialized functions for every possible
8 // field type (eg. oneof boolean field with a 1 byte tag) and then dispatch
9 // to the specialized function as quickly as possible.
10
11 #include "upb/decode_fast.h"
12
13 #include "upb/decode.int.h"
14
15 /* Must be last. */
16 #include "upb/port_def.inc"
17
18 #if UPB_FASTTABLE
19
20 // The standard set of arguments passed to each parsing function.
21 // Thanks to x86-64 calling conventions, these will stay in registers.
22 #define UPB_PARSE_PARAMS \
23 upb_decstate *d, const char *ptr, upb_msg *msg, intptr_t table, \
24 uint64_t hasbits, uint64_t data
25
26 #define UPB_PARSE_ARGS d, ptr, msg, table, hasbits, data
27
28 #define RETURN_GENERIC(m) \
29 /* fprintf(stderr, m); */ \
30 return fastdecode_generic(d, ptr, msg, table, hasbits, 0);
31
32 typedef enum {
33 CARD_s = 0, /* Singular (optional, non-repeated) */
34 CARD_o = 1, /* Oneof */
35 CARD_r = 2, /* Repeated */
36 CARD_p = 3 /* Packed Repeated */
37 } upb_card;
38
39 UPB_NOINLINE
fastdecode_isdonefallback(upb_decstate * d,const char * ptr,upb_msg * msg,intptr_t table,uint64_t hasbits,int overrun)40 static const char *fastdecode_isdonefallback(upb_decstate *d, const char *ptr,
41 upb_msg *msg, intptr_t table,
42 uint64_t hasbits, int overrun) {
43 ptr = decode_isdonefallback_inl(d, ptr, overrun);
44 if (ptr == NULL) {
45 return fastdecode_err(d);
46 }
47 uint16_t tag = fastdecode_loadtag(ptr);
48 return fastdecode_tagdispatch(d, ptr, msg, table, hasbits, tag);
49 }
50
51 UPB_FORCEINLINE
fastdecode_dispatch(upb_decstate * d,const char * ptr,upb_msg * msg,intptr_t table,uint64_t hasbits)52 static const char *fastdecode_dispatch(upb_decstate *d, const char *ptr,
53 upb_msg *msg, intptr_t table,
54 uint64_t hasbits) {
55 if (UPB_UNLIKELY(ptr >= d->limit_ptr)) {
56 int overrun = ptr - d->end;
57 if (UPB_LIKELY(overrun == d->limit)) {
58 // Parse is finished.
59 *(uint32_t*)msg |= hasbits; // Sync hasbits.
60 return ptr;
61 } else {
62 return fastdecode_isdonefallback(d, ptr, msg, table, hasbits, overrun);
63 }
64 }
65
66 // Read two bytes of tag data (for a one-byte tag, the high byte is junk).
67 uint16_t tag = fastdecode_loadtag(ptr);
68 return fastdecode_tagdispatch(d, ptr, msg, table, hasbits, tag);
69 }
70
71 UPB_FORCEINLINE
fastdecode_checktag(uint64_t data,int tagbytes)72 static bool fastdecode_checktag(uint64_t data, int tagbytes) {
73 if (tagbytes == 1) {
74 return (data & 0xff) == 0;
75 } else {
76 return (data & 0xffff) == 0;
77 }
78 }
79
80 UPB_FORCEINLINE
fastdecode_longsize(const char * ptr,int * size)81 static const char *fastdecode_longsize(const char *ptr, int *size) {
82 int i;
83 UPB_ASSERT(*size & 0x80);
84 *size &= 0xff;
85 for (i = 0; i < 3; i++) {
86 ptr++;
87 size_t byte = (uint8_t)ptr[-1];
88 *size += (byte - 1) << (7 + 7 * i);
89 if (UPB_LIKELY((byte & 0x80) == 0)) return ptr;
90 }
91 ptr++;
92 size_t byte = (uint8_t)ptr[-1];
93 // len is limited by 2gb not 4gb, hence 8 and not 16 as normally expected
94 // for a 32 bit varint.
95 if (UPB_UNLIKELY(byte >= 8)) return NULL;
96 *size += (byte - 1) << 28;
97 return ptr;
98 }
99
100 UPB_FORCEINLINE
fastdecode_boundscheck(const char * ptr,size_t len,const char * end)101 static bool fastdecode_boundscheck(const char *ptr, size_t len,
102 const char *end) {
103 uintptr_t uptr = (uintptr_t)ptr;
104 uintptr_t uend = (uintptr_t)end + 16;
105 uintptr_t res = uptr + len;
106 return res < uptr || res > uend;
107 }
108
109 UPB_FORCEINLINE
fastdecode_boundscheck2(const char * ptr,size_t len,const char * end)110 static bool fastdecode_boundscheck2(const char *ptr, size_t len,
111 const char *end) {
112 // This is one extra branch compared to the more normal:
113 // return (size_t)(end - ptr) < size;
114 // However it is one less computation if we are just about to use "ptr + len":
115 // https://godbolt.org/z/35YGPz
116 // In microbenchmarks this shows an overall 4% improvement.
117 uintptr_t uptr = (uintptr_t)ptr;
118 uintptr_t uend = (uintptr_t)end;
119 uintptr_t res = uptr + len;
120 return res < uptr || res > uend;
121 }
122
123 typedef const char *fastdecode_delimfunc(upb_decstate *d, const char *ptr,
124 void *ctx);
125
126 UPB_FORCEINLINE
fastdecode_delimited(upb_decstate * d,const char * ptr,fastdecode_delimfunc * func,void * ctx)127 static const char *fastdecode_delimited(upb_decstate *d, const char *ptr,
128 fastdecode_delimfunc *func, void *ctx) {
129 ptr++;
130 int len = (int8_t)ptr[-1];
131 if (fastdecode_boundscheck2(ptr, len, d->limit_ptr)) {
132 // Slow case: Sub-message is >=128 bytes and/or exceeds the current buffer.
133 // If it exceeds the buffer limit, limit/limit_ptr will change during
134 // sub-message parsing, so we need to preserve delta, not limit.
135 if (UPB_UNLIKELY(len & 0x80)) {
136 // Size varint >1 byte (length >= 128).
137 ptr = fastdecode_longsize(ptr, &len);
138 if (!ptr) {
139 // Corrupt wire format: size exceeded INT_MAX.
140 return NULL;
141 }
142 }
143 if (ptr - d->end + (int)len > d->limit) {
144 // Corrupt wire format: invalid limit.
145 return NULL;
146 }
147 int delta = decode_pushlimit(d, ptr, len);
148 ptr = func(d, ptr, ctx);
149 decode_poplimit(d, ptr, delta);
150 } else {
151 // Fast case: Sub-message is <128 bytes and fits in the current buffer.
152 // This means we can preserve limit/limit_ptr verbatim.
153 const char *saved_limit_ptr = d->limit_ptr;
154 int saved_limit = d->limit;
155 d->limit_ptr = ptr + len;
156 d->limit = d->limit_ptr - d->end;
157 UPB_ASSERT(d->limit_ptr == d->end + UPB_MIN(0, d->limit));
158 ptr = func(d, ptr, ctx);
159 d->limit_ptr = saved_limit_ptr;
160 d->limit = saved_limit;
161 UPB_ASSERT(d->limit_ptr == d->end + UPB_MIN(0, d->limit));
162 }
163 return ptr;
164 }
165
166 /* singular, oneof, repeated field handling ***********************************/
167
168 typedef struct {
169 upb_array *arr;
170 void *end;
171 } fastdecode_arr;
172
173 typedef enum {
174 FD_NEXT_ATLIMIT,
175 FD_NEXT_SAMEFIELD,
176 FD_NEXT_OTHERFIELD
177 } fastdecode_next;
178
179 typedef struct {
180 void *dst;
181 fastdecode_next next;
182 uint32_t tag;
183 } fastdecode_nextret;
184
185 UPB_FORCEINLINE
fastdecode_resizearr(upb_decstate * d,void * dst,fastdecode_arr * farr,int valbytes)186 static void *fastdecode_resizearr(upb_decstate *d, void *dst,
187 fastdecode_arr *farr, int valbytes) {
188 if (UPB_UNLIKELY(dst == farr->end)) {
189 size_t old_size = farr->arr->size;
190 size_t old_bytes = old_size * valbytes;
191 size_t new_size = old_size * 2;
192 size_t new_bytes = new_size * valbytes;
193 char *old_ptr = _upb_array_ptr(farr->arr);
194 char *new_ptr = upb_arena_realloc(&d->arena, old_ptr, old_bytes, new_bytes);
195 uint8_t elem_size_lg2 = __builtin_ctz(valbytes);
196 farr->arr->size = new_size;
197 farr->arr->data = _upb_array_tagptr(new_ptr, elem_size_lg2);
198 dst = (void*)(new_ptr + (old_size * valbytes));
199 farr->end = (void*)(new_ptr + (new_size * valbytes));
200 }
201 return dst;
202 }
203
204 UPB_FORCEINLINE
fastdecode_tagmatch(uint32_t tag,uint64_t data,int tagbytes)205 static bool fastdecode_tagmatch(uint32_t tag, uint64_t data, int tagbytes) {
206 if (tagbytes == 1) {
207 return (uint8_t)tag == (uint8_t)data;
208 } else {
209 return (uint16_t)tag == (uint16_t)data;
210 }
211 }
212
213 UPB_FORCEINLINE
fastdecode_commitarr(void * dst,fastdecode_arr * farr,int valbytes)214 static void fastdecode_commitarr(void *dst, fastdecode_arr *farr,
215 int valbytes) {
216 farr->arr->len =
217 (size_t)((char *)dst - (char *)_upb_array_ptr(farr->arr)) / valbytes;
218 }
219
220 UPB_FORCEINLINE
fastdecode_nextrepeated(upb_decstate * d,void * dst,const char ** ptr,fastdecode_arr * farr,uint64_t data,int tagbytes,int valbytes)221 static fastdecode_nextret fastdecode_nextrepeated(upb_decstate *d, void *dst,
222 const char **ptr,
223 fastdecode_arr *farr,
224 uint64_t data, int tagbytes,
225 int valbytes) {
226 fastdecode_nextret ret;
227 dst = (char *)dst + valbytes;
228
229 if (UPB_LIKELY(!decode_isdone(d, ptr))) {
230 ret.tag = fastdecode_loadtag(*ptr);
231 if (fastdecode_tagmatch(ret.tag, data, tagbytes)) {
232 ret.next = FD_NEXT_SAMEFIELD;
233 } else {
234 fastdecode_commitarr(dst, farr, valbytes);
235 ret.next = FD_NEXT_OTHERFIELD;
236 }
237 } else {
238 fastdecode_commitarr(dst, farr, valbytes);
239 ret.next = FD_NEXT_ATLIMIT;
240 }
241
242 ret.dst = dst;
243 return ret;
244 }
245
246 UPB_FORCEINLINE
fastdecode_fieldmem(upb_msg * msg,uint64_t data)247 static void *fastdecode_fieldmem(upb_msg *msg, uint64_t data) {
248 size_t ofs = data >> 48;
249 return (char *)msg + ofs;
250 }
251
252 UPB_FORCEINLINE
fastdecode_getfield(upb_decstate * d,const char * ptr,upb_msg * msg,uint64_t * data,uint64_t * hasbits,fastdecode_arr * farr,int valbytes,upb_card card)253 static void *fastdecode_getfield(upb_decstate *d, const char *ptr, upb_msg *msg,
254 uint64_t *data, uint64_t *hasbits,
255 fastdecode_arr *farr, int valbytes,
256 upb_card card) {
257 switch (card) {
258 case CARD_s: {
259 uint8_t hasbit_index = *data >> 24;
260 // Set hasbit and return pointer to scalar field.
261 *hasbits |= 1ull << hasbit_index;
262 return fastdecode_fieldmem(msg, *data);
263 }
264 case CARD_o: {
265 uint16_t case_ofs = *data >> 32;
266 uint32_t *oneof_case = UPB_PTR_AT(msg, case_ofs, uint32_t);
267 uint8_t field_number = *data >> 24;
268 *oneof_case = field_number;
269 return fastdecode_fieldmem(msg, *data);
270 }
271 case CARD_r: {
272 // Get pointer to upb_array and allocate/expand if necessary.
273 uint8_t elem_size_lg2 = __builtin_ctz(valbytes);
274 upb_array **arr_p = fastdecode_fieldmem(msg, *data);
275 char *begin;
276 *(uint32_t*)msg |= *hasbits;
277 *hasbits = 0;
278 if (UPB_LIKELY(!*arr_p)) {
279 farr->arr = _upb_array_new(&d->arena, 8, elem_size_lg2);
280 *arr_p = farr->arr;
281 } else {
282 farr->arr = *arr_p;
283 }
284 begin = _upb_array_ptr(farr->arr);
285 farr->end = begin + (farr->arr->size * valbytes);
286 *data = fastdecode_loadtag(ptr);
287 return begin + (farr->arr->len * valbytes);
288 }
289 default:
290 UPB_UNREACHABLE();
291 }
292 }
293
294 UPB_FORCEINLINE
fastdecode_flippacked(uint64_t * data,int tagbytes)295 static bool fastdecode_flippacked(uint64_t *data, int tagbytes) {
296 *data ^= (0x2 ^ 0x0); // Patch data to match packed wiretype.
297 return fastdecode_checktag(*data, tagbytes);
298 }
299
300 /* varint fields **************************************************************/
301
302 UPB_FORCEINLINE
fastdecode_munge(uint64_t val,int valbytes,bool zigzag)303 static uint64_t fastdecode_munge(uint64_t val, int valbytes, bool zigzag) {
304 if (valbytes == 1) {
305 return val != 0;
306 } else if (zigzag) {
307 if (valbytes == 4) {
308 uint32_t n = val;
309 return (n >> 1) ^ -(int32_t)(n & 1);
310 } else if (valbytes == 8) {
311 return (val >> 1) ^ -(int64_t)(val & 1);
312 }
313 UPB_UNREACHABLE();
314 }
315 return val;
316 }
317
318 UPB_FORCEINLINE
fastdecode_varint64(const char * ptr,uint64_t * val)319 static const char *fastdecode_varint64(const char *ptr, uint64_t *val) {
320 ptr++;
321 *val = (uint8_t)ptr[-1];
322 if (UPB_UNLIKELY(*val & 0x80)) {
323 int i;
324 for (i = 0; i < 8; i++) {
325 ptr++;
326 uint64_t byte = (uint8_t)ptr[-1];
327 *val += (byte - 1) << (7 + 7 * i);
328 if (UPB_LIKELY((byte & 0x80) == 0)) goto done;
329 }
330 ptr++;
331 uint64_t byte = (uint8_t)ptr[-1];
332 if (byte > 1) {
333 return NULL;
334 }
335 *val += (byte - 1) << 63;
336 }
337 done:
338 UPB_ASSUME(ptr != NULL);
339 return ptr;
340 }
341
342 UPB_FORCEINLINE
fastdecode_unpackedvarint(UPB_PARSE_PARAMS,int tagbytes,int valbytes,upb_card card,bool zigzag,_upb_field_parser * packed)343 static const char *fastdecode_unpackedvarint(UPB_PARSE_PARAMS, int tagbytes,
344 int valbytes, upb_card card,
345 bool zigzag,
346 _upb_field_parser *packed) {
347 uint64_t val;
348 void *dst;
349 fastdecode_arr farr;
350
351 if (UPB_UNLIKELY(!fastdecode_checktag(data, tagbytes))) {
352 if (card == CARD_r && fastdecode_flippacked(&data, tagbytes)) {
353 return packed(UPB_PARSE_ARGS);
354 }
355 RETURN_GENERIC("varint field tag mismatch\n");
356 }
357
358 dst =
359 fastdecode_getfield(d, ptr, msg, &data, &hasbits, &farr, valbytes, card);
360 if (card == CARD_r) {
361 if (UPB_UNLIKELY(!dst)) {
362 RETURN_GENERIC("need array resize\n");
363 }
364 }
365
366 again:
367 if (card == CARD_r) {
368 dst = fastdecode_resizearr(d, dst, &farr, valbytes);
369 }
370
371 ptr += tagbytes;
372 ptr = fastdecode_varint64(ptr, &val);
373 if (ptr == NULL) return fastdecode_err(d);
374 val = fastdecode_munge(val, valbytes, zigzag);
375 memcpy(dst, &val, valbytes);
376
377 if (card == CARD_r) {
378 fastdecode_nextret ret =
379 fastdecode_nextrepeated(d, dst, &ptr, &farr, data, tagbytes, valbytes);
380 switch (ret.next) {
381 case FD_NEXT_SAMEFIELD:
382 dst = ret.dst;
383 goto again;
384 case FD_NEXT_OTHERFIELD:
385 return fastdecode_tagdispatch(d, ptr, msg, table, hasbits, ret.tag);
386 case FD_NEXT_ATLIMIT:
387 return ptr;
388 }
389 }
390
391 return fastdecode_dispatch(d, ptr, msg, table, hasbits);
392 }
393
394 typedef struct {
395 uint8_t valbytes;
396 bool zigzag;
397 void *dst;
398 fastdecode_arr farr;
399 } fastdecode_varintdata;
400
401 UPB_FORCEINLINE
fastdecode_topackedvarint(upb_decstate * d,const char * ptr,void * ctx)402 static const char *fastdecode_topackedvarint(upb_decstate *d, const char *ptr,
403 void *ctx) {
404 fastdecode_varintdata *data = ctx;
405 void *dst = data->dst;
406 uint64_t val;
407
408 while (!decode_isdone(d, &ptr)) {
409 dst = fastdecode_resizearr(d, dst, &data->farr, data->valbytes);
410 ptr = fastdecode_varint64(ptr, &val);
411 if (ptr == NULL) return NULL;
412 val = fastdecode_munge(val, data->valbytes, data->zigzag);
413 memcpy(dst, &val, data->valbytes);
414 dst = (char *)dst + data->valbytes;
415 }
416
417 fastdecode_commitarr(dst, &data->farr, data->valbytes);
418 return ptr;
419 }
420
421 UPB_FORCEINLINE
fastdecode_packedvarint(UPB_PARSE_PARAMS,int tagbytes,int valbytes,bool zigzag,_upb_field_parser * unpacked)422 static const char *fastdecode_packedvarint(UPB_PARSE_PARAMS, int tagbytes,
423 int valbytes, bool zigzag,
424 _upb_field_parser *unpacked) {
425 fastdecode_varintdata ctx = {valbytes, zigzag};
426
427 if (UPB_UNLIKELY(!fastdecode_checktag(data, tagbytes))) {
428 if (fastdecode_flippacked(&data, tagbytes)) {
429 return unpacked(UPB_PARSE_ARGS);
430 } else {
431 RETURN_GENERIC("varint field tag mismatch\n");
432 }
433 }
434
435 ctx.dst = fastdecode_getfield(d, ptr, msg, &data, &hasbits, &ctx.farr,
436 valbytes, CARD_r);
437 if (UPB_UNLIKELY(!ctx.dst)) {
438 RETURN_GENERIC("need array resize\n");
439 }
440
441 ptr += tagbytes;
442 ptr = fastdecode_delimited(d, ptr, &fastdecode_topackedvarint, &ctx);
443
444 if (UPB_UNLIKELY(ptr == NULL)) {
445 return fastdecode_err(d);
446 }
447
448 return fastdecode_dispatch(d, ptr, msg, table, hasbits);
449 }
450
451 UPB_FORCEINLINE
fastdecode_varint(UPB_PARSE_PARAMS,int tagbytes,int valbytes,upb_card card,bool zigzag,_upb_field_parser * unpacked,_upb_field_parser * packed)452 static const char *fastdecode_varint(UPB_PARSE_PARAMS, int tagbytes,
453 int valbytes, upb_card card, bool zigzag,
454 _upb_field_parser *unpacked,
455 _upb_field_parser *packed) {
456 if (card == CARD_p) {
457 return fastdecode_packedvarint(UPB_PARSE_ARGS, tagbytes, valbytes, zigzag,
458 unpacked);
459 } else {
460 return fastdecode_unpackedvarint(UPB_PARSE_ARGS, tagbytes, valbytes, card,
461 zigzag, packed);
462 }
463 }
464
465 #define z_ZZ true
466 #define b_ZZ false
467 #define v_ZZ false
468
469 /* Generate all combinations:
470 * {s,o,r,p} x {b1,v4,z4,v8,z8} x {1bt,2bt} */
471
472 #define F(card, type, valbytes, tagbytes) \
473 UPB_NOINLINE \
474 const char *upb_p##card##type##valbytes##_##tagbytes##bt(UPB_PARSE_PARAMS) { \
475 return fastdecode_varint(UPB_PARSE_ARGS, tagbytes, valbytes, CARD_##card, \
476 type##_ZZ, \
477 &upb_pr##type##valbytes##_##tagbytes##bt, \
478 &upb_pp##type##valbytes##_##tagbytes##bt); \
479 }
480
481 #define TYPES(card, tagbytes) \
482 F(card, b, 1, tagbytes) \
483 F(card, v, 4, tagbytes) \
484 F(card, v, 8, tagbytes) \
485 F(card, z, 4, tagbytes) \
486 F(card, z, 8, tagbytes)
487
488 #define TAGBYTES(card) \
489 TYPES(card, 1) \
490 TYPES(card, 2)
491
492 TAGBYTES(s)
TAGBYTES(o)493 TAGBYTES(o)
494 TAGBYTES(r)
495 TAGBYTES(p)
496
497 #undef z_ZZ
498 #undef b_ZZ
499 #undef v_ZZ
500 #undef o_ONEOF
501 #undef s_ONEOF
502 #undef r_ONEOF
503 #undef F
504 #undef TYPES
505 #undef TAGBYTES
506
507
508 /* fixed fields ***************************************************************/
509
510 UPB_FORCEINLINE
511 static const char *fastdecode_unpackedfixed(UPB_PARSE_PARAMS, int tagbytes,
512 int valbytes, upb_card card,
513 _upb_field_parser *packed) {
514 void *dst;
515 fastdecode_arr farr;
516
517 if (UPB_UNLIKELY(!fastdecode_checktag(data, tagbytes))) {
518 if (card == CARD_r && fastdecode_flippacked(&data, tagbytes)) {
519 return packed(UPB_PARSE_ARGS);
520 }
521 RETURN_GENERIC("fixed field tag mismatch\n");
522 }
523
524 dst =
525 fastdecode_getfield(d, ptr, msg, &data, &hasbits, &farr, valbytes, card);
526 if (card == CARD_r) {
527 if (UPB_UNLIKELY(!dst)) {
528 RETURN_GENERIC("couldn't allocate array in arena\n");
529 }
530 }
531
532
533 again:
534 if (card == CARD_r) {
535 dst = fastdecode_resizearr(d, dst, &farr, valbytes);
536 }
537
538 ptr += tagbytes;
539 memcpy(dst, ptr, valbytes);
540 ptr += valbytes;
541
542 if (card == CARD_r) {
543 fastdecode_nextret ret =
544 fastdecode_nextrepeated(d, dst, &ptr, &farr, data, tagbytes, valbytes);
545 switch (ret.next) {
546 case FD_NEXT_SAMEFIELD:
547 dst = ret.dst;
548 goto again;
549 case FD_NEXT_OTHERFIELD:
550 return fastdecode_tagdispatch(d, ptr, msg, table, hasbits, ret.tag);
551 case FD_NEXT_ATLIMIT:
552 return ptr;
553 }
554 }
555
556 return fastdecode_dispatch(d, ptr, msg, table, hasbits);
557 }
558
559 UPB_FORCEINLINE
fastdecode_packedfixed(UPB_PARSE_PARAMS,int tagbytes,int valbytes,_upb_field_parser * unpacked)560 static const char *fastdecode_packedfixed(UPB_PARSE_PARAMS, int tagbytes,
561 int valbytes,
562 _upb_field_parser *unpacked) {
563 if (UPB_UNLIKELY(!fastdecode_checktag(data, tagbytes))) {
564 if (fastdecode_flippacked(&data, tagbytes)) {
565 return unpacked(UPB_PARSE_ARGS);
566 } else {
567 RETURN_GENERIC("varint field tag mismatch\n");
568 }
569 }
570
571 ptr += tagbytes;
572 int size = (uint8_t)ptr[0];
573 ptr++;
574 if (size & 0x80) {
575 ptr = fastdecode_longsize(ptr, &size);
576 }
577
578 if (UPB_UNLIKELY(fastdecode_boundscheck(ptr, size, d->limit_ptr)) ||
579 (size % valbytes) != 0) {
580 return fastdecode_err(d);
581 }
582
583 upb_array **arr_p = fastdecode_fieldmem(msg, data);
584 upb_array *arr = *arr_p;
585 uint8_t elem_size_lg2 = __builtin_ctz(valbytes);
586 int elems = size / valbytes;
587
588 if (UPB_LIKELY(!arr)) {
589 *arr_p = arr = _upb_array_new(&d->arena, elems, elem_size_lg2);
590 if (!arr) {
591 return fastdecode_err(d);
592 }
593 } else {
594 _upb_array_resize(arr, elems, &d->arena);
595 }
596
597 char *dst = _upb_array_ptr(arr);
598 memcpy(dst, ptr, size);
599 arr->len = elems;
600
601 return fastdecode_dispatch(d, ptr + size, msg, table, hasbits);
602 }
603
604 UPB_FORCEINLINE
fastdecode_fixed(UPB_PARSE_PARAMS,int tagbytes,int valbytes,upb_card card,_upb_field_parser * unpacked,_upb_field_parser * packed)605 static const char *fastdecode_fixed(UPB_PARSE_PARAMS, int tagbytes,
606 int valbytes, upb_card card,
607 _upb_field_parser *unpacked,
608 _upb_field_parser *packed) {
609 if (card == CARD_p) {
610 return fastdecode_packedfixed(UPB_PARSE_ARGS, tagbytes, valbytes, unpacked);
611 } else {
612 return fastdecode_unpackedfixed(UPB_PARSE_ARGS, tagbytes, valbytes, card,
613 packed);
614 }
615 }
616
617 /* Generate all combinations:
618 * {s,o,r,p} x {f4,f8} x {1bt,2bt} */
619
620 #define F(card, valbytes, tagbytes) \
621 UPB_NOINLINE \
622 const char *upb_p##card##f##valbytes##_##tagbytes##bt(UPB_PARSE_PARAMS) { \
623 return fastdecode_fixed(UPB_PARSE_ARGS, tagbytes, valbytes, CARD_##card, \
624 &upb_ppf##valbytes##_##tagbytes##bt, \
625 &upb_prf##valbytes##_##tagbytes##bt); \
626 }
627
628 #define TYPES(card, tagbytes) \
629 F(card, 4, tagbytes) \
630 F(card, 8, tagbytes)
631
632 #define TAGBYTES(card) \
633 TYPES(card, 1) \
634 TYPES(card, 2)
635
636 TAGBYTES(s)
637 TAGBYTES(o)
638 TAGBYTES(r)
639 TAGBYTES(p)
640
641 #undef F
642 #undef TYPES
643 #undef TAGBYTES
644
645 /* string fields **************************************************************/
646
647 typedef const char *fastdecode_copystr_func(struct upb_decstate *d,
648 const char *ptr, upb_msg *msg,
649 const upb_msglayout *table,
650 uint64_t hasbits, upb_strview *dst);
651
652 UPB_NOINLINE
fastdecode_verifyutf8(upb_decstate * d,const char * ptr,upb_msg * msg,intptr_t table,uint64_t hasbits,upb_strview * dst)653 static const char *fastdecode_verifyutf8(upb_decstate *d, const char *ptr,
654 upb_msg *msg, intptr_t table,
655 uint64_t hasbits, upb_strview *dst) {
656 if (!decode_verifyutf8_inl(dst->data, dst->size)) {
657 return fastdecode_err(d);
658 }
659 return fastdecode_dispatch(d, ptr, msg, table, hasbits);
660 }
661
662 UPB_FORCEINLINE
fastdecode_longstring(struct upb_decstate * d,const char * ptr,upb_msg * msg,intptr_t table,uint64_t hasbits,upb_strview * dst,bool validate_utf8)663 static const char *fastdecode_longstring(struct upb_decstate *d,
664 const char *ptr, upb_msg *msg,
665 intptr_t table, uint64_t hasbits,
666 upb_strview *dst,
667 bool validate_utf8) {
668 int size = (uint8_t)ptr[0]; // Could plumb through hasbits.
669 ptr++;
670 if (size & 0x80) {
671 ptr = fastdecode_longsize(ptr, &size);
672 }
673
674 if (UPB_UNLIKELY(fastdecode_boundscheck(ptr, size, d->limit_ptr))) {
675 dst->size = 0;
676 return fastdecode_err(d);
677 }
678
679 if (d->alias) {
680 dst->data = ptr;
681 dst->size = size;
682 } else {
683 char *data = upb_arena_malloc(&d->arena, size);
684 if (!data) {
685 return fastdecode_err(d);
686 }
687 memcpy(data, ptr, size);
688 dst->data = data;
689 dst->size = size;
690 }
691
692 if (validate_utf8) {
693 return fastdecode_verifyutf8(d, ptr + size, msg, table, hasbits, dst);
694 } else {
695 return fastdecode_dispatch(d, ptr + size, msg, table, hasbits);
696 }
697 }
698
699 UPB_NOINLINE
fastdecode_longstring_utf8(struct upb_decstate * d,const char * ptr,upb_msg * msg,intptr_t table,uint64_t hasbits,upb_strview * dst)700 static const char *fastdecode_longstring_utf8(struct upb_decstate *d,
701 const char *ptr, upb_msg *msg,
702 intptr_t table, uint64_t hasbits,
703 upb_strview *dst) {
704 return fastdecode_longstring(d, ptr, msg, table, hasbits, dst, true);
705 }
706
707 UPB_NOINLINE
fastdecode_longstring_noutf8(struct upb_decstate * d,const char * ptr,upb_msg * msg,intptr_t table,uint64_t hasbits,upb_strview * dst)708 static const char *fastdecode_longstring_noutf8(struct upb_decstate *d,
709 const char *ptr, upb_msg *msg,
710 intptr_t table,
711 uint64_t hasbits,
712 upb_strview *dst) {
713 return fastdecode_longstring(d, ptr, msg, table, hasbits, dst, false);
714 }
715
716 UPB_FORCEINLINE
fastdecode_docopy(upb_decstate * d,const char * ptr,uint32_t size,int copy,char * data,upb_strview * dst)717 static void fastdecode_docopy(upb_decstate *d, const char *ptr, uint32_t size,
718 int copy, char *data, upb_strview *dst) {
719 d->arena.head.ptr += copy;
720 dst->data = data;
721 UPB_UNPOISON_MEMORY_REGION(data, copy);
722 memcpy(data, ptr, copy);
723 UPB_POISON_MEMORY_REGION(data + size, copy - size);
724 }
725
726 UPB_FORCEINLINE
fastdecode_copystring(UPB_PARSE_PARAMS,int tagbytes,upb_card card,bool validate_utf8)727 static const char *fastdecode_copystring(UPB_PARSE_PARAMS, int tagbytes,
728 upb_card card, bool validate_utf8) {
729 upb_strview *dst;
730 fastdecode_arr farr;
731 int64_t size;
732 size_t arena_has;
733 size_t common_has;
734 char *buf;
735
736 UPB_ASSERT(!d->alias);
737 UPB_ASSERT(fastdecode_checktag(data, tagbytes));
738
739 dst = fastdecode_getfield(d, ptr, msg, &data, &hasbits, &farr,
740 sizeof(upb_strview), card);
741
742 again:
743 if (card == CARD_r) {
744 dst = fastdecode_resizearr(d, dst, &farr, sizeof(upb_strview));
745 }
746
747 size = (uint8_t)ptr[tagbytes];
748 ptr += tagbytes + 1;
749 dst->size = size;
750
751 buf = d->arena.head.ptr;
752 arena_has = _upb_arenahas(&d->arena);
753 common_has = UPB_MIN(arena_has, (d->end - ptr) + 16);
754
755 if (UPB_LIKELY(size <= 15 - tagbytes)) {
756 if (arena_has < 16) goto longstr;
757 d->arena.head.ptr += 16;
758 memcpy(buf, ptr - tagbytes - 1, 16);
759 dst->data = buf + tagbytes + 1;
760 } else if (UPB_LIKELY(size <= 32)) {
761 if (UPB_UNLIKELY(common_has < 32)) goto longstr;
762 fastdecode_docopy(d, ptr, size, 32, buf, dst);
763 } else if (UPB_LIKELY(size <= 64)) {
764 if (UPB_UNLIKELY(common_has < 64)) goto longstr;
765 fastdecode_docopy(d, ptr, size, 64, buf, dst);
766 } else if (UPB_LIKELY(size < 128)) {
767 if (UPB_UNLIKELY(common_has < 128)) goto longstr;
768 fastdecode_docopy(d, ptr, size, 128, buf, dst);
769 } else {
770 goto longstr;
771 }
772
773 ptr += size;
774
775 if (card == CARD_r) {
776 if (validate_utf8 && !decode_verifyutf8_inl(dst->data, dst->size)) {
777 return fastdecode_err(d);
778 }
779 fastdecode_nextret ret = fastdecode_nextrepeated(
780 d, dst, &ptr, &farr, data, tagbytes, sizeof(upb_strview));
781 switch (ret.next) {
782 case FD_NEXT_SAMEFIELD:
783 dst = ret.dst;
784 goto again;
785 case FD_NEXT_OTHERFIELD:
786 return fastdecode_tagdispatch(d, ptr, msg, table, hasbits, ret.tag);
787 case FD_NEXT_ATLIMIT:
788 return ptr;
789 }
790 }
791
792 if (card != CARD_r && validate_utf8) {
793 return fastdecode_verifyutf8(d, ptr, msg, table, hasbits, dst);
794 }
795
796 return fastdecode_dispatch(d, ptr, msg, table, hasbits);
797
798 longstr:
799 ptr--;
800 if (validate_utf8) {
801 return fastdecode_longstring_utf8(d, ptr, msg, table, hasbits, dst);
802 } else {
803 return fastdecode_longstring_noutf8(d, ptr, msg, table, hasbits, dst);
804 }
805 }
806
807 UPB_FORCEINLINE
fastdecode_string(UPB_PARSE_PARAMS,int tagbytes,upb_card card,_upb_field_parser * copyfunc,bool validate_utf8)808 static const char *fastdecode_string(UPB_PARSE_PARAMS, int tagbytes,
809 upb_card card, _upb_field_parser *copyfunc,
810 bool validate_utf8) {
811 upb_strview *dst;
812 fastdecode_arr farr;
813 int64_t size;
814
815 if (UPB_UNLIKELY(!fastdecode_checktag(data, tagbytes))) {
816 RETURN_GENERIC("string field tag mismatch\n");
817 }
818
819 if (UPB_UNLIKELY(!d->alias)) {
820 return copyfunc(UPB_PARSE_ARGS);
821 }
822
823 dst = fastdecode_getfield(d, ptr, msg, &data, &hasbits, &farr,
824 sizeof(upb_strview), card);
825
826 again:
827 if (card == CARD_r) {
828 dst = fastdecode_resizearr(d, dst, &farr, sizeof(upb_strview));
829 }
830
831 size = (int8_t)ptr[tagbytes];
832 ptr += tagbytes + 1;
833 dst->data = ptr;
834 dst->size = size;
835
836 if (UPB_UNLIKELY(fastdecode_boundscheck(ptr, size, d->end))) {
837 ptr--;
838 if (validate_utf8) {
839 return fastdecode_longstring_utf8(d, ptr, msg, table, hasbits, dst);
840 } else {
841 return fastdecode_longstring_noutf8(d, ptr, msg, table, hasbits, dst);
842 }
843 }
844
845 ptr += size;
846
847 if (card == CARD_r) {
848 if (validate_utf8 && !decode_verifyutf8_inl(dst->data, dst->size)) {
849 return fastdecode_err(d);
850 }
851 fastdecode_nextret ret = fastdecode_nextrepeated(
852 d, dst, &ptr, &farr, data, tagbytes, sizeof(upb_strview));
853 switch (ret.next) {
854 case FD_NEXT_SAMEFIELD:
855 dst = ret.dst;
856 if (UPB_UNLIKELY(!d->alias)) {
857 // Buffer flipped and we can't alias any more. Bounce to copyfunc(),
858 // but via dispatch since we need to reload table data also.
859 fastdecode_commitarr(dst, &farr, sizeof(upb_strview));
860 return fastdecode_tagdispatch(d, ptr, msg, table, hasbits, ret.tag);
861 }
862 goto again;
863 case FD_NEXT_OTHERFIELD:
864 return fastdecode_tagdispatch(d, ptr, msg, table, hasbits, ret.tag);
865 case FD_NEXT_ATLIMIT:
866 return ptr;
867 }
868 }
869
870 if (card != CARD_r && validate_utf8) {
871 return fastdecode_verifyutf8(d, ptr, msg, table, hasbits, dst);
872 }
873
874 return fastdecode_dispatch(d, ptr, msg, table, hasbits);
875 }
876
877 /* Generate all combinations:
878 * {p,c} x {s,o,r} x {s, b} x {1bt,2bt} */
879
880 #define s_VALIDATE true
881 #define b_VALIDATE false
882
883 #define F(card, tagbytes, type) \
884 UPB_NOINLINE \
885 const char *upb_c##card##type##_##tagbytes##bt(UPB_PARSE_PARAMS) { \
886 return fastdecode_copystring(UPB_PARSE_ARGS, tagbytes, CARD_##card, \
887 type##_VALIDATE); \
888 } \
889 const char *upb_p##card##type##_##tagbytes##bt(UPB_PARSE_PARAMS) { \
890 return fastdecode_string(UPB_PARSE_ARGS, tagbytes, CARD_##card, \
891 &upb_c##card##type##_##tagbytes##bt, \
892 type##_VALIDATE); \
893 }
894
895 #define UTF8(card, tagbytes) \
896 F(card, tagbytes, s) \
897 F(card, tagbytes, b)
898
899 #define TAGBYTES(card) \
900 UTF8(card, 1) \
901 UTF8(card, 2)
902
903 TAGBYTES(s)
TAGBYTES(o)904 TAGBYTES(o)
905 TAGBYTES(r)
906
907 #undef s_VALIDATE
908 #undef b_VALIDATE
909 #undef F
910 #undef TAGBYTES
911
912 /* message fields *************************************************************/
913
914 UPB_INLINE
915 upb_msg *decode_newmsg_ceil(upb_decstate *d, const upb_msglayout *l,
916 int msg_ceil_bytes) {
917 size_t size = l->size + sizeof(upb_msg_internal);
918 char *msg_data;
919 if (UPB_LIKELY(msg_ceil_bytes > 0 &&
920 _upb_arenahas(&d->arena) >= msg_ceil_bytes)) {
921 UPB_ASSERT(size <= (size_t)msg_ceil_bytes);
922 msg_data = d->arena.head.ptr;
923 d->arena.head.ptr += size;
924 UPB_UNPOISON_MEMORY_REGION(msg_data, msg_ceil_bytes);
925 memset(msg_data, 0, msg_ceil_bytes);
926 UPB_POISON_MEMORY_REGION(msg_data + size, msg_ceil_bytes - size);
927 } else {
928 msg_data = (char*)upb_arena_malloc(&d->arena, size);
929 memset(msg_data, 0, size);
930 }
931 return msg_data + sizeof(upb_msg_internal);
932 }
933
934 typedef struct {
935 intptr_t table;
936 upb_msg *msg;
937 } fastdecode_submsgdata;
938
939 UPB_FORCEINLINE
fastdecode_tosubmsg(upb_decstate * d,const char * ptr,void * ctx)940 static const char *fastdecode_tosubmsg(upb_decstate *d, const char *ptr,
941 void *ctx) {
942 fastdecode_submsgdata *submsg = ctx;
943 ptr = fastdecode_dispatch(d, ptr, submsg->msg, submsg->table, 0);
944 UPB_ASSUME(ptr != NULL);
945 return ptr;
946 }
947
948 UPB_FORCEINLINE
fastdecode_submsg(UPB_PARSE_PARAMS,int tagbytes,int msg_ceil_bytes,upb_card card)949 static const char *fastdecode_submsg(UPB_PARSE_PARAMS, int tagbytes,
950 int msg_ceil_bytes, upb_card card) {
951
952 if (UPB_UNLIKELY(!fastdecode_checktag(data, tagbytes))) {
953 RETURN_GENERIC("submessage field tag mismatch\n");
954 }
955
956 if (--d->depth == 0) return fastdecode_err(d);
957
958 upb_msg **dst;
959 uint32_t submsg_idx = (data >> 16) & 0xff;
960 const upb_msglayout *tablep = decode_totablep(table);
961 const upb_msglayout *subtablep = tablep->submsgs[submsg_idx];
962 fastdecode_submsgdata submsg = {decode_totable(subtablep)};
963 fastdecode_arr farr;
964
965 if (subtablep->table_mask == (uint8_t)-1) {
966 RETURN_GENERIC("submessage doesn't have fast tables.");
967 }
968
969 dst = fastdecode_getfield(d, ptr, msg, &data, &hasbits, &farr,
970 sizeof(upb_msg *), card);
971
972 if (card == CARD_s) {
973 *(uint32_t*)msg |= hasbits;
974 hasbits = 0;
975 }
976
977 again:
978 if (card == CARD_r) {
979 dst = fastdecode_resizearr(d, dst, &farr, sizeof(upb_msg*));
980 }
981
982 submsg.msg = *dst;
983
984 if (card == CARD_r || UPB_LIKELY(!submsg.msg)) {
985 *dst = submsg.msg = decode_newmsg_ceil(d, subtablep, msg_ceil_bytes);
986 }
987
988 ptr += tagbytes;
989 ptr = fastdecode_delimited(d, ptr, fastdecode_tosubmsg, &submsg);
990
991 if (UPB_UNLIKELY(ptr == NULL || d->end_group != DECODE_NOGROUP)) {
992 return fastdecode_err(d);
993 }
994
995 if (card == CARD_r) {
996 fastdecode_nextret ret = fastdecode_nextrepeated(
997 d, dst, &ptr, &farr, data, tagbytes, sizeof(upb_msg *));
998 switch (ret.next) {
999 case FD_NEXT_SAMEFIELD:
1000 dst = ret.dst;
1001 goto again;
1002 case FD_NEXT_OTHERFIELD:
1003 d->depth++;
1004 return fastdecode_tagdispatch(d, ptr, msg, table, hasbits, ret.tag);
1005 case FD_NEXT_ATLIMIT:
1006 d->depth++;
1007 return ptr;
1008 }
1009 }
1010
1011 d->depth++;
1012 return fastdecode_dispatch(d, ptr, msg, table, hasbits);
1013 }
1014
1015 #define F(card, tagbytes, size_ceil, ceil_arg) \
1016 const char *upb_p##card##m_##tagbytes##bt_max##size_ceil##b( \
1017 UPB_PARSE_PARAMS) { \
1018 return fastdecode_submsg(UPB_PARSE_ARGS, tagbytes, ceil_arg, CARD_##card); \
1019 }
1020
1021 #define SIZES(card, tagbytes) \
1022 F(card, tagbytes, 64, 64) \
1023 F(card, tagbytes, 128, 128) \
1024 F(card, tagbytes, 192, 192) \
1025 F(card, tagbytes, 256, 256) \
1026 F(card, tagbytes, max, -1)
1027
1028 #define TAGBYTES(card) \
1029 SIZES(card, 1) \
1030 SIZES(card, 2)
1031
1032 TAGBYTES(s)
1033 TAGBYTES(o)
1034 TAGBYTES(r)
1035
1036 #undef TAGBYTES
1037 #undef SIZES
1038 #undef F
1039
1040 #endif /* UPB_FASTTABLE */
1041