diff options
Diffstat (limited to 'tools/skycpt/KmpSearch.cpp')
-rw-r--r-- | tools/skycpt/KmpSearch.cpp | 129 |
1 files changed, 129 insertions, 0 deletions
diff --git a/tools/skycpt/KmpSearch.cpp b/tools/skycpt/KmpSearch.cpp new file mode 100644 index 0000000000..228741ca1f --- /dev/null +++ b/tools/skycpt/KmpSearch.cpp @@ -0,0 +1,129 @@ +#include "stdafx.h" +#include "KmpSearch.h" + +__declspec(naked) void __fastcall KmpSearch::init(const char *subStr) { + __asm { + // kmp initialization, make jump table for mismatches + push esi + push edi + push ebp + push ebx + push ecx + + mov esi, edx // edx: subStr argument + lea edi, [ecx + KmpSearch::_subStr] // this + 0x100 + lea ebx, [ecx + KmpSearch::_retarget] // this + lea ebp, [ecx + 1] + + mov byte ptr [ebx], -1 + + xor eax, eax + + loopStart: + shr ecx, 8 + test al, 3 + jnz short dontLoad + mov ecx, dword ptr [esi + eax] // load next 4 bytes of subStr + mov dword ptr [edi], ecx // and copy them to this._subStr while we're at it + lea edi, [edi + 4] + dontLoad: + + or cl, cl // end of subStr? + jz short endOfString + + mov edx, eax // save counter (i) in edx + + xlat // al = retarget[i] + inc al + mov byte ptr [ebp + edx], al // retarget[i + 1] = retarget[i] + 1 + jz short decLoopEnd + decrementLoop: + dec al + mov ah, byte ptr [esi + eax] // ah = sub[retarget[i + 1] - 1] + cmp ah, cl // if (ah == sub[i]) + jz short decLoopEnd // goto decLoopEnd + + xlat // al = retarget[retarget[i + 1] - 1] + xor ah, ah + inc al // al = retarget[retarget[i + 1] - 1] + 1 + mov byte ptr [ebp + edx], al // retarget[i + 1] = al + jnz short decrementLoop + decLoopEnd: + lea eax, [edx + 1] // i = i + 1 + jmp short loopStart + + endOfString: + + pop ecx // this + mov [ecx + KmpSearch::_strLen], eax // length of substring (without '\0') + + pop ebx + pop ebp + pop edi + pop esi + ret + } +} + +__declspec(naked) char * __fastcall KmpSearch::search(const char *str) { + __asm { + push esi + push edi + push ebx + + mov esi, edx // edx: str argument + lea edi, [ecx + KmpSearch::_subStr] + lea ebx, [ecx + KmpSearch::_retarget] + mov ch, byte ptr [ecx + KmpSearch::_strLen] + + or ch, ch // if (_strLen == 0) + jz short endOfString // goto endOfString + + xor edx, edx // index + + mov cl, 3 + searchLoop: + shr eax, 8 + inc cl + test cl, 4 + jz short skipRead + lodsd + xor cl, cl + skipRead: + + test al, al + jz short endOfString + + newIndexLoop: + cmp al, byte ptr [edi + edx] // while (c != sub[index]) { + jz short gotNewIndex + or edx, edx // if (index == 0) + jz short searchLoop // goto searchLoop + movzx edx, byte ptr [ebx + edx] // index = retarget[index] + jmp short newIndexLoop // } + + gotNewIndex: + inc edx + cmp dl, ch // if (index != _strLen) + jne short searchLoop // goto searchLoop + + movzx ebx, cl // bytes of eax used + movzx ecx, ch // length of subStr + + lea eax, [esi + ebx - 3] + sub eax, ecx + + pop ebx + pop edi + pop esi + ret + + endOfString: + xor eax, eax // return NULL + pop ebx + pop edi + pop esi + ret + } +} + |