sysdeps/powerpc/powerpc64/strtok.S

   1 /* Optimized strtok 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 /* Performance gains are grabbed through following techniques:
  21
  22    > hashing of needle.
  23    > hashing avoids scanning of duplicate entries in needle
  24      across the string.
  25    > unrolling when scanning for character in string
  26      across hash table.  */
  27
  28 /* Algorithm is as below:
  29    1. A empty hash table/dictionary is created comprising of
  30       256 ascii character set
  31    2. When hash entry is found in needle , the hash index
  32       is initialized to 1
  33    3. The string is scanned until end and for every character,
  34       its corresponding hash index is compared.
  35    4. initial length of string (count) until first hit of
  36       accept needle is calculated and moved.(strspn)
  37    5. The string is again scanned until end and for every character,
  38       its corresponding hash index is compared.(strpbrk)
  39    6. If hash index is set to 1 for the index of string,
  40       set it to null and set the saveptr to point to the next char.
  41    7. Otherwise count is incremented and scanning continues
  42       until end of string.  */
  43
  44 #include <sysdep.h>
  45 #ifdef USE_AS_STRTOK_R
  46 # define FUNC_NAME __strtok_r
  47 #else
  48 # define FUNC_NAME strtok
  49 #endif
  50
  51 EALIGN(FUNC_NAME, 4, 0)
  52 #ifdef USE_AS_STRTOK_R
  53         CALL_MCOUNT     3
  54         cmpdi   cr7, r3, 0              /* Is input null? */
  55         bne     cr7, L(inputnotNull)
  56         ld      r3, 0(r5)               /* Load from r5 */
  57 #else
  58         CALL_MCOUNT     2
  59         addis   r5, r2, .LANCHOR0@toc@ha
  60         cmpdi   cr7, r3, 0              /* Is r3 NULL? */
  61         bne     cr7, L(inputnotNull)
  62         ld      r3, .LANCHOR0@toc@l(r5) /* Load from saveptr */
  63 #endif
  64 L(inputnotNull):
  65         mr      r7, r3
  66         cmpdi   cr7, r3, 0
  67         beq     cr7, L(returnNULL)
  68         lbz     r8, 0(r3)
  69         cmpdi   cr7, r8, 0
  70         beq     cr7, L(returnNULL)
  71
  72         addi    r9, r1, -256    /* r9 is a hash of 256 bytes  */
  73
  74         /*Iniatliaze hash table with Zeroes */
  75         li      r6, 0
  76         li      r8, 4
  77         mtctr   r8
  78         mr      r10, r9
  79         .align  4
  80 L(zerohash):
  81         std     r6, 0(r10)
  82         std     r6, 8(r10)
  83         std     r6, 16(r10)
  84         std     r6, 24(r10)
  85         std     r6, 32(r10)
  86         std     r6, 40(r10)
  87         std     r6, 48(r10)
  88         std     r6, 56(r10)
  89         addi    r10, r10, 64
  90         bdnz    L(zerohash)
  91
  92
  93         lbz     r10, 0(r4)      /* load r10 with needle (r4)  */
  94         li      r8, 1           /* r8=1, marker into hash if found in
  95                                    needle  */
  96
  97         cmpdi   cr7, r10, 0     /* accept needle is NULL  */
  98         beq     cr7, L(skipHashing)     /* if needle is NULL, skip hashing  */
  99
 100         .align 4                /* align section to 16 byte boundary  */
 101 L(hashing):
 102         stbx    r8, r9, r10     /* update hash with marker for the pivot of
 103                                    the needle  */
 104         lbzu    r10, 1(r4)      /* load needle into r10 and update to next  */
 105         cmpdi   cr7, r10, 0     /* if needle is has reached NULL, continue  */
 106         bne     cr7, L(hashing) /* loop to hash the needle  */
 107
 108 L(skipHashing):
 109         b       L(beginScan)
 110
 111         .align 4                /* align section to 16 byte boundary  */
 112 L(scanUnroll):
 113         lbzx    r8, r9, r8      /* load r8 with hash value at index  */
 114         cmpwi   cr7, r8, 0      /* check the hash  value */
 115         beq     cr7, L(ret1stIndex)     /* we have hit accept needle */
 116
 117         lbz     r8, 1(r7)       /* load string[1] into r8  */
 118         lbzx    r8, r9, r8      /* load r8 with hash value at index  */
 119         cmpwi   cr7, r8, 0      /* check the hash  value */
 120         beq     cr7, L(ret2ndIndex)     /* we have hit accept needle */
 121
 122         lbz     r8, 2(r7)       /* load string[1] into r8  */
 123         lbzx    r8, r9, r8      /* load r8 with hash value at index  */
 124         cmpwi   cr7, r8, 0      /* check the hash  value */
 125         beq     cr7, L(ret3rdIndex)     /* we have hit accept needle */
 126
 127         lbz     r8, 3(r7)       /* load string[1] into r8  */
 128         addi    r7, r7, 4
 129         lbzx    r8, r9, r8      /* load r8 with hash value at index  */
 130         cmpwi   cr7, r8, 0      /* check the hash  value */
 131         beq     cr7,L(ret4thIndex)      /* we have hit accept needle */
 132
 133 L(beginScan):
 134         lbz     r8, 0(r7)       /* load string[0] into r8  */
 135         addi    r6, r7, 1
 136         addi    r11, r7, 2
 137         addi    r4, r7, 3
 138         cmpdi   cr7, r8, 0      /*  check if its null */
 139         bne     cr7, L(scanUnroll)      /* continue scanning  */
 140
 141 L(ret1stIndex):
 142         mr      r3, r7
 143         b       L(next)
 144 L(ret2ndIndex):
 145         mr      r3, r6
 146         b       L(next)
 147 L(ret3rdIndex):
 148         mr      r3, r11
 149         b       L(next)
 150 L(ret4thIndex):
 151         mr      r3, r4
 152 L(next):
 153         mr      r7, r3
 154         lbz     r8, 0(r7)
 155         cmpdi   cr7, r8, 0
 156         beq     cr7, L(returnNULL)
 157         li      r8, 1
 158         li      r10, 0          /* load counter = 0  */
 159         stbx    r8, r9, r10     /* update hash for NULL */
 160         b       L(mainloop)
 161
 162 L(unroll):
 163         lbz     r8, 1(r7)       /* load string[1] into r8  */
 164         lbzx    r8, r9, r8      /* load r8 with hash value at index  */
 165         cmpwi   r7, r8, 1       /* check the hash */
 166         beq     cr7, L(foundat1st)      /* we have hit accept needle */
 167         lbz     r8, 2(r7)
 168         lbzx    r8, r9, r8
 169         cmpwi   cr7, r8, 1
 170         beq     cr7, L(foundat2nd)
 171         lbz     r8, 3(r7)
 172         addi    r7, r7, 4
 173         lbzx    r8, r9, r8
 174         cmpwi   cr7, r8, 1
 175         beq     cr7, L(foundat3rd)
 176 L(mainloop):
 177         lbz     r8, 0(r7)
 178         addi    r6, r7, 1
 179         addi    r11, r7, 2
 180         addi    r4, r7, 3
 181         lbzx    r8, r9, r8
 182         cmpwi   cr7, r8, 1
 183         bne     cr7, L(unroll)  /* continue scanning  */
 184
 185         b       L(found)
 186 L(foundat1st):
 187         mr      r7, r6
 188         b       L(found)
 189 L(foundat2nd):
 190         mr      r7, r11
 191         b       L(found)
 192 L(foundat3rd):
 193         mr      r7, r4
 194 L(found):
 195         lbz     r8, 0(r7)
 196         cmpdi   cr7, r8, 0
 197         beq     cr7, L(end)
 198         li      r10, 0
 199         stb     r10, 0(r7)      /* Terminate string */
 200         addi    r7, r7, 1       /* Store the pointer to the next char */
 201 L(end):
 202 #ifdef USE_AS_STRTOK_R
 203         std     r7, 0(r5)       /* Update saveptr */
 204 #else
 205         std     r7, .LANCHOR0@toc@l(r5)
 206 #endif
 207         blr                     /* done  */
 208 L(returnNULL):
 209 #ifndef USE_AS_STRTOK_R
 210         li      r7, 0
 211 #endif
 212         li      r3, 0           /* return NULL */
 213         b       L(end)
 214 END(FUNC_NAME)
 215 #ifdef USE_AS_STRTOK_R
 216 libc_hidden_builtin_def (strtok_r)
 217 #else
 218         .section        ".bss"
 219         .align 3
 220         .set    .LANCHOR0,. + 0
 221         .type   olds, @object
 222         .size   olds, 8
 223 olds:
 224         .zero   8
 225 libc_hidden_builtin_def (strtok)
 226 #endif