[PATCH] delta creation
[git/git.git] / mkdelta.c
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
11 #include "cache.h"
12 #include "delta.h"
13
14 static int replace_object(char *buf, unsigned long size, unsigned char *sha1)
15 {
16 char tmpfile[PATH_MAX];
17 int fd;
18
19 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 }
38
39 static void *create_object(char *buf, unsigned long len, char *hdr, int hdrlen,
40 unsigned long *retsize)
41 {
42 char *compressed;
43 unsigned long size;
44 z_stream stream;
45
46 /* 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
52 /* Compress it */
53 stream.next_out = compressed;
54 stream.avail_out = size;
55
56 /* First header.. */
57 stream.next_in = hdr;
58 stream.avail_in = hdrlen;
59 while (deflate(&stream, 0) == Z_OK)
60 /* nothing */;
61
62 /* 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 }
71
72 static int restore_original_object(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
80 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 }
86
87 static void *create_delta_object(char *buf, unsigned long len,
88 unsigned char *sha1_ref, unsigned long *size)
89 {
90 char hdr[50];
91 int hdrlen;
92
93 /* 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
98 return create_object(buf, len, hdr, hdrlen, size);
99 }
100
101 static unsigned long get_object_size(unsigned char *sha1)
102 {
103 struct stat st;
104 if (stat(sha1_file_name(sha1), &st))
105 die("%s: %s", sha1_to_hex(sha1), strerror(errno));
106 return st.st_size;
107 }
108
109 static void *get_buffer(unsigned char *sha1, char *type, unsigned long *size)
110 {
111 unsigned long mapsize;
112 void *map = map_sha1_file(sha1, &mapsize);
113 if (map) {
114 void *buffer = unpack_sha1_file(map, mapsize, type, size);
115 munmap(map, mapsize);
116 if (buffer)
117 return buffer;
118 }
119 error("unable to get object %s", sha1_to_hex(sha1));
120 return NULL;
121 }
122
123 static void *expand_delta(void *delta, unsigned long delta_size, char *type,
124 unsigned long *size, unsigned int *depth, char *head)
125 {
126 void *buf = NULL;
127 *depth++;
128 if (delta_size < 20) {
129 error("delta object is bad");
130 free(delta);
131 } else {
132 unsigned long ref_size;
133 void *ref = get_buffer(delta, type, &ref_size);
134 if (ref && !strcmp(type, "delta"))
135 ref = expand_delta(ref, ref_size, type, &ref_size,
136 depth, head);
137 else
138 memcpy(head, delta, 20);
139 if (ref)
140 buf = patch_delta(ref, ref_size, delta+20,
141 delta_size-20, size);
142 free(ref);
143 free(delta);
144 }
145 return buf;
146 }
147
148 static char *mkdelta_usage =
149 "mkdelta [ --max-depth=N ] <reference_sha1> <target_sha1> [ <next_sha1> ... ]";
150
151 int main(int argc, char **argv)
152 {
153 unsigned char sha1_ref[20], sha1_trg[20], head_ref[20], head_trg[20];
154 char type_ref[20], type_trg[20];
155 void *buf_ref, *buf_trg, *buf_delta;
156 unsigned long size_ref, size_trg, size_orig, size_delta;
157 unsigned int depth_ref, depth_trg, depth_max = -1;
158 int i, verbose = 0;
159
160 for (i = 1; i < argc; i++) {
161 if (!strcmp(argv[i], "-v")) {
162 verbose = 1;
163 } else if (!strcmp(argv[i], "-d") && i+1 < argc) {
164 depth_max = atoi(argv[++i]);
165 } else if (!strncmp(argv[i], "--max-depth=", 12)) {
166 depth_max = atoi(argv[i]+12);
167 } else
168 break;
169 }
170
171 if (i + (depth_max != 0) >= argc)
172 usage(mkdelta_usage);
173
174 if (get_sha1(argv[i], sha1_ref))
175 die("bad sha1 %s", argv[i]);
176 depth_ref = 0;
177 buf_ref = get_buffer(sha1_ref, type_ref, &size_ref);
178 if (buf_ref && !strcmp(type_ref, "delta"))
179 buf_ref = expand_delta(buf_ref, size_ref, type_ref,
180 &size_ref, &depth_ref, head_ref);
181 else
182 memcpy(head_ref, sha1_ref, 20);
183 if (!buf_ref)
184 die("unable to obtain initial object %s", argv[i]);
185
186 if (depth_ref > depth_max) {
187 if (restore_original_object(buf_ref, size_ref, type_ref, sha1_ref))
188 die("unable to restore %s", argv[i]);
189 if (verbose)
190 printf("undelta %s (depth was %d)\n", argv[i], depth_ref);
191 depth_ref = 0;
192 }
193
194 /*
195 * TODO: deltafication should be tried against any early object
196 * in the object list and not only the previous object.
197 */
198
199 while (++i < argc) {
200 if (get_sha1(argv[i], sha1_trg))
201 die("bad sha1 %s", argv[i]);
202 depth_trg = 0;
203 buf_trg = get_buffer(sha1_trg, type_trg, &size_trg);
204 if (buf_trg && !size_trg) {
205 if (verbose)
206 printf("skip %s (object is empty)\n", argv[i]);
207 continue;
208 }
209 size_orig = size_trg;
210 if (buf_trg && !strcmp(type_trg, "delta")) {
211 if (!memcmp(buf_trg, sha1_ref, 20)) {
212 /* delta already in place */
213 depth_ref++;
214 memcpy(sha1_ref, sha1_trg, 20);
215 buf_ref = patch_delta(buf_ref, size_ref,
216 buf_trg+20, size_trg-20,
217 &size_ref);
218 if (!buf_ref)
219 die("unable to apply delta %s", argv[i]);
220 if (depth_ref > depth_max) {
221 if (restore_original_object(buf_ref, size_ref,
222 type_ref, sha1_ref))
223 die("unable to restore %s", argv[i]);
224 if (verbose)
225 printf("undelta %s (depth was %d)\n", argv[i], depth_ref);
226 depth_ref = 0;
227 continue;
228 }
229 if (verbose)
230 printf("skip %s (delta already in place)\n", argv[i]);
231 continue;
232 }
233 buf_trg = expand_delta(buf_trg, size_trg, type_trg,
234 &size_trg, &depth_trg, head_trg);
235 } else
236 memcpy(head_trg, sha1_trg, 20);
237 if (!buf_trg)
238 die("unable to read target object %s", argv[i]);
239
240 if (depth_trg > depth_max) {
241 if (restore_original_object(buf_trg, size_trg, type_trg, sha1_trg))
242 die("unable to restore %s", argv[i]);
243 if (verbose)
244 printf("undelta %s (depth was %d)\n", argv[i], depth_trg);
245 depth_trg = 0;
246 size_orig = size_trg;
247 }
248
249 if (depth_max == 0)
250 goto skip;
251
252 if (strcmp(type_ref, type_trg))
253 die("type mismatch for object %s", argv[i]);
254
255 if (!size_ref) {
256 if (verbose)
257 printf("skip %s (initial object is empty)\n", argv[i]);
258 goto skip;
259 }
260
261 if (depth_ref + 1 > depth_max) {
262 if (verbose)
263 printf("skip %s (exceeding max link depth)\n", argv[i]);
264 goto skip;
265 }
266
267 if (!memcmp(head_ref, sha1_trg, 20)) {
268 if (verbose)
269 printf("skip %s (would create a loop)\n", argv[i]);
270 goto skip;
271 }
272
273 buf_delta = diff_delta(buf_ref, size_ref, buf_trg, size_trg, &size_delta);
274 if (!buf_delta)
275 die("out of memory");
276
277 /* no need to even try to compress if original
278 uncompressed is already smaller */
279 if (size_delta+20 < size_orig) {
280 void *buf_obj;
281 unsigned long size_obj;
282 buf_obj = create_delta_object(buf_delta, size_delta,
283 sha1_ref, &size_obj);
284 free(buf_delta);
285 size_orig = get_object_size(sha1_trg);
286 if (size_obj >= size_orig) {
287 free(buf_obj);
288 if (verbose)
289 printf("skip %s (original is smaller)\n", argv[i]);
290 goto skip;
291 }
292 if (replace_object(buf_obj, size_obj, sha1_trg))
293 die("unable to write delta for %s", argv[i]);
294 free(buf_obj);
295 depth_ref++;
296 if (verbose)
297 printf("delta %s (size=%ld.%02ld%%, depth=%d)\n",
298 argv[i], size_obj*100 / size_orig,
299 (size_obj*10000 / size_orig)%100,
300 depth_ref);
301 } else {
302 free(buf_delta);
303 if (verbose)
304 printf("skip %s (original is smaller)\n", argv[i]);
305 skip:
306 depth_ref = depth_trg;
307 memcpy(head_ref, head_trg, 20);
308 }
309
310 free(buf_ref);
311 buf_ref = buf_trg;
312 size_ref = size_trg;
313 memcpy(sha1_ref, sha1_trg, 20);
314 }
315
316 return 0;
317 }