#include <iostream>

#include <intrin.h>


using namespace std;


inline size_t has_zero_byte( const size_t n ) // 32bit 전용

{

    const size_t finder = (size_t)0x01010101;

    const size_t masker = (size_t)0x80808080;

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

}


char    lower_ascii[ 0x100 ];

inline char*   strstr_i( 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*   strstr_i2( 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( ( lower_ascii[ s[ 0 ] ] != c ) &&

                ( lower_ascii[ s[ 1 ] ] != c ) &&

                ( lower_ascii[ s[ 2 ] ] != c ) &&

                ( lower_ascii[ s[ 3 ] ] != c ) )

                s += 4;

            else

            {

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

                return s - 1;

            }

        }

    }

    else

    {

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

        {

            if( ( lower_ascii[ s[ 0 ] ] != c ) &&

                ( lower_ascii[ s[ 1 ] ] != c ) &&

                ( lower_ascii[ s[ 2 ] ] != c ) &&

                ( lower_ascii[ s[ 3 ] ] != c ) )

                s += 4;

            else

            {

                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 );

            }

        }

    }

    return strstr_i(s, sub);

}


inline size_t has_zero_byte_ttt( const size_t n ) // 32bit 전용

{

    return !( ( n & 0xFF ) && ( ( n >> 8 ) & 0xFF ) && ( ( n >> 16 ) & 0xFF ) && ( n >> 24 ) );

}


char*   strstr_i3( 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_ttt( *(size_t*)s ) )

        {

            if( ( lower_ascii[ s[ 0 ] ] != c ) &&

                ( lower_ascii[ s[ 1 ] ] != c ) &&

                ( lower_ascii[ s[ 2 ] ] != c ) &&

                ( lower_ascii[ s[ 3 ] ] != c ) )

                s += 4;

            else

            {

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

                return s - 1;

            }

        }

    }

    else

    {

        while( !has_zero_byte_ttt( *(size_t*)s ) )

        {

            if( ( lower_ascii[ s[ 0 ] ] != c ) &&

                ( lower_ascii[ s[ 1 ] ] != c ) &&

                ( lower_ascii[ s[ 2 ] ] != c ) &&

                ( lower_ascii[ s[ 3 ] ] != c ) )

                s += 4;

            else

            {

                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 );

            }

        }

    }

    return strstr_i( s, sub );

}



int main()

{

    char* src = new char[100 * 1024 * 1024];

    char sub[] = "Hello world";

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

    src[100 * 1024 * 1024 - 1] = 0;

    strcpy(src + 100 * 1024 * 1024 - 100, sub);


    __int64 begin, elapsed1, elapsed2;

    begin = __rdtsc();

    size_t position_strstr = ( strstr_i3( src, "hello World" ) - src );

    elapsed1 = __rdtsc() - begin;


    begin = __rdtsc();

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

    elapsed2 = __rdtsc() - begin;


    delete[] src;


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

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


    getchar();

    return 0;

}