source: trunk/libtransmission/bencode.c @ 8154

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

(trunk) Use proper notation for json floating-point and bool types. For backwards compatability, still allow old-style printf strings as doubles, and 0s and 1s as bools.

  • Property svn:keywords set to Date Rev Author Id
File size: 39.0 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 8154 2009-04-05 17:52:21Z 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    tr_bool success = FALSE;
418
419    if( !success && (( success = tr_bencIsInt( val ))))
420        if( setme )
421            *setme = val->val.i;
422
423    if( !success && (( success = tr_bencIsBool( val )))) {
424        fprintf( stderr, "warning: reading bool as an int\n" );
425        if( setme )
426            *setme = val->val.b ? 1 : 0;
427    }
428
429    return success;
430}
431
432tr_bool
433tr_bencGetStr( const tr_benc * val,
434               const char **   setme )
435{
436    const int success = tr_bencIsString( val );
437
438    if( success )
439        *setme = val->val.s.s;
440
441    return success;
442}
443
444tr_bool
445tr_bencGetBool( const tr_benc * val, tr_bool * setme )
446{
447    tr_bool success = FALSE;
448
449    if(( success = tr_bencIsBool( val )))
450        *setme = val->val.b;
451
452    if( !success && tr_bencIsInt( val ) )
453        if(( success = ( val->val.i==0 || val->val.i==1 ) ))
454            *setme = val->val.i!=0;
455
456    if( !success && tr_bencIsString( val ) )
457        if(( success = ( !strcmp(val->val.s.s,"true") || !strcmp(val->val.s.s,"false"))))
458            *setme = !strcmp(val->val.s.s,"true");
459
460    return success;
461}
462
463tr_bool
464tr_bencGetReal( const tr_benc * val, double * setme )
465{
466    tr_bool success = FALSE;
467
468    if( !success && (( success = tr_bencIsReal( val ))))
469        *setme = val->val.d;
470
471    if( !success && (( success = tr_bencIsInt( val ))))
472        *setme = val->val.i;
473
474    if( !success && tr_bencIsString(val) )
475    {
476        char * endptr;
477        char * locale; 
478        double d;
479
480        /* the json spec requires a '.' decimal point regardless of locale */
481        locale = tr_strdup( setlocale ( LC_NUMERIC, NULL ) );
482        setlocale( LC_NUMERIC, "POSIX" );
483        d  = strtod( val->val.s.s, &endptr );
484        setlocale( LC_NUMERIC, locale );
485        tr_free( locale );
486
487        if(( success = ( val->val.s.s != endptr ) && !*endptr ))
488            *setme = d;
489    }
490
491
492    return success;
493}
494
495tr_bool
496tr_bencDictFindInt( tr_benc * dict, const char * key, int64_t * setme )
497{
498    return tr_bencGetInt( tr_bencDictFind( dict, key ), setme );
499}
500
501tr_bool
502tr_bencDictFindBool( tr_benc * dict, const char * key, tr_bool * setme )
503{
504    return tr_bencGetBool( tr_bencDictFind( dict, key ), setme );
505}
506
507tr_bool
508tr_bencDictFindReal( tr_benc * dict, const char * key, double * setme )
509{
510    return tr_bencGetReal( tr_bencDictFind( dict, key ), setme );
511}
512
513tr_bool
514tr_bencDictFindList( tr_benc * dict, const char * key, tr_benc ** setme )
515{
516    tr_bool found = FALSE;
517    tr_benc * child = tr_bencDictFindType( dict, key, TYPE_LIST );
518
519    if( child )
520    {
521        if( setme != NULL )
522            *setme = child;
523        found = TRUE;
524    }
525
526    return found;
527}
528
529tr_bool
530tr_bencDictFindDict( tr_benc * dict, const char * key, tr_benc ** setme )
531{
532    tr_bool found = FALSE;
533    tr_benc * child = tr_bencDictFindType( dict, key, TYPE_DICT );
534
535    if( child )
536    {
537        if( setme != NULL )
538            *setme = child;
539        found = TRUE;
540    }
541
542    return found;
543}
544
545tr_bool
546tr_bencDictFindStr( tr_benc *  dict, const char *  key, const char ** setme )
547{
548    tr_bool found = FALSE;
549    tr_benc * child = tr_bencDictFindType( dict, key, TYPE_STR );
550
551    if( child )
552    {
553        if( setme )
554            *setme = child->val.s.s;
555        found = TRUE;
556    }
557
558    return found;
559}
560
561tr_bool
562tr_bencDictFindRaw( tr_benc         * dict,
563                    const char      * key,
564                    const uint8_t  ** setme_raw,
565                    size_t          * setme_len )
566{
567    tr_bool found = FALSE;
568    tr_benc * child = tr_bencDictFindType( dict, key, TYPE_STR );
569
570    if( child )
571    {
572        *setme_raw = (uint8_t*) child->val.s.s;
573        *setme_len = child->val.s.i;
574        found = TRUE;
575    }
576
577    return found;
578}
579
580/***
581****
582***/
583
584void
585tr_bencInitRaw( tr_benc *    val,
586                const void * src,
587                size_t       byteCount )
588{
589    tr_bencInit( val, TYPE_STR );
590    val->val.s.i = byteCount;
591    val->val.s.s = tr_memdup( src, byteCount );
592}
593
594void
595tr_bencInitStr( tr_benc *    val,
596                const void * str,
597                int          len )
598{
599    tr_bencInit( val, TYPE_STR );
600
601    val->val.s.s = tr_strndup( str, len );
602
603    if( val->val.s.s == NULL )
604        val->val.s.i = 0;
605    else if( len < 0 )
606        val->val.s.i = strlen( val->val.s.s );
607    else
608        val->val.s.i = len;
609}
610
611void
612tr_bencInitBool( tr_benc * b, int value )
613{
614    tr_bencInit( b, TYPE_BOOL );
615    b->val.b = value != 0;
616}
617
618void
619tr_bencInitReal( tr_benc * b, double value )
620{
621    tr_bencInit( b, TYPE_REAL );
622    b->val.d = value;
623}
624
625void
626tr_bencInitInt( tr_benc * b, int64_t value )
627{
628    tr_bencInit( b, TYPE_INT );
629    b->val.i = value;
630}
631
632int
633tr_bencInitList( tr_benc * b, size_t reserveCount )
634{
635    tr_bencInit( b, TYPE_LIST );
636    return tr_bencListReserve( b, reserveCount );
637}
638
639int
640tr_bencListReserve( tr_benc * b, size_t count )
641{
642    assert( tr_bencIsList( b ) );
643    return makeroom( b, count );
644}
645
646int
647tr_bencInitDict( tr_benc * b, size_t reserveCount )
648{
649    tr_bencInit( b, TYPE_DICT );
650    return tr_bencDictReserve( b, reserveCount );
651}
652
653int
654tr_bencDictReserve( tr_benc * b, size_t reserveCount )
655{
656    assert( tr_bencIsDict( b ) );
657    return makeroom( b, reserveCount * 2 );
658}
659
660tr_benc *
661tr_bencListAdd( tr_benc * list )
662{
663    tr_benc * item;
664
665    assert( tr_bencIsList( list ) );
666
667    if( list->val.l.count == list->val.l.alloc )
668        tr_bencListReserve( list, LIST_SIZE );
669
670    assert( list->val.l.count < list->val.l.alloc );
671
672    item = &list->val.l.vals[list->val.l.count];
673    list->val.l.count++;
674    tr_bencInit( item, TYPE_INT );
675
676    return item;
677}
678
679tr_benc *
680tr_bencListAddInt( tr_benc * list,
681                   int64_t   val )
682{
683    tr_benc * node = tr_bencListAdd( list );
684
685    tr_bencInitInt( node, val );
686    return node;
687}
688
689tr_benc *
690tr_bencListAddStr( tr_benc *    list,
691                   const char * val )
692{
693    tr_benc * node = tr_bencListAdd( list );
694
695    tr_bencInitStr( node, val, -1 );
696    return node;
697}
698
699tr_benc*
700tr_bencListAddList( tr_benc * list,
701                    size_t    reserveCount )
702{
703    tr_benc * child = tr_bencListAdd( list );
704
705    tr_bencInitList( child, reserveCount );
706    return child;
707}
708
709tr_benc*
710tr_bencListAddDict( tr_benc * list,
711                    size_t    reserveCount )
712{
713    tr_benc * child = tr_bencListAdd( list );
714
715    tr_bencInitDict( child, reserveCount );
716    return child;
717}
718
719tr_benc *
720tr_bencDictAdd( tr_benc *    dict,
721                const char * key )
722{
723    tr_benc * keyval, * itemval;
724
725    assert( tr_bencIsDict( dict ) );
726    if( dict->val.l.count + 2 > dict->val.l.alloc )
727        makeroom( dict, 2 );
728    assert( dict->val.l.count + 2 <= dict->val.l.alloc );
729
730    keyval = dict->val.l.vals + dict->val.l.count++;
731    tr_bencInitStr( keyval, key, -1 );
732
733    itemval = dict->val.l.vals + dict->val.l.count++;
734    tr_bencInit( itemval, TYPE_INT );
735
736    return itemval;
737}
738
739static tr_benc*
740dictFindOrAdd( tr_benc * dict, const char * key, int type )
741{
742    tr_benc * child;
743
744    /* see if it already exists, and if so, try to reuse it */
745    if(( child = tr_bencDictFind( dict, key ))) {
746        if( !tr_bencIsType( child, type ) ) {
747            tr_bencDictRemove( dict, key );
748            child = NULL;
749        }
750    }
751
752    /* if it doesn't exist, create it */
753    if( child == NULL )
754        child = tr_bencDictAdd( dict, key );
755
756    return child;
757}
758
759tr_benc*
760tr_bencDictAddInt( tr_benc *    dict,
761                   const char * key,
762                   int64_t      val )
763{
764    tr_benc * child = dictFindOrAdd( dict, key, TYPE_INT );
765    tr_bencInitInt( child, val );
766    return child;
767}
768
769tr_benc*
770tr_bencDictAddBool( tr_benc * dict, const char * key, tr_bool val )
771{
772    tr_benc * child = dictFindOrAdd( dict, key, TYPE_BOOL );
773    tr_bencInitBool( child, val );
774    return child;
775}
776
777tr_benc*
778tr_bencDictAddReal( tr_benc * dict, const char * key, double val )
779{
780    tr_benc * child = dictFindOrAdd( dict, key, TYPE_REAL );
781    tr_bencInitReal( child, val );
782    return child;
783}
784
785tr_benc*
786tr_bencDictAddStr( tr_benc * dict, const char * key, const char * val )
787{
788    tr_benc * child;
789
790    /* see if it already exists, and if so, try to reuse it */
791    if(( child = tr_bencDictFind( dict, key ))) {
792        if( tr_bencIsString( child ) )
793            tr_free( child->val.s.s );
794        else {
795            tr_bencDictRemove( dict, key );
796            child = NULL;
797        }
798    }
799
800    /* if it doesn't exist, create it */
801    if( child == NULL )
802        child = tr_bencDictAdd( dict, key );
803
804    /* set it */
805    tr_bencInitStr( child, val, -1 );
806
807    return child;
808}
809
810#if 0
811tr_benc*
812tr_bencDictAddReal( tr_benc * dict, const char * key, double d )
813{
814    ccc
815    char buf[128];
816    char * locale;
817
818    /* the json spec requires a '.' decimal point regardless of locale */
819    locale = tr_strdup( setlocale ( LC_NUMERIC, NULL ) );
820    setlocale( LC_NUMERIC, "POSIX" );
821    tr_snprintf( buf, sizeof( buf ), "%f", d );
822    setlocale( LC_NUMERIC, locale );
823    tr_free( locale );
824
825    return tr_bencDictAddStr( dict, key, buf );
826}
827#endif
828
829tr_benc*
830tr_bencDictAddList( tr_benc *    dict,
831                    const char * key,
832                    size_t       reserveCount )
833{
834    tr_benc * child = tr_bencDictAdd( dict, key );
835
836    tr_bencInitList( child, reserveCount );
837    return child;
838}
839
840tr_benc*
841tr_bencDictAddDict( tr_benc *    dict,
842                    const char * key,
843                    size_t       reserveCount )
844{
845    tr_benc * child = tr_bencDictAdd( dict, key );
846
847    tr_bencInitDict( child, reserveCount );
848    return child;
849}
850
851tr_benc*
852tr_bencDictAddRaw( tr_benc *    dict,
853                   const char * key,
854                   const void * src,
855                   size_t       len )
856{
857    tr_benc * child = tr_bencDictAdd( dict, key );
858
859    tr_bencInitRaw( child, src, len );
860    return child;
861}
862
863int
864tr_bencDictRemove( tr_benc *    dict,
865                   const char * key )
866{
867    int i = dictIndexOf( dict, key );
868
869    if( i >= 0 )
870    {
871        const int n = dict->val.l.count;
872        tr_bencFree( &dict->val.l.vals[i] );
873        tr_bencFree( &dict->val.l.vals[i + 1] );
874        if( i + 2 < n )
875        {
876            dict->val.l.vals[i]   = dict->val.l.vals[n - 2];
877            dict->val.l.vals[i + 1] = dict->val.l.vals[n - 1];
878        }
879        dict->val.l.count -= 2;
880    }
881    return i >= 0; /* return true if found */
882}
883
884/***
885****  BENC WALKING
886***/
887
888struct KeyIndex
889{
890    const char *  key;
891    int           index;
892};
893
894static int
895compareKeyIndex( const void * va,
896                 const void * vb )
897{
898    const struct KeyIndex * a = va;
899    const struct KeyIndex * b = vb;
900
901    return strcmp( a->key, b->key );
902}
903
904struct SaveNode
905{
906    const tr_benc *  val;
907    int              valIsVisited;
908    int              childCount;
909    int              childIndex;
910    int *            children;
911};
912
913static struct SaveNode*
914nodeNewDict( const tr_benc * val )
915{
916    int               i, j;
917    int               nKeys;
918    struct SaveNode * node;
919    struct KeyIndex * indices;
920
921    assert( tr_bencIsDict( val ) );
922
923    nKeys = val->val.l.count / 2;
924    node = tr_new0( struct SaveNode, 1 );
925    node->val = val;
926    node->children = tr_new0( int, nKeys * 2 );
927
928    /* ugh, a dictionary's children have to be sorted by key... */
929    indices = tr_new( struct KeyIndex, nKeys );
930    for( i = j = 0; i < ( nKeys * 2 ); i += 2, ++j )
931    {
932        indices[j].key = val->val.l.vals[i].val.s.s;
933        indices[j].index = i;
934    }
935    qsort( indices, j, sizeof( struct KeyIndex ), compareKeyIndex );
936    for( i = 0; i < j; ++i )
937    {
938        const int index = indices[i].index;
939        node->children[node->childCount++] = index;
940        node->children[node->childCount++] = index + 1;
941    }
942
943    assert( node->childCount == nKeys * 2 );
944    tr_free( indices );
945    return node;
946}
947
948static struct SaveNode*
949nodeNewList( const tr_benc * val )
950{
951    int               i, n;
952    struct SaveNode * node;
953
954    assert( tr_bencIsList( val ) );
955
956    n = val->val.l.count;
957    node = tr_new0( struct SaveNode, 1 );
958    node->val = val;
959    node->childCount = n;
960    node->children = tr_new0( int, n );
961    for( i = 0; i < n; ++i ) /* a list's children don't need to be reordered */
962        node->children[i] = i;
963
964    return node;
965}
966
967static struct SaveNode*
968nodeNewLeaf( const tr_benc * val )
969{
970    struct SaveNode * node;
971
972    assert( !isContainer( val ) );
973
974    node = tr_new0( struct SaveNode, 1 );
975    node->val = val;
976    return node;
977}
978
979static struct SaveNode*
980nodeNew( const tr_benc * val )
981{
982    struct SaveNode * node;
983
984    if( tr_bencIsList( val ) )
985        node = nodeNewList( val );
986    else if( tr_bencIsDict( val ) )
987        node = nodeNewDict( val );
988    else
989        node = nodeNewLeaf( val );
990
991    return node;
992}
993
994typedef void ( *BencWalkFunc )( const tr_benc * val, void * user_data );
995
996struct WalkFuncs
997{
998    BencWalkFunc    intFunc;
999    BencWalkFunc    boolFunc;
1000    BencWalkFunc    realFunc;
1001    BencWalkFunc    stringFunc;
1002    BencWalkFunc    dictBeginFunc;
1003    BencWalkFunc    listBeginFunc;
1004    BencWalkFunc    containerEndFunc;
1005};
1006
1007/**
1008 * This function's previous recursive implementation was
1009 * easier to read, but was vulnerable to a smash-stacking
1010 * attack via maliciously-crafted bencoded data. (#667)
1011 */
1012static void
1013bencWalk( const tr_benc *    top,
1014          struct WalkFuncs * walkFuncs,
1015          void *             user_data )
1016{
1017    tr_ptrArray stack = TR_PTR_ARRAY_INIT;
1018
1019    tr_ptrArrayAppend( &stack, nodeNew( top ) );
1020
1021    while( !tr_ptrArrayEmpty( &stack ) )
1022    {
1023        struct SaveNode * node = tr_ptrArrayBack( &stack );
1024        const tr_benc *   val;
1025
1026        if( !node->valIsVisited )
1027        {
1028            val = node->val;
1029            node->valIsVisited = TRUE;
1030        }
1031        else if( node->childIndex < node->childCount )
1032        {
1033            const int index = node->children[node->childIndex++];
1034            val = node->val->val.l.vals +  index;
1035        }
1036        else /* done with this node */
1037        {
1038            if( isContainer( node->val ) )
1039                walkFuncs->containerEndFunc( node->val, user_data );
1040            tr_ptrArrayPop( &stack );
1041            tr_free( node->children );
1042            tr_free( node );
1043            continue;
1044        }
1045
1046        if( val ) switch( val->type )
1047            {
1048                case TYPE_INT:
1049                    walkFuncs->intFunc( val, user_data );
1050                    break;
1051
1052                case TYPE_BOOL:
1053                    walkFuncs->boolFunc( val, user_data );
1054                    break;
1055
1056                case TYPE_REAL:
1057                    walkFuncs->realFunc( val, user_data );
1058                    break;
1059
1060                case TYPE_STR:
1061                    walkFuncs->stringFunc( val, user_data );
1062                    break;
1063
1064                case TYPE_LIST:
1065                    if( val != node->val )
1066                        tr_ptrArrayAppend( &stack, nodeNew( val ) );
1067                    else
1068                        walkFuncs->listBeginFunc( val, user_data );
1069                    break;
1070
1071                case TYPE_DICT:
1072                    if( val != node->val )
1073                        tr_ptrArrayAppend( &stack, nodeNew( val ) );
1074                    else
1075                        walkFuncs->dictBeginFunc( val, user_data );
1076                    break;
1077
1078                default:
1079                    /* did caller give us an uninitialized val? */
1080                    tr_err( _( "Invalid metadata" ) );
1081                    break;
1082            }
1083    }
1084
1085    tr_ptrArrayDestruct( &stack, NULL );
1086}
1087
1088/****
1089*****
1090****/
1091
1092static void
1093saveIntFunc( const tr_benc * val,
1094             void *          evbuf )
1095{
1096    evbuffer_add_printf( evbuf, "i%" PRId64 "e", val->val.i );
1097}
1098
1099static void
1100saveBoolFunc( const tr_benc * val, void * evbuf )
1101{
1102    evbuffer_add_printf( evbuf, "i%de", val->val.b?1:0 );
1103}
1104
1105static void
1106saveRealFunc( const tr_benc * val, void * evbuf )
1107{
1108    char buf[128];
1109    char * locale;
1110    size_t len;
1111
1112    /* always use a '.' decimal point s.t. locale-hopping doesn't bite us */
1113    locale = tr_strdup( setlocale ( LC_NUMERIC, NULL ) );
1114    setlocale( LC_NUMERIC, "POSIX" );
1115    tr_snprintf( buf, sizeof( buf ), "%f", val->val.d );
1116    setlocale( LC_NUMERIC, locale );
1117    tr_free( locale );
1118
1119    len = strlen( buf );
1120    evbuffer_add_printf( evbuf, "%lu:", (unsigned long)buf );
1121    evbuffer_add( evbuf, buf, len );
1122}
1123
1124static void
1125saveStringFunc( const tr_benc * val,
1126                void *          vevbuf )
1127{
1128    struct evbuffer * evbuf = vevbuf;
1129
1130    evbuffer_add_printf( evbuf, "%lu:", (unsigned long)val->val.s.i );
1131    evbuffer_add( evbuf, val->val.s.s, val->val.s.i );
1132}
1133
1134static void
1135saveDictBeginFunc( const tr_benc * val UNUSED,
1136                   void *              evbuf )
1137{
1138    evbuffer_add_printf( evbuf, "d" );
1139}
1140
1141static void
1142saveListBeginFunc( const tr_benc * val UNUSED,
1143                   void *              evbuf )
1144{
1145    evbuffer_add_printf( evbuf, "l" );
1146}
1147
1148static void
1149saveContainerEndFunc( const tr_benc * val UNUSED,
1150                      void *              evbuf )
1151{
1152    evbuffer_add_printf( evbuf, "e" );
1153}
1154
1155char*
1156tr_bencSave( const tr_benc * top,
1157             int *           len )
1158{
1159    char *            ret;
1160    struct WalkFuncs  walkFuncs;
1161    struct evbuffer * out = tr_getBuffer( );
1162
1163    walkFuncs.intFunc = saveIntFunc;
1164    walkFuncs.boolFunc = saveBoolFunc;
1165    walkFuncs.realFunc = saveRealFunc;
1166    walkFuncs.stringFunc = saveStringFunc;
1167    walkFuncs.dictBeginFunc = saveDictBeginFunc;
1168    walkFuncs.listBeginFunc = saveListBeginFunc;
1169    walkFuncs.containerEndFunc = saveContainerEndFunc;
1170    bencWalk( top, &walkFuncs, out );
1171
1172    if( len )
1173        *len = EVBUFFER_LENGTH( out );
1174    ret = tr_strndup( EVBUFFER_DATA( out ), EVBUFFER_LENGTH( out ) );
1175
1176    tr_releaseBuffer( out );
1177    return ret;
1178}
1179
1180/***
1181****
1182***/
1183
1184static void
1185freeDummyFunc( const tr_benc * val UNUSED,
1186               void * buf          UNUSED  )
1187{}
1188
1189static void
1190freeStringFunc( const tr_benc * val,
1191                void *          freeme )
1192{
1193    tr_ptrArrayAppend( freeme, val->val.s.s );
1194}
1195
1196static void
1197freeContainerBeginFunc( const tr_benc * val,
1198                        void *          freeme )
1199{
1200    tr_ptrArrayAppend( freeme, val->val.l.vals );
1201}
1202
1203void
1204tr_bencFree( tr_benc * val )
1205{
1206    if( val && val->type )
1207    {
1208        tr_ptrArray a = TR_PTR_ARRAY_INIT;
1209        struct WalkFuncs walkFuncs;
1210
1211        walkFuncs.intFunc = freeDummyFunc;
1212        walkFuncs.boolFunc = freeDummyFunc;
1213        walkFuncs.realFunc = freeDummyFunc;
1214        walkFuncs.stringFunc = freeStringFunc;
1215        walkFuncs.dictBeginFunc = freeContainerBeginFunc;
1216        walkFuncs.listBeginFunc = freeContainerBeginFunc;
1217        walkFuncs.containerEndFunc = freeDummyFunc;
1218        bencWalk( val, &walkFuncs, &a );
1219
1220        tr_ptrArrayDestruct( &a, tr_free );
1221    }
1222}
1223
1224/***
1225****
1226***/
1227
1228struct ParentState
1229{
1230    int    bencType;
1231    int    childIndex;
1232    int    childCount;
1233};
1234
1235struct jsonWalk
1236{
1237    tr_list *          parents;
1238    struct evbuffer *  out;
1239};
1240
1241static void
1242jsonIndent( struct jsonWalk * data )
1243{
1244    const int width = tr_list_size( data->parents ) * 4;
1245
1246    evbuffer_add_printf( data->out, "\n%*.*s", width, width, " " );
1247}
1248
1249static void
1250jsonChildFunc( struct jsonWalk * data )
1251{
1252    if( data->parents )
1253    {
1254        struct ParentState * parentState = data->parents->data;
1255
1256        switch( parentState->bencType )
1257        {
1258            case TYPE_DICT:
1259            {
1260                const int i = parentState->childIndex++;
1261                if( !( i % 2 ) )
1262                    evbuffer_add_printf( data->out, ": " );
1263                else
1264                {
1265                    evbuffer_add_printf( data->out, ", " );
1266                    jsonIndent( data );
1267                }
1268                break;
1269            }
1270
1271            case TYPE_LIST:
1272            {
1273                ++parentState->childIndex;
1274                evbuffer_add_printf( data->out, ", " );
1275                jsonIndent( data );
1276                break;
1277            }
1278
1279            default:
1280                break;
1281        }
1282    }
1283}
1284
1285static void
1286jsonPushParent( struct jsonWalk * data,
1287                const tr_benc *   benc )
1288{
1289    struct ParentState * parentState = tr_new( struct ParentState, 1 );
1290
1291    parentState->bencType = benc->type;
1292    parentState->childIndex = 0;
1293    parentState->childCount = benc->val.l.count;
1294    tr_list_prepend( &data->parents, parentState );
1295}
1296
1297static void
1298jsonPopParent( struct jsonWalk * data )
1299{
1300    tr_free( tr_list_pop_front( &data->parents ) );
1301}
1302
1303static void
1304jsonIntFunc( const tr_benc * val,
1305             void *          vdata )
1306{
1307    struct jsonWalk * data = vdata;
1308
1309    evbuffer_add_printf( data->out, "%" PRId64, val->val.i );
1310    jsonChildFunc( data );
1311}
1312
1313static void
1314jsonBoolFunc( const tr_benc * val, void * vdata )
1315{
1316    struct jsonWalk * data = vdata;
1317
1318    evbuffer_add_printf( data->out, "%s", (val->val.b?"true":"false") );
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,
1340                void *          vdata )
1341{
1342    struct jsonWalk *    data = vdata;
1343    const unsigned char *it, *end;
1344
1345    evbuffer_add_printf( data->out, "\"" );
1346    for( it = (const unsigned char*)val->val.s.s, end = it + val->val.s.i;
1347         it != end; ++it )
1348    {
1349        switch( *it )
1350        {
1351            case '/':
1352                evbuffer_add_printf( data->out, "\\/" ); break;
1353
1354            case '\b':
1355                evbuffer_add_printf( data->out, "\\b" ); break;
1356
1357            case '\f':
1358                evbuffer_add_printf( data->out, "\\f" ); break;
1359
1360            case '\n':
1361                evbuffer_add_printf( data->out, "\\n" ); break;
1362
1363            case '\r':
1364                evbuffer_add_printf( data->out, "\\r" ); break;
1365
1366            case '\t':
1367                evbuffer_add_printf( data->out, "\\t" ); break;
1368
1369            case '"':
1370                evbuffer_add_printf( data->out, "\\\"" ); break;
1371
1372            case '\\':
1373                evbuffer_add_printf( data->out, "\\\\" ); break;
1374
1375            default:
1376                if( isascii( *it ) )
1377                {
1378                    /*fprintf( stderr, "[%c]\n", *it );*/
1379                    evbuffer_add_printf( data->out, "%c", *it );
1380                }
1381                else
1382                {
1383                    const UTF8 * tmp = it;
1384                    UTF32        buf = 0;
1385                    UTF32 *      u32 = &buf;
1386                    ConversionResult result = ConvertUTF8toUTF32( &tmp, end, &u32, &buf + 1, 0 );
1387                    if( ( result != conversionOK ) && ( tmp == it ) )
1388                        ++it; /* it's beyond help; skip it */
1389                    else {
1390                        evbuffer_add_printf( data->out, "\\u%04x", (unsigned int)buf );
1391                        it = tmp - 1;
1392                    }
1393                    /*fprintf( stderr, "[\\u%04x]\n", buf );*/
1394                }
1395        }
1396    }
1397    evbuffer_add_printf( data->out, "\"" );
1398    jsonChildFunc( data );
1399}
1400
1401static void
1402jsonDictBeginFunc( const tr_benc * val,
1403                   void *          vdata )
1404{
1405    struct jsonWalk * data = vdata;
1406
1407    jsonPushParent( data, val );
1408    evbuffer_add_printf( data->out, "{" );
1409    if( val->val.l.count )
1410        jsonIndent( data );
1411}
1412
1413static void
1414jsonListBeginFunc( const tr_benc * val,
1415                   void *          vdata )
1416{
1417    const size_t      nChildren = tr_bencListSize( val );
1418    struct jsonWalk * data = vdata;
1419
1420    jsonPushParent( data, val );
1421    evbuffer_add_printf( data->out, "[" );
1422    if( nChildren )
1423        jsonIndent( data );
1424}
1425
1426static void
1427jsonContainerEndFunc( const tr_benc * val,
1428                      void *          vdata )
1429{
1430    size_t            i;
1431    struct jsonWalk * data = vdata;
1432    char *            str;
1433    int               emptyContainer = FALSE;
1434
1435    /* trim out the trailing comma, if any */
1436    str = (char*) EVBUFFER_DATA( data->out );
1437    for( i = EVBUFFER_LENGTH( data->out ) - 1; i > 0; --i )
1438    {
1439        if( isspace( str[i] ) ) continue;
1440        if( str[i] == ',' )
1441            EVBUFFER_LENGTH( data->out ) = i;
1442        if( str[i] == '{' || str[i] == '[' )
1443            emptyContainer = TRUE;
1444        break;
1445    }
1446
1447    jsonPopParent( data );
1448    if( !emptyContainer )
1449        jsonIndent( data );
1450    if( tr_bencIsDict( val ) )
1451        evbuffer_add_printf( data->out, "}" );
1452    else /* list */
1453        evbuffer_add_printf( data->out, "]" );
1454    jsonChildFunc( data );
1455}
1456
1457char*
1458tr_bencSaveAsJSON( const tr_benc * top, struct evbuffer * out )
1459{
1460    struct WalkFuncs walkFuncs;
1461    struct jsonWalk  data;
1462
1463    evbuffer_drain( out, EVBUFFER_LENGTH( out ) );
1464
1465    data.out = out;
1466    data.parents = NULL;
1467
1468    walkFuncs.intFunc = jsonIntFunc;
1469    walkFuncs.boolFunc = jsonBoolFunc;
1470    walkFuncs.realFunc = jsonRealFunc;
1471    walkFuncs.stringFunc = jsonStringFunc;
1472    walkFuncs.dictBeginFunc = jsonDictBeginFunc;
1473    walkFuncs.listBeginFunc = jsonListBeginFunc;
1474    walkFuncs.containerEndFunc = jsonContainerEndFunc;
1475
1476    bencWalk( top, &walkFuncs, &data );
1477
1478    if( EVBUFFER_LENGTH( out ) )
1479        evbuffer_add_printf( out, "\n" );
1480
1481    return (char*) EVBUFFER_DATA( out );
1482}
1483
1484char*
1485tr_bencToJSON( const tr_benc * top )
1486{
1487    char * ret;
1488    struct evbuffer * buf = evbuffer_new( );
1489    tr_bencSaveAsJSON( top, buf );
1490    ret = tr_strndup( EVBUFFER_DATA( buf ), EVBUFFER_LENGTH( buf ) );
1491    evbuffer_free( buf );
1492    return ret;
1493}
1494
1495/***
1496****
1497***/
1498
1499static size_t
1500tr_bencDictSize( const tr_benc * dict )
1501{
1502    size_t count = 0;
1503
1504    if( tr_bencIsDict( dict ) )
1505        count = dict->val.l.count / 2;
1506
1507    return count;
1508}
1509
1510static tr_bool
1511tr_bencDictChild( const tr_benc * dict, size_t n, const char ** key, const tr_benc ** val )
1512{
1513    tr_bool success = 0;
1514
1515    assert( tr_bencIsDict( dict ) );
1516
1517    if( tr_bencIsDict( dict ) && (n*2)+1 <= dict->val.l.count )
1518    {
1519        tr_benc * k = dict->val.l.vals + (n*2);
1520        tr_benc * v = dict->val.l.vals + (n*2) + 1;
1521        if(( success = tr_bencGetStr( k, key ) && isSomething( v )))
1522            *val = v;
1523    }
1524
1525    return success;
1526}
1527
1528void 
1529tr_bencMergeDicts( tr_benc * target, const tr_benc * source )
1530{
1531    size_t i;
1532    const size_t sourceCount = tr_bencDictSize( source );
1533
1534    assert( tr_bencIsDict( target ) );
1535    assert( tr_bencIsDict( source ) );
1536
1537    for( i=0; i<sourceCount; ++i )
1538    {
1539        const char * key;
1540        const tr_benc * val;
1541
1542        if( tr_bencDictChild( source, i, &key, &val ) )
1543        {
1544            int64_t i64;
1545            const char * str;
1546            tr_benc * t;
1547
1548            if( tr_bencGetInt( val, &i64 ) )
1549            {
1550                tr_bencDictRemove( target, key );
1551                tr_bencDictAddInt( target, key, i64 );
1552            }
1553            else if( tr_bencGetStr( val, &str ) )
1554            {
1555                tr_bencDictRemove( target, key );
1556                tr_bencDictAddStr( target, key, str );
1557            }
1558            else if( tr_bencIsDict( val ) && tr_bencDictFindDict( target, key, &t ) )
1559            {
1560                tr_bencMergeDicts( t, val );
1561            }
1562            else
1563            {
1564           
1565                tr_dbg( "tr_bencMergeDicts skipping \"%s\"", key );
1566            }
1567        }
1568    }
1569}
1570
1571/***
1572****
1573***/ 
1574
1575static int
1576saveFile( const char * filename,
1577          const char * content,
1578          size_t       len )
1579{
1580    int    err = 0;
1581    FILE * out = NULL;
1582
1583    out = fopen( filename, "wb+" );
1584
1585    if( !out )
1586    {
1587        err = errno;
1588        tr_err( _( "Couldn't open \"%1$s\": %2$s" ),
1589                filename, tr_strerror( errno ) );
1590    }
1591    else if( fwrite( content, sizeof( char ), len, out ) != (size_t)len )
1592    {
1593        err = errno;
1594        tr_err( _( "Couldn't save file \"%1$s\": %2$s" ),
1595               filename, tr_strerror( errno ) );
1596    }
1597
1598    if( !err )
1599        tr_dbg( "tr_bencSaveFile saved \"%s\"", filename );
1600    if( out )
1601        fclose( out );
1602    return err;
1603}
1604
1605int
1606tr_bencSaveFile( const char *    filename,
1607                 const tr_benc * b )
1608{
1609    int       len;
1610    char *    content = tr_bencSave( b, &len );
1611    const int err = saveFile( filename, content, len );
1612
1613    tr_free( content );
1614    return err;
1615}
1616
1617int
1618tr_bencSaveJSONFile( const char *    filename,
1619                     const tr_benc * b )
1620{
1621    struct evbuffer * buf = tr_getBuffer( );
1622    const char * json = tr_bencSaveAsJSON( b, buf );
1623    const int err = saveFile( filename, json, EVBUFFER_LENGTH( buf ) );
1624    tr_releaseBuffer( buf );
1625    return err;
1626}
1627
1628/***
1629****
1630***/
1631
1632int
1633tr_bencLoadFile( const char * filename, tr_benc * b )
1634{
1635    int       err;
1636    size_t    contentLen;
1637    uint8_t * content;
1638
1639    content = tr_loadFile( filename, &contentLen );
1640    if( !content && errno )
1641        err = errno;
1642    else if( !content )
1643        err = ENODATA;
1644    else
1645        err = tr_bencLoad( content, contentLen, b, NULL );
1646
1647    tr_free( content );
1648    return err;
1649}
1650
1651int
1652tr_bencLoadJSONFile( const char * filename, tr_benc * b )
1653{
1654    int        err;
1655    size_t     contentLen;
1656    uint8_t  * content;
1657
1658    content = tr_loadFile( filename, &contentLen );
1659    if( !content && errno )
1660        err = errno;
1661    else if( !content )
1662        err = ENODATA;
1663    else
1664        err = tr_jsonParse( content, contentLen, b, NULL );
1665
1666    tr_free( content );
1667    return err;
1668}
Note: See TracBrowser for help on using the repository browser.