]> git.proxmox.com Git - libgit2.git/blob - src/util.c
New upstream version 1.4.3+dfsg.1
[libgit2.git] / src / util.c
1 /*
2 * Copyright (C) the libgit2 contributors. All rights reserved.
3 *
4 * This file is part of libgit2, distributed under the GNU GPL v2 with
5 * a Linking Exception. For full terms see the included COPYING file.
6 */
7
8 #include "util.h"
9
10 #include "common.h"
11
12 #ifdef GIT_WIN32
13 # include "win32/utf-conv.h"
14 # include "win32/w32_buffer.h"
15
16 # ifndef WIN32_LEAN_AND_MEAN
17 # define WIN32_LEAN_AND_MEAN
18 # endif
19 # include <windows.h>
20
21 # ifdef GIT_QSORT_S
22 # include <search.h>
23 # endif
24 #endif
25
26 #ifdef _MSC_VER
27 # include <Shlwapi.h>
28 #endif
29
30 #if defined(hpux) || defined(__hpux) || defined(_hpux)
31 # include <sys/pstat.h>
32 #endif
33
34 int git__strntol64(int64_t *result, const char *nptr, size_t nptr_len, const char **endptr, int base)
35 {
36 const char *p;
37 int64_t n, nn, v;
38 int c, ovfl, neg, ndig;
39
40 p = nptr;
41 neg = 0;
42 n = 0;
43 ndig = 0;
44 ovfl = 0;
45
46 /*
47 * White space
48 */
49 while (nptr_len && git__isspace(*p))
50 p++, nptr_len--;
51
52 if (!nptr_len)
53 goto Return;
54
55 /*
56 * Sign
57 */
58 if (*p == '-' || *p == '+') {
59 if (*p == '-')
60 neg = 1;
61 p++;
62 nptr_len--;
63 }
64
65 if (!nptr_len)
66 goto Return;
67
68 /*
69 * Automatically detect the base if none was given to us.
70 * Right now, we assume that a number starting with '0x'
71 * is hexadecimal and a number starting with '0' is
72 * octal.
73 */
74 if (base == 0) {
75 if (*p != '0')
76 base = 10;
77 else if (nptr_len > 2 && (p[1] == 'x' || p[1] == 'X'))
78 base = 16;
79 else
80 base = 8;
81 }
82
83 if (base < 0 || 36 < base)
84 goto Return;
85
86 /*
87 * Skip prefix of '0x'-prefixed hexadecimal numbers. There is no
88 * need to do the same for '0'-prefixed octal numbers as a
89 * leading '0' does not have any impact. Also, if we skip a
90 * leading '0' in such a string, then we may end up with no
91 * digits left and produce an error later on which isn't one.
92 */
93 if (base == 16 && nptr_len > 2 && p[0] == '0' && (p[1] == 'x' || p[1] == 'X')) {
94 p += 2;
95 nptr_len -= 2;
96 }
97
98 /*
99 * Non-empty sequence of digits
100 */
101 for (; nptr_len > 0; p++,ndig++,nptr_len--) {
102 c = *p;
103 v = base;
104 if ('0'<=c && c<='9')
105 v = c - '0';
106 else if ('a'<=c && c<='z')
107 v = c - 'a' + 10;
108 else if ('A'<=c && c<='Z')
109 v = c - 'A' + 10;
110 if (v >= base)
111 break;
112 v = neg ? -v : v;
113 if (git__multiply_int64_overflow(&nn, n, base) || git__add_int64_overflow(&n, nn, v)) {
114 ovfl = 1;
115 /* Keep on iterating until the end of this number */
116 continue;
117 }
118 }
119
120 Return:
121 if (ndig == 0) {
122 git_error_set(GIT_ERROR_INVALID, "failed to convert string to long: not a number");
123 return -1;
124 }
125
126 if (endptr)
127 *endptr = p;
128
129 if (ovfl) {
130 git_error_set(GIT_ERROR_INVALID, "failed to convert string to long: overflow error");
131 return -1;
132 }
133
134 *result = n;
135 return 0;
136 }
137
138 int git__strntol32(int32_t *result, const char *nptr, size_t nptr_len, const char **endptr, int base)
139 {
140 const char *tmp_endptr;
141 int32_t tmp_int;
142 int64_t tmp_long;
143 int error;
144
145 if ((error = git__strntol64(&tmp_long, nptr, nptr_len, &tmp_endptr, base)) < 0)
146 return error;
147
148 tmp_int = tmp_long & 0xFFFFFFFF;
149 if (tmp_int != tmp_long) {
150 int len = (int)(tmp_endptr - nptr);
151 git_error_set(GIT_ERROR_INVALID, "failed to convert: '%.*s' is too large", len, nptr);
152 return -1;
153 }
154
155 *result = tmp_int;
156 if (endptr)
157 *endptr = tmp_endptr;
158
159 return error;
160 }
161
162 int git__strcasecmp(const char *a, const char *b)
163 {
164 while (*a && *b && git__tolower(*a) == git__tolower(*b))
165 ++a, ++b;
166 return ((unsigned char)git__tolower(*a) - (unsigned char)git__tolower(*b));
167 }
168
169 int git__strcasesort_cmp(const char *a, const char *b)
170 {
171 int cmp = 0;
172
173 while (*a && *b) {
174 if (*a != *b) {
175 if (git__tolower(*a) != git__tolower(*b))
176 break;
177 /* use case in sort order even if not in equivalence */
178 if (!cmp)
179 cmp = (int)(*(const uint8_t *)a) - (int)(*(const uint8_t *)b);
180 }
181
182 ++a, ++b;
183 }
184
185 if (*a || *b)
186 return (unsigned char)git__tolower(*a) - (unsigned char)git__tolower(*b);
187
188 return cmp;
189 }
190
191 int git__strncasecmp(const char *a, const char *b, size_t sz)
192 {
193 int al, bl;
194
195 do {
196 al = (unsigned char)git__tolower(*a);
197 bl = (unsigned char)git__tolower(*b);
198 ++a, ++b;
199 } while (--sz && al && al == bl);
200
201 return al - bl;
202 }
203
204 void git__strntolower(char *str, size_t len)
205 {
206 size_t i;
207
208 for (i = 0; i < len; ++i) {
209 str[i] = (char)git__tolower(str[i]);
210 }
211 }
212
213 void git__strtolower(char *str)
214 {
215 git__strntolower(str, strlen(str));
216 }
217
218 GIT_INLINE(int) prefixcmp(const char *str, size_t str_n, const char *prefix, bool icase)
219 {
220 int s, p;
221
222 while (str_n--) {
223 s = (unsigned char)*str++;
224 p = (unsigned char)*prefix++;
225
226 if (icase) {
227 s = git__tolower(s);
228 p = git__tolower(p);
229 }
230
231 if (!p)
232 return 0;
233
234 if (s != p)
235 return s - p;
236 }
237
238 return (0 - *prefix);
239 }
240
241 int git__prefixcmp(const char *str, const char *prefix)
242 {
243 unsigned char s, p;
244
245 while (1) {
246 p = *prefix++;
247 s = *str++;
248
249 if (!p)
250 return 0;
251
252 if (s != p)
253 return s - p;
254 }
255 }
256
257 int git__prefixncmp(const char *str, size_t str_n, const char *prefix)
258 {
259 return prefixcmp(str, str_n, prefix, false);
260 }
261
262 int git__prefixcmp_icase(const char *str, const char *prefix)
263 {
264 return prefixcmp(str, SIZE_MAX, prefix, true);
265 }
266
267 int git__prefixncmp_icase(const char *str, size_t str_n, const char *prefix)
268 {
269 return prefixcmp(str, str_n, prefix, true);
270 }
271
272 int git__suffixcmp(const char *str, const char *suffix)
273 {
274 size_t a = strlen(str);
275 size_t b = strlen(suffix);
276 if (a < b)
277 return -1;
278 return strcmp(str + (a - b), suffix);
279 }
280
281 char *git__strtok(char **end, const char *sep)
282 {
283 char *ptr = *end;
284
285 while (*ptr && strchr(sep, *ptr))
286 ++ptr;
287
288 if (*ptr) {
289 char *start = ptr;
290 *end = start + 1;
291
292 while (**end && !strchr(sep, **end))
293 ++*end;
294
295 if (**end) {
296 **end = '\0';
297 ++*end;
298 }
299
300 return start;
301 }
302
303 return NULL;
304 }
305
306 /* Similar to strtok, but does not collapse repeated tokens. */
307 char *git__strsep(char **end, const char *sep)
308 {
309 char *start = *end, *ptr = *end;
310
311 while (*ptr && !strchr(sep, *ptr))
312 ++ptr;
313
314 if (*ptr) {
315 *end = ptr + 1;
316 *ptr = '\0';
317
318 return start;
319 }
320
321 return NULL;
322 }
323
324 size_t git__linenlen(const char *buffer, size_t buffer_len)
325 {
326 char *nl = memchr(buffer, '\n', buffer_len);
327 return nl ? (size_t)(nl - buffer) + 1 : buffer_len;
328 }
329
330 /*
331 * Adapted Not So Naive algorithm from http://www-igm.univ-mlv.fr/~lecroq/string/
332 */
333 const void * git__memmem(const void *haystack, size_t haystacklen,
334 const void *needle, size_t needlelen)
335 {
336 const char *h, *n;
337 size_t j, k, l;
338
339 if (needlelen > haystacklen || !haystacklen || !needlelen)
340 return NULL;
341
342 h = (const char *) haystack,
343 n = (const char *) needle;
344
345 if (needlelen == 1)
346 return memchr(haystack, *n, haystacklen);
347
348 if (n[0] == n[1]) {
349 k = 2;
350 l = 1;
351 } else {
352 k = 1;
353 l = 2;
354 }
355
356 j = 0;
357 while (j <= haystacklen - needlelen) {
358 if (n[1] != h[j + 1]) {
359 j += k;
360 } else {
361 if (memcmp(n + 2, h + j + 2, needlelen - 2) == 0 &&
362 n[0] == h[j])
363 return h + j;
364 j += l;
365 }
366 }
367
368 return NULL;
369 }
370
371 void git__hexdump(const char *buffer, size_t len)
372 {
373 static const size_t LINE_WIDTH = 16;
374
375 size_t line_count, last_line, i, j;
376 const char *line;
377
378 line_count = (len / LINE_WIDTH);
379 last_line = (len % LINE_WIDTH);
380
381 for (i = 0; i < line_count; ++i) {
382 printf("%08" PRIxZ " ", (i * LINE_WIDTH));
383
384 line = buffer + (i * LINE_WIDTH);
385 for (j = 0; j < LINE_WIDTH; ++j, ++line) {
386 printf("%02x ", (unsigned char)*line & 0xFF);
387
388 if (j == (LINE_WIDTH / 2))
389 printf(" ");
390 }
391
392 printf(" |");
393
394 line = buffer + (i * LINE_WIDTH);
395 for (j = 0; j < LINE_WIDTH; ++j, ++line)
396 printf("%c", (*line >= 32 && *line <= 126) ? *line : '.');
397
398 printf("|\n");
399 }
400
401 if (last_line > 0) {
402 printf("%08" PRIxZ " ", (line_count * LINE_WIDTH));
403
404 line = buffer + (line_count * LINE_WIDTH);
405 for (j = 0; j < last_line; ++j, ++line) {
406 printf("%02x ", (unsigned char)*line & 0xFF);
407
408 if (j == (LINE_WIDTH / 2))
409 printf(" ");
410 }
411
412 if (j < (LINE_WIDTH / 2))
413 printf(" ");
414 for (j = 0; j < (LINE_WIDTH - last_line); ++j)
415 printf(" ");
416
417 printf(" |");
418
419 line = buffer + (line_count * LINE_WIDTH);
420 for (j = 0; j < last_line; ++j, ++line)
421 printf("%c", (*line >= 32 && *line <= 126) ? *line : '.');
422
423 printf("|\n");
424 }
425
426 printf("\n");
427 }
428
429 #ifdef GIT_LEGACY_HASH
430 uint32_t git__hash(const void *key, int len, unsigned int seed)
431 {
432 const uint32_t m = 0x5bd1e995;
433 const int r = 24;
434 uint32_t h = seed ^ len;
435
436 const unsigned char *data = (const unsigned char *)key;
437
438 while(len >= 4) {
439 uint32_t k = *(uint32_t *)data;
440
441 k *= m;
442 k ^= k >> r;
443 k *= m;
444
445 h *= m;
446 h ^= k;
447
448 data += 4;
449 len -= 4;
450 }
451
452 switch(len) {
453 case 3: h ^= data[2] << 16;
454 case 2: h ^= data[1] << 8;
455 case 1: h ^= data[0];
456 h *= m;
457 };
458
459 h ^= h >> 13;
460 h *= m;
461 h ^= h >> 15;
462
463 return h;
464 }
465 #else
466 /*
467 Cross-platform version of Murmurhash3
468 http://code.google.com/p/smhasher/wiki/MurmurHash3
469 by Austin Appleby (aappleby@gmail.com)
470
471 This code is on the public domain.
472 */
473 uint32_t git__hash(const void *key, int len, uint32_t seed)
474 {
475
476 #define MURMUR_BLOCK() {\
477 k1 *= c1; \
478 k1 = git__rotl(k1,11);\
479 k1 *= c2;\
480 h1 ^= k1;\
481 h1 = h1*3 + 0x52dce729;\
482 c1 = c1*5 + 0x7b7d159c;\
483 c2 = c2*5 + 0x6bce6396;\
484 }
485
486 const uint8_t *data = (const uint8_t*)key;
487 const int nblocks = len / 4;
488
489 const uint32_t *blocks = (const uint32_t *)(data + nblocks * 4);
490 const uint8_t *tail = (const uint8_t *)(data + nblocks * 4);
491
492 uint32_t h1 = 0x971e137b ^ seed;
493 uint32_t k1;
494
495 uint32_t c1 = 0x95543787;
496 uint32_t c2 = 0x2ad7eb25;
497
498 int i;
499
500 for (i = -nblocks; i; i++) {
501 k1 = blocks[i];
502 MURMUR_BLOCK();
503 }
504
505 k1 = 0;
506
507 switch(len & 3) {
508 case 3: k1 ^= tail[2] << 16;
509 /* fall through */
510 case 2: k1 ^= tail[1] << 8;
511 /* fall through */
512 case 1: k1 ^= tail[0];
513 MURMUR_BLOCK();
514 }
515
516 h1 ^= len;
517 h1 ^= h1 >> 16;
518 h1 *= 0x85ebca6b;
519 h1 ^= h1 >> 13;
520 h1 *= 0xc2b2ae35;
521 h1 ^= h1 >> 16;
522
523 return h1;
524 }
525 #endif
526
527 /**
528 * A modified `bsearch` from the BSD glibc.
529 *
530 * Copyright (c) 1990 Regents of the University of California.
531 * All rights reserved.
532 * Redistribution and use in source and binary forms, with or without
533 * modification, are permitted provided that the following conditions
534 * are met:
535 * 1. Redistributions of source code must retain the above copyright
536 * notice, this list of conditions and the following disclaimer.
537 * 2. Redistributions in binary form must reproduce the above copyright
538 * notice, this list of conditions and the following disclaimer in the
539 * documentation and/or other materials provided with the distribution.
540 * 3. [rescinded 22 July 1999]
541 * 4. Neither the name of the University nor the names of its contributors
542 * may be used to endorse or promote products derived from this software
543 * without specific prior written permission.
544 *
545 * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
546 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
547 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
548 * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
549 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
550 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
551 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
552 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
553 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
554 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
555 * SUCH DAMAGE.
556 */
557 int git__bsearch(
558 void **array,
559 size_t array_len,
560 const void *key,
561 int (*compare)(const void *, const void *),
562 size_t *position)
563 {
564 size_t lim;
565 int cmp = -1;
566 void **part, **base = array;
567
568 for (lim = array_len; lim != 0; lim >>= 1) {
569 part = base + (lim >> 1);
570 cmp = (*compare)(key, *part);
571 if (cmp == 0) {
572 base = part;
573 break;
574 }
575 if (cmp > 0) { /* key > p; take right partition */
576 base = part + 1;
577 lim--;
578 } /* else take left partition */
579 }
580
581 if (position)
582 *position = (base - array);
583
584 return (cmp == 0) ? 0 : GIT_ENOTFOUND;
585 }
586
587 int git__bsearch_r(
588 void **array,
589 size_t array_len,
590 const void *key,
591 int (*compare_r)(const void *, const void *, void *),
592 void *payload,
593 size_t *position)
594 {
595 size_t lim;
596 int cmp = -1;
597 void **part, **base = array;
598
599 for (lim = array_len; lim != 0; lim >>= 1) {
600 part = base + (lim >> 1);
601 cmp = (*compare_r)(key, *part, payload);
602 if (cmp == 0) {
603 base = part;
604 break;
605 }
606 if (cmp > 0) { /* key > p; take right partition */
607 base = part + 1;
608 lim--;
609 } /* else take left partition */
610 }
611
612 if (position)
613 *position = (base - array);
614
615 return (cmp == 0) ? 0 : GIT_ENOTFOUND;
616 }
617
618 /**
619 * A strcmp wrapper
620 *
621 * We don't want direct pointers to the CRT on Windows, we may
622 * get stdcall conflicts.
623 */
624 int git__strcmp_cb(const void *a, const void *b)
625 {
626 return strcmp((const char *)a, (const char *)b);
627 }
628
629 int git__strcasecmp_cb(const void *a, const void *b)
630 {
631 return strcasecmp((const char *)a, (const char *)b);
632 }
633
634 int git__parse_bool(int *out, const char *value)
635 {
636 /* A missing value means true */
637 if (value == NULL ||
638 !strcasecmp(value, "true") ||
639 !strcasecmp(value, "yes") ||
640 !strcasecmp(value, "on")) {
641 *out = 1;
642 return 0;
643 }
644 if (!strcasecmp(value, "false") ||
645 !strcasecmp(value, "no") ||
646 !strcasecmp(value, "off") ||
647 value[0] == '\0') {
648 *out = 0;
649 return 0;
650 }
651
652 return -1;
653 }
654
655 size_t git__unescape(char *str)
656 {
657 char *scan, *pos = str;
658
659 if (!str)
660 return 0;
661
662 for (scan = str; *scan; pos++, scan++) {
663 if (*scan == '\\' && *(scan + 1) != '\0')
664 scan++; /* skip '\' but include next char */
665 if (pos != scan)
666 *pos = *scan;
667 }
668
669 if (pos != scan) {
670 *pos = '\0';
671 }
672
673 return (pos - str);
674 }
675
676 #if defined(GIT_QSORT_S) || defined(GIT_QSORT_R_BSD)
677 typedef struct {
678 git__sort_r_cmp cmp;
679 void *payload;
680 } git__qsort_r_glue;
681
682 static int GIT_LIBGIT2_CALL git__qsort_r_glue_cmp(
683 void *payload, const void *a, const void *b)
684 {
685 git__qsort_r_glue *glue = payload;
686 return glue->cmp(a, b, glue->payload);
687 }
688 #endif
689
690
691 #if !defined(GIT_QSORT_R_BSD) && \
692 !defined(GIT_QSORT_R_GNU) && \
693 !defined(GIT_QSORT_S)
694 static void swap(uint8_t *a, uint8_t *b, size_t elsize)
695 {
696 char tmp[256];
697
698 while (elsize) {
699 size_t n = elsize < sizeof(tmp) ? elsize : sizeof(tmp);
700 memcpy(tmp, a + elsize - n, n);
701 memcpy(a + elsize - n, b + elsize - n, n);
702 memcpy(b + elsize - n, tmp, n);
703 elsize -= n;
704 }
705 }
706
707 static void insertsort(
708 void *els, size_t nel, size_t elsize,
709 git__sort_r_cmp cmp, void *payload)
710 {
711 uint8_t *base = els;
712 uint8_t *end = base + nel * elsize;
713 uint8_t *i, *j;
714
715 for (i = base + elsize; i < end; i += elsize)
716 for (j = i; j > base && cmp(j, j - elsize, payload) < 0; j -= elsize)
717 swap(j, j - elsize, elsize);
718 }
719 #endif
720
721 void git__qsort_r(
722 void *els, size_t nel, size_t elsize, git__sort_r_cmp cmp, void *payload)
723 {
724 #if defined(GIT_QSORT_R_BSD)
725 git__qsort_r_glue glue = { cmp, payload };
726 qsort_r(els, nel, elsize, &glue, git__qsort_r_glue_cmp);
727 #elif defined(GIT_QSORT_R_GNU)
728 qsort_r(els, nel, elsize, cmp, payload);
729 #elif defined(GIT_QSORT_S)
730 git__qsort_r_glue glue = { cmp, payload };
731 qsort_s(els, nel, elsize, git__qsort_r_glue_cmp, &glue);
732 #else
733 insertsort(els, nel, elsize, cmp, payload);
734 #endif
735 }
736
737 #ifdef GIT_WIN32
738 int git__getenv(git_str *out, const char *name)
739 {
740 wchar_t *wide_name = NULL, *wide_value = NULL;
741 DWORD value_len;
742 int error = -1;
743
744 git_str_clear(out);
745
746 if (git__utf8_to_16_alloc(&wide_name, name) < 0)
747 return -1;
748
749 if ((value_len = GetEnvironmentVariableW(wide_name, NULL, 0)) > 0) {
750 wide_value = git__malloc(value_len * sizeof(wchar_t));
751 GIT_ERROR_CHECK_ALLOC(wide_value);
752
753 value_len = GetEnvironmentVariableW(wide_name, wide_value, value_len);
754 }
755
756 if (value_len)
757 error = git_str_put_w(out, wide_value, value_len);
758 else if (GetLastError() == ERROR_SUCCESS || GetLastError() == ERROR_ENVVAR_NOT_FOUND)
759 error = GIT_ENOTFOUND;
760 else
761 git_error_set(GIT_ERROR_OS, "could not read environment variable '%s'", name);
762
763 git__free(wide_name);
764 git__free(wide_value);
765 return error;
766 }
767 #else
768 int git__getenv(git_str *out, const char *name)
769 {
770 const char *val = getenv(name);
771
772 git_str_clear(out);
773
774 if (!val)
775 return GIT_ENOTFOUND;
776
777 return git_str_puts(out, val);
778 }
779 #endif
780
781 /*
782 * By doing this in two steps we can at least get
783 * the function to be somewhat coherent, even
784 * with this disgusting nest of #ifdefs.
785 */
786 #ifndef _SC_NPROCESSORS_ONLN
787 # ifdef _SC_NPROC_ONLN
788 # define _SC_NPROCESSORS_ONLN _SC_NPROC_ONLN
789 # elif defined _SC_CRAY_NCPU
790 # define _SC_NPROCESSORS_ONLN _SC_CRAY_NCPU
791 # endif
792 #endif
793
794 int git__online_cpus(void)
795 {
796 #ifdef _SC_NPROCESSORS_ONLN
797 long ncpus;
798 #endif
799
800 #ifdef _WIN32
801 SYSTEM_INFO info;
802 GetSystemInfo(&info);
803
804 if ((int)info.dwNumberOfProcessors > 0)
805 return (int)info.dwNumberOfProcessors;
806 #elif defined(hpux) || defined(__hpux) || defined(_hpux)
807 struct pst_dynamic psd;
808
809 if (!pstat_getdynamic(&psd, sizeof(psd), (size_t)1, 0))
810 return (int)psd.psd_proc_cnt;
811 #endif
812
813 #ifdef _SC_NPROCESSORS_ONLN
814 if ((ncpus = (long)sysconf(_SC_NPROCESSORS_ONLN)) > 0)
815 return (int)ncpus;
816 #endif
817
818 return 1;
819 }