xref: /illumos-gate/usr/src/boot/lib/libc/string/strlen.c (revision 199767f8)
1*199767f8SToomas Soome /*-
2*199767f8SToomas Soome  * Copyright (c) 2009, 2010 Xin LI <delphij@FreeBSD.org>
3*199767f8SToomas Soome  * All rights reserved.
4*199767f8SToomas Soome  *
5*199767f8SToomas Soome  * Redistribution and use in source and binary forms, with or without
6*199767f8SToomas Soome  * modification, are permitted provided that the following conditions
7*199767f8SToomas Soome  * are met:
8*199767f8SToomas Soome  * 1. Redistributions of source code must retain the above copyright
9*199767f8SToomas Soome  *    notice, this list of conditions and the following disclaimer.
10*199767f8SToomas Soome  * 2. Redistributions in binary form must reproduce the above copyright
11*199767f8SToomas Soome  *    notice, this list of conditions and the following disclaimer in the
12*199767f8SToomas Soome  *    documentation and/or other materials provided with the distribution.
13*199767f8SToomas Soome  *
14*199767f8SToomas Soome  * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
15*199767f8SToomas Soome  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16*199767f8SToomas Soome  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
17*199767f8SToomas Soome  * ARE DISCLAIMED.  IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
18*199767f8SToomas Soome  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
19*199767f8SToomas Soome  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
20*199767f8SToomas Soome  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
21*199767f8SToomas Soome  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
22*199767f8SToomas Soome  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
23*199767f8SToomas Soome  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
24*199767f8SToomas Soome  * SUCH DAMAGE.
25*199767f8SToomas Soome  */
26*199767f8SToomas Soome 
27*199767f8SToomas Soome #include <sys/cdefs.h>
28*199767f8SToomas Soome __FBSDID("$FreeBSD$");
29*199767f8SToomas Soome 
30*199767f8SToomas Soome #include <sys/limits.h>
31*199767f8SToomas Soome #include <sys/types.h>
32*199767f8SToomas Soome #include <string.h>
33*199767f8SToomas Soome 
34*199767f8SToomas Soome /*
35*199767f8SToomas Soome  * Portable strlen() for 32-bit and 64-bit systems.
36*199767f8SToomas Soome  *
37*199767f8SToomas Soome  * Rationale: it is generally much more efficient to do word length
38*199767f8SToomas Soome  * operations and avoid branches on modern computer systems, as
39*199767f8SToomas Soome  * compared to byte-length operations with a lot of branches.
40*199767f8SToomas Soome  *
41*199767f8SToomas Soome  * The expression:
42*199767f8SToomas Soome  *
43*199767f8SToomas Soome  *	((x - 0x01....01) & ~x & 0x80....80)
44*199767f8SToomas Soome  *
45*199767f8SToomas Soome  * would evaluate to a non-zero value iff any of the bytes in the
46*199767f8SToomas Soome  * original word is zero.
47*199767f8SToomas Soome  *
48*199767f8SToomas Soome  * On multi-issue processors, we can divide the above expression into:
49*199767f8SToomas Soome  *	a)  (x - 0x01....01)
50*199767f8SToomas Soome  *	b) (~x & 0x80....80)
51*199767f8SToomas Soome  *	c) a & b
52*199767f8SToomas Soome  *
53*199767f8SToomas Soome  * Where, a) and b) can be partially computed in parallel.
54*199767f8SToomas Soome  *
55*199767f8SToomas Soome  * The algorithm above is found on "Hacker's Delight" by
56*199767f8SToomas Soome  * Henry S. Warren, Jr.
57*199767f8SToomas Soome  */
58*199767f8SToomas Soome 
59*199767f8SToomas Soome /* Magic numbers for the algorithm */
60*199767f8SToomas Soome #if LONG_BIT == 32
61*199767f8SToomas Soome static const unsigned long mask01 = 0x01010101;
62*199767f8SToomas Soome static const unsigned long mask80 = 0x80808080;
63*199767f8SToomas Soome #elif LONG_BIT == 64
64*199767f8SToomas Soome static const unsigned long mask01 = 0x0101010101010101;
65*199767f8SToomas Soome static const unsigned long mask80 = 0x8080808080808080;
66*199767f8SToomas Soome #else
67*199767f8SToomas Soome #error Unsupported word size
68*199767f8SToomas Soome #endif
69*199767f8SToomas Soome 
70*199767f8SToomas Soome #define	LONGPTR_MASK (sizeof(long) - 1)
71*199767f8SToomas Soome 
72*199767f8SToomas Soome /*
73*199767f8SToomas Soome  * Helper macro to return string length if we caught the zero
74*199767f8SToomas Soome  * byte.
75*199767f8SToomas Soome  */
76*199767f8SToomas Soome #define testbyte(x)				\
77*199767f8SToomas Soome 	do {					\
78*199767f8SToomas Soome 		if (p[x] == '\0')		\
79*199767f8SToomas Soome 		    return (p - str + x);	\
80*199767f8SToomas Soome 	} while (0)
81*199767f8SToomas Soome 
82*199767f8SToomas Soome size_t
strlen(const char * str)83*199767f8SToomas Soome strlen(const char *str)
84*199767f8SToomas Soome {
85*199767f8SToomas Soome 	const char *p;
86*199767f8SToomas Soome 	const unsigned long *lp;
87*199767f8SToomas Soome 	long va, vb;
88*199767f8SToomas Soome 
89*199767f8SToomas Soome 	/*
90*199767f8SToomas Soome 	 * Before trying the hard (unaligned byte-by-byte access) way
91*199767f8SToomas Soome 	 * to figure out whether there is a nul character, try to see
92*199767f8SToomas Soome 	 * if there is a nul character is within this accessible word
93*199767f8SToomas Soome 	 * first.
94*199767f8SToomas Soome 	 *
95*199767f8SToomas Soome 	 * p and (p & ~LONGPTR_MASK) must be equally accessible since
96*199767f8SToomas Soome 	 * they always fall in the same memory page, as long as page
97*199767f8SToomas Soome 	 * boundaries is integral multiple of word size.
98*199767f8SToomas Soome 	 */
99*199767f8SToomas Soome 	lp = (const unsigned long *)((uintptr_t)str & ~LONGPTR_MASK);
100*199767f8SToomas Soome 	va = (*lp - mask01);
101*199767f8SToomas Soome 	vb = ((~*lp) & mask80);
102*199767f8SToomas Soome 	lp++;
103*199767f8SToomas Soome 	if (va & vb)
104*199767f8SToomas Soome 		/* Check if we have \0 in the first part */
105*199767f8SToomas Soome 		for (p = str; p < (const char *)lp; p++)
106*199767f8SToomas Soome 			if (*p == '\0')
107*199767f8SToomas Soome 				return (p - str);
108*199767f8SToomas Soome 
109*199767f8SToomas Soome 	/* Scan the rest of the string using word sized operation */
110*199767f8SToomas Soome 	for (; ; lp++) {
111*199767f8SToomas Soome 		va = (*lp - mask01);
112*199767f8SToomas Soome 		vb = ((~*lp) & mask80);
113*199767f8SToomas Soome 		if (va & vb) {
114*199767f8SToomas Soome 			p = (const char *)(lp);
115*199767f8SToomas Soome 			testbyte(0);
116*199767f8SToomas Soome 			testbyte(1);
117*199767f8SToomas Soome 			testbyte(2);
118*199767f8SToomas Soome 			testbyte(3);
119*199767f8SToomas Soome #if (LONG_BIT >= 64)
120*199767f8SToomas Soome 			testbyte(4);
121*199767f8SToomas Soome 			testbyte(5);
122*199767f8SToomas Soome 			testbyte(6);
123*199767f8SToomas Soome 			testbyte(7);
124*199767f8SToomas Soome #endif
125*199767f8SToomas Soome 		}
126*199767f8SToomas Soome 	}
127*199767f8SToomas Soome 
128*199767f8SToomas Soome 	/* NOTREACHED */
129*199767f8SToomas Soome 	return (0);
130*199767f8SToomas Soome }
131