1/* $OpenBSD: strchr.S,v 1.7 2022/12/07 19:26:39 guenther 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 <machine/asm.h> 36 37STRONG_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, r9) 48 RETGUARD_PUSH(r9) 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_TRAPS 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(r9) 103 RETGUARD_CHECK(strchr, r9) 104 ret 105 lfence 106 107/* Source misaligned: read aligned word and make low bytes invalid */ 108/* I (dsl) think aligning the text here will slow things down! */ 10920: 110 xor %rcx,%rcx 111 sub %dil,%cl /* Convert low address values 1..7 ... */ 112 sbb %rsi,%rsi /* carry was set, so %rsi now ~0u! */ 113 and $7,%cl /* ... to 7..1 */ 114 and $~7,%dil /* move address to start of word */ 115 shl $3,%cl /* now 56, 48 ... 16, 8 */ 116 movq (%rdi),%rax /* aligned word containing first data */ 117 xor %rdx,%rsi /* invert of search pattern (~c) */ 118 je 22f /* searching for 0xff */ 11921: shr %cl,%rsi /* ~c in low bytes */ 120 or %rsi,%rax /* set some bits making low bytes invalid */ 121 jmp 2b 122 123/* We are searching for 0xff, so can't use ~pattern for invalid value */ 12422: 125 mov %r8,%r10 /* 0x01 pattern */ 126 lea (%r8,%r8),%rsi /* 0x02 - bits gets set (above) */ 127 not %r10 /* now 0xfe */ 128 sar %cl,%r10 /* top bytes 0xff */ 129 and %r10,%rax /* clear lsb from unwanted low bytes */ 130 jmp 21b 131END(strchr) 132