pb.h

#ifndef pb_h
#define pb_h

#ifndef PB_NS_BEGIN
# ifdef __cplusplus
#   define PB_NS_BEGIN extern "C" {
#   define PB_NS_END   }
# else
#   define PB_NS_BEGIN
#   define PB_NS_END
# endif
#endif /* PB_NS_BEGIN */

#ifndef PB_STATIC
# if __GNUC__
#   define PB_STATIC static __attribute((unused))
# else
#   define PB_STATIC static
# endif
#endif

#ifdef PB_STATIC_API
# ifndef PB_IMPLEMENTATION
#   define PB_IMPLEMENTATION
# endif
# define PB_API PB_STATIC
#endif

#if !defined(PB_API) && defined(_WIN32)
# ifdef PB_IMPLEMENTATION
#   define PB_API __declspec(dllexport)
# else
#   define PB_API __declspec(dllimport)
# endif
#endif

#ifndef PB_API
# define PB_API extern
#endif

#if defined(_MSC_VER) || defined(__UNIXOS2__) || defined(__SOL64__)
typedef unsigned char      uint8_t;
typedef signed char        int8_t;
typedef unsigned short     uint16_t;
typedef signed short       int16_t;
typedef unsigned int       uint32_t;
typedef signed int         int32_t;
typedef unsigned long long uint64_t;
typedef signed long long   int64_t;

# ifndef INT64_MIN
#   define INT64_MIN LLONG_MIN
# endif

# ifndef INT64_MAX
#   define INT64_MAX LLONG_MAX
# endif

#elif defined(__SCO__) || defined(__USLC__) || defined(__MINGW32__)
# include <stdint.h>
#else
# include <inttypes.h>
# if (defined(__sun__) || defined(__digital__))
#   if defined(__STDC__) && (defined(__arch64__) || defined(_LP64))
typedef unsigned long int uint64_t;
typedef signed long int   int64_t;
#   else
typedef unsigned long long uint64_t;
typedef signed long long   int64_t;
#   endif /* LP64 */
# endif /* __sun__ || __digital__ */
#endif

#include <limits.h>
#include <stddef.h>

PB_NS_BEGIN

/* types */

/* clang-format off */
#define PB_WIRETYPES(X)   /* X(id,    name,    fmt) */\
    X(VARINT, "varint", 'v') X(64BIT, "64bit", 'q') X(BYTES, "bytes", 's') \
    X(GSTART, "gstart", '!') X(GEND,  "gend",  '!') X(32BIT, "32bit", 'd') \

#define PB_TYPES(X)          /* X(name,     type,     fmt) */\
    X(double,   double,   'F')  X(float,    float,    'f') \
    X(int64,    int64_t,  'I')  X(uint64,   uint64_t, 'U') \
    X(int32,    int32_t,  'i')  X(fixed64,  uint64_t, 'X') \
    X(fixed32,  uint32_t, 'x')  X(bool,     int,      'b') \
    X(string,   pb_Slice, 't')  X(group,    pb_Slice, 'g') \
    X(message,  pb_Slice, 'S')  X(bytes,    pb_Slice, 's') \
    X(uint32,   uint32_t, 'u')  X(enum,     int32_t,  'v') \
    X(sfixed32, int32_t,  'y')  X(sfixed64, int64_t,  'Y') \
    X(sint32,   int32_t,  'j')  X(sint64,   int64_t,  'J') \

typedef enum pb_WireType {
#define X(id,name,fmt) PB_T##id,
    PB_WIRETYPES(X)
#undef  X
    PB_TWIRECOUNT
} pb_WireType;

typedef enum pb_FieldType {
    PB_TNONE,
#define X(name,type,fmt) PB_T##name,
    PB_TYPES(X)
#undef  X
    PB_TYPECOUNT
} pb_FieldType;
/* clang-format on */

/* conversions */

PB_API uint64_t pb_expandsig(uint32_t v);
PB_API uint32_t pb_encode_sint32(int32_t v);
PB_API int32_t  pb_decode_sint32(uint32_t v);
PB_API uint64_t pb_encode_sint64(int64_t v);
PB_API int64_t  pb_decode_sint64(uint64_t v);
PB_API uint32_t pb_encode_float(float v);
PB_API float    pb_decode_float(uint32_t v);
PB_API uint64_t pb_encode_double(double v);
PB_API double   pb_decode_double(uint64_t v);

/* decode */

/* clang-format off */
typedef struct pb_Slice { const char *p, *start, *end; } pb_Slice;
#define pb_gettype(v)      ((v) & 7)
#define pb_gettag(v)       ((v) >> 3)
#define pb_pair(tag, type) ((uint32_t)(tag) << 3 | ((uint32_t)(type) & 7))
/* clang-format on */

PB_API pb_Slice pb_slice(const char *p);
PB_API pb_Slice pb_lslice(const char *p, size_t len);

PB_API size_t pb_pos(const pb_Slice s);
PB_API size_t pb_len(const pb_Slice s);

PB_API size_t pb_readvarint32(pb_Slice *s, uint32_t *pv);
PB_API size_t pb_readvarint64(pb_Slice *s, uint64_t *pv);
PB_API size_t pb_readfixed32(pb_Slice *s, uint32_t *pv);
PB_API size_t pb_readfixed64(pb_Slice *s, uint64_t *pv);

PB_API size_t pb_readslice(pb_Slice *s, size_t len, pb_Slice *pv);
PB_API size_t pb_readbytes(pb_Slice *s, pb_Slice *pv);
PB_API size_t pb_readgroup(pb_Slice *s, uint32_t tag, pb_Slice *pv);

PB_API size_t pb_skipvarint(pb_Slice *s);
PB_API size_t pb_skipbytes(pb_Slice *s);
PB_API size_t pb_skipslice(pb_Slice *s, size_t len);
PB_API size_t pb_skipvalue(pb_Slice *s, uint32_t tag);

PB_API const char *pb_wtypename(int wiretype, const char *def);
PB_API const char *pb_typename(int type, const char *def);

PB_API int pb_typebyname(const char *name, int def);
PB_API int pb_wtypebyname(const char *name, int def);
PB_API int pb_wtypebytype(int type);

/* encode */

/* clang-format off */
typedef struct pb_Buffer { unsigned capacity, size; char *buff; } pb_Buffer;
#define pb_buffer(b)           ((b)->buff)
#define pb_bufflen(b)          ((b)->size)
#define pb_addsize(b, sz)      ((void)((b)->size += (unsigned)(sz)))
#define pb_prepbuffsize(b, sz) ((b)->size + (sz) <= (b)->capacity ? \
                           &(b)->buff[(b)->size] : pb_prepbuffsize_((b), (sz)))
/* clang-format on */

PB_API void  pb_initbuffer(pb_Buffer *b);
PB_API void  pb_resetbuffer(pb_Buffer *b);
PB_API char *pb_prepbuffsize_(pb_Buffer *b, size_t len);

PB_API pb_Slice pb_result(const pb_Buffer *b);

PB_API size_t pb_addvarint32(pb_Buffer *b, uint32_t v);
PB_API size_t pb_addvarint64(pb_Buffer *b, uint64_t v);
PB_API size_t pb_addfixed32(pb_Buffer *b, uint32_t v);
PB_API size_t pb_addfixed64(pb_Buffer *b, uint64_t v);

PB_API size_t pb_addslice(pb_Buffer *b, pb_Slice s);
PB_API size_t pb_addbytes(pb_Buffer *b, pb_Slice s);
PB_API size_t pb_addlength(pb_Buffer *b, size_t len, size_t prealloc);

/* type info database state and name table */

typedef struct pb_State pb_State;
typedef struct pb_Name  pb_Name;
typedef struct pb_Cache pb_Cache;

PB_API void pb_init(pb_State *S);
PB_API void pb_free(pb_State *S);

PB_API pb_Name *pb_newname(pb_State *S, pb_Slice s, pb_Cache *cache);
PB_API void     pb_delname(pb_State *S, pb_Name *name);
PB_API pb_Name *pb_usename(pb_Name *name);

PB_API const pb_Name *pb_name(const pb_State *S, pb_Slice s, pb_Cache *cache);

/* type info */

typedef struct pb_Type  pb_Type;
typedef struct pb_Field pb_Field;

#define PB_OK     0
#define PB_ERROR  1
#define PB_ENOMEM 2

PB_API int pb_load(pb_State *S, pb_Slice *s);

PB_API pb_Type  *pb_newtype(pb_State *S, pb_Name *tname);
PB_API void      pb_deltype(pb_State *S, pb_Type *t);
PB_API pb_Field *pb_newfield(pb_State *S, pb_Type *t, pb_Name *fn, int32_t n);
PB_API void      pb_delfield(pb_State *S, pb_Type *t, pb_Field *f);

PB_API const pb_Type  *pb_type(const pb_State *S, const pb_Name *tname);
PB_API const pb_Field *pb_fname(const pb_Type *t, const pb_Name *tname);
PB_API const pb_Field *pb_field(const pb_Type *t, int32_t number);

PB_API const pb_Name *pb_oneofname(const pb_Type *t, int oneof_index);

PB_API int pb_nexttype(const pb_State *S, const pb_Type **ptype);
PB_API int pb_nextfield(const pb_Type *t, const pb_Field **pfield);

PB_API pb_Field **pb_sortedfields(const pb_Type *t);

/* util: memory pool */

#define PB_POOLSIZE 4096

typedef struct pb_Pool {
    void  *pages;
    void  *freed;
    size_t obj_size;
} pb_Pool;

PB_API void pb_initpool(pb_Pool *pool, size_t obj_size);
PB_API void pb_freepool(pb_Pool *pool);

PB_API void *pb_poolalloc(pb_Pool *pool);
PB_API void  pb_poolfree(pb_Pool *pool, void *obj);

/* util: hash table */

typedef struct pb_Table pb_Table;
typedef struct pb_Entry pb_Entry;
typedef ptrdiff_t       pb_Key;

PB_API void pb_inittable(pb_Table *t, size_t entrysize);
PB_API void pb_freetable(pb_Table *t);

PB_API size_t pb_resizetable(pb_Table *t, size_t size);

PB_API pb_Entry *pb_gettable(const pb_Table *t, pb_Key key);
PB_API pb_Entry *pb_settable(pb_Table *t, pb_Key key);

PB_API int pb_nextentry(const pb_Table *t, const pb_Entry **pentry);

struct pb_Table {
    unsigned  size;
    unsigned  lastfree;
    unsigned  entry_size : sizeof(unsigned) * CHAR_BIT - 1;
    pb_Entry *hash;
};

struct pb_Entry {
    pb_Key   key;
    int      next;
    unsigned dead : 1;
};

/* fields */

#define PB_CACHE_SIZE (53)

typedef struct pb_NameEntry {
    struct pb_NameEntry *next;
    unsigned             hash : 32;
    unsigned             length : 16;
    unsigned             refcount : 16;
} pb_NameEntry;

typedef struct pb_NameTable {
    size_t         size;
    size_t         count;
    pb_NameEntry **hash;
} pb_NameTable;

typedef struct pb_CacheSlot {
    const char *name;
    unsigned    hash;
} pb_CacheSlot;

struct pb_Cache {
    pb_CacheSlot slots[PB_CACHE_SIZE][2];
    unsigned     hash;
};

struct pb_State {
    pb_NameTable nametable;
    pb_Table     types;
    pb_Pool      typepool;
    pb_Pool      fieldpool;
};

struct pb_Field {
    pb_Name *name;
    pb_Type *type;
    pb_Name *default_value;
    int32_t  number;
    uint32_t sorted_idx;
    uint32_t oneof_idx;
    unsigned type_id : 5; /* PB_T* enum */
    unsigned repeated : 1;
    unsigned packed : 1;
    unsigned scalar : 1;
};

struct pb_Type {
    pb_Name    *name;
    const char *basename;
    pb_Field  **sorted_fields;
    pb_Table    field_tags;
    pb_Table    field_names;
    pb_Table    oneof_index;
    unsigned    oneof_count; /* extra field count from oneof entries */
    unsigned    oneof_field; /* extra field in oneof declarations */
    unsigned    field_count : 28;
    unsigned    is_enum : 1;
    unsigned    is_map : 1;
    unsigned    is_proto3 : 1;
    unsigned    is_dead : 1;
};

PB_NS_END

#endif /* pb_h */

#if defined(PB_IMPLEMENTATION) && !defined(pb_implemented)
#define pb_implemented

#define PB_MAX_SIZET          ((unsigned)~0 - 100)
#define PB_MAX_HASHSIZE       ((unsigned)~0 - 100)
#define PB_MIN_STRTABLE_SIZE  16
#define PB_MIN_HASHTABLE_SIZE 8
#define PB_HASHLIMIT          5

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

PB_NS_BEGIN

/* conversions */

/* clang-format off */
PB_API uint32_t pb_encode_sint32(int32_t value)
{ return ((uint32_t)value << 1) ^ -(value < 0); }

PB_API int32_t pb_decode_sint32(uint32_t value)
{ return (value >> 1) ^ -(int32_t)(value & 1); }

PB_API uint64_t pb_encode_sint64(int64_t value)
{ return ((uint64_t)value << 1) ^ -(value < 0); }

PB_API int64_t pb_decode_sint64(uint64_t value)
{ return (value >> 1) ^ -(int64_t)(value & 1); }

PB_API uint64_t pb_expandsig(uint32_t value)
{ uint64_t m = (uint64_t)1U << 31; return (value ^ m) - m; }

PB_API uint32_t pb_encode_float(float value)
{ union { uint32_t u32; float f; } u; u.f = value; return u.u32; }

PB_API float pb_decode_float(uint32_t value)
{ union { uint32_t u32; float f; } u; u.u32 = value; return u.f; }

PB_API uint64_t pb_encode_double(double value)
{ union { uint64_t u64; double d; } u; u.d = value; return u.u64; }

PB_API double pb_decode_double(uint64_t value)
{ union { uint64_t u64; double d; } u; u.u64 = value; return u.d; }

/* decode */

PB_API pb_Slice pb_slice(const char *s)
{ return s ? pb_lslice(s, strlen(s)) : pb_lslice(NULL, 0); }
/* clang-format on */

PB_API size_t pb_pos(const pb_Slice s) { return s.p - s.start; }
PB_API size_t pb_len(const pb_Slice s) { return s.end - s.p; }

static size_t pb_readvarint_slow(pb_Slice *s, uint64_t *pv) {
    const char *p = s->p;
    uint64_t    n = 0;
    int         i = 0;
    while (s->p < s->end && i < 10) {
        int b = *s->p++;
        n |= ((uint64_t)b & 0x7F) << (7 * i++);
        if ((b & 0x80) == 0) return (*pv = n), i;
    }
    return (s->p = p), 0;
}

static size_t pb_readvarint32_fallback(pb_Slice *s, uint32_t *pv) {
    const uint8_t *p = (const uint8_t *)s->p, *o = p;
    uint32_t       b, n;
    for (;;) { /* clang-format off */
        n = *p++ - 0x80, n += (b = *p++) <<  7; if (!(b & 0x80)) break;
        n -= 0x80 <<  7, n += (b = *p++) << 14; if (!(b & 0x80)) break;
        n -= 0x80 << 14, n += (b = *p++) << 21; if (!(b & 0x80)) break;
        n -= 0x80 << 21, n += (b = *p++) << 28; if (!(b & 0x80)) break;
        /* n -= 0x80 << 28; */
        if (!(*p++ & 0x80)) break;
        if (!(*p++ & 0x80)) break;
        if (!(*p++ & 0x80)) break;
        if (!(*p++ & 0x80)) break;
        if (!(*p++ & 0x80)) break;
        return (*pv = 0), 0;
    } /* clang-format on */
    return (*pv = n, s->p = (const char *)p), p - o;
}

static size_t pb_readvarint64_fallback(pb_Slice *s, uint64_t *pv) {
    const uint8_t *p = (const uint8_t *)s->p, *o = p;
    uint32_t       b, n1, n2 = 0, n3 = 0;
    for (;;) { /* clang-format off */
        n1 = *p++ - 0x80, n1 += (b = *p++) <<  7; if (!(b & 0x80)) break;
        n1 -= 0x80 <<  7, n1 += (b = *p++) << 14; if (!(b & 0x80)) break;
        n1 -= 0x80 << 14, n1 += (b = *p++) << 21; if (!(b & 0x80)) break;
        n1 -= 0x80 << 21, n2 += (b = *p++)      ; if (!(b & 0x80)) break;
        n2 -= 0x80      , n2 += (b = *p++) <<  7; if (!(b & 0x80)) break;
        n2 -= 0x80 <<  7, n2 += (b = *p++) << 14; if (!(b & 0x80)) break;
        n2 -= 0x80 << 14, n2 += (b = *p++) << 21; if (!(b & 0x80)) break;
        n2 -= 0x80 << 21, n3 += (b = *p++)      ; if (!(b & 0x80)) break;
        n3 -= 0x80      , n3 += (b = *p++) <<  7; if (!(b & 0x80)) break;
        return (*pv = 0), 0;
    } /* clang-format on */
    *pv = n1 | ((uint64_t)n2 << 28) | ((uint64_t)n3 << 56);
    return (s->p = (const char *)p), p - o;
}

PB_API pb_Slice pb_lslice(const char *s, size_t len) {
    pb_Slice slice;
    slice.start = slice.p = s, slice.end = s + len;
    return slice;
}

PB_API size_t pb_readvarint32(pb_Slice *s, uint32_t *pv) {
    uint64_t u64;
    size_t   ret;
    if (s->p >= s->end) return (*pv = 0), 0;
    if (!(*s->p & 0x80)) return (*pv = *s->p++), 1;
    if (pb_len(*s) >= 10 || !(s->end[-1] & 0x80))
        return pb_readvarint32_fallback(s, pv);
    if ((ret = pb_readvarint_slow(s, &u64)) != 0) *pv = (uint32_t)u64;
    return ret;
}

PB_API size_t pb_readvarint64(pb_Slice *s, uint64_t *pv) {
    if (s->p >= s->end) return (*pv = 0), 0;
    if (!(*s->p & 0x80)) return (*pv = *s->p++), 1;
    if (pb_len(*s) >= 10 || !(s->end[-1] & 0x80))
        return pb_readvarint64_fallback(s, pv);
    return pb_readvarint_slow(s, pv);
}

PB_API size_t pb_readfixed32(pb_Slice *s, uint32_t *pv) {
    int      i;
    uint32_t n = 0;
    if (s->p + 4 > s->end) return 0;
    for (i = 3; i >= 0; --i) n <<= 8, n |= s->p[i] & 0xFF;
    return (s->p += 4, *pv = n), 4;
}

PB_API size_t pb_readfixed64(pb_Slice *s, uint64_t *pv) {
    int      i;
    uint64_t n = 0;
    if (s->p + 8 > s->end) return 0;
    for (i = 7; i >= 0; --i) n <<= 8, n |= s->p[i] & 0xFF;
    return (s->p += 8, *pv = n), 8;
}

PB_API size_t pb_readslice(pb_Slice *s, size_t len, pb_Slice *pv) {
    if (pb_len(*s) < len) return 0;
    pv->start = s->start, pv->p = s->p, pv->end = s->p + len;
    return (s->p = pv->end), len;
}

PB_API size_t pb_readbytes(pb_Slice *s, pb_Slice *pv) {
    const char *p = s->p;
    uint64_t    len;
    if (pb_readvarint64(s, &len) == 0 || pb_len(*s) < len) return (s->p = p), 0;
    pv->start = s->start, pv->p = s->p, pv->end = s->p + len;
    return (s->p = pv->end), s->p - p;
}

PB_API size_t pb_readgroup(pb_Slice *s, uint32_t tag, pb_Slice *pv) {
    const char *p = s->p;
    uint32_t    newtag = 0;
    size_t      count, nested = 0;
    assert(pb_gettype(tag) == PB_TGSTART);
    while ((count = pb_readvarint32(s, &newtag)) != 0) {
        if (nested == 0 && pb_gettype(newtag) == PB_TGEND) {
            if (pb_gettag(newtag) != pb_gettag(tag)) break;
            pv->start = s->start, pv->p = p, pv->end = s->p - count;
            return s->p - p;
        }
        if (pb_gettype(newtag) == PB_TGSTART)
            nested += 1;
        else if (pb_gettype(newtag) == PB_TGEND)
            nested -= 1;
        else if (pb_skipvalue(s, newtag) == 0)
            break;
    }
    return (s->p = p), 0;
}

PB_API size_t pb_skipvalue(pb_Slice *s, uint32_t tag) {
    const char *p = s->p;
    size_t      ret = 0;
    pb_Slice    data;
    switch (pb_gettype(tag)) {
    default: break;
    case PB_TVARINT: ret = pb_skipvarint(s); break;
    case PB_T64BIT: ret = pb_skipslice(s, 8); break;
    case PB_TBYTES: ret = pb_skipbytes(s); break;
    case PB_T32BIT: ret = pb_skipslice(s, 4); break;
    case PB_TGSTART: ret = pb_readgroup(s, tag, &data); break;
    }
    if (!ret) s->p = p;
    return ret;
}

PB_API size_t pb_skipvarint(pb_Slice *s) {
    const char *p = s->p, *op = p;
    while (p < s->end && (*p & 0x80) != 0) ++p;
    if (p >= s->end) return 0;
    return (s->p = ++p), p - op;
}

PB_API size_t pb_skipbytes(pb_Slice *s) {
    const char *p = s->p;
    uint64_t    var;
    if (!pb_readvarint64(s, &var)) return 0;
    if (pb_len(*s) < var) return (s->p = 0), 0;
    return (s->p += var), s->p - p;
}

PB_API size_t pb_skipslice(pb_Slice *s, size_t len) {
    if (s->p + len > s->end) return 0;
    return (s->p += len), len;
}

PB_API int pb_wtypebytype(int type) {
    switch (type) {
    case PB_Tdouble: return PB_T64BIT;
    case PB_Tfloat: return PB_T32BIT;
    case PB_Tint64: return PB_TVARINT;
    case PB_Tuint64: return PB_TVARINT;
    case PB_Tint32: return PB_TVARINT;
    case PB_Tfixed64: return PB_T64BIT;
    case PB_Tfixed32: return PB_T32BIT;
    case PB_Tbool: return PB_TVARINT;
    case PB_Tstring: return PB_TBYTES;
    case PB_Tmessage: return PB_TBYTES;
    case PB_Tbytes: return PB_TBYTES;
    case PB_Tuint32: return PB_TVARINT;
    case PB_Tenum: return PB_TVARINT;
    case PB_Tsfixed32: return PB_T32BIT;
    case PB_Tsfixed64: return PB_T64BIT;
    case PB_Tsint32: return PB_TVARINT;
    case PB_Tsint64: return PB_TVARINT;
    default: return PB_TWIRECOUNT;
    }
}

PB_API const char *pb_wtypename(int wiretype, const char *def) {
    switch (wiretype) { /* clang-format off */
#define X(id, name, fmt) case PB_T##id: return name;
        PB_WIRETYPES(X)
#undef X /* clang-format on */
    default: return def ? def : "<unknown>";
    }
}

PB_API const char *pb_typename(int type, const char *def) {
    switch (type) { /* clang-format off */
#define X(name, type, fmt) case PB_T##name: return #name;
        PB_TYPES(X)
#undef X /* clang-format on */
    default: return def ? def : "<unknown>";
    }
}

PB_API int pb_typebyname(const char *name, int def) {
    static struct entry {
        const char *name;
        int         value;
    } names[] = {
#define X(name, type, fmt) {#name, PB_T##name},
            PB_TYPES(X)
#undef X
                    {NULL, 0}};
    struct entry *p;
    for (p = names; p->name != NULL; ++p)
        if (strcmp(p->name, name) == 0) return p->value;
    return def;
}

PB_API int pb_wtypebyname(const char *name, int def) {
    static struct entry {
        const char *name;
        int         value;
    } names[] = {
#define X(id, name, fmt) {name, PB_T##id},
            PB_WIRETYPES(X)
#undef X
                    {NULL, 0}};
    struct entry *p;
    for (p = names; p->name != NULL; ++p)
        if (strcmp(p->name, name) == 0) return p->value;
    return def;
}

/* encode */

/* clang-format off */
PB_API pb_Slice pb_result(const pb_Buffer *b)
{ pb_Slice slice = pb_lslice(pb_buffer(b), pb_bufflen(b)); return slice; }

PB_API void pb_initbuffer(pb_Buffer *b)
{ memset(b, 0, sizeof(pb_Buffer)); }

PB_API void pb_resetbuffer(pb_Buffer *b)
{ free(b->buff); pb_initbuffer(b); }
/* clang-format on */

static int pb_write32(char *buff, uint32_t n) {
    int p, c = 0;
    assert(buff != NULL);
    do { /* clang-format off */
        p = n & 0x7F; if ((n >>= 7) == 0) break; *buff++ = p | 0x80, ++c;
        p = n & 0x7F; if ((n >>= 7) == 0) break; *buff++ = p | 0x80, ++c;
        p = n & 0x7F; if ((n >>= 7) == 0) break; *buff++ = p | 0x80, ++c;
        p = n & 0x7F; if ((n >>= 7) == 0) break; *buff++ = p | 0x80, ++c;
        p = n;
    } while (0); /* clang-format on */
    return (*buff++ = p), ++c;
}

static int pb_write64(char *buff, uint64_t n) {
    int p, c = 0;
    assert(buff != NULL);
    do { /* clang-format off */
        p = n & 0x7F; if ((n >>= 7) == 0) break; *buff++ = p | 0x80, ++c;
        p = n & 0x7F; if ((n >>= 7) == 0) break; *buff++ = p | 0x80, ++c;
        p = n & 0x7F; if ((n >>= 7) == 0) break; *buff++ = p | 0x80, ++c;
        p = n & 0x7F; if ((n >>= 7) == 0) break; *buff++ = p | 0x80, ++c;
        p = n & 0x7F; if ((n >>= 7) == 0) break; *buff++ = p | 0x80, ++c;
        p = n & 0x7F; if ((n >>= 7) == 0) break; *buff++ = p | 0x80, ++c;
        p = n & 0x7F; if ((n >>= 7) == 0) break; *buff++ = p | 0x80, ++c;
        p = n & 0x7F; if ((n >>= 7) == 0) break; *buff++ = p | 0x80, ++c;
        p = n & 0x7F; if ((n >>= 7) == 0) break; *buff++ = p | 0x80, ++c;
        p = n & 0x7F;
    } while (0); /* clang-format on */
    return (*buff++ = p), ++c;
}

PB_API char *pb_prepbuffsize_(pb_Buffer *b, size_t len) {
    char  *newp, *oldp = b->buff;
    size_t expected = pb_bufflen(b) + len;
    size_t newsize = sizeof(pb_Buffer) * 2;
    while (newsize < PB_MAX_SIZET / 2 && newsize < expected)
        newsize += newsize >> 1;
    if (newsize < expected) return NULL;
    if ((newp = (char *)realloc(oldp, newsize)) == NULL) return NULL;
    b->buff = newp, b->capacity = (unsigned)newsize;
    return &pb_buffer(b)[pb_bufflen(b)];
}

PB_API size_t pb_addslice(pb_Buffer *b, pb_Slice s) {
    size_t len = pb_len(s);
    char  *buff = pb_prepbuffsize(b, len);
    if (buff == NULL) return 0;
    return (memcpy(buff, s.p, len), pb_addsize(b, len)), len;
}

PB_API size_t pb_addlength(pb_Buffer *b, size_t len, size_t prealloc) {
    char   buff[10], *s;
    size_t bl, ml, rl = 0;
    if ((bl = pb_bufflen(b)) < len) return 0;
    ml = pb_write64(buff, bl - len);
    s = pb_buffer(b) + len - prealloc;
    assert(ml >= prealloc);
    if (ml > prealloc) {
        rl = ml - prealloc;
        if (pb_prepbuffsize(b, rl) == NULL) return 0;
        s = pb_buffer(b) + len - prealloc;
        memmove(s + ml, s + prealloc, bl - len);
    }
    memcpy(s, buff, ml), pb_addsize(b, rl);
    return ml + (bl - len);
}

PB_API size_t pb_addbytes(pb_Buffer *b, pb_Slice s) {
    size_t ret, len = pb_len(s);
    if (pb_prepbuffsize(b, len + 5) == NULL) return 0;
    ret = pb_addvarint32(b, (uint32_t)len);
    return ret + pb_addslice(b, s);
}

PB_API size_t pb_addvarint32(pb_Buffer *b, uint32_t n) {
    char  *buff = pb_prepbuffsize(b, 5);
    size_t l;
    if (buff == NULL) return 0;
    l = pb_write32(buff, n), pb_addsize(b, l);
    return l;
}

PB_API size_t pb_addvarint64(pb_Buffer *b, uint64_t n) {
    char  *buff = pb_prepbuffsize(b, 10);
    size_t l;
    if (buff == NULL) return 0;
    l = pb_write64(buff, n), pb_addsize(b, l);
    return l;
}

PB_API size_t pb_addfixed32(pb_Buffer *b, uint32_t n) {
    char *ch = pb_prepbuffsize(b, 4);
    if (ch == NULL) return 0;
    *ch++ = n & 0xFF, n >>= 8;
    *ch++ = n & 0xFF, n >>= 8;
    *ch++ = n & 0xFF, n >>= 8;
    *ch = n & 0xFF;
    return pb_addsize(b, 4), 4;
}

PB_API size_t pb_addfixed64(pb_Buffer *b, uint64_t n) {
    char *ch = pb_prepbuffsize(b, 8);
    if (ch == NULL) return 0;
    *ch++ = n & 0xFF, n >>= 8;
    *ch++ = n & 0xFF, n >>= 8;
    *ch++ = n & 0xFF, n >>= 8;
    *ch++ = n & 0xFF, n >>= 8;
    *ch++ = n & 0xFF, n >>= 8;
    *ch++ = n & 0xFF, n >>= 8;
    *ch++ = n & 0xFF, n >>= 8;
    *ch = n & 0xFF;
    return pb_addsize(b, 8), 8;
}

/* memory pool */

PB_API void pb_initpool(pb_Pool *pool, size_t obj_size) {
    memset(pool, 0, sizeof(pb_Pool));
    pool->obj_size = obj_size;
    assert(obj_size > sizeof(void *) && obj_size < PB_POOLSIZE / 4);
}

PB_API void pb_freepool(pb_Pool *pool) {
    void *next, *page = pool->pages;
    for (; page; page = next) {
        next = *(void **)((char *)page + PB_POOLSIZE - sizeof(void *));
        free(page);
    }
    pb_initpool(pool, pool->obj_size);
}

PB_API void *pb_poolalloc(pb_Pool *pool) {
    void *obj = pool->freed;
    if (obj == NULL) {
        size_t objsize = pool->obj_size, offset;
        void  *newpage = malloc(PB_POOLSIZE);
        if (newpage == NULL) return NULL;
        offset = ((PB_POOLSIZE - sizeof(void *)) / objsize - 1) * objsize;
        for (; offset > 0; offset -= objsize) {
            void **entry = (void **)((char *)newpage + offset);
            *entry = pool->freed, pool->freed = (void *)entry;
        }
        *(void **)((char *)newpage + PB_POOLSIZE
                   - sizeof(void *)) = pool->pages;
        pool->pages = newpage;
        return newpage;
    }
    pool->freed = *(void **)obj;
    return obj;
}

/* clang-format off */
PB_API void pb_poolfree(pb_Pool *pool, void *obj)
{ *(void**)obj = pool->freed, pool->freed = obj; }

/* hash table */

#define pbT_offset(a,b) ((char*)(a) - (char*)(b))
#define pbT_index(a,b)  ((pb_Entry*)((char*)(a) + (b)))

PB_API void pb_inittable(pb_Table *t, size_t entrysize)
{ memset(t, 0, sizeof(pb_Table)), t->entry_size = (unsigned)entrysize; }

PB_API void pb_freetable(pb_Table *t)
{ free(t->hash); pb_inittable(t, t->entry_size); }
/* clang-format on */

static pb_Entry *pbT_hash(const pb_Table *t, pb_Key key) {
    size_t h = ((size_t)key * 2654435761U) & (t->size - 1);
    if (key && h == 0) h = 1;
    return pbT_index(t->hash, h * t->entry_size);
}

static pb_Entry *pbT_newkey(pb_Table *t, pb_Key key) {
    pb_Entry *mp, *on, *next, *f = NULL;
    if (t->size == 0 && pb_resizetable(t, (size_t)t->size * 2) == 0)
        return NULL;
    if ((mp = pbT_hash(t, key))->key != 0 && !mp->dead) {
        while (f == NULL) {
            pb_Entry *cur = pbT_index(t->hash, t->lastfree -= t->entry_size);
            if ((cur->key == 0 || cur->dead) && cur->next == 0) f = cur;
        }
        if (f == t->hash) {
            if (pb_resizetable(t, t->size * (size_t)2) == 0) return NULL;
            return pbT_newkey(t, key);
        }
        if ((on = pbT_hash(t, mp->key)) != mp) {
            while ((next = pbT_index(on, on->next)) != mp) on = next;
            on->next = pbT_offset(f, on);
            memcpy(f, mp, t->entry_size);
            if (mp->next != 0) f->next += pbT_offset(mp, f), mp->next = 0;
        } else {
            if (mp->next != 0)
                f->next = pbT_offset(mp, f) + mp->next;
            else
                assert(f->next == 0);
            mp->next = pbT_offset(f, mp), mp = f;
        }
    }
    mp->key = key, mp->dead = 0;
    if (t->entry_size != sizeof(pb_Entry))
        memset(mp + 1, 0, t->entry_size - sizeof(pb_Entry));
    return mp;
}

PB_API size_t pb_resizetable(pb_Table *t, size_t size) {
    pb_Table nt = *t;
    unsigned i, rawsize = t->size * t->entry_size;
    unsigned newsize = PB_MIN_HASHTABLE_SIZE;
    while (newsize < PB_MAX_HASHSIZE / t->entry_size && newsize < size)
        newsize <<= 1;
    if (newsize < size) return 0;
    nt.size = newsize;
    nt.lastfree = nt.entry_size * newsize;
    nt.hash = (pb_Entry *)malloc(nt.lastfree);
    if (nt.hash == NULL) return 0;
    memset(nt.hash, 0, nt.lastfree);
    nt.hash->dead = 1;
    for (i = 0; i < rawsize; i += t->entry_size) {
        pb_Entry *olde = (pb_Entry *)((char *)t->hash + i);
        pb_Entry *newe = pbT_newkey(&nt, olde->key);
        if (nt.entry_size > sizeof(pb_Entry))
            memcpy(newe + 1, olde + 1, nt.entry_size - sizeof(pb_Entry));
    }
    return (free(t->hash), *t = nt), newsize;
}

PB_API pb_Entry *pb_gettable(const pb_Table *t, pb_Key key) {
    pb_Entry *entry;
    if (t == NULL || t->size == 0) return NULL;
    for (entry = pbT_hash(t, key); entry->key != key || entry->dead;
         entry = pbT_index(entry, entry->next))
        if (entry->next == 0) return NULL;
    return entry;
}

PB_API pb_Entry *pb_settable(pb_Table *t, pb_Key key) {
    pb_Entry *entry;
    if ((entry = pb_gettable(t, key)) != NULL) return entry;
    return pbT_newkey(t, key);
}

PB_API int pb_nextentry(const pb_Table *t, const pb_Entry **pentry) {
    size_t i = *pentry ? pbT_offset(*pentry, t->hash) : 0;
    size_t size = t->hash ? (size_t)t->size * t->entry_size : 0;
    if (*pentry == NULL && t->hash && !t->hash->dead)
        return (*pentry = t->hash), 1;
    while (i += t->entry_size, i < size) {
        pb_Entry *entry = pbT_index(t->hash, i);
        if (entry->key && !entry->dead) return (*pentry = entry), 1;
    }
    return (*pentry = NULL), 0;
}

/* name table */

/* clang-format off */
static void pbN_init(pb_State *S)
{ memset(&S->nametable, 0, sizeof(pb_NameTable)); }

PB_API pb_Name *pb_usename(pb_Name *name)
{ if (name != NULL) ++((pb_NameEntry*)name-1)->refcount; return name; }
/* clang-format on */

static void pbN_free(pb_State *S) {
    pb_NameTable *nt = &S->nametable;
    size_t        i;
    for (i = 0; i < nt->size; ++i) {
        pb_NameEntry *next, *ne = nt->hash[i];
        while (ne != NULL) next = ne->next, free(ne), ne = next;
    }
    free(nt->hash), pbN_init(S);
}

static unsigned pbN_calchash(pb_Slice s) {
    size_t   i, len = pb_len(s);
    unsigned h = (unsigned)len;
    for (i = 0; i < len; ++i)
        h ^= ((h << 5) + (h >> 2) + (unsigned char)(s.p[i]));
    return h;
}

static size_t pbN_resize(pb_State *S, size_t size) {
    pb_NameTable  *nt = &S->nametable;
    pb_NameEntry **hash;
    size_t         i, newsize = PB_MIN_STRTABLE_SIZE;
    while (newsize < PB_MAX_HASHSIZE / sizeof(pb_NameEntry *) && newsize < size)
        newsize <<= 1;
    if (newsize < size) return 0;
    hash = (pb_NameEntry **)malloc(newsize * sizeof(pb_NameEntry *));
    if (hash == NULL) return 0;
    memset(hash, 0, newsize * sizeof(pb_NameEntry *));
    for (i = 0; i < nt->size; ++i) {
        pb_NameEntry *next, **newh, *entry = nt->hash[i];
        for (; entry != NULL; entry = next) {
            next = entry->next;
            newh = &hash[entry->hash & (newsize - 1)];
            entry->next = *newh, *newh = entry;
        }
    }
    free(nt->hash);
    return (nt->hash = hash, nt->size = newsize), newsize;
}

static pb_NameEntry *pbN_newname(pb_State *S, pb_Slice s, unsigned hash) {
    pb_NameTable  *nt = &S->nametable;
    pb_NameEntry **list, *newobj;
    size_t         len = pb_len(s);
    if (nt->count >= nt->size && !pbN_resize(S, nt->size * 2)) return NULL;
    list = &nt->hash[hash & (nt->size - 1)];
    newobj = (pb_NameEntry *)malloc(sizeof(pb_NameEntry) + len + 1);
    if (newobj == NULL) return NULL;
    newobj->next = *list;
    newobj->length = (unsigned)len;
    newobj->refcount = 0;
    newobj->hash = hash;
    memcpy(newobj + 1, s.p, len);
    ((char *)(newobj + 1))[len] = '\0';
    ++nt->count;
    return (*list = newobj), newobj;
}

static void pbN_delname(pb_State *S, pb_NameEntry *name) {
    pb_NameTable  *nt = &S->nametable;
    pb_NameEntry **list = &nt->hash[name->hash & (nt->size - 1)];
    for (; *list != NULL; list = &(*list)->next) {
        if (*list == name) {
            *list = (*list)->next, --nt->count, free(name);
            break;
        }
    }
}

static pb_NameEntry *pbN_getname(const pb_State *S, pb_Slice s, unsigned hash) {
    const pb_NameTable *nt = &S->nametable;
    pb_NameEntry       *entry;
    size_t              len = pb_len(s);
    if (!nt->hash) return NULL;
    entry = nt->hash[hash & (nt->size - 1)];
    for (; entry != NULL; entry = entry->next)
        if (entry->hash == hash && entry->length == len
            && memcmp(s.p, entry + 1, len) == 0)
            return entry;
    return NULL;
}

PB_API void pb_delname(pb_State *S, pb_Name *name) {
    pb_NameEntry *ne;
    if (name == NULL) return;
    if ((ne = (pb_NameEntry *)name - 1)->refcount > 1)
        --ne->refcount;
    else
        pbN_delname(S, ne);
}

PB_API pb_Name *pb_newname(pb_State *S, pb_Slice s, pb_Cache *cache) {
    pb_NameEntry *entry;
    if (s.p == NULL) return NULL;
    (void)cache, assert(cache == NULL);
    /* if (cache == NULL) */ {
        unsigned hash = pbN_calchash(s);
        entry = pbN_getname(S, s, hash);
        if (entry == NULL) entry = pbN_newname(S, s, hash);
    }
    /* else {
        pb_Name *name = (pb_Name*)pb_name(S, s, cache);
        if (name) return pb_usename(name);
        entry = pbN_newname(S, s, cache->hash);
    }*/
    return entry ? pb_usename((pb_Name *)(entry + 1)) : NULL;
}

PB_API const pb_Name *pb_name(const pb_State *S, pb_Slice s, pb_Cache *cache) {
    pb_NameEntry *entry = NULL;
    pb_CacheSlot *slot;
    if (S == NULL || s.p == NULL) return NULL;
    if (cache == NULL)
        entry = pbN_getname(S, s, pbN_calchash(s));
    else {
        slot = cache->slots[((uintptr_t)s.p * 2654435761U) % PB_CACHE_SIZE];
        if (slot[0].name == s.p)
            entry = pbN_getname(S, s, /*cache->hash = */ slot[0].hash);
        else if (slot[1].name == s.p)
            entry = pbN_getname(S, s, /*cache->hash = */ (++slot)[0].hash);
        else
            slot[1] = slot[0], slot[0].name = s.p;
        if (entry == NULL) {
            /*cache->hash = */ slot[0].hash = pbN_calchash(s);
            entry = pbN_getname(S, s, slot[0].hash);
        }
    }
    return entry ? (pb_Name *)(entry + 1) : NULL;
}

/* state */

/* clang-format off */
typedef struct pb_TypeEntry { pb_Entry entry; pb_Type *value; } pb_TypeEntry;
typedef struct pb_FieldEntry { pb_Entry entry; pb_Field *value; } pb_FieldEntry;
/* clang-format on */

typedef struct pb_OneofEntry {
    pb_Entry entry;
    pb_Name *name;
    unsigned index;
} pb_OneofEntry;

PB_API void pb_init(pb_State *S) {
    memset(S, 0, sizeof(pb_State));
    S->types.entry_size = sizeof(pb_TypeEntry);
    pb_initpool(&S->typepool, sizeof(pb_Type));
    pb_initpool(&S->fieldpool, sizeof(pb_Field));
}

PB_API void pb_free(pb_State *S) {
    const pb_Entry *e = NULL;
    if (S == NULL) return;
    while (pb_nextentry(&S->types, &e)) {
        pb_TypeEntry *te = (pb_TypeEntry *)e;
        if (te->value != NULL) pb_deltype(S, te->value);
    }
    pb_freetable(&S->types);
    pb_freepool(&S->typepool);
    pb_freepool(&S->fieldpool);
    pbN_free(S);
}

PB_API const pb_Type *pb_type(const pb_State *S, const pb_Name *tname) {
    pb_TypeEntry *te = NULL;
    if (S != NULL && tname != NULL)
        te = (pb_TypeEntry *)pb_gettable(&S->types, (pb_Key)tname);
    return te && !te->value->is_dead ? te->value : NULL;
}

PB_API const pb_Field *pb_fname(const pb_Type *t, const pb_Name *name) {
    pb_FieldEntry *fe = NULL;
    if (t != NULL && name != NULL)
        fe = (pb_FieldEntry *)pb_gettable(&t->field_names, (pb_Key)name);
    return fe ? fe->value : 0;
}

PB_API const pb_Field *pb_field(const pb_Type *t, int32_t number) {
    pb_FieldEntry *fe = NULL;
    if (t != NULL) fe = (pb_FieldEntry *)pb_gettable(&t->field_tags, number);
    return fe ? fe->value : NULL;
}

PB_API const pb_Name *pb_oneofname(const pb_Type *t, int idx) {
    pb_OneofEntry *oe = NULL;
    if (t != NULL) oe = (pb_OneofEntry *)pb_gettable(&t->oneof_index, idx);
    return oe ? oe->name : NULL;
}

PB_API int pb_nexttype(const pb_State *S, const pb_Type **ptype) {
    if (S != NULL) {
        const pb_Entry *ent = NULL;
        if (*ptype != NULL)
            ent = pb_gettable(&S->types, (pb_Key)(*ptype)->name);
        while (pb_nextentry(&S->types, &ent)) {
            const pb_TypeEntry *e = (const pb_TypeEntry *)ent;
            if ((*ptype = e->value) != NULL && !(*ptype)->is_dead) return 1;
        }
    }
    return (*ptype = NULL), 0;
}

PB_API int pb_nextfield(const pb_Type *t, const pb_Field **pfield) {
    if (t != NULL) {
        const pb_Entry *ent = NULL;
        if (*pfield != NULL)
            ent = pb_gettable(&t->field_tags, (*pfield)->number);
        while (pb_nextentry(&t->field_tags, &ent)) {
            const pb_FieldEntry *e = (const pb_FieldEntry *)ent;
            if ((*pfield = e->value) != NULL) return 1;
        }
    }
    return (*pfield = NULL), 0;
}

/* clang-format off */
static int pb_cmpfield(const void *a, const void *b)
{ return (*(const pb_Field **)a)->number - (*(const pb_Field **)b)->number; }
/* clang-format on */

PB_API pb_Field **pb_sortedfields(const pb_Type *t) {
    if (t == NULL) return NULL;
    if (!t->sorted_fields && t->field_count) {
        unsigned        i = 0;
        const pb_Field *f = NULL;
        pb_Field      **list;
        size_t          size = sizeof(pb_Field *) * t->field_count;
        list = (pb_Field **)malloc(size);
        if (list == NULL) return NULL;
        while (pb_nextfield(t, &f)) list[i++] = (pb_Field *)f;
        qsort(list, i, sizeof(pb_Field *), pb_cmpfield);
        for (i = 0; i < t->field_count; i++) list[i]->sorted_idx = i + 1;
        ((pb_Type *)t)->sorted_fields = list;
    }
    return t->sorted_fields;
}

/* new type/field */

/* clang-format off */
static void pb_invalidsort(pb_Type *t)
{ if (t->sorted_fields) free(t->sorted_fields), t->sorted_fields = NULL; }
/* clang-format on */

static const char *pbT_basename(const char *tname) {
    const char *end = tname + strlen(tname);
    while (tname < end && *--end != '.');
    return *end != '.' ? end : end + 1;
}

static void pbT_inittype(pb_Type *t) {
    memset(t, 0, sizeof(pb_Type));
    pb_inittable(&t->field_names, sizeof(pb_FieldEntry));
    pb_inittable(&t->field_tags, sizeof(pb_FieldEntry));
    pb_inittable(&t->oneof_index, sizeof(pb_OneofEntry));
}

static void pbT_freefield(pb_State *S, pb_Field *f) {
    pb_delname(S, f->default_value);
    pb_delname(S, f->name);
    pb_poolfree(&S->fieldpool, f);
}

PB_API pb_Type *pb_newtype(pb_State *S, pb_Name *tname) {
    pb_TypeEntry *te;
    pb_Type      *t;
    if (tname == NULL) return NULL;
    te = (pb_TypeEntry *)pb_settable(&S->types, (pb_Key)tname);
    if (te == NULL) return NULL;
    if ((t = te->value) != NULL) return t->is_dead = 0, t;
    if (!(t = (pb_Type *)pb_poolalloc(&S->typepool))) return NULL;
    pbT_inittype(t);
    t->name = tname;
    t->basename = pbT_basename((const char *)tname);
    return te->value = t;
}

PB_API void pb_deltype(pb_State *S, pb_Type *t) {
    const pb_Entry *e = NULL;
    if (S == NULL || t == NULL) return;
    while (pb_nextentry(&t->field_names, &e)) {
        const pb_FieldEntry *nf = (const pb_FieldEntry *)e;
        if (nf->value != NULL) {
            pb_FieldEntry *of = (pb_FieldEntry *)pb_gettable(&t->field_tags,
                                                             nf->value->number);
            if (of && of->value == nf->value)
                of->entry.dead = 1, of->value = NULL;
            pbT_freefield(S, nf->value);
        }
    }
    while (pb_nextentry(&t->field_tags, &e)) {
        pb_FieldEntry *nf = (pb_FieldEntry *)e;
        if (nf->value != NULL) pbT_freefield(S, nf->value);
    }
    while (pb_nextentry(&t->oneof_index, &e)) {
        pb_OneofEntry *oe = (pb_OneofEntry *)e;
        pb_delname(S, oe->name);
    }
    pb_freetable(&t->field_tags);
    pb_freetable(&t->field_names);
    pb_freetable(&t->oneof_index);
    pb_invalidsort(t);
    /*pb_delname(S, t->name); */
    /*pb_poolfree(&S->typepool, t); */
    t->oneof_field = 0, t->field_count = 0;
    t->is_dead = 1;
}

PB_API pb_Field *pb_newfield(pb_State *S, pb_Type *t, pb_Name *fn, int32_t n) {
    pb_FieldEntry *nf, *tf;
    pb_Field      *f;
    if (fn == NULL) return NULL;
    nf = (pb_FieldEntry *)pb_settable(&t->field_names, (pb_Key)fn);
    tf = (pb_FieldEntry *)pb_settable(&t->field_tags, n);
    if (nf == NULL || tf == NULL) return NULL;
    if ((f = nf->value) != NULL && tf->value == f)
        return pb_delname(S, f->default_value), (f->default_value = NULL), f;
    if (!(f = (pb_Field *)pb_poolalloc(&S->fieldpool))) return NULL;
    memset(f, 0, sizeof(pb_Field));
    f->name = fn, f->type = t, f->number = n;
    if (nf->value && pb_field(t, nf->value->number) != nf->value)
        pbT_freefield(S, nf->value), --t->field_count;
    if (tf->value && pb_fname(t, tf->value->name) != tf->value)
        pbT_freefield(S, tf->value), --t->field_count;
    pb_invalidsort(t);
    return ++t->field_count, (nf->value = tf->value = f), f;
}

PB_API void pb_delfield(pb_State *S, pb_Type *t, pb_Field *f) {
    pb_FieldEntry *nf, *tf;
    int            count = 0;
    if (S == NULL || t == NULL || f == NULL) return;
    nf = (pb_FieldEntry *)pb_gettable(&t->field_names, (pb_Key)f->name);
    tf = (pb_FieldEntry *)pb_gettable(&t->field_tags, (pb_Key)f->number);
    if (nf && nf->value == f) nf->entry.dead = 1, nf->value = NULL, ++count;
    if (tf && tf->value == f) tf->entry.dead = 1, tf->value = NULL, ++count;
    if (count) {
        if (f->oneof_idx) --t->oneof_field;
        pbT_freefield(S, f), --t->field_count;
        pb_invalidsort(t);
    }
}

/* .pb proto loader */

typedef struct pb_Loader         pb_Loader;
typedef struct pbL_FieldInfo     pbL_FieldInfo;
typedef struct pbL_EnumValueInfo pbL_EnumValueInfo;
typedef struct pbL_EnumInfo      pbL_EnumInfo;
typedef struct pbL_TypeInfo      pbL_TypeInfo;
typedef struct pbL_FileInfo      pbL_FileInfo;

/* clang-format off */
#define pbC(e)  do { int r = (e); if (r != PB_OK) return r; } while (0)
#define pbCM(e) do { if ((e) == NULL) return PB_ENOMEM; } while (0)
#define pbCE(e) do { if ((e) == NULL) return PB_ERROR; } while (0)

typedef struct pb_ArrayHeader { unsigned count, capacity; } pb_ArrayHeader;

#define pbL_rawh(A)   ((pb_ArrayHeader *)(A) - 1)
#define pbL_delete(A) ((A) ? (void)free(pbL_rawh(A)) : (void)0)
#define pbL_count(A)  ((A) ? pbL_rawh(A)->count : 0)
#define pbL_add(A)    (pbL_grow((void *)&(A), sizeof(*(A))) == PB_OK && \
                       (A) != NULL ? &(A)[pbL_rawh(A)->count++] : NULL)
/* clang-format on */

/* max DescriptorProto nesting depth; DoS bound for untrusted input */
#define PB_MAX_LEVELS (100)

struct pb_Loader {
    pb_State *S;
    pb_Slice  s;
    pb_Buffer b;
    int       is_proto3;
};

/* parsers */

struct pbL_EnumValueInfo {
    pb_Slice name;
    int32_t  number;
};

struct pbL_EnumInfo {
    pb_Slice           name;
    pbL_EnumValueInfo *value;
};

struct pbL_FieldInfo {
    pb_Slice name;
    pb_Slice type_name;
    pb_Slice extendee;
    pb_Slice default_value;
    int32_t  number;
    int32_t  label;
    int32_t  type;
    int32_t  oneof_index;
    int32_t  packed;
};

struct pbL_TypeInfo {
    pb_Slice       name;
    int32_t        is_map;
    pbL_FieldInfo *field;
    pbL_FieldInfo *extension;
    pbL_EnumInfo  *enum_type;
    pbL_TypeInfo  *nested_type;
    pb_Slice      *oneof_decl;
};

struct pbL_FileInfo {
    pb_Slice       package;
    pb_Slice       syntax;
    pbL_EnumInfo  *enum_type;
    pbL_TypeInfo  *message_type;
    pbL_FieldInfo *extension;
};

/* clang-format off */
static int pbL_readbytes(pb_Loader *L, pb_Slice *pv)
{ return pb_readbytes(&L->s, pv) == 0 ? PB_ERROR : PB_OK; }

static int pbL_beginmsg(pb_Loader *L, pb_Slice *pv)
{ pb_Slice v; pbC(pbL_readbytes(L, &v)); return (*pv = L->s, L->s = v, PB_OK); }
/* clang-format on */

static void pbL_endmsg(pb_Loader *L, pb_Slice *pv) { L->s = *pv; }

static int pbL_grow(void *p, size_t objs) {
    union {
        void *p, **pp;
    } up;
    pb_ArrayHeader *nh, *h = (up.p = p, *up.pp) ? pbL_rawh(*up.pp) : NULL;
    if (h == NULL || h->capacity <= h->count) {
        size_t used = (h ? h->count : 0), bytes;
        size_t size = used + 4, nsize = size + (size >> 1);
        if (nsize < size) return PB_ENOMEM;
        bytes = sizeof(pb_ArrayHeader) + nsize * objs;
        nh = (pb_ArrayHeader *)realloc(h, bytes);
        if (nh == NULL) return PB_ENOMEM;
        nh->count = (unsigned)used, nh->capacity = (unsigned)nsize;
        *up.pp = nh + 1;
        memset((char *)*up.pp + used * objs, 0, (nsize - used) * objs);
    }
    return PB_OK;
}

static int pbL_readint32(pb_Loader *L, int32_t *pv) {
    uint32_t v;
    if (pb_readvarint32(&L->s, &v) == 0) return PB_ERROR;
    return (*pv = (int32_t)v), PB_OK;
}

static int pbL_FieldOptions(pb_Loader *L, pbL_FieldInfo *info) {
    pb_Slice s;
    uint32_t tag;
    pbC(pbL_beginmsg(L, &s));
    while (pb_readvarint32(&L->s, &tag)) {
        switch (tag) {
        case pb_pair(2, PB_TVARINT): /* bool packed */
            pbC(pbL_readint32(L, &info->packed));
            break;
        default:
            if (pb_skipvalue(&L->s, tag) == 0) return PB_ERROR;
        }
    }
    return pbL_endmsg(L, &s), PB_OK;
}

static int pbL_FieldDescriptorProto(pb_Loader *L, pbL_FieldInfo *info) {
    pb_Slice s;
    uint32_t tag;
    pbCM(info);
    pbC(pbL_beginmsg(L, &s));
    info->packed = -1;
    while (pb_readvarint32(&L->s, &tag)) {
        switch (tag) {
        case pb_pair(1, PB_TBYTES): /* string name */
            pbC(pbL_readbytes(L, &info->name));
            break;
        case pb_pair(3, PB_TVARINT): /* int32 number */
            pbC(pbL_readint32(L, &info->number));
            break;
        case pb_pair(4, PB_TVARINT): /* Label label */
            pbC(pbL_readint32(L, &info->label));
            break;
        case pb_pair(5, PB_TVARINT): /* Type type */
            pbC(pbL_readint32(L, &info->type));
            break;
        case pb_pair(6, PB_TBYTES): /* string type_name */
            pbC(pbL_readbytes(L, &info->type_name));
            break;
        case pb_pair(2, PB_TBYTES): /* string extendee */
            pbC(pbL_readbytes(L, &info->extendee));
            break;
        case pb_pair(7, PB_TBYTES): /* string default_value */
            pbC(pbL_readbytes(L, &info->default_value));
            break;
        case pb_pair(8, PB_TBYTES): /* FieldOptions options */
            pbC(pbL_FieldOptions(L, info));
            break;
        case pb_pair(9, PB_TVARINT): /* int32 oneof_index */
            pbC(pbL_readint32(L, &info->oneof_index));
            ++info->oneof_index;
            break;
        default:
            if (pb_skipvalue(&L->s, tag) == 0) return PB_ERROR;
        }
    }
    return pbL_endmsg(L, &s), PB_OK;
}

static int pbL_EnumValueDescriptorProto(pb_Loader *L, pbL_EnumValueInfo *info) {
    pb_Slice s;
    uint32_t tag;
    pbCM(info);
    pbC(pbL_beginmsg(L, &s));
    while (pb_readvarint32(&L->s, &tag)) {
        switch (tag) {
        case pb_pair(1, PB_TBYTES): /* string name */
            pbC(pbL_readbytes(L, &info->name));
            break;
        case pb_pair(2, PB_TVARINT): /* int32 number */
            pbC(pbL_readint32(L, &info->number));
            break;
        default:
            if (pb_skipvalue(&L->s, tag) == 0) return PB_ERROR;
        }
    }
    return pbL_endmsg(L, &s), PB_OK;
}

static int pbL_EnumDescriptorProto(pb_Loader *L, pbL_EnumInfo *info) {
    pb_Slice s;
    uint32_t tag;
    pbCM(info);
    pbC(pbL_beginmsg(L, &s));
    while (pb_readvarint32(&L->s, &tag)) {
        switch (tag) {
        case pb_pair(1, PB_TBYTES): /* string name */
            pbC(pbL_readbytes(L, &info->name));
            break;
        case pb_pair(2, PB_TBYTES): /* EnumValueDescriptorProto value */
            pbC(pbL_EnumValueDescriptorProto(L, pbL_add(info->value)));
            break;
        default:
            if (pb_skipvalue(&L->s, tag) == 0) return PB_ERROR;
        }
    }
    return pbL_endmsg(L, &s), PB_OK;
}

static int pbL_MessageOptions(pb_Loader *L, pbL_TypeInfo *info) {
    pb_Slice s;
    uint32_t tag;
    pbCM(info);
    pbC(pbL_beginmsg(L, &s));
    while (pb_readvarint32(&L->s, &tag)) {
        switch (tag) {
        case pb_pair(7, PB_TVARINT): /* bool map_entry */
            pbC(pbL_readint32(L, &info->is_map));
            break;
        default:
            if (pb_skipvalue(&L->s, tag) == 0) return PB_ERROR;
        }
    }
    return pbL_endmsg(L, &s), PB_OK;
}

static int pbL_OneofDescriptorProto(pb_Loader *L, pbL_TypeInfo *info) {
    pb_Slice s;
    uint32_t tag;
    pbCM(info);
    pbC(pbL_beginmsg(L, &s));
    while (pb_readvarint32(&L->s, &tag)) {
        switch (tag) {
        case pb_pair(1, PB_TBYTES): /* string name */
            pbC(pbL_readbytes(L, pbL_add(info->oneof_decl)));
            break;
        default:
            if (pb_skipvalue(&L->s, tag) == 0) return PB_ERROR;
        }
    }
    return pbL_endmsg(L, &s), PB_OK;
}

static int pbL_DescriptorProto(pb_Loader *L, pbL_TypeInfo *info, int level) {
    pb_Slice s;
    uint32_t tag;
    if (level > PB_MAX_LEVELS) return PB_ERROR;
    pbCM(info);
    pbC(pbL_beginmsg(L, &s));
    while (pb_readvarint32(&L->s, &tag)) {
        switch (tag) {
        case pb_pair(1, PB_TBYTES): /* string name */
            pbC(pbL_readbytes(L, &info->name));
            break;
        case pb_pair(2, PB_TBYTES): /* FieldDescriptorProto field */
            pbC(pbL_FieldDescriptorProto(L, pbL_add(info->field)));
            break;
        case pb_pair(6, PB_TBYTES): /* FieldDescriptorProto extension */
            pbC(pbL_FieldDescriptorProto(L, pbL_add(info->extension)));
            break;
        case pb_pair(3, PB_TBYTES): /* DescriptorProto nested_type */
            pbC(pbL_DescriptorProto(L, pbL_add(info->nested_type), level + 1));
            break;
        case pb_pair(4, PB_TBYTES): /* EnumDescriptorProto enum_type */
            pbC(pbL_EnumDescriptorProto(L, pbL_add(info->enum_type)));
            break;
        case pb_pair(8, PB_TBYTES): /* OneofDescriptorProto oneof_decl */
            pbC(pbL_OneofDescriptorProto(L, info));
            break;
        case pb_pair(7, PB_TBYTES): /* MessageOptions options */
            pbC(pbL_MessageOptions(L, info));
            break;
        default:
            if (pb_skipvalue(&L->s, tag) == 0) return PB_ERROR;
        }
    }
    return pbL_endmsg(L, &s), PB_OK;
}

static int pbL_FileDescriptorProto(pb_Loader *L, pbL_FileInfo *info) {
    pb_Slice s;
    uint32_t tag;
    pbCM(info);
    pbC(pbL_beginmsg(L, &s));
    while (pb_readvarint32(&L->s, &tag)) {
        switch (tag) {
        case pb_pair(2, PB_TBYTES): /* string package */
            pbC(pbL_readbytes(L, &info->package));
            break;
        case pb_pair(4, PB_TBYTES): /* DescriptorProto message_type */
            pbC(pbL_DescriptorProto(L, pbL_add(info->message_type), 1));
            break;
        case pb_pair(5, PB_TBYTES): /* EnumDescriptorProto enum_type */
            pbC(pbL_EnumDescriptorProto(L, pbL_add(info->enum_type)));
            break;
        case pb_pair(7, PB_TBYTES): /* FieldDescriptorProto extension */
            pbC(pbL_FieldDescriptorProto(L, pbL_add(info->extension)));
            break;
        case pb_pair(12, PB_TBYTES): /* string syntax */
            pbC(pbL_readbytes(L, &info->syntax));
            break;
        default:
            if (pb_skipvalue(&L->s, tag) == 0) return PB_ERROR;
        }
    }
    return pbL_endmsg(L, &s), PB_OK;
}

static int pbL_FileDescriptorSet(pb_Loader *L, pbL_FileInfo **pfiles) {
    uint32_t tag;
    while (pb_readvarint32(&L->s, &tag)) {
        switch (tag) {
        case pb_pair(1, PB_TBYTES): /* FileDescriptorProto file */
            pbC(pbL_FileDescriptorProto(L, pbL_add(*pfiles)));
            break;
        default:
            if (pb_skipvalue(&L->s, tag) == 0) return PB_ERROR;
        }
    }
    return PB_OK;
}

/* loader */

static void pbL_delTypeInfo(pbL_TypeInfo *info) {
    size_t i, count;
    for (i = 0, count = pbL_count(info->nested_type); i < count; ++i)
        pbL_delTypeInfo(&info->nested_type[i]);
    for (i = 0, count = pbL_count(info->enum_type); i < count; ++i)
        pbL_delete(info->enum_type[i].value);
    pbL_delete(info->nested_type);
    pbL_delete(info->enum_type);
    pbL_delete(info->field);
    pbL_delete(info->extension);
    pbL_delete(info->oneof_decl);
}

static void pbL_delFileInfo(pbL_FileInfo *files) {
    size_t i, count, j, jcount;
    for (i = 0, count = pbL_count(files); i < count; ++i) {
        for (j = 0, jcount = pbL_count(files[i].message_type); j < jcount; ++j)
            pbL_delTypeInfo(&files[i].message_type[j]);
        for (j = 0, jcount = pbL_count(files[i].enum_type); j < jcount; ++j)
            pbL_delete(files[i].enum_type[j].value);
        pbL_delete(files[i].message_type);
        pbL_delete(files[i].enum_type);
        pbL_delete(files[i].extension);
    }
    pbL_delete(files);
}

static int pbL_prefixname(pb_Loader *L, pb_Slice s, size_t *ps, pb_Name **out) {
    char *buff;
    *ps = pb_bufflen(&L->b);
    pbCM(buff = pb_prepbuffsize(&L->b, pb_len(s) + 1));
    *buff = '.';
    pb_addsize(&L->b, 1);
    if (pb_addslice(&L->b, s) == 0) return PB_ENOMEM;
    if (out) *out = pb_newname(L->S, pb_result(&L->b), NULL);
    return PB_OK;
}

static int pbL_loadEnum(pb_Loader *L, pbL_EnumInfo *info) {
    size_t   i, count, curr;
    pb_Name *name;
    pb_Type *t;
    pbC(pbL_prefixname(L, info->name, &curr, &name));
    pbCM(t = pb_newtype(L->S, name));
    t->is_enum = 1;
    for (i = 0, count = pbL_count(info->value); i < count; ++i) {
        pbL_EnumValueInfo *ev = &info->value[i];
        pbCE(pb_newfield(L->S, t, pb_newname(L->S, ev->name, NULL),
                         ev->number));
    }
    return (pb_bufflen(&L->b) = (unsigned)curr), PB_OK;
}

static int pbL_loadField(pb_Loader *L, pbL_FieldInfo *info, pb_Type *t) {
    pb_Type  *ft = NULL;
    pb_Field *f;
    if (info->type == PB_Tmessage || info->type == PB_Tenum)
        pbCE(ft = pb_newtype(L->S, pb_newname(L->S, info->type_name, NULL)));
    if (t == NULL)
        pbCE(t = pb_newtype(L->S, pb_newname(L->S, info->extendee, NULL)));
    pbCE(f = pb_newfield(L->S, t, pb_newname(L->S, info->name, NULL),
                         info->number));
    f->default_value = pb_newname(L->S, info->default_value, NULL);
    f->type = ft;
    if ((f->oneof_idx = info->oneof_index)) ++t->oneof_field;
    f->type_id = info->type;
    f->repeated = info->label == 3; /* repeated */
    f->packed = info->packed >= 0 ? info->packed : L->is_proto3 && f->repeated;
    if (f->type_id >= 9 && f->type_id <= 12) f->packed = 0;
    f->scalar = (f->type == NULL);
    return PB_OK;
}

static int pbL_loadType(pb_Loader *L, pbL_TypeInfo *info) {
    size_t   i, count, curr;
    pb_Name *name;
    pb_Type *t;
    pbC(pbL_prefixname(L, info->name, &curr, &name));
    pbCM(t = pb_newtype(L->S, name));
    t->is_map = info->is_map, t->is_proto3 = L->is_proto3;
    for (i = 0, count = pbL_count(info->oneof_decl); i < count; ++i) {
        pb_OneofEntry *e = (pb_OneofEntry *)pb_settable(&t->oneof_index, i + 1);
        pbCM(e);
        pbCE(e->name = pb_newname(L->S, info->oneof_decl[i], NULL));
        e->index = (int)i + 1;
    }
    for (i = 0, count = pbL_count(info->field); i < count; ++i)
        pbC(pbL_loadField(L, &info->field[i], t));
    for (i = 0, count = pbL_count(info->extension); i < count; ++i)
        pbC(pbL_loadField(L, &info->extension[i], NULL));
    for (i = 0, count = pbL_count(info->enum_type); i < count; ++i)
        pbC(pbL_loadEnum(L, &info->enum_type[i]));
    for (i = 0, count = pbL_count(info->nested_type); i < count; ++i)
        pbC(pbL_loadType(L, &info->nested_type[i]));
    t->oneof_count = pbL_count(info->oneof_decl);
    return (pb_bufflen(&L->b) = (unsigned)curr), PB_OK;
}

static int pbL_loadFile(pbL_FileInfo *info, pb_Loader *L) {
    size_t   i, count, j, jcount, curr = 0;
    pb_Name *syntax;
    pbCM(syntax = pb_newname(L->S, pb_slice("proto3"), NULL));
    for (i = 0, count = pbL_count(info); i < count; ++i) {
        if (info[i].package.p)
            pbC(pbL_prefixname(L, info[i].package, &curr, NULL));
        L->is_proto3 = (pb_name(L->S, info[i].syntax, NULL) == syntax);
        for (j = 0, jcount = pbL_count(info[i].enum_type); j < jcount; ++j)
            pbC(pbL_loadEnum(L, &info[i].enum_type[j]));
        for (j = 0, jcount = pbL_count(info[i].message_type); j < jcount; ++j)
            pbC(pbL_loadType(L, &info[i].message_type[j]));
        for (j = 0, jcount = pbL_count(info[i].extension); j < jcount; ++j)
            pbC(pbL_loadField(L, &info[i].extension[j], NULL));
        pb_bufflen(&L->b) = (unsigned)curr;
    }
    return PB_OK;
}

PB_API int pb_load(pb_State *S, pb_Slice *s) {
    pbL_FileInfo *files = NULL;
    pb_Loader     L;
    int           r;
    pb_initbuffer(&L.b), L.S = S, L.s = *s, L.is_proto3 = 0;
    if ((r = pbL_FileDescriptorSet(&L, &files)) == PB_OK)
        r = pbL_loadFile(files, &L);
    pbL_delFileInfo(files), pb_resetbuffer(&L.b);
    return (s->p = L.s.p), r;
}

PB_NS_END

#endif /* PB_IMPLEMENTATION */

/* cc: flags+='-shared -DPB_IMPLEMENTATION -xc' output='pb.so' */