1/* $NetBSD: strlen.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/* 33 * Inspired by a version written by J.T. Conklin <jtc@acorntoolworks.com> 34 * (Only the long comment really remains his work!) 35 */ 36 37#include <machine/asm.h> 38 39#if defined(LIBC_SCCS) 40 RCSID("$NetBSD: strlen.S,v 1.6 2014/03/22 19:16:34 jakllsch Exp $") 41#endif 42 43/* 44 * There are many well known branch-free sequences which are used 45 * for determining whether a zero-byte is contained within a word. 46 * These sequences are generally much more efficent than loading 47 * and comparing each byte individually. 48 * 49 * The expression [1,2]: 50 * 51 * (1) ~(((x & 0x7f....7f) + 0x7f....7f) | (x | 0x7f....7f)) 52 * 53 * evaluates to a non-zero value if any of the bytes in the 54 * original word is zero. 55 * 56 * It also has the useful property that bytes in the result word 57 * that correspond to non-zero bytes in the original word have 58 * the value 0x00, while bytes corresponding to zero bytes have 59 * the value 0x80. This allows calculation of the first (and 60 * last) occurrence of a zero byte within the word (useful for C's 61 * str* primitives) by counting the number of leading (or 62 * trailing) zeros and dividing the result by 8. On machines 63 * without (or with slow) clz() / ctz() instructions, testing 64 * each byte in the result word for zero is necessary. 65 * 66 * This typically takes 4 instructions (5 on machines without 67 * "not-or") not including those needed to load the constant. 68 * 69 * 70 * The expression: 71 * 72 * (2) ((x - 0x01....01) & 0x80....80 & ~x) 73 * 74 * evaluates to a non-zero value if any of the bytes in the 75 * original word is zero. 76 * 77 * On little endian machines, the first byte in the result word 78 * that corresponds to a zero byte in the original byte is 0x80, 79 * so clz() can be used as above. On big endian machines, and 80 * little endian machines without (or with a slow) clz() insn, 81 * testing each byte in the original for zero is necessary. 82 * 83 * This typically takes 3 instructions (4 on machines without 84 * "and with complement") not including those needed to load 85 * constants. 86 * 87 * 88 * The expression: 89 * 90 * (3) ((x - 0x01....01) & 0x80....80) 91 * 92 * always evaluates to a non-zero value if any of the bytes in 93 * the original word is zero or has the top bit set. 94 * For strings that are likely to only contain 7-bit ascii these 95 * false positives will be rare. 96 * 97 * To account for possible false positives, each byte of the 98 * original word must be checked when the expression evaluates to 99 * a non-zero value. However, because it is simpler than those 100 * presented above, code that uses it will be faster as long as 101 * the rate of false positives is low. 102 * 103 * This is likely, because the the false positive can only occur 104 * if the most siginificant bit of a byte within the word is set. 105 * The expression will never fail for typical 7-bit ASCII strings. 106 * 107 * This typically takes 2 instructions not including those needed 108 * to load constants. 109 * 110 * 111 * [1] Henry S. Warren Jr., "Hacker's Delight", Addison-Westley 2003 112 * 113 * [2] International Business Machines, "The PowerPC Compiler Writer's 114 * Guide", Warthman Associates, 1996 115 */ 116 117#ifdef TEST_STRLEN 118ENTRY(test_strlen) 119#else 120ENTRY(strlen) 121#endif 122 movabsq $0x0101010101010101,%r8 123 124 test $7,%dil 125 movq %rdi,%rax /* Buffer, %rdi unchanged */ 126 movabsq $0x8080808080808080,%r9 127 jnz 10f /* Jump if misaligned */ 128 129 _ALIGN_TEXT 1301: 131 movq (%rax),%rdx /* get bytes to check */ 1322: 133 addq $8,%rax 134 mov %rdx,%rcx /* save for later check */ 135 subq %r8,%rdx /* alg (3) above first */ 136 not %rcx /* Invert of data */ 137 andq %r9,%rdx 138 je 1b /* jump if all 0x01-0x80 */ 139 140 /* Do check from alg (2) above - loops for 0x81..0xff bytes */ 141 andq %rcx,%rdx 142 je 1b 143 144 /* Since we are LE, use bit scan for first 0x80 byte */ 145 sub %rdi,%rax /* length to next word */ 146 bsf %rdx,%rdx /* 7, 15, 23 ... 63 */ 147 shr $3,%rdx /* 0, 1, 2 ... 7 */ 148 lea -8(%rax,%rdx),%rax 149 ret 150 151/* Misaligned, read aligned word and make low bytes non-zero */ 152 _ALIGN_TEXT 15310: 154 mov %al,%cl 155 mov $1,%rsi 156 and $7,%cl /* offset into word 1..7 */ 157 and $~7,%al /* start of word with buffer */ 158 shl $3,%cl /* bit count 8, 16 .. 56 */ 159 movq (%rax),%rdx /* first data in high bytes */ 160 shl %cl,%rsi 161 dec %rsi 162 or %rsi,%rdx /* low bytes now non-zero */ 163 jmp 2b 164#ifdef TEST_STRLEN 165END(test_strlen) 166#else 167END(strlen) 168#endif 169 170#ifdef TEST_STRLEN 171/* trivial implementation when testing above! */ 172ENTRY(strlen) 173 mov %rdi,%rax 1741: 175 cmpb $0,(%rax) 176 jz 2f 177 inc %rax 178 jmp 1b 1792: sub %rdi,%rax 180 ret 181END(strlen) 182#endif 183