← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/_groupcompress_pyx.pyx

merge python groupcompress implementation into bbc

Show diffs side-by-side

added added

removed removed

Lines of Context:
bzrlib/_groupcompress_pyx.pyx
89
89
    cdef readonly unsigned int _max_num_sources
90
90
    cdef public unsigned long _source_offset
91
91
 
92
 
    def __repr__(self):
93
 
        return '%s(%d, %d)' % (self.__class__.__name__,
94
 
            len(self._sources), self._source_offset)
95
 
 
96
92
    def __init__(self, source=None):
97
93
        self._sources = []
98
94
        self._index = NULL
104
100
        if source is not None:
105
101
            self.add_source(source, 0)
106
102
 
 
103
    def __repr__(self):
 
104
        return '%s(%d, %d)' % (self.__class__.__name__,
 
105
            len(self._sources), self._source_offset)
 
106
 
107
107
    def __dealloc__(self):
108
108
        if self._index != NULL:
109
109
            free_delta_index(self._index)
226
226
    cdef Py_ssize_t source_size
227
227
    cdef char *delta
228
228
    cdef Py_ssize_t delta_size
229
 
    cdef unsigned char *data, *top
230
 
    cdef unsigned char *dst_buf, *out, cmd
231
 
    cdef Py_ssize_t size
232
 
    cdef unsigned long cp_off, cp_size
233
229
 
234
230
    if not PyString_CheckExact(source_bytes):
235
231
        raise TypeError('source is not a str')
236
232
    if not PyString_CheckExact(delta_bytes):
237
233
        raise TypeError('delta is not a str')
238
 
 
239
234
    source = PyString_AS_STRING(source_bytes)
240
235
    source_size = PyString_GET_SIZE(source_bytes)
241
236
    delta = PyString_AS_STRING(delta_bytes)
242
237
    delta_size = PyString_GET_SIZE(delta_bytes)
243
 
 
244
238
    # Code taken from patch-delta.c, only brought here to give better error
245
239
    # handling, and to avoid double allocating memory
246
240
    if (delta_size < DELTA_SIZE_MIN):
248
242
        raise RuntimeError('delta_size %d smaller than min delta size %d'
249
243
                           % (delta_size, DELTA_SIZE_MIN))
250
244
 
 
245
    return _apply_delta(source, source_size, delta, delta_size)
 
246
 
 
247
 
 
248
cdef unsigned char *_decode_copy_instruction(unsigned char *bytes,
 
249
    unsigned char cmd, unsigned int *offset, unsigned int *length):
 
250
    """Decode a copy instruction from the next few bytes.
 
251
 
 
252
    A copy instruction is a variable number of bytes, so we will parse the
 
253
    bytes we care about, and return the new position, as well as the offset and
 
254
    length referred to in the bytes.
 
255
 
 
256
    :param bytes: Pointer to the start of bytes after cmd
 
257
    :param cmd: The command code
 
258
    :return: Pointer to the bytes just after the last decode byte
 
259
    """
 
260
    cdef unsigned int off, size, count
 
261
    off = 0
 
262
    size = 0
 
263
    count = 0
 
264
    if (cmd & 0x01):
 
265
        off = bytes[count]
 
266
        count = count + 1
 
267
    if (cmd & 0x02):
 
268
        off = off | (bytes[count] << 8)
 
269
        count = count + 1
 
270
    if (cmd & 0x04):
 
271
        off = off | (bytes[count] << 16)
 
272
        count = count + 1
 
273
    if (cmd & 0x08):
 
274
        off = off | (bytes[count] << 24)
 
275
        count = count + 1
 
276
    if (cmd & 0x10):
 
277
        size = bytes[count]
 
278
        count = count + 1
 
279
    if (cmd & 0x20):
 
280
        size = size | (bytes[count] << 8)
 
281
        count = count + 1
 
282
    if (cmd & 0x40):
 
283
        size = size | (bytes[count] << 16)
 
284
        count = count + 1
 
285
    if (size == 0):
 
286
        size = 0x10000
 
287
    offset[0] = off
 
288
    length[0] = size
 
289
    return bytes + count
 
290
 
 
291
 
 
292
cdef object _apply_delta(char *source, Py_ssize_t source_size,
 
293
                         char *delta, Py_ssize_t delta_size):
 
294
    """common functionality between apply_delta and apply_delta_to_source."""
 
295
    cdef unsigned char *data, *top
 
296
    cdef unsigned char *dst_buf, *out, cmd
 
297
    cdef Py_ssize_t size
 
298
    cdef unsigned int cp_off, cp_size
 
299
 
251
300
    data = <unsigned char *>delta
252
301
    top = data + delta_size
253
302
 
254
 
    # make sure the orig file size matches what we expect
255
 
    # XXX: gcc warns because data isn't defined as 'const'
256
 
    size = get_delta_hdr_size(&data, top)
257
 
    if (size > source_size):
258
 
        # XXX: mismatched source size
259
 
        raise RuntimeError('source size %d < expected source size %d'
260
 
                           % (source_size, size))
261
 
    source_size = size
262
 
 
263
303
    # now the result size
264
304
    size = get_delta_hdr_size(&data, top)
265
305
    result = PyString_FromStringAndSize(NULL, size)
266
306
    dst_buf = <unsigned char*>PyString_AS_STRING(result)
267
 
    # XXX: The original code added a trailing null here, but this shouldn't be
268
 
    #      necessary when using PyString_FromStringAndSize
269
 
    # dst_buf[size] = 0
270
307
 
271
308
    out = dst_buf
272
309
    while (data < top):
273
310
        cmd = data[0]
274
311
        data = data + 1
275
312
        if (cmd & 0x80):
276
 
            cp_off = cp_size = 0
277
 
            if (cmd & 0x01):
278
 
                cp_off = data[0]
279
 
                data = data + 1
280
 
            if (cmd & 0x02):
281
 
                cp_off = cp_off | (data[0] << 8)
282
 
                data = data + 1
283
 
            if (cmd & 0x04):
284
 
                cp_off = cp_off | (data[0] << 16)
285
 
                data = data + 1
286
 
            if (cmd & 0x08):
287
 
                cp_off = cp_off | (data[0] << 24)
288
 
                data = data + 1
289
 
            if (cmd & 0x10):
290
 
                cp_size = data[0]
291
 
                data = data + 1
292
 
            if (cmd & 0x20):
293
 
                cp_size = cp_size | (data[0] << 8)
294
 
                data = data + 1
295
 
            if (cmd & 0x40):
296
 
                cp_size = cp_size | (data[0] << 16)
297
 
                data = data + 1
298
 
            if (cp_size == 0):
299
 
                cp_size = 0x10000
 
313
            # Copy instruction
 
314
            data = _decode_copy_instruction(data, cmd, &cp_off, &cp_size)
300
315
            if (cp_off + cp_size < cp_size or
301
316
                cp_off + cp_size > source_size or
302
317
                cp_size > size):
307
322
            memcpy(out, source + cp_off, cp_size)
308
323
            out = out + cp_size
309
324
            size = size - cp_size
310
 
        elif (cmd):
 
325
        else:
 
326
            # Insert instruction
 
327
            if cmd == 0:
 
328
                # cmd == 0 is reserved for future encoding
 
329
                # extensions. In the mean time we must fail when
 
330
                # encountering them (might be data corruption).
 
331
                raise RuntimeError('Got delta opcode: 0, not supported')
311
332
            if (cmd > size):
312
333
                raise RuntimeError('Insert instruction longer than remaining'
313
334
                    ' bytes: %d > %d' % (cmd, size))
315
336
            out = out + cmd
316
337
            data = data + cmd
317
338
            size = size - cmd
318
 
        else:
319
 
            # /*
320
 
            #  * cmd == 0 is reserved for future encoding
321
 
            #  * extensions. In the mean time we must fail when
322
 
            #  * encountering them (might be data corruption).
323
 
            #  */
324
 
            ## /* XXX: error("unexpected delta opcode 0"); */
325
 
            raise RuntimeError('Got delta opcode: 0, not supported')
326
339
 
327
 
    # /* sanity check */
 
340
    # sanity check
328
341
    if (data != top or size != 0):
329
 
        ## /* XXX: error("delta replay has gone wild"); */
330
342
        raise RuntimeError('Did not extract the number of bytes we expected'
331
343
            ' we were left with %d bytes in "size", and top - data = %d'
332
344
            % (size, <int>(top - data)))
333
345
        return None
334
346
 
335
347
    # *dst_size = out - dst_buf;
336
 
    assert (out - dst_buf) == PyString_GET_SIZE(result)
 
348
    if (out - dst_buf) != PyString_GET_SIZE(result):
 
349
        raise RuntimeError('Number of bytes extracted did not match the'
 
350
            ' size encoded in the delta header.')
337
351
    return result
 
352
 
 
353
 
 
354
def apply_delta_to_source(source, delta_start, delta_end):
 
355
    """Extract a delta from source bytes, and apply it."""
 
356
    cdef char *c_source
 
357
    cdef Py_ssize_t c_source_size
 
358
    cdef char *c_delta
 
359
    cdef Py_ssize_t c_delta_size
 
360
    cdef Py_ssize_t c_delta_start, c_delta_end
 
361
 
 
362
    if not PyString_CheckExact(source):
 
363
        raise TypeError('source is not a str')
 
364
    c_source_size = PyString_GET_SIZE(source)
 
365
    c_delta_start = delta_start
 
366
    c_delta_end = delta_end
 
367
    if c_delta_start >= c_source_size:
 
368
        raise ValueError('delta starts after source')
 
369
    if c_delta_end > c_source_size:
 
370
        raise ValueError('delta ends after source')
 
371
    if c_delta_start >= c_delta_end:
 
372
        raise ValueError('delta starts after it ends')
 
373
 
 
374
    c_delta_size = c_delta_end - c_delta_start
 
375
    c_source = PyString_AS_STRING(source)
 
376
    c_delta = c_source + c_delta_start
 
377
    # We don't use source_size, because we know the delta should not refer to
 
378
    # any bytes after it starts
 
379
    return _apply_delta(c_source, c_delta_start, c_delta, c_delta_size)
 
380
 
 
381
 
 
382
def encode_base128_int(val):
 
383
    """Convert an integer into a 7-bit lsb encoding."""
 
384
    cdef unsigned int c_val
 
385
    cdef Py_ssize_t count
 
386
    cdef unsigned int num_bytes
 
387
    cdef unsigned char c_bytes[8] # max size for 32-bit int is 5 bytes
 
388
 
 
389
    c_val = val
 
390
    count = 0
 
391
    while c_val >= 0x80 and count < 8:
 
392
        c_bytes[count] = <unsigned char>((c_val | 0x80) & 0xFF)
 
393
        c_val = c_val >> 7
 
394
        count = count + 1
 
395
    if count >= 8 or c_val >= 0x80:
 
396
        raise ValueError('encode_base128_int overflowed the buffer')
 
397
    c_bytes[count] = <unsigned char>(c_val & 0xFF)
 
398
    count = count + 1
 
399
    return PyString_FromStringAndSize(<char *>c_bytes, count)
 
400
 
 
401
 
 
402
def decode_base128_int(bytes):
 
403
    """Decode an integer from a 7-bit lsb encoding."""
 
404
    cdef int offset
 
405
    cdef int val
 
406
    cdef unsigned int uval
 
407
    cdef int shift
 
408
    cdef Py_ssize_t num_low_bytes
 
409
    cdef unsigned char *c_bytes
 
410
 
 
411
    offset = 0
 
412
    val = 0
 
413
    shift = 0
 
414
    if not PyString_CheckExact(bytes):
 
415
        raise TypeError('bytes is not a string')
 
416
    c_bytes = <unsigned char*>PyString_AS_STRING(bytes)
 
417
    # We take off 1, because we have to be able to decode the non-expanded byte
 
418
    num_low_bytes = PyString_GET_SIZE(bytes) - 1
 
419
    while (c_bytes[offset] & 0x80) and offset < num_low_bytes:
 
420
        val |= (c_bytes[offset] & 0x7F) << shift
 
421
        shift = shift + 7
 
422
        offset = offset + 1
 
423
    if c_bytes[offset] & 0x80:
 
424
        raise ValueError('Data not properly formatted, we ran out of'
 
425
                         ' bytes before 0x80 stopped being set.')
 
426
    val |= c_bytes[offset] << shift
 
427
    offset = offset + 1
 
428
    if val < 0:
 
429
        uval = <unsigned int> val
 
430
        return uval, offset
 
431
    return val, offset
 
432
 
 
433