« back to all changes in this revision
Viewing changes to bzrlib/_groupcompress_py.py
- browse files at revision 3735.40.11
- compare with another revision
- compare with revision 6170
- download diff
- download tarball
- view history from revision 3735.40.11
- Committer: John Arbash Meinel
- Date: 2009-03-27 20:12:12 UTC
- mto: (3735.39.2 clean)
- mto: This revision was merged to the branch mainline in revision 4280.
- Revision ID: john@arbash-meinel.com-20090327201212-1ykalx15yr1cquxt
Implement make_delta and apply_delta.
Update the permuted tests so that both implementations are tested.
Update the permuted tests so that both implementations are tested.
added
removed
bzrlib/_groupcompress_py.py
206
206
out_lines.append(copy_bytes)
207
207
index_lines.append(False)
208
208
209
def make_delta(self, new_lines, soft=False):
209
def make_delta(self, new_lines, bytes_length=None, soft=False):
210
210
"""Compute the delta for this content versus the original content."""
211
# reserved for content type, content length, target_len
212
out_lines = ['', '', '']
211
if bytes_length is None:
212
bytes_length = sum(map(len, new_lines))
213
# reserved for content type, content length
214
out_lines = ['', '', encode_base128_int(bytes_length)]
213
215
index_lines = [False, False, False]
214
216
blocks = self.get_matching_blocks(new_lines, soft=soft)
215
217
current_line_num = 0
226
228
return out_lines, index_lines
227
229
228
230
231
def encode_base128_int(val):
232
"""Convert an integer into a 7-bit lsb encoding."""
233
bytes = []
234
count = 0
235
while val >= 0x80:
236
bytes.append(chr((val | 0x80) & 0xFF))
237
val >>= 7
238
bytes.append(chr(val))
239
return ''.join(bytes)
240
241
242
def decode_base128_int(bytes):
243
"""Decode an integer from a 7-bit lsb encoding."""
244
offset = 0
245
val = 0
246
shift = 0
247
bval = ord(bytes[offset])
248
while bval >= 0x80:
249
val |= (bval & 0x7F) << shift
250
shift += 7
251
offset += 1
252
bval = ord(bytes[offset])
253
val |= bval << shift
254
offset += 1
255
return val, offset
256
257
229
258
def encode_copy_instruction(offset, length):
230
259
"""Convert this offset into a control code and bytes."""
231
260
copy_command = 0x80
258
287
return ''.join(copy_bytes)
259
288
260
289
290
def decode_copy_instruction(bytes, cmd, pos):
291
"""Decode a copy instruction from the next few bytes.
292
293
A copy instruction is a variable number of bytes, so we will parse the
294
bytes we care about, and return the new position, as well as the offset and
295
length referred to in the bytes.
296
297
:param bytes: A string of bytes
298
:param cmd: The command code
299
:param pos: The position in bytes right after the copy command
300
:return: (offset, length, newpos)
301
The offset of the copy start, the number of bytes to copy, and the
302
position after the last byte of the copy
303
"""
304
if cmd & 0x80 != 0x80:
305
raise ValueError('copy instructions must have bit 0x80 set')
306
offset = 0
307
length = 0
308
if (cmd & 0x01):
309
offset = ord(bytes[pos])
310
pos += 1
311
if (cmd & 0x02):
312
offset = offset | (ord(bytes[pos]) << 8)
313
pos += 1
314
if (cmd & 0x04):
315
offset = offset | (ord(bytes[pos]) << 16)
316
pos += 1
317
if (cmd & 0x08):
318
offset = offset | (ord(bytes[pos]) << 24)
319
pos += 1
320
if (cmd & 0x10):
321
length = ord(bytes[pos])
322
pos += 1
323
if (cmd & 0x20):
324
length = length | (ord(bytes[pos]) << 8)
325
pos += 1
326
if (cmd & 0x40):
327
length = length | (ord(bytes[pos]) << 16)
328
pos += 1
329
if length == 0:
330
length = 65536
331
return (offset, length, pos)
332
261
333
262
334
def make_delta(source_bytes, target_bytes):
263
335
"""Create a delta from source to target."""
264
336
# TODO: The checks below may not be a the right place yet.
265
if not isinstance(source_bytes, str):
337
if type(source_bytes) is not str:
266
338
raise TypeError('source is not a str')
267
if not isinstance(target_bytes, str):
339
if type(target_bytes) is not str:
268
340
raise TypeError('target is not a str')
269
341
line_locations = EquivalenceTable([])
270
return None
342
source_lines = osutils.split_lines(source_bytes)
343
line_locations.extend_lines(source_lines, [True]*len(source_lines))
344
delta, _ = line_locations.make_delta(osutils.split_lines(target_bytes),
345
bytes_length=len(target_bytes))
346
return ''.join(delta)
271
347
272
348
273
349
def apply_delta(basis, delta):
274
350
"""Apply delta to this object to become new_version_id."""
351
if type(basis) is not str:
352
raise TypeError('basis is not a str')
353
if type(delta) is not str:
354
raise TypeError('delta is not a str')
355
target_length, pos = decode_base128_int(delta)
275
356
lines = []
276
last_offset = 0
277
# eq ranges occur where gaps occur
278
# start, end refer to offsets in basis
279
for op, start, count, delta_lines in delta:
280
if op == 'c':
281
lines.append(basis[start:start+count])
282
else:
283
lines.extend(delta_lines)
284
return lines
357
len_delta = len(delta)
358
while pos < len_delta:
359
cmd = ord(delta[pos])
360
pos += 1
361
if cmd & 0x80:
362
offset, length, pos = decode_copy_instruction(delta, cmd, pos)
363
lines.append(basis[offset:offset+length])
364
else: # Insert of 'cmd' bytes
365
if cmd == 0:
366
raise ValueError('Command == 0 not supported yet')
367
lines.append(delta[pos:pos+cmd])
368
pos += cmd
369
bytes = ''.join(lines)
370
if len(bytes) != target_length:
371
raise ValueError('Delta claimed to be %d long, but ended up'
372
' %d long' % (target_length, len(bytes)))
373
return bytes
Loggerhead is a web-based interface for Breezy
Version: 2.0.1