{"thread":{"id":"5632","subject":"[PATCH 4/6] teach git-unpack-objects about deltas with offset to base","startedAt":"2006-09-21T04:07:39Z","lastAt":"2006-09-21T04:07:39Z","messageCount":1,"participants":["Nicolas Pitre"],"isPatch":true,"patchVersion":1,"patchTotal":6},"messages":[{"id":"27330","messageId":"Pine.LNX.4.64.0609210006520.2627@xanadu.home","threadId":"5632","inReplyTo":null,"subject":"[PATCH 4/6] teach git-unpack-objects about deltas with offset to base","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-09-21T04:07:39Z","receivedAt":"2006-09-21T04:07:39Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"For delta resolution to be possible, a list of sha1/offset tupple must\nbe constructed in memory in order to load the appropriate base object.\n\nSigned-off-by: Nicolas Pitre <nico@cam.org>\n\ndiff --git a/builtin-unpack-objects.c b/builtin-unpack-objects.c\nindex c6c6368..e70a711 100644\n--- a/builtin-unpack-objects.c\n+++ b/builtin-unpack-objects.c\n@@ -15,7 +15,7 @@ static const char unpack_usage[] = \"git-\n \n /* We always read in 4kB chunks. */\n static unsigned char buffer[4096];\n-static unsigned long offset, len;\n+static unsigned long offset, len, consumed_bytes;\n static SHA_CTX ctx;\n \n /*\n@@ -51,6 +51,7 @@ static void use(int bytes)\n \t\tdie(\"used more bytes than were available\");\n \tlen -= bytes;\n \toffset += bytes;\n+\tconsumed_bytes += bytes;\n }\n \n static void *get_data(unsigned long size)\n@@ -89,35 +90,49 @@ static void *get_data(unsigned long size\n \n struct delta_info {\n \tunsigned char base_sha1[20];\n+\tunsigned long base_offset;\n \tunsigned long size;\n \tvoid *delta;\n+\tunsigned nr;\n \tstruct delta_info *next;\n };\n \n static struct delta_info *delta_list;\n \n-static void add_delta_to_list(unsigned char *base_sha1, void *delta, unsigned long size)\n+static void add_delta_to_list(unsigned nr, unsigned const char *base_sha1,\n+\t\t\t      unsigned long base_offset,\n+\t\t\t      void *delta, unsigned long size)\n {\n \tstruct delta_info *info = xmalloc(sizeof(*info));\n \n \thashcpy(info->base_sha1, base_sha1);\n+\tinfo->base_offset = base_offset;\n \tinfo->size = size;\n \tinfo->delta = delta;\n+\tinfo->nr = nr;\n \tinfo->next = delta_list;\n \tdelta_list = info;\n }\n \n-static void added_object(unsigned char *sha1, const char *type, void *data, unsigned long size);\n+struct obj_info {\n+\tunsigned long offset;\n+\tunsigned char sha1[20];\n+};\n+\n+static struct obj_info *obj_list;\n \n-static void write_object(void *buf, unsigned long size, const char *type)\n+static void added_object(unsigned nr, const char *type, void *data,\n+\t\t\t unsigned long size);\n+\n+static void write_object(unsigned nr, void *buf, unsigned long size,\n+\t\t\t const char *type)\n {\n-\tunsigned char sha1[20];\n-\tif (write_sha1_file(buf, size, type, sha1) < 0)\n+\tif (write_sha1_file(buf, size, type, obj_list[nr].sha1) < 0)\n \t\tdie(\"failed to write object\");\n-\tadded_object(sha1, type, buf, size);\n+\tadded_object(nr, type, buf, size);\n }\n \n-static void resolve_delta(const char *type,\n+static void resolve_delta(unsigned nr, const char *type,\n \t\t\t  void *base, unsigned long base_size,\n \t\t\t  void *delta, unsigned long delta_size)\n {\n@@ -130,20 +145,23 @@ static void resolve_delta(const char *ty\n \tif (!result)\n \t\tdie(\"failed to apply delta\");\n \tfree(delta);\n-\twrite_object(result, result_size, type);\n+\twrite_object(nr, result, result_size, type);\n \tfree(result);\n }\n \n-static void added_object(unsigned char *sha1, const char *type, void *data, unsigned long size)\n+static void added_object(unsigned nr, const char *type, void *data,\n+\t\t\t unsigned long size)\n {\n \tstruct delta_info **p = &delta_list;\n \tstruct delta_info *info;\n \n \twhile ((info = *p) != NULL) {\n-\t\tif (!hashcmp(info->base_sha1, sha1)) {\n+\t\tif (!hashcmp(info->base_sha1, obj_list[nr].sha1) ||\n+\t\t    info->base_offset == obj_list[nr].offset) {\n \t\t\t*p = info->next;\n \t\t\tp = &delta_list;\n-\t\t\tresolve_delta(type, data, size, info->delta, info->size);\n+\t\t\tresolve_delta(info->nr, type, data, size,\n+\t\t\t\t      info->delta, info->size);\n \t\t\tfree(info);\n \t\t\tcontinue;\n \t\t}\n@@ -151,7 +169,8 @@ static void added_object(unsigned char *\n \t}\n }\n \n-static void unpack_non_delta_entry(enum object_type kind, unsigned long size)\n+static void unpack_non_delta_entry(enum object_type kind, unsigned long size,\n+\t\t\t\t   unsigned nr)\n {\n \tvoid *buf = get_data(size);\n \tconst char *type;\n@@ -164,30 +183,80 @@ static void unpack_non_delta_entry(enum \n \tdefault: die(\"bad type %d\", kind);\n \t}\n \tif (!dry_run && buf)\n-\t\twrite_object(buf, size, type);\n+\t\twrite_object(nr, buf, size, type);\n \tfree(buf);\n }\n \n-static void unpack_delta_entry(unsigned long delta_size)\n+static void unpack_delta_entry(enum object_type kind, unsigned long delta_size,\n+\t\t\t       unsigned nr)\n {\n \tvoid *delta_data, *base;\n \tunsigned long base_size;\n \tchar type[20];\n \tunsigned char base_sha1[20];\n \n-\thashcpy(base_sha1, fill(20));\n-\tuse(20);\n+\tif (kind == OBJ_REF_DELTA) {\n+\t\thashcpy(base_sha1, fill(20));\n+\t\tuse(20);\n+\t\tdelta_data = get_data(delta_size);\n+\t\tif (dry_run || !delta_data) {\n+\t\t\tfree(delta_data);\n+\t\t\treturn;\n+\t\t}\n+\t\tif (!has_sha1_file(base_sha1)) {\n+\t\t\thashcpy(obj_list[nr].sha1, null_sha1);\n+\t\t\tadd_delta_to_list(nr, base_sha1, 0, delta_data, delta_size);\n+\t\t\treturn;\n+\t\t}\n+\t} else {\n+\t\tunsigned base_found = 0;\n+\t\tunsigned char *pack, c;\n+\t\tunsigned long base_offset;\n+\t\tunsigned lo, mid, hi;\n \n-\tdelta_data = get_data(delta_size);\n-\tif (dry_run || !delta_data) {\n-\t\tfree(delta_data);\n-\t\treturn;\n-\t}\n+\t\tpack = fill(1);\n+\t\tc = *pack;\n+\t\tuse(1);\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\tdie(\"offset value overflow for delta base object\");\n+\t\t\tpack = fill(1);\n+\t\t\tc = *pack;\n+\t\t\tuse(1);\n+\t\t\tbase_offset = (base_offset << 7) + (c & 127);\n+\t\t}\n+\t\tbase_offset = obj_list[nr].offset - base_offset;\n \n-\tif (!has_sha1_file(base_sha1)) {\n-\t\tadd_delta_to_list(base_sha1, delta_data, delta_size);\n-\t\treturn;\n+\t\tdelta_data = get_data(delta_size);\n+\t\tif (dry_run || !delta_data) {\n+\t\t\tfree(delta_data);\n+\t\t\treturn;\n+\t\t}\n+\t\tlo = 0;\n+\t\thi = nr;\n+\t\twhile (lo < hi) {\n+\t\t\tmid = (lo + hi)/2;\n+\t\t\tif (base_offset < obj_list[mid].offset) {\n+\t\t\t\thi = mid;\n+\t\t\t} else if (base_offset > obj_list[mid].offset) {\n+\t\t\t\tlo = mid + 1;\n+\t\t\t} else {\n+\t\t\t\thashcpy(base_sha1, obj_list[mid].sha1);\n+\t\t\t\tbase_found = !is_null_sha1(base_sha1);\n+\t\t\t\tbreak;\n+\t\t\t}\n+\t\t}\n+\t\tif (!base_found) {\n+\t\t\t/* The delta base object is itself a delta that\n+\t\t\t   has not been\tresolved yet. */\n+\t\t\thashcpy(obj_list[nr].sha1, null_sha1);\n+\t\t\tadd_delta_to_list(nr, null_sha1, base_offset, delta_data, delta_size);\n+\t\t\treturn;\n+\t\t}\n \t}\n+\n \tbase = read_sha1_file(base_sha1, type, &base_size);\n \tif (!base) {\n \t\terror(\"failed to read delta-pack base object %s\",\n@@ -197,7 +266,7 @@ static void unpack_delta_entry(unsigned \n \t\thas_errors = 1;\n \t\treturn;\n \t}\n-\tresolve_delta(type, base, base_size, delta_data, delta_size);\n+\tresolve_delta(nr, type, base, base_size, delta_data, delta_size);\n \tfree(base);\n }\n \n@@ -208,6 +277,8 @@ static void unpack_one(unsigned nr, unsi\n \tunsigned long size;\n \tenum object_type type;\n \n+\tobj_list[nr].offset = consumed_bytes;\n+\n \tpack = fill(1);\n \tc = *pack;\n \tuse(1);\n@@ -216,7 +287,7 @@ static void unpack_one(unsigned nr, unsi\n \tshift = 4;\n \twhile (c & 0x80) {\n \t\tpack = fill(1);\n-\t\tc = *pack++;\n+\t\tc = *pack;\n \t\tuse(1);\n \t\tsize += (c & 0x7f) << shift;\n \t\tshift += 7;\n@@ -225,13 +296,14 @@ static void unpack_one(unsigned nr, unsi\n \t\tstatic unsigned long last_sec;\n \t\tstatic unsigned last_percent;\n \t\tstruct timeval now;\n-\t\tunsigned percentage = (nr * 100) / total;\n+\t\tunsigned percentage = ((nr+1) * 100) / total;\n \n \t\tgettimeofday(&now, NULL);\n \t\tif (percentage != last_percent || now.tv_sec != last_sec) {\n \t\t\tlast_sec = now.tv_sec;\n \t\t\tlast_percent = percentage;\n-\t\t\tfprintf(stderr, \"%4u%% (%u/%u) done\\r\", percentage, nr, total);\n+\t\t\tfprintf(stderr, \"%4u%% (%u/%u) done\\r\",\n+\t\t\t\t\tpercentage, (nr+1), total);\n \t\t}\n \t}\n \tswitch (type) {\n@@ -239,10 +311,11 @@ static void unpack_one(unsigned nr, unsi\n \tcase OBJ_TREE:\n \tcase OBJ_BLOB:\n \tcase OBJ_TAG:\n-\t\tunpack_non_delta_entry(type, size);\n+\t\tunpack_non_delta_entry(type, size, nr);\n \t\treturn;\n \tcase OBJ_REF_DELTA:\n-\t\tunpack_delta_entry(size);\n+\tcase OBJ_OFS_DELTA:\n+\t\tunpack_delta_entry(type, size, nr);\n \t\treturn;\n \tdefault:\n \t\terror(\"bad object type %d\", type);\n@@ -265,9 +338,10 @@ static void unpack_all(void)\n \t\tdie(\"unknown pack file version %d\", ntohl(hdr->hdr_version));\n \tfprintf(stderr, \"Unpacking %d objects\\n\", nr_objects);\n \n+\tobj_list = xmalloc(nr_objects * sizeof(*obj_list));\n \tuse(sizeof(struct pack_header));\n \tfor (i = 0; i < nr_objects; i++)\n-\t\tunpack_one(i+1, nr_objects);\n+\t\tunpack_one(i, nr_objects);\n \tif (delta_list)\n \t\tdie(\"unresolved deltas left after unpacking\");\n }\n"}]}