{"thread":{"id":"738","subject":"[PATCH] mkdelta enhancements (take 2)","startedAt":"2005-05-27T19:29:00Z","lastAt":"2005-05-30T01:52:19Z","messageCount":2,"participants":["Nicolas Pitre"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"4072","messageId":"Pine.LNX.4.62.0505271511450.16151@localhost.localdomain","threadId":"738","inReplyTo":null,"subject":"[PATCH] mkdelta enhancements (take 2)","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2005-05-27T19:29:00Z","receivedAt":"2005-05-27T19:29:00Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"\nAlthough it was described as such, git-mkdelta didn't really attempt to\nfind the best delta against any previous object in the list but was only\nable to create a delta against the preceeding object.  This patch \nreworks the code to fix that limitation and hopefully makes it a bit\nclearer than before.\n\nThis means that\n\n        git-mkdelta sha1 sha2 sha3 sha4 sha5 sha6\n\nwill now create a sha2 delta against sha1, a sha3 delta against either\nsha2 or sha1 and keep the best one, a sha4 delta against either sha3,\nsha2 or sha1, etc.  The --max-behind argument limits that search for the\nbest delta to the specified number of previous objects in the list.  If\nno limit is specified it is unlimited (note: it might run out of \nmemory with long object lists).\n\nAlso added a -q (quiet) switch so it is possible to have 3 levels of\noutput: -q for nothing, -v for verbose, and if none of -q nor -v is\nspecified then only actual changes on the object database are shown.\n\nFinally the git-deltafy-script has been updated accordingly, and some \nbugs fixed (thanks to Stephen C. Tweedie for spotting them).\n\nThis version has been toroughly tested and I think it might be ready\nfor public consumption.\n\nSigned-off-by: Nicolas Pitre <nico@cam.org>\n\ndiff --git a/git-deltafy-script b/git-deltafy-script\nold mode 100644\nnew mode 100755\n--- a/git-deltafy-script\n+++ b/git-deltafy-script\n@@ -1,40 +1,67 @@\n #!/bin/bash\n \n-# Script to deltafy an entire GIT repository based on the commit list.\n+# Example script to deltafy an entire GIT repository based on the commit list.\n # The most recent version of a file is the reference and previous versions\n # are made delta against the best earlier version available. And so on for\n-# successive versions going back in time.  This way the delta overhead is\n-# pushed towards older version of any given file.\n-#\n-# NOTE: the \"best earlier version\" is not implemented in mkdelta yet\n-#       and therefore only the next eariler version is used at this time.\n-#\n-# TODO: deltafy tree objects as well.\n+# successive versions going back in time.  This way the increasing delta\n+# overhead is pushed towards older versions of any given file.\n #\n # The -d argument allows to provide a limit on the delta chain depth.\n-# If 0 is passed then everything is undeltafied.\n+# If 0 is passed then everything is undeltafied.  Limiting the delta\n+# depth is meaningful for subsequent access performance to old revisions.\n+# A value of 16 might be a good compromize between performance and good\n+# space saving.  Current default is unbounded.\n+#\n+# The --max-behind=30 argument is passed to git-mkdelta so to keep\n+# combinations and memory usage bounded a bit.  If you have lots of memory\n+# and CPU power you may remove it (or set to 0) to let git-mkdelta find the\n+# best delta match regardless of the number of revisions for a given file.\n+# You can also make the value smaller to make it faster and less\n+# memory hungry.  A value of 5 ought to still give pretty good results.\n+# When set to 0 or ommitted then look behind is unbounded.  Note that\n+# git-mkdelta might die with a segmentation fault in that case if it\n+# runs out of memory.  Note that the GIT repository will still be consistent\n+# even if git-mkdelta dies unexpectedly.\n \n set -e\n \n depth=\n [ \"$1\" == \"-d\" ] && depth=\"--max-depth=$2\" && shift 2\n \n+function process_list() {\n+\tif [ \"$list\" ]; then\n+\t\techo \"Processing $curr_file\"\n+\t\techo \"$head $list\" | xargs git-mkdelta $depth --max-behind=30 -v\n+\tfi\n+}\n+\n curr_file=\"\"\n \n git-rev-list HEAD |\n-git-diff-tree -r --stdin |\n-awk '/^:/ { if ($5 == \"M\" || $5 == \"N\") print $4, $6 }' |\n+git-diff-tree -r -t --stdin |\n+awk '/^:/ { if ($5 == \"M\" || $5 == \"N\") print $4, $6;\n+            if ($5 == \"M\") print $3, $6 }' |\n LC_ALL=C sort -s -k 2 | uniq |\n while read sha1 file; do\n \tif [ \"$file\" == \"$curr_file\" ]; then\n \t\tlist=\"$list $sha1\"\n \telse\n-\t\tif [ \"$list\" ]; then\n-\t\t\techo \"Processing $curr_file\"\n-\t\t\techo \"$head $list\" | xargs git-mkdelta $depth -v\n-\t\tfi\n+\t\tprocess_list\n \t\tcurr_file=\"$file\"\n \t\tlist=\"\"\n \t\thead=\"$sha1\"\n \tfi\n done\n+process_list\n+\n+curr_file=\"root directory\"\n+head=\"\"\n+list=\"$(\n+\tgit-rev-list HEAD |\n+\twhile read commit; do\n+\t\tgit-cat-file commit $commit |\n+\t\tsed -n 's/tree //p;Q'\n+\tdone\n+\t)\"\n+process_list\n+\ndiff --git a/mkdelta.c b/mkdelta.c\n--- a/mkdelta.c\n+++ b/mkdelta.c\n@@ -98,21 +98,16 @@ static void *create_delta_object(char *b\n \treturn create_object(buf, len, hdr, hdrlen, size);\n }\n \n-static unsigned long get_object_size(unsigned char *sha1)\n-{\n-\tstruct stat st;\n-\tif (stat(sha1_file_name(sha1), &st))\n-\t\tdie(\"%s: %s\", sha1_to_hex(sha1), strerror(errno));\n-\treturn st.st_size;\n-}\n-\n-static void *get_buffer(unsigned char *sha1, char *type, unsigned long *size)\n+static void *get_buffer(unsigned char *sha1, char *type,\n+\t\t\tunsigned long *size, unsigned long *compsize)\n {\n \tunsigned long mapsize;\n \tvoid *map = map_sha1_file(sha1, &mapsize);\n \tif (map) {\n \t\tvoid *buffer = unpack_sha1_file(map, mapsize, type, size);\n \t\tmunmap(map, mapsize);\n+\t\tif (compsize)\n+\t\t\t*compsize = mapsize;\n \t\tif (buffer)\n \t\t\treturn buffer;\n \t}\n@@ -120,198 +115,246 @@ static void *get_buffer(unsigned char *s\n \treturn NULL;\n }\n \n-static void *expand_delta(void *delta, unsigned long delta_size, char *type,\n-\t\t\t  unsigned long *size, unsigned int *depth, char *head)\n+static void *expand_delta(void *delta, unsigned long *size, char *type,\n+\t\t\t  unsigned int *depth, unsigned char **links)\n {\n \tvoid *buf = NULL;\n-\t*depth++;\n-\tif (delta_size < 20) {\n+\tunsigned int level = (*depth)++;\n+\tif (*size < 20) {\n \t\terror(\"delta object is bad\");\n \t\tfree(delta);\n \t} else {\n \t\tunsigned long ref_size;\n-\t\tvoid *ref = get_buffer(delta, type, &ref_size);\n+\t\tvoid *ref = get_buffer(delta, type, &ref_size, NULL);\n \t\tif (ref && !strcmp(type, \"delta\"))\n-\t\t\tref = expand_delta(ref, ref_size, type, &ref_size,\n-\t\t\t\t\t   depth, head);\n-\t\telse\n-\t\t\tmemcpy(head, delta, 20);\n-\t\tif (ref)\n-\t\t\tbuf = patch_delta(ref, ref_size, delta+20,\n-\t\t\t\t\t  delta_size-20, size);\n-\t\tfree(ref);\n+\t\t\tref = expand_delta(ref, &ref_size, type, depth, links);\n+\t\telse if (ref)\n+{\n+\t\t\t*links = xmalloc(*depth * 20);\n+}\n+\t\tif (ref) {\n+\t\t\tbuf = patch_delta(ref, ref_size, delta+20, *size-20, size);\n+\t\t\tfree(ref);\n+\t\t\tif (buf)\n+\t\t\t\tmemcpy(*links + level*20, delta, 20);\n+\t\t\telse\n+\t\t\t\tfree(*links);\n+\t\t}\n \t\tfree(delta);\n \t}\n \treturn buf;\n }\n \n static char *mkdelta_usage =\n-\"mkdelta [ --max-depth=N ] <reference_sha1> <target_sha1> [ <next_sha1> ... ]\";\n+\"mkdelta [--max-depth=N] [--max-behind=N] <reference_sha1> <target_sha1> [<next_sha1> ...]\";\n \n+struct delta {\n+\tunsigned char sha1[20];\t\t/* object sha1 */\n+\tunsigned long size;\t\t/* object size */\n+\tvoid *buf;\t\t\t/* object content */\n+\tunsigned char *links;\t\t/* delta reference links */\n+\tunsigned int depth;\t\t/* delta depth */\n+};\n+\t\n int main(int argc, char **argv)\n {\n-\tunsigned char sha1_ref[20], sha1_trg[20], head_ref[20], head_trg[20];\n-\tchar type_ref[20], type_trg[20];\n-\tvoid *buf_ref, *buf_trg, *buf_delta;\n-\tunsigned long size_ref, size_trg, size_orig, size_delta;\n-\tunsigned int depth_ref, depth_trg, depth_max = -1;\n-\tint i, verbose = 0;\n+\tstruct delta *ref, trg;\n+\tchar ref_type[20], trg_type[20], *skip_reason;\n+\tvoid *best_buf;\n+\tunsigned long best_size, orig_size, orig_compsize;\n+\tunsigned int r, orig_ref, best_ref, nb_refs, next_ref, max_refs = 0;\n+\tunsigned int i, duplicate, skip_lvl, verbose = 0, quiet = 0;\n+\tunsigned int max_depth = -1;\n \n \tfor (i = 1; i < argc; i++) {\n \t\tif (!strcmp(argv[i], \"-v\")) {\n \t\t\tverbose = 1;\n+\t\t\tquiet = 0;\n+\t\t} else if (!strcmp(argv[i], \"-q\")) {\n+\t\t\tquiet = 1;\n+\t\t\tverbose = 0;\n \t\t} else if (!strcmp(argv[i], \"-d\") && i+1 < argc) {\n-\t\t\tdepth_max = atoi(argv[++i]);\n+\t\t\tmax_depth = atoi(argv[++i]);\n \t\t} else if (!strncmp(argv[i], \"--max-depth=\", 12)) {\n-\t\t\tdepth_max = atoi(argv[i]+12);\n+\t\t\tmax_depth = atoi(argv[i]+12);\n+\t\t} else if (!strcmp(argv[i], \"-b\") && i+1 < argc) {\n+\t\t\tmax_refs = atoi(argv[++i]);\n+\t\t} else if (!strncmp(argv[i], \"--max-behind=\", 13)) {\n+\t\t\tmax_refs = atoi(argv[i]+13);\n \t\t} else\n \t\t\tbreak;\n \t}\n \n-\tif (i + (depth_max != 0) >= argc)\n+\tif (i + (max_depth != 0) >= argc)\n \t\tusage(mkdelta_usage);\n \n-\tif (get_sha1(argv[i], sha1_ref))\n-\t\tdie(\"bad sha1 %s\", argv[i]);\n-\tdepth_ref = 0;\n-\tbuf_ref = get_buffer(sha1_ref, type_ref, &size_ref);\n-\tif (buf_ref && !strcmp(type_ref, \"delta\"))\n-\t\tbuf_ref = expand_delta(buf_ref, size_ref, type_ref,\n-\t\t\t\t       &size_ref, &depth_ref, head_ref);\n-\telse\n-\t\tmemcpy(head_ref, sha1_ref, 20);\n-\tif (!buf_ref)\n-\t\tdie(\"unable to obtain initial object %s\", argv[i]);\n-\n-\tif (depth_ref > depth_max) {\n-\t\tif (restore_original_object(buf_ref, size_ref, type_ref, sha1_ref))\n-\t\t\tdie(\"unable to restore %s\", argv[i]);\n-\t\tif (verbose)\n-\t\t\tprintf(\"undelta %s (depth was %d)\\n\", argv[i], depth_ref);\n-\t\tdepth_ref = 0;\n-\t}\n-\n-\t/*\n-\t * TODO: deltafication should be tried against any early object\n-\t * in the object list and not only the previous object.\n-\t */\n+\tif (!max_refs || max_refs > argc - i)\n+\t\tmax_refs = argc - i;\n+\tref = xmalloc(max_refs * sizeof(*ref));\n+\tfor (r = 0; r < max_refs; r++)\n+\t\tref[r].buf = ref[r].links = NULL;\n+\tnext_ref = nb_refs = 0;\n \n-\twhile (++i < argc) {\n-\t\tif (get_sha1(argv[i], sha1_trg))\n+\tdo {\n+\t\tif (get_sha1(argv[i], trg.sha1))\n \t\t\tdie(\"bad sha1 %s\", argv[i]);\n-\t\tdepth_trg = 0;\n-\t\tbuf_trg = get_buffer(sha1_trg, type_trg, &size_trg);\n-\t\tif (buf_trg && !size_trg) {\n+\t\ttrg.buf = get_buffer(trg.sha1, trg_type, &trg.size, &orig_compsize);\n+\t\tif (trg.buf && !trg.size) {\n \t\t\tif (verbose)\n \t\t\t\tprintf(\"skip    %s (object is empty)\\n\", argv[i]);\n \t\t\tcontinue;\n \t\t}\n-\t\tsize_orig = size_trg;\n-\t\tif (buf_trg && !strcmp(type_trg, \"delta\")) {\n-\t\t\tif (!memcmp(buf_trg, sha1_ref, 20)) {\n-\t\t\t\t/* delta already in place */\n-\t\t\t\tdepth_ref++;\n-\t\t\t\tmemcpy(sha1_ref, sha1_trg, 20);\n-\t\t\t\tbuf_ref = patch_delta(buf_ref, size_ref,\n-\t\t\t\t\t\t      buf_trg+20, size_trg-20,\n-\t\t\t\t\t\t      &size_ref);\n-\t\t\t\tif (!buf_ref)\n-\t\t\t\t\tdie(\"unable to apply delta %s\", argv[i]);\n-\t\t\t\tif (depth_ref > depth_max) {\n-\t\t\t\t\tif (restore_original_object(buf_ref, size_ref,\n-\t\t\t\t\t\t\t\t    type_ref, sha1_ref))\n-\t\t\t\t\t\tdie(\"unable to restore %s\", argv[i]);\n-\t\t\t\t\tif (verbose)\n-\t\t\t\t\t\tprintf(\"undelta %s (depth was %d)\\n\", argv[i], depth_ref);\n-\t\t\t\t\tdepth_ref = 0;\n-\t\t\t\t\tcontinue;\n-\t\t\t\t}\n-\t\t\t\tif (verbose)\n-\t\t\t\t\tprintf(\"skip    %s (delta already in place)\\n\", argv[i]);\n-\t\t\t\tcontinue;\n+\t\torig_size = trg.size;\n+\t\torig_ref = -1;\n+\t\ttrg.depth = 0;\n+\t\ttrg.links = NULL;\n+\t\tif (trg.buf && !strcmp(trg_type, \"delta\")) {\n+\t\t\tfor (r = 0; r < nb_refs; r++)\n+\t\t\t\tif (!memcmp(trg.buf, ref[r].sha1, 20))\n+\t\t\t\t\tbreak;\n+\t\t\tif (r < nb_refs) {\n+\t\t\t\t/* no need to reload the reference object */\n+\t\t\t\ttrg.depth = ref[r].depth + 1;\n+\t\t\t\ttrg.links = xmalloc(trg.depth*20);\n+\t\t\t\tmemcpy(trg.links, trg.buf, 20);\n+\t\t\t\tmemcpy(trg.links+20, ref[r].links, ref[r].depth*20);\n+\t\t\t\ttrg.buf = patch_delta(ref[r].buf, ref[r].size,\n+\t\t\t\t\t\t      trg.buf+20, trg.size-20,\n+\t\t\t\t\t\t      &trg.size);\n+\t\t\t\tstrcpy(trg_type, ref_type);\n+\t\t\t\torig_ref = r;\n+\t\t\t} else {\n+\t\t\t\ttrg.buf = expand_delta(trg.buf, &trg.size, trg_type,\n+\t\t\t\t\t\t       &trg.depth, &trg.links);\n \t\t\t}\n-\t\t\tbuf_trg = expand_delta(buf_trg, size_trg, type_trg,\n-\t\t\t\t\t       &size_trg, &depth_trg, head_trg);\n-\t\t} else\n-\t\t\tmemcpy(head_trg, sha1_trg, 20);\n-\t\tif (!buf_trg)\n-\t\t\tdie(\"unable to read target object %s\", argv[i]);\n-\n-\t\tif (depth_trg > depth_max) {\n-\t\t\tif (restore_original_object(buf_trg, size_trg, type_trg, sha1_trg))\n-\t\t\t\tdie(\"unable to restore %s\", argv[i]);\n-\t\t\tif (verbose)\n-\t\t\t\tprintf(\"undelta %s (depth was %d)\\n\", argv[i], depth_trg);\n-\t\t\tdepth_trg = 0;\n-\t\t\tsize_orig = size_trg;\n \t\t}\n+\t\tif (!trg.buf)\n+\t\t\tdie(\"unable to read target object %s\", argv[i]);\n \n-\t\tif (depth_max == 0)\n-\t\t\tgoto skip;\n-\n-\t\tif (strcmp(type_ref, type_trg))\n+\t\tif (!nb_refs) {\n+\t\t\tstrcpy(ref_type, trg_type);\n+\t\t} else if (max_depth && strcmp(ref_type, trg_type)) {\n \t\t\tdie(\"type mismatch for object %s\", argv[i]);\n-\n-\t\tif (!size_ref) {\n-\t\t\tif (verbose)\n-\t\t\t\tprintf(\"skip    %s (initial object is empty)\\n\", argv[i]);\n-\t\t\tgoto skip;\n-\t\t}\n-\t\t\n-\t\tif (depth_ref + 1 > depth_max) {\n-\t\t\tif (verbose)\n-\t\t\t\tprintf(\"skip    %s (exceeding max link depth)\\n\", argv[i]);\n-\t\t\tgoto skip;\n \t\t}\n \n-\t\tif (!memcmp(head_ref, sha1_trg, 20)) {\n-\t\t\tif (verbose)\n-\t\t\t\tprintf(\"skip    %s (would create a loop)\\n\", argv[i]);\n-\t\t\tgoto skip;\n+\t\tduplicate = 0;\n+\t\tbest_buf = NULL;\n+\t\tbest_size = -1;\n+\t\tbest_ref = -1;\n+\t\tskip_lvl = 0;\n+\t\tskip_reason = NULL;\n+\t\tfor (r = 0; max_depth && r < nb_refs; r++) {\n+\t\t\tvoid *delta_buf, *comp_buf;\n+\t\t\tunsigned long delta_size, comp_size;\n+\t\t\tunsigned int l;\n+\n+\t\t\tduplicate = !memcmp(trg.sha1, ref[r].sha1, 20);\n+\t\t\tif (duplicate) {\n+\t\t\t\tskip_reason = \"already seen\";\n+\t\t\t\tbreak;\n+\t\t\t}\n+\t\t\tif (ref[r].depth >= max_depth) {\n+\t\t\t\tif (skip_lvl < 1) {\n+\t\t\t\t\tskip_reason = \"exceeding max link depth\";\n+\t\t\t\t\tskip_lvl = 1;\n+\t\t\t\t}\n+\t\t\t\tcontinue;\n+\t\t\t}\n+\t\t\tfor (l = 0; l < ref[r].depth; l++)\n+\t\t\t\tif (!memcmp(trg.sha1, ref[r].links + l*20, 20))\n+\t\t\t\t\tbreak;\n+\t\t\tif (l != ref[r].depth) {\n+\t\t\t\tif (skip_lvl < 2) {\n+\t\t\t\t\tskip_reason = \"would create a loop\";\n+\t\t\t\t\tskip_lvl = 2;\n+\t\t\t\t}\n+\t\t\t\tcontinue;\n+\t\t\t}\n+\t\t\tif (trg.depth < max_depth && r == orig_ref) {\n+\t\t\t\tif (skip_lvl < 3) {\n+\t\t\t\t\tskip_reason = \"delta already in place\";\n+\t\t\t\t\tskip_lvl = 3;\n+\t\t\t\t}\n+\t\t\t\tcontinue;\n+\t\t\t}\n+\t\t\tdelta_buf = diff_delta(ref[r].buf, ref[r].size,\n+\t\t\t\t\t       trg.buf, trg.size, &delta_size);\n+\t\t\tif (!delta_buf)\n+\t\t\t\tdie(\"out of memory\");\n+\t\t\tif (trg.depth < max_depth &&\n+\t\t\t    delta_size+20 >= orig_size) {\n+\t\t\t\t/* no need to even try to compress if original\n+\t\t\t\t   object is smaller than this delta */\n+\t\t\t\tfree(delta_buf);\n+\t\t\t\tif (skip_lvl < 4) {\n+\t\t\t\t\tskip_reason = \"no size reduction\";\n+\t\t\t\t\tskip_lvl = 4;\n+\t\t\t\t}\n+\t\t\t\tcontinue;\n+\t\t\t}\n+\t\t\tcomp_buf = create_delta_object(delta_buf, delta_size,\n+\t\t\t\t\t\t       ref[r].sha1, &comp_size);\n+\t\t\tif (!comp_buf)\n+\t\t\t\tdie(\"out of memory\");\n+\t\t\tfree(delta_buf);\n+\t\t\tif (trg.depth < max_depth &&\n+\t\t\t    comp_size >= orig_compsize) {\n+\t\t\t\tfree(comp_buf);\n+\t\t\t\tif (skip_lvl < 5) {\n+\t\t\t\t\tskip_reason = \"no size reduction\";\n+\t\t\t\t\tskip_lvl = 5;\n+\t\t\t\t}\n+\t\t\t\tcontinue;\n+\t\t\t}\n+\t\t\tif ((comp_size < best_size) ||\n+\t\t\t    (comp_size == best_size &&\n+\t\t\t     ref[r].depth < ref[best_ref].depth)) {\n+\t\t\t\tfree(best_buf);\n+\t\t\t\tbest_buf = comp_buf;\n+\t\t\t\tbest_size = comp_size;\n+\t\t\t\tbest_ref = r;\n+\t\t\t}\n \t\t}\n \n-\t\tbuf_delta = diff_delta(buf_ref, size_ref, buf_trg, size_trg, &size_delta);\n-\t\tif (!buf_delta)\n-\t\t\tdie(\"out of memory\");\n-\n-\t\t/* no need to even try to compress if original\n-\t\t   uncompressed is already smaller */\n-\t\tif (size_delta+20 < size_orig) {\n-\t\t\tvoid *buf_obj;\n-\t\t\tunsigned long size_obj;\n-\t\t\tbuf_obj = create_delta_object(buf_delta, size_delta,\n-\t\t\t\t\t\t      sha1_ref, &size_obj);\n-\t\t\tfree(buf_delta);\n-\t\t\tsize_orig = get_object_size(sha1_trg);\n-\t\t\tif (size_obj >= size_orig) {\n-\t\t\t\tfree(buf_obj);\n-\t\t\t\tif (verbose)\n-\t\t\t\t\tprintf(\"skip    %s (original is smaller)\\n\", argv[i]);\n-\t\t\t\tgoto skip;\n-\t\t\t}\n-\t\t\tif (replace_object(buf_obj, size_obj, sha1_trg))\n+\t\tif (best_buf) {\n+\t\t\tif (replace_object(best_buf, best_size, trg.sha1))\n \t\t\t\tdie(\"unable to write delta for %s\", argv[i]);\n-\t\t\tfree(buf_obj);\n-\t\t\tdepth_ref++;\n-\t\t\tif (verbose)\n-\t\t\t\tprintf(\"delta   %s (size=%ld.%02ld%%, depth=%d)\\n\",\n-\t\t\t\t       argv[i], size_obj*100 / size_orig,\n-\t\t\t\t       (size_obj*10000 / size_orig)%100,\n-\t\t\t\t       depth_ref);\n-\t\t} else {\n-\t\t\tfree(buf_delta);\n-\t\t\tif (verbose)\n-\t\t\t\tprintf(\"skip    %s (original is smaller)\\n\", argv[i]);\n-\t\t\tskip:\n-\t\t\tdepth_ref = depth_trg;\n-\t\t\tmemcpy(head_ref, head_trg, 20);\n+\t\t\tfree(best_buf);\n+\t\t\tfree(trg.links);\n+\t\t\ttrg.depth = ref[best_ref].depth + 1;\n+\t\t\ttrg.links = xmalloc(trg.depth*20);\n+\t\t\tmemcpy(trg.links, ref[best_ref].sha1, 20);\n+\t\t\tmemcpy(trg.links+20, ref[best_ref].links, ref[best_ref].depth*20);\n+\t\t\tif (!quiet)\n+\t\t\t\tprintf(\"delta   %s (size=%ld.%02ld%% depth=%d dist=%d)\\n\",\n+\t\t\t\t       argv[i], best_size*100 / orig_compsize,\n+\t\t\t\t       (best_size*10000 / orig_compsize)%100,\n+\t\t\t\t       trg.depth,\n+\t\t\t\t       (next_ref - best_ref + max_refs)\n+\t\t\t\t       % (max_refs + 1) + 1);\n+\t\t} else if (trg.depth > max_depth) {\n+\t\t\tif (restore_original_object(trg.buf, trg.size, trg_type, trg.sha1))\n+\t\t\t\tdie(\"unable to restore %s\", argv[i]);\n+\t\t\tif (!quiet)\n+\t\t\t\tprintf(\"undelta %s (depth was %d)\\n\",\n+\t\t\t\t       argv[i], trg.depth);\n+\t\t\ttrg.depth = 0;\n+\t\t\tfree(trg.links);\n+\t\t\ttrg.links = NULL;\n+\t\t} else if (skip_reason && verbose) {\n+\t\t\tprintf(\"skip    %s (%s)\\n\", argv[i], skip_reason);\n \t\t}\n \n-\t\tfree(buf_ref);\n-\t\tbuf_ref = buf_trg;\n-\t\tsize_ref = size_trg;\n-\t\tmemcpy(sha1_ref, sha1_trg, 20);\n-\t}\n+\t\tif (!duplicate) {\n+\t\t\tfree(ref[next_ref].buf);\n+\t\t\tfree(ref[next_ref].links);\n+\t\t\tref[next_ref] = trg;\n+\t\t\tif (++next_ref > nb_refs)\n+\t\t\t\tnb_refs = next_ref;\n+\t\t\tif (next_ref == max_refs)\n+\t\t\t\tnext_ref = 0;\n+\t\t}\n+\t} while (++i < argc);\n \n \treturn 0;\n }\n"},{"id":"4227","messageId":"Pine.LNX.4.62.0505292141160.5666@localhost.localdomain","threadId":"738","inReplyTo":"Pine.LNX.4.62.0505271511450.16151@localhost.localdomain","subject":"[PATCH / RESEND] mkdelta enhancements (take 2)","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2005-05-30T01:52:19Z","receivedAt":"2005-05-30T01:52:19Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"\nLinus, please apply.\n\nCurrent version of mkdelta has the potential to corrupt a repository and \nI'd like for that problem to go away ASAP before it creates too much \ndammage.\n\n==========\n\nAlthough it was described as such, git-mkdelta didn't really attempt to\nfind the best delta against any previous object in the list, but was \nonly able to create a delta against the preceeding object.  This patch \nreworks the code to fix that limitation and hopefully makes it a bit\nclearer than before, including fixing the delta loop detection which was \nbroken.\n\nThis means that\n\n\tgit-mkdelta sha1 sha2 sha3 sha4 sha5 sha6\n\nwill now create a sha2 delta against sha1, a sha3 delta against either\nsha2 or sha1 and keep the best one, a sha4 delta against either sha3,\nsha2 or sha1, etc.  The --max-behind argument limits that search for the\nbest delta to the specified number of previous objects in the list.  If\nno limit is specified it is unlimited (note: it might run out of \nmemory with long object lists).\n\nAlso added a -q (quiet) switch so it is possible to have 3 levels of\noutput: -q for nothing, -v for verbose, and if none of -q nor -v is\nspecified then only actual changes on the object database are shown.\n\nFinally the git-deltafy-script has been updated accordingly, and some \nbugs fixed (thanks to Stephen C. Tweedie for spotting them).\n\nThis version has been toroughly tested and I think it is ready\nfor public consumption.\n\nSigned-off-by: Nicolas Pitre <nico@cam.org>\n\ndiff --git a/git-deltafy-script b/git-deltafy-script\nold mode 100644\nnew mode 100755\n--- a/git-deltafy-script\n+++ b/git-deltafy-script\n@@ -1,40 +1,67 @@\n #!/bin/bash\n \n-# Script to deltafy an entire GIT repository based on the commit list.\n+# Example script to deltafy an entire GIT repository based on the commit list.\n # The most recent version of a file is the reference and previous versions\n # are made delta against the best earlier version available. And so on for\n-# successive versions going back in time.  This way the delta overhead is\n-# pushed towards older version of any given file.\n-#\n-# NOTE: the \"best earlier version\" is not implemented in mkdelta yet\n-#       and therefore only the next eariler version is used at this time.\n-#\n-# TODO: deltafy tree objects as well.\n+# successive versions going back in time.  This way the increasing delta\n+# overhead is pushed towards older versions of any given file.\n #\n # The -d argument allows to provide a limit on the delta chain depth.\n-# If 0 is passed then everything is undeltafied.\n+# If 0 is passed then everything is undeltafied.  Limiting the delta\n+# depth is meaningful for subsequent access performance to old revisions.\n+# A value of 16 might be a good compromize between performance and good\n+# space saving.  Current default is unbounded.\n+#\n+# The --max-behind=30 argument is passed to git-mkdelta so to keep\n+# combinations and memory usage bounded a bit.  If you have lots of memory\n+# and CPU power you may remove it (or set to 0) to let git-mkdelta find the\n+# best delta match regardless of the number of revisions for a given file.\n+# You can also make the value smaller to make it faster and less\n+# memory hungry.  A value of 5 ought to still give pretty good results.\n+# When set to 0 or ommitted then look behind is unbounded.  Note that\n+# git-mkdelta might die with a segmentation fault in that case if it\n+# runs out of memory.  Note that the GIT repository will still be consistent\n+# even if git-mkdelta dies unexpectedly.\n \n set -e\n \n depth=\n [ \"$1\" == \"-d\" ] && depth=\"--max-depth=$2\" && shift 2\n \n+function process_list() {\n+\tif [ \"$list\" ]; then\n+\t\techo \"Processing $curr_file\"\n+\t\techo \"$head $list\" | xargs git-mkdelta $depth --max-behind=30 -v\n+\tfi\n+}\n+\n curr_file=\"\"\n \n git-rev-list HEAD |\n-git-diff-tree -r --stdin |\n-awk '/^:/ { if ($5 == \"M\" || $5 == \"N\") print $4, $6 }' |\n+git-diff-tree -r -t --stdin |\n+awk '/^:/ { if ($5 == \"M\" || $5 == \"N\") print $4, $6;\n+            if ($5 == \"M\") print $3, $6 }' |\n LC_ALL=C sort -s -k 2 | uniq |\n while read sha1 file; do\n \tif [ \"$file\" == \"$curr_file\" ]; then\n \t\tlist=\"$list $sha1\"\n \telse\n-\t\tif [ \"$list\" ]; then\n-\t\t\techo \"Processing $curr_file\"\n-\t\t\techo \"$head $list\" | xargs git-mkdelta $depth -v\n-\t\tfi\n+\t\tprocess_list\n \t\tcurr_file=\"$file\"\n \t\tlist=\"\"\n \t\thead=\"$sha1\"\n \tfi\n done\n+process_list\n+\n+curr_file=\"root directory\"\n+head=\"\"\n+list=\"$(\n+\tgit-rev-list HEAD |\n+\twhile read commit; do\n+\t\tgit-cat-file commit $commit |\n+\t\tsed -n 's/tree //p;Q'\n+\tdone\n+\t)\"\n+process_list\n+\ndiff --git a/mkdelta.c b/mkdelta.c\n--- a/mkdelta.c\n+++ b/mkdelta.c\n@@ -98,21 +98,16 @@ static void *create_delta_object(char *b\n \treturn create_object(buf, len, hdr, hdrlen, size);\n }\n \n-static unsigned long get_object_size(unsigned char *sha1)\n-{\n-\tstruct stat st;\n-\tif (stat(sha1_file_name(sha1), &st))\n-\t\tdie(\"%s: %s\", sha1_to_hex(sha1), strerror(errno));\n-\treturn st.st_size;\n-}\n-\n-static void *get_buffer(unsigned char *sha1, char *type, unsigned long *size)\n+static void *get_buffer(unsigned char *sha1, char *type,\n+\t\t\tunsigned long *size, unsigned long *compsize)\n {\n \tunsigned long mapsize;\n \tvoid *map = map_sha1_file(sha1, &mapsize);\n \tif (map) {\n \t\tvoid *buffer = unpack_sha1_file(map, mapsize, type, size);\n \t\tmunmap(map, mapsize);\n+\t\tif (compsize)\n+\t\t\t*compsize = mapsize;\n \t\tif (buffer)\n \t\t\treturn buffer;\n \t}\n@@ -120,198 +115,249 @@ static void *get_buffer(unsigned char *s\n \treturn NULL;\n }\n \n-static void *expand_delta(void *delta, unsigned long delta_size, char *type,\n-\t\t\t  unsigned long *size, unsigned int *depth, char *head)\n+static void *expand_delta(void *delta, unsigned long *size, char *type,\n+\t\t\t  unsigned int *depth, unsigned char **links)\n {\n \tvoid *buf = NULL;\n-\t*depth++;\n-\tif (delta_size < 20) {\n+\tunsigned int level = (*depth)++;\n+\tif (*size < 20) {\n \t\terror(\"delta object is bad\");\n \t\tfree(delta);\n \t} else {\n \t\tunsigned long ref_size;\n-\t\tvoid *ref = get_buffer(delta, type, &ref_size);\n+\t\tvoid *ref = get_buffer(delta, type, &ref_size, NULL);\n \t\tif (ref && !strcmp(type, \"delta\"))\n-\t\t\tref = expand_delta(ref, ref_size, type, &ref_size,\n-\t\t\t\t\t   depth, head);\n-\t\telse\n-\t\t\tmemcpy(head, delta, 20);\n-\t\tif (ref)\n-\t\t\tbuf = patch_delta(ref, ref_size, delta+20,\n-\t\t\t\t\t  delta_size-20, size);\n-\t\tfree(ref);\n+\t\t\tref = expand_delta(ref, &ref_size, type, depth, links);\n+\t\telse if (ref)\n+{\n+\t\t\t*links = xmalloc(*depth * 20);\n+}\n+\t\tif (ref) {\n+\t\t\tbuf = patch_delta(ref, ref_size, delta+20, *size-20, size);\n+\t\t\tfree(ref);\n+\t\t\tif (buf)\n+\t\t\t\tmemcpy(*links + level*20, delta, 20);\n+\t\t\telse\n+\t\t\t\tfree(*links);\n+\t\t}\n \t\tfree(delta);\n \t}\n \treturn buf;\n }\n \n static char *mkdelta_usage =\n-\"mkdelta [ --max-depth=N ] <reference_sha1> <target_sha1> [ <next_sha1> ... ]\";\n+\"mkdelta [--max-depth=N] [--max-behind=N] <reference_sha1> <target_sha1> [<next_sha1> ...]\";\n \n+struct delta {\n+\tunsigned char sha1[20];\t\t/* object sha1 */\n+\tunsigned long size;\t\t/* object size */\n+\tvoid *buf;\t\t\t/* object content */\n+\tunsigned char *links;\t\t/* delta reference links */\n+\tunsigned int depth;\t\t/* delta depth */\n+};\n+\t\n int main(int argc, char **argv)\n {\n-\tunsigned char sha1_ref[20], sha1_trg[20], head_ref[20], head_trg[20];\n-\tchar type_ref[20], type_trg[20];\n-\tvoid *buf_ref, *buf_trg, *buf_delta;\n-\tunsigned long size_ref, size_trg, size_orig, size_delta;\n-\tunsigned int depth_ref, depth_trg, depth_max = -1;\n-\tint i, verbose = 0;\n+\tstruct delta *ref, trg;\n+\tchar ref_type[20], trg_type[20], *skip_reason;\n+\tvoid *best_buf;\n+\tunsigned long best_size, orig_size, orig_compsize;\n+\tunsigned int r, orig_ref, best_ref, nb_refs, next_ref, max_refs = 0;\n+\tunsigned int i, duplicate, skip_lvl, verbose = 0, quiet = 0;\n+\tunsigned int max_depth = -1;\n \n \tfor (i = 1; i < argc; i++) {\n \t\tif (!strcmp(argv[i], \"-v\")) {\n \t\t\tverbose = 1;\n+\t\t\tquiet = 0;\n+\t\t} else if (!strcmp(argv[i], \"-q\")) {\n+\t\t\tquiet = 1;\n+\t\t\tverbose = 0;\n \t\t} else if (!strcmp(argv[i], \"-d\") && i+1 < argc) {\n-\t\t\tdepth_max = atoi(argv[++i]);\n+\t\t\tmax_depth = atoi(argv[++i]);\n \t\t} else if (!strncmp(argv[i], \"--max-depth=\", 12)) {\n-\t\t\tdepth_max = atoi(argv[i]+12);\n+\t\t\tmax_depth = atoi(argv[i]+12);\n+\t\t} else if (!strcmp(argv[i], \"-b\") && i+1 < argc) {\n+\t\t\tmax_refs = atoi(argv[++i]);\n+\t\t} else if (!strncmp(argv[i], \"--max-behind=\", 13)) {\n+\t\t\tmax_refs = atoi(argv[i]+13);\n \t\t} else\n \t\t\tbreak;\n \t}\n \n-\tif (i + (depth_max != 0) >= argc)\n+\tif (i + (max_depth != 0) >= argc)\n \t\tusage(mkdelta_usage);\n \n-\tif (get_sha1(argv[i], sha1_ref))\n-\t\tdie(\"bad sha1 %s\", argv[i]);\n-\tdepth_ref = 0;\n-\tbuf_ref = get_buffer(sha1_ref, type_ref, &size_ref);\n-\tif (buf_ref && !strcmp(type_ref, \"delta\"))\n-\t\tbuf_ref = expand_delta(buf_ref, size_ref, type_ref,\n-\t\t\t\t       &size_ref, &depth_ref, head_ref);\n-\telse\n-\t\tmemcpy(head_ref, sha1_ref, 20);\n-\tif (!buf_ref)\n-\t\tdie(\"unable to obtain initial object %s\", argv[i]);\n-\n-\tif (depth_ref > depth_max) {\n-\t\tif (restore_original_object(buf_ref, size_ref, type_ref, sha1_ref))\n-\t\t\tdie(\"unable to restore %s\", argv[i]);\n-\t\tif (verbose)\n-\t\t\tprintf(\"undelta %s (depth was %d)\\n\", argv[i], depth_ref);\n-\t\tdepth_ref = 0;\n-\t}\n-\n-\t/*\n-\t * TODO: deltafication should be tried against any early object\n-\t * in the object list and not only the previous object.\n-\t */\n+\tif (!max_refs || max_refs > argc - i)\n+\t\tmax_refs = argc - i;\n+\tref = xmalloc(max_refs * sizeof(*ref));\n+\tfor (r = 0; r < max_refs; r++)\n+\t\tref[r].buf = ref[r].links = NULL;\n+\tnext_ref = nb_refs = 0;\n \n-\twhile (++i < argc) {\n-\t\tif (get_sha1(argv[i], sha1_trg))\n+\tdo {\n+\t\tif (get_sha1(argv[i], trg.sha1))\n \t\t\tdie(\"bad sha1 %s\", argv[i]);\n-\t\tdepth_trg = 0;\n-\t\tbuf_trg = get_buffer(sha1_trg, type_trg, &size_trg);\n-\t\tif (buf_trg && !size_trg) {\n+\t\ttrg.buf = get_buffer(trg.sha1, trg_type, &trg.size, &orig_compsize);\n+\t\tif (trg.buf && !trg.size) {\n \t\t\tif (verbose)\n \t\t\t\tprintf(\"skip    %s (object is empty)\\n\", argv[i]);\n \t\t\tcontinue;\n \t\t}\n-\t\tsize_orig = size_trg;\n-\t\tif (buf_trg && !strcmp(type_trg, \"delta\")) {\n-\t\t\tif (!memcmp(buf_trg, sha1_ref, 20)) {\n-\t\t\t\t/* delta already in place */\n-\t\t\t\tdepth_ref++;\n-\t\t\t\tmemcpy(sha1_ref, sha1_trg, 20);\n-\t\t\t\tbuf_ref = patch_delta(buf_ref, size_ref,\n-\t\t\t\t\t\t      buf_trg+20, size_trg-20,\n-\t\t\t\t\t\t      &size_ref);\n-\t\t\t\tif (!buf_ref)\n-\t\t\t\t\tdie(\"unable to apply delta %s\", argv[i]);\n-\t\t\t\tif (depth_ref > depth_max) {\n-\t\t\t\t\tif (restore_original_object(buf_ref, size_ref,\n-\t\t\t\t\t\t\t\t    type_ref, sha1_ref))\n-\t\t\t\t\t\tdie(\"unable to restore %s\", argv[i]);\n-\t\t\t\t\tif (verbose)\n-\t\t\t\t\t\tprintf(\"undelta %s (depth was %d)\\n\", argv[i], depth_ref);\n-\t\t\t\t\tdepth_ref = 0;\n-\t\t\t\t\tcontinue;\n-\t\t\t\t}\n-\t\t\t\tif (verbose)\n-\t\t\t\t\tprintf(\"skip    %s (delta already in place)\\n\", argv[i]);\n-\t\t\t\tcontinue;\n+\t\torig_size = trg.size;\n+\t\torig_ref = -1;\n+\t\ttrg.depth = 0;\n+\t\ttrg.links = NULL;\n+\t\tif (trg.buf && !strcmp(trg_type, \"delta\")) {\n+\t\t\tfor (r = 0; r < nb_refs; r++)\n+\t\t\t\tif (!memcmp(trg.buf, ref[r].sha1, 20))\n+\t\t\t\t\tbreak;\n+\t\t\tif (r < nb_refs) {\n+\t\t\t\t/* no need to reload the reference object */\n+\t\t\t\ttrg.depth = ref[r].depth + 1;\n+\t\t\t\ttrg.links = xmalloc(trg.depth*20);\n+\t\t\t\tmemcpy(trg.links, trg.buf, 20);\n+\t\t\t\tmemcpy(trg.links+20, ref[r].links, ref[r].depth*20);\n+\t\t\t\ttrg.buf = patch_delta(ref[r].buf, ref[r].size,\n+\t\t\t\t\t\t      trg.buf+20, trg.size-20,\n+\t\t\t\t\t\t      &trg.size);\n+\t\t\t\tstrcpy(trg_type, ref_type);\n+\t\t\t\torig_ref = r;\n+\t\t\t} else {\n+\t\t\t\ttrg.buf = expand_delta(trg.buf, &trg.size, trg_type,\n+\t\t\t\t\t\t       &trg.depth, &trg.links);\n \t\t\t}\n-\t\t\tbuf_trg = expand_delta(buf_trg, size_trg, type_trg,\n-\t\t\t\t\t       &size_trg, &depth_trg, head_trg);\n-\t\t} else\n-\t\t\tmemcpy(head_trg, sha1_trg, 20);\n-\t\tif (!buf_trg)\n-\t\t\tdie(\"unable to read target object %s\", argv[i]);\n-\n-\t\tif (depth_trg > depth_max) {\n-\t\t\tif (restore_original_object(buf_trg, size_trg, type_trg, sha1_trg))\n-\t\t\t\tdie(\"unable to restore %s\", argv[i]);\n-\t\t\tif (verbose)\n-\t\t\t\tprintf(\"undelta %s (depth was %d)\\n\", argv[i], depth_trg);\n-\t\t\tdepth_trg = 0;\n-\t\t\tsize_orig = size_trg;\n \t\t}\n+\t\tif (!trg.buf)\n+\t\t\tdie(\"unable to read target object %s\", argv[i]);\n \n-\t\tif (depth_max == 0)\n-\t\t\tgoto skip;\n-\n-\t\tif (strcmp(type_ref, type_trg))\n+\t\tif (!nb_refs) {\n+\t\t\tstrcpy(ref_type, trg_type);\n+\t\t} else if (max_depth && strcmp(ref_type, trg_type)) {\n \t\t\tdie(\"type mismatch for object %s\", argv[i]);\n-\n-\t\tif (!size_ref) {\n-\t\t\tif (verbose)\n-\t\t\t\tprintf(\"skip    %s (initial object is empty)\\n\", argv[i]);\n-\t\t\tgoto skip;\n-\t\t}\n-\t\t\n-\t\tif (depth_ref + 1 > depth_max) {\n-\t\t\tif (verbose)\n-\t\t\t\tprintf(\"skip    %s (exceeding max link depth)\\n\", argv[i]);\n-\t\t\tgoto skip;\n \t\t}\n \n-\t\tif (!memcmp(head_ref, sha1_trg, 20)) {\n-\t\t\tif (verbose)\n-\t\t\t\tprintf(\"skip    %s (would create a loop)\\n\", argv[i]);\n-\t\t\tgoto skip;\n+\t\tduplicate = 0;\n+\t\tbest_buf = NULL;\n+\t\tbest_size = -1;\n+\t\tbest_ref = -1;\n+\t\tskip_lvl = 0;\n+\t\tskip_reason = NULL;\n+\t\tfor (r = 0; max_depth && r < nb_refs; r++) {\n+\t\t\tvoid *delta_buf, *comp_buf;\n+\t\t\tunsigned long delta_size, comp_size;\n+\t\t\tunsigned int l;\n+\n+\t\t\tduplicate = !memcmp(trg.sha1, ref[r].sha1, 20);\n+\t\t\tif (duplicate) {\n+\t\t\t\tskip_reason = \"already seen\";\n+\t\t\t\tbreak;\n+\t\t\t}\n+\t\t\tif (ref[r].depth >= max_depth) {\n+\t\t\t\tif (skip_lvl < 1) {\n+\t\t\t\t\tskip_reason = \"exceeding max link depth\";\n+\t\t\t\t\tskip_lvl = 1;\n+\t\t\t\t}\n+\t\t\t\tcontinue;\n+\t\t\t}\n+\t\t\tfor (l = 0; l < ref[r].depth; l++)\n+\t\t\t\tif (!memcmp(trg.sha1, ref[r].links + l*20, 20))\n+\t\t\t\t\tbreak;\n+\t\t\tif (l != ref[r].depth) {\n+\t\t\t\tif (skip_lvl < 2) {\n+\t\t\t\t\tskip_reason = \"would create a loop\";\n+\t\t\t\t\tskip_lvl = 2;\n+\t\t\t\t}\n+\t\t\t\tcontinue;\n+\t\t\t}\n+\t\t\tif (trg.depth < max_depth && r == orig_ref) {\n+\t\t\t\tif (skip_lvl < 3) {\n+\t\t\t\t\tskip_reason = \"delta already in place\";\n+\t\t\t\t\tskip_lvl = 3;\n+\t\t\t\t}\n+\t\t\t\tcontinue;\n+\t\t\t}\n+\t\t\tdelta_buf = diff_delta(ref[r].buf, ref[r].size,\n+\t\t\t\t\t       trg.buf, trg.size, &delta_size);\n+\t\t\tif (!delta_buf)\n+\t\t\t\tdie(\"out of memory\");\n+\t\t\tif (trg.depth < max_depth &&\n+\t\t\t    delta_size+20 >= orig_size) {\n+\t\t\t\t/* no need to even try to compress if original\n+\t\t\t\t   object is smaller than this delta */\n+\t\t\t\tfree(delta_buf);\n+\t\t\t\tif (skip_lvl < 4) {\n+\t\t\t\t\tskip_reason = \"no size reduction\";\n+\t\t\t\t\tskip_lvl = 4;\n+\t\t\t\t}\n+\t\t\t\tcontinue;\n+\t\t\t}\n+\t\t\tcomp_buf = create_delta_object(delta_buf, delta_size,\n+\t\t\t\t\t\t       ref[r].sha1, &comp_size);\n+\t\t\tif (!comp_buf)\n+\t\t\t\tdie(\"out of memory\");\n+\t\t\tfree(delta_buf);\n+\t\t\tif (trg.depth < max_depth &&\n+\t\t\t    comp_size >= orig_compsize) {\n+\t\t\t\tfree(comp_buf);\n+\t\t\t\tif (skip_lvl < 5) {\n+\t\t\t\t\tskip_reason = \"no size reduction\";\n+\t\t\t\t\tskip_lvl = 5;\n+\t\t\t\t}\n+\t\t\t\tcontinue;\n+\t\t\t}\n+\t\t\tif ((comp_size < best_size) ||\n+\t\t\t    (comp_size == best_size &&\n+\t\t\t     ref[r].depth < ref[best_ref].depth)) {\n+\t\t\t\tfree(best_buf);\n+\t\t\t\tbest_buf = comp_buf;\n+\t\t\t\tbest_size = comp_size;\n+\t\t\t\tbest_ref = r;\n+\t\t\t}\n \t\t}\n \n-\t\tbuf_delta = diff_delta(buf_ref, size_ref, buf_trg, size_trg, &size_delta);\n-\t\tif (!buf_delta)\n-\t\t\tdie(\"out of memory\");\n-\n-\t\t/* no need to even try to compress if original\n-\t\t   uncompressed is already smaller */\n-\t\tif (size_delta+20 < size_orig) {\n-\t\t\tvoid *buf_obj;\n-\t\t\tunsigned long size_obj;\n-\t\t\tbuf_obj = create_delta_object(buf_delta, size_delta,\n-\t\t\t\t\t\t      sha1_ref, &size_obj);\n-\t\t\tfree(buf_delta);\n-\t\t\tsize_orig = get_object_size(sha1_trg);\n-\t\t\tif (size_obj >= size_orig) {\n-\t\t\t\tfree(buf_obj);\n-\t\t\t\tif (verbose)\n-\t\t\t\t\tprintf(\"skip    %s (original is smaller)\\n\", argv[i]);\n-\t\t\t\tgoto skip;\n-\t\t\t}\n-\t\t\tif (replace_object(buf_obj, size_obj, sha1_trg))\n+\t\tif (best_buf) {\n+\t\t\tif (replace_object(best_buf, best_size, trg.sha1))\n \t\t\t\tdie(\"unable to write delta for %s\", argv[i]);\n-\t\t\tfree(buf_obj);\n-\t\t\tdepth_ref++;\n-\t\t\tif (verbose)\n-\t\t\t\tprintf(\"delta   %s (size=%ld.%02ld%%, depth=%d)\\n\",\n-\t\t\t\t       argv[i], size_obj*100 / size_orig,\n-\t\t\t\t       (size_obj*10000 / size_orig)%100,\n-\t\t\t\t       depth_ref);\n-\t\t} else {\n-\t\t\tfree(buf_delta);\n-\t\t\tif (verbose)\n-\t\t\t\tprintf(\"skip    %s (original is smaller)\\n\", argv[i]);\n-\t\t\tskip:\n-\t\t\tdepth_ref = depth_trg;\n-\t\t\tmemcpy(head_ref, head_trg, 20);\n+\t\t\tfree(best_buf);\n+\t\t\tfree(trg.links);\n+\t\t\ttrg.depth = ref[best_ref].depth + 1;\n+\t\t\ttrg.links = xmalloc(trg.depth*20);\n+\t\t\tmemcpy(trg.links, ref[best_ref].sha1, 20);\n+\t\t\tmemcpy(trg.links+20, ref[best_ref].links, ref[best_ref].depth*20);\n+\t\t\tif (!quiet)\n+\t\t\t\tprintf(\"delta   %s (size=%ld.%02ld%% depth=%d dist=%d)\\n\",\n+\t\t\t\t       argv[i], best_size*100 / orig_compsize,\n+\t\t\t\t       (best_size*10000 / orig_compsize)%100,\n+\t\t\t\t       trg.depth,\n+\t\t\t\t       (next_ref - best_ref + max_refs)\n+\t\t\t\t       % (max_refs + 1) + 1);\n+\t\t} else if (trg.depth > max_depth) {\n+\t\t\tif (restore_original_object(trg.buf, trg.size, trg_type, trg.sha1))\n+\t\t\t\tdie(\"unable to restore %s\", argv[i]);\n+\t\t\tif (!quiet)\n+\t\t\t\tprintf(\"undelta %s (depth was %d)\\n\",\n+\t\t\t\t       argv[i], trg.depth);\n+\t\t\ttrg.depth = 0;\n+\t\t\tfree(trg.links);\n+\t\t\ttrg.links = NULL;\n+\t\t} else if (skip_reason && verbose) {\n+\t\t\tprintf(\"skip    %s (%s)\\n\", argv[i], skip_reason);\n \t\t}\n \n-\t\tfree(buf_ref);\n-\t\tbuf_ref = buf_trg;\n-\t\tsize_ref = size_trg;\n-\t\tmemcpy(sha1_ref, sha1_trg, 20);\n-\t}\n+\t\tif (!duplicate) {\n+\t\t\tfree(ref[next_ref].buf);\n+\t\t\tfree(ref[next_ref].links);\n+\t\t\tref[next_ref] = trg;\n+\t\t\tif (++next_ref > nb_refs)\n+\t\t\t\tnb_refs = next_ref;\n+\t\t\tif (next_ref == max_refs)\n+\t\t\t\tnext_ref = 0;\n+\t\t} else {\n+\t\t\tfree(trg.buf);\n+\t\t\tfree(trg.links);\n+\t\t}\n+\t} while (++i < argc);\n \n \treturn 0;\n }\n"}]}