From: Nathan McSween <nwmcsween@gmail.com>
To: musl@lists.openwall.com
Cc: Nathan McSween <nwmcsween@gmail.com>
Subject: [RFC PATCH 2/5] string: modify wordwise functions to match new style
Date: Sat, 15 Jul 2017 19:55:38 +0000 [thread overview]
Message-ID: <20170715195541.3136-3-nwmcsween@gmail.com> (raw)
In-Reply-To: <20170715195541.3136-1-nwmcsween@gmail.com>
Text sizes w/ gcc 6.3.0:
Before | After
307 | 248 memccpy.lo
234 | 225 memchr.lo
177 | 183 stpcpy.lo
228 | 310 stpncpy.lo
234 | 269 strchrnul.lo
121 | 131 strlen.lo
1301 | 1366 (TOTALS)
Size increases are due to a any of:
* __may_alias__ use.
* skipping to bytewise when element count is less than sizeof(size_t) * 3.
* early return after alignment loop.
---
src/string/memccpy.c | 51 ++++++++++++++++++++++++++------------------------
src/string/memchr.c | 37 ++++++++++++++++++++----------------
src/string/stpcpy.c | 37 +++++++++++++++++++-----------------
src/string/stpncpy.c | 40 ++++++++++++++++++++-------------------
src/string/strchrnul.c | 33 +++++++++++++++++---------------
src/string/strlen.c | 27 +++++++++++++++-----------
6 files changed, 123 insertions(+), 102 deletions(-)
diff --git a/src/string/memccpy.c b/src/string/memccpy.c
index 7c233d5e..068f6a2d 100644
--- a/src/string/memccpy.c
+++ b/src/string/memccpy.c
@@ -1,31 +1,34 @@
#include <string.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)
+#define aliases __attribute__((__may_alias__))
+#define byte_repeat(x) ((size_t)~0 / 0xff * (x))
+#define word_has_zero(x) (((x) - byte_repeat(0x01)) & ~(x) & byte_repeat(0x80))
-void *memccpy(void *restrict dest, const void *restrict src, int c, size_t n)
+void *memccpy(void *restrict _d, const void *restrict _s, int i, size_t n)
{
- unsigned char *d = dest;
- const unsigned char *s = src;
- size_t *wd, k;
- const size_t *ws;
+ i = (unsigned char)i;
+ unsigned char *d = _d;
+ const unsigned char *s = _s;
+ size_t aliases *wd;
+ const size_t aliases *ws, wi = byte_repeat(i);
- c = (unsigned char)c;
- if (((uintptr_t)s & ALIGN) == ((uintptr_t)d & ALIGN)) {
- for (; ((uintptr_t)s & ALIGN) && n && (*d=*s)!=c; n--, s++, d++);
- if ((uintptr_t)s & ALIGN) goto tail;
- k = ONES * c;
- wd=(void *)d; ws=(const void *)s;
- for (; n>=sizeof(size_t) && !HASZERO(*ws^k);
- n-=sizeof(size_t), ws++, wd++) *wd = *ws;
- d=(void *)wd; s=(const void *)ws;
- }
- for (; n && (*d=*s)!=c; n--, s++, d++);
-tail:
- if (*s==c) return d+1;
- return 0;
+ if (n < sizeof(size_t) * 3 || ((uintptr_t)d | (uintptr_t)s)
+ & sizeof(size_t) - 1) goto bytewise;
+
+ for (; (uintptr_t)s & sizeof(size_t) - 1 && *s != i
+ ; d++, s++, n--) *d = *s;
+ if ((uintptr_t)s & sizeof(size_t) - 1) return d + 1;
+
+ wd = (void *)d;
+ ws = (const void *)s;
+ for (; n >= sizeof(size_t) && !word_has_zero(*ws ^ wi)
+ ; *wd++ = *ws++, n -= sizeof(size_t));
+ d = (void *)wd;
+ s = (const void *)ws;
+
+bytewise:
+ for (; n && *d != i; *d++ = *s++, n--);
+
+ return n ? d + 1 : 0;
}
diff --git a/src/string/memchr.c b/src/string/memchr.c
index 4daff7bb..0b3d3d80 100644
--- a/src/string/memchr.c
+++ b/src/string/memchr.c
@@ -1,23 +1,28 @@
#include <string.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)
+#define aliases __attribute__((__may_alias__))
+#define byte_repeat(x) ((size_t)~0 / 0xff * (x))
+#define word_has_zero(x) (((x) - byte_repeat(0x01)) & ~(x) & byte_repeat(0x80))
-void *memchr(const void *src, int c, size_t n)
+void *memchr(const void *_s, int i, 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--);
- }
+ i = (unsigned char)i;
+ const unsigned char *s = _s;
+ const size_t aliases *ws, wi = byte_repeat(i);
+
+ if (n < sizeof(size_t) * 3) goto bytewise;
+
+ for (; (uintptr_t)s & sizeof(size_t) - 1 && *s != i; s++, n--);
+ if ((uintptr_t)s & sizeof(size_t) - 1) return (void *)s;
+
+ ws = (const void *)s;
+ for (; n >= sizeof(size_t) && !word_has_zero(*ws ^ wi)
+ ; ws++, n -= sizeof(size_t));
+ s = (const void *)ws;
+
+bytewise:
+ for (; n && *s != i; s++, n--);
+
return n ? (void *)s : 0;
}
diff --git a/src/string/stpcpy.c b/src/string/stpcpy.c
index 06623c44..0c4eb21a 100644
--- a/src/string/stpcpy.c
+++ b/src/string/stpcpy.c
@@ -1,26 +1,29 @@
#include <string.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)
+#define aliases __attribute__((__may_alias__))
+#define byte_repeat(x) ((size_t)~0 / 0xff * (x))
+#define word_has_zero(x) (((x) - byte_repeat(0x01)) & ~(x) & byte_repeat(0x80))
+#define weak_alias(o, n) extern __typeof__(o) n __attribute__((weak, alias(#o)))
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++);
+ size_t aliases *wd;
+ const size_t aliases *ws;
+
+ if (((uintptr_t)d | (uintptr_t)s) & sizeof(size_t) - 1) goto bytewise;
+
+ for (; (uintptr_t)s & sizeof(size_t) - 1 && (*d = *s); d++, s++);
+ if ((uintptr_t)s & sizeof(size_t) - 1) return d;
+
+ wd = (void *)d;
+ ws = (const void *)s;
+ for (; !word_has_zero(*ws); wd++, ws++) *wd = *ws;
+ d = (void *)wd;
+ s = (const void *)ws;
+
+bytewise:
+ for (; *d = *s; d++, s++);
return d;
}
diff --git a/src/string/stpncpy.c b/src/string/stpncpy.c
index 1f57a4dd..0b37da5d 100644
--- a/src/string/stpncpy.c
+++ b/src/string/stpncpy.c
@@ -1,31 +1,33 @@
#include <string.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)
+#define aliases __attribute__((__may_alias__))
+#define byte_repeat(x) ((size_t)~0 / 0xff * (x))
+#define word_has_zero(x) (((x) - byte_repeat(0x01)) & ~(x) & byte_repeat(0x80))
+#define weak_alias(o, n) extern __typeof__(o) n __attribute__((weak, alias(#o)))
char *__stpncpy(char *restrict d, const char *restrict 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;
+ if (n < sizeof(size_t) * 3 || ((uintptr_t)d | (uintptr_t)s)
+ & sizeof(size_t) - 1) goto bytewise;
+
+ for (; ((uintptr_t)s & sizeof(size_t) - 1) && (*d = *s); d++, s++, n--);
+ if (!*s) return memset(d, 0, n);
+
+ wd = (void *)d;
+ ws = (const void *)s;
+ for (; n >= sizeof(size_t) && !word_has_zero(*ws)
+ ; n -= sizeof(size_t), wd++, ws++) *wd = *ws;
+ d = (void *)wd;
+ s = (const void *)ws;
+
+bytewise:
+ for (; n && (*d = *s); d++, s++, n--);
+
+ return memset(d, 0, n);
}
weak_alias(__stpncpy, stpncpy);
-
diff --git a/src/string/strchrnul.c b/src/string/strchrnul.c
index 05700ad6..80405595 100644
--- a/src/string/strchrnul.c
+++ b/src/string/strchrnul.c
@@ -1,25 +1,28 @@
#include <string.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)
+#define aliases __attribute__((__may_alias__))
+#define byte_repeat(x) ((size_t)~0 / 0xff * (x))
+#define word_has_zero(x) (((x) - byte_repeat(0x01)) & ~(x) & byte_repeat(0x80))
+#define weak_alias(o, n) extern __typeof__(o) n __attribute__((weak, alias(#o)))
-char *__strchrnul(const char *s, int c)
+char *__strchrnul(const char *_s, int i)
{
- size_t *w, k;
+ i = (unsigned char)i;
+ const unsigned char *s = (const void *)_s;
+ const size_t aliases *ws, wi = byte_repeat(i);
- c = (unsigned char)c;
- if (!c) return (char *)s + strlen(s);
+ if (!i) return (char *)s + strlen((char *)s);
+
+ for (; (uintptr_t)s & sizeof(size_t) - 1 && *s && *s != i; s++);
+ if ((uintptr_t)s & sizeof(size_t) - 1) return (char *)s;
+
+ ws = (const void *)s;
+ for (; !word_has_zero(*ws) && !word_has_zero(*ws ^ wi); ws++);
+ s = (const void *)ws;
+
+ for (; *s && *s != i; s++);
- for (; (uintptr_t)s % ALIGN; s++)
- if (!*s || *(unsigned char *)s == c) return (char *)s;
- k = ONES * c;
- for (w = (void *)s; !HASZERO(*w) && !HASZERO(*w^k); w++);
- for (s = (void *)w; *s && *(unsigned char *)s != c; s++);
return (char *)s;
}
diff --git a/src/string/strlen.c b/src/string/strlen.c
index 929ddcbc..19ba310a 100644
--- a/src/string/strlen.c
+++ b/src/string/strlen.c
@@ -1,18 +1,23 @@
#include <string.h>
#include <stdint.h>
-#include <limits.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)
+#define aliases __attribute__((__may_alias__))
+#define byte_repeat(x) ((size_t)~0 / 0xff * (x))
+#define word_has_zero(x) (((x) - byte_repeat(0x01)) & ~(x) & byte_repeat(0x80))
size_t strlen(const char *s)
{
- const char *a = s;
- const size_t *w;
- for (; (uintptr_t)s % ALIGN; s++) if (!*s) return s-a;
- for (w = (const void *)s; !HASZERO(*w); w++);
- for (s = (const void *)w; *s; s++);
- return s-a;
+ const char *const s0 = s;
+ const size_t aliases *ws;
+
+ for (; (uintptr_t)s & sizeof(size_t) - 1 && *s; s++);
+ if (!*s) return s - s0;
+
+ ws = (const void *)s;
+ for (; !word_has_zero(*ws); ws++);
+ s = (const void *)ws;
+
+ for (; *s; s++);
+
+ return s - s0;
}
--
2.13.2
next prev parent reply other threads:[~2017-07-15 19:55 UTC|newest]
Thread overview: 6+ messages / expand[flat|nested] mbox.gz Atom feed top
2017-07-15 19:55 [RFC PATCH 0/5] Add explicit_bzero, vectorize and 'normalize' various string functions Nathan McSween
2017-07-15 19:55 ` [RFC PATCH 1/5] string: vectorize various functions Nathan McSween
2017-07-15 19:55 ` Nathan McSween [this message]
2017-07-15 19:55 ` [RFC PATCH 3/5] string: add strscpy and modify functions to use strscpy Nathan McSween
2017-07-15 19:55 ` [RFC PATCH 4/5] string: use strchrnul in strcasestr instead of bytewise iteration Nathan McSween
2017-07-15 19:55 ` [RFC PATCH 5/5] string: add memsset a 'secure' memset and bsd explicit_bzero Nathan McSween
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20170715195541.3136-3-nwmcsween@gmail.com \
--to=nwmcsween@gmail.com \
--cc=musl@lists.openwall.com \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
Code repositories for project(s) associated with this public inbox
https://git.vuxu.org/mirror/musl/
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).