git.samba.org - gd/nettle/blob - sexp.c

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