third_party/upb/upb/decode_fast.c

   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
  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
  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
  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
  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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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)
 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
 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
 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
 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
 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
 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
 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
 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
 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
 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)
 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
 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
 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 */