* Copyright (c) 2010, Apple Inc. All rights reserved.
* This file contains Original Code and/or Modifications of Original Code
* as defined in and that are subject to the Apple Public Source License
* Version 2.0 (the 'License'). You may not use this file except in
* compliance with the License. Please obtain a copy of the License at
* http://www.opensource.apple.com/apsl/ and read it before using this
* The Original Code and all software distributed under the License are
* distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
* EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
* INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
* Please see the License for the specific language governing rights and
* limitations under the License.
// char * strstr(const char *s1, const char *s2)// If s2 is empty, s1 is returned.
// If s2 does not occur in s1, NULL is returned.
// Otherwise, a pointer to the first character of the first occurrence of s2
// in s1 is returned.
// We use a hand-tuned version of the naive quadratic time algorithm// found wanting. The increased startup cost combines with the frequency of
// calls to strstr with small strings to swamp the gains from improved
// asymptotic complexity.
#define CLEAR_FRAME_AND_RETURN \
add r7, sp, #12
// Throughout this function, I will refer to the string in which we are
// searching as "string" and the string for which we are searching as "word".
// Using s1 and s2 is too confusing. Thus, we want to return a pointer to
// the first occurrence of "word" in "string".
mov r5, r1
mov r4, r0
// We begin by calling strlen to find the length of "word". We also handle
// two special cases here: we early-out if word is an empty string (length
// zero), and we call strchr if word is only a single character.
mov r0, r5
subs r0, r0, #1
// Load the first character of word
ldrb ip, [r5]
// Load the first character from string. If it is equal to the first
// character of word, or is a zero byte, then we do more processing ldrb r1, [r4],#1
cmp r1, ip
tstne r1, r1
// The byte that we loaded from string either matched the first character
// of word, or was a zero byte. If it was a zero byte, then we have reached
// the end of string without finding a match of word. Otherwise, we fall
// into a loop that checks additional characters to see if we have a match.
tst r1, r1
// We have found a match for the first character of word// of word. We want to be sure to preserve the state of the outside loop,
// r0: length(word) - 1
// r4: pointer to the next character in string
// r5: pointer to the first character in word
// ip: first character in word
// The registers r1-r3, r6, and lr are available as scratch. We set them up
// for the inner loop as follows:
// r1: remaining length to be matched
// r2: pointer to next character of string to match
// r3: pointer to next character of word to match
// r6: current character from string
// lr: current character from word
mov r2, r4
add r3, r5, #1
mov r1, r0
// Load the next byte from both the candidate match and from word. If they
// are not equal, jump back to the outer loop. If they are equal, decrement
// the length, and continue the inner loop if we have not yet found a
// complete match.
// We don't need to worry about looking for null bytes in this loop// earlier, and are using that as a termination condition. If we hit a null
// byte in string, the comparison will fail (because the corresponding byte
// in word is non-null), and we will return to the outer loop, where the
// null byte will be detected and handled properly.
ldrb r6, [r2],#1
ldrb lr, [r3],#1
cmp r6, lr
subs r1, r1, #1
// We have exhausted the length of word without finding a mismatched character
// so we have found a match. Return a pointer to the beginning of the match
// string. (This pointer is r4 - 1 because r4 was auto-incremented when we
// loaded the first character).
sub r0, r4, #1
// No match was found CLEAR_FRAME_AND_RETURN
// "word" is either empty or a single character. If it is a single character,
// translate strstr into a call to the (more efficient) strchr.
ldrb r1, [r5]
mov r0, r4
// "word" is empty CLEAR_FRAME_AND_RETURN