1/*
2 * Deltafication of a GIT database.
3 *
4 * (C) 2005 Nicolas Pitre <nico@cam.org>
5 *
6 * This code is free software; you can redistribute it and/or modify
7 * it under the terms of the GNU General Public License version 2 as
8 * published by the Free Software Foundation.
9 */
10#include "cache.h"
12#include "delta.h"
13static int replace_object(char *buf, unsigned long size, unsigned char *sha1)
15{
16 char tmpfile[PATH_MAX];
17 int fd;
18 snprintf(tmpfile, sizeof(tmpfile), "%s/obj_XXXXXX", get_object_directory());
20 fd = mkstemp(tmpfile);
21 if (fd < 0)
22 return error("%s: %s\n", tmpfile, strerror(errno));
23 if (write(fd, buf, size) != size) {
24 perror("unable to write file");
25 close(fd);
26 unlink(tmpfile);
27 return -1;
28 }
29 fchmod(fd, 0444);
30 close(fd);
31 if (rename(tmpfile, sha1_file_name(sha1))) {
32 perror("unable to replace original object");
33 unlink(tmpfile);
34 return -1;
35 }
36 return 0;
37}
38static void *create_object(unsigned char *buf, unsigned long len,
40 char *hdr, int hdrlen, unsigned long *retsize)
41{
42 unsigned char *compressed;
43 unsigned long size;
44 z_stream stream;
45 /* Set it up */
47 memset(&stream, 0, sizeof(stream));
48 deflateInit(&stream, Z_BEST_COMPRESSION);
49 size = deflateBound(&stream, len+hdrlen);
50 compressed = xmalloc(size);
51 /* Compress it */
53 stream.next_out = compressed;
54 stream.avail_out = size;
55 /* First header.. */
57 stream.next_in = (unsigned char *)hdr;
58 stream.avail_in = hdrlen;
59 while (deflate(&stream, 0) == Z_OK)
60 /* nothing */;
61 /* Then the data itself.. */
63 stream.next_in = buf;
64 stream.avail_in = len;
65 while (deflate(&stream, Z_FINISH) == Z_OK)
66 /* nothing */;
67 deflateEnd(&stream);
68 *retsize = stream.total_out;
69 return compressed;
70}
71static int restore_original_object(unsigned char *buf, unsigned long len,
73 char *type, unsigned char *sha1)
74{
75 char hdr[50];
76 int hdrlen, ret;
77 void *compressed;
78 unsigned long size;
79 hdrlen = sprintf(hdr, "%s %lu", type, len)+1;
81 compressed = create_object(buf, len, hdr, hdrlen, &size);
82 ret = replace_object(compressed, size, sha1);
83 free(compressed);
84 return ret;
85}
86static void *create_delta_object(unsigned char *buf, unsigned long len,
88 unsigned char *sha1_ref, unsigned long *size)
89{
90 char hdr[50];
91 int hdrlen;
92 /* Generate the header + sha1 of reference for delta */
94 hdrlen = sprintf(hdr, "delta %lu", len+20)+1;
95 memcpy(hdr + hdrlen, sha1_ref, 20);
96 hdrlen += 20;
97 return create_object(buf, len, hdr, hdrlen, size);
99}
100static void *get_buffer(unsigned char *sha1, char *type,
102 unsigned long *size, unsigned long *compsize)
103{
104 unsigned long mapsize;
105 void *map = map_sha1_file(sha1, &mapsize);
106 if (map) {
107 void *buffer = unpack_sha1_file(map, mapsize, type, size);
108 munmap(map, mapsize);
109 if (compsize)
110 *compsize = mapsize;
111 if (buffer)
112 return buffer;
113 }
114 error("unable to get object %s", sha1_to_hex(sha1));
115 return NULL;
116}
117static void *expand_delta(void *delta, unsigned long *size, char *type,
119 unsigned int *depth, unsigned char **links)
120{
121 void *buf = NULL;
122 unsigned int level = (*depth)++;
123 if (*size < 20) {
124 error("delta object is bad");
125 free(delta);
126 } else {
127 unsigned long ref_size;
128 void *ref = get_buffer(delta, type, &ref_size, NULL);
129 if (ref && !strcmp(type, "delta"))
130 ref = expand_delta(ref, &ref_size, type, depth, links);
131 else if (ref)
132{
133 *links = xmalloc(*depth * 20);
134}
135 if (ref) {
136 buf = patch_delta(ref, ref_size, delta+20, *size-20, size);
137 free(ref);
138 if (buf)
139 memcpy(*links + level*20, delta, 20);
140 else
141 free(*links);
142 }
143 free(delta);
144 }
145 return buf;
146}
147static char *mkdelta_usage =
149"mkdelta [--max-depth=N] [--max-behind=N] <reference_sha1> <target_sha1> [<next_sha1> ...]";
150struct delta {
152 unsigned char sha1[20]; /* object sha1 */
153 unsigned long size; /* object size */
154 void *buf; /* object content */
155 unsigned char *links; /* delta reference links */
156 unsigned int depth; /* delta depth */
157};
158
159int main(int argc, char **argv)
160{
161 struct delta *ref, trg;
162 char ref_type[20], trg_type[20], *skip_reason;
163 void *best_buf;
164 unsigned long best_size, orig_size, orig_compsize;
165 unsigned int r, orig_ref, best_ref, nb_refs, next_ref, max_refs = 0;
166 unsigned int i, duplicate, skip_lvl, verbose = 0, quiet = 0;
167 unsigned int max_depth = -1;
168 for (i = 1; i < argc; i++) {
170 if (!strcmp(argv[i], "-v")) {
171 verbose = 1;
172 quiet = 0;
173 } else if (!strcmp(argv[i], "-q")) {
174 quiet = 1;
175 verbose = 0;
176 } else if (!strcmp(argv[i], "-d") && i+1 < argc) {
177 max_depth = atoi(argv[++i]);
178 } else if (!strncmp(argv[i], "--max-depth=", 12)) {
179 max_depth = atoi(argv[i]+12);
180 } else if (!strcmp(argv[i], "-b") && i+1 < argc) {
181 max_refs = atoi(argv[++i]);
182 } else if (!strncmp(argv[i], "--max-behind=", 13)) {
183 max_refs = atoi(argv[i]+13);
184 } else
185 break;
186 }
187 if (i + (max_depth != 0) >= argc)
189 usage(mkdelta_usage);
190 if (!max_refs || max_refs > argc - i)
192 max_refs = argc - i;
193 ref = xmalloc(max_refs * sizeof(*ref));
194 for (r = 0; r < max_refs; r++)
195 ref[r].buf = ref[r].links = NULL;
196 next_ref = nb_refs = 0;
197 do {
199 if (get_sha1(argv[i], trg.sha1))
200 die("bad sha1 %s", argv[i]);
201 trg.buf = get_buffer(trg.sha1, trg_type, &trg.size, &orig_compsize);
202 if (trg.buf && !trg.size) {
203 if (verbose)
204 printf("skip %s (object is empty)\n", argv[i]);
205 continue;
206 }
207 orig_size = trg.size;
208 orig_ref = -1;
209 trg.depth = 0;
210 trg.links = NULL;
211 if (trg.buf && !strcmp(trg_type, "delta")) {
212 for (r = 0; r < nb_refs; r++)
213 if (!memcmp(trg.buf, ref[r].sha1, 20))
214 break;
215 if (r < nb_refs) {
216 /* no need to reload the reference object */
217 trg.depth = ref[r].depth + 1;
218 trg.links = xmalloc(trg.depth*20);
219 memcpy(trg.links, trg.buf, 20);
220 memcpy(trg.links+20, ref[r].links, ref[r].depth*20);
221 trg.buf = patch_delta(ref[r].buf, ref[r].size,
222 trg.buf+20, trg.size-20,
223 &trg.size);
224 strcpy(trg_type, ref_type);
225 orig_ref = r;
226 } else {
227 trg.buf = expand_delta(trg.buf, &trg.size, trg_type,
228 &trg.depth, &trg.links);
229 }
230 }
231 if (!trg.buf)
232 die("unable to read target object %s", argv[i]);
233 if (!nb_refs) {
235 strcpy(ref_type, trg_type);
236 } else if (max_depth && strcmp(ref_type, trg_type)) {
237 die("type mismatch for object %s", argv[i]);
238 }
239 duplicate = 0;
241 best_buf = NULL;
242 best_size = -1;
243 best_ref = -1;
244 skip_lvl = 0;
245 skip_reason = NULL;
246 for (r = 0; max_depth && r < nb_refs; r++) {
247 void *delta_buf, *comp_buf;
248 unsigned long delta_size, comp_size;
249 unsigned int l;
250 duplicate = !memcmp(trg.sha1, ref[r].sha1, 20);
252 if (duplicate) {
253 skip_reason = "already seen";
254 break;
255 }
256 if (ref[r].depth >= max_depth) {
257 if (skip_lvl < 1) {
258 skip_reason = "exceeding max link depth";
259 skip_lvl = 1;
260 }
261 continue;
262 }
263 for (l = 0; l < ref[r].depth; l++)
264 if (!memcmp(trg.sha1, ref[r].links + l*20, 20))
265 break;
266 if (l != ref[r].depth) {
267 if (skip_lvl < 2) {
268 skip_reason = "would create a loop";
269 skip_lvl = 2;
270 }
271 continue;
272 }
273 if (trg.depth < max_depth && r == orig_ref) {
274 if (skip_lvl < 3) {
275 skip_reason = "delta already in place";
276 skip_lvl = 3;
277 }
278 continue;
279 }
280 delta_buf = diff_delta(ref[r].buf, ref[r].size,
281 trg.buf, trg.size, &delta_size);
282 if (!delta_buf)
283 die("out of memory");
284 if (trg.depth < max_depth &&
285 delta_size+20 >= orig_size) {
286 /* no need to even try to compress if original
287 object is smaller than this delta */
288 free(delta_buf);
289 if (skip_lvl < 4) {
290 skip_reason = "no size reduction";
291 skip_lvl = 4;
292 }
293 continue;
294 }
295 comp_buf = create_delta_object(delta_buf, delta_size,
296 ref[r].sha1, &comp_size);
297 if (!comp_buf)
298 die("out of memory");
299 free(delta_buf);
300 if (trg.depth < max_depth &&
301 comp_size >= orig_compsize) {
302 free(comp_buf);
303 if (skip_lvl < 5) {
304 skip_reason = "no size reduction";
305 skip_lvl = 5;
306 }
307 continue;
308 }
309 if ((comp_size < best_size) ||
310 (comp_size == best_size &&
311 ref[r].depth < ref[best_ref].depth)) {
312 free(best_buf);
313 best_buf = comp_buf;
314 best_size = comp_size;
315 best_ref = r;
316 }
317 }
318 if (best_buf) {
320 if (replace_object(best_buf, best_size, trg.sha1))
321 die("unable to write delta for %s", argv[i]);
322 free(best_buf);
323 free(trg.links);
324 trg.depth = ref[best_ref].depth + 1;
325 trg.links = xmalloc(trg.depth*20);
326 memcpy(trg.links, ref[best_ref].sha1, 20);
327 memcpy(trg.links+20, ref[best_ref].links, ref[best_ref].depth*20);
328 if (!quiet)
329 printf("delta %s (size=%ld.%02ld%% depth=%d dist=%d)\n",
330 argv[i], best_size*100 / orig_compsize,
331 (best_size*10000 / orig_compsize)%100,
332 trg.depth,
333 (next_ref - best_ref + max_refs)
334 % (max_refs + 1) + 1);
335 } else if (trg.depth > max_depth) {
336 if (restore_original_object(trg.buf, trg.size, trg_type, trg.sha1))
337 die("unable to restore %s", argv[i]);
338 if (!quiet)
339 printf("undelta %s (depth was %d)\n",
340 argv[i], trg.depth);
341 trg.depth = 0;
342 free(trg.links);
343 trg.links = NULL;
344 } else if (skip_reason && verbose) {
345 printf("skip %s (%s)\n", argv[i], skip_reason);
346 }
347 if (!duplicate) {
349 free(ref[next_ref].buf);
350 free(ref[next_ref].links);
351 ref[next_ref] = trg;
352 if (++next_ref > nb_refs)
353 nb_refs = next_ref;
354 if (next_ref == max_refs)
355 next_ref = 0;
356 } else {
357 free(trg.buf);
358 free(trg.links);
359 }
360 } while (++i < argc);
361 return 0;
363}