tools/skycpt/KmpSearch.cpp

   1 /* ScummVM Tools
   2  * Copyright (C) 2007 The ScummVM project
   3  *
   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.
   8
   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.
  13
  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.
  17  *
  18  * $URL$
  19  * $Id$
  20  *
  21  */
  22
  23 #include "stdafx.h"
  24 #include "KmpSearch.h"
  25 #include <stdio.h>
  26 #include <stdlib.h>
  27 #include <string.h>
  28
  29 #ifdef _MSC_VER
  30
  31 __declspec(naked) void __fastcall KmpSearch::init(const char *subStr) {
  32         __asm {
  33                 // kmp initialization, make jump table for mismatches
  34                 push esi
  35                 push edi
  36                 push ebp
  37                 push ebx
  38                 push ecx
  39
  40                 mov esi, edx // edx: subStr argument
  41                 lea edi, [ecx + KmpSearch::_subStr]   // this + 0x100
  42                 lea ebx, [ecx + KmpSearch::_retarget] // this
  43                 lea ebp, [ecx + 1]
  44
  45                 mov byte ptr [ebx], -1
  46
  47                 xor eax, eax
  48
  49                 loopStart:
  50                         shr ecx, 8
  51                         test al, 3
  52                         jnz short dontLoad
  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
  55                                 lea edi, [edi + 4]
  56                         dontLoad:
  57
  58                         or cl, cl                                    // end of subStr?
  59                         jz short endOfString
  60
  61                         mov edx, eax                         // save counter (i) in edx
  62
  63                         xlat                                         // al = retarget[i]
  64                         inc al
  65                         mov byte ptr [ebp + edx], al // retarget[i + 1] = retarget[i] + 1
  66                         jz short decLoopEnd
  67                                 decrementLoop:
  68                                         dec al
  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
  72
  73                                         xlat                                                    // al = retarget[retarget[i + 1] - 1]
  74                                         xor ah, ah
  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
  78                         decLoopEnd:
  79                         lea eax, [edx + 1]                   // i = i + 1
  80                 jmp short loopStart
  81
  82                 endOfString:
  83
  84                 pop ecx         // this
  85                 mov [ecx + KmpSearch::_strLen], eax // length of substring (without '\0')
  86
  87                 pop ebx
  88                 pop ebp
  89                 pop edi
  90                 pop esi
  91                 ret
  92         }
  93 }
  94
  95 __declspec(naked) char * __fastcall KmpSearch::search(const char *str) {
  96         __asm {
  97                 push esi
  98                 push edi
  99                 push ebx
 100
 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]
 105
 106                 or  ch, ch                              // if (_strLen == 0)
 107                 jz  short endOfString   //         goto endOfString
 108
 109                 xor edx, edx    // index
 110
 111                 mov cl, 3
 112                 searchLoop:
 113                         shr eax, 8
 114                         inc cl
 115                         test cl, 4
 116                         jz short skipRead
 117                                 lodsd
 118                                 xor cl, cl
 119                         skipRead:
 120
 121                         test al, al
 122                         jz short endOfString
 123
 124                         newIndexLoop:
 125                                 cmp al, byte ptr [edi + edx]     // while (c != sub[index]) {
 126                                 jz short gotNewIndex
 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                           // }
 131
 132                         gotNewIndex:
 133                         inc edx
 134                         cmp dl, ch                // if (index != _strLen)
 135                 jne short searchLoop  //        goto searchLoop
 136
 137                 movzx ebx, cl   // bytes of eax used
 138                 movzx ecx, ch   // length of subStr
 139
 140                 lea eax, [esi + ebx - 3]
 141                 sub eax, ecx
 142
 143                 pop ebx
 144                 pop edi
 145                 pop esi
 146                 ret
 147
 148                 endOfString:
 149                 xor eax, eax    // return NULL
 150                 pop ebx
 151                 pop edi
 152                 pop esi
 153                 ret
 154         }
 155 }
 156
 157 #else
 158
 159 void __fastcall KmpSearch::init(const char *subStr) {
 160         strcpy(_subStr, subStr);
 161 }
 162
 163 char * __fastcall KmpSearch::search(const char *str) {
 164         return strstr(str, _subStr);
 165 }
 166
 167 #endif
 168