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 48ENTRY(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 */ 611: 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 */ 682: 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 */ 8620: 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 */ 10730: xorq %rax,%rax 108 ret 109END(memchr) 110