Re: [PATCH 08/23] pack v4: basic references encoding

> Add variable length number encoding.  Let's apply the same encoding
> currently used for the offset to base of OBJ_OFS_DELTA objects which
> is the most efficient way to do this, and apply it to everything with
> pack version 4.
>
> Also add SHA1 reference encoding.  This one is either an index into a
> SHA1 table encoded using the variable length number encoding, or the
> literal 20 bytes SHA1 prefixed with a 0.
>
> The index 0 discriminates between an actual index value or the literal
> SHA1.  Therefore when the index is used its value must be increased by 1.
>
> Signed-off-by: Nicolas Pitre <nico@fluxnic.net>
> ---
>  packv4-create.c | 44 ++++++++++++++++++++++++++++++++++++++++++++
>  1 file changed, 44 insertions(+)
>
> diff --git a/packv4-create.c b/packv4-create.c
> index 012129b..bf33d15 100644
> --- a/packv4-create.c
> +++ b/packv4-create.c
> @@ -245,6 +245,50 @@ static void dict_dump(void)
>  	dump_dict_table(tree_path_table);
>  }
>  
> +/*
> + * Encode a numerical value with variable length into the destination buffer
> + */
> +static unsigned char *add_number(unsigned char *dst, uint64_t value)
> +{
> +	unsigned char buf[20];
> +	unsigned pos = sizeof(buf) - 1;
> +	buf[pos] = value & 127;
> +	while (value >>= 7)
> +		buf[--pos] = 128 | (--value & 127);
> +	do {
> +		*dst++ = buf[pos++];
> +	} while (pos < sizeof(buf));
> +	return dst;
> +}

> +/*
> + * Encode an object SHA1 reference with either an object index into the
> + * pack SHA1 table incremented by 1, or the literal SHA1 value prefixed
> + * with a zero byte if the needed SHA1 is not available in the table.
> + */
> +static struct pack_idx_entry *all_objs;
> +static unsigned all_objs_nr;
> +static unsigned char *add_sha1_ref(unsigned char *dst, const unsigned char *sha1)
> +{
> +	unsigned lo = 0, hi = all_objs_nr;
> +
> +	do {
> +		unsigned mi = (lo + hi) / 2;
> +		int cmp = hashcmp(all_objs[mi].sha1, sha1);
> +
> +		if (cmp == 0)
> +			return add_number(dst, mi + 1);
> +		if (cmp > 0)
> +			hi = mi;
> +		else
> +			lo = mi+1;
> +	} while (lo < hi);
> +
> +	*dst++ = 0;
> +	hashcpy(dst, sha1);
> +	return dst + 20;
> +}
> +
>  static struct pack_idx_entry *get_packed_object_list(struct packed_git *p)
>  {
>  	unsigned i, nr_objects = p->num_objects;