arm/string/strstr.s

   1 /*
   2  * Copyright (c) 2010, Apple Inc. All rights reserved.
   3  *
   4  * @APPLE_LICENSE_HEADER_START@
   5  *
   6  * This file contains Original Code and/or Modifications of Original Code
   7  * as defined in and that are subject to the Apple Public Source License
   8  * Version 2.0 (the 'License'). You may not use this file except in
   9  * compliance with the License. Please obtain a copy of the License at
  10  * http://www.opensource.apple.com/apsl/ and read it before using this
  11  * file.
  12  *
  13  * The Original Code and all software distributed under the License are
  14  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  15  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  16  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  18  * Please see the License for the specific language governing rights and
  19  * limitations under the License.
  20  *
  21  * @APPLE_LICENSE_HEADER_END@
  22  */
  23
  24 //  char * strstr(const char *s1, const char *s2);
  25 //
  26 //  If s2 is empty, s1 is returned.
  27 //  If s2 does not occur in s1, NULL is returned.
  28 //  Otherwise, a pointer to the first character of the first occurrence of s2
  29 //  in s1 is returned.
  30 //
  31 //  We use a hand-tuned version of the naive quadratic time algorithm; we have
  32 //  experimented with more sophisticated algorithms, however they have been
  33 //  found wanting.  The increased startup cost combines with the frequency of
  34 //  calls to strstr with small strings to swamp the gains from improved
  35 //  asymptotic complexity.
  36
  37 #define CLEAR_FRAME_AND_RETURN \
  38     pop    {r4,r5,r6,r7,pc}
  39
  40 .text
  41 .syntax unified
  42 .code 32
  43 .globl _strstr
  44 .align 2
  45 _strstr:
  46     push   {r4,r5,r6,r7,lr}
  47     add     r7,     sp, #12
  48
  49 //  Throughout this function, I will refer to the string in which we are
  50 //  searching as "string" and the string for which we are searching as "word".
  51 //  Using s1 and s2 is too confusing.  Thus, we want to return a pointer to
  52 //  the first occurrence of "word" in "string".
  53     mov     r5,     r1
  54     mov     r4,     r0
  55
  56 //  We begin by calling strlen to find the length of "word".  We also handle
  57 //  two special cases here: we early-out if word is an empty string (length
  58 //  zero), and we call strchr if word is only a single character.
  59     mov     r0,     r5
  60     bl      _strlen
  61     subs    r0,     r0, #1
  62     ble     L_tinyWord
  63
  64 //  Load the first character of word
  65     ldrb    ip,    [r5]
  66
  67 L_lookForFirstCharacter:
  68 //  Load the first character from string.  If it is equal to the first
  69 //  character of word, or is a zero byte, then we do more processing;
  70 //  otherwise, proceed to the next character.
  71     ldrb    r1,    [r4],#1
  72     cmp     r1,     ip
  73     tstne   r1,     r1
  74     bne     L_lookForFirstCharacter
  75
  76 //  The byte that we loaded from string either matched the first character
  77 //  of word, or was a zero byte.  If it was a zero byte, then we have reached
  78 //  the end of string without finding a match of word.  Otherwise, we fall
  79 //  into a loop that checks additional characters to see if we have a match.
  80     tst     r1,     r1
  81     beq     L_noMatch
  82
  83 //  We have found a match for the first character of word; we want to read
  84 //  characters from this point on to see if we have a match for the entirety
  85 //  of word.  We want to be sure to preserve the state of the outside loop,
  86 //  however:
  87 //
  88 //      r0: length(word) - 1
  89 //      r4: pointer to the next character in string
  90 //      r5: pointer to the first character in word
  91 //      ip: first character in word
  92 //
  93 //  The registers r1-r3, r6, and lr are available as scratch.  We set them up
  94 //  for the inner loop as follows:
  95 //
  96 //      r1: remaining length to be matched
  97 //      r2: pointer to next character of string to match
  98 //      r3: pointer to next character of word to match
  99 //      r6: current character from string
 100 //      lr: current character from word
 101     mov     r2,     r4
 102     add     r3,     r5, #1
 103     mov     r1,     r0
 104
 105 L_checkMatch:
 106 //  Load the next byte from both the candidate match and from word.  If they
 107 //  are not equal, jump back to the outer loop.  If they are equal, decrement
 108 //  the length, and continue the inner loop if we have not yet found a
 109 //  complete match.
 110 //
 111 //  We don't need to worry about looking for null bytes in this loop; we know
 112 //  that we won't load a null byte from word, because we computed it's length
 113 //  earlier, and are using that as a termination condition.  If we hit a null
 114 //  byte in string, the comparison will fail (because the corresponding byte
 115 //  in word is non-null), and we will return to the outer loop, where the
 116 //  null byte will be detected and handled properly.
 117     ldrb    r6,    [r2],#1
 118     ldrb    lr,    [r3],#1
 119     cmp     r6,     lr
 120     bne     L_lookForFirstCharacter
 121     subs    r1,     r1, #1
 122     bne     L_checkMatch
 123
 124 //  We have exhausted the length of word without finding a mismatched character
 125 //  so we have found a match.  Return a pointer to the beginning of the match
 126 //  string.  (This pointer is r4 - 1 because r4 was auto-incremented when we
 127 //  loaded the first character).
 128     sub     r0,     r4, #1
 129     CLEAR_FRAME_AND_RETURN
 130
 131 L_noMatch:
 132 //  No match was found; return NULL.
 133     mov     r0,     #0
 134     CLEAR_FRAME_AND_RETURN
 135
 136 L_tinyWord:
 137 //  "word" is either empty or a single character.  If it is a single character,
 138 //  translate strstr into a call to the (more efficient) strchr.
 139     blt     L_emptyWord
 140     ldrb    r1,    [r5]
 141     mov     r0,     r4
 142     bl      _strchr
 143     CLEAR_FRAME_AND_RETURN
 144
 145 L_emptyWord:
 146 //  "word" is empty; return "string".
 147     movlt   r0,     r4
 148     CLEAR_FRAME_AND_RETURN
 149