lib/strstr.c

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