1 /* Copyright (C) 1994, 1999, 2002-2003, 2005-2006 Free Software Foundation, Inc. 2 This file is part of the GNU C Library. 3 4 This program is free software; you can redistribute it and/or modify 5 it under the terms of the GNU General Public License as published by 6 the Free Software Foundation; either version 2, or (at your option) 7 any later version. 8 9 This program is distributed in the hope that it will be useful, 10 but WITHOUT ANY WARRANTY; without even the implied warranty of 11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 12 GNU General Public License for more details. 13 14 You should have received a copy of the GNU General Public License 15 along with this program; if not, write to the Free Software Foundation, 16 Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */ 17 18 /* 19 * My personal strstr() implementation that beats most other algorithms. 20 * Until someone tells me otherwise, I assume that this is the 21 * fastest implementation of strstr() in C. 22 * I deliberately chose not to comment it. You should have at least 23 * as much fun trying to understand it, as I had to write it :-). 24 * 25 * Stephen R. van den Berg, berg@pool.informatik.rwth-aachen.de */ 26 27 #include <config.h> 28 29 /* Specification. */ 30 #include "c-strstr.h" 31 32 #include <string.h> 33 34 typedef unsigned chartype; 35 36 char * 37 c_strstr (const char *phaystack, const char *pneedle) 38 { 39 register const unsigned char *haystack, *needle; 40 register chartype b, c; 41 42 haystack = (const unsigned char *) phaystack; 43 needle = (const unsigned char *) pneedle; 44 45 b = *needle; 46 if (b != '\0') 47 { 48 haystack--; /* possible ANSI violation */ 49 do 50 { 51 c = *++haystack; 52 if (c == '\0') 53 goto ret0; 54 } 55 while (c != b); 56 57 c = *++needle; 58 if (c == '\0') 59 goto foundneedle; 60 ++needle; 61 goto jin; 62 63 for (;;) 64 { 65 register chartype a; 66 register const unsigned char *rhaystack, *rneedle; 67 68 do 69 { 70 a = *++haystack; 71 if (a == '\0') 72 goto ret0; 73 if (a == b) 74 break; 75 a = *++haystack; 76 if (a == '\0') 77 goto ret0; 78 shloop:; } 79 while (a != b); 80 81 jin: a = *++haystack; 82 if (a == '\0') 83 goto ret0; 84 85 if (a != c) 86 goto shloop; 87 88 rhaystack = haystack-- + 1; 89 rneedle = needle; 90 a = *rneedle; 91 92 if (*rhaystack == a) 93 do 94 { 95 if (a == '\0') 96 goto foundneedle; 97 ++rhaystack; 98 a = *++needle; 99 if (*rhaystack != a) 100 break; 101 if (a == '\0') 102 goto foundneedle; 103 ++rhaystack; 104 a = *++needle; 105 } 106 while (*rhaystack == a); 107 108 needle = rneedle; /* took the register-poor approach */ 109 110 if (a == '\0') 111 break; 112 } 113 } 114 foundneedle: 115 return (char *) haystack; 116 ret0: 117 return 0; 118 } 119