source: trunk/libtransmission/bencode.c @ 8114

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

(trunk) make tr_bencGetReal() work better in i18n settings

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