src/google/protobuf-c/protobuf-c.c

   1 /* --- protobuf-c.c: public protobuf c runtime implementation --- */
   2
   3 /*
   4  * Copyright 2008, Dave Benson.
   5  *
   6  * Licensed under the Apache License, Version 2.0 (the "License");
   7  * you may not use this file except in compliance with
   8  * the License. You may obtain a copy of the License
   9  * at http://www.apache.org/licenses/LICENSE-2.0 Unless
  10  * required by applicable law or agreed to in writing,
  11  * software distributed under the License is distributed on
  12  * an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
  13  * KIND, either express or implied. See the License for the
  14  * specific language governing permissions and limitations
  15  * under the License.
  16  */
  17
  18 /* TODO: certain implementations use 32-bit math even for
  19    (uint64_size, uint64_pack, parse_uint64) */
  20
  21 /* TODO: get_packed_size and pack seem to use type-prefixed names,
  22    whereas parse uses type-suffixed names.  pick one and stick with it.
  23       Decision:  go with type-suffixed, since the type (or its instance)
  24       is typically the object of the verb.
  25    NOTE: perhaps the "parse" methods should be reanemd to "unpack"
  26    at the same time.
  27  */
  28
  29 #include <stdio.h>                      /* for occasional printf()s */
  30 #include <stdlib.h>                     /* for abort(), malloc() etc */
  31 #include <string.h>                     /* for strlen(), memcpy(), memmove() */
  32
  33 #ifndef PRINT_UNPACK_ERRORS
  34 #define PRINT_UNPACK_ERRORS              1
  35 #endif
  36
  37 #include "protobuf-c.h"
  38
  39 #define MAX_UINT64_ENCODED_SIZE 10
  40
  41 /* convenience macros */
  42 #define TMPALLOC(allocator, size) ((allocator)->tmp_alloc ((allocator)->allocator_data, (size)))
  43 #define FREE(allocator, ptr)   \
  44    do { if ((ptr) != NULL) ((allocator)->free ((allocator)->allocator_data, (ptr))); } while(0)
  45 #define UNALIGNED_ALLOC(allocator, size) ALLOC (allocator, size) /* placeholder */
  46 #define STRUCT_MEMBER_P(struct_p, struct_offset)   \
  47     ((void *) ((uint8_t*) (struct_p) + (struct_offset)))
  48 #define STRUCT_MEMBER(member_type, struct_p, struct_offset)   \
  49     (*(member_type*) STRUCT_MEMBER_P ((struct_p), (struct_offset)))
  50 #define STRUCT_MEMBER_PTR(member_type, struct_p, struct_offset)   \
  51     ((member_type*) STRUCT_MEMBER_P ((struct_p), (struct_offset)))
  52 #define TRUE 1
  53 #define FALSE 0
  54
  55 static void
  56 alloc_failed_warning (unsigned size, const char *filename, unsigned line)
  57 {
  58   fprintf (stderr,
  59            "WARNING: out-of-memory allocating a block of size %u (%s:%u)\n",
  60            size, filename, line);
  61 }
  62
  63 /* Try to allocate memory, running some special code if it fails. */
  64 #define DO_ALLOC(dst, allocator, size, fail_code)                           \
  65 { size_t da__allocation_size = (size);                                      \
  66   if (da__allocation_size == 0)                                             \
  67     dst = NULL;                                                             \
  68   else if ((dst=((allocator)->alloc ((allocator)->allocator_data,           \
  69                                      da__allocation_size))) == NULL)        \
  70     {                                                                       \
  71       alloc_failed_warning (da__allocation_size, __FILE__, __LINE__);       \
  72       fail_code;                                                            \
  73     }                                                                       \
  74 }
  75 #define DO_UNALIGNED_ALLOC  DO_ALLOC            /* placeholder */
  76
  77
  78
  79 #define ASSERT_IS_ENUM_DESCRIPTOR(desc) \
  80   assert((desc)->magic == PROTOBUF_C_ENUM_DESCRIPTOR_MAGIC)
  81 #define ASSERT_IS_MESSAGE_DESCRIPTOR(desc) \
  82   assert((desc)->magic == PROTOBUF_C_MESSAGE_DESCRIPTOR_MAGIC)
  83 #define ASSERT_IS_MESSAGE(message) \
  84   ASSERT_IS_MESSAGE_DESCRIPTOR((message)->descriptor)
  85 #define ASSERT_IS_SERVICE_DESCRIPTOR(desc) \
  86   assert((desc)->magic == PROTOBUF_C_SERVICE_DESCRIPTOR_MAGIC)
  87
  88 /* --- allocator --- */
  89
  90 static void protobuf_c_out_of_memory_default (void)
  91 {
  92   fprintf (stderr, "Out Of Memory!!!\n");
  93   abort ();
  94 }
  95 void (*protobuf_c_out_of_memory) (void) = protobuf_c_out_of_memory_default;
  96
  97 static void *system_alloc(void *allocator_data, size_t size)
  98 {
  99   void *rv;
 100   (void) allocator_data;
 101   if (size == 0)
 102     return NULL;
 103   rv = malloc (size);
 104   if (rv == NULL)
 105     protobuf_c_out_of_memory ();
 106   return rv;
 107 }
 108
 109 static void system_free (void *allocator_data, void *data)
 110 {
 111   (void) allocator_data;
 112   if (data)
 113     free (data);
 114 }
 115
 116 ProtobufCAllocator protobuf_c_default_allocator =
 117 {
 118   system_alloc,
 119   system_free,
 120   NULL,
 121   8192,
 122   NULL
 123 };
 124
 125 ProtobufCAllocator protobuf_c_system_allocator =
 126 {
 127   system_alloc,
 128   system_free,
 129   NULL,
 130   8192,
 131   NULL
 132 };
 133
 134 /* === buffer-simple === */
 135 void
 136 protobuf_c_buffer_simple_append (ProtobufCBuffer *buffer,
 137                                  size_t           len,
 138                                  const uint8_t   *data)
 139 {
 140   ProtobufCBufferSimple *simp = (ProtobufCBufferSimple *) buffer;
 141   size_t new_len = simp->len + len;
 142   if (new_len > simp->alloced)
 143     {
 144       size_t new_alloced = simp->alloced * 2;
 145       uint8_t *new_data;
 146       while (new_alloced < new_len)
 147         new_alloced += new_alloced;
 148       DO_ALLOC (new_data, &protobuf_c_default_allocator, new_alloced, return);
 149       memcpy (new_data, simp->data, simp->len);
 150       if (simp->must_free_data)
 151         FREE (&protobuf_c_default_allocator, simp->data);
 152       else
 153         simp->must_free_data = 1;
 154       simp->data = new_data;
 155       simp->alloced = new_alloced;
 156     }
 157   memcpy (simp->data + simp->len, data, len);
 158   simp->len = new_len;
 159 }
 160
 161 /* === get_packed_size() === */
 162
 163 /* Return the number of bytes required to store the
 164    tag for the field (which includes 3 bits for
 165    the wire-type, and a single bit that denotes the end-of-tag. */
 166 static inline size_t
 167 get_tag_size (unsigned number)
 168 {
 169   if (number < (1<<4))
 170     return 1;
 171   else if (number < (1<<11))
 172     return 2;
 173   else if (number < (1<<18))
 174     return 3;
 175   else if (number < (1<<25))
 176     return 4;
 177   else
 178     return 5;
 179 }
 180
 181 /* Return the number of bytes required to store
 182    a variable-length unsigned integer that fits in 32-bit uint
 183    in base-128 encoding. */
 184 static inline size_t
 185 uint32_size (uint32_t v)
 186 {
 187   if (v < (1<<7))
 188     return 1;
 189   else if (v < (1<<14))
 190     return 2;
 191   else if (v < (1<<21))
 192     return 3;
 193   else if (v < (1<<28))
 194     return 4;
 195   else
 196     return 5;
 197 }
 198 /* Return the number of bytes required to store
 199    a variable-length signed integer that fits in 32-bit int
 200    in base-128 encoding. */
 201 static inline size_t
 202 int32_size (int32_t v)
 203 {
 204   if (v < 0)
 205     return 10;
 206   else if (v < (1<<7))
 207     return 1;
 208   else if (v < (1<<14))
 209     return 2;
 210   else if (v < (1<<21))
 211     return 3;
 212   else if (v < (1<<28))
 213     return 4;
 214   else
 215     return 5;
 216 }
 217 /* return the zigzag-encoded 32-bit unsigned int from a 32-bit signed int */
 218 static inline uint32_t
 219 zigzag32 (int32_t v)
 220 {
 221   if (v < 0)
 222     return ((uint32_t)(-v)) * 2 - 1;
 223   else
 224     return v * 2;
 225 }
 226 /* Return the number of bytes required to store
 227    a variable-length signed integer that fits in 32-bit int,
 228    converted to unsigned via the zig-zag algorithm,
 229    then packed using base-128 encoding. */
 230 static inline size_t
 231 sint32_size (int32_t v)
 232 {
 233   return uint32_size(zigzag32(v));
 234 }
 235
 236 /* Return the number of bytes required to store
 237    a variable-length unsigned integer that fits in 64-bit uint
 238    in base-128 encoding. */
 239 static inline size_t
 240 uint64_size (uint64_t v)
 241 {
 242   uint32_t upper_v = (v>>32);
 243   if (upper_v == 0)
 244     return uint32_size ((uint32_t)v);
 245   else if (upper_v < (1<<3))
 246     return 5;
 247   else if (upper_v < (1<<10))
 248     return 6;
 249   else if (upper_v < (1<<17))
 250     return 7;
 251   else if (upper_v < (1<<24))
 252     return 8;
 253   else if (upper_v < (1U<<31))
 254     return 9;
 255   else
 256     return 10;
 257 }
 258
 259 /* return the zigzag-encoded 64-bit unsigned int from a 64-bit signed int */
 260 static inline uint64_t
 261 zigzag64 (int64_t v)
 262 {
 263   if (v < 0)
 264     return ((uint64_t)(-v)) * 2 - 1;
 265   else
 266     return v * 2;
 267 }
 268
 269 /* Return the number of bytes required to store
 270    a variable-length signed integer that fits in 64-bit int,
 271    converted to unsigned via the zig-zag algorithm,
 272    then packed using base-128 encoding. */
 273 static inline size_t
 274 sint64_size (int64_t v)
 275 {
 276   return uint64_size(zigzag64(v));
 277 }
 278
 279 /* Get serialized size of a single field in the message,
 280    including the space needed by the identifying tag. */
 281 static size_t
 282 required_field_get_packed_size (const ProtobufCFieldDescriptor *field,
 283                                 const void *member)
 284 {
 285   size_t rv = get_tag_size (field->id);
 286   switch (field->type)
 287     {
 288     case PROTOBUF_C_TYPE_SINT32:
 289       return rv + sint32_size (*(const int32_t *) member);
 290     case PROTOBUF_C_TYPE_INT32:
 291       return rv + int32_size (*(const uint32_t *) member);
 292     case PROTOBUF_C_TYPE_UINT32:
 293       return rv + uint32_size (*(const uint32_t *) member);
 294     case PROTOBUF_C_TYPE_SINT64:
 295       return rv + sint64_size (*(const int64_t *) member);
 296     case PROTOBUF_C_TYPE_INT64:
 297     case PROTOBUF_C_TYPE_UINT64:
 298       return rv + uint64_size (*(const uint64_t *) member);
 299     case PROTOBUF_C_TYPE_SFIXED32:
 300     case PROTOBUF_C_TYPE_FIXED32:
 301       return rv + 4;
 302     case PROTOBUF_C_TYPE_SFIXED64:
 303     case PROTOBUF_C_TYPE_FIXED64:
 304       return rv + 8;
 305     case PROTOBUF_C_TYPE_BOOL:
 306       return rv + 1;
 307     case PROTOBUF_C_TYPE_FLOAT:
 308       return rv + 4;
 309     case PROTOBUF_C_TYPE_DOUBLE:
 310       return rv + 8;
 311     case PROTOBUF_C_TYPE_ENUM:
 312       // TODO: is this correct for negative-valued enums?
 313       return rv + uint32_size (*(const uint32_t *) member);
 314     case PROTOBUF_C_TYPE_STRING:
 315       {
 316         const char *str = *(char * const *) member;
 317         size_t len = str ? strlen (str) : 0;
 318         return rv + uint32_size (len) + len;
 319       }
 320     case PROTOBUF_C_TYPE_BYTES:
 321       {
 322         size_t len = ((const ProtobufCBinaryData*) member)->len;
 323         return rv + uint32_size (len) + len;
 324       }
 325     //case PROTOBUF_C_TYPE_GROUP:
 326     case PROTOBUF_C_TYPE_MESSAGE:
 327       {
 328         const ProtobufCMessage *msg = * (ProtobufCMessage * const *) member;
 329         size_t subrv = msg ? protobuf_c_message_get_packed_size (msg) : 0;
 330         return rv + uint32_size (subrv) + subrv;
 331       }
 332     }
 333   PROTOBUF_C_ASSERT_NOT_REACHED ();
 334   return 0;
 335 }
 336
 337 /* Get serialized size of a single optional field in the message,
 338    including the space needed by the identifying tag.
 339    Returns 0 if the optional field isn't set. */
 340 static size_t
 341 optional_field_get_packed_size (const ProtobufCFieldDescriptor *field,
 342                                 const protobuf_c_boolean *has,
 343                                 const void *member)
 344 {
 345   if (field->type == PROTOBUF_C_TYPE_MESSAGE
 346    || field->type == PROTOBUF_C_TYPE_STRING)
 347     {
 348       const void *ptr = * (const void * const *) member;
 349       if (ptr == NULL
 350        || ptr == field->default_value)
 351         return 0;
 352     }
 353   else
 354     {
 355       if (!*has)
 356         return 0;
 357     }
 358   return required_field_get_packed_size (field, member);
 359 }
 360
 361 /* Get serialized size of a repeated field in the message,
 362    which may consist of any number of values (including 0).
 363    Includes the space needed by the identifying tags (as needed). */
 364 static size_t
 365 repeated_field_get_packed_size (const ProtobufCFieldDescriptor *field,
 366                                 size_t count,
 367                                 const void *member)
 368 {
 369   size_t rv = get_tag_size (field->id) * count;
 370   unsigned i;
 371   void *array = * (void * const *) member;
 372   switch (field->type)
 373     {
 374     case PROTOBUF_C_TYPE_SINT32:
 375       for (i = 0; i < count; i++)
 376         rv += sint32_size (((int32_t*)array)[i]);
 377       break;
 378     case PROTOBUF_C_TYPE_INT32:
 379       for (i = 0; i < count; i++)
 380         rv += int32_size (((uint32_t*)array)[i]);
 381       break;
 382     case PROTOBUF_C_TYPE_UINT32:
 383     case PROTOBUF_C_TYPE_ENUM:
 384       for (i = 0; i < count; i++)
 385         rv += uint32_size (((uint32_t*)array)[i]);
 386       break;
 387     case PROTOBUF_C_TYPE_SINT64:
 388       for (i = 0; i < count; i++)
 389         rv += sint64_size (((int64_t*)array)[i]);
 390       break;
 391     case PROTOBUF_C_TYPE_INT64:
 392     case PROTOBUF_C_TYPE_UINT64:
 393       for (i = 0; i < count; i++)
 394         rv += uint64_size (((uint64_t*)array)[i]);
 395       break;
 396     case PROTOBUF_C_TYPE_SFIXED32:
 397     case PROTOBUF_C_TYPE_FIXED32:
 398     case PROTOBUF_C_TYPE_FLOAT:
 399       rv += 4 * count;
 400       break;
 401     case PROTOBUF_C_TYPE_SFIXED64:
 402     case PROTOBUF_C_TYPE_FIXED64:
 403     case PROTOBUF_C_TYPE_DOUBLE:
 404       rv += 8 * count;
 405       break;
 406     case PROTOBUF_C_TYPE_BOOL:
 407       rv += count;
 408       break;
 409     case PROTOBUF_C_TYPE_STRING:
 410       for (i = 0; i < count; i++)
 411         {
 412           size_t len = strlen (((char**) array)[i]);
 413           rv += uint32_size (len) + len;
 414         }
 415       break;
 416
 417     case PROTOBUF_C_TYPE_BYTES:
 418       for (i = 0; i < count; i++)
 419         {
 420           size_t len = ((ProtobufCBinaryData*) array)[i].len;
 421           rv += uint32_size (len) + len;
 422         }
 423       break;
 424     case PROTOBUF_C_TYPE_MESSAGE:
 425       for (i = 0; i < count; i++)
 426         {
 427           size_t len = protobuf_c_message_get_packed_size (((ProtobufCMessage **) array)[i]);
 428           rv += uint32_size (len) + len;
 429         }
 430       break;
 431     //case PROTOBUF_C_TYPE_GROUP:          // NOT SUPPORTED
 432     }
 433   return rv;
 434 }
 435
 436 /* Get the packed size of a unknown field (meaning one that
 437    is passed through mostly uninterpreted... this is done
 438    for forward compatibilty with the addition of new fields). */
 439 static inline size_t
 440 unknown_field_get_packed_size (const ProtobufCMessageUnknownField *field)
 441 {
 442   return get_tag_size (field->tag) + field->len;
 443 }
 444
 445 /* Get the number of bytes that the message will occupy once serialized. */
 446 size_t
 447 protobuf_c_message_get_packed_size(const ProtobufCMessage *message)
 448 {
 449   unsigned i;
 450   size_t rv = 0;
 451   ASSERT_IS_MESSAGE (message);
 452   for (i = 0; i < message->descriptor->n_fields; i++)
 453     {
 454       const ProtobufCFieldDescriptor *field = message->descriptor->fields + i;
 455       const void *member = ((const char *) message) + field->offset;
 456       const void *qmember = ((const char *) message) + field->quantifier_offset;
 457
 458       if (field->label == PROTOBUF_C_LABEL_REQUIRED)
 459         rv += required_field_get_packed_size (field, member);
 460       else if (field->label == PROTOBUF_C_LABEL_OPTIONAL)
 461         rv += optional_field_get_packed_size (field, qmember, member);
 462       else
 463         rv += repeated_field_get_packed_size (field, * (const size_t *) qmember, member);
 464     }
 465   for (i = 0; i < message->n_unknown_fields; i++)
 466     rv += unknown_field_get_packed_size (&message->unknown_fields[i]);
 467
 468   return rv;
 469 }
 470 /* === pack() === */
 471 /* Pack an unsigned 32-bit integer in base-128 encoding, and return the number of bytes needed:
 472    this will be 5 or less. */
 473 static inline size_t
 474 uint32_pack (uint32_t value, uint8_t *out)
 475 {
 476   unsigned rv = 0;
 477   if (value >= 0x80)
 478     {
 479       out[rv++] = value | 0x80;
 480       value >>= 7;
 481       if (value >= 0x80)
 482         {
 483           out[rv++] = value | 0x80;
 484           value >>= 7;
 485           if (value >= 0x80)
 486             {
 487               out[rv++] = value | 0x80;
 488               value >>= 7;
 489               if (value >= 0x80)
 490                 {
 491                   out[rv++] = value | 0x80;
 492                   value >>= 7;
 493                 }
 494             }
 495         }
 496     }
 497   /* assert: value<128 */
 498   out[rv++] = value;
 499   return rv;
 500 }
 501
 502 /* Pack a 32-bit signed integer, returning the number of bytes needed.
 503    Negative numbers are packed as twos-complement 64-bit integers. */
 504 static inline size_t
 505 int32_pack (int32_t value, uint8_t *out)
 506 {
 507   if (value < 0)
 508     {
 509       out[0] = value | 0x80;
 510       out[1] = (value>>7) | 0x80;
 511       out[2] = (value>>14) | 0x80;
 512       out[3] = (value>>21) | 0x80;
 513       out[4] = (value>>28) | 0x80;
 514       out[5] = out[6] = out[7] = out[8] = 0xff;
 515       out[9] = 0x01;
 516       return 10;
 517     }
 518   else
 519     return uint32_pack (value, out);
 520 }
 521
 522 /* Pack a 32-bit integer in zigwag encoding. */
 523 static inline size_t
 524 sint32_pack (int32_t value, uint8_t *out)
 525 {
 526   return uint32_pack (zigzag32 (value), out);
 527 }
 528
 529 /* Pack a 64-bit unsigned integer that fits in a 64-bit uint,
 530    using base-128 encoding. */
 531 static size_t
 532 uint64_pack (uint64_t value, uint8_t *out)
 533 {
 534   uint32_t hi = value>>32;
 535   uint32_t lo = value;
 536   unsigned rv;
 537   if (hi == 0)
 538     return uint32_pack ((uint32_t)lo, out);
 539   out[0] = (lo) | 0x80;
 540   out[1] = (lo>>7) | 0x80;
 541   out[2] = (lo>>14) | 0x80;
 542   out[3] = (lo>>21) | 0x80;
 543   if (hi < 8)
 544     {
 545       out[4] = (hi<<4) | (lo>>28);
 546       return 5;
 547     }
 548   else
 549     {
 550       out[4] = ((hi&7)<<4) | (lo>>28) | 0x80;
 551       hi >>= 3;
 552     }
 553   rv = 5;
 554   while (hi >= 128)
 555     {
 556       out[rv++] = hi | 0x80;
 557       hi >>= 7;
 558     }
 559   out[rv++] = hi;
 560   return rv;
 561 }
 562
 563 /* Pack a 64-bit signed integer in zigzan encoding,
 564    return the size of the packed output.
 565    (Max returned value is 10) */
 566 static inline size_t
 567 sint64_pack (int64_t value, uint8_t *out)
 568 {
 569   return uint64_pack (zigzag64 (value), out);
 570 }
 571
 572 /* Pack a 32-bit value, little-endian.
 573    Used for fixed32, sfixed32, float) */
 574 static inline size_t
 575 fixed32_pack (uint32_t value, uint8_t *out)
 576 {
 577 #if IS_LITTLE_ENDIAN
 578   memcpy (out, &value, 4);
 579 #else
 580   out[0] = value;
 581   out[1] = value>>8;
 582   out[2] = value>>16;
 583   out[3] = value>>24;
 584 #endif
 585   return 4;
 586 }
 587
 588 static inline size_t
 589 fixed64_pack (uint64_t value, uint8_t *out)
 590 {
 591 #if IS_LITTLE_ENDIAN
 592   memcpy (out, &value, 8);
 593 #else
 594   fixed32_pack (value, out);
 595   fixed32_pack (value>>32, out+4);
 596 #endif
 597   return 8;
 598 }
 599
 600 static inline size_t
 601 boolean_pack (protobuf_c_boolean value, uint8_t *out)
 602 {
 603   *out = value ? 1 : 0;
 604   return 1;
 605 }
 606
 607 static inline size_t
 608 string_pack (const char * str, uint8_t *out)
 609 {
 610   if (str == NULL)
 611     {
 612       out[0] = 0;
 613       return 1;
 614     }
 615   else
 616     {
 617       size_t len = strlen (str);
 618       size_t rv = uint32_pack (len, out);
 619       memcpy (out + rv, str, len);
 620       return rv + len;
 621     }
 622 }
 623
 624 static inline size_t
 625 binary_data_pack (const ProtobufCBinaryData *bd, uint8_t *out)
 626 {
 627   size_t len = bd->len;
 628   size_t rv = uint32_pack (len, out);
 629   memcpy (out + rv, bd->data, len);
 630   return rv + len;
 631 }
 632
 633 static inline size_t
 634 prefixed_message_pack (const ProtobufCMessage *message, uint8_t *out)
 635 {
 636   if (message == NULL)
 637     {
 638       out[0] = 0;
 639       return 1;
 640     }
 641   else
 642     {
 643       size_t rv = protobuf_c_message_pack (message, out + 1);
 644       uint32_t rv_packed_size = uint32_size (rv);
 645       if (rv_packed_size != 1)
 646         memmove (out + rv_packed_size, out + 1, rv);
 647       return uint32_pack (rv, out) + rv;
 648     }
 649 }
 650
 651 /* wire-type will be added in required_field_pack() */
 652 static size_t tag_pack (uint32_t id, uint8_t *out)
 653 {
 654   if (id < (1<<(32-3)))
 655     return uint32_pack (id<<3, out);
 656   else
 657     return uint64_pack (((uint64_t)id) << 3, out);
 658 }
 659 static size_t
 660 required_field_pack (const ProtobufCFieldDescriptor *field,
 661                      const void *member,
 662                      uint8_t *out)
 663 {
 664   size_t rv = tag_pack (field->id, out);
 665   switch (field->type)
 666     {
 667     case PROTOBUF_C_TYPE_SINT32:
 668       out[0] |= PROTOBUF_C_WIRE_TYPE_VARINT;
 669       return rv + sint32_pack (*(const int32_t *) member, out + rv);
 670     case PROTOBUF_C_TYPE_INT32:
 671       out[0] |= PROTOBUF_C_WIRE_TYPE_VARINT;
 672       return rv + int32_pack (*(const uint32_t *) member, out + rv);
 673     case PROTOBUF_C_TYPE_UINT32:
 674     case PROTOBUF_C_TYPE_ENUM:
 675       out[0] |= PROTOBUF_C_WIRE_TYPE_VARINT;
 676       return rv + uint32_pack (*(const uint32_t *) member, out + rv);
 677     case PROTOBUF_C_TYPE_SINT64:
 678       out[0] |= PROTOBUF_C_WIRE_TYPE_VARINT;
 679       return rv + sint64_pack (*(const int64_t *) member, out + rv);
 680     case PROTOBUF_C_TYPE_INT64:
 681     case PROTOBUF_C_TYPE_UINT64:
 682       out[0] |= PROTOBUF_C_WIRE_TYPE_VARINT;
 683       return rv + uint64_pack (*(const uint64_t *) member, out + rv);
 684     case PROTOBUF_C_TYPE_SFIXED32:
 685     case PROTOBUF_C_TYPE_FIXED32:
 686     case PROTOBUF_C_TYPE_FLOAT:
 687       out[0] |= PROTOBUF_C_WIRE_TYPE_32BIT;
 688       return rv + fixed32_pack (*(const uint64_t *) member, out + rv);
 689     case PROTOBUF_C_TYPE_SFIXED64:
 690     case PROTOBUF_C_TYPE_FIXED64:
 691     case PROTOBUF_C_TYPE_DOUBLE:
 692       out[0] |= PROTOBUF_C_WIRE_TYPE_64BIT;
 693       return rv + fixed64_pack (*(const uint64_t *) member, out + rv);
 694     case PROTOBUF_C_TYPE_BOOL:
 695       out[0] |= PROTOBUF_C_WIRE_TYPE_VARINT;
 696       return rv + boolean_pack (*(const protobuf_c_boolean *) member, out + rv);
 697     case PROTOBUF_C_TYPE_STRING:
 698       {
 699         out[0] |= PROTOBUF_C_WIRE_TYPE_LENGTH_PREFIXED;
 700         return rv + string_pack (*(char * const *) member, out + rv);
 701       }
 702
 703     case PROTOBUF_C_TYPE_BYTES:
 704       {
 705         const ProtobufCBinaryData * bd = ((const ProtobufCBinaryData*) member);
 706         out[0] |= PROTOBUF_C_WIRE_TYPE_LENGTH_PREFIXED;
 707         return rv + binary_data_pack (bd, out + rv);
 708       }
 709     //case PROTOBUF_C_TYPE_GROUP:          // NOT SUPPORTED
 710     case PROTOBUF_C_TYPE_MESSAGE:
 711       {
 712         out[0] |= PROTOBUF_C_WIRE_TYPE_LENGTH_PREFIXED;
 713         return rv + prefixed_message_pack (*(ProtobufCMessage * const *) member,
 714                                            out + rv);
 715       }
 716     }
 717   PROTOBUF_C_ASSERT_NOT_REACHED ();
 718   return 0;
 719 }
 720 static size_t
 721 optional_field_pack (const ProtobufCFieldDescriptor *field,
 722                      const protobuf_c_boolean *has,
 723                      const void *member,
 724                      uint8_t *out)
 725 {
 726   if (field->type == PROTOBUF_C_TYPE_MESSAGE
 727    || field->type == PROTOBUF_C_TYPE_STRING)
 728     {
 729       const void *ptr = * (const void * const *) member;
 730       if (ptr == NULL
 731        || ptr == field->default_value)
 732         return 0;
 733     }
 734   else
 735     {
 736       if (!*has)
 737         return 0;
 738     }
 739   return required_field_pack (field, member, out);
 740 }
 741
 742 /* TODO: implement as a table lookup */
 743 static inline size_t sizeof_elt_in_repeated_array (ProtobufCType type)
 744 {
 745   switch (type)
 746     {
 747     case PROTOBUF_C_TYPE_SINT32:
 748     case PROTOBUF_C_TYPE_INT32:
 749     case PROTOBUF_C_TYPE_UINT32:
 750     case PROTOBUF_C_TYPE_SFIXED32:
 751     case PROTOBUF_C_TYPE_FIXED32:
 752     case PROTOBUF_C_TYPE_FLOAT:
 753     case PROTOBUF_C_TYPE_ENUM:
 754       return 4;
 755     case PROTOBUF_C_TYPE_SINT64:
 756     case PROTOBUF_C_TYPE_INT64:
 757     case PROTOBUF_C_TYPE_UINT64:
 758     case PROTOBUF_C_TYPE_SFIXED64:
 759     case PROTOBUF_C_TYPE_FIXED64:
 760     case PROTOBUF_C_TYPE_DOUBLE:
 761       return 8;
 762     case PROTOBUF_C_TYPE_BOOL:
 763       return sizeof (protobuf_c_boolean);
 764     case PROTOBUF_C_TYPE_STRING:
 765     case PROTOBUF_C_TYPE_MESSAGE:
 766       return sizeof (void *);
 767     case PROTOBUF_C_TYPE_BYTES:
 768       return sizeof (ProtobufCBinaryData);
 769     }
 770   PROTOBUF_C_ASSERT_NOT_REACHED ();
 771   return 0;
 772 }
 773 static size_t
 774 repeated_field_pack (const ProtobufCFieldDescriptor *field,
 775                      size_t count,
 776                      const void *member,
 777                      uint8_t *out)
 778 {
 779   char *array = * (char * const *) member;
 780   size_t siz;
 781   unsigned i;
 782   size_t rv = 0;
 783   /* CONSIDER: optimize this case a bit (by putting the loop inside the switch) */
 784   siz = sizeof_elt_in_repeated_array (field->type);
 785   for (i = 0; i < count; i++)
 786     {
 787       rv += required_field_pack (field, array, out + rv);
 788       array += siz;
 789     }
 790   return rv;
 791 }
 792 static size_t
 793 unknown_field_pack (const ProtobufCMessageUnknownField *field, uint8_t *out)
 794 {
 795   size_t rv = tag_pack (field->tag, out);
 796   out[0] |= field->wire_type;
 797   memcpy (out + rv, field->data, field->len);
 798   return rv + field->len;
 799 }
 800
 801 size_t    protobuf_c_message_pack           (const ProtobufCMessage *message,
 802                                              uint8_t                *out)
 803 {
 804   unsigned i;
 805   size_t rv = 0;
 806   ASSERT_IS_MESSAGE (message);
 807   for (i = 0; i < message->descriptor->n_fields; i++)
 808     {
 809       const ProtobufCFieldDescriptor *field = message->descriptor->fields + i;
 810       const void *member = ((const char *) message) + field->offset;
 811       const void *qmember = ((const char *) message) + field->quantifier_offset;
 812
 813       if (field->label == PROTOBUF_C_LABEL_REQUIRED)
 814         rv += required_field_pack (field, member, out + rv);
 815       else if (field->label == PROTOBUF_C_LABEL_OPTIONAL)
 816         rv += optional_field_pack (field, qmember, member, out + rv);
 817       else
 818         rv += repeated_field_pack (field, * (const size_t *) qmember, member, out + rv);
 819     }
 820   for (i = 0; i < message->n_unknown_fields; i++)
 821     rv += unknown_field_pack (&message->unknown_fields[i], out + rv);
 822   return rv;
 823 }
 824
 825 /* === pack_to_buffer() === */
 826 static size_t
 827 required_field_pack_to_buffer (const ProtobufCFieldDescriptor *field,
 828                                const void *member,
 829                                ProtobufCBuffer *buffer)
 830 {
 831   size_t rv;
 832   uint8_t scratch[MAX_UINT64_ENCODED_SIZE * 2];
 833   rv = tag_pack (field->id, scratch);
 834   switch (field->type)
 835     {
 836     case PROTOBUF_C_TYPE_SINT32:
 837       scratch[0] |= PROTOBUF_C_WIRE_TYPE_VARINT;
 838       rv += sint32_pack (*(const int32_t *) member, scratch + rv);
 839       buffer->append (buffer, rv, scratch);
 840       break;
 841     case PROTOBUF_C_TYPE_INT32:
 842       scratch[0] |= PROTOBUF_C_WIRE_TYPE_VARINT;
 843       rv += int32_pack (*(const uint32_t *) member, scratch + rv);
 844       buffer->append (buffer, rv, scratch);
 845       break;
 846     case PROTOBUF_C_TYPE_UINT32:
 847     case PROTOBUF_C_TYPE_ENUM:
 848       scratch[0] |= PROTOBUF_C_WIRE_TYPE_VARINT;
 849       rv += uint32_pack (*(const uint32_t *) member, scratch + rv);
 850       buffer->append (buffer, rv, scratch);
 851       break;
 852     case PROTOBUF_C_TYPE_SINT64:
 853       scratch[0] |= PROTOBUF_C_WIRE_TYPE_VARINT;
 854       rv += sint64_pack (*(const int64_t *) member, scratch + rv);
 855       buffer->append (buffer, rv, scratch);
 856       break;
 857     case PROTOBUF_C_TYPE_INT64:
 858     case PROTOBUF_C_TYPE_UINT64:
 859       scratch[0] |= PROTOBUF_C_WIRE_TYPE_VARINT;
 860       rv += uint64_pack (*(const uint64_t *) member, scratch + rv);
 861       buffer->append (buffer, rv, scratch);
 862       break;
 863     case PROTOBUF_C_TYPE_SFIXED32:
 864     case PROTOBUF_C_TYPE_FIXED32:
 865     case PROTOBUF_C_TYPE_FLOAT:
 866       scratch[0] |= PROTOBUF_C_WIRE_TYPE_32BIT;
 867       rv += fixed32_pack (*(const uint64_t *) member, scratch + rv);
 868       buffer->append (buffer, rv, scratch);
 869       break;
 870     case PROTOBUF_C_TYPE_SFIXED64:
 871     case PROTOBUF_C_TYPE_FIXED64:
 872     case PROTOBUF_C_TYPE_DOUBLE:
 873       scratch[0] |= PROTOBUF_C_WIRE_TYPE_64BIT;
 874       rv += fixed64_pack (*(const uint64_t *) member, scratch + rv);
 875       buffer->append (buffer, rv, scratch);
 876       break;
 877     case PROTOBUF_C_TYPE_BOOL:
 878       scratch[0] |= PROTOBUF_C_WIRE_TYPE_VARINT;
 879       rv += boolean_pack (*(const protobuf_c_boolean *) member, scratch + rv);
 880       buffer->append (buffer, rv, scratch);
 881       break;
 882     case PROTOBUF_C_TYPE_STRING:
 883       {
 884         const char *str = *(char * const *) member;
 885         size_t sublen = str ? strlen (str) : 0;
 886         scratch[0] |= PROTOBUF_C_WIRE_TYPE_LENGTH_PREFIXED;
 887         rv += uint32_pack (sublen, scratch + rv);
 888         buffer->append (buffer, rv, scratch);
 889         buffer->append (buffer, sublen, (const uint8_t *) str);
 890         rv += sublen;
 891         break;
 892       }
 893
 894     case PROTOBUF_C_TYPE_BYTES:
 895       {
 896         const ProtobufCBinaryData * bd = ((const ProtobufCBinaryData*) member);
 897         size_t sublen = bd->len;
 898         scratch[0] |= PROTOBUF_C_WIRE_TYPE_LENGTH_PREFIXED;
 899         rv += uint32_pack (sublen, scratch + rv);
 900         buffer->append (buffer, rv, scratch);
 901         buffer->append (buffer, sublen, bd->data);
 902         rv += sublen;
 903         break;
 904       }
 905     //PROTOBUF_C_TYPE_GROUP,          // NOT SUPPORTED
 906     case PROTOBUF_C_TYPE_MESSAGE:
 907       {
 908         uint8_t simple_buffer_scratch[256];
 909         size_t sublen;
 910         ProtobufCBufferSimple simple_buffer
 911           = PROTOBUF_C_BUFFER_SIMPLE_INIT (simple_buffer_scratch);
 912         const ProtobufCMessage *msg = *(ProtobufCMessage * const *) member;
 913         scratch[0] |= PROTOBUF_C_WIRE_TYPE_LENGTH_PREFIXED;
 914         if (msg == NULL)
 915           sublen = 0;
 916         else
 917           sublen = protobuf_c_message_pack_to_buffer (msg, &simple_buffer.base);
 918         rv += uint32_pack (sublen, scratch + rv);
 919         buffer->append (buffer, rv, scratch);
 920         buffer->append (buffer, sublen, simple_buffer.data);
 921         rv += sublen;
 922         PROTOBUF_C_BUFFER_SIMPLE_CLEAR (&simple_buffer);
 923         break;
 924       }
 925     default:
 926       PROTOBUF_C_ASSERT_NOT_REACHED ();
 927     }
 928   return rv;
 929 }
 930 static size_t
 931 optional_field_pack_to_buffer (const ProtobufCFieldDescriptor *field,
 932                                const protobuf_c_boolean *has,
 933                                const void *member,
 934                                ProtobufCBuffer *buffer)
 935 {
 936   if (field->type == PROTOBUF_C_TYPE_MESSAGE
 937    || field->type == PROTOBUF_C_TYPE_STRING)
 938     {
 939       const void *ptr = * (const void * const *) member;
 940       if (ptr == NULL
 941        || ptr == field->default_value)
 942         return 0;
 943     }
 944   else
 945     {
 946       if (!*has)
 947         return 0;
 948     }
 949   return required_field_pack_to_buffer (field, member, buffer);
 950 }
 951
 952 static size_t
 953 repeated_field_pack_to_buffer (const ProtobufCFieldDescriptor *field,
 954                                unsigned count,
 955                                const void *member,
 956                                ProtobufCBuffer *buffer)
 957 {
 958   char *array = * (char * const *) member;
 959   size_t siz;
 960   unsigned i;
 961   /* CONSIDER: optimize this case a bit (by putting the loop inside the switch) */
 962   unsigned rv = 0;
 963   siz = sizeof_elt_in_repeated_array (field->type);
 964   for (i = 0; i < count; i++)
 965     {
 966       rv += required_field_pack_to_buffer (field, array, buffer);
 967       array += siz;
 968     }
 969   return rv;
 970 }
 971
 972 static size_t
 973 unknown_field_pack_to_buffer (const ProtobufCMessageUnknownField *field,
 974                               ProtobufCBuffer *buffer)
 975 {
 976   uint8_t header[MAX_UINT64_ENCODED_SIZE];
 977   size_t rv = tag_pack (field->tag, header);
 978   header[0] |= field->wire_type;
 979   buffer->append (buffer, rv, header);
 980   buffer->append (buffer, field->len, field->data);
 981   return rv + field->len;
 982 }
 983
 984 size_t
 985 protobuf_c_message_pack_to_buffer (const ProtobufCMessage *message,
 986                                    ProtobufCBuffer  *buffer)
 987 {
 988   unsigned i;
 989   size_t rv = 0;
 990   ASSERT_IS_MESSAGE (message);
 991   for (i = 0; i < message->descriptor->n_fields; i++)
 992     {
 993       const ProtobufCFieldDescriptor *field = message->descriptor->fields + i;
 994       const void *member = ((const char *) message) + field->offset;
 995       const void *qmember = ((const char *) message) + field->quantifier_offset;
 996
 997       if (field->label == PROTOBUF_C_LABEL_REQUIRED)
 998         rv += required_field_pack_to_buffer (field, member, buffer);
 999       else if (field->label == PROTOBUF_C_LABEL_OPTIONAL)
1000         rv += optional_field_pack_to_buffer (field, qmember, member, buffer);
1001       else
1002         rv += repeated_field_pack_to_buffer (field, * (const size_t *) qmember, member, buffer);
1003     }
1004   for (i = 0; i < message->n_unknown_fields; i++)
1005     rv += unknown_field_pack_to_buffer (&message->unknown_fields[i], buffer);
1006
1007   return rv;
1008 }
1009
1010 /* === unpacking === */
1011 #if PRINT_UNPACK_ERRORS
1012 # define UNPACK_ERROR(args)  do { printf args;printf("\n"); }while(0)
1013 #else
1014 # define UNPACK_ERROR(args)  do { } while (0)
1015 #endif
1016
1017 static inline int
1018 int_range_lookup (unsigned n_ranges,
1019                   const ProtobufCIntRange *ranges,
1020                   int value)
1021 {
1022   unsigned start, n;
1023   if (n_ranges == 0)
1024     return -1;
1025   start = 0;
1026   n = n_ranges;
1027   while (n > 1)
1028     {
1029       unsigned mid = start + n / 2;
1030       if (value < ranges[mid].start_value)
1031         {
1032           n = mid - start;
1033         }
1034       else if (value >= ranges[mid].start_value + (int)(ranges[mid+1].orig_index-ranges[mid].orig_index))
1035         {
1036           unsigned new_start = mid + 1;
1037           n = start + n - new_start;
1038           start = new_start;
1039         }
1040       else
1041         return (value - ranges[mid].start_value) + ranges[mid].orig_index;
1042     }
1043   if (n > 0)
1044     {
1045       unsigned start_orig_index = ranges[start].orig_index;
1046       unsigned range_size = ranges[start+1].orig_index - start_orig_index;
1047
1048       if (ranges[start].start_value <= value
1049        && value < (int)(ranges[start].start_value + range_size))
1050         return (value - ranges[start].start_value) + start_orig_index;
1051     }
1052   return -1;
1053 }
1054
1055 static size_t
1056 parse_tag_and_wiretype (size_t len,
1057                         const uint8_t *data,
1058                         uint32_t *tag_out,
1059                         ProtobufCWireType *wiretype_out)
1060 {
1061   unsigned max_rv = len > 5 ? 5 : len;
1062   uint32_t tag = (data[0]&0x7f) >> 3;
1063   unsigned shift = 4;
1064   unsigned rv;
1065   *wiretype_out = data[0] & 7;
1066   if ((data[0] & 0x80) == 0)
1067     {
1068       *tag_out = tag;
1069       return 1;
1070     }
1071   for (rv = 1; rv < max_rv; rv++)
1072     if (data[rv] & 0x80)
1073       {
1074         tag |= (data[rv] & 0x7f) << shift;
1075         shift += 7;
1076       }
1077     else
1078       {
1079         tag |= data[rv] << shift;
1080         *tag_out = tag;
1081         return rv + 1;
1082       }
1083   return 0;                   /* error: bad header */
1084 }
1085
1086 /* sizeof(ScannedMember) must be <= (1<<BOUND_SIZEOF_SCANNED_MEMBER_LOG2) */
1087 #define BOUND_SIZEOF_SCANNED_MEMBER_LOG2  5
1088 typedef struct _ScannedMember ScannedMember;
1089 struct _ScannedMember
1090 {
1091   uint32_t tag;
1092   uint8_t wire_type;
1093   uint8_t length_prefix_len;
1094   const ProtobufCFieldDescriptor *field;
1095   size_t len;
1096   const uint8_t *data;
1097 };
1098
1099 #define MESSAGE_GET_UNKNOWNS(message) \
1100   STRUCT_MEMBER_PTR (ProtobufCMessageUnknownFieldArray, \
1101                      (message), (message)->descriptor->unknown_field_array_offset)
1102
1103 static inline uint32_t
1104 scan_length_prefixed_data (size_t len, const uint8_t *data, size_t *prefix_len_out)
1105 {
1106   unsigned hdr_max = len < 5 ? len : 5;
1107   unsigned hdr_len;
1108   uint32_t val = 0;
1109   unsigned i;
1110   unsigned shift = 0;
1111   for (i = 0; i < hdr_max; i++)
1112     {
1113       val |= (data[i] & 0x7f) << shift;
1114       shift += 7;
1115       if ((data[i] & 0x80) == 0)
1116         break;
1117     }
1118   if (i == hdr_max)
1119     {
1120       UNPACK_ERROR (("error parsing length for length-prefixed data"));
1121       return 0;
1122     }
1123   hdr_len = i + 1;
1124   *prefix_len_out = hdr_len;
1125   if (hdr_len + val > len)
1126     {
1127       UNPACK_ERROR (("data too short after length-prefix of %u",
1128                      val));
1129       return 0;
1130     }
1131   return hdr_len + val;
1132 }
1133
1134 static inline uint32_t
1135 parse_uint32 (unsigned len, const uint8_t *data)
1136 {
1137   unsigned rv = data[0] & 0x7f;
1138   if (len > 1)
1139     {
1140       rv |= ((data[1] & 0x7f) << 7);
1141       if (len > 2)
1142         {
1143           rv |= ((data[2] & 0x7f) << 14);
1144           if (len > 3)
1145             {
1146               rv |= ((data[3] & 0x7f) << 21);
1147               if (len > 4)
1148                 rv |= (data[4] << 28);
1149             }
1150         }
1151     }
1152   return rv;
1153 }
1154 static inline uint32_t
1155 parse_int32 (unsigned len, const uint8_t *data)
1156 {
1157   return parse_uint32 (len, data);
1158 }
1159 static inline int32_t
1160 unzigzag32 (uint32_t v)
1161 {
1162   if (v&1)
1163     return -(v>>1) - 1;
1164   else
1165     return v>>1;
1166 }
1167 static inline uint32_t
1168 parse_fixed_uint32 (const uint8_t *data)
1169 {
1170 #if IS_LITTLE_ENDIAN
1171   uint32_t t;
1172   memcpy (&t, data, 4);
1173   return t;
1174 #else
1175   return data[0] | (data[1] << 8) | (data[2] << 16) | (data[3] << 24);
1176 #endif
1177 }
1178 static uint64_t
1179 parse_uint64 (unsigned len, const uint8_t *data)
1180 {
1181   unsigned shift, i;
1182   if (len < 5)
1183     return parse_uint32 (len, data);
1184   uint64_t rv = ((data[0] & 0x7f))
1185               | ((data[1] & 0x7f)<<7)
1186               | ((data[2] & 0x7f)<<14)
1187               | ((data[3] & 0x7f)<<21);
1188   shift = 28;
1189   for (i = 4; i < len; i++)
1190     {
1191       rv |= (((uint64_t)(data[i]&0x7f)) << shift);
1192       shift += 7;
1193     }
1194   return rv;
1195 }
1196 static inline int64_t
1197 unzigzag64 (uint64_t v)
1198 {
1199   if (v&1)
1200     return -(v>>1) - 1;
1201   else
1202     return v>>1;
1203 }
1204 static inline uint64_t
1205 parse_fixed_uint64 (const uint8_t *data)
1206 {
1207 #if IS_LITTLE_ENDIAN
1208   uint64_t t;
1209   memcpy (&t, data, 8);
1210   return t;
1211 #else
1212   return (uint64_t)parse_fixed_uint32 (data)
1213       | (((uint64_t)parse_fixed_uint32(data+4)) << 32);
1214 #endif
1215 }
1216 static protobuf_c_boolean
1217 parse_boolean (unsigned len, const uint8_t *data)
1218 {
1219   unsigned i;
1220   for (i = 0; i < len; i++)
1221     if (data[i] & 0x7f)
1222       return 1;
1223   return 0;
1224 }
1225 static protobuf_c_boolean
1226 parse_required_member (ScannedMember *scanned_member,
1227                        void *member,
1228                        ProtobufCAllocator *allocator,
1229                        protobuf_c_boolean maybe_clear)
1230 {
1231   unsigned len = scanned_member->len;
1232   const uint8_t *data = scanned_member->data;
1233   ProtobufCWireType wire_type = scanned_member->wire_type;
1234   switch (scanned_member->field->type)
1235     {
1236     case PROTOBUF_C_TYPE_INT32:
1237       if (wire_type != PROTOBUF_C_WIRE_TYPE_VARINT)
1238         return 0;
1239       *(uint32_t*)member = parse_int32 (len, data);
1240       return 1;
1241     case PROTOBUF_C_TYPE_UINT32:
1242       if (wire_type != PROTOBUF_C_WIRE_TYPE_VARINT)
1243         return 0;
1244       *(uint32_t*)member = parse_uint32 (len, data);
1245       return 1;
1246     case PROTOBUF_C_TYPE_SINT32:
1247       if (wire_type != PROTOBUF_C_WIRE_TYPE_VARINT)
1248         return 0;
1249       *(int32_t*)member = unzigzag32 (parse_uint32 (len, data));
1250       return 1;
1251     case PROTOBUF_C_TYPE_SFIXED32:
1252     case PROTOBUF_C_TYPE_FIXED32:
1253     case PROTOBUF_C_TYPE_FLOAT:
1254       if (wire_type != PROTOBUF_C_WIRE_TYPE_32BIT)
1255         return 0;
1256       *(uint32_t*)member = parse_fixed_uint32 (data);
1257       return 1;
1258
1259     case PROTOBUF_C_TYPE_INT64:
1260     case PROTOBUF_C_TYPE_UINT64:
1261       if (wire_type != PROTOBUF_C_WIRE_TYPE_VARINT)
1262         return 0;
1263       *(uint64_t*)member = parse_uint64 (len, data);
1264       return 1;
1265     case PROTOBUF_C_TYPE_SINT64:
1266       if (wire_type != PROTOBUF_C_WIRE_TYPE_VARINT)
1267         return 0;
1268       *(int64_t*)member = unzigzag64 (parse_uint64 (len, data));
1269       return 1;
1270     case PROTOBUF_C_TYPE_SFIXED64:
1271     case PROTOBUF_C_TYPE_FIXED64:
1272     case PROTOBUF_C_TYPE_DOUBLE:
1273       if (wire_type != PROTOBUF_C_WIRE_TYPE_64BIT)
1274         return 0;
1275       *(uint64_t*)member = parse_fixed_uint64 (data);
1276       return 1;
1277
1278     case PROTOBUF_C_TYPE_BOOL:
1279       *(protobuf_c_boolean*)member = parse_boolean (len, data);
1280       return 1;
1281
1282     case PROTOBUF_C_TYPE_ENUM:
1283       if (wire_type != PROTOBUF_C_WIRE_TYPE_VARINT)
1284         return 0;
1285       *(uint32_t*)member = parse_uint32 (len, data);
1286       return 1;
1287
1288     case PROTOBUF_C_TYPE_STRING:
1289       if (wire_type != PROTOBUF_C_WIRE_TYPE_LENGTH_PREFIXED)
1290         return 0;
1291       {
1292         char **pstr = member;
1293         unsigned pref_len = scanned_member->length_prefix_len;
1294         if (maybe_clear && *pstr != NULL)
1295           {
1296             const char *def = scanned_member->field->default_value;
1297             if (*pstr != NULL && *pstr != def)
1298               FREE (allocator, *pstr);
1299           }
1300         DO_ALLOC (*pstr, allocator, len - pref_len + 1, return 0);
1301         memcpy (*pstr, data + pref_len, len - pref_len);
1302         (*pstr)[len-pref_len] = 0;
1303         return 1;
1304       }
1305     case PROTOBUF_C_TYPE_BYTES:
1306       if (wire_type != PROTOBUF_C_WIRE_TYPE_LENGTH_PREFIXED)
1307         return 0;
1308       {
1309         ProtobufCBinaryData *bd = member;
1310         const ProtobufCBinaryData *def_bd;
1311         unsigned pref_len = scanned_member->length_prefix_len;
1312         def_bd = scanned_member->field->default_value;
1313         if (maybe_clear && bd->data != NULL && bd->data != def_bd->data)
1314           FREE (allocator, bd->data);
1315         DO_ALLOC (bd->data, allocator, len - pref_len, return 0);
1316         memcpy (bd->data, data + pref_len, len - pref_len);
1317         bd->len = len - pref_len;
1318         return 1;
1319       }
1320     //case PROTOBUF_C_TYPE_GROUP,          // NOT SUPPORTED
1321     case PROTOBUF_C_TYPE_MESSAGE:
1322       if (wire_type != PROTOBUF_C_WIRE_TYPE_LENGTH_PREFIXED)
1323         return 0;
1324       {
1325         ProtobufCMessage **pmessage = member;
1326         ProtobufCMessage *subm;
1327         const ProtobufCMessage *def_mess;
1328         unsigned pref_len = scanned_member->length_prefix_len;
1329         def_mess = scanned_member->field->default_value;
1330         if (maybe_clear && *pmessage != NULL && *pmessage != def_mess)
1331           protobuf_c_message_free_unpacked (*pmessage, allocator);
1332         subm = protobuf_c_message_unpack (scanned_member->field->descriptor,
1333                                           allocator,
1334                                           len - pref_len, data + pref_len);
1335         *pmessage = subm;       /* since we freed the message we must clear the field, even if NULL */
1336         if (subm == NULL)
1337           return 0;
1338         return 1;
1339       }
1340     }
1341   return 0;
1342 }
1343
1344 static protobuf_c_boolean
1345 parse_optional_member (ScannedMember *scanned_member,
1346                        void *member,
1347                        ProtobufCMessage *message,
1348                        ProtobufCAllocator *allocator)
1349 {
1350   if (!parse_required_member (scanned_member, member, allocator, TRUE))
1351     return 0;
1352   if (scanned_member->field->quantifier_offset != 0)
1353     STRUCT_MEMBER (protobuf_c_boolean,
1354                    message,
1355                    scanned_member->field->quantifier_offset) = 1;
1356   return 1;
1357 }
1358
1359 static protobuf_c_boolean
1360 parse_repeated_member (ScannedMember *scanned_member,
1361                        void *member,
1362                        ProtobufCMessage *message,
1363                        ProtobufCAllocator *allocator)
1364 {
1365   const ProtobufCFieldDescriptor *field = scanned_member->field;
1366   size_t *p_n = STRUCT_MEMBER_PTR(size_t, message, field->quantifier_offset);
1367   size_t siz = sizeof_elt_in_repeated_array (field->type);
1368   char *array = *(char**)member;
1369   if (!parse_required_member (scanned_member,
1370                               array + siz * (*p_n),
1371                               allocator,
1372                               FALSE))
1373     return 0;
1374   *p_n += 1;
1375   return 1;
1376 }
1377
1378 static protobuf_c_boolean
1379 parse_member (ScannedMember *scanned_member,
1380               ProtobufCMessage *message,
1381               ProtobufCAllocator *allocator)
1382 {
1383   const ProtobufCFieldDescriptor *field = scanned_member->field;
1384   void *member;
1385   if (field == NULL)
1386     {
1387       ProtobufCMessageUnknownField *ufield = message->unknown_fields + (message->n_unknown_fields++);
1388       ufield->tag = scanned_member->tag;
1389       ufield->wire_type = scanned_member->wire_type;
1390       ufield->len = scanned_member->len;
1391       DO_UNALIGNED_ALLOC (ufield->data, allocator, scanned_member->len, return 0);
1392       memcpy (ufield->data, scanned_member->data, ufield->len);
1393       return 1;
1394     }
1395   member = (char*)message + field->offset;
1396   switch (field->label)
1397     {
1398     case PROTOBUF_C_LABEL_REQUIRED:
1399       return parse_required_member (scanned_member, member, allocator, TRUE);
1400     case PROTOBUF_C_LABEL_OPTIONAL:
1401       return parse_optional_member (scanned_member, member, message, allocator);
1402     case PROTOBUF_C_LABEL_REPEATED:
1403       return parse_repeated_member (scanned_member, member, message, allocator);
1404     }
1405   PROTOBUF_C_ASSERT_NOT_REACHED ();
1406   return 0;
1407 }
1408
1409 static inline void
1410 setup_default_values (ProtobufCMessage *message)
1411 {
1412   const ProtobufCMessageDescriptor *desc = message->descriptor;
1413   unsigned i;
1414   for (i = 0; i < desc->n_fields; i++)
1415     if (desc->fields[i].default_value != NULL
1416      && desc->fields[i].label != PROTOBUF_C_LABEL_REPEATED)
1417       {
1418         void *field = STRUCT_MEMBER_P (message, desc->fields[i].offset);
1419         const void *dv = desc->fields[i].default_value;
1420         switch (desc->fields[i].type)
1421         {
1422         case PROTOBUF_C_TYPE_INT32:
1423         case PROTOBUF_C_TYPE_SINT32:
1424         case PROTOBUF_C_TYPE_SFIXED32:
1425         case PROTOBUF_C_TYPE_UINT32:
1426         case PROTOBUF_C_TYPE_FIXED32:
1427         case PROTOBUF_C_TYPE_FLOAT:
1428         case PROTOBUF_C_TYPE_ENUM:
1429           memcpy (field, dv, 4);
1430           break;
1431
1432         case PROTOBUF_C_TYPE_INT64:
1433         case PROTOBUF_C_TYPE_SINT64:
1434         case PROTOBUF_C_TYPE_SFIXED64:
1435         case PROTOBUF_C_TYPE_UINT64:
1436         case PROTOBUF_C_TYPE_FIXED64:
1437         case PROTOBUF_C_TYPE_DOUBLE:
1438           memcpy (field, dv, 8);
1439           break;
1440
1441         case PROTOBUF_C_TYPE_BOOL:
1442           memcpy (field, dv, sizeof (protobuf_c_boolean));
1443           break;
1444
1445         case PROTOBUF_C_TYPE_BYTES:
1446           memcpy (field, dv, sizeof (ProtobufCBinaryData));
1447           break;
1448
1449         case PROTOBUF_C_TYPE_STRING:
1450         case PROTOBUF_C_TYPE_MESSAGE:
1451           /* the next line essentially implements a cast from const,
1452              which is totally unavoidable. */
1453           *(const void**)field = dv;
1454           break;
1455         }
1456       }
1457 }
1458
1459 /* ScannedMember slabs (an unpacking implementation detail).
1460    Before doing real unpacking, we first scan through the
1461    elements to see how many there are (for repeated fields),
1462    and which field to use (for non-repeated fields given twice).
1463
1464  * In order to avoid allocations for small messages,
1465    we keep a stack-allocated slab of ScannedMembers of
1466    size FIRST_SCANNED_MEMBER_SLAB_SIZE (16).
1467    After we fill that up, we allocate each slab twice
1468    as large as the previous one. */
1469 #define FIRST_SCANNED_MEMBER_SLAB_SIZE_LOG2             4
1470
1471 /* The number of slabs, including the stack-allocated ones;
1472    choose the number so that we would overflow if we needed
1473    a slab larger than provided. */
1474 #define MAX_SCANNED_MEMBER_SLAB                          \
1475   (sizeof(void*)*8 - 1                                   \
1476    - BOUND_SIZEOF_SCANNED_MEMBER_LOG2                    \
1477    - FIRST_SCANNED_MEMBER_SLAB_SIZE_LOG2)
1478
1479 ProtobufCMessage *
1480 protobuf_c_message_unpack         (const ProtobufCMessageDescriptor *desc,
1481                                    ProtobufCAllocator  *allocator,
1482                                    size_t               len,
1483                                    const uint8_t       *data)
1484 {
1485   ProtobufCMessage *rv;
1486   size_t rem = len;
1487   const uint8_t *at = data;
1488   const ProtobufCFieldDescriptor *last_field = desc->fields + 0;
1489   ScannedMember first_member_slab[1<<FIRST_SCANNED_MEMBER_SLAB_SIZE_LOG2];
1490
1491   /* scanned_member_slabs[i] is an array of arrays of ScannedMember.
1492      The first slab (scanned_member_slabs[0] is just a pointer to
1493      first_member_slab), above.  All subsequent slabs will be allocated
1494      using the allocator. */
1495   ScannedMember *scanned_member_slabs[MAX_SCANNED_MEMBER_SLAB+1];
1496   unsigned which_slab = 0;       /* the slab we are currently populating */
1497   unsigned in_slab_index = 0;    /* number of members in the slab */
1498   size_t n_unknown = 0;
1499   unsigned f;
1500   unsigned i_slab;
1501
1502   ASSERT_IS_MESSAGE_DESCRIPTOR (desc);
1503
1504   if (allocator == NULL)
1505     allocator = &protobuf_c_default_allocator;
1506   DO_ALLOC (rv, allocator, desc->sizeof_message, return NULL);
1507   scanned_member_slabs[0] = first_member_slab;
1508
1509   memset (rv, 0, desc->sizeof_message);
1510   rv->descriptor = desc;
1511
1512   setup_default_values (rv);
1513
1514   while (rem > 0)
1515     {
1516       uint32_t tag;
1517       ProtobufCWireType wire_type;
1518       size_t used = parse_tag_and_wiretype (rem, at, &tag, &wire_type);
1519       const ProtobufCFieldDescriptor *field;
1520       ScannedMember tmp;
1521       if (used == 0)
1522         {
1523           UNPACK_ERROR (("error parsing tag/wiretype at offset %u",
1524                          (unsigned)(at-data)));
1525           goto error_cleanup_during_scan;
1526         }
1527       /* XXX: consider optimizing for field[1].id == tag, if field[1] exists! */
1528       if (last_field->id != tag)
1529         {
1530           /* lookup field */
1531           int field_index = int_range_lookup (desc->n_field_ranges,
1532                                               desc->field_ranges,
1533                                               tag);
1534           if (field_index < 0)
1535             {
1536               field = NULL;
1537               n_unknown++;
1538             }
1539           else
1540             {
1541               field = desc->fields + field_index;
1542               last_field = field;
1543             }
1544         }
1545       else
1546         field = last_field;
1547
1548       at += used;
1549       rem -= used;
1550       tmp.tag = tag;
1551       tmp.wire_type = wire_type;
1552       tmp.field = field;
1553       tmp.data = at;
1554       switch (wire_type)
1555         {
1556         case PROTOBUF_C_WIRE_TYPE_VARINT:
1557           {
1558             unsigned max_len = rem < 10 ? rem : 10;
1559             unsigned i;
1560             for (i = 0; i < max_len; i++)
1561               if ((at[i] & 0x80) == 0)
1562                 break;
1563             if (i == max_len)
1564               {
1565                 UNPACK_ERROR (("unterminated varint at offset %u",
1566                                (unsigned)(at-data)));
1567                 goto error_cleanup_during_scan;
1568               }
1569             tmp.len = i + 1;
1570           }
1571           break;
1572         case PROTOBUF_C_WIRE_TYPE_64BIT:
1573           if (rem < 8)
1574             {
1575               UNPACK_ERROR (("too short after 64bit wiretype at offset %u",
1576                              (unsigned)(at-data)));
1577               goto error_cleanup_during_scan;
1578             }
1579           tmp.len = 8;
1580           break;
1581         case PROTOBUF_C_WIRE_TYPE_LENGTH_PREFIXED:
1582           {
1583             size_t pref_len;
1584             tmp.len = scan_length_prefixed_data (rem, at, &pref_len);
1585             if (tmp.len == 0)
1586               {
1587                 /* NOTE: scan_length_prefixed_data calls UNPACK_ERROR */
1588                 goto error_cleanup_during_scan;
1589               }
1590             tmp.length_prefix_len = pref_len;
1591             break;
1592           }
1593         case PROTOBUF_C_WIRE_TYPE_32BIT:
1594           if (rem < 4)
1595             {
1596               UNPACK_ERROR (("too short after 32bit wiretype at offset %u",
1597                              (unsigned)(at-data)));
1598               goto error_cleanup_during_scan;
1599             }
1600           tmp.len = 4;
1601           break;
1602         default:
1603           UNPACK_ERROR (("unsupported tag %u at offset %u",
1604                          wire_type, (unsigned)(at-data)));
1605           goto error_cleanup_during_scan;
1606         }
1607       if (in_slab_index == (1U<<(which_slab+FIRST_SCANNED_MEMBER_SLAB_SIZE_LOG2)))
1608         {
1609           size_t size;
1610           in_slab_index = 0;
1611           if (which_slab == MAX_SCANNED_MEMBER_SLAB)
1612             {
1613               UNPACK_ERROR (("too many fields"));
1614               goto error_cleanup_during_scan;
1615             }
1616           which_slab++;
1617           size = sizeof(ScannedMember) << (which_slab+FIRST_SCANNED_MEMBER_SLAB_SIZE_LOG2);
1618           /* TODO: consider using alloca() ! */
1619           if (allocator->tmp_alloc != NULL)
1620             scanned_member_slabs[which_slab] = TMPALLOC(allocator, size);
1621           else
1622             DO_ALLOC (scanned_member_slabs[which_slab], allocator, size, goto error_cleanup_during_scan);
1623         }
1624       scanned_member_slabs[which_slab][in_slab_index++] = tmp;
1625
1626       if (field != NULL && field->label == PROTOBUF_C_LABEL_REPEATED)
1627         {
1628           STRUCT_MEMBER (size_t, rv, field->quantifier_offset) += 1;
1629         }
1630
1631       at += tmp.len;
1632       rem -= tmp.len;
1633     }
1634
1635   /* allocate space for repeated fields */
1636   for (f = 0; f < desc->n_fields; f++)
1637     if (desc->fields[f].label == PROTOBUF_C_LABEL_REPEATED)
1638       {
1639         const ProtobufCFieldDescriptor *field = desc->fields + f;
1640         size_t siz = sizeof_elt_in_repeated_array (field->type);
1641         size_t *n_ptr = STRUCT_MEMBER_PTR (size_t, rv, field->quantifier_offset);
1642         if (*n_ptr != 0)
1643           {
1644             unsigned n = *n_ptr;
1645             *n_ptr = 0;
1646             assert(rv->descriptor != NULL);
1647 #define CLEAR_REMAINING_N_PTRS()                                            \
1648             for(f++;f < desc->n_fields; f++)                                \
1649               {                                                             \
1650                 field = desc->fields + f;                                   \
1651                 if (field->label == PROTOBUF_C_LABEL_REPEATED)              \
1652                   STRUCT_MEMBER (size_t, rv, field->quantifier_offset) = 0; \
1653               }
1654             DO_ALLOC (STRUCT_MEMBER (void *, rv, field->offset),
1655                       allocator, siz * n,
1656                       CLEAR_REMAINING_N_PTRS (); goto error_cleanup);
1657 #undef CLEAR_REMAINING_N_PTRS
1658           }
1659       }
1660
1661   /* allocate space for unknown fields */
1662   if (n_unknown)
1663     {
1664       DO_ALLOC (rv->unknown_fields,
1665                 allocator, n_unknown * sizeof (ProtobufCMessageUnknownField),
1666                 goto error_cleanup);
1667     }
1668
1669   /* do real parsing */
1670   for (i_slab = 0; i_slab <= which_slab; i_slab++)
1671     {
1672       unsigned max = (i_slab == which_slab) ? in_slab_index : (1U<<(i_slab+4));
1673       ScannedMember *slab = scanned_member_slabs[i_slab];
1674       unsigned j;
1675       for (j = 0; j < max; j++)
1676         {
1677           if (!parse_member (slab + j, rv, allocator))
1678             {
1679               UNPACK_ERROR (("error parsing member %s of %s",
1680                              slab->field ? slab->field->name : "*unknown-field*", desc->name));
1681               goto error_cleanup;
1682             }
1683         }
1684     }
1685
1686   /* cleanup */
1687   if (allocator->tmp_alloc == NULL)
1688     {
1689       unsigned j;
1690       for (j = 1; j <= which_slab; j++)
1691         FREE (allocator, scanned_member_slabs[j]);
1692     }
1693
1694   return rv;
1695
1696 error_cleanup:
1697   protobuf_c_message_free_unpacked (rv, allocator);
1698   if (allocator->tmp_alloc == NULL)
1699     {
1700       unsigned j;
1701       for (j = 1; j <= which_slab; j++)
1702         FREE (allocator, scanned_member_slabs[j]);
1703     }
1704   return NULL;
1705
1706 error_cleanup_during_scan:
1707   FREE (allocator, rv);
1708   if (allocator->tmp_alloc == NULL)
1709     {
1710       unsigned j;
1711       for (j = 1; j <= which_slab; j++)
1712         FREE (allocator, scanned_member_slabs[j]);
1713     }
1714   return NULL;
1715 }
1716
1717 /* === free_unpacked === */
1718 void
1719 protobuf_c_message_free_unpacked  (ProtobufCMessage    *message,
1720                                    ProtobufCAllocator  *allocator)
1721 {
1722   const ProtobufCMessageDescriptor *desc = message->descriptor;
1723   unsigned f;
1724   ASSERT_IS_MESSAGE (message);
1725   if (allocator == NULL)
1726     allocator = &protobuf_c_default_allocator;
1727   message->descriptor = NULL;
1728   for (f = 0; f < desc->n_fields; f++)
1729     {
1730       if (desc->fields[f].label == PROTOBUF_C_LABEL_REPEATED)
1731         {
1732           size_t n = STRUCT_MEMBER (size_t, message, desc->fields[f].quantifier_offset);
1733           void * arr = STRUCT_MEMBER (void *, message, desc->fields[f].offset);
1734           if (desc->fields[f].type == PROTOBUF_C_TYPE_STRING)
1735             {
1736               unsigned i;
1737               for (i = 0; i < n; i++)
1738                 FREE (allocator, ((char**)arr)[i]);
1739             }
1740           else if (desc->fields[f].type == PROTOBUF_C_TYPE_BYTES)
1741             {
1742               unsigned i;
1743               for (i = 0; i < n; i++)
1744                 FREE (allocator, ((ProtobufCBinaryData*)arr)[i].data);
1745             }
1746           else if (desc->fields[f].type == PROTOBUF_C_TYPE_MESSAGE)
1747             {
1748               unsigned i;
1749               for (i = 0; i < n; i++)
1750                 protobuf_c_message_free_unpacked (((ProtobufCMessage**)arr)[i], allocator);
1751             }
1752           if (arr != NULL)
1753             FREE (allocator, arr);
1754         }
1755       else if (desc->fields[f].type == PROTOBUF_C_TYPE_STRING)
1756         {
1757           char *str = STRUCT_MEMBER (char *, message, desc->fields[f].offset);
1758           if (str && str != desc->fields[f].default_value)
1759             FREE (allocator, str);
1760         }
1761       else if (desc->fields[f].type == PROTOBUF_C_TYPE_BYTES)
1762         {
1763           void *data = STRUCT_MEMBER (ProtobufCBinaryData, message, desc->fields[f].offset).data;
1764           const ProtobufCBinaryData *default_bd;
1765           default_bd = desc->fields[f].default_value;
1766           if (data != NULL
1767            && (default_bd == NULL || default_bd->data != data))
1768             FREE (allocator, data);
1769         }
1770       else if (desc->fields[f].type == PROTOBUF_C_TYPE_MESSAGE)
1771         {
1772           ProtobufCMessage *sm;
1773           sm = STRUCT_MEMBER (ProtobufCMessage *, message,desc->fields[f].offset);
1774           if (sm && sm != desc->fields[f].default_value)
1775             protobuf_c_message_free_unpacked (sm, allocator);
1776         }
1777     }
1778
1779   for (f = 0; f < message->n_unknown_fields; f++)
1780     FREE (allocator, message->unknown_fields[f].data);
1781   if (message->unknown_fields != NULL)
1782     FREE (allocator, message->unknown_fields);
1783
1784   FREE (allocator, message);
1785 }
1786
1787 /* === services === */
1788 typedef void (*DestroyHandler)(void *service);
1789 typedef void (*GenericHandler)(void *service,
1790                                const ProtobufCMessage *input,
1791                                ProtobufCClosure  closure,
1792                                void             *closure_data);
1793 void
1794 protobuf_c_service_invoke_internal(ProtobufCService *service,
1795                                   unsigned          method_index,
1796                                   const ProtobufCMessage *input,
1797                                   ProtobufCClosure  closure,
1798                                   void             *closure_data)
1799 {
1800   GenericHandler *handlers;
1801   GenericHandler handler;
1802   PROTOBUF_C_ASSERT (method_index < service->descriptor->n_methods);
1803   handlers = (GenericHandler *) (service + 1);
1804   handler = handlers[method_index];
1805   (*handler) (service, input, closure, closure_data);
1806 }
1807
1808 void
1809 protobuf_c_service_generated_init (ProtobufCService *service,
1810                                    const ProtobufCServiceDescriptor *descriptor,
1811                                    ProtobufCServiceDestroy destroy)
1812 {
1813   ASSERT_IS_SERVICE_DESCRIPTOR(descriptor);
1814   service->descriptor = descriptor;
1815   service->destroy = destroy;
1816   service->invoke = protobuf_c_service_invoke_internal;
1817   memset (service + 1, 0, descriptor->n_methods * sizeof (GenericHandler));
1818 }
1819
1820 void protobuf_c_service_destroy (ProtobufCService *service)
1821 {
1822   service->destroy (service);
1823 }
1824
1825 /* --- querying the descriptors --- */
1826 const ProtobufCEnumValue *
1827 protobuf_c_enum_descriptor_get_value_by_name
1828                          (const ProtobufCEnumDescriptor    *desc,
1829                           const char                       *name)
1830 {
1831   unsigned start = 0, count = desc->n_value_names;
1832   while (count > 1)
1833     {
1834       unsigned mid = start + count / 2;
1835       int rv = strcmp (desc->values_by_name[mid].name, name);
1836       if (rv == 0)
1837         return desc->values + desc->values_by_name[mid].index;
1838       else if (rv < 0)
1839         {
1840           count = start + count - (mid - 1);
1841           start = mid + 1;
1842         }
1843       else
1844         count = mid - start;
1845     }
1846   if (count == 0)
1847     return NULL;
1848   if (strcmp (desc->values_by_name[start].name, name) == 0)
1849     return desc->values + desc->values_by_name[start].index;
1850   return NULL;
1851 }
1852 const ProtobufCEnumValue *
1853 protobuf_c_enum_descriptor_get_value
1854                          (const ProtobufCEnumDescriptor    *desc,
1855                           int                               value)
1856 {
1857   int rv = int_range_lookup (desc->n_value_ranges, desc->value_ranges, value);
1858   if (rv < 0)
1859     return NULL;
1860   return desc->values + rv;
1861 }
1862
1863 const ProtobufCFieldDescriptor *
1864 protobuf_c_message_descriptor_get_field_by_name
1865                          (const ProtobufCMessageDescriptor *desc,
1866                           const char                       *name)
1867 {
1868   unsigned start = 0, count = desc->n_fields;
1869   const ProtobufCFieldDescriptor *field;
1870   while (count > 1)
1871     {
1872       unsigned mid = start + count / 2;
1873       int rv;
1874       field = desc->fields + desc->fields_sorted_by_name[mid];
1875       rv = strcmp (field->name, name);
1876       if (rv == 0)
1877         return field;
1878       else if (rv < 0)
1879         {
1880           count = start + count - (mid + 1);
1881           start = mid + 1;
1882         }
1883       else
1884         count = mid - start;
1885     }
1886   if (count == 0)
1887     return NULL;
1888   field = desc->fields + desc->fields_sorted_by_name[start];
1889   if (strcmp (field->name, name) == 0)
1890     return field;
1891   return NULL;
1892 }
1893
1894 const ProtobufCFieldDescriptor *
1895 protobuf_c_message_descriptor_get_field
1896                          (const ProtobufCMessageDescriptor *desc,
1897                           unsigned                          value)
1898 {
1899   int rv = int_range_lookup (desc->n_field_ranges,
1900                              desc->field_ranges,
1901                              value);
1902   if (rv < 0)
1903     return NULL;
1904   return desc->fields + rv;
1905 }
1906
1907 const ProtobufCMethodDescriptor *
1908 protobuf_c_service_descriptor_get_method_by_name
1909                          (const ProtobufCServiceDescriptor *desc,
1910                           const char                       *name)
1911 {
1912   unsigned start = 0, count = desc->n_methods;
1913   while (count > 1)
1914     {
1915       unsigned mid = start + count / 2;
1916       int rv = strcmp (desc->methods[desc->method_indices_by_name[mid]].name, name);
1917       if (rv == 0)
1918         return desc->methods + desc->method_indices_by_name[mid];
1919       if (rv < 0)
1920         {
1921           count = start + count - (mid - 1);
1922           start = mid + 1;
1923         }
1924       else
1925         {
1926           count = mid - start;
1927         }
1928     }
1929   if (count == 0)
1930     return NULL;
1931   if (strcmp (desc->methods[desc->method_indices_by_name[start]].name, name) == 0)
1932     return desc->methods + desc->method_indices_by_name[start];
1933   return NULL;
1934 }