linux-kernel - [PATCH 2/2] string: improve strlen performance

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [thread-next>] [day] [month] [year] [list]

Message-Id: <20240502141359.89567-1-harry021633@gmail.com>
Date: Thu,  2 May 2024 22:13:59 +0800
From: "Hsin-Yu.Chen" <harry021633@...il.com>
To: keescook@...omium.org
Cc: andy@...nel.org,
	akpm@...ux-foundation.org,
	linux-hardening@...r.kernel.org,
	linux-kernel@...r.kernel.org,
	"Hsin-Yu.Chen" <harry021633@...il.com>
Subject: [PATCH 2/2] string: improve strlen performance

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@...il.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