sysdeps/powerpc/powerpc64/power7/strstr.S

   1 /* Optimized strstr implementation for PowerPC64/POWER7.
   2    Copyright (C) 2015-2017 Free Software Foundation, Inc.
   3    This file is part of the GNU C Library.
   4
   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.
   9
  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.
  14
  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/>.  */
  18
  19 #include <sysdep.h>
  20
  21 /* Char * [r3] strstr (char *s [r3], char * pat[r4])  */
  22
  23 /* The performance gain is obtained using aligned memory access, load
  24  * doubleword and usage of cmpb instruction for quicker comparison.  */
  25
  26 #define ITERATIONS      64
  27
  28 #ifndef STRLEN
  29 /* For builds with no IFUNC support, local calls should be made to internal
  30    GLIBC symbol (created by libc_hidden_builtin_def).  */
  31 # ifdef SHARED
  32 #  define STRLEN   __GI_strlen
  33 # else
  34 #  define STRLEN   strlen
  35 # endif
  36 #endif
  37
  38 #ifndef STRNLEN
  39 /* For builds with no IFUNC support, local calls should be made to internal
  40    GLIBC symbol (created by libc_hidden_builtin_def).  */
  41 # ifdef SHARED
  42 #  define STRNLEN   __GI_strnlen
  43 # else
  44 #  define STRNLEN  __strnlen
  45 # endif
  46 #endif
  47
  48 #ifndef STRCHR
  49 # ifdef SHARED
  50 #  define STRCHR   __GI_strchr
  51 # else
  52 #  define STRCHR   strchr
  53 # endif
  54 #endif
  55
  56 #define FRAMESIZE       (FRAME_MIN_SIZE+32)
  57         .machine  power7
  58 EALIGN (strstr, 4, 0)
  59         CALL_MCOUNT 2
  60         mflr    r0                      /* Load link register LR to r0.  */
  61         std     r31, -8(r1)             /* Save callers register r31.  */
  62         std     r30, -16(r1)            /* Save callers register r30.  */
  63         std     r29, -24(r1)            /* Save callers register r29.  */
  64         std     r28, -32(r1)            /* Save callers register r28.  */
  65         std     r0, 16(r1)              /* Store the link register.  */
  66         cfi_offset(r31, -8)
  67         cfi_offset(r30, -16)
  68         cfi_offset(r28, -32)
  69         cfi_offset(r29, -24)
  70         cfi_offset(lr, 16)
  71         stdu    r1, -FRAMESIZE(r1)      /* Create the stack frame.  */
  72         cfi_adjust_cfa_offset(FRAMESIZE)
  73
  74         dcbt    0, r3
  75         dcbt    0, r4
  76         cmpdi   cr7, r3, 0
  77         beq     cr7, L(retnull)
  78         cmpdi   cr7, r4, 0
  79         beq     cr7, L(retnull)
  80
  81         mr      r29, r3
  82         mr      r30, r4
  83         mr      r3, r4
  84         bl      STRLEN
  85         nop
  86
  87         cmpdi   cr7, r3, 0      /* If search str is null.  */
  88         beq     cr7, L(ret_r3)
  89
  90         mr      r31, r3
  91         mr      r4, r3
  92         mr      r3, r29
  93         bl      STRNLEN
  94         nop
  95
  96         cmpd    cr7, r3, r31    /* If len(r3) < len(r4).  */
  97         blt     cr7, L(retnull)
  98         mr      r3, r29
  99         lbz     r4, 0(r30)
 100         bl      STRCHR
 101         nop
 102
 103         mr      r11, r3
 104         /* If first char of search str is not present.  */
 105         cmpdi   cr7, r3, 0
 106         ble     cr7, L(end)
 107         /* Reg r28 is used to count the number of iterations. */
 108         li      r28, 0
 109         rldicl  r8, r3, 0, 52   /* Page cross check.  */
 110         cmpldi  cr7, r8, 4096-16
 111         bgt     cr7, L(bytebybyte)
 112
 113         rldicl  r8, r30, 0, 52
 114         cmpldi  cr7, r8, 4096-16
 115         bgt     cr7, L(bytebybyte)
 116
 117         /* If len(r4) < 8 handle in a different way.  */
 118         /* Shift position based on null and use cmpb.  */
 119         cmpdi   cr7, r31, 8
 120         blt     cr7, L(lessthan8)
 121
 122         /* Len(r4) >= 8 reaches here.  */
 123         mr      r8, r3          /* Save r3 for future use.  */
 124         mr      r4, r30         /* Restore r4.  */
 125         li      r0, 0
 126         rlwinm  r10, r30, 3, 26, 28     /* Calculate padding in bits.  */
 127         clrrdi  r4, r4, 3       /* Make r4 aligned to 8.  */
 128         ld      r6, 0(r4)
 129         addi    r4, r4, 8
 130         cmpdi   cr7, r10, 0     /* Check if its already aligned?  */
 131         beq     cr7, L(begin1)
 132 #ifdef __LITTLE_ENDIAN__
 133         srd     r6, r6, r10     /* Discard unwanted bits.  */
 134 #else
 135         sld     r6, r6, r10
 136 #endif
 137         ld      r9, 0(r4)
 138         subfic  r10, r10, 64
 139 #ifdef __LITTLE_ENDIAN__
 140         sld     r9, r9, r10     /* Discard unwanted bits.  */
 141 #else
 142         srd     r9, r9, r10
 143 #endif
 144         or      r6, r6, r9      /* Form complete search str.  */
 145 L(begin1):
 146         mr      r29, r6
 147         rlwinm  r10, r3, 3, 26, 28
 148         clrrdi  r3, r3, 3
 149         ld      r5, 0(r3)
 150         cmpb    r9, r0, r6      /* Check if input has null.  */
 151         cmpdi   cr7, r9, 0
 152         bne     cr7, L(return3)
 153         cmpb    r9, r0, r5      /* Check if input has null.  */
 154 #ifdef __LITTLE_ENDIAN__
 155         srd     r9, r9, r10
 156 #else
 157         sld     r9, r9, r10
 158 #endif
 159         cmpdi   cr7, r9, 0
 160         bne     cr7, L(retnull)
 161
 162         li      r12, -8         /* Shift values.  */
 163         li      r11, 72         /* Shift values.  */
 164         cmpdi   cr7, r10, 0
 165         beq     cr7, L(nextbyte1)
 166         mr      r12, r10
 167         addi    r12, r12, -8
 168         subfic  r11, r12, 64
 169
 170 L(nextbyte1):
 171         ldu     r7, 8(r3)       /* Load next dw.  */
 172         addi    r12, r12, 8     /* Shift one byte and compare.  */
 173         addi    r11, r11, -8
 174 #ifdef __LITTLE_ENDIAN__
 175         srd     r9, r5, r12     /* Rotate based on mask.  */
 176         sld     r10, r7, r11
 177 #else
 178         sld     r9, r5, r12
 179         srd     r10, r7, r11
 180 #endif
 181         /* Form single dw from few bytes on first load and second load.  */
 182         or      r10, r9, r10
 183         /* Check for null in the formed dw.  */
 184         cmpb    r9, r0, r10
 185         cmpdi   cr7, r9, 0
 186         bne     cr7, L(retnull)
 187         /* Cmpb search str and input str.  */
 188         cmpb    r9, r10, r6
 189         cmpdi   cr7, r9, -1
 190         beq     cr7, L(match)
 191         addi    r8, r8, 1
 192         b       L(begin)
 193
 194         .align  4
 195 L(match):
 196         /* There is a match of 8 bytes, check next bytes.  */
 197         cmpdi   cr7, r31, 8
 198         beq     cr7, L(return)
 199         /* Update next starting point r8.  */
 200         srdi    r9, r11, 3
 201         subf    r9, r9, r3
 202         mr      r8, r9
 203
 204 L(secondmatch):
 205         mr      r5, r7
 206         rlwinm  r10, r30, 3, 26, 28     /* Calculate padding in bits.  */
 207         ld      r6, 0(r4)
 208         addi    r4, r4, 8
 209         cmpdi   cr7, r10, 0     /* Check if its already aligned?  */
 210         beq     cr7, L(proceed3)
 211 #ifdef __LITTLE_ENDIAN__
 212         srd     r6, r6, r10     /* Discard unwanted bits.  */
 213         cmpb    r9, r0, r6
 214         sld     r9, r9, r10
 215 #else
 216         sld     r6, r6, r10
 217         cmpb    r9, r0, r6
 218         srd     r9, r9, r10
 219 #endif
 220         cmpdi   cr7, r9, 0
 221         bne     cr7, L(proceed3)
 222         ld      r9, 0(r4)
 223         subfic  r10, r10, 64
 224 #ifdef __LITTLE_ENDIAN__
 225         sld     r9, r9, r10     /* Discard unwanted bits.  */
 226 #else
 227         srd     r9, r9, r10
 228 #endif
 229         or      r6, r6, r9      /* Form complete search str.  */
 230
 231 L(proceed3):
 232         li      r7, 0
 233         addi    r3, r3, 8
 234         cmpb    r9, r0, r5
 235         cmpdi   cr7, r9, 0
 236         bne     cr7, L(proceed4)
 237         ld      r7, 0(r3)
 238 L(proceed4):
 239 #ifdef __LITTLE_ENDIAN__
 240         srd     r9, r5, r12
 241         sld     r10, r7, r11
 242 #else
 243         sld     r9, r5, r12
 244         srd     r10, r7, r11
 245 #endif
 246         /* Form single dw with few bytes from first and second load.  */
 247         or      r10, r9, r10
 248         cmpb    r9, r0, r6
 249         cmpdi   cr7, r9, 0
 250         bne     cr7, L(return4)
 251         /* Check for null in the formed dw.  */
 252         cmpb    r9, r0, r10
 253         cmpdi   cr7, r9, 0
 254         bne     cr7, L(retnull)
 255         /* If the next 8 bytes dont match, start search again.  */
 256         cmpb    r9, r10, r6
 257         cmpdi   cr7, r9, -1
 258         bne     cr7, L(reset)
 259         /* If the next 8 bytes match, load and compare next 8.  */
 260         b       L(secondmatch)
 261
 262         .align  4
 263 L(reset):
 264         /* Start the search again.  */
 265         addi    r8, r8, 1
 266         b       L(begin)
 267
 268         .align  4
 269 L(return3):
 270         /* Count leading zeros and compare partial dw.  */
 271 #ifdef __LITTLE_ENDIAN__
 272         addi    r7, r9, -1
 273         andc    r7, r7, r9
 274         popcntd r7, r7
 275         subfic  r7, r7, 64
 276         sld     r10, r5, r7
 277         sld     r6, r6, r7
 278 #else
 279         cntlzd  r7, r9
 280         subfic  r7, r7, 64
 281         srd     r10, r5, r7
 282         srd     r6, r6, r7
 283 #endif
 284         cmpb    r9, r10, r6
 285         cmpdi   cr7, r9, -1
 286         addi    r8, r8, 1
 287         /* Start search again if there is no match.  */
 288         bne     cr7, L(begin)
 289         /* If the words match, update return values.  */
 290         subfic  r7, r7, 64
 291         srdi    r7, r7, 3
 292         add     r3, r3, r7
 293         subf    r3, r31, r3
 294         b       L(end)
 295
 296         .align  4
 297 L(return4):
 298         /* Count leading zeros and compare partial dw.  */
 299 #ifdef __LITTLE_ENDIAN__
 300         addi    r7, r9, -1
 301         andc    r7, r7, r9
 302         popcntd r7, r7
 303         subfic  r7, r7, 64
 304         sld     r10, r10, r7
 305         sld     r6, r6, r7
 306 #else
 307         cntlzd  r7, r9
 308         subfic  r7, r7, 64
 309         srd     r10, r10, r7
 310         srd     r6, r6, r7
 311 #endif
 312         cmpb    r9, r10, r6
 313         cmpdi   cr7, r9, -1
 314         addi    r8, r8, 1
 315         bne     cr7, L(begin)
 316         subfic  r7, r7, 64
 317         srdi    r11, r11, 3
 318         subf    r3, r11, r3
 319         srdi    r7, r7, 3
 320         add     r3, r3, r7
 321         subf    r3, r31, r3
 322         b       L(end)
 323
 324         .align  4
 325 L(begin):
 326         mr      r3, r8
 327         /* When our iterations exceed ITERATIONS,fall back to default. */
 328         addi    r28, r28, 1
 329         cmpdi   cr7, r28, ITERATIONS
 330         beq     cr7, L(default)
 331         lbz     r4, 0(r30)
 332         bl      STRCHR
 333         nop
 334         /* If first char of search str is not present.  */
 335         cmpdi   cr7, r3, 0
 336         ble     cr7, L(end)
 337         mr      r8, r3
 338         mr      r4, r30         /* Restore r4.  */
 339         li      r0, 0
 340         mr      r6, r29
 341         clrrdi  r4, r4, 3
 342         addi    r4, r4, 8
 343         b       L(begin1)
 344
 345         /* Handle less than 8 search string.  */
 346         .align  4
 347 L(lessthan8):
 348         mr      r4, r3
 349         mr      r9, r30
 350         li      r0, 0
 351
 352         rlwinm  r10, r9, 3, 26, 28      /* Calculate padding in bits.  */
 353         srdi    r8, r10, 3      /* Padding in bytes.  */
 354         clrrdi  r9, r9, 3       /* Make r4 aligned to 8.  */
 355         ld      r6, 0(r9)
 356         cmpdi   cr7, r10, 0     /* Check if its already aligned?  */
 357         beq     cr7, L(proceed2)
 358 #ifdef __LITTLE_ENDIAN__
 359         srd     r6, r6, r10     /* Discard unwanted bits.  */
 360 #else
 361         sld     r6, r6, r10
 362 #endif
 363         subfic  r8, r8, 8
 364         cmpd    cr7, r8, r31    /* Next load needed?  */
 365         bge     cr7, L(proceed2)
 366         ld      r7, 8(r9)
 367         subfic  r10, r10, 64
 368 #ifdef __LITTLE_ENDIAN__
 369         sld     r7, r7, r10     /* Discard unwanted bits.  */
 370 #else
 371         srd     r7, r7, r10
 372 #endif
 373         or      r6, r6, r7      /* Form complete search str.  */
 374 L(proceed2):
 375         mr      r29, r6
 376         rlwinm  r10, r3, 3, 26, 28
 377         clrrdi  r7, r3, 3       /* Make r3 aligned.  */
 378         ld      r5, 0(r7)
 379         sldi    r8, r31, 3
 380         subfic  r8, r8, 64
 381 #ifdef __LITTLE_ENDIAN__
 382         sld     r6, r6, r8
 383         cmpb    r9, r0, r5
 384         srd     r9, r9, r10
 385 #else
 386         srd     r6, r6, r8
 387         cmpb    r9, r0, r5
 388         sld     r9, r9, r10
 389 #endif
 390         cmpdi   cr7, r9, 0
 391         bne     cr7, L(noload)
 392         cmpdi   cr7, r10, 0
 393         beq     cr7, L(continue)
 394         ld      r7, 8(r7)
 395 L(continue1):
 396         mr      r12, r10
 397         addi    r12, r12, -8
 398         subfic  r11, r12, 64
 399         b       L(nextbyte)
 400
 401         .align  4
 402 L(continue):
 403         ld      r7, 8(r7)
 404         li      r12, -8         /* Shift values.  */
 405         li      r11, 72         /* Shift values.  */
 406 L(nextbyte):
 407         addi    r12, r12, 8     /* Mask for rotation.  */
 408         addi    r11, r11, -8
 409 #ifdef __LITTLE_ENDIAN__
 410         srd     r9, r5, r12
 411         sld     r10, r7, r11
 412         or      r10, r9, r10
 413         sld     r10, r10, r8
 414         cmpb    r9, r0, r10
 415         srd     r9, r9, r8
 416 #else
 417         sld     r9, r5, r12
 418         srd     r10, r7, r11
 419         or      r10, r9, r10
 420         srd     r10, r10, r8
 421         cmpb    r9, r0, r10
 422         sld     r9, r9, r8
 423 #endif
 424         cmpdi   cr7, r9, 0
 425         bne     cr7, L(retnull)
 426         cmpb    r9, r10, r6
 427         cmpdi   cr7, r9, -1
 428         beq     cr7, L(end)
 429         addi    r3, r4, 1
 430         /* When our iterations exceed ITERATIONS,fall back to default. */
 431         addi    r28, r28, 1
 432         cmpdi   cr7, r28, ITERATIONS
 433         beq     cr7, L(default)
 434         lbz     r4, 0(r30)
 435         bl      STRCHR
 436         nop
 437         /* If first char of search str is not present.  */
 438         cmpdi   cr7, r3, 0
 439         ble     cr7, L(end)
 440         mr      r4, r3
 441         mr      r6, r29
 442         li      r0, 0
 443         b       L(proceed2)
 444
 445         .align  4
 446 L(noload):
 447         /* Reached null in r3, so skip next load.  */
 448         li      r7, 0
 449         b       L(continue1)
 450
 451         .align  4
 452 L(return):
 453         /* Update return values.  */
 454         srdi    r9, r11, 3
 455         subf    r3, r9, r3
 456         b       L(end)
 457
 458         /* Handling byte by byte.  */
 459         .align  4
 460 L(bytebybyte):
 461         mr      r8, r3
 462         addi    r8, r8, -1
 463 L(loop1):
 464         addi    r8, r8, 1
 465         mr      r3, r8
 466         mr      r4, r30
 467         lbz     r6, 0(r4)
 468         cmpdi   cr7, r6, 0
 469         beq     cr7, L(updater3)
 470 L(loop):
 471         lbz     r5, 0(r3)
 472         cmpdi   cr7, r5, 0
 473         beq     cr7, L(retnull)
 474         cmpld   cr7, r6, r5
 475         bne     cr7, L(loop1)
 476         addi    r3, r3, 1
 477         addi    r4, r4, 1
 478         lbz     r6, 0(r4)
 479         cmpdi   cr7, r6, 0
 480         beq     cr7, L(updater3)
 481         b       L(loop)
 482
 483         /* Handling return values.  */
 484         .align  4
 485 L(updater3):
 486         subf    r3, r31, r3     /* Reduce len of r4 from r3.  */
 487         b       L(end)
 488
 489         .align  4
 490 L(ret_r3):
 491         mr      r3, r29         /* Return r3.  */
 492         b       L(end)
 493
 494         .align  4
 495 L(retnull):
 496         li      r3, 0           /* Return NULL.  */
 497         b       L(end)
 498
 499         .align  4
 500 L(default):
 501         mr      r4, r30
 502         bl      __strstr_ppc
 503         nop
 504
 505         .align  4
 506 L(end):
 507         addi    r1, r1, FRAMESIZE       /* Restore stack pointer.  */
 508         cfi_adjust_cfa_offset(-FRAMESIZE)
 509         ld      r0, 16(r1)      /* Restore the saved link register.  */
 510         ld      r28, -32(r1)    /* Restore callers save register r28.  */
 511         ld      r29, -24(r1)    /* Restore callers save register r29.  */
 512         ld      r30, -16(r1)    /* Restore callers save register r30.  */
 513         ld      r31, -8(r1)     /* Restore callers save register r31.  */
 514         mtlr    r0              /* Branch to link register.  */
 515         blr
 516 END (strstr)
 517 libc_hidden_builtin_def (strstr)