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

[Nicolas Pitre <nico@fluxnic.net>]

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;
-- 
1.8.4.22.g54757b7