1/* 2 * Copyright (c) 2013 ARM Ltd 3 * All rights reserved. 4 * 5 * Redistribution and use in source and binary forms, with or without 6 * modification, are permitted provided that the following conditions 7 * are met: 8 * 1. Redistributions of source code must retain the above copyright 9 * notice, this list of conditions and the following disclaimer. 10 * 2. Redistributions in binary form must reproduce the above copyright 11 * notice, this list of conditions and the following disclaimer in the 12 * documentation and/or other materials provided with the distribution. 13 * 3. The name of the company may not be used to endorse or promote 14 * products derived from this software without specific prior written 15 * permission. 16 * 17 * THIS SOFTWARE IS PROVIDED BY ARM LTD ``AS IS'' AND ANY EXPRESS OR IMPLIED 18 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES OF 19 * MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. 20 * IN NO EVENT SHALL ARM LTD BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 21 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED 22 * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 23 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF 24 * LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING 25 * NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS 26 * SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 */ 28 29#include <machine/cpu-features.h> 30#include <private/bionic_asm.h> 31 32#ifdef __ARMEB__ 33#define S2LOMEM lsl 34#define S2LOMEMEQ lsleq 35#define S2HIMEM lsr 36#define MSB 0x000000ff 37#define LSB 0xff000000 38#define BYTE0_OFFSET 24 39#define BYTE1_OFFSET 16 40#define BYTE2_OFFSET 8 41#define BYTE3_OFFSET 0 42#else /* not __ARMEB__ */ 43#define S2LOMEM lsr 44#define S2LOMEMEQ lsreq 45#define S2HIMEM lsl 46#define BYTE0_OFFSET 0 47#define BYTE1_OFFSET 8 48#define BYTE2_OFFSET 16 49#define BYTE3_OFFSET 24 50#define MSB 0xff000000 51#define LSB 0x000000ff 52#endif /* not __ARMEB__ */ 53 54.syntax unified 55 56#if defined (__thumb__) 57 .thumb 58 .thumb_func 59#endif 60 61ENTRY(strcmp) 62 /* Use LDRD whenever possible. */ 63 64/* The main thing to look out for when comparing large blocks is that 65 the loads do not cross a page boundary when loading past the index 66 of the byte with the first difference or the first string-terminator. 67 68 For example, if the strings are identical and the string-terminator 69 is at index k, byte by byte comparison will not load beyond address 70 s1+k and s2+k; word by word comparison may load up to 3 bytes beyond 71 k; double word - up to 7 bytes. If the load of these bytes crosses 72 a page boundary, it might cause a memory fault (if the page is not mapped) 73 that would not have happened in byte by byte comparison. 74 75 If an address is (double) word aligned, then a load of a (double) word 76 from that address will not cross a page boundary. 77 Therefore, the algorithm below considers word and double-word alignment 78 of strings separately. */ 79 80/* High-level description of the algorithm. 81 82 * The fast path: if both strings are double-word aligned, 83 use LDRD to load two words from each string in every loop iteration. 84 * If the strings have the same offset from a word boundary, 85 use LDRB to load and compare byte by byte until 86 the first string is aligned to a word boundary (at most 3 bytes). 87 This is optimized for quick return on short unaligned strings. 88 * If the strings have the same offset from a double-word boundary, 89 use LDRD to load two words from each string in every loop iteration, as in the fast path. 90 * If the strings do not have the same offset from a double-word boundary, 91 load a word from the second string before the loop to initialize the queue. 92 Use LDRD to load two words from every string in every loop iteration. 93 Inside the loop, load the second word from the second string only after comparing 94 the first word, using the queued value, to guarantee safety across page boundaries. 95 * If the strings do not have the same offset from a word boundary, 96 use LDR and a shift queue. Order of loads and comparisons matters, 97 similarly to the previous case. 98 99 * Use UADD8 and SEL to compare words, and use REV and CLZ to compute the return value. 100 * The only difference between ARM and Thumb modes is the use of CBZ instruction. 101 * The only difference between big and little endian is the use of REV in little endian 102 to compute the return value, instead of MOV. 103*/ 104 105 .macro m_cbz reg label 106#ifdef __thumb2__ 107 cbz \reg, \label 108#else /* not defined __thumb2__ */ 109 cmp \reg, #0 110 beq \label 111#endif /* not defined __thumb2__ */ 112 .endm /* m_cbz */ 113 114 .macro m_cbnz reg label 115#ifdef __thumb2__ 116 cbnz \reg, \label 117#else /* not defined __thumb2__ */ 118 cmp \reg, #0 119 bne \label 120#endif /* not defined __thumb2__ */ 121 .endm /* m_cbnz */ 122 123 .macro init 124 /* Macro to save temporary registers and prepare magic values. */ 125 subs sp, sp, #16 126 .cfi_def_cfa_offset 16 127 strd r4, r5, [sp, #8] 128 .cfi_rel_offset r4, 0 129 .cfi_rel_offset r5, 4 130 strd r6, r7, [sp] 131 .cfi_rel_offset r6, 8 132 .cfi_rel_offset r7, 12 133 mvn r6, #0 /* all F */ 134 mov r7, #0 /* all 0 */ 135 .endm /* init */ 136 137 .macro magic_compare_and_branch w1 w2 label 138 /* Macro to compare registers w1 and w2 and conditionally branch to label. */ 139 cmp \w1, \w2 /* Are w1 and w2 the same? */ 140 magic_find_zero_bytes \w1 141 it eq 142 cmpeq ip, #0 /* Is there a zero byte in w1? */ 143 bne \label 144 .endm /* magic_compare_and_branch */ 145 146 .macro magic_find_zero_bytes w1 147 /* Macro to find all-zero bytes in w1, result is in ip. */ 148 uadd8 ip, \w1, r6 149 sel ip, r7, r6 150 .endm /* magic_find_zero_bytes */ 151 152 .macro setup_return w1 w2 153#ifdef __ARMEB__ 154 mov r1, \w1 155 mov r2, \w2 156#else /* not __ARMEB__ */ 157 rev r1, \w1 158 rev r2, \w2 159#endif /* not __ARMEB__ */ 160 .endm /* setup_return */ 161 162 pld [r0, #0] 163 pld [r1, #0] 164 165 /* Are both strings double-word aligned? */ 166 orr ip, r0, r1 167 tst ip, #7 168 bne .L_do_align 169 170 /* Fast path. */ 171 init 172 173.L_doubleword_aligned: 174 175 /* Get here when the strings to compare are double-word aligned. */ 176 /* Compare two words in every iteration. */ 177 .p2align 2 1782: 179 pld [r0, #16] 180 pld [r1, #16] 181 182 /* Load the next double-word from each string. */ 183 ldrd r2, r3, [r0], #8 184 ldrd r4, r5, [r1], #8 185 186 magic_compare_and_branch w1=r2, w2=r4, label=.L_return_24 187 magic_compare_and_branch w1=r3, w2=r5, label=.L_return_35 188 b 2b 189 190.L_do_align: 191 /* Is the first string word-aligned? */ 192 ands ip, r0, #3 193 beq .L_word_aligned_r0 194 195 /* Fast compare byte by byte until the first string is word-aligned. */ 196 /* The offset of r0 from a word boundary is in ip. Thus, the number of bytes 197 to read until the next word boundary is 4-ip. */ 198 bic r0, r0, #3 199 ldr r2, [r0], #4 200 lsls ip, ip, #31 201 beq .L_byte2 202 bcs .L_byte3 203 204.L_byte1: 205 ldrb ip, [r1], #1 206 uxtb r3, r2, ror #BYTE1_OFFSET 207 subs ip, r3, ip 208 bne .L_fast_return 209 m_cbz reg=r3, label=.L_fast_return 210 211.L_byte2: 212 ldrb ip, [r1], #1 213 uxtb r3, r2, ror #BYTE2_OFFSET 214 subs ip, r3, ip 215 bne .L_fast_return 216 m_cbz reg=r3, label=.L_fast_return 217 218.L_byte3: 219 ldrb ip, [r1], #1 220 uxtb r3, r2, ror #BYTE3_OFFSET 221 subs ip, r3, ip 222 bne .L_fast_return 223 m_cbnz reg=r3, label=.L_word_aligned_r0 224 225.L_fast_return: 226 mov r0, ip 227 bx lr 228 229.L_word_aligned_r0: 230 init 231 /* The first string is word-aligned. */ 232 /* Is the second string word-aligned? */ 233 ands ip, r1, #3 234 bne .L_strcmp_unaligned 235 236.L_word_aligned: 237 /* The strings are word-aligned. */ 238 /* Is the first string double-word aligned? */ 239 tst r0, #4 240 beq .L_doubleword_aligned_r0 241 242 /* If r0 is not double-word aligned yet, align it by loading 243 and comparing the next word from each string. */ 244 ldr r2, [r0], #4 245 ldr r4, [r1], #4 246 magic_compare_and_branch w1=r2 w2=r4 label=.L_return_24 247 248.L_doubleword_aligned_r0: 249 /* Get here when r0 is double-word aligned. */ 250 /* Is r1 doubleword_aligned? */ 251 tst r1, #4 252 beq .L_doubleword_aligned 253 254 /* Get here when the strings to compare are word-aligned, 255 r0 is double-word aligned, but r1 is not double-word aligned. */ 256 257 /* Initialize the queue. */ 258 ldr r5, [r1], #4 259 260 /* Compare two words in every iteration. */ 261 .p2align 2 2623: 263 pld [r0, #16] 264 pld [r1, #16] 265 266 /* Load the next double-word from each string and compare. */ 267 ldrd r2, r3, [r0], #8 268 magic_compare_and_branch w1=r2 w2=r5 label=.L_return_25 269 ldrd r4, r5, [r1], #8 270 magic_compare_and_branch w1=r3 w2=r4 label=.L_return_34 271 b 3b 272 273 .macro miscmp_word offsetlo offsethi 274 /* Macro to compare misaligned strings. */ 275 /* r0, r1 are word-aligned, and at least one of the strings 276 is not double-word aligned. */ 277 /* Compare one word in every loop iteration. */ 278 /* OFFSETLO is the original bit-offset of r1 from a word-boundary, 279 OFFSETHI is 32 - OFFSETLO (i.e., offset from the next word). */ 280 281 /* Initialize the shift queue. */ 282 ldr r5, [r1], #4 283 284 /* Compare one word from each string in every loop iteration. */ 285 .p2align 2 2867: 287 ldr r3, [r0], #4 288 S2LOMEM r5, r5, #\offsetlo 289 magic_find_zero_bytes w1=r3 290 cmp r7, ip, S2HIMEM #\offsetlo 291 and r2, r3, r6, S2LOMEM #\offsetlo 292 it eq 293 cmpeq r2, r5 294 bne .L_return_25 295 ldr r5, [r1], #4 296 cmp ip, #0 297 eor r3, r2, r3 298 S2HIMEM r2, r5, #\offsethi 299 it eq 300 cmpeq r3, r2 301 bne .L_return_32 302 b 7b 303 .endm /* miscmp_word */ 304 305.L_return_32: 306 setup_return w1=r3, w2=r2 307 b .L_do_return 308.L_return_34: 309 setup_return w1=r3, w2=r4 310 b .L_do_return 311.L_return_25: 312 setup_return w1=r2, w2=r5 313 b .L_do_return 314.L_return_35: 315 setup_return w1=r3, w2=r5 316 b .L_do_return 317.L_return_24: 318 setup_return w1=r2, w2=r4 319 320.L_do_return: 321 322#ifdef __ARMEB__ 323 mov r0, ip 324#else /* not __ARMEB__ */ 325 rev r0, ip 326#endif /* not __ARMEB__ */ 327 328 /* Restore temporaries early, before computing the return value. */ 329 ldrd r6, r7, [sp] 330 ldrd r4, r5, [sp, #8] 331 adds sp, sp, #16 332 .cfi_def_cfa_offset 0 333 .cfi_restore r4 334 .cfi_restore r5 335 .cfi_restore r6 336 .cfi_restore r7 337 338 /* There is a zero or a different byte between r1 and r2. */ 339 /* r0 contains a mask of all-zero bytes in r1. */ 340 /* Using r0 and not ip here because cbz requires low register. */ 341 m_cbz reg=r0, label=.L_compute_return_value 342 clz r0, r0 343 /* r0 contains the number of bits on the left of the first all-zero byte in r1. */ 344 rsb r0, r0, #24 345 /* Here, r0 contains the number of bits on the right of the first all-zero byte in r1. */ 346 lsr r1, r1, r0 347 lsr r2, r2, r0 348 349.L_compute_return_value: 350 movs r0, #1 351 cmp r1, r2 352 /* The return value is computed as follows. 353 If r1>r2 then (C==1 and Z==0) and LS doesn't hold and r0 is #1 at return. 354 If r1<r2 then (C==0 and Z==0) and we execute SBC with carry_in=0, 355 which means r0:=r0-r0-1 and r0 is #-1 at return. 356 If r1=r2 then (C==1 and Z==1) and we execute SBC with carry_in=1, 357 which means r0:=r0-r0 and r0 is #0 at return. 358 (C==0 and Z==1) cannot happen because the carry bit is "not borrow". */ 359 it ls 360 sbcls r0, r0, r0 361 bx lr 362 363 /* The code from the previous version of strcmp.S handles all of the 364 * cases where the first string and seconds string cannot both be 365 * aligned to a word boundary faster than the new algorithm. See 366 * bionic/libc/arch-arm/cortex-a15/bionic/strcmp.S for the unedited 367 * version of the code. 368 */ 369.L_strcmp_unaligned: 370 wp1 .req r0 371 wp2 .req r1 372 b1 .req r2 373 w1 .req r4 374 w2 .req r5 375 t1 .req ip 376 @ r3 is scratch 377 3782: 379 mov b1, #1 380 orr b1, b1, b1, lsl #8 381 orr b1, b1, b1, lsl #16 382 383 and t1, wp2, #3 384 bic wp2, wp2, #3 385 ldr w1, [wp1], #4 386 ldr w2, [wp2], #4 387 cmp t1, #2 388 beq 2f 389 bhi 3f 390 391 /* Critical inner Loop: Block with 3 bytes initial overlap */ 392 .p2align 2 3931: 394 bic t1, w1, #MSB 395 cmp t1, w2, S2LOMEM #8 396 sub r3, w1, b1 397 bic r3, r3, w1 398 bne 4f 399 ands r3, r3, b1, lsl #7 400 it eq 401 ldreq w2, [wp2], #4 402 bne 5f 403 eor t1, t1, w1 404 cmp t1, w2, S2HIMEM #24 405 bne 6f 406 ldr w1, [wp1], #4 407 b 1b 4084: 409 S2LOMEM w2, w2, #8 410 b 8f 411 4125: 413#ifdef __ARMEB__ 414 /* The syndrome value may contain false ones if the string ends 415 * with the bytes 0x01 0x00 416 */ 417 tst w1, #0xff000000 418 itt ne 419 tstne w1, #0x00ff0000 420 tstne w1, #0x0000ff00 421 beq 7f 422#else 423 bics r3, r3, #0xff000000 424 bne 7f 425#endif 426 ldrb w2, [wp2] 427 S2LOMEM t1, w1, #24 428#ifdef __ARMEB__ 429 lsl w2, w2, #24 430#endif 431 b 8f 432 4336: 434 S2LOMEM t1, w1, #24 435 and w2, w2, #LSB 436 b 8f 437 438 /* Critical inner Loop: Block with 2 bytes initial overlap */ 439 .p2align 2 4402: 441 S2HIMEM t1, w1, #16 442 sub r3, w1, b1 443 S2LOMEM t1, t1, #16 444 bic r3, r3, w1 445 cmp t1, w2, S2LOMEM #16 446 bne 4f 447 ands r3, r3, b1, lsl #7 448 it eq 449 ldreq w2, [wp2], #4 450 bne 5f 451 eor t1, t1, w1 452 cmp t1, w2, S2HIMEM #16 453 bne 6f 454 ldr w1, [wp1], #4 455 b 2b 456 4575: 458#ifdef __ARMEB__ 459 /* The syndrome value may contain false ones if the string ends 460 * with the bytes 0x01 0x00 461 */ 462 tst w1, #0xff000000 463 it ne 464 tstne w1, #0x00ff0000 465 beq 7f 466#else 467 lsls r3, r3, #16 468 bne 7f 469#endif 470 ldrh w2, [wp2] 471 S2LOMEM t1, w1, #16 472#ifdef __ARMEB__ 473 lsl w2, w2, #16 474#endif 475 b 8f 476 4776: 478 S2HIMEM w2, w2, #16 479 S2LOMEM t1, w1, #16 4804: 481 S2LOMEM w2, w2, #16 482 b 8f 483 484 /* Critical inner Loop: Block with 1 byte initial overlap */ 485 .p2align 2 4863: 487 and t1, w1, #LSB 488 cmp t1, w2, S2LOMEM #24 489 sub r3, w1, b1 490 bic r3, r3, w1 491 bne 4f 492 ands r3, r3, b1, lsl #7 493 it eq 494 ldreq w2, [wp2], #4 495 bne 5f 496 eor t1, t1, w1 497 cmp t1, w2, S2HIMEM #8 498 bne 6f 499 ldr w1, [wp1], #4 500 b 3b 5014: 502 S2LOMEM w2, w2, #24 503 b 8f 5045: 505 /* The syndrome value may contain false ones if the string ends 506 * with the bytes 0x01 0x00 507 */ 508 tst w1, #LSB 509 beq 7f 510 ldr w2, [wp2], #4 5116: 512 S2LOMEM t1, w1, #8 513 bic w2, w2, #MSB 514 b 8f 5157: 516 mov r0, #0 517 518 /* Restore registers and stack. */ 519 ldrd r6, r7, [sp] 520 ldrd r4, r5, [sp, #8] 521 adds sp, sp, #16 522 .cfi_def_cfa_offset 0 523 .cfi_restore r4 524 .cfi_restore r5 525 .cfi_restore r6 526 .cfi_restore r7 527 528 bx lr 529 5308: 531 and r2, t1, #LSB 532 and r0, w2, #LSB 533 cmp r0, #1 534 it cs 535 cmpcs r0, r2 536 itt eq 537 S2LOMEMEQ t1, t1, #8 538 S2LOMEMEQ w2, w2, #8 539 beq 8b 540 sub r0, r2, r0 541 542 /* Restore registers and stack. */ 543 ldrd r6, r7, [sp] 544 ldrd r4, r5, [sp, #8] 545 adds sp, sp, #16 546 547 bx lr 548END(strcmp) 549