{"thread":{"id":"18720","subject":"[PATCH 1/4] sha1-lookup: add new \"sha1_pos\" function to efficiently lookup sha1","startedAt":"2009-04-04T20:59:26Z","lastAt":"2009-04-06T00:30:13Z","messageCount":20,"participants":["Christian Couder","Sverre Rabbelier","Johannes Schindelin","Jeff King","Junio C Hamano","Felipe Contreras","Reece Dunn","Teemu Likonen","Jay Soffian"],"isPatch":true,"patchVersion":1,"patchTotal":4},"messages":[{"id":"110345","messageId":"20090404225926.a9ad50e0.chriscool@tuxfamily.org","threadId":"18720","inReplyTo":null,"subject":"[PATCH 1/4] sha1-lookup: add new \"sha1_pos\" function to efficiently lookup sha1","fromName":"Christian Couder","fromEmail":"chriscool@tuxfamily.org","sentAt":"2009-04-04T20:59:26Z","receivedAt":"2009-04-04T20:59:26Z","isPatch":true,"sender":{"key":"christian.couder@gmail.com","avatar":"https://avatars.githubusercontent.com/u/208954?v=4"},"body":"This function has been copied from the \"patch_pos\" function in\n\"patch-ids.c\" but an additional parameter has been added.\n\nThe new parameter is a function pointer, that is used to access the\nsha1 of an element in the table.\n\nSigned-off-by: Christian Couder \n---\n sha1-lookup.c | 101 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++\n sha1-lookup.h | 7 ++++\n 2 files changed, 108 insertions(+), 0 deletions(-)\n\ndiff --git a/sha1-lookup.c b/sha1-lookup.c\nindex da35747..055dd87 100644\n--- a/sha1-lookup.c\n+++ b/sha1-lookup.c\n@@ -1,6 +1,107 @@\n #include \"cache.h\"\n #include \"sha1-lookup.h\"\n \n+static uint32_t take2(const unsigned char *sha1)\n+{\n+\treturn ((sha1[0] << 8) | sha1[1]);\n+}\n+\n+/*\n+ * Conventional binary search loop looks like this:\n+ *\n+ * do {\n+ * int mi = (lo + hi) / 2;\n+ * int cmp = \"entry pointed at by mi\" minus \"target\";\n+ * if (!cmp)\n+ * return (mi is the wanted one)\n+ * if (cmp > 0)\n+ * hi = mi; \"mi is larger than target\"\n+ * else\n+ * lo = mi+1; \"mi is smaller than target\"\n+ * } while (lo < hi);\n+ *\n+ * The invariants are:\n+ *\n+ * - When entering the loop, lo points at a slot that is never\n+ * above the target (it could be at the target), hi points at a\n+ * slot that is guaranteed to be above the target (it can never\n+ * be at the target).\n+ *\n+ * - We find a point 'mi' between lo and hi (mi could be the same\n+ * as lo, but never can be the same as hi), and check if it hits\n+ * the target. There are three cases:\n+ *\n+ * - if it is a hit, we are happy.\n+ *\n+ * - if it is strictly higher than the target, we update hi with\n+ * it.\n+ *\n+ * - if it is strictly lower than the target, we update lo to be\n+ * one slot after it, because we allow lo to be at the target.\n+ *\n+ * When choosing 'mi', we do not have to take the \"middle\" but\n+ * anywhere in between lo and hi, as long as lo <= mi < hi is\n+ * satisfied. When we somehow know that the distance between the\n+ * target and lo is much shorter than the target and hi, we could\n+ * pick mi that is much closer to lo than the midway.\n+ */\n+/*\n+ * The table should contain \"nr\" elements.\n+ * The sha1 of element i (between 0 and nr - 1) should be returned\n+ * by \"fn(i, table)\".\n+ */\n+int sha1_pos(const unsigned char *sha1, void *table, size_t nr,\n+\t sha1_access_fn fn)\n+{\n+\tsize_t hi = nr;\n+\tsize_t lo = 0;\n+\tsize_t mi = 0;\n+\n+\tif (!nr)\n+\t\treturn -1;\n+\n+\tif (nr != 1) {\n+\t\tsize_t lov, hiv, miv, ofs;\n+\n+\t\tfor (ofs = 0; ofs < 18; ofs += 2) {\n+\t\t\tlov = take2(fn(0, table) + ofs);\n+\t\t\thiv = take2(fn(nr - 1, table) + ofs);\n+\t\t\tmiv = take2(sha1 + ofs);\n+\t\t\tif (miv < lov)\n+\t\t\t\treturn -1;\n+\t\t\tif (hiv < miv)\n+\t\t\t\treturn -1 - nr;\n+\t\t\tif (lov != hiv) {\n+\t\t\t\t/*\n+\t\t\t\t * At this point miv could be equal\n+\t\t\t\t * to hiv (but sha1 could still be higher);\n+\t\t\t\t * the invariant of (mi < hi) should be\n+\t\t\t\t * kept.\n+\t\t\t\t */\n+\t\t\t\tmi = (nr - 1) * (miv - lov) / (hiv - lov);\n+\t\t\t\tif (lo <= mi && mi < hi)\n+\t\t\t\t\tbreak;\n+\t\t\t\tdie(\"oops\");\n+\t\t\t}\n+\t\t}\n+\t\tif (18 <= ofs)\n+\t\t\tdie(\"cannot happen -- lo and hi are identical\");\n+\t}\n+\n+\tdo {\n+\t\tint cmp;\n+\t\tcmp = hashcmp(fn(mi, table), sha1);\n+\t\tif (!cmp)\n+\t\t\treturn mi;\n+\t\tif (cmp > 0)\n+\t\t\thi = mi;\n+\t\telse\n+\t\t\tlo = mi + 1;\n+\t\tmi = (hi + lo) / 2;\n+\t} while (lo < hi);\n+\treturn -lo-1;\n+}\n+\n /*\n * Conventional binary search loop looks like this:\n *\ndiff --git a/sha1-lookup.h b/sha1-lookup.h\nindex 3249a81..20af285 100644\n--- a/sha1-lookup.h\n+++ b/sha1-lookup.h\n@@ -1,6 +1,13 @@\n #ifndef SHA1_LOOKUP_H\n #define SHA1_LOOKUP_H\n \n+typedef const unsigned char *sha1_access_fn(size_t index, void *table);\n+\n+extern int sha1_pos(const unsigned char *sha1,\n+\t\t void *table,\n+\t\t size_t nr,\n+\t\t sha1_access_fn fn);\n+\n extern int sha1_entry_pos(const void *table,\n \t\t\t size_t elem_size,\n \t\t\t size_t key_offset,\n-- \n1.6.2.2.404.ge96f3.dirty\n"},{"id":"110402","messageId":"fabb9a1e0904050317o1399118erb15ddf86d0fe6c3c@mail.gmail.com","threadId":"18720","inReplyTo":"20090404225926.a9ad50e0.chriscool@tuxfamily.org","subject":"Re: [PATCH 1/4] sha1-lookup: add new \"sha1_pos\" function to efficiently lookup sha1","fromName":"Sverre Rabbelier","fromEmail":"srabbelier@gmail.com","sentAt":"2009-04-05T10:17:32Z","receivedAt":"2009-04-05T10:17:32Z","isPatch":true,"sender":{"key":"srabbelier@gmail.com","avatar":"https://avatars.githubusercontent.com/u/3098?v=4"},"body":"Heya,\n\nOn Sat, Apr 4, 2009 at 22:59, Christian Couder wrote:\n> +                               if (lo <= mi && mi < hi)\n> +                                       break;\n> +                               die(\"oops\");\n\nThat's going to be an official git error message? Why not make it \"The\nfatal error oops has occured, press ctrl-c to lose all your work, or\npress any other key to do the same\"?\n\n-- \nCheers,\n\nSverre Rabbelier\n"},{"id":"110411","messageId":"alpine.DEB.1.00.0904051510490.10279@pacific.mpi-cbg.de","threadId":"18720","inReplyTo":"20090404225926.a9ad50e0.chriscool@tuxfamily.org","subject":"Re: [PATCH 1/4] sha1-lookup: add new \"sha1_pos\" function to efficiently lookup sha1","fromName":"Johannes Schindelin","fromEmail":"johannes.schindelin@gmx.de","sentAt":"2009-04-05T13:11:48Z","receivedAt":"2009-04-05T13:11:48Z","isPatch":true,"sender":{"key":"johannes.schindelin@gmx.de","avatar":"https://avatars.githubusercontent.com/u/127790?v=4"},"body":"Hi,\n\nOn Sat, 4 Apr 2009, Christian Couder wrote:\n\n> This function has been copied from the \"patch_pos\" function in\n> \"patch-ids.c\" but an additional parameter has been added.\n> \n> The new parameter is a function pointer, that is used to access the\n> sha1 of an element in the table.\n\nFrankly, this is hard to follow.\n\nIt would have been easier if the first patch added that parameter, and the \nsecond patch just _moved_ the function.\n\nCiao,\nDscho\n"},{"id":"110417","messageId":"20090405144111.GB2076@sigill.intra.peff.net","threadId":"18720","inReplyTo":"fabb9a1e0904050317o1399118erb15ddf86d0fe6c3c@mail.gmail.com","subject":"Re: [PATCH 1/4] sha1-lookup: add new \"sha1_pos\" function to efficiently lookup sha1","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2009-04-05T14:41:11Z","receivedAt":"2009-04-05T14:41:11Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Apr 05, 2009 at 12:17:32PM +0200, Sverre Rabbelier wrote:\n\n> On Sat, Apr 4, 2009 at 22:59, Christian Couder wrote:\n> > +                               if (lo <= mi && mi < hi)\n> > +                                       break;\n> > +                               die(\"oops\");\n> \n> That's going to be an official git error message? Why not make it \"The\n> fatal error oops has occured, press ctrl-c to lose all your work, or\n> press any other key to do the same\"?\n\nFrom my cursory reading of the code, this is a \"cannot happen\"\nassertion (and there is one a few lines below, too):\n\n+ die(\"oops\");\n+ }\n+ }\n+ if (18 <= ofs)\n+ die(\"cannot happen -- lo and hi are identical\");\n+ }\n\nI don't think we have an established style for such assertions. In\ntheory, users never see it, but the whole point of it being there is\nthat they _might_. :) One could use the \"assert\" macro, though I think\nits output is just as cryptic to end users. I usually do\n\n die(\"BUG: \");\n\nsome examples of which you can see via \"git grep BUG:\".\n\nOf course, \"binary search on fire?\" would probably work, too.\n\n-Peff\n"},{"id":"110418","messageId":"fabb9a1e0904050742t6b0d9d5s116539adf8434fc9@mail.gmail.com","threadId":"18720","inReplyTo":"20090405144111.GB2076@sigill.intra.peff.net","subject":"Re: [PATCH 1/4] sha1-lookup: add new \"sha1_pos\" function to efficiently lookup sha1","fromName":"Sverre Rabbelier","fromEmail":"srabbelier@gmail.com","sentAt":"2009-04-05T14:42:30Z","receivedAt":"2009-04-05T14:42:30Z","isPatch":true,"sender":{"key":"srabbelier@gmail.com","avatar":"https://avatars.githubusercontent.com/u/3098?v=4"},"body":"Heya,\n\nOn Sun, Apr 5, 2009 at 16:41, Jeff King wrote:\n> some examples of which you can see via \"git grep BUG:\".\n>\n> Of course, \"binary search on fire?\" would probably work, too.\n\nRight, I'm thinking anything that makes it easier to find out what\nwent wrong later on would be better than just \"oops\".\n\n-- \nCheers,\n\nSverre Rabbelier\n"},{"id":"110426","messageId":"7vvdpjrkp0.fsf@gitster.siamese.dyndns.org","threadId":"18720","inReplyTo":"fabb9a1e0904050317o1399118erb15ddf86d0fe6c3c@mail.gmail.com","subject":"Re: [PATCH 1/4] sha1-lookup: add new \"sha1_pos\" function to efficiently lookup sha1","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-04-05T18:59:07Z","receivedAt":"2009-04-05T18:59:07Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Sverre Rabbelier writes:\n\n> On Sat, Apr 4, 2009 at 22:59, Christian Couder wrote:\n>> +                               if (lo <= mi && mi < hi)\n>> +                                       break;\n>> +                               die(\"oops\");\n>\n> That's going to be an official git error message? Why not make it \"The\n\nIt's not \"going to be\", but \"has been so for the last two years since\n5d23e13\".\n\nIt is an assert, and I think Peff's die(\"BUG: ...\") would be a good idea.\n"},{"id":"110430","messageId":"fabb9a1e0904051206l11a629cald95a794815c2d76f@mail.gmail.com","threadId":"18720","inReplyTo":"7vvdpjrkp0.fsf@gitster.siamese.dyndns.org","subject":"Re: [PATCH 1/4] sha1-lookup: add new \"sha1_pos\" function to efficiently lookup sha1","fromName":"Sverre Rabbelier","fromEmail":"srabbelier@gmail.com","sentAt":"2009-04-05T19:06:56Z","receivedAt":"2009-04-05T19:06:56Z","isPatch":true,"sender":{"key":"srabbelier@gmail.com","avatar":"https://avatars.githubusercontent.com/u/3098?v=4"},"body":"Heya,\n\nOn Sun, Apr 5, 2009 at 20:59, Junio C Hamano wrote:\n> It's not \"going to be\", but \"has been so for the last two years since\n> 5d23e13\".\n\nAh, I did not see that earlier, as I read and commented-on this patch\nbefore reading 3/4.\n\n> It is an assert, and I think Peff's die(\"BUG: ...\") would be a good idea.\n\nAs long as the does indeed\nmake sense, right :).\n\n-- \nCheers,\n\nSverre Rabbelier\n"},{"id":"110432","messageId":"94a0d4530904051219q7d9ed028jd6e05f541d7c12b5@mail.gmail.com","threadId":"18720","inReplyTo":"7vvdpjrkp0.fsf@gitster.siamese.dyndns.org","subject":"Re: [PATCH 1/4] sha1-lookup: add new \"sha1_pos\" function to efficiently lookup sha1","fromName":"Felipe Contreras","fromEmail":"felipe.contreras@gmail.com","sentAt":"2009-04-05T19:19:27Z","receivedAt":"2009-04-05T19:19:27Z","isPatch":true,"sender":{"key":"felipe.contreras@gmail.com","avatar":"https://avatars.githubusercontent.com/u/8358?v=4"},"body":"On Sun, Apr 5, 2009 at 9:59 PM, Junio C Hamano wrote:\n> U3ZlcnJlIFJhYmJlbGllciA8c3JhYmJlbGllckBnbWFpbC5jb20+IHdyaXRlczoNCg0KPiBPbiBT\n> YXQsIEFwciA0LCAyMDA5IGF0IDIyOjU5LCBDaHJpc3RpYW4gQ291ZGVyIDxjaHJpc2Nvb2xAdHV4\n> ZmFtaWx5Lm9yZz4gd3JvdGU6DQo+PiArIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKg\n> IMKgIMKgIMKgIMKgIGlmIChsbyA8PSBtaSAmJiBtaSA8IGhpKQ0KPj4gKyDCoCDCoCDCoCDCoCDC\n> oCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCBicmVhazsNCj4+ICsg\n> wqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgZGllKCJvb3BzIik7\n> DQo+DQo+IFRoYXQncyBnb2luZyB0byBiZSBhbiBvZmZpY2lhbCBnaXQgZXJyb3IgbWVzc2FnZT8g\n> V2h5IG5vdCBtYWtlIGl0ICJUaGUNCg0KSXQncyBub3QgImdvaW5nIHRvIGJlIiwgYnV0ICJoYXMg\n> YmVlbiBzbyBmb3IgdGhlIGxhc3QgdHdvIHllYXJzIHNpbmNlDQo1ZDIzZTEzIi4NCg0KSXQgaXMg\n> YW4gYXNzZXJ0LCBhbmQgSSB0aGluayBQZWZmJ3MgZGllKCJCVUc6IC4uLiIpIHdvdWxkIGJlIGEg\n> Z29vZCBpZGVhLg0K\n\nHuh?\n\n-- \nFelipe Contreras\n"},{"id":"110436","messageId":"94a0d4530904051230x7feae9a9o6a9b81e8673d4fa1@mail.gmail.com","threadId":"18720","inReplyTo":"87vdpi29a4.fsf@iki.fi","subject":"Re: [PATCH 1/4] sha1-lookup: add new \"sha1_pos\" function to efficiently lookup sha1","fromName":"Felipe Contreras","fromEmail":"felipe.contreras@gmail.com","sentAt":"2009-04-05T19:30:51Z","receivedAt":"2009-04-05T19:30:51Z","isPatch":true,"sender":{"key":"felipe.contreras@gmail.com","avatar":"https://avatars.githubusercontent.com/u/8358?v=4"},"body":"On Sun, Apr 5, 2009 at 10:24 PM, Teemu Likonen wrote:\n> On 2009-04-05 22:19 (+0300), Felipe Contreras wrote:\n>\n>> On Sun, Apr 5, 2009 at 9:59 PM, Junio C Hamano wrote:\n>>> U3ZlcnJlIFJhYmJlbGllciA8c3JhYmJlbGllckBnbWFpbC5jb20+IHdyaXRlczoNCg0KPiBPbiBT\n> [...]\n>> Huh?\n>\n> Base64 transfer encoding:\n>\n>    Content-Type: text/plain; charset=utf-8\n>    Content-Transfer-Encoding: base64\n\nYeah, I know, but apparently Gmail doesn't support it.\n\n-- \nFelipe Contreras\n"},{"id":"110435","messageId":"3f4fd2640904051231x17117a4g3efe38067c8d3359@mail.gmail.com","threadId":"18720","inReplyTo":"94a0d4530904051219q7d9ed028jd6e05f541d7c12b5@mail.gmail.com","subject":"Re: [PATCH 1/4] sha1-lookup: add new \"sha1_pos\" function to efficiently lookup sha1","fromName":"Reece Dunn","fromEmail":"msclrhd@googlemail.com","sentAt":"2009-04-05T19:31:06Z","receivedAt":"2009-04-05T19:31:06Z","isPatch":true,"sender":{"key":"msclrhd@googlemail.com","avatar":null},"body":"2009/4/5 Felipe Contreras :\n> On Sun, Apr 5, 2009 at 9:59 PM, Junio C Hamano wrote:\n>> U3ZlcnJlIFJhYmJlbGllciA8c3JhYmJlbGllckBnbWFpbC5jb20+IHdyaXRlczoNCg0KPiBPbiBT\n>> YXQsIEFwciA0LCAyMDA5IGF0IDIyOjU5LCBDaHJpc3RpYW4gQ291ZGVyIDxjaHJpc2Nvb2xAdHV4\n>> ZmFtaWx5Lm9yZz4gd3JvdGU6DQo+PiArIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKg\n>> IMKgIMKgIMKgIMKgIGlmIChsbyA8PSBtaSAmJiBtaSA8IGhpKQ0KPj4gKyDCoCDCoCDCoCDCoCDC\n>> oCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCBicmVhazsNCj4+ICsg\n>> wqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgZGllKCJvb3BzIik7\n>> DQo+DQo+IFRoYXQncyBnb2luZyB0byBiZSBhbiBvZmZpY2lhbCBnaXQgZXJyb3IgbWVzc2FnZT8g\n>> V2h5IG5vdCBtYWtlIGl0ICJUaGUNCg0KSXQncyBub3QgImdvaW5nIHRvIGJlIiwgYnV0ICJoYXMg\n>> YmVlbiBzbyBmb3IgdGhlIGxhc3QgdHdvIHllYXJzIHNpbmNlDQo1ZDIzZTEzIi4NCg0KSXQgaXMg\n>> YW4gYXNzZXJ0LCBhbmQgSSB0aGluayBQZWZmJ3MgZGllKCJCVUc6IC4uLiIpIHdvdWxkIGJlIGEg\n>> Z29vZCBpZGVhLg0K\n>\n> Huh?\n\nI think Junio is trying to learn base64 :)!\n\nThis is what `base64 -d` gives:\n\nSverre Rabbelier writes:\n\n> On Sat, Apr 4, 2009 at 22:59, Christian Couder wrote:\n>> +                               if (lo <= mi && mi < hi)\n>> +                                       break;\n>> +                               die(\"oops\");\n>\n> That's going to be an official git error message? Why not make it \"The\n\nIt's not \"going to be\", but \"has been so for the last two years since\n5d23e13\".\n\nIt is an assert, and I think Peff's die(\"BUG: ...\") would be a good idea.\n"},{"id":"110441","messageId":"20090405195908.GB4716@coredump.intra.peff.net","threadId":"18720","inReplyTo":"fabb9a1e0904051206l11a629cald95a794815c2d76f@mail.gmail.com","subject":"Re: [PATCH 1/4] sha1-lookup: add new \"sha1_pos\" function to efficiently lookup sha1","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2009-04-05T19:59:09Z","receivedAt":"2009-04-05T19:59:09Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Apr 05, 2009 at 09:06:56PM +0200, Sverre Rabbelier wrote:\n\n> > It is an assert, and I think Peff's die(\"BUG: ...\") would be a good idea.\n> \n> As long as the does indeed\n> make sense, right :).\n\nI think:\n\n die(\"BUG: assertion failed in binary search\")\n\nwould be sufficient to tell the user what is going on, and let them\ninform the list what happened.\n\nHowever, if this \"oops\" has been there for 2 years and nobody has seen\nit, it's entirely possible that somebody actually got the binary search\ncode right in the first place. ;)\n\n-Peff\n"},{"id":"110443","messageId":"7vocvaq36x.fsf@gitster.siamese.dyndns.org","threadId":"18720","inReplyTo":"3f4fd2640904051231x17117a4g3efe38067c8d3359@mail.gmail.com","subject":"Re: [PATCH 1/4] sha1-lookup: add new \"sha1_pos\" function to efficiently lookup sha1","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-04-05T20:02:30Z","receivedAt":"2009-04-05T20:02:30Z","isPatch":true,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Reece Dunn writes:\n\n> 2009/4/5 Felipe Contreras :\n>> On Sun, Apr 5, 2009 at 9:59 PM, Junio C Hamano wrote:\n>>> U3ZlcnJlIFJhYmJlbGllciA8c3JhYmJlbGllckBnbWFpbC5jb20+IHdyaXRlczoNCg0KPiBPbiBT\n>>> YXQsIEFwciA0LCAyMDA5IGF0IDIyOjU5LCBDaHJpc3RpYW4gQ291ZGVyIDxjaHJpc2Nvb2xAdHV4\n>>> ZmFtaWx5Lm9yZz4gd3JvdGU6DQo+PiArIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKg\n>>> IMKgIMKgIMKgIMKgIGlmIChsbyA8PSBtaSAmJiBtaSA8IGhpKQ0KPj4gKyDCoCDCoCDCoCDCoCDC\n>>> oCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCBicmVhazsNCj4+ICsg\n>>> wqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgZGllKCJvb3BzIik7\n>>> DQo+DQo+IFRoYXQncyBnb2luZyB0byBiZSBhbiBvZmZpY2lhbCBnaXQgZXJyb3IgbWVzc2FnZT8g\n>>> V2h5IG5vdCBtYWtlIGl0ICJUaGUNCg0KSXQncyBub3QgImdvaW5nIHRvIGJlIiwgYnV0ICJoYXMg\n>>> YmVlbiBzbyBmb3IgdGhlIGxhc3QgdHdvIHllYXJzIHNpbmNlDQo1ZDIzZTEzIi4NCg0KSXQgaXMg\n>>> YW4gYXNzZXJ0LCBhbmQgSSB0aGluayBQZWZmJ3MgZGllKCJCVUc6IC4uLiIpIHdvdWxkIGJlIGEg\n>>> Z29vZCBpZGVhLg0K\n>>\n>> Huh?\n>\n> I think Junio is trying to learn base64 :)!\n\nI think that is what my Gnus/message-mode did. I do not know which letter\ntriggered it to decide it is UTF-8 to begin with, though. As far as I am\naware, I didn't type anything non-ascii in my message.\n"},{"id":"110444","messageId":"fabb9a1e0904051305m66b08c44y23129469198bfd0b@mail.gmail.com","threadId":"18720","inReplyTo":"20090405195908.GB4716@coredump.intra.peff.net","subject":"Re: [PATCH 1/4] sha1-lookup: add new \"sha1_pos\" function to efficiently lookup sha1","fromName":"Sverre Rabbelier","fromEmail":"srabbelier@gmail.com","sentAt":"2009-04-05T20:05:22Z","receivedAt":"2009-04-05T20:05:22Z","isPatch":true,"sender":{"key":"srabbelier@gmail.com","avatar":"https://avatars.githubusercontent.com/u/3098?v=4"},"body":"Heya,\n\nOn Sun, Apr 5, 2009 at 21:59, Jeff King wrote:\n>  die(\"BUG: assertion failed in binary search\")\n\nGiven that we now only have one binary search (which should be re-used\neverywhere), I think it's fair enough to describe it like that.\n\n> However, if this \"oops\" has been there for 2 years and nobody has seen\n> it, it's entirely possible that somebody actually got the binary search\n> code right in the first place. ;)\n\nHehe, never underestimate the difficulty of writing a proper binary\nsearch! :P But I do agree two years of 'testing' is more than more\nbinary searches get before being 'released' ;).\n\n-- \nCheers,\n\nSverre Rabbelier\n"},{"id":"110445","messageId":"20090405201700.GC4716@coredump.intra.peff.net","threadId":"18720","inReplyTo":"3f4fd2640904051231x17117a4g3efe38067c8d3359@mail.gmail.com","subject":"Re: [PATCH 1/4] sha1-lookup: add new \"sha1_pos\" function to efficiently lookup sha1","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2009-04-05T20:17:00Z","receivedAt":"2009-04-05T20:17:00Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Apr 05, 2009 at 08:31:06PM +0100, Reece Dunn wrote:\n\n> This is what `base64 -d` gives:\n> [...]\n> It's not \"going to be\", but \"has been so for the last two years since\n> 5d23e13\".\n> \n> It is an assert, and I think Peff's die(\"BUG: ...\") would be a good idea.\n\nInterestingly, I get a bunch of unprintable crap at the end. The culprit\nseems to be that vger stupidly adds:\n\n --\n To unsubscribe from this list: send the line \"unsubscribe git\" in\n the body of a message to majordomo@vger.kernel.org\n More majordomo info at http://vger.kernel.org/majordomo-info.html\n\nto the bottom, regardless of transfer-encoding. At best, this is\npointless and invisible, as the reader will just show the base64\ncontent. But some decoders (like mutt) actually treat non-base64\ncharacters not as \"end of base64\" but as \"ignore and keep looking for\nmore base64\". So this decodes into a bunch of random characters. And to\nmake it even more fun, it only happens if the message is a certain\nlength; otherwise, it needs \"=\" fill characters at the end, which\nunambiguously signal the end.\n\n\"openssl base64 -d\" stops decoding at the cruft. But I think what mutt\nis doing is right. According to RFC 2045:\n\n The encoded output stream must be represented in lines of no more\n than 76 characters each. All line breaks or other characters not\n found in Table 1 must be ignored by decoding software. In base64\n data, characters other than those in Table 1, line breaks, and\n other white space probably indicate a transmission error, about\n which a warning message or even a message rejection might be\n appropriate under some circumstances.\n\nI don't know if it is worth trying to get vger to be smarter. According\nto this, they consider base64 text parts not worth handling:\n\n http://lkml.indiana.edu/hypermail/linux/kernel/0304.0/0901.html\n\nSo maybe it is worth trying to get Junio not to send base64 mail. ;)\n\n-Peff\n"},{"id":"110447","messageId":"20090405202551.GD4716@coredump.intra.peff.net","threadId":"18720","inReplyTo":"7vocvaq36x.fsf@gitster.siamese.dyndns.org","subject":"Re: [PATCH 1/4] sha1-lookup: add new \"sha1_pos\" function to efficiently lookup sha1","fromName":"Jeff King","fromEmail":"peff@peff.net","sentAt":"2009-04-05T20:25:51Z","receivedAt":"2009-04-05T20:25:51Z","isPatch":true,"sender":{"key":"peff@peff.net","avatar":"https://avatars.githubusercontent.com/u/45925?v=4"},"body":"On Sun, Apr 05, 2009 at 01:02:30PM -0700, Junio C Hamano wrote:\n\n> > I think Junio is trying to learn base64 :)!\n> \n> I think that is what my Gnus/message-mode did. I do not know which letter\n> triggered it to decide it is UTF-8 to begin with, though. As far as I am\n> aware, I didn't type anything non-ascii in my message.\n\nActually, it is Sverre's fault. :)\n\nYou quoted his message, quoting Christian's message. Christian's message\nwas 7bit. But for some reason, Sverre's quoting of Christian's message\ncontains weird iso8859 space characters (0xa0).\n\nBut it is probably worth configuring Gnus to use QP instead of base64.\nIt's more efficient (for mostly ascii text), more readable to humans\nlooking at the encoded form, and is less likely to make you look like a\nspammer. :)\n\n-Peff\n"},{"id":"110449","messageId":"87r60626c9.fsf_-_@iki.fi","threadId":"18720","inReplyTo":"7vocvaq36x.fsf@gitster.siamese.dyndns.org","subject":"Gnus content transfer encoding (was: [PATCH 1/4] sha1-lookup: add new \"sha1_pos\" function to efficiently lookup sha1)","fromName":"Teemu Likonen","fromEmail":"tlikonen@iki.fi","sentAt":"2009-04-05T20:28:22Z","receivedAt":"2009-04-05T20:28:22Z","isPatch":true,"sender":{"key":"tlikonen@iki.fi","avatar":null},"body":"On 2009-04-05 13:02 (-0700), Junio C Hamano wrote:\n\n> Reece Dunn writes:\n>> I think Junio is trying to learn base64 :)!\n>\n> I think that is what my Gnus/message-mode did. I do not know which\n> letter triggered it to decide it is UTF-8 to begin with, though. As\n> far as I am aware, I didn't type anything non-ascii in my message.\n\nYou can customize the encoding decision mechanism, for example:\n\n (setq mm-body-charset-encoding-alist\n '((iso-8859-1 . 8bit)\n (utf-8 . 8bit)))\n\nFor more info, see:\n\n C-h v mm-body-charset-encoding-alist RET\n"},{"id":"110451","messageId":"76718490904051334p67e34ee5t89e73430a311bff3@mail.gmail.com","threadId":"18720","inReplyTo":"3f4fd2640904051231x17117a4g3efe38067c8d3359@mail.gmail.com","subject":"Re: [PATCH 1/4] sha1-lookup: add new \"sha1_pos\" function to efficiently lookup sha1","fromName":"Jay Soffian","fromEmail":"jaysoffian@gmail.com","sentAt":"2009-04-05T20:34:58Z","receivedAt":"2009-04-05T20:34:58Z","isPatch":true,"sender":{"key":"jaysoffian@gmail.com","avatar":"https://avatars.githubusercontent.com/u/155970?v=4"},"body":"On Sun, Apr 5, 2009 at 3:31 PM, Reece Dunn wrote:\n> 2009/4/5 Felipe Contreras :\n>> On Sun, Apr 5, 2009 at 9:59 PM, Junio C Hamano wrote:\n>>> U3ZlcnJlIFJhYmJlbGllciA8c3JhYmJlbGllckBnbWFpbC5jb20+IHdyaXRlczoNCg0KPiBPbiBT\n>>> YXQsIEFwciA0LCAyMDA5IGF0IDIyOjU5LCBDaHJpc3RpYW4gQ291ZGVyIDxjaHJpc2Nvb2xAdHV4\n>>> ZmFtaWx5Lm9yZz4gd3JvdGU6DQo+PiArIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKgIMKg\n>>> IMKgIMKgIMKgIMKgIGlmIChsbyA8PSBtaSAmJiBtaSA8IGhpKQ0KPj4gKyDCoCDCoCDCoCDCoCDC\n>>> oCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCDCoCBicmVhazsNCj4+ICsg\n>>> wqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgwqAgZGllKCJvb3BzIik7\n>>> DQo+DQo+IFRoYXQncyBnb2luZyB0byBiZSBhbiBvZmZpY2lhbCBnaXQgZXJyb3IgbWVzc2FnZT8g\n>>> V2h5IG5vdCBtYWtlIGl0ICJUaGUNCg0KSXQncyBub3QgImdvaW5nIHRvIGJlIiwgYnV0ICJoYXMg\n>>> YmVlbiBzbyBmb3IgdGhlIGxhc3QgdHdvIHllYXJzIHNpbmNlDQo1ZDIzZTEzIi4NCg0KSXQgaXMg\n>>> YW4gYXNzZXJ0LCBhbmQgSSB0aGluayBQZWZmJ3MgZGllKCJCVUc6IC4uLiIpIHdvdWxkIGJlIGEg\n>>> Z29vZCBpZGVhLg0K\n>>\n>> Huh?\n>\n> I think Junio is trying to learn base64 :)!\n\nJunio's _original_ message was fine. The problem is that vger\n(majordomo) appends the mailing list footer which technically corrupts\nthe message. Respectable MUA's can deal with the corruption, but\ngmail's web-interface just shows the raw base64 (previously it used to\njust show an empty message). I've filed a bug against gmail, but who\nknows.\n\nThe other options are:\n\n- fix majordomo on vger\n- replace majordomo on vger with a decent MLM\n- disable the mailing list footer\n- deal with it if you're a gmail user\n\nj.\n"},{"id":"110452","messageId":"fabb9a1e0904051335l4382986cib738171967971ffe@mail.gmail.com","threadId":"18720","inReplyTo":"20090405202551.GD4716@coredump.intra.peff.net","subject":"Re: [PATCH 1/4] sha1-lookup: add new \"sha1_pos\" function to efficiently lookup sha1","fromName":"Sverre Rabbelier","fromEmail":"srabbelier@gmail.com","sentAt":"2009-04-05T20:35:12Z","receivedAt":"2009-04-05T20:35:12Z","isPatch":true,"sender":{"key":"srabbelier@gmail.com","avatar":"https://avatars.githubusercontent.com/u/3098?v=4"},"body":"Heya,\n\nOn Sun, Apr 5, 2009 at 22:25, Jeff King wrote:\n> Actually, it is Sverre's fault. :)\n\nFine, blame the Dutch, why not! :P\n\n> You quoted his message, quoting Christian's message. Christian's message\n> was 7bit. But for some reason, Sverre's quoting of Christian's message\n> contains weird iso8859 space characters (0xa0).\n\n*points at GMail*, I ain't dun nothing funny! It's always been funny\nWRT to vger and encoding issues though, so I'm not surprised.\n\n-- \nCheers,\n\nSverre Rabbelier\n"},{"id":"110453","messageId":"3f4fd2640904051339h8d31d73t40d79b03ba121e1c@mail.gmail.com","threadId":"18720","inReplyTo":"7vocvaq36x.fsf@gitster.siamese.dyndns.org","subject":"Re: [PATCH 1/4] sha1-lookup: add new \"sha1_pos\" function to efficiently lookup sha1","fromName":"Reece Dunn","fromEmail":"msclrhd@googlemail.com","sentAt":"2009-04-05T20:39:44Z","receivedAt":"2009-04-05T20:39:44Z","isPatch":true,"sender":{"key":"msclrhd@googlemail.com","avatar":null},"body":"2009/4/5 Junio C Hamano :\n> Reece Dunn writes:\n>\n>> 2009/4/5 Felipe Contreras :\n>>>\n>>> Huh?\n>>\n>> I think Junio is trying to learn base64 :)!\n>\n> I think that is what my Gnus/message-mode did.  I do not know which letter\n> triggered it to decide it is UTF-8 to begin with, though.  As far as I am\n> aware, I didn't type anything non-ascii in my message.\n\nOk, so digging a little deeper, `base64 -d | od -t x1` gives the\nfollowing (partial) output:\n\n0000200 6f 74 65 3a 0d 0a 3e 3e 20 2b 20 c2 a0 20 c2 a0\n\nThe key entry here is the a0 character (NO-BREAK SPACE) or NBSP.\n\nThis is at:\n$ base64 -d test | od -t x1 | grep a0 | head -n 1 | xxd -r\note:\n>> +\n\nSo looks like it is in the patch you are quoting. NOTE: I have removed\nthe spaces after the +. Also, according to www.unicode.org, c2 is A^\n(A with a circumflex) -- not sure what that is doing there, though.\n\n- Reece\n"},{"id":"110495","messageId":"7vskkmoc8a.fsf@gitster.siamese.dyndns.org","threadId":"18720","inReplyTo":"87r60626c9.fsf_-_@iki.fi","subject":"Re: Gnus content transfer encoding","fromName":"Junio C Hamano","fromEmail":"gitster@pobox.com","sentAt":"2009-04-06T00:30:13Z","receivedAt":"2009-04-06T00:30:13Z","isPatch":false,"sender":{"key":"gitster@pobox.com","avatar":"https://avatars.githubusercontent.com/u/54884?v=4"},"body":"Teemu Likonen writes:\n\n> On 2009-04-05 13:02 (-0700), Junio C Hamano wrote:\n>\n>> Reece Dunn writes:\n>>> I think Junio is trying to learn base64 :)!\n>>\n>> I think that is what my Gnus/message-mode did. I do not know which\n>> letter triggered it to decide it is UTF-8 to begin with, though. As\n>> far as I am aware, I didn't type anything non-ascii in my message.\n>\n> You can customize the encoding decision mechanism, for example:\n>\n> (setq mm-body-charset-encoding-alist\n> '((iso-8859-1 . 8bit)\n> (utf-8 . 8bit)))\n>\n> For more info, see:\n>\n> C-h v mm-body-charset-encoding-alist RET\n\nInteresting.\n\nI have had these for a long time:\n\n\t(setq mm-coding-system-priorities '(us-ascii iso-2022-jp utf-8 iso-8859-1))\n (setq mm-content-transfer-encoding-defaults\n '((\"text/.*\" 8bit)\n (\"message/rfc822\" 8bit)\n (\"application/emacs-lisp\" qp-or-base64)\n (\"application/x-emacs-lisp\" qp-or-base64)\n (\"application/x-patch\" qp-or-base64)\n (\".*\" base64)))\n\nI did not have any customization on my own to body-charset-encoding-alist \nand C-h v gave me:\n\n mm-body-charset-encoding-alist's value is \n ((iso-2022-jp . 7bit)\n (iso-2022-jp-2 . 7bit)\n (utf-16 . base64)\n (utf-16be . base64)\n (utf-16le . base64))\n\nI'll have the following in my .emacs in addition to the coding-system-prio\nand c-t-e-defaults I already have:\n\n (setq mm-body-charset-encoding-alist\n '((iso-2022-jp . 7bit)\n (iso-2022-jp-2 . 7bit)\n (iso-8859-1 . 8bit)\n (utf-8 . 8bit)))\n\nand will see what happens, but I wonder how this new one interacts with\nthe c-t-e-defaults.\n\nThanks.\n"}]}