source: trunk/libtransmission/bencode.c @ 2228

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

get the bencoded text compliant with the bittorrent spec w.r.t. dictionaries: "keys must be strings and appear in sorted order (sorted as raw strings, not alphanumerics)."

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