| blob | 6ac6572f3becf944e10bb3050eea9355b428143f |
1 /* Optimized strcasestr implementation for PowerPC64/POWER8.
2 Copyright (C) 2016-2017 Free Software Foundation, Inc.
3 This file is part of the GNU C Library.
5 The GNU C Library is free software; you can redistribute it and/or
6 modify it under the terms of the GNU Lesser General Public
7 License as published by the Free Software Foundation; either
8 version 2.1 of the License, or (at your option) any later version.
10 The GNU C Library is distributed in the hope that it will be useful,
11 but WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 Lesser General Public License for more details.
15 You should have received a copy of the GNU Lesser General Public
16 License along with the GNU C Library; if not, see
17 <http://www.gnu.org/licenses/>. */
19 #include <sysdep.h>
20 #include <locale-defines.h>
22 /* Char * [r3] strcasestr (char *s [r3], char * pat[r4]) */
24 /* The performance gain is obtained by comparing 16 bytes. */
26 /* When the first char of r4 is hit ITERATIONS times in r3
27 fallback to default. */
28 #define ITERATIONS 64
30 #ifndef STRCASESTR
31 # define STRCASESTR __strcasestr
32 #endif
34 #ifndef STRLEN
35 /* For builds without IFUNC support, local calls should be made to internal
36 GLIBC symbol (created by libc_hidden_builtin_def). */
37 # ifdef SHARED
38 # define STRLEN __GI_strlen
39 # else
40 # define STRLEN strlen
41 # endif
42 #endif
44 #ifndef STRNLEN
45 /* For builds without IFUNC support, local calls should be made to internal
46 GLIBC symbol (created by libc_hidden_builtin_def). */
47 # ifdef SHARED
48 # define STRNLEN __GI_strnlen
49 # else
50 # define STRNLEN __strnlen
51 # endif
52 #endif
54 #ifndef STRCHR
55 # ifdef SHARED
56 # define STRCHR __GI_strchr
57 # else
58 # define STRCHR strchr
59 # endif
60 #endif
62 /* Convert 16 bytes of v4 and reg to lowercase and compare. */
63 #define TOLOWER(reg) \
64 vcmpgtub v6, v4, v1; \
65 vcmpgtub v7, v2, v4; \
66 vand v8, v7, v6; \
67 vand v8, v8, v3; \
68 vor v4, v8, v4; \
69 vcmpgtub v6, reg, v1; \
70 vcmpgtub v7, v2, reg; \
71 vand v8, v7, v6; \
72 vand v8, v8, v3; \
73 vor reg, v8, reg; \
74 vcmpequb. v6, reg, v4;
76 /* TODO: change these to the actual instructions when the minimum required
77 binutils allows it. */
78 #ifdef _ARCH_PWR8
79 #define VCLZD_V8_v7 vclzd v8, v7;
80 #else
81 #define VCLZD_V8_v7 .long 0x11003fc2
82 #endif
84 #define FRAMESIZE (FRAME_MIN_SIZE+48)
85 /* TODO: change this to .machine power8 when the minimum required binutils
86 allows it. */
87 .machine power7
88 EALIGN (STRCASESTR, 4, 0)
89 CALL_MCOUNT 2
90 mflr r0 /* Load link register LR to r0. */
91 std r31, -8(r1) /* Save callers register r31. */
92 std r30, -16(r1) /* Save callers register r30. */
93 std r29, -24(r1) /* Save callers register r29. */
94 std r28, -32(r1) /* Save callers register r28. */
95 std r27, -40(r1) /* Save callers register r27. */
96 std r0, 16(r1) /* Store the link register. */
97 cfi_offset(r31, -8)
98 cfi_offset(r30, -16)
99 cfi_offset(r29, -24)
100 cfi_offset(r28, -32)
101 cfi_offset(r27, -40)
102 cfi_offset(lr, 16)
103 stdu r1, -FRAMESIZE(r1) /* Create the stack frame. */
104 cfi_adjust_cfa_offset(FRAMESIZE)
106 dcbt 0, r3
107 dcbt 0, r4
108 cmpdi cr7, r3, 0 /* Input validation. */
109 beq cr7, L(retnull)
110 cmpdi cr7, r4, 0
111 beq cr7, L(retnull)
113 mr r29, r3
114 mr r30, r4
115 /* Load first byte from r4 and check if its null. */
116 lbz r6, 0(r4)
117 cmpdi cr7, r6, 0
118 beq cr7, L(ret_r3)
120 ld r10, __libc_tsd_LOCALE@got@tprel(r2)
121 add r9, r10, __libc_tsd_LOCALE@tls
122 ld r9, 0(r9)
123 ld r9, LOCALE_CTYPE_TOUPPER(r9)
124 sldi r10, r6, 2 /* Convert to upper case. */
125 lwzx r28, r9, r10
127 ld r10, __libc_tsd_LOCALE@got@tprel(r2)
128 add r11, r10, __libc_tsd_LOCALE@tls
129 ld r11, 0(r11)
130 ld r11, LOCALE_CTYPE_TOLOWER(r11)
131 sldi r10, r6, 2 /* Convert to lower case. */
132 lwzx r27, r11, r10
134 /* Check if the first char is present. */
135 mr r4, r27
136 bl STRCHR
137 nop
138 mr r5, r3
139 mr r3, r29
140 mr r29, r5
141 mr r4, r28
142 bl STRCHR
143 nop
144 cmpdi cr7, r29, 0
145 beq cr7, L(firstpos)
146 cmpdi cr7, r3, 0
147 beq cr7, L(skipcheck)
148 cmpw cr7, r3, r29
149 ble cr7, L(firstpos)
150 /* Move r3 to the first occurence. */
151 L(skipcheck):
152 mr r3, r29
153 L(firstpos):
154 mr r29, r3
156 sldi r9, r27, 8
157 or r28, r9, r28
158 /* Reg r27 is used to count the number of iterations. */
159 li r27, 0
160 /* If first char of search str is not present. */
161 cmpdi cr7, r3, 0
162 ble cr7, L(end)
164 /* Find the length of pattern. */
165 mr r3, r30
166 bl STRLEN
167 nop
169 cmpdi cr7, r3, 0 /* If search str is null. */
170 beq cr7, L(ret_r3)
172 mr r31, r3
173 mr r4, r3
174 mr r3, r29
175 bl STRNLEN
176 nop
178 cmpd cr7, r3, r31 /* If len(r3) < len(r4). */
179 blt cr7, L(retnull)
181 mr r3, r29
183 /* Locales not matching ASCII for single bytes. */
184 ld r10, __libc_tsd_LOCALE@got@tprel(r2)
185 add r9, r10, __libc_tsd_LOCALE@tls
186 ld r9, 0(r9)
187 ld r7, 0(r9)
188 addi r7, r7, LOCALE_DATA_VALUES+_NL_CTYPE_NONASCII_CASE*SIZEOF_VALUES
189 lwz r8, 0(r7)
190 cmpdi cr7, r8, 1
191 beq cr7, L(bytebybyte)
193 /* If len(r4) < 16 handle byte by byte. */
194 /* For shorter strings we will not use vector registers. */
195 cmpdi cr7, r31, 16
196 blt cr7, L(bytebybyte)
198 /* Comparison values used for TOLOWER. */
199 /* Load v1 = 64('A' - 1), v2 = 91('Z' + 1), v3 = 32 in each byte. */
200 vspltish v0, 0
201 vspltisb v5, 2
202 vspltisb v4, 4
203 vsl v3, v5, v4
204 vaddubm v1, v3, v3
205 vspltisb v5, 15
206 vaddubm v2, v5, v5
207 vaddubm v2, v1, v2
208 vspltisb v4, -3
209 vaddubm v2, v2, v4
211 /*
212 1. Load 16 bytes from r3 and r4
213 2. Check if there is null, If yes, proceed byte by byte path.
214 3. Else,Convert both to lowercase and compare.
215 4. If they are same proceed to 1.
216 5. If they dont match, find if first char of r4 is present in the
217 loaded 16 byte of r3.
218 6. If yes, move position, load next 16 bytes of r3 and proceed to 2.
219 */
221 mr r8, r3 /* Save r3 for future use. */
222 mr r4, r30 /* Restore r4. */
223 clrldi r10, r4, 60
224 lvx v5, 0, r4 /* Load 16 bytes from r4. */
225 cmpdi cr7, r10, 0
226 beq cr7, L(begin2)
227 /* If r4 is unaligned, load another 16 bytes. */
228 #ifdef __LITTLE_ENDIAN__
229 lvsr v7, 0, r4
230 #else
231 lvsl v7, 0, r4
232 #endif
233 addi r5, r4, 16
234 lvx v9, 0, r5
235 #ifdef __LITTLE_ENDIAN__
236 vperm v5, v9, v5, v7
237 #else
238 vperm v5, v5, v9, v7
239 #endif
240 L(begin2):
241 lvx v4, 0, r3
242 vcmpequb. v7, v0, v4 /* Check for null. */
243 beq cr6, L(nullchk6)
244 b L(trailcheck)
246 .align 4
247 L(nullchk6):
248 clrldi r10, r3, 60
249 cmpdi cr7, r10, 0
250 beq cr7, L(next16)
251 #ifdef __LITTLE_ENDIAN__
252 lvsr v7, 0, r3
253 #else
254 lvsl v7, 0, r3
255 #endif
256 addi r5, r3, 16
257 /* If r3 is unaligned, load another 16 bytes. */
258 lvx v10, 0, r5
259 #ifdef __LITTLE_ENDIAN__
260 vperm v4, v10, v4, v7
261 #else
262 vperm v4, v4, v10, v7
263 #endif
264 L(next16):
265 vcmpequb. v6, v0, v5 /* Check for null. */
266 beq cr6, L(nullchk)
267 b L(trailcheck)
269 .align 4
270 L(nullchk):
271 vcmpequb. v6, v0, v4
272 beq cr6, L(nullchk1)
273 b L(retnull)
275 .align 4
276 L(nullchk1):
277 /* Convert both v3 and v4 to lower. */
278 TOLOWER(v5)
279 /* If both are same, branch to match. */
280 blt cr6, L(match)
281 /* Find if the first char is present in next 15 bytes. */
282 #ifdef __LITTLE_ENDIAN__
283 vspltb v6, v5, 15
284 vsldoi v7, v0, v4, 15
285 #else
286 vspltb v6, v5, 0
287 vspltisb v7, 8
288 vslo v7, v4, v7
289 #endif
290 vcmpequb v7, v6, v7
291 vcmpequb. v6, v0, v7
292 /* Shift r3 by 16 bytes and proceed. */
293 blt cr6, L(shift16)
294 VCLZD_V8_v7
295 #ifdef __LITTLE_ENDIAN__
296 vspltb v6, v8, 15
297 #else
298 vspltb v6, v8, 7
299 #endif
300 vcmpequb. v6, v6, v1
301 /* Shift r3 by 8 bytes and proceed. */
302 blt cr6, L(shift8)
303 b L(begin)
305 .align 4
306 L(match):
307 /* There is a match of 16 bytes, check next bytes. */
308 cmpdi cr7, r31, 16
309 mr r29, r3
310 beq cr7, L(ret_r3)
312 L(secondmatch):
313 addi r3, r3, 16
314 addi r4, r4, 16
315 /* Load next 16 bytes of r3 and r4 and compare. */
316 clrldi r10, r4, 60
317 cmpdi cr7, r10, 0
318 beq cr7, L(nextload)
319 /* Handle unaligned case. */
320 vor v6, v9, v9
321 vcmpequb. v7, v0, v6
322 beq cr6, L(nullchk2)
323 b L(trailcheck)
325 .align 4
326 L(nullchk2):
327 #ifdef __LITTLE_ENDIAN__
328 lvsr v7, 0, r4
329 #else
330 lvsl v7, 0, r4
331 #endif
332 addi r5, r4, 16
333 /* If r4 is unaligned, load another 16 bytes. */
334 lvx v9, 0, r5
335 #ifdef __LITTLE_ENDIAN__
336 vperm v11, v9, v6, v7
337 #else
338 vperm v11, v6, v9, v7
339 #endif
340 b L(compare)
342 .align 4
343 L(nextload):
344 lvx v11, 0, r4
345 L(compare):
346 vcmpequb. v7, v0, v11
347 beq cr6, L(nullchk3)
348 b L(trailcheck)
350 .align 4
351 L(nullchk3):
352 clrldi r10, r3, 60
353 cmpdi cr7, r10, 0
354 beq cr7, L(nextload1)
355 /* Handle unaligned case. */
356 vor v4, v10, v10
357 vcmpequb. v7, v0, v4
358 beq cr6, L(nullchk4)
359 b L(retnull)
361 .align 4
362 L(nullchk4):
363 #ifdef __LITTLE_ENDIAN__
364 lvsr v7, 0, r3
365 #else
366 lvsl v7, 0, r3
367 #endif
368 addi r5, r3, 16
369 /* If r3 is unaligned, load another 16 bytes. */
370 lvx v10, 0, r5
371 #ifdef __LITTLE_ENDIAN__
372 vperm v4, v10, v4, v7
373 #else
374 vperm v4, v4, v10, v7
375 #endif
376 b L(compare1)
378 .align 4
379 L(nextload1):
380 lvx v4, 0, r3
381 L(compare1):
382 vcmpequb. v7, v0, v4
383 beq cr6, L(nullchk5)
384 b L(retnull)
386 .align 4
387 L(nullchk5):
388 /* Convert both v3 and v4 to lower. */
389 TOLOWER(v11)
390 /* If both are same, branch to secondmatch. */
391 blt cr6, L(secondmatch)
392 /* Continue the search. */
393 b L(begin)
395 .align 4
396 L(trailcheck):
397 ld r10, __libc_tsd_LOCALE@got@tprel(r2)
398 add r11, r10, __libc_tsd_LOCALE@tls
399 ld r11, 0(r11)
400 ld r11, LOCALE_CTYPE_TOLOWER(r11)
401 L(loop2):
402 lbz r5, 0(r3) /* Load byte from r3. */
403 lbz r6, 0(r4) /* Load next byte from r4. */
404 cmpdi cr7, r6, 0 /* Is it null? */
405 beq cr7, L(updater3)
406 cmpdi cr7, r5, 0 /* Is it null? */
407 beq cr7, L(retnull) /* If yes, return. */
408 addi r3, r3, 1
409 addi r4, r4, 1 /* Increment r4. */
410 sldi r10, r5, 2 /* Convert to lower case. */
411 lwzx r10, r11, r10
412 sldi r7, r6, 2 /* Convert to lower case. */
413 lwzx r7, r11, r7
414 cmpw cr7, r7, r10 /* Compare with byte from r4. */
415 bne cr7, L(begin)
416 b L(loop2)
418 .align 4
419 L(shift8):
420 addi r8, r8, 7
421 b L(begin)
422 .align 4
423 L(shift16):
424 addi r8, r8, 15
425 .align 4
426 L(begin):
427 addi r8, r8, 1
428 mr r3, r8
429 /* When our iterations exceed ITERATIONS,fall back to default. */
430 addi r27, r27, 1
431 cmpdi cr7, r27, ITERATIONS
432 beq cr7, L(default)
433 mr r4, r30 /* Restore r4. */
434 b L(begin2)
436 /* Handling byte by byte. */
437 .align 4
438 L(loop1):
439 mr r3, r8
440 addi r27, r27, 1
441 cmpdi cr7, r27, ITERATIONS
442 beq cr7, L(default)
443 mr r29, r8
444 srdi r4, r28, 8
445 /* Check if the first char is present. */
446 bl STRCHR
447 nop
448 mr r5, r3
449 mr r3, r29
450 mr r29, r5
451 sldi r4, r28, 56
452 srdi r4, r4, 56
453 bl STRCHR
454 nop
455 cmpdi cr7, r29, 0
456 beq cr7, L(nextpos)
457 cmpdi cr7, r3, 0
458 beq cr7, L(skipcheck1)
459 cmpw cr7, r3, r29
460 ble cr7, L(nextpos)
461 /* Move r3 to first occurence. */
462 L(skipcheck1):
463 mr r3, r29
464 L(nextpos):
465 mr r29, r3
466 cmpdi cr7, r3, 0
467 ble cr7, L(retnull)
468 L(bytebybyte):
469 ld r10, __libc_tsd_LOCALE@got@tprel(r2)
470 add r11, r10, __libc_tsd_LOCALE@tls
471 ld r11, 0(r11)
472 ld r11, LOCALE_CTYPE_TOLOWER(r11)
473 mr r4, r30 /* Restore r4. */
474 mr r8, r3 /* Save r3. */
475 addi r8, r8, 1
477 L(loop):
478 addi r3, r3, 1
479 lbz r5, 0(r3) /* Load byte from r3. */
480 addi r4, r4, 1 /* Increment r4. */
481 lbz r6, 0(r4) /* Load next byte from r4. */
482 cmpdi cr7, r6, 0 /* Is it null? */
483 beq cr7, L(updater3)
484 cmpdi cr7, r5, 0 /* Is it null? */
485 beq cr7, L(retnull) /* If yes, return. */
486 sldi r10, r5, 2 /* Convert to lower case. */
487 lwzx r10, r11, r10
488 sldi r7, r6, 2 /* Convert to lower case. */
489 lwzx r7, r11, r7
490 cmpw cr7, r7, r10 /* Compare with byte from r4. */
491 bne cr7, L(loop1)
492 b L(loop)
494 /* Handling return values. */
495 .align 4
496 L(updater3):
497 subf r3, r31, r3 /* Reduce r31 (len of r4) from r3. */
498 b L(end)
500 .align 4
501 L(ret_r3):
502 mr r3, r29 /* Return point of match. */
503 b L(end)
505 .align 4
506 L(retnull):
507 li r3, 0 /* Substring was not found. */
508 b L(end)
510 .align 4
511 L(default):
512 mr r4, r30
513 bl __strcasestr_ppc
514 nop
516 .align 4
517 L(end):
518 addi r1, r1, FRAMESIZE /* Restore stack pointer. */
519 cfi_adjust_cfa_offset(-FRAMESIZE)
520 ld r0, 16(r1) /* Restore the saved link register. */
521 ld r27, -40(r1)
522 ld r28, -32(r1)
523 ld r29, -24(r1) /* Restore callers save register r29. */
524 ld r30, -16(r1) /* Restore callers save register r30. */
525 ld r31, -8(r1) /* Restore callers save register r31. */
526 cfi_restore(lr)
527 cfi_restore(r27)
528 cfi_restore(r28)
529 cfi_restore(r29)
530 cfi_restore(r30)
531 cfi_restore(r31)
532 mtlr r0 /* Branch to link register. */
533 blr
534 END (STRCASESTR)
536 weak_alias (__strcasestr, strcasestr)
537 libc_hidden_def (__strcasestr)
538 libc_hidden_builtin_def (strcasestr)