hashsig.c 7.89 KB
Newer Older
1 2 3 4 5 6
/*
 * Copyright (C) the libgit2 contributors. All rights reserved.
 *
 * This file is part of libgit2, distributed under the GNU GPL v2 with
 * a Linking Exception. For full terms see the included COPYING file.
 */
7
#include "git2/sys/hashsig.h"
8
#include "fileops.h"
9
#include "util.h"
10 11 12 13 14 15

typedef uint32_t hashsig_t;
typedef uint64_t hashsig_state;

#define HASHSIG_SCALE 100

16 17
#define HASHSIG_MAX_RUN 80
#define HASHSIG_HASH_START	0x012345678ABCDEF0LL
18
#define HASHSIG_HASH_SHIFT  5
19 20 21

#define HASHSIG_HASH_MIX(S,CH) \
	(S) = ((S) << HASHSIG_HASH_SHIFT) - (S) + (hashsig_state)(CH)
22 23

#define HASHSIG_HEAP_SIZE ((1 << 7) - 1)
24
#define HASHSIG_HEAP_MIN_SIZE 4
25

26
typedef int (*hashsig_cmp)(const void *a, const void *b, void *);
27 28 29 30 31 32 33 34 35 36

typedef struct {
	int size, asize;
	hashsig_cmp cmp;
	hashsig_t values[HASHSIG_HEAP_SIZE];
} hashsig_heap;

struct git_hashsig {
	hashsig_heap mins;
	hashsig_heap maxs;
37
	size_t lines;
38 39 40
	git_hashsig_option_t opt;
};

41 42
#define HEAP_LCHILD_OF(I) (((I)<<1)+1)
#define HEAP_RCHILD_OF(I) (((I)<<1)+2)
43 44 45 46 47 48 49 50 51
#define HEAP_PARENT_OF(I) (((I)-1)>>1)

static void hashsig_heap_init(hashsig_heap *h, hashsig_cmp cmp)
{
	h->size  = 0;
	h->asize = HASHSIG_HEAP_SIZE;
	h->cmp   = cmp;
}

52
static int hashsig_cmp_max(const void *a, const void *b, void *payload)
53 54
{
	hashsig_t av = *(const hashsig_t *)a, bv = *(const hashsig_t *)b;
55
	GIT_UNUSED(payload);
56 57 58
	return (av < bv) ? -1 : (av > bv) ? 1 : 0;
}

59
static int hashsig_cmp_min(const void *a, const void *b, void *payload)
60 61
{
	hashsig_t av = *(const hashsig_t *)a, bv = *(const hashsig_t *)b;
62
	GIT_UNUSED(payload);
63 64 65 66 67 68 69
	return (av > bv) ? -1 : (av < bv) ? 1 : 0;
}

static void hashsig_heap_up(hashsig_heap *h, int el)
{
	int parent_el = HEAP_PARENT_OF(el);

70
	while (el > 0 && h->cmp(&h->values[parent_el], &h->values[el], NULL) > 0) {
71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92
		hashsig_t t = h->values[el];
		h->values[el] = h->values[parent_el];
		h->values[parent_el] = t;

		el = parent_el;
		parent_el = HEAP_PARENT_OF(el);
	}
}

static void hashsig_heap_down(hashsig_heap *h, int el)
{
	hashsig_t v, lv, rv;

	/* 'el < h->size / 2' tests if el is bottom row of heap */

	while (el < h->size / 2) {
		int lel = HEAP_LCHILD_OF(el), rel = HEAP_RCHILD_OF(el), swapel;

		v  = h->values[el];
		lv = h->values[lel];
		rv = h->values[rel];

93
		if (h->cmp(&v, &lv, NULL) < 0 && h->cmp(&v, &rv, NULL) < 0)
94 95
			break;

96
		swapel = (h->cmp(&lv, &rv, NULL) < 0) ? lel : rel;
97 98 99 100 101 102 103 104 105 106 107

		h->values[el] = h->values[swapel];
		h->values[swapel] = v;

		el = swapel;
	}
}

static void hashsig_heap_sort(hashsig_heap *h)
{
	/* only need to do this at the end for signature comparison */
108
	git__qsort_r(h->values, h->size, sizeof(hashsig_t), h->cmp, NULL);
109 110 111 112 113 114 115 116 117 118
}

static void hashsig_heap_insert(hashsig_heap *h, hashsig_t val)
{
	/* if heap is not full, insert new element */
	if (h->size < h->asize) {
		h->values[h->size++] = val;
		hashsig_heap_up(h, h->size - 1);
	}

119 120 121 122 123
	/* if heap is full, pop top if new element should replace it */
	else if (h->cmp(&val, &h->values[0], NULL) > 0) {
		h->size--;
		h->values[0] = h->values[h->size];
		hashsig_heap_down(h, 0);
124 125 126 127
	}

}

128 129 130 131
typedef struct {
	int use_ignores;
	uint8_t ignore_ch[256];
} hashsig_in_progress;
132

133 134 135 136 137
static void hashsig_in_progress_init(
	hashsig_in_progress *prog, git_hashsig *sig)
{
	int i;

138 139 140 141 142
	/* no more than one can be set */
	assert(!(sig->opt & GIT_HASHSIG_IGNORE_WHITESPACE) ||
		   !(sig->opt & GIT_HASHSIG_SMART_WHITESPACE));

	if (sig->opt & GIT_HASHSIG_IGNORE_WHITESPACE) {
143 144 145
		for (i = 0; i < 256; ++i)
			prog->ignore_ch[i] = git__isspace_nonlf(i);
		prog->use_ignores = 1;
146
	} else if (sig->opt & GIT_HASHSIG_SMART_WHITESPACE) {
147 148 149
		for (i = 0; i < 256; ++i)
			prog->ignore_ch[i] = git__isspace(i);
		prog->use_ignores = 1;
150
	} else {
151
		memset(prog, 0, sizeof(*prog));
152 153 154 155 156
	}
}

static int hashsig_add_hashes(
	git_hashsig *sig,
157
	const uint8_t *data,
158 159 160
	size_t size,
	hashsig_in_progress *prog)
{
161 162 163 164 165 166 167 168 169 170 171 172 173 174
	const uint8_t *scan = data, *end = data + size;
	hashsig_state state = HASHSIG_HASH_START;
	int use_ignores = prog->use_ignores, len;
	uint8_t ch;

	while (scan < end) {
		state = HASHSIG_HASH_START;

		for (len = 0; scan < end && len < HASHSIG_MAX_RUN; ) {
			ch = *scan;

			if (use_ignores)
				for (; scan < end && git__isspace_nonlf(ch); ch = *scan)
					++scan;
175 176
			else if (sig->opt &
					 (GIT_HASHSIG_IGNORE_WHITESPACE | GIT_HASHSIG_SMART_WHITESPACE))
177 178 179 180
				for (; scan < end && ch == '\r'; ch = *scan)
					++scan;

			/* peek at next character to decide what to do next */
181
			if (sig->opt & GIT_HASHSIG_SMART_WHITESPACE)
182 183 184 185 186 187 188
				use_ignores = (ch == '\n');

			if (scan >= end)
				break;
			++scan;

			/* check run terminator */
189 190
			if (ch == '\n' || ch == '\0') {
				sig->lines++;
191
				break;
192
			}
193 194 195 196

			++len;
			HASHSIG_HASH_MIX(state, ch);
		}
197

198 199 200
		if (len > 0) {
			hashsig_heap_insert(&sig->mins, (hashsig_t)state);
			hashsig_heap_insert(&sig->maxs, (hashsig_t)state);
201

202 203 204
			while (scan < end && (*scan == '\n' || !*scan))
				++scan;
		}
205 206
	}

207
	prog->use_ignores = use_ignores;
208 209 210 211 212 213

	return 0;
}

static int hashsig_finalize_hashes(git_hashsig *sig)
{
214 215
	if (sig->mins.size < HASHSIG_HEAP_MIN_SIZE &&
		!(sig->opt & GIT_HASHSIG_ALLOW_SMALL_FILES)) {
216 217 218 219 220 221 222 223 224 225 226 227 228 229 230 231 232 233 234 235 236 237 238 239 240 241
		giterr_set(GITERR_INVALID,
			"File too small for similarity signature calculation");
		return GIT_EBUFS;
	}

	hashsig_heap_sort(&sig->mins);
	hashsig_heap_sort(&sig->maxs);

	return 0;
}

static git_hashsig *hashsig_alloc(git_hashsig_option_t opts)
{
	git_hashsig *sig = git__calloc(1, sizeof(git_hashsig));
	if (!sig)
		return NULL;

	hashsig_heap_init(&sig->mins, hashsig_cmp_min);
	hashsig_heap_init(&sig->maxs, hashsig_cmp_max);
	sig->opt = opts;

	return sig;
}

int git_hashsig_create(
	git_hashsig **out,
242 243
	const char *buf,
	size_t buflen,
244 245 246
	git_hashsig_option_t opts)
{
	int error;
247
	hashsig_in_progress prog;
248 249 250
	git_hashsig *sig = hashsig_alloc(opts);
	GITERR_CHECK_ALLOC(sig);

251 252 253
	hashsig_in_progress_init(&prog, sig);

	error = hashsig_add_hashes(sig, (const uint8_t *)buf, buflen, &prog);
254 255 256 257 258 259 260 261 262 263 264 265 266 267 268 269 270

	if (!error)
		error = hashsig_finalize_hashes(sig);

	if (!error)
		*out = sig;
	else
		git_hashsig_free(sig);

	return error;
}

int git_hashsig_create_fromfile(
	git_hashsig **out,
	const char *path,
	git_hashsig_option_t opts)
{
271
	uint8_t buf[0x1000];
272 273
	ssize_t buflen = 0;
	int error = 0, fd;
274
	hashsig_in_progress prog;
275 276 277 278 279 280 281 282
	git_hashsig *sig = hashsig_alloc(opts);
	GITERR_CHECK_ALLOC(sig);

	if ((fd = git_futils_open_ro(path)) < 0) {
		git__free(sig);
		return fd;
	}

283 284
	hashsig_in_progress_init(&prog, sig);

285 286
	while (!error) {
		if ((buflen = p_read(fd, buf, sizeof(buf))) <= 0) {
287
			if ((error = (int)buflen) < 0)
288 289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315 316 317 318 319 320 321 322
				giterr_set(GITERR_OS,
					"Read error on '%s' calculating similarity hashes", path);
			break;
		}

		error = hashsig_add_hashes(sig, buf, buflen, &prog);
	}

	p_close(fd);

	if (!error)
		error = hashsig_finalize_hashes(sig);

	if (!error)
		*out = sig;
	else
		git_hashsig_free(sig);

	return error;
}

void git_hashsig_free(git_hashsig *sig)
{
	git__free(sig);
}

static int hashsig_heap_compare(const hashsig_heap *a, const hashsig_heap *b)
{
	int matches = 0, i, j, cmp;

	assert(a->cmp == b->cmp);

	/* hash heaps are sorted - just look for overlap vs total */

	for (i = 0, j = 0; i < a->size && j < b->size; ) {
323
		cmp = a->cmp(&a->values[i], &b->values[j], NULL);
324 325 326 327 328 329 330 331 332 333 334 335 336 337 338

		if (cmp < 0)
			++i;
		else if (cmp > 0)
			++j;
		else {
			++i; ++j; ++matches;
		}
	}

	return HASHSIG_SCALE * (matches * 2) / (a->size + b->size);
}

int git_hashsig_compare(const git_hashsig *a, const git_hashsig *b)
{
339 340 341 342 343 344 345 346 347 348 349 350
	/* if we have no elements in either file then each file is either
	 * empty or blank.  if we're ignoring whitespace then the files are
	 * similar, otherwise they're dissimilar.
	 */
	if (a->mins.size == 0 && b->mins.size == 0) {
		if ((!a->lines && !b->lines) ||
			(a->opt & GIT_HASHSIG_IGNORE_WHITESPACE))
			return HASHSIG_SCALE;
		else
			return 0;
	}

351 352 353 354 355 356 357 358
	/* if we have fewer than the maximum number of elements, then just use
	 * one array since the two arrays will be the same
	 */
	if (a->mins.size < HASHSIG_HEAP_SIZE)
		return hashsig_heap_compare(&a->mins, &b->mins);
	else
		return (hashsig_heap_compare(&a->mins, &b->mins) +
				hashsig_heap_compare(&a->maxs, &b->maxs)) / 2;
359
}