revision: --topo-order and --unpacked
[git.git] / diff-delta.c
1 /*
2  * diff-delta.c: generate a delta between two buffers
3  *
4  *  Many parts of this file have been lifted from LibXDiff version 0.10.
5  *  http://www.xmailserver.org/xdiff-lib.html
6  *
7  *  LibXDiff was written by Davide Libenzi <davidel@xmailserver.org>
8  *  Copyright (C) 2003  Davide Libenzi
9  *
10  *  Many mods for GIT usage by Nicolas Pitre <nico@cam.org>, (C) 2005.
11  *
12  *  This file is free software; you can redistribute it and/or
13  *  modify it under the terms of the GNU Lesser General Public
14  *  License as published by the Free Software Foundation; either
15  *  version 2.1 of the License, or (at your option) any later version.
16  *
17  *  Use of this within git automatically means that the LGPL
18  *  licensing gets turned into GPLv2 within this project.
19  */
20
21 #include <stdlib.h>
22 #include <string.h>
23 #include <zlib.h>
24 #include "delta.h"
25
26
27 /* block size: min = 16, max = 64k, power of 2 */
28 #define BLK_SIZE 16
29
30 #define MIN(a, b) ((a) < (b) ? (a) : (b))
31
32 #define GR_PRIME 0x9e370001
33 #define HASH(v, shift) (((unsigned int)(v) * GR_PRIME) >> (shift))
34
35 struct index {
36         const unsigned char *ptr;
37         unsigned int val;
38         struct index *next;
39 };
40
41 static struct index ** delta_index(const unsigned char *buf,
42                                    unsigned long bufsize,
43                                    unsigned long trg_bufsize,
44                                    unsigned int *hash_shift)
45 {
46         unsigned int i, hsize, hshift, hlimit, entries, *hash_count;
47         const unsigned char *data;
48         struct index *entry, **hash;
49         void *mem;
50
51         /* determine index hash size */
52         entries = bufsize  / BLK_SIZE;
53         hsize = entries / 4;
54         for (i = 4; (1 << i) < hsize && i < 31; i++);
55         hsize = 1 << i;
56         hshift = 32 - i;
57         *hash_shift = hshift;
58
59         /* allocate lookup index */
60         mem = malloc(hsize * sizeof(*hash) + entries * sizeof(*entry));
61         if (!mem)
62                 return NULL;
63         hash = mem;
64         entry = mem + hsize * sizeof(*hash);
65         memset(hash, 0, hsize * sizeof(*hash));
66
67         /* allocate an array to count hash entries */
68         hash_count = calloc(hsize, sizeof(*hash_count));
69         if (!hash_count) {
70                 free(hash);
71                 return NULL;
72         }
73
74         /* then populate the index */
75         data = buf + entries * BLK_SIZE - BLK_SIZE;
76         while (data >= buf) {
77                 unsigned int val = adler32(0, data, BLK_SIZE);
78                 i = HASH(val, hshift);
79                 entry->ptr = data;
80                 entry->val = val;
81                 entry->next = hash[i];
82                 hash[i] = entry++;
83                 hash_count[i]++;
84                 data -= BLK_SIZE;
85         }
86
87         /*
88          * Determine a limit on the number of entries in the same hash
89          * bucket.  This guard us against patological data sets causing
90          * really bad hash distribution with most entries in the same hash
91          * bucket that would bring us to O(m*n) computing costs (m and n
92          * corresponding to reference and target buffer sizes).
93          *
94          * The more the target buffer is large, the more it is important to
95          * have small entry lists for each hash buckets.  With such a limit
96          * the cost is bounded to something more like O(m+n).
97          */
98         hlimit = (1 << 26) / trg_bufsize;
99         if (hlimit < 4*BLK_SIZE)
100                 hlimit = 4*BLK_SIZE;
101
102         /*
103          * Now make sure none of the hash buckets has more entries than
104          * we're willing to test.  Otherwise we cull the entry list
105          * uniformly to still preserve a good repartition across
106          * the reference buffer.
107          */
108         for (i = 0; i < hsize; i++) {
109                 if (hash_count[i] < hlimit)
110                         continue;
111                 entry = hash[i];
112                 do {
113                         struct index *keep = entry;
114                         int skip = hash_count[i] / hlimit / 2;
115                         do {
116                                 entry = entry->next;
117                         } while(--skip && entry);
118                         keep->next = entry;
119                 } while(entry);
120         }
121         free(hash_count);
122
123         return hash;
124 }
125
126 /* provide the size of the copy opcode given the block offset and size */
127 #define COPYOP_SIZE(o, s) \
128     (!!(o & 0xff) + !!(o & 0xff00) + !!(o & 0xff0000) + !!(o & 0xff000000) + \
129      !!(s & 0xff) + !!(s & 0xff00) + 1)
130
131 /* the maximum size for any opcode */
132 #define MAX_OP_SIZE COPYOP_SIZE(0xffffffff, 0xffffffff)
133
134 void *diff_delta(void *from_buf, unsigned long from_size,
135                  void *to_buf, unsigned long to_size,
136                  unsigned long *delta_size,
137                  unsigned long max_size)
138 {
139         unsigned int i, outpos, outsize, hash_shift;
140         int inscnt;
141         const unsigned char *ref_data, *ref_top, *data, *top;
142         unsigned char *out;
143         struct index *entry, **hash;
144
145         if (!from_size || !to_size)
146                 return NULL;
147         hash = delta_index(from_buf, from_size, to_size, &hash_shift);
148         if (!hash)
149                 return NULL;
150
151         outpos = 0;
152         outsize = 8192;
153         if (max_size && outsize >= max_size)
154                 outsize = max_size + MAX_OP_SIZE + 1;
155         out = malloc(outsize);
156         if (!out) {
157                 free(hash);
158                 return NULL;
159         }
160
161         ref_data = from_buf;
162         ref_top = from_buf + from_size;
163         data = to_buf;
164         top = to_buf + to_size;
165
166         /* store reference buffer size */
167         out[outpos++] = from_size;
168         from_size >>= 7;
169         while (from_size) {
170                 out[outpos - 1] |= 0x80;
171                 out[outpos++] = from_size;
172                 from_size >>= 7;
173         }
174
175         /* store target buffer size */
176         out[outpos++] = to_size;
177         to_size >>= 7;
178         while (to_size) {
179                 out[outpos - 1] |= 0x80;
180                 out[outpos++] = to_size;
181                 to_size >>= 7;
182         }
183
184         inscnt = 0;
185
186         while (data < top) {
187                 unsigned int moff = 0, msize = 0;
188                 if (data + BLK_SIZE <= top) {
189                         unsigned int val = adler32(0, data, BLK_SIZE);
190                         i = HASH(val, hash_shift);
191                         for (entry = hash[i]; entry; entry = entry->next) {
192                                 const unsigned char *ref = entry->ptr;
193                                 const unsigned char *src = data;
194                                 unsigned int ref_size = ref_top - ref;
195                                 if (entry->val != val)
196                                         continue;
197                                 if (ref_size > top - src)
198                                         ref_size = top - src;
199                                 if (ref_size > 0x10000)
200                                         ref_size = 0x10000;
201                                 if (ref_size <= msize)
202                                         break;
203                                 while (ref_size-- && *src++ == *ref)
204                                         ref++;
205                                 if (msize < ref - entry->ptr) {
206                                         /* this is our best match so far */
207                                         msize = ref - entry->ptr;
208                                         moff = entry->ptr - ref_data;
209                                 }
210                         }
211                 }
212
213                 if (!msize || msize < COPYOP_SIZE(moff, msize)) {
214                         if (!inscnt)
215                                 outpos++;
216                         out[outpos++] = *data++;
217                         inscnt++;
218                         if (inscnt == 0x7f) {
219                                 out[outpos - inscnt - 1] = inscnt;
220                                 inscnt = 0;
221                         }
222                 } else {
223                         unsigned char *op;
224
225                         if (inscnt) {
226                                 while (moff && ref_data[moff-1] == data[-1]) {
227                                         if (msize == 0x10000)
228                                                 break;
229                                         /* we can match one byte back */
230                                         msize++;
231                                         moff--;
232                                         data--;
233                                         outpos--;
234                                         if (--inscnt)
235                                                 continue;
236                                         outpos--;  /* remove count slot */
237                                         inscnt--;  /* make it -1 */
238                                         break;
239                                 }
240                                 out[outpos - inscnt - 1] = inscnt;
241                                 inscnt = 0;
242                         }
243
244                         data += msize;
245                         op = out + outpos++;
246                         i = 0x80;
247
248                         if (moff & 0xff) { out[outpos++] = moff; i |= 0x01; }
249                         moff >>= 8;
250                         if (moff & 0xff) { out[outpos++] = moff; i |= 0x02; }
251                         moff >>= 8;
252                         if (moff & 0xff) { out[outpos++] = moff; i |= 0x04; }
253                         moff >>= 8;
254                         if (moff & 0xff) { out[outpos++] = moff; i |= 0x08; }
255
256                         if (msize & 0xff) { out[outpos++] = msize; i |= 0x10; }
257                         msize >>= 8;
258                         if (msize & 0xff) { out[outpos++] = msize; i |= 0x20; }
259
260                         *op = i;
261                 }
262
263                 if (outpos >= outsize - MAX_OP_SIZE) {
264                         void *tmp = out;
265                         outsize = outsize * 3 / 2;
266                         if (max_size && outsize >= max_size)
267                                 outsize = max_size + MAX_OP_SIZE + 1;
268                         if (max_size && outpos > max_size)
269                                 out = NULL;
270                         else
271                                 out = realloc(out, outsize);
272                         if (!out) {
273                                 free(tmp);
274                                 free(hash);
275                                 return NULL;
276                         }
277                 }
278         }
279
280         if (inscnt)
281                 out[outpos - inscnt - 1] = inscnt;
282
283         free(hash);
284         *delta_size = outpos;
285         return out;
286 }