Show More
@@ -0,0 +1,103 b'' | |||||
|
1 | # mpatch.py - Python implementation of mpatch.c | |||
|
2 | # | |||
|
3 | # Copyright 2009 Matt Mackall <mpm@selenic.com> and others | |||
|
4 | # | |||
|
5 | # This software may be used and distributed according to the terms | |||
|
6 | # of the GNU General Public License, incorporated herein by reference. | |||
|
7 | ||||
|
8 | import struct, mmap | |||
|
9 | ||||
|
10 | devzero = file("/dev/zero") | |||
|
11 | ||||
|
12 | # This attempts to apply a series of patches in time proportional to | |||
|
13 | # the total size of the patches, rather than patches * len(text). This | |||
|
14 | # means rather than shuffling strings around, we shuffle around | |||
|
15 | # pointers to fragments with fragment lists. | |||
|
16 | # | |||
|
17 | # When the fragment lists get too long, we collapse them. To do this | |||
|
18 | # efficiently, we do all our operations inside a buffer created by | |||
|
19 | # mmap and simply use memmove. This avoids creating a bunch of large | |||
|
20 | # temporary string buffers. | |||
|
21 | ||||
|
22 | def patches(a, bins): | |||
|
23 | if not bins: return a | |||
|
24 | ||||
|
25 | plens = [len(x) for x in bins] | |||
|
26 | pl = sum(plens) | |||
|
27 | bl = len(a) + pl | |||
|
28 | tl = bl + bl + pl # enough for the patches and two working texts | |||
|
29 | b1, b2 = 0, bl | |||
|
30 | ||||
|
31 | if not tl: return a | |||
|
32 | ||||
|
33 | m = mmap.mmap(devzero.fileno(), tl, mmap.MAP_PRIVATE) | |||
|
34 | ||||
|
35 | # load our original text | |||
|
36 | m.write(a) | |||
|
37 | frags = [(len(a), b1)] | |||
|
38 | ||||
|
39 | # copy all the patches into our segment so we can memmove from them | |||
|
40 | pos = b2 + bl | |||
|
41 | m.seek(pos) | |||
|
42 | for p in bins: m.write(p) | |||
|
43 | ||||
|
44 | def pull(dst, src, l): # pull l bytes from src | |||
|
45 | while l: | |||
|
46 | f = src.pop(0) | |||
|
47 | if f[0] > l: # do we need to split? | |||
|
48 | src.insert(0, (f[0] - l, f[1] + l)) | |||
|
49 | dst.append((l, f[1])) | |||
|
50 | return | |||
|
51 | dst.append(f) | |||
|
52 | l -= f[0] | |||
|
53 | ||||
|
54 | def collect(buf, list): | |||
|
55 | start = buf | |||
|
56 | for l, p in list: | |||
|
57 | m.move(buf, p, l) | |||
|
58 | buf += l | |||
|
59 | return (buf - start, start) | |||
|
60 | ||||
|
61 | for plen in plens: | |||
|
62 | # if our list gets too long, execute it | |||
|
63 | if len(frags) > 128: | |||
|
64 | b2, b1 = b1, b2 | |||
|
65 | frags = [collect(b1, frags)] | |||
|
66 | ||||
|
67 | new = [] | |||
|
68 | end = pos + plen | |||
|
69 | last = 0 | |||
|
70 | while pos < end: | |||
|
71 | p1, p2, l = struct.unpack(">lll", m[pos:pos + 12]) | |||
|
72 | pull(new, frags, p1 - last) # what didn't change | |||
|
73 | pull([], frags, p2 - p1) # what got deleted | |||
|
74 | new.append((l, pos + 12)) # what got added | |||
|
75 | pos += l + 12 | |||
|
76 | last = p2 | |||
|
77 | frags = new + frags # what was left at the end | |||
|
78 | ||||
|
79 | t = collect(b2, frags) | |||
|
80 | ||||
|
81 | return m[t[1]:t[1] + t[0]] | |||
|
82 | ||||
|
83 | def patchedsize(orig, delta): | |||
|
84 | outlen, last, bin = 0, 0, 0 | |||
|
85 | binend = len(delta) | |||
|
86 | data = 12 | |||
|
87 | ||||
|
88 | while data <= binend: | |||
|
89 | decode = delta[bin:bin + 12] | |||
|
90 | start, end, length = struct.unpack(">lll", decode) | |||
|
91 | if start > end: | |||
|
92 | break | |||
|
93 | bin = data + length | |||
|
94 | data = bin + 12 | |||
|
95 | outlen += start - last | |||
|
96 | last = end | |||
|
97 | outlen += length | |||
|
98 | ||||
|
99 | if bin != binend: | |||
|
100 | raise Exception("patch cannot be decoded") | |||
|
101 | ||||
|
102 | outlen += orig - last | |||
|
103 | return outlen |
General Comments 0
You need to be logged in to leave comments.
Login now