478 lines · plain
1/*2 * strcmp for ARMv73 *4 * Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.5 * See https://llvm.org/LICENSE.txt for license information.6 * SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception7 */8 9#if __ARM_ARCH >= 7 && __ARM_ARCH_ISA_ARM >= 110 11/* Implementation of strcmp for ARMv7 when DSP instructions are12 available. Use ldrd to support wider loads, provided the data13 is sufficiently aligned. Use saturating arithmetic to optimize14 the compares. */15 16#include "../asmdefs.h"17 18/* Build Options:19 STRCMP_NO_PRECHECK: Don't run a quick pre-check of the first20 byte in the string. If comparing completely random strings21 the pre-check will save time, since there is a very high22 probability of a mismatch in the first character: we save23 significant overhead if this is the common case. However,24 if strings are likely to be identical (eg because we're25 verifying a hit in a hash table), then this check is largely26 redundant. */27 28#define STRCMP_NO_PRECHECK 029 30 /* This version uses Thumb-2 code. */31 .thumb32 .syntax unified33 34#ifdef __ARM_BIG_ENDIAN35#define S2LO lsl36#define S2LOEQ lsleq37#define S2HI lsr38#define MSB 0x000000ff39#define LSB 0xff00000040#define BYTE0_OFFSET 2441#define BYTE1_OFFSET 1642#define BYTE2_OFFSET 843#define BYTE3_OFFSET 044#else /* not __ARM_BIG_ENDIAN */45#define S2LO lsr46#define S2LOEQ lsreq47#define S2HI lsl48#define BYTE0_OFFSET 049#define BYTE1_OFFSET 850#define BYTE2_OFFSET 1651#define BYTE3_OFFSET 2452#define MSB 0xff00000053#define LSB 0x000000ff54#endif /* not __ARM_BIG_ENDIAN */55 56/* Parameters and result. */57#define src1 r058#define src2 r159#define result r0 /* Overlaps src1. */60 61/* Internal variables. */62#define tmp1 r463#define tmp2 r564#define const_m1 r1265 66/* Additional internal variables for 64-bit aligned data. */67#define data1a r268#define data1b r369#define data2a r670#define data2b r771#define syndrome_a tmp172#define syndrome_b tmp273 74/* Additional internal variables for 32-bit aligned data. */75#define data1 r276#define data2 r377#define syndrome tmp278 79 80 /* Macro to compute and return the result value for word-aligned81 cases. */82 .macro strcmp_epilogue_aligned synd d1 d2 restore_r683#ifdef __ARM_BIG_ENDIAN84 /* If data1 contains a zero byte, then syndrome will contain a 1 in85 bit 7 of that byte. Otherwise, the highest set bit in the86 syndrome will highlight the first different bit. It is therefore87 sufficient to extract the eight bits starting with the syndrome88 bit. */89 clz tmp1, \synd90 lsl r1, \d2, tmp191 .if \restore_r692 ldrd r6, r7, [sp, #8]93 .endif94 .cfi_restore 695 .cfi_restore 796 lsl \d1, \d1, tmp197 .cfi_remember_state98 lsr result, \d1, #2499 ldrd r4, r5, [sp], #16100 .cfi_restore 4101 .cfi_restore 5102 sub result, result, r1, lsr #24103 bx lr104#else105 /* To use the big-endian trick we'd have to reverse all three words.106 that's slower than this approach. */107 rev \synd, \synd108 clz tmp1, \synd109 bic tmp1, tmp1, #7110 lsr r1, \d2, tmp1111 .cfi_remember_state112 .if \restore_r6113 ldrd r6, r7, [sp, #8]114 .endif115 .cfi_restore 6116 .cfi_restore 7117 lsr \d1, \d1, tmp1118 and result, \d1, #255119 and r1, r1, #255120 ldrd r4, r5, [sp], #16121 .cfi_restore 4122 .cfi_restore 5123 sub result, result, r1124 125 bx lr126#endif127 .endm128 129 .text130 .p2align 5131L(strcmp_start_addr):132#if STRCMP_NO_PRECHECK == 0133L(fastpath_exit):134 sub r0, r2, r3135 bx lr136 nop137#endif138ENTRY_ALIGN (__strcmp_arm, 0)139#if STRCMP_NO_PRECHECK == 0140 ldrb r2, [src1]141 ldrb r3, [src2]142 cmp r2, #1143 it cs144 cmpcs r2, r3145 bne L(fastpath_exit)146#endif147 strd r4, r5, [sp, #-16]!148 .cfi_def_cfa_offset 16149 .cfi_offset 4, -16150 .cfi_offset 5, -12151 orr tmp1, src1, src2152 strd r6, r7, [sp, #8]153 .cfi_offset 6, -8154 .cfi_offset 7, -4155 mvn const_m1, #0156 lsl r2, tmp1, #29157 cbz r2, L(loop_aligned8)158 159L(not_aligned):160 eor tmp1, src1, src2161 tst tmp1, #7162 bne L(misaligned8)163 164 /* Deal with mutual misalignment by aligning downwards and then165 masking off the unwanted loaded data to prevent a difference. */166 and tmp1, src1, #7167 bic src1, src1, #7168 and tmp2, tmp1, #3169 bic src2, src2, #7170 lsl tmp2, tmp2, #3 /* Bytes -> bits. */171 ldrd data1a, data1b, [src1], #16172 tst tmp1, #4173 ldrd data2a, data2b, [src2], #16174 /* In thumb code we can't use MVN with a register shift, but175 we do have ORN. */176 S2HI tmp1, const_m1, tmp2177 orn data1a, data1a, tmp1178 orn data2a, data2a, tmp1179 beq L(start_realigned8)180 orn data1b, data1b, tmp1181 mov data1a, const_m1182 orn data2b, data2b, tmp1183 mov data2a, const_m1184 b L(start_realigned8)185 186 /* Unwind the inner loop by a factor of 2, giving 16 bytes per187 pass. */188 .p2align 5,,12 /* Don't start in the tail bytes of a cache line. */189 .p2align 2 /* Always word aligned. */190L(loop_aligned8):191 ldrd data1a, data1b, [src1], #16192 ldrd data2a, data2b, [src2], #16193L(start_realigned8):194 uadd8 syndrome_b, data1a, const_m1 /* Only want GE bits, */195 eor syndrome_a, data1a, data2a196 sel syndrome_a, syndrome_a, const_m1197 cbnz syndrome_a, L(diff_in_a)198 uadd8 syndrome_b, data1b, const_m1 /* Only want GE bits. */199 eor syndrome_b, data1b, data2b200 sel syndrome_b, syndrome_b, const_m1201 cbnz syndrome_b, L(diff_in_b)202 203 ldrd data1a, data1b, [src1, #-8]204 ldrd data2a, data2b, [src2, #-8]205 uadd8 syndrome_b, data1a, const_m1 /* Only want GE bits, */206 eor syndrome_a, data1a, data2a207 sel syndrome_a, syndrome_a, const_m1208 uadd8 syndrome_b, data1b, const_m1 /* Only want GE bits. */209 eor syndrome_b, data1b, data2b210 sel syndrome_b, syndrome_b, const_m1211 /* Can't use CBZ for backwards branch. */212 orrs syndrome_b, syndrome_b, syndrome_a /* Only need if s_a == 0 */213 beq L(loop_aligned8)214 215L(diff_found):216 cbnz syndrome_a, L(diff_in_a)217 218L(diff_in_b):219 strcmp_epilogue_aligned syndrome_b, data1b, data2b 1220 221L(diff_in_a):222 .cfi_restore_state223 strcmp_epilogue_aligned syndrome_a, data1a, data2a 1224 225 .cfi_restore_state226L(misaligned8):227 tst tmp1, #3228 bne L(misaligned4)229 ands tmp1, src1, #3230 bne L(mutual_align4)231 232 /* Unrolled by a factor of 2, to reduce the number of post-increment233 operations. */234L(loop_aligned4):235 ldr data1, [src1], #8236 ldr data2, [src2], #8237L(start_realigned4):238 uadd8 syndrome, data1, const_m1 /* Only need GE bits. */239 eor syndrome, data1, data2240 sel syndrome, syndrome, const_m1241 cbnz syndrome, L(aligned4_done)242 ldr data1, [src1, #-4]243 ldr data2, [src2, #-4]244 uadd8 syndrome, data1, const_m1245 eor syndrome, data1, data2246 sel syndrome, syndrome, const_m1247 cmp syndrome, #0248 beq L(loop_aligned4)249 250L(aligned4_done):251 strcmp_epilogue_aligned syndrome, data1, data2, 0252 253L(mutual_align4):254 .cfi_restore_state255 /* Deal with mutual misalignment by aligning downwards and then256 masking off the unwanted loaded data to prevent a difference. */257 lsl tmp1, tmp1, #3 /* Bytes -> bits. */258 bic src1, src1, #3259 ldr data1, [src1], #8260 bic src2, src2, #3261 ldr data2, [src2], #8262 263 /* In thumb code we can't use MVN with a register shift, but264 we do have ORN. */265 S2HI tmp1, const_m1, tmp1266 orn data1, data1, tmp1267 orn data2, data2, tmp1268 b L(start_realigned4)269 270L(misaligned4):271 ands tmp1, src1, #3272 beq L(src1_aligned)273 sub src2, src2, tmp1274 bic src1, src1, #3275 lsls tmp1, tmp1, #31276 ldr data1, [src1], #4277 beq L(aligned_m2)278 bcs L(aligned_m1)279 280#if STRCMP_NO_PRECHECK == 1281 ldrb data2, [src2, #1]282 uxtb tmp1, data1, ror #BYTE1_OFFSET283 subs tmp1, tmp1, data2284 bne L(misaligned_exit)285 cbz data2, L(misaligned_exit)286 287L(aligned_m2):288 ldrb data2, [src2, #2]289 uxtb tmp1, data1, ror #BYTE2_OFFSET290 subs tmp1, tmp1, data2291 bne L(misaligned_exit)292 cbz data2, L(misaligned_exit)293 294L(aligned_m1):295 ldrb data2, [src2, #3]296 uxtb tmp1, data1, ror #BYTE3_OFFSET297 subs tmp1, tmp1, data2298 bne L(misaligned_exit)299 add src2, src2, #4300 cbnz data2, L(src1_aligned)301#else /* STRCMP_NO_PRECHECK */302 /* If we've done the pre-check, then we don't need to check the303 first byte again here. */304 ldrb data2, [src2, #2]305 uxtb tmp1, data1, ror #BYTE2_OFFSET306 subs tmp1, tmp1, data2307 bne L(misaligned_exit)308 cbz data2, L(misaligned_exit)309 310L(aligned_m2):311 ldrb data2, [src2, #3]312 uxtb tmp1, data1, ror #BYTE3_OFFSET313 subs tmp1, tmp1, data2314 bne L(misaligned_exit)315 cbnz data2, L(aligned_m1)316#endif317 318L(misaligned_exit):319 .cfi_remember_state320 mov result, tmp1321 ldr r4, [sp], #16322 .cfi_restore 4323 bx lr324 325#if STRCMP_NO_PRECHECK == 0326L(aligned_m1):327 add src2, src2, #4328#endif329L(src1_aligned):330 .cfi_restore_state331 /* src1 is word aligned, but src2 has no common alignment332 with it. */333 ldr data1, [src1], #4334 lsls tmp1, src2, #31 /* C=src2[1], Z=src2[0]. */335 336 bic src2, src2, #3337 ldr data2, [src2], #4338 bhi L(overlap1) /* C=1, Z=0 => src2[1:0] = 0b11. */339 bcs L(overlap2) /* C=1, Z=1 => src2[1:0] = 0b10. */340 341 /* (overlap3) C=0, Z=0 => src2[1:0] = 0b01. */342L(overlap3):343 bic tmp1, data1, #MSB344 uadd8 syndrome, data1, const_m1345 eors syndrome, tmp1, data2, S2LO #8346 sel syndrome, syndrome, const_m1347 bne 4f348 cbnz syndrome, 5f349 ldr data2, [src2], #4350 eor tmp1, tmp1, data1351 cmp tmp1, data2, S2HI #24352 bne 6f353 ldr data1, [src1], #4354 b L(overlap3)3554:356 S2LO data2, data2, #8357 b L(strcmp_tail)358 3595:360 bics syndrome, syndrome, #MSB361 bne L(strcmp_done_equal)362 363 /* We can only get here if the MSB of data1 contains 0, so364 fast-path the exit. */365 ldrb result, [src2]366 .cfi_remember_state367 ldrd r4, r5, [sp], #16368 .cfi_restore 4369 .cfi_restore 5370 /* R6/7 Not used in this sequence. */371 .cfi_restore 6372 .cfi_restore 7373 neg result, result374 bx lr375 3766:377 .cfi_restore_state378 S2LO data1, data1, #24379 and data2, data2, #LSB380 b L(strcmp_tail)381 382 .p2align 5,,12 /* Ensure at least 3 instructions in cache line. */383L(overlap2):384 and tmp1, data1, const_m1, S2LO #16385 uadd8 syndrome, data1, const_m1386 eors syndrome, tmp1, data2, S2LO #16387 sel syndrome, syndrome, const_m1388 bne 4f389 cbnz syndrome, 5f390 ldr data2, [src2], #4391 eor tmp1, tmp1, data1392 cmp tmp1, data2, S2HI #16393 bne 6f394 ldr data1, [src1], #4395 b L(overlap2)3964:397 S2LO data2, data2, #16398 b L(strcmp_tail)3995:400 ands syndrome, syndrome, const_m1, S2LO #16401 bne L(strcmp_done_equal)402 403 ldrh data2, [src2]404 S2LO data1, data1, #16405#ifdef __ARM_BIG_ENDIAN406 lsl data2, data2, #16407#endif408 b L(strcmp_tail)409 4106:411 S2LO data1, data1, #16412 and data2, data2, const_m1, S2LO #16413 b L(strcmp_tail)414 415 .p2align 5,,12 /* Ensure at least 3 instructions in cache line. */416L(overlap1):417 and tmp1, data1, #LSB418 uadd8 syndrome, data1, const_m1419 eors syndrome, tmp1, data2, S2LO #24420 sel syndrome, syndrome, const_m1421 bne 4f422 cbnz syndrome, 5f423 ldr data2, [src2], #4424 eor tmp1, tmp1, data1425 cmp tmp1, data2, S2HI #8426 bne 6f427 ldr data1, [src1], #4428 b L(overlap1)4294:430 S2LO data2, data2, #24431 b L(strcmp_tail)4325:433 tst syndrome, #LSB434 bne L(strcmp_done_equal)435 ldr data2, [src2]4366:437 S2LO data1, data1, #8438 bic data2, data2, #MSB439 b L(strcmp_tail)440 441L(strcmp_done_equal):442 mov result, #0443 .cfi_remember_state444 ldrd r4, r5, [sp], #16445 .cfi_restore 4446 .cfi_restore 5447 /* R6/7 not used in this sequence. */448 .cfi_restore 6449 .cfi_restore 7450 bx lr451 452L(strcmp_tail):453 .cfi_restore_state454#ifndef __ARM_BIG_ENDIAN455 rev data1, data1456 rev data2, data2457 /* Now everything looks big-endian... */458#endif459 uadd8 tmp1, data1, const_m1460 eor tmp1, data1, data2461 sel syndrome, tmp1, const_m1462 clz tmp1, syndrome463 lsl data1, data1, tmp1464 lsl data2, data2, tmp1465 lsr result, data1, #24466 ldrd r4, r5, [sp], #16467 .cfi_restore 4468 .cfi_restore 5469 /* R6/7 not used in this sequence. */470 .cfi_restore 6471 .cfi_restore 7472 sub result, result, data2, lsr #24473 bx lr474 475END (__strcmp_arm)476 477#endif /* __ARM_ARCH >= 7 && __ARM_ARCH_ISA_ARM >= 1 */478