11573Srgrimes/*- 2205099Sdelphij * Copyright (c) 2009, 2010 Xin LI <delphij@FreeBSD.org> 3187700Sdelphij * All rights reserved. 41573Srgrimes * 51573Srgrimes * Redistribution and use in source and binary forms, with or without 61573Srgrimes * modification, are permitted provided that the following conditions 71573Srgrimes * are met: 81573Srgrimes * 1. Redistributions of source code must retain the above copyright 91573Srgrimes * notice, this list of conditions and the following disclaimer. 101573Srgrimes * 2. Redistributions in binary form must reproduce the above copyright 111573Srgrimes * notice, this list of conditions and the following disclaimer in the 121573Srgrimes * documentation and/or other materials provided with the distribution. 131573Srgrimes * 14187700Sdelphij * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 151573Srgrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 161573Srgrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 17187700Sdelphij * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 181573Srgrimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 191573Srgrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 201573Srgrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 211573Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 221573Srgrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 231573Srgrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 241573Srgrimes * SUCH DAMAGE. 251573Srgrimes */ 261573Srgrimes 2786170Sobrien#include <sys/cdefs.h> 2886170Sobrien__FBSDID("$FreeBSD: releng/10.3/lib/libc/string/strlen.c 205108 2010-03-13 00:15:06Z delphij $"); 291573Srgrimes 30187700Sdelphij#include <sys/limits.h> 31187700Sdelphij#include <sys/types.h> 321573Srgrimes#include <string.h> 331573Srgrimes 34187700Sdelphij/* 35187700Sdelphij * Portable strlen() for 32-bit and 64-bit systems. 36187700Sdelphij * 37187700Sdelphij * Rationale: it is generally much more efficient to do word length 38187700Sdelphij * operations and avoid branches on modern computer systems, as 39187700Sdelphij * compared to byte-length operations with a lot of branches. 40187700Sdelphij * 41187700Sdelphij * The expression: 42187700Sdelphij * 43187700Sdelphij * ((x - 0x01....01) & ~x & 0x80....80) 44187700Sdelphij * 45187700Sdelphij * would evaluate to a non-zero value iff any of the bytes in the 46205099Sdelphij * original word is zero. 47187700Sdelphij * 48205099Sdelphij * On multi-issue processors, we can divide the above expression into: 49205099Sdelphij * a) (x - 0x01....01) 50205099Sdelphij * b) (~x & 0x80....80) 51205099Sdelphij * c) a & b 52187700Sdelphij * 53205099Sdelphij * Where, a) and b) can be partially computed in parallel. 54205099Sdelphij * 55205099Sdelphij * The algorithm above is found on "Hacker's Delight" by 56205099Sdelphij * Henry S. Warren, Jr. 57187700Sdelphij */ 58187700Sdelphij 59187700Sdelphij/* Magic numbers for the algorithm */ 60187700Sdelphij#if LONG_BIT == 32 61187700Sdelphijstatic const unsigned long mask01 = 0x01010101; 62187700Sdelphijstatic const unsigned long mask80 = 0x80808080; 63187700Sdelphij#elif LONG_BIT == 64 64187700Sdelphijstatic const unsigned long mask01 = 0x0101010101010101; 65187700Sdelphijstatic const unsigned long mask80 = 0x8080808080808080; 66187700Sdelphij#else 67187700Sdelphij#error Unsupported word size 68187700Sdelphij#endif 69187700Sdelphij 70187700Sdelphij#define LONGPTR_MASK (sizeof(long) - 1) 71187700Sdelphij 72187700Sdelphij/* 73187700Sdelphij * Helper macro to return string length if we caught the zero 74187700Sdelphij * byte. 75187700Sdelphij */ 76187700Sdelphij#define testbyte(x) \ 77187700Sdelphij do { \ 78187700Sdelphij if (p[x] == '\0') \ 79187700Sdelphij return (p - str + x); \ 80187700Sdelphij } while (0) 81187700Sdelphij 821573Srgrimessize_t 83187700Sdelphijstrlen(const char *str) 841573Srgrimes{ 85187700Sdelphij const char *p; 86187700Sdelphij const unsigned long *lp; 87205099Sdelphij long va, vb; 881573Srgrimes 89205099Sdelphij /* 90205099Sdelphij * Before trying the hard (unaligned byte-by-byte access) way 91205099Sdelphij * to figure out whether there is a nul character, try to see 92205099Sdelphij * if there is a nul character is within this accessible word 93205099Sdelphij * first. 94205099Sdelphij * 95205099Sdelphij * p and (p & ~LONGPTR_MASK) must be equally accessible since 96205099Sdelphij * they always fall in the same memory page, as long as page 97205099Sdelphij * boundaries is integral multiple of word size. 98205099Sdelphij */ 99205099Sdelphij lp = (const unsigned long *)((uintptr_t)str & ~LONGPTR_MASK); 100205099Sdelphij va = (*lp - mask01); 101205099Sdelphij vb = ((~*lp) & mask80); 102205108Sdelphij lp++; 103205099Sdelphij if (va & vb) 104205099Sdelphij /* Check if we have \0 in the first part */ 105205108Sdelphij for (p = str; p < (const char *)lp; p++) 106205100Sdelphij if (*p == '\0') 107205100Sdelphij return (p - str); 108187700Sdelphij 109187700Sdelphij /* Scan the rest of the string using word sized operation */ 110205108Sdelphij for (; ; lp++) { 111205099Sdelphij va = (*lp - mask01); 112205099Sdelphij vb = ((~*lp) & mask80); 113205099Sdelphij if (va & vb) { 114205100Sdelphij p = (const char *)(lp); 115205100Sdelphij testbyte(0); 116205100Sdelphij testbyte(1); 117205100Sdelphij testbyte(2); 118205100Sdelphij testbyte(3); 119187700Sdelphij#if (LONG_BIT >= 64) 120205100Sdelphij testbyte(4); 121205100Sdelphij testbyte(5); 122205100Sdelphij testbyte(6); 123205100Sdelphij testbyte(7); 124187700Sdelphij#endif 125205100Sdelphij } 126205099Sdelphij } 127187700Sdelphij 128187700Sdelphij /* NOTREACHED */ 129187707Sdelphij return (0); 1301573Srgrimes} 131