See ChangeLog: Thu Jul 8 16:21:27 CEST 1999 Werner Koch
[libgcrypt.git] / src / sexp.c
1 /* sexp.c  -  S-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( gcry_mpi_print( GCRYMPI_FMT_HEX, buffer, &n, a ) )
91         fputs("[MPI too large to print]", stderr );
92     else
93         fputs( buffer, stderr );
94 }
95
96
97 static void
98 do_dump_list( NODE node, int indent )
99 {
100     for( ; node; node = node->next ) {
101         switch( node->type ) {
102           case ntLIST:
103             if( indent )
104                 putc('\n', stderr);
105             fprintf(stderr, "%*s(", indent, "");
106             do_dump_list( node->u.list, indent+1 );
107             putc(')', stderr);
108             break;
109           case ntDATA:
110             if( !node->u.data.len )
111                 fputs("EMPTY", stderr );
112             else
113                 print_string(stderr, node->u.data.d, node->u.data.len, ')');
114             putc(' ', stderr);
115             break;
116           case ntMPI:
117             dump_mpi( node->u.mpi );
118             putc(' ', stderr);
119             break;
120         }
121         if( !indent )
122             putc('\n', stderr);
123     }
124 }
125
126 static void
127 dump_sexp( NODE node )
128 {
129     do_dump_list( node, 0 );
130 }
131
132
133 /****************
134  * Create a new SEXP element (data)
135  */
136 GCRY_SEXP
137 gcry_sexp_new( const char *buffer, size_t length )
138 {
139     NODE node;
140
141     node = m_alloc_clear( sizeof *node + length );
142     node->type = ntDATA;
143     node->u.data.len = length;
144     memcpy(node->u.data.d, buffer, length );
145     return node;
146 }
147
148 /****************
149  * Release resource of the given SEXP object.
150  */
151 void
152 gcry_sexp_release( GCRY_SEXP sexp )
153 {
154 }
155
156
157
158
159 /****************
160  * Make a pair from items a and b
161  */
162 GCRY_SEXP
163 gcry_sexp_cons( GCRY_SEXP a, GCRY_SEXP b )
164 {
165     NODE head;
166
167     head = m_alloc_clear( sizeof *head );
168     head->type = ntLIST;
169     head->u.list = a;
170     a->up = head;
171     a->next = b;
172     b->up = head;
173     return head;
174 }
175
176 /****************
177  * Make a list from all items, the end of list is indicated by a NULL
178  */
179 GCRY_SEXP
180 gcry_sexp_vlist( GCRY_SEXP a, ... )
181 {
182     NODE head, tail, node;
183     va_list arg_ptr ;
184
185     head = m_alloc_clear( sizeof *node );
186     head->type = ntLIST;
187     head->u.list = a;
188     a->up = head;
189     tail = a;
190
191     va_start( arg_ptr, a ) ;
192     while( (node = va_arg( arg_ptr, NODE )) ) {
193         tail->next = node;
194         node->up = head;
195         tail = node;
196     }
197
198     va_end( arg_ptr );
199     return head;
200 }
201
202
203
204
205
206
207
208
209
210 /****************
211  * Scan the provided buffer and return the S expression in our internal
212  * format.  Returns a newly allocated expression.  If erroff is not NULL and
213  * a parsing error has occured, the offset into buffer will be returned.
214  */
215 int
216 gcry_sexp_sscan( GCRY_SEXP *retsexp, const char *buffer,
217                                      size_t length, size_t *erroff )
218 {
219     static const char tokenchars[] = "abcdefghijklmnopqrstuvwxyz"
220                                      "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
221                                      "0123456789-./_:*+=";
222     const char *p;
223     size_t n;
224     NODE head, tail, node;
225     const char *digptr=NULL;
226     const char *quoted=NULL;
227     const char *tokenp=NULL;
228     const char *hexfmt=NULL;
229     const char *base64=NULL;
230     const char *disphint=NULL;
231     int quoted_esc=0;
232     int datalen=0;
233     int first;
234
235     tail = head = NULL;
236     first = 0;
237     for(p=buffer,n=length; n; p++, n-- ) {
238         if( tokenp ) {
239             if( strchr( tokenchars, *p ) )
240                 continue;
241         }
242         if( quoted ) {
243             if( quoted_esc ) {
244                 switch( *p ) {
245                   case 'b': case 't': case 'v': case 'n': case 'f':
246                   case 'r': case '"': case '\'': case '\\':
247                     quoted_esc = 0;
248                     break;
249                   case '0': case '1': case '2': case '3': case '4':
250                   case '5': case '6': case '7':
251                     if( !(n > 2 && p[1] >= '0' && p[1] <= '7'
252                                 && p[2] >= '0' && p[2] <= '7') ) {
253                         *erroff = p - buffer;
254                         return -6;   /* invalid octal value */
255                     }
256                     p += 2; n -= 2;
257                     quoted_esc = 0;
258                     break;
259                   case 'x':
260                     if( !(n > 2 && isxdigit(p[1]) && isxdigit(p[2]) ) ) {
261                         *erroff = p - buffer;
262                         return -6;   /* invalid hex value */
263                     }
264                     p += 2; n -= 2;
265                     quoted_esc = 0;
266                     break;
267                   case '\r':  /* ignore CR[,LF] */
268                     if( n && p[1] == '\n' ) {
269                         p++; n--;
270                     }
271                     quoted_esc = 0;
272                     break;
273                   case '\n':  /* ignore LF[,CR] */
274                     if( n && p[1] == '\r' ) {
275                         p++; n--;
276                     }
277                     quoted_esc = 0;
278                     break;
279                   default:
280                     *erroff = p - buffer;
281                     return -6;   /* invalid quoted string escape */
282                 }
283             }
284             else if( *p == '\\' )
285                 quoted_esc = 1;
286             else if( *p == '\"' ) {
287                 /* fixme: add item */
288                 quoted = NULL;
289             }
290         }
291         else if( hexfmt ) {
292             if( *p == '#' )
293                hexfmt = NULL;
294         }
295         else if( base64 ) {
296             if( *p == '|' )
297                base64 = NULL;
298         }
299         else if( digptr ) {
300             if( isdigit(*p) )
301                 ;
302             else if( *p == ':' ) {
303                 if( !head ) {
304                     *erroff = 0;
305                     return -4;   /* not a list */
306                 }
307                 datalen = atoi( digptr ); /* fixme: check for overflow */
308                 digptr = NULL;
309                 if( datalen > n-1 ) {
310                     *erroff = p - buffer;
311                     return -2; /* buffer too short */
312                 }
313                 /* make a new list entry */
314                 node = m_alloc_clear( sizeof *node + datalen );
315                 if( first ) { /* stuff it into the first node */
316                     first = 0;
317                     node->up = tail;
318                     tail->u.list = node;
319                 }
320                 else {
321                     node->up = tail->up;
322                     tail->next = node;
323                 }
324                 tail = node;
325                 /* and fill in the value (we store the value in the node)*/
326                 node->type = ntDATA;
327                 node->u.data.len = datalen;
328                 memcpy(node->u.data.d, p+1, datalen );
329
330                 n -= datalen;
331                 p += datalen;
332             }
333             else if( *p == '\"' ) {
334                 digptr = NULL; /* we ignore the optional length */
335                 quoted = p;
336                 quoted_esc = 0;
337             }
338             else if( *p == '#' ) {
339                 digptr = NULL; /* we ignore the optional length */
340                 hexfmt = p;
341             }
342             else if( *p == '|' ) {
343                 digptr = NULL; /* we ignore the optional length */
344                 base64 = p;
345             }
346             else {
347                 *erroff = p - buffer;
348                 return -1;
349             }
350         }
351         else if( *p == '(' ) {
352             if( disphint ) {
353                 *erroff = p - buffer;
354                 return -9; /* open display hint */
355             }
356             node = m_alloc_clear( sizeof *node );
357             if( !head )
358                 head = node;
359             else {
360                 node->up = tail->up;
361                 tail->next = node;
362             }
363             node->type = ntLIST;
364             tail = node;
365             first = 1;
366         }
367         else if( *p == ')' ) { /* walk up */
368             if( disphint ) {
369                 *erroff = p - buffer;
370                 return -9; /* open display hint */
371             }
372             if( !head ) {
373                 *erroff = 0;
374                 return -4;   /* not a list */
375             }
376             tail = tail->up;
377             if( !tail ) {
378                 *erroff = p - buffer;
379                 return -3;
380             }
381         }
382         else if( *p == '\"' ) {
383             quoted = p;
384             quoted_esc = 0;
385         }
386         else if( *p == '#' )
387             hexfmt = p;
388         else if( *p == '|' )
389             base64 = p;
390         else if( *p == '[' ) {
391             if( disphint ) {
392                 *erroff = p - buffer;
393                 return -8; /* nested display hints */
394             }
395             disphint = p;
396         }
397         else if( *p == ']' ) {
398             if( !disphint ) {
399                 *erroff = p - buffer;
400                 return -9; /* unmatched display hint close */
401             }
402             disphint = NULL;
403         }
404         else if( isdigit(*p) ) {
405             if( *p == '0' ) { /* a length may not begin with zero */
406                 *erroff = p - buffer;
407                 return -7;
408             }
409             digptr = p;
410         }
411         else if( strchr( tokenchars, *p ) )
412             tokenp = p;
413         else if( isspace(*p) )
414             ;
415         else if( *p == '{' ) {
416             /* fixme: handle rescanning:
417              * we can do this by saving our current state
418              * and start over at p+1 -- Hmmm. At this point here
419              * we are in a well defined state, so we donĀ“ need to save
420              * it.  Great.
421              */
422             *erroff = p - buffer;
423             return -10; /* unexpected reserved punctuation */
424         }
425         else if( strchr( "&\\", *p ) ) { /*reserved punctuation*/
426             *erroff = p - buffer;
427             return -10; /* unexpected reserved punctuation */
428         }
429         else { /* bad or unavailable*/
430             *erroff = p - buffer;
431             return -5;
432         }
433
434     }
435     dump_sexp( head );
436     return 0;
437 }
438
439
440 /****************
441  * Print SEXP to buffer using the MODE.  Returns the length of the
442  * SEXP in buffer or 0 if the buffer is too short (We have at least an
443  * empty list consisting of 2 bytes).  If a buffer of NULL is provided,
444  * the required length is returned.
445  */
446 size_t
447 gcry_sexp_sprint( GCRY_SEXP sexp, int mode, char *buffer, size_t maxlength )
448 {
449     return 0;
450 }
451
452
453
454 /***********************************************************/
455
456 const char *
457 strusage( int level )
458 {
459     return default_strusage(level);
460 }
461
462 int
463 main(int argc, char **argv)
464 {
465     char buffer[5000];
466     size_t erroff;
467     int rc, n;
468     FILE *fp;
469     GCRY_SEXP s_pk, s_dsa, s_p, s_q, s_g, sexp;
470
471     if( argc > 1 ) {
472         fp = fopen( argv[1], "r" );
473         if( !fp )
474             exit(1);
475         n = fread(buffer, 1, 5000, fp );
476         fprintf(stderr,"read %d bytes\n", n );
477         rc = gcry_sexp_sscan( NULL, buffer, n, &erroff );
478         fprintf(stderr, "read: rc=%d  erroff=%u\n", rc, erroff );
479     }
480
481     s_pk = SEXP_NEW( "public-key", 10 );
482     fputs("pk:\n",stderr);dump_sexp( s_pk );
483     s_dsa = SEXP_NEW( "dsa", 3 );
484     s_p = SEXP_CONS( SEXP_NEW( "p", 1 ), SEXP_NEW( "PPPPPP", 6 ) );
485     fputs("p:\n",stderr);dump_sexp( s_p );
486     s_q = SEXP_CONS( SEXP_NEW( "q", 1 ), SEXP_NEW( "QQQ", 3 ) );
487     s_g = SEXP_CONS( SEXP_NEW( "g", 1 ), SEXP_NEW( "GGGGGG", 6 ) );
488     sexp = SEXP_CONS( s_pk, gcry_sexp_vlist( s_dsa,
489                                              s_p,
490                                              s_q,
491                                              s_g,
492                                              NULL ));
493     fputs("all:\n",stderr);dump_sexp( sexp );
494
495     return 0;
496 }
497