[PATCH 2/2] string: improve strlen performance

From: Hsin-Yu.Chen
Date: Thu May 02 2024 - 10:14:27 EST


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@xxxxxxxxx>
---
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