← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/_bencode_c.pyx

  • Committer: Jelmer Vernooij
  • Date: 2009-05-27 08:33:37 UTC
  • mto: (4398.5.1 bencode_serializer)
  • mto: This revision was merged to the branch mainline in revision 4410.
  • Revision ID: jelmer@samba.org-20090527083337-fij2klthhtsdl2hy
Fix copyright headers, add _bencode_py.py to the list of files that do not have to have canonical copyright.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/_bencode_c.pyx
1
 
# Copyright (C) 2007, 2009, 2010 Canonical Ltd
 
1
# Copyright (C) 2007,2009 Canonical Ltd
2
2
#
3
3
# This program is free software; you can redistribute it and/or modify
4
4
# it under the terms of the GNU General Public License as published by
14
14
# along with this program; if not, write to the Free Software
15
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
16
16
 
 
17
 
17
18
"""Pyrex implementation for bencode coder/decoder"""
18
19
 
19
20
 
20
 
cdef extern from "stddef.h":
21
 
    ctypedef unsigned int size_t
22
 
 
23
21
cdef extern from "Python.h":
24
22
    ctypedef int  Py_ssize_t
25
23
    int PyInt_CheckExact(object o)
32
30
    object PyString_FromStringAndSize(char *v, Py_ssize_t len)
33
31
    char *PyString_AS_STRING(object o) except NULL
34
32
    Py_ssize_t PyString_GET_SIZE(object o) except -1
35
 
    object PyInt_FromString(char *str, char **pend, int base)
36
 
    int Py_GetRecursionLimit()
37
 
    int Py_EnterRecursiveCall(char *)
38
 
    void Py_LeaveRecursiveCall()
 
33
    long PyInt_GetMax()
 
34
    object PyLong_FromLong(unsigned long)
39
35
 
40
 
    int PyList_Append(object, object) except -1
 
36
cdef extern from "stddef.h":
 
37
    ctypedef unsigned int size_t
41
38
 
42
39
cdef extern from "stdlib.h":
43
40
    void free(void *memblock)
44
41
    void *malloc(size_t size)
45
42
    void *realloc(void *memblock, size_t size)
46
 
    long strtol(char *, char **, int)
 
43
    long int strtol(char *nptr, char **endptr, int base)
 
44
 
47
45
 
48
46
cdef extern from "string.h":
49
47
    void *memcpy(void *dest, void *src, size_t count)
 
48
    char *memchr(void *dest, int size, char c)
50
49
 
51
50
cdef extern from "python-compat.h":
52
51
    int snprintf(char* buffer, size_t nsize, char* fmt, ...)
53
52
 
54
 
cdef class Decoder
55
 
cdef class Encoder
56
 
 
57
 
cdef extern from "_bencode_pyx.h":
58
 
    void D_UPDATE_TAIL(Decoder, int n)
59
 
    void E_UPDATE_TAIL(Encoder, int n)
60
 
 
61
 
# To maintain compatibility with older versions of pyrex, we have to use the
62
 
# relative import here, rather than 'bzrlib._static_tuple_c'
63
 
from _static_tuple_c cimport StaticTuple, StaticTuple_CheckExact, \
64
 
    import_static_tuple_c
65
 
 
66
 
import_static_tuple_c()
67
 
 
68
53
 
69
54
cdef class Decoder:
70
55
    """Bencode decoder"""
71
56
 
72
57
    cdef readonly char *tail
73
 
    cdef readonly int size
74
 
    cdef readonly int _yield_tuples
75
 
    cdef object text
 
58
    cdef readonly int   size
 
59
 
 
60
    cdef readonly long   _MAXINT
 
61
    cdef readonly int    _MAXN
 
62
    cdef readonly object _longint
 
63
    cdef readonly int    _yield_tuples
76
64
 
77
65
    def __init__(self, s, yield_tuples=0):
78
66
        """Initialize decoder engine.
81
69
        if not PyString_CheckExact(s):
82
70
            raise TypeError("String required")
83
71
 
84
 
        self.text = s
85
72
        self.tail = PyString_AS_STRING(s)
86
73
        self.size = PyString_GET_SIZE(s)
87
74
        self._yield_tuples = int(yield_tuples)
88
75
 
 
76
        self._MAXINT = PyInt_GetMax()
 
77
        self._MAXN = len(str(self._MAXINT))
 
78
        self._longint = long(0)
 
79
 
89
80
    def decode(self):
90
 
        result = self._decode_object()
 
81
        result = self.decode_object()
91
82
        if self.size != 0:
92
83
            raise ValueError('junk in stream')
93
84
        return result
94
85
 
95
86
    def decode_object(self):
96
 
        return self._decode_object()
97
 
 
98
 
    cdef object _decode_object(self):
99
87
        cdef char ch
100
88
 
101
89
        if 0 == self.size:
102
90
            raise ValueError('stream underflow')
103
91
 
104
 
        if Py_EnterRecursiveCall("_decode_object"):
105
 
            raise RuntimeError("too deeply nested")
106
 
        try:
107
 
            ch = self.tail[0]
108
 
            if c'0' <= ch <= c'9':
109
 
                return self._decode_string()
110
 
            elif ch == c'l':
111
 
                D_UPDATE_TAIL(self, 1)
112
 
                return self._decode_list()
113
 
            elif ch == c'i':
114
 
                D_UPDATE_TAIL(self, 1)
115
 
                return self._decode_int()
116
 
            elif ch == c'd':
117
 
                D_UPDATE_TAIL(self, 1)
118
 
                return self._decode_dict()
119
 
            else:
120
 
                raise ValueError('unknown object type identifier %r' % ch)
121
 
        finally:
122
 
            Py_LeaveRecursiveCall()
123
 
 
124
 
    cdef int _read_digits(self, char stop_char) except -1:
125
 
        cdef int i
126
 
        i = 0
127
 
        while ((self.tail[i] >= c'0' and self.tail[i] <= c'9') or
128
 
               self.tail[i] == c'-') and i < self.size:
129
 
            i = i + 1
130
 
 
131
 
        if self.tail[i] != stop_char:
132
 
            raise ValueError("Stop character %c not found: %c" % 
133
 
                (stop_char, self.tail[i]))
134
 
        if (self.tail[0] == c'0' or 
135
 
                (self.tail[0] == c'-' and self.tail[1] == c'0')):
136
 
            if i == 1:
137
 
                return i
138
 
            else:
139
 
                raise ValueError # leading zeroes are not allowed
140
 
        return i
 
92
        ch = self.tail[0]
 
93
 
 
94
        if ch == c'i':
 
95
            self._update_tail(1)
 
96
            return self._decode_int()
 
97
        elif c'0' <= ch <= c'9':
 
98
            return self._decode_string()
 
99
        elif ch == c'l':
 
100
            self._update_tail(1)
 
101
            return self._decode_list()
 
102
        elif ch == c'd':
 
103
            self._update_tail(1)
 
104
            return self._decode_dict()
 
105
        else:
 
106
            raise ValueError('unknown object type identifier %r' % ch)
 
107
 
 
108
    cdef void _update_tail(self, int n):
 
109
        """Update tail pointer and resulting size by n characters"""
 
110
        self.size = self.size - n
 
111
        self.tail = &self.tail[n]
141
112
 
142
113
    cdef object _decode_int(self):
143
 
        cdef int i
144
 
        i = self._read_digits(c'e')
145
 
        self.tail[i] = 0
146
 
        try:
147
 
            ret = PyInt_FromString(self.tail, NULL, 10)
148
 
        finally:
149
 
            self.tail[i] = c'e'
150
 
        D_UPDATE_TAIL(self, i+1)
 
114
        cdef int result
 
115
        result = self._decode_int_until(c'e')
 
116
        if result != self._MAXINT:
 
117
            return result
 
118
        else:
 
119
            return self._longint
 
120
 
 
121
    cdef int _decode_int_until(self, char stop_char) except? -1:
 
122
        """Decode int from stream until stop_char encountered"""
 
123
        cdef char *actual_tail, *expected_tail
 
124
        cdef int n
 
125
        expected_tail = memchr(self.tail, self.size, stop_char)
 
126
        if expected_tail == NULL:
 
127
            raise ValueError
 
128
        ret = PyLong_FromLong(strtol(self.tail, &actual_tail, 10))
 
129
        if actual_tail != expected_tail or actual_tail == self.tail:
 
130
            raise ValueError
 
131
        self._update_tail(actual_tail - self.tail)
151
132
        return ret
152
133
 
153
134
    cdef object _decode_string(self):
154
135
        cdef int n
155
 
        cdef char *next_tail
156
 
        # strtol allows leading whitespace, negatives, and leading zeros
157
 
        # however, all callers have already checked that '0' <= tail[0] <= '9'
158
 
        # or they wouldn't have called _decode_string
159
 
        # strtol will stop at trailing whitespace, etc
160
 
        n = strtol(self.tail, &next_tail, 10)
161
 
        if next_tail == NULL or next_tail[0] != c':':
162
 
            raise ValueError('string len not terminated by ":"')
163
 
        # strtol allows leading zeros, so validate that we don't have that
164
 
        if (self.tail[0] == c'0'
165
 
            and (n != 0 or (next_tail - self.tail != 1))):
166
 
            raise ValueError('leading zeros are not allowed')
167
 
        D_UPDATE_TAIL(self, next_tail - self.tail + 1)
 
136
 
 
137
        n = self._decode_int_until(c':')
168
138
        if n == 0:
169
139
            return ''
 
140
        if n == self._MAXINT:
 
141
            # strings longer than 1GB is not supported
 
142
            raise ValueError('too long string')
170
143
        if n > self.size:
171
144
            raise ValueError('stream underflow')
172
145
        if n < 0:
173
146
            raise ValueError('string size below zero: %d' % n)
174
147
 
175
148
        result = PyString_FromStringAndSize(self.tail, n)
176
 
        D_UPDATE_TAIL(self, n)
 
149
        self._update_tail(n)
177
150
        return result
178
151
 
179
152
    cdef object _decode_list(self):
181
154
 
182
155
        while self.size > 0:
183
156
            if self.tail[0] == c'e':
184
 
                D_UPDATE_TAIL(self, 1)
 
157
                self._update_tail(1)
185
158
                if self._yield_tuples:
186
159
                    return tuple(result)
187
160
                else:
188
161
                    return result
189
162
            else:
190
 
                # As a quick shortcut, check to see if the next object is a
191
 
                # string, since we know that won't be creating recursion
192
 
                # if self.tail[0] >= c'0' and self.tail[0] <= c'9':
193
 
                PyList_Append(result, self._decode_object())
 
163
                result.append(self.decode_object())
194
164
 
195
165
        raise ValueError('malformed list')
196
166
 
203
173
        while self.size > 0:
204
174
            ch = self.tail[0]
205
175
            if ch == c'e':
206
 
                D_UPDATE_TAIL(self, 1)
 
176
                self._update_tail(1)
207
177
                return result
208
 
            else:
 
178
            elif c'0' <= ch <= c'9':
209
179
                # keys should be strings only
210
 
                if self.tail[0] < c'0' or self.tail[0] > c'9':
211
 
                    raise ValueError('key was not a simple string.')
212
180
                key = self._decode_string()
213
181
                if lastkey >= key:
214
182
                    raise ValueError('dict keys disordered')
215
183
                else:
216
184
                    lastkey = key
217
 
                value = self._decode_object()
 
185
                value = self.decode_object()
218
186
                result[key] = value
 
187
            else:
 
188
                raise ValueError('keys in dict should be strings only')
219
189
 
220
190
        raise ValueError('malformed dict')
221
191
 
239
209
 
240
210
cdef enum:
241
211
    INITSIZE = 1024     # initial size for encoder buffer
242
 
    INT_BUF_SIZE = 32
243
212
 
244
213
 
245
214
cdef class Encoder:
246
215
    """Bencode encoder"""
247
216
 
248
 
    cdef readonly char *tail
249
 
    cdef readonly int size
250
217
    cdef readonly char *buffer
251
 
    cdef readonly int maxsize
 
218
    cdef readonly int   maxsize
 
219
    cdef readonly char *tail
 
220
    cdef readonly int   size
252
221
 
253
222
    def __init__(self, int maxsize=INITSIZE):
254
223
        """Initialize encoder engine
268
237
        self.maxsize = maxsize
269
238
        self.tail = p
270
239
 
271
 
    def __dealloc__(self):
 
240
    def __del__(self):
272
241
        free(self.buffer)
273
242
        self.buffer = NULL
274
243
        self.maxsize = 0
302
271
        self.tail = &new_buffer[self.size]
303
272
        return 1
304
273
 
 
274
    cdef void _update_tail(self, int n):
 
275
        """Update tail pointer and resulting size by n characters"""
 
276
        self.size = self.size + n
 
277
        self.tail = &self.tail[n]
 
278
 
305
279
    cdef int _encode_int(self, int x) except 0:
306
280
        """Encode int to bencode string iNNNe
307
281
        @param  x:  value to encode
308
282
        """
309
283
        cdef int n
310
 
        self._ensure_buffer(INT_BUF_SIZE)
311
 
        n = snprintf(self.tail, INT_BUF_SIZE, "i%de", x)
 
284
        self._ensure_buffer(32)
 
285
        n = snprintf(self.tail, 32, "i%de", x)
312
286
        if n < 0:
313
287
            raise MemoryError('int %d too big to encode' % x)
314
 
        E_UPDATE_TAIL(self, n)
 
288
        self._update_tail(n)
315
289
        return 1
316
290
 
317
291
    cdef int _encode_long(self, x) except 0:
318
292
        return self._append_string(''.join(('i', str(x), 'e')))
319
293
 
320
294
    cdef int _append_string(self, s) except 0:
321
 
        cdef Py_ssize_t n
322
 
        n = PyString_GET_SIZE(s)
323
 
        self._ensure_buffer(n)
324
 
        memcpy(self.tail, PyString_AS_STRING(s), n)
325
 
        E_UPDATE_TAIL(self, n)
 
295
        self._ensure_buffer(PyString_GET_SIZE(s))
 
296
        memcpy(self.tail, PyString_AS_STRING(s), PyString_GET_SIZE(s))
 
297
        self._update_tail(PyString_GET_SIZE(s))
326
298
        return 1
327
299
 
328
300
    cdef int _encode_string(self, x) except 0:
329
301
        cdef int n
330
 
        cdef Py_ssize_t x_len
331
 
        x_len = PyString_GET_SIZE(x)
332
 
        self._ensure_buffer(x_len + INT_BUF_SIZE)
333
 
        n = snprintf(self.tail, INT_BUF_SIZE, '%d:', x_len)
 
302
        self._ensure_buffer(PyString_GET_SIZE(x) + 32)
 
303
        n = snprintf(self.tail, 32, '%d:', PyString_GET_SIZE(x))
334
304
        if n < 0:
335
305
            raise MemoryError('string %s too big to encode' % x)
336
 
        memcpy(<void *>(self.tail+n), PyString_AS_STRING(x), x_len)
337
 
        E_UPDATE_TAIL(self, n + x_len)
 
306
        memcpy(<void *>self.tail+n, PyString_AS_STRING(x), 
 
307
               PyString_GET_SIZE(x))
 
308
        self._update_tail(n+PyString_GET_SIZE(x))
338
309
        return 1
339
310
 
340
311
    cdef int _encode_list(self, x) except 0:
341
 
        self._ensure_buffer(1)
 
312
        self._ensure_buffer(2)
342
313
        self.tail[0] = c'l'
343
 
        E_UPDATE_TAIL(self, 1)
 
314
        self._update_tail(1)
344
315
 
345
316
        for i in x:
346
317
            self.process(i)
347
318
 
348
 
        self._ensure_buffer(1)
349
319
        self.tail[0] = c'e'
350
 
        E_UPDATE_TAIL(self, 1)
 
320
        self._update_tail(1)
351
321
        return 1
352
322
 
353
323
    cdef int _encode_dict(self, x) except 0:
354
 
        self._ensure_buffer(1)
 
324
        self._ensure_buffer(2)
355
325
        self.tail[0] = c'd'
356
 
        E_UPDATE_TAIL(self, 1)
 
326
        self._update_tail(1)
357
327
 
358
328
        keys = x.keys()
359
329
        keys.sort()
363
333
            self._encode_string(k)
364
334
            self.process(x[k])
365
335
 
366
 
        self._ensure_buffer(1)
367
336
        self.tail[0] = c'e'
368
 
        E_UPDATE_TAIL(self, 1)
 
337
        self._update_tail(1)
369
338
        return 1
370
339
 
371
340
    def process(self, object x):
372
 
        if Py_EnterRecursiveCall("encode"):
373
 
            raise RuntimeError("too deeply nested")
374
 
        try:
375
 
            if PyString_CheckExact(x):
376
 
                self._encode_string(x)
377
 
            elif PyInt_CheckExact(x):
378
 
                self._encode_int(x)
379
 
            elif PyLong_CheckExact(x):
380
 
                self._encode_long(x)
381
 
            elif (PyList_CheckExact(x) or PyTuple_CheckExact(x)
382
 
                  or StaticTuple_CheckExact(x)):
383
 
                self._encode_list(x)
384
 
            elif PyDict_CheckExact(x):
385
 
                self._encode_dict(x)
386
 
            elif PyBool_Check(x):
387
 
                self._encode_int(int(x))
388
 
            elif isinstance(x, Bencached):
389
 
                self._append_string(x.bencoded)
390
 
            else:
391
 
                raise TypeError('unsupported type %r' % x)
392
 
        finally:
393
 
            Py_LeaveRecursiveCall()
 
341
        if PyString_CheckExact(x):
 
342
            self._encode_string(x)
 
343
        elif PyInt_CheckExact(x):
 
344
            self._encode_int(x)
 
345
        elif PyLong_CheckExact(x):
 
346
            self._encode_long(x)
 
347
        elif PyList_CheckExact(x) or PyTuple_CheckExact(x):
 
348
            self._encode_list(x)
 
349
        elif PyDict_CheckExact(x):
 
350
            self._encode_dict(x)
 
351
        elif PyBool_Check(x):
 
352
            self._encode_int(int(x))
 
353
        elif isinstance(x, Bencached):
 
354
            self._append_string(x.bencoded)
 
355
        else:
 
356
            raise TypeError('unsupported type %r' % x)
394
357
 
395
358
 
396
359
def bencode(x):