public inbox for linux-kernel@vger.kernel.org
 help / color / mirror / Atom feed
* [PATCH 2/2] string: improve strlen performance
@ 2024-05-02 14:13 Hsin-Yu.Chen
  2024-05-02 14:59 ` Andy Shevchenko
  0 siblings, 1 reply; 6+ messages in thread
From: Hsin-Yu.Chen @ 2024-05-02 14:13 UTC (permalink / raw)
  To: keescook; +Cc: andy, akpm, linux-hardening, linux-kernel, Hsin-Yu.Chen

Port `strlen` in gcc, which enhance performance over 10 times

Please refer to these following articles
1. [Determine if a word has a byte less than n]
   (https://graphics.stanford.edu/~seander/bithacks.html#HasLessInWord)
2. [Determine if a word has a zero byte]
   (https://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord)

Signed-off-by: Hsin-Yu.Chen <harry021633@gmail.com>
---
 lib/string.c | 77 +++++++++++++++++++++++++++++++++++++++++++++++++---
 1 file changed, 73 insertions(+), 4 deletions(-)

diff --git a/lib/string.c b/lib/string.c
index 6891d15ce991..31e8642422af 100644
--- a/lib/string.c
+++ b/lib/string.c
@@ -398,11 +398,80 @@ EXPORT_SYMBOL(strnchr);
 #ifndef __HAVE_ARCH_STRLEN
 size_t strlen(const char *s)
 {
-	const char *sc;
+	const char *char_ptr;
+	const unsigned long *longword_ptr;
+	unsigned long longword, himagic, lomagic;
 
-	for (sc = s; *sc != '\0'; ++sc)
-		/* nothing */;
-	return sc - s;
+	/* Handle the first few characters by reading one character at a time.
+	 * Do this until CHAR_PTR is aligned on a longword boundary.
+	 */
+	for (char_ptr = s; ((unsigned long) char_ptr
+		& (sizeof(longword) - 1)) != 0;
+		++char_ptr)
+		if (*char_ptr == '\0')
+			return char_ptr - s;
+
+	/* All these elucidatory comments refer to 4-byte longwords,
+	 * but the theory applies equally well to 8-byte longwords.
+	 */
+	longword_ptr = (unsigned long *) char_ptr;
+
+	/* Bits 31, 24, 16, and 8 of this number are zero.
+	 * Call these bits the "holes."
+	 * Note that there is a hole just to the left of
+	 * each byte, with an extra at the end:
+	 * bits:  01111110 11111110 11111110 11111111
+	 * bytes: AAAAAAAA BBBBBBBB CCCCCCCC DDDDDDDD
+	 * The 1-bits make sure that carries propagate to the next 0-bit.
+	 * The 0-bits provide holes for carries to fall into.
+	 */
+	himagic = 0x80808080L;
+	lomagic = 0x01010101L;
+
+	if (sizeof(longword) > 4) {
+		/* 64-bit version of the magic. */
+		/* Do the shift in two steps to avoid a warning if long has 32 bits.
+		 */
+		himagic = ((himagic << 16) << 16) | himagic;
+		lomagic = ((lomagic << 16) << 16) | lomagic;
+	}
+
+	if (sizeof(longword) > 8)
+		abort();
+
+	/* Instead of the traditional loop which tests each character,
+	 * we will test a longword at a time.  The tricky part is testing
+	 * if *any of the four* bytes in the longword in question are zero.
+	 */
+	for (;;) {
+		longword = *longword_ptr++;
+		if (((longword - lomagic) & ~longword & himagic) != 0) {
+
+			/* Which of the bytes was the zero?
+			 * If none of them were, it was a misfire; continue the search.
+			 */
+			const char *cp = (const char *) (longword_ptr - 1);
+
+			if (cp[0] == 0)
+				return cp - s;
+			else if (cp[1] == 0)
+				return cp - s + 1;
+			else if (cp[2] == 0)
+				return cp - s + 2;
+			else if (cp[3] == 0)
+				return cp - s + 3;
+			if (sizeof(longword) > 4) {
+				if (cp[4] == 0)
+					return cp - s + 4;
+				else if (cp[5] == 0)
+					return cp - s + 5;
+				else if (cp[6] == 0)
+					return cp - s + 6;
+				else if (cp[7] == 0)
+					return cp - s + 7;
+			}
+		}
+	}
 }
 EXPORT_SYMBOL(strlen);
 #endif
-- 
2.38.1


^ permalink raw reply related	[flat|nested] 6+ messages in thread
end of thread, other threads:[~2024-05-05 13:39 UTC | newest]

Thread overview: 6+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2024-05-02 14:13 [PATCH 2/2] string: improve strlen performance Hsin-Yu.Chen
2024-05-02 14:59 ` Andy Shevchenko
2024-05-02 15:03   ` Andy Shevchenko
2024-05-02 15:10     ` Kees Cook
2024-05-02 15:38       ` Andy Shevchenko
2024-05-05 13:38       ` David Laight

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox