{"thread":{"id":"5633","subject":"[PATCH 5/6] teach git-index-pack about deltas with offset to base","startedAt":"2006-09-21T04:08:33Z","lastAt":"2006-09-21T04:08:33Z","messageCount":1,"participants":["Nicolas Pitre"],"isPatch":true,"patchVersion":1,"patchTotal":6},"messages":[{"id":"27331","messageId":"Pine.LNX.4.64.0609210007430.2627@xanadu.home","threadId":"5633","inReplyTo":null,"subject":"[PATCH 5/6] teach git-index-pack about deltas with offset to base","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-09-21T04:08:33Z","receivedAt":"2006-09-21T04:08:33Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"\nSigned-off-by: Nicolas Pitre <nico@cam.org>\n\ndiff --git a/index-pack.c b/index-pack.c\nindex aef7f0a..fffddd2 100644\n--- a/index-pack.c\n+++ b/index-pack.c\n@@ -18,10 +18,15 @@ struct object_entry\n \tunsigned char sha1[20];\n };\n \n+union delta_base {\n+\tunsigned char sha1[20];\n+\tunsigned long offset;\n+};\n+\n struct delta_entry\n {\n \tstruct object_entry *obj;\n-\tunsigned char base_sha1[20];\n+\tunion delta_base base;\n };\n \n static const char *pack_name;\n@@ -134,13 +139,13 @@ static void *unpack_entry_data(unsigned \n static void *unpack_raw_entry(unsigned long offset,\n \t\t\t      enum object_type *obj_type,\n \t\t\t      unsigned long *obj_size,\n-\t\t\t      unsigned char *delta_base,\n+\t\t\t      union delta_base *delta_base,\n \t\t\t      unsigned long *next_obj_offset)\n {\n \tunsigned long pack_limit = pack_size - 20;\n \tunsigned long pos = offset;\n \tunsigned char c;\n-\tunsigned long size;\n+\tunsigned long size, base_offset;\n \tunsigned shift;\n \tenum object_type type;\n \tvoid *data;\n@@ -161,26 +166,43 @@ static void *unpack_raw_entry(unsigned l\n \tcase OBJ_REF_DELTA:\n \t\tif (pos + 20 >= pack_limit)\n \t\t\tbad_object(offset, \"object extends past end of pack\");\n-\t\thashcpy(delta_base, pack_base + pos);\n+\t\thashcpy(delta_base->sha1, pack_base + pos);\n \t\tpos += 20;\n-\t\t/* fallthru */\n+\t\tbreak;\n+\tcase OBJ_OFS_DELTA:\n+\t\tmemset(delta_base, 0, sizeof(*delta_base));\n+\t\tc = pack_base[pos++];\n+\t\tbase_offset = c & 127;\n+\t\twhile (c & 128) {\n+\t\t\tbase_offset += 1;\n+\t\t\tif (!base_offset || base_offset & ~(~0UL >> 7))\n+\t\t\t\tbad_object(offset, \"offset value overflow for delta base object\");\n+\t\t\tif (pos >= pack_limit)\n+\t\t\t\tbad_object(offset, \"object extends past end of pack\");\n+\t\t\tc = pack_base[pos++];\n+\t\t\tbase_offset = (base_offset << 7) + (c & 127);\n+\t\t}\n+\t\tdelta_base->offset = offset - base_offset;\n+\t\tif (delta_base->offset >= offset)\n+\t\t\tbad_object(offset, \"delta base offset is out of bound\");\n+\t\tbreak;\n \tcase OBJ_COMMIT:\n \tcase OBJ_TREE:\n \tcase OBJ_BLOB:\n \tcase OBJ_TAG:\n-\t\tdata = unpack_entry_data(offset, &pos, size);\n \t\tbreak;\n \tdefault:\n \t\tbad_object(offset, \"bad object type %d\", type);\n \t}\n \n+\tdata = unpack_entry_data(offset, &pos, size);\n \t*obj_type = type;\n \t*obj_size = size;\n \t*next_obj_offset = pos;\n \treturn data;\n }\n \n-static int find_delta(const unsigned char *base_sha1)\n+static int find_delta(const union delta_base *base)\n {\n \tint first = 0, last = nr_deltas;\n \n@@ -189,7 +211,7 @@ static int find_delta(const unsigned cha\n                 struct delta_entry *delta = &deltas[next];\n                 int cmp;\n \n-                cmp = hashcmp(base_sha1, delta->base_sha1);\n+                cmp = memcmp(base, &delta->base, sizeof(*base));\n                 if (!cmp)\n                         return next;\n                 if (cmp < 0) {\n@@ -201,18 +223,18 @@ static int find_delta(const unsigned cha\n         return -first-1;\n }\n \n-static int find_deltas_based_on_sha1(const unsigned char *base_sha1,\n-\t\t\t\t     int *first_index, int *last_index)\n+static int find_delta_childs(const union delta_base *base,\n+\t\t\t     int *first_index, int *last_index)\n {\n-\tint first = find_delta(base_sha1);\n+\tint first = find_delta(base);\n \tint last = first;\n \tint end = nr_deltas - 1;\n \n \tif (first < 0)\n \t\treturn -1;\n-\twhile (first > 0 && !hashcmp(deltas[first - 1].base_sha1, base_sha1))\n+\twhile (first > 0 && !memcmp(&deltas[first - 1].base, base, sizeof(*base)))\n \t\t--first;\n-\twhile (last < end && !hashcmp(deltas[last + 1].base_sha1, base_sha1))\n+\twhile (last < end && !memcmp(&deltas[last + 1].base, base, sizeof(*base)))\n \t\t++last;\n \t*first_index = first;\n \t*last_index = last;\n@@ -253,13 +275,13 @@ static void resolve_delta(struct delta_e\n \tvoid *result;\n \tunsigned long result_size;\n \tenum object_type delta_type;\n-\tunsigned char base_sha1[20];\n+\tunion delta_base delta_base;\n \tunsigned long next_obj_offset;\n \tint j, first, last;\n \n \tobj->real_type = type;\n \tdelta_data = unpack_raw_entry(obj->offset, &delta_type,\n-\t\t\t\t      &delta_size, base_sha1,\n+\t\t\t\t      &delta_size, &delta_base,\n \t\t\t\t      &next_obj_offset);\n \tresult = patch_delta(base_data, base_size, delta_data, delta_size,\n \t\t\t     &result_size);\n@@ -267,10 +289,22 @@ static void resolve_delta(struct delta_e\n \tif (!result)\n \t\tbad_object(obj->offset, \"failed to apply delta\");\n \tsha1_object(result, result_size, type, obj->sha1);\n-\tif (!find_deltas_based_on_sha1(obj->sha1, &first, &last)) {\n+\n+\thashcpy(delta_base.sha1, obj->sha1);\n+\tif (!find_delta_childs(&delta_base, &first, &last)) {\n \t\tfor (j = first; j <= last; j++)\n-\t\t\tresolve_delta(&deltas[j], result, result_size, type);\n+\t\t\tif (deltas[j].obj->type == OBJ_REF_DELTA)\n+\t\t\t\tresolve_delta(&deltas[j], result, result_size, type);\n \t}\n+\n+\tmemset(&delta_base, 0, sizeof(delta_base));\n+\tdelta_base.offset = obj->offset;\n+\tif (!find_delta_childs(&delta_base, &first, &last)) {\n+\t\tfor (j = first; j <= last; j++)\n+\t\t\tif (deltas[j].obj->type == OBJ_OFS_DELTA)\n+\t\t\t\tresolve_delta(&deltas[j], result, result_size, type);\n+\t}\n+\n \tfree(result);\n }\n \n@@ -278,14 +312,14 @@ static int compare_delta_entry(const voi\n {\n \tconst struct delta_entry *delta_a = a;\n \tconst struct delta_entry *delta_b = b;\n-\treturn hashcmp(delta_a->base_sha1, delta_b->base_sha1);\n+\treturn memcmp(&delta_a->base, &delta_b->base, sizeof(union delta_base));\n }\n \n static void parse_pack_objects(void)\n {\n \tint i;\n \tunsigned long offset = sizeof(struct pack_header);\n-\tunsigned char base_sha1[20];\n+\tstruct delta_entry *delta = deltas;\n \tvoid *data;\n \tunsigned long data_size;\n \n@@ -299,12 +333,12 @@ static void parse_pack_objects(void)\n \t\tstruct object_entry *obj = &objects[i];\n \t\tobj->offset = offset;\n \t\tdata = unpack_raw_entry(offset, &obj->type, &data_size,\n-\t\t\t\t\tbase_sha1, &offset);\n+\t\t\t\t\t&delta->base, &offset);\n \t\tobj->real_type = obj->type;\n-\t\tif (obj->type == OBJ_REF_DELTA) {\n-\t\t\tstruct delta_entry *delta = &deltas[nr_deltas++];\n+\t\tif (obj->type == OBJ_REF_DELTA || obj->type == OBJ_OFS_DELTA) {\n+\t\t\tnr_deltas++;\n \t\t\tdelta->obj = obj;\n-\t\t\thashcpy(delta->base_sha1, base_sha1);\n+\t\t\tdelta++;\n \t\t} else\n \t\t\tsha1_object(data, data_size, obj->type, obj->sha1);\n \t\tfree(data);\n@@ -312,7 +346,7 @@ static void parse_pack_objects(void)\n \tif (offset != pack_size - 20)\n \t\tdie(\"packfile '%s' has junk at the end\", pack_name);\n \n-\t/* Sort deltas by base SHA1 for fast searching */\n+\t/* Sort deltas by base SHA1/offset for fast searching */\n \tqsort(deltas, nr_deltas, sizeof(struct delta_entry),\n \t      compare_delta_entry);\n \n@@ -326,22 +360,37 @@ static void parse_pack_objects(void)\n \t */\n \tfor (i = 0; i < nr_objects; i++) {\n \t\tstruct object_entry *obj = &objects[i];\n-\t\tint j, first, last;\n+\t\tunion delta_base base;\n+\t\tint j, ref, ref_first, ref_last, ofs, ofs_first, ofs_last;\n \n-\t\tif (obj->type == OBJ_REF_DELTA)\n+\t\tif (obj->type == OBJ_REF_DELTA || obj->type == OBJ_OFS_DELTA)\n \t\t\tcontinue;\n-\t\tif (find_deltas_based_on_sha1(obj->sha1, &first, &last))\n+\t\thashcpy(base.sha1, obj->sha1);\n+\t\tref = !find_delta_childs(&base, &ref_first, &ref_last);\n+\t\tmemset(&base, 0, sizeof(base));\n+\t\tbase.offset = obj->offset;\n+\t\tofs = !find_delta_childs(&base, &ofs_first, &ofs_last);\n+\t\tif (!ref && !ofs)\n \t\t\tcontinue;\n \t\tdata = unpack_raw_entry(obj->offset, &obj->type, &data_size,\n-\t\t\t\t\tbase_sha1, &offset);\n-\t\tfor (j = first; j <= last; j++)\n-\t\t\tresolve_delta(&deltas[j], data, data_size, obj->type);\n+\t\t\t\t\t&base, &offset);\n+\t\tif (ref)\n+\t\t\tfor (j = ref_first; j <= ref_last; j++)\n+\t\t\t\tif (deltas[j].obj->type == OBJ_REF_DELTA)\n+\t\t\t\t\tresolve_delta(&deltas[j], data,\n+\t\t\t\t\t\t      data_size, obj->type);\n+\t\tif (ofs)\n+\t\t\tfor (j = ofs_first; j <= ofs_last; j++)\n+\t\t\t\tif (deltas[j].obj->type == OBJ_OFS_DELTA)\n+\t\t\t\t\tresolve_delta(&deltas[j], data,\n+\t\t\t\t\t\t      data_size, obj->type);\n \t\tfree(data);\n \t}\n \n \t/* Check for unresolved deltas */\n \tfor (i = 0; i < nr_deltas; i++) {\n-\t\tif (deltas[i].obj->real_type == OBJ_REF_DELTA)\n+\t\tif (deltas[i].obj->real_type == OBJ_REF_DELTA ||\n+\t\t    deltas[i].obj->real_type == OBJ_OFS_DELTA)\n \t\t\tdie(\"packfile '%s' has unresolved deltas\",  pack_name);\n \t}\n }\n"}]}