{"thread":{"id":"3938","subject":"RFC: New diff-delta.c implementation","startedAt":"2006-04-21T21:16:10Z","lastAt":"2006-04-25T18:22:23Z","messageCount":32,"participants":["Geert Bosch","Junio C Hamano","Davide Libenzi","Nicolas Pitre","Rene Scharfe","Rutger Nijlunsing","Petr Baudis"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"18981","messageId":"602974A9-09A3-46E9-92D6-D30728923C11@adacore.com","threadId":"3938","inReplyTo":null,"subject":"RFC: New diff-delta.c implementation","fromName":"Geert Bosch","fromEmail":"bosch@adacore.com","sentAt":"2006-04-21T21:16:10Z","receivedAt":"2006-04-21T21:16:10Z","isPatch":false,"sender":{"key":"bosch@adacore.com","avatar":null},"body":"I wrote a new binary differencing algorithm that is both faster\nand generates smaller deltas than the current implementation.\nThe format is compatible with that used by patch-delta, so\nit should be easy to integrate.\n\nOriginally, I wrote this for the GDIFF format, see http://www.w3.org/ \nTR/NOTE-gdiff-19970901.\nThe adaptation for GIT format was relatively simple, but is not \nthoroughly tested.\nThe code is not derived from libxdiff, but uses the rabin_slide \nfunction written\nby David Mazieres (dm@uun.org). Also the tables are generated using \nhis code.\nFinally, this was developed on Darwin, and not a Linux system, so \nsome changes may be needed.\n\nInitial testing seems quite positive, take for example git-1.2.5.tar \nvs git-1.2.6.tar\non my PowerBook (both with -O2 -DNDEBUG):\n\ncurrent: 2.281s, patch size 36563\nnew : 0.109s, patch size 16199\n\nPlease feel free to play around with this code, and give feedback.\nKeep in mind this wasn't originally written for GIT, and C is not\nmy native language, so don't mind my formatting etc.\n\n -Geert\n\n"},{"id":"19009","messageId":"Pine.LNX.4.64.0604212308080.2215@localhost.localdomain","threadId":"3938","inReplyTo":"602974A9-09A3-46E9-92D6-D30728923C11@adacore.com","subject":"Re: RFC: New diff-delta.c implementation","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-04-22T03:19:31Z","receivedAt":"2006-04-22T03:19:31Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Fri, 21 Apr 2006, Geert Bosch wrote:\n\n> I wrote a new binary differencing algorithm that is both faster\n> and generates smaller deltas than the current implementation.\n> The format is compatible with that used by patch-delta, so\n> it should be easy to integrate.\n\nIt looks really interesting.\n\nIt ignores the max_size argument but that is trivially fixed.\n\nThen it triggers some assertions in the code when running the test \nsuite.\n\n> Originally, I wrote this for the GDIFF format, see\n> http://www.w3.org/TR/NOTE-gdiff-19970901.\n> The adaptation for GIT format was relatively simple, but is not thoroughly\n> tested.\n\nSome trivial tests look fine but it fail on some others.\n\n> The code is not derived from libxdiff, but uses the rabin_slide function\n> written\n> by David Mazieres (dm@uun.org). Also the tables are generated using his code.\n> Finally, this was developed on Darwin, and not a Linux system, so some changes\n> may be needed.\n\nIt does compile out of the box on Linux.\n\n> Please feel free to play around with this code, and give feedback.\n> Keep in mind this wasn't originally written for GIT, and C is not\n> my native language, so don't mind my formatting etc.\n\nI did reformat it a bit to be more inline with the rest of GIT's coding \nstyle (and to help me read it). I'll look at fixing the issues I can \nfix and post it back.\n\n\nNicolas\n"},{"id":"18994","messageId":"Pine.LNX.4.64.0604212220070.22622@alien.or.mcafeemobile.com","threadId":"3938","inReplyTo":"602974A9-09A3-46E9-92D6-D30728923C11@adacore.com","subject":"Re: RFC: New diff-delta.c implementation","fromName":"Davide Libenzi","fromEmail":"davidel@xmailserver.org","sentAt":"2006-04-22T05:21:56Z","receivedAt":"2006-04-22T05:21:56Z","isPatch":false,"sender":{"key":"davidel@xmailserver.org","avatar":null},"body":"On Fri, 21 Apr 2006, Geert Bosch wrote:\n\n> I wrote a new binary differencing algorithm that is both faster\n> and generates smaller deltas than the current implementation.\n> The format is compatible with that used by patch-delta, so\n> it should be easy to integrate.\n>\n> Originally, I wrote this for the GDIFF format, see \n> http://www.w3.org/TR/NOTE-gdiff-19970901.\n> The adaptation for GIT format was relatively simple, but is not thoroughly \n> tested.\n> The code is not derived from libxdiff, but uses the rabin_slide function \n> written\n> by David Mazieres (dm@uun.org). Also the tables are generated using his code.\n> Finally, this was developed on Darwin, and not a Linux system, so some \n> changes may be needed.\n>\n> Initial testing seems quite positive, take for example git-1.2.5.tar vs \n> git-1.2.6.tar\n> on my PowerBook (both with -O2 -DNDEBUG):\n>\n> current: 2.281s, patch size 36563\n> new : 0.109s, patch size 16199\n\nGeert, the code needs some works IMO ;), but otherwise very lever idea to \nuse Rabin's polynomials and impressive results!\n\n\n\n- Davide\n"},{"id":"18986","messageId":"A2284531-175D-4357-B766-B87BDB357B32@adacore.com","threadId":"3938","inReplyTo":"Pine.LNX.4.64.0604212220070.22622@alien.or.mcafeemobile.com","subject":"Re: RFC: New diff-delta.c implementation","fromName":"Geert Bosch","fromEmail":"bosch@adacore.com","sentAt":"2006-04-22T09:12:35Z","receivedAt":"2006-04-22T09:12:35Z","isPatch":false,"sender":{"key":"bosch@adacore.com","avatar":null},"body":"\nOn Apr 22, 2006, at 01:21, Davide Libenzi wrote:\n\n> Geert, the code needs some works IMO ;), but otherwise very lever \n> idea to use Rabin's polynomials and impressive results!\n\nI'm fixing the obvious mistakes: as the code was lifted from\nmy stand-alone command processing a single source file, I didn't\nbother freeing memory, as process exit would do that anyway.\n\nAlso, there are a few issues that cropped up as I adapted\nthe output from GDIFF format to the one used by GIT.\nI'll post a new version when I'm done.\nPlease withhold further judgment until then. :)\n\n -Geert\n"},{"id":"19004","messageId":"A856A2C5-2BD7-4DC5-9CCC-CD53E9A2623C@adacore.com","threadId":"3938","inReplyTo":"Pine.LNX.4.64.0604212308080.2215@localhost.localdomain","subject":"Re: RFC: New diff-delta.c implementation","fromName":"Geert Bosch","fromEmail":"bosch@adacore.com","sentAt":"2006-04-22T11:04:38Z","receivedAt":"2006-04-22T11:04:38Z","isPatch":false,"sender":{"key":"bosch@adacore.com","avatar":null},"body":"\nOn Apr 21, 2006, at 23:19, Nicolas Pitre wrote:\n> It looks really interesting.\n>\n> It ignores the max_size argument but that is trivially fixed.\n>\n> Then it triggers some assertions in the code when running the test\n> suite.\nYes, these were errors in the change to the GIT output format.\nThey were trivially fixed. More importantly, I didn't finalize\nthe indexing data, since the code was originally used in a stand-alone\nprogram that would terminate after the diff.\n\n> I did reformat it a bit to be more inline with the rest of GIT's \n> coding\n> style (and to help me read it). I'll look at fixing the issues I can\n> fix and post it back.\n\nPlease apply the attached patch first.\n\n -Geert\n\nBTW. It's a shame that we don't reuse the index when comparing one \nsource\n against multiple targets. Creating the index takes about 70% of \nthe time.\n\n"},{"id":"19001","messageId":"7v7j5hkglq.fsf@assigned-by-dhcp.cox.net","threadId":"3938","inReplyTo":"A856A2C5-2BD7-4DC5-9CCC-CD53E9A2623C@adacore.com","subject":"Re: RFC: New diff-delta.c implementation","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-04-22T11:13:53Z","receivedAt":"2006-04-22T11:13:53Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Geert Bosch writes:\n\n> BTW. It's a shame that we don't reuse the index when comparing one\n> source\n> against multiple targets. Creating the index takes about 70% of\n> the time.\n\n(Please line-wrap sensibly).\n\nI think we tried that with Nico/Davide's delta already, and IIRC\nwe had mixed results.\n\nIt really depends on how big an index for a source is. Keep in\nmind that we keep --window (default=10) of the source text\nin-core, and you are suggesting to keep index in-core as well,\nso we need to take memory pressure into account.\n\nHaving said that, the initial number you posted suggests the\nalgorithm is very fast, in which case reusing index may not\nmatter. We will see ;-).\n"},{"id":"18999","messageId":"6794F5B2-A277-4CD9-9BA8-509F86378E68@adacore.com","threadId":"3938","inReplyTo":"7v7j5hkglq.fsf@assigned-by-dhcp.cox.net","subject":"Re: RFC: New diff-delta.c implementation","fromName":"Geert Bosch","fromEmail":"bosch@adacore.com","sentAt":"2006-04-22T12:35:14Z","receivedAt":"2006-04-22T12:35:14Z","isPatch":false,"sender":{"key":"bosch@adacore.com","avatar":null},"body":"\nOn Apr 22, 2006, at 07:13, Junio C Hamano wrote:\n> (Please line-wrap sensibly).\nApologies. I'm using a broken mailer, which insists\non breaking longish lines. I'll try to avoid this.\n\n> I think we tried that with Nico/Davide's delta already, and IIRC\n> we had mixed results.\n>\n> It really depends on how big an index for a source is. Keep\n> in mind that we keep --window (default=10) of the source\n> text in-core, and you are suggesting to keep index in-core\n> as well, so we need to take memory pressure into account.\nThe point is that if we do the following comparisons:\n\n diff A B\n diff A C\n diff A D\n\nthen we should keep A and its index in core for all\nthree comparisons. Discarding and recreating can never\nbe better :)\n> Having said that, the initial number you posted suggests the\n> algorithm is very fast, in which case reusing index may not\n> matter. We will see ;-).\n\nBTW, after applying the obvious fixes, I get the following\nmessage:\npotomac%./git-pack-objects --no-reuse-delta --stdout I wrote a new binary differencing algorithm that is both faster and\n> generates smaller deltas than the current implementation. The format\n> is compatible with that used by patch-delta, so it should be easy to\n> integrate.\n[...]\n> Initial testing seems quite positive, take for example git-1.2.5.tar\n> vs git-1.2.6.tar on my PowerBook (both with -O2 -DNDEBUG):\n> \n> current: 2.281s, patch size 36563\n> new : 0.109s, patch size 16199\n> \n> Please feel free to play around with this code, and give feedback. \n> Keep in mind this wasn't originally written for GIT, and C is not my\n> native language, so don't mind my formatting etc.\n\nnice speedup! Though I cannot comment on what it actually does, I have\nsome comments on style. B-)\n\nCould you please send your code inline, not as an attachment? And\npossibly as a patch with a Signed-off-by: tag (see\nDocumentation/SubmittingPatches)?\n\nRegarding your FIXME comment about endianess: I think you are looking\nfor htonl(). Use it to convert the values from host byte order to\nnetwork byte order (= big endian) and you can get rid of those ugly\nbranches.\n\nYou can use \"indent -npro -kr -i8 -ts8 -l80 -ss -ncs\" to reformat your\ncode into a similar style as used in the rest of git (settings taken\nfrom Lindent which is shipped with the Linux source).\n\nAfter converting to htonl() \"make test\" ran fine on my x86 box. Here is\nwhat I get when I try to repack the git repo, though:\n\n $ git repack -a -d\n Generating pack...\n Done counting 18985 objects.\n Deltifying 18985 objects.\n git-pack-objects: diff-delta.c:766: create_delta: Assertion `ptr -\ndelta == (int)delta_size' failed.\n\nPlease let me know if you need more details.\n\nThanks,\nRené\n"},{"id":"18996","messageId":"Pine.LNX.4.64.0604220835190.2215@localhost.localdomain","threadId":"3938","inReplyTo":"7v7j5hkglq.fsf@assigned-by-dhcp.cox.net","subject":"Re: RFC: New diff-delta.c implementation","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-04-22T12:45:07Z","receivedAt":"2006-04-22T12:45:07Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Sat, 22 Apr 2006, Junio C Hamano wrote:\n\n> Geert Bosch writes:\n> \n> > BTW. It's a shame that we don't reuse the index when comparing one\n> > source\n> > against multiple targets. Creating the index takes about 70% of\n> > the time.\n> \n> I think we tried that with Nico/Davide's delta already, and IIRC\n> we had mixed results.\n\nWell, actually I was measuring a 10% speed improvement with a quick and \nnaive (not memory efficient) approach for pack-objects with the current \nalgorithm.\n\n> It really depends on how big an index for a source is. Keep in\n> mind that we keep --window (default=10) of the source text\n> in-core, and you are suggesting to keep index in-core as well,\n> so we need to take memory pressure into account.\n\nThe idea to avoid memory pressure is to reverse the window processing \nsuch that the object to delta against is constant for the entire window \ninstead of the current logic where the target object is constant. This \nway there would be only one index in memory at all time.\n\n\nNicolas\n"},{"id":"18995","messageId":"Pine.LNX.4.64.0604220846040.2215@localhost.localdomain","threadId":"3938","inReplyTo":"6794F5B2-A277-4CD9-9BA8-509F86378E68@adacore.com","subject":"Re: RFC: New diff-delta.c implementation","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-04-22T12:51:34Z","receivedAt":"2006-04-22T12:51:34Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Sat, 22 Apr 2006, Geert Bosch wrote:\n\n> BTW, after applying the obvious fixes, I get the following\n> message:\n> potomac%./git-pack-objects --no-reuse-delta --stdout Generating pack...\n> Done counting 16984 objects.\n> Deltifying 16984 objects.\n> 100% (16984/16984) done\n> fatal: delta size changed\n> \n> Is this expected now I have a different algorithm?\n\nIt should not.\n\nFirst, pack-objects tries to find the best object combinations producing \nthe smallest delta. Then there is a second pass where the best delta \nare actually written out. When that message appears that means the \ndelta size for the same object pair does not match between those two \npasses.\n\n\nNicolas\n"},{"id":"18997","messageId":"81E2B4A6-3591-418D-9448-47648AF4A687@adacore.com","threadId":"3938","inReplyTo":"Pine.LNX.4.64.0604220846040.2215@localhost.localdomain","subject":"Re: RFC: New diff-delta.c implementation","fromName":"Geert Bosch","fromEmail":"bosch@adacore.com","sentAt":"2006-04-22T13:39:05Z","receivedAt":"2006-04-22T13:39:05Z","isPatch":false,"sender":{"key":"bosch@adacore.com","avatar":null},"body":"\nOn Apr 22, 2006, at 08:51, Nicolas Pitre wrote:\n> First, pack-objects tries to find the best object combinations\n> producing the smallest delta. Then there is a second pass\n> where the best delta are actually written out. When that\n> message appears that means the delta size for the same object\n> pair does not match between those two passes.\n\nOK, thanks for that info. There are very few comments in the\ncode, or specs of either the file format used, or\nfor function arguments. I'll look a the code again with this\ninfo.\n\nWhat is the exact role of the max_size parameter that is\npassed to diff_delta? I took it to mean return 0 if\nthe size of the delta would be bigger than max_size and\nmax_size is nonzero.\n\nI only set *delta_size when returning a nonzero delta.\n\n -Geert\n"},{"id":"18993","messageId":"67A687D6-8C1D-4028-9770-DC86867BF6B5@adacore.com","threadId":"3938","inReplyTo":"Pine.LNX.4.64.0604220835190.2215@localhost.localdomain","subject":"Re: RFC: New diff-delta.c implementation","fromName":"Geert Bosch","fromEmail":"bosch@adacore.com","sentAt":"2006-04-22T14:17:01Z","receivedAt":"2006-04-22T14:17:01Z","isPatch":false,"sender":{"key":"bosch@adacore.com","avatar":null},"body":"\nOn Apr 22, 2006, at 08:45, Nicolas Pitre wrote:\n> The idea to avoid memory pressure is to reverse the window processing\n> such that the object to delta against is constant for the entire \n> window\n> instead of the current logic where the target object is constant. \n> This\n> way there would be only one index in memory at all time.\n\nRight, this is essential. In my measurements, diff-delta\nspends about 70% of time generating the index, and 30%\nmatching.\n\nRight now, for 10 candidates per file, we'd do 11 units of\nwork, since we repeat the final delta. When reusing the\nindex, and keeping the smallest delta around, we'd use\n0.7 + 3 = 3.7 units of work. This is almost a 3x speedup.\nThere's no way we can get decent performance without this.\nWith the similarity fingerprints, another factor 2x should\nbe attainable, by only considering the 3 files with the\nnearest fingerprints.\n\n -Geert\n"},{"id":"18984","messageId":"7v3bg5k0ev.fsf@assigned-by-dhcp.cox.net","threadId":"3938","inReplyTo":"81E2B4A6-3591-418D-9448-47648AF4A687@adacore.com","subject":"Re: RFC: New diff-delta.c implementation","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-04-22T17:03:36Z","receivedAt":"2006-04-22T17:03:36Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Geert Bosch writes:\n\n> On Apr 22, 2006, at 08:51, Nicolas Pitre wrote:\n>> First, pack-objects tries to find the best object combinations\n>> producing the smallest delta. Then there is a second pass\n>> where the best delta are actually written out. When that\n>> message appears that means the delta size for the same object\n>> pair does not match between those two passes.\n>\n> OK, thanks for that info. There are very few comments in the\n> code, or specs of either the file format used, or\n> for function arguments. I'll look a the code again with this\n> info.\n\nInitially I thought it would be irrelevant to your work, but\ngenerating packs is the only way to really exercise the diff-delta\ncode these days; Documentation/technical/pack-format.txt might\nhelp.\n\n> What is the exact role of the max_size parameter that is\n> passed to diff_delta? I took it to mean return 0 if\n> the size of the delta would be bigger than max_size and\n> max_size is nonzero.\n\nNo, that is a _strong_ hint to tell diff_delta to quit early\nwithout wasting cycles if the result exceeds the given size,\neither because we already have a delta smaller than that, or\nbecause we expect to get an undeltified representation\ncompressed down to that size. So if your algorithm cannot\nnotice early stage of the processing if the result would exceed\nthat max_size, just code things to ignore it first.\n"},{"id":"18988","messageId":"EB4042E4-D74E-4346-A9CA-50E9CB33F18C@adacore.com","threadId":"3938","inReplyTo":"7v3bg5k0ev.fsf@assigned-by-dhcp.cox.net","subject":"Re: RFC: New diff-delta.c implementation","fromName":"Geert Bosch","fromEmail":"bosch@adacore.com","sentAt":"2006-04-22T17:28:23Z","receivedAt":"2006-04-22T17:28:23Z","isPatch":false,"sender":{"key":"bosch@adacore.com","avatar":null},"body":"\nOn Apr 22, 2006, at 13:03, Junio C Hamano wrote:\n>> What is the exact role of the max_size parameter that\n>> is passed to diff_delta? I took it to mean return 0 if\n>> the size of the delta would be bigger than max_size and\n>> max_size is nonzero.\n>\n> No, that is a _strong_ hint to tell diff_delta to quit\n> early without wasting cycles if the result exceeds the\n> given size, either because we already have a delta smaller\n> than that, or because we expect to get an undeltified\n> representation compressed down to that size. So if\n> your algorithm cannot notice early stage of the processing\n> if the result would exceed that max_size, just code things\n> to ignore it first.\n\nThat's about how I implemented it in my last patch.\nIs it correct that 0 means that there is no max_size?\nShould I set *delta_size to 0 when doing an early\nreturn, or leave it alone?\n\nNote that this really is a micro-optimization, since\nall the expensive stuff is the indexing and then the\nmatching. Since my algorithm matches both forward and\nbackward, there is no way to know that the patch size\ncan't be optimized until after matching completes,\neven though it will never actually create the patch\nor allocate memory for it.\n\n -Geert\n"},{"id":"18989","messageId":"7vslo5ikmk.fsf@assigned-by-dhcp.cox.net","threadId":"3938","inReplyTo":"Pine.LNX.4.64.0604220835190.2215@localhost.localdomain","subject":"Re: RFC: New diff-delta.c implementation","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-04-22T17:29:55Z","receivedAt":"2006-04-22T17:29:55Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Nicolas Pitre writes:\n\n> Well, actually I was measuring a 10% speed improvement with a quick and \n> naive (not memory efficient) approach for pack-objects with the current \n> algorithm.\n>...\n> The idea to avoid memory pressure is to reverse the window processing \n> such that the object to delta against is constant for the entire window \n> instead of the current logic where the target object is constant. This \n> way there would be only one index in memory at all time.\n\nYour are right. The first led to the latter unexplored idea.\n\nI expect to be offline most of the day today, and have other\nthings I can work on for the next few days anyway, so if you or\nsomebody else have an inclination and energy to reverse the\ndelta window, I would appreciate that.\n\nMaybe the calling convention of diff-delta.c would become\nsomething like this?\n\nstruct delta_index; /* opaque to the caller; implementation\n\t\t * defines what's in it.\n */\n\n/* returns a newly allocated struct delta_index.\n * input \"buf\" pointer can be stored in the struct, but \"buf\"\n * does not belong to diff-delta module (i.e. borrowed reference).\n */\nstruct delta_index *delta_index(\n void *buf,\t\t\t/* input: from buffer */\n unsigned long size,\t\t/* input: from size */\n);\n\n/* ... so free the structure and its internal data, but\n * do not free the borrowed reference!\n */\nvoid free_delta_index(struct delta_index *);\n\n/* Take \"from\", an already preprocessed delta_index for the\n * traditional from_buffer/from_size, and to_buf/to_size, and\n * produce delta in newly allocated buffer (caller should\n * free() when it is done), and return the result size in\n * *delta_size. Stop early if the result would exceed max_size.\n */\nvoid *diff_delta(\n struct delta_index *from,\t/* input: prepared by delta_index() */\n void *to_buf,\t\t/* input: destination buffer */\n unsigned long to_size,\t/* input: destination size */\n unsigned long *delta_size,\t/* output: result size */\n unsigned long max_size\t/* input: do not waste cycles if\n you cannot generate result\n smaller than this */\n);\n\nand the calling convention would be:\n\n\tstruct unpacked *s, *d;\n\tunsigned long max_size;\n\n\t/* precompute the index */\n\tstruct delta_index *src = delta_index(s->data, s->entry->size);\n\n\t/* do the delta */\n void *delta_buf = diff_delta(src, d->data, d->entry->size,\n &sz, max_size);\n /* do useful thing here on delta_buf and sz */\n free(delta_buf);\n\n\t/* the caller can reuse *src with other *d,\n * but when it is done...\n */\n free_delta_index(src);\n"},{"id":"18991","messageId":"7vd5f9ijcy.fsf@assigned-by-dhcp.cox.net","threadId":"3938","inReplyTo":"EB4042E4-D74E-4346-A9CA-50E9CB33F18C@adacore.com","subject":"Re: RFC: New diff-delta.c implementation","fromName":"Junio C Hamano","fromEmail":"junkio@cox.net","sentAt":"2006-04-22T17:57:17Z","receivedAt":"2006-04-22T17:57:17Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Geert Bosch writes:\n\n> That's about how I implemented it in my last patch.\n> Is it correct that 0 means that there is no max_size?\n> Should I set *delta_size to 0 when doing an early\n> return, or leave it alone?\n\nWhen failing, I think\nthe convention is to return NULL and what you do with *delta_size\ndoes not matter, but Nico and pack-objects.c code can answer\nthat better than I can ;-).\n\n> Note that this really is a micro-optimization,\n\nTrue. max_size is a hint, and the caller validates the size\nindependently anyway, so ignoring is fine.\n"},{"id":"18998","messageId":"Pine.LNX.4.64.0604221556170.2215@localhost.localdomain","threadId":"3938","inReplyTo":"7vslo5ikmk.fsf@assigned-by-dhcp.cox.net","subject":"Re: RFC: New diff-delta.c implementation","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-04-22T19:58:46Z","receivedAt":"2006-04-22T19:58:46Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Sat, 22 Apr 2006, Junio C Hamano wrote:\n\n> Nicolas Pitre writes:\n> \n> > Well, actually I was measuring a 10% speed improvement with a quick and \n> > naive (not memory efficient) approach for pack-objects with the current \n> > algorithm.\n> >...\n> > The idea to avoid memory pressure is to reverse the window processing \n> > such that the object to delta against is constant for the entire window \n> > instead of the current logic where the target object is constant. This \n> > way there would be only one index in memory at all time.\n> \n> Your are right. The first led to the latter unexplored idea.\n> \n> I expect to be offline most of the day today, and have other\n> things I can work on for the next few days anyway, so if you or\n> somebody else have an inclination and energy to reverse the\n> delta window, I would appreciate that.\n\nI'll probably give it a try.\n\nI'm still reviewing Geert's code right now and found minor things \npertaining to the GIT delta encoding here and there which probably \nexplain why it doesn't pack the Linux kernel archive yet.\n\n\nNicolas\n"},{"id":"19003","messageId":"Pine.LNX.4.64.0604221333470.23166@alien.or.mcafeemobile.com","threadId":"3938","inReplyTo":"602974A9-09A3-46E9-92D6-D30728923C11@adacore.com","subject":"Re: RFC: New diff-delta.c implementation","fromName":"Davide Libenzi","fromEmail":"davidel@xmailserver.org","sentAt":"2006-04-22T20:36:07Z","receivedAt":"2006-04-22T20:36:07Z","isPatch":false,"sender":{"key":"davidel@xmailserver.org","avatar":null},"body":"On Fri, 21 Apr 2006, Geert Bosch wrote:\n\n> I wrote a new binary differencing algorithm that is both faster\n> and generates smaller deltas than the current implementation.\n> The format is compatible with that used by patch-delta, so\n> it should be easy to integrate.\n>\n> Originally, I wrote this for the GDIFF format, see \n> http://www.w3.org/TR/NOTE-gdiff-19970901.\n> The adaptation for GIT format was relatively simple, but is not thoroughly \n> tested.\n> The code is not derived from libxdiff, but uses the rabin_slide function \n> written\n> by David Mazieres (dm@uun.org). Also the tables are generated using his code.\n> Finally, this was developed on Darwin, and not a Linux system, so some \n> changes may be needed.\n>\n> Initial testing seems quite positive, take for example git-1.2.5.tar vs \n> git-1.2.6.tar\n> on my PowerBook (both with -O2 -DNDEBUG):\n>\n> current: 2.281s, patch size 36563\n> new : 0.109s, patch size 16199\n>\n> Please feel free to play around with this code, and give feedback.\n> Keep in mind this wasn't originally written for GIT, and C is not\n> my native language, so don't mind my formatting etc.\n\nGeert, I saw you're using a shift of 55 bits, that gives an degree of the \nroot polynomial of 63, that is not prime. Where did you get the root \npolynomial, and why you did not chose 61 as degree of the root?\nJust curious ...\n\n\n\n- Davide\n"},{"id":"19014","messageId":"20060423023144.GA17704@adacore.com","threadId":"3938","inReplyTo":"Pine.LNX.4.64.0604221333470.23166@alien.or.mcafeemobile.com","subject":"Re: RFC: New diff-delta.c implementation","fromName":"Geert Bosch","fromEmail":"bosch@adacore.com","sentAt":"2006-04-23T02:31:44Z","receivedAt":"2006-04-23T02:31:44Z","isPatch":false,"sender":{"key":"bosch@adacore.com","avatar":null},"body":"On Sat, Apr 22, 2006 at 01:36:07PM -0700, Davide Libenzi wrote:\n> Geert, I saw you're using a shift of 55 bits, that gives an degree of the \n> root polynomial of 63, that is not prime. Where did you get the root \n> polynomial, and why you did not chose 61 as degree of the root?\n> Just curious ...\n\nThe polynomial was randomly created using code by David Mazieres, that\nis part of LBFS. I chose a (irreducible) polynomial of degree 63 as\nthat was the same as LBFS did. As for my purposes it's best to have\na constant polynomial and I wanted to have all the code for\nthe computations in the same compilation unit for performance,\nI decided to just have a little program print out the tables\nand include it directly. The chosen polynomial was 0xb15e234bd3792f63.\n\nLater on I haven't revisited this decision, although I agree that\nit'd probably be a good idea to use a polynomial of prime degree,\neven though we're not looking for cryptographically strong hashes here.\n\nBelow I include new tables for degree 61. The window size of 22 was\nfound by plotting graphs on a number of largish test cases (30-100MB)\nand seeing how the size of the compressed output changed. It is\nessential to do all comparisons using gzipped output. I've been\ntempted a number of times to include new optimizations, only\nto find out that the uncompressed size reduced, but final compressed\nsize grew. More smaller copies and literal data segments is generally\nworse.\n\n -Geert\n\n#define RABIN_POLY 0x25bd5331c0d7096dULL\n#define RABIN_DEGREE 61\n#define RABIN_SHIFT 53\n#define RABIN_WINDOW_SIZE 22\n\nunsigned long long T[256] =\n{ 0x0000000000000000ULL, 0x25bd5331c0d7096dULL, 0x4b7aa66381ae12daULL,\n 0x6ec7f55241791bb7ULL, 0x96f54cc7035c25b4ULL, 0xb3481ff6c38b2cd9ULL,\n 0xdd8feaa482f2376eULL, 0xf832b99542253e03ULL, 0x0857cabfc66f4205ULL,\n 0x2dea998e06b84b68ULL, 0x432d6cdc47c150dfULL, 0x66903fed871659b2ULL,\n 0x9ea28678c53367b1ULL, 0xbb1fd54905e46edcULL, 0xd5d8201b449d756bULL,\n 0xf065732a844a7c06ULL, 0x10af957f8cde840aULL, 0x3512c64e4c098d67ULL,\n 0x5bd5331c0d7096d0ULL, 0x7e68602dcda79fbdULL, 0x865ad9b88f82a1beULL,\n 0xa3e78a894f55a8d3ULL, 0xcd207fdb0e2cb364ULL, 0xe89d2ceacefbba09ULL,\n 0x18f85fc04ab1c60fULL, 0x3d450cf18a66cf62ULL, 0x5382f9a3cb1fd4d5ULL,\n 0x763faa920bc8ddb8ULL, 0x8e0d130749ede3bbULL, 0xabb04036893aead6ULL,\n 0xc577b564c843f161ULL, 0xe0cae6550894f80cULL, 0x04e279ced96a0179ULL,\n 0x215f2aff19bd0814ULL, 0x4f98dfad58c413a3ULL, 0x6a258c9c98131aceULL,\n 0x92173509da3624cdULL, 0xb7aa66381ae12da0ULL, 0xd96d936a5b983617ULL,\n 0xfcd0c05b9b4f3f7aULL, 0x0cb5b3711f05437cULL, 0x2908e040dfd24a11ULL,\n 0x47cf15129eab51a6ULL, 0x627246235e7c58cbULL, 0x9a40ffb61c5966c8ULL,\n 0xbffdac87dc8e6fa5ULL, 0xd13a59d59df77412ULL, 0xf4870ae45d207d7fULL,\n 0x144decb155b48573ULL, 0x31f0bf8095638c1eULL, 0x5f374ad2d41a97a9ULL,\n 0x7a8a19e314cd9ec4ULL, 0x82b8a07656e8a0c7ULL, 0xa705f347963fa9aaULL,\n 0xc9c20615d746b21dULL, 0xec7f55241791bb70ULL, 0x1c1a260e93dbc776ULL,\n 0x39a7753f530cce1bULL, 0x5760806d1275d5acULL, 0x72ddd35cd2a2dcc1ULL,\n 0x8aef6ac99087e2c2ULL, 0xaf5239f85050ebafULL, 0xc195ccaa1129f018ULL,\n 0xe4289f9bd1fef975ULL, 0x09c4f39db2d402f2ULL, 0x2c79a0ac72030b9fULL,\n 0x42be55fe337a1028ULL, 0x670306cff3ad1945ULL, 0x9f31bf5ab1882746ULL,\n 0xba8cec6b715f2e2bULL, 0xd44b19393026359cULL, 0xf1f64a08f0f13cf1ULL,\n 0x0193392274bb40f7ULL, 0x242e6a13b46c499aULL, 0x4ae99f41f515522dULL,\n 0x6f54cc7035c25b40ULL, 0x976675e577e76543ULL, 0xb2db26d4b7306c2eULL,\n 0xdc1cd386f6497799ULL, 0xf9a180b7369e7ef4ULL, 0x196b66e23e0a86f8ULL,\n 0x3cd635d3fedd8f95ULL, 0x5211c081bfa49422ULL, 0x77ac93b07f739d4fULL,\n 0x8f9e2a253d56a34cULL, 0xaa237914fd81aa21ULL, 0xc4e48c46bcf8b196ULL,\n 0xe159df777c2fb8fbULL, 0x113cac5df865c4fdULL, 0x3481ff6c38b2cd90ULL,\n 0x5a460a3e79cbd627ULL, 0x7ffb590fb91cdf4aULL, 0x87c9e09afb39e149ULL,\n 0xa274b3ab3beee824ULL, 0xccb346f97a97f393ULL, 0xe90e15c8ba40fafeULL,\n 0x0d268a536bbe038bULL, 0x289bd962ab690ae6ULL, 0x465c2c30ea101151ULL,\n 0x63e17f012ac7183cULL, 0x9bd3c69468e2263fULL, 0xbe6e95a5a8352f52ULL,\n 0xd0a960f7e94c34e5ULL, 0xf51433c6299b3d88ULL, 0x057140ecadd1418eULL,\n 0x20cc13dd6d0648e3ULL, 0x4e0be68f2c7f5354ULL, 0x6bb6b5beeca85a39ULL,\n 0x93840c2bae8d643aULL, 0xb6395f1a6e5a6d57ULL, 0xd8feaa482f2376e0ULL,\n 0xfd43f979eff47f8dULL, 0x1d891f2ce7608781ULL, 0x38344c1d27b78eecULL,\n 0x56f3b94f66ce955bULL, 0x734eea7ea6199c36ULL, 0x8b7c53ebe43ca235ULL,\n 0xaec100da24ebab58ULL, 0xc006f5886592b0efULL, 0xe5bba6b9a545b982ULL,\n 0x15ded593210fc584ULL, 0x306386a2e1d8cce9ULL, 0x5ea473f0a0a1d75eULL,\n 0x7b1920c16076de33ULL, 0x832b99542253e030ULL, 0xa696ca65e284e95dULL,\n 0xc8513f37a3fdf2eaULL, 0xedec6c06632afb87ULL, 0x1389e73b65a805e4ULL,\n 0x3634b40aa57f0c89ULL, 0x58f34158e406173eULL, 0x7d4e126924d11e53ULL,\n 0x857cabfc66f42050ULL, 0xa0c1f8cda623293dULL, 0xce060d9fe75a328aULL,\n 0xebbb5eae278d3be7ULL, 0x1bde2d84a3c747e1ULL, 0x3e637eb563104e8cULL,\n 0x50a48be72269553bULL, 0x7519d8d6e2be5c56ULL, 0x8d2b6143a09b6255ULL,\n 0xa8963272604c6b38ULL, 0xc651c7202135708fULL, 0xe3ec9411e1e279e2ULL,\n 0x03267244e97681eeULL, 0x269b217529a18883ULL, 0x485cd42768d89334ULL,\n 0x6de18716a80f9a59ULL, 0x95d33e83ea2aa45aULL, 0xb06e6db22afdad37ULL,\n 0xdea998e06b84b680ULL, 0xfb14cbd1ab53bfedULL, 0x0b71b8fb2f19c3ebULL,\n 0x2eccebcaefceca86ULL, 0x400b1e98aeb7d131ULL, 0x65b64da96e60d85cULL,\n 0x9d84f43c2c45e65fULL, 0xb839a70dec92ef32ULL, 0xd6fe525fadebf485ULL,\n 0xf343016e6d3cfde8ULL, 0x176b9ef5bcc2049dULL, 0x32d6cdc47c150df0ULL,\n 0x5c1138963d6c1647ULL, 0x79ac6ba7fdbb1f2aULL, 0x819ed232bf9e2129ULL,\n 0xa42381037f492844ULL, 0xcae474513e3033f3ULL, 0xef592760fee73a9eULL,\n 0x1f3c544a7aad4698ULL, 0x3a81077bba7a4ff5ULL, 0x5446f229fb035442ULL,\n 0x71fba1183bd45d2fULL, 0x89c9188d79f1632cULL, 0xac744bbcb9266a41ULL,\n 0xc2b3beeef85f71f6ULL, 0xe70eeddf3888789bULL, 0x07c40b8a301c8097ULL,\n 0x227958bbf0cb89faULL, 0x4cbeade9b1b2924dULL, 0x6903fed871659b20ULL,\n 0x9131474d3340a523ULL, 0xb48c147cf397ac4eULL, 0xda4be12eb2eeb7f9ULL,\n 0xfff6b21f7239be94ULL, 0x0f93c135f673c292ULL, 0x2a2e920436a4cbffULL,\n 0x44e9675677ddd048ULL, 0x61543467b70ad925ULL, 0x99668df2f52fe726ULL,\n 0xbcdbdec335f8ee4bULL, 0xd21c2b917481f5fcULL, 0xf7a178a0b456fc91ULL,\n 0x1a4d14a6d77c0716ULL, 0x3ff0479717ab0e7bULL, 0x5137b2c556d215ccULL,\n 0x748ae1f496051ca1ULL, 0x8cb85861d42022a2ULL, 0xa9050b5014f72bcfULL,\n 0xc7c2fe02558e3078ULL, 0xe27fad3395593915ULL, 0x121ade1911134513ULL,\n 0x37a78d28d1c44c7eULL, 0x5960787a90bd57c9ULL, 0x7cdd2b4b506a5ea4ULL,\n 0x84ef92de124f60a7ULL, 0xa152c1efd29869caULL, 0xcf9534bd93e1727dULL,\n 0xea28678c53367b10ULL, 0x0ae281d95ba2831cULL, 0x2f5fd2e89b758a71ULL,\n 0x419827bada0c91c6ULL, 0x6425748b1adb98abULL, 0x9c17cd1e58fea6a8ULL,\n 0xb9aa9e2f9829afc5ULL, 0xd76d6b7dd950b472ULL, 0xf2d0384c1987bd1fULL,\n 0x02b54b669dcdc119ULL, 0x270818575d1ac874ULL, 0x49cfed051c63d3c3ULL,\n 0x6c72be34dcb4daaeULL, 0x944007a19e91e4adULL, 0xb1fd54905e46edc0ULL,\n 0xdf3aa1c21f3ff677ULL, 0xfa87f2f3dfe8ff1aULL, 0x1eaf6d680e16066fULL,\n 0x3b123e59cec10f02ULL, 0x55d5cb0b8fb814b5ULL, 0x7068983a4f6f1dd8ULL,\n 0x885a21af0d4a23dbULL, 0xade7729ecd9d2ab6ULL, 0xc32087cc8ce43101ULL,\n 0xe69dd4fd4c33386cULL, 0x16f8a7d7c879446aULL, 0x3345f4e608ae4d07ULL,\n 0x5d8201b449d756b0ULL, 0x783f528589005fddULL, 0x800deb10cb2561deULL,\n 0xa5b0b8210bf268b3ULL, 0xcb774d734a8b7304ULL, 0xeeca1e428a5c7a69ULL,\n 0x0e00f81782c88265ULL, 0x2bbdab26421f8b08ULL, 0x457a5e74036690bfULL,\n 0x60c70d45c3b199d2ULL, 0x98f5b4d08194a7d1ULL, 0xbd48e7e14143aebcULL,\n 0xd38f12b3003ab50bULL, 0xf6324182c0edbc66ULL, 0x065732a844a7c060ULL,\n 0x23ea61998470c90dULL, 0x4d2d94cbc509d2baULL, 0x6890c7fa05dedbd7ULL,\n 0x90a27e6f47fbe5d4ULL, 0xb51f2d5e872cecb9ULL, 0xdbd8d80cc655f70eULL,\n 0xfe658b3d0682fe63ULL\n};\n\nunsigned long long U[256] =\n{ 0x0000000000000000ULL, 0x067b86c43d6a6cb0ULL, 0x0cf70d887ad4d960ULL,\n 0x0a8c8b4c47beb5d0ULL, 0x19ee1b10f5a9b2c0ULL, 0x1f959dd4c8c3de70ULL,\n 0x151916988f7d6ba0ULL, 0x1362905cb2170710ULL, 0x166165102b846cedULL,\n 0x101ae3d416ee005dULL, 0x1a9668985150b58dULL, 0x1cedee5c6c3ad93dULL,\n 0x0f8f7e00de2dde2dULL, 0x09f4f8c4e347b29dULL, 0x03787388a4f9074dULL,\n 0x0503f54c99936bfdULL, 0x097f991197dfd0b7ULL, 0x0f041fd5aab5bc07ULL,\n 0x05889499ed0b09d7ULL, 0x03f3125dd0616567ULL, 0x1091820162766277ULL,\n 0x16ea04c55f1c0ec7ULL, 0x1c668f8918a2bb17ULL, 0x1a1d094d25c8d7a7ULL,\n 0x1f1efc01bc5bbc5aULL, 0x19657ac58131d0eaULL, 0x13e9f189c68f653aULL,\n 0x1592774dfbe5098aULL, 0x06f0e71149f20e9aULL, 0x008b61d57498622aULL,\n 0x0a07ea993326d7faULL, 0x0c7c6c5d0e4cbb4aULL, 0x12ff32232fbfa16eULL,\n 0x1484b4e712d5cddeULL, 0x1e083fab556b780eULL, 0x1873b96f680114beULL,\n 0x0b112933da1613aeULL, 0x0d6aaff7e77c7f1eULL, 0x07e624bba0c2caceULL,\n 0x019da27f9da8a67eULL, 0x049e5733043bcd83ULL, 0x02e5d1f73951a133ULL,\n 0x08695abb7eef14e3ULL, 0x0e12dc7f43857853ULL, 0x1d704c23f1927f43ULL,\n 0x1b0bcae7ccf813f3ULL, 0x118741ab8b46a623ULL, 0x17fcc76fb62cca93ULL,\n 0x1b80ab32b86071d9ULL, 0x1dfb2df6850a1d69ULL, 0x1777a6bac2b4a8b9ULL,\n 0x110c207effdec409ULL, 0x026eb0224dc9c319ULL, 0x041536e670a3afa9ULL,\n 0x0e99bdaa371d1a79ULL, 0x08e23b6e0a7776c9ULL, 0x0de1ce2293e41d34ULL,\n 0x0b9a48e6ae8e7184ULL, 0x0116c3aae930c454ULL, 0x076d456ed45aa8e4ULL,\n 0x140fd532664daff4ULL, 0x127453f65b27c344ULL, 0x18f8d8ba1c997694ULL,\n 0x1e835e7e21f31a24ULL, 0x004337779fa84bb1ULL, 0x0638b1b3a2c22701ULL,\n 0x0cb43affe57c92d1ULL, 0x0acfbc3bd816fe61ULL, 0x19ad2c676a01f971ULL,\n 0x1fd6aaa3576b95c1ULL, 0x155a21ef10d52011ULL, 0x1321a72b2dbf4ca1ULL,\n 0x16225267b42c275cULL, 0x1059d4a389464becULL, 0x1ad55fefcef8fe3cULL,\n 0x1caed92bf392928cULL, 0x0fcc49774185959cULL, 0x09b7cfb37ceff92cULL,\n 0x033b44ff3b514cfcULL, 0x0540c23b063b204cULL, 0x093cae6608779b06ULL,\n 0x0f4728a2351df7b6ULL, 0x05cba3ee72a34266ULL, 0x03b0252a4fc92ed6ULL,\n 0x10d2b576fdde29c6ULL, 0x16a933b2c0b44576ULL, 0x1c25b8fe870af0a6ULL,\n 0x1a5e3e3aba609c16ULL, 0x1f5dcb7623f3f7ebULL, 0x19264db21e999b5bULL,\n 0x13aac6fe59272e8bULL, 0x15d1403a644d423bULL, 0x06b3d066d65a452bULL,\n 0x00c856a2eb30299bULL, 0x0a44ddeeac8e9c4bULL, 0x0c3f5b2a91e4f0fbULL,\n 0x12bc0554b017eadfULL, 0x14c783908d7d866fULL, 0x1e4b08dccac333bfULL,\n 0x18308e18f7a95f0fULL, 0x0b521e4445be581fULL, 0x0d29988078d434afULL,\n 0x07a513cc3f6a817fULL, 0x01de95080200edcfULL, 0x04dd60449b938632ULL,\n 0x02a6e680a6f9ea82ULL, 0x082a6dcce1475f52ULL, 0x0e51eb08dc2d33e2ULL,\n 0x1d337b546e3a34f2ULL, 0x1b48fd9053505842ULL, 0x11c476dc14eeed92ULL,\n 0x17bff01829848122ULL, 0x1bc39c4527c83a68ULL, 0x1db81a811aa256d8ULL,\n 0x173491cd5d1ce308ULL, 0x114f170960768fb8ULL, 0x022d8755d26188a8ULL,\n 0x04560191ef0be418ULL, 0x0eda8adda8b551c8ULL, 0x08a10c1995df3d78ULL,\n 0x0da2f9550c4c5685ULL, 0x0bd97f9131263a35ULL, 0x0155f4dd76988fe5ULL,\n 0x072e72194bf2e355ULL, 0x144ce245f9e5e445ULL, 0x12376481c48f88f5ULL,\n 0x18bbefcd83313d25ULL, 0x1ec06909be5b5195ULL, 0x00866eef3f509762ULL,\n 0x06fde82b023afbd2ULL, 0x0c71636745844e02ULL, 0x0a0ae5a378ee22b2ULL,\n 0x196875ffcaf925a2ULL, 0x1f13f33bf7934912ULL, 0x159f7877b02dfcc2ULL,\n 0x13e4feb38d479072ULL, 0x16e70bff14d4fb8fULL, 0x109c8d3b29be973fULL,\n 0x1a1006776e0022efULL, 0x1c6b80b3536a4e5fULL, 0x0f0910efe17d494fULL,\n 0x0972962bdc1725ffULL, 0x03fe1d679ba9902fULL, 0x05859ba3a6c3fc9fULL,\n 0x09f9f7fea88f47d5ULL, 0x0f82713a95e52b65ULL, 0x050efa76d25b9eb5ULL,\n 0x03757cb2ef31f205ULL, 0x1017ecee5d26f515ULL, 0x166c6a2a604c99a5ULL,\n 0x1ce0e16627f22c75ULL, 0x1a9b67a21a9840c5ULL, 0x1f9892ee830b2b38ULL,\n 0x19e3142abe614788ULL, 0x136f9f66f9dff258ULL, 0x151419a2c4b59ee8ULL,\n 0x067689fe76a299f8ULL, 0x000d0f3a4bc8f548ULL, 0x0a8184760c764098ULL,\n 0x0cfa02b2311c2c28ULL, 0x12795ccc10ef360cULL, 0x1402da082d855abcULL,\n 0x1e8e51446a3bef6cULL, 0x18f5d780575183dcULL, 0x0b9747dce54684ccULL,\n 0x0decc118d82ce87cULL, 0x07604a549f925dacULL, 0x011bcc90a2f8311cULL,\n 0x041839dc3b6b5ae1ULL, 0x0263bf1806013651ULL, 0x08ef345441bf8381ULL,\n 0x0e94b2907cd5ef31ULL, 0x1df622cccec2e821ULL, 0x1b8da408f3a88491ULL,\n 0x11012f44b4163141ULL, 0x177aa980897c5df1ULL, 0x1b06c5dd8730e6bbULL,\n 0x1d7d4319ba5a8a0bULL, 0x17f1c855fde43fdbULL, 0x118a4e91c08e536bULL,\n 0x02e8decd7299547bULL, 0x049358094ff338cbULL, 0x0e1fd345084d8d1bULL,\n 0x086455813527e1abULL, 0x0d67a0cdacb48a56ULL, 0x0b1c260991dee6e6ULL,\n 0x0190ad45d6605336ULL, 0x07eb2b81eb0a3f86ULL, 0x1489bbdd591d3896ULL,\n 0x12f23d1964775426ULL, 0x187eb65523c9e1f6ULL, 0x1e0530911ea38d46ULL,\n 0x00c55998a0f8dcd3ULL, 0x06bedf5c9d92b063ULL, 0x0c325410da2c05b3ULL,\n 0x0a49d2d4e7466903ULL, 0x192b428855516e13ULL, 0x1f50c44c683b02a3ULL,\n 0x15dc4f002f85b773ULL, 0x13a7c9c412efdbc3ULL, 0x16a43c888b7cb03eULL,\n 0x10dfba4cb616dc8eULL, 0x1a533100f1a8695eULL, 0x1c28b7c4ccc205eeULL,\n 0x0f4a27987ed502feULL, 0x0931a15c43bf6e4eULL, 0x03bd2a100401db9eULL,\n 0x05c6acd4396bb72eULL, 0x09bac08937270c64ULL, 0x0fc1464d0a4d60d4ULL,\n 0x054dcd014df3d504ULL, 0x03364bc57099b9b4ULL, 0x1054db99c28ebea4ULL,\n 0x162f5d5dffe4d214ULL, 0x1ca3d611b85a67c4ULL, 0x1ad850d585300b74ULL,\n 0x1fdba5991ca36089ULL, 0x19a0235d21c90c39ULL, 0x132ca8116677b9e9ULL,\n 0x15572ed55b1dd559ULL, 0x0635be89e90ad249ULL, 0x004e384dd460bef9ULL,\n 0x0ac2b30193de0b29ULL, 0x0cb935c5aeb46799ULL, 0x123a6bbb8f477dbdULL,\n 0x1441ed7fb22d110dULL, 0x1ecd6633f593a4ddULL, 0x18b6e0f7c8f9c86dULL,\n 0x0bd470ab7aeecf7dULL, 0x0daff66f4784a3cdULL, 0x07237d23003a161dULL,\n 0x0158fbe73d507aadULL, 0x045b0eaba4c31150ULL, 0x0220886f99a97de0ULL,\n 0x08ac0323de17c830ULL, 0x0ed785e7e37da480ULL, 0x1db515bb516aa390ULL,\n 0x1bce937f6c00cf20ULL, 0x114218332bbe7af0ULL, 0x17399ef716d41640ULL,\n 0x1b45f2aa1898ad0aULL, 0x1d3e746e25f2c1baULL, 0x17b2ff22624c746aULL,\n 0x11c979e65f2618daULL, 0x02abe9baed311fcaULL, 0x04d06f7ed05b737aULL,\n 0x0e5ce43297e5c6aaULL, 0x082762f6aa8faa1aULL, 0x0d2497ba331cc1e7ULL,\n 0x0b5f117e0e76ad57ULL, 0x01d39a3249c81887ULL, 0x07a81cf674a27437ULL,\n 0x14ca8caac6b57327ULL, 0x12b10a6efbdf1f97ULL, 0x183d8122bc61aa47ULL,\n 0x1e4607e6810bc6f7ULL\n};\n"},{"id":"19032","messageId":"20060424025741.GA636@adacore.com","threadId":"3938","inReplyTo":"444A2334.3030501@lsrfire.ath.cx","subject":"Re: RFC: New diff-delta.c implementation","fromName":"Geert Bosch","fromEmail":"bosch@adacore.com","sentAt":"2006-04-24T02:57:41Z","receivedAt":"2006-04-24T02:57:41Z","isPatch":false,"sender":{"key":"bosch@adacore.com","avatar":null},"body":"On Sat, Apr 22, 2006 at 02:36:04PM +0200, Rene Scharfe wrote:\n> Could you please send your code inline, not as an attachment? And\n> possibly as a patch with a Signed-off-by: tag (see\n> Documentation/SubmittingPatches)?\nFor various reasons, mostly to do with managing and searching huge\nmailboxes, I'm using Apple Mail. What sucks though is that automatic\nline wrapping can't be turned off. This never got fixed, so it's useless\nfor posting inline patches. That said, I now leave a synchronized copy\nof the git repository on my mailserver and use mutt for this reply.\nHopefully things will be better.\n\nNote that I sent this code as a RFC, with explicit disclaimers about\nstyle. So, I did not want to sign off on this code, since I pretty\nmuch knew there would be some problems with the undocumented\n(\"proprietary\", according the libxdiff site) file format. In contrast\nthe GDIFF fileformat was documented very well, and I have a version\nof this code that works flawlessly with that format.\n\n> Regarding your FIXME comment about endianess: I think you are looking\n> for htonl(). Use it to convert the values from host byte order to\n> network byte order (= big endian) and you can get rid of those ugly\n> branches.\nAh, I'll use that. It's of course a slight change that all processing\nnow is big-endian centric, but that might actually even result in\nbetter code in this case. I'm just assuming any decent system has\nsome highly optimized macro for this and will never do a function call.\nThis is used in the most performance critical loops, and doing function\ncalls here will lead to horrendous performance.\n> \n> You can use \"indent -npro -kr -i8 -ts8 -l80 -ss -ncs\" to reformat your\n> code into a similar style as used in the rest of git (settings taken\n> from Lindent which is shipped with the Linux source).\nAlthough I cringe at 8-space indenting, and find much of the GIT\ncode close to unreadable for lack of design-level comments, I'll\ngladly reformat any code to conform to existing code standards.\nPlease let me know if you've got documentation on that, as it would\nbe helpful for me to know what the standard is. (No flame intended. :-)\n> \n> After converting to htonl() \"make test\" ran fine on my x86 box. Here is\n> what I get when I try to repack the git repo, though:\n> \n> $ git repack -a -d\n> Generating pack...\n> Done counting 18985 objects.\n> Deltifying 18985 objects.\n> git-pack-objects: diff-delta.c:766: create_delta: Assertion `ptr -\n> delta == (int)delta_size' failed.\n> \n> Please let me know if you need more details.\nThis was a result of incorrect calculation of the size of copy and\ndata commands. I fixed this in a follow-up patch sent to the list.\nFor any bug reports, they're easiest to fix if you can find a reproducer\nusing test-delta.\n\n -Geert\n"},{"id":"19038","messageId":"Pine.LNX.4.64.0604232327500.3603@localhost.localdomain","threadId":"3938","inReplyTo":"20060424025741.GA636@adacore.com","subject":"Re: RFC: New diff-delta.c implementation","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-04-24T05:27:07Z","receivedAt":"2006-04-24T05:27:07Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Sun, 23 Apr 2006, Geert Bosch wrote:\n\n> Note that I sent this code as a RFC, with explicit disclaimers about\n> style.\n\nI took the liberty of reworking the coding style, as well as simplifying \nsome constructs a bit.\n\nI also fixed all the format encoding and size computations bugs the \noriginal code has so it works perfectly now.\n\n> So, I did not want to sign off on this code, since I pretty\n> much knew there would be some problems with the undocumented\n> (\"proprietary\", according the libxdiff site) file format. In contrast\n> the GDIFF fileformat was documented very well, and I have a version\n> of this code that works flawlessly with that format.\n\nNote that the GIT encoding is itself different (a bit denser) from the \nxdiff encoding.\n\n> > Regarding your FIXME comment about endianess: I think you are looking\n> > for htonl(). Use it to convert the values from host byte order to\n> > network byte order (= big endian) and you can get rid of those ugly\n> > branches.\n> Ah, I'll use that. It's of course a slight change that all processing\n> now is big-endian centric, but that might actually even result in\n> better code in this case. I'm just assuming any decent system has\n> some highly optimized macro for this and will never do a function call.\n> This is used in the most performance critical loops, and doing function\n> calls here will lead to horrendous performance.\n\nPlease just completely drop that word fetch \"optimization\". Not only \ndoes it produce worse assembly code in the end due to the extra loop \ncounter and extra shifting in turn increasing register pressure, but it \nalso assumes that the target data buffer is always word aligned which is \nnot guaranteed (casting a char pointer to an unsigned and dereferencing \nit is not portable since on some architecture such misaligned accesses \nare not allowed). And it even has worse performance. For example, with \nword fetch and shift code, packing the Linux kernel archive on my P4 at \n3GHz:\n\n$ git-repack -a -f\n...\nreal 7m5.727s\nuser 6m33.797s\nsys 0m31.394s\n\nAnd with the word fetch optimization completely ripped out:\n\n$ git-repack -a -f\n...\nreal 6m45.443s\nuser 6m13.911s\nsys 0m31.434s\n\nSo you must be extremely careful when trying to implement such kind of \noptimizations.\n\nNow disabling all assert() statements gives:\n\n$ git-repack -a -f\n...\nreal 6m42.478s\nuser 6m12.031s\nsys 0m31.090s\n\nBut here comes the sad part. Even after simplifying the code as much as \nI could, performance is still significantly worse than the current \ndiff-delta.c code. Repacking again the same Linux kernel repository \nwith the current code:\n\n$ git-repack -a -f\n...\nreal 4m20.742s\nuser 3m52.255s\nsys 0m28.758s\n\nThe final pack is smaller with your code but not significantly: \n117867049 bytes vs 118824550 bytes with the current code, i.e. less than \n1% difference.\n\nYou can find attached my current version of your code.\n\nIn the mean time I'll try replacing the adler32 hashing with your Rabin \npolynomial hashing into the current code just to see if it helps (and I \nthink it will help quite a bit). The best solution might be a mix of \nboth approaches.\n\nOf course there is the issue of reversing the object matching window \nlogic in pack-object.c to further improve things, but I consider that an \northogonal improvement at this point which both approaches will benefit \nfrom anyway.\n\n\nNicolas\n\n\n#include \n\n#include \n\n#include \n\n#include \n\n#include \n\n\n\n#undef assert\n\n#define assert(x) do { } while (0)\n\n\n\n/*\n\n * MIN_HTAB_SIZE is fixed amount to be added to the size of the hash table\n\n * used for indexing and must be a power of two. This allows for small files\n\n * to have a sparse hash table, since in that case it's cheap.\n\n * Hash table sizes are rounded up to a power of two to avoid integer division. \n\n */\n\n#define MIN_HTAB_SIZE 8192\n\n#define MAX_HTAB_SIZE (1024*1024*1024)\n\n\n\n/*\n\n * Diffing files of gigabyte range is impractical with the current\n\n * algorithm, so we're assuming 32-bit sizes everywhere.\n\n * Size leaves some room for expansion when diffing random files.\n\n */\n\n#define MAX_SIZE (0x7eff0000)\n\n\n\n/* Initial size of copies table, dynamically extended as needed. */\n\n#define MAX_COPIES 4096\n\n\n\n/*\n\n * Matching is done using a sliding window for which a Rabin\n\n * polynomial is computed. The advantage of such polynomials is\n\n * that they can efficiently be updated at every position.\n\n * The tables needed for this are precomputed, as it is desirable\n\n * to use the same polynomial all the time for repeatable results.\n\n */\n\n\n\n#if 0\t/* those don't seem to work */\n\n\n\n#define RABIN_POLY 0x25bd5331c0d7096dULL\n\n#define RABIN_DEGREE 61\n\n#define RABIN_SHIFT 53\n\n#define RABIN_WINDOW_SIZE 22\n\n\n\nstatic const u_int64_t T[256] = {\n\n\t0x6ec7f55241791bb7ULL, 0x96f54cc7035c25b4ULL, 0xb3481ff6c38b2cd9ULL,\n\n\t0xdd8feaa482f2376eULL, 0xf832b99542253e03ULL, 0x0857cabfc66f4205ULL,\n\n\t0x2dea998e06b84b68ULL, 0x432d6cdc47c150dfULL, 0x66903fed871659b2ULL,\n\n\t0x9ea28678c53367b1ULL, 0xbb1fd54905e46edcULL, 0xd5d8201b449d756bULL,\n\n\t0xf065732a844a7c06ULL, 0x10af957f8cde840aULL, 0x3512c64e4c098d67ULL,\n\n\t0x5bd5331c0d7096d0ULL, 0x7e68602dcda79fbdULL, 0x865ad9b88f82a1beULL,\n\n\t0xa3e78a894f55a8d3ULL, 0xcd207fdb0e2cb364ULL, 0xe89d2ceacefbba09ULL,\n\n\t0x18f85fc04ab1c60fULL, 0x3d450cf18a66cf62ULL, 0x5382f9a3cb1fd4d5ULL,\n\n\t0x763faa920bc8ddb8ULL, 0x8e0d130749ede3bbULL, 0xabb04036893aead6ULL,\n\n\t0xc577b564c843f161ULL, 0xe0cae6550894f80cULL, 0x04e279ced96a0179ULL,\n\n\t0x215f2aff19bd0814ULL, 0x4f98dfad58c413a3ULL, 0x6a258c9c98131aceULL,\n\n\t0x92173509da3624cdULL, 0xb7aa66381ae12da0ULL, 0xd96d936a5b983617ULL,\n\n\t0xfcd0c05b9b4f3f7aULL, 0x0cb5b3711f05437cULL, 0x2908e040dfd24a11ULL,\n\n\t0x47cf15129eab51a6ULL, 0x627246235e7c58cbULL, 0x9a40ffb61c5966c8ULL,\n\n\t0xbffdac87dc8e6fa5ULL, 0xd13a59d59df77412ULL, 0xf4870ae45d207d7fULL,\n\n\t0x144decb155b48573ULL, 0x31f0bf8095638c1eULL, 0x5f374ad2d41a97a9ULL,\n\n\t0x7a8a19e314cd9ec4ULL, 0x82b8a07656e8a0c7ULL, 0xa705f347963fa9aaULL,\n\n\t0xc9c20615d746b21dULL, 0xec7f55241791bb70ULL, 0x1c1a260e93dbc776ULL,\n\n\t0x39a7753f530cce1bULL, 0x5760806d1275d5acULL, 0x72ddd35cd2a2dcc1ULL,\n\n\t0x8aef6ac99087e2c2ULL, 0xaf5239f85050ebafULL, 0xc195ccaa1129f018ULL,\n\n\t0xe4289f9bd1fef975ULL, 0x09c4f39db2d402f2ULL, 0x2c79a0ac72030b9fULL,\n\n\t0x42be55fe337a1028ULL, 0x670306cff3ad1945ULL, 0x9f31bf5ab1882746ULL,\n\n\t0xba8cec6b715f2e2bULL, 0xd44b19393026359cULL, 0xf1f64a08f0f13cf1ULL,\n\n\t0x0193392274bb40f7ULL, 0x242e6a13b46c499aULL, 0x4ae99f41f515522dULL,\n\n\t0x6f54cc7035c25b40ULL, 0x976675e577e76543ULL, 0xb2db26d4b7306c2eULL,\n\n\t0xdc1cd386f6497799ULL, 0xf9a180b7369e7ef4ULL, 0x196b66e23e0a86f8ULL,\n\n\t0x3cd635d3fedd8f95ULL, 0x5211c081bfa49422ULL, 0x77ac93b07f739d4fULL,\n\n\t0x8f9e2a253d56a34cULL, 0xaa237914fd81aa21ULL, 0xc4e48c46bcf8b196ULL,\n\n\t0xe159df777c2fb8fbULL, 0x113cac5df865c4fdULL, 0x3481ff6c38b2cd90ULL,\n\n\t0x5a460a3e79cbd627ULL, 0x7ffb590fb91cdf4aULL, 0x87c9e09afb39e149ULL,\n\n\t0xa274b3ab3beee824ULL, 0xccb346f97a97f393ULL, 0xe90e15c8ba40fafeULL,\n\n\t0x0d268a536bbe038bULL, 0x289bd962ab690ae6ULL, 0x465c2c30ea101151ULL,\n\n\t0x63e17f012ac7183cULL, 0x9bd3c69468e2263fULL, 0xbe6e95a5a8352f52ULL,\n\n\t0xd0a960f7e94c34e5ULL, 0xf51433c6299b3d88ULL, 0x057140ecadd1418eULL,\n\n\t0x20cc13dd6d0648e3ULL, 0x4e0be68f2c7f5354ULL, 0x6bb6b5beeca85a39ULL,\n\n\t0x93840c2bae8d643aULL, 0xb6395f1a6e5a6d57ULL, 0xd8feaa482f2376e0ULL,\n\n\t0xfd43f979eff47f8dULL, 0x1d891f2ce7608781ULL, 0x38344c1d27b78eecULL,\n\n\t0x56f3b94f66ce955bULL, 0x734eea7ea6199c36ULL, 0x8b7c53ebe43ca235ULL,\n\n\t0xaec100da24ebab58ULL, 0xc006f5886592b0efULL, 0xe5bba6b9a545b982ULL,\n\n\t0x15ded593210fc584ULL, 0x306386a2e1d8cce9ULL, 0x5ea473f0a0a1d75eULL,\n\n\t0x7b1920c16076de33ULL, 0x832b99542253e030ULL, 0xa696ca65e284e95dULL,\n\n\t0xc8513f37a3fdf2eaULL, 0xedec6c06632afb87ULL, 0x1389e73b65a805e4ULL,\n\n\t0x3634b40aa57f0c89ULL, 0x58f34158e406173eULL, 0x7d4e126924d11e53ULL,\n\n\t0x857cabfc66f42050ULL, 0xa0c1f8cda623293dULL, 0xce060d9fe75a328aULL,\n\n\t0xebbb5eae278d3be7ULL, 0x1bde2d84a3c747e1ULL, 0x3e637eb563104e8cULL,\n\n\t0x50a48be72269553bULL, 0x7519d8d6e2be5c56ULL, 0x8d2b6143a09b6255ULL,\n\n\t0xa8963272604c6b38ULL, 0xc651c7202135708fULL, 0xe3ec9411e1e279e2ULL,\n\n\t0x03267244e97681eeULL, 0x269b217529a18883ULL, 0x485cd42768d89334ULL,\n\n\t0x6de18716a80f9a59ULL, 0x95d33e83ea2aa45aULL, 0xb06e6db22afdad37ULL,\n\n\t0xdea998e06b84b680ULL, 0xfb14cbd1ab53bfedULL, 0x0b71b8fb2f19c3ebULL,\n\n\t0x2eccebcaefceca86ULL, 0x400b1e98aeb7d131ULL, 0x65b64da96e60d85cULL,\n\n\t0x9d84f43c2c45e65fULL, 0xb839a70dec92ef32ULL, 0xd6fe525fadebf485ULL,\n\n\t0xf343016e6d3cfde8ULL, 0x176b9ef5bcc2049dULL, 0x32d6cdc47c150df0ULL,\n\n\t0x5c1138963d6c1647ULL, 0x79ac6ba7fdbb1f2aULL, 0x819ed232bf9e2129ULL,\n\n\t0xa42381037f492844ULL, 0xcae474513e3033f3ULL, 0xef592760fee73a9eULL,\n\n\t0x1f3c544a7aad4698ULL, 0x3a81077bba7a4ff5ULL, 0x5446f229fb035442ULL,\n\n\t0x71fba1183bd45d2fULL, 0x89c9188d79f1632cULL, 0xac744bbcb9266a41ULL,\n\n\t0xc2b3beeef85f71f6ULL, 0xe70eeddf3888789bULL, 0x07c40b8a301c8097ULL,\n\n\t0x227958bbf0cb89faULL, 0x4cbeade9b1b2924dULL, 0x6903fed871659b20ULL,\n\n\t0x9131474d3340a523ULL, 0xb48c147cf397ac4eULL, 0xda4be12eb2eeb7f9ULL,\n\n\t0xfff6b21f7239be94ULL, 0x0f93c135f673c292ULL, 0x2a2e920436a4cbffULL,\n\n\t0x44e9675677ddd048ULL, 0x61543467b70ad925ULL, 0x99668df2f52fe726ULL,\n\n\t0xbcdbdec335f8ee4bULL, 0xd21c2b917481f5fcULL, 0xf7a178a0b456fc91ULL,\n\n\t0x1a4d14a6d77c0716ULL, 0x3ff0479717ab0e7bULL, 0x5137b2c556d215ccULL,\n\n\t0x748ae1f496051ca1ULL, 0x8cb85861d42022a2ULL, 0xa9050b5014f72bcfULL,\n\n\t0xc7c2fe02558e3078ULL, 0xe27fad3395593915ULL, 0x121ade1911134513ULL,\n\n\t0x37a78d28d1c44c7eULL, 0x5960787a90bd57c9ULL, 0x7cdd2b4b506a5ea4ULL,\n\n\t0x84ef92de124f60a7ULL, 0xa152c1efd29869caULL, 0xcf9534bd93e1727dULL,\n\n\t0xea28678c53367b10ULL, 0x0ae281d95ba2831cULL, 0x2f5fd2e89b758a71ULL,\n\n\t0x419827bada0c91c6ULL, 0x6425748b1adb98abULL, 0x9c17cd1e58fea6a8ULL,\n\n\t0xb9aa9e2f9829afc5ULL, 0xd76d6b7dd950b472ULL, 0xf2d0384c1987bd1fULL,\n\n\t0x02b54b669dcdc119ULL, 0x270818575d1ac874ULL, 0x49cfed051c63d3c3ULL,\n\n\t0x6c72be34dcb4daaeULL, 0x944007a19e91e4adULL, 0xb1fd54905e46edc0ULL,\n\n\t0xdf3aa1c21f3ff677ULL, 0xfa87f2f3dfe8ff1aULL, 0x1eaf6d680e16066fULL,\n\n\t0x3b123e59cec10f02ULL, 0x55d5cb0b8fb814b5ULL, 0x7068983a4f6f1dd8ULL,\n\n\t0x885a21af0d4a23dbULL, 0xade7729ecd9d2ab6ULL, 0xc32087cc8ce43101ULL,\n\n\t0xe69dd4fd4c33386cULL, 0x16f8a7d7c879446aULL, 0x3345f4e608ae4d07ULL,\n\n\t0x5d8201b449d756b0ULL, 0x783f528589005fddULL, 0x800deb10cb2561deULL,\n\n\t0xa5b0b8210bf268b3ULL, 0xcb774d734a8b7304ULL, 0xeeca1e428a5c7a69ULL,\n\n\t0x0e00f81782c88265ULL, 0x2bbdab26421f8b08ULL, 0x457a5e74036690bfULL,\n\n\t0x60c70d45c3b199d2ULL, 0x98f5b4d08194a7d1ULL, 0xbd48e7e14143aebcULL,\n\n\t0xd38f12b3003ab50bULL, 0xf6324182c0edbc66ULL, 0x065732a844a7c060ULL,\n\n\t0x23ea61998470c90dULL, 0x4d2d94cbc509d2baULL, 0x6890c7fa05dedbd7ULL,\n\n\t0x90a27e6f47fbe5d4ULL, 0xb51f2d5e872cecb9ULL, 0xdbd8d80cc655f70eULL,\n\n\t0xfe658b3d0682fe63ULL\n\n};\n\n\n\nstatic const u_int64_t U[256] = {\n\n\t0x0000000000000000ULL, 0x067b86c43d6a6cb0ULL, 0x0cf70d887ad4d960ULL,\n\n\t0x0a8c8b4c47beb5d0ULL, 0x19ee1b10f5a9b2c0ULL, 0x1f959dd4c8c3de70ULL,\n\n\t0x151916988f7d6ba0ULL, 0x1362905cb2170710ULL, 0x166165102b846cedULL,\n\n\t0x101ae3d416ee005dULL, 0x1a9668985150b58dULL, 0x1cedee5c6c3ad93dULL,\n\n\t0x0f8f7e00de2dde2dULL, 0x09f4f8c4e347b29dULL, 0x03787388a4f9074dULL,\n\n\t0x0503f54c99936bfdULL, 0x097f991197dfd0b7ULL, 0x0f041fd5aab5bc07ULL,\n\n\t0x05889499ed0b09d7ULL, 0x03f3125dd0616567ULL, 0x1091820162766277ULL,\n\n\t0x16ea04c55f1c0ec7ULL, 0x1c668f8918a2bb17ULL, 0x1a1d094d25c8d7a7ULL,\n\n\t0x1f1efc01bc5bbc5aULL, 0x19657ac58131d0eaULL, 0x13e9f189c68f653aULL,\n\n\t0x1592774dfbe5098aULL, 0x06f0e71149f20e9aULL, 0x008b61d57498622aULL,\n\n\t0x0a07ea993326d7faULL, 0x0c7c6c5d0e4cbb4aULL, 0x12ff32232fbfa16eULL,\n\n\t0x1484b4e712d5cddeULL, 0x1e083fab556b780eULL, 0x1873b96f680114beULL,\n\n\t0x0b112933da1613aeULL, 0x0d6aaff7e77c7f1eULL, 0x07e624bba0c2caceULL,\n\n\t0x019da27f9da8a67eULL, 0x049e5733043bcd83ULL, 0x02e5d1f73951a133ULL,\n\n\t0x08695abb7eef14e3ULL, 0x0e12dc7f43857853ULL, 0x1d704c23f1927f43ULL,\n\n\t0x1b0bcae7ccf813f3ULL, 0x118741ab8b46a623ULL, 0x17fcc76fb62cca93ULL,\n\n\t0x1b80ab32b86071d9ULL, 0x1dfb2df6850a1d69ULL, 0x1777a6bac2b4a8b9ULL,\n\n\t0x110c207effdec409ULL, 0x026eb0224dc9c319ULL, 0x041536e670a3afa9ULL,\n\n\t0x0e99bdaa371d1a79ULL, 0x08e23b6e0a7776c9ULL, 0x0de1ce2293e41d34ULL,\n\n\t0x0b9a48e6ae8e7184ULL, 0x0116c3aae930c454ULL, 0x076d456ed45aa8e4ULL,\n\n\t0x140fd532664daff4ULL, 0x127453f65b27c344ULL, 0x18f8d8ba1c997694ULL,\n\n\t0x1e835e7e21f31a24ULL, 0x004337779fa84bb1ULL, 0x0638b1b3a2c22701ULL,\n\n\t0x0cb43affe57c92d1ULL, 0x0acfbc3bd816fe61ULL, 0x19ad2c676a01f971ULL,\n\n\t0x1fd6aaa3576b95c1ULL, 0x155a21ef10d52011ULL, 0x1321a72b2dbf4ca1ULL,\n\n\t0x16225267b42c275cULL, 0x1059d4a389464becULL, 0x1ad55fefcef8fe3cULL,\n\n\t0x1caed92bf392928cULL, 0x0fcc49774185959cULL, 0x09b7cfb37ceff92cULL,\n\n\t0x033b44ff3b514cfcULL, 0x0540c23b063b204cULL, 0x093cae6608779b06ULL,\n\n\t0x0f4728a2351df7b6ULL, 0x05cba3ee72a34266ULL, 0x03b0252a4fc92ed6ULL,\n\n\t0x10d2b576fdde29c6ULL, 0x16a933b2c0b44576ULL, 0x1c25b8fe870af0a6ULL,\n\n\t0x1a5e3e3aba609c16ULL, 0x1f5dcb7623f3f7ebULL, 0x19264db21e999b5bULL,\n\n\t0x13aac6fe59272e8bULL, 0x15d1403a644d423bULL, 0x06b3d066d65a452bULL,\n\n\t0x00c856a2eb30299bULL, 0x0a44ddeeac8e9c4bULL, 0x0c3f5b2a91e4f0fbULL,\n\n\t0x12bc0554b017eadfULL, 0x14c783908d7d866fULL, 0x1e4b08dccac333bfULL,\n\n\t0x18308e18f7a95f0fULL, 0x0b521e4445be581fULL, 0x0d29988078d434afULL,\n\n\t0x07a513cc3f6a817fULL, 0x01de95080200edcfULL, 0x04dd60449b938632ULL,\n\n\t0x02a6e680a6f9ea82ULL, 0x082a6dcce1475f52ULL, 0x0e51eb08dc2d33e2ULL,\n\n\t0x1d337b546e3a34f2ULL, 0x1b48fd9053505842ULL, 0x11c476dc14eeed92ULL,\n\n\t0x17bff01829848122ULL, 0x1bc39c4527c83a68ULL, 0x1db81a811aa256d8ULL,\n\n\t0x173491cd5d1ce308ULL, 0x114f170960768fb8ULL, 0x022d8755d26188a8ULL,\n\n\t0x04560191ef0be418ULL, 0x0eda8adda8b551c8ULL, 0x08a10c1995df3d78ULL,\n\n\t0x0da2f9550c4c5685ULL, 0x0bd97f9131263a35ULL, 0x0155f4dd76988fe5ULL,\n\n\t0x072e72194bf2e355ULL, 0x144ce245f9e5e445ULL, 0x12376481c48f88f5ULL,\n\n\t0x18bbefcd83313d25ULL, 0x1ec06909be5b5195ULL, 0x00866eef3f509762ULL,\n\n\t0x06fde82b023afbd2ULL, 0x0c71636745844e02ULL, 0x0a0ae5a378ee22b2ULL,\n\n\t0x196875ffcaf925a2ULL, 0x1f13f33bf7934912ULL, 0x159f7877b02dfcc2ULL,\n\n\t0x13e4feb38d479072ULL, 0x16e70bff14d4fb8fULL, 0x109c8d3b29be973fULL,\n\n\t0x1a1006776e0022efULL, 0x1c6b80b3536a4e5fULL, 0x0f0910efe17d494fULL,\n\n\t0x0972962bdc1725ffULL, 0x03fe1d679ba9902fULL, 0x05859ba3a6c3fc9fULL,\n\n\t0x09f9f7fea88f47d5ULL, 0x0f82713a95e52b65ULL, 0x050efa76d25b9eb5ULL,\n\n\t0x03757cb2ef31f205ULL, 0x1017ecee5d26f515ULL, 0x166c6a2a604c99a5ULL,\n\n\t0x1ce0e16627f22c75ULL, 0x1a9b67a21a9840c5ULL, 0x1f9892ee830b2b38ULL,\n\n\t0x19e3142abe614788ULL, 0x136f9f66f9dff258ULL, 0x151419a2c4b59ee8ULL,\n\n\t0x067689fe76a299f8ULL, 0x000d0f3a4bc8f548ULL, 0x0a8184760c764098ULL,\n\n\t0x0cfa02b2311c2c28ULL, 0x12795ccc10ef360cULL, 0x1402da082d855abcULL,\n\n\t0x1e8e51446a3bef6cULL, 0x18f5d780575183dcULL, 0x0b9747dce54684ccULL,\n\n\t0x0decc118d82ce87cULL, 0x07604a549f925dacULL, 0x011bcc90a2f8311cULL,\n\n\t0x041839dc3b6b5ae1ULL, 0x0263bf1806013651ULL, 0x08ef345441bf8381ULL,\n\n\t0x0e94b2907cd5ef31ULL, 0x1df622cccec2e821ULL, 0x1b8da408f3a88491ULL,\n\n\t0x11012f44b4163141ULL, 0x177aa980897c5df1ULL, 0x1b06c5dd8730e6bbULL,\n\n\t0x1d7d4319ba5a8a0bULL, 0x17f1c855fde43fdbULL, 0x118a4e91c08e536bULL,\n\n\t0x02e8decd7299547bULL, 0x049358094ff338cbULL, 0x0e1fd345084d8d1bULL,\n\n\t0x086455813527e1abULL, 0x0d67a0cdacb48a56ULL, 0x0b1c260991dee6e6ULL,\n\n\t0x0190ad45d6605336ULL, 0x07eb2b81eb0a3f86ULL, 0x1489bbdd591d3896ULL,\n\n\t0x12f23d1964775426ULL, 0x187eb65523c9e1f6ULL, 0x1e0530911ea38d46ULL,\n\n\t0x00c55998a0f8dcd3ULL, 0x06bedf5c9d92b063ULL, 0x0c325410da2c05b3ULL,\n\n\t0x0a49d2d4e7466903ULL, 0x192b428855516e13ULL, 0x1f50c44c683b02a3ULL,\n\n\t0x15dc4f002f85b773ULL, 0x13a7c9c412efdbc3ULL, 0x16a43c888b7cb03eULL,\n\n\t0x10dfba4cb616dc8eULL, 0x1a533100f1a8695eULL, 0x1c28b7c4ccc205eeULL,\n\n\t0x0f4a27987ed502feULL, 0x0931a15c43bf6e4eULL, 0x03bd2a100401db9eULL,\n\n\t0x05c6acd4396bb72eULL, 0x09bac08937270c64ULL, 0x0fc1464d0a4d60d4ULL,\n\n\t0x054dcd014df3d504ULL, 0x03364bc57099b9b4ULL, 0x1054db99c28ebea4ULL,\n\n\t0x162f5d5dffe4d214ULL, 0x1ca3d611b85a67c4ULL, 0x1ad850d585300b74ULL,\n\n\t0x1fdba5991ca36089ULL, 0x19a0235d21c90c39ULL, 0x132ca8116677b9e9ULL,\n\n\t0x15572ed55b1dd559ULL, 0x0635be89e90ad249ULL, 0x004e384dd460bef9ULL,\n\n\t0x0ac2b30193de0b29ULL, 0x0cb935c5aeb46799ULL, 0x123a6bbb8f477dbdULL,\n\n\t0x1441ed7fb22d110dULL, 0x1ecd6633f593a4ddULL, 0x18b6e0f7c8f9c86dULL,\n\n\t0x0bd470ab7aeecf7dULL, 0x0daff66f4784a3cdULL, 0x07237d23003a161dULL,\n\n\t0x0158fbe73d507aadULL, 0x045b0eaba4c31150ULL, 0x0220886f99a97de0ULL,\n\n\t0x08ac0323de17c830ULL, 0x0ed785e7e37da480ULL, 0x1db515bb516aa390ULL,\n\n\t0x1bce937f6c00cf20ULL, 0x114218332bbe7af0ULL, 0x17399ef716d41640ULL,\n\n\t0x1b45f2aa1898ad0aULL, 0x1d3e746e25f2c1baULL, 0x17b2ff22624c746aULL,\n\n\t0x11c979e65f2618daULL, 0x02abe9baed311fcaULL, 0x04d06f7ed05b737aULL,\n\n\t0x0e5ce43297e5c6aaULL, 0x082762f6aa8faa1aULL, 0x0d2497ba331cc1e7ULL,\n\n\t0x0b5f117e0e76ad57ULL, 0x01d39a3249c81887ULL, 0x07a81cf674a27437ULL,\n\n\t0x14ca8caac6b57327ULL, 0x12b10a6efbdf1f97ULL, 0x183d8122bc61aa47ULL,\n\n\t0x1e4607e6810bc6f7ULL\n\n};\n\n\n\n#else\t/* the original ones */\n\n\n\n#define RABIN_WINDOW_SIZE 22\n\n#define RABIN_SHIFT 55\n\n\n\nstatic const u_int64_t T[256] = {\n\n\t0x0000000000000000ULL, 0xb15e234bd3792f63ULL, 0x62bc4697a6f25ec6ULL,\n\n\t0xd3e265dc758b71a5ULL, 0x7426ae649e9d92efULL, 0xc5788d2f4de4bd8cULL,\n\n\t0x169ae8f3386fcc29ULL, 0xa7c4cbb8eb16e34aULL, 0x59137f82ee420abdULL,\n\n\t0xe84d5cc93d3b25deULL, 0x3baf391548b0547bULL, 0x8af11a5e9bc97b18ULL,\n\n\t0x2d35d1e670df9852ULL, 0x9c6bf2ada3a6b731ULL, 0x4f899771d62dc694ULL,\n\n\t0xfed7b43a0554e9f7ULL, 0x0378dc4e0ffd3a19ULL, 0xb226ff05dc84157aULL,\n\n\t0x61c49ad9a90f64dfULL, 0xd09ab9927a764bbcULL, 0x775e722a9160a8f6ULL,\n\n\t0xc600516142198795ULL, 0x15e234bd3792f630ULL, 0xa4bc17f6e4ebd953ULL,\n\n\t0x5a6ba3cce1bf30a4ULL, 0xeb35808732c61fc7ULL, 0x38d7e55b474d6e62ULL,\n\n\t0x8989c61094344101ULL, 0x2e4d0da87f22a24bULL, 0x9f132ee3ac5b8d28ULL,\n\n\t0x4cf14b3fd9d0fc8dULL, 0xfdaf68740aa9d3eeULL, 0x06f1b89c1ffa7432ULL,\n\n\t0xb7af9bd7cc835b51ULL, 0x644dfe0bb9082af4ULL, 0xd513dd406a710597ULL,\n\n\t0x72d716f88167e6ddULL, 0xc38935b3521ec9beULL, 0x106b506f2795b81bULL,\n\n\t0xa1357324f4ec9778ULL, 0x5fe2c71ef1b87e8fULL, 0xeebce45522c151ecULL,\n\n\t0x3d5e8189574a2049ULL, 0x8c00a2c284330f2aULL, 0x2bc4697a6f25ec60ULL,\n\n\t0x9a9a4a31bc5cc303ULL, 0x49782fedc9d7b2a6ULL, 0xf8260ca61aae9dc5ULL,\n\n\t0x058964d210074e2bULL, 0xb4d74799c37e6148ULL, 0x67352245b6f510edULL,\n\n\t0xd66b010e658c3f8eULL, 0x71afcab68e9adcc4ULL, 0xc0f1e9fd5de3f3a7ULL,\n\n\t0x13138c2128688202ULL, 0xa24daf6afb11ad61ULL, 0x5c9a1b50fe454496ULL,\n\n\t0xedc4381b2d3c6bf5ULL, 0x3e265dc758b71a50ULL, 0x8f787e8c8bce3533ULL,\n\n\t0x28bcb53460d8d679ULL, 0x99e2967fb3a1f91aULL, 0x4a00f3a3c62a88bfULL,\n\n\t0xfb5ed0e81553a7dcULL, 0x0de371383ff4e864ULL, 0xbcbd5273ec8dc707ULL,\n\n\t0x6f5f37af9906b6a2ULL, 0xde0114e44a7f99c1ULL, 0x79c5df5ca1697a8bULL,\n\n\t0xc89bfc17721055e8ULL, 0x1b7999cb079b244dULL, 0xaa27ba80d4e20b2eULL,\n\n\t0x54f00ebad1b6e2d9ULL, 0xe5ae2df102cfcdbaULL, 0x364c482d7744bc1fULL,\n\n\t0x87126b66a43d937cULL, 0x20d6a0de4f2b7036ULL, 0x918883959c525f55ULL,\n\n\t0x426ae649e9d92ef0ULL, 0xf334c5023aa00193ULL, 0x0e9bad763009d27dULL,\n\n\t0xbfc58e3de370fd1eULL, 0x6c27ebe196fb8cbbULL, 0xdd79c8aa4582a3d8ULL,\n\n\t0x7abd0312ae944092ULL, 0xcbe320597ded6ff1ULL, 0x1801458508661e54ULL,\n\n\t0xa95f66cedb1f3137ULL, 0x5788d2f4de4bd8c0ULL, 0xe6d6f1bf0d32f7a3ULL,\n\n\t0x3534946378b98606ULL, 0x846ab728abc0a965ULL, 0x23ae7c9040d64a2fULL,\n\n\t0x92f05fdb93af654cULL, 0x41123a07e62414e9ULL, 0xf04c194c355d3b8aULL,\n\n\t0x0b12c9a4200e9c56ULL, 0xba4ceaeff377b335ULL, 0x69ae8f3386fcc290ULL,\n\n\t0xd8f0ac785585edf3ULL, 0x7f3467c0be930eb9ULL, 0xce6a448b6dea21daULL,\n\n\t0x1d8821571861507fULL, 0xacd6021ccb187f1cULL, 0x5201b626ce4c96ebULL,\n\n\t0xe35f956d1d35b988ULL, 0x30bdf0b168bec82dULL, 0x81e3d3fabbc7e74eULL,\n\n\t0x2627184250d10404ULL, 0x97793b0983a82b67ULL, 0x449b5ed5f6235ac2ULL,\n\n\t0xf5c57d9e255a75a1ULL, 0x086a15ea2ff3a64fULL, 0xb93436a1fc8a892cULL,\n\n\t0x6ad6537d8901f889ULL, 0xdb8870365a78d7eaULL, 0x7c4cbb8eb16e34a0ULL,\n\n\t0xcd1298c562171bc3ULL, 0x1ef0fd19179c6a66ULL, 0xafaede52c4e54505ULL,\n\n\t0x51796a68c1b1acf2ULL, 0xe027492312c88391ULL, 0x33c52cff6743f234ULL,\n\n\t0x829b0fb4b43add57ULL, 0x255fc40c5f2c3e1dULL, 0x9401e7478c55117eULL,\n\n\t0x47e3829bf9de60dbULL, 0xf6bda1d02aa74fb8ULL, 0x1bc6e2707fe9d0c8ULL,\n\n\t0xaa98c13bac90ffabULL, 0x797aa4e7d91b8e0eULL, 0xc82487ac0a62a16dULL,\n\n\t0x6fe04c14e1744227ULL, 0xdebe6f5f320d6d44ULL, 0x0d5c0a8347861ce1ULL,\n\n\t0xbc0229c894ff3382ULL, 0x42d59df291abda75ULL, 0xf38bbeb942d2f516ULL,\n\n\t0x2069db65375984b3ULL, 0x9137f82ee420abd0ULL, 0x36f333960f36489aULL,\n\n\t0x87ad10dddc4f67f9ULL, 0x544f7501a9c4165cULL, 0xe511564a7abd393fULL,\n\n\t0x18be3e3e7014ead1ULL, 0xa9e01d75a36dc5b2ULL, 0x7a0278a9d6e6b417ULL,\n\n\t0xcb5c5be2059f9b74ULL, 0x6c98905aee89783eULL, 0xddc6b3113df0575dULL,\n\n\t0x0e24d6cd487b26f8ULL, 0xbf7af5869b02099bULL, 0x41ad41bc9e56e06cULL,\n\n\t0xf0f362f74d2fcf0fULL, 0x2311072b38a4beaaULL, 0x924f2460ebdd91c9ULL,\n\n\t0x358befd800cb7283ULL, 0x84d5cc93d3b25de0ULL, 0x5737a94fa6392c45ULL,\n\n\t0xe6698a0475400326ULL, 0x1d375aec6013a4faULL, 0xac6979a7b36a8b99ULL,\n\n\t0x7f8b1c7bc6e1fa3cULL, 0xced53f301598d55fULL, 0x6911f488fe8e3615ULL,\n\n\t0xd84fd7c32df71976ULL, 0x0badb21f587c68d3ULL, 0xbaf391548b0547b0ULL,\n\n\t0x4424256e8e51ae47ULL, 0xf57a06255d288124ULL, 0x269863f928a3f081ULL,\n\n\t0x97c640b2fbdadfe2ULL, 0x30028b0a10cc3ca8ULL, 0x815ca841c3b513cbULL,\n\n\t0x52becd9db63e626eULL, 0xe3e0eed665474d0dULL, 0x1e4f86a26fee9ee3ULL,\n\n\t0xaf11a5e9bc97b180ULL, 0x7cf3c035c91cc025ULL, 0xcdade37e1a65ef46ULL,\n\n\t0x6a6928c6f1730c0cULL, 0xdb370b8d220a236fULL, 0x08d56e51578152caULL,\n\n\t0xb98b4d1a84f87da9ULL, 0x475cf92081ac945eULL, 0xf602da6b52d5bb3dULL,\n\n\t0x25e0bfb7275eca98ULL, 0x94be9cfcf427e5fbULL, 0x337a57441f3106b1ULL,\n\n\t0x8224740fcc4829d2ULL, 0x51c611d3b9c35877ULL, 0xe09832986aba7714ULL,\n\n\t0x16259348401d38acULL, 0xa77bb003936417cfULL, 0x7499d5dfe6ef666aULL,\n\n\t0xc5c7f69435964909ULL, 0x62033d2cde80aa43ULL, 0xd35d1e670df98520ULL,\n\n\t0x00bf7bbb7872f485ULL, 0xb1e158f0ab0bdbe6ULL, 0x4f36eccaae5f3211ULL,\n\n\t0xfe68cf817d261d72ULL, 0x2d8aaa5d08ad6cd7ULL, 0x9cd48916dbd443b4ULL,\n\n\t0x3b1042ae30c2a0feULL, 0x8a4e61e5e3bb8f9dULL, 0x59ac04399630fe38ULL,\n\n\t0xe8f227724549d15bULL, 0x155d4f064fe002b5ULL, 0xa4036c4d9c992dd6ULL,\n\n\t0x77e10991e9125c73ULL, 0xc6bf2ada3a6b7310ULL, 0x617be162d17d905aULL,\n\n\t0xd025c2290204bf39ULL, 0x03c7a7f5778fce9cULL, 0xb29984bea4f6e1ffULL,\n\n\t0x4c4e3084a1a20808ULL, 0xfd1013cf72db276bULL, 0x2ef27613075056ceULL,\n\n\t0x9fac5558d42979adULL, 0x38689ee03f3f9ae7ULL, 0x8936bdabec46b584ULL,\n\n\t0x5ad4d87799cdc421ULL, 0xeb8afb3c4ab4eb42ULL, 0x10d42bd45fe74c9eULL,\n\n\t0xa18a089f8c9e63fdULL, 0x72686d43f9151258ULL, 0xc3364e082a6c3d3bULL,\n\n\t0x64f285b0c17ade71ULL, 0xd5aca6fb1203f112ULL, 0x064ec327678880b7ULL,\n\n\t0xb710e06cb4f1afd4ULL, 0x49c75456b1a54623ULL, 0xf899771d62dc6940ULL,\n\n\t0x2b7b12c1175718e5ULL, 0x9a25318ac42e3786ULL, 0x3de1fa322f38d4ccULL,\n\n\t0x8cbfd979fc41fbafULL, 0x5f5dbca589ca8a0aULL, 0xee039fee5ab3a569ULL,\n\n\t0x13acf79a501a7687ULL, 0xa2f2d4d1836359e4ULL, 0x7110b10df6e82841ULL,\n\n\t0xc04e924625910722ULL, 0x678a59fece87e468ULL, 0xd6d47ab51dfecb0bULL,\n\n\t0x05361f696875baaeULL, 0xb4683c22bb0c95cdULL, 0x4abf8818be587c3aULL,\n\n\t0xfbe1ab536d215359ULL, 0x2803ce8f18aa22fcULL, 0x995dedc4cbd30d9fULL,\n\n\t0x3e99267c20c5eed5ULL, 0x8fc70537f3bcc1b6ULL, 0x5c2560eb8637b013ULL,\n\n\t0xed7b43a0554e9f70ULL\n\n};\n\n\n\nstatic const u_int64_t U[256] = {\n\n\t0x0000000000000000ULL, 0x079343d61ab9f60eULL, 0x0f2687ac3573ec1cULL,\n\n\t0x08b5c47a2fca1a12ULL, 0x1e4d0f586ae7d838ULL, 0x19de4c8e705e2e36ULL,\n\n\t0x116b88f45f943424ULL, 0x16f8cb22452dc22aULL, 0x3c9a1eb0d5cfb070ULL,\n\n\t0x3b095d66cf76467eULL, 0x33bc991ce0bc5c6cULL, 0x342fdacafa05aa62ULL,\n\n\t0x22d711e8bf286848ULL, 0x2544523ea5919e46ULL, 0x2df196448a5b8454ULL,\n\n\t0x2a62d59290e2725aULL, 0x79343d61ab9f60e0ULL, 0x7ea77eb7b12696eeULL,\n\n\t0x7612bacd9eec8cfcULL, 0x7181f91b84557af2ULL, 0x67793239c178b8d8ULL,\n\n\t0x60ea71efdbc14ed6ULL, 0x685fb595f40b54c4ULL, 0x6fccf643eeb2a2caULL,\n\n\t0x45ae23d17e50d090ULL, 0x423d600764e9269eULL, 0x4a88a47d4b233c8cULL,\n\n\t0x4d1be7ab519aca82ULL, 0x5be32c8914b708a8ULL, 0x5c706f5f0e0efea6ULL,\n\n\t0x54c5ab2521c4e4b4ULL, 0x5356e8f33b7d12baULL, 0x433659888447eea3ULL,\n\n\t0x44a51a5e9efe18adULL, 0x4c10de24b13402bfULL, 0x4b839df2ab8df4b1ULL,\n\n\t0x5d7b56d0eea0369bULL, 0x5ae81506f419c095ULL, 0x525dd17cdbd3da87ULL,\n\n\t0x55ce92aac16a2c89ULL, 0x7fac473851885ed3ULL, 0x783f04ee4b31a8ddULL,\n\n\t0x708ac09464fbb2cfULL, 0x771983427e4244c1ULL, 0x61e148603b6f86ebULL,\n\n\t0x66720bb621d670e5ULL, 0x6ec7cfcc0e1c6af7ULL, 0x69548c1a14a59cf9ULL,\n\n\t0x3a0264e92fd88e43ULL, 0x3d91273f3561784dULL, 0x3524e3451aab625fULL,\n\n\t0x32b7a09300129451ULL, 0x244f6bb1453f567bULL, 0x23dc28675f86a075ULL,\n\n\t0x2b69ec1d704cba67ULL, 0x2cfaafcb6af54c69ULL, 0x06987a59fa173e33ULL,\n\n\t0x010b398fe0aec83dULL, 0x09befdf5cf64d22fULL, 0x0e2dbe23d5dd2421ULL,\n\n\t0x18d5750190f0e60bULL, 0x1f4636d78a491005ULL, 0x17f3f2ada5830a17ULL,\n\n\t0x1060b17bbf3afc19ULL, 0x3732905adbf6f225ULL, 0x30a1d38cc14f042bULL,\n\n\t0x381417f6ee851e39ULL, 0x3f875420f43ce837ULL, 0x297f9f02b1112a1dULL,\n\n\t0x2eecdcd4aba8dc13ULL, 0x265918ae8462c601ULL, 0x21ca5b789edb300fULL,\n\n\t0x0ba88eea0e394255ULL, 0x0c3bcd3c1480b45bULL, 0x048e09463b4aae49ULL,\n\n\t0x031d4a9021f35847ULL, 0x15e581b264de9a6dULL, 0x1276c2647e676c63ULL,\n\n\t0x1ac3061e51ad7671ULL, 0x1d5045c84b14807fULL, 0x4e06ad3b706992c5ULL,\n\n\t0x4995eeed6ad064cbULL, 0x41202a97451a7ed9ULL, 0x46b369415fa388d7ULL,\n\n\t0x504ba2631a8e4afdULL, 0x57d8e1b50037bcf3ULL, 0x5f6d25cf2ffda6e1ULL,\n\n\t0x58fe6619354450efULL, 0x729cb38ba5a622b5ULL, 0x750ff05dbf1fd4bbULL,\n\n\t0x7dba342790d5cea9ULL, 0x7a2977f18a6c38a7ULL, 0x6cd1bcd3cf41fa8dULL,\n\n\t0x6b42ff05d5f80c83ULL, 0x63f73b7ffa321691ULL, 0x646478a9e08be09fULL,\n\n\t0x7404c9d25fb11c86ULL, 0x73978a044508ea88ULL, 0x7b224e7e6ac2f09aULL,\n\n\t0x7cb10da8707b0694ULL, 0x6a49c68a3556c4beULL, 0x6dda855c2fef32b0ULL,\n\n\t0x656f4126002528a2ULL, 0x62fc02f01a9cdeacULL, 0x489ed7628a7eacf6ULL,\n\n\t0x4f0d94b490c75af8ULL, 0x47b850cebf0d40eaULL, 0x402b1318a5b4b6e4ULL,\n\n\t0x56d3d83ae09974ceULL, 0x51409becfa2082c0ULL, 0x59f55f96d5ea98d2ULL,\n\n\t0x5e661c40cf536edcULL, 0x0d30f4b3f42e7c66ULL, 0x0aa3b765ee978a68ULL,\n\n\t0x0216731fc15d907aULL, 0x058530c9dbe46674ULL, 0x137dfbeb9ec9a45eULL,\n\n\t0x14eeb83d84705250ULL, 0x1c5b7c47abba4842ULL, 0x1bc83f91b103be4cULL,\n\n\t0x31aaea0321e1cc16ULL, 0x3639a9d53b583a18ULL, 0x3e8c6daf1492200aULL,\n\n\t0x391f2e790e2bd604ULL, 0x2fe7e55b4b06142eULL, 0x2874a68d51bfe220ULL,\n\n\t0x20c162f77e75f832ULL, 0x2752212164cc0e3cULL, 0x6e6520b5b7ede44aULL,\n\n\t0x69f66363ad541244ULL, 0x6143a719829e0856ULL, 0x66d0e4cf9827fe58ULL,\n\n\t0x70282feddd0a3c72ULL, 0x77bb6c3bc7b3ca7cULL, 0x7f0ea841e879d06eULL,\n\n\t0x789deb97f2c02660ULL, 0x52ff3e056222543aULL, 0x556c7dd3789ba234ULL,\n\n\t0x5dd9b9a95751b826ULL, 0x5a4afa7f4de84e28ULL, 0x4cb2315d08c58c02ULL,\n\n\t0x4b21728b127c7a0cULL, 0x4394b6f13db6601eULL, 0x4407f527270f9610ULL,\n\n\t0x17511dd41c7284aaULL, 0x10c25e0206cb72a4ULL, 0x18779a78290168b6ULL,\n\n\t0x1fe4d9ae33b89eb8ULL, 0x091c128c76955c92ULL, 0x0e8f515a6c2caa9cULL,\n\n\t0x063a952043e6b08eULL, 0x01a9d6f6595f4680ULL, 0x2bcb0364c9bd34daULL,\n\n\t0x2c5840b2d304c2d4ULL, 0x24ed84c8fcced8c6ULL, 0x237ec71ee6772ec8ULL,\n\n\t0x35860c3ca35aece2ULL, 0x32154feab9e31aecULL, 0x3aa08b90962900feULL,\n\n\t0x3d33c8468c90f6f0ULL, 0x2d53793d33aa0ae9ULL, 0x2ac03aeb2913fce7ULL,\n\n\t0x2275fe9106d9e6f5ULL, 0x25e6bd471c6010fbULL, 0x331e7665594dd2d1ULL,\n\n\t0x348d35b343f424dfULL, 0x3c38f1c96c3e3ecdULL, 0x3babb21f7687c8c3ULL,\n\n\t0x11c9678de665ba99ULL, 0x165a245bfcdc4c97ULL, 0x1eefe021d3165685ULL,\n\n\t0x197ca3f7c9afa08bULL, 0x0f8468d58c8262a1ULL, 0x08172b03963b94afULL,\n\n\t0x00a2ef79b9f18ebdULL, 0x0731acafa34878b3ULL, 0x5467445c98356a09ULL,\n\n\t0x53f4078a828c9c07ULL, 0x5b41c3f0ad468615ULL, 0x5cd28026b7ff701bULL,\n\n\t0x4a2a4b04f2d2b231ULL, 0x4db908d2e86b443fULL, 0x450ccca8c7a15e2dULL,\n\n\t0x429f8f7edd18a823ULL, 0x68fd5aec4dfada79ULL, 0x6f6e193a57432c77ULL,\n\n\t0x67dbdd4078893665ULL, 0x60489e966230c06bULL, 0x76b055b4271d0241ULL,\n\n\t0x712316623da4f44fULL, 0x7996d218126eee5dULL, 0x7e0591ce08d71853ULL,\n\n\t0x5957b0ef6c1b166fULL, 0x5ec4f33976a2e061ULL, 0x567137435968fa73ULL,\n\n\t0x51e2749543d10c7dULL, 0x471abfb706fcce57ULL, 0x4089fc611c453859ULL,\n\n\t0x483c381b338f224bULL, 0x4faf7bcd2936d445ULL, 0x65cdae5fb9d4a61fULL,\n\n\t0x625eed89a36d5011ULL, 0x6aeb29f38ca74a03ULL, 0x6d786a25961ebc0dULL,\n\n\t0x7b80a107d3337e27ULL, 0x7c13e2d1c98a8829ULL, 0x74a626abe640923bULL,\n\n\t0x7335657dfcf96435ULL, 0x20638d8ec784768fULL, 0x27f0ce58dd3d8081ULL,\n\n\t0x2f450a22f2f79a93ULL, 0x28d649f4e84e6c9dULL, 0x3e2e82d6ad63aeb7ULL,\n\n\t0x39bdc100b7da58b9ULL, 0x3108057a981042abULL, 0x369b46ac82a9b4a5ULL,\n\n\t0x1cf9933e124bc6ffULL, 0x1b6ad0e808f230f1ULL, 0x13df149227382ae3ULL,\n\n\t0x144c57443d81dcedULL, 0x02b49c6678ac1ec7ULL, 0x0527dfb06215e8c9ULL,\n\n\t0x0d921bca4ddff2dbULL, 0x0a01581c576604d5ULL, 0x1a61e967e85cf8ccULL,\n\n\t0x1df2aab1f2e50ec2ULL, 0x15476ecbdd2f14d0ULL, 0x12d42d1dc796e2deULL,\n\n\t0x042ce63f82bb20f4ULL, 0x03bfa5e99802d6faULL, 0x0b0a6193b7c8cce8ULL,\n\n\t0x0c992245ad713ae6ULL, 0x26fbf7d73d9348bcULL, 0x2168b401272abeb2ULL,\n\n\t0x29dd707b08e0a4a0ULL, 0x2e4e33ad125952aeULL, 0x38b6f88f57749084ULL,\n\n\t0x3f25bb594dcd668aULL, 0x37907f2362077c98ULL, 0x30033cf578be8a96ULL,\n\n\t0x6355d40643c3982cULL, 0x64c697d0597a6e22ULL, 0x6c7353aa76b07430ULL,\n\n\t0x6be0107c6c09823eULL, 0x7d18db5e29244014ULL, 0x7a8b9888339db61aULL,\n\n\t0x723e5cf21c57ac08ULL, 0x75ad1f2406ee5a06ULL, 0x5fcfcab6960c285cULL,\n\n\t0x585c89608cb5de52ULL, 0x50e94d1aa37fc440ULL, 0x577a0eccb9c6324eULL,\n\n\t0x4182c5eefcebf064ULL, 0x46118638e652066aULL, 0x4ea44242c9981c78ULL,\n\n\t0x49370194d321ea76ULL\n\n};\n\n\n\n#endif\n\n\n\nstatic unsigned char rabin_window[RABIN_WINDOW_SIZE];\n\nstatic unsigned rabin_pos = 0;\n\n\n\n#define MIN(x,y) ((y)<(x) ? (y) : (x))\n\n#define MAX(x,y) ((y)>(x) ? (y) : (x))\n\n\n\n/*\n\n * The copies array is the central data structure for diff generation.\n\n * Data statements are implicit, for ranges not covered by any copy command.\n\n *\n\n * The sum of tgt and length for each entry must be monotonically increasing,\n\n * and data ranges must be non-overlapping. This is accomplished by not\n\n * extending matches backwards during initial matching.\n\n *\n\n * Copies may have zero length, to make it quick to delete copies during\n\n * optimization. However, the last copy in the list must always be a\n\n * non-trivial copy.\n\n *\n\n * Before committing copies, an important optimization is performed: during \n\n * a backward pass through the copies array, each entry is extended backwards,\n\n * and redundant copies are eliminated.\n\n *\n\n * If each match were extended backwards on insertion, the same data may be\n\n * matched an arbitrary number of times, resulting in potentially quadratic\n\n * time behavior.\n\n */\n\n\n\ntypedef struct copyinfo {\n\n\tunsigned src;\n\n\tunsigned tgt;\n\n\tunsigned length;\n\n} CopyInfo;\n\n\n\nstatic CopyInfo *copies;\n\nstatic int copy_count = 0;\n\nstatic unsigned max_copies = 0; /* Dynamically increased */\n\n\n\nstatic unsigned *idx;\n\nstatic unsigned idx_size;\n\nstatic unsigned char *idx_data;\n\nstatic unsigned idx_data_len;\n\n\n\nstatic void rabin_reset(void)\n\n{\n\n\tmemset(rabin_window, 0, sizeof(rabin_window));\n\n}\n\n\n\nstatic u_int64_t rabin_slide (u_int64_t fp, unsigned char m)\n\n{\n\n\tunsigned char om;\n\n\tif (++rabin_pos == RABIN_WINDOW_SIZE) rabin_pos = 0;\n\n\tom = rabin_window[rabin_pos];\n\n\tfp ^= U[om];\n\n\trabin_window[rabin_pos] = m;\n\n\tfp = ((fp << 8) | m) ^ T[fp >> RABIN_SHIFT];\n\n\treturn fp;\n\n}\n\n\n\nstatic void init_idx (unsigned char *data, size_t len, int level)\n\n{\n\n\tunsigned index_step = RABIN_WINDOW_SIZE / sizeof(unsigned) * sizeof(unsigned);\n\n\tsize_t j, k;\n\n\tunsigned char ch = 0;\n\n\tunsigned maxofs[256];\n\n\tunsigned maxlen[256];\n\n\tunsigned maxfp[256];\n\n\tunsigned runlen = 0;\n\n\tu_int64_t fp = 0;\n\n\n\n\tassert (len <= MAX_SIZE);\n\n\tassert (level >= 0 && level <= 9);\n\n\tmemset(maxofs, 0, sizeof(maxofs));\n\n\tmemset(maxlen, 0, sizeof(maxlen));\n\n\tmemset(maxfp, 0, sizeof(maxfp));\n\n\n\n\t/* index_step must be multiple of word size */\n\n\tif (level >= 1)\n\n\t\tindex_step = MIN(index_step, 4 * sizeof(unsigned));\n\n\t/* Use smaller step size for higher optimization levels or smaller files */\n\n\tif (level >= 3 || len <= 65536)\n\n\t\tindex_step = MIN (index_step, 3 * sizeof (unsigned));\n\n\tif (level >= 4 || len <= 32768)\n\n\t\tindex_step = MIN (index_step, 2 * sizeof (unsigned));\n\n\tif (level >= 6 || len < 16384)\n\n\t\tindex_step = MIN (index_step, 1 * sizeof (unsigned));\n\n\tassert (index_step && !(index_step % sizeof (unsigned)));\n\n\n\n\t/* Add fixed amount to hash table size, as small files will benefit\n\n\t a lot without using significantly more memory or time. */\n\n\tidx_size = (level + 1) * (len / index_step) / 2 + MIN_HTAB_SIZE;\n\n\tidx_size = MIN (idx_size, MAX_HTAB_SIZE - 1); /* So rounding up works */\n\n\n\n\t/* Round up to next power of two, but limit to MAX_HTAB_SIZE. */\n\n\t{\n\n\t\tunsigned s = MIN_HTAB_SIZE;\n\n\t\twhile (s < idx_size) s += s;\n\n\t\tidx_size = s;\n\n\t}\n\n\n\n\tidx_data = data;\n\n\tidx_data_len = len;\n\n\tidx = calloc(idx_size, sizeof(unsigned)); \n\n\n\n\t/* It is tempting to first index higher addresses, so hashes of lower\n\n\t addresses will get preference in the hash table. However, for\n\n\t repetitive patterns with a period that is a divisor of the fingerprint\n\n\t window, this may mean the match is not anchored at the end. \n\n\t Furthermore, even when using a window length that is prime, the\n\n\t benefits are small and the irregularity of the first matches being\n\n\t more important is not worth it. */\n\n\n\n\trabin_reset();\n\n\n\n\tch = 0;\n\n\trunlen = 0;\n\n\n\n\tfor (j = 0; j + index_step < len; j += index_step) {\n\n\t\tunsigned char pch = 0;\n\n\t\tunsigned hash;\n\n\n\n\t\tfor (k = 0; k < index_step; k++) {\n\n\t\t\tpch = ch;\n\n\t\t\tch = data[j + k];\n\n\t\t\tif (ch != pch)\n\n\t\t\t\trunlen = 0;\n\n\t\t\trunlen++;\n\n\t\t\tfp = rabin_slide(fp, ch);\n\n\t\t}\n\n\n\n\t\t/* See if there is a word-aligned window-sized run of equal characters */\n\n\t\tif (runlen >= RABIN_WINDOW_SIZE + sizeof(unsigned) - 1) {\n\n\t\t\t/* Skip ahead to end of run of identical input characters */\n\n\t\t\twhile (j + k < len && data[j + k] == ch) {\n\n\t\t\t\tk++;\n\n\t\t\t\trunlen++;\n\n\t\t\t}\n\n\n\n\t\t\t/* Although matches are usually anchored at the end, in the case\n\n\t\t\t of extended runs of equal characters it is better to anchor after the\n\n\t\t\t first RABIN_WINDOW_SIZE bytes. This allows for quick skip ahead \n\n\t\t\t while matching such runs, avoiding unneeded fingerprint calculations.\n\n\t\t\t Also, when anchoring at the end, matches will be generated after\n\n\t\t\t every word, because the fingerprint stays constant. Even though\n\n\t\t\t all matches would get combined during match optimization, \n\n\t\t\t it wastes time and space. */\n\n\t\t\tif (runlen > maxlen[pch] + 4) {\n\n\t\t\t\tunsigned ofs;\n\n\t\t\t\t/* ofs points RABIN_WINDOW_SIZE bytes after the start of the run,\n\n\t\t\t\t rounded up to the next word */\n\n\t\t\t\tofs = j + k - runlen + RABIN_WINDOW_SIZE + (sizeof (unsigned) - 1);\n\n\t\t\t\tofs -= ofs % sizeof(unsigned);\n\n\t\t\t\tmaxofs[pch] = ofs;\n\n\t\t\t\tmaxlen [pch] = runlen;\n\n\t\t\t\tassert(maxfp[pch] == 0 || maxfp[pch] == (unsigned)fp);\n\n\t\t\t\tmaxfp[pch] = (unsigned)fp;\n\n\t\t\t}\n\n\t\t\t/* Keep input aligned as if no special run processing had taken place */\n\n\t\t\tj += k - (k % index_step) - index_step;\n\n\t\t\tk = index_step;\n\n\t\t}\n\n\n\n\t\t/* Testing showed that avoiding collisions using secondary hashing, or\n\n\t\t hash chaining had little effect and is not worth the time. */\n\n\t\thash = ((unsigned)fp) & (idx_size - 1);\n\n\t\tidx[hash] = j + k;\n\n\t}\n\n\n\n\t/* Lastly, index the longest runs of equal characters found before.\n\n\t This ensures we always match the longerst such runs available. */\n\n\tfor (j = 0; j < 256; j++) \n\n\t\tif (maxlen[j]) \n\n\t\t\tidx[maxfp[j] % idx_size] = maxofs[j];\n\n}\n\n\n\n/* Match data against the current index and record all possible copies */\n\nstatic int find_copies(unsigned char *data, size_t len)\n\n{\n\n\tsize_t j = 0;\n\n\tu_int64_t fp = 0;\n\n\n\n\trabin_reset();\n\n\n\n\twhile (j < RABIN_WINDOW_SIZE && j < len)\n\n\t\tfp = rabin_slide(fp, data[j++]);\n\n\n\n\twhile (j < len) { \n\n\t\tunsigned hash, ofs, src, tgt, runlen, maxrun;\n\n\n\n\t\tfp = rabin_slide(fp, data[j++]);\n\n\t\thash = fp & (idx_size - 1);\n\n\t\tofs = idx[hash];\n\n\n\n\t\t/* Invariant:\n\n\t\t data[0] .. data[j-1] has been processed\n\n\t\t fp is fingerprint of sliding window ending at j-1\n\n\t\t ofs is zero or points just past tentative match\n\n\t\t ofs is a multiple of index_step */\n\n\n\n\t\tif (!ofs)\n\n\t\t\tcontinue;\n\n\n\n\t\trunlen = 0;\n\n\t\ttgt = j - 4;\n\n\t\tsrc = ofs - 4;\n\n\t\tmaxrun = MIN(idx_data_len - src, len - tgt);\n\n\n\n\t\t/* Hot loop */\n\n\t\twhile (runlen < maxrun &&\n\n\t\t data[tgt + runlen] == idx_data[src + runlen])\n\n\t\t\trunlen++;\n\n\t\tif (runlen < 4)\n\n\t\t\tcontinue;\n\n\n\n\t\tif (copy_count == max_copies) {\n\n\t\t\tmax_copies *= 2;\n\n\t\t\tif (!copies) {\n\n\t\t\t\tmax_copies = MAX_COPIES;\n\n\t\t\t\tcopies = malloc(max_copies * sizeof(CopyInfo));\n\n\t\t\t} else {\n\n\t\t\t\tcopies = realloc(copies, max_copies * sizeof (CopyInfo));\n\n\t\t\t}\n\n\t\t\tif (!copies)\n\n\t\t\t\treturn 0;\n\n\t\t}\n\n\n\n\t\tcopies[copy_count].src = src;\n\n\t\tcopies[copy_count].tgt = tgt;\n\n\t\tcopies[copy_count].length = runlen;\n\n\t\tcopy_count++;\n\n\n\n\t\t/* For runs extending more than RABIN_WINDOW_SIZE bytes beyond j,\n\n\t\t skip ahead to prevent useless fingerprint computations. */\n\n\t\tif (tgt + runlen > j + RABIN_WINDOW_SIZE)\n\n\t\t\tj = tgt + runlen - RABIN_WINDOW_SIZE;\n\n\n\n\t\t/* Quickly scan ahead without looking for matches\n\n\t\t until the end of this run */\n\n\t\twhile (j < tgt + runlen)\n\n\t\t\tfp = rabin_slide(fp, data[j++]);\n\n\t}\n\n\n\n\treturn 1;\n\n}\n\n\n\nstatic unsigned header_length(unsigned srclen, unsigned tgtlen)\n\n{\n\n\tunsigned len = 0;\n\n\tassert (srclen <= MAX_SIZE && tgtlen <= MAX_SIZE);\n\n\n\n\t/* GIT headers start with the length of the source and target,\n\n\t with 7 bits per byte, least significant byte first, and\n\n\t the high bit indicating continuation. */\n\n\tdo { len++; srclen >>= 7; } while (srclen);\n\n\tdo { len++; tgtlen >>= 7; } while (tgtlen);\n\n\n\n\treturn len;\n\n}\n\n\n\nstatic unsigned char *write_header(unsigned char *patch, unsigned srclen, unsigned tgtlen)\n\n{\n\n\tassert (srclen <= MAX_SIZE && tgtlen <= MAX_SIZE);\n\n\n\n\twhile (srclen >= 0x80) {\n\n\t\t*patch++ = srclen | 0x80;\n\n\t\tsrclen >>= 7;\n\n\t}\n\n\t*patch++ = srclen;\n\n\n\n\twhile (tgtlen >= 0x80) {\n\n\t\t*patch++ = tgtlen | 0x80;\n\n\t\ttgtlen >>= 7;\n\n\t}\n\n\t*patch++ = tgtlen;\n\n\n\n\treturn patch;\n\n}\n\n\n\nstatic unsigned data_length(unsigned length)\n\n{\n\n\t/* Can only include 0x7f data bytes per command */\n\n\tunsigned partial = length % 0x7f;\n\n\tassert (length > 0 && length <= MAX_SIZE);\n\n\tif (partial) partial++;\n\n\treturn partial + (length / 0x7f) * 0x80;\n\n}\n\n\n\nstatic unsigned char *write_data(unsigned char *patch, unsigned char *data, unsigned size)\n\n{\n\n\tassert (size > 0 && size < MAX_SIZE);\n\n\t/* The return value must be equal to patch + data_length (patch, size).\n\n\t This correspondence is essential for calculating the patch size. */\n\n\n\n\t/* GIT has no data commands for large data, rest is same as GDIFF */\n\n\tdo {\n\n\t\tunsigned s = size;\n\n\t\tif (s > 0x7f)\n\n\t\t\ts = 0x7f;\n\n\t\t*patch++ = s;\n\n\t\tmemcpy(patch, data, s);\n\n\t\tdata += s;\n\n\t\tpatch += s;\n\n\t\tsize -= s;\n\n\t} while (size);\n\n\n\n\treturn patch;\n\n} \n\n\n\nstatic unsigned copy_length (unsigned offset, unsigned length)\n\n{\n\n\tunsigned size = 0;\n\n\n\n\tassert (offset < MAX_SIZE && length < MAX_SIZE);\n\n\n\n\t/* For now we only copy a maximum of 0x10000 bytes per command.\n\n\t Longer copies are broken into pieces of that size. */\n\n\tdo {\n\n\t\tsigned s = length;\n\n\t\tif (s > 0x10000)\n\n\t\t\ts = 0x10000;\n\n\t\tsize += !!(s & 0xff) + !!(s & 0xff00);\n\n\t\tsize += !!(offset & 0xff) + !!(offset & 0xff00) + \n\n\t\t\t!!(offset & 0xff0000) + !!(offset & 0xff000000);\n\n\t\tsize += 1;\n\n\t\toffset += s;\n\n\t\tlength -= s;\n\n\t} while (length);\n\n\n\n\treturn size;\n\n}\n\n\n\nstatic unsigned char * write_copy(unsigned char *patch, unsigned offset, unsigned size)\n\n{\n\n\t/* The return value must be equal to patch + copy_length (patch,offset,size).\n\n\t This correspondence is essential for calculating the patch size. */\n\n\n\n\tdo {\n\n\t\tunsigned char c = 0x80, *cmd = patch++;\n\n\t\tunsigned v, s = size;\n\n\t\tif (s > 0x10000)\n\n\t\t\ts = 0x10000;\n\n\n\n\t\tv = offset;\n\n\t\tif (v & 0xff) c |= 0x01, *patch++ = v;\n\n\t\tv >>= 8;\n\n\t\tif (v & 0xff) c |= 0x02, *patch++ = v;\n\n\t\tv >>= 8;\n\n\t\tif (v & 0xff) c |= 0x04, *patch++ = v;\n\n\t\tv >>= 8;\n\n\t\tif (v & 0xff) c |= 0x08, *patch++ = v;\n\n\n\n\t\tv = s;\n\n\t\tif (v & 0xff) c |= 0x10, *patch++ = v;\n\n\t\tv >>= 8;\n\n\t\tif (v & 0xff) c |= 0x20, *patch++ = v;\n\n\n\n\t\t*cmd = c;\n\n\t\toffset += s;\n\n\t\tsize -= s;\n\n\t} while (size);\n\n\n\n\treturn patch;\n\n} \n\n\n\nstatic unsigned process_copies (unsigned char *data, unsigned length, unsigned maxlen)\n\n{\n\n\tint j;\n\n\tunsigned ptr = length;\n\n\tunsigned patch_bytes = header_length(idx_data_len, length);\n\n\n\n\t/* Work through the copies backwards, extending each one backwards. */\n\n\tfor (j = copy_count - 1; j >= 0; j--) {\n\n\t\tCopyInfo *copy = copies+j;\n\n\t\tunsigned src = copy->src;\n\n\t\tunsigned tgt = copy->tgt;\n\n\t\tunsigned len = copy->length;\n\n\t\tint data_follows;\n\n\n\n\t\tif (tgt + len > ptr) {\n\n\t\t\t/* Part of copy already covered by later one, so shorten copy. */\n\n\t\t\tif (ptr < tgt) {\n\n\t\t\t\t/* Copy completely disappeared, but guess that a backward extension\n\n\t\t\t\t might still be useful. This extension is non-contiguous, as it is\n\n\t\t\t\t irrelevant whether the skipped data would have matched or not.\n\n\t\t\t\t Be careful to not extend past the beginning of the source. */\n\n\t\t\t\tunsigned adjust = tgt - ptr;\n\n\n\n\t\t\t\ttgt = ptr;\n\n\t\t\t\tsrc = (src < adjust) ? 0 : src - adjust;\n\n\n\n\t\t\t\tcopy->tgt = tgt;\n\n\t\t\t\tcopy->src = src;\n\n\t\t\t}\n\n\n\n\t\t\tlen = ptr - tgt;\n\n\t\t}\n\n\n\n\t\twhile (src && tgt && idx_data[src - 1] == data[tgt - 1]) {\n\n\t\t\tsrc--;\n\n\t\t\ttgt--;\n\n\t\t}\n\n\t\tlen += copy->tgt - tgt;\n\n\n\n\t\tdata_follows = (tgt + len < ptr);\n\n\n\n\t\t/* A short copy may cost as much as 6 bytes for the copy and\n\n\t\t 5 as result of an extra data command.\n\n\t\t It's not worth having extra copies in order to just save a byte or two.\n\n\t\t Being too smart here may hurt later compression as well. */\n\n\t\tif (len < (data_follows ? 16 : 10))\n\n\t\t\tlen = 0;\n\n\n\n\t\t/* Some target data is not covered by the copies, account for\n\n\t\t the DATA command that will follow the copy. */\n\n\t\tif (len && data_follows) \n\n\t\t\tpatch_bytes += data_length(ptr - (tgt + len));\n\n\n\n\t\t/* Everything about the copy is known and will not change.\n\n\t\t Write back the new information and update the patch size\n\n\t\t with the size of the copy instruction. */\n\n\t\tcopy->length = len;\n\n\t\tcopy->src = src;\n\n\t\tcopy->tgt = tgt;\n\n\n\n\t\tif (len) {\n\n\t\t\t/* update patch size for copy command */\n\n\t\t\tpatch_bytes += copy_length (src, len);\n\n\t\t\tptr = tgt;\n\n\t\t} else if (j == copy_count - 1) {\n\n\t\t\t/* Remove empty copies at end of list. */\n\n\t\t\tcopy_count--;\n\n\t\t}\n\n\n\n\t\tif (patch_bytes > maxlen)\n\n\t\t\treturn 0;\n\n\t}\n\n\n\n\t/* Account for data before first copy */\n\n\tif (ptr != 0)\n\n\t\tpatch_bytes += data_length(ptr);\n\n\n\n\tif (patch_bytes > maxlen)\n\n\t\treturn 0;\n\n\treturn patch_bytes;\n\n}\n\n\n\nstatic unsigned calculate_delta(void *to_buf, unsigned long to_size, unsigned long max_size)\n\n{\n\n\tassert (to_size < MAX_SIZE);\n\n\n\n\tif (!find_copies(to_buf, to_size))\n\n\t\treturn 0;\n\n\treturn process_copies(to_buf, to_size, max_size);\n\n}\n\n\n\nstatic void *create_delta (unsigned char *data, unsigned len, unsigned delta_size)\n\n{\n\n\tunsigned char *delta = malloc(delta_size);\n\n\tunsigned char *ptr = delta;\n\n\tunsigned offset = 0;\n\n\tint j;\n\n\n\n\tptr = write_header(ptr, idx_data_len, len);\n\n\n\n\tfor (j = 0; j < copy_count; j++) {\n\n\t\tCopyInfo *copy = copies + j;\n\n\t\tunsigned copylen = copy->length;\n\n\n\n\t\tif (!copylen)\n\n\t\t\tcontinue;\n\n\n\n\t\tif (copy->tgt > offset) {\n\n\t\t\tassert (delta_size - (ptr - delta) > data_length(copy->tgt - offset));\n\n\t\t\tptr = write_data(ptr, data + offset, copy->tgt - offset);\n\n\t\t}\n\n\n\n\t\tassert(delta_size - (ptr - delta) >= copy_length(copy->src, copylen));\n\n\t\tptr = write_copy(ptr, copy->src, copylen);\n\n\t\toffset = copy->tgt + copylen;\n\n\t}\n\n\n\n\tif (offset < len)\n\n\t\tptr = write_data(ptr, data + offset, len - offset);\n\n\n\n\tassert(ptr - delta == delta_size);\n\n\n\n\treturn delta;\n\n}\n\n\n\nstatic void finalize_idx()\n\n{\n\n\tfree(copies);\n\n\tcopies = 0;\n\n\tmax_copies = 0;\n\n\tcopy_count = 0;\n\n\tfree(idx);\n\n\tidx = 0;\n\n\tidx_size = 0;\n\n\tidx_data = 0;\n\n\tidx_data_len = 0;\n\n}\n\n\n\nvoid *diff_delta(void *from_buf, unsigned long from_size,\n\n\t\t void *to_buf, unsigned long to_size,\n\n\t\t unsigned long *delta_size, unsigned long max_size)\n\n{\n\n\tunsigned char *delta = 0;\n\n\tunsigned dsize;\n\n\n\n\tassert (from_size <= MAX_SIZE && to_size <= MAX_SIZE);\n\n\tinit_idx(from_buf, from_size, 1); /* Use optimization level 1 */\n\n\tif (!max_size)\n\n\t\tmax_size = MAX_SIZE;\n\n\tdsize = calculate_delta (to_buf, to_size, max_size);\n\n\tif (dsize)\n\n\t\tdelta = create_delta (to_buf, to_size, dsize);\n\n\tfinalize_idx ();\n\n\tif (delta)\t\n\n\t\t*delta_size = dsize;\n\n\treturn delta;\n\n}\n\n"},{"id":"19044","messageId":"20060424151901.GA2663@adacore.com","threadId":"3938","inReplyTo":"Pine.LNX.4.64.0604232327500.3603@localhost.localdomain","subject":"Re: RFC: New diff-delta.c implementation","fromName":"Geert Bosch","fromEmail":"bosch@adacore.com","sentAt":"2006-04-24T15:19:01Z","receivedAt":"2006-04-24T15:19:01Z","isPatch":false,"sender":{"key":"bosch@adacore.com","avatar":null},"body":"On Mon, Apr 24, 2006 at 01:27:07AM -0400, Nicolas Pitre wrote:\n> I took the liberty of reworking the coding style, as well as simplifying \n> some constructs a bit.\n> \n> I also fixed all the format encoding and size computations bugs the \n> original code has so it works perfectly now.\nThanks for fixing that! I'll have a more detailed look at your\nchanges later, as not all changes are immediately obvious since the\nformatting is different.\n> Note that the GIT encoding is itself different (a bit denser) from the \n> xdiff encoding.\nOK, I mostly looked a patch-delta.c to reverse engineer the format,\nand mainly looked at libxdiff in the hope to find some format description\nthere.\n> Please just completely drop that word fetch \"optimization\". Not only \n> does it produce worse assembly code in the end due to the extra loop \n> counter and extra shifting in turn increasing register pressure, but it \n> also assumes that the target data buffer is always word aligned which is \n> not guaranteed (casting a char pointer to an unsigned and dereferencing \n> it is not portable since on some architecture such misaligned accesses \n> are not allowed). And it even has worse performance. For example, with \n> word fetch and shift code, packing the Linux kernel archive on my P4 at \n> 3GHz:\n\n> user 6m33.797s\n[vs.]\n> user 6m13.911s\n> So you must be extremely careful when trying to implement such kind of \n> optimizations.\n\nAs a compiler writer, I am more than aware of this. \nYour change results in a 70% slowdown on PowerPC. On many targets\nbyte-accesses are relatively slow. Indeed, I had expect this to be\nmostly neutral on x86, and the 5% slowdown you saw is not unexpected.\nNote that in this case aligned accesses are guaranteed, because the\nindex_step is guaranteed to be a multiple of the word size.\n\n> But here comes the sad part. Even after simplifying the code as much as \n> I could, performance is still significantly worse than the current \n> diff-delta.c code. Repacking again the same Linux kernel repository \n> with the current code:\nThat's unexpected, but I can see how this could be if most files have\nvery few differences and are relatively small. For such cases, almost\nany hash will do, and the more complicated hashing will be more compute\nintensive.\n\n\nI have benchmarked my original diff code on a set of large files with\nlots of changes. These are hardest to get right, and hardest to get\ngood performance with. Just try diffing any two large (uncompressed)\ntar files, and you'll see. On many of such large files, the new code\nis orders of magnitude faster. On these cases, the resulting deltas\nare also much smaller.\n\nThe comparison is a bit between a O(n^2) sort that is fast on small\nor mostly sorted inputs (but horrible on large ones) and a more\ncomplex O(nlogn) algorithm that is a bit slower for the simple\ncases, but far faster for more complex cases.\n\n> In the mean time I'll try replacing the adler32 hashing with your Rabin \n> polynomial hashing into the current code just to see if it helps (and I \n> think it will help quite a bit). The best solution might be a mix of \n> both approaches.\nI think the most interesting part of my code is in process_copies.\nThis optimization results in elimination of about half the commands\nin large test cases, while taking virtually no time at all.\nAlso, I believe that any form of hash chaining of secondary hashing\nis useless. I have done many benchmarks, and in all cases a slight\nincrease of hash table size was both more effective for pack size and\nfaster due to less cache misses.\n> Of course there is the issue of reversing the object matching window \n> logic in pack-object.c to further improve things, but I consider that an \n> orthogonal improvement at this point which both approaches will benefit \n> from anyway.\n\nRight, this will be the most important one for performance for now.\n\nThanks again for taking the time to look at my code and fixing the\nerrors in handling the git file format.\n\n -Geert\n\nPS. Somehow your code had \"double line spacing\" :)\n"},{"id":"19045","messageId":"Pine.LNX.4.64.0604241123490.18520@localhost.localdomain","threadId":"3938","inReplyTo":"20060424151901.GA2663@adacore.com","subject":"Re: RFC: New diff-delta.c implementation","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-04-24T15:57:38Z","receivedAt":"2006-04-24T15:57:38Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Mon, 24 Apr 2006, Geert Bosch wrote:\n\n> On Mon, Apr 24, 2006 at 01:27:07AM -0400, Nicolas Pitre wrote:\n> > Please just completely drop that word fetch \"optimization\". Not only \n> > does it produce worse assembly code in the end due to the extra loop \n> > counter and extra shifting in turn increasing register pressure, but it \n> > also assumes that the target data buffer is always word aligned which is \n> > not guaranteed (casting a char pointer to an unsigned and dereferencing \n> > it is not portable since on some architecture such misaligned accesses \n> > are not allowed). And it even has worse performance. For example, with \n> > word fetch and shift code, packing the Linux kernel archive on my P4 at \n> > 3GHz:\n> \n> > user 6m33.797s\n> [vs.]\n> > user 6m13.911s\n> > So you must be extremely careful when trying to implement such kind of \n> > optimizations.\n> \n> As a compiler writer, I am more than aware of this. \n> Your change results in a 70% slowdown on PowerPC.\n\nHuh!?\n\n> On many targets\n> byte-accesses are relatively slow. Indeed, I had expect this to be\n> mostly neutral on x86, and the 5% slowdown you saw is not unexpected.\n\nFWIW I'd expect a slowdown on ARM as well but I didn't bench it.\n\n> Note that in this case aligned accesses are guaranteed, because the\n> index_step is guaranteed to be a multiple of the word size.\n\nSure, but the data buffers aren't necessarily so. At least some code to \nalign index_step with actual memory offset if necessary should be \nconsidered.\n\n> > But here comes the sad part. Even after simplifying the code as much as \n> > I could, performance is still significantly worse than the current \n> > diff-delta.c code. Repacking again the same Linux kernel repository \n> > with the current code:\n> That's unexpected, but I can see how this could be if most files have\n> very few differences and are relatively small. For such cases, almost\n> any hash will do, and the more complicated hashing will be more compute\n> intensive.\n> \n> \n> I have benchmarked my original diff code on a set of large files with\n> lots of changes. These are hardest to get right, and hardest to get\n> good performance with. Just try diffing any two large (uncompressed)\n> tar files, and you'll see. On many of such large files, the new code\n> is orders of magnitude faster. On these cases, the resulting deltas\n> are also much smaller.\n> \n> The comparison is a bit between a O(n^2) sort that is fast on small\n> or mostly sorted inputs (but horrible on large ones) and a more\n> complex O(nlogn) algorithm that is a bit slower for the simple\n> cases, but far faster for more complex cases.\n\nIndeed. And since the primary goal for GIT is to manage relatively \nsmall files with relatively few differences then we have to optimize for \nthat case while trying to simply limit the dammage in the other cases.\n\n> > In the mean time I'll try replacing the adler32 hashing with your Rabin \n> > polynomial hashing into the current code just to see if it helps (and I \n> > think it will help quite a bit). The best solution might be a mix of \n> > both approaches.\n> I think the most interesting part of my code is in process_copies.\n> This optimization results in elimination of about half the commands\n> in large test cases, while taking virtually no time at all.\n\nYes, I found that part really nice and clever.\n\n> Also, I believe that any form of hash chaining of secondary hashing\n> is useless. I have done many benchmarks, and in all cases a slight\n> increase of hash table size was both more effective for pack size and\n> faster due to less cache misses.\n\nWell, I did lots of benchmarks too over the Linux kernel repository \nwith the current code. It is of course a dataset quite different from \ntwo large files. And simply increasing the hash size to improve on pack \nsize did increase CPU usage quite significantly.\n\n> PS. Somehow your code had \"double line spacing\" :)\n\nGah. Your original version must have CRLF line terminations, and vi \nsimply notice that and writes the file back with CRLF by default. Find \nattached a version with those converted to LF only.\n\n\nNicolas\n\n\n#include \n#include \n#include \n#include \n#include \n\n#undef assert\n#define assert(x) do { } while (0)\n\n/*\n * MIN_HTAB_SIZE is fixed amount to be added to the size of the hash table\n * used for indexing and must be a power of two. This allows for small files\n * to have a sparse hash table, since in that case it's cheap.\n * Hash table sizes are rounded up to a power of two to avoid integer division. \n */\n#define MIN_HTAB_SIZE 8192\n#define MAX_HTAB_SIZE (1024*1024*1024)\n\n/*\n * Diffing files of gigabyte range is impractical with the current\n * algorithm, so we're assuming 32-bit sizes everywhere.\n * Size leaves some room for expansion when diffing random files.\n */\n#define MAX_SIZE (0x7eff0000)\n\n/* Initial size of copies table, dynamically extended as needed. */\n#define MAX_COPIES 4096\n\n/*\n * Matching is done using a sliding window for which a Rabin\n * polynomial is computed. The advantage of such polynomials is\n * that they can efficiently be updated at every position.\n * The tables needed for this are precomputed, as it is desirable\n * to use the same polynomial all the time for repeatable results.\n */\n\n#if 0\t/* those don't seem to work */\n\n#define RABIN_POLY 0x25bd5331c0d7096dULL\n#define RABIN_DEGREE 61\n#define RABIN_SHIFT 53\n#define RABIN_WINDOW_SIZE 22\n\nstatic const u_int64_t T[256] = {\n\t0x6ec7f55241791bb7ULL, 0x96f54cc7035c25b4ULL, 0xb3481ff6c38b2cd9ULL,\n\t0xdd8feaa482f2376eULL, 0xf832b99542253e03ULL, 0x0857cabfc66f4205ULL,\n\t0x2dea998e06b84b68ULL, 0x432d6cdc47c150dfULL, 0x66903fed871659b2ULL,\n\t0x9ea28678c53367b1ULL, 0xbb1fd54905e46edcULL, 0xd5d8201b449d756bULL,\n\t0xf065732a844a7c06ULL, 0x10af957f8cde840aULL, 0x3512c64e4c098d67ULL,\n\t0x5bd5331c0d7096d0ULL, 0x7e68602dcda79fbdULL, 0x865ad9b88f82a1beULL,\n\t0xa3e78a894f55a8d3ULL, 0xcd207fdb0e2cb364ULL, 0xe89d2ceacefbba09ULL,\n\t0x18f85fc04ab1c60fULL, 0x3d450cf18a66cf62ULL, 0x5382f9a3cb1fd4d5ULL,\n\t0x763faa920bc8ddb8ULL, 0x8e0d130749ede3bbULL, 0xabb04036893aead6ULL,\n\t0xc577b564c843f161ULL, 0xe0cae6550894f80cULL, 0x04e279ced96a0179ULL,\n\t0x215f2aff19bd0814ULL, 0x4f98dfad58c413a3ULL, 0x6a258c9c98131aceULL,\n\t0x92173509da3624cdULL, 0xb7aa66381ae12da0ULL, 0xd96d936a5b983617ULL,\n\t0xfcd0c05b9b4f3f7aULL, 0x0cb5b3711f05437cULL, 0x2908e040dfd24a11ULL,\n\t0x47cf15129eab51a6ULL, 0x627246235e7c58cbULL, 0x9a40ffb61c5966c8ULL,\n\t0xbffdac87dc8e6fa5ULL, 0xd13a59d59df77412ULL, 0xf4870ae45d207d7fULL,\n\t0x144decb155b48573ULL, 0x31f0bf8095638c1eULL, 0x5f374ad2d41a97a9ULL,\n\t0x7a8a19e314cd9ec4ULL, 0x82b8a07656e8a0c7ULL, 0xa705f347963fa9aaULL,\n\t0xc9c20615d746b21dULL, 0xec7f55241791bb70ULL, 0x1c1a260e93dbc776ULL,\n\t0x39a7753f530cce1bULL, 0x5760806d1275d5acULL, 0x72ddd35cd2a2dcc1ULL,\n\t0x8aef6ac99087e2c2ULL, 0xaf5239f85050ebafULL, 0xc195ccaa1129f018ULL,\n\t0xe4289f9bd1fef975ULL, 0x09c4f39db2d402f2ULL, 0x2c79a0ac72030b9fULL,\n\t0x42be55fe337a1028ULL, 0x670306cff3ad1945ULL, 0x9f31bf5ab1882746ULL,\n\t0xba8cec6b715f2e2bULL, 0xd44b19393026359cULL, 0xf1f64a08f0f13cf1ULL,\n\t0x0193392274bb40f7ULL, 0x242e6a13b46c499aULL, 0x4ae99f41f515522dULL,\n\t0x6f54cc7035c25b40ULL, 0x976675e577e76543ULL, 0xb2db26d4b7306c2eULL,\n\t0xdc1cd386f6497799ULL, 0xf9a180b7369e7ef4ULL, 0x196b66e23e0a86f8ULL,\n\t0x3cd635d3fedd8f95ULL, 0x5211c081bfa49422ULL, 0x77ac93b07f739d4fULL,\n\t0x8f9e2a253d56a34cULL, 0xaa237914fd81aa21ULL, 0xc4e48c46bcf8b196ULL,\n\t0xe159df777c2fb8fbULL, 0x113cac5df865c4fdULL, 0x3481ff6c38b2cd90ULL,\n\t0x5a460a3e79cbd627ULL, 0x7ffb590fb91cdf4aULL, 0x87c9e09afb39e149ULL,\n\t0xa274b3ab3beee824ULL, 0xccb346f97a97f393ULL, 0xe90e15c8ba40fafeULL,\n\t0x0d268a536bbe038bULL, 0x289bd962ab690ae6ULL, 0x465c2c30ea101151ULL,\n\t0x63e17f012ac7183cULL, 0x9bd3c69468e2263fULL, 0xbe6e95a5a8352f52ULL,\n\t0xd0a960f7e94c34e5ULL, 0xf51433c6299b3d88ULL, 0x057140ecadd1418eULL,\n\t0x20cc13dd6d0648e3ULL, 0x4e0be68f2c7f5354ULL, 0x6bb6b5beeca85a39ULL,\n\t0x93840c2bae8d643aULL, 0xb6395f1a6e5a6d57ULL, 0xd8feaa482f2376e0ULL,\n\t0xfd43f979eff47f8dULL, 0x1d891f2ce7608781ULL, 0x38344c1d27b78eecULL,\n\t0x56f3b94f66ce955bULL, 0x734eea7ea6199c36ULL, 0x8b7c53ebe43ca235ULL,\n\t0xaec100da24ebab58ULL, 0xc006f5886592b0efULL, 0xe5bba6b9a545b982ULL,\n\t0x15ded593210fc584ULL, 0x306386a2e1d8cce9ULL, 0x5ea473f0a0a1d75eULL,\n\t0x7b1920c16076de33ULL, 0x832b99542253e030ULL, 0xa696ca65e284e95dULL,\n\t0xc8513f37a3fdf2eaULL, 0xedec6c06632afb87ULL, 0x1389e73b65a805e4ULL,\n\t0x3634b40aa57f0c89ULL, 0x58f34158e406173eULL, 0x7d4e126924d11e53ULL,\n\t0x857cabfc66f42050ULL, 0xa0c1f8cda623293dULL, 0xce060d9fe75a328aULL,\n\t0xebbb5eae278d3be7ULL, 0x1bde2d84a3c747e1ULL, 0x3e637eb563104e8cULL,\n\t0x50a48be72269553bULL, 0x7519d8d6e2be5c56ULL, 0x8d2b6143a09b6255ULL,\n\t0xa8963272604c6b38ULL, 0xc651c7202135708fULL, 0xe3ec9411e1e279e2ULL,\n\t0x03267244e97681eeULL, 0x269b217529a18883ULL, 0x485cd42768d89334ULL,\n\t0x6de18716a80f9a59ULL, 0x95d33e83ea2aa45aULL, 0xb06e6db22afdad37ULL,\n\t0xdea998e06b84b680ULL, 0xfb14cbd1ab53bfedULL, 0x0b71b8fb2f19c3ebULL,\n\t0x2eccebcaefceca86ULL, 0x400b1e98aeb7d131ULL, 0x65b64da96e60d85cULL,\n\t0x9d84f43c2c45e65fULL, 0xb839a70dec92ef32ULL, 0xd6fe525fadebf485ULL,\n\t0xf343016e6d3cfde8ULL, 0x176b9ef5bcc2049dULL, 0x32d6cdc47c150df0ULL,\n\t0x5c1138963d6c1647ULL, 0x79ac6ba7fdbb1f2aULL, 0x819ed232bf9e2129ULL,\n\t0xa42381037f492844ULL, 0xcae474513e3033f3ULL, 0xef592760fee73a9eULL,\n\t0x1f3c544a7aad4698ULL, 0x3a81077bba7a4ff5ULL, 0x5446f229fb035442ULL,\n\t0x71fba1183bd45d2fULL, 0x89c9188d79f1632cULL, 0xac744bbcb9266a41ULL,\n\t0xc2b3beeef85f71f6ULL, 0xe70eeddf3888789bULL, 0x07c40b8a301c8097ULL,\n\t0x227958bbf0cb89faULL, 0x4cbeade9b1b2924dULL, 0x6903fed871659b20ULL,\n\t0x9131474d3340a523ULL, 0xb48c147cf397ac4eULL, 0xda4be12eb2eeb7f9ULL,\n\t0xfff6b21f7239be94ULL, 0x0f93c135f673c292ULL, 0x2a2e920436a4cbffULL,\n\t0x44e9675677ddd048ULL, 0x61543467b70ad925ULL, 0x99668df2f52fe726ULL,\n\t0xbcdbdec335f8ee4bULL, 0xd21c2b917481f5fcULL, 0xf7a178a0b456fc91ULL,\n\t0x1a4d14a6d77c0716ULL, 0x3ff0479717ab0e7bULL, 0x5137b2c556d215ccULL,\n\t0x748ae1f496051ca1ULL, 0x8cb85861d42022a2ULL, 0xa9050b5014f72bcfULL,\n\t0xc7c2fe02558e3078ULL, 0xe27fad3395593915ULL, 0x121ade1911134513ULL,\n\t0x37a78d28d1c44c7eULL, 0x5960787a90bd57c9ULL, 0x7cdd2b4b506a5ea4ULL,\n\t0x84ef92de124f60a7ULL, 0xa152c1efd29869caULL, 0xcf9534bd93e1727dULL,\n\t0xea28678c53367b10ULL, 0x0ae281d95ba2831cULL, 0x2f5fd2e89b758a71ULL,\n\t0x419827bada0c91c6ULL, 0x6425748b1adb98abULL, 0x9c17cd1e58fea6a8ULL,\n\t0xb9aa9e2f9829afc5ULL, 0xd76d6b7dd950b472ULL, 0xf2d0384c1987bd1fULL,\n\t0x02b54b669dcdc119ULL, 0x270818575d1ac874ULL, 0x49cfed051c63d3c3ULL,\n\t0x6c72be34dcb4daaeULL, 0x944007a19e91e4adULL, 0xb1fd54905e46edc0ULL,\n\t0xdf3aa1c21f3ff677ULL, 0xfa87f2f3dfe8ff1aULL, 0x1eaf6d680e16066fULL,\n\t0x3b123e59cec10f02ULL, 0x55d5cb0b8fb814b5ULL, 0x7068983a4f6f1dd8ULL,\n\t0x885a21af0d4a23dbULL, 0xade7729ecd9d2ab6ULL, 0xc32087cc8ce43101ULL,\n\t0xe69dd4fd4c33386cULL, 0x16f8a7d7c879446aULL, 0x3345f4e608ae4d07ULL,\n\t0x5d8201b449d756b0ULL, 0x783f528589005fddULL, 0x800deb10cb2561deULL,\n\t0xa5b0b8210bf268b3ULL, 0xcb774d734a8b7304ULL, 0xeeca1e428a5c7a69ULL,\n\t0x0e00f81782c88265ULL, 0x2bbdab26421f8b08ULL, 0x457a5e74036690bfULL,\n\t0x60c70d45c3b199d2ULL, 0x98f5b4d08194a7d1ULL, 0xbd48e7e14143aebcULL,\n\t0xd38f12b3003ab50bULL, 0xf6324182c0edbc66ULL, 0x065732a844a7c060ULL,\n\t0x23ea61998470c90dULL, 0x4d2d94cbc509d2baULL, 0x6890c7fa05dedbd7ULL,\n\t0x90a27e6f47fbe5d4ULL, 0xb51f2d5e872cecb9ULL, 0xdbd8d80cc655f70eULL,\n\t0xfe658b3d0682fe63ULL\n};\n\nstatic const u_int64_t U[256] = {\n\t0x0000000000000000ULL, 0x067b86c43d6a6cb0ULL, 0x0cf70d887ad4d960ULL,\n\t0x0a8c8b4c47beb5d0ULL, 0x19ee1b10f5a9b2c0ULL, 0x1f959dd4c8c3de70ULL,\n\t0x151916988f7d6ba0ULL, 0x1362905cb2170710ULL, 0x166165102b846cedULL,\n\t0x101ae3d416ee005dULL, 0x1a9668985150b58dULL, 0x1cedee5c6c3ad93dULL,\n\t0x0f8f7e00de2dde2dULL, 0x09f4f8c4e347b29dULL, 0x03787388a4f9074dULL,\n\t0x0503f54c99936bfdULL, 0x097f991197dfd0b7ULL, 0x0f041fd5aab5bc07ULL,\n\t0x05889499ed0b09d7ULL, 0x03f3125dd0616567ULL, 0x1091820162766277ULL,\n\t0x16ea04c55f1c0ec7ULL, 0x1c668f8918a2bb17ULL, 0x1a1d094d25c8d7a7ULL,\n\t0x1f1efc01bc5bbc5aULL, 0x19657ac58131d0eaULL, 0x13e9f189c68f653aULL,\n\t0x1592774dfbe5098aULL, 0x06f0e71149f20e9aULL, 0x008b61d57498622aULL,\n\t0x0a07ea993326d7faULL, 0x0c7c6c5d0e4cbb4aULL, 0x12ff32232fbfa16eULL,\n\t0x1484b4e712d5cddeULL, 0x1e083fab556b780eULL, 0x1873b96f680114beULL,\n\t0x0b112933da1613aeULL, 0x0d6aaff7e77c7f1eULL, 0x07e624bba0c2caceULL,\n\t0x019da27f9da8a67eULL, 0x049e5733043bcd83ULL, 0x02e5d1f73951a133ULL,\n\t0x08695abb7eef14e3ULL, 0x0e12dc7f43857853ULL, 0x1d704c23f1927f43ULL,\n\t0x1b0bcae7ccf813f3ULL, 0x118741ab8b46a623ULL, 0x17fcc76fb62cca93ULL,\n\t0x1b80ab32b86071d9ULL, 0x1dfb2df6850a1d69ULL, 0x1777a6bac2b4a8b9ULL,\n\t0x110c207effdec409ULL, 0x026eb0224dc9c319ULL, 0x041536e670a3afa9ULL,\n\t0x0e99bdaa371d1a79ULL, 0x08e23b6e0a7776c9ULL, 0x0de1ce2293e41d34ULL,\n\t0x0b9a48e6ae8e7184ULL, 0x0116c3aae930c454ULL, 0x076d456ed45aa8e4ULL,\n\t0x140fd532664daff4ULL, 0x127453f65b27c344ULL, 0x18f8d8ba1c997694ULL,\n\t0x1e835e7e21f31a24ULL, 0x004337779fa84bb1ULL, 0x0638b1b3a2c22701ULL,\n\t0x0cb43affe57c92d1ULL, 0x0acfbc3bd816fe61ULL, 0x19ad2c676a01f971ULL,\n\t0x1fd6aaa3576b95c1ULL, 0x155a21ef10d52011ULL, 0x1321a72b2dbf4ca1ULL,\n\t0x16225267b42c275cULL, 0x1059d4a389464becULL, 0x1ad55fefcef8fe3cULL,\n\t0x1caed92bf392928cULL, 0x0fcc49774185959cULL, 0x09b7cfb37ceff92cULL,\n\t0x033b44ff3b514cfcULL, 0x0540c23b063b204cULL, 0x093cae6608779b06ULL,\n\t0x0f4728a2351df7b6ULL, 0x05cba3ee72a34266ULL, 0x03b0252a4fc92ed6ULL,\n\t0x10d2b576fdde29c6ULL, 0x16a933b2c0b44576ULL, 0x1c25b8fe870af0a6ULL,\n\t0x1a5e3e3aba609c16ULL, 0x1f5dcb7623f3f7ebULL, 0x19264db21e999b5bULL,\n\t0x13aac6fe59272e8bULL, 0x15d1403a644d423bULL, 0x06b3d066d65a452bULL,\n\t0x00c856a2eb30299bULL, 0x0a44ddeeac8e9c4bULL, 0x0c3f5b2a91e4f0fbULL,\n\t0x12bc0554b017eadfULL, 0x14c783908d7d866fULL, 0x1e4b08dccac333bfULL,\n\t0x18308e18f7a95f0fULL, 0x0b521e4445be581fULL, 0x0d29988078d434afULL,\n\t0x07a513cc3f6a817fULL, 0x01de95080200edcfULL, 0x04dd60449b938632ULL,\n\t0x02a6e680a6f9ea82ULL, 0x082a6dcce1475f52ULL, 0x0e51eb08dc2d33e2ULL,\n\t0x1d337b546e3a34f2ULL, 0x1b48fd9053505842ULL, 0x11c476dc14eeed92ULL,\n\t0x17bff01829848122ULL, 0x1bc39c4527c83a68ULL, 0x1db81a811aa256d8ULL,\n\t0x173491cd5d1ce308ULL, 0x114f170960768fb8ULL, 0x022d8755d26188a8ULL,\n\t0x04560191ef0be418ULL, 0x0eda8adda8b551c8ULL, 0x08a10c1995df3d78ULL,\n\t0x0da2f9550c4c5685ULL, 0x0bd97f9131263a35ULL, 0x0155f4dd76988fe5ULL,\n\t0x072e72194bf2e355ULL, 0x144ce245f9e5e445ULL, 0x12376481c48f88f5ULL,\n\t0x18bbefcd83313d25ULL, 0x1ec06909be5b5195ULL, 0x00866eef3f509762ULL,\n\t0x06fde82b023afbd2ULL, 0x0c71636745844e02ULL, 0x0a0ae5a378ee22b2ULL,\n\t0x196875ffcaf925a2ULL, 0x1f13f33bf7934912ULL, 0x159f7877b02dfcc2ULL,\n\t0x13e4feb38d479072ULL, 0x16e70bff14d4fb8fULL, 0x109c8d3b29be973fULL,\n\t0x1a1006776e0022efULL, 0x1c6b80b3536a4e5fULL, 0x0f0910efe17d494fULL,\n\t0x0972962bdc1725ffULL, 0x03fe1d679ba9902fULL, 0x05859ba3a6c3fc9fULL,\n\t0x09f9f7fea88f47d5ULL, 0x0f82713a95e52b65ULL, 0x050efa76d25b9eb5ULL,\n\t0x03757cb2ef31f205ULL, 0x1017ecee5d26f515ULL, 0x166c6a2a604c99a5ULL,\n\t0x1ce0e16627f22c75ULL, 0x1a9b67a21a9840c5ULL, 0x1f9892ee830b2b38ULL,\n\t0x19e3142abe614788ULL, 0x136f9f66f9dff258ULL, 0x151419a2c4b59ee8ULL,\n\t0x067689fe76a299f8ULL, 0x000d0f3a4bc8f548ULL, 0x0a8184760c764098ULL,\n\t0x0cfa02b2311c2c28ULL, 0x12795ccc10ef360cULL, 0x1402da082d855abcULL,\n\t0x1e8e51446a3bef6cULL, 0x18f5d780575183dcULL, 0x0b9747dce54684ccULL,\n\t0x0decc118d82ce87cULL, 0x07604a549f925dacULL, 0x011bcc90a2f8311cULL,\n\t0x041839dc3b6b5ae1ULL, 0x0263bf1806013651ULL, 0x08ef345441bf8381ULL,\n\t0x0e94b2907cd5ef31ULL, 0x1df622cccec2e821ULL, 0x1b8da408f3a88491ULL,\n\t0x11012f44b4163141ULL, 0x177aa980897c5df1ULL, 0x1b06c5dd8730e6bbULL,\n\t0x1d7d4319ba5a8a0bULL, 0x17f1c855fde43fdbULL, 0x118a4e91c08e536bULL,\n\t0x02e8decd7299547bULL, 0x049358094ff338cbULL, 0x0e1fd345084d8d1bULL,\n\t0x086455813527e1abULL, 0x0d67a0cdacb48a56ULL, 0x0b1c260991dee6e6ULL,\n\t0x0190ad45d6605336ULL, 0x07eb2b81eb0a3f86ULL, 0x1489bbdd591d3896ULL,\n\t0x12f23d1964775426ULL, 0x187eb65523c9e1f6ULL, 0x1e0530911ea38d46ULL,\n\t0x00c55998a0f8dcd3ULL, 0x06bedf5c9d92b063ULL, 0x0c325410da2c05b3ULL,\n\t0x0a49d2d4e7466903ULL, 0x192b428855516e13ULL, 0x1f50c44c683b02a3ULL,\n\t0x15dc4f002f85b773ULL, 0x13a7c9c412efdbc3ULL, 0x16a43c888b7cb03eULL,\n\t0x10dfba4cb616dc8eULL, 0x1a533100f1a8695eULL, 0x1c28b7c4ccc205eeULL,\n\t0x0f4a27987ed502feULL, 0x0931a15c43bf6e4eULL, 0x03bd2a100401db9eULL,\n\t0x05c6acd4396bb72eULL, 0x09bac08937270c64ULL, 0x0fc1464d0a4d60d4ULL,\n\t0x054dcd014df3d504ULL, 0x03364bc57099b9b4ULL, 0x1054db99c28ebea4ULL,\n\t0x162f5d5dffe4d214ULL, 0x1ca3d611b85a67c4ULL, 0x1ad850d585300b74ULL,\n\t0x1fdba5991ca36089ULL, 0x19a0235d21c90c39ULL, 0x132ca8116677b9e9ULL,\n\t0x15572ed55b1dd559ULL, 0x0635be89e90ad249ULL, 0x004e384dd460bef9ULL,\n\t0x0ac2b30193de0b29ULL, 0x0cb935c5aeb46799ULL, 0x123a6bbb8f477dbdULL,\n\t0x1441ed7fb22d110dULL, 0x1ecd6633f593a4ddULL, 0x18b6e0f7c8f9c86dULL,\n\t0x0bd470ab7aeecf7dULL, 0x0daff66f4784a3cdULL, 0x07237d23003a161dULL,\n\t0x0158fbe73d507aadULL, 0x045b0eaba4c31150ULL, 0x0220886f99a97de0ULL,\n\t0x08ac0323de17c830ULL, 0x0ed785e7e37da480ULL, 0x1db515bb516aa390ULL,\n\t0x1bce937f6c00cf20ULL, 0x114218332bbe7af0ULL, 0x17399ef716d41640ULL,\n\t0x1b45f2aa1898ad0aULL, 0x1d3e746e25f2c1baULL, 0x17b2ff22624c746aULL,\n\t0x11c979e65f2618daULL, 0x02abe9baed311fcaULL, 0x04d06f7ed05b737aULL,\n\t0x0e5ce43297e5c6aaULL, 0x082762f6aa8faa1aULL, 0x0d2497ba331cc1e7ULL,\n\t0x0b5f117e0e76ad57ULL, 0x01d39a3249c81887ULL, 0x07a81cf674a27437ULL,\n\t0x14ca8caac6b57327ULL, 0x12b10a6efbdf1f97ULL, 0x183d8122bc61aa47ULL,\n\t0x1e4607e6810bc6f7ULL\n};\n\n#else\t/* the original ones */\n\n#define RABIN_WINDOW_SIZE 22\n#define RABIN_SHIFT 55\n\nstatic const u_int64_t T[256] = {\n\t0x0000000000000000ULL, 0xb15e234bd3792f63ULL, 0x62bc4697a6f25ec6ULL,\n\t0xd3e265dc758b71a5ULL, 0x7426ae649e9d92efULL, 0xc5788d2f4de4bd8cULL,\n\t0x169ae8f3386fcc29ULL, 0xa7c4cbb8eb16e34aULL, 0x59137f82ee420abdULL,\n\t0xe84d5cc93d3b25deULL, 0x3baf391548b0547bULL, 0x8af11a5e9bc97b18ULL,\n\t0x2d35d1e670df9852ULL, 0x9c6bf2ada3a6b731ULL, 0x4f899771d62dc694ULL,\n\t0xfed7b43a0554e9f7ULL, 0x0378dc4e0ffd3a19ULL, 0xb226ff05dc84157aULL,\n\t0x61c49ad9a90f64dfULL, 0xd09ab9927a764bbcULL, 0x775e722a9160a8f6ULL,\n\t0xc600516142198795ULL, 0x15e234bd3792f630ULL, 0xa4bc17f6e4ebd953ULL,\n\t0x5a6ba3cce1bf30a4ULL, 0xeb35808732c61fc7ULL, 0x38d7e55b474d6e62ULL,\n\t0x8989c61094344101ULL, 0x2e4d0da87f22a24bULL, 0x9f132ee3ac5b8d28ULL,\n\t0x4cf14b3fd9d0fc8dULL, 0xfdaf68740aa9d3eeULL, 0x06f1b89c1ffa7432ULL,\n\t0xb7af9bd7cc835b51ULL, 0x644dfe0bb9082af4ULL, 0xd513dd406a710597ULL,\n\t0x72d716f88167e6ddULL, 0xc38935b3521ec9beULL, 0x106b506f2795b81bULL,\n\t0xa1357324f4ec9778ULL, 0x5fe2c71ef1b87e8fULL, 0xeebce45522c151ecULL,\n\t0x3d5e8189574a2049ULL, 0x8c00a2c284330f2aULL, 0x2bc4697a6f25ec60ULL,\n\t0x9a9a4a31bc5cc303ULL, 0x49782fedc9d7b2a6ULL, 0xf8260ca61aae9dc5ULL,\n\t0x058964d210074e2bULL, 0xb4d74799c37e6148ULL, 0x67352245b6f510edULL,\n\t0xd66b010e658c3f8eULL, 0x71afcab68e9adcc4ULL, 0xc0f1e9fd5de3f3a7ULL,\n\t0x13138c2128688202ULL, 0xa24daf6afb11ad61ULL, 0x5c9a1b50fe454496ULL,\n\t0xedc4381b2d3c6bf5ULL, 0x3e265dc758b71a50ULL, 0x8f787e8c8bce3533ULL,\n\t0x28bcb53460d8d679ULL, 0x99e2967fb3a1f91aULL, 0x4a00f3a3c62a88bfULL,\n\t0xfb5ed0e81553a7dcULL, 0x0de371383ff4e864ULL, 0xbcbd5273ec8dc707ULL,\n\t0x6f5f37af9906b6a2ULL, 0xde0114e44a7f99c1ULL, 0x79c5df5ca1697a8bULL,\n\t0xc89bfc17721055e8ULL, 0x1b7999cb079b244dULL, 0xaa27ba80d4e20b2eULL,\n\t0x54f00ebad1b6e2d9ULL, 0xe5ae2df102cfcdbaULL, 0x364c482d7744bc1fULL,\n\t0x87126b66a43d937cULL, 0x20d6a0de4f2b7036ULL, 0x918883959c525f55ULL,\n\t0x426ae649e9d92ef0ULL, 0xf334c5023aa00193ULL, 0x0e9bad763009d27dULL,\n\t0xbfc58e3de370fd1eULL, 0x6c27ebe196fb8cbbULL, 0xdd79c8aa4582a3d8ULL,\n\t0x7abd0312ae944092ULL, 0xcbe320597ded6ff1ULL, 0x1801458508661e54ULL,\n\t0xa95f66cedb1f3137ULL, 0x5788d2f4de4bd8c0ULL, 0xe6d6f1bf0d32f7a3ULL,\n\t0x3534946378b98606ULL, 0x846ab728abc0a965ULL, 0x23ae7c9040d64a2fULL,\n\t0x92f05fdb93af654cULL, 0x41123a07e62414e9ULL, 0xf04c194c355d3b8aULL,\n\t0x0b12c9a4200e9c56ULL, 0xba4ceaeff377b335ULL, 0x69ae8f3386fcc290ULL,\n\t0xd8f0ac785585edf3ULL, 0x7f3467c0be930eb9ULL, 0xce6a448b6dea21daULL,\n\t0x1d8821571861507fULL, 0xacd6021ccb187f1cULL, 0x5201b626ce4c96ebULL,\n\t0xe35f956d1d35b988ULL, 0x30bdf0b168bec82dULL, 0x81e3d3fabbc7e74eULL,\n\t0x2627184250d10404ULL, 0x97793b0983a82b67ULL, 0x449b5ed5f6235ac2ULL,\n\t0xf5c57d9e255a75a1ULL, 0x086a15ea2ff3a64fULL, 0xb93436a1fc8a892cULL,\n\t0x6ad6537d8901f889ULL, 0xdb8870365a78d7eaULL, 0x7c4cbb8eb16e34a0ULL,\n\t0xcd1298c562171bc3ULL, 0x1ef0fd19179c6a66ULL, 0xafaede52c4e54505ULL,\n\t0x51796a68c1b1acf2ULL, 0xe027492312c88391ULL, 0x33c52cff6743f234ULL,\n\t0x829b0fb4b43add57ULL, 0x255fc40c5f2c3e1dULL, 0x9401e7478c55117eULL,\n\t0x47e3829bf9de60dbULL, 0xf6bda1d02aa74fb8ULL, 0x1bc6e2707fe9d0c8ULL,\n\t0xaa98c13bac90ffabULL, 0x797aa4e7d91b8e0eULL, 0xc82487ac0a62a16dULL,\n\t0x6fe04c14e1744227ULL, 0xdebe6f5f320d6d44ULL, 0x0d5c0a8347861ce1ULL,\n\t0xbc0229c894ff3382ULL, 0x42d59df291abda75ULL, 0xf38bbeb942d2f516ULL,\n\t0x2069db65375984b3ULL, 0x9137f82ee420abd0ULL, 0x36f333960f36489aULL,\n\t0x87ad10dddc4f67f9ULL, 0x544f7501a9c4165cULL, 0xe511564a7abd393fULL,\n\t0x18be3e3e7014ead1ULL, 0xa9e01d75a36dc5b2ULL, 0x7a0278a9d6e6b417ULL,\n\t0xcb5c5be2059f9b74ULL, 0x6c98905aee89783eULL, 0xddc6b3113df0575dULL,\n\t0x0e24d6cd487b26f8ULL, 0xbf7af5869b02099bULL, 0x41ad41bc9e56e06cULL,\n\t0xf0f362f74d2fcf0fULL, 0x2311072b38a4beaaULL, 0x924f2460ebdd91c9ULL,\n\t0x358befd800cb7283ULL, 0x84d5cc93d3b25de0ULL, 0x5737a94fa6392c45ULL,\n\t0xe6698a0475400326ULL, 0x1d375aec6013a4faULL, 0xac6979a7b36a8b99ULL,\n\t0x7f8b1c7bc6e1fa3cULL, 0xced53f301598d55fULL, 0x6911f488fe8e3615ULL,\n\t0xd84fd7c32df71976ULL, 0x0badb21f587c68d3ULL, 0xbaf391548b0547b0ULL,\n\t0x4424256e8e51ae47ULL, 0xf57a06255d288124ULL, 0x269863f928a3f081ULL,\n\t0x97c640b2fbdadfe2ULL, 0x30028b0a10cc3ca8ULL, 0x815ca841c3b513cbULL,\n\t0x52becd9db63e626eULL, 0xe3e0eed665474d0dULL, 0x1e4f86a26fee9ee3ULL,\n\t0xaf11a5e9bc97b180ULL, 0x7cf3c035c91cc025ULL, 0xcdade37e1a65ef46ULL,\n\t0x6a6928c6f1730c0cULL, 0xdb370b8d220a236fULL, 0x08d56e51578152caULL,\n\t0xb98b4d1a84f87da9ULL, 0x475cf92081ac945eULL, 0xf602da6b52d5bb3dULL,\n\t0x25e0bfb7275eca98ULL, 0x94be9cfcf427e5fbULL, 0x337a57441f3106b1ULL,\n\t0x8224740fcc4829d2ULL, 0x51c611d3b9c35877ULL, 0xe09832986aba7714ULL,\n\t0x16259348401d38acULL, 0xa77bb003936417cfULL, 0x7499d5dfe6ef666aULL,\n\t0xc5c7f69435964909ULL, 0x62033d2cde80aa43ULL, 0xd35d1e670df98520ULL,\n\t0x00bf7bbb7872f485ULL, 0xb1e158f0ab0bdbe6ULL, 0x4f36eccaae5f3211ULL,\n\t0xfe68cf817d261d72ULL, 0x2d8aaa5d08ad6cd7ULL, 0x9cd48916dbd443b4ULL,\n\t0x3b1042ae30c2a0feULL, 0x8a4e61e5e3bb8f9dULL, 0x59ac04399630fe38ULL,\n\t0xe8f227724549d15bULL, 0x155d4f064fe002b5ULL, 0xa4036c4d9c992dd6ULL,\n\t0x77e10991e9125c73ULL, 0xc6bf2ada3a6b7310ULL, 0x617be162d17d905aULL,\n\t0xd025c2290204bf39ULL, 0x03c7a7f5778fce9cULL, 0xb29984bea4f6e1ffULL,\n\t0x4c4e3084a1a20808ULL, 0xfd1013cf72db276bULL, 0x2ef27613075056ceULL,\n\t0x9fac5558d42979adULL, 0x38689ee03f3f9ae7ULL, 0x8936bdabec46b584ULL,\n\t0x5ad4d87799cdc421ULL, 0xeb8afb3c4ab4eb42ULL, 0x10d42bd45fe74c9eULL,\n\t0xa18a089f8c9e63fdULL, 0x72686d43f9151258ULL, 0xc3364e082a6c3d3bULL,\n\t0x64f285b0c17ade71ULL, 0xd5aca6fb1203f112ULL, 0x064ec327678880b7ULL,\n\t0xb710e06cb4f1afd4ULL, 0x49c75456b1a54623ULL, 0xf899771d62dc6940ULL,\n\t0x2b7b12c1175718e5ULL, 0x9a25318ac42e3786ULL, 0x3de1fa322f38d4ccULL,\n\t0x8cbfd979fc41fbafULL, 0x5f5dbca589ca8a0aULL, 0xee039fee5ab3a569ULL,\n\t0x13acf79a501a7687ULL, 0xa2f2d4d1836359e4ULL, 0x7110b10df6e82841ULL,\n\t0xc04e924625910722ULL, 0x678a59fece87e468ULL, 0xd6d47ab51dfecb0bULL,\n\t0x05361f696875baaeULL, 0xb4683c22bb0c95cdULL, 0x4abf8818be587c3aULL,\n\t0xfbe1ab536d215359ULL, 0x2803ce8f18aa22fcULL, 0x995dedc4cbd30d9fULL,\n\t0x3e99267c20c5eed5ULL, 0x8fc70537f3bcc1b6ULL, 0x5c2560eb8637b013ULL,\n\t0xed7b43a0554e9f70ULL\n};\n\nstatic const u_int64_t U[256] = {\n\t0x0000000000000000ULL, 0x079343d61ab9f60eULL, 0x0f2687ac3573ec1cULL,\n\t0x08b5c47a2fca1a12ULL, 0x1e4d0f586ae7d838ULL, 0x19de4c8e705e2e36ULL,\n\t0x116b88f45f943424ULL, 0x16f8cb22452dc22aULL, 0x3c9a1eb0d5cfb070ULL,\n\t0x3b095d66cf76467eULL, 0x33bc991ce0bc5c6cULL, 0x342fdacafa05aa62ULL,\n\t0x22d711e8bf286848ULL, 0x2544523ea5919e46ULL, 0x2df196448a5b8454ULL,\n\t0x2a62d59290e2725aULL, 0x79343d61ab9f60e0ULL, 0x7ea77eb7b12696eeULL,\n\t0x7612bacd9eec8cfcULL, 0x7181f91b84557af2ULL, 0x67793239c178b8d8ULL,\n\t0x60ea71efdbc14ed6ULL, 0x685fb595f40b54c4ULL, 0x6fccf643eeb2a2caULL,\n\t0x45ae23d17e50d090ULL, 0x423d600764e9269eULL, 0x4a88a47d4b233c8cULL,\n\t0x4d1be7ab519aca82ULL, 0x5be32c8914b708a8ULL, 0x5c706f5f0e0efea6ULL,\n\t0x54c5ab2521c4e4b4ULL, 0x5356e8f33b7d12baULL, 0x433659888447eea3ULL,\n\t0x44a51a5e9efe18adULL, 0x4c10de24b13402bfULL, 0x4b839df2ab8df4b1ULL,\n\t0x5d7b56d0eea0369bULL, 0x5ae81506f419c095ULL, 0x525dd17cdbd3da87ULL,\n\t0x55ce92aac16a2c89ULL, 0x7fac473851885ed3ULL, 0x783f04ee4b31a8ddULL,\n\t0x708ac09464fbb2cfULL, 0x771983427e4244c1ULL, 0x61e148603b6f86ebULL,\n\t0x66720bb621d670e5ULL, 0x6ec7cfcc0e1c6af7ULL, 0x69548c1a14a59cf9ULL,\n\t0x3a0264e92fd88e43ULL, 0x3d91273f3561784dULL, 0x3524e3451aab625fULL,\n\t0x32b7a09300129451ULL, 0x244f6bb1453f567bULL, 0x23dc28675f86a075ULL,\n\t0x2b69ec1d704cba67ULL, 0x2cfaafcb6af54c69ULL, 0x06987a59fa173e33ULL,\n\t0x010b398fe0aec83dULL, 0x09befdf5cf64d22fULL, 0x0e2dbe23d5dd2421ULL,\n\t0x18d5750190f0e60bULL, 0x1f4636d78a491005ULL, 0x17f3f2ada5830a17ULL,\n\t0x1060b17bbf3afc19ULL, 0x3732905adbf6f225ULL, 0x30a1d38cc14f042bULL,\n\t0x381417f6ee851e39ULL, 0x3f875420f43ce837ULL, 0x297f9f02b1112a1dULL,\n\t0x2eecdcd4aba8dc13ULL, 0x265918ae8462c601ULL, 0x21ca5b789edb300fULL,\n\t0x0ba88eea0e394255ULL, 0x0c3bcd3c1480b45bULL, 0x048e09463b4aae49ULL,\n\t0x031d4a9021f35847ULL, 0x15e581b264de9a6dULL, 0x1276c2647e676c63ULL,\n\t0x1ac3061e51ad7671ULL, 0x1d5045c84b14807fULL, 0x4e06ad3b706992c5ULL,\n\t0x4995eeed6ad064cbULL, 0x41202a97451a7ed9ULL, 0x46b369415fa388d7ULL,\n\t0x504ba2631a8e4afdULL, 0x57d8e1b50037bcf3ULL, 0x5f6d25cf2ffda6e1ULL,\n\t0x58fe6619354450efULL, 0x729cb38ba5a622b5ULL, 0x750ff05dbf1fd4bbULL,\n\t0x7dba342790d5cea9ULL, 0x7a2977f18a6c38a7ULL, 0x6cd1bcd3cf41fa8dULL,\n\t0x6b42ff05d5f80c83ULL, 0x63f73b7ffa321691ULL, 0x646478a9e08be09fULL,\n\t0x7404c9d25fb11c86ULL, 0x73978a044508ea88ULL, 0x7b224e7e6ac2f09aULL,\n\t0x7cb10da8707b0694ULL, 0x6a49c68a3556c4beULL, 0x6dda855c2fef32b0ULL,\n\t0x656f4126002528a2ULL, 0x62fc02f01a9cdeacULL, 0x489ed7628a7eacf6ULL,\n\t0x4f0d94b490c75af8ULL, 0x47b850cebf0d40eaULL, 0x402b1318a5b4b6e4ULL,\n\t0x56d3d83ae09974ceULL, 0x51409becfa2082c0ULL, 0x59f55f96d5ea98d2ULL,\n\t0x5e661c40cf536edcULL, 0x0d30f4b3f42e7c66ULL, 0x0aa3b765ee978a68ULL,\n\t0x0216731fc15d907aULL, 0x058530c9dbe46674ULL, 0x137dfbeb9ec9a45eULL,\n\t0x14eeb83d84705250ULL, 0x1c5b7c47abba4842ULL, 0x1bc83f91b103be4cULL,\n\t0x31aaea0321e1cc16ULL, 0x3639a9d53b583a18ULL, 0x3e8c6daf1492200aULL,\n\t0x391f2e790e2bd604ULL, 0x2fe7e55b4b06142eULL, 0x2874a68d51bfe220ULL,\n\t0x20c162f77e75f832ULL, 0x2752212164cc0e3cULL, 0x6e6520b5b7ede44aULL,\n\t0x69f66363ad541244ULL, 0x6143a719829e0856ULL, 0x66d0e4cf9827fe58ULL,\n\t0x70282feddd0a3c72ULL, 0x77bb6c3bc7b3ca7cULL, 0x7f0ea841e879d06eULL,\n\t0x789deb97f2c02660ULL, 0x52ff3e056222543aULL, 0x556c7dd3789ba234ULL,\n\t0x5dd9b9a95751b826ULL, 0x5a4afa7f4de84e28ULL, 0x4cb2315d08c58c02ULL,\n\t0x4b21728b127c7a0cULL, 0x4394b6f13db6601eULL, 0x4407f527270f9610ULL,\n\t0x17511dd41c7284aaULL, 0x10c25e0206cb72a4ULL, 0x18779a78290168b6ULL,\n\t0x1fe4d9ae33b89eb8ULL, 0x091c128c76955c92ULL, 0x0e8f515a6c2caa9cULL,\n\t0x063a952043e6b08eULL, 0x01a9d6f6595f4680ULL, 0x2bcb0364c9bd34daULL,\n\t0x2c5840b2d304c2d4ULL, 0x24ed84c8fcced8c6ULL, 0x237ec71ee6772ec8ULL,\n\t0x35860c3ca35aece2ULL, 0x32154feab9e31aecULL, 0x3aa08b90962900feULL,\n\t0x3d33c8468c90f6f0ULL, 0x2d53793d33aa0ae9ULL, 0x2ac03aeb2913fce7ULL,\n\t0x2275fe9106d9e6f5ULL, 0x25e6bd471c6010fbULL, 0x331e7665594dd2d1ULL,\n\t0x348d35b343f424dfULL, 0x3c38f1c96c3e3ecdULL, 0x3babb21f7687c8c3ULL,\n\t0x11c9678de665ba99ULL, 0x165a245bfcdc4c97ULL, 0x1eefe021d3165685ULL,\n\t0x197ca3f7c9afa08bULL, 0x0f8468d58c8262a1ULL, 0x08172b03963b94afULL,\n\t0x00a2ef79b9f18ebdULL, 0x0731acafa34878b3ULL, 0x5467445c98356a09ULL,\n\t0x53f4078a828c9c07ULL, 0x5b41c3f0ad468615ULL, 0x5cd28026b7ff701bULL,\n\t0x4a2a4b04f2d2b231ULL, 0x4db908d2e86b443fULL, 0x450ccca8c7a15e2dULL,\n\t0x429f8f7edd18a823ULL, 0x68fd5aec4dfada79ULL, 0x6f6e193a57432c77ULL,\n\t0x67dbdd4078893665ULL, 0x60489e966230c06bULL, 0x76b055b4271d0241ULL,\n\t0x712316623da4f44fULL, 0x7996d218126eee5dULL, 0x7e0591ce08d71853ULL,\n\t0x5957b0ef6c1b166fULL, 0x5ec4f33976a2e061ULL, 0x567137435968fa73ULL,\n\t0x51e2749543d10c7dULL, 0x471abfb706fcce57ULL, 0x4089fc611c453859ULL,\n\t0x483c381b338f224bULL, 0x4faf7bcd2936d445ULL, 0x65cdae5fb9d4a61fULL,\n\t0x625eed89a36d5011ULL, 0x6aeb29f38ca74a03ULL, 0x6d786a25961ebc0dULL,\n\t0x7b80a107d3337e27ULL, 0x7c13e2d1c98a8829ULL, 0x74a626abe640923bULL,\n\t0x7335657dfcf96435ULL, 0x20638d8ec784768fULL, 0x27f0ce58dd3d8081ULL,\n\t0x2f450a22f2f79a93ULL, 0x28d649f4e84e6c9dULL, 0x3e2e82d6ad63aeb7ULL,\n\t0x39bdc100b7da58b9ULL, 0x3108057a981042abULL, 0x369b46ac82a9b4a5ULL,\n\t0x1cf9933e124bc6ffULL, 0x1b6ad0e808f230f1ULL, 0x13df149227382ae3ULL,\n\t0x144c57443d81dcedULL, 0x02b49c6678ac1ec7ULL, 0x0527dfb06215e8c9ULL,\n\t0x0d921bca4ddff2dbULL, 0x0a01581c576604d5ULL, 0x1a61e967e85cf8ccULL,\n\t0x1df2aab1f2e50ec2ULL, 0x15476ecbdd2f14d0ULL, 0x12d42d1dc796e2deULL,\n\t0x042ce63f82bb20f4ULL, 0x03bfa5e99802d6faULL, 0x0b0a6193b7c8cce8ULL,\n\t0x0c992245ad713ae6ULL, 0x26fbf7d73d9348bcULL, 0x2168b401272abeb2ULL,\n\t0x29dd707b08e0a4a0ULL, 0x2e4e33ad125952aeULL, 0x38b6f88f57749084ULL,\n\t0x3f25bb594dcd668aULL, 0x37907f2362077c98ULL, 0x30033cf578be8a96ULL,\n\t0x6355d40643c3982cULL, 0x64c697d0597a6e22ULL, 0x6c7353aa76b07430ULL,\n\t0x6be0107c6c09823eULL, 0x7d18db5e29244014ULL, 0x7a8b9888339db61aULL,\n\t0x723e5cf21c57ac08ULL, 0x75ad1f2406ee5a06ULL, 0x5fcfcab6960c285cULL,\n\t0x585c89608cb5de52ULL, 0x50e94d1aa37fc440ULL, 0x577a0eccb9c6324eULL,\n\t0x4182c5eefcebf064ULL, 0x46118638e652066aULL, 0x4ea44242c9981c78ULL,\n\t0x49370194d321ea76ULL\n};\n\n#endif\n\nstatic unsigned char rabin_window[RABIN_WINDOW_SIZE];\nstatic unsigned rabin_pos = 0;\n\n#define MIN(x,y) ((y)<(x) ? (y) : (x))\n#define MAX(x,y) ((y)>(x) ? (y) : (x))\n\n/*\n * The copies array is the central data structure for diff generation.\n * Data statements are implicit, for ranges not covered by any copy command.\n *\n * The sum of tgt and length for each entry must be monotonically increasing,\n * and data ranges must be non-overlapping. This is accomplished by not\n * extending matches backwards during initial matching.\n *\n * Copies may have zero length, to make it quick to delete copies during\n * optimization. However, the last copy in the list must always be a\n * non-trivial copy.\n *\n * Before committing copies, an important optimization is performed: during \n * a backward pass through the copies array, each entry is extended backwards,\n * and redundant copies are eliminated.\n *\n * If each match were extended backwards on insertion, the same data may be\n * matched an arbitrary number of times, resulting in potentially quadratic\n * time behavior.\n */\n\ntypedef struct copyinfo {\n\tunsigned src;\n\tunsigned tgt;\n\tunsigned length;\n} CopyInfo;\n\nstatic CopyInfo *copies;\nstatic int copy_count = 0;\nstatic unsigned max_copies = 0; /* Dynamically increased */\n\nstatic unsigned *idx;\nstatic unsigned idx_size;\nstatic unsigned char *idx_data;\nstatic unsigned idx_data_len;\n\nstatic void rabin_reset(void)\n{\n\tmemset(rabin_window, 0, sizeof(rabin_window));\n}\n\nstatic u_int64_t rabin_slide (u_int64_t fp, unsigned char m)\n{\n\tunsigned char om;\n\tif (++rabin_pos == RABIN_WINDOW_SIZE) rabin_pos = 0;\n\tom = rabin_window[rabin_pos];\n\tfp ^= U[om];\n\trabin_window[rabin_pos] = m;\n\tfp = ((fp << 8) | m) ^ T[fp >> RABIN_SHIFT];\n\treturn fp;\n}\n\nstatic void init_idx (unsigned char *data, size_t len, int level)\n{\n\tunsigned index_step = RABIN_WINDOW_SIZE / sizeof(unsigned) * sizeof(unsigned);\n\tsize_t j, k;\n\tunsigned char ch = 0;\n\tunsigned maxofs[256];\n\tunsigned maxlen[256];\n\tunsigned maxfp[256];\n\tunsigned runlen = 0;\n\tu_int64_t fp = 0;\n\n\tassert (len <= MAX_SIZE);\n\tassert (level >= 0 && level <= 9);\n\tmemset(maxofs, 0, sizeof(maxofs));\n\tmemset(maxlen, 0, sizeof(maxlen));\n\tmemset(maxfp, 0, sizeof(maxfp));\n\n\t/* index_step must be multiple of word size */\n\tif (level >= 1)\n\t\tindex_step = MIN(index_step, 4 * sizeof(unsigned));\n\t/* Use smaller step size for higher optimization levels or smaller files */\n\tif (level >= 3 || len <= 65536)\n\t\tindex_step = MIN (index_step, 3 * sizeof (unsigned));\n\tif (level >= 4 || len <= 32768)\n\t\tindex_step = MIN (index_step, 2 * sizeof (unsigned));\n\tif (level >= 6 || len < 16384)\n\t\tindex_step = MIN (index_step, 1 * sizeof (unsigned));\n\tassert (index_step && !(index_step % sizeof (unsigned)));\n\n\t/* Add fixed amount to hash table size, as small files will benefit\n\t a lot without using significantly more memory or time. */\n\tidx_size = (level + 1) * (len / index_step) / 2 + MIN_HTAB_SIZE;\n\tidx_size = MIN (idx_size, MAX_HTAB_SIZE - 1); /* So rounding up works */\n\n\t/* Round up to next power of two, but limit to MAX_HTAB_SIZE. */\n\t{\n\t\tunsigned s = MIN_HTAB_SIZE;\n\t\twhile (s < idx_size) s += s;\n\t\tidx_size = s;\n\t}\n\n\tidx_data = data;\n\tidx_data_len = len;\n\tidx = calloc(idx_size, sizeof(unsigned)); \n\n\t/* It is tempting to first index higher addresses, so hashes of lower\n\t addresses will get preference in the hash table. However, for\n\t repetitive patterns with a period that is a divisor of the fingerprint\n\t window, this may mean the match is not anchored at the end. \n\t Furthermore, even when using a window length that is prime, the\n\t benefits are small and the irregularity of the first matches being\n\t more important is not worth it. */\n\n\trabin_reset();\n\n\tch = 0;\n\trunlen = 0;\n\n\tfor (j = 0; j + index_step < len; j += index_step) {\n\t\tunsigned char pch = 0;\n\t\tunsigned hash;\n\n\t\tfor (k = 0; k < index_step; k++) {\n\t\t\tpch = ch;\n\t\t\tch = data[j + k];\n\t\t\tif (ch != pch)\n\t\t\t\trunlen = 0;\n\t\t\trunlen++;\n\t\t\tfp = rabin_slide(fp, ch);\n\t\t}\n\n\t\t/* See if there is a word-aligned window-sized run of equal characters */\n\t\tif (runlen >= RABIN_WINDOW_SIZE + sizeof(unsigned) - 1) {\n\t\t\t/* Skip ahead to end of run of identical input characters */\n\t\t\twhile (j + k < len && data[j + k] == ch) {\n\t\t\t\tk++;\n\t\t\t\trunlen++;\n\t\t\t}\n\n\t\t\t/* Although matches are usually anchored at the end, in the case\n\t\t\t of extended runs of equal characters it is better to anchor after the\n\t\t\t first RABIN_WINDOW_SIZE bytes. This allows for quick skip ahead \n\t\t\t while matching such runs, avoiding unneeded fingerprint calculations.\n\t\t\t Also, when anchoring at the end, matches will be generated after\n\t\t\t every word, because the fingerprint stays constant. Even though\n\t\t\t all matches would get combined during match optimization, \n\t\t\t it wastes time and space. */\n\t\t\tif (runlen > maxlen[pch] + 4) {\n\t\t\t\tunsigned ofs;\n\t\t\t\t/* ofs points RABIN_WINDOW_SIZE bytes after the start of the run,\n\t\t\t\t rounded up to the next word */\n\t\t\t\tofs = j + k - runlen + RABIN_WINDOW_SIZE + (sizeof (unsigned) - 1);\n\t\t\t\tofs -= ofs % sizeof(unsigned);\n\t\t\t\tmaxofs[pch] = ofs;\n\t\t\t\tmaxlen [pch] = runlen;\n\t\t\t\tassert(maxfp[pch] == 0 || maxfp[pch] == (unsigned)fp);\n\t\t\t\tmaxfp[pch] = (unsigned)fp;\n\t\t\t}\n\t\t\t/* Keep input aligned as if no special run processing had taken place */\n\t\t\tj += k - (k % index_step) - index_step;\n\t\t\tk = index_step;\n\t\t}\n\n\t\t/* Testing showed that avoiding collisions using secondary hashing, or\n\t\t hash chaining had little effect and is not worth the time. */\n\t\thash = ((unsigned)fp) & (idx_size - 1);\n\t\tidx[hash] = j + k;\n\t}\n\n\t/* Lastly, index the longest runs of equal characters found before.\n\t This ensures we always match the longerst such runs available. */\n\tfor (j = 0; j < 256; j++) \n\t\tif (maxlen[j]) \n\t\t\tidx[maxfp[j] % idx_size] = maxofs[j];\n}\n\n/* Match data against the current index and record all possible copies */\nstatic int find_copies(unsigned char *data, size_t len)\n{\n\tsize_t j = 0;\n\tu_int64_t fp = 0;\n\n\trabin_reset();\n\n\twhile (j < RABIN_WINDOW_SIZE && j < len)\n\t\tfp = rabin_slide(fp, data[j++]);\n\n\twhile (j < len) { \n\t\tunsigned hash, ofs, src, tgt, runlen, maxrun;\n\n\t\tfp = rabin_slide(fp, data[j++]);\n\t\thash = fp & (idx_size - 1);\n\t\tofs = idx[hash];\n\n\t\t/* Invariant:\n\t\t data[0] .. data[j-1] has been processed\n\t\t fp is fingerprint of sliding window ending at j-1\n\t\t ofs is zero or points just past tentative match\n\t\t ofs is a multiple of index_step */\n\n\t\tif (!ofs)\n\t\t\tcontinue;\n\n\t\trunlen = 0;\n\t\ttgt = j - 4;\n\t\tsrc = ofs - 4;\n\t\tmaxrun = MIN(idx_data_len - src, len - tgt);\n\n\t\t/* Hot loop */\n\t\twhile (runlen < maxrun &&\n\t\t data[tgt + runlen] == idx_data[src + runlen])\n\t\t\trunlen++;\n\t\tif (runlen < 4)\n\t\t\tcontinue;\n\n\t\tif (copy_count == max_copies) {\n\t\t\tmax_copies *= 2;\n\t\t\tif (!copies) {\n\t\t\t\tmax_copies = MAX_COPIES;\n\t\t\t\tcopies = malloc(max_copies * sizeof(CopyInfo));\n\t\t\t} else {\n\t\t\t\tcopies = realloc(copies, max_copies * sizeof (CopyInfo));\n\t\t\t}\n\t\t\tif (!copies)\n\t\t\t\treturn 0;\n\t\t}\n\n\t\tcopies[copy_count].src = src;\n\t\tcopies[copy_count].tgt = tgt;\n\t\tcopies[copy_count].length = runlen;\n\t\tcopy_count++;\n\n\t\t/* For runs extending more than RABIN_WINDOW_SIZE bytes beyond j,\n\t\t skip ahead to prevent useless fingerprint computations. */\n\t\tif (tgt + runlen > j + RABIN_WINDOW_SIZE)\n\t\t\tj = tgt + runlen - RABIN_WINDOW_SIZE;\n\n\t\t/* Quickly scan ahead without looking for matches\n\t\t until the end of this run */\n\t\twhile (j < tgt + runlen)\n\t\t\tfp = rabin_slide(fp, data[j++]);\n\t}\n\n\treturn 1;\n}\n\nstatic unsigned header_length(unsigned srclen, unsigned tgtlen)\n{\n\tunsigned len = 0;\n\tassert (srclen <= MAX_SIZE && tgtlen <= MAX_SIZE);\n\n\t/* GIT headers start with the length of the source and target,\n\t with 7 bits per byte, least significant byte first, and\n\t the high bit indicating continuation. */\n\tdo { len++; srclen >>= 7; } while (srclen);\n\tdo { len++; tgtlen >>= 7; } while (tgtlen);\n\n\treturn len;\n}\n\nstatic unsigned char *write_header(unsigned char *patch, unsigned srclen, unsigned tgtlen)\n{\n\tassert (srclen <= MAX_SIZE && tgtlen <= MAX_SIZE);\n\n\twhile (srclen >= 0x80) {\n\t\t*patch++ = srclen | 0x80;\n\t\tsrclen >>= 7;\n\t}\n\t*patch++ = srclen;\n\n\twhile (tgtlen >= 0x80) {\n\t\t*patch++ = tgtlen | 0x80;\n\t\ttgtlen >>= 7;\n\t}\n\t*patch++ = tgtlen;\n\n\treturn patch;\n}\n\nstatic unsigned data_length(unsigned length)\n{\n\t/* Can only include 0x7f data bytes per command */\n\tunsigned partial = length % 0x7f;\n\tassert (length > 0 && length <= MAX_SIZE);\n\tif (partial) partial++;\n\treturn partial + (length / 0x7f) * 0x80;\n}\n\nstatic unsigned char *write_data(unsigned char *patch, unsigned char *data, unsigned size)\n{\n\tassert (size > 0 && size < MAX_SIZE);\n\t/* The return value must be equal to patch + data_length (patch, size).\n\t This correspondence is essential for calculating the patch size. */\n\n\t/* GIT has no data commands for large data, rest is same as GDIFF */\n\tdo {\n\t\tunsigned s = size;\n\t\tif (s > 0x7f)\n\t\t\ts = 0x7f;\n\t\t*patch++ = s;\n\t\tmemcpy(patch, data, s);\n\t\tdata += s;\n\t\tpatch += s;\n\t\tsize -= s;\n\t} while (size);\n\n\treturn patch;\n} \n\nstatic unsigned copy_length (unsigned offset, unsigned length)\n{\n\tunsigned size = 0;\n\n\tassert (offset < MAX_SIZE && length < MAX_SIZE);\n\n\t/* For now we only copy a maximum of 0x10000 bytes per command.\n\t Longer copies are broken into pieces of that size. */\n\tdo {\n\t\tsigned s = length;\n\t\tif (s > 0x10000)\n\t\t\ts = 0x10000;\n\t\tsize += !!(s & 0xff) + !!(s & 0xff00);\n\t\tsize += !!(offset & 0xff) + !!(offset & 0xff00) + \n\t\t\t!!(offset & 0xff0000) + !!(offset & 0xff000000);\n\t\tsize += 1;\n\t\toffset += s;\n\t\tlength -= s;\n\t} while (length);\n\n\treturn size;\n}\n\nstatic unsigned char * write_copy(unsigned char *patch, unsigned offset, unsigned size)\n{\n\t/* The return value must be equal to patch + copy_length (patch,offset,size).\n\t This correspondence is essential for calculating the patch size. */\n\n\tdo {\n\t\tunsigned char c = 0x80, *cmd = patch++;\n\t\tunsigned v, s = size;\n\t\tif (s > 0x10000)\n\t\t\ts = 0x10000;\n\n\t\tv = offset;\n\t\tif (v & 0xff) c |= 0x01, *patch++ = v;\n\t\tv >>= 8;\n\t\tif (v & 0xff) c |= 0x02, *patch++ = v;\n\t\tv >>= 8;\n\t\tif (v & 0xff) c |= 0x04, *patch++ = v;\n\t\tv >>= 8;\n\t\tif (v & 0xff) c |= 0x08, *patch++ = v;\n\n\t\tv = s;\n\t\tif (v & 0xff) c |= 0x10, *patch++ = v;\n\t\tv >>= 8;\n\t\tif (v & 0xff) c |= 0x20, *patch++ = v;\n\n\t\t*cmd = c;\n\t\toffset += s;\n\t\tsize -= s;\n\t} while (size);\n\n\treturn patch;\n} \n\nstatic unsigned process_copies (unsigned char *data, unsigned length, unsigned maxlen)\n{\n\tint j;\n\tunsigned ptr = length;\n\tunsigned patch_bytes = header_length(idx_data_len, length);\n\n\t/* Work through the copies backwards, extending each one backwards. */\n\tfor (j = copy_count - 1; j >= 0; j--) {\n\t\tCopyInfo *copy = copies+j;\n\t\tunsigned src = copy->src;\n\t\tunsigned tgt = copy->tgt;\n\t\tunsigned len = copy->length;\n\t\tint data_follows;\n\n\t\tif (tgt + len > ptr) {\n\t\t\t/* Part of copy already covered by later one, so shorten copy. */\n\t\t\tif (ptr < tgt) {\n\t\t\t\t/* Copy completely disappeared, but guess that a backward extension\n\t\t\t\t might still be useful. This extension is non-contiguous, as it is\n\t\t\t\t irrelevant whether the skipped data would have matched or not.\n\t\t\t\t Be careful to not extend past the beginning of the source. */\n\t\t\t\tunsigned adjust = tgt - ptr;\n\n\t\t\t\ttgt = ptr;\n\t\t\t\tsrc = (src < adjust) ? 0 : src - adjust;\n\n\t\t\t\tcopy->tgt = tgt;\n\t\t\t\tcopy->src = src;\n\t\t\t}\n\n\t\t\tlen = ptr - tgt;\n\t\t}\n\n\t\twhile (src && tgt && idx_data[src - 1] == data[tgt - 1]) {\n\t\t\tsrc--;\n\t\t\ttgt--;\n\t\t}\n\t\tlen += copy->tgt - tgt;\n\n\t\tdata_follows = (tgt + len < ptr);\n\n\t\t/* A short copy may cost as much as 6 bytes for the copy and\n\t\t 5 as result of an extra data command.\n\t\t It's not worth having extra copies in order to just save a byte or two.\n\t\t Being too smart here may hurt later compression as well. */\n\t\tif (len < (data_follows ? 16 : 10))\n\t\t\tlen = 0;\n\n\t\t/* Some target data is not covered by the copies, account for\n\t\t the DATA command that will follow the copy. */\n\t\tif (len && data_follows) \n\t\t\tpatch_bytes += data_length(ptr - (tgt + len));\n\n\t\t/* Everything about the copy is known and will not change.\n\t\t Write back the new information and update the patch size\n\t\t with the size of the copy instruction. */\n\t\tcopy->length = len;\n\t\tcopy->src = src;\n\t\tcopy->tgt = tgt;\n\n\t\tif (len) {\n\t\t\t/* update patch size for copy command */\n\t\t\tpatch_bytes += copy_length (src, len);\n\t\t\tptr = tgt;\n\t\t} else if (j == copy_count - 1) {\n\t\t\t/* Remove empty copies at end of list. */\n\t\t\tcopy_count--;\n\t\t}\n\n\t\tif (patch_bytes > maxlen)\n\t\t\treturn 0;\n\t}\n\n\t/* Account for data before first copy */\n\tif (ptr != 0)\n\t\tpatch_bytes += data_length(ptr);\n\n\tif (patch_bytes > maxlen)\n\t\treturn 0;\n\treturn patch_bytes;\n}\n\nstatic unsigned calculate_delta(void *to_buf, unsigned long to_size, unsigned long max_size)\n{\n\tassert (to_size < MAX_SIZE);\n\n\tif (!find_copies(to_buf, to_size))\n\t\treturn 0;\n\treturn process_copies(to_buf, to_size, max_size);\n}\n\nstatic void *create_delta (unsigned char *data, unsigned len, unsigned delta_size)\n{\n\tunsigned char *delta = malloc(delta_size);\n\tunsigned char *ptr = delta;\n\tunsigned offset = 0;\n\tint j;\n\n\tptr = write_header(ptr, idx_data_len, len);\n\n\tfor (j = 0; j < copy_count; j++) {\n\t\tCopyInfo *copy = copies + j;\n\t\tunsigned copylen = copy->length;\n\n\t\tif (!copylen)\n\t\t\tcontinue;\n\n\t\tif (copy->tgt > offset) {\n\t\t\tassert (delta_size - (ptr - delta) > data_length(copy->tgt - offset));\n\t\t\tptr = write_data(ptr, data + offset, copy->tgt - offset);\n\t\t}\n\n\t\tassert(delta_size - (ptr - delta) >= copy_length(copy->src, copylen));\n\t\tptr = write_copy(ptr, copy->src, copylen);\n\t\toffset = copy->tgt + copylen;\n\t}\n\n\tif (offset < len)\n\t\tptr = write_data(ptr, data + offset, len - offset);\n\n\tassert(ptr - delta == delta_size);\n\n\treturn delta;\n}\n\nstatic void finalize_idx()\n{\n\tfree(copies);\n\tcopies = 0;\n\tmax_copies = 0;\n\tcopy_count = 0;\n\tfree(idx);\n\tidx = 0;\n\tidx_size = 0;\n\tidx_data = 0;\n\tidx_data_len = 0;\n}\n\nvoid *diff_delta(void *from_buf, unsigned long from_size,\n\t\t void *to_buf, unsigned long to_size,\n\t\t unsigned long *delta_size, unsigned long max_size)\n{\n\tunsigned char *delta = 0;\n\tunsigned dsize;\n\n\tassert (from_size <= MAX_SIZE && to_size <= MAX_SIZE);\n\tinit_idx(from_buf, from_size, 1); /* Use optimization level 1 */\n\tif (!max_size)\n\t\tmax_size = MAX_SIZE;\n\tdsize = calculate_delta (to_buf, to_size, max_size);\n\tif (dsize)\n\t\tdelta = create_delta (to_buf, to_size, dsize);\n\tfinalize_idx ();\n\tif (delta)\t\n\t\t*delta_size = dsize;\n\treturn delta;\n}\n"},{"id":"19046","messageId":"D1E1F442-2CE8-4CA0-A6E6-94B8FFC5E82D@adacore.com","threadId":"3938","inReplyTo":"Pine.LNX.4.64.0604241123490.18520@localhost.localdomain","subject":"Re: RFC: New diff-delta.c implementation","fromName":"Geert Bosch","fromEmail":"bosch@adacore.com","sentAt":"2006-04-24T16:31:27Z","receivedAt":"2006-04-24T16:31:27Z","isPatch":false,"sender":{"key":"bosch@adacore.com","avatar":null},"body":"> Sure, but the data buffers aren't necessarily so. At least some \n> code to\n> align index_step with actual memory offset if necessary should be\n> considered.\nI don't quite understand. Do you mean that if I mmap a file, I can't\ncount on the memory being word-aligned? Note that I traverse the\ntarget buffer byte-by-byte, but the matches in the source buffer are\nalways aligned to index_step. Doing a word load there instead of\nindividual byte loads actually is a significant speedup on PPC,\nand most other non-Intel platforms.\n> Indeed. And since the primary goal for GIT is to manage relatively\n> small files with relatively few differences then we have to \n> optimize for\n> that case while trying to simply limit the dammage in the other cases.\nYes, I'll look at those now. Also, comparing one index against\n10 target files may change the profile quite a bit. The new\nalgorithm spends most time on indexing, but when comparing against\nmany files, the find_copy part suddenly becomes dominant.\n\n> Well, I did lots of benchmarks too over the Linux kernel repository\n> with the current code. It is of course a dataset quite different from\n> two large files. And simply increasing the hash size to improve on \n> pack\n> size did increase CPU usage quite significantly.\nBTW, I still get:\npotomac%git-rev-list --objects \ne64961b0573b0e72bd55eab6d36bd97f859f9516 | ./git-pack-objects --no- \nreuse-delta --stdout\nGenerating pack...\nDone counting 17005 objects.\nDeltifying 17005 objects.\n100% (17005/17005) done\nfatal: delta size changed\n(This is for my git.git tree.)\n\n>> PS. Somehow your code had \"double line spacing\" :)\n> Gah. Your original version must have CRLF line terminations, and vi\n> simply notice that and writes the file back with CRLF by default. \n> Find\n> attached a version with those converted to LF only.\nStrange, my platform doesn't use CRLF, and my sources all have\npristine LF line terminations.\n\n -Geert\n"},{"id":"19047","messageId":"9EB87AF5-ACC3-4213-81B9-EF87AE68401C@adacore.com","threadId":"3938","inReplyTo":"D1E1F442-2CE8-4CA0-A6E6-94B8FFC5E82D@adacore.com","subject":"Re: RFC: New diff-delta.c implementation","fromName":"Geert Bosch","fromEmail":"bosch@adacore.com","sentAt":"2006-04-24T18:24:47Z","receivedAt":"2006-04-24T18:24:47Z","isPatch":false,"sender":{"key":"bosch@adacore.com","avatar":null},"body":"\nOn Apr 24, 2006, at 12:31, Geert Bosch wrote:\n> BTW, I still get:\n> potomac%git-rev-list --objects \n> e64961b0573b0e72bd55eab6d36bd97f859f9516 | ./git-pack-objects --no- \n> reuse-delta --stdout\n> Generating pack...\n> Done counting 17005 objects.\n> Deltifying 17005 objects.\n> 100% (17005/17005) done\n> fatal: delta size changed\n> (This is for my git.git tree.)\n\nIgnore this, I hadn't had my coffee yet.\n"},{"id":"19048","messageId":"EC4542D3-2C18-44D4-8FDB-86918054CA9B@adacore.com","threadId":"3938","inReplyTo":"Pine.LNX.4.64.0604241123490.18520@localhost.localdomain","subject":"Re: RFC: New diff-delta.c implementation","fromName":"Geert Bosch","fromEmail":"bosch@adacore.com","sentAt":"2006-04-24T18:27:19Z","receivedAt":"2006-04-24T18:27:19Z","isPatch":false,"sender":{"key":"bosch@adacore.com","avatar":null},"body":"On Apr 24, 2006, at 11:57, Nicolas Pitre wrote:\n>> As a compiler writer, I am more than aware of this.\n>> Your change results in a 70% slowdown on PowerPC.\n>\n> Huh!?\n\n2.5s instead of 1.5s comparing gcc-2.95.1.tar against\ngcc-2.95.2.tar. Byte loads are relatively expensive on\nthis platform. I'll put the word loads back in and make\nsure they don't slow things down on x86.\n\n -Geert\n"},{"id":"19049","messageId":"A175169A-0875-4DEF-BE97-C556325EB6DB@adacore.com","threadId":"3938","inReplyTo":"Pine.LNX.4.64.0604232327500.3603@localhost.localdomain","subject":"Re: RFC: New diff-delta.c implementation","fromName":"Geert Bosch","fromEmail":"bosch@adacore.com","sentAt":"2006-04-24T18:44:24Z","receivedAt":"2006-04-24T18:44:24Z","isPatch":false,"sender":{"key":"bosch@adacore.com","avatar":null},"body":"\nOn Apr 24, 2006, at 01:27, Nicolas Pitre wrote:\n> But here comes the sad part. Even after simplifying the code as \n> much as\n> I could, performance is still significantly worse than the current\n> diff-delta.c code. Repacking again the same Linux kernel repository\n> with the current code:\n\nChanging the level parameter in the call to init_idx to 0\ngives a significant speedup. After that, by far the most\ntime is spent computing hashes. I have some ideas of\ncutting down on that for this test case.\n> The final pack is smaller with your code but not significantly:\n> 117867049 bytes vs 118824550 bytes with the current code, i.e. less \n> than\n> 1% difference.\n\nI'm doing tests on the git.git repository now, and even though\nI see similar performance, I noted that the new algorithm packs\nmore files, so the pack size is not the only thing to look at.\nStill, it remains the case that when you compare two files with\njust one or two changes, the simplest algorithm is still good\nenough.\n\nIt will be very interesting how things will work out when\ncomparing 10 files at a time. Then the extra cost of building the\nindex isn't that significant, and the higher quality of the index\nmay then pay off.\n\n -Geert\n"},{"id":"19050","messageId":"Pine.LNX.4.64.0604241155000.18685@alien.or.mcafeemobile.com","threadId":"3938","inReplyTo":"20060423023144.GA17704@adacore.com","subject":"Re: RFC: New diff-delta.c implementation","fromName":"Davide Libenzi","fromEmail":"davidel@xmailserver.org","sentAt":"2006-04-24T19:10:32Z","receivedAt":"2006-04-24T19:10:32Z","isPatch":false,"sender":{"key":"davidel@xmailserver.org","avatar":null},"body":"On Sat, 22 Apr 2006, Geert Bosch wrote:\n\n> On Sat, Apr 22, 2006 at 01:36:07PM -0700, Davide Libenzi wrote:\n>> Geert, I saw you're using a shift of 55 bits, that gives an degree of the\n>> root polynomial of 63, that is not prime. Where did you get the root\n>> polynomial, and why you did not chose 61 as degree of the root?\n>> Just curious ...\n>\n> The polynomial was randomly created using code by David Mazieres, that\n> is part of LBFS. I chose a (irreducible) polynomial of degree 63 as\n> that was the same as LBFS did. As for my purposes it's best to have\n> a constant polynomial and I wanted to have all the code for\n> the computations in the same compilation unit for performance,\n> I decided to just have a little program print out the tables\n> and include it directly. The chosen polynomial was 0xb15e234bd3792f63.\n>\n> Later on I haven't revisited this decision, although I agree that\n> it'd probably be a good idea to use a polynomial of prime degree,\n> even though we're not looking for cryptographically strong hashes here.\n\nRight, but you are looking at highest equal-probability distribution over \nyour hash buckets ;)\nAnyway, thanks for bringing Rabin's polynomial fingerprint up from the \nforgotten lands. Performance and delta size are quite amazing, and I \ndecided to add Rabin's delta to libxdiff.\nI hacked some code (attached) to generate T/U tables. Since libxdiff must \nbe portable everywhere, even on system w/out 64 bits support, I use xrabin \nto create both 64 bits tables (poly degree 61) and 32 bits tables (poly \ndegree 31), and store them in a .c file letting the build environment to \npick the correct one for the platform.\n\n\n\n- Davide\n\n\n\n/*\n * xrabin by Davide Libenzi (Rabin's polynomial generator)\n * Copyright (C) 2006 Davide Libenzi\n *\n * This program is free software; you can redistribute it and/or modify\n * it under the terms of the GNU General Public License as published by\n * the Free Software Foundation; either version 2 of the License, or\n * (at your option) any later version.\n *\n * This program is distributed in the hope that it will be useful,\n * but WITHOUT ANY WARRANTY; without even the implied warranty of\n * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the\n * GNU General Public License for more details.\n *\n * You should have received a copy of the GNU General Public License\n * along with this program; if not, write to the Free Software\n * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA\n *\n * Davide Libenzi \n *\n *\n * Hints, ideas and code for the implementation came from:\n *\n * Rabin's original paper: http://www.xmailserver.org/rabin.pdf\n * Chan & Lu's paper: http://www.xmailserver.org/rabin_impl.pdf\n * Broder's paper: http://www.xmailserver.org/rabin_apps.pdf\n * LBFS source code: http://www.fs.net/sfswww/lbfs/\n * Geert Bosch's post: http://marc.theaimsgroup.com/?l=git&m=114565424620771&w=2\n *\n */\n\n#include \n#include \n#include \n#include \n\n\n\n#if defined(WIN32)\n#define strtoll _strtoi64\n#endif\n\n\n#if !defined(XRAB_WORD_TYPE)\n#if defined(WIN32)\n#define XRAB_WORD_TYPE __int64\n\n#else /* #if defined(WIN32) */\n#define XRAB_WORD_TYPE long long\n\n#endif /* #if defined(WIN32) */\n#endif /* #if !defined(XRAB_WORD_TYPE) */\n\n#if !defined(XRAB_WORD_PFMT)\n#if defined(WIN32)\n#define XRAB_WORD_PFMT \"0x%I64x\"\n\n#else /* #if defined(WIN32) */\n#define XRAB_WORD_PFMT \"0x%llx\"\n\n#endif /* #if defined(WIN32) */\n#endif /* #if !defined(XRAB_WORD_PFMT) */\n\n#define XPLYW_BITS (sizeof(xply_word) * 8)\n#define XPLYW_MSB ((xply_word) 1 << (sizeof(xply_word) * 8 - 1))\n\n\n\ntypedef unsigned XRAB_WORD_TYPE xply_word;\n\n\n\n\nstatic int xrab_isprime(int n) {\n\n\tif (n > 3) {\n\t\tif (n & 1) {\n\t\t\tint i, hn = n / 2;\n\n\t\t\tfor (i = 3; i < hn; i += 2)\n\t\t\t\tif (!(n % i))\n\t\t\t\t\treturn 0;\n\t\t} else\n\t\t\treturn 0;\n\t}\n\n\treturn 1;\n}\n\nstatic int xrab_fls(xply_word v) {\n\tint r, s;\n\txply_word mask = ~(((xply_word) 1 << (XPLYW_BITS / 2)) - 1);\n\n\tif (v == 0)\n\t\treturn 0;\n\tfor (r = XPLYW_BITS, s = r / 2; s != 0;) {\n\t\tif ((v & mask) == 0) {\n\t\t\tv <<= s;\n\t\t\tr -= s;\n\t\t}\n\t\ts /= 2;\n\t\tmask <<= s;\n\t}\n\n\treturn r;\n}\n\nstatic xply_word xrab_polymod(xply_word nh, xply_word nl, xply_word d) {\n\tint i, k = xrab_fls(d) - 1;\n\n\td <<= (XPLYW_BITS - 1) - k;\n\tif (nh) {\n\t\tif (nh & XPLYW_MSB)\n\t\t\tnh ^= d;\n\t\tfor (i = XPLYW_BITS - 2; i >= 0; i--)\n\t\t\tif (nh & ((xply_word) 1) << i) {\n\t\t\t\tnh ^= d >> (XPLYW_BITS - 1) - i;\n\t\t\t\tnl ^= d << i + 1;\n\t\t\t}\n\t}\n\tfor (i = XPLYW_BITS - 1; i >= k; i--)\n\t\tif (nl & ((xply_word) 1 << i))\n\t\t\tnl ^= d >> (XPLYW_BITS - 1) - i;\n\n\treturn nl;\n}\n\nstatic xply_word xrab_polygcd(xply_word x, xply_word y) {\n\n\tfor (;;) {\n\t\tif (!y)\n\t\t\treturn x;\n\t\tx = xrab_polymod(0, x, y);\n\t\tif (!x)\n\t\t\treturn y;\n\t\ty = xrab_polymod(0, y, x);\n\t}\n}\n\nstatic void xrab_polymult(xply_word *php, xply_word *plp, xply_word x,\n\t\t\t xply_word y) {\n\tint i;\n\txply_word ph = 0, pl = 0;\n\n\tif (x & 1)\n\t\tpl = y;\n\tfor (i = 1; i < XPLYW_BITS; i++)\n\t\tif (x & (((xply_word) 1) << i)) {\n\t\t\tph ^= y >> (XPLYW_BITS - i);\n\t\t\tpl ^= y << i;\n\t\t}\n\tif (php)\n\t\t*php = ph;\n\tif (plp)\n\t\t*plp = pl;\n}\n\nstatic xply_word xrab_polymmult(xply_word x, xply_word y, xply_word d) {\n\txply_word h, l;\n\n\txrab_polymult(&h, &l, x, y);\n\n\treturn xrab_polymod(h, l, d);\n}\n\nstatic int xrab_polyirreducible(xply_word f) {\n\txply_word u = 2;\n\tint i, m = (xrab_fls(f) - 1) >> 1;\n\n\tfor (i = 0; i < m; i++) {\n\t\tu = xrab_polymmult(u, u, f);\n\t\tif (xrab_polygcd(f, u ^ 2) != 1)\n\t\t\treturn 0;\n\t}\n\n\treturn 1;\n}\n\nstatic void xrab_rndgen(xply_word *f) {\n\tunsigned int i;\n\txply_word g;\n\n\tfor (i = 0, g = 0; i < sizeof(xply_word); i++)\n\t\tg ^= (g << 11) + (unsigned int) rand() + (g >> 7);\n\t*f = g;\n}\n\nstatic int xrab_polygen(int degree, xply_word *ply) {\n\txply_word msb, mask, f;\n\n\tif (degree <= 0 || degree >= XPLYW_BITS)\n\t\treturn -1;\n\tmsb = ((xply_word) 1) << degree;\n\tmask = msb - 1;\n\tsrand(time(NULL));\n\tdo {\n\t\txrab_rndgen(&f);\n\t\tf = (f & mask) | msb;\n\t} while (!xrab_polyirreducible(f));\n\t*ply = f;\n\n\treturn 0;\n}\n\nstatic int xarb_calc_tu(xply_word poly, int size, xply_word *t, xply_word *u) {\n\tint j, xshift, shift;\n\txply_word t1, ssh;\n\n\txshift = xrab_fls(poly) - 1;\n\tshift = xshift - 8;\n\tif (shift < 0)\n\t\treturn -1;\n\tt1 = xrab_polymod(0, ((xply_word) 1) << xshift, poly);\n\tfor (j = 0; j < 256; j++)\n\t\tt[j] = xrab_polymmult(j, t1, poly) | ((xply_word) j << xshift);\n\tfor (j = 1, ssh = 1; j < size; j++)\n\t\tssh = (ssh << 8) ^ t[ssh >> shift];\n\tfor (j = 0; j < 256; j++)\n\t\tu[j] = xrab_polymmult(j, ssh, poly);\n\n\treturn 0;\n}\n\nint main(int ac, char **av) {\n\tint i, size = 24, degree = 0, shift;\n\txply_word ply = 0, t[256], u[256];\n\n\tfor (i = 1; i < ac; i++) {\n\t\tif (strcmp(av[i], \"-s\") == 0) {\n\t\t\tif (++i < ac)\n\t\t\t\tsize = atol(av[i]);\n\t\t} else if (strcmp(av[i], \"-p\") == 0) {\n\t\t\tif (++i < ac)\n\t\t\t\tply = (xply_word) strtoll(av[i], NULL, 16);\n\t\t} else if (strcmp(av[i], \"-d\") == 0) {\n\t\t\tif (++i < ac)\n\t\t\t\tdegree = atol(av[i]);\n\t\t}\n\t}\n\tif (degree && (degree < 8 || degree >= XPLYW_BITS)) {\n\t\tfprintf(stderr, \"degree (%d) out of bound for the poly word size (8..%u)\\n\",\n\t\t\tdegree, XPLYW_BITS);\n\t\treturn 1;\n\t}\n\tif (degree == 0)\n\t\tfor (degree = XPLYW_BITS - 1; !xrab_isprime(degree); degree--);\n\tif (ply == 0 && xrab_polygen(degree, &ply) < 0)\n\t\treturn 2;\n\tshift = (xrab_fls(ply) - 1) - 8;\n\tfprintf(stderr, \"found poly = \" XRAB_WORD_PFMT \" (shift %d)\\n\",\n\t\tply, shift);\n\tif (xarb_calc_tu(ply, size, t, u) < 0)\n\t\treturn 3;\n\n\tfprintf(stdout, \"#if defined(XRABPLY_TYPE%d)\\n\\n\", XPLYW_BITS);\n\tfprintf(stdout, \"#if !defined(XV%d)\\n\", XPLYW_BITS);\n\tfprintf(stdout, \"#define XV%d(v) ((xply_word) v ## ULL)\\n\", XPLYW_BITS);\n\tfprintf(stdout, \"#endif\\n\\n\");\n\tfprintf(stdout, \"#define XRAB_ROOTPOLY XV%d(\" XRAB_WORD_PFMT \")\\n\\n\",\n\t\tXPLYW_BITS, ply);\n\tfprintf(stdout, \"#define XRAB_SHIFT %d\\n\", shift);\n\tfprintf(stdout, \"#define XRAB_WNDSIZE %d\\n\\n\", size);\n\tfprintf(stdout, \"typedef unsigned XRABPLY_TYPE%d xply_word;\\n\\n\", XPLYW_BITS);\n\tfprintf(stdout, \"static const xply_word T[256] = {\\n\");\n\tfor (i = 0; i < 256; i++) {\n\t\tif (i) {\n\t\t\tfputs(\",\", stdout);\n\t\t\tif (i % 4 == 0)\n\t\t\t\tfputs(\"\\n\\t\", stdout);\n\t\t\telse\n\t\t\t\tfputs(\" \", stdout);\n\t\t} else\n\t\t\tfputs(\"\\t\", stdout);\n\t\tfprintf(stdout, \"XV%d(\" XRAB_WORD_PFMT \")\", XPLYW_BITS, t[i]);\n\t}\n\tfprintf(stdout, \"\\n};\\n\\n\");\n\n\tfprintf(stdout, \"static const xply_word U[256] = {\\n\");\n\tfor (i = 0; i < 256; i++) {\n\t\tif (i) {\n\t\t\tfputs(\",\", stdout);\n\t\t\tif (i % 4 == 0)\n\t\t\t\tfputs(\"\\n\\t\", stdout);\n\t\t\telse\n\t\t\t\tfputs(\" \", stdout);\n\t\t} else\n\t\t\tfputs(\"\\t\", stdout);\n\t\tfprintf(stdout, \"XV%d(\" XRAB_WORD_PFMT \")\", XPLYW_BITS, u[i]);\n\t}\n\tfprintf(stdout, \"\\n};\\n\\n\");\n\n\tfprintf(stdout, \"#endif /* if defined(XRABPLY_TYPE%d) */\\n\\n\", XPLYW_BITS);\n\n\treturn 0;\n}\n\n"},{"id":"19052","messageId":"20060424192133.GA6446@nospam.com","threadId":"3938","inReplyTo":"Pine.LNX.4.64.0604241123490.18520@localhost.localdomain","subject":"Re: RFC: New diff-delta.c implementation","fromName":"Rutger Nijlunsing","fromEmail":"rutger@nospam.com","sentAt":"2006-04-24T19:21:33Z","receivedAt":"2006-04-24T19:21:33Z","isPatch":false,"sender":{"key":"rutger.nijlunsing@gmail.com","avatar":null},"body":"On Mon, Apr 24, 2006 at 11:57:38AM -0400, Nicolas Pitre wrote:\n> On Mon, 24 Apr 2006, Geert Bosch wrote:\n> > \n> > The comparison is a bit between a O(n^2) sort that is fast on small\n> > or mostly sorted inputs (but horrible on large ones) and a more\n> > complex O(nlogn) algorithm that is a bit slower for the simple\n> > cases, but far faster for more complex cases.\n> \n> Indeed. And since the primary goal for GIT is to manage relatively \n> small files with relatively few differences then we have to optimize for \n> that case while trying to simply limit the dammage in the other cases.\n\nLike others (the large-Maildir-storage thread comes to mind), I am\nlooking into storing more diverse data (say, $HOME) into git repo's\nand I would mind the O(n log n) instead of O(n^2) where the constant\nfactor of the first is larger than the constant factor of the second.\n\n...but then again, I'm just a user ;)\n\n\n-- \nRutger Nijlunsing ---------------------------------- eludias ed dse.nl\nnever attribute to a conspiracy which can be explained by incompetence\n----------------------------------------------------------------------\n"},{"id":"19053","messageId":"0C184231-78A3-4517-89B2-2AE5C2CC9752@adacore.com","threadId":"3938","inReplyTo":"Pine.LNX.4.64.0604241155000.18685@alien.or.mcafeemobile.com","subject":"Re: RFC: New diff-delta.c implementation","fromName":"Geert Bosch","fromEmail":"bosch@adacore.com","sentAt":"2006-04-24T19:23:15Z","receivedAt":"2006-04-24T19:23:15Z","isPatch":false,"sender":{"key":"bosch@adacore.com","avatar":null},"body":"\nOn Apr 24, 2006, at 15:10, Davide Libenzi wrote:\n> Right, but you are looking at highest equal-probability \n> distribution over your hash buckets ;)\n> Anyway, thanks for bringing Rabin's polynomial fingerprint up from \n> the forgotten lands. Performance and delta size are quite amazing, \n> and I decided to add Rabin's delta to libxdiff.\n> I hacked some code (attached) to generate T/U tables. Since \n> libxdiff must be portable everywhere, even on system w/out 64 bits \n> support, I use xrabin to create both 64 bits tables (poly degree \n> 61) and 32 bits tables (poly degree 31), and store them in a .c \n> file letting the build environment to pick the correct one for the \n> platform.\n\nIt might actually make sense to use the 32-bit code for GIT\nas well, since it turns out that on the typical small source files\nwith few differences, the full 64-bit Rabin is a problem for\nperformance.\n\nWhen diffing large files (my main interest), this is more than\noffset by the better hash quality. For tiny files with few changes\nit appears to be overkill...\n\n -Geert\n"},{"id":"19057","messageId":"20060424203734.GH27689@pasky.or.cz","threadId":"3938","inReplyTo":"20060424151901.GA2663@adacore.com","subject":"Re: RFC: New diff-delta.c implementation","fromName":"Petr Baudis","fromEmail":"pasky@suse.cz","sentAt":"2006-04-24T20:37:34Z","receivedAt":"2006-04-24T20:37:34Z","isPatch":false,"sender":{"key":"pasky@ucw.cz","avatar":"https://avatars.githubusercontent.com/u/18439?v=4"},"body":"Dear diary, on Mon, Apr 24, 2006 at 05:19:01PM CEST, I got a letter\nwhere Geert Bosch said that...\n> > But here comes the sad part. Even after simplifying the code as much as \n> > I could, performance is still significantly worse than the current \n> > diff-delta.c code. Repacking again the same Linux kernel repository \n> > with the current code:\n> That's unexpected, but I can see how this could be if most files have\n> very few differences and are relatively small. For such cases, almost\n> any hash will do, and the more complicated hashing will be more compute\n> intensive.\n> \n> \n> I have benchmarked my original diff code on a set of large files with\n> lots of changes. These are hardest to get right, and hardest to get\n> good performance with. Just try diffing any two large (uncompressed)\n> tar files, and you'll see. On many of such large files, the new code\n> is orders of magnitude faster. On these cases, the resulting deltas\n> are also much smaller.\n> \n> The comparison is a bit between a O(n^2) sort that is fast on small\n> or mostly sorted inputs (but horrible on large ones) and a more\n> complex O(nlogn) algorithm that is a bit slower for the simple\n> cases, but far faster for more complex cases.\n\nCan't you just switch between different delta algorithms based on some\nheuristic like the blob size?\n\n-- \n\t\t\t\tPetr \"Pasky\" Baudis\nStuff: http://pasky.or.cz/\nRight now I am having amnesia and deja-vu at the same time. I think\nI have forgotten this before.\n"},{"id":"19110","messageId":"444E68DF.1020105@lsrfire.ath.cx","threadId":"3938","inReplyTo":"20060424025741.GA636@adacore.com","subject":"Re: RFC: New diff-delta.c implementation","fromName":"Rene Scharfe","fromEmail":"rene.scharfe@lsrfire.ath.cx","sentAt":"2006-04-25T18:22:23Z","receivedAt":"2006-04-25T18:22:23Z","isPatch":false,"sender":{"key":"l.s.r@web.de","avatar":"https://avatars.githubusercontent.com/u/26122331?v=4"},"body":"Geert Bosch schrieb:\n> On Sat, Apr 22, 2006 at 02:36:04PM +0200, Rene Scharfe wrote:\n>> You can use \"indent -npro -kr -i8 -ts8 -l80 -ss -ncs\" to reformat your\n>> code into a similar style as used in the rest of git (settings taken\n>> from Lindent which is shipped with the Linux source).\n> Although I cringe at 8-space indenting, and find much of the GIT\n> code close to unreadable for lack of design-level comments, I'll\n> gladly reformat any code to conform to existing code standards.\n> Please let me know if you've got documentation on that, as it would\n> be helpful for me to know what the standard is. (No flame intended. :-)\n\nI'm not aware of a document mandating a certain formatting. The output\nof that indent call should come close to a \"standard format\", because\nLinus followed this style from the beginning and Junio didn't go astray.\n\nDon't worry too much about it. I just wanted to point out an easy way\nto reformat your code to use sane indenting. :->\n\nRené\n"}]}