teach git-index-pack about deltas with offset to base

Signed-off-by: Nicolas Pitre <nico@cam.org>
Signed-off-by: Junio C Hamano <junkio@cox.net>

diff --git a/index-pack.c b/index-pack.c
index aef7f0a32efa7eb5dd9d94702822cde643da651b..fffddd25c9b9cc92b837434d7099cb7b4180ce0b 100644 (file)
--- a/index-pack.c
+++ b/index-pack.c
@@ -18,10 +18,15 @@ struct object_entry
        unsigned char sha1[20];
 };
 
        unsigned char sha1[20];
 };
 

+union delta_base {
+       unsigned char sha1[20];
+       unsigned long offset;
+};
+

 struct delta_entry
 {
        struct object_entry *obj;
 struct delta_entry
 {
        struct object_entry *obj;

-       unsigned char base_sha1[20];
+       union delta_base base;

 };
 
 static const char *pack_name;
 };
 
 static const char *pack_name;


@@ -134,13 +139,13 @@ static void *unpack_entry_data(unsigned long offset,
 static void *unpack_raw_entry(unsigned long offset,
                              enum object_type *obj_type,
                              unsigned long *obj_size,
 static void *unpack_raw_entry(unsigned long offset,
                              enum object_type *obj_type,
                              unsigned long *obj_size,

-                             unsigned char *delta_base,
+                             union delta_base *delta_base,

                              unsigned long *next_obj_offset)
 {
        unsigned long pack_limit = pack_size - 20;
        unsigned long pos = offset;
        unsigned char c;
                              unsigned long *next_obj_offset)
 {
        unsigned long pack_limit = pack_size - 20;
        unsigned long pos = offset;
        unsigned char c;

-       unsigned long size;
+       unsigned long size, base_offset;

        unsigned shift;
        enum object_type type;
        void *data;
        unsigned shift;
        enum object_type type;
        void *data;


@@ -161,26 +166,43 @@ static void *unpack_raw_entry(unsigned long offset,
        case OBJ_REF_DELTA:
                if (pos + 20 >= pack_limit)
                        bad_object(offset, "object extends past end of pack");
        case OBJ_REF_DELTA:
                if (pos + 20 >= pack_limit)
                        bad_object(offset, "object extends past end of pack");

-               hashcpy(delta_base, pack_base + pos);
+               hashcpy(delta_base->sha1, pack_base + pos);

                pos += 20;
                pos += 20;

-               /* fallthru */
+               break;
+       case OBJ_OFS_DELTA:
+               memset(delta_base, 0, sizeof(*delta_base));
+               c = pack_base[pos++];
+               base_offset = c & 127;
+               while (c & 128) {
+                       base_offset += 1;
+                       if (!base_offset || base_offset & ~(~0UL >> 7))
+                               bad_object(offset, "offset value overflow for delta base object");
+                       if (pos >= pack_limit)
+                               bad_object(offset, "object extends past end of pack");
+                       c = pack_base[pos++];
+                       base_offset = (base_offset << 7) + (c & 127);
+               }
+               delta_base->offset = offset - base_offset;
+               if (delta_base->offset >= offset)
+                       bad_object(offset, "delta base offset is out of bound");
+               break;

        case OBJ_COMMIT:
        case OBJ_TREE:
        case OBJ_BLOB:
        case OBJ_TAG:
        case OBJ_COMMIT:
        case OBJ_TREE:
        case OBJ_BLOB:
        case OBJ_TAG:

-               data = unpack_entry_data(offset, &pos, size);

                break;
        default:
                bad_object(offset, "bad object type %d", type);
        }
 
                break;
        default:
                bad_object(offset, "bad object type %d", type);
        }
 

+       data = unpack_entry_data(offset, &pos, size);

        *obj_type = type;
        *obj_size = size;
        *next_obj_offset = pos;
        return data;
 }
 
        *obj_type = type;
        *obj_size = size;
        *next_obj_offset = pos;
        return data;
 }
 

-static int find_delta(const unsigned char *base_sha1)
+static int find_delta(const union delta_base *base)

 {
        int first = 0, last = nr_deltas;
 
 {
        int first = 0, last = nr_deltas;
 


@@ -189,7 +211,7 @@ static int find_delta(const unsigned char *base_sha1)
                 struct delta_entry *delta = &deltas[next];
                 int cmp;
 
                 struct delta_entry *delta = &deltas[next];
                 int cmp;
 

-                cmp = hashcmp(base_sha1, delta->base_sha1);
+                cmp = memcmp(base, &delta->base, sizeof(*base));

                 if (!cmp)
                         return next;
                 if (cmp < 0) {
                 if (!cmp)
                         return next;
                 if (cmp < 0) {


@@ -201,18 +223,18 @@ static int find_delta(const unsigned char *base_sha1)
         return -first-1;
 }
 
         return -first-1;
 }
 

-static int find_deltas_based_on_sha1(const unsigned char *base_sha1,
-                                    int *first_index, int *last_index)
+static int find_delta_childs(const union delta_base *base,
+                            int *first_index, int *last_index)

 {
 {

-       int first = find_delta(base_sha1);
+       int first = find_delta(base);

        int last = first;
        int end = nr_deltas - 1;
 
        if (first < 0)
                return -1;
        int last = first;
        int end = nr_deltas - 1;
 
        if (first < 0)
                return -1;

-       while (first > 0 && !hashcmp(deltas[first - 1].base_sha1, base_sha1))
+       while (first > 0 && !memcmp(&deltas[first - 1].base, base, sizeof(*base)))

                --first;
                --first;

-       while (last < end && !hashcmp(deltas[last + 1].base_sha1, base_sha1))
+       while (last < end && !memcmp(&deltas[last + 1].base, base, sizeof(*base)))

                ++last;
        *first_index = first;
        *last_index = last;
                ++last;
        *first_index = first;
        *last_index = last;


@@ -253,13 +275,13 @@ static void resolve_delta(struct delta_entry *delta, void *base_data,
        void *result;
        unsigned long result_size;
        enum object_type delta_type;
        void *result;
        unsigned long result_size;
        enum object_type delta_type;

-       unsigned char base_sha1[20];
+       union delta_base delta_base;

        unsigned long next_obj_offset;
        int j, first, last;
 
        obj->real_type = type;
        delta_data = unpack_raw_entry(obj->offset, &delta_type,
        unsigned long next_obj_offset;
        int j, first, last;
 
        obj->real_type = type;
        delta_data = unpack_raw_entry(obj->offset, &delta_type,

-                                     &delta_size, base_sha1,
+                                     &delta_size, &delta_base,

                                      &next_obj_offset);
        result = patch_delta(base_data, base_size, delta_data, delta_size,
                             &result_size);
                                      &next_obj_offset);
        result = patch_delta(base_data, base_size, delta_data, delta_size,
                             &result_size);


@@ -267,10 +289,22 @@ static void resolve_delta(struct delta_entry *delta, void *base_data,
        if (!result)
                bad_object(obj->offset, "failed to apply delta");
        sha1_object(result, result_size, type, obj->sha1);
        if (!result)
                bad_object(obj->offset, "failed to apply delta");
        sha1_object(result, result_size, type, obj->sha1);

-       if (!find_deltas_based_on_sha1(obj->sha1, &first, &last)) {
+
+       hashcpy(delta_base.sha1, obj->sha1);
+       if (!find_delta_childs(&delta_base, &first, &last)) {

                for (j = first; j <= last; j++)
                for (j = first; j <= last; j++)

-                       resolve_delta(&deltas[j], result, result_size, type);
+                       if (deltas[j].obj->type == OBJ_REF_DELTA)
+                               resolve_delta(&deltas[j], result, result_size, type);

        }
        }

+
+       memset(&delta_base, 0, sizeof(delta_base));
+       delta_base.offset = obj->offset;
+       if (!find_delta_childs(&delta_base, &first, &last)) {
+               for (j = first; j <= last; j++)
+                       if (deltas[j].obj->type == OBJ_OFS_DELTA)
+                               resolve_delta(&deltas[j], result, result_size, type);
+       }
+

        free(result);
 }
 
        free(result);
 }
 


@@ -278,14 +312,14 @@ static int compare_delta_entry(const void *a, const void *b)
 {
        const struct delta_entry *delta_a = a;
        const struct delta_entry *delta_b = b;
 {
        const struct delta_entry *delta_a = a;
        const struct delta_entry *delta_b = b;

-       return hashcmp(delta_a->base_sha1, delta_b->base_sha1);
+       return memcmp(&delta_a->base, &delta_b->base, sizeof(union delta_base));

 }
 
 static void parse_pack_objects(void)
 {
        int i;
        unsigned long offset = sizeof(struct pack_header);
 }
 
 static void parse_pack_objects(void)
 {
        int i;
        unsigned long offset = sizeof(struct pack_header);

-       unsigned char base_sha1[20];
+       struct delta_entry *delta = deltas;

        void *data;
        unsigned long data_size;
 
        void *data;
        unsigned long data_size;
 


@@ -299,12 +333,12 @@ static void parse_pack_objects(void)
                struct object_entry *obj = &objects[i];
                obj->offset = offset;
                data = unpack_raw_entry(offset, &obj->type, &data_size,
                struct object_entry *obj = &objects[i];
                obj->offset = offset;
                data = unpack_raw_entry(offset, &obj->type, &data_size,

-                                       base_sha1, &offset);
+                                       &delta->base, &offset);

                obj->real_type = obj->type;
                obj->real_type = obj->type;

-               if (obj->type == OBJ_REF_DELTA) {
-                       struct delta_entry *delta = &deltas[nr_deltas++];
+               if (obj->type == OBJ_REF_DELTA || obj->type == OBJ_OFS_DELTA) {
+                       nr_deltas++;

                        delta->obj = obj;
                        delta->obj = obj;

-                       hashcpy(delta->base_sha1, base_sha1);
+                       delta++;

                } else
                        sha1_object(data, data_size, obj->type, obj->sha1);
                free(data);
                } else
                        sha1_object(data, data_size, obj->type, obj->sha1);
                free(data);


@@ -312,7 +346,7 @@ static void parse_pack_objects(void)
        if (offset != pack_size - 20)
                die("packfile '%s' has junk at the end", pack_name);
 
        if (offset != pack_size - 20)
                die("packfile '%s' has junk at the end", pack_name);
 

-       /* Sort deltas by base SHA1 for fast searching */
+       /* Sort deltas by base SHA1/offset for fast searching */

        qsort(deltas, nr_deltas, sizeof(struct delta_entry),
              compare_delta_entry);
 
        qsort(deltas, nr_deltas, sizeof(struct delta_entry),
              compare_delta_entry);
 


@@ -326,22 +360,37 @@ static void parse_pack_objects(void)
         */
        for (i = 0; i < nr_objects; i++) {
                struct object_entry *obj = &objects[i];
         */
        for (i = 0; i < nr_objects; i++) {
                struct object_entry *obj = &objects[i];

-               int j, first, last;
+               union delta_base base;
+               int j, ref, ref_first, ref_last, ofs, ofs_first, ofs_last;

 
 

-               if (obj->type == OBJ_REF_DELTA)
+               if (obj->type == OBJ_REF_DELTA || obj->type == OBJ_OFS_DELTA)

                        continue;
                        continue;

-               if (find_deltas_based_on_sha1(obj->sha1, &first, &last))
+               hashcpy(base.sha1, obj->sha1);
+               ref = !find_delta_childs(&base, &ref_first, &ref_last);
+               memset(&base, 0, sizeof(base));
+               base.offset = obj->offset;
+               ofs = !find_delta_childs(&base, &ofs_first, &ofs_last);
+               if (!ref && !ofs)

                        continue;
                data = unpack_raw_entry(obj->offset, &obj->type, &data_size,
                        continue;
                data = unpack_raw_entry(obj->offset, &obj->type, &data_size,

-                                       base_sha1, &offset);
-               for (j = first; j <= last; j++)
-                       resolve_delta(&deltas[j], data, data_size, obj->type);
+                                       &base, &offset);
+               if (ref)
+                       for (j = ref_first; j <= ref_last; j++)
+                               if (deltas[j].obj->type == OBJ_REF_DELTA)
+                                       resolve_delta(&deltas[j], data,
+                                                     data_size, obj->type);
+               if (ofs)
+                       for (j = ofs_first; j <= ofs_last; j++)
+                               if (deltas[j].obj->type == OBJ_OFS_DELTA)
+                                       resolve_delta(&deltas[j], data,
+                                                     data_size, obj->type);

                free(data);
        }
 
        /* Check for unresolved deltas */
        for (i = 0; i < nr_deltas; i++) {
                free(data);
        }
 
        /* Check for unresolved deltas */
        for (i = 0; i < nr_deltas; i++) {

-               if (deltas[i].obj->real_type == OBJ_REF_DELTA)
+               if (deltas[i].obj->real_type == OBJ_REF_DELTA ||
+                   deltas[i].obj->real_type == OBJ_OFS_DELTA)

                        die("packfile '%s' has unresolved deltas",  pack_name);
        }
 }
                        die("packfile '%s' has unresolved deltas",  pack_name);
        }
 }