Openwall GNU/*/Linux - a small security-enhanced Linux distro for servers
[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]
Date: Sat, 15 Jul 2017 19:55:37 +0000
From: Nathan McSween <nwmcsween@...il.com>
To: musl@...ts.openwall.com
Cc: Nathan McSween <nwmcsween@...il.com>
Subject: [RFC PATCH 1/5] string: vectorize various functions

Text sizes with gcc version 6.3.0
Before | After
 49  |   153  memcmp.lo
 38  |   294  memrchr.lo
120  |   376  strcasecmp.lo
 96  |   305  strncmp.lo
155  |   454  strncasecmp.lo
 96  |   305  strncmp.lo
861  |  1887  (TOTALS)

The size increase is mainly due to vectorizing but also to both the
__may_alias__ attribute and the conditional before the alignment loop for
functions that take a size argument.

The str[n]casecmp macros are of particular interest and work via tagging the
high bit for any character in the range of A-Z and rhs said high bit two to give
a-z.
---
 src/string/memcmp.c      | 28 ++++++++++++++++++++++++----
 src/string/memrchr.c     | 29 +++++++++++++++++++++++------
 src/string/strcasecmp.c  | 34 ++++++++++++++++++++++++++++++----
 src/string/strcmp.c      | 27 ++++++++++++++++++++++++---
 src/string/strncasecmp.c | 37 +++++++++++++++++++++++++++++++++----
 src/string/strncmp.c     | 28 ++++++++++++++++++++++++++--
 6 files changed, 160 insertions(+), 23 deletions(-)

diff --git a/src/string/memcmp.c b/src/string/memcmp.c
index bdbce9f0..7d2e8077 100644
--- a/src/string/memcmp.c
+++ b/src/string/memcmp.c
@@ -1,8 +1,28 @@
 #include <string.h>
+#include <stdint.h>
 
-int memcmp(const void *vl, const void *vr, size_t n)
+#define aliases __attribute__((__may_alias__))
+
+int memcmp(const void *_l, const void *_r, size_t n)
 {
-	const unsigned char *l=vl, *r=vr;
-	for (; n && *l == *r; n--, l++, r++);
-	return n ? *l-*r : 0;
+	const unsigned char *l = _l, *r = _r;
+	const size_t aliases *wl, aliases *wr;
+
+	if (n < sizeof(size_t) * 3 || ((uintptr_t)l | (uintptr_t)r)
+	    & sizeof(size_t) - 1) goto bytewise;
+
+	for (; (uintptr_t)l & sizeof(size_t) - 1 && *l == *r; l++, r++, n--);
+	if ((uintptr_t)l & sizeof(size_t) -1) return *l - *r;
+
+	wl = (const void *)l;
+	wr = (const void *)r;
+	for (; n >= sizeof(size_t) && *wl == *wr
+	     ; wl++, wr++, n -= sizeof(size_t));
+	l = (const void *)wl;
+	r = (const void *)wr;
+
+bytewise:
+	for (; n && *l == *r; l++, r++, n--);
+
+	return n ? *l - *r : 0;
 }
diff --git a/src/string/memrchr.c b/src/string/memrchr.c
index a78e9d6c..165c422b 100644
--- a/src/string/memrchr.c
+++ b/src/string/memrchr.c
@@ -1,12 +1,29 @@
 #include <string.h>
-#include "libc.h"
+#include <stdint.h>
 
-void *__memrchr(const void *m, int c, size_t n)
+#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)))
+
+void *__memrchr(const void *_s, int i, size_t n)
 {
-	const unsigned char *s = m;
-	c = (unsigned char)c;
-	while (n--) if (s[n]==c) return (void *)(s+n);
-	return 0;
+	i = (unsigned char )i;
+	const unsigned char *s = _s;
+	const size_t wi = byte_repeat(i);
+
+	if (n < sizeof(size_t) * 3) goto bytewise;
+
+	for (; (uintptr_t)(s + n) & sizeof(size_t) - 1 && s[n - 1] != i; n--);
+	if ((uintptr_t)(s + n) & sizeof(size_t) - 1) return (void *)(s + n - 1);
+
+	for (; n >= sizeof(size_t) &&
+	       !word_has_zero(*(size_t *)(s + n - sizeof(size_t)) ^ wi)
+	     ; n -= sizeof(size_t));
+
+bytewise:
+	for (; n && s[n - 1] != i; n--);
+
+	return n ? (void *)(s + n - 1) : 0;
 }
 
 weak_alias(__memrchr, memrchr);
diff --git a/src/string/strcasecmp.c b/src/string/strcasecmp.c
index 3cd5f2d0..07d56c5d 100644
--- a/src/string/strcasecmp.c
+++ b/src/string/strcasecmp.c
@@ -1,15 +1,41 @@
 #include <strings.h>
 #include <ctype.h>
-#include "libc.h"
+#include <stdint.h>
+
+#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 word_tag_range(x, t, s, e) ((((x) | byte_repeat(t)) \
+- byte_repeat(s) & ~((x) | byte_repeat(t)) - \
+byte_repeat((e) + 1)) & (~(x) & byte_repeat(t)))
+#define word_to_lower(x) ((x) - (word_tag_range((x), 'a', 'z', 0x80)) >> 2)
+#define weak_alias(o, n) extern __typeof__(o) n __attribute__((weak, alias(#o)))
 
 int strcasecmp(const char *_l, const char *_r)
 {
-	const unsigned char *l=(void *)_l, *r=(void *)_r;
-	for (; *l && *r && (*l == *r || tolower(*l) == tolower(*r)); l++, r++);
+	const unsigned char *l = (const void *)_l, *r = (const void *)_r;
+	const size_t aliases *wl, aliases *wr;
+
+	if (((uintptr_t)l | (uintptr_t)r) & sizeof(size_t) - 1) goto bytewise;
+
+	for (;(uintptr_t)l & sizeof(size_t) - 1 && *l
+	     && tolower(*l) == tolower(*r); l++, r++);
+	if ((uintptr_t)l & sizeof(size_t) - 1) return tolower(*l) - tolower(*r);
+
+	wl = (const void *)l;
+	wr = (const void *)r;
+	for (; !word_has_zero(*wl) && word_to_lower(*wl) == word_to_lower(*wr)
+	     ; wl++, wr++);
+	l = (const void *)wl;
+	r = (const void *)wr;
+
+bytewise:
+	for (; *l && tolower(*l) == tolower(*r); l++, r++);
+
 	return tolower(*l) - tolower(*r);
 }
 
-int __strcasecmp_l(const char *l, const char *r, locale_t loc)
+int __strcasecmp_l(const char *l, const char *r, locale_t unused)
 {
 	return strcasecmp(l, r);
 }
diff --git a/src/string/strcmp.c b/src/string/strcmp.c
index 808bd837..a2f358a9 100644
--- a/src/string/strcmp.c
+++ b/src/string/strcmp.c
@@ -1,7 +1,28 @@
 #include <string.h>
+#include <stdint.h>
 
-int strcmp(const char *l, const char *r)
+#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))
+
+int strcmp(const char *_l, const char *_r)
 {
-	for (; *l==*r && *l; l++, r++);
-	return *(unsigned char *)l - *(unsigned char *)r;
+	const unsigned char *l = (const void *)_l, *r = (const void *)_r;
+	const size_t aliases *wl, aliases *wr;
+
+	if (((uintptr_t)l | (uintptr_t)r) & sizeof(size_t) - 1) goto bytewise;
+
+	for (; (uintptr_t)l & sizeof(size_t) - 1 && *l && *l == *r; l++, r++);
+	if ((uintptr_t)l & sizeof(size_t) - 1) return *l - *r;
+
+	wl = (const void *)l;
+	wr = (const void *)r;
+	for (; !word_has_zero(*wl) && *wl == *wr; wl++, wr++);
+	l = (const void *)wl;
+	r = (const void *)wr;
+
+bytewise:
+	for (; *l && *l == *r; l++, r++);
+
+	return *l - *r;
 }
diff --git a/src/string/strncasecmp.c b/src/string/strncasecmp.c
index 3af53008..e1a9454a 100644
--- a/src/string/strncasecmp.c
+++ b/src/string/strncasecmp.c
@@ -1,16 +1,45 @@
 #include <strings.h>
 #include <ctype.h>
-#include "libc.h"
+#include <stdint.h>
+
+#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 word_tag_range(x, t, s, e) ((((x) | byte_repeat(t)) \
+- byte_repeat(s) & ~((x) | byte_repeat(t)) - \
+byte_repeat((e) + 1)) & (~(x) & byte_repeat(t)))
+#define word_to_tolower(x) ((x) - (word_tag_range((x), 'a', 'z', 0x80)) >> 2)
+#define weak_alias(o, n) extern __typeof__(o) n __attribute__((weak, alias(#o)))
 
 int strncasecmp(const char *_l, const char *_r, size_t n)
 {
-	const unsigned char *l=(void *)_l, *r=(void *)_r;
+	const unsigned char *l = (const void *)_l, *r = (const void *)_r;
+	const size_t aliases *wl, aliases *wr;
+
 	if (!n--) return 0;
-	for (; *l && *r && n && (*l == *r || tolower(*l) == tolower(*r)); l++, r++, n--);
+
+	if (n < sizeof(size_t) * 3 || ((uintptr_t)l | (uintptr_t)r)
+	    & sizeof(size_t) - 1) goto bytewise;
+
+	for (;(uintptr_t)l & sizeof(size_t) - 1 && *l
+	     && tolower(*l) == tolower(*r); l++, r++, n--);
+	if ((uintptr_t)l & sizeof(size_t) - 1) return tolower(*l) - tolower(*r);
+
+	wl = (const void *)l;
+	wr = (const void *)r;
+	for (; n >= sizeof(size_t) && !word_has_zero(*wl)
+	       && word_to_tolower(*wl) == word_to_tolower(*wr)
+	     ; wl++, wr++, n -= sizeof(size_t));
+	l = (const void *)wl;
+	r = (const void *)wr;
+
+bytewise:
+	for (; n && *l && tolower(*l) == tolower(*r); l++, r++, n--);
+
 	return tolower(*l) - tolower(*r);
 }
 
-int __strncasecmp_l(const char *l, const char *r, size_t n, locale_t loc)
+int __strncasecmp_l(const char *l, const char *r, size_t n, locale_t unused)
 {
 	return strncasecmp(l, r, n);
 }
diff --git a/src/string/strncmp.c b/src/string/strncmp.c
index e228843f..667498e1 100644
--- a/src/string/strncmp.c
+++ b/src/string/strncmp.c
@@ -1,9 +1,33 @@
 #include <string.h>
+#include <stdint.h>
+
+#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))
 
 int strncmp(const char *_l, const char *_r, size_t n)
 {
-	const unsigned char *l=(void *)_l, *r=(void *)_r;
+	const unsigned char *l = (const void *)_l, *r = (const void *)_r;
+	const size_t aliases *wl, aliases *wr;
+
 	if (!n--) return 0;
-	for (; *l && *r && n && *l == *r ; l++, r++, n--);
+
+	if (n < sizeof(size_t) * 3 || ((uintptr_t)l | (uintptr_t)r)
+	    & sizeof(size_t) - 1) goto bytewise;
+
+	for (; (uintptr_t)l & sizeof(size_t) - 1 && *l && *l == *r
+	     ; l++, r++, n--);
+	if ((uintptr_t)l & sizeof(size_t) - 1) return *l - *r;
+
+	wl = (const void *)l;
+	wr = (const void *)r;
+	for (; n >= sizeof(size_t) && !word_has_zero(*wl) && *wl == *wr
+	     ; wl++, wr++, n -= sizeof(size_t));
+	l = (const void *)wl;
+	r = (const void *)wr;
+
+bytewise:
+	for (; n && *l && *l == *r; l++, r++, n--);
+
 	return *l - *r;
 }
-- 
2.13.2

Powered by blists - more mailing lists

Your e-mail address:

Powered by Openwall GNU/*/Linux - Powered by OpenVZ