/src/nghttp2/lib/sfparse.c

Source
/*
 * sfparse
 *
 * Copyright (c) 2023 sfparse contributors
 * Copyright (c) 2019 nghttp3 contributors
 * Copyright (c) 2015 nghttp2 contributors
 *
 * Permission is hereby granted, free of charge, to any person obtaining
 * a copy of this software and associated documentation files (the
 * "Software"), to deal in the Software without restriction, including
 * without limitation the rights to use, copy, modify, merge, publish,
 * distribute, sublicense, and/or sell copies of the Software, and to
 * permit persons to whom the Software is furnished to do so, subject to
 * the following conditions:
 *
 * The above copyright notice and this permission notice shall be
 * included in all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
 * LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
 * OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
 * WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */
#include "sfparse.h"

#include <string.h>
#include <assert.h>
#include <stdlib.h>

#ifdef __AVX2__
#  include <immintrin.h>
#endif /* __AVX2__ */

#define SFPARSE_STATE_DICT 0x08u
#define SFPARSE_STATE_LIST 0x10u
#define SFPARSE_STATE_ITEM 0x18u

#define SFPARSE_STATE_INNER_LIST 0x04u

#define SFPARSE_STATE_BEFORE 0x00u
#define SFPARSE_STATE_BEFORE_PARAMS 0x01u
#define SFPARSE_STATE_PARAMS 0x02u
#define SFPARSE_STATE_AFTER 0x03u

#define SFPARSE_STATE_OP_MASK 0x03u

#define SFPARSE_SET_STATE_AFTER(NAME)                                          \
  (SFPARSE_STATE_##NAME | SFPARSE_STATE_AFTER)
#define SFPARSE_SET_STATE_BEFORE_PARAMS(NAME)                                  \
  (SFPARSE_STATE_##NAME | SFPARSE_STATE_BEFORE_PARAMS)
#define SFPARSE_SET_STATE_INNER_LIST_BEFORE(NAME)                              \
  (SFPARSE_STATE_##NAME | SFPARSE_STATE_INNER_LIST | SFPARSE_STATE_BEFORE)

#define SFPARSE_STATE_DICT_AFTER SFPARSE_SET_STATE_AFTER(DICT)
#define SFPARSE_STATE_DICT_BEFORE_PARAMS SFPARSE_SET_STATE_BEFORE_PARAMS(DICT)
#define SFPARSE_STATE_DICT_INNER_LIST_BEFORE                                   \
  SFPARSE_SET_STATE_INNER_LIST_BEFORE(DICT)

#define SFPARSE_STATE_LIST_AFTER SFPARSE_SET_STATE_AFTER(LIST)
#define SFPARSE_STATE_LIST_BEFORE_PARAMS SFPARSE_SET_STATE_BEFORE_PARAMS(LIST)
#define SFPARSE_STATE_LIST_INNER_LIST_BEFORE                                   \
  SFPARSE_SET_STATE_INNER_LIST_BEFORE(LIST)

#define SFPARSE_STATE_ITEM_AFTER SFPARSE_SET_STATE_AFTER(ITEM)
#define SFPARSE_STATE_ITEM_BEFORE_PARAMS SFPARSE_SET_STATE_BEFORE_PARAMS(ITEM)
#define SFPARSE_STATE_ITEM_INNER_LIST_BEFORE                                   \
  SFPARSE_SET_STATE_INNER_LIST_BEFORE(ITEM)

#define SFPARSE_STATE_INITIAL 0x00u

#define DIGIT_CASES                                                            \
  case '0':                                                                    \
  case '1':                                                                    \
  case '2':                                                                    \
  case '3':                                                                    \
  case '4':                                                                    \
  case '5':                                                                    \
  case '6':                                                                    \
  case '7':                                                                    \
  case '8':                                                                    \
  case '9'

#define LCALPHA_CASES                                                          \
  case 'a':                                                                    \
  case 'b':                                                                    \
  case 'c':                                                                    \
  case 'd':                                                                    \
  case 'e':                                                                    \
  case 'f':                                                                    \
  case 'g':                                                                    \
  case 'h':                                                                    \
  case 'i':                                                                    \
  case 'j':                                                                    \
  case 'k':                                                                    \
  case 'l':                                                                    \
  case 'm':                                                                    \
  case 'n':                                                                    \
  case 'o':                                                                    \
  case 'p':                                                                    \
  case 'q':                                                                    \
  case 'r':                                                                    \
  case 's':                                                                    \
  case 't':                                                                    \
  case 'u':                                                                    \
  case 'v':                                                                    \
  case 'w':                                                                    \
  case 'x':                                                                    \
  case 'y':                                                                    \
  case 'z'

#define UCALPHA_CASES                                                          \
  case 'A':                                                                    \
  case 'B':                                                                    \
  case 'C':                                                                    \
  case 'D':                                                                    \
  case 'E':                                                                    \
  case 'F':                                                                    \
  case 'G':                                                                    \
  case 'H':                                                                    \
  case 'I':                                                                    \
  case 'J':                                                                    \
  case 'K':                                                                    \
  case 'L':                                                                    \
  case 'M':                                                                    \
  case 'N':                                                                    \
  case 'O':                                                                    \
  case 'P':                                                                    \
  case 'Q':                                                                    \
  case 'R':                                                                    \
  case 'S':                                                                    \
  case 'T':                                                                    \
  case 'U':                                                                    \
  case 'V':                                                                    \
  case 'W':                                                                    \
  case 'X':                                                                    \
  case 'Y':                                                                    \
  case 'Z'

#define ALPHA_CASES                                                            \
  UCALPHA_CASES:                                                               \
  LCALPHA_CASES

#define TOKEN_CASES                                                            \
  case '!':                                                                    \
  case '#':                                                                    \
  case '$':                                                                    \
  case '%':                                                                    \
  case '&':                                                                    \
  case '\'':                                                                   \
  case '*':                                                                    \
  case '+':                                                                    \
  case '-':                                                                    \
  case '.':                                                                    \
  case '/':                                                                    \
  DIGIT_CASES:                                                                 \
  case ':':                                                                    \
  UCALPHA_CASES:                                                               \
  case '^':                                                                    \
  case '_':                                                                    \
  case '`':                                                                    \
  LCALPHA_CASES:                                                               \
  case '|':                                                                    \
  case '~'

#define LCHEXALPHA_CASES                                                       \
  case 'a':                                                                    \
  case 'b':                                                                    \
  case 'c':                                                                    \
  case 'd':                                                                    \
  case 'e':                                                                    \
  case 'f'

#define X00_1F_CASES                                                           \
  case 0x00:                                                                   \
  case 0x01:                                                                   \
  case 0x02:                                                                   \
  case 0x03:                                                                   \
  case 0x04:                                                                   \
  case 0x05:                                                                   \
  case 0x06:                                                                   \
  case 0x07:                                                                   \
  case 0x08:                                                                   \
  case 0x09:                                                                   \
  case 0x0a:                                                                   \
  case 0x0b:                                                                   \
  case 0x0c:                                                                   \
  case 0x0d:                                                                   \
  case 0x0e:                                                                   \
  case 0x0f:                                                                   \
  case 0x10:                                                                   \
  case 0x11:                                                                   \
  case 0x12:                                                                   \
  case 0x13:                                                                   \
  case 0x14:                                                                   \
  case 0x15:                                                                   \
  case 0x16:                                                                   \
  case 0x17:                                                                   \
  case 0x18:                                                                   \
  case 0x19:                                                                   \
  case 0x1a:                                                                   \
  case 0x1b:                                                                   \
  case 0x1c:                                                                   \
  case 0x1d:                                                                   \
  case 0x1e:                                                                   \
  case 0x1f

#define X20_21_CASES                                                           \
  case ' ':                                                                    \
  case '!'

#define X23_5B_CASES                                                           \
  case '#':                                                                    \
  case '$':                                                                    \
  case '%':                                                                    \
  case '&':                                                                    \
  case '\'':                                                                   \
  case '(':                                                                    \
  case ')':                                                                    \
  case '*':                                                                    \
  case '+':                                                                    \
  case ',':                                                                    \
  case '-':                                                                    \
  case '.':                                                                    \
  case '/':                                                                    \
  DIGIT_CASES:                                                                 \
  case ':':                                                                    \
  case ';':                                                                    \
  case '<':                                                                    \
  case '=':                                                                    \
  case '>':                                                                    \
  case '?':                                                                    \
  case '@':                                                                    \
  UCALPHA_CASES:                                                               \
  case '['

#define X5D_7E_CASES                                                           \
  case ']':                                                                    \
  case '^':                                                                    \
  case '_':                                                                    \
  case '`':                                                                    \
  LCALPHA_CASES:                                                               \
  case '{':                                                                    \
  case '|':                                                                    \
  case '}':                                                                    \
  case '~'

#define X7F_FF_CASES                                                           \
  case 0x7f:                                                                   \
  case 0x80:                                                                   \
  case 0x81:                                                                   \
  case 0x82:                                                                   \
  case 0x83:                                                                   \
  case 0x84:                                                                   \
  case 0x85:                                                                   \
  case 0x86:                                                                   \
  case 0x87:                                                                   \
  case 0x88:                                                                   \
  case 0x89:                                                                   \
  case 0x8a:                                                                   \
  case 0x8b:                                                                   \
  case 0x8c:                                                                   \
  case 0x8d:                                                                   \
  case 0x8e:                                                                   \
  case 0x8f:                                                                   \
  case 0x90:                                                                   \
  case 0x91:                                                                   \
  case 0x92:                                                                   \
  case 0x93:                                                                   \
  case 0x94:                                                                   \
  case 0x95:                                                                   \
  case 0x96:                                                                   \
  case 0x97:                                                                   \
  case 0x98:                                                                   \
  case 0x99:                                                                   \
  case 0x9a:                                                                   \
  case 0x9b:                                                                   \
  case 0x9c:                                                                   \
  case 0x9d:                                                                   \
  case 0x9e:                                                                   \
  case 0x9f:                                                                   \
  case 0xa0:                                                                   \
  case 0xa1:                                                                   \
  case 0xa2:                                                                   \
  case 0xa3:                                                                   \
  case 0xa4:                                                                   \
  case 0xa5:                                                                   \
  case 0xa6:                                                                   \
  case 0xa7:                                                                   \
  case 0xa8:                                                                   \
  case 0xa9:                                                                   \
  case 0xaa:                                                                   \
  case 0xab:                                                                   \
  case 0xac:                                                                   \
  case 0xad:                                                                   \
  case 0xae:                                                                   \
  case 0xaf:                                                                   \
  case 0xb0:                                                                   \
  case 0xb1:                                                                   \
  case 0xb2:                                                                   \
  case 0xb3:                                                                   \
  case 0xb4:                                                                   \
  case 0xb5:                                                                   \
  case 0xb6:                                                                   \
  case 0xb7:                                                                   \
  case 0xb8:                                                                   \
  case 0xb9:                                                                   \
  case 0xba:                                                                   \
  case 0xbb:                                                                   \
  case 0xbc:                                                                   \
  case 0xbd:                                                                   \
  case 0xbe:                                                                   \
  case 0xbf:                                                                   \
  case 0xc0:                                                                   \
  case 0xc1:                                                                   \
  case 0xc2:                                                                   \
  case 0xc3:                                                                   \
  case 0xc4:                                                                   \
  case 0xc5:                                                                   \
  case 0xc6:                                                                   \
  case 0xc7:                                                                   \
  case 0xc8:                                                                   \
  case 0xc9:                                                                   \
  case 0xca:                                                                   \
  case 0xcb:                                                                   \
  case 0xcc:                                                                   \
  case 0xcd:                                                                   \
  case 0xce:                                                                   \
  case 0xcf:                                                                   \
  case 0xd0:                                                                   \
  case 0xd1:                                                                   \
  case 0xd2:                                                                   \
  case 0xd3:                                                                   \
  case 0xd4:                                                                   \
  case 0xd5:                                                                   \
  case 0xd6:                                                                   \
  case 0xd7:                                                                   \
  case 0xd8:                                                                   \
  case 0xd9:                                                                   \
  case 0xda:                                                                   \
  case 0xdb:                                                                   \
  case 0xdc:                                                                   \
  case 0xdd:                                                                   \
  case 0xde:                                                                   \
  case 0xdf:                                                                   \
  case 0xe0:                                                                   \
  case 0xe1:                                                                   \
  case 0xe2:                                                                   \
  case 0xe3:                                                                   \
  case 0xe4:                                                                   \
  case 0xe5:                                                                   \
  case 0xe6:                                                                   \
  case 0xe7:                                                                   \
  case 0xe8:                                                                   \
  case 0xe9:                                                                   \
  case 0xea:                                                                   \
  case 0xeb:                                                                   \
  case 0xec:                                                                   \
  case 0xed:                                                                   \
  case 0xee:                                                                   \
  case 0xef:                                                                   \
  case 0xf0:                                                                   \
  case 0xf1:                                                                   \
  case 0xf2:                                                                   \
  case 0xf3:                                                                   \
  case 0xf4:                                                                   \
  case 0xf5:                                                                   \
  case 0xf6:                                                                   \
  case 0xf7:                                                                   \
  case 0xf8:                                                                   \
  case 0xf9:                                                                   \
  case 0xfa:                                                                   \
  case 0xfb:                                                                   \
  case 0xfc:                                                                   \
  case 0xfd:                                                                   \
  case 0xfe:                                                                   \
  case 0xff

static int is_ws(uint8_t c) {
  switch (c) {
  case ' ':
  case '\t':
    return 1;
  default:
    return 0;
  }
}

#ifdef __AVX2__
#  ifdef _MSC_VER
#    include <intrin.h>

static int ctz(unsigned int v) {
  unsigned long n;

  /* Assume that v is not 0. */
  _BitScanForward(&n, v);

  return (int)n;
}
#  else /* !_MSC_VER */
#    define ctz __builtin_ctz
#  endif /* !_MSC_VER */
#endif   /* __AVX2__ */

static int parser_eof(sfparse_parser *sfp) { return sfp->pos == sfp->end; }

static void parser_discard_ows(sfparse_parser *sfp) {
  for (; !parser_eof(sfp) && is_ws(*sfp->pos); ++sfp->pos)
    ;
}

static void parser_discard_sp(sfparse_parser *sfp) {
  for (; !parser_eof(sfp) && *sfp->pos == ' '; ++sfp->pos)
    ;
}

static void parser_set_op_state(sfparse_parser *sfp, uint32_t op) {
  sfp->state &= ~SFPARSE_STATE_OP_MASK;
  sfp->state |= op;
}

static void parser_unset_inner_list_state(sfparse_parser *sfp) {
  sfp->state &= ~SFPARSE_STATE_INNER_LIST;
}

#ifdef __AVX2__
static const uint8_t *find_char_key(const uint8_t *first, const uint8_t *last) {
  const __m256i us = _mm256_set1_epi8('_');
  const __m256i ds = _mm256_set1_epi8('-');
  const __m256i dot = _mm256_set1_epi8('.');
  const __m256i ast = _mm256_set1_epi8('*');
  const __m256i r0l = _mm256_set1_epi8('0' - 1);
  const __m256i r0r = _mm256_set1_epi8('9' + 1);
  const __m256i r1l = _mm256_set1_epi8('a' - 1);
  const __m256i r1r = _mm256_set1_epi8('z' + 1);
  __m256i s, x;
  uint32_t m;

  for (; first != last; first += 32) {
    s = _mm256_loadu_si256((void *)first);

    x = _mm256_cmpeq_epi8(s, us);
    x = _mm256_or_si256(_mm256_cmpeq_epi8(s, ds), x);
    x = _mm256_or_si256(_mm256_cmpeq_epi8(s, dot), x);
    x = _mm256_or_si256(_mm256_cmpeq_epi8(s, ast), x);
    x = _mm256_or_si256(
      _mm256_and_si256(_mm256_cmpgt_epi8(s, r0l), _mm256_cmpgt_epi8(r0r, s)),
      x);
    x = _mm256_or_si256(
      _mm256_and_si256(_mm256_cmpgt_epi8(s, r1l), _mm256_cmpgt_epi8(r1r, s)),
      x);

    m = ~(uint32_t)_mm256_movemask_epi8(x);
    if (m) {
      return first + ctz(m);
    }
  }

  return last;
}
#endif /* __AVX2__ */

static int parser_key(sfparse_parser *sfp, sfparse_vec *dest) {
  const uint8_t *base;
#ifdef __AVX2__
  const uint8_t *last;
#endif /* __AVX2__ */

  switch (*sfp->pos) {
  case '*':
  LCALPHA_CASES:
    break;
  default:
    return SFPARSE_ERR_PARSE;
  }

  base = sfp->pos++;

#ifdef __AVX2__
  if (sfp->end - sfp->pos >= 32) {
    last = sfp->pos + ((sfp->end - sfp->pos) & ~0x1fu);

    sfp->pos = find_char_key(sfp->pos, last);
    if (sfp->pos != last) {
      goto fin;
    }
  }
#endif /* __AVX2__ */

  for (; !parser_eof(sfp); ++sfp->pos) {
    switch (*sfp->pos) {
    case '_':
    case '-':
    case '.':
    case '*':
    DIGIT_CASES:
    LCALPHA_CASES:
      continue;
    }

    break;
  }

#ifdef __AVX2__
fin:
#endif /* __AVX2__ */
  if (dest) {
    dest->base = (uint8_t *)base;
    dest->len = (size_t)(sfp->pos - dest->base);
  }

  return 0;
}

static int parser_number(sfparse_parser *sfp, sfparse_value *dest) {
  int sign = 1;
  int64_t value = 0;
  size_t len = 0;
  size_t fpos = 0;

  if (*sfp->pos == '-') {
    ++sfp->pos;
    if (parser_eof(sfp)) {
      return SFPARSE_ERR_PARSE;
    }

    sign = -1;
  }

  assert(!parser_eof(sfp));

  for (; !parser_eof(sfp); ++sfp->pos) {
    switch (*sfp->pos) {
    DIGIT_CASES:
      if (++len > 15) {
        return SFPARSE_ERR_PARSE;
      }

      value *= 10;
      value += *sfp->pos - '0';

      continue;
    }

    break;
  }

  if (len == 0) {
    return SFPARSE_ERR_PARSE;
  }

  if (parser_eof(sfp) || *sfp->pos != '.') {
    if (dest) {
      dest->type = SFPARSE_TYPE_INTEGER;
      dest->flags = SFPARSE_VALUE_FLAG_NONE;
      dest->integer = value * sign;
    }

    return 0;
  }

  /* decimal */

  if (len > 12) {
    return SFPARSE_ERR_PARSE;
  }

  fpos = len;

  ++sfp->pos;

  for (; !parser_eof(sfp); ++sfp->pos) {
    switch (*sfp->pos) {
    DIGIT_CASES:
      if (++len > 15) {
        return SFPARSE_ERR_PARSE;
      }

      value *= 10;
      value += *sfp->pos - '0';

      continue;
    }

    break;
  }

  if (fpos == len || len - fpos > 3) {
    return SFPARSE_ERR_PARSE;
  }

  if (dest) {
    dest->type = SFPARSE_TYPE_DECIMAL;
    dest->flags = SFPARSE_VALUE_FLAG_NONE;
    dest->decimal.numer = value * sign;

    switch (len - fpos) {
    case 1:
      dest->decimal.denom = 10;

      break;
    case 2:
      dest->decimal.denom = 100;

      break;
    case 3:
      dest->decimal.denom = 1000;

      break;
    }
  }

  return 0;
}

static int parser_date(sfparse_parser *sfp, sfparse_value *dest) {
  int rv;
  sfparse_value val;

  /* The first byte has already been validated by the caller. */
  assert('@' == *sfp->pos);

  ++sfp->pos;

  if (parser_eof(sfp)) {
    return SFPARSE_ERR_PARSE;
  }

  rv = parser_number(sfp, &val);
  if (rv != 0) {
    return rv;
  }

  if (val.type != SFPARSE_TYPE_INTEGER) {
    return SFPARSE_ERR_PARSE;
  }

  if (dest) {
    *dest = val;
    dest->type = SFPARSE_TYPE_DATE;
  }

  return 0;
}

#ifdef __AVX2__
static const uint8_t *find_char_string(const uint8_t *first,
                                       const uint8_t *last) {
  const __m256i bs = _mm256_set1_epi8('\\');
  const __m256i dq = _mm256_set1_epi8('"');
  const __m256i del = _mm256_set1_epi8(0x7f);
  const __m256i sp = _mm256_set1_epi8(' ');
  __m256i s, x;
  uint32_t m;

  for (; first != last; first += 32) {
    s = _mm256_loadu_si256((void *)first);

    x = _mm256_cmpgt_epi8(sp, s);
    x = _mm256_or_si256(_mm256_cmpeq_epi8(s, bs), x);
    x = _mm256_or_si256(_mm256_cmpeq_epi8(s, dq), x);
    x = _mm256_or_si256(_mm256_cmpeq_epi8(s, del), x);

    m = (uint32_t)_mm256_movemask_epi8(x);
    if (m) {
      return first + ctz(m);
    }
  }

  return last;
}
#endif /* __AVX2__ */

static int parser_string(sfparse_parser *sfp, sfparse_value *dest) {
  const uint8_t *base;
#ifdef __AVX2__
  const uint8_t *last;
#endif /* __AVX2__ */
  uint32_t flags = SFPARSE_VALUE_FLAG_NONE;

  /* The first byte has already been validated by the caller. */
  assert('"' == *sfp->pos);

  base = ++sfp->pos;

#ifdef __AVX2__
  for (; sfp->end - sfp->pos >= 32; ++sfp->pos) {
    last = sfp->pos + ((sfp->end - sfp->pos) & ~0x1fu);

    sfp->pos = find_char_string(sfp->pos, last);
    if (sfp->pos == last) {
      break;
    }

    switch (*sfp->pos) {
    case '\\':
      ++sfp->pos;
      if (parser_eof(sfp)) {
        return SFPARSE_ERR_PARSE;
      }

      switch (*sfp->pos) {
      case '"':
      case '\\':
        flags = SFPARSE_VALUE_FLAG_ESCAPED_STRING;

        break;
      default:
        return SFPARSE_ERR_PARSE;
      }

      break;
    case '"':
      goto fin;
    default:
      return SFPARSE_ERR_PARSE;
    }
  }
#endif /* __AVX2__ */

  for (; !parser_eof(sfp); ++sfp->pos) {
    switch (*sfp->pos) {
    X20_21_CASES:
    X23_5B_CASES:
    X5D_7E_CASES:
      break;
    case '\\':
      ++sfp->pos;
      if (parser_eof(sfp)) {
        return SFPARSE_ERR_PARSE;
      }

      switch (*sfp->pos) {
      case '"':
      case '\\':
        flags = SFPARSE_VALUE_FLAG_ESCAPED_STRING;

        break;
      default:
        return SFPARSE_ERR_PARSE;
      }

      break;
    case '"':
      goto fin;
    default:
      return SFPARSE_ERR_PARSE;
    }
  }

  return SFPARSE_ERR_PARSE;

fin:
  if (dest) {
    dest->type = SFPARSE_TYPE_STRING;
    dest->flags = flags;
    dest->vec.len = (size_t)(sfp->pos - base);
    dest->vec.base = dest->vec.len == 0 ? NULL : (uint8_t *)base;
  }

  ++sfp->pos;

  return 0;
}

#ifdef __AVX2__
static const uint8_t *find_char_token(const uint8_t *first,
                                      const uint8_t *last) {
  /* r0: !..:, excluding "(),
     r1: A..Z
     r2: ^..~, excluding {} */
  const __m256i r0l = _mm256_set1_epi8('!' - 1);
  const __m256i r0r = _mm256_set1_epi8(':' + 1);
  const __m256i dq = _mm256_set1_epi8('"');
  const __m256i prl = _mm256_set1_epi8('(');
  const __m256i prr = _mm256_set1_epi8(')');
  const __m256i comma = _mm256_set1_epi8(',');
  const __m256i r1l = _mm256_set1_epi8('A' - 1);
  const __m256i r1r = _mm256_set1_epi8('Z' + 1);
  const __m256i r2l = _mm256_set1_epi8('^' - 1);
  const __m256i r2r = _mm256_set1_epi8('~' + 1);
  const __m256i cbl = _mm256_set1_epi8('{');
  const __m256i cbr = _mm256_set1_epi8('}');
  __m256i s, x;
  uint32_t m;

  for (; first != last; first += 32) {
    s = _mm256_loadu_si256((void *)first);

    x = _mm256_andnot_si256(
      _mm256_cmpeq_epi8(s, comma),
      _mm256_andnot_si256(
        _mm256_cmpeq_epi8(s, prr),
        _mm256_andnot_si256(
          _mm256_cmpeq_epi8(s, prl),
          _mm256_andnot_si256(_mm256_cmpeq_epi8(s, dq),
                              _mm256_and_si256(_mm256_cmpgt_epi8(s, r0l),
                                               _mm256_cmpgt_epi8(r0r, s))))));
    x = _mm256_or_si256(
      _mm256_and_si256(_mm256_cmpgt_epi8(s, r1l), _mm256_cmpgt_epi8(r1r, s)),
      x);
    x = _mm256_or_si256(
      _mm256_andnot_si256(
        _mm256_cmpeq_epi8(s, cbr),
        _mm256_andnot_si256(_mm256_cmpeq_epi8(s, cbl),
                            _mm256_and_si256(_mm256_cmpgt_epi8(s, r2l),
                                             _mm256_cmpgt_epi8(r2r, s)))),
      x);

    m = ~(uint32_t)_mm256_movemask_epi8(x);
    if (m) {
      return first + ctz(m);
    }
  }

  return last;
}
#endif /* __AVX2__ */

static int parser_token(sfparse_parser *sfp, sfparse_value *dest) {
  const uint8_t *base;
#ifdef __AVX2__
  const uint8_t *last;
#endif /* __AVX2__ */

  /* The first byte has already been validated by the caller. */
  base = sfp->pos++;

#ifdef __AVX2__
  if (sfp->end - sfp->pos >= 32) {
    last = sfp->pos + ((sfp->end - sfp->pos) & ~0x1fu);

    sfp->pos = find_char_token(sfp->pos, last);
    if (sfp->pos != last) {
      goto fin;
    }
  }
#endif /* __AVX2__ */

  for (; !parser_eof(sfp); ++sfp->pos) {
    switch (*sfp->pos) {
    TOKEN_CASES:
      continue;
    }

    break;
  }

#ifdef __AVX2__
fin:
#endif /* __AVX2__ */
  if (dest) {
    dest->type = SFPARSE_TYPE_TOKEN;
    dest->flags = SFPARSE_VALUE_FLAG_NONE;
    dest->vec.base = (uint8_t *)base;
    dest->vec.len = (size_t)(sfp->pos - base);
  }

  return 0;
}

#ifdef __AVX2__
static const uint8_t *find_char_byteseq(const uint8_t *first,
                                        const uint8_t *last) {
  const __m256i pls = _mm256_set1_epi8('+');
  const __m256i fs = _mm256_set1_epi8('/');
  const __m256i r0l = _mm256_set1_epi8('0' - 1);
  const __m256i r0r = _mm256_set1_epi8('9' + 1);
  const __m256i r1l = _mm256_set1_epi8('A' - 1);
  const __m256i r1r = _mm256_set1_epi8('Z' + 1);
  const __m256i r2l = _mm256_set1_epi8('a' - 1);
  const __m256i r2r = _mm256_set1_epi8('z' + 1);
  __m256i s, x;
  uint32_t m;

  for (; first != last; first += 32) {
    s = _mm256_loadu_si256((void *)first);

    x = _mm256_cmpeq_epi8(s, pls);
    x = _mm256_or_si256(_mm256_cmpeq_epi8(s, fs), x);
    x = _mm256_or_si256(
      _mm256_and_si256(_mm256_cmpgt_epi8(s, r0l), _mm256_cmpgt_epi8(r0r, s)),
      x);
    x = _mm256_or_si256(
      _mm256_and_si256(_mm256_cmpgt_epi8(s, r1l), _mm256_cmpgt_epi8(r1r, s)),
      x);
    x = _mm256_or_si256(
      _mm256_and_si256(_mm256_cmpgt_epi8(s, r2l), _mm256_cmpgt_epi8(r2r, s)),
      x);

    m = ~(uint32_t)_mm256_movemask_epi8(x);
    if (m) {
      return first + ctz(m);
    }
  }

  return last;
}
#endif /* __AVX2__ */

static int parser_byteseq(sfparse_parser *sfp, sfparse_value *dest) {
  const uint8_t *base;
#ifdef __AVX2__
  const uint8_t *last;
#endif /* __AVX2__ */

  /* The first byte has already been validated by the caller. */
  assert(':' == *sfp->pos);

  base = ++sfp->pos;

#ifdef __AVX2__
  if (sfp->end - sfp->pos >= 32) {
    last = sfp->pos + ((sfp->end - sfp->pos) & ~0x1fu);
    sfp->pos = find_char_byteseq(sfp->pos, last);
  }
#endif /* __AVX2__ */

  for (; !parser_eof(sfp); ++sfp->pos) {
    switch (*sfp->pos) {
    case '+':
    case '/':
    DIGIT_CASES:
    ALPHA_CASES:
      continue;
    case '=':
      switch ((sfp->pos - base) & 0x3) {
      case 0:
      case 1:
        return SFPARSE_ERR_PARSE;
      case 2:
        ++sfp->pos;

        if (parser_eof(sfp)) {
          return SFPARSE_ERR_PARSE;
        }

        if (*sfp->pos == '=') {
          ++sfp->pos;
        }

        break;
      case 3:
        ++sfp->pos;

        break;
      }

      if (parser_eof(sfp) || *sfp->pos != ':') {
        return SFPARSE_ERR_PARSE;
      }

      goto fin;
    case ':':
      if (((sfp->pos - base) & 0x3) == 1) {
        return SFPARSE_ERR_PARSE;
      }

      goto fin;
    default:
      return SFPARSE_ERR_PARSE;
    }
  }

  return SFPARSE_ERR_PARSE;

fin:
  if (dest) {
    dest->type = SFPARSE_TYPE_BYTESEQ;
    dest->flags = SFPARSE_VALUE_FLAG_NONE;
    dest->vec.len = (size_t)(sfp->pos - base);
    dest->vec.base = dest->vec.len == 0 ? NULL : (uint8_t *)base;
  }

  ++sfp->pos;

  return 0;
}

static int parser_boolean(sfparse_parser *sfp, sfparse_value *dest) {
  int b;

  /* The first byte has already been validated by the caller. */
  assert('?' == *sfp->pos);

  ++sfp->pos;

  if (parser_eof(sfp)) {
    return SFPARSE_ERR_PARSE;
  }

  switch (*sfp->pos) {
  case '0':
    b = 0;

    break;
  case '1':
    b = 1;

    break;
  default:
    return SFPARSE_ERR_PARSE;
  }

  ++sfp->pos;

  if (dest) {
    dest->type = SFPARSE_TYPE_BOOLEAN;
    dest->flags = SFPARSE_VALUE_FLAG_NONE;
    dest->boolean = b;
  }

  return 0;
}

static int pctdecode(uint8_t *pc, const uint8_t **ppos) {
  uint8_t c, b = **ppos;

  switch (b) {
  DIGIT_CASES:
    c = (uint8_t)((b - '0') << 4);

    break;
  LCHEXALPHA_CASES:
    c = (uint8_t)((b - 'a' + 10) << 4);

    break;
  default:
    return -1;
  }

  b = *++*ppos;

  switch (b) {
  DIGIT_CASES:
    c |= (uint8_t)(b - '0');

    break;
  LCHEXALPHA_CASES:
    c |= (uint8_t)(b - 'a' + 10);

    break;
  default:
    return -1;
  }

  *pc = c;
  ++*ppos;

  return 0;
}

/* Start of utf8 dfa */
/* Copyright (c) 2008-2010 Bjoern Hoehrmann <bjoern@hoehrmann.de>
 * See http://bjoern.hoehrmann.de/utf-8/decoder/dfa/ for details.
 *
 * Copyright (c) 2008-2009 Bjoern Hoehrmann <bjoern@hoehrmann.de>
 *
 * Permission is hereby granted, free of charge, to any person
 * obtaining a copy of this software and associated documentation
 * files (the "Software"), to deal in the Software without
 * restriction, including without limitation the rights to use, copy,
 * modify, merge, publish, distribute, sublicense, and/or sell copies
 * of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be
 * included in all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
 * NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS
 * BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN
 * ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN
 * CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
 * SOFTWARE.
 */
#define UTF8_ACCEPT 0
#define UTF8_REJECT 12

/* clang-format off */
static const uint8_t utf8d[] = {
  /*
   * The first part of the table maps bytes to character classes that
   * to reduce the size of the transition table and create bitmasks.
   */
   0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
   0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
   0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
   0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,  0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
   1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,  9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,9,
   7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,  7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,7,
   8,8,2,2,2,2,2,2,2,2,2,2,2,2,2,2,  2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,2,
  10,3,3,3,3,3,3,3,3,3,3,3,3,4,3,3, 11,6,6,6,5,8,8,8,8,8,8,8,8,8,8,8,

   /*
    * The second part is a transition table that maps a combination
    * of a state of the automaton and a character class to a state.
    */
   0,12,24,36,60,96,84,12,12,12,48,72, 12,12,12,12,12,12,12,12,12,12,12,12,
  12, 0,12,12,12,12,12, 0,12, 0,12,12, 12,24,12,12,12,12,12,24,12,24,12,12,
  12,12,12,12,12,12,12,24,12,12,12,12, 12,24,12,12,12,12,12,12,12,24,12,12,
  12,12,12,12,12,12,12,36,12,36,12,12, 12,36,12,12,12,12,12,36,12,36,12,12,
  12,36,12,12,12,12,12,12,12,12,12,12,
};
/* clang-format on */

static void utf8_decode(uint32_t *state, uint8_t byte) {
  *state = utf8d[256 + *state + utf8d[byte]];
}

/* End of utf8 dfa */

static int parser_dispstring(sfparse_parser *sfp, sfparse_value *dest) {
  const uint8_t *base;
  uint8_t c;
  uint32_t utf8state = UTF8_ACCEPT;

  assert('%' == *sfp->pos);

  ++sfp->pos;

  if (parser_eof(sfp) || *sfp->pos != '"') {
    return SFPARSE_ERR_PARSE;
  }

  base = ++sfp->pos;

  for (; !parser_eof(sfp);) {
    switch (*sfp->pos) {
    X00_1F_CASES:
    X7F_FF_CASES:
      return SFPARSE_ERR_PARSE;
    case '%':
      ++sfp->pos;

      if (sfp->pos + 2 > sfp->end) {
        return SFPARSE_ERR_PARSE;
      }

      if (pctdecode(&c, &sfp->pos) != 0) {
        return SFPARSE_ERR_PARSE;
      }

      utf8_decode(&utf8state, c);
      if (utf8state == UTF8_REJECT) {
        return SFPARSE_ERR_PARSE;
      }

      break;
    case '"':
      if (utf8state != UTF8_ACCEPT) {
        return SFPARSE_ERR_PARSE;
      }

      if (dest) {
        dest->type = SFPARSE_TYPE_DISPSTRING;
        dest->flags = SFPARSE_VALUE_FLAG_NONE;
        dest->vec.len = (size_t)(sfp->pos - base);
        dest->vec.base = dest->vec.len == 0 ? NULL : (uint8_t *)base;
      }

      ++sfp->pos;

      return 0;
    default:
      if (utf8state != UTF8_ACCEPT) {
        return SFPARSE_ERR_PARSE;
      }

      ++sfp->pos;
    }
  }

  return SFPARSE_ERR_PARSE;
}

static int parser_bare_item(sfparse_parser *sfp, sfparse_value *dest) {
  switch (*sfp->pos) {
  case '"':
    return parser_string(sfp, dest);
  case '-':
  DIGIT_CASES:
    return parser_number(sfp, dest);
  case '@':
    return parser_date(sfp, dest);
  case ':':
    return parser_byteseq(sfp, dest);
  case '?':
    return parser_boolean(sfp, dest);
  case '*':
  ALPHA_CASES:
    return parser_token(sfp, dest);
  case '%':
    return parser_dispstring(sfp, dest);
  default:
    return SFPARSE_ERR_PARSE;
  }
}

static int parser_skip_inner_list(sfparse_parser *sfp);

int sfparse_parser_param(sfparse_parser *sfp, sfparse_vec *dest_key,
                         sfparse_value *dest_value) {
  int rv;

  switch (sfp->state & SFPARSE_STATE_OP_MASK) {
  case SFPARSE_STATE_BEFORE:
    rv = parser_skip_inner_list(sfp);
    if (rv != 0) {
      return rv;
    }

    /* fall through */
  case SFPARSE_STATE_BEFORE_PARAMS:
    parser_set_op_state(sfp, SFPARSE_STATE_PARAMS);

    break;
  case SFPARSE_STATE_PARAMS:
    break;
  default:
    assert(0);
    abort();
  }

  if (parser_eof(sfp) || *sfp->pos != ';') {
    parser_set_op_state(sfp, SFPARSE_STATE_AFTER);

    return SFPARSE_ERR_EOF;
  }

  ++sfp->pos;

  parser_discard_sp(sfp);
  if (parser_eof(sfp)) {
    return SFPARSE_ERR_PARSE;
  }

  rv = parser_key(sfp, dest_key);
  if (rv != 0) {
    return rv;
  }

  if (parser_eof(sfp) || *sfp->pos != '=') {
    if (dest_value) {
      dest_value->type = SFPARSE_TYPE_BOOLEAN;
      dest_value->flags = SFPARSE_VALUE_FLAG_NONE;
      dest_value->boolean = 1;
    }

    return 0;
  }

  ++sfp->pos;

  if (parser_eof(sfp)) {
    return SFPARSE_ERR_PARSE;
  }

  return parser_bare_item(sfp, dest_value);
}

static int parser_skip_params(sfparse_parser *sfp) {
  int rv;

  for (;;) {
    rv = sfparse_parser_param(sfp, NULL, NULL);
    switch (rv) {
    case 0:
      break;
    case SFPARSE_ERR_EOF:
      return 0;
    case SFPARSE_ERR_PARSE:
      return rv;
    default:
      assert(0);
      abort();
    }
  }
}

int sfparse_parser_inner_list(sfparse_parser *sfp, sfparse_value *dest) {
  int rv;

  switch (sfp->state & SFPARSE_STATE_OP_MASK) {
  case SFPARSE_STATE_BEFORE:
    parser_discard_sp(sfp);
    if (parser_eof(sfp)) {
      return SFPARSE_ERR_PARSE;
    }

    break;
  case SFPARSE_STATE_BEFORE_PARAMS:
    rv = parser_skip_params(sfp);
    if (rv != 0) {
      return rv;
    }

    /* Technically, we are entering SFPARSE_STATE_AFTER, but we will set
       another state without reading the state. */
    /* parser_set_op_state(sfp, SFPARSE_STATE_AFTER); */

    /* fall through */
  case SFPARSE_STATE_AFTER:
    if (parser_eof(sfp)) {
      return SFPARSE_ERR_PARSE;
    }

    switch (*sfp->pos) {
    case ' ':
      parser_discard_sp(sfp);
      if (parser_eof(sfp)) {
        return SFPARSE_ERR_PARSE;
      }

      break;
    case ')':
      break;
    default:
      return SFPARSE_ERR_PARSE;
    }

    break;
  default:
    assert(0);
    abort();
  }

  if (*sfp->pos == ')') {
    ++sfp->pos;

    parser_unset_inner_list_state(sfp);
    parser_set_op_state(sfp, SFPARSE_STATE_BEFORE_PARAMS);

    return SFPARSE_ERR_EOF;
  }

  rv = parser_bare_item(sfp, dest);
  if (rv != 0) {
    return rv;
  }

  parser_set_op_state(sfp, SFPARSE_STATE_BEFORE_PARAMS);

  return 0;
}

static int parser_skip_inner_list(sfparse_parser *sfp) {
  int rv;

  for (;;) {
    rv = sfparse_parser_inner_list(sfp, NULL);
    switch (rv) {
    case 0:
      break;
    case SFPARSE_ERR_EOF:
      return 0;
    case SFPARSE_ERR_PARSE:
      return rv;
    default:
      assert(0);
      abort();
    }
  }
}

static int parser_next_key_or_item(sfparse_parser *sfp) {
  parser_discard_ows(sfp);

  if (parser_eof(sfp)) {
    return SFPARSE_ERR_EOF;
  }

  if (*sfp->pos != ',') {
    return SFPARSE_ERR_PARSE;
  }

  ++sfp->pos;

  parser_discard_ows(sfp);
  if (parser_eof(sfp)) {
    return SFPARSE_ERR_PARSE;
  }

  return 0;
}

static int parser_dict_value(sfparse_parser *sfp, sfparse_value *dest) {
  int rv;

  if (parser_eof(sfp) || *(sfp->pos) != '=') {
    /* Boolean true */
    if (dest) {
      dest->type = SFPARSE_TYPE_BOOLEAN;
      dest->flags = SFPARSE_VALUE_FLAG_NONE;
      dest->boolean = 1;
    }

    sfp->state = SFPARSE_STATE_DICT_BEFORE_PARAMS;

    return 0;
  }

  ++sfp->pos;

  if (parser_eof(sfp)) {
    return SFPARSE_ERR_PARSE;
  }

  if (*sfp->pos == '(') {
    if (dest) {
      dest->type = SFPARSE_TYPE_INNER_LIST;
      dest->flags = SFPARSE_VALUE_FLAG_NONE;
    }

    ++sfp->pos;

    sfp->state = SFPARSE_STATE_DICT_INNER_LIST_BEFORE;

    return 0;
  }

  rv = parser_bare_item(sfp, dest);
  if (rv != 0) {
    return rv;
  }

  sfp->state = SFPARSE_STATE_DICT_BEFORE_PARAMS;

  return 0;
}

int sfparse_parser_dict(sfparse_parser *sfp, sfparse_vec *dest_key,
                        sfparse_value *dest_value) {
  int rv;

  switch (sfp->state) {
  case SFPARSE_STATE_DICT_INNER_LIST_BEFORE:
    rv = parser_skip_inner_list(sfp);
    if (rv != 0) {
      return rv;
    }

    /* fall through */
  case SFPARSE_STATE_DICT_BEFORE_PARAMS:
    rv = parser_skip_params(sfp);
    if (rv != 0) {
      return rv;
    }

    /* fall through */
  case SFPARSE_STATE_DICT_AFTER:
    rv = parser_next_key_or_item(sfp);
    if (rv != 0) {
      return rv;
    }

    break;
  case SFPARSE_STATE_INITIAL:
    parser_discard_sp(sfp);

    if (parser_eof(sfp)) {
      return SFPARSE_ERR_EOF;
    }

    break;
  default:
    assert(0);
    abort();
  }

  rv = parser_key(sfp, dest_key);
  if (rv != 0) {
    return rv;
  }

  return parser_dict_value(sfp, dest_value);
}

int sfparse_parser_list(sfparse_parser *sfp, sfparse_value *dest) {
  int rv;

  switch (sfp->state) {
  case SFPARSE_STATE_LIST_INNER_LIST_BEFORE:
    rv = parser_skip_inner_list(sfp);
    if (rv != 0) {
      return rv;
    }

    /* fall through */
  case SFPARSE_STATE_LIST_BEFORE_PARAMS:
    rv = parser_skip_params(sfp);
    if (rv != 0) {
      return rv;
    }

    /* fall through */
  case SFPARSE_STATE_LIST_AFTER:
    rv = parser_next_key_or_item(sfp);
    if (rv != 0) {
      return rv;
    }

    break;
  case SFPARSE_STATE_INITIAL:
    parser_discard_sp(sfp);

    if (parser_eof(sfp)) {
      return SFPARSE_ERR_EOF;
    }

    break;
  default:
    assert(0);
    abort();
  }

  if (*sfp->pos == '(') {
    if (dest) {
      dest->type = SFPARSE_TYPE_INNER_LIST;
      dest->flags = SFPARSE_VALUE_FLAG_NONE;
    }

    ++sfp->pos;

    sfp->state = SFPARSE_STATE_LIST_INNER_LIST_BEFORE;

    return 0;
  }

  rv = parser_bare_item(sfp, dest);
  if (rv != 0) {
    return rv;
  }

  sfp->state = SFPARSE_STATE_LIST_BEFORE_PARAMS;

  return 0;
}

int sfparse_parser_item(sfparse_parser *sfp, sfparse_value *dest) {
  int rv;

  switch (sfp->state) {
  case SFPARSE_STATE_INITIAL:
    parser_discard_sp(sfp);

    if (parser_eof(sfp)) {
      return SFPARSE_ERR_PARSE;
    }

    break;
  case SFPARSE_STATE_ITEM_INNER_LIST_BEFORE:
    rv = parser_skip_inner_list(sfp);
    if (rv != 0) {
      return rv;
    }

    /* fall through */
  case SFPARSE_STATE_ITEM_BEFORE_PARAMS:
    rv = parser_skip_params(sfp);
    if (rv != 0) {
      return rv;
    }

    /* fall through */
  case SFPARSE_STATE_ITEM_AFTER:
    parser_discard_sp(sfp);

    if (!parser_eof(sfp)) {
      return SFPARSE_ERR_PARSE;
    }

    return SFPARSE_ERR_EOF;
  default:
    assert(0);
    abort();
  }

  if (*sfp->pos == '(') {
    if (dest) {
      dest->type = SFPARSE_TYPE_INNER_LIST;
      dest->flags = SFPARSE_VALUE_FLAG_NONE;
    }

    ++sfp->pos;

    sfp->state = SFPARSE_STATE_ITEM_INNER_LIST_BEFORE;

    return 0;
  }

  rv = parser_bare_item(sfp, dest);
  if (rv != 0) {
    return rv;
  }

  sfp->state = SFPARSE_STATE_ITEM_BEFORE_PARAMS;

  return 0;
}

void sfparse_parser_init(sfparse_parser *sfp, const uint8_t *data,
                         size_t datalen) {
  if (datalen == 0) {
    sfp->pos = sfp->end = NULL;
  } else {
    sfp->pos = data;
    sfp->end = data + datalen;
  }

  sfp->state = SFPARSE_STATE_INITIAL;
}

void sfparse_unescape(sfparse_vec *dest, const sfparse_vec *src) {
  const uint8_t *p, *q;
  uint8_t *o;
  size_t len, slen;

  if (src->len == 0) {
    dest->len = 0;

    return;
  }

  o = dest->base;
  p = src->base;
  len = src->len;

  for (;;) {
    q = memchr(p, '\\', len);
    if (q == NULL) {
      memcpy(o, p, len);
      o += len;

      dest->len = (size_t)(o - dest->base);

      return;
    }

    slen = (size_t)(q - p);
    memcpy(o, p, slen);
    o += slen;

    p = q + 1;
    *o++ = *p++;
    len -= slen + 2;
  }
}

void sfparse_base64decode(sfparse_vec *dest, const sfparse_vec *src) {
  static const int index_tbl[] = {
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
    -1, -1, -1, -1, -1, 62, -1, -1, -1, 63, 52, 53, 54, 55, 56, 57, 58, 59, 60,
    61, -1, -1, -1, -1, -1, -1, -1, 0,  1,  2,  3,  4,  5,  6,  7,  8,  9,  10,
    11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, -1, -1, -1, -1,
    -1, -1, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42,
    43, 44, 45, 46, 47, 48, 49, 50, 51, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
    -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1,
    -1, -1, -1, -1, -1, -1, -1, -1, -1};
  uint8_t *o;
  const uint8_t *p, *end;
  uint32_t n;
  size_t i, left;
  int idx;

  if (src->len == 0) {
    dest->len = 0;

    return;
  }

  o = dest->base;
  p = src->base;
  left = src->len & 0x3;
  if (left == 0 && src->base[src->len - 1] == '=') {
    left = 4;
  }
  end = src->base + src->len - left;

  for (; p != end;) {
    n = 0;

    for (i = 1; i <= 4; ++i, ++p) {
      idx = index_tbl[*p];

      assert(idx != -1);

      n += (uint32_t)(idx << (24 - i * 6));
    }

    *o++ = (uint8_t)(n >> 16);
    *o++ = (n >> 8) & 0xffu;
    *o++ = n & 0xffu;
  }

  switch (left) {
  case 0:
    goto fin;
  case 1:
    assert(0);
    abort();
  case 3:
    if (src->base[src->len - 1] == '=') {
      left = 2;
    }

    break;
  case 4:
    assert('=' == src->base[src->len - 1]);

    if (src->base[src->len - 2] == '=') {
      left = 2;
    } else {
      left = 3;
    }

    break;
  }

  switch (left) {
  case 2:
    *o = (uint8_t)(index_tbl[*p++] << 2);
    *o++ |= (uint8_t)(index_tbl[*p++] >> 4);

    break;
  case 3:
    n = (uint32_t)(index_tbl[*p++] << 10);
    n += (uint32_t)(index_tbl[*p++] << 4);
    n += (uint32_t)(index_tbl[*p++] >> 2);
    *o++ = (n >> 8) & 0xffu;
    *o++ = n & 0xffu;

    break;
  }

fin:
  dest->len = (size_t)(o - dest->base);
}

void sfparse_pctdecode(sfparse_vec *dest, const sfparse_vec *src) {
  const uint8_t *p, *q;
  uint8_t *o;
  size_t len, slen;

  if (src->len == 0) {
    dest->len = 0;

    return;
  }

  o = dest->base;
  p = src->base;
  len = src->len;

  for (;;) {
    q = memchr(p, '%', len);
    if (q == NULL) {
      memcpy(o, p, len);
      o += len;

      dest->len = (size_t)(o - dest->base);

      return;
    }

    slen = (size_t)(q - p);
    memcpy(o, p, slen);
    o += slen;

    p = q + 1;

    pctdecode(o++, &p);

    len -= slen + 3;
  }
}

Coverage Report

Created: 2025-11-11 06:53