2003-02-28 Moritz Schulte <moritz@g10code.com>
[libgcrypt.git] / src / sexp.c
1 /* sexp.c  -  S-Expression handling
2  *      Copyright (C) 1999, 2000, 2001, 2002 Free Software Foundation, Inc.
3  *
4  * This file is part of Libgcrypt.
5  *
6  * Libgcrypt is free software; you can redistribute it and/or modify
7  * it under the terms of the GNU Lesser general Public License as
8  * published by the Free Software Foundation; either version 2.1 of
9  * the License, or (at your option) any later version.
10  *
11  * Libgcrypt 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 Lesser General Public License for more details.
15  *
16  * You should have received a copy of the GNU Lesser General Public
17  * License 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 #include <config.h>
23 #include <stdio.h>
24 #include <stdlib.h>
25 #include <string.h>
26 #include <stdarg.h>
27 #include <ctype.h>
28 #include <assert.h>
29
30 #define GCRYPT_NO_MPI_MACROS 1
31 #include "g10lib.h"
32 #include "memory.h"
33
34 typedef struct gcry_sexp *NODE;
35 typedef unsigned short DATALEN;
36
37 struct gcry_sexp {
38     byte d[1];
39 };
40
41 #define ST_STOP  0
42 #define ST_DATA  1  /* datalen follows */
43 #define ST_HINT  2  /* datalen follows */
44 #define ST_OPEN  3
45 #define ST_CLOSE 4
46
47 /* the atoi macros assume that the buffer has only valid digits */
48 #define atoi_1(p)   (*(p) - '0' )
49 #define xtoi_1(p)   (*(p) <= '9'? (*(p)- '0'): \
50                      *(p) <= 'F'? (*(p)-'A'+10):(*(p)-'a'+10))
51 #define xtoi_2(p)   ((xtoi_1(p) * 16) + xtoi_1((p)+1))
52
53 #define TOKEN_SPECIALS  "-./_:*+="
54
55 #define OLDPARSECODE(a) (-((GCRYERR_SEXP_ ## a)-GCRYERR_SEXP_INV_LEN_SPEC+1))
56
57
58 static int
59 sexp_sscan( GCRY_SEXP *retsexp, size_t *erroff ,
60             const char *buffer, size_t length, va_list arg_ptr, int argflag);
61
62
63 #if 0
64 static void
65 dump_mpi( GCRY_MPI a )
66 {
67     char buffer[1000];
68     size_t n = 1000;
69
70     if( !a )
71         fputs("[no MPI]", stderr );
72     else if( gcry_mpi_print( GCRYMPI_FMT_HEX, buffer, &n, a ) )
73         fputs("[MPI too large to print]", stderr );
74     else
75         fputs( buffer, stderr );
76 }
77 #endif
78
79 static void
80 dump_string (const byte *p, size_t n, int delim )
81 {
82   for (; n; n--, p++ )
83     {
84       if ((*p & 0x80) || iscntrl( *p ) || *p == delim ) 
85         {
86           if( *p == '\n' )
87             log_printf ("\\n");
88           else if( *p == '\r' )
89             log_printf ("\\r");
90           else if( *p == '\f' )
91             log_printf ("\\f");
92           else if( *p == '\v' )
93             log_printf ("\\v");
94             else if( *p == '\b' )
95               log_printf ("\\b");
96           else if( !*p )       
97             log_printf ("\\0");
98           else
99             log_printf ("\\x%02x", *p );
100         }
101       else
102         log_printf ("%c", *p);
103     }
104 }
105
106
107 void
108 gcry_sexp_dump (const GCRY_SEXP a)
109 {
110   const byte *p;
111   int indent = 0;
112   int type;
113
114   if (!a)
115     {
116       log_printf ( "[nil]\n");
117       return;
118     }
119
120   p = a->d;
121   while ( (type = *p) != ST_STOP )
122     {
123       p++;
124       switch ( type )
125         {
126         case ST_OPEN:
127           log_printf ("%*s[open]\n", 2*indent, "");
128           indent++;
129           break;
130         case ST_CLOSE:
131           if( indent )
132             indent--;
133           log_printf ("%*s[close]\n", 2*indent, "");
134           break;
135         case ST_DATA: {
136           DATALEN n;
137           memcpy ( &n, p, sizeof n );
138           p += sizeof n;
139           log_printf ("%*s[data=\"", 2*indent, "" );
140           dump_string (p, n, '\"' );
141           log_printf ("\"]\n");
142           p += n;
143         }
144         break;
145         default:
146           log_printf ("%*s[unknown tag %d]\n", 2*indent, "", type);
147           break;
148         }
149     }
150 }
151
152 /****************
153  * Pass list through except when it is an empty list - in that case
154  * return NULL and release the passed list.
155  */
156 static GCRY_SEXP
157 normalize ( GCRY_SEXP list )
158 {
159     char *p;
160     if ( !list )
161         return NULL;
162     p = list->d;
163     if ( *p == ST_STOP ) {
164         /* this is "" */
165         gcry_sexp_release ( list );
166         return NULL;
167     }
168     if( *p == ST_OPEN && p[1] == ST_CLOSE ) {
169         /* this is "()" */
170         gcry_sexp_release ( list );
171         return NULL;
172     }
173
174     return list;
175 }
176
177 /* Create a new S-expression object by reading LENGTH bytes from
178    BUFFER, assuming it is canonilized encoded or autodetected encoding
179    when AUTODETECT is set to 1.  With FREEFNC not NULL, ownership of
180    the buffer is transferred to tyhe newle created object.  FREEFNC
181    should be the freefnc used to release BUFFER; there is no guarantee
182    at which point this function is called; most likey you want to use
183    free() or gcry_free(). 
184  
185    Passing LENGTH and AUTODETECT as 0 is allowed to indicate that
186    BUFFER points to a valid canonical encoded S-expression.  A LENGTH
187    of 0 and AUTODETECT 1 indicates that buffer points to a
188    null-terminated string.
189   
190    This function returns 0 and and the pointer to the new object in
191    RETSEXP or an error code in which case RETSEXP is set to NULL.  */
192 int 
193 gcry_sexp_create (GCRY_SEXP *retsexp, void *buffer, size_t length,
194                   int autodetect, void (*freefnc)(void*) )
195 {
196   int errcode;
197   GCRY_SEXP se;
198   volatile va_list dummy_arg_ptr;
199
200   if (!retsexp)
201     return GCRYERR_INV_ARG;
202   *retsexp = NULL;
203   if (autodetect < 0 || autodetect > 1 || !buffer)
204     return GCRYERR_INV_ARG;
205
206   if (!length && !autodetect)
207     { /* What a brave caller to assume that there is really a canonical
208          encoded S-expression in buffer */
209       length = gcry_sexp_canon_len (buffer, 0, NULL, &errcode);
210       if (!length)
211         return 200 - errcode;
212     }
213   else if (!length && autodetect)
214     { /* buffer is a string */
215       length = strlen ((char *)buffer);
216     }
217
218   errcode = sexp_sscan (&se, NULL, buffer, length, dummy_arg_ptr, 0);
219   if (errcode)
220     return 200 - errcode;
221
222   *retsexp = se;
223   if (freefnc)
224     {
225       /* For now we release the buffer immediately.  As soon as we
226          have changed the internal represenation of S-expression to
227          the canoncial format - which has the advantage of faster
228          parsing - we will use this function as a closure in our
229          GCRYSEXP object and use the BUFFER directly */
230       freefnc (buffer);
231     }
232   return 0;
233 }
234
235 /* Same as gcry_sexp_create but don't transfer ownership */
236 int
237 gcry_sexp_new (GCRY_SEXP *retsexp, const void *buffer, size_t length,
238                int autodetect)
239 {
240   return gcry_sexp_create (retsexp, (void *)buffer, length, autodetect, NULL);
241 }
242
243
244 /****************
245  * Release resource of the given SEXP object.
246  */
247 void
248 gcry_sexp_release( GCRY_SEXP sexp )
249 {
250     gcry_free ( sexp );
251 }
252
253
254 /****************
255  * Make a pair from lists a and b, don't use a or b later on.
256  * Special behaviour:  If one is a single element list we put the
257  * element straight into the new pair.
258  */
259 GCRY_SEXP
260 gcry_sexp_cons( const GCRY_SEXP a, const GCRY_SEXP b )
261 {
262     /* NYI: Implementation should be quite easy with our new data representation */
263     BUG ();
264     return NULL;
265 }
266
267
268 /****************
269  * Make a list from all items in the array the end of the array is marked
270  * with a NULL.                                                                       y a NULL
271  */
272 GCRY_SEXP
273 gcry_sexp_alist( const GCRY_SEXP *array )
274 {
275     /* NYI: Implementaion should be quite easy with our new data representation */
276     BUG ();
277     return NULL;
278 }
279
280 /****************
281  * Make a list from all items, the end of list is indicated by a NULL
282  */
283 GCRY_SEXP
284 gcry_sexp_vlist( const GCRY_SEXP a, ... )
285 {
286     /* NYI: Implementaion should be quite easy with our new data representation */
287     BUG ();
288     return NULL;
289 }
290
291
292 /****************
293  * Append n to the list a
294  * Returns: a new ist (which maybe a)
295  */
296 GCRY_SEXP
297 gcry_sexp_append( const GCRY_SEXP a, const GCRY_SEXP n )
298 {
299     /* NYI: Implementaion should be quite easy with our new data representation */
300     BUG ();
301     return NULL;
302 }
303
304 GCRY_SEXP
305 gcry_sexp_prepend( const GCRY_SEXP a, const GCRY_SEXP n )
306 {
307     /* NYI: Implementaion should be quite easy with our new data representation */
308     BUG ();
309     return NULL;
310 }
311
312
313
314 /****************
315  * Locate token in a list. The token must be the car of a sublist.
316  * Returns: A new list with this sublist or NULL if not found.
317  */
318 GCRY_SEXP
319 gcry_sexp_find_token( const GCRY_SEXP list, const char *tok, size_t toklen )
320 {
321     const byte *p;
322     DATALEN n;
323
324     if ( !list )
325         return NULL;
326
327     if( !toklen )
328         toklen = strlen(tok);
329     p = list->d;
330     while ( *p != ST_STOP ) {
331         if ( *p == ST_OPEN && p[1] == ST_DATA ) {
332             const byte *head = p;
333
334             p += 2;
335             memcpy ( &n, p, sizeof n ); p += sizeof n;
336             if ( n == toklen && !memcmp( p, tok, toklen ) ) { /* found it */
337                 GCRY_SEXP newlist;
338                 byte *d;
339                 int level = 1;
340
341                 /* look for the end of the list */
342                 for ( p += n; level; p++ ) {
343                     if ( *p == ST_DATA ) {
344                         memcpy ( &n, ++p, sizeof n );
345                         p += sizeof n + n;
346                         p--; /* compensate for later increment */
347                     }
348                     else if ( *p == ST_OPEN ) {
349                         level++;
350                     }
351                     else if ( *p == ST_CLOSE ) {
352                         level--;
353                     }
354                     else if ( *p == ST_STOP ) {
355                         BUG ();
356                     }
357                 } while ( level );
358                 n = p - head;
359
360                 newlist = gcry_xmalloc ( sizeof *newlist + n );
361                 d = newlist->d;
362                 memcpy ( d, head, n ); d += n;
363                 *d++ = ST_STOP;
364                 return normalize ( newlist );
365             }
366             p += n;
367         }
368         else if ( *p == ST_DATA ) {
369             memcpy ( &n, ++p, sizeof n ); p += sizeof n;
370             p += n;
371         }
372         else
373             p++;
374     }
375     return NULL;
376 }
377
378 /****************
379  * Return the length of the given list
380  */
381 int
382 gcry_sexp_length( const GCRY_SEXP list )
383 {
384     const byte *p;
385     DATALEN n;
386     int type;
387     int length = 0;
388     int level = 0;
389
390     if ( !list )
391         return 0;
392
393     p = list->d;
394     while ( (type=*p) != ST_STOP ) {
395         p++;
396         if ( type == ST_DATA ) {
397             memcpy ( &n, p, sizeof n );
398             p += sizeof n + n;
399             if ( level == 1 )
400                 length++;
401         }
402         else if ( type == ST_OPEN ) {
403             if ( level == 1 )
404                 length++;
405             level++;
406         }
407         else if ( type == ST_CLOSE ) {
408             level--;
409         }
410     }
411     return length;
412 }
413
414
415
416 /****************
417  * Extract the CAR of the given list
418  */
419 GCRY_SEXP
420 gcry_sexp_nth( const GCRY_SEXP list, int number )
421 {
422     const byte *p;
423     DATALEN n;
424     GCRY_SEXP newlist;
425     byte *d;
426     int level = 0;
427
428     if ( !list || list->d[0] != ST_OPEN )
429         return NULL;
430     p = list->d;
431
432     while ( number > 0 ) {
433         p++;
434         if ( *p == ST_DATA ) {
435             memcpy ( &n, ++p, sizeof n );
436             p += sizeof n + n;
437             p--;
438             if ( !level )
439                 number--;
440         }
441         else if ( *p == ST_OPEN ) {
442             level++;
443         }
444         else if ( *p == ST_CLOSE ) {
445             level--;
446             if ( !level )
447                 number--;
448         }
449         else if ( *p == ST_STOP ) {
450             return NULL;
451         }
452     }
453     p++;
454
455     if ( *p == ST_DATA ) {
456         memcpy ( &n, p, sizeof n ); p += sizeof n;
457         newlist = gcry_xmalloc ( sizeof *newlist + n + 1 );
458         d = newlist->d;
459         memcpy ( d, p, n ); d += n;
460         *d++ = ST_STOP;
461     }
462     else if ( *p == ST_OPEN ) {
463         const byte *head = p;
464
465         level = 1;
466         do {
467             p++;
468             if ( *p == ST_DATA ) {
469                 memcpy ( &n, ++p, sizeof n );
470                 p += sizeof n + n;
471                 p--;
472             }
473             else if ( *p == ST_OPEN ) {
474                 level++;
475             }
476             else if ( *p == ST_CLOSE ) {
477                 level--;
478             }
479             else if ( *p == ST_STOP ) {
480                 BUG ();
481             }
482         } while ( level );
483         n = p + 1 - head;
484
485         newlist = gcry_xmalloc ( sizeof *newlist + n );
486         d = newlist->d;
487         memcpy ( d, head, n ); d += n;
488         *d++ = ST_STOP;
489     }
490     else
491         newlist = NULL;
492
493     return normalize (newlist);
494 }
495
496 GCRY_SEXP
497 gcry_sexp_car( const GCRY_SEXP list )
498 {
499     return gcry_sexp_nth ( list, 0 );
500 }
501
502 /****************
503  * Get data from the car.  The returned value is valid as long as the list
504  * is not modified.
505  */
506 const char *
507 gcry_sexp_nth_data( const GCRY_SEXP list, int number, size_t *datalen )
508 {
509     const byte *p;
510     DATALEN n;
511     int level = 0;
512
513     *datalen = 0;
514     if ( !list ) {
515         return NULL;
516     }
517     p = list->d;
518     if ( *p == ST_OPEN )
519         p++;         /* yep, a list */
520     else if (number )
521         return NULL; /* not a list but an n > 0 element requested */
522
523     /* skip n elements */
524     while ( number > 0 ) {
525         if ( *p == ST_DATA ) {
526             memcpy ( &n, ++p, sizeof n );
527             p += sizeof n + n;
528             p--;
529             if ( !level )
530                 number--;
531         }
532         else if ( *p == ST_OPEN ) {
533             level++;
534         }
535         else if ( *p == ST_CLOSE ) {
536             level--;
537             if ( !level )
538                 number--;
539         }
540         else if ( *p == ST_STOP ) {
541             return NULL;
542         }
543         p++;
544     }
545
546
547     if ( *p == ST_DATA ) {
548         memcpy ( &n, ++p, sizeof n );
549         *datalen = n;
550         return p + sizeof n;
551     }
552
553     return NULL;
554 }
555
556 /****************
557  * Get a MPI from the car
558  */
559 GCRY_MPI
560 gcry_sexp_nth_mpi( GCRY_SEXP list, int number, int mpifmt )
561 {
562     const byte *p;
563     DATALEN n;
564     int level = 0;
565
566     if ( !list )
567         return NULL;
568     if ( !mpifmt )
569         mpifmt = GCRYMPI_FMT_STD;
570
571     p = list->d;
572     if ( *p == ST_OPEN )
573         p++;         /* yep, a list */
574     else if (number )
575         return NULL; /* not a list but an n > 0 element requested */
576
577     /* skip n elements */
578     while ( number > 0 ) {
579         if ( *p == ST_DATA ) {
580             memcpy ( &n, ++p, sizeof n );
581             p += sizeof n + n;
582             p--;
583             if ( !level )
584                 number--;
585         }
586         else if ( *p == ST_OPEN ) {
587             level++;
588         }
589         else if ( *p == ST_CLOSE ) {
590             level--;
591             if ( !level )
592                 number--;
593         }
594         else if ( *p == ST_STOP ) {
595             return NULL;
596         }
597         p++;
598     }
599
600     if ( *p == ST_DATA ) {
601         MPI a;
602         size_t nbytes;
603
604         memcpy ( &n, ++p, sizeof n );
605         p += sizeof n;
606         nbytes = n;
607         if( !gcry_mpi_scan( &a, mpifmt, p, &nbytes ) )
608             return a;
609     }
610
611     return NULL;
612 }
613
614
615 /****************
616  * Get the CDR
617  */
618 GCRY_SEXP
619 gcry_sexp_cdr( const GCRY_SEXP list )
620 {
621     const byte *p;
622     const byte *head;
623     DATALEN n;
624     GCRY_SEXP newlist;
625     byte *d;
626     int level = 0;
627     int skip = 1;
628
629     if ( !list || list->d[0] != ST_OPEN )
630         return NULL;
631     p = list->d;
632
633     while ( skip > 0 ) {
634         p++;
635         if ( *p == ST_DATA ) {
636             memcpy ( &n, ++p, sizeof n );
637             p += sizeof n + n;
638             p--;
639             if ( !level )
640                 skip--;
641         }
642         else if ( *p == ST_OPEN ) {
643             level++;
644         }
645         else if ( *p == ST_CLOSE ) {
646             level--;
647             if ( !level )
648                 skip--;
649         }
650         else if ( *p == ST_STOP ) {
651             return NULL;
652         }
653     }
654     p++;
655
656     head = p;
657     level = 0;
658     do {
659         if ( *p == ST_DATA ) {
660             memcpy ( &n, ++p, sizeof n );
661             p += sizeof n + n;
662             p--;
663         }
664         else if ( *p == ST_OPEN ) {
665             level++;
666         }
667         else if ( *p == ST_CLOSE ) {
668             level--;
669         }
670         else if ( *p == ST_STOP ) {
671             return NULL;
672         }
673         p++;
674     } while ( level );
675     n = p - head;
676
677     newlist = gcry_xmalloc ( sizeof *newlist + n + 2 );
678     d = newlist->d;
679     *d++ = ST_OPEN;
680     memcpy ( d, head, n ); d += n;
681     *d++ = ST_CLOSE;
682     *d++ = ST_STOP;
683
684     return normalize (newlist);
685 }
686
687 GCRY_SEXP
688 gcry_sexp_cadr ( const GCRY_SEXP list )
689 {
690     GCRY_SEXP a, b;
691
692     a = gcry_sexp_cdr ( list );
693     b = gcry_sexp_car ( a );
694     gcry_sexp_release ( a );
695     return b;
696 }
697
698
699
700 static int
701 hextobyte( const byte *s )
702 {
703     int c=0;
704
705     if( *s >= '0' && *s <= '9' )
706         c = 16 * (*s - '0');
707     else if( *s >= 'A' && *s <= 'F' )
708         c = 16 * (10 + *s - 'A');
709     else if( *s >= 'a' && *s <= 'f' ) {
710         c = 16 * (10 + *s - 'a');
711     }
712     s++;
713     if( *s >= '0' && *s <= '9' )
714         c += *s - '0';
715     else if( *s >= 'A' && *s <= 'F' )
716         c += 10 + *s - 'A';
717     else if( *s >= 'a' && *s <= 'f' ) {
718         c += 10 + *s - 'a';
719     }
720     return c;
721 }
722
723 struct make_space_ctx {
724     GCRY_SEXP sexp;
725     size_t allocated;
726     byte *pos;
727 };
728
729 static void
730 make_space ( struct make_space_ctx *c, size_t n )
731 {
732     size_t used = c->pos - c->sexp->d;
733
734     if ( used + n + sizeof(DATALEN) + 1 >= c->allocated ) {
735         GCRY_SEXP newsexp;
736         byte *newhead;
737
738         c->allocated += 2*(n+sizeof(DATALEN)+1);
739         newsexp = gcry_xrealloc ( c->sexp, sizeof *newsexp + c->allocated - 1 );
740         newhead = newsexp->d;
741         c->pos = newhead + used;
742         c->sexp = newsexp;
743     }
744 }
745
746
747 /* Unquote STRING of LENGTH and store it into BUF.  The surrounding
748    quotes are must already be removed from STRING.  We assume that the
749    quoted string is syntacillay correct.  */
750 static size_t
751 unquote_string (const unsigned char *string, size_t length, unsigned char *buf)
752 {
753   int esc = 0;
754   const unsigned char *s = string;
755   unsigned char *d = buf;
756   size_t n = length;
757
758   for (; n; n--, s++)
759     {
760       if (esc)
761         {
762           switch (*s)
763             {
764             case 'b':  *d++ = '\b'; break;
765             case 't':  *d++ = '\t'; break;
766             case 'v':  *d++ = '\v'; break;
767             case 'n':  *d++ = '\n'; break;
768             case 'f':  *d++ = '\f'; break;
769             case 'r':  *d++ = '\r'; break;
770             case '"':  *d++ = '\"'; break;
771             case '\'': *d++ = '\''; break;
772             case '\\': *d++ = '\\'; break;
773
774             case '\r':  /* ignore CR[,LF] */
775               if (n>1 && s[1] == '\n')
776                 {
777                   s++; n--;
778                 }
779               esc = 0;
780               break;
781               
782             case '\n':  /* ignore LF[,CR] */
783               if (n>1 && s[1] == '\r')
784                 {
785                   s++; n--;
786                 }
787               break;
788
789             case 'x': /* hex value */
790               if (n>2 && hexdigitp (s+1) && hexdigitp (s+2))
791                 {
792                   s++; n--;
793                   *d++ = xtoi_2 (s);
794                   s++; n--;
795                 }
796               break;
797
798             default:
799               if (n>2 && octdigitp (s) && octdigitp (s+1) && octdigitp (s+2))
800                 {
801                   *d++ = (atoi_1 (s)*64) + (atoi_1 (s+1)*8) + atoi_1 (s+2);
802                   s += 2;
803                   n -= 2;
804                 }
805               break;
806             }
807           esc = 0;
808         }
809       else if( *s == '\\' )
810         esc = 1;
811       else
812         *d++ = *s;
813     } 
814
815   return d - buf;
816 }
817
818 /****************
819  * Scan the provided buffer and return the S expression in our internal
820  * format.  Returns a newly allocated expression.  If erroff is not NULL and
821  * a parsing error has occured, the offset into buffer will be returned.
822  * If ARGFLAG is true, the function supports some printf like
823  * expressions.
824  *  These are:
825  *      %m - MPI
826  *      %s - string (no autoswitch to secure allocation)
827  *      %d - integer stored as string (no autoswitch to secure allocation)
828  *  all other format elements are currently not defined and return an error.
829  *  this includes the "%%" sequence becauce the percent sign is not an
830  *  allowed character.
831  * FIXME: We should find a way to store the secure-MPIS not in the string
832  * but as reference to somewhere - this can help us to save huge amounts
833  * of secure memory.  The problem is, that if only one element is secure, all
834  * other elements are automagicaly copied to secure meory too, so the most
835  * common operation gcry_sexp_cdr_mpi() will always return a secure MPI
836  * regardless whether it is needed or not.
837  */
838 static int
839 sexp_sscan( GCRY_SEXP *retsexp, size_t *erroff ,
840             const char *buffer, size_t length, va_list arg_ptr, int argflag )
841 {
842     static const char tokenchars[] = "abcdefghijklmnopqrstuvwxyz"
843                                      "ABCDEFGHIJKLMNOPQRSTUVWXYZ"
844                                      "0123456789-./_:*+=";
845     const char *p;
846     size_t n;
847     const char *digptr=NULL;
848     const char *quoted=NULL;
849     const char *tokenp=NULL;
850     const char *hexfmt=NULL;
851     const char *base64=NULL;
852     const char *disphint=NULL;
853     const char *percent=NULL;
854     int hexcount=0;
855     int quoted_esc=0;
856     int datalen=0;
857     size_t dummy_erroff;
858
859     struct make_space_ctx c;
860
861     if( !erroff )
862         erroff = &dummy_erroff;
863
864     /* FIXME: replace all the returns by a jump to the leave label
865      * and invent better error codes. Make sure that everything is cleaned up*/
866   #define MAKE_SPACE(n)  do { make_space ( &c, (n) ); } while (0)
867   #define STORE_LEN(p,n) do {                                              \
868                             DATALEN ashort = (n);                          \
869                             memcpy ( (p), &ashort, sizeof(ashort) );       \
870                             (p) += sizeof (ashort);                        \
871                         } while (0)
872
873     /* We assume that the internal representation takes less memory
874      * than the provided one.  However, we add space for one extra datalen
875      * so that the code which does the ST_CLOSE can use MAKE_SPACE */
876     c.allocated = length + sizeof(DATALEN);
877     c.sexp = gcry_xmalloc ( sizeof *c.sexp + c.allocated - 1 );
878     c.pos = c.sexp->d;
879
880     for(p=buffer,n=length; n; p++, n-- ) {
881         if( tokenp && !hexfmt ) {
882             if( strchr( tokenchars, *p ) )
883                 continue;
884             datalen = p - tokenp;
885             MAKE_SPACE ( datalen );
886             *c.pos++ = ST_DATA;
887             STORE_LEN ( c.pos, datalen );
888             memcpy ( c.pos, tokenp, datalen );
889             c.pos += datalen;
890             tokenp = NULL;
891         }
892         if( quoted ) {
893             if( quoted_esc ) {
894                 switch( *p ) {
895                   case 'b': case 't': case 'v': case 'n': case 'f':
896                   case 'r': case '"': case '\'': case '\\':
897                     quoted_esc = 0;
898                     break;
899                   case '0': case '1': case '2': case '3': case '4':
900                   case '5': case '6': case '7':
901                     if( !(n > 2 && p[1] >= '0' && p[1] <= '7'
902                                 && p[2] >= '0' && p[2] <= '7') ) {
903                         *erroff = p - buffer;
904                         return -6;   /* invalid octal value */
905                     }
906                     p += 2; n -= 2;
907                     quoted_esc = 0;
908                     break;
909                   case 'x':
910                     if( !(n > 2 && isxdigit(p[1]) && isxdigit(p[2]) ) ) {
911                         *erroff = p - buffer;
912                         return -6;   /* invalid hex value */
913                     }
914                     p += 2; n -= 2;
915                     quoted_esc = 0;
916                     break;
917                   case '\r':  /* ignore CR[,LF] */
918                     if( n && p[1] == '\n' ) {
919                         p++; n--;
920                     }
921                     quoted_esc = 0;
922                     break;
923                   case '\n':  /* ignore LF[,CR] */
924                     if( n && p[1] == '\r' ) {
925                         p++; n--;
926                     }
927                     quoted_esc = 0;
928                     break;
929                   default:
930                     *erroff = p - buffer;
931                     return -6;   /* invalid quoted string escape */
932                 }
933             }
934             else if( *p == '\\' )
935                 quoted_esc = 1;
936             else if( *p == '\"' ) {
937                 /* keep it easy - we know that the unquoted string will
938                    never be larger */
939                 char *save;
940                 size_t len;
941                 
942                 quoted++; /* skip leading quote */
943                 MAKE_SPACE (p - quoted);
944                 *c.pos++ = ST_DATA;
945                 save = c.pos;
946                 STORE_LEN (c.pos, 0); /* will be fixed up later */
947                 len = unquote_string (quoted, p - quoted, c.pos);
948                 c.pos += len;
949                 STORE_LEN (save, len);
950                 quoted = NULL;
951             }
952         }
953         else if( hexfmt ) {
954             if( isxdigit( *p ) )
955                 hexcount++;
956             else if( *p == '#' ) {
957                 if( (hexcount & 1) ) {
958                     *erroff = p - buffer;
959                     return OLDPARSECODE (ODD_HEX_NUMBERS);
960                 }
961
962                 datalen = hexcount/2;
963                 MAKE_SPACE (datalen);
964                 *c.pos++ = ST_DATA;
965                 STORE_LEN (c.pos, datalen);
966                 for( hexfmt++; hexfmt < p; hexfmt++ ) {
967                     if( isspace( *hexfmt ) )
968                         continue;
969                     *c.pos++ = hextobyte( hexfmt );
970                     hexfmt++;
971                 }
972                 hexfmt = NULL;
973             }
974             else if( !isspace( *p ) ) {
975                 *erroff = p - buffer;
976                 return OLDPARSECODE (BAD_HEX_CHAR);
977             }
978         }
979         else if( base64 ) {
980             if( *p == '|' )
981                base64 = NULL;
982         }
983         else if( digptr ) {
984             if( isdigit(*p) )
985                 ;
986             else if( *p == ':' ) {
987                 datalen = atoi( digptr ); /* fixme: check for overflow */
988                 digptr = NULL;
989                 if( datalen > n-1 ) {
990                     *erroff = p - buffer;
991                     return -2; /* buffer too short */
992                 }
993                 /* make a new list entry */
994                 MAKE_SPACE (datalen);
995                 *c.pos++ = ST_DATA;
996                 STORE_LEN (c.pos, datalen);
997                 memcpy (c.pos, p+1, datalen );
998                 c.pos += datalen;
999                 n -= datalen;
1000                 p += datalen;
1001             }
1002             else if( *p == '\"' ) {
1003                 digptr = NULL; /* we ignore the optional length */
1004                 quoted = p;
1005                 quoted_esc = 0;
1006             }
1007             else if( *p == '#' ) {
1008                 digptr = NULL; /* we ignore the optional length */
1009                 hexfmt = p;
1010                 hexcount = 0;
1011             }
1012             else if( *p == '|' ) {
1013                 digptr = NULL; /* we ignore the optional length */
1014                 base64 = p;
1015             }
1016             else {
1017                 *erroff = p - buffer;
1018                 return -1;
1019             }
1020         }
1021         else if ( percent ) {
1022             if ( *p == 'm' ) { /* insert an MPI */
1023                 GCRY_MPI m = va_arg (arg_ptr, GCRY_MPI);
1024                 size_t nm;
1025
1026                 if ( gcry_mpi_print( GCRYMPI_FMT_STD, NULL, &nm, m ) )
1027                     BUG ();
1028
1029                 MAKE_SPACE (nm);
1030                 if ( !gcry_is_secure ( c.sexp->d )
1031                      &&  gcry_mpi_get_flag ( m, GCRYMPI_FLAG_SECURE ) ) {
1032                     /* we have to switch to secure allocation */
1033                     GCRY_SEXP newsexp;
1034                     byte *newhead;
1035
1036                     newsexp = gcry_xmalloc_secure ( sizeof *newsexp
1037                                                    + c.allocated - 1 );
1038                     newhead = newsexp->d;
1039                     memcpy ( newhead, c.sexp->d, (c.pos - c.sexp->d) );
1040                     c.pos = newhead + ( c.pos - c.sexp->d );
1041                     gcry_free ( c.sexp );
1042                     c.sexp = newsexp;
1043                 }
1044
1045                 *c.pos++ = ST_DATA;
1046                 STORE_LEN (c.pos, nm);
1047                 if ( gcry_mpi_print( GCRYMPI_FMT_STD, c.pos, &nm, m ) )
1048                     BUG ();
1049                 c.pos += nm;
1050             }
1051             else if ( *p == 's' ) { /* insert an string */
1052                 const char *astr = va_arg (arg_ptr, const char *);
1053                 size_t alen = strlen ( astr );
1054
1055                 MAKE_SPACE (alen);
1056                 *c.pos++ = ST_DATA;
1057                 STORE_LEN (c.pos, alen);
1058                 memcpy ( c.pos, astr, alen );
1059                 c.pos += alen;
1060             }
1061             else if ( *p == 'd' ) { /* insert an integer as string */
1062                 int aint = va_arg (arg_ptr, int);
1063                 size_t alen;
1064                 char buf[20];
1065
1066                 sprintf ( buf, "%d", aint );
1067                 alen = strlen ( buf );
1068                 MAKE_SPACE (alen);
1069                 *c.pos++ = ST_DATA;
1070                 STORE_LEN (c.pos, alen);
1071                 memcpy ( c.pos, buf, alen );
1072                 c.pos += alen;
1073             }
1074             else {
1075                 *erroff = p - buffer;
1076                 return -1;  /* invalid format specifier */
1077             }
1078             percent = NULL;
1079         }
1080         else if( *p == '(' ) {
1081             if( disphint ) {
1082                 *erroff = p - buffer;
1083                 return -9; /* open display hint */
1084             }
1085             MAKE_SPACE (0);
1086             *c.pos++ = ST_OPEN;
1087         }
1088         else if( *p == ')' ) { /* walk up */
1089             if( disphint ) {
1090                 *erroff = p - buffer;
1091                 return -9; /* open display hint */
1092             }
1093             MAKE_SPACE (0);
1094             *c.pos++ = ST_CLOSE;
1095         }
1096         else if( *p == '\"' ) {
1097             quoted = p;
1098             quoted_esc = 0;
1099         }
1100         else if( *p == '#' ) {
1101             hexfmt = p;
1102             hexcount = 0;
1103         }
1104         else if( *p == '|' )
1105             base64 = p;
1106         else if( *p == '[' ) {
1107             if( disphint ) {
1108                 *erroff = p - buffer;
1109                 return -8; /* nested display hints */
1110             }
1111             disphint = p;
1112         }
1113         else if( *p == ']' ) {
1114             if( !disphint ) {
1115                 *erroff = p - buffer;
1116                 return -9; /* unmatched display hint close */
1117             }
1118             disphint = NULL;
1119         }
1120         else if( isdigit(*p) ) {
1121             if( *p == '0' ) { /* a length may not begin with zero */
1122                 *erroff = p - buffer;
1123                 return -7;
1124             }
1125             digptr = p;
1126         }
1127         else if( strchr( tokenchars, *p ) )
1128             tokenp = p;
1129         else if( isspace(*p) )
1130             ;
1131         else if( *p == '{' ) {
1132             /* fixme: handle rescanning:
1133              * we can do this by saving our current state
1134              * and start over at p+1 -- Hmmm. At this point here
1135              * we are in a well defined state, so we don't need to save
1136              * it.  Great.
1137              */
1138             *erroff = p - buffer;
1139             return -10; /* unexpected reserved punctuation */
1140         }
1141         else if( strchr( "&\\", *p ) ) { /*reserved punctuation*/
1142             *erroff = p - buffer;
1143             return -10; /* unexpected reserved punctuation */
1144         }
1145         else if( argflag && *p == '%' ) {
1146             percent = p;
1147         }
1148         else { /* bad or unavailable*/
1149             *erroff = p - buffer;
1150             return -5;
1151         }
1152
1153     }
1154     MAKE_SPACE (0);
1155     *c.pos++ = ST_STOP;
1156
1157     *retsexp = normalize ( c.sexp );
1158     return 0;
1159   #undef MAKE_SPACE
1160   #undef STORE_LEN
1161 }
1162
1163 int
1164 gcry_sexp_build( GCRY_SEXP *retsexp, size_t *erroff, const char *format, ... )
1165 {
1166     int rc;
1167     va_list arg_ptr ;
1168
1169     va_start( arg_ptr, format ) ;
1170     rc = sexp_sscan( retsexp, erroff, format, strlen(format), arg_ptr, 1 );
1171     va_end(arg_ptr);
1172
1173     return rc;
1174 }
1175
1176 int
1177 gcry_sexp_sscan( GCRY_SEXP *retsexp, size_t *erroff,
1178                             const char *buffer, size_t length )
1179 {
1180   /* We don't need the va_list because it is controlled by the
1181      following flag, however we have to pass it but can't initialize
1182      it as there is no portable way to do so.  volatile is needed to
1183      suppress the compiler warning */
1184   volatile va_list dummy_arg_ptr;
1185
1186   return sexp_sscan( retsexp, erroff, buffer, length, dummy_arg_ptr, 0 );
1187 }
1188
1189 \f
1190 /* Figure out a suitable encoding for BUFFER of LENGTH.
1191    Returns: 0 = Binary
1192             1 = String possible
1193             2 = Token possible
1194 */
1195 static int
1196 suitable_encoding (const unsigned char *buffer, size_t length)
1197 {
1198   const unsigned char *s;
1199   int maybe_token = 1;
1200
1201   if (!length)
1202     return 1;
1203   
1204   for (s=buffer; length; s++, length--)
1205     {
1206       if ( (*s < 0x20 || (*s >= 0x7f && *s <= 0xa0))
1207            && !strchr ("\b\t\v\n\f\r\"\'\\", *s))
1208         return 0; /*binary*/
1209       if ( maybe_token
1210            && !alphap (s) && !digitp (s)  && !strchr (TOKEN_SPECIALS, *s))
1211         maybe_token = 0;
1212     }
1213   s = buffer;
1214   if ( maybe_token && !digitp (s) )
1215     return 2;
1216   return 1;
1217 }
1218
1219
1220 static int
1221 convert_to_hex (const unsigned char *src, size_t len, unsigned char *dest)
1222 {
1223   int i;
1224
1225   if (dest)
1226     {
1227       *dest++ = '#';
1228       for (i=0; i < len; i++, dest += 2 )
1229         sprintf (dest, "%02X", src[i]);
1230       *dest++ = '#';
1231     }
1232   return len*2+2;
1233 }
1234
1235 static int
1236 convert_to_string (const unsigned char *s, size_t len, unsigned char *dest)
1237 {
1238   if (dest)
1239     {
1240       unsigned char *p = dest;
1241       *p++ = '\"';
1242       for (; len; len--, s++ )
1243         {
1244           switch (*s)
1245             {
1246             case '\b': *p++ = '\\'; *p++ = 'b';  break;
1247             case '\t': *p++ = '\\'; *p++ = 't';  break;
1248             case '\v': *p++ = '\\'; *p++ = 'v';  break;
1249             case '\n': *p++ = '\\'; *p++ = 'n';  break;
1250             case '\f': *p++ = '\\'; *p++ = 'f';  break;
1251             case '\r': *p++ = '\\'; *p++ = 'r';  break;
1252             case '\"': *p++ = '\\'; *p++ = '\"';  break;
1253             case '\'': *p++ = '\\'; *p++ = '\'';  break;
1254             case '\\': *p++ = '\\'; *p++ = '\\';  break;
1255             default: 
1256               if ( (*s < 0x20 || (*s >= 0x7f && *s <= 0xa0)))
1257                 {
1258                   sprintf (p, "\\x%02x", *s); 
1259                   p += 4;
1260                 }
1261               else
1262                 *p++ = *s;
1263             }
1264         }
1265       *p++ = '\"';
1266       return p - dest;
1267     }
1268   else
1269     {
1270       int count = 2;
1271       for (; len; len--, s++ )
1272         {
1273           switch (*s)
1274             {
1275             case '\b': 
1276             case '\t': 
1277             case '\v': 
1278             case '\n': 
1279             case '\f': 
1280             case '\r': 
1281             case '\"':
1282             case '\'':
1283             case '\\': count += 2; break;
1284             default: 
1285               if ( (*s < 0x20 || (*s >= 0x7f && *s <= 0xa0)))
1286                 count += 4;
1287               else
1288                 count++;
1289             }
1290         }
1291       return count;
1292     }
1293 }
1294
1295
1296
1297 static int
1298 convert_to_token (const unsigned char *src, size_t len, unsigned char *dest)
1299 {
1300   if (dest)
1301     memcpy (dest, src, len);
1302   return len;
1303 }
1304
1305
1306 /****************
1307  * Print SEXP to buffer using the MODE.  Returns the length of the
1308  * SEXP in buffer or 0 if the buffer is too short (We have at least an
1309  * empty list consisting of 2 bytes).  If a buffer of NULL is provided,
1310  * the required length is returned.
1311  */
1312 size_t
1313 gcry_sexp_sprint( const GCRY_SEXP list, int mode,
1314                                         char *buffer, size_t maxlength )
1315 {
1316   static byte empty[3] = { ST_OPEN, ST_CLOSE, ST_STOP };
1317   const byte *s;
1318   char *d;
1319   DATALEN n;
1320   char numbuf[20];
1321   size_t len = 0;
1322   int i, indent = 0;
1323   
1324   s = list? list->d : empty;
1325   d = buffer;
1326   while ( *s != ST_STOP )
1327     {
1328       switch ( *s )
1329         {
1330         case ST_OPEN:
1331           s++;
1332           if ( mode != GCRYSEXP_FMT_CANON )
1333             {
1334               if (indent)
1335                 len++; 
1336               len += indent;
1337             }
1338           len++;
1339           if ( buffer ) 
1340             {
1341               if ( len >= maxlength )
1342                 return 0;
1343               if ( mode != GCRYSEXP_FMT_CANON )
1344                 {
1345                   if (indent)
1346                     *d++ = '\n'; 
1347                   for (i=0; i < indent; i++)
1348                     *d++ = ' ';
1349                 }
1350               *d++ = '(';
1351             }
1352           indent++;
1353           break;
1354         case ST_CLOSE:
1355           s++;
1356           len++;
1357           if ( buffer ) 
1358             {
1359               if ( len >= maxlength )
1360                 return 0;
1361               *d++ = ')';
1362             }
1363           indent--;
1364           if (*s != ST_OPEN && *s != ST_STOP && mode != GCRYSEXP_FMT_CANON)
1365             {
1366               len++;
1367               len += indent;
1368               if (buffer)
1369                 {
1370                   if (len >= maxlength)
1371                     return 0;
1372                   *d++ = '\n';
1373                   for (i=0; i < indent; i++)
1374                     *d++ = ' ';
1375                 }
1376             }
1377           break;
1378         case ST_DATA:
1379           s++;
1380           memcpy ( &n, s, sizeof n ); s += sizeof n;
1381           if (mode == GCRYSEXP_FMT_ADVANCED)
1382             {
1383               int type;
1384               size_t nn;
1385
1386               switch ( (type=suitable_encoding (s, n)))
1387                 {
1388                 case 1: nn = convert_to_string (s, n, NULL); break;
1389                 case 2: nn = convert_to_token (s, n, NULL); break;
1390                 default: nn = convert_to_hex (s, n, NULL); break;
1391                 }
1392               len += nn;
1393               if (buffer)
1394                 {
1395                   if (len >= maxlength)
1396                     return 0;
1397                   switch (type)
1398                     {
1399                     case 1: convert_to_string (s, n, d); break;
1400                     case 2: convert_to_token (s, n, d); break;
1401                     default: convert_to_hex (s, n, d); break;
1402                     }
1403                   d += nn;
1404                 }
1405               if (s[n] != ST_CLOSE)
1406                 {
1407                   len++;
1408                   if (buffer)
1409                     {
1410                       if (len >= maxlength)
1411                         return 0;
1412                       *d++ = ' ';
1413                     }
1414                 }
1415             }
1416           else
1417             {
1418               sprintf (numbuf, "%u:", (unsigned int)n );
1419               len += strlen (numbuf) + n;
1420               if ( buffer ) 
1421                 {
1422                   if ( len >= maxlength )
1423                     return 0;
1424                   d = stpcpy ( d, numbuf );
1425                   memcpy ( d, s, n ); d += n;
1426                 }
1427             }
1428           s += n;
1429           break;
1430         default:
1431           BUG ();
1432         }
1433     }
1434   if ( mode != GCRYSEXP_FMT_CANON )
1435     {
1436       len++;
1437       if (buffer)
1438         {
1439           if ( len >= maxlength )
1440             return 0;
1441           *d++ = '\n'; 
1442         }
1443     }
1444   if (buffer) 
1445     {
1446       if ( len >= maxlength )
1447         return 0;
1448       *d++ = 0; /* for convenience we make a C string */
1449     }
1450   else
1451     len++; /* we need one byte more for this */
1452
1453   return len;
1454 }
1455
1456
1457
1458
1459 /* Scan a cannocial encoded buffer with implicit length values and
1460    return the actual length this S-expression uses.  For a valid S-Exp
1461    it should never return 0.  If LENGTH is not zero, the maximum
1462    length to scan is given - this can be used for syntax checks of
1463    data passed from outside. errorcode and erroff may both be passed as
1464    NULL
1465
1466    Errorcodes (for historic reasons they are all negative):
1467     -1 := invalid length specification
1468     -2 := string too long 
1469     -3 := unmatched parenthesis
1470     -4 := not a (canonical) S-expression
1471     -5 := bad character 
1472     -6 := invalid hex octal value or bad quotation
1473     -7 := a length may not begin with zero 
1474     -8 := nested display hints 
1475     -9 := unmatched display hint close
1476    -10 := unexpected reserved punctuation          
1477
1478    Use this formula to convert the errorcodes:
1479    gcryerr = 200 - errcode;
1480  */
1481 size_t
1482 gcry_sexp_canon_len (const unsigned char *buffer, size_t length, 
1483                      size_t *erroff, int *errcode)
1484 {
1485   const unsigned char *p;
1486   const char *disphint=NULL;
1487   unsigned int datalen = 0;
1488   size_t dummy_erroff;
1489   int    dummy_errcode;
1490   size_t count = 0;
1491   int level = 0;
1492
1493   if (!erroff)
1494     erroff = &dummy_erroff;
1495   if (!errcode)
1496     errcode = &dummy_errcode;
1497
1498   *errcode = 0;
1499   *erroff = 0;
1500   if (!buffer)
1501     return 0;
1502   if (*buffer != '(')
1503     {
1504       *errcode = OLDPARSECODE (NOT_CANONICAL);
1505       return 0;
1506     }
1507
1508   for (p=buffer; ; p++, count++ )
1509     {
1510       if (length && count >= length)
1511         {
1512           *erroff = count;
1513           *errcode = OLDPARSECODE (STRING_TOO_LONG); 
1514           return 0;
1515         }
1516       
1517       if (datalen)
1518         {
1519           if (*p == ':')
1520             {
1521               if (length && (count+datalen) >= length)
1522                 {
1523                   *erroff = count;
1524                   *errcode = OLDPARSECODE (STRING_TOO_LONG);
1525                   return 0;
1526                 }
1527               count += datalen;
1528               p += datalen;
1529               datalen = 0;
1530             }
1531           else if (digitp(p))
1532             datalen = datalen*10 + atoi_1(p);
1533           else 
1534             {
1535               *erroff = count;
1536               *errcode = OLDPARSECODE (INV_LEN_SPEC);
1537               return 0;
1538             }
1539         }
1540       else if (*p == '(')
1541         {
1542           if (disphint)
1543             {
1544               *erroff = count;
1545               *errcode = OLDPARSECODE (UNMATCHED_DH);
1546               return 0;
1547             }
1548           level++;
1549         }
1550       else if (*p == ')')
1551         { /* walk up */
1552           if (!level)
1553             {
1554               *erroff = count;
1555               *errcode = OLDPARSECODE (UNMATCHED_PAREN);
1556               return 0;
1557             }
1558           if (disphint)
1559             {
1560               *erroff = count;
1561               *errcode = OLDPARSECODE (UNMATCHED_DH);
1562               return 0;
1563             }
1564           if (!--level)
1565             return ++count; /* ready */
1566         }
1567       else if (*p == '[')
1568         {
1569           if (disphint) 
1570             {
1571               *erroff = count;
1572               *errcode = OLDPARSECODE (NESTED_DH);
1573               return 0;
1574             }
1575           disphint = p;
1576         }
1577       else if (*p == ']')
1578         {
1579           if( !disphint ) 
1580             {
1581               *erroff = count;
1582               *errcode = OLDPARSECODE (UNMATCHED_DH);
1583               return 0;
1584             }
1585           disphint = NULL;
1586         }
1587       else if (digitp (p) )
1588         {
1589           if (*p == '0')
1590             { 
1591               *erroff = count;
1592               *errcode = OLDPARSECODE (ZERO_PREFIX);
1593               return 0;
1594             }
1595           datalen = atoi_1 (p);
1596         }
1597       else if (*p == '&' || *p == '\\')
1598         {
1599           *erroff = count;
1600           *errcode = OLDPARSECODE (UNEXPECTED_PUNC);
1601           return 0;
1602         }
1603       else
1604         { 
1605           *erroff = count;
1606           *errcode = OLDPARSECODE (BAD_CHARACTER);
1607           return 0;
1608         }
1609     }
1610 }