memchr.S revision 1.2
1 1.2 dsl /* $NetBSD: memchr.S,v 1.2 2009/07/18 18:06:56 dsl Exp $ */ 2 1.2 dsl 3 1.2 dsl /*- 4 1.2 dsl * Copyright (c) 2009 The NetBSD Foundation, Inc. 5 1.2 dsl * All rights reserved. 6 1.2 dsl * 7 1.2 dsl * This code is derived from software contributed to The NetBSD Foundation 8 1.2 dsl * by David Laight. 9 1.2 dsl * 10 1.2 dsl * Redistribution and use in source and binary forms, with or without 11 1.2 dsl * modification, are permitted provided that the following conditions 12 1.2 dsl * are met: 13 1.2 dsl * 1. Redistributions of source code must retain the above copyright 14 1.2 dsl * notice, this list of conditions and the following disclaimer. 15 1.2 dsl * 2. Redistributions in binary form must reproduce the above copyright 16 1.2 dsl * notice, this list of conditions and the following disclaimer in the 17 1.2 dsl * documentation and/or other materials provided with the distribution. 18 1.2 dsl * 19 1.2 dsl * THIS SOFTWARE IS PROVIDED BY THE NETBSD FOUNDATION, INC. AND CONTRIBUTORS 20 1.2 dsl * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED 21 1.2 dsl * TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 22 1.2 dsl * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE FOUNDATION OR CONTRIBUTORS 23 1.2 dsl * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 24 1.2 dsl * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 25 1.2 dsl * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 26 1.2 dsl * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 27 1.2 dsl * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 28 1.2 dsl * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 29 1.2 dsl * POSSIBILITY OF SUCH DAMAGE. 30 1.1 christos */ 31 1.1 christos 32 1.1 christos #include <machine/asm.h> 33 1.1 christos 34 1.1 christos #if defined(LIBC_SCCS) 35 1.2 dsl RCSID("$NetBSD: memchr.S,v 1.2 2009/07/18 18:06:56 dsl Exp $") 36 1.1 christos #endif 37 1.1 christos 38 1.2 dsl /* 39 1.2 dsl * The instruction sequences used try to avoid data dependencies 40 1.2 dsl * between adjacent instructions (to allow parallel execution). 41 1.2 dsl * The 'imul' for %r9 could be put into the delay following the 42 1.2 dsl * memory read (ie inside the loop) at no obvious cost - except 43 1.2 dsl * that the loop is currently exactly 32 bytes - 2 fetch blocks!. 44 1.2 dsl * 45 1.2 dsl * I don't think aligning any of the other branch targets is useful. 46 1.2 dsl */ 47 1.2 dsl 48 1.1 christos ENTRY(memchr) 49 1.2 dsl movabsq $0x0101010101010101,%r8 50 1.2 dsl lea (%rdi,%rdx),%r10 /* limit of buffer to scan */ 51 1.2 dsl movzbq %sil,%rsi /* mask high bits! */ 52 1.1 christos 53 1.2 dsl /* 'directpath' imuls can execute 3 at a time ... (amd) */ 54 1.2 dsl imul %r8,%rsi /* search byte replicated in word */ 55 1.2 dsl imul $0x80,%r8,%r9 /* 0x8080808080808080 */ 56 1.2 dsl test $7,%dil 57 1.2 dsl jnz 20f /* jump if misaligned */ 58 1.2 dsl jmp 1f /* jump to avoid 4 nops (13 bytes) in gap */ 59 1.2 dsl 60 1.2 dsl _ALIGN_TEXT /* entire loop now in 32 aligned bytes */ 61 1.2 dsl 1: 62 1.2 dsl cmpq %r10,%rdi /* end of buffer ? */ 63 1.2 dsl jae 30f /* jump if so */ 64 1.1 christos 65 1.2 dsl movq (%rdi),%rax /* value to check */ 66 1.2 dsl 2: 67 1.1 christos addq $8,%rdi 68 1.2 dsl xorq %rsi,%rax /* now looking for zeros */ 69 1.2 dsl mov %rax,%rcx 70 1.2 dsl subq %r8,%rax /* x - 0x10 */ 71 1.2 dsl not %rcx 72 1.2 dsl andq %r9,%rax /* (x - 0x10) & 0x80 */ 73 1.2 dsl andq %rcx,%rax /* ((x - 0x10) & 0x80) ^ ~x */ 74 1.2 dsl je 1b /* jump if not found */ 75 1.2 dsl 76 1.2 dsl /* Found byte in word, get its address */ 77 1.2 dsl bsf %rax,%rax 78 1.2 dsl shr $3,%eax 79 1.2 dsl lea -8(%rax,%rdi),%rax 80 1.2 dsl cmpq %r10,%rax /* need to check not beyond buffer */ 81 1.2 dsl jae 30f 82 1.2 dsl rep 83 1.2 dsl ret /* amd - no ret after jmp */ 84 1.2 dsl 85 1.2 dsl /* Input misaligned, read aligned and kill low bits */ 86 1.2 dsl /* (Getting a -1 is surprisingly hard work!) */ 87 1.2 dsl 20: 88 1.2 dsl xor %eax,%eax /* zeros all 64 bits */ 89 1.2 dsl mov %dil,%cl /* misalignment amount 1..7 (+high bits )*/ 90 1.2 dsl test %rdx,%rdx /* zero length, don't read */ 91 1.2 dsl jz 30f 92 1.2 dsl 93 1.2 dsl and $~7,%dil /* %rdi now start of word */ 94 1.2 dsl lea -1(%rax),%r11 /* all 0xff */ 95 1.2 dsl and $7,%cl /* 1..7 */ 96 1.2 dsl 97 1.2 dsl mov (%rdi),%rax /* word containing first byte */ 98 1.2 dsl shl $3,%cl /* 8..56 */ 99 1.2 dsl test %r11,%rsi /* searching for 0xff */ 100 1.2 dsl jz 25f 101 1.2 dsl 102 1.2 dsl /* Searching for other than 0xff, set low bytes */ 103 1.2 dsl shl %cl,%r11 /* 0xff in high (wanted) bytes */ 104 1.2 dsl not %r11 /* 0xff in low (unwanted) bytes */ 105 1.2 dsl or %r11,%rax /* low bytes now set */ 106 1.2 dsl jmp 2b 107 1.2 dsl 108 1.2 dsl 25: /* Searching for 0xff, clear low bytes */ 109 1.2 dsl shl %cl,%r11 /* 0xff in high (wanted) bytes */ 110 1.2 dsl and %r11,%rax /* low bytes now zero */ 111 1.2 dsl jmp 2b 112 1.1 christos 113 1.2 dsl /* Not found */ 114 1.2 dsl 30: xorq %rax,%rax 115 1.1 christos ret 116
Indexes created Thu Sep 25 16:09:42 GMT 2025