git.saurik.com Git - apple/xnu.git/blame_incremental - libsyscall/wrappers/string/strlen.c

... / ...

Commit	Line	Data
	1	/*-
	2	* Copyright (c) 2009 Xin LI <delphij@FreeBSD.org>
	3	* All rights reserved.
	4	*
	5	* Redistribution and use in source and binary forms, with or without
	6	* modification, are permitted provided that the following conditions
	7	* are met:
	8	* 1. Redistributions of source code must retain the above copyright
	9	* notice, this list of conditions and the following disclaimer.
	10	* 2. Redistributions in binary form must reproduce the above copyright
	11	* notice, this list of conditions and the following disclaimer in the
	12	* documentation and/or other materials provided with the distribution.
	13	*
	14	* THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ``AS IS'' AND
	15	* ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
	16	* IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
	17	* ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
	18	* FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
	19	* DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
	20	* OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
	21	* HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
	22	* LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
	23	* OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
	24	* SUCH DAMAGE.
	25	*/
	26
	27	#include "string.h"
	28	#include <limits.h>
	29
	30	/*
	31	* Portable strlen() for 32-bit and 64-bit systems.
	32	*
	33	* Rationale: it is generally much more efficient to do word length
	34	* operations and avoid branches on modern computer systems, as
	35	* compared to byte-length operations with a lot of branches.
	36	*
	37	* The expression:
	38	*
	39	* ((x - 0x01....01) & ~x & 0x80....80)
	40	*
	41	* would evaluate to a non-zero value iff any of the bytes in the
	42	* original word is zero. However, we can further reduce ~1/3 of
	43	* time if we consider that strlen() usually operate on 7-bit ASCII
	44	* by employing the following expression, which allows false positive
	45	* when high bit of 1 and use the tail case to catch these case:
	46	*
	47	* ((x - 0x01....01) & 0x80....80)
	48	*
	49	* This is more than 5.2 times as fast as the raw implementation on
	50	* Intel T7300 under long mode for strings longer than word length.
	51	*/
	52
	53	/* Magic numbers for the algorithm */
	54	#if LONG_BIT == 32
	55	static const unsigned long mask01 = 0x01010101;
	56	static const unsigned long mask80 = 0x80808080;
	57	#elif LONG_BIT == 64
	58	static const unsigned long mask01 = 0x0101010101010101;
	59	static const unsigned long mask80 = 0x8080808080808080;
	60	#else
	61	#error Unsupported word size
	62	#endif
	63
	64	#define LONGPTR_MASK (sizeof(long) - 1)
	65
	66	/*
	67	* Helper macro to return string length if we caught the zero
	68	* byte.
	69	*/
	70	#define testbyte(x) \
	71	do { \
	72	if (p[x] == '\0') \
	73	return (p - str + x); \
	74	} while (0)
	75
	76	__attribute__((visibility("hidden")))
	77	size_t
	78	_libkernel_strlen(const char *str)
	79	{
	80	const char *p;
	81	const unsigned long *lp;
	82
	83	/* Skip the first few bytes until we have an aligned p */
	84	for (p = str; (uintptr_t)p & LONGPTR_MASK; p++) {
	85	if (*p == '\0') {
	86	return p - str;
	87	}
	88	}
	89
	90	/* Scan the rest of the string using word sized operation */
	91	for (lp = (const unsigned long *)p;; lp++) {
	92	if ((*lp - mask01) & mask80) {
	93	p = (const char *)(lp);
	94	testbyte(0);
	95	testbyte(1);
	96	testbyte(2);
	97	testbyte(3);
	98	#if (LONG_BIT >= 64)
	99	testbyte(4);
	100	testbyte(5);
	101	testbyte(6);
	102	testbyte(7);
	103	#endif
	104	}
	105	}
	106
	107	/* NOTREACHED */
	108	return 0;
	109	}