t1402: add some more tests
[gitweb.git] / diff-delta.c
index 9e440a9299b902bc96749ad2c86c08df6492eb1c..93385e12baa0d90ae475bd02500edf5ddcce320c 100644 (file)
@@ -4,7 +4,7 @@
  * This code was greatly inspired by parts of LibXDiff from Davide Libenzi
  * http://www.xmailserver.org/xdiff-lib.html
  *
- * Rewritten for GIT by Nicolas Pitre <nico@cam.org>, (C) 2005-2007
+ * Rewritten for GIT by Nicolas Pitre <nico@fluxnic.net>, (C) 2005-2007
  *
  * This code is free software; you can redistribute it and/or modify
  * it under the terms of the GNU General Public License version 2 as
@@ -146,7 +146,14 @@ struct delta_index * create_delta_index(const void *buf, unsigned long bufsize)
        /* Determine index hash size.  Note that indexing skips the
           first byte to allow for optimizing the Rabin's polynomial
           initialization in create_delta(). */
-       entries = (bufsize - 1)  / RABIN_WINDOW;
+       entries = (bufsize - 1) / RABIN_WINDOW;
+       if (bufsize >= 0xffffffffUL) {
+               /*
+                * Current delta format can't encode offsets into
+                * reference buffer with more than 32 bits.
+                */
+               entries = 0xfffffffeU / RABIN_WINDOW;
+       }
        hsize = entries / 4;
        for (i = 4; (1u << i) < hsize && i < 31; i++);
        hsize = 1 << i;
@@ -212,11 +219,24 @@ struct delta_index * create_delta_index(const void *buf, unsigned long bufsize)
                if (hash_count[i] <= HASH_LIMIT)
                        continue;
 
-               entries -= hash_count[i] - HASH_LIMIT;
                /* We leave exactly HASH_LIMIT entries in the bucket */
+               entries -= hash_count[i] - HASH_LIMIT;
 
                entry = hash[i];
                acc = 0;
+
+               /*
+                * Assume that this loop is gone through exactly
+                * HASH_LIMIT times and is entered and left with
+                * acc==0.  So the first statement in the loop
+                * contributes (hash_count[i]-HASH_LIMIT)*HASH_LIMIT
+                * to the accumulator, and the inner loop consequently
+                * is run (hash_count[i]-HASH_LIMIT) times, removing
+                * one element from the list each time.  Since acc
+                * balances out to 0 at the final run, the inner loop
+                * body can't be left with entry==NULL.  So we indeed
+                * encounter entry==NULL in the outer loop only.
+                */
                do {
                        acc += hash_count[i] - HASH_LIMIT;
                        if (acc > 0) {
@@ -229,30 +249,17 @@ struct delta_index * create_delta_index(const void *buf, unsigned long bufsize)
                        }
                        entry = entry->next;
                } while (entry);
-
-               /* Assume that this loop is gone through exactly
-                * HASH_LIMIT times and is entered and left with
-                * acc==0.  So the first statement in the loop
-                * contributes (hash_count[i]-HASH_LIMIT)*HASH_LIMIT
-                * to the accumulator, and the inner loop consequently
-                * is run (hash_count[i]-HASH_LIMIT) times, removing
-                * one element from the list each time.  Since acc
-                * balances out to 0 at the final run, the inner loop
-                * body can't be left with entry==NULL.  So we indeed
-                * encounter entry==NULL in the outer loop only.
-                */
        }
        free(hash_count);
 
-       /* Now create the packed index in array form rather than
-        * linked lists */
-
+       /*
+        * Now create the packed index in array form
+        * rather than linked lists.
+        */
        memsize = sizeof(*index)
                + sizeof(*packed_hash) * (hsize+1)
                + sizeof(*packed_entry) * entries;
-
        mem = malloc(memsize);
-
        if (!mem) {
                free(hash);
                return NULL;
@@ -264,24 +271,24 @@ struct delta_index * create_delta_index(const void *buf, unsigned long bufsize)
        index->src_size = bufsize;
        index->hash_mask = hmask;
 
-       mem = index + 1;
+       mem = index->hash;
        packed_hash = mem;
        mem = packed_hash + (hsize+1);
        packed_entry = mem;
 
-       /* Coalesce all entries belonging to one linked list into
-        * consecutive array entries */
-
        for (i = 0; i < hsize; i++) {
+               /*
+                * Coalesce all entries belonging to one linked list
+                * into consecutive array entries.
+                */
                packed_hash[i] = packed_entry;
                for (entry = hash[i]; entry; entry = entry->next)
                        *packed_entry++ = entry->entry;
        }
 
-       /* Sentinel value to indicate the length of the last hash
-        * bucket */
-
+       /* Sentinel value to indicate the length of the last hash bucket */
        packed_hash[hsize] = packed_entry;
+
        assert(packed_entry - (struct index_entry *)mem == entries);
        free(hash);