blob: ba6cbee76ba0180db352d4baf0653af201304046 [file] [log] [blame]
Elijah Newrena64215b2023-02-24 00:09:30 +00001#include "git-compat-util.h"
Junio C Hamano65416752006-02-28 16:01:36 -08002#include "diffcore.h"
Junio C Hamano65416752006-02-28 16:01:36 -08003
Junio C Hamanoba23bbc2006-03-04 03:21:55 -08004/*
5 * Idea here is very simple.
6 *
Junio C Hamanoaf3abef2007-06-28 23:11:40 -07007 * Almost all data we are interested in are text, but sometimes we have
8 * to deal with binary data. So we cut them into chunks delimited by
9 * LF byte, or 64-byte sequence, whichever comes first, and hash them.
Junio C Hamanoba23bbc2006-03-04 03:21:55 -080010 *
Junio C Hamanoaf3abef2007-06-28 23:11:40 -070011 * For those chunks, if the source buffer has more instances of it
12 * than the destination buffer, that means the difference are the
13 * number of bytes not copied from source to destination. If the
14 * counts are the same, everything was copied from source to
15 * destination. If the destination has more, everything was copied,
16 * and destination added more.
Junio C Hamanoba23bbc2006-03-04 03:21:55 -080017 *
18 * We are doing an approximation so we do not really have to waste
19 * memory by actually storing the sequence. We just hash them into
20 * somewhere around 2^16 hashbuckets and count the occurrences.
Junio C Hamanoba23bbc2006-03-04 03:21:55 -080021 */
22
Junio C Hamanoc06c7962006-03-12 03:22:10 -080023/* Wild guess at the initial hash size */
Junio C Hamano28211042006-03-12 16:39:51 -080024#define INITIAL_HASH_SIZE 9
Junio C Hamanofc66d212006-03-12 20:32:06 -080025
Junio C Hamano28211042006-03-12 16:39:51 -080026/* We leave more room in smaller hash but do not let it
27 * grow to have unused hole too much.
28 */
29#define INITIAL_FREE(sz_log2) ((1<<(sz_log2))*(sz_log2-3)/(sz_log2))
Junio C Hamanoba23bbc2006-03-04 03:21:55 -080030
Junio C Hamanofc66d212006-03-12 20:32:06 -080031/* A prime rather carefully chosen between 2^16..2^17, so that
32 * HASHBASE < INITIAL_FREE(17). We want to keep the maximum hashtable
33 * size under the current 2<<17 maximum, which can hold this many
34 * different values before overflowing to hashtable of size 2<<18.
35 */
36#define HASHBASE 107927
37
Junio C Hamanoc06c7962006-03-12 03:22:10 -080038struct spanhash {
Linus Torvaldse31c9f22006-03-15 00:37:57 -080039 unsigned int hashval;
40 unsigned int cnt;
Junio C Hamanoc06c7962006-03-12 03:22:10 -080041};
42struct spanhash_top {
43 int alloc_log2;
44 int free;
45 struct spanhash data[FLEX_ARRAY];
46};
47
Junio C Hamanoc06c7962006-03-12 03:22:10 -080048static struct spanhash_top *spanhash_rehash(struct spanhash_top *orig)
49{
Brandon Williams94a5c5d2018-02-14 10:59:40 -080050 struct spanhash_top *new_spanhash;
Junio C Hamanoc06c7962006-03-12 03:22:10 -080051 int i;
52 int osz = 1 << orig->alloc_log2;
53 int sz = osz << 1;
54
Brandon Williams94a5c5d2018-02-14 10:59:40 -080055 new_spanhash = xmalloc(st_add(sizeof(*orig),
Jeff King50a6c8e2016-02-22 17:44:35 -050056 st_mult(sizeof(struct spanhash), sz)));
Brandon Williams94a5c5d2018-02-14 10:59:40 -080057 new_spanhash->alloc_log2 = orig->alloc_log2 + 1;
58 new_spanhash->free = INITIAL_FREE(new_spanhash->alloc_log2);
59 memset(new_spanhash->data, 0, sizeof(struct spanhash) * sz);
Junio C Hamanoc06c7962006-03-12 03:22:10 -080060 for (i = 0; i < osz; i++) {
61 struct spanhash *o = &(orig->data[i]);
62 int bucket;
63 if (!o->cnt)
64 continue;
65 bucket = o->hashval & (sz - 1);
66 while (1) {
Brandon Williams94a5c5d2018-02-14 10:59:40 -080067 struct spanhash *h = &(new_spanhash->data[bucket++]);
Junio C Hamanoc06c7962006-03-12 03:22:10 -080068 if (!h->cnt) {
69 h->hashval = o->hashval;
70 h->cnt = o->cnt;
Brandon Williams94a5c5d2018-02-14 10:59:40 -080071 new_spanhash->free--;
Junio C Hamanoc06c7962006-03-12 03:22:10 -080072 break;
73 }
74 if (sz <= bucket)
75 bucket = 0;
76 }
77 }
78 free(orig);
Brandon Williams94a5c5d2018-02-14 10:59:40 -080079 return new_spanhash;
Junio C Hamanoc06c7962006-03-12 03:22:10 -080080}
81
82static struct spanhash_top *add_spanhash(struct spanhash_top *top,
Linus Torvaldse31c9f22006-03-15 00:37:57 -080083 unsigned int hashval, int cnt)
Junio C Hamanoc06c7962006-03-12 03:22:10 -080084{
85 int bucket, lim;
86 struct spanhash *h;
87
88 lim = (1 << top->alloc_log2);
89 bucket = hashval & (lim - 1);
90 while (1) {
91 h = &(top->data[bucket++]);
92 if (!h->cnt) {
93 h->hashval = hashval;
Linus Torvalds3c7ceba2006-03-15 00:37:57 -080094 h->cnt = cnt;
Junio C Hamanoc06c7962006-03-12 03:22:10 -080095 top->free--;
96 if (top->free < 0)
97 return spanhash_rehash(top);
98 return top;
99 }
100 if (h->hashval == hashval) {
Linus Torvalds3c7ceba2006-03-15 00:37:57 -0800101 h->cnt += cnt;
Junio C Hamanoc06c7962006-03-12 03:22:10 -0800102 return top;
103 }
104 if (lim <= bucket)
105 bucket = 0;
106 }
107}
108
Linus Torvaldseb4d0e32007-10-02 19:28:19 -0700109static int spanhash_cmp(const void *a_, const void *b_)
110{
111 const struct spanhash *a = a_;
112 const struct spanhash *b = b_;
113
114 /* A count of zero compares at the end.. */
115 if (!a->cnt)
116 return !b->cnt ? 0 : 1;
117 if (!b->cnt)
118 return -1;
119 return a->hashval < b->hashval ? -1 :
120 a->hashval > b->hashval ? 1 : 0;
121}
122
Nguyễn Thái Ngọc Duyb78ea5f2018-09-21 17:57:19 +0200123static struct spanhash_top *hash_chars(struct repository *r,
124 struct diff_filespec *one)
Junio C Hamanoc06c7962006-03-12 03:22:10 -0800125{
Linus Torvalds3c7ceba2006-03-15 00:37:57 -0800126 int i, n;
Linus Torvaldse31c9f22006-03-15 00:37:57 -0800127 unsigned int accum1, accum2, hashval;
Junio C Hamanoc06c7962006-03-12 03:22:10 -0800128 struct spanhash_top *hash;
Junio C Hamanob9905fe2007-06-28 23:14:13 -0700129 unsigned char *buf = one->data;
130 unsigned int sz = one->size;
Nguyễn Thái Ngọc Duyb78ea5f2018-09-21 17:57:19 +0200131 int is_text = !diff_filespec_is_binary(r, one);
Junio C Hamanoc06c7962006-03-12 03:22:10 -0800132
133 i = INITIAL_HASH_SIZE;
Jeff King50a6c8e2016-02-22 17:44:35 -0500134 hash = xmalloc(st_add(sizeof(*hash),
Philip Oakley62e84522021-12-01 00:29:01 +0000135 st_mult(sizeof(struct spanhash), (size_t)1 << i)));
Junio C Hamanoc06c7962006-03-12 03:22:10 -0800136 hash->alloc_log2 = i;
Junio C Hamano28211042006-03-12 16:39:51 -0800137 hash->free = INITIAL_FREE(i);
Philip Oakley62e84522021-12-01 00:29:01 +0000138 memset(hash->data, 0, sizeof(struct spanhash) * ((size_t)1 << i));
Junio C Hamano65416752006-02-28 16:01:36 -0800139
Linus Torvalds3c7ceba2006-03-15 00:37:57 -0800140 n = 0;
141 accum1 = accum2 = 0;
Junio C Hamanoba23bbc2006-03-04 03:21:55 -0800142 while (sz) {
Linus Torvaldse31c9f22006-03-15 00:37:57 -0800143 unsigned int c = *buf++;
144 unsigned int old_1 = accum1;
Junio C Hamanoba23bbc2006-03-04 03:21:55 -0800145 sz--;
Junio C Hamanob9905fe2007-06-28 23:14:13 -0700146
147 /* Ignore CR in CRLF sequence if text */
148 if (is_text && c == '\r' && sz && *buf == '\n')
149 continue;
150
Linus Torvaldse31c9f22006-03-15 00:37:57 -0800151 accum1 = (accum1 << 7) ^ (accum2 >> 25);
152 accum2 = (accum2 << 7) ^ (old_1 >> 25);
Linus Torvalds3c7ceba2006-03-15 00:37:57 -0800153 accum1 += c;
154 if (++n < 64 && c != '\n')
155 continue;
156 hashval = (accum1 + accum2 * 0x61) % HASHBASE;
157 hash = add_spanhash(hash, hashval, n);
158 n = 0;
159 accum1 = accum2 = 0;
Junio C Hamanoba23bbc2006-03-04 03:21:55 -0800160 }
Elijah Newren1c5bc692024-01-13 04:26:13 +0000161 if (n > 0) {
162 hashval = (accum1 + accum2 * 0x61) % HASHBASE;
163 hash = add_spanhash(hash, hashval, n);
164 }
Philip Oakley62e84522021-12-01 00:29:01 +0000165 QSORT(hash->data, (size_t)1ul << hash->alloc_log2, spanhash_cmp);
Junio C Hamanoc06c7962006-03-12 03:22:10 -0800166 return hash;
Junio C Hamano65416752006-02-28 16:01:36 -0800167}
168
Nguyễn Thái Ngọc Duyb78ea5f2018-09-21 17:57:19 +0200169int diffcore_count_changes(struct repository *r,
170 struct diff_filespec *src,
Junio C Hamanod8c3d032007-06-28 22:54:37 -0700171 struct diff_filespec *dst,
Junio C Hamanoc06c7962006-03-12 03:22:10 -0800172 void **src_count_p,
173 void **dst_count_p,
Junio C Hamano65416752006-02-28 16:01:36 -0800174 unsigned long *src_copied,
175 unsigned long *literal_added)
176{
Linus Torvaldseb4d0e32007-10-02 19:28:19 -0700177 struct spanhash *s, *d;
Junio C Hamanoc06c7962006-03-12 03:22:10 -0800178 struct spanhash_top *src_count, *dst_count;
Junio C Hamanoba23bbc2006-03-04 03:21:55 -0800179 unsigned long sc, la;
180
Junio C Hamanoc06c7962006-03-12 03:22:10 -0800181 src_count = dst_count = NULL;
182 if (src_count_p)
183 src_count = *src_count_p;
184 if (!src_count) {
Nguyễn Thái Ngọc Duyb78ea5f2018-09-21 17:57:19 +0200185 src_count = hash_chars(r, src);
Junio C Hamanoc06c7962006-03-12 03:22:10 -0800186 if (src_count_p)
187 *src_count_p = src_count;
Junio C Hamanoba23bbc2006-03-04 03:21:55 -0800188 }
Junio C Hamanoc06c7962006-03-12 03:22:10 -0800189 if (dst_count_p)
190 dst_count = *dst_count_p;
191 if (!dst_count) {
Nguyễn Thái Ngọc Duyb78ea5f2018-09-21 17:57:19 +0200192 dst_count = hash_chars(r, dst);
Junio C Hamanoc06c7962006-03-12 03:22:10 -0800193 if (dst_count_p)
194 *dst_count_p = dst_count;
195 }
196 sc = la = 0;
197
Linus Torvaldseb4d0e32007-10-02 19:28:19 -0700198 s = src_count->data;
199 d = dst_count->data;
200 for (;;) {
Junio C Hamanoc06c7962006-03-12 03:22:10 -0800201 unsigned dst_cnt, src_cnt;
202 if (!s->cnt)
Linus Torvaldseb4d0e32007-10-02 19:28:19 -0700203 break; /* we checked all in src */
204 while (d->cnt) {
205 if (d->hashval >= s->hashval)
206 break;
Linus Torvalds77cd6ab2009-12-04 12:07:47 -0800207 la += d->cnt;
Linus Torvaldseb4d0e32007-10-02 19:28:19 -0700208 d++;
209 }
Junio C Hamanoc06c7962006-03-12 03:22:10 -0800210 src_cnt = s->cnt;
Linus Torvalds77cd6ab2009-12-04 12:07:47 -0800211 dst_cnt = 0;
212 if (d->cnt && d->hashval == s->hashval) {
213 dst_cnt = d->cnt;
214 d++;
215 }
Junio C Hamanoc06c7962006-03-12 03:22:10 -0800216 if (src_cnt < dst_cnt) {
217 la += dst_cnt - src_cnt;
218 sc += src_cnt;
219 }
220 else
221 sc += dst_cnt;
Linus Torvaldseb4d0e32007-10-02 19:28:19 -0700222 s++;
Junio C Hamanoc06c7962006-03-12 03:22:10 -0800223 }
Linus Torvalds77cd6ab2009-12-04 12:07:47 -0800224 while (d->cnt) {
225 la += d->cnt;
226 d++;
227 }
Junio C Hamanoc06c7962006-03-12 03:22:10 -0800228
229 if (!src_count_p)
230 free(src_count);
231 if (!dst_count_p)
232 free(dst_count);
Junio C Hamanoba23bbc2006-03-04 03:21:55 -0800233 *src_copied = sc;
234 *literal_added = la;
Junio C Hamanoba23bbc2006-03-04 03:21:55 -0800235 return 0;
Junio C Hamano65416752006-02-28 16:01:36 -0800236}