source: trunk/libtransmission/bencode.c @ 7567

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

(trunk libT) Fix sparse warnings: symbol 'XXX' shadows an earlier one

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