]>
Commit | Line | Data |
---|---|---|
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> | |
8e1454b5 NP |
22 | #include <string.h> |
23 | #include <zlib.h> | |
a310d434 NP |
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 | |
8e1454b5 | 33 | #define HASH(v, shift) (((unsigned int)(v) * GR_PRIME) >> (shift)) |
a310d434 | 34 | |
8e1454b5 | 35 | struct index { |
a310d434 | 36 | const unsigned char *ptr; |
8e1454b5 NP |
37 | unsigned int val; |
38 | struct index *next; | |
39 | }; | |
a310d434 | 40 | |
8e1454b5 NP |
41 | static struct index ** delta_index(const unsigned char *buf, |
42 | unsigned long bufsize, | |
43 | unsigned int *hash_shift) | |
a310d434 | 44 | { |
8e1454b5 NP |
45 | unsigned int hsize, hshift, entries, blksize, i; |
46 | const unsigned char *data; | |
47 | struct index *entry, **hash; | |
48 | void *mem; | |
49 | ||
50 | /* determine index hash size */ | |
51 | entries = (bufsize + BLK_SIZE - 1) / BLK_SIZE; | |
52 | hsize = entries / 4; | |
53 | for (i = 4; (1 << i) < hsize && i < 16; i++); | |
54 | hsize = 1 << i; | |
55 | hshift = 32 - i; | |
56 | *hash_shift = hshift; | |
57 | ||
58 | /* allocate lookup index */ | |
59 | mem = malloc(hsize * sizeof(*hash) + entries * sizeof(*entry)); | |
60 | if (!mem) | |
61 | return NULL; | |
62 | hash = mem; | |
63 | entry = mem + hsize * sizeof(*hash); | |
64 | memset(hash, 0, hsize * sizeof(*hash)); | |
65 | ||
66 | /* then populate it */ | |
67 | data = buf + entries * BLK_SIZE - BLK_SIZE; | |
68 | blksize = bufsize - (data - buf); | |
69 | while (data >= buf) { | |
70 | unsigned int val = adler32(0, data, blksize); | |
71 | i = HASH(val, hshift); | |
72 | entry->ptr = data; | |
73 | entry->val = val; | |
74 | entry->next = hash[i]; | |
75 | hash[i] = entry++; | |
76 | blksize = BLK_SIZE; | |
a310d434 | 77 | data -= BLK_SIZE; |
8e1454b5 | 78 | } |
a310d434 | 79 | |
8e1454b5 | 80 | return hash; |
a310d434 NP |
81 | } |
82 | ||
fe474b58 | 83 | /* provide the size of the copy opcode given the block offset and size */ |
a310d434 NP |
84 | #define COPYOP_SIZE(o, s) \ |
85 | (!!(o & 0xff) + !!(o & 0xff00) + !!(o & 0xff0000) + !!(o & 0xff000000) + \ | |
86 | !!(s & 0xff) + !!(s & 0xff00) + 1) | |
87 | ||
fe474b58 NP |
88 | /* the maximum size for any opcode */ |
89 | #define MAX_OP_SIZE COPYOP_SIZE(0xffffffff, 0xffffffff) | |
90 | ||
a310d434 NP |
91 | void *diff_delta(void *from_buf, unsigned long from_size, |
92 | void *to_buf, unsigned long to_size, | |
75c42d8c LT |
93 | unsigned long *delta_size, |
94 | unsigned long max_size) | |
a310d434 | 95 | { |
8e1454b5 NP |
96 | unsigned int i, outpos, outsize, inscnt, hash_shift; |
97 | const unsigned char *ref_data, *ref_top, *data, *top; | |
98 | unsigned char *out; | |
99 | struct index *entry, **hash; | |
a310d434 | 100 | |
8e1454b5 | 101 | if (!from_size || !to_size) |
a310d434 | 102 | return NULL; |
8e1454b5 NP |
103 | hash = delta_index(from_buf, from_size, &hash_shift); |
104 | if (!hash) | |
105 | return NULL; | |
106 | ||
a310d434 NP |
107 | outpos = 0; |
108 | outsize = 8192; | |
fe474b58 NP |
109 | if (max_size && outsize >= max_size) |
110 | outsize = max_size + MAX_OP_SIZE + 1; | |
a310d434 NP |
111 | out = malloc(outsize); |
112 | if (!out) { | |
8e1454b5 | 113 | free(hash); |
a310d434 NP |
114 | return NULL; |
115 | } | |
116 | ||
e5e3a9d8 NP |
117 | ref_data = from_buf; |
118 | ref_top = from_buf + from_size; | |
a310d434 NP |
119 | data = to_buf; |
120 | top = to_buf + to_size; | |
121 | ||
122 | /* store reference buffer size */ | |
69a2d426 NP |
123 | out[outpos++] = from_size; |
124 | from_size >>= 7; | |
125 | while (from_size) { | |
126 | out[outpos - 1] |= 0x80; | |
127 | out[outpos++] = from_size; | |
128 | from_size >>= 7; | |
129 | } | |
a310d434 NP |
130 | |
131 | /* store target buffer size */ | |
69a2d426 NP |
132 | out[outpos++] = to_size; |
133 | to_size >>= 7; | |
134 | while (to_size) { | |
135 | out[outpos - 1] |= 0x80; | |
136 | out[outpos++] = to_size; | |
137 | to_size >>= 7; | |
138 | } | |
a310d434 NP |
139 | |
140 | inscnt = 0; | |
a310d434 | 141 | |
8e1454b5 NP |
142 | while (data < top) { |
143 | unsigned int moff = 0, msize = 0; | |
144 | unsigned int blksize = MIN(top - data, BLK_SIZE); | |
145 | unsigned int val = adler32(0, data, blksize); | |
146 | i = HASH(val, hash_shift); | |
147 | for (entry = hash[i]; entry; entry = entry->next) { | |
148 | const unsigned char *ref = entry->ptr; | |
149 | const unsigned char *src = data; | |
150 | unsigned int ref_size = ref_top - ref; | |
151 | if (entry->val != val) | |
152 | continue; | |
153 | if (ref_size > top - src) | |
154 | ref_size = top - src; | |
155 | while (ref_size && *src++ == *ref) { | |
156 | ref++; | |
157 | ref_size--; | |
158 | } | |
159 | ref_size = ref - entry->ptr; | |
160 | if (ref_size > msize) { | |
161 | /* this is our best match so far */ | |
162 | moff = entry->ptr - ref_data; | |
163 | msize = ref_size; | |
164 | if (msize >= 0x10000) { | |
165 | msize = 0x10000; | |
166 | break; | |
a310d434 NP |
167 | } |
168 | } | |
169 | } | |
170 | ||
171 | if (!msize || msize < COPYOP_SIZE(moff, msize)) { | |
172 | if (!inscnt) | |
173 | outpos++; | |
174 | out[outpos++] = *data++; | |
175 | inscnt++; | |
176 | if (inscnt == 0x7f) { | |
177 | out[outpos - inscnt - 1] = inscnt; | |
178 | inscnt = 0; | |
179 | } | |
180 | } else { | |
8e1454b5 NP |
181 | unsigned char *op; |
182 | ||
a310d434 NP |
183 | if (inscnt) { |
184 | out[outpos - inscnt - 1] = inscnt; | |
185 | inscnt = 0; | |
186 | } | |
187 | ||
188 | data += msize; | |
8e1454b5 | 189 | op = out + outpos++; |
a310d434 NP |
190 | i = 0x80; |
191 | ||
192 | if (moff & 0xff) { out[outpos++] = moff; i |= 0x01; } | |
193 | moff >>= 8; | |
194 | if (moff & 0xff) { out[outpos++] = moff; i |= 0x02; } | |
195 | moff >>= 8; | |
196 | if (moff & 0xff) { out[outpos++] = moff; i |= 0x04; } | |
197 | moff >>= 8; | |
198 | if (moff & 0xff) { out[outpos++] = moff; i |= 0x08; } | |
199 | ||
200 | if (msize & 0xff) { out[outpos++] = msize; i |= 0x10; } | |
201 | msize >>= 8; | |
202 | if (msize & 0xff) { out[outpos++] = msize; i |= 0x20; } | |
203 | ||
8e1454b5 | 204 | *op = i; |
a310d434 NP |
205 | } |
206 | ||
fe474b58 | 207 | if (outpos >= outsize - MAX_OP_SIZE) { |
a310d434 NP |
208 | void *tmp = out; |
209 | outsize = outsize * 3 / 2; | |
fe474b58 NP |
210 | if (max_size && outsize >= max_size) |
211 | outsize = max_size + MAX_OP_SIZE + 1; | |
212 | if (max_size && outpos > max_size) | |
213 | out = NULL; | |
214 | else | |
215 | out = realloc(out, outsize); | |
a310d434 NP |
216 | if (!out) { |
217 | free(tmp); | |
8e1454b5 | 218 | free(hash); |
a310d434 NP |
219 | return NULL; |
220 | } | |
221 | } | |
222 | } | |
223 | ||
224 | if (inscnt) | |
225 | out[outpos - inscnt - 1] = inscnt; | |
226 | ||
8e1454b5 | 227 | free(hash); |
a310d434 NP |
228 | *delta_size = outpos; |
229 | return out; | |
230 | } |