include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <ctype.h>
#include <sys/time.h>

#define NRUNS 20
#define BS 0xffff

//////////////////////
//  find a substring in another using CASELESS comparison
inline char *
stristr(char *haystack, char *needle)
{
    char    *np = needle, tmph, tmpn;

    while( (tmph = *haystack) ){
        if( (tmpn = *np) && toupper(tmpn) == toupper(tmph) )
            np++;
        else{
            if(!tmpn)
                return (haystack - strlen(needle));
            np = needle;
        }
        haystack++;
    }

    return NULL;
}

static inline int pstamps(struct timeval *tso, struct timeval *tsn)
{
    long srem = 0, uadd = 0, ns, nms;

    //for overflow
    if(tsn->tv_usec < tso->tv_usec){
        srem = 1;
        uadd = 1000000;
    }

    //sanity
    if(tsn->tv_sec < tso->tv_sec)
        printf("jumped back in time!!\n");

    //calc diff and # bytes per ms
    ns = (tsn->tv_sec - tso->tv_sec - srem);
    nms = (tsn->tv_usec - tso->tv_usec + uadd);
    printf("diff is %ld s %ld ms\n", ns, nms);
    
    return 0;
}

char    buf[BS], *needle = "foobar";

void test(char * (*func)(char *, char *))
{   
    int x = 0;
    
    for(x = 0; x < NRUNS; x++)
        func(buf, needle);
}

int main()
{   
    struct timeval  to, tn;
    
    //NULL it
    memset(buf, 'a', BS-1);
    buf[BS-1] = 0; 
    memset(&to, 0, sizeof(to));
    tn = to;
    
    gettimeofday(&to, NULL);
    test(stristr);
    gettimeofday(&tn, NULL);
    pstamps(&to, &tn);
    
    return 0;
}

#define eq(x,y) ((!(x^y)))  || (((x^y) == 0x20) && (((x|y) > 0x60) && ((x|y) < 0x7b)))

char *stristr2 (char *hay, char *needle)
{
    char *h, *n, *hMax, *hMin;

    if (hay[0])
    {
        if (needle[0])
        {
            hMax = h = hay; n = needle;
            while (*hMax++);
            while (*n++) hMax--;
            n = needle;
            if (hMax > h)
            {
                while ((h < hMax) && (!(eq(*h,*n)))) h++;
                if (h < hMax)
                {
                    if (n [1])
                    {
                        hMin = h;
                        while (*(h = hMin))
                        {
                            n = needle;
                            while ((h < hMax) && (!(eq(*h,*n)))) h++;
                            if ((h < hMax))
                            {
                                hMin = h + 1;
                                while ((*h) && (eq(*h,*n))) {h++; n++;}
                                if (!*n) return --hMin;
                            }
                            else break;
                        }
                    }
                    else return h;
                }
            }
        }
        else return hay;
    }
    return NULL;
}

#!/usr/bin/perl

use strict;

print "\n";

# data
my @stra = split //, "0127498796198375981709570913750971309580913850981309580913091730957190837905831095809137985701974097";
my @strb = split //, "1983509713097598173587190485831098591381598309850913750973981735709137590813095810938509813909173493";

# options
my $goal_size = 5;  # set goal match size
my $disp_each = 0;  # toggle individual match display

my $use_cache = 0;
while ($use_cache <= 1) {

  # results set
  my @matches = ();     # matches
  my $match_count = 0;  # total matches
  my $cycle_count = 0;  # total loop cycles
  my $cache_usage_count = 0; # total cache uses
  my $compa_count = 0;  # total comparisons performed

  # machine vars
  my %hit_cache = ();
  my $cache_size = 0;
  my $hit_count = 0;
  my ($na, $achar, $nb, $bchar, $nhc, $cache, $cvn, $offset);

  # machine
  for ($na = 0; $na <= $#stra; $na++)
  {
    $achar = $stra[$na];

    if ($use_cache && defined($hit_cache{$achar}))
    {
      ++$cache_usage_count;

      $cache = $hit_cache{$achar};

      for ($nhc = 0; $nhc <= $#{$cache}; $nhc++)
      {
        ++$cycle_count;
        ++$compa_count;

        $cvn = $cache->[$nhc];

        $hit_count = 0;
        $offset = 0;
        while ( $offset <= $#stra
             && $offset <= $#strb
             && $stra[$na + $offset] == $strb[$cvn + $offset]
        ) {
          ++$compa_count;

          ++$offset;
          ++$hit_count;

          if ($hit_count == $goal_size) {
            if ($disp_each) {
              print "Matched A [".$na."] at B [".$cvn."]\n";
            }
            push @matches, [$na, $cvn];
            ++$match_count;
            last;
          }
        }
      }
    }
    else
    {
      for ($nb = 0; $nb <= $#strb; $nb++)
      {
        $bchar = $strb[$nb];

        ++$cycle_count;
        ++$compa_count;

        if ($achar == $bchar)
        {
          if ($use_cache) {
            push @{$hit_cache{$achar}}, $nb;
            ++$cache_size;
          }

          $hit_count = 0;
          $offset = 1;
          while ( $offset <= $#stra
               && $offset <= $#strb
               && $stra[$na + $offset] == $strb[$nb + $offset]
          ) {
            ++$compa_count;

            ++$offset;
            ++$hit_count;

            if ($hit_count == $goal_size) {
              if ($disp_each) {
                print "Matched A [".$na."] at B [".$nb."]\n";
              }
              push @matches, [$na, $nb];
              ++$match_count;
              last;
            }
          }
        }
      }
    }
  }

  # output
  print "WORK MODE:     ".($use_cache ? "CACHED": "STANDARD")."\n"
      . "CACHE SIZE:    ".$cache_size."\n"
      . "CACHE USES:    ".$cache_usage_count."\n"
      . "MATCHES:       ".$match_count."\n"
      . "CYCLES:        ".$cycle_count."\n"
      . "COMPARISONS:   ".$compa_count."\n\n";

  ++$use_cache;
}