/*
 * Copyright (c) 2008-2015, Dave Benson and the protobuf-c authors.
 * All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met:
 *
 *     * Redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer.
 *
 *     * Redistributions in binary form must reproduce the above
 * copyright notice, this list of conditions and the following disclaimer
 * in the documentation and/or other materials provided with the
 * distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

/*! \file
 * Support library for `protoc-c` generated code.
 *
 * This file implements the public API used by the code generated
 * by `protoc-c`.
 *
 * \authors Dave Benson and the protobuf-c authors
 *
 * \copyright 2008-2014. Licensed under the terms of the [BSD-2-Clause] license.
 */

/**
 * \todo 64-BIT OPTIMIZATION: certain implementations use 32-bit math
 * even on 64-bit platforms (uint64_size, uint64_pack, parse_uint64).
 *
 * \todo Use size_t consistently.
 */

#include <stdlib.h> /* for malloc, free */
#include <string.h> /* for strcmp, strlen, memcpy, memmove, memset */

#include "protobuf-c.h"

#define TRUE 1
#define FALSE 0

#define PROTOBUF_C__ASSERT_NOT_REACHED() assert(0)

/* Workaround for Microsoft compilers. */
#ifdef _MSC_VER
#define inline __inline
#endif

/**
 * \defgroup internal Internal functions and macros
 *
 * These are not exported by the library but are useful to developers working
 * on `libprotobuf-c` itself.
 */

/**
 * \defgroup macros Utility macros for manipulating structures
 *
 * Macros and constants used to manipulate the base "classes" generated by
 * `protobuf-c`. They also define limits and check correctness.
 *
 * \ingroup internal
 * @{
 */

/** The maximum length of a 64-bit integer in varint encoding. */
#define MAX_UINT64_ENCODED_SIZE 10

#ifndef PROTOBUF_C_UNPACK_ERROR
#define PROTOBUF_C_UNPACK_ERROR(...)
#endif

const char protobuf_c_empty_string[] = "";

/**
 * Internal `ProtobufCMessage` manipulation macro.
 *
 * Base macro for manipulating a `ProtobufCMessage`. Used by STRUCT_MEMBER() and
 * STRUCT_MEMBER_PTR().
 */
#define STRUCT_MEMBER_P(struct_p, struct_offset) \
  ((void *)((uint8_t *)(struct_p) + (struct_offset)))

/**
 * Return field in a `ProtobufCMessage` based on offset.
 *
 * Take a pointer to a `ProtobufCMessage` and find the field at the offset.
 * Cast it to the passed type.
 */
#define STRUCT_MEMBER(member_type, struct_p, struct_offset) \
  (*(member_type *)STRUCT_MEMBER_P((struct_p), (struct_offset)))

/**
 * Return field in a `ProtobufCMessage` based on offset.
 *
 * Take a pointer to a `ProtobufCMessage` and find the field at the offset. Cast
 * it to a pointer to the passed type.
 */
#define STRUCT_MEMBER_PTR(member_type, struct_p, struct_offset) \
  ((member_type *)STRUCT_MEMBER_P((struct_p), (struct_offset)))

/* Assertions for magic numbers. */

#define ASSERT_IS_ENUM_DESCRIPTOR(desc) \
  assert((desc)->magic == PROTOBUF_C__ENUM_DESCRIPTOR_MAGIC)

#define ASSERT_IS_MESSAGE_DESCRIPTOR(desc) \
  assert((desc)->magic == PROTOBUF_C__MESSAGE_DESCRIPTOR_MAGIC)

#define ASSERT_IS_MESSAGE(message) \
  ASSERT_IS_MESSAGE_DESCRIPTOR((message)->descriptor)

#define ASSERT_IS_SERVICE_DESCRIPTOR(desc) \
  assert((desc)->magic == PROTOBUF_C__SERVICE_DESCRIPTOR_MAGIC)

/**@}*/

/* --- version --- */

const char *protobuf_c_version(void) { return PROTOBUF_C_VERSION; }

uint32_t protobuf_c_version_number(void) { return PROTOBUF_C_VERSION_NUMBER; }

/* --- allocator --- */

static void *system_alloc(void *allocator_data, size_t size) {
  return malloc(size);
}

static void system_free(void *allocator_data, void *data) { free(data); }

static inline void *do_alloc(ProtobufCAllocator *allocator, size_t size) {
  return allocator->alloc(allocator->allocator_data, size);
}

static inline void do_free(ProtobufCAllocator *allocator, void *data) {
  if (data != NULL) allocator->free(allocator->allocator_data, data);
}

/*
 * This allocator uses the system's malloc() and free(). It is the default
 * allocator used if NULL is passed as the ProtobufCAllocator to an exported
 * function.
 */
static ProtobufCAllocator protobuf_c__allocator = {
    .alloc = &system_alloc,
    .free = &system_free,
    .allocator_data = NULL,
};

/* === buffer-simple === */

void protobuf_c_buffer_simple_append(ProtobufCBuffer *buffer, size_t len,
                                     const uint8_t *data) {
  ProtobufCBufferSimple *simp = (ProtobufCBufferSimple *)buffer;
  size_t new_len = simp->len + len;

  if (new_len > simp->alloced) {
    ProtobufCAllocator *allocator = simp->allocator;
    size_t new_alloced = simp->alloced * 2;
    uint8_t *new_data;

    if (allocator == NULL) allocator = &protobuf_c__allocator;
    while (new_alloced < new_len) new_alloced += new_alloced;
    new_data = do_alloc(allocator, new_alloced);
    if (!new_data) return;
    memcpy(new_data, simp->data, simp->len);
    if (simp->must_free_data)
      do_free(allocator, simp->data);
    else
      simp->must_free_data = TRUE;
    simp->data = new_data;
    simp->alloced = new_alloced;
  }
  memcpy(simp->data + simp->len, data, len);
  simp->len = new_len;
}

/**
 * \defgroup packedsz protobuf_c_message_get_packed_size() implementation
 *
 * Routines mainly used by protobuf_c_message_get_packed_size().
 *
 * \ingroup internal
 * @{
 */

/**
 * Return the number of bytes required to store the tag for the field. Includes
 * 3 bits for the wire-type, and a single bit that denotes the end-of-tag.
 *
 * \param number
 *      Field tag to encode.
 * \return
 *      Number of bytes required.
 */
static inline size_t get_tag_size(uint32_t number) {
  if (number < (1UL << 4)) {
    return 1;
  } else if (number < (1UL << 11)) {
    return 2;
  } else if (number < (1UL << 18)) {
    return 3;
  } else if (number < (1UL << 25)) {
    return 4;
  } else {
    return 5;
  }
}

/**
 * Return the number of bytes required to store a variable-length unsigned
 * 32-bit integer in base-128 varint encoding.
 *
 * \param v
 *      Value to encode.
 * \return
 *      Number of bytes required.
 */
static inline size_t uint32_size(uint32_t v) {
  if (v < (1UL << 7)) {
    return 1;
  } else if (v < (1UL << 14)) {
    return 2;
  } else if (v < (1UL << 21)) {
    return 3;
  } else if (v < (1UL << 28)) {
    return 4;
  } else {
    return 5;
  }
}

/**
 * Return the number of bytes required to store a variable-length signed 32-bit
 * integer in base-128 varint encoding.
 *
 * \param v
 *      Value to encode.
 * \return
 *      Number of bytes required.
 */
static inline size_t int32_size(int32_t v) {
  if (v < 0) {
    return 10;
  } else if (v < (1L << 7)) {
    return 1;
  } else if (v < (1L << 14)) {
    return 2;
  } else if (v < (1L << 21)) {
    return 3;
  } else if (v < (1L << 28)) {
    return 4;
  } else {
    return 5;
  }
}

/**
 * Return the ZigZag-encoded 32-bit unsigned integer form of a 32-bit signed
 * integer.
 *
 * \param v
 *      Value to encode.
 * \return
 *      ZigZag encoded integer.
 */
static inline uint32_t zigzag32(int32_t v) {
  if (v < 0)
    return (-(uint32_t)v) * 2 - 1;
  else
    return (uint32_t)(v)*2;
}

/**
 * Return the number of bytes required to store a signed 32-bit integer,
 * converted to an unsigned 32-bit integer with ZigZag encoding, using base-128
 * varint encoding.
 *
 * \param v
 *      Value to encode.
 * \return
 *      Number of bytes required.
 */
static inline size_t sint32_size(int32_t v) { return uint32_size(zigzag32(v)); }

/**
 * Return the number of bytes required to store a 64-bit unsigned integer in
 * base-128 varint encoding.
 *
 * \param v
 *      Value to encode.
 * \return
 *      Number of bytes required.
 */
static inline size_t uint64_size(uint64_t v) {
  uint32_t upper_v = (uint32_t)(v >> 32);

  if (upper_v == 0) {
    return uint32_size((uint32_t)v);
  } else if (upper_v < (1UL << 3)) {
    return 5;
  } else if (upper_v < (1UL << 10)) {
    return 6;
  } else if (upper_v < (1UL << 17)) {
    return 7;
  } else if (upper_v < (1UL << 24)) {
    return 8;
  } else if (upper_v < (1UL << 31)) {
    return 9;
  } else {
    return 10;
  }
}

/**
 * Return the ZigZag-encoded 64-bit unsigned integer form of a 64-bit signed
 * integer.
 *
 * \param v
 *      Value to encode.
 * \return
 *      ZigZag encoded integer.
 */
static inline uint64_t zigzag64(int64_t v) {
  if (v < 0)
    return (-(uint64_t)v) * 2 - 1;
  else
    return (uint64_t)(v)*2;
}

/**
 * Return the number of bytes required to store a signed 64-bit integer,
 * converted to an unsigned 64-bit integer with ZigZag encoding, using base-128
 * varint encoding.
 *
 * \param v
 *      Value to encode.
 * \return
 *      Number of bytes required.
 */
static inline size_t sint64_size(int64_t v) { return uint64_size(zigzag64(v)); }

/**
 * Calculate the serialized size of a single required message field, including
 * the space needed by the preceding tag.
 *
 * \param field
 *      Field descriptor for member.
 * \param member
 *      Field to encode.
 * \return
 *      Number of bytes required.
 */
static size_t required_field_get_packed_size(
    const ProtobufCFieldDescriptor *field, const void *member) {
  size_t rv = get_tag_size(field->id);

  switch (field->type) {
    case PROTOBUF_C_TYPE_SINT32:
      return rv + sint32_size(*(const int32_t *)member);
    case PROTOBUF_C_TYPE_ENUM:
    case PROTOBUF_C_TYPE_INT32:
      return rv + int32_size(*(const int32_t *)member);
    case PROTOBUF_C_TYPE_UINT32:
      return rv + uint32_size(*(const uint32_t *)member);
    case PROTOBUF_C_TYPE_SINT64:
      return rv + sint64_size(*(const int64_t *)member);
    case PROTOBUF_C_TYPE_INT64:
    case PROTOBUF_C_TYPE_UINT64:
      return rv + uint64_size(*(const uint64_t *)member);
    case PROTOBUF_C_TYPE_SFIXED32:
    case PROTOBUF_C_TYPE_FIXED32:
      return rv + 4;
    case PROTOBUF_C_TYPE_SFIXED64:
    case PROTOBUF_C_TYPE_FIXED64:
      return rv + 8;
    case PROTOBUF_C_TYPE_BOOL:
      return rv + 1;
    case PROTOBUF_C_TYPE_FLOAT:
      return rv + 4;
    case PROTOBUF_C_TYPE_DOUBLE:
      return rv + 8;
    case PROTOBUF_C_TYPE_STRING: {
      const char *str = *(char *const *)member;
      size_t len = str ? strlen(str) : 0;
      return rv + uint32_size(len) + len;
    }
    case PROTOBUF_C_TYPE_BYTES: {
      size_t len = ((const ProtobufCBinaryData *)member)->len;
      return rv + uint32_size(len) + len;
    }
    case PROTOBUF_C_TYPE_MESSAGE: {
      const ProtobufCMessage *msg = *(ProtobufCMessage *const *)member;
      size_t subrv = msg ? protobuf_c_message_get_packed_size(msg) : 0;
      return rv + uint32_size(subrv) + subrv;
    }
  }
  PROTOBUF_C__ASSERT_NOT_REACHED();
  return 0;
}

/**
 * Calculate the serialized size of a single oneof message field, including
 * the space needed by the preceding tag. Returns 0 if the oneof field isn't
 * selected or is not set.
 *
 * \param field
 *      Field descriptor for member.
 * \param oneof_case
 *      Enum value that selects the field in the oneof.
 * \param member
 *      Field to encode.
 * \return
 *      Number of bytes required.
 */
static size_t oneof_field_get_packed_size(const ProtobufCFieldDescriptor *field,
                                          uint32_t oneof_case,
                                          const void *member) {
  if (oneof_case != field->id) {
    return 0;
  }
  if (field->type == PROTOBUF_C_TYPE_MESSAGE ||
      field->type == PROTOBUF_C_TYPE_STRING) {
    const void *ptr = *(const void *const *)member;
    if (ptr == NULL || ptr == field->default_value) return 0;
  }
  return required_field_get_packed_size(field, member);
}

/**
 * Calculate the serialized size of a single optional message field, including
 * the space needed by the preceding tag. Returns 0 if the optional field isn't
 * set.
 *
 * \param field
 *      Field descriptor for member.
 * \param has
 *      True if the field exists, false if not.
 * \param member
 *      Field to encode.
 * \return
 *      Number of bytes required.
 */
static size_t optional_field_get_packed_size(
    const ProtobufCFieldDescriptor *field, const protobuf_c_boolean has,
    const void *member) {
  if (field->type == PROTOBUF_C_TYPE_MESSAGE ||
      field->type == PROTOBUF_C_TYPE_STRING) {
    const void *ptr = *(const void *const *)member;
    if (ptr == NULL || ptr == field->default_value) return 0;
  } else {
    if (!has) return 0;
  }
  return required_field_get_packed_size(field, member);
}

static protobuf_c_boolean field_is_zeroish(
    const ProtobufCFieldDescriptor *field, const void *member) {
  protobuf_c_boolean ret = FALSE;

  switch (field->type) {
    case PROTOBUF_C_TYPE_BOOL:
      ret = (0 == *(const protobuf_c_boolean *)member);
      break;
    case PROTOBUF_C_TYPE_ENUM:
    case PROTOBUF_C_TYPE_SINT32:
    case PROTOBUF_C_TYPE_INT32:
    case PROTOBUF_C_TYPE_UINT32:
    case PROTOBUF_C_TYPE_SFIXED32:
    case PROTOBUF_C_TYPE_FIXED32:
      ret = (0 == *(const uint32_t *)member);
      break;
    case PROTOBUF_C_TYPE_SINT64:
    case PROTOBUF_C_TYPE_INT64:
    case PROTOBUF_C_TYPE_UINT64:
    case PROTOBUF_C_TYPE_SFIXED64:
    case PROTOBUF_C_TYPE_FIXED64:
      ret = (0 == *(const uint64_t *)member);
      break;
    case PROTOBUF_C_TYPE_FLOAT:
      ret = (0 == *(const float *)member);
      break;
    case PROTOBUF_C_TYPE_DOUBLE:
      ret = (0 == *(const double *)member);
      break;
    case PROTOBUF_C_TYPE_STRING:
      ret = (NULL == *(const char *const *)member) ||
            ('\0' == **(const char *const *)member);
      break;
    case PROTOBUF_C_TYPE_BYTES:
    case PROTOBUF_C_TYPE_MESSAGE:
      ret = (NULL == *(const void *const *)member);
      break;
    default:
      ret = TRUE;
      break;
  }

  return ret;
}

/**
 * Calculate the serialized size of a single unlabeled message field, including
 * the space needed by the preceding tag. Returns 0 if the field isn't set or
 * if it is set to a "zeroish" value (null pointer or 0 for numerical values).
 * Unlabeled fields are supported only in proto3.
 *
 * \param field
 *      Field descriptor for member.
 * \param member
 *      Field to encode.
 * \return
 *      Number of bytes required.
 */
static size_t unlabeled_field_get_packed_size(
    const ProtobufCFieldDescriptor *field, const void *member) {
  if (field_is_zeroish(field, member)) return 0;
  return required_field_get_packed_size(field, member);
}

/**
 * Calculate the serialized size of repeated message fields, which may consist
 * of any number of values (including 0). Includes the space needed by the
 * preceding tags (as needed).
 *
 * \param field
 *      Field descriptor for member.
 * \param count
 *      Number of repeated field members.
 * \param member
 *      Field to encode.
 * \return
 *      Number of bytes required.
 */
static size_t repeated_field_get_packed_size(
    const ProtobufCFieldDescriptor *field, size_t count, const void *member) {
  size_t header_size;
  size_t rv = 0;
  unsigned i;
  void *array = *(void *const *)member;

  if (count == 0) return 0;
  header_size = get_tag_size(field->id);
  if (0 == (field->flags & PROTOBUF_C_FIELD_FLAG_PACKED)) header_size *= count;

  switch (field->type) {
    case PROTOBUF_C_TYPE_SINT32:
      for (i = 0; i < count; i++) rv += sint32_size(((int32_t *)array)[i]);
      break;
    case PROTOBUF_C_TYPE_ENUM:
    case PROTOBUF_C_TYPE_INT32:
      for (i = 0; i < count; i++) rv += int32_size(((int32_t *)array)[i]);
      break;
    case PROTOBUF_C_TYPE_UINT32:
      for (i = 0; i < count; i++) rv += uint32_size(((uint32_t *)array)[i]);
      break;
    case PROTOBUF_C_TYPE_SINT64:
      for (i = 0; i < count; i++) rv += sint64_size(((int64_t *)array)[i]);
      break;
    case PROTOBUF_C_TYPE_INT64:
    case PROTOBUF_C_TYPE_UINT64:
      for (i = 0; i < count; i++) rv += uint64_size(((uint64_t *)array)[i]);
      break;
    case PROTOBUF_C_TYPE_SFIXED32:
    case PROTOBUF_C_TYPE_FIXED32:
    case PROTOBUF_C_TYPE_FLOAT:
      rv += 4 * count;
      break;
    case PROTOBUF_C_TYPE_SFIXED64:
    case PROTOBUF_C_TYPE_FIXED64:
    case PROTOBUF_C_TYPE_DOUBLE:
      rv += 8 * count;
      break;
    case PROTOBUF_C_TYPE_BOOL:
      rv += count;
      break;
    case PROTOBUF_C_TYPE_STRING:
      for (i = 0; i < count; i++) {
        size_t len = strlen(((char **)array)[i]);
        rv += uint32_size(len) + len;
      }
      break;
    case PROTOBUF_C_TYPE_BYTES:
      for (i = 0; i < count; i++) {
        size_t len = ((ProtobufCBinaryData *)array)[i].len;
        rv += uint32_size(len) + len;
      }
      break;
    case PROTOBUF_C_TYPE_MESSAGE:
      for (i = 0; i < count; i++) {
        size_t len =
            protobuf_c_message_get_packed_size(((ProtobufCMessage **)array)[i]);
        rv += uint32_size(len) + len;
      }
      break;
  }

  if (0 != (field->flags & PROTOBUF_C_FIELD_FLAG_PACKED))
    header_size += uint32_size(rv);
  return header_size + rv;
}

/**
 * Calculate the serialized size of an unknown field, i.e. one that is passed
 * through mostly uninterpreted. This is required for forward compatibility if
 * new fields are added to the message descriptor.
 *
 * \param field
 *      Unknown field type.
 * \return
 *      Number of bytes required.
 */
static inline size_t unknown_field_get_packed_size(
    const ProtobufCMessageUnknownField *field) {
  return get_tag_size(field->tag) + field->len;
}

/**@}*/

/*
 * Calculate the serialized size of the message.
 */
size_t protobuf_c_message_get_packed_size(const ProtobufCMessage *message) {
  unsigned i;
  size_t rv = 0;

  ASSERT_IS_MESSAGE(message);
  for (i = 0; i < message->descriptor->n_fields; i++) {
    const ProtobufCFieldDescriptor *field = message->descriptor->fields + i;
    const void *member = ((const char *)message) + field->offset;
    const void *qmember = ((const char *)message) + field->quantifier_offset;

    if (field->label == PROTOBUF_C_LABEL_REQUIRED) {
      rv += required_field_get_packed_size(field, member);
    } else if ((field->label == PROTOBUF_C_LABEL_OPTIONAL ||
                field->label == PROTOBUF_C_LABEL_NONE) &&
               (0 != (field->flags & PROTOBUF_C_FIELD_FLAG_ONEOF))) {
      rv += oneof_field_get_packed_size(field, *(const uint32_t *)qmember,
                                        member);
    } else if (field->label == PROTOBUF_C_LABEL_OPTIONAL) {
      rv += optional_field_get_packed_size(
          field, *(protobuf_c_boolean *)qmember, member);
    } else if (field->label == PROTOBUF_C_LABEL_NONE) {
      rv += unlabeled_field_get_packed_size(field, member);
    } else {
      rv += repeated_field_get_packed_size(field, *(const size_t *)qmember,
                                           member);
    }
  }
  for (i = 0; i < message->n_unknown_fields; i++)
    rv += unknown_field_get_packed_size(&message->unknown_fields[i]);
  return rv;
}

/**
 * \defgroup pack protobuf_c_message_pack() implementation
 *
 * Routines mainly used by protobuf_c_message_pack().
 *
 * \ingroup internal
 * @{
 */

/**
 * Pack an unsigned 32-bit integer in base-128 varint encoding and return the
 * number of bytes written, which must be 5 or less.
 *
 * \param value
 *      Value to encode.
 * \param[out] out
 *      Packed value.
 * \return
 *      Number of bytes written to `out`.
 */
static inline size_t uint32_pack(uint32_t value, uint8_t *out) {
  unsigned rv = 0;

  if (value >= 0x80) {
    out[rv++] = value | 0x80;
    value >>= 7;
    if (value >= 0x80) {
      out[rv++] = value | 0x80;
      value >>= 7;
      if (value >= 0x80) {
        out[rv++] = value | 0x80;
        value >>= 7;
        if (value >= 0x80) {
          out[rv++] = value | 0x80;
          value >>= 7;
        }
      }
    }
  }
  /* assert: value<128 */
  out[rv++] = value;
  return rv;
}

/**
 * Pack a signed 32-bit integer and return the number of bytes written.
 * Negative numbers are encoded as two's complement 64-bit integers.
 *
 * \param value
 *      Value to encode.
 * \param[out] out
 *      Packed value.
 * \return
 *      Number of bytes written to `out`.
 */
static inline size_t int32_pack(int32_t value, uint8_t *out) {
  if (value < 0) {
    out[0] = value | 0x80;
    out[1] = (value >> 7) | 0x80;
    out[2] = (value >> 14) | 0x80;
    out[3] = (value >> 21) | 0x80;
    out[4] = (value >> 28) | 0x80;
    out[5] = out[6] = out[7] = out[8] = 0xff;
    out[9] = 0x01;
    return 10;
  } else {
    return uint32_pack(value, out);
  }
}

/**
 * Pack a signed 32-bit integer using ZigZag encoding and return the number of
 * bytes written.
 *
 * \param value
 *      Value to encode.
 * \param[out] out
 *      Packed value.
 * \return
 *      Number of bytes written to `out`.
 */
static inline size_t sint32_pack(int32_t value, uint8_t *out) {
  return uint32_pack(zigzag32(value), out);
}

/**
 * Pack a 64-bit unsigned integer using base-128 varint encoding and return the
 * number of bytes written.
 *
 * \param value
 *      Value to encode.
 * \param[out] out
 *      Packed value.
 * \return
 *      Number of bytes written to `out`.
 */
static size_t uint64_pack(uint64_t value, uint8_t *out) {
  uint32_t hi = (uint32_t)(value >> 32);
  uint32_t lo = (uint32_t)value;
  unsigned rv;

  if (hi == 0) return uint32_pack((uint32_t)lo, out);
  out[0] = (lo) | 0x80;
  out[1] = (lo >> 7) | 0x80;
  out[2] = (lo >> 14) | 0x80;
  out[3] = (lo >> 21) | 0x80;
  if (hi < 8) {
    out[4] = (hi << 4) | (lo >> 28);
    return 5;
  } else {
    out[4] = ((hi & 7) << 4) | (lo >> 28) | 0x80;
    hi >>= 3;
  }
  rv = 5;
  while (hi >= 128) {
    out[rv++] = hi | 0x80;
    hi >>= 7;
  }
  out[rv++] = hi;
  return rv;
}

/**
 * Pack a 64-bit signed integer in ZigZag encoding and return the number of
 * bytes written.
 *
 * \param value
 *      Value to encode.
 * \param[out] out
 *      Packed value.
 * \return
 *      Number of bytes written to `out`.
 */
static inline size_t sint64_pack(int64_t value, uint8_t *out) {
  return uint64_pack(zigzag64(value), out);
}

/**
 * Pack a 32-bit quantity in little-endian byte order. Used for protobuf wire
 * types fixed32, sfixed32, float. Similar to "htole32".
 *
 * \param value
 *      Value to encode.
 * \param[out] out
 *      Packed value.
 * \return
 *      Number of bytes written to `out`.
 */
static inline size_t fixed32_pack(uint32_t value, void *out) {
#if !defined(WORDS_BIGENDIAN)
  memcpy(out, &value, 4);
#else
  uint8_t *buf = out;

  buf[0] = value;
  buf[1] = value >> 8;
  buf[2] = value >> 16;
  buf[3] = value >> 24;
#endif
  return 4;
}

/**
 * Pack a 64-bit quantity in little-endian byte order. Used for protobuf wire
 * types fixed64, sfixed64, double. Similar to "htole64".
 *
 * \todo The big-endian impl is really only good for 32-bit machines, a 64-bit
 * version would be appreciated, plus a way to decide to use 64-bit math where
 * convenient.
 *
 * \param value
 *      Value to encode.
 * \param[out] out
 *      Packed value.
 * \return
 *      Number of bytes written to `out`.
 */
static inline size_t fixed64_pack(uint64_t value, void *out) {
#if !defined(WORDS_BIGENDIAN)
  memcpy(out, &value, 8);
#else
  fixed32_pack(value, out);
  fixed32_pack(value >> 32, ((char *)out) + 4);
#endif
  return 8;
}

/**
 * Pack a boolean value as an integer and return the number of bytes written.
 *
 * \todo Perhaps on some platforms *out = !!value would be a better impl, b/c
 * that is idiomatic C++ in some STL implementations.
 *
 * \param value
 *      Value to encode.
 * \param[out] out
 *      Packed value.
 * \return
 *      Number of bytes written to `out`.
 */
static inline size_t boolean_pack(protobuf_c_boolean value, uint8_t *out) {
  *out = value ? TRUE : FALSE;
  return 1;
}

/**
 * Pack a NUL-terminated C string and return the number of bytes written. The
 * output includes a length delimiter.
 *
 * The NULL pointer is treated as an empty string. This isn't really necessary,
 * but it allows people to leave required strings blank. (See Issue #13 in the
 * bug tracker for a little more explanation).
 *
 * \param str
 *      String to encode.
 * \param[out] out
 *      Packed value.
 * \return
 *      Number of bytes written to `out`.
 */
static inline size_t string_pack(const char *str, uint8_t *out) {
  if (str == NULL) {
    out[0] = 0;
    return 1;
  } else {
    size_t len = strlen(str);
    size_t rv = uint32_pack(len, out);
    memcpy(out + rv, str, len);
    return rv + len;
  }
}

/**
 * Pack a ProtobufCBinaryData and return the number of bytes written. The output
 * includes a length delimiter.
 *
 * \param bd
 *      ProtobufCBinaryData to encode.
 * \param[out] out
 *      Packed value.
 * \return
 *      Number of bytes written to `out`.
 */
static inline size_t binary_data_pack(const ProtobufCBinaryData *bd,
                                      uint8_t *out) {
  size_t len = bd->len;
  size_t rv = uint32_pack(len, out);
  memcpy(out + rv, bd->data, len);
  return rv + len;
}

/**
 * Pack a ProtobufCMessage and return the number of bytes written. The output
 * includes a length delimiter.
 *
 * \param message
 *      ProtobufCMessage object to pack.
 * \param[out] out
 *      Packed message.
 * \return
 *      Number of bytes written to `out`.
 */
static inline size_t prefixed_message_pack(const ProtobufCMessage *message,
                                           uint8_t *out) {
  if (message == NULL) {
    out[0] = 0;
    return 1;
  } else {
    size_t rv = protobuf_c_message_pack(message, out + 1);
    uint32_t rv_packed_size = uint32_size(rv);
    if (rv_packed_size != 1) memmove(out + rv_packed_size, out + 1, rv);
    return uint32_pack(rv, out) + rv;
  }
}

/**
 * Pack a field tag.
 *
 * Wire-type will be added in required_field_pack().
 *
 * \todo Just call uint64_pack on 64-bit platforms.
 *
 * \param id
 *      Tag value to encode.
 * \param[out] out
 *      Packed value.
 * \return
 *      Number of bytes written to `out`.
 */
static size_t tag_pack(uint32_t id, uint8_t *out) {
  if (id < (1UL << (32 - 3)))
    return uint32_pack(id << 3, out);
  else
    return uint64_pack(((uint64_t)id) << 3, out);
}

/**
 * Pack a required field and return the number of bytes written.
 *
 * \param field
 *      Field descriptor.
 * \param member
 *      The field member.
 * \param[out] out
 *      Packed value.
 * \return
 *      Number of bytes written to `out`.
 */
static size_t required_field_pack(const ProtobufCFieldDescriptor *field,
                                  const void *member, uint8_t *out) {
  size_t rv = tag_pack(field->id, out);

  switch (field->type) {
    case PROTOBUF_C_TYPE_SINT32:
      out[0] |= PROTOBUF_C_WIRE_TYPE_VARINT;
      return rv + sint32_pack(*(const int32_t *)member, out + rv);
    case PROTOBUF_C_TYPE_ENUM:
    case PROTOBUF_C_TYPE_INT32:
      out[0] |= PROTOBUF_C_WIRE_TYPE_VARINT;
      return rv + int32_pack(*(const int32_t *)member, out + rv);
    case PROTOBUF_C_TYPE_UINT32:
      out[0] |= PROTOBUF_C_WIRE_TYPE_VARINT;
      return rv + uint32_pack(*(const uint32_t *)member, out + rv);
    case PROTOBUF_C_TYPE_SINT64:
      out[0] |= PROTOBUF_C_WIRE_TYPE_VARINT;
      return rv + sint64_pack(*(const int64_t *)member, out + rv);
    case PROTOBUF_C_TYPE_INT64:
    case PROTOBUF_C_TYPE_UINT64:
      out[0] |= PROTOBUF_C_WIRE_TYPE_VARINT;
      return rv + uint64_pack(*(const uint64_t *)member, out + rv);
    case PROTOBUF_C_TYPE_SFIXED32:
    case PROTOBUF_C_TYPE_FIXED32:
    case PROTOBUF_C_TYPE_FLOAT:
      out[0] |= PROTOBUF_C_WIRE_TYPE_32BIT;
      return rv + fixed32_pack(*(const uint32_t *)member, out + rv);
    case PROTOBUF_C_TYPE_SFIXED64:
    case PROTOBUF_C_TYPE_FIXED64:
    case PROTOBUF_C_TYPE_DOUBLE:
      out[0] |= PROTOBUF_C_WIRE_TYPE_64BIT;
      return rv + fixed64_pack(*(const uint64_t *)member, out + rv);
    case PROTOBUF_C_TYPE_BOOL:
      out[0] |= PROTOBUF_C_WIRE_TYPE_VARINT;
      return rv + boolean_pack(*(const protobuf_c_boolean *)member, out + rv);
    case PROTOBUF_C_TYPE_STRING:
      out[0] |= PROTOBUF_C_WIRE_TYPE_LENGTH_PREFIXED;
      return rv + string_pack(*(char *const *)member, out + rv);
    case PROTOBUF_C_TYPE_BYTES:
      out[0] |= PROTOBUF_C_WIRE_TYPE_LENGTH_PREFIXED;
      return rv +
             binary_data_pack((const ProtobufCBinaryData *)member, out + rv);
    case PROTOBUF_C_TYPE_MESSAGE:
      out[0] |= PROTOBUF_C_WIRE_TYPE_LENGTH_PREFIXED;
      return rv + prefixed_message_pack(*(ProtobufCMessage *const *)member,
                                        out + rv);
  }
  PROTOBUF_C__ASSERT_NOT_REACHED();
  return 0;
}

/**
 * Pack a oneof field and return the number of bytes written. Only packs the
 * field that is selected by the case enum.
 *
 * \param field
 *      Field descriptor.
 * \param oneof_case
 *      Enum value that selects the field in the oneof.
 * \param member
 *      The field member.
 * \param[out] out
 *      Packed value.
 * \return
 *      Number of bytes written to `out`.
 */
static size_t oneof_field_pack(const ProtobufCFieldDescriptor *field,
                               uint32_t oneof_case, const void *member,
                               uint8_t *out) {
  if (oneof_case != field->id) {
    return 0;
  }
  if (field->type == PROTOBUF_C_TYPE_MESSAGE ||
      field->type == PROTOBUF_C_TYPE_STRING) {
    const void *ptr = *(const void *const *)member;
    if (ptr == NULL || ptr == field->default_value) return 0;
  }
  return required_field_pack(field, member, out);
}

/**
 * Pack an optional field and return the number of bytes written.
 *
 * \param field
 *      Field descriptor.
 * \param has
 *      Whether the field is set.
 * \param member
 *      The field member.
 * \param[out] out
 *      Packed value.
 * \return
 *      Number of bytes written to `out`.
 */
static size_t optional_field_pack(const ProtobufCFieldDescriptor *field,
                                  const protobuf_c_boolean has,
                                  const void *member, uint8_t *out) {
  if (field->type == PROTOBUF_C_TYPE_MESSAGE ||
      field->type == PROTOBUF_C_TYPE_STRING) {
    const void *ptr = *(const void *const *)member;
    if (ptr == NULL || ptr == field->default_value) return 0;
  } else {
    if (!has) return 0;
  }
  return required_field_pack(field, member, out);
}

/**
 * Pack an unlabeled field and return the number of bytes written.
 *
 * \param field
 *      Field descriptor.
 * \param member
 *      The field member.
 * \param[out] out
 *      Packed value.
 * \return
 *      Number of bytes written to `out`.
 */
static size_t unlabeled_field_pack(const ProtobufCFieldDescriptor *field,
                                   const void *member, uint8_t *out) {
  if (field_is_zeroish(field, member)) return 0;
  return required_field_pack(field, member, out);
}

/**
 * Given a field type, return the in-memory size.
 *
 * \todo Implement as a table lookup.
 *
 * \param type
 *      Field type.
 * \return
 *      Size of the field.
 */
static inline size_t sizeof_elt_in_repeated_array(ProtobufCType type) {
  switch (type) {
    case PROTOBUF_C_TYPE_SINT32:
    case PROTOBUF_C_TYPE_INT32:
    case PROTOBUF_C_TYPE_UINT32:
    case PROTOBUF_C_TYPE_SFIXED32:
    case PROTOBUF_C_TYPE_FIXED32:
    case PROTOBUF_C_TYPE_FLOAT:
    case PROTOBUF_C_TYPE_ENUM:
      return 4;
    case PROTOBUF_C_TYPE_SINT64:
    case PROTOBUF_C_TYPE_INT64:
    case PROTOBUF_C_TYPE_UINT64:
    case PROTOBUF_C_TYPE_SFIXED64:
    case PROTOBUF_C_TYPE_FIXED64:
    case PROTOBUF_C_TYPE_DOUBLE:
      return 8;
    case PROTOBUF_C_TYPE_BOOL:
      return sizeof(protobuf_c_boolean);
    case PROTOBUF_C_TYPE_STRING:
    case PROTOBUF_C_TYPE_MESSAGE:
      return sizeof(void *);
    case PROTOBUF_C_TYPE_BYTES:
      return sizeof(ProtobufCBinaryData);
  }
  PROTOBUF_C__ASSERT_NOT_REACHED();
  return 0;
}

/**
 * Pack an array of 32-bit quantities.
 *
 * \param[out] out
 *      Destination.
 * \param[in] in
 *      Source.
 * \param[in] n
 *      Number of elements in the source array.
 */
static void copy_to_little_endian_32(void *out, const void *in,
                                     const unsigned n) {
#if !defined(WORDS_BIGENDIAN)
  memcpy(out, in, n * 4);
#else
  unsigned i;
  const uint32_t *ini = in;
  for (i = 0; i < n; i++) fixed32_pack(ini[i], (uint32_t *)out + i);
#endif
}

/**
 * Pack an array of 64-bit quantities.
 *
 * \param[out] out
 *      Destination.
 * \param[in] in
 *      Source.
 * \param[in] n
 *      Number of elements in the source array.
 */
static void copy_to_little_endian_64(void *out, const void *in,
                                     const unsigned n) {
#if !defined(WORDS_BIGENDIAN)
  memcpy(out, in, n * 8);
#else
  unsigned i;
  const uint64_t *ini = in;
  for (i = 0; i < n; i++) fixed64_pack(ini[i], (uint64_t *)out + i);
#endif
}

/**
 * Get the minimum number of bytes required to pack a field value of a
 * particular type.
 *
 * \param type
 *      Field type.
 * \return
 *      Number of bytes.
 */
static unsigned get_type_min_size(ProtobufCType type) {
  if (type == PROTOBUF_C_TYPE_SFIXED32 || type == PROTOBUF_C_TYPE_FIXED32 ||
      type == PROTOBUF_C_TYPE_FLOAT) {
    return 4;
  }
  if (type == PROTOBUF_C_TYPE_SFIXED64 || type == PROTOBUF_C_TYPE_FIXED64 ||
      type == PROTOBUF_C_TYPE_DOUBLE) {
    return 8;
  }
  return 1;
}

/**
 * Get the packed size of an array of same field type.
 *
 * \param field
 *      Field descriptor.
 * \param count
 *      Number of elements of this type.
 * \param array
 *      The elements to get the size of.
 * \return
 *      Number of bytes required.
 */
static size_t get_packed_payload_length(const ProtobufCFieldDescriptor *field,
                                        unsigned count, const void *array) {
  unsigned rv = 0;
  unsigned i;

  switch (field->type) {
    case PROTOBUF_C_TYPE_SFIXED32:
    case PROTOBUF_C_TYPE_FIXED32:
    case PROTOBUF_C_TYPE_FLOAT:
      return count * 4;
    case PROTOBUF_C_TYPE_SFIXED64:
    case PROTOBUF_C_TYPE_FIXED64:
    case PROTOBUF_C_TYPE_DOUBLE:
      return count * 8;
    case PROTOBUF_C_TYPE_ENUM:
    case PROTOBUF_C_TYPE_INT32: {
      const int32_t *arr = (const int32_t *)array;
      for (i = 0; i < count; i++) rv += int32_size(arr[i]);
      break;
    }
    case PROTOBUF_C_TYPE_SINT32: {
      const int32_t *arr = (const int32_t *)array;
      for (i = 0; i < count; i++) rv += sint32_size(arr[i]);
      break;
    }
    case PROTOBUF_C_TYPE_UINT32: {
      const uint32_t *arr = (const uint32_t *)array;
      for (i = 0; i < count; i++) rv += uint32_size(arr[i]);
      break;
    }
    case PROTOBUF_C_TYPE_SINT64: {
      const int64_t *arr = (const int64_t *)array;
      for (i = 0; i < count; i++) rv += sint64_size(arr[i]);
      break;
    }
    case PROTOBUF_C_TYPE_INT64:
    case PROTOBUF_C_TYPE_UINT64: {
      const uint64_t *arr = (const uint64_t *)array;
      for (i = 0; i < count; i++) rv += uint64_size(arr[i]);
      break;
    }
    case PROTOBUF_C_TYPE_BOOL:
      return count;
    default:
      PROTOBUF_C__ASSERT_NOT_REACHED();
  }
  return rv;
}

/**
 * Pack an array of same field type to a virtual buffer.
 *
 * \param field
 *      Field descriptor.
 * \param count
 *      Number of elements of this type.
 * \param array
 *      The elements to get the size of.
 * \param[out] buffer
 *      Virtual buffer to append data to.
 * \return
 *      Number of bytes packed.
 */
static size_t pack_buffer_packed_payload(const ProtobufCFieldDescriptor *field,
                                         unsigned count, const void *array,
                                         ProtobufCBuffer *buffer) {
  uint8_t scratch[16];
  size_t rv = 0;
  unsigned i;

  switch (field->type) {
    case PROTOBUF_C_TYPE_SFIXED32:
    case PROTOBUF_C_TYPE_FIXED32:
    case PROTOBUF_C_TYPE_FLOAT:
#if !defined(WORDS_BIGENDIAN)
      rv = count * 4;
      goto no_packing_needed;
#else
      for (i = 0; i < count; i++) {
        unsigned len = fixed32_pack(((uint32_t *)array)[i], scratch);
        buffer->append(buffer, len, scratch);
        rv += len;
      }
      break;
#endif
    case PROTOBUF_C_TYPE_SFIXED64:
    case PROTOBUF_C_TYPE_FIXED64:
    case PROTOBUF_C_TYPE_DOUBLE:
#if !defined(WORDS_BIGENDIAN)
      rv = count * 8;
      goto no_packing_needed;
#else
      for (i = 0; i < count; i++) {
        unsigned len = fixed64_pack(((uint64_t *)array)[i], scratch);
        buffer->append(buffer, len, scratch);
        rv += len;
      }
      break;
#endif
    case PROTOBUF_C_TYPE_ENUM:
    case PROTOBUF_C_TYPE_INT32:
      for (i = 0; i < count; i++) {
        unsigned len = int32_pack(((int32_t *)array)[i], scratch);
        buffer->append(buffer, len, scratch);
        rv += len;
      }
      break;
    case PROTOBUF_C_TYPE_SINT32:
      for (i = 0; i < count; i++) {
        unsigned len = sint32_pack(((int32_t *)array)[i], scratch);
        buffer->append(buffer, len, scratch);
        rv += len;
      }
      break;
    case PROTOBUF_C_TYPE_UINT32:
      for (i = 0; i < count; i++) {
        unsigned len = uint32_pack(((uint32_t *)array)[i], scratch);
        buffer->append(buffer, len, scratch);
        rv += len;
      }
      break;
    case PROTOBUF_C_TYPE_SINT64:
      for (i = 0; i < count; i++) {
        unsigned len = sint64_pack(((int64_t *)array)[i], scratch);
        buffer->append(buffer, len, scratch);
        rv += len;
      }
      break;
    case PROTOBUF_C_TYPE_INT64:
    case PROTOBUF_C_TYPE_UINT64:
      for (i = 0; i < count; i++) {
        unsigned len = uint64_pack(((uint64_t *)array)[i], scratch);
        buffer->append(buffer, len, scratch);
        rv += len;
      }
      break;
    case PROTOBUF_C_TYPE_BOOL:
      for (i = 0; i < count; i++) {
        unsigned len = boolean_pack(((protobuf_c_boolean *)array)[i], scratch);
        buffer->append(buffer, len, scratch);
        rv += len;
      }
      return count;
    default:
      PROTOBUF_C__ASSERT_NOT_REACHED();
  }
  return rv;

#if !defined(WORDS_BIGENDIAN)
no_packing_needed:
  buffer->append(buffer, rv, array);
  return rv;
#endif
}

static inline int int_range_lookup(unsigned n_ranges,
                                   const ProtobufCIntRange *ranges, int value) {
  unsigned n;
  unsigned start;

  if (n_ranges == 0) return -1;
  start = 0;
  n = n_ranges;
  while (n > 1) {
    unsigned mid = start + n / 2;

    if (value < ranges[mid].start_value) {
      n = mid - start;
    } else if (value >=
               ranges[mid].start_value +
                   (int)(ranges[mid + 1].orig_index - ranges[mid].orig_index)) {
      unsigned new_start = mid + 1;
      n = start + n - new_start;
      start = new_start;
    } else
      return (value - ranges[mid].start_value) + ranges[mid].orig_index;
  }
  if (n > 0) {
    unsigned start_orig_index = ranges[start].orig_index;
    unsigned range_size = ranges[start + 1].orig_index - start_orig_index;

    if (ranges[start].start_value <= value &&
        value < (int)(ranges[start].start_value + range_size)) {
      return (value - ranges[start].start_value) + start_orig_index;
    }
  }
  return -1;
}

static size_t parse_tag_and_wiretype(size_t len, const uint8_t *data,
                                     uint32_t *tag_out,
                                     ProtobufCWireType *wiretype_out) {
  unsigned max_rv = len > 5 ? 5 : len;
  uint32_t tag = (data[0] & 0x7f) >> 3;
  unsigned shift = 4;
  unsigned rv;

  *wiretype_out = data[0] & 7;
  if ((data[0] & 0x80) == 0) {
    *tag_out = tag;
    return 1;
  }
  for (rv = 1; rv < max_rv; rv++) {
    if (data[rv] & 0x80) {
      tag |= (data[rv] & 0x7f) << shift;
      shift += 7;
    } else {
      tag |= data[rv] << shift;
      *tag_out = tag;
      return rv + 1;
    }
  }
  return 0; /* error: bad header */
}

/* sizeof(ScannedMember) must be <= (1UL<<BOUND_SIZEOF_SCANNED_MEMBER_LOG2) */
#define BOUND_SIZEOF_SCANNED_MEMBER_LOG2 5
typedef struct _ScannedMember ScannedMember;
/** Field as it's being read. */
struct _ScannedMember {
  uint32_t tag;                          /**< Field tag. */
  uint8_t wire_type;                     /**< Field type. */
  uint8_t length_prefix_len;             /**< Prefix length. */
  const ProtobufCFieldDescriptor *field; /**< Field descriptor. */
  size_t len;                            /**< Field length. */
  const uint8_t *data;                   /**< Pointer to field data. */
};

static inline uint32_t scan_length_prefixed_data(size_t len,
                                                 const uint8_t *data,
                                                 size_t *prefix_len_out) {
  unsigned hdr_max = len < 5 ? len : 5;
  unsigned hdr_len;
  uint32_t val = 0;
  unsigned i;
  unsigned shift = 0;

  for (i = 0; i < hdr_max; i++) {
    val |= (data[i] & 0x7f) << shift;
    shift += 7;
    if ((data[i] & 0x80) == 0) break;
  }
  if (i == hdr_max) {
    PROTOBUF_C_UNPACK_ERROR("error parsing length for length-prefixed data");
    return 0;
  }
  hdr_len = i + 1;
  *prefix_len_out = hdr_len;
  if (hdr_len + val > len) {
    PROTOBUF_C_UNPACK_ERROR("data too short after length-prefix of %u", val);
    return 0;
  }
  return hdr_len + val;
}

static size_t max_b128_numbers(size_t len, const uint8_t *data) {
  size_t rv = 0;
  while (len--)
    if ((*data++ & 0x80) == 0) ++rv;
  return rv;
}

/**@}*/

/**
 * Merge earlier message into a latter message.
 *
 * For numeric types and strings, if the same value appears multiple
 * times, the parser accepts the last value it sees. For embedded
 * message fields, the parser merges multiple instances of the same
 * field. That is, all singular scalar fields in the latter instance
 * replace those in the former, singular embedded messages are merged,
 * and repeated fields are concatenated.
 *
 * The earlier message should be freed after calling this function, as
 * some of its fields may have been reused and changed to their default
 * values during the merge.
 */
static protobuf_c_boolean merge_messages(ProtobufCMessage *earlier_msg,
                                         ProtobufCMessage *latter_msg,
                                         ProtobufCAllocator *allocator) {
  unsigned i;
  const ProtobufCFieldDescriptor *fields = latter_msg->descriptor->fields;
  for (i = 0; i < latter_msg->descriptor->n_fields; i++) {
    if (fields[i].label == PROTOBUF_C_LABEL_REPEATED) {
      size_t *n_earlier =
          STRUCT_MEMBER_PTR(size_t, earlier_msg, fields[i].quantifier_offset);
      uint8_t **p_earlier =
          STRUCT_MEMBER_PTR(uint8_t *, earlier_msg, fields[i].offset);
      size_t *n_latter =
          STRUCT_MEMBER_PTR(size_t, latter_msg, fields[i].quantifier_offset);
      uint8_t **p_latter =
          STRUCT_MEMBER_PTR(uint8_t *, latter_msg, fields[i].offset);

      if (*n_earlier > 0) {
        if (*n_latter > 0) {
          /* Concatenate the repeated field */
          size_t el_size = sizeof_elt_in_repeated_array(fields[i].type);
          uint8_t *new_field;

          new_field = do_alloc(allocator, (*n_earlier + *n_latter) * el_size);
          if (!new_field) return FALSE;

          memcpy(new_field, *p_earlier, *n_earlier * el_size);
          memcpy(new_field + *n_earlier * el_size, *p_latter,
                 *n_latter * el_size);

          do_free(allocator, *p_latter);
          do_free(allocator, *p_earlier);
          *p_latter = new_field;
          *n_latter = *n_earlier + *n_latter;
        } else {
          /* Zero copy the repeated field from the earlier message */
          *n_latter = *n_earlier;
          *p_latter = *p_earlier;
        }
        /* Make sure the field does not get double freed */
        *n_earlier = 0;
        *p_earlier = 0;
      }
    } else if (fields[i].label == PROTOBUF_C_LABEL_OPTIONAL ||
               fields[i].label == PROTOBUF_C_LABEL_NONE) {
      const ProtobufCFieldDescriptor *field;
      uint32_t *earlier_case_p =
          STRUCT_MEMBER_PTR(uint32_t, earlier_msg, fields[i].quantifier_offset);
      uint32_t *latter_case_p =
          STRUCT_MEMBER_PTR(uint32_t, latter_msg, fields[i].quantifier_offset);
      protobuf_c_boolean need_to_merge = FALSE;
      void *earlier_elem;
      void *latter_elem;
      const void *def_val;

      if (fields[i].flags & PROTOBUF_C_FIELD_FLAG_ONEOF) {
        if (*latter_case_p == 0) {
          /* lookup correct oneof field */
          int field_index = int_range_lookup(
              latter_msg->descriptor->n_field_ranges,
              latter_msg->descriptor->field_ranges, *earlier_case_p);
          field = latter_msg->descriptor->fields + field_index;
        } else {
          /* Oneof is present in the latter message, move on */
          continue;
        }
      } else {
        field = &fields[i];
      }

      earlier_elem = STRUCT_MEMBER_P(earlier_msg, field->offset);
      latter_elem = STRUCT_MEMBER_P(latter_msg, field->offset);
      def_val = field->default_value;

      switch (field->type) {
        case PROTOBUF_C_TYPE_MESSAGE: {
          ProtobufCMessage *em = *(ProtobufCMessage **)earlier_elem;
          ProtobufCMessage *lm = *(ProtobufCMessage **)latter_elem;
          if (em != NULL) {
            if (lm != NULL) {
              if (!merge_messages(em, lm, allocator)) return FALSE;
              /* Already merged */
              need_to_merge = FALSE;
            } else {
              /* Zero copy the message */
              need_to_merge = TRUE;
            }
          }
          break;
        }
        case PROTOBUF_C_TYPE_BYTES: {
          uint8_t *e_data = ((ProtobufCBinaryData *)earlier_elem)->data;
          uint8_t *l_data = ((ProtobufCBinaryData *)latter_elem)->data;
          const ProtobufCBinaryData *d_bd = (ProtobufCBinaryData *)def_val;

          need_to_merge =
              (e_data != NULL && (d_bd == NULL || e_data != d_bd->data)) &&
              (l_data == NULL || (d_bd != NULL && l_data == d_bd->data));
          break;
        }
        case PROTOBUF_C_TYPE_STRING: {
          char *e_str = *(char **)earlier_elem;
          char *l_str = *(char **)latter_elem;
          const char *d_str = def_val;

          need_to_merge = e_str != d_str && l_str == d_str;
          break;
        }
        default: {
          /* Could be has field or case enum, the logic is
           * equivalent, since 0 (FALSE) means not set for
           * oneof */
          need_to_merge = (*earlier_case_p != 0) && (*latter_case_p == 0);
          break;
        }
      }

      if (need_to_merge) {
        size_t el_size = sizeof_elt_in_repeated_array(field->type);
        memcpy(latter_elem, earlier_elem, el_size);
        /*
         * Reset the element from the old message to 0
         * to make sure earlier message deallocation
         * doesn't corrupt zero-copied data in the new
         * message, earlier message will be freed after
         * this function is called anyway
         */
        memset(earlier_elem, 0, el_size);

        if (field->quantifier_offset != 0) {
          /* Set the has field or the case enum,
           * if applicable */
          *latter_case_p = *earlier_case_p;
          *earlier_case_p = 0;
        }
      }
    }
  }
  return TRUE;
}

/**
 * Count packed elements.
 *
 * Given a raw slab of packed-repeated values, determine the number of
 * elements. This function detects certain kinds of errors but not
 * others; the remaining error checking is done by
 * parse_packed_repeated_member().
 */
static protobuf_c_boolean count_packed_elements(ProtobufCType type, size_t len,
                                                const uint8_t *data,
                                                size_t *count_out) {
  switch (type) {
    case PROTOBUF_C_TYPE_SFIXED32:
    case PROTOBUF_C_TYPE_FIXED32:
    case PROTOBUF_C_TYPE_FLOAT:
      if (len % 4 != 0) {
        PROTOBUF_C_UNPACK_ERROR(
            "length must be a multiple of 4 for fixed-length 32-bit types");
        return FALSE;
      }
      *count_out = len / 4;
      return TRUE;
    case PROTOBUF_C_TYPE_SFIXED64:
    case PROTOBUF_C_TYPE_FIXED64:
    case PROTOBUF_C_TYPE_DOUBLE:
      if (len % 8 != 0) {
        PROTOBUF_C_UNPACK_ERROR(
            "length must be a multiple of 8 for fixed-length 64-bit types");
        return FALSE;
      }
      *count_out = len / 8;
      return TRUE;
    case PROTOBUF_C_TYPE_ENUM:
    case PROTOBUF_C_TYPE_INT32:
    case PROTOBUF_C_TYPE_SINT32:
    case PROTOBUF_C_TYPE_UINT32:
    case PROTOBUF_C_TYPE_INT64:
    case PROTOBUF_C_TYPE_SINT64:
    case PROTOBUF_C_TYPE_UINT64:
      *count_out = max_b128_numbers(len, data);
      return TRUE;
    case PROTOBUF_C_TYPE_BOOL:
      *count_out = len;
      return TRUE;
    case PROTOBUF_C_TYPE_STRING:
    case PROTOBUF_C_TYPE_BYTES:
    case PROTOBUF_C_TYPE_MESSAGE:
    default:
      PROTOBUF_C_UNPACK_ERROR("bad protobuf-c type %u for packed-repeated",
                              type);
      return FALSE;
  }
}

static inline uint32_t parse_uint32(unsigned len, const uint8_t *data) {
  uint32_t rv = data[0] & 0x7f;
  if (len > 1) {
    rv |= ((uint32_t)(data[1] & 0x7f) << 7);
    if (len > 2) {
      rv |= ((uint32_t)(data[2] & 0x7f) << 14);
      if (len > 3) {
        rv |= ((uint32_t)(data[3] & 0x7f) << 21);
        if (len > 4) rv |= ((uint32_t)(data[4]) << 28);
      }
    }
  }
  return rv;
}

static inline uint32_t parse_int32(unsigned len, const uint8_t *data) {
  return parse_uint32(len, data);
}

static inline int32_t unzigzag32(uint32_t v) {
  if (v & 1)
    return -(v >> 1) - 1;
  else
    return v >> 1;
}

static inline uint32_t parse_fixed_uint32(const uint8_t *data) {
#if !defined(WORDS_BIGENDIAN)
  uint32_t t;
  memcpy(&t, data, 4);
  return t;
#else
  return data[0] | ((uint32_t)(data[1]) << 8) | ((uint32_t)(data[2]) << 16) |
         ((uint32_t)(data[3]) << 24);
#endif
}

static uint64_t parse_uint64(unsigned len, const uint8_t *data) {
  unsigned shift, i;
  uint64_t rv;

  if (len < 5) return parse_uint32(len, data);
  rv = ((uint64_t)(data[0] & 0x7f)) | ((uint64_t)(data[1] & 0x7f) << 7) |
       ((uint64_t)(data[2] & 0x7f) << 14) | ((uint64_t)(data[3] & 0x7f) << 21);
  shift = 28;
  for (i = 4; i < len; i++) {
    rv |= (((uint64_t)(data[i] & 0x7f)) << shift);
    shift += 7;
  }
  return rv;
}

static inline int64_t unzigzag64(uint64_t v) {
  if (v & 1)
    return -(v >> 1) - 1;
  else
    return v >> 1;
}

static inline uint64_t parse_fixed_uint64(const uint8_t *data) {
#if !defined(WORDS_BIGENDIAN)
  uint64_t t;
  memcpy(&t, data, 8);
  return t;
#else
  return (uint64_t)parse_fixed_uint32(data) |
         (((uint64_t)parse_fixed_uint32(data + 4)) << 32);
#endif
}

static protobuf_c_boolean parse_boolean(unsigned len, const uint8_t *data) {
  unsigned i;
  for (i = 0; i < len; i++)
    if (data[i] & 0x7f) return TRUE;
  return FALSE;
}

static protobuf_c_boolean parse_required_member(
    ScannedMember *scanned_member, void *member, ProtobufCAllocator *allocator,
    protobuf_c_boolean maybe_clear) {
  unsigned len = scanned_member->len;
  const uint8_t *data = scanned_member->data;
  ProtobufCWireType wire_type = scanned_member->wire_type;

  switch (scanned_member->field->type) {
    case PROTOBUF_C_TYPE_ENUM:
    case PROTOBUF_C_TYPE_INT32:
      if (wire_type != PROTOBUF_C_WIRE_TYPE_VARINT) return FALSE;
      *(int32_t *)member = parse_int32(len, data);
      return TRUE;
    case PROTOBUF_C_TYPE_UINT32:
      if (wire_type != PROTOBUF_C_WIRE_TYPE_VARINT) return FALSE;
      *(uint32_t *)member = parse_uint32(len, data);
      return TRUE;
    case PROTOBUF_C_TYPE_SINT32:
      if (wire_type != PROTOBUF_C_WIRE_TYPE_VARINT) return FALSE;
      *(int32_t *)member = unzigzag32(parse_uint32(len, data));
      return TRUE;
    case PROTOBUF_C_TYPE_SFIXED32:
    case PROTOBUF_C_TYPE_FIXED32:
    case PROTOBUF_C_TYPE_FLOAT:
      if (wire_type != PROTOBUF_C_WIRE_TYPE_32BIT) return FALSE;
      *(uint32_t *)member = parse_fixed_uint32(data);
      return TRUE;
    case PROTOBUF_C_TYPE_INT64:
    case PROTOBUF_C_TYPE_UINT64:
      if (wire_type != PROTOBUF_C_WIRE_TYPE_VARINT) return FALSE;
      *(uint64_t *)member = parse_uint64(len, data);
      return TRUE;
    case PROTOBUF_C_TYPE_SINT64:
      if (wire_type != PROTOBUF_C_WIRE_TYPE_VARINT) return FALSE;
      *(int64_t *)member = unzigzag64(parse_uint64(len, data));
      return TRUE;
    case PROTOBUF_C_TYPE_SFIXED64:
    case PROTOBUF_C_TYPE_FIXED64:
    case PROTOBUF_C_TYPE_DOUBLE:
      if (wire_type != PROTOBUF_C_WIRE_TYPE_64BIT) return FALSE;
      *(uint64_t *)member = parse_fixed_uint64(data);
      return TRUE;
    case PROTOBUF_C_TYPE_BOOL:
      *(protobuf_c_boolean *)member = parse_boolean(len, data);
      return TRUE;
    case PROTOBUF_C_TYPE_STRING: {
      char **pstr = member;
      unsigned pref_len = scanned_member->length_prefix_len;

      if (wire_type != PROTOBUF_C_WIRE_TYPE_LENGTH_PREFIXED) return FALSE;

      if (maybe_clear && *pstr != NULL) {
        const char *def = scanned_member->field->default_value;
        if (*pstr != NULL && *pstr != def) do_free(allocator, *pstr);
      }
      *pstr = do_alloc(allocator, len - pref_len + 1);
      if (*pstr == NULL) return FALSE;
      memcpy(*pstr, data + pref_len, len - pref_len);
      (*pstr)[len - pref_len] = 0;
      return TRUE;
    }
    case PROTOBUF_C_TYPE_BYTES: {
      ProtobufCBinaryData *bd = member;
      const ProtobufCBinaryData *def_bd;
      unsigned pref_len = scanned_member->length_prefix_len;

      if (wire_type != PROTOBUF_C_WIRE_TYPE_LENGTH_PREFIXED) return FALSE;

      def_bd = scanned_member->field->default_value;
      if (maybe_clear && bd->data != NULL &&
          (def_bd == NULL || bd->data != def_bd->data)) {
        do_free(allocator, bd->data);
      }
      if (len - pref_len > 0) {
        bd->data = do_alloc(allocator, len - pref_len);
        if (bd->data == NULL) return FALSE;
        memcpy(bd->data, data + pref_len, len - pref_len);
      } else {
        bd->data = NULL;
      }
      bd->len = len - pref_len;
      return TRUE;
    }
    case PROTOBUF_C_TYPE_MESSAGE: {
      ProtobufCMessage **pmessage = member;
      ProtobufCMessage *subm;
      const ProtobufCMessage *def_mess;
      protobuf_c_boolean merge_successful = TRUE;
      unsigned pref_len = scanned_member->length_prefix_len;

      if (wire_type != PROTOBUF_C_WIRE_TYPE_LENGTH_PREFIXED) return FALSE;

      def_mess = scanned_member->field->default_value;
      subm =
          protobuf_c_message_unpack(scanned_member->field->descriptor,
                                    allocator, len - pref_len, data + pref_len);

      if (maybe_clear && *pmessage != NULL && *pmessage != def_mess) {
        if (subm != NULL)
          merge_successful = merge_messages(*pmessage, subm, allocator);
        /* Delete the previous message */
        protobuf_c_message_free_unpacked(*pmessage, allocator);
      }
      *pmessage = subm;
      if (subm == NULL || !merge_successful) return FALSE;
      return TRUE;
    }
  }
  return FALSE;
}

static protobuf_c_boolean parse_oneof_member(ScannedMember *scanned_member,
                                             void *member,
                                             ProtobufCMessage *message,
                                             ProtobufCAllocator *allocator) {
  uint32_t *oneof_case = STRUCT_MEMBER_PTR(
      uint32_t, message, scanned_member->field->quantifier_offset);

  /* If we have already parsed a member of this oneof, free it. */
  if (*oneof_case != 0) {
    /* lookup field */
    int field_index =
        int_range_lookup(message->descriptor->n_field_ranges,
                         message->descriptor->field_ranges, *oneof_case);
    const ProtobufCFieldDescriptor *old_field =
        message->descriptor->fields + field_index;
    size_t el_size = sizeof_elt_in_repeated_array(old_field->type);

    switch (old_field->type) {
      case PROTOBUF_C_TYPE_STRING: {
        char **pstr = member;
        const char *def = old_field->default_value;
        if (*pstr != NULL && *pstr != def) do_free(allocator, *pstr);
        break;
      }
      case PROTOBUF_C_TYPE_BYTES: {
        ProtobufCBinaryData *bd = member;
        const ProtobufCBinaryData *def_bd = old_field->default_value;
        if (bd->data != NULL && (def_bd == NULL || bd->data != def_bd->data)) {
          do_free(allocator, bd->data);
        }
        break;
      }
      case PROTOBUF_C_TYPE_MESSAGE: {
        ProtobufCMessage **pmessage = member;
        const ProtobufCMessage *def_mess = old_field->default_value;
        if (*pmessage != NULL && *pmessage != def_mess)
          protobuf_c_message_free_unpacked(*pmessage, allocator);
        break;
      }
      default:
        break;
    }

    memset(member, 0, el_size);
  }
  if (!parse_required_member(scanned_member, member, allocator, TRUE))
    return FALSE;

  *oneof_case = scanned_member->tag;
  return TRUE;
}

static protobuf_c_boolean parse_optional_member(ScannedMember *scanned_member,
                                                void *member,
                                                ProtobufCMessage *message,
                                                ProtobufCAllocator *allocator) {
  if (!parse_required_member(scanned_member, member, allocator, TRUE))
    return FALSE;
  if (scanned_member->field->quantifier_offset != 0)
    STRUCT_MEMBER(protobuf_c_boolean, message,
                  scanned_member->field->quantifier_offset) = TRUE;
  return TRUE;
}

static protobuf_c_boolean parse_repeated_member(ScannedMember *scanned_member,
                                                void *member,
                                                ProtobufCMessage *message,
                                                ProtobufCAllocator *allocator) {
  const ProtobufCFieldDescriptor *field = scanned_member->field;
  size_t *p_n = STRUCT_MEMBER_PTR(size_t, message, field->quantifier_offset);
  size_t siz = sizeof_elt_in_repeated_array(field->type);
  char *array = *(char **)member;

  if (!parse_required_member(scanned_member, array + siz * (*p_n), allocator,
                             FALSE)) {
    return FALSE;
  }
  *p_n += 1;
  return TRUE;
}

static unsigned scan_varint(unsigned len, const uint8_t *data) {
  unsigned i;
  if (len > 10) len = 10;
  for (i = 0; i < len; i++)
    if ((data[i] & 0x80) == 0) break;
  if (i == len) return 0;
  return i + 1;
}

static protobuf_c_boolean parse_packed_repeated_member(
    ScannedMember *scanned_member, void *member, ProtobufCMessage *message) {
  const ProtobufCFieldDescriptor *field = scanned_member->field;
  size_t *p_n = STRUCT_MEMBER_PTR(size_t, message, field->quantifier_offset);
  size_t siz = sizeof_elt_in_repeated_array(field->type);
  void *array = *(char **)member + siz * (*p_n);
  const uint8_t *at = scanned_member->data + scanned_member->length_prefix_len;
  size_t rem = scanned_member->len - scanned_member->length_prefix_len;
  size_t count = 0;
  unsigned i;

  switch (field->type) {
    case PROTOBUF_C_TYPE_SFIXED32:
    case PROTOBUF_C_TYPE_FIXED32:
    case PROTOBUF_C_TYPE_FLOAT:
      count = (scanned_member->len - scanned_member->length_prefix_len) / 4;
#if !defined(WORDS_BIGENDIAN)
      goto no_unpacking_needed;
#else
      for (i = 0; i < count; i++) {
        ((uint32_t *)array)[i] = parse_fixed_uint32(at);
        at += 4;
      }
      break;
#endif
    case PROTOBUF_C_TYPE_SFIXED64:
    case PROTOBUF_C_TYPE_FIXED64:
    case PROTOBUF_C_TYPE_DOUBLE:
      count = (scanned_member->len - scanned_member->length_prefix_len) / 8;
#if !defined(WORDS_BIGENDIAN)
      goto no_unpacking_needed;
#else
      for (i = 0; i < count; i++) {
        ((uint64_t *)array)[i] = parse_fixed_uint64(at);
        at += 8;
      }
      break;
#endif
    case PROTOBUF_C_TYPE_ENUM:
    case PROTOBUF_C_TYPE_INT32:
      while (rem > 0) {
        unsigned s = scan_varint(rem, at);
        if (s == 0) {
          PROTOBUF_C_UNPACK_ERROR("bad packed-repeated int32 value");
          return FALSE;
        }
        ((int32_t *)array)[count++] = parse_int32(s, at);
        at += s;
        rem -= s;
      }
      break;
    case PROTOBUF_C_TYPE_SINT32:
      while (rem > 0) {
        unsigned s = scan_varint(rem, at);
        if (s == 0) {
          PROTOBUF_C_UNPACK_ERROR("bad packed-repeated sint32 value");
          return FALSE;
        }
        ((int32_t *)array)[count++] = unzigzag32(parse_uint32(s, at));
        at += s;
        rem -= s;
      }
      break;
    case PROTOBUF_C_TYPE_UINT32:
      while (rem > 0) {
        unsigned s = scan_varint(rem, at);
        if (s == 0) {
          PROTOBUF_C_UNPACK_ERROR("bad packed-repeated enum or uint32 value");
          return FALSE;
        }
        ((uint32_t *)array)[count++] = parse_uint32(s, at);
        at += s;
        rem -= s;
      }
      break;

    case PROTOBUF_C_TYPE_SINT64:
      while (rem > 0) {
        unsigned s = scan_varint(rem, at);
        if (s == 0) {
          PROTOBUF_C_UNPACK_ERROR("bad packed-repeated sint64 value");
          return FALSE;
        }
        ((int64_t *)array)[count++] = unzigzag64(parse_uint64(s, at));
        at += s;
        rem -= s;
      }
      break;
    case PROTOBUF_C_TYPE_INT64:
    case PROTOBUF_C_TYPE_UINT64:
      while (rem > 0) {
        unsigned s = scan_varint(rem, at);
        if (s == 0) {
          PROTOBUF_C_UNPACK_ERROR("bad packed-repeated int64/uint64 value");
          return FALSE;
        }
        ((int64_t *)array)[count++] = parse_uint64(s, at);
        at += s;
        rem -= s;
      }
      break;
    case PROTOBUF_C_TYPE_BOOL:
      count = rem;
      for (i = 0; i < count; i++) {
        if (at[i] > 1) {
          PROTOBUF_C_UNPACK_ERROR("bad packed-repeated boolean value");
          return FALSE;
        }
        ((protobuf_c_boolean *)array)[i] = at[i];
      }
      break;
    default:
      PROTOBUF_C__ASSERT_NOT_REACHED();
  }
  *p_n += count;
  return TRUE;

#if !defined(WORDS_BIGENDIAN)
no_unpacking_needed:
  memcpy(array, at, count * siz);
  *p_n += count;
  return TRUE;
#endif
}

static protobuf_c_boolean is_packable_type(ProtobufCType type) {
  return type != PROTOBUF_C_TYPE_STRING && type != PROTOBUF_C_TYPE_BYTES &&
         type != PROTOBUF_C_TYPE_MESSAGE;
}

static protobuf_c_boolean parse_member(ScannedMember *scanned_member,
                                       ProtobufCMessage *message,
                                       ProtobufCAllocator *allocator) {
  const ProtobufCFieldDescriptor *field = scanned_member->field;
  void *member;

  if (field == NULL) {
    ProtobufCMessageUnknownField *ufield =
        message->unknown_fields + (message->n_unknown_fields++);
    ufield->tag = scanned_member->tag;
    ufield->wire_type = scanned_member->wire_type;
    ufield->len = scanned_member->len;
    ufield->data = do_alloc(allocator, scanned_member->len);
    if (ufield->data == NULL) return FALSE;
    memcpy(ufield->data, scanned_member->data, ufield->len);
    return TRUE;
  }
  member = (char *)message + field->offset;
  switch (field->label) {
    case PROTOBUF_C_LABEL_REQUIRED:
      return parse_required_member(scanned_member, member, allocator, TRUE);
    case PROTOBUF_C_LABEL_OPTIONAL:
    case PROTOBUF_C_LABEL_NONE:
      if (0 != (field->flags & PROTOBUF_C_FIELD_FLAG_ONEOF)) {
        return parse_oneof_member(scanned_member, member, message, allocator);
      } else {
        return parse_optional_member(scanned_member, member, message,
                                     allocator);
      }
    case PROTOBUF_C_LABEL_REPEATED:
      if (scanned_member->wire_type == PROTOBUF_C_WIRE_TYPE_LENGTH_PREFIXED &&
          (0 != (field->flags & PROTOBUF_C_FIELD_FLAG_PACKED) ||
           is_packable_type(field->type))) {
        return parse_packed_repeated_member(scanned_member, member, message);
      } else {
        return parse_repeated_member(scanned_member, member, message,
                                     allocator);
      }
  }
  PROTOBUF_C__ASSERT_NOT_REACHED();
  return 0;
}

/**
 * Initialise messages generated by old code.
 *
 * This function is used if desc->message_init == NULL (which occurs
 * for old code, and which would be useful to support allocating
 * descriptors dynamically).
 */
static void message_init_generic(const ProtobufCMessageDescriptor *desc,
                                 ProtobufCMessage *message) {
  unsigned i;

  memset(message, 0, desc->sizeof_message);
  message->descriptor = desc;
  for (i = 0; i < desc->n_fields; i++) {
    if (desc->fields[i].default_value != NULL &&
        desc->fields[i].label != PROTOBUF_C_LABEL_REPEATED) {
      void *field = STRUCT_MEMBER_P(message, desc->fields[i].offset);
      const void *dv = desc->fields[i].default_value;

      switch (desc->fields[i].type) {
        case PROTOBUF_C_TYPE_INT32:
        case PROTOBUF_C_TYPE_SINT32:
        case PROTOBUF_C_TYPE_SFIXED32:
        case PROTOBUF_C_TYPE_UINT32:
        case PROTOBUF_C_TYPE_FIXED32:
        case PROTOBUF_C_TYPE_FLOAT:
        case PROTOBUF_C_TYPE_ENUM:
          memcpy(field, dv, 4);
          break;
        case PROTOBUF_C_TYPE_INT64:
        case PROTOBUF_C_TYPE_SINT64:
        case PROTOBUF_C_TYPE_SFIXED64:
        case PROTOBUF_C_TYPE_UINT64:
        case PROTOBUF_C_TYPE_FIXED64:
        case PROTOBUF_C_TYPE_DOUBLE:
          memcpy(field, dv, 8);
          break;
        case PROTOBUF_C_TYPE_BOOL:
          memcpy(field, dv, sizeof(protobuf_c_boolean));
          break;
        case PROTOBUF_C_TYPE_BYTES:
          memcpy(field, dv, sizeof(ProtobufCBinaryData));
          break;

        case PROTOBUF_C_TYPE_STRING:
        case PROTOBUF_C_TYPE_MESSAGE:
          /*
           * The next line essentially implements a cast
           * from const, which is totally unavoidable.
           */
          *(const void **)field = dv;
          break;
      }
    }
  }
}

/**@}*/

/*
 * ScannedMember slabs (an unpacking implementation detail). Before doing real
 * unpacking, we first scan through the elements to see how many there are (for
 * repeated fields), and which field to use (for non-repeated fields given
 * twice).
 *
 * In order to avoid allocations for small messages, we keep a stack-allocated
 * slab of ScannedMembers of size FIRST_SCANNED_MEMBER_SLAB_SIZE (16). After we
 * fill that up, we allocate each slab twice as large as the previous one.
 */
#define FIRST_SCANNED_MEMBER_SLAB_SIZE_LOG2 4

/*
 * The number of slabs, including the stack-allocated ones; choose the number so
 * that we would overflow if we needed a slab larger than provided.
 */
#define MAX_SCANNED_MEMBER_SLAB                                      \
  (sizeof(unsigned int) * 8 - 1 - BOUND_SIZEOF_SCANNED_MEMBER_LOG2 - \
   FIRST_SCANNED_MEMBER_SLAB_SIZE_LOG2)

#define REQUIRED_FIELD_BITMAP_SET(index) \
  (required_fields_bitmap[(index) / 8] |= (1UL << ((index) % 8)))

#define REQUIRED_FIELD_BITMAP_IS_SET(index) \
  (required_fields_bitmap[(index) / 8] & (1UL << ((index) % 8)))

ProtobufCMessage *protobuf_c_message_unpack(
    const ProtobufCMessageDescriptor *desc, ProtobufCAllocator *allocator,
    size_t len, const uint8_t *data) {
  ProtobufCMessage *rv;
  size_t rem = len;
  const uint8_t *at = data;
  const ProtobufCFieldDescriptor *last_field = desc->fields + 0;
  ScannedMember first_member_slab[1UL << FIRST_SCANNED_MEMBER_SLAB_SIZE_LOG2];

  /*
   * scanned_member_slabs[i] is an array of arrays of ScannedMember.
   * The first slab (scanned_member_slabs[0] is just a pointer to
   * first_member_slab), above. All subsequent slabs will be allocated
   * using the allocator.
   */
  ScannedMember *scanned_member_slabs[MAX_SCANNED_MEMBER_SLAB + 1];
  unsigned which_slab = 0;    /* the slab we are currently populating */
  unsigned in_slab_index = 0; /* number of members in the slab */
  size_t n_unknown = 0;
  unsigned f;
  unsigned j;
  unsigned i_slab;
  unsigned last_field_index = 0;
  unsigned required_fields_bitmap_len;
  unsigned char required_fields_bitmap_stack[16];
  unsigned char *required_fields_bitmap = required_fields_bitmap_stack;
  protobuf_c_boolean required_fields_bitmap_alloced = FALSE;

  ASSERT_IS_MESSAGE_DESCRIPTOR(desc);

  if (allocator == NULL) allocator = &protobuf_c__allocator;

  rv = do_alloc(allocator, desc->sizeof_message);
  if (!rv) return (NULL);
  scanned_member_slabs[0] = first_member_slab;

  required_fields_bitmap_len = (desc->n_fields + 7) / 8;
  if (required_fields_bitmap_len > sizeof(required_fields_bitmap_stack)) {
    required_fields_bitmap = do_alloc(allocator, required_fields_bitmap_len);
    if (!required_fields_bitmap) {
      do_free(allocator, rv);
      return (NULL);
    }
    required_fields_bitmap_alloced = TRUE;
  }
  memset(required_fields_bitmap, 0, required_fields_bitmap_len);

  /*
   * Generated code always defines "message_init". However, we provide a
   * fallback for (1) users of old protobuf-c generated-code that do not
   * provide the function, and (2) descriptors constructed from some other
   * source (most likely, direct construction from the .proto file).
   */
  if (desc->message_init != NULL)
    protobuf_c_message_init(desc, rv);
  else
    message_init_generic(desc, rv);

  while (rem > 0) {
    uint32_t tag;
    ProtobufCWireType wire_type;
    size_t used = parse_tag_and_wiretype(rem, at, &tag, &wire_type);
    const ProtobufCFieldDescriptor *field;
    ScannedMember tmp;

    if (used == 0) {
      PROTOBUF_C_UNPACK_ERROR("error parsing tag/wiretype at offset %u",
                              (unsigned)(at - data));
      goto error_cleanup_during_scan;
    }
    /*
     * \todo Consider optimizing for field[1].id == tag, if field[1]
     * exists!
     */
    if (last_field == NULL || last_field->id != tag) {
      /* lookup field */
      int field_index =
          int_range_lookup(desc->n_field_ranges, desc->field_ranges, tag);
      if (field_index < 0) {
        field = NULL;
        n_unknown++;
      } else {
        field = desc->fields + field_index;
        last_field = field;
        last_field_index = field_index;
      }
    } else {
      field = last_field;
    }

    if (field != NULL && field->label == PROTOBUF_C_LABEL_REQUIRED)
      REQUIRED_FIELD_BITMAP_SET(last_field_index);

    at += used;
    rem -= used;
    tmp.tag = tag;
    tmp.wire_type = wire_type;
    tmp.field = field;
    tmp.data = at;
    tmp.length_prefix_len = 0;

    switch (wire_type) {
      case PROTOBUF_C_WIRE_TYPE_VARINT: {
        unsigned max_len = rem < 10 ? rem : 10;
        unsigned i;

        for (i = 0; i < max_len; i++)
          if ((at[i] & 0x80) == 0) break;
        if (i == max_len) {
          PROTOBUF_C_UNPACK_ERROR("unterminated varint at offset %u",
                                  (unsigned)(at - data));
          goto error_cleanup_during_scan;
        }
        tmp.len = i + 1;
        break;
      }
      case PROTOBUF_C_WIRE_TYPE_64BIT:
        if (rem < 8) {
          PROTOBUF_C_UNPACK_ERROR("too short after 64bit wiretype at offset %u",
                                  (unsigned)(at - data));
          goto error_cleanup_during_scan;
        }
        tmp.len = 8;
        break;
      case PROTOBUF_C_WIRE_TYPE_LENGTH_PREFIXED: {
        size_t pref_len;

        tmp.len = scan_length_prefixed_data(rem, at, &pref_len);
        if (tmp.len == 0) {
          /* NOTE: scan_length_prefixed_data calls UNPACK_ERROR */
          goto error_cleanup_during_scan;
        }
        tmp.length_prefix_len = pref_len;
        break;
      }
      case PROTOBUF_C_WIRE_TYPE_32BIT:
        if (rem < 4) {
          PROTOBUF_C_UNPACK_ERROR("too short after 32bit wiretype at offset %u",
                                  (unsigned)(at - data));
          goto error_cleanup_during_scan;
        }
        tmp.len = 4;
        break;
      default:
        PROTOBUF_C_UNPACK_ERROR("unsupported tag %u at offset %u", wire_type,
                                (unsigned)(at - data));
        goto error_cleanup_during_scan;
    }

    if (in_slab_index ==
        (1UL << (which_slab + FIRST_SCANNED_MEMBER_SLAB_SIZE_LOG2))) {
      size_t size;

      in_slab_index = 0;
      if (which_slab == MAX_SCANNED_MEMBER_SLAB) {
        PROTOBUF_C_UNPACK_ERROR("too many fields");
        goto error_cleanup_during_scan;
      }
      which_slab++;
      size = sizeof(ScannedMember)
             << (which_slab + FIRST_SCANNED_MEMBER_SLAB_SIZE_LOG2);
      scanned_member_slabs[which_slab] = do_alloc(allocator, size);
      if (scanned_member_slabs[which_slab] == NULL)
        goto error_cleanup_during_scan;
    }
    scanned_member_slabs[which_slab][in_slab_index++] = tmp;

    if (field != NULL && field->label == PROTOBUF_C_LABEL_REPEATED) {
      size_t *n = STRUCT_MEMBER_PTR(size_t, rv, field->quantifier_offset);
      if (wire_type == PROTOBUF_C_WIRE_TYPE_LENGTH_PREFIXED &&
          (0 != (field->flags & PROTOBUF_C_FIELD_FLAG_PACKED) ||
           is_packable_type(field->type))) {
        size_t count;
        if (!count_packed_elements(field->type, tmp.len - tmp.length_prefix_len,
                                   tmp.data + tmp.length_prefix_len, &count)) {
          PROTOBUF_C_UNPACK_ERROR("counting packed elements");
          goto error_cleanup_during_scan;
        }
        *n += count;
      } else {
        *n += 1;
      }
    }

    at += tmp.len;
    rem -= tmp.len;
  }

  /* allocate space for repeated fields, also check that all required fields
   * have been set */
  for (f = 0; f < desc->n_fields; f++) {
    const ProtobufCFieldDescriptor *field = desc->fields + f;
    if (field->label == PROTOBUF_C_LABEL_REPEATED) {
      size_t siz = sizeof_elt_in_repeated_array(field->type);
      size_t *n_ptr = STRUCT_MEMBER_PTR(size_t, rv, field->quantifier_offset);
      if (*n_ptr != 0) {
        unsigned n = *n_ptr;
        void *a;
        *n_ptr = 0;
        assert(rv->descriptor != NULL);
#define CLEAR_REMAINING_N_PTRS()                               \
  for (f++; f < desc->n_fields; f++) {                         \
    field = desc->fields + f;                                  \
    if (field->label == PROTOBUF_C_LABEL_REPEATED)             \
      STRUCT_MEMBER(size_t, rv, field->quantifier_offset) = 0; \
  }
        a = do_alloc(allocator, siz * n);
        if (!a) {
          CLEAR_REMAINING_N_PTRS();
          goto error_cleanup;
        }
        STRUCT_MEMBER(void *, rv, field->offset) = a;
      }
    } else if (field->label == PROTOBUF_C_LABEL_REQUIRED) {
      if (field->default_value == NULL && !REQUIRED_FIELD_BITMAP_IS_SET(f)) {
        CLEAR_REMAINING_N_PTRS();
        PROTOBUF_C_UNPACK_ERROR("message '%s': missing required field '%s'",
                                desc->name, field->name);
        goto error_cleanup;
      }
    }
  }
#undef CLEAR_REMAINING_N_PTRS

  /* allocate space for unknown fields */
  if (n_unknown) {
    rv->unknown_fields =
        do_alloc(allocator, n_unknown * sizeof(ProtobufCMessageUnknownField));
    if (rv->unknown_fields == NULL) goto error_cleanup;
  }

  /* do real parsing */
  for (i_slab = 0; i_slab <= which_slab; i_slab++) {
    unsigned max =
        (i_slab == which_slab) ? in_slab_index : (1UL << (i_slab + 4));
    ScannedMember *slab = scanned_member_slabs[i_slab];

    for (j = 0; j < max; j++) {
      if (!parse_member(slab + j, rv, allocator)) {
        PROTOBUF_C_UNPACK_ERROR(
            "error parsing member %s of %s",
            slab->field ? slab->field->name : "*unknown-field*", desc->name);
        goto error_cleanup;
      }
    }
  }

  /* cleanup */
  for (j = 1; j <= which_slab; j++) do_free(allocator, scanned_member_slabs[j]);
  if (required_fields_bitmap_alloced)
    do_free(allocator, required_fields_bitmap);
  return rv;

error_cleanup:
  protobuf_c_message_free_unpacked(rv, allocator);
  for (j = 1; j <= which_slab; j++) do_free(allocator, scanned_member_slabs[j]);
  if (required_fields_bitmap_alloced)
    do_free(allocator, required_fields_bitmap);
  return NULL;

error_cleanup_during_scan:
  do_free(allocator, rv);
  for (j = 1; j <= which_slab; j++) do_free(allocator, scanned_member_slabs[j]);
  if (required_fields_bitmap_alloced)
    do_free(allocator, required_fields_bitmap);
  return NULL;
}

void protobuf_c_message_free_unpacked(ProtobufCMessage *message,
                                      ProtobufCAllocator *allocator) {
  const ProtobufCMessageDescriptor *desc;
  unsigned f;

  if (message == NULL) return;

  desc = message->descriptor;

  ASSERT_IS_MESSAGE(message);

  if (allocator == NULL) allocator = &protobuf_c__allocator;
  message->descriptor = NULL;
  for (f = 0; f < desc->n_fields; f++) {
    if (0 != (desc->fields[f].flags & PROTOBUF_C_FIELD_FLAG_ONEOF) &&
        desc->fields[f].id !=
            STRUCT_MEMBER(uint32_t, message,
                          desc->fields[f].quantifier_offset)) {
      /* This is not the selected oneof, skip it */
      continue;
    }

    if (desc->fields[f].label == PROTOBUF_C_LABEL_REPEATED) {
      size_t n =
          STRUCT_MEMBER(size_t, message, desc->fields[f].quantifier_offset);
      void *arr = STRUCT_MEMBER(void *, message, desc->fields[f].offset);

      if (arr != NULL) {
        if (desc->fields[f].type == PROTOBUF_C_TYPE_STRING) {
          unsigned i;
          for (i = 0; i < n; i++) do_free(allocator, ((char **)arr)[i]);
        } else if (desc->fields[f].type == PROTOBUF_C_TYPE_BYTES) {
          unsigned i;
          for (i = 0; i < n; i++)
            do_free(allocator, ((ProtobufCBinaryData *)arr)[i].data);
        } else if (desc->fields[f].type == PROTOBUF_C_TYPE_MESSAGE) {
          unsigned i;
          for (i = 0; i < n; i++)
            protobuf_c_message_free_unpacked(((ProtobufCMessage **)arr)[i],
                                             allocator);
        }
        do_free(allocator, arr);
      }
    } else if (desc->fields[f].type == PROTOBUF_C_TYPE_STRING) {
      char *str = STRUCT_MEMBER(char *, message, desc->fields[f].offset);

      if (str && str != desc->fields[f].default_value) do_free(allocator, str);
    } else if (desc->fields[f].type == PROTOBUF_C_TYPE_BYTES) {
      void *data =
          STRUCT_MEMBER(ProtobufCBinaryData, message, desc->fields[f].offset)
              .data;
      const ProtobufCBinaryData *default_bd;

      default_bd = desc->fields[f].default_value;
      if (data != NULL && (default_bd == NULL || default_bd->data != data)) {
        do_free(allocator, data);
      }
    } else if (desc->fields[f].type == PROTOBUF_C_TYPE_MESSAGE) {
      ProtobufCMessage *sm;

      sm = STRUCT_MEMBER(ProtobufCMessage *, message, desc->fields[f].offset);
      if (sm && sm != desc->fields[f].default_value)
        protobuf_c_message_free_unpacked(sm, allocator);
    }
  }

  for (f = 0; f < message->n_unknown_fields; f++)
    do_free(allocator, message->unknown_fields[f].data);
  if (message->unknown_fields != NULL)
    do_free(allocator, message->unknown_fields);

  do_free(allocator, message);
}

void protobuf_c_message_init(const ProtobufCMessageDescriptor *descriptor,
                             void *message) {
  descriptor->message_init((ProtobufCMessage *)(message));
}

protobuf_c_boolean protobuf_c_message_check(const ProtobufCMessage *message) {
  unsigned i;

  if (!message || !message->descriptor ||
      message->descriptor->magic != PROTOBUF_C__MESSAGE_DESCRIPTOR_MAGIC) {
    return FALSE;
  }

  for (i = 0; i < message->descriptor->n_fields; i++) {
    const ProtobufCFieldDescriptor *f = message->descriptor->fields + i;
    ProtobufCType type = f->type;
    ProtobufCLabel label = f->label;
    void *field = STRUCT_MEMBER_P(message, f->offset);

    if (label == PROTOBUF_C_LABEL_REPEATED) {
      size_t *quantity = STRUCT_MEMBER_P(message, f->quantifier_offset);

      if (*quantity > 0 && *(void **)field == NULL) {
        return FALSE;
      }

      if (type == PROTOBUF_C_TYPE_MESSAGE) {
        ProtobufCMessage **submessage = *(ProtobufCMessage ***)field;
        unsigned j;
        for (j = 0; j < *quantity; j++) {
          if (!protobuf_c_message_check(submessage[j])) return FALSE;
        }
      } else if (type == PROTOBUF_C_TYPE_STRING) {
        char **string = *(char ***)field;
        unsigned j;
        for (j = 0; j < *quantity; j++) {
          if (!string[j]) return FALSE;
        }
      } else if (type == PROTOBUF_C_TYPE_BYTES) {
        ProtobufCBinaryData *bd = *(ProtobufCBinaryData **)field;
        unsigned j;
        for (j = 0; j < *quantity; j++) {
          if (bd[j].len > 0 && bd[j].data == NULL) return FALSE;
        }
      }

    } else { /* PROTOBUF_C_LABEL_REQUIRED or PROTOBUF_C_LABEL_OPTIONAL */

      if (type == PROTOBUF_C_TYPE_MESSAGE) {
        ProtobufCMessage *submessage = *(ProtobufCMessage **)field;
        if (label == PROTOBUF_C_LABEL_REQUIRED || submessage != NULL) {
          if (!protobuf_c_message_check(submessage)) return FALSE;
        }
      } else if (type == PROTOBUF_C_TYPE_STRING) {
        char *string = *(char **)field;
        if (label == PROTOBUF_C_LABEL_REQUIRED && string == NULL) return FALSE;
      } else if (type == PROTOBUF_C_TYPE_BYTES) {
        protobuf_c_boolean *has =
            STRUCT_MEMBER_P(message, f->quantifier_offset);
        ProtobufCBinaryData *bd = field;
        if (label == PROTOBUF_C_LABEL_REQUIRED || *has == TRUE) {
          if (bd->len > 0 && bd->data == NULL) return FALSE;
        }
      }
    }
  }

  return TRUE;
}

/* === services === */

typedef void (*GenericHandler)(void *service, const ProtobufCMessage *input,
                               ProtobufCClosure closure, void *closure_data);