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