Finding substring in assembly

Question

I'm wondering if there is a more efficient method to finding a substring in assembly then what I am currently planning to do.

I know the string instruction "scansb/scasw/scads" can compare a value in EAX to a value addressed by EDI. However, as far as I understand, I can only search for one character at a time using this methodology.

So, if I want to find the location of "help" in string "pleasehelpme", I could use scansb to find the offset of the h, then jump to another function where I compare the remainder. If the remainder isn't correct, I jump back to scansb and try searching again, this time after the previous offset mark.

However, I would hate to do this and then discover there is a more efficient method. Any advice? Thanks in advance

Answer 1

There are indeed more efficient ways, both instruction-wise and algorithmically.

If you have the hardware you can use the sse 4.2 compare string functions, which are very fast. See an overview http://software.intel.com/sites/products/documentation/studio/composer/en-us/2009/compiler_c/intref_cls/common/intref_sse42_comp.htm and an example using the C instrinsics http://software.intel.com/en-us/articles/xml-parsing-accelerator-with-intel-streaming-simd-extensions-4-intel-sse4/

If you have long substrings or multiple search patterns, the Boyer-Moore, Knuth-Morris-Pratt and Rabin-Karp algorithms may be more efficient.

Answer 2

scansb is the assembly variant for strcmp, not for strstr. if you want a really efficient method, then you have to use better algorithm.

For example, if you search in a long string, then you could try some special algorithms: http://en.wikipedia.org/wiki/String_searching_algorithm

Answer 3

I don't think there is a more efficient method (only some optimizations that can be done to this method). Also this might be of interest.