1/* $OpenBSD: strchr.S,v 1.8 2015/11/14 21:53:03 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 "DEFS.h" 36 37WEAK_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 movabsq $0x0101010101010101,%r8 48 49 movzbq %sil,%rdx /* value to search for (c) */ 50 /* These imul are 'directpath' on athlons, so are fast */ 51 imul $0x80,%r8,%r9 /* 0x8080808080808080 */ 52 imul %r8,%rdx /* (c) copied to all bytes */ 53 test $7,%dil 54 jnz 20f /* jump if misaligned */ 55 56 _ALIGN_TEXT /* one byte nop */ 571: 58 movq (%rdi),%rax /* bytes to check (x) */ 592: 60 addq $8,%rdi 61 mov %rax,%r10 62 mov %rax,%r11 /* for 'char' check */ 63 not %r10 /* invert of data (~x) */ 64 65 xorq %rdx,%r11 /* convert 'char' test to one for NUL */ 66 subq %r8,%rax /* x - 0x10 */ 67 movq %r10,%rsi /* ~x */ 68 subq %r8,%r11 /* (x ^ c) - 0x10 */ 69/* 70 * Here we could check ((x - 0x10) | ((x ^ c) - 0x10)) & 0x80 71 * and short-circuit the case where no top bits are set, and 72 * we continue the loop. 73 * However it needs 3 more clocks that are difficult to interleave 74 * in the existing dependency chain ... 75 */ 76 andq %r9,%rax /* (x - 0x10) & 0x80 */ 77 xorq %rdx,%rsi /* c ^ ~x == ~(c ^ x) */ 78 andq %r9,%r11 /* ((x ^ c) - 0x10) & 0x80 */ 79 andq %r10,%rax /* (x - 0x10) & 0x80 & ~x */ 80 jne 10f /* jump if string ends */ 81 andq %rsi,%r11 /* ((x ^ c) - 0x10) & 0x80 & ~(x ^ c) */ 82 je 1b /* jump if no match */ 83 84 /* Found char, since LE can use bit scan */ 85 bsf %r11,%r11 /* 7, 15, 23 ... 63 */ 868: shr $3,%r11 /* 0, 1, 2 .. 7 */ 87 lea -8(%r11,%rdi),%rax 88 ret 89 90/* End of string, check whether char is before NUL */ 91 _ALIGN_TEXT /* adds three byte nop */ 9210: 93 bsf %rax,%rax /* count to NUL */ 94 andq %rsi,%r11 /* check for char in last 8 bytes */ 95 je 11f 96 bsf %r11,%r11 /* NUL and char - see which was first */ 97 cmp %r11,%rax 98 jae 8b /* return 'found' if same - searching for NUL */ 9911: xor %eax,%eax /* char not found */ 100 ret 101 102/* Source misaligned: read aligned word and make low bytes invalid */ 103/* I (dsl) think a _ALIGN_TEXT here will slow things down! */ 10420: 105 xor %rcx,%rcx 106 sub %dil,%cl /* Convert low address values 1..7 ... */ 107 sbb %rsi,%rsi /* carry was set, so %rsi now ~0u! */ 108 and $7,%cl /* ... to 7..1 */ 109 and $~7,%dil /* move address to start of word */ 110 shl $3,%cl /* now 56, 48 ... 16, 8 */ 111 movq (%rdi),%rax /* aligned word containing first data */ 112 xor %rdx,%rsi /* invert of search pattern (~c) */ 113 je 22f /* searching for 0xff */ 11421: shr %cl,%rsi /* ~c in low bytes */ 115 or %rsi,%rax /* set some bits making low bytes invalid */ 116 jmp 2b 117 118/* We are searching for 0xff, so can't use ~pattern for invalid value */ 11922: 120 mov %r8,%r10 /* 0x01 pattern */ 121 lea (%r8,%r8),%rsi /* 0x02 - bits gets set (above) */ 122 not %r10 /* now 0xfe */ 123 sar %cl,%r10 /* top bytes 0xff */ 124 and %r10,%rax /* clear lsb from unwanted low bytes */ 125 jmp 21b 126END_STRONG(strchr) 127