common/lib/libc/arch/x86_64/string/strlen.S

   1 /*      $NetBSD: strlen.S,v 1.5 2009/07/12 21:24:21 dsl 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.5 2009/07/12 21:24:21 dsl 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
 118 ENTRY(test_strlen)
 119 #else
 120 ENTRY(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
 130 1:
 131         movq    (%rax),%rdx             /* get bytes to check */
 132 2:
 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
 153 10:
 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
 165 #ifdef TEST_STRLEN
 166 /* trivial implementation when testing above! */
 167 ENTRY(strlen)
 168         mov     %rdi,%rax
 169 1:
 170         cmpb    $0,(%rax)
 171         jz      2f
 172         inc     %rax
 173         jmp     1b
 174 2:      sub     %rdi,%rax
 175         ret
 176 #endif