fork(1) download
copy 
  1. #include <string.h>
  2.  
  3. unsigned char   lower_ascii[ 0x100 ];
  4.  
  5. inline  void    build_lower_table()
  6. {
  7.     if( !lower_ascii[ 0xFF ] )
  8.     {
  9.         size_t i;
  10.         for( i = 0; i < 'A'; ++i ) lower_ascii[i] = (unsigned char)i;
  11.         for( ;     i <= 'Z'; ++i ) lower_ascii[i] = (unsigned char)i | 0x20;
  12.         for( ;    i < 0x100; ++i ) lower_ascii[i] = (unsigned char)i;
  13.     }
  14. }
  15.  
  16. inline  size_t  has_zero_byte( const size_t n )
  17. {
  18.     const   size_t  finder = (size_t)0x0101010101010101ULL;
  19.     const   size_t  masker = (size_t)0x8080808080808080ULL;
  20.     return ( n - finder ) & ( ~n & masker );
  21. }
  22.  
  23. inline  size_t  has_some_byte( const unsigned char* s, const size_t cs )
  24. {
  25.     return has_zero_byte( ( *(size_t*)s | (size_t)0x2020202020202020ULL ) ^ cs );
  26. }
  27.  
  28. inline  char*   strstrcase( const unsigned char* src, const unsigned char* sub )
  29. {
  30.     unsigned char* s = (unsigned char*)src;
  31.     unsigned char* r = (unsigned char*)sub;
  32.     unsigned char* o = s;
  33.     while( *s )
  34.     {
  35.         if( lower_ascii[*s] == lower_ascii[*r] )
  36.         {
  37.             s++;
  38.             r++;
  39.             if( !*r ) return (char*)o - 1;
  40.         }
  41.         else
  42.         {
  43.             s = o++;
  44.             r = (unsigned char*)sub;
  45.         }
  46.     }
  47.     return NULL;
  48. }
  49.  
  50. inline  char*   strstrcase( const char* src, const char* sub )
  51. {
  52.     build_lower_table();
  53.     if( !( (size_t)src | (size_t)sub ) ) return NULL;
  54.     return strstrcase( (unsigned char*)src, (unsigned char*)sub );
  55. }
  56.  
  57. inline  int     strdiff_except_ascii( const unsigned char* s1, const unsigned char* s2 )
  58. {
  59.     for( size_t i = 0; s2[i]; )
  60.     {
  61.         if( s1[i] & 0x80 )
  62.         {
  63.             if( *(short*)( s1 + i ) != *(short*)( s2 + i ) )   return 1;
  64.             i += 2;
  65.             continue;
  66.         }
  67.         i++;
  68.     }
  69.     return 0;
  70. }
  71.  
  72. inline  char*   strstrcase_fast( const unsigned char* src, const unsigned char* sub )
  73. {
  74.     build_lower_table();
  75.     if( !( (size_t)src | (size_t)sub ) ) return NULL;
  76.  
  77.     size_t* s               = (size_t*)src;
  78.     unsigned char*  r       = (unsigned char*)sub + 1;
  79.     const unsigned char c0  = lower_ascii[ sub[0] ];
  80.     const unsigned char c0t = sub[0] | 0x20;
  81.     const size_t    c0s     =
  82.     #ifdef _WIN64
  83.                               ( (size_t)c0t << 56 ) | ( (size_t)c0t << 48 ) |
  84.                               ( (size_t)c0t << 40 ) | ( (size_t)c0t << 32 ) |
  85.     #endif
  86.                               ( (size_t)c0t << 24 ) | ( (size_t)c0t << 16 ) |
  87.                               ( (size_t)c0t <<  8 ) | ( (size_t)c0t );
  88.  
  89.     if( !*r )
  90.     {
  91.         while( !has_zero_byte( *(size_t*)s ) )
  92.         {
  93.             if( has_some_byte( (unsigned char*)s, c0t ) )
  94.             {
  95.                 unsigned char* ss = (unsigned char*)s;
  96.                 while( lower_ascii[ *ss++ ] != c0 );
  97.                 return (char*)ss - 1;
  98.             }
  99.             else s++;
  100.         }
  101.     }
  102.     else
  103.     {
  104.         const unsigned char c1t = sub[1] | 0x20;
  105.         const size_t        c1s =
  106.         #ifdef _WIN64
  107.                               ( (size_t)c1t << 56 ) | ( (size_t)c1t << 48 ) |
  108.                               ( (size_t)c1t << 40 ) | ( (size_t)c1t << 32 ) |
  109.         #endif
  110.                               ( (size_t)c1t << 24 ) | ( (size_t)c1t << 16 ) |
  111.                               ( (size_t)c1t <<  8 ) | ( (size_t)c1t );
  112.  
  113.         while( !has_zero_byte( *(size_t*)s ) )
  114.         {
  115.             if( has_some_byte( (unsigned char*)s, c0s ) &&
  116.                 has_some_byte( (unsigned char*)s + 1, c1s ) )
  117.             {
  118.                 unsigned char* ss = (unsigned char*)s;
  119.                 s++;
  120.                 while( lower_ascii[ *ss++ ] != c0 );
  121.                 retry:
  122.                 for( int i = 0; lower_ascii[ ss[i] ] == lower_ascii[ r[i] ]; ++i )
  123.                 {
  124.                     if( !ss[i] ) return NULL;
  125.                     if( !r[i + 1] )
  126.                     {
  127.                         if( !strdiff_except_ascii( ss - 1, sub ) ) return (char*)ss - 1;
  128.                         break;
  129.                     }
  130.                 }
  131.                 do if( lower_ascii[*ss++] == c0 ) goto retry; while( ss < (unsigned char*)s );
  132.             }
  133.             else s++;
  134.         }
  135.     }
  136.     return strstrcase( (unsigned char*)s, sub );
  137. }
  138.  
  139. char*   strstrcase_fast( const char* src, const char* sub )
  140. {
  141.     return  strstrcase_fast( (unsigned char*)src, (unsigned char*)sub );
  142. }
  143.  
  144. typedef unsigned long long  tick_t;
  145.  
  146. #ifdef _MSC_VER
  147.     #include <intrin.h>
  148.     #define clock()         __rdtsc()
  149. #else
  150.     #if 0
  151.     inline unsigned long long rdtsc()
  152.     {
  153.         tick_t tick;
  154.         __asm volatile ( ".byte 0x0f, 0x31" : "=A" ( tick ) );
  155.         return tick;
  156.     }
  157.     #endif
  158. #endif
  159.  
  160. #include <string.h>
  161. #include <iostream>
  162. using   namespace   std;
  163.  
  164. #define min( a, b ) ( (a) < (b)? (a): (b) )
  165. #define update_min( a, b ) ( (a) = min( (a), (b) ) )
  166.  
  167. int main()
  168. {
  169.     // RDTSC recipie
  170.                 tick_t  elapsed0,   elapsed1,   elapsed2;
  171.     volatile    size_t  sum0 = 0,   sum1 = 0,   sum2 = 0;
  172.  
  173.     // set to the max
  174.     elapsed0    = elapsed1  = elapsed2  = -1;
  175.  
  176.     // parameters
  177.     #define     LOOP_COUNT              10000
  178.     #define     TEST_STRING_LENGTH      100000
  179.     char*       src_string  = new char[TEST_STRING_LENGTH];
  180.     char*       sub_string1 = "한글Hello World";
  181.     char*       sub_string2 = "한글heLLo worLd";
  182.  
  183.     for( int i = 0; i < TEST_STRING_LENGTH - 1; ++i ) src_string[i] = rand() % 255 + 1;
  184.     src_string[TEST_STRING_LENGTH - 1] = 0;
  185.     strcpy( src_string + TEST_STRING_LENGTH - 100, sub_string1 );
  186.  
  187.     for( int i = 0; i < LOOP_COUNT; ++i )
  188.     {
  189.         tick_t  begin   = clock();
  190.         tick_t  elapsed = clock() - begin;
  191.         update_min( elapsed0, elapsed );
  192.     }
  193.  
  194.     for( int i = 0; i < LOOP_COUNT; ++i )
  195.     {
  196.         tick_t  begin   = clock();
  197.         sum1    = strcasestr( src_string, sub_string2 ) - src_string;
  198.         tick_t  elapsed = clock() - begin;
  199.         update_min( elapsed1, elapsed );
  200.     }
  201.  
  202.     for( int i = 0; i < LOOP_COUNT; ++i )
  203.     {
  204.         tick_t  begin   = clock();
  205.         sum2    = strstrcase_fast( src_string, sub_string2 ) - src_string;
  206.         tick_t  elapsed = clock() - begin;
  207.         update_min( elapsed2, elapsed );
  208.     }
  209.  
  210.     cout << "RDTSC cost : " << elapsed0 << " clocks" << endl << endl;
  211.     cout << sum1 << "     " << elapsed1 - elapsed0 << endl;
  212.     cout << sum2 << "     " << elapsed2 - elapsed0 << endl;
  213.  
  214.     getchar();
  215.     return 0;
  216. }
  217.  
Success #stdin #stdout 3.98s 3468KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
RDTSC cost : 0 clocks

99900     245
99900     149
https://ideone.com/4iXsZU
strcasestr
language:
C++14 (gcc 8.3)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!