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