Author: delphij
Date: Mon Dec 3 18:03:06 2012
New Revision: 243810
URL: http://svnweb.freebsd.org/changeset/base/243810
Log:
MFC r242506:
Sync strlen with userland implementation.
Modified:
stable/8/sys/libkern/strlen.c
Directory Properties:
stable/8/sys/ (props changed)
stable/8/sys/libkern/ (props changed)
Modified: stable/8/sys/libkern/strlen.c
==============================================================================
--- stable/8/sys/libkern/strlen.c Mon Dec 3 18:01:53 2012
(r243809)
+++ stable/8/sys/libkern/strlen.c Mon Dec 3 18:03:06 2012
(r243810)
@@ -1,6 +1,6 @@
/*-
- * Copyright (c) 1990, 1993
- * The Regents of the University of California. All rights reserved.
+ * Copyright (c) 2009, 2010 Xin LI <delp...@freebsd.org>
+ * All rights reserved.
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions
@@ -10,14 +10,11 @@
* 2. Redistributions in binary form must reproduce the above copyright
* notice, this list of conditions and the following disclaimer in the
* documentation and/or other materials provided with the distribution.
- * 4. Neither the name of the University nor the names of its contributors
- * may be used to endorse or promote products derived from this software
- * without specific prior written permission.
*
- * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
+ * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
- * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
+ * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
@@ -31,14 +28,102 @@
__FBSDID("$FreeBSD$");
#include <sys/libkern.h>
+#include <sys/limits.h>
+
+/*
+ * Portable strlen() for 32-bit and 64-bit systems.
+ *
+ * Rationale: it is generally much more efficient to do word length
+ * operations and avoid branches on modern computer systems, as
+ * compared to byte-length operations with a lot of branches.
+ *
+ * The expression:
+ *
+ * ((x - 0x01....01) & ~x & 0x80....80)
+ *
+ * would evaluate to a non-zero value iff any of the bytes in the
+ * original word is zero.
+ *
+ * On multi-issue processors, we can divide the above expression into:
+ * a) (x - 0x01....01)
+ * b) (~x & 0x80....80)
+ * c) a & b
+ *
+ * Where, a) and b) can be partially computed in parallel.
+ *
+ * The algorithm above is found on "Hacker's Delight" by
+ * Henry S. Warren, Jr.
+ */
+
+/* Magic numbers for the algorithm */
+#if LONG_BIT == 32
+static const unsigned long mask01 = 0x01010101;
+static const unsigned long mask80 = 0x80808080;
+#elif LONG_BIT == 64
+static const unsigned long mask01 = 0x0101010101010101;
+static const unsigned long mask80 = 0x8080808080808080;
+#else
+#error Unsupported word size
+#endif
+
+#define LONGPTR_MASK (sizeof(long) - 1)
+
+/*
+ * Helper macro to return string length if we caught the zero
+ * byte.
+ */
+#define testbyte(x) \
+ do { \
+ if (p[x] == '\0') \
+ return (p - str + x); \
+ } while (0)
size_t
-strlen(str)
- const char *str;
+strlen(const char *str)
{
- register const char *s;
+ const char *p;
+ const unsigned long *lp;
+ long va, vb;
- for (s = str; *s; ++s);
- return(s - str);
-}
+ /*
+ * Before trying the hard (unaligned byte-by-byte access) way
+ * to figure out whether there is a nul character, try to see
+ * if there is a nul character is within this accessible word
+ * first.
+ *
+ * p and (p & ~LONGPTR_MASK) must be equally accessible since
+ * they always fall in the same memory page, as long as page
+ * boundaries is integral multiple of word size.
+ */
+ lp = (const unsigned long *)((uintptr_t)str & ~LONGPTR_MASK);
+ va = (*lp - mask01);
+ vb = ((~*lp) & mask80);
+ lp++;
+ if (va & vb)
+ /* Check if we have \0 in the first part */
+ for (p = str; p < (const char *)lp; p++)
+ if (*p == '\0')
+ return (p - str);
+ /* Scan the rest of the string using word sized operation */
+ for (; ; lp++) {
+ va = (*lp - mask01);
+ vb = ((~*lp) & mask80);
+ if (va & vb) {
+ p = (const char *)(lp);
+ testbyte(0);
+ testbyte(1);
+ testbyte(2);
+ testbyte(3);
+#if (LONG_BIT >= 64)
+ testbyte(4);
+ testbyte(5);
+ testbyte(6);
+ testbyte(7);
+#endif
+ }
+ }
+
+ /* NOTREACHED */
+ return (0);
+}
_______________________________________________
svn-src-all@freebsd.org mailing list
http://lists.freebsd.org/mailman/listinfo/svn-src-all
To unsubscribe, send any mail to "svn-src-all-unsubscr...@freebsd.org"
