From: linux@horizon.com
Date: Sun, 03 Jul 2005 00:17:43 GMT
Subject: Re: kernel.org and GIT tree rebuilding
Message-ID: <20050703025112.18758.qmail@science.horizon.com>

> 	unsigned long size;
> 	unsigned char c;
> 
> 	c = *pack++;
> 	size = c & 15;
> 	type = (c >> 4) & 7;
> 	while (c & 0x80) {
> 		c = *pack++;
> 		size = (size << 7) + (c & 0x7f);
> 	}
> 
> or something. That's even denser.

If you're going for density, you missed something.  Try:

 	c = *pack++;
 	size = c & 15;
 	type = (c >> 4) & 7;
 	while (c & 0x80) {
 		c = *pack++;
 		size = (size << 7) + (c & 0x7f) + 16;
 	}

Encoding is most easily done in little-endian order, such as:

static unsigned
encode(unsigned char *p, unsigned long x)
{
        unsigned char *q = p;
        unsigned char buf[5];
        unsigned char *b = buf;

        while (x > 15) {
                assert(b < buf+5);
                x -= 16;
                *b++ = x & 0x7f;
                x >>= 7;
        }
        *b = x;

        while (b != buf)
                *q++ = *b-- | 0x80;
        *q++ = *b;
        return (unsigned)(q - p);
}

(You'll probably want to rewrite the above, but it's abandoned to the
public domain in any case.  Go nuts.)