← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/_groupcompress_pyx.pyx

  • Committer: Canonical.com Patch Queue Manager
  • Date: 2010-09-01 08:02:42 UTC
  • mfrom: (5390.3.3 faster-revert-593560)
  • Revision ID: pqm@pqm.ubuntu.com-20100901080242-esg62ody4frwmy66
(spiv) Avoid repeatedly calling self.target.all_file_ids() in
 InterTree.iter_changes. (Andrew Bennetts)

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/_groupcompress_pyx.pyx
1
 
# Copyright (C) 2009 Canonical Ltd
 
1
# Copyright (C) 2008, 2009, 2010 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
16
16
 
17
17
"""Compiled extensions for doing compression."""
18
18
 
 
19
#python2.4 support
 
20
cdef extern from "python-compat.h":
 
21
    pass
 
22
 
 
23
 
 
24
cdef extern from "Python.h":
 
25
    ctypedef struct PyObject:
 
26
        pass
 
27
    ctypedef int Py_ssize_t # Required for older pyrex versions
 
28
    int PyString_CheckExact(object)
 
29
    char * PyString_AS_STRING(object)
 
30
    Py_ssize_t PyString_GET_SIZE(object)
 
31
    object PyString_FromStringAndSize(char *, Py_ssize_t)
 
32
 
 
33
 
19
34
cdef extern from *:
20
35
    ctypedef unsigned long size_t
21
 
    void * malloc(size_t)
22
 
    void * realloc(void *, size_t)
23
 
    void free(void *)
24
 
    void memcpy(void *, void *, size_t)
 
36
    void * malloc(size_t) nogil
 
37
    void * realloc(void *, size_t) nogil
 
38
    void free(void *) nogil
 
39
    void memcpy(void *, void *, size_t) nogil
 
40
 
25
41
 
26
42
cdef extern from "delta.h":
27
43
    struct source_info:
30
46
        unsigned long agg_offset
31
47
    struct delta_index:
32
48
        pass
33
 
    delta_index * create_delta_index(source_info *src, delta_index *old)
 
49
    delta_index * create_delta_index(source_info *src, delta_index *old) nogil
34
50
    delta_index * create_delta_index_from_delta(source_info *delta,
35
 
                                                delta_index *old)
36
 
    void free_delta_index(delta_index *index)
 
51
                                                delta_index *old) nogil
 
52
    void free_delta_index(delta_index *index) nogil
37
53
    void *create_delta(delta_index *indexes,
38
54
             void *buf, unsigned long bufsize,
39
 
             unsigned long *delta_size, unsigned long max_delta_size)
 
55
             unsigned long *delta_size, unsigned long max_delta_size) nogil
40
56
    unsigned long get_delta_hdr_size(unsigned char **datap,
41
 
                                     unsigned char *top)
 
57
                                     unsigned char *top) nogil
 
58
    unsigned long sizeof_delta_index(delta_index *index)
42
59
    Py_ssize_t DELTA_SIZE_MIN
43
 
    void *patch_delta(void *src_buf, unsigned long src_size,
44
 
                      void *delta_buf, unsigned long delta_size,
45
 
                      unsigned long *dst_size)
46
 
 
47
 
cdef extern from "Python.h":
48
 
    int PyString_CheckExact(object)
49
 
    char * PyString_AS_STRING(object)
50
 
    Py_ssize_t PyString_GET_SIZE(object)
51
 
    object PyString_FromStringAndSize(char *, Py_ssize_t)
52
60
 
53
61
 
54
62
cdef void *safe_malloc(size_t count) except NULL:
86
94
    cdef readonly object _sources
87
95
    cdef source_info *_source_infos
88
96
    cdef delta_index *_index
 
97
    cdef public unsigned long _source_offset
89
98
    cdef readonly unsigned int _max_num_sources
90
 
    cdef public unsigned long _source_offset
91
99
 
92
100
    def __init__(self, source=None):
93
101
        self._sources = []
100
108
        if source is not None:
101
109
            self.add_source(source, 0)
102
110
 
 
111
    def __sizeof__(self):
 
112
        # We want to track the _source_infos allocations, but the referenced
 
113
        # void* are actually tracked in _sources itself.
 
114
        # XXX: Cython is capable of doing sizeof(class) and returning the size
 
115
        #      of the underlying struct. Pyrex (<= 0.9.9) refuses, so we need
 
116
        #      to do it manually. *sigh* Note that we might get it wrong
 
117
        #      because of alignment issues.
 
118
        cdef Py_ssize_t size
 
119
        # PyObject start, vtable *, 3 object pointers, 2 C ints
 
120
        size = ((sizeof(PyObject) + sizeof(void*) + 3*sizeof(PyObject*)
 
121
                 + sizeof(unsigned long)
 
122
                 + sizeof(unsigned int))
 
123
                + (sizeof(source_info) * self._max_num_sources)
 
124
                + sizeof_delta_index(self._index))
 
125
        return size
 
126
 
103
127
    def __repr__(self):
104
128
        return '%s(%d, %d)' % (self.__class__.__name__,
105
129
            len(self._sources), self._source_offset)
110
134
            self._index = NULL
111
135
        safe_free(<void **>&self._source_infos)
112
136
 
 
137
    def _has_index(self):
 
138
        return (self._index != NULL)
 
139
 
113
140
    def add_delta_source(self, delta, unadded_bytes):
114
141
        """Add a new delta to the source texts.
115
142
 
137
164
        src.buf = c_delta
138
165
        src.size = c_delta_size
139
166
        src.agg_offset = self._source_offset + unadded_bytes
140
 
        index = create_delta_index_from_delta(src, self._index)
 
167
        with nogil:
 
168
            index = create_delta_index_from_delta(src, self._index)
141
169
        self._source_offset = src.agg_offset + src.size
142
170
        if index != NULL:
143
171
            free_delta_index(self._index)
163
191
        source_location = len(self._sources)
164
192
        if source_location >= self._max_num_sources:
165
193
            self._expand_sources()
 
194
        if source_location != 0 and self._index == NULL:
 
195
            # We were lazy about populating the index, create it now
 
196
            self._populate_first_index()
166
197
        self._sources.append(source)
167
198
        c_source = PyString_AS_STRING(source)
168
199
        c_source_size = PyString_GET_SIZE(source)
171
202
        src.size = c_source_size
172
203
 
173
204
        src.agg_offset = self._source_offset + unadded_bytes
174
 
        index = create_delta_index(src, self._index)
175
205
        self._source_offset = src.agg_offset + src.size
176
 
        if index != NULL:
177
 
            free_delta_index(self._index)
178
 
            self._index = index
 
206
        # We delay creating the index on the first insert
 
207
        if source_location != 0:
 
208
            with nogil:
 
209
                index = create_delta_index(src, self._index)
 
210
            if index != NULL:
 
211
                free_delta_index(self._index)
 
212
                self._index = index
 
213
 
 
214
    cdef _populate_first_index(self):
 
215
        cdef delta_index *index
 
216
        if len(self._sources) != 1 or self._index != NULL:
 
217
            raise AssertionError('_populate_first_index should only be'
 
218
                ' called when we have a single source and no index yet')
 
219
 
 
220
        # We know that self._index is already NULL, so whatever
 
221
        # create_delta_index returns is fine
 
222
        with nogil:
 
223
            self._index = create_delta_index(&self._source_infos[0], NULL)
 
224
        assert self._index != NULL
179
225
 
180
226
    cdef _expand_sources(self):
181
227
        raise RuntimeError('if we move self._source_infos, then we need to'
191
237
        cdef Py_ssize_t target_size
192
238
        cdef void * delta
193
239
        cdef unsigned long delta_size
 
240
        cdef unsigned long c_max_delta_size
194
241
 
195
242
        if self._index == NULL:
196
 
            return None
 
243
            if len(self._sources) == 0:
 
244
                return None
 
245
            # We were just lazy about generating the index
 
246
            self._populate_first_index()
197
247
 
198
248
        if not PyString_CheckExact(target_bytes):
199
249
            raise TypeError('target is not a str')
204
254
        # TODO: inline some of create_delta so we at least don't have to double
205
255
        #       malloc, and can instead use PyString_FromStringAndSize, to
206
256
        #       allocate the bytes into the final string
207
 
        delta = create_delta(self._index,
208
 
                             target, target_size,
209
 
                             &delta_size, max_delta_size)
 
257
        c_max_delta_size = max_delta_size
 
258
        with nogil:
 
259
            delta = create_delta(self._index,
 
260
                                 target, target_size,
 
261
                                 &delta_size, c_max_delta_size)
210
262
        result = None
211
263
        if delta:
212
264
            result = PyString_FromStringAndSize(<char *>delta, delta_size)
245
297
    return _apply_delta(source, source_size, delta, delta_size)
246
298
 
247
299
 
 
300
cdef unsigned char *_decode_copy_instruction(unsigned char *bytes,
 
301
    unsigned char cmd, unsigned int *offset,
 
302
    unsigned int *length) nogil: # cannot_raise
 
303
    """Decode a copy instruction from the next few bytes.
 
304
 
 
305
    A copy instruction is a variable number of bytes, so we will parse the
 
306
    bytes we care about, and return the new position, as well as the offset and
 
307
    length referred to in the bytes.
 
308
 
 
309
    :param bytes: Pointer to the start of bytes after cmd
 
310
    :param cmd: The command code
 
311
    :return: Pointer to the bytes just after the last decode byte
 
312
    """
 
313
    cdef unsigned int off, size, count
 
314
    off = 0
 
315
    size = 0
 
316
    count = 0
 
317
    if (cmd & 0x01):
 
318
        off = bytes[count]
 
319
        count = count + 1
 
320
    if (cmd & 0x02):
 
321
        off = off | (bytes[count] << 8)
 
322
        count = count + 1
 
323
    if (cmd & 0x04):
 
324
        off = off | (bytes[count] << 16)
 
325
        count = count + 1
 
326
    if (cmd & 0x08):
 
327
        off = off | (bytes[count] << 24)
 
328
        count = count + 1
 
329
    if (cmd & 0x10):
 
330
        size = bytes[count]
 
331
        count = count + 1
 
332
    if (cmd & 0x20):
 
333
        size = size | (bytes[count] << 8)
 
334
        count = count + 1
 
335
    if (cmd & 0x40):
 
336
        size = size | (bytes[count] << 16)
 
337
        count = count + 1
 
338
    if (size == 0):
 
339
        size = 0x10000
 
340
    offset[0] = off
 
341
    length[0] = size
 
342
    return bytes + count
 
343
 
 
344
 
248
345
cdef object _apply_delta(char *source, Py_ssize_t source_size,
249
346
                         char *delta, Py_ssize_t delta_size):
250
347
    """common functionality between apply_delta and apply_delta_to_source."""
251
348
    cdef unsigned char *data, *top
252
349
    cdef unsigned char *dst_buf, *out, cmd
253
350
    cdef Py_ssize_t size
254
 
    cdef unsigned long cp_off, cp_size
 
351
    cdef unsigned int cp_off, cp_size
 
352
    cdef int failed
255
353
 
256
354
    data = <unsigned char *>delta
257
355
    top = data + delta_size
260
358
    size = get_delta_hdr_size(&data, top)
261
359
    result = PyString_FromStringAndSize(NULL, size)
262
360
    dst_buf = <unsigned char*>PyString_AS_STRING(result)
263
 
    # XXX: The original code added a trailing null here, but this shouldn't be
264
 
    #      necessary when using PyString_FromStringAndSize
265
 
    # dst_buf[size] = 0
266
 
 
267
 
    out = dst_buf
268
 
    while (data < top):
269
 
        cmd = data[0]
270
 
        data = data + 1
271
 
        if (cmd & 0x80):
272
 
            cp_off = cp_size = 0
273
 
            if (cmd & 0x01):
274
 
                cp_off = data[0]
275
 
                data = data + 1
276
 
            if (cmd & 0x02):
277
 
                cp_off = cp_off | (data[0] << 8)
278
 
                data = data + 1
279
 
            if (cmd & 0x04):
280
 
                cp_off = cp_off | (data[0] << 16)
281
 
                data = data + 1
282
 
            if (cmd & 0x08):
283
 
                cp_off = cp_off | (data[0] << 24)
284
 
                data = data + 1
285
 
            if (cmd & 0x10):
286
 
                cp_size = data[0]
287
 
                data = data + 1
288
 
            if (cmd & 0x20):
289
 
                cp_size = cp_size | (data[0] << 8)
290
 
                data = data + 1
291
 
            if (cmd & 0x40):
292
 
                cp_size = cp_size | (data[0] << 16)
293
 
                data = data + 1
294
 
            if (cp_size == 0):
295
 
                cp_size = 0x10000
296
 
            if (cp_off + cp_size < cp_size or
297
 
                cp_off + cp_size > source_size or
298
 
                cp_size > size):
299
 
                raise RuntimeError('Something wrong with:'
300
 
                    ' cp_off = %s, cp_size = %s'
301
 
                    ' source_size = %s, size = %s'
302
 
                    % (cp_off, cp_size, source_size, size))
303
 
            memcpy(out, source + cp_off, cp_size)
304
 
            out = out + cp_size
305
 
            size = size - cp_size
306
 
        elif (cmd):
307
 
            if (cmd > size):
308
 
                raise RuntimeError('Insert instruction longer than remaining'
309
 
                    ' bytes: %d > %d' % (cmd, size))
310
 
            memcpy(out, data, cmd)
311
 
            out = out + cmd
312
 
            data = data + cmd
313
 
            size = size - cmd
314
 
        else:
315
 
            # /*
316
 
            #  * cmd == 0 is reserved for future encoding
317
 
            #  * extensions. In the mean time we must fail when
318
 
            #  * encountering them (might be data corruption).
319
 
            #  */
320
 
            ## /* XXX: error("unexpected delta opcode 0"); */
321
 
            raise RuntimeError('Got delta opcode: 0, not supported')
322
 
 
323
 
    # /* sanity check */
 
361
 
 
362
    failed = 0
 
363
    with nogil:
 
364
        out = dst_buf
 
365
        while (data < top):
 
366
            cmd = data[0]
 
367
            data = data + 1
 
368
            if (cmd & 0x80):
 
369
                # Copy instruction
 
370
                data = _decode_copy_instruction(data, cmd, &cp_off, &cp_size)
 
371
                if (cp_off + cp_size < cp_size or
 
372
                    cp_off + cp_size > source_size or
 
373
                    cp_size > size):
 
374
                    failed = 1
 
375
                    break
 
376
                memcpy(out, source + cp_off, cp_size)
 
377
                out = out + cp_size
 
378
                size = size - cp_size
 
379
            else:
 
380
                # Insert instruction
 
381
                if cmd == 0:
 
382
                    # cmd == 0 is reserved for future encoding
 
383
                    # extensions. In the mean time we must fail when
 
384
                    # encountering them (might be data corruption).
 
385
                    failed = 2
 
386
                    break
 
387
                if cmd > size:
 
388
                    failed = 3
 
389
                    break
 
390
                memcpy(out, data, cmd)
 
391
                out = out + cmd
 
392
                data = data + cmd
 
393
                size = size - cmd
 
394
    if failed:
 
395
        if failed == 1:
 
396
            raise ValueError('Something wrong with:'
 
397
                ' cp_off = %s, cp_size = %s'
 
398
                ' source_size = %s, size = %s'
 
399
                % (cp_off, cp_size, source_size, size))
 
400
        elif failed == 2:
 
401
            raise ValueError('Got delta opcode: 0, not supported')
 
402
        elif failed == 3:
 
403
            raise ValueError('Insert instruction longer than remaining'
 
404
                ' bytes: %d > %d' % (cmd, size))
 
405
 
 
406
    # sanity check
324
407
    if (data != top or size != 0):
325
 
        ## /* XXX: error("delta replay has gone wild"); */
326
408
        raise RuntimeError('Did not extract the number of bytes we expected'
327
409
            ' we were left with %d bytes in "size", and top - data = %d'
328
410
            % (size, <int>(top - data)))
329
411
        return None
330
412
 
331
413
    # *dst_size = out - dst_buf;
332
 
    assert (out - dst_buf) == PyString_GET_SIZE(result)
 
414
    if (out - dst_buf) != PyString_GET_SIZE(result):
 
415
        raise RuntimeError('Number of bytes extracted did not match the'
 
416
            ' size encoded in the delta header.')
333
417
    return result
334
418
 
335
419
 
399
483
    # We take off 1, because we have to be able to decode the non-expanded byte
400
484
    num_low_bytes = PyString_GET_SIZE(bytes) - 1
401
485
    while (c_bytes[offset] & 0x80) and offset < num_low_bytes:
402
 
        val |= (c_bytes[offset] & 0x7F) << shift
 
486
        val = val | ((c_bytes[offset] & 0x7F) << shift)
403
487
        shift = shift + 7
404
488
        offset = offset + 1
405
489
    if c_bytes[offset] & 0x80:
406
490
        raise ValueError('Data not properly formatted, we ran out of'
407
491
                         ' bytes before 0x80 stopped being set.')
408
 
    val |= c_bytes[offset] << shift
 
492
    val = val | (c_bytes[offset] << shift)
409
493
    offset = offset + 1
410
494
    if val < 0:
411
495
        uval = <unsigned int> val