hashsig.c 7.36 KB
Newer Older
1 2 3 4 5 6 7 8
/*
 * 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.
 */
#include "hashsig.h"
#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 37 38 39 40

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;
	git_hashsig_option_t opt;
	int considered;
};

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 138 139 140 141 142 143 144 145 146 147 148 149 150 151
static void hashsig_in_progress_init(
	hashsig_in_progress *prog, git_hashsig *sig)
{
	int i;

	switch (sig->opt) {
	case GIT_HASHSIG_IGNORE_WHITESPACE:
		for (i = 0; i < 256; ++i)
			prog->ignore_ch[i] = git__isspace_nonlf(i);
		prog->use_ignores = 1;
		break;
	case GIT_HASHSIG_SMART_WHITESPACE:
		for (i = 0; i < 256; ++i)
			prog->ignore_ch[i] = git__isspace(i);
		prog->use_ignores = 1;
		break;
	default:
		memset(prog, 0, sizeof(*prog));
		break;
152 153 154
	}
}

155 156
#define HASHSIG_IN_PROGRESS_INIT { 1 }

157 158
static int hashsig_add_hashes(
	git_hashsig *sig,
159
	const uint8_t *data,
160 161 162
	size_t size,
	hashsig_in_progress *prog)
{
163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 185 186 187 188 189 190 191 192 193 194 195
	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;
			else if (sig->opt != GIT_HASHSIG_NORMAL)
				for (; scan < end && ch == '\r'; ch = *scan)
					++scan;

			/* peek at next character to decide what to do next */
			if (sig->opt == GIT_HASHSIG_SMART_WHITESPACE)
				use_ignores = (ch == '\n');

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

			/* check run terminator */
			if (ch == '\n' || ch == '\0')
				break;

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

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

201
			sig->considered++;
202

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

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

	return 0;
}

static int hashsig_finalize_hashes(git_hashsig *sig)
{
215
	if (sig->mins.size < HASHSIG_HEAP_MIN_SIZE) {
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
	/* 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;
347
}