This is like hitting 2 birds in one stone. :) I don't know if anybody noticed this but when using the GetDlgItemText function it actually returns the length of the string in EAX more like putting the text into the buffer as well as returning the length of the string...

I was doing this experiment to speed up the KMP algo without calling any strlen function. Since this is a requirement for KMP to determine the length of both strings.

The KMP algo has a preprocessing phase of O(m) while it searches at O(n+m) time complexity where m is the length of the string pattern and n the length of the source string. Not to mention, we also need to find the length of the string pattern and the string source before the KMP algorithm. What if the length of the source string is 65mb and the search pattern is 50k that would cost us a lot of time, running twice as slow as both preprocessing and searching combined + delay bound. Here's a program that will show you what I mean.

Usage:

1. Type in anything on the edit box.
2. Right click anywhere on the program avoiding the big edit box and a menu will appear, choose that option.
3. Look at the value of EAX on the register group box. It's the string length of text you entered on the edit box.

And if you take a look at my code there's no calling of any strlen function. :) Nice isn't it!!
Posted on 2002-03-13 01:24:19 by stryker
Nice work.

I was thinking of testing AL for zero during preproccessing and allocating the preprocessing space on the stack, but this requires reworking the algo a bit.
Posted on 2002-03-13 01:30:49 by bitRAKE
Ahh stupid me!!! I just looked at the Platform SDK it says it returns the number of TCHARs ....bzzzt sorry for the false alarm. At least everybody who didn't knew now knows!! :) I didn't knew this info exists, this was just an experiment.

Now we can speed up some algos that we think that needs any strlen function.

I was thinking before that, ESI or EDI would point to the end of the string. So, EDI/ESI - OFFSET PatternString would equal to the length of the string, but I was wrong. Maybe we could experiment more on other win32 API functions and observe the register values for patterns... That would be great isn't it. :) Who knows what we'll discover.

You know what? That stack idea is nice rather than the dynamic memory allocation I went through. That would speed up things.
Posted on 2002-03-13 01:30:50 by stryker
No no no, you can *NOT* depend on register values after calling
an API :). ESI/EDI/EBX will be preserved anyway, and who knows
what trash will be in ECX/EDX. It could very well change very much
depending on windows version.

And as for the string length returned by GetDlgItemText... it does
pay off to read the PlatformSDK, doesn't it? ;)


Now we can speed up some algos that we think that needs any strlen function.

You can't speed up the algo itself, but you can speed up the use of
it a bit... there's quite a difference.
Posted on 2002-03-13 07:50:02 by f0dder
No no no, you can *NOT* depend on register values after calling an API . ESI/EDI/EBX will be preserved anyway, and who knows what trash will be in ECX/EDX. It could very well change very much depending on windows version.
I know these would be save but I didn't assume any registers to be save during any API call just for the sake of experiment. I was building my theory not to assume anything. And rely on other register values for patterns that might be of use.
You can't speed up the algo itself, but you can speed up the use of it a bit... there's quite a difference.
I meant, the whole time(reduce any API or function calls) not just inside the KMP but before it including Mem. Allocation, getting the string from the edit box, finding the length of the strings...(We can now remove the use of strlen function) :) Sorry for the misunderstanding.

Just call me. The scavenger :grin:
Posted on 2002-03-13 08:40:18 by stryker