modules/misc/webservices/json.c

   1 /* vim: set et ts=3 sw=3 ft=c:
   2  *
   3  * Copyright (C) 2012 James McLaughlin et al.  All rights reserved.
   4  * https://github.com/udp/json-parser
   5  *
   6  * Redistribution and use in source and binary forms, with or without
   7  * modification, are permitted provided that the following conditions
   8  * are met:
   9  *
  10  * 1. Redistributions of source code must retain the above copyright
  11  *   notice, this list of conditions and the following disclaimer.
  12  *
  13  * 2. Redistributions in binary form must reproduce the above copyright
  14  *   notice, this list of conditions and the following disclaimer in the
  15  *   documentation and/or other materials provided with the distribution.
  16  *
  17  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
  18  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
  19  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
  20  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
  21  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
  22  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
  23  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
  24  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
  25  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
  26  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
  27  * SUCH DAMAGE.
  28  */
  29
  30 #include "json.h"
  31
  32 #ifdef _MSC_VER
  33    #ifndef _CRT_SECURE_NO_WARNINGS
  34       #define _CRT_SECURE_NO_WARNINGS
  35    #endif
  36 #endif
  37
  38 #ifdef __cplusplus
  39    const struct _json_value json_value_none; /* zero-d by ctor */
  40 #else
  41    const struct _json_value json_value_none = { 0, 0, { 0 }, { 0 } };
  42 #endif
  43
  44 #include <stdlib.h>
  45 #include <stdio.h>
  46 #include <string.h>
  47 #include <ctype.h>
  48 #include <math.h>
  49
  50 typedef unsigned short json_uchar;
  51
  52 static unsigned char hex_value (json_char c)
  53 {
  54    if (c >= 'A' && c <= 'F')
  55       return (c - 'A') + 10;
  56
  57    if (c >= 'a' && c <= 'f')
  58       return (c - 'a') + 10;
  59
  60    if (c >= '0' && c <= '9')
  61       return c - '0';
  62
  63    return 0xFF;
  64 }
  65
  66 typedef struct
  67 {
  68    json_settings settings;
  69    int first_pass;
  70
  71    unsigned long used_memory;
  72
  73    unsigned int uint_max;
  74    unsigned long ulong_max;
  75
  76 } json_state;
  77
  78 static void * json_alloc (json_state * state, unsigned long size, int zero)
  79 {
  80    void * mem;
  81
  82    if ((state->ulong_max - state->used_memory) < size)
  83       return 0;
  84
  85    if (state->settings.max_memory
  86          && (state->used_memory += size) > state->settings.max_memory)
  87    {
  88       return 0;
  89    }
  90
  91    if (! (mem = zero ? calloc (size, 1) : malloc (size)))
  92       return 0;
  93
  94    return mem;
  95 }
  96
  97 static int new_value
  98    (json_state * state, json_value ** top, json_value ** root, json_value ** alloc, json_type type)
  99 {
 100    json_value * value;
 101    int values_size;
 102
 103    if (!state->first_pass)
 104    {
 105       value = *top = *alloc;
 106       *alloc = (*alloc)->_reserved.next_alloc;
 107
 108       if (!*root)
 109          *root = value;
 110
 111       switch (value->type)
 112       {
 113          case json_array:
 114
 115             if (! (value->u.array.values = (json_value **) json_alloc
 116                (state, value->u.array.length * sizeof (json_value *), 0)) )
 117             {
 118                return 0;
 119             }
 120
 121             value->u.array.length = 0;
 122             break;
 123
 124          case json_object:
 125
 126             values_size = sizeof (*value->u.object.values) * value->u.object.length;
 127
 128             if (! ((*(void **) &value->u.object.values) = json_alloc
 129                   (state, values_size + ((unsigned long) value->u.object.values), 0)) )
 130             {
 131                return 0;
 132             }
 133
 134             value->_reserved.object_mem = (*(char **) &value->u.object.values) + values_size;
 135
 136             value->u.object.length = 0;
 137             break;
 138
 139          case json_string:
 140
 141             if (! (value->u.string.ptr = (json_char *) json_alloc
 142                (state, (value->u.string.length + 1) * sizeof (json_char), 0)) )
 143             {
 144                return 0;
 145             }
 146
 147             value->u.string.length = 0;
 148             break;
 149
 150          default:
 151             break;
 152       };
 153
 154       return 1;
 155    }
 156
 157    value = (json_value *) json_alloc (state, sizeof (json_value), 1);
 158
 159    if (!value)
 160       return 0;
 161
 162    if (!*root)
 163       *root = value;
 164
 165    value->type = type;
 166    value->parent = *top;
 167
 168    if (*alloc)
 169       (*alloc)->_reserved.next_alloc = value;
 170
 171    *alloc = *top = value;
 172
 173    return 1;
 174 }
 175
 176 #define e_off \
 177    ((int) (i - cur_line_begin))
 178
 179 #define whitespace \
 180    case '\n': ++ cur_line;  cur_line_begin = i; \
 181    /* fall through */ \
 182    case ' ': case '\t': case '\r'
 183
 184 #define string_add(b)  \
 185    do { if (!state.first_pass) string [string_length] = b;  ++ string_length; } while (0);
 186
 187 static const long
 188    flag_next = 1,  flag_reproc = 2,  flag_need_comma = 4,  flag_seek_value = 8,
 189    flag_escaped = 16,  flag_string = 32,  flag_need_colon = 64,  flag_done = 128,
 190    flag_num_negative = 256,  flag_num_zero = 512,  flag_num_e = 1024,
 191    flag_num_e_got_sign = 2048,  flag_num_e_negative = 4096;
 192
 193 json_value * json_parse_ex (json_settings * settings, const json_char * json, char * error_buf)
 194 {
 195    json_char error [128];
 196    unsigned int cur_line;
 197    const json_char * cur_line_begin, * i;
 198    json_value * top, * root, * alloc = 0;
 199    json_state state;
 200    long flags;
 201    long num_digits = 0, num_fraction = 0, num_e = 0;
 202
 203    error[0] = '\0';
 204
 205    memset (&state, 0, sizeof (json_state));
 206    memcpy (&state.settings, settings, sizeof (json_settings));
 207
 208    memset (&state.uint_max, 0xFF, sizeof (state.uint_max));
 209    memset (&state.ulong_max, 0xFF, sizeof (state.ulong_max));
 210
 211    state.uint_max -= 8; /* limit of how much can be added before next check */
 212    state.ulong_max -= 8;
 213
 214    for (state.first_pass = 1; state.first_pass >= 0; -- state.first_pass)
 215    {
 216       json_uchar uchar;
 217       unsigned char uc_b1, uc_b2, uc_b3, uc_b4;
 218       json_char * string = NULL;
 219       unsigned int string_length = 0;
 220
 221       top = root = 0;
 222       flags = flag_seek_value;
 223
 224       cur_line = 1;
 225       cur_line_begin = json;
 226
 227       for (i = json ;; ++ i)
 228       {
 229          json_char b = *i;
 230
 231          if (flags & flag_done)
 232          {
 233             if (!b)
 234                break;
 235
 236             switch (b)
 237             {
 238                whitespace:
 239                   continue;
 240
 241                default:
 242                   sprintf (error, "%d:%d: Trailing garbage: `%c`", cur_line, e_off, b);
 243                   goto e_failed;
 244             };
 245          }
 246
 247          if (flags & flag_string)
 248          {
 249             if (!b)
 250             {  sprintf (error, "Unexpected EOF in string (at %d:%d)", cur_line, e_off);
 251                goto e_failed;
 252             }
 253
 254             if (string_length > state.uint_max)
 255                goto e_overflow;
 256
 257             if (flags & flag_escaped)
 258             {
 259                flags &= ~ flag_escaped;
 260
 261                switch (b)
 262                {
 263                   case 'b':  string_add ('\b');  break;
 264                   case 'f':  string_add ('\f');  break;
 265                   case 'n':  string_add ('\n');  break;
 266                   case 'r':  string_add ('\r');  break;
 267                   case 't':  string_add ('\t');  break;
 268                   case 'u':
 269
 270                     if ((uc_b1 = hex_value (*++ i)) == 0xFF || (uc_b2 = hex_value (*++ i)) == 0xFF
 271                           || (uc_b3 = hex_value (*++ i)) == 0xFF || (uc_b4 = hex_value (*++ i)) == 0xFF)
 272                     {
 273                         sprintf (error, "Invalid character value `%c` (at %d:%d)", b, cur_line, e_off);
 274                         goto e_failed;
 275                     }
 276
 277                     uc_b1 = uc_b1 * 16 + uc_b2;
 278                     uc_b2 = uc_b3 * 16 + uc_b4;
 279
 280                     uchar = ((json_char) uc_b1) * 256 + uc_b2;
 281
 282                     if (sizeof (json_char) >= sizeof (json_uchar) || (uc_b1 == 0 && uc_b2 <= 0x7F))
 283                     {
 284                        string_add ((json_char) uchar);
 285                        break;
 286                     }
 287
 288                     if (uchar <= 0x7FF)
 289                     {
 290                         if (state.first_pass)
 291                            string_length += 2;
 292                         else
 293                         {  string [string_length ++] = 0xC0 | ((uc_b2 & 0xC0) >> 6) | ((uc_b1 & 0x7) << 2);
 294                            string [string_length ++] = 0x80 | (uc_b2 & 0x3F);
 295                         }
 296
 297                         break;
 298                     }
 299
 300                     if (state.first_pass)
 301                        string_length += 3;
 302                     else
 303                     {  string [string_length ++] = 0xE0 | ((uc_b1 & 0xF0) >> 4);
 304                        string [string_length ++] = 0x80 | ((uc_b1 & 0xF) << 2) | ((uc_b2 & 0xC0) >> 6);
 305                        string [string_length ++] = 0x80 | (uc_b2 & 0x3F);
 306                     }
 307
 308                     break;
 309
 310                   default:
 311                      string_add (b);
 312                };
 313
 314                continue;
 315             }
 316
 317             if (b == '\\')
 318             {
 319                flags |= flag_escaped;
 320                continue;
 321             }
 322
 323             if (b == '"')
 324             {
 325                if (!state.first_pass)
 326                   string [string_length] = 0;
 327
 328                flags &= ~ flag_string;
 329                string = 0;
 330
 331                switch (top->type)
 332                {
 333                   case json_string:
 334
 335                      top->u.string.length = string_length;
 336                      flags |= flag_next;
 337
 338                      break;
 339
 340                   case json_object:
 341
 342                      if (state.first_pass)
 343                         (*(json_char **) &top->u.object.values) += string_length + 1;
 344                      else
 345                      {
 346                         top->u.object.values [top->u.object.length].name
 347                            = (json_char *) top->_reserved.object_mem;
 348
 349                         (*(json_char **) &top->_reserved.object_mem) += string_length + 1;
 350                      }
 351
 352                      flags |= flag_seek_value | flag_need_colon;
 353                      continue;
 354
 355                   default:
 356                      break;
 357                };
 358             }
 359             else
 360             {
 361                string_add (b);
 362                continue;
 363             }
 364          }
 365
 366          if (flags & flag_seek_value)
 367          {
 368             switch (b)
 369             {
 370                whitespace:
 371                   continue;
 372
 373                case ']':
 374
 375                   if (top->type == json_array)
 376                      flags = (flags & ~ (flag_need_comma | flag_seek_value)) | flag_next;
 377                   else if (!state.settings.settings & json_relaxed_commas)
 378                   {  sprintf (error, "%d:%d: Unexpected ]", cur_line, e_off);
 379                      goto e_failed;
 380                   }
 381
 382                   break;
 383
 384                default:
 385
 386                   if (flags & flag_need_comma)
 387                   {
 388                      if (b == ',')
 389                      {  flags &= ~ flag_need_comma;
 390                         continue;
 391                      }
 392                      else
 393                      {  sprintf (error, "%d:%d: Expected , before %c", cur_line, e_off, b);
 394                         goto e_failed;
 395                      }
 396                   }
 397
 398                   if (flags & flag_need_colon)
 399                   {
 400                      if (b == ':')
 401                      {  flags &= ~ flag_need_colon;
 402                         continue;
 403                      }
 404                      else
 405                      {  sprintf (error, "%d:%d: Expected : before %c", cur_line, e_off, b);
 406                         goto e_failed;
 407                      }
 408                   }
 409
 410                   flags &= ~ flag_seek_value;
 411
 412                   switch (b)
 413                   {
 414                      case '{':
 415
 416                         if (!new_value (&state, &top, &root, &alloc, json_object))
 417                            goto e_alloc_failure;
 418
 419                         continue;
 420
 421                      case '[':
 422
 423                         if (!new_value (&state, &top, &root, &alloc, json_array))
 424                            goto e_alloc_failure;
 425
 426                         flags |= flag_seek_value;
 427                         continue;
 428
 429                      case '"':
 430
 431                         if (!new_value (&state, &top, &root, &alloc, json_string))
 432                            goto e_alloc_failure;
 433
 434                         flags |= flag_string;
 435
 436                         string = top->u.string.ptr;
 437                         string_length = 0;
 438
 439                         continue;
 440
 441                      case 't':
 442
 443                         if (*(++ i) != 'r' || *(++ i) != 'u' || *(++ i) != 'e')
 444                            goto e_unknown_value;
 445
 446                         if (!new_value (&state, &top, &root, &alloc, json_boolean))
 447                            goto e_alloc_failure;
 448
 449                         top->u.boolean = 1;
 450
 451                         flags |= flag_next;
 452                         break;
 453
 454                      case 'f':
 455
 456                         if (*(++ i) != 'a' || *(++ i) != 'l' || *(++ i) != 's' || *(++ i) != 'e')
 457                            goto e_unknown_value;
 458
 459                         if (!new_value (&state, &top, &root, &alloc, json_boolean))
 460                            goto e_alloc_failure;
 461
 462                         flags |= flag_next;
 463                         break;
 464
 465                      case 'n':
 466
 467                         if (*(++ i) != 'u' || *(++ i) != 'l' || *(++ i) != 'l')
 468                            goto e_unknown_value;
 469
 470                         if (!new_value (&state, &top, &root, &alloc, json_null))
 471                            goto e_alloc_failure;
 472
 473                         flags |= flag_next;
 474                         break;
 475
 476                      default:
 477
 478                         if (isdigit (b) || b == '-')
 479                         {
 480                            if (!new_value (&state, &top, &root, &alloc, json_integer))
 481                               goto e_alloc_failure;
 482
 483                            if (!state.first_pass)
 484                            {
 485                               while (isdigit (b) || b == '+' || b == '-'
 486                                         || b == 'e' || b == 'E' || b == '.')
 487                               {
 488                                  b = *++ i;
 489                               }
 490
 491                               flags |= flag_next | flag_reproc;
 492                               break;
 493                            }
 494
 495                            flags &= ~ (flag_num_negative | flag_num_e |
 496                                         flag_num_e_got_sign | flag_num_e_negative |
 497                                            flag_num_zero);
 498
 499                            num_digits = 0;
 500                            num_fraction = 0;
 501                            num_e = 0;
 502
 503                            if (b != '-')
 504                            {
 505                               flags |= flag_reproc;
 506                               break;
 507                            }
 508
 509                            flags |= flag_num_negative;
 510                            continue;
 511                         }
 512                         else
 513                         {  sprintf (error, "%d:%d: Unexpected %c when seeking value", cur_line, e_off, b);
 514                            goto e_failed;
 515                         }
 516                   };
 517             };
 518          }
 519          else
 520          {
 521             switch (top->type)
 522             {
 523             case json_object:
 524
 525                switch (b)
 526                {
 527                   whitespace:
 528                      continue;
 529
 530                   case '"':
 531
 532                      if (flags & flag_need_comma && (!state.settings.settings & json_relaxed_commas))
 533                      {
 534                         sprintf (error, "%d:%d: Expected , before \"", cur_line, e_off);
 535                         goto e_failed;
 536                      }
 537
 538                      flags |= flag_string;
 539
 540                      string = (json_char *) top->_reserved.object_mem;
 541                      string_length = 0;
 542
 543                      break;
 544
 545                   case '}':
 546
 547                      flags = (flags & ~ flag_need_comma) | flag_next;
 548                      break;
 549
 550                   case ',':
 551
 552                      if (flags & flag_need_comma)
 553                      {
 554                         flags &= ~ flag_need_comma;
 555                         break;
 556                      }
 557
 558                      /* fall through */
 559                   default:
 560
 561                      sprintf (error, "%d:%d: Unexpected `%c` in object", cur_line, e_off, b);
 562                      goto e_failed;
 563                };
 564
 565                break;
 566
 567             case json_integer:
 568             case json_double:
 569
 570                if (isdigit (b))
 571                {
 572                   ++ num_digits;
 573
 574                   if (top->type == json_integer || flags & flag_num_e)
 575                   {
 576                      if (! (flags & flag_num_e))
 577                      {
 578                         if (flags & flag_num_zero)
 579                         {  sprintf (error, "%d:%d: Unexpected `0` before `%c`", cur_line, e_off, b);
 580                            goto e_failed;
 581                         }
 582
 583                         if (num_digits == 1 && b == '0')
 584                            flags |= flag_num_zero;
 585                      }
 586                      else
 587                      {
 588                         flags |= flag_num_e_got_sign;
 589                         num_e = (num_e * 10) + (b - '0');
 590                         continue;
 591                      }
 592
 593                      top->u.integer = (top->u.integer * 10) + (b - '0');
 594                      continue;
 595                   }
 596
 597                   num_fraction = (num_fraction * 10) + (b - '0');
 598                   continue;
 599                }
 600
 601                if (b == '+' || b == '-')
 602                {
 603                   if ( (flags & flag_num_e) && !(flags & flag_num_e_got_sign))
 604                   {
 605                      flags |= flag_num_e_got_sign;
 606
 607                      if (b == '-')
 608                         flags |= flag_num_e_negative;
 609
 610                      continue;
 611                   }
 612                }
 613                else if (b == '.' && top->type == json_integer)
 614                {
 615                   if (!num_digits)
 616                   {  sprintf (error, "%d:%d: Expected digit before `.`", cur_line, e_off);
 617                      goto e_failed;
 618                   }
 619
 620                   top->type = json_double;
 621                   top->u.dbl = (double) top->u.integer;
 622
 623                   num_digits = 0;
 624                   continue;
 625                }
 626
 627                if (! (flags & flag_num_e))
 628                {
 629                   if (top->type == json_double)
 630                   {
 631                      if (!num_digits)
 632                      {  sprintf (error, "%d:%d: Expected digit after `.`", cur_line, e_off);
 633                         goto e_failed;
 634                      }
 635
 636                      top->u.dbl += ((double) num_fraction) / (pow ( (double) 10.0, (double) num_digits));
 637                   }
 638
 639                   if (b == 'e' || b == 'E')
 640                   {
 641                      flags |= flag_num_e;
 642
 643                      if (top->type == json_integer)
 644                      {
 645                         top->type = json_double;
 646                         top->u.dbl = (double) top->u.integer;
 647                      }
 648
 649                      num_digits = 0;
 650                      flags &= ~ flag_num_zero;
 651
 652                      continue;
 653                   }
 654                }
 655                else
 656                {
 657                   if (!num_digits)
 658                   {  sprintf (error, "%d:%d: Expected digit after `e`", cur_line, e_off);
 659                      goto e_failed;
 660                   }
 661
 662                   top->u.dbl *= pow (10, (double) (flags & flag_num_e_negative ? - num_e : num_e));
 663                }
 664
 665                if (flags & flag_num_negative)
 666                {
 667                   if (top->type == json_integer)
 668                      top->u.integer = - top->u.integer;
 669                   else
 670                      top->u.dbl = - top->u.dbl;
 671                }
 672
 673                flags |= flag_next | flag_reproc;
 674                break;
 675
 676             default:
 677                break;
 678             };
 679          }
 680
 681          if (flags & flag_reproc)
 682          {
 683             flags &= ~ flag_reproc;
 684             -- i;
 685          }
 686
 687          if (flags & flag_next)
 688          {
 689             flags = (flags & ~ flag_next) | flag_need_comma;
 690
 691             if (!top->parent)
 692             {
 693                /* root value done */
 694
 695                flags |= flag_done;
 696                continue;
 697             }
 698
 699             if (top->parent->type == json_array)
 700                flags |= flag_seek_value;
 701
 702             if (!state.first_pass)
 703             {
 704                json_value * parent = top->parent;
 705
 706                switch (parent->type)
 707                {
 708                   case json_object:
 709
 710                      parent->u.object.values
 711                         [parent->u.object.length].value = top;
 712
 713                      break;
 714
 715                   case json_array:
 716
 717                      parent->u.array.values
 718                            [parent->u.array.length] = top;
 719
 720                      break;
 721
 722                   default:
 723                      break;
 724                };
 725             }
 726
 727             if ( (++ top->parent->u.array.length) > state.uint_max)
 728                goto e_overflow;
 729
 730             top = top->parent;
 731
 732             continue;
 733          }
 734       }
 735
 736       alloc = root;
 737    }
 738
 739    return root;
 740
 741 e_unknown_value:
 742
 743    sprintf (error, "%d:%d: Unknown value", cur_line, e_off);
 744    goto e_failed;
 745
 746 e_alloc_failure:
 747
 748    strcpy (error, "Memory allocation failure");
 749    goto e_failed;
 750
 751 e_overflow:
 752
 753    sprintf (error, "%d:%d: Too long (caught overflow)", cur_line, e_off);
 754    goto e_failed;
 755
 756 e_failed:
 757
 758    if (error_buf)
 759    {
 760       if (*error)
 761          strcpy (error_buf, error);
 762       else
 763          strcpy (error_buf, "Unknown error");
 764    }
 765
 766    if (state.first_pass)
 767       alloc = root;
 768
 769    while (alloc)
 770    {
 771       top = alloc->_reserved.next_alloc;
 772       free (alloc);
 773       alloc = top;
 774    }
 775
 776    if (!state.first_pass)
 777       json_value_free (root);
 778
 779    return 0;
 780 }
 781
 782 json_value * json_parse (const json_char * json)
 783 {
 784    json_settings settings;
 785    memset (&settings, 0, sizeof (json_settings));
 786
 787    return json_parse_ex (&settings, json, 0);
 788 }
 789
 790 void json_value_free (json_value * value)
 791 {
 792    json_value * cur_value;
 793
 794    if (!value)
 795       return;
 796
 797    value->parent = 0;
 798
 799    while (value)
 800    {
 801       switch (value->type)
 802       {
 803          case json_array:
 804
 805             if (!value->u.array.length)
 806             {
 807                free (value->u.array.values);
 808                break;
 809             }
 810
 811             value = value->u.array.values [-- value->u.array.length];
 812             continue;
 813
 814          case json_object:
 815
 816             if (!value->u.object.length)
 817             {
 818                free (value->u.object.values);
 819                break;
 820             }
 821
 822             value = value->u.object.values [-- value->u.object.length].value;
 823             continue;
 824
 825          case json_string:
 826
 827             free (value->u.string.ptr);
 828             break;
 829
 830          default:
 831             break;
 832       };
 833
 834       cur_value = value;
 835       value = value->parent;
 836       free (cur_value);
 837    }
 838 }