← Back to branch summary

~bzr-pqm/bzr/bzr.dev

« back to all changes in this revision

Viewing changes to bzrlib/_groupcompress_pyx.pyx

  • Committer: Colin Watson
  • Date: 2015-07-02 11:30:47 UTC
  • mto: This revision was merged to the branch mainline in revision 6605.
  • Revision ID: cjwatson@canonical.com-20150702113047-359s4zsi07wvfwso
Use assertLength.

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
22
22
 
23
23
 
24
24
cdef extern from "Python.h":
 
25
    ctypedef struct PyObject:
 
26
        pass
25
27
    ctypedef int Py_ssize_t # Required for older pyrex versions
26
28
    int PyString_CheckExact(object)
27
29
    char * PyString_AS_STRING(object)
44
46
        unsigned long agg_offset
45
47
    struct delta_index:
46
48
        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
 
49
    ctypedef enum delta_result:
 
50
        DELTA_OK
 
51
        DELTA_OUT_OF_MEMORY
 
52
        DELTA_INDEX_NEEDED
 
53
        DELTA_SOURCE_EMPTY
 
54
        DELTA_SOURCE_BAD
 
55
        DELTA_BUFFER_EMPTY
 
56
        DELTA_SIZE_TOO_BIG
 
57
    delta_result create_delta_index(source_info *src,
 
58
                                    delta_index *old,
 
59
                                    delta_index **fresh,
 
60
                                    int max_entries) nogil
 
61
    delta_result create_delta_index_from_delta(source_info *delta,
 
62
                                               delta_index *old,
 
63
                                               delta_index **fresh) nogil
50
64
    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
 
65
    delta_result create_delta(delta_index *indexes,
 
66
                              void *buf, unsigned long bufsize,
 
67
                              unsigned long *delta_size,
 
68
                              unsigned long max_delta_size,
 
69
                              void **delta_data) nogil
54
70
    unsigned long get_delta_hdr_size(unsigned char **datap,
55
71
                                     unsigned char *top) nogil
 
72
    unsigned long sizeof_delta_index(delta_index *index)
56
73
    Py_ssize_t DELTA_SIZE_MIN
 
74
    int get_hash_offset(delta_index *index, int pos, unsigned int *hash_offset)
 
75
    int get_entry_summary(delta_index *index, int pos,
 
76
                          unsigned int *global_offset, unsigned int *hash_val)
 
77
    unsigned int rabin_hash (unsigned char *data)
57
78
 
58
79
 
59
80
cdef void *safe_malloc(size_t count) except NULL:
83
104
    return DeltaIndex(source)
84
105
 
85
106
 
 
107
cdef object _translate_delta_failure(delta_result result):
 
108
    if result == DELTA_OUT_OF_MEMORY:
 
109
        return MemoryError("Delta function failed to allocate memory")
 
110
    elif result == DELTA_INDEX_NEEDED:
 
111
        return ValueError("Delta function requires delta_index param")
 
112
    elif result == DELTA_SOURCE_EMPTY:
 
113
        return ValueError("Delta function given empty source_info param")
 
114
    elif result == DELTA_SOURCE_BAD:
 
115
        return RuntimeError("Delta function given invalid source_info param")
 
116
    elif result == DELTA_BUFFER_EMPTY:
 
117
        return ValueError("Delta function given empty buffer params")
 
118
    return AssertionError("Unrecognised delta result code: %d" % result)
 
119
 
 
120
 
 
121
def _rabin_hash(content):
 
122
    if not PyString_CheckExact(content):
 
123
        raise ValueError('content must be a string')
 
124
    if len(content) < 16:
 
125
        raise ValueError('content must be at least 16 bytes long')
 
126
    # Try to cast it to an int, if it can fit
 
127
    return int(rabin_hash(<unsigned char*>(PyString_AS_STRING(content))))
 
128
 
 
129
 
86
130
cdef class DeltaIndex:
87
131
 
88
132
    # We need Pyrex 0.9.8+ to understand a 'list' definition, and this object
91
135
    cdef readonly object _sources
92
136
    cdef source_info *_source_infos
93
137
    cdef delta_index *_index
 
138
    cdef public unsigned long _source_offset
94
139
    cdef readonly unsigned int _max_num_sources
95
 
    cdef public unsigned long _source_offset
 
140
    cdef public int _max_bytes_to_index
96
141
 
97
 
    def __init__(self, source=None):
 
142
    def __init__(self, source=None, max_bytes_to_index=None):
98
143
        self._sources = []
99
144
        self._index = NULL
100
145
        self._max_num_sources = 65000
101
146
        self._source_infos = <source_info *>safe_malloc(sizeof(source_info)
102
147
                                                        * self._max_num_sources)
103
148
        self._source_offset = 0
 
149
        self._max_bytes_to_index = 0
 
150
        if max_bytes_to_index is not None:
 
151
            self._max_bytes_to_index = max_bytes_to_index
104
152
 
105
153
        if source is not None:
106
154
            self.add_source(source, 0)
107
155
 
 
156
    def __sizeof__(self):
 
157
        # We want to track the _source_infos allocations, but the referenced
 
158
        # void* are actually tracked in _sources itself.
 
159
        # XXX: Cython is capable of doing sizeof(class) and returning the size
 
160
        #      of the underlying struct. Pyrex (<= 0.9.9) refuses, so we need
 
161
        #      to do it manually. *sigh* Note that we might get it wrong
 
162
        #      because of alignment issues.
 
163
        cdef Py_ssize_t size
 
164
        # PyObject start, vtable *, 3 object pointers, 2 C ints
 
165
        size = ((sizeof(PyObject) + sizeof(void*) + 3*sizeof(PyObject*)
 
166
                 + sizeof(unsigned long)
 
167
                 + sizeof(unsigned int))
 
168
                + (sizeof(source_info) * self._max_num_sources)
 
169
                + sizeof_delta_index(self._index))
 
170
        return size
 
171
 
108
172
    def __repr__(self):
109
173
        return '%s(%d, %d)' % (self.__class__.__name__,
110
174
            len(self._sources), self._source_offset)
118
182
    def _has_index(self):
119
183
        return (self._index != NULL)
120
184
 
 
185
    def _dump_index(self):
 
186
        """Dump the pointers in the index.
 
187
 
 
188
        This is an arbitrary layout, used for testing. It is not meant to be
 
189
        used in production code.
 
190
 
 
191
        :return: (hash_list, entry_list)
 
192
            hash_list   A list of offsets, so hash[i] points to the 'hash
 
193
                        bucket' starting at the given offset and going until
 
194
                        hash[i+1]
 
195
            entry_list  A list of (text_offset, hash_val). text_offset is the
 
196
                        offset in the "source" texts, and hash_val is the RABIN
 
197
                        hash for that offset.
 
198
                        Note that the entry should be in the hash bucket
 
199
                        defined by
 
200
                        hash[(hash_val & mask)] && hash[(hash_val & mask) + 1]
 
201
        """
 
202
        cdef int pos
 
203
        cdef unsigned int text_offset
 
204
        cdef unsigned int hash_val
 
205
        cdef unsigned int hash_offset
 
206
        if self._index == NULL:
 
207
            return None
 
208
        hash_list = []
 
209
        pos = 0
 
210
        while get_hash_offset(self._index, pos, &hash_offset):
 
211
            hash_list.append(int(hash_offset))
 
212
            pos += 1
 
213
        entry_list = []
 
214
        pos = 0
 
215
        while get_entry_summary(self._index, pos, &text_offset, &hash_val):
 
216
            # Map back using 'int' so that we don't get Long everywhere, when
 
217
            # almost everything is <2**31.
 
218
            val = tuple(map(int, [text_offset, hash_val]))
 
219
            entry_list.append(val)
 
220
            pos += 1
 
221
        return hash_list, entry_list
 
222
 
121
223
    def add_delta_source(self, delta, unadded_bytes):
122
224
        """Add a new delta to the source texts.
123
225
 
128
230
        cdef char *c_delta
129
231
        cdef Py_ssize_t c_delta_size
130
232
        cdef delta_index *index
 
233
        cdef delta_result res
131
234
        cdef unsigned int source_location
132
235
        cdef source_info *src
133
236
        cdef unsigned int num_indexes
146
249
        src.size = c_delta_size
147
250
        src.agg_offset = self._source_offset + unadded_bytes
148
251
        with nogil:
149
 
            index = create_delta_index_from_delta(src, self._index)
 
252
            res = create_delta_index_from_delta(src, self._index, &index)
 
253
        if res != DELTA_OK:
 
254
            raise _translate_delta_failure(res)
150
255
        self._source_offset = src.agg_offset + src.size
151
 
        if index != NULL:
 
256
        if index != self._index:
152
257
            free_delta_index(self._index)
153
258
            self._index = index
154
259
 
158
263
        :param source: The text in question, this must be a byte string
159
264
        :param unadded_bytes: Assume there are this many bytes that didn't get
160
265
            added between this source and the end of the previous source.
 
266
        :param max_pointers: Add no more than this many entries to the index.
 
267
            By default, we sample every 16 bytes, if that would require more
 
268
            than max_entries, we will reduce the sampling rate.
 
269
            A value of 0 means unlimited, None means use the default limit.
161
270
        """
162
271
        cdef char *c_source
163
272
        cdef Py_ssize_t c_source_size
164
273
        cdef delta_index *index
 
274
        cdef delta_result res
165
275
        cdef unsigned int source_location
166
276
        cdef source_info *src
167
277
        cdef unsigned int num_indexes
 
278
        cdef int max_num_entries
168
279
 
169
280
        if not PyString_CheckExact(source):
170
281
            raise TypeError('source is not a str')
187
298
        # We delay creating the index on the first insert
188
299
        if source_location != 0:
189
300
            with nogil:
190
 
                index = create_delta_index(src, self._index)
191
 
            if index != NULL:
 
301
                res = create_delta_index(src, self._index, &index,
 
302
                                         self._max_bytes_to_index)
 
303
            if res != DELTA_OK:
 
304
                raise _translate_delta_failure(res)
 
305
            if index != self._index:
192
306
                free_delta_index(self._index)
193
307
                self._index = index
194
308
 
195
309
    cdef _populate_first_index(self):
196
310
        cdef delta_index *index
 
311
        cdef delta_result res
197
312
        if len(self._sources) != 1 or self._index != NULL:
198
313
            raise AssertionError('_populate_first_index should only be'
199
314
                ' called when we have a single source and no index yet')
200
315
 
201
 
        # We know that self._index is already NULL, so whatever
202
 
        # create_delta_index returns is fine
 
316
        # We know that self._index is already NULL, so create_delta_index
 
317
        # will always create a new index unless there's a malloc failure
203
318
        with nogil:
204
 
            self._index = create_delta_index(&self._source_infos[0], NULL)
205
 
        assert self._index != NULL
 
319
            res = create_delta_index(&self._source_infos[0], NULL, &index,
 
320
                                     self._max_bytes_to_index)
 
321
        if res != DELTA_OK:
 
322
            raise _translate_delta_failure(res)
 
323
        self._index = index
206
324
 
207
325
    cdef _expand_sources(self):
208
326
        raise RuntimeError('if we move self._source_infos, then we need to'
219
337
        cdef void * delta
220
338
        cdef unsigned long delta_size
221
339
        cdef unsigned long c_max_delta_size
 
340
        cdef delta_result res
222
341
 
223
342
        if self._index == NULL:
224
343
            if len(self._sources) == 0:
237
356
        #       allocate the bytes into the final string
238
357
        c_max_delta_size = max_delta_size
239
358
        with nogil:
240
 
            delta = create_delta(self._index,
241
 
                                 target, target_size,
242
 
                                 &delta_size, c_max_delta_size)
 
359
            res = create_delta(self._index, target, target_size,
 
360
                               &delta_size, c_max_delta_size, &delta)
243
361
        result = None
244
 
        if delta:
 
362
        if res == DELTA_OK:
245
363
            result = PyString_FromStringAndSize(<char *>delta, delta_size)
246
364
            free(delta)
 
365
        elif res != DELTA_SIZE_TOO_BIG:
 
366
            raise _translate_delta_failure(res)
247
367
        return result
248
368
 
249
369
 
350
470
                # Copy instruction
351
471
                data = _decode_copy_instruction(data, cmd, &cp_off, &cp_size)
352
472
                if (cp_off + cp_size < cp_size or
353
 
                    cp_off + cp_size > source_size or
354
 
                    cp_size > size):
 
473
                    cp_off + cp_size > <unsigned int>source_size or
 
474
                    cp_size > <unsigned int>size):
355
475
                    failed = 1
356
476
                    break
357
477
                memcpy(out, source + cp_off, cp_size)