source: trunk/libtransmission/bencode.c @ 7524

Last change on this file since 7524 was 7524, checked in by charles, 12 years ago

(trunk libT) avoid some unnecessary memory fragmentation... for composited objects that have a tr_ptrArray, contain the tr_ptrArray directly rather than a pointer to one allocated elsewhere on the heap.

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