난 함수형 프로그래밍에 관심이 많은 편이라 C++같은거 잘 못 만져서 좀 오래 걸렸음.

그러고도 소스는 개판임. 이해 바람 :)  버그도 많을듯.

일단 무조건 sub string이 포함되어 있다고 가정하고 대충짜서 포함 안되어 있을 때도 마지막값 대충 출력 해버리는 버그 등등.



간단히 설명하자면 주어진 문자열을 워드 사이즈(얼라인 되어 있다고 가정) 만큼씩 카피(코세가 요구한대로 원본을 보존하기 위해서) 하면서 

동시에 bitwise | 0x20202020 연산을 통해서 대문자를 소문자로 바꾼다.


이때 대문자가 소문자로 바뀌는 것은 맞지만 다른 값들도 엉뚱하게 바뀌는 경우가 생김

일단 이 어레이에다가 라이브러리의 strcmp를 사용해서 원하는 문자열을 찾은 다음.

정확하게 하기 위해서 이제는 그부분만 if (c >= 'A' && c <= 'Z') c+= 32; 을

사용하여 정확하게 대소문자만 변경해서 이번에도 일치하면 결과를 냄

여기도 비트 연산으로 더 최적화 시킬 수 있을듯


위 결과가 내꺼임





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




}



void memcpy_roughly(char * src, char* dst, int bytes) {

int words = bytes / 4;


for (int word = 0; word < words; ++word)

*(((int*)dst) + word) = (*(((int*)src) + word) | 0x20202020);


for (int byte = words*4; byte < bytes; ++byte)

*(dst + byte) = *(src + byte) | 0x20;

}


void memcpy_exactly(char * src, char* dst, int bytes) {

for (int byte = 0; byte < bytes; ++byte) {

char c = *(src + byte);

if (c >= 'A' && c <= 'Z') c+= 32;

*(dst + byte) = c;

}

}


#define SRC_LEN 1024*1024*100

int main()


{


char* src = new char[SRC_LEN];


char sub[] = "Hello world";


for (int i = 0; i < SRC_LEN - 1; ++i) {

src[i] = rand() % 127 + 1;

}


src[SRC_LEN - 1] = 0;


memcpy(src + SRC_LEN - 1000, sub, strlen(sub));

src[SRC_LEN - 1000] = 'h';




__int64 begin, elapsed1, elapsed2;

begin = __rdtsc();


size_t position_strstr;

{

int sub_len = strlen(sub);


char * src_rough_copy = new char[SRC_LEN];

char * sub_rough_copy = new char[100];

char * sub_lower_copy = new char[100];


memcpy_roughly(src, src_rough_copy, SRC_LEN);

memcpy_roughly(sub, sub_rough_copy, sub_len);

sub_rough_copy[sub_len] = 0;

memcpy_exactly(sub, sub_lower_copy, sub_len);

sub_lower_copy[sub_len] = 0;



int current_position = 0;

while (true) {

char * po = strstr(src_rough_copy + current_position, sub_rough_copy);

if (po == nullptr) {

break;

}

current_position = po - src_rough_copy;

memcpy_exactly(src + current_position, src_rough_copy + current_position, sub_len);

int result = memcmp(src_rough_copy+ current_position, sub_lower_copy, sub_len);

if (!result) {

position_strstr = current_position;

break;

}

current_position++;

}

}


elapsed1 = __rdtsc() - begin;




begin = __rdtsc();


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



elapsed2 = __rdtsc() - begin;








delete[] src;


cout << " ";

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


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




getchar();


return 0;










}