diff options
Diffstat (limited to 'src/util/util.c')
| -rw-r--r-- | src/util/util.c | 819 |
1 files changed, 819 insertions, 0 deletions
diff --git a/src/util/util.c b/src/util/util.c new file mode 100644 index 000000000..aee95fddf --- /dev/null +++ b/src/util/util.c @@ -0,0 +1,819 @@ +/* + * 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 "util.h" + +#include "git2_util.h" + +#ifdef GIT_WIN32 +# include "win32/utf-conv.h" +# include "win32/w32_buffer.h" + +# ifndef WIN32_LEAN_AND_MEAN +# define WIN32_LEAN_AND_MEAN +# endif +# include <windows.h> + +# ifdef GIT_QSORT_S +# include <search.h> +# endif +#endif + +#ifdef _MSC_VER +# include <Shlwapi.h> +#endif + +#if defined(hpux) || defined(__hpux) || defined(_hpux) +# include <sys/pstat.h> +#endif + +int git__strntol64(int64_t *result, const char *nptr, size_t nptr_len, const char **endptr, int base) +{ + const char *p; + int64_t n, nn, v; + int c, ovfl, neg, ndig; + + p = nptr; + neg = 0; + n = 0; + ndig = 0; + ovfl = 0; + + /* + * White space + */ + while (nptr_len && git__isspace(*p)) + p++, nptr_len--; + + if (!nptr_len) + goto Return; + + /* + * Sign + */ + if (*p == '-' || *p == '+') { + if (*p == '-') + neg = 1; + p++; + nptr_len--; + } + + if (!nptr_len) + goto Return; + + /* + * Automatically detect the base if none was given to us. + * Right now, we assume that a number starting with '0x' + * is hexadecimal and a number starting with '0' is + * octal. + */ + if (base == 0) { + if (*p != '0') + base = 10; + else if (nptr_len > 2 && (p[1] == 'x' || p[1] == 'X')) + base = 16; + else + base = 8; + } + + if (base < 0 || 36 < base) + goto Return; + + /* + * Skip prefix of '0x'-prefixed hexadecimal numbers. There is no + * need to do the same for '0'-prefixed octal numbers as a + * leading '0' does not have any impact. Also, if we skip a + * leading '0' in such a string, then we may end up with no + * digits left and produce an error later on which isn't one. + */ + if (base == 16 && nptr_len > 2 && p[0] == '0' && (p[1] == 'x' || p[1] == 'X')) { + p += 2; + nptr_len -= 2; + } + + /* + * Non-empty sequence of digits + */ + for (; nptr_len > 0; p++,ndig++,nptr_len--) { + 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; + v = neg ? -v : v; + if (git__multiply_int64_overflow(&nn, n, base) || git__add_int64_overflow(&n, nn, v)) { + ovfl = 1; + /* Keep on iterating until the end of this number */ + continue; + } + } + +Return: + if (ndig == 0) { + git_error_set(GIT_ERROR_INVALID, "failed to convert string to long: not a number"); + return -1; + } + + if (endptr) + *endptr = p; + + if (ovfl) { + git_error_set(GIT_ERROR_INVALID, "failed to convert string to long: overflow error"); + return -1; + } + + *result = n; + return 0; +} + +int git__strntol32(int32_t *result, const char *nptr, size_t nptr_len, const char **endptr, int base) +{ + const char *tmp_endptr; + int32_t tmp_int; + int64_t tmp_long; + int error; + + if ((error = git__strntol64(&tmp_long, nptr, nptr_len, &tmp_endptr, base)) < 0) + return error; + + tmp_int = tmp_long & 0xFFFFFFFF; + if (tmp_int != tmp_long) { + int len = (int)(tmp_endptr - nptr); + git_error_set(GIT_ERROR_INVALID, "failed to convert: '%.*s' is too large", len, nptr); + return -1; + } + + *result = tmp_int; + if (endptr) + *endptr = tmp_endptr; + + return error; +} + +int git__strcasecmp(const char *a, const char *b) +{ + while (*a && *b && git__tolower(*a) == git__tolower(*b)) + ++a, ++b; + return ((unsigned char)git__tolower(*a) - (unsigned char)git__tolower(*b)); +} + +int git__strcasesort_cmp(const char *a, const char *b) +{ + int cmp = 0; + + while (*a && *b) { + if (*a != *b) { + if (git__tolower(*a) != git__tolower(*b)) + break; + /* use case in sort order even if not in equivalence */ + if (!cmp) + cmp = (int)(*(const uint8_t *)a) - (int)(*(const uint8_t *)b); + } + + ++a, ++b; + } + + if (*a || *b) + return (unsigned char)git__tolower(*a) - (unsigned char)git__tolower(*b); + + return cmp; +} + +int git__strncasecmp(const char *a, const char *b, size_t sz) +{ + int al, bl; + + do { + al = (unsigned char)git__tolower(*a); + bl = (unsigned char)git__tolower(*b); + ++a, ++b; + } while (--sz && al && al == bl); + + return al - bl; +} + +void git__strntolower(char *str, size_t len) +{ + size_t i; + + for (i = 0; i < len; ++i) { + str[i] = (char)git__tolower(str[i]); + } +} + +void git__strtolower(char *str) +{ + git__strntolower(str, strlen(str)); +} + +GIT_INLINE(int) prefixcmp(const char *str, size_t str_n, const char *prefix, bool icase) +{ + int s, p; + + while (str_n--) { + s = (unsigned char)*str++; + p = (unsigned char)*prefix++; + + if (icase) { + s = git__tolower(s); + p = git__tolower(p); + } + + if (!p) + return 0; + + if (s != p) + return s - p; + } + + return (0 - *prefix); +} + +int git__prefixcmp(const char *str, const char *prefix) +{ + unsigned char s, p; + + while (1) { + p = *prefix++; + s = *str++; + + if (!p) + return 0; + + if (s != p) + return s - p; + } +} + +int git__prefixncmp(const char *str, size_t str_n, const char *prefix) +{ + return prefixcmp(str, str_n, prefix, false); +} + +int git__prefixcmp_icase(const char *str, const char *prefix) +{ + return prefixcmp(str, SIZE_MAX, prefix, true); +} + +int git__prefixncmp_icase(const char *str, size_t str_n, const char *prefix) +{ + return prefixcmp(str, str_n, prefix, true); +} + +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; +} + +/* Similar to strtok, but does not collapse repeated tokens. */ +char *git__strsep(char **end, const char *sep) +{ + char *start = *end, *ptr = *end; + + while (*ptr && !strchr(sep, *ptr)) + ++ptr; + + if (*ptr) { + *end = ptr + 1; + *ptr = '\0'; + + return start; + } + + return NULL; +} + +size_t git__linenlen(const char *buffer, size_t buffer_len) +{ + char *nl = memchr(buffer, '\n', buffer_len); + return nl ? (size_t)(nl - buffer) + 1 : buffer_len; +} + +/* + * Adapted Not So Naive algorithm from http://www-igm.univ-mlv.fr/~lecroq/string/ + */ +const void * git__memmem(const void *haystack, size_t haystacklen, + const void *needle, size_t needlelen) +{ + const char *h, *n; + size_t j, k, l; + + if (needlelen > haystacklen || !haystacklen || !needlelen) + return NULL; + + h = (const char *) haystack, + n = (const char *) needle; + + if (needlelen == 1) + return memchr(haystack, *n, haystacklen); + + if (n[0] == n[1]) { + k = 2; + l = 1; + } else { + k = 1; + l = 2; + } + + j = 0; + while (j <= haystacklen - needlelen) { + if (n[1] != h[j + 1]) { + j += k; + } else { + if (memcmp(n + 2, h + j + 2, needlelen - 2) == 0 && + n[0] == h[j]) + return h + j; + j += l; + } + } + + 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) { + printf("%08" PRIxZ " ", (i * LINE_WIDTH)); + + line = buffer + (i * LINE_WIDTH); + for (j = 0; j < LINE_WIDTH; ++j, ++line) { + printf("%02x ", (unsigned char)*line & 0xFF); + + if (j == (LINE_WIDTH / 2)) + printf(" "); + } + + 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) { + printf("%08" PRIxZ " ", (line_count * LINE_WIDTH)); + + line = buffer + (line_count * LINE_WIDTH); + for (j = 0; j < last_line; ++j, ++line) { + printf("%02x ", (unsigned char)*line & 0xFF); + + if (j == (LINE_WIDTH / 2)) + printf(" "); + } + + if (j < (LINE_WIDTH / 2)) + printf(" "); + 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; + /* fall through */ + case 2: k1 ^= tail[1] << 8; + /* fall through */ + 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 modified `bsearch` from the BSD glibc. + * + * Copyright (c) 1990 Regents of the University of California. + * All rights reserved. + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * 1. Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * 2. Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * 3. [rescinded 22 July 1999] + * 4. Neither the name of the University nor the names of its contributors + * may be used to endorse or promote products derived from this software + * without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND + * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE + * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE + * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE + * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL + * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS + * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT + * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY + * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF + * SUCH DAMAGE. + */ +int git__bsearch( + void **array, + size_t array_len, + const void *key, + int (*compare)(const void *, const void *), + size_t *position) +{ + size_t lim; + int cmp = -1; + void **part, **base = array; + + for (lim = array_len; lim != 0; lim >>= 1) { + part = base + (lim >> 1); + cmp = (*compare)(key, *part); + if (cmp == 0) { + base = part; + break; + } + if (cmp > 0) { /* key > p; take right partition */ + base = part + 1; + lim--; + } /* else take left partition */ + } + + if (position) + *position = (base - array); + + return (cmp == 0) ? 0 : GIT_ENOTFOUND; +} + +int git__bsearch_r( + void **array, + size_t array_len, + const void *key, + int (*compare_r)(const void *, const void *, void *), + void *payload, + size_t *position) +{ + size_t lim; + int cmp = -1; + void **part, **base = array; + + for (lim = array_len; lim != 0; lim >>= 1) { + part = base + (lim >> 1); + cmp = (*compare_r)(key, *part, payload); + if (cmp == 0) { + base = part; + break; + } + if (cmp > 0) { /* key > p; take right partition */ + base = part + 1; + lim--; + } /* else take left partition */ + } + + if (position) + *position = (base - array); + + return (cmp == 0) ? 0 : GIT_ENOTFOUND; +} + +/** + * A strcmp wrapper + * + * We don't want direct pointers to the CRT on Windows, we may + * get stdcall conflicts. + */ +int git__strcmp_cb(const void *a, const void *b) +{ + return strcmp((const char *)a, (const char *)b); +} + +int git__strcasecmp_cb(const void *a, const void *b) +{ + return strcasecmp((const char *)a, (const char *)b); +} + +int git__parse_bool(int *out, const char *value) +{ + /* A missing value means true */ + if (value == NULL || + !strcasecmp(value, "true") || + !strcasecmp(value, "yes") || + !strcasecmp(value, "on")) { + *out = 1; + return 0; + } + if (!strcasecmp(value, "false") || + !strcasecmp(value, "no") || + !strcasecmp(value, "off") || + value[0] == '\0') { + *out = 0; + return 0; + } + + return -1; +} + +size_t git__unescape(char *str) +{ + char *scan, *pos = str; + + if (!str) + return 0; + + for (scan = str; *scan; pos++, scan++) { + if (*scan == '\\' && *(scan + 1) != '\0') + scan++; /* skip '\' but include next char */ + if (pos != scan) + *pos = *scan; + } + + if (pos != scan) { + *pos = '\0'; + } + + return (pos - str); +} + +#if defined(GIT_QSORT_S) || defined(GIT_QSORT_R_BSD) +typedef struct { + git__sort_r_cmp cmp; + void *payload; +} git__qsort_r_glue; + +static int GIT_LIBGIT2_CALL git__qsort_r_glue_cmp( + void *payload, const void *a, const void *b) +{ + git__qsort_r_glue *glue = payload; + return glue->cmp(a, b, glue->payload); +} +#endif + + +#if !defined(GIT_QSORT_R_BSD) && \ + !defined(GIT_QSORT_R_GNU) && \ + !defined(GIT_QSORT_S) +static void swap(uint8_t *a, uint8_t *b, size_t elsize) +{ + char tmp[256]; + + while (elsize) { + size_t n = elsize < sizeof(tmp) ? elsize : sizeof(tmp); + memcpy(tmp, a + elsize - n, n); + memcpy(a + elsize - n, b + elsize - n, n); + memcpy(b + elsize - n, tmp, n); + elsize -= n; + } +} + +static void insertsort( + void *els, size_t nel, size_t elsize, + git__sort_r_cmp cmp, void *payload) +{ + uint8_t *base = els; + uint8_t *end = base + nel * elsize; + uint8_t *i, *j; + + for (i = base + elsize; i < end; i += elsize) + for (j = i; j > base && cmp(j, j - elsize, payload) < 0; j -= elsize) + swap(j, j - elsize, elsize); +} +#endif + +void git__qsort_r( + void *els, size_t nel, size_t elsize, git__sort_r_cmp cmp, void *payload) +{ +#if defined(GIT_QSORT_R_BSD) + git__qsort_r_glue glue = { cmp, payload }; + qsort_r(els, nel, elsize, &glue, git__qsort_r_glue_cmp); +#elif defined(GIT_QSORT_R_GNU) + qsort_r(els, nel, elsize, cmp, payload); +#elif defined(GIT_QSORT_S) + git__qsort_r_glue glue = { cmp, payload }; + qsort_s(els, nel, elsize, git__qsort_r_glue_cmp, &glue); +#else + insertsort(els, nel, elsize, cmp, payload); +#endif +} + +#ifdef GIT_WIN32 +int git__getenv(git_str *out, const char *name) +{ + wchar_t *wide_name = NULL, *wide_value = NULL; + DWORD value_len; + int error = -1; + + git_str_clear(out); + + if (git__utf8_to_16_alloc(&wide_name, name) < 0) + return -1; + + if ((value_len = GetEnvironmentVariableW(wide_name, NULL, 0)) > 0) { + wide_value = git__malloc(value_len * sizeof(wchar_t)); + GIT_ERROR_CHECK_ALLOC(wide_value); + + value_len = GetEnvironmentVariableW(wide_name, wide_value, value_len); + } + + if (value_len) + error = git_str_put_w(out, wide_value, value_len); + else if (GetLastError() == ERROR_SUCCESS || GetLastError() == ERROR_ENVVAR_NOT_FOUND) + error = GIT_ENOTFOUND; + else + git_error_set(GIT_ERROR_OS, "could not read environment variable '%s'", name); + + git__free(wide_name); + git__free(wide_value); + return error; +} +#else +int git__getenv(git_str *out, const char *name) +{ + const char *val = getenv(name); + + git_str_clear(out); + + if (!val) + return GIT_ENOTFOUND; + + return git_str_puts(out, val); +} +#endif + +/* + * By doing this in two steps we can at least get + * the function to be somewhat coherent, even + * with this disgusting nest of #ifdefs. + */ +#ifndef _SC_NPROCESSORS_ONLN +# ifdef _SC_NPROC_ONLN +# define _SC_NPROCESSORS_ONLN _SC_NPROC_ONLN +# elif defined _SC_CRAY_NCPU +# define _SC_NPROCESSORS_ONLN _SC_CRAY_NCPU +# endif +#endif + +int git__online_cpus(void) +{ +#ifdef _SC_NPROCESSORS_ONLN + long ncpus; +#endif + +#ifdef _WIN32 + SYSTEM_INFO info; + GetSystemInfo(&info); + + if ((int)info.dwNumberOfProcessors > 0) + return (int)info.dwNumberOfProcessors; +#elif defined(hpux) || defined(__hpux) || defined(_hpux) + struct pst_dynamic psd; + + if (!pstat_getdynamic(&psd, sizeof(psd), (size_t)1, 0)) + return (int)psd.psd_proc_cnt; +#endif + +#ifdef _SC_NPROCESSORS_ONLN + if ((ncpus = (long)sysconf(_SC_NPROCESSORS_ONLN)) > 0) + return (int)ncpus; +#endif + + return 1; +} |