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 37 WEAK_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 46 ENTRY(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 */ 59 1: 60 movq (%rdi),%rax /* bytes to check (x) */ 61 2: 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 */ 88 8: 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 */ 94 10: 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 */ 101 11: xor %eax,%eax /* char not found */ 102 12: 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! */ 108 20: 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 */ 118 21: 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 */ 123 22: 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 130 END_STRONG(strchr) 131