diff options
Diffstat (limited to 'src/string')
60 files changed, 1054 insertions, 0 deletions
diff --git a/src/string/bcmp.c b/src/string/bcmp.c new file mode 100644 index 00000000..5d6a388b --- /dev/null +++ b/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/src/string/bcopy.c b/src/string/bcopy.c new file mode 100644 index 00000000..e76272fc --- /dev/null +++ b/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/src/string/bzero.c b/src/string/bzero.c new file mode 100644 index 00000000..0f98b4a5 --- /dev/null +++ b/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/src/string/index.c b/src/string/index.c new file mode 100644 index 00000000..dd611251 --- /dev/null +++ b/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/src/string/memchr.c b/src/string/memchr.c new file mode 100644 index 00000000..a0472f78 --- /dev/null +++ b/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/src/string/memcmp.c b/src/string/memcmp.c new file mode 100644 index 00000000..bdbce9f0 --- /dev/null +++ b/src/string/memcmp.c @@ -0,0 +1,8 @@ +#include <string.h> + +int memcmp(const void *vl, const void *vr, size_t n) +{ + const unsigned char *l=vl, *r=vr; + for (; n && *l == *r; n--, l++, r++); + return n ? *l-*r : 0; +} diff --git a/src/string/memcpy.c b/src/string/memcpy.c new file mode 100644 index 00000000..02cb4694 --- /dev/null +++ b/src/string/memcpy.c @@ -0,0 +1,29 @@ +#include <string.h> +#include <stdlib.h> +#include <stdint.h> + +#define SS (sizeof(size_t)) +#define ALIGN (sizeof(size_t)-1) +#define ONES ((size_t)-1/UCHAR_MAX) + +void *memcpy(void *dest, const void *src, size_t n) +{ + unsigned char *d = dest; + const unsigned char *s = src; + + if (((uintptr_t)d & ALIGN) != ((uintptr_t)s & ALIGN)) + goto misaligned; + + for (; ((uintptr_t)d & ALIGN) && n; n--) *d++ = *s++; + if (n) { + size_t *wd = (void *)d; + const size_t *ws = (const void *)s; + + for (; n>=SS; n-=SS) *wd++ = *ws++; + d = (void *)wd; + s = (const void *)ws; +misaligned: + for (; n; n--) *d++ = *s++; + } + return dest; +} diff --git a/src/string/memmove.c b/src/string/memmove.c new file mode 100644 index 00000000..22bb4b35 --- /dev/null +++ b/src/string/memmove.c @@ -0,0 +1,14 @@ +#include <string.h> + +void *memmove(void *dest, const void *src, size_t n) +{ + char *d = dest; + const char *s = src; + if (d==s) return d; + if ((size_t)(d-s) < n) { + while (n--) d[n] = s[n]; + return dest; + } + /* Assumes memcpy is overlap-safe when dest < src */ + return memcpy(d, s, n); +} diff --git a/src/string/mempcpy.c b/src/string/mempcpy.c new file mode 100644 index 00000000..e54251cd --- /dev/null +++ b/src/string/mempcpy.c @@ -0,0 +1,7 @@ +#include <string.h> + +void *mempcpy(void *dest, void *src, size_t n) +{ + memcpy(dest, src, n); + return (char *)dest + n; +} diff --git a/src/string/memset.c b/src/string/memset.c new file mode 100644 index 00000000..20e47c45 --- /dev/null +++ b/src/string/memset.c @@ -0,0 +1,21 @@ +#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) + +void *memset(void *dest, int c, size_t n) +{ + unsigned char *s = dest; + c = (unsigned char)c; + for (; ((uintptr_t)s & ALIGN) && n; n--) *s++ = c; + if (n) { + size_t *w, k = ONES * c; + for (w = (void *)s; n>=SS; n-=SS, w++) *w = k; + for (s = (void *)w; n; n--, s++) *s = c; + } + return dest; +} diff --git a/src/string/rindex.c b/src/string/rindex.c new file mode 100644 index 00000000..17df2bf2 --- /dev/null +++ b/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/src/string/stpcpy.c b/src/string/stpcpy.c new file mode 100644 index 00000000..10ca4933 --- /dev/null +++ b/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)-1) +#define ONES ((size_t)-1/UCHAR_MAX) +#define HIGHS (ONES * (UCHAR_MAX/2+1)) +#define HASZERO(x) ((x)-ONES & ~(x) & HIGHS) + +char *__stpcpy(char *d, const char *s) +{ + size_t *wd; + const size_t *ws; + + if (((uintptr_t)s & ALIGN) == ((uintptr_t)d & ALIGN)) { + for (; (*d=*s) && ((uintptr_t)s & ALIGN); s++, d++); + if (!*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/src/string/stpncpy.c b/src/string/stpncpy.c new file mode 100644 index 00000000..a877f5fe --- /dev/null +++ b/src/string/stpncpy.c @@ -0,0 +1,32 @@ +#include <string.h> +#include <stdlib.h> +#include <stdint.h> +#include <limits.h> +#include "libc.h" + +#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) + +char *__stpncpy(char *d, const char *s, size_t n) +{ + size_t *wd; + const size_t *ws; + + if (((uintptr_t)s & ALIGN) != ((uintptr_t)d & ALIGN)) { + for (; ((uintptr_t)s & ALIGN) && n && (*d=*s); n--, s++, d++); + if (!n || !*s) goto tail; + wd=(void *)d; ws=(const void *)s; + for (; n>=sizeof(size_t) && !HASZERO(*ws); + n-=sizeof(size_t), ws++, *wd++) *wd = *ws; + d=(void *)wd; s=(const void *)ws; + } + for (; n && (*d=*s); n--, s++, d++); +tail: + memset(d, 0, n); + return d; +} + +weak_alias(__stpncpy, stpncpy); + diff --git a/src/string/strcasecmp.c b/src/string/strcasecmp.c new file mode 100644 index 00000000..dd879052 --- /dev/null +++ b/src/string/strcasecmp.c @@ -0,0 +1,9 @@ +#include <strings.h> +#include <ctype.h> + +int strcasecmp(const char *_l, const char *_r) +{ + const unsigned char *l=_l, *r=_r; + for (; *l && *r && (*l == *r || tolower(*l) == tolower(*r)); l++, r++); + return tolower(*l) - tolower(*r); +} diff --git a/src/string/strcasestr.c b/src/string/strcasestr.c new file mode 100644 index 00000000..f1cb0e84 --- /dev/null +++ b/src/string/strcasestr.c @@ -0,0 +1,7 @@ +#include <string.h> + +char *strcasestr(const char *h, const char *n) +{ + //FIXME! + return strstr(h, n); +} diff --git a/src/string/strcat.c b/src/string/strcat.c new file mode 100644 index 00000000..29fdb611 --- /dev/null +++ b/src/string/strcat.c @@ -0,0 +1,7 @@ +#include <string.h> + +char *strcat(char *dest, const char *src) +{ + strcpy(dest + strlen(dest), src); + return dest; +} diff --git a/src/string/strchr.c b/src/string/strchr.c new file mode 100644 index 00000000..e606f4fe --- /dev/null +++ b/src/string/strchr.c @@ -0,0 +1,23 @@ +#include <string.h> +#include <stdlib.h> +#include <stdint.h> +#include <limits.h> + +#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) + +char *strchr(const char *s, int c) +{ + c = (char)c; + if (!c) return (char *)s + strlen(s); + for (; ((uintptr_t)s & ALIGN) && *s && *s != c; s++); + if (*s && *s != c) { + const size_t *w; + size_t k = ONES * c; + for (w = (const void *)s; !HASZERO(*w) && !HASZERO(*w^k); w++); + for (s = (const void *)w; *s && *s != c; s++); + } + return *s ? (char *)s : 0; +} diff --git a/src/string/strchrnul.c b/src/string/strchrnul.c new file mode 100644 index 00000000..5e0c1a1a --- /dev/null +++ b/src/string/strchrnul.c @@ -0,0 +1,7 @@ +#include <string.h> + +char *strchrnul(const char *s, int c) +{ + char *p = strchr(s, c); + return p ? p : (char *)s + strlen(s); +} diff --git a/src/string/strcmp.c b/src/string/strcmp.c new file mode 100644 index 00000000..91eb7404 --- /dev/null +++ b/src/string/strcmp.c @@ -0,0 +1,7 @@ +#include <string.h> + +int strcmp(const char *l, const char *r) +{ + for (; *l==*r && *l && *r; l++, r++); + return *(unsigned char *)l - *(unsigned char *)r; +} diff --git a/src/string/strcpy.c b/src/string/strcpy.c new file mode 100644 index 00000000..7675e9ce --- /dev/null +++ b/src/string/strcpy.c @@ -0,0 +1,16 @@ +#include <string.h> + +char *__stpcpy(char *, const char *); + +char *strcpy(char *dest, const char *src) +{ +#if 1 + __stpcpy(dest, src); + return dest; +#else + const unsigned char *s = src; + unsigned char *d = dest; + while ((*d++ = *s++)); + return dest; +#endif +} diff --git a/src/string/strcspn.c b/src/string/strcspn.c new file mode 100644 index 00000000..439b7be4 --- /dev/null +++ b/src/string/strcspn.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 strcspn(const char *_s, const char *_c) +{ + const unsigned char *s = _s; + const unsigned char *c = _c; + const unsigned char *a = s; + size_t byteset[32/sizeof(size_t)]; + + if (!c[0]) return strlen(s); + if (!c[1]) return (s=strchr(s, *c)) ? s-a : strlen(a); + + memset(byteset, 0, sizeof byteset); + for (; *c && BITOP(byteset, *c, |=); c++); + for (; *s && !BITOP(byteset, *s, &); s++); + return s-a; +} diff --git a/src/string/strdup.c b/src/string/strdup.c new file mode 100644 index 00000000..dd5f80c1 --- /dev/null +++ b/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/src/string/strerror_r.c b/src/string/strerror_r.c new file mode 100644 index 00000000..6fdd4ce2 --- /dev/null +++ b/src/string/strerror_r.c @@ -0,0 +1,11 @@ +#include <string.h> +#include <errno.h> + +int strerror_r(int err, char *buf, size_t buflen) +{ + char *msg = strerror(err); + if (strlen(msg) >= buflen) + return ERANGE; + strcpy(buf, msg); + return 0; +} diff --git a/src/string/strlcat.c b/src/string/strlcat.c new file mode 100644 index 00000000..a6b94c4c --- /dev/null +++ b/src/string/strlcat.c @@ -0,0 +1,8 @@ +#include <string.h> + +size_t strlcat(char *d, const char *s, size_t n) +{ + size_t l = strnlen(d, n); + if (l == n) return l + strlen(s); + return l + strlcpy(d+l, s, n-l); +} diff --git a/src/string/strlcpy.c b/src/string/strlcpy.c new file mode 100644 index 00000000..bbebf1db --- /dev/null +++ b/src/string/strlcpy.c @@ -0,0 +1,32 @@ +#include <string.h> +#include <stdlib.h> +#include <stdint.h> +#include <limits.h> +#include "libc.h" + +#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) + +size_t strlcpy(char *d, const char *s, size_t n) +{ + char *d0 = d; + size_t *wd; + const size_t *ws; + + if (!n--) goto finish; + if (((uintptr_t)s & ALIGN) != ((uintptr_t)d & ALIGN)) { + for (; ((uintptr_t)s & ALIGN) && n && (*d=*s); n--, s++, d++); + if (n && *s) { + wd=(void *)d; ws=(const void *)s; + for (; n>=sizeof(size_t) && !HASZERO(*ws); + n-=sizeof(size_t), ws++, *wd++) *wd = *ws; + d=(void *)wd; s=(const void *)ws; + } + } + for (; n && (*d=*s); n--, s++, d++); + *d = 0; +finish: + return d-d0 + strlen(s); +} diff --git a/src/string/strlen.c b/src/string/strlen.c new file mode 100644 index 00000000..936fb5cf --- /dev/null +++ b/src/string/strlen.c @@ -0,0 +1,21 @@ +#include <string.h> +#include <stdlib.h> +#include <stdint.h> +#include <limits.h> + +#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) + +size_t strlen(const char *s) +{ + const char *a = s; + const size_t *w; + for (; ((uintptr_t)s & ALIGN) && *s; s++); + if (*s) { + for (w = (const void *)s; !HASZERO(*w); w++); + for (s = (const void *)w; *s; s++); + } + return s-a; +} diff --git a/src/string/strncasecmp.c b/src/string/strncasecmp.c new file mode 100644 index 00000000..4f9230e1 --- /dev/null +++ b/src/string/strncasecmp.c @@ -0,0 +1,10 @@ +#include <strings.h> +#include <ctype.h> + +int strncasecmp(const char *_l, const char *_r, size_t n) +{ + const unsigned char *l=_l, *r=_r; + if (!n--) return 0; + for (; *l && *r && n && (*l == *r || tolower(*l) == tolower(*r)); l++, r++, n--); + return tolower(*l) - tolower(*r); +} diff --git a/src/string/strncat.c b/src/string/strncat.c new file mode 100644 index 00000000..255b7a72 --- /dev/null +++ b/src/string/strncat.c @@ -0,0 +1,10 @@ +#include <string.h> + +char *strncat(char *d, const char *s, size_t n) +{ + char *a = d; + d += strlen(d); + while (n && (*d++ = *s++)) n--; + *d++ = 0; + return a; +} diff --git a/src/string/strncmp.c b/src/string/strncmp.c new file mode 100644 index 00000000..52ba0323 --- /dev/null +++ b/src/string/strncmp.c @@ -0,0 +1,9 @@ +#include <string.h> + +int strncmp(const char *_l, const char *_r, size_t n) +{ + const unsigned char *l=_l, *r=_r; + if (!n--) return 0; + for (; *l && *r && n && *l == *r ; l++, r++, n--); + return *l - *r; +} diff --git a/src/string/strncpy.c b/src/string/strncpy.c new file mode 100644 index 00000000..c0cd7974 --- /dev/null +++ b/src/string/strncpy.c @@ -0,0 +1,9 @@ +#include <string.h> + +char *__stpncpy(char *, const char *, size_t); + +char *strncpy(char *d, const char *s, size_t n) +{ + __stpncpy(d, s, n); + return d; +} diff --git a/src/string/strndup.c b/src/string/strndup.c new file mode 100644 index 00000000..617d27ba --- /dev/null +++ b/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/src/string/strnlen.c b/src/string/strnlen.c new file mode 100644 index 00000000..6442eb79 --- /dev/null +++ b/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/src/string/strpbrk.c b/src/string/strpbrk.c new file mode 100644 index 00000000..55947c64 --- /dev/null +++ b/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/src/string/strrchr.c b/src/string/strrchr.c new file mode 100644 index 00000000..31c8e0b8 --- /dev/null +++ b/src/string/strrchr.c @@ -0,0 +1,9 @@ +#include <string.h> + +char *strrchr(const char *s, int c) +{ + const char *p; + c = (char)c; + for (p=s+strlen(s); p>=s && *p!=c; p--); + return p>=s ? (char *)p : 0; +} diff --git a/src/string/strsep.c b/src/string/strsep.c new file mode 100644 index 00000000..1bfe1db1 --- /dev/null +++ b/src/string/strsep.c @@ -0,0 +1,12 @@ +#include <string.h> + +char *strsep(char **str, const char *sep) +{ + char *s = *str, *end; + if (!s) return NULL; + end = s + strcspn(s, sep); + if (*end) *end++ = 0; + else end = 0; + *str = end; + return s; +} diff --git a/src/string/strsignal.c b/src/string/strsignal.c new file mode 100644 index 00000000..72fba8d1 --- /dev/null +++ b/src/string/strsignal.c @@ -0,0 +1,98 @@ +#include <signal.h> + +#if (SIGHUP == 1) && (SIGINT == 2) && (SIGQUIT == 3) && (SIGILL == 4) \ + && (SIGTRAP == 5) && (SIGABRT == 6) && (SIGBUS == 7) && (SIGFPE == 8) \ + && (SIGKILL == 9) && (SIGUSR1 == 10) && (SIGSEGV == 11) && (SIGUSR2 == 12) \ + && (SIGPIPE == 13) && (SIGALRM == 14) && (SIGTERM == 15) && (SIGSTKFLT == 16) \ + && (SIGCHLD == 17) && (SIGCONT == 18) && (SIGSTOP == 19) && (SIGTSTP == 20) \ + && (SIGTTIN == 21) && (SIGTTOU == 22) && (SIGURG == 23) && (SIGXCPU == 24) \ + && (SIGXFSZ == 25) && (SIGVTALRM == 26) && (SIGPROF == 27) && (SIGWINCH == 28) \ + && (SIGPOLL == 29) && (SIGPWR == 30) && (SIGSYS == 31) + +#define sigmap(x) x + +#else + +static const char map[] = { + [SIGHUP] = 1, + [SIGINT] = 2, + [SIGQUIT] = 3, + [SIGILL] = 4, + [SIGTRAP] = 5, + [SIGABRT] = 6, + [SIGBUS] = 7, + [SIGFPE] = 8, + [SIGKILL] = 9, + [SIGUSR1] = 10, + [SIGSEGV] = 11, + [SIGUSR2] = 12, + [SIGPIPE] = 13, + [SIGALRM] = 14, + [SIGTERM] = 15, + [SIGSTKFLT] = 16, + [SIGCHLD] = 17, + [SIGCONT] = 18, + [SIGSTOP] = 19, + [SIGTSTP] = 20, + [SIGTTIN] = 21, + [SIGTTOU] = 22, + [SIGURG] = 23, + [SIGXCPU] = 24, + [SIGXFSZ] = 25, + [SIGVTALRM] = 26, + [SIGPROF] = 27, + [SIGWINCH] = 28, + [SIGPOLL] = 29, + [SIGPWR] = 30, + [SIGSYS] = 31 +}; + +#define sigmap(x) ((unsigned)(x) > sizeof map ? 0 : map[(unsigned)(x)]) + +#endif + +static const char strings[] = + "Unknown signal\0" + "Hangup\0" + "Interrupt\0" + "Quit\0" + "Illegal instruction\0" + "Trace/breakpoint trap\0" + "Aborted\0" + "Bus error\0" + "Floating point exception\0" + "Killed\0" + "User defined signal 1\0" + "Segmentation fault\0" + "User defined signal 2\0" + "Broken pipe\0" + "Alarm clock\0" + "Terminated\0" + "Stack fault\0" + "Child exited\0" + "Continued\0" + "Stopped (signal)\0" + "Stopped\0" + "Stopped (tty input)\0" + "Stopped (tty output)\0" + "Urgent I/O condition\0" + "CPU time limit exceeded\0" + "File size limit exceeded\0" + "Virtual timer expired\0" + "Profiling timer expired\0" + "Window changed\0" + "I/O possible\0" + "Power failure\0" + "Bad system call"; + +char *strsignal(int signum) +{ + char *s = (char *)strings; + + signum = sigmap(signum); + if ((unsigned)signum - 1 > 31) signum = 0; + + for (; signum--; s++) for (; *s; s++); + + return s; +} diff --git a/src/string/strspn.c b/src/string/strspn.c new file mode 100644 index 00000000..59b063e5 --- /dev/null +++ b/src/string/strspn.c @@ -0,0 +1,22 @@ +#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 unsigned char *s = _s; + const unsigned char *c = _c; + const unsigned 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, *c, |=); c++); + for (; *s && BITOP(byteset, *s, &); s++); + return s-a; +} diff --git a/src/string/strstr.c b/src/string/strstr.c new file mode 100644 index 00000000..4d536a73 --- /dev/null +++ b/src/string/strstr.c @@ -0,0 +1,166 @@ +#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; +} + +#if 0 +static char *naive_strstr(const char *h, const char *n) +{ + size_t i; + for (i=0; n[i] && h[i]; i++) + for ( ; n[i] != h[i]; h++, i=0); + return n[i] ? 0 : (char *)h; +} +#endif + +#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 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(h, n); + if (!h[2]) return 0; + if (!n[3]) return threebyte_strstr(h, n); + if (!h[3]) return 0; + if (!n[4]) return fourbyte_strstr(h, n); + + return twoway_strstr(h, n); +} diff --git a/src/string/strtok.c b/src/string/strtok.c new file mode 100644 index 00000000..1ba221cb --- /dev/null +++ b/src/string/strtok.c @@ -0,0 +1,13 @@ +#include <string.h> + +char *strtok(char *s, const char *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/src/string/strtok_r.c b/src/string/strtok_r.c new file mode 100644 index 00000000..c763897a --- /dev/null +++ b/src/string/strtok_r.c @@ -0,0 +1,12 @@ +#include <string.h> + +char *strtok_r(char *s, const char *sep, 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/src/string/swab.c b/src/string/swab.c new file mode 100644 index 00000000..b2132884 --- /dev/null +++ b/src/string/swab.c @@ -0,0 +1,13 @@ +#include <unistd.h> + +void swab(const void *_src, void *_dest, ssize_t n) +{ + const char *src = _src; + char *dest = _dest; + for (; n>0; n-=2) { + dest[0] = src[1]; + dest[1] = src[0]; + dest += 2; + src += 2; + } +} diff --git a/src/string/wcscat.c b/src/string/wcscat.c new file mode 100644 index 00000000..946f16e2 --- /dev/null +++ b/src/string/wcscat.c @@ -0,0 +1,7 @@ +#include <wchar.h> + +wchar_t *wcscat(wchar_t *dest, const wchar_t *src) +{ + wcscpy(dest + wcslen(dest), src); + return dest; +} diff --git a/src/string/wcschr.c b/src/string/wcschr.c new file mode 100644 index 00000000..8dfc2f31 --- /dev/null +++ b/src/string/wcschr.c @@ -0,0 +1,8 @@ +#include <wchar.h> + +wchar_t *wcschr(const wchar_t *s, wchar_t c) +{ + if (!c) return (wchar_t *)s + wcslen(s); + for (; *s && *s != c; s++); + return *s ? (wchar_t *)s : 0; +} diff --git a/src/string/wcscmp.c b/src/string/wcscmp.c new file mode 100644 index 00000000..26eeee70 --- /dev/null +++ b/src/string/wcscmp.c @@ -0,0 +1,7 @@ +#include <wchar.h> + +int wcscmp(const wchar_t *l, const wchar_t *r) +{ + for (; *l==*r && *l && *r; l++, r++); + return *l - *r; +} diff --git a/src/string/wcscpy.c b/src/string/wcscpy.c new file mode 100644 index 00000000..e0ac194f --- /dev/null +++ b/src/string/wcscpy.c @@ -0,0 +1,8 @@ +#include <wchar.h> + +wchar_t *wcscpy(wchar_t *d, const wchar_t *s) +{ + wchar_t *a = d; + while ((*d++ = *s++)); + return a; +} diff --git a/src/string/wcscspn.c b/src/string/wcscspn.c new file mode 100644 index 00000000..c4e52722 --- /dev/null +++ b/src/string/wcscspn.c @@ -0,0 +1,10 @@ +#include <wchar.h> + +size_t wcscspn(const wchar_t *s, const wchar_t *c) +{ + const wchar_t *a; + if (!c[0]) return wcslen(s); + if (!c[1]) return (s=wcschr(a=s, *c)) ? s-a : wcslen(a); + for (a=s; *s && !wcschr(c, *s); s++); + return s-a; +} diff --git a/src/string/wcslen.c b/src/string/wcslen.c new file mode 100644 index 00000000..1b7b6655 --- /dev/null +++ b/src/string/wcslen.c @@ -0,0 +1,8 @@ +#include <wchar.h> + +size_t wcslen(const wchar_t *s) +{ + const wchar_t *a; + for (a=s; *s; s++); + return s-a; +} diff --git a/src/string/wcsncat.c b/src/string/wcsncat.c new file mode 100644 index 00000000..b07abe45 --- /dev/null +++ b/src/string/wcsncat.c @@ -0,0 +1,10 @@ +#include <wchar.h> + +wchar_t *wcsncat(wchar_t *d, const wchar_t *s, size_t n) +{ + wchar_t *a = d; + d += wcslen(d); + while (n && (*d++ = *s++)) n--; + *d++ = 0; + return a; +} diff --git a/src/string/wcsncmp.c b/src/string/wcsncmp.c new file mode 100644 index 00000000..1b159f41 --- /dev/null +++ b/src/string/wcsncmp.c @@ -0,0 +1,7 @@ +#include <wchar.h> + +int wcsncmp(const wchar_t *l, const wchar_t *r, size_t n) +{ + for (; n && *l==*r && *l && *r; l++, r++); + return n ? *l - *r : 0; +} diff --git a/src/string/wcsncpy.c b/src/string/wcsncpy.c new file mode 100644 index 00000000..0164208d --- /dev/null +++ b/src/string/wcsncpy.c @@ -0,0 +1,9 @@ +#include <wchar.h> + +wchar_t *wcsncpy(wchar_t *d, const wchar_t *s, size_t n) +{ + wchar_t *a = d; + while (n && (*d++ = *s++)) n--; + wmemset(d, 0, n); + return a; +} diff --git a/src/string/wcspbrk.c b/src/string/wcspbrk.c new file mode 100644 index 00000000..0c72c197 --- /dev/null +++ b/src/string/wcspbrk.c @@ -0,0 +1,7 @@ +#include <wchar.h> + +wchar_t *wcspbrk(const wchar_t *s, const wchar_t *b) +{ + s += wcscspn(s, b); + return *s ? (wchar_t *)s : NULL; +} diff --git a/src/string/wcsrchr.c b/src/string/wcsrchr.c new file mode 100644 index 00000000..7503475a --- /dev/null +++ b/src/string/wcsrchr.c @@ -0,0 +1,8 @@ +#include <wchar.h> + +wchar_t *wcsrchr(const wchar_t *s, wint_t c) +{ + const wchar_t *p; + for (p=s+wcslen(s); p>=s && *p!=c; p--); + return p>=s ? (wchar_t *)p : 0; +} diff --git a/src/string/wcsspn.c b/src/string/wcsspn.c new file mode 100644 index 00000000..4320d8f6 --- /dev/null +++ b/src/string/wcsspn.c @@ -0,0 +1,8 @@ +#include <wchar.h> + +size_t wcsspn(const wchar_t *s, const wchar_t *c) +{ + const wchar_t *a; + for (a=s; *s && wcschr(c, *s); s++); + return s-a; +} diff --git a/src/string/wcsstr.c b/src/string/wcsstr.c new file mode 100644 index 00000000..966174f8 --- /dev/null +++ b/src/string/wcsstr.c @@ -0,0 +1,117 @@ +#include <wchar.h> +#include <string.h> +#include <stdlib.h> +#include <stdint.h> + +static wchar_t *naive_wcsstr(const wchar_t *h, const wchar_t *n) +{ + size_t i; + for (i=0; n[i] && h[i]; i++) + for ( ; n[i] != h[i]; h++, i=0); + return n[i] ? 0 : (wchar_t *)h; +} + +#define MAX(a,b) ((a)>(b)?(a):(b)) +#define MIN(a,b) ((a)<(b)?(a):(b)) + +static wchar_t *twoway_wcsstr(const wchar_t *h, const wchar_t *n) +{ + const wchar_t *z; + size_t l, ip, jp, k, p, ms, p0, mem, mem0; + + /* Computing length of needle */ + for (l=0; n[l] && h[l]; l++); + 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 (wmemcmp(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 wchar_t *z2 = wmemchr(z, 0, grow); + if (z2) { + z = z2; + if (z-h < l) return 0; + } else z += grow; + } + + /* 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 (wchar_t *)h; + h += p; + mem = mem0; + } +} + +wchar_t *wcsstr(const wchar_t *h, const wchar_t *n) +{ + /* Return immediately on empty needle or haystack */ + if (!n[0]) return (wchar_t *)h; + if (!h[0]) return 0; + + /* Use faster algorithms for short needles */ + h = wcschr(h, *n); + if (!h || !n[1]) return (wchar_t *)h; + if (!h[1]) return 0; + if (!n[2] || !n[3] || !n[4]) return naive_wcsstr(h, n); + + return twoway_wcsstr(h, n); +} diff --git a/src/string/wcswcs.c b/src/string/wcswcs.c new file mode 100644 index 00000000..9cfe4ac4 --- /dev/null +++ b/src/string/wcswcs.c @@ -0,0 +1,6 @@ +#include <wchar.h> + +wchar_t *wcswcs(const wchar_t *haystack, const wchar_t *needle) +{ + return wcsstr(haystack, needle); +} diff --git a/src/string/wmemchr.c b/src/string/wmemchr.c new file mode 100644 index 00000000..a3ee0e61 --- /dev/null +++ b/src/string/wmemchr.c @@ -0,0 +1,8 @@ +#include <string.h> +#include <wchar.h> + +wchar_t *wmemchr(const wchar_t *s, wchar_t c, size_t n) +{ + for (; n && *s != c; s++); + return n ? (wchar_t *)s : 0; +} diff --git a/src/string/wmemcmp.c b/src/string/wmemcmp.c new file mode 100644 index 00000000..6788a383 --- /dev/null +++ b/src/string/wmemcmp.c @@ -0,0 +1,8 @@ +#include <string.h> +#include <wchar.h> + +int wmemcmp(const wchar_t *l, const wchar_t *r, size_t n) +{ + for (; n && *l==*r; n--, l++, r++); + return n ? *l-*r : 0; +} diff --git a/src/string/wmemcpy.c b/src/string/wmemcpy.c new file mode 100644 index 00000000..330e37c7 --- /dev/null +++ b/src/string/wmemcpy.c @@ -0,0 +1,9 @@ +#include <string.h> +#include <wchar.h> + +wchar_t *wmemcpy(wchar_t *d, const wchar_t *s, size_t n) +{ + wchar_t *a = d; + while (n--) *d++ = *s++; + return a; +} diff --git a/src/string/wmemmove.c b/src/string/wmemmove.c new file mode 100644 index 00000000..49608cae --- /dev/null +++ b/src/string/wmemmove.c @@ -0,0 +1,11 @@ +#include <string.h> +#include <wchar.h> + +wchar_t *wmemmove(wchar_t *d, const wchar_t *s, size_t n) +{ + if ((size_t)(d-s) < n) { + while (n--) d[n] = s[n]; + return d; + } + return wmemcpy(d, s, n); +} diff --git a/src/string/wmemset.c b/src/string/wmemset.c new file mode 100644 index 00000000..1a2a8618 --- /dev/null +++ b/src/string/wmemset.c @@ -0,0 +1,9 @@ +#include <string.h> +#include <wchar.h> + +wchar_t *wmemset(wchar_t *d, wchar_t c, size_t n) +{ + wchar_t *ret = d; + while (n--) *d++ = c; + return ret; +} |