# Re: A look at some alternative PACK file encodings 3 messages from 2006-09-07 to 2006-09-07. Participants: linux@horizon.com, Nicolas Pitre. Thread: https://gitlist.dev/t/5508 ## linux@horizon.com, 2006-09-07 08:41 Subject: Re: A look at some alternative PACK file encodings Message-ID: <20060907084158.25725.qmail@science.horizon.com> URL: https://gitlist.dev/e/20060907084158.25725.qmail%40science.horizon.com ``` A few notes: Re: base-128 encodings, it's a pet peeve of mine that meny people, even while trying to save space, waste it by allowing redundant encodings. The optimal way, assming msbit=1 means "more", is 0x00 -> 0 0x01 -> 1 0x7f -> 127 0x80 0x00 -> 128 0x80 0x7f -> 255 0x81 0x00 -> 256 0xfe 0x7f -> 16383 0xff 0x00 -> 16384 0xff 0x7f -> 16511 0x80 0x00 0x00 -> 16512 The decoding code can be written several ways, but try: c = *p++; x = c & 127; while (c & 128) { c = *p++; x = ((x + 1) << 7) + (c & 127); } encoding is most easily done in reverse: char buf[9]; char *p = buf+8; *p = x & 127; while (x >>= 7) *--p = 0x80 | (--x & 127); write_out(p, buf + 9 - p); If you want to do signed offsets, the easiest way to write the code is to convert to an unsigned with the sign bit as lsbit: u = (s << 1) ^ -(s < 0); And then feed the resulting unsigned number to the functions above. Handling the sign bit specially in the encoding is messier. And finally, regarding qsort(), stability is not guaranteed, but glibc actually uses a stable merge sort if it can allocate the memory. See http://sourceware.org/cgi-bin/cvsweb.cgi/libc/stdlib/msort.c?rev=1.21&cvsroot=glibc This leads to the slightly annoying question of whether it's worth writing a stable sort just to make git work a little bit better on non-glibc platforms, when it doesn't affect most current users personally and it still works correctly with an unstable qsort. It might be simplest to simply lift the glibc mergesort implementation, possibly inlining the compares for efficiency. If you touch the code, please (my eyes! it hurts us!) consider fixing the brace style. ``` ## Nicolas Pitre, 2006-09-07 17:20 Subject: Re: A look at some alternative PACK file encodings Message-ID: URL: https://gitlist.dev/e/Pine.LNX.4.64.0609071228560.18635%40xanadu.home In-Reply-To: <20060907084158.25725.qmail@science.horizon.com> ``` On Thu, 7 Sep 2006, linux@horizon.com wrote: > A few notes: > > > Re: base-128 encodings, it's a pet peeve of mine that meny people, even > while trying to save space, waste it by allowing redundant encodings. > The optimal way, assming msbit=1 means "more", is > > 0x00 -> 0 0x01 -> 1 > 0x7f -> 127 0x80 0x00 -> 128 > 0x80 0x7f -> 255 0x81 0x00 -> 256 > 0xfe 0x7f -> 16383 0xff 0x00 -> 16384 > 0xff 0x7f -> 16511 0x80 0x00 0x00 -> 16512 Indeed. But... Since we already use 3 bit of object type and that most objects are larger than 15 bytes this means with 2 bytes we have 11 bits or up to 2047. With your encoding that would mean 2175. So a byte would be saved only for objects whose size is between 2048 and 2175. I don't know what is the proportion of objects that fall into that range in the average pack, but even for those objects that means a reduction of less than 0.1% with an average deflate rate of 50%. And we can forget about cases where the size would require a fourth byte or more since saving a byte in those cases is even less significant. So I don't think we would gain that much using that encoding unless/until the pack format is made completely incompatible due to other changes, and that's something we should try to avoid as much as possible anyway. Nicolas ``` ## linux@horizon.com, 2006-09-07 19:16 Subject: Re: A look at some alternative PACK file encodings Message-ID: <20060907191622.7597.qmail@science.horizon.com> URL: https://gitlist.dev/e/20060907191622.7597.qmail%40science.horizon.com In-Reply-To: ``` > So I don't think we would gain that much using that encoding > unless/until the pack format is made completely incompatible due to > other changes, and that's something we should try to avoid as much as > possible anyway. Ah, I'm sorry; I didn't realize that it was already used elsewhere in the pack format and this was just code re-use. That is indeed a good reason to stick with what's already there. I agree the savings are minimal, but if you're starting from scratch, they're free, so why not use them? I tried to show that the code complexity is truly negligible. I'm sorry I didn't realize the details of pack structure before. ```