1/* $NetBSD: memchr.S,v 1.4 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#include <machine/asm.h> 33 34#if defined(LIBC_SCCS) 35 RCSID("$NetBSD: memchr.S,v 1.4 2009/07/20 15:21:00 christos 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 */ 662: 67 addq $8,%rdi 68 xorq %rsi,%rax /* now looking for zeros */ 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 kill low bits */ 86/* (Getting a -1 is surprisingly hard work!) */ 8720: 88 xor %eax,%eax /* zeros all 64 bits */ 89 mov %dil,%cl /* misalignment amount 1..7 (+high bits )*/ 90 test %rdx,%rdx /* zero length, don't read */ 91 jz 30f 92 93 and $~7,%dil /* %rdi now start of word */ 94 lea -1(%rax),%r11 /* all 0xff */ 95 and $7,%cl /* 1..7 */ 96 97 mov (%rdi),%rax /* word containing first byte */ 98 shl $3,%cl /* 8..56 */ 99 cmp %r11,%rsi /* searching for 0xff */ 100 jz 25f 101 102 /* Searching for other than 0xff, set low bytes */ 103 shl %cl,%r11 /* 0xff in high (wanted) bytes */ 104 not %r11 /* 0xff in low (unwanted) bytes */ 105 or %r11,%rax /* low bytes now set */ 106 jmp 2b 107 10825: /* Searching for 0xff, clear low bytes */ 109 shl %cl,%r11 /* 0xff in high (wanted) bytes */ 110 and %r11,%rax /* low bytes now zero */ 111 jmp 2b 112 113/* Not found */ 11430: xorq %rax,%rax 115 ret 116