[libgit2.git] / src / util.c

#include <git2.h>
#include "common.h"
#include <stdarg.h>
#include <stdio.h>
#include <ctype.h>
#include "posix.h"

#ifdef _MSV_VER
# include <Shlwapi.h>
#endif

void git_libgit2_version(int *major, int *minor, int *rev)
{
	*major = LIBGIT2_VER_MAJOR;
	*minor = LIBGIT2_VER_MINOR;
	*rev = LIBGIT2_VER_REVISION;
}

void git_strarray_free(git_strarray *array)
{
	size_t i;
	for (i = 0; i < array->count; ++i)
		free(array->strings[i]);

	free(array->strings);
}

int git__fnmatch(const char *pattern, const char *name, int flags)
{
	int ret;

	ret = p_fnmatch(pattern, name, flags);
	switch (ret) {
	case 0:
		return GIT_SUCCESS;
	case FNM_NOMATCH:
		return GIT_ENOMATCH;
	default:
		return git__throw(GIT_EOSERR, "Error trying to match path");
	}
}

int git__strtol32(long *result, const char *nptr, const char **endptr, int base)
{
	const char *p;
	long n, nn;
	int c, ovfl, v, neg, ndig;

	p = nptr;
	neg = 0;
	n = 0;
	ndig = 0;
	ovfl = 0;

	/*
	 * White space
	 */
	while (isspace(*p))
		p++;

	/*
	 * Sign
	 */
	if (*p == '-' || *p == '+')
		if (*p++ == '-')
			neg = 1;

	/*
	 * Base
	 */
	if (base == 0) {
		if (*p != '0')
			base = 10;
		else {
			base = 8;
			if (p[1] == 'x' || p[1] == 'X') {
				p += 2;
				base = 16;
			}
		}
	} else if (base == 16 && *p == '0') {
		if (p[1] == 'x' || p[1] == 'X')
			p += 2;
	} else if (base < 0 || 36 < base)
		goto Return;

	/*
	 * Non-empty sequence of digits
	 */
	for (;; p++,ndig++) {
		c = *p;
		v = base;
		if ('0'<=c && c<='9')
			v = c - '0';
		else if ('a'<=c && c<='z')
			v = c - 'a' + 10;
		else if ('A'<=c && c<='Z')
			v = c - 'A' + 10;
		if (v >= base)
			break;
		nn = n*base + v;
		if (nn < n)
			ovfl = 1;
		n = nn;
	}

Return:
	if (ndig == 0)
		return git__throw(GIT_ENOTNUM, "Failed to convert string to long. Not a number");

	if (endptr)
		*endptr = p;

	if (ovfl)
		return git__throw(GIT_EOVERFLOW, "Failed to convert string to long. Overflow error");

	*result = neg ? -n : n;
	return GIT_SUCCESS;
}

int git__fmt(char *buf, size_t buf_sz, const char *fmt, ...)
{
	va_list va;
	int r;

	va_start(va, fmt);
	r = vsnprintf(buf, buf_sz, fmt, va);
	va_end(va);
	if (r < 0 || ((size_t) r) >= buf_sz)
		return git__throw(GIT_ERROR, "Failed to format string");
	return r;
}

void git__strntolower(char *str, int len)
{
	int i;

	for (i = 0; i < len; ++i) {
		str[i] = (char) tolower(str[i]);
	}
}

void git__strtolower(char *str)
{
	git__strntolower(str, strlen(str));
}

int git__prefixcmp(const char *str, const char *prefix)
{
	for (;;) {
		char p = *(prefix++), s;
		if (!p)
			return 0;
		if ((s = *(str++)) != p)
			return s - p;
	}
}

int git__suffixcmp(const char *str, const char *suffix)
{
	size_t a = strlen(str);
	size_t b = strlen(suffix);
	if (a < b)
		return -1;
	return strcmp(str + (a - b), suffix);
}

char *git__strtok(char **end, const char *sep)
{
	char *ptr = *end;

	while (*ptr && strchr(sep, *ptr))
		++ptr;

	if (*ptr) {
		char *start = ptr;
		*end = start + 1;

		while (**end && !strchr(sep, **end))
			++*end;

		if (**end) {
			**end = '\0';
			++*end;
		}

		return start;
	}

	return NULL;
}

void git__hexdump(const char *buffer, size_t len)
{
	static const size_t LINE_WIDTH = 16;

	size_t line_count, last_line, i, j;
	const char *line;

	line_count = (len / LINE_WIDTH);
	last_line = (len % LINE_WIDTH);

	for (i = 0; i < line_count; ++i) {
		line = buffer + (i * LINE_WIDTH);
		for (j = 0; j < LINE_WIDTH; ++j, ++line)
			printf("%02X ", (unsigned char)*line & 0xFF);

		printf("| ");

		line = buffer + (i * LINE_WIDTH);
		for (j = 0; j < LINE_WIDTH; ++j, ++line)
			printf("%c", (*line >= 32 && *line <= 126) ? *line : '.');

		printf("\n");
	}

	if (last_line > 0) {

		line = buffer + (line_count * LINE_WIDTH);
		for (j = 0; j < last_line; ++j, ++line)
			printf("%02X ", (unsigned char)*line & 0xFF);

		for (j = 0; j < (LINE_WIDTH - last_line); ++j)
			printf("   ");

		printf("| ");

		line = buffer + (line_count * LINE_WIDTH);
		for (j = 0; j < last_line; ++j, ++line)
			printf("%c", (*line >= 32 && *line <= 126) ? *line : '.');

		printf("\n");
	}

	printf("\n");
}

#ifdef GIT_LEGACY_HASH
uint32_t git__hash(const void *key, int len, unsigned int seed)
{
	const uint32_t m = 0x5bd1e995;
	const int r = 24;
	uint32_t h = seed ^ len;

	const unsigned char *data = (const unsigned char *)key;

	while(len >= 4) {
		uint32_t k = *(uint32_t *)data;

		k *= m;
		k ^= k >> r;
		k *= m;

		h *= m;
		h ^= k;

		data += 4;
		len -= 4;
	}

	switch(len) {
	case 3: h ^= data[2] << 16;
	case 2: h ^= data[1] << 8;
	case 1: h ^= data[0];
	        h *= m;
	};

	h ^= h >> 13;
	h *= m;
	h ^= h >> 15;

	return h;
}
#else
/*
	Cross-platform version of Murmurhash3
	http://code.google.com/p/smhasher/wiki/MurmurHash3
	by Austin Appleby (aappleby@gmail.com)

	This code is on the public domain.
*/
uint32_t git__hash(const void *key, int len, uint32_t seed)
{

#define MURMUR_BLOCK() {\
    k1 *= c1; \
    k1  = git__rotl(k1,11);\
    k1 *= c2;\
    h1 ^= k1;\
    h1 = h1*3 + 0x52dce729;\
    c1 = c1*5 + 0x7b7d159c;\
    c2 = c2*5 + 0x6bce6396;\
}

	const uint8_t *data = (const uint8_t*)key;
	const int nblocks = len / 4;

	const uint32_t *blocks = (const uint32_t *)(data + nblocks * 4);
	const uint8_t *tail = (const uint8_t *)(data + nblocks * 4);

	uint32_t h1 = 0x971e137b ^ seed;
	uint32_t k1;

	uint32_t c1 = 0x95543787;
	uint32_t c2 = 0x2ad7eb25;

	int i;

	for (i = -nblocks; i; i++) {
		k1 = blocks[i];
		MURMUR_BLOCK();
	}

	k1 = 0;

	switch(len & 3) {
	case 3: k1 ^= tail[2] << 16;
	case 2: k1 ^= tail[1] << 8;
	case 1: k1 ^= tail[0];
			MURMUR_BLOCK();
	}

	h1 ^= len;
	h1 ^= h1 >> 16;
	h1 *= 0x85ebca6b;
	h1 ^= h1 >> 13;
	h1 *= 0xc2b2ae35;
	h1 ^= h1 >> 16;

	return h1;
}
#endif

/*
 * A merge sort implementation, simplified from the qsort implementation
 * by Mike Haertel, which is a part of the GNU C Library.
 */
static void msort_with_tmp(void *b, size_t n, size_t s,
		int (*cmp)(const void *, const void *),
		char *t)
{
	char *tmp;
	char *b1, *b2;
	size_t n1, n2;

	if (n <= 1)
		return;

	n1 = n / 2;
	n2 = n - n1;
	b1 = b;
	b2 = (char *)b + (n1 * s);

	msort_with_tmp(b1, n1, s, cmp, t);
	msort_with_tmp(b2, n2, s, cmp, t);

	tmp = t;

	while (n1 > 0 && n2 > 0) {
		if (cmp(b1, b2) <= 0) {
			memcpy(tmp, b1, s);
			tmp += s;
			b1 += s;
			--n1;
		} else {
			memcpy(tmp, b2, s);
			tmp += s;
			b2 += s;
			--n2;
		}
	}
	if (n1 > 0)
		memcpy(tmp, b1, n1 * s);
	memcpy(b, t, (n - n2) * s);
}

int git__msort(void *b, size_t n, size_t s,
		int (*cmp)(const void *, const void *))
{
	const size_t size = n * s;
	char buf[1024];

	if (size < sizeof(buf)) {
		/* The temporary array fits on the small on-stack buffer. */
		msort_with_tmp(b, n, s, cmp, buf);
	} else {
		/* It's somewhat large, so malloc it.  */
		char *tmp = git__malloc(size);
		if (tmp == NULL)
			return GIT_ENOMEM;
		msort_with_tmp(b, n, s, cmp, tmp);
		free(tmp);
	}

	return GIT_SUCCESS;
}
Commit	Line	Data
536955f9	1	#include <git2.h>
64a47c01	2	#include "common.h"
2c4b7707 SP	3	#include <stdarg.h>
2c4b7707 SP	4	#include <stdio.h>
c6e65aca	5	#include <ctype.h>
e9c6571d	6	#include "posix.h"
64a47c01	7
63f91e1c CMN	8	#ifdef _MSV_VER
63f91e1c CMN	9	# include <Shlwapi.h>
63f91e1c CMN	10	#endif
63f91e1c CMN	11
536955f9 VM	12	void git_libgit2_version(int major, int minor, int *rev)
	13	{
	14	*major = LIBGIT2_VER_MAJOR;
	15	*minor = LIBGIT2_VER_MINOR;
	16	*rev = LIBGIT2_VER_REVISION;
	17	}
	18
955f9ae9 VM	19	void git_strarray_free(git_strarray *array)
	20	{
	21	size_t i;
	22	for (i = 0; i < array->count; ++i)
	23	free(array->strings[i]);
	24
	25	free(array->strings);
	26	}
	27
63f91e1c CMN	28	int git__fnmatch(const char pattern, const char name, int flags)
	29	{
	30	int ret;
	31
e9c6571d	32	ret = p_fnmatch(pattern, name, flags);
63f91e1c CMN	33	switch (ret) {
	34	case 0:
	35	return GIT_SUCCESS;
	36	case FNM_NOMATCH:
	37	return GIT_ENOMATCH;
	38	default:
	39	return git__throw(GIT_EOSERR, "Error trying to match path");
	40	}
	41	}
	42
c6e65aca VM	43	int git__strtol32(long result, const char nptr, const char **endptr, int base)
	44	{
	45	const char *p;
	46	long n, nn;
	47	int c, ovfl, v, neg, ndig;
	48
	49	p = nptr;
	50	neg = 0;
	51	n = 0;
	52	ndig = 0;
	53	ovfl = 0;
	54
	55	/*
	56	* White space
	57	*/
	58	while (isspace(*p))
	59	p++;
	60
	61	/*
	62	* Sign
	63	*/
	64	if (p == '-' \|\| p == '+')
	65	if (*p++ == '-')
	66	neg = 1;
	67
	68	/*
	69	* Base
	70	*/
	71	if (base == 0) {
	72	if (*p != '0')
	73	base = 10;
	74	else {
	75	base = 8;
	76	if (p[1] == 'x' \|\| p[1] == 'X') {
	77	p += 2;
	78	base = 16;
	79	}
	80	}
	81	} else if (base == 16 && *p == '0') {
	82	if (p[1] == 'x' \|\| p[1] == 'X')
	83	p += 2;
	84	} else if (base < 0 \|\| 36 < base)
	85	goto Return;
	86
	87	/*
	88	* Non-empty sequence of digits
	89	*/
	90	for (;; p++,ndig++) {
	91	c = *p;
	92	v = base;
	93	if ('0'<=c && c<='9')
	94	v = c - '0';
	95	else if ('a'<=c && c<='z')
	96	v = c - 'a' + 10;
	97	else if ('A'<=c && c<='Z')
	98	v = c - 'A' + 10;
	99	if (v >= base)
	100	break;
	101	nn = n*base + v;
	102	if (nn < n)
	103	ovfl = 1;
	104	n = nn;
	105	}
	106
107	Return:
108	if (ndig == 0)
33b1d19e	109	return git__throw(GIT_ENOTNUM, "Failed to convert string to long. Not a number");
c6e65aca VM	110
	111	if (endptr)
	112	*endptr = p;
	113
	114	if (ovfl)
33b1d19e	115	return git__throw(GIT_EOVERFLOW, "Failed to convert string to long. Overflow error");
c6e65aca VM	116
	117	*result = neg ? -n : n;
	118	return GIT_SUCCESS;
	119	}
	120
2c4b7707 SP	121	int git__fmt(char buf, size_t buf_sz, const char fmt, ...)
	122	{
	123	va_list va;
	124	int r;
	125
	126	va_start(va, fmt);
	127	r = vsnprintf(buf, buf_sz, fmt, va);
	128	va_end(va);
0ef9d2aa	129	if (r < 0 \|\| ((size_t) r) >= buf_sz)
33b1d19e	130	return git__throw(GIT_ERROR, "Failed to format string");
2c4b7707 SP	131	return r;
	132	}
	133
0da2c700 VM	134	void git__strntolower(char *str, int len)
	135	{
	136	int i;
	137
	138	for (i = 0; i < len; ++i) {
3a1c4310	139	str[i] = (char) tolower(str[i]);
0da2c700 VM	140	}
	141	}
	142
	143	void git__strtolower(char *str)
	144	{
	145	git__strntolower(str, strlen(str));
	146	}
	147
9eb79764 SP	148	int git__prefixcmp(const char str, const char prefix)
	149	{
	150	for (;;) {
	151	char p = *(prefix++), s;
	152	if (!p)
	153	return 0;
	154	if ((s = *(str++)) != p)
	155	return s - p;
	156	}
	157	}
	158
	159	int git__suffixcmp(const char str, const char suffix)
	160	{
	161	size_t a = strlen(str);
	162	size_t b = strlen(suffix);
	163	if (a < b)
	164	return -1;
	165	return strcmp(str + (a - b), suffix);
	166	}
ced645ea	167
0291b5b7	168	char git__strtok(char end, const char sep)
f725931b	169	{
0291b5b7	170	char ptr = end;
ced645ea	171
0291b5b7 VM	172	while (ptr && strchr(sep, ptr))
0291b5b7 VM	173	++ptr;
f725931b	174
0291b5b7 VM	175	if (*ptr) {
	176	char *start = ptr;
	177	*end = start + 1;
ced645ea	178
0291b5b7 VM	179	while (end && !strchr(sep, end))
0291b5b7 VM	180	++*end;
f725931b	181
0291b5b7 VM	182	if (**end) {
	183	**end = '\0';
	184	++*end;
	185	}
	186
	187	return start;
	188	}
	189
	190	return NULL;
ced645ea RJ	191	}
ced645ea RJ	192
0e465f97 VM	193	void git__hexdump(const char *buffer, size_t len)
	194	{
	195	static const size_t LINE_WIDTH = 16;
	196
	197	size_t line_count, last_line, i, j;
	198	const char *line;
	199
	200	line_count = (len / LINE_WIDTH);
	201	last_line = (len % LINE_WIDTH);
	202
	203	for (i = 0; i < line_count; ++i) {
	204	line = buffer + (i * LINE_WIDTH);
	205	for (j = 0; j < LINE_WIDTH; ++j, ++line)
	206	printf("%02X ", (unsigned char)*line & 0xFF);
	207
	208	printf("\| ");
	209
	210	line = buffer + (i * LINE_WIDTH);
	211	for (j = 0; j < LINE_WIDTH; ++j, ++line)
	212	printf("%c", (line >= 32 && line <= 126) ? *line : '.');
	213
	214	printf("\n");
	215	}
	216
	217	if (last_line > 0) {
	218
	219	line = buffer + (line_count * LINE_WIDTH);
	220	for (j = 0; j < last_line; ++j, ++line)
	221	printf("%02X ", (unsigned char)*line & 0xFF);
	222
	223	for (j = 0; j < (LINE_WIDTH - last_line); ++j)
	224	printf(" ");
	225
	226	printf("\| ");
	227
	228	line = buffer + (line_count * LINE_WIDTH);
	229	for (j = 0; j < last_line; ++j, ++line)
	230	printf("%c", (line >= 32 && line <= 126) ? *line : '.');
	231
	232	printf("\n");
	233	}
	234
	235	printf("\n");
	236	}
e0646b38 VM	237
	238	#ifdef GIT_LEGACY_HASH
	239	uint32_t git__hash(const void *key, int len, unsigned int seed)
	240	{
	241	const uint32_t m = 0x5bd1e995;
	242	const int r = 24;
	243	uint32_t h = seed ^ len;
	244
	245	const unsigned char data = (const unsigned char )key;
	246
	247	while(len >= 4) {
	248	uint32_t k = (uint32_t )data;
	249
932d1baf KS	250	k *= m;
	251	k ^= k >> r;
	252	k *= m;
	253
	254	h *= m;
e0646b38 VM	255	h ^= k;
	256
	257	data += 4;
	258	len -= 4;
	259	}
932d1baf	260
e0646b38 VM	261	switch(len) {
	262	case 3: h ^= data[2] << 16;
	263	case 2: h ^= data[1] << 8;
	264	case 1: h ^= data[0];
	265	h *= m;
	266	};
	267
	268	h ^= h >> 13;
	269	h *= m;
	270	h ^= h >> 15;
	271
	272	return h;
932d1baf	273	}
e0646b38 VM	274	#else
	275	/*
	276	Cross-platform version of Murmurhash3
	277	http://code.google.com/p/smhasher/wiki/MurmurHash3
	278	by Austin Appleby (aappleby@gmail.com)
	279
	280	This code is on the public domain.
	281	*/
	282	uint32_t git__hash(const void *key, int len, uint32_t seed)
	283	{
	284
	285	#define MURMUR_BLOCK() {\
	286	k1 *= c1; \
	287	k1 = git__rotl(k1,11);\
	288	k1 *= c2;\
	289	h1 ^= k1;\
	290	h1 = h1*3 + 0x52dce729;\
	291	c1 = c1*5 + 0x7b7d159c;\
	292	c2 = c2*5 + 0x6bce6396;\
	293	}
	294
	295	const uint8_t data = (const uint8_t)key;
	296	const int nblocks = len / 4;
	297
	298	const uint32_t blocks = (const uint32_t )(data + nblocks * 4);
	299	const uint8_t tail = (const uint8_t )(data + nblocks * 4);
	300
	301	uint32_t h1 = 0x971e137b ^ seed;
	302	uint32_t k1;
	303
	304	uint32_t c1 = 0x95543787;
	305	uint32_t c2 = 0x2ad7eb25;
	306
	307	int i;
	308
	309	for (i = -nblocks; i; i++) {
	310	k1 = blocks[i];
	311	MURMUR_BLOCK();
	312	}
	313
	314	k1 = 0;
	315
	316	switch(len & 3) {
	317	case 3: k1 ^= tail[2] << 16;
	318	case 2: k1 ^= tail[1] << 8;
	319	case 1: k1 ^= tail[0];
	320	MURMUR_BLOCK();
	321	}
	322
	323	h1 ^= len;
	324	h1 ^= h1 >> 16;
	325	h1 *= 0x85ebca6b;
	326	h1 ^= h1 >> 13;
	327	h1 *= 0xc2b2ae35;
	328	h1 ^= h1 >> 16;
	329
	330	return h1;
932d1baf	331	}
e0646b38	332	#endif
c20ffa61 KS	333
	334	/*
	335	* A merge sort implementation, simplified from the qsort implementation
	336	* by Mike Haertel, which is a part of the GNU C Library.
	337	*/
	338	static void msort_with_tmp(void *b, size_t n, size_t s,
	339	int (cmp)(const void , const void *),
	340	char *t)
	341	{
	342	char *tmp;
	343	char b1, b2;
	344	size_t n1, n2;
	345
	346	if (n <= 1)
	347	return;
	348
	349	n1 = n / 2;
	350	n2 = n - n1;
	351	b1 = b;
	352	b2 = (char )b + (n1 s);
	353
	354	msort_with_tmp(b1, n1, s, cmp, t);
	355	msort_with_tmp(b2, n2, s, cmp, t);
	356
	357	tmp = t;
	358
	359	while (n1 > 0 && n2 > 0) {
	360	if (cmp(b1, b2) <= 0) {
	361	memcpy(tmp, b1, s);
	362	tmp += s;
	363	b1 += s;
	364	--n1;
	365	} else {
	366	memcpy(tmp, b2, s);
	367	tmp += s;
	368	b2 += s;
	369	--n2;
	370	}
	371	}
	372	if (n1 > 0)
	373	memcpy(tmp, b1, n1 * s);
	374	memcpy(b, t, (n - n2) * s);
	375	}
	376
	377	int git__msort(void *b, size_t n, size_t s,
	378	int (cmp)(const void , const void *))
	379	{
	380	const size_t size = n * s;
	381	char buf[1024];
	382
	383	if (size < sizeof(buf)) {
	384	/* The temporary array fits on the small on-stack buffer. */
	385	msort_with_tmp(b, n, s, cmp, buf);
	386	} else {
	387	/* It's somewhat large, so malloc it. */
	388	char *tmp = git__malloc(size);
	389	if (tmp == NULL)
	390	return GIT_ENOMEM;
	391	msort_with_tmp(b, n, s, cmp, tmp);
	392	free(tmp);
	393	}
	394
	395	return GIT_SUCCESS;
	396	}