{"thread":{"id":"2812","subject":"diff-core segfault","startedAt":"2005-12-12T16:29:50Z","lastAt":"2005-12-13T03:23:48Z","messageCount":15,"participants":["Darrin Thompson","Johannes Schindelin","Junio C Hamano","Nicolas Pitre","Linus Torvalds"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"13513","messageId":"1134404990.5928.4.camel@localhost.localdomain","threadId":"2812","inReplyTo":null,"subject":"diff-core segfault","fromName":"Darrin Thompson","fromEmail":"darrint@progeny.com","sentAt":"2005-12-12T16:29:50Z","receivedAt":"2005-12-12T16:29:50Z","isPatch":false,"sender":{"key":"darrint@progeny.com","avatar":null},"body":"$ mkdir a\n$ cd a/\n$ git-init-db\ndefaulting to local storage area\n$ touch a\n$ git-update-index --add a\n$ git-commit -m 'message'\nCommitting initial tree 496d6428b9cf92981dc9495211e6e1120fb6f2ba\n$ echo hello >a\n$ git-diff-files\n:100644 100644 e69de29bb2d1d6434b8b29ae775ad8c2e48c5391\n0000000000000000000000000000000000000000 M      a\n$ git-diff-files -B\nSegmentation fault\n\nDisclaimer: I'm running 1.0rc2. I did some searching of recent mailing\nlist posts and commits. I see no evidence that this has been addressed.\n\nCould someone confirm that this exists on more recent git heads and fix\nif needed?\n\nThanks.\n\n--\nDarrin\n"},{"id":"13514","messageId":"Pine.LNX.4.63.0512121754340.6749@wbgn013.biozentrum.uni-wuerzburg.de","threadId":"2812","inReplyTo":"1134404990.5928.4.camel@localhost.localdomain","subject":"Re: diff-core segfault","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2005-12-12T16:56:36Z","receivedAt":"2005-12-12T16:56:36Z","isPatch":false,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Mon, 12 Dec 2005, Darrin Thompson wrote:\n\n> $ git-diff-files -B\n> Segmentation fault\n\nThis looks exactly like the problem on cygwin which is fixed by using \nNO_MMAP=YesPlease.\n\nHow about enabling NO_MMAP=YesPlease on cygwin per default? I think there \nare enough cases where it helps. If it is too slow *and* the user knows \nwhat she's doing, she can recompile NO_MMAP=NoNoNo.\n\nOpinions, please?\n\nCiao,\nDscho\n"},{"id":"13522","messageId":"7vmzj6i206.fsf@assigned-by-dhcp.cox.net","threadId":"2812","inReplyTo":"1134404990.5928.4.camel@localhost.localdomain","subject":"Re: diff-core segfault","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-12-12T18:50:01Z","receivedAt":"2005-12-12T18:50:01Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Darrin Thompson <darrint@progeny.com> writes:\n\n> Could someone confirm that this exists on more recent git heads and fix\n> if needed?\n\n(1) Yup.  I can reproduce it.\n(2) Will look into it when able.\n"},{"id":"13523","messageId":"7virtui1kj.fsf_-_@assigned-by-dhcp.cox.net","threadId":"2812","inReplyTo":"7vmzj6i206.fsf@assigned-by-dhcp.cox.net","subject":"Delitifier broken (Re: diff-core segfault)","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-12-12T18:59:24Z","receivedAt":"2005-12-12T18:59:24Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Junio C Hamano <junkio@cox.net> writes:\n\n> Darrin Thompson <darrint@progeny.com> writes:\n>\n>> Could someone confirm that this exists on more recent git heads and fix\n>> if needed?\n>\n> (1) Yup.  I can reproduce it.\n> (2) Will look into it when able.\n\nThis is not just \"diff\".  Our deltify code is half-broken, and\nin the worst case this can corrupt our packs if an empty blob is\ninvolved.\n\nThe problem is if from_size or to_size is empty, it does not\nproduce any.\n\n        if (!from_size || !to_size || delta_prepare(from_buf, from_size, &bdf))\n                return NULL;\n\t\n\nI think either we need to make the users more careful or fix\ndeltifier to produce trivial delta.  I'd vote for the latter;\nlet me rig up something.\n"},{"id":"13525","messageId":"7vacf6hwwc.fsf@assigned-by-dhcp.cox.net","threadId":"2812","inReplyTo":"1134404990.5928.4.camel@localhost.localdomain","subject":"[PATCH 2/2] diff-delta.c: allow delta with empty blob.","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-12-12T20:40:19Z","receivedAt":"2005-12-12T20:40:19Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Delta computation with an empty blob used to punt and returned NULL.\nThis commit allows creation with empty blob; all combination of\nempty->empty, empty->something, and something->empty are allowed.\n\nSigned-off-by: Junio C Hamano <junkio@cox.net>\n\n---\n\n Darrin Thompson <darrint@progeny.com> writes:\n\n > $ git-diff-files -B\n > Segmentation fault\n\n > Could someone confirm that this exists on more recent git heads and fix\n > if needed?\n\n Could you try this patch?  It is marked as 2/2 but 1/2 is a\n test script to reproduce the problem with the current code,\n which this patch is supposed to fix, and this should be the\n only fix you need.\n\n delta.h      |    4 ++--\n diff-delta.c |    2 +-\n 2 files changed, 3 insertions(+), 3 deletions(-)\n\n1e4d6f6618abb72e3948419d113a6f2f14c83ebc\ndiff --git a/delta.h b/delta.h\nindex 31d1820..c6a4763 100644\n--- a/delta.h\n+++ b/delta.h\n@@ -9,8 +9,8 @@ extern void *patch_delta(void *src_buf, \n \t\t\t void *delta_buf, unsigned long delta_size,\n \t\t\t unsigned long *dst_size);\n \n-/* the smallest possible delta size is 4 bytes */\n-#define DELTA_SIZE_MIN\t4\n+/* the smallest possible delta size is 2 bytes (empty to empty) */\n+#define DELTA_SIZE_MIN\t2\n \n /*\n  * This must be called twice on the delta data buffer, first to get the\ndiff --git a/diff-delta.c b/diff-delta.c\nindex b2ae7b5..cf50138 100644\n--- a/diff-delta.c\n+++ b/diff-delta.c\n@@ -213,7 +213,7 @@ void *diff_delta(void *from_buf, unsigne\n \tbdrecord_t *brec;\n \tbdfile_t bdf;\n \n-\tif (!from_size || !to_size || delta_prepare(from_buf, from_size, &bdf))\n+\tif (delta_prepare(from_buf, from_size, &bdf))\n \t\treturn NULL;\n \t\n \toutpos = 0;\n-- \n0.99.9.GIT\n"},{"id":"13530","messageId":"1134421972.5928.48.camel@localhost.localdomain","threadId":"2812","inReplyTo":"7vacf6hwwc.fsf@assigned-by-dhcp.cox.net","subject":"Re: [PATCH 2/2] diff-delta.c: allow delta with empty blob.","fromName":"Darrin Thompson","fromEmail":"darrint@progeny.com","sentAt":"2005-12-12T21:12:51Z","receivedAt":"2005-12-12T21:12:51Z","isPatch":true,"sender":{"key":"darrint@progeny.com","avatar":null},"body":"On Mon, 2005-12-12 at 12:40 -0800, Junio C Hamano wrote:\n>  Could you try this patch?  It is marked as 2/2 but 1/2 is a\n>  test script to reproduce the problem with the current code,\n>  which this patch is supposed to fix, and this should be the\n>  only fix you need.\n\nI'm almost out of time for today. Possibly tomorrow I can get to it.\n\n--\nDarrin\n"},{"id":"13531","messageId":"Pine.LNX.4.64.0512121620380.26663@localhost.localdomain","threadId":"2812","inReplyTo":"7virtui1kj.fsf_-_@assigned-by-dhcp.cox.net","subject":"Re: Delitifier broken (Re: diff-core segfault)","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2005-12-12T21:28:49Z","receivedAt":"2005-12-12T21:28:49Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Mon, 12 Dec 2005, Junio C Hamano wrote:\n\n> Junio C Hamano <junkio@cox.net> writes:\n> \n> > Darrin Thompson <darrint@progeny.com> writes:\n> >\n> >> Could someone confirm that this exists on more recent git heads and fix\n> >> if needed?\n> >\n> > (1) Yup.  I can reproduce it.\n> > (2) Will look into it when able.\n> \n> This is not just \"diff\".  Our deltify code is half-broken, and\n> in the worst case this can corrupt our packs if an empty blob is\n> involved.\n\nI would say involving an empty blob with deltas _is_ the bug in the \nfirst place.  Please don't let that happen.\n\nEspecially with pack files, an empty blob can be represented with a \n_single_ byte.  A delta must always be against something else and simply \nstoring the reference for the object the delta is against will always \nuse at least 20 bytes even for empty ones.\n\n> The problem is if from_size or to_size is empty, it does not\n> produce any.\n> \n>         if (!from_size || !to_size || delta_prepare(from_buf, from_size, &bdf))\n>                 return NULL;\n> \t\n> \n> I think either we need to make the users more careful or fix\n> deltifier to produce trivial delta.  I'd vote for the latter;\n> let me rig up something.\n\nIf my opinion is still of any weight I'd strongly vote for the former.  \nA delta against an empty object, or a delta that produces an empty \nobject simply makes no sense since it is always suboptimal compared to\nstoring the non deltified object (or finding another object to deltify \nagainst).  Allowing empty deltas only paper over another more \nfundamental bug IMHO.\n\n\nNicolas\n"},{"id":"13533","messageId":"7vek4igevq.fsf@assigned-by-dhcp.cox.net","threadId":"2812","inReplyTo":"Pine.LNX.4.64.0512121620380.26663@localhost.localdomain","subject":"Re: Delitifier broken (Re: diff-core segfault)","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-12-12T21:54:49Z","receivedAt":"2005-12-12T21:54:49Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nicolas Pitre <nico@cam.org> writes:\n\n>> This is not just \"diff\".  Our deltify code is half-broken, and\n>> in the worst case this can corrupt our packs if an empty blob is\n>> involved.\n>\n> I would say involving an empty blob with deltas _is_ the bug in the \n> first place.  Please don't let that happen.\n\nNot all use of delta is to produce a pack.  An empty->empty\ndelta is a valid two byte \\0\\0 sequence, and I do not see any\nreason to forbid it.  Although using such delta to represent\nanything in a pack does *not* make any sense as you say, it\nmakes other callers simpler if they do not have to check if\nfrom_len and to_len are empty before calling the delta code.\nThey care about from_len=0 (or to_len=0) case to produce similar\nresults as from_len=1 (or to_len=1) case and do not care at all\nabout the produced delta being a useful one for compressed\nstorage purposes.\n\n> Especially with pack files, an empty blob can be represented with a \n> _single_ byte.  A delta must always be against something else and simply \n> storing the reference for the object the delta is against will always \n> use at least 20 bytes even for empty ones.\n\nTrue, and the pack code is actually safe.  It punts on NULL\nreturn, so my initial worry about packs turns out to be\nunneeded.\n\n> If my opinion is still of any weight I'd strongly vote for the former.  \n\nI ended up doing both ;-).  The call site of diffcore-break was\ncertainly careless and broken (fixed); I've run git-grep to\ncheck all callers to diff_delta() and the only one that did not\ncheck the return value with NULL was the one that started with\nthread.\n"},{"id":"13535","messageId":"Pine.LNX.4.64.0512121529200.15597@g5.osdl.org","threadId":"2812","inReplyTo":"7vek4igevq.fsf@assigned-by-dhcp.cox.net","subject":"Re: Delitifier broken (Re: diff-core segfault)","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-12-12T23:31:42Z","receivedAt":"2005-12-12T23:31:42Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 12 Dec 2005, Junio C Hamano wrote:\n> Nicolas Pitre <nico@cam.org> writes:\n> >\n> > I would say involving an empty blob with deltas _is_ the bug in the \n> > first place.  Please don't let that happen.\n\nI agree with Nicolas.\n\n> Not all use of delta is to produce a pack.  An empty->empty\n> delta is a valid two byte \\0\\0 sequence, and I do not see any\n> reason to forbid it.  Although using such delta to represent\n> anything in a pack does *not* make any sense as you say, it\n> makes other callers simpler if they do not have to check if\n> from_len and to_len are empty before calling the delta code.\n\nAnd you don't need to.\n\nDo what pack-objects.c does: just call \"diff_delta()\" and check the result \nfor NULL. If the result is NULL, then you have to do some special code, \nbecause that means that it's a full create or a full delete (or it's an \nunchanged empty file). Regardless, it really _is_ a special case, and it \nwould be silly to generate a delta for it.\n\n\t\tLinus\n"},{"id":"13544","messageId":"7vlkypdcsb.fsf@assigned-by-dhcp.cox.net","threadId":"2812","inReplyTo":"Pine.LNX.4.64.0512121529200.15597@g5.osdl.org","subject":"Re: Delitifier broken (Re: diff-core segfault)","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-12-13T01:08:20Z","receivedAt":"2005-12-13T01:08:20Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds <torvalds@osdl.org> writes:\n\n> Do what pack-objects.c does: just call \"diff_delta()\" and check the result \n> for NULL. If the result is NULL, then you have to do some special code, \n> because that means that it's a full create or a full delete (or it's an \n> unchanged empty file). Regardless, it really _is_ a special case, and it \n> would be silly to generate a delta for it.\n\nWhen the result is NULL, it could be delta against empty, or\nother failure in diff_delta() (could be it exceeded max_size,\ncould be it could not allocate memory, could be we introduced\nsome other failure modes later...).\n\nI'll revert the changes anyway, but not because I necessarily\nagree with you two.  I am not 100% confident that the core of\nthe diff_delta code would work fine with empty input (it seems\nto from my limited test), and I do not want to break things\nunnecessarily at this point.  More importantly, for the updated\ndelta code that allows empty input to work, the codepaths the\nvarious existing callers that check with NULL must not be\nassuming non-NULL return means non empty input -- otherwise my\nchange would subtly break things -- and I do not have enough\nenergy to verify that right now.\n\nSince we do not break files smaller than MINIMUM_BREAK_SIZE,\nthis becomes a non-issue with the attached patch.  I do not know\nwhy I did not check both sides when I did it the first time; I\ndo not know why I was too stupid to notice that the earlier test\nin the if() was far more expensive than the later one, either ;-).\n\n-- >8 --\ndiff --git a/diffcore-break.c b/diffcore-break.c\nindex e6a468e..9b27456 100644\n--- a/diffcore-break.c\n+++ b/diffcore-break.c\n@@ -55,12 +55,6 @@ static int should_break(struct diff_file\n \t\t\t     * is the default.\n \t\t\t     */\n \n-\tif (!S_ISREG(src->mode) || !S_ISREG(dst->mode))\n-\t\treturn 0; /* leave symlink rename alone */\n-\n-\tif (diff_populate_filespec(src, 0) || diff_populate_filespec(dst, 0))\n-\t\treturn 0; /* error but caught downstream */\n-\n \tbase_size = ((src->size < dst->size) ? src->size : dst->size);\n \n \tdelta = diff_delta(src->data, src->size,\n@@ -169,9 +163,15 @@ void diffcore_break(int break_score)\n \t\tif (DIFF_FILE_VALID(p->one) && DIFF_FILE_VALID(p->two) &&\n \t\t    !S_ISDIR(p->one->mode) && !S_ISDIR(p->two->mode) &&\n \t\t    !strcmp(p->one->path, p->two->path)) {\n-\t\t\tif (should_break(p->one, p->two,\n-\t\t\t\t\t break_score, &score) &&\n-\t\t\t    MINIMUM_BREAK_SIZE <= p->one->size) {\n+\t\t\t\n+\t\t\tif (S_ISREG(p->one->mode) &&\n+\t\t\t    S_ISREG(p->two->mode) &&\n+\t\t\t    !diff_populate_filespec(p->one, 0) &&\n+\t\t\t    MINIMUM_BREAK_SIZE <= p->one->size &&\n+\t\t\t    !diff_populate_filespec(p->two, 0) &&\n+\t\t\t    MINIMUM_BREAK_SIZE <= p->two->size &&\n+\t\t\t    should_break(p->one, p->two,\n+\t\t\t\t\t break_score, &score)) {\n \t\t\t\t/* Split this into delete and create */\n \t\t\t\tstruct diff_filespec *null_one, *null_two;\n \t\t\t\tstruct diff_filepair *dp;\n"},{"id":"13547","messageId":"Pine.LNX.4.64.0512121720150.15597@g5.osdl.org","threadId":"2812","inReplyTo":"7vlkypdcsb.fsf@assigned-by-dhcp.cox.net","subject":"Re: Delitifier broken (Re: diff-core segfault)","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-12-13T01:34:28Z","receivedAt":"2005-12-13T01:34:28Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 12 Dec 2005, Junio C Hamano wrote:\n> \n> I'll revert the changes anyway, but not because I necessarily\n> agree with you two.  I am not 100% confident that the core of\n> the diff_delta code would work fine with empty input (it seems\n> to from my limited test), and I do not want to break things\n> unnecessarily at this point.\n\nWell, I checked the pack-objects.c side, and your patch to diff_delta() \nshould not hurt at least there. We already check the size and would have \nbroken out long before if either side was zero-sized.\n\nBut that's kind of part of the point - any user of diff_delta() is likely \nto have checked the size anyway for other reasons. There's just very \nseldom any valid reason to generate a delta against an empty file, there's \nno interesting information that diff_delta() can really give us.\n\nBasically, the binary diffs that diff-delta returns are interesting for \njust two things:\n\n - efficient packing, in the pack-objects.c style.\n\n   As mentioned, pack-objects.c needs to check the size heuristics before \n   doing diff_delta() _anyway_, for performance reasons as well as simply \n   because the secondary use of diff_delta() is to estimate how big the \n   delta is, and it's always pointless to generate a delta that is \n   guaranteed to be bigger than the file (which is always the case with \n   either side being an empty file - the size difference will inevitably \n   be bigger than the size of the resulting file).\n\n - difference size estimation (ie for rename/copy detection)\n\n   This boils down to the same case as the secondary use of pack-objects, \n   ie delta size estimation. Again, if either side is empty, we _know_ \n   that the delta generation is pointless, because the delta is always \n   going to be bigger than the end result, and thus it can't be sensible \n   for rename/copy detection.\n\nSo in one sense I actually agree with your patch: it makes the deltifier \ncode more generic and actually simplifies the diff_delta() code a bit by \navoiding one special case, and in that sense it's a good change.\n\nSo the reason I disagree with it is that doing the delta is always going \nto be unnecessary work. And regardless of how we're ever going to use the \ndelta, we _know_ that it's unnecessary work.\n\nSo I think your diffcore-break.c patch is much more appropriate: it also \nfixes the bug, but it fixes it by virtue of realizing that the delta \ncannot matter and thus should never even be computed.\n\nNow, your diff_setup() change may actually be worth it because of the \nsimplification, but on the other hand, you can also consider the NULL \nreturn as being nice because it's effectively a way of saying \"the delta \nis meaningless, why did you even ask me?\"\n\n\t\t\tLinus\n"},{"id":"13549","messageId":"7vhd9ddb9a.fsf@assigned-by-dhcp.cox.net","threadId":"2812","inReplyTo":"Pine.LNX.4.64.0512121720150.15597@g5.osdl.org","subject":"Re: Delitifier broken (Re: diff-core segfault)","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-12-13T01:41:21Z","receivedAt":"2005-12-13T01:41:21Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Linus Torvalds <torvalds@osdl.org> writes:\n\n> So I think your diffcore-break.c patch is much more appropriate: it also \n> fixes the bug, but it fixes it by virtue of realizing that the delta \n> cannot matter and thus should never even be computed.\n\nAgreed, redone and pushed out.\n"},{"id":"13551","messageId":"Pine.LNX.4.64.0512121758410.15597@g5.osdl.org","threadId":"2812","inReplyTo":"Pine.LNX.4.64.0512121720150.15597@g5.osdl.org","subject":"Re: Delitifier broken (Re: diff-core segfault)","fromName":"Linus Torvalds","fromEmail":"torvalds@osdl.org","sentAt":"2005-12-13T02:05:59Z","receivedAt":"2005-12-13T02:05:59Z","isPatch":false,"sender":{"key":"torvalds@linux-foundation.org","avatar":"https://avatars.githubusercontent.com/u/1024025?v=4"},"body":"\n\nOn Mon, 12 Dec 2005, Linus Torvalds wrote:\n> \n>    As mentioned, pack-objects.c needs to check the size heuristics before \n>    doing diff_delta() _anyway_, for performance reasons as well as simply \n>    because the secondary use of diff_delta() is to estimate how big the \n>    delta is, and it's always pointless to generate a delta that is \n>    guaranteed to be bigger than the file (which is always the case with \n>    either side being an empty file - the size difference will inevitably \n>    be bigger than the size of the resulting file).\n\nSide note: this isn't technically entirely true. A binary diff that has a \nsource file that is empty could in theory be smaller than the destination \nfile simply because it may involve a certain amount of automatic \ncompression in the form of \"insert 100 spaces\" kind of diff encoding. I'm \nnot sure whether xdelta actually does something like that, but it's \ncertainly possible at least in theory.\n\nOf course, even if the delta in such a case may be smaller than the \nresulting file, such a delta is still not interesting: even from a packing \nangle, if the resulting file has patterns that makes it easy to generate a \nsmall delta against an empty file, the fact is, such a regular end result \nwill _compress_ better than the delta will, assuming any decent \ncompression mechanism.\n\nSo from a packing standpoint, generating the delta is still the wrong \nthing to do - you're better off with just compressing the undeltified \nresult.\n\nAnd from a similarity-estimation standpoint, going from an empty file to \nanything else is also obviously not interesting either. An empty file \ncannot be \"similar\" to anything else (except perhaps another empty file, \nand even that is a matter of taste).\n\nI just wanted to correct the technicality that delta's can certainly be \nsmaller than the result at least if the delta format allows for that kind \nof encoding.\n\n\t\tLinus\n"},{"id":"13553","messageId":"Pine.LNX.4.64.0512122114090.26663@localhost.localdomain","threadId":"2812","inReplyTo":"Pine.LNX.4.64.0512121758410.15597@g5.osdl.org","subject":"Re: Delitifier broken (Re: diff-core segfault)","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2005-12-13T02:45:16Z","receivedAt":"2005-12-13T02:45:16Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Mon, 12 Dec 2005, Linus Torvalds wrote:\n\n> \n> \n> On Mon, 12 Dec 2005, Linus Torvalds wrote:\n> > \n> >    As mentioned, pack-objects.c needs to check the size heuristics before \n> >    doing diff_delta() _anyway_, for performance reasons as well as simply \n> >    because the secondary use of diff_delta() is to estimate how big the \n> >    delta is, and it's always pointless to generate a delta that is \n> >    guaranteed to be bigger than the file (which is always the case with \n> >    either side being an empty file - the size difference will inevitably \n> >    be bigger than the size of the resulting file).\n> \n> Side note: this isn't technically entirely true. A binary diff that has a \n> source file that is empty could in theory be smaller than the destination \n> file simply because it may involve a certain amount of automatic \n> compression in the form of \"insert 100 spaces\" kind of diff encoding. I'm \n> not sure whether xdelta actually does something like that, but it's \n> certainly possible at least in theory.\n\nxdelta doesn't.  It only has two functions currently:\n\n 1) copy x bytes from offset y in source file to current position in \n    destination file;\n\n 2) paste the x following bytes straight from the delta stream to \n    current position into the destination file.\n\nOf course in the GIT context files are buffers.\n\nHowever I added the possibility for (1) to use the destination file as \nwell as the \"source\" file for block copy in patch_delta().  However \ndiff_delta() currently doesn't use that capability.  But if it did then \nthe \"insert 100 spaces\" would be:\n\n\t- paste \\x20\\x20\\x20\\x20 to dest\n\t  (delta = 5 bytes, dest = 4 bytes)\n\n\t- copy 4 bytes from offset 0 of dest to dest\n\t  (delta = 7 bytes, dest = 8 bytes)\n\n\t- copy 8 bytes from offset 0 of dest to dest\n\t  (delta = 9 bytes, dest = 16 bytes)\n\n\t- copy 16 bytes from offset 0 of dest to dest\n\t  (delta = 11 bytes, dest = 32 bytes)\n\n\t- copy 32 bytes from offset 0 of dest to dest\n\t  (delta = 13 bytes, dest = 64 bytes)\n\n\t- copy 36 bytes from offset 0 of dest to dest\n\t  (delta = 15 bytes, dest = 100 bytes)\n\nAnd yet that could be optimized further with a better size for the \ninitial paste.  However adding that capability to diff_delta() might \nmake it significantly slower for still unknown gain for real life data.  \nBut I should write the code some day.\n\n\nNicolas\n"},{"id":"13555","messageId":"7v8xupd6ij.fsf@assigned-by-dhcp.cox.net","threadId":"2812","inReplyTo":"Pine.LNX.4.64.0512122114090.26663@localhost.localdomain","subject":"Re: Delitifier broken (Re: diff-core segfault)","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2005-12-13T03:23:48Z","receivedAt":"2005-12-13T03:23:48Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nicolas Pitre <nico@cam.org> writes:\n\n> However I added the possibility for (1) to use the destination file as \n> well as the \"source\" file for block copy in patch_delta().\n\nAh, I've been wondering where that one came from.\n"}]}