{"thread":{"id":"5631","subject":"[PATCH 3/6] introduce delta objects with offset to base","startedAt":"2006-09-21T04:06:49Z","lastAt":"2006-09-21T04:06:49Z","messageCount":1,"participants":["Nicolas Pitre"],"isPatch":true,"patchVersion":1,"patchTotal":6},"messages":[{"id":"27329","messageId":"Pine.LNX.4.64.0609210005430.2627@xanadu.home","threadId":"5631","inReplyTo":null,"subject":"[PATCH 3/6] introduce delta objects with offset to base","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-09-21T04:06:49Z","receivedAt":"2006-09-21T04:06:49Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"This adds a new object, namely OBJ_OFS_DELTA, renames OBJ_DELTA to\nOBJ_REF_DELTA to better make the distinction between those two delta\nobjects, and adds support for the handling of those new delta objects\nin sha1_file.c only.\n\nThe OBJ_OFS_DELTA contains a relative offset from the delta object's\nposition in a pack instead of the 20-byte SHA1 reference to identify\nthe base object.  Since the base is likely to be not so far away, the\nrelative offset is more likely to have a smaller encoding on average\nthan an absolute offset.  And for those delta objects the base must\nalways be stored first because there is no way to know the distance of\nlater objects when streaming a pack.  Hence this relative offset is\nalways meant to be negative.\n\nThe offset encoding is slightly denser than the one used for object\nsize -- credits to <linux@horizon.com> (whoever this is) for bringing\nit to my attention.\n\nThis allows for pack size reduction between 3.2% (Linux-2.6) to over 5%\n(linux-historic).  Runtime pack access should be faster too since delta\nreplay does skip a search in the pack index for each delta in a chain.\n\nSigned-off-by: Nicolas Pitre <nico@cam.org>\n\ndiff --git a/builtin-pack-objects.c b/builtin-pack-objects.c\nindex 96c069a..c62734a 100644\n--- a/builtin-pack-objects.c\n+++ b/builtin-pack-objects.c\n@@ -232,7 +232,7 @@ static int encode_header(enum object_typ\n \tint n = 1;\n \tunsigned char c;\n \n-\tif (type < OBJ_COMMIT || type > OBJ_DELTA)\n+\tif (type < OBJ_COMMIT || type > OBJ_REF_DELTA)\n \t\tdie(\"bad type %d\", type);\n \n \tc = (type << 4) | (size & 15);\n@@ -297,7 +297,7 @@ static int revalidate_pack_entry(struct \n \tused = unpack_object_header_gently(data, len, &type, &size);\n \tif (!used)\n \t\treturn -1;\n-\tif (type == OBJ_DELTA)\n+\tif (type == OBJ_REF_DELTA)\n \t\tused += 20; /* skip base object name */\n \tdata += used;\n \tlen -= used;\n@@ -340,7 +340,7 @@ static unsigned long write_object(struct\n \tobj_type = entry->type;\n \tif (! entry->in_pack)\n \t\tto_reuse = 0;\t/* can't reuse what we don't have */\n-\telse if (obj_type == OBJ_DELTA)\n+\telse if (obj_type == OBJ_REF_DELTA)\n \t\tto_reuse = 1;\t/* check_object() decided it for us */\n \telse if (obj_type != entry->in_pack_type)\n \t\tto_reuse = 0;\t/* pack has delta which is unusable */\n@@ -380,7 +380,7 @@ static unsigned long write_object(struct\n \t\tif (entry->delta) {\n \t\t\tbuf = delta_against(buf, size, entry);\n \t\t\tsize = entry->delta_size;\n-\t\t\tobj_type = OBJ_DELTA;\n+\t\t\tobj_type = OBJ_REF_DELTA;\n \t\t}\n \t\t/*\n \t\t * The object header is a byte of 'type' followed by zero or\n@@ -409,11 +409,11 @@ static unsigned long write_object(struct\n \t\tsha1write(f, buf, datalen);\n \t\tunuse_packed_git(p);\n \t\thdrlen = 0; /* not really */\n-\t\tif (obj_type == OBJ_DELTA)\n+\t\tif (obj_type == OBJ_REF_DELTA)\n \t\t\treused_delta++;\n \t\treused++;\n \t}\n-\tif (obj_type == OBJ_DELTA)\n+\tif (obj_type == OBJ_REF_DELTA)\n \t\twritten_delta++;\n \twritten++;\n \treturn hdrlen + datalen;\n@@ -916,7 +916,7 @@ static void check_object(struct object_e\n \t\t * delta.\n \t\t */\n \t\tif (!no_reuse_delta &&\n-\t\t    entry->in_pack_type == OBJ_DELTA &&\n+\t\t    entry->in_pack_type == OBJ_REF_DELTA &&\n \t\t    (base_entry = locate_object_entry(base)) &&\n \t\t    (!base_entry->preferred_base)) {\n \n@@ -929,7 +929,7 @@ static void check_object(struct object_e\n \t\t\t/* uncompressed size of the delta data */\n \t\t\tentry->size = entry->delta_size = size;\n \t\t\tentry->delta = base_entry;\n-\t\t\tentry->type = OBJ_DELTA;\n+\t\t\tentry->type = OBJ_REF_DELTA;\n \n \t\t\tentry->delta_sibling = base_entry->delta_child;\n \t\t\tbase_entry->delta_child = entry;\ndiff --git a/builtin-unpack-objects.c b/builtin-unpack-objects.c\nindex 4f96bca..c6c6368 100644\n--- a/builtin-unpack-objects.c\n+++ b/builtin-unpack-objects.c\n@@ -241,7 +241,7 @@ static void unpack_one(unsigned nr, unsi\n \tcase OBJ_TAG:\n \t\tunpack_non_delta_entry(type, size);\n \t\treturn;\n-\tcase OBJ_DELTA:\n+\tcase OBJ_REF_DELTA:\n \t\tunpack_delta_entry(size);\n \t\treturn;\n \tdefault:\ndiff --git a/cache.h b/cache.h\nindex 42f13e2..7ecab65 100644\n--- a/cache.h\n+++ b/cache.h\n@@ -273,8 +273,9 @@ enum object_type {\n \tOBJ_TREE = 2,\n \tOBJ_BLOB = 3,\n \tOBJ_TAG = 4,\n-\t/* 5/6 for future expansion */\n-\tOBJ_DELTA = 7,\n+\t/* 5 for future expansion */\n+\tOBJ_OFS_DELTA = 6,\n+\tOBJ_REF_DELTA = 7,\n \tOBJ_BAD,\n };\n \ndiff --git a/index-pack.c b/index-pack.c\nindex 80bc6cb..aef7f0a 100644\n--- a/index-pack.c\n+++ b/index-pack.c\n@@ -158,7 +158,7 @@ static void *unpack_raw_entry(unsigned l\n \t}\n \n \tswitch (type) {\n-\tcase OBJ_DELTA:\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@@ -301,7 +301,7 @@ static void parse_pack_objects(void)\n \t\tdata = unpack_raw_entry(offset, &obj->type, &data_size,\n \t\t\t\t\tbase_sha1, &offset);\n \t\tobj->real_type = obj->type;\n-\t\tif (obj->type == OBJ_DELTA) {\n+\t\tif (obj->type == OBJ_REF_DELTA) {\n \t\t\tstruct delta_entry *delta = &deltas[nr_deltas++];\n \t\t\tdelta->obj = obj;\n \t\t\thashcpy(delta->base_sha1, base_sha1);\n@@ -328,7 +328,7 @@ static void parse_pack_objects(void)\n \t\tstruct object_entry *obj = &objects[i];\n \t\tint j, first, last;\n \n-\t\tif (obj->type == OBJ_DELTA)\n+\t\tif (obj->type == OBJ_REF_DELTA)\n \t\t\tcontinue;\n \t\tif (find_deltas_based_on_sha1(obj->sha1, &first, &last))\n \t\t\tcontinue;\n@@ -341,7 +341,7 @@ static void parse_pack_objects(void)\n \n \t/* Check for unresolved deltas */\n \tfor (i = 0; i < nr_deltas; i++) {\n-\t\tif (deltas[i].obj->real_type == OBJ_DELTA)\n+\t\tif (deltas[i].obj->real_type == OBJ_REF_DELTA)\n \t\t\tdie(\"packfile '%s' has unresolved deltas\",  pack_name);\n \t}\n }\ndiff --git a/sha1_file.c b/sha1_file.c\nindex 6fae766..66ebdde 100644\n--- a/sha1_file.c\n+++ b/sha1_file.c\n@@ -887,26 +887,61 @@ void * unpack_sha1_file(void *map, unsig\n \treturn unpack_sha1_rest(&stream, hdr, *size);\n }\n \n+static unsigned long get_delta_base(struct packed_git *p,\n+\t\t\t\t    unsigned long offset,\n+\t\t\t\t    enum object_type kind,\n+\t\t\t\t    unsigned long delta_obj_offset,\n+\t\t\t\t    unsigned long *base_obj_offset)\n+{\n+\tunsigned char *base_info = (unsigned char *) p->pack_base + offset;\n+\tunsigned long base_offset;\n+\n+\t/* there must be at least 20 bytes left regardless of delta type */\n+\tif (p->pack_size <= offset + 20)\n+\t\tdie(\"truncated pack file\");\n+\n+\tif (kind == OBJ_OFS_DELTA) {\n+\t\tunsigned used = 0;\n+\t\tunsigned char c = base_info[used++];\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\tc = base_info[used++];\n+\t\t\tbase_offset = (base_offset << 7) + (c & 127);\n+\t\t}\n+\t\tbase_offset = delta_obj_offset - base_offset;\n+\t\tif (base_offset >= delta_obj_offset)\n+\t\t\tdie(\"delta base offset out of bound\");\n+\t\toffset += used;\n+\t} else if (kind == OBJ_REF_DELTA) {\n+\t\t/* The base entry _must_ be in the same pack */\n+\t\tbase_offset = find_pack_entry_one(base_info, p);\n+\t\tif (!base_offset)\n+\t\t\tdie(\"failed to find delta-pack base object %s\",\n+\t\t\t\tsha1_to_hex(base_info));\n+\t\toffset += 20;\n+\t} else\n+\t\tdie(\"I am totally screwed\");\n+\t*base_obj_offset = base_offset;\n+\treturn offset;\n+}\n+\n /* forward declaration for a mutually recursive function */\n static int packed_object_info(struct packed_git *p, unsigned long offset,\n \t\t\t      char *type, unsigned long *sizep);\n \n static int packed_delta_info(struct packed_git *p,\n \t\t\t     unsigned long offset,\n+\t\t\t     enum object_type kind,\n+\t\t\t     unsigned long obj_offset,\n \t\t\t     char *type,\n \t\t\t     unsigned long *sizep)\n {\n \tunsigned long base_offset;\n-\tunsigned char *base_sha1 = (unsigned char *) p->pack_base + offset;\n \n-\tif (p->pack_size < offset + 20)\n-\t\tdie(\"truncated pack file\");\n-\t/* The base entry _must_ be in the same pack */\n-\tbase_offset = find_pack_entry_one(base_sha1, p);\n-\tif (!base_offset)\n-\t\tdie(\"failed to find delta-pack base object %s\",\n-\t\t    sha1_to_hex(base_sha1));\n-\toffset += 20;\n+\toffset = get_delta_base(p, offset, kind, obj_offset, &base_offset);\n \n \t/* We choose to only get the type of the base object and\n \t * ignore potentially corrupt pack file that expects the delta\n@@ -979,7 +1014,7 @@ int check_reuse_pack_delta(struct packed\n \tuse_packed_git(p);\n \tptr = offset;\n \tptr = unpack_object_header(p, ptr, kindp, sizep);\n-\tif (*kindp != OBJ_DELTA)\n+\tif (*kindp != OBJ_REF_DELTA)\n \t\tgoto done;\n \thashcpy(base, (unsigned char *) p->pack_base + ptr);\n \tstatus = 0;\n@@ -996,11 +1031,12 @@ void packed_object_info_detail(struct pa\n \t\t\t       unsigned int *delta_chain_length,\n \t\t\t       unsigned char *base_sha1)\n {\n-\tunsigned long val;\n+\tunsigned long obj_offset, val;\n \tunsigned char *next_sha1;\n \tenum object_type kind;\n \n \t*delta_chain_length = 0;\n+\tobj_offset = offset;\n \toffset = unpack_object_header(p, offset, &kind, size);\n \n \tfor (;;) {\n@@ -1015,7 +1051,13 @@ void packed_object_info_detail(struct pa\n \t\t\tstrcpy(type, type_names[kind]);\n \t\t\t*store_size = 0; /* notyet */\n \t\t\treturn;\n-\t\tcase OBJ_DELTA:\n+\t\tcase OBJ_OFS_DELTA:\n+\t\t\tget_delta_base(p, offset, kind, obj_offset, &offset);\n+\t\t\tif (*delta_chain_length == 0) {\n+\t\t\t\t/* TODO: find base_sha1 as pointed by offset */\n+\t\t\t}\n+\t\t\tbreak;\n+\t\tcase OBJ_REF_DELTA:\n \t\t\tif (p->pack_size <= offset + 20)\n \t\t\t\tdie(\"pack file %s records an incomplete delta base\",\n \t\t\t    \t    p->pack_name);\n@@ -1025,6 +1067,7 @@ void packed_object_info_detail(struct pa\n \t\t\toffset = find_pack_entry_one(next_sha1, p);\n \t\t\tbreak;\n \t\t}\n+\t\tobj_offset = offset;\n \t\toffset = unpack_object_header(p, offset, &kind, &val);\n \t\t(*delta_chain_length)++;\n \t}\n@@ -1033,15 +1076,15 @@ void packed_object_info_detail(struct pa\n static int packed_object_info(struct packed_git *p, unsigned long offset,\n \t\t\t      char *type, unsigned long *sizep)\n {\n-\tunsigned long size;\n+\tunsigned long size, obj_offset = offset;\n \tenum object_type kind;\n \n \toffset = unpack_object_header(p, offset, &kind, &size);\n \n-\tif (kind == OBJ_DELTA)\n-\t\treturn packed_delta_info(p, offset, type, sizep);\n-\n \tswitch (kind) {\n+\tcase OBJ_OFS_DELTA:\n+\tcase OBJ_REF_DELTA:\n+\t\treturn packed_delta_info(p, offset, kind, obj_offset, type, sizep);\n \tcase OBJ_COMMIT:\n \tcase OBJ_TREE:\n \tcase OBJ_BLOB:\n@@ -1087,23 +1130,15 @@ static void *unpack_compressed_entry(str\n static void *unpack_delta_entry(struct packed_git *p,\n \t\t\t\tunsigned long offset,\n \t\t\t\tunsigned long delta_size,\n+\t\t\t\tenum object_type kind,\n+\t\t\t\tunsigned long obj_offset,\n \t\t\t\tchar *type,\n \t\t\t\tunsigned long *sizep)\n {\n \tvoid *delta_data, *result, *base;\n \tunsigned long result_size, base_size, base_offset;\n-\tunsigned char *base_sha1;\n-\n-\tif (p->pack_size < offset + 20)\n-\t\tdie(\"truncated pack file\");\n-\t/* The base entry _must_ be in the same pack */\n-\tbase_sha1 = (unsigned char*)p->pack_base + offset;\n-\tbase_offset = find_pack_entry_one(base_sha1, p);\n-\tif (!base_offset)\n-\t\tdie(\"failed to find delta-pack base object %s\",\n-\t\t    sha1_to_hex(base_sha1));\n-\toffset += 20;\n \n+\toffset = get_delta_base(p, offset, kind, obj_offset, &base_offset);\n \tbase = unpack_entry_gently(p, base_offset, type, &base_size);\n \tif (!base)\n \t\tdie(\"failed to read delta base object at %lu from %s\",\n@@ -1140,13 +1175,14 @@ static void *unpack_entry(struct pack_en\n void *unpack_entry_gently(struct packed_git *p, unsigned long offset,\n \t\t\t  char *type, unsigned long *sizep)\n {\n-\tunsigned long size;\n+\tunsigned long size, obj_offset = offset;\n \tenum object_type kind;\n \n \toffset = unpack_object_header(p, offset, &kind, &size);\n \tswitch (kind) {\n-\tcase OBJ_DELTA:\n-\t\treturn unpack_delta_entry(p, offset, size, type, sizep);\n+\tcase OBJ_OFS_DELTA:\n+\tcase OBJ_REF_DELTA:\n+\t\treturn unpack_delta_entry(p, offset, size, kind, obj_offset, type, sizep);\n \tcase OBJ_COMMIT:\n \tcase OBJ_TREE:\n \tcase OBJ_BLOB:\n"}]}