mercurial/mpatch.c
author Brendan Cully <brendan@kublai.com>
Mon, 12 Mar 2007 13:58:06 -0700
changeset 4201 7e95381a9f1e
parent 4073 95ffa36d1d2a
child 4377 4759da3e4dc8
permissions -rw-r--r--
Strip [PATCH...] from message subject when importing patches
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
     1
/*
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
     2
 mpatch.c - efficient binary patching for Mercurial
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
     3
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
     4
 This implements a patch algorithm that's O(m + nlog n) where m is the
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
     5
 size of the output and n is the number of patches.
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
     6
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
     7
 Given a list of binary patches, it unpacks each into a hunk list,
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
     8
 then combines the hunk lists with a treewise recursion to form a
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
     9
 single hunk list. This hunk list is then applied to the original
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    10
 text.
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    11
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    12
 The text (or binary) fragments are copied directly from their source
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    13
 Python objects into a preallocated output string to avoid the
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    14
 allocation of intermediate Python objects. Working memory is about 2x
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    15
 the total number of hunks.
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    16
2859
345bac2bc4ec update copyrights.
Vadim Gelfer <vadim.gelfer@gmail.com>
parents: 2543
diff changeset
    17
 Copyright 2005, 2006 Matt Mackall <mpm@selenic.com>
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    18
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    19
 This software may be used and distributed according to the terms
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    20
 of the GNU General Public License, incorporated herein by reference.
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    21
*/
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    22
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    23
#include <Python.h>
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    24
#include <stdlib.h>
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    25
#include <string.h>
2468
1ac0574f1768 mac os x: fixes for 10.2 from chris monson <monpublic@gmail.com>
Vadim Gelfer <vadim.gelfer@gmail.com>
parents: 2083
diff changeset
    26
410
7c678976df3e Make mpatch.c compilable under the other `OS'
mpm@selenic.com
parents: 384
diff changeset
    27
#ifdef _WIN32
2468
1ac0574f1768 mac os x: fixes for 10.2 from chris monson <monpublic@gmail.com>
Vadim Gelfer <vadim.gelfer@gmail.com>
parents: 2083
diff changeset
    28
# ifdef _MSC_VER
1ac0574f1768 mac os x: fixes for 10.2 from chris monson <monpublic@gmail.com>
Vadim Gelfer <vadim.gelfer@gmail.com>
parents: 2083
diff changeset
    29
/* msvc 6.0 has problems */
1ac0574f1768 mac os x: fixes for 10.2 from chris monson <monpublic@gmail.com>
Vadim Gelfer <vadim.gelfer@gmail.com>
parents: 2083
diff changeset
    30
#  define inline __inline
551
b460a2fd8bb7 [PATCH] bdiff/mpatch under MSVC
mpm@selenic.com
parents: 510
diff changeset
    31
typedef unsigned long uint32_t;
2468
1ac0574f1768 mac os x: fixes for 10.2 from chris monson <monpublic@gmail.com>
Vadim Gelfer <vadim.gelfer@gmail.com>
parents: 2083
diff changeset
    32
# else
1ac0574f1768 mac os x: fixes for 10.2 from chris monson <monpublic@gmail.com>
Vadim Gelfer <vadim.gelfer@gmail.com>
parents: 2083
diff changeset
    33
#  include <stdint.h>
1ac0574f1768 mac os x: fixes for 10.2 from chris monson <monpublic@gmail.com>
Vadim Gelfer <vadim.gelfer@gmail.com>
parents: 2083
diff changeset
    34
# endif
411
9e9f7ab43ce2 Add 'other OS' bits to bdiff.c / style cleanups
mpm@selenic.com
parents: 410
diff changeset
    35
static uint32_t ntohl(uint32_t x)
9e9f7ab43ce2 Add 'other OS' bits to bdiff.c / style cleanups
mpm@selenic.com
parents: 410
diff changeset
    36
{
9e9f7ab43ce2 Add 'other OS' bits to bdiff.c / style cleanups
mpm@selenic.com
parents: 410
diff changeset
    37
	return ((x & 0x000000ffUL) << 24) |
9e9f7ab43ce2 Add 'other OS' bits to bdiff.c / style cleanups
mpm@selenic.com
parents: 410
diff changeset
    38
		((x & 0x0000ff00UL) <<  8) |
9e9f7ab43ce2 Add 'other OS' bits to bdiff.c / style cleanups
mpm@selenic.com
parents: 410
diff changeset
    39
		((x & 0x00ff0000UL) >>  8) |
9e9f7ab43ce2 Add 'other OS' bits to bdiff.c / style cleanups
mpm@selenic.com
parents: 410
diff changeset
    40
		((x & 0xff000000UL) >> 24);
410
7c678976df3e Make mpatch.c compilable under the other `OS'
mpm@selenic.com
parents: 384
diff changeset
    41
}
7c678976df3e Make mpatch.c compilable under the other `OS'
mpm@selenic.com
parents: 384
diff changeset
    42
#else
2468
1ac0574f1768 mac os x: fixes for 10.2 from chris monson <monpublic@gmail.com>
Vadim Gelfer <vadim.gelfer@gmail.com>
parents: 2083
diff changeset
    43
/* not windows */
1ac0574f1768 mac os x: fixes for 10.2 from chris monson <monpublic@gmail.com>
Vadim Gelfer <vadim.gelfer@gmail.com>
parents: 2083
diff changeset
    44
# include <sys/types.h>
4073
95ffa36d1d2a BeOS compatibility support
Andrew Bachmann <andrewbachmann@gmail.com>
parents: 3138
diff changeset
    45
# ifdef __BEOS__
95ffa36d1d2a BeOS compatibility support
Andrew Bachmann <andrewbachmann@gmail.com>
parents: 3138
diff changeset
    46
#  include <ByteOrder.h>
95ffa36d1d2a BeOS compatibility support
Andrew Bachmann <andrewbachmann@gmail.com>
parents: 3138
diff changeset
    47
# else
95ffa36d1d2a BeOS compatibility support
Andrew Bachmann <andrewbachmann@gmail.com>
parents: 3138
diff changeset
    48
#  include <arpa/inet.h>
95ffa36d1d2a BeOS compatibility support
Andrew Bachmann <andrewbachmann@gmail.com>
parents: 3138
diff changeset
    49
# endif
2543
860e9c83fc59 Include inttypes.h instead of stdint.h (fixes issue299)
Thomas Arendsen Hein <thomas@intevation.de>
parents: 2468
diff changeset
    50
# include <inttypes.h>
410
7c678976df3e Make mpatch.c compilable under the other `OS'
mpm@selenic.com
parents: 384
diff changeset
    51
#endif
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    52
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    53
static char mpatch_doc[] = "Efficient binary patching.";
1722
681c5c211b92 catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 597
diff changeset
    54
static PyObject *mpatch_Error;
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    55
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    56
struct frag {
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    57
	int start, end, len;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    58
	char *data;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    59
};
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    60
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    61
struct flist {
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    62
	struct frag *base, *head, *tail;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    63
};
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    64
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    65
static struct flist *lalloc(int size)
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    66
{
128
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
    67
	struct flist *a = NULL;
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    68
3138
cc856c4d91ca mpatch: Fix for malloc corner case on AIX
Matt Mackall <mpm@selenic.com>
parents: 2859
diff changeset
    69
	if (size < 1)
cc856c4d91ca mpatch: Fix for malloc corner case on AIX
Matt Mackall <mpm@selenic.com>
parents: 2859
diff changeset
    70
		size = 1;
cc856c4d91ca mpatch: Fix for malloc corner case on AIX
Matt Mackall <mpm@selenic.com>
parents: 2859
diff changeset
    71
1978
10606ee61107 do proper typecasting on malloc() and calloc() calls
TK Soh <teekaysoh@yahoo.com>
parents: 1746
diff changeset
    72
	a = (struct flist *)malloc(sizeof(struct flist));
128
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
    73
	if (a) {
1978
10606ee61107 do proper typecasting on malloc() and calloc() calls
TK Soh <teekaysoh@yahoo.com>
parents: 1746
diff changeset
    74
		a->base = (struct frag *)malloc(sizeof(struct frag) * size);
2048
8f9660c568b8 Set correct exception for another possible malloc error in mpatch.c
Thomas Arendsen Hein <thomas@intevation.de>
parents: 1978
diff changeset
    75
		if (a->base) {
128
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
    76
			a->head = a->tail = a->base;
2048
8f9660c568b8 Set correct exception for another possible malloc error in mpatch.c
Thomas Arendsen Hein <thomas@intevation.de>
parents: 1978
diff changeset
    77
			return a;
8f9660c568b8 Set correct exception for another possible malloc error in mpatch.c
Thomas Arendsen Hein <thomas@intevation.de>
parents: 1978
diff changeset
    78
		}
8f9660c568b8 Set correct exception for another possible malloc error in mpatch.c
Thomas Arendsen Hein <thomas@intevation.de>
parents: 1978
diff changeset
    79
		free(a);
8f9660c568b8 Set correct exception for another possible malloc error in mpatch.c
Thomas Arendsen Hein <thomas@intevation.de>
parents: 1978
diff changeset
    80
		a = NULL;
128
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
    81
	}
1722
681c5c211b92 catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 597
diff changeset
    82
	if (!PyErr_Occurred())
681c5c211b92 catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 597
diff changeset
    83
		PyErr_NoMemory();
681c5c211b92 catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 597
diff changeset
    84
	return NULL;
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    85
}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    86
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    87
static void lfree(struct flist *a)
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    88
{
128
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
    89
	if (a) {
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
    90
		free(a->base);
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
    91
		free(a);
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
    92
	}
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    93
}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    94
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    95
static int lsize(struct flist *a)
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    96
{
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    97
	return a->tail - a->head;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    98
}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
    99
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   100
/* move hunks in source that are less cut to dest, compensating
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   101
   for changes in offset. the last hunk may be split if necessary.
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   102
*/
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   103
static int gather(struct flist *dest, struct flist *src, int cut, int offset)
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   104
{
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   105
	struct frag *d = dest->tail, *s = src->head;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   106
	int postend, c, l;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   107
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   108
	while (s != src->tail) {
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   109
		if (s->start + offset >= cut)
82
7ed96baa7caa Gotos are embarrassing.
mpm@selenic.com
parents: 72
diff changeset
   110
			break; /* we've gone far enough */
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   111
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   112
		postend = offset + s->start + s->len;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   113
		if (postend <= cut) {
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   114
			/* save this hunk */
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   115
			offset += s->start + s->len - s->end;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   116
			*d++ = *s++;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   117
		}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   118
		else {
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   119
			/* break up this hunk */
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   120
			c = cut - offset;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   121
			if (s->end < c)
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   122
				c = s->end;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   123
			l = cut - offset - s->start;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   124
			if (s->len < l)
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   125
				l = s->len;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   126
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   127
			offset += s->start + l - c;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   128
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   129
			d->start = s->start;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   130
			d->end = c;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   131
			d->len = l;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   132
			d->data = s->data;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   133
			d++;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   134
			s->start = c;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   135
			s->len = s->len - l;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   136
			s->data = s->data + l;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   137
82
7ed96baa7caa Gotos are embarrassing.
mpm@selenic.com
parents: 72
diff changeset
   138
			break;
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   139
		}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   140
	}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   141
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   142
	dest->tail = d;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   143
	src->head = s;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   144
	return offset;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   145
}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   146
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   147
/* like gather, but with no output list */
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   148
static int discard(struct flist *src, int cut, int offset)
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   149
{
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   150
	struct frag *s = src->head;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   151
	int postend, c, l;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   152
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   153
	while (s != src->tail) {
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   154
		if (s->start + offset >= cut)
82
7ed96baa7caa Gotos are embarrassing.
mpm@selenic.com
parents: 72
diff changeset
   155
			break;
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   156
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   157
		postend = offset + s->start + s->len;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   158
		if (postend <= cut) {
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   159
			offset += s->start + s->len - s->end;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   160
			s++;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   161
		}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   162
		else {
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   163
			c = cut - offset;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   164
			if (s->end < c)
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   165
				c = s->end;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   166
			l = cut - offset - s->start;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   167
			if (s->len < l)
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   168
				l = s->len;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   169
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   170
			offset += s->start + l - c;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   171
			s->start = c;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   172
			s->len = s->len - l;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   173
			s->data = s->data + l;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   174
82
7ed96baa7caa Gotos are embarrassing.
mpm@selenic.com
parents: 72
diff changeset
   175
			break;
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   176
		}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   177
	}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   178
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   179
	src->head = s;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   180
	return offset;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   181
}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   182
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   183
/* combine hunk lists a and b, while adjusting b for offset changes in a/
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   184
   this deletes a and b and returns the resultant list. */
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   185
static struct flist *combine(struct flist *a, struct flist *b)
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   186
{
128
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
   187
	struct flist *c = NULL;
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
   188
	struct frag *bh, *ct;
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   189
	int offset = 0, post;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   190
128
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
   191
	if (a && b)
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
   192
		c = lalloc((lsize(a) + lsize(b)) * 2);
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
   193
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
   194
	if (c) {
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   195
128
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
   196
		for (bh = b->head; bh != b->tail; bh++) {
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
   197
			/* save old hunks */
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
   198
			offset = gather(c, a, bh->start, offset);
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   199
128
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
   200
			/* discard replaced hunks */
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
   201
			post = discard(a, bh->end, offset);
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   202
128
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
   203
			/* insert new hunk */
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
   204
			ct = c->tail;
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
   205
			ct->start = bh->start - offset;
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
   206
			ct->end = bh->end - post;
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
   207
			ct->len = bh->len;
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
   208
			ct->data = bh->data;
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
   209
			c->tail++;
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
   210
			offset = post;
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
   211
		}
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
   212
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
   213
		/* hold on to tail from a */
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
   214
		memcpy(c->tail, a->head, sizeof(struct frag) * lsize(a));
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
   215
		c->tail += lsize(a);
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   216
	}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   217
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   218
	lfree(a);
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   219
	lfree(b);
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   220
	return c;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   221
}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   222
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   223
/* decode a binary patch into a hunk list */
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   224
static struct flist *decode(char *bin, int len)
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   225
{
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   226
	struct flist *l;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   227
	struct frag *lt;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   228
	char *end = bin + len;
384
a29decbf7475 mpatch: attempt to handle unpack alignment issues on Solaris
mpm@selenic.com
parents: 282
diff changeset
   229
	char decode[12]; /* for dealing with alignment issues */
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   230
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   231
	/* assume worst case size, we won't have many of these lists */
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   232
	l = lalloc(len / 12);
1722
681c5c211b92 catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 597
diff changeset
   233
	if (!l)
681c5c211b92 catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 597
diff changeset
   234
		return NULL;
681c5c211b92 catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 597
diff changeset
   235
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   236
	lt = l->tail;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   237
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   238
	while (bin < end) {
384
a29decbf7475 mpatch: attempt to handle unpack alignment issues on Solaris
mpm@selenic.com
parents: 282
diff changeset
   239
		memcpy(decode, bin, 12);
a29decbf7475 mpatch: attempt to handle unpack alignment issues on Solaris
mpm@selenic.com
parents: 282
diff changeset
   240
		lt->start = ntohl(*(uint32_t *)decode);
a29decbf7475 mpatch: attempt to handle unpack alignment issues on Solaris
mpm@selenic.com
parents: 282
diff changeset
   241
		lt->end = ntohl(*(uint32_t *)(decode + 4));
a29decbf7475 mpatch: attempt to handle unpack alignment issues on Solaris
mpm@selenic.com
parents: 282
diff changeset
   242
		lt->len = ntohl(*(uint32_t *)(decode + 8));
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   243
		lt->data = bin + 12;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   244
		bin += 12 + lt->len;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   245
		lt++;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   246
	}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   247
1722
681c5c211b92 catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 597
diff changeset
   248
	if (bin != end) {
681c5c211b92 catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 597
diff changeset
   249
		if (!PyErr_Occurred())
681c5c211b92 catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 597
diff changeset
   250
			PyErr_SetString(mpatch_Error, "patch cannot be decoded");
681c5c211b92 catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 597
diff changeset
   251
		lfree(l);
681c5c211b92 catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 597
diff changeset
   252
		return NULL;
681c5c211b92 catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 597
diff changeset
   253
	}
681c5c211b92 catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 597
diff changeset
   254
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   255
	l->tail = lt;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   256
	return l;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   257
}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   258
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   259
/* calculate the size of resultant text */
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   260
static int calcsize(int len, struct flist *l)
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   261
{
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   262
	int outlen = 0, last = 0;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   263
	struct frag *f = l->head;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   264
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   265
	while (f != l->tail) {
1722
681c5c211b92 catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 597
diff changeset
   266
		if (f->start < last || f->end > len) {
681c5c211b92 catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 597
diff changeset
   267
			if (!PyErr_Occurred())
681c5c211b92 catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 597
diff changeset
   268
				PyErr_SetString(mpatch_Error,
681c5c211b92 catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 597
diff changeset
   269
				                "invalid patch");
681c5c211b92 catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 597
diff changeset
   270
			return -1;
681c5c211b92 catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 597
diff changeset
   271
		}
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   272
		outlen += f->start - last;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   273
		last = f->end;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   274
		outlen += f->len;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   275
		f++;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   276
	}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   277
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   278
	outlen += len - last;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   279
	return outlen;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   280
}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   281
1722
681c5c211b92 catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 597
diff changeset
   282
static int apply(char *buf, char *orig, int len, struct flist *l)
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   283
{
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   284
	struct frag *f = l->head;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   285
	int last = 0;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   286
	char *p = buf;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   287
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   288
	while (f != l->tail) {
1722
681c5c211b92 catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 597
diff changeset
   289
		if (f->start < last || f->end > len) {
681c5c211b92 catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 597
diff changeset
   290
			if (!PyErr_Occurred())
681c5c211b92 catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 597
diff changeset
   291
				PyErr_SetString(mpatch_Error,
681c5c211b92 catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 597
diff changeset
   292
				                "invalid patch");
681c5c211b92 catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 597
diff changeset
   293
			return 0;
681c5c211b92 catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 597
diff changeset
   294
		}
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   295
		memcpy(p, orig + last, f->start - last);
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   296
		p += f->start - last;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   297
		memcpy(p, f->data, f->len);
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   298
		last = f->end;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   299
		p += f->len;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   300
		f++;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   301
	}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   302
	memcpy(p, orig + last, len - last);
1722
681c5c211b92 catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 597
diff changeset
   303
	return 1;
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   304
}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   305
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   306
/* recursively generate a patch of all bins between start and end */
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   307
static struct flist *fold(PyObject *bins, int start, int end)
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   308
{
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   309
	int len;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   310
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   311
	if (start + 1 == end) {
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   312
		/* trivial case, output a decoded list */
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   313
		PyObject *tmp = PyList_GetItem(bins, start);
128
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
   314
		if (!tmp)
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
   315
			return NULL;
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   316
		return decode(PyString_AsString(tmp), PyString_Size(tmp));
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   317
	}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   318
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   319
	/* divide and conquer, memory management is elsewhere */
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   320
	len = (end - start) / 2;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   321
	return combine(fold(bins, start, start + len),
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   322
		       fold(bins, start + len, end));
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   323
}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   324
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   325
static PyObject *
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   326
patches(PyObject *self, PyObject *args)
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   327
{
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   328
	PyObject *text, *bins, *result;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   329
	struct flist *patch;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   330
	char *in, *out;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   331
	int len, outlen;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   332
128
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
   333
	if (!PyArg_ParseTuple(args, "SO:mpatch", &text, &bins))
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   334
		return NULL;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   335
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   336
	len = PyList_Size(bins);
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   337
	if (!len) {
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   338
		/* nothing to do */
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   339
		Py_INCREF(text);
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   340
		return text;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   341
	}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   342
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   343
	patch = fold(bins, 0, len);
128
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
   344
	if (!patch)
1722
681c5c211b92 catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 597
diff changeset
   345
		return NULL;
128
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
   346
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   347
	outlen = calcsize(PyString_Size(text), patch);
1722
681c5c211b92 catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 597
diff changeset
   348
	if (outlen < 0) {
681c5c211b92 catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 597
diff changeset
   349
		result = NULL;
681c5c211b92 catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 597
diff changeset
   350
		goto cleanup;
681c5c211b92 catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 597
diff changeset
   351
	}
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   352
	result = PyString_FromStringAndSize(NULL, outlen);
1722
681c5c211b92 catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 597
diff changeset
   353
	if (!result) {
681c5c211b92 catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 597
diff changeset
   354
		result = NULL;
681c5c211b92 catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 597
diff changeset
   355
		goto cleanup;
128
d6afb6dbf9f2 Add safety checking to mpatch
mpm@selenic.com
parents: 82
diff changeset
   356
	}
1722
681c5c211b92 catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 597
diff changeset
   357
	in = PyString_AsString(text);
681c5c211b92 catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 597
diff changeset
   358
	out = PyString_AsString(result);
681c5c211b92 catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 597
diff changeset
   359
	if (!apply(out, in, PyString_Size(text), patch)) {
681c5c211b92 catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 597
diff changeset
   360
		Py_DECREF(result);
681c5c211b92 catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 597
diff changeset
   361
		result = NULL;
681c5c211b92 catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 597
diff changeset
   362
	}
681c5c211b92 catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 597
diff changeset
   363
cleanup:
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   364
	lfree(patch);
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   365
	return result;
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   366
}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   367
2078
441ea218414e Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents: 1978
diff changeset
   368
/* calculate size of a patched file directly */
441ea218414e Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents: 1978
diff changeset
   369
static PyObject *
441ea218414e Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents: 1978
diff changeset
   370
patchedsize(PyObject *self, PyObject *args)
441ea218414e Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents: 1978
diff changeset
   371
{
441ea218414e Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents: 1978
diff changeset
   372
	long orig, start, end, len, outlen = 0, last = 0;
441ea218414e Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents: 1978
diff changeset
   373
	int patchlen;
441ea218414e Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents: 1978
diff changeset
   374
	char *bin, *binend;
441ea218414e Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents: 1978
diff changeset
   375
	char decode[12]; /* for dealing with alignment issues */
441ea218414e Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents: 1978
diff changeset
   376
441ea218414e Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents: 1978
diff changeset
   377
	if (!PyArg_ParseTuple(args, "ls#", &orig, &bin, &patchlen))
441ea218414e Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents: 1978
diff changeset
   378
		return NULL;
441ea218414e Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents: 1978
diff changeset
   379
441ea218414e Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents: 1978
diff changeset
   380
	binend = bin + patchlen;
441ea218414e Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents: 1978
diff changeset
   381
441ea218414e Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents: 1978
diff changeset
   382
	while (bin < binend) {
441ea218414e Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents: 1978
diff changeset
   383
		memcpy(decode, bin, 12);
441ea218414e Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents: 1978
diff changeset
   384
		start = ntohl(*(uint32_t *)decode);
441ea218414e Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents: 1978
diff changeset
   385
		end = ntohl(*(uint32_t *)(decode + 4));
441ea218414e Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents: 1978
diff changeset
   386
		len = ntohl(*(uint32_t *)(decode + 8));
441ea218414e Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents: 1978
diff changeset
   387
		bin += 12 + len;
441ea218414e Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents: 1978
diff changeset
   388
		outlen += start - last;
441ea218414e Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents: 1978
diff changeset
   389
		last = end;
441ea218414e Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents: 1978
diff changeset
   390
		outlen += len;
441ea218414e Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents: 1978
diff changeset
   391
	}
441ea218414e Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents: 1978
diff changeset
   392
441ea218414e Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents: 1978
diff changeset
   393
	if (bin != binend) {
441ea218414e Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents: 1978
diff changeset
   394
		if (!PyErr_Occurred())
441ea218414e Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents: 1978
diff changeset
   395
			PyErr_SetString(mpatch_Error, "patch cannot be decoded");
441ea218414e Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents: 1978
diff changeset
   396
		return NULL;
441ea218414e Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents: 1978
diff changeset
   397
	}
441ea218414e Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents: 1978
diff changeset
   398
441ea218414e Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents: 1978
diff changeset
   399
	outlen += orig - last;
441ea218414e Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents: 1978
diff changeset
   400
	return Py_BuildValue("l", outlen);
441ea218414e Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents: 1978
diff changeset
   401
}
441ea218414e Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents: 1978
diff changeset
   402
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   403
static PyMethodDef methods[] = {
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   404
	{"patches", patches, METH_VARARGS, "apply a series of patches\n"},
2078
441ea218414e Fill in the uncompressed size during revlog.addgroup
mason@suse.com
parents: 1978
diff changeset
   405
	{"patchedsize", patchedsize, METH_VARARGS, "calculed patched size\n"},
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   406
	{NULL, NULL}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   407
};
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   408
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   409
PyMODINIT_FUNC
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   410
initmpatch(void)
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   411
{
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   412
	Py_InitModule3("mpatch", methods, mpatch_doc);
1722
681c5c211b92 catch errors and throw exception with invalid binary patch data
Benoit Boissinot <benoit.boissinot@ens-lyon.org>
parents: 597
diff changeset
   413
	mpatch_Error = PyErr_NewException("mpatch.mpatchError", NULL, NULL);
72
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   414
}
4a6ab4d80dc4 Add an O(m + nlog n) patching extension
mpm@selenic.com
parents:
diff changeset
   415