1/*
2 * Copyright (c) 2012 Apple Computer, Inc. All rights reserved.
3 *
4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
5 *
6 * This file contains Original Code and/or Modifications of Original Code
7 * as defined in and that are subject to the Apple Public Source License
8 * Version 2.0 (the 'License'). You may not use this file except in
9 * compliance with the License. The rights granted to you under the License
10 * may not be used to create, or enable the creation or redistribution of,
11 * unlawful or unlicensed copies of an Apple operating system, or to
12 * circumvent, violate, or enable the circumvention or violation of, any
13 * terms of an Apple operating system software license agreement.
14 *
15 * Please obtain a copy of the License at
16 * http://www.opensource.apple.com/apsl/ and read it before using this file.
17 *
18 * The Original Code and all software distributed under the License are
19 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
20 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
21 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
22 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
23 * Please see the License for the specific language governing rights and
24 * limitations under the License.
25 *
26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
27 *
28 * This file implements the following function for the arm64 architecture:
29 *
30 * size_t strnlen(const char *string, size_t maxlen);
31 *
32 * The strnlen function returns either strlen(string) or maxlen, whichever
33 * is amller, without reading beyond the first maxlen characters of string.
34 */
35
36#include <arm64/asm.h>
37
38.globl _strlen
39.globl _strnlen
40
41/*****************************************************************************
42 * Macros *
43 *****************************************************************************/
44
45.macro EstablishFrame
46 ARM64_STACK_PROLOG
47 stp fp, lr, [sp, #-16]!
48 mov fp, sp
49.endm
50
51.macro ClearFrameAndReturn
52 ldp fp, lr, [sp], #16
53 ARM64_STACK_EPILOG
54.endm
55
56/*****************************************************************************
57 * Constants *
58 *****************************************************************************/
59
60.text
61.align 5
62L_masks:
63.quad 0x0706050403020100, 0x0f0e0d0c0b0a0908
64.quad 0x0000000000000000, 0x0000000000000000
65
66/*****************************************************************************
67 * strnlen entrypoint *
68 *****************************************************************************/
69
70_strnlen:
71// If n == 0, return NULL without loading any data from s. If n is so large
72// that it exceeds the size of any buffer that can be allocted, jump into a
73// simpler implementation that omits all length checks. This is both faster
74// and lets us avoid some messy edgecases in the mainline.
75 tst x1, x1
76 b.mi _strlen
77 b.eq L_maxlenIsZero
78 EstablishFrame
79// Load the 16-byte aligned vector containing the start of the string.
80 and x2, x0, #-16
81 ldr q0, [x2]
82// Load a vector {0,1,2, ... ,15} for use in finding the index of the NUL
83// byte once we identify one. We don't use this vector until the very end
84// of the routine; it simply falls out naturally to load it now.
85 adr x3, L_masks
86 ldr q2, [x3],#16
87// The aligned vector that we loaded to q0 contains the start of the string,
88// but if the string was not originally aligned, it also contains bytes
89// which preceed the start of the string, and which may cause false positives
90// when we search for the terminating NUL. We generate a mask to OR into the
91// vector using an unaligned load to prevent this. The mask has non-zero
92// values only in those bytes which correspond to bytes preceeding the start
93// of the string in the aligned vector load.
94 and x4, x0, #0xf
95 sub x3, x3, x4
96 ldr q1, [x3]
97 orr.16b v0, v0, v1
98// Adjust maxlen to account for bytes which preceed the start of the string,
99// and jump into the main scanning loop.
100 add x1, x1, x4
101 b 1f
102
103// Main loop. Identical to strlen, except that we also need to check that we
104// don't read more than maxlen bytes. To that end, we decrement maxlen by 16
105// on each iteration, and exit the loop if the result is zero or negative.
106.align 4
1070: ldr q0, [x2, #16]!
1081: uminv.16b b1, v0
109 fmov w3, s1
110 cbz w3, L_foundNUL
111 subs x1, x1, #16
112 b.hi 0b
113
114// We exhausted maxlen bytes without finding a terminating NUL character, so
115// we need to return maxlen.
116 sub x0, x2, x0
117 add x1, x1, #16
118 add x0, x0, x1
119 ClearFrameAndReturn
120
121L_maxlenIsZero:
122 mov x0, #0
123 ret // No stack frame, so don't clear it.
124
125L_foundNUL:
126// Compute the index of the NUL byte, and check if it occurs before maxlen
127// bytes into the vector. If not, return maxlen. Otherwise, return the
128// length of the string.
129 eor.16b v1, v1, v1
130 cmhi.16b v0, v0, v1
131 orr.16b v0, v0, v2
132 uminv.16b b1, v0
133 fmov w3, s1 // index of NUL byte in vector
134 sub x0, x2, x0 // index of vector in string
135 cmp x1, x3 // if NUL occurs before maxlen bytes
136 csel x1, x1, x3, cc // return strlen, else maxlen
137 add x0, x0, x1
138 ClearFrameAndReturn
139
140/*****************************************************************************
141 * strlen entrypoint *
142 *****************************************************************************/
143
144.align 4
145_strlen:
146 EstablishFrame
147// Load the 16-byte aligned vector containing the start of the string.
148 and x1, x0, #-16
149 ldr q0, [x1]
150// Load a vector {0,1,2, ... ,15} for use in finding the index of the NUL
151// byte once we identify one. We don't use this vector until the very end
152// of the routine; it simply falls out naturally to load it now.
153 adr x3, L_masks
154 ldr q2, [x3],#16
155// The aligned vector that we loaded to q0 contains the start of the string,
156// but if the string was not originally aligned, it also contains bytes
157// which preceed the start of the string, and which may cause false positives
158// when we search for the terminating NUL. We generate a mask to OR into the
159// vector using an unaligned load to prevent this. The mask has non-zero
160// values only in those bytes which correspond to bytes preceeding the start
161// of the string in the aligned vector load.
162 and x2, x0, #0xf
163 sub x3, x3, x2
164 ldr q1, [x3]
165 orr.16b v0, v0, v1
166 b 1f
167
168// Main loop. On each iteration we do the following:
169//
170// q0 <-- next 16 aligned bytes of string
171// b1 <-- unsigned minimum byte in q0
172// if (b1 != 0) continue
173//
174// Thus, we continue the loop until the 16 bytes we load contain a zero byte.
175.align 4
1760: ldr q0, [x1, #16]!
1771: uminv.16b b1, v0
178 fmov w2, s1 // umov.b would be more natural, but requries 2 µops.
179 cbnz w2, 0b
180
181// A zero byte has been found. The following registers contain values that
182// we need to compute the string's length:
183//
184// x0 pointer to start of string
185// x1 pointer to vector containing terminating NUL byte
186// v0 vector containing terminating NUL byte
187// v2 {0, 1, 2, ... , 15}
188//
189// We compute the index of the terminating NUL byte in the string (which is
190// precisely the length of the string) as follows:
191//
192// vec <-- mask(v0 != 0) | v2
193// index <-- x1 - x0 + unsignedMinimum(vec)
194 eor.16b v1, v1, v1
195 cmhi.16b v0, v0, v1
196 orr.16b v0, v0, v2
197 uminv.16b b1, v0
198 fmov w2, s1
199 sub x0, x1, x0
200 add x0, x0, x2
201 ClearFrameAndReturn
202