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