[444] | 1 | /* |
---|
| 2 | * Copyright (c) 2012-2014 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 | /* Very similar to the generic code, but uses Thumb2 as implemented |
---|
| 30 | in ARMv7-M. */ |
---|
| 31 | |
---|
| 32 | /* Parameters and result. */ |
---|
| 33 | #define src1 r0 |
---|
| 34 | #define src2 r1 |
---|
| 35 | #define result r0 /* Overlaps src1. */ |
---|
| 36 | |
---|
| 37 | /* Internal variables. */ |
---|
| 38 | #define data1 r2 |
---|
| 39 | #define data2 r3 |
---|
| 40 | #define tmp2 r5 |
---|
| 41 | #define tmp1 r12 |
---|
| 42 | #define syndrome r12 /* Overlaps tmp1 */ |
---|
| 43 | |
---|
| 44 | .thumb |
---|
| 45 | .syntax unified |
---|
| 46 | def_fn strcmp |
---|
| 47 | .cfi_sections .debug_frame |
---|
| 48 | .cfi_startproc |
---|
| 49 | eor tmp1, src1, src2 |
---|
| 50 | tst tmp1, #3 |
---|
| 51 | /* Strings not at same byte offset from a word boundary. */ |
---|
| 52 | bne .Lstrcmp_unaligned |
---|
| 53 | ands tmp1, src1, #3 |
---|
| 54 | bic src1, src1, #3 |
---|
| 55 | bic src2, src2, #3 |
---|
| 56 | ldr data1, [src1], #4 |
---|
| 57 | it eq |
---|
| 58 | ldreq data2, [src2], #4 |
---|
| 59 | beq 4f |
---|
| 60 | /* Although s1 and s2 have identical initial alignment, they are |
---|
| 61 | not currently word aligned. Rather than comparing bytes, |
---|
| 62 | make sure that any bytes fetched from before the addressed |
---|
| 63 | bytes are forced to 0xff. Then they will always compare |
---|
| 64 | equal. */ |
---|
| 65 | eor tmp1, tmp1, #3 |
---|
| 66 | mvn data2, #MSB |
---|
| 67 | lsl tmp1, tmp1, #3 |
---|
| 68 | S2LO tmp1, data2, tmp1 |
---|
| 69 | ldr data2, [src2], #4 |
---|
| 70 | orr data1, data1, tmp1 |
---|
| 71 | orr data2, data2, tmp1 |
---|
| 72 | .p2align 2 |
---|
| 73 | /* Critical loop. */ |
---|
| 74 | 4: |
---|
| 75 | sub syndrome, data1, #0x01010101 |
---|
| 76 | cmp data1, data2 |
---|
| 77 | /* check for any zero bytes in first word */ |
---|
| 78 | itttt eq |
---|
| 79 | biceq syndrome, syndrome, data1 |
---|
| 80 | tsteq syndrome, #0x80808080 |
---|
| 81 | ldreq data1, [src1], #4 |
---|
| 82 | ldreq data2, [src2], #4 |
---|
| 83 | beq 4b |
---|
| 84 | 2: |
---|
| 85 | /* There's a zero or a different byte in the word */ |
---|
| 86 | S2HI result, data1, #24 |
---|
| 87 | S2LO data1, data1, #8 |
---|
| 88 | cmp result, #1 |
---|
| 89 | it cs |
---|
| 90 | cmpcs result, data2, S2HI #24 |
---|
| 91 | it eq |
---|
| 92 | S2LOEQ data2, data2, #8 |
---|
| 93 | beq 2b |
---|
| 94 | /* On a big-endian machine, RESULT contains the desired byte in bits |
---|
| 95 | 0-7; on a little-endian machine they are in bits 24-31. In |
---|
| 96 | both cases the other bits in RESULT are all zero. For DATA2 the |
---|
| 97 | interesting byte is at the other end of the word, but the |
---|
| 98 | other bits are not necessarily zero. We need a signed result |
---|
| 99 | representing the differnece in the unsigned bytes, so for the |
---|
| 100 | little-endian case we can't just shift the interesting bits |
---|
| 101 | up. */ |
---|
| 102 | #ifdef __ARM_BIG_ENDIAN |
---|
| 103 | sub result, result, data2, lsr #24 |
---|
| 104 | #else |
---|
| 105 | and data2, data2, #255 |
---|
| 106 | lsrs result, result, #24 |
---|
| 107 | subs result, result, data2 |
---|
| 108 | #endif |
---|
| 109 | bx lr |
---|
| 110 | |
---|
| 111 | |
---|
| 112 | #if 0 |
---|
| 113 | /* The assembly code below is based on the following alogrithm. */ |
---|
| 114 | #ifdef __ARM_BIG_ENDIAN |
---|
| 115 | #define RSHIFT << |
---|
| 116 | #define LSHIFT >> |
---|
| 117 | #else |
---|
| 118 | #define RSHIFT >> |
---|
| 119 | #define LSHIFT << |
---|
| 120 | #endif |
---|
| 121 | |
---|
| 122 | #define body(shift) \ |
---|
| 123 | mask = 0xffffffffU RSHIFT shift; \ |
---|
| 124 | data1 = *src1++; \ |
---|
| 125 | data2 = *src2++; \ |
---|
| 126 | do \ |
---|
| 127 | { \ |
---|
| 128 | tmp2 = data1 & mask; \ |
---|
| 129 | if (__builtin_expect(tmp2 != data2 RSHIFT shift, 0)) \ |
---|
| 130 | { \ |
---|
| 131 | data2 RSHIFT= shift; \ |
---|
| 132 | break; \ |
---|
| 133 | } \ |
---|
| 134 | if (__builtin_expect(((data1 - b1) & ~data1) & (b1 << 7), 0)) \ |
---|
| 135 | { \ |
---|
| 136 | /* See comment in assembler below re syndrome on big-endian */\ |
---|
| 137 | if ((((data1 - b1) & ~data1) & (b1 << 7)) & mask) \ |
---|
| 138 | data2 RSHIFT= shift; \ |
---|
| 139 | else \ |
---|
| 140 | { \ |
---|
| 141 | data2 = *src2; \ |
---|
| 142 | tmp2 = data1 RSHIFT (32 - shift); \ |
---|
| 143 | data2 = (data2 LSHIFT (32 - shift)) RSHIFT (32 - shift); \ |
---|
| 144 | } \ |
---|
| 145 | break; \ |
---|
| 146 | } \ |
---|
| 147 | data2 = *src2++; \ |
---|
| 148 | tmp2 ^= data1; \ |
---|
| 149 | if (__builtin_expect(tmp2 != data2 LSHIFT (32 - shift), 0)) \ |
---|
| 150 | { \ |
---|
| 151 | tmp2 = data1 >> (32 - shift); \ |
---|
| 152 | data2 = (data2 << (32 - shift)) RSHIFT (32 - shift); \ |
---|
| 153 | break; \ |
---|
| 154 | } \ |
---|
| 155 | data1 = *src1++; \ |
---|
| 156 | } while (1) |
---|
| 157 | |
---|
| 158 | const unsigned* src1; |
---|
| 159 | const unsigned* src2; |
---|
| 160 | unsigned data1, data2; |
---|
| 161 | unsigned mask; |
---|
| 162 | unsigned shift; |
---|
| 163 | unsigned b1 = 0x01010101; |
---|
| 164 | char c1, c2; |
---|
| 165 | unsigned tmp2; |
---|
| 166 | |
---|
| 167 | while (((unsigned) s1) & 3) |
---|
| 168 | { |
---|
| 169 | c1 = *s1++; |
---|
| 170 | c2 = *s2++; |
---|
| 171 | if (c1 == 0 || c1 != c2) |
---|
| 172 | return c1 - (int)c2; |
---|
| 173 | } |
---|
| 174 | src1 = (unsigned*) (((unsigned)s1) & ~3); |
---|
| 175 | src2 = (unsigned*) (((unsigned)s2) & ~3); |
---|
| 176 | tmp2 = ((unsigned) s2) & 3; |
---|
| 177 | if (tmp2 == 1) |
---|
| 178 | { |
---|
| 179 | body(8); |
---|
| 180 | } |
---|
| 181 | else if (tmp2 == 2) |
---|
| 182 | { |
---|
| 183 | body(16); |
---|
| 184 | } |
---|
| 185 | else |
---|
| 186 | { |
---|
| 187 | body (24); |
---|
| 188 | } |
---|
| 189 | |
---|
| 190 | do |
---|
| 191 | { |
---|
| 192 | #ifdef __ARM_BIG_ENDIAN |
---|
| 193 | c1 = (char) tmp2 >> 24; |
---|
| 194 | c2 = (char) data2 >> 24; |
---|
| 195 | #else /* not __ARM_BIG_ENDIAN */ |
---|
| 196 | c1 = (char) tmp2; |
---|
| 197 | c2 = (char) data2; |
---|
| 198 | #endif /* not __ARM_BIG_ENDIAN */ |
---|
| 199 | tmp2 RSHIFT= 8; |
---|
| 200 | data2 RSHIFT= 8; |
---|
| 201 | } while (c1 != 0 && c1 == c2); |
---|
| 202 | return c1 - c2; |
---|
| 203 | #endif /* 0 */ |
---|
| 204 | |
---|
| 205 | |
---|
| 206 | /* First of all, compare bytes until src1(sp1) is word-aligned. */ |
---|
| 207 | .Lstrcmp_unaligned: |
---|
| 208 | tst src1, #3 |
---|
| 209 | beq 2f |
---|
| 210 | ldrb data1, [src1], #1 |
---|
| 211 | ldrb data2, [src2], #1 |
---|
| 212 | cmp data1, #1 |
---|
| 213 | it cs |
---|
| 214 | cmpcs data1, data2 |
---|
| 215 | beq .Lstrcmp_unaligned |
---|
| 216 | sub result, data1, data2 |
---|
| 217 | bx lr |
---|
| 218 | |
---|
| 219 | 2: |
---|
| 220 | stmfd sp!, {r5} |
---|
| 221 | .cfi_def_cfa_offset 4 |
---|
| 222 | .cfi_offset 5, -4 |
---|
| 223 | |
---|
| 224 | ldr data1, [src1], #4 |
---|
| 225 | and tmp2, src2, #3 |
---|
| 226 | bic src2, src2, #3 |
---|
| 227 | ldr data2, [src2], #4 |
---|
| 228 | cmp tmp2, #2 |
---|
| 229 | beq .Loverlap2 |
---|
| 230 | bhi .Loverlap1 |
---|
| 231 | |
---|
| 232 | /* Critical inner Loop: Block with 3 bytes initial overlap */ |
---|
| 233 | .p2align 2 |
---|
| 234 | .Loverlap3: |
---|
| 235 | bic tmp2, data1, #MSB |
---|
| 236 | cmp tmp2, data2, S2LO #8 |
---|
| 237 | sub syndrome, data1, #0x01010101 |
---|
| 238 | bic syndrome, syndrome, data1 |
---|
| 239 | bne 4f |
---|
| 240 | ands syndrome, syndrome, #0x80808080 |
---|
| 241 | it eq |
---|
| 242 | ldreq data2, [src2], #4 |
---|
| 243 | bne 5f |
---|
| 244 | eor tmp2, tmp2, data1 |
---|
| 245 | cmp tmp2, data2, S2HI #24 |
---|
| 246 | bne 6f |
---|
| 247 | ldr data1, [src1], #4 |
---|
| 248 | b .Loverlap3 |
---|
| 249 | 4: |
---|
| 250 | S2LO data2, data2, #8 |
---|
| 251 | b .Lstrcmp_tail |
---|
| 252 | |
---|
| 253 | 5: |
---|
| 254 | #ifdef __ARM_BIG_ENDIAN |
---|
| 255 | /* The syndrome value may contain false ones if the string ends |
---|
| 256 | with the bytes 0x01 0x00. */ |
---|
| 257 | tst data1, #0xff000000 |
---|
| 258 | itt ne |
---|
| 259 | tstne data1, #0x00ff0000 |
---|
| 260 | tstne data1, #0x0000ff00 |
---|
| 261 | beq .Lstrcmp_done_equal |
---|
| 262 | #else |
---|
| 263 | bics syndrome, syndrome, #0xff000000 |
---|
| 264 | bne .Lstrcmp_done_equal |
---|
| 265 | #endif |
---|
| 266 | ldrb data2, [src2] |
---|
| 267 | S2LO tmp2, data1, #24 |
---|
| 268 | #ifdef __ARM_BIG_ENDIAN |
---|
| 269 | lsl data2, data2, #24 |
---|
| 270 | #endif |
---|
| 271 | b .Lstrcmp_tail |
---|
| 272 | |
---|
| 273 | 6: |
---|
| 274 | S2LO tmp2, data1, #24 |
---|
| 275 | and data2, data2, #LSB |
---|
| 276 | b .Lstrcmp_tail |
---|
| 277 | |
---|
| 278 | /* Critical inner Loop: Block with 2 bytes initial overlap. */ |
---|
| 279 | .p2align 2 |
---|
| 280 | .Loverlap2: |
---|
| 281 | S2HI tmp2, data1, #16 |
---|
| 282 | sub syndrome, data1, #0x01010101 |
---|
| 283 | S2LO tmp2, tmp2, #16 |
---|
| 284 | bic syndrome, syndrome, data1 |
---|
| 285 | cmp tmp2, data2, S2LO #16 |
---|
| 286 | bne 4f |
---|
| 287 | ands syndrome, syndrome, #0x80808080 |
---|
| 288 | it eq |
---|
| 289 | ldreq data2, [src2], #4 |
---|
| 290 | bne 5f |
---|
| 291 | eor tmp2, tmp2, data1 |
---|
| 292 | cmp tmp2, data2, S2HI #16 |
---|
| 293 | bne 6f |
---|
| 294 | ldr data1, [src1], #4 |
---|
| 295 | b .Loverlap2 |
---|
| 296 | |
---|
| 297 | 5: |
---|
| 298 | #ifdef __ARM_BIG_ENDIAN |
---|
| 299 | /* The syndrome value may contain false ones if the string ends |
---|
| 300 | with the bytes 0x01 0x00 */ |
---|
| 301 | tst data1, #0xff000000 |
---|
| 302 | it ne |
---|
| 303 | tstne data1, #0x00ff0000 |
---|
| 304 | beq .Lstrcmp_done_equal |
---|
| 305 | #else |
---|
| 306 | lsls syndrome, syndrome, #16 |
---|
| 307 | bne .Lstrcmp_done_equal |
---|
| 308 | #endif |
---|
| 309 | ldrh data2, [src2] |
---|
| 310 | S2LO tmp2, data1, #16 |
---|
| 311 | #ifdef __ARM_BIG_ENDIAN |
---|
| 312 | lsl data2, data2, #16 |
---|
| 313 | #endif |
---|
| 314 | b .Lstrcmp_tail |
---|
| 315 | |
---|
| 316 | 6: |
---|
| 317 | S2HI data2, data2, #16 |
---|
| 318 | S2LO tmp2, data1, #16 |
---|
| 319 | 4: |
---|
| 320 | S2LO data2, data2, #16 |
---|
| 321 | b .Lstrcmp_tail |
---|
| 322 | |
---|
| 323 | /* Critical inner Loop: Block with 1 byte initial overlap. */ |
---|
| 324 | .p2align 2 |
---|
| 325 | .Loverlap1: |
---|
| 326 | and tmp2, data1, #LSB |
---|
| 327 | cmp tmp2, data2, S2LO #24 |
---|
| 328 | sub syndrome, data1, #0x01010101 |
---|
| 329 | bic syndrome, syndrome, data1 |
---|
| 330 | bne 4f |
---|
| 331 | ands syndrome, syndrome, #0x80808080 |
---|
| 332 | it eq |
---|
| 333 | ldreq data2, [src2], #4 |
---|
| 334 | bne 5f |
---|
| 335 | eor tmp2, tmp2, data1 |
---|
| 336 | cmp tmp2, data2, S2HI #8 |
---|
| 337 | bne 6f |
---|
| 338 | ldr data1, [src1], #4 |
---|
| 339 | b .Loverlap1 |
---|
| 340 | 4: |
---|
| 341 | S2LO data2, data2, #24 |
---|
| 342 | b .Lstrcmp_tail |
---|
| 343 | 5: |
---|
| 344 | /* The syndrome value may contain false ones if the string ends |
---|
| 345 | with the bytes 0x01 0x00. */ |
---|
| 346 | tst data1, #LSB |
---|
| 347 | beq .Lstrcmp_done_equal |
---|
| 348 | ldr data2, [src2], #4 |
---|
| 349 | 6: |
---|
| 350 | S2LO tmp2, data1, #8 |
---|
| 351 | bic data2, data2, #MSB |
---|
| 352 | b .Lstrcmp_tail |
---|
| 353 | .Lstrcmp_done_equal: |
---|
| 354 | mov result, #0 |
---|
| 355 | .cfi_remember_state |
---|
| 356 | ldmfd sp!, {r5} |
---|
| 357 | .cfi_restore 5 |
---|
| 358 | .cfi_def_cfa_offset 0 |
---|
| 359 | bx lr |
---|
| 360 | |
---|
| 361 | .Lstrcmp_tail: |
---|
| 362 | .cfi_restore_state |
---|
| 363 | and r2, tmp2, #LSB |
---|
| 364 | and result, data2, #LSB |
---|
| 365 | cmp result, #1 |
---|
| 366 | it cs |
---|
| 367 | cmpcs result, r2 |
---|
| 368 | itt eq |
---|
| 369 | S2LOEQ tmp2, tmp2, #8 |
---|
| 370 | S2LOEQ data2, data2, #8 |
---|
| 371 | beq .Lstrcmp_tail |
---|
| 372 | sub result, r2, result |
---|
| 373 | ldmfd sp!, {r5} |
---|
| 374 | .cfi_restore 5 |
---|
| 375 | .cfi_def_cfa_offset 0 |
---|
| 376 | bx lr |
---|
| 377 | .cfi_endproc |
---|
| 378 | .size strcmp, . - strcmp |
---|