1199767f8SToomas Soome /*-
2199767f8SToomas Soome * Copyright (c) 2009, 2010 Xin LI <delphij@FreeBSD.org>
3199767f8SToomas Soome * All rights reserved.
4199767f8SToomas Soome *
5199767f8SToomas Soome * Redistribution and use in source and binary forms, with or without
6199767f8SToomas Soome * modification, are permitted provided that the following conditions
7199767f8SToomas Soome * are met:
8199767f8SToomas Soome * 1. Redistributions of source code must retain the above copyright
9199767f8SToomas Soome * notice, this list of conditions and the following disclaimer.
10199767f8SToomas Soome * 2. Redistributions in binary form must reproduce the above copyright
11199767f8SToomas Soome * notice, this list of conditions and the following disclaimer in the
12199767f8SToomas Soome * documentation and/or other materials provided with the distribution.
13199767f8SToomas Soome *
14199767f8SToomas Soome * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
15199767f8SToomas Soome * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16199767f8SToomas Soome * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
17199767f8SToomas Soome * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
18199767f8SToomas Soome * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
19199767f8SToomas Soome * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
20199767f8SToomas Soome * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
21199767f8SToomas Soome * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
22199767f8SToomas Soome * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
23199767f8SToomas Soome * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
24199767f8SToomas Soome * SUCH DAMAGE.
25199767f8SToomas Soome */
26199767f8SToomas Soome
27199767f8SToomas Soome #include <sys/cdefs.h>
28199767f8SToomas Soome __FBSDID("$FreeBSD$");
29199767f8SToomas Soome
30199767f8SToomas Soome #include <sys/limits.h>
31199767f8SToomas Soome #include <sys/types.h>
32199767f8SToomas Soome #include <string.h>
33199767f8SToomas Soome
34199767f8SToomas Soome /*
35199767f8SToomas Soome * Portable strlen() for 32-bit and 64-bit systems.
36199767f8SToomas Soome *
37199767f8SToomas Soome * Rationale: it is generally much more efficient to do word length
38199767f8SToomas Soome * operations and avoid branches on modern computer systems, as
39199767f8SToomas Soome * compared to byte-length operations with a lot of branches.
40199767f8SToomas Soome *
41199767f8SToomas Soome * The expression:
42199767f8SToomas Soome *
43199767f8SToomas Soome * ((x - 0x01....01) & ~x & 0x80....80)
44199767f8SToomas Soome *
45199767f8SToomas Soome * would evaluate to a non-zero value iff any of the bytes in the
46199767f8SToomas Soome * original word is zero.
47199767f8SToomas Soome *
48199767f8SToomas Soome * On multi-issue processors, we can divide the above expression into:
49199767f8SToomas Soome * a) (x - 0x01....01)
50199767f8SToomas Soome * b) (~x & 0x80....80)
51199767f8SToomas Soome * c) a & b
52199767f8SToomas Soome *
53199767f8SToomas Soome * Where, a) and b) can be partially computed in parallel.
54199767f8SToomas Soome *
55199767f8SToomas Soome * The algorithm above is found on "Hacker's Delight" by
56199767f8SToomas Soome * Henry S. Warren, Jr.
57199767f8SToomas Soome */
58199767f8SToomas Soome
59199767f8SToomas Soome /* Magic numbers for the algorithm */
60199767f8SToomas Soome #if LONG_BIT == 32
61199767f8SToomas Soome static const unsigned long mask01 = 0x01010101;
62199767f8SToomas Soome static const unsigned long mask80 = 0x80808080;
63199767f8SToomas Soome #elif LONG_BIT == 64
64199767f8SToomas Soome static const unsigned long mask01 = 0x0101010101010101;
65199767f8SToomas Soome static const unsigned long mask80 = 0x8080808080808080;
66199767f8SToomas Soome #else
67199767f8SToomas Soome #error Unsupported word size
68199767f8SToomas Soome #endif
69199767f8SToomas Soome
70199767f8SToomas Soome #define LONGPTR_MASK (sizeof(long) - 1)
71199767f8SToomas Soome
72199767f8SToomas Soome /*
73199767f8SToomas Soome * Helper macro to return string length if we caught the zero
74199767f8SToomas Soome * byte.
75199767f8SToomas Soome */
76199767f8SToomas Soome #define testbyte(x) \
77199767f8SToomas Soome do { \
78199767f8SToomas Soome if (p[x] == '\0') \
79199767f8SToomas Soome return (p - str + x); \
80199767f8SToomas Soome } while (0)
81199767f8SToomas Soome
82199767f8SToomas Soome size_t
strlen(const char * str)83199767f8SToomas Soome strlen(const char *str)
84199767f8SToomas Soome {
85199767f8SToomas Soome const char *p;
86199767f8SToomas Soome const unsigned long *lp;
87199767f8SToomas Soome long va, vb;
88199767f8SToomas Soome
89199767f8SToomas Soome /*
90199767f8SToomas Soome * Before trying the hard (unaligned byte-by-byte access) way
91199767f8SToomas Soome * to figure out whether there is a nul character, try to see
92199767f8SToomas Soome * if there is a nul character is within this accessible word
93199767f8SToomas Soome * first.
94199767f8SToomas Soome *
95199767f8SToomas Soome * p and (p & ~LONGPTR_MASK) must be equally accessible since
96199767f8SToomas Soome * they always fall in the same memory page, as long as page
97199767f8SToomas Soome * boundaries is integral multiple of word size.
98199767f8SToomas Soome */
99199767f8SToomas Soome lp = (const unsigned long *)((uintptr_t)str & ~LONGPTR_MASK);
100199767f8SToomas Soome va = (*lp - mask01);
101199767f8SToomas Soome vb = ((~*lp) & mask80);
102199767f8SToomas Soome lp++;
103199767f8SToomas Soome if (va & vb)
104199767f8SToomas Soome /* Check if we have \0 in the first part */
105199767f8SToomas Soome for (p = str; p < (const char *)lp; p++)
106199767f8SToomas Soome if (*p == '\0')
107199767f8SToomas Soome return (p - str);
108199767f8SToomas Soome
109199767f8SToomas Soome /* Scan the rest of the string using word sized operation */
110199767f8SToomas Soome for (; ; lp++) {
111199767f8SToomas Soome va = (*lp - mask01);
112199767f8SToomas Soome vb = ((~*lp) & mask80);
113199767f8SToomas Soome if (va & vb) {
114199767f8SToomas Soome p = (const char *)(lp);
115199767f8SToomas Soome testbyte(0);
116199767f8SToomas Soome testbyte(1);
117199767f8SToomas Soome testbyte(2);
118199767f8SToomas Soome testbyte(3);
119199767f8SToomas Soome #if (LONG_BIT >= 64)
120199767f8SToomas Soome testbyte(4);
121199767f8SToomas Soome testbyte(5);
122199767f8SToomas Soome testbyte(6);
123199767f8SToomas Soome testbyte(7);
124199767f8SToomas Soome #endif
125199767f8SToomas Soome }
126199767f8SToomas Soome }
127199767f8SToomas Soome
128199767f8SToomas Soome /* NOTREACHED */
129199767f8SToomas Soome return (0);
130199767f8SToomas Soome }
131