On Sat, 7 Sep 2013, Nguyễn Thái Ngọc Duy wrote:
> This is the most common case for delta trees. In fact it's the only
> kind that's produced by packv4-create. It fits well in the way
> index-pack resolves deltas and benefits from threading (the set of
> objects depending on this base does not overlap with the set of
> objects depending on another base)
>
> Multi-base trees will be probably processed differently.
>
> Signed-off-by: Nguyễn Thái Ngọc Duy <pclouds@xxxxxxxxx>
> ---
> builtin/index-pack.c | 194 ++++++++++++++++++++++++++++++++++++++++++++++-----
> 1 file changed, 178 insertions(+), 16 deletions(-)
>
> diff --git a/builtin/index-pack.c b/builtin/index-pack.c
> index 1fa74f4..4a24bc3 100644
> --- a/builtin/index-pack.c
> +++ b/builtin/index-pack.c
> @@ -12,6 +12,8 @@
> #include "streaming.h"
> #include "thread-utils.h"
> #include "packv4-parse.h"
> +#include "varint.h"
> +#include "tree-walk.h"
>
> static const char index_pack_usage[] =
> "git index-pack [-v] [-o <index-file>] [--keep | --keep=<msg>] [--verify] [--strict] (<pack-file> | --stdin [--fix-thin] [<pack-file>])";
> @@ -38,8 +40,8 @@ struct base_data {
> struct object_entry *obj;
> void *data;
> unsigned long size;
> - int ref_first, ref_last;
> - int ofs_first, ofs_last;
> + int ref_first, ref_last, tree_first;
> + int ofs_first, ofs_last, tree_last;
> };
>
> #if !defined(NO_PTHREADS) && defined(NO_THREAD_SAFE_PREAD)
> @@ -437,6 +439,7 @@ static struct base_data *alloc_base_data(void)
> memset(base, 0, sizeof(*base));
> base->ref_last = -1;
> base->ofs_last = -1;
> + base->tree_last = -1;
> return base;
> }
>
> @@ -670,6 +673,8 @@ static void *unpack_tree_v4(struct object_entry *obj,
> }
>
> if (last_base) {
> + if (nr_deltas - delta_start > 1)
> + die("sorry guys, multi-base trees are not supported yet");
> strbuf_release(&sb);
> return NULL;
> } else {
> @@ -794,6 +799,83 @@ static void *unpack_raw_entry(struct object_entry *obj,
> return data;
> }
>
> +static void *patch_one_base_tree(const struct object_entry *src,
> + const unsigned char *src_buf,
> + const unsigned char *delta_buf,
> + unsigned long delta_size,
> + unsigned long *dst_size)
> +{
> + unsigned int nr;
> + const unsigned char *last_base = NULL;
> + struct strbuf sb = STRBUF_INIT;
> + const unsigned char *p = delta_buf;
> +
> + nr = decode_varint(&p);
> + while (nr && p < delta_buf + delta_size) {
> + unsigned int copy_start_or_path = decode_varint(&p);
> + if (copy_start_or_path & 1) { /* copy_start */
> + struct tree_desc desc;
> + struct name_entry entry;
> + unsigned int copy_count = decode_varint(&p);
> + unsigned int copy_start = copy_start_or_path >> 1;
> + if (!src)
> + die("we are not supposed to copy from another tree!");
> + if (copy_count & 1) { /* first delta */
> + unsigned int id = decode_varint(&p);
> + if (!id) {
> + last_base = p;
> + p += 20;
> + } else
> + last_base = sha1_table + (id - 1) * 20;
> + if (hashcmp(last_base, src->idx.sha1))
> + die(_("bad tree base in patch_one_base_tree"));
> + } else if (!last_base)
> + die(_("bad copy count index in patch_one_base_tree"));
> + copy_count >>= 1;
> + if (!copy_count)
> + die(_("bad copy count index in patch_one_base_tree"));
> + nr -= copy_count;
> +
> + init_tree_desc(&desc, src_buf, src->size);
> + while (tree_entry(&desc, &entry)) {
> + if (copy_start)
> + copy_start--;
> + else if (copy_count) {
> + strbuf_addf(&sb, "%o %s%c", entry.mode, entry.path, '\0');
> + strbuf_add(&sb, entry.sha1, 20);
> + copy_count--;
> + } else
> + break;
> + }
> + } else { /* path */
> + unsigned int path_idx = copy_start_or_path >> 1;
> + const unsigned char *path;
> + unsigned mode;
> + unsigned int id;
> + const unsigned char *entry_sha1;
> +
> + if (path_idx >= path_dict->nb_entries)
> + die(_("bad path index in unpack_tree_v4"));
> + id = decode_varint(&p);
> + if (!id) {
> + entry_sha1 = p;
> + p += 20;
> + } else
> + entry_sha1 = sha1_table + (id - 1) * 20;
You should verify that id doesn't overflow the sha1 table here.
Similarly in other places.
Nicolas