return create_object(buf, len, hdr, hdrlen, size);
}
-static unsigned long get_object_size(unsigned char *sha1)
-{
- struct stat st;
- if (stat(sha1_file_name(sha1), &st))
- die("%s: %s", sha1_to_hex(sha1), strerror(errno));
- return st.st_size;
-}
-
-static void *get_buffer(unsigned char *sha1, char *type, unsigned long *size)
+static void *get_buffer(unsigned char *sha1, char *type,
+ unsigned long *size, unsigned long *compsize)
{
unsigned long mapsize;
void *map = map_sha1_file(sha1, &mapsize);
if (map) {
void *buffer = unpack_sha1_file(map, mapsize, type, size);
munmap(map, mapsize);
+ if (compsize)
+ *compsize = mapsize;
if (buffer)
return buffer;
}
return NULL;
}
-static void *expand_delta(void *delta, unsigned long delta_size, char *type,
- unsigned long *size, unsigned int *depth, char *head)
+static void *expand_delta(void *delta, unsigned long *size, char *type,
+ unsigned int *depth, unsigned char **links)
{
void *buf = NULL;
- *depth++;
- if (delta_size < 20) {
+ unsigned int level = (*depth)++;
+ if (*size < 20) {
error("delta object is bad");
free(delta);
} else {
unsigned long ref_size;
- void *ref = get_buffer(delta, type, &ref_size);
+ void *ref = get_buffer(delta, type, &ref_size, NULL);
if (ref && !strcmp(type, "delta"))
- ref = expand_delta(ref, ref_size, type, &ref_size,
- depth, head);
- else
- memcpy(head, delta, 20);
- if (ref)
- buf = patch_delta(ref, ref_size, delta+20,
- delta_size-20, size);
- free(ref);
+ ref = expand_delta(ref, &ref_size, type, depth, links);
+ else if (ref)
+{
+ *links = xmalloc(*depth * 20);
+}
+ if (ref) {
+ buf = patch_delta(ref, ref_size, delta+20, *size-20, size);
+ free(ref);
+ if (buf)
+ memcpy(*links + level*20, delta, 20);
+ else
+ free(*links);
+ }
free(delta);
}
return buf;
}
static char *mkdelta_usage =
-"mkdelta [ --max-depth=N ] <reference_sha1> <target_sha1> [ <next_sha1> ... ]";
-
+"mkdelta [--max-depth=N] [--max-behind=N] <reference_sha1> <target_sha1> [<next_sha1> ...]";
+
+struct delta {
+ unsigned char sha1[20]; /* object sha1 */
+ unsigned long size; /* object size */
+ void *buf; /* object content */
+ unsigned char *links; /* delta reference links */
+ unsigned int depth; /* delta depth */
+};
+
int main(int argc, char **argv)
{
- unsigned char sha1_ref[20], sha1_trg[20], head_ref[20], head_trg[20];
- char type_ref[20], type_trg[20];
- void *buf_ref, *buf_trg, *buf_delta;
- unsigned long size_ref, size_trg, size_orig, size_delta;
- unsigned int depth_ref, depth_trg, depth_max = -1;
- int i, verbose = 0;
+ struct delta *ref, trg;
+ char ref_type[20], trg_type[20], *skip_reason;
+ void *best_buf;
+ unsigned long best_size, orig_size, orig_compsize;
+ unsigned int r, orig_ref, best_ref, nb_refs, next_ref, max_refs = 0;
+ unsigned int i, duplicate, skip_lvl, verbose = 0, quiet = 0;
+ unsigned int max_depth = -1;
for (i = 1; i < argc; i++) {
if (!strcmp(argv[i], "-v")) {
verbose = 1;
+ quiet = 0;
+ } else if (!strcmp(argv[i], "-q")) {
+ quiet = 1;
+ verbose = 0;
} else if (!strcmp(argv[i], "-d") && i+1 < argc) {
- depth_max = atoi(argv[++i]);
+ max_depth = atoi(argv[++i]);
} else if (!strncmp(argv[i], "--max-depth=", 12)) {
- depth_max = atoi(argv[i]+12);
+ max_depth = atoi(argv[i]+12);
+ } else if (!strcmp(argv[i], "-b") && i+1 < argc) {
+ max_refs = atoi(argv[++i]);
+ } else if (!strncmp(argv[i], "--max-behind=", 13)) {
+ max_refs = atoi(argv[i]+13);
} else
break;
}
- if (i + (depth_max != 0) >= argc)
+ if (i + (max_depth != 0) >= argc)
usage(mkdelta_usage);
- if (get_sha1(argv[i], sha1_ref))
- die("bad sha1 %s", argv[i]);
- depth_ref = 0;
- buf_ref = get_buffer(sha1_ref, type_ref, &size_ref);
- if (buf_ref && !strcmp(type_ref, "delta"))
- buf_ref = expand_delta(buf_ref, size_ref, type_ref,
- &size_ref, &depth_ref, head_ref);
- else
- memcpy(head_ref, sha1_ref, 20);
- if (!buf_ref)
- die("unable to obtain initial object %s", argv[i]);
+ if (!max_refs || max_refs > argc - i)
+ max_refs = argc - i;
+ ref = xmalloc(max_refs * sizeof(*ref));
+ for (r = 0; r < max_refs; r++)
+ ref[r].buf = ref[r].links = NULL;
+ next_ref = nb_refs = 0;
- if (depth_ref > depth_max) {
- if (restore_original_object(buf_ref, size_ref, type_ref, sha1_ref))
- die("unable to restore %s", argv[i]);
- if (verbose)
- printf("undelta %s (depth was %d)\n", argv[i], depth_ref);
- depth_ref = 0;
- }
-
- /*
- * TODO: deltafication should be tried against any early object
- * in the object list and not only the previous object.
- */
-
- while (++i < argc) {
- if (get_sha1(argv[i], sha1_trg))
+ do {
+ if (get_sha1(argv[i], trg.sha1))
die("bad sha1 %s", argv[i]);
- depth_trg = 0;
- buf_trg = get_buffer(sha1_trg, type_trg, &size_trg);
- if (buf_trg && !size_trg) {
+ trg.buf = get_buffer(trg.sha1, trg_type, &trg.size, &orig_compsize);
+ if (trg.buf && !trg.size) {
if (verbose)
printf("skip %s (object is empty)\n", argv[i]);
continue;
}
- size_orig = size_trg;
- if (buf_trg && !strcmp(type_trg, "delta")) {
- if (!memcmp(buf_trg, sha1_ref, 20)) {
- /* delta already in place */
- depth_ref++;
- memcpy(sha1_ref, sha1_trg, 20);
- buf_ref = patch_delta(buf_ref, size_ref,
- buf_trg+20, size_trg-20,
- &size_ref);
- if (!buf_ref)
- die("unable to apply delta %s", argv[i]);
- if (depth_ref > depth_max) {
- if (restore_original_object(buf_ref, size_ref,
- type_ref, sha1_ref))
- die("unable to restore %s", argv[i]);
- if (verbose)
- printf("undelta %s (depth was %d)\n", argv[i], depth_ref);
- depth_ref = 0;
- continue;
- }
- if (verbose)
- printf("skip %s (delta already in place)\n", argv[i]);
- continue;
+ orig_size = trg.size;
+ orig_ref = -1;
+ trg.depth = 0;
+ trg.links = NULL;
+ if (trg.buf && !strcmp(trg_type, "delta")) {
+ for (r = 0; r < nb_refs; r++)
+ if (!memcmp(trg.buf, ref[r].sha1, 20))
+ break;
+ if (r < nb_refs) {
+ /* no need to reload the reference object */
+ trg.depth = ref[r].depth + 1;
+ trg.links = xmalloc(trg.depth*20);
+ memcpy(trg.links, trg.buf, 20);
+ memcpy(trg.links+20, ref[r].links, ref[r].depth*20);
+ trg.buf = patch_delta(ref[r].buf, ref[r].size,
+ trg.buf+20, trg.size-20,
+ &trg.size);
+ strcpy(trg_type, ref_type);
+ orig_ref = r;
+ } else {
+ trg.buf = expand_delta(trg.buf, &trg.size, trg_type,
+ &trg.depth, &trg.links);
}
- buf_trg = expand_delta(buf_trg, size_trg, type_trg,
- &size_trg, &depth_trg, head_trg);
- } else
- memcpy(head_trg, sha1_trg, 20);
- if (!buf_trg)
- die("unable to read target object %s", argv[i]);
-
- if (depth_trg > depth_max) {
- if (restore_original_object(buf_trg, size_trg, type_trg, sha1_trg))
- die("unable to restore %s", argv[i]);
- if (verbose)
- printf("undelta %s (depth was %d)\n", argv[i], depth_trg);
- depth_trg = 0;
- size_orig = size_trg;
}
+ if (!trg.buf)
+ die("unable to read target object %s", argv[i]);
- if (depth_max == 0)
- goto skip;
-
- if (strcmp(type_ref, type_trg))
+ if (!nb_refs) {
+ strcpy(ref_type, trg_type);
+ } else if (max_depth && strcmp(ref_type, trg_type)) {
die("type mismatch for object %s", argv[i]);
-
- if (!size_ref) {
- if (verbose)
- printf("skip %s (initial object is empty)\n", argv[i]);
- goto skip;
- }
-
- if (depth_ref + 1 > depth_max) {
- if (verbose)
- printf("skip %s (exceeding max link depth)\n", argv[i]);
- goto skip;
}
- if (!memcmp(head_ref, sha1_trg, 20)) {
- if (verbose)
- printf("skip %s (would create a loop)\n", argv[i]);
- goto skip;
+ duplicate = 0;
+ best_buf = NULL;
+ best_size = -1;
+ best_ref = -1;
+ skip_lvl = 0;
+ skip_reason = NULL;
+ for (r = 0; max_depth && r < nb_refs; r++) {
+ void *delta_buf, *comp_buf;
+ unsigned long delta_size, comp_size;
+ unsigned int l;
+
+ duplicate = !memcmp(trg.sha1, ref[r].sha1, 20);
+ if (duplicate) {
+ skip_reason = "already seen";
+ break;
+ }
+ if (ref[r].depth >= max_depth) {
+ if (skip_lvl < 1) {
+ skip_reason = "exceeding max link depth";
+ skip_lvl = 1;
+ }
+ continue;
+ }
+ for (l = 0; l < ref[r].depth; l++)
+ if (!memcmp(trg.sha1, ref[r].links + l*20, 20))
+ break;
+ if (l != ref[r].depth) {
+ if (skip_lvl < 2) {
+ skip_reason = "would create a loop";
+ skip_lvl = 2;
+ }
+ continue;
+ }
+ if (trg.depth < max_depth && r == orig_ref) {
+ if (skip_lvl < 3) {
+ skip_reason = "delta already in place";
+ skip_lvl = 3;
+ }
+ continue;
+ }
+ delta_buf = diff_delta(ref[r].buf, ref[r].size,
+ trg.buf, trg.size, &delta_size);
+ if (!delta_buf)
+ die("out of memory");
+ if (trg.depth < max_depth &&
+ delta_size+20 >= orig_size) {
+ /* no need to even try to compress if original
+ object is smaller than this delta */
+ free(delta_buf);
+ if (skip_lvl < 4) {
+ skip_reason = "no size reduction";
+ skip_lvl = 4;
+ }
+ continue;
+ }
+ comp_buf = create_delta_object(delta_buf, delta_size,
+ ref[r].sha1, &comp_size);
+ if (!comp_buf)
+ die("out of memory");
+ free(delta_buf);
+ if (trg.depth < max_depth &&
+ comp_size >= orig_compsize) {
+ free(comp_buf);
+ if (skip_lvl < 5) {
+ skip_reason = "no size reduction";
+ skip_lvl = 5;
+ }
+ continue;
+ }
+ if ((comp_size < best_size) ||
+ (comp_size == best_size &&
+ ref[r].depth < ref[best_ref].depth)) {
+ free(best_buf);
+ best_buf = comp_buf;
+ best_size = comp_size;
+ best_ref = r;
+ }
}
- buf_delta = diff_delta(buf_ref, size_ref, buf_trg, size_trg, &size_delta);
- if (!buf_delta)
- die("out of memory");
-
- /* no need to even try to compress if original
- uncompressed is already smaller */
- if (size_delta+20 < size_orig) {
- void *buf_obj;
- unsigned long size_obj;
- buf_obj = create_delta_object(buf_delta, size_delta,
- sha1_ref, &size_obj);
- free(buf_delta);
- size_orig = get_object_size(sha1_trg);
- if (size_obj >= size_orig) {
- free(buf_obj);
- if (verbose)
- printf("skip %s (original is smaller)\n", argv[i]);
- goto skip;
- }
- if (replace_object(buf_obj, size_obj, sha1_trg))
+ if (best_buf) {
+ if (replace_object(best_buf, best_size, trg.sha1))
die("unable to write delta for %s", argv[i]);
- free(buf_obj);
- depth_ref++;
- if (verbose)
- printf("delta %s (size=%ld.%02ld%%, depth=%d)\n",
- argv[i], size_obj*100 / size_orig,
- (size_obj*10000 / size_orig)%100,
- depth_ref);
- } else {
- free(buf_delta);
- if (verbose)
- printf("skip %s (original is smaller)\n", argv[i]);
- skip:
- depth_ref = depth_trg;
- memcpy(head_ref, head_trg, 20);
+ free(best_buf);
+ free(trg.links);
+ trg.depth = ref[best_ref].depth + 1;
+ trg.links = xmalloc(trg.depth*20);
+ memcpy(trg.links, ref[best_ref].sha1, 20);
+ memcpy(trg.links+20, ref[best_ref].links, ref[best_ref].depth*20);
+ if (!quiet)
+ printf("delta %s (size=%ld.%02ld%% depth=%d dist=%d)\n",
+ argv[i], best_size*100 / orig_compsize,
+ (best_size*10000 / orig_compsize)%100,
+ trg.depth,
+ (next_ref - best_ref + max_refs)
+ % (max_refs + 1) + 1);
+ } else if (trg.depth > max_depth) {
+ if (restore_original_object(trg.buf, trg.size, trg_type, trg.sha1))
+ die("unable to restore %s", argv[i]);
+ if (!quiet)
+ printf("undelta %s (depth was %d)\n",
+ argv[i], trg.depth);
+ trg.depth = 0;
+ free(trg.links);
+ trg.links = NULL;
+ } else if (skip_reason && verbose) {
+ printf("skip %s (%s)\n", argv[i], skip_reason);
}
- free(buf_ref);
- buf_ref = buf_trg;
- size_ref = size_trg;
- memcpy(sha1_ref, sha1_trg, 20);
- }
+ if (!duplicate) {
+ free(ref[next_ref].buf);
+ free(ref[next_ref].links);
+ ref[next_ref] = trg;
+ if (++next_ref > nb_refs)
+ nb_refs = next_ref;
+ if (next_ref == max_refs)
+ next_ref = 0;
+ } else {
+ free(trg.buf);
+ free(trg.links);
+ }
+ } while (++i < argc);
return 0;
}
projects / git.git / blobdiff