{"thread":{"id":"678","subject":"[PATCH 3/3] delta creation","startedAt":"2005-05-20T21:00:23Z","lastAt":"2005-05-21T05:02:28Z","messageCount":2,"participants":["Nicolas Pitre","Junio C Hamano"],"isPatch":true,"patchVersion":1,"patchTotal":3},"messages":[{"id":"3646","messageId":"Pine.LNX.4.62.0505201659190.4397@localhost.localdomain","threadId":"678","inReplyTo":null,"subject":"[PATCH 3/3] delta creation","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2005-05-20T21:00:23Z","receivedAt":"2005-05-20T21:00:23Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"This patch adds the ability to actually create delta objects using a\nnew tool: git-mkdelta.  It uses an ordered list of potential objects\nto deltafy against earlier objects in the list.  A cap on the depth of\ndelta references can be provided as well, otherwise the default is to\nnot have any limit.  A limit of 0 will also undeltafy any given object.\n\nAlso provided is the beginning of a script to deltafy an entire\nrepository.\n\nSigned-off-by: Nicolas Pitre <nico@cam.org>\n\nIndex: git/Makefile\n===================================================================\n--- git.orig/Makefile\n+++ git/Makefile\n@@ -19,7 +19,8 @@\n INSTALL=install\n \n SCRIPTS=git-apply-patch-script git-merge-one-file-script git-prune-script \\\n-\tgit-pull-script git-tag-script git-resolve-script git-whatchanged\n+\tgit-pull-script git-tag-script git-resolve-script git-whatchanged \\\n+\tgit-deltafy-script\n \n PROG=   git-update-cache git-diff-files git-init-db git-write-tree \\\n \tgit-read-tree git-commit-tree git-cat-file git-fsck-cache \\\n@@ -28,7 +29,7 @@\n \tgit-unpack-file git-export git-diff-cache git-convert-cache \\\n \tgit-http-pull git-rpush git-rpull git-rev-list git-mktag \\\n \tgit-diff-helper git-tar-tree git-local-pull git-write-blob \\\n-\tgit-get-tar-commit-id\n+\tgit-get-tar-commit-id git-mkdelta\n \n all: $(PROG)\n \n@@ -107,6 +108,7 @@\n git-diff-helper: diff-helper.c\n git-tar-tree: tar-tree.c\n git-write-blob: write-blob.c\n+git-mkdelta: mkdelta.c\n \n git-http-pull: LIBS += -lcurl\n \nIndex: git/mkdelta.c\n===================================================================\n--- /dev/null\n+++ git/mkdelta.c\n@@ -0,0 +1,317 @@\n+/*\n+ * Deltafication of a GIT database.\n+ *\n+ * (C) 2005 Nicolas Pitre <nico@cam.org>\n+ *\n+ * This code is free software; you can redistribute it and/or modify\n+ * it under the terms of the GNU General Public License version 2 as\n+ * published by the Free Software Foundation.\n+ */\n+\n+#include \"cache.h\"\n+#include \"delta.h\"\n+\n+static int replace_object(char *buf, unsigned long size, unsigned char *sha1)\n+{\n+\tchar tmpfile[PATH_MAX];\n+\tint fd;\n+\n+\tsnprintf(tmpfile, sizeof(tmpfile), \"%s/obj_XXXXXX\", get_object_directory());\n+\tfd = mkstemp(tmpfile);\n+\tif (fd < 0)\n+\t\treturn error(\"%s: %s\\n\", tmpfile, strerror(errno));\n+\tif (write(fd, buf, size) != size) {\n+\t\tperror(\"unable to write file\");\n+\t\tclose(fd);\n+\t\tunlink(tmpfile);\n+\t\treturn -1;\n+\t}\n+\tfchmod(fd, 0444);\n+\tclose(fd);\n+\tif (rename(tmpfile, sha1_file_name(sha1))) {\n+\t\tperror(\"unable to replace original object\");\n+\t\tunlink(tmpfile);\n+\t\treturn -1;\n+\t}\n+\treturn 0;\n+}\n+\n+static void *create_object(char *buf, unsigned long len, char *hdr, int hdrlen,\n+\t\t\t   unsigned long *retsize)\n+{\n+\tchar *compressed;\n+\tunsigned long size;\n+\tz_stream stream;\n+\n+\t/* Set it up */\n+\tmemset(&stream, 0, sizeof(stream));\n+\tdeflateInit(&stream, Z_BEST_COMPRESSION);\n+\tsize = deflateBound(&stream, len+hdrlen);\n+\tcompressed = xmalloc(size);\n+\n+\t/* Compress it */\n+\tstream.next_out = compressed;\n+\tstream.avail_out = size;\n+\n+\t/* First header.. */\n+\tstream.next_in = hdr;\n+\tstream.avail_in = hdrlen;\n+\twhile (deflate(&stream, 0) == Z_OK)\n+\t\t/* nothing */;\n+\n+\t/* Then the data itself.. */\n+\tstream.next_in = buf;\n+\tstream.avail_in = len;\n+\twhile (deflate(&stream, Z_FINISH) == Z_OK)\n+\t\t/* nothing */;\n+\tdeflateEnd(&stream);\n+\t*retsize = stream.total_out;\n+\treturn compressed;\n+}\n+\n+static int restore_original_object(char *buf, unsigned long len,\n+\t\t\t\t   char *type, unsigned char *sha1)\n+{\n+\tchar hdr[50];\n+\tint hdrlen, ret;\n+\tvoid *compressed;\n+\tunsigned long size;\n+\n+\thdrlen = sprintf(hdr, \"%s %lu\", type, len)+1;\n+\tcompressed = create_object(buf, len, hdr, hdrlen, &size);\n+\tret = replace_object(compressed, size, sha1);\n+\tfree(compressed);\n+\treturn ret;\n+}\n+\n+static void *create_delta_object(char *buf, unsigned long len,\n+\t\t\t\t unsigned char *sha1_ref, unsigned long *size)\n+{\n+\tchar hdr[50];\n+\tint hdrlen;\n+\n+\t/* Generate the header + sha1 of reference for delta */\n+\thdrlen = sprintf(hdr, \"delta %lu\", len+20)+1;\n+\tmemcpy(hdr + hdrlen, sha1_ref, 20);\n+\thdrlen += 20;\n+\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+{\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 (buffer)\n+\t\t\treturn buffer;\n+\t}\n+\terror(\"unable to get object %s\", sha1_to_hex(sha1));\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+{\n+\tvoid *buf = NULL;\n+\t*depth++;\n+\tif (delta_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\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\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+\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+\n+\tfor (i = 1; i < argc; i++) {\n+\t\tif (!strcmp(argv[i], \"-v\")) {\n+\t\t\tverbose = 1;\n+\t\t} else if (!strcmp(argv[i], \"-d\") && i+1 < argc) {\n+\t\t\tdepth_max = 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} else\n+\t\t\tbreak;\n+\t}\n+\n+\tif (i + (depth_max != 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+\n+\twhile (++i < argc) {\n+\t\tif (get_sha1(argv[i], sha1_trg))\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\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\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+\n+\t\tif (depth_max == 0)\n+\t\t\tgoto skip;\n+\n+\t\tif (strcmp(type_ref, type_trg))\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\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\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}\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+\n+\treturn 0;\n+}\nIndex: git/git-deltafy-script\n===================================================================\n--- /dev/null\n+++ git/git-deltafy-script\n@@ -0,0 +1,39 @@\n+#!/bin/bash\n+\n+# 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+#\n+# The -d argument allows to provide a limit on the delta chain depth.\n+# If 0 is passed then everything is undeltafied.\n+\n+set -e\n+\n+depth=\n+[ \"$1\" == \"-d\" ] && depth=\"--max-depth=$2\" && shift 2\n+\n+curr_file=\"\"\n+\n+git-rev-list HEAD |\n+git-diff-tree -r --stdin |\n+sed -n '/^\\*/ s/^.*->\\(.\\{41\\}\\)\\(.*\\)$/\\2 \\1/p' | sort | uniq |\n+while read file sha1; 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\tcurr_file=\"$file\"\n+\t\tlist=\"\"\n+\t\thead=\"$sha1\"\n+\tfi\n+done\n"},{"id":"3678","messageId":"7vwtptnpcr.fsf@assigned-by-dhcp.cox.net","threadId":"678","inReplyTo":"Pine.LNX.4.62.0505201659190.4397@localhost.localdomain","subject":"Re: [PATCH 3/3] delta creation","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-05-21T05:02:28Z","receivedAt":"2005-05-21T05:02:28Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Just a stupid wording question, but is \"deltafy\" the word we\nwant to use?  The other command name \"mkdelta\" feels more easier\nto swallow at least for me ...\n\n\n"}]}