1 /*

     2  mpatch.c - efficient binary patching for Mercurial

     3 

     4  This implements a patch algorithm that's O(m + nlog n) where m is the

     5  size of the output and n is the number of patches.

     6 

     7  Given a list of binary patches, it unpacks each into a hunk list,

     8  then combines the hunk lists with a treewise recursion to form a

     9  single hunk list. This hunk list is then applied to the original

    10  text.

    11 

    12  The text (or binary) fragments are copied directly from their source

    13  Python objects into a preallocated output string to avoid the

    14  allocation of intermediate Python objects. Working memory is about 2x

    15  the total number of hunks.

    16 

    17  Copyright 2005, 2006 Matt Mackall <mpm@selenic.com>

    18 

    19  This software may be used and distributed according to the terms

    20  of the GNU General Public License, incorporated herein by reference.

    21 */

    22 

    23 #define PY_SSIZE_T_CLEAN

    24 #include <Python.h>

    25 #include <stdlib.h>

    26 #include <string.h>

    27 

    28 #include "util.h"

    29 #include "bitmanipulation.h"

    30 #include "compat.h"

    31 #include "mpatch.h"

    32 

    33 static char mpatch_doc[] = "Efficient binary patching.";

    34 static PyObject *mpatch_Error;

    35 

    36 static void setpyerr(int r)

    37 {

    38 	switch (r) {

    39 	case MPATCH_ERR_NO_MEM:

    40 		PyErr_NoMemory();

    41 		break;

    42 	case MPATCH_ERR_CANNOT_BE_DECODED:

    43 		PyErr_SetString(mpatch_Error, "patch cannot be decoded");

    44 		break;

    45 	case MPATCH_ERR_INVALID_PATCH:

    46 		PyErr_SetString(mpatch_Error, "invalid patch");

    47 		break;

    48 	}

    49 }

    50 

    51 struct mpatch_flist *cpygetitem(void *bins, ssize_t pos)

    52 {

    53 	const char *buffer;

    54 	struct mpatch_flist *res;

    55 	ssize_t blen;

    56 	int r;

    57 

    58 	PyObject *tmp = PyList_GetItem((PyObject*)bins, pos);

    59 	if (!tmp)

    60 		return NULL;

    61 	if (PyObject_AsCharBuffer(tmp, &buffer, (Py_ssize_t*)&blen))

    62 		return NULL;

    63 	if ((r = mpatch_decode(buffer, blen, &res)) < 0) {

    64 		if (!PyErr_Occurred())

    65 			setpyerr(r);

    66 		return NULL;

    67 	}

    68 	return res;

    69 }

    70 

    71 static PyObject *

    72 patches(PyObject *self, PyObject *args)

    73 {

    74 	PyObject *text, *bins, *result;

    75 	struct mpatch_flist *patch;

    76 	const char *in;

    77 	int r = 0;

    78 	char *out;

    79 	Py_ssize_t len, outlen, inlen;

    80 

    81 	if (!PyArg_ParseTuple(args, "OO:mpatch", &text, &bins))

    82 		return NULL;

    83 

    84 	len = PyList_Size(bins);

    85 	if (!len) {

    86 		/* nothing to do */

    87 		Py_INCREF(text);

    88 		return text;

    89 	}

    90 

    91 	if (PyObject_AsCharBuffer(text, &in, &inlen))

    92 		return NULL;

    93 

    94 	patch = mpatch_fold(bins, cpygetitem, 0, len);

    95 	if (!patch) { /* error already set or memory error */

    96 		if (!PyErr_Occurred())

    97 			PyErr_NoMemory();

    98 		return NULL;

    99 	}

   100 

   101 	outlen = mpatch_calcsize(inlen, patch);

   102 	if (outlen < 0) {

   103 		r = (int)outlen;

   104 		result = NULL;

   105 		goto cleanup;

   106 	}

   107 	result = PyBytes_FromStringAndSize(NULL, outlen);

   108 	if (!result) {

   109 		result = NULL;

   110 		goto cleanup;

   111 	}

   112 	out = PyBytes_AsString(result);

   113 	if ((r = mpatch_apply(out, in, inlen, patch)) < 0) {

   114 		Py_DECREF(result);

   115 		result = NULL;

   116 	}

   117 cleanup:

   118 	mpatch_lfree(patch);

   119 	if (!result && !PyErr_Occurred())

   120 		setpyerr(r);

   121 	return result;

   122 }

   123 

   124 /* calculate size of a patched file directly */

   125 static PyObject *

   126 patchedsize(PyObject *self, PyObject *args)

   127 {

   128 	long orig, start, end, len, outlen = 0, last = 0, pos = 0;

   129 	Py_ssize_t patchlen;

   130 	char *bin;

   131 

   132 	if (!PyArg_ParseTuple(args, "ls#", &orig, &bin, &patchlen))

   133 		return NULL;

   134 

   135 	while (pos >= 0 && pos < patchlen) {

   136 		start = getbe32(bin + pos);

   137 		end = getbe32(bin + pos + 4);

   138 		len = getbe32(bin + pos + 8);

   139 		if (start > end)

   140 			break; /* sanity check */

   141 		pos += 12 + len;

   142 		outlen += start - last;

   143 		last = end;

   144 		outlen += len;

   145 	}

   146 

   147 	if (pos != patchlen) {

   148 		if (!PyErr_Occurred())

   149 			PyErr_SetString(mpatch_Error, "patch cannot be decoded");

   150 		return NULL;

   151 	}

   152 

   153 	outlen += orig - last;

   154 	return Py_BuildValue("l", outlen);

   155 }

   156 

   157 static PyMethodDef methods[] = {

   158 	{"patches", patches, METH_VARARGS, "apply a series of patches\n"},

   159 	{"patchedsize", patchedsize, METH_VARARGS, "calculed patched size\n"},

   160 	{NULL, NULL}

   161 };

   162 

   163 #ifdef IS_PY3K

   164 static struct PyModuleDef mpatch_module = {

   165 	PyModuleDef_HEAD_INIT,

   166 	"mpatch",

   167 	mpatch_doc,

   168 	-1,

   169 	methods

   170 };

   171 

   172 PyMODINIT_FUNC PyInit_mpatch(void)

   173 {

   174 	PyObject *m;

   175 

   176 	m = PyModule_Create(&mpatch_module);

   177 	if (m == NULL)

   178 		return NULL;

   179 

   180 	mpatch_Error = PyErr_NewException("mercurial.mpatch.mpatchError",

   181 					  NULL, NULL);

   182 	Py_INCREF(mpatch_Error);

   183 	PyModule_AddObject(m, "mpatchError", mpatch_Error);

   184 

   185 	return m;

   186 }

   187 #else

   188 PyMODINIT_FUNC

   189 initmpatch(void)

   190 {

   191 	Py_InitModule3("mpatch", methods, mpatch_doc);

   192 	mpatch_Error = PyErr_NewException("mercurial.mpatch.mpatchError",

   193 					  NULL, NULL);

   194 }

   195 #endif