common/lib/libc/arch/x86_64/string/strchr.S

   1 /*      $NetBSD: strchr.S,v 1.6 2009/07/20 15:21:00 christos 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.6 2009/07/20 15:21:00 christos 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
  52 ENTRY(test_strchr)
  53 #else
  54 ENTRY(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 */
  66 1:
  67         movq    (%rdi),%rax     /* bytes to check (x) */
  68 2:
  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 */
  95 8:      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 */
 101 10:
 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 */
 108 11:     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! */
 113 20:
 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 */
 123 21:     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 */
 128 22:
 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
 136 #ifdef TEST_STRCHR
 137 /* Trivial version for bug-fixing above */
 138 ENTRY(strchr)
 139         movq    %rsi,%rdx
 140         movq    %rdi,%rsi
 141 1:
 142         lodsb
 143         cmp     %al,%dl
 144         je      2f
 145         test    %al,%al
 146         jne     1b
 147         xor     %eax,%eax
 148         ret
 149 2:      lea     -1(%rsi),%rax
 150         ret
 151 #endif
 152
 153 STRONG_ALIAS(index,strchr)