source: trunk/libtransmission/bencode.c @ 4869

Last change on this file since 4869 was 4869, checked in by charles, 15 years ago

part 1 of the bencode exploit fix:

  • better error checking for int & string parsing
  • add automated unit tests
  • Property svn:keywords set to Date Rev Author Id
File size: 14.7 KB
Line 
1/******************************************************************************
2 * $Id: bencode.c 4869 2008-01-30 15:39:41Z charles $
3 *
4 * Copyright (c) 2005-2008 Transmission authors and contributors
5 *
6 * Permission is hereby granted, free of charge, to any person obtaining a
7 * copy of this software and associated documentation files (the "Software"),
8 * to deal in the Software without restriction, including without limitation
9 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
10 * and/or sell copies of the Software, and to permit persons to whom the
11 * Software is furnished to do so, subject to the following conditions:
12 *
13 * The above copyright notice and this permission notice shall be included in
14 * all copies or substantial portions of the Software.
15 *
16 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
21 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
22 * DEALINGS IN THE SOFTWARE.
23 *****************************************************************************/
24
25#include <assert.h>
26#include <ctype.h> /* isdigit, isprint */
27#include <errno.h>
28#include <stdarg.h>
29#include <stdio.h>
30#include <stdlib.h>
31
32#include <event.h>
33
34#include "transmission.h"
35#include "bencode.h"
36#include "utils.h"
37
38/**
39***
40**/
41
42static int
43tr_bencIsInt ( const benc_val_t * val ) {
44    return val!=NULL && val->type==TYPE_INT;
45}
46
47static int
48tr_bencIsList( const benc_val_t * val ) {
49    return val!=NULL && val->type==TYPE_LIST;
50}
51
52static int
53tr_bencIsDict( const benc_val_t * val ) {
54    return val!=NULL && val->type==TYPE_DICT;
55}
56
57/**
58***
59**/
60
61/**
62 * The initial i and trailing e are beginning and ending delimiters.
63 * You can have negative numbers such as i-3e. You cannot prefix the
64 * number with a zero such as i04e. However, i0e is valid. 
65 * Example: i3e represents the integer "3"
66 * NOTE: The maximum number of bit of this integer is unspecified,
67 * but to handle it as a signed 64bit integer is mandatory to handle
68 * "large files" aka .torrent for more that 4Gbyte
69 */
70int
71tr_bencParseInt( const uint8_t  * buf,
72                 size_t           buflen,
73                 const uint8_t ** setme_end, 
74                 int64_t        * setme_val )
75{
76    int err = TR_OK;
77    char * endptr;
78    const void * begin;
79    const void * end;
80    int64_t val;
81
82    if( !buflen )
83        return TR_ERROR;
84    if( *buf != 'i' )
85        return TR_ERROR;
86
87    begin = buf + 1;
88    end = memchr( begin, 'e', buflen-1 );
89    if( end == NULL )
90        return TR_ERROR;
91
92    errno = 0;
93    val = strtoll( begin, &endptr, 10 );
94    if( errno || ( endptr != end ) ) /* incomplete parse */
95        err = TR_ERROR;
96    else if( val && *(const char*)begin=='0' ) /* the spec forbids leading zeroes */
97        err = TR_ERROR;
98    else {
99        *setme_end = end + 1;
100        *setme_val = val;
101    }
102
103    return err;
104}
105
106
107/**
108 * Byte strings are encoded as follows:
109 * <string length encoded in base ten ASCII>:<string data>
110 * Note that there is no constant beginning delimiter, and no ending delimiter.
111 * Example: 4:spam represents the string "spam"
112 */
113int
114tr_bencParseStr( const uint8_t  * buf,
115                 size_t           buflen,
116                 const uint8_t ** setme_end,
117                 uint8_t       ** setme_str,
118                 size_t         * setme_strlen )
119{
120    size_t len;
121    const void * end;
122    char * endptr;
123
124    if( !buflen )
125        return TR_ERROR;
126
127    if( !isdigit( *buf  ) )
128        return TR_ERROR;
129
130    end = memchr( buf, ':', buflen );
131    if( end == NULL )
132        return TR_ERROR;
133
134    errno = 0;
135    len = strtoul( (const char*)buf, &endptr, 10 );
136    if( errno || endptr!=end )
137        return TR_ERROR;
138
139    if( ( (const uint8_t*)end - buf ) + 1 + len > buflen )
140        return TR_ERROR;
141
142    *setme_end = end + 1 + len;
143    *setme_str = (uint8_t*) tr_strndup( end + 1, len );
144    *setme_strlen = len;
145    return TR_OK;
146}
147
148/* setting to 1 to help expose bugs with tr_bencListAdd and tr_bencDictAdd */
149#define LIST_SIZE   20 /* number of items to increment list/dict buffer by */
150
151static int makeroom( benc_val_t * val, int count )
152{
153    assert( TYPE_LIST == val->type || TYPE_DICT == val->type );
154
155    if( val->val.l.count + count > val->val.l.alloc )
156    {
157        /* We need a bigger boat */
158        const int len = val->val.l.alloc + count +
159            ( count % LIST_SIZE ? LIST_SIZE - ( count % LIST_SIZE ) : 0 );
160        void * new = realloc( val->val.l.vals, len * sizeof( benc_val_t ) );
161        if( NULL == new )
162            return 1;
163
164        val->val.l.alloc = len;
165        val->val.l.vals  = new;
166    }
167
168    return 0;
169}
170
171int _tr_bencLoad( char * buf, int len, benc_val_t * val, char ** end )
172{
173    char * p, * e, * foo;
174
175    if( !end )
176    {
177        /* So we only have to check once */
178        end = &foo;
179    }
180
181    for( ;; )
182    {
183        if( !buf || len<1 ) /* no more text to parse... */
184            return 1;
185
186        if( *buf=='i' ) /* Integer: i1234e */
187        {
188            int64_t num;
189
190            e = memchr( &buf[1], 'e', len - 1 );
191            if( !e )
192                return 1;
193
194            *e = '\0';
195            num = strtoll( &buf[1], &p, 10 );
196            *e = 'e';
197
198            if( p != e )
199                return 1;
200
201            tr_bencInitInt( val, num );
202            *end = p + 1;
203            break;
204        }
205        else if( *buf=='l' || *buf=='d' )
206        {
207            /* List: l<item1><item2>e
208               Dict: d<string1><item1><string2><item2>e
209               A dictionary is just a special kind of list with an even
210               count of items, and where even items are strings. */
211            char * cur;
212            char   is_dict;
213            char   str_expected;
214
215            is_dict      = ( buf[0] == 'd' );
216            cur          = &buf[1];
217            str_expected = 1;
218            tr_bencInit( val, ( is_dict ? TYPE_DICT : TYPE_LIST ) );
219            while( cur - buf < len && cur[0] != 'e' )
220            {
221                if( makeroom( val, 1 ) ||
222                    tr_bencLoad( cur, len - (cur - buf),
223                                 &val->val.l.vals[val->val.l.count], &p ) )
224                {
225                    tr_bencFree( val );
226                    return 1;
227                }
228                val->val.l.count++;
229                if( is_dict && str_expected &&
230                    val->val.l.vals[val->val.l.count - 1].type != TYPE_STR )
231                {
232                    tr_bencFree( val );
233                    return 1;
234                }
235                str_expected = !str_expected;
236
237                cur = p;
238            }
239
240            if( is_dict && ( val->val.l.count & 1 ) )
241            {
242                tr_bencFree( val );
243                return 1;
244            }
245
246            *end = cur + 1;
247            break;
248        }
249        else if( isdigit(*buf) )
250        {
251            int    slen;
252            char * sbuf;
253
254            e = memchr( buf, ':', len );
255            if( NULL == e )
256            {
257                return 1;
258            }
259
260            /* String: 12:whateverword */
261            e[0] = '\0';
262            slen = strtol( buf, &p, 10 );
263            e[0] = ':';
264
265            if( p != e || 0 > slen || len - ( ( p + 1 ) - buf ) < slen )
266            {
267                return 1;
268            }
269
270            sbuf = malloc( slen + 1 );
271            if( NULL == sbuf )
272            {
273                return 1;
274            }
275
276            memcpy( sbuf, p + 1, slen );
277            sbuf[slen] = '\0';
278            tr_bencInitStr( val, sbuf, slen, 0 );
279
280            *end = p + 1 + val->val.s.i;
281            break;
282        }
283        else /* invalid bencoded text... march past it */
284        {
285            ++buf;
286            --len;
287        }
288    }
289
290    return 0;
291}
292
293static void __bencPrint( benc_val_t * val, int space )
294{
295    int ii;
296
297    for( ii = 0; ii < space; ii++ )
298    {
299        putc( ' ', stderr );
300    }
301
302    switch( val->type )
303    {
304        case TYPE_INT:
305            fprintf( stderr, "int:  %"PRId64"\n", tr_bencGetInt(val) );
306            break;
307
308        case TYPE_STR:
309            for( ii = 0; val->val.s.i > ii; ii++ )
310            {
311                if( '\\' == val->val.s.s[ii] )
312                {
313                    putc( '\\', stderr );
314                    putc( '\\', stderr );
315                }
316                else if( isprint( val->val.s.s[ii] ) )
317                {
318                    putc( val->val.s.s[ii], stderr );
319                }
320                else
321                {
322                    fprintf( stderr, "\\x%02x", val->val.s.s[ii] );
323                }
324            }
325            putc( '\n', stderr );
326            break;
327
328        case TYPE_LIST:
329            fprintf( stderr, "list\n" );
330            for( ii = 0; ii < val->val.l.count; ii++ )
331            {
332                __bencPrint( &val->val.l.vals[ii], space + 1 );
333            }
334            break;
335
336        case TYPE_DICT:
337            fprintf( stderr, "dict\n" );
338            for( ii = 0; ii < val->val.l.count; ii++ )
339            {
340                __bencPrint( &val->val.l.vals[ii], space + 1 );
341            }
342            break;
343    }
344}
345
346void tr_bencPrint( benc_val_t * val )
347{
348    __bencPrint( val, 0 );
349}
350
351void tr_bencFree( benc_val_t * val )
352{
353    int i;
354
355    switch( val->type )
356    {
357        case TYPE_INT:
358            break;
359
360        case TYPE_STR:
361            if( !val->val.s.nofree )
362            {
363                free( val->val.s.s );
364            }
365            break;
366
367        case TYPE_LIST:
368        case TYPE_DICT:
369            for( i = 0; i < val->val.l.count; i++ )
370            {
371                tr_bencFree( &val->val.l.vals[i] );
372            }
373            free( val->val.l.vals );
374            break;
375    }
376}
377
378benc_val_t * tr_bencDictFind( benc_val_t * val, const char * key )
379{
380    int len, ii;
381
382    if( val->type != TYPE_DICT )
383    {
384        return NULL;
385    }
386
387    len = strlen( key );
388   
389    for( ii = 0; ii + 1 < val->val.l.count; ii += 2 )
390    {
391        if( TYPE_STR  != val->val.l.vals[ii].type ||
392            len       != val->val.l.vals[ii].val.s.i ||
393            0 != memcmp( val->val.l.vals[ii].val.s.s, key, len ) )
394        {
395            continue;
396        }
397        return &val->val.l.vals[ii+1];
398    }
399
400    return NULL;
401}
402
403benc_val_t * tr_bencDictFindFirst( benc_val_t * val, ... )
404{
405    const char * key;
406    benc_val_t * ret;
407    va_list      ap;
408
409    ret = NULL;
410    va_start( ap, val );
411    while( ( key = va_arg( ap, const char * ) ) )
412    {
413        ret = tr_bencDictFind( val, key );
414        if( NULL != ret )
415        {
416            break;
417        }
418    }
419    va_end( ap );
420
421    return ret;
422}
423
424char * tr_bencStealStr( benc_val_t * val )
425{
426    assert( TYPE_STR == val->type );
427    val->val.s.nofree = 1;
428    return val->val.s.s;
429}
430
431void _tr_bencInitStr( benc_val_t * val, char * str, int len, int nofree )
432{
433    tr_bencInit( val, TYPE_STR );
434    val->val.s.s      = str;
435    val->val.s.nofree = nofree;
436    if( 0 >= len )
437    {
438        len = ( NULL == str ? 0 : strlen( str ) );
439    }
440    val->val.s.i = len;
441}
442
443int tr_bencInitStrDup( benc_val_t * val, const char * str )
444{
445    char * newStr = tr_strdup( str );
446    if( newStr == NULL )
447        return 1;
448
449    _tr_bencInitStr( val, newStr, 0, 0 );
450    return 0;
451}
452
453void tr_bencInitInt( benc_val_t * val, int64_t num )
454{
455    tr_bencInit( val, TYPE_INT );
456    val->val.i = num;
457}
458
459int tr_bencListReserve( benc_val_t * val, int count )
460{
461    assert( TYPE_LIST == val->type );
462
463    return makeroom( val, count );
464}
465
466int tr_bencDictReserve( benc_val_t * val, int count )
467{
468    assert( TYPE_DICT == val->type );
469
470    return makeroom( val, count * 2 );
471}
472
473benc_val_t * tr_bencListAdd( benc_val_t * list )
474{
475    benc_val_t * item;
476
477    assert( tr_bencIsList( list ) );
478    assert( list->val.l.count < list->val.l.alloc );
479
480    item = &list->val.l.vals[list->val.l.count];
481    list->val.l.count++;
482    tr_bencInit( item, TYPE_INT );
483
484    return item;
485}
486
487benc_val_t * tr_bencDictAdd( benc_val_t * dict, const char * key )
488{
489    benc_val_t * keyval, * itemval;
490
491    assert( tr_bencIsDict( dict ) );
492    assert( dict->val.l.count + 2 <= dict->val.l.alloc );
493
494    keyval = dict->val.l.vals + dict->val.l.count++;
495    tr_bencInitStr( keyval, (char*)key, -1, 1 );
496
497    itemval = dict->val.l.vals + dict->val.l.count++;
498    tr_bencInit( itemval, TYPE_INT );
499
500    return itemval;
501}
502
503struct KeyIndex
504{
505    const char * key;
506    int index;
507};
508
509static int compareKeyIndex( const void * va, const void * vb )
510{
511    const struct KeyIndex * a = va;
512    const struct KeyIndex * b = vb;
513    return strcmp( a->key, b->key );
514}
515
516static void
517saveImpl( struct evbuffer * out, const benc_val_t * val )
518{
519    int ii;
520
521    switch( val->type )
522    {
523        case TYPE_INT:
524            evbuffer_add_printf( out, "i%"PRId64"e", tr_bencGetInt(val) );
525            break;
526
527        case TYPE_STR:
528            evbuffer_add_printf( out, "%i:", val->val.s.i );
529            evbuffer_add( out, val->val.s.s, val->val.s.i );
530            break;
531
532        case TYPE_LIST:
533            evbuffer_add_printf( out, "l" );
534            for( ii = 0; val->val.l.count > ii; ii++ )
535                saveImpl( out, val->val.l.vals + ii );
536            evbuffer_add_printf( out, "e" );
537            break;
538
539        case TYPE_DICT:
540            /* Keys must be strings and appear in sorted order
541               (sorted as raw strings, not alphanumerics). */
542            evbuffer_add_printf( out, "d" );
543            if( 1 ) {
544                int i;
545                struct KeyIndex * indices = tr_new( struct KeyIndex, val->val.l.count );
546                for( ii=i=0; i<val->val.l.count; i+=2 ) {
547                    indices[ii].key = val->val.l.vals[i].val.s.s;
548                    indices[ii].index = i;
549                    ii++;
550                }
551                qsort( indices, ii, sizeof(struct KeyIndex), compareKeyIndex );
552                for( i=0; i<ii; ++i ) {
553                    const int index = indices[i].index;
554                    saveImpl( out, val->val.l.vals + index );
555                    saveImpl( out, val->val.l.vals + index + 1 );
556                }
557                tr_free( indices );
558            }
559            evbuffer_add_printf( out, "e" );
560            break;
561    }
562}
563
564char*
565tr_bencSave( const benc_val_t * val, int * len )
566{
567    struct evbuffer * buf = evbuffer_new( );
568    char * ret;
569    saveImpl( buf, val );
570    if( len != NULL )
571        *len = EVBUFFER_LENGTH( buf );
572    ret = tr_strndup( (char*) EVBUFFER_DATA( buf ), EVBUFFER_LENGTH( buf ) );
573    evbuffer_free( buf );
574    return ret;
575}
576
577/**
578***
579**/
580
581benc_val_t*
582tr_bencDictFindType( benc_val_t * val, const char * key, int type )
583{
584    benc_val_t * ret = tr_bencDictFind( val, key );
585    return ret && ret->type == type ? ret : NULL;
586}
587
588int64_t
589tr_bencGetInt ( const benc_val_t * val )
590{
591    assert( tr_bencIsInt( val ) );
592    return val->val.i;
593}
Note: See TracBrowser for help on using the repository browser.