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