#include "stdafx.h"


char            lower_ascii[ 0x100 ];


inline  size_t  has_zero_byte( const size_t n )

{

    const   size_t  finder = (size_t)0x01010101;

    const   size_t  masker = (size_t)0x80808080;

    return  ( n - finder ) & ( ~n & masker );

}


inline  size_t  has_some_byte( const char* s, const char c )

{

    return  lower_ascii[ s[ 0 ] ] == c || lower_ascii[ s[ 1 ] ] == c ||

            lower_ascii[ s[ 2 ] ] == c || lower_ascii[ s[ 3 ] ] == c;

}


inline  char*   istrstr( const char* src, const char* sub )

{

    char* s = (char*)src;

    char* r = (char*)sub;

    char* o = s;

    while( *s )

    {

        if( lower_ascii[ *s ] == lower_ascii[ *r ] )

        {

            s++;

            r++;

            if ( !*r ) return o - 1; 

        }

        else

        {

            s = o++;

            r = (char*)sub;

        }

    }

    return  NULL;

}


char*   ex_strstr( const char* src, const char* sub )

{

    if( !lower_ascii[ 0xFF ] )

    {

        size_t i;

        for( i = 0; i < 'A'; ++i ) lower_ascii[ i ] = (char)i;

        for( ; i <= 'Z'; ++i ) lower_ascii[ i ] = (char)i | 0x20;

        for( ; i < 0x100; ++i ) lower_ascii[ i ] = (char)i;

    }

    if( !( (size_t)src | (size_t)sub ) ) return NULL;


    char* s = (char*)src;

    char* r = (char*)sub + 1;

    char  c = lower_ascii[ *sub ];

    if( !*r )

    {

        while( !has_zero_byte( *(size_t*)s ) )

        {

            if( has_some_byte( s, c ) )

            {

                while( lower_ascii[ *s++ ] != c );

                return s - 1;

            }

            else s += 4;

        }

    }

    else

    {

        while( !has_zero_byte( *(size_t*)s ) )

        {

            if( has_some_byte( s, c ) )

            {

                char* ss = s;

                s += 4;

                while( lower_ascii[ *ss++ ] != c );

                retry:

                for( int i = 0; lower_ascii[ ss[ i ] ] == lower_ascii[ r[ i ] ]; ++i )

                    if( !r[ i + 1 ] ) return ss - 1;

                do if( lower_ascii[ *ss++ ] == c ) goto retry; while( ss < s );

            }

            else s += 4;

        }

    }

    return  istrstr(s, sub);

}


#define STRING_SIZE     ( 100 * 1024 * 1024 )


#include <iostream>

#include <intrin.h>

using namespace std;


int main()

{

    char* src = new char[ STRING_SIZE ];

    char sub[] = "Hello world";

    for(int i = 0; i < STRING_SIZE - 1; ++i ) src[i] = rand() % 127 + 1;

    src[ STRING_SIZE - 1] = 0;

    strcpy(src + STRING_SIZE - 100, sub);


    __int64 begin, elapsed1, elapsed2;


    begin = __rdtsc();

    size_t position_strstr      = strstr( src, sub ) - src;

    elapsed1 = __rdtsc() - begin;


    begin = __rdtsc();

    size_t position_strstr_i    = ex_strstr( src, "hello World" ) - src;

    elapsed2 = __rdtsc() - begin;


    delete[] src;


    cout << position_strstr     << "    " << elapsed1 << endl;

    cout << position_strstr_i   << "    " << elapsed2 << endl;


    getchar();

    return  0;

}


잘난체 어쩌구 하던 애는 왜 함흥차사냐...