Mercurial > public > mercurial-scm > hg

annotate mercurial/cext/bdiff.c @ 36075:ac33dc94e1d5

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
wireprotoserver: add version to SSH protocol names (API) We recently introduced version 2 of the SSH protocol. Like we did for the peer, we will need to differentiate version 1 and 2 of the server. So, we add version components to the advertised name of the protocol handler. Nothing in core looks for the old value. But an extension may. .. api:: SSH protocol handler now advertises its name internally as "ssh-v1" instead of "ssh." Differential Revision: https://phab.mercurial-scm.org/D2092
author Gregory Szorc <gregory.szorc@gmail.com>
date Wed, 07 Feb 2018 20:37:51 -0800
parents b4fdc6177b29
children 29dd37a418aa
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
29541
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
1 /*
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
2 bdiff.c - efficient binary diff extension for Mercurial
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
3
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
4 Copyright 2005, 2006 Matt Mackall <mpm@selenic.com>
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
5
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
6 This software may be used and distributed according to the terms of
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
7 the GNU General Public License, incorporated herein by reference.
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
8
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
9 Based roughly on Python difflib
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
10 */
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
11
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
12 #define PY_SSIZE_T_CLEAN
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
13 #include <Python.h>
34438
b90e8da190da cext: reorder #include
Gregory Szorc <gregory.szorc@gmail.com>
parents: 32369
diff changeset
14 #include <limits.h>
29541
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
15 #include <stdlib.h>
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
16 #include <string.h>
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
17
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
18 #include "bdiff.h"
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
19 #include "bitmanipulation.h"
30170
15635d8b17e0 bdiff: include util.h
Gregory Szorc <gregory.szorc@gmail.com>
parents: 29541
diff changeset
20 #include "util.h"
29541
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
21
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
22 static PyObject *blocks(PyObject *self, PyObject *args)
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
23 {
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
24 PyObject *sa, *sb, *rl = NULL, *m;
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
25 struct bdiff_line *a, *b;
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
26 struct bdiff_hunk l, *h;
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
27 int an, bn, count, pos = 0;
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
28
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
29 l.next = NULL;
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
30
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
31 if (!PyArg_ParseTuple(args, "SS:bdiff", &sa, &sb))
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
32 return NULL;
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
33
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
34 an = bdiff_splitlines(PyBytes_AsString(sa), PyBytes_Size(sa), &a);
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
35 bn = bdiff_splitlines(PyBytes_AsString(sb), PyBytes_Size(sb), &b);
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
36
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
37 if (!a || !b)
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
38 goto nomem;
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
39
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
40 count = bdiff_diff(a, an, b, bn, &l);
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
41 if (count < 0)
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
42 goto nomem;
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
43
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
44 rl = PyList_New(count);
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
45 if (!rl)
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
46 goto nomem;
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
47
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
48 for (h = l.next; h; h = h->next) {
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
49 m = Py_BuildValue("iiii", h->a1, h->a2, h->b1, h->b2);
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
50 PyList_SetItem(rl, pos, m);
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
51 pos++;
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
52 }
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
53
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
54 nomem:
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
55 free(a);
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
56 free(b);
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
57 bdiff_freehunks(l.next);
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
58 return rl ? rl : PyErr_NoMemory();
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
59 }
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
60
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
61 static PyObject *bdiff(PyObject *self, PyObject *args)
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
62 {
30561
7c0c722d568d bdiff: early pruning of common prefix before doing expensive computations
Mads Kiilerich <madski@unity3d.com>
parents: 30170
diff changeset
63 char *sa, *sb, *rb, *ia, *ib;
29541
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
64 PyObject *result = NULL;
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
65 struct bdiff_line *al, *bl;
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
66 struct bdiff_hunk l, *h;
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
67 int an, bn, count;
30561
7c0c722d568d bdiff: early pruning of common prefix before doing expensive computations
Mads Kiilerich <madski@unity3d.com>
parents: 30170
diff changeset
68 Py_ssize_t len = 0, la, lb, li = 0, lcommon = 0, lmax;
29541
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
69 PyThreadState *_save;
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
70
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
71 l.next = NULL;
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
72
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
73 if (!PyArg_ParseTuple(args, "s#s#:bdiff", &sa, &la, &sb, &lb))
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
74 return NULL;
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
75
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
76 if (la > UINT_MAX || lb > UINT_MAX) {
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
77 PyErr_SetString(PyExc_ValueError, "bdiff inputs too large");
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
78 return NULL;
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
79 }
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
80
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
81 _save = PyEval_SaveThread();
30561
7c0c722d568d bdiff: early pruning of common prefix before doing expensive computations
Mads Kiilerich <madski@unity3d.com>
parents: 30170
diff changeset
82
7c0c722d568d bdiff: early pruning of common prefix before doing expensive computations
Mads Kiilerich <madski@unity3d.com>
parents: 30170
diff changeset
83 lmax = la > lb ? lb : la;
36055
b4fdc6177b29 bdiff: add to clang-format oversight
Augie Fackler <augie@google.com>
parents: 34438
diff changeset
84 for (ia = sa, ib = sb; li < lmax && *ia == *ib; ++li, ++ia, ++ib)
30561
7c0c722d568d bdiff: early pruning of common prefix before doing expensive computations
Mads Kiilerich <madski@unity3d.com>
parents: 30170
diff changeset
85 if (*ia == '\n')
7c0c722d568d bdiff: early pruning of common prefix before doing expensive computations
Mads Kiilerich <madski@unity3d.com>
parents: 30170
diff changeset
86 lcommon = li + 1;
7c0c722d568d bdiff: early pruning of common prefix before doing expensive computations
Mads Kiilerich <madski@unity3d.com>
parents: 30170
diff changeset
87 /* we can almost add: if (li == lmax) lcommon = li; */
7c0c722d568d bdiff: early pruning of common prefix before doing expensive computations
Mads Kiilerich <madski@unity3d.com>
parents: 30170
diff changeset
88
7c0c722d568d bdiff: early pruning of common prefix before doing expensive computations
Mads Kiilerich <madski@unity3d.com>
parents: 30170
diff changeset
89 an = bdiff_splitlines(sa + lcommon, la - lcommon, &al);
7c0c722d568d bdiff: early pruning of common prefix before doing expensive computations
Mads Kiilerich <madski@unity3d.com>
parents: 30170
diff changeset
90 bn = bdiff_splitlines(sb + lcommon, lb - lcommon, &bl);
29541
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
91 if (!al || !bl)
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
92 goto nomem;
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
93
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
94 count = bdiff_diff(al, an, bl, bn, &l);
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
95 if (count < 0)
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
96 goto nomem;
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
97
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
98 /* calculate length of output */
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
99 la = lb = 0;
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
100 for (h = l.next; h; h = h->next) {
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
101 if (h->a1 != la || h->b1 != lb)
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
102 len += 12 + bl[h->b1].l - bl[lb].l;
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
103 la = h->a2;
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
104 lb = h->b2;
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
105 }
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
106 PyEval_RestoreThread(_save);
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
107 _save = NULL;
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
108
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
109 result = PyBytes_FromStringAndSize(NULL, len);
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
110
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
111 if (!result)
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
112 goto nomem;
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
113
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
114 /* build binary patch */
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
115 rb = PyBytes_AsString(result);
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
116 la = lb = 0;
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
117
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
118 for (h = l.next; h; h = h->next) {
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
119 if (h->a1 != la || h->b1 != lb) {
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
120 len = bl[h->b1].l - bl[lb].l;
30561
7c0c722d568d bdiff: early pruning of common prefix before doing expensive computations
Mads Kiilerich <madski@unity3d.com>
parents: 30170
diff changeset
121 putbe32((uint32_t)(al[la].l + lcommon - al->l), rb);
36055
b4fdc6177b29 bdiff: add to clang-format oversight
Augie Fackler <augie@google.com>
parents: 34438
diff changeset
122 putbe32((uint32_t)(al[h->a1].l + lcommon - al->l),
b4fdc6177b29 bdiff: add to clang-format oversight
Augie Fackler <augie@google.com>
parents: 34438
diff changeset
123 rb + 4);
29541
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
124 putbe32((uint32_t)len, rb + 8);
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
125 memcpy(rb + 12, bl[lb].l, len);
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
126 rb += 12 + len;
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
127 }
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
128 la = h->a2;
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
129 lb = h->b2;
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
130 }
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
131
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
132 nomem:
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
133 if (_save)
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
134 PyEval_RestoreThread(_save);
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
135 free(al);
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
136 free(bl);
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
137 bdiff_freehunks(l.next);
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
138 return result ? result : PyErr_NoMemory();
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
139 }
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
140
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
141 /*
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
142 * If allws != 0, remove all whitespace (' ', \t and \r). Otherwise,
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
143 * reduce whitespace sequences to a single space and trim remaining whitespace
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
144 * from end of lines.
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
145 */
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
146 static PyObject *fixws(PyObject *self, PyObject *args)
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
147 {
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
148 PyObject *s, *result = NULL;
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
149 char allws, c;
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
150 const char *r;
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
151 Py_ssize_t i, rlen, wlen = 0;
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
152 char *w;
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
153
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
154 if (!PyArg_ParseTuple(args, "Sb:fixws", &s, &allws))
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
155 return NULL;
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
156 r = PyBytes_AsString(s);
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
157 rlen = PyBytes_Size(s);
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
158
31467
08ecec297521 bdiff: use Python memory allocator in fixws
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30561
diff changeset
159 w = (char *)PyMem_Malloc(rlen ? rlen : 1);
29541
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
160 if (!w)
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
161 goto nomem;
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
162
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
163 for (i = 0; i != rlen; i++) {
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
164 c = r[i];
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
165 if (c == ' ' || c == '\t' || c == '\r') {
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
166 if (!allws && (wlen == 0 || w[wlen - 1] != ' '))
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
167 w[wlen++] = ' ';
36055
b4fdc6177b29 bdiff: add to clang-format oversight
Augie Fackler <augie@google.com>
parents: 34438
diff changeset
168 } else if (c == '\n' && !allws && wlen > 0 &&
b4fdc6177b29 bdiff: add to clang-format oversight
Augie Fackler <augie@google.com>
parents: 34438
diff changeset
169 w[wlen - 1] == ' ') {
29541
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
170 w[wlen - 1] = '\n';
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
171 } else {
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
172 w[wlen++] = c;
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
173 }
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
174 }
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
175
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
176 result = PyBytes_FromStringAndSize(w, wlen);
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
177
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
178 nomem:
31467
08ecec297521 bdiff: use Python memory allocator in fixws
Gregory Szorc <gregory.szorc@gmail.com>
parents: 30561
diff changeset
179 PyMem_Free(w);
29541
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
180 return result ? result : PyErr_NoMemory();
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
181 }
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
182
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
183 static char mdiff_doc[] = "Efficient binary diff.";
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
184
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
185 static PyMethodDef methods[] = {
36055
b4fdc6177b29 bdiff: add to clang-format oversight
Augie Fackler <augie@google.com>
parents: 34438
diff changeset
186 {"bdiff", bdiff, METH_VARARGS, "calculate a binary diff\n"},
b4fdc6177b29 bdiff: add to clang-format oversight
Augie Fackler <augie@google.com>
parents: 34438
diff changeset
187 {"blocks", blocks, METH_VARARGS, "find a list of matching lines\n"},
b4fdc6177b29 bdiff: add to clang-format oversight
Augie Fackler <augie@google.com>
parents: 34438
diff changeset
188 {"fixws", fixws, METH_VARARGS, "normalize diff whitespaces\n"},
b4fdc6177b29 bdiff: add to clang-format oversight
Augie Fackler <augie@google.com>
parents: 34438
diff changeset
189 {NULL, NULL},
29541
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
190 };
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
191
32355
4195b84940e9 bdiff: add version to help detect breaking binary changes
Jun Wu <quark@fb.com>
parents: 31467
diff changeset
192 static const int version = 1;
4195b84940e9 bdiff: add version to help detect breaking binary changes
Jun Wu <quark@fb.com>
parents: 31467
diff changeset
193
29541
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
194 #ifdef IS_PY3K
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
195 static struct PyModuleDef bdiff_module = {
36055
b4fdc6177b29 bdiff: add to clang-format oversight
Augie Fackler <augie@google.com>
parents: 34438
diff changeset
196 PyModuleDef_HEAD_INIT, "bdiff", mdiff_doc, -1, methods,
29541
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
197 };
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
198
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
199 PyMODINIT_FUNC PyInit_bdiff(void)
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
200 {
32355
4195b84940e9 bdiff: add version to help detect breaking binary changes
Jun Wu <quark@fb.com>
parents: 31467
diff changeset
201 PyObject *m;
4195b84940e9 bdiff: add version to help detect breaking binary changes
Jun Wu <quark@fb.com>
parents: 31467
diff changeset
202 m = PyModule_Create(&bdiff_module);
4195b84940e9 bdiff: add version to help detect breaking binary changes
Jun Wu <quark@fb.com>
parents: 31467
diff changeset
203 PyModule_AddIntConstant(m, "version", version);
4195b84940e9 bdiff: add version to help detect breaking binary changes
Jun Wu <quark@fb.com>
parents: 31467
diff changeset
204 return m;
29541
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
205 }
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
206 #else
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
207 PyMODINIT_FUNC initbdiff(void)
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
208 {
32355
4195b84940e9 bdiff: add version to help detect breaking binary changes
Jun Wu <quark@fb.com>
parents: 31467
diff changeset
209 PyObject *m;
4195b84940e9 bdiff: add version to help detect breaking binary changes
Jun Wu <quark@fb.com>
parents: 31467
diff changeset
210 m = Py_InitModule3("bdiff", methods, mdiff_doc);
4195b84940e9 bdiff: add version to help detect breaking binary changes
Jun Wu <quark@fb.com>
parents: 31467
diff changeset
211 PyModule_AddIntConstant(m, "version", version);
29541
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
212 }
9631ff5ebbeb bdiff: split bdiff into cpy-aware and cpy-agnostic part
Maciej Fijalkowski <fijall@gmail.com>
parents:
diff changeset
213 #endif