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
*spanhash_find(struct spanhash_top
*top
,
52 int sz
= 1 << top
->alloc_log2
;
53 int bucket
= hashval
& (sz
- 1);
55 struct spanhash
*h
= &(top
->data
[bucket
++]);
58 if (h
->hashval
== hashval
)
65 static struct spanhash_top
*spanhash_rehash(struct spanhash_top
*orig
)
67 struct spanhash_top
*new;
69 int osz
= 1 << orig
->alloc_log2
;
72 new = xmalloc(sizeof(*orig
) + sizeof(struct spanhash
) * sz
);
73 new->alloc_log2
= orig
->alloc_log2
+ 1;
74 new->free
= INITIAL_FREE(new->alloc_log2
);
75 memset(new->data
, 0, sizeof(struct spanhash
) * sz
);
76 for (i
= 0; i
< osz
; i
++) {
77 struct spanhash
*o
= &(orig
->data
[i
]);
81 bucket
= o
->hashval
& (sz
- 1);
83 struct spanhash
*h
= &(new->data
[bucket
++]);
85 h
->hashval
= o
->hashval
;
98 static struct spanhash_top
*add_spanhash(struct spanhash_top
*top
,
99 unsigned int hashval
, int cnt
)
104 lim
= (1 << top
->alloc_log2
);
105 bucket
= hashval
& (lim
- 1);
107 h
= &(top
->data
[bucket
++]);
109 h
->hashval
= hashval
;
113 return spanhash_rehash(top
);
116 if (h
->hashval
== hashval
) {
125 static struct spanhash_top
*hash_chars(unsigned char *buf
, unsigned int sz
)
128 unsigned int accum1
, accum2
, hashval
;
129 struct spanhash_top
*hash
;
131 i
= INITIAL_HASH_SIZE
;
132 hash
= xmalloc(sizeof(*hash
) + sizeof(struct spanhash
) * (1<<i
));
133 hash
->alloc_log2
= i
;
134 hash
->free
= INITIAL_FREE(i
);
135 memset(hash
->data
, 0, sizeof(struct spanhash
) * (1<<i
));
140 unsigned int c
= *buf
++;
141 unsigned int old_1
= accum1
;
143 accum1
= (accum1
<< 7) ^ (accum2
>> 25);
144 accum2
= (accum2
<< 7) ^ (old_1
>> 25);
146 if (++n
< 64 && c
!= '\n')
148 hashval
= (accum1
+ accum2
* 0x61) % HASHBASE
;
149 hash
= add_spanhash(hash
, hashval
, n
);
156 int diffcore_count_changes(struct diff_filespec
*src
,
157 struct diff_filespec
*dst
,
160 unsigned long delta_limit
,
161 unsigned long *src_copied
,
162 unsigned long *literal_added
)
165 struct spanhash_top
*src_count
, *dst_count
;
166 unsigned long sc
, la
;
168 src_count
= dst_count
= NULL
;
170 src_count
= *src_count_p
;
172 src_count
= hash_chars(src
->data
, src
->size
);
174 *src_count_p
= src_count
;
177 dst_count
= *dst_count_p
;
179 dst_count
= hash_chars(dst
->data
, dst
->size
);
181 *dst_count_p
= dst_count
;
185 ssz
= 1 << src_count
->alloc_log2
;
186 for (i
= 0; i
< ssz
; i
++) {
187 struct spanhash
*s
= &(src_count
->data
[i
]);
189 unsigned dst_cnt
, src_cnt
;
193 d
= spanhash_find(dst_count
, s
->hashval
);
194 dst_cnt
= d
? d
->cnt
: 0;
195 if (src_cnt
< dst_cnt
) {
196 la
+= dst_cnt
- src_cnt
;