← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/_groupcompress_pyx.pyx

  • Committer: Martin
  • Date: 2010-05-16 15:18:43 UTC
  • mfrom: (5235 +trunk)
  • mto: This revision was merged to the branch mainline in revision 5239.
  • Revision ID: gzlist@googlemail.com-20100516151843-lu53u7caehm3ie3i
Merge bzr.dev to resolve conflicts in NEWS and _chk_map_pyx

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 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
 
19
32
cdef extern from *:
20
33
    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)
 
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
 
25
39
 
26
40
cdef extern from "delta.h":
27
41
    struct source_info:
30
44
        unsigned long agg_offset
31
45
    struct delta_index:
32
46
        pass
33
 
    delta_index * create_delta_index(source_info *src, delta_index *old)
 
47
    delta_index * create_delta_index(source_info *src, delta_index *old) nogil
34
48
    delta_index * create_delta_index_from_delta(source_info *delta,
35
 
                                                delta_index *old)
36
 
    void free_delta_index(delta_index *index)
 
49
                                                delta_index *old) nogil
 
50
    void free_delta_index(delta_index *index) nogil
37
51
    void *create_delta(delta_index *indexes,
38
52
             void *buf, unsigned long bufsize,
39
 
             unsigned long *delta_size, unsigned long max_delta_size)
 
53
             unsigned long *delta_size, unsigned long max_delta_size) nogil
40
54
    unsigned long get_delta_hdr_size(unsigned char **datap,
41
 
                                     unsigned char *top)
 
55
                                     unsigned char *top) nogil
42
56
    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
57
 
53
58
 
54
59
cdef void *safe_malloc(size_t count) except NULL:
110
115
            self._index = NULL
111
116
        safe_free(<void **>&self._source_infos)
112
117
 
 
118
    def _has_index(self):
 
119
        return (self._index != NULL)
 
120
 
113
121
    def add_delta_source(self, delta, unadded_bytes):
114
122
        """Add a new delta to the source texts.
115
123
 
137
145
        src.buf = c_delta
138
146
        src.size = c_delta_size
139
147
        src.agg_offset = self._source_offset + unadded_bytes
140
 
        index = create_delta_index_from_delta(src, self._index)
 
148
        with nogil:
 
149
            index = create_delta_index_from_delta(src, self._index)
141
150
        self._source_offset = src.agg_offset + src.size
142
151
        if index != NULL:
143
152
            free_delta_index(self._index)
163
172
        source_location = len(self._sources)
164
173
        if source_location >= self._max_num_sources:
165
174
            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()
166
178
        self._sources.append(source)
167
179
        c_source = PyString_AS_STRING(source)
168
180
        c_source_size = PyString_GET_SIZE(source)
171
183
        src.size = c_source_size
172
184
 
173
185
        src.agg_offset = self._source_offset + unadded_bytes
174
 
        index = create_delta_index(src, self._index)
175
186
        self._source_offset = src.agg_offset + src.size
176
 
        if index != NULL:
177
 
            free_delta_index(self._index)
178
 
            self._index = index
 
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
179
206
 
180
207
    cdef _expand_sources(self):
181
208
        raise RuntimeError('if we move self._source_infos, then we need to'
191
218
        cdef Py_ssize_t target_size
192
219
        cdef void * delta
193
220
        cdef unsigned long delta_size
 
221
        cdef unsigned long c_max_delta_size
194
222
 
195
223
        if self._index == NULL:
196
 
            return None
 
224
            if len(self._sources) == 0:
 
225
                return None
 
226
            # We were just lazy about generating the index
 
227
            self._populate_first_index()
197
228
 
198
229
        if not PyString_CheckExact(target_bytes):
199
230
            raise TypeError('target is not a str')
204
235
        # TODO: inline some of create_delta so we at least don't have to double
205
236
        #       malloc, and can instead use PyString_FromStringAndSize, to
206
237
        #       allocate the bytes into the final string
207
 
        delta = create_delta(self._index,
208
 
                             target, target_size,
209
 
                             &delta_size, max_delta_size)
 
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)
210
243
        result = None
211
244
        if delta:
212
245
            result = PyString_FromStringAndSize(<char *>delta, delta_size)
245
278
    return _apply_delta(source, source_size, delta, delta_size)
246
279
 
247
280
 
 
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
 
248
326
cdef object _apply_delta(char *source, Py_ssize_t source_size,
249
327
                         char *delta, Py_ssize_t delta_size):
250
328
    """common functionality between apply_delta and apply_delta_to_source."""
251
329
    cdef unsigned char *data, *top
252
330
    cdef unsigned char *dst_buf, *out, cmd
253
331
    cdef Py_ssize_t size
254
 
    cdef unsigned long cp_off, cp_size
 
332
    cdef unsigned int cp_off, cp_size
 
333
    cdef int failed
255
334
 
256
335
    data = <unsigned char *>delta
257
336
    top = data + delta_size
260
339
    size = get_delta_hdr_size(&data, top)
261
340
    result = PyString_FromStringAndSize(NULL, size)
262
341
    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 */
 
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
324
388
    if (data != top or size != 0):
325
 
        ## /* XXX: error("delta replay has gone wild"); */
326
389
        raise RuntimeError('Did not extract the number of bytes we expected'
327
390
            ' we were left with %d bytes in "size", and top - data = %d'
328
391
            % (size, <int>(top - data)))
329
392
        return None
330
393
 
331
394
    # *dst_size = out - dst_buf;
332
 
    assert (out - dst_buf) == PyString_GET_SIZE(result)
 
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.')
333
398
    return result
334
399
 
335
400
 
399
464
    # We take off 1, because we have to be able to decode the non-expanded byte
400
465
    num_low_bytes = PyString_GET_SIZE(bytes) - 1
401
466
    while (c_bytes[offset] & 0x80) and offset < num_low_bytes:
402
 
        val |= (c_bytes[offset] & 0x7F) << shift
 
467
        val = val | ((c_bytes[offset] & 0x7F) << shift)
403
468
        shift = shift + 7
404
469
        offset = offset + 1
405
470
    if c_bytes[offset] & 0x80:
406
471
        raise ValueError('Data not properly formatted, we ran out of'
407
472
                         ' bytes before 0x80 stopped being set.')
408
 
    val |= c_bytes[offset] << shift
 
473
    val = val | (c_bytes[offset] << shift)
409
474
    offset = offset + 1
410
475
    if val < 0:
411
476
        uval = <unsigned int> val