Blame src/util.c

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