Mercurial > hg
annotate mercurial/base85.c @ 7104:9514cbb6e4f6
bdiff: normalize the diff (issue1295)
When the common part of a diff can be moved forward, move it forward.
Otherwise we don't get deterministic results (it would depends on the way we
split for the recursion).
That way we get identical hunks when doing the same change, it helps to solve
issue1295 (inconsistent diffs on different side during a merge).
author | Benoit Boissinot <benoit.boissinot@ens-lyon.org> |
---|---|
date | Tue, 14 Oct 2008 20:13:53 +0200 |
parents | 4bad632913d8 |
children | aecea6934fdd |
rev | line source |
---|---|
3283 | 1 /* |
2 base85 codec | |
3 | |
4 Copyright 2006 Brendan Cully <brendan@kublai.com> | |
5 | |
6 This software may be used and distributed according to the terms of | |
7 the GNU General Public License, incorporated herein by reference. | |
8 | |
9 Largely based on git's implementation | |
10 */ | |
11 | |
12 #include <Python.h> | |
13 | |
14 static const char b85chars[] = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ" | |
15 "abcdefghijklmnopqrstuvwxyz!#$%&()*+-;<=>?@^_`{|}~"; | |
16 static char b85dec[256]; | |
17 | |
18 static void | |
19 b85prep(void) | |
20 { | |
21 int i; | |
22 | |
23 memset(b85dec, 0, sizeof(b85dec)); | |
24 for (i = 0; i < sizeof(b85chars); i++) | |
25 b85dec[(int)(b85chars[i])] = i + 1; | |
26 } | |
27 | |
28 static PyObject * | |
29 b85encode(PyObject *self, PyObject *args) | |
30 { | |
31 const unsigned char *text; | |
32 PyObject *out; | |
33 char *dst; | |
34 int len, olen, i; | |
35 unsigned int acc, val, ch; | |
3288
e93c926e069e
Handle odd-sized base85 input and output
Brendan Cully <brendan@kublai.com>
parents:
3283
diff
changeset
|
36 int pad = 0; |
3283 | 37 |
3369
4bad632913d8
python2.5 PyArg_ParseTuple fix
Alexis S. L. Carvalho <alexis@cecm.usp.br>
parents:
3332
diff
changeset
|
38 if (!PyArg_ParseTuple(args, "s#|i", &text, &len, &pad)) |
3283 | 39 return NULL; |
40 | |
3288
e93c926e069e
Handle odd-sized base85 input and output
Brendan Cully <brendan@kublai.com>
parents:
3283
diff
changeset
|
41 if (pad) |
e93c926e069e
Handle odd-sized base85 input and output
Brendan Cully <brendan@kublai.com>
parents:
3283
diff
changeset
|
42 olen = ((len + 3) / 4 * 5) - 3; |
e93c926e069e
Handle odd-sized base85 input and output
Brendan Cully <brendan@kublai.com>
parents:
3283
diff
changeset
|
43 else { |
e93c926e069e
Handle odd-sized base85 input and output
Brendan Cully <brendan@kublai.com>
parents:
3283
diff
changeset
|
44 olen = len % 4; |
e93c926e069e
Handle odd-sized base85 input and output
Brendan Cully <brendan@kublai.com>
parents:
3283
diff
changeset
|
45 if (olen) |
e93c926e069e
Handle odd-sized base85 input and output
Brendan Cully <brendan@kublai.com>
parents:
3283
diff
changeset
|
46 olen++; |
e93c926e069e
Handle odd-sized base85 input and output
Brendan Cully <brendan@kublai.com>
parents:
3283
diff
changeset
|
47 olen += len / 4 * 5; |
e93c926e069e
Handle odd-sized base85 input and output
Brendan Cully <brendan@kublai.com>
parents:
3283
diff
changeset
|
48 } |
e93c926e069e
Handle odd-sized base85 input and output
Brendan Cully <brendan@kublai.com>
parents:
3283
diff
changeset
|
49 if (!(out = PyString_FromStringAndSize(NULL, olen + 3))) |
3283 | 50 return NULL; |
51 | |
52 dst = PyString_AS_STRING(out); | |
53 | |
3288
e93c926e069e
Handle odd-sized base85 input and output
Brendan Cully <brendan@kublai.com>
parents:
3283
diff
changeset
|
54 while (len) { |
3283 | 55 acc = 0; |
56 for (i = 24; i >= 0; i -= 8) { | |
57 ch = *text++; | |
58 acc |= ch << i; | |
59 if (--len == 0) | |
60 break; | |
61 } | |
62 for (i = 4; i >= 0; i--) { | |
63 val = acc % 85; | |
64 acc /= 85; | |
65 dst[i] = b85chars[val]; | |
66 } | |
67 dst += 5; | |
68 } | |
69 | |
3288
e93c926e069e
Handle odd-sized base85 input and output
Brendan Cully <brendan@kublai.com>
parents:
3283
diff
changeset
|
70 if (!pad) |
e93c926e069e
Handle odd-sized base85 input and output
Brendan Cully <brendan@kublai.com>
parents:
3283
diff
changeset
|
71 _PyString_Resize(&out, olen); |
e93c926e069e
Handle odd-sized base85 input and output
Brendan Cully <brendan@kublai.com>
parents:
3283
diff
changeset
|
72 |
3283 | 73 return out; |
74 } | |
75 | |
76 static PyObject * | |
77 b85decode(PyObject *self, PyObject *args) | |
78 { | |
79 PyObject *out; | |
80 const char *text; | |
81 char *dst; | |
3288
e93c926e069e
Handle odd-sized base85 input and output
Brendan Cully <brendan@kublai.com>
parents:
3283
diff
changeset
|
82 int len, i, j, olen, c, cap; |
3283 | 83 unsigned int acc; |
84 | |
3369
4bad632913d8
python2.5 PyArg_ParseTuple fix
Alexis S. L. Carvalho <alexis@cecm.usp.br>
parents:
3332
diff
changeset
|
85 if (!PyArg_ParseTuple(args, "s#", &text, &len)) |
3283 | 86 return NULL; |
87 | |
3288
e93c926e069e
Handle odd-sized base85 input and output
Brendan Cully <brendan@kublai.com>
parents:
3283
diff
changeset
|
88 olen = len / 5 * 4; |
e93c926e069e
Handle odd-sized base85 input and output
Brendan Cully <brendan@kublai.com>
parents:
3283
diff
changeset
|
89 i = len % 5; |
e93c926e069e
Handle odd-sized base85 input and output
Brendan Cully <brendan@kublai.com>
parents:
3283
diff
changeset
|
90 if (i) |
e93c926e069e
Handle odd-sized base85 input and output
Brendan Cully <brendan@kublai.com>
parents:
3283
diff
changeset
|
91 olen += i - 1; |
3283 | 92 if (!(out = PyString_FromStringAndSize(NULL, olen))) |
93 return NULL; | |
94 | |
95 dst = PyString_AS_STRING(out); | |
96 | |
3288
e93c926e069e
Handle odd-sized base85 input and output
Brendan Cully <brendan@kublai.com>
parents:
3283
diff
changeset
|
97 i = 0; |
e93c926e069e
Handle odd-sized base85 input and output
Brendan Cully <brendan@kublai.com>
parents:
3283
diff
changeset
|
98 while (i < len) |
3283 | 99 { |
100 acc = 0; | |
3288
e93c926e069e
Handle odd-sized base85 input and output
Brendan Cully <brendan@kublai.com>
parents:
3283
diff
changeset
|
101 cap = len - i - 1; |
e93c926e069e
Handle odd-sized base85 input and output
Brendan Cully <brendan@kublai.com>
parents:
3283
diff
changeset
|
102 if (cap > 4) |
e93c926e069e
Handle odd-sized base85 input and output
Brendan Cully <brendan@kublai.com>
parents:
3283
diff
changeset
|
103 cap = 4; |
e93c926e069e
Handle odd-sized base85 input and output
Brendan Cully <brendan@kublai.com>
parents:
3283
diff
changeset
|
104 for (j = 0; j < cap; i++, j++) |
3283 | 105 { |
106 c = b85dec[(int)*text++] - 1; | |
107 if (c < 0) | |
108 return PyErr_Format(PyExc_ValueError, "Bad base85 character at position %d", i); | |
109 acc = acc * 85 + c; | |
110 } | |
3288
e93c926e069e
Handle odd-sized base85 input and output
Brendan Cully <brendan@kublai.com>
parents:
3283
diff
changeset
|
111 if (i++ < len) |
3283 | 112 { |
113 c = b85dec[(int)*text++] - 1; | |
114 if (c < 0) | |
115 return PyErr_Format(PyExc_ValueError, "Bad base85 character at position %d", i); | |
3288
e93c926e069e
Handle odd-sized base85 input and output
Brendan Cully <brendan@kublai.com>
parents:
3283
diff
changeset
|
116 /* overflow detection: 0xffffffff == "|NsC0", |
e93c926e069e
Handle odd-sized base85 input and output
Brendan Cully <brendan@kublai.com>
parents:
3283
diff
changeset
|
117 * "|NsC" == 0x03030303 */ |
e93c926e069e
Handle odd-sized base85 input and output
Brendan Cully <brendan@kublai.com>
parents:
3283
diff
changeset
|
118 if (acc > 0x03030303 || (acc *= 85) > 0xffffffff - c) |
e93c926e069e
Handle odd-sized base85 input and output
Brendan Cully <brendan@kublai.com>
parents:
3283
diff
changeset
|
119 return PyErr_Format(PyExc_ValueError, "Bad base85 sequence at position %d", i); |
e93c926e069e
Handle odd-sized base85 input and output
Brendan Cully <brendan@kublai.com>
parents:
3283
diff
changeset
|
120 acc += c; |
3283 | 121 } |
122 | |
3288
e93c926e069e
Handle odd-sized base85 input and output
Brendan Cully <brendan@kublai.com>
parents:
3283
diff
changeset
|
123 cap = olen < 4 ? olen : 4; |
e93c926e069e
Handle odd-sized base85 input and output
Brendan Cully <brendan@kublai.com>
parents:
3283
diff
changeset
|
124 olen -= cap; |
e93c926e069e
Handle odd-sized base85 input and output
Brendan Cully <brendan@kublai.com>
parents:
3283
diff
changeset
|
125 for (j = 0; j < 4 - cap; j++) |
e93c926e069e
Handle odd-sized base85 input and output
Brendan Cully <brendan@kublai.com>
parents:
3283
diff
changeset
|
126 acc *= 85; |
e93c926e069e
Handle odd-sized base85 input and output
Brendan Cully <brendan@kublai.com>
parents:
3283
diff
changeset
|
127 if (cap && cap < 4) |
e93c926e069e
Handle odd-sized base85 input and output
Brendan Cully <brendan@kublai.com>
parents:
3283
diff
changeset
|
128 acc += 0xffffff >> (cap - 1) * 8; |
e93c926e069e
Handle odd-sized base85 input and output
Brendan Cully <brendan@kublai.com>
parents:
3283
diff
changeset
|
129 for (j = 0; j < cap; j++) |
3283 | 130 { |
131 acc = (acc << 8) | (acc >> 24); | |
3288
e93c926e069e
Handle odd-sized base85 input and output
Brendan Cully <brendan@kublai.com>
parents:
3283
diff
changeset
|
132 *dst++ = acc; |
3283 | 133 } |
134 } | |
135 | |
136 return out; | |
137 } | |
138 | |
139 static char base85_doc[] = "Base85 Data Encoding"; | |
140 | |
141 static PyMethodDef methods[] = { | |
3288
e93c926e069e
Handle odd-sized base85 input and output
Brendan Cully <brendan@kublai.com>
parents:
3283
diff
changeset
|
142 {"b85encode", b85encode, METH_VARARGS, |
e93c926e069e
Handle odd-sized base85 input and output
Brendan Cully <brendan@kublai.com>
parents:
3283
diff
changeset
|
143 "Encode text in base85.\n\n" |
e93c926e069e
Handle odd-sized base85 input and output
Brendan Cully <brendan@kublai.com>
parents:
3283
diff
changeset
|
144 "If the second parameter is true, pad the result to a multiple of " |
e93c926e069e
Handle odd-sized base85 input and output
Brendan Cully <brendan@kublai.com>
parents:
3283
diff
changeset
|
145 "five characters.\n"}, |
e93c926e069e
Handle odd-sized base85 input and output
Brendan Cully <brendan@kublai.com>
parents:
3283
diff
changeset
|
146 {"b85decode", b85decode, METH_VARARGS, "Decode base85 text.\n"}, |
3283 | 147 {NULL, NULL} |
148 }; | |
149 | |
150 PyMODINIT_FUNC initbase85(void) | |
151 { | |
152 Py_InitModule3("base85", methods, base85_doc); | |
153 | |
154 b85prep(); | |
155 } |