#include <string.h>

unsigned char   lower_ascii[ 0x100 ];

inline  void    build_lower_table()
{
    if( !lower_ascii[ 0xFF ] )
    {
        size_t i;
        for( i = 0; i < 'A'; ++i ) lower_ascii[i] = (unsigned char)i;
        for( ;     i <= 'Z'; ++i ) lower_ascii[i] = (unsigned char)i | 0x20;
        for( ;    i < 0x100; ++i ) lower_ascii[i] = (unsigned char)i;
    }
}

inline  size_t  has_zero_byte( const size_t n )
{
    const   size_t  finder = (size_t)0x0101010101010101ULL;
    const   size_t  masker = (size_t)0x8080808080808080ULL;
    return ( n - finder ) & ( ~n & masker );
}

inline  size_t  has_some_byte( const unsigned char* s, const size_t cs )
{
    return has_zero_byte( ( *(size_t*)s | (size_t)0x2020202020202020ULL ) ^ cs );
}

inline  char*   strstrcase( const unsigned char* src, const unsigned char* sub )
{
    unsigned char* s = (unsigned char*)src;
    unsigned char* r = (unsigned char*)sub;
    unsigned char* o = s;
    while( *s )
    {
        if( lower_ascii[*s] == lower_ascii[*r] )
        {
            s++;
            r++;
            if( !*r ) return (char*)o - 1;
        }
        else
        {
            s = o++;
            r = (unsigned char*)sub;
        }
    }
    return NULL;
}

inline  char*   strstrcase( const char* src, const char* sub )
{
    build_lower_table();
    if( !( (size_t)src | (size_t)sub ) ) return NULL;
    return strstrcase( (unsigned char*)src, (unsigned char*)sub );
}

inline  int     strdiff_except_ascii( const unsigned char* s1, const unsigned char* s2 )
{
    for( size_t i = 0; s2[i]; )
    {
        if( s1[i] & 0x80 )
        {
            if( *(short*)( s1 + i ) != *(short*)( s2 + i ) )   return 1;
            i += 2;
            continue;
        }
        i++;
    }
    return 0;
}

inline  char*   strstrcase_fast( const unsigned char* src, const unsigned char* sub )
{
    build_lower_table();
    if( !( (size_t)src | (size_t)sub ) ) return NULL;

    size_t* s               = (size_t*)src;
    unsigned char*  r       = (unsigned char*)sub + 1;
    const unsigned char c0  = lower_ascii[ sub[0] ];
    const unsigned char c0t = sub[0] | 0x20;
    const size_t    c0s     =
    #ifdef _WIN64
                              ( (size_t)c0t << 56 ) | ( (size_t)c0t << 48 ) |
                              ( (size_t)c0t << 40 ) | ( (size_t)c0t << 32 ) |
    #endif
                              ( (size_t)c0t << 24 ) | ( (size_t)c0t << 16 ) |
                              ( (size_t)c0t <<  8 ) | ( (size_t)c0t );

    if( !*r )
    {
        while( !has_zero_byte( *(size_t*)s ) )
        {
            if( has_some_byte( (unsigned char*)s, c0t ) )
            {
                unsigned char* ss = (unsigned char*)s;
                while( lower_ascii[ *ss++ ] != c0 );
                return (char*)ss - 1;
            }
            else s++;
        }
    }
    else
    {
        const unsigned char c1t = sub[1] | 0x20;
        const size_t        c1s =
        #ifdef _WIN64
                              ( (size_t)c1t << 56 ) | ( (size_t)c1t << 48 ) |
                              ( (size_t)c1t << 40 ) | ( (size_t)c1t << 32 ) |
        #endif
                              ( (size_t)c1t << 24 ) | ( (size_t)c1t << 16 ) |
                              ( (size_t)c1t <<  8 ) | ( (size_t)c1t );

        while( !has_zero_byte( *(size_t*)s ) )
        {
            if( has_some_byte( (unsigned char*)s, c0s ) &&
                has_some_byte( (unsigned char*)s + 1, c1s ) )
            {
                unsigned char* ss = (unsigned char*)s;
                s++;
                while( lower_ascii[ *ss++ ] != c0 );
                retry:
                for( int i = 0; lower_ascii[ ss[i] ] == lower_ascii[ r[i] ]; ++i )
                {
                    if( !ss[i] ) return NULL;
                    if( !r[i + 1] )
                    {
                        if( !strdiff_except_ascii( ss - 1, sub ) ) return (char*)ss - 1;
                        break;
                    }
                }
                do if( lower_ascii[*ss++] == c0 ) goto retry; while( ss < (unsigned char*)s );
            }
            else s++;
        }
    }
    return strstrcase( (unsigned char*)s, sub );
}

char*   strstrcase_fast( const char* src, const char* sub )
{
    return  strstrcase_fast( (unsigned char*)src, (unsigned char*)sub );
}

typedef unsigned long long  tick_t;

#ifdef _MSC_VER
    #include <intrin.h>
    #define clock()         __rdtsc()
#else
    #if 0
    inline unsigned long long rdtsc()
    {
        tick_t tick;
        __asm volatile ( ".byte 0x0f, 0x31" : "=A" ( tick ) );
        return tick;
    }
    #endif
#endif

#include <string.h>
#include <iostream>
using   namespace   std;

#define min( a, b ) ( (a) < (b)? (a): (b) )
#define update_min( a, b ) ( (a) = min( (a), (b) ) )

int main()
{
    // RDTSC recipie
                tick_t  elapsed0,   elapsed1,   elapsed2;
    volatile    size_t  sum0 = 0,   sum1 = 0,   sum2 = 0;

    // set to the max
    elapsed0    = elapsed1  = elapsed2  = -1;

    // parameters
    #define     LOOP_COUNT              10000
    #define     TEST_STRING_LENGTH      100000
    char*       src_string  = new char[TEST_STRING_LENGTH];
    char*       sub_string1 = "한글Hello World";
    char*       sub_string2 = "한글heLLo worLd";

    for( int i = 0; i < TEST_STRING_LENGTH - 1; ++i ) src_string[i] = rand() % 255 + 1;
    src_string[TEST_STRING_LENGTH - 1] = 0;
    strcpy( src_string + TEST_STRING_LENGTH - 100, sub_string1 );

    for( int i = 0; i < LOOP_COUNT; ++i )
    {
        tick_t  begin   = clock();
        tick_t  elapsed = clock() - begin;
        update_min( elapsed0, elapsed );
    }

    for( int i = 0; i < LOOP_COUNT; ++i )
    {
        tick_t  begin   = clock();
        sum1    = strcasestr( src_string, sub_string2 ) - src_string;
        tick_t  elapsed = clock() - begin;
        update_min( elapsed1, elapsed );
    }

    for( int i = 0; i < LOOP_COUNT; ++i )
    {
        tick_t  begin   = clock();
        sum2    = strstrcase_fast( src_string, sub_string2 ) - src_string;
        tick_t  elapsed = clock() - begin;
        update_min( elapsed2, elapsed );
    }

    cout << "RDTSC cost : " << elapsed0 << " clocks" << endl << endl;
    cout << sum1 << "     " << elapsed1 - elapsed0 << endl;
    cout << sum2 << "     " << elapsed2 - elapsed0 << endl;

    getchar();
    return 0;
}