See ChangeLog: Tue Jul 13 17:39:25 CEST 1999 Werner Koch
[libgcrypt.git] / src / sexp.c
1 /* sexp.c  -  Sex^H^H-Expression handling
2  *      Copyright (C) 1999 Free Software Foundation, Inc.
3  *
4  * This file is part of GnuPG.
5  *
6  * GnuPG is free software; you can redistribute it and/or modify
7  * it under the terms of the GNU General Public License as published by
8  * the Free Software Foundation; either version 2 of the License, or
9  * (at your option) any later version.
10  *
11  * GnuPG is distributed in the hope that it will be useful,
12  * but WITHOUT ANY WARRANTY; without even the implied warranty of
13  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14  * GNU General Public License for more details.
15  *
16  * You should have received a copy of the GNU General Public License
17  * along with this program; if not, write to the Free Software
18  * Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA
19  */
20
21
22 /****************
23  * TODO:
24  *  - implement reference counting to defere freeing of
25  *    data and make copies of the data on demand.
26  *    --> do we really need this?
27  *
28  */
29
30 #include <config.h>
31 #include <stdio.h>
32 #include <stdlib.h>
33 #include <string.h>
34 #include <stdarg.h>
35 #include <ctype.h>
36 #include <assert.h>
37
38 #define GCRYPT_NO_MPI_MACROS 1
39 #include "g10lib.h"
40 #include "util.h"
41 #include "memory.h"
42
43
44 /* FIXME: We should really have the m_lib functions to allow
45  *        overriding of the default malloc functions
46  * For now use this kludge: */
47 #define m_lib_alloc        m_alloc
48 #define m_lib_alloc_clear  m_alloc_clear
49 #define m_lib_free         m_free
50
51
52
53
54 #if 0
55 struct sexp_node;
56 typedef struct sexp_node *NODE;
57
58 struct gcry_sexp {
59     int orig_format;  /* format which we used to create this object */
60     NODE sexp;        /* a NULL indicates an empty list */
61 };
62 #else
63 typedef struct gcry_sexp *NODE;
64 #endif
65
66
67 enum node_types { ntLIST, ntDATA, ntMPI };
68
69 struct gcry_sexp {
70     NODE next;
71     NODE up;        /* helper needed for faster traversal */
72     enum node_types type;
73     union {
74         NODE list;
75         GCRY_MPI mpi;
76         struct {
77             size_t len;
78             byte  d[1];
79         } data;
80     } u;
81 };
82
83
84 static void
85 dump_mpi( GCRY_MPI a )
86 {
87     char buffer[1000];
88     size_t n = 1000;
89
90     if( !a )
91         fputs("[no MPI]", stderr );
92     else if( gcry_mpi_print( GCRYMPI_FMT_HEX, buffer, &n, a ) )
93         fputs("[MPI too large to print]", stderr );
94     else
95         fputs( buffer, stderr );
96 }
97
98
99 static void
100 do_dump_list( NODE node, int indent )
101 {
102     for( ; node; node = node->next ) {
103         switch( node->type ) {
104           case ntLIST:
105             if( indent )
106                 putc('\n', stderr);
107             fprintf(stderr, "%*s(", indent, "");
108             do_dump_list( node->u.list, indent+1 );
109             putc(')', stderr);
110             break;
111           case ntDATA:
112             if( !node->u.data.len )
113                 fputs("EMPTY", stderr );
114             else
115                 print_string(stderr, node->u.data.d, node->u.data.len, ')');
116             putc(' ', stderr);
117             break;
118           case ntMPI:
119             dump_mpi( node->u.mpi );
120             putc(' ', stderr);
121             break;
122         }
123         if( !indent )
124             putc('\n', stderr);
125     }
126 }
127
128 static void
129 dump_sexp( NODE node )
130 {
131     do_dump_list( node, 0 );
132 }
133
134
135 /****************
136  * Create a new SEXP element (data)
137  */
138 GCRY_SEXP
139 gcry_sexp_new_data( const char *buffer, size_t length )
140 {
141     NODE node;
142
143     node = m_alloc_clear( sizeof *node + length );
144     node->type = ntDATA;
145     node->u.data.len = length;
146     memcpy(node->u.data.d, buffer, length );
147     return node;
148 }
149
150 /****************
151  * Release resource of the given SEXP object.
152  */
153 void
154 gcry_sexp_release( GCRY_SEXP sexp )
155 {
156 }
157
158
159
160
161 /****************
162  * Make a pair from items a and b
163  */
164 GCRY_SEXP
165 gcry_sexp_cons( GCRY_SEXP a, GCRY_SEXP b )
166 {
167     NODE head;
168
169     head = m_alloc_clear( sizeof *head );
170     head->type = ntLIST;
171     head->u.list = a;
172     a->up = head;
173     a->next = b;
174     b->up = head;
175     return head;
176 }
177
178 /****************
179  * Make a list from all items, the end of list is indicated by a NULL
180  */
181 GCRY_SEXP
182 gcry_sexp_vlist( GCRY_SEXP a, ... )
183 {
184     NODE head, tail, node;
185     va_list arg_ptr ;
186
187     head = m_alloc_clear( sizeof *node );
188     head->type = ntLIST;
189     head->u.list = a;
190     a->up = head;
191     tail = a;
192
193     va_start( arg_ptr, a ) ;
194     while( (node = va_arg( arg_ptr, NODE )) ) {
195         tail->next = node;
196         node->up = head;
197         tail = node;
198     }
199
200     va_end( arg_ptr );
201     return head;
202 }
203
204
205
206 /****************
207  * Locate data in a list. Data must be the first item in the list.
208  * Returns: The sublist with that Data (don't modify it!)
209  */
210 GCRY_SEXP
211 gcry_sexp_find_token( GCRY_SEXP list, const char *tok, size_t toklen )
212 {
213     NODE node;
214
215     if( !toklen )
216         toklen = strlen(tok);
217
218     for( node=list ; node; node = node->next )
219       {
220         switch( node->type ) {
221           case ntLIST: {
222                 NODE n = gcry_sexp_find_token( node->u.list, tok, toklen );
223                 if( n )
224                     return n;
225             }
226             break;
227           case ntDATA:
228             if( node == list
229                 && node->u.data.len == toklen
230                 && !memcmp( node->u.data.d, tok, toklen ) )
231               {
232                 return node;
233               }
234             break;
235           case ntMPI:
236             break;
237         }
238       }
239
240     return NULL;
241 }
242
243
244 /****************
245  * Enumerate all objects in the list.  Ther first time you call this, pass
246  * the address of a void pointer initialized to NULL.  Then don't touch this
247  * variable anymore but pass it verbatim to the function; you will get
248  * all lists back in turn. End of lists is indicated by a returned NIL in
249  * whic case you should not continue to use this function
250  * (it would wrap around).  If you decide to cancel the operation before
251  * the final NIL you vae to release the context by calling the function
252  * with a the context but a LIST set to NULL.
253  * Note that this function returns only lists and not single objects.
254  */
255 GCRY_SEXP
256 gcry_sexp_enum( GCRY_SEXP list, void **context, int mode )
257 {
258     NODE node;
259
260     if( mode )
261         return NULL; /* mode is reserved and must be 0 */
262     if( !list ) {
263         /* we are lucky that we can hold all information in the pointer
264          * value ;-) - so there is no need to release any memory */
265         *context = NULL;
266         return NULL;
267     }
268     if( !*context )  /* start enumeration */
269         node = list;
270     else {
271         node = *context;
272         node = node->next;
273     }
274
275     for( ; node; node = node->next ) {
276         *context = node; /* store our context */
277         if( node->type == ntLIST )
278             return node->u.list;
279         return node;
280     }
281
282     /* release resources and return nil */
283     return gcry_sexp_enum( NULL, context, mode );
284 }
285
286
287
288 /****************
289  * Get data from the car
290  */
291 const char *
292 gcry_sexp_car_data( GCRY_SEXP list, size_t *datalen )
293 {
294     if( list && list->type == ntDATA ) {
295         *datalen = list->u.data.len;
296         return list->u.data.d;
297     }
298
299     return NULL;
300 }
301
302 /****************
303  * Get data from the cdr assuming this is a pair
304  */
305 const char *
306 gcry_sexp_cdr_data( GCRY_SEXP list, size_t *datalen )
307 {
308     if( list && (list = list->next) && list->type == ntDATA ) {
309         *datalen = list->u.data.len;
310         return list->u.data.d;
311     }
312
313     return NULL;
314 }
315
316
317 /****************
318  * cdr the mpi from the list or NULL if there is no MPI.
319  * This function tries to convert plain data to an MPI.
320  * Actually this funtion returns only the second item of the list
321  * and ignores any further arguments.
322  */
323 MPI
324 gcry_sexp_cdr_mpi( GCRY_SEXP list, int mpifmt )
325 {
326     NODE node = list;
327
328     if( !node || !(node = node->next) || node == ntLIST )
329         return NULL;
330     if( node->type == ntDATA ) {
331         MPI a;
332         size_t n = node->u.data.len;
333         if( gcry_mpi_scan( &a, mpifmt, node->u.data.d, &n ) )
334             return NULL;
335         return a;
336     }
337     else if( node->type == ntMPI )
338         return gcry_mpi_copy( node->u.mpi );
339     else
340         return NULL;
341 }
342
343
344 /****************
345  * Check wether the car is equal to data
346  */
347 #if 0 /* not tested */
348 int
349 gcry_sexp_eqp_car( GCRY_SEXP list, const char *data, size_t datalen )
350 {
351     if( list && list->type == ntDATA
352         && list->u.data.len == datalen
353         && !memcmp( list->u.data.d, list, listlen ) )
354         return 1;
355
356     return 0;
357 }
358 #endif
359
360 /****************
361  * Scan the provided buffer and return the S expression in our internal
362  * format.  Returns a newly allocated expression.  If erroff is not NULL and
363  * a parsing error has occured, the offset into buffer will be returned.
364  */
365 int
366 gcry_sexp_sscan( GCRY_SEXP *retsexp, const char *buffer,
367                                      size_t length, size_t *erroff )
368 {
369     static const char tokenchars[] = "abcdefghijklmnopqrstuvwxyz"
370                                      "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
371                                      "0123456789-./_:*+=";
372     const char *p;
373     size_t n;
374     NODE head, tail, node;
375     const char *digptr=NULL;
376     const char *quoted=NULL;
377     const char *tokenp=NULL;
378     const char *hexfmt=NULL;
379     const char *base64=NULL;
380     const char *disphint=NULL;
381     int quoted_esc=0;
382     int datalen=0;
383     int first;
384
385     tail = head = NULL;
386     first = 0;
387     for(p=buffer,n=length; n; p++, n-- ) {
388         if( tokenp ) {
389             if( strchr( tokenchars, *p ) )
390                 continue;
391         }
392         if( quoted ) {
393             if( quoted_esc ) {
394                 switch( *p ) {
395                   case 'b': case 't': case 'v': case 'n': case 'f':
396                   case 'r': case '"': case '\'': case '\\':
397                     quoted_esc = 0;
398                     break;
399                   case '0': case '1': case '2': case '3': case '4':
400                   case '5': case '6': case '7':
401                     if( !(n > 2 && p[1] >= '0' && p[1] <= '7'
402                                 && p[2] >= '0' && p[2] <= '7') ) {
403                         *erroff = p - buffer;
404                         return -6;   /* invalid octal value */
405                     }
406                     p += 2; n -= 2;
407                     quoted_esc = 0;
408                     break;
409                   case 'x':
410                     if( !(n > 2 && isxdigit(p[1]) && isxdigit(p[2]) ) ) {
411                         *erroff = p - buffer;
412                         return -6;   /* invalid hex value */
413                     }
414                     p += 2; n -= 2;
415                     quoted_esc = 0;
416                     break;
417                   case '\r':  /* ignore CR[,LF] */
418                     if( n && p[1] == '\n' ) {
419                         p++; n--;
420                     }
421                     quoted_esc = 0;
422                     break;
423                   case '\n':  /* ignore LF[,CR] */
424                     if( n && p[1] == '\r' ) {
425                         p++; n--;
426                     }
427                     quoted_esc = 0;
428                     break;
429                   default:
430                     *erroff = p - buffer;
431                     return -6;   /* invalid quoted string escape */
432                 }
433             }
434             else if( *p == '\\' )
435                 quoted_esc = 1;
436             else if( *p == '\"' ) {
437                 /* fixme: add item */
438                 quoted = NULL;
439             }
440         }
441         else if( hexfmt ) {
442             if( *p == '#' )
443                hexfmt = NULL;
444         }
445         else if( base64 ) {
446             if( *p == '|' )
447                base64 = NULL;
448         }
449         else if( digptr ) {
450             if( isdigit(*p) )
451                 ;
452             else if( *p == ':' ) {
453                 if( !head ) {
454                     *erroff = 0;
455                     return -4;   /* not a list */
456                 }
457                 datalen = atoi( digptr ); /* fixme: check for overflow */
458                 digptr = NULL;
459                 if( datalen > n-1 ) {
460                     *erroff = p - buffer;
461                     return -2; /* buffer too short */
462                 }
463                 /* make a new list entry */
464                 node = m_alloc_clear( sizeof *node + datalen );
465                 if( first ) { /* stuff it into the first node */
466                     first = 0;
467                     node->up = tail;
468                     tail->u.list = node;
469                 }
470                 else {
471                     node->up = tail->up;
472                     tail->next = node;
473                 }
474                 tail = node;
475                 /* and fill in the value (we store the value in the node)*/
476                 node->type = ntDATA;
477                 node->u.data.len = datalen;
478                 memcpy(node->u.data.d, p+1, datalen );
479
480                 n -= datalen;
481                 p += datalen;
482             }
483             else if( *p == '\"' ) {
484                 digptr = NULL; /* we ignore the optional length */
485                 quoted = p;
486                 quoted_esc = 0;
487             }
488             else if( *p == '#' ) {
489                 digptr = NULL; /* we ignore the optional length */
490                 hexfmt = p;
491             }
492             else if( *p == '|' ) {
493                 digptr = NULL; /* we ignore the optional length */
494                 base64 = p;
495             }
496             else {
497                 *erroff = p - buffer;
498                 return -1;
499             }
500         }
501         else if( *p == '(' ) {
502             if( disphint ) {
503                 *erroff = p - buffer;
504                 return -9; /* open display hint */
505             }
506             node = m_alloc_clear( sizeof *node );
507             if( !head )
508                 head = node;
509             else {
510                 node->up = tail->up;
511                 tail->next = node;
512             }
513             node->type = ntLIST;
514             tail = node;
515             first = 1;
516         }
517         else if( *p == ')' ) { /* walk up */
518             if( disphint ) {
519                 *erroff = p - buffer;
520                 return -9; /* open display hint */
521             }
522             if( !head ) {
523                 *erroff = 0;
524                 return -4;   /* not a list */
525             }
526             tail = tail->up;
527             if( !tail ) {
528                 *erroff = p - buffer;
529                 return -3;
530             }
531         }
532         else if( *p == '\"' ) {
533             quoted = p;
534             quoted_esc = 0;
535         }
536         else if( *p == '#' )
537             hexfmt = p;
538         else if( *p == '|' )
539             base64 = p;
540         else if( *p == '[' ) {
541             if( disphint ) {
542                 *erroff = p - buffer;
543                 return -8; /* nested display hints */
544             }
545             disphint = p;
546         }
547         else if( *p == ']' ) {
548             if( !disphint ) {
549                 *erroff = p - buffer;
550                 return -9; /* unmatched display hint close */
551             }
552             disphint = NULL;
553         }
554         else if( isdigit(*p) ) {
555             if( *p == '0' ) { /* a length may not begin with zero */
556                 *erroff = p - buffer;
557                 return -7;
558             }
559             digptr = p;
560         }
561         else if( strchr( tokenchars, *p ) )
562             tokenp = p;
563         else if( isspace(*p) )
564             ;
565         else if( *p == '{' ) {
566             /* fixme: handle rescanning:
567              * we can do this by saving our current state
568              * and start over at p+1 -- Hmmm. At this point here
569              * we are in a well defined state, so we donĀ“ need to save
570              * it.  Great.
571              */
572             *erroff = p - buffer;
573             return -10; /* unexpected reserved punctuation */
574         }
575         else if( strchr( "&\\", *p ) ) { /*reserved punctuation*/
576             *erroff = p - buffer;
577             return -10; /* unexpected reserved punctuation */
578         }
579         else { /* bad or unavailable*/
580             *erroff = p - buffer;
581             return -5;
582         }
583
584     }
585     *retsexp = head;
586     return 0;
587 }
588
589
590 /****************
591  * Print SEXP to buffer using the MODE.  Returns the length of the
592  * SEXP in buffer or 0 if the buffer is too short (We have at least an
593  * empty list consisting of 2 bytes).  If a buffer of NULL is provided,
594  * the required length is returned.
595  */
596 size_t
597 gcry_sexp_sprint( GCRY_SEXP sexp, int mode, char *buffer, size_t maxlength )
598 {
599     return 0;
600 }
601
602
603
604 /***********************************************************/
605
606 const char *
607 strusage( int level )
608 {
609     return default_strusage(level);
610 }
611
612 int
613 main(int argc, char **argv)
614 {
615     char buffer[5000];
616     size_t erroff;
617     int rc, n;
618     FILE *fp;
619     GCRY_SEXP s_pk, s_dsa, s_p, s_q, s_g, sexp;
620
621   #if 1
622     fp = stdin;
623     n = fread(buffer, 1, 5000, fp );
624     rc = gcry_sexp_sscan( &sexp, buffer, n, &erroff );
625     if( rc ) {
626         fprintf(stderr, "parse error %d at offset %u\n", rc, erroff );
627         exit(1);
628     }
629   #else
630     s_pk = SEXP_NEW( "public-key", 10 );
631     fputs("pk:\n",stderr);dump_sexp( s_pk );
632     s_dsa = SEXP_NEW( "dsa", 3 );
633     s_p = SEXP_CONS( SEXP_NEW( "p", 1 ), SEXP_NEW( "PPPPPP", 6 ) );
634     fputs("p:\n",stderr);dump_sexp( s_p );
635     s_q = SEXP_CONS( SEXP_NEW( "q", 1 ), SEXP_NEW( "QQQ", 3 ) );
636     s_g = SEXP_CONS( SEXP_NEW( "g", 1 ), SEXP_NEW( "GGGGGG", 6 ) );
637     sexp = SEXP_CONS( s_pk, gcry_sexp_vlist( s_dsa,
638                                              s_p,
639                                              s_q,
640                                              s_g,
641                                              NULL ));
642     fputs("Here is what we have:\n",stderr);
643     dump_sexp( sexp );
644   #endif
645
646     /* now find something */
647     if( argc > 1 )
648       {
649         GCRY_SEXP s1;
650
651         s1 = gcry_sexp_find_token( sexp, argv[1], strlen(argv[1]) );
652         if( !s1 )
653           {
654             fprintf(stderr, "didn't found `%s'\n", argv[1] );
655           }
656         else
657           {
658             fprintf(stderr, "found `%s':\n", argv[1] );
659             dump_sexp( s1 );
660           }
661
662
663         if( argc > 2 ) /* get the MPI out of the list */
664         #if 0
665           {
666             GCRY_SEXP s2;
667             MPI a;
668
669             s2 = gcry_sexp_find_token( s1, argv[2], strlen(argv[2]) );
670             if( !s1 )
671             {
672                fprintf(stderr, "didn't found `%s'\n", argv[2] );
673                exit(1);
674             }
675
676             a = gcry_sexp_cdr_mpi( s2, GCRYMPI_FMT_USG );
677             if( a ) {
678                 fprintf(stderr, "MPI: ");
679                 dump_mpi( a );
680                 fprintf(stderr, "\n");
681             }
682             else
683                 fprintf(stderr, "cannot cdr a mpi\n" );
684           }
685          #else
686           {    /* print all MPIs */
687             void *ctx = NULL;
688             GCRY_SEXP s2;
689             MPI a;
690
691             while( (s2 = gcry_sexp_enum( s1, &ctx, 0 )) )
692               {
693                 const char *car_d;
694                 size_t car_n;
695
696                 car_d = gcry_sexp_car_data( s2, &car_n );
697                 if( car_d ) {
698                    fprintf(stderr, "CAR: %.*s=", (int)car_n, car_d );
699                    a = gcry_sexp_cdr_mpi( s2, GCRYMPI_FMT_USG );
700                    dump_mpi( a );
701                    fprintf(stderr, "\n");
702
703                 }
704                 else
705                     fprintf(stderr, "no CAR\n");
706               }
707           }
708          #endif
709       }
710     return 0;
711 }
712