lib/strstr.c

   1 /* Copyright (C) 1994, 1999, 2002 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
  16 Foundation, 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
  35 typedef unsigned chartype;
  36
  37 #undef strstr
  38
  39 char *
  40 strstr (const char *phaystack, const char *pneedle)
  41 {
  42   register const unsigned char *haystack, *needle;
  43   register chartype b, c;
  44
  45   haystack = (const unsigned char *) phaystack;
  46   needle = (const unsigned char *) pneedle;
  47
  48   b = *needle;
  49   if (b != '\0')
  50     {
  51       haystack--;                               /* possible ANSI violation */
  52       do
  53         {
  54           c = *++haystack;
  55           if (c == '\0')
  56             goto ret0;
  57         }
  58       while (c != b);
  59
  60       c = *++needle;
  61       if (c == '\0')
  62         goto foundneedle;
  63       ++needle;
  64       goto jin;
  65
  66       for (;;)
  67         {
  68           register chartype a;
  69           register const unsigned char *rhaystack, *rneedle;
  70
  71           do
  72             {
  73               a = *++haystack;
  74               if (a == '\0')
  75                 goto ret0;
  76               if (a == b)
  77                 break;
  78               a = *++haystack;
  79               if (a == '\0')
  80                 goto ret0;
  81 shloop:;    }
  82           while (a != b);
  83
  84 jin:      a = *++haystack;
  85           if (a == '\0')
  86             goto ret0;
  87
  88           if (a != c)
  89             goto shloop;
  90
  91           rhaystack = haystack-- + 1;
  92           rneedle = needle;
  93           a = *rneedle;
  94
  95           if (*rhaystack == a)
  96             do
  97               {
  98                 if (a == '\0')
  99                   goto foundneedle;
 100                 ++rhaystack;
 101                 a = *++needle;
 102                 if (*rhaystack != a)
 103                   break;
 104                 if (a == '\0')
 105                   goto foundneedle;
 106                 ++rhaystack;
 107                 a = *++needle;
 108               }
 109             while (*rhaystack == a);
 110
 111           needle = rneedle;                /* took the register-poor approach */
 112
 113           if (a == '\0')
 114             break;
 115         }
 116     }
 117 foundneedle:
 118   return (char*) haystack;
 119 ret0:
 120   return 0;
 121 }