source: trunk/libtransmission/bencode.c @ 8181

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

(trunk) tr_metaInfoBuilderCreate() doesn't need a tr_session* handle anymore

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