Blame src/util.c

Packit ae9e2a
/*
Packit ae9e2a
 * Copyright (C) the libgit2 contributors. All rights reserved.
Packit ae9e2a
 *
Packit ae9e2a
 * This file is part of libgit2, distributed under the GNU GPL v2 with
Packit ae9e2a
 * a Linking Exception. For full terms see the included COPYING file.
Packit ae9e2a
 */
Packit ae9e2a
#include <git2.h>
Packit ae9e2a
#include "common.h"
Packit ae9e2a
#include <stdio.h>
Packit ae9e2a
#include <ctype.h>
Packit ae9e2a
#include "posix.h"
Packit ae9e2a
Packit ae9e2a
#ifdef GIT_WIN32
Packit ae9e2a
# include "win32/w32_buffer.h"
Packit ae9e2a
#endif
Packit ae9e2a
Packit ae9e2a
#ifdef _MSC_VER
Packit ae9e2a
# include <Shlwapi.h>
Packit ae9e2a
#endif
Packit ae9e2a
Packit ae9e2a
void git_strarray_free(git_strarray *array)
Packit ae9e2a
{
Packit ae9e2a
	size_t i;
Packit ae9e2a
Packit ae9e2a
	if (array == NULL)
Packit ae9e2a
		return;
Packit ae9e2a
Packit ae9e2a
	for (i = 0; i < array->count; ++i)
Packit ae9e2a
		git__free(array->strings[i]);
Packit ae9e2a
Packit ae9e2a
	git__free(array->strings);
Packit ae9e2a
Packit ae9e2a
	memset(array, 0, sizeof(*array));
Packit ae9e2a
}
Packit ae9e2a
Packit ae9e2a
int git_strarray_copy(git_strarray *tgt, const git_strarray *src)
Packit ae9e2a
{
Packit ae9e2a
	size_t i;
Packit ae9e2a
Packit ae9e2a
	assert(tgt && src);
Packit ae9e2a
Packit ae9e2a
	memset(tgt, 0, sizeof(*tgt));
Packit ae9e2a
Packit ae9e2a
	if (!src->count)
Packit ae9e2a
		return 0;
Packit ae9e2a
Packit ae9e2a
	tgt->strings = git__calloc(src->count, sizeof(char *));
Packit ae9e2a
	GITERR_CHECK_ALLOC(tgt->strings);
Packit ae9e2a
Packit ae9e2a
	for (i = 0; i < src->count; ++i) {
Packit ae9e2a
		if (!src->strings[i])
Packit ae9e2a
			continue;
Packit ae9e2a
Packit ae9e2a
		tgt->strings[tgt->count] = git__strdup(src->strings[i]);
Packit ae9e2a
		if (!tgt->strings[tgt->count]) {
Packit ae9e2a
			git_strarray_free(tgt);
Packit ae9e2a
			memset(tgt, 0, sizeof(*tgt));
Packit ae9e2a
			return -1;
Packit ae9e2a
		}
Packit ae9e2a
Packit ae9e2a
		tgt->count++;
Packit ae9e2a
	}
Packit ae9e2a
Packit ae9e2a
	return 0;
Packit ae9e2a
}
Packit ae9e2a
Packit ae9e2a
int git__strntol64(int64_t *result, const char *nptr, size_t nptr_len, const char **endptr, int base)
Packit ae9e2a
{
Packit ae9e2a
	const char *p;
Packit ae9e2a
	int64_t n, nn;
Packit ae9e2a
	int c, ovfl, v, neg, ndig;
Packit ae9e2a
Packit ae9e2a
	p = nptr;
Packit ae9e2a
	neg = 0;
Packit ae9e2a
	n = 0;
Packit ae9e2a
	ndig = 0;
Packit ae9e2a
	ovfl = 0;
Packit ae9e2a
Packit ae9e2a
	/*
Packit ae9e2a
	 * White space
Packit ae9e2a
	 */
Packit ae9e2a
	while (git__isspace(*p))
Packit ae9e2a
		p++;
Packit ae9e2a
Packit ae9e2a
	/*
Packit ae9e2a
	 * Sign
Packit ae9e2a
	 */
Packit ae9e2a
	if (*p == '-' || *p == '+')
Packit ae9e2a
		if (*p++ == '-')
Packit ae9e2a
			neg = 1;
Packit ae9e2a
Packit ae9e2a
	/*
Packit ae9e2a
	 * Base
Packit ae9e2a
	 */
Packit ae9e2a
	if (base == 0) {
Packit ae9e2a
		if (*p != '0')
Packit ae9e2a
			base = 10;
Packit ae9e2a
		else {
Packit ae9e2a
			base = 8;
Packit ae9e2a
			if (p[1] == 'x' || p[1] == 'X') {
Packit ae9e2a
				p += 2;
Packit ae9e2a
				base = 16;
Packit ae9e2a
			}
Packit ae9e2a
		}
Packit ae9e2a
	} else if (base == 16 && *p == '0') {
Packit ae9e2a
		if (p[1] == 'x' || p[1] == 'X')
Packit ae9e2a
			p += 2;
Packit ae9e2a
	} else if (base < 0 || 36 < base)
Packit ae9e2a
		goto Return;
Packit ae9e2a
Packit ae9e2a
	/*
Packit ae9e2a
	 * Non-empty sequence of digits
Packit ae9e2a
	 */
Packit ae9e2a
	for (; nptr_len > 0; p++,ndig++,nptr_len--) {
Packit ae9e2a
		c = *p;
Packit ae9e2a
		v = base;
Packit ae9e2a
		if ('0'<=c && c<='9')
Packit ae9e2a
			v = c - '0';
Packit ae9e2a
		else if ('a'<=c && c<='z')
Packit ae9e2a
			v = c - 'a' + 10;
Packit ae9e2a
		else if ('A'<=c && c<='Z')
Packit ae9e2a
			v = c - 'A' + 10;
Packit ae9e2a
		if (v >= base)
Packit ae9e2a
			break;
Packit ae9e2a
		v = neg ? -v : v;
Packit ae9e2a
		if (n > INT64_MAX / base || n < INT64_MIN / base) {
Packit ae9e2a
			ovfl = 1;
Packit ae9e2a
			/* Keep on iterating until the end of this number */
Packit ae9e2a
			continue;
Packit ae9e2a
		}
Packit ae9e2a
		nn = n * base;
Packit ae9e2a
		if ((v > 0 && nn > INT64_MAX - v) ||
Packit ae9e2a
		    (v < 0 && nn < INT64_MIN - v)) {
Packit ae9e2a
			ovfl = 1;
Packit ae9e2a
			/* Keep on iterating until the end of this number */
Packit ae9e2a
			continue;
Packit ae9e2a
		}
Packit ae9e2a
		n = nn + v;
Packit ae9e2a
	}
Packit ae9e2a
Packit ae9e2a
Return:
Packit ae9e2a
	if (ndig == 0) {
Packit ae9e2a
		giterr_set(GITERR_INVALID, "failed to convert string to long: not a number");
Packit ae9e2a
		return -1;
Packit ae9e2a
	}
Packit ae9e2a
Packit ae9e2a
	if (endptr)
Packit ae9e2a
		*endptr = p;
Packit ae9e2a
Packit ae9e2a
	if (ovfl) {
Packit ae9e2a
		giterr_set(GITERR_INVALID, "failed to convert string to long: overflow error");
Packit ae9e2a
		return -1;
Packit ae9e2a
	}
Packit ae9e2a
Packit ae9e2a
	*result = n;
Packit ae9e2a
	return 0;
Packit ae9e2a
}
Packit ae9e2a
Packit ae9e2a
int git__strntol32(int32_t *result, const char *nptr, size_t nptr_len, const char **endptr, int base)
Packit ae9e2a
{
Packit ae9e2a
	const char *tmp_endptr;
Packit ae9e2a
	int32_t tmp_int;
Packit ae9e2a
	int64_t tmp_long;
Packit ae9e2a
	int error;
Packit ae9e2a
Packit ae9e2a
	if ((error = git__strntol64(&tmp_long, nptr, nptr_len, &tmp_endptr, base)) < 0)
Packit ae9e2a
		return error;
Packit ae9e2a
Packit ae9e2a
	tmp_int = tmp_long & 0xFFFFFFFF;
Packit ae9e2a
	if (tmp_int != tmp_long) {
Packit ae9e2a
		int len = tmp_endptr - nptr;
Packit ae9e2a
		giterr_set(GITERR_INVALID, "failed to convert: '%.*s' is too large", len, nptr);
Packit ae9e2a
		return -1;
Packit ae9e2a
	}
Packit ae9e2a
Packit ae9e2a
	*result = tmp_int;
Packit ae9e2a
	if (endptr)
Packit ae9e2a
		*endptr = tmp_endptr;
Packit ae9e2a
Packit ae9e2a
	return error;
Packit ae9e2a
}
Packit ae9e2a
Packit ae9e2a
int git__strcmp(const char *a, const char *b)
Packit ae9e2a
{
Packit ae9e2a
	while (*a && *b && *a == *b)
Packit ae9e2a
		++a, ++b;
Packit ae9e2a
	return (int)(*(const unsigned char *)a) - (int)(*(const unsigned char *)b);
Packit ae9e2a
}
Packit ae9e2a
Packit ae9e2a
int git__strcasecmp(const char *a, const char *b)
Packit ae9e2a
{
Packit ae9e2a
	while (*a && *b && git__tolower(*a) == git__tolower(*b))
Packit ae9e2a
		++a, ++b;
Packit ae9e2a
	return ((unsigned char)git__tolower(*a) - (unsigned char)git__tolower(*b));
Packit ae9e2a
}
Packit ae9e2a
Packit ae9e2a
int git__strcasesort_cmp(const char *a, const char *b)
Packit ae9e2a
{
Packit ae9e2a
	int cmp = 0;
Packit ae9e2a
Packit ae9e2a
	while (*a && *b) {
Packit ae9e2a
		if (*a != *b) {
Packit ae9e2a
			if (git__tolower(*a) != git__tolower(*b))
Packit ae9e2a
				break;
Packit ae9e2a
			/* use case in sort order even if not in equivalence */
Packit ae9e2a
			if (!cmp)
Packit ae9e2a
				cmp = (int)(*(const uint8_t *)a) - (int)(*(const uint8_t *)b);
Packit ae9e2a
		}
Packit ae9e2a
Packit ae9e2a
		++a, ++b;
Packit ae9e2a
	}
Packit ae9e2a
Packit ae9e2a
	if (*a || *b)
Packit ae9e2a
		return (unsigned char)git__tolower(*a) - (unsigned char)git__tolower(*b);
Packit ae9e2a
Packit ae9e2a
	return cmp;
Packit ae9e2a
}
Packit ae9e2a
Packit ae9e2a
int git__strncmp(const char *a, const char *b, size_t sz)
Packit ae9e2a
{
Packit ae9e2a
	while (sz && *a && *b && *a == *b)
Packit ae9e2a
		--sz, ++a, ++b;
Packit ae9e2a
	if (!sz)
Packit ae9e2a
		return 0;
Packit ae9e2a
	return (int)(*(const unsigned char *)a) - (int)(*(const unsigned char *)b);
Packit ae9e2a
}
Packit ae9e2a
Packit ae9e2a
int git__strncasecmp(const char *a, const char *b, size_t sz)
Packit ae9e2a
{
Packit ae9e2a
	int al, bl;
Packit ae9e2a
Packit ae9e2a
	do {
Packit ae9e2a
		al = (unsigned char)git__tolower(*a);
Packit ae9e2a
		bl = (unsigned char)git__tolower(*b);
Packit ae9e2a
		++a, ++b;
Packit ae9e2a
	} while (--sz && al && al == bl);
Packit ae9e2a
Packit ae9e2a
	return al - bl;
Packit ae9e2a
}
Packit ae9e2a
Packit ae9e2a
void git__strntolower(char *str, size_t len)
Packit ae9e2a
{
Packit ae9e2a
	size_t i;
Packit ae9e2a
Packit ae9e2a
	for (i = 0; i < len; ++i) {
Packit ae9e2a
		str[i] = (char)git__tolower(str[i]);
Packit ae9e2a
	}
Packit ae9e2a
}
Packit ae9e2a
Packit ae9e2a
void git__strtolower(char *str)
Packit ae9e2a
{
Packit ae9e2a
	git__strntolower(str, strlen(str));
Packit ae9e2a
}
Packit ae9e2a
Packit ae9e2a
GIT_INLINE(int) prefixcmp(const char *str, size_t str_n, const char *prefix, bool icase)
Packit ae9e2a
{
Packit ae9e2a
	int s, p;
Packit ae9e2a
Packit ae9e2a
	while (str_n--) {
Packit ae9e2a
		s = (unsigned char)*str++;
Packit ae9e2a
		p = (unsigned char)*prefix++;
Packit ae9e2a
Packit ae9e2a
		if (icase) {
Packit ae9e2a
			s = git__tolower(s);
Packit ae9e2a
			p = git__tolower(p);
Packit ae9e2a
		}
Packit ae9e2a
Packit ae9e2a
		if (!p)
Packit ae9e2a
			return 0;
Packit ae9e2a
Packit ae9e2a
		if (s != p)
Packit ae9e2a
			return s - p;
Packit ae9e2a
	}
Packit ae9e2a
Packit ae9e2a
	return (0 - *prefix);
Packit ae9e2a
}
Packit ae9e2a
Packit ae9e2a
int git__prefixcmp(const char *str, const char *prefix)
Packit ae9e2a
{
Packit ae9e2a
	return prefixcmp(str, SIZE_MAX, prefix, false);
Packit ae9e2a
}
Packit ae9e2a
Packit ae9e2a
int git__prefixncmp(const char *str, size_t str_n, const char *prefix)
Packit ae9e2a
{
Packit ae9e2a
	return prefixcmp(str, str_n, prefix, false);
Packit ae9e2a
}
Packit ae9e2a
Packit ae9e2a
int git__prefixcmp_icase(const char *str, const char *prefix)
Packit ae9e2a
{
Packit ae9e2a
	return prefixcmp(str, SIZE_MAX, prefix, true);
Packit ae9e2a
}
Packit ae9e2a
Packit ae9e2a
int git__prefixncmp_icase(const char *str, size_t str_n, const char *prefix)
Packit ae9e2a
{
Packit ae9e2a
	return prefixcmp(str, str_n, prefix, true);
Packit ae9e2a
}
Packit ae9e2a
Packit ae9e2a
int git__suffixcmp(const char *str, const char *suffix)
Packit ae9e2a
{
Packit ae9e2a
	size_t a = strlen(str);
Packit ae9e2a
	size_t b = strlen(suffix);
Packit ae9e2a
	if (a < b)
Packit ae9e2a
		return -1;
Packit ae9e2a
	return strcmp(str + (a - b), suffix);
Packit ae9e2a
}
Packit ae9e2a
Packit ae9e2a
char *git__strtok(char **end, const char *sep)
Packit ae9e2a
{
Packit ae9e2a
	char *ptr = *end;
Packit ae9e2a
Packit ae9e2a
	while (*ptr && strchr(sep, *ptr))
Packit ae9e2a
		++ptr;
Packit ae9e2a
Packit ae9e2a
	if (*ptr) {
Packit ae9e2a
		char *start = ptr;
Packit ae9e2a
		*end = start + 1;
Packit ae9e2a
Packit ae9e2a
		while (**end && !strchr(sep, **end))
Packit ae9e2a
			++*end;
Packit ae9e2a
Packit ae9e2a
		if (**end) {
Packit ae9e2a
			**end = '\0';
Packit ae9e2a
			++*end;
Packit ae9e2a
		}
Packit ae9e2a
Packit ae9e2a
		return start;
Packit ae9e2a
	}
Packit ae9e2a
Packit ae9e2a
	return NULL;
Packit ae9e2a
}
Packit ae9e2a
Packit ae9e2a
/* Similar to strtok, but does not collapse repeated tokens. */
Packit ae9e2a
char *git__strsep(char **end, const char *sep)
Packit ae9e2a
{
Packit ae9e2a
	char *start = *end, *ptr = *end;
Packit ae9e2a
Packit ae9e2a
	while (*ptr && !strchr(sep, *ptr))
Packit ae9e2a
		++ptr;
Packit ae9e2a
Packit ae9e2a
	if (*ptr) {
Packit ae9e2a
		*end = ptr + 1;
Packit ae9e2a
		*ptr = '\0';
Packit ae9e2a
Packit ae9e2a
		return start;
Packit ae9e2a
	}
Packit ae9e2a
Packit ae9e2a
	return NULL;
Packit ae9e2a
}
Packit ae9e2a
Packit ae9e2a
size_t git__linenlen(const char *buffer, size_t buffer_len)
Packit ae9e2a
{
Packit ae9e2a
	char *nl = memchr(buffer, '\n', buffer_len);
Packit ae9e2a
	return nl ? (size_t)(nl - buffer) + 1 : buffer_len;
Packit ae9e2a
}
Packit ae9e2a
Packit ae9e2a
/*
Packit ae9e2a
 * Adapted Not So Naive algorithm from http://www-igm.univ-mlv.fr/~lecroq/string/
Packit ae9e2a
 */
Packit ae9e2a
const void * git__memmem(const void *haystack, size_t haystacklen,
Packit ae9e2a
			 const void *needle, size_t needlelen)
Packit ae9e2a
{
Packit ae9e2a
	const char *h, *n;
Packit ae9e2a
	size_t j, k, l;
Packit ae9e2a
Packit ae9e2a
	if (needlelen > haystacklen || !haystacklen || !needlelen)
Packit ae9e2a
		return NULL;
Packit ae9e2a
Packit ae9e2a
	h = (const char *) haystack,
Packit ae9e2a
	n = (const char *) needle;
Packit ae9e2a
Packit ae9e2a
	if (needlelen == 1)
Packit ae9e2a
		return memchr(haystack, *n, haystacklen);
Packit ae9e2a
Packit ae9e2a
	if (n[0] == n[1]) {
Packit ae9e2a
		k = 2;
Packit ae9e2a
		l = 1;
Packit ae9e2a
	} else {
Packit ae9e2a
		k = 1;
Packit ae9e2a
		l = 2;
Packit ae9e2a
	}
Packit ae9e2a
Packit ae9e2a
	j = 0;
Packit ae9e2a
	while (j <= haystacklen - needlelen) {
Packit ae9e2a
		if (n[1] != h[j + 1]) {
Packit ae9e2a
			j += k;
Packit ae9e2a
		} else {
Packit ae9e2a
			if (memcmp(n + 2, h + j + 2, needlelen - 2) == 0 &&
Packit ae9e2a
			    n[0] == h[j])
Packit ae9e2a
				return h + j;
Packit ae9e2a
			j += l;
Packit ae9e2a
		}
Packit ae9e2a
	}
Packit ae9e2a
Packit ae9e2a
	return NULL;
Packit ae9e2a
}
Packit ae9e2a
Packit ae9e2a
void git__hexdump(const char *buffer, size_t len)
Packit ae9e2a
{
Packit ae9e2a
	static const size_t LINE_WIDTH = 16;
Packit ae9e2a
Packit ae9e2a
	size_t line_count, last_line, i, j;
Packit ae9e2a
	const char *line;
Packit ae9e2a
Packit ae9e2a
	line_count = (len / LINE_WIDTH);
Packit ae9e2a
	last_line = (len % LINE_WIDTH);
Packit ae9e2a
Packit ae9e2a
	for (i = 0; i < line_count; ++i) {
Packit ae9e2a
		line = buffer + (i * LINE_WIDTH);
Packit ae9e2a
		for (j = 0; j < LINE_WIDTH; ++j, ++line)
Packit ae9e2a
			printf("%02X ", (unsigned char)*line & 0xFF);
Packit ae9e2a
Packit ae9e2a
		printf("| ");
Packit ae9e2a
Packit ae9e2a
		line = buffer + (i * LINE_WIDTH);
Packit ae9e2a
		for (j = 0; j < LINE_WIDTH; ++j, ++line)
Packit ae9e2a
			printf("%c", (*line >= 32 && *line <= 126) ? *line : '.');
Packit ae9e2a
Packit ae9e2a
		printf("\n");
Packit ae9e2a
	}
Packit ae9e2a
Packit ae9e2a
	if (last_line > 0) {
Packit ae9e2a
Packit ae9e2a
		line = buffer + (line_count * LINE_WIDTH);
Packit ae9e2a
		for (j = 0; j < last_line; ++j, ++line)
Packit ae9e2a
			printf("%02X ", (unsigned char)*line & 0xFF);
Packit ae9e2a
Packit ae9e2a
		for (j = 0; j < (LINE_WIDTH - last_line); ++j)
Packit ae9e2a
			printf("	");
Packit ae9e2a
Packit ae9e2a
		printf("| ");
Packit ae9e2a
Packit ae9e2a
		line = buffer + (line_count * LINE_WIDTH);
Packit ae9e2a
		for (j = 0; j < last_line; ++j, ++line)
Packit ae9e2a
			printf("%c", (*line >= 32 && *line <= 126) ? *line : '.');
Packit ae9e2a
Packit ae9e2a
		printf("\n");
Packit ae9e2a
	}
Packit ae9e2a
Packit ae9e2a
	printf("\n");
Packit ae9e2a
}
Packit ae9e2a
Packit ae9e2a
#ifdef GIT_LEGACY_HASH
Packit ae9e2a
uint32_t git__hash(const void *key, int len, unsigned int seed)
Packit ae9e2a
{
Packit ae9e2a
	const uint32_t m = 0x5bd1e995;
Packit ae9e2a
	const int r = 24;
Packit ae9e2a
	uint32_t h = seed ^ len;
Packit ae9e2a
Packit ae9e2a
	const unsigned char *data = (const unsigned char *)key;
Packit ae9e2a
Packit ae9e2a
	while(len >= 4) {
Packit ae9e2a
		uint32_t k = *(uint32_t *)data;
Packit ae9e2a
Packit ae9e2a
		k *= m;
Packit ae9e2a
		k ^= k >> r;
Packit ae9e2a
		k *= m;
Packit ae9e2a
Packit ae9e2a
		h *= m;
Packit ae9e2a
		h ^= k;
Packit ae9e2a
Packit ae9e2a
		data += 4;
Packit ae9e2a
		len -= 4;
Packit ae9e2a
	}
Packit ae9e2a
Packit ae9e2a
	switch(len) {
Packit ae9e2a
	case 3: h ^= data[2] << 16;
Packit ae9e2a
	case 2: h ^= data[1] << 8;
Packit ae9e2a
	case 1: h ^= data[0];
Packit ae9e2a
			h *= m;
Packit ae9e2a
	};
Packit ae9e2a
Packit ae9e2a
	h ^= h >> 13;
Packit ae9e2a
	h *= m;
Packit ae9e2a
	h ^= h >> 15;
Packit ae9e2a
Packit ae9e2a
	return h;
Packit ae9e2a
}
Packit ae9e2a
#else
Packit ae9e2a
/*
Packit ae9e2a
	Cross-platform version of Murmurhash3
Packit ae9e2a
	http://code.google.com/p/smhasher/wiki/MurmurHash3
Packit ae9e2a
	by Austin Appleby (aappleby@gmail.com)
Packit ae9e2a
Packit ae9e2a
	This code is on the public domain.
Packit ae9e2a
*/
Packit ae9e2a
uint32_t git__hash(const void *key, int len, uint32_t seed)
Packit ae9e2a
{
Packit ae9e2a
Packit ae9e2a
#define MURMUR_BLOCK() {\
Packit ae9e2a
	k1 *= c1; \
Packit ae9e2a
	k1 = git__rotl(k1,11);\
Packit ae9e2a
	k1 *= c2;\
Packit ae9e2a
	h1 ^= k1;\
Packit ae9e2a
	h1 = h1*3 + 0x52dce729;\
Packit ae9e2a
	c1 = c1*5 + 0x7b7d159c;\
Packit ae9e2a
	c2 = c2*5 + 0x6bce6396;\
Packit ae9e2a
}
Packit ae9e2a
Packit ae9e2a
	const uint8_t *data = (const uint8_t*)key;
Packit ae9e2a
	const int nblocks = len / 4;
Packit ae9e2a
Packit ae9e2a
	const uint32_t *blocks = (const uint32_t *)(data + nblocks * 4);
Packit ae9e2a
	const uint8_t *tail = (const uint8_t *)(data + nblocks * 4);
Packit ae9e2a
Packit ae9e2a
	uint32_t h1 = 0x971e137b ^ seed;
Packit ae9e2a
	uint32_t k1;
Packit ae9e2a
Packit ae9e2a
	uint32_t c1 = 0x95543787;
Packit ae9e2a
	uint32_t c2 = 0x2ad7eb25;
Packit ae9e2a
Packit ae9e2a
	int i;
Packit ae9e2a
Packit ae9e2a
	for (i = -nblocks; i; i++) {
Packit ae9e2a
		k1 = blocks[i];
Packit ae9e2a
		MURMUR_BLOCK();
Packit ae9e2a
	}
Packit ae9e2a
Packit ae9e2a
	k1 = 0;
Packit ae9e2a
Packit ae9e2a
	switch(len & 3) {
Packit ae9e2a
	case 3: k1 ^= tail[2] << 16;
Packit ae9e2a
	case 2: k1 ^= tail[1] << 8;
Packit ae9e2a
	case 1: k1 ^= tail[0];
Packit ae9e2a
			MURMUR_BLOCK();
Packit ae9e2a
	}
Packit ae9e2a
Packit ae9e2a
	h1 ^= len;
Packit ae9e2a
	h1 ^= h1 >> 16;
Packit ae9e2a
	h1 *= 0x85ebca6b;
Packit ae9e2a
	h1 ^= h1 >> 13;
Packit ae9e2a
	h1 *= 0xc2b2ae35;
Packit ae9e2a
	h1 ^= h1 >> 16;
Packit ae9e2a
Packit ae9e2a
	return h1;
Packit ae9e2a
}
Packit ae9e2a
#endif
Packit ae9e2a
Packit ae9e2a
/**
Packit ae9e2a
 * A modified `bsearch` from the BSD glibc.
Packit ae9e2a
 *
Packit ae9e2a
 * Copyright (c) 1990 Regents of the University of California.
Packit ae9e2a
 * All rights reserved.
Packit ae9e2a
 * Redistribution and use in source and binary forms, with or without
Packit ae9e2a
 * modification, are permitted provided that the following conditions
Packit ae9e2a
 * are met:
Packit ae9e2a
 * 1. Redistributions of source code must retain the above copyright
Packit ae9e2a
 * notice, this list of conditions and the following disclaimer.
Packit ae9e2a
 * 2. Redistributions in binary form must reproduce the above copyright
Packit ae9e2a
 * notice, this list of conditions and the following disclaimer in the
Packit ae9e2a
 * documentation and/or other materials provided with the distribution.
Packit ae9e2a
 * 3. [rescinded 22 July 1999]
Packit ae9e2a
 * 4. Neither the name of the University nor the names of its contributors
Packit ae9e2a
 * may be used to endorse or promote products derived from this software
Packit ae9e2a
 * without specific prior written permission.
Packit ae9e2a
 *
Packit ae9e2a
 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
Packit ae9e2a
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
Packit ae9e2a
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
Packit ae9e2a
 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
Packit ae9e2a
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
Packit ae9e2a
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
Packit ae9e2a
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
Packit ae9e2a
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
Packit ae9e2a
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
Packit ae9e2a
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
Packit ae9e2a
 * SUCH DAMAGE.
Packit ae9e2a
 */
Packit ae9e2a
int git__bsearch(
Packit ae9e2a
	void **array,
Packit ae9e2a
	size_t array_len,
Packit ae9e2a
	const void *key,
Packit ae9e2a
	int (*compare)(const void *, const void *),
Packit ae9e2a
	size_t *position)
Packit ae9e2a
{
Packit ae9e2a
	size_t lim;
Packit ae9e2a
	int cmp = -1;
Packit ae9e2a
	void **part, **base = array;
Packit ae9e2a
Packit ae9e2a
	for (lim = array_len; lim != 0; lim >>= 1) {
Packit ae9e2a
		part = base + (lim >> 1);
Packit ae9e2a
		cmp = (*compare)(key, *part);
Packit ae9e2a
		if (cmp == 0) {
Packit ae9e2a
			base = part;
Packit ae9e2a
			break;
Packit ae9e2a
		}
Packit ae9e2a
		if (cmp > 0) { /* key > p; take right partition */
Packit ae9e2a
			base = part + 1;
Packit ae9e2a
			lim--;
Packit ae9e2a
		} /* else take left partition */
Packit ae9e2a
	}
Packit ae9e2a
Packit ae9e2a
	if (position)
Packit ae9e2a
		*position = (base - array);
Packit ae9e2a
Packit ae9e2a
	return (cmp == 0) ? 0 : GIT_ENOTFOUND;
Packit ae9e2a
}
Packit ae9e2a
Packit ae9e2a
int git__bsearch_r(
Packit ae9e2a
	void **array,
Packit ae9e2a
	size_t array_len,
Packit ae9e2a
	const void *key,
Packit ae9e2a
	int (*compare_r)(const void *, const void *, void *),
Packit ae9e2a
	void *payload,
Packit ae9e2a
	size_t *position)
Packit ae9e2a
{
Packit ae9e2a
	size_t lim;
Packit ae9e2a
	int cmp = -1;
Packit ae9e2a
	void **part, **base = array;
Packit ae9e2a
Packit ae9e2a
	for (lim = array_len; lim != 0; lim >>= 1) {
Packit ae9e2a
		part = base + (lim >> 1);
Packit ae9e2a
		cmp = (*compare_r)(key, *part, payload);
Packit ae9e2a
		if (cmp == 0) {
Packit ae9e2a
			base = part;
Packit ae9e2a
			break;
Packit ae9e2a
		}
Packit ae9e2a
		if (cmp > 0) { /* key > p; take right partition */
Packit ae9e2a
			base = part + 1;
Packit ae9e2a
			lim--;
Packit ae9e2a
		} /* else take left partition */
Packit ae9e2a
	}
Packit ae9e2a
Packit ae9e2a
	if (position)
Packit ae9e2a
		*position = (base - array);
Packit ae9e2a
Packit ae9e2a
	return (cmp == 0) ? 0 : GIT_ENOTFOUND;
Packit ae9e2a
}
Packit ae9e2a
Packit ae9e2a
/**
Packit ae9e2a
 * A strcmp wrapper
Packit ae9e2a
 *
Packit ae9e2a
 * We don't want direct pointers to the CRT on Windows, we may
Packit ae9e2a
 * get stdcall conflicts.
Packit ae9e2a
 */
Packit ae9e2a
int git__strcmp_cb(const void *a, const void *b)
Packit ae9e2a
{
Packit ae9e2a
	return strcmp((const char *)a, (const char *)b);
Packit ae9e2a
}
Packit ae9e2a
Packit ae9e2a
int git__strcasecmp_cb(const void *a, const void *b)
Packit ae9e2a
{
Packit ae9e2a
	return strcasecmp((const char *)a, (const char *)b);
Packit ae9e2a
}
Packit ae9e2a
Packit ae9e2a
int git__parse_bool(int *out, const char *value)
Packit ae9e2a
{
Packit ae9e2a
	/* A missing value means true */
Packit ae9e2a
	if (value == NULL ||
Packit ae9e2a
		!strcasecmp(value, "true") ||
Packit ae9e2a
		!strcasecmp(value, "yes") ||
Packit ae9e2a
		!strcasecmp(value, "on")) {
Packit ae9e2a
		*out = 1;
Packit ae9e2a
		return 0;
Packit ae9e2a
	}
Packit ae9e2a
	if (!strcasecmp(value, "false") ||
Packit ae9e2a
		!strcasecmp(value, "no") ||
Packit ae9e2a
		!strcasecmp(value, "off") ||
Packit ae9e2a
		value[0] == '\0') {
Packit ae9e2a
		*out = 0;
Packit ae9e2a
		return 0;
Packit ae9e2a
	}
Packit ae9e2a
Packit ae9e2a
	return -1;
Packit ae9e2a
}
Packit ae9e2a
Packit ae9e2a
size_t git__unescape(char *str)
Packit ae9e2a
{
Packit ae9e2a
	char *scan, *pos = str;
Packit ae9e2a
Packit ae9e2a
	if (!str)
Packit ae9e2a
		return 0;
Packit ae9e2a
Packit ae9e2a
	for (scan = str; *scan; pos++, scan++) {
Packit ae9e2a
		if (*scan == '\\' && *(scan + 1) != '\0')
Packit ae9e2a
			scan++; /* skip '\' but include next char */
Packit ae9e2a
		if (pos != scan)
Packit ae9e2a
			*pos = *scan;
Packit ae9e2a
	}
Packit ae9e2a
Packit ae9e2a
	if (pos != scan) {
Packit ae9e2a
		*pos = '\0';
Packit ae9e2a
	}
Packit ae9e2a
Packit ae9e2a
	return (pos - str);
Packit ae9e2a
}
Packit ae9e2a
Packit ae9e2a
#if defined(HAVE_QSORT_S) || (defined(HAVE_QSORT_R) && defined(BSD))
Packit ae9e2a
typedef struct {
Packit ae9e2a
	git__sort_r_cmp cmp;
Packit ae9e2a
	void *payload;
Packit ae9e2a
} git__qsort_r_glue;
Packit ae9e2a
Packit ae9e2a
static int GIT_STDLIB_CALL git__qsort_r_glue_cmp(
Packit ae9e2a
	void *payload, const void *a, const void *b)
Packit ae9e2a
{
Packit ae9e2a
	git__qsort_r_glue *glue = payload;
Packit ae9e2a
	return glue->cmp(a, b, glue->payload);
Packit ae9e2a
}
Packit ae9e2a
#endif
Packit ae9e2a
Packit ae9e2a
void git__qsort_r(
Packit ae9e2a
	void *els, size_t nel, size_t elsize, git__sort_r_cmp cmp, void *payload)
Packit ae9e2a
{
Packit ae9e2a
#if defined(HAVE_QSORT_R) && defined(BSD)
Packit ae9e2a
	git__qsort_r_glue glue = { cmp, payload };
Packit ae9e2a
	qsort_r(els, nel, elsize, &glue, git__qsort_r_glue_cmp);
Packit ae9e2a
#elif defined(HAVE_QSORT_R) && defined(__GLIBC__)
Packit ae9e2a
	qsort_r(els, nel, elsize, cmp, payload);
Packit ae9e2a
#elif defined(HAVE_QSORT_S)
Packit ae9e2a
	git__qsort_r_glue glue = { cmp, payload };
Packit ae9e2a
	qsort_s(els, nel, elsize, git__qsort_r_glue_cmp, &glue);
Packit ae9e2a
#else
Packit ae9e2a
	git__insertsort_r(els, nel, elsize, NULL, cmp, payload);
Packit ae9e2a
#endif
Packit ae9e2a
}
Packit ae9e2a
Packit ae9e2a
void git__insertsort_r(
Packit ae9e2a
	void *els, size_t nel, size_t elsize, void *swapel,
Packit ae9e2a
	git__sort_r_cmp cmp, void *payload)
Packit ae9e2a
{
Packit ae9e2a
	uint8_t *base = els;
Packit ae9e2a
	uint8_t *end = base + nel * elsize;
Packit ae9e2a
	uint8_t *i, *j;
Packit ae9e2a
	bool freeswap = !swapel;
Packit ae9e2a
Packit ae9e2a
	if (freeswap)
Packit ae9e2a
		swapel = git__malloc(elsize);
Packit ae9e2a
Packit ae9e2a
	for (i = base + elsize; i < end; i += elsize)
Packit ae9e2a
		for (j = i; j > base && cmp(j, j - elsize, payload) < 0; j -= elsize) {
Packit ae9e2a
			memcpy(swapel, j, elsize);
Packit ae9e2a
			memcpy(j, j - elsize, elsize);
Packit ae9e2a
			memcpy(j - elsize, swapel, elsize);
Packit ae9e2a
		}
Packit ae9e2a
Packit ae9e2a
	if (freeswap)
Packit ae9e2a
		git__free(swapel);
Packit ae9e2a
}
Packit ae9e2a
Packit ae9e2a
/*
Packit ae9e2a
 * git__utf8_iterate is taken from the utf8proc project,
Packit ae9e2a
 * http://www.public-software-group.org/utf8proc
Packit ae9e2a
 *
Packit ae9e2a
 * Copyright (c) 2009 Public Software Group e. V., Berlin, Germany
Packit ae9e2a
 *
Packit ae9e2a
 * Permission is hereby granted, free of charge, to any person obtaining a
Packit ae9e2a
 * copy of this software and associated documentation files (the ""Software""),
Packit ae9e2a
 * to deal in the Software without restriction, including without limitation
Packit ae9e2a
 * the rights to use, copy, modify, merge, publish, distribute, sublicense,
Packit ae9e2a
 * and/or sell copies of the Software, and to permit persons to whom the
Packit ae9e2a
 * Software is furnished to do so, subject to the following conditions:
Packit ae9e2a
 *
Packit ae9e2a
 * The above copyright notice and this permission notice shall be included in
Packit ae9e2a
 * all copies or substantial portions of the Software.
Packit ae9e2a
 *
Packit ae9e2a
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
Packit ae9e2a
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
Packit ae9e2a
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
Packit ae9e2a
 * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
Packit ae9e2a
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
Packit ae9e2a
 * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER
Packit ae9e2a
 * DEALINGS IN THE SOFTWARE.
Packit ae9e2a
 */
Packit ae9e2a
Packit ae9e2a
static const int8_t utf8proc_utf8class[256] = {
Packit ae9e2a
	1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
Packit ae9e2a
	1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
Packit ae9e2a
	1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
Packit ae9e2a
	1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
Packit ae9e2a
	1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
Packit ae9e2a
	1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
Packit ae9e2a
	1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
Packit ae9e2a
	1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
Packit ae9e2a
	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
Packit ae9e2a
	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
Packit ae9e2a
	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
Packit ae9e2a
	0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
Packit ae9e2a
	2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
Packit ae9e2a
	2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2,
Packit ae9e2a
	3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3,
Packit ae9e2a
	4, 4, 4, 4, 4, 4, 4, 4, 0, 0, 0, 0, 0, 0, 0, 0
Packit ae9e2a
};
Packit ae9e2a
Packit ae9e2a
int git__utf8_charlen(const uint8_t *str, int str_len)
Packit ae9e2a
{
Packit ae9e2a
	int length, i;
Packit ae9e2a
Packit ae9e2a
	length = utf8proc_utf8class[str[0]];
Packit ae9e2a
	if (!length)
Packit ae9e2a
		return -1;
Packit ae9e2a
Packit ae9e2a
	if (str_len >= 0 && length > str_len)
Packit ae9e2a
		return -str_len;
Packit ae9e2a
Packit ae9e2a
	for (i = 1; i < length; i++) {
Packit ae9e2a
		if ((str[i] & 0xC0) != 0x80)
Packit ae9e2a
			return -i;
Packit ae9e2a
	}
Packit ae9e2a
Packit ae9e2a
	return length;
Packit ae9e2a
}
Packit ae9e2a
Packit ae9e2a
int git__utf8_iterate(const uint8_t *str, int str_len, int32_t *dst)
Packit ae9e2a
{
Packit ae9e2a
	int length;
Packit ae9e2a
	int32_t uc = -1;
Packit ae9e2a
Packit ae9e2a
	*dst = -1;
Packit ae9e2a
	length = git__utf8_charlen(str, str_len);
Packit ae9e2a
	if (length < 0)
Packit ae9e2a
		return -1;
Packit ae9e2a
Packit ae9e2a
	switch (length) {
Packit ae9e2a
		case 1:
Packit ae9e2a
			uc = str[0];
Packit ae9e2a
			break;
Packit ae9e2a
		case 2:
Packit ae9e2a
			uc = ((str[0] & 0x1F) <<  6) + (str[1] & 0x3F);
Packit ae9e2a
			if (uc < 0x80) uc = -1;
Packit ae9e2a
			break;
Packit ae9e2a
		case 3:
Packit ae9e2a
			uc = ((str[0] & 0x0F) << 12) + ((str[1] & 0x3F) <<  6)
Packit ae9e2a
				+ (str[2] & 0x3F);
Packit ae9e2a
			if (uc < 0x800 || (uc >= 0xD800 && uc < 0xE000) ||
Packit ae9e2a
					(uc >= 0xFDD0 && uc < 0xFDF0)) uc = -1;
Packit ae9e2a
			break;
Packit ae9e2a
		case 4:
Packit ae9e2a
			uc = ((str[0] & 0x07) << 18) + ((str[1] & 0x3F) << 12)
Packit ae9e2a
				+ ((str[2] & 0x3F) <<  6) + (str[3] & 0x3F);
Packit ae9e2a
			if (uc < 0x10000 || uc >= 0x110000) uc = -1;
Packit ae9e2a
			break;
Packit ae9e2a
	}
Packit ae9e2a
Packit ae9e2a
	if (uc < 0 || ((uc & 0xFFFF) >= 0xFFFE))
Packit ae9e2a
		return -1;
Packit ae9e2a
Packit ae9e2a
	*dst = uc;
Packit ae9e2a
	return length;
Packit ae9e2a
}
Packit ae9e2a
Packit ae9e2a
double git_time_monotonic(void)
Packit ae9e2a
{
Packit ae9e2a
	return git__timer();
Packit ae9e2a
}
Packit ae9e2a
Packit ae9e2a
#ifdef GIT_WIN32
Packit ae9e2a
int git__getenv(git_buf *out, const char *name)
Packit ae9e2a
{
Packit ae9e2a
	wchar_t *wide_name = NULL, *wide_value = NULL;
Packit ae9e2a
	DWORD value_len;
Packit ae9e2a
	int error = -1;
Packit ae9e2a
Packit ae9e2a
	git_buf_clear(out);
Packit ae9e2a
Packit ae9e2a
	if (git__utf8_to_16_alloc(&wide_name, name) < 0)
Packit ae9e2a
		return -1;
Packit ae9e2a
Packit ae9e2a
	if ((value_len = GetEnvironmentVariableW(wide_name, NULL, 0)) > 0) {
Packit ae9e2a
		wide_value = git__malloc(value_len * sizeof(wchar_t));
Packit ae9e2a
		GITERR_CHECK_ALLOC(wide_value);
Packit ae9e2a
Packit ae9e2a
		value_len = GetEnvironmentVariableW(wide_name, wide_value, value_len);
Packit ae9e2a
	}
Packit ae9e2a
Packit ae9e2a
	if (value_len)
Packit ae9e2a
		error = git_buf_put_w(out, wide_value, value_len);
Packit ae9e2a
	else if (GetLastError() == ERROR_ENVVAR_NOT_FOUND)
Packit ae9e2a
		error = GIT_ENOTFOUND;
Packit ae9e2a
	else
Packit ae9e2a
		giterr_set(GITERR_OS, "could not read environment variable '%s'", name);
Packit ae9e2a
Packit ae9e2a
	git__free(wide_name);
Packit ae9e2a
	git__free(wide_value);
Packit ae9e2a
	return error;
Packit ae9e2a
}
Packit ae9e2a
#else
Packit ae9e2a
int git__getenv(git_buf *out, const char *name)
Packit ae9e2a
{
Packit ae9e2a
	const char *val = getenv(name);
Packit ae9e2a
Packit ae9e2a
	git_buf_clear(out);
Packit ae9e2a
Packit ae9e2a
	if (!val)
Packit ae9e2a
		return GIT_ENOTFOUND;
Packit ae9e2a
Packit ae9e2a
	return git_buf_puts(out, val);
Packit ae9e2a
}
Packit ae9e2a
#endif