Mercurial > public > mercurial-scm > hg
annotate mercurial/base85.c @ 7305:c21d236ca897
hgweb: descend empty directories in web view
When a manifest has a series of directories with nothing in them but a single
directory, displaying the entire chain of empty directories allows for
navigation down to the first non-empty directory with a single click.
Because Java links package hierarchy to directory hierarchy, and because Java
conventions include at least three empty directories at the top of this
hierarchy, descending down empty directories is very common in Java web tools.
| author | Ry4an Brase <ry4an-hg@ry4an.org> |
|---|---|
| date | Mon, 03 Nov 2008 10:20:28 +0100 |
| parents | aecea6934fdd |
| children | 08a0f04b56bd |
| 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; | |
|
7190
aecea6934fdd
Some additional space/tab cleanups
Thomas Arendsen Hein <thomas@intevation.de>
parents:
3369
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 | |
|
7190
aecea6934fdd
Some additional space/tab cleanups
Thomas Arendsen Hein <thomas@intevation.de>
parents:
3369
diff
changeset
|
41 if (pad) |
|
aecea6934fdd
Some additional space/tab cleanups
Thomas Arendsen Hein <thomas@intevation.de>
parents:
3369
diff
changeset
|
42 olen = ((len + 3) / 4 * 5) - 3; |
|
aecea6934fdd
Some additional space/tab cleanups
Thomas Arendsen Hein <thomas@intevation.de>
parents:
3369
diff
changeset
|
43 else { |
|
aecea6934fdd
Some additional space/tab cleanups
Thomas Arendsen Hein <thomas@intevation.de>
parents:
3369
diff
changeset
|
44 olen = len % 4; |
|
aecea6934fdd
Some additional space/tab cleanups
Thomas Arendsen Hein <thomas@intevation.de>
parents:
3369
diff
changeset
|
45 if (olen) |
|
aecea6934fdd
Some additional space/tab cleanups
Thomas Arendsen Hein <thomas@intevation.de>
parents:
3369
diff
changeset
|
46 olen++; |
|
aecea6934fdd
Some additional space/tab cleanups
Thomas Arendsen Hein <thomas@intevation.de>
parents:
3369
diff
changeset
|
47 olen += len / 4 * 5; |
|
aecea6934fdd
Some additional space/tab cleanups
Thomas Arendsen Hein <thomas@intevation.de>
parents:
3369
diff
changeset
|
48 } |
|
3288
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 | |
|
7190
aecea6934fdd
Some additional space/tab cleanups
Thomas Arendsen Hein <thomas@intevation.de>
parents:
3369
diff
changeset
|
70 if (!pad) |
|
aecea6934fdd
Some additional space/tab cleanups
Thomas Arendsen Hein <thomas@intevation.de>
parents:
3369
diff
changeset
|
71 _PyString_Resize(&out, olen); |
|
3288
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, |
|
7190
aecea6934fdd
Some additional space/tab cleanups
Thomas Arendsen Hein <thomas@intevation.de>
parents:
3369
diff
changeset
|
143 "Encode text in base85.\n\n" |
|
aecea6934fdd
Some additional space/tab cleanups
Thomas Arendsen Hein <thomas@intevation.de>
parents:
3369
diff
changeset
|
144 "If the second parameter is true, pad the result to a multiple of " |
|
aecea6934fdd
Some additional space/tab cleanups
Thomas Arendsen Hein <thomas@intevation.de>
parents:
3369
diff
changeset
|
145 "five characters.\n"}, |
|
3288
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 } |