1/*	$OpenBSD: strchr.S,v 1.9 2018/07/03 23:14:05 mortimer Exp $	*/
2/*	$NetBSD: strchr.S,v 1.7 2014/03/22 19:16:34 jakllsch Exp $	*/
3
4/*-
5 * Copyright (c) 2009 The NetBSD Foundation, Inc.
6 * All rights reserved.
7 *
8 * This code is derived from software contributed to The NetBSD Foundation
9 * by David Laight.
10 *
11 * Redistribution and use in source and binary forms, with or without
12 * modification, are permitted provided that the following conditions
13 * are met:
14 * 1. Redistributions of source code must retain the above copyright
15 *    notice, this list of conditions and the following disclaimer.
16 * 2. Redistributions in binary form must reproduce the above copyright
17 *    notice, this list of conditions and the following disclaimer in the
18 *    documentation and/or other materials provided with the distribution.
19 *
20 * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS
21 * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
22 * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
23 * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS
24 * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
25 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
26 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
27 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
28 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
29 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
30 * POSSIBILITY OF SUCH DAMAGE.
31 */
32
33/* See comments in strlen.S about checking words for byte values */
34
35#include "DEFS.h"
36
37WEAK_ALIAS(index, strchr)
38
39/*
40 * On entry %rdi is the buffer and the low byte of %rsi (%sil) the
41 * character to search for.
42 *
43 * Registers %rdx, %rcx, %r8-%r11 and %rax are also usable
44 */
45
46ENTRY(strchr)
47	RETGUARD_SETUP(strchr, r8)
48	RETGUARD_PUSH(r8)
49	movabsq	$0x0101010101010101,%r8
50
51	movzbq	%sil,%rdx	/* value to search for (c) */
52	/* These imul are 'directpath' on athlons, so are fast */
53	imul	$0x80,%r8,%r9	/* 0x8080808080808080 */
54	imul	%r8,%rdx	/* (c) copied to all bytes */
55	test	$7,%dil
56	jnz	20f		/* jump if misaligned */
57
58	_ALIGN_TEXT		/* one byte nop */
591:
60	movq	(%rdi),%rax	/* bytes to check (x) */
612:
62	addq	$8,%rdi
63	mov	%rax,%r10
64	mov	%rax,%r11	/* for 'char' check */
65	not	%r10		/* invert of data (~x) */
66
67	xorq	%rdx,%r11	/* convert 'char' test to one for NUL */
68	subq	%r8,%rax	/* x - 0x10 */
69	movq	%r10,%rsi	/* ~x */
70	subq	%r8,%r11	/* (x ^ c) - 0x10 */
71/*
72 * Here we could check ((x - 0x10) | ((x ^ c) - 0x10)) & 0x80
73 * and short-circuit the case where no top bits are set, and
74 * we continue the loop.
75 * However it needs 3 more clocks that are difficult to interleave
76 * in the existing dependency chain ...
77 */
78	andq	%r9,%rax	/* (x - 0x10) & 0x80 */
79	xorq	%rdx,%rsi	/* c ^ ~x == ~(c ^ x) */
80	andq	%r9,%r11	/* ((x ^ c) - 0x10) & 0x80 */
81	andq	%r10,%rax	/* (x - 0x10) & 0x80 & ~x */
82	jne	10f		/* jump if string ends */
83	andq	%rsi,%r11	/* ((x ^ c) - 0x10) & 0x80 & ~(x ^ c) */
84	je	1b		/* jump if no match */
85
86	/* Found char, since LE can use bit scan */
87	bsf	%r11,%r11	/* 7, 15, 23 ... 63 */
888:	shr	$3,%r11		/* 0, 1, 2 .. 7 */
89	lea	-8(%r11,%rdi),%rax
90	jmp 12f
91
92/* End of string, check whether char is before NUL */
93	_ALIGN_TEXT		/* adds three byte nop */
9410:
95	bsf	%rax,%rax	/* count to NUL */
96	andq	%rsi,%r11	/* check for char in last 8 bytes */
97	je	11f
98	bsf	%r11,%r11	/* NUL and char - see which was first */
99	cmp	%r11,%rax
100	jae	8b		/* return 'found' if same - searching for NUL */
10111:	xor	%eax,%eax	/* char not found */
10212:	RETGUARD_POP(r11)
103	RETGUARD_CHECK(strchr, r11)
104	ret
105
106/* Source misaligned: read aligned word and make low bytes invalid */
107/* I (dsl) think a _ALIGN_TEXT here will slow things down! */
10820:
109	xor	%rcx,%rcx
110	sub	%dil,%cl	/* Convert low address values 1..7 ... */
111	sbb	%rsi,%rsi	/* carry was set, so %rsi now ~0u! */
112	and	$7,%cl		/* ... to 7..1 */
113	and	$~7,%dil	/* move address to start of word */
114	shl	$3,%cl		/* now 56, 48 ... 16, 8 */
115	movq	(%rdi),%rax	/* aligned word containing first data */
116	xor	%rdx,%rsi	/* invert of search pattern (~c) */
117	je	22f		/* searching for 0xff */
11821:	shr	%cl,%rsi	/* ~c in low bytes */
119	or	%rsi,%rax	/* set some bits making low bytes invalid */
120	jmp	2b
121
122/* We are searching for 0xff, so can't use ~pattern for invalid value */
12322:
124	mov	%r8,%r10	/* 0x01 pattern */
125	lea	(%r8,%r8),%rsi	/* 0x02 - bits gets set (above) */
126	not	%r10		/* now 0xfe */
127	sar	%cl,%r10	/* top bytes 0xff */
128	and	%r10,%rax	/* clear lsb from unwanted low bytes */
129	jmp	21b
130END_STRONG(strchr)
131