sexp.c

   1 /* sexp.c
   2  *
   3  * Parsing s-expressions.
   4  */
   5
   6 /* nettle, low-level cryptographics library
   7  *
   8  * Copyright (C) 2002 Niels Möller
   9  *
  10  * The nettle library is free software; you can redistribute it and/or modify
  11  * it under the terms of the GNU Lesser General Public License as published by
  12  * the Free Software Foundation; either version 2.1 of the License, or (at your
  13  * option) any later version.
  14  *
  15  * The nettle library is distributed in the hope that it will be useful, but
  16  * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  17  * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  18  * License for more details.
  19  *
  20  * You should have received a copy of the GNU Lesser General Public License
  21  * along with the nettle library; see the file COPYING.LIB.  If not, write to
  22  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston,
  23  * MA 02111-1301, USA.
  24  */
  25
  26 #if HAVE_CONFIG_H
  27 # include "config.h"
  28 #endif
  29
  30 #include <stdlib.h>
  31 #include <string.h>
  32
  33 #include "sexp.h"
  34
  35 #include "macros.h"
  36 #include "nettle-internal.h"
  37
  38 /* Initializes the iterator, but one has to call next to get to the
  39  * first element. */
  40 static void
  41 sexp_iterator_init(struct sexp_iterator *iterator,
  42                    unsigned length, const uint8_t *input)
  43 {
  44   iterator->length = length;
  45   iterator->buffer = input;
  46   iterator->pos = 0;
  47   iterator->level = 0;
  48   iterator->type = SEXP_END; /* Value doesn't matter */
  49   iterator->display_length = 0;
  50   iterator->display = NULL;
  51   iterator->atom_length = 0;
  52   iterator->atom = NULL;
  53 }
  54
  55 #define EMPTY(i) ((i)->pos == (i)->length)
  56 #define NEXT(i) ((i)->buffer[(i)->pos++])
  57
  58 static int
  59 sexp_iterator_simple(struct sexp_iterator *iterator,
  60                      unsigned *size,
  61                      const uint8_t **string)
  62 {
  63   unsigned length = 0;
  64   uint8_t c;
  65
  66   if (EMPTY(iterator)) return 0;
  67   c = NEXT(iterator);
  68   if (EMPTY(iterator)) return 0;
  69
  70   if (c >= '1' && c <= '9')
  71     do
  72       {
  73         length = length * 10 + (c - '0');
  74         if (length > (iterator->length - iterator->pos))
  75           return 0;
  76
  77         if (EMPTY(iterator)) return 0;
  78         c = NEXT(iterator);
  79       }
  80     while (c >= '0' && c <= '9');
  81
  82   else if (c == '0')
  83     /* There can be only one */
  84     c = NEXT(iterator);
  85   else
  86     return 0;
  87
  88   if (c != ':')
  89     return 0;
  90
  91   *size = length;
  92   *string = iterator->buffer + iterator->pos;
  93   iterator->pos += length;
  94
  95   return 1;
  96 }
  97
  98 /* All these functions return 1 on success, 0 on failure */
  99
 100 /* Look at the current position in the data. Sets iterator->type, and
 101  * ignores the old value. */
 102
 103 static int
 104 sexp_iterator_parse(struct sexp_iterator *iterator)
 105 {
 106   iterator->start = iterator->pos;
 107
 108   if (EMPTY(iterator))
 109     {
 110       if (iterator->level)
 111         return 0;
 112
 113       iterator->type = SEXP_END;
 114       return 1;
 115     }
 116   switch (iterator->buffer[iterator->pos])
 117     {
 118     case '(': /* A list */
 119       iterator->type = SEXP_LIST;
 120       return 1;
 121
 122     case ')':
 123       if (!iterator->level)
 124         return 0;
 125
 126       iterator->pos++;
 127       iterator->type = SEXP_END;
 128       return 1;
 129
 130     case '[': /* Atom with display type */
 131       iterator->pos++;
 132       if (!sexp_iterator_simple(iterator,
 133                                 &iterator->display_length,
 134                                 &iterator->display))
 135         return 0;
 136       if (EMPTY(iterator) || NEXT(iterator) != ']')
 137         return 0;
 138
 139       break;
 140
 141     default:
 142       /* Must be either a decimal digit or a syntax error.
 143        * Errors are detected by sexp_iterator_simple. */
 144       iterator->display_length = 0;
 145       iterator->display = NULL;
 146
 147       break;
 148     }
 149
 150   iterator->type = SEXP_ATOM;
 151
 152   return sexp_iterator_simple(iterator,
 153                               &iterator->atom_length,
 154                               &iterator->atom);
 155 }
 156
 157 int
 158 sexp_iterator_first(struct sexp_iterator *iterator,
 159                     unsigned length, const uint8_t *input)
 160 {
 161   sexp_iterator_init(iterator, length, input);
 162   return sexp_iterator_parse(iterator);
 163 }
 164
 165 int
 166 sexp_iterator_next(struct sexp_iterator *iterator)
 167 {
 168   switch (iterator->type)
 169     {
 170     case SEXP_END:
 171       return 1;
 172     case SEXP_LIST:
 173       /* Skip this list */
 174       return sexp_iterator_enter_list(iterator)
 175         && sexp_iterator_exit_list(iterator);
 176     case SEXP_ATOM:
 177       /* iterator->pos should already point at the start of the next
 178        * element. */
 179       return sexp_iterator_parse(iterator);
 180     }
 181   /* If we get here, we have a bug. */
 182   abort();
 183 }
 184
 185 /* Current element must be a list. */
 186 int
 187 sexp_iterator_enter_list(struct sexp_iterator *iterator)
 188 {
 189   if (iterator->type != SEXP_LIST)
 190     return 0;
 191
 192   if (EMPTY(iterator) || NEXT(iterator) != '(')
 193     /* Internal error */
 194     abort();
 195
 196   iterator->level++;
 197
 198   return sexp_iterator_parse(iterator);
 199 }
 200
 201 /* Skips the rest of the current list */
 202 int
 203 sexp_iterator_exit_list(struct sexp_iterator *iterator)
 204 {
 205   if (!iterator->level)
 206     return 0;
 207
 208   while(iterator->type != SEXP_END)
 209     if (!sexp_iterator_next(iterator))
 210       return 0;
 211
 212   iterator->level--;
 213
 214   return sexp_iterator_parse(iterator);
 215 }
 216
 217 #if 0
 218 /* What's a reasonable interface for this? */
 219 int
 220 sexp_iterator_exit_lists(struct sexp_iterator *iterator,
 221                          unsigned level)
 222 {
 223   assert(iterator->level >= level);
 224
 225   while (iterator->level > level)
 226     if (!sexp_iterator_exit_list(iterator))
 227       return 0;
 228
 229   return 1;
 230 }
 231 #endif
 232
 233 const uint8_t *
 234 sexp_iterator_subexpr(struct sexp_iterator *iterator,
 235                       unsigned *length)
 236 {
 237   unsigned start = iterator->start;
 238   if (!sexp_iterator_next(iterator))
 239     return 0;
 240
 241   *length = iterator->start - start;
 242   return iterator->buffer + start;
 243 }
 244
 245 int
 246 sexp_iterator_get_uint32(struct sexp_iterator *iterator,
 247                          uint32_t *x)
 248 {
 249   if (iterator->type == SEXP_ATOM
 250       && !iterator->display
 251       && iterator->atom_length
 252       && iterator->atom[0] < 0x80)
 253     {
 254       unsigned length = iterator->atom_length;
 255       const uint8_t *p = iterator->atom;
 256
 257       /* Skip leading zeros. */
 258       while(length && !*p)
 259         {
 260           length--; p++;
 261         }
 262
 263       switch(length)
 264         {
 265         case 0:
 266           *x = 0;
 267           break;
 268         case 1:
 269           *x = p[0];
 270           break;
 271         case 2:
 272           *x = READ_UINT16(p);
 273           break;
 274         case 3:
 275           *x = READ_UINT24(p);
 276           break;
 277         case 4:
 278           *x = READ_UINT32(p);
 279           break;
 280         default:
 281           return 0;
 282         }
 283       return sexp_iterator_next(iterator);
 284     }
 285   return 0;
 286 }
 287
 288 int
 289 sexp_iterator_check_type(struct sexp_iterator *iterator,
 290                          const uint8_t *type)
 291 {
 292   return (sexp_iterator_enter_list(iterator)
 293           && iterator->type == SEXP_ATOM
 294           && !iterator->display
 295           && strlen(type) == iterator->atom_length
 296           && !memcmp(type, iterator->atom, iterator->atom_length)
 297           && sexp_iterator_next(iterator));
 298 }
 299
 300 const uint8_t *
 301 sexp_iterator_check_types(struct sexp_iterator *iterator,
 302                           unsigned ntypes,
 303                           const uint8_t * const *types)
 304 {
 305   if (sexp_iterator_enter_list(iterator)
 306       && iterator->type == SEXP_ATOM
 307       && !iterator->display)
 308     {
 309       unsigned i;
 310       for (i = 0; i<ntypes; i++)
 311         if (strlen(types[i]) == iterator->atom_length
 312             && !memcmp(types[i], iterator->atom,
 313                        iterator->atom_length))
 314           return sexp_iterator_next(iterator) ? types[i] : NULL;
 315     }
 316   return NULL;
 317 }
 318
 319 int
 320 sexp_iterator_assoc(struct sexp_iterator *iterator,
 321                     unsigned nkeys,
 322                     const uint8_t * const *keys,
 323                     struct sexp_iterator *values)
 324 {
 325   TMP_DECL(found, int, NETTLE_MAX_SEXP_ASSOC);
 326   unsigned nfound;
 327   unsigned i;
 328
 329   TMP_ALLOC(found, nkeys);
 330   for (i = 0; i<nkeys; i++)
 331     found[i] = 0;
 332
 333   nfound = 0;
 334
 335   for (;;)
 336     {
 337       switch (iterator->type)
 338         {
 339         case SEXP_LIST:
 340
 341           if (!sexp_iterator_enter_list(iterator))
 342             return 0;
 343
 344           if (iterator->type == SEXP_ATOM
 345               && !iterator->display)
 346             {
 347               /* Compare to the given keys */
 348               for (i = 0; i<nkeys; i++)
 349                 {
 350                   /* NOTE: The strlen could be put outside of the
 351                    * loop */
 352                   if (strlen(keys[i]) == iterator->atom_length
 353                       && !memcmp(keys[i], iterator->atom,
 354                                  iterator->atom_length))
 355                     {
 356                       if (found[i])
 357                         /* We don't allow duplicates */
 358                         return 0;
 359
 360                       /* Advance to point to value */
 361                       if (!sexp_iterator_next(iterator))
 362                         return 0;
 363
 364                       found[i] = 1;
 365                       nfound++;
 366
 367                       /* Record this position. */
 368                       values[i] = *iterator;
 369
 370                       break;
 371                     }
 372                 }
 373             }
 374           if (!sexp_iterator_exit_list(iterator))
 375             return 0;
 376           break;
 377         case SEXP_ATOM:
 378           /* Just ignore */
 379           if (!sexp_iterator_next(iterator))
 380             return 0;
 381           break;
 382
 383         case SEXP_END:
 384           return sexp_iterator_exit_list(iterator)
 385             && (nfound == nkeys);
 386
 387         default:
 388           abort();
 389         }
 390     }
 391 }