6 * Idea here is very simple.
8 * Almost all data we are interested in are text, but sometimes we have
9 * to deal with binary data. So we cut them into chunks delimited by
10 * LF byte, or 64-byte sequence, whichever comes first, and hash them.
12 * For those chunks, if the source buffer has more instances of it
13 * than the destination buffer, that means the difference are the
14 * number of bytes not copied from source to destination. If the
15 * counts are the same, everything was copied from source to
16 * destination. If the destination has more, everything was copied,
17 * and destination added more.
19 * We are doing an approximation so we do not really have to waste
20 * memory by actually storing the sequence. We just hash them into
21 * somewhere around 2^16 hashbuckets and count the occurrences.
24 /* Wild guess at the initial hash size */
25 #define INITIAL_HASH_SIZE 9
27 /* We leave more room in smaller hash but do not let it
28 * grow to have unused hole too much.
30 #define INITIAL_FREE(sz_log2) ((1<<(sz_log2))*(sz_log2-3)/(sz_log2))
32 /* A prime rather carefully chosen between 2^16..2^17, so that
33 * HASHBASE < INITIAL_FREE(17). We want to keep the maximum hashtable
34 * size under the current 2<<17 maximum, which can hold this many
35 * different values before overflowing to hashtable of size 2<<18.
37 #define HASHBASE 107927
46 struct spanhash data
[FLEX_ARRAY
];
49 static struct spanhash_top
*spanhash_rehash(struct spanhash_top
*orig
)
51 struct spanhash_top
*new_spanhash
;
53 int osz
= 1 << orig
->alloc_log2
;
56 new_spanhash
= xmalloc(st_add(sizeof(*orig
),
57 st_mult(sizeof(struct spanhash
), sz
)));
58 new_spanhash
->alloc_log2
= orig
->alloc_log2
+ 1;
59 new_spanhash
->free
= INITIAL_FREE(new_spanhash
->alloc_log2
);
60 memset(new_spanhash
->data
, 0, sizeof(struct spanhash
) * sz
);
61 for (i
= 0; i
< osz
; i
++) {
62 struct spanhash
*o
= &(orig
->data
[i
]);
66 bucket
= o
->hashval
& (sz
- 1);
68 struct spanhash
*h
= &(new_spanhash
->data
[bucket
++]);
70 h
->hashval
= o
->hashval
;
83 static struct spanhash_top
*add_spanhash(struct spanhash_top
*top
,
84 unsigned int hashval
, int cnt
)
89 lim
= (1 << top
->alloc_log2
);
90 bucket
= hashval
& (lim
- 1);
92 h
= &(top
->data
[bucket
++]);
98 return spanhash_rehash(top
);
101 if (h
->hashval
== hashval
) {
110 static int spanhash_cmp(const void *a_
, const void *b_
)
112 const struct spanhash
*a
= a_
;
113 const struct spanhash
*b
= b_
;
115 /* A count of zero compares at the end.. */
117 return !b
->cnt
? 0 : 1;
120 return a
->hashval
< b
->hashval
? -1 :
121 a
->hashval
> b
->hashval
? 1 : 0;
124 static struct spanhash_top
*hash_chars(struct diff_filespec
*one
)
127 unsigned int accum1
, accum2
, hashval
;
128 struct spanhash_top
*hash
;
129 unsigned char *buf
= one
->data
;
130 unsigned int sz
= one
->size
;
131 int is_text
= !diff_filespec_is_binary(one
);
133 i
= INITIAL_HASH_SIZE
;
134 hash
= xmalloc(st_add(sizeof(*hash
),
135 st_mult(sizeof(struct spanhash
), 1<<i
)));
136 hash
->alloc_log2
= i
;
137 hash
->free
= INITIAL_FREE(i
);
138 memset(hash
->data
, 0, sizeof(struct spanhash
) * (1<<i
));
143 unsigned int c
= *buf
++;
144 unsigned int old_1
= accum1
;
147 /* Ignore CR in CRLF sequence if text */
148 if (is_text
&& c
== '\r' && sz
&& *buf
== '\n')
151 accum1
= (accum1
<< 7) ^ (accum2
>> 25);
152 accum2
= (accum2
<< 7) ^ (old_1
>> 25);
154 if (++n
< 64 && c
!= '\n')
156 hashval
= (accum1
+ accum2
* 0x61) % HASHBASE
;
157 hash
= add_spanhash(hash
, hashval
, n
);
161 QSORT(hash
->data
, 1ul << hash
->alloc_log2
, spanhash_cmp
);
165 int diffcore_count_changes(struct diff_filespec
*src
,
166 struct diff_filespec
*dst
,
169 unsigned long *src_copied
,
170 unsigned long *literal_added
)
172 struct spanhash
*s
, *d
;
173 struct spanhash_top
*src_count
, *dst_count
;
174 unsigned long sc
, la
;
176 src_count
= dst_count
= NULL
;
178 src_count
= *src_count_p
;
180 src_count
= hash_chars(src
);
182 *src_count_p
= src_count
;
185 dst_count
= *dst_count_p
;
187 dst_count
= hash_chars(dst
);
189 *dst_count_p
= dst_count
;
196 unsigned dst_cnt
, src_cnt
;
198 break; /* we checked all in src */
200 if (d
->hashval
>= s
->hashval
)
207 if (d
->cnt
&& d
->hashval
== s
->hashval
) {
211 if (src_cnt
< dst_cnt
) {
212 la
+= dst_cnt
- src_cnt
;