source: trunk/libtransmission/bencode.c @ 8179

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

(trunk libT) faster serialization from tr_benc structs into json and benc formats

  • 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 8179 2009-04-08 17:25:17Z 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    int i;
1238    char buf[1024], *pch=buf;
1239    const int width = tr_list_size( data->parents ) * 4;
1240
1241    *pch++ = '\n';
1242    for( i=0; i<width; ++i )
1243        *pch++ = ' ';
1244
1245    evbuffer_add( data->out, buf, pch-buf );
1246}
1247
1248static void
1249jsonChildFunc( struct jsonWalk * data )
1250{
1251    if( data->parents )
1252    {
1253        struct ParentState * parentState = data->parents->data;
1254
1255        switch( parentState->bencType )
1256        {
1257            case TR_TYPE_DICT:
1258            {
1259                const int i = parentState->childIndex++;
1260                if( !( i % 2 ) )
1261                    evbuffer_add( data->out, ": ", 2 );
1262                else
1263                {
1264                    evbuffer_add( data->out, ", ", 2 );
1265                    jsonIndent( data );
1266                }
1267                break;
1268            }
1269
1270            case TR_TYPE_LIST:
1271            {
1272                ++parentState->childIndex;
1273                evbuffer_add( data->out, ", ", 2 );
1274                jsonIndent( data );
1275                break;
1276            }
1277
1278            default:
1279                break;
1280        }
1281    }
1282}
1283
1284static void
1285jsonPushParent( struct jsonWalk * data,
1286                const tr_benc *   benc )
1287{
1288    struct ParentState * parentState = tr_new( struct ParentState, 1 );
1289
1290    parentState->bencType = benc->type;
1291    parentState->childIndex = 0;
1292    parentState->childCount = benc->val.l.count;
1293    tr_list_prepend( &data->parents, parentState );
1294}
1295
1296static void
1297jsonPopParent( struct jsonWalk * data )
1298{
1299    tr_free( tr_list_pop_front( &data->parents ) );
1300}
1301
1302static void
1303jsonIntFunc( const tr_benc * val,
1304             void *          vdata )
1305{
1306    struct jsonWalk * data = vdata;
1307
1308    evbuffer_add_printf( data->out, "%" PRId64, val->val.i );
1309    jsonChildFunc( data );
1310}
1311
1312static void
1313jsonBoolFunc( const tr_benc * val, void * vdata )
1314{
1315    struct jsonWalk * data = vdata;
1316
1317    if( val->val.b )
1318        evbuffer_add( data->out, "true", 4 );
1319    else
1320        evbuffer_add( data->out, "false", 5 );
1321
1322    jsonChildFunc( data );
1323}
1324
1325static void
1326jsonRealFunc( const tr_benc * val, void * vdata )
1327{
1328    struct jsonWalk * data = vdata;
1329    char * locale;
1330
1331    /* json requires a '.' decimal point regardless of locale */
1332    locale = tr_strdup( setlocale ( LC_NUMERIC, NULL ) );
1333    setlocale( LC_NUMERIC, "POSIX" );
1334    evbuffer_add_printf( data->out, "%f", val->val.d );
1335    setlocale( LC_NUMERIC, locale );
1336    tr_free( locale );
1337
1338    jsonChildFunc( data );
1339}
1340
1341static void
1342jsonStringFunc( const tr_benc * val, void * vdata )
1343{
1344    struct jsonWalk * data = vdata;
1345    const unsigned char *it, *end;
1346
1347    evbuffer_add( data->out, "\"", 1 );
1348    for( it = (const unsigned char*)val->val.s.s, end = it + val->val.s.i;
1349         it != end; ++it )
1350    {
1351        switch( *it )
1352        {
1353            case '"':
1354            case '\\':
1355            case '/':
1356            case '\b':
1357            case '\f':
1358            case '\n':
1359            case '\r':
1360            case '\t': {
1361                char buf[2] = { '\\', *it };
1362                evbuffer_add( data->out, buf, 2 );
1363                break;
1364            }
1365
1366            default:
1367                if( isascii( *it ) )
1368                {
1369                    /*fprintf( stderr, "[%c]\n", *it );*/
1370                    evbuffer_add( data->out, it, 1 );
1371                }
1372                else
1373                {
1374                    const UTF8 * tmp = it;
1375                    UTF32        buf = 0;
1376                    UTF32 *      u32 = &buf;
1377                    ConversionResult result = ConvertUTF8toUTF32( &tmp, end, &u32, &buf + 1, 0 );
1378                    if( ( result != conversionOK ) && ( tmp == it ) )
1379                        ++it; /* it's beyond help; skip it */
1380                    else {
1381                        evbuffer_add_printf( data->out, "\\u%04x", (unsigned int)buf );
1382                        it = tmp - 1;
1383                    }
1384                    /*fprintf( stderr, "[\\u%04x]\n", buf );*/
1385                }
1386        }
1387    }
1388    evbuffer_add( data->out, "\"", 1 );
1389    jsonChildFunc( data );
1390}
1391
1392static void
1393jsonDictBeginFunc( const tr_benc * val,
1394                   void *          vdata )
1395{
1396    struct jsonWalk * data = vdata;
1397
1398    jsonPushParent( data, val );
1399    evbuffer_add( data->out, "{", 1 );
1400    if( val->val.l.count )
1401        jsonIndent( data );
1402}
1403
1404static void
1405jsonListBeginFunc( const tr_benc * val,
1406                   void *          vdata )
1407{
1408    const size_t      nChildren = tr_bencListSize( val );
1409    struct jsonWalk * data = vdata;
1410
1411    jsonPushParent( data, val );
1412    evbuffer_add( data->out, "[", 1 );
1413    if( nChildren )
1414        jsonIndent( data );
1415}
1416
1417static void
1418jsonContainerEndFunc( const tr_benc * val,
1419                      void *          vdata )
1420{
1421    size_t            i;
1422    struct jsonWalk * data = vdata;
1423    char *            str;
1424    int               emptyContainer = FALSE;
1425
1426    /* trim out the trailing comma, if any */
1427    str = (char*) EVBUFFER_DATA( data->out );
1428    for( i = EVBUFFER_LENGTH( data->out ) - 1; i > 0; --i )
1429    {
1430        if( isspace( str[i] ) ) continue;
1431        if( str[i] == ',' )
1432            EVBUFFER_LENGTH( data->out ) = i;
1433        if( str[i] == '{' || str[i] == '[' )
1434            emptyContainer = TRUE;
1435        break;
1436    }
1437
1438    jsonPopParent( data );
1439    if( !emptyContainer )
1440        jsonIndent( data );
1441    if( tr_bencIsDict( val ) )
1442        evbuffer_add( data->out, "}", 1 );
1443    else /* list */
1444        evbuffer_add( data->out, "]", 1 );
1445    jsonChildFunc( data );
1446}
1447
1448char*
1449tr_bencSaveAsJSON( const tr_benc * top, struct evbuffer * out )
1450{
1451    struct WalkFuncs walkFuncs;
1452    struct jsonWalk  data;
1453
1454    evbuffer_drain( out, EVBUFFER_LENGTH( out ) );
1455
1456    data.out = out;
1457    data.parents = NULL;
1458
1459    walkFuncs.intFunc = jsonIntFunc;
1460    walkFuncs.boolFunc = jsonBoolFunc;
1461    walkFuncs.realFunc = jsonRealFunc;
1462    walkFuncs.stringFunc = jsonStringFunc;
1463    walkFuncs.dictBeginFunc = jsonDictBeginFunc;
1464    walkFuncs.listBeginFunc = jsonListBeginFunc;
1465    walkFuncs.containerEndFunc = jsonContainerEndFunc;
1466
1467    bencWalk( top, &walkFuncs, &data );
1468
1469    if( EVBUFFER_LENGTH( out ) )
1470        evbuffer_add_printf( out, "\n" );
1471
1472    return (char*) EVBUFFER_DATA( out );
1473}
1474
1475char*
1476tr_bencToJSON( const tr_benc * top )
1477{
1478    char * ret;
1479    struct evbuffer * buf = evbuffer_new( );
1480    tr_bencSaveAsJSON( top, buf );
1481    ret = tr_strndup( EVBUFFER_DATA( buf ), EVBUFFER_LENGTH( buf ) );
1482    evbuffer_free( buf );
1483    return ret;
1484}
1485
1486/***
1487****
1488***/
1489
1490static size_t
1491tr_bencDictSize( const tr_benc * dict )
1492{
1493    size_t count = 0;
1494
1495    if( tr_bencIsDict( dict ) )
1496        count = dict->val.l.count / 2;
1497
1498    return count;
1499}
1500
1501static tr_bool
1502tr_bencDictChild( const tr_benc * dict, size_t n, const char ** key, const tr_benc ** val )
1503{
1504    tr_bool success = 0;
1505
1506    assert( tr_bencIsDict( dict ) );
1507
1508    if( tr_bencIsDict( dict ) && (n*2)+1 <= dict->val.l.count )
1509    {
1510        tr_benc * k = dict->val.l.vals + (n*2);
1511        tr_benc * v = dict->val.l.vals + (n*2) + 1;
1512        if(( success = tr_bencGetStr( k, key ) && isSomething( v )))
1513            *val = v;
1514    }
1515
1516    return success;
1517}
1518
1519void 
1520tr_bencMergeDicts( tr_benc * target, const tr_benc * source )
1521{
1522    size_t i;
1523    const size_t sourceCount = tr_bencDictSize( source );
1524
1525    assert( tr_bencIsDict( target ) );
1526    assert( tr_bencIsDict( source ) );
1527
1528    for( i=0; i<sourceCount; ++i )
1529    {
1530        const char * key;
1531        const tr_benc * val;
1532        tr_benc * t;
1533
1534        if( tr_bencDictChild( source, i, &key, &val ) )
1535        {
1536            if( tr_bencIsBool( val ) )
1537            {
1538                tr_bool boolVal;
1539                tr_bencGetBool( val, &boolVal );
1540                tr_bencDictAddBool( target, key, boolVal );
1541            }
1542            else if( tr_bencIsReal( val ) )
1543            {
1544                double realVal;
1545                tr_bencGetReal( val, &realVal );
1546                tr_bencDictAddReal( target, key, realVal );
1547            }
1548            else if( tr_bencIsInt( val ) )
1549            {
1550                int64_t intVal;
1551                tr_bencGetInt( val, &intVal );
1552                tr_bencDictAddInt( target, key, intVal );
1553            }
1554            else if( tr_bencIsString( val ) )
1555            {
1556                const char * strVal;
1557                tr_bencGetStr( val, &strVal );
1558                tr_bencDictAddStr( target, key, strVal );
1559            }
1560            else if( tr_bencIsDict( val ) && tr_bencDictFindDict( target, key, &t ) )
1561            {
1562                tr_bencMergeDicts( t, val );
1563            }
1564            else
1565            {
1566                tr_dbg( "tr_bencMergeDicts skipping \"%s\"", key );
1567            }
1568        }
1569    }
1570}
1571
1572/***
1573****
1574***/ 
1575
1576static int
1577saveFile( const char * filename,
1578          const char * content,
1579          size_t       len )
1580{
1581    int    err = 0;
1582    FILE * out = NULL;
1583
1584    out = fopen( filename, "wb+" );
1585
1586    if( !out )
1587    {
1588        err = errno;
1589        tr_err( _( "Couldn't open \"%1$s\": %2$s" ),
1590                filename, tr_strerror( errno ) );
1591    }
1592    else if( fwrite( content, sizeof( char ), len, out ) != (size_t)len )
1593    {
1594        err = errno;
1595        tr_err( _( "Couldn't save file \"%1$s\": %2$s" ),
1596               filename, tr_strerror( errno ) );
1597    }
1598
1599    if( !err )
1600        tr_dbg( "tr_bencSaveFile saved \"%s\"", filename );
1601    if( out )
1602        fclose( out );
1603    return err;
1604}
1605
1606int
1607tr_bencSaveFile( const char *    filename,
1608                 const tr_benc * b )
1609{
1610    int       len;
1611    char *    content = tr_bencSave( b, &len );
1612    const int err = saveFile( filename, content, len );
1613
1614    tr_free( content );
1615    return err;
1616}
1617
1618int
1619tr_bencSaveJSONFile( const char *    filename,
1620                     const tr_benc * b )
1621{
1622    struct evbuffer * buf = tr_getBuffer( );
1623    const char * json = tr_bencSaveAsJSON( b, buf );
1624    const int err = saveFile( filename, json, EVBUFFER_LENGTH( buf ) );
1625    tr_releaseBuffer( buf );
1626    return err;
1627}
1628
1629/***
1630****
1631***/
1632
1633int
1634tr_bencLoadFile( const char * filename, tr_benc * b )
1635{
1636    int       err;
1637    size_t    contentLen;
1638    uint8_t * content;
1639
1640    content = tr_loadFile( filename, &contentLen );
1641    if( !content && errno )
1642        err = errno;
1643    else if( !content )
1644        err = ENODATA;
1645    else
1646        err = tr_bencLoad( content, contentLen, b, NULL );
1647
1648    tr_free( content );
1649    return err;
1650}
1651
1652int
1653tr_bencLoadJSONFile( const char * filename, tr_benc * b )
1654{
1655    int        err;
1656    size_t     contentLen;
1657    uint8_t  * content;
1658
1659    content = tr_loadFile( filename, &contentLen );
1660    if( !content && errno )
1661        err = errno;
1662    else if( !content )
1663        err = ENODATA;
1664    else
1665        err = tr_jsonParse( content, contentLen, b, NULL );
1666
1667    tr_free( content );
1668    return err;
1669}
Note: See TracBrowser for help on using the repository browser.