Assembly code snippets

Details

Title	Knuth-Morris-Pratt String Search Algorithm
Author	stryker
Submitted by:	stryker
Date added:	2002-03-21 01:20:39
Date modified:	2002-03-21 01:20:39

Comments

Parameters:
StringSource - A pointer to a null terminated string
SourceLength - The length of the string, StringSource
StringPattern - A pointer to a null terminated string
Patternlength - The length of the string, StringPattern
ShiftTable - A pointer to an array of DWORDs.

Return Values: (in EAX)
-1 == String not found.
N >= 0 == Position of the string.

Note: ShiftTable is an array of DWORDs. The number of elements in the array is calculated as PatternLength + 1. This is best suited to be dynamically allocated, since we don't want to assume a range limit. If you do dynamic memory allocation use this equation to determine the number of bytes to allocate: # of bytes to allocate = (PatternLength+1)*4

Snippet

;Check out a sample program on win32asmcommunity.net under Algorithms and Source Code section.

KMP PROC USES ebx esi edi StringSource:DWORD, SourceLength:DWORD, StringPattern:DWORD, PatternLength:DWORD, ShiftTable:DWORD

    mov     eax, PatternLength
    push    eax
    mov     eax, SourceLength
    push    eax
    mov     eax, 0FFFFFFFFh
    mov     ebx, ShiftTable
    xor     ecx, ecx
    mov     [ebx][ecx*04h], eax
    mov     esi, StringSource
    mov     edi, StringPattern

    @@GENERATE_TABLE:

        cmp     ecx, DWORD PTR [esp+04h]
        je      @@TABLE_FINISHED

    @@INNER_TABLE_LOOP:

        test    eax, eax
        js      @@CONTINUE_TABLE
        mov     dl, BYTE PTR [edi+ecx]
        cmp     dl, BYTE PTR [edi+eax]
        je      @@CONTINUE_TABLE
        mov     eax, [ebx][eax*04h]
        jmp     @@INNER_TABLE_LOOP

    @@CONTINUE_TABLE:

        inc     ecx
        inc     eax
        mov     dl, BYTE PTR [edi+ecx]
        cmp     dl, BYTE PTR [edi+eax]
        jne     @@SHIFTTABLE_VALUE_IS_EAX
        mov     edx, [ebx][eax*04h]
        mov     [ebx][ecx*04h], edx
        jmp     @@GENERATE_TABLE

    @@SHIFTTABLE_VALUE_IS_EAX:

        mov     [ebx][ecx*04h], eax
        jmp     @@GENERATE_TABLE

    @@TABLE_FINISHED:

    xor     eax, eax
    xor     ecx, ecx

    @@KMP_SEARCH:

        cmp     eax, DWORD PTR [esp]
        je      @@KMP_END
        cmp     ecx, DWORD PTR [esp+04h]
        je      @@KMP_END

    @@INNER_KMP:

        test    ecx, ecx
        js      @@KMP_CONTINUE
        mov     dl, BYTE PTR [esi+eax]
        cmp     dl, BYTE PTR [edi+ecx]
        je      @@KMP_CONTINUE
        mov     ecx, [ebx][ecx*04h]
        jmp     @@INNER_KMP

    @@KMP_CONTINUE:

        inc     eax
        inc     ecx
        jmp     @@KMP_SEARCH

    @@KMP_END:

        pop     edx
        pop     edx

        cmp     ecx, edx
        jne     @@STRING_NOT_FOUND

        sub     eax, edx
        ret

    @@STRING_NOT_FOUND:

        mov     eax, 0FFFFFFFFh
        ret

KMP ENDP