Add a "max_size" parameter to diff_delta()
[git/git.git] / mkdelta.c
index 11c7e22..d4c5f3b 100644 (file)
--- a/mkdelta.c
+++ b/mkdelta.c
@@ -36,10 +36,10 @@ static int replace_object(char *buf, unsigned long size, unsigned char *sha1)
        return 0;
 }
 
-static void *create_object(char *buf, unsigned long len, char *hdr, int hdrlen,
-                          unsigned long *retsize)
+static void *create_object(unsigned char *buf, unsigned long len,
+                          char *hdr, int hdrlen, unsigned long *retsize)
 {
-       char *compressed;
+       unsigned char *compressed;
        unsigned long size;
        z_stream stream;
 
@@ -54,7 +54,7 @@ static void *create_object(char *buf, unsigned long len, char *hdr, int hdrlen,
        stream.avail_out = size;
 
        /* First header.. */
-       stream.next_in = hdr;
+       stream.next_in = (unsigned char *)hdr;
        stream.avail_in = hdrlen;
        while (deflate(&stream, 0) == Z_OK)
                /* nothing */;
@@ -69,7 +69,7 @@ static void *create_object(char *buf, unsigned long len, char *hdr, int hdrlen,
        return compressed;
 }
 
-static int restore_original_object(char *buf, unsigned long len,
+static int restore_original_object(unsigned char *buf, unsigned long len,
                                   char *type, unsigned char *sha1)
 {
        char hdr[50];
@@ -84,7 +84,7 @@ static int restore_original_object(char *buf, unsigned long len,
        return ret;
 }
 
-static void *create_delta_object(char *buf, unsigned long len,
+static void *create_delta_object(unsigned char *buf, unsigned long len,
                                 unsigned char *sha1_ref, unsigned long *size)
 {
        char hdr[50];
@@ -98,21 +98,16 @@ static void *create_delta_object(char *buf, unsigned long len,
        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;
        }
@@ -120,198 +115,250 @@ static void *get_buffer(unsigned char *sha1, char *type, unsigned long *size)
        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, ~0UL);
+                       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;
 }