comparison MoinMoin/util/bdiff.py @ 961:21eb4cb11e2c

Added binary diffing! Not much left for the getDiff function.
author Alexander Schremmer <alex AT alexanderweb DOT de>
date Sat, 01 Jul 2006 01:28:46 +0200
parents
children 930c9e82a60b
comparison
equal deleted inserted replaced
960:afb156d4caa5 961:21eb4cb11e2c
1 # Binary patching and diffing
2 #
3 # Copyright 2005 Matt Mackall <mpm@selenic.com>
4 # Copyright 2006 MoinMoin:AlexanderSchremmer
5 #
6 # Algorithm taken from mercurial's mdiff.py
7 #
8 # This software may be used and distributed according to the terms
9 # of the GNU General Public License, incorporated herein by reference.
10
11 import zlib, difflib, struct
12
13 BDIFF_PATT = ">lll"
14
15 def compress(text):
16 return zlib.compress(text) # here we could tune the compression level
17
18 def decompress(bin):
19 return zlib.decompress(bin)
20
21 def diff(a, b):
22 """ Generates a binary diff of the passed strings. """
23 if not a:
24 return b and (struct.pack(BDIFF_PATT, 0, 0, len(b)) + b)
25
26 bin = []
27 la = lb = 0
28
29 p = [0]
30 for i in a: p.append(p[-1] + len(i))
31
32 for am, bm, size in difflib.SequenceMatcher(None, a, b).get_matching_blocks():
33 s = "".join(b[lb:bm])
34 if am > la or s:
35 bin.append(struct.pack(BDIFF_PATT, p[la], p[am], len(s)) + s)
36 la = am + size
37 lb = bm + size
38
39 return "".join(bin)
40
41 def patchtext(bin):
42 """ Returns the new hunks that are contained in a binary diff."""
43 pos = 0
44 t = []
45 while pos < len(bin):
46 p1, p2, l = struct.unpack(BDIFF_PATT, bin[pos:pos + 12])
47 pos += 12
48 t.append(bin[pos:pos + l])
49 pos += l
50 return "".join(t)
51
52 def patch(a, bin):
53 """ Patches the string a with the binary patch bin. """
54 c = last = pos = 0
55 r = []
56
57 while pos < len(bin):
58 p1, p2, l = struct.unpack(BDIFF_PATT, bin[pos:pos + 12])
59 pos += 12
60 r.append(a[last:p1])
61 r.append(bin[pos:pos + l])
62 pos += l
63 last = p2
64 c += 1
65 r.append(a[last:])
66
67 return "".join(r)
68
69 def test():
70 a = "fo" * 30
71 b = "br" * 30
72 d = diff(a, b)
73 z = compress(d)
74 print `patchtext(d)`
75 #print `d`
76 print b == patch(a, d)
77 print len(d), len(z)
78
79 test()