relax delta selection filtering in pack-objects
[git/git.git] / diff-delta.c
CommitLineData
a310d434
NP
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 "delta.h"
04fe2a17 23#include "zlib.h"
a310d434
NP
24
25
26/* block size: min = 16, max = 64k, power of 2 */
27#define BLK_SIZE 16
28
29#define MIN(a, b) ((a) < (b) ? (a) : (b))
30
31#define GR_PRIME 0x9e370001
32#define HASH(v, b) (((unsigned int)(v) * GR_PRIME) >> (32 - (b)))
33
a310d434
NP
34static unsigned int hashbits(unsigned int size)
35{
36 unsigned int val = 1, bits = 0;
37 while (val < size && bits < 32) {
38 val <<= 1;
39 bits++;
40 }
41 return bits ? bits: 1;
42}
43
44typedef struct s_chanode {
45 struct s_chanode *next;
46 int icurr;
47} chanode_t;
48
49typedef struct s_chastore {
a310d434
NP
50 int isize, nsize;
51 chanode_t *ancur;
a310d434
NP
52} chastore_t;
53
54static void cha_init(chastore_t *cha, int isize, int icount)
55{
a310d434
NP
56 cha->isize = isize;
57 cha->nsize = icount * isize;
e5e3a9d8 58 cha->ancur = NULL;
a310d434
NP
59}
60
61static void *cha_alloc(chastore_t *cha)
62{
63 chanode_t *ancur;
64 void *data;
65
66 ancur = cha->ancur;
67 if (!ancur || ancur->icurr == cha->nsize) {
68 ancur = malloc(sizeof(chanode_t) + cha->nsize);
69 if (!ancur)
70 return NULL;
71 ancur->icurr = 0;
e5e3a9d8 72 ancur->next = cha->ancur;
a310d434
NP
73 cha->ancur = ancur;
74 }
75
76 data = (void *)ancur + sizeof(chanode_t) + ancur->icurr;
77 ancur->icurr += cha->isize;
78 return data;
79}
80
81static void cha_free(chastore_t *cha)
82{
e5e3a9d8 83 chanode_t *cur = cha->ancur;
a310d434
NP
84 while (cur) {
85 chanode_t *tmp = cur;
86 cur = cur->next;
87 free(tmp);
88 }
89}
90
91typedef struct s_bdrecord {
92 struct s_bdrecord *next;
93 unsigned int fp;
94 const unsigned char *ptr;
95} bdrecord_t;
96
97typedef struct s_bdfile {
a310d434
NP
98 chastore_t cha;
99 unsigned int fphbits;
100 bdrecord_t **fphash;
101} bdfile_t;
102
103static int delta_prepare(const unsigned char *buf, int bufsize, bdfile_t *bdf)
104{
105 unsigned int fphbits;
106 int i, hsize;
e5e3a9d8 107 const unsigned char *data, *top;
a310d434
NP
108 bdrecord_t *brec;
109 bdrecord_t **fphash;
110
111 fphbits = hashbits(bufsize / BLK_SIZE + 1);
112 hsize = 1 << fphbits;
113 fphash = malloc(hsize * sizeof(bdrecord_t *));
114 if (!fphash)
115 return -1;
116 for (i = 0; i < hsize; i++)
117 fphash[i] = NULL;
118 cha_init(&bdf->cha, sizeof(bdrecord_t), hsize / 4 + 1);
119
e5e3a9d8
NP
120 top = buf + bufsize;
121 data = buf + (bufsize / BLK_SIZE) * BLK_SIZE;
a310d434
NP
122 if (data == top)
123 data -= BLK_SIZE;
124
e5e3a9d8 125 for ( ; data >= buf; data -= BLK_SIZE) {
a310d434
NP
126 brec = cha_alloc(&bdf->cha);
127 if (!brec) {
128 cha_free(&bdf->cha);
129 free(fphash);
130 return -1;
131 }
132 brec->fp = adler32(0, data, MIN(BLK_SIZE, top - data));
133 brec->ptr = data;
134 i = HASH(brec->fp, fphbits);
135 brec->next = fphash[i];
136 fphash[i] = brec;
137 }
138
139 bdf->fphbits = fphbits;
140 bdf->fphash = fphash;
141
142 return 0;
143}
144
145static void delta_cleanup(bdfile_t *bdf)
146{
147 free(bdf->fphash);
148 cha_free(&bdf->cha);
149}
150
151#define COPYOP_SIZE(o, s) \
152 (!!(o & 0xff) + !!(o & 0xff00) + !!(o & 0xff0000) + !!(o & 0xff000000) + \
153 !!(s & 0xff) + !!(s & 0xff00) + 1)
154
155void *diff_delta(void *from_buf, unsigned long from_size,
156 void *to_buf, unsigned long to_size,
75c42d8c
LT
157 unsigned long *delta_size,
158 unsigned long max_size)
a310d434
NP
159{
160 int i, outpos, outsize, inscnt, csize, msize, moff;
161 unsigned int fp;
e5e3a9d8 162 const unsigned char *ref_data, *ref_top, *data, *top, *ptr1, *ptr2;
a310d434
NP
163 unsigned char *out, *orig;
164 bdrecord_t *brec;
165 bdfile_t bdf;
166
c7a45bd2 167 if (!from_size || !to_size || delta_prepare(from_buf, from_size, &bdf))
a310d434
NP
168 return NULL;
169
170 outpos = 0;
171 outsize = 8192;
172 out = malloc(outsize);
173 if (!out) {
174 delta_cleanup(&bdf);
175 return NULL;
176 }
177
e5e3a9d8
NP
178 ref_data = from_buf;
179 ref_top = from_buf + from_size;
a310d434
NP
180 data = to_buf;
181 top = to_buf + to_size;
182
183 /* store reference buffer size */
69a2d426
NP
184 out[outpos++] = from_size;
185 from_size >>= 7;
186 while (from_size) {
187 out[outpos - 1] |= 0x80;
188 out[outpos++] = from_size;
189 from_size >>= 7;
190 }
a310d434
NP
191
192 /* store target buffer size */
69a2d426
NP
193 out[outpos++] = to_size;
194 to_size >>= 7;
195 while (to_size) {
196 out[outpos - 1] |= 0x80;
197 out[outpos++] = to_size;
198 to_size >>= 7;
199 }
a310d434
NP
200
201 inscnt = 0;
202 moff = 0;
203 while (data < top) {
204 msize = 0;
205 fp = adler32(0, data, MIN(top - data, BLK_SIZE));
206 i = HASH(fp, bdf.fphbits);
207 for (brec = bdf.fphash[i]; brec; brec = brec->next) {
208 if (brec->fp == fp) {
e5e3a9d8 209 csize = ref_top - brec->ptr;
a310d434
NP
210 if (csize > top - data)
211 csize = top - data;
212 for (ptr1 = brec->ptr, ptr2 = data;
213 csize && *ptr1 == *ptr2;
214 csize--, ptr1++, ptr2++);
215
216 csize = ptr1 - brec->ptr;
217 if (csize > msize) {
e5e3a9d8 218 moff = brec->ptr - ref_data;
a310d434
NP
219 msize = csize;
220 if (msize >= 0x10000) {
221 msize = 0x10000;
222 break;
223 }
224 }
225 }
226 }
227
228 if (!msize || msize < COPYOP_SIZE(moff, msize)) {
229 if (!inscnt)
230 outpos++;
231 out[outpos++] = *data++;
232 inscnt++;
233 if (inscnt == 0x7f) {
234 out[outpos - inscnt - 1] = inscnt;
235 inscnt = 0;
236 }
237 } else {
238 if (inscnt) {
239 out[outpos - inscnt - 1] = inscnt;
240 inscnt = 0;
241 }
242
243 data += msize;
244 orig = out + outpos++;
245 i = 0x80;
246
247 if (moff & 0xff) { out[outpos++] = moff; i |= 0x01; }
248 moff >>= 8;
249 if (moff & 0xff) { out[outpos++] = moff; i |= 0x02; }
250 moff >>= 8;
251 if (moff & 0xff) { out[outpos++] = moff; i |= 0x04; }
252 moff >>= 8;
253 if (moff & 0xff) { out[outpos++] = moff; i |= 0x08; }
254
255 if (msize & 0xff) { out[outpos++] = msize; i |= 0x10; }
256 msize >>= 8;
257 if (msize & 0xff) { out[outpos++] = msize; i |= 0x20; }
258
259 *orig = i;
260 }
261
75c42d8c
LT
262 if (max_size && outpos > max_size) {
263 free(out);
264 delta_cleanup(&bdf);
265 return NULL;
266 }
dcde55bc
NP
267
268 /* next time around the largest possible output is 1 + 4 + 3 */
a310d434
NP
269 if (outpos > outsize - 8) {
270 void *tmp = out;
271 outsize = outsize * 3 / 2;
272 out = realloc(out, outsize);
273 if (!out) {
274 free(tmp);
275 delta_cleanup(&bdf);
276 return NULL;
277 }
278 }
279 }
280
281 if (inscnt)
282 out[outpos - inscnt - 1] = inscnt;
283
284 delta_cleanup(&bdf);
285 *delta_size = outpos;
286 return out;
287}