| blob | 90445b9c478067ec8916bdd9c941abb44f8945ab |
1 /* strcmp implementation for ARMv7-A, optimized for Cortex-A15.
2 Copyright (C) 2012-2015 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 <arm-features.h>
20 #include <sysdep.h>
22 /* Implementation of strcmp for ARMv7 when DSP instructions are
23 available. Use ldrd to support wider loads, provided the data
24 is sufficiently aligned. Use saturating arithmetic to optimize
25 the compares. */
27 /* Build Options:
28 STRCMP_PRECHECK: Run a quick pre-check of the first byte in the
29 string. If comparing completely random strings the pre-check will
30 save time, since there is a very high probability of a mismatch in
31 the first character: we save significant overhead if this is the
32 common case. However, if strings are likely to be identical (e.g.
33 because we're verifying a hit in a hash table), then this check
34 is largely redundant. */
36 #define STRCMP_PRECHECK 1
38 .syntax unified
40 #ifdef __ARM_BIG_ENDIAN
41 # define S2LO lsl
42 # define S2LOEQ lsleq
43 # define S2HI lsr
44 # define MSB 0x000000ff
45 # define LSB 0xff000000
46 # define BYTE0_OFFSET 24
47 # define BYTE1_OFFSET 16
48 # define BYTE2_OFFSET 8
49 # define BYTE3_OFFSET 0
50 #else /* not __ARM_BIG_ENDIAN */
51 # define S2LO lsr
52 # define S2LOEQ lsreq
53 # define S2HI lsl
54 # define BYTE0_OFFSET 0
55 # define BYTE1_OFFSET 8
56 # define BYTE2_OFFSET 16
57 # define BYTE3_OFFSET 24
58 # define MSB 0xff000000
59 # define LSB 0x000000ff
60 #endif /* not __ARM_BIG_ENDIAN */
62 /* Parameters and result. */
63 #define src1 r0
64 #define src2 r1
65 #define result r0 /* Overlaps src1. */
67 /* Internal variables. */
68 #define tmp1 r4
69 #define tmp2 r5
70 #define const_m1 r12
72 /* Additional internal variables for 64-bit aligned data. */
73 #define data1a r2
74 #define data1b r3
75 #define data2a r6
76 #define data2b r7
77 #define syndrome_a tmp1
78 #define syndrome_b tmp2
80 /* Additional internal variables for 32-bit aligned data. */
81 #define data1 r2
82 #define data2 r3
83 #define syndrome tmp2
86 #ifndef NO_THUMB
87 /* This code is best on Thumb. */
88 .thumb
90 /* In Thumb code we can't use MVN with a register shift, but we do have ORN. */
91 .macro prepare_mask mask_reg, nbits_reg
92 S2HI \mask_reg, const_m1, \nbits_reg
93 .endm
94 .macro apply_mask data_reg, mask_reg
95 orn \data_reg, \data_reg, \mask_reg
96 .endm
97 #else
98 /* In ARM code we don't have ORN, but we can use MVN with a register shift. */
99 .macro prepare_mask mask_reg, nbits_reg
100 mvn \mask_reg, const_m1, S2HI \nbits_reg
101 .endm
102 .macro apply_mask data_reg, mask_reg
103 orr \data_reg, \data_reg, \mask_reg
104 .endm
106 /* These clobber the condition codes, which the real Thumb cbz/cbnz
107 instructions do not. But it doesn't matter for any of the uses here. */
108 .macro cbz reg, label
109 cmp \reg, #0
110 beq \label
111 .endm
112 .macro cbnz reg, label
113 cmp \reg, #0
114 bne \label
115 .endm
116 #endif
119 /* Macro to compute and return the result value for word-aligned
120 cases. */
121 .macro strcmp_epilogue_aligned synd d1 d2 restore_r6
122 #ifdef __ARM_BIG_ENDIAN
123 /* If data1 contains a zero byte, then syndrome will contain a 1 in
124 bit 7 of that byte. Otherwise, the highest set bit in the
125 syndrome will highlight the first different bit. It is therefore
126 sufficient to extract the eight bits starting with the syndrome
127 bit. */
128 clz tmp1, \synd
129 lsl r1, \d2, tmp1
130 .if \restore_r6
131 ldrd r6, r7, [sp, #8]
132 .endif
133 lsl \d1, \d1, tmp1
134 lsr result, \d1, #24
135 ldrd r4, r5, [sp], #16
136 cfi_remember_state
137 cfi_def_cfa_offset (0)
138 cfi_restore (r4)
139 cfi_restore (r5)
140 cfi_restore (r6)
141 cfi_restore (r7)
142 sub result, result, r1, lsr #24
143 bx lr
144 #else
145 /* To use the big-endian trick we'd have to reverse all three words.
146 that's slower than this approach. */
147 rev \synd, \synd
148 clz tmp1, \synd
149 bic tmp1, tmp1, #7
150 lsr r1, \d2, tmp1
151 .if \restore_r6
152 ldrd r6, r7, [sp, #8]
153 .endif
154 lsr \d1, \d1, tmp1
155 and result, \d1, #255
156 and r1, r1, #255
157 ldrd r4, r5, [sp], #16
158 cfi_remember_state
159 cfi_def_cfa_offset (0)
160 cfi_restore (r4)
161 cfi_restore (r5)
162 cfi_restore (r6)
163 cfi_restore (r7)
164 sub result, result, r1
166 bx lr
167 #endif
168 .endm
170 .text
171 .p2align 5
172 .Lstrcmp_start_addr:
173 #if STRCMP_PRECHECK == 1
174 .Lfastpath_exit:
175 sub r0, r2, r3
176 bx lr
177 nop
178 #endif
179 ENTRY (strcmp)
180 #if STRCMP_PRECHECK == 1
181 sfi_breg src1, \
182 ldrb r2, [\B]
183 sfi_breg src2, \
184 ldrb r3, [\B]
185 cmp r2, #1
186 it cs
187 cmpcs r2, r3
188 bne .Lfastpath_exit
189 #endif
190 strd r4, r5, [sp, #-16]!
191 cfi_def_cfa_offset (16)
192 cfi_offset (r4, -16)
193 cfi_offset (r5, -12)
194 orr tmp1, src1, src2
195 strd r6, r7, [sp, #8]
196 cfi_offset (r6, -8)
197 cfi_offset (r7, -4)
198 mvn const_m1, #0
199 lsl r2, tmp1, #29
200 cbz r2, .Lloop_aligned8
202 .Lnot_aligned:
203 eor tmp1, src1, src2
204 tst tmp1, #7
205 bne .Lmisaligned8
207 /* Deal with mutual misalignment by aligning downwards and then
208 masking off the unwanted loaded data to prevent a difference. */
209 and tmp1, src1, #7
210 bic src1, src1, #7
211 and tmp2, tmp1, #3
212 bic src2, src2, #7
213 lsl tmp2, tmp2, #3 /* Bytes -> bits. */
214 sfi_breg src1, \
215 ldrd data1a, data1b, [\B], #16
216 tst tmp1, #4
217 sfi_breg src2, \
218 ldrd data2a, data2b, [\B], #16
219 prepare_mask tmp1, tmp2
220 apply_mask data1a, tmp1
221 apply_mask data2a, tmp1
222 beq .Lstart_realigned8
223 apply_mask data1b, tmp1
224 mov data1a, const_m1
225 apply_mask data2b, tmp1
226 mov data2a, const_m1
227 b .Lstart_realigned8
229 /* Unwind the inner loop by a factor of 2, giving 16 bytes per
230 pass. */
231 .p2align 5,,12 /* Don't start in the tail bytes of a cache line. */
232 .p2align 2 /* Always word aligned. */
233 .Lloop_aligned8:
234 sfi_breg src1, \
235 ldrd data1a, data1b, [\B], #16
236 sfi_breg src2, \
237 ldrd data2a, data2b, [\B], #16
238 .Lstart_realigned8:
239 uadd8 syndrome_b, data1a, const_m1 /* Only want GE bits, */
240 eor syndrome_a, data1a, data2a
241 sel syndrome_a, syndrome_a, const_m1
242 cbnz syndrome_a, .Ldiff_in_a
243 uadd8 syndrome_b, data1b, const_m1 /* Only want GE bits. */
244 eor syndrome_b, data1b, data2b
245 sel syndrome_b, syndrome_b, const_m1
246 cbnz syndrome_b, .Ldiff_in_b
248 sfi_breg src1, \
249 ldrd data1a, data1b, [\B, #-8]
250 sfi_breg src2, \
251 ldrd data2a, data2b, [\B, #-8]
252 uadd8 syndrome_b, data1a, const_m1 /* Only want GE bits, */
253 eor syndrome_a, data1a, data2a
254 sel syndrome_a, syndrome_a, const_m1
255 uadd8 syndrome_b, data1b, const_m1 /* Only want GE bits. */
256 eor syndrome_b, data1b, data2b
257 sel syndrome_b, syndrome_b, const_m1
258 /* Can't use CBZ for backwards branch. */
259 orrs syndrome_b, syndrome_b, syndrome_a /* Only need if s_a == 0 */
260 beq .Lloop_aligned8
262 .Ldiff_found:
263 cbnz syndrome_a, .Ldiff_in_a
265 .Ldiff_in_b:
266 strcmp_epilogue_aligned syndrome_b, data1b, data2b 1
268 .Ldiff_in_a:
269 cfi_restore_state
270 strcmp_epilogue_aligned syndrome_a, data1a, data2a 1
272 cfi_restore_state
273 .Lmisaligned8:
274 tst tmp1, #3
275 bne .Lmisaligned4
276 ands tmp1, src1, #3
277 bne .Lmutual_align4
279 /* Unrolled by a factor of 2, to reduce the number of post-increment
280 operations. */
281 .Lloop_aligned4:
282 sfi_breg src1, \
283 ldr data1, [\B], #8
284 sfi_breg src2, \
285 ldr data2, [\B], #8
286 .Lstart_realigned4:
287 uadd8 syndrome, data1, const_m1 /* Only need GE bits. */
288 eor syndrome, data1, data2
289 sel syndrome, syndrome, const_m1
290 cbnz syndrome, .Laligned4_done
291 sfi_breg src1, \
292 ldr data1, [\B, #-4]
293 sfi_breg src2, \
294 ldr data2, [\B, #-4]
295 uadd8 syndrome, data1, const_m1
296 eor syndrome, data1, data2
297 sel syndrome, syndrome, const_m1
298 cmp syndrome, #0
299 beq .Lloop_aligned4
301 .Laligned4_done:
302 strcmp_epilogue_aligned syndrome, data1, data2, 0
304 .Lmutual_align4:
305 cfi_restore_state
306 /* Deal with mutual misalignment by aligning downwards and then
307 masking off the unwanted loaded data to prevent a difference. */
308 lsl tmp1, tmp1, #3 /* Bytes -> bits. */
309 bic src1, src1, #3
310 sfi_breg src1, \
311 ldr data1, [\B], #8
312 bic src2, src2, #3
313 sfi_breg src2, \
314 ldr data2, [\B], #8
316 prepare_mask tmp1, tmp1
317 apply_mask data1, tmp1
318 apply_mask data2, tmp1
319 b .Lstart_realigned4
321 .Lmisaligned4:
322 ands tmp1, src1, #3
323 beq .Lsrc1_aligned
324 sub src2, src2, tmp1
325 bic src1, src1, #3
326 lsls tmp1, tmp1, #31
327 sfi_breg src1, \
328 ldr data1, [\B], #4
329 beq .Laligned_m2
330 bcs .Laligned_m1
332 #if STRCMP_PRECHECK == 0
333 sfi_breg src2, \
334 ldrb data2, [\B, #1]
335 uxtb tmp1, data1, ror #BYTE1_OFFSET
336 subs tmp1, tmp1, data2
337 bne .Lmisaligned_exit
338 cbz data2, .Lmisaligned_exit
340 .Laligned_m2:
341 sfi_breg src2, \
342 ldrb data2, [\B, #2]
343 uxtb tmp1, data1, ror #BYTE2_OFFSET
344 subs tmp1, tmp1, data2
345 bne .Lmisaligned_exit
346 cbz data2, .Lmisaligned_exit
348 .Laligned_m1:
349 sfi_breg src2, \
350 ldrb data2, [\B, #3]
351 uxtb tmp1, data1, ror #BYTE3_OFFSET
352 subs tmp1, tmp1, data2
353 bne .Lmisaligned_exit
354 add src2, src2, #4
355 cbnz data2, .Lsrc1_aligned
356 #else /* STRCMP_PRECHECK */
357 /* If we've done the pre-check, then we don't need to check the
358 first byte again here. */
359 sfi_breg src2, \
360 ldrb data2, [\B, #2]
361 uxtb tmp1, data1, ror #BYTE2_OFFSET
362 subs tmp1, tmp1, data2
363 bne .Lmisaligned_exit
364 cbz data2, .Lmisaligned_exit
366 .Laligned_m2:
367 sfi_breg src2, \
368 ldrb data2, [\B, #3]
369 uxtb tmp1, data1, ror #BYTE3_OFFSET
370 subs tmp1, tmp1, data2
371 bne .Lmisaligned_exit
372 cbnz data2, .Laligned_m1
373 #endif
375 .Lmisaligned_exit:
376 mov result, tmp1
377 ldr r4, [sp], #16
378 cfi_remember_state
379 cfi_def_cfa_offset (0)
380 cfi_restore (r4)
381 cfi_restore (r5)
382 cfi_restore (r6)
383 cfi_restore (r7)
384 bx lr
386 #if STRCMP_PRECHECK == 1
387 .Laligned_m1:
388 add src2, src2, #4
389 #endif
390 .Lsrc1_aligned:
391 cfi_restore_state
392 /* src1 is word aligned, but src2 has no common alignment
393 with it. */
394 sfi_breg src1, \
395 ldr data1, [\B], #4
396 lsls tmp1, src2, #31 /* C=src2[1], Z=src2[0]. */
398 bic src2, src2, #3
399 sfi_breg src2, \
400 ldr data2, [\B], #4
401 bhi .Loverlap1 /* C=1, Z=0 => src2[1:0] = 0b11. */
402 bcs .Loverlap2 /* C=1, Z=1 => src2[1:0] = 0b10. */
404 /* (overlap3) C=0, Z=0 => src2[1:0] = 0b01. */
405 .Loverlap3:
406 bic tmp1, data1, #MSB
407 uadd8 syndrome, data1, const_m1
408 eors syndrome, tmp1, data2, S2LO #8
409 sel syndrome, syndrome, const_m1
410 bne 4f
411 cbnz syndrome, 5f
412 sfi_breg src2, \
413 ldr data2, [\B], #4
414 eor tmp1, tmp1, data1
415 cmp tmp1, data2, S2HI #24
416 bne 6f
417 sfi_breg src1, \
418 ldr data1, [\B], #4
419 b .Loverlap3
420 4:
421 S2LO data2, data2, #8
422 b .Lstrcmp_tail
424 5:
425 bics syndrome, syndrome, #MSB
426 bne .Lstrcmp_done_equal
428 /* We can only get here if the MSB of data1 contains 0, so
429 fast-path the exit. */
430 sfi_breg src2, \
431 ldrb result, [\B]
432 ldrd r4, r5, [sp], #16
433 cfi_remember_state
434 cfi_def_cfa_offset (0)
435 cfi_restore (r4)
436 cfi_restore (r5)
437 /* R6/7 Not used in this sequence. */
438 cfi_restore (r6)
439 cfi_restore (r7)
440 neg result, result
441 bx lr
443 6:
444 cfi_restore_state
445 S2LO data1, data1, #24
446 and data2, data2, #LSB
447 b .Lstrcmp_tail
449 .p2align 5,,12 /* Ensure at least 3 instructions in cache line. */
450 .Loverlap2:
451 and tmp1, data1, const_m1, S2LO #16
452 uadd8 syndrome, data1, const_m1
453 eors syndrome, tmp1, data2, S2LO #16
454 sel syndrome, syndrome, const_m1
455 bne 4f
456 cbnz syndrome, 5f
457 sfi_breg src2, \
458 ldr data2, [\B], #4
459 eor tmp1, tmp1, data1
460 cmp tmp1, data2, S2HI #16
461 bne 6f
462 sfi_breg src1, \
463 ldr data1, [\B], #4
464 b .Loverlap2
465 4:
466 S2LO data2, data2, #16
467 b .Lstrcmp_tail
468 5:
469 ands syndrome, syndrome, const_m1, S2LO #16
470 bne .Lstrcmp_done_equal
472 sfi_breg src2, \
473 ldrh data2, [\B]
474 S2LO data1, data1, #16
475 #ifdef __ARM_BIG_ENDIAN
476 lsl data2, data2, #16
477 #endif
478 b .Lstrcmp_tail
480 6:
481 S2LO data1, data1, #16
482 and data2, data2, const_m1, S2LO #16
483 b .Lstrcmp_tail
485 .p2align 5,,12 /* Ensure at least 3 instructions in cache line. */
486 .Loverlap1:
487 and tmp1, data1, #LSB
488 uadd8 syndrome, data1, const_m1
489 eors syndrome, tmp1, data2, S2LO #24
490 sel syndrome, syndrome, const_m1
491 bne 4f
492 cbnz syndrome, 5f
493 sfi_breg src2, \
494 ldr data2, [\B], #4
495 eor tmp1, tmp1, data1
496 cmp tmp1, data2, S2HI #8
497 bne 6f
498 sfi_breg src1, \
499 ldr data1, [\B], #4
500 b .Loverlap1
501 4:
502 S2LO data2, data2, #24
503 b .Lstrcmp_tail
504 5:
505 tst syndrome, #LSB
506 bne .Lstrcmp_done_equal
507 sfi_breg src2, \
508 ldr data2, [\B]
509 6:
510 S2LO data1, data1, #8
511 bic data2, data2, #MSB
512 b .Lstrcmp_tail
514 .Lstrcmp_done_equal:
515 mov result, #0
516 ldrd r4, r5, [sp], #16
517 cfi_remember_state
518 cfi_def_cfa_offset (0)
519 cfi_restore (r4)
520 cfi_restore (r5)
521 /* R6/7 not used in this sequence. */
522 cfi_restore (r6)
523 cfi_restore (r7)
524 bx lr
526 .Lstrcmp_tail:
527 cfi_restore_state
528 #ifndef __ARM_BIG_ENDIAN
529 rev data1, data1
530 rev data2, data2
531 /* Now everything looks big-endian... */
532 #endif
533 uadd8 tmp1, data1, const_m1
534 eor tmp1, data1, data2
535 sel syndrome, tmp1, const_m1
536 clz tmp1, syndrome
537 lsl data1, data1, tmp1
538 lsl data2, data2, tmp1
539 lsr result, data1, #24
540 ldrd r4, r5, [sp], #16
541 cfi_def_cfa_offset (0)
542 cfi_restore (r4)
543 cfi_restore (r5)
544 /* R6/7 not used in this sequence. */
545 cfi_restore (r6)
546 cfi_restore (r7)
547 sub result, result, data2, lsr #24
548 bx lr
549 END (strcmp)
550 libc_hidden_builtin_def (strcmp)