aboutsummaryrefslogtreecommitdiff
path: root/lib/libc/amd64/string/strcspn.S
blob: 7ebd7a847d67174e33760baebbc4bd6aef95fa11 (plain) (blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
/*
 * Copyright (c) 2023 The FreeBSD Foundation
 *
 * This software was developed by Robert Clausecker <fuz@FreeBSD.org>
 * under sponsorship from the FreeBSD Foundation.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in the
 *    documentation and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE AUTHOR AND CONTRIBUTORS ''AS IS'' AND
 * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE AUTHOR OR CONTRIBUTORS BE LIABLE
 * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
 * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
 * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
 * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
 * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
 * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE
 */

#include <machine/asm.h>
#include <machine/param.h>

#include "amd64_archlevel.h"

#define ALIGN_TEXT	.p2align 4,0x90 /* 16-byte alignment, nop filled */

	.weak strcspn
	.set strcspn, __strcspn
ARCHFUNCS(__strcspn)
	ARCHFUNC(__strcspn, scalar)
	NOARCHFUNC
	ARCHFUNC(__strcspn, x86_64_v2)
ENDARCHFUNCS(__strcspn)

ARCHENTRY(__strcspn, scalar)
	push	%rbp			# align stack to enable function call
	mov	%rsp, %rbp
	sub	$256, %rsp		# allocate space for lookup table

	/* check for special cases */
	movzbl	(%rsi), %eax		# first character in the set
	test	%eax, %eax
	jz	.Lstrlen

	movzbl	1(%rsi), %edx		# second character in the set
	test	%edx, %edx
	jz	.Lstrchr

	/* no special case matches -- prepare lookup table */
	xor	%r8d, %r8d
	mov	$28, %ecx
0:	mov	%r8, (%rsp, %rcx, 8)
	mov	%r8, 8(%rsp, %rcx, 8)
	mov	%r8, 16(%rsp, %rcx, 8)
	mov	%r8, 24(%rsp, %rcx, 8)
	sub	$4, %ecx
	jnc	0b

	add	$2, %rsi
	movb	$1, (%rsp, %rax, 1)	# register first chars in set
	movb	$1, (%rsp, %rdx, 1)
	mov	%rdi, %rax		# a copy of the source to iterate over

	/* process remaining chars in set */
	ALIGN_TEXT
0:	movzbl	(%rsi), %ecx
	movb	$1, (%rsp, %rcx, 1)
	test	%ecx, %ecx
	jz	1f

	movzbl	1(%rsi), %ecx
	movb	$1, (%rsp, %rcx, 1)
	test	%ecx, %ecx
	jz	1f

	add	$2, %rsi
	jmp	0b

	/* find match */
	ALIGN_TEXT
1:	movzbl	(%rax), %ecx
	cmpb	$0, (%rsp, %rcx, 1)
	jne	2f

	movzbl	1(%rax), %ecx
	cmpb	$0, (%rsp, %rcx, 1)
	jne	3f

	movzbl	2(%rax), %ecx
	cmpb	$0, (%rsp, %rcx, 1)
	jne	4f

	movzbl	3(%rax), %ecx
	add	$4, %rax
	cmpb	$0, (%rsp, %rcx, 1)
	je	1b

	sub	$3, %rax
4:	dec	%rdi
3:	inc	%rax
2:	sub	%rdi, %rax		# number of characters preceding match
	leave
	ret

	/* set is empty, degrades to strlen */
.Lstrlen:
	leave
	jmp	CNAME(strlen)

	/* just one character in set, degrades to strchr */
.Lstrchr:
	mov	%rdi, (%rsp)		# stash a copy of the string
	mov	%eax, %esi		# find the character in the set
	call	CNAME(strchrnul)
	sub	(%rsp), %rax		# length of prefix before match
	leave
	ret
ARCHEND(__strcspn, scalar)

	/*
	 * This kernel uses pcmpistri to do the heavy lifting.
	 * We provide five code paths, depending on set size:
	 *
	 *      0: call strlen()
	 *      1: call strchr()
	 *  2--16: one pcmpistri per 16 bytes of input
	 * 17--32: two pcmpistri per 16 bytes of input
	 *   >=33: fall back to look up table
	 */
ARCHENTRY(__strcspn, x86_64_v2)
	push		%rbp
	mov		%rsp, %rbp
	sub		$256, %rsp

	/* check for special cases */
	movzbl		(%rsi), %eax
	test		%eax, %eax		# empty string?
	jz		.Lstrlenv2

	cmpb		$0, 1(%rsi)		# single character string?
	jz		.Lstrchrv2

	/* find set size and copy up to 32 bytes to (%rsp) */
	mov		%esi, %ecx
	and		$~0xf, %rsi		# align set pointer
	movdqa		(%rsi), %xmm0
	pxor		%xmm1, %xmm1
	and		$0xf, %ecx		# amount of bytes rsi is past alignment
	xor		%edx, %edx
	pcmpeqb		%xmm0, %xmm1		# end of string reached?
	movdqa		%xmm0, 32(%rsp)		# transfer head of set to stack
	pmovmskb	%xmm1, %eax
	shr		%cl, %eax		# clear out junk before string
	test		%eax, %eax		# end of set reached?
	jnz		0f

	movdqa		16(%rsi), %xmm0		# second chunk of the set
	mov		$16, %edx
	sub		%ecx, %edx		# length of set preceding xmm0
	pxor		%xmm1, %xmm1
	pcmpeqb		%xmm0, %xmm1
	movdqa		%xmm0, 48(%rsp)
	movdqu		32(%rsp, %rcx, 1), %xmm2 # head of set
	pmovmskb	%xmm1, %eax
	test		%eax, %eax
	jnz		1f

	movdqa		32(%rsi), %xmm0		# third chunk
	add		$16, %edx
	pxor		%xmm1, %xmm1
	pcmpeqb		%xmm0, %xmm1
	movdqa		%xmm0, 64(%rsp)
	pmovmskb	%xmm1, %eax
	test		%eax, %eax		# still not done?
	jz		.Lgt32v2

0:	movdqu		32(%rsp, %rcx, 1), %xmm2 # head of set
1:	tzcnt		%eax, %eax
	add		%eax, %edx		# length of set (excluding NUL byte)
	cmp		$32, %edx		# above 32 bytes?
	ja		.Lgt32v2

	/*
	 * At this point we know that we want to use pcmpistri.
	 * one last problem obtains: the head of the string is not
	 * aligned and may cross a cacheline.  If this is the case,
	 * we take the part before the page boundary and repeat the
	 * last byte to fill up the xmm register.
	 */
	mov		%rdi, %rax		# save original string pointer
	lea		15(%rdi), %esi		# last byte of the head
	xor		%edi, %esi
	test		$PAGE_SIZE, %esi	# does the head cross a page?
	jz		0f

	/* head crosses page: copy to stack to fix up */
	and		$~0xf, %rax		# align head pointer temporarily
	movzbl		15(%rax), %esi		# last head byte on the page
	movdqa		(%rax), %xmm0
	movabs		$0x0101010101010101, %r8
	imul		%r8, %rsi		# repeated 8 times
	movdqa		%xmm0, (%rsp)		# head word on stack
	mov		%rsi, 16(%rsp)		# followed by filler (last byte x8)
	mov		%rsi, 24(%rsp)
	mov		%edi, %eax
	and		$0xf, %eax		# offset of head from alignment
	add		%rsp, %rax		# pointer to fake head

0:	movdqu		(%rax), %xmm0		# load head (fake or real)
	lea		16(%rdi), %rax
	and		$~0xf, %rax		# second 16 bytes of string (aligned)
1:	cmp		$16, %edx		# 16--32 bytes?
	ja		.Lgt16v2


	/* set is 2--16 bytes in size */

	/* _SIDD_UBYTE_OPS|_SIDD_CMP_EQUAL_ANY|_SIDD_LEAST_SIGNIFICANT */
	pcmpistri	$0, %xmm0, %xmm2	# match in head?
	jbe		.Lheadmatchv2

	ALIGN_TEXT
0:	pcmpistri	$0, (%rax), %xmm2
	jbe		1f			# match or end of string?
	pcmpistri	$0, 16(%rax), %xmm2
	lea		32(%rax), %rax
	ja		0b			# match or end of string?

3:	lea		-16(%rax), %rax		# go back to second half
1:	jc		2f			# jump if match found
	movdqa		(%rax), %xmm0		# reload string piece
	pxor		%xmm1, %xmm1
	pcmpeqb		%xmm1, %xmm0		# where is the NUL byte?
	pmovmskb	%xmm0, %ecx
	tzcnt		%ecx, %ecx		# location of NUL byte in (%rax)
2:	sub		%rdi, %rax		# offset of %xmm0 from beginning of string
	add		%rcx, %rax		# prefix length before match/NUL
	leave
	ret

.Lheadmatchv2:
	jc		2f			# jump if match found
	pxor		%xmm1, %xmm1
	pcmpeqb		%xmm1, %xmm0
	pmovmskb	%xmm0, %ecx
	tzcnt		%ecx, %ecx		# location of NUL byte
2:	mov		%ecx, %eax		# prefix length before match/NUL
	leave
	ret

	/* match in first set half during head */
.Lheadmatchv2first:
	mov		%ecx, %eax
	pcmpistri	$0, %xmm0, %xmm3	# match in second set half?
	cmp		%ecx, %eax		# before the first half match?
	cmova		%ecx, %eax		# use the earlier match
	leave
	ret

.Lgt16v2:
	movdqu		48(%rsp, %rcx, 1), %xmm3 # second part of set

	/* set is 17--32 bytes in size */
	pcmpistri	$0, %xmm0, %xmm2	# match in first set half?
	jb		.Lheadmatchv2first
	pcmpistri	$0, %xmm0, %xmm3	# match in second set half or end of string?
	jbe		.Lheadmatchv2

	ALIGN_TEXT
0:	movdqa		(%rax), %xmm0
	pcmpistri	$0, %xmm0, %xmm2
	jb		4f			# match in first set half?
	pcmpistri	$0, %xmm0, %xmm3
	jbe		1f			# match in second set half or end of string?
	movdqa		16(%rax), %xmm0
	add		$32, %rax
	pcmpistri	$0, %xmm0, %xmm2
	jb		3f			# match in first set half?
	pcmpistri	$0, %xmm0, %xmm3
	ja		0b			# neither match in 2nd half nor string end?

	/* match in second half or NUL */
	lea		-16(%rax), %rax		# go back to second half
1:	jc		2f			# jump if match found
	pxor		%xmm1, %xmm1
	pcmpeqb		%xmm1, %xmm0		# where is the NUL byte?
	pmovmskb	%xmm0, %ecx
	tzcnt		%ecx, %ecx		# location of NUL byte in (%rax)
2:	sub		%rdi, %rax		# offset of %xmm0 from beginning of string
	add		%rcx, %rax		# prefix length before match/NUL
	leave
	ret

	/* match in first half */
3:	sub		$16, %rax		# go back to second half
4:	sub		%rdi, %rax		# offset of %xmm0 from beginning of string
	mov		%ecx, %edx
	pcmpistri	$0, %xmm0, %xmm3	# match in second set half?
	cmp		%ecx, %edx		# before the first half match?
	cmova		%ecx, %edx		# use the earlier match
	add		%rdx, %rax		# return full ofset
	leave
	ret

	/* set is empty, degrades to strlen */
.Lstrlenv2:
	leave
	jmp	CNAME(strlen)

	/* just one character in set, degrades to strchr */
.Lstrchrv2:
	mov	%rdi, (%rsp)		# stash a copy of the string
	mov	%eax, %esi		# find this character
	call	CNAME(strchrnul)
	sub	(%rsp), %rax		# length of prefix before match
	leave
	ret

	/* set is >=33 bytes in size */
.Lgt32v2:
	xorps	%xmm0, %xmm0
	mov	$256-64, %edx

	/* clear out look up table */
0:	movaps	%xmm0, (%rsp, %rdx, 1)
	movaps	%xmm0, 16(%rsp, %rdx, 1)
	movaps	%xmm0, 32(%rsp, %rdx, 1)
	movaps	%xmm0, 48(%rsp, %rdx, 1)
	sub	$64, %edx
	jnc	0b

	add	%rcx, %rsi		# restore string pointer
	mov	%rdi, %rax		# keep a copy of the string

	/* initialise look up table */
	ALIGN_TEXT
0:	movzbl	(%rsi), %ecx
	movb	$1, (%rsp, %rcx, 1)
	test	%ecx, %ecx
	jz	1f

	movzbl	1(%rsi), %ecx
	movb	$1, (%rsp, %rcx, 1)
	test	%ecx, %ecx
	jz	1f

	movzbl	2(%rsi), %ecx
	movb	$1, (%rsp, %rcx, 1)
	test	%ecx, %ecx
	jz	1f

	movzbl	3(%rsi), %ecx
	movb	$1, (%rsp, %rcx, 1)
	test	%ecx, %ecx
	jz	1f

	add	$4, %rsi
	jmp	0b

	/* find match */
	ALIGN_TEXT
1:	movzbl	(%rax), %ecx
	cmpb	$0, (%rsp, %rcx, 1)
	jne	2f

	movzbl	1(%rax), %ecx
	cmpb	$0, (%rsp, %rcx, 1)
	jne	3f

	movzbl	2(%rax), %ecx
	cmpb	$0, (%rsp, %rcx, 1)
	jne	4f

	movzbl	3(%rax), %ecx
	add	$4, %rax
	cmpb	$0, (%rsp, %rcx, 1)
	je	1b

	sub	$3, %rax
4:	dec	%rdi
3:	inc	%rax
2:	sub	%rdi, %rax		# number of characters preceding match
	leave
	ret
ARCHEND(__strcspn, x86_64_v2)

	.section .note.GNU-stack,"",%progbits