source: trunk/libtransmission/bencode.c @ 8248

Last change on this file since 8248 was 8248, checked in by charles, 13 years ago

(trunk libT) minor benc cleanups

  • Property svn:keywords set to Date Rev Author Id
File size: 38.6 KB
Line 
1/*
2 * This file Copyright (C) 2008-2009 Charles Kerr <charles@transmissionbt.com>
3 *
4 * This file is licensed by the GPL version 2.  Works owned by the
5 * Transmission project are granted a special exemption to clause 2(b)
6 * so that the bulk of its code can remain under the MIT license.
7 * This exemption does not extend to derived works not owned by
8 * the Transmission project.
9 *
10 * $Id: bencode.c 8248 2009-04-16 21:01:00Z charles $
11 */
12
13#include <assert.h>
14#include <ctype.h> /* isdigit, isprint, isspace */
15#include <errno.h>
16#include <stdio.h>
17#include <stdlib.h>
18#include <string.h>
19
20#include <locale.h>
21
22#include <event.h> /* evbuffer */
23
24#include "ConvertUTF.h"
25
26#include "transmission.h"
27#include "bencode.h"
28#include "json.h"
29#include "list.h"
30#include "ptrarray.h"
31#include "utils.h" /* tr_new(), tr_free() */
32
33#ifndef ENODATA
34 #define ENODATA EIO
35#endif
36
37/**
38***
39**/
40
41static tr_bool
42isContainer( const tr_benc * val )
43{
44    return tr_bencIsList( val ) || tr_bencIsDict( val );
45}
46
47static tr_bool
48isSomething( const tr_benc * val )
49{
50    return isContainer( val ) || tr_bencIsInt( val )
51                              || tr_bencIsString( val )
52                              || tr_bencIsReal( val )
53                              || tr_bencIsBool( val );
54}
55
56static void
57tr_bencInit( tr_benc * val,
58             int       type )
59{
60    memset( val, 0, sizeof( *val ) );
61    val->type = type;
62}
63
64/***
65****  tr_bencParse()
66****  tr_bencLoad()
67***/
68
69/**
70 * The initial i and trailing e are beginning and ending delimiters.
71 * You can have negative numbers such as i-3e. You cannot prefix the
72 * number with a zero such as i04e. However, i0e is valid.
73 * Example: i3e represents the integer "3"
74 * NOTE: The maximum number of bit of this integer is unspecified,
75 * but to handle it as a signed 64bit integer is mandatory to handle
76 * "large files" aka .torrent for more that 4Gbyte
77 */
78int
79tr_bencParseInt( const uint8_t *  buf,
80                 const uint8_t *  bufend,
81                 const uint8_t ** setme_end,
82                 int64_t *        setme_val )
83{
84    int          err = 0;
85    char *       endptr;
86    const void * begin;
87    const void * end;
88    int64_t      val;
89
90    if( buf >= bufend )
91        return EILSEQ;
92    if( *buf != 'i' )
93        return EILSEQ;
94
95    begin = buf + 1;
96    end = memchr( begin, 'e', ( bufend - buf ) - 1 );
97    if( end == NULL )
98        return EILSEQ;
99
100    errno = 0;
101    val = evutil_strtoll( begin, &endptr, 10 );
102    if( errno || ( endptr != end ) ) /* incomplete parse */
103        err = EILSEQ;
104    else if( val && *(const char*)begin == '0' ) /* no leading zeroes! */
105        err = EILSEQ;
106    else
107    {
108        *setme_end = (const uint8_t*)end + 1;
109        *setme_val = val;
110    }
111
112    return err;
113}
114
115/**
116 * Byte strings are encoded as follows:
117 * <string length encoded in base ten ASCII>:<string data>
118 * Note that there is no constant beginning delimiter, and no ending delimiter.
119 * Example: 4:spam represents the string "spam"
120 */
121int
122tr_bencParseStr( const uint8_t *  buf,
123                 const uint8_t *  bufend,
124                 const uint8_t ** setme_end,
125                 const uint8_t ** setme_str,
126                 size_t *         setme_strlen )
127{
128    size_t       len;
129    const void * end;
130    char *       endptr;
131
132    if( buf >= bufend )
133        return EILSEQ;
134
135    if( !isdigit( *buf  ) )
136        return EILSEQ;
137
138    end = memchr( buf, ':', bufend - buf );
139    if( end == NULL )
140        return EILSEQ;
141
142    errno = 0;
143    len = strtoul( (const char*)buf, &endptr, 10 );
144    if( errno || endptr != end )
145        return EILSEQ;
146
147    if( (const uint8_t*)end + 1 + len > bufend )
148        return EILSEQ;
149
150    *setme_end = (const uint8_t*)end + 1 + len;
151    *setme_str = (const uint8_t*)end + 1;
152    *setme_strlen = len;
153    return 0;
154}
155
156/* set to 1 to help expose bugs with tr_bencListAdd and tr_bencDictAdd */
157#define LIST_SIZE 8 /* number of items to increment list/dict buffer by */
158
159static int
160makeroom( tr_benc * val,
161          size_t    count )
162{
163    assert( TR_TYPE_LIST == val->type || TR_TYPE_DICT == val->type );
164
165    if( val->val.l.count + count > val->val.l.alloc )
166    {
167        /* We need a bigger boat */
168        const int len = val->val.l.alloc + count +
169                        ( count % LIST_SIZE ? LIST_SIZE -
170                          ( count % LIST_SIZE ) : 0 );
171        void * tmp = realloc( val->val.l.vals, len * sizeof( tr_benc ) );
172        if( !tmp )
173            return 1;
174
175        val->val.l.alloc = len;
176        val->val.l.vals  = tmp;
177    }
178
179    return 0;
180}
181
182static tr_benc*
183getNode( tr_benc *     top,
184         tr_ptrArray * parentStack,
185         int           type )
186{
187    tr_benc * parent;
188
189    assert( top );
190    assert( parentStack );
191
192    if( tr_ptrArrayEmpty( parentStack ) )
193        return top;
194
195    parent = tr_ptrArrayBack( parentStack );
196    assert( parent );
197
198    /* dictionary keys must be strings */
199    if( ( parent->type == TR_TYPE_DICT )
200      && ( type != TR_TYPE_STR )
201      && ( !( parent->val.l.count % 2 ) ) )
202        return NULL;
203
204    makeroom( parent, 1 );
205    return parent->val.l.vals + parent->val.l.count++;
206}
207
208/**
209 * This function's previous recursive implementation was
210 * easier to read, but was vulnerable to a smash-stacking
211 * attack via maliciously-crafted bencoded data. (#667)
212 */
213static int
214tr_bencParseImpl( const void *     buf_in,
215                  const void *     bufend_in,
216                  tr_benc *        top,
217                  tr_ptrArray *    parentStack,
218                  const uint8_t ** setme_end )
219{
220    int             err;
221    const uint8_t * buf = buf_in;
222    const uint8_t * bufend = bufend_in;
223
224    tr_bencInit( top, 0 );
225
226    while( buf != bufend )
227    {
228        if( buf > bufend ) /* no more text to parse... */
229            return 1;
230
231        if( *buf == 'i' ) /* int */
232        {
233            int64_t         val;
234            const uint8_t * end;
235            tr_benc *       node;
236
237            if( ( err = tr_bencParseInt( buf, bufend, &end, &val ) ) )
238                return err;
239
240            node = getNode( top, parentStack, TR_TYPE_INT );
241            if( !node )
242                return EILSEQ;
243
244            tr_bencInitInt( node, val );
245            buf = end;
246
247            if( tr_ptrArrayEmpty( parentStack ) )
248                break;
249        }
250        else if( *buf == 'l' ) /* list */
251        {
252            tr_benc * node = getNode( top, parentStack, TR_TYPE_LIST );
253            if( !node )
254                return EILSEQ;
255            tr_bencInit( node, TR_TYPE_LIST );
256            tr_ptrArrayAppend( parentStack, node );
257            ++buf;
258        }
259        else if( *buf == 'd' ) /* dict */
260        {
261            tr_benc * node = getNode( top, parentStack, TR_TYPE_DICT );
262            if( !node )
263                return EILSEQ;
264            tr_bencInit( node, TR_TYPE_DICT );
265            tr_ptrArrayAppend( parentStack, node );
266            ++buf;
267        }
268        else if( *buf == 'e' ) /* end of list or dict */
269        {
270            tr_benc * node;
271            ++buf;
272            if( tr_ptrArrayEmpty( parentStack ) )
273                return EILSEQ;
274
275            node = tr_ptrArrayBack( parentStack );
276            if( tr_bencIsDict( node ) && ( node->val.l.count % 2 ) )
277            {
278                /* odd # of children in dict */
279                tr_bencFree( &node->val.l.vals[--node->val.l.count] );
280                return EILSEQ;
281            }
282
283            tr_ptrArrayPop( parentStack );
284            if( tr_ptrArrayEmpty( parentStack ) )
285                break;
286        }
287        else if( isdigit( *buf ) ) /* string? */
288        {
289            const uint8_t * end;
290            const uint8_t * str;
291            size_t          str_len;
292            tr_benc *       node;
293
294            if( ( err = tr_bencParseStr( buf, bufend, &end, &str, &str_len ) ) )
295                return err;
296
297            node = getNode( top, parentStack, TR_TYPE_STR );
298            if( !node )
299                return EILSEQ;
300
301            tr_bencInitStr( node, str, str_len );
302            buf = end;
303
304            if( tr_ptrArrayEmpty( parentStack ) )
305                break;
306        }
307        else /* invalid bencoded text... march past it */
308        {
309            ++buf;
310        }
311    }
312
313    err = !isSomething( top ) || !tr_ptrArrayEmpty( parentStack );
314
315    if( !err && setme_end )
316        *setme_end = buf;
317
318    return err;
319}
320
321int
322tr_bencParse( const void *     buf,
323              const void *     end,
324              tr_benc *        top,
325              const uint8_t ** setme_end )
326{
327    int           err;
328    tr_ptrArray   parentStack = TR_PTR_ARRAY_INIT;
329
330    top->type = 0; /* set to `uninitialized' */
331    err = tr_bencParseImpl( buf, end, top, &parentStack, setme_end );
332    if( err )
333        tr_bencFree( top );
334
335    tr_ptrArrayDestruct( &parentStack, NULL );
336    return err;
337}
338
339int
340tr_bencLoad( const void * buf_in,
341             size_t       buflen,
342             tr_benc *    setme_benc,
343             char **      setme_end )
344{
345    const uint8_t * buf = buf_in;
346    const uint8_t * end;
347    const int       ret = tr_bencParse( buf, buf + buflen, setme_benc, &end );
348
349    if( !ret && setme_end )
350        *setme_end = (char*) end;
351    return ret;
352}
353
354/***
355****
356***/
357
358static int
359dictIndexOf( const tr_benc * val,
360             const char *    key )
361{
362    if( tr_bencIsDict( val ) )
363    {
364        size_t       i;
365        const size_t len = strlen( key );
366
367        for( i = 0; ( i + 1 ) < val->val.l.count; i += 2 )
368        {
369            const tr_benc * child = val->val.l.vals + i;
370
371            if( ( child->type == TR_TYPE_STR )
372              && ( child->val.s.i == len )
373              && !memcmp( child->val.s.s, key, len ) )
374                return i;
375        }
376    }
377
378    return -1;
379}
380
381tr_benc *
382tr_bencDictFind( tr_benc * val, const char * key )
383{
384    const int i = dictIndexOf( val, key );
385
386    return i < 0 ? NULL : &val->val.l.vals[i + 1];
387}
388
389static tr_bool
390tr_bencDictFindType( tr_benc * dict, const char * key, int type, tr_benc ** setme )
391{
392    return tr_bencIsType( *setme = tr_bencDictFind( dict, key ), type );
393}
394
395size_t
396tr_bencListSize( const tr_benc * list )
397{
398    return tr_bencIsList( list ) ? list->val.l.count : 0;
399}
400
401tr_benc*
402tr_bencListChild( tr_benc * val,
403                  size_t    i )
404{
405    tr_benc * ret = NULL;
406
407    if( tr_bencIsList( val ) && ( i < val->val.l.count ) )
408        ret = val->val.l.vals + i;
409    return ret;
410}
411
412static void
413tr_benc_warning( const char * err )
414{
415    fprintf( stderr, "warning: %s\n", err );
416}
417
418tr_bool
419tr_bencGetInt( const tr_benc * val,
420               int64_t *       setme )
421{
422    tr_bool success = FALSE;
423
424    if( !success && (( success = tr_bencIsInt( val ))))
425        if( setme )
426            *setme = val->val.i;
427
428    if( !success && (( success = tr_bencIsBool( val )))) {
429        tr_benc_warning( "reading bool as an int" );
430        if( setme )
431            *setme = val->val.b ? 1 : 0;
432    }
433
434    return success;
435}
436
437tr_bool
438tr_bencGetStr( const tr_benc * val,
439               const char **   setme )
440{
441    const int success = tr_bencIsString( val );
442
443    if( success )
444        *setme = val->val.s.s;
445
446    return success;
447}
448
449tr_bool
450tr_bencGetBool( const tr_benc * val, tr_bool * setme )
451{
452    tr_bool success = FALSE;
453
454    if(( success = tr_bencIsBool( val )))
455        *setme = val->val.b;
456
457    if( !success && tr_bencIsInt( val ) )
458        if(( success = ( val->val.i==0 || val->val.i==1 ) ))
459            *setme = val->val.i!=0;
460
461    if( !success && tr_bencIsString( val ) )
462        if(( success = ( !strcmp(val->val.s.s,"true") || !strcmp(val->val.s.s,"false"))))
463            *setme = !strcmp(val->val.s.s,"true");
464
465    return success;
466}
467
468tr_bool
469tr_bencGetReal( const tr_benc * val, double * setme )
470{
471    tr_bool success = FALSE;
472
473    if( !success && (( success = tr_bencIsReal( val ))))
474        *setme = val->val.d;
475
476    if( !success && (( success = tr_bencIsInt( val ))))
477        *setme = val->val.i;
478
479    if( !success && tr_bencIsString(val) )
480    {
481        char * endptr;
482        char * locale; 
483        double d;
484
485        /* the json spec requires a '.' decimal point regardless of locale */
486        locale = tr_strdup( setlocale ( LC_NUMERIC, NULL ) );
487        setlocale( LC_NUMERIC, "POSIX" );
488        d  = strtod( val->val.s.s, &endptr );
489        setlocale( LC_NUMERIC, locale );
490        tr_free( locale );
491
492        if(( success = ( val->val.s.s != endptr ) && !*endptr ))
493            *setme = d;
494    }
495
496
497    return success;
498}
499
500tr_bool
501tr_bencDictFindInt( tr_benc * dict, const char * key, int64_t * setme )
502{
503    return tr_bencGetInt( tr_bencDictFind( dict, key ), setme );
504}
505
506tr_bool
507tr_bencDictFindBool( tr_benc * dict, const char * key, tr_bool * setme )
508{
509    return tr_bencGetBool( tr_bencDictFind( dict, key ), setme );
510}
511
512tr_bool
513tr_bencDictFindReal( tr_benc * dict, const char * key, double * setme )
514{
515    return tr_bencGetReal( tr_bencDictFind( dict, key ), setme );
516}
517
518tr_bool
519tr_bencDictFindStr( tr_benc *  dict, const char *  key, const char ** setme )
520{
521    return tr_bencGetStr( tr_bencDictFind( dict, key ), setme );
522}
523
524tr_bool
525tr_bencDictFindList( tr_benc * dict, const char * key, tr_benc ** setme )
526{
527    return tr_bencDictFindType( dict, key, TR_TYPE_LIST, setme );
528}
529
530tr_bool
531tr_bencDictFindDict( tr_benc * dict, const char * key, tr_benc ** setme )
532{
533    return tr_bencDictFindType( dict, key, TR_TYPE_DICT, setme );
534}
535
536tr_bool
537tr_bencDictFindRaw( tr_benc         * dict,
538                    const char      * key,
539                    const uint8_t  ** setme_raw,
540                    size_t          * setme_len )
541{
542    tr_benc * child;
543    const tr_bool found = tr_bencDictFindType( dict, key, TR_TYPE_STR, &child );
544
545    if( found ) {
546        *setme_raw = (uint8_t*) child->val.s.s;
547        *setme_len = child->val.s.i;
548    }
549
550    return found;
551}
552
553/***
554****
555***/
556
557void
558tr_bencInitRaw( tr_benc *    val,
559                const void * src,
560                size_t       byteCount )
561{
562    tr_bencInit( val, TR_TYPE_STR );
563    val->val.s.i = byteCount;
564    val->val.s.s = tr_memdup( src, byteCount );
565}
566
567void
568tr_bencInitStr( tr_benc *    val,
569                const void * str,
570                int          len )
571{
572    tr_bencInit( val, TR_TYPE_STR );
573
574    val->val.s.s = tr_strndup( str, len );
575
576    if( val->val.s.s == NULL )
577        val->val.s.i = 0;
578    else if( len < 0 )
579        val->val.s.i = strlen( val->val.s.s );
580    else
581        val->val.s.i = len;
582}
583
584void
585tr_bencInitBool( tr_benc * b, int value )
586{
587    tr_bencInit( b, TR_TYPE_BOOL );
588    b->val.b = value != 0;
589}
590
591void
592tr_bencInitReal( tr_benc * b, double value )
593{
594    tr_bencInit( b, TR_TYPE_REAL );
595    b->val.d = value;
596}
597
598void
599tr_bencInitInt( tr_benc * b, int64_t value )
600{
601    tr_bencInit( b, TR_TYPE_INT );
602    b->val.i = value;
603}
604
605int
606tr_bencInitList( tr_benc * b, size_t reserveCount )
607{
608    tr_bencInit( b, TR_TYPE_LIST );
609    return tr_bencListReserve( b, reserveCount );
610}
611
612int
613tr_bencListReserve( tr_benc * b, size_t count )
614{
615    assert( tr_bencIsList( b ) );
616    return makeroom( b, count );
617}
618
619int
620tr_bencInitDict( tr_benc * b, size_t reserveCount )
621{
622    tr_bencInit( b, TR_TYPE_DICT );
623    return tr_bencDictReserve( b, reserveCount );
624}
625
626int
627tr_bencDictReserve( tr_benc * b, size_t reserveCount )
628{
629    assert( tr_bencIsDict( b ) );
630    return makeroom( b, reserveCount * 2 );
631}
632
633tr_benc *
634tr_bencListAdd( tr_benc * list )
635{
636    tr_benc * item;
637
638    assert( tr_bencIsList( list ) );
639
640    if( list->val.l.count == list->val.l.alloc )
641        tr_bencListReserve( list, LIST_SIZE );
642
643    assert( list->val.l.count < list->val.l.alloc );
644
645    item = &list->val.l.vals[list->val.l.count];
646    list->val.l.count++;
647    tr_bencInit( item, TR_TYPE_INT );
648
649    return item;
650}
651
652tr_benc *
653tr_bencListAddInt( tr_benc * list,
654                   int64_t   val )
655{
656    tr_benc * node = tr_bencListAdd( list );
657
658    tr_bencInitInt( node, val );
659    return node;
660}
661
662tr_benc *
663tr_bencListAddStr( tr_benc *    list,
664                   const char * val )
665{
666    tr_benc * node = tr_bencListAdd( list );
667
668    tr_bencInitStr( node, val, -1 );
669    return node;
670}
671
672tr_benc*
673tr_bencListAddList( tr_benc * list,
674                    size_t    reserveCount )
675{
676    tr_benc * child = tr_bencListAdd( list );
677
678    tr_bencInitList( child, reserveCount );
679    return child;
680}
681
682tr_benc*
683tr_bencListAddDict( tr_benc * list,
684                    size_t    reserveCount )
685{
686    tr_benc * child = tr_bencListAdd( list );
687
688    tr_bencInitDict( child, reserveCount );
689    return child;
690}
691
692tr_benc *
693tr_bencDictAdd( tr_benc *    dict,
694                const char * key )
695{
696    tr_benc * keyval, * itemval;
697
698    assert( tr_bencIsDict( dict ) );
699    if( dict->val.l.count + 2 > dict->val.l.alloc )
700        makeroom( dict, 2 );
701    assert( dict->val.l.count + 2 <= dict->val.l.alloc );
702
703    keyval = dict->val.l.vals + dict->val.l.count++;
704    tr_bencInitStr( keyval, key, -1 );
705
706    itemval = dict->val.l.vals + dict->val.l.count++;
707    tr_bencInit( itemval, TR_TYPE_INT );
708
709    return itemval;
710}
711
712static tr_benc*
713dictFindOrAdd( tr_benc * dict, const char * key, int type )
714{
715    tr_benc * child;
716
717    /* see if it already exists, and if so, try to reuse it */
718    if(( child = tr_bencDictFind( dict, key ))) {
719        if( !tr_bencIsType( child, type ) ) {
720            tr_bencDictRemove( dict, key );
721            child = NULL;
722        }
723    }
724
725    /* if it doesn't exist, create it */
726    if( child == NULL )
727        child = tr_bencDictAdd( dict, key );
728
729    return child;
730}
731
732tr_benc*
733tr_bencDictAddInt( tr_benc *    dict,
734                   const char * key,
735                   int64_t      val )
736{
737    tr_benc * child = dictFindOrAdd( dict, key, TR_TYPE_INT );
738    tr_bencInitInt( child, val );
739    return child;
740}
741
742tr_benc*
743tr_bencDictAddBool( tr_benc * dict, const char * key, tr_bool val )
744{
745    tr_benc * child = dictFindOrAdd( dict, key, TR_TYPE_BOOL );
746    tr_bencInitBool( child, val );
747    return child;
748}
749
750tr_benc*
751tr_bencDictAddReal( tr_benc * dict, const char * key, double val )
752{
753    tr_benc * child = dictFindOrAdd( dict, key, TR_TYPE_REAL );
754    tr_bencInitReal( child, val );
755    return child;
756}
757
758tr_benc*
759tr_bencDictAddStr( tr_benc * dict, const char * key, const char * val )
760{
761    tr_benc * child;
762
763    /* see if it already exists, and if so, try to reuse it */
764    if(( child = tr_bencDictFind( dict, key ))) {
765        if( tr_bencIsString( child ) )
766            tr_free( child->val.s.s );
767        else {
768            tr_bencDictRemove( dict, key );
769            child = NULL;
770        }
771    }
772
773    /* if it doesn't exist, create it */
774    if( child == NULL )
775        child = tr_bencDictAdd( dict, key );
776
777    /* set it */
778    tr_bencInitStr( child, val, -1 );
779
780    return child;
781}
782
783tr_benc*
784tr_bencDictAddList( tr_benc *    dict,
785                    const char * key,
786                    size_t       reserveCount )
787{
788    tr_benc * child = tr_bencDictAdd( dict, key );
789
790    tr_bencInitList( child, reserveCount );
791    return child;
792}
793
794tr_benc*
795tr_bencDictAddDict( tr_benc *    dict,
796                    const char * key,
797                    size_t       reserveCount )
798{
799    tr_benc * child = tr_bencDictAdd( dict, key );
800
801    tr_bencInitDict( child, reserveCount );
802    return child;
803}
804
805tr_benc*
806tr_bencDictAddRaw( tr_benc *    dict,
807                   const char * key,
808                   const void * src,
809                   size_t       len )
810{
811    tr_benc * child = tr_bencDictAdd( dict, key );
812
813    tr_bencInitRaw( child, src, len );
814    return child;
815}
816
817int
818tr_bencDictRemove( tr_benc *    dict,
819                   const char * key )
820{
821    int i = dictIndexOf( dict, key );
822
823    if( i >= 0 )
824    {
825        const int n = dict->val.l.count;
826        tr_bencFree( &dict->val.l.vals[i] );
827        tr_bencFree( &dict->val.l.vals[i + 1] );
828        if( i + 2 < n )
829        {
830            dict->val.l.vals[i]   = dict->val.l.vals[n - 2];
831            dict->val.l.vals[i + 1] = dict->val.l.vals[n - 1];
832        }
833        dict->val.l.count -= 2;
834    }
835    return i >= 0; /* return true if found */
836}
837
838/***
839****  BENC WALKING
840***/
841
842struct KeyIndex
843{
844    const char *  key;
845    int           index;
846};
847
848static int
849compareKeyIndex( const void * va,
850                 const void * vb )
851{
852    const struct KeyIndex * a = va;
853    const struct KeyIndex * b = vb;
854
855    return strcmp( a->key, b->key );
856}
857
858struct SaveNode
859{
860    const tr_benc *  val;
861    int              valIsVisited;
862    int              childCount;
863    int              childIndex;
864    int *            children;
865};
866
867static struct SaveNode*
868nodeNewDict( const tr_benc * val )
869{
870    int               i, j;
871    int               nKeys;
872    struct SaveNode * node;
873    struct KeyIndex * indices;
874
875    assert( tr_bencIsDict( val ) );
876
877    nKeys = val->val.l.count / 2;
878    node = tr_new0( struct SaveNode, 1 );
879    node->val = val;
880    node->children = tr_new0( int, nKeys * 2 );
881
882    /* ugh, a dictionary's children have to be sorted by key... */
883    indices = tr_new( struct KeyIndex, nKeys );
884    for( i = j = 0; i < ( nKeys * 2 ); i += 2, ++j )
885    {
886        indices[j].key = val->val.l.vals[i].val.s.s;
887        indices[j].index = i;
888    }
889    qsort( indices, j, sizeof( struct KeyIndex ), compareKeyIndex );
890    for( i = 0; i < j; ++i )
891    {
892        const int index = indices[i].index;
893        node->children[node->childCount++] = index;
894        node->children[node->childCount++] = index + 1;
895    }
896
897    assert( node->childCount == nKeys * 2 );
898    tr_free( indices );
899    return node;
900}
901
902static struct SaveNode*
903nodeNewList( const tr_benc * val )
904{
905    int               i, n;
906    struct SaveNode * node;
907
908    assert( tr_bencIsList( val ) );
909
910    n = val->val.l.count;
911    node = tr_new0( struct SaveNode, 1 );
912    node->val = val;
913    node->childCount = n;
914    node->children = tr_new0( int, n );
915    for( i = 0; i < n; ++i ) /* a list's children don't need to be reordered */
916        node->children[i] = i;
917
918    return node;
919}
920
921static struct SaveNode*
922nodeNewLeaf( const tr_benc * val )
923{
924    struct SaveNode * node;
925
926    assert( !isContainer( val ) );
927
928    node = tr_new0( struct SaveNode, 1 );
929    node->val = val;
930    return node;
931}
932
933static struct SaveNode*
934nodeNew( const tr_benc * val )
935{
936    struct SaveNode * node;
937
938    if( tr_bencIsList( val ) )
939        node = nodeNewList( val );
940    else if( tr_bencIsDict( val ) )
941        node = nodeNewDict( val );
942    else
943        node = nodeNewLeaf( val );
944
945    return node;
946}
947
948typedef void ( *BencWalkFunc )( const tr_benc * val, void * user_data );
949
950struct WalkFuncs
951{
952    BencWalkFunc    intFunc;
953    BencWalkFunc    boolFunc;
954    BencWalkFunc    realFunc;
955    BencWalkFunc    stringFunc;
956    BencWalkFunc    dictBeginFunc;
957    BencWalkFunc    listBeginFunc;
958    BencWalkFunc    containerEndFunc;
959};
960
961/**
962 * This function's previous recursive implementation was
963 * easier to read, but was vulnerable to a smash-stacking
964 * attack via maliciously-crafted bencoded data. (#667)
965 */
966static void
967bencWalk( const tr_benc          * top,
968          const struct WalkFuncs * walkFuncs,
969          void                   * user_data )
970{
971    tr_ptrArray stack = TR_PTR_ARRAY_INIT;
972
973    tr_ptrArrayAppend( &stack, nodeNew( top ) );
974
975    while( !tr_ptrArrayEmpty( &stack ) )
976    {
977        struct SaveNode * node = tr_ptrArrayBack( &stack );
978        const tr_benc *   val;
979
980        if( !node->valIsVisited )
981        {
982            val = node->val;
983            node->valIsVisited = TRUE;
984        }
985        else if( node->childIndex < node->childCount )
986        {
987            const int index = node->children[node->childIndex++];
988            val = node->val->val.l.vals +  index;
989        }
990        else /* done with this node */
991        {
992            if( isContainer( node->val ) )
993                walkFuncs->containerEndFunc( node->val, user_data );
994            tr_ptrArrayPop( &stack );
995            tr_free( node->children );
996            tr_free( node );
997            continue;
998        }
999
1000        if( val ) switch( val->type )
1001            {
1002                case TR_TYPE_INT:
1003                    walkFuncs->intFunc( val, user_data );
1004                    break;
1005
1006                case TR_TYPE_BOOL:
1007                    walkFuncs->boolFunc( val, user_data );
1008                    break;
1009
1010                case TR_TYPE_REAL:
1011                    walkFuncs->realFunc( val, user_data );
1012                    break;
1013
1014                case TR_TYPE_STR:
1015                    walkFuncs->stringFunc( val, user_data );
1016                    break;
1017
1018                case TR_TYPE_LIST:
1019                    if( val != node->val )
1020                        tr_ptrArrayAppend( &stack, nodeNew( val ) );
1021                    else
1022                        walkFuncs->listBeginFunc( val, user_data );
1023                    break;
1024
1025                case TR_TYPE_DICT:
1026                    if( val != node->val )
1027                        tr_ptrArrayAppend( &stack, nodeNew( val ) );
1028                    else
1029                        walkFuncs->dictBeginFunc( val, user_data );
1030                    break;
1031
1032                default:
1033                    /* did caller give us an uninitialized val? */
1034                    tr_err( _( "Invalid metadata" ) );
1035                    break;
1036            }
1037    }
1038
1039    tr_ptrArrayDestruct( &stack, NULL );
1040}
1041
1042/****
1043*****
1044****/
1045
1046static void
1047saveIntFunc( const tr_benc * val, void * evbuf )
1048{
1049    evbuffer_add_printf( evbuf, "i%" PRId64 "e", val->val.i );
1050}
1051
1052static void
1053saveBoolFunc( const tr_benc * val, void * evbuf )
1054{
1055    if( val->val.b )
1056        evbuffer_add( evbuf, "i1e", 3 );
1057    else
1058        evbuffer_add( evbuf, "i0e", 3 );
1059}
1060
1061static void
1062saveRealFunc( const tr_benc * val, void * evbuf )
1063{
1064    char buf[128];
1065    char * locale;
1066    size_t len;
1067
1068    /* always use a '.' decimal point s.t. locale-hopping doesn't bite us */
1069    locale = tr_strdup( setlocale ( LC_NUMERIC, NULL ) );
1070    setlocale( LC_NUMERIC, "POSIX" );
1071    tr_snprintf( buf, sizeof( buf ), "%f", val->val.d );
1072    setlocale( LC_NUMERIC, locale );
1073    tr_free( locale );
1074
1075    len = strlen( buf );
1076    evbuffer_add_printf( evbuf, "%lu:", (unsigned long)len );
1077    evbuffer_add( evbuf, buf, len );
1078}
1079
1080static void
1081saveStringFunc( const tr_benc * val, void * evbuf )
1082{
1083    evbuffer_add_printf( evbuf, "%lu:", (unsigned long)val->val.s.i );
1084    evbuffer_add( evbuf, val->val.s.s, val->val.s.i );
1085}
1086
1087static void
1088saveDictBeginFunc( const tr_benc * val UNUSED, void * evbuf )
1089{
1090    evbuffer_add( evbuf, "d", 1 );
1091}
1092
1093static void
1094saveListBeginFunc( const tr_benc * val UNUSED, void * evbuf )
1095{
1096    evbuffer_add( evbuf, "l", 1 );
1097}
1098
1099static void
1100saveContainerEndFunc( const tr_benc * val UNUSED, void * evbuf )
1101{
1102    evbuffer_add( evbuf, "e", 1 );
1103}
1104
1105static const struct WalkFuncs saveFuncs = { saveIntFunc,
1106                                            saveBoolFunc,
1107                                            saveRealFunc,
1108                                            saveStringFunc,
1109                                            saveDictBeginFunc,
1110                                            saveListBeginFunc,
1111                                            saveContainerEndFunc };
1112
1113char*
1114tr_bencSave( const tr_benc * top,
1115             int *           len )
1116{
1117    char * ret;
1118    struct evbuffer * out = tr_getBuffer( );
1119
1120    bencWalk( top, &saveFuncs, out );
1121
1122    if( len )
1123        *len = EVBUFFER_LENGTH( out );
1124    ret = tr_strndup( EVBUFFER_DATA( out ), EVBUFFER_LENGTH( out ) );
1125
1126    tr_releaseBuffer( out );
1127    return ret;
1128}
1129
1130/***
1131****
1132***/
1133
1134static void
1135freeDummyFunc( const tr_benc * val UNUSED,
1136               void * buf          UNUSED  )
1137{}
1138
1139static void
1140freeStringFunc( const tr_benc * val,
1141                void *          freeme )
1142{
1143    tr_ptrArrayAppend( freeme, val->val.s.s );
1144}
1145
1146static void
1147freeContainerBeginFunc( const tr_benc * val,
1148                        void *          freeme )
1149{
1150    tr_ptrArrayAppend( freeme, val->val.l.vals );
1151}
1152
1153static const struct WalkFuncs freeWalkFuncs = { freeDummyFunc,
1154                                                freeDummyFunc,
1155                                                freeDummyFunc,
1156                                                freeStringFunc,
1157                                                freeContainerBeginFunc,
1158                                                freeContainerBeginFunc,
1159                                                freeDummyFunc };
1160
1161void
1162tr_bencFree( tr_benc * val )
1163{
1164    if( isSomething( val ) )
1165    {
1166        tr_ptrArray a = TR_PTR_ARRAY_INIT;
1167        bencWalk( val, &freeWalkFuncs, &a );
1168        tr_ptrArrayDestruct( &a, tr_free );
1169    }
1170}
1171
1172/***
1173****
1174***/
1175
1176struct ParentState
1177{
1178    int    bencType;
1179    int    childIndex;
1180    int    childCount;
1181};
1182
1183struct jsonWalk
1184{
1185    tr_list *          parents;
1186    struct evbuffer *  out;
1187};
1188
1189static void
1190jsonIndent( struct jsonWalk * data )
1191{
1192    char buf[1024];
1193    const int width = tr_list_size( data->parents ) * 4;
1194
1195    buf[0] = '\n';
1196    memset( buf+1, ' ', width );
1197    evbuffer_add( data->out, buf, 1+width );
1198}
1199
1200static void
1201jsonChildFunc( struct jsonWalk * data )
1202{
1203    if( data->parents )
1204    {
1205        struct ParentState * parentState = data->parents->data;
1206
1207        switch( parentState->bencType )
1208        {
1209            case TR_TYPE_DICT:
1210            {
1211                const int i = parentState->childIndex++;
1212                if( !( i % 2 ) )
1213                    evbuffer_add( data->out, ": ", 2 );
1214                else
1215                {
1216                    evbuffer_add( data->out, ", ", 2 );
1217                    jsonIndent( data );
1218                }
1219                break;
1220            }
1221
1222            case TR_TYPE_LIST:
1223            {
1224                ++parentState->childIndex;
1225                evbuffer_add( data->out, ", ", 2 );
1226                jsonIndent( data );
1227                break;
1228            }
1229
1230            default:
1231                break;
1232        }
1233    }
1234}
1235
1236static void
1237jsonPushParent( struct jsonWalk * data,
1238                const tr_benc *   benc )
1239{
1240    struct ParentState * parentState = tr_new( struct ParentState, 1 );
1241
1242    parentState->bencType = benc->type;
1243    parentState->childIndex = 0;
1244    parentState->childCount = benc->val.l.count;
1245    tr_list_prepend( &data->parents, parentState );
1246}
1247
1248static void
1249jsonPopParent( struct jsonWalk * data )
1250{
1251    tr_free( tr_list_pop_front( &data->parents ) );
1252}
1253
1254static void
1255jsonIntFunc( const tr_benc * val,
1256             void *          vdata )
1257{
1258    struct jsonWalk * data = vdata;
1259
1260    evbuffer_add_printf( data->out, "%" PRId64, val->val.i );
1261    jsonChildFunc( data );
1262}
1263
1264static void
1265jsonBoolFunc( const tr_benc * val, void * vdata )
1266{
1267    struct jsonWalk * data = vdata;
1268
1269    if( val->val.b )
1270        evbuffer_add( data->out, "true", 4 );
1271    else
1272        evbuffer_add( data->out, "false", 5 );
1273
1274    jsonChildFunc( data );
1275}
1276
1277static void
1278jsonRealFunc( const tr_benc * val, void * vdata )
1279{
1280    struct jsonWalk * data = vdata;
1281    char * locale;
1282
1283    /* json requires a '.' decimal point regardless of locale */
1284    locale = tr_strdup( setlocale ( LC_NUMERIC, NULL ) );
1285    setlocale( LC_NUMERIC, "POSIX" );
1286    evbuffer_add_printf( data->out, "%f", val->val.d );
1287    setlocale( LC_NUMERIC, locale );
1288    tr_free( locale );
1289
1290    jsonChildFunc( data );
1291}
1292
1293static void
1294jsonStringFunc( const tr_benc * val, void * vdata )
1295{
1296    struct jsonWalk * data = vdata;
1297    const unsigned char * it = (const unsigned char *) val->val.s.s;
1298    const unsigned char * end = it + val->val.s.i;
1299
1300    evbuffer_expand( data->out, val->val.s.i + 2 );
1301    evbuffer_add( data->out, "\"", 1 );
1302
1303    for( ; it!=end; ++it )
1304    {
1305        switch( *it )
1306        {
1307            case '/': evbuffer_add( data->out, "\\/", 2 ); break;
1308            case '\b': evbuffer_add( data->out, "\\b", 2 ); break;
1309            case '\f': evbuffer_add( data->out, "\\f", 2 ); break;
1310            case '\n': evbuffer_add( data->out, "\\n", 2 ); break;
1311            case '\r': evbuffer_add( data->out, "\\r", 2 ); break;
1312            case '\t': evbuffer_add( data->out, "\\t", 2 ); break;
1313            case '"': evbuffer_add( data->out, "\\\"", 2 ); break;
1314            case '\\': evbuffer_add( data->out, "\\\\", 2 ); break;
1315
1316            default:
1317                if( isascii( *it ) )
1318                    evbuffer_add( data->out, it, 1 );
1319                else {
1320                    const UTF8 * tmp = it;
1321                    UTF32        buf = 0;
1322                    UTF32 *      u32 = &buf;
1323                    ConversionResult result = ConvertUTF8toUTF32( &tmp, end, &u32, &buf + 1, 0 );
1324                    if( ( result != conversionOK ) && ( tmp == it ) )
1325                        ++it; /* it's beyond help; skip it */
1326                    else {
1327                        evbuffer_add_printf( data->out, "\\u%04x", (unsigned int)buf );
1328                        it = tmp - 1;
1329                    }
1330                }
1331        }
1332    }
1333    evbuffer_add( data->out, "\"", 1 );
1334    jsonChildFunc( data );
1335}
1336
1337static void
1338jsonDictBeginFunc( const tr_benc * val,
1339                   void *          vdata )
1340{
1341    struct jsonWalk * data = vdata;
1342
1343    jsonPushParent( data, val );
1344    evbuffer_add( data->out, "{", 1 );
1345    if( val->val.l.count )
1346        jsonIndent( data );
1347}
1348
1349static void
1350jsonListBeginFunc( const tr_benc * val,
1351                   void *          vdata )
1352{
1353    const size_t      nChildren = tr_bencListSize( val );
1354    struct jsonWalk * data = vdata;
1355
1356    jsonPushParent( data, val );
1357    evbuffer_add( data->out, "[", 1 );
1358    if( nChildren )
1359        jsonIndent( data );
1360}
1361
1362static void
1363jsonContainerEndFunc( const tr_benc * val,
1364                      void *          vdata )
1365{
1366    size_t            i;
1367    struct jsonWalk * data = vdata;
1368    char *            str;
1369    int               emptyContainer = FALSE;
1370
1371    /* trim out the trailing comma, if any */
1372    str = (char*) EVBUFFER_DATA( data->out );
1373    for( i = EVBUFFER_LENGTH( data->out ) - 1; i > 0; --i )
1374    {
1375        if( isspace( str[i] ) ) continue;
1376        if( str[i] == ',' )
1377            EVBUFFER_LENGTH( data->out ) = i;
1378        if( str[i] == '{' || str[i] == '[' )
1379            emptyContainer = TRUE;
1380        break;
1381    }
1382
1383    jsonPopParent( data );
1384    if( !emptyContainer )
1385        jsonIndent( data );
1386    if( tr_bencIsDict( val ) )
1387        evbuffer_add( data->out, "}", 1 );
1388    else /* list */
1389        evbuffer_add( data->out, "]", 1 );
1390    jsonChildFunc( data );
1391}
1392
1393static const struct WalkFuncs jsonWalkFuncs = { jsonIntFunc,
1394                                                jsonBoolFunc,
1395                                                jsonRealFunc,
1396                                                jsonStringFunc,
1397                                                jsonDictBeginFunc,
1398                                                jsonListBeginFunc,
1399                                                jsonContainerEndFunc };
1400                                           
1401char*
1402tr_bencSaveAsJSON( const tr_benc * top, struct evbuffer * out )
1403{
1404    struct jsonWalk data;
1405
1406    evbuffer_drain( out, EVBUFFER_LENGTH( out ) );
1407
1408    data.out = out;
1409    data.parents = NULL;
1410
1411    bencWalk( top, &jsonWalkFuncs, &data );
1412
1413    if( EVBUFFER_LENGTH( out ) )
1414        evbuffer_add_printf( out, "\n" );
1415
1416    return (char*) EVBUFFER_DATA( out );
1417}
1418
1419char*
1420tr_bencToJSON( const tr_benc * top )
1421{
1422    char * ret;
1423    struct evbuffer * buf = evbuffer_new( );
1424    tr_bencSaveAsJSON( top, buf );
1425    ret = tr_strndup( EVBUFFER_DATA( buf ), EVBUFFER_LENGTH( buf ) );
1426    evbuffer_free( buf );
1427    return ret;
1428}
1429
1430/***
1431****
1432***/
1433
1434static size_t
1435tr_bencDictSize( const tr_benc * dict )
1436{
1437    size_t count = 0;
1438
1439    if( tr_bencIsDict( dict ) )
1440        count = dict->val.l.count / 2;
1441
1442    return count;
1443}
1444
1445static tr_bool
1446tr_bencDictChild( const tr_benc * dict, size_t n, const char ** key, const tr_benc ** val )
1447{
1448    tr_bool success = 0;
1449
1450    assert( tr_bencIsDict( dict ) );
1451
1452    if( tr_bencIsDict( dict ) && (n*2)+1 <= dict->val.l.count )
1453    {
1454        tr_benc * k = dict->val.l.vals + (n*2);
1455        tr_benc * v = dict->val.l.vals + (n*2) + 1;
1456        if(( success = tr_bencGetStr( k, key ) && isSomething( v )))
1457            *val = v;
1458    }
1459
1460    return success;
1461}
1462
1463void 
1464tr_bencMergeDicts( tr_benc * target, const tr_benc * source )
1465{
1466    size_t i;
1467    const size_t sourceCount = tr_bencDictSize( source );
1468
1469    assert( tr_bencIsDict( target ) );
1470    assert( tr_bencIsDict( source ) );
1471
1472    for( i=0; i<sourceCount; ++i )
1473    {
1474        const char * key;
1475        const tr_benc * val;
1476        tr_benc * t;
1477
1478        if( tr_bencDictChild( source, i, &key, &val ) )
1479        {
1480            if( tr_bencIsBool( val ) )
1481            {
1482                tr_bool boolVal;
1483                tr_bencGetBool( val, &boolVal );
1484                tr_bencDictAddBool( target, key, boolVal );
1485            }
1486            else if( tr_bencIsReal( val ) )
1487            {
1488                double realVal;
1489                tr_bencGetReal( val, &realVal );
1490                tr_bencDictAddReal( target, key, realVal );
1491            }
1492            else if( tr_bencIsInt( val ) )
1493            {
1494                int64_t intVal;
1495                tr_bencGetInt( val, &intVal );
1496                tr_bencDictAddInt( target, key, intVal );
1497            }
1498            else if( tr_bencIsString( val ) )
1499            {
1500                const char * strVal;
1501                tr_bencGetStr( val, &strVal );
1502                tr_bencDictAddStr( target, key, strVal );
1503            }
1504            else if( tr_bencIsDict( val ) && tr_bencDictFindDict( target, key, &t ) )
1505            {
1506                tr_bencMergeDicts( t, val );
1507            }
1508            else
1509            {
1510                tr_dbg( "tr_bencMergeDicts skipping \"%s\"", key );
1511            }
1512        }
1513    }
1514}
1515
1516/***
1517****
1518***/ 
1519
1520static int
1521saveFile( const char * filename,
1522          const char * content,
1523          size_t       len )
1524{
1525    int    err = 0;
1526    FILE * out = NULL;
1527
1528    out = fopen( filename, "wb+" );
1529
1530    if( !out )
1531    {
1532        err = errno;
1533        tr_err( _( "Couldn't open \"%1$s\": %2$s" ),
1534                filename, tr_strerror( errno ) );
1535    }
1536    else if( fwrite( content, sizeof( char ), len, out ) != (size_t)len )
1537    {
1538        err = errno;
1539        tr_err( _( "Couldn't save file \"%1$s\": %2$s" ),
1540               filename, tr_strerror( errno ) );
1541    }
1542
1543    if( !err )
1544        tr_dbg( "tr_bencSaveFile saved \"%s\"", filename );
1545    if( out )
1546        fclose( out );
1547    return err;
1548}
1549
1550int
1551tr_bencSaveFile( const char *    filename,
1552                 const tr_benc * b )
1553{
1554    int       len;
1555    char *    content = tr_bencSave( b, &len );
1556    const int err = saveFile( filename, content, len );
1557
1558    tr_free( content );
1559    return err;
1560}
1561
1562int
1563tr_bencSaveJSONFile( const char *    filename,
1564                     const tr_benc * b )
1565{
1566    struct evbuffer * buf = tr_getBuffer( );
1567    const char * json = tr_bencSaveAsJSON( b, buf );
1568    const int err = saveFile( filename, json, EVBUFFER_LENGTH( buf ) );
1569    tr_releaseBuffer( buf );
1570    return err;
1571}
1572
1573/***
1574****
1575***/
1576
1577int
1578tr_bencLoadFile( const char * filename, tr_benc * b )
1579{
1580    int       err;
1581    size_t    contentLen;
1582    uint8_t * content;
1583
1584    content = tr_loadFile( filename, &contentLen );
1585    if( !content && errno )
1586        err = errno;
1587    else if( !content )
1588        err = ENODATA;
1589    else
1590        err = tr_bencLoad( content, contentLen, b, NULL );
1591
1592    tr_free( content );
1593    return err;
1594}
1595
1596int
1597tr_bencLoadJSONFile( const char * filename, tr_benc * b )
1598{
1599    int        err;
1600    size_t     contentLen;
1601    uint8_t  * content;
1602
1603    content = tr_loadFile( filename, &contentLen );
1604    if( !content && errno )
1605        err = errno;
1606    else if( !content )
1607        err = ENODATA;
1608    else
1609        err = tr_jsonParse( content, contentLen, b, NULL );
1610
1611    tr_free( content );
1612    return err;
1613}
Note: See TracBrowser for help on using the repository browser.