Line data    Source code

       1             : /*
       2             :  * Copyright (c) 2017 Intel Corporation
       3             :  * Copyright (c) 2020 L. A. F. Pereira <l@tia.mat.br>
       4             :  *
       5             :  * SPDX-License-Identifier: Apache-2.0
       6             :  */
       7             : 
       8             : #include <assert.h>
       9             : #include <ctype.h>
      10             : #include <errno.h>
      11             : #include <limits.h>
      12             : #include <stdbool.h>
      13             : #include <stdint.h>
      14             : #include <stdio.h>
      15             : #include <stdlib.h>
      16             : #include <string.h>
      17             : 
      18             : #include "json.h"
      19             : #include "lwan.h"
      20             : #include "int-to-str.h"
      21             : 
      22             : struct token {
      23             :     enum json_tokens type;
      24             :     char *start;
      25             :     char *end;
      26             : };
      27             : 
      28             : struct lexer {
      29             :     void *(*state)(struct lexer *lexer);
      30             :     char *start;
      31             :     char *pos;
      32             :     char *end;
      33             :     struct token token;
      34             : };
      35             : 
      36             : struct json_obj {
      37             :     struct lexer lexer;
      38             : };
      39             : 
      40             : struct json_obj_key_value {
      41             :     const char *key;
      42             :     size_t key_len;
      43             :     struct token value;
      44             : };
      45             : 
      46           0 : static bool lexer_consume(struct lexer *lexer,
      47             :                           struct token *token,
      48             :                           enum json_tokens empty_token)
      49             : {
      50           0 :     if (lexer->token.type == empty_token) {
      51           0 :         return false;
      52             :     }
      53             : 
      54           0 :     *token = lexer->token;
      55           0 :     lexer->token.type = empty_token;
      56             : 
      57           0 :     return true;
      58             : }
      59             : 
      60           0 : static bool lexer_next(struct lexer *lexer, struct token *token)
      61             : {
      62           0 :     while (lexer->state) {
      63           0 :         if (lexer_consume(lexer, token, JSON_TOK_NONE)) {
      64           0 :             return true;
      65             :         }
      66             : 
      67           0 :         lexer->state = lexer->state(lexer);
      68             :     }
      69             : 
      70           0 :     return lexer_consume(lexer, token, JSON_TOK_EOF);
      71             : }
      72             : 
      73             : static void *lexer_json(struct lexer *lexer);
      74             : 
      75           0 : static void emit(struct lexer *lexer, enum json_tokens token)
      76             : {
      77           0 :     lexer->token.type = token;
      78           0 :     lexer->token.start = lexer->start;
      79           0 :     lexer->token.end = lexer->pos;
      80           0 :     lexer->start = lexer->pos;
      81           0 : }
      82             : 
      83           0 : static void* emit_cont(struct lexer *lexer, enum json_tokens token)
      84             : {
      85           0 :     emit(lexer, token);
      86           0 :     return lexer_json;
      87             : }
      88             : 
      89           0 : static void* emit_end(struct lexer *lexer, enum json_tokens token)
      90             : {
      91           0 :     emit(lexer, token);
      92           0 :     return NULL;
      93             : }
      94             : 
      95           0 : static int next(struct lexer *lexer)
      96             : {
      97           0 :     if (lexer->pos >= lexer->end) {
      98           0 :         lexer->pos = lexer->end + 1;
      99             : 
     100           0 :         return '\0';
     101             :     }
     102             : 
     103           0 :     return *lexer->pos++;
     104             : }
     105             : 
     106           0 : static void ignore(struct lexer *lexer) { lexer->start = lexer->pos; }
     107             : 
     108           0 : static void backup(struct lexer *lexer) { lexer->pos--; }
     109             : 
     110           0 : static int peek(struct lexer *lexer)
     111             : {
     112           0 :     int chr = next(lexer);
     113             : 
     114           0 :     backup(lexer);
     115             : 
     116           0 :     return chr;
     117             : }
     118             : 
     119           0 : static void *lexer_string(struct lexer *lexer)
     120             : {
     121           0 :     ignore(lexer);
     122             : 
     123           0 :     while (true) {
     124           0 :         int chr = next(lexer);
     125             : 
     126           0 :         if (UNLIKELY(chr == '\0')) {
     127           0 :             return emit_end(lexer, JSON_TOK_ERROR);
     128             :         }
     129             : 
     130           0 :         if (chr == '\\') {
     131           0 :             switch (next(lexer)) {
     132           0 :             case '"':
     133             :             case '\\':
     134             :             case '/':
     135             :             case 'b':
     136             :             case 'f':
     137             :             case 'n':
     138             :             case 'r':
     139             :             case 't':
     140           0 :                 continue;
     141           0 :             case 'u':
     142           0 :                 if (UNLIKELY(!isxdigit(next(lexer)))) {
     143           0 :                     goto error;
     144             :                 }
     145             : 
     146           0 :                 if (UNLIKELY(!isxdigit(next(lexer)))) {
     147           0 :                     goto error;
     148             :                 }
     149             : 
     150           0 :                 if (UNLIKELY(!isxdigit(next(lexer)))) {
     151           0 :                     goto error;
     152             :                 }
     153             : 
     154           0 :                 if (UNLIKELY(!isxdigit(next(lexer)))) {
     155           0 :                     goto error;
     156             :                 }
     157             : 
     158           0 :                 break;
     159           0 :             default:
     160           0 :                 goto error;
     161             :             }
     162             :         }
     163             : 
     164           0 :         if (chr == '"') {
     165           0 :             backup(lexer);
     166           0 :             emit(lexer, JSON_TOK_STRING);
     167             : 
     168           0 :             next(lexer);
     169           0 :             ignore(lexer);
     170             : 
     171           0 :             return lexer_json;
     172             :         }
     173             :     }
     174             : 
     175           0 : error:
     176           0 :     return emit_end(lexer, JSON_TOK_ERROR);
     177             : }
     178             : 
     179           0 : static int accept_run(struct lexer *lexer, const char *run)
     180             : {
     181           0 :     for (; *run; run++) {
     182           0 :         if (UNLIKELY(next(lexer) != *run)) {
     183           0 :             return -EINVAL;
     184             :         }
     185             :     }
     186             : 
     187           0 :     return 0;
     188             : }
     189             : 
     190           0 : static void *lexer_boolean(struct lexer *lexer)
     191             : {
     192             :     /* Already matched either `t' or `f' at this point */
     193             : 
     194           0 :     switch (next(lexer)) {
     195           0 :     case 'r':
     196           0 :         if (LIKELY(!accept_run(lexer, "ue"))) {
     197           0 :             return emit_cont(lexer, JSON_TOK_TRUE);
     198             :         }
     199           0 :         break;
     200           0 :     case 'a':
     201           0 :         if (LIKELY(!accept_run(lexer, "lse"))) {
     202           0 :             return emit_cont(lexer, JSON_TOK_FALSE);
     203             :         }
     204           0 :         break;
     205             :     }
     206             : 
     207           0 :     return emit_end(lexer, JSON_TOK_ERROR);
     208             : }
     209             : 
     210           0 : static void *lexer_null(struct lexer *lexer)
     211             : {
     212           0 :     if (UNLIKELY(accept_run(lexer, "ull") < 0)) {
     213           0 :         return emit_end(lexer, JSON_TOK_ERROR);
     214             :     }
     215             : 
     216           0 :     return emit_cont(lexer, JSON_TOK_NULL);
     217             : }
     218             : 
     219           0 : static void *lexer_number(struct lexer *lexer)
     220             : {
     221           0 :     while (true) {
     222           0 :         int chr = next(lexer);
     223             : 
     224           0 :         if (isdigit(chr) || chr == '.') {
     225           0 :             continue;
     226             :         }
     227             : 
     228           0 :         backup(lexer);
     229           0 :         return emit_cont(lexer, JSON_TOK_NUMBER);
     230             :     }
     231             : }
     232             : 
     233           0 : static void *lexer_json(struct lexer *lexer)
     234             : {
     235           0 :     while (true) {
     236           0 :         int chr = next(lexer);
     237             : 
     238           0 :         switch (chr) {
     239           0 :         case '\0':
     240           0 :             return emit_end(lexer, JSON_TOK_EOF);
     241             : 
     242           0 :         case '}':
     243             :         case '{':
     244             :         case '[':
     245             :         case ']':
     246             :         case ',':
     247             :         case ':':
     248           0 :             return emit_cont(lexer, (enum json_tokens)chr);
     249             : 
     250           0 :         case '"':
     251           0 :             return lexer_string;
     252             : 
     253           0 :         case 'n':
     254           0 :             return lexer_null;
     255             : 
     256           0 :         case 't':
     257             :         case 'f':
     258           0 :             return lexer_boolean;
     259             : 
     260           0 :         case '-':
     261           0 :             if (LIKELY(isdigit(peek(lexer)))) {
     262           0 :                 return lexer_number;
     263             :             }
     264             : 
     265             :             /* fallthrough */
     266             :         default:
     267           0 :             if (isspace(chr)) {
     268           0 :                 ignore(lexer);
     269           0 :                 continue;
     270             :             }
     271             : 
     272           0 :             if (LIKELY(isdigit(chr))) {
     273           0 :                 return lexer_number;
     274             :             }
     275             : 
     276           0 :             return emit_end(lexer, JSON_TOK_ERROR);
     277             :         }
     278             :     }
     279             : }
     280             : 
     281           0 : static void lexer_init(struct lexer *lexer, char *data, size_t len)
     282             : {
     283           0 :     lexer->state = lexer_json;
     284           0 :     lexer->start = data;
     285           0 :     lexer->pos = data;
     286           0 :     lexer->end = data + len;
     287           0 :     lexer->token.type = JSON_TOK_NONE;
     288           0 : }
     289             : 
     290           0 : static int obj_init(struct json_obj *json, char *data, size_t len)
     291             : {
     292             :     struct token token;
     293             : 
     294           0 :     lexer_init(&json->lexer, data, len);
     295             : 
     296           0 :     if (UNLIKELY(!lexer_next(&json->lexer, &token))) {
     297           0 :         return -EINVAL;
     298             :     }
     299             : 
     300           0 :     if (UNLIKELY(token.type != JSON_TOK_OBJECT_START)) {
     301           0 :         return -EINVAL;
     302             :     }
     303             : 
     304           0 :     return 0;
     305             : }
     306             : 
     307           0 : static int element_token(enum json_tokens token)
     308             : {
     309           0 :     switch (token) {
     310           0 :     case JSON_TOK_OBJECT_START:
     311             :     case JSON_TOK_LIST_START:
     312             :     case JSON_TOK_STRING:
     313             :     case JSON_TOK_NUMBER:
     314             :     case JSON_TOK_TRUE:
     315             :     case JSON_TOK_FALSE:
     316           0 :         return 0;
     317           0 :     default:
     318           0 :         return -EINVAL;
     319             :     }
     320             : }
     321             : 
     322           0 : static int obj_next(struct json_obj *json, struct json_obj_key_value *kv)
     323             : {
     324             :     struct token token;
     325             : 
     326           0 :     if (UNLIKELY(!lexer_next(&json->lexer, &token))) {
     327           0 :         return -EINVAL;
     328             :     }
     329             : 
     330             :     /* Match end of object or next key */
     331           0 :     switch (token.type) {
     332           0 :     case JSON_TOK_OBJECT_END:
     333           0 :         kv->key = NULL;
     334           0 :         kv->key_len = 0;
     335           0 :         kv->value = token;
     336             : 
     337           0 :         return 0;
     338           0 :     case JSON_TOK_COMMA:
     339           0 :         if (UNLIKELY(!lexer_next(&json->lexer, &token))) {
     340           0 :             return -EINVAL;
     341             :         }
     342             : 
     343           0 :         if (UNLIKELY(token.type != JSON_TOK_STRING)) {
     344           0 :             return -EINVAL;
     345             :         }
     346             : 
     347             :         /* fallthrough */
     348             :     case JSON_TOK_STRING:
     349           0 :         kv->key = token.start;
     350           0 :         kv->key_len = (size_t)(token.end - token.start);
     351           0 :         break;
     352           0 :     default:
     353           0 :         return -EINVAL;
     354             :     }
     355             : 
     356             :     /* Match : after key */
     357           0 :     if (UNLIKELY(!lexer_next(&json->lexer, &token))) {
     358           0 :         return -EINVAL;
     359             :     }
     360             : 
     361           0 :     if (UNLIKELY(token.type != JSON_TOK_COLON)) {
     362           0 :         return -EINVAL;
     363             :     }
     364             : 
     365             :     /* Match value */
     366           0 :     if (UNLIKELY(!lexer_next(&json->lexer, &kv->value))) {
     367           0 :         return -EINVAL;
     368             :     }
     369             : 
     370           0 :     return element_token(kv->value.type);
     371             : }
     372             : 
     373           0 : static int arr_next(struct json_obj *json, struct token *value)
     374             : {
     375           0 :     if (UNLIKELY(!lexer_next(&json->lexer, value))) {
     376           0 :         return -EINVAL;
     377             :     }
     378             : 
     379           0 :     if (value->type == JSON_TOK_LIST_END) {
     380           0 :         return 0;
     381             :     }
     382             : 
     383           0 :     if (value->type == JSON_TOK_COMMA) {
     384           0 :         if (UNLIKELY(!lexer_next(&json->lexer, value))) {
     385           0 :             return -EINVAL;
     386             :         }
     387             :     }
     388             : 
     389           0 :     return element_token(value->type);
     390             : }
     391             : 
     392           0 : static int decode_num(const struct token *token, int32_t *num)
     393             : {
     394             :     /* FIXME: strtod() is not available in newlib/minimal libc,
     395             :      * so using strtol() here.
     396             :      */
     397             :     char *endptr;
     398             :     char prev_end;
     399             : 
     400           0 :     prev_end = *token->end;
     401           0 :     *token->end = '\0';
     402             : 
     403           0 :     errno = 0;
     404           0 :     long v = strtol(token->start, &endptr, 10);
     405           0 :     if ((long)(int)v != v) {
     406           0 :         return -ERANGE;
     407             :     }
     408             : 
     409           0 :     *num = (int)v;
     410             : 
     411           0 :     *token->end = prev_end;
     412             : 
     413           0 :     if (errno != 0) {
     414           0 :         return -errno;
     415             :     }
     416             : 
     417           0 :     if (endptr != token->end) {
     418           0 :         return -EINVAL;
     419             :     }
     420             : 
     421           0 :     return 0;
     422             : }
     423             : 
     424           0 : static bool equivalent_types(enum json_tokens type1, enum json_tokens type2)
     425             : {
     426           0 :     if (type1 == JSON_TOK_TRUE || type1 == JSON_TOK_FALSE) {
     427           0 :         return type2 == JSON_TOK_TRUE || type2 == JSON_TOK_FALSE;
     428             :     }
     429             : 
     430           0 :     return type1 == type2;
     431             : }
     432             : 
     433             : static int obj_parse(struct json_obj *obj,
     434             :                      const struct json_obj_descr *descr,
     435             :                      size_t descr_len,
     436             :                      void *val);
     437             : static int arr_parse(struct json_obj *obj,
     438             :                      const struct json_obj_descr *elem_descr,
     439             :                      size_t max_elements,
     440             :                      void *field,
     441             :                      void *val);
     442             : 
     443           0 : static int decode_value(struct json_obj *obj,
     444             :                         const struct json_obj_descr *descr,
     445             :                         struct token *value,
     446             :                         void *field,
     447             :                         void *val)
     448             : {
     449             : 
     450           0 :     if (!equivalent_types(value->type, descr->type)) {
     451           0 :         return -EINVAL;
     452             :     }
     453             : 
     454           0 :     switch (descr->type) {
     455           0 :     case JSON_TOK_OBJECT_START:
     456           0 :         return obj_parse(obj, descr->object.sub_descr,
     457           0 :                          descr->object.sub_descr_len, field);
     458           0 :     case JSON_TOK_LIST_START:
     459           0 :         return arr_parse(obj, descr->array.element_descr,
     460           0 :                          descr->array.n_elements, field, val);
     461           0 :     case JSON_TOK_FALSE:
     462             :     case JSON_TOK_TRUE: {
     463           0 :         bool *v = field;
     464             : 
     465           0 :         *v = value->type == JSON_TOK_TRUE;
     466             : 
     467           0 :         return 0;
     468             :     }
     469           0 :     case JSON_TOK_NUMBER: {
     470           0 :         int32_t *num = field;
     471             : 
     472           0 :         return decode_num(value, num);
     473             :     }
     474           0 :     case JSON_TOK_STRING: {
     475           0 :         char **str = field;
     476             : 
     477           0 :         *value->end = '\0';
     478           0 :         *str = value->start;
     479             : 
     480           0 :         return 0;
     481             :     }
     482           0 :     default:
     483           0 :         return -EINVAL;
     484             :     }
     485             : }
     486             : 
     487          24 : static ptrdiff_t get_elem_size(const struct json_obj_descr *descr)
     488             : {
     489          24 :     switch (descr->type) {
     490          16 :     case JSON_TOK_NUMBER:
     491          16 :         return sizeof(int32_t);
     492           0 :     case JSON_TOK_STRING:
     493           0 :         return sizeof(char *);
     494           0 :     case JSON_TOK_TRUE:
     495             :     case JSON_TOK_FALSE:
     496           0 :         return sizeof(bool);
     497           0 :     case JSON_TOK_LIST_START:
     498           0 :         return (ptrdiff_t)descr->array.n_elements *
     499           0 :                get_elem_size(descr->array.element_descr);
     500           8 :     case JSON_TOK_OBJECT_START: {
     501           8 :         ptrdiff_t total = 0;
     502             :         size_t i;
     503             : 
     504          24 :         for (i = 0; i < descr->object.sub_descr_len; i++) {
     505          16 :             ptrdiff_t s = get_elem_size(&descr->object.sub_descr[i]);
     506             : 
     507          16 :             total += (ptrdiff_t)ROUND_UP(s, descr->object.sub_descr[i].align);
     508             :         }
     509             : 
     510           8 :         return total;
     511             :     }
     512           0 :     default:
     513           0 :         return -EINVAL;
     514             :     }
     515             : }
     516             : 
     517           0 : static int arr_parse(struct json_obj *obj,
     518             :                      const struct json_obj_descr *elem_descr,
     519             :                      size_t max_elements,
     520             :                      void *field,
     521             :                      void *val)
     522             : {
     523           0 :     ptrdiff_t elem_size = get_elem_size(elem_descr);
     524           0 :     void *last_elem = (char *)field + elem_size * (ptrdiff_t)max_elements;
     525           0 :     size_t *elements = (size_t *)((char *)val + elem_descr->offset);
     526             :     struct token value;
     527             : 
     528           0 :     assert(elem_size > 0);
     529             : 
     530           0 :     *elements = 0;
     531             : 
     532           0 :     while (!arr_next(obj, &value)) {
     533           0 :         if (value.type == JSON_TOK_LIST_END) {
     534           0 :             return 0;
     535             :         }
     536             : 
     537           0 :         if (UNLIKELY(field == last_elem)) {
     538           0 :             return -ENOSPC;
     539             :         }
     540             : 
     541           0 :         if (UNLIKELY(decode_value(obj, elem_descr, &value, field, val) < 0)) {
     542           0 :             return -EINVAL;
     543             :         }
     544             : 
     545           0 :         (*elements)++;
     546           0 :         field = (char *)field + elem_size;
     547             :     }
     548             : 
     549           0 :     return -EINVAL;
     550             : }
     551             : 
     552           0 : static int obj_parse(struct json_obj *obj,
     553             :                      const struct json_obj_descr *descr,
     554             :                      size_t descr_len,
     555             :                      void *val)
     556             : {
     557             :     struct json_obj_key_value kv;
     558           0 :     int32_t decoded_fields = 0;
     559             :     size_t i;
     560             :     int ret;
     561             : 
     562           0 :     while (!obj_next(obj, &kv)) {
     563           0 :         if (kv.value.type == JSON_TOK_OBJECT_END) {
     564           0 :             return decoded_fields;
     565             :         }
     566             : 
     567           0 :         for (i = 0; i < descr_len; i++) {
     568           0 :             void *decode_field = (char *)val + descr[i].offset;
     569             : 
     570             :             /* Field has been decoded already, skip */
     571           0 :             if (decoded_fields & (1 << i)) {
     572           0 :                 continue;
     573             :             }
     574             : 
     575             :             /* Check if it's the i-th field */
     576           0 :             if (kv.key_len != descr[i].field_name_len) {
     577           0 :                 continue;
     578             :             }
     579             : 
     580           0 :             if (memcmp(kv.key, descr[i].field_name, descr[i].field_name_len)) {
     581           0 :                 continue;
     582             :             }
     583             : 
     584             :             /* Store the decoded value */
     585           0 :             ret = decode_value(obj, &descr[i], &kv.value, decode_field, val);
     586           0 :             if (UNLIKELY(UNLIKELY(ret < 0))) {
     587           0 :                 return ret;
     588             :             }
     589             : 
     590           0 :             decoded_fields |= 1 << i;
     591           0 :             break;
     592             :         }
     593             :     }
     594             : 
     595           0 :     return -EINVAL;
     596             : }
     597             : 
     598           0 : int json_obj_parse(char *payload,
     599             :                    size_t len,
     600             :                    const struct json_obj_descr *descr,
     601             :                    size_t descr_len,
     602             :                    void *val)
     603             : {
     604             :     struct json_obj obj;
     605             :     int ret;
     606             : 
     607           0 :     assert(descr_len < (sizeof(ret) * CHAR_BIT - 1));
     608             : 
     609           0 :     ret = obj_init(&obj, payload, len);
     610           0 :     if (UNLIKELY(ret < 0)) {
     611           0 :         return ret;
     612             :     }
     613             : 
     614           0 :     return obj_parse(&obj, descr, descr_len, val);
     615             : }
     616             : 
     617             : /*
     618             :  * Routines has_zero() and has_value() are from
     619             :  * https://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord
     620             :  */
     621             : static ALWAYS_INLINE uint64_t has_zero(uint64_t v)
     622             : {
     623          13 :     return (v - 0x0101010101010101UL) & ~v & 0x8080808080808080UL;
     624             : }
     625             : 
     626             : static ALWAYS_INLINE uint64_t has_value(uint64_t x, char n)
     627             : {
     628          13 :     return has_zero(x ^ (~0UL / 255 * (uint64_t)n));
     629             : }
     630             : 
     631          13 : static char escape_as(char chr)
     632             : {
     633             :     static const char escaped[] = {'"', '\\', 'b', 'f', 'n', 'r', 't', 't'};
     634          13 :     uint64_t mask = has_value(0x225c080c0a0d0909UL, chr);
     635          13 :     return mask == 0 ? 0 : escaped[__builtin_clzl(mask) / 8];
     636             : }
     637             : 
     638           1 : static int json_escape_internal(const char *str,
     639             :                                 json_append_bytes_t append_bytes,
     640             :                                 void *data)
     641             : {
     642             :     const char *cur;
     643             :     const char *unescaped;
     644           1 :     int ret = 0;
     645             : 
     646          14 :     for (cur = unescaped = str; *cur; cur++) {
     647          13 :         char escaped = escape_as(*cur);
     648             : 
     649          13 :         if (escaped) {
     650           0 :             char bytes[2] = {'\\', escaped};
     651             : 
     652           0 :             if (cur - unescaped) {
     653           0 :                 ret |= append_bytes(unescaped, (size_t)(cur - unescaped), data);
     654           0 :                 unescaped = cur + 1;
     655             :             }
     656             : 
     657           0 :             ret |= append_bytes(bytes, 2, data);
     658             :         }
     659             :     }
     660             : 
     661           1 :     if (cur - unescaped)
     662           1 :         ret |= append_bytes(unescaped, (size_t)(cur - unescaped), data);
     663             : 
     664           1 :     return ret;
     665             : }
     666             : 
     667           0 : size_t json_calc_escaped_len(const char *str, size_t len)
     668             : {
     669           0 :     size_t escaped_len = len;
     670             :     size_t pos;
     671             : 
     672           0 :     for (pos = 0; pos < len; pos++) {
     673           0 :         if (escape_as(str[pos])) {
     674           0 :             escaped_len++;
     675             :         }
     676             :     }
     677             : 
     678           0 :     return escaped_len;
     679             : }
     680             : 
     681           0 : ssize_t json_escape(char *str, size_t *len, size_t buf_size)
     682             : {
     683             :     char *next; /* Points after next character to escape. */
     684             :     char *dest; /* Points after next place to write escaped character. */
     685           0 :     size_t escaped_len = json_calc_escaped_len(str, *len);
     686             : 
     687           0 :     if (escaped_len == *len) {
     688             :         /*
     689             :          * If no escape is necessary, there is nothing to do.
     690             :          */
     691           0 :         return 0;
     692             :     }
     693             : 
     694           0 :     if (UNLIKELY(escaped_len >= buf_size)) {
     695           0 :         return -ENOMEM;
     696             :     }
     697             : 
     698             :     /*
     699             :      * By walking backwards in the buffer from the end positions
     700             :      * of both the original and escaped strings, we avoid using
     701             :      * extra space. Characters in the original string are
     702             :      * overwritten only after they have already been escaped.
     703             :      */
     704           0 :     str[escaped_len] = '\0';
     705           0 :     for (next = &str[*len], dest = &str[escaped_len]; next != str;) {
     706           0 :         char next_c = *(--next);
     707           0 :         char escape = escape_as(next_c);
     708             : 
     709           0 :         if (escape) {
     710           0 :             *(--dest) = escape;
     711           0 :             *(--dest) = '\\';
     712             :         } else {
     713           0 :             *(--dest) = next_c;
     714             :         }
     715             :     }
     716           0 :     *len = escaped_len;
     717             : 
     718           0 :     return 0;
     719             : }
     720             : 
     721             : static int encode(const struct json_obj_descr *descr,
     722             :                   const void *val,
     723             :                   json_append_bytes_t append_bytes,
     724             :                   void *data,
     725             :                   bool escape_key);
     726             : 
     727           8 : static int arr_encode(const struct json_obj_descr *elem_descr,
     728             :                       const void *field,
     729             :                       const void *val,
     730             :                       json_append_bytes_t append_bytes,
     731             :                       void *data,
     732             :                       bool escape_key)
     733             : {
     734           8 :     ptrdiff_t elem_size = get_elem_size(elem_descr);
     735             :     /*
     736             :      * NOTE: Since an element descriptor's offset isn't meaningful (array
     737             :      * elements occur at multiple offsets in `val'), we use its space in
     738             :      * elem_descr to store the offset to the field containing the number of
     739             :      * elements.
     740             :      */
     741           8 :     size_t n_elem = *(size_t *)((char *)val + elem_descr->offset);
     742           8 :     int ret = append_bytes("[", 1, data);
     743             : 
     744           8 :     if (LIKELY(n_elem)) {
     745           8 :         n_elem--;
     746        1114 :         for (size_t i = 0; i < n_elem; i++) {
     747             :             /*
     748             :              * Though "field" points at the next element in the array which we
     749             :              * need to encode, the value in elem_descr->offset is actually the
     750             :              * offset of the length field in the "parent" struct containing the
     751             :              * array.
     752             :              *
     753             :              * To patch things up, we lie to encode() about where the field is
     754             :              * by exactly the amount it will offset it.  This is a size
     755             :              * optimization for struct json_obj_descr: the alternative is to
     756             :              * keep a separate field next to element_descr which is an offset to
     757             :              * the length field in the parent struct, but that would add a
     758             :              * size_t to every descriptor.
     759             :              */
     760        1106 :             ret |= encode(elem_descr, (char *)field - elem_descr->offset,
     761             :                           append_bytes, data, escape_key);
     762             : 
     763        1106 :             ret |= append_bytes(",", 1, data);
     764             : 
     765        1106 :             field = (char *)field + elem_size;
     766             :         }
     767             : 
     768           8 :         ret |= encode(elem_descr, (char *)field - elem_descr->offset,
     769             :                       append_bytes, data, escape_key);
     770             :     }
     771             : 
     772           8 :     return ret | append_bytes("]", 1, data);
     773             : }
     774             : 
     775           1 : static int str_encode(const char **str,
     776             :                       json_append_bytes_t append_bytes,
     777             :                       void *data)
     778             : {
     779           1 :     int ret = append_bytes("\"", 1, data);
     780             : 
     781           1 :     ret |= json_escape_internal(*str, append_bytes, data);
     782             : 
     783           1 :     return ret | append_bytes("\"", 1, data);
     784             : }
     785             : 
     786             : static int
     787        2230 : num_encode(const int32_t *num, json_append_bytes_t append_bytes, void *data)
     788             : {
     789             :     char buf[INT_TO_STR_BUFFER_SIZE];
     790             :     size_t len;
     791        2230 :     char *as_string = int_to_string(*num, buf, &len);
     792             : 
     793        2230 :     return append_bytes(as_string, len, data);
     794             : }
     795             : 
     796             : static int
     797           0 : bool_encode(const bool *value, json_append_bytes_t append_bytes, void *data)
     798             : {
     799           0 :     if (*value) {
     800           0 :         return append_bytes("true", 4, data);
     801             :     }
     802             : 
     803           0 :     return append_bytes("false", 5, data);
     804             : }
     805             : 
     806           8 : int json_arr_encode_full(const struct json_obj_descr *descr,
     807             :                          const void *val,
     808             :                          json_append_bytes_t append_bytes,
     809             :                          void *data,
     810             :                          bool escape_key)
     811             : {
     812           8 :     void *ptr = (char *)val + descr->offset;
     813             : 
     814           8 :     return arr_encode(descr->array.element_descr, ptr, val, append_bytes, data,
     815             :                       escape_key);
     816             : }
     817             : 
     818        3345 : static int encode(const struct json_obj_descr *descr,
     819             :                   const void *val,
     820             :                   json_append_bytes_t append_bytes,
     821             :                   void *data,
     822             :                   bool escape_key)
     823             : {
     824        3345 :     void *ptr = (char *)val + descr->offset;
     825             : 
     826        3345 :     switch (descr->type) {
     827           0 :     case JSON_TOK_FALSE:
     828             :     case JSON_TOK_TRUE:
     829           0 :         return bool_encode(ptr, append_bytes, data);
     830           1 :     case JSON_TOK_STRING:
     831           1 :         return str_encode(ptr, append_bytes, data);
     832           0 :     case JSON_TOK_LIST_START:
     833           0 :         return arr_encode(descr->array.element_descr, ptr, val,
     834             :                           append_bytes, data, escape_key);
     835        1114 :     case JSON_TOK_OBJECT_START:
     836        1114 :         return json_obj_encode_full(descr->object.sub_descr,
     837        1114 :                                     descr->object.sub_descr_len, ptr, append_bytes,
     838             :                                     data, escape_key);
     839        2230 :     case JSON_TOK_NUMBER:
     840        2230 :         return num_encode(ptr, append_bytes, data);
     841           0 :     default:
     842           0 :         return -EINVAL;
     843             :     }
     844             : }
     845             : 
     846        2231 : static inline int encode_key(const struct json_obj_descr *descr,
     847             :                              json_append_bytes_t append_bytes,
     848             :                              void *data,
     849             :                              bool escape_key)
     850             : {
     851             :     int ret;
     852             : 
     853        2231 :     if (!escape_key) {
     854             :         /* Keys are encoded twice in the descriptor; once without quotes and
     855             :          * the trailing comma, and one with.  Doing it like so cuts some
     856             :          * indirect calls to append_bytes(), which in turn also potentially
     857             :          * cuts some branches in most implementations of it.  */
     858        2231 :         ret = append_bytes(descr->field_name + descr->field_name_len,
     859        2231 :                            descr->field_name_len + 3 /* 3=len('"":') */, data);
     860             :     } else {
     861           0 :         ret = str_encode((const char **)&descr->field_name, append_bytes, data);
     862           0 :         ret |= append_bytes(":", 1, data);
     863             :     }
     864             : 
     865        2231 :     return ret;
     866             : }
     867             : 
     868        1116 : int json_obj_encode_full(const struct json_obj_descr *descr,
     869             :                          size_t descr_len,
     870             :                          const void *val,
     871             :                          json_append_bytes_t append_bytes,
     872             :                          void *data,
     873             :                          bool escape_key)
     874             : {
     875        1116 :     int ret = append_bytes("{", 1, data);
     876             : 
     877        1116 :     if (LIKELY(descr_len)) {
     878             :         /* To avoid checking if we're encoding the last element on each
     879             :          * iteration of this loop, start at the second descriptor, and always
     880             :          * write the comma. Then, after the loop, encode the first descriptor.
     881             :          * If the descriptor array has only 1 element, this loop won't run. This
     882             :          * is fine since order isn't important for objects, and we save some
     883             :          * branches.  */
     884             : 
     885        2231 :         for (size_t i = 1; i < descr_len; i++) {
     886        1115 :             ret |= encode_key(&descr[i], append_bytes, data, escape_key);
     887        1115 :             ret |= encode(&descr[i], val, append_bytes, data, escape_key);
     888        1115 :             ret |= append_bytes(",", 1, data);
     889             :         }
     890             : 
     891        1116 :         ret |= encode_key(&descr[0], append_bytes, data, escape_key);
     892        1116 :         ret |= encode(&descr[0], val, append_bytes, data, escape_key);
     893             :     }
     894             : 
     895        1116 :     return ret | append_bytes("}", 1, data);
     896             : }
     897             : 
     898             : struct appender {
     899             :     char *buffer;
     900             :     size_t used;
     901             :     size_t size;
     902             : };
     903             : 
     904           0 : static int append_bytes_to_buf(const char *bytes, size_t len, void *data)
     905             : {
     906           0 :     struct appender *appender = data;
     907             : 
     908           0 :     if (UNLIKELY(len > appender->size - appender->used)) {
     909           0 :         return -ENOMEM;
     910             :     }
     911             : 
     912           0 :     memcpy(appender->buffer + appender->used, bytes, len);
     913           0 :     appender->used += len;
     914           0 :     appender->buffer[appender->used] = '\0';
     915             : 
     916           0 :     return 0;
     917             : }
     918             : 
     919           0 : int json_obj_encode_buf(const struct json_obj_descr *descr,
     920             :                         size_t descr_len,
     921             :                         const void *val,
     922             :                         char *buffer,
     923             :                         size_t buf_size)
     924             : {
     925           0 :     struct appender appender = {.buffer = buffer, .size = buf_size};
     926             : 
     927           0 :     return json_obj_encode(descr, descr_len, val, append_bytes_to_buf,
     928             :                            &appender);
     929             : }
     930             : 
     931             : static int
     932           0 : measure_bytes(const char *bytes __attribute__((unused)), size_t len, void *data)
     933             : {
     934           0 :     ssize_t *total = data;
     935             : 
     936           0 :     *total += (ssize_t)len;
     937             : 
     938           0 :     return 0;
     939             : }
     940             : 
     941           0 : ssize_t json_calc_encoded_len(const struct json_obj_descr *descr,
     942             :                               size_t descr_len,
     943             :                               const void *val)
     944             : {
     945           0 :     ssize_t total = 0;
     946             :     int ret;
     947             : 
     948           0 :     ret = json_obj_encode(descr, descr_len, val, measure_bytes, &total);
     949           0 :     if (UNLIKELY(ret < 0)) {
     950           0 :         return ret;
     951             :     }
     952             : 
     953           0 :     return total;
     954             : }