{"thread":{"id":"4062","subject":"[PATCH] binary patch.","startedAt":"2006-05-04T23:52:48Z","lastAt":"2006-05-06T07:40:22Z","messageCount":12,"participants":["Junio C Hamano","Nicolas Pitre","Daniel Barkalow"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"19532","messageId":"7vodyd2vqn.fsf@assigned-by-dhcp.cox.net","threadId":"4062","inReplyTo":null,"subject":"[PATCH] binary patch.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-05-04T23:52:48Z","receivedAt":"2006-05-04T23:52:48Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"This adds \"binary patch\" to the diff output and teaches apply\nwhat to do with them.\n\nOn the diff generation side, traditionally, we said \"Binary\nfiles differ\\n\" without giving anything other than the preimage\nand postimage object name on the index line.  This was good\nenough for applying a patch generated from your own repository\n(very useful while rebasing), because the postimage would be\navailable in such a case.  However, this was not useful when the\nrecipient of such a patch via e-mail were to apply it, even if\nthe preimage was available.\n\nThis patch allows the diff to generate \"binary\" patch when\noperating under --full-index option.  The binary patch follows\nthe usual extended git diff headers, and looks like this:\n\n\t\"GIT binary patch\\n\"\n\t<length byte><data>\"\\n\"\n\t...\n\t\"\\n\"\n\nEach line is prefixed with a \"length-byte\", whose value is upper\nor lowercase alphabet that encodes number of bytes that the data\non the line decodes to (1..52 -- 'A' means 1, 'B' means 2, ...,\n'Z' means 26, 'a' means 27, ...).  <data> is 1 or more groups of\n5-byte sequence, each of which encodes up to 4 bytes in base85\nencoding.  Because 52 / 4 * 5 = 65 and we have the length byte,\nan output line is capped to 66 characters.  The payload is the\nsame diff-delta as we use in the packfiles.\n\nOn the consumption side, git-apply now can decode and apply the\nbinary patch when --allow-binary-replacement is given, the diff\nwas generated with --full-index, and the receiving repository\nhas the preimage blob, which is the same condition as it always\nrequired when accepting an \"Binary files differ\\n\" patch.\n\nSigned-off-by: Junio C Hamano <junkio@cox.net>\n\n---\n\n Makefile |    2 -\n apply.c  |  232 ++++++++++++++++++++++++++++++++++++++++++++++----------------\n cache.h  |    3 +\n diff.c   |  106 ++++++++++++++++++++++++++--\n 4 files changed, 275 insertions(+), 68 deletions(-)\n\ndiff --git a/Makefile b/Makefile\nindex a3f7e92..b6be520 100644\n--- a/Makefile\n+++ b/Makefile\n@@ -205,7 +205,7 @@ DIFF_OBJS = \\\n \tdiffcore-delta.o log-tree.o\n \n LIB_OBJS = \\\n-\tblob.o commit.o connect.o csum-file.o \\\n+\tblob.o commit.o connect.o csum-file.o base85.o \\\n \tdate.o diff-delta.o entry.o exec_cmd.o ident.o index.o \\\n \tobject.o pack-check.o patch-delta.o path.o pkt-line.o \\\n \tquote.o read-cache.o refs.o run-command.o \\\ndiff --git a/apply.c b/apply.c\nindex 269210a..e37c4eb 100644\n--- a/apply.c\n+++ b/apply.c\n@@ -10,6 +10,7 @@ #include <fnmatch.h>\n #include \"cache.h\"\n #include \"quote.h\"\n #include \"blob.h\"\n+#include \"delta.h\"\n \n //  --check turns on checking that the working tree matches the\n //    files that are being modified, but doesn't apply the patch\n@@ -966,6 +967,70 @@ static inline int metadata_changes(struc\n \t\t patch->old_mode != patch->new_mode);\n }\n \n+static int parse_binary(char *buffer, unsigned long size, struct patch *patch)\n+{\n+\t/* We have read \"GIT binary patch\\n\"; what follows is a\n+\t * sequence of 'length-byte' followed by base-85 encoded\n+\t * delta data.\n+\t *\n+\t * Each 5-byte sequence of base-85 encodes up to 4 bytes,\n+\t * and we would limit the patch line to 66 characters,\n+\t * so one line can fit up to 13 groups that would decode\n+\t * to 52 bytes max.  The length byte 'A'-'Z' corresponds\n+\t * to 1-26 bytes, and 'a'-'z' corresponds to 27-52 bytes.\n+\t * The end of binary is signalled with an empty line.\n+\t */\n+\tint llen, used;\n+\tstruct fragment *fragment;\n+\tchar *delta = NULL;\n+\n+\tpatch->is_binary = 1;\n+\tpatch->fragments = fragment = xcalloc(1, sizeof(*fragment));\n+\tused = 0;\n+\twhile (1) {\n+\t\tint byte_length, max_byte_length, newsize;\n+\t\tllen = linelen(buffer, size);\n+\t\tused += llen;\n+\t\tlinenr++;\n+\t\tif (llen == 1)\n+\t\t\tbreak;\n+\t\t/* Minimum line is \"A00000\\n\" which is 7-byte long,\n+\t\t * and the line length must be multiple of 5 plus 2.\n+\t\t */\n+\t\tif ((llen < 7) || (llen-2) % 5)\n+\t\t\tgoto corrupt;\n+\t\tmax_byte_length = (llen - 2) / 5 * 4;\n+\t\tbyte_length = *buffer;\n+\t\tif ('A' <= byte_length && byte_length <= 'Z')\n+\t\t\tbyte_length = byte_length - 'A' + 1;\n+\t\telse if ('a' <= byte_length && byte_length <= 'z')\n+\t\t\tbyte_length = byte_length - 'a' + 27;\n+\t\telse\n+\t\t\tgoto corrupt;\n+\t\t/* if the input length was not multiple of 4, we would\n+\t\t * have filler at the end but the filler should never\n+\t\t * exceed 3 bytes\n+\t\t */\n+\t\tif (max_byte_length < byte_length ||\n+\t\t    byte_length <= max_byte_length - 4)\n+\t\t\tgoto corrupt;\n+\t\tnewsize = fragment->size + byte_length;\n+\t\tdelta = xrealloc(delta, newsize);\n+\t\tif (decode_85(delta + fragment->size,\n+\t\t\t      buffer + 1,\n+\t\t\t      byte_length))\n+\t\t\tgoto corrupt;\n+\t\tfragment->size = newsize;\n+\t\tbuffer += llen;\n+\t\tsize -= llen;\n+\t}\n+\tfragment->patch = delta;\n+\treturn used;\n+ corrupt:\n+\treturn error(\"corrupt binary patch at line %d: %.*s\",\n+\t\t     linenr-1, llen-1, buffer);\n+}\n+\n static int parse_chunk(char *buffer, unsigned long size, struct patch *patch)\n {\n \tint hdrsize, patchsize;\n@@ -982,19 +1047,34 @@ static int parse_chunk(char *buffer, uns\n \t\t\t\"Files \",\n \t\t\tNULL,\n \t\t};\n+\t\tstatic const char git_binary[] = \"GIT binary patch\\n\";\n \t\tint i;\n \t\tint hd = hdrsize + offset;\n \t\tunsigned long llen = linelen(buffer + hd, size - hd);\n \n-\t\tif (!memcmp(\" differ\\n\", buffer + hd + llen - 8, 8))\n+\t\tif (llen == sizeof(git_binary) - 1 &&\n+\t\t    !memcmp(git_binary, buffer + hd, llen)) {\n+\t\t\tint used;\n+\t\t\tlinenr++;\n+\t\t\tused = parse_binary(buffer + hd + llen,\n+\t\t\t\t\t    size - hd - llen, patch);\n+\t\t\tif (used)\n+\t\t\t\tpatchsize = used + llen;\n+\t\t\telse\n+\t\t\t\tpatchsize = 0;\n+\t\t}\n+\t\telse if (!memcmp(\" differ\\n\", buffer + hd + llen - 8, 8)) {\n \t\t\tfor (i = 0; binhdr[i]; i++) {\n \t\t\t\tint len = strlen(binhdr[i]);\n \t\t\t\tif (len < size - hd &&\n \t\t\t\t    !memcmp(binhdr[i], buffer + hd, len)) {\n+\t\t\t\t\tlinenr++;\n \t\t\t\t\tpatch->is_binary = 1;\n+\t\t\t\t\tpatchsize = llen;\n \t\t\t\t\tbreak;\n \t\t\t\t}\n \t\t\t}\n+\t\t}\n \n \t\t/* Empty patch cannot be applied if:\n \t\t * - it is a binary patch and we do not do binary_replace, or\n@@ -1345,76 +1425,108 @@ #endif\n \treturn offset;\n }\n \n-static int apply_fragments(struct buffer_desc *desc, struct patch *patch)\n+static int apply_binary(struct buffer_desc *desc, struct patch *patch)\n {\n-\tstruct fragment *frag = patch->fragments;\n \tconst char *name = patch->old_name ? patch->old_name : patch->new_name;\n+\tunsigned char sha1[20];\n+\tunsigned char hdr[50];\n+\tint hdrlen;\n \n-\tif (patch->is_binary) {\n-\t\tunsigned char sha1[20];\n+\tif (!allow_binary_replacement)\n+\t\treturn error(\"cannot apply binary patch to '%s' \"\n+\t\t\t     \"without --allow-binary-replacement\",\n+\t\t\t     name);\n \n-\t\tif (!allow_binary_replacement)\n-\t\t\treturn error(\"cannot apply binary patch to '%s' \"\n-\t\t\t\t     \"without --allow-binary-replacement\",\n-\t\t\t\t     name);\n+\t/* For safety, we require patch index line to contain\n+\t * full 40-byte textual SHA1 for old and new, at least for now.\n+\t */\n+\tif (strlen(patch->old_sha1_prefix) != 40 ||\n+\t    strlen(patch->new_sha1_prefix) != 40 ||\n+\t    get_sha1_hex(patch->old_sha1_prefix, sha1) ||\n+\t    get_sha1_hex(patch->new_sha1_prefix, sha1))\n+\t\treturn error(\"cannot apply binary patch to '%s' \"\n+\t\t\t     \"without full index line\", name);\n \n-\t\t/* For safety, we require patch index line to contain\n-\t\t * full 40-byte textual SHA1 for old and new, at least for now.\n+\tif (patch->old_name) {\n+\t\t/* See if the old one matches what the patch\n+\t\t * applies to.\n \t\t */\n-\t\tif (strlen(patch->old_sha1_prefix) != 40 ||\n-\t\t    strlen(patch->new_sha1_prefix) != 40 ||\n-\t\t    get_sha1_hex(patch->old_sha1_prefix, sha1) ||\n-\t\t    get_sha1_hex(patch->new_sha1_prefix, sha1))\n-\t\t\treturn error(\"cannot apply binary patch to '%s' \"\n-\t\t\t\t     \"without full index line\", name);\n-\n-\t\tif (patch->old_name) {\n-\t\t\tunsigned char hdr[50];\n-\t\t\tint hdrlen;\n-\n-\t\t\t/* See if the old one matches what the patch\n-\t\t\t * applies to.\n-\t\t\t */\n-\t\t\twrite_sha1_file_prepare(desc->buffer, desc->size,\n-\t\t\t\t\t\tblob_type, sha1, hdr, &hdrlen);\n-\t\t\tif (strcmp(sha1_to_hex(sha1), patch->old_sha1_prefix))\n-\t\t\t\treturn error(\"the patch applies to '%s' (%s), \"\n-\t\t\t\t\t     \"which does not match the \"\n-\t\t\t\t\t     \"current contents.\",\n-\t\t\t\t\t     name, sha1_to_hex(sha1));\n-\t\t}\n-\t\telse {\n-\t\t\t/* Otherwise, the old one must be empty. */\n-\t\t\tif (desc->size)\n-\t\t\t\treturn error(\"the patch applies to an empty \"\n-\t\t\t\t\t     \"'%s' but it is not empty\", name);\n-\t\t}\n+\t\twrite_sha1_file_prepare(desc->buffer, desc->size,\n+\t\t\t\t\tblob_type, sha1, hdr, &hdrlen);\n+\t\tif (strcmp(sha1_to_hex(sha1), patch->old_sha1_prefix))\n+\t\t\treturn error(\"the patch applies to '%s' (%s), \"\n+\t\t\t\t     \"which does not match the \"\n+\t\t\t\t     \"current contents.\",\n+\t\t\t\t     name, sha1_to_hex(sha1));\n+\t}\n+\telse {\n+\t\t/* Otherwise, the old one must be empty. */\n+\t\tif (desc->size)\n+\t\t\treturn error(\"the patch applies to an empty \"\n+\t\t\t\t     \"'%s' but it is not empty\", name);\n+\t}\n+\n+\tif (desc->buffer) {\n+\t\tfree(desc->buffer);\n+\t\tdesc->alloc = desc->size = 0;\n+\t}\n+\tget_sha1_hex(patch->new_sha1_prefix, sha1);\n+\tif (!memcmp(sha1, null_sha1, 20))\n+\t\treturn 0; /* deletion patch */\n+\n+\tif (has_sha1_file(sha1)) {\n+\t\tchar type[10];\n+\t\tunsigned long size;\n \n-\t\t/* For now, we do not record post-image data in the patch,\n-\t\t * and require the object already present in the recipient's\n-\t\t * object database.\n+\t\tdesc->buffer = read_sha1_file(sha1, type, &size);\n+\t\tif (!desc->buffer)\n+\t\t\treturn error(\"the necessary postimage %s for \"\n+\t\t\t\t     \"'%s' cannot be read\",\n+\t\t\t\t     patch->new_sha1_prefix, name);\n+\t\tdesc->alloc = desc->size = size;\n+\t}\n+\telse {\n+\t\tchar type[10];\n+\t\tunsigned long src_size, dst_size;\n+\t\tvoid *src;\n+\n+\t\tget_sha1_hex(patch->old_sha1_prefix, sha1);\n+\t\tsrc = read_sha1_file(sha1, type, &src_size);\n+\t\tif (!src)\n+\t\t\treturn error(\"the necessary preimage %s for \"\n+\t\t\t\t     \"'%s' cannot be read\",\n+\t\t\t\t     patch->old_sha1_prefix, name);\n+\n+\t\t/* patch->fragment->patch has the delta data and\n+\t\t * we should apply it to the preimage.\n \t\t */\n-\t\tif (desc->buffer) {\n-\t\t\tfree(desc->buffer);\n-\t\t\tdesc->alloc = desc->size = 0;\n-\t\t}\n-\t\tget_sha1_hex(patch->new_sha1_prefix, sha1);\n-\n-\t\tif (memcmp(sha1, null_sha1, 20)) {\n-\t\t\tchar type[10];\n-\t\t\tunsigned long size;\n-\n-\t\t\tdesc->buffer = read_sha1_file(sha1, type, &size);\n-\t\t\tif (!desc->buffer)\n-\t\t\t\treturn error(\"the necessary postimage %s for \"\n-\t\t\t\t\t     \"'%s' does not exist\",\n-\t\t\t\t\t     patch->new_sha1_prefix, name);\n-\t\t\tdesc->alloc = desc->size = size;\n-\t\t}\n+\t\tdesc->buffer = patch_delta(src, src_size,\n+\t\t\t\t\t   (void*) patch->fragments->patch,\n+\t\t\t\t\t   patch->fragments->size,\n+\t\t\t\t\t   &dst_size);\n+\t\tif (!desc->buffer)\n+\t\t\treturn error(\"binary patch does not apply to '%s'\",\n+\t\t\t\t     name);\n+\t\tdesc->size = desc->alloc = dst_size;\n \n-\t\treturn 0;\n+\t\t/* verify that the result matches */\n+\t\twrite_sha1_file_prepare(desc->buffer, desc->size, blob_type,\n+\t\t\t\t\tsha1, hdr, &hdrlen);\n+\t\tif (strcmp(sha1_to_hex(sha1), patch->new_sha1_prefix))\n+\t\t\treturn error(\"binary patch to '%s' creates incorrect result\", name);\n \t}\n \n+\treturn 0;\n+}\n+\n+static int apply_fragments(struct buffer_desc *desc, struct patch *patch)\n+{\n+\tstruct fragment *frag = patch->fragments;\n+\tconst char *name = patch->old_name ? patch->old_name : patch->new_name;\n+\n+\tif (patch->is_binary)\n+\t\treturn apply_binary(desc, patch);\n+\n \twhile (frag) {\n \t\tif (apply_one_fragment(desc, frag) < 0)\n \t\t\treturn error(\"patch failed: %s:%ld\",\ndiff --git a/cache.h b/cache.h\nindex 9d0ddcf..2f32f3d 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -363,4 +363,7 @@ extern int receive_keep_pack(int fd[2], \n /* pager.c */\n extern void setup_pager(void);\n \n+/* base85 */\n+int decode_85(char *dst, char *line, int linelen);\n+\n #endif /* CACHE_H */\ndiff --git a/diff.c b/diff.c\nindex c845c87..b14d897 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -8,6 +8,7 @@ #include \"cache.h\"\n #include \"quote.h\"\n #include \"diff.h\"\n #include \"diffcore.h\"\n+#include \"delta.h\"\n #include \"xdiff-interface.h\"\n \n static int use_size_cache;\n@@ -391,6 +392,90 @@ static void show_stats(struct diffstat_t\n \t\t\ttotal_files, adds, dels);\n }\n \n+static void *encode_delta_size(void *data, unsigned long size)\n+{\n+\tunsigned char *cp = data;\n+\t*cp++ = size;\n+\tsize >>= 7;\n+\twhile (size) {\n+\t\tcp[-1] |= 0x80;\n+\t\t*cp++ = size;\n+\t\tsize >>= 7;\n+\t}\n+\treturn cp;\n+}\n+\n+static void *safe_diff_delta(const unsigned char *src, unsigned long src_size,\n+\t\t\t     const unsigned char *dst, unsigned long dst_size,\n+\t\t\t     unsigned long *delta_size)\n+{\n+\tunsigned long bufsize;\n+\tunsigned char *data;\n+\tunsigned char *cp;\n+\n+\tif (src_size && dst_size)\n+\t\treturn diff_delta(src, src_size, dst, dst_size, delta_size, 0);\n+\n+\t/* diff-delta does not like to do delta with empty, so\n+\t * we do that by hand here.  Sigh...\n+\t */\n+\n+\tif (!src_size)\n+\t\t/* literal copy can be done only 127-byte at a time.\n+\t\t */\n+\t\tbufsize = dst_size + (dst_size / 127) + 40;\n+\telse\n+\t\tbufsize = 40;\n+\tdata = xmalloc(bufsize);\n+\tcp = encode_delta_size(data, src_size);\n+\tcp = encode_delta_size(cp, dst_size);\n+\n+\tif (dst_size) {\n+\t\t/* copy out literally */\n+\t\twhile (dst_size) {\n+\t\t\tint sz = (127 < dst_size) ? 127 : dst_size;\n+\t\t\t*cp++ = sz;\n+\t\t\tdst_size -= sz;\n+\t\t\twhile (sz) {\n+\t\t\t\t*cp++ = *dst++;\n+\t\t\t\tsz--;\n+\t\t\t}\n+\t\t}\n+\t}\n+\t*delta_size = (cp - data);\n+\treturn data;\n+}\n+\n+static void emit_binary_diff(mmfile_t *one, mmfile_t *two)\n+{\n+\tvoid *delta, *cp;\n+\tunsigned long delta_size;\n+\n+\tprintf(\"GIT binary patch\\n\");\n+\tdelta = safe_diff_delta(one->ptr, one->size,\n+\t\t\t\ttwo->ptr, two->size,\n+\t\t\t\t&delta_size);\n+\tif (!delta)\n+\t\tdie(\"unable to generate binary diff\");\n+\n+\t/* emit delta encoded in base85 */\n+\tcp = delta;\n+\twhile (delta_size) {\n+\t\tint bytes = (52 < delta_size) ? 52 : delta_size;\n+\t\tchar line[70];\n+\t\tdelta_size -= bytes;\n+\t\tif (bytes <= 26)\n+\t\t\tline[0] = bytes + 'A' - 1;\n+\t\telse\n+\t\t\tline[0] = bytes - 26 + 'a' - 1;\n+\t\tencode_85(line + 1, cp, bytes);\n+\t\tcp += bytes;\n+\t\tputs(line);\n+\t}\n+\tprintf(\"\\n\");\n+\tfree(delta);\n+}\n+\n #define FIRST_FEW_BYTES 8000\n static int mmfile_is_binary(mmfile_t *mf)\n {\n@@ -407,6 +492,7 @@ static void builtin_diff(const char *nam\n \t\t\t struct diff_filespec *one,\n \t\t\t struct diff_filespec *two,\n \t\t\t const char *xfrm_msg,\n+\t\t\t struct diff_options *o,\n \t\t\t int complete_rewrite)\n {\n \tmmfile_t mf1, mf2;\n@@ -451,8 +537,13 @@ static void builtin_diff(const char *nam\n \tif (fill_mmfile(&mf1, one) < 0 || fill_mmfile(&mf2, two) < 0)\n \t\tdie(\"unable to read files to diff\");\n \n-\tif (mmfile_is_binary(&mf1) || mmfile_is_binary(&mf2))\n-\t\tprintf(\"Binary files %s and %s differ\\n\", lbl[0], lbl[1]);\n+\tif (mmfile_is_binary(&mf1) || mmfile_is_binary(&mf2)) {\n+\t\tif (o->full_index)\n+\t\t\temit_binary_diff(&mf1, &mf2);\n+\t\telse\n+\t\t\tprintf(\"Binary files %s and %s differ\\n\",\n+\t\t\t       lbl[0], lbl[1]);\n+\t}\n \telse {\n \t\t/* Crazy xdl interfaces.. */\n \t\tconst char *diffopts = getenv(\"GIT_DIFF_OPTS\");\n@@ -928,6 +1019,7 @@ static void run_diff_cmd(const char *pgm\n \t\t\t struct diff_filespec *one,\n \t\t\t struct diff_filespec *two,\n \t\t\t const char *xfrm_msg,\n+\t\t\t struct diff_options *o,\n \t\t\t int complete_rewrite)\n {\n \tif (pgm) {\n@@ -937,7 +1029,7 @@ static void run_diff_cmd(const char *pgm\n \t}\n \tif (one && two)\n \t\tbuiltin_diff(name, other ? other : name,\n-\t\t\t     one, two, xfrm_msg, complete_rewrite);\n+\t\t\t     one, two, xfrm_msg, o, complete_rewrite);\n \telse\n \t\tprintf(\"* Unmerged path %s\\n\", name);\n }\n@@ -971,7 +1063,7 @@ static void run_diff(struct diff_filepai\n \n \tif (DIFF_PAIR_UNMERGED(p)) {\n \t\t/* unmerged */\n-\t\trun_diff_cmd(pgm, p->one->path, NULL, NULL, NULL, NULL, 0);\n+\t\trun_diff_cmd(pgm, p->one->path, NULL, NULL, NULL, NULL, o, 0);\n \t\treturn;\n \t}\n \n@@ -1041,14 +1133,14 @@ static void run_diff(struct diff_filepai\n \t\t * needs to be split into deletion and creation.\n \t\t */\n \t\tstruct diff_filespec *null = alloc_filespec(two->path);\n-\t\trun_diff_cmd(NULL, name, other, one, null, xfrm_msg, 0);\n+\t\trun_diff_cmd(NULL, name, other, one, null, xfrm_msg, o, 0);\n \t\tfree(null);\n \t\tnull = alloc_filespec(one->path);\n-\t\trun_diff_cmd(NULL, name, other, null, two, xfrm_msg, 0);\n+\t\trun_diff_cmd(NULL, name, other, null, two, xfrm_msg, o, 0);\n \t\tfree(null);\n \t}\n \telse\n-\t\trun_diff_cmd(pgm, name, other, one, two, xfrm_msg,\n+\t\trun_diff_cmd(pgm, name, other, one, two, xfrm_msg, o,\n \t\t\t     complete_rewrite);\n \n \tfree(name_munged);\n-- \n1.3.1.g25a9\n"},{"id":"19543","messageId":"Pine.LNX.4.64.0605042241240.28543@localhost.localdomain","threadId":"4062","inReplyTo":"7vodyd2vqn.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] binary patch.","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-05-05T02:47:29Z","receivedAt":"2006-05-05T02:47:29Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Thu, 4 May 2006, Junio C Hamano wrote:\n\n> This adds \"binary patch\" to the diff output and teaches apply\n> what to do with them.\n\nThis is nice.\n\nHowever I'd deflate the delta data before encoding it with base85.\n\n\nNicolas\n"},{"id":"19549","messageId":"7vwtd10xyd.fsf@assigned-by-dhcp.cox.net","threadId":"4062","inReplyTo":"Pine.LNX.4.64.0605042241240.28543@localhost.localdomain","subject":"Re: [PATCH] binary patch.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-05-05T06:47:54Z","receivedAt":"2006-05-05T06:47:54Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nicolas Pitre <nico@cam.org> writes:\n\n> On Thu, 4 May 2006, Junio C Hamano wrote:\n>\n>> This adds \"binary patch\" to the diff output and teaches apply\n>> what to do with them.\n>\n> This is nice.\n>\n> However I'd deflate the delta data before encoding it with base85.\n\nYeah, things still to be done are deflating both delta and\noptionally perhaps use just deflate without delta for \"new file\"\ncodepath.\n\nAnd testsuite.\n"},{"id":"19554","messageId":"7vy7xgzsiu.fsf@assigned-by-dhcp.cox.net","threadId":"4062","inReplyTo":"7vwtd10xyd.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] binary patch.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-05-05T10:15:53Z","receivedAt":"2006-05-05T10:15:53Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <junkio@cox.net> writes:\n\n> Nicolas Pitre <nico@cam.org> writes:\n>\n>> This is nice.\n>>\n>> However I'd deflate the delta data before encoding it with base85.\n>\n> Yeah, things still to be done are deflating both delta and\n> optionally perhaps use just deflate without delta for \"new file\"\n> codepath.\n>\n> And testsuite.\n\n-- >8 --\n[PATCH] binary diff: further updates.\n\nThis updates the user interface and generated diff data format.\n\n * \"diff --binary\" is used to signal that we want an e-mailable\n   binary patch.  It implies --full-index and -p.\n\n * \"apply --allow-binary-replacement\" acquired a short synonym\n   \"apply --binary\".\n\n * After the \"GIT binary patch\\n\" header line there is a token\n   to record which binary patch mechanism was used, so that we\n   can extend it later.  Currently there are two mechanisms\n   defined: \"literal\" and \"delta\".  The former records the\n   deflated postimage and the latter records the deflated delta\n   from the preimage to postimage.\n\n   For purely implementation convenience, I added the deflated\n   length after these \"literal/delta\" tokens (otherwise the\n   decoding side needs to guess and reallocate the buffer while\n   inflating).  Improvement patches are very welcomed.\n\nSigned-off-by: Junio C Hamano <junkio@cox.net>\n\n---\n\n * Have done only very minimum testing, and unlike somebody else ;-)\n   my code is not always perfect, so this will still stay out of\n   \"next\" for a while.\n\n apply.c |  130 +++++++++++++++++++++++++++++++++++++++++++++----------------\n cache.h |    1 \n diff.c  |  135 +++++++++++++++++++++++++++++++++------------------------------\n diff.h  |    1 \n 4 files changed, 169 insertions(+), 98 deletions(-)\n\ndiff --git a/apply.c b/apply.c\nindex e37c4eb..1b93aab 100644\n--- a/apply.c\n+++ b/apply.c\n@@ -114,6 +114,9 @@ struct patch {\n \tchar *new_name, *old_name, *def_name;\n \tunsigned int old_mode, new_mode;\n \tint is_rename, is_copy, is_new, is_delete, is_binary;\n+#define BINARY_DELTA_DEFLATED 1\n+#define BINARY_LITERAL_DEFLATED 2\n+\tunsigned long deflate_origlen;\n \tint lines_added, lines_deleted;\n \tint score;\n \tstruct fragment *fragments;\n@@ -969,9 +972,11 @@ static inline int metadata_changes(struc\n \n static int parse_binary(char *buffer, unsigned long size, struct patch *patch)\n {\n-\t/* We have read \"GIT binary patch\\n\"; what follows is a\n-\t * sequence of 'length-byte' followed by base-85 encoded\n-\t * delta data.\n+\t/* We have read \"GIT binary patch\\n\"; what follows is a line\n+\t * that says the patch method (currently, either \"deflated\n+\t * literal\" or \"deflated delta\") and the length of data before\n+\t * deflating; a sequence of 'length-byte' followed by base-85\n+\t * encoded data follows.\n \t *\n \t * Each 5-byte sequence of base-85 encodes up to 4 bytes,\n \t * and we would limit the patch line to 66 characters,\n@@ -982,11 +987,27 @@ static int parse_binary(char *buffer, un\n \t */\n \tint llen, used;\n \tstruct fragment *fragment;\n-\tchar *delta = NULL;\n+\tchar *data = NULL;\n \n-\tpatch->is_binary = 1;\n \tpatch->fragments = fragment = xcalloc(1, sizeof(*fragment));\n-\tused = 0;\n+\n+\t/* Grab the type of patch */\n+\tllen = linelen(buffer, size);\n+\tused = llen;\n+\tlinenr++;\n+\n+\tif (!strncmp(buffer, \"delta \", 6)) {\n+\t\tpatch->is_binary = BINARY_DELTA_DEFLATED;\n+\t\tpatch->deflate_origlen = strtoul(buffer + 6, NULL, 10);\n+\t}\n+\telse if (!strncmp(buffer, \"literal \", 8)) {\n+\t\tpatch->is_binary = BINARY_LITERAL_DEFLATED;\n+\t\tpatch->deflate_origlen = strtoul(buffer + 8, NULL, 10);\n+\t}\n+\telse\n+\t\treturn error(\"unrecognized binary patch at line %d: %.*s\",\n+\t\t\t     linenr-1, llen-1, buffer);\n+\tbuffer += llen;\n \twhile (1) {\n \t\tint byte_length, max_byte_length, newsize;\n \t\tllen = linelen(buffer, size);\n@@ -1015,8 +1036,8 @@ static int parse_binary(char *buffer, un\n \t\t    byte_length <= max_byte_length - 4)\n \t\t\tgoto corrupt;\n \t\tnewsize = fragment->size + byte_length;\n-\t\tdelta = xrealloc(delta, newsize);\n-\t\tif (decode_85(delta + fragment->size,\n+\t\tdata = xrealloc(data, newsize);\n+\t\tif (decode_85(data + fragment->size,\n \t\t\t      buffer + 1,\n \t\t\t      byte_length))\n \t\t\tgoto corrupt;\n@@ -1024,7 +1045,7 @@ static int parse_binary(char *buffer, un\n \t\tbuffer += llen;\n \t\tsize -= llen;\n \t}\n-\tfragment->patch = delta;\n+\tfragment->patch = data;\n \treturn used;\n  corrupt:\n \treturn error(\"corrupt binary patch at line %d: %.*s\",\n@@ -1425,6 +1446,61 @@ #endif\n \treturn offset;\n }\n \n+static char *inflate_it(const void *data, unsigned long size,\n+\t\t\tunsigned long inflated_size)\n+{\n+\tz_stream stream;\n+\tvoid *out;\n+\tint st;\n+\n+\tmemset(&stream, 0, sizeof(stream));\n+\n+\tstream.next_in = (unsigned char *)data;\n+\tstream.avail_in = size;\n+\tstream.next_out = out = xmalloc(inflated_size);\n+\tstream.avail_out = inflated_size;\n+\tinflateInit(&stream);\n+\tst = inflate(&stream, Z_FINISH);\n+\tif ((st != Z_STREAM_END) || stream.total_out != inflated_size) {\n+\t\tfree(out);\n+\t\treturn NULL;\n+\t}\n+\treturn out;\n+}\n+\n+static int apply_binary_fragment(struct buffer_desc *desc, struct patch *patch)\n+{\n+\tunsigned long dst_size;\n+\tstruct fragment *fragment = patch->fragments;\n+\tvoid *data;\n+\tvoid *result;\n+\n+\tdata = inflate_it(fragment->patch, fragment->size,\n+\t\t\t  patch->deflate_origlen);\n+\tif (!data)\n+\t\treturn error(\"corrupt patch data\");\n+\tswitch (patch->is_binary) {\n+\tcase BINARY_DELTA_DEFLATED:\n+\t\tresult = patch_delta(desc->buffer, desc->size,\n+\t\t\t\t     data,\n+\t\t\t\t     patch->deflate_origlen,\n+\t\t\t\t     &dst_size);\n+\t\tfree(desc->buffer);\n+\t\tdesc->buffer = result;\n+\t\tfree(data);\n+\t\tbreak;\n+\tcase BINARY_LITERAL_DEFLATED:\n+\t\tfree(desc->buffer);\n+\t\tdesc->buffer = data;\n+\t\tdst_size = patch->deflate_origlen;\n+\t\tbreak;\n+\t}\n+\tif (!desc->buffer)\n+\t\treturn -1;\n+\tdesc->size = desc->alloc = dst_size;\n+\treturn 0;\n+}\n+\n static int apply_binary(struct buffer_desc *desc, struct patch *patch)\n {\n \tconst char *name = patch->old_name ? patch->old_name : patch->new_name;\n@@ -1466,18 +1542,20 @@ static int apply_binary(struct buffer_de\n \t\t\t\t     \"'%s' but it is not empty\", name);\n \t}\n \n-\tif (desc->buffer) {\n+\tget_sha1_hex(patch->new_sha1_prefix, sha1);\n+\tif (!memcmp(sha1, null_sha1, 20)) {\n \t\tfree(desc->buffer);\n \t\tdesc->alloc = desc->size = 0;\n-\t}\n-\tget_sha1_hex(patch->new_sha1_prefix, sha1);\n-\tif (!memcmp(sha1, null_sha1, 20))\n+\t\tdesc->buffer = NULL;\n \t\treturn 0; /* deletion patch */\n+\t}\n \n \tif (has_sha1_file(sha1)) {\n+\t\t/* We already have the postimage */\n \t\tchar type[10];\n \t\tunsigned long size;\n \n+\t\tfree(desc->buffer);\n \t\tdesc->buffer = read_sha1_file(sha1, type, &size);\n \t\tif (!desc->buffer)\n \t\t\treturn error(\"the necessary postimage %s for \"\n@@ -1486,28 +1564,13 @@ static int apply_binary(struct buffer_de\n \t\tdesc->alloc = desc->size = size;\n \t}\n \telse {\n-\t\tchar type[10];\n-\t\tunsigned long src_size, dst_size;\n-\t\tvoid *src;\n-\n-\t\tget_sha1_hex(patch->old_sha1_prefix, sha1);\n-\t\tsrc = read_sha1_file(sha1, type, &src_size);\n-\t\tif (!src)\n-\t\t\treturn error(\"the necessary preimage %s for \"\n-\t\t\t\t     \"'%s' cannot be read\",\n-\t\t\t\t     patch->old_sha1_prefix, name);\n-\n-\t\t/* patch->fragment->patch has the delta data and\n-\t\t * we should apply it to the preimage.\n+\t\t/* We have verified desc matches the preimage;\n+\t\t * apply the patch data to it, which is stored\n+\t\t * in the patch->fragments->{patch,size}.\n \t\t */\n-\t\tdesc->buffer = patch_delta(src, src_size,\n-\t\t\t\t\t   (void*) patch->fragments->patch,\n-\t\t\t\t\t   patch->fragments->size,\n-\t\t\t\t\t   &dst_size);\n-\t\tif (!desc->buffer)\n+\t\tif (apply_binary_fragment(desc, patch))\n \t\t\treturn error(\"binary patch does not apply to '%s'\",\n \t\t\t\t     name);\n-\t\tdesc->size = desc->alloc = dst_size;\n \n \t\t/* verify that the result matches */\n \t\twrite_sha1_file_prepare(desc->buffer, desc->size, blob_type,\n@@ -2102,7 +2165,8 @@ int main(int argc, char **argv)\n \t\t\tdiffstat = 1;\n \t\t\tcontinue;\n \t\t}\n-\t\tif (!strcmp(arg, \"--allow-binary-replacement\")) {\n+\t\tif (!strcmp(arg, \"--allow-binary-replacement\") ||\n+\t\t    !strcmp(arg, \"--binary\")) {\n \t\t\tallow_binary_replacement = 1;\n \t\t\tcontinue;\n \t\t}\ndiff --git a/cache.h b/cache.h\nindex 2f32f3d..4b7a439 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -365,5 +365,6 @@ extern void setup_pager(void);\n \n /* base85 */\n int decode_85(char *dst, char *line, int linelen);\n+void encode_85(char *buf, unsigned char *data, int bytes);\n \n #endif /* CACHE_H */\ndiff --git a/diff.c b/diff.c\nindex b14d897..94bd94a 100644\n--- a/diff.c\n+++ b/diff.c\n@@ -392,78 +392,75 @@ static void show_stats(struct diffstat_t\n \t\t\ttotal_files, adds, dels);\n }\n \n-static void *encode_delta_size(void *data, unsigned long size)\n+static unsigned char *deflate_it(char *data,\n+\t\t\t\t unsigned long size,\n+\t\t\t\t unsigned long *result_size)\n {\n-\tunsigned char *cp = data;\n-\t*cp++ = size;\n-\tsize >>= 7;\n-\twhile (size) {\n-\t\tcp[-1] |= 0x80;\n-\t\t*cp++ = size;\n-\t\tsize >>= 7;\n-\t}\n-\treturn cp;\n-}\n-\n-static void *safe_diff_delta(const unsigned char *src, unsigned long src_size,\n-\t\t\t     const unsigned char *dst, unsigned long dst_size,\n-\t\t\t     unsigned long *delta_size)\n-{\n-\tunsigned long bufsize;\n-\tunsigned char *data;\n-\tunsigned char *cp;\n-\n-\tif (src_size && dst_size)\n-\t\treturn diff_delta(src, src_size, dst, dst_size, delta_size, 0);\n-\n-\t/* diff-delta does not like to do delta with empty, so\n-\t * we do that by hand here.  Sigh...\n-\t */\n-\n-\tif (!src_size)\n-\t\t/* literal copy can be done only 127-byte at a time.\n-\t\t */\n-\t\tbufsize = dst_size + (dst_size / 127) + 40;\n-\telse\n-\t\tbufsize = 40;\n-\tdata = xmalloc(bufsize);\n-\tcp = encode_delta_size(data, src_size);\n-\tcp = encode_delta_size(cp, dst_size);\n-\n-\tif (dst_size) {\n-\t\t/* copy out literally */\n-\t\twhile (dst_size) {\n-\t\t\tint sz = (127 < dst_size) ? 127 : dst_size;\n-\t\t\t*cp++ = sz;\n-\t\t\tdst_size -= sz;\n-\t\t\twhile (sz) {\n-\t\t\t\t*cp++ = *dst++;\n-\t\t\t\tsz--;\n-\t\t\t}\n-\t\t}\n-\t}\n-\t*delta_size = (cp - data);\n-\treturn data;\n+\tint bound;\n+\tunsigned char *deflated;\n+\tz_stream stream;\n+\n+\tmemset(&stream, 0, sizeof(stream));\n+\tdeflateInit(&stream, Z_BEST_COMPRESSION);\n+\tbound = deflateBound(&stream, size);\n+\tdeflated = xmalloc(bound);\n+\tstream.next_out = deflated;\n+\tstream.avail_out = bound;\n+\n+\tstream.next_in = (unsigned char *)data;\n+\tstream.avail_in = size;\n+\twhile (deflate(&stream, Z_FINISH) == Z_OK)\n+\t\t; /* nothing */\n+\tdeflateEnd(&stream);\n+\t*result_size = stream.total_out;\n+\treturn deflated;\n }\n \n static void emit_binary_diff(mmfile_t *one, mmfile_t *two)\n {\n-\tvoid *delta, *cp;\n+\tvoid *cp;\n+\tvoid *delta;\n+\tvoid *deflated;\n+\tvoid *data;\n+\tunsigned long orig_size;\n \tunsigned long delta_size;\n+\tunsigned long deflate_size;\n+\tunsigned long data_size;\n \n \tprintf(\"GIT binary patch\\n\");\n-\tdelta = safe_diff_delta(one->ptr, one->size,\n-\t\t\t\ttwo->ptr, two->size,\n-\t\t\t\t&delta_size);\n-\tif (!delta)\n-\t\tdie(\"unable to generate binary diff\");\n-\n-\t/* emit delta encoded in base85 */\n-\tcp = delta;\n-\twhile (delta_size) {\n-\t\tint bytes = (52 < delta_size) ? 52 : delta_size;\n+\t/* We could do deflated delta, or we could do just deflated two,\n+\t * whichever is smaller.\n+\t */\n+\tdelta = NULL;\n+\tdeflated = deflate_it(two->ptr, two->size, &deflate_size);\n+\tif (one->size && two->size) {\n+\t\tdelta = diff_delta(one->ptr, one->size,\n+\t\t\t\t   two->ptr, two->size,\n+\t\t\t\t   &delta_size, deflate_size);\n+\t\torig_size = delta_size;\n+\t\tif (delta)\n+\t\t\tdelta = deflate_it(delta, delta_size, &delta_size);\n+\t}\n+\n+\tif (delta && delta_size < deflate_size) {\n+\t\tprintf(\"delta %lu\\n\", orig_size);\n+\t\tfree(deflated);\n+\t\tdata = delta;\n+\t\tdata_size = delta_size;\n+\t}\n+\telse {\n+\t\tprintf(\"literal %lu\\n\", two->size);\n+\t\tfree(delta);\n+\t\tdata = deflated;\n+\t\tdata_size = deflate_size;\n+\t}\n+\n+\t/* emit data encoded in base85 */\n+\tcp = data;\n+\twhile (data_size) {\n+\t\tint bytes = (52 < data_size) ? 52 : data_size;\n \t\tchar line[70];\n-\t\tdelta_size -= bytes;\n+\t\tdata_size -= bytes;\n \t\tif (bytes <= 26)\n \t\t\tline[0] = bytes + 'A' - 1;\n \t\telse\n@@ -473,7 +470,7 @@ static void emit_binary_diff(mmfile_t *o\n \t\tputs(line);\n \t}\n \tprintf(\"\\n\");\n-\tfree(delta);\n+\tfree(data);\n }\n \n #define FIRST_FEW_BYTES 8000\n@@ -538,7 +535,11 @@ static void builtin_diff(const char *nam\n \t\tdie(\"unable to read files to diff\");\n \n \tif (mmfile_is_binary(&mf1) || mmfile_is_binary(&mf2)) {\n-\t\tif (o->full_index)\n+\t\t/* Quite common confusing case */\n+\t\tif (mf1.size == mf2.size &&\n+\t\t    !memcmp(mf1.ptr, mf2.ptr, mf1.size))\n+\t\t\tgoto free_ab_and_return;\n+\t\tif (o->binary)\n \t\t\temit_binary_diff(&mf1, &mf2);\n \t\telse\n \t\t\tprintf(\"Binary files %s and %s differ\\n\",\n@@ -1239,6 +1240,10 @@ int diff_opt_parse(struct diff_options *\n \t\toptions->rename_limit = strtoul(arg+2, NULL, 10);\n \telse if (!strcmp(arg, \"--full-index\"))\n \t\toptions->full_index = 1;\n+\telse if (!strcmp(arg, \"--binary\")) {\n+\t\toptions->output_format = DIFF_FORMAT_PATCH;\n+\t\toptions->full_index = options->binary = 1;\n+\t}\n \telse if (!strcmp(arg, \"--name-only\"))\n \t\toptions->output_format = DIFF_FORMAT_NAME;\n \telse if (!strcmp(arg, \"--name-status\"))\ndiff --git a/diff.h b/diff.h\nindex b3b2c4d..d052608 100644\n--- a/diff.h\n+++ b/diff.h\n@@ -28,6 +28,7 @@ struct diff_options {\n \t\t with_raw:1,\n \t\t with_stat:1,\n \t\t tree_in_recursive:1,\n+\t\t binary:1,\n \t\t full_index:1,\n \t\t silent_on_remove:1,\n \t\t find_copies_harder:1;\n-- \n1.3.1.g25a9\n"},{"id":"19561","messageId":"Pine.LNX.4.64.0605051128100.28543@localhost.localdomain","threadId":"4062","inReplyTo":"7vy7xgzsiu.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] binary patch.","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-05-05T15:41:32Z","receivedAt":"2006-05-05T15:41:32Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Fri, 5 May 2006, Junio C Hamano wrote:\n\n> > Yeah, things still to be done are deflating both delta and\n> > optionally perhaps use just deflate without delta for \"new file\"\n> > codepath.\n\n> +\t/* We could do deflated delta, or we could do just deflated two,\n> +\t * whichever is smaller.\n> +\t */\n> +\tdelta = NULL;\n> +\tdeflated = deflate_it(two->ptr, two->size, &deflate_size);\n> +\tif (one->size && two->size) {\n> +\t\tdelta = diff_delta(one->ptr, one->size,\n> +\t\t\t\t   two->ptr, two->size,\n> +\t\t\t\t   &delta_size, deflate_size);\n\nHere you probably want to use deflate_size-1 (deflate_size can't be 0).\n\n> +\t\torig_size = delta_size;\n> +\t\tif (delta)\n> +\t\t\tdelta = deflate_it(delta, delta_size, &delta_size);\n\nHere you're leaking the original delta buffer memory.\n\n\nNicolas\n"},{"id":"19566","messageId":"7vejz8z80p.fsf@assigned-by-dhcp.cox.net","threadId":"4062","inReplyTo":"Pine.LNX.4.64.0605051128100.28543@localhost.localdomain","subject":"Re: [PATCH] binary patch.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-05-05T17:38:46Z","receivedAt":"2006-05-05T17:38:46Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nicolas Pitre <nico@cam.org> writes:\n\n>> +\tdelta = NULL;\n>> +\tdeflated = deflate_it(two->ptr, two->size, &deflate_size);\n>> +\tif (one->size && two->size) {\n>> +\t\tdelta = diff_delta(one->ptr, one->size,\n>> +\t\t\t\t   two->ptr, two->size,\n>> +\t\t\t\t   &delta_size, deflate_size);\n>\n> Here you probably want to use deflate_size-1 (deflate_size can't be 0).\n\nI am not sure if -1 is worth here.\n\nThe delta is going to be deflated and hopefully gets a bit\nsmaller, so if we really care that level of detail, it might be\nworth to do (deflate_size*3/2) or something like that here, use\ndelta with or without deflate whichever is smaller, and mark the\nuncompressed delta with a different tag (\"uncompressed delta\"?).\nAnd for symmetry, to deal with uncompressible data, we may want\nto have \"uncompressed literal\" as well.\n\n>> +\t\torig_size = delta_size;\n>> +\t\tif (delta)\n>> +\t\t\tdelta = deflate_it(delta, delta_size, &delta_size);\n>\n> Here you're leaking the original delta buffer memory.\n\nIndeed.  Thanks.\n"},{"id":"19572","messageId":"Pine.LNX.4.64.0605051431390.24505@localhost.localdomain","threadId":"4062","inReplyTo":"7vejz8z80p.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] binary patch.","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-05-05T18:33:01Z","receivedAt":"2006-05-05T18:33:01Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Fri, 5 May 2006, Junio C Hamano wrote:\n\n> Nicolas Pitre <nico@cam.org> writes:\n> \n> >> +\tdelta = NULL;\n> >> +\tdeflated = deflate_it(two->ptr, two->size, &deflate_size);\n> >> +\tif (one->size && two->size) {\n> >> +\t\tdelta = diff_delta(one->ptr, one->size,\n> >> +\t\t\t\t   two->ptr, two->size,\n> >> +\t\t\t\t   &delta_size, deflate_size);\n> >\n> > Here you probably want to use deflate_size-1 (deflate_size can't be 0).\n> \n> I am not sure if -1 is worth here.\n> \n> The delta is going to be deflated and hopefully gets a bit\n> smaller, so if we really care that level of detail, it might be\n> worth to do (deflate_size*3/2) or something like that here, use\n> delta with or without deflate whichever is smaller, and mark the\n> uncompressed delta with a different tag (\"uncompressed delta\"?).\n> And for symmetry, to deal with uncompressible data, we may want\n> to have \"uncompressed literal\" as well.\n\nNah...  Please just forget that.  ;-)\n\n\nNicolas\n"},{"id":"19581","messageId":"7vac9wxom0.fsf@assigned-by-dhcp.cox.net","threadId":"4062","inReplyTo":"Pine.LNX.4.64.0605051431390.24505@localhost.localdomain","subject":"Re: [PATCH] binary patch.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-05-05T19:23:19Z","receivedAt":"2006-05-05T19:23:19Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nicolas Pitre <nico@cam.org> writes:\n\n> On Fri, 5 May 2006, Junio C Hamano wrote:\n>\n>> The delta is going to be deflated and hopefully gets a bit\n>> smaller, so if we really care that level of detail, it might be\n>> worth to do (deflate_size*3/2) or something like that here, use\n>> delta with or without deflate whichever is smaller, and mark the\n>> uncompressed delta with a different tag (\"uncompressed delta\"?).\n>> And for symmetry, to deal with uncompressible data, we may want\n>> to have \"uncompressed literal\" as well.\n>\n> Nah...  Please just forget that.  ;-)\n\nI was serious about the above actually.\n\nBTW, this \"binary patch\" opens a different can of worms.\n\nCurrently, the diff uses a heuristic borrowed from GNU diff \n(I did not look at the code when I did it, but it is described\nin its documentation) to decide if a file is binary (look at the\nfirst few bytes and find NUL).  I am sure people will want to\nhave a way to say \"that heuristic fails but this _is_ a binary\nfile and please treat it as such\".\n\nThere are two, both valid, I think, ways to do it.\n\n - give an option to \"diff\" that says \"treat this path as binary\n   for this invocation of the program\".\n\n - give an attribute to blob object that says \"this blob is\n   binary and should be treated as such\".\n\nThe latter is probably the right way to go in the longer term.\n\nA blob being binary or not is a property of the content and does\nnot depend on where it sits in the history, so unlike \"recording\nrenames as a hint in commit objects\", the attribute is at the\nblob level, not at the commit nor the tree that points at the\nblob.\n\nBut \"binaryness\" affects only certain operations that extract\nthe data (e.g. diff and grep) and not others (e.g. fetch).\nAlso, it makes sense to being able to retroactively mark a blob,\nwhich was not marked as such originally, is a binary.  So I do\nnot think it should be recorded in the object header.\n\nWhich suggests that we may perhaps want to have notes that can\nbe attached to existing objects to augment them without changing\nthe contents of the data, and have tools notice these notes when\nthey are available.  Another example is to associate correct\nMIME types to blobs so, gitweb _blob_ links can do sensible\nthings to them.\n\nThese external notes are purely for Porcelains (in the context\nof this sentence \"diff\" and \"grep\" are Porcelain), but we would\nalso want a way to propagate them across repositories somehow.\nIn a sense, \"grafts\" information is similar to the external\nnotes in that it augments existing commit objects, but its\neffect is a bit more intrusive; it affects the way the core\noperates.\n"},{"id":"19585","messageId":"Pine.LNX.4.64.0605051547420.24505@localhost.localdomain","threadId":"4062","inReplyTo":"7vac9wxom0.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] binary patch.","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-05-05T20:07:40Z","receivedAt":"2006-05-05T20:07:40Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Fri, 5 May 2006, Junio C Hamano wrote:\n\n> Nicolas Pitre <nico@cam.org> writes:\n> \n> > On Fri, 5 May 2006, Junio C Hamano wrote:\n> >\n> >> The delta is going to be deflated and hopefully gets a bit\n> >> smaller, so if we really care that level of detail, it might be\n> >> worth to do (deflate_size*3/2) or something like that here, use\n> >> delta with or without deflate whichever is smaller, and mark the\n> >> uncompressed delta with a different tag (\"uncompressed delta\"?).\n> >> And for symmetry, to deal with uncompressible data, we may want\n> >> to have \"uncompressed literal\" as well.\n> >\n> > Nah...  Please just forget that.  ;-)\n> \n> I was serious about the above actually.\n\nAnd I think this is overkill.\n\nFirst, if a deflated delta is to be _larger_ than its inflated version \nthis is because the delta data is really really short, most probably \nshorter than a single base85 line.  Same for literal data.\n\nSo I truely think the pretty special and rare case where not deflating \nmight be smaller is simply not worth the added complexity.\n\n> BTW, this \"binary patch\" opens a different can of worms.\n> \n> Currently, the diff uses a heuristic borrowed from GNU diff \n> (I did not look at the code when I did it, but it is described\n> in its documentation) to decide if a file is binary (look at the\n> first few bytes and find NUL).  I am sure people will want to\n> have a way to say \"that heuristic fails but this _is_ a binary\n> file and please treat it as such\".\n> \n> There are two, both valid, I think, ways to do it.\n> \n>  - give an option to \"diff\" that says \"treat this path as binary\n>    for this invocation of the program\".\n> \n>  - give an attribute to blob object that says \"this blob is\n>    binary and should be treated as such\".\n> \n> The latter is probably the right way to go in the longer term.\n\nI'm not sure I agree.\n\n> A blob being binary or not is a property of the content and does\n> not depend on where it sits in the history, so unlike \"recording\n> renames as a hint in commit objects\", the attribute is at the\n> blob level, not at the commit nor the tree that points at the\n> blob.\n\nWell, sort of.\n\n> But \"binaryness\" affects only certain operations that extract\n> the data (e.g. diff and grep) and not others (e.g. fetch).\n> Also, it makes sense to being able to retroactively mark a blob,\n> which was not marked as such originally, is a binary.  So I do\n> not think it should be recorded in the object header.\n\nAgreed.\n\n> Which suggests that we may perhaps want to have notes that can\n> be attached to existing objects to augment them without changing\n> the contents of the data, and have tools notice these notes when\n> they are available.  Another example is to associate correct\n> MIME types to blobs so, gitweb _blob_ links can do sensible\n> things to them.\n\nI think blobs are the wrong level to attach such notes.  If you go that \npath you'll have to add as many entries for the number of blobs many \nrevisions of the same file might have.\n\nInstead I think it should be attached to files.  After all being a \nbinary or not is a file attribute regardless of its revision.  And \nimplementation wise I'd do it as a .gitbin file listing all names of \nfiles that should be considered as binaries, with path globing and all, \njust like .gitignore currently lists files that should be ignored.\n\nAnd the advantage is that those .gitbin files can be distributed and \nrevision-controlled just like the .gitignore files.\n\nAnd in addition to those files you could have a section in the repo \nconfig file listing default name patterns for files that are considered \nbinaries.  Or even a section, if present, that lists patterns for files \nthat are _not_ binaries since that list might certainly be shorter.  \nThere could be a corresponding .gittext as well.\n\nAnd in the absence of any of those then the default automatic euristic \napplies.\n\n\nNicolas\n"},{"id":"19586","messageId":"Pine.LNX.4.64.0605051605340.6713@iabervon.org","threadId":"4062","inReplyTo":"7vac9wxom0.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] binary patch.","fromName":"Daniel Barkalow","fromEmail":"barkalow@iabervon.org","sentAt":"2006-05-05T20:33:55Z","receivedAt":"2006-05-05T20:33:55Z","isPatch":true,"sender":{"key":"barkalow@iabervon.org","avatar":"https://avatars.githubusercontent.com/u/55364219?v=4"},"body":"On Fri, 5 May 2006, Junio C Hamano wrote:\n\n> But \"binaryness\" affects only certain operations that extract\n> the data (e.g. diff and grep) and not others (e.g. fetch).\n> Also, it makes sense to being able to retroactively mark a blob,\n> which was not marked as such originally, is a binary.  So I do\n> not think it should be recorded in the object header.\n\nWhy do you think it makes sense to retroactively mark a blob with things \nlike binariness or MIME type? To the extent that the information is not \npossible to extract from the blob contents, it seems to me to be a \npermanent aspect of the blob. And I could see having blobs with the same \ncontent but different type information (that one is a ZIP archive, while \nthis one is a OpenDocument file), and tools may care how they were \nspecified, and the user would want to be able to track how they had \nhistorically been marked, if the system allows them to be marked at all.\n\nOf course, there's still the issue of how this info is generated for a new \nblob; I think it should live in the index for tracked files and come from \na .gitignore-style file for new files. (For that matter, there could be a \n.gitmetadata file, which would handle \"ignore\" as well as binary and \nwhatever other info you want to produce about your not-previously-tracked \nfiles.)\n\n\t-Daniel\n*This .sig left intentionally blank*\n"},{"id":"19588","messageId":"7vmzdww60f.fsf@assigned-by-dhcp.cox.net","threadId":"4062","inReplyTo":"Pine.LNX.4.64.0605051605340.6713@iabervon.org","subject":"Re: [PATCH] binary patch.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-05-05T20:50:24Z","receivedAt":"2006-05-05T20:50:24Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Daniel Barkalow <barkalow@iabervon.org> writes:\n\n> On Fri, 5 May 2006, Junio C Hamano wrote:\n>\n>> But \"binaryness\" affects only certain operations that extract\n>> the data (e.g. diff and grep) and not others (e.g. fetch).\n>> Also, it makes sense to being able to retroactively mark a blob,\n>> which was not marked as such originally, is a binary.  So I do\n>> not think it should be recorded in the object header.\n>\n> Why do you think it makes sense to retroactively mark a blob with things \n> like binariness or MIME type? To the extent that the information is not \n> possible to extract from the blob contents, it seems to me to be a \n> permanent aspect of the blob. And I could see having blobs with the same \n> content but different type information (that one is a ZIP archive, while \n> this one is a OpenDocument file), and tools may care how they were \n> specified, and the user would want to be able to track how they had \n> historically been marked, if the system allows them to be marked at all.\n>\n> Of course, there's still the issue of how this info is generated for a new \n> blob; I think it should live in the index for tracked files and come from \n> a .gitignore-style file for new files. (For that matter, there could be a \n> .gitmetadata file, which would handle \"ignore\" as well as binary and \n> whatever other info you want to produce about your not-previously-tracked \n> files.)\n\nI think Nico's solution (compromise?) is the right and most\npractical one.\n"},{"id":"19600","messageId":"7vwtcztxcp.fsf@assigned-by-dhcp.cox.net","threadId":"4062","inReplyTo":"7vy7xgzsiu.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH] binary patch.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-05-06T07:40:22Z","receivedAt":"2006-05-06T07:40:22Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <junkio@cox.net> writes:\n\n>> Yeah, things still to be done are deflating both delta and\n>> optionally perhaps use just deflate without delta for \"new file\"\n>> codepath.\n>>\n>> And testsuite.\n>\n> -- >8 --\n> [PATCH] binary diff: further updates.\n>...\n> Signed-off-by: Junio C Hamano <junkio@cox.net>\n>\n> ---\n>\n>  * Have done only very minimum testing, and unlike somebody else ;-)\n>    my code is not always perfect, so this will still stay out of\n>    \"next\" for a while.\n\nOK, now it passes the testsuite I wrote, so I'll push this out\nin \"next\".  I was not drunk while doing the testsuite so the\ncode now must be perfect ;-).\n"}]}