~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-02-01 13:53:24 UTC
  • mfrom: (4990.1.2 rm-obsolete)
  • Revision ID: pqm@pqm.ubuntu.com-20100201135324-cuhuolr97guf5xjp
(Jelmer) Remove obsolete (and broken) biobench and history2revfiles
        tools.

Show diffs side-by-side

added added

removed removed

Lines of Context:
 
1
# Copyright (C) 2009 Canonical Ltd
 
2
#
 
3
# This program is free software; you can redistribute it and/or modify
 
4
# it under the terms of the GNU General Public License as published by
 
5
# the Free Software Foundation; either version 2 of the License, or
 
6
# (at your option) any later version.
 
7
#
 
8
# This program is distributed in the hope that it will be useful,
 
9
# but WITHOUT ANY WARRANTY; without even the implied warranty of
 
10
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 
11
# GNU General Public License for more details.
 
12
#
 
13
# You should have received a copy of the GNU General Public License
 
14
# along with this program; if not, write to the Free Software
 
15
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
 
16
 
 
17
"""Compiled extensions for doing compression."""
 
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
cdef extern from *:
 
33
    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
 
 
39
 
 
40
cdef extern from "delta.h":
 
41
    struct source_info:
 
42
        void *buf
 
43
        unsigned long size
 
44
        unsigned long agg_offset
 
45
    struct delta_index:
 
46
        pass
 
47
    delta_index * create_delta_index(source_info *src, delta_index *old) nogil
 
48
    delta_index * create_delta_index_from_delta(source_info *delta,
 
49
                                                delta_index *old) nogil
 
50
    void free_delta_index(delta_index *index) nogil
 
51
    void *create_delta(delta_index *indexes,
 
52
             void *buf, unsigned long bufsize,
 
53
             unsigned long *delta_size, unsigned long max_delta_size) nogil
 
54
    unsigned long get_delta_hdr_size(unsigned char **datap,
 
55
                                     unsigned char *top) nogil
 
56
    Py_ssize_t DELTA_SIZE_MIN
 
57
 
 
58
 
 
59
cdef void *safe_malloc(size_t count) except NULL:
 
60
    cdef void *result
 
61
    result = malloc(count)
 
62
    if result == NULL:
 
63
        raise MemoryError('Failed to allocate %d bytes of memory' % (count,))
 
64
    return result
 
65
 
 
66
 
 
67
cdef void *safe_realloc(void * old, size_t count) except NULL:
 
68
    cdef void *result
 
69
    result = realloc(old, count)
 
70
    if result == NULL:
 
71
        raise MemoryError('Failed to reallocate to %d bytes of memory'
 
72
                          % (count,))
 
73
    return result
 
74
 
 
75
 
 
76
cdef int safe_free(void **val) except -1:
 
77
    assert val != NULL
 
78
    if val[0] != NULL:
 
79
        free(val[0])
 
80
        val[0] = NULL
 
81
 
 
82
def make_delta_index(source):
 
83
    return DeltaIndex(source)
 
84
 
 
85
 
 
86
cdef class DeltaIndex:
 
87
 
 
88
    # We need Pyrex 0.9.8+ to understand a 'list' definition, and this object
 
89
    # isn't performance critical
 
90
    # cdef readonly list _sources
 
91
    cdef readonly object _sources
 
92
    cdef source_info *_source_infos
 
93
    cdef delta_index *_index
 
94
    cdef readonly unsigned int _max_num_sources
 
95
    cdef public unsigned long _source_offset
 
96
 
 
97
    def __init__(self, source=None):
 
98
        self._sources = []
 
99
        self._index = NULL
 
100
        self._max_num_sources = 65000
 
101
        self._source_infos = <source_info *>safe_malloc(sizeof(source_info)
 
102
                                                        * self._max_num_sources)
 
103
        self._source_offset = 0
 
104
 
 
105
        if source is not None:
 
106
            self.add_source(source, 0)
 
107
 
 
108
    def __repr__(self):
 
109
        return '%s(%d, %d)' % (self.__class__.__name__,
 
110
            len(self._sources), self._source_offset)
 
111
 
 
112
    def __dealloc__(self):
 
113
        if self._index != NULL:
 
114
            free_delta_index(self._index)
 
115
            self._index = NULL
 
116
        safe_free(<void **>&self._source_infos)
 
117
 
 
118
    def _has_index(self):
 
119
        return (self._index != NULL)
 
120
 
 
121
    def add_delta_source(self, delta, unadded_bytes):
 
122
        """Add a new delta to the source texts.
 
123
 
 
124
        :param delta: The text of the delta, this must be a byte string.
 
125
        :param unadded_bytes: Number of bytes that were added to the source
 
126
            that were not indexed.
 
127
        """
 
128
        cdef char *c_delta
 
129
        cdef Py_ssize_t c_delta_size
 
130
        cdef delta_index *index
 
131
        cdef unsigned int source_location
 
132
        cdef source_info *src
 
133
        cdef unsigned int num_indexes
 
134
 
 
135
        if not PyString_CheckExact(delta):
 
136
            raise TypeError('delta is not a str')
 
137
 
 
138
        source_location = len(self._sources)
 
139
        if source_location >= self._max_num_sources:
 
140
            self._expand_sources()
 
141
        self._sources.append(delta)
 
142
        c_delta = PyString_AS_STRING(delta)
 
143
        c_delta_size = PyString_GET_SIZE(delta)
 
144
        src = self._source_infos + source_location
 
145
        src.buf = c_delta
 
146
        src.size = c_delta_size
 
147
        src.agg_offset = self._source_offset + unadded_bytes
 
148
        with nogil:
 
149
            index = create_delta_index_from_delta(src, self._index)
 
150
        self._source_offset = src.agg_offset + src.size
 
151
        if index != NULL:
 
152
            free_delta_index(self._index)
 
153
            self._index = index
 
154
 
 
155
    def add_source(self, source, unadded_bytes):
 
156
        """Add a new bit of source text to the delta indexes.
 
157
 
 
158
        :param source: The text in question, this must be a byte string
 
159
        :param unadded_bytes: Assume there are this many bytes that didn't get
 
160
            added between this source and the end of the previous source.
 
161
        """
 
162
        cdef char *c_source
 
163
        cdef Py_ssize_t c_source_size
 
164
        cdef delta_index *index
 
165
        cdef unsigned int source_location
 
166
        cdef source_info *src
 
167
        cdef unsigned int num_indexes
 
168
 
 
169
        if not PyString_CheckExact(source):
 
170
            raise TypeError('source is not a str')
 
171
 
 
172
        source_location = len(self._sources)
 
173
        if source_location >= self._max_num_sources:
 
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()
 
178
        self._sources.append(source)
 
179
        c_source = PyString_AS_STRING(source)
 
180
        c_source_size = PyString_GET_SIZE(source)
 
181
        src = self._source_infos + source_location
 
182
        src.buf = c_source
 
183
        src.size = c_source_size
 
184
 
 
185
        src.agg_offset = self._source_offset + unadded_bytes
 
186
        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
 
206
 
 
207
    cdef _expand_sources(self):
 
208
        raise RuntimeError('if we move self._source_infos, then we need to'
 
209
                           ' change all of the index pointers as well.')
 
210
        self._max_num_sources = self._max_num_sources * 2
 
211
        self._source_infos = <source_info *>safe_realloc(self._source_infos,
 
212
                                                sizeof(source_info)
 
213
                                                * self._max_num_sources)
 
214
 
 
215
    def make_delta(self, target_bytes, max_delta_size=0):
 
216
        """Create a delta from the current source to the target bytes."""
 
217
        cdef char *target
 
218
        cdef Py_ssize_t target_size
 
219
        cdef void * delta
 
220
        cdef unsigned long delta_size
 
221
        cdef unsigned long c_max_delta_size
 
222
 
 
223
        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()
 
228
 
 
229
        if not PyString_CheckExact(target_bytes):
 
230
            raise TypeError('target is not a str')
 
231
 
 
232
        target = PyString_AS_STRING(target_bytes)
 
233
        target_size = PyString_GET_SIZE(target_bytes)
 
234
 
 
235
        # TODO: inline some of create_delta so we at least don't have to double
 
236
        #       malloc, and can instead use PyString_FromStringAndSize, to
 
237
        #       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)
 
243
        result = None
 
244
        if delta:
 
245
            result = PyString_FromStringAndSize(<char *>delta, delta_size)
 
246
            free(delta)
 
247
        return result
 
248
 
 
249
 
 
250
def make_delta(source_bytes, target_bytes):
 
251
    """Create a delta, this is a wrapper around DeltaIndex.make_delta."""
 
252
    di = DeltaIndex(source_bytes)
 
253
    return di.make_delta(target_bytes)
 
254
 
 
255
 
 
256
def apply_delta(source_bytes, delta_bytes):
 
257
    """Apply a delta generated by make_delta to source_bytes."""
 
258
    cdef char *source
 
259
    cdef Py_ssize_t source_size
 
260
    cdef char *delta
 
261
    cdef Py_ssize_t delta_size
 
262
 
 
263
    if not PyString_CheckExact(source_bytes):
 
264
        raise TypeError('source is not a str')
 
265
    if not PyString_CheckExact(delta_bytes):
 
266
        raise TypeError('delta is not a str')
 
267
    source = PyString_AS_STRING(source_bytes)
 
268
    source_size = PyString_GET_SIZE(source_bytes)
 
269
    delta = PyString_AS_STRING(delta_bytes)
 
270
    delta_size = PyString_GET_SIZE(delta_bytes)
 
271
    # Code taken from patch-delta.c, only brought here to give better error
 
272
    # handling, and to avoid double allocating memory
 
273
    if (delta_size < DELTA_SIZE_MIN):
 
274
        # XXX: Invalid delta block
 
275
        raise RuntimeError('delta_size %d smaller than min delta size %d'
 
276
                           % (delta_size, DELTA_SIZE_MIN))
 
277
 
 
278
    return _apply_delta(source, source_size, delta, delta_size)
 
279
 
 
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
 
 
326
cdef object _apply_delta(char *source, Py_ssize_t source_size,
 
327
                         char *delta, Py_ssize_t delta_size):
 
328
    """common functionality between apply_delta and apply_delta_to_source."""
 
329
    cdef unsigned char *data, *top
 
330
    cdef unsigned char *dst_buf, *out, cmd
 
331
    cdef Py_ssize_t size
 
332
    cdef unsigned int cp_off, cp_size
 
333
    cdef int failed
 
334
 
 
335
    data = <unsigned char *>delta
 
336
    top = data + delta_size
 
337
 
 
338
    # now the result size
 
339
    size = get_delta_hdr_size(&data, top)
 
340
    result = PyString_FromStringAndSize(NULL, size)
 
341
    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
 
388
    if (data != top or size != 0):
 
389
        raise RuntimeError('Did not extract the number of bytes we expected'
 
390
            ' we were left with %d bytes in "size", and top - data = %d'
 
391
            % (size, <int>(top - data)))
 
392
        return None
 
393
 
 
394
    # *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.')
 
398
    return result
 
399
 
 
400
 
 
401
def apply_delta_to_source(source, delta_start, delta_end):
 
402
    """Extract a delta from source bytes, and apply it."""
 
403
    cdef char *c_source
 
404
    cdef Py_ssize_t c_source_size
 
405
    cdef char *c_delta
 
406
    cdef Py_ssize_t c_delta_size
 
407
    cdef Py_ssize_t c_delta_start, c_delta_end
 
408
 
 
409
    if not PyString_CheckExact(source):
 
410
        raise TypeError('source is not a str')
 
411
    c_source_size = PyString_GET_SIZE(source)
 
412
    c_delta_start = delta_start
 
413
    c_delta_end = delta_end
 
414
    if c_delta_start >= c_source_size:
 
415
        raise ValueError('delta starts after source')
 
416
    if c_delta_end > c_source_size:
 
417
        raise ValueError('delta ends after source')
 
418
    if c_delta_start >= c_delta_end:
 
419
        raise ValueError('delta starts after it ends')
 
420
 
 
421
    c_delta_size = c_delta_end - c_delta_start
 
422
    c_source = PyString_AS_STRING(source)
 
423
    c_delta = c_source + c_delta_start
 
424
    # We don't use source_size, because we know the delta should not refer to
 
425
    # any bytes after it starts
 
426
    return _apply_delta(c_source, c_delta_start, c_delta, c_delta_size)
 
427
 
 
428
 
 
429
def encode_base128_int(val):
 
430
    """Convert an integer into a 7-bit lsb encoding."""
 
431
    cdef unsigned int c_val
 
432
    cdef Py_ssize_t count
 
433
    cdef unsigned int num_bytes
 
434
    cdef unsigned char c_bytes[8] # max size for 32-bit int is 5 bytes
 
435
 
 
436
    c_val = val
 
437
    count = 0
 
438
    while c_val >= 0x80 and count < 8:
 
439
        c_bytes[count] = <unsigned char>((c_val | 0x80) & 0xFF)
 
440
        c_val = c_val >> 7
 
441
        count = count + 1
 
442
    if count >= 8 or c_val >= 0x80:
 
443
        raise ValueError('encode_base128_int overflowed the buffer')
 
444
    c_bytes[count] = <unsigned char>(c_val & 0xFF)
 
445
    count = count + 1
 
446
    return PyString_FromStringAndSize(<char *>c_bytes, count)
 
447
 
 
448
 
 
449
def decode_base128_int(bytes):
 
450
    """Decode an integer from a 7-bit lsb encoding."""
 
451
    cdef int offset
 
452
    cdef int val
 
453
    cdef unsigned int uval
 
454
    cdef int shift
 
455
    cdef Py_ssize_t num_low_bytes
 
456
    cdef unsigned char *c_bytes
 
457
 
 
458
    offset = 0
 
459
    val = 0
 
460
    shift = 0
 
461
    if not PyString_CheckExact(bytes):
 
462
        raise TypeError('bytes is not a string')
 
463
    c_bytes = <unsigned char*>PyString_AS_STRING(bytes)
 
464
    # We take off 1, because we have to be able to decode the non-expanded byte
 
465
    num_low_bytes = PyString_GET_SIZE(bytes) - 1
 
466
    while (c_bytes[offset] & 0x80) and offset < num_low_bytes:
 
467
        val = val | ((c_bytes[offset] & 0x7F) << shift)
 
468
        shift = shift + 7
 
469
        offset = offset + 1
 
470
    if c_bytes[offset] & 0x80:
 
471
        raise ValueError('Data not properly formatted, we ran out of'
 
472
                         ' bytes before 0x80 stopped being set.')
 
473
    val = val | (c_bytes[offset] << shift)
 
474
    offset = offset + 1
 
475
    if val < 0:
 
476
        uval = <unsigned int> val
 
477
        return uval, offset
 
478
    return val, offset
 
479
 
 
480