1/*        $NetBSD: strlen.S,v 1.8 2024/03/30 22:03:39 andvar 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.8 2024/03/30 22:03:39 andvar 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 efficient 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-Wesley 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