source: trunk/libtransmission/bencode.c @ 3921

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

some progress on the overall statistics, though probably not visible to end users yet

  • Property svn:keywords set to Date Rev Author Id
File size: 12.5 KB
Line 
1/******************************************************************************
2 * $Id: bencode.c 3921 2007-11-21 20:03:53Z charles $
3 *
4 * Copyright (c) 2005-2007 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 <stdarg.h>
28#include <stdio.h>
29#include <stdlib.h>
30
31#include <event.h>
32
33#include "transmission.h"
34#include "bencode.h"
35#include "utils.h"
36
37/**
38***
39**/
40
41static int
42tr_bencIsInt ( const benc_val_t * val ) {
43    return val!=NULL && val->type==TYPE_INT;
44}
45
46static int
47tr_bencIsList( const benc_val_t * val ) {
48    return val!=NULL && val->type==TYPE_LIST;
49}
50
51static int
52tr_bencIsDict( const benc_val_t * val ) {
53    return val!=NULL && val->type==TYPE_DICT;
54}
55
56/**
57***
58**/
59
60/* setting to 1 to help expose bugs with tr_bencListAdd and tr_bencDictAdd */
61#define LIST_SIZE   20 /* number of items to increment list/dict buffer by */
62
63static int makeroom( benc_val_t * val, int count )
64{
65    assert( TYPE_LIST == val->type || TYPE_DICT == val->type );
66
67    if( val->val.l.count + count > val->val.l.alloc )
68    {
69        /* We need a bigger boat */
70        const int len = val->val.l.alloc + count +
71            ( count % LIST_SIZE ? LIST_SIZE - ( count % LIST_SIZE ) : 0 );
72        void * new = realloc( val->val.l.vals, len * sizeof( benc_val_t ) );
73        if( NULL == new )
74            return 1;
75
76        val->val.l.alloc = len;
77        val->val.l.vals  = new;
78    }
79
80    return 0;
81}
82
83int _tr_bencLoad( char * buf, int len, benc_val_t * val, char ** end )
84{
85    char * p, * e, * foo;
86
87    if( !end )
88    {
89        /* So we only have to check once */
90        end = &foo;
91    }
92
93    for( ;; )
94    {
95        if( !buf || len<1 ) /* no more text to parse... */
96            return 1;
97
98        if( *buf=='i' ) /* Integer: i1234e */
99        {
100            int64_t num;
101
102            e = memchr( &buf[1], 'e', len - 1 );
103            if( !e )
104                return 1;
105
106            *e = '\0';
107            num = strtoll( &buf[1], &p, 10 );
108            *e = 'e';
109
110            if( p != e )
111                return 1;
112
113            tr_bencInitInt( val, num );
114            *end = p + 1;
115            break;
116        }
117        else if( *buf=='l' || *buf=='d' )
118        {
119            /* List: l<item1><item2>e
120               Dict: d<string1><item1><string2><item2>e
121               A dictionary is just a special kind of list with an even
122               count of items, and where even items are strings. */
123            char * cur;
124            char   is_dict;
125            char   str_expected;
126
127            is_dict      = ( buf[0] == 'd' );
128            cur          = &buf[1];
129            str_expected = 1;
130            tr_bencInit( val, ( is_dict ? TYPE_DICT : TYPE_LIST ) );
131            while( cur - buf < len && cur[0] != 'e' )
132            {
133                if( makeroom( val, 1 ) ||
134                    tr_bencLoad( cur, len - (cur - buf),
135                                 &val->val.l.vals[val->val.l.count], &p ) )
136                {
137                    tr_bencFree( val );
138                    return 1;
139                }
140                val->val.l.count++;
141                if( is_dict && str_expected &&
142                    val->val.l.vals[val->val.l.count - 1].type != TYPE_STR )
143                {
144                    tr_bencFree( val );
145                    return 1;
146                }
147                str_expected = !str_expected;
148
149                cur = p;
150            }
151
152            if( is_dict && ( val->val.l.count & 1 ) )
153            {
154                tr_bencFree( val );
155                return 1;
156            }
157
158            *end = cur + 1;
159            break;
160        }
161        else if( isdigit(*buf) )
162        {
163            int    slen;
164            char * sbuf;
165
166            e = memchr( buf, ':', len );
167            if( NULL == e )
168            {
169                return 1;
170            }
171
172            /* String: 12:whateverword */
173            e[0] = '\0';
174            slen = strtol( buf, &p, 10 );
175            e[0] = ':';
176
177            if( p != e || 0 > slen || len - ( ( p + 1 ) - buf ) < slen )
178            {
179                return 1;
180            }
181
182            sbuf = malloc( slen + 1 );
183            if( NULL == sbuf )
184            {
185                return 1;
186            }
187
188            memcpy( sbuf, p + 1, slen );
189            sbuf[slen] = '\0';
190            tr_bencInitStr( val, sbuf, slen, 0 );
191
192            *end = p + 1 + val->val.s.i;
193            break;
194        }
195        else /* invalid bencoded text... march past it */
196        {
197            ++buf;
198            --len;
199        }
200    }
201
202    val->begin = buf;
203    val->end   = *end;
204
205    return 0;
206}
207
208static void __bencPrint( benc_val_t * val, int space )
209{
210    int ii;
211
212    for( ii = 0; ii < space; ii++ )
213    {
214        putc( ' ', stderr );
215    }
216
217    switch( val->type )
218    {
219        case TYPE_INT:
220            fprintf( stderr, "int:  %"PRId64"\n", tr_bencGetInt(val) );
221            break;
222
223        case TYPE_STR:
224            for( ii = 0; val->val.s.i > ii; ii++ )
225            {
226                if( '\\' == val->val.s.s[ii] )
227                {
228                    putc( '\\', stderr );
229                    putc( '\\', stderr );
230                }
231                else if( isprint( val->val.s.s[ii] ) )
232                {
233                    putc( val->val.s.s[ii], stderr );
234                }
235                else
236                {
237                    fprintf( stderr, "\\x%02x", val->val.s.s[ii] );
238                }
239            }
240            putc( '\n', stderr );
241            break;
242
243        case TYPE_LIST:
244            fprintf( stderr, "list\n" );
245            for( ii = 0; ii < val->val.l.count; ii++ )
246            {
247                __bencPrint( &val->val.l.vals[ii], space + 1 );
248            }
249            break;
250
251        case TYPE_DICT:
252            fprintf( stderr, "dict\n" );
253            for( ii = 0; ii < val->val.l.count; ii++ )
254            {
255                __bencPrint( &val->val.l.vals[ii], space + 1 );
256            }
257            break;
258    }
259}
260
261void tr_bencPrint( benc_val_t * val )
262{
263    __bencPrint( val, 0 );
264}
265
266void tr_bencFree( benc_val_t * val )
267{
268    int i;
269
270    switch( val->type )
271    {
272        case TYPE_INT:
273            break;
274
275        case TYPE_STR:
276            if( !val->val.s.nofree )
277            {
278                free( val->val.s.s );
279            }
280            break;
281
282        case TYPE_LIST:
283        case TYPE_DICT:
284            for( i = 0; i < val->val.l.count; i++ )
285            {
286                tr_bencFree( &val->val.l.vals[i] );
287            }
288            free( val->val.l.vals );
289            break;
290    }
291}
292
293benc_val_t * tr_bencDictFind( benc_val_t * val, const char * key )
294{
295    int len, ii;
296
297    if( val->type != TYPE_DICT )
298    {
299        return NULL;
300    }
301
302    len = strlen( key );
303   
304    for( ii = 0; ii + 1 < val->val.l.count; ii += 2 )
305    {
306        if( TYPE_STR  != val->val.l.vals[ii].type ||
307            len       != val->val.l.vals[ii].val.s.i ||
308            0 != memcmp( val->val.l.vals[ii].val.s.s, key, len ) )
309        {
310            continue;
311        }
312        return &val->val.l.vals[ii+1];
313    }
314
315    return NULL;
316}
317
318benc_val_t * tr_bencDictFindFirst( benc_val_t * val, ... )
319{
320    const char * key;
321    benc_val_t * ret;
322    va_list      ap;
323
324    ret = NULL;
325    va_start( ap, val );
326    while( ( key = va_arg( ap, const char * ) ) )
327    {
328        ret = tr_bencDictFind( val, key );
329        if( NULL != ret )
330        {
331            break;
332        }
333    }
334    va_end( ap );
335
336    return ret;
337}
338
339char * tr_bencStealStr( benc_val_t * val )
340{
341    assert( TYPE_STR == val->type );
342    val->val.s.nofree = 1;
343    return val->val.s.s;
344}
345
346void _tr_bencInitStr( benc_val_t * val, char * str, int len, int nofree )
347{
348    tr_bencInit( val, TYPE_STR );
349    val->val.s.s      = str;
350    val->val.s.nofree = nofree;
351    if( 0 >= len )
352    {
353        len = ( NULL == str ? 0 : strlen( str ) );
354    }
355    val->val.s.i = len;
356}
357
358int tr_bencInitStrDup( benc_val_t * val, const char * str )
359{
360    char * newStr = tr_strdup( str );
361    if( newStr == NULL )
362        return 1;
363
364    _tr_bencInitStr( val, newStr, 0, 0 );
365    return 0;
366}
367
368void tr_bencInitInt( benc_val_t * val, int64_t num )
369{
370    tr_bencInit( val, TYPE_INT );
371    val->val.i = num;
372}
373
374int tr_bencListReserve( benc_val_t * val, int count )
375{
376    assert( TYPE_LIST == val->type );
377
378    return makeroom( val, count );
379}
380
381int tr_bencDictReserve( benc_val_t * val, int count )
382{
383    assert( TYPE_DICT == val->type );
384
385    return makeroom( val, count * 2 );
386}
387
388benc_val_t * tr_bencListAdd( benc_val_t * list )
389{
390    benc_val_t * item;
391
392    assert( tr_bencIsList( list ) );
393    assert( list->val.l.count < list->val.l.alloc );
394
395    item = &list->val.l.vals[list->val.l.count];
396    list->val.l.count++;
397    tr_bencInit( item, TYPE_INT );
398
399    return item;
400}
401
402benc_val_t * tr_bencDictAdd( benc_val_t * dict, const char * key )
403{
404    benc_val_t * keyval, * itemval;
405
406    assert( tr_bencIsDict( dict ) );
407    assert( dict->val.l.count + 2 <= dict->val.l.alloc );
408
409    keyval = dict->val.l.vals + dict->val.l.count++;
410    tr_bencInitStr( keyval, (char*)key, -1, 1 );
411
412    itemval = dict->val.l.vals + dict->val.l.count++;
413    tr_bencInit( itemval, TYPE_INT );
414
415    return itemval;
416}
417
418struct KeyIndex
419{
420    const char * key;
421    int index;
422};
423
424static int compareKeyIndex( const void * va, const void * vb )
425{
426    const struct KeyIndex * a = va;
427    const struct KeyIndex * b = vb;
428    return strcmp( a->key, b->key );
429}
430
431static void
432saveImpl( struct evbuffer * out, const benc_val_t * val )
433{
434    int ii;
435
436    switch( val->type )
437    {
438        case TYPE_INT:
439            evbuffer_add_printf( out, "i%"PRId64"e", tr_bencGetInt(val) );
440            break;
441
442        case TYPE_STR:
443            evbuffer_add_printf( out, "%i:", val->val.s.i );
444            evbuffer_add( out, val->val.s.s, val->val.s.i );
445            break;
446
447        case TYPE_LIST:
448            evbuffer_add_printf( out, "l" );
449            for( ii = 0; val->val.l.count > ii; ii++ )
450                saveImpl( out, val->val.l.vals + ii );
451            evbuffer_add_printf( out, "e" );
452            break;
453
454        case TYPE_DICT:
455            /* Keys must be strings and appear in sorted order
456               (sorted as raw strings, not alphanumerics). */
457            evbuffer_add_printf( out, "d" );
458            if( 1 ) {
459                int i;
460                struct KeyIndex * indices = tr_new( struct KeyIndex, val->val.l.count );
461                for( ii=i=0; i<val->val.l.count; i+=2 ) {
462                    indices[ii].key = val->val.l.vals[i].val.s.s;
463                    indices[ii].index = i;
464                    ii++;
465                }
466                qsort( indices, ii, sizeof(struct KeyIndex), compareKeyIndex );
467                for( i=0; i<ii; ++i ) {
468                    const int index = indices[i].index;
469                    saveImpl( out, val->val.l.vals + index );
470                    saveImpl( out, val->val.l.vals + index + 1 );
471                }
472                tr_free( indices );
473            }
474            evbuffer_add_printf( out, "e" );
475            break;
476    }
477}
478
479char*
480tr_bencSave( const benc_val_t * val, int * len )
481{
482    struct evbuffer * buf = evbuffer_new( );
483    char * ret;
484    saveImpl( buf, val );
485    if( len != NULL )
486        *len = EVBUFFER_LENGTH( buf );
487    ret = tr_strndup( (char*) EVBUFFER_DATA( buf ), EVBUFFER_LENGTH( buf ) );
488    evbuffer_free( buf );
489    return ret;
490}
491
492/**
493***
494**/
495
496benc_val_t*
497tr_bencDictFindType( benc_val_t * val, const char * key, int type )
498{
499    benc_val_t * ret = tr_bencDictFind( val, key );
500    return ret && ret->type == type ? ret : NULL;
501}
502
503int64_t
504tr_bencGetInt ( const benc_val_t * val )
505{
506    assert( tr_bencIsInt( val ) );
507    return val->val.i;
508}
Note: See TracBrowser for help on using the repository browser.