← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/_groupcompress_pyx.pyx

  • Committer: John Arbash Meinel
  • Date: 2009-03-27 22:29:55 UTC
  • mto: (3735.39.2 clean)
  • mto: This revision was merged to the branch mainline in revision 4280.
  • Revision ID: john@arbash-meinel.com-20090327222955-utifmfm888zerixt
Implement apply_delta_to_source which doesn't have to malloc another string.

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/_groupcompress_pyx.pyx
1
 
# Copyright (C) 2008, 2009, 2010 Canonical Ltd
 
1
# Copyright (C) 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
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
 
 
34
19
cdef extern from *:
35
20
    ctypedef unsigned long 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
 
 
 
21
    void * malloc(size_t)
 
22
    void * realloc(void *, size_t)
 
23
    void free(void *)
 
24
    void memcpy(void *, void *, size_t)
41
25
 
42
26
cdef extern from "delta.h":
43
27
    struct source_info:
46
30
        unsigned long agg_offset
47
31
    struct delta_index:
48
32
        pass
49
 
    delta_index * create_delta_index(source_info *src, delta_index *old) nogil
 
33
    delta_index * create_delta_index(source_info *src, delta_index *old)
50
34
    delta_index * create_delta_index_from_delta(source_info *delta,
51
 
                                                delta_index *old) nogil
52
 
    void free_delta_index(delta_index *index) nogil
 
35
                                                delta_index *old)
 
36
    void free_delta_index(delta_index *index)
53
37
    void *create_delta(delta_index *indexes,
54
38
             void *buf, unsigned long bufsize,
55
 
             unsigned long *delta_size, unsigned long max_delta_size) nogil
 
39
             unsigned long *delta_size, unsigned long max_delta_size)
56
40
    unsigned long get_delta_hdr_size(unsigned char **datap,
57
 
                                     unsigned char *top) nogil
58
 
    unsigned long sizeof_delta_index(delta_index *index)
 
41
                                     unsigned char *top)
59
42
    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)
60
52
 
61
53
 
62
54
cdef void *safe_malloc(size_t count) except NULL:
94
86
    cdef readonly object _sources
95
87
    cdef source_info *_source_infos
96
88
    cdef delta_index *_index
 
89
    cdef readonly unsigned int _max_num_sources
97
90
    cdef public unsigned long _source_offset
98
 
    cdef readonly unsigned int _max_num_sources
99
91
 
100
92
    def __init__(self, source=None):
101
93
        self._sources = []
108
100
        if source is not None:
109
101
            self.add_source(source, 0)
110
102
 
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
 
 
127
103
    def __repr__(self):
128
104
        return '%s(%d, %d)' % (self.__class__.__name__,
129
105
            len(self._sources), self._source_offset)
134
110
            self._index = NULL
135
111
        safe_free(<void **>&self._source_infos)
136
112
 
137
 
    def _has_index(self):
138
 
        return (self._index != NULL)
139
 
 
140
113
    def add_delta_source(self, delta, unadded_bytes):
141
114
        """Add a new delta to the source texts.
142
115
 
164
137
        src.buf = c_delta
165
138
        src.size = c_delta_size
166
139
        src.agg_offset = self._source_offset + unadded_bytes
167
 
        with nogil:
168
 
            index = create_delta_index_from_delta(src, self._index)
 
140
        index = create_delta_index_from_delta(src, self._index)
169
141
        self._source_offset = src.agg_offset + src.size
170
142
        if index != NULL:
171
143
            free_delta_index(self._index)
191
163
        source_location = len(self._sources)
192
164
        if source_location >= self._max_num_sources:
193
165
            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()
197
166
        self._sources.append(source)
198
167
        c_source = PyString_AS_STRING(source)
199
168
        c_source_size = PyString_GET_SIZE(source)
202
171
        src.size = c_source_size
203
172
 
204
173
        src.agg_offset = self._source_offset + unadded_bytes
 
174
        index = create_delta_index(src, self._index)
205
175
        self._source_offset = src.agg_offset + src.size
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
 
176
        if index != NULL:
 
177
            free_delta_index(self._index)
 
178
            self._index = index
225
179
 
226
180
    cdef _expand_sources(self):
227
181
        raise RuntimeError('if we move self._source_infos, then we need to'
237
191
        cdef Py_ssize_t target_size
238
192
        cdef void * delta
239
193
        cdef unsigned long delta_size
240
 
        cdef unsigned long c_max_delta_size
241
194
 
242
195
        if self._index == NULL:
243
 
            if len(self._sources) == 0:
244
 
                return None
245
 
            # We were just lazy about generating the index
246
 
            self._populate_first_index()
 
196
            return None
247
197
 
248
198
        if not PyString_CheckExact(target_bytes):
249
199
            raise TypeError('target is not a str')
254
204
        # TODO: inline some of create_delta so we at least don't have to double
255
205
        #       malloc, and can instead use PyString_FromStringAndSize, to
256
206
        #       allocate the bytes into the final string
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)
 
207
        delta = create_delta(self._index,
 
208
                             target, target_size,
 
209
                             &delta_size, max_delta_size)
262
210
        result = None
263
211
        if delta:
264
212
            result = PyString_FromStringAndSize(<char *>delta, delta_size)
297
245
    return _apply_delta(source, source_size, delta, delta_size)
298
246
 
299
247
 
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
 
 
345
248
cdef object _apply_delta(char *source, Py_ssize_t source_size,
346
249
                         char *delta, Py_ssize_t delta_size):
347
250
    """common functionality between apply_delta and apply_delta_to_source."""
348
251
    cdef unsigned char *data, *top
349
252
    cdef unsigned char *dst_buf, *out, cmd
350
253
    cdef Py_ssize_t size
351
 
    cdef unsigned int cp_off, cp_size
352
 
    cdef int failed
 
254
    cdef unsigned long cp_off, cp_size
353
255
 
354
256
    data = <unsigned char *>delta
355
257
    top = data + delta_size
358
260
    size = get_delta_hdr_size(&data, top)
359
261
    result = PyString_FromStringAndSize(NULL, size)
360
262
    dst_buf = <unsigned char*>PyString_AS_STRING(result)
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
 
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 */
407
324
    if (data != top or size != 0):
 
325
        ## /* XXX: error("delta replay has gone wild"); */
408
326
        raise RuntimeError('Did not extract the number of bytes we expected'
409
327
            ' we were left with %d bytes in "size", and top - data = %d'
410
328
            % (size, <int>(top - data)))
411
329
        return None
412
330
 
413
331
    # *dst_size = out - dst_buf;
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.')
 
332
    assert (out - dst_buf) == PyString_GET_SIZE(result)
417
333
    return result
418
334
 
419
335
 
483
399
    # We take off 1, because we have to be able to decode the non-expanded byte
484
400
    num_low_bytes = PyString_GET_SIZE(bytes) - 1
485
401
    while (c_bytes[offset] & 0x80) and offset < num_low_bytes:
486
 
        val = val | ((c_bytes[offset] & 0x7F) << shift)
 
402
        val |= (c_bytes[offset] & 0x7F) << shift
487
403
        shift = shift + 7
488
404
        offset = offset + 1
489
405
    if c_bytes[offset] & 0x80:
490
406
        raise ValueError('Data not properly formatted, we ran out of'
491
407
                         ' bytes before 0x80 stopped being set.')
492
 
    val = val | (c_bytes[offset] << shift)
 
408
    val |= c_bytes[offset] << shift
493
409
    offset = offset + 1
494
410
    if val < 0:
495
411
        uval = <unsigned int> val