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 PyObject *

    37 patches(PyObject *self, PyObject *args)

    38 {

    39 	PyObject *text, *bins, *result;

    40 	struct mpatch_flist *patch;

    41 	const char *in;

    42 	char *out;

    43 	Py_ssize_t len, outlen, inlen;

    44 

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

    46 		return NULL;

    47 

    48 	len = PyList_Size(bins);

    49 	if (!len) {

    50 		/* nothing to do */

    51 		Py_INCREF(text);

    52 		return text;

    53 	}

    54 

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

    56 		return NULL;

    57 

    58 	patch = mpatch_fold(bins, 0, len);

    59 	if (!patch)

    60 		return NULL;

    61 

    62 	outlen = mpatch_calcsize(inlen, patch);

    63 	if (outlen < 0) {

    64 		result = NULL;

    65 		goto cleanup;

    66 	}

    67 	result = PyBytes_FromStringAndSize(NULL, outlen);

    68 	if (!result) {

    69 		result = NULL;

    70 		goto cleanup;

    71 	}

    72 	out = PyBytes_AsString(result);

    73 	if (!mpatch_apply(out, in, inlen, patch)) {

    74 		Py_DECREF(result);

    75 		result = NULL;

    76 	}

    77 cleanup:

    78 	mpatch_lfree(patch);

    79 	return result;

    80 }

    81 

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

    83 static PyObject *

    84 patchedsize(PyObject *self, PyObject *args)

    85 {

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

    87 	Py_ssize_t patchlen;

    88 	char *bin;

    89 

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

    91 		return NULL;

    92 

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

    94 		start = getbe32(bin + pos);

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

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

    97 		if (start > end)

    98 			break; /* sanity check */

    99 		pos += 12 + len;

   100 		outlen += start - last;

   101 		last = end;

   102 		outlen += len;

   103 	}

   104 

   105 	if (pos != patchlen) {

   106 		if (!PyErr_Occurred())

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

   108 		return NULL;

   109 	}

   110 

   111 	outlen += orig - last;

   112 	return Py_BuildValue("l", outlen);

   113 }

   114 

   115 static PyMethodDef methods[] = {

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

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

   118 	{NULL, NULL}

   119 };

   120 

   121 #ifdef IS_PY3K

   122 static struct PyModuleDef mpatch_module = {

   123 	PyModuleDef_HEAD_INIT,

   124 	"mpatch",

   125 	mpatch_doc,

   126 	-1,

   127 	methods

   128 };

   129 

   130 PyMODINIT_FUNC PyInit_mpatch(void)

   131 {

   132 	PyObject *m;

   133 

   134 	m = PyModule_Create(&mpatch_module);

   135 	if (m == NULL)

   136 		return NULL;

   137 

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

   139 					  NULL, NULL);

   140 	Py_INCREF(mpatch_Error);

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

   142 

   143 	return m;

   144 }

   145 #else

   146 PyMODINIT_FUNC

   147 initmpatch(void)

   148 {

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

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

   151 					  NULL, NULL);

   152 }

   153 #endif