{"thread":{"id":"450","subject":"[PATCH] delta compressed git","startedAt":"2005-05-03T01:30:08Z","lastAt":"2005-05-03T02:43:25Z","messageCount":2,"participants":["Chris Mason","Nicolas Pitre"],"isPatch":true,"patchVersion":1,"patchTotal":null},"messages":[{"id":"2429","messageId":"200505022130.10958.mason@suse.com","threadId":"450","inReplyTo":null,"subject":"[PATCH] delta compressed git","fromName":"Chris Mason","fromEmail":"mason@suse.com","sentAt":"2005-05-03T01:30:08Z","receivedAt":"2005-05-03T01:30:08Z","isPatch":true,"sender":{"key":"mason@suse.com","avatar":null},"body":"Hello everyone,\n\nHere's an early form of some code for delta compression in git archives.  It \nbuilds on top of my packed item patch from before.  Using this patch will \ncreate repositories that can't be read by unpatched git, and it is only ready \nfor light testing.  The file format might change slightly in later revs.\n\ndeltas live as subfiles in packed files, and the packed item header has the \nsha1 of the file the delta is against. deltas are never taken against deltas, \nonly whole files (so the chain length is only 1).  \n\nWhen importing all of Ingo's bk->cvs patches into git (28,000 changesets), \ndelta git applies the patches faster (2hrs vs 2.5hrs), consumes less space \n(900MB vs 2.5GB), and checks out the resulting git tree faster in hot and \ncold caches.\n\nAnother 200MB or so would be saved by packing trees and commits into the same \nfiles as the blobs.  This is easy to do, but makes the patch harder to \nmaintain because I need to move code around in commit-tree.c and \nwrite-tree.c.  So I've left those bits out for now.\n\nBecause the packed files are created per changeset, if a changeset only \nmodifies one file the delta will still end up using a whole block.  So, you \ncould get much higher space savings with a tool to walk back over existing \nchangesets and pack them together.  This doesn't exist yet, but wouldn't be \ndifficult, and I expect it to get close to the mercurial/bk repository sizes.\n\nThe patch uses zdelta for delta compression, which you can download here:\nhttp://cis.poly.edu/zdelta/\n\nI'm open to suggestions on better delta libs.  I picked this one because it \nwas easy to code.  In order for things to work with git you need to apply the \nattached zdelta.diff to the zdelta-2.1 sources.  It fixes a silly default in \nthe Makefile and a symbol collision with zlib.\n\n-chris\n\n\ndiff -ur zdelta-2.1.orig/infcodes.c zdelta-2.1/infcodes.c\n--- zdelta-2.1.orig/infcodes.c\t2003-10-26 19:30:09.000000000 -0500\n+++ zdelta-2.1/infcodes.c\t2005-05-02 16:03:37.000000000 -0400\n@@ -145,7 +145,7 @@\n     if (m >= MAX_MATCH && n >= 10) \n     {\n       UPDATE\n-      r = inflate_fast(c->lbits, c->dbits, c->zdbits, \n+      r = zd_inflate_fast(c->lbits, c->dbits, c->zdbits, \n \t\t       c->ltree, c->dtree, c->zdtree, s, z);\n       LOAD\n       if (r != ZD_OK)\nOnly in zdelta-2.1: infcodes.o\ndiff -ur zdelta-2.1.orig/inffast.c zdelta-2.1/inffast.c\n--- zdelta-2.1.orig/inffast.c\t2003-10-26 19:30:09.000000000 -0500\n+++ zdelta-2.1/inffast.c\t2005-05-02 16:03:20.000000000 -0400\n@@ -8,7 +8,7 @@\n /* zdelta:\n  *\n  * modified: \n- *          inflate_fast\n+ *          zd_inflate_fast\n  * added:\n  *          --\n  * removed:\n@@ -41,7 +41,7 @@\n /*\n  * zdelta: modified\n  */\n-int inflate_fast(bl, bd, bzd, tl, td, tzd, s, z)\n+int zd_inflate_fast(bl, bd, bzd, tl, td, tzd, s, z)\n uInt bl, bd, bzd;\n inflate_huft *tl;\n inflate_huft *td;\ndiff -ur zdelta-2.1.orig/inffast.h zdelta-2.1/inffast.h\n--- zdelta-2.1.orig/inffast.h\t2003-10-26 19:30:13.000000000 -0500\n+++ zdelta-2.1/inffast.h\t2005-05-02 16:02:58.000000000 -0400\n@@ -22,7 +22,7 @@\n \n #ifndef ZD_INFFAST_H\n #define ZD_INFFAST_H\n-extern int inflate_fast OF((\n+extern int zd_inflate_fast OF((\n     uInt,\n     uInt,\n     uInt,\ndiff -ur zdelta-2.1.orig/Makefile zdelta-2.1/Makefile\n--- zdelta-2.1.orig/Makefile\t2004-02-13 18:19:51.000000000 -0500\n+++ zdelta-2.1/Makefile\t2005-05-02 15:30:08.000000000 -0400\n@@ -35,7 +35,7 @@\n \n CC=gcc\n \n-CFLAGS= -O2 -W -Wall -pedantic -ansi -g -DREFNUM=2\n+CFLAGS= -O2 -W -Wall -pedantic -ansi -g -DREFNUM=1\n \n LDSHARED=$(CC)\n CPP=$(CC) -E\n\n\nIndex: Makefile\n===================================================================\n--- 89fdfd09b281fdf5071bc13a30ef683bd6851b61/Makefile  (mode:100644 sha1:2d2913b6b98ac836b43755b1304d2a838dad87dd)\n+++ uncommitted/Makefile  (mode:100644)\n@@ -36,7 +36,7 @@\n LIB_OBJS += diff.o\n \n LIBS = $(LIB_FILE)\n-LIBS += -lz\n+LIBS += -lzd -lz\n \n ifdef MOZILLA_SHA1\n   SHA1_HEADER=\"mozilla-sha1/sha1.h\"\nIndex: cache.h\n===================================================================\n--- 89fdfd09b281fdf5071bc13a30ef683bd6851b61/cache.h  (mode:100644 sha1:3277d48708f885fa1b7cc56c9d16061c65a2eeb9)\n+++ uncommitted/cache.h  (mode:100644)\n@@ -16,6 +16,7 @@\n \n #include SHA1_HEADER\n #include <zlib.h>\n+#include <zdlib.h>\n \n /*\n  * Basic data structures for the directory cache\n@@ -64,6 +65,18 @@\n \tchar name[0];\n };\n \n+struct packed_item {\n+\t/* length of compressed data */\n+\tunsigned long len;\n+\tstruct packed_item *next;\n+\t/* sha1 of uncompressed data */\n+\tchar sha1[20];\n+\tchar refsha1[20];\n+\tchar type[20];\n+\t/* compressed data */\n+\tchar *data;\n+};\n+\n #define CE_NAMEMASK  (0x0fff)\n #define CE_STAGEMASK (0x3000)\n #define CE_STAGESHIFT 12\n@@ -119,7 +132,7 @@\n \n /* Read and unpack a sha1 file into memory, write memory to a sha1 file */\n extern void * map_sha1_file(const unsigned char *sha1, unsigned long *size);\n-extern void * unpack_sha1_file(void *map, unsigned long mapsize, char *type, unsigned long *size);\n+extern void * unpack_sha1_file(const unsigned char *sha1, void *map, unsigned long mapsize, char *type, unsigned long *size);\n extern void * read_sha1_file(const unsigned char *sha1, char *type, unsigned long *size);\n extern int write_sha1_file(char *buf, unsigned long len, const char *type, unsigned char *return_sha1);\n \n@@ -135,6 +148,10 @@\n /* Convert to/from hex/sha1 representation */\n extern int get_sha1_hex(const char *hex, unsigned char *sha1);\n extern char *sha1_to_hex(const unsigned char *sha1);\t/* static buffer result! */\n+extern int pack_sha1_buffer(void *buf, unsigned long buf_len, char *type,\n+                            unsigned char *returnsha1, unsigned char *refsha1, \n+\t\t\t    struct packed_item **);\n+int write_packed_buffer(struct packed_item *head);\n \n /* General helper functions */\n extern void usage(const char *err);\nIndex: fsck-cache.c\n===================================================================\n--- 89fdfd09b281fdf5071bc13a30ef683bd6851b61/fsck-cache.c  (mode:100644 sha1:f9b1431dd8f4f3b426a7e410de952277aaa11401)\n+++ uncommitted/fsck-cache.c  (mode:100644)\n@@ -142,7 +142,7 @@\n \t\tif (map) {\n \t\t\tchar type[100];\n \t\t\tunsigned long size;\n-\t\t\tvoid *buffer = unpack_sha1_file(map, mapsize, type, &size);\n+\t\t\tvoid *buffer = unpack_sha1_file(sha1, map, mapsize, type, &size);\n \t\t\tif (!buffer)\n \t\t\t\treturn -1;\n \t\t\tif (check_sha1_signature(sha1, buffer, size, type) < 0)\nIndex: git-mktag.c\n===================================================================\n--- 89fdfd09b281fdf5071bc13a30ef683bd6851b61/git-mktag.c  (mode:100644 sha1:5d2830dc2bdfa2e76afc3fd4687db8faffaefba2)\n+++ uncommitted/git-mktag.c  (mode:100644)\n@@ -31,7 +31,7 @@\n \tif (map) {\n \t\tchar type[100];\n \t\tunsigned long size;\n-\t\tvoid *buffer = unpack_sha1_file(map, mapsize, type, &size);\n+\t\tvoid *buffer = unpack_sha1_file(sha1,map,mapsize,type,&size);\n \n \t\tif (buffer) {\n \t\t\tif (!strcmp(type, expected_type))\nIndex: sha1_file.c\n===================================================================\n--- 89fdfd09b281fdf5071bc13a30ef683bd6851b61/sha1_file.c  (mode:100644 sha1:db2880e389e556dd3a5eef02aa8a3bb235528057)\n+++ uncommitted/sha1_file.c  (mode:100644)\n@@ -139,31 +139,195 @@\n \treturn map;\n }\n \n-void * unpack_sha1_file(void *map, unsigned long mapsize, char *type, unsigned long *size)\n+static int find_packed_header(const unsigned char *sha1, char *buf, unsigned long buf_len,\n+\t\t              unsigned char *refsha1, char *type, unsigned long *offset)\n+{\n+\tchar *p;\n+\tp = buf;\n+\n+\t*offset = 0;\n+\twhile(p < buf + buf_len) {\n+\t\tunsigned long item_len;\n+\t\tunsigned char item_sha[20];\n+\t\tmemcpy(item_sha, p, 20);\n+\t\tsscanf(p + 20, \"%s %lu \", type, &item_len);\n+\t\tp += 20 + strlen(p + 20) + 1;\n+\t\tif (strcmp(type, \"delta\") == 0) {\n+\t\t\tmemcpy(refsha1, p, 20);\n+\t\t\tp += 20;\n+\t\t}\n+\t\tif (memcmp(item_sha, sha1, 20) == 0)\n+\t\t\treturn 0;\n+\t\t*offset += item_len;\n+\t}\n+\treturn -1;\n+}\n+\n+\n+static void * _unpack_sha1_file(z_stream *stream, const unsigned char *sha1, void *map, \n+\t\t\tunsigned long mapsize, char *type, unsigned long *size)\n {\n \tint ret, bytes;\n+\tchar buffer[8192];\n+\tchar *buf;\n+\n+\t/* Get the data stream */\n+\tmemset(stream, 0, sizeof(*stream));\n+\tstream->next_in = map;\n+\tstream->avail_in = mapsize;\n+\tstream->next_out = buffer;\n+\tstream->avail_out = sizeof(buffer);\n+\n+\tinflateInit(stream);\n+\tret = inflate(stream, 0);\n+\tif (ret < Z_OK) {\n+\t\treturn NULL;\n+\t}\n+\tif (sscanf(buffer, \"%10s %lu\", type, size) != 2) {\n+\t\treturn NULL;\n+\t}\n+\tbytes = strlen(buffer) + 1;\n+\tbuf = xmalloc(*size);\n+\n+\tmemcpy(buf, buffer + bytes, stream->total_out - bytes);\n+\tbytes = stream->total_out - bytes;\n+\tif (bytes < *size && ret == Z_OK) {\n+\t\tstream->next_out = buf + bytes;\n+\t\tstream->avail_out = *size - bytes;\n+\t\twhile (inflate(stream, Z_FINISH) == Z_OK)\n+\t\t\t/* nothing */;\n+\t}\n+\tinflateEnd(stream);\n+\treturn buf;\n+}\n+static int find_sha1_ref(unsigned char *sha1)\n+{\n+\tunsigned char foundsha1[20];\n \tz_stream stream;\n+\tchar *buf;\n+\tunsigned long header_len;\n+\tchar type[20];\n+\tchar *map;\n+\tunsigned long mapsize;\n+\tunsigned long offset;\n+\n+\tmap = map_sha1_file(sha1, &mapsize);\n+\tif (!map)\n+\t\treturn -1;\n+\tbuf = _unpack_sha1_file(&stream, sha1, map, mapsize, type, &header_len);\n+\n+\tif (!buf)\n+\t\tgoto fail;\n+\tif (strcmp(type, \"packed\"))\n+\t\tgoto fail;\n+        if (find_packed_header(sha1, buf, header_len, foundsha1, type, &offset))\n+\t\tgoto fail;\n+\tmunmap(map, mapsize);\n+\tfree(buf);\n+\n+\tif (strcmp(type, \"delta\"))\n+\t\treturn 0;\n+\tmemcpy(sha1, foundsha1, 20);\n+\treturn 0;\n+fail:\n+\tmunmap(map, mapsize);\n+\tfree(buf);\n+\treturn -1;\n+}\n+\n+static void * unpack_delta(char *refsha1, char *delta_start, \n+\t\t\t   unsigned long delta_len, char *type, \n+\t\t\t   unsigned long *size)\n+{\n+\tzd_stream dstream;\n+\tint ret, bytes;\n \tchar buffer[8192];\n \tchar *buf;\n+\tchar *refbuffer = NULL;\n+\tunsigned long refsize = 0;\n \n+\tmemset(&dstream, 0, sizeof(dstream));\n+\trefbuffer = read_sha1_file(refsha1, type, &refsize);\n+\tif (!refbuffer) {\n+\t\treturn NULL;\n+\t}\n+\tdstream.base[0] = refbuffer;\n+\tdstream.base_avail[0] = refsize;\n+\tdstream.refnum = 1;\n+\tdstream.next_in = delta_start;\n+\tdstream.avail_in = delta_len;\n+\tdstream.next_out = buffer;\n+\tdstream.avail_out = sizeof(buffer);\n+\tret = zd_inflateInit(&dstream);\n+\tret = zd_inflate(&dstream, 0);\n+\tif (sscanf(buffer, \"%10s %lu\", type, size) != 2) {\n+\t\tfree(refbuffer);\n+\t\treturn NULL;\n+\t}\n+\tbytes = strlen(buffer) + 1;\n+\tbuf = xmalloc(*size);\n+\tmemcpy(buf, buffer + bytes, \n+\t\tdstream.total_out - bytes);\n+\tbytes = dstream.total_out - bytes;\n+\tif (bytes < *size && ret == ZD_OK) {\n+\t\tdstream.next_out = buf + bytes;\n+\t\tdstream.avail_out = *size - bytes;\n+\t\twhile (zd_inflate(&dstream, ZD_FINISH) == ZD_OK)\n+\t\t\t/* nothing */;\n+\t}\n+\tzd_inflateEnd(&dstream);\n+\tfree(refbuffer);\n+\treturn buf;\n+}\n+\n+void * unpack_sha1_file(const unsigned char *sha1, void *map, \n+\t\t\tunsigned long mapsize, char *type, unsigned long *size)\n+{\n+\tint ret, bytes;\n+\tz_stream stream;\n+\tchar buffer[8192];\n+\tchar *buf;\n+\tunsigned long offset;\n+\tunsigned long header_len;\n+\tunsigned char refsha1[20];\n+\tunsigned char headertype[20];\n+\n+\tbuf = _unpack_sha1_file(&stream, sha1, map, mapsize, type, size);\n+\tif (!buf)\n+\t\treturn buf;\n+\tif (strcmp(type, \"packed\"))\n+\t\treturn buf;\n+\n+\tif (!sha1) {\n+\t\tfree(buf);\n+\t\treturn NULL;\n+\t}\n+\theader_len = *size;\n+        if (find_packed_header(sha1, buf, header_len, refsha1, headertype, &offset)) {\n+\t\tfree(buf);\n+\t\treturn NULL;\n+\t}\n+\toffset += stream.total_in;\n+\tfree(buf);\n+\tif (!strcmp(headertype, \"delta\"))\n+\t\treturn unpack_delta(refsha1, map+offset, mapsize-offset, type,size);\n \t/* Get the data stream */\n \tmemset(&stream, 0, sizeof(stream));\n-\tstream.next_in = map;\n-\tstream.avail_in = mapsize;\n+\tbuf = NULL;\n+\tstream.next_in = map + offset;\n+\tstream.avail_in = mapsize - offset;\n \tstream.next_out = buffer;\n \tstream.avail_out = sizeof(buffer);\n+\tret = inflateInit(&stream);\n \n-\tinflateInit(&stream);\n \tret = inflate(&stream, 0);\n-\tif (ret < Z_OK)\n-\t\treturn NULL;\n-\tif (sscanf(buffer, \"%10s %lu\", type, size) != 2)\n+\tif (sscanf(buffer, \"%10s %lu\", type, size) != 2) {\n \t\treturn NULL;\n-\n+\t}\n \tbytes = strlen(buffer) + 1;\n \tbuf = xmalloc(*size);\n-\n-\tmemcpy(buf, buffer + bytes, stream.total_out - bytes);\n+\tmemcpy(buf, buffer + bytes, \n+\t\tstream.total_out - bytes);\n \tbytes = stream.total_out - bytes;\n \tif (bytes < *size && ret == Z_OK) {\n \t\tstream.next_out = buf + bytes;\n@@ -182,7 +346,7 @@\n \n \tmap = map_sha1_file(sha1, &mapsize);\n \tif (map) {\n-\t\tbuf = unpack_sha1_file(map, mapsize, type, size);\n+\t\tbuf = unpack_sha1_file(sha1, map, mapsize, type, size);\n \t\tmunmap(map, mapsize);\n \t\treturn buf;\n \t}\n@@ -268,7 +432,8 @@\n \t/* Set it up */\n \tmemset(&stream, 0, sizeof(stream));\n \tdeflateInit(&stream, Z_BEST_COMPRESSION);\n-\tsize = deflateBound(&stream, len+hdrlen);\n+\t// size = zd_deflateBound(&stream, len+hdrlen);\n+\tsize = len + hdrlen + 12;\n \tcompressed = xmalloc(size);\n \n \t/* Compress it */\n@@ -413,3 +578,323 @@\n \t\treturn 1;\n \treturn 0;\n }\n+\n+static void *pack_delta_buffer(void *buf, unsigned long buf_len, char *metadata, int metadata_size, unsigned long *compsize, unsigned char *refsha1)\n+{\n+\tchar *compressed;\n+\tzd_stream stream;\n+\tunsigned long size;\n+\tchar *refbuffer = NULL;\n+\tchar reftype[20];\n+\tunsigned long refsize = 0;\n+\tint ret;\n+\n+\tif (find_sha1_ref(refsha1)) {\n+\t\treturn NULL;\n+\t}\n+\trefbuffer = read_sha1_file(refsha1, reftype, &refsize);\n+\n+\t/* note, we could just continue without the delta here */\n+\tif (!refbuffer) {\n+\t\tfree(refbuffer);\n+\t\treturn NULL;\n+\t}\n+\n+\t/* Set it up */\n+\tmemset(&stream, 0, sizeof(stream));\n+\t/* TODO, real deflate bound here */\n+\tsize = buf_len + metadata_size + 12;\n+\tcompressed = xmalloc(size);\n+\n+\t/*\n+\t * ASCII size + nul byte\n+\t */\t\n+\tstream.base[0] = refbuffer;\n+\tstream.base_avail[0] = refsize;\n+\tstream.refnum = 1;\n+\tstream.next_in = metadata;\n+\tstream.avail_in = metadata_size;\n+\tstream.next_out = compressed;\n+\tstream.avail_out = size;\n+\tret = zd_deflateInit(&stream, ZD_BEST_COMPRESSION);\n+\t/* TODO check for -ENOMEM */\n+\twhile ((ret = zd_deflate(&stream, 0)) == ZD_OK)\n+\t\t/* nothing */;\n+\n+\tstream.next_in = buf;\n+\tstream.avail_in = buf_len;\n+\t/* Compress it */\n+\twhile ((ret = zd_deflate(&stream, ZD_FINISH)) == ZD_OK)\n+\t\t/* nothing */;\n+\tret = zd_deflateEnd(&stream);\n+\tsize = stream.total_out;\n+\t*compsize = size;\n+\n+\t/* ugh, we're comparing the compressed size against the uncompressed size\n+\t * of the reference buffer.  But, this is as good as we can do without\n+\t * an extra read\n+\t */\n+\tif (size > refsize) {\n+\t\tfree(refbuffer);\n+\t\tfree(compressed);\n+\t\treturn NULL;\n+\t}\n+\tfree(refbuffer);\n+\treturn compressed;\n+}\n+\n+static void *pack_buffer(void *buf, unsigned long buf_len, char *metadata, int metadata_size, unsigned long *compsize)\n+{\n+\tchar *compressed;\n+\tz_stream stream;\n+\tunsigned long size;\n+\tint ret;\n+\n+\t/* Set it up */\n+\tmemset(&stream, 0, sizeof(stream));\n+\t/* TODO, real deflate bound here */\n+\tsize = buf_len + metadata_size + 12;\n+\tcompressed = xmalloc(size);\n+\n+\t/*\n+\t * ASCII size + nul byte\n+\t */\t\n+\tstream.next_in = metadata;\n+\tstream.avail_in = metadata_size;\n+\tstream.next_out = compressed;\n+\tstream.avail_out = size;\n+\tret = deflateInit(&stream, Z_BEST_COMPRESSION);\n+\t/* TODO check for -ENOMEM */\n+\twhile ((ret = deflate(&stream, 0)) == Z_OK)\n+\t\t/* nothing */;\n+\n+\tstream.next_in = buf;\n+\tstream.avail_in = buf_len;\n+\t/* Compress it */\n+\twhile ((ret = deflate(&stream, Z_FINISH)) == Z_OK)\n+\t\t/* nothing */;\n+\tret = deflateEnd(&stream);\n+\tsize = stream.total_out;\n+\t*compsize = size;\n+\treturn compressed;\n+}\n+\n+int pack_sha1_buffer(void *buf, unsigned long buf_len, char *type,\n+\t\t     unsigned char *returnsha1,\n+\t\t     unsigned char *refsha1,\n+\t\t     struct packed_item **packed_item)\n+{\n+\tunsigned char sha1[20];\n+\tSHA_CTX c;\n+\tchar *filename;\n+\tstruct stat st;\n+\tchar *compressed = NULL;\n+\tunsigned long size;\n+\tstruct packed_item *item;\n+\tchar *metadata = xmalloc(200);\n+\tint metadata_size;\n+\tint delta = 0;\n+\n+\t*packed_item = NULL;\n+\n+\tmetadata_size = 1 + sprintf(metadata, \"%s %lu\", type, buf_len);\n+\n+\t/* Sha1.. */\n+\tSHA1_Init(&c);\n+\tSHA1_Update(&c, metadata, metadata_size);\n+\tSHA1_Update(&c, buf, buf_len);\n+\tSHA1_Final(sha1, &c);\n+\n+\tif (returnsha1)\n+\t\tmemcpy(returnsha1, sha1, 20);\n+\n+\tfilename = sha1_file_name(sha1);\n+\tif (stat(filename, &st) == 0)\n+\t\tgoto out;\n+\n+\t\n+\tif (refsha1) {\n+\t\tcompressed = pack_delta_buffer(buf, buf_len, metadata, metadata_size, &size, refsha1);\n+\t\tdelta = (compressed != NULL);\n+\t}\n+\tif (!compressed) {\n+\t\tcompressed = pack_buffer(buf, buf_len, metadata, metadata_size, &size);\n+\t}\n+\tfree(metadata);\n+\tif (!compressed) {\n+\t\treturn -1;\n+\t}\n+\titem = xmalloc(sizeof(struct packed_item));\n+\tmemcpy(item->sha1, sha1, 20);\n+\tif (delta) {\n+\t\tstrcpy(item->type, \"delta\");\n+\t\tmemcpy(item->refsha1, refsha1, 20);\n+\t} else {\n+\t\tstrcpy(item->type, type);\n+\t\tmemset(item->refsha1, 0, 20);\n+\t}\n+\titem->len = size;\n+\titem->next = NULL;\n+\titem->data = compressed;\n+\t*packed_item = item;\n+out:\n+\treturn 0;\n+}\n+\n+static char *create_packed_header(struct packed_item *head, unsigned long *size)\n+{\n+\tchar *metadata = NULL;\n+\tint metadata_size = 0;\n+\t*size = 0;\n+\tint entry_size = 0;\n+\n+\twhile(head) {\n+\t\tchar *p;\n+\t\tmetadata = realloc(metadata, metadata_size + 220);\n+\t\tif (!metadata)\n+\t\t\treturn NULL;\n+\t\tp = metadata+metadata_size;\n+\t\tmemcpy(p, head->sha1, 20);\n+\t\tp += 20;\n+\t\tentry_size = 1 + sprintf(p, \"%s %lu\", head->type, head->len);\n+\t\tmetadata_size += entry_size + 20;\n+\t\tif (strcmp(head->type, \"delta\") == 0) {\n+\t\t\tmemcpy(p + entry_size, head->refsha1, 20);\n+\t\t\tmetadata_size += 20;\n+\t\t}\n+\n+\t\thead = head->next;\n+\t}\n+\t*size = metadata_size;\n+\treturn metadata;\n+}\n+\n+#define WRITE_BUFFER_SIZE 8192\n+static char write_buffer[WRITE_BUFFER_SIZE];\n+static unsigned long write_buffer_len;\n+\n+static int c_write(int fd, void *data, unsigned int len)\n+{\n+\twhile (len) {\n+\t\tunsigned int buffered = write_buffer_len;\n+\t\tunsigned int partial = WRITE_BUFFER_SIZE - buffered;\n+\t\tif (partial > len)\n+\t\t\tpartial = len;\n+\t\tmemcpy(write_buffer + buffered, data, partial);\n+\t\tbuffered += partial;\n+\t\tif (buffered == WRITE_BUFFER_SIZE) {\n+\t\t\tif (write(fd, write_buffer, WRITE_BUFFER_SIZE) != WRITE_BUFFER_SIZE)\n+\t\t\t\treturn -1;\n+\t\t\tbuffered = 0;\n+\t\t}\n+\t\twrite_buffer_len = buffered;\n+\t\tlen -= partial;\n+\t\tdata += partial;\n+ \t}\n+ \treturn 0;\n+}\n+\n+static int c_flush(int fd)\n+{\n+\tif (write_buffer_len) {\n+\t\tint left = write_buffer_len;\n+\t\tif (write(fd, write_buffer, left) != left)\n+\t\t\treturn -1;\n+\t\twrite_buffer_len = 0;\n+\t}\n+\treturn 0;\n+}\n+int write_packed_buffer(struct packed_item *head)\n+{\n+\tunsigned char sha1[20];\n+\tSHA_CTX c;\n+\tchar *filename;\n+\tchar *metadata = xmalloc(200);\n+\tchar *header;\n+\tint metadata_size;\n+\tint fd;\n+\tint ret = 0;\n+\tunsigned long header_len;\n+\tstruct packed_item *item;\n+\tchar *compressed;\n+\tz_stream stream;\n+\tunsigned long size;\n+\tint zdret;\n+\n+\theader = create_packed_header(head, &header_len);\n+\tmetadata_size = 1+sprintf(metadata, \"packed %lu\", header_len);\n+\t/* \n+\t * the header contains the sha1 of each item, so we only sha1 the\n+\t * header\n+\t */ \n+\tSHA1_Init(&c);\n+\tSHA1_Update(&c, metadata, metadata_size);\n+\tSHA1_Update(&c, header, header_len);\n+\tSHA1_Final(sha1, &c);\n+\n+\tfilename = strdup(sha1_file_name(sha1));\n+\tfd = open(filename, O_WRONLY | O_CREAT | O_EXCL, 0666);\n+\tif (fd < 0) {\n+\t\t/* add collision check! */\n+\t\tif (errno != EEXIST) {\n+\t\t\tret = -errno;\n+\t\t}\n+\t\tgoto out_nofile;\n+\t}\n+       /* compress just the header info */\n+        memset(&stream, 0, sizeof(stream));\n+        deflateInit(&stream, Z_BEST_COMPRESSION);\n+\t/* TODO, bounds check */\n+\tsize = header_len + metadata_size + 12;\n+        compressed = xmalloc(size);\n+\n+        stream.next_in = metadata;\n+        stream.avail_in = metadata_size;\n+        stream.next_out = compressed;\n+        stream.avail_out = size;\n+        while ((zdret = deflate(&stream, 0)) == Z_OK)\n+                /* nothing */;\n+        stream.next_in = header;\n+        stream.avail_in = header_len;\n+        while ((zdret = deflate(&stream, Z_FINISH)) == Z_OK)\n+                /* nothing */;\n+        zdret = deflateEnd(&stream);\n+        size = stream.total_out;\n+\n+\tc_write(fd, compressed, size);\n+\tfree(compressed);\n+\n+\titem = head;\n+\twhile(item) {\n+\t\tif (c_write(fd, item->data, item->len)) {\n+\t\t\tret = -EIO;\n+\t\t\tgoto out;\n+\t\t}\n+\t\titem = item->next;\n+\t}\n+\tif (c_flush(fd)) {\n+\t\tret = -EIO;\n+\t\tgoto out;\n+\t}\n+\titem = head;\n+\twhile(item) {\n+\t\tchar *item_file;\n+\t\tstruct packed_item *next = item->next;\n+\t\titem_file = sha1_file_name(item->sha1);\n+\t\tif (link(filename, item_file) && errno != EEXIST) {\n+\t\t\tret = -errno;\n+\t\t\tbreak;\n+\t\t}\n+\t\tfree(item->data);\n+\t\tfree(item);\n+\t\titem = next;\n+\t}\n+\tunlink(filename);\n+out:\n+\tclose(fd);\n+out_nofile:\n+\tfree(header);\n+\tfree(metadata);\n+\tfree(filename);\n+\treturn ret;\n+}\nIndex: update-cache.c\n===================================================================\n--- 89fdfd09b281fdf5071bc13a30ef683bd6851b61/update-cache.c  (mode:100644 sha1:16e1bb9aea6413db35039042289605124d759501)\n+++ uncommitted/update-cache.c  (mode:100644)\n@@ -31,55 +31,39 @@\n \treturn (unsigned long)ptr > (unsigned long)-1000L;\n }\n \n-static int index_fd(unsigned char *sha1, int fd, struct stat *st)\n+static int index_fd(unsigned char *sha1, unsigned char *refsha1, int fd, struct stat *st, struct packed_item **head, struct packed_item **tail, unsigned long *packed_size, int *packed_nr)\n {\n-\tz_stream stream;\n \tunsigned long size = st->st_size;\n-\tint max_out_bytes = size + 200;\n-\tvoid *out = xmalloc(max_out_bytes);\n-\tvoid *metadata = xmalloc(200);\n-\tint metadata_size;\n \tvoid *in;\n-\tSHA_CTX c;\n+\tint ret;\n+\tstruct packed_item *new_item;\n \n \tin = \"\";\n \tif (size)\n \t\tin = mmap(NULL, size, PROT_READ, MAP_PRIVATE, fd, 0);\n \tclose(fd);\n-\tif (!out || (int)(long)in == -1)\n+\tif ((int)(long)in == -1) {\n \t\treturn -1;\n-\n-\tmetadata_size = 1+sprintf(metadata, \"blob %lu\", size);\n-\n-\tSHA1_Init(&c);\n-\tSHA1_Update(&c, metadata, metadata_size);\n-\tSHA1_Update(&c, in, size);\n-\tSHA1_Final(sha1, &c);\n-\n-\tmemset(&stream, 0, sizeof(stream));\n-\tdeflateInit(&stream, Z_BEST_COMPRESSION);\n-\n-\t/*\n-\t * ASCII size + nul byte\n-\t */\t\n-\tstream.next_in = metadata;\n-\tstream.avail_in = metadata_size;\n-\tstream.next_out = out;\n-\tstream.avail_out = max_out_bytes;\n-\twhile (deflate(&stream, 0) == Z_OK)\n-\t\t/* nothing */;\n-\n-\t/*\n-\t * File content\n-\t */\n-\tstream.next_in = in;\n-\tstream.avail_in = size;\n-\twhile (deflate(&stream, Z_FINISH) == Z_OK)\n-\t\t/*nothing */;\n-\n-\tdeflateEnd(&stream);\n-\t\n-\treturn write_sha1_buffer(sha1, out, stream.total_out);\n+\t}\n+\tret = pack_sha1_buffer(in, size, \"blob\", sha1, refsha1, &new_item);\n+\tif (new_item) {\n+\t\tif (*tail)\n+\t\t\t(*tail)->next = new_item;\n+\t\t*tail = new_item;\n+\t\tif (!*head)\n+\t\t\t*head = new_item;\n+\t\t*packed_size += new_item->len;\n+\t\t*packed_nr++;\n+\t\tif (*packed_size > (512 * 1024) || *packed_nr > 1024) {\n+\t\t\twrite_packed_buffer(*head);\n+\t\t\t*head = NULL;\n+\t\t\t*tail = NULL;\n+\t\t\t*packed_size = 0;\n+\t\t\t*packed_nr = 0;\n+\t\t}\n+\t}\n+\tmunmap(in, size);\n+\treturn ret;\n }\n \n /*\n@@ -102,12 +86,14 @@\n \tce->ce_size = htonl(st->st_size);\n }\n \n-static int add_file_to_cache(char *path)\n+static int add_file_to_cache(char *path, struct packed_item **packed_head, struct packed_item **packed_tail, unsigned long *packed_size, int *packed_nr)\n {\n \tint size, namelen;\n \tstruct cache_entry *ce;\n \tstruct stat st;\n \tint fd;\n+\tint pos;\n+\tunsigned char *refsha1 = NULL;\n \n \tfd = open(path, O_RDONLY);\n \tif (fd < 0) {\n@@ -129,8 +115,12 @@\n \tfill_stat_cache_info(ce, &st);\n \tce->ce_mode = create_ce_mode(st.st_mode);\n \tce->ce_flags = htons(namelen);\n+\tpos = cache_name_pos(ce->name, namelen);\n+\tif (pos >= 0)\n+\t\trefsha1 = active_cache[pos]->sha1;\n \n-\tif (index_fd(ce->sha1, fd, &st) < 0)\n+\tif (index_fd(ce->sha1, refsha1, fd, &st, packed_head, \n+\t\t     packed_tail, packed_size, packed_nr) < 0)\n \t\treturn -1;\n \n \treturn add_cache_entry(ce, allow_add);\n@@ -311,6 +301,10 @@\n \tint allow_options = 1;\n \tstatic char lockfile[MAXPATHLEN+1];\n \tconst char *indexfile = get_index_file();\n+\tstruct packed_item *packed_head = NULL;\n+\tstruct packed_item *packed_tail = NULL;\n+\tunsigned long packed_size = 0;\n+\tint packed_nr = 0;\n \n \tsnprintf(lockfile, sizeof(lockfile), \"%s.lock\", indexfile);\n \n@@ -362,8 +356,13 @@\n \t\t\tfprintf(stderr, \"Ignoring path %s\\n\", argv[i]);\n \t\t\tcontinue;\n \t\t}\n-\t\tif (add_file_to_cache(path))\n+\t\tif (add_file_to_cache(path, &packed_head, &packed_tail, &packed_size, &packed_nr))\n \t\t\tdie(\"Unable to add %s to database\", path);\n+\n+\t}\n+\tif (packed_head) {\n+\t\tif (write_packed_buffer(packed_head))\n+\t\t\tdie(\"write packed buffer failed\");\n \t}\n \tif (write_cache(newfd, active_cache, active_nr) || rename(lockfile, indexfile))\n \t\tdie(\"Unable to write new cachefile\");\nIndex: write-tree.c\n===================================================================\n--- 89fdfd09b281fdf5071bc13a30ef683bd6851b61/write-tree.c  (mode:100644 sha1:168352853d37bdca71d68ad8312b87b84477dea1)\n+++ uncommitted/write-tree.c  (mode:100644)\n@@ -5,24 +5,13 @@\n  */\n #include \"cache.h\"\n \n-static int check_valid_sha1(unsigned char *sha1)\n-{\n-\tchar *filename = sha1_file_name(sha1);\n-\tint ret;\n-\n-\t/* If we were anal, we'd check that the sha1 of the contents actually matches */\n-\tret = access(filename, R_OK);\n-\tif (ret)\n-\t\tperror(filename);\n-\treturn ret;\n-}\n-\n-static int write_tree(struct cache_entry **cachep, int maxentries, const char *base, int baselen, unsigned char *returnsha1)\n+static int write_tree(struct cache_entry **cachep, int maxentries, const char *base, int baselen, unsigned char *returnsha1, struct packed_item **head)\n {\n \tunsigned char subdir_sha1[20];\n \tunsigned long size, offset;\n \tchar *buffer;\n \tint nr;\n+\tstruct packed_item *item;\n \n \t/* Guess at some random initial size */\n \tsize = 8192;\n@@ -50,7 +39,7 @@\n \t\tif (dirname) {\n \t\t\tint subdir_written;\n \n-\t\t\tsubdir_written = write_tree(cachep + nr, maxentries - nr, pathname, dirname-pathname+1, subdir_sha1);\n+\t\t\tsubdir_written = write_tree(cachep + nr, maxentries - nr, pathname, dirname-pathname+1, subdir_sha1, head);\n \t\t\tnr += subdir_written;\n \n \t\t\t/* Now we need to write out the directory entry into this tree.. */\n@@ -62,9 +51,6 @@\n \t\t\tsha1 = subdir_sha1;\n \t\t}\n \n-\t\tif (check_valid_sha1(sha1) < 0)\n-\t\t\texit(1);\n-\n \t\tentrylen = pathlen - baselen;\n \t\tif (offset + entrylen + 100 > size) {\n \t\t\tsize = alloc_nr(offset + entrylen + 100);\n@@ -77,7 +63,11 @@\n \t\tnr++;\n \t} while (nr < maxentries);\n \n-\twrite_sha1_file(buffer, offset, \"tree\", returnsha1);\n+\tpack_sha1_buffer(buffer, offset, \"tree\", returnsha1, NULL, &item);\n+\tif (item) {\n+\t\titem->next = *head;\n+\t\t*head = item;\n+\t}\n \tfree(buffer);\n \treturn nr;\n }\n@@ -87,6 +77,7 @@\n \tint i, unmerged;\n \tint entries = read_cache();\n \tunsigned char sha1[20];\n+\tstruct packed_item *head = NULL;\n \n \tif (entries <= 0)\n \t\tdie(\"write-tree: no cache contents to write\");\n@@ -107,8 +98,12 @@\n \t\tdie(\"write-tree: not able to write tree\");\n \n \t/* Ok, write it out */\n-\tif (write_tree(active_cache, entries, \"\", 0, sha1) != entries)\n+\tif (write_tree(active_cache, entries, \"\", 0, sha1, &head) != entries)\n \t\tdie(\"write-tree: internal error\");\n+\tif (head) {\n+\t\tif (write_packed_buffer(head))\n+\t\t\tdie(\"write_packed_buffer error\");\n+\t}\n \tprintf(\"%s\\n\", sha1_to_hex(sha1));\n \treturn 0;\n }\n"},{"id":"2433","messageId":"Pine.LNX.4.62.0505022227280.14033@localhost.localdomain","threadId":"450","inReplyTo":"200505022130.10958.mason@suse.com","subject":"Re: [PATCH] delta compressed git","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2005-05-03T02:43:25Z","receivedAt":"2005-05-03T02:43:25Z","isPatch":true,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Mon, 2 May 2005, Chris Mason wrote:\n\n"}]}