I found a flaw again, this is a fix :) I'm learning, I'm learning :)




[size=9]

Test Case: String Source: hello cruel world
String To Search: lo

Cause: Bad Shift

Problem:

First Attempt:
hello cruel world
l

Second Attempt:
hello cruel world
l

Third Attempt:
hello cruel world
l

Fourth Attempt:
hello cruel world
lo

Fifth Attempt:

hello cruel world
l
...

As you can see between the 4th and 5th attempt it had a bad shift so,
we must return to the byte we started comparing. To fix that, here it is...

UKPM PROC USES ebx esi edi srcStr:DWORD, fndStr:DWORD

xor eax, eax
xor ebx, ebx
xor ecx, ecx
xor edx, edx
mov esi, srcStr
mov edi, fndStr

@@KPMSCAN:

inc ecx
mov dl, BYTE PTR [edi]
or edx, edx
jz @@KPMSTOPSCAN
mov al, BYTE PTR [esi+ecx-1]
or eax, eax
jz @@KPMSTOPSCAN
cmp al, dl
jne @@KPMRESETSCAN
inc edi
or ebx, ebx
jnz @@KPMSCAN
mov ebx, ecx
jmp @@KPMSCAN

@@KPMRESETSCAN:
[color=blue]
or ebx, ebx
jz @@KPMSEARCHCONTIN
mov ecx, ebx
xor ebx, ebx

@@KPMSEARCHCONTIN:
[/color]
mov edi, fndStr
jmp @@KPMSCAN

@@KPMSTOPSCAN:

or edx, edx
jnz @@KPMEXIT
or eax, eax
jz @@KPMEXIT
mov eax, ebx
ret

@@KPMEXIT:

xor eax, eax
ret

UKPM ENDP

[color=blue]
I'll just add this lame strlen for everybody to use :)
and this one has no bugs I'm pretty sure :)

Return value in ECX
[/color]

strlen PROC srcStr:DWORD

xor ecx, ecx
mov esi, srcStr

@@:

mov al, BYTE PTR [esi+ecx]
inc ecx
or al, al
jnz @b

dec ecx

ret

strlen ENDP

[/size]



Sorry for the mistake :)


I moved up the xor ebx, ebx that was after the label @@KPMSEARCHCONTIN: to save a few cycles when executing a non matching byte.
Posted on 2002-02-27 22:58:28 by stryker
I would like to thank all the people who have responded to this thread and the sites I mentioned. To wrap all things up here is a program that will do a search using this algorithm. I hope you'll find this useful. The controls of this program are pretty basic, just be careful find and find next have 2 different jobs. If you click on find it will always start at the first byte of the string, if you click on find next it will continue what has been started by the find button. Try entering a lot of string combo on the big edit box and your search terms on the small one to test its limits. I've tested this algorithm rigorously using a lot of string combinations and found :) no bugs :) If there are bugs, that you'll find, please let me know. Thank You All!!! :alright:


Happy ASMing!!!
Posted on 2002-02-28 00:57:10 by stryker
If i'm not wrong : just a little change that makes you disappear a "mov edi, fndStr" and remove a jumping overhead.
(It is untested and I'm very tired these days then please take care to test it).

Your original version in blue, my additions/changes in green

UKPM PROC USES ebx esi edi srcStr:DWORD, fndStr:DWORD

xor eax, eax
xor ebx, ebx
xor ecx, ecx
xor edx, edx
mov esi, srcStr
@@KPMRESCAN:
mov edi, fndStr

@@KPMSCAN:

inc ecx
mov dl, BYTE PTR
or edx, edx
jz @@KPMSTOPSCAN
mov al, BYTE PTR
or eax, eax
jz @@KPMSTOPSCAN
cmp al, dl
jne @@KPMRESETSCAN
inc edi
or ebx, ebx
jnz @@KPMSCAN
mov ebx, ecx
jmp @@KPMSCAN

@@KPMRESETSCAN:

or ebx, ebx
;jz @@KPMSEARCHCONTIN
jz @@KPMRESCAN
mov ecx, ebx
xor ebx, ebx

;@@KPMSEARCHCONTIN:

;mov edi, fndStr
;jmp @@KPMSCAN

jmp @@KPMRESCAN



@@KPMSTOPSCAN:

or edx, edx
jnz @@KPMEXIT
or eax, eax
jz @@KPMEXIT
mov eax, ebx
ret

@@KPMEXIT:

xor eax, eax
ret

UKPM ENDP
Posted on 2002-02-28 01:53:30 by JCP
and if you reorganize a bit your initialization code you can suppress a xor ebx, ebx somewhere... but I'm not sure if it would not result in a bit slower initialization code (pairing).
I can't benchmark nor test here : annoying. :mad:
Posted on 2002-02-28 02:10:31 by JCP
Readiosys, that's great, I tested it and it worked!!! :alright: great job. And I must say, I've learned a lot :) But as for xor ebx, ebx you really need to have it as part of the initialization. Because the problem always lies if the match is found at the first byte. Anyway, I'll do some benchmarking tomorrow, it's getting late here.

BTW, yours is 1 instruction less than mine. :) Also, I tried to hide the xor ebx, ebx before a label to save a cycle during a first byte mismatch.

:)
Posted on 2002-02-28 02:38:41 by stryker
First, I'm happy it worked and it is smaller and faster. ;)
It is possible we can do even more things like that... I only had a quick look to it...

About ebx, I know you need it but I was thinking to do something like :



xor eax, eax
xor ebx, ebx
xor ecx, ecx
xor edx, edx
mov esi, srcStr
@@KPMRESCAN:
mov edi, fndStr


becomes



xor eax, eax
xor ecx, ecx
xor edx, edx
mov esi, srcStr
[color=green]@@KPMRESCANebx:
xor ebx, ebx[/color]
@@KPMRESCAN:
mov edi, fndStr


---



or ebx, ebx
jz @@KPMRESCAN
mov ecx, ebx
xor ebx, ebx
jmp @@KPMRESCAN


becomes



or ebx, ebx
jz @@KPMRESCAN
mov ecx, ebx
[color=blue];xor ebx, ebx ;We do not need it to be there anymore[/color]
[color=green]jmp @@KPMRESCANebx[/color]


The xor ebx, ebx dissapeared but is still executed... it is only a size optimization, I don't really think it will be faster...
The inconvenient is the changes in the initialization routine perhaps breaks some pairing rules... it is something to test... and if it works well, please find a better name for the label @@KPMRESCANebx : the name I gave to is not explicit at all in an algo implementation routine... ;)
Posted on 2002-02-28 02:56:04 by JCP
I'll check this out tomorrow :) I need sleep :) yawn :) to really test that it works just replace my proc on kmp.asm and try these strings for testing.

In case you want to know. This is how I test my procedures


Source String: Hello Cruel World
Search Terms: 1: He
2: llo
3: l0
4: ld
5: d
6: orld
7: ue
8: lo

Source String: elelelelelelelelelelelelelaaaaaleleleleeelllel
Search Terms: 1: el
2: le
3: al
4: la
5: lx
And lastly do anything random


I'll try to code up your idea tomorrow. Thanks!!!
Posted on 2002-02-28 03:03:50 by stryker
Ok, good night ;)

Maybe this is better for pairing : please test them both since I don't know which is the best... this second solution seems more logical than the first one though... (the four xor are rassembled into the same code block while the first one breaks this harmony by inserting the mov esi, srcStr between the xor instructions).



[color=green]mov esi, srcStr[/color]
xor eax, eax
xor ecx, ecx
xor edx, edx
@@KPMRESCANebx:
xor ebx, ebx
@@KPMRESCAN:
mov edi, fndStr
Posted on 2002-02-28 03:20:02 by JCP
Readiosys, Here it is and it still does the same thing:




[size=9]
UKPM PROC USES ebx esi edi srcStr:DWORD, fndStr:DWORD

mov esi, srcStr
xor eax, eax
xor ecx, ecx
xor edx, edx

@@KPMRESETEBX:

xor ebx, ebx

@@KPMRESCAN:

mov edi, fndStr

@@KPMSCAN:

inc ecx
mov dl, BYTE PTR [edi]
or edx, edx
jz @@KPMSTOPSCAN
mov al, BYTE PTR [esi+ecx-1]
or eax, eax
jz @@KPMSTOPSCAN
cmp al, dl
jne @@KPMRESETSCAN
inc edi
or ebx, ebx
jnz @@KPMSCAN
mov ebx, ecx
jmp @@KPMSCAN

@@KPMRESETSCAN:

or ebx, ebx
jz @@KPMRESCAN
mov ecx, ebx
jmp @@KPMRESETEBX

@@KPMSTOPSCAN:

or edx, edx
jnz @@KPMEXIT
or eax, eax
jz @@KPMEXIT
mov eax, ebx
ret

@@KPMEXIT:

xor eax, eax
ret

UKPM ENDP
[/size]



BTW, this is now 2 instructions less than the original one :)


Happy ASMing!!!
Posted on 2002-02-28 10:53:38 by stryker
Hi

I like this thread and your small "Hybrid-KPM", umberg.

Just a small question:

What is the faster method:

using Repne Scasb or the way, umberg does it (with manually increase ecx and edi, mov al, BYTE PTR and so on) ?
I was of the opinion that string instructions are faster Wrong or right?

Thx and HAND!
:cool:
Posted on 2002-02-28 11:21:54 by Rennsemmel
scasb is slower
Posted on 2002-02-28 11:24:47 by The Svin
Thanks, rensemmel. Svin's right scasb is slower, it'll take you more cycles for this instruction. I'll dig up more on MMX and change the routines to MMX ones, I should be able to remove most of the jump instruction, maybe :)
Posted on 2002-02-28 12:15:24 by stryker
We russian programmers have a joke that there are only
three men in the whole world who understand what is
KMP algorithm and how it works.
Their names are Knuth, Morris and ... you know who else :)

I see the joke can be applied not only to our programmers but
also to this whole board :)
I'm the only who say that it is not KMP algo.
I gave you already the algo with both sceme of the algo and one
possible realization.
Why do you not have a look and think how it works?

When you reset search you always start comparing from begining
of pattern string.
It is against KMP logic.
What you did is simple forward search.
You may call it UM algo but stop call it KMP algo.

Steve, you too had better learn what KMP is before confusing
umberg6007 with you remarks.
Posted on 2002-02-28 17:50:47 by The Svin
Alex,

Its sheer ignorance on my part, when I needed a table based search system, I poked through the technical data and went in the direction of BM, not KPM so I have not done the work there.

I think umberg6007 is developing a hybrid algo that may end up being a UMB search algo and I think thats great. I will leave the label for it up to him as he is the one developing it.

Regards,

hutch@movsd.com
Posted on 2002-02-28 19:23:55 by hutch--
Just converted this KPM algo - I haven't tested this, yet.
;  Knuth-Morris-Pratt Algorithm

; ==============================
; - performs the comparisons from left to right
; - preprocessing phase in O(m) space and time complexity
; - searching phase in O(n+m) time complexity (independent from the alphabet size)
; - delay bounded by log(m) where the base of the log is the golden ratio
;
;void KMP(char *x, int m, char *y, int n) {
; int i, j, kmpNext[XSIZE];
;
; /* Preprocessing */
; i = 0;
; j = kmpNext[0] = -1;
; while (i < m) {
; while (j > -1 && x[i] != x[j]) j = kmpNext[j];
; i++; j++;
; if (x[i] == x[j])
; kmpNext[i] = kmpNext[j];
; else
; kmpNext[i] = j;
; }
;
; /* Searching */
; i = j = 0;
; while (j < n) {
; while (i > -1 && x[i] != y[j]) i = kmpNext[i];
; i++; j++;
; if (i >= m) {
; OUTPUT(j - i);
; i = kmpNext[i];
; }
; }
; }

KMP PROC uses ebx esi edi, x:DWORD, m:DWORD, y:DWORD, n:DWORD
LOCAL kmpNext[256]:DWORD

_i TEXTEQU <ecx>
_i TEXTEQU <edx>
_x TEXTEQU <esi>
_y TEXTEQU <edi>

mov _x,x
mov _y,y

; Preprocessing

xor _i, _i
mov _j, -1
mov [kmpNext], _j
jmp @F
preLoop:
mov _j, [kmpNext + _j*4]
mov al,[_x + _i]
cmp al,[_x + _j]
jne preLoop
@@: inc _j
inc _i
push [kmpNext + _j*4] ; assume kmpNext[j]
mov al,[_x + _i]
cmp al,[_x + _j]
je @F
mov [esp], _j
@@: pop [kmpNext + _i*4]
cmp _i, m
jne preLoop


; Searching

xor _i, _i
xor _j, _j
sLoop:
test _i, _i
js @F
mov al, [_y + _j]
cmp al, [_x + _i]
je @F
mov _i, [kmpNext + _i*4]
jmp sLoop
@@: inc _i
inc _j
cmp _i, m
jge Output
@@: cmp _j, n
jl sLoop

mov eax,-1
ret
Output:
mov eax, _j
sub eax, _i
; mov _i, [kmpNext + _i*4]
; jmp @B ; get next...
ret
KMP ENDP
Fairly straight forward conversion - I haven't optimized, yet. :)

Edit: Already found a bugs in the conversion...will fix...

Once I have increase my understanding, then I'll code it from an assembly perspective. This is the first part of my process. Looking at the flow of the data at the machine level.

Here is some good text on the algo:
http://www1.ics.uci.edu/~eppstein/161/960227.html
PHP: http://www.iezzi.ch/algodat/kmp.php
CAML: http://pauillac.inria.fr/coq/contribs/kmp.html
C: http://www-igm.univ-mlv.fr/~lecroq/string/node8.html
Posted on 2002-02-28 20:37:54 by bitRAKE
About this very algo I can say - it IS KMP :)
I just don't understand one this - why you keep calling it
KPM - even at start of you source written:
Knuth-Morris-Pratt
so it is K M P
Posted on 2002-02-28 20:57:00 by The Svin
Ok, I'll take a look at the source code but you also have to consider the link, bitrake gave. I just want to explain how my algo works and I say it's kmp/kpm.





0 1 2 3 4 5 6 7 8 9 10 11
T: b a n a n a n o b a n o

i=0: X
i=1: X
i=2: n a n X
i=3: X
i=4: n a n o
i=5: X
i=6: n X
i=7: X
i=8: X
i=9: n X
i=10: X




You might not agree to it since I said on my earlier posts that there are variations to it, and I say mine belongs to the first one(http://www1.ics.uci.edu/~eppstein/161/960227.html ).

This site gives you an example and that's how my algo works!
Posted on 2002-02-28 21:23:31 by stryker
umberg6007:
I don't need any sites to learn anything about KMP.
Since I have all that Mr. D.Knuth wrote on my bookshelf.
Let me say it straight? May I?
I tried as I may in my previous post.
You'd better read the same site twice. And more carefull.
You analyzed just first picture-sceme and missunderstood the whole idea. One shift forward is just in WORST case. In better case shift more than one.
I'm done it's my last post on the topic.
Posted on 2002-02-28 21:45:02 by The Svin
You can have may variations to KMP, but saying mine is not KMP is wrong, and I have prove my algorithm that it does what first version of what the site says. I have noticed that what bitrake and you have done is the second one. I'm sure you are an open minded person but please for discussion sakes, take a look at that site and prove me wrong that I didn't do the KMP algo.
Posted on 2002-02-28 21:49:48 by stryker
Give me Donald Knuth work were he discribe this algo as KMP.
In the site is first step explonation is not KMP but material wich preparing learners to KMP idea.
In original it starts even earlier Knuth starts explonation from broot-force search - but it does not make broot-force search KMP algo.
Posted on 2002-02-28 21:59:39 by The Svin