Follow @Openwall on Twitter for new release announcements and other news
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Message-Id: <20170715195541.3136-3-nwmcsween@gmail.com>
Date: Sat, 15 Jul 2017 19:55:38 +0000
From: Nathan McSween <nwmcsween@...il.com>
To: musl@...ts.openwall.com
Cc: Nathan McSween <nwmcsween@...il.com>
Subject: [RFC PATCH 2/5] string: modify wordwise functions to match new style

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

Powered by blists - more mailing lists

Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.