diff options
Diffstat (limited to 'system')
27 files changed, 786 insertions, 0 deletions
diff --git a/system/lib/libc.symbols b/system/lib/libc.symbols index 53a27082..eb2053ce 100644 --- a/system/lib/libc.symbols +++ b/system/lib/libc.symbols @@ -50,6 +50,8 @@ T __towrite T __uflow T atof + T atoi + T atol W bulk_free W calloc W free diff --git a/system/lib/libc/musl/arch/js/atomic.h b/system/lib/libc/musl/arch/js/atomic.h new file mode 100644 index 00000000..07d5d4b6 --- /dev/null +++ b/system/lib/libc/musl/arch/js/atomic.h @@ -0,0 +1,103 @@ +#ifndef _INTERNAL_ATOMIC_H +#define _INTERNAL_ATOMIC_H + +#include <stdint.h> + +static inline int a_ctz_l(unsigned long x) +{ + if (x == 0) + return 32; + int nTrailingZeros = 0; + while(!(x&1)) + { + ++nTrailingZeros; + x >>= 1; + } + return nTrailingZeros; +} + +static inline int a_ctz_64(uint64_t x) +{ + uint32_t lo = (uint32_t)x; + if (lo == 0) + return a_ctz_l((unsigned long)(x >> 32)) + 32; + else + return a_ctz_l((unsigned long)lo); +} + +static inline void a_and_64(volatile uint64_t *p, uint64_t v) +{ + *p &= v; +} + +static inline void a_or_64(volatile uint64_t *p, uint64_t v) +{ + *p |= v; +} + +static inline void a_store_l(volatile void *p, long x) +{ + *(long*)p = x; +} + +static inline void a_or_l(volatile void *p, long v) +{ + *(long*)p |= v; +} + +static inline void *a_cas_p(volatile void *p, void *t, void *s) +{ + if (*(long*)p == t) + *(long*)p = s; + return t; +} + +static inline long a_cas_l(volatile void *p, long t, long s) +{ + if (*(long*)p == t) + *(long*)p = s; + return t; +} + +static inline int a_cas(volatile int *p, int t, int s) +{ + if (*p == t) + *p = s; + return t; +} + +static inline void a_or(volatile void *p, int v) +{ + *(int*)p |= v; +} + +static inline void a_and(volatile void *p, int v) +{ + *(int*)p &= v; +} + +static inline void a_inc(volatile int *x) +{ + ++*x; +} + +static inline void a_dec(volatile int *x) +{ + --*x; +} + +static inline void a_store(volatile int *p, int x) +{ + *p = x; +} + +static inline void a_spin() +{ +} + +static inline void a_crash() +{ +} + + +#endif diff --git a/system/lib/libc/musl/src/stdlib/atoi.c b/system/lib/libc/musl/src/stdlib/atoi.c new file mode 100644 index 00000000..9baca7b8 --- /dev/null +++ b/system/lib/libc/musl/src/stdlib/atoi.c @@ -0,0 +1,16 @@ +#include <stdlib.h> +#include <ctype.h> + +int atoi(const char *s) +{ + int n=0, neg=0; + while (isspace(*s)) s++; + switch (*s) { + case '-': neg=1; + case '+': s++; + } + /* Compute n as a negative number to avoid overflow on INT_MIN */ + while (isdigit(*s)) + n = 10*n - (*s++ - '0'); + return neg ? n : -n; +} diff --git a/system/lib/libc/musl/src/stdlib/atol.c b/system/lib/libc/musl/src/stdlib/atol.c new file mode 100644 index 00000000..140ea3ea --- /dev/null +++ b/system/lib/libc/musl/src/stdlib/atol.c @@ -0,0 +1,17 @@ +#include <stdlib.h> +#include <ctype.h> + +long atol(const char *s) +{ + long n=0; + int neg=0; + while (isspace(*s)) s++; + switch (*s) { + case '-': neg=1; + case '+': s++; + } + /* Compute n as a negative number to avoid overflow on LONG_MIN */ + while (isdigit(*s)) + n = 10*n - (*s++ - '0'); + return neg ? n : -n; +} diff --git a/system/lib/libc/musl/src/stdlib/atoll.c b/system/lib/libc/musl/src/stdlib/atoll.c new file mode 100644 index 00000000..b6930489 --- /dev/null +++ b/system/lib/libc/musl/src/stdlib/atoll.c @@ -0,0 +1,17 @@ +#include <stdlib.h> +#include <ctype.h> + +long long atoll(const char *s) +{ + long long n=0; + int neg=0; + while (isspace(*s)) s++; + switch (*s) { + case '-': neg=1; + case '+': s++; + } + /* Compute n as a negative number to avoid overflow on LLONG_MIN */ + while (isdigit(*s)) + n = 10*n - (*s++ - '0'); + return neg ? n : -n; +} diff --git a/system/lib/libc/musl/src/stdlib/bsearch.c b/system/lib/libc/musl/src/stdlib/bsearch.c new file mode 100644 index 00000000..61d89367 --- /dev/null +++ b/system/lib/libc/musl/src/stdlib/bsearch.c @@ -0,0 +1,20 @@ +#include <stdlib.h> + +void *bsearch(const void *key, const void *base, size_t nel, size_t width, int (*cmp)(const void *, const void *)) +{ + void *try; + int sign; + while (nel > 0) { + try = (char *)base + width*(nel/2); + sign = cmp(key, try); + if (!sign) return try; + else if (nel == 1) break; + else if (sign < 0) + nel /= 2; + else { + base = try; + nel -= nel/2; + } + } + return NULL; +} diff --git a/system/lib/libc/musl/src/stdlib/qsort.c b/system/lib/libc/musl/src/stdlib/qsort.c new file mode 100644 index 00000000..434d9350 --- /dev/null +++ b/system/lib/libc/musl/src/stdlib/qsort.c @@ -0,0 +1,215 @@ +/* Copyright (C) 2011 by Valentin Ochs + * + * Permission is hereby granted, free of charge, to any person obtaining a copy + * of this software and associated documentation files (the "Software"), to + * deal in the Software without restriction, including without limitation the + * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or + * sell copies of the Software, and to permit persons to whom the Software is + * furnished to do so, subject to the following conditions: + * + * The above copyright notice and this permission notice shall be included in + * all copies or substantial portions of the Software. + * + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE + * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING + * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS + * IN THE SOFTWARE. + */ + +/* Minor changes by Rich Felker for integration in musl, 2011-04-27. */ + +#include <stdint.h> +#include <stdlib.h> +#include <string.h> + +#include "atomic.h" +#define ntz(x) a_ctz_l((x)) + +typedef int (*cmpfun)(const void *, const void *); + +static inline int pntz(size_t p[2]) { + int r = ntz(p[0] - 1); + if(r != 0 || (r = 8*sizeof(size_t) + ntz(p[1])) != 8*sizeof(size_t)) { + return r; + } + return 0; +} + +static void cycle(size_t width, unsigned char* ar[], int n) +{ + unsigned char tmp[256]; + size_t l; + int i; + + if(n < 2) { + return; + } + + ar[n] = tmp; + while(width) { + l = sizeof(tmp) < width ? sizeof(tmp) : width; + memcpy(ar[n], ar[0], l); + for(i = 0; i < n; i++) { + memcpy(ar[i], ar[i + 1], l); + ar[i] += l; + } + width -= l; + } +} + +/* shl() and shr() need n > 0 */ +static inline void shl(size_t p[2], int n) +{ + if(n >= 8 * sizeof(size_t)) { + n -= 8 * sizeof(size_t); + p[1] = p[0]; + p[0] = 0; + } + p[1] <<= n; + p[1] |= p[0] >> (sizeof(size_t) * 8 - n); + p[0] <<= n; +} + +static inline void shr(size_t p[2], int n) +{ + if(n >= 8 * sizeof(size_t)) { + n -= 8 * sizeof(size_t); + p[0] = p[1]; + p[1] = 0; + } + p[0] >>= n; + p[0] |= p[1] << (sizeof(size_t) * 8 - n); + p[1] >>= n; +} + +static void sift(unsigned char *head, size_t width, cmpfun cmp, int pshift, size_t lp[]) +{ + unsigned char *rt, *lf; + unsigned char *ar[14 * sizeof(size_t) + 1]; + int i = 1; + + ar[0] = head; + while(pshift > 1) { + rt = head - width; + lf = head - width - lp[pshift - 2]; + + if((*cmp)(ar[0], lf) >= 0 && (*cmp)(ar[0], rt) >= 0) { + break; + } + if((*cmp)(lf, rt) >= 0) { + ar[i++] = lf; + head = lf; + pshift -= 1; + } else { + ar[i++] = rt; + head = rt; + pshift -= 2; + } + } + cycle(width, ar, i); +} + +static void trinkle(unsigned char *head, size_t width, cmpfun cmp, size_t pp[2], int pshift, int trusty, size_t lp[]) +{ + unsigned char *stepson, + *rt, *lf; + size_t p[2]; + unsigned char *ar[14 * sizeof(size_t) + 1]; + int i = 1; + int trail; + + p[0] = pp[0]; + p[1] = pp[1]; + + ar[0] = head; + while(p[0] != 1 || p[1] != 0) { + stepson = head - lp[pshift]; + if((*cmp)(stepson, ar[0]) <= 0) { + break; + } + if(!trusty && pshift > 1) { + rt = head - width; + lf = head - width - lp[pshift - 2]; + if((*cmp)(rt, stepson) >= 0 || (*cmp)(lf, stepson) >= 0) { + break; + } + } + + ar[i++] = stepson; + head = stepson; + trail = pntz(p); + shr(p, trail); + pshift += trail; + trusty = 0; + } + if(!trusty) { + cycle(width, ar, i); + sift(head, width, cmp, pshift, lp); + } +} + +void qsort(void *base, size_t nel, size_t width, cmpfun cmp) +{ + size_t lp[12*sizeof(size_t)]; + size_t i, size = width * nel; + unsigned char *head, *high; + size_t p[2] = {1, 0}; + int pshift = 1; + int trail; + + if (!size) return; + + head = base; + high = head + size - width; + + /* Precompute Leonardo numbers, scaled by element width */ + for(lp[0]=lp[1]=width, i=2; (lp[i]=lp[i-2]+lp[i-1]+width) < size; i++); + + while(head < high) { + if((p[0] & 3) == 3) { + sift(head, width, cmp, pshift, lp); + shr(p, 2); + pshift += 2; + } else { + if(lp[pshift - 1] >= high - head) { + trinkle(head, width, cmp, p, pshift, 0, lp); + } else { + sift(head, width, cmp, pshift, lp); + } + + if(pshift == 1) { + shl(p, 1); + pshift = 0; + } else { + shl(p, pshift - 1); + pshift = 1; + } + } + + p[0] |= 1; + head += width; + } + + trinkle(head, width, cmp, p, pshift, 0, lp); + + while(pshift != 1 || p[0] != 1 || p[1] != 0) { + if(pshift <= 1) { + trail = pntz(p); + shr(p, trail); + pshift += trail; + } else { + shl(p, 2); + pshift -= 2; + p[0] ^= 7; + shr(p, 1); + trinkle(head - lp[pshift] - width, width, cmp, p, pshift + 1, 1, lp); + shl(p, 1); + p[0] |= 1; + trinkle(head - width, width, cmp, p, pshift, 1, lp); + } + head -= width; + } +} diff --git a/system/lib/libc/musl/src/string/bcmp.c b/system/lib/libc/musl/src/string/bcmp.c new file mode 100644 index 00000000..5d6a388b --- /dev/null +++ b/system/lib/libc/musl/src/string/bcmp.c @@ -0,0 +1,7 @@ +#include <string.h> +#include <strings.h> + +int bcmp(const void *s1, const void *s2, size_t n) +{ + return memcmp(s1, s2, n); +} diff --git a/system/lib/libc/musl/src/string/bcopy.c b/system/lib/libc/musl/src/string/bcopy.c new file mode 100644 index 00000000..e76272fc --- /dev/null +++ b/system/lib/libc/musl/src/string/bcopy.c @@ -0,0 +1,7 @@ +#include <string.h> +#include <strings.h> + +void bcopy(const void *s1, void *s2, size_t n) +{ + memmove(s2, s1, n); +} diff --git a/system/lib/libc/musl/src/string/bzero.c b/system/lib/libc/musl/src/string/bzero.c new file mode 100644 index 00000000..0f98b4a5 --- /dev/null +++ b/system/lib/libc/musl/src/string/bzero.c @@ -0,0 +1,7 @@ +#include <string.h> +#include <strings.h> + +void bzero(void *s, size_t n) +{ + memset(s, 0, n); +} diff --git a/system/lib/libc/musl/src/string/index.c b/system/lib/libc/musl/src/string/index.c new file mode 100644 index 00000000..dd611251 --- /dev/null +++ b/system/lib/libc/musl/src/string/index.c @@ -0,0 +1,7 @@ +#include <string.h> +#include <strings.h> + +char *index(const char *s, int c) +{ + return strchr(s, c); +} diff --git a/system/lib/libc/musl/src/string/memchr.c b/system/lib/libc/musl/src/string/memchr.c new file mode 100644 index 00000000..a0472f78 --- /dev/null +++ b/system/lib/libc/musl/src/string/memchr.c @@ -0,0 +1,24 @@ +#include <string.h> +#include <stdlib.h> +#include <stdint.h> +#include <limits.h> + +#define SS (sizeof(size_t)) +#define ALIGN (sizeof(size_t)-1) +#define ONES ((size_t)-1/UCHAR_MAX) +#define HIGHS (ONES * (UCHAR_MAX/2+1)) +#define HASZERO(x) ((x)-ONES & ~(x) & HIGHS) + +void *memchr(const void *src, int c, size_t n) +{ + const unsigned char *s = src; + c = (unsigned char)c; + for (; ((uintptr_t)s & ALIGN) && n && *s != c; s++, n--); + if (n && *s != c) { + const size_t *w; + size_t k = ONES * c; + for (w = (const void *)s; n>=SS && !HASZERO(*w^k); w++, n-=SS); + for (s = (const void *)w; n && *s != c; s++, n--); + } + return n ? (void *)s : 0; +} diff --git a/system/lib/libc/musl/src/string/rindex.c b/system/lib/libc/musl/src/string/rindex.c new file mode 100644 index 00000000..17df2bf2 --- /dev/null +++ b/system/lib/libc/musl/src/string/rindex.c @@ -0,0 +1,7 @@ +#include <string.h> +#include <strings.h> + +char *rindex(const char *s, int c) +{ + return strrchr(s, c); +} diff --git a/system/lib/libc/musl/src/string/stpcpy.c b/system/lib/libc/musl/src/string/stpcpy.c new file mode 100644 index 00000000..feb9eb81 --- /dev/null +++ b/system/lib/libc/musl/src/string/stpcpy.c @@ -0,0 +1,29 @@ +#include <string.h> +#include <stdlib.h> +#include <stdint.h> +#include <limits.h> +#include "libc.h" + +#define ALIGN (sizeof(size_t)) +#define ONES ((size_t)-1/UCHAR_MAX) +#define HIGHS (ONES * (UCHAR_MAX/2+1)) +#define HASZERO(x) ((x)-ONES & ~(x) & HIGHS) + +char *__stpcpy(char *restrict d, const char *restrict s) +{ + size_t *wd; + const size_t *ws; + + if ((uintptr_t)s % ALIGN == (uintptr_t)d % ALIGN) { + for (; (uintptr_t)s % ALIGN; s++, d++) + if (!(*d=*s)) return d; + wd=(void *)d; ws=(const void *)s; + for (; !HASZERO(*ws); *wd++ = *ws++); + d=(void *)wd; s=(const void *)ws; + } + for (; (*d=*s); s++, d++); + + return d; +} + +weak_alias(__stpcpy, stpcpy); diff --git a/system/lib/libc/musl/src/string/strchr.c b/system/lib/libc/musl/src/string/strchr.c new file mode 100644 index 00000000..bfae8f9f --- /dev/null +++ b/system/lib/libc/musl/src/string/strchr.c @@ -0,0 +1,9 @@ +#include <string.h> + +char *__strchrnul(const char *, int); + +char *strchr(const char *s, int c) +{ + char *r = __strchrnul(s, c); + return *(unsigned char *)r == (unsigned char)c ? r : 0; +} diff --git a/system/lib/libc/musl/src/string/strcspn.c b/system/lib/libc/musl/src/string/strcspn.c new file mode 100644 index 00000000..cfdba114 --- /dev/null +++ b/system/lib/libc/musl/src/string/strcspn.c @@ -0,0 +1,19 @@ +#include <string.h> + +#define BITOP(a,b,op) \ + ((a)[(size_t)(b)/(8*sizeof *(a))] op (size_t)1<<((size_t)(b)%(8*sizeof *(a)))) + +char *__strchrnul(const char *, int); + +size_t strcspn(const char *s, const char *c) +{ + const char *a = s; + size_t byteset[32/sizeof(size_t)]; + + if (!c[0] || !c[1]) return __strchrnul(s, *c)-a; + + memset(byteset, 0, sizeof byteset); + for (; *c && BITOP(byteset, *(unsigned char *)c, |=); c++); + for (; *s && !BITOP(byteset, *(unsigned char *)s, &); s++); + return s-a; +} diff --git a/system/lib/libc/musl/src/string/strdup.c b/system/lib/libc/musl/src/string/strdup.c new file mode 100644 index 00000000..dd5f80c1 --- /dev/null +++ b/system/lib/libc/musl/src/string/strdup.c @@ -0,0 +1,13 @@ +#include <stdlib.h> +#include <string.h> +#include "libc.h" + +char *__strdup(const char *s) +{ + size_t l = strlen(s); + char *d = malloc(l+1); + if (!d) return NULL; + return memcpy(d, s, l+1); +} + +weak_alias(__strdup, strdup); diff --git a/system/lib/libc/musl/src/string/strncat.c b/system/lib/libc/musl/src/string/strncat.c new file mode 100644 index 00000000..01ca2a23 --- /dev/null +++ b/system/lib/libc/musl/src/string/strncat.c @@ -0,0 +1,10 @@ +#include <string.h> + +char *strncat(char *restrict d, const char *restrict s, size_t n) +{ + char *a = d; + d += strlen(d); + while (n && *s) n--, *d++ = *s++; + *d++ = 0; + return a; +} diff --git a/system/lib/libc/musl/src/string/strndup.c b/system/lib/libc/musl/src/string/strndup.c new file mode 100644 index 00000000..617d27ba --- /dev/null +++ b/system/lib/libc/musl/src/string/strndup.c @@ -0,0 +1,12 @@ +#include <stdlib.h> +#include <string.h> + +char *strndup(const char *s, size_t n) +{ + size_t l = strnlen(s, n); + char *d = malloc(l+1); + if (!d) return NULL; + memcpy(d, s, l); + d[l] = 0; + return d; +} diff --git a/system/lib/libc/musl/src/string/strnlen.c b/system/lib/libc/musl/src/string/strnlen.c new file mode 100644 index 00000000..6442eb79 --- /dev/null +++ b/system/lib/libc/musl/src/string/strnlen.c @@ -0,0 +1,7 @@ +#include <string.h> + +size_t strnlen(const char *s, size_t n) +{ + const char *p = memchr(s, 0, n); + return p ? p-s : n; +} diff --git a/system/lib/libc/musl/src/string/strpbrk.c b/system/lib/libc/musl/src/string/strpbrk.c new file mode 100644 index 00000000..55947c64 --- /dev/null +++ b/system/lib/libc/musl/src/string/strpbrk.c @@ -0,0 +1,7 @@ +#include <string.h> + +char *strpbrk(const char *s, const char *b) +{ + s += strcspn(s, b); + return *s ? (char *)s : 0; +} diff --git a/system/lib/libc/musl/src/string/strrchr.c b/system/lib/libc/musl/src/string/strrchr.c new file mode 100644 index 00000000..635fb3c1 --- /dev/null +++ b/system/lib/libc/musl/src/string/strrchr.c @@ -0,0 +1,8 @@ +#include <string.h> + +void *__memrchr(const void *, int, size_t); + +char *strrchr(const char *s, int c) +{ + return __memrchr(s, c, strlen(s) + 1); +} diff --git a/system/lib/libc/musl/src/string/strspn.c b/system/lib/libc/musl/src/string/strspn.c new file mode 100644 index 00000000..9543dad0 --- /dev/null +++ b/system/lib/libc/musl/src/string/strspn.c @@ -0,0 +1,20 @@ +#include <string.h> + +#define BITOP(a,b,op) \ + ((a)[(size_t)(b)/(8*sizeof *(a))] op (size_t)1<<((size_t)(b)%(8*sizeof *(a)))) + +size_t strspn(const char *s, const char *c) +{ + const char *a = s; + size_t byteset[32/sizeof(size_t)] = { 0 }; + + if (!c[0]) return 0; + if (!c[1]) { + for (; *s == *c; s++); + return s-a; + } + + for (; *c && BITOP(byteset, *(unsigned char *)c, |=); c++); + for (; *s && BITOP(byteset, *(unsigned char *)s, &); s++); + return s-a; +} diff --git a/system/lib/libc/musl/src/string/strstr.c b/system/lib/libc/musl/src/string/strstr.c new file mode 100644 index 00000000..06491748 --- /dev/null +++ b/system/lib/libc/musl/src/string/strstr.c @@ -0,0 +1,156 @@ +#include <string.h> +#include <stdlib.h> +#include <stdint.h> + +static char *twobyte_strstr(const unsigned char *h, const unsigned char *n) +{ + uint16_t nw = n[0]<<8 | n[1], hw = h[0]<<8 | h[1]; + for (h++; *h && hw != nw; hw = hw<<8 | *++h); + return *h ? (char *)h-1 : 0; +} + +static char *threebyte_strstr(const unsigned char *h, const unsigned char *n) +{ + uint32_t nw = n[0]<<24 | n[1]<<16 | n[2]<<8; + uint32_t hw = h[0]<<24 | h[1]<<16 | h[2]<<8; + for (h+=2; *h && hw != nw; hw = (hw|*++h)<<8); + return *h ? (char *)h-2 : 0; +} + +static char *fourbyte_strstr(const unsigned char *h, const unsigned char *n) +{ + uint32_t nw = n[0]<<24 | n[1]<<16 | n[2]<<8 | n[3]; + uint32_t hw = h[0]<<24 | h[1]<<16 | h[2]<<8 | h[3]; + for (h+=3; *h && hw != nw; hw = hw<<8 | *++h); + return *h ? (char *)h-3 : 0; +} + +#define MAX(a,b) ((a)>(b)?(a):(b)) +#define MIN(a,b) ((a)<(b)?(a):(b)) + +#define BITOP(a,b,op) \ + ((a)[(size_t)(b)/(8*sizeof *(a))] op (size_t)1<<((size_t)(b)%(8*sizeof *(a)))) + +static char *twoway_strstr(const unsigned char *h, const unsigned char *n) +{ + const unsigned char *z; + size_t l, ip, jp, k, p, ms, p0, mem, mem0; + size_t byteset[32 / sizeof(size_t)] = { 0 }; + size_t shift[256]; + + /* Computing length of needle and fill shift table */ + for (l=0; n[l] && h[l]; l++) + BITOP(byteset, n[l], |=), shift[n[l]] = l+1; + if (n[l]) return 0; /* hit the end of h */ + + /* Compute maximal suffix */ + ip = -1; jp = 0; k = p = 1; + while (jp+k<l) { + if (n[ip+k] == n[jp+k]) { + if (k == p) { + jp += p; + k = 1; + } else k++; + } else if (n[ip+k] > n[jp+k]) { + jp += k; + k = 1; + p = jp - ip; + } else { + ip = jp++; + k = p = 1; + } + } + ms = ip; + p0 = p; + + /* And with the opposite comparison */ + ip = -1; jp = 0; k = p = 1; + while (jp+k<l) { + if (n[ip+k] == n[jp+k]) { + if (k == p) { + jp += p; + k = 1; + } else k++; + } else if (n[ip+k] < n[jp+k]) { + jp += k; + k = 1; + p = jp - ip; + } else { + ip = jp++; + k = p = 1; + } + } + if (ip+1 > ms+1) ms = ip; + else p = p0; + + /* Periodic needle? */ + if (memcmp(n, n+p, ms+1)) { + mem0 = 0; + p = MAX(ms, l-ms-1) + 1; + } else mem0 = l-p; + mem = 0; + + /* Initialize incremental end-of-haystack pointer */ + z = h; + + /* Search loop */ + for (;;) { + /* Update incremental end-of-haystack pointer */ + if (z-h < l) { + /* Fast estimate for MIN(l,63) */ + size_t grow = l | 63; + const unsigned char *z2 = memchr(z, 0, grow); + if (z2) { + z = z2; + if (z-h < l) return 0; + } else z += grow; + } + + /* Check last byte first; advance by shift on mismatch */ + if (BITOP(byteset, h[l-1], &)) { + k = l-shift[h[l-1]]; + //printf("adv by %zu (on %c) at [%s] (%zu;l=%zu)\n", k, h[l-1], h, shift[h[l-1]], l); + if (k) { + if (mem0 && mem && k < p) k = l-p; + h += k; + mem = 0; + continue; + } + } else { + h += l; + mem = 0; + continue; + } + + /* Compare right half */ + for (k=MAX(ms+1,mem); n[k] && n[k] == h[k]; k++); + if (n[k]) { + h += k-ms; + mem = 0; + continue; + } + /* Compare left half */ + for (k=ms+1; k>mem && n[k-1] == h[k-1]; k--); + if (k == mem) return (char *)h; + h += p; + mem = mem0; + } +} + +char *strstr(const char *h, const char *n) +{ + /* Return immediately on empty needle */ + if (!n[0]) return (char *)h; + + /* Use faster algorithms for short needles */ + h = strchr(h, *n); + if (!h || !n[1]) return (char *)h; + if (!h[1]) return 0; + if (!n[2]) return twobyte_strstr((void *)h, (void *)n); + if (!h[2]) return 0; + if (!n[3]) return threebyte_strstr((void *)h, (void *)n); + if (!h[3]) return 0; + if (!n[4]) return fourbyte_strstr((void *)h, (void *)n); + + return twoway_strstr((void *)h, (void *)n); +} diff --git a/system/lib/libc/musl/src/string/strtok.c b/system/lib/libc/musl/src/string/strtok.c new file mode 100644 index 00000000..35087902 --- /dev/null +++ b/system/lib/libc/musl/src/string/strtok.c @@ -0,0 +1,13 @@ +#include <string.h> + +char *strtok(char *restrict s, const char *restrict sep) +{ + static char *p; + if (!s && !(s = p)) return NULL; + s += strspn(s, sep); + if (!*s) return p = 0; + p = s + strcspn(s, sep); + if (*p) *p++ = 0; + else p = 0; + return s; +} diff --git a/system/lib/libc/musl/src/string/strtok_r.c b/system/lib/libc/musl/src/string/strtok_r.c new file mode 100644 index 00000000..862d4fe4 --- /dev/null +++ b/system/lib/libc/musl/src/string/strtok_r.c @@ -0,0 +1,12 @@ +#include <string.h> + +char *strtok_r(char *restrict s, const char *restrict sep, char **restrict p) +{ + if (!s && !(s = *p)) return NULL; + s += strspn(s, sep); + if (!*s) return *p = 0; + *p = s + strcspn(s, sep); + if (**p) *(*p)++ = 0; + else *p = 0; + return s; +} diff --git a/system/lib/libcextra.symbols b/system/lib/libcextra.symbols index 54176b1d..64ba670a 100644 --- a/system/lib/libcextra.symbols +++ b/system/lib/libcextra.symbols @@ -22,6 +22,11 @@ T __wcscoll_l T __wcsxfrm_l W __wctype_l + T atoll + T bcmp + T bcopy + T bzero + T bsearch T btowc T ecvt T err @@ -40,6 +45,7 @@ T ilogb T ilogbf T ilogbl + T index T iswalnum T iswalnum_l T iswalpha @@ -87,6 +93,7 @@ T mbstowcs T mbtowc T memccpy + T memchr T memmem T mempcpy W memrchr @@ -96,21 +103,36 @@ C optopt W optreset W putwc_unlocked + T qsort T regcomp T regerror T regexec T regfree + T rindex T scalbnf D signgam + T stpcpy T strcasecmp_l T strcasestr W strchrnul + T strchr + T strcspn + T strdup T strfmon T strfmon_l T strlcat T strlcpy T strncasecmp_l + T strncat + T strndup + T strnlen + T strpbrk + T strrchr T strsep + T strspn + T strstr + T strtok + T strtok_r T strverscmp T strxfrm W strxfrm_l |