sysdeps/powerpc/powerpc64/strspn.S

   1 /* Optimized strspn implementation for PowerPC64.
   2
   3    Copyright (C) 2014-2015 Free Software Foundation, Inc.
   4    This file is part of the GNU C Library.
   5
   6    The GNU C Library is free software; you can redistribute it and/or
   7    modify it under the terms of the GNU Lesser General Public
   8    License as published by the Free Software Foundation; either
   9    version 2.1 of the License, or (at your option) any later version.
  10
  11    The GNU C Library is distributed in the hope that it will be useful,
  12    but WITHOUT ANY WARRANTY; without even the implied warranty of
  13    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14    Lesser General Public License for more details.
  15
  16    You should have received a copy of the GNU Lesser General Public
  17    License along with the GNU C Library; if not, see
  18    <http://www.gnu.org/licenses/>.  */
  19
  20 /* size_t [r3] strspn (const char *string [r3],
  21                        const char *needleAccept [r4]  */
  22
  23 /* Performance gains are grabbed through following techniques:
  24
  25    > hashing of needle.
  26    > hashing avoids scanning of duplicate entries in needle
  27      across the string.
  28    > unrolling when scanning for character in string
  29      across hash table.  */
  30
  31 /* Algorithm is as below:
  32    1. A empty hash table/dictionary is created comprising of
  33       256 ascii character set
  34    2. When hash entry is found in needle , the hash index
  35       is initialized to 1
  36    3. The string is scanned until end and for every character,
  37       its corresponding hash index is compared.
  38    4. initial length of string (count) until first hit of
  39       accept needle to be found is set to 0
  40    4. If hash index is set to 1 for the index of string,
  41       count is returned.
  42    5. Otherwise count is incremented and scanning continues
  43       until end of string.  */
  44
  45 #include <sysdep.h>
  46
  47 EALIGN(strspn, 4, 0)
  48         CALL_MCOUNT 3
  49
  50         /* PPC64 ELF ABI stack is aligned to 16 bytes.  */
  51         addi    r9,r1,-256
  52         /* Clear the table with 0 values  */
  53         li      r6, 0
  54         li      r8, 4
  55         mtctr   r8
  56         mr      r10, r9
  57         .align  4
  58 L(zerohash):
  59         std     r6, 0(r10)
  60         std     r6, 8(r10)
  61         std     r6, 16(r10)
  62         std     r6, 24(r10)
  63         std     r6, 32(r10)
  64         std     r6, 40(r10)
  65         std     r6, 48(r10)
  66         std     r6, 56(r10)
  67         addi    r10, r10, 64
  68         bdnz    L(zerohash)
  69
  70         lbz     r10,0(r4)
  71         li r8, 1                /* r8=1, marker into hash if found in
  72                                    needle  */
  73         cmpdi cr7, r10, 0       /* accept needle is NULL  */
  74         beq cr7, L(skipHashing) /* if needle is NULL, skip hashing  */
  75
  76         .align 4                /* align section to 16 byte boundary  */
  77 L(hashing):
  78         stbx r8, r9, r10        /* update hash with marker for the pivot of
  79                                    the needle  */
  80         lbzu r10, 1(r4)         /* load needle into r10 and update to next  */
  81         cmpdi cr7, r10, 0       /* if needle is has reached NULL, continue  */
  82         bne cr7, L(hashing)     /* loop to hash the needle  */
  83
  84 L(skipHashing):
  85         li r10, 0               /* load counter = 0  */
  86         b L(beginScan)
  87
  88         .align 4                /* align section to 16 byte boundary  */
  89 L(scanUnroll):
  90         lbzx r8, r9, r8         /* load r8 with hash value at index  */
  91         cmpwi cr7, r8, 0        /* if we hit marker in hash, we have found
  92                                    accept needle  */
  93         beq cr7, L(ret1stIndex) /* we have hit accept needle, return the
  94                                    count  */
  95
  96         lbz r8, 1(r3)           /* load string[1] into r8  */
  97         addi r10, r10, 4        /* increment counter  */
  98         lbzx r8, r9, r8         /* load r8 with hash value at index  */
  99         cmpwi cr7, r8, 0        /* if we hit marker in hash, we have found
 100                                    accept needle  */
 101         beq cr7, L(ret2ndIndex) /* we have hit accept needle, return the
 102                                    count  */
 103
 104         lbz r8, 2(r3)           /* load string[2] into r8  */
 105         lbzx r8, r9, r8         /* load r8 with hash value at index  */
 106         cmpwi cr7, r8, 0        /* if we hit marker in hash, we have found
 107                                    accept needle  */
 108         beq cr7, L(ret3rdIndex) /* we have hit accept needle, return the
 109                                    count  */
 110
 111         lbz r8, 3(r3)           /* load string[3] into r8  */
 112         lbzx r8, r9, r8         /* load r8 with hash value at index  */
 113         addi r3, r3, 4          /* unroll factor , increment string by 4  */
 114         cmpwi cr7, r8, 0        /* if we hit marker in hash, we have found
 115                                    accept needle  */
 116         beq cr7,L(ret4thIndex)  /* we have hit accept needle, return the
 117                                    count  */
 118
 119 L(beginScan):
 120         lbz r8, 0(r3)           /* load string[0] into r8  */
 121         addi r6, r10, 1         /* place holder for counter + 1  */
 122         addi r5, r10, 2         /* place holder for counter + 2  */
 123         addi r4, r10, 3         /* place holder for counter + 3  */
 124         cmpdi cr7, r8, 0        /* if we hit marker in hash, we have found
 125                                    accept needle  */
 126         bne cr7, L(scanUnroll)  /* continue scanning  */
 127
 128 L(ret1stIndex):
 129         mr r3, r10              /* update r3 for return  */
 130         blr                     /* return  */
 131
 132 L(ret2ndIndex):
 133         mr r3, r6               /* update r3 for return  */
 134         blr                     /* return  */
 135
 136 L(ret3rdIndex):
 137         mr r3, r5               /* update r3 for return  */
 138         blr                     /* return  */
 139
 140 L(ret4thIndex):
 141         mr r3, r4               /* update r3 for return  */
 142         blr                     /* done  */
 143 END(strspn)
 144 libc_hidden_builtin_def (strspn)