2 * Copyright (C) 2007 The ScummVM project
4 * This program is free software; you can redistribute it and/or
5 * modify it under the terms of the GNU General Public License
6 * as published by the Free Software Foundation; either version 2
7 * of the License, or (at your option) any later version.
9 * This program is distributed in the hope that it will be useful,
10 * but WITHOUT ANY WARRANTY; without even the implied warranty of
11 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 * GNU General Public License for more details.
14 * You should have received a copy of the GNU General Public License
15 * along with this program; if not, write to the Free Software
16 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
24 #include "KmpSearch.h"
31 __declspec(naked
) void __fastcall
KmpSearch::init(const char *subStr
) {
33 // kmp initialization, make jump table for mismatches
40 mov esi
, edx
// edx: subStr argument
41 lea edi
, [ecx
+ KmpSearch::_subStr
] // this + 0x100
42 lea ebx
, [ecx
+ KmpSearch::_retarget
] // this
45 mov byte ptr
[ebx
], -1
53 mov ecx
, dword ptr
[esi
+ eax
] // load next 4 bytes of subStr
54 mov dword ptr
[edi
], ecx
// and copy them to this._subStr while we're at it
58 or cl
, cl
// end of subStr?
61 mov edx
, eax
// save counter (i) in edx
63 xlat
// al = retarget[i]
65 mov byte ptr
[ebp
+ edx
], al
// retarget[i + 1] = retarget[i] + 1
69 mov ah
, byte ptr
[esi
+ eax
] // ah = sub[retarget[i + 1] - 1]
70 cmp ah
, cl
// if (ah == sub[i])
71 jz
short decLoopEnd
// goto decLoopEnd
73 xlat
// al = retarget[retarget[i + 1] - 1]
75 inc al
// al = retarget[retarget[i + 1] - 1] + 1
76 mov byte ptr
[ebp
+ edx
], al
// retarget[i + 1] = al
77 jnz
short decrementLoop
79 lea eax
, [edx
+ 1] // i = i + 1
85 mov
[ecx
+ KmpSearch::_strLen
], eax
// length of substring (without '\0')
95 __declspec(naked
) char * __fastcall
KmpSearch::search(const char *str
) {
101 mov esi
, edx
// edx: str argument
102 lea edi
, [ecx
+ KmpSearch::_subStr
]
103 lea ebx
, [ecx
+ KmpSearch::_retarget
]
104 mov ch
, byte ptr
[ecx
+ KmpSearch::_strLen
]
106 or ch
, ch
// if (_strLen == 0)
107 jz
short endOfString
// goto endOfString
109 xor edx
, edx
// index
125 cmp al
, byte ptr
[edi
+ edx
] // while (c != sub[index]) {
127 or edx
, edx
// if (index == 0)
128 jz
short searchLoop
// goto searchLoop
129 movzx edx
, byte ptr
[ebx
+ edx
] // index = retarget[index]
130 jmp
short newIndexLoop
// }
134 cmp dl
, ch
// if (index != _strLen)
135 jne
short searchLoop
// goto searchLoop
137 movzx ebx
, cl
// bytes of eax used
138 movzx ecx
, ch
// length of subStr
140 lea eax
, [esi
+ ebx
- 3]
149 xor eax
, eax
// return NULL
159 void __fastcall
KmpSearch::init(const char *subStr
) {
160 strcpy(_subStr
, subStr
);
163 char * __fastcall
KmpSearch::search(const char *str
) {
164 return strstr(str
, _subStr
);