{"thread":{"id":"5508","subject":"Re: A look at some alternative PACK file encodings","startedAt":"2006-09-07T08:41:58Z","lastAt":"2006-09-07T19:16:22Z","messageCount":3,"participants":["linux@horizon.com","Nicolas Pitre"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"26501","messageId":"20060907084158.25725.qmail@science.horizon.com","threadId":"5508","inReplyTo":null,"subject":"Re: A look at some alternative PACK file encodings","fromName":"","fromEmail":"linux@horizon.com","sentAt":"2006-09-07T08:41:58Z","receivedAt":"2006-09-07T08:41:58Z","isPatch":false,"sender":{"key":"linux@horizon.com","avatar":null},"body":"A few notes:\n\n\nRe: base-128 encodings, it's a pet peeve of mine that meny people, even\nwhile trying to save space, waste it by allowing redundant encodings.\nThe optimal way, assming msbit=1 means \"more\", is\n\n\t0x00 -> 0\t\t0x01 -> 1\n\t0x7f -> 127\t\t0x80 0x00 -> 128\n\t0x80 0x7f -> 255\t0x81 0x00 -> 256\n\t0xfe 0x7f -> 16383\t0xff 0x00 -> 16384\n\t0xff 0x7f -> 16511\t0x80 0x00 0x00 -> 16512\n\nThe decoding code can be written several ways, but try:\n\n\tc = *p++;\n\tx = c & 127;\n\twhile (c & 128) {\n\t\tc = *p++;\n\t\tx = ((x + 1) << 7) + (c & 127);\n\t}\n\nencoding is most easily done in reverse:\n\n\tchar buf[9];\n\tchar *p = buf+8;\n\n\t*p = x & 127;\n\twhile (x >>= 7)\n\t\t*--p = 0x80 | (--x & 127);\n\n\twrite_out(p, buf + 9 - p);\n\n\nIf you want to do signed offsets, the easiest way to write the code\nis to convert to an unsigned with the sign bit as lsbit:\n\n\tu = (s << 1) ^ -(s < 0);\n\nAnd then feed the resulting unsigned number to the functions above.\nHandling the sign bit specially in the encoding is messier.\n\n\nAnd finally, regarding qsort(), stability is not guaranteed, but glibc\nactually uses a stable merge sort if it can allocate the memory.  See\nhttp://sourceware.org/cgi-bin/cvsweb.cgi/libc/stdlib/msort.c?rev=1.21&cvsroot=glibc\n\nThis leads to the slightly annoying question of whether it's worth\nwriting a stable sort just to make git work a little bit better\non non-glibc platforms, when it doesn't affect most current users\npersonally and it still works correctly with an unstable qsort.\n\nIt might be simplest to simply lift the glibc mergesort implementation,\npossibly inlining the compares for efficiency.  If you touch the code,\nplease (my eyes!  it hurts us!) consider fixing the brace style.\n"},{"id":"26528","messageId":"Pine.LNX.4.64.0609071228560.18635@xanadu.home","threadId":"5508","inReplyTo":"20060907084158.25725.qmail@science.horizon.com","subject":"Re: A look at some alternative PACK file encodings","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-09-07T17:20:21Z","receivedAt":"2006-09-07T17:20:21Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Thu, 7 Sep 2006, linux@horizon.com wrote:\n\n> A few notes:\n> \n> \n> Re: base-128 encodings, it's a pet peeve of mine that meny people, even\n> while trying to save space, waste it by allowing redundant encodings.\n> The optimal way, assming msbit=1 means \"more\", is\n> \n> \t0x00 -> 0\t\t0x01 -> 1\n> \t0x7f -> 127\t\t0x80 0x00 -> 128\n> \t0x80 0x7f -> 255\t0x81 0x00 -> 256\n> \t0xfe 0x7f -> 16383\t0xff 0x00 -> 16384\n> \t0xff 0x7f -> 16511\t0x80 0x00 0x00 -> 16512\n\nIndeed.  But...\n\nSince we already use 3 bit of object type and that most objects are \nlarger than 15 bytes this means with 2 bytes we have 11 bits or up to \n2047.  With your encoding that would mean 2175.  So a byte would be \nsaved only for objects whose size is between 2048 and 2175.  I don't \nknow what is the proportion of objects that fall into that range in the \naverage pack, but even for those objects that means a reduction of less \nthan 0.1% with an average deflate rate of 50%.\n\nAnd we can forget about cases where the size would require a fourth byte \nor more since saving a byte in those cases is even less significant.\n\nSo I don't think we would gain that much using that encoding \nunless/until the pack format is made completely incompatible due to \nother changes, and that's something we should try to avoid as much as \npossible anyway.\n\n\nNicolas\n"},{"id":"26534","messageId":"20060907191622.7597.qmail@science.horizon.com","threadId":"5508","inReplyTo":"Pine.LNX.4.64.0609071228560.18635@xanadu.home","subject":"Re: A look at some alternative PACK file encodings","fromName":"","fromEmail":"linux@horizon.com","sentAt":"2006-09-07T19:16:22Z","receivedAt":"2006-09-07T19:16:22Z","isPatch":false,"sender":{"key":"linux@horizon.com","avatar":null},"body":"> So I don't think we would gain that much using that encoding \n> unless/until the pack format is made completely incompatible due to \n> other changes, and that's something we should try to avoid as much as \n> possible anyway.\n\nAh, I'm sorry; I didn't realize that it was already used elsewhere in\nthe pack format and this was just code re-use.  That is indeed a good\nreason to stick with what's already there.\n\nI agree the savings are minimal, but if you're starting from scratch,\nthey're free, so why not use them?  I tried to show that the code\ncomplexity is truly negligible.\n\nI'm sorry I didn't realize the details of pack structure before.\n"}]}