{"thread":{"id":"3839","subject":"[RFH] Exploration of an alternative diff_delta() algorithm","startedAt":"2006-04-09T14:31:17Z","lastAt":"2006-04-10T03:29:33Z","messageCount":9,"participants":["Peter Eriksen","Nicolas Pitre"],"isPatch":false,"patchVersion":null,"patchTotal":null},"messages":[{"id":"18498","messageId":"20060409143117.GA23908@erlang.gbar.dtu.dk","threadId":"3839","inReplyTo":null,"subject":"[RFH] Exploration of an alternative diff_delta() algorithm","fromName":"Peter Eriksen","fromEmail":"s022018@student.dtu.dk","sentAt":"2006-04-09T14:31:17Z","receivedAt":"2006-04-09T14:31:17Z","isPatch":false,"sender":{"key":"s022018@student.dtu.dk","avatar":null},"body":"Greetings Gitlings,\n\nI've been trying to implement an alternative algorithm\nfor diff_delta().  I'm getting close to something that\nworks, but now I'm stuck!  I think it has something to\ndo with pack-objects.c, but I'm not sure.  Here's the\nfirst test that fails:\n\n*** t5500-fetch-pack.sh ***\n* FAIL 1: 1st pull\n        git-fetch-pack -v .. B A > log.txt 2>&1\n* FAIL 2: fsck\n        git-fsck-objects --full > fsck.txt 2>&1\n* FAIL 3: new object count after 1st pull\n        test 33 = 0\n* FAIL 4: minimal count\n        test 33 = 0\n* FAIL 5: repack && prune-packed in client\n        (git-repack && git-prune-packed)2>>log.txt\n*   ok 5: 2nd pull\n*   ok 6: fsck\n* FAIL 7: new object count after 2nd pull\n        test 192 = 198\n* FAIL 8: minimal count\n        test 192 = 198\n* FAIL 9: repack && prune-packed in client\n        (git-repack && git-prune-packed)2>>log.txt\n*   ok 9: 3rd pull\n*   ok 10: fsck\n* FAIL 11: new object count after 3rd pull\n        test 3 = 228\n* FAIL 12: minimal count\n        test 3 = 30\n* failed 8 among 12 test(s)\n\nI've been looking all around the current diff_delta(), and I\ncan't see, what I'm missing.  Any ideas?  The file is meant to\nreplace the current diff-delta.c.\n\nPeter\n\n----->8--diff-delta.c----->8----\n#include <stdlib.h>\n#include <stdio.h>\n#include <string.h>\n#include \"delta.h\"\n\n\n#define BASE 257\n#define PREFIX_SIZE 3\n\n#define SIZE 10\n#define HASH_TABLE_SIZE (1<<SIZE)\n\n#define DELTA_SIZE (1024 * 1024)\n\n\nunsigned int init_hash(unsigned char* data) {\n  return data[0]*BASE*BASE + data[1]*BASE + data[2];\n}\n\nunsigned int hash(unsigned char* data, unsigned int hash) {\n  return (hash - data[-1]*BASE*BASE)*BASE + data[2];\n}\n\n#define GR_PRIME 0x9e370001\n#define HASH(v) ((v * GR_PRIME) >> (32 - SIZE))\n\nstruct entry {\n  char file;\n  char* offset;\n};\n\n\nvoid flush(struct entry* table) {\n  memset(table, 0, HASH_TABLE_SIZE * sizeof(struct entry));\n}\n\n\nint same_prefixes(char* data1, char* data2) {\n  return !memcmp(data1, data2, PREFIX_SIZE);  \n}\n\n\nvoid encode_add(char* out, int* outpos, char* version_start, char* version_copy) {\n  unsigned int size = version_copy - version_start;\n  if (!size) return;\n  int pos = *outpos;\n\n  while(size > 127) {\n    out[pos++] = 127;\n    memcpy(out + pos, version_start, 127);\n    pos += 127;\n    version_start += 127;\n    size -= 127;\n  }\n  out[pos++] = size;\n  memcpy(out + pos, version_start, size);  \n  pos += size;\n\n  *outpos = pos;\n}\n\n\nvoid encode_copy(char* out, int* outpos, int offset, int size) {\n     int pos = (*outpos) + 1;\n     int i = 0x80;\n\n     if (offset & 0xff) { out[pos++] = offset; i |= 0x01; }\n     offset >>= 8;\n     if (offset & 0xff) { out[pos++] = offset; i |= 0x02; }\n     offset >>= 8;\n     if (offset & 0xff) { out[pos++] = offset; i |= 0x04; }\n     offset >>= 8;\n     if (offset & 0xff) { out[pos++] = offset; i |= 0x08; }\n\n     if (size & 0xff) { out[pos++] = size; i |= 0x10; }\n     size >>= 8;\n     if (size & 0xff) { out[pos++] = size; i |= 0x20; }\n\n     out[*outpos] = i;\n     *outpos = pos;\n}\n\n\n\nvoid encode_size(char* out, int* outpos, unsigned long size) {\n  int pos = *outpos;\n  out[pos] = size;\n  size >>= 7;\n  while (size) {\n    out[pos++] |= 0x80;\n    out[pos] = size;\n    size >>= 7;\n  }\n  *outpos = ++pos;\n}\n\n\nvoid *diff_delta(void *from_buf, unsigned long from_size,\n\t\t void *to_buf, unsigned long to_size,\n\t\t unsigned long *delta_size,\n\t\t unsigned long max_size) {\n  int index;\n  int l;\n  char* base = from_buf;\n  char* version = to_buf;\n  unsigned long base_size = from_size;\n  unsigned long version_size = to_size;\n\n  char* base_copy = base;\n  char* version_copy = version;\n  struct entry* table = calloc(HASH_TABLE_SIZE, sizeof(struct entry));\n  //int delta_alloc = DELTA_SIZE;\n  char* delta = malloc(DELTA_SIZE);\n  int deltapos = 0;\n  char* base_top = base + base_size;\n  char* version_top = version + version_size;\n\n  encode_size(delta, &deltapos, base_size);\n  encode_size(delta, &deltapos, version_size);\n\n  char* base_offset = base;\n  char* version_offset = version;\n  unsigned int base_hash = init_hash(base);\n  unsigned int version_hash = init_hash(version);\n  char* version_start = version;\n\n  while(base_offset + PREFIX_SIZE < base_top && \n\tversion_offset  + PREFIX_SIZE < version_top) {  \n    // step2:\n    \n    index = HASH(base_hash);\n    switch (table[index].file) {\n    case '\\0': {\n      table[index].file = 'b';\n      table[index].offset = base_offset;\n      break;\n    }\n    case 'v': {\n      if (same_prefixes(base_offset, table[index].offset)) {\n\tbase_copy = base_offset;\n\tversion_copy = table[index].offset;\n\tgoto step3;\n      } else break;\n    }\n    case 'b': break;\n    default: printf(\"AAAAAARGH 2b\\n\");\n    }\n    \n    index = HASH(version_hash);\n    switch (table[index].file) {\n    case '\\0': {\n      table[index].file = 'v';\n      table[index].offset = version_offset;\n      break;\n    }\n    case 'b': {\n      if (same_prefixes(table[index].offset, version_offset)) {\n\tbase_copy = table[index].offset;\n\tversion_copy = version_offset;\n\tgoto step3;\n      } else break;\n    }\n    case 'v': break;\n    default: printf(\"AAAAAARGH 2v\\n\");\n    }\n    \n    base_offset++;\n    version_offset++;\n\n    base_hash = hash(base_offset, base_hash);\n    version_hash = hash(version_offset, version_hash);\n    continue;  //  goto step2;\n    \n  step3:\n    l = 0;\n    while(base_copy[l] == version_copy[l]) l++;\n    base_offset = base_copy + l;\n    version_offset = version_copy + l;\n    \n    /*\n    // Make sure we don't run out of delta buffer when encoding.\n    if((delta_alloc - deltapos) < \n       (version_start - version_copy) + 1 + 8 + (PREFIX_SIZE + 1)) {\n      delta_alloc = delta_alloc * 3 / 2;\n      delta = (char*) realloc(delta, delta_alloc);\n    }\n    */\n\tif(max_size && deltapos > max_size) {\n\t\tfree(delta);\n\t\tfree(table);\n\t\treturn NULL;\n\t}\n\n    // step4:\n    encode_add(delta, &deltapos, version_start, version_copy);\n    encode_copy(delta, &deltapos, base_copy - base, l);\n    \n    // step5:\n    flush(table);\n    \n    version_start = version_offset;\n    \n    base_hash = init_hash(base_offset);\n    version_hash = init_hash(version_offset);\n    \n  }  //  goto step2;\n  \n  encode_add(delta, &deltapos, version_start, version + version_size);\n  *delta_size = deltapos;\n\n  free(table);\n\n  return delta;\n}\n"},{"id":"18502","messageId":"Pine.LNX.4.64.0604091307460.2215@localhost.localdomain","threadId":"3839","inReplyTo":"20060409143117.GA23908@erlang.gbar.dtu.dk","subject":"Re: [RFH] Exploration of an alternative diff_delta() algorithm","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-04-09T17:14:31Z","receivedAt":"2006-04-09T17:14:31Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Sun, 9 Apr 2006, Peter Eriksen wrote:\n\n> Greetings Gitlings,\n> \n> I've been trying to implement an alternative algorithm\n> for diff_delta().  I'm getting close to something that\n> works, but now I'm stuck!  I think it has something to\n> do with pack-objects.c, but I'm not sure.  Here's the\n> first test that fails:\n> \n> *** t5500-fetch-pack.sh ***\n> * FAIL 1: 1st pull\n>         git-fetch-pack -v .. B A > log.txt 2>&1\n> * FAIL 2: fsck\n>         git-fsck-objects --full > fsck.txt 2>&1\n> * FAIL 3: new object count after 1st pull\n>         test 33 = 0\n> * FAIL 4: minimal count\n>         test 33 = 0\n> * FAIL 5: repack && prune-packed in client\n>         (git-repack && git-prune-packed)2>>log.txt\n> *   ok 5: 2nd pull\n> *   ok 6: fsck\n> * FAIL 7: new object count after 2nd pull\n>         test 192 = 198\n> * FAIL 8: minimal count\n>         test 192 = 198\n> * FAIL 9: repack && prune-packed in client\n>         (git-repack && git-prune-packed)2>>log.txt\n> *   ok 9: 3rd pull\n> *   ok 10: fsck\n> * FAIL 11: new object count after 3rd pull\n>         test 3 = 228\n> * FAIL 12: minimal count\n>         test 3 = 30\n> * failed 8 among 12 test(s)\n> \n> I've been looking all around the current diff_delta(), and I\n> can't see, what I'm missing.  Any ideas?  The file is meant to\n> replace the current diff-delta.c.\n\nNothing outside diff-delta.c and patch-delta.c is aware of the delta \ndata format.  So if your version is meant to be a transparent \nreplacement then it should pass all tests.  If it doesn't then it is \nbroken.\n\nTo help you play around you could try the test-delta utility (make \ntest-delta to build it).\n\nSo:\n\n\ttest-delta -d file1 file2 delta_file\n\ttest-delta -p file1 delta_file file3\n\tcmp file2 file3\n\nYou should always have file3 identical to file2.\n\n\nNicolas\n"},{"id":"18503","messageId":"20060409173409.GB23908@erlang.gbar.dtu.dk","threadId":"3839","inReplyTo":"Pine.LNX.4.64.0604091307460.2215@localhost.localdomain","subject":"Re: [RFH] Exploration of an alternative diff_delta() algorithm","fromName":"Peter Eriksen","fromEmail":"s022018@student.dtu.dk","sentAt":"2006-04-09T17:34:09Z","receivedAt":"2006-04-09T17:34:09Z","isPatch":false,"sender":{"key":"s022018@student.dtu.dk","avatar":null},"body":"On Sun, Apr 09, 2006 at 01:14:31PM -0400, Nicolas Pitre wrote:\n...\n> Nothing outside diff-delta.c and patch-delta.c is aware of the delta \n> data format.  So if your version is meant to be a transparent \n> replacement then it should pass all tests.  If it doesn't then it is \n> broken.\n> \n> To help you play around you could try the test-delta utility (make \n> test-delta to build it).\n> \n> So:\n> \n> \ttest-delta -d file1 file2 delta_file\n> \ttest-delta -p file1 delta_file file3\n> \tcmp file2 file3\n\nMy tests of these kinds doesn't show any errors.  Though, if file2 is\nempty, test-delta writes: \"file2: Invalid argument\".\n\nPeter\n"},{"id":"18504","messageId":"Pine.LNX.4.64.0604091333140.2215@localhost.localdomain","threadId":"3839","inReplyTo":"Pine.LNX.4.64.0604091307460.2215@localhost.localdomain","subject":"Re: [RFH] Exploration of an alternative diff_delta() algorithm","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-04-09T17:40:14Z","receivedAt":"2006-04-09T17:40:14Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Sun, 9 Apr 2006, Nicolas Pitre wrote:\n\n> On Sun, 9 Apr 2006, Peter Eriksen wrote:\n> \n> > Greetings Gitlings,\n> > \n> > I've been trying to implement an alternative algorithm\n> > for diff_delta().  I'm getting close to something that\n> > works, but now I'm stuck!\n> \n> Nothing outside diff-delta.c and patch-delta.c is aware of the delta \n> data format.  So if your version is meant to be a transparent \n> replacement then it should pass all tests.  If it doesn't then it is \n> broken.\n> \n> To help you play around you could try the test-delta utility (make \n> test-delta to build it).\n> \n> So:\n> \n> \ttest-delta -d file1 file2 delta_file\n> \ttest-delta -p file1 delta_file file3\n> \tcmp file2 file3\n> \n> You should always have file3 identical to file2.\n\nOut of curiosity I just tried your diff-delta version with test-delta \nand it produced a segmentation fault on the first attempt.\n\nIt also has lots of compilation warnings.\n\n\nNicolas\n"},{"id":"18505","messageId":"Pine.LNX.4.64.0604091340540.2215@localhost.localdomain","threadId":"3839","inReplyTo":"20060409173409.GB23908@erlang.gbar.dtu.dk","subject":"Re: [RFH] Exploration of an alternative diff_delta() algorithm","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-04-09T17:45:00Z","receivedAt":"2006-04-09T17:45:00Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Sun, 9 Apr 2006, Peter Eriksen wrote:\n\n> On Sun, Apr 09, 2006 at 01:14:31PM -0400, Nicolas Pitre wrote:\n> ...\n> > Nothing outside diff-delta.c and patch-delta.c is aware of the delta \n> > data format.  So if your version is meant to be a transparent \n> > replacement then it should pass all tests.  If it doesn't then it is \n> > broken.\n> > \n> > To help you play around you could try the test-delta utility (make \n> > test-delta to build it).\n> > \n> > So:\n> > \n> > \ttest-delta -d file1 file2 delta_file\n> > \ttest-delta -p file1 delta_file file3\n> > \tcmp file2 file3\n> \n> My tests of these kinds doesn't show any errors. \n\nTry this with the README file from the git source tree:\n\n\tsed s/git/GIT/g < ./README > /tmp/README.mod\n\ttest-delta -d ./README /tmp/README.mod /tmp/README.delta\n\t[BOOM!]\n\n> Though, if file2 is empty, test-delta writes: \"file2: Invalid \n> argument\".\n\nWe never delta against or towards empty files.\n\n\nNicolas\n"},{"id":"18506","messageId":"20060409175316.GA21455@erlang.gbar.dtu.dk","threadId":"3839","inReplyTo":"Pine.LNX.4.64.0604091333140.2215@localhost.localdomain","subject":"Re: [RFH] Exploration of an alternative diff_delta() algorithm","fromName":"Peter Eriksen","fromEmail":"s022018@student.dtu.dk","sentAt":"2006-04-09T17:53:16Z","receivedAt":"2006-04-09T17:53:16Z","isPatch":false,"sender":{"key":"s022018@student.dtu.dk","avatar":null},"body":"On Sun, Apr 09, 2006 at 01:40:14PM -0400, Nicolas Pitre wrote:\n...\n> Out of curiosity I just tried your diff-delta version with test-delta \n> and it produced a segmentation fault on the first attempt.\n\nYes, I get that too with your README example.\n\n> It also has lots of compilation warnings.\n\nHm, I don't get any warnings.  Would you mind pasting them, so I\ncan see what it's about?\n\nAt least now I have one segmentation fault to work on.  \nThanks.\n\nPeter\n"},{"id":"18507","messageId":"Pine.LNX.4.64.0604091401560.2215@localhost.localdomain","threadId":"3839","inReplyTo":"20060409175316.GA21455@erlang.gbar.dtu.dk","subject":"Re: [RFH] Exploration of an alternative diff_delta() algorithm","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-04-09T18:08:38Z","receivedAt":"2006-04-09T18:08:38Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Sun, 9 Apr 2006, Peter Eriksen wrote:\n\n> On Sun, Apr 09, 2006 at 01:40:14PM -0400, Nicolas Pitre wrote:\n> ...\n> > It also has lots of compilation warnings.\n> \n> Hm, I don't get any warnings.  Would you mind pasting them, so I\n> can see what it's about?\n\ngcc -o diff-delta.o -c -g -O2 -Wall -DSHA1_HEADER='<openssl/sha.h>'  diff-delta.c\ndiff-delta.c: In function 'diff_delta':\ndiff-delta.c:123: warning: pointer targets in passing argument 1 of 'init_hash' differ in signedness\ndiff-delta.c:124: warning: pointer targets in passing argument 1 of 'init_hash' differ in signedness\ndiff-delta.c:170: warning: pointer targets in passing argument 1 of 'hash' differ in signedness\ndiff-delta.c:171: warning: pointer targets in passing argument 1 of 'hash' differ in signedness\ndiff-delta.c:203: warning: pointer targets in passing argument 1 of 'init_hash' differ in signedness\ndiff-delta.c:204: warning: pointer targets in passing argument 1 of 'init_hash' differ in signedness\n\nAlso you should avoid declaring new variables after code in the same \nscope, like you do with version_offset for example.  This is a feature \nthat many C compilers don't support.\n\n\nNicolas\n"},{"id":"18521","messageId":"20060409224548.GB21455@erlang.gbar.dtu.dk","threadId":"3839","inReplyTo":"Pine.LNX.4.64.0604091340540.2215@localhost.localdomain","subject":"Re: [RFH] Exploration of an alternative diff_delta() algorithm","fromName":"Peter Eriksen","fromEmail":"s022018@student.dtu.dk","sentAt":"2006-04-09T22:45:48Z","receivedAt":"2006-04-09T22:45:48Z","isPatch":false,"sender":{"key":"s022018@student.dtu.dk","avatar":null},"body":"On Sun, Apr 09, 2006 at 01:45:00PM -0400, Nicolas Pitre wrote:\n...\n> Try this with the README file from the git source tree:\n> \n> \tsed s/git/GIT/g < ./README > /tmp/README.mod\n> \ttest-delta -d ./README /tmp/README.mod /tmp/README.delta\n> \t[BOOM!]\n\nI found the bug.  The code still has some limitations, but now\nit passes the test suite.  Thanks for your help, Nicolas.\n\nPeter\n\n----->8---diff-delta.c---->8-------\n#include <stdlib.h>\n#include <stdio.h>\n#include <string.h>\n#include \"delta.h\"\n\n\n#define BASE 257\n#define PREFIX_SIZE 3\n\n#define SIZE 10\n#define HASH_TABLE_SIZE (1<<SIZE)\n\n#define DELTA_SIZE (1024 * 1024)\n\n\nunsigned int init_hash(unsigned char* data) {\n  return data[0]*BASE*BASE + data[1]*BASE + data[2];\n}\n\nunsigned int hash(unsigned char* data, unsigned int hash) {\n  return (hash - data[-1]*BASE*BASE)*BASE + data[2];\n}\n\n#define GR_PRIME 0x9e370001\n#define HASH(v) ((v * GR_PRIME) >> (32 - SIZE))\n\nstruct entry {\n  char file;\n  char* offset;\n};\n\n\nvoid flush(struct entry* table) {\n  memset(table, 0, HASH_TABLE_SIZE * sizeof(struct entry));\n}\n\n\nint same_prefixes(char* data1, char* data2) {\n  return !memcmp(data1, data2, PREFIX_SIZE);  \n}\n\n\nvoid encode_add(char* out, int* outpos, char* version_start, char* version_copy) {\n  unsigned int size = version_copy - version_start;\n  if (!size) return;\n  int pos = *outpos;\n\n  while(size > 127) {\n    out[pos++] = 127;\n    memcpy(out + pos, version_start, 127);\n    pos += 127;\n    version_start += 127;\n    size -= 127;\n  }\n  out[pos++] = size;\n  memcpy(out + pos, version_start, size);  \n  pos += size;\n\n  *outpos = pos;\n}\n\n\nvoid encode_copy(char* out, int* outpos, int offset, int size) {\n     int pos = (*outpos) + 1;\n     int i = 0x80;\n\n     if (offset & 0xff) { out[pos++] = offset; i |= 0x01; }\n     offset >>= 8;\n     if (offset & 0xff) { out[pos++] = offset; i |= 0x02; }\n     offset >>= 8;\n     if (offset & 0xff) { out[pos++] = offset; i |= 0x04; }\n     offset >>= 8;\n     if (offset & 0xff) { out[pos++] = offset; i |= 0x08; }\n\n     if (size & 0xff) { out[pos++] = size; i |= 0x10; }\n     size >>= 8;\n     if (size & 0xff) { out[pos++] = size; i |= 0x20; }\n\n     out[*outpos] = i;\n     *outpos = pos;\n}\n\n\n\nvoid encode_size(char* out, int* outpos, unsigned long size) {\n  int pos = *outpos;\n  out[pos] = size;\n  size >>= 7;\n  while (size) {\n    out[pos++] |= 0x80;\n    out[pos] = size;\n    size >>= 7;\n  }\n  *outpos = ++pos;\n}\n\n\n\n\nvoid *diff_delta(void *from_buf, unsigned long from_size,\n\t\t void *to_buf, unsigned long to_size,\n\t\t unsigned long *delta_size,\n\t\t unsigned long max_size) {\n  unsigned int index;\n  unsigned int l;\n  unsigned char* base = from_buf;\n  unsigned char* version = to_buf;\n  unsigned long base_size = from_size;\n  unsigned long version_size = to_size;\n\n  unsigned char* base_copy = base;\n  unsigned char* version_copy = version;\n  struct entry* table = calloc(HASH_TABLE_SIZE, sizeof(struct entry));\n  //int delta_alloc = DELTA_SIZE;\n  unsigned char* delta = malloc(DELTA_SIZE);\n  unsigned int deltapos = 0;\n  unsigned char* base_top = base + base_size;\n  unsigned char* version_top = version + version_size;\n\n  encode_size(delta, &deltapos, base_size);\n  encode_size(delta, &deltapos, version_size);\n\n  unsigned char* base_offset = base;\n  unsigned char* version_offset = version;\n  unsigned int base_hash = init_hash(base);\n  unsigned int version_hash = init_hash(version);\n  unsigned char* version_start = version;\n\n  while(base_offset - base + PREFIX_SIZE < base_top - base && \n\tversion_offset - version + PREFIX_SIZE < version_top - version) {  \n    // step2:\n\n    index = HASH(base_hash);\n    switch (table[index].file) {\n    case '\\0': {\n      table[index].file = 'b';\n      table[index].offset = base_offset;\n      break;\n    }\n    case 'v': {\n      if (same_prefixes(base_offset, table[index].offset)) {\n\tbase_copy = base_offset;\n\tversion_copy = table[index].offset;\n\tgoto step3;\n      } else break;\n    }\n    case 'b': break;\n    default: printf(\"AAAAAARGH 2b\\n\");\n    }\n    \n    index = HASH(version_hash);\n    switch (table[index].file) {\n    case '\\0': {\n      table[index].file = 'v';\n      table[index].offset = version_offset;\n      break;\n    }\n    case 'b': {\n      if (same_prefixes(table[index].offset, version_offset)) {\n\tbase_copy = table[index].offset;\n\tversion_copy = version_offset;\n\tgoto step3;\n      } else break;\n    }\n    case 'v': break;\n    default: printf(\"AAAAAARGH 2v\\n\");\n    }\n    \n    base_offset++;\n    version_offset++;\n\n    base_hash = hash(base_offset, base_hash);\n    version_hash = hash(version_offset, version_hash);\n    continue;  //  goto step2;\n    \n  step3:\n    l = 0;\n    while(base_copy[l] == version_copy[l] && base_copy + l < base_top && version_copy + l < version_top) l++;\n    base_offset = base_copy + l;\n    version_offset = version_copy + l;\n    \n    /*\n    // Make sure we don't run out of delta buffer when encoding.\n    if((delta_alloc - deltapos) < \n       (version_start - version_copy) + 1 + 8 + (PREFIX_SIZE + 1)) {\n      delta_alloc = delta_alloc * 3 / 2;\n      delta = (char*) realloc(delta, delta_alloc);\n    }\n    */\n\tif(max_size && deltapos > max_size) {\n\t\tfree(delta);\n\t\tfree(table);\n\t\treturn NULL;\n\t}\n\n\t//fprintf(stdout, \"add: pos %u, v_start %u, v_copy %u\\n\", \n\t//\tdeltapos, version_start - version, version_copy - version);\t\n\n\n    // step4:\n    encode_add(delta, &deltapos, version_start, version_copy);\n\n\t//fprintf(stdout, \"copy: pos %u, v_copy %u, l %u\\n\", \n\t//\tdeltapos, base_copy - base, l);\t\n\n\n    encode_copy(delta, &deltapos, base_copy - base, l);\n    \n    // step5:\n    flush(table);\n    \n    version_start = version_offset;\n    \n    base_hash = init_hash(base_offset);\n    version_hash = init_hash(version_offset);\n    \n\t//fprintf(stdout, \"3) pos %u, v_start %u, v %u, b %u\\n\", \n\t//\tdeltapos, version_start - version, version_offset - version, base_offset- base);\t\n  }  //  goto step2;\n  \n\t//fprintf(stdout, \"pos %u, v_start %u, v_top %u\\n\", \n\t//\tdeltapos, version_start - version, version_size);\t\n  encode_add(delta, &deltapos, version_start, version + version_size);\n  *delta_size = deltapos;\n  free(table);\n  return delta;\n}\n"},{"id":"18526","messageId":"Pine.LNX.4.64.0604092305000.2215@localhost.localdomain","threadId":"3839","inReplyTo":"20060409224548.GB21455@erlang.gbar.dtu.dk","subject":"Re: [RFH] Exploration of an alternative diff_delta() algorithm","fromName":"Nicolas Pitre","fromEmail":"nico@cam.org","sentAt":"2006-04-10T03:29:33Z","receivedAt":"2006-04-10T03:29:33Z","isPatch":false,"sender":{"key":"nico@fluxnic.net","avatar":"https://avatars.githubusercontent.com/u/702790?v=4"},"body":"On Mon, 10 Apr 2006, Peter Eriksen wrote:\n\n> On Sun, Apr 09, 2006 at 01:45:00PM -0400, Nicolas Pitre wrote:\n> ...\n> > Try this with the README file from the git source tree:\n> > \n> > \tsed s/git/GIT/g < ./README > /tmp/README.mod\n> > \ttest-delta -d ./README /tmp/README.mod /tmp/README.delta\n> > \t[BOOM!]\n> \n> I found the bug.  The code still has some limitations, but now\n> it passes the test suite.  Thanks for your help, Nicolas.\n\nOK here's some more meat for you:\n\nCopy the same README file from the git source tree, then edit the copied \nversion so the \"Blob Object\" section and the \"Tree Object\" section are \nswapped around like shown in the attached patch.\n\nThe best delta that can be achieved is 24 bytes.\n\nWith the current code the produced delta is 42 bytes.\n\nWith your code the resulting delta is 4978 bytes, about twice as large \nas the attached patch.\n\nOne major limitation of your algorithm appears to not have a global view \nof the base buffer before starting to find matches.\n\n\nNicolas\n\n\n--- f1\t2006-04-09 13:31:26.000000000 -0400\n+++ f2\t2006-04-09 23:04:10.000000000 -0400\n@@ -87,26 +87,6 @@\n \n The object types in some more detail:\n \n-Blob Object\n-~~~~~~~~~~~\n-A \"blob\" object is nothing but a binary blob of data, and doesn't\n-refer to anything else.  There is no signature or any other\n-verification of the data, so while the object is consistent (it 'is'\n-indexed by its sha1 hash, so the data itself is certainly correct), it\n-has absolutely no other attributes.  No name associations, no\n-permissions.  It is purely a blob of data (i.e. normally \"file\n-contents\").\n-\n-In particular, since the blob is entirely defined by its data, if two\n-files in a directory tree (or in multiple different versions of the\n-repository) have the same contents, they will share the same blob\n-object. The object is totally independent of its location in the\n-directory tree, and renaming a file does not change the object that\n-file is associated with in any way.\n-\n-A blob is typically created when gitlink:git-update-index[1]\n-is run, and its data can be accessed by gitlink:git-cat-file[1].\n-\n Tree Object\n ~~~~~~~~~~~\n The next hierarchical object type is the \"tree\" object.  A tree object\n@@ -147,6 +127,26 @@\n its data can be accessed by gitlink:git-ls-tree[1].\n Two trees can be compared with gitlink:git-diff-tree[1].\n \n+Blob Object\n+~~~~~~~~~~~\n+A \"blob\" object is nothing but a binary blob of data, and doesn't\n+refer to anything else.  There is no signature or any other\n+verification of the data, so while the object is consistent (it 'is'\n+indexed by its sha1 hash, so the data itself is certainly correct), it\n+has absolutely no other attributes.  No name associations, no\n+permissions.  It is purely a blob of data (i.e. normally \"file\n+contents\").\n+\n+In particular, since the blob is entirely defined by its data, if two\n+files in a directory tree (or in multiple different versions of the\n+repository) have the same contents, they will share the same blob\n+object. The object is totally independent of its location in the\n+directory tree, and renaming a file does not change the object that\n+file is associated with in any way.\n+\n+A blob is typically created when gitlink:git-update-index[1]\n+is run, and its data can be accessed by gitlink:git-cat-file[1].\n+\n Commit Object\n ~~~~~~~~~~~~~\n The \"commit\" object is an object that introduces the notion of\n"}]}