11541Srgrimes/*- 2243809Sdelphij * Copyright (c) 2009, 2010 Xin LI <delphij@FreeBSD.org> 3243809Sdelphij * All rights reserved. 41541Srgrimes * 51541Srgrimes * Redistribution and use in source and binary forms, with or without 61541Srgrimes * modification, are permitted provided that the following conditions 71541Srgrimes * are met: 81541Srgrimes * 1. Redistributions of source code must retain the above copyright 91541Srgrimes * notice, this list of conditions and the following disclaimer. 101541Srgrimes * 2. Redistributions in binary form must reproduce the above copyright 111541Srgrimes * notice, this list of conditions and the following disclaimer in the 121541Srgrimes * documentation and/or other materials provided with the distribution. 131541Srgrimes * 14243809Sdelphij * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND 151541Srgrimes * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 161541Srgrimes * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 17243809Sdelphij * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE 181541Srgrimes * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 191541Srgrimes * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS 201541Srgrimes * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) 211541Srgrimes * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT 221541Srgrimes * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY 231541Srgrimes * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 241541Srgrimes * SUCH DAMAGE. 251541Srgrimes */ 261541Srgrimes 27116189Sobrien#include <sys/cdefs.h> 28116189Sobrien__FBSDID("$FreeBSD$"); 29116189Sobrien 30102281Sjhb#include <sys/libkern.h> 31243809Sdelphij#include <sys/limits.h> 321541Srgrimes 33243809Sdelphij/* 34243809Sdelphij * Portable strlen() for 32-bit and 64-bit systems. 35243809Sdelphij * 36243809Sdelphij * Rationale: it is generally much more efficient to do word length 37243809Sdelphij * operations and avoid branches on modern computer systems, as 38243809Sdelphij * compared to byte-length operations with a lot of branches. 39243809Sdelphij * 40243809Sdelphij * The expression: 41243809Sdelphij * 42243809Sdelphij * ((x - 0x01....01) & ~x & 0x80....80) 43243809Sdelphij * 44243809Sdelphij * would evaluate to a non-zero value iff any of the bytes in the 45243809Sdelphij * original word is zero. 46243809Sdelphij * 47243809Sdelphij * On multi-issue processors, we can divide the above expression into: 48243809Sdelphij * a) (x - 0x01....01) 49243809Sdelphij * b) (~x & 0x80....80) 50243809Sdelphij * c) a & b 51243809Sdelphij * 52243809Sdelphij * Where, a) and b) can be partially computed in parallel. 53243809Sdelphij * 54243809Sdelphij * The algorithm above is found on "Hacker's Delight" by 55243809Sdelphij * Henry S. Warren, Jr. 56243809Sdelphij */ 57243809Sdelphij 58243809Sdelphij/* Magic numbers for the algorithm */ 59243809Sdelphij#if LONG_BIT == 32 60243809Sdelphijstatic const unsigned long mask01 = 0x01010101; 61243809Sdelphijstatic const unsigned long mask80 = 0x80808080; 62243809Sdelphij#elif LONG_BIT == 64 63243809Sdelphijstatic const unsigned long mask01 = 0x0101010101010101; 64243809Sdelphijstatic const unsigned long mask80 = 0x8080808080808080; 65243809Sdelphij#else 66243809Sdelphij#error Unsupported word size 67243809Sdelphij#endif 68243809Sdelphij 69243809Sdelphij#define LONGPTR_MASK (sizeof(long) - 1) 70243809Sdelphij 71243809Sdelphij/* 72243809Sdelphij * Helper macro to return string length if we caught the zero 73243809Sdelphij * byte. 74243809Sdelphij */ 75243809Sdelphij#define testbyte(x) \ 76243809Sdelphij do { \ 77243809Sdelphij if (p[x] == '\0') \ 78243809Sdelphij return (p - str + x); \ 79243809Sdelphij } while (0) 80243809Sdelphij 811541Srgrimessize_t 82243809Sdelphijstrlen(const char *str) 831541Srgrimes{ 84243809Sdelphij const char *p; 85243809Sdelphij const unsigned long *lp; 86243809Sdelphij long va, vb; 871541Srgrimes 88243809Sdelphij /* 89243809Sdelphij * Before trying the hard (unaligned byte-by-byte access) way 90243809Sdelphij * to figure out whether there is a nul character, try to see 91243809Sdelphij * if there is a nul character is within this accessible word 92243809Sdelphij * first. 93243809Sdelphij * 94243809Sdelphij * p and (p & ~LONGPTR_MASK) must be equally accessible since 95243809Sdelphij * they always fall in the same memory page, as long as page 96243809Sdelphij * boundaries is integral multiple of word size. 97243809Sdelphij */ 98243809Sdelphij lp = (const unsigned long *)((uintptr_t)str & ~LONGPTR_MASK); 99243809Sdelphij va = (*lp - mask01); 100243809Sdelphij vb = ((~*lp) & mask80); 101243809Sdelphij lp++; 102243809Sdelphij if (va & vb) 103243809Sdelphij /* Check if we have \0 in the first part */ 104243809Sdelphij for (p = str; p < (const char *)lp; p++) 105243809Sdelphij if (*p == '\0') 106243809Sdelphij return (p - str); 107243809Sdelphij 108243809Sdelphij /* Scan the rest of the string using word sized operation */ 109243809Sdelphij for (; ; lp++) { 110243809Sdelphij va = (*lp - mask01); 111243809Sdelphij vb = ((~*lp) & mask80); 112243809Sdelphij if (va & vb) { 113243809Sdelphij p = (const char *)(lp); 114243809Sdelphij testbyte(0); 115243809Sdelphij testbyte(1); 116243809Sdelphij testbyte(2); 117243809Sdelphij testbyte(3); 118243809Sdelphij#if (LONG_BIT >= 64) 119243809Sdelphij testbyte(4); 120243809Sdelphij testbyte(5); 121243809Sdelphij testbyte(6); 122243809Sdelphij testbyte(7); 123243809Sdelphij#endif 124243809Sdelphij } 125243809Sdelphij } 126243809Sdelphij 127243809Sdelphij /* NOTREACHED */ 128243809Sdelphij return (0); 1291541Srgrimes} 130