← 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 int Py_ssize_t # Required for older pyrex versions
26
 
    int PyString_CheckExact(object)
27
 
    char * PyString_AS_STRING(object)
28
 
    Py_ssize_t PyString_GET_SIZE(object)
29
 
    object PyString_FromStringAndSize(char *, Py_ssize_t)
30
 
 
31
 
 
32
19
cdef extern from *:
33
20
    ctypedef unsigned long size_t
34
 
    void * malloc(size_t) nogil
35
 
    void * realloc(void *, size_t) nogil
36
 
    void free(void *) nogil
37
 
    void memcpy(void *, void *, size_t) nogil
38
 
 
 
21
    void * malloc(size_t)
 
22
    void * realloc(void *, size_t)
 
23
    void free(void *)
 
24
    void memcpy(void *, void *, size_t)
39
25
 
40
26
cdef extern from "delta.h":
41
27
    struct source_info:
44
30
        unsigned long agg_offset
45
31
    struct delta_index:
46
32
        pass
47
 
    delta_index * create_delta_index(source_info *src, delta_index *old) nogil
 
33
    delta_index * create_delta_index(source_info *src, delta_index *old)
48
34
    delta_index * create_delta_index_from_delta(source_info *delta,
49
 
                                                delta_index *old) nogil
50
 
    void free_delta_index(delta_index *index) nogil
 
35
                                                delta_index *old)
 
36
    void free_delta_index(delta_index *index)
51
37
    void *create_delta(delta_index *indexes,
52
38
             void *buf, unsigned long bufsize,
53
 
             unsigned long *delta_size, unsigned long max_delta_size) nogil
 
39
             unsigned long *delta_size, unsigned long max_delta_size)
54
40
    unsigned long get_delta_hdr_size(unsigned char **datap,
55
 
                                     unsigned char *top) nogil
 
41
                                     unsigned char *top)
56
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)
57
52
 
58
53
 
59
54
cdef void *safe_malloc(size_t count) except NULL:
115
110
            self._index = NULL
116
111
        safe_free(<void **>&self._source_infos)
117
112
 
118
 
    def _has_index(self):
119
 
        return (self._index != NULL)
120
 
 
121
113
    def add_delta_source(self, delta, unadded_bytes):
122
114
        """Add a new delta to the source texts.
123
115
 
145
137
        src.buf = c_delta
146
138
        src.size = c_delta_size
147
139
        src.agg_offset = self._source_offset + unadded_bytes
148
 
        with nogil:
149
 
            index = create_delta_index_from_delta(src, self._index)
 
140
        index = create_delta_index_from_delta(src, self._index)
150
141
        self._source_offset = src.agg_offset + src.size
151
142
        if index != NULL:
152
143
            free_delta_index(self._index)
172
163
        source_location = len(self._sources)
173
164
        if source_location >= self._max_num_sources:
174
165
            self._expand_sources()
175
 
        if source_location != 0 and self._index == NULL:
176
 
            # We were lazy about populating the index, create it now
177
 
            self._populate_first_index()
178
166
        self._sources.append(source)
179
167
        c_source = PyString_AS_STRING(source)
180
168
        c_source_size = PyString_GET_SIZE(source)
183
171
        src.size = c_source_size
184
172
 
185
173
        src.agg_offset = self._source_offset + unadded_bytes
 
174
        index = create_delta_index(src, self._index)
186
175
        self._source_offset = src.agg_offset + src.size
187
 
        # We delay creating the index on the first insert
188
 
        if source_location != 0:
189
 
            with nogil:
190
 
                index = create_delta_index(src, self._index)
191
 
            if index != NULL:
192
 
                free_delta_index(self._index)
193
 
                self._index = index
194
 
 
195
 
    cdef _populate_first_index(self):
196
 
        cdef delta_index *index
197
 
        if len(self._sources) != 1 or self._index != NULL:
198
 
            raise AssertionError('_populate_first_index should only be'
199
 
                ' called when we have a single source and no index yet')
200
 
 
201
 
        # We know that self._index is already NULL, so whatever
202
 
        # create_delta_index returns is fine
203
 
        with nogil:
204
 
            self._index = create_delta_index(&self._source_infos[0], NULL)
205
 
        assert self._index != NULL
 
176
        if index != NULL:
 
177
            free_delta_index(self._index)
 
178
            self._index = index
206
179
 
207
180
    cdef _expand_sources(self):
208
181
        raise RuntimeError('if we move self._source_infos, then we need to'
218
191
        cdef Py_ssize_t target_size
219
192
        cdef void * delta
220
193
        cdef unsigned long delta_size
221
 
        cdef unsigned long c_max_delta_size
222
194
 
223
195
        if self._index == NULL:
224
 
            if len(self._sources) == 0:
225
 
                return None
226
 
            # We were just lazy about generating the index
227
 
            self._populate_first_index()
 
196
            return None
228
197
 
229
198
        if not PyString_CheckExact(target_bytes):
230
199
            raise TypeError('target is not a str')
235
204
        # TODO: inline some of create_delta so we at least don't have to double
236
205
        #       malloc, and can instead use PyString_FromStringAndSize, to
237
206
        #       allocate the bytes into the final string
238
 
        c_max_delta_size = max_delta_size
239
 
        with nogil:
240
 
            delta = create_delta(self._index,
241
 
                                 target, target_size,
242
 
                                 &delta_size, c_max_delta_size)
 
207
        delta = create_delta(self._index,
 
208
                             target, target_size,
 
209
                             &delta_size, max_delta_size)
243
210
        result = None
244
211
        if delta:
245
212
            result = PyString_FromStringAndSize(<char *>delta, delta_size)
278
245
    return _apply_delta(source, source_size, delta, delta_size)
279
246
 
280
247
 
281
 
cdef unsigned char *_decode_copy_instruction(unsigned char *bytes,
282
 
    unsigned char cmd, unsigned int *offset,
283
 
    unsigned int *length) nogil: # cannot_raise
284
 
    """Decode a copy instruction from the next few bytes.
285
 
 
286
 
    A copy instruction is a variable number of bytes, so we will parse the
287
 
    bytes we care about, and return the new position, as well as the offset and
288
 
    length referred to in the bytes.
289
 
 
290
 
    :param bytes: Pointer to the start of bytes after cmd
291
 
    :param cmd: The command code
292
 
    :return: Pointer to the bytes just after the last decode byte
293
 
    """
294
 
    cdef unsigned int off, size, count
295
 
    off = 0
296
 
    size = 0
297
 
    count = 0
298
 
    if (cmd & 0x01):
299
 
        off = bytes[count]
300
 
        count = count + 1
301
 
    if (cmd & 0x02):
302
 
        off = off | (bytes[count] << 8)
303
 
        count = count + 1
304
 
    if (cmd & 0x04):
305
 
        off = off | (bytes[count] << 16)
306
 
        count = count + 1
307
 
    if (cmd & 0x08):
308
 
        off = off | (bytes[count] << 24)
309
 
        count = count + 1
310
 
    if (cmd & 0x10):
311
 
        size = bytes[count]
312
 
        count = count + 1
313
 
    if (cmd & 0x20):
314
 
        size = size | (bytes[count] << 8)
315
 
        count = count + 1
316
 
    if (cmd & 0x40):
317
 
        size = size | (bytes[count] << 16)
318
 
        count = count + 1
319
 
    if (size == 0):
320
 
        size = 0x10000
321
 
    offset[0] = off
322
 
    length[0] = size
323
 
    return bytes + count
324
 
 
325
 
 
326
248
cdef object _apply_delta(char *source, Py_ssize_t source_size,
327
249
                         char *delta, Py_ssize_t delta_size):
328
250
    """common functionality between apply_delta and apply_delta_to_source."""
329
251
    cdef unsigned char *data, *top
330
252
    cdef unsigned char *dst_buf, *out, cmd
331
253
    cdef Py_ssize_t size
332
 
    cdef unsigned int cp_off, cp_size
333
 
    cdef int failed
 
254
    cdef unsigned long cp_off, cp_size
334
255
 
335
256
    data = <unsigned char *>delta
336
257
    top = data + delta_size
339
260
    size = get_delta_hdr_size(&data, top)
340
261
    result = PyString_FromStringAndSize(NULL, size)
341
262
    dst_buf = <unsigned char*>PyString_AS_STRING(result)
342
 
 
343
 
    failed = 0
344
 
    with nogil:
345
 
        out = dst_buf
346
 
        while (data < top):
347
 
            cmd = data[0]
348
 
            data = data + 1
349
 
            if (cmd & 0x80):
350
 
                # Copy instruction
351
 
                data = _decode_copy_instruction(data, cmd, &cp_off, &cp_size)
352
 
                if (cp_off + cp_size < cp_size or
353
 
                    cp_off + cp_size > source_size or
354
 
                    cp_size > size):
355
 
                    failed = 1
356
 
                    break
357
 
                memcpy(out, source + cp_off, cp_size)
358
 
                out = out + cp_size
359
 
                size = size - cp_size
360
 
            else:
361
 
                # Insert instruction
362
 
                if cmd == 0:
363
 
                    # cmd == 0 is reserved for future encoding
364
 
                    # extensions. In the mean time we must fail when
365
 
                    # encountering them (might be data corruption).
366
 
                    failed = 2
367
 
                    break
368
 
                if cmd > size:
369
 
                    failed = 3
370
 
                    break
371
 
                memcpy(out, data, cmd)
372
 
                out = out + cmd
373
 
                data = data + cmd
374
 
                size = size - cmd
375
 
    if failed:
376
 
        if failed == 1:
377
 
            raise ValueError('Something wrong with:'
378
 
                ' cp_off = %s, cp_size = %s'
379
 
                ' source_size = %s, size = %s'
380
 
                % (cp_off, cp_size, source_size, size))
381
 
        elif failed == 2:
382
 
            raise ValueError('Got delta opcode: 0, not supported')
383
 
        elif failed == 3:
384
 
            raise ValueError('Insert instruction longer than remaining'
385
 
                ' bytes: %d > %d' % (cmd, size))
386
 
 
387
 
    # 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 */
388
324
    if (data != top or size != 0):
 
325
        ## /* XXX: error("delta replay has gone wild"); */
389
326
        raise RuntimeError('Did not extract the number of bytes we expected'
390
327
            ' we were left with %d bytes in "size", and top - data = %d'
391
328
            % (size, <int>(top - data)))
392
329
        return None
393
330
 
394
331
    # *dst_size = out - dst_buf;
395
 
    if (out - dst_buf) != PyString_GET_SIZE(result):
396
 
        raise RuntimeError('Number of bytes extracted did not match the'
397
 
            ' size encoded in the delta header.')
 
332
    assert (out - dst_buf) == PyString_GET_SIZE(result)
398
333
    return result
399
334
 
400
335
 
464
399
    # We take off 1, because we have to be able to decode the non-expanded byte
465
400
    num_low_bytes = PyString_GET_SIZE(bytes) - 1
466
401
    while (c_bytes[offset] & 0x80) and offset < num_low_bytes:
467
 
        val = val | ((c_bytes[offset] & 0x7F) << shift)
 
402
        val |= (c_bytes[offset] & 0x7F) << shift
468
403
        shift = shift + 7
469
404
        offset = offset + 1
470
405
    if c_bytes[offset] & 0x80:
471
406
        raise ValueError('Data not properly formatted, we ran out of'
472
407
                         ' bytes before 0x80 stopped being set.')
473
 
    val = val | (c_bytes[offset] << shift)
 
408
    val |= c_bytes[offset] << shift
474
409
    offset = offset + 1
475
410
    if val < 0:
476
411
        uval = <unsigned int> val