strlen.c revision 205099
1234287Sdim/*- 2234287Sdim * Copyright (c) 2009, 2010 Xin LI <delphij@FreeBSD.org> 3234287Sdim * All rights reserved. 4234287Sdim * 5234287Sdim * Redistribution and use in source and binary forms, with or without 6234287Sdim * modification, are permitted provided that the following conditions 7234287Sdim * are met: 8234287Sdim * 1. Redistributions of source code must retain the above copyright 9234287Sdim * notice, this list of conditions and the following disclaimer. 10234287Sdim * 2. Redistributions in binary form must reproduce the above copyright 11234287Sdim * notice, this list of conditions and the following disclaimer in the 12234287Sdim * documentation and/or other materials provided with the distribution. 13234287Sdim * 14234287Sdim * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 15234287Sdim * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 16234287Sdim * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 17234287Sdim * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 18239462Sdim * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 19234287Sdim * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 20234287Sdim * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 21234287Sdim * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 22234287Sdim * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 23234287Sdim * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 24234287Sdim * SUCH DAMAGE. 25234287Sdim */ 26234287Sdim 27234287Sdim#include <sys/cdefs.h> 28234287Sdim__FBSDID("$FreeBSD: head/lib/libc/string/strlen.c 205099 2010-03-12 21:14:56Z delphij $"); 29234287Sdim 30234287Sdim#include <sys/limits.h> 31234287Sdim#include <sys/types.h> 32234287Sdim#include <string.h> 33263508Sdim 34234287Sdim/* 35234287Sdim * Portable strlen() for 32-bit and 64-bit systems. 36234287Sdim * 37239462Sdim * Rationale: it is generally much more efficient to do word length 38239462Sdim * operations and avoid branches on modern computer systems, as 39239462Sdim * compared to byte-length operations with a lot of branches. 40249423Sdim * 41249423Sdim * The expression: 42234287Sdim * 43234287Sdim * ((x - 0x01....01) & ~x & 0x80....80) 44234287Sdim * 45234287Sdim * would evaluate to a non-zero value iff any of the bytes in the 46234287Sdim * original word is zero. 47234287Sdim * 48234287Sdim * On multi-issue processors, we can divide the above expression into: 49234287Sdim * a) (x - 0x01....01) 50234287Sdim * b) (~x & 0x80....80) 51234287Sdim * c) a & b 52234287Sdim * 53234287Sdim * Where, a) and b) can be partially computed in parallel. 54234287Sdim * 55234287Sdim * The algorithm above is found on "Hacker's Delight" by 56234287Sdim * Henry S. Warren, Jr. 57263508Sdim */ 58263508Sdim 59263508Sdim/* Magic numbers for the algorithm */ 60263508Sdim#if LONG_BIT == 32 61263508Sdimstatic const unsigned long mask01 = 0x01010101; 62263508Sdimstatic const unsigned long mask80 = 0x80808080; 63263508Sdim#elif LONG_BIT == 64 64263508Sdimstatic const unsigned long mask01 = 0x0101010101010101; 65263508Sdimstatic const unsigned long mask80 = 0x8080808080808080; 66263508Sdim#else 67263508Sdim#error Unsupported word size 68263508Sdim#endif 69263508Sdim 70263508Sdim#define LONGPTR_MASK (sizeof(long) - 1) 71234287Sdim 72263508Sdim/* 73263508Sdim * Helper macro to return string length if we caught the zero 74263508Sdim * byte. 75263508Sdim */ 76263508Sdim#define testbyte(x) \ 77263508Sdim do { \ 78234287Sdim if (p[x] == '\0') \ 79234287Sdim return (p - str + x); \ 80234287Sdim } while (0) 81263508Sdim 82263508Sdimsize_t 83263508Sdimstrlen(const char *str) 84263508Sdim{ 85234287Sdim const char *p; 86234287Sdim const unsigned long *lp; 87234287Sdim long va, vb; 88234287Sdim 89234287Sdim /* 90234287Sdim * Before trying the hard (unaligned byte-by-byte access) way 91234287Sdim * to figure out whether there is a nul character, try to see 92234287Sdim * if there is a nul character is within this accessible word 93263508Sdim * first. 94234287Sdim * 95234287Sdim * p and (p & ~LONGPTR_MASK) must be equally accessible since 96234287Sdim * they always fall in the same memory page, as long as page 97234287Sdim * boundaries is integral multiple of word size. 98234287Sdim */ 99234287Sdim lp = (const unsigned long *)((uintptr_t)str & ~LONGPTR_MASK); 100234287Sdim va = (*lp - mask01); 101263508Sdim vb = ((~*lp) & mask80); 102263508Sdim if (va & vb) 103263508Sdim /* Check if we have \0 in the first part */ 104263508Sdim for (p = str; (uintptr_t)p & LONGPTR_MASK; p++) 105243830Sdim if (*p == '\0') 106263508Sdim return (p - str); 107263508Sdim 108263508Sdim /* Scan the rest of the string using word sized operation */ 109263508Sdim for (lp = (const unsigned long *)p; ; lp++) { 110263508Sdim va = (*lp - mask01); 111263508Sdim vb = ((~*lp) & mask80); 112263508Sdim if (va & vb) { 113263508Sdim p = (const char *)(lp); 114263508Sdim testbyte(0); 115263508Sdim testbyte(1); 116263508Sdim testbyte(2); 117243830Sdim testbyte(3); 118243830Sdim#if (LONG_BIT >= 64) 119234287Sdim testbyte(4); 120239462Sdim testbyte(5); 121234287Sdim testbyte(6); 122239462Sdim testbyte(7); 123234287Sdim#endif 124234287Sdim } 125239462Sdim } 126239462Sdim 127234287Sdim /* NOTREACHED */ 128234287Sdim return (0); 129234287Sdim} 130234287Sdim