#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 ] ) // NULL parameter 를 이용해 초기화할 수 있게 해주지뭐.

    {

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

    char* o = 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

        {

            char* ss = s;

            char* se = s + 4;

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

            if( !*r ) return ss - 1; // 1바이트 찾기 따로 뺄까?

        retry:

            char* p = ss;

            while( 1 )

            {

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

                {

                    if( !r[ 1 ] ) return p - 1;

                    ss++;

                    r++;

                }

                else

                {

                    ss = p;

                    do

                    {

                        if ( lower_ascii[ *ss++ ] == c )

                            goto retry;

                    } while( ss < se );

                    s += 4;

                    r = o;

                    break;

                }

            }

        }

    }

    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( src, sub ) - 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;

}