1/* Copyright (C) 1994, 1999 Free Software Foundation, Inc. 2This file is part of the GNU C Library. 3 4This program is free software; you can redistribute it and/or modify 5it under the terms of the GNU General Public License as published by 6the Free Software Foundation; either version 2, or (at your option) 7any later version. 8 9This program is distributed in the hope that it will be useful, 10but WITHOUT ANY WARRANTY; without even the implied warranty of 11MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 12GNU General Public License for more details. 13 14You should have received a copy of the GNU General Public License 15along with this program; if not, write to the Free Software 16Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, 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#if HAVE_CONFIG_H 28# include <config.h> 29#endif 30 31#if defined _LIBC || defined HAVE_STRING_H 32# include <string.h> 33#endif 34#include <sys/types.h> 35 36typedef unsigned chartype; 37 38#undef strstr 39 40char * 41strstr (const char *phaystack, const char *pneedle) 42{ 43 register const unsigned char *haystack, *needle; 44 register chartype b, c; 45 46 haystack = (const unsigned char *) phaystack; 47 needle = (const unsigned char *) pneedle; 48 49 b = *needle; 50 if (b != '\0') 51 { 52 haystack--; /* possible ANSI violation */ 53 do 54 { 55 c = *++haystack; 56 if (c == '\0') 57 goto ret0; 58 } 59 while (c != b); 60 61 c = *++needle; 62 if (c == '\0') 63 goto foundneedle; 64 ++needle; 65 goto jin; 66 67 for (;;) 68 { 69 register chartype a; 70 register const unsigned char *rhaystack, *rneedle; 71 72 do 73 { 74 a = *++haystack; 75 if (a == '\0') 76 goto ret0; 77 if (a == b) 78 break; 79 a = *++haystack; 80 if (a == '\0') 81 goto ret0; 82shloop:; } 83 while (a != b); 84 85jin: a = *++haystack; 86 if (a == '\0') 87 goto ret0; 88 89 if (a != c) 90 goto shloop; 91 92 rhaystack = haystack-- + 1; 93 rneedle = needle; 94 a = *rneedle; 95 96 if (*rhaystack == a) 97 do 98 { 99 if (a == '\0') 100 goto foundneedle; 101 ++rhaystack; 102 a = *++needle; 103 if (*rhaystack != a) 104 break; 105 if (a == '\0') 106 goto foundneedle; 107 ++rhaystack; 108 a = *++needle; 109 } 110 while (*rhaystack == a); 111 112 needle = rneedle; /* took the register-poor approach */ 113 114 if (a == '\0') 115 break; 116 } 117 } 118foundneedle: 119 return (char*) haystack; 120ret0: 121 return 0; 122} 123