Home | History | Annotate | Line # | Download | only in string 
      1 /*	$NetBSD: memchr.S,v 1.6 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 #include <machine/asm.h>
     33 
     34 #if defined(LIBC_SCCS)
     35 	RCSID("$NetBSD: memchr.S,v 1.6 2014/03/22 19:16:34 jakllsch Exp $")
     36 #endif
     37 
     38 /*
     39  * The instruction sequences used try to avoid data dependencies
     40  * between adjacent instructions (to allow parallel execution).
     41  * The 'imul' for %r9 could be put into the delay following the
     42  * memory read (ie inside the loop) at no obvious cost - except
     43  * that the loop is currently exactly 32 bytes - 2 fetch blocks!.
     44  *
     45  * I don't think aligning any of the other branch targets is useful.
     46  */
     47 
     48 ENTRY(memchr)
     49 	movabsq	$0x0101010101010101,%r8
     50 	lea	(%rdi,%rdx),%r10	/* limit of buffer to scan */
     51 	movzbq	%sil,%rsi	/* mask high bits! */
     52 
     53 	/* 'directpath' imuls can execute 3 at a time ... (amd) */
     54 	imul	%r8,%rsi	/* search byte replicated in word */
     55 	imul	$0x80,%r8,%r9	/* 0x8080808080808080 */
     56 	test	$7,%dil
     57 	jnz	20f		/* jump if misaligned */
     58 	jmp	1f		/* jump to avoid 4 nops (13 bytes) in gap */
     59 
     60 	_ALIGN_TEXT		/* entire loop now in 32 aligned bytes */
     61 1:
     62 	cmpq	%r10,%rdi	/* end of buffer ? */
     63 	jae	30f		/* jump if so */
     64 
     65 	movq	(%rdi),%rax	/* value to check */
     66 	addq	$8,%rdi
     67 	xorq	%rsi,%rax	/* now looking for zeros */
     68 2:
     69 	mov	%rax,%rcx
     70 	subq	%r8,%rax	/* x - 0x01 */
     71 	not	%rcx
     72 	andq	%r9,%rax	/* (x - 0x01) & 0x80 */
     73 	andq	%rcx,%rax	/* ((x - 0x01) & 0x80) & ~x */
     74 	je	1b		/* jump if not found */
     75 
     76 /* Found byte in word, get its address */
     77 	bsf	%rax,%rax
     78 	shr	$3,%eax
     79 	lea	-8(%rax,%rdi),%rax
     80 	cmpq	%r10,%rax	/* need to check not beyond buffer */
     81 	jae	30f
     82 	rep
     83 	ret			/* amd - no ret after jmp */
     84 
     85 /* Input misaligned, read aligned and make low bytes invalid */
     86 20:
     87 	mov	%dil,%cl	/* misalignment amount 1..7 (+high bits )*/
     88 	and	$~7,%dil	/* %rdi now start of word */
     89 	test	%rdx,%rdx	/* zero length, don't read */
     90 	jz	30f
     91 
     92 	neg	%cl		/* 7..1 (+high bits) */
     93 	mov	(%rdi),%rax	/* word containing first byte */
     94 	addq	$8,%rdi
     95 	and	$7,%cl		/* 7..1 */
     96 
     97 	mov	%r8,%r11	/* any value with bits in each byte */
     98 	shl	$3,%cl		/* 56..8 */
     99 	xorq	%rsi,%rax	/* now looking for zeros */
    100 
    101 	/* Set low bytes non-zero */
    102 	shr	%cl,%r11	/* non-zero in unwanted bytes */
    103 	or	%r11,%rax	/* low bytes now set */
    104 	jmp	2b
    105 
    106 /* Not found */
    107 30:	xorq	%rax,%rax
    108 	ret
    109 END(memchr)
    110